Обработка переполнения в GMP pow

(Я являюсь непрямым пользователем библиотеки GMP, главным образом через swi-prolog и yap.Но я очень заинтересован в решении этой проблемы.)

При выполнении возведения в степень со смехотворно большими значениями хост-системы или GMP больше не могут правильно обрабатывать переполнения. Я разговаривал с разработчиками вышеуказанных систем, но они не видят простого решения этой проблемы.

Известна ли эта проблема другим системам/пользователям GMP? Как вы справляетесь с такими переполнениями?

В качестве проверки работоспособности сначала проверьте значение для 7 ^ 7 ^ 7, которое должно быть: 375982...32343.

В 32-битных системах, например, запрос ?- X is 13^1150000000. приводит к такому переполнению. Вот что дает ЯП:

GNU gdb (GDB) 7.0-ubuntu
Copyright (C) 2009 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later 
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "i486-linux-gnu".
For bug reporting instructions, please see:
...
Reading symbols from /opt/gupu/src/yap-6.3/narch-gupu2/yap...done.
(gdb) run -f
Starting program: /opt/gupu/src/yap-6.3/narch-gupu2/yap -f
YAP 6.3.2 (i686-linux): Sun Nov 11 04:19:37 CET 2012
?- X is 13^1150000000.

Program received signal SIGSEGV, Segmentation fault.
0x001638d8 in ?? () from /usr/lib/libgmp.so.3
(gdb) bt
#0  0x001638d8 in ?? () from /usr/lib/libgmp.so.3
#1  0x00164470 in __gmpn_mul_fft () from /usr/lib/libgmp.so.3
#2  0x001646c2 in __gmpn_mul_fft_full () from /usr/lib/libgmp.so.3
#3  0x00165f28 in __gmpn_sqr_n () from /usr/lib/libgmp.so.3
#4  0x0014b58b in __gmpz_n_pow_ui () from /usr/lib/libgmp.so.3
#5  0x0014c4a1 in __gmpz_pow_ui () from /usr/lib/libgmp.so.3
#6  0x080c4a1d in Yap_gmp_exp_int_int (i1=13, i2=1150000000) at ../C/gmp_support.c:939
#7  0x0815f9df in p_exp (t1=, t2=3082051592) at ../C/arith2.c:609
#8  0x080b1f19 in Eval (t=0) at ../C/eval.c:147
#9  0x080b2251 in p_is () at ../C/eval.c:186
#10 0x0806b56a in Yap_absmi (inp=0) at ../C/absmi.c:6912
#11 0x080b3655 in exec_absmi (top=) at ../C/exec.c:1002
#12 0x080b3b1f in do_goal (t=, CodeAdr=, arity=, 
    pt=0x0, top=1) at ../C/exec.c:1068
#13 0x080b3d1d in Yap_RunTopGoal (t=135918154) at ../C/exec.c:1291
#14 0x08061a6f in YAP_RunGoalOnce (t=135918154) at ../C/c_interface.c:2511
#15 0x0805c2f5 in do_top_goal (argc=2, argv=0xbffff4c4) at ../console/yap.c:84
#16 exec_top_level (argc=2, argv=0xbffff4c4) at ../console/yap.c:131
#17 main (argc=2, argv=0xbffff4c4) at ../console/yap.c:172
(gdb)

Изменить: это также верно для 64-битных систем; вот так:

Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.3.5)
Copyright (c) 1990-2012 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- X is 3445^2^62.
gmp: overflow in mpz type
Abort

Тем не мение,

?- X is 2^2^63.
ERROR: Out of global stack
?- X is 2^2^62.
gmp: overflow in mpz type
Abort

И снизу:

?- X is 2^2^36.
ERROR: Out of global stack
?- X is 2^2^37.
gmp: overflow in mpz type
Abort

Таким образом, если число достаточно велико, ошибка обнаруживается SWI и, следовательно, может быть обработана SWI (сообщение ERROR: от SWI).


c gmp biginteger swi-prolog yap
person false    schedule 11.11.2012    source источник

Ответы (5)


arrow_upward
5
arrow_downward

