溢出GMP戰俘

Question

處理（我只在GMP庫的間接用戶主要通過swi-prolog和yap，但我解決這個問題我很感興趣。）

當執行與大的離譜值指數運算，主機系統或GMP不再能夠適當地處理溢出。我已經與上述系統的開發人員進行了交流，但他們沒有看到這方面的簡單解決方案。

這個問題是否爲其他GMP系統/用戶所知？你如何處理這種溢出？

作爲健全性檢查第一測試7^7^7這應該是值：375982 ... 32343

在32位系統中，例如查詢?- X is 13^1150000000.收率這樣的溢出。以下是YAP給出：

 
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處理）。

Answer 1

嗯，看來我的運氣：

Even the most recent version確實

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

至少這個溢出處理，不能被用作攻擊。

而任何使用GMP的系統都沒有這個問題，必須使用修改過的庫或者重複估計尺寸的功能。

Answer 2

13^1,150,000,000是約2^4,255,505,675，其中需要4,255,505,675比特來表示。 每個字節8位，這是大約500 MB的內存。 似乎它應該適合。

也許在計算中涉及到幾個臨時變量，它超過了處理大小限制。

Answer 3

看起來，如果你有克雷敷設，它會工作。

#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

的東西，有些人做，以解決此問題（不支持它泄露了一些記憶，但他們覺得比沒有好）：GMP，您可以指定更換分配器（mp_set_memory_functions）。從這個分配器中，你可以調用malloc，如果失敗，你可以拋出一個C++異常（如果你使用gcc，請用-fexceptions重新編譯gmp），或者調用longjmp或類似的東西來繞過GMP的失敗處理並跳回到你控制的代碼。

Answer 5

不是一個真正的答案，而是SWI-Prolog的解釋。首先，它估計是否可能發生溢出 。如果確定的話，它會在調用GMP之前產生錯誤。否則， 依賴於GMP分配掛鉤，並在失敗時執行longjmp（）。它會跟蹤哪些內存分配用於分配內存，並釋放分配給中止的GMP操作的內存。它可以做到這一點，因爲記憶永遠不會永久在GMP的控制之下。成功的 GMP計算結果被複制到Prolog堆棧並受Prolog內存管理。

這用於工作，但它在最近的版本中不起作用。我懷疑GMP估計的大小爲 ，如果知道這將失敗，甚至不會打擾調用malloc（）鉤子。我所需要的是確保鉤子始終被調用的方法，即使具有可笑的巨大價值。任何大於size_t可以表示的東西都可以用（size_t）-1調用鉤子。

P.s.由於複製到（較小的）Prolog運行時堆棧，它比內存可以存儲的時間早得多。