arc_swap/debt/
mod.rs

1//! Debt handling.
2//!
3//! A debt is a reference count of a smart pointer that is owed. This module provides a lock-free
4//! storage for debts.
5//!
6//! Each thread has its own node with bunch of slots. Only that thread can allocate debts in there,
7//! but others are allowed to inspect and pay them. The nodes form a linked list for the reason of
8//! inspection. The nodes are never removed (even after the thread terminates), but if the thread
9//! gives it up, another (new) thread can claim it.
10//!
11//! The writers walk the whole chain and pay the debts (by bumping the ref counts) of the just
12//! removed pointer.
13//!
14//! Each node has some fast (but fallible) nodes and a fallback node, with different algorithms to
15//! claim them (see the relevant submodules).
16
17use core::sync::atomic::AtomicUsize;
18use core::sync::atomic::Ordering::*;
19
20pub(crate) use self::list::{LocalNode, Node};
21use super::RefCnt;
22
23mod fast;
24mod helping;
25mod list;
26
27/// One debt slot.
28///
29/// It may contain an „owed“ reference count.
30#[derive(Debug)]
31pub(crate) struct Debt(pub(crate) AtomicUsize);
32
33impl Debt {
34    /// The value of pointer `3` should be pretty safe, for two reasons:
35    ///
36    /// * It's an odd number, but the pointers we have are likely aligned at least to the word size,
37    ///   because the data at the end of the `Arc` has the counters.
38    /// * It's in the very first page where NULL lives, so it's not mapped.
39    pub(crate) const NONE: usize = 0b11;
40}
41
42impl Default for Debt {
43    fn default() -> Self {
44        Debt(AtomicUsize::new(Self::NONE))
45    }
46}
47
48impl Debt {
49    /// Tries to pay the given debt.
50    ///
51    /// If the debt is still there, for the given pointer, it is paid and `true` is returned. If it
52    /// is empty or if there's some other pointer, it is not paid and `false` is returned, meaning
53    /// the debt was paid previously by someone else.
54    ///
55    /// # Notes
56    ///
57    /// * It is possible that someone paid the debt and then someone else put a debt for the same
58    ///   pointer in there. This is fine, as we'll just pay the debt for that someone else.
59    /// * This relies on the fact that the same pointer must point to the same object and
60    ///   specifically to the same type ‒ the caller provides the type, it's destructor, etc.
61    /// * It also relies on the fact the same thing is not stuffed both inside an `Arc` and `Rc` or
62    ///   something like that, but that sounds like a reasonable assumption. Someone storing it
63    ///   through `ArcSwap<T>` and someone else with `ArcSwapOption<T>` will work.
64    #[inline]
65    pub(crate) fn pay<T: RefCnt>(&self, ptr: *const T::Base) -> bool {
66        self.0
67            // If we don't change anything because there's something else, Relaxed is fine.
68            //
69            // The Release works as kind of Mutex. We make sure nothing from the debt-protected
70            // sections leaks below this point.
71            //
72            // Note that if it got paid already, it is inside the reference count. We don't
73            // necessarily observe that increment, but whoever destroys the pointer *must* see the
74            // up to date value, with all increments already counted in (the Arc takes care of that
75            // part).
76            .compare_exchange(ptr as usize, Self::NONE, Release, Relaxed)
77            .is_ok()
78    }
79
80    /// Pays all the debts on the given pointer and the storage.
81    pub(crate) fn pay_all<T, R>(ptr: *const T::Base, storage_addr: usize, replacement: R)
82    where
83        T: RefCnt,
84        R: Fn() -> T,
85    {
86        LocalNode::with(|local| {
87            let val = unsafe { T::from_ptr(ptr) };
88            // Pre-pay one ref count that can be safely put into a debt slot to pay it.
89            T::inc(&val);
90
91            Node::traverse::<(), _>(|node| {
92                // Make the cooldown trick know we are poking into this node.
93                let _reservation = node.reserve_writer();
94
95                local.help(node, storage_addr, &replacement);
96
97                let all_slots = node
98                    .fast_slots()
99                    .chain(core::iter::once(node.helping_slot()));
100                for slot in all_slots {
101                    // Note: Release is enough even here. That makes sure the increment is
102                    // visible to whoever might acquire on this slot and can't leak below this.
103                    // And we are the ones doing decrements anyway.
104                    if slot.pay::<T>(ptr) {
105                        // Pre-pay one more, for another future slot
106                        T::inc(&val);
107                    }
108                }
109
110                None
111            });
112            // Implicit dec by dropping val in here, pair for the above
113        })
114    }
115}
116
117#[cfg(test)]
118mod tests {
119    use alloc::sync::Arc;
120
121    /// Checks the assumption that arcs to ZSTs have different pointer values.
122    #[test]
123    fn arc_zst() {
124        struct A;
125        struct B;
126
127        let a = Arc::new(A);
128        let b = Arc::new(B);
129
130        let aref: &A = &a;
131        let bref: &B = &b;
132
133        let aptr = aref as *const _ as usize;
134        let bptr = bref as *const _ as usize;
135        assert_ne!(aptr, bptr);
136    }
137}
arc_swap/debt/mod.rs

arc_swap/debt/
mod.rs
