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 
17 use std::sync::atomic::AtomicUsize;
18 use std::sync::atomic::Ordering::*;
19 
20 pub(crate) use self::list::{LocalNode, Node};
21 use super::RefCnt;
22 
23 mod fast;
24 mod helping;
25 mod list;
26 
27 /// One debt slot.
28 ///
29 /// It may contain an „owed“ reference count.
30 #[derive(Debug)]
31 pub(crate) struct Debt(pub(crate) AtomicUsize);
32 
33 impl 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 
42 impl Default for Debt {
default() -> Self43     fn default() -> Self {
44         Debt(AtomicUsize::new(Self::NONE))
45     }
46 }
47 
48 impl 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]
pay<T: RefCnt>(&self, ptr: *const T::Base) -> bool65     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.
pay_all<T, R>(ptr: *const T::Base, storage_addr: usize, replacement: R) where T: RefCnt, R: Fn() -> T,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(std::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)]
118 mod tests {
119     use std::sync::Arc;
120 
121     /// Checks the assumption that arcs to ZSTs have different pointer values.
122     #[test]
arc_zst()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 }
138