Rust 学习笔记

目录

1. 基础语法
2. 所有权系统
3. 结构体与枚举
4. 错误处理
5. 并发编程
6. 高级特性
7. 实用工具

基础语法

变量与可变性

1
2
3

let x = 5;          // 不可变绑定
let mut y = 10;     // 可变绑定
const PI: f64 = 3.14; // 常量

数据类型

• ‌标量类型‌：

  • 整数: i32, u64
  • 浮点: f64
  • 布尔: bool
  • 字符: char (4字节Unicode)

• ‌复合类型‌：

  1 2 3 4 5

  // 元组 let tup: (i32, f64, char) = (500, 6.4, 'A'); // 数组 let arr: [i32; 3] = [1, 2, 3];

控制流

1
2
3
4
5
6
7
8
9
10
11
12
13

// if表达式
let number = if condition { 5 } else { 6 };

// 循环
for i in 1..=5 {
    println!("{}", i);
}

// 模式匹配
match value {
    1 => println!("one"),
    _ => println!("other"),
}

所有权系统

三大规则

1. 每个值有且只有一个所有者
2. 值在作用域结束时自动释放
3. 所有权可通过移动(move)转移

示例

1
2
3

let s1 = String::from("hello");
let s2 = s1;  // s1的所有权转移到s2
// println!("{}", s1); // 错误！s1已失效

借用规则

• 同一时间，要么：
  • 只能有一个可变引用(&mut T)
  • 或多个不可变引用(&T)
• 引用必须总是有效的

1
2
3

fn calculate_length(s: &String) -> usize {
    s.len()
}

结构体与枚举

结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

struct User {
    username: String,
    email: String,
    sign_in_count: u64,
}

impl User {
    // 关联函数
    fn new(name: String, email: String) -> Self {
        User {
            username: name,
            email,
            sign_in_count: 1,
        }
    }
    
    // 方法
    fn greet(&self) {
        println!("Hello, {}!", self.username);
    }
}

枚举与模式匹配

1
2
3
4
5
6
7
8
9
10
11

enum IpAddr {
    V4(u8, u8, u8, u8),
    V6(String),
}

let home = IpAddr::V4(127, 0, 0, 1);

match home {
    IpAddr::V4(a, b, c, d) => println!("IPv4: {}.{}.{}.{}", a, b, c, d),
    IpAddr::V6(s) => println!("IPv6: {}", s),
}

错误处理

Result类型

1
2
3
4
5
6
7
8

use std::fs::File;

let f = File::open("hello.txt");

let f = match f {
    Ok(file) => file,
    Err(error) => panic!("打开文件失败: {:?}", error),
};

?运算符

1
2
3
4
5
6
7
8

use std::io;
use std::io::Read;

fn read_username_from_file() -> Result<String, io::Error> {
    let mut s = String::new();
    File::open("hello.txt")?.read_to_string(&mut s)?;
    Ok(s)
}

并发编程

线程

1
2
3
4
5
6
7

use std::thread;

let handle = thread::spawn(|| {
    println!("来自线程的消息");
});

handle.join().unwrap();

通道

1
2
3
4
5
6
7
8
9
10

use std::sync::mpsc;

let (tx, rx) = mpsc::channel();

thread::spawn(move || {
    tx.send(42).unwrap();
});

let received = rx.recv().unwrap();
println!("收到: {}", received);

高级特性

生命周期

1
2
3

fn longest<'a>(x: &'a str, y: &'a str) -> &'a str {
    if x.len() > y.len() { x } else { y }
}

Trait

1
2
3
4
5
6
7
8
9

trait Greet {
    fn greet(&self);
}

impl Greet for String {
    fn greet(&self) {
        println!("Hello, {}!", self);
    }
}

实用工具

常用Cargo命令

1
2
3
4
5

cargo new project_name  # 创建新项目
cargo build            # 编译项目
cargo run              # 编译并运行
cargo test             # 运行测试
cargo doc --open       # 生成文档并打开

推荐工具链

• rustup: Rust版本管理工具
• rust-analyzer: IDE插件
• clippy: 代码检查工具

学习资源

• The Rust Book
• Rust by Example
• Rust标准库文档
• Crates.io (第三方库仓库)

rcore 学习笔记

目录

1. 批处理系统
2. 多道程序与分时多任务
3. 地址空间
4. 进程与进程管理
5. 文件系统与I/O重定向
6. 进程间通信
7. 并发

批处理系统

一、批处理系统概述

批处理系统(Batch System)是一种用于管理无需或仅需少量用户交互即可运行程序的操作系统模型‌。它能够自动安排程序的执行顺序，在资源允许的情况下高效运行多个程序‌。批处理系统的主要特点包括：

• 自动调度多个作业顺序执行
• 提高CPU和I/O设备利用率
• 减少人工干预
• 适用于计算密集型任务‌

二、RISC-V特权级架构

批处理系统实现的基础是RISC-V的特权级机制‌：

1. ‌用户模式(U-mode)‌：应用程序运行的特权级
2. ‌监督者模式(S-mode)‌：操作系统内核运行的特权级
3. ‌机器模式(M-mode)‌：最底层硬件操作特权级

特权级机制的根本原因是确保操作系统的安全性，限制应用程序的两种行为：

• 不能访问任意的地址空间
• 不能执行某些可能危害系统的指令‌

三、批处理系统实现要点

3.1 应用程序设计

1. ‌内存布局‌：通过链接脚本调整应用程序的内存布局‌
2. ‌系统调用‌：应用程序通过ecall指令请求操作系统服务‌
3. ‌二进制转换‌：将应用程序从ELF格式转化为binary格式‌

3.2 系统实现流程

1. ‌初始化Trap机制‌：
   • 设置stvec寄存器指向trap处理入口(__alltraps)‌
   • 定义TrapContext结构保存寄存器状态‌
2. ‌任务调度‌：
   • 依次加载并执行内存中的多个程序‌
   • 通过ecall指令实现特权级切换‌
3. ‌上下文保存与恢复‌：
   • 保存用户程序寄存器状态到TrapContext
   • 处理完成后恢复上下文继续执行‌

四、关键代码分析

4.1 Trap初始化代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// os/src/main.rs
#[no_mangle]
pub fn rust_main() -> ! {
    clear_bss();
    println!("[kernel] Hello, world!");
    trap::init();
    ...
}

// os/trap/mod.rs
global_asm!(include_str!("trap.S"));

/// initialize CSR `stvec` as the entry of `__alltraps`
pub fn init() {
    extern "C" { fn __alltraps(); }
    unsafe {
        stvec::write(__alltraps as usize, TrapMode::Direct);
    }
}

4.2 Trap上下文结构

1
2
3
4
5
6
7
8
9

// os/trap/context.rs
pub struct TrapContext {
    /// general regs[0..31]
    pub x: [usize; 32],
    /// CSR sstatus
    pub sstatus: Sstatus,
    /// CSR sepc
    pub sepc: usize,
}

五、批处理系统工作流程

1. 系统启动时初始化Trap机制‌
2. 加载多个应用程序到内存‌
3. 依次执行每个应用程序：
   • 应用程序通过ecall触发系统调用‌
   • CPU切换到S模式，跳转到__alltraps‌
   • 保存应用程序上下文到TrapContext‌
   • 执行系统调用处理程序
   • 恢复上下文，返回用户程序继续执行‌
4. 当前程序执行完成后，加载并执行下一个程序‌

六、与后续章节的关联

批处理系统是多道程序与分时多任务系统的基础‌。后续章节将在批处理系统基础上实现：

• 提前加载应用程序到内存减少切换开销‌
• 协作机制支持程序主动放弃处理器‌
• 抢占机制支持程序被动放弃处理器‌

