3 ms·
The GC needs to unwind the stack to find roots. The only difference between segmented stacks and contiguous stacks as far as unwinding the stack is concerned is
by pcwalton 3y ago
The GC needs to unwind the stack to find roots. The only difference between segmented stacks and contiguous stacks as far as unwinding the stack is concerned is that in segmented stacks the stack pointer isn't monotonically increasing as you go up. This is usually not a problem. (The only time I've seen it be a problem is in GDB, where some versions have a "stack corruption check" that ensures that the stack pointer is monotonically increasing and assumes the stack has been corrupted if it isn't. To make such versions of GDB compatible with segmented stacks, you just need to remove that check.)
Relocatable stacks are a different beast. With relocatable stacks, pointers into the stack move when the stack resizes. This means that you must be able to find those pointers, which may be anywhere in the stack or the heap, and update them. The garbage collector already knows how to do that--walking the heap is its job, after all--so typically resizable stacks are implemented by having the stack resizing machinery call into the GC to perform the pointer updates.
Note that, as an alternative implementation of relocatable stacks, you can simply forbid pointers into the stack. This means that your GC doesn't need to be moving. I believe that's what Go does, as as far as I'm aware Go doesn't have moving GC (though I'm not up to date and very much could be wrong here). This doesn't help Pike's argument, though, because in that scenario the impact of relocatable stacks on the GC is much less.
As an aside, in my view the legitimate reasons to not use LLVM would have been (1) compile times and (2) that precise GC, which Go didn't ship with but which was added not too long thereafter, was hard in LLVM at the time due to SelectionDAG and lower layers losing the difference between integer and pointer.
- zozbot234 3y ago> SelectionDAG and lower layers losing the difference between integer and pointer Doesn't pointer-provenance support address this point nowadays? AIUI, a barebones version of what amounts to provenance ("pointer safety" IIRC) was even included in the C++ standard as a gesture towards GC support. It's been removed from the upcoming version of the standard, having become redundant.
- pcwalton 3y agoI think CHERI addresses the issue, but I don't know how much of that is in upstream LLVM. Pointer provenance as used for optimization mostly affects the IR-level optimizations, not CodeGen ones. In any case, Azul's work addresses the GC metadata problem nowadays.
- typical182 3y ago> you can simply forbid pointers into the stack. This means that your GC doesn't need to be moving. I believe that's what Go does I might have misunderstood your comment, but FWIW, Go does allow pointers into the stack from the stack. When resizing/moving/copying a stack, the Go runtime does indeed find those pointers (via a stack map) and adjust them to point to the new stack locations. For example: https://github.com/golang/go/blob/b25f5558c69140deb652337afaab5c1186cd0ff1/src/runtime/stack.go#L678-L684 https://github.com/golang/go/blob/b25f5558c69140deb652337afa... (The growable stacks I think replaced the segmented stacks circa Go 1.3 or so; I can't speak to whether they were contemplating growable stacks in the early days whilst considering whether to start their project with the Plan 9 toolchain, LLVM, or GCC, but to your broader point, they were likely considering multiple factors, including how quickly they could adapt the Plan 9 toolchain).