引言

想起我們之前在學(xué)習(xí)C的時(shí)候,總是提到 malloc ,總是提起,使用 malloc 現(xiàn)場申請(qǐng)的內(nèi)存是屬于 堆 ,而直接定義的變量內(nèi)存屬于 棧 .

還記得當(dāng)初學(xué)習(xí)STM32的時(shí)候CubeIDE要設(shè)置 stack 和 heap 的大小.

但是我們要記得,這么好用的功能,實(shí)際上是 操作系統(tǒng)在負(fù)重前行 .

那么為了實(shí)現(xiàn)動(dòng)態(tài)內(nèi)存分配功能,操作系統(tǒng)需要有如下功能:

• 初始時(shí)能提供一塊大內(nèi)存空間作為初始的“堆”。在沒有分頁機(jī)制情況下，這塊空間是物理內(nèi)存空間，否則就是虛擬內(nèi)存空間。
• 提供在堆上分配和釋放內(nèi)存的函數(shù)接口。這樣函數(shù)調(diào)用方通過分配內(nèi)存函數(shù)接口得到地址連續(xù)的空閑內(nèi)存塊進(jìn)行讀寫，也能通過釋放內(nèi)存函數(shù)接口回收內(nèi)存，以備后續(xù)的內(nèi)存分配請(qǐng)求。
• 提供空閑空間管理的連續(xù)內(nèi)存分配算法。相關(guān)算法能動(dòng)態(tài)地維護(hù)一系列空閑和已分配的內(nèi)存塊，從而有效地管理空閑塊。
• （可選）提供建立在堆上的數(shù)據(jù)結(jié)構(gòu)和操作。有了上述基本的內(nèi)存分配與釋放

動(dòng)態(tài)內(nèi)存分配

實(shí)現(xiàn)方法

動(dòng)態(tài)內(nèi)存分配的實(shí)現(xiàn)方法 :

應(yīng)用另外放置了一個(gè)大小可以隨著應(yīng)用的運(yùn)行動(dòng)態(tài)增減的內(nèi)存空間 – 堆（Heap）。同時(shí)，應(yīng)用還要能夠?qū)⑦@個(gè)堆管理起來，即支持在運(yùn)行的時(shí)候從里面分配一塊空間來存放變量，而在變量的生命周期結(jié)束之后，這塊空間需要被回收以待后面的使用。如果堆的大小固定，那么這其實(shí)就是一個(gè)連續(xù)內(nèi)存分配問題，同學(xué)們可以使用操作系統(tǒng)課上所介紹到的 各種連續(xù)內(nèi)存分配算法 。

內(nèi)存碎片

動(dòng)態(tài)內(nèi)存分配的弊端---內(nèi)存碎片 :

應(yīng)用進(jìn)行多次不同大小的內(nèi)存分配和釋放操作后，會(huì)產(chǎn)生內(nèi)存空間的浪費(fèi)，即存在無法被應(yīng)用使用的空閑內(nèi)存碎片。

內(nèi)存碎片是指無法被分配和使用的空閑內(nèi)存空間�？蛇M(jìn)一步細(xì)分為內(nèi)碎片和外碎片：

• 內(nèi)碎片：已被分配出去（屬于某個(gè)在運(yùn)行的應(yīng)用）內(nèi)存區(qū)域，占有這些區(qū)域的應(yīng)用并不使用這塊區(qū)域，操作系統(tǒng)也無法利用這塊區(qū)域。
• 外碎片：還沒被分配出去（不屬于任何在運(yùn)行的應(yīng)用）內(nèi)存空閑區(qū)域，由于太小而無法分配給提出申請(qǐng)內(nèi)存空間的應(yīng)用。

STD庫中的動(dòng)態(tài)內(nèi)存分配

這里 首先提到了在 STD 庫中的堆相關(guān)的數(shù)據(jù)結(jié)構(gòu).可以自行閱讀并且大概理解下圖.

但是這一部分向我們傳達(dá)的信息是:

1. rust編程可以很優(yōu)雅地實(shí)現(xiàn)動(dòng)態(tài)內(nèi)存管理
2. std庫提供了動(dòng)態(tài)內(nèi)存管理的方法
3. 但是我們的操作系統(tǒng)內(nèi)核只能使用rust的core庫來實(shí)現(xiàn),因此需要重視和借用這些std庫里的方法

在內(nèi)核中支持動(dòng)態(tài)內(nèi)存分配

如上部分所說:

