动态内存之堆的分配（一）

AllGlobalAlloctrait

GlobalAlloctrait定义了堆分配器必须提供的功能，该属性很特殊，因为程序员几乎从不直接使用它。相反，当使用分配和集合类型的alloc时，编译器会自动地将适当的调用插入到trait方法中。

因为我们需要为所有的分配器类型实现该属性，因此有必要仔细研究其声明：

pub unsafe trait GlobalAlloc {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8;
    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout);
    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 { ... }
    unsafe fn realloc(
        &self,
        ptr: *mut u8,
        layout: Layout,
        new_size: usize
    ) -> *mut u8 { ... }
}

它定义了两个必需的方法alloc和dealloc，它们对应于我们在本例中使用的分配和deallocate函数：

alloc方法将布局实例作为参数，该实例描述分配的内存应具有的所需大小和对齐方式。它返回原始指针，指向分配的内存块的第一个字节。alloc方法不是显式的错误值，而是返回一个空指针来表示分配错误。这有点不习惯，但它的优点是包装现有的系统分配器很容易，因为它们使用相同的约定。

dealloc方法是对应的，负责再次释放内存块。它接收两个参数，一个是alloc返回的指针，另一个是用于分配的布局。

该trait还定义了两个方法alloc_zeroed和realloc，它们都有默认的实现：

alloc_zeroed方法等效于调用alloc，然后将分配的内存块设置为零，这正是提供的默认实现所执行的。如果可能的话，分配器实现可以使用更有效的自定义实现来覆盖默认实现。

realloc方法允许增加或减少分配，默认实现分配一个具有所需大小的新内存块，并复制先前分配的所有内容。同样，分配器实现可能可以提供此方法的更有效实现，例如，如果可能的话，在适当的位置增加/减少分配。

要注意的一件事是，trait本身和所有trait方法都被声明为不安全的：

将该trait声明为不安全的原因是，程序员必须保证分配器类型的trait实现是正确的。例如，alloc方法绝不能返回已在其他地方使用的内存块，因为这将导致未定义的行为。

类似地，方法不安全的原因是调用者在调用方法时必须确保各种不变量，例如，传递给alloc的布局指定一个非零大小。这在实践中并不真正相关，因为编译器通常直接调用这些方法，以确保满足需求。

DummyAllocator

现在我们知道了分配器类型应该提供什么，我们可以创建一个简单的虚拟分配器。为此，我们创建了一个新的分配器模块:

// in src/lib.rs
pub mod allocator;

我们的虚拟分配器执行绝对最小值来实现特征，并且总是在调用alloc时返回一个错误。看起来像这样：

// in src/allocator.rs
use alloc::alloc::{GlobalAlloc, Layout};
use core::ptr::null_mut;
pub struct Dummy;
unsafe impl GlobalAlloc for Dummy {
    unsafe fn alloc(&self, _layout: Layout) -> *mut u8 {
        null_mut()
    }
    unsafe fn dealloc(&self, _ptr: *mut u8, _layout: Layout) {
        panic!("dealloc should be never called")
    }
}

该结构不需要任何字段，因此我们将其创建为零尺寸类型。如上所述，我们总是从alloc返回空指针，这对应于分配漏洞。因为分配器从不返回任何内存，所以对dealloc的调用应该不会发生。因此，我们只是对dealloc方法感到恐慌。 alloc_zeroed和realloc方法具有默认实现，因此我们无需为其提供实现。

现在我们有了一个简单的分配器，但是我们仍然必须告诉Rust编译器它应该使用这个分配器，这就是#[global_allocator]属性发挥作用的地方。

＃[global_allocator]属性

＃[global_allocator]属性告诉Rust编译器应该使用哪个分配器实例作为全局堆分配器。该属性仅适用于实现GlobalAlloctrait的静态对象。让我们将Dummy分配器的一个实例注册为全局分配器：

// in src/lib.rs
#[global_allocator]
static ALLOCATOR: allocator::Dummy = allocator::Dummy;

由于Dummy分配器是零大小的类型，因此我们不需要在初始化表达式中指定任何字段。注意，＃[global_allocator]模块不能在子模块中使用，因此我们需要将其放入lib.rs中。

