1 //! A lock-free concurrent slab. 2 3 mod addr; 4 pub(crate) use addr::Address; 5 6 mod entry; 7 pub(crate) use entry::Entry; 8 9 mod generation; 10 pub(crate) use generation::Generation; 11 12 mod page; 13 14 mod shard; 15 use shard::Shard; 16 17 mod slot; 18 use slot::Slot; 19 20 mod stack; 21 use stack::TransferStack; 22 23 #[cfg(all(loom, test))] 24 mod tests; 25 26 use crate::loom::sync::Mutex; 27 use crate::util::bit; 28 29 use std::fmt; 30 31 #[cfg(target_pointer_width = "64")] 32 const MAX_THREADS: usize = 4096; 33 34 #[cfg(target_pointer_width = "32")] 35 const MAX_THREADS: usize = 2048; 36 37 /// Max number of pages per slab 38 const MAX_PAGES: usize = bit::pointer_width() as usize / 4; 39 40 cfg_not_loom! { 41 /// Size of first page 42 const INITIAL_PAGE_SIZE: usize = 32; 43 } 44 45 cfg_loom! { 46 const INITIAL_PAGE_SIZE: usize = 2; 47 } 48 49 /// A sharded slab. 50 pub(crate) struct Slab<T> { 51 // Signal shard for now. Eventually there will be more. 52 shard: Shard<T>, 53 local: Mutex<()>, 54 } 55 56 unsafe impl<T: Send> Send for Slab<T> {} 57 unsafe impl<T: Sync> Sync for Slab<T> {} 58 59 impl<T: Entry> Slab<T> { 60 /// Returns a new slab with the default configuration parameters. new() -> Slab<T>61 pub(crate) fn new() -> Slab<T> { 62 Slab { 63 shard: Shard::new(), 64 local: Mutex::new(()), 65 } 66 } 67 68 /// allocs a value into the slab, returning a key that can be used to 69 /// access it. 70 /// 71 /// If this function returns `None`, then the shard for the current thread 72 /// is full and no items can be added until some are removed, or the maximum 73 /// number of shards has been reached. alloc(&self) -> Option<Address>74 pub(crate) fn alloc(&self) -> Option<Address> { 75 // we must lock the slab to alloc an item. 76 let _local = self.local.lock().unwrap(); 77 self.shard.alloc() 78 } 79 80 /// Removes the value associated with the given key from the slab. remove(&self, idx: Address)81 pub(crate) fn remove(&self, idx: Address) { 82 // try to lock the slab so that we can use `remove_local`. 83 let lock = self.local.try_lock(); 84 85 // if we were able to lock the slab, we are "local" and can use the fast 86 // path; otherwise, we will use `remove_remote`. 87 if lock.is_ok() { 88 self.shard.remove_local(idx) 89 } else { 90 self.shard.remove_remote(idx) 91 } 92 } 93 94 /// Return a reference to the value associated with the given key. 95 /// 96 /// If the slab does not contain a value for the given key, `None` is 97 /// returned instead. get(&self, token: Address) -> Option<&T>98 pub(crate) fn get(&self, token: Address) -> Option<&T> { 99 self.shard.get(token) 100 } 101 } 102 103 impl<T> fmt::Debug for Slab<T> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result104 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 105 f.debug_struct("Slab").field("shard", &self.shard).finish() 106 } 107 } 108