Leveraging Immutability to Validate Hazard Pointers for Optimistic Traversals
Open Access
- 10 June 2025
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 9 (PLDI) , 26-47
Abstract
Hazard pointers (HP) is one of the earliest manual memory reclamation algorithms for concurrent data structures. It is widely used for its robustness: memory overhead is bounded (e.g., by the number of threads). To access a node, threads first announce the protection of each to-be-accessed node, which prevents its reclamation. After announcement, they validate the node's reachability from the root to ensure that no threads have missed the announcement and reclaimed it. Traversal-based data structures typically takes a marking-based validation strategy. This strategy uses a node's mark to indicate whether the node is to be detached. Unmarked nodes are considered safe to traverse as both the node and its successors are still reachable, while marked nodes are considered unsafe. However, this strategy is inapplicable to the efficient optimistic traversal strategy that skips over marked nodes. We propose a new validation strategy for HP that supports lock-free data structures with optimistic traversal, such as lists, trees, and skip lists. The key idea is to exploit the immutability of marked nodes, and validate their reachability at once by checking the reachability of the most recent unmarked node. To ensure correctness, we prove the safety of Harris's list protected with the new strategy in Rocq using the Iris separation logic framework. We show that the new strategy's performance is competitive with state-of-the-art reclamation algorithms when applied to data structures with optimistic traversal, while remaining simple and robust.Keywords
Funding Information
- IITP (RS-2024-00459026, IITP-2025-RS-2023-00256472, IITP-2025-RS-2020-II201795)
This publication has 39 references indexed in Scilit:
- FEASTACM Transactions on Parallel Computing, 2020
- Universal wait-free memory reclamation2020
- Iris from the ground up: A modular foundation for higher-order concurrent separation logicJournal of Functional Programming, 2018
- Interactive proofs in higher-order concurrent separation logicACM SIGPLAN Notices, 2017
- Practical concurrent binary search trees via logical orderingACM SIGPLAN Notices, 2014
- A general technique for non-blocking treesACM SIGPLAN Notices, 2014
- User-Level Implementations of Read-Copy UpdateIEEE Transactions on Parallel and Distributed Systems, 2011
- Non-blocking binary search trees2010
- Hazard pointers: safe memory reclamation for lock-free objectsIEEE Transactions on Parallel and Distributed Systems, 2004
- Linearizability: a correctness condition for concurrent objectsACM Transactions on Programming Languages and Systems, 1990