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