早期内存分配器的设计 - ArceOS Tutorial Book

第四节早期内存分配器的设计

在 Rust 开发中，String、Vector 之类的各种复合类型为我们带来了很大便利。但是我们的内核目前还不支持，因为没有实现动态内存分配器。我们可以来尝试一下，把 axorigin 的 main 函数改成这样：

// axorigin/src/main.rs
#![no_std]
#![no_main]

extern crate alloc;
use alloc::string::String;
use axhal::ax_println;

#[no_mangle]
pub fn main(_hartid: usize, _dtb: usize) {
    let s = String::from("from String");
    ax_println!("\nHello, ArceOS![{}]", s);
}

通过 make build 编译一下，报错：

error: no global memory allocator found but one is required; link to std or add `#[global_allocator]` to a static item that implements the GlobalAlloc trait

果然不支持，String 需要动态内存即堆管理的支持，普通 Rust 应用经由 STD 标准库去申请底层操作系统内核对内存分配的支持，但是我们本身就是在实现内核，所以只能自己实现，即 - 我们按照 Rust 框架要求，实现内核级的动态内存分配器。

内核级内存分配器需要满足两个方面的要求：

分配器必须实现 GlobalAlloc trait，如 String、Vector 等集合数据类型都需要基于这个 trait 定义接口对分配器发出要求，请求以字节为最小分配单位。
内核的很多功能都要求申请以页为基本单位，并且开始地址按页对齐的分配块。这种按页分配在内核开发中是十分常用和必要的，有必要作为独立的服务接口对外提供。

总结一下，功能上我们需要两种相互独立的内存分配器，一种基于字节分配，另一种基于页分配。

当前阶段，我们先采用最简单的设计方案，即让一个分配器同时支持两种分配功能。

分配机制：字节与页分配共用同一块内存空间，从前向后字节分配，从后向前页分配。它们分别使用一个指针维护当前到达的位置。

释放机制，同样采取最简单的策略：

针对字节分配，用 count 变量记录分配次数，仅在 count 回复到零时，才把当前位置指针重置成起始位置。也就是说，只有在所有申请的内存块全部释放时，才真正的释放空间。这样的内存使用效率当然不高，但在引导阶段这不是问题。
对于页分配，没有为它设计释放机制。一方面是为了简单，另一方面在早期内存分配器生效的这段时间，内核需要申请的页都是它这一生都需要的，所以并不需要释放。

建立新组件 axalloc 在内核中负责动态内存分配的功能。未来几章，我们将在该组件中定义一系列内存分配器，用于不同阶段和不同类型，本章首先定义早期内存分配器 EarlyAllocator：

// axalloc/src/lib.rs
#![no_std]

extern crate alloc;
mod early;

#[derive(Debug)]
pub enum AllocError {
    InvalidParam,
    MemoryOverlap,
    NoMemory,
    NotAllocated,
}
pub type AllocResult<T = ()> = Result<T, AllocError>;

// axalloc/src/early.rs
#![allow(dead_code)]
use core::alloc::Layout;
use core::ptr::NonNull;
use axconfig::{align_up, align_down, PAGE_SIZE};
use crate::{AllocResult, AllocError};

#[derive(Default)]
pub struct EarlyAllocator {
    start:  usize,
    end:    usize,
    count:  usize,
    byte_pos:  usize,
    page_pos:  usize,
}

impl EarlyAllocator {
    pub fn init(&mut self, start: usize, size: usize) {
        self.start = start;
        self.end = start + size;
        self.byte_pos = start;
        self.page_pos = self.end;
    }
    pub const fn uninit_new() -> Self {
        Self {
            start: 0, end: 0, count: 0,
            byte_pos: 0, page_pos: 0,
        }
    }
}

// axalloc/Cargo.toml
[dependencies]
axconfig = { path = "../axconfig" }

第 33~38 行：指定地址范围初始化分配器，字节分配指针 byte_pos 和页分配指针 page_pos 的初始位置分别在两端。

第 17 行：目前临时加上 #![allow(dead_code)] 以屏蔽警告，等到正式引用 EarlyAllocator 时再取消这行。

然后是字节分配功能的实现：

// axalloc/src/early.rs
impl EarlyAllocator {
    pub fn alloc_bytes(&mut self, layout: Layout) -> AllocResult<NonNull<u8>> {
        let start = align_up(self.byte_pos, layout.align());
        let next = start + layout.size();
        if next > self.page_pos {
            alloc::alloc::handle_alloc_error(layout)
        } else {
            self.byte_pos = next;
            self.count += 1;
            NonNull::new(start as *mut u8).ok_or(AllocError::NoMemory)
        }
    }

    pub fn dealloc_bytes(&mut self, _ptr: NonNull<u8>, _layout: Layout) {
        self.count -= 1;
        if self.count == 0 {
            self.byte_pos = self.start;
        }
    }

    fn total_bytes(&self) -> usize {
        self.end - self.start
    }
    fn used_bytes(&self) -> usize {
        self.byte_pos - self.start
    }
    fn available_bytes(&self) -> usize {
        self.page_pos - self.byte_pos
    }
}

第 3~13 行：字节分配方法，从前往后分配。首先对分配范围的开始位置对齐，然后计算结束位置并检查越界。注意：是否越界参照的是页分配指针 page_pos 指向的当前位置，而不是整个区域的结束位置。通过检查后，就把结束位置作为下次分配的开始搜索位置；另外，把 count 计数加一，用于记录已分配的块数。

