9

（我只是 GMP 库的间接用户，主要通过和。但我对解决这个问题非常感兴趣。）

当执行具有大得离谱的值的幂运算时，主机系统或 GMP 不再能够适当地处理溢出。我已经与上述系统的开发人员进行了交谈，但他们没有看到一个简单的解决方法。

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

作为健全性检查，首先测试 7^7^7 的值，它应该是：375982...32343

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

GNU gdb (GDB) 7.0-ubuntu
版权所有 (C) 2009 Free Software Foundation, Inc.
许可 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 -f
YAP 6.3.2 (i686-linux)：2012 年 11 月 11 日星期日 04:19:37 CET
?- X 是 13^1150000000。

程序收到信号 SIGSEGV，分段错误。
0x001638d8 在?? () 来自 /usr/lib/libgmp.so.3
(gdb) BT
#0 0x001638d8 在?? () 来自 /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 在 Yap_absmi (inp=0) at ../C/absmi.c:6912
#11 0x080b3655 in exec_absmi (top=) at ../C/exec.c:1002
#12 0x080b3b1f 在 do_goal (t=, CodeAdr=, arity=,
    pt=0x0，顶部=1) 在 ../C/exec.c:1068
#13 0x080b3d1d in Yap_RunTopGoal (t=135918154) at ../C/exec.c:1291
#14 0x08061a6f 在 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 主要 (argc=2, argv=0xbffff4c4) 在 ../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 处理（错误：消息由 SWI 处理）。

4

5 回答 5

5

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

这曾经有效，但在最近的版本中不起作用。我怀疑 GMP 会估计大小，如果知道这将失败，它甚至不会打扰调用 malloc() 钩子。我所需要的只是一种确保始终调用钩子的方法，即使它的值非常大。任何大于 size_t 可以表示的东西都可以用 (size_t)-1 调用钩子。

Ps 由于复制到（较小的）Prolog 运行时堆栈，它比内存可以存储的内存要早得多。

于 2013-01-09T20:11:46.367 回答
4

有些人为解决此问题所做的一些事情（不受支持并且它会泄漏一些内存，但他们发现它总比没有好）：GMP 允许您指定替换分配器（mp_set_memory_functions）。从这个分配器中，您可以调用 malloc，如果它失败了，您可以抛出 C++ 异常（如果您使用 gcc，请使用 -fexceptions 重新编译 gmp）或调用 longjmp 或类似的东西来绕过 GMP 的故障处理并跳回您控制的代码。

于 2013-01-09T15:40:43.557 回答
2

13^1,150,000,000 大约是 2^4,255,505,675，需要 4,255,505,675 位来表示。每字节 8 位，这大约是 500 MB 的内存。好像应该合适。

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

于 2012-12-11T22:52:46.493 回答
2

好吧，看来我不走运：

即使是最新版本

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

至少这个溢出被处理并且不能被用作漏洞利用。

并且任何使用 GMP 的没有此问题的系统都必须使用修改后的库或复制用于估计大小的功能。

于 2012-11-14T14:54:53.337 回答
1

看起来如果你有一个克雷，它会工作的。

#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
于 2012-12-13T02:04:06.350 回答