the sticky mark-bit algorithm — wingologthe sticky mark-bit algorithm<br>22 October 2022 8:42 AM<br>garbage collection<br>mark-sweep<br>sticky mark bit<br>whippet<br>demers<br>javascriptcore<br>igalia<br>gc<br>Good day, hackfolk!
The Sticky Mark-Bit Algorithm
Also an intro to mark-sweep GC
7 Oct 2022 – Igalia
Andy Wingo
A funny post today; I gave an internal presentation at work recently<br>describing the so-called “sticky mark bit” algorithm. I figured I might<br>as well post it here, as a gift to you from your local garbage human.
Automatic Memory Management
“Don’t free, the system will do it for you”
Eliminate a class of bugs: use-after-free
Relative to bare malloc/free, qualitative performance improvements
cheap bump-pointer allocation
cheap reclamation/recycling
better locality
Continuum: bmalloc / tcmalloc grow towards GC
Before diving in though, we start with some broad context about<br>automatic memory management. The term mostly means “garbage<br>collection” these days, but really it describes a component of a system<br>that provides fresh memory for new objects and automatically reclaims memory for objects that won’t be needed in the program’s future. This stands in<br>contrast to manual memory management, which relies on the programmer<br>to free their objects.<br>Of course, automatic memory management ensures some valuable system-wide<br>properties, like lack of use-after-free<br>vulnerabilities. But also by<br>enlarging the scope of the memory management system to include full<br>object lifetimes, we gain some potential speed benefits, for example<br>eliminating any cost for free, in the case of e.g. a semi-space<br>collector.
Automatic Memory Management
Two strategies to determine live object graph
Reference counting
Tracing
What to do if you trace
Mark, and then sweep or compact
Evacuate
Tracing O(n) in live object count
I should mention that reference counting is a form of automatic memory<br>management. It’s not enough on its own; unreachable cycles in the object reference<br>graph have to be detected either by a heap tracer or broken by weak references.<br>It used to be that we GC nerds made fun of reference counting as being<br>an expensive, half-assed solution that didn’t work very well, but there have been<br>some fundamental advances in the state of the<br>art in<br>the last 10 years or so.<br>But this talk is more about the other kind of memory management, which<br>involves periodically tracing the graph of objects in the heap.<br>Generally speaking, as you trace you can do one of two things: mark<br>the object, simply setting a bit indicating that an object is live, or<br>evacuate the object to some other location. If you mark, you may<br>choose to then compact by sliding all objects down to lower addresses,<br>squeezing out any holes, or you might sweep all holes into a free list<br>for use by further allocations.
Mark-sweep GC (1/3)
freelist := []
allocate():<br>if freelist is empty: collect()<br>return freelist.pop()
collect():<br>mark()<br>sweep()<br>if freelist is empty: abort
Concretely, let’s look closer at mark-sweep. Let’s assume for the<br>moment that all objects are the same size. Allocation pops fresh<br>objects off a freelist, and collects if there is none. Collection does<br>a mark and then a sweep, aborting if sweeping yielded no free objects.
Mark-sweep GC (2/3)
mark():<br>worklist := []<br>for ref in get_roots():<br>if mark_one(ref):<br>worklist.add(ref)<br>while worklist is not empty:<br>for ref in trace(worklist.pop()):<br>if mark_one(ref):<br>worklist.add(ref)
sweep():<br>for ref in heap:<br>if marked(ref):<br>unmark_one(ref)<br>else<br>freelist.add(ref)
Going a bit deeper, here we have some basic implementations of mark<br>and sweep. Marking starts with the roots: edges from outside the<br>automatically-managed heap indicating a set of initial live objects.<br>You might get these by maintaining a stack of objects that are currently<br>in use. Then it traces references from these roots to other objects,<br>until there are no more references to trace. It will visit each live<br>object exactly once, and so is O(n) in the number of live objects.<br>Sweeping requires the ability to iterate the heap. With the<br>precondition here that collect is only ever called with an empty<br>freelist, it will clear the mark bit from each live object it sees, and<br>otherwise add newly-freed objects to the global freelist. Sweep is O(n)<br>in total heap size, but some optimizations can amortize this cost.
Mark-sweep GC (3/3)
marked := 1
get_tag(ref):<br>return *(uintptr_t*)ref<br>set_tag(ref, tag):<br>*(uintptr_t*)ref = tag
marked(ref):<br>return (get_tag(ref) & 1) == marked<br>mark_one(ref):<br>if marked(ref): return false;<br>set_tag(ref, (get_tag(ref) & ~1) | marked)<br>return true<br>unmark_one(ref):<br>set_tag(ref, (get_tag(ref) ^ 1))
Finally, some details on how you might represent a mark bit. If a ref<br>is a pointer, we could store the mark bit in the first word of the<br>objects, as we do here. You can choose instead to store them in a side<br>table, but it doesn’t matter for today’s example.
Observations
Freelist implementation crucial to allocation speed
Non-contiguous...