GNU bug report logs - #2099
stack overflow in GC when creating large nested object

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 2099 in the body.
You can then email your comments to 2099 AT debbugs.gnu.org in the normal way.

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

Message #5 received at submit <at> emacsbugs.donarmstrong.com (full text, mbox):

From: Markus Triska <markus.triska <at> gmx.at>
To: emacs-pretest-bug <at> gnu.org
Subject: 23.0.60; `mark_object' with larger nested objects crashes Emacs
Date: Thu, 29 Jan 2009 00:06:45 +0100 (CET)

When you do:

   $ emacs -Q --eval "(let (v) (while t (setq v (cons v v))))"

then Emacs crashes with:

   Program received signal EXC_BAD_ACCESS, Could not access memory.
   Reason: KERN_INVALID_ADDRESS at address: 0xbf7ffffc
   0x0013bc1a in mark_object (arg=40166541) at alloc.c:5372
   (gdb) bt
   #0  0x0013bc1a in mark_object (arg=40166541) at alloc.c:5372
   #1  0x0013bdf8 in mark_object (arg=40166549) at alloc.c:5655
   #2  0x0013bdf8 in mark_object (arg=40166557) at alloc.c:5655
   #3  0x0013bdf8 in mark_object (arg=40166565) at alloc.c:5655
   #4  0x0013bdf8 in mark_object (arg=40166573) at alloc.c:5655
   #5  0x0013bdf8 in mark_object (arg=40166581) at alloc.c:5655
   #6  0x0013bdf8 in mark_object (arg=40166589) at alloc.c:5655
   ...

Throwing an error or making GC stackless seems much preferable here.

In GNU Emacs 23.0.60.1 (i386-apple-darwin8.11.1, GTK+ Version 2.12.9)
 of 2009-01-28 on mt-computer.local
Windowing system distributor `The XFree86 Project, Inc', version 11.0.40400000
Important settings:
  value of $LC_ALL: nil
  value of $LC_COLLATE: nil
  value of $LC_CTYPE: nil
  value of $LC_MESSAGES: nil
  value of $LC_MONETARY: nil
  value of $LC_NUMERIC: nil
  value of $LC_TIME: nil
  value of $LANG: en_GB.UTF-8
  value of $XMODIFIERS: nil
  locale-coding-system: nil
  default-enable-multibyte-characters: t

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

From: Lars Magne Ingebrigtsen <larsi <at> gnus.org>
To: Markus Triska <markus.triska <at> gmx.at>
Cc: 2099 <at> debbugs.gnu.org
Subject: Re: 23.0.60; `mark_object' with larger nested objects crashes Emacs
Date: Sun, 11 Sep 2011 23:08:07 +0200

Markus Triska <markus.triska <at> gmx.at> writes:

> When you do:
>
>    $ emacs -Q --eval "(let (v) (while t (setq v (cons v v))))"
>
> then Emacs crashes with:
>
>    Program received signal EXC_BAD_ACCESS, Could not access memory.
>    Reason: KERN_INVALID_ADDRESS at address: 0xbf7ffffc
>    0x0013bc1a in mark_object (arg=40166541) at alloc.c:5372
>    (gdb) bt
>    #0  0x0013bc1a in mark_object (arg=40166541) at alloc.c:5372

I can confirm that the crash is still present in Emacs 24:

[larsi <at> stories ~/src/emacs/trunk]$ gdb  --args ./src/emacs -Q --eval "(let (v) (while t (setq v (cons v v))))"

[...]

(gdb) run
Starting program: /home/larsi/src/emacs/trunk/src/emacs -Q --eval \(let\ \(v\)\ \(while\ t\ \(setq\ v\ \(cons\ v\ v\)\)\)\)
[Thread debugging using libthread_db enabled]

Program received signal SIGSEGV, Segmentation fault.
mark_object (arg=21115190) at alloc.c:5396
5396    {


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

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

From: Andreas Schwab <schwab <at> linux-m68k.org>
To: Lars Magne Ingebrigtsen <larsi <at> gnus.org>
Cc: 2099 <at> debbugs.gnu.org, Markus Triska <markus.triska <at> gmx.at>
Subject: Re: bug#2099: 23.0.60;
	`mark_object' with larger nested objects crashes Emacs
Date: Sun, 11 Sep 2011 23:54:52 +0200

Lars Magne Ingebrigtsen <larsi <at> gnus.org> writes:

> I can confirm that the crash is still present in Emacs 24:
>
> [larsi <at> stories ~/src/emacs/trunk]$ gdb  --args ./src/emacs -Q --eval "(let (v) (while t (setq v (cons v v))))"

