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

To date, existing quiescent-state-based safe memory reclamation algorithms have relied on a global epoch counter maintained through software timestamps. While most quiescent-state-based approaches demonstrate good performance when employed in lock-free concurrent data structures, they grapple with issues concerning robustness. Specifically, in interval-based reclamation (IBR), a thread reclaiming a shared memory block must compare whether the lifetime of the block intersects with all threads’ reserved epoch intervals. IBR can provide more fine-grained memory reclamation management than epoch-based reclamation and hazard era. Here, we introduce the use of a hardware timestamp, which is obtained from the CPU’s Time Stamp Counter (TSC) register, a clock with cycle-level resolution. We propose a variant of IBR, named TSC-IBR, which leverages TSC instead of the software timestamp used in IBR. The value of TSC can be swiftly accessed without necessitating a system call. In our experiments, compared to other quiescent-state-based methods using the software timestamp, TSC-IBR exhibits excellent robustness across all lock-free concurrent data structure benchmarks, while also attaining high throughput in the vast majority of them.