Lock-Free C++ in Production
Mastering the Memory Model with Hazard Pointers and Epoch-Based Reclamation
Weston Ashgrove
IntroductionPart I: The Foundations
Chapter 1: Why lock-free, and when not to- 1.1 What locks really cost: contention, convoying, and priority inversion
- 1.2 Progress guarantees: obstruction-free, lock-free, and wait-free
- 1.3 When lock-free is the wrong answer
- 1.4 Reference workloads and the concurrency test harness
- 2.1 Cache coherence: MESI, MOESI, and the cost of sharing a line
- 2.2 Store buffers, invalidation queues, and why reordering happens
- 2.3 x86 total store order vs. ARM weak ordering
- 2.4 The cost of atomic read-modify-write: LOCK prefixes and LL/SC
Part II: The Memory Model
Chapter 3: The C++ memory model, precisely- 3.1 Happens-before, synchronizes-with, and modification order
- 3.2 Data races and why they are undefined behavior
- 3.3
std::atomic,std::atomic_ref, andis_always_lock_free - 3.4 Coherence rules and what they guarantee even under relaxed ordering
- 4.1 Relaxed ordering: counters, statistics, and its real limits
- 4.2 Acquire and release: safe publication patterns
- 4.3 Sequential consistency: store-load ordering and when you truly need it
- 4.4 Fences, signal fences, and why
memory_order_consumefailed
- 5.1 Compare-and-swap loops: weak vs. strong and spurious failure
- 5.2 The ABA problem and tagged pointers
- 5.3 Double-width CAS and 128-bit atomics
- 5.4 Waiting without spinning:
atomic::wait,notify, and futexes
Part III: Lock-Free Data Structures
Chapter 6: Queues- 6.1 Single-producer single-consumer ring buffers
- 6.2 Multi-producer single-consumer queues
- 6.3 Bounded multi-producer multi-consumer queues
- 6.4 Unbounded queues: the Michael-Scott algorithm
- 6.5 The Chase-Lev work-stealing deque
- 7.1 The Treiber stack and elimination backoff
- 7.2 Lock-free linked lists with logical deletion
- 7.3 Lock-free hash maps and split-ordered lists
- 7.4 Lock-free skip lists
- 7.5 Wait-free techniques: helping and fast-path/slow-path
- 8.1 Seqlocks for read-mostly data
- 8.2 Read-copy-update patterns in user space
- 8.3
std::atomic<std::shared_ptr>and its hidden costs - 8.4 Spinlocks done right: TTAS, exponential backoff, and MCS locks
Part IV: Memory Reclamation
Chapter 9: The reclamation problem- 9.1 Why
deletebreaks lock-free code - 9.2 Reference counting and its limits under contention
- 9.3 Split reference counts
- 9.4 A taxonomy of reclamation schemes
- 10.1 The hazard pointer algorithm
- 10.2 Building a hazard pointer domain in C++
- 10.3 Retire lists, scanning, and amortized reclamation
- 10.4
std::hazard_pointerin C++26
- 11.1 The epoch algorithm
- 11.2 Building an epoch-based reclaimer in C++
- 11.3 The stalled-thread problem and bounding memory growth
- 11.4 Quiescent-state reclamation and
std::rcuin C++26
- 12.1 Hybrid schemes: hazard eras and interval-based reclamation
- 12.2 Comparing schemes by throughput, latency, and memory footprint
- 12.3 Integrating reclamation with custom allocators
- 12.4 Choosing a scheme for your workload
Part V: Correctness and Performance
Chapter 13: Proving it works- 13.1 ThreadSanitizer and its blind spots
- 13.2 Stress testing and randomized scheduling
- 13.3 Model checking with Relacy, CDSChecker, and GenMC
- 13.4 Linearizability checking
- 14.1 False sharing and
hardware_destructive_interference_size - 14.2 Contention management and backoff strategies
- 14.3 Scalability benchmarking across core counts
- 14.4 NUMA effects on lock-free structures
Part VI: Production
Chapter 15: Lock-free code in production- 15.1 Designing APIs around lock-free structures
- 15.2 Debugging lock-free failures with core dumps and
rr - 15.3 Portability between x86 and ARM
- 15.4 The lock-free decision guide
Appendices
- Appendix A: Memory ordering reference tables
- Appendix B: Atomic instruction mapping for x86 and ARM
- Appendix C: Reclamation scheme comparison
- Appendix D: Lock-free code review checklist
- Appendix E: Production libraries