diff options
Diffstat (limited to 'vendor/sharded-slab/src/cfg.rs')
-rw-r--r-- | vendor/sharded-slab/src/cfg.rs | 215 |
1 files changed, 215 insertions, 0 deletions
diff --git a/vendor/sharded-slab/src/cfg.rs b/vendor/sharded-slab/src/cfg.rs new file mode 100644 index 000000000..b690ab2bf --- /dev/null +++ b/vendor/sharded-slab/src/cfg.rs @@ -0,0 +1,215 @@ +use crate::page::{ + slot::{Generation, RefCount}, + Addr, +}; +use crate::Pack; +use std::{fmt, marker::PhantomData}; +/// Configuration parameters which can be overridden to tune the behavior of a slab. +pub trait Config: Sized { + /// The maximum number of threads which can access the slab. + /// + /// This value (rounded to a power of two) determines the number of shards + /// in the slab. If a thread is created, accesses the slab, and then terminates, + /// its shard may be reused and thus does not count against the maximum + /// number of threads once the thread has terminated. + const MAX_THREADS: usize = DefaultConfig::MAX_THREADS; + /// The maximum number of pages in each shard in the slab. + /// + /// This value, in combination with `INITIAL_PAGE_SIZE`, determines how many + /// bits of each index are used to represent page addresses. + const MAX_PAGES: usize = DefaultConfig::MAX_PAGES; + /// The size of the first page in each shard. + /// + /// When a page in a shard has been filled with values, a new page + /// will be allocated that is twice as large as the previous page. Thus, the + /// second page will be twice this size, and the third will be four times + /// this size, and so on. + /// + /// Note that page sizes must be powers of two. If this value is not a power + /// of two, it will be rounded to the next power of two. + const INITIAL_PAGE_SIZE: usize = DefaultConfig::INITIAL_PAGE_SIZE; + /// Sets a number of high-order bits in each index which are reserved from + /// user code. + /// + /// Note that these bits are taken from the generation counter; if the page + /// address and thread IDs are configured to use a large number of bits, + /// reserving additional bits will decrease the period of the generation + /// counter. These should thus be used relatively sparingly, to ensure that + /// generation counters are able to effectively prevent the ABA problem. + const RESERVED_BITS: usize = 0; +} + +pub(crate) trait CfgPrivate: Config { + const USED_BITS: usize = Generation::<Self>::LEN + Generation::<Self>::SHIFT; + const INITIAL_SZ: usize = next_pow2(Self::INITIAL_PAGE_SIZE); + const MAX_SHARDS: usize = next_pow2(Self::MAX_THREADS - 1); + const ADDR_INDEX_SHIFT: usize = Self::INITIAL_SZ.trailing_zeros() as usize + 1; + + fn page_size(n: usize) -> usize { + Self::INITIAL_SZ * 2usize.pow(n as _) + } + + fn debug() -> DebugConfig<Self> { + DebugConfig { _cfg: PhantomData } + } + + fn validate() { + assert!( + Self::INITIAL_SZ.is_power_of_two(), + "invalid Config: {:#?}", + Self::debug(), + ); + assert!( + Self::INITIAL_SZ <= Addr::<Self>::BITS, + "invalid Config: {:#?}", + Self::debug() + ); + + assert!( + Generation::<Self>::BITS >= 3, + "invalid Config: {:#?}\ngeneration counter should be at least 3 bits!", + Self::debug() + ); + + assert!( + Self::USED_BITS <= WIDTH, + "invalid Config: {:#?}\ntotal number of bits per index is too large to fit in a word!", + Self::debug() + ); + + assert!( + WIDTH - Self::USED_BITS >= Self::RESERVED_BITS, + "invalid Config: {:#?}\nindices are too large to fit reserved bits!", + Self::debug() + ); + + assert!( + RefCount::<Self>::MAX > 1, + "invalid config: {:#?}\n maximum concurrent references would be {}", + Self::debug(), + RefCount::<Self>::MAX, + ); + } + + #[inline(always)] + fn unpack<A: Pack<Self>>(packed: usize) -> A { + A::from_packed(packed) + } + + #[inline(always)] + fn unpack_addr(packed: usize) -> Addr<Self> { + Self::unpack(packed) + } + + #[inline(always)] + fn unpack_tid(packed: usize) -> crate::Tid<Self> { + Self::unpack(packed) + } + + #[inline(always)] + fn unpack_gen(packed: usize) -> Generation<Self> { + Self::unpack(packed) + } +} +impl<C: Config> CfgPrivate for C {} + +/// Default slab configuration values. +#[derive(Copy, Clone)] +pub struct DefaultConfig { + _p: (), +} + +pub(crate) struct DebugConfig<C: Config> { + _cfg: PhantomData<fn(C)>, +} + +pub(crate) const WIDTH: usize = std::mem::size_of::<usize>() * 8; + +pub(crate) const fn next_pow2(n: usize) -> usize { + let pow2 = n.count_ones() == 1; + let zeros = n.leading_zeros(); + 1 << (WIDTH - zeros as usize - pow2 as usize) +} + +// === impl DefaultConfig === + +impl Config for DefaultConfig { + const INITIAL_PAGE_SIZE: usize = 32; + + #[cfg(target_pointer_width = "64")] + const MAX_THREADS: usize = 4096; + #[cfg(target_pointer_width = "32")] + // TODO(eliza): can we find enough bits to give 32-bit platforms more threads? + const MAX_THREADS: usize = 128; + + const MAX_PAGES: usize = WIDTH / 2; +} + +impl fmt::Debug for DefaultConfig { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + Self::debug().fmt(f) + } +} + +impl<C: Config> fmt::Debug for DebugConfig<C> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct(std::any::type_name::<C>()) + .field("initial_page_size", &C::INITIAL_SZ) + .field("max_shards", &C::MAX_SHARDS) + .field("max_pages", &C::MAX_PAGES) + .field("used_bits", &C::USED_BITS) + .field("reserved_bits", &C::RESERVED_BITS) + .field("pointer_width", &WIDTH) + .field("max_concurrent_references", &RefCount::<C>::MAX) + .finish() + } +} + +#[cfg(test)] +mod tests { + use super::*; + use crate::test_util; + use crate::Slab; + + #[test] + #[cfg_attr(loom, ignore)] + #[should_panic] + fn validates_max_refs() { + struct GiantGenConfig; + + // Configure the slab with a very large number of bits for the generation + // counter. This will only leave 1 bit to use for the slot reference + // counter, which will fail to validate. + impl Config for GiantGenConfig { + const INITIAL_PAGE_SIZE: usize = 1; + const MAX_THREADS: usize = 1; + const MAX_PAGES: usize = 1; + } + + let _slab = Slab::<usize>::new_with_config::<GiantGenConfig>(); + } + + #[test] + #[cfg_attr(loom, ignore)] + fn big() { + let slab = Slab::new(); + + for i in 0..10000 { + println!("{:?}", i); + let k = slab.insert(i).expect("insert"); + assert_eq!(slab.get(k).expect("get"), i); + } + } + + #[test] + #[cfg_attr(loom, ignore)] + fn custom_page_sz() { + let slab = Slab::new_with_config::<test_util::TinyConfig>(); + + for i in 0..4096 { + println!("{}", i); + let k = slab.insert(i).expect("insert"); + assert_eq!(slab.get(k).expect("get"), i); + } + } +} |