1 //! A SCAllocator that can allocate fixed size objects. 2 3 use core::mem; 4 5 use crate::*; 6 7 /// A genius(?) const min() 8 /// 9 /// # What this does 10 /// * create an array of the two elements you want to choose between 11 /// * create an arbitrary boolean expression 12 /// * cast said expresison to a usize 13 /// * use that value to index into the array created above 14 /// 15 /// # Source 16 /// https://stackoverflow.com/questions/53619695/calculating-maximum-value-of-a-set-of-constant-expressions-at-compile-time 17 #[cfg(feature = "unstable")] 18 const fn cmin(a: usize, b: usize) -> usize { 19 [a, b][(a > b) as usize] 20 } 21 22 /// The boring variant of min (not const). 23 #[cfg(not(feature = "unstable"))] 24 fn cmin(a: usize, b: usize) -> usize { 25 core::cmp::min(a, b) 26 } 27 28 /// A slab allocator allocates elements of a fixed size. 29 /// 30 /// It maintains three internal lists of objects that implement `AllocablePage` 31 /// from which it can allocate memory. 32 /// 33 /// * `empty_slabs`: Is a list of pages that the SCAllocator maintains, but 34 /// has 0 allocations in them, these can be given back to a requestor in case 35 /// of reclamation. 36 /// * `slabs`: A list of pages partially allocated and still have room for more. 37 /// * `full_slabs`: A list of pages that are completely allocated. 38 /// 39 /// On allocation we allocate memory from `slabs`, however if the list is empty 40 /// we try to reclaim a page from `empty_slabs` before we return with an out-of-memory 41 /// error. If a page becomes full after the allocation we move it from `slabs` to 42 /// `full_slabs`. 43 /// 44 /// Similarly, on dealloaction we might move a page from `full_slabs` to `slabs` 45 /// or from `slabs` to `empty_slabs` after we deallocated an object. 46 /// 47 /// If an allocation returns `OutOfMemory` a client using SCAllocator can refill 48 /// it using the `refill` function. 49 pub struct SCAllocator<'a, P: AllocablePage> { 50 /// Maximum possible allocation size for this `SCAllocator`. 51 pub(crate) size: usize, 52 /// Keeps track of succeeded allocations. 53 pub(crate) allocation_count: usize, 54 /// max objects per page 55 pub(crate) obj_per_page: usize, 56 /// List of empty ObjectPages (nothing allocated in these). 57 pub(crate) empty_slabs: PageList<'a, P>, 58 /// List of partially used ObjectPage (some objects allocated but pages are not full). 59 pub(crate) slabs: PageList<'a, P>, 60 /// List of full ObjectPages (everything allocated in these don't need to search them). 61 pub(crate) full_slabs: PageList<'a, P>, 62 /// Free objects count 63 pub(crate) free_obj_count: usize, 64 /// Maximum free objects num for this `SCAllocator`. 65 pub(crate) free_limit: usize, 66 } 67 68 /// Creates an instance of a scallocator, we do this in a macro because we 69 /// re-use the code in const and non-const functions 70 macro_rules! new_sc_allocator { 71 ($size:expr) => {{ 72 let obj_per_page = cmin((P::SIZE - OBJECT_PAGE_METADATA_OVERHEAD) / $size, 8 * 64); 73 SCAllocator { 74 size: $size, 75 allocation_count: 0, 76 obj_per_page, 77 empty_slabs: PageList::new(), 78 slabs: PageList::new(), 79 full_slabs: PageList::new(), 80 // TODO: 优化free_limit的计算: https://bbs.dragonos.org.cn/t/topic/358 81 free_limit: 2 * obj_per_page, 82 free_obj_count: 0, 83 } 84 }}; 85 } 86 87 impl<'a, P: AllocablePage> SCAllocator<'a, P> { 88 const REBALANCE_COUNT: usize = 64; 89 90 /// Create a new SCAllocator. 91 #[cfg(feature = "unstable")] 92 pub const fn new(size: usize) -> SCAllocator<'a, P> { 93 new_sc_allocator!(size) 94 } 95 96 #[cfg(not(feature = "unstable"))] 97 pub fn new(size: usize) -> SCAllocator<'a, P> { 98 new_sc_allocator!(size) 99 } 100 101 /// Returns the maximum supported object size of this allocator. 102 pub fn size(&self) -> usize { 103 self.size 104 } 105 106 /// Add a new ObjectPage. 107 fn insert_partial_slab(&mut self, new_head: &'a mut P) { 108 self.slabs.insert_front(new_head); 109 } 110 111 /// Add page to empty list. 112 fn insert_empty(&mut self, new_head: &'a mut P) { 113 assert_eq!( 114 new_head as *const P as usize % P::SIZE, 115 0, 116 "Inserted page is not aligned to page-size." 117 ); 118 self.empty_slabs.insert_front(new_head); 119 } 120 121 /// Since `dealloc` can not reassign pages without requiring a lock 122 /// we check slabs and full slabs periodically as part of `alloc` 123 /// and move them to the empty or partially allocated slab lists. 124 pub(crate) fn check_page_assignments(&mut self) { 125 for slab_page in self.full_slabs.iter_mut() { 126 if !slab_page.is_full() { 127 // We need to move it from self.full_slabs -> self.slabs 128 trace!("move {:p} full -> partial", slab_page); 129 self.move_full_to_partial(slab_page); 130 } 131 } 132 133 for slab_page in self.slabs.iter_mut() { 134 if slab_page.is_empty(self.obj_per_page) { 135 // We need to move it from self.slabs -> self.empty_slabs 136 trace!("move {:p} partial -> empty", slab_page); 137 self.move_to_empty(slab_page); 138 } 139 } 140 } 141 142 /// Move a page from `slabs` to `empty_slabs`. 143 fn move_to_empty(&mut self, page: &'a mut P) { 144 let page_ptr = page as *const P; 145 146 debug_assert!(self.slabs.contains(page_ptr)); 147 debug_assert!( 148 !self.empty_slabs.contains(page_ptr), 149 "Page {:p} already in emtpy_slabs", 150 page_ptr 151 ); 152 153 self.slabs.remove_from_list(page); 154 self.empty_slabs.insert_front(page); 155 156 debug_assert!(!self.slabs.contains(page_ptr)); 157 debug_assert!(self.empty_slabs.contains(page_ptr)); 158 } 159 160 /// Move a page from `full_slabs` to `slab`. 161 fn move_partial_to_full(&mut self, page: &'a mut P) { 162 let page_ptr = page as *const P; 163 164 debug_assert!(self.slabs.contains(page_ptr)); 165 debug_assert!(!self.full_slabs.contains(page_ptr)); 166 167 self.slabs.remove_from_list(page); 168 self.full_slabs.insert_front(page); 169 170 debug_assert!(!self.slabs.contains(page_ptr)); 171 debug_assert!(self.full_slabs.contains(page_ptr)); 172 } 173 174 /// Move a page from `full_slabs` to `slab`. 175 fn move_full_to_partial(&mut self, page: &'a mut P) { 176 let page_ptr = page as *const P; 177 178 debug_assert!(!self.slabs.contains(page_ptr)); 179 debug_assert!(self.full_slabs.contains(page_ptr)); 180 181 self.full_slabs.remove_from_list(page); 182 self.slabs.insert_front(page); 183 184 debug_assert!(self.slabs.contains(page_ptr)); 185 debug_assert!(!self.full_slabs.contains(page_ptr)); 186 } 187 188 /// Tries to allocate a block of memory with respect to the `layout`. 189 /// Searches within already allocated slab pages, if no suitable spot is found 190 /// will try to use a page from the empty page list. 191 /// 192 /// # Arguments 193 /// * `sc_layout`: This is not the original layout but adjusted for the 194 /// SCAllocator size (>= original). 195 fn try_allocate_from_pagelist(&mut self, sc_layout: Layout) -> *mut u8 { 196 // TODO: Do we really need to check multiple slab pages (due to alignment) 197 // If not we can get away with a singly-linked list and have 8 more bytes 198 // for the bitfield in an ObjectPage. 199 200 for slab_page in self.slabs.iter_mut() { 201 let ptr = slab_page.allocate(sc_layout); 202 if !ptr.is_null() { 203 if slab_page.is_full() { 204 trace!("move {:p} partial -> full", slab_page); 205 self.move_partial_to_full(slab_page); 206 } 207 self.allocation_count += 1; 208 return ptr; 209 } else { 210 continue; 211 } 212 } 213 214 // Periodically rebalance page-lists (since dealloc can't do it for us) 215 if self.allocation_count > SCAllocator::<P>::REBALANCE_COUNT { 216 self.check_page_assignments(); 217 self.allocation_count = 0; 218 } 219 220 ptr::null_mut() 221 } 222 223 pub fn try_reclaim_pages<F>(&mut self, to_reclaim: usize, dealloc: &mut F) -> usize 224 where 225 F: FnMut(*mut P), 226 { 227 self.check_page_assignments(); 228 let mut reclaimed = 0; 229 while reclaimed < to_reclaim { 230 if let Some(page) = self.empty_slabs.pop() { 231 dealloc(page as *mut P); 232 reclaimed += 1; 233 } else { 234 break; 235 } 236 } 237 238 reclaimed 239 } 240 241 /// Refill the SCAllocator 242 /// 243 /// # Safety 244 /// ObjectPage needs to be empty etc. 245 pub unsafe fn refill(&mut self, page: &'a mut P) { 246 page.bitfield_mut() 247 .initialize(self.size, P::SIZE - OBJECT_PAGE_METADATA_OVERHEAD); 248 *page.prev() = Rawlink::none(); 249 *page.next() = Rawlink::none(); 250 trace!("adding page to SCAllocator {:p}", page); 251 self.insert_empty(page); 252 self.free_obj_count += self.obj_per_page; 253 } 254 255 /// Allocates a block of memory descriped by `layout`. 256 /// 257 /// Returns a pointer to a valid region of memory or an 258 /// AllocationError. 259 /// 260 /// The function may also move around pages between lists 261 /// (empty -> partial or partial -> full). 262 pub fn allocate(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocationError> { 263 trace!( 264 "SCAllocator({}) is trying to allocate {:?}", 265 self.size, 266 layout 267 ); 268 assert!(layout.size() <= self.size); 269 assert!(self.size <= (P::SIZE - OBJECT_PAGE_METADATA_OVERHEAD)); 270 let new_layout = unsafe { Layout::from_size_align_unchecked(self.size, layout.align()) }; 271 assert!(new_layout.size() >= layout.size()); 272 273 let ptr = { 274 // Try to allocate from partial slabs, 275 // if we fail check if we have empty pages and allocate from there 276 let ptr = self.try_allocate_from_pagelist(new_layout); 277 if ptr.is_null() && self.empty_slabs.head.is_some() { 278 // Re-try allocation in empty page 279 let empty_page = self.empty_slabs.pop().expect("We checked head.is_some()"); 280 debug_assert!(!self.empty_slabs.contains(empty_page)); 281 282 let ptr = empty_page.allocate(layout); 283 debug_assert!(!ptr.is_null(), "Allocation must have succeeded here."); 284 285 trace!( 286 "move {:p} empty -> partial empty count {}", 287 empty_page, 288 self.empty_slabs.elements 289 ); 290 // Move empty page to partial pages 291 self.insert_partial_slab(empty_page); 292 ptr 293 } else { 294 ptr 295 } 296 }; 297 298 let res = NonNull::new(ptr).ok_or(AllocationError::OutOfMemory); 299 300 if !ptr.is_null() { 301 trace!( 302 "SCAllocator({}) allocated ptr=0x{:x}", 303 self.size, 304 ptr as usize 305 ); 306 self.free_obj_count -= 1; 307 } 308 309 res 310 } 311 312 /// Deallocates a previously allocated `ptr` described by `Layout`. 313 /// 314 /// May return an error in case an invalid `layout` is provided. 315 /// The function may also move internal slab pages between lists partial -> empty 316 /// or full -> partial lists. 317 pub unsafe fn deallocate( 318 &mut self, 319 ptr: NonNull<u8>, 320 layout: Layout, 321 slab_callback: &'static dyn CallBack, 322 ) -> Result<(), AllocationError> { 323 assert!(layout.size() <= self.size); 324 assert!(self.size <= (P::SIZE - OBJECT_PAGE_METADATA_OVERHEAD)); 325 trace!( 326 "SCAllocator({}) is trying to deallocate ptr = {:p} layout={:?} P.size= {}", 327 self.size, 328 ptr, 329 layout, 330 P::SIZE 331 ); 332 333 let page = (ptr.as_ptr() as usize) & !(P::SIZE - 1); 334 335 // Figure out which page we are on and construct a reference to it 336 // TODO: The linked list will have another &mut reference 337 let slab_page = unsafe { mem::transmute::<VAddr, &'a mut P>(page) }; 338 let new_layout = unsafe { Layout::from_size_align_unchecked(self.size, layout.align()) }; 339 340 let ret = slab_page.deallocate(ptr, new_layout); 341 debug_assert!(ret.is_ok(), "Slab page deallocate won't fail at the moment"); 342 self.free_obj_count += 1; 343 let is_empty_after_dealloc = slab_page.is_empty(self.obj_per_page); 344 345 // 如果slab_page是空白的，且空闲块数大于free_limit，将slab_page归还buddy 346 if self.free_obj_count >= self.free_limit && is_empty_after_dealloc { 347 self.slabs.remove_from_list(slab_page); 348 // 将slab_page归还buddy 349 slab_callback.free_slab_page(slab_page as *const P as *mut u8, P::SIZE); 350 } 351 self.check_page_assignments(); 352 353 ret 354 } 355 } 356