1 //! The fast slots for the primary strategy. 2 //! 3 //! They are faster, but fallible (in case the slots run out or if there's a collision with a 4 //! writer thread, this gives up and falls back to secondary strategy). 5 //! 6 //! They are based on hazard pointer ideas. To acquire one, the pointer is loaded, stored in the 7 //! slot and the debt is confirmed by loading it again and checking it is the same. 8 //! 9 //! # Orderings 10 //! 11 //! We ensure just one thing here. Since we do both the acquisition of the slot and the exchange of 12 //! the pointer in the writer with SeqCst, we are guaranteed to either see the change in case it 13 //! hits somewhere in between the two reads of the pointer, or to have successfully acquired it 14 //! before the change and before any cleanup of the old pointer happened (in which case we know the 15 //! writer will see our debt). 16 17 use std::cell::Cell; 18 use std::slice::Iter; 19 use std::sync::atomic::Ordering::*; 20 21 use super::Debt; 22 23 const DEBT_SLOT_CNT: usize = 8; 24 25 /// Thread-local information for the [`Slots`] 26 #[derive(Default)] 27 pub(super) struct Local { 28 // The next slot in round-robin rotation. Heuristically tries to balance the load across them 29 // instead of having all of them stuffed towards the start of the array which gets 30 // unsuccessfully iterated through every time. 31 offset: Cell<usize>, 32 } 33 34 /// Bunch of fast debt slots. 35 #[derive(Default)] 36 pub(super) struct Slots([Debt; DEBT_SLOT_CNT]); 37 38 impl Slots { 39 /// Try to allocate one slot and get the pointer in it. 40 /// 41 /// Fails if there are no free slots. 42 #[inline] get_debt(&self, ptr: usize, local: &Local) -> Option<&Debt>43 pub(super) fn get_debt(&self, ptr: usize, local: &Local) -> Option<&Debt> { 44 // Trick with offsets: we rotate through the slots (save the value from last time) 45 // so successive leases are likely to succeed on the first attempt (or soon after) 46 // instead of going through the list of already held ones. 47 let offset = local.offset.get(); 48 let len = self.0.len(); 49 for i in 0..len { 50 let i = (i + offset) % len; 51 // Note: the indexing check is almost certainly optimised out because the len 52 // is used above. And using .get_unchecked was actually *slower*. 53 let slot = &self.0[i]; 54 if slot.0.load(Relaxed) == Debt::NONE { 55 // We are allowed to split into the check and acquiring the debt. That's because we 56 // are the only ones allowed to change NONE to something else. But we still need a 57 // read-write operation wit SeqCst on it :-( 58 let old = slot.0.swap(ptr, SeqCst); 59 debug_assert_eq!(Debt::NONE, old); 60 local.offset.set(i + 1); 61 return Some(&self.0[i]); 62 } 63 } 64 None 65 } 66 } 67 68 impl<'a> IntoIterator for &'a Slots { 69 type Item = &'a Debt; 70 71 type IntoIter = Iter<'a, Debt>; 72 into_iter(self) -> Self::IntoIter73 fn into_iter(self) -> Self::IntoIter { 74 self.0.iter() 75 } 76 } 77