Skip to main content

libc_rs/
heap.rs

1//! Dynamic `mmap_anonymous` slab and page-granularity allocator for unikernel EL0 binaries.
2
3use core::cell::UnsafeCell;
4use core::ptr::null_mut;
5use core::sync::atomic::{AtomicBool, Ordering};
6
7use crate::sync::FutexMutex;
8
9#[repr(C)]
10struct FreeNode {
11    next: *mut FreeNode,
12}
13
14#[inline]
15const fn align_up(value: usize, align: usize) -> Option<usize> {
16    let mask = align - 1;
17    match value.checked_add(mask) {
18        Some(v) => Some(v & !mask),
19        None => None,
20    }
21}
22
23const MMAP_NUM_CLASSES: usize = 8;
24const _: () = assert!(MMAP_NUM_CLASSES == 8);
25const MMAP_CLASS_TOTAL_SIZES: [usize; MMAP_NUM_CLASSES] = [32, 64, 128, 256, 512, 1024, 2048, 4096];
26const MMAP_HEADER_BYTES: usize = 16;
27const MMAP_LARGE_HEADER_BYTES: usize = 32;
28const MMAP_MAX_SMALL_PAYLOAD: usize = 4080;
29const MMAP_SLAB_BYTES: usize = 16 * crate::mm::PAGE_SIZE;
30
31const SMALL_MAGIC_BASE: usize = 0xC0DE_5A1B_0000_0000;
32const SMALL_MAGIC_MASK: usize = 0xFFFF_FFFF_FFFF_FF00;
33const LARGE_MAGIC: usize = 0xC0DE_1A6E_5A1B_0001;
34
35const MAGAZINE_SLOTS: usize = 64;
36const MAGAZINE_CAP: usize = 16;
37const MAGAZINE_BATCH: usize = 8;
38const _: () = {
39    assert!(MAGAZINE_SLOTS == 64);
40    assert!(MAGAZINE_CAP == 16);
41};
42
43#[derive(Copy, Clone)]
44struct ClassMagazine {
45    len: usize,
46    ptrs: [*mut u8; 16],
47}
48
49impl ClassMagazine {
50    const fn new() -> Self {
51        Self {
52            len: 0,
53            ptrs: [null_mut(); 16],
54        }
55    }
56}
57
58#[repr(align(64))]
59struct ThreadMagazineSlot {
60    in_use: AtomicBool,
61    classes: UnsafeCell<[ClassMagazine; 8]>,
62}
63
64// SAFETY: Access to `classes` is serialized per slot via `in_use` acquire/release compare-exchange.
65unsafe impl Sync for ThreadMagazineSlot {}
66
67impl ThreadMagazineSlot {
68    const fn new() -> Self {
69        Self {
70            in_use: AtomicBool::new(false),
71            classes: UnsafeCell::new([ClassMagazine::new(); 8]),
72        }
73    }
74}
75
76#[cfg(not(all(target_arch = "aarch64", target_os = "none")))]
77#[inline]
78fn current_magazine_slot_index() -> usize {
79    let tid = crate::thread::current_thread_id();
80    let mixed = tid ^ (tid >> 6) ^ (tid >> 12) ^ (tid >> 19);
81    (mixed as usize) & (MAGAZINE_SLOTS - 1)
82}
83
84#[inline]
85const fn mmap_small_class_index(size: usize) -> Option<usize> {
86    let total = match size.checked_add(MMAP_HEADER_BYTES) {
87        Some(v) => v,
88        None => return None,
89    };
90    if total > 4096 {
91        return None;
92    }
93    if total <= 32 {
94        return Some(0);
95    }
96    Some((usize::BITS - 5 - (total - 1).leading_zeros()) as usize)
97}
98
99struct MmapHeapInner {
100    free_lists: [*mut FreeNode; 8],
101    slab_ptr: *mut u8,
102    slab_rem: usize,
103}
104
105// SAFETY: `MmapHeapInner` is only accessed while holding `MmapHeap::inner`'s `FutexMutex`.
106unsafe impl Send for MmapHeapInner {}
107
108impl MmapHeapInner {
109    const fn new() -> Self {
110        Self {
111            free_lists: [
112                null_mut(),
113                null_mut(),
114                null_mut(),
115                null_mut(),
116                null_mut(),
117                null_mut(),
118                null_mut(),
119                null_mut(),
120            ],
121            slab_ptr: null_mut(),
122            slab_rem: 0,
123        }
124    }
125
126    unsafe fn alloc_small(&mut self, class_idx: usize) -> *mut u8 {
127        let block_bytes = MMAP_CLASS_TOTAL_SIZES[class_idx];
128        let payload_bytes = block_bytes - MMAP_HEADER_BYTES;
129        let head = self.free_lists[class_idx];
130        let block_ptr = if !head.is_null() {
131            // SAFETY: `head` is a valid free-list node previously carved from a slab.
132            unsafe {
133                self.free_lists[class_idx] = (*head).next;
134            }
135            head.cast::<u8>()
136        } else {
137            if self.slab_rem < block_bytes {
138                let slab = match crate::mm::mmap_anonymous(
139                    MMAP_SLAB_BYTES,
140                    crate::mm::PROT_READ | crate::mm::PROT_WRITE,
141                    0,
142                ) {
143                    Ok(p) if !p.is_null() => p,
144                    _ => return null_mut(),
145                };
146                self.slab_ptr = slab;
147                self.slab_rem = MMAP_SLAB_BYTES;
148            }
149            let p = self.slab_ptr;
150            // SAFETY: `self.slab_rem >= block_bytes` guarantees `add(block_bytes)` stays within the slab.
151            self.slab_ptr = unsafe { self.slab_ptr.add(block_bytes) };
152            self.slab_rem -= block_bytes;
153            p
154        };
155
156        // SAFETY: `block_ptr` is 16-byte aligned and has at least `block_bytes` writable bytes.
157        unsafe {
158            let hdr = block_ptr.cast::<usize>();
159            hdr.write(SMALL_MAGIC_BASE | class_idx);
160            hdr.add(1).write(payload_bytes);
161            block_ptr.add(MMAP_HEADER_BYTES)
162        }
163    }
164
165    unsafe fn free_small(&mut self, block_ptr: *mut u8, class_idx: usize) {
166        let node = block_ptr.cast::<FreeNode>();
167        // SAFETY: `block_ptr` is the start of a small slab block of size >= 32 bytes.
168        unsafe {
169            (*node).next = self.free_lists[class_idx];
170        }
171        self.free_lists[class_idx] = node;
172    }
173}
174
175#[cfg(all(target_arch = "aarch64", target_os = "none"))]
176const TCB_MAG_CAP: usize = 8;
177#[cfg(all(target_arch = "aarch64", target_os = "none"))]
178const TCB_MAG_BATCH: usize = 4;
179
180#[cfg(not(all(target_arch = "aarch64", target_os = "none")))]
181static GLOBAL_MAGAZINES: [ThreadMagazineSlot; 64] = [const { ThreadMagazineSlot::new() }; 64];
182
183pub(crate) fn flush_current_thread_magazine() {
184    #[cfg(all(target_arch = "aarch64", target_os = "none"))]
185    {
186        let tcb = crate::thread::current_tcb_ptr();
187        // SAFETY: Accessing the calling thread's own inline TCB magazine arrays on thread exit.
188        unsafe {
189            let lens = &mut *(*tcb).mag_len.get();
190            let ptrs = &mut *(*tcb).mag_ptrs.get();
191            let mut any = false;
192            let mut c = 0;
193            while c < MMAP_NUM_CLASSES {
194                if lens[c] != 0 {
195                    any = true;
196                    break;
197                }
198                c += 1;
199            }
200            if !any {
201                return;
202            }
203            let mut inner = GLOBAL_MMAP_HEAP.inner.lock();
204            let mut cls = 0;
205            while cls < MMAP_NUM_CLASSES {
206                let mut n = lens[cls] as usize;
207                lens[cls] = 0;
208                while n > 0 {
209                    n -= 1;
210                    let victim_block = ptrs[cls][n].sub(MMAP_HEADER_BYTES);
211                    inner.free_small(victim_block, cls);
212                }
213                cls += 1;
214            }
215        }
216    }
217}
218
219/// Dynamic virtual-memory allocator backed by `mmap_anonymous` slabs for small blocks
220/// (`<= 4080` bytes) and direct page-granularity `mmap_anonymous`/`munmap` mappings for
221/// large or over-aligned allocations.
222pub struct MmapHeap {
223    inner: FutexMutex<MmapHeapInner>,
224    use_tls_cache: bool,
225}
226
227impl Default for MmapHeap {
228    fn default() -> Self {
229        Self::new()
230    }
231}
232
233impl MmapHeap {
234    /// Creates a new uninitialized [`MmapHeap`] without the per-thread magazine cache.
235    #[must_use]
236    pub const fn new() -> Self {
237        Self {
238            inner: FutexMutex::new(MmapHeapInner::new()),
239            use_tls_cache: false,
240        }
241    }
242
243    /// Creates a new uninitialized [`MmapHeap`] with the lock-free per-thread small-block magazine cache enabled.
244    #[must_use]
245    pub const fn new_cached() -> Self {
246        Self {
247            inner: FutexMutex::new(MmapHeapInner::new()),
248            use_tls_cache: true,
249        }
250    }
251
252    #[inline]
253    unsafe fn alloc_small_cached(&self, class_idx: usize) -> *mut u8 {
254        #[cfg(all(target_arch = "aarch64", target_os = "none"))]
255        {
256            let tcb = crate::thread::current_tcb_ptr();
257            // SAFETY: `tcb` belongs exclusively to the calling thread.
258            unsafe {
259                let lens = &mut *(*tcb).mag_len.get();
260                let n = lens[class_idx] as usize;
261                if n > 0 {
262                    let next = n - 1;
263                    lens[class_idx] = next as u8;
264                    return (*(*tcb).mag_ptrs.get())[class_idx][next];
265                }
266                return self.alloc_small_refill_tcb(tcb, class_idx);
267            }
268        }
269        #[cfg(not(all(target_arch = "aarch64", target_os = "none")))]
270        {
271            let slot = &GLOBAL_MAGAZINES[current_magazine_slot_index()];
272            if slot
273                .in_use
274                .compare_exchange(false, true, Ordering::Acquire, Ordering::Relaxed)
275                .is_ok()
276            {
277                // SAFETY: `slot.in_use` is exclusively held by the current thread.
278                let mag = unsafe { &mut (*slot.classes.get())[class_idx] };
279                if mag.len > 0 {
280                    mag.len -= 1;
281                    let ptr = mag.ptrs[mag.len];
282                    slot.in_use.store(false, Ordering::Release);
283                    return ptr;
284                }
285                // SAFETY: `slot.in_use` is held by the caller and released inside `alloc_small_refill`.
286                return unsafe { self.alloc_small_refill(slot, class_idx) };
287            }
288            // SAFETY: `class_idx` is a valid small class index.
289            unsafe { self.alloc_small_contended(class_idx) }
290        }
291    }
292
293    #[cfg(all(target_arch = "aarch64", target_os = "none"))]
294    #[cold]
295    #[inline(never)]
296    unsafe fn alloc_small_refill_tcb(
297        &self,
298        tcb: *mut crate::thread::ThreadControlBlock,
299        class_idx: usize,
300    ) -> *mut u8 {
301        let mut inner = self.inner.lock();
302        let first = unsafe { inner.alloc_small(class_idx) };
303        if !first.is_null() {
304            unsafe {
305                let lens = &mut *(*tcb).mag_len.get();
306                let ptrs = &mut *(*tcb).mag_ptrs.get();
307                let mut n = lens[class_idx] as usize;
308                let mut i = 1;
309                while i < TCB_MAG_BATCH && n < TCB_MAG_CAP {
310                    let extra = inner.alloc_small(class_idx);
311                    if extra.is_null() {
312                        break;
313                    }
314                    ptrs[class_idx][n] = extra;
315                    n += 1;
316                    i += 1;
317                }
318                lens[class_idx] = n as u8;
319            }
320        }
321        first
322    }
323
324    #[cfg(not(all(target_arch = "aarch64", target_os = "none")))]
325    #[cold]
326    #[inline(never)]
327    unsafe fn alloc_small_refill(&self, slot: &ThreadMagazineSlot, class_idx: usize) -> *mut u8 {
328        // SAFETY: `slot.in_use` was acquired by `alloc_small_cached`.
329        let mag = unsafe { &mut (*slot.classes.get())[class_idx] };
330        let mut inner = self.inner.lock();
331        // SAFETY: `class_idx` is a valid small class index.
332        let first = unsafe { inner.alloc_small(class_idx) };
333        if !first.is_null() {
334            let mut i = 1;
335            while i < MAGAZINE_BATCH && mag.len < MAGAZINE_CAP {
336                // SAFETY: `class_idx` is a valid small class index.
337                let extra = unsafe { inner.alloc_small(class_idx) };
338                if extra.is_null() {
339                    break;
340                }
341                mag.ptrs[mag.len] = extra;
342                mag.len += 1;
343                i += 1;
344            }
345        }
346        drop(inner);
347        slot.in_use.store(false, Ordering::Release);
348        first
349    }
350
351    #[cold]
352    #[inline(never)]
353    unsafe fn alloc_small_contended(&self, class_idx: usize) -> *mut u8 {
354        let mut inner = self.inner.lock();
355        // SAFETY: `class_idx` is a valid small class index.
356        unsafe { inner.alloc_small(class_idx) }
357    }
358
359    #[inline]
360    unsafe fn free_small_cached(&self, ptr: *mut u8, block_ptr: *mut u8, class_idx: usize) {
361        #[cfg(all(target_arch = "aarch64", target_os = "none"))]
362        {
363            let _ = block_ptr;
364            let tcb = crate::thread::current_tcb_ptr();
365            // SAFETY: `tcb` belongs exclusively to the calling thread.
366            unsafe {
367                let lens = &mut *(*tcb).mag_len.get();
368                let n = lens[class_idx] as usize;
369                if n < TCB_MAG_CAP {
370                    (*(*tcb).mag_ptrs.get())[class_idx][n] = ptr;
371                    lens[class_idx] = (n + 1) as u8;
372                    return;
373                }
374                self.free_small_spill_tcb(tcb, ptr, class_idx);
375                return;
376            }
377        }
378        #[cfg(not(all(target_arch = "aarch64", target_os = "none")))]
379        {
380            let slot = &GLOBAL_MAGAZINES[current_magazine_slot_index()];
381            if slot
382                .in_use
383                .compare_exchange(false, true, Ordering::Acquire, Ordering::Relaxed)
384                .is_ok()
385            {
386                // SAFETY: `slot.in_use` is exclusively held by the current thread.
387                let mag = unsafe { &mut (*slot.classes.get())[class_idx] };
388                if mag.len < MAGAZINE_CAP {
389                    mag.ptrs[mag.len] = ptr;
390                    mag.len += 1;
391                    slot.in_use.store(false, Ordering::Release);
392                    return;
393                }
394                // SAFETY: `slot.in_use` is held by the caller and released inside `free_small_spill`.
395                unsafe { self.free_small_spill(slot, ptr, class_idx) };
396                return;
397            }
398            // SAFETY: `block_ptr` is a small slab block for `class_idx`.
399            unsafe { self.free_small_contended(block_ptr, class_idx) };
400        }
401    }
402
403    #[cfg(all(target_arch = "aarch64", target_os = "none"))]
404    #[cold]
405    #[inline(never)]
406    unsafe fn free_small_spill_tcb(
407        &self,
408        tcb: *mut crate::thread::ThreadControlBlock,
409        ptr: *mut u8,
410        class_idx: usize,
411    ) {
412        unsafe {
413            let lens = &mut *(*tcb).mag_len.get();
414            let ptrs = &mut *(*tcb).mag_ptrs.get();
415            let mut n = lens[class_idx] as usize;
416            let mut inner = self.inner.lock();
417            let mut spilled = 0;
418            while spilled < TCB_MAG_BATCH && n > 0 {
419                n -= 1;
420                let victim_block = ptrs[class_idx][n].sub(MMAP_HEADER_BYTES);
421                inner.free_small(victim_block, class_idx);
422                spilled += 1;
423            }
424            drop(inner);
425            ptrs[class_idx][n] = ptr;
426            lens[class_idx] = (n + 1) as u8;
427        }
428    }
429
430    #[cfg(not(all(target_arch = "aarch64", target_os = "none")))]
431    #[cold]
432    #[inline(never)]
433    unsafe fn free_small_spill(&self, slot: &ThreadMagazineSlot, ptr: *mut u8, class_idx: usize) {
434        // SAFETY: `slot.in_use` was acquired by `free_small_cached`.
435        let mag = unsafe { &mut (*slot.classes.get())[class_idx] };
436        let mut inner = self.inner.lock();
437        let mut spilled = 0;
438        while spilled < MAGAZINE_BATCH && mag.len > 0 {
439            mag.len -= 1;
440            let victim_ptr = mag.ptrs[mag.len];
441            // SAFETY: `victim_ptr` is a small user pointer preceded by `MMAP_HEADER_BYTES`.
442            let victim_block = unsafe { victim_ptr.sub(MMAP_HEADER_BYTES) };
443            unsafe { inner.free_small(victim_block, class_idx) };
444            spilled += 1;
445        }
446        drop(inner);
447        mag.ptrs[mag.len] = ptr;
448        mag.len += 1;
449        slot.in_use.store(false, Ordering::Release);
450    }
451
452    #[cold]
453    #[inline(never)]
454    unsafe fn free_small_contended(&self, block_ptr: *mut u8, class_idx: usize) {
455        let mut inner = self.inner.lock();
456        // SAFETY: `block_ptr` is a small slab block for `class_idx`.
457        unsafe { inner.free_small(block_ptr, class_idx) };
458    }
459
460    /// Allocates `size` bytes with alignment `align` (at least 16-byte aligned), recording
461    /// C-compatible metadata immediately preceding the returned user pointer.
462    ///
463    /// # Safety
464    ///
465    /// Any non-null pointer returned must be released via [`MmapHeap::free_c`] or [`MmapHeap::realloc_c`].
466    #[inline]
467    pub unsafe fn alloc_c(&self, size: usize, align: usize) -> *mut u8 {
468        let eff_align = if align < 16 { 16 } else { align };
469        if !eff_align.is_power_of_two() {
470            return null_mut();
471        }
472        let req_size = if size == 0 { 1 } else { size };
473
474        if eff_align == 16 && req_size <= MMAP_MAX_SMALL_PAYLOAD {
475            if let Some(class_idx) = mmap_small_class_index(req_size) {
476                if self.use_tls_cache {
477                    // SAFETY: `class_idx` is a valid small class index.
478                    return unsafe { self.alloc_small_cached(class_idx) };
479                }
480                // SAFETY: `class_idx` is a valid small class index.
481                return unsafe { self.alloc_small_contended(class_idx) };
482            }
483        }
484
485        // SAFETY: `eff_align` is a power of two >= 16.
486        unsafe { Self::alloc_large(req_size, eff_align) }
487    }
488
489    #[cold]
490    #[inline(never)]
491    unsafe fn alloc_large(size: usize, align: usize) -> *mut u8 {
492        let extra = match align.checked_add(MMAP_LARGE_HEADER_BYTES) {
493            Some(v) => v,
494            None => return null_mut(),
495        };
496        let raw_needed = match size.checked_add(extra) {
497            Some(v) => v,
498            None => return null_mut(),
499        };
500        let map_total_len = match align_up(raw_needed, crate::mm::PAGE_SIZE) {
501            Some(v) => v,
502            None => return null_mut(),
503        };
504
505        let map_base = match crate::mm::mmap_anonymous(
506            map_total_len,
507            crate::mm::PROT_READ | crate::mm::PROT_WRITE,
508            0,
509        ) {
510            Ok(p) if !p.is_null() => p,
511            _ => return null_mut(),
512        };
513
514        let base_addr = map_base as usize;
515        let min_user_addr = match base_addr.checked_add(MMAP_LARGE_HEADER_BYTES) {
516            Some(v) => v,
517            None => {
518                // SAFETY: `map_base` and `map_total_len` were just returned by `mmap_anonymous`.
519                let _ = unsafe { crate::mm::munmap(map_base, map_total_len) };
520                return null_mut();
521            }
522        };
523        let user_addr = match align_up(min_user_addr, align) {
524            Some(v) => v,
525            None => {
526                // SAFETY: `map_base` and `map_total_len` were just returned by `mmap_anonymous`.
527                let _ = unsafe { crate::mm::munmap(map_base, map_total_len) };
528                return null_mut();
529            }
530        };
531        let offset = user_addr - base_addr;
532        let usable_size = map_total_len.saturating_sub(offset);
533        // SAFETY: `user_addr` lies within `[base_addr + 32, base_addr + map_total_len)`.
534        unsafe {
535            let user_ptr = map_base.add(offset);
536            let hdr = user_ptr.sub(MMAP_LARGE_HEADER_BYTES).cast::<usize>();
537            hdr.write(base_addr);
538            hdr.add(1).write(map_total_len);
539            hdr.add(2).write(LARGE_MAGIC);
540            hdr.add(3).write(usable_size);
541            user_ptr
542        }
543    }
544
545    /// Allocates and zero-initializes `nobj * size` bytes.
546    ///
547    /// # Safety
548    ///
549    /// Any non-null pointer returned must be released via [`MmapHeap::free_c`] or [`MmapHeap::realloc_c`].
550    pub unsafe fn calloc_c(&self, nobj: usize, size: usize) -> *mut u8 {
551        let total = match nobj.checked_mul(size) {
552            Some(v) => v,
553            None => return null_mut(),
554        };
555        let req_size = if total == 0 { 1 } else { total };
556        if req_size <= MMAP_MAX_SMALL_PAYLOAD {
557            // SAFETY: `req_size` is validated and alignment is 16.
558            let ptr = unsafe { self.alloc_c(req_size, 16) };
559            if !ptr.is_null() {
560                // SAFETY: `ptr` has at least `req_size` writable bytes.
561                unsafe {
562                    crate::mem::set_bytes(ptr, 0, req_size);
563                }
564            }
565            return ptr;
566        }
567        // SAFETY: `req_size > MMAP_MAX_SMALL_PAYLOAD` takes the direct `mmap_anonymous` path.
568        unsafe { Self::alloc_large(req_size, 16) }
569    }
570
571    /// Frees a pointer previously returned by [`MmapHeap::alloc_c`], [`MmapHeap::calloc_c`],
572    /// or [`MmapHeap::realloc_c`]. Passing null is a safe no-op.
573    ///
574    /// # Safety
575    ///
576    /// `ptr` must be null or a live pointer allocated by this [`MmapHeap`].
577    #[inline]
578    pub unsafe fn free_c(&self, ptr: *mut u8) {
579        if ptr.is_null() {
580            return;
581        }
582        // SAFETY: Every pointer allocated by `MmapHeap` is preceded by at least 16 bytes of metadata.
583        let hdr = unsafe { ptr.sub(MMAP_HEADER_BYTES).cast::<usize>() };
584        let magic = unsafe { hdr.read() };
585
586        if (magic & SMALL_MAGIC_MASK) == SMALL_MAGIC_BASE {
587            let class_idx = magic & 0xFF;
588            if class_idx < MMAP_NUM_CLASSES {
589                let block_ptr = hdr.cast::<u8>();
590                if self.use_tls_cache {
591                    // SAFETY: `ptr` and `block_ptr` belong to small slab class `class_idx`.
592                    unsafe { self.free_small_cached(ptr, block_ptr, class_idx) };
593                    return;
594                }
595                // SAFETY: `block_ptr` is a small slab block for `class_idx`.
596                unsafe { self.free_small_contended(block_ptr, class_idx) };
597            }
598            return;
599        }
600
601        if magic == LARGE_MAGIC {
602            // SAFETY: `ptr` has `LARGE_MAGIC` header immediately preceding it.
603            unsafe { Self::free_large(ptr) };
604        }
605    }
606
607    #[cold]
608    #[inline(never)]
609    unsafe fn free_large(ptr: *mut u8) {
610        // SAFETY: Large allocations store `[base_addr, map_total_len]` in the 16 bytes before `hdr`.
611        unsafe {
612            let large_hdr = ptr.sub(MMAP_LARGE_HEADER_BYTES).cast::<usize>();
613            let base_addr = large_hdr.read();
614            let map_total_len = large_hdr.add(1).read();
615            let _ = crate::mm::munmap(base_addr as *mut u8, map_total_len);
616        }
617    }
618
619    /// Resizes an existing allocation to `new_size` bytes.
620    ///
621    /// # Safety
622    ///
623    /// `ptr` must be null or a live pointer allocated by this [`MmapHeap`].
624    pub unsafe fn realloc_c(&self, ptr: *mut u8, new_size: usize) -> *mut u8 {
625        if ptr.is_null() {
626            // SAFETY: Delegating to `alloc_c` with 16-byte alignment.
627            return unsafe { self.alloc_c(new_size, 16) };
628        }
629        if new_size == 0 {
630            // SAFETY: Caller guarantees `ptr` is a valid allocation from this heap.
631            unsafe { self.free_c(ptr) };
632            return null_mut();
633        }
634
635        // SAFETY: `ptr` is preceded by a 16-byte metadata header.
636        let hdr = unsafe { ptr.sub(MMAP_HEADER_BYTES).cast::<usize>() };
637        let magic = unsafe { hdr.read() };
638        let old_usable = unsafe { hdr.add(1).read() };
639
640        if (magic & SMALL_MAGIC_MASK) == SMALL_MAGIC_BASE {
641            let cur_class = magic & 0xFF;
642            if let Some(target_class) = mmap_small_class_index(new_size) {
643                if target_class == cur_class {
644                    return ptr;
645                }
646            }
647        } else if magic == LARGE_MAGIC
648            && new_size <= old_usable
649            && new_size > MMAP_MAX_SMALL_PAYLOAD
650        {
651            return ptr;
652        }
653
654        // SAFETY: Allocating replacement buffer of `new_size` bytes.
655        let new_ptr = unsafe { self.alloc_c(new_size, 16) };
656        if new_ptr.is_null() {
657            return null_mut();
658        }
659        let copy_len = if old_usable < new_size {
660            old_usable
661        } else {
662            new_size
663        };
664        // SAFETY: Both `ptr` and `new_ptr` are valid non-overlapping buffers of at least `copy_len` bytes.
665        unsafe {
666            crate::mem::copy_nonoverlapping_bytes(new_ptr, ptr, copy_len);
667            self.free_c(ptr);
668        }
669        new_ptr
670    }
671
672    /// POSIX-compatible aligned allocation writing the result into `*out`.
673    ///
674    /// # Safety
675    ///
676    /// `out` must be a valid non-null writable pointer to `*mut u8`.
677    pub unsafe fn posix_memalign_c(&self, out: *mut *mut u8, align: usize, size: usize) -> i32 {
678        if out.is_null() || align < core::mem::size_of::<usize>() || !align.is_power_of_two() {
679            return crate::errno::EINVAL;
680        }
681        // SAFETY: `align` is a power of two.
682        let ptr = unsafe { self.alloc_c(size, align) };
683        if ptr.is_null() {
684            return crate::errno::ENOMEM;
685        }
686        // SAFETY: `out` was checked for non-null above and caller guarantees writability.
687        unsafe {
688            out.write(ptr);
689        }
690        0
691    }
692}
693
694unsafe impl core::alloc::GlobalAlloc for MmapHeap {
695    #[inline]
696    unsafe fn alloc(&self, layout: core::alloc::Layout) -> *mut u8 {
697        // SAFETY: Forwarding `GlobalAlloc::alloc` to `alloc_c`.
698        unsafe { self.alloc_c(layout.size(), layout.align()) }
699    }
700
701    #[inline]
702    unsafe fn alloc_zeroed(&self, layout: core::alloc::Layout) -> *mut u8 {
703        if layout.align() <= 16 {
704            // SAFETY: `calloc_c` returns 16-byte aligned zeroed memory.
705            unsafe { self.calloc_c(1, layout.size()) }
706        } else {
707            // SAFETY: Over-aligned allocation + explicit zeroing when small.
708            let ptr = unsafe { self.alloc_c(layout.size(), layout.align()) };
709            if !ptr.is_null() && layout.size() <= MMAP_MAX_SMALL_PAYLOAD {
710                unsafe {
711                    crate::mem::set_bytes(ptr, 0, layout.size());
712                }
713            }
714            ptr
715        }
716    }
717
718    #[inline]
719    unsafe fn dealloc(&self, ptr: *mut u8, _layout: core::alloc::Layout) {
720        // SAFETY: `ptr` was allocated by `self`.
721        unsafe { self.free_c(ptr) }
722    }
723
724    #[inline]
725    unsafe fn realloc(
726        &self,
727        ptr: *mut u8,
728        layout: core::alloc::Layout,
729        new_size: usize,
730    ) -> *mut u8 {
731        if layout.align() <= 16 {
732            // SAFETY: Standard 16-byte aligned reallocation.
733            unsafe { self.realloc_c(ptr, new_size) }
734        } else {
735            // SAFETY: Over-aligned reallocation allocates fresh aligned block, copies, and frees.
736            let new_ptr = unsafe { self.alloc_c(new_size, layout.align()) };
737            if !new_ptr.is_null() {
738                let copy_len = if layout.size() < new_size {
739                    layout.size()
740                } else {
741                    new_size
742                };
743                unsafe {
744                    crate::mem::copy_nonoverlapping_bytes(new_ptr, ptr, copy_len);
745                    self.free_c(ptr);
746                }
747            }
748            new_ptr
749        }
750    }
751}
752
753/// Process-wide global [`MmapHeap`] instance used by `c_malloc`, `c_calloc`, `c_realloc`,
754/// `c_free`, and `c_posix_memalign`.
755pub static GLOBAL_MMAP_HEAP: MmapHeap = MmapHeap::new_cached();
756
757/// Allocates `size` bytes of 16-byte aligned memory from [`GLOBAL_MMAP_HEAP`].
758///
759/// # Safety
760///
761/// Returned memory is uninitialized and must be released with [`c_free`] or [`c_realloc`].
762#[inline]
763pub unsafe fn c_malloc(size: usize) -> *mut u8 {
764    // SAFETY: Delegating to `GLOBAL_MMAP_HEAP.alloc_c`.
765    unsafe { GLOBAL_MMAP_HEAP.alloc_c(size, 16) }
766}
767
768/// Allocates and zero-initializes `nobj * size` bytes from [`GLOBAL_MMAP_HEAP`].
769///
770/// # Safety
771///
772/// Returned pointer must be released with [`c_free`] or [`c_realloc`].
773pub unsafe fn c_calloc(nobj: usize, size: usize) -> *mut u8 {
774    // SAFETY: Delegating to `GLOBAL_MMAP_HEAP.calloc_c`.
775    unsafe { GLOBAL_MMAP_HEAP.calloc_c(nobj, size) }
776}
777
778/// Resizes the allocation at `ptr` to `new_size` bytes in [`GLOBAL_MMAP_HEAP`].
779///
780/// # Safety
781///
782/// `ptr` must be null or a pointer previously returned by `c_malloc`, `c_calloc`,
783/// `c_realloc`, or `c_posix_memalign`.
784pub unsafe fn c_realloc(ptr: *mut u8, new_size: usize) -> *mut u8 {
785    // SAFETY: Delegating to `GLOBAL_MMAP_HEAP.realloc_c`.
786    unsafe { GLOBAL_MMAP_HEAP.realloc_c(ptr, new_size) }
787}
788
789/// Frees a pointer previously allocated from [`GLOBAL_MMAP_HEAP`].
790///
791/// # Safety
792///
793/// `ptr` must be null or a live pointer returned by `c_malloc`, `c_calloc`,
794/// `c_realloc`, or `c_posix_memalign`.
795#[inline]
796pub unsafe fn c_free(ptr: *mut u8) {
797    // SAFETY: Delegating to `GLOBAL_MMAP_HEAP.free_c`.
798    unsafe { GLOBAL_MMAP_HEAP.free_c(ptr) }
799}
800
801/// Allocates `size` bytes aligned to `align` and writes the pointer to `*out`.
802///
803/// # Safety
804///
805/// `out` must be a valid writable pointer to `*mut u8`.
806pub unsafe fn c_posix_memalign(out: *mut *mut u8, align: usize, size: usize) -> i32 {
807    // SAFETY: Delegating to `GLOBAL_MMAP_HEAP.posix_memalign_c`.
808    unsafe { GLOBAL_MMAP_HEAP.posix_memalign_c(out, align, size) }
809}
810
811#[cfg(test)]
812mod tests {
813    use super::*;
814    use core::sync::atomic::{AtomicUsize, Ordering};
815
816    #[test]
817    fn mmap_heap_small_large_realloc_calloc_and_memalign() {
818        use crate::errno::{ENOMEM, Errno};
819        use crate::raw::{nr, with_mock_syscall};
820
821        #[repr(align(4096))]
822        struct AlignedArena([u8; 256 * 1024]);
823
824        static mut ARENA: AlignedArena = AlignedArena([0; 256 * 1024]);
825        static OFFSET: AtomicUsize = AtomicUsize::new(0);
826        static MUNMAP_COUNT: AtomicUsize = AtomicUsize::new(0);
827        static LAST_MUNMAP_LEN: AtomicUsize = AtomicUsize::new(0);
828
829        OFFSET.store(0, Ordering::SeqCst);
830        MUNMAP_COUNT.store(0, Ordering::SeqCst);
831        LAST_MUNMAP_LEN.store(0, Ordering::SeqCst);
832
833        with_mock_syscall(
834            |sysno, args| match sysno {
835                nr::MMAP => {
836                    let len = args[1];
837                    let aligned_len = (len + 4095) & !4095;
838                    let start = OFFSET.fetch_add(aligned_len, Ordering::SeqCst);
839                    if start + aligned_len > 256 * 1024 {
840                        return Err(Errno(ENOMEM));
841                    }
842                    // SAFETY: `start + aligned_len` is within `ARENA`.
843                    let ptr = unsafe { core::ptr::addr_of_mut!(ARENA.0).cast::<u8>().add(start) };
844                    unsafe {
845                        crate::mem::set_bytes(ptr, 0, aligned_len);
846                    }
847                    Ok(ptr as usize)
848                }
849                nr::MUNMAP => {
850                    MUNMAP_COUNT.fetch_add(1, Ordering::SeqCst);
851                    LAST_MUNMAP_LEN.store(args[1], Ordering::SeqCst);
852                    Ok(0)
853                }
854                _ => Err(Errno(crate::errno::ENOSYS)),
855            },
856            || {
857                let p1 = unsafe { c_malloc(24) };
858                assert!(!p1.is_null());
859                assert_eq!((p1 as usize) % 16, 0);
860                unsafe {
861                    crate::mem::set_bytes(p1, 0xAB, 24);
862                    c_free(p1);
863                }
864                let p2 = unsafe { c_malloc(24) };
865                assert_eq!(p1, p2);
866
867                let p_same = unsafe { c_realloc(p2, 40) };
868                assert_eq!(p_same, p2);
869
870                let p_grow = unsafe { c_realloc(p_same, 200) };
871                assert!(!p_grow.is_null());
872                assert_ne!(p_grow, p_same);
873                for i in 0..24 {
874                    assert_eq!(unsafe { *p_grow.add(i) }, 0xAB);
875                }
876                unsafe {
877                    c_free(p_grow);
878                }
879
880                let overflow = unsafe { c_calloc(usize::MAX, 2) };
881                assert!(overflow.is_null());
882                let zeroed = unsafe { c_calloc(8, 16) };
883                assert!(!zeroed.is_null());
884                for i in 0..128 {
885                    assert_eq!(unsafe { *zeroed.add(i) }, 0);
886                }
887                unsafe {
888                    c_free(zeroed);
889                }
890
891                let big = unsafe { c_malloc(8192) };
892                assert!(!big.is_null());
893                assert_eq!((big as usize) % 16, 0);
894                unsafe {
895                    *big = 0x55;
896                    *big.add(8191) = 0x77;
897                    c_free(big);
898                }
899                assert_eq!(MUNMAP_COUNT.load(Ordering::SeqCst), 1);
900                assert!(LAST_MUNMAP_LEN.load(Ordering::SeqCst) >= 8192);
901
902                let mut aligned_out: *mut u8 = null_mut();
903                assert_eq!(
904                    unsafe { c_posix_memalign(&mut aligned_out, 3, 64) },
905                    crate::errno::EINVAL
906                );
907                assert_eq!(
908                    unsafe { c_posix_memalign(&mut aligned_out, 4, 64) },
909                    crate::errno::EINVAL
910                );
911                assert_eq!(unsafe { c_posix_memalign(&mut aligned_out, 4096, 1024) }, 0);
912                assert!(!aligned_out.is_null());
913                assert_eq!((aligned_out as usize) % 4096, 0);
914                unsafe {
915                    c_free(aligned_out);
916                }
917                assert_eq!(MUNMAP_COUNT.load(Ordering::SeqCst), 2);
918            },
919        );
920    }
921
922    #[test]
923    fn mmap_heap_magazine_hit_refill_and_spill_all_classes() {
924        use crate::errno::{ENOMEM, Errno};
925        use crate::raw::{nr, with_mock_syscall};
926
927        #[repr(align(4096))]
928        struct AlignedArena([u8; 512 * 1024]);
929
930        static mut ARENA: AlignedArena = AlignedArena([0; 512 * 1024]);
931        static OFFSET: AtomicUsize = AtomicUsize::new(0);
932
933        OFFSET.store(0, Ordering::SeqCst);
934
935        with_mock_syscall(
936            |sysno, args| match sysno {
937                nr::MMAP => {
938                    let len = args[1];
939                    let aligned_len = (len + 4095) & !4095;
940                    let start = OFFSET.fetch_add(aligned_len, Ordering::SeqCst);
941                    if start + aligned_len > 512 * 1024 {
942                        return Err(Errno(ENOMEM));
943                    }
944                    // SAFETY: `start + aligned_len` is within `ARENA`.
945                    let ptr = unsafe { core::ptr::addr_of_mut!(ARENA.0).cast::<u8>().add(start) };
946                    unsafe {
947                        crate::mem::set_bytes(ptr, 0, aligned_len);
948                    }
949                    Ok(ptr as usize)
950                }
951                nr::MUNMAP => Ok(0),
952                _ => Err(Errno(crate::errno::ENOSYS)),
953            },
954            || {
955                let heap = MmapHeap::new_cached();
956                let uncached = MmapHeap::new();
957                assert!(heap.use_tls_cache);
958                assert!(!uncached.use_tls_cache);
959                let slot_idx = current_magazine_slot_index();
960                unsafe {
961                    *GLOBAL_MAGAZINES[slot_idx].classes.get() = [ClassMagazine::new(); 8];
962                }
963
964                for (class_idx, &total_bytes) in MMAP_CLASS_TOTAL_SIZES.iter().enumerate() {
965                    let payload = total_bytes - MMAP_HEADER_BYTES;
966                    let mut allocated = [null_mut::<u8>(); 20];
967
968                    // First allocation triggers a batch refill of 8 blocks (1 returned + 7 cached).
969                    allocated[0] = unsafe { heap.alloc_c(payload, 16) };
970                    assert!(!allocated[0].is_null());
971                    let mag_len_after_first =
972                        unsafe { (*GLOBAL_MAGAZINES[slot_idx].classes.get())[class_idx].len };
973                    assert_eq!(mag_len_after_first, MAGAZINE_BATCH - 1);
974
975                    // Allocate 19 more blocks across a second and third refill batch.
976                    for (i, slot_ptr) in allocated.iter_mut().enumerate().skip(1) {
977                        let p = unsafe { heap.alloc_c(payload, 16) };
978                        assert!(!p.is_null());
979                        assert_eq!((p as usize) % 16, 0);
980                        unsafe {
981                            crate::mem::set_bytes(
982                                p,
983                                (class_idx as u8).wrapping_add(i as u8),
984                                payload,
985                            );
986                        }
987                        *slot_ptr = p;
988                    }
989
990                    // Drain any remaining cached blocks in this class so we test exact fill and spill.
991                    loop {
992                        let cur_len =
993                            unsafe { (*GLOBAL_MAGAZINES[slot_idx].classes.get())[class_idx].len };
994                        if cur_len == 0 {
995                            break;
996                        }
997                        let extra = unsafe { heap.alloc_c(payload, 16) };
998                        assert!(!extra.is_null());
999                    }
1000
1001                    // Free 16 blocks to fill the magazine to MAGAZINE_CAP (16).
1002                    for &ptr in allocated.iter().take(MAGAZINE_CAP) {
1003                        unsafe { heap.free_c(ptr) };
1004                    }
1005                    let mag_len_full =
1006                        unsafe { (*GLOBAL_MAGAZINES[slot_idx].classes.get())[class_idx].len };
1007                    assert_eq!(mag_len_full, MAGAZINE_CAP);
1008
1009                    // Freeing the 17th block spills MAGAZINE_BATCH (8) blocks to MmapHeapInner
1010                    // and pushes the new block, leaving `MAGAZINE_CAP - MAGAZINE_BATCH + 1 == 9`.
1011                    unsafe { heap.free_c(allocated[MAGAZINE_CAP]) };
1012                    let mag_len_after_spill =
1013                        unsafe { (*GLOBAL_MAGAZINES[slot_idx].classes.get())[class_idx].len };
1014                    assert_eq!(mag_len_after_spill, MAGAZINE_CAP - MAGAZINE_BATCH + 1);
1015
1016                    // LIFO magazine hit returns the most recently freed block without touching inner.
1017                    let hit = unsafe { heap.alloc_c(payload, 16) };
1018                    assert_eq!(hit, allocated[MAGAZINE_CAP]);
1019
1020                    // Verify calloc_c and realloc_c work seamlessly with the magazine cache.
1021                    let zeroed = unsafe { heap.calloc_c(1, payload) };
1022                    assert!(!zeroed.is_null());
1023                    for b in 0..payload {
1024                        assert_eq!(unsafe { *zeroed.add(b) }, 0);
1025                    }
1026                    let shrunk = unsafe { heap.realloc_c(zeroed, 8) };
1027                    assert!(!shrunk.is_null());
1028                    unsafe {
1029                        heap.free_c(shrunk);
1030                        heap.free_c(hit);
1031                    }
1032                    for &ptr in allocated.iter().skip(MAGAZINE_CAP + 1) {
1033                        unsafe { heap.free_c(ptr) };
1034                    }
1035                }
1036            },
1037        );
1038    }
1039}