c-GMP pow中的溢出处理



(我只是GMP库的间接用户,主要通过swi-prolog和yap。但我对解决这个问题非常感兴趣。)

当用大得离谱的值执行幂运算时,主机系统或GMP将无法再适当地处理溢出。我已经和上述系统的开发人员谈过了,但他们认为没有一个简单的解决方案。

其他GMP系统/用户是否知道这个问题?你是如何处理这种溢出的?

作为健全性检查,首先测试7^7^7的值,该值应为:375982…32343

例如,在32位系统上,查询?- X is 13^1150000000.会产生这样的溢出。以下是YAP提供的:

GNU gdb(gdb)7.0-ubuntu版权所有(C)2009自由软件基金会,股份有限公司。许可证GPLv3+:GNU GPL版本3或更高版本这是免费软件:你可以自由更改和重新分发它。在法律允许的范围内,不存在任何担保。键入"显示复制"以及"显示保修"以了解详细信息。这个GDB被配置为"i486-linux-gnu"。有关错误报告说明,请参阅:。。。从/opt/gupu/src/yap-6.3/narch-gupu2/yap读取符号…完成。(gdb)运行-f启动程序:/opt/gupu/src/yap-6.3/narch-gupu2/yap-fYAP 6.3.2(i686 linux):2012年11月11日星期日欧洲中部时间04:19:37?-X为13^1150000000。程序接收到信号SIGSEGV,分段故障。0x001638d8英寸??()来自/usr/lib/libgmp.so.3(gdb)bt#0 0x001638d8英寸??()来自/usr/lib/libgmp.so.3#1来自/usr/lib/libgmp.so的__gmpn_mul_fft()中的0x00164470。3#2来自/usr/lib/libgmp.so的__gmpn_mul_fft_full()中的0x001646c2。3#3来自/usr/lib/libgmp.so.3的__gmpn_sqr_n()中的0x00165f28#4来自/usr/lib/libgmp.so的__gmpz_n_pow_ui()中的0x0014b58b。3#来自/usr/lib/libgmp.so.3的__gmpz_pow_ui()中的5 0x0014c4a1Yap_gmp_exp_int_int(i1=13,i2=115000000)中的#6 0x080c4a1d/C/gmp_support.C:939#7 p_exp中的0x0815f9df(t1=,t2=3082051592)在/C/arith2.C:609#8 0x080b1f19,Eval(t=0)中/C/eval.C:147#p_is()中的9 0x080b2251位于/C/eval.C:186#Yap_absmi(inp=0)中的10 0x0806b56a/C/absmi.C:6912#位于..的exec_absmi(顶部=)中的11 0x080b3655/C/exec.C:1002#do_goal中的12 0x080b3b1f(t=,CodeAdr=,arity=,pt=0x0,top=1)在/C/exec.C:1068#Yap_RunTopGoal(t=135918154)中的13 0x080b3d1d,位于/C/exec.C:1291#14 0x08061a6f在..处的YAP_RunGoalOnce(t=135918154)中/C/C_interface.C:2511#15 do_top_teal(argc=2,argv=0xffff4C4)中的0x0805c2f5,位于/控制台/yap.c:84#16 exec_top_level(argc=2,argv=0xffff4C4),位于/控制台/yap.c:131#17 main(argc=2,argv=0xffff4C4)at/控制台/yap.c:172(gdb)

Edit: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处理(错误:消息由SWI)。

不是一个真正的答案,而是对SWI-Prolog功能的解释。首先,它估计则可能发生溢出。如果确定,它将在调用GMP之前引发一个错误。否则,它依赖于GMP分配挂钩,并在失败时执行longjmp()。它会跟踪对分配给中止的GMP操作的内存进行分配和解除分配。它能够做到这一点是因为记忆永远不会永远处于GMP的控制之下。成功的结果GMP计算被复制到Prolog堆栈,并接受Prolog内存管理。

这以前是有效的,但在最近的版本中不起作用。我怀疑GMP估计了如果它知道这将失败,甚至不需要调用malloc()钩子。我只需要一种方法来确保钩子总是被调用,即使它的值大得离谱。任何大于size_t所能表示的值的东西都可以用(size_t)-1调用钩子。

另外,由于复制到(较小的)Prolog运行时堆栈,它的溢出时间比内存所能存储的要早得多。

有些人为了解决这个问题而做的一些事情(不受支持,它会泄漏一些内存,但他们觉得总比什么都没有好):GMP允许您指定一个替换分配器(mp_set_memory_functions)。从这个分配器,你可以调用malloc,如果它失败了,你可以抛出C++异常(如果你使用gcc,请用-fexceptions重新编译gmp),或者调用longjmp或类似的东西来绕过gmp的故障处理,跳回到你控制的代码。

看来我运气不好:

即使是最新的版本也有

fprintf(stderr,"gmp:mpz类型中的溢出\n");中止()

至少此溢出已处理,不能用作漏洞攻击。

任何使用GMP的系统如果没有这个问题,都必须使用修改过的库或复制功能来估计大小。

13^1150000000大约是2^4255505675,需要425550567 5位来表示。每个字节有8位,这大约是500 MB的内存。看起来应该合适。

也许计算中涉及到几个临时变量,并且它超出了进程大小的限制。

看起来如果你有一个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

相关内容

  • 没有找到相关文章

最新更新