1 //! Tracks the location of an entry in a slab.
2 //!
3 //! # Index packing
4 //!
5 //! A slab index consists of multiple indices packed into a single `usize` value
6 //! that correspond to different parts of the slab.
7 //!
8 //! The least significant `MAX_PAGES + INITIAL_PAGE_SIZE.trailing_zeros() + 1`
9 //! bits store the address within a shard, starting at 0 for the first slot on
10 //! the first page. To index a slot within a shard, we first find the index of
11 //! the page that the address falls on, and then the offset of the slot within
12 //! that page.
13 //!
14 //! Since every page is twice as large as the previous page, and all page sizes
15 //! are powers of two, we can determine the page index that contains a given
16 //! address by shifting the address down by the smallest page size and looking
17 //! at how many twos places necessary to represent that number, telling us what
18 //! power of two page size it fits inside of. We can determine the number of
19 //! twos places by counting the number of leading zeros (unused twos places) in
20 //! the number's binary representation, and subtracting that count from the
21 //! total number of bits in a word.
22 //!
23 //! Once we know what page contains an address, we can subtract the size of all
24 //! previous pages from the address to determine the offset within the page.
25 //!
26 //! After the page address, the next `MAX_THREADS.trailing_zeros() + 1` least
27 //! significant bits are the thread ID. These are used to index the array of
28 //! shards to find which shard a slot belongs to. If an entry is being removed
29 //! and the thread ID of its index matches that of the current thread, we can
30 //! use the `remove_local` fast path; otherwise, we have to use the synchronized
31 //! `remove_remote` path.
32 //!
33 //! Finally, a generation value is packed into the index. The `RESERVED_BITS`
34 //! most significant bits are left unused, and the remaining bits between the
35 //! last bit of the thread ID and the first reserved bit are used to store the
36 //! generation. The generation is used as part of an atomic read-modify-write
37 //! loop every time a `ScheduledIo`'s readiness is modified, or when the
38 //! resource is removed, to guard against the ABA problem.
39 //!
40 //! Visualized:
41 //!
42 //! ```text
43 //!     ┌──────────┬───────────────┬──────────────────┬──────────────────────────┐
44 //!     │ reserved │  generation   │    thread ID     │         address          │
45 //!     └▲─────────┴▲──────────────┴▲─────────────────┴▲────────────────────────▲┘
46 //!      │          │               │                  │                        │
47 //! bits(usize)     │       bits(MAX_THREADS)          │                        0
48 //!                 │                                  │
49 //!      bits(usize) - RESERVED       MAX_PAGES + bits(INITIAL_PAGE_SIZE)
50 //! ```
51 
52 use crate::util::bit;
53 use crate::util::slab::{Generation, INITIAL_PAGE_SIZE, MAX_PAGES, MAX_THREADS};
54 
55 use std::usize;
56 
57 /// References the location at which an entry is stored in a slab.
58 #[derive(Debug, Copy, Clone, Eq, PartialEq)]
59 pub(crate) struct Address(usize);
60 
61 const PAGE_INDEX_SHIFT: u32 = INITIAL_PAGE_SIZE.trailing_zeros() + 1;
62 
63 /// Address in the shard
64 const SLOT: bit::Pack = bit::Pack::least_significant(MAX_PAGES as u32 + PAGE_INDEX_SHIFT);
65 
66 /// Masks the thread identifier
67 const THREAD: bit::Pack = SLOT.then(MAX_THREADS.trailing_zeros() + 1);
68 
69 /// Masks the generation
70 const GENERATION: bit::Pack = THREAD
71     .then(bit::pointer_width().wrapping_sub(RESERVED.width() + THREAD.width() + SLOT.width()));
72 
73 // Chosen arbitrarily
74 const RESERVED: bit::Pack = bit::Pack::most_significant(5);
75 
76 impl Address {
77     /// Represents no entry, picked to avoid collision with Mio's internals.
78     /// This value should not be passed to mio.
79     pub(crate) const NULL: usize = usize::MAX >> 1;
80 
81     /// Re-exported by `Generation`.
82     pub(super) const GENERATION_WIDTH: u32 = GENERATION.width();
83 
new(shard_index: usize, generation: Generation) -> Address84     pub(super) fn new(shard_index: usize, generation: Generation) -> Address {
85         let mut repr = 0;
86 
87         repr = SLOT.pack(shard_index, repr);
88         repr = GENERATION.pack(generation.to_usize(), repr);
89 
90         Address(repr)
91     }
92 
93     /// Convert from a `usize` representation.
from_usize(src: usize) -> Address94     pub(crate) fn from_usize(src: usize) -> Address {
95         assert_ne!(src, Self::NULL);
96 
97         Address(src)
98     }
99 
100     /// Convert to a `usize` representation
to_usize(self) -> usize101     pub(crate) fn to_usize(self) -> usize {
102         self.0
103     }
104 
generation(self) -> Generation105     pub(crate) fn generation(self) -> Generation {
106         Generation::new(GENERATION.unpack(self.0))
107     }
108 
109     /// Returns the page index
page(self) -> usize110     pub(super) fn page(self) -> usize {
111         // Since every page is twice as large as the previous page, and all page
112         // sizes are powers of two, we can determine the page index that
113         // contains a given address by shifting the address down by the smallest
114         // page size and looking at how many twos places necessary to represent
115         // that number, telling us what power of two page size it fits inside
116         // of. We can determine the number of twos places by counting the number
117         // of leading zeros (unused twos places) in the number's binary
118         // representation, and subtracting that count from the total number of
119         // bits in a word.
120         let slot_shifted = (self.slot() + INITIAL_PAGE_SIZE) >> PAGE_INDEX_SHIFT;
121         (bit::pointer_width() - slot_shifted.leading_zeros()) as usize
122     }
123 
124     /// Returns the slot index
slot(self) -> usize125     pub(super) fn slot(self) -> usize {
126         SLOT.unpack(self.0)
127     }
128 }
129 
130 #[cfg(test)]
131 cfg_not_loom! {
132     use proptest::proptest;
133 
134     #[test]
135     fn test_pack_format() {
136         assert_eq!(5, RESERVED.width());
137         assert_eq!(0b11111, RESERVED.max_value());
138     }
139 
140     proptest! {
141         #[test]
142         fn address_roundtrips(
143             slot in 0usize..SLOT.max_value(),
144             generation in 0usize..Generation::MAX,
145         ) {
146             let address = Address::new(slot, Generation::new(generation));
147             // Round trip
148             let address = Address::from_usize(address.to_usize());
149 
150             assert_eq!(address.slot(), slot);
151             assert_eq!(address.generation().to_usize(), generation);
152         }
153     }
154 }
155