Subject: bug#54698: non-recursive GC marking [PATCH]

From: Mattias Engdegård <[email-masked]>
Date: Tue, 5 Apr 2022 10:08:11 +0200

5 apr. 2022 kl. 03.15 skrev Po Lu <[email-masked]>:

> What happens if it runs out of memory?

Good question! In theory the answer is simple: abort, as with any other failed xmalloc.

In practice, though, malloc probably won't fail at all -- more likely the OS will keep handing out addresses from its 64-bit space and slowly swap itself to death. On Linux, the out-of-memory killer will murder some essential processes at some point. If you have a hard disk you will at least get a premonition of what is going to happen from the rumbling.

But it would take a lot of heap for the mark stack requirements to become that big; it's much more likely that you run out of memory allocating your Lisp objects (or something else) first.

> The incremental GC I'm working on also has a similar stack for objects
> that have not been marked yet, and it also grows dynamically.

That's nice! I'm using a monolithic stack because it's easiest and gives good performance. A segmented stack would be an alternative for extreme memory conditions but the extra segment underflow checks would make the common case slower. (I have a patch for using a segmented stack in the bytecode engine, where it makes more sense and the overhead is lower, but it's still nonzero.)

> If growing the stack fails, it aborts garbage collection and tells the
> user to type C-x s and exit Emacs.

Frankly I wouldn't trust saving buffers to be possible when growing the mark stack wasn't. Have you actually tested this?

>   Objects are left with mark bits, but
> that is the case when Lisp code is allowed to run "between" parts of
> garbage collection anyway, and I hopefully did a good enough job fixing
> the code that assumed objects cannot have mark bits during regular Lisp
> execution.

That requires some careful invariant maintenance but I could see it working. Is the collector generational as well? Otherwise I suppose the total GC cost is higher than before, right?