第 15~20 行：字节释放方法，每释放一块就把计数 count 减一。当 count 减到 0 时，意味着之前分配的所有内存块都已经释放，字节分配指针回到初始位置。

第 22~30 行：监控字节分配率的三个方法，其中 available_bytes 是 page_pos 与 byte_pos 之间的区域长度。

执行 make test 先来测试一下字节分配的功能：

// axalloc/src/early.rs
#[cfg(test)]
mod tests;

// axalloc/src/early/tests.rs
use axconfig::PAGE_SIZE;
use core::alloc::Layout;
use super::EarlyAllocator;

#[test]
fn test_alloc_bytes() {
    let space: [u8; PAGE_SIZE] = [0; PAGE_SIZE];
    let base = space.as_ptr() as usize;

    let mut early = EarlyAllocator::default();
    early.init(base, PAGE_SIZE);
    assert_eq!(early.total_bytes(), PAGE_SIZE);
    assert_eq!(early.available_bytes(), PAGE_SIZE);
    assert_eq!(early.used_bytes(), 0);

    let layout = Layout::from_size_align(2, 2).unwrap();
    let p0 = early.alloc_bytes(layout).unwrap();
    assert_eq!(p0.as_ptr() as usize - base, 0);
    assert_eq!(early.used_bytes(), 2);

    let layout = Layout::from_size_align(4, 4).unwrap();
    let p1 = early.alloc_bytes(layout).unwrap();
    assert_eq!(p1.as_ptr() as usize - base, 4);
    assert_eq!(early.used_bytes(), 8);

    early.dealloc_bytes(p0, Layout::new::<usize>());
    early.dealloc_bytes(p1, Layout::new::<usize>());
    assert_eq!(early.total_bytes(), PAGE_SIZE);
    assert_eq!(early.available_bytes(), PAGE_SIZE);
    assert_eq!(early.used_bytes(), 0);
}

从后向前是为页分配准备的区域，如前所述，在内核引导的早期申请的页面会一直使用，所以只需要实现 alloc_pages：

// axalloc/src/early.rs
impl EarlyAllocator {
    pub fn alloc_pages(&mut self, layout: Layout) -> AllocResult<NonNull<u8>> {
        assert_eq!(layout.size() % PAGE_SIZE, 0);
        let next = align_down(self.page_pos - layout.size(), layout.align());
        if next <= self.byte_pos {
            alloc::alloc::handle_alloc_error(layout)
        } else {
            self.page_pos = next;
            NonNull::new(next as *mut u8).ok_or(AllocError::NoMemory)
        }
    }

    pub fn total_pages(&self) -> usize {
        (self.end - self.start) / PAGE_SIZE
    }
    pub fn used_pages(&self) -> usize {
        (self.end - self.page_pos) / PAGE_SIZE
    }
    pub fn available_pages(&self) -> usize {
        (self.page_pos - self.byte_pos) / PAGE_SIZE
    }
}

第 4 行：页分配必须按页对齐。

第 5 行：从后向前查找可分配的页内存区，并且这个待分配内存区的开始地址必须按页对齐。

第 6~7 行：检查越界 - 新申请的页内存分配区域不能与现有的字节分配区域重叠。

第 9~10 行：在 page_pos 中记录当前分配到的位置，并成功返回内存块的地址。

第 14~22 行：跟踪页分配情况的三个方法，同样，注意 available_pages 对应的是 page_pos 和 byte_pos 之间的区域长度。

现在来验证页分配功能，执行测试 make test：

// axalloc/src/early/tests.rs
#[test]
fn test_alloc_pages() {
    let num_pages = 16;
    let total_size = PAGE_SIZE * num_pages;
    let layout = Layout::from_size_align(total_size, PAGE_SIZE).unwrap();
    let space = unsafe { alloc::alloc::alloc(layout) };
    let start = space as usize;
    let end = start + total_size;

    let mut early = EarlyAllocator::default();
    early.init(start, total_size);
    assert_eq!(early.total_pages(), num_pages);
    assert_eq!(early.available_pages(), num_pages);
    assert_eq!(early.used_pages(), 0);

    let layout = Layout::from_size_align(PAGE_SIZE, PAGE_SIZE).unwrap();
    let p0 = early.alloc_pages(layout).unwrap();
    assert_eq!(p0.as_ptr() as usize, end - PAGE_SIZE);
    assert_eq!(early.used_pages(), 1);

    let layout = Layout::from_size_align(PAGE_SIZE*2, PAGE_SIZE).unwrap();
    let p1 = early.alloc_pages(layout).unwrap();
    assert_eq!(p1.as_ptr() as usize, end - PAGE_SIZE*3);
    assert_eq!(early.used_pages(), 3);
}

本节我们为内核准备了一个早期引导过程中使用的动态内存分配器，它同时支持字节分配和页分配的功能。

但是该分配还没有启用，所以如果此时 make run 去运行本节开头的 axorigin 中的新代码，仍然会报同样的错误。下节我们来启用内存分配器，让内核初步支持动态内存分配。

ArceOS Tutorial Book

第四节 早期内存分配器的设计

第四节早期内存分配器的设计