1 use crate::util::slab::{page, Address, Entry, MAX_PAGES}; 2 3 use std::fmt; 4 5 // ┌─────────────┐ ┌────────┐ 6 // │ page 1 │ │ │ 7 // ├─────────────┤ ┌───▶│ next──┼─┐ 8 // │ page 2 │ │ ├────────┤ │ 9 // │ │ │ │XXXXXXXX│ │ 10 // │ local_free──┼─┘ ├────────┤ │ 11 // │ global_free─┼─┐ │ │◀┘ 12 // ├─────────────┤ └───▶│ next──┼─┐ 13 // │ page 3 │ ├────────┤ │ 14 // └─────────────┘ │XXXXXXXX│ │ 15 // ... ├────────┤ │ 16 // ┌─────────────┐ │XXXXXXXX│ │ 17 // │ page n │ ├────────┤ │ 18 // └─────────────┘ │ │◀┘ 19 // │ next──┼───▶ 20 // ├────────┤ 21 // │XXXXXXXX│ 22 // └────────┘ 23 // ... 24 pub(super) struct Shard<T> { 25 /// The local free list for each page. 26 /// 27 /// These are only ever accessed from this shard's thread, so they are 28 /// stored separately from the shared state for the page that can be 29 /// accessed concurrently, to minimize false sharing. 30 local: Box<[page::Local]>, 31 /// The shared state for each page in this shard. 32 /// 33 /// This consists of the page's metadata (size, previous size), remote free 34 /// list, and a pointer to the actual array backing that page. 35 shared: Box<[page::Shared<T>]>, 36 } 37 38 impl<T: Entry> Shard<T> { new() -> Shard<T>39 pub(super) fn new() -> Shard<T> { 40 let mut total_sz = 0; 41 let shared = (0..MAX_PAGES) 42 .map(|page_num| { 43 let sz = page::size(page_num); 44 let prev_sz = total_sz; 45 total_sz += sz; 46 page::Shared::new(sz, prev_sz) 47 }) 48 .collect(); 49 50 let local = (0..MAX_PAGES).map(|_| page::Local::new()).collect(); 51 52 Shard { local, shared } 53 } 54 alloc(&self) -> Option<Address>55 pub(super) fn alloc(&self) -> Option<Address> { 56 // Can we fit the value into an existing page? 57 for (page_idx, page) in self.shared.iter().enumerate() { 58 let local = self.local(page_idx); 59 60 if let Some(page_offset) = page.alloc(local) { 61 return Some(page_offset); 62 } 63 } 64 65 None 66 } 67 get(&self, addr: Address) -> Option<&T>68 pub(super) fn get(&self, addr: Address) -> Option<&T> { 69 let page_idx = addr.page(); 70 71 if page_idx > self.shared.len() { 72 return None; 73 } 74 75 self.shared[page_idx].get(addr) 76 } 77 78 /// Remove an item on the shard's local thread. remove_local(&self, addr: Address)79 pub(super) fn remove_local(&self, addr: Address) { 80 let page_idx = addr.page(); 81 82 if let Some(page) = self.shared.get(page_idx) { 83 page.remove_local(self.local(page_idx), addr); 84 } 85 } 86 87 /// Remove an item, while on a different thread from the shard's local thread. remove_remote(&self, addr: Address)88 pub(super) fn remove_remote(&self, addr: Address) { 89 if let Some(page) = self.shared.get(addr.page()) { 90 page.remove_remote(addr); 91 } 92 } 93 local(&self, i: usize) -> &page::Local94 fn local(&self, i: usize) -> &page::Local { 95 &self.local[i] 96 } 97 } 98 99 impl<T> fmt::Debug for Shard<T> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result100 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 101 f.debug_struct("Shard") 102 .field("shared", &self.shared) 103 .finish() 104 } 105 } 106