Skip to main content

store_io_buf/
stack.rs

1//! A bounded, lock-free stack of `u32` indices: the free list of each buffer
2//! size class, most recently freed first.
3//!
4//! Why last in, first out: a buffer just returned is still warm in the CPU's
5//! caches, so the next operation copies from or into memory that is already
6//! there. A first-in-first-out free list rotates through every buffer of a
7//! class instead; 1 MiB appends kept 8 deep measured 7-10% less bandwidth
8//! that way at memory speed (a 64-buffer rotation against a 9-buffer one, on
9//! CI).
10//!
11//! Treiber's stack over an index array. `head` packs a 40-bit tag
12//! (incremented on every successful change) with `top + 1` in the low 24
13//! bits (0: empty), and `next[i]` holds the entry below index `i`, plus one.
14//! The tag makes a compare-and-swap fail whenever the head changed in
15//! between, even back to the same index (ABA): a popper that read
16//! `next[top]` before another thread popped `top`, popped the entry below it
17//! and pushed `top` back cannot then install the stale `next` and hand out
18//! an index that is no longer free. Only a popper stalled between its read
19//! and its exchange for exactly a multiple of 2^40 changes (about six hours
20//! at 20 ns a change, with the same index on top) could be fooled. Every
21//! index is pushed at most once while free (the pool's ownership rule), so
22//! the stack never holds more than its capacity. No `unsafe`, no allocation
23//! after creation.
24
25use crate::pad::CachePadded;
26use crate::sync::{AtomicU32, AtomicU64, Ordering, spin};
27
28/// Low bits of the head word holding `top + 1`; the tag has the rest.
29const TOP_BITS: u32 = 24;
30const TOP_MASK: u64 = (1 << TOP_BITS) - 1;
31
32/// Bounded LIFO stack of `u32` values below its capacity.
33pub struct IndexStack {
34    head: CachePadded<AtomicU64>,
35    next: Box<[AtomicU32]>,
36}
37
38/// The head word for `tag` (its low 40 bits) and `top_plus_one`.
39#[inline]
40fn pack(tag: u64, top_plus_one: u32) -> u64 {
41    (tag << TOP_BITS) | u64::from(top_plus_one)
42}
43
44#[inline]
45#[allow(clippy::cast_possible_truncation)]
46fn unpack(word: u64) -> (u64, u32) {
47    (word >> TOP_BITS, (word & TOP_MASK) as u32)
48}
49
50impl IndexStack {
51    /// The largest capacity (2^24 - 1 values).
52    pub const MAX_CAPACITY: u32 = (1 << TOP_BITS) - 1;
53
54    /// An empty stack for the values `0..capacity`; a capacity above
55    /// [`Self::MAX_CAPACITY`] is reduced to it.
56    #[must_use]
57    pub fn with_capacity(capacity: u32) -> Self {
58        let capacity = capacity.min(Self::MAX_CAPACITY);
59        Self {
60            head: CachePadded::new(AtomicU64::new(0)),
61            next: (0..capacity).map(|_| AtomicU32::new(0)).collect(),
62        }
63    }
64
65    /// The number of values the stack can hold (every value is below it).
66    #[must_use]
67    pub fn capacity(&self) -> usize {
68        self.next.len()
69    }
70
71    /// Pushes `value`; returns it back if it is not below the capacity.
72    /// Never blocks. `value` must not already be on the stack: pushing it
73    /// twice corrupts the stack (a cycle that pops repeat, and the entries
74    /// below it lost). The pool pushes an index once, when its buffer is
75    /// dropped.
76    pub fn push(&self, value: u32) -> Result<(), u32> {
77        let Some(slot) = self.next.get(value as usize) else {
78            return Err(value);
79        };
80        let mut head = self.head.load(Ordering::Acquire);
81        loop {
82            let (tag, top) = unpack(head);
83            // Published by the release below, before the value is visible.
84            slot.store(top, Ordering::Relaxed);
85            match self.head.compare_exchange_weak(
86                head,
87                pack(tag.wrapping_add(1), value + 1),
88                Ordering::Release,
89                Ordering::Acquire,
90            ) {
91                Ok(_) => return Ok(()),
92                Err(current) => {
93                    head = current;
94                    spin();
95                }
96            }
97        }
98    }
99
100    /// Pops the most recently pushed value, or `None` if the stack is empty.
101    /// Never blocks.
102    pub fn pop(&self) -> Option<u32> {
103        let mut head = self.head.load(Ordering::Acquire);
104        loop {
105            let (tag, top) = unpack(head);
106            let index = top.checked_sub(1)?;
107            // `top`'s entry below it, as its pusher wrote it before the
108            // release this acquire saw. If `top` was popped and pushed back
109            // since, the tag has moved and the exchange below fails.
110            let below = self.next[index as usize].load(Ordering::Relaxed);
111            match self.head.compare_exchange_weak(
112                head,
113                pack(tag.wrapping_add(1), below),
114                Ordering::Acquire,
115                Ordering::Acquire,
116            ) {
117                Ok(_) => return Some(index),
118                Err(current) => {
119                    head = current;
120                    spin();
121                }
122            }
123        }
124    }
125}
126
127#[cfg(all(test, not(loom)))]
128mod tests {
129    #![allow(clippy::unwrap_used)]
130
131    use std::sync::Arc;
132
133    use super::*;
134
135    #[test]
136    fn test_stack_is_lifo_and_empty_and_bounded() {
137        let s = IndexStack::with_capacity(4);
138        assert_eq!(s.capacity(), 4);
139        assert_eq!(s.pop(), None);
140        for i in 0..4 {
141            assert_eq!(s.push(i), Ok(()));
142        }
143        assert_eq!(s.push(4), Err(4), "a value outside the capacity");
144        for i in (0..4).rev() {
145            assert_eq!(s.pop(), Some(i));
146        }
147        assert_eq!(s.pop(), None);
148        // The most recently returned value comes back first.
149        s.push(2).unwrap();
150        s.push(0).unwrap();
151        assert_eq!(s.pop(), Some(0));
152        s.push(3).unwrap();
153        assert_eq!(s.pop(), Some(3));
154        assert_eq!(s.pop(), Some(2));
155        assert_eq!(s.pop(), None);
156    }
157
158    /// The largest value keeps its own index in the head word's low bits,
159    /// the tag never spills into them, and a tag past 40 bits wraps to 0.
160    #[test]
161    fn test_stack_head_word_packing() {
162        let top = IndexStack::MAX_CAPACITY - 1;
163        let tag = u64::MAX >> TOP_BITS;
164        assert_eq!(unpack(pack(tag, top + 1)), (tag, top + 1));
165        assert_eq!(unpack(pack(3, 0)), (3, 0));
166        assert_eq!(unpack(pack(tag.wrapping_add(1), 5)), (0, 5));
167    }
168
169    /// The largest capacity holds its largest value (16 million slots: too
170    /// large for Miri).
171    #[test]
172    #[cfg_attr(miri, ignore)]
173    fn test_stack_largest_capacity_holds_its_largest_value() {
174        let top = IndexStack::MAX_CAPACITY - 1;
175        let s = IndexStack::with_capacity(u32::MAX);
176        assert_eq!(s.capacity(), IndexStack::MAX_CAPACITY as usize);
177        assert_eq!(s.push(top + 1), Err(top + 1));
178        for _ in 0..3 {
179            s.push(top).unwrap();
180            s.push(0).unwrap();
181            assert_eq!(s.pop(), Some(0));
182            assert_eq!(s.pop(), Some(top));
183            assert_eq!(s.pop(), None);
184        }
185    }
186
187    /// Many threads taking and returning values: every value is held by at
188    /// most one thread at a time, and none is lost.
189    #[test]
190    fn test_stack_concurrent_values_are_never_shared_or_lost() {
191        const N: u32 = 64;
192        let s = Arc::new(IndexStack::with_capacity(N));
193        for i in 0..N {
194            s.push(i).unwrap();
195        }
196        let held: Arc<Vec<AtomicU32>> = Arc::new((0..N).map(|_| AtomicU32::new(0)).collect());
197        let threads: Vec<_> = (0..8)
198            .map(|_| {
199                let (s, held) = (Arc::clone(&s), Arc::clone(&held));
200                std::thread::spawn(move || {
201                    for _ in 0..if cfg!(miri) { 50 } else { 20_000 } {
202                        if let Some(v) = s.pop() {
203                            let was = held[v as usize].fetch_add(1, Ordering::AcqRel);
204                            assert_eq!(was, 0, "value {v} handed out twice");
205                            let _released = held[v as usize].fetch_sub(1, Ordering::AcqRel);
206                            s.push(v).unwrap();
207                        }
208                    }
209                })
210            })
211            .collect();
212        for t in threads {
213            t.join().unwrap();
214        }
215        let mut all: Vec<u32> = std::iter::from_fn(|| s.pop()).collect();
216        all.sort_unstable();
217        assert_eq!(
218            all,
219            (0..N).collect::<Vec<_>>(),
220            "a value was lost or duplicated"
221        );
222    }
223}
224
225#[cfg(all(test, loom))]
226mod loom_tests {
227    use loom::sync::Arc;
228
229    use super::*;
230
231    /// The ABA case: one thread pops while another pops two values and
232    /// pushes the first back. No value may be held by both threads, or be
233    /// held and still on the stack, and none may be lost.
234    #[test]
235    fn loom_a_stale_pop_never_hands_out_a_held_value() {
236        loom::model(|| {
237            let s = Arc::new(IndexStack::with_capacity(3));
238            for i in 0..3 {
239                s.push(i).unwrap();
240            }
241            let a = {
242                let s = Arc::clone(&s);
243                loom::thread::spawn(move || s.pop())
244            };
245            let b = {
246                let s = Arc::clone(&s);
247                loom::thread::spawn(move || {
248                    let x = s.pop();
249                    let y = s.pop();
250                    if let Some(x) = x {
251                        s.push(x).unwrap();
252                    }
253                    y
254                })
255            };
256            let got_a = a.join().unwrap();
257            let held_b = b.join().unwrap();
258            if let (Some(va), Some(vb)) = (got_a, held_b) {
259                assert_ne!(va, vb, "a value held by one thread was handed to another");
260            }
261            // Conservation: the stack holds exactly the values nobody holds.
262            let mut rest: Vec<u32> = std::iter::from_fn(|| s.pop()).collect();
263            for held in [got_a, held_b].into_iter().flatten() {
264                assert!(!rest.contains(&held), "a held value is still on the stack");
265            }
266            rest.extend(got_a);
267            rest.extend(held_b);
268            rest.sort_unstable();
269            assert_eq!(rest, vec![0, 1, 2]);
270        });
271    }
272}