Skip to main content

libc_rs/
heap.rs

1//! Dynamic `mmap_anonymous` slab and page-granularity allocator for unikernel EL0 binaries.
2
3use core::ptr::null_mut;
4
5use crate::sync::FutexMutex;
6
7#[repr(C)]
8struct FreeNode {
9    next: *mut FreeNode,
10}
11
12#[inline]
13const fn align_up(value: usize, align: usize) -> Option<usize> {
14    let mask = align - 1;
15    match value.checked_add(mask) {
16        Some(v) => Some(v & !mask),
17        None => None,
18    }
19}
20
21const MMAP_NUM_CLASSES: usize = 8;
22const MMAP_CLASS_TOTAL_SIZES: [usize; MMAP_NUM_CLASSES] = [32, 64, 128, 256, 512, 1024, 2048, 4096];
23const MMAP_HEADER_BYTES: usize = 16;
24const MMAP_LARGE_HEADER_BYTES: usize = 32;
25const MMAP_MAX_SMALL_PAYLOAD: usize = 4080;
26const MMAP_SLAB_BYTES: usize = 16 * crate::mm::PAGE_SIZE;
27
28const SMALL_MAGIC_BASE: usize = 0xC0DE_5A1B_0000_0000;
29const SMALL_MAGIC_MASK: usize = 0xFFFF_FFFF_FFFF_FF00;
30const LARGE_MAGIC: usize = 0xC0DE_1A6E_5A1B_0001;
31
32#[inline]
33const fn mmap_small_class_index(size: usize) -> Option<usize> {
34    let total = match size.checked_add(MMAP_HEADER_BYTES) {
35        Some(v) => v,
36        None => return None,
37    };
38    let mut i = 0;
39    while i < MMAP_NUM_CLASSES {
40        if total <= MMAP_CLASS_TOTAL_SIZES[i] {
41            return Some(i);
42        }
43        i += 1;
44    }
45    None
46}
47
48struct MmapHeapInner {
49    free_lists: [*mut FreeNode; MMAP_NUM_CLASSES],
50    slab_ptr: *mut u8,
51    slab_rem: usize,
52}
53
54// SAFETY: `MmapHeapInner` is only accessed while holding `MmapHeap::inner`'s `FutexMutex`.
55unsafe impl Send for MmapHeapInner {}
56
57impl MmapHeapInner {
58    const fn new() -> Self {
59        Self {
60            free_lists: [null_mut(); MMAP_NUM_CLASSES],
61            slab_ptr: null_mut(),
62            slab_rem: 0,
63        }
64    }
65
66    unsafe fn alloc_small(&mut self, class_idx: usize) -> *mut u8 {
67        let block_bytes = MMAP_CLASS_TOTAL_SIZES[class_idx];
68        let payload_bytes = block_bytes - MMAP_HEADER_BYTES;
69        let head = self.free_lists[class_idx];
70        let block_ptr = if !head.is_null() {
71            // SAFETY: `head` is a valid free-list node previously carved from a slab.
72            unsafe {
73                self.free_lists[class_idx] = (*head).next;
74            }
75            head.cast::<u8>()
76        } else {
77            if self.slab_rem < block_bytes {
78                let slab = match crate::mm::mmap_anonymous(
79                    MMAP_SLAB_BYTES,
80                    crate::mm::PROT_READ | crate::mm::PROT_WRITE,
81                    0,
82                ) {
83                    Ok(p) if !p.is_null() => p,
84                    _ => return null_mut(),
85                };
86                self.slab_ptr = slab;
87                self.slab_rem = MMAP_SLAB_BYTES;
88            }
89            let p = self.slab_ptr;
90            // SAFETY: `self.slab_rem >= block_bytes` guarantees `add(block_bytes)` stays within the slab.
91            self.slab_ptr = unsafe { self.slab_ptr.add(block_bytes) };
92            self.slab_rem -= block_bytes;
93            p
94        };
95
96        // SAFETY: `block_ptr` is 16-byte aligned and has at least `block_bytes` writable bytes.
97        unsafe {
98            let hdr = block_ptr.cast::<usize>();
99            hdr.write(SMALL_MAGIC_BASE | class_idx);
100            hdr.add(1).write(payload_bytes);
101            block_ptr.add(MMAP_HEADER_BYTES)
102        }
103    }
104
105    unsafe fn free_small(&mut self, block_ptr: *mut u8, class_idx: usize) {
106        let node = block_ptr.cast::<FreeNode>();
107        // SAFETY: `block_ptr` is the start of a small slab block of size >= 32 bytes.
108        unsafe {
109            (*node).next = self.free_lists[class_idx];
110        }
111        self.free_lists[class_idx] = node;
112    }
113}
114
115/// Dynamic virtual-memory allocator backed by `mmap_anonymous` slabs for small blocks
116/// (`<= 4080` bytes) and direct page-granularity `mmap_anonymous`/`munmap` mappings for
117/// large or over-aligned allocations.
118pub struct MmapHeap {
119    inner: FutexMutex<MmapHeapInner>,
120}
121
122impl Default for MmapHeap {
123    fn default() -> Self {
124        Self::new()
125    }
126}
127
128impl MmapHeap {
129    /// Creates a new uninitialized [`MmapHeap`].
130    #[must_use]
131    pub const fn new() -> Self {
132        Self {
133            inner: FutexMutex::new(MmapHeapInner::new()),
134        }
135    }
136
137    /// Allocates `size` bytes with alignment `align` (at least 16-byte aligned), recording
138    /// C-compatible metadata immediately preceding the returned user pointer.
139    ///
140    /// # Safety
141    ///
142    /// Any non-null pointer returned must be released via [`MmapHeap::free_c`] or [`MmapHeap::realloc_c`].
143    pub unsafe fn alloc_c(&self, size: usize, align: usize) -> *mut u8 {
144        let eff_align = if align < 16 { 16 } else { align };
145        if !eff_align.is_power_of_two() {
146            return null_mut();
147        }
148        let req_size = if size == 0 { 1 } else { size };
149
150        if eff_align == 16 && req_size <= MMAP_MAX_SMALL_PAYLOAD {
151            if let Some(class_idx) = mmap_small_class_index(req_size) {
152                let mut inner = self.inner.lock();
153                // SAFETY: `class_idx` is a valid small class index.
154                return unsafe { inner.alloc_small(class_idx) };
155            }
156        }
157
158        // SAFETY: `eff_align` is a power of two >= 16.
159        unsafe { Self::alloc_large(req_size, eff_align) }
160    }
161
162    unsafe fn alloc_large(size: usize, align: usize) -> *mut u8 {
163        let extra = match align.checked_add(MMAP_LARGE_HEADER_BYTES) {
164            Some(v) => v,
165            None => return null_mut(),
166        };
167        let raw_needed = match size.checked_add(extra) {
168            Some(v) => v,
169            None => return null_mut(),
170        };
171        let map_total_len = match align_up(raw_needed, crate::mm::PAGE_SIZE) {
172            Some(v) => v,
173            None => return null_mut(),
174        };
175
176        let map_base = match crate::mm::mmap_anonymous(
177            map_total_len,
178            crate::mm::PROT_READ | crate::mm::PROT_WRITE,
179            0,
180        ) {
181            Ok(p) if !p.is_null() => p,
182            _ => return null_mut(),
183        };
184
185        let base_addr = map_base as usize;
186        let min_user_addr = match base_addr.checked_add(MMAP_LARGE_HEADER_BYTES) {
187            Some(v) => v,
188            None => {
189                // SAFETY: `map_base` and `map_total_len` were just returned by `mmap_anonymous`.
190                let _ = unsafe { crate::mm::munmap(map_base, map_total_len) };
191                return null_mut();
192            }
193        };
194        let user_addr = match align_up(min_user_addr, align) {
195            Some(v) => v,
196            None => {
197                // SAFETY: `map_base` and `map_total_len` were just returned by `mmap_anonymous`.
198                let _ = unsafe { crate::mm::munmap(map_base, map_total_len) };
199                return null_mut();
200            }
201        };
202        let offset = user_addr - base_addr;
203        let usable_size = map_total_len.saturating_sub(offset);
204        // SAFETY: `user_addr` lies within `[base_addr + 32, base_addr + map_total_len)`.
205        unsafe {
206            let user_ptr = map_base.add(offset);
207            let hdr = user_ptr.sub(MMAP_LARGE_HEADER_BYTES).cast::<usize>();
208            hdr.write(base_addr);
209            hdr.add(1).write(map_total_len);
210            hdr.add(2).write(LARGE_MAGIC);
211            hdr.add(3).write(usable_size);
212            user_ptr
213        }
214    }
215
216    /// Allocates and zero-initializes `nobj * size` bytes.
217    ///
218    /// # Safety
219    ///
220    /// Any non-null pointer returned must be released via [`MmapHeap::free_c`] or [`MmapHeap::realloc_c`].
221    pub unsafe fn calloc_c(&self, nobj: usize, size: usize) -> *mut u8 {
222        let total = match nobj.checked_mul(size) {
223            Some(v) => v,
224            None => return null_mut(),
225        };
226        let req_size = if total == 0 { 1 } else { total };
227        if req_size <= MMAP_MAX_SMALL_PAYLOAD {
228            // SAFETY: `req_size` is validated and alignment is 16.
229            let ptr = unsafe { self.alloc_c(req_size, 16) };
230            if !ptr.is_null() {
231                // SAFETY: `ptr` has at least `req_size` writable bytes.
232                unsafe {
233                    crate::mem::set_bytes(ptr, 0, req_size);
234                }
235            }
236            return ptr;
237        }
238        // SAFETY: `req_size > MMAP_MAX_SMALL_PAYLOAD` takes the direct `mmap_anonymous` path.
239        unsafe { Self::alloc_large(req_size, 16) }
240    }
241
242    /// Frees a pointer previously returned by [`MmapHeap::alloc_c`], [`MmapHeap::calloc_c`],
243    /// or [`MmapHeap::realloc_c`]. Passing null is a safe no-op.
244    ///
245    /// # Safety
246    ///
247    /// `ptr` must be null or a live pointer allocated by this [`MmapHeap`].
248    pub unsafe fn free_c(&self, ptr: *mut u8) {
249        if ptr.is_null() {
250            return;
251        }
252        // SAFETY: Every pointer allocated by `MmapHeap` is preceded by at least 16 bytes of metadata.
253        let hdr = unsafe { ptr.sub(MMAP_HEADER_BYTES).cast::<usize>() };
254        let magic = unsafe { hdr.read() };
255
256        if (magic & SMALL_MAGIC_MASK) == SMALL_MAGIC_BASE {
257            let class_idx = magic & 0xFF;
258            if class_idx < MMAP_NUM_CLASSES {
259                let block_ptr = hdr.cast::<u8>();
260                let mut inner = self.inner.lock();
261                // SAFETY: `block_ptr` is a small slab block for `class_idx`.
262                unsafe { inner.free_small(block_ptr, class_idx) };
263            }
264            return;
265        }
266
267        if magic == LARGE_MAGIC {
268            // SAFETY: Large allocations store `[base_addr, map_total_len]` in the 16 bytes before `hdr`.
269            unsafe {
270                let large_hdr = ptr.sub(MMAP_LARGE_HEADER_BYTES).cast::<usize>();
271                let base_addr = large_hdr.read();
272                let map_total_len = large_hdr.add(1).read();
273                let _ = crate::mm::munmap(base_addr as *mut u8, map_total_len);
274            }
275        }
276    }
277
278    /// Resizes an existing allocation to `new_size` bytes.
279    ///
280    /// # Safety
281    ///
282    /// `ptr` must be null or a live pointer allocated by this [`MmapHeap`].
283    pub unsafe fn realloc_c(&self, ptr: *mut u8, new_size: usize) -> *mut u8 {
284        if ptr.is_null() {
285            // SAFETY: Delegating to `alloc_c` with 16-byte alignment.
286            return unsafe { self.alloc_c(new_size, 16) };
287        }
288        if new_size == 0 {
289            // SAFETY: Caller guarantees `ptr` is a valid allocation from this heap.
290            unsafe { self.free_c(ptr) };
291            return null_mut();
292        }
293
294        // SAFETY: `ptr` is preceded by a 16-byte metadata header.
295        let hdr = unsafe { ptr.sub(MMAP_HEADER_BYTES).cast::<usize>() };
296        let magic = unsafe { hdr.read() };
297        let old_usable = unsafe { hdr.add(1).read() };
298
299        if (magic & SMALL_MAGIC_MASK) == SMALL_MAGIC_BASE {
300            let cur_class = magic & 0xFF;
301            if let Some(target_class) = mmap_small_class_index(new_size) {
302                if target_class == cur_class {
303                    return ptr;
304                }
305            }
306        } else if magic == LARGE_MAGIC
307            && new_size <= old_usable
308            && new_size > MMAP_MAX_SMALL_PAYLOAD
309        {
310            return ptr;
311        }
312
313        // SAFETY: Allocating replacement buffer of `new_size` bytes.
314        let new_ptr = unsafe { self.alloc_c(new_size, 16) };
315        if new_ptr.is_null() {
316            return null_mut();
317        }
318        let copy_len = if old_usable < new_size {
319            old_usable
320        } else {
321            new_size
322        };
323        // SAFETY: Both `ptr` and `new_ptr` are valid non-overlapping buffers of at least `copy_len` bytes.
324        unsafe {
325            crate::mem::copy_nonoverlapping_bytes(new_ptr, ptr, copy_len);
326            self.free_c(ptr);
327        }
328        new_ptr
329    }
330
331    /// POSIX-compatible aligned allocation writing the result into `*out`.
332    ///
333    /// # Safety
334    ///
335    /// `out` must be a valid non-null writable pointer to `*mut u8`.
336    pub unsafe fn posix_memalign_c(&self, out: *mut *mut u8, align: usize, size: usize) -> i32 {
337        if out.is_null() || align < core::mem::size_of::<usize>() || !align.is_power_of_two() {
338            return crate::errno::EINVAL;
339        }
340        // SAFETY: `align` is a power of two.
341        let ptr = unsafe { self.alloc_c(size, align) };
342        if ptr.is_null() {
343            return crate::errno::ENOMEM;
344        }
345        // SAFETY: `out` was checked for non-null above and caller guarantees writability.
346        unsafe {
347            out.write(ptr);
348        }
349        0
350    }
351}
352
353unsafe impl core::alloc::GlobalAlloc for MmapHeap {
354    unsafe fn alloc(&self, layout: core::alloc::Layout) -> *mut u8 {
355        // SAFETY: Forwarding `GlobalAlloc::alloc` to `alloc_c`.
356        unsafe { self.alloc_c(layout.size(), layout.align()) }
357    }
358
359    unsafe fn alloc_zeroed(&self, layout: core::alloc::Layout) -> *mut u8 {
360        if layout.align() <= 16 {
361            // SAFETY: `calloc_c` returns 16-byte aligned zeroed memory.
362            unsafe { self.calloc_c(1, layout.size()) }
363        } else {
364            // SAFETY: Over-aligned allocation + explicit zeroing when small.
365            let ptr = unsafe { self.alloc_c(layout.size(), layout.align()) };
366            if !ptr.is_null() && layout.size() <= MMAP_MAX_SMALL_PAYLOAD {
367                unsafe {
368                    crate::mem::set_bytes(ptr, 0, layout.size());
369                }
370            }
371            ptr
372        }
373    }
374
375    unsafe fn dealloc(&self, ptr: *mut u8, _layout: core::alloc::Layout) {
376        // SAFETY: `ptr` was allocated by `self`.
377        unsafe { self.free_c(ptr) }
378    }
379
380    unsafe fn realloc(
381        &self,
382        ptr: *mut u8,
383        layout: core::alloc::Layout,
384        new_size: usize,
385    ) -> *mut u8 {
386        if layout.align() <= 16 {
387            // SAFETY: Standard 16-byte aligned reallocation.
388            unsafe { self.realloc_c(ptr, new_size) }
389        } else {
390            // SAFETY: Over-aligned reallocation allocates fresh aligned block, copies, and frees.
391            let new_ptr = unsafe { self.alloc_c(new_size, layout.align()) };
392            if !new_ptr.is_null() {
393                let copy_len = if layout.size() < new_size {
394                    layout.size()
395                } else {
396                    new_size
397                };
398                unsafe {
399                    crate::mem::copy_nonoverlapping_bytes(new_ptr, ptr, copy_len);
400                    self.free_c(ptr);
401                }
402            }
403            new_ptr
404        }
405    }
406}
407
408/// Process-wide global [`MmapHeap`] instance used by `c_malloc`, `c_calloc`, `c_realloc`,
409/// `c_free`, and `c_posix_memalign`.
410pub static GLOBAL_MMAP_HEAP: MmapHeap = MmapHeap::new();
411
412/// Allocates `size` bytes of 16-byte aligned memory from [`GLOBAL_MMAP_HEAP`].
413///
414/// # Safety
415///
416/// Returned memory is uninitialized and must be released with [`c_free`] or [`c_realloc`].
417pub unsafe fn c_malloc(size: usize) -> *mut u8 {
418    // SAFETY: Delegating to `GLOBAL_MMAP_HEAP.alloc_c`.
419    unsafe { GLOBAL_MMAP_HEAP.alloc_c(size, 16) }
420}
421
422/// Allocates and zero-initializes `nobj * size` bytes from [`GLOBAL_MMAP_HEAP`].
423///
424/// # Safety
425///
426/// Returned pointer must be released with [`c_free`] or [`c_realloc`].
427pub unsafe fn c_calloc(nobj: usize, size: usize) -> *mut u8 {
428    // SAFETY: Delegating to `GLOBAL_MMAP_HEAP.calloc_c`.
429    unsafe { GLOBAL_MMAP_HEAP.calloc_c(nobj, size) }
430}
431
432/// Resizes the allocation at `ptr` to `new_size` bytes in [`GLOBAL_MMAP_HEAP`].
433///
434/// # Safety
435///
436/// `ptr` must be null or a pointer previously returned by `c_malloc`, `c_calloc`,
437/// `c_realloc`, or `c_posix_memalign`.
438pub unsafe fn c_realloc(ptr: *mut u8, new_size: usize) -> *mut u8 {
439    // SAFETY: Delegating to `GLOBAL_MMAP_HEAP.realloc_c`.
440    unsafe { GLOBAL_MMAP_HEAP.realloc_c(ptr, new_size) }
441}
442
443/// Frees a pointer previously allocated from [`GLOBAL_MMAP_HEAP`].
444///
445/// # Safety
446///
447/// `ptr` must be null or a live pointer returned by `c_malloc`, `c_calloc`,
448/// `c_realloc`, or `c_posix_memalign`.
449pub unsafe fn c_free(ptr: *mut u8) {
450    // SAFETY: Delegating to `GLOBAL_MMAP_HEAP.free_c`.
451    unsafe { GLOBAL_MMAP_HEAP.free_c(ptr) }
452}
453
454/// Allocates `size` bytes aligned to `align` and writes the pointer to `*out`.
455///
456/// # Safety
457///
458/// `out` must be a valid writable pointer to `*mut u8`.
459pub unsafe fn c_posix_memalign(out: *mut *mut u8, align: usize, size: usize) -> i32 {
460    // SAFETY: Delegating to `GLOBAL_MMAP_HEAP.posix_memalign_c`.
461    unsafe { GLOBAL_MMAP_HEAP.posix_memalign_c(out, align, size) }
462}
463
464#[cfg(test)]
465mod tests {
466    use super::*;
467    use core::sync::atomic::{AtomicUsize, Ordering};
468
469    #[test]
470    fn mmap_heap_small_large_realloc_calloc_and_memalign() {
471        use crate::errno::{ENOMEM, Errno};
472        use crate::raw::{nr, with_mock_syscall};
473
474        #[repr(align(4096))]
475        struct AlignedArena([u8; 256 * 1024]);
476
477        static mut ARENA: AlignedArena = AlignedArena([0; 256 * 1024]);
478        static OFFSET: AtomicUsize = AtomicUsize::new(0);
479        static MUNMAP_COUNT: AtomicUsize = AtomicUsize::new(0);
480        static LAST_MUNMAP_LEN: AtomicUsize = AtomicUsize::new(0);
481
482        OFFSET.store(0, Ordering::SeqCst);
483        MUNMAP_COUNT.store(0, Ordering::SeqCst);
484        LAST_MUNMAP_LEN.store(0, Ordering::SeqCst);
485
486        with_mock_syscall(
487            |sysno, args| match sysno {
488                nr::MMAP => {
489                    let len = args[1];
490                    let aligned_len = (len + 4095) & !4095;
491                    let start = OFFSET.fetch_add(aligned_len, Ordering::SeqCst);
492                    if start + aligned_len > 256 * 1024 {
493                        return Err(Errno(ENOMEM));
494                    }
495                    // SAFETY: `start + aligned_len` is within `ARENA`.
496                    let ptr = unsafe { core::ptr::addr_of_mut!(ARENA.0).cast::<u8>().add(start) };
497                    unsafe {
498                        crate::mem::set_bytes(ptr, 0, aligned_len);
499                    }
500                    Ok(ptr as usize)
501                }
502                nr::MUNMAP => {
503                    MUNMAP_COUNT.fetch_add(1, Ordering::SeqCst);
504                    LAST_MUNMAP_LEN.store(args[1], Ordering::SeqCst);
505                    Ok(0)
506                }
507                _ => Err(Errno(crate::errno::ENOSYS)),
508            },
509            || {
510                let p1 = unsafe { c_malloc(24) };
511                assert!(!p1.is_null());
512                assert_eq!((p1 as usize) % 16, 0);
513                unsafe {
514                    crate::mem::set_bytes(p1, 0xAB, 24);
515                    c_free(p1);
516                }
517                let p2 = unsafe { c_malloc(24) };
518                assert_eq!(p1, p2);
519
520                let p_same = unsafe { c_realloc(p2, 40) };
521                assert_eq!(p_same, p2);
522
523                let p_grow = unsafe { c_realloc(p_same, 200) };
524                assert!(!p_grow.is_null());
525                assert_ne!(p_grow, p_same);
526                for i in 0..24 {
527                    assert_eq!(unsafe { *p_grow.add(i) }, 0xAB);
528                }
529                unsafe {
530                    c_free(p_grow);
531                }
532
533                let overflow = unsafe { c_calloc(usize::MAX, 2) };
534                assert!(overflow.is_null());
535                let zeroed = unsafe { c_calloc(8, 16) };
536                assert!(!zeroed.is_null());
537                for i in 0..128 {
538                    assert_eq!(unsafe { *zeroed.add(i) }, 0);
539                }
540                unsafe {
541                    c_free(zeroed);
542                }
543
544                let big = unsafe { c_malloc(8192) };
545                assert!(!big.is_null());
546                assert_eq!((big as usize) % 16, 0);
547                unsafe {
548                    *big = 0x55;
549                    *big.add(8191) = 0x77;
550                    c_free(big);
551                }
552                assert_eq!(MUNMAP_COUNT.load(Ordering::SeqCst), 1);
553                assert!(LAST_MUNMAP_LEN.load(Ordering::SeqCst) >= 8192);
554
555                let mut aligned_out: *mut u8 = null_mut();
556                assert_eq!(
557                    unsafe { c_posix_memalign(&mut aligned_out, 3, 64) },
558                    crate::errno::EINVAL
559                );
560                assert_eq!(
561                    unsafe { c_posix_memalign(&mut aligned_out, 4, 64) },
562                    crate::errno::EINVAL
563                );
564                assert_eq!(unsafe { c_posix_memalign(&mut aligned_out, 4096, 1024) }, 0);
565                assert!(!aligned_out.is_null());
566                assert_eq!((aligned_out as usize) % 4096, 0);
567                unsafe {
568                    c_free(aligned_out);
569                }
570                assert_eq!(MUNMAP_COUNT.load(Ordering::SeqCst), 2);
571            },
572        );
573    }
574}