1 // Copyright 2022, The Android Open Source Project
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 //! Heap implementation.
16
17 use alloc::alloc::alloc;
18 use alloc::alloc::Layout;
19 use alloc::boxed::Box;
20
21 use core::alloc::GlobalAlloc as _;
22 use core::ffi::c_void;
23 use core::mem;
24 use core::num::NonZeroUsize;
25 use core::ptr;
26 use core::ptr::NonNull;
27
28 use buddy_system_allocator::LockedHeap;
29
30 /// 128 KiB
31 const HEAP_SIZE: usize = 0x20000;
32 static mut HEAP: [u8; HEAP_SIZE] = [0; HEAP_SIZE];
33
34 #[global_allocator]
35 static HEAP_ALLOCATOR: LockedHeap<32> = LockedHeap::<32>::new();
36
37 /// SAFETY: Must be called no more than once.
init()38 pub unsafe fn init() {
39 // SAFETY: Nothing else accesses this memory, and we hand it over to the heap to manage and
40 // never touch it again. The heap is locked, so there cannot be any races.
41 let (start, size) = unsafe { (HEAP.as_mut_ptr() as usize, HEAP.len()) };
42
43 let mut heap = HEAP_ALLOCATOR.lock();
44 // SAFETY: We are supplying a valid memory range, and we only do this once.
45 unsafe { heap.init(start, size) };
46 }
47
48 /// Allocate an aligned but uninitialized slice of heap.
aligned_boxed_slice(size: usize, align: usize) -> Option<Box<[u8]>>49 pub fn aligned_boxed_slice(size: usize, align: usize) -> Option<Box<[u8]>> {
50 let size = NonZeroUsize::new(size)?.get();
51 let layout = Layout::from_size_align(size, align).ok()?;
52 // SAFETY - We verify that `size` and the returned `ptr` are non-null.
53 let ptr = unsafe { alloc(layout) };
54 let ptr = NonNull::new(ptr)?.as_ptr();
55 let slice_ptr = ptr::slice_from_raw_parts_mut(ptr, size);
56
57 // SAFETY - The memory was allocated using the proper layout by our global_allocator.
58 Some(unsafe { Box::from_raw(slice_ptr) })
59 }
60
61 #[no_mangle]
malloc(size: usize) -> *mut c_void62 unsafe extern "C" fn malloc(size: usize) -> *mut c_void {
63 allocate(size, false).map_or(ptr::null_mut(), |p| p.cast::<c_void>().as_ptr())
64 }
65
66 #[no_mangle]
calloc(nmemb: usize, size: usize) -> *mut c_void67 unsafe extern "C" fn calloc(nmemb: usize, size: usize) -> *mut c_void {
68 let Some(size) = nmemb.checked_mul(size) else {
69 return ptr::null_mut()
70 };
71 allocate(size, true).map_or(ptr::null_mut(), |p| p.cast::<c_void>().as_ptr())
72 }
73
74 #[no_mangle]
75 /// SAFETY: ptr must be null or point to a currently-allocated block returned by allocate (either
76 /// directly or via malloc or calloc). Note that this function is called directly from C, so we have
77 /// to trust that the C code is doing the right thing; there are checks below which will catch some
78 /// errors.
free(ptr: *mut c_void)79 unsafe extern "C" fn free(ptr: *mut c_void) {
80 let Some(ptr) = NonNull::new(ptr) else { return };
81 // SAFETY: The contents of the HEAP slice may change, but the address range never does.
82 let heap_range = unsafe { HEAP.as_ptr_range() };
83 assert!(
84 heap_range.contains(&(ptr.as_ptr() as *const u8)),
85 "free() called on a pointer that is not part of the HEAP: {ptr:?}"
86 );
87 let (ptr, size) = unsafe {
88 // SAFETY: ptr is non-null and was allocated by allocate, which prepends a correctly aligned
89 // usize.
90 let ptr = ptr.cast::<usize>().as_ptr().offset(-1);
91 (ptr, *ptr)
92 };
93 let size = NonZeroUsize::new(size).unwrap();
94 let layout = malloc_layout(size).unwrap();
95 // SAFETY: If our precondition is satisfied, then this is a valid currently-allocated block.
96 unsafe { HEAP_ALLOCATOR.dealloc(ptr as *mut u8, layout) }
97 }
98
99 /// Allocate a block of memory suitable to return from `malloc()` etc. Returns a valid pointer
100 /// to a suitable aligned region of size bytes, optionally zeroed (and otherwise uninitialized), or
101 /// None if size is 0 or allocation fails. The block can be freed by passing the returned pointer to
102 /// `free()`.
allocate(size: usize, zeroed: bool) -> Option<NonNull<usize>>103 fn allocate(size: usize, zeroed: bool) -> Option<NonNull<usize>> {
104 let size = NonZeroUsize::new(size)?.checked_add(mem::size_of::<usize>())?;
105 let layout = malloc_layout(size)?;
106 // SAFETY: layout is known to have non-zero size.
107 let ptr = unsafe {
108 if zeroed {
109 HEAP_ALLOCATOR.alloc_zeroed(layout)
110 } else {
111 HEAP_ALLOCATOR.alloc(layout)
112 }
113 };
114 let ptr = NonNull::new(ptr)?.cast::<usize>().as_ptr();
115 // SAFETY: ptr points to a newly allocated block of memory which is properly aligned
116 // for a usize and is big enough to hold a usize as well as the requested number of
117 // bytes.
118 unsafe {
119 *ptr = size.get();
120 NonNull::new(ptr.offset(1))
121 }
122 }
123
malloc_layout(size: NonZeroUsize) -> Option<Layout>124 fn malloc_layout(size: NonZeroUsize) -> Option<Layout> {
125 // We want at least 8 byte alignment, and we need to be able to store a usize.
126 const ALIGN: usize = const_max_size(mem::size_of::<usize>(), mem::size_of::<u64>());
127 Layout::from_size_align(size.get(), ALIGN).ok()
128 }
129
const_max_size(a: usize, b: usize) -> usize130 const fn const_max_size(a: usize, b: usize) -> usize {
131 if a > b {
132 a
133 } else {
134 b
135 }
136 }
137