多道程序与分时多任务

一、基本概念与设计目标

多道程序设计是指允许多个程序同时进入计算机主存储器并启动计算的方法‌。分时系统是多道程序设计的延伸，通过高频率的任务切换实现用户与系统的交互‌。rCore实现这两种机制的核心目标是：

• 提高系统性能和效率
• 减少应用程序切换开销
• 通过协作机制支持程序主动放弃处理器
• 通过抢占机制保证处理器资源使用的公平性‌

二、多道程序的放置与加载

2.1 内存布局设计

在rCore中，每个应用程序需要按照编号被分别放置到内存中不同位置，这与第二章将所有程序复制到同一内存区域不同‌。实现方法包括：

• 通过链接脚本指定每个应用程序的起始地址
• 内核运行时正确获取地址并将应用代码放置到指定位置‌

2.2 地址空间问题

每个应用程序需要知道自己运行时在内存中的位置，这给编写带来麻烦。操作系统也需要知道每个程序的位置，不能任意移动应用程序所在的内存空间‌。这种限制导致：

• 无法在运行时根据内存空闲情况动态调整程序位置
• 可能影响后续对内存碎片空间的利用‌

三、任务切换机制

3.1 基本概念

• ‌任务‌：应用程序的一个计算阶段的执行过程‌
• ‌任务切换‌：从一个程序的任务切换到另一个程序的任务‌
• ‌任务上下文‌：任务切换和恢复时相关的寄存器集合‌

3.2 切换流程

任务切换通过内核栈上的task_context压入和弹出实现‌，具体分为五个阶段：

1. Trap执行流A调用__switch前，A内核栈只有Trap上下文和调用栈信息
2. A在内核栈分配任务上下文空间保存寄存器快照，更新task_cx_ptr
3. 读取B的task_cx_ptr获取B内核栈栈顶位置，切换sp寄存器实现执行流切换
4. CPU从B内核栈取出任务上下文恢复寄存器状态
5. B从调用__switch位置继续执行‌

四、关键数据结构与实现

4.1 TrapContext结构

1
2
3
4
5
6

#[repr(C)]
pub struct TrapContext {
    pub x: [usize; 32],    // 通用寄存器
    pub sstatus: Sstatus,  // 状态寄存器
    pub sepc: usize,       // 异常程序计数器
}

该结构用于保存和恢复任务状态，在os/src/trap/context.rs中定义‌。

4.2 系统调用处理

在trap_handler中对用户态环境调用(Exception::UserEnvCall)的处理：

1
2
3
4

Trap::Exception(Exception::UserEnvCall) => {
    cx.sepc += 4;
    cx.x = syscall(cx.x[...]);
}

通过修改sepc和x寄存器实现系统调用返回‌。

五、分时多任务实现机制

5.1 协作式调度

• 程序通过主动调用yield系统调用放弃CPU
• 提高系统执行效率但依赖程序配合‌

5.2 抢占式调度

• 通过时钟中断强制任务切换
• 保证不同程序对处理器资源的公平使用
• 提高对I/O事件的响应效率‌

地址空间

一、地址空间基本概念

1.1 虚拟地址与物理地址

• ‌虚拟地址‌：应用程序使用的逻辑地址，由操作系统和硬件共同维护的抽象层‌
• ‌物理地址‌：实际内存硬件使用的地址，由CPU地址线直接访问‌
• ‌转换机制‌：通过MMU(Memory Management Unit)硬件单元实现虚拟地址到物理地址的转换‌

1.2 地址空间定义

地址空间是指程序在运行时用于访问内存的逻辑地址集合，包含：

• 用户地址空间：每个应用程序独占的虚拟地址范围‌
• 内核地址空间：操作系统内核使用的虚拟地址范围‌

二、地址空间实现原理

2.1 SV39分页机制

RISC-V采用SV39分页方案，主要特点包括：

• 39位虚拟地址空间，支持512GB寻址‌
• 三级页表结构（页全局目录、页中间目录、页表）‌
• 页大小为4KB，作为基本映射单位‌

2.2 页表管理

• ‌satp寄存器：控制分页模式，存储根页表物理地址‌
  • MODE字段：设置为8表示启用SV39分页‌
  • PPN字段：存储一级页表物理页号‌
• ‌页表项结构‌：包含物理页号、访问权限等控制位‌

三、地址空间隔离与保护

3.1 隔离机制

• ‌应用间隔离‌：每个应用有独立的页表，V标记位控制有效访问范围‌
• ‌内核保护‌：页表项U位控制用户态访问权限‌
• ‌空分复用‌：不同应用可使用相同虚拟地址映射到不同物理页‌

3.2 内存安全

通过地址空间机制实现：

• 防止应用随意访问其他应用或内核数据‌
• 避免物理内存布局冲突，简化应用开发‌
• 增强系统整体安全性和稳定性‌

四、关键数据结构与实现

4.1 页表相关结构

1
2
3
4
5
6
7
8
9
10

// 页表项定义
struct PageTableEntry {
    bits: usize,  // 存储物理页号和标志位
}

impl PageTableEntry {
    fn ppn(&self) -> PhysPageNum { /*...*/ }
    fn flags(&self) -> PTEFlags { /*...*/ }
    fn is_valid(&self) -> bool { /*...*/ }
}

4.2 地址空间管理

• ‌MemorySet结构：管理应用的地址空间‌
  • 包含页表、内存区域映射等信息
  • 实现地址映射的建立与销毁

五、地址空间工作流程

1. ‌初始化阶段‌：
   • 创建内核地址空间‌
   • 设置satp寄存器启用分页‌
2. ‌应用加载‌：
   • 为应用创建独立地址空间‌
   • 建立代码段、数据段等内存映射‌
3. ‌运行时‌：
   • MMU自动完成地址转换‌
   • 页错误异常处理‌

进程与进程管理

一、进程基本概念

1.1 进程定义

进程是正在运行并使用计算机资源的程序，是操作系统资源分配的基本单位‌。在rCore中，进程由以下部分组成：

• 程序代码和数据段
• 虚拟内存空间
• 进程控制块(PCB)‌

1.2 进程与程序区别

• ‌程序‌：静态的可执行文件
• ‌进程‌：动态的执行实体，具有生命周期‌

1.3 进程控制块(PCB)

PCB是进程存在的唯一标志，包含：

• 进程标识符(PID)
• 处理机状态(寄存器值等)
• 进程调度信息
• 进程控制信息‌

二、rCore进程管理实现

2.1 进程相关系统调用

rCore实现了以下关键进程管理系统调用：

• fork()：创建与当前进程相同的子进程‌
• wait_pid()：父进程等待子进程结束‌
• exec()：用新程序替换当前进程‌

2.2 进程创建流程

1. 系统启动时加载初始进程(initproc)‌
2. initproc通过fork创建shell进程‌
3. shell根据用户输入创建其他进程‌

2.3 进程调度

rCore采用以下调度策略：

• 协作式调度：进程主动放弃CPU
• 抢占式调度：通过时钟中断强制切换‌

三、关键数据结构

3.1 进程控制块实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 进程状态定义
pub enum TaskStatus {
    Ready,
    Running,
    Blocked,
}

// 进程控制块结构
pub struct TaskControlBlock {
    pub pid: usize,          // 进程ID
    pub status: TaskStatus,  // 进程状态
    pub context: TaskContext,// 进程上下文
    pub memory_set: MemorySet, // 地址空间
    // 其他字段...
}

3.2 进程上下文

1
2
3
4
5
6

#[repr(C)]
pub struct TaskContext {
    pub ra: usize,       // 返回地址
    pub sp: usize,       // 栈指针
    pub s: [usize; 12], // 保存的寄存器
}