现在，当我们尝试编译它时，第一个漏洞应该消失了。让我们修复第二个漏洞：

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

[alloc_error_handler]属性

正如我们在讨论GlobalAlloc特征时所了解的，alloc函数可以通过返回空指针来发出分配错误的信号。问题是:Rust运行时应该如何应对这样的分配失败?这就是#[alloc_error_handler]属性的作用。它指定在分配错误发生时调用的函数，类似于在发生紧急情况时调用紧急处理程序的方式。

让我们添加这样的函数来修复编译漏洞：

// in src/lib.rs
#![feature(alloc_error_handler)] // at the top of the file
#[alloc_error_handler]
fn alloc_error_handler(layout: alloc::alloc::Layout) -> ! {
    panic!("allocation error: {:?}", layout)
}

alloc_error_handler函数仍然不稳定，因此我们需要一个函数来启用它。该函数接收一个参数：发生分配失败时传递给alloc的布局实例。我们无法解决该故障，因此我们只对包含布局实例的消息感到恐慌。

使用此函数，应该修复编译错误。现在我们可以使用分配类型和集合类型的alloc，例如我们可以使用一个框来分配堆上的一个值：

// in src/main.rs
extern crate alloc;
use alloc::boxed::Box;
fn kernel_main(boot_info: &'static BootInfo) -> ! {
    // […] print "Hello World!", call `init`, create `mapper` and `frame_allocator`
    let x = Box::new(41);
    // […] call `test_main` in test mode
    println!("It did not crash!");
    blog_os::hlt_loop();
}

请注意，我们也需要在main.rs中指定extern crate alloc语句。这是必需的，因为lib.rs和main.rs部分被视为单独的crate。但是，我们不需要创建另一个＃[global_allocator]静态变量，因为全局分配器适用于项目中的所有crate。实际上，在另一个crate中指定其他分配器将会产生漏洞。

当我们运行上面的代码时，我们看到我们的alloc_error_handler函数被调用：

调用错误处理程序是因为Box::new函数隐式地调用全局分配器的alloc函数，我们的虚拟分配器总是返回一个空指针，所以每次分配都会失败。要解决这个问题，我们需要创建一个实际返回可用内存的分配器。

创建内核堆

在创建合适的分配器之前，我们首先需要创建一个堆内存区域，分配器可以从中分配内存。为此，我们需要为堆区域定义一个虚拟内存范围，然后将该区域映射到物理帧。

第一步是为堆定义一个虚拟内存区域。我们可以选择任何我们喜欢的虚拟地址范围，只要它尚未用于其他内存区域即可。让我们将其定义为从地址0x_4444_4444_0000开始的内存，以便稍后可以轻松识别堆指针：

// in src/allocator.rs
pub const HEAP_START: usize = 0x_4444_4444_0000;
pub const HEAP_SIZE: usize = 100 * 1024; // 100 KiB

我们现在将堆大小设置为100 KiB，如果我们在未来需要更多的空间，我们可以简单地增加它。

如果我们现在尝试使用这个堆区域，则会出现页面错误，因为虚拟内存区域还没有映射到物理内存。为了解决这个问题，我们创建了一个init_heap函数，它使用我们在“分页实现”中介绍的Mapper API来映射堆页面：

// in src/allocator.rs
use x86_64::{
    structures::paging::{
        mapper::MapToError, FrameAllocator, Mapper, Page, PageTableFlags, Size4KiB,
    },
    VirtAddr,
};
pub fn init_heap(
    mapper: &mut impl Mapper<Size4KiB>,
    frame_allocator: &mut impl FrameAllocator<Size4KiB>,
) -> Result<(), MapToError> {
    let page_range = {
        let heap_start = VirtAddr::new(HEAP_START as u64);
        let heap_end = heap_start + HEAP_SIZE - 1u64;
        let heap_start_page = Page::containing_address(heap_start);
        let heap_end_page = Page::containing_address(heap_end);
        Page::range_inclusive(heap_start_page, heap_end_page)
    };
    for page in page_range {
        let frame = frame_allocator
            .allocate_frame()
            .ok_or(MapToError::FrameAllocationFailed)?;
        let flags = PageTableFlags::PRESENT | PageTableFlags::WRITABLE;
        unsafe { mapper.map_to(page, frame, flags, frame_allocator)?.flush() };
    }
    Ok(())
}

