[PATCH 0/3] libstdc++: implement std::hazard_pointer (P2530R3, C++26)

[Paul Xi Cao]

Thanks for the review, and in particular for chasing R1 down with Maged
rather than just flagging it.  You were right; it is a real
use-after-free.

All four findings are addressed, plus two I found while doing so.  v2 is
posted as a separate thread, "[PATCH v2 0/3] libstdc++: Implement
std::hazard_pointer (P2530R3)".  The per-patch rationale is in the
commit messages there; below is only what answers the review.

1. Reclaim-side ordering.  Fixed: _M_synchronize() now executes a
   seq_cst atomic_thread_fence between the collect step and the record
   scan.  Your diagnosis carried over exactly, including the part that
   is the tempting one-line fix -- upgrading the scan's loads to
   seq_cst does not work, because the removal store on the source is
   user code that P2530R3 does not require to be seq_cst.

   I reproduced your herd7 verdicts independently before changing
   anything: Sometimes for the acquire scan, Sometimes for seq_cst
   snapshot loads without the fence, Never with the fence.  Those three
   tests now gate CI in the standalone prototype, which is also where
   every number below was measured:

     https://github.com/PaulXiCao/hazard_pointer_prototype

   They have no home in the libstdc++ tree, but I am happy to post them
   separately.

   I would still like the litmus tests you offered.  One consequence
   worth naming: R2 through R4 were done without your transcription as
   a cross-check on our abstraction of the algorithm, so if your files
   disagree with ours, what needs revisiting is the R1 argument itself,
   not just the files.

   One correction to a detail, because it changes how much a green
   concurrent.cc is worth.  x86 does not hide the litmus shape: over
   10^6 runs with litmus7 on x86_64 we see 1 positive for the acquire
   scan and 127 with seq_cst snapshot loads, 0 with the fence.  TSO
   permits exactly this StoreLoad reordering.  Your "x86 as compiled
   hides it" is right about the real code, where the reclaim path's
   mutex puts locked RMWs between the removal store and the scan -- a
   different program from the litmus test, and the distinction is now
   written into the test file so nobody reads a green x86 run as
   evidence of correctness.

2. retire() and noexcept.  Fixed, and it forced a decision I would
   rather the maintainers confirmed than take on my own authority.

   retire() is now a pointer splice onto an intrusive list whose link
   lives in the object.  There is no way to make it non-allocating
   otherwise -- a per-thread side table has to be grown by retire()
   itself -- and moving the storage into the object changes the layout
   of hazard_pointer_obj_base, a type users derive from, so its size
   lands in their binaries and doc/xml/manual/abi.xml lists that as a
   prohibited change after release.  v2 therefore takes P2530R3
   sec. 1.5 at its word and reserves both items it names, a cohort
   pointer and a 64-bit counter.  The reserved members are initialised
   now, because the constructor is inlined into user code; the
   corresponding check in retire() can wait, because nothing today can
   set a non-null cohort.  Precedent for the shape:
   chrono::tzdb_list::const_iterator's void* _M_reserved = nullptr.

   Three consequences I would rather flag than have found.  The type is
   no longer trivially copyable, both because reserving anything makes
   the default constructor non-trivial and because the "not retired"
   sentinel needs user-provided copy and move, or retiring a copy would
   look like a double retire.  The match key is now the private base
   subobject address on both sides rather than the T*, which is what
   makes struct T : Other, hazard_pointer_obj_base<T> correct.  And we
   are asking for more than the reference implementation gives: Folly's
   retire() is not noexcept and its do_reclamation() builds an
   F14FastSet, so matching Folly answers the intrusive push but not the
   guarantee the clause demands.

   The cost is memory: sizeof(hazard_pointer_obj_base<Node>) 1 -> 32,
   sizeof(Node) 16 -> 48, sizeof(hazard_pointer) 8 -> 8.  That is 32
   bytes per protectable object whether or not it is ever retired,
   against 16 bytes per retired object before.  It buys no speed --
   push-only retire() is 11.1ns against 11.2ns, the per-thread list
   mutex dominating both -- so the case for it is the noexcept
   guarantee alone.  (Amortised over reclamation retire() is 50.3ns
   against 66.7ns, but that is the scan improving, not the push.)
   The no-allocation claim is checked by a test that
   replaces the global allocation functions and was validated by
   reinstating an allocation on the retire path; the first control I
   tried, `delete new int`, is elided by the compiler and proved
   nothing.

