use crate::BoAllocError;
pub const KIB: usize = 1024;
pub const MIB: usize = 1024 * KIB;
pub const DEFAULT_PAGE_SIZE: usize = 4 * KIB;
pub const SMALL_SPAN_SIZE: usize = 64 * KIB;
pub const SMALL_PAYLOAD_OFFSET: usize = 4 * KIB;
pub(crate) const ACCOUNTING_TRANSIENT_LIVE_SLACK: u32 = 4096;
pub const MAX_RECENT_SPANS_PER_CLASS: usize = 8;
pub const MAX_LOCAL_MAGAZINE_CAPACITY: usize = 16;
pub const MAX_BLACK_SPAN_RING_CAPACITY: usize = 8;
pub const MAX_REMOTE_CACHE_CAPACITY: usize = 8;
pub const MAX_RECENT_FREE_WORD_HINTS: usize = 4;
pub const MAX_LOCALITY_WINDOW_SPANS: usize = 64;
pub const MAX_LOW_CAPACITY_PAGE_QUEUE_SPANS: usize = 32;
pub const MAX_ADAPTIVE_TERRITORY_EXTENSION_SPANS: usize = 8;
pub const MAX_ADAPTIVE_RUN_TERRITORY_EXTENSION_EXTENTS: usize = 56;
pub const MAX_RUN_LOCAL_WINDOW_CAPACITY: usize = 8;
pub const DEFAULT_DEDICATED_COMMIT_CACHE_BYTES: usize = 384 * MIB;
const MIN_LOCALITY_TERRITORY_SPANS: usize = 5;
const LOCALITY_TERRITORY_OBJECT_TARGET: usize = 2048;
pub const SIZE_CLASSES: [usize; 24] = [
8, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144,
8192, 12288, 16384, 24576, 32768,
];
const CLASS_LOOKUP_QUANTUM: usize = SIZE_CLASSES[0];
const CLASS_LOOKUP_ENTRIES: usize = SIZE_CLASSES[SIZE_CLASSES.len() - 1] / CLASS_LOOKUP_QUANTUM + 1;
const SMALL_ALIGNMENT_COUNT: usize = DEFAULT_PAGE_SIZE.trailing_zeros() as usize + 1;
const INVALID_CLASS: u8 = u8::MAX;
#[inline]
pub(crate) const fn small_payload_offset(class_index: usize) -> usize {
match class_index {
23 => 0,
_ => SMALL_PAYLOAD_OFFSET,
}
}
#[inline]
pub(crate) const fn small_span_capacity(class_index: usize) -> usize {
(SMALL_SPAN_SIZE - small_payload_offset(class_index)) / SIZE_CLASSES[class_index]
}
#[inline]
pub(crate) const fn headerless_small_class_for_size(size: usize) -> Option<usize> {
if size > SIZE_CLASSES[22] && size <= SIZE_CLASSES[23] {
Some(23)
} else {
None
}
}
const fn build_size_class_lookup() -> [u8; CLASS_LOOKUP_ENTRIES] {
let mut lookup = [INVALID_CLASS; CLASS_LOOKUP_ENTRIES];
let mut quantum = 0;
let mut class_index = 0;
while quantum < CLASS_LOOKUP_ENTRIES {
let minimum = if quantum == 0 {
1
} else {
quantum * CLASS_LOOKUP_QUANTUM
};
while class_index < SIZE_CLASSES.len() && SIZE_CLASSES[class_index] < minimum {
class_index += 1;
}
if class_index < SIZE_CLASSES.len() {
lookup[quantum] = class_index as u8;
}
quantum += 1;
}
lookup
}
const fn build_aligned_class_lookup() -> [[u8; SIZE_CLASSES.len()]; SMALL_ALIGNMENT_COUNT] {
let mut lookup = [[INVALID_CLASS; SIZE_CLASSES.len()]; SMALL_ALIGNMENT_COUNT];
let mut alignment_index = 0;
while alignment_index < SMALL_ALIGNMENT_COUNT {
let alignment = 1_usize << alignment_index;
let mut start = 0;
while start < SIZE_CLASSES.len() {
let mut class_index = start;
while class_index < SIZE_CLASSES.len()
&& SIZE_CLASSES[class_index] & (alignment - 1) != 0
{
class_index += 1;
}
if class_index < SIZE_CLASSES.len() {
lookup[alignment_index][start] = class_index as u8;
}
start += 1;
}
alignment_index += 1;
}
lookup
}
const SIZE_CLASS_BY_QUANTUM: [u8; CLASS_LOOKUP_ENTRIES] = build_size_class_lookup();
const ALIGNED_CLASS_FROM: [[u8; SIZE_CLASSES.len()]; SMALL_ALIGNMENT_COUNT] =
build_aligned_class_lookup();
#[derive(Clone, Debug)]
pub struct Config {
pub chunk_size: usize,
pub small_max: usize,
pub large_threshold: usize,
pub empty_spans_per_class: usize,
pub recent_spans_per_class: usize,
pub young_ring_spans: usize,
pub local_magazine_capacity: usize,
pub black_span_ring_capacity: usize,
pub recent_free_word_hints: usize,
pub locality_window_spans: usize,
pub locality_reserve_spans: usize,
pub adaptive_territory_extension_spans: usize,
pub adaptive_run_territory_extension_extents: usize,
pub run_local_window_capacity: usize,
pub dedicated_commit_cache_bytes: usize,
pub low_capacity_page_queue_spans: usize,
pub remote_free_batching: bool,
pub remote_cache_capacity: usize,
pub red_cold_slow_paths: u64,
pub conflict_threshold: u32,
pub jump_probability_denominator: u32,
pub max_random_jumps: u32,
pub random_seed: Option<u64>,
}
impl Default for Config {
fn default() -> Self {
Self::new()
}
}
impl Config {
pub const fn new() -> Self {
Self {
chunk_size: 16 * MIB,
small_max: 32 * KIB,
large_threshold: MIB,
empty_spans_per_class: 1,
recent_spans_per_class: MAX_RECENT_SPANS_PER_CLASS,
young_ring_spans: 0,
local_magazine_capacity: 8,
black_span_ring_capacity: MAX_BLACK_SPAN_RING_CAPACITY,
recent_free_word_hints: MAX_RECENT_FREE_WORD_HINTS,
locality_window_spans: 32,
locality_reserve_spans: 32,
adaptive_territory_extension_spans: 3,
adaptive_run_territory_extension_extents: 56,
run_local_window_capacity: if cfg!(windows) {
MAX_RUN_LOCAL_WINDOW_CAPACITY
} else {
0
},
dedicated_commit_cache_bytes: DEFAULT_DEDICATED_COMMIT_CACHE_BYTES,
low_capacity_page_queue_spans: 32,
remote_free_batching: false,
remote_cache_capacity: MAX_REMOTE_CACHE_CAPACITY,
red_cold_slow_paths: 4096,
conflict_threshold: 4,
jump_probability_denominator: 8,
max_random_jumps: 0,
random_seed: None,
}
}
pub const fn runtime_gc() -> Self {
let mut config = Self::new();
config.local_magazine_capacity = MAX_LOCAL_MAGAZINE_CAPACITY;
config
}
pub(crate) fn validate(&self, allocation_granularity: usize) -> Result<(), BoAllocError> {
if self.chunk_size < SMALL_SPAN_SIZE
|| !self.chunk_size.is_power_of_two()
|| self.chunk_size % allocation_granularity != 0
|| self.small_max != *SIZE_CLASSES.last().unwrap()
|| self.large_threshold <= self.small_max
|| self.empty_spans_per_class > self.recent_spans_per_class
|| !(1..=MAX_RECENT_SPANS_PER_CLASS).contains(&self.recent_spans_per_class)
|| self.young_ring_spans > self.recent_spans_per_class
|| self.local_magazine_capacity > MAX_LOCAL_MAGAZINE_CAPACITY
|| self.black_span_ring_capacity > MAX_BLACK_SPAN_RING_CAPACITY
|| !(1..=MAX_RECENT_FREE_WORD_HINTS).contains(&self.recent_free_word_hints)
|| !(1..=MAX_LOCALITY_WINDOW_SPANS).contains(&self.locality_window_spans)
|| !(1..=MAX_LOCALITY_WINDOW_SPANS).contains(&self.locality_reserve_spans)
|| self.adaptive_territory_extension_spans > MAX_ADAPTIVE_TERRITORY_EXTENSION_SPANS
|| self.adaptive_run_territory_extension_extents
> MAX_ADAPTIVE_RUN_TERRITORY_EXTENSION_EXTENTS
|| self.run_local_window_capacity > MAX_RUN_LOCAL_WINDOW_CAPACITY
|| self.low_capacity_page_queue_spans > MAX_LOW_CAPACITY_PAGE_QUEUE_SPANS
|| self.remote_cache_capacity > MAX_REMOTE_CACHE_CAPACITY
|| self.jump_probability_denominator == 0
{
return Err(BoAllocError::InvalidConfig);
}
Ok(())
}
#[inline]
pub(crate) fn class_for(&self, size: usize, align: usize) -> Option<usize> {
if !self.is_small_layout(size, align) {
return None;
}
debug_assert!(align.is_power_of_two());
let quantum = size.max(1).div_ceil(CLASS_LOOKUP_QUANTUM);
let start = SIZE_CLASS_BY_QUANTUM[quantum];
if start == INVALID_CLASS {
return None;
}
let class_index = ALIGNED_CLASS_FROM[align.trailing_zeros() as usize][start as usize];
(class_index != INVALID_CLASS).then_some(class_index as usize)
}
#[inline]
pub(crate) fn is_small_layout(&self, size: usize, align: usize) -> bool {
size <= self.small_max && align <= DEFAULT_PAGE_SIZE
}
pub(crate) fn small_territory_spans(&self, class_index: usize) -> usize {
debug_assert!(class_index < SIZE_CLASSES.len());
self.small_territory_demand_spans(class_index)
.min(self.locality_reserve_spans)
}
pub(crate) fn adaptive_small_territory_spans(&self, class_index: usize) -> usize {
let initial = self.small_territory_spans(class_index);
self.small_territory_demand_spans(class_index)
.min(initial.saturating_add(self.adaptive_territory_extension_spans))
}
fn small_territory_demand_spans(&self, class_index: usize) -> usize {
debug_assert!(class_index < SIZE_CLASSES.len());
let capacity = small_span_capacity(class_index);
let floor = MIN_LOCALITY_TERRITORY_SPANS.min(self.locality_reserve_spans);
LOCALITY_TERRITORY_OBJECT_TARGET
.div_ceil(capacity)
.max(floor)
.min(MAX_LOCALITY_WINDOW_SPANS)
}
}
#[cfg(test)]
mod tests {
use super::{
headerless_small_class_for_size, small_payload_offset, small_span_capacity, Config,
DEFAULT_PAGE_SIZE, MAX_LOCAL_MAGAZINE_CAPACITY, SIZE_CLASSES, SMALL_PAYLOAD_OFFSET,
};
fn reference_class(size: usize, align: usize) -> Option<usize> {
if size > *SIZE_CLASSES.last().unwrap() || align > DEFAULT_PAGE_SIZE {
return None;
}
let minimum = size.max(1);
let start = SIZE_CLASSES.partition_point(|class| *class < minimum);
SIZE_CLASSES[start..]
.iter()
.position(|class| *class & (align - 1) == 0)
.map(|offset| start + offset)
}
#[test]
fn compact_class_lookup_matches_reference_for_every_small_layout() {
let config = Config::default();
for size in 0..=config.small_max {
let mut align = 1;
while align <= DEFAULT_PAGE_SIZE {
assert_eq!(
config.class_for(size, align),
reference_class(size, align),
"size={size} align={align}"
);
align *= 2;
}
}
assert_eq!(config.class_for(config.small_max + 1, 8), None);
assert_eq!(config.class_for(8, DEFAULT_PAGE_SIZE * 2), None);
}
#[test]
fn runtime_gc_preset_raises_only_the_local_magazine_ceiling() {
let default = Config::new();
let runtime_gc = Config::runtime_gc();
assert_eq!(default.local_magazine_capacity, 8);
assert_eq!(
runtime_gc.local_magazine_capacity,
MAX_LOCAL_MAGAZINE_CAPACITY
);
assert_eq!(runtime_gc.chunk_size, default.chunk_size);
assert_eq!(
runtime_gc.recent_spans_per_class,
default.recent_spans_per_class
);
assert_eq!(
runtime_gc.remote_cache_capacity,
default.remote_cache_capacity
);
assert!(runtime_gc.validate(64 * 1024).is_ok());
}
#[test]
fn small_territory_scales_only_for_low_capacity_classes() {
let config = Config::default();
assert_eq!(config.small_territory_spans(1), 5); assert_eq!(config.small_territory_spans(8), 7); assert_eq!(config.small_territory_spans(9), 9); assert_eq!(config.small_territory_spans(11), 18); assert_eq!(config.small_territory_spans(12), 26); assert_eq!(config.small_territory_spans(13), 32); assert_eq!(config.small_territory_spans(17), 32); assert_eq!(config.small_territory_spans(19), 32); assert_eq!(config.small_territory_spans(21), 32); assert_eq!(config.small_territory_spans(22), 32); assert_eq!(config.small_territory_spans(23), 32); assert_eq!(config.adaptive_small_territory_spans(6), 5); assert_eq!(config.adaptive_small_territory_spans(13), 35);
let wide = Config {
locality_reserve_spans: 64,
..Config::default()
};
assert_eq!(wide.small_territory_spans(13), 35);
assert_eq!(wide.adaptive_small_territory_spans(13), 35);
let one = Config {
locality_reserve_spans: 1,
..Config::default()
};
assert_eq!(one.small_territory_spans(1), 1);
assert_eq!(one.small_territory_spans(23), 1);
}
#[test]
fn headerless_large_small_classes_recover_the_anchor_page() {
assert_eq!(small_payload_offset(20), SMALL_PAYLOAD_OFFSET); assert_eq!(small_payload_offset(21), SMALL_PAYLOAD_OFFSET); assert_eq!(small_payload_offset(22), SMALL_PAYLOAD_OFFSET); assert_eq!(small_payload_offset(23), 0); assert_eq!(small_span_capacity(21), 3);
assert_eq!(small_span_capacity(23), 2);
assert_eq!(headerless_small_class_for_size(12_288), None);
assert_eq!(headerless_small_class_for_size(12_289), None);
assert_eq!(headerless_small_class_for_size(16_384), None);
assert_eq!(headerless_small_class_for_size(16_385), None);
assert_eq!(headerless_small_class_for_size(24_576), None);
assert_eq!(headerless_small_class_for_size(24_577), Some(23));
assert_eq!(headerless_small_class_for_size(32_768), Some(23));
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum TrimMode {
Excess,
Aggressive,
}