1 /// @Author: longjin@dragonos.org 2 /// @Author: kongweichao@dragonos.org 3 /// @Date: 2023-03-28 16:03:47 4 /// @FilePath: /DragonOS/kernel/src/mm/allocator/buddy.rs 5 /// @Description: 伙伴分配器 6 use crate::arch::MMArch; 7 use crate::mm::allocator::bump::BumpAllocator; 8 use crate::mm::allocator::page_frame::{FrameAllocator, PageFrameCount, PageFrameUsage}; 9 use crate::mm::{MemoryManagementArch, PhysAddr, VirtAddr}; 10 use crate::{kdebug, kerror, kwarn}; 11 use core::cmp::{max, min}; 12 use core::fmt::Debug; 13 use core::intrinsics::{likely, unlikely}; 14 15 use core::{marker::PhantomData, mem}; 16 17 // 一个全局变量MAX_ORDER,用来表示buddy算法的最大阶数 [MIN_ORDER, MAX_ORDER)左闭右开区间 18 const MAX_ORDER: usize = 31; 19 // 4KB 20 const MIN_ORDER: usize = 12; 21 22 /// 保存buddy算法中每一页存放的BuddyEntry的信息,占据每个页的起始位置 23 #[derive(Debug)] 24 pub struct PageList<A> { 25 // 页存放entry的数量 26 entry_num: usize, 27 // 下一个页面的地址 28 next_page: PhysAddr, 29 phantom: PhantomData<A>, 30 } 31 32 impl<A> Clone for PageList<A> { 33 fn clone(&self) -> Self { 34 Self { 35 entry_num: self.entry_num, 36 next_page: self.next_page, 37 phantom: PhantomData, 38 } 39 } 40 } 41 42 impl<A> PageList<A> { 43 #[allow(dead_code)] 44 fn empty() -> Self { 45 Self { 46 entry_num: 0, 47 next_page: PhysAddr::new(0), 48 phantom: PhantomData, 49 } 50 } 51 fn new(entry_num: usize, next_page: PhysAddr) -> Self { 52 Self { 53 entry_num, 54 next_page, 55 phantom: PhantomData, 56 } 57 } 58 } 59 60 /// @brief: 用来表示 buddy 算法中的一个 buddy 块,整体存放在area的头部 61 // 这种方式会出现对齐问题 62 // #[repr(packed)] 63 #[repr(C)] 64 #[derive(Debug)] 65 pub struct BuddyAllocator<A> { 66 // 存放每个阶的空闲“链表”的头部地址 67 free_area: [PhysAddr; (MAX_ORDER - MIN_ORDER) as usize], 68 phantom: PhantomData<A>, 69 } 70 71 impl<A: MemoryManagementArch> BuddyAllocator<A> { 72 const BUDDY_ENTRIES: usize = 73 // 定义一个变量记录buddy表的大小 74 (A::PAGE_SIZE - mem::size_of::<PageList<A>>()) / mem::size_of::<PhysAddr>(); 75 76 pub unsafe fn new(mut bump_allocator: BumpAllocator<A>) -> Option<Self> { 77 let initial_free_pages = bump_allocator.usage().free(); 78 kdebug!("Free pages before init buddy: {:?}", initial_free_pages); 79 kdebug!("Buddy entries: {}", Self::BUDDY_ENTRIES); 80 // 最高阶的链表页数 81 let max_order_linked_list_page_num = max( 82 1, 83 (((initial_free_pages.data() * A::PAGE_SIZE) >> (MAX_ORDER - 1)) + Self::BUDDY_ENTRIES 84 - 1) 85 / Self::BUDDY_ENTRIES, 86 ); 87 88 let mut free_area: [PhysAddr; (MAX_ORDER - MIN_ORDER) as usize] = 89 [PhysAddr::new(0); (MAX_ORDER - MIN_ORDER) as usize]; 90 91 // Buddy初始占用的空间从bump分配 92 for f in free_area.iter_mut() { 93 let curr_page = bump_allocator.allocate_one(); 94 // 保存每个阶的空闲链表的头部地址 95 *f = curr_page.unwrap(); 96 // 清空当前页 97 core::ptr::write_bytes(MMArch::phys_2_virt(*f)?.data() as *mut u8, 0, A::PAGE_SIZE); 98 99 let page_list: PageList<A> = PageList::new(0, PhysAddr::new(0)); 100 Self::write_page(*f, page_list); 101 } 102 103 // 分配最高阶的链表页 104 for _ in 1..max_order_linked_list_page_num { 105 let curr_page = bump_allocator.allocate_one().unwrap(); 106 // 清空当前页 107 core::ptr::write_bytes( 108 MMArch::phys_2_virt(curr_page)?.data() as *mut u8, 109 0, 110 A::PAGE_SIZE, 111 ); 112 113 let page_list: PageList<A> = 114 PageList::new(0, free_area[Self::order2index((MAX_ORDER - 1) as u8)]); 115 Self::write_page(curr_page, page_list); 116 free_area[Self::order2index((MAX_ORDER - 1) as u8)] = curr_page; 117 } 118 119 let initial_bump_offset = bump_allocator.offset(); 120 let pages_to_buddy = bump_allocator.usage().free(); 121 kdebug!("pages_to_buddy {:?}", pages_to_buddy); 122 // kdebug!("initial_bump_offset {:#x}", initial_bump_offset); 123 let mut paddr = initial_bump_offset; 124 let mut remain_pages = pages_to_buddy; 125 // 设置entry,这里假设了bump_allocator当前offset之后,所有的area的地址是连续的. 126 // TODO: 这里需要修改,按照area来处理 127 for i in MIN_ORDER..MAX_ORDER { 128 // kdebug!("i {i}, remain pages={}", remain_pages.data()); 129 if remain_pages.data() < (1 << (i - MIN_ORDER)) { 130 break; 131 } 132 133 assert!(paddr & ((1 << i) - 1) == 0); 134 135 if likely(i != MAX_ORDER - 1) { 136 // 要填写entry 137 if paddr & (1 << i) != 0 { 138 let page_list_paddr: PhysAddr = free_area[Self::order2index(i as u8)]; 139 let mut page_list: PageList<A> = Self::read_page(page_list_paddr); 140 141 A::write( 142 Self::entry_virt_addr(page_list_paddr, page_list.entry_num), 143 paddr, 144 ); 145 page_list.entry_num += 1; 146 Self::write_page(page_list_paddr, page_list); 147 148 paddr += 1 << i; 149 remain_pages -= 1 << (i - MIN_ORDER); 150 }; 151 } else { 152 // 往最大的阶数的链表中添加entry(注意要考虑到最大阶数的链表可能有多页) 153 // 断言剩余页面数量是MAX_ORDER-1阶的整数倍 154 155 let mut entries = (remain_pages.data() * A::PAGE_SIZE) >> i; 156 let mut page_list_paddr: PhysAddr = free_area[Self::order2index(i as u8)]; 157 let block_size = 1usize << i; 158 159 if entries > Self::BUDDY_ENTRIES { 160 // 在第一页填写一些entries 161 let num = entries % Self::BUDDY_ENTRIES; 162 entries -= num; 163 164 let mut page_list: PageList<A> = Self::read_page(page_list_paddr); 165 for _j in 0..num { 166 A::write( 167 Self::entry_virt_addr(page_list_paddr, page_list.entry_num), 168 paddr, 169 ); 170 page_list.entry_num += 1; 171 paddr += block_size; 172 remain_pages -= 1 << (i - MIN_ORDER); 173 } 174 page_list_paddr = page_list.next_page; 175 Self::write_page(page_list_paddr, page_list); 176 assert!(!page_list_paddr.is_null()); 177 } 178 179 while entries > 0 { 180 let mut page_list: PageList<A> = Self::read_page(page_list_paddr); 181 182 for _ in 0..Self::BUDDY_ENTRIES { 183 A::write( 184 Self::entry_virt_addr(page_list_paddr, page_list.entry_num), 185 paddr, 186 ); 187 page_list.entry_num += 1; 188 paddr += block_size; 189 remain_pages -= 1 << (i - MIN_ORDER); 190 entries -= 1; 191 if entries == 0 { 192 break; 193 } 194 } 195 page_list_paddr = page_list.next_page; 196 Self::write_page(page_list_paddr, page_list); 197 198 if likely(entries > 0) { 199 assert!(!page_list_paddr.is_null()); 200 } 201 } 202 } 203 } 204 205 let mut remain_bytes = remain_pages.data() * A::PAGE_SIZE; 206 207 assert!(remain_bytes < (1 << MAX_ORDER - 1)); 208 209 for i in (MIN_ORDER..MAX_ORDER).rev() { 210 if remain_bytes & (1 << i) != 0 { 211 let page_list_paddr: PhysAddr = free_area[Self::order2index(i as u8)]; 212 let mut page_list: PageList<A> = Self::read_page(page_list_paddr); 213 214 A::write( 215 Self::entry_virt_addr(page_list_paddr, page_list.entry_num), 216 paddr, 217 ); 218 page_list.entry_num += 1; 219 Self::write_page(page_list_paddr, page_list); 220 221 paddr += 1 << i; 222 remain_bytes -= 1 << i; 223 } 224 } 225 226 assert!(remain_bytes == 0); 227 assert!(paddr == initial_bump_offset + pages_to_buddy.data() * A::PAGE_SIZE); 228 229 // Self::print_free_area(free_area); 230 let allocator = Self { 231 free_area, 232 phantom: PhantomData, 233 }; 234 235 Some(allocator) 236 } 237 /// 获取第j个entry的虚拟地址, 238 /// j从0开始计数 239 pub fn entry_virt_addr(base_addr: PhysAddr, j: usize) -> VirtAddr { 240 let entry_virt_addr = unsafe { A::phys_2_virt(Self::entry_addr(base_addr, j)) }; 241 return entry_virt_addr.unwrap(); 242 } 243 pub fn entry_addr(base_addr: PhysAddr, j: usize) -> PhysAddr { 244 let entry_addr = base_addr + mem::size_of::<PageList<A>>() + j * mem::size_of::<PhysAddr>(); 245 return entry_addr; 246 } 247 pub fn read_page<T>(addr: PhysAddr) -> T { 248 let page_list = unsafe { A::read(A::phys_2_virt(addr).unwrap()) }; 249 return page_list; 250 } 251 252 pub fn write_page(curr_page: PhysAddr, page_list: PageList<A>) { 253 // 把物理地址转换为虚拟地址 254 let virt_addr = unsafe { A::phys_2_virt(curr_page) }; 255 let virt_addr = virt_addr.unwrap(); 256 unsafe { A::write(virt_addr, page_list) }; 257 } 258 259 /// 从order转换为free_area的下标 260 /// 261 /// # 参数 262 /// 263 /// - `order` - order 264 /// 265 /// # 返回值 266 /// 267 /// free_area的下标 268 #[inline] 269 fn order2index(order: u8) -> usize { 270 (order as usize - MIN_ORDER) as usize 271 } 272 273 /// 从空闲链表的开头,取出1个指定阶数的伙伴块,如果没有,则返回None 274 /// 275 /// ## 参数 276 /// 277 /// - `order` - 伙伴块的阶数 278 fn pop_front(&mut self, order: u8) -> Option<PhysAddr> { 279 let mut alloc_in_specific_order = |spec_order: u8| { 280 // 先尝试在order阶的“空闲链表”的开头位置分配一个伙伴块 281 let mut page_list_addr = self.free_area[Self::order2index(spec_order)]; 282 let mut page_list: PageList<A> = Self::read_page(page_list_addr); 283 284 // kdebug!("page_list={page_list:?}"); 285 286 // 循环删除头部的空闲链表页 287 while page_list.entry_num == 0 { 288 let next_page_list_addr = page_list.next_page; 289 // 找完了,都是空的 290 if next_page_list_addr.is_null() { 291 return None; 292 } 293 294 if !next_page_list_addr.is_null() { 295 // 此时page_list已经没有空闲伙伴块了,又因为非唯一页,需要删除该page_list 296 self.free_area[Self::order2index(spec_order)] = next_page_list_addr; 297 drop(page_list); 298 // kdebug!("FREE: page_list_addr={:b}", page_list_addr.data()); 299 unsafe { 300 self.buddy_free(page_list_addr, MMArch::PAGE_SHIFT as u8); 301 } 302 } 303 // 由于buddy_free可能导致首部的链表页发生变化,因此需要重新读取 304 let next_page_list_addr = self.free_area[Self::order2index(spec_order)]; 305 assert!(!next_page_list_addr.is_null()); 306 page_list = Self::read_page(next_page_list_addr); 307 page_list_addr = next_page_list_addr; 308 } 309 310 // 有空闲页面,直接分配 311 if page_list.entry_num > 0 { 312 let entry: PhysAddr = unsafe { 313 A::read(Self::entry_virt_addr( 314 page_list_addr, 315 page_list.entry_num - 1, 316 )) 317 }; 318 if entry.is_null() { 319 kerror!( 320 "entry is null, entry={:?}, order={}, entry_num = {}", 321 entry, 322 spec_order, 323 page_list.entry_num - 1 324 ); 325 } 326 // kdebug!("entry={entry:?}"); 327 // 更新page_list的entry_num 328 page_list.entry_num -= 1; 329 let tmp_current_entry_num = page_list.entry_num; 330 if page_list.entry_num == 0 { 331 if !page_list.next_page.is_null() { 332 // 此时page_list已经没有空闲伙伴块了,又因为非唯一页,需要删除该page_list 333 self.free_area[Self::order2index(spec_order)] = page_list.next_page; 334 drop(page_list); 335 unsafe { self.buddy_free(page_list_addr, MMArch::PAGE_SHIFT as u8) }; 336 } else { 337 Self::write_page(page_list_addr, page_list); 338 } 339 } else { 340 // 若entry_num不为0,说明该page_list还有空闲伙伴块,需要更新该page_list 341 // 把更新后的page_list写回 342 Self::write_page(page_list_addr, page_list.clone()); 343 } 344 345 // 检测entry 是否对齐 346 if !entry.check_aligned(1 << spec_order) { 347 panic!("entry={:?} is not aligned, spec_order={spec_order}, page_list.entry_num={}", entry,tmp_current_entry_num); 348 } 349 return Some(entry); 350 } 351 return None; 352 }; 353 354 let result: Option<PhysAddr> = alloc_in_specific_order(order as u8); 355 // kdebug!("result={:?}", result); 356 if result.is_some() { 357 return result; 358 } 359 // 尝试从更大的链表中分裂 360 361 let mut current_order = (order + 1) as usize; 362 let mut x: Option<PhysAddr> = None; 363 while current_order < MAX_ORDER { 364 x = alloc_in_specific_order(current_order as u8); 365 // kdebug!("current_order={:?}", current_order); 366 if x.is_some() { 367 break; 368 } 369 current_order += 1; 370 } 371 372 // kdebug!("x={:?}", x); 373 // 如果找到一个大的块,就进行分裂 374 if x.is_some() { 375 // 分裂到order阶 376 while current_order > order as usize { 377 current_order -= 1; 378 // 把后面那半块放回空闲链表 379 380 let buddy = *x.as_ref().unwrap() + (1 << current_order); 381 // kdebug!("x={:?}, buddy={:?}", x, buddy); 382 // kdebug!("current_order={:?}, buddy={:?}", current_order, buddy); 383 unsafe { self.buddy_free(buddy, current_order as u8) }; 384 } 385 return x; 386 } 387 388 return None; 389 } 390 391 /// 从伙伴系统中分配count个页面 392 /// 393 /// ## 参数 394 /// 395 /// - `count`:需要分配的页面数 396 /// 397 /// ## 返回值 398 /// 399 /// 返回分配的页面的物理地址和页面数 400 fn buddy_alloc(&mut self, count: PageFrameCount) -> Option<(PhysAddr, PageFrameCount)> { 401 assert!(count.data().is_power_of_two()); 402 // 计算需要分配的阶数 403 let mut order = log2(count.data() as usize); 404 if count.data() & ((1 << order) - 1) != 0 { 405 order += 1; 406 } 407 let order = (order + MIN_ORDER) as u8; 408 if order as usize >= MAX_ORDER { 409 return None; 410 } 411 412 // kdebug!("buddy_alloc: order = {}", order); 413 // 获取该阶数的一个空闲页面 414 let free_addr = self.pop_front(order); 415 // kdebug!( 416 // "buddy_alloc: order = {}, free_addr = {:?}", 417 // order, 418 // free_addr 419 // ); 420 return free_addr 421 .map(|addr| (addr, PageFrameCount::new(1 << (order as usize - MIN_ORDER)))); 422 } 423 424 /// 释放一个块 425 /// 426 /// ## 参数 427 /// 428 /// - `base` - 块的起始地址 429 /// - `order` - 块的阶数 430 unsafe fn buddy_free(&mut self, mut base: PhysAddr, order: u8) { 431 // kdebug!("buddy_free: base = {:?}, order = {}", base, order); 432 let mut order = order as usize; 433 434 while order < MAX_ORDER { 435 // 检测地址是否合法 436 if base.data() & ((1 << (order)) - 1) != 0 { 437 panic!( 438 "buddy_free: base is not aligned, base = {:#x}, order = {}", 439 base.data(), 440 order 441 ); 442 } 443 444 // 在链表中寻找伙伴块 445 // 伙伴块的地址是base ^ (1 << order) 446 let buddy_addr = PhysAddr::new(base.data() ^ (1 << order)); 447 448 let first_page_list_paddr = self.free_area[Self::order2index(order as u8)]; 449 let mut page_list_paddr = first_page_list_paddr; 450 let mut page_list: PageList<A> = Self::read_page(page_list_paddr); 451 let first_page_list = page_list.clone(); 452 453 let mut buddy_entry_virt_vaddr = None; 454 let mut buddy_entry_page_list_paddr = None; 455 // 除非order是最大的,否则尝试查找伙伴块 456 if likely(order != MAX_ORDER - 1) { 457 'outer: loop { 458 for i in 0..page_list.entry_num { 459 let entry_virt_addr = Self::entry_virt_addr(page_list_paddr, i); 460 let entry: PhysAddr = unsafe { A::read(entry_virt_addr) }; 461 if entry == buddy_addr { 462 // 找到了伙伴块,记录该entry相关信息,然后退出查找 463 buddy_entry_virt_vaddr = Some(entry_virt_addr); 464 buddy_entry_page_list_paddr = Some(page_list_paddr); 465 break 'outer; 466 } 467 } 468 if page_list.next_page.is_null() { 469 break; 470 } 471 page_list_paddr = page_list.next_page; 472 page_list = Self::read_page(page_list_paddr); 473 } 474 } 475 476 // 如果没有找到伙伴块 477 if buddy_entry_virt_vaddr.is_none() { 478 assert!( 479 page_list.entry_num <= Self::BUDDY_ENTRIES, 480 "buddy_free: page_list.entry_num > Self::BUDDY_ENTRIES" 481 ); 482 483 // 当前第一个page_list没有空间了 484 if first_page_list.entry_num == Self::BUDDY_ENTRIES { 485 // 如果当前order是最小的,那么就把这个块当作新的page_list使用 486 let new_page_list_addr = if order == MIN_ORDER { 487 base 488 } else { 489 // 否则分配新的page_list 490 // 请注意,分配之后,有可能当前的entry_num会减1(伙伴块分裂),造成出现整个链表为null的entry数量为Self::BUDDY_ENTRIES+1的情况 491 // 但是不影响,我们在后面插入链表项的时候,会处理这种情况,检查链表中的第2个页是否有空位 492 self.buddy_alloc(PageFrameCount::new(1)) 493 .expect("buddy_alloc failed: no enough memory") 494 .0 495 }; 496 497 // 清空这个页面 498 core::ptr::write_bytes( 499 A::phys_2_virt(new_page_list_addr) 500 .expect( 501 "Buddy free: failed to get virt address of [new_page_list_addr]", 502 ) 503 .as_ptr::<u8>(), 504 0, 505 1 << order, 506 ); 507 assert!( 508 first_page_list_paddr == self.free_area[Self::order2index(order as u8)] 509 ); 510 // 初始化新的page_list 511 let new_page_list = PageList::new(0, first_page_list_paddr); 512 Self::write_page(new_page_list_addr, new_page_list); 513 self.free_area[Self::order2index(order as u8)] = new_page_list_addr; 514 } 515 516 // 由于上面可能更新了第一个链表页,因此需要重新获取这个值 517 let first_page_list_paddr = self.free_area[Self::order2index(order as u8)]; 518 let first_page_list: PageList<A> = Self::read_page(first_page_list_paddr); 519 520 // 检查第二个page_list是否有空位 521 let second_page_list = if first_page_list.next_page.is_null() { 522 None 523 } else { 524 Some(Self::read_page::<PageList<A>>(first_page_list.next_page)) 525 }; 526 527 let (paddr, mut page_list) = if let Some(second) = second_page_list { 528 // 第二个page_list有空位 529 // 应当符合之前的假设:还有1个空位 530 assert!(second.entry_num == Self::BUDDY_ENTRIES - 1); 531 532 (first_page_list.next_page, second) 533 } else { 534 // 在第一个page list中分配 535 (first_page_list_paddr, first_page_list) 536 }; 537 538 // kdebug!("to write entry, page_list_base={paddr:?}, page_list.entry_num={}, value={base:?}", page_list.entry_num); 539 assert!(page_list.entry_num < Self::BUDDY_ENTRIES); 540 // 把要归还的块,写入到链表项中 541 unsafe { A::write(Self::entry_virt_addr(paddr, page_list.entry_num), base) } 542 page_list.entry_num += 1; 543 Self::write_page(paddr, page_list); 544 return; 545 } else { 546 // 如果找到了伙伴块,合并,向上递归 547 548 // 伙伴块所在的表项的虚拟地址 549 let buddy_entry_virt_addr = buddy_entry_virt_vaddr.unwrap(); 550 // 伙伴块所在的page_list的物理地址 551 let buddy_entry_page_list_paddr = buddy_entry_page_list_paddr.unwrap(); 552 553 let mut page_list_paddr = self.free_area[Self::order2index(order as u8)]; 554 let mut page_list = Self::read_page::<PageList<A>>(page_list_paddr); 555 // 找第一个有空闲块的链表页。跳过空闲链表页。不进行回收的原因是担心出现死循环 556 while page_list.entry_num == 0 { 557 if page_list.next_page.is_null() { 558 panic!( 559 "buddy_free: page_list.entry_num == 0 && page_list.next_page.is_null()" 560 ); 561 } 562 page_list_paddr = page_list.next_page; 563 page_list = Self::read_page(page_list_paddr); 564 } 565 566 // 如果伙伴块不在第一个链表页,则把第一个链表中的某个空闲块替换到伙伴块的位置 567 if page_list_paddr != buddy_entry_page_list_paddr { 568 let entry: PhysAddr = unsafe { 569 A::read(Self::entry_virt_addr( 570 page_list_paddr, 571 page_list.entry_num - 1, 572 )) 573 }; 574 // 把这个空闲块写入到伙伴块的位置 575 unsafe { 576 A::write(buddy_entry_virt_addr, entry); 577 } 578 // 设置刚才那个entry为空 579 unsafe { 580 A::write( 581 Self::entry_virt_addr(page_list_paddr, page_list.entry_num - 1), 582 PhysAddr::new(0), 583 ); 584 } 585 // 更新当前链表页的统计数据 586 page_list.entry_num -= 1; 587 Self::write_page(page_list_paddr, page_list); 588 } else { 589 // 伙伴块所在的链表页就是第一个链表页 590 let last_entry: PhysAddr = unsafe { 591 A::read(Self::entry_virt_addr( 592 page_list_paddr, 593 page_list.entry_num - 1, 594 )) 595 }; 596 597 // 如果最后一个空闲块不是伙伴块,则把最后一个空闲块移动到伙伴块的位置 598 // 否则后面的操作也将删除这个伙伴块 599 if last_entry != buddy_addr { 600 unsafe { 601 A::write(buddy_entry_virt_addr, last_entry); 602 A::write( 603 Self::entry_virt_addr(page_list_paddr, page_list.entry_num - 1), 604 PhysAddr::new(0), 605 ); 606 } 607 } else { 608 unsafe { 609 A::write( 610 Self::entry_virt_addr(page_list_paddr, page_list.entry_num - 1), 611 PhysAddr::new(0), 612 ); 613 } 614 } 615 // 更新当前链表页的统计数据 616 page_list.entry_num -= 1; 617 Self::write_page(page_list_paddr, page_list); 618 } 619 } 620 base = min(base, buddy_addr); 621 order += 1; 622 } 623 // 走到这一步,order应该为MAX_ORDER-1 624 assert!(order == MAX_ORDER - 1); 625 } 626 } 627 628 impl<A: MemoryManagementArch> FrameAllocator for BuddyAllocator<A> { 629 unsafe fn allocate(&mut self, count: PageFrameCount) -> Option<(PhysAddr, PageFrameCount)> { 630 return self.buddy_alloc(count); 631 } 632 633 /// 释放一个块 634 /// 635 /// ## 参数 636 /// 637 /// - `base` - 块的起始地址 638 /// - `count` - 块的页数(必须是2的幂) 639 /// 640 /// ## Panic 641 /// 642 /// 如果count不是2的幂,会panic 643 unsafe fn free(&mut self, base: PhysAddr, count: PageFrameCount) { 644 // 要求count是2的幂 645 if unlikely(!count.data().is_power_of_two()) { 646 kwarn!("buddy free: count is not power of two"); 647 } 648 let mut order = log2(count.data() as usize); 649 if count.data() & ((1 << order) - 1) != 0 { 650 order += 1; 651 } 652 let order = (order + MIN_ORDER) as u8; 653 // kdebug!("free: base={:?}, count={:?}", base, count); 654 self.buddy_free(base, order); 655 } 656 657 unsafe fn usage(&self) -> PageFrameUsage { 658 todo!("BuddyAllocator::usage") 659 } 660 } 661 662 /// 一个用于计算整数的对数的函数,会向下取整。(由于内核不能进行浮点运算,因此需要这个函数) 663 fn log2(x: usize) -> usize { 664 let leading_zeros = x.leading_zeros() as usize; 665 let log2x = 63 - leading_zeros; 666 return log2x; 667 } 668