THE FOLD / RESPAWN / GARBAGE COLLECTION / THE HAZARD POINTER
THE HAZARD POINTER
say out loud which pointer you are holding
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
RCU waits for everyone. Magged Michael’s alternative asks each reader to say, out loud, which pointer it is using — and then the writer frees everything nobody named.
LIT verified live. enumerating all 20 interleavings of a three-step reader against a three-step writer, the protocol with the re-verification step suffers 0 use-after-free, aborting and retrying in 16 of them and deferring 16 frees. Delete the re-verification — publish the hazard pointer and dereference — and 3 of the same 20 touch reclaimed memory. The reclamation bound is the other half: 64 threads holding 2 hazard pointers each can strand at most 128 nodes, where a single RCU reader stalled across 50 grace periods at 100 nodes each strands 5,000 — 39 times more.
LIT verified live. enumerating all 20 interleavings of a three-step reader against a three-step writer, the protocol with the re-verification step suffers 0 use-after-free, aborting and retrying in 16 of them and deferring 16 frees. Delete the re-verification — publish the hazard pointer and dereference — and 3 of the same 20 touch reclaimed memory. The reclamation bound is the other half: 64 threads holding 2 hazard pointers each can strand at most 128 nodes, where a single RCU reader stalled across 50 grace periods at 100 nodes each strands 5,000 — 39 times more.
2 HOW IT WAS WEAVED · AI + HUMAN
Hazard pointers are Maged Michael’s (2004); the publish-verify-use protocol and the per-thread bound are his.
AVAN (AI) ran the enumeration to isolate which step does the work, because the interesting part of this algorithm is the one that looks redundant. Publishing the hazard pointer is not enough: the node can be unlinked and freed between the load and the publish, so the reader must re-read the shared pointer and confirm it is still the same. Removing only that step gives 3 of 20. It is a step whose entire justification is a window it is hard to believe exists.
AVAN (AI) ran the enumeration to isolate which step does the work, because the interesting part of this algorithm is the one that looks redundant. Publishing the hazard pointer is not enough: the node can be unlinked and freed between the load and the publish, so the reader must re-read the shared pointer and confirm it is still the same. Removing only that step gives 3 of 20. It is a step whose entire justification is a window it is hard to believe exists.
3 ONE DIMENSION
20 interleavings. The redundant-looking step is the whole protocol.
4 TWO DIMENSIONS · INTERACTIVE
Delete the re-verification and watch the window open.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that hazard pointers bound the garbage. The inverse is that they bound it by making every reader pay, forever, for a danger almost none of them are in. RCU costs readers nothing and reclaims late; hazard pointers reclaim promptly and charge every single read a store and a fence, whether or not any writer exists. Read backwards, the two are the same trade seen from opposite ends — and neither removes the cost of not knowing who is looking. One defers it into memory, the other collects it up front from everyone.
LIT enumerating all 20 interleavings of a three-step reader against a three-step writer, the protocol with the re-verification step suffers 0 use-after-free, aborting in 16 and deferring 16 frees; delete the re-verification and 3 of the same 20 touch reclaimed memory - and the bound is the other half, since 64 threads holding 2 hazard pointers each strand at most 128 nodes where one RCU reader stalled across 50 grace periods at 100 nodes each strands 5,000, 39 times more
FIG Hazard pointers are Maged Michael's (2004). AVAN ran the enumeration to isolate WHICH step does the work, because the interesting part of this algorithm is the one that looks redundant: the node can be unlinked and freed between the load and the publish, so the reader must re-read the shared pointer and confirm. Removing only that step gives 3 of 20 - a step whose entire justification is a window it is hard to believe exists.
FIG Hazard pointers are Maged Michael's (2004). AVAN ran the enumeration to isolate WHICH step does the work, because the interesting part of this algorithm is the one that looks redundant: the node can be unlinked and freed between the load and the publish, so the reader must re-read the shared pointer and confirm. Removing only that step gives 3 of 20 - a step whose entire justification is a window it is hard to believe exists.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of GARBAGE COLLECTION · David Lee Wise (ROOT0), with AVAN