Hello all, and happy new year. Today's note continues the series onimplementing ephemerons in a garbagecollector.
In our lastdispatch welooked at a serial algorithm to trace ephemerons. However, productiongarbage collectors are parallel: during collection, they tracethe object graph using multiple worker threads. Our problem is toextend the ephemeron-tracing algorithm with support for multiple tracingthreads, without introducing stalls or serial bottlenecks.
Recall that we ended up having to define a table of pending ephemerons:
struct gc\_pending\_ephemeron\_table { struct gc\_ephemeron *resolved; size\_t nbuckets; struct gc\_ephemeron *buckets[0];};This table holds pending ephemerons that have been visited by thegraph tracer but whose keys haven't been found yet, as well as asingly-linked list of resolved ephemerons that are waiting to havetheir values traced. As a global data structure, the pending ephemerontable is a point of contention between tracing threads that we need todesign around.
Allow me to confess my sins: things would be a bit simpler if I didn'tallow tracing workers to race.
As background, if your GC supports marking in place instead of alwaysevacuating, then there is a mark bit associated with each object. Toreduce the overhead of contention, a common strategy is to actually usea whole byte for the mark bit, and to write to it using relaxed atomics(or even raw stores). This avoids the cost of a compare-and-swap, butat the cost that multiple marking threads might see that an object'smark was unset, go to mark the object, and think that they were thethread that marked the object. As far as the mark byte goes, that's OKbecause everybody is writing the same value. The object gets pushed onthe to-be-traced grey object queues multiple times, but that's OK too becausetracing should be idempotent.
This is a common optimization for parallel marking, and it doesn't haveany significant impact on other parts of the GC--except ephemeronmarking. For ephemerons, because the state transition isn't simply fromunmarked to marked, we need more coordination.
The parallel ephemeron marking algorithm modifiesthe serial algorithm in just a few ways:
We have an atomically-updated state field in the ephemeron, usedto know if e.g. an ephemeron is pending or resolved;
We use separate fields for the pending and resolved links, toallow for concurrent readers across a state change;
We introduce "traced" and "claimed" states to resolve races betweenparallel tracers on the same ephemeron, and track the "epoch" atwhich an ephemeron was last traced;
We remove resolved ephemerons from the pending ephemeron hash tablelazily, and use atomic swaps to pop from the resolved ephemeronslist;
We have to re-check key liveness after publishing an ephemeron tothe pending ephemeron table.
Regarding the first point, there are four possible values for theephemeron's state field:
enum { TRACED, CLAIMED, PENDING, RESOLVED};The state transition diagram looks like this:
,----->TRACED<-----. , | ^ ., v | .| CLAIMED || ,-----/ \---. || v v |PENDING--------->RESOLVED
With this information, we can start to flesh out the ephemeron objectitself:
struct gc\_ephemeron { uint8\_t state; uint8\_t is\_dead; unsigned epoch; struct gc\_ephemeron *pending; struct gc\_ephemeron *resolved; void *key; void *value;};The state field holds one of the four state values; is\_deadindicates if a live ephemeron was ever proven to have a dead key, or ifthe user explicitly killed the ephemeron; and epoch is the GC count atwhich the ephemeron was last traced. Ephemerons are born TRACED inthe current GC epoch, and the collector is responsible for incrementingthe current epoch before each collection.
When the collector first finds an ephemeron, it does a compare-and-swap(CAS) on the state from TRACED to CLAIMED. If that succeeds, wecheck the epoch; if it's current, we revert to the TRACED state:there's nothing to do.
(Without marking races, you wouldn't need either TRACED or CLAIMED states, or the epoch; it would be implicit in the fact that the ephemeron was being traced at all that you had a TRACED ephemeron with an old epoch.)
So now we have a CLAIMED ephemeron with an out-of-date epoch. We update the epoch and clear the pending and resolvedfields, setting them to NULL. If, then, the ephemeron is\_dead, we aredone, and we go back to TRACED.
Otherwise we check if the key has already been traced. If so weforward it (if evacuating) and then trace the value edge as well, andtransition to TRACED.
Otherwise we have a live E but we don't know about K; this ephemeronis pending. We transition E's state to PENDING and add it to the front of K's hash bucket in the pending ephemerons table, using CAS to avoid locks.
We then have to re-check if K is live, after publishing E, toaccount for other threads racing to mark to K while we mark E; ifindeed K is live, then we transition to RESOLVED and push E on theglobal resolved ephemeron list, using CAS, via the resolved link.
So far, so good: either the ephemeron is fully traced, or it's pendingand published, or (rarely) published-then-resolved and waiting to betraced.
The annoying thing about tracing ephemerons is that it potentiallyimpacts tracing of all objects: any object could be the key thatresolves a pending ephemeron.
When we trace an object, we look it up in the pending ephemeron hashtable. But, as we traverse the chains in a bucket, we also load each node's state. If we find a nodethat's not in the PENDING state, we atomically forward its predecessorto point to its successor. This is correct for concurrent readers because theend of the chain is always reachable: we only skip nodes that are notPENDING, nodes never become PENDING after they transition away frombeing PENDING, and we only add PENDING nodes to the front of thechain. We even leave the pending field in place, so that anyconcurrent reader of the chain can still find the tail, even when theephemeron has gone on to be RESOLVED or even TRACED.
(I had thought I would need Tim Harris' atomic listimplementation, but it turnsout that since I only ever insert items at the head, having annotatedlinks is not necessary.)
If we find a PENDING ephemeron that has K as its key, then we CASits state from PENDING to RESOLVED. If this works, we CAS it ontothe front of the resolved list. (Note that we also have to forward thekey at this point, for a moving GC; this was a bug in my originalimplementation.)
Periodically a thread tracing the graph will run out of objects to trace(its mark stack is empty). That's a good time to check if there areresolved ephemerons to trace. We atomically exchange the globalresolved list with NULL, and then if there were resolved ephemerons,then we trace their values and transition them to TRACED.
At the very end of the GC cycle, we sweep the pending ephemeron table,marking any ephemeron that's still there as is\_dead, transitioningthem back to TRACED, clearing the buckets of the pending ephemerontable as we go.
So that's it. There are some drawbacks, for example that this solutiontakes at least three words per ephemeron. Oh well.
There is also an annoying point of serialization, which is related tothe lazy ephemeron resolution optimization. Consider that checking the pendingephemeron table on every object visit is overhead; it would be nice toavoid this. So instead, we start in "lazy" mode, in which pendingephemerons are never resolved by marking; and then once the mark stack /grey object worklist fully empties, we sweep through the pendingephemeron table, checking each ephemeron's key to see if it was visitedin the end, and resolving those ephemerons; we then switch to "eager"mode in which each object visit could potentially resolve ephemerons.In this way the cost of ephemeron tracing is avoided for that part ofthe graph that is strongly reachable. However, with parallel markers,would you switch to eager mode when any thread runs out of objects tomark, or when all threads run out of objects? You would get greatestparallelism with the former, but you run the risk of some workersprematurely running out of data, but when there is still a significantpart of the strongly-reachable graph to traverse. If you wait for allthreads to be done, you introduce a serialization point. There is arelated question of when to pump the resolved ephemerons list. Butthese are engineering details.
Speaking of details, there are some gnarly pitfalls, particularly that you have to be very careful about pre-visit versuspost-visit object addresses; for a semi-space collector, visiting anobject will move it, so for example in the pending ephemeron table whichby definition is keyed by pre-visit (fromspace) object addresses, you need to be sure totrace the ephemeron key for any transition to RESOLVED, and there are afew places this happens (the re-check after publish, sweeping the table after transitioning from lazy to eager, and whenresolving eagerly).
If you've read this far, you may be interested in theimplementation;it's only a few hundred lines long. It took me quite a while to whittleit down!
Ephemerons are challenging from a software engineering perspective,because they are logically a separate module, but they interact both withusers of the GC and with the collector implementations. It's trickyto find the abstractions that work for all GC algorithms, whether theymark in place or move their objects, and whether they mark the heapprecisely or if there are some conservative edges. But if this is thesort of thing that interests you, voilà the API forusers andthe API to and from collectorimplementations.
And, that's it! I am looking forward to climbing out of this GC hole,one blog at a time. There are just a few more features before I canseriously attack integrating this into Guile. Until the next time,happy hacking :)