Idea for stack mini-GC: when a called function F returns to its parent function G, the value V it returns can only depend either on values in the context of the parent function (which are still accessible), or on values on the stack of F. We could therefore GC and compact only the stack of F, using V as root, and keep the stack of F as an extension of the stack of G. Any dependency in F whose memory location lies at an earlier point of the stack (before F's stack starts) does not need to be recorded or moved.
This movement can be generalized to a general maneuver "save value at stack index B to U, pop stack up to index A and push U". When it is guaranteed that every pointer on the stack always points to an earlier stack location, we can simply tag U as root, then sweep down from B to A, scan tagged areas for references which in turn tag references further back, then sweep up from A to B, compacting the stack. U will then sit on top of the stack as expected, with all its dependencies still intact. Without the address constraint (which is arguably more interesting as it allows for cyclical references), we need to maintain a temporary map of visited/relocated addresses and visit pointers with a temporary queue, both of which can live at the end of the stack. The size required for both is bounded by (B - A).
If U is returned through many functions though, the GC would needlessly run on every return. It would therefore make sense to delay the collection and just preserve the stack as-is, garbage and all, until the stack is large enough to warrant some cleanup. We keep track of a "waterline" tag T that marks the point up to which the stack is to be preserved. When we "pop" to an index K where K < T, then T is set to K, and the pop is not performed. When the difference between stack top and T exceeds a threshold, we finally perform the cleanup.
We can safely perform cheap regular stack pops where U does not contain any pointers.
Multithreading requires that the main thread must wait for all subthreads to join before returning, and that the stacks recovered from the subthreads, based on their returned value, must be merged with the main stack. It would be useful here to perform this as a per-thread GC that copies the memory to the main stack on compaction. Other than that, there is no limitation.
The maneuver is quite comparable to Cheney on the MTA, although with some differences:
- Functions are allowed to return when the returned value does not contain any pointers, as truncating the stack is then safe.
- Like in CotMTA, returning a pointer conceptually requires a continuation call instead, but unlike CotMTA, we also need to pass a stack index as "return address" that is used for the virtual "pop", to update the waterline and to possibly initiate the GC.
- After the GC is performed, the continuations must return only up to the waterline, and no further. In CotMTA, the entire stack returns.
- The benefit of our maneuver is that we always maximally mark the same amount of memory, making the GC incremental.
- We don't move values from stack to heap. The compaction occurs in-place.
- If the goal is to use the process stack, then it's possibly not doable in plain C, and would likely require custom calling conventions and assembly. Usage of an application maintained stack allocator poses no problem though.
- As such, it's an extension to arena allocators.