四、进程生命周期管理

4.1 进程创建

• 分配新的PID
• 创建地址空间
• 初始化进程上下文‌

4.2 进程切换

1. 保存当前进程上下文
2. 选择下一个要运行的进程
3. 恢复新进程上下文‌

4.3 进程终止

• 释放占用的资源
• 通知父进程
• 从进程表中移除‌

五、进程间通信

5.1 共享内存

通过地址空间机制实现进程间数据共享‌

5.2 信号量

提供同步原语，协调进程执行顺序‌

文件系统与I/O重定向

一、文件系统基础概念

1.1 文件系统作用

文件系统是操作系统用于持久存储数据的关键组件，主要解决内存易失性与外存持久性之间的矛盾‌。rCore文件系统实现了：

• 数据持久化存储
• 文件命名与组织
• 访问控制与权限管理‌

1.2 存储设备分类

UNIX系统将I/O设备分为三类：

1. ‌块设备‌：如磁盘，以固定大小块(512B-32KB)为单位传输‌
2. ‌字符设备‌：如键盘/串口，以字符流为单位传输‌
3. ‌网络设备‌：面向报文传输，BSD引入socket接口处理‌

二、文件系统核心结构

2.1 磁盘布局

rCore文件系统采用类UNIX布局：

• ‌超级块‌：记录文件系统元信息
• ‌inode区‌：文件索引节点存储
• ‌数据块区‌：实际文件内容存储‌

2.2 关键数据结构

1
2
3
4
5
6
7
8
9

// 文件系统超级块
struct SuperBlock {
    magic: u32,          // 文件系统魔数
    blocks: u32,         // 总块数
    inode_bitmap: u32,   // inode位图起始块
    data_bitmap: u32,    // 数据块位图起始块
    inode_area: u32,     // inode区域起始块
    data_area: u32,      // 数据区域起始块
}

三、文件操作接口

3.1 系统调用接口

rCore实现以下核心文件操作：

• open()：打开/创建文件‌
• read()/write()：文件读写‌
• lseek()：调整文件指针位置‌
• close()：关闭文件描述符‌

3.2 文件描述符

每个进程维护文件描述符表：

• 0：标准输入(stdin)
• 1：标准输出(stdout)
• 2：标准错误(stderr)
• ≥3：用户打开的文件‌

四、I/O重定向机制

4.1 重定向类型

• ‌输入重定向‌：< 将文件内容作为程序输入‌
• ‌输出重定向‌：> 覆盖写入文件，>> 追加写入‌
• ‌错误重定向‌：2> 重定向stderr‌

4.2 实现原理

通过修改进程文件描述符表实现：

1. 打开目标文件获取新fd
2. 关闭原标准流fd(0/1/2)
3. 复制新fd到标准流位置‌

五、管道通信机制

5.1 管道特点

• 半双工通信，包含读端和写端‌
• 基于队列的有限缓冲区‌
• 读空/写满时阻塞等待‌

5.2 使用示例

1
2
3
4
5
6
7
8
9

// 创建管道
let mut pipe_fd = [0usize; 2];
pipe(&mut pipe_fd);

// 子进程读管道
if fork() == 0 {
    close(pipe_fd); // 关闭写端
    read(pipe_fd, &mut buffer);
}

六、设备驱动实现

6.1 virtio驱动

rCore通过virtio协议访问块设备：

• 设备树信息由OpenSBI提供‌
• 使用DMA提高传输效率‌
• 实现磁盘块缓存优化性能‌

6.2 三种I/O方式

1. ‌PIO‌：CPU直接控制I/O‌
2. ‌中断驱动‌：设备就绪后通知CPU‌
3. ‌DMA‌：设备直接访问内存‌

并发

一、并发基础概念

1.1 并发与并行区别

• ‌并发‌：多个任务交替执行，宏观上”同时”运行‌
• ‌并行‌：多个任务真正同时执行，需要多核硬件支持‌

1.2 并发实现方式

rCore主要采用以下并发模型：

• 多道程序：通过任务切换实现并发‌
• 分时多任务：基于时间片轮转调度‌
• 多线程：轻量级执行单元共享地址空间‌

二、任务调度机制

2.1 任务控制块(TCB)

1
2
3
4
5

struct TaskControlBlock {
    task_cx: TaskContext,  // 任务上下文
    task_status: TaskStatus, // 任务状态
    // 其他调度相关信息...
}

2.2 调度策略

rCore实现了两种基本调度方式：

1. ‌协作式调度‌：任务主动yield让出CPU‌
2. ‌抢占式调度‌：通过时钟中断强制任务切换‌

三、同步原语实现

3.1 自旋锁

1
2
3
4

pub struct SpinLock<T> {
    locked: AtomicBool,
    data: UnsafeCell<T>,
}

• 基于原子操作实现‌
• 获取锁时忙等待‌

3.2 信号量

1
2
3
4

pub struct Semaphore {
    count: isize,
    wait_queue: VecDeque<TaskControlBlock>,
}

• 维护计数器+等待队列‌
• 提供P/V操作接口‌

四、中断与异常处理

4.1 中断处理流程

1. 保存当前任务上下文‌
2. 执行中断服务例程(ISR)‌
3. 恢复或切换任务上下文‌

4.2 特权级切换

• 用户态(U-Mode)通过ecall进入内核态(S-Mode)‌
• 内核通过sret返回用户态‌

五、并发编程实践

5.1 线程创建

1
2
3
4
5

fn thread_create(entry: fn()) -> Tid {
    // 分配线程栈
    // 初始化线程上下文
    // 加入调度队列
}

5.2 互斥访问示例

1
2
3
4
5

let lock = SpinLock::new(shared_data);
{
    let mut guard = lock.lock();
    *guard += 1; // 临界区操作
} // 自动释放锁

六、性能优化技术

6.1 无锁数据结构

• 基于原子操作实现‌
• 适用于高并发场景‌

6.2 读写锁

1
2
3
4

pub struct RwLock<T> {
    state: AtomicIsize,
    data: UnsafeCell<T>,
}

• 区分读写访问‌
• 提高读多写少场景性能‌

二阶段 rCore 实验总结 - 折鸦

实验环境配置

用 Rust 开发操作系统内核源代码, 通过 rustc 交叉编译到 riscv64gc-unknown-none-elf (一般情况下是 x86_64-unknown-linux-gnu), 通过 rust-objcopy 提取出 bin, 然后放到 qemu-system-riscv64 模拟器进行模拟, 大概是这么个工具链.

QEMU 最好装 7.0.0 版本的, 从源码编译安装的话需要注意一下依赖, 部分发行版的依赖可以在 Running 64- and 32-bit RISC-V Linux on QEMU — RISC-V - Getting Started Guide 找到

Arch Linux 仓库里是 QEMU 9, 需要修改一下 RustSBI 的版本. 注意如果你想直接 downgrade 到 7.0.0 的话可能会需要连带降级一些非常核心的软件包, 非常不建议尝试. 有需要也可以自行寻找依赖包然后从源代码编译, 但是有一些接口变动可能会导致编译失败, 所以最佳方案还是替换 RustSBI 版本, 这里不再赘述.

构建一个能跑但仅仅能跑的操作系统

根据 OSTEP 的说法, 操作系统的主要三个任务部分在于: 虚拟化, 并发, 可持久化

• 虚拟化主要表现在:
  • 对内存的抽象: 每个进程有自己的虚拟地址空间, 造成每个进程独占一个主存的假象(学过 CSAPP 可以回忆一下第九章, 博客还在补)
  • 对 CPU 的虚拟化: 主要表现在操作系统内核对各个任务的调度, 使得每个任务产生独占 CPU 的假象(这就是一种并发)
  • 对外设设备的虚拟化等等