Не совсем ответ, а объяснение того, что делает SWI-Prolog. Прежде всего, он оценивает, может ли произойти переполнение. Если он уверен, он вызовет ошибку перед вызовом GMP. В противном случае он полагается на ловушку распределения GMP и выполняет longjmp() в случае неудачи. Он отслеживает, какие выделения для чего сделаны, и освобождает память, выделенную для прерванной операции GMP. Это возможно, потому что память никогда не находится под постоянным контролем GMP. Результаты успешных вычислений GMP копируются в стек Prolog и подлежат управлению памятью Prolog.

Раньше это работало, но не работает в последних версиях. Я подозреваю, что GMP оценивает размер и даже не вызывает хук malloc(), если знает, что это не удастся. Все, что мне нужно, это способ убедиться, что хук всегда вызывается, даже если его значение смехотворно велико. Все, что больше, чем может представлять size_t, может вызывать хук с (size_t)-1.

P.S. он переполняется намного раньше, чем может хранить память, из-за копирования в (меньшие) стеки времени выполнения Prolog.

person Jan Wielemaker    schedule 09.01.2013

arrow_upward
4
arrow_downward

Кое-что, что некоторые люди делают, чтобы обойти эту проблему (не поддерживается и приводит к утечке памяти, но они считают, что это лучше, чем ничего): GMP позволяет указать заменяющий распределитель (mp_set_memory_functions). Из этого распределителя вы можете вызвать malloc, и в случае сбоя вы можете сгенерировать исключение C++ (если вы используете gcc, перекомпилируйте gmp с параметром -fexceptions) или вызвать longjmp или что-то подобное, чтобы обойти обработку ошибок GMP и вернуться к коду, которым вы управляете.

person Marc Glisse    schedule 09.01.2013
comment
Спасибо! Нужно переварить это на некоторое время :-)! - person false; 09.01.2013

arrow_upward
2
arrow_downward

Что ж, похоже, мне не повезло:

даже самая последняя версия

   fprintf (stderr, "gmp: overflow in mpz type\n");
   abort ();

По крайней мере, это переполнение обрабатывается и не может быть использовано в качестве эксплойта.

И любая система, использующая GMP, в которой нет этой проблемы, должна использовать либо модифицированную библиотеку, либо дублировать функционал для оценки размера.

person false    schedule 14.11.2012

arrow_upward
2
arrow_downward

13 ^ 1 150 000 000 - это примерно 2 ^ 4 255 505 675, для представления которых требуется 4 255 505 675 бит. С 8 битами на байт это около 500 МБ памяти. Вроде должно подойти.

Возможно, в вычислениях задействована пара временных переменных, и это превысило ограничение на размер процесса.

person brian beuning    schedule 11.12.2012
comment
В последних версиях он распечатывает сообщение и прерывает работу. Таким образом, приложение не может обработать переполнение. В этом случае SWI-Prolog - person false; 12.12.2012

arrow_upward
1
arrow_downward

Похоже, если у вас есть Cray, это сработает.

#if defined (_CRAY) && ! defined (_CRAYMPP)
/* plain `int' is much faster (48 bits) */
#define __GMP_MP_SIZE_T_INT     1
typedef int         mp_size_t;
typedef int         mp_exp_t;
#else
#define __GMP_MP_SIZE_T_INT     0
typedef long int        mp_size_t;
typedef long int        mp_exp_t;
#endif
person brian beuning    schedule 13.12.2012
comment
Чтобы быть уверенным: что меня интересует, так это получить чистую ошибку, которая может быть обработана SWI напрямую. - person false; 13.12.2012
comment
В UNIX функция abort() генерирует сигнал SIGABRT. Если у вас есть обработчик SIGABRT, процесс не умрет. - person brian beuning; 13.12.2012
comment
К сожалению, слишком грубо: переполнение обычно обрабатывается предоставленным пользователем malloc. За исключением случаев как таковых. - person false; 13.12.2012
comment
Возможное решение может состоять в том, чтобы потребовать (-1) много байтов или подобное. - person false; 13.12.2012