bug#16999: calc crashes when computation limit is increased

bug#16999: calc crashes when computation limit is increased

[Florian Beck]

M-x calc
2n
0
kc

I.e. try to calculate the binomial coefficient of (-2 0). This doesn't
work and calc suggests you give it more time:

Computation got stuck or ran too long.  Type `M' to increase the limit

So do

M
kc

and repeat a couple of times.

Once `max-lisp-eval-depth' hits 64000 emacs crashes.

I can send a backtrace if necessary.


In GNU Emacs 24.3.50.46 (x86_64-unknown-linux-gnu, GTK+ Version 3.8.6)
  of 2014-03-12 on sophokles
Windowing system distributor `The X.Org Foundation', version 11.0.11405000
System Description:	Ubuntu 13.10

Configured using:
  `configure CC=gcc 'CFLAGS=-march=native -mtune=native -msse -msse2
  -msse3 -mmmx -O2 -pipe -g3 -fno-omit-frame-pointer -fno-crossjumping'
  LDFLAGS=-O2'


-- 
Florian Beck

bug#16999: calc crashes when computation limit is increased

[Jay Belanger]

> M-x calc
> 2n
> 0
> kc
>
> I.e. try to calculate the binomial coefficient of (-2 0).

This causes Calc to enter an infinite loop.  It needs to be fixed, but
the problem has been around for a while so it probably needs to wait
until after the release.

> Computation got stuck or ran too long.  Type `M' to increase the limit
>
> So do
>
> M
> kc
>
> and repeat a couple of times.
>
> Once `max-lisp-eval-depth' hits 64000 emacs crashes.