This creates a deeply nested object that is doomed to overflow the stack
during garbage collecting.  There are many ways to shoot yourself in the
foot.

Andreas.

-- 
Andreas Schwab, schwab <at> linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

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

From: Lars Magne Ingebrigtsen <larsi <at> gnus.org>
To: Andreas Schwab <schwab <at> linux-m68k.org>
Cc: 2099 <at> debbugs.gnu.org, Markus Triska <markus.triska <at> gmx.at>
Subject: Re: bug#2099: 23.0.60;
	`mark_object' with larger nested objects crashes Emacs
Date: Sun, 11 Sep 2011 23:53:48 +0200

Andreas Schwab <schwab <at> linux-m68k.org> writes:

> This creates a deeply nested object that is doomed to overflow the stack
> during garbage collecting.  There are many ways to shoot yourself in the
> foot.

But it would be nice if Emacs did something other than segfault.  :-)

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

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

From: Lars Magne Ingebrigtsen <larsi <at> gnus.org>
To: bug-gnu-emacs <at> gnu.org
Subject: Re: bug#2099: 23.0.60;
	`mark_object' with larger nested objects crashes Emacs
Date: Mon, 12 Sep 2011 01:47:42 +0200

So, the problem here seems simply to be that we blow up the stack by
recursing so ridiculously deep?  I think?

Looking at mark_object, it seems like it could pretty easily be
rewritten to be non-recursive, just by changing it into a loop, and
using a stack to do visit all the objects.

But that's probably not an Emacs 24.1 thing.

The other question is what other interesting deep-nesting bugs a
structure like that might reveal, so even if we fix the mark_object
case, that might not help us much.  Difficult to say...

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

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

From: Alan J Third <alan <at> idiocy.org>
To: Lars Magne Ingebrigtsen <larsi <at> gnus.org>
Cc: 2099 <at> debbugs.gnu.org, Markus Triska <markus.triska <at> gmx.at>
Subject: Re: bug#2099: 23.0.60;
 `mark_object' with larger nested objects crashes Emacs
Date: Sun, 10 Jan 2016 22:12:10 +0000

Lars Magne Ingebrigtsen <larsi <at> gnus.org> writes:

> Markus Triska <markus.triska <at> gmx.at> writes:
>
>> When you do:
>>
>>    $ emacs -Q --eval "(let (v) (while t (setq v (cons v v))))"
>>
>> then Emacs crashes with:
>>
>>    Program received signal EXC_BAD_ACCESS, Could not access memory.
>>    Reason: KERN_INVALID_ADDRESS at address: 0xbf7ffffc
>>    0x0013bc1a in mark_object (arg=40166541) at alloc.c:5372
>>    (gdb) bt
>>    #0  0x0013bc1a in mark_object (arg=40166541) at alloc.c:5372
>
> I can confirm that the crash is still present in Emacs 24:

And Emacs 25:

Fatal error 11: Segmentation fault
-- 
Alan Third

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

From: Eli Zaretskii <eliz <at> gnu.org>
To: Alan J Third <alan <at> idiocy.org>
Cc: larsi <at> gnus.org, 2099 <at> debbugs.gnu.org, markus.triska <at> gmx.at
Subject: Re: bug#2099: 23.0.60;
 `mark_object' with larger nested objects crashes Emacs
Date: Mon, 11 Jan 2016 17:11:44 +0200

> From: Alan J Third <alan <at> idiocy.org>
> Date: Sun, 10 Jan 2016 22:12:10 +0000
> Cc: Markus Triska <markus.triska <at> gmx.at>, 2099 <at> debbugs.gnu.org
> 
> > Markus Triska <address <at> hidden> writes:
> >
> >> When you do:
> >>
> >>    $ emacs -Q --eval "(let (v) (while t (setq v (cons v v))))"
> >>
> >> then Emacs crashes with:
> >>
> >>    Program received signal EXC_BAD_ACCESS, Could not access memory.
> >>    Reason: KERN_INVALID_ADDRESS at address: 0xbf7ffffc
> >>    0x0013bc1a in mark_object (arg=40166541) at alloc.c:5372
> >>    (gdb) bt
> >>    #0  0x0013bc1a in mark_object (arg=40166541) at alloc.c:5372
> >
> > I can confirm that the crash is still present in Emacs 24:
> 
> And Emacs 25:
> 
> Fatal error 11: Segmentation fault

Of course: this is expected.

