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

[Thomas Rodgers]

Thanks for taking this on, the test matrix and the memory-ordering
write-up in your patch announcement made the review much easier.

1. Reclaim-side memory ordering - This is a real use-after-free on
   weak-memory targets, and I confirmed the finding with Maged.
   _M_synchronize() snapshots the slots with memory_order_acquire.
   The reader side is correct (the hazard store and the validation
   reload are both seq_cst) but an acquire load on the scan side does
   not join the seq_cst total order, and the collect step's lock chain
   only orders the *writer's* retirement against the collect, not the
   independent reader's hazard store against the scan.

   Your announcement cites P2530R3's seq_cst/acquire pairing, but the
   acquire prescribed there is the reader's try_protect reload; the scan
   is constrained by [saferecl.hp.general] p6, which wants the end of
   the protection epoch to strongly happen before the reclamation, and
   an acquire-only scan doesn't give you that.

   Concretely: src == O; a reader does hazard.store(O, seq_cst) then
   reloads src seq_cst and still sees O, so it believes O is protected;
   a writer swaps O out and retires it; the reclaimer's acquire-load
   reads a stale null, does not see the hazard, and frees O; the reader
   then dereferences freed memory.

   x86 as compiled hides it (the seq_cst store's fence and the locked
   RMWs on the reclaim path), but the abstract machine permits it, so
   weaker targets (POWER) and future compiler transformations are
   entitled to it. Fix: a seq_cst fence between the collect step and the
   snapshot loop (the snapshot loads can then stay acquire). Upgrading
   the loads alone doesn't close it, the removal store on src is user
   code and P2530R3 doesn't require it to be seq_cst.

   I checked the shape with herd7: the bad outcome is allowed as written
   (acquire scan), still allowed with seq_cst snapshot loads when the
   removal store is only release, and forbidden with the fence. On
   POWER9 and POWER10 (compile farm, litmus7 7.58) the acquire scan
   reordering is observed on hardware, up to 1.4M of 959M runs, and the
   fence stays at zero across ~10^9. Folly's implementation agrees,
   do_reclamation() issues a seq_cst asymmetric_thread_fence_heavy
   immediately before load_hazptr_vals() and the slot loads themselves
   are only relaxed (acquire only under TSan). I can post the litmus
   tests if that's useful.

2. retire() and noexcept - retire() is noexcept per [saferecl.hp.base]
   and your noexcept.cc rightly asserts it, but the current path pushes
   onto a std::vector and may call _M_synchronize(), which also
   allocates, so OOM becomes terminate(). Strictly that's a QoI question
   rather than a conformance one, but the clause's shape says what's
   intended: make_hazard_pointer gets an explicit "Throws: May throw
   bad_alloc" while retire is noexcept with even the deleter move-assign
   covered by precondition, and P2530R3's ABI guidance (section 1.5)
   already expects the obj_base to carry intrusive bookkeeping (it
   reserves a counter and a cohort pointer there). An intrusive retire
   link in the same spirit is how Folly's hazptr_obj keeps retire() from
   allocating. The retire path shouldn't be able to fail, which comes
   down to where the retire-list storage lives.

3. Slot acquire/release cost - Every make_hazard_pointer() and every
   non-empty ~hazard_pointer() serializes on the one _M_slot_free_mutex;
   taking that lock is the real cost, and the scans under it (std::find
   over the free bitmap, std::find_if over the whole deque because the
   handle caches a raw slot pointer, not an index) stretch the critical
   section by O(pool) on top. The deque/std::find choices from the RFC
   round are fine locally. The performance the paper holds up (section
   3.1) is ~4ns construction/destruction, so this is perhaps worth
   reconsidering.

4. concurrent.cc can't detect the failure in (1) - It flags
   use-after-free only via p->value < 0, but the writers only ever
   publish positive counters, so a reused Node won't trip it. A
   poisoning/tagging scheme so (1) can actually fail a test on a
   weak-memory target rather than pass green would be good to have. I
   did run an end-to-end repro on POWER9 (trunk g++, ASan) against your
   header and didn't observe a failure, but that's inconclusive, not
   exculpatory: the model permits the outcome, so a clean run doesn't
   clear it.

Tom.