Further ponder reworking allocator ephemeral claim implementation

Writing this down just to get it out of my head so I can stop thinking about it...

The allocator's ephemeral claim ("hazard" and "hazard quarantine") machinery uses two arrays, both with size 2 * threads * sizeof(void*):

• a static shared object that's excitingly carved up by the loader and directly mutable by other threads, and
• a private array at the top of the heap arena that holds, essentially, a snapshot of the former. Each free operation involves O(threads * (1 + live ephemeral claims)) work on these structures (that can't skip it; no client free can skip):
• of course there's the O(threads) work to see if the to-be-freed object is ephemerally claimed (note that the allocation being tested here is whole and not a subobject), but first we had to...
• rescan the live ephemeral claims, which is again an O(threads) operation per live ephemeral claim (which, again, are whole allocations, not proper subobjects).

It would be really nice to have something linear, rather than quadratic, here... alas the need to support ephemeral claims on subobjects is challenging!

---

Just to write it down, I had been considering a revised design which additionally...

• increased the size of the private array to have room for exactly one more pointer
• allocated a three-value field in the object header for tracking ephemeral claim state. Call its values ECNo, ECDying, and ECActive. In the steady state, all objects are either ECNo or ECActive, and all and only ECActive objects are enumerated in the array of live ephemeral claims.

So equipped, on each free, we would then, with the allocator lock held...

1. walk the private list (of ECActive objects), moving them all to ECDying but leaving them on the list.
2. increment (make odd) the ephemeral claim epoch
3. walk the public list of requested ephemeral claims to move ECDying objects to ECActive.
   • Alas, this requires mapping each public request back to its containing object!
4. walk the private list, freeing anything still ECDying and compacting the private array. At most 2 * threads objects survive this culling, meaning the private array cannot be full.
5. walk the public list again, looking for (subobjects of) the object being freed, like now. If such is found, mark the object ECActive and append it to the private list.
6. increment (make even) the ephemeral claim epoch. (We would probably want some machinery to delay revocation for the duration, batching quarantine until after the epoch is even again.)

This requires O(threads) work, in the sense that each walk is linear and each probe of object headers constant time. Alas, in practice, it is probably worse because every free now incurs the cost of mapping all public requests to their object headers, though.