1 //! A ZoneAllocator to allocate arbitrary object sizes (up to `ZoneAllocator::MAX_ALLOC_SIZE`) 2 //! 3 //! The ZoneAllocator achieves this by having many `SCAllocator` 4 5 use crate::*; 6 7 /// Creates an instance of a zone, we do this in a macro because we 8 /// re-use the code in const and non-const functions 9 /// 10 /// We can get rid of this once the const fn feature is fully stabilized. 11 macro_rules! new_zone { 12 () => { 13 ZoneAllocator { 14 // TODO(perf): We should probably pick better classes 15 // rather than powers-of-two (see SuperMalloc etc.) 16 small_slabs: [ 17 SCAllocator::new(1 << 3), // 8 18 SCAllocator::new(1 << 4), // 16 19 SCAllocator::new(1 << 5), // 32 20 SCAllocator::new(1 << 6), // 64 21 SCAllocator::new(1 << 7), // 128 22 SCAllocator::new(1 << 8), // 256 23 SCAllocator::new(1 << 9), // 512 24 SCAllocator::new(1 << 10), // 1024 25 SCAllocator::new(1 << 11), // 2048 ], 26 ], 27 total: 0, 28 } 29 }; 30 } 31 32 /// A zone allocator for arbitrary sized allocations. 33 /// 34 /// Has a bunch of `SCAllocator` and through that can serve allocation 35 /// requests for many different object sizes up to (MAX_SIZE_CLASSES) by selecting 36 /// the right `SCAllocator` for allocation and deallocation. 37 /// 38 /// The allocator provides to refill functions `refill` and `refill_large` 39 /// to provide the underlying `SCAllocator` with more memory in case it runs out. 40 pub struct ZoneAllocator<'a> { 41 small_slabs: [SCAllocator<'a, ObjectPage<'a>>; ZoneAllocator::MAX_BASE_SIZE_CLASSES], 42 total: u64, 43 } 44 45 impl<'a> Default for ZoneAllocator<'a> { 46 fn default() -> ZoneAllocator<'a> { 47 new_zone!() 48 } 49 } 50 51 enum Slab { 52 Base(usize), 53 Unsupported, 54 } 55 56 impl<'a> ZoneAllocator<'a> { 57 /// Maximum size which is allocated with ObjectPages (4 KiB pages). 58 /// 59 /// e.g. this is 4 KiB - 80 bytes of meta-data. 60 pub const MAX_BASE_ALLOC_SIZE: usize = 1 << 11; 61 62 /// How many allocators of type SCAllocator<ObjectPage> we have. 63 pub const MAX_BASE_SIZE_CLASSES: usize = 9; 64 65 #[cfg(feature = "unstable")] 66 pub const fn new() -> ZoneAllocator<'a> { 67 new_zone!() 68 } 69 70 #[cfg(not(feature = "unstable"))] 71 pub fn new() -> ZoneAllocator<'a> { 72 new_zone!() 73 } 74 75 /// Return maximum size an object of size `current_size` can use. 76 /// 77 /// Used to optimize `realloc`. 78 pub fn get_max_size(current_size: usize) -> Option<usize> { 79 match current_size { 80 0..=8 => Some(8), 81 9..=16 => Some(16), 82 17..=32 => Some(32), 83 33..=64 => Some(64), 84 65..=128 => Some(128), 85 129..=256 => Some(256), 86 257..=512 => Some(512), 87 513..=1024 => Some(1024), 88 1025..=2048 => Some(2048), 89 _ => None, 90 } 91 } 92 93 /// Figure out index into zone array to get the correct slab allocator for that size. 94 fn get_slab(requested_size: usize) -> Slab { 95 match requested_size { 96 0..=8 => Slab::Base(0), 97 9..=16 => Slab::Base(1), 98 17..=32 => Slab::Base(2), 99 33..=64 => Slab::Base(3), 100 65..=128 => Slab::Base(4), 101 129..=256 => Slab::Base(5), 102 257..=512 => Slab::Base(6), 103 513..=1024 => Slab::Base(7), 104 1025..=2048 => Slab::Base(8), 105 _ => Slab::Unsupported, 106 } 107 } 108 109 /// Reclaims empty pages by calling `dealloc` on it and removing it from the 110 /// empty lists in the [`SCAllocator`]. 111 /// 112 /// The `dealloc` function is called at most `reclaim_base_max` times for 113 /// base pages, and at most `reclaim_large_max` for large pages. 114 pub fn try_reclaim_base_pages<F>(&mut self, mut to_reclaim: usize, mut dealloc: F) 115 where 116 F: Fn(*mut ObjectPage), 117 { 118 for i in 0..ZoneAllocator::MAX_BASE_SIZE_CLASSES { 119 let slab = &mut self.small_slabs[i]; 120 // reclaim的page数 121 let just_reclaimed = slab.try_reclaim_pages(to_reclaim, &mut dealloc); 122 self.total -= (just_reclaimed * OBJECT_PAGE_SIZE) as u64; 123 to_reclaim = to_reclaim.saturating_sub(just_reclaimed); 124 if to_reclaim == 0 { 125 break; 126 } 127 } 128 } 129 130 /// 获取scallocator中的还未被分配的空间 131 pub fn free_space(&mut self) -> u64 { 132 // 记录空闲空间 133 let mut free = 0; 134 // 遍历所有scallocator 135 for count in 0..ZoneAllocator::MAX_BASE_SIZE_CLASSES { 136 // 获取scallocator 137 let scallocator = &mut self.small_slabs[count]; 138 139 // 遍历scallocator中的部分分配的page(partial_page) 140 for slab_page in scallocator.slabs.iter_mut() { 141 // 剩余可分配object数乘上page中规定的每个object的大小，即空闲空间 142 free += slab_page.free_obj_count() * scallocator.size(); 143 } 144 // 遍历scallocator中的empty_page，把空页空间也加上去 145 free += 146 scallocator.empty_slabs.elements * (scallocator.obj_per_page * scallocator.size()); 147 } 148 free as u64 149 } 150 151 pub fn usage(&mut self) -> SlabUsage { 152 let free_num = self.free_space(); 153 SlabUsage::new(self.total, free_num) 154 } 155 } 156 157 unsafe impl<'a> crate::Allocator<'a> for ZoneAllocator<'a> { 158 /// Allocate a pointer to a block of memory described by `layout`. 159 fn allocate(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocationError> { 160 match ZoneAllocator::get_slab(layout.size()) { 161 Slab::Base(idx) => self.small_slabs[idx].allocate(layout), 162 Slab::Unsupported => Err(AllocationError::InvalidLayout), 163 } 164 } 165 166 /// Deallocates a pointer to a block of memory, which was 167 /// previously allocated by `allocate`. 168 /// 169 /// # Arguments 170 /// * `ptr` - Address of the memory location to free. 171 /// * `layout` - Memory layout of the block pointed to by `ptr`. 172 /// * `slab_callback` - The callback function to free slab_page in buddy. 173 unsafe fn deallocate( 174 &mut self, 175 ptr: NonNull<u8>, 176 layout: Layout, 177 slab_callback: &'static dyn CallBack, 178 ) -> Result<(), AllocationError> { 179 match ZoneAllocator::get_slab(layout.size()) { 180 Slab::Base(idx) => self.small_slabs[idx].deallocate(ptr, layout, slab_callback), 181 Slab::Unsupported => Err(AllocationError::InvalidLayout), 182 } 183 } 184 185 /// Refills the SCAllocator for a given Layout with an ObjectPage. 186 /// 187 /// # Safety 188 /// ObjectPage needs to be emtpy etc. 189 unsafe fn refill( 190 &mut self, 191 layout: Layout, 192 new_page: &'a mut ObjectPage<'a>, 193 ) -> Result<(), AllocationError> { 194 match ZoneAllocator::get_slab(layout.size()) { 195 Slab::Base(idx) => { 196 self.small_slabs[idx].refill(new_page); 197 // 每refill一个page就为slab的总空间统计加上4KB 198 self.total += OBJECT_PAGE_SIZE as u64; 199 Ok(()) 200 } 201 Slab::Unsupported => Err(AllocationError::InvalidLayout), 202 } 203 } 204 } 205 206 /// Slab内存空间使用情况 207 pub struct SlabUsage { 208 // slab总共使用的内存空间 209 total: u64, 210 // slab的空闲空间 211 free: u64, 212 } 213 214 impl SlabUsage { 215 /// 初始化SlabUsage 216 pub fn new(total: u64, free: u64) -> Self { 217 Self { total, free } 218 } 219 220 pub fn total(&self) -> u64 { 221 self.total 222 } 223 224 pub fn used(&self) -> u64 { 225 self.total - self.free 226 } 227 228 pub fn free(&self) -> u64 { 229 self.free 230 } 231 } 232