Overflow xử lý trong GMP pow

Question

(Tôi chỉ là một người sử dụng gián tiếp của GMP-thư viện chủ yếu thông qua swi-prolog và yap. Nhưng tôi rất quan tâm đến việc sửa chữa vấn đề này.)

Khi thực hiện exponentiations với các giá trị ridiculously lớn, các hệ thống máy chủ hoặc GMP không còn có khả năng xử lý các tràn một cách thích hợp. Tôi đã nói chuyện với các nhà phát triển của các hệ thống trên, nhưng họ không thấy một sửa chữa dễ dàng cho việc này.

Vấn đề này có được biết đến với các hệ thống/người dùng GMP khác không? Làm thế nào để bạn xử lý tràn như vậy?

Là một kiểm tra sanity đầu tiên kiểm tra giá trị trong 7^7^7 mà nên là: 375.982 ... 32343

Trên các hệ thống 32-bit, ví dụ như sản lượng truy vấn ?- X is 13^1150000000. như một tràn. Đây là những gì YAP cho:

 
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) 

---

Chỉnh sửa: Điều này cũng đúng cho các hệ thống 64-bit; như vậy:

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 

Tuy nhiên,

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

Và từ bên dưới:

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

Vì vậy, nếu con số này đủ lớn, các lỗi được phát hiện bởi SWI - và do đó có thể xử lý bởi SWI (L ERI: tin nhắn là bởi SWI).

Answer 1

Vâng, có vẻ như tôi không gặp may:

Even the most recent version không

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

Ít nhất tràn này được xử lý và không thể được sử dụng như một khai thác.

Và bất kỳ hệ thống nào sử dụng GMP không có vấn đề này phải sử dụng thư viện sửa đổi hoặc nhân đôi chức năng để ước tính kích thước.

Answer 2

13^1,150.000.000 là khoảng 2^4,255,505,675, có 4,255,505,675 bit để đại diện. Với 8 bit mỗi byte, đây là khoảng 500 MB bộ nhớ. Có vẻ như nó phải phù hợp.

Có thể có một vài biến tạm thời liên quan đến tính toán và vượt quá giới hạn kích thước quy trình.

Answer 3

Có vẻ như nếu bạn có một chiếc Cray nằm xung quanh, nó sẽ hoạt động.

#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

Cái gì mà một số người làm gì để làm việc xung quanh vấn đề này (không được hỗ trợ và nó rò rỉ một số bộ nhớ, nhưng họ nhận thấy nó còn hơn không): GMP phép bạn chỉ định một cấp phát thay thế (mp_set_memory_functions). Từ bộ cấp phát này, bạn có thể gọi malloc và nếu nó thất bại, bạn có thể ném một ngoại lệ C++ (nếu bạn sử dụng gcc, hãy biên dịch lại gmp với -fexceptions) hoặc gọi longjmp hoặc một cái gì đó tương tự để bỏ qua xử lý lỗi của GMP và nhảy ngược lại mã bạn kiểm soát.

Answer 5

Không thực sự là câu trả lời, nhưng giải thích những gì SWI-Prolog làm.Trước hết, nó ước tính liệu có thể xảy ra tràn hay không. Nếu nó chắc chắn, nó sẽ gây ra lỗi trước khi gọi GMP. Nếu không, nó dựa trên móc phân bổ GMP và thực hiện một longjmp() trên thất bại. Nó theo dõi trong đó phân bổ được thực hiện cho những gì và deallocates bộ nhớ được phân bổ cho các hoạt động GMP bị hủy bỏ. Nó có thể làm như vậy bởi vì bộ nhớ không bao giờ được kiểm soát lâu dài bởi GMP. Kết quả thành công Tính toán GMP được sao chép vào ngăn xếp Prolog và tùy thuộc vào quản lý bộ nhớ Prolog.

Điều này được sử dụng để hoạt động nhưng không hoạt động trong các phiên bản gần đây. Tôi nghi ngờ rằng GMP ước tính kích thước và thậm chí không bận tâm gọi móc malloc() nếu nó biết điều này sẽ thất bại. Tất cả những gì tôi cần là một cách để đảm bảo rằng móc luôn luôn được gọi, ngay cả với một giá trị cực kỳ lớn. Mọi thứ lớn hơn kích thước của size_t có thể gọi là hook với (size_t) -1.

P.s. nó tràn sớm hơn nhiều so với bộ nhớ có thể lưu trữ vì sao chép vào các ngăn xếp thời gian chạy Prolog (nhỏ hơn).