140fe15e0SLoGin /// @Author: longjin@dragonos.org 240fe15e0SLoGin /// @Author: kongweichao@dragonos.org 340fe15e0SLoGin /// @Date: 2023-03-28 16:03:47 440fe15e0SLoGin /// @FilePath: /DragonOS/kernel/src/mm/allocator/buddy.rs 540fe15e0SLoGin /// @Description: 伙伴分配器 640fe15e0SLoGin use crate::arch::MMArch; 740fe15e0SLoGin use crate::mm::allocator::bump::BumpAllocator; 840fe15e0SLoGin use crate::mm::allocator::page_frame::{FrameAllocator, PageFrameCount, PageFrameUsage}; 940fe15e0SLoGin use crate::mm::{MemoryManagementArch, PhysAddr, VirtAddr}; 1026887c63SLoGin use crate::{kdebug, kwarn}; 1140fe15e0SLoGin use core::cmp::{max, min}; 1240fe15e0SLoGin use core::fmt::Debug; 1340fe15e0SLoGin use core::intrinsics::{likely, unlikely}; 1440fe15e0SLoGin 1540fe15e0SLoGin use core::{marker::PhantomData, mem}; 1640fe15e0SLoGin 1740fe15e0SLoGin // 一个全局变量MAX_ORDER,用来表示buddy算法的最大阶数 [MIN_ORDER, MAX_ORDER)左闭右开区间 1840fe15e0SLoGin const MAX_ORDER: usize = 31; 1940fe15e0SLoGin // 4KB 2040fe15e0SLoGin const MIN_ORDER: usize = 12; 2140fe15e0SLoGin 2240fe15e0SLoGin /// 保存buddy算法中每一页存放的BuddyEntry的信息,占据每个页的起始位置 2340fe15e0SLoGin #[derive(Debug)] 2440fe15e0SLoGin pub struct PageList<A> { 2540fe15e0SLoGin // 页存放entry的数量 2640fe15e0SLoGin entry_num: usize, 2740fe15e0SLoGin // 下一个页面的地址 2840fe15e0SLoGin next_page: PhysAddr, 2940fe15e0SLoGin phantom: PhantomData<A>, 3040fe15e0SLoGin } 3140fe15e0SLoGin 3240fe15e0SLoGin impl<A> Clone for PageList<A> { 3340fe15e0SLoGin fn clone(&self) -> Self { 3440fe15e0SLoGin Self { 3540fe15e0SLoGin entry_num: self.entry_num, 3640fe15e0SLoGin next_page: self.next_page, 3740fe15e0SLoGin phantom: PhantomData, 3840fe15e0SLoGin } 3940fe15e0SLoGin } 4040fe15e0SLoGin } 4140fe15e0SLoGin 4240fe15e0SLoGin impl<A> PageList<A> { 4340fe15e0SLoGin #[allow(dead_code)] 4440fe15e0SLoGin fn empty() -> Self { 4540fe15e0SLoGin Self { 4640fe15e0SLoGin entry_num: 0, 4740fe15e0SLoGin next_page: PhysAddr::new(0), 4840fe15e0SLoGin phantom: PhantomData, 4940fe15e0SLoGin } 5040fe15e0SLoGin } 5140fe15e0SLoGin fn new(entry_num: usize, next_page: PhysAddr) -> Self { 5240fe15e0SLoGin Self { 5340fe15e0SLoGin entry_num, 5440fe15e0SLoGin next_page, 5540fe15e0SLoGin phantom: PhantomData, 5640fe15e0SLoGin } 5740fe15e0SLoGin } 5840fe15e0SLoGin } 5940fe15e0SLoGin 6040fe15e0SLoGin /// @brief: 用来表示 buddy 算法中的一个 buddy 块,整体存放在area的头部 6140fe15e0SLoGin // 这种方式会出现对齐问题 6240fe15e0SLoGin // #[repr(packed)] 6340fe15e0SLoGin #[repr(C)] 6440fe15e0SLoGin #[derive(Debug)] 6540fe15e0SLoGin pub struct BuddyAllocator<A> { 6640fe15e0SLoGin // 存放每个阶的空闲“链表”的头部地址 6740fe15e0SLoGin free_area: [PhysAddr; (MAX_ORDER - MIN_ORDER) as usize], 68*34e6d6c8Syuyi2439 /// 总页数 69*34e6d6c8Syuyi2439 total: PageFrameCount, 7040fe15e0SLoGin phantom: PhantomData<A>, 7140fe15e0SLoGin } 7240fe15e0SLoGin 7340fe15e0SLoGin impl<A: MemoryManagementArch> BuddyAllocator<A> { 7440fe15e0SLoGin const BUDDY_ENTRIES: usize = 7540fe15e0SLoGin // 定义一个变量记录buddy表的大小 7640fe15e0SLoGin (A::PAGE_SIZE - mem::size_of::<PageList<A>>()) / mem::size_of::<PhysAddr>(); 7740fe15e0SLoGin 7840fe15e0SLoGin pub unsafe fn new(mut bump_allocator: BumpAllocator<A>) -> Option<Self> { 7940fe15e0SLoGin let initial_free_pages = bump_allocator.usage().free(); 8040fe15e0SLoGin kdebug!("Free pages before init buddy: {:?}", initial_free_pages); 8140fe15e0SLoGin kdebug!("Buddy entries: {}", Self::BUDDY_ENTRIES); 8240fe15e0SLoGin // 最高阶的链表页数 8340fe15e0SLoGin let max_order_linked_list_page_num = max( 8440fe15e0SLoGin 1, 8540fe15e0SLoGin (((initial_free_pages.data() * A::PAGE_SIZE) >> (MAX_ORDER - 1)) + Self::BUDDY_ENTRIES 8640fe15e0SLoGin - 1) 8740fe15e0SLoGin / Self::BUDDY_ENTRIES, 8840fe15e0SLoGin ); 8940fe15e0SLoGin 9040fe15e0SLoGin let mut free_area: [PhysAddr; (MAX_ORDER - MIN_ORDER) as usize] = 9140fe15e0SLoGin [PhysAddr::new(0); (MAX_ORDER - MIN_ORDER) as usize]; 9240fe15e0SLoGin 9340fe15e0SLoGin // Buddy初始占用的空间从bump分配 9440fe15e0SLoGin for f in free_area.iter_mut() { 9540fe15e0SLoGin let curr_page = bump_allocator.allocate_one(); 9640fe15e0SLoGin // 保存每个阶的空闲链表的头部地址 9740fe15e0SLoGin *f = curr_page.unwrap(); 9840fe15e0SLoGin // 清空当前页 9940fe15e0SLoGin core::ptr::write_bytes(MMArch::phys_2_virt(*f)?.data() as *mut u8, 0, A::PAGE_SIZE); 10040fe15e0SLoGin 10140fe15e0SLoGin let page_list: PageList<A> = PageList::new(0, PhysAddr::new(0)); 10240fe15e0SLoGin Self::write_page(*f, page_list); 10340fe15e0SLoGin } 10440fe15e0SLoGin 10540fe15e0SLoGin // 分配最高阶的链表页 10640fe15e0SLoGin for _ in 1..max_order_linked_list_page_num { 10740fe15e0SLoGin let curr_page = bump_allocator.allocate_one().unwrap(); 10840fe15e0SLoGin // 清空当前页 10940fe15e0SLoGin core::ptr::write_bytes( 11040fe15e0SLoGin MMArch::phys_2_virt(curr_page)?.data() as *mut u8, 11140fe15e0SLoGin 0, 11240fe15e0SLoGin A::PAGE_SIZE, 11340fe15e0SLoGin ); 11440fe15e0SLoGin 11540fe15e0SLoGin let page_list: PageList<A> = 11640fe15e0SLoGin PageList::new(0, free_area[Self::order2index((MAX_ORDER - 1) as u8)]); 11740fe15e0SLoGin Self::write_page(curr_page, page_list); 11840fe15e0SLoGin free_area[Self::order2index((MAX_ORDER - 1) as u8)] = curr_page; 11940fe15e0SLoGin } 12040fe15e0SLoGin 12140fe15e0SLoGin let initial_bump_offset = bump_allocator.offset(); 12240fe15e0SLoGin let pages_to_buddy = bump_allocator.usage().free(); 12340fe15e0SLoGin kdebug!("pages_to_buddy {:?}", pages_to_buddy); 12440fe15e0SLoGin // kdebug!("initial_bump_offset {:#x}", initial_bump_offset); 12540fe15e0SLoGin let mut paddr = initial_bump_offset; 12640fe15e0SLoGin let mut remain_pages = pages_to_buddy; 12740fe15e0SLoGin // 设置entry,这里假设了bump_allocator当前offset之后,所有的area的地址是连续的. 12840fe15e0SLoGin // TODO: 这里需要修改,按照area来处理 12940fe15e0SLoGin for i in MIN_ORDER..MAX_ORDER { 13040fe15e0SLoGin // kdebug!("i {i}, remain pages={}", remain_pages.data()); 13140fe15e0SLoGin if remain_pages.data() < (1 << (i - MIN_ORDER)) { 13240fe15e0SLoGin break; 13340fe15e0SLoGin } 13440fe15e0SLoGin 13540fe15e0SLoGin assert!(paddr & ((1 << i) - 1) == 0); 13640fe15e0SLoGin 13740fe15e0SLoGin if likely(i != MAX_ORDER - 1) { 13840fe15e0SLoGin // 要填写entry 13940fe15e0SLoGin if paddr & (1 << i) != 0 { 14040fe15e0SLoGin let page_list_paddr: PhysAddr = free_area[Self::order2index(i as u8)]; 14140fe15e0SLoGin let mut page_list: PageList<A> = Self::read_page(page_list_paddr); 14240fe15e0SLoGin 14340fe15e0SLoGin A::write( 14440fe15e0SLoGin Self::entry_virt_addr(page_list_paddr, page_list.entry_num), 14540fe15e0SLoGin paddr, 14640fe15e0SLoGin ); 14740fe15e0SLoGin page_list.entry_num += 1; 14840fe15e0SLoGin Self::write_page(page_list_paddr, page_list); 14940fe15e0SLoGin 15040fe15e0SLoGin paddr += 1 << i; 15140fe15e0SLoGin remain_pages -= 1 << (i - MIN_ORDER); 15240fe15e0SLoGin }; 15340fe15e0SLoGin } else { 15440fe15e0SLoGin // 往最大的阶数的链表中添加entry(注意要考虑到最大阶数的链表可能有多页) 15540fe15e0SLoGin // 断言剩余页面数量是MAX_ORDER-1阶的整数倍 15640fe15e0SLoGin 15740fe15e0SLoGin let mut entries = (remain_pages.data() * A::PAGE_SIZE) >> i; 15840fe15e0SLoGin let mut page_list_paddr: PhysAddr = free_area[Self::order2index(i as u8)]; 15940fe15e0SLoGin let block_size = 1usize << i; 16040fe15e0SLoGin 16140fe15e0SLoGin if entries > Self::BUDDY_ENTRIES { 16240fe15e0SLoGin // 在第一页填写一些entries 16340fe15e0SLoGin let num = entries % Self::BUDDY_ENTRIES; 16440fe15e0SLoGin entries -= num; 16540fe15e0SLoGin 16640fe15e0SLoGin let mut page_list: PageList<A> = Self::read_page(page_list_paddr); 16740fe15e0SLoGin for _j in 0..num { 16840fe15e0SLoGin A::write( 16940fe15e0SLoGin Self::entry_virt_addr(page_list_paddr, page_list.entry_num), 17040fe15e0SLoGin paddr, 17140fe15e0SLoGin ); 17240fe15e0SLoGin page_list.entry_num += 1; 17340fe15e0SLoGin paddr += block_size; 17440fe15e0SLoGin remain_pages -= 1 << (i - MIN_ORDER); 17540fe15e0SLoGin } 17640fe15e0SLoGin page_list_paddr = page_list.next_page; 17740fe15e0SLoGin Self::write_page(page_list_paddr, page_list); 17840fe15e0SLoGin assert!(!page_list_paddr.is_null()); 17940fe15e0SLoGin } 18040fe15e0SLoGin 18140fe15e0SLoGin while entries > 0 { 18240fe15e0SLoGin let mut page_list: PageList<A> = Self::read_page(page_list_paddr); 18340fe15e0SLoGin 18440fe15e0SLoGin for _ in 0..Self::BUDDY_ENTRIES { 18540fe15e0SLoGin A::write( 18640fe15e0SLoGin Self::entry_virt_addr(page_list_paddr, page_list.entry_num), 18740fe15e0SLoGin paddr, 18840fe15e0SLoGin ); 18940fe15e0SLoGin page_list.entry_num += 1; 19040fe15e0SLoGin paddr += block_size; 19140fe15e0SLoGin remain_pages -= 1 << (i - MIN_ORDER); 19240fe15e0SLoGin entries -= 1; 19340fe15e0SLoGin if entries == 0 { 19440fe15e0SLoGin break; 19540fe15e0SLoGin } 19640fe15e0SLoGin } 19740fe15e0SLoGin page_list_paddr = page_list.next_page; 19840fe15e0SLoGin Self::write_page(page_list_paddr, page_list); 19940fe15e0SLoGin 20040fe15e0SLoGin if likely(entries > 0) { 20140fe15e0SLoGin assert!(!page_list_paddr.is_null()); 20240fe15e0SLoGin } 20340fe15e0SLoGin } 20440fe15e0SLoGin } 20540fe15e0SLoGin } 20640fe15e0SLoGin 20740fe15e0SLoGin let mut remain_bytes = remain_pages.data() * A::PAGE_SIZE; 20840fe15e0SLoGin 20940fe15e0SLoGin assert!(remain_bytes < (1 << MAX_ORDER - 1)); 21040fe15e0SLoGin 21140fe15e0SLoGin for i in (MIN_ORDER..MAX_ORDER).rev() { 21226887c63SLoGin if remain_bytes >= (1 << i) { 21326887c63SLoGin assert!(paddr & ((1 << i) - 1) == 0); 21440fe15e0SLoGin let page_list_paddr: PhysAddr = free_area[Self::order2index(i as u8)]; 21540fe15e0SLoGin let mut page_list: PageList<A> = Self::read_page(page_list_paddr); 21640fe15e0SLoGin 21740fe15e0SLoGin A::write( 21840fe15e0SLoGin Self::entry_virt_addr(page_list_paddr, page_list.entry_num), 21940fe15e0SLoGin paddr, 22040fe15e0SLoGin ); 22140fe15e0SLoGin page_list.entry_num += 1; 22240fe15e0SLoGin Self::write_page(page_list_paddr, page_list); 22340fe15e0SLoGin 22440fe15e0SLoGin paddr += 1 << i; 22540fe15e0SLoGin remain_bytes -= 1 << i; 22640fe15e0SLoGin } 22740fe15e0SLoGin } 22840fe15e0SLoGin 22940fe15e0SLoGin assert!(remain_bytes == 0); 23040fe15e0SLoGin assert!(paddr == initial_bump_offset + pages_to_buddy.data() * A::PAGE_SIZE); 23140fe15e0SLoGin 23240fe15e0SLoGin let allocator = Self { 23340fe15e0SLoGin free_area, 234*34e6d6c8Syuyi2439 total: pages_to_buddy, 23540fe15e0SLoGin phantom: PhantomData, 23640fe15e0SLoGin }; 23740fe15e0SLoGin 23840fe15e0SLoGin Some(allocator) 23940fe15e0SLoGin } 24040fe15e0SLoGin /// 获取第j个entry的虚拟地址, 24140fe15e0SLoGin /// j从0开始计数 24240fe15e0SLoGin pub fn entry_virt_addr(base_addr: PhysAddr, j: usize) -> VirtAddr { 24340fe15e0SLoGin let entry_virt_addr = unsafe { A::phys_2_virt(Self::entry_addr(base_addr, j)) }; 24440fe15e0SLoGin return entry_virt_addr.unwrap(); 24540fe15e0SLoGin } 24640fe15e0SLoGin pub fn entry_addr(base_addr: PhysAddr, j: usize) -> PhysAddr { 24740fe15e0SLoGin let entry_addr = base_addr + mem::size_of::<PageList<A>>() + j * mem::size_of::<PhysAddr>(); 24840fe15e0SLoGin return entry_addr; 24940fe15e0SLoGin } 25040fe15e0SLoGin pub fn read_page<T>(addr: PhysAddr) -> T { 25140fe15e0SLoGin let page_list = unsafe { A::read(A::phys_2_virt(addr).unwrap()) }; 25240fe15e0SLoGin return page_list; 25340fe15e0SLoGin } 25440fe15e0SLoGin 25540fe15e0SLoGin pub fn write_page(curr_page: PhysAddr, page_list: PageList<A>) { 25640fe15e0SLoGin // 把物理地址转换为虚拟地址 25740fe15e0SLoGin let virt_addr = unsafe { A::phys_2_virt(curr_page) }; 25840fe15e0SLoGin let virt_addr = virt_addr.unwrap(); 25940fe15e0SLoGin unsafe { A::write(virt_addr, page_list) }; 26040fe15e0SLoGin } 26140fe15e0SLoGin 26240fe15e0SLoGin /// 从order转换为free_area的下标 26340fe15e0SLoGin /// 26440fe15e0SLoGin /// # 参数 26540fe15e0SLoGin /// 26640fe15e0SLoGin /// - `order` - order 26740fe15e0SLoGin /// 26840fe15e0SLoGin /// # 返回值 26940fe15e0SLoGin /// 27040fe15e0SLoGin /// free_area的下标 27140fe15e0SLoGin #[inline] 27240fe15e0SLoGin fn order2index(order: u8) -> usize { 27340fe15e0SLoGin (order as usize - MIN_ORDER) as usize 27440fe15e0SLoGin } 27540fe15e0SLoGin 27640fe15e0SLoGin /// 从空闲链表的开头,取出1个指定阶数的伙伴块,如果没有,则返回None 27740fe15e0SLoGin /// 27840fe15e0SLoGin /// ## 参数 27940fe15e0SLoGin /// 28040fe15e0SLoGin /// - `order` - 伙伴块的阶数 28140fe15e0SLoGin fn pop_front(&mut self, order: u8) -> Option<PhysAddr> { 28240fe15e0SLoGin let mut alloc_in_specific_order = |spec_order: u8| { 28340fe15e0SLoGin // 先尝试在order阶的“空闲链表”的开头位置分配一个伙伴块 28440fe15e0SLoGin let mut page_list_addr = self.free_area[Self::order2index(spec_order)]; 28540fe15e0SLoGin let mut page_list: PageList<A> = Self::read_page(page_list_addr); 28640fe15e0SLoGin 28740fe15e0SLoGin // 循环删除头部的空闲链表页 28840fe15e0SLoGin while page_list.entry_num == 0 { 28940fe15e0SLoGin let next_page_list_addr = page_list.next_page; 29040fe15e0SLoGin // 找完了,都是空的 29140fe15e0SLoGin if next_page_list_addr.is_null() { 29240fe15e0SLoGin return None; 29340fe15e0SLoGin } 29440fe15e0SLoGin 29540fe15e0SLoGin if !next_page_list_addr.is_null() { 29640fe15e0SLoGin // 此时page_list已经没有空闲伙伴块了,又因为非唯一页,需要删除该page_list 29740fe15e0SLoGin self.free_area[Self::order2index(spec_order)] = next_page_list_addr; 29840fe15e0SLoGin drop(page_list); 29940fe15e0SLoGin // kdebug!("FREE: page_list_addr={:b}", page_list_addr.data()); 30040fe15e0SLoGin unsafe { 30140fe15e0SLoGin self.buddy_free(page_list_addr, MMArch::PAGE_SHIFT as u8); 30240fe15e0SLoGin } 30340fe15e0SLoGin } 30440fe15e0SLoGin // 由于buddy_free可能导致首部的链表页发生变化,因此需要重新读取 30540fe15e0SLoGin let next_page_list_addr = self.free_area[Self::order2index(spec_order)]; 30640fe15e0SLoGin assert!(!next_page_list_addr.is_null()); 30740fe15e0SLoGin page_list = Self::read_page(next_page_list_addr); 30840fe15e0SLoGin page_list_addr = next_page_list_addr; 30940fe15e0SLoGin } 31040fe15e0SLoGin 31140fe15e0SLoGin // 有空闲页面,直接分配 31240fe15e0SLoGin if page_list.entry_num > 0 { 31340fe15e0SLoGin let entry: PhysAddr = unsafe { 31440fe15e0SLoGin A::read(Self::entry_virt_addr( 31540fe15e0SLoGin page_list_addr, 31640fe15e0SLoGin page_list.entry_num - 1, 31740fe15e0SLoGin )) 31840fe15e0SLoGin }; 31926887c63SLoGin // 清除该entry 32026887c63SLoGin unsafe { 32126887c63SLoGin A::write( 32226887c63SLoGin Self::entry_virt_addr(page_list_addr, page_list.entry_num - 1), 32326887c63SLoGin PhysAddr::new(0), 32426887c63SLoGin ) 32526887c63SLoGin }; 32640fe15e0SLoGin if entry.is_null() { 32726887c63SLoGin panic!( 32840fe15e0SLoGin "entry is null, entry={:?}, order={}, entry_num = {}", 32940fe15e0SLoGin entry, 33040fe15e0SLoGin spec_order, 33140fe15e0SLoGin page_list.entry_num - 1 33240fe15e0SLoGin ); 33340fe15e0SLoGin } 33440fe15e0SLoGin // kdebug!("entry={entry:?}"); 33526887c63SLoGin 33640fe15e0SLoGin // 更新page_list的entry_num 33740fe15e0SLoGin page_list.entry_num -= 1; 33840fe15e0SLoGin let tmp_current_entry_num = page_list.entry_num; 33940fe15e0SLoGin if page_list.entry_num == 0 { 34040fe15e0SLoGin if !page_list.next_page.is_null() { 34140fe15e0SLoGin // 此时page_list已经没有空闲伙伴块了,又因为非唯一页,需要删除该page_list 34240fe15e0SLoGin self.free_area[Self::order2index(spec_order)] = page_list.next_page; 34340fe15e0SLoGin drop(page_list); 34440fe15e0SLoGin unsafe { self.buddy_free(page_list_addr, MMArch::PAGE_SHIFT as u8) }; 34540fe15e0SLoGin } else { 34640fe15e0SLoGin Self::write_page(page_list_addr, page_list); 34740fe15e0SLoGin } 34840fe15e0SLoGin } else { 34940fe15e0SLoGin // 若entry_num不为0,说明该page_list还有空闲伙伴块,需要更新该page_list 35040fe15e0SLoGin // 把更新后的page_list写回 35140fe15e0SLoGin Self::write_page(page_list_addr, page_list.clone()); 35240fe15e0SLoGin } 35340fe15e0SLoGin 35440fe15e0SLoGin // 检测entry 是否对齐 35540fe15e0SLoGin if !entry.check_aligned(1 << spec_order) { 35640fe15e0SLoGin panic!("entry={:?} is not aligned, spec_order={spec_order}, page_list.entry_num={}", entry, tmp_current_entry_num); 35740fe15e0SLoGin } 35840fe15e0SLoGin return Some(entry); 35940fe15e0SLoGin } 36040fe15e0SLoGin return None; 36140fe15e0SLoGin }; 36240fe15e0SLoGin let result: Option<PhysAddr> = alloc_in_specific_order(order as u8); 36340fe15e0SLoGin // kdebug!("result={:?}", result); 36440fe15e0SLoGin if result.is_some() { 36540fe15e0SLoGin return result; 36640fe15e0SLoGin } 36740fe15e0SLoGin // 尝试从更大的链表中分裂 36840fe15e0SLoGin 36940fe15e0SLoGin let mut current_order = (order + 1) as usize; 37040fe15e0SLoGin let mut x: Option<PhysAddr> = None; 37140fe15e0SLoGin while current_order < MAX_ORDER { 37240fe15e0SLoGin x = alloc_in_specific_order(current_order as u8); 37340fe15e0SLoGin // kdebug!("current_order={:?}", current_order); 37440fe15e0SLoGin if x.is_some() { 37540fe15e0SLoGin break; 37640fe15e0SLoGin } 37740fe15e0SLoGin current_order += 1; 37840fe15e0SLoGin } 37940fe15e0SLoGin 38040fe15e0SLoGin // kdebug!("x={:?}", x); 38140fe15e0SLoGin // 如果找到一个大的块,就进行分裂 38240fe15e0SLoGin if x.is_some() { 38340fe15e0SLoGin // 分裂到order阶 38440fe15e0SLoGin while current_order > order as usize { 38540fe15e0SLoGin current_order -= 1; 38640fe15e0SLoGin // 把后面那半块放回空闲链表 38740fe15e0SLoGin 38840fe15e0SLoGin let buddy = *x.as_ref().unwrap() + (1 << current_order); 38940fe15e0SLoGin // kdebug!("x={:?}, buddy={:?}", x, buddy); 39040fe15e0SLoGin // kdebug!("current_order={:?}, buddy={:?}", current_order, buddy); 39140fe15e0SLoGin unsafe { self.buddy_free(buddy, current_order as u8) }; 39240fe15e0SLoGin } 39340fe15e0SLoGin return x; 39440fe15e0SLoGin } 39540fe15e0SLoGin 39640fe15e0SLoGin return None; 39740fe15e0SLoGin } 39840fe15e0SLoGin 39940fe15e0SLoGin /// 从伙伴系统中分配count个页面 40040fe15e0SLoGin /// 40140fe15e0SLoGin /// ## 参数 40240fe15e0SLoGin /// 40340fe15e0SLoGin /// - `count`:需要分配的页面数 40440fe15e0SLoGin /// 40540fe15e0SLoGin /// ## 返回值 40640fe15e0SLoGin /// 40740fe15e0SLoGin /// 返回分配的页面的物理地址和页面数 40840fe15e0SLoGin fn buddy_alloc(&mut self, count: PageFrameCount) -> Option<(PhysAddr, PageFrameCount)> { 40940fe15e0SLoGin assert!(count.data().is_power_of_two()); 41040fe15e0SLoGin // 计算需要分配的阶数 41140fe15e0SLoGin let mut order = log2(count.data() as usize); 41240fe15e0SLoGin if count.data() & ((1 << order) - 1) != 0 { 41340fe15e0SLoGin order += 1; 41440fe15e0SLoGin } 41540fe15e0SLoGin let order = (order + MIN_ORDER) as u8; 41640fe15e0SLoGin if order as usize >= MAX_ORDER { 41740fe15e0SLoGin return None; 41840fe15e0SLoGin } 41940fe15e0SLoGin 42040fe15e0SLoGin // kdebug!("buddy_alloc: order = {}", order); 42140fe15e0SLoGin // 获取该阶数的一个空闲页面 42240fe15e0SLoGin let free_addr = self.pop_front(order); 42340fe15e0SLoGin // kdebug!( 42440fe15e0SLoGin // "buddy_alloc: order = {}, free_addr = {:?}", 42540fe15e0SLoGin // order, 42640fe15e0SLoGin // free_addr 42740fe15e0SLoGin // ); 42840fe15e0SLoGin return free_addr 42940fe15e0SLoGin .map(|addr| (addr, PageFrameCount::new(1 << (order as usize - MIN_ORDER)))); 43040fe15e0SLoGin } 43140fe15e0SLoGin 43240fe15e0SLoGin /// 释放一个块 43340fe15e0SLoGin /// 43440fe15e0SLoGin /// ## 参数 43540fe15e0SLoGin /// 43640fe15e0SLoGin /// - `base` - 块的起始地址 43740fe15e0SLoGin /// - `order` - 块的阶数 43840fe15e0SLoGin unsafe fn buddy_free(&mut self, mut base: PhysAddr, order: u8) { 43940fe15e0SLoGin // kdebug!("buddy_free: base = {:?}, order = {}", base, order); 44040fe15e0SLoGin let mut order = order as usize; 44140fe15e0SLoGin 44240fe15e0SLoGin while order < MAX_ORDER { 44340fe15e0SLoGin // 检测地址是否合法 44440fe15e0SLoGin if base.data() & ((1 << (order)) - 1) != 0 { 44540fe15e0SLoGin panic!( 44640fe15e0SLoGin "buddy_free: base is not aligned, base = {:#x}, order = {}", 44740fe15e0SLoGin base.data(), 44840fe15e0SLoGin order 44940fe15e0SLoGin ); 45040fe15e0SLoGin } 45140fe15e0SLoGin 45240fe15e0SLoGin // 在链表中寻找伙伴块 45340fe15e0SLoGin // 伙伴块的地址是base ^ (1 << order) 45440fe15e0SLoGin let buddy_addr = PhysAddr::new(base.data() ^ (1 << order)); 45540fe15e0SLoGin 45640fe15e0SLoGin let first_page_list_paddr = self.free_area[Self::order2index(order as u8)]; 45740fe15e0SLoGin let mut page_list_paddr = first_page_list_paddr; 45840fe15e0SLoGin let mut page_list: PageList<A> = Self::read_page(page_list_paddr); 45940fe15e0SLoGin let first_page_list = page_list.clone(); 46040fe15e0SLoGin 46140fe15e0SLoGin let mut buddy_entry_virt_vaddr = None; 46240fe15e0SLoGin let mut buddy_entry_page_list_paddr = None; 46340fe15e0SLoGin // 除非order是最大的,否则尝试查找伙伴块 46440fe15e0SLoGin if likely(order != MAX_ORDER - 1) { 46540fe15e0SLoGin 'outer: loop { 46640fe15e0SLoGin for i in 0..page_list.entry_num { 46740fe15e0SLoGin let entry_virt_addr = Self::entry_virt_addr(page_list_paddr, i); 46840fe15e0SLoGin let entry: PhysAddr = unsafe { A::read(entry_virt_addr) }; 46940fe15e0SLoGin if entry == buddy_addr { 47040fe15e0SLoGin // 找到了伙伴块,记录该entry相关信息,然后退出查找 47140fe15e0SLoGin buddy_entry_virt_vaddr = Some(entry_virt_addr); 47240fe15e0SLoGin buddy_entry_page_list_paddr = Some(page_list_paddr); 47340fe15e0SLoGin break 'outer; 47440fe15e0SLoGin } 47540fe15e0SLoGin } 47640fe15e0SLoGin if page_list.next_page.is_null() { 47740fe15e0SLoGin break; 47840fe15e0SLoGin } 47940fe15e0SLoGin page_list_paddr = page_list.next_page; 48040fe15e0SLoGin page_list = Self::read_page(page_list_paddr); 48140fe15e0SLoGin } 48240fe15e0SLoGin } 48340fe15e0SLoGin 48440fe15e0SLoGin // 如果没有找到伙伴块 48540fe15e0SLoGin if buddy_entry_virt_vaddr.is_none() { 48640fe15e0SLoGin assert!( 48740fe15e0SLoGin page_list.entry_num <= Self::BUDDY_ENTRIES, 48840fe15e0SLoGin "buddy_free: page_list.entry_num > Self::BUDDY_ENTRIES" 48940fe15e0SLoGin ); 49040fe15e0SLoGin 49140fe15e0SLoGin // 当前第一个page_list没有空间了 49240fe15e0SLoGin if first_page_list.entry_num == Self::BUDDY_ENTRIES { 49340fe15e0SLoGin // 如果当前order是最小的,那么就把这个块当作新的page_list使用 49440fe15e0SLoGin let new_page_list_addr = if order == MIN_ORDER { 49540fe15e0SLoGin base 49640fe15e0SLoGin } else { 49740fe15e0SLoGin // 否则分配新的page_list 49840fe15e0SLoGin // 请注意,分配之后,有可能当前的entry_num会减1(伙伴块分裂),造成出现整个链表为null的entry数量为Self::BUDDY_ENTRIES+1的情况 49940fe15e0SLoGin // 但是不影响,我们在后面插入链表项的时候,会处理这种情况,检查链表中的第2个页是否有空位 50040fe15e0SLoGin self.buddy_alloc(PageFrameCount::new(1)) 50140fe15e0SLoGin .expect("buddy_alloc failed: no enough memory") 50240fe15e0SLoGin .0 50340fe15e0SLoGin }; 50440fe15e0SLoGin 50540fe15e0SLoGin // 清空这个页面 50640fe15e0SLoGin core::ptr::write_bytes( 50740fe15e0SLoGin A::phys_2_virt(new_page_list_addr) 50840fe15e0SLoGin .expect( 50940fe15e0SLoGin "Buddy free: failed to get virt address of [new_page_list_addr]", 51040fe15e0SLoGin ) 51140fe15e0SLoGin .as_ptr::<u8>(), 51240fe15e0SLoGin 0, 51340fe15e0SLoGin 1 << order, 51440fe15e0SLoGin ); 51540fe15e0SLoGin assert!( 51640fe15e0SLoGin first_page_list_paddr == self.free_area[Self::order2index(order as u8)] 51740fe15e0SLoGin ); 51840fe15e0SLoGin // 初始化新的page_list 51940fe15e0SLoGin let new_page_list = PageList::new(0, first_page_list_paddr); 52040fe15e0SLoGin Self::write_page(new_page_list_addr, new_page_list); 52140fe15e0SLoGin self.free_area[Self::order2index(order as u8)] = new_page_list_addr; 52240fe15e0SLoGin } 52340fe15e0SLoGin 52440fe15e0SLoGin // 由于上面可能更新了第一个链表页,因此需要重新获取这个值 52540fe15e0SLoGin let first_page_list_paddr = self.free_area[Self::order2index(order as u8)]; 52640fe15e0SLoGin let first_page_list: PageList<A> = Self::read_page(first_page_list_paddr); 52740fe15e0SLoGin 52840fe15e0SLoGin // 检查第二个page_list是否有空位 52940fe15e0SLoGin let second_page_list = if first_page_list.next_page.is_null() { 53040fe15e0SLoGin None 53140fe15e0SLoGin } else { 53240fe15e0SLoGin Some(Self::read_page::<PageList<A>>(first_page_list.next_page)) 53340fe15e0SLoGin }; 53440fe15e0SLoGin 53540fe15e0SLoGin let (paddr, mut page_list) = if let Some(second) = second_page_list { 53640fe15e0SLoGin // 第二个page_list有空位 53740fe15e0SLoGin // 应当符合之前的假设:还有1个空位 53840fe15e0SLoGin assert!(second.entry_num == Self::BUDDY_ENTRIES - 1); 53940fe15e0SLoGin 54040fe15e0SLoGin (first_page_list.next_page, second) 54140fe15e0SLoGin } else { 54240fe15e0SLoGin // 在第一个page list中分配 54340fe15e0SLoGin (first_page_list_paddr, first_page_list) 54440fe15e0SLoGin }; 54540fe15e0SLoGin 54640fe15e0SLoGin // kdebug!("to write entry, page_list_base={paddr:?}, page_list.entry_num={}, value={base:?}", page_list.entry_num); 54740fe15e0SLoGin assert!(page_list.entry_num < Self::BUDDY_ENTRIES); 54840fe15e0SLoGin // 把要归还的块,写入到链表项中 54940fe15e0SLoGin unsafe { A::write(Self::entry_virt_addr(paddr, page_list.entry_num), base) } 55040fe15e0SLoGin page_list.entry_num += 1; 55140fe15e0SLoGin Self::write_page(paddr, page_list); 55240fe15e0SLoGin return; 55340fe15e0SLoGin } else { 55440fe15e0SLoGin // 如果找到了伙伴块,合并,向上递归 55540fe15e0SLoGin 55640fe15e0SLoGin // 伙伴块所在的表项的虚拟地址 55740fe15e0SLoGin let buddy_entry_virt_addr = buddy_entry_virt_vaddr.unwrap(); 55840fe15e0SLoGin // 伙伴块所在的page_list的物理地址 55940fe15e0SLoGin let buddy_entry_page_list_paddr = buddy_entry_page_list_paddr.unwrap(); 56040fe15e0SLoGin 56140fe15e0SLoGin let mut page_list_paddr = self.free_area[Self::order2index(order as u8)]; 56240fe15e0SLoGin let mut page_list = Self::read_page::<PageList<A>>(page_list_paddr); 56340fe15e0SLoGin // 找第一个有空闲块的链表页。跳过空闲链表页。不进行回收的原因是担心出现死循环 56440fe15e0SLoGin while page_list.entry_num == 0 { 56540fe15e0SLoGin if page_list.next_page.is_null() { 56640fe15e0SLoGin panic!( 56740fe15e0SLoGin "buddy_free: page_list.entry_num == 0 && page_list.next_page.is_null()" 56840fe15e0SLoGin ); 56940fe15e0SLoGin } 57040fe15e0SLoGin page_list_paddr = page_list.next_page; 57140fe15e0SLoGin page_list = Self::read_page(page_list_paddr); 57240fe15e0SLoGin } 57340fe15e0SLoGin 57440fe15e0SLoGin // 如果伙伴块不在第一个链表页,则把第一个链表中的某个空闲块替换到伙伴块的位置 57540fe15e0SLoGin if page_list_paddr != buddy_entry_page_list_paddr { 57640fe15e0SLoGin let entry: PhysAddr = unsafe { 57740fe15e0SLoGin A::read(Self::entry_virt_addr( 57840fe15e0SLoGin page_list_paddr, 57940fe15e0SLoGin page_list.entry_num - 1, 58040fe15e0SLoGin )) 58140fe15e0SLoGin }; 58240fe15e0SLoGin // 把这个空闲块写入到伙伴块的位置 58340fe15e0SLoGin unsafe { 58440fe15e0SLoGin A::write(buddy_entry_virt_addr, entry); 58540fe15e0SLoGin } 58640fe15e0SLoGin // 设置刚才那个entry为空 58740fe15e0SLoGin unsafe { 58840fe15e0SLoGin A::write( 58940fe15e0SLoGin Self::entry_virt_addr(page_list_paddr, page_list.entry_num - 1), 59040fe15e0SLoGin PhysAddr::new(0), 59140fe15e0SLoGin ); 59240fe15e0SLoGin } 59340fe15e0SLoGin // 更新当前链表页的统计数据 59440fe15e0SLoGin page_list.entry_num -= 1; 59540fe15e0SLoGin Self::write_page(page_list_paddr, page_list); 59640fe15e0SLoGin } else { 59740fe15e0SLoGin // 伙伴块所在的链表页就是第一个链表页 59840fe15e0SLoGin let last_entry: PhysAddr = unsafe { 59940fe15e0SLoGin A::read(Self::entry_virt_addr( 60040fe15e0SLoGin page_list_paddr, 60140fe15e0SLoGin page_list.entry_num - 1, 60240fe15e0SLoGin )) 60340fe15e0SLoGin }; 60440fe15e0SLoGin 60540fe15e0SLoGin // 如果最后一个空闲块不是伙伴块,则把最后一个空闲块移动到伙伴块的位置 60640fe15e0SLoGin // 否则后面的操作也将删除这个伙伴块 60740fe15e0SLoGin if last_entry != buddy_addr { 60840fe15e0SLoGin unsafe { 60940fe15e0SLoGin A::write(buddy_entry_virt_addr, last_entry); 61040fe15e0SLoGin A::write( 61140fe15e0SLoGin Self::entry_virt_addr(page_list_paddr, page_list.entry_num - 1), 61240fe15e0SLoGin PhysAddr::new(0), 61340fe15e0SLoGin ); 61440fe15e0SLoGin } 61540fe15e0SLoGin } else { 61640fe15e0SLoGin unsafe { 61740fe15e0SLoGin A::write( 61840fe15e0SLoGin Self::entry_virt_addr(page_list_paddr, page_list.entry_num - 1), 61940fe15e0SLoGin PhysAddr::new(0), 62040fe15e0SLoGin ); 62140fe15e0SLoGin } 62240fe15e0SLoGin } 62340fe15e0SLoGin // 更新当前链表页的统计数据 62440fe15e0SLoGin page_list.entry_num -= 1; 62540fe15e0SLoGin Self::write_page(page_list_paddr, page_list); 62640fe15e0SLoGin } 62740fe15e0SLoGin } 62840fe15e0SLoGin base = min(base, buddy_addr); 62940fe15e0SLoGin order += 1; 63040fe15e0SLoGin } 63140fe15e0SLoGin // 走到这一步,order应该为MAX_ORDER-1 63240fe15e0SLoGin assert!(order == MAX_ORDER - 1); 63340fe15e0SLoGin } 63440fe15e0SLoGin } 63540fe15e0SLoGin 63640fe15e0SLoGin impl<A: MemoryManagementArch> FrameAllocator for BuddyAllocator<A> { 63740fe15e0SLoGin unsafe fn allocate(&mut self, count: PageFrameCount) -> Option<(PhysAddr, PageFrameCount)> { 63840fe15e0SLoGin return self.buddy_alloc(count); 63940fe15e0SLoGin } 64040fe15e0SLoGin 64140fe15e0SLoGin /// 释放一个块 64240fe15e0SLoGin /// 64340fe15e0SLoGin /// ## 参数 64440fe15e0SLoGin /// 64540fe15e0SLoGin /// - `base` - 块的起始地址 64640fe15e0SLoGin /// - `count` - 块的页数(必须是2的幂) 64740fe15e0SLoGin /// 64840fe15e0SLoGin /// ## Panic 64940fe15e0SLoGin /// 65040fe15e0SLoGin /// 如果count不是2的幂,会panic 65140fe15e0SLoGin unsafe fn free(&mut self, base: PhysAddr, count: PageFrameCount) { 65240fe15e0SLoGin // 要求count是2的幂 65340fe15e0SLoGin if unlikely(!count.data().is_power_of_two()) { 65440fe15e0SLoGin kwarn!("buddy free: count is not power of two"); 65540fe15e0SLoGin } 65640fe15e0SLoGin let mut order = log2(count.data() as usize); 65740fe15e0SLoGin if count.data() & ((1 << order) - 1) != 0 { 65840fe15e0SLoGin order += 1; 65940fe15e0SLoGin } 66040fe15e0SLoGin let order = (order + MIN_ORDER) as u8; 66140fe15e0SLoGin // kdebug!("free: base={:?}, count={:?}", base, count); 66240fe15e0SLoGin self.buddy_free(base, order); 66340fe15e0SLoGin } 66440fe15e0SLoGin 66540fe15e0SLoGin unsafe fn usage(&self) -> PageFrameUsage { 666*34e6d6c8Syuyi2439 let mut free_page_num: usize = 0; 667*34e6d6c8Syuyi2439 for index in 0..(MAX_ORDER - MIN_ORDER) { 668*34e6d6c8Syuyi2439 let mut pagelist: PageList<A> = Self::read_page(self.free_area[index]); 669*34e6d6c8Syuyi2439 loop { 670*34e6d6c8Syuyi2439 free_page_num += pagelist.entry_num << index; 671*34e6d6c8Syuyi2439 if pagelist.next_page.is_null() { 672*34e6d6c8Syuyi2439 break; 673*34e6d6c8Syuyi2439 } 674*34e6d6c8Syuyi2439 pagelist = Self::read_page(pagelist.next_page); 675*34e6d6c8Syuyi2439 } 676*34e6d6c8Syuyi2439 } 677*34e6d6c8Syuyi2439 let free = PageFrameCount::new(free_page_num); 678*34e6d6c8Syuyi2439 PageFrameUsage::new(self.total - free, self.total) 67940fe15e0SLoGin } 68040fe15e0SLoGin } 68140fe15e0SLoGin 68240fe15e0SLoGin /// 一个用于计算整数的对数的函数,会向下取整。(由于内核不能进行浮点运算,因此需要这个函数) 68340fe15e0SLoGin fn log2(x: usize) -> usize { 68440fe15e0SLoGin let leading_zeros = x.leading_zeros() as usize; 68540fe15e0SLoGin let log2x = 63 - leading_zeros; 68640fe15e0SLoGin return log2x; 68740fe15e0SLoGin } 688