bug#75322: SAFE_ALLOCA assumed to root Lisp_Objects/SSDATA(string)

[Daniel Colascione <dancol@dancol.org>]

On January 5, 2025 2:07:26 PM EST, Eli Zaretskii <eliz@gnu.org> wrote:
>> From: Gerd Möllmann <gerd.moellmann@gmail.com>
>> Cc: pipcet@protonmail.com,  75322@debbugs.gnu.org
>> Date: Sun, 05 Jan 2025 19:17:37 +0100
>> 
>> Eli Zaretskii <eliz@gnu.org> writes:
>> 
>> > OK, but in most, if not all of these cases, the objects are referenced
>> > from the stack.  For example, in the above fragment, the args[] array
>> > is on the stack.  Right?
>> 
>> That args is a parameter
>> 
>>   call_process (ptrdiff_t nargs, Lisp_Object *args, int filefd,
>> 
>> So just from this I see only args itself on the stack, not args[0],
>> args[1] and so on. I would have to look at all callers to determine
>> that. Not good enough in my book.
>
>So what, we will now need to copy every args[] into a Lisp vector
>created by SAFE_ALLOCA_LISP, or xstrdup all of them, and do it in
>each and every function that gets the args[] array, all the way down
>to where the array is finally used (because usually we have 3 or 4
>nested levels that pass args[] to one another)?  That's insane!
>
>> > What does it mean in detail "the object may move"?  A Lisp object is a
>> > tagged pointer.  Do you mean the pointer should no point to a
>> > different address, i.e. the value of a Lisp object as a number should
>> > change to still be valid?  
>> 
>> Exactly. Unless an ambiguous reference prevents the copying that can
>> happen.
>
>How can we possibly make sure this works reliably and safely??  For
>each variable we have in every function, we will need to analyze
>whether the variable is
>
>  . an automatic variable
>  . a static variable that is protected by someone
>  . a global variable that is protected by someone
>  . a result of dereferencing a pointer that is somehow protected
>
>etc. etc., where "protected by someone" means that it is a descendant
>of some staticpro, or of some root, or...

Well, yeah. Every other GC program does this. Emacs can too. There's no great burden: all Lisp objects get traced automatically. Everything on the stack or in a register gets traced automatically, and, because the scanning is conservative, pinned. You only have to take extra steps to tell the GC about something when you're going out of your way to go around the GC.

It's simply not true that to adopt a modern GC every line of code has to change.  I wrote a moving GC for Emacs myself years ago. Worked fine. No rewrite.

>And if we cannot prove to ourselves that one of the above happens,
>then we'd need to force a copy of the variable to be on the stack?
>
>Does this sound practical?
>
>If this is the price of using MPS, and I'm not missing something
>obvious, then it sounds like we should run away from MPS, fast.
>Because we will sooner or later have to rewrite every single line of
>code we ever wrote.

No, you do it by adopting a rule that when a function receives a pointer, the caller guarantees the validity of the pointer for the duration of the call. This way, only the level of the stack that spills the array to the heap has to take on the responsibility of keeping the referenced objects alive, and making the spilled array a pointer to the pinned guts of a Lisp vector is an adequate way to do this. 

"Oh, but won't that kill performance?"

In a generational system, allocating small, short-lived objects is actually cheap ---- usually faster than mallloc. I don't recall how MPS does it, but in some garbage collectors, a gen0 allocation of this sort is literally just incrementing a pointer.

Malloc has a substantial cost of its own too.

Yes, these objects make a gen0 GC happen sooner. So what? Young generation GC is cheap. If you could observe a performance problem, you could solve the reference problem by maintaining a thread local linked list of spilled array blocks and teach the GC to scan them, but that's likely overkill.

Anyway, every native code program anywhere that uses GC has to care about lifetimes and references.  Abandoning MPS doesn't magically make the problem go away. The *existing* code is broken, and you don't see it because we use alloca to allocate on the stack almost all the time.