This seems to be an Emacs problem, rather than a problem specific to Calc.
Typing M doubles the sizes of `max-lisp-eval-depth' and
`max-specpdl-size'.  Having  `max-lisp-eval-depth' equal to 64000 by
itself doesn't seem to cause problems, but having `max-lisp-eval-depth'
equal to 64000 and `max-specpdl-size' equal to 83200 does cause Emacs to
crash on an infinite loop; evaluating:

  (setq max-specpdl-size 83200
        max-lisp-eval-depth 64000)

  (defun f ()
     (f))

  (f)

will crash Emacs.

bug#16999: calc crashes when computation limit is increased

[Dmitry Antipov]

On 03/13/2014 02:44 AM, Jay Belanger wrote:

> This seems to be an Emacs problem, rather than a problem specific to Calc.
> Typing M doubles the sizes of `max-lisp-eval-depth' and
> `max-specpdl-size'.  Having  `max-lisp-eval-depth' equal to 64000 by
> itself doesn't seem to cause problems, but having `max-lisp-eval-depth'
> equal to 64000 and `max-specpdl-size' equal to 83200 does cause Emacs to
> crash on an infinite loop; evaluating:
>
>    (setq max-specpdl-size 83200
>          max-lisp-eval-depth 64000)
>
>    (defun f ()
>       (f))
>
>    (f)
>
> will crash Emacs.

This is C stack overflow (try to attach gdb and do 'bt' on crash). On
*NIX system, 'ulimit -s' shows your current limit.

Perhaps there should be a kind of protection against this. For example,
eval_sub can check current stack depth against getrlimit (RLIMIT_STACK,...).

Dmitry

bug#16999: calc crashes when computation limit is increased

[Dmitry Antipov]

[-- Attachment #1: Type: text/plain, Size: 513 bytes --]

On 03/13/2014 09:13 AM, Dmitry Antipov wrote:

> Perhaps there should be a kind of protection against this. For example,
> eval_sub can check current stack depth against getrlimit (RLIMIT_STACK,...).

This is rather simple on general *NIX. But:

1) it should be implemented for MS-Windows and OSX too if we really need this;
2) Linux has prlimit to tweak limits of another process at run time,
    so actual limit should be checked each time eval_sub is called, thus
    introducing a (minor?) slowdown.

Dmitry


[-- Attachment #2: error_if_c_stack_overflow.patch --]
[-- Type: text/x-patch, Size: 1566 bytes --]

=== modified file 'src/eval.c'
--- src/eval.c	2014-02-10 09:48:17 +0000
+++ src/eval.c	2014-03-13 08:59:39 +0000
@@ -33,6 +33,10 @@
 #include "xterm.h"
 #endif
 
+#ifdef HAVE_SYS_RESOURCE_H
+#include <sys/resource.h>
+#endif
+
 /* Chain of condition and catch handlers currently in effect.  */
 
 struct handler *handlerlist;
@@ -240,6 +244,13 @@
 
 static struct handler handlerlist_sentinel;
 
+/* C stack overflow protection.  */
+
+#if defined (HAVE_GETRLIMIT) && defined (RLIMIT_STACK)
+/* Current C stack slimit.  */
+static struct rlimit stack_limit;
+#endif
+
 void
 init_eval (void)
 {
@@ -262,6 +273,10 @@
 #endif
   /* This is less than the initial value of num_nonmacro_input_events.  */
   when_entered_debugger = -1;
+#if defined (HAVE_GETRLIMIT) && defined (RLIMIT_STACK)
+  if (getrlimit (RLIMIT_STACK, &stack_limit))
+    emacs_abort ();
+#endif  
 }
 
 /* Unwind-protect function used by call_debugger.  */
@@ -2060,6 +2075,19 @@
   Lisp_Object funcar;
   struct gcpro gcpro1, gcpro2, gcpro3;
 
+#if defined (HAVE_GETRLIMIT) && defined (RLIMIT_STACK)
+  ptrdiff_t stack_size;
+  char stack_top_variable;
+  const ptrdiff_t stack_extra = 128 * 1024;
+
+  if (&stack_top_variable < stack_bottom)
+    stack_size = stack_bottom - &stack_top_variable;
+  else
+    stack_size = &stack_top_variable - stack_bottom;
+  if (stack_size + stack_extra > stack_limit.rlim_cur)
+    error ("Attempt to overflow C stack");
+#endif /* HAVE_GETRLIMIT && RLIMIT_STACK */
+  
   if (SYMBOLP (form))
     {
       /* Look up its binding in the lexical environment.

bug#16999: calc crashes when computation limit is increased

[Stefan Monnier]

> Perhaps there should be a kind of protection against this.

There is, in the form of max-specpdl-size and max-lisp-eval-depth.
If you bump them up too high, you're asking for trouble.


        Stefan

bug#16999: calc crashes when computation limit is increased

[Florian Beck]

On 13.03.2014 10:11, Dmitry Antipov wrote:
> On 03/13/2014 09:13 AM, Dmitry Antipov wrote:
>
>> Perhaps there should be a kind of protection against this. For example,
>> eval_sub can check current stack depth against getrlimit
>> (RLIMIT_STACK,...).

Sorry, this doesn't work for me. (I applied the patch and bootstrapped, 
but I still get the crash.)


-- 
Florian Beck

bug#16999: calc crashes when computation limit is increased

[Florian Beck]

On 13.03.2014 14:42, Stefan Monnier wrote:
>> Perhaps there should be a kind of protection against this.
>
> There is, in the form of max-specpdl-size and max-lisp-eval-depth.
> If you bump them up too high, you're asking for trouble.

Maybe calc shouldn't bump them too high, then.

Would I start calc, repetedly press "M" and then crash emacs – well, 
maybe I was asking for trouble. But I pressed M as suggested, then 
checked to docs, then again pressed M as suggested, then did something 
else, returned to calc, pressed M again as suggested, and so on...
-- 
Florian Beck

bug#16999: calc crashes when computation limit is increased

[Dmitry Antipov]

[-- Attachment #1: Type: text/plain, Size: 212 bytes --]

On 03/13/2014 06:06 PM, Florian Beck wrote:

> Sorry, this doesn't work for me. (I applied the patch and bootstrapped, but I still get the crash.)

Oops, the guard should be installed in Ffuncall too...

Dmitry


[-- Attachment #2: error_if_c_stack_overflow_fixed.patch --]
[-- Type: text/x-patch, Size: 2168 bytes --]

=== modified file 'src/eval.c'
--- src/eval.c	2014-02-10 09:48:17 +0000
+++ src/eval.c	2014-03-13 14:27:14 +0000
@@ -33,6 +33,10 @@
 #include "xterm.h"
 #endif
 
+#ifdef HAVE_SYS_RESOURCE_H
+#include <sys/resource.h>
+#endif
+
 /* Chain of condition and catch handlers currently in effect.  */
 
 struct handler *handlerlist;
@@ -240,6 +244,13 @@
 
 static struct handler handlerlist_sentinel;
 
+/* C stack overflow protection.  */
+
+#if defined (HAVE_GETRLIMIT) && defined (RLIMIT_STACK)
+/* Current C stack slimit.  */
+static struct rlimit stack_limit;
+#endif
+
 void
 init_eval (void)
 {
@@ -262,6 +273,10 @@
 #endif
   /* This is less than the initial value of num_nonmacro_input_events.  */
   when_entered_debugger = -1;
+#if defined (HAVE_GETRLIMIT) && defined (RLIMIT_STACK)
+  if (getrlimit (RLIMIT_STACK, &stack_limit))
+    emacs_abort ();
+#endif  
 }
 
 /* Unwind-protect function used by call_debugger.  */
@@ -2060,6 +2075,19 @@
   Lisp_Object funcar;
   struct gcpro gcpro1, gcpro2, gcpro3;
 
+#if defined (HAVE_GETRLIMIT) && defined (RLIMIT_STACK)
+  ptrdiff_t stack_size;
+  char stack_top_variable;
+  const ptrdiff_t stack_extra = 128 * 1024;
+
+  if (&stack_top_variable < stack_bottom)
+    stack_size = stack_bottom - &stack_top_variable;
+  else
+    stack_size = &stack_top_variable - stack_bottom;
+  if (stack_size + stack_extra > stack_limit.rlim_cur)
+    error ("Attempt to overflow C stack");
+#endif /* HAVE_GETRLIMIT && RLIMIT_STACK */
+  
   if (SYMBOLP (form))
     {
       /* Look up its binding in the lexical environment.
@@ -2749,6 +2777,19 @@
   register Lisp_Object *internal_args;
   ptrdiff_t i;
 
+#if defined (HAVE_GETRLIMIT) && defined (RLIMIT_STACK)
+  ptrdiff_t stack_size;
+  char stack_top_variable;
+  const ptrdiff_t stack_extra = 128 * 1024;
+
+  if (&stack_top_variable < stack_bottom)
+    stack_size = stack_bottom - &stack_top_variable;
+  else
+    stack_size = &stack_top_variable - stack_bottom;
+  if (stack_size + stack_extra > stack_limit.rlim_cur)
+    error ("Attempt to overflow C stack");
+#endif /* HAVE_GETRLIMIT && RLIMIT_STACK */
+
   QUIT;
 
   if (++lisp_eval_depth > max_lisp_eval_depth)

bug#16999: calc crashes when computation limit is increased

[Eli Zaretskii]

> Date: Thu, 13 Mar 2014 13:11:50 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> CC: Paul Eggert <eggert@cs.ucla.edu>, Eli Zaretskii <eliz@gnu.org>
> 
> On 03/13/2014 09:13 AM, Dmitry Antipov wrote:
> 
> > Perhaps there should be a kind of protection against this. For example,
> > eval_sub can check current stack depth against getrlimit (RLIMIT_STACK,...).
> 
> This is rather simple on general *NIX. But:
> 
> 1) it should be implemented for MS-Windows and OSX too if we really need this;

It should be easy enough to emulate on MS-Windows getrlimit that
supports RLIMIT_STACK.  Let me know if you want me to do that (should
ideally be ready before it is used, to avoid breaking the build).

> 2) Linux has prlimit to tweak limits of another process at run time,
>     so actual limit should be checked each time eval_sub is called, thus
>     introducing a (minor?) slowdown.

I'm not sure we should bother.  We already use getrlimit/setrlimit for
making sure the stack is large enough to accommodate re_max_failures.
We do that only once, at startup, and never look back.  And yet I
don't think we've seen regexp related crashes that would point to
stack overflow.

bug#16999: calc crashes when computation limit is increased

[Jay Belanger]

>> There is, in the form of max-specpdl-size and max-lisp-eval-depth.
>> If you bump them up too high, you're asking for trouble.
>
> Maybe calc shouldn't bump them too high, then.

The Elisp manual has a warning about bumping them too high; perhaps the
Calc manual should have one also.  But this seems more like an Emacs
issue than specifically a Calc issue, so any other fixes should probably
take place out of Calc.

Dmitry has started a separate discussion on handling this issue; good
deal. 

> Would I start calc, repetedly press "M" and then crash emacs – well,
> maybe I was asking for trouble.

The main culprit here is the infinite loop itself, which needs to be
fixed.  Without that, you wouldn't have had any problems.

bug#16999: calc crashes when computation limit is increased

[Stefan Monnier]

> Maybe calc shouldn't bump them too high, then.

Indeed, it shouldn't.


        Stefan

bug#16999: calc crashes when computation limit is increased

[Lars Ingebrigtsen]

Florian Beck <fb@miszellen.de> writes:

> M-x calc
> 2n
> 0
> kc
>
> I.e. try to calculate the binomial coefficient of (-2 0). This doesn't
> work and calc suggests you give it more time:
>
> Computation got stuck or ran too long.  Type `M' to increase the limit
>
> So do
>
> M
> kc
>
> and repeat a couple of times.
>
> Once `max-lisp-eval-depth' hits 64000 emacs crashes.

It seems like this problem has been fixed by the general C stack
protection.  Trying this in Emacs 28 I just get:

  Re-entering top level after C stack overflow

So I'm closing this bug report.  If this is still a problem, please
respond to the debbugs address and we'll reopen.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#16999: calc crashes when computation limit is increased

[Mattias Engdegård]

reopen 16999
make it so

While the C-level crash has been fixed, the Calc bug (infinite loop) has not.

Whether to signal a domain error for (-2 choose 0) or return the conventional value by extension is a matter of taste; I think the latter would be more useful. In fact, I see no reason not to extend the function to all integral arguments, but would of course value any half-supported opinion on the matter.

Let me attempt a patch, and please forgive my reopening the bug.

bug#16999: calc crashes when computation limit is increased

[Mattias Engdegård]

[-- Attachment #1: Type: text/plain, Size: 999 bytes --]

10 sep. 2020 kl. 18.02 skrev Mattias Engdegård <mattiase@acm.org>:

> Let me attempt a patch, and please forgive my reopening the bug.

Here is that patch. Sadly mail to Florian Beck's address bounced but perhaps someone else will see the proposal and subject it to scrutiny. In short:

1. A sign mistake in the original code caused the infinite recursion. Fixed.
2. Some parts of the computation used tail recursion, which limited their applicability in elisp. Changed to use an imperative loop (alas).
3. The binomial coefficients have now been extended for all integral arguments, using definitions from [1]; see also [2] and [3].

[1] M. J. Kronenburg; The Binomial Coefficient for Negative Arguments; https://arxiv.org/abs/1105.3689
[2] D. Loeb, E. Damiani and O. D’Antona; Getting Results with Negative Thinking; https://arxiv.org/abs/math/9502214
[3] David Fowler; The Binomial Coefficient Function; The American Mathematical Monthly, Vol. 103, No. 1 (Jan., 1996), pp. 1-17


[-- Attachment #2: 0001-Calc-fix-binomial-coefficients-for-negative-argument.patch --]
[-- Type: application/octet-stream, Size: 6320 bytes --]

From c451146726adfacdec69247c3da6dc4ebacd1b97 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Mattias=20Engdeg=C3=A5rd?= <mattiase@acm.org>
Date: Fri, 11 Sep 2020 11:43:15 +0200
Subject: [PATCH] Calc: fix binomial coefficients for negative arguments
 (bug#16999)
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

For some values outside integers 0≤k≤n, (n choose k) gave wrong
results, entered infinite recursion or used unreasonably amounts of
stack space.  This change fixes that and extends the function to all
integer arguments using the definitions from M. J. Kronenburg
(https://arxiv.org/abs/1105.3689).

* lisp/calc/calc-comb.el (calcFunc-choose):
Fix sign error to prevent infinite recursion and extend function to
handle all integer arguments.
(math-choose-iter, math-choose-float-iter): Rewrite in iterative form;
no TCO in elisp yet.
* test/lisp/calc/calc-tests.el (calc-tests--fac, calc-tests--choose)
(calc-tests--check-choose, calc-tests--explain-choose)
(calc-tests--calc-to-number): New helper functions.
(calc-choose): New test.
---
 lisp/calc/calc-comb.el       | 42 +++++++++++++++-------
 test/lisp/calc/calc-tests.el | 67 ++++++++++++++++++++++++++++++++++++
 2 files changed, 96 insertions(+), 13 deletions(-)

diff --git a/lisp/calc/calc-comb.el b/lisp/calc/calc-comb.el
index c5d4d0837e..ce676d17a9 100644
--- a/lisp/calc/calc-comb.el
+++ b/lisp/calc/calc-comb.el
@@ -445,12 +445,25 @@ calcFunc-choose
 	   (math-div (calcFunc-fact (math-float n))
 		     (math-mul (calcFunc-fact m)
 			       (calcFunc-fact (math-sub n m))))))
-	((math-negp m) 0)
-	((math-negp n)
-	 (let ((val (calcFunc-choose (math-add (math-add n m) -1) m)))
+        ;; For the extension to negative integer arguments we follow
+        ;; M. J. Kronenburg, The Binomial Coefficient for Negative Arguments,
+        ;; arXiv:1105.3689v2
+        ((and (math-negp n) (not (math-negp m)))
+         ;; n<0≤m: (n choose m) = (-1)^m (-n+m-1 choose m)
+	 (let ((val (calcFunc-choose (math-add (math-sub m n) -1) m)))
 	   (if (math-evenp (math-trunc m))
 	       val
 	     (math-neg val))))
+        ((and (math-negp n) (math-num-integerp n))
+         (if (math-lessp n m)
+             0
+           ;; m≤n<0: (n choose m) = (-1)^(n-m) (-m-1 choose n-m)
+           (let ((val (calcFunc-choose (math-sub (math-neg m) 1)
+                                       (math-sub n m))))
+             (if (math-evenp (math-sub n m))
+                 val
+               (math-neg val)))))
+	((math-negp m) 0)
 	((and (math-num-integerp n)
 	      (Math-lessp n m))
 	 0)
@@ -467,20 +480,23 @@ calcFunc-choose
 	       (math-choose-float-iter tm n 1 1)))))))
 
 (defun math-choose-iter (m n i c)
-  (if (and (= (% i 5) 1) (> i 5))
+  (while (<= i m)
+    (when (and (= (% i 5) 1) (> i 5))
       (math-working (format "choose(%d)" (1- i)) c))
-  (if (<= i m)
-      (math-choose-iter m (1- n) (1+ i)
-			(math-quotient (math-mul c n) i))
-    c))
+    (setq c (math-quotient (math-mul c n) i))
+    (setq n (1- n))
+    (setq i (1+ i)))
+  c)
 
 (defun math-choose-float-iter (count n i c)
-  (if (= (% i 5) 1)
+  (while (> count 0)
+    (when (= (% i 5) 1)
       (math-working (format "choose(%d)" (1- i)) c))
-  (if (> count 0)
-      (math-choose-float-iter (1- count) (math-sub n 1) (1+ i)
-			      (math-div (math-mul c n) i))
-    c))
+    (setq c (math-div (math-mul c n) i))
+    (setq n (math-sub n 1))
+    (setq i (1+ i))
+    (setq count (1- count)))
+  c)
 
 
 ;;; Stirling numbers.
diff --git a/test/lisp/calc/calc-tests.el b/test/lisp/calc/calc-tests.el
index c8cb97a8bc..5030a55472 100644
--- a/test/lisp/calc/calc-tests.el
+++ b/test/lisp/calc/calc-tests.el
@@ -397,6 +397,73 @@ calc-sum-gcd
                     (var n var-n) -1 1))
                  8)))
 
+(defun calc-tests--fac (n)
+  (apply #'* (number-sequence 1 n)))
+
+(defun calc-tests--choose (n k)
+  "N choose K, reference implementation."
+  (cond
+   ((and (integerp n) (integerp k))
+    (if (<= 0 n)
+        (if (<= 0 k n)
+            (/ (calc-tests--fac n)
+               (* (calc-tests--fac k) (calc-tests--fac (- n k))))
+          0)    ; 0≤n<k
+      ;; n<0, n and k integers: use extension from M. J. Kronenburg
+      (cond
+       ((<= 0 k)
+        (* (expt -1 k)
+           (calc-tests--choose (+ (- n) k -1) k)))
+       ((<= k n)
+        (* (expt -1 (- n k))
+           (calc-tests--choose (+ (- k) -1) (- n k))))
+       (t  ; n<k<0
+        0))))
+   ((natnump k)
+    ;; Generalisation for any n, integral k≥0: use falling product
+    (/ (apply '* (number-sequence n (- n (1- k)) -1))
+       (calc-tests--fac k)))
+   (t (error "case not covered"))))
+
+(defun calc-tests--check-choose (n k)
+  (equal (calcFunc-choose n k)
+         (calc-tests--choose n k)))
+
+(defun calc-tests--explain-choose (n k)
+  (let ((got (calcFunc-choose n k))
+        (expected (calc-tests--choose n k)))
+    (format "(calcFunc-choose %d %d) => %S, expected %S" n k got expected)))
+
+(put 'calc-tests--check-choose 'ert-explainer 'calc-tests--explain-choose)
+
+(defun calc-tests--calc-to-number (x)
+  "Convert a Calc object to a Lisp number."
+  (pcase x
+    ((pred numberp) x)
+    (`(frac ,p ,q) (/ (float p) q))
+    (`(float ,m ,e) (* m (expt 10 e)))
+    (_ (error "calc object not converted: %S" x))))
+
+(ert-deftest calc-choose ()
+  "Test computation of binomial coefficients (bug#16999)."
+  ;; Integral arguments
+  (dolist (n (number-sequence -6 6))
+    (dolist (k (number-sequence -6 6))
+      (should (calc-tests--check-choose n k))))
+
+  ;; Fractional n, natural k
+  (should (equal (calc-tests--calc-to-number
+                  (calcFunc-choose '(frac 15 2) 3))
+                 (calc-tests--choose 7.5 3)))
+
+  (should (equal (calc-tests--calc-to-number
+                  (calcFunc-choose '(frac 1 2) 2))
+                 (calc-tests--choose 0.5 2)))
+
+  (should (equal (calc-tests--calc-to-number
+                  (calcFunc-choose '(frac -15 2) 3))
+                 (calc-tests--choose -7.5 3))))
+
 (provide 'calc-tests)
 ;;; calc-tests.el ends here
 
-- 
2.21.1 (Apple Git-122.3)

bug#16999: calc crashes when computation limit is increased

[Lars Ingebrigtsen]

Mattias Engdegård <mattiase@acm.org> writes:

> While the C-level crash has been fixed, the Calc bug (infinite loop) has not.

Ah, sorry, I thought I had tested that bit too, but I must have done
something wrong...

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#16999: calc crashes when computation limit is increased

[Mattias Engdegård]

11 sep. 2020 kl. 13.54 skrev Lars Ingebrigtsen <larsi@gnus.org>:

> Ah, sorry, I thought I had tested that bit too, but I must have done
> something wrong...

Well, you dug up an old bug and turned our attention to it, so in a sense you did bring about the resolution!

Patch pushed and bug closed (again).