bomalloc 0.3.1

A fragmentation-aware experimental allocator built around address-span ownership
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
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;

/// The 32 KiB class would otherwise lose half of every 64 KiB span to the
/// in-band anchor/alignment page. Its local owner resolves the span from TLS,
/// while a foreign deallocator uses the lock-free address tree, so this class
/// uses the full aligned span as payload. The 16 KiB class keeps its anchor: its
/// smaller 3-to-4 capacity gain did not justify the same hot-free lookup cost.
#[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]
}

/// Resolves the only anchor-free class ranges from the caller-provided original
/// size. Config validation fixes `small_max` and the class table, avoiding the
/// general lookup table on these deallocation hot paths.
#[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,
    /// Number of newest spans per eligible size class that remain allocation
    /// candidates. Zero disables cohort sealing. The first implementation is
    /// intentionally limited to classes no larger than 4 KiB.
    pub young_ring_spans: usize,
    /// Maximum inline-prefetched thread-exclusive blocks per size class.
    /// Magazines start at one and grow adaptively to this bound. Once learned,
    /// same-span local frees may remain in an intrusive owner-only overflow list.
    pub local_magazine_capacity: usize,
    /// Number of recently exhausted owner spans that retain a persistent Black
    /// lease for local nursery-style frees. Zero disables the ring. The first
    /// implementation applies only to classes no larger than 4 KiB.
    pub black_span_ring_capacity: usize,
    /// Number of recently freed bitmap words retained and probed before the bump frontier.
    pub recent_free_word_hints: usize,
    /// Maximum address-neighbor window inspected before falling back to a
    /// whole-class snapshot scan after the TLS span ring misses.
    pub locality_window_spans: usize,
    /// Maximum adjacent small-span slots softly reserved for the same owner.
    /// Growth keeps at least five slots when allowed, then scales toward this
    /// bound only for classes that need more spans to cover a 2,048-object
    /// allocation phase. The larger target amortizes snapshot traversal for
    /// low-capacity classes without reserving more space for tiny objects.
    /// The reservation is virtual/uncommitted and remains stealable by others.
    pub locality_reserve_spans: usize,
    /// Additional adjacent slots that may be claimed only after an owner has
    /// exhausted its initial soft territory. Zero disables adaptive growth.
    /// The extension is carved from the immediately following same-owner or
    /// White free extent; failure leaves the ordinary search path unchanged.
    pub adaptive_territory_extension_spans: usize,
    /// Additional page-run extents retained after the initial eight extents.
    /// A non-zero extension keeps the complete territory in one stable tree
    /// descriptor and commits its fixed-stride runs on demand. Zero preserves
    /// the original eight-descriptor batching policy.
    pub adaptive_run_territory_extension_extents: usize,
    /// Maximum number of virgin page-run slots claimed by one owner-local TLS
    /// window with a single shared bump CAS. TLS windows grow adaptively from two
    /// slots after repeated drains. The default is eight on Windows, where a
    /// batch also amortizes `MEM_COMMIT`, and zero on Linux, whose logical
    /// commit is already syscall-free. Zero disables batching for A/B testing.
    pub run_local_window_capacity: usize,
    /// Maximum undiscarded committed bytes retained by empty dedicated
    /// reservations. Older reservations stay committed and mapped, but the OS
    /// may reclaim their obsolete physical contents until compatible reuse.
    pub dedicated_commit_cache_bytes: usize,
    /// Number of lifetime-safe descriptors retained in the owner-local page
    /// queue for 24/32 KiB classes. Zero disables the queue. Handles do not
    /// retain ownership or object slots and are revalidated on every use.
    pub low_capacity_page_queue_spans: usize,
    /// Queue cross-owner small-object releases behind one span-local MPSC head and
    /// publish them to the recycled bitmap in batches. Disabled by default because
    /// direct bitmap publication scales better when many threads free one span.
    pub remote_free_batching: bool,
    /// Maximum cross-owner frees retained as thread-exclusive Black blocks per
    /// size class. Matching allocations reuse them without shared metadata;
    /// full or replaced caches publish one bitmap/accounting batch.
    pub remote_cache_capacity: usize,
    /// Consecutive foreign slow-path probes before another owner's still
    /// unallocated Green reservation is treated as transferable Red territory.
    /// Activated Black spans are never made Red based on utilization.
    pub red_cold_slow_paths: u64,
    pub conflict_threshold: u32,
    pub jump_probability_denominator: u32,
    /// Maximum randomized restarts after a contended global territory probe.
    /// Zero disables the experimental policy, which is the default until a
    /// representative cross-platform workload demonstrates a tail-latency win.
    pub max_random_jumps: u32,
    pub random_seed: Option<u64>,
}

impl Default for Config {
    fn default() -> Self {
        Self::new()
    }
}

impl Config {
    /// Returns the default configuration in a const context.
    ///
    /// This is equivalent to [`Default::default`], but can be used when building
    /// a static [`crate::BoGlobalAllocator`].
    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,
        }
    }

    /// Returns an opt-in configuration for thread-local generational runtimes.
    ///
    /// This keeps the general ownership and retention policy, but raises the
    /// per-class local magazine ceiling from eight to the compiled maximum of
    /// sixteen blocks. The larger owner-only batch reduces nursery-birth refill
    /// transitions when most objects are also released by their allocating
    /// thread. It is not the default because burst and remote-release workloads
    /// can be slightly slower with the larger magazine.
    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::{
        Config, DEFAULT_PAGE_SIZE, MAX_LOCAL_MAGAZINE_CAPACITY, SIZE_CLASSES, SMALL_PAYLOAD_OFFSET,
        headerless_small_class_for_size, small_payload_offset, small_span_capacity,
    };

    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); // 16 B
        assert_eq!(config.small_territory_spans(8), 7); // 192 B
        assert_eq!(config.small_territory_spans(9), 9); // 256 B
        assert_eq!(config.small_territory_spans(11), 18); // 512 B
        assert_eq!(config.small_territory_spans(12), 26); // 768 B
        assert_eq!(config.small_territory_spans(13), 32); // 1 KiB
        assert_eq!(config.small_territory_spans(17), 32); // 4 KiB
        assert_eq!(config.small_territory_spans(19), 32); // 8 KiB
        assert_eq!(config.small_territory_spans(21), 32); // 16 KiB
        assert_eq!(config.small_territory_spans(22), 32); // 24 KiB
        assert_eq!(config.small_territory_spans(23), 32); // 32 KiB
        assert_eq!(config.adaptive_small_territory_spans(6), 5); // 96 B needs no extension
        assert_eq!(config.adaptive_small_territory_spans(13), 35); // 1 KiB learns +3

        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); // 12 KiB
        assert_eq!(small_payload_offset(21), SMALL_PAYLOAD_OFFSET); // 16 KiB
        assert_eq!(small_payload_offset(22), SMALL_PAYLOAD_OFFSET); // 24 KiB
        assert_eq!(small_payload_offset(23), 0); // 32 KiB
        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,
}