动态内存之堆的分配(二)

gejigeji Web安全 2019年11月12日发布
Favorite收藏

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

动态内存之堆的分配(一)

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函数被调用:

19.png

调用错误处理程序是因为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)。运行它时,我们看到以下内容:

27.png

正如预期的那样,我们看到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。在下一篇文章,我将详细介绍如何从头开始实现分配器,解释我会介绍多种可能的分配器设计,展示如何实现它们的简单版本,并说明其优缺点。

本文翻译自:https://os.phil-opp.com/heap-allocation/如若转载,请注明原文地址: https://www.4hou.com/web/21300.html
点赞 0
  • 分享至
取消

感谢您的支持,我会继续努力的!

扫码支持

打开微信扫一扫后点击右上角即可分享哟

发表评论