• 并发主要表现在:
  • 进程概念的抽象和实现, 进程间通信
  • 多线程的实现
• 可持久化主要涉及文件系统

而形式上, 操作系统是一个二进制文件或二进制文件镜像, 被 bootloader 加载进内存的特定位置, 驻留在内存中的特定代码, 这些代码负责一些加载应用程序(简单来说就是把可执行文件加载到内存), 管理资源(设备/文件)并提供访问的任务, 这些任务以系统调用(syscall)的形式暴露给应用程序, 只是系统调用函数比较敏感特殊, 下面会仔细介绍.

那么我们的任务就比较明确了:

• 先设计一个基本的能把应用程序加载到内存的功能 (当然因为现在内核没有任何调度能力也没有让应用程序启动其他应用程序的必要(这依赖进程的实现), 所以我们暂时不需要设计 execve 系统调用)
• 实现标准输出能力 (实际上标准输出就是调用系统调用 write, 目标为 1 (标准输入))
• 实现退出程序的能力 (exit 系统调用)

一、前言

通过阅读实验指导书，我跟着操作系统的发展历程，学习了批处理系统、多道程序与分时多任务、虚拟地址空间、进程管理、文件系统、进程通信和并发等核心概念，并对rCore的实现有了更深入的认识。以下是我对这两周学习过程的总结。

二、学习内容

1. 搭建执行环境：

   学习了平台与目标三元组，理解了应用程序执行环境。

2. 批处理系统：

   学习了批处理系统的基本原理，包括作业调度、作业执行过程。

3. 多道程序与分时多任务：

   掌握了多道程序设计的基本概念，以及如何实现分时多任务调度。

4. 虚拟地址空间：

   理解了虚拟内存的概念，包括页表、地址映射。

5. 进程管理：

   学习了进程的管理、调度，更加深入的理解了fork+exec。

6. 文件系统：

   掌握了文件系统的基本结构，包括目录、文件。

7. 进程通信：

   学习了父子进程之间的通信机制——管道。

8. 并发：

   学习了线程管理机制的设计与实现，理解了同步互斥的实现，包括锁、信号量、条件变量。

三、学习心得

第二次学习rCore，加之前段时间学习xv6的经历，对rCore有了更深入的认识，包括trap的过程、地址空间的切换等，和群里同学的讨论也加深了我对代码的理解。

通过学习rCore，我对操作系统的原理有了更深入的理解，虽然考研的时候较为系统的学习了操作系统的知识，但是基本上还是停留在理论知识方面。这次rCore学习之旅，我获取PCB对进程进行操作、实现课本上学习过的系统调用、深入汇编代码理解什么是 ‘陷入’ ，让我对操作系统的设计理念、计算机的体系结构有了具象化的认识。

在学习过程中，我也遇到了许多挑战，解决了旧问题又出现了新问题，对操作系统有了更深入的认识反而产生了更多的问题，但是我相信计算机没有魔法，多查资料多看源码一定能把疑惑解开。

两周的rCore学习之旅让我受益匪浅。通过学习rCore，我对操作系统的设计和实现有了更深刻的认识，同时也提升了我的编程技能。我相信，这些知识和经验将对我未来的学习和职业发展产生积极影响。

一、前言

通读了一遍《Rust程序设计语言》书籍并完成了训练营的Rustlings练习。经过两周的学习，我对Rust有了初步的认识和掌握。以下是我对这两周学习过程的总结。

二、学习内容

1. Rust基础知识

• Rust编程语言的基本语法，包括变量、数据类型、运算符、控制流等。
• Rust的所有权系统，包括所有权、借用、生命周期等概念。

2. Rustlings练习

• 通过完成一系列练习，巩固对Rust基础知识的理解和应用。
• 练习涵盖了Rust的所有权、借用、生命周期、错误处理、宏、模式匹配等方面的内容。

三、学习心得

这一阶段印象最深的还是最后的算法部份，尤其是前两道关于链表的题目，其实之前一直是使用c++做算法题，对链表也较为熟悉了，但是由于对rust的特性不熟悉以及对链表没有深刻理解，让我有一种有力使不出的感觉，后面通过阅读题目的框架，以及对书本知识的巩固，终于是对rust中的链表有了初步的认识，写完链表的题目后，后续的题目也很快完成了。rust语言的特性让我对编程和计算机有了更深的理解，尽管现在还是写得磕磕绊绊，但是相信通过不断学习和时间，将来我也能够编写出优秀的rust代码。

与同学们互相讨论

在本次学习过程中，我对Rust异步编程中的一些核心挑战进行了深入思考：

1. 函数着色和异步Drop的挑战

目前Rust异步编程中最棘手的问题是函数着色和async drop机制。特别是在资源管理方面，由于future是基于poll的机制，在处理background task和事务时面临两个主要场景的挑战：

• 结构体持有background task（如连接或stream）时的资源释放
• 需要uncancelable语义的事务处理场景

2. 资源安全释放的困境

在系统信号处理方面存在显著挑战。特别是在进程接收信号时的安全资源释放问题仍然没有完善的解决方案。虽然对于使用事务的SQL系统影响相对较小，但在文件系统或WAL文件等场景中，这个问题尤为突出。

3. 互斥锁的使用策略

在异步编程中，关于互斥锁的选择需要特别注意。Tokio提供了一个重要的见解：在异步代码中使用标准库的普通Mutex通常是可行且推荐的。异步互斥锁的主要优势在于能够在.await点保持锁定状态，但这也使其比阻塞式互斥锁更昂贵。因此，对于单纯的数据访问，使用标准库的阻塞式互斥锁是更合适的选择。

4. 操作系统层面的应用

在操作系统内核中，协程的应用主要可以考虑用于替代传统的自旋锁场景，而io_uring的引入则可能带来更广泛的应用空间。

5. 异步编程模型的适用场景

从资源管理的角度来看，异步编程模型在不同场景下有其独特的优势和局限。特别是在处理IO密集型任务时，异步模型能够提供更好的性能和资源利用率。

第一周：

• 复习并重新学习WASM上的async runtime相关知识
• 计划完善OS仓库，准备移植文件系统和SMP多核启动

第二周：

• 阅读Rust语言相关RFC文档：
  • async_trait与async fn in trait
  • Object Safety
  • pin_project_lite
• 为内核态编写async runtime
• 开始实现文件系统与block device
• 计划将async runtime合并到OS仓库中

第三周：

• 因家人住院需要陪护，本周暂无工作产出

概要设计

众所周知，操作系统内核对性能和时延的需求都是非常高的。当应用程序通过传统系统调用使用操作系统能力时，CPU需要经过两次特权模式转换、用户栈的保存与恢复等操作，这会消耗数十甚至数百CPU时钟周期。因此，在操作系统内核中引入异步协程机制时，不应增加这些基础开销。

在应用程序通过操作系统与外部设备交互时，由于大多数外部设备的性能都慢于CPU执行速度，且受限于信号传输延迟，响应延迟是不可避免的。操作系统在等待外部响应时采用自旋等待是非常低效的。因此，我的设想是在IO部分引入协程机制，通过用户进程的IO操作与内核线程通信的方式，为内核代码赋予异步能力。

在二阶段学习rCoreOS时，我发现其中与virtIO block-device的交互部分非常适合进行异步协程改造。

然而，我不赞成将所有内核代码和锁都替换为异步协程版本。如前所述，操作系统内核代码对性能非常敏感。虽然无栈协程的切换开销较小，但在内核开发中这种开销仍然不容忽视。此外，由于CPU大部分时间都会交由用户线程执行以最大化资源利用率，载体线程（CPU核心）会尽可能运行用户代码，这在某种程度上违反了协程使用原则，可能导致其他任务出现饥饿现象。