上述與堆相關(guān)的智能指針或容器都可以在 Rust 自帶的 alloc crate 中找到。當(dāng)我們使用 Rust 標(biāo)準(zhǔn)庫 std 的時(shí)候可以不用關(guān)心這個(gè) crate ，因?yàn)闃?biāo)準(zhǔn)庫內(nèi)已經(jīng)已經(jīng)實(shí)現(xiàn)了一套堆管理算法，并將 alloc 的內(nèi)容包含在 std 名字空間之下讓開發(fā)者可以直接使用。然而操作系統(tǒng)內(nèi)核運(yùn)行在禁用標(biāo)準(zhǔn)庫（即 no_std ）的裸機(jī)平臺(tái)上，核心庫 core 也并沒有動(dòng)態(tài)內(nèi)存分配的功能，這個(gè)時(shí)候就要考慮利用 alloc 庫定義的接口來實(shí)現(xiàn)基本的動(dòng)態(tài)內(nèi)存分配器。

具體實(shí)現(xiàn)這個(gè) 動(dòng)態(tài)內(nèi)存分配器 ,是為自己實(shí)現(xiàn)的這個(gè) 結(jié)構(gòu)體 ,實(shí)現(xiàn) GlobalAlloc 的 Trait .

alloc 庫需要我們提供給它一個(gè) 全局的動(dòng)態(tài)內(nèi)存分配器 ，它會(huì)利用該分配器來管理堆空間，從而使得與堆相關(guān)的智能指針或容器數(shù)據(jù)結(jié)構(gòu)可以正常工作。具體而言，我們的動(dòng)態(tài)內(nèi)存分配器需要實(shí)現(xiàn)它提供的 GlobalAlloc Trait

GlobalAlloc 的抽象接口:

// alloc::alloc::GlobalAlloc

pub unsafe fn alloc(&self, layout: Layout) -> *mut u8;
pub unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout);

可以看到，它們類似 C 語言中的 malloc/free ，分別代表堆空間的分配和回收，也同樣使用一個(gè)裸指針（也就是地址）作為分配的返回值和回收的參數(shù)。兩個(gè)接口中都有一個(gè) alloc::alloc::Layout 類型的參數(shù)， 它指出了分配的需求，分為兩部分，分別是所需空間的大小 size ，以及返回地址的對(duì)齊要求 align 。這個(gè)對(duì)齊要求必須是一個(gè) 2 的冪次，單位為字節(jié)數(shù)，限制返回的地址必須是 align 的倍數(shù)。

具體編程實(shí)現(xiàn)

引入已有的內(nèi)存分配器庫

在 os/Cargo.toml 中引入:

buddy_system_allocator = "0.6"

引入 alloc 庫

在 os/src/main.rs 中引入.

// os/src/main.rs

extern crate alloc;

實(shí)例化全局動(dòng)態(tài)內(nèi)存分配器

創(chuàng)建 os/src/mm/heap_allocator.rs .

// os/src/mm/heap_allocator.rs

use buddy_system_allocator::LockedHeap;
use crate::config::KERNEL_HEAP_SIZE;

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

static mut HEAP_SPACE: [u8; KERNEL_HEAP_SIZE] = [0; KERNEL_HEAP_SIZE];

pub fn init_heap() {
    unsafe {
        HEAP_ALLOCATOR
            .lock()
            .init(HEAP_SPACE.as_ptr() as usize, KERNEL_HEAP_SIZE);
    }
}

可以看到 實(shí)例化 了一個(gè)靜態(tài)變量 HEAP_ALLOCATOR .并且 實(shí)例化 了一個(gè)數(shù)組 HEAP_SPACE 來作為它的 堆 .

其中. HEAP_SPACE 的大小為 KERNEL_HEAP_SIZE .

那么這個(gè) KERNEL_HEAP_SIZE 是取自 config 這個(gè)包的.

這里根據(jù) 代碼倉庫里的代碼 來設(shè)置 KERNEL_HEAP_SIZE 的大小.

// os/src/config.rs
pub const KERNEL_HEAP_SIZE: usize = 0x30_0000;

大小為 3145728 .

標(biāo)注全局動(dòng)態(tài)內(nèi)存分配器的語義項(xiàng)

注意上一段的代碼,要標(biāo)注 #[global_allocator] 這樣這里的內(nèi)存分配器才能被識(shí)別為全局動(dòng)態(tài)內(nèi)存分配器.

#[global_allocator]

處理動(dòng)態(tài)內(nèi)存分配失敗的情形

需要 開啟條件編譯 ,所以需要在 main.rs 里聲明:

#![feature(alloc_error_handler)]

這時(shí)候就可以在 os/src/mm/heap_allocator.rs 里創(chuàng)建處理函數(shù)了:

// os/src/mm/heap_allocator.rs

#[alloc_error_handler]
pub fn handle_alloc_error(layout: core::alloc::Layout) -> ! {
    panic!("Heap allocation error, layout = {:?}", layout);
}

測試實(shí)現(xiàn)效果

創(chuàng)建測試函數(shù)

在 os/src/mm/heap_allocator.rs 里創(chuàng)建測試函數(shù).

