1use crate::page::{
2 slot::{Generation, RefCount},
3 Addr,
4};
5use crate::Pack;
6use std::{fmt, marker::PhantomData};
7/// Configuration parameters which can be overridden to tune the behavior of a slab.
8pub trait Config: Sized {
9 /// The maximum number of threads which can access the slab.
10 ///
11 /// This value (rounded to a power of two) determines the number of shards
12 /// in the slab. If a thread is created, accesses the slab, and then terminates,
13 /// its shard may be reused and thus does not count against the maximum
14 /// number of threads once the thread has terminated.
15 const MAX_THREADS: usize = DefaultConfig::MAX_THREADS;
16 /// The maximum number of pages in each shard in the slab.
17 ///
18 /// This value, in combination with `INITIAL_PAGE_SIZE`, determines how many
19 /// bits of each index are used to represent page addresses.
20 const MAX_PAGES: usize = DefaultConfig::MAX_PAGES;
21 /// The size of the first page in each shard.
22 ///
23 /// When a page in a shard has been filled with values, a new page
24 /// will be allocated that is twice as large as the previous page. Thus, the
25 /// second page will be twice this size, and the third will be four times
26 /// this size, and so on.
27 ///
28 /// Note that page sizes must be powers of two. If this value is not a power
29 /// of two, it will be rounded to the next power of two.
30 const INITIAL_PAGE_SIZE: usize = DefaultConfig::INITIAL_PAGE_SIZE;
31 /// Sets a number of high-order bits in each index which are reserved from
32 /// user code.
33 ///
34 /// Note that these bits are taken from the generation counter; if the page
35 /// address and thread IDs are configured to use a large number of bits,
36 /// reserving additional bits will decrease the period of the generation
37 /// counter. These should thus be used relatively sparingly, to ensure that
38 /// generation counters are able to effectively prevent the ABA problem.
39 const RESERVED_BITS: usize = 0;
40}
41
42pub(crate) trait CfgPrivate: Config {
43 const USED_BITS: usize = Generation::<Self>::LEN + Generation::<Self>::SHIFT;
44 const INITIAL_SZ: usize = next_pow2(Self::INITIAL_PAGE_SIZE);
45 const MAX_SHARDS: usize = next_pow2(Self::MAX_THREADS - 1);
46 const ADDR_INDEX_SHIFT: usize = Self::INITIAL_SZ.trailing_zeros() as usize + 1;
47
48 fn page_size(n: usize) -> usize {
49 Self::INITIAL_SZ * 2usize.pow(n as _)
50 }
51
52 fn debug() -> DebugConfig<Self> {
53 DebugConfig { _cfg: PhantomData }
54 }
55
56 fn validate() {
57 assert!(
58 Self::INITIAL_SZ.is_power_of_two(),
59 "invalid Config: {:#?}",
60 Self::debug(),
61 );
62 assert!(
63 Self::INITIAL_SZ <= Addr::<Self>::BITS,
64 "invalid Config: {:#?}",
65 Self::debug()
66 );
67
68 assert!(
69 Generation::<Self>::BITS >= 3,
70 "invalid Config: {:#?}\ngeneration counter should be at least 3 bits!",
71 Self::debug()
72 );
73
74 assert!(
75 Self::USED_BITS <= WIDTH,
76 "invalid Config: {:#?}\ntotal number of bits per index is too large to fit in a word!",
77 Self::debug()
78 );
79
80 assert!(
81 WIDTH - Self::USED_BITS >= Self::RESERVED_BITS,
82 "invalid Config: {:#?}\nindices are too large to fit reserved bits!",
83 Self::debug()
84 );
85
86 assert!(
87 RefCount::<Self>::MAX > 1,
88 "invalid config: {:#?}\n maximum concurrent references would be {}",
89 Self::debug(),
90 RefCount::<Self>::MAX,
91 );
92 }
93
94 #[inline(always)]
95 fn unpack<A: Pack<Self>>(packed: usize) -> A {
96 A::from_packed(packed)
97 }
98
99 #[inline(always)]
100 fn unpack_addr(packed: usize) -> Addr<Self> {
101 Self::unpack(packed)
102 }
103
104 #[inline(always)]
105 fn unpack_tid(packed: usize) -> crate::Tid<Self> {
106 Self::unpack(packed)
107 }
108
109 #[inline(always)]
110 fn unpack_gen(packed: usize) -> Generation<Self> {
111 Self::unpack(packed)
112 }
113}
114impl<C: Config> CfgPrivate for C {}
115
116/// Default slab configuration values.
117#[derive(Copy, Clone)]
118pub struct DefaultConfig {
119 _p: (),
120}
121
122pub(crate) struct DebugConfig<C: Config> {
123 _cfg: PhantomData<fn(C)>,
124}
125
126pub(crate) const WIDTH: usize = std::mem::size_of::<usize>() * 8;
127
128pub(crate) const fn next_pow2(n: usize) -> usize {
129 let pow2 = n.count_ones() == 1;
130 let zeros = n.leading_zeros();
131 1 << (WIDTH - zeros as usize - pow2 as usize)
132}
133
134// === impl DefaultConfig ===
135
136impl Config for DefaultConfig {
137 const INITIAL_PAGE_SIZE: usize = 32;
138
139 #[cfg(target_pointer_width = "64")]
140 const MAX_THREADS: usize = 4096;
141 #[cfg(target_pointer_width = "32")]
142 // TODO(eliza): can we find enough bits to give 32-bit platforms more threads?
143 const MAX_THREADS: usize = 128;
144
145 const MAX_PAGES: usize = WIDTH / 2;
146}
147
148impl fmt::Debug for DefaultConfig {
149 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
150 Self::debug().fmt(f)
151 }
152}
153
154impl<C: Config> fmt::Debug for DebugConfig<C> {
155 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
156 f.debug_struct(std::any::type_name::<C>())
157 .field("initial_page_size", &C::INITIAL_SZ)
158 .field("max_shards", &C::MAX_SHARDS)
159 .field("max_pages", &C::MAX_PAGES)
160 .field("used_bits", &C::USED_BITS)
161 .field("reserved_bits", &C::RESERVED_BITS)
162 .field("pointer_width", &WIDTH)
163 .field("max_concurrent_references", &RefCount::<C>::MAX)
164 .finish()
165 }
166}
167
168#[cfg(test)]
169mod tests {
170 use super::*;
171 use crate::test_util;
172 use crate::Slab;
173
174 #[test]
175 #[cfg_attr(loom, ignore)]
176 #[should_panic]
177 fn validates_max_refs() {
178 struct GiantGenConfig;
179
180 // Configure the slab with a very large number of bits for the generation
181 // counter. This will only leave 1 bit to use for the slot reference
182 // counter, which will fail to validate.
183 impl Config for GiantGenConfig {
184 const INITIAL_PAGE_SIZE: usize = 1;
185 const MAX_THREADS: usize = 1;
186 const MAX_PAGES: usize = 1;
187 }
188
189 let _slab = Slab::<usize>::new_with_config::<GiantGenConfig>();
190 }
191
192 #[test]
193 #[cfg_attr(loom, ignore)]
194 fn big() {
195 let slab = Slab::new();
196
197 for i in 0..10000 {
198 println!("{:?}", i);
199 let k = slab.insert(i).expect("insert");
200 assert_eq!(slab.get(k).expect("get"), i);
201 }
202 }
203
204 #[test]
205 #[cfg_attr(loom, ignore)]
206 fn custom_page_sz() {
207 let slab = Slab::new_with_config::<test_util::TinyConfig>();
208
209 for i in 0..4096 {
210 println!("{}", i);
211 let k = slab.insert(i).expect("insert");
212 assert_eq!(slab.get(k).expect("get"), i);
213 }
214 }
215}
216