该函数接受对Mapper和FrameAllocator实例的可变引用，通过使用Size4KiB作为泛型参数，这两个实例都被限制为4KiB页。该函数的返回值是一个结果，单位类型()作为成功变量，MapToError作为错误变量，这是Mapper::map_to方法返回的错误类型。在这里重用错误类型是有意义的，因为map_to方法是这个函数中错误的主要来源。

实现可以分为两部分：

创建页面范围：要创建我们要映射的页面范围，我们将HEAP_START指针转换为VirtAddr类型。然后，我们通过添加HEAP_SIZE从中计算出堆结束地址。我们需要一个包含性的边界（堆最后一个字节的地址），因此我们减去1。接下来，我们使用containing_address函数将地址转换为页面类型。最后，我们使用page:: range_inclusion函数创建从开始到结束的页面范围。

映射页面：第二步是映射我们刚刚创建的页面范围的所有页面。为此，我们使用for循环遍历该范围内的页面。对于每个页面，我们执行以下操作：

我们使用FrameAllocator :: allocate_frame方法分配页面应映射到的物理框架。当没有更多的帧时，此方法返回None。我们通过使用Option :: ok_or方法将其映射到MapToError :: FrameAllocationFailed漏洞来处理这种情况，然后应用问号运算符以在出现漏洞的情况下尽早返回。

我们为页面设置了必需的PRESENT标志和WRITABLE标志。使用这些标志，允许读取和写入访问，这对于堆内存是有意义的。

我们使用不安全的Mapper :: map_to方法在活动页面表中创建映射，该方法可能会失败，因此我们再次使用问号运算符将漏洞转发给调用方。成功后，该方法将返回一个MapperFlush实例，我们可以使用该实例使用flush方法来更新转换后备缓冲区。

最后一步是从我们的kernel_main调用此函数：

// in src/main.rs
fn kernel_main(boot_info: &'static BootInfo) -> ! {
    use blog_os::allocator; // new import
    use blog_os::memory::{self, BootInfoFrameAllocator};
    println!("Hello World{}", "!");
    blog_os::init();
    let phys_mem_offset = VirtAddr::new(boot_info.physical_memory_offset);
    let mut mapper = unsafe { memory::init(phys_mem_offset) };
    let mut frame_allocator = unsafe {
        BootInfoFrameAllocator::init(&boot_info.memory_map)
    };
    // new
    allocator::init_heap(&mut mapper, &mut frame_allocator)
        .expect("heap initialization failed");
    let x = Box::new(41);
    // […] call `test_main` in test mode
    println!("It did not crash!");
    blog_os::hlt_loop();
}

我们在这里显示上下文的完整功能，惟一的新行是blog_os :: allocator导入和对allocator :: init_heap函数的调用。如果init_heap函数返回漏洞，我们就会使用Result::expect方法，因为目前还没有合适的方法来处理这个错误。

现在，我们有一个准备使用的映射堆内存区域。 Box :: new调用仍然使用我们旧的Dummy分配器，因此运行它时，你仍然会看到“内存不足”漏洞。让我们通过使用适当的分配器来解决此问题。

使用分配器crate

由于实现分配器有些复杂，因此我们首先使用外部分配器crate。在下一篇文章中，我们将学习如何实现自己的分配器。

no_std应用程序的一个简单分配器crate是linked_list_allocator crate，它的名称来自以下事实：它使用链接列表数据结构来跟踪释放的内存区域，下一篇文章将对这种方法进行更详细的解释。

要使用crate，我们首先需要在Cargo.toml中添加对它的依赖：

# in Cargo.toml
[dependencies]
linked_list_allocator = "0.6.4"

然后，我们可以用crate提供的分配器替换虚拟分配器：

// in src/lib.rs
use linked_list_allocator::LockedHeap;
#[global_allocator]
static ALLOCATOR: LockedHeap = LockedHeap::empty();

