COMMON: Introduce Atomic Unique Ptr and Lock free primitives for reclaiming memory
An atomic unique ptr type is introduced, which can be used in situations where you'd expect a heavy read and rarely updated workload. On the writer side, you'd have to copy and reset the pointer to publish a new version of data. However in the reset call we don't delete the old ptr and actually return it back to the caller, this is because we don't know when it is a safe point to reclaim this memory as there could be ongoing reads. Since pointer loads and stores are atomic in x86_64, performance wise it is the same as using a plain unique ptr for all workloads.
Some common techniques to track this would be
- Hazard Pointers - where each thread announces what they are using in a globally shared list of hazard pointers
- RCU - A light weight synchronization technique kernel uses, Readers mark their critical section with rcu_read_lock/unlock. Uses a deferred deletion approach, when a writer updates a pointer, the old pointer is kept alive until all readers complete their critical section.
However tracking reader states isn't that easy, folly's RCU implementation for eg. uses a thread local counter per thread when a reader enters a critical section, and on the writer side all the reader counters are checked for non zero. Another approach is having a global hash table of per thread/epoch counters, however the hash table access would likely dominate the times here.
We use a simple reference counting where every reader doing lock basically increments a counter at an epoch. On the write side you just have to ensure that the previous epoch has no readers left before deleting the old ptr.
https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p2545r0.pdf