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