1use 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
54unsafe 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 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 self.slab_ptr = unsafe { self.slab_ptr.add(block_bytes) };
92 self.slab_rem -= block_bytes;
93 p
94 };
95
96 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 unsafe {
109 (*node).next = self.free_lists[class_idx];
110 }
111 self.free_lists[class_idx] = node;
112 }
113}
114
115pub 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 #[must_use]
131 pub const fn new() -> Self {
132 Self {
133 inner: FutexMutex::new(MmapHeapInner::new()),
134 }
135 }
136
137 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 return unsafe { inner.alloc_small(class_idx) };
155 }
156 }
157
158 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 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 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 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 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 let ptr = unsafe { self.alloc_c(req_size, 16) };
230 if !ptr.is_null() {
231 unsafe {
233 crate::mem::set_bytes(ptr, 0, req_size);
234 }
235 }
236 return ptr;
237 }
238 unsafe { Self::alloc_large(req_size, 16) }
240 }
241
242 pub unsafe fn free_c(&self, ptr: *mut u8) {
249 if ptr.is_null() {
250 return;
251 }
252 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 unsafe { inner.free_small(block_ptr, class_idx) };
263 }
264 return;
265 }
266
267 if magic == LARGE_MAGIC {
268 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 pub unsafe fn realloc_c(&self, ptr: *mut u8, new_size: usize) -> *mut u8 {
284 if ptr.is_null() {
285 return unsafe { self.alloc_c(new_size, 16) };
287 }
288 if new_size == 0 {
289 unsafe { self.free_c(ptr) };
291 return null_mut();
292 }
293
294 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 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 unsafe {
325 crate::mem::copy_nonoverlapping_bytes(new_ptr, ptr, copy_len);
326 self.free_c(ptr);
327 }
328 new_ptr
329 }
330
331 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 let ptr = unsafe { self.alloc_c(size, align) };
342 if ptr.is_null() {
343 return crate::errno::ENOMEM;
344 }
345 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 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 unsafe { self.calloc_c(1, layout.size()) }
363 } else {
364 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 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 unsafe { self.realloc_c(ptr, new_size) }
389 } else {
390 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
408pub static GLOBAL_MMAP_HEAP: MmapHeap = MmapHeap::new();
411
412pub unsafe fn c_malloc(size: usize) -> *mut u8 {
418 unsafe { GLOBAL_MMAP_HEAP.alloc_c(size, 16) }
420}
421
422pub unsafe fn c_calloc(nobj: usize, size: usize) -> *mut u8 {
428 unsafe { GLOBAL_MMAP_HEAP.calloc_c(nobj, size) }
430}
431
432pub unsafe fn c_realloc(ptr: *mut u8, new_size: usize) -> *mut u8 {
439 unsafe { GLOBAL_MMAP_HEAP.realloc_c(ptr, new_size) }
441}
442
443pub unsafe fn c_free(ptr: *mut u8) {
450 unsafe { GLOBAL_MMAP_HEAP.free_c(ptr) }
452}
453
454pub unsafe fn c_posix_memalign(out: *mut *mut u8, align: usize, size: usize) -> i32 {
460 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 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}