3. Slot acquire/release cost.  Mostly settled by the layout work, and
   now measured.  Sec. 1.5 item 3 puts the reserved domain pointer in
   the record rather than the handle, which ruled out the obvious cheap
   fix of a slot index, since an index cannot name a domain.  With the
   handle holding a _Hazptr_rec* and one word wide, records became an
   append-only list that is never unlinked: the std::find_if, the deque
   and the free bitmap are gone, claiming a record is a flag CAS, and
   _M_synchronize() walks the list with no lock and no snapshot array.

   make_hazard_pointer() + ~hazard_pointer(), medians of 5, 6-core
   x86_64 (the 8- and 16-thread rows oversubscribe that box; read them
   as trends):

       threads     v1      v2
          1      16.8ns  14.9ns   1.13x
          2       218ns  68.7ns   3.2x
          4       297ns   298ns   equal
          8      1558ns   678ns   2.3x
         16      3511ns   930ns   3.8x

   Three things I do not want to oversell.  The win is contention
   scaling, not latency: 14.9ns single-threaded is against sec. 3.1's
   ~4ns, so v2 does not reach the paper's figure.  Claiming a handle
   with 256 already held is 1.3x slower than v1's bitmap search (36.2us
   against 27.3us), and _M_synchronize() likewise wins 1.4-2.0x up to
   256 records but loses 1.16x at 1024 -- cache-line-padded records in
   a linked list cannot prefetch like a contiguous pool, and records
   are never unlinked, so a process that once peaked at 1024 live
   handles pays that walk for the rest of its life.  And the benchmark
   caught a 6x regression before it
   shipped: the natural CAS-per-record claim walk costs a locked RMW
   per occupied record, so a 256-deep claim was 175us against v1's
   27us, fixed with test-and-test-and-set (36us now).  The
   architecture change had made your finding worse while looking like a
   fix, and only measuring found it -- which is also the honest answer
   to why there were no numbers in v1.

   protect()/reset_protection() is unchanged within noise, 4.27 ->
   4.33ns, which is the number that most needed not to regress.

4. concurrent.cc.  Correct, and worse than it looked: readers checked
   `p->value < 0` while writers only ever published `++counter`, so
   every "no data race" claim from that file was vacuous.  Rewritten;
   reclaimed nodes now go through a deleter that poisons them and parks
   them on a lock-free quarantine, so a reader that dereferences a
   reclaimed node observes the poison without reading freed memory, and
   every converted test asserts it observed at least one node.
   Validated by negative control rather than by a green run: breaking
   the protected-set check makes it abort on the error count.  3/3's
   commit message has the detail, including why writing the poison from
   ~Node() does not work.  This is also what your POWER9 repro was
   missing, and you said so yourself -- a clean run was inconclusive
   rather than exculpatory, because nothing in the test could have
   reported the failure.  It can now.

Two more, self-found rather than from the review.  v1 shipped a
bits/version.h whose condition for __cpp_lib_hazard_pointer was only
__cplusplus, although version.def declares the entry gthread and
hosted, so the macro was advertised on exactly the builds the gating
exists to exclude; fixed by regenerating with autogen, which produced
no other churn.  The v1 ChangeLog blocks were also space-indented.

Tomasz: both of the things you suggested in the RFC round, the
std::deque<_Slot> and std::find over the vector<bool> free bitmap, are
gone in v2.  That is not a rejection of the advice -- it was right for
the design it was given for, and Tom's review agreed those choices were
fine locally.  What removed them was sec. 1.5 item 3 forcing the handle
to hold a _Hazptr_rec*, after which the deque, the bitmap and the mutex
over them had nothing left to do.

Two questions that are maintainer calls rather than review comments:

  a. Is now the right moment to freeze the layout of
     hazard_pointer_obj_base, and are those the right two
     reservations?  The alternative is a smaller object and accepting
     that the paper's two extensions can never be added, so doing
     nothing decides it too.

  b. Is it acceptable to ship v2 with the known-slower deep-pool case
     and follow up with a performance patch?  The fix is per-thread
     record caching (Folly's hazptr_tc), which addresses both the
     14.9-vs-4ns gap and the 256-handle regression.  I propose
     deferring it because it is the one part of this work that is not a
     one-way door: it lives in thread-local storage inside the domain,
     hazard_pointer stays one word and hazard_pointer_obj_base is
     untouched.  I recognise this is the item most likely to draw an
     objection, given that you raised R3 as a performance finding.

Still open, so that none of it reads as an oversight: retire() can
throw from std::mutex::lock, which needs the per-thread retire list to
become lock-free; the protected-set buffer is the one allocation left
in reclamation, now reused across scans and falling back to a linear
membership test rather than deferring if it cannot grow; and contracts
integration remains deferred, waiting on a macro that says contracts
are evaluated rather than merely supported.

Disclosure: the prose of this message was rephrased with LLM
assistance.

Paul