#[allow(unused)]
pub fn heap_test() {
    use alloc::boxed::Box;
    use alloc::vec::Vec;
    extern "C" {
        fn sbss();
        fn ebss();
    }
    let bss_range = sbss as usize..ebss as usize;
    let a = Box::new(5);
    assert_eq!(*a, 5);
    assert!(bss_range.contains(&(a.as_ref() as *const _ as usize)));
    drop(a);
    let mut v: Vec = Vec::new();
    for i in 0..500 {
        v.push(i);
    }
    for i in 0..500 {
        assert_eq!(v[i], i);
    }
    assert!(bss_range.contains(&(v.as_ptr() as usize)));
    drop(v);
    println!("heap_test passed!");
}

這里的 #[allow(unused)] 很有意思,可以 阻止編譯器對(duì)你因?yàn)檎{(diào)試暫時(shí)不調(diào)用的函數(shù)報(bào)錯(cuò) .

這里注意使用了 println ,在文件最上邊加一句 use crate::println .

這里的測試程序先獲取了 sbss 的到 ebss 的范圍.

這里回顧清零 bss 段的代碼:

1. bss 段本身是一個(gè)儲(chǔ)存未初始化的全局變量的內(nèi)存區(qū)域
2. sbss 是 bss 的開頭 ebss 是 bss 的結(jié)尾

那么 bss_range 實(shí)際上是 bss 的范圍.

根據(jù) 這里 ,理解 Box::new(5) 是嘗試在堆上儲(chǔ)存 a 的值,且這個(gè)值為 5 .

那么下邊的斷言語句:

assert_eq!(*a, 5);
assert!(bss_range.contains(&(a.as_ref() as *const _ as usize)));

就很好理解了:

1. 判斷 a 的值是否為 5
2. 判斷 a 的指針是否在 bss 的范圍內(nèi)

隨后的操作則是創(chuàng)建了一個(gè) Vec 容器,然后儲(chǔ)存了 0..500 的值進(jìn)去,并且分別執(zhí)行上述對(duì) a 的斷言判斷.

如果斷言沒有報(bào)錯(cuò),那么最后自然會(huì)輸出 heap_test passed! .

(最后注意 drop 是在堆(動(dòng)態(tài)內(nèi)存)里釋放掉某個(gè)變量)

使mm包可調(diào)用

在 os/src/mm 下創(chuàng)建 mod.rs 使得 mm 可以被識(shí)別為一個(gè)包.

為了使用 heap_allocator 里的 init_heap 和 heap_test ,需要公開聲明這個(gè) mod :

// os/src/mm/mod.rs
pub mod heap_allocator;

編輯 main 函數(shù),實(shí)現(xiàn)測試

// os/src/main.rs

/// the rust entry-point of os
#[no_mangle]
pub fn rust_main() -> ! {
    clear_bss();
    println!("[kernel] Hello, world!");
    logging::init();
    println!("[kernel] logging init end");
    mm::heap_allocator::init_heap();
    println!("[kernel] heap init end");
    mm::heap_allocator::heap_test();
    println!("heap test passed");
    trap::init();
    println!("[kernel] trap init end");
    loader::load_apps();
    trap::enable_timer_interrupt();
    timer::set_next_trigger();
    task::run_first_task();
    panic!("Unreachable in rust_main!");
}

運(yùn)行測試

cd os
make run

得到運(yùn)行結(jié)果:

[rustsbi] RustSBI version 0.3.1, adapting to RISC-V SBI v1.0.0
.______       __    __      _______.___________.  _______..______   __
|   _  \     |  |  |  |    /       |           | /       ||   _  \ |  |
|  |_)  |    |  |  |  |   |   (----`---|  |----`|   (----`|  |_)  ||  |
|      /     |  |  |  |    \   \       |  |      \   \    |   _  < |  |
|  |\  \----.|  `--'  |.----)   |      |  |  .----)   |   |  |_)  ||  |
| _| `._____| \______/ |_______/       |__|  |_______/    |______/ |__|
[rustsbi] Implementation     : RustSBI-QEMU Version 0.2.0-alpha.2
[rustsbi] Platform Name      : riscv-virtio,qemu
[rustsbi] Platform SMP       : 1
[rustsbi] Platform Memory    : 0x80000000..0x88000000
[rustsbi] Boot HART          : 0
[rustsbi] Device Tree Region : 0x87000000..0x87000f02
[rustsbi] Firmware Address   : 0x80000000
[rustsbi] Supervisor Address : 0x80200000
[rustsbi] pmp01: 0x00000000..0x80000000 (-wr)
[rustsbi] pmp02: 0x80000000..0x80200000 (---)
[rustsbi] pmp03: 0x80200000..0x88000000 (xwr)
[rustsbi] pmp04: 0x88000000..0x00000000 (-wr)
[kernel] Hello, world!
heap_test passed!
[kernel] IllegalInstruction in application, kernel killed it.
All applications completed!

這里我為了log比較簡短,把 user 里需要編譯的app只保留了一個(gè) user/src/bin/00hello_world.rs .

這里看log, heap_test passed! ,說明測試成功了.