diff options
Diffstat (limited to 'crates/buddy_allocator/src/lib.rs')
| -rw-r--r-- | crates/buddy_allocator/src/lib.rs | 27 |
1 files changed, 13 insertions, 14 deletions
diff --git a/crates/buddy_allocator/src/lib.rs b/crates/buddy_allocator/src/lib.rs index f0c8daa..c543ca6 100644 --- a/crates/buddy_allocator/src/lib.rs +++ b/crates/buddy_allocator/src/lib.rs @@ -48,8 +48,6 @@ mod bitvec; mod free_list; mod tree; -// mod stripe; - use crate::{ bitvec::{Bitset, SubregionStatus}, free_list::{FreeList, FreeListNode}, @@ -176,7 +174,7 @@ impl< while let Some((ptr, mut len_pages)) = free_list_alloc.pop() { while len_pages > 0 { let size_class = (len_pages.trailing_zeros() as usize).min(SIZE_CLASS_COUNT - 1); - trees[i].base_ptr = ptr.cast().as_ptr(); + trees[i].base_ptr = Some(ptr.cast()); trees[i].size_class = size_class; i += 1; len_pages -= 1 << size_class; @@ -192,7 +190,7 @@ impl< // Slice the trees slice to fit how many trees actually remained, then sort them by // address. let trees = &mut trees[..i]; - trees.sort_by_key(|tree| tree.base_ptr as usize); + trees.sort_by_key(|tree| tree.base_addr()); // Compute the number of bits that belong to each tree and assign them. let mut bitset_offset = 0; @@ -213,16 +211,12 @@ impl< unsafe { metadata.cast::<u8>().add(metadata.len()).as_ptr() } as usize; for tree in &mut *trees { // SAFETY: This is the one-past-the-end address. - let tree_addr_hi = unsafe { tree.base_ptr.add(1 << tree.size_class) } as usize; + let tree_addr_hi = tree.base_addr() + (PAGE_SIZE << tree.size_class); if metadata_addr_hi == tree_addr_hi { // If the metadata was present inside the tree... TODO. std::eprintln!("TODO"); } else { // Otherwise, we can take the whole range of the tree and add it to the free list. - // - // UNWRAP: The pointer must have been non-null when it was in the free-list - // allocator. - let ptr = NonNull::new(tree.base_ptr as *mut u8).unwrap(); // SAFETY: There are as many sentinels as size classes, so this will be in-bounds. let sentinel = unsafe { free_list_sentinels.add(tree.size_class) }; @@ -233,7 +227,7 @@ impl< // SAFETY: This region is not owned or borrowed by anything else (the only thing it // could be would be the metadata, but that's not in this tree), is of the correct // size, and is composed of untyped memory. - unsafe { free_list.push(ptr) }; + unsafe { free_list.push(tree.base_ptr.unwrap().cast()) }; // Then, set a bit in the bitset to say that this region is present. tree.bitset_mark_as_present(bitset, tree.size_class, 0); @@ -276,7 +270,7 @@ impl< /// - `ptr` must have been returned by a call to `alloc` with the same `size_class`. /// - `ptr` must convey ownership over the entire region. #[requires(size_class < SIZE_CLASS_COUNT)] - pub unsafe fn dealloc(&mut self, ptr: NonNull<u8>, mut size_class: usize) { + pub unsafe fn dealloc(&mut self, ptr: NonNull<u8>, size_class: usize) { // Find the corresponding tree and the offset of the subregion in the tree. let (tree_index, offset) = self.tree_index_and_offset(ptr); let tree = &mut self.trees[tree_index]; @@ -288,12 +282,17 @@ impl< ); // Start combining size classes. + assert!(size_class <= tree.size_class); while size_class < tree.size_class { let buddy_offset = offset ^ (PAGE_SIZE << size_class); todo!("{buddy_offset:#x} {offset:#x}"); } - todo!("{tree:#?}") + // Mark the pointer as being in the tree. + tree.bitset_mark_as_present(&mut self.bitset, size_class, offset); + + // Return the pointer to the appropriate free list. + self.free_list(size_class).push(ptr); } /// Returns the free list with the given size class. @@ -313,7 +312,7 @@ impl< let addr = ptr.as_ptr() as usize; let tree_index = self .trees - .binary_search_by_key(&addr, |tree| tree.base_ptr as usize); + .binary_search_by_key(&addr, |tree| tree.base_addr()); let tree_index = match tree_index { Ok(i) => i, Err(i) => { @@ -321,7 +320,7 @@ impl< i - 1 } }; - let offset = addr - self.trees[tree_index].base_ptr as usize; + let offset = addr - self.trees[tree_index].base_addr(); (tree_index, offset) } } |