Überlauf-Handling in GMP pow

Question

(Ich bin nur ein indirekter Benutzer der GMP-Bibliothek in erster Linie durch swi-prolog und yap. Aber ich bin sehr daran interessiert, dieses Problems bei der Festsetzung.)

Wenn Exponentiationen mit lächerlich großen Werten durchgeführt wird, Die Host-Systeme oder GMP sind nicht mehr in der Lage, die Überläufe angemessen zu behandeln. Ich habe mit den Entwicklern der obigen Systeme gesprochen, aber sie sehen keine einfache Lösung dafür.

Ist dieses Problem anderen GMP-Systemen/Benutzern bekannt? Wie gehst du mit solchen Überläufen um?

Als Plausibilitätsprüfpunktfunktion zuerst für den Wert Test 7^7^7, das sein soll: 375982 ... 32343

Auf 32-Bit-Systemen, zum Beispiel eines Überlauf der Abfrage ?- X is 13^1150000000. Ausbeuten solche. Hier ist, was YAP gibt:

 
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: Dies gilt auch für 64-Bit-Systeme; etwa 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 

jedoch

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

Und von unten:

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

Also, wenn die Zahl groß genug ist, wird der Fehler durch SWI erkannt - und damit sein behandelt von SWI (Der Fehler: Nachricht ist von SWI).

Answer 1

Nun, es scheint, ich bin kein Glück:

Even the most recent version tut

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

Zumindest Überlauf behandelt wird und nicht als ein Exploit verwendet werden kann.

Und jedes System, das GMP verwendet, das dieses Problem nicht aufweist, muss entweder eine geänderte Bibliothek verwenden oder die Funktionalität zum Schätzen der Größe duplizieren.

Answer 2

13^1,150,000,000 ist etwa 2^4.255.505,675, die 4,255,505,675 Bits zu repräsentieren. Mit 8 Bits pro Byte sind dies rund 500 MB Speicher. Scheint so, als sollte es passen.

Möglicherweise sind einige temporäre Variablen in die Berechnung involviert und die Prozessgrößenbeschränkung wurde überschritten.

Answer 3

Sieht aus, als ob Sie einen Cray herumliegen haben, würde es funktionieren.

#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 

Answer 4

Etwas, das einige Leute tun, um dieses Problem zu arbeiten (nicht unterstützt und es leckt etwas Speicher, aber sie finden es besser als nichts): GMP können Sie einen Ersatz allocator angeben (mp_set_memory_functions). Von diesem Zuordner können Sie malloc aufrufen und wenn es fehlschlägt, können Sie eine C++ Ausnahme auslösen (wenn Sie gcc verwenden, bitte gmp mit -fexceptions neu kompilieren) oder longjmp oder etwas Ähnliches aufrufen, um GMPs Fehlerbehandlung zu umgehen und zurück zu dem von Ihnen kontrollierten Code zu springen.

Answer 5

Nicht wirklich eine Antwort, aber eine Erklärung, was SWI-Prolog tut.Zunächst wird geschätzt, ob ein Überlauf auftreten kann. Wenn es sicher ist, wird vor dem Aufruf von GMP ein Fehler auftreten. Andernfalls wird auf die GMP-Zuweisung Hook und führt eine Longjmp() bei Fehler. Es verfolgt, welche Zuweisungen für was gemacht werden, und hebt den Speicher auf, der für die abgebrochene GMP-Operation zugewiesen wurde. Es kann dies tun, weil Speicher nie permanent unter Kontrolle von GMP ist. Die Ergebnisse der erfolgreichen GMP-Berechnungen werden in den Prolog-Stack kopiert und unterliegen der Prolog-Speicherverwaltung.

Dies funktioniert, aber es funktioniert nicht in den letzten Versionen. Ich vermute, dass GMP die Größe schätzt und nicht einmal den malloc() Haken aufruft, wenn er weiß, dass dies fehlschlagen wird. Alles, was ich brauche, ist eine Möglichkeit, sicherzustellen, dass der Hook immer aufgerufen wird, sogar mit einem lächerlich hohen Wert. Alles, was größer ist als das, was size_t darstellen kann, könnte den Hook mit (size_t) -1 aufrufen.

Ps.s. es überläuft viel früher, als was Speicher speichern kann, aufgrund des Kopierens auf die (kleineren) Prolog-Laufzeitstacks.