GNU bug report logs - #54501
Segfault on recursive structure

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 54501 in the body.
You can then email your comments to 54501 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: Andy Gaynor <goldipox <at> mail.com>
To: bug-gnu-emacs <at> gnu.org
Subject: 27.2; to be disclosed in private
Date: Mon, 21 Mar 2022 15:26:02 +0100

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

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

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Andy Gaynor <goldipox <at> mail.com>
Cc: 54501 <at> debbugs.gnu.org, Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: Re: bug#54501: Segfault on recursive structure
Date: Tue, 22 Mar 2022 15:44:43 +0100

So this bug report is about two things.  The first is that this reads to
(nil):

#0=#0#

Which seems odd.  Reading #0=#1# signals an error, but it's not
immediately clear to me whether #0=#0# is totally nonsensical or not.
And if not, is (nil) the right result?  Anybody?

The other thing is more serious, and reading the following will segfault
your Emacs, so don't do that:

#0=[#1=(#0# . #1#)]

Now, Emacs segfaults on trying to gc a number of recursive objects
(especially ones that recurse in the `car'), but this seems to actually
segfault in the reader.  Is it obvious to anybody why?

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

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

From: Andreas Schwab <schwab <at> linux-m68k.org>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: Andy Gaynor <goldipox <at> mail.com>, 54501 <at> debbugs.gnu.org,
 Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: Re: bug#54501: Segfault on recursive structure
Date: Tue, 22 Mar 2022 16:02:57 +0100

On Mär 22 2022, Lars Ingebrigtsen wrote:

> So this bug report is about two things.  The first is that this reads to
> (nil):
>
> #0=#0#
>
> Which seems odd.  Reading #0=#1# signals an error, but it's not
> immediately clear to me whether #0=#0# is totally nonsensical or not.
> And if not, is (nil) the right result?  Anybody?

That's an side effect of the implementation: (nil) is the placeholder
object which #0# then references.

> The other thing is more serious, and reading the following will segfault
> your Emacs, so don't do that:
>
> #0=[#1=(#0# . #1#)]
>
> Now, Emacs segfaults on trying to gc a number of recursive objects
> (especially ones that recurse in the `car'), but this seems to actually
> segfault in the reader.  Is it obvious to anybody why?

Does it crash in substitute_object_recurse?

-- 
Andreas Schwab, schwab <at> linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

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

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Andreas Schwab <schwab <at> linux-m68k.org>
Cc: Andy Gaynor <goldipox <at> mail.com>, 54501 <at> debbugs.gnu.org,
 Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: Re: bug#54501: Segfault on recursive structure
Date: Tue, 22 Mar 2022 16:04:19 +0100

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

> That's an side effect of the implementation: (nil) is the placeholder
> object which #0# then references.

Ah, right.  Should it signal an error instead, do you think?

> Does it crash in substitute_object_recurse?

Yup.

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

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

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Andy Gaynor <goldipox <at> mail.com>
Cc: 54501 <at> debbugs.gnu.org
Subject: Re: bug#54501: Segfault on recursive structure
Date: Fri, 25 Mar 2022 16:34:30 +0100

(Re-sending for the bug tracker.)

Andy Gaynor <goldipox <at> mail.com> writes:

>> #0=#0#  =  (nil)
>
> This error is intrinsic to the process, much like the first time Scheme
> sees (define z z).  It probably needs to be checked explicitly--when
> first defining a label, its value cannot be a reference to that label.
> If the label is already defined, dandy, nothing to check or initialize.
>
> That (nil) = (nil . nil) looks suspiciously stubby.  (Nil nil nil, so
> much nil in the world, the most distinguished value in the language,
> tossed around so casually.)  I wouldn't be surprised to learn that it's
> an optimization, a speculative initialization favoring the common case of
> defining a label to a pair.  I could be wrong.  Hmmm, (#0=3 #0=#0#) is
> well-defined, and should be (3 3).  Or prohibited for no good reason,
> which seems to be the trend nowadays.  Prohibiting this is consistent
> with prohibiting assignments and restricting alists to only allow one
> association per key.  Stupid.  (Oh, did I write that out loud?)
>
> In Emacs, (#0=3 #0=#0#) = (3 (nil)), ung, (nil . nil) again.  Given that
> [#0=3 #0=#0#] = [3 3] and #s(#0=Z #0=#0#) = #s(Z Z), I'm more inclined to
> call this another pair-handling error.
>
>> Emacs segfaults on trying to gc a number of recursive objects,
>> but #0=[#1=(#0# . #1#)] seems to actually segfault in the reader.
>> Is it obvious to anybody why?
>
> Perhaps this instance is more... distilled.  Both objects are labeled,
> both labels are used, all components are labels, and one is self-cyclic.
> Note that the expression crashes when either pair component is
> self-cyclic, and doesn't crash when- Strike that, let's start with simple
> and work our way up.
>
>   #0=(#0# . #0#)  =  #1=(#1# . #1#)  =  ok
>
>   #1=#0=[#0#   #0#]  =   #1=[#1#   #1#]         =  ok
>   #1=#0=(#0# . #0#)  =  (#1=(#1# . #1#) . #1#)  =  bad
>
>   #2=#1=#0=[#0#   #0#]  =    #1=[#1#   #1#]         =  ok
>   #2=#1=#0=(#0# . #0#)  ->  (#1=(#1# . #1#) . #1#)  =  bad
>
> Another bug manifesting for pairs and not other stuff?  I'm satisfied.
>
> I haven't looked inside Emacs yet, but usually, most types are treated
> much the same, but pairs are augmented with optimizations for lists,
> making them more complicated.  Heck, in my still-skeletal fasl, arrays
> are handled with 4 instructions, the model-to-be for most referential
> types.  However, pairs/lists have 11 instructions, handling list and
> list* under various conditions (automatically selected, of course).  I
> added the list optimizations very early, in near isolation, because this
> is subtle business.
>
> I just polled 24 Lisps.  9 didn't implement labels.  2 gave me guff
> (dammit Racket and a no-name), so screw 'em.  Of the 13 left, the same 5
> flubbed label-thyself and relabel-thyself.  4 flubbed #0=(#0# . #0#), and
> 3 flubbed #0=[#1=(#0# . #1#)].  The point, oh yeah.  These folks are
> skilled programmers on familiar turf and still have problems.  Being a
> GNU venue, I'll mention that GCL failed to build (incorrectly setting
> things up for signal.h?) and Guile flubbed all four tests.
>
> Other than the label issues and pairs/lists going to hell in a humv, do
> things seem ok?  I just fed emacs a lot of funk, but with no pairs/lists
> or fringe label cases, and everything worked.  I recommend running with
> that, which seems safer than trying to debug something unfamiliar that
> trips up everyone.  Make a working copy of read.  Completely remove any
> handling for pairs/lists, label stubs, whatever.  Make labels nice, work
> the kinks out of the fringe cases.  Add pairs back generically, coded
> much like everything else--no label or list optimizations.  When you've
> got it right, commit to the copy.  The snipped optimizations can be
> snarfed from a trusted source (no guff or flubs from Bigloo, Chez, Clisp,
> Gambit, Gauche, Kawa, SBCL) at your convenience.  Kawa was the one that
> retained label redefinitions, making it worth a peek.
>
> Regards, Andy

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

From: Mattias Engdegård <mattiase <at> acm.org>
To: Andy Gaynor <goldipox <at> mail.com>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>, 54501 <at> debbugs.gnu.org,
 Andreas Schwab <schwab <at> linux-m68k.org>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: bug#54501: Segfault on recursive structure
Date: Sat, 26 Mar 2022 16:58:53 +0100

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

> #0=[#1=(#0# . #1#)]

When the reader encounters an expression in the form #N=X, the following steps take place:

1. Create a placeholder value P which is a fresh (nil . nil) cons pair.
2. Assign the number N to P in the read_objects_map.
3. Read X as the value V, where P is used for any occurrences of #N#.
4. Add V to the read_objects_completed set. This is used for future substitutions.
5. Traverse V to replace any occurrence of P with V itself, and return V so modified.

So far all good, but there is an optimisation: if X is a cons, then step 5 is skipped. Instead, since P is already a cons, its CAR and CDR slots are modified to those of V, and P is returned. That way no potentially expensive traversal of V is required.

The alert (human) reader has now spotted the error in the (lisp) reader: step 4 added the now defunct value V to read_objects_completed, not the actually returned value P. The traversal of the outer value, the vector #0 in the above example, will then enter infinite recursion because value #1 was never added to read_objects_completed.

The simplest solution is to remove the optimisation but I'd say it's algorithmically valuable and propose the attached patch.

The patch fixes the #0=#0# nonsense as well since it's a trivial check. Admittedly it doesn't handle #1=#2=#1# -- please keep this bug open if you think it's important.

[0001-Fix-reader-infinite-recursion-for-circular-mixed-typ.patch (application/octet-stream, attachment)]

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

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Andy Gaynor <goldipox <at> mail.com>, 54501 <at> debbugs.gnu.org,
 Andreas Schwab <schwab <at> linux-m68k.org>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#54501: Segfault on recursive structure
Date: Sat, 26 Mar 2022 17:33:22 +0100

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

> The patch fixes the #0=#0# nonsense as well since it's a trivial
> check.

Thanks; seems to work perfectly.

Do you think this is safe enough to go on the release branch?

This isn't a regression (Emacs has segfaulted on the #0=[#1=(#0# . #1#)]
as far back as I have Emacs versions), so I'd tend toward thinking it's
not vital enough to install on the release branch, but perhaps Eli has a
different opinion.  Eli?

> Admittedly it doesn't handle #1=#2=#1# -- please keep this bug
> open if you think it's important.

No, I think this fix is sufficient.

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

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

From: Mattias Engdegård <mattiase <at> acm.org>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: Andy Gaynor <goldipox <at> mail.com>, 54501-done <at> debbugs.gnu.org,
 Andreas Schwab <schwab <at> linux-m68k.org>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#54501: Segfault on recursive structure
Date: Sat, 26 Mar 2022 18:43:23 +0100

26 mars 2022 kl. 17.33 skrev Lars Ingebrigtsen <larsi <at> gnus.org>:

> Do you think this is safe enough to go on the release branch?
> 
> This isn't a regression (Emacs has segfaulted on the #0=[#1=(#0# . #1#)]
> as far back as I have Emacs versions), so I'd tend toward thinking it's
> not vital enough to install on the release branch

The context of the bug wasn't clear to me, but I didn't get the impression that it was impeding normal Emacs usage. I'm committing the patch to master for now.

Thanks for taking a look!

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

From: Eli Zaretskii <eliz <at> gnu.org>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: mattiase <at> acm.org, 54501 <at> debbugs.gnu.org, schwab <at> linux-m68k.org,
 monnier <at> iro.umontreal.ca, goldipox <at> mail.com
Subject: Re: bug#54501: Segfault on recursive structure
Date: Sat, 26 Mar 2022 21:00:48 +0300

> From: Lars Ingebrigtsen <larsi <at> gnus.org>
> Cc: Andy Gaynor <goldipox <at> mail.com>,  54501 <at> debbugs.gnu.org,  Stefan Monnier
>  <monnier <at> iro.umontreal.ca>,  Andreas Schwab <schwab <at> linux-m68k.org>, Eli
>  Zaretskii <eliz <at> gnu.org>
> Date: Sat, 26 Mar 2022 17:33:22 +0100
> 
> Mattias Engdegård <mattiase <at> acm.org> writes:
> 
> > The patch fixes the #0=#0# nonsense as well since it's a trivial
> > check.
> 
> Thanks; seems to work perfectly.
> 
> Do you think this is safe enough to go on the release branch?
> 
> This isn't a regression (Emacs has segfaulted on the #0=[#1=(#0# . #1#)]
> as far back as I have Emacs versions), so I'd tend toward thinking it's
> not vital enough to install on the release branch, but perhaps Eli has a
> different opinion.  Eli?

I think we shouldn't install this on the release branch, it's too
risky, and the original problem has been with us forever, or
thereabouts.

Previous Next

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