/// @Author: longjin@dragonos.org
/// @Author: kongweichao@dragonos.org
/// @Date: 2023-03-28 16:03:47
/// @FilePath: /DragonOS/kernel/src/mm/allocator/buddy.rs
/// @Description: 伙伴分配器
use crate::arch::MMArch;
use crate::mm::allocator::bump::BumpAllocator;
use crate::mm::allocator::page_frame::{FrameAllocator, PageFrameCount, PageFrameUsage};
use crate::mm::{MemoryManagementArch, PhysAddr, PhysMemoryArea, VirtAddr};
use crate::{kdebug, kwarn};
use core::cmp::min;
use core::fmt::Debug;
use core::intrinsics::{likely, unlikely};
use core::{marker::PhantomData, mem};
// 一个全局变量MAX_ORDER,用来表示buddy算法的最大阶数 [MIN_ORDER, MAX_ORDER)左闭右开区间
const MAX_ORDER: usize = 31;
// 4KB
const MIN_ORDER: usize = 12;
/// 保存buddy算法中每一页存放的BuddyEntry的信息,占据每个页的起始位置
#[derive(Debug)]
pub struct PageList {
// 页存放entry的数量
entry_num: usize,
// 下一个页面的地址
next_page: PhysAddr,
phantom: PhantomData,
}
impl Clone for PageList {
fn clone(&self) -> Self {
Self {
entry_num: self.entry_num,
next_page: self.next_page,
phantom: PhantomData,
}
}
}
impl PageList {
#[allow(dead_code)]
fn empty() -> Self {
Self {
entry_num: 0,
next_page: PhysAddr::new(0),
phantom: PhantomData,
}
}
fn new(entry_num: usize, next_page: PhysAddr) -> Self {
Self {
entry_num,
next_page,
phantom: PhantomData,
}
}
}
/// @brief: 用来表示 buddy 算法中的一个 buddy 块,整体存放在area的头部
// 这种方式会出现对齐问题
// #[repr(packed)]
#[repr(C)]
#[derive(Debug)]
pub struct BuddyAllocator {
// 存放每个阶的空闲“链表”的头部地址
free_area: [PhysAddr; (MAX_ORDER - MIN_ORDER) as usize],
/// 总页数
total: PageFrameCount,
phantom: PhantomData,
}
impl BuddyAllocator {
const BUDDY_ENTRIES: usize =
// 定义一个变量记录buddy表的大小
(A::PAGE_SIZE - mem::size_of::>()) / mem::size_of::();
pub unsafe fn new(mut bump_allocator: BumpAllocator) -> Option {
let initial_free_pages = bump_allocator.usage().free();
let total_memory = bump_allocator.usage().total();
kdebug!("Free pages before init buddy: {:?}", initial_free_pages);
kdebug!("Buddy entries: {}", Self::BUDDY_ENTRIES);
let mut free_area: [PhysAddr; (MAX_ORDER - MIN_ORDER) as usize] =
[PhysAddr::new(0); (MAX_ORDER - MIN_ORDER) as usize];
// Buddy初始占用的空间从bump分配
for f in free_area.iter_mut() {
let curr_page = bump_allocator.allocate_one();
// 保存每个阶的空闲链表的头部地址
*f = curr_page.unwrap();
// 清空当前页
core::ptr::write_bytes(MMArch::phys_2_virt(*f)?.data() as *mut u8, 0, A::PAGE_SIZE);
let page_list: PageList = PageList::new(0, PhysAddr::new(0));
Self::write_page(*f, page_list);
}
let mut allocator = Self {
free_area,
total: PageFrameCount::new(0),
phantom: PhantomData,
};
let mut total_pages_to_buddy = PageFrameCount::new(0);
let mut res_areas = [PhysMemoryArea::default(); 128];
let mut offset_in_remain_area = bump_allocator
.remain_areas(&mut res_areas)
.expect("BuddyAllocator: failed to get remain areas from bump allocator");
let remain_areas = &res_areas[0..];
kdebug!("Remain areas: {:?}", &remain_areas[0..10]);
kdebug!("offset_in_remain_area: {:?}", offset_in_remain_area);
for area in remain_areas {
let mut paddr = (area.area_base_aligned() + offset_in_remain_area).data();
let mut remain_pages =
PageFrameCount::from_bytes(area.area_end_aligned().data() - paddr).unwrap();
total_pages_to_buddy += remain_pages;
if offset_in_remain_area != 0 {
offset_in_remain_area = 0;
}
// 先从低阶开始,尽可能地填满空闲链表
for i in MIN_ORDER..MAX_ORDER {
// kdebug!("i {i}, remain pages={}", remain_pages.data());
if remain_pages.data() < (1 << (i - MIN_ORDER)) {
break;
}
assert!(paddr & ((1 << i) - 1) == 0);
if likely(i != MAX_ORDER - 1) {
// 要填写entry
if paddr & (1 << i) != 0 {
allocator.buddy_free(PhysAddr::new(paddr), i as u8);
paddr += 1 << i;
remain_pages -= 1 << (i - MIN_ORDER);
};
} else {
// 往最大的阶数的链表中添加entry(注意要考虑到最大阶数的链表可能有多页)
// 断言剩余页面数量是MAX_ORDER-1阶的整数倍
let mut entries = (remain_pages.data() * A::PAGE_SIZE) >> i;
while entries > 0 {
allocator.buddy_free(PhysAddr::new(paddr), i as u8);
paddr += 1 << i;
remain_pages -= 1 << (i - MIN_ORDER);
entries -= 1;
}
}
}
// 然后从高往低,把剩余的页面加入链表
let mut remain_bytes = remain_pages.data() * A::PAGE_SIZE;
assert!(remain_bytes < (1 << MAX_ORDER - 1));
for i in (MIN_ORDER..MAX_ORDER).rev() {
if remain_bytes >= (1 << i) {
assert!(paddr & ((1 << i) - 1) == 0);
allocator.buddy_free(PhysAddr::new(paddr), i as u8);
paddr += 1 << i;
remain_bytes -= 1 << i;
}
}
assert!(remain_bytes == 0);
}
kdebug!("Total pages to buddy: {:?}", total_pages_to_buddy);
allocator.total = total_memory;
Some(allocator)
}
/// 获取第j个entry的虚拟地址,
/// j从0开始计数
pub fn entry_virt_addr(base_addr: PhysAddr, j: usize) -> VirtAddr {
let entry_virt_addr = unsafe { A::phys_2_virt(Self::entry_addr(base_addr, j)) };
return entry_virt_addr.unwrap();
}
pub fn entry_addr(base_addr: PhysAddr, j: usize) -> PhysAddr {
let entry_addr = base_addr + mem::size_of::>() + j * mem::size_of::();
return entry_addr;
}
pub fn read_page(addr: PhysAddr) -> T {
let page_list = unsafe { A::read(A::phys_2_virt(addr).unwrap()) };
return page_list;
}
pub fn write_page(curr_page: PhysAddr, page_list: PageList) {
// 把物理地址转换为虚拟地址
let virt_addr = unsafe { A::phys_2_virt(curr_page) };
let virt_addr = virt_addr.unwrap();
unsafe { A::write(virt_addr, page_list) };
}
/// 从order转换为free_area的下标
///
/// # 参数
///
/// - `order` - order
///
/// # 返回值
///
/// free_area的下标
#[inline]
fn order2index(order: u8) -> usize {
(order as usize - MIN_ORDER) as usize
}
/// 从空闲链表的开头,取出1个指定阶数的伙伴块,如果没有,则返回None
///
/// ## 参数
///
/// - `order` - 伙伴块的阶数
fn pop_front(&mut self, order: u8) -> Option {
let mut alloc_in_specific_order = |spec_order: u8| {
// 先尝试在order阶的“空闲链表”的开头位置分配一个伙伴块
let mut page_list_addr = self.free_area[Self::order2index(spec_order)];
let mut page_list: PageList = Self::read_page(page_list_addr);
// 循环删除头部的空闲链表页
while page_list.entry_num == 0 {
let next_page_list_addr = page_list.next_page;
// 找完了,都是空的
if next_page_list_addr.is_null() {
return None;
}
if !next_page_list_addr.is_null() {
// 此时page_list已经没有空闲伙伴块了,又因为非唯一页,需要删除该page_list
self.free_area[Self::order2index(spec_order)] = next_page_list_addr;
drop(page_list);
// kdebug!("FREE: page_list_addr={:b}", page_list_addr.data());
unsafe {
self.buddy_free(page_list_addr, MMArch::PAGE_SHIFT as u8);
}
}
// 由于buddy_free可能导致首部的链表页发生变化,因此需要重新读取
let next_page_list_addr = self.free_area[Self::order2index(spec_order)];
assert!(!next_page_list_addr.is_null());
page_list = Self::read_page(next_page_list_addr);
page_list_addr = next_page_list_addr;
}
// 有空闲页面,直接分配
if page_list.entry_num > 0 {
let entry: PhysAddr = unsafe {
A::read(Self::entry_virt_addr(
page_list_addr,
page_list.entry_num - 1,
))
};
// 清除该entry
unsafe {
A::write(
Self::entry_virt_addr(page_list_addr, page_list.entry_num - 1),
PhysAddr::new(0),
)
};
if entry.is_null() {
panic!(
"entry is null, entry={:?}, order={}, entry_num = {}",
entry,
spec_order,
page_list.entry_num - 1
);
}
// kdebug!("entry={entry:?}");
// 更新page_list的entry_num
page_list.entry_num -= 1;
let tmp_current_entry_num = page_list.entry_num;
if page_list.entry_num == 0 {
if !page_list.next_page.is_null() {
// 此时page_list已经没有空闲伙伴块了,又因为非唯一页,需要删除该page_list
self.free_area[Self::order2index(spec_order)] = page_list.next_page;
drop(page_list);
unsafe { self.buddy_free(page_list_addr, MMArch::PAGE_SHIFT as u8) };
} else {
Self::write_page(page_list_addr, page_list);
}
} else {
// 若entry_num不为0,说明该page_list还有空闲伙伴块,需要更新该page_list
// 把更新后的page_list写回
Self::write_page(page_list_addr, page_list.clone());
}
// 检测entry 是否对齐
if !entry.check_aligned(1 << spec_order) {
panic!("entry={:?} is not aligned, spec_order={spec_order}, page_list.entry_num={}", entry, tmp_current_entry_num);
}
return Some(entry);
}
return None;
};
let result: Option = alloc_in_specific_order(order as u8);
// kdebug!("result={:?}", result);
if result.is_some() {
return result;
}
// 尝试从更大的链表中分裂
let mut current_order = (order + 1) as usize;
let mut x: Option = None;
while current_order < MAX_ORDER {
x = alloc_in_specific_order(current_order as u8);
// kdebug!("current_order={:?}", current_order);
if x.is_some() {
break;
}
current_order += 1;
}
// kdebug!("x={:?}", x);
// 如果找到一个大的块,就进行分裂
if x.is_some() {
// 分裂到order阶
while current_order > order as usize {
current_order -= 1;
// 把后面那半块放回空闲链表
let buddy = *x.as_ref().unwrap() + (1 << current_order);
// kdebug!("x={:?}, buddy={:?}", x, buddy);
// kdebug!("current_order={:?}, buddy={:?}", current_order, buddy);
unsafe { self.buddy_free(buddy, current_order as u8) };
}
return x;
}
return None;
}
/// 从伙伴系统中分配count个页面
///
/// ## 参数
///
/// - `count`:需要分配的页面数
///
/// ## 返回值
///
/// 返回分配的页面的物理地址和页面数
fn buddy_alloc(&mut self, count: PageFrameCount) -> Option<(PhysAddr, PageFrameCount)> {
assert!(count.data().is_power_of_two());
// 计算需要分配的阶数
let mut order = log2(count.data() as usize);
if count.data() & ((1 << order) - 1) != 0 {
order += 1;
}
let order = (order + MIN_ORDER) as u8;
if order as usize >= MAX_ORDER {
return None;
}
// kdebug!("buddy_alloc: order = {}", order);
// 获取该阶数的一个空闲页面
let free_addr = self.pop_front(order);
// kdebug!(
// "buddy_alloc: order = {}, free_addr = {:?}",
// order,
// free_addr
// );
return free_addr
.map(|addr| (addr, PageFrameCount::new(1 << (order as usize - MIN_ORDER))));
}
/// 释放一个块
///
/// ## 参数
///
/// - `base` - 块的起始地址
/// - `order` - 块的阶数
unsafe fn buddy_free(&mut self, mut base: PhysAddr, order: u8) {
// kdebug!("buddy_free: base = {:?}, order = {}", base, order);
let mut order = order as usize;
while order < MAX_ORDER {
// 检测地址是否合法
if base.data() & ((1 << (order)) - 1) != 0 {
panic!(
"buddy_free: base is not aligned, base = {:#x}, order = {}",
base.data(),
order
);
}
// 在链表中寻找伙伴块
// 伙伴块的地址是base ^ (1 << order)
let buddy_addr = PhysAddr::new(base.data() ^ (1 << order));
let first_page_list_paddr = self.free_area[Self::order2index(order as u8)];
let mut page_list_paddr = first_page_list_paddr;
let mut page_list: PageList = Self::read_page(page_list_paddr);
let first_page_list = page_list.clone();
let mut buddy_entry_virt_vaddr = None;
let mut buddy_entry_page_list_paddr = None;
// 除非order是最大的,否则尝试查找伙伴块
if likely(order != MAX_ORDER - 1) {
'outer: loop {
for i in 0..page_list.entry_num {
let entry_virt_addr = Self::entry_virt_addr(page_list_paddr, i);
let entry: PhysAddr = unsafe { A::read(entry_virt_addr) };
if entry == buddy_addr {
// 找到了伙伴块,记录该entry相关信息,然后退出查找
buddy_entry_virt_vaddr = Some(entry_virt_addr);
buddy_entry_page_list_paddr = Some(page_list_paddr);
break 'outer;
}
}
if page_list.next_page.is_null() {
break;
}
page_list_paddr = page_list.next_page;
page_list = Self::read_page(page_list_paddr);
}
}
// 如果没有找到伙伴块
if buddy_entry_virt_vaddr.is_none() {
assert!(
page_list.entry_num <= Self::BUDDY_ENTRIES,
"buddy_free: page_list.entry_num > Self::BUDDY_ENTRIES"
);
// 当前第一个page_list没有空间了
if first_page_list.entry_num == Self::BUDDY_ENTRIES {
// 如果当前order是最小的,那么就把这个块当作新的page_list使用
let new_page_list_addr = if order == MIN_ORDER {
base
} else {
// 否则分配新的page_list
// 请注意,分配之后,有可能当前的entry_num会减1(伙伴块分裂),造成出现整个链表为null的entry数量为Self::BUDDY_ENTRIES+1的情况
// 但是不影响,我们在后面插入链表项的时候,会处理这种情况,检查链表中的第2个页是否有空位
self.buddy_alloc(PageFrameCount::new(1))
.expect("buddy_alloc failed: no enough memory")
.0
};
// 清空这个页面
core::ptr::write_bytes(
A::phys_2_virt(new_page_list_addr)
.expect(
"Buddy free: failed to get virt address of [new_page_list_addr]",
)
.as_ptr::(),
0,
1 << order,
);
assert!(
first_page_list_paddr == self.free_area[Self::order2index(order as u8)]
);
// 初始化新的page_list
let new_page_list = PageList::new(0, first_page_list_paddr);
Self::write_page(new_page_list_addr, new_page_list);
self.free_area[Self::order2index(order as u8)] = new_page_list_addr;
}
// 由于上面可能更新了第一个链表页,因此需要重新获取这个值
let first_page_list_paddr = self.free_area[Self::order2index(order as u8)];
let first_page_list: PageList = Self::read_page(first_page_list_paddr);
// 检查第二个page_list是否有空位
let second_page_list = if first_page_list.next_page.is_null() {
None
} else {
Some(Self::read_page::>(first_page_list.next_page))
};
let (paddr, mut page_list) = if let Some(second) = second_page_list {
// 第二个page_list有空位
// 应当符合之前的假设:还有1个空位
assert!(second.entry_num == Self::BUDDY_ENTRIES - 1);
(first_page_list.next_page, second)
} else {
// 在第一个page list中分配
(first_page_list_paddr, first_page_list)
};
// kdebug!("to write entry, page_list_base={paddr:?}, page_list.entry_num={}, value={base:?}", page_list.entry_num);
assert!(page_list.entry_num < Self::BUDDY_ENTRIES);
// 把要归还的块,写入到链表项中
unsafe { A::write(Self::entry_virt_addr(paddr, page_list.entry_num), base) }
page_list.entry_num += 1;
Self::write_page(paddr, page_list);
return;
} else {
// 如果找到了伙伴块,合并,向上递归
// 伙伴块所在的表项的虚拟地址
let buddy_entry_virt_addr = buddy_entry_virt_vaddr.unwrap();
// 伙伴块所在的page_list的物理地址
let buddy_entry_page_list_paddr = buddy_entry_page_list_paddr.unwrap();
let mut page_list_paddr = self.free_area[Self::order2index(order as u8)];
let mut page_list = Self::read_page::>(page_list_paddr);
// 找第一个有空闲块的链表页。跳过空闲链表页。不进行回收的原因是担心出现死循环
while page_list.entry_num == 0 {
if page_list.next_page.is_null() {
panic!(
"buddy_free: page_list.entry_num == 0 && page_list.next_page.is_null()"
);
}
page_list_paddr = page_list.next_page;
page_list = Self::read_page(page_list_paddr);
}
// 如果伙伴块不在第一个链表页,则把第一个链表中的某个空闲块替换到伙伴块的位置
if page_list_paddr != buddy_entry_page_list_paddr {
let entry: PhysAddr = unsafe {
A::read(Self::entry_virt_addr(
page_list_paddr,
page_list.entry_num - 1,
))
};
// 把这个空闲块写入到伙伴块的位置
unsafe {
A::write(buddy_entry_virt_addr, entry);
}
// 设置刚才那个entry为空
unsafe {
A::write(
Self::entry_virt_addr(page_list_paddr, page_list.entry_num - 1),
PhysAddr::new(0),
);
}
// 更新当前链表页的统计数据
page_list.entry_num -= 1;
Self::write_page(page_list_paddr, page_list);
} else {
// 伙伴块所在的链表页就是第一个链表页
let last_entry: PhysAddr = unsafe {
A::read(Self::entry_virt_addr(
page_list_paddr,
page_list.entry_num - 1,
))
};
// 如果最后一个空闲块不是伙伴块,则把最后一个空闲块移动到伙伴块的位置
// 否则后面的操作也将删除这个伙伴块
if last_entry != buddy_addr {
unsafe {
A::write(buddy_entry_virt_addr, last_entry);
A::write(
Self::entry_virt_addr(page_list_paddr, page_list.entry_num - 1),
PhysAddr::new(0),
);
}
} else {
unsafe {
A::write(
Self::entry_virt_addr(page_list_paddr, page_list.entry_num - 1),
PhysAddr::new(0),
);
}
}
// 更新当前链表页的统计数据
page_list.entry_num -= 1;
Self::write_page(page_list_paddr, page_list);
}
}
base = min(base, buddy_addr);
order += 1;
}
// 走到这一步,order应该为MAX_ORDER-1
assert!(order == MAX_ORDER - 1);
}
}
impl FrameAllocator for BuddyAllocator {
unsafe fn allocate(&mut self, count: PageFrameCount) -> Option<(PhysAddr, PageFrameCount)> {
return self.buddy_alloc(count);
}
/// 释放一个块
///
/// ## 参数
///
/// - `base` - 块的起始地址
/// - `count` - 块的页数(必须是2的幂)
///
/// ## Panic
///
/// 如果count不是2的幂,会panic
unsafe fn free(&mut self, base: PhysAddr, count: PageFrameCount) {
// 要求count是2的幂
if unlikely(!count.data().is_power_of_two()) {
kwarn!("buddy free: count is not power of two");
}
let mut order = log2(count.data() as usize);
if count.data() & ((1 << order) - 1) != 0 {
order += 1;
}
let order = (order + MIN_ORDER) as u8;
// kdebug!("free: base={:?}, count={:?}", base, count);
self.buddy_free(base, order);
}
unsafe fn usage(&self) -> PageFrameUsage {
let mut free_page_num: usize = 0;
for index in 0..(MAX_ORDER - MIN_ORDER) {
let mut pagelist: PageList = Self::read_page(self.free_area[index]);
loop {
free_page_num += pagelist.entry_num << index;
if pagelist.next_page.is_null() {
break;
}
pagelist = Self::read_page(pagelist.next_page);
}
}
let free = PageFrameCount::new(free_page_num);
PageFrameUsage::new(self.total - free, self.total)
}
}
/// 一个用于计算整数的对数的函数,会向下取整。(由于内核不能进行浮点运算,因此需要这个函数)
fn log2(x: usize) -> usize {
let leading_zeros = x.leading_zeros() as usize;
let log2x = 63 - leading_zeros;
return log2x;
}