1 | use crate::cfg::{self, CfgPrivate}; |
2 | use crate::clear::Clear; |
3 | use crate::sync::UnsafeCell; |
4 | use crate::Pack; |
5 | |
6 | pub(crate) mod slot; |
7 | mod stack; |
8 | pub(crate) use self::slot::Slot; |
9 | use std::{fmt, marker::PhantomData}; |
10 | |
11 | /// A page address encodes the location of a slot within a shard (the page |
12 | /// number and offset within that page) as a single linear value. |
13 | #[repr (transparent)] |
14 | pub(crate) struct Addr<C: cfg::Config = cfg::DefaultConfig> { |
15 | addr: usize, |
16 | _cfg: PhantomData<fn(C)>, |
17 | } |
18 | |
19 | impl<C: cfg::Config> Addr<C> { |
20 | const NULL: usize = Self::BITS + 1; |
21 | |
22 | pub(crate) fn index(self) -> usize { |
23 | // Since every page is twice as large as the previous page, and all page sizes |
24 | // are powers of two, we can determine the page index that contains a given |
25 | // address by counting leading zeros, which tells us what power of two |
26 | // the offset fits into. |
27 | // |
28 | // First, we must shift down to the smallest page size, so that the last |
29 | // offset on the first page becomes 0. |
30 | let shifted: usize = (self.addr + C::INITIAL_SZ) >> C::ADDR_INDEX_SHIFT; |
31 | // Now, we can determine the number of twos places by counting the |
32 | // number of leading zeros (unused twos places) in the number's binary |
33 | // representation, and subtracting that count from the total number of bits in a word. |
34 | cfg::WIDTH - shifted.leading_zeros() as usize |
35 | } |
36 | |
37 | pub(crate) fn offset(self) -> usize { |
38 | self.addr |
39 | } |
40 | } |
41 | |
42 | pub(crate) trait FreeList<C> { |
43 | fn push<T>(&self, new_head: usize, slot: &Slot<T, C>) |
44 | where |
45 | C: cfg::Config; |
46 | } |
47 | |
48 | impl<C: cfg::Config> Pack<C> for Addr<C> { |
49 | const LEN: usize = C::MAX_PAGES + C::ADDR_INDEX_SHIFT; |
50 | |
51 | type Prev = (); |
52 | |
53 | fn as_usize(&self) -> usize { |
54 | self.addr |
55 | } |
56 | |
57 | fn from_usize(addr: usize) -> Self { |
58 | debug_assert!(addr <= Self::BITS); |
59 | Self { |
60 | addr, |
61 | _cfg: PhantomData, |
62 | } |
63 | } |
64 | } |
65 | |
66 | pub(crate) type Iter<'a, T, C> = std::iter::FilterMap< |
67 | std::slice::Iter<'a, Slot<Option<T>, C>>, |
68 | fn(&'a Slot<Option<T>, C>) -> Option<&'a T>, |
69 | >; |
70 | |
71 | pub(crate) struct Local { |
72 | /// Index of the first slot on the local free list |
73 | head: UnsafeCell<usize>, |
74 | } |
75 | |
76 | pub(crate) struct Shared<T, C> { |
77 | /// The remote free list |
78 | /// |
79 | /// Slots freed from a remote thread are pushed onto this list. |
80 | remote: stack::TransferStack<C>, |
81 | // Total size of the page. |
82 | // |
83 | // If the head index of the local or remote free list is greater than the size of the |
84 | // page, then that free list is emtpy. If the head of both free lists is greater than `size` |
85 | // then there are no slots left in that page. |
86 | size: usize, |
87 | prev_sz: usize, |
88 | slab: UnsafeCell<Option<Slots<T, C>>>, |
89 | } |
90 | |
91 | type Slots<T, C> = Box<[Slot<T, C>]>; |
92 | |
93 | impl Local { |
94 | pub(crate) fn new() -> Self { |
95 | Self { |
96 | head: UnsafeCell::new(data:0), |
97 | } |
98 | } |
99 | |
100 | #[inline (always)] |
101 | fn head(&self) -> usize { |
102 | self.head.with(|head: *const usize| unsafe { *head }) |
103 | } |
104 | |
105 | #[inline (always)] |
106 | fn set_head(&self, new_head: usize) { |
107 | self.head.with_mut(|head: *mut usize| unsafe { |
108 | *head = new_head; |
109 | }) |
110 | } |
111 | } |
112 | |
113 | impl<C: cfg::Config> FreeList<C> for Local { |
114 | fn push<T>(&self, new_head: usize, slot: &Slot<T, C>) { |
115 | slot.set_next(self.head()); |
116 | self.set_head(new_head); |
117 | } |
118 | } |
119 | |
120 | impl<T, C> Shared<T, C> |
121 | where |
122 | C: cfg::Config, |
123 | { |
124 | const NULL: usize = Addr::<C>::NULL; |
125 | |
126 | pub(crate) fn new(size: usize, prev_sz: usize) -> Self { |
127 | Self { |
128 | prev_sz, |
129 | size, |
130 | remote: stack::TransferStack::new(), |
131 | slab: UnsafeCell::new(None), |
132 | } |
133 | } |
134 | |
135 | /// Return the head of the freelist |
136 | /// |
137 | /// If there is space on the local list, it returns the head of the local list. Otherwise, it |
138 | /// pops all the slots from the global list and returns the head of that list |
139 | /// |
140 | /// *Note*: The local list's head is reset when setting the new state in the slot pointed to be |
141 | /// `head` returned from this function |
142 | #[inline ] |
143 | fn pop(&self, local: &Local) -> Option<usize> { |
144 | let head = local.head(); |
145 | |
146 | test_println!("-> local head {:?}" , head); |
147 | |
148 | // are there any items on the local free list? (fast path) |
149 | let head = if head < self.size { |
150 | head |
151 | } else { |
152 | // slow path: if the local free list is empty, pop all the items on |
153 | // the remote free list. |
154 | let head = self.remote.pop_all(); |
155 | |
156 | test_println!("-> remote head {:?}" , head); |
157 | head? |
158 | }; |
159 | |
160 | // if the head is still null, both the local and remote free lists are |
161 | // empty --- we can't fit any more items on this page. |
162 | if head == Self::NULL { |
163 | test_println!("-> NULL! {:?}" , head); |
164 | None |
165 | } else { |
166 | Some(head) |
167 | } |
168 | } |
169 | |
170 | /// Returns `true` if storage is currently allocated for this page, `false` |
171 | /// otherwise. |
172 | #[inline ] |
173 | fn is_unallocated(&self) -> bool { |
174 | self.slab.with(|s| unsafe { (*s).is_none() }) |
175 | } |
176 | |
177 | #[inline ] |
178 | pub(crate) fn with_slot<'a, U>( |
179 | &'a self, |
180 | addr: Addr<C>, |
181 | f: impl FnOnce(&'a Slot<T, C>) -> Option<U>, |
182 | ) -> Option<U> { |
183 | let poff = addr.offset() - self.prev_sz; |
184 | |
185 | test_println!("-> offset {:?}" , poff); |
186 | |
187 | self.slab.with(|slab| { |
188 | let slot = unsafe { &*slab }.as_ref()?.get(poff)?; |
189 | f(slot) |
190 | }) |
191 | } |
192 | |
193 | #[inline (always)] |
194 | pub(crate) fn free_list(&self) -> &impl FreeList<C> { |
195 | &self.remote |
196 | } |
197 | } |
198 | |
199 | impl<'a, T, C> Shared<Option<T>, C> |
200 | where |
201 | C: cfg::Config + 'a, |
202 | { |
203 | pub(crate) fn take<F>( |
204 | &self, |
205 | addr: Addr<C>, |
206 | gen: slot::Generation<C>, |
207 | free_list: &F, |
208 | ) -> Option<T> |
209 | where |
210 | F: FreeList<C>, |
211 | { |
212 | let offset = addr.offset() - self.prev_sz; |
213 | |
214 | test_println!("-> take: offset {:?}" , offset); |
215 | |
216 | self.slab.with(|slab| { |
217 | let slab = unsafe { &*slab }.as_ref()?; |
218 | let slot = slab.get(offset)?; |
219 | slot.remove_value(gen, offset, free_list) |
220 | }) |
221 | } |
222 | |
223 | pub(crate) fn remove<F: FreeList<C>>( |
224 | &self, |
225 | addr: Addr<C>, |
226 | gen: slot::Generation<C>, |
227 | free_list: &F, |
228 | ) -> bool { |
229 | let offset = addr.offset() - self.prev_sz; |
230 | |
231 | test_println!("-> offset {:?}" , offset); |
232 | |
233 | self.slab.with(|slab| { |
234 | let slab = unsafe { &*slab }.as_ref(); |
235 | if let Some(slot) = slab.and_then(|slab| slab.get(offset)) { |
236 | slot.try_remove_value(gen, offset, free_list) |
237 | } else { |
238 | false |
239 | } |
240 | }) |
241 | } |
242 | |
243 | // Need this function separately, as we need to pass a function pointer to `filter_map` and |
244 | // `Slot::value` just returns a `&T`, specifically a `&Option<T>` for this impl. |
245 | fn make_ref(slot: &'a Slot<Option<T>, C>) -> Option<&'a T> { |
246 | slot.value().as_ref() |
247 | } |
248 | |
249 | pub(crate) fn iter(&self) -> Option<Iter<'a, T, C>> { |
250 | let slab = self.slab.with(|slab| unsafe { (&*slab).as_ref() }); |
251 | slab.map(|slab| { |
252 | slab.iter() |
253 | .filter_map(Shared::make_ref as fn(&'a Slot<Option<T>, C>) -> Option<&'a T>) |
254 | }) |
255 | } |
256 | } |
257 | |
258 | impl<T, C> Shared<T, C> |
259 | where |
260 | T: Clear + Default, |
261 | C: cfg::Config, |
262 | { |
263 | pub(crate) fn init_with<U>( |
264 | &self, |
265 | local: &Local, |
266 | init: impl FnOnce(usize, &Slot<T, C>) -> Option<U>, |
267 | ) -> Option<U> { |
268 | let head = self.pop(local)?; |
269 | |
270 | // do we need to allocate storage for this page? |
271 | if self.is_unallocated() { |
272 | self.allocate(); |
273 | } |
274 | |
275 | let index = head + self.prev_sz; |
276 | |
277 | let result = self.slab.with(|slab| { |
278 | let slab = unsafe { &*(slab) } |
279 | .as_ref() |
280 | .expect("page must have been allocated to insert!" ); |
281 | let slot = &slab[head]; |
282 | let result = init(index, slot)?; |
283 | local.set_head(slot.next()); |
284 | Some(result) |
285 | })?; |
286 | |
287 | test_println!("-> init_with: insert at offset: {}" , index); |
288 | Some(result) |
289 | } |
290 | |
291 | /// Allocates storage for the page's slots. |
292 | #[cold ] |
293 | fn allocate(&self) { |
294 | test_println!("-> alloc new page ( {})" , self.size); |
295 | debug_assert!(self.is_unallocated()); |
296 | |
297 | let mut slab = Vec::with_capacity(self.size); |
298 | slab.extend((1..self.size).map(Slot::new)); |
299 | slab.push(Slot::new(Self::NULL)); |
300 | self.slab.with_mut(|s| { |
301 | // safety: this mut access is safe — it only occurs to initially allocate the page, |
302 | // which only happens on this thread; if the page has not yet been allocated, other |
303 | // threads will not try to access it yet. |
304 | unsafe { |
305 | *s = Some(slab.into_boxed_slice()); |
306 | } |
307 | }); |
308 | } |
309 | |
310 | pub(crate) fn mark_clear<F: FreeList<C>>( |
311 | &self, |
312 | addr: Addr<C>, |
313 | gen: slot::Generation<C>, |
314 | free_list: &F, |
315 | ) -> bool { |
316 | let offset = addr.offset() - self.prev_sz; |
317 | |
318 | test_println!("-> offset {:?}" , offset); |
319 | |
320 | self.slab.with(|slab| { |
321 | let slab = unsafe { &*slab }.as_ref(); |
322 | if let Some(slot) = slab.and_then(|slab| slab.get(offset)) { |
323 | slot.try_clear_storage(gen, offset, free_list) |
324 | } else { |
325 | false |
326 | } |
327 | }) |
328 | } |
329 | |
330 | pub(crate) fn clear<F: FreeList<C>>( |
331 | &self, |
332 | addr: Addr<C>, |
333 | gen: slot::Generation<C>, |
334 | free_list: &F, |
335 | ) -> bool { |
336 | let offset = addr.offset() - self.prev_sz; |
337 | |
338 | test_println!("-> offset {:?}" , offset); |
339 | |
340 | self.slab.with(|slab| { |
341 | let slab = unsafe { &*slab }.as_ref(); |
342 | if let Some(slot) = slab.and_then(|slab| slab.get(offset)) { |
343 | slot.clear_storage(gen, offset, free_list) |
344 | } else { |
345 | false |
346 | } |
347 | }) |
348 | } |
349 | } |
350 | |
351 | impl fmt::Debug for Local { |
352 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
353 | self.head.with(|head: *const usize| { |
354 | let head: usize = unsafe { *head }; |
355 | f&mut DebugStruct<'_, '_>.debug_struct("Local" ) |
356 | .field(name:"head" , &format_args!(" {:#0x}" , head)) |
357 | .finish() |
358 | }) |
359 | } |
360 | } |
361 | |
362 | impl<C, T> fmt::Debug for Shared<C, T> { |
363 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
364 | f&mut DebugStruct<'_, '_>.debug_struct("Shared" ) |
365 | .field("remote" , &self.remote) |
366 | .field("prev_sz" , &self.prev_sz) |
367 | .field(name:"size" , &self.size) |
368 | // .field("slab", &self.slab) |
369 | .finish() |
370 | } |
371 | } |
372 | |
373 | impl<C: cfg::Config> fmt::Debug for Addr<C> { |
374 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
375 | f&mut DebugStruct<'_, '_>.debug_struct("Addr" ) |
376 | .field("addr" , &format_args!(" {:#0x}" , &self.addr)) |
377 | .field("index" , &self.index()) |
378 | .field(name:"offset" , &self.offset()) |
379 | .finish() |
380 | } |
381 | } |
382 | |
383 | impl<C: cfg::Config> PartialEq for Addr<C> { |
384 | fn eq(&self, other: &Self) -> bool { |
385 | self.addr == other.addr |
386 | } |
387 | } |
388 | |
389 | impl<C: cfg::Config> Eq for Addr<C> {} |
390 | |
391 | impl<C: cfg::Config> PartialOrd for Addr<C> { |
392 | fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> { |
393 | self.addr.partial_cmp(&other.addr) |
394 | } |
395 | } |
396 | |
397 | impl<C: cfg::Config> Ord for Addr<C> { |
398 | fn cmp(&self, other: &Self) -> std::cmp::Ordering { |
399 | self.addr.cmp(&other.addr) |
400 | } |
401 | } |
402 | |
403 | impl<C: cfg::Config> Clone for Addr<C> { |
404 | fn clone(&self) -> Self { |
405 | Self::from_usize(self.addr) |
406 | } |
407 | } |
408 | |
409 | impl<C: cfg::Config> Copy for Addr<C> {} |
410 | |
411 | #[inline (always)] |
412 | pub(crate) fn indices<C: cfg::Config>(idx: usize) -> (Addr<C>, usize) { |
413 | let addr: Addr = C::unpack_addr(packed:idx); |
414 | (addr, addr.index()) |
415 | } |
416 | |
417 | #[cfg (test)] |
418 | mod test { |
419 | use super::*; |
420 | use crate::Pack; |
421 | use proptest::prelude::*; |
422 | |
423 | proptest! { |
424 | #[test] |
425 | fn addr_roundtrips(pidx in 0usize..Addr::<cfg::DefaultConfig>::BITS) { |
426 | let addr = Addr::<cfg::DefaultConfig>::from_usize(pidx); |
427 | let packed = addr.pack(0); |
428 | assert_eq!(addr, Addr::from_packed(packed)); |
429 | } |
430 | #[test] |
431 | fn gen_roundtrips(gen in 0usize..slot::Generation::<cfg::DefaultConfig>::BITS) { |
432 | let gen = slot::Generation::<cfg::DefaultConfig>::from_usize(gen); |
433 | let packed = gen.pack(0); |
434 | assert_eq!(gen, slot::Generation::from_packed(packed)); |
435 | } |
436 | |
437 | #[test] |
438 | fn page_roundtrips( |
439 | gen in 0usize..slot::Generation::<cfg::DefaultConfig>::BITS, |
440 | addr in 0usize..Addr::<cfg::DefaultConfig>::BITS, |
441 | ) { |
442 | let gen = slot::Generation::<cfg::DefaultConfig>::from_usize(gen); |
443 | let addr = Addr::<cfg::DefaultConfig>::from_usize(addr); |
444 | let packed = gen.pack(addr.pack(0)); |
445 | assert_eq!(addr, Addr::from_packed(packed)); |
446 | assert_eq!(gen, slot::Generation::from_packed(packed)); |
447 | } |
448 | } |
449 | } |
450 | |