总结

四阶段开始前, 我曾立下这个目标: 希望能开发出我自己的操作系统内核, 并在 Lichee Pi 4A 真机设备上成功启动.

无奈上周夫人孕期遭遇大出血, 紧急住院保胎一周. 我作为陪护家属, 暂停了一周的学习与工作照顾夫人. 故未能完成四阶段开始前立下的目标😔.

第一阶段总结

第一阶段主要考察 Rust 基础编程和数据结构与算法，由于我有一定 Rust 基础，所以前 100 道题比较轻松，但从未使用 Rust 刷过算法题，因此后 10 道题让我学习了如何使用 Rust 编写常见数据结构如链表、栈、堆、图等，以及常见的排序、搜索算法等，有所收获！

第二阶段总结

第二阶段我的学习方法是先看完 v3 book 对应章节，然后再做实验题。v3 book 写得循序渐进，质量上乘，读懂后做实验题都比较轻松。第二阶段的精华都在 v3 book 中，十分建议精读一遍，我自己精读一遍后发现了若干内容和文字错误，还提交了 19 个 pr 修复。这期间我还写了篇博客分析有栈协程示例代码。

五个实验题中最后的死锁检测算法花费的时间要久一点，因为前面章节没有铺垫，直接就是抛出一个算法让实现，且算法只有过程描述，没有原理分析。这个算法似乎很少在生产上见到被实际使用（可能是我孤陋寡闻），我建议换成其他更有意义的实验，比如实现某一种同步互斥原语。

第三阶段总结

第三阶段主要是理解 ArceOS 组件化概念，如何划分组件以及如何将这些组件组装成不同的系统，如 Unikernel/宏内核/hypervisor 等。

在这个阶段，我完成了四个练习（print_with_color/support_hashmap/alt_alloc/simple_hv）和一个挑战任务：针对特定应用实现一个专门优化过的内存分配器。挑战任务并没有花太多时间，只是在 slab 分配器上做了些修改，所以得分不高，刚过及格线，排名第 14。

在这个阶段，我花费了许多时间来学习 RISC-V 的虚拟化扩展，本来是准备在第四阶段选择虚拟化项目的，但最后发现项目并没有采用 RISC-V 指令集（不想再花时间学习另一个指令集的特权架构，最终选择了基于协程异步机制的操作系统/驱动项目）。我研究了 arceos-hypervisor org 下的一些虚拟化项目和 KuangjuX/hypocaust-2 项目，arceos-hypervisor 项目因为需要做到组件复用，包括统一不同指令集架构，所以有很多抽象，学习成本有些高，而 KuangjuX/hypocaust-2 项目目前跑不起来，项目并没有指定 rust-toolchain，而且代码质量感觉不够高。最终我还是决定自己从零开始写一个纯 RISC-V 的一型 hypervisor，因为毕竟花了几个月时间参加训练营，还是想在最后自己能独立编写一个完整的实际项目。项目地址是 https://github.com/systemxlabs/riscv-hypervisor , 目前刚能将 rCore-Tutorial-v3 的第 5 章的内核作为 guest 跑起来，最终目标是能跑起 Linux。RISC-V 虚拟化扩展因为稳定不久，资料很少，所以写的过程中遇到许多困难，而且不好 debug，希望能坚持下去不弃坑~

第四阶段总结

第一周，阅读 200 行 rust 代码实现绿色线程、 200 行 rust 代码实现 futures 以及 blog_os 的 async/await 文章，输出了一篇博客，同时提了 pr 修复 rCore-Tutorial-v3 中 stackful_coroutine 示例代码，自己还将 stackful_coroutine 示例移植到 Linux for RISC-V 上（项目地址：https://github.com/systemxlabs/green-threads-in-200-lines-of-rust ），对原示例代码做了很多重构以便具有更好的可读性。调试自己的riscv hypervisor项目（第三周使用），目前可以运行 rCore-Tutorial-v3 第六章带文件系统的内核。

第二周，主要阅读 smol 生态 crates 源码，着重阅读了 polling / async-io / async-task / async-executor 库源码，理解最重要的 IO 多路复用 / reactor / driver / task / executor 等概念，输出了一篇博客。

第三周，编写异步 os（项目地址：https://github.com/systemxlabs/async-os ），本来是想把之前写的 riscv-hypervisor 改成异步，但感觉没有意义，因为 os 上面可能有成千上万的线程，所以将 os 改成异步减少上下文切换是有意义的，但 hypervisor 跟 os 不同，hypervisor 上面没有那么多的 guests，且 hypervisor 为了高性能，通常都尽可能去避免 vm exit，所以我放弃将之前写的 riscv-hypervisor 改成异步，改为实现一个异步 os，参考 phoenix 和 rCore-Tutorial-v3，特点是全隔离内核、内核栈复用、trap return回用户态时无需保存内核执行流。目前已实现多核启动、device tree解析、物理页帧和堆分配器、页表和地址空间、内核和用户态trap handling、异步runtime。

作为常年开发网络程序的我，对异步、并发操作却仅仅停留在使用层面，这对我来说是一件长期的困扰。于是在第四阶段，我毫不犹豫地选择了“基于协程异步机制的OS”方向。在这个方向上，我学到了很多新的知识，也遇到了很多新的问题。

第一周

第一周的任务主要是了解 Rust 中异步的基本概念，通过阅读资料，我了解到了 Rust 中的 async 和 await 关键字背后的原理，并且了解到了如何实现有栈/无栈协程。过去我只了解过有栈协程，而无栈协程对我来说是一个全新的概念，其 LLVM Generator 的实现机制让我感到十分精妙。在这一周中，我主要是通过阅读资料和代码来了解这些概念，对于这些概念的理解还不是很深入。

第二周

第二周主要的工作是阅读 Tokio 代码，我阅读了 Tokio 的 net、signal 和 sync 模块，我将部分代码的分析记录在了共享文档中，这些代码的阅读让我对异步编程有了更深入的理解。

第三周

第三周通过阅读 epoll、io-uring 等相关资料，我了解到了异步 IO 的原理。通过阅读 async-io 和 polling 的代码，我了解了 epoll 在 Rust 异步运行时中的运用，而通过阅读 monoio 和 tokio-uring 的代码，我了解了 io-uring 在 Rust 异步运行时中的运用，这些代码的阅读让我对异步 IO 有了更深入的理解。io-uring 的机制起初让我感到困惑，但是在领悟到 io-uring 事实上是一个异步的系统调用框架而不是 epoll 这样的文件描述符复用机制后，我便茅塞顿开。

在阅读了大量相关的资料后，我也着手开始实现一个简单的异步运行时，通过对 mini-rust-runtime 的学习和修改，我将其中使用 polling 实现的基于 epoll 的异步运行时改为了基于 io-uring 的异步运行时，并初步支持了文件的异步读写和 TCP 连接。因为使用 io-uring 必须从系统调用层面进行编程，抽象层次很低，在查阅了大量资料后我才勉强完成了这个十分粗糙的实现。

总结

毫不夸张的说，这短短的三周我学到了近年来对我来说最有价值的知识，使我对异步编程的理解有了质的飞跃，使我未来能更好地开发出高性能的网络程序。在学习的过程中，我也遇到了很多问题，但是通过查阅资料和请教老师，我都得到了解决。这次训练营对我来说是一次非常有意义的经历，我也希望未来能有机会继续参加这样的活动。

参与方向：宏内核，posix 接口相关。

我在四阶段中编写的是 futex 有关的代码。

设计思路

暂时请求了五个 os 需要实现的接口，分别是

