Fixing non-blocking data structures for better compatibility with memory reclamation schemes

Md Amit Hasan Arovi, Ruslan Nikolaev · 2025

Read Fixing non-blocking data structures for better compatibility with memory reclamation schemes by Md Amit Hasan Arovi, Ruslan Nikolaev (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-06254.txt.

Introduction

Arovi and Ruslan Nikolaev fix a clash between fast data structures and safe memory reuse in this two thousand twenty-five paper. Non-blocking structures let many threads work without locks. Freed memory must wait until no thread still reads it. Robust protection schemes guard against stalled threads but clash with optimistic search styles used by famous lists and trees. Older fixes slowed those structures down.

Their technique, SCOT, adapts the structures while leaving the protection schemes untouched. Speed of the originals is kept. They show it on a classic list and a search tree, noting wider use. A small change adds wait-free search on top. Systems programmers building shared data structures are the readers.

Catalog record

CREATORMd Amit Hasan Arovi, Ruslan Nikolaev
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE56 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-06254

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fixing non-blocking data structures for better compatibility with memory reclamation schemes Md Amit Hasan Arovi, Ruslan Nikolaev Abstract We present a new technique, Safe Concurrent Optimistic Traversals (SCOT), to address a well-known problem related to optimistic traversals with both classical and more recent memory reclamation schemes, such as Hazard Pointers (HP), Hazard Eras (HE), Interval-Based Reclamation (IBR), and Hyaline. Unlike Epoch-Based Reclamation (EBR), these schemes guarantee protection against stalled threads (robustness) but lack support for well-known data structures with optimistic traversals such as Harris’ original list, Natarajan-Mittal tree, among others. For these reclamation schemes, existing data structure implementations are either buggy (e.g., Natarajan-Mittal tree) or come with performance trade-offs (e.g., Harris-Michael modified list). A recent work, HP++, supports optimistic traversals but uses a different API and is generally slower than even HP, not to mention more recent schemes such as IBR or Hyaline. Moreover, it has undesirable applicability trade-offs, and more complex implementation, among other issues. We propose a different method which keeps existing reclamation schemes intact but instead relies on data structure adaptations. Unlike existing Harris-Michael approach or HP++, our method retains performance benefits of the original data structure and also does not compromise performance of the underlying reclamation scheme. In fact, for IBR and Hyaline, our results almost match those of EBR, which often serves as a practical upper bound due to its great performance. We implement and evaluate two fundamentally different data structures: Harris’ list and Natarajan-Mittal tree. SCOT enables their first correct implementations with optimistic traversals for HP, HE, IBR, and Hyaline. Our method is also directly applicable to other data structures, e.g., Fraser’s skip list or hash map that uses Harris’ list internally. We observe similar performance speedups (e.g., Harris vs. Harris-Michael list) that were previously available only to EBR users. As we discuss in the paper, our version of Natarajan-Mittal tree is the first bug-free implementation for HP, HE, IBR, and Hyaline; it achieves very high throughput, comparable to that of EBR. Keywords : hazard pointers, non-blocking, Harris’ list, Natarajan-Mittal tree 1 Introduction With the growing prevalence of multicore and manycore systems, parallelization is becoming crucial for enhancing performance across the entire software stack – applications, middleware, core system services, and low-level components inside an operating system (OS). Non-blocking data structures, which are not dependent on mutual exclusion, are becoming increasingly popular due to their scalability, throughput, and latency characteristics. Unfortunately, many data structures that utilize non-blocking techniques conflict with fundamental assumptions of classical memory management. This is because memory cannot be promptly reclaimed after an object is removed from a data structure, as there may still exist stale pointers to the object due to ongoing operations. When using manual memory management, memory has to be safely reclaimed by freeing memory only when all ongoing operations with stale pointers complete. A number of past researchers proposed various safe memory reclamation (SMR) techniques in C, C++, or Rust. Non-blocking SMR progress is often crucial for the overall progress guarantees, as we do not want to compromise data structure progress properties. Unfortunately, many SMR schemes are trying to attain several highly desirable properties simultaneously while often unknowingly compromising non-blocking progress or other important properties one way or the other. A recent work [ 22 ] sheds more light onto this conundrum: it proves that it is impossible to achieve three highly desirable SMR properties simultaneously, i.e., only two properties can ever be achieved: (A) robustness (bounded memory usage), (B) easy integration (no dependency on any special APIs, such as roll-back mechanisms or OS-based primitives), and (C) wide applicability (compatibility with most non-blocking data structures). While striving to have (A) for non-blocking progress, 1 1 1 If memory usage is unbounded, no further system progress can be made once memory is exhausted, regardless of whether actual locks are present. past researchers would compromise either (B), (C), or other properties that are tangentially related to non-blocking progress, sometimes without fully realizing that. To make matters worse, many researchers prioritize (C) because, intuitively, their goal is to support as many data structures as possible. However, we argue that sacrificing (C) rather than (B) by carefully adapting existing problematic data structures is a “necessary evil”, which is a crucial new insight . First, (C) in its strongest form – applying to all data structures – only currently known to exist in blocking SMR schemes [ 22 ] , which is a non-starter for us. Second, even if we accept (C) in its relaxed form – applying to most data structures – the absence of (B) would lead to either inability to achieve non-blocking progress in practice due to dependence on OS-based primitives, lack of universally-defined APIs, or both. (We discuss some specific examples in Section 6 .) Third, the absence of (C) simply implies that adaptations are required, not impossibility of the implementation. EBR [ 9 ] is a fast and easy-to-use approach but has a serious drawback that any stalled thread results in unbounded memory usage, i.e., it lacks (A). Once exhausting memory, the system must either reboot or block until memory is freed. Many researchers prefer EBR’s simplicity but attempt to solve its robustness issue. Unfortunately, such approaches typically sacrifice strict non-blocking progress [ 5 , 23 , 4 , 1 , 2 ] , as discussed in Section 6 , or need non-trivial roll-back mechanisms [ 21 ] , which are fairly hard to generalize in terms of the API within the same library framework. HP [ 14 ] is an antipode of EBR: it is somewhat slower and more difficult to use but provides robustness with strict non-blocking guarantees by placing a hard limit on the number of local pointers within each thread. Prior to this work, well-known data structures such as Harris’ linked list [ 10 ] with optimistic traversals 2 2 2 The original paper [ 10 ] did not explicitly mention that search can be done in a read-only manner (w/o any CAS operations). In this paper, by Harris’ list, we denote the enhanced version [ 11 ] with optimistic read-only traversals. and Natarajan-Mittal’s binary search tree (BST) [ 16 ] were not known to work 3 3 3 Despite presenting Natarajan-Mittal Tree results in [ 26 , 18 ] for HP and other SMR schemes, it was later argued [ 3 ] that such implementations are buggy and leak memory. Moreover, [ 3 ] pointed out two bugs, and only one bug was resolved in [ 3 ] . Prior to our work, the second bug related to optimistic traversals remained unresolved. with HP [ 12 , 3 ] , which is due to HP’s lack of the wide-applicability (C) property. A number of other recent schemes, including Interval Based Reclamation (IBR) [ 26 ] , Hyaline-1S [ 18 ] , and Hazard Eras (HE) [ 20 ] , sometimes offer better performance but have similar issues to HP. HP++ [ 12 ] is another recent scheme. HP++ is slower than HP and, strictly speaking, makes compromises with both (B) and (C). However, HP++ still demonstrates support for these two data structures. We are inspired by HP++’s success with these data structures, which is indicative that many existing data structures can still

Read the complete text