Comment by samsquire
3 years ago
if you need code to understand garbage collection, there is walkthrough of garbage collector and C code at http://maplant.com/gc.html is really helpful.
I tweaked it to work on amd64 and started adding register scanning based on what eatonphil's discord people told me to do.
https://github.com/samsquire/garbage-collector
It's not fit for any purpose but more of a learning exercise.
Bob Nystrom (of Game Programming Patterns, Crafting Interpreters, and dartfmt fame) also wrote a tutorial implementation[1], of a precise tracing GC as opposed to a conservative one.
Regarding register scanning in a conservative GC, Andreas Kling has made (or at least quoted) the amusing observation[2] that your C runtime already has a primitive to dump all callee-save registers to memory: setjmp(). So all you have to do to scan both registers and stack is to put a jmp_buf onto the stack, setjmp() to it, then scan the stack normally starting from its address.
[1] https://journal.stuffwithstuff.com/2013/12/08/babys-first-ga...
[2] https://youtu.be/IzB6iTeo8kk
Glibc's mangles some pointer registers in setjmp(). It XORs a per-process value with the stack pointer, frame pointer and instruction pointer stored in the jmp_buf, on all (or nearly all) architectures.
Although losing the stack and instruction pointers is unlikely to be a problem for the GC context, the frame pointer register need not contain a frame pointer value. It can be an arbitrary program value depending on compile options. That's something to watch out for with this GC technique.
You’re right, and I shouldn’t have dismissed the PTR_MANGLE business so easily when I looked at the source[1]. In hindsight, the __ILP32__ (i.e. x32) special case for the high part of %rbp on x86-64 looks awfully suspicious even if you don’t know the details.
Given that __attribute__((optimize("no-omit-frame-pointer"))) doesn’t seem to get GCC to save the parent frame pointer on the stack reliably, while Clang doesn’t understand that atribute (or #pragma GCC optimize(...)) at all, this now looks less slick than it initially seemed.
... Have I mentioned that I dislike hardening techniques?
[1] https://elixir.bootlin.com/glibc/glibc-2.37/source/sysdeps/x...
Implementations are unfortunately allowed to do whatever they want to that jmp_buf, they could xor the contents for all you know. Hopefully no implementation does something silly like that.
This seems like a reasonable environmental assumption if you’re already scanning the stack conservatively. I’d be more worried about pointer authentication (AArch64), pointer encryption (Glibc) or perhaps register windows (SPARC, Itanium). Still, as a cheap trick for avoiding assembly it seems to work well enough in non-exotic situations.
Seems like a reasonable thing to do to avoid forging jmp_bufs.
Side topic, but the maplant website design is great.
Besides the code blocks, it has 0 CSS. So what you're actually complementing is your browser's default styles for HTML