该结构被命名为LockedHeap，因为它使用spin :: 互斥锁进行同步。这是必需的，因为多个线程可以同时访问ALLOCATOR静态对象。一如往常，在使用互斥锁时，我们需要注意不要意外导致死锁。这意味着我们不应该在中断处理程序中执行任何分配，因为它们可以在任意时间运行，并且可能会中断正在进行的分配。

仅将LockedHeap设置为全局分配器是不够的。原因是我们使用了空的构造函数，该函数创建了一个没有任何后备内存的分配器。就像我们的虚拟分配器一样，它总是在分配时返回漏洞。为了解决这个问题，我们需要在创建堆之后初始化分配器：

// in src/allocator.rs
pub fn init_heap(
    mapper: &mut impl Mapper<Size4KiB>,
    frame_allocator: &mut impl FrameAllocator<Size4KiB>,
) -> Result<(), MapToError> {
    // […] map all heap pages to physical frames
    // new
    unsafe {
        super::ALLOCATOR.lock().init(HEAP_START, HEAP_SIZE);
    }
    Ok(())
}

我们使用LockedHeap :: lock方法获取对包装后的Heap实例的排他性引用，然后在该实例上以堆边界作为参数调用init方法。重要的是在映射堆页面之后初始化堆，因为init函数已经尝试写入堆内存。

初始化堆之后，我们现在可以使用内置alloc crate的所有分配和收集类型，而不会出现漏洞：

// in src/main.rs
use alloc::{boxed::Box, vec, vec::Vec, rc::Rc};
fn kernel_main(boot_info: &'static BootInfo) -> ! {
    // […] initialize interrupts, mapper, frame_allocator, heap
    // allocate a number on the heap
    let heap_value = Box::new(41);
    println!("heap_value at {:p}", heap_value);
    // create a dynamically sized vector
    let mut vec = Vec::new();
    for i in 0..500 {
        vec.push(i);
    }
    println!("vec at {:p}", vec.as_slice());
    // create a reference counted vector -> will be freed when count reaches 0
    let reference_counted = Rc::new(vec![1, 2, 3]);
    let cloned_reference = reference_counted.clone();
    println!("current reference count is {}", Rc::strong_count(&cloned_reference));
    core::mem::drop(reference_counted);
    println!("reference count is {} now", Rc::strong_count(&cloned_reference));
    // […] call `test_main` in test context
    println!("It did not crash!");
    blog_os::hlt_loop();
}

此代码示例显示Box，Vec和Rc类型的某些用法。对于Box和Vec类型，我们使用{:p}格式说明符来打印基础堆指针。为了展示Rc，我们创建一个引用计数的堆值，并在删除实例之前和之后使用Rc::strong_count函数来打印当前引用计数(使用core::mem::drop)。运行它时，我们看到以下内容：

正如预期的那样，我们看到Box和Vec值存在于堆中，如以0x_4444_4444开头的指针所示。引用计数值的行为也与预期的一样，在克隆调用之后，引用计数为2，在删除一个实例之后，再次为1。

向量从偏移量0x800开始的原因不是装crate的值大0x800字节，而是向量需要增加其容量时发生的重新分配。例如，当向量的容量为32且我们尝试添加下一个元素时，该向量在后台分配一个容量为64的新后备数组，并复制所有元素，然后释放旧的分配。

当然，在alloc crate中有更多的分配和收集类型，我们现在可以在我们的内核中使用，包括：

1. 线程安全引用计数的指针Arc；

2. 拥有的字符串类型String和format!宏；

3. LinkedList；

4. 可增长的环形缓冲区VecDeque；

5. BinaryHeap优先级队列；

6. BTreeMap和BTreeSet。

当我们要实现线程列表，调度队列或支持异步/等待时，这些类型将变得非常有用。

添加测试

为了确保我们不会意外破坏新的分配代码，我们应该为其添加集成测试。我们首先创建一个新的tests / heap_allocation.rs文件，其内容如下：

// in tests/heap_allocation.rs
#![no_std]
#![no_main]
#![feature(custom_test_frameworks)]
#![test_runner(blog_os::test_runner)]
#![reexport_test_harness_main = "test_main"]
extern crate alloc;
use bootloader::{entry_point, BootInfo};
use core::panic::PanicInfo;
entry_point!(main);
fn main(boot_info: &'static BootInfo) -> ! {
    unimplemented!();
}
#[panic_handler]
fn panic(info: &PanicInfo) -> ! {
    blog_os::test_panic_handler(info)
}

