Let's make the GC safe and iterative (Was: Re: bug#30626)

[Daniel Colascione]

Noam mentioned that I should make a new thread for this proposal, so I'm 
posting an edited version of my original message.
tl;dr: we should be able to make the GC non-recursive with minimal 
overhead, solving the "Emacs crashed because we ran out of stack space 
in GC" problem once and for all.
On 02/27/2018 10:08 AM, Eli Zaretskii wrote:
> What can we do instead in such cases?  Stack-overflow protection
> cannot work in GC, so you are shooting yourself in the foot by
> creating such large recursive structures.  By the time we get to GC,
> where the problem will happen, it's too late, because the memory was
> already allocated.
>
> Does anyone has a reasonable idea for avoiding the crash in such
> programs?
We need to fix GC being deeply recursive once and for all. Tweaking 
stack sizes on various platforms and trying to spot-fix GC for the 
occasional deeply recursive structure is annoying. Here's my proposal:
I. NAIVE APPROACH

Turn garbage_collect_1 into a queue-draining loop, initializing the 
object queue with the GC roots before draining it. We'll make 
mark_object put an object on this queue, turning the existing 
mark_object code into a mark_queued_object function.
garbage_collect_1 will just call mark_queued_object in a loop; 
mark_queued_object can call mark_object, but since mark_object just 
enqueues an object and doesn't recurse, we can't exhaust the stack with 
deep object graphs. (We'll repurpose the mark bit to mean that the 
object is on the to-mark queue; by the time we fully drain the queue, 
just before we sweep, the mark bit will have the same meaning it does now.)
We can't allocate memory to hold the queue during GC, so we'll have to 
pre-allocate it. We can implement the queue as a list of queue blocks, 
where each queue block is an array of 16k or so Lisp_Objects. During 
allocation, we'll just make sure we have one Lisp_Object queue-block 
slot for every non-self-representing Lisp object we allocate.
Since we know that we'll have enough queue blocks for the worst GC case, 
we can have mark_object pull queue blocks from a free list, aborting if 
for some reason it ever runs out of queue blocks. (The previous 
paragraph guarantees we won't.) garbage_collect_1 will churn through 
these heap blocks and place each back on the free list after it's called 
mark_queued_object on every Lisp_Object in the queue block.
In this way, in non-pathological cases of GC, we'll end up using the 
same few queue blocks over and over. That's a nice optimization, because 
we can MADV_DONTNEED unused queue blocks so the OS doesn't actually have 
to remember their contents.
In this way, I think we can make the current GC model recursion-proof 
without drastically changing how we allocate Lisp objects. The 
additional memory requirements should be modest: it's basically one 
Lisp_Object per Lisp object allocated.
II. ELABORATION

The naive version of this scheme needs about 4.6MB of overhead on my 
current 20MB Emacs heap, but it should be possible to reduce the 
overhead significantly by taking advantage of the block allocation we do 
for conses and other types --- we can put whole blocks on the queue 
instead of pointers to individual block parts, so we can get away with a 
much smaller queue.
It's also interesting to note that we don't need separate queue blocks 
to put a block on the queue, as we do if we want to enqueue individual 
Lisp_Object pointers. Instead, we can add to each block type a pointer 
to the next block *on the to-be-marked queue* and a bitmask yielding the 
positions within that block that we want to mark.
For example, cons_block right now looks like this:

struct cons_block
{
  /* Place `conses' at the beginning, to ease up CONS_INDEX's job.  */
  struct Lisp_Cons conses[CONS_BLOCK_SIZE];
  bits_word gcmarkbits[1 + CONS_BLOCK_SIZE / BITS_PER_BITS_WORD];
  struct cons_block *next;
};

We'd turn it into something like this:

struct cons_block
{
  /* Place `conses' at the beginning, to ease up CONS_INDEX's job.  */
  struct Lisp_Cons conses[CONS_BLOCK_SIZE];
  bits_word gcmarkbits[1 + CONS_BLOCK_SIZE / BITS_PER_BITS_WORD];
  bits_word scan_pending[1 + CONS_BLOCK_SIZE / BITS_PER_BITS_WORD];
  struct cons_block *next;
  struct cons_block *next_scan_pending;
};

When we call mark_object on a cons, we'll look up its cons_block and 
look up the cons in gcmarkbits. If we find the cons mark bit set, we're 
done. Otherwise, we look at the scan_pending bit for the cons cell. If 
_that's_ set, we're also done. If we find the scan_pending bit unset, 
however, we set it, and then look at next_scan_pending. If that's 
non-zero, we know the block as a whole is enqueued for scanning, and 
we're done. If *that's* zero, then we add the whole block to the 
to-be-scanned queue.
We'll modify garbage_collect_1 to drain both the Lisp_Object queue I 
described in the last section (which we still need for big objects like 
buffers) *and* the queue of blocks pending scanning. When we get a cons 
block, we'll scan all the conses with scan_pending bits set to one, set 
their gcmarkbits, and remove the cons block from the queue.
That same cons block might make it back onto the queue later if someone 
calls mark_object for one if its conses we didn't already scan, but 
that's okay. Scanning scan_pending should be very cheap, especially on 
modern CPUs with bit-prefix-scan instructions.
Under this approach, the reserved-queue-block scheme would impose an 
overhead of somewhere around 1MB on the same heap. (I think it'd 
actually be a bit smaller actually.) Conses, strings, and vectors are 
the overwhelming majority of heap-allocated objects, and thanks to block 
packing, we'd get bookkeeping for them for practically free. This amount 
of overhead seems reasonable. I think we may end up actually using less 
memory that we would for recursive mark_object stack invocation.
This scheme interacts well with the portable dumper too. pdumper already 
uses a big bit array to store mark bits; we'd just add another array for 
its scan_pending. We'd basically treat the entire pdumper region as one 
big cons_block for GC purposes.
What do you think? I think this approach solves a longstanding fiddly 
problem with Emacs GC without too much disruption to the internals. It 
also paves the way for concurrent or generational GC if we ever want to 
implement these features.