实现堆内存
本地变量与栈内存
outer 方法调用 inner 方法的栈，从上至下。
inner 方法执行完成后。
静态变量
静态变量存储在独立于堆栈的固定内存位置。
该内存位置在编译时由链接器分配，并在可执行文件中编码。
动态内存
本地变量只生存于作用域内，静态变量全局可用、不能够回收、所有权不清晰。
两者都有一个固定的大小，所以无法存储会动态增长的变量。
为了解决这些问题，编程语言都会引入第三块内存区域： heap。
假设使用 allocate 和 deallocate 来分配和释放内存：
在调用 deallocate 之后，内存变成如下图所示：
所以相对于静态变量来说，z[1] 这块内存区域，我们可以复用。
但是 z[0] 和 z[2] 永远不释放，这就造成了内存泄漏。
其它错误
除了内存泄漏，但它并不会使我们的程序更易受到攻击，还有两种类型的错误会有更严重的后果：
- use-after-free: 在 deallocate 之后尝试使用这个变量，这种错误会导致无法预料的行为，经常被攻击者利用来执行任意代码。
- double-free: 释放两次，可能会释放掉一个在 deallocate 之后又重新分配的地址，也有可能导致 use-after-free 问题。
即使是最好的程序员，也无法永远不出错误地处理这些分配和释放流程，而且每年都会有新的错误， 比如可以在搜索引擎尝试搜索 use-after-free 2024，你可以把 2024 换成当年的年份。
为了解决这些问题，java 和 python 会使用垃圾回收机制，核心思想是，编码者无需手动写 allocate 和 deallocate，而是定时暂停、 扫描程序中未使用的堆变量，然后释放掉这些内存。这样，以上错误就不会再出现，缺点是定时扫描导致的性能开销，以及长时间的暂停。
rust 使用了不一样的解决方法：它使用所有权设计，来在编译时检查动态内存操作的正确性，于是rust消灭了垃圾回收，当然也就没有性能开销了。 另一个好处是，编码者仍然对内存拥有细粒度的控制，就像 C、C++，缺点就是你会有很多编译错误需要解决。
rust 中的分配
Rust 中最重要的类型之一是 Box，它其实是堆变量的封装，使用 Box::new 接收一个变量，执行 allocate 分配一个变量大小的区域，然后将变量 的值转移到堆中。要释放这块区域，Box 中还有 Drop 特质，它会调用 deallocate。
光有 Box 肯定不够，下面的代码块，z[1]的引用被分配给了x（这被称为 borrow），紧接着z会被释放，但是你可能在代码块之外调用x。
1let x = {
2 let z = Box::new([1,2,3]);
3 &z[1]
4}; // z goes out of scope and `deallocate` is called
5println!("{}", x);
于是所有权发挥作用了，你会遇到编译错误：
borrow 一个变量和现实生活中的借一样，你没有所有权，不能销毁它。rust 通过检查在一个变量销毁前，所有的 borrow 都结束，来确保不会发生
use-after-free。
rust 的这一切都是在编译期发生的，因此不会像在 C 中手写内存管理一样产生性能开销。
实现一个操作系统的堆内存
实现堆内存，需要如下几步：
- 创建一块内存区域
- 确定一块虚拟内存区域
- 将这块区域映射到物理 frame
- 创建一个 allocator
1.1 确定内存区域
一个开始地址，一个大小，就可以确定一块区域。开始地址可以随便写，只要不与程序中的其它内存区域冲突。
1pub const HEAP_START: usize = 0x_4444_4444_0000;
2pub const HEAP_SIZE: usize = 100 * 1024; // 100 KiB
1.2 映射到物理地址
1linked_list_allocator = "0.9.0"
1// lib/allocator.rs
2use alloc::alloc::GlobalAlloc;
3use linked_list_allocator::LockedHeap;
4use x86_64::{
5 structures::paging::{
6 FrameAllocator, Mapper, mapper::MapToError, Page, PageTableFlags, Size4KiB,
7 },
8 VirtAddr,
9};
10
11pub const HEAP_START: usize = 0x_4444_4444_0000;
12pub const HEAP_SIZE: usize = 100 * 1024; // 100 KiB
13
14pub fn init_heap(
15 mapper: &mut impl Mapper<Size4KiB>,
16 frame_allocator: &mut impl FrameAllocator<Size4KiB>,
17) -> Result<(), MapToError<Size4KiB>> {
18 let page_range = {
19 let heap_start = VirtAddr::new(HEAP_START as u64);
20 let heap_end = heap_start + HEAP_SIZE - 1u64;
21 let heap_start_page = Page::containing_address(heap_start);
22 let heap_end_page = Page::containing_address(heap_end);
23 Page::range_inclusive(heap_start_page, heap_end_page)
24 };
25
26 for page in page_range {
27 let frame = frame_allocator
28 .allocate_frame()
29 .ok_or(MapToError::FrameAllocationFailed)?;
30 let flags = PageTableFlags::PRESENT | PageTableFlags::WRITABLE;
31 unsafe {
32 mapper.map_to(page, frame, flags, frame_allocator)?.flush()
33 };
34 }
35
36 unsafe {
37 ALLOCATOR.lock().init(HEAP_START, HEAP_SIZE);
38 }
39
40 Ok(())
41}
42
43#[global_allocator]
44static ALLOCATOR: LockedHeap = LockedHeap::empty();
1// src/main.rs
2...
3extern crate alloc;
4entry_point!(kernel_main);
5
6// 非测试情况，在程序崩溃的时候调用的函数
7#[cfg(not(test))] // new attribute
8#[panic_handler]
9fn panic(info: &PanicInfo) -> ! {
10 ...
11}
12
13#[cfg(test)]
14#[panic_handler]
15fn panic(info: &PanicInfo) -> ! {
16 rust_os::test_panic_handler(info)
17}
18
19fn kernel_main(boot_info: &'static BootInfo) -> ! {
20 // region use
21 ...
22 // endregion use
23
24 println!("Hello World{}", "!");
25
26 // region 异常与中断
27 rust_os::init();
28 // endregion
29
30 // region 内存映射
31 let phys_mem_offset = VirtAddr::new(boot_info.physical_memory_offset);
32 let mut mapper = unsafe { memory::init(phys_mem_offset) };
33 let mut frame_allocator = unsafe {
34 BootInfoFrameAllocator::init(&boot_info.memory_map)
35 };
36 allocator::init_heap(&mut mapper, &mut frame_allocator)
37 .expect("heap initialization failed");
38 // endregion 内存映射
39
40 // region 测试堆内存使用
41 let heap_value = Box::new(41);
42 println!("heap_value at {:p}", heap_value);
43
44 // create a dynamically sized vector
45 let mut vec = Vec::new();
46 for i in 0..500 {
47 vec.push(i);
48 }
49 println!("vec at {:p}", vec.as_slice());
50
51 // create a reference counted vector -> will be freed when count reaches 0
52 let reference_counted = Rc::new(vec![1, 2, 3]);
53 let cloned_reference = reference_counted.clone();
54 println!("current reference count is {}", Rc::strong_count(&cloned_reference));
55 core::mem::drop(reference_counted);
56 println!("reference count is {} now", Rc::strong_count(&cloned_reference));
57 // endregion 测试堆内存使用
58
59 // region 单元测试入口
60 ...
61 // endregion 单元测试入口
62
63 println!("It did not crash!");
64 rust_os::hlt_loop();
65}
我们创建了一个Box，一个Vec，一个Rc包裹的变量。
如此就实现了堆内存。注意vec分配的地址比box便宜了0x800，不是因为box值大小是0x800字节大，而是vec需要增加容量，发生了重分配。
比如vector的容量是32，我们尝试添加一个新元素，vector就分配一个新的64大小的数组，将之前的元素全部拷贝过来，这一步就会释放旧的内存。
内存 Allocator 手动实现
主要目标
- allocate 返回可用的内存区域；
- deallocate 释放指定的内存区域。
Bump Allocator
也叫 Stack Allocator。
缺点：有严重的限制，只能一次释放所有内存，释放完成后才能服用内存。 有点：很快
如下图，next永远指向可用内存的开头位置。
Linked List Allocator
缺点：性能差，可能要遍历链表才能找到一块区域。
Fixed-Size Block Allocator
- 多链表，每个链表固定大小。
- 不足大小向上取整
缺点：容易造成空间浪费。
Linux 中使用的 Fixed-Size Block Allocator 变体
Slab Allocator 和 Buddy Allocator
Pin 与自引用 struct
通过 allocate 分配在堆内存上的变量，有一个固定的地址，并且同时有一个指针类型例如 Box
但是在自引用结构中（上述提到的状态机，会用一种自引用结构实现），这种
1fn main() {
2 // 创建一个名为 SelfReferential 的 struct，其中包含一个指针字段 self_ptr。
3 let mut heap_value = Box::new(SelfReferential {
4 // 首先，使用空指针初始化， 然后使用 Box::new 在堆上分配该 struct。
5 self_ptr: 0 as *const _,
6 });
7 // 然后，我们获取到堆分配结构的内存地址，并将其存储在一个 ptr 变量中。
8 let ptr = &*heap_value as *const SelfReferential;
9 // 最后，我们将 ptr 变量赋值给 self_ptr 字段，使 struct 成为自引用 struct。
10 heap_value.self_ptr = ptr;
11 println!("heap value at: {:p}", heap_value);
12 println!("internal reference: {:p}", heap_value.self_ptr);
13
14 // 破坏自引用结构，将 heap_value 转移到了 stack 上，上面的 self_ptr 此时变成了悬空引用
15 let stack_value = mem::replace(&mut *heap_value, SelfReferential {
16 self_ptr: 0 as *const _,
17 });
18
19 // 下面的两个值不一样，结构被破坏
20 println!("value at: {:p}", &stack_value);
21 println!("internal reference: {:p}", stack_value.self_ptr);
22}
23
24struct SelfReferential {
25 self_ptr: *const Self,
26}
27// heap value at: 0x55eaf7ad09b0
28// internal reference: 0x55eaf7ad09b0
29// value at: 0x7ffccbf74a58
30// internal reference: 0x55eaf7ad09b0
原因在于 Box
Pin<Box> and Unpin
1use core::marker::PhantomPinned; // 标记类型，唯一作用是不实现 UnPin 特质
2
3struct SelfReferential {
4 self_ptr: *const Self,
5 _pin: PhantomPinned // 只要有一个字段 UnPin，整个 struct 就是 Unpin 的
6}
如下代码将会按预料报错。
1use std::mem;
2use std::marker::PhantomPinned;
3
4fn main() {
5 let mut heap_value = Box::pin(SelfReferential {
6 self_ptr: 0 as *const _,
7 _pin: PhantomPinned,
8 });
9 let ptr = &*heap_value as *const SelfReferential;
10 heap_value.self_ptr = ptr; // 报错 trait `DerefMut` is required to modify through a dereference
11 println!("heap value at: {:p}", heap_value);
12 println!("internal reference: {:p}", heap_value.self_ptr);
13
14 // break it
15 // 报错 trait `DerefMut` is required to modify through a dereference
16 let stack_value = mem::replace(&mut *heap_value, SelfReferential {
17 self_ptr: 0 as *const _,
18 _pin: PhantomPinned,
19 });
20 println!("value at: {:p}", &stack_value);
21 println!("internal reference: {:p}", stack_value.self_ptr);
22}
23
24struct SelfReferential {
25 self_ptr: *const Self,
26 _pin: PhantomPinned,
27}
现在编译器虽然修复了 self_ptr 的 move 问题，但是我们现在也无法初始化了。要想修复此问题，需要：
1use std::mem;
2use std::marker::PhantomPinned;
3use std::pin::Pin;
4
5fn main() {
6 let mut heap_value = Box::pin(SelfReferential {
7 self_ptr: 0 as *const _,
8 _pin: PhantomPinned,
9 });
10 let ptr = &*heap_value as *const SelfReferential;
11
12 // safe because modifying a field doesn't move the whole struct
13 unsafe {
14 let mut_ref = Pin::as_mut(&mut heap_value);
15 Pin::get_unchecked_mut(mut_ref).self_ptr = ptr;
16 }
17
18 println!("heap value at: {:p}", heap_value);
19 println!("internal reference: {:p}", heap_value.self_ptr);
20
21 // break it
22 // 现在这段代码，只有这里报错了。这里是我们需要它报错，我们不希望将 heap 上的变量 move 到 stack 上。
23 let stack_value = mem::replace(&mut *heap_value, SelfReferential {
24 self_ptr: 0 as *const _,
25 _pin: PhantomPinned,
26 });
27 println!("value at: {:p}", &stack_value);
28 println!("internal reference: {:p}", stack_value.self_ptr);
29}
30
31struct SelfReferential {
32 self_ptr: *const Self,
33 _pin: PhantomPinned,
34}
