[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Daniel Colascione
Subject: Let's make the GC safe and iterative (Was: Re: bug#30626)
Date: Thu, 1 Mar 2018 15:22:39 -0800
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.6.0

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

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:


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.


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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]