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