• sched_yield 退出当前的任务，不放回调度队列。
• translate_vaddr 将当前任务的虚拟地址转换成操作系统可以访问的地址
• current_task 取得当前任务
• current_prosess_id 取得进程 id
• wake 传入一个 FutexQ 类型，唤醒任务（提供了 get_task 函数取得任务）

FutexQ 是存放任务的重要类型，内有 key bitset task 三个字段，其中 key 和 bitset 是用来唤醒任务的重要字段。

FutexKey 是一个枚举，现在只实现了一个 Private，Shared 暂时没有开发的思路。

任务等待队列存储在 FutexQueues 中，通过一个 futex 的唯一 key 通过哈希变换后放入或唤醒。

现在实现的调用有：FUTEX_WAIT FUTEX_WAKE FUTEX_REQUEUE FUTEX_CMP_REQUEUE FUTEX_WAKE_OP 以及对应的 bitset 版本

因为三阶段提供的宏内核中没有合适的线程实现，二阶短的项目不知道什么原因不能编译 link-me 的代码，所以我直接把整个模块删除 linkme 后移植到了阶段二的仓库，并编写测试通过。

收获

说实话还是不是很擅长编写 no_std 的代码，所以我还是依赖了很多外部库。

虽然没有通过最初的设想去适配到任何一个系统里去（直接移植还是太不松耦合了），但是我也花了很多时间去尝试适配，其中阶段二的项目仓库是最接近完成的一个，结果编译错误了，经过测试发现把 futex::syscall::sys_futex 函数调用去掉就可以通过编译，一时间不知道从何改起。转到 arceos 适配的时候，在被迫阅读了大量源码之后，发现提供的宏内核示例压根没有创建线程的系统调用，自己写了半天并没有写出来，所以又放弃了。

虽然写的挺差的，而且最近也到学校的期末周了，确实有没有太多时间写这个项目了，但是通过这次 posix 接口的编写，我还是学会了不少东西。

总结

从训练营开始到现在也过去 12 周了，看着自己从对操作系统毫无概念一步步到现在还是很感慨的。感谢老师的辛勤付出，感谢训练营能给我一个这样的平台。

你们好，我是catme0w，来分享一下我在内存分配器挑战中的经历。

也看看我在二阶段的文章吧：https://rcore-os.cn/blog/2024/11/10/2024%E7%A7%8B%E5%86%AC%E5%AD%A3%E5%BC%80%E6%BA%90%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E8%AE%AD%E7%BB%83%E8%90%A5%E7%AC%AC%E4%B8%80%E3%80%81%E4%BA%8C%E9%98%B6%E6%AE%B5%E6%80%BB%E7%BB%93-catme0w/

Round 1：更好的TLSF分配器

一开始拿到题目的时候，是想尝试一下改善“正常的分配器”的，也就是实现通用分配器，因为那时想着，毕竟在内核空间之中搞小动作太过容易，以非正常方式刷分数显得太cheaty了一点也不好玩。

粗略了解过后，认识到原来TLSF实现所使用的rlsf库已经是分配器算法的较优实现了：https://github.com/yvt/rlsf#measured-performance 。尝试调整了一下rlsf的参数（FLLEN和SLLEN），发现并没有什么变化，无法突破170。

认识到试图优化TLSF似乎是没有前途的；改善TLSF的路线，宣告失败。

Round 2：面向测例分配器

那么，我们不得不从头开始写我们自己的东西了。

要了解分数由什么决定，也就是什么决定了indicator数量的上限，进一步地，了解每一步中内存分配行为和内存碎片的变化。

不难看出，测例会释放掉偶数项的块，而保留奇数项。

由此，我们可以针对性地“攻击”这一点——研究测例的分配模式，追踪每一次分配是否是“不会被释放”的那一批，将其连续排列在一个特殊的区域中，使得内存碎片完全不会出现，利用率达到惊人的100%。

可当我准备动手时，意识到这个东西在现实世界里没有意义，它只能针对这个测例起效。至少在我看来，这已经和非正常方式没有太大差异了。

那么，要不……一不做二不休，干脆直接把非正常方式做到极致？

Round 3：假的分配器

从测例的行为可以了解到，它只会验证块的最后一个字节是否正确，那么思路就很简单了，追踪每次分配行为，如果是外层的Vec，就给它用真的分配器；如果是内层Vec，就只分配两个字节，然后返回伪造的内存地址！

可是，说的倒轻巧，思路是简单不假，可是究竟有什么方法精确地识别一个堆分配操作来自哪里呢？答案是没门！更不要提伪造内存地址会有多难做。

我确实尝试了一下，但是……很快放弃了。

值得一提的是，分配器的部分不直接在内核中，没有println可用，因而调试极其困难。

必须再换一个思路才行。

Round 4：他不体面你就帮他体面分配器

注意到：每次分配的内存大小由base+delta构成，base指数增长，从32开始，每次为之前的两倍，直到达到512 KB；delta为indicator数量。

释放的规律上文已提过，偶数项释放，奇数项保留。

那么，新的思路由此诞生：追踪indicator的数量，确定当前测例位于哪一“回合”，进而精确计算出哪些分配会被测例保留，记下它们的内存地址……

然后，从分配器的代码内，释放掉它们！

他不体面，你就帮他体面！

我最开始思路还要更简单些，只是记录下所有分配的内存地址，当遇到大于512 KB的释放时，就释放掉之前记录的所有地址。

但这样会有一个显而易见的问题：double free——测例本身还会释放一半呢。

由于测例很简单，我一开始不认为这是个问题，但在我无数次撞在LoadFault上之后，我投降了……

以下是我最终的详细思路：

具体不会被释放的块，长度为64+delta、256+delta、1024+delta……。

将其base值，也就是64、256、1024……维护在分配器内的一个Vec中。

当分配器命中这些值时，把它们的内存地址和大小保存在另一个Vec中。

当分配器命中下一“回合”的32+delta，也就是第一次分配时，标志前一“回合”结束，此时，将记录到的那些不会被测例释放的内存块释放掉。

由此，我们便消除了测例的“内存泄漏”，内存将永远无法被耗尽。

但没那么简单，这个“正确的思路”第一版实现仍然会停止在130，并且不是no memory，而是触发了LoadFault，内存越界了。

经观察，我所记录的那些“我要帮它体面”的内存块中，恰好有某项命中了外层Vec的扩张大小……

由于临近截止，我没有时间仔细去寻找它们到底命中哪个长度了，只能暂时绕过它。

在indicator足够大之前，每回合均不释放开头的两项。

一阵操作之后，我终于第一次看到了indicator数量超越170。

或者说，我终于得到了梦寐以求（？）的无尽indicator。

在何时停止好呢？来做一个114514吧，多有纪念意义啊。

只是，它在65536就停了下来，显示no memory。

何故呢？

原来，测例中负责释放的那部分（free_pass）所使用的delta长度是u8，只有负责分配的部分（alloc_pass）才是usize。65536是u8的上限，不是我的上限。

我的114514，梦碎了。

“这不可能！”

我大叫起来。

此时临截止不到一个小时了，我分明记得之前看到过有人把indicator刷到了六位数。

他们怎么绕过u8的上限的？

Round ？：一种基于kernel exploit的分配器

想要打破u8，那就得让free_pass不执行。

得发挥更强大的想象力，寻找更下作（？）的手段。

那么，这其中的花样可就多了……

此时的操作系统仍是unikernel，没有虚拟内存，不存在用户空间，所有的代码共用同一个（物理）地址空间。

你可以找到测例里alloc_pass那个循环下标的内存地址，然后直接把它改成114514……

或者，直接覆盖掉println……

