6. 内存分配

本章代码对应 commit ：ce95a018b972c80c59d83e8f7eb5d0d2a7f9b6b5

概要

上一章我们通过 bbl 启用了分页机制。但是这个由于这个页表过于简陋，所以我们希望能够使用自己写的页表。显然，系统需要一片内存来存放页表。本章我们的目标是将物理内存分配给页表。但是在此之前我们需要先能够管理物理内存，为此我们需要：

1. 判断内存的那些部分是可以供我们分配的。

2. 引入 buddy allocator 辅助管理物理内存。

3. 实现物理内存的分配与释放。

设置可分配内存范围

首先，新建 consts.rs 保存一些常量：

pub const KERNEL_OFFSET: usize = 0xC000_0000;

pub const MEMORY_OFFSET: usize = 0x8000_0000;

pub const PAGE_SIZE: usize = 4096;

pub const MAX_DTB_SIZE: usize = 0x2000;

pub const KERNEL_HEAP_SIZE: usize = 0x00a0_0000;

在实现内存分配之前，堆的初始化是必须的：

Cargo.toml

[dependencies]
buddy_system_allocator = "0.1"

lib.rs

use buddy_system_allocator::LockedHeap;
#[global_allocator]
static HEAP_ALLOCATOR: LockedHeap = LockedHeap::empty();

memory/mod.rs

use crate::HEAP_ALLOCATOR;

pub fn init(dtb: usize) {
    use riscv::register::sstatus;
    unsafe {
        // Allow user memory access
        sstatus::set_sum();
    }
    init_heap();
}

fn init_heap() {
    static mut HEAP: [u8; KERNEL_HEAP_SIZE] = [0; KERNEL_HEAP_SIZE];
    unsafe {
        HEAP_ALLOCATOR
            .lock()
            .init(HEAP.as_ptr() as usize, KERNEL_HEAP_SIZE);
    }
    println!("heap init end");
}

现在我们便可以开始计算哪些部分的内存是能够被分配的。

在 Cargo.toml 中加入：

[dependencies]
device_tree = { path = "crate/device_tree-rs" }

这时编译出现如下错误：

error: `#[alloc_error_handler]` function required, but not found

error: aborting due to previous error

error: Could not compile `os`.

To learn more, run the command again with --verbose.
Makefile:30: recipe for target 'kernel' failed
make: *** [kernel] Error 101

FIX error： #[alloc_error_handler] function required, but not found

这需要在os/lib.rs中添加一行：

#![feature(alloc_error_handler)]

表示要定义alloc_error_handler这个函数。然后在os/memory/mod.rs中实现这个函数的定义：

#[alloc_error_handler]
fn foo(_: core::alloc::Layout) -> ! {
    panic!("DO NOTHING alloc_error_handler set by kernel");
}

其实这个函数只是简单地panic整个OS。

显示机器和内核的内存信息

通过 let Some((addr, mem_size)) = device_tree::DeviceTree::dtb_query_memory(dtb) 即可从 dtb 中读取内存的起始地址和大小。？？？

在内核结束的位置，紧接着就会存放 dtb ：

let kernel_end = dtb - KERNEL_OFFSET + MEMORY_OFFSET + PAGE_SIZE; // 内核的起始物理地址
let kernel_size = kernel_end - addr; // 内核的终止物理地址

这里给 dtb 留出了一页的大小存放

引入 buddy allocator

创建文件： memory/frame_allocator/mod.rs 。

在 Cargo.toml 中添加：

[dependencies]
bit_field = "0.9"
buddy-allocator = { path = "crate/buddy-allocator" }
lazy_static = { version = "1.3", features = ["spin_no_std"] }
spin = "0.3"

buddy_allocator 通过 buddy system 算法分配内存，算法细节可自行上网查询。

在 memory/frame_allocator/mod.rs 中添加：

use buddy_allocator::{ BuddyAllocator, log2_down };
use lazy_static::*;
use spin::Mutex;
use riscv::addr::*;
use crate::consts::*;

// 物理页帧分配器
lazy_static! {
    pub static ref BUDDY_ALLOCATOR: Mutex<BuddyAllocator>
        = Mutex::new(BuddyAllocator::new());
}

static mut KERNEL_END: usize = 0;

pub fn init(start: usize, lenth: usize) {
    unsafe {
        KERNEL_END = start;
    }
    let mut bu = BUDDY_ALLOCATOR.lock()
        .init(log2_down(lenth / PAGE_SIZE) as u8);
    println!("++++init frame allocator succeed!++++");
}

对详细实现过程感兴趣的读者请自行上 GitHub 阅读代码，这里不做过多介绍

这里我们需要创建一个用于分配内存的 BUDDY_ALLOCATOR 全局静态变量。但是他的值需要在运行时才能被确定。这里 lazy_static 便帮我们解决了这个问题。