I admit I don't really understand what is the purpose of this bug
report; perhaps the OP could clarify.

Here's my take on this:

  . What happens is clear: stack overflow during GC.  Since the stack
    space is always limited, one can always overflow it by
    deliberately consing larger and larger objects.

  . When stack overflow happens during GC, Emacs commits suicide,
    because such fatal errors are not recoverable with the current
    code.

  . Making GC non-recursive is a large job, that will most probably
    require significant changes in GC as a whole, not just in the
    recursive mark step.  If someone wants to work on that, they
    surely don't need this bug as an inspiration.

IOW, this is a known limitation of the current GC implementation.  So
I think we should mark this bug "wishlist" (or maybe even "wontfix"),
and leave it at that.

Any objections/comments/suggestions?

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

From: Alan J Third <alan <at> idiocy.org>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: larsi <at> gnus.org, markus.triska <at> gmx.at, 2099 <at> debbugs.gnu.org
Subject: Re: bug#2099: 23.0.60;
 `mark_object' with larger nested objects crashes Emacs
Date: Mon, 11 Jan 2016 17:49:59 +0000

Eli Zaretskii <eliz <at> gnu.org> writes:

> this is a known limitation of the current GC implementation.  So
> I think we should mark this bug "wishlist" (or maybe even "wontfix"),
> and leave it at that.
>
> Any objections/comments/suggestions?

My inclination would be to go with "wontfix", but I'm new around here so
I don't know that my opinion counts for much.
-- 
Alan Third

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

From: markus.triska <at> gmx.at
To: "Alan J Third" <alan <at> idiocy.org>
Cc: Eli Zaretskii <eliz <at> gnu.org>, larsi <at> gnus.org, 2099 <at> debbugs.gnu.org
Subject: Re: bug#2099: 23.0.60; `mark_object' with larger nested objects
 crashes Emacs
Date: Mon, 11 Jan 2016 20:10:26 +0100

Hi Alan,

Alan Third writes:

> My inclination would be to go with "wontfix", but I'm new around here so
> I don't know that my opinion counts for much.

Marking this as "wontfix" seems particularly inapplicable to me: This
shortcoming crashes Emacs and potentially causes data loss for users,
not only in such an artificial test case but in other situations too.
This shortcoming prevents my testing Emacs in many other ways that would
help me to find and correct more shortcomings and make Emacs more robust.

All the best,
Markus

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

From: Eli Zaretskii <eliz <at> gnu.org>
To: markus.triska <at> gmx.at
Cc: alan <at> idiocy.org, larsi <at> gnus.org, 2099 <at> debbugs.gnu.org
Subject: Re: bug#2099: 23.0.60; `mark_object' with larger nested objects
 crashes Emacs
Date: Mon, 11 Jan 2016 21:16:38 +0200

> From: markus.triska <at> gmx.at
> Cc: "Eli Zaretskii" <eliz <at> gnu.org>, 2099 <at> debbugs.gnu.org, larsi <at> gnus.org
> Date: Mon, 11 Jan 2016 20:10:26 +0100
> 
> Marking this as "wontfix" seems particularly inapplicable to me: This
> shortcoming crashes Emacs and potentially causes data loss for users,
> not only in such an artificial test case but in other situations too.
> This shortcoming prevents my testing Emacs in many other ways that would
> help me to find and correct more shortcomings and make Emacs more robust.

Sorry, I don't understand: what testing?  Can you describe the
real-life use case behind this bug report?  The recipe as shown looks
like a deliberate way to cause Emacs to overflow its stack; surely,
that's not what you intended to test?

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

From: markus.triska <at> gmx.at
To: eliz <at> gnu.org
Cc: alan <at> idiocy.org, larsi <at> gnus.org, 2099 <at> debbugs.gnu.org
Subject: Re: bug#2099: 23.0.60; `mark_object' with larger nested objects
 crashes Emacs
Date: Mon, 11 Jan 2016 20:57:49 +0100

> Sorry, I don't understand: what testing? Can you describe the
> real-life use case behind this bug report? The recipe as shown looks
> like a deliberate way to cause Emacs to overflow its stack; surely,
> that's not what you intended to test?

That's not what I intended to test: Emacs crashing on such datastructures
prevents more serious automatic tests that can, among other data, also
create such structures. So far, this shortcoming has prevented my working
further on such tests.

I find it hard to believe that a way to crash Emacs is somehow *not*
considered a bug. If that is the case, I agree with what Glenn recently
said: Just deal with this report in any way you wish.

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

