Overflow handling in GMP pow

Question

(I am only an indirect user of the GMP-library primarily through swi-prolog and yap. But I am very much interested in fixing this problem.)

When performing exponentiations with ridiculously large values, the host-systems or GMP are no longer able to handle the overflows appropriately. I have talked to the developers of above systems, but they do not see an easy fix for this.

Is this problem known to other GMP systems/users? How do you handle such overflows?

As a sanity check first test the value for 7^7^7 which should be: 375982...32343

On 32-bit systems, for example the query ?- X is 13^1150000000. yields such an overflow. Here is what YAP gives:

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) 

---

Edit: This is also true for 64-bit systems ; like so:

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

However,

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

And from below:

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

So, if the number is large enough, the error is detected by SWI - and thus can be handled by SWI (The ERROR: message is by SWI).

Kioto

Answer 1

Not really an answer, but an explanation what SWI-Prolog does. First of all, it estimates whether an overflow may occur. If it is sure, it will raise an error before calling GMP. Otherwise, it relies on the GMP allocation hook and performs a longjmp() on failure. It keeps track of which allocations are made for what and deallocates memory allocated for the aborted GMP operation. It can do so because memory is never permanently under control of GMP. The results of successful GMP computations are copied to the Prolog stack and subject to Prolog memory management.

This used to work, but it doesn't work in recent versions. I suspect that GMP estimates the size and doesn't even bother calling the malloc() hook if it knows this is going to fail. All I need is a way to make sure that the hook is always called, even with a ridiculously large value. Everything that is larger than what size_t can represent could call the hook with (size_t)-1.

P.s. it overflows much earlier than what memory can store because of the copying to the (smaller) Prolog runtime stacks.

Benyamin

Answer 2

Something that some people do to work around this issue (unsupported and it leaks some memory, but they find it better than nothing): GMP lets you specify a replacement allocator (mp_set_memory_functions). From this allocator, you can call malloc and if it fails you can throw a C++ exception (if you use gcc, please recompile gmp with -fexceptions) or call longjmp or something similar to bypass GMP's failure handling and jump back to code you control.

Superman

Thank you! Need to digest this for some time :-)! – Kioto

Answer 3

Well, it seems I am out of luck:

Even the most recent version does

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

At least this overflow is handled and cannot be used as an exploit.

And any system using GMP that does not have this problem must use either a modified library or duplicate the functionality for estimating the size.

Kioto

Answer 4

13^1,150,000,000 is about 2^4,255,505,675 which take 4,255,505,675 bits to represent. With 8 bits per byte, this is around 500 MB of memory. Seems like it should fit.

Maybe there are a couple of temporary variables involved in the computation and it exceeded the process size limitation.

Callant

In recent versions it prints out the message and aborts. In this manner the overflow cannot be handled by the application. In this case SWI-Prolog – Kioto

Answer 5

Looks like if you have a Cray laying around, it would work.

#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

Callant

To be sure: What I am interested in is to get a clean error that can be handled by SWI directly. – Kioto

On UNIX abort() generates signal SIGABRT. If you have a handler for SIGABRT, the process will not die. – Callant

Unfortunately, too coarse: Overflow is usually handled by the user-provided malloc. Except in cases as such. – Kioto

A possible solution might be to demand (-1) many bytes or similar. – Kioto