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            // On failure, we have observed that the debt has been paid, but we need to establish a
68            // happens-before relationship with that debt being paid before we do anything that
69            // relies on the Arc's strong counter being incremented, so we need to Acquire.
70            // Arc does not sufficiently take care of this, as the memory model permits its Drop's
71            // `fetch_sub` to observe itself to be last remaining instance before the `fetch_add`s
72            // from the debt being repaid, and only after that observation does Arc have an Acquire
73            // fence.
74            //
75            // Unfortunately, we need SeqCst on the success
76            .compare_exchange(ptr as usize, Self::NONE, SeqCst, SeqCst)
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