甚至，还可以想办法在我们能允许修改的这一小块代码中弄出些use-after-free，来点缓冲区溢出，来点ROP……

但我想，已经刷到六位数的那些人用的并不是这样的方法。他们会怎么做呢？比赛结束之后再去看看吧。

100% Honest Review

在最开始，我对参与这项挑战的兴趣不大。我不喜欢这种有零和博弈味道的规则——早提交可能失去优化机会，晚提交可能因结果相同而落后。

ArceOS已经很难了，题目若再有压力，我会直接躺平。我承认我很脆弱。

话虽这么说，我还是来了。尽管我很晚才开始了解挑战的细节，而到那时，已经有人发掘出了非正常方式。

那时我的反应与群里一位的想法几乎一致：这不就彻底没意思了吗？

但当我亲自上手这个题目时，想法还是逐渐发生了变化。哎真香

纵使前期有些不愉快，最终还是收获了不少快乐与知识。

但倘若你问我，还想不想再玩一次这样的挑战题目的话……

我的回答是否定的。

内存分配器-字节分配器：Chaos 一点都不 Chaos

分析内存结构

堆中的 Vec<Vec<u8>> 结构数据

使用上述任意分配器，并在 alloc 和 dealloc 函数，中分别打印 Layout。在打印结果中可以看到一些比较特殊的内存大小分别为 96、192、384

这是什么呢？根据 lab1/src/main.rs 中的测例代码分析可得知 let mut items: Vec<Vec<u8>> = Vec::new(); 的内层 Vec 将存放在堆内存中。

而 Rust 中的堆数据结构 中的一张图片展示了 Vec 的内存结构为指针、长度和容量，每一部分各占 usize，在 64 位系统中，uszie 大小为 8 字节，即一个空数组内存占用为 24 字节，这与 96 字节仍有出入。

再观察分配情况，在 Indicator: 0 时，96 字节的 alloc 是在第一次 32 字节 alloc 后产生的，猜测是在 items.push 后进行了一次 扩容，alloc_pass 修改为如下代码进行验证：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

fn alloc_pass(delta: usize) -> Vec<Vec<u8>> {
    let mut items = Vec::new();
    let mut base = 32;
    loop {
        let c = (delta % 256) as u8;
        let a = vec![c; base+delta];
        items.push(a);
        println!("Item Capacity: {}", items.capacity());
        if base >= 512*1024 {
            break;
        }
        base *= 2;
    }
    items
}

结果为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Running bumb tests...
Indicator: 0
Item Capacity: 4
Item Capacity: 4
Item Capacity: 4
Item Capacity: 4
Item Capacity: 8
Item Capacity: 8
Item Capacity: 8
Item Capacity: 8
Item Capacity: 16
Item Capacity: 16
Item Capacity: 16
Item Capacity: 16
Item Capacity: 16
Item Capacity: 16
Item Capacity: 16

就对上了，24 * 4 = 96 24 * 8 = 192 24 * 16 = 384

同时，至少在这里来说，Vec 初始容量为 0，第一次扩容时为 4，扩容机制为每次容量翻倍。

存放数据的堆空间

再回到测例代码：

1
2
3
4
5
6
7
8
9
10

fn free_pass(items: &mut Vec<Vec<u8>>, delta: u8) {
    let total = items.len();
    for j in (0..total).rev() {
        if j % 2 == 0 {
            let ret = items.remove(j);
            assert_eq!(delta, ret[0]);
            assert_eq!(delta, ret[ret.len()-1]);
        }
    }
}

这段代码在检查是否为偶数项，偶数项数组才会被 free_pass 的 remove() 释放。

因此针对这段代码，可以在分配器中设置一个奇偶标志位，当标志位为奇数时将数据从内存的起始位置开始分配，偶数时分配在末尾位置且向起始位置增长。扩容时，不考虑内存扩容时传入的内存地址起始位置而只改变结尾位置时也无需多余操作。

Chaos 真的不 Chaos

整体结构

考虑：

1. 堆中的 Vec<Vec<u8>> 数据结构，大小固定为 96 + 192 + 384 = 672 字节，位于可分配内存的起始位置
2. 奇数项堆，动态增长，紧跟 672 字节
3. 偶数项堆，动态增长，位于可分配内存的末尾位置

使用以下结构体来描述整个可分配内存区域

1
2
3
4
5
6
7
8
9
10
11
12

pub struct Chaos {
    pub vec_reserve: (usize, usize, usize),

    pub start: usize,
    pub end: usize,
    pub head: usize,
    pub tail: usize,
    pub is_even: bool,

    pub allocated: usize,
    pub total: usize,
}

内存结构如下：

vec_reserve: (usize, usize, usize) 用作存储先前描述的三片特殊的堆中 Vec 元数据结构，vec_reserve 为固定长度：96 + 192 + 384 字节。

pub start: usize 和 pub end: usize 分别存储 init 或是 add_to_heap 时给定的可分配内存地址范围。

pub head: usize 和 pub tail: usize 分别存储当前奇数堆的末尾位置和偶数堆的起始位置，通过 head - start + vec_reserve 可以得出奇数堆大小，通过 end - tail 则可以得出偶数堆大小。

pub is_even: bool 用于记录上一次分配是奇数还是偶数，在分配的最后将其翻转。

实现

在开始之前，还要确定一个很重要的问题。目前的设计，并没有考虑扩容时分配在本程序堆内存前内存区域的地址，因此使用代码简单判断下：

1
2
3
4
5
6
7
8

pub fn add_to_heap(&mut self, start: usize, end: usize) {
    log::warn!("head: 0x{:x}, tail: 0x{:x}, start: 0x{:x}, end: 0x{:x}", self.head, self.tail, start, end);

    self.head = start;
    self.tail = end;

    panic!("add_to_heap");
}

从 add_to_heap 的输出：

1
2
3
4
5
6

Running bumb tests...
Indicator: 0
[  0.082919 0 lab_allocator::chaos:66] head, tail: 0xffffffc08026d2a0, 0xffffffc080275000
[  0.087323 0 lab_allocator::chaos:44] head: 0xffffffc08026d2a0, tail: 0xffffffc080275000, start: 0xffffffc080275000, end: 0xffffffc08027d000
[  0.091091 0 axruntime::lang_items:5] panicked at labs/lab_allocator/src/chaos.rs:49:9:
add_to_heap

可以看到后续追加的内存与当前程序的堆尾部是连续的，只需要更改 tail 字段扩容当前内存即可。

1. 初始化以及扩容

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

   pub unsafe fn init(&mut self, start: usize, size: usize) { self.vec_reserve = (start, start + 96, start + 96 + 192); self.start = start + 96 + 192 + 384; self.head = start + 96 + 192 + 384; self.end = start + size; self.tail = start + size; self.allocated = 96 + 192 + 384; self.total = self.end - self.start; } pub fn add_to_heap(&mut self, start: usize, end: usize) { self.end = end; self.tail = end; self.total += end - start; }