什么是 Mutex ？我们用一个现实生活中的例子来理解：假设你去超市买了一个笔记本，付款之后你还没来得及把他拿走，这时来了另一个人，也付了钱，买了这个笔记本。那么这个笔记本属于谁呢？这不是我们乐意见到的。为了防止这种情况，在超市买东西的时候，前一个人的结账尚未完成的时候，下一个人是不能够开始结账的。同样的道理适用于内存块的分配，这里的内存块就可以类比于超市的笔记本，互斥锁（Mutex）就使得内存在分配时不会收到外界干扰。

更详细的互斥锁内容将在以后的章节介绍

init 根据内存大小初始化了 buddy_allocator ，同时修改了内核结束地址，以便后续物理内存的分配和释放时使用。

物理内存块的分配与释放

有了上面的这些工作，内存分配和释放的实现变得十分简洁：

// in memory/frame_allocator/mod.rs

use riscv::addr::*;

pub fn alloc_frame() -> Option<Frame> {
        alloc_frames(1)
}

pub fn alloc_frames(size: usize) -> Option<Frame> {
    unsafe {
        let ret = BUDDY_ALLOCATOR
            .lock()
            .alloc(size)
            .map(|id| id * PAGE_SIZE + KERNEL_END);
        ret.map(|addr| Frame::of_addr(PhysAddr::new(addr)))
    }
}

pub fn dealloc_frame(target: Frame) {
        dealloc_frames(target, 1);
}

pub fn dealloc_frames(target: Frame, size: usize) {
    unsafe {
        BUDDY_ALLOCATOR
            .lock()
            .dealloc(target.number() - KERNEL_END / PAGE_SIZE, size);
    }
}

riscv::addr::* 引入了 struct Frame 以及一些相关函数。由于 buddy_allocator.alloc 返回的是内存块编号，类型为 Option<usize> ，所以需要将其转换为物理地址，然后通过 Frame::of_addr 转换为物理帧。

这里涉及到一个 rust 的语法：闭包。我们举一个例子便能理解他：

• Some(233).map(|x| x + 666) = Some(899)

完成了分配和释放的函数，让我们来简单的测试一下他的正确性。在 memory/frame_allocator/mod.rs 中加入：

pub fn test() {
    let frame1: Frame = alloc_frame().expect("failed to alloc frame");
    println!("test frame_allocator: {:#x}", frame1.start_address().as_usize());
    let frame2: Frame = alloc_frame().expect("failed to alloc frame");
    println!("test frame_allocator: {:#x}", frame2.start_address().as_usize());
    dealloc_frame(frame1);
    let frame3: Frame = alloc_frame().expect("failed to alloc frame");
    println!("test frame_allocator: {:#x}", frame3.start_address().as_usize());
    dealloc_frame(frame2);
    dealloc_frame(frame3);
}

然后修改 memory/mod.rs 的 init() ：

pub mod frame_allocator;

use frame_allocator::{ init as init_frame_allocator, test as test_frame_allocator };
use crate::consts::*;
use crate::HEAP_ALLOCATOR;

pub fn init(dtb: usize) {
    use riscv::register::sstatus;
    unsafe {
        // Allow user memory access
        sstatus::set_sum();
    }
    init_heap();
    if let Some((addr, mem_size)) = device_tree::DeviceTree::dtb_query_memory(dtb) {
        assert_eq!(addr, MEMORY_OFFSET);
        let KERNEL_END = dtb - KERNEL_OFFSET + MEMORY_OFFSET + PAGE_SIZE;
        let KERNEL_SIZE = KERNEL_END - addr;
        init_frame_allocator(KERNEL_END, KERNEL_SIZE);
    } else {
        panic!("failed to query memory");
    }
    test_frame_allocator();
}

执行 make run ，出现了如下错误：

error[E0152]: duplicate lang item found: `oom`.
  --> src/memory/mod.rs:49:1
   |
49 | / fn foo(_: core::alloc::Layout) -> ! {
50 | |     panic!("DO NOTHING alloc_error_handler set by kernel");
51 | | }
   | |_^
   |
   = note: first defined in crate `buddy_allocator`.

error: aborting due to previous error

For more information about this error, try `rustc --explain E0152`.
error: Could not compile `os`.

这是由于buddy_allocator也定义了对内存分配错误的处理函数，这样就和我们之前定义的alloc_error_handler冲突了。把我们的老代码src/memory/mod.rs：47-51 lines删除掉即可。再次执行make run，编译正确，且运行的屏幕部分显示内容为：

++++init frame allocator succeed!++++
test frame_allocator: 0x80c01000
test frame_allocator: 0x80c02000
test frame_allocator: 0x80c01000

注意到 0x80c02000 - 0x80c01000 = 0x1000 = 4096 ，每次分配的内存恰好就为一个页面的大小（PAGE_SIZE）。

这里输出的均为物理地址

预告

本章我们实现了内存分配，下一章我们将利用 frame_allocator 创建页表。