buddy_slab_allocator/slab/
mod.rs

1//! Slab allocator — bitmap-based with lock-free cross-CPU freeing.
2//!
3//! The [`SlabAllocator`] is a standalone component that manages object allocation
4//! within pre-supplied slab pages.  It does **not** allocate pages itself; instead
5//! it returns [`SlabAllocResult::NeedsSlab`] to request pages from the caller.
6//!
7//! Cross-CPU frees go through the lock-free [`SlabPageHeader::remote_free`] path.
8
9pub mod cache;
10pub mod page;
11pub mod size_class;
12
13pub use page::SlabPageHeader;
14pub use size_class::SizeClass;
15
16use cache::{CacheDeallocResult, SlabCache};
17use core::alloc::Layout;
18use core::ptr::NonNull;
19
20use crate::error::{AllocError, AllocResult};
21
22/// Result of a slab allocation attempt.
23pub enum SlabAllocResult {
24    /// Object successfully allocated.
25    Allocated(NonNull<u8>),
26    /// The slab cache for this size class has no free objects.
27    /// The caller should allocate `pages` pages from the buddy allocator,
28    /// call [`SlabAllocator::add_slab`], and retry.
29    NeedsSlab { size_class: SizeClass, pages: usize },
30}
31
32/// Result of a slab deallocation.
33pub enum SlabDeallocResult {
34    /// Object freed, nothing else to do.
35    Done,
36    /// The slab page at `base` became empty and should be returned to the buddy.
37    FreeSlab { base: usize, pages: usize },
38}
39
40/// Standalone slab allocator (one per CPU or standalone use).
41pub struct SlabAllocator<const PAGE_SIZE: usize = 0x1000> {
42    caches: [SlabCache; SizeClass::COUNT],
43}
44
45impl<const PAGE_SIZE: usize> SlabAllocator<PAGE_SIZE> {
46    /// Create a new (empty) slab allocator.  No pages are owned yet.
47    pub const fn new() -> Self {
48        Self {
49            caches: [
50                SlabCache::new(SizeClass::Bytes8),
51                SlabCache::new(SizeClass::Bytes16),
52                SlabCache::new(SizeClass::Bytes32),
53                SlabCache::new(SizeClass::Bytes64),
54                SlabCache::new(SizeClass::Bytes128),
55                SlabCache::new(SizeClass::Bytes256),
56                SlabCache::new(SizeClass::Bytes512),
57                SlabCache::new(SizeClass::Bytes1024),
58                SlabCache::new(SizeClass::Bytes2048),
59            ],
60        }
61    }
62}
63
64impl<const PAGE_SIZE: usize> Default for SlabAllocator<PAGE_SIZE> {
65    fn default() -> Self {
66        Self::new()
67    }
68}
69
70impl<const PAGE_SIZE: usize> SlabAllocator<PAGE_SIZE> {
71    /// Try to allocate an object matching `layout`.
72    ///
73    /// If the matching cache is exhausted, [`SlabAllocResult::NeedsSlab`] is returned
74    /// so the caller can supply pages and retry.
75    pub fn alloc(&mut self, layout: Layout) -> AllocResult<SlabAllocResult> {
76        let sc = SizeClass::from_layout(layout).ok_or(AllocError::InvalidParam)?;
77        let cache = &mut self.caches[sc.index()];
78
79        match cache.alloc_object::<PAGE_SIZE>() {
80            Some(addr) => {
81                // SAFETY: `addr` is non-null, aligned, and within a live slab page.
82                let ptr = unsafe { NonNull::new_unchecked(addr as *mut u8) };
83                Ok(SlabAllocResult::Allocated(ptr))
84            }
85            None => Ok(SlabAllocResult::NeedsSlab {
86                size_class: sc,
87                pages: sc.slab_pages(PAGE_SIZE),
88            }),
89        }
90    }
91
92    /// Free an object previously allocated with [`alloc`](Self::alloc).
93    ///
94    /// This is the **local** (owner-CPU) path.  Cross-CPU frees should go through
95    /// [`SlabPageHeader::remote_free`] directly (see [`GlobalAllocator`]).
96    pub fn dealloc(&mut self, ptr: NonNull<u8>, layout: Layout) -> SlabDeallocResult {
97        let sc = SizeClass::from_layout(layout).expect("layout exceeds slab size");
98        let cache = &mut self.caches[sc.index()];
99
100        match cache.dealloc_object::<PAGE_SIZE>(ptr.as_ptr() as usize) {
101            CacheDeallocResult::Done => SlabDeallocResult::Done,
102            CacheDeallocResult::FreeSlab { base, pages } => {
103                SlabDeallocResult::FreeSlab { base, pages }
104            }
105        }
106    }
107
108    /// Supply a freshly allocated slab page to the given size class.
109    ///
110    /// `base` is the virtual address of the page(s), `bytes` = pages × PAGE_SIZE.
111    pub fn add_slab(&mut self, size_class: SizeClass, base: usize, bytes: usize, owner_cpu: u16) {
112        self.caches[size_class.index()].add_slab(base, bytes, owner_cpu);
113    }
114}
buddy_slab_allocator/slab/mod.rs

buddy_slab_allocator/slab/
mod.rs
