TSC-IBR: A Variant of Interval-Based Memory Reclamation Using CPU’s Time-Stamp Counter

Hardware timestamps are increasingly used in concurrent data structures. On the x86_64 platform, a clock with cycle-level resolution maintained by the CPU’s time-stamp counter register is frequently employed to implement parallel algorithms, and its value can be accessed swiftly without a system call. In line with this emerging trend, our research focuses on leveraging the CPU’s time-stamp counter in a memory management algorithm to secure safe memory reclamation in concurrent data structures. Existing quiescent-state-based memory reclamation algorithms rely on a global epoch counter maintained via a software timestamp. Although most quiescent-state-based methods demonstrate good performance when employed in lock-free concurrent data structures, they grapple with issues concerning robustness. Specifically, in Interval-Based Reclamation, a thread reclaiming a shared memory block must check whether the lifetime of the block intersects with the reserved epoch intervals of all threads. Interval-Based Reclamation can provide more fine-grained memory management than Epoch-Based Reclamation and hazard eras. In this study, we propose TSC-IBR, a variant of Interval-Based Reclamation. TSC-IBR leverages the CPU’s timestamp counter instead of the software timestamp. Our experiments confirmed the practicability of employing the CPU’s time-stamp counter in a memory reclamation algorithm. Compared to other quiescent-state-based methods using the software timestamp, TSC-IBR exhibits excellent robustness across all our lock-free concurrent data structure benchmarks and attains high throughput in most cases.