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