内存分配

本章代码对应分支：alloc-memory

概要

  1. 初始化内核堆。
  2. 判断内存的那些部分是可以供我们分配的。
  3. 引入 buddy allocator 辅助管理物理内存。
  4. 实现物理内存的分配与释放。

初始化内核堆

内存可以在 stack 上分配，在我们的 os 中，stack 的大小在 boot/entry.asm 被定为 4 * 4k 。但是如 Vec ，其内存分配是在 heap 上的。堆的大小取决于 全局分配器 。目前 rust 语言并没有指定 全局分配器 ，有些编译器可能会帮忙指定。#[global_allocator] 标签允许我们实现自己的 全局分配器 。这里如果不指定 全局分配器 会导致后续无法使用 Vec 等数据结构。

more about global allocator

这里我们使用一个现成的适用于本 os 的 全局分配器 ：

  • Cargo.toml
[dependencies]
buddy_system_allocator = "0.1"
  • lib.rs
#![feature(alloc_error_handler)]

mod memory;
mod consts;

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

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

接下来创建目录和文件，对堆进行初始化：

  • consts.rs
pub const KERNEL_HEAP_SIZE: usize = 0x00a0_0000;

大小可以自行规定，合适就行，后续（下一章）将根据实际情况修改它

  • memory/mod.rs
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();
}

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);
    }
}

这里我们将 sum 位设为 1 。sum（permit supervisor user memory access）位修改 S 模式读、写和指令获取访问虚拟内存的权限。仅当 sum = 1 时则允许在 S 模式下访问属于 U 模式（U = 1）的内存，否则会产生异常 这一步现在还不是必须的，要到用户程序时才能体现出作用

计算可用内存

硬件信息需要通过 device tree 获得，但是略繁琐，所以这里我们暂时直接钦定 MEMORY_END：

  • consts.rs
pub const MEMORY_OFFSET: usize = 0x8000_0000;
pub const MEMORY_END: usize = 0x8800_0000;
pub const PAGE_SIZE: usize = 4096;
  • memory/mod.rs
// Symbols provided by linker script
extern "C" {
    fn end();
}

use frame_allocator::{ init as init_frame_allocator, test as test_frame_allocator };    // TODO

pub fn init() {
    unsafe {
        sstatus::set_sum(); // Allow user memory access
    }
    init_heap();
    let memory_start = (end as usize) + PAGE_SIZE;
    let memory_size = MEMORY_END - memory_start;
    init_frame_allocator(memory_start, memory_size);
    test_frame_allocator();
}

boot/linker.ld 为 end 赋值，这个是 kernel 的结束虚拟地址，此时由于尚未启用页表，虚实地址相等。在此之后是 device tree base ，我们为其留出 PAGE_SIZE 大小的空间存放

物理内存块的分配与释放

我们将内存整体视为许多连续的“块”，这里我们将每个块的大小定为 4k ，也即 PAGE_SIZE 。那么我们需要一个数据结构来管理这些块：哪些块被分配了、哪些块是空闲的、如何进行分配和释放等。buddy system 就是通过二叉树对内存块进行管理的一种算法。

  • Cargo.toml

这里提供已经写好的 buddy system 算法 ，请自行下载并放于 crate 目录下：

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

算法细节可阅读 伙伴分配器的一个极简实现 也可以直接看提供的代码

  • memory/frame_allocator/mod.rs

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

同时，为了防止多线程时内存被重复分配，需要使用互斥锁(Mutex)管理 BUDDY_ALLOCATOR 。

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

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());
}

pub fn init(start: usize, lenth: usize) {
    BUDDY_ALLOCATOR.lock()
        .init(log2_down((start + lenth - MEMORY_OFFSET) / PAGE_SIZE) as u8);
    alloc_frames((start - MEMORY_OFFSET - 1) / PAGE_SIZE + 1);
    println!("++++init frame allocator succeed!++++");
}

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

pub fn alloc_frames(size: usize) -> Option<Frame> {
    let ret = BUDDY_ALLOCATOR
        .lock()
        .alloc(size)
        .map(|id| id * PAGE_SIZE + MEMORY_OFFSET);
    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) {
    BUDDY_ALLOCATOR
        .lock()
        .dealloc(target.start_address().as_usize() / PAGE_SIZE - MEMORY_OFFSET / 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_frames(2).expect("failed to alloc frame");
    println!("test frame_allocator: {:#x}", frame2.start_address().as_usize());
    let frame3: Frame = alloc_frame().expect("failed to alloc frame");
    println!("test frame_allocator: {:#x}", frame3.start_address().as_usize());
    dealloc_frame(frame1);
    dealloc_frames(frame2, 2);
    dealloc_frame(frame3);
}
  • init.rs
#[no_mangle]
pub fn rust_main() -> ! {
    crate::interrupt::init();
    crate::clock::init();
    crate::memory::init();
    loop {}
}

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

error[E0152]: duplicate lang item found: `oom`.
  --> src/lib.rs:23:1
   |
23 | / fn foo(_: core::alloc::Layout) -> ! {
24 | |     panic!("DO NOTHING alloc_error_handler set by kernel");
25 | | }
   | |_^
   |
   = 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 冲突了。把我们实现的 alloc_error_handler 删掉即可。再次执行 make run ，编译正确，屏幕输出：

...
++++init frame allocator succeed!++++
test frame_allocator: 0x81000000
test frame_allocator: 0x81002000
test frame_allocator: 0x81001000
100 ticks!
...

仔细观察输出的地址，再思考一下 buddy system 分配内存的过程 这里输出的均为物理地址

预告

本章我们实现了内存分配，下一章我们学习管理已分配的内存的工具：页表。

results matching ""

    No results matching ""

    results matching ""

      No results matching ""