2. 分配

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

   pub fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, ()> { let vec_reserve_ptr = match layout.size() { 96 => Some(self.vec_reserve.0 as *const u8), 192 => Some(self.vec_reserve.1 as *const u8), 384 => Some(self.vec_reserve.2 as *const u8), _ => None, }; if vec_reserve_ptr.is_some() { return Ok(NonNull::new(vec_reserve_ptr.unwrap() as *mut u8).unwrap()); } // check if memory is overflow if self.tail - layout.size() <= self.head { return Err(()); } let ptr = if self.is_even { let mem = self.tail - layout.size(); self.tail = mem; NonNull::new(mem as *mut u8).unwrap() } else { let mem = self.head; self.head = mem + layout.size(); NonNull::new(mem as *mut u8).unwrap() }; self.is_even = !self.is_even; self.allocated += layout.size(); Ok(ptr) }

3. 释放

   1 2 3 4 5 6 7 8

   pub fn dealloc(&mut self, pos: NonNull<u8>, layout: Layout) { if (pos.as_ptr() as usize) < self.start + 96 + 192 + 384 { return; } self.tail +=layout.size(); self.allocated -= layout.size(); }

越界访问

第 32 轮分配时发生了 Unhandled Supervisor Page Fault，本机的 panic 位置为 0xffffffc0802005fc，远在可分配的起始地址 0xffffffc08026d2a0 前，猜测本次的 panic 发生在栈区或是发生在从 tail 进行分配或释放时发生的。

说起来很好笑，let mut pool = Vec::new(); 和 items 一样，也会占用一些堆区内存，但因为其只写不读，即使内部全部都是无效的堆内存地址也没有问题。但这提醒到了一点：在分配用于 items: Vec<Vec<u8>> 的堆内存时，使用了一个特判：

1
2
3
4
5
6

let vec_reserve_ptr = match layout.size() {
    96 => Some(self.vec_reserve.0 as *const u8),
    192 => Some(self.vec_reserve.1 as *const u8),
    384 => Some(self.vec_reserve.2 as *const u8),
    _ => None,
};

这几个数字并没有问题，但先前我们忽略了 let a = vec![c; base+delta]; 的 base 总是从 32 开始，每次 alloc 翻倍，delta 则每轮增加 1。恰好， 第 32 轮的第二次 alloc 时那么不恰好的 base = 64 和 delta = 32，这不是 96 了嘛 uwu，所以到这时候，原本该分配给 items: Vec<Vec<u8>> 的地址被当作了 tail 堆的起始地址，又因为 tail 是 tail = tail - size 取得空闲地址，所以结果是越界了。

根据观察后，在 Layout 中存在字段 align，align 字段在 items: Vec<Vec<u8>> 分配中总是 8，而普通分配总是 1。

因此简单写个判断就可以解决了：

1
2
3

if vec_reserve_ptr.is_some() && layout.align() == 8 {
    return Ok(NonNull::new(vec_reserve_ptr.unwrap() as *mut u8).unwrap());
}

处理完这个问题后，算法成功跑到 152 轮。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

Indicator: 152
[ 25.511024 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f352a8, tail=0xffffffc085015be2, size=0xb8
[ 25.513985 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc085015b2a
[ 25.516487 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f352a8, tail=0xffffffc085015b2a, size=0xd8
[ 25.519232 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f352a8
[ 25.521127 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f35380, tail=0xffffffc085015b2a, size=0x118
[ 25.523938 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc085015a12
[ 25.525770 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f35380, tail=0xffffffc085015a12, size=0x198
[ 25.528492 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f35380
[ 25.530458 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f35518, tail=0xffffffc085015a12, size=0x298
[ 25.533267 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc08501577a
[ 25.535172 0 lab_allocator::chaos:94] head, tail: 0xffffffc084f35518, 0xffffffc08501577a
[ 25.537270 0 lab_allocator::chaos:95] dealloc_memory: pos=0xffffffc08026f000, size=0x60
[ 25.540115 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f35518, tail=0xffffffc08501577a, size=0x498
[ 25.542925 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f35518
[ 25.544869 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f359b0, tail=0xffffffc08501577a, size=0x898
[ 25.547528 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc085014ee2
[ 25.549466 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f359b0, tail=0xffffffc085014ee2, size=0x1098
[ 25.552112 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f359b0
[ 25.554013 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f36a48, tail=0xffffffc085014ee2, size=0x2098
[ 25.558305 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc085012e4a
[ 25.560458 0 lab_allocator::chaos:94] head, tail: 0xffffffc084f36a48, 0xffffffc085012e4a
[ 25.562665 0 lab_allocator::chaos:95] dealloc_memory: pos=0xffffffc08026f060, size=0xc0
[ 25.564900 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f36a48, tail=0xffffffc085012e4a, size=0x4098
[ 25.567790 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f36a48
[ 25.569725 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f3aae0, tail=0xffffffc085012e4a, size=0x8098
[ 25.572420 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc08500adb2
[ 25.575027 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f3aae0, tail=0xffffffc08500adb2, size=0x10098
[ 25.577664 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f3aae0
[ 25.579570 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f4ab78, tail=0xffffffc08500adb2, size=0x20098
[ 25.582385 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084fead1a
[ 25.584478 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f4ab78, tail=0xffffffc084fead1a, size=0x40098
[ 25.587429 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f4ab78
[ 25.591690 0 axruntime::lang_items:5] panicked at modules/axalloc/src/lib.rs:124:31:
Bumb: NoMemory.

预分配：尽可能使用更多的内存

在观察 152 轮和 add_memory 的 log 时发现：

1. 本轮的偶数区并没有得到释放。
2. 内存从一开始分配起，每次扩容即为前一次空间 x2，最大为 32 MB。而 qemu 虚拟机分配的是 128MB，只分配到了 32MB，显然还不是极限。

1

pub fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, ()> { Err(()) }

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Indicator: 0
[  0.088199 0 lab_allocator::chaos:46] add_memory: start=0xffffffc080275000, end=0xffffffc08027d000 # 32768
[  0.090785 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08027d000, end=0xffffffc08028d000 # 65536
[  0.093210 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08028d000, end=0xffffffc0802ad000 # 131072
[  0.095720 0 lab_allocator::chaos:46] add_memory: start=0xffffffc0802ad000, end=0xffffffc0802ed000 # 262144
[  0.098368 0 lab_allocator::chaos:46] add_memory: start=0xffffffc0802ed000, end=0xffffffc08036d000 # 524288
[  0.100928 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08036d000, end=0xffffffc08046d000 # 1048576
[  0.103497 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08046d000, end=0xffffffc08066d000 # 2097152
[  0.106127 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08066d000, end=0xffffffc080a6d000 # 4194304
[  0.108677 0 lab_allocator::chaos:46] add_memory: start=0xffffffc080a6d000, end=0xffffffc08126d000 # 8388608
[  0.111219 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08126d000, end=0xffffffc08226d000 # 16777216
[  0.114057 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08226d000, end=0xffffffc08426d000 # 33554432 byte = 32MB
[  0.117634 0 axruntime::lang_items:5] panicked at modules/axalloc/src/lib.rs:124:31:
Bumb: NoMemory.

因此，我们可以打第一次 alloc 开始就强迫系统预分配一大堆内存给测例。比如在 pub fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, ()> 的合理位置添加下面的代码：

1
2
3
4

// get as much memory as possible
if self.end <= 0xffffffc08426d000 {
    return Err(());
}

修改后，轮数为 189。此时，内存分配量到达了 64MB，这样下来仍有很多剩余空间。

再挤一挤，内存还是有的

看一眼 axalloc 中：

1
2
3
4
5
6
7
8
9

let old_size = balloc.total_bytes();
let expand_size = old_size
    .max(layout.size())
    .next_power_of_two()
    .max(PAGE_SIZE);
let heap_ptr = match self.alloc_pages(expand_size / PAGE_SIZE, PAGE_SIZE) {
    Ok(ptr) => ptr,
    Err(e) => panic!("Bumb: {:?}.", e),
};

不难发现 axalloc 是依赖于 total_bytes() 来判断该扩容多少内存。

简单一些处理，只需要修改原先的 total_bytes 代码，使得 total_bytes 永远返回 0。

1
2
3

pub fn total_bytes(&self) -> usize {
    0
}

修改后的最终轮数为 245。

也许还会在 我的博客 更新，代码仓库可能会在后续删除，为了不再占用的过多空间，完整代码同样也附带在我的博客里