1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
#![feature(unique)] #![feature(const_fn)] #![no_std] #[cfg(test)] #[macro_use] extern crate std; use hole::HoleList; mod hole; #[cfg(test)] mod test; /// A fixed size heap backed by a linked list of free memory blocks. pub struct Heap { bottom: usize, size: usize, holes: HoleList, } impl Heap { /// Creates an empty heap. All allocate calls will return `None`. pub const fn empty() -> Heap { Heap { bottom: 0, size: 0, holes: HoleList::empty(), } } /// Creates a new heap with the given `bottom` and `size`. The bottom address must be valid /// and the memory in the `[heap_bottom, heap_bottom + heap_size)` range must not be used for /// anything else. This function is unsafe because it can cause undefined behavior if the /// given address is invalid. pub unsafe fn new(heap_bottom: usize, heap_size: usize) -> Heap { Heap { bottom: heap_bottom, size: heap_size, holes: HoleList::new(heap_bottom, heap_size), } } /// Allocates a chunk of the given size with the given alignment. Returns a pointer to the /// beginning of that chunk if it was successful. Else it returns `None`. /// This function scans the list of free memory blocks and uses the first block that is big /// enough. The runtime is in O(n) where n is the number of free blocks, but it should be /// reasonably fast for small allocations. pub fn allocate_first_fit(&mut self, mut size: usize, align: usize) -> Option<*mut u8> { if size < HoleList::min_size() { size = HoleList::min_size(); } self.holes.allocate_first_fit(size, align) } /// Frees the given allocation. `ptr` must be a pointer returned /// by a call to the `allocate_first_fit` function with identical size and alignment. Undefined /// behavior may occur for invalid arguments, thus this function is unsafe. /// /// This function walks the list of free memory blocks and inserts the freed block at the /// correct place. If the freed block is adjacent to another free block, the blocks are merged /// again. This operation is in `O(n)` since the list needs to be sorted by address. pub unsafe fn deallocate(&mut self, ptr: *mut u8, mut size: usize, _align: usize) { if size < HoleList::min_size() { size = HoleList::min_size(); } self.holes.deallocate(ptr, size); } /// Returns the bottom address of the heap. pub fn bottom(&self) -> usize { self.bottom } /// Returns the size of the heap. pub fn size(&self) -> usize { self.size } } /// Align downwards. Returns the greatest x with alignment `align` /// so that x <= addr. The alignment must be a power of 2. pub fn align_down(addr: usize, align: usize) -> usize { if align.is_power_of_two() { addr & !(align - 1) } else if align == 0 { addr } else { panic!("`align` must be a power of 2"); } } /// Align upwards. Returns the smallest x with alignment `align` /// so that x >= addr. The alignment must be a power of 2. pub fn align_up(addr: usize, align: usize) -> usize { align_down(addr + align - 1, align) }