我们重用lib.rs中的test_runner和test_panic_handler函数。由于我们要测试分配，因此我们通过extern crate alloc语句启用了alloc crate。

主函数的实现如下：

// in tests/heap_allocation.rs
fn main(boot_info: &'static BootInfo) -> ! {
    use blog_os::allocator;
    use blog_os::memory::{self, BootInfoFrameAllocator};
    use x86_64::VirtAddr;
    blog_os::init();
    let phys_mem_offset = VirtAddr::new(boot_info.physical_memory_offset);
    let mut mapper = unsafe { memory::init(phys_mem_offset) };
    let mut frame_allocator = unsafe {
        BootInfoFrameAllocator::init(&boot_info.memory_map)
    };
    allocator::init_heap(&mut mapper, &mut frame_allocator)
        .expect("heap initialization failed");
    test_main();
    loop {}
}

它与main.rs中的kernel_main函数非常相似，不同之处在于我们不调用println，不包括任何示例分配以及无条件调用test_main。

现在我们准备添加一些测试用例，首先，我们添加一个测试，该测试使用Box执行简单分配并检查分配的值，以确保基本分配有效：

// in tests/heap_allocation.rs
use blog_os::{serial_print, serial_println};
use alloc::boxed::Box;
#[test_case]
fn simple_allocation() {
    serial_print!("simple_allocation... ");
    let heap_value = Box::new(41);
    assert_eq!(*heap_value, 41);
    serial_println!("[ok]");
}

最重要的是，这个测试可以验证有没有发生分配错误。

接下来，我们迭代地构建一个大的向量，来测试由于重新分配产生的大的分配和多个分配：

// in tests/heap_allocation.rs
use alloc::vec::Vec;
#[test_case]
fn large_vec() {
    serial_print!("large_vec... ");
    let n = 1000;
    let mut vec = Vec::new();
    for i in 0..n {
        vec.push(i);
    }
    assert_eq!(vec.iter().sum::<u64>(), (n - 1) * n / 2);
    serial_println!("[ok]");
}

我们通过与第n个部分和的公式进行比较来验证和，这使我们确信所分配的值都是正确的。

作为第三个测试，我们依次创建10000个分配：

// in tests/heap_allocation.rs
#[test_case]
fn many_boxes() {
    serial_print!("many_boxes... ");
    for i in 0..10_000 {
        let x = Box::new(i);
        assert_eq!(*x, i);
    }
    serial_println!("[ok]");
}

此测试可确保分配器将释放的内存重新用于后续分配，否则分配器将耗尽内存。这似乎是一个明显的分配器需求，但是有些分配器设计并不这样做，如缓冲分配器的设计，我将在下一篇文章中解释。

让我们运行新的集成测试：

> cargo xtest --test heap_allocation
[…]
Running 3 tests
simple_allocation... [ok]
large_vec... [ok]
many_boxes... [ok]

三个测试都成功了！你还可以调用cargo xtest（不带–test参数）来运行所有单元测试和集成测试。

总结

这篇文章介绍了动态内存，并解释了为什么以及在哪里需要动态内存。我们了解了Rust的借用检查器如何防止常见漏洞，并了解了Rust的分配API的工作方式。

在使用虚拟分配器创建了Rust分配器接口的最小实现之后，我们为内核创建了一个适当的堆内存区域。为此，我们为堆定义了一个虚拟地址范围，然后使用上一篇文章中的Mapper和FrameAllocator将范围的所有页面映射到物理帧。

最后，我们添加了对linked_list_allocatorcrate的依赖性，以向内核添加适当的分配器。有了这个分配器，我们就可以使用Box，Vec以及alloc crate中的其他分配和收集类型。

虽然我们已经在本文中介绍了堆分配支持，但是我们将大部分工作留给了linked_list_allocatorcrate。在下一篇文章，我将详细介绍如何从头开始实现分配器，解释我会介绍多种可能的分配器设计，展示如何实现它们的简单版本，并说明其优缺点。