GNU bug report logs - #16999
calc crashes when computation limit is increased

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 16999 in the body.
You can then email your comments to 16999 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Florian Beck <fb <at> miszellen.de>
To: bug-gnu-emacs <at> gnu.org
Subject: calc crashes when computation limit is increased
Date: Wed, 12 Mar 2014 19:30:49 +0100

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

Message #8 received at 16999 <at> debbugs.gnu.org (full text, mbox):

From: Jay Belanger <jay.p.belanger <at> gmail.com>
To: Florian Beck <fb <at> miszellen.de>
Cc: jay.p.belanger <at> gmail.com, 16999 <at> debbugs.gnu.org
Subject: Re: bug#16999: calc crashes when computation limit is increased
Date: Wed, 12 Mar 2014 17:44:15 -0500

> 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.

Message #11 received at 16999 <at> debbugs.gnu.org (full text, mbox):

From: Dmitry Antipov <dmantipov <at> yandex.ru>
To: jay.p.belanger <at> gmail.com, Florian Beck <fb <at> miszellen.de>
Cc: 16999 <at> debbugs.gnu.org
Subject: Re: bug#16999: calc crashes when computation limit is increased
Date: Thu, 13 Mar 2014 09:13:54 +0400

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

Message #14 received at 16999 <at> debbugs.gnu.org (full text, mbox):

From: Dmitry Antipov <dmantipov <at> yandex.ru>
To: 16999 <at> debbugs.gnu.org
Cc: Eli Zaretskii <eliz <at> gnu.org>, Paul Eggert <eggert <at> cs.ucla.edu>
Subject: Re: bug#16999: calc crashes when computation limit is increased
Date: Thu, 13 Mar 2014 13:11:50 +0400

[Message part 1 (text/plain, inline)]

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

[error_if_c_stack_overflow.patch (text/x-patch, attachment)]

Message #17 received at 16999 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Dmitry Antipov <dmantipov <at> yandex.ru>
Cc: jay.p.belanger <at> gmail.com, 16999 <at> debbugs.gnu.org,
 Florian Beck <fb <at> miszellen.de>
Subject: Re: bug#16999: calc crashes when computation limit is increased
Date: Thu, 13 Mar 2014 09:42:20 -0400

> 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

Message #20 received at 16999 <at> debbugs.gnu.org (full text, mbox):

From: Florian Beck <fb <at> miszellen.de>
To: Dmitry Antipov <dmantipov <at> yandex.ru>, 16999 <at> debbugs.gnu.org
Subject: Re: bug#16999: calc crashes when computation limit is increased
Date: Thu, 13 Mar 2014 15:06:06 +0100

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

Message #23 received at 16999 <at> debbugs.gnu.org (full text, mbox):

From: Florian Beck <fb <at> miszellen.de>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>, 
 Dmitry Antipov <dmantipov <at> yandex.ru>
Cc: 16999 <at> debbugs.gnu.org
Subject: Re: bug#16999: calc crashes when computation limit is increased
Date: Thu, 13 Mar 2014 15:12:02 +0100

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

Message #26 received at 16999 <at> debbugs.gnu.org (full text, mbox):

From: Dmitry Antipov <dmantipov <at> yandex.ru>
To: Florian Beck <fb <at> miszellen.de>
Cc: 16999 <at> debbugs.gnu.org
Subject: Re: bug#16999: calc crashes when computation limit is increased
Date: Thu, 13 Mar 2014 18:30:40 +0400

[Message part 1 (text/plain, inline)]

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

[error_if_c_stack_overflow_fixed.patch (text/x-patch, attachment)]

Message #29 received at 16999 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Dmitry Antipov <dmantipov <at> yandex.ru>
Cc: eggert <at> cs.ucla.edu, 16999 <at> debbugs.gnu.org
Subject: Re: bug#16999: calc crashes when computation limit is increased
Date: Thu, 13 Mar 2014 18:56:53 +0200

> Date: Thu, 13 Mar 2014 13:11:50 +0400
> From: Dmitry Antipov <dmantipov <at> yandex.ru>
> CC: Paul Eggert <eggert <at> cs.ucla.edu>, Eli Zaretskii <eliz <at> 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.

Message #32 received at 16999 <at> debbugs.gnu.org (full text, mbox):

From: Jay Belanger <jay.p.belanger <at> gmail.com>
To: Florian Beck <fb <at> miszellen.de>
Cc: jay.p.belanger <at> gmail.com, Dmitry Antipov <dmantipov <at> yandex.ru>,
 16999 <at> debbugs.gnu.org
Subject: Re: bug#16999: calc crashes when computation limit is increased
Date: Thu, 13 Mar 2014 16:15:56 -0500

>> 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.

Message #35 received at 16999 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Florian Beck <fb <at> miszellen.de>
Cc: Dmitry Antipov <dmantipov <at> yandex.ru>, 16999 <at> debbugs.gnu.org
Subject: Re: bug#16999: calc crashes when computation limit is increased
Date: Thu, 13 Mar 2014 18:10:05 -0400

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

Indeed, it shouldn't.


        Stefan

Message #38 received at 16999 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Florian Beck <fb <at> miszellen.de>
Cc: 16999 <at> debbugs.gnu.org
Subject: Re: bug#16999: calc crashes when computation limit is increased
Date: Wed, 09 Sep 2020 14:19:17 +0200

Florian Beck <fb <at> 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

Message #43 received at 16999 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: Florian Beck <fb <at> miszellen.de>, 16999 <at> debbugs.gnu.org
Subject: Re: bug#16999: calc crashes when computation limit is increased
Date: Thu, 10 Sep 2020 18:02:39 +0200

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.

Message #48 received at 16999 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: 16999 <at> debbugs.gnu.org
Subject: Re: bug#16999: calc crashes when computation limit is increased
Date: Fri, 11 Sep 2020 12:29:54 +0200

[Message part 1 (text/plain, inline)]

10 sep. 2020 kl. 18.02 skrev Mattias Engdegård <mattiase <at> 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

[0001-Calc-fix-binomial-coefficients-for-negative-argument.patch (application/octet-stream, attachment)]

Message #51 received at 16999 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Florian Beck <fb <at> miszellen.de>, 16999 <at> debbugs.gnu.org
Subject: Re: bug#16999: calc crashes when computation limit is increased
Date: Fri, 11 Sep 2020 13:54:05 +0200

Mattias Engdegård <mattiase <at> 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

Message #56 received at 16999-done <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: 16999-done <at> debbugs.gnu.org
Subject: Re: bug#16999: calc crashes when computation limit is increased
Date: Mon, 14 Sep 2020 11:45:42 +0200

11 sep. 2020 kl. 13.54 skrev Lars Ingebrigtsen <larsi <at> 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).

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.