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