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

[Po Lu]

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

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

I think a failed xmalloc will also make Emacs prompt to "C-x s, then
exit".  But the regular memory_full codepath might not work during
garbage collection.  (Mark bits get left around, for example).

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

Indeed.

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

I agree.

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

That code wasn't tested in an actual out-of-memory situation yet (it's
too soon to consider this), but hopefully it will work.  I think it
works when running out of memory in general, because otherwise it
wouldn't be what memory_full eventually asks the user to do.

Emacs keeps a small amount of malloc'd "spare memory" around during
normal execution, and frees it when running out of memory, so that some
allocation might be able to continue.  I didn't yet touch that
mechanism, but it should perhaps be replaced by a mechanism that
directly allocates objects out of that spare memory.

> That requires some careful invariant maintenance but I could see it
> working. Is the collector generational as well?

It isn't.

> Otherwise I suppose the total GC cost is higher than before, right?

Yes, the total GC cost is higher than before.  Lisp execution during the
garbage collection is also much slower than otherwise, since (for
starters) a linear search through the page aligned "block" of objects is
used every time a hardware write barrier is hit.  There's a lot of other
low hanging fruit for optimization as well, but it's too early to work
on those, since at present the garbage collector is not even working due
to the recent changes that added a manually managed stack to the
bytecode interpreter.

Thanks.