From: Eli Zaretskii <eliz <at> gnu.org>
To: markus.triska <at> gmx.at
Cc: alan <at> idiocy.org, larsi <at> gnus.org, 2099 <at> debbugs.gnu.org
Subject: Re: bug#2099: 23.0.60; `mark_object' with larger nested objects
 crashes Emacs
Date: Mon, 11 Jan 2016 22:32:52 +0200

> From: markus.triska <at> gmx.at
> Cc: alan <at> idiocy.org, 2099 <at> debbugs.gnu.org, larsi <at> gnus.org
> Date: Mon, 11 Jan 2016 20:57:49 +0100
> 
> > Sorry, I don't understand: what testing? Can you describe the
> > real-life use case behind this bug report? The recipe as shown looks
> > like a deliberate way to cause Emacs to overflow its stack; surely,
> > that's not what you intended to test?
> 
> That's not what I intended to test: Emacs crashing on such datastructures
> prevents more serious automatic tests that can, among other data, also
> create such structures.

I'm asking to describe the data structures that you intended to test,
and their purpose.  The recipe that you posted when you filed the bug
conses an infinitely large object in an infinite loop.  Can you please
tell what is the purpose of creating such a data structure in this
way?  It's clear that at some point Emacs will run out of memory, and
it is also clear that at some other point it will GC.  So what is
being tested by such a data structure, given that these outcomes are
known in advance?

> So far, this shortcoming has prevented my working further on such
> tests.

Knowing more about those tests might help us become more motivated to
work on the problems that interfere with your testing, or suggest how
to work around them.

> I find it hard to believe that a way to crash Emacs is somehow *not*
> considered a bug.

There could be many ways to overcome these problems, some of them
easier than others.  It all depends on what problems get in your way.

For example, there could be a way of letting Emacs run out of heap
memory without triggering GC -- would that help you continue with your
testing?  I don't know, maybe you could tell.

IOW, if there are practical issues for which you'd like to have a
solution or a workaround, so that you could continue with your
testing, we could try helping you on that way.  I'm sure you agree
that leaving the bug without any action will not help you make any
progress with your project.  Please help us help you in any practical
way that's possible, by telling more about the specific aspects of
Emacs you'd like to test.

> If that is the case, I agree with what Glenn recently said: Just
> deal with this report in any way you wish.

Relax, no one said this isn't a bug, so this is uncalled for.  I'm
just trying to understand what is being tested here.  I couldn't
understand that from the recipe you posted, because that recipe has an
outcome that's known in advance.

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

From: Alan J Third <alan <at> idiocy.org>
To: markus.triska <at> gmx.at
Cc: eliz <at> gnu.org, larsi <at> gnus.org, 2099 <at> debbugs.gnu.org
Subject: Re: bug#2099: 23.0.60;
 `mark_object' with larger nested objects crashes Emacs
Date: Mon, 11 Jan 2016 20:32:48 +0000

markus.triska <at> gmx.at writes:

> I find it hard to believe that a way to crash Emacs is somehow *not*
> considered a bug. If that is the case, I agree with what Glenn recently
> said: Just deal with this report in any way you wish.

My thinking was simply that it sounds like it will require
reimplementation of the GC, and that's not likely to happen any time
soon, or perhaps ever.

Looking over the debbugs docs again, though, it should probably be
changed to wishlist, as Eli suggested originally. Like you say, a crash
is surely a bug, even if it is hard to fix.

FWIW I found a 'real-world' bug report, bug#16039, which appears to have
the same cause, although it requires a different remedy.
-- 
Alan Third

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

From: Eli Zaretskii <eliz <at> gnu.org>
To: Alan J Third <alan <at> idiocy.org>
Cc: larsi <at> gnus.org, 2099 <at> debbugs.gnu.org, markus.triska <at> gmx.at
Subject: Re: bug#2099: 23.0.60;
 `mark_object' with larger nested objects crashes Emacs
Date: Mon, 11 Jan 2016 22:45:42 +0200

> From: Alan J Third <alan <at> idiocy.org>
> Cc: eliz <at> gnu.org,  2099 <at> debbugs.gnu.org,  larsi <at> gnus.org
> Date: Mon, 11 Jan 2016 20:32:48 +0000
> 
> FWIW I found a 'real-world' bug report, bug#16039, which appears to have
> the same cause, although it requires a different remedy.

No, that's a different cause.  That bug is about stack overflow in
regexp matcher, not in GC.  Such stack overflows should nowadays be
recoverable (at least on most platforms), unlike a stack overflow in
GC that still isn't.

Previous Next

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