第一阶段总结

1年前开始学习rust，初衷是了解一门操作系统级别的开发语言(深入了解，作为工作语言那种)。并为此写了系列的微信公众号文章《拥抱未来语言Rust》并在社区取得了不错的反响，感兴趣的可以微信公众号搜索“三角兽”，欢迎关注。
rust作为一门系统级语言，拥有高性能的同时还具有高安全性，基于RAII风格自动资源管理，避免了很多内存安全问题(这也是吸引我学习的主要原因)。本次比赛是我第一次参加的系统级比赛，通过比赛，夯实了对rust语言的理解，包括：所有权，作用域，生命周期，智能指针等。非常有意义，在此感谢主办方！

第二阶段总结

一直以来对OS非常感兴趣，本次通过身临其境的“代码调试”，熟悉了整个项目架构，并对OS有了进一步的深刻认识。在调试过程中不仅熟悉了OS，还对Rust语言有了更深入的认识。第二阶段的操作系统实现基于RISC-V指令集，之前没有了解过RISC-V，因此看汇编语言会有些头痛，但结合RISC-V手册加上AI的辅助，理解这些汇编代码完全没有问题。
通过第二阶段的学习，破除了一直以来对操作系统底层实现机制的迷雾，那层隔阂在应用开发人员心底的对操作系统的朦胧自此打破，世界上没有彩蛋，只有认识盲区，破除这些盲区，就是扩大自己的认知，增加自己的技术自信。后面打算写系列的博客来总结、分享操作系统，影响更多的人来学习操作系统。

第三阶段总结

第三阶段基础知识阶段，让我了解到了几个不同的方向，分别是Unikernel、MicroKernel、Hypervisor、以及Async OS。主键化开发思想非常重要，将系统无关的公共逻辑抽象出来形成crate，达到软件复用的效果。让我第一次认识到原来OS开发也可以像App开发一样，按模块自由组合，基于底层的积木搭建高楼大厦。
工作方面的原因，第三节段的作业我没有太深入的去做，所有的课程录屏及PPT都有仔细观看和阅读，后面抽时间好好做一做课后作业，相信会加深对OS的理解。
另外结合自身实际，选择项目四作为实习方向。一直对高并发，异步比较感兴趣（其实对虚拟化也挺感兴趣的，但是对陌生的指令集比较恐惧，怕花太多的时间反而没太大的结果）。
系统通过第四阶段对异步操作系统的研究及tokio源码的注释，对异步有更深入的了解，虽然我不是从事系统类软件开发，但始终相信，学习操作系统底层，对上层应用开发也大有裨益，最后感谢清华大学的操作系统课程，后面会写系列博客分享，为社区助力！

课后练习1：print_with_color

在axstd中的wirte方法中，利用终端控制序列（ANSI 转义码）进行有颜色的输出

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

fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
    let color_prefix = b"\x1b[32m";
    let color_suffix = b"\x1b[0m";
    

    if let Err(e) = arceos_api::stdio::ax_console_write_bytes(color_prefix) {
        return Err(e);
    }

    let result = arceos_api::stdio::ax_console_write_bytes(buf);
    if let Err(e) = result {
        return Err(e);
    }
    
    if let Err(e) = arceos_api::stdio::ax_console_write_bytes(color_suffix) {
        return Err(e);
    }
    
    result
}

MMIO：将设备寄存器直接映射到内存空间上，并具有独立的地址
u_3_0模拟闪存磁盘，启动时自动从文件加载内容到固定的MMIO区域。（对读操作不需要驱动，直接访问）

paging特征决定了是否启动后期重建完成的空间映射

课后练习3：实现bump内存分配算法

引导问题（bootstrap problem），也被称为“先有鸡还是先有蛋”的问题。内核在刚启动时，需要分配内存来建立自己的数据结构（例如内存映射、页表等），但此时还不知道系统中有多少物理内存，也没有初始化内存分配器。然而，要调用库函数（如用于解析设备树、初始化驱动等），可能需要动态内存分配。这就导致了一个悖论：需要分配内存来初始化内存管理，但又需要内存管理来分配内存。
练习：在引导阶段实现bump内存分配
分别为BaseAllocator，ByteAllocator，PageAllocator实现特征即可

实现相关特征即可，注意在页分配的时候进行对齐，字节分配器下的dealloc只需对count进行操作即可

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

pub struct EarlyAllocator {
    start: usize,
    end: usize,
    b_pos: usize,
    p_pos: usize,
    count: usize,
}

impl EarlyAllocator {
    pub const fn new() -> Self {
        Self {
            start: 0,
            end: 0,
            b_pos: 0,
            p_pos: 0,
            count: 0,
        }
    }
}


impl BaseAllocator for EarlyAllocator {
    fn init(&mut self, start: usize, size: usize) {
        self.start = start;
        self.end = start + size;
        self.b_pos = start;
        self.p_pos = self.end;
        self.count = 0;
    }

    fn add_memory(&mut self, start: usize, size: usize) -> AllocResult {
        self.end += size;
        Ok(())
    }
}

impl ByteAllocator for EarlyAllocator {
    fn alloc(&mut self, layout: Layout) -> AllocResult<NonNull<u8>> {
        let size = layout.size();

        if self.b_pos + size > self.p_pos {
            return Err(allocator::AllocError::NoMemory);
        }

        let ptr = self.b_pos;
        self.b_pos = self.b_pos + size;
        self.count += 1;

        unsafe { Ok(NonNull::new_unchecked(ptr as *mut u8)) }
    }

    fn dealloc(&mut self, _pos: NonNull<u8>, _layout: Layout) {
        if self.count > 0 {
            self.count -= 1;
        }
        if self.count == 0 {
            self.b_pos = self.start;
        }
    }

    fn total_bytes(&self) -> usize {
        self.end - self.start
    }

    fn used_bytes(&self) -> usize {
        self.b_pos - self.start
    }

    fn available_bytes(&self) -> usize {
        self.p_pos - self.b_pos
    }
}



impl PageAllocator for EarlyAllocator {
    const PAGE_SIZE: usize = 0x1000; 

    fn alloc_pages(&mut self, num_pages: usize, align_pow2: usize) -> AllocResult<usize> {
        let size = num_pages * Self::PAGE_SIZE;

        let new_p_pos = (self.p_pos - size) & !(align_pow2 - 1);

        if new_p_pos < self.b_pos {
            return Err(allocator::AllocError::NoMemory);
        }

        self.p_pos = new_p_pos;
        Ok(self.p_pos)
    }

    fn dealloc_pages(&mut self, _pos: usize, _num_pages: usize) {
    }

    fn total_pages(&self) -> usize {
        (self.end - self.start) / Self::PAGE_SIZE
    }

    fn used_pages(&self) -> usize {
        (self.end - self.p_pos) / Self::PAGE_SIZE
    }

    fn available_pages(&self) -> usize {
        (self.p_pos - self.b_pos) / Self::PAGE_SIZE
    }
}

增加axsync
抢占式调度机制
触发优先级高的任务及时获得调用机会，避免个别任务长期不合理占据CPU

支持从磁盘块设备读数据，替换PFlash
管理方式：static or dyn

块设备驱动Trait：BlockDriverOps

课后练习4：为shell增加文件操作命令

底层以fatfs为框架实现好了，我们只需调用api即可

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

fn do_mv(args: &str) {
    let args = args.trim();
    if args.is_empty() {
        print_err!("mv", "missing operand");
        return;
    }

    let mut paths = args.split_whitespace();
    let src = match paths.next() {
        Some(p) => p,
        None => {
            print_err!("mv", "missing source file");
            return;
        }
    };

    let dest_dir = match paths.next() {
        Some(p) => p,
        None => {
            print_err!("mv", "missing destination directory");
            return;
        }
    };


    let dest_path = format!("{}/{}", dest_dir, src);

    if let Err(e) = fs::rename(src, &dest_path) {
        print_err!("mv", format!("failed to move {} to {}", src, dest_dir), e);
    }
}

fn do_rename(args: &str) {
    let args = args.trim();
    if args.is_empty() {
        print_err!("rename", "missing operand");
        return;
    }

    let mut paths = args.split_whitespace();
    let old_name = match paths.next() {
        Some(p) => p,
        None => {
            print_err!("rename", "missing old file name");
            return;
        }
    };

    let new_name = match paths.next() {
        Some(p) => p,
        None => {
            print_err!("rename", "missing new file name");
            return;
        }
    };
    if let Err(e) = fs::rename(old_name, new_name) {
        print_err!("rename", format!("failed to rename {} to {}", old_name, new_name), e);
    }
}

ArceOS Unikernel包括两阶段的地址映射
Boot阶段默认开启1G空间的恒等映射
如果需要支持设备的MMIO区间，通过指定一个feature- "paging"来实现重映射

可选的重建映射

1. 为了管理更大范围的地址空间，包括设备的MMIO范围
2. 分类和权限的细粒度控制

宏内核

• 增加了用户特权级
• 创建独立的用户地址空间
• 内核运行运行时可以随时加载应用Image投入运行
• 应用与内核界限分明

高端内核空间，低端用户应用空间

宏内核的地址空间管理

地址空间区域映射后端

1. linear：对应物理地址必须连续
2. alloc：按页映射，可能不连续

多级调用handle_page_fault

populate为true时，申请页帧后直接完成映射；为false时仅建立空映射

如何让Linux的原始应用直接在我们宏内核上直接运行

实现兼容页面，包含syscall，procfs & sysfs等伪文件系统，awareness of aspace

ELF格式应用的加载

需要注意文件内偏移和预定的虚拟地址空间内的偏移可能不一致，特别是数据段的部分

存零，清零

应用的用户栈的初始化
支持系统调用的层次结构

系统调用号与体系结构相关

对Linux常用文件系统的支持

课后练习：实现mmap系统调用

Hypervisor

建立最简化的Hypervisor 过程 新建地址空间，加载内核镜像 准备上下文 设置两级页表 切换V模式 OS内核只有一条指令：调用sbi-call的关机操作。但由于这种操作超出了V模式的权限，导致VM_EXIT退出虚拟机，切换回Hypervisor Hypervisor响应VM_EXIT的函数（vmexit_handler`）检查退出原因和参数，进行处理，由于时请求关机，清理虚拟机后退出

进入虚拟化模式准备的条件
ISA寄存器misa第7位代表Hypervisor扩展的启用/禁止。
进入V模式路径的控制：hstatus第7位SPV记录上一次进入HS特权级前的模式，1代表来自虚拟化模式。
执行sret时，根据SPV决定是返回用户态，还是返回虚拟化模式。
Hypervisor首次启动Guest的内核之前，伪造上下文作准备：
设置Guest的sstatus，让其初始特权级为Supervisor；
设置Guest的sepc为OS启动入口地址VM_ENTRY，VM_ENTRY值就是内核启动的入口地址，
对于Riscv64，其地址是0x8020_0000。

如何从pflash设备读出数据

1. 模拟模式：为虚拟机模拟一个pflash
2. 透传模式：直接把qumu的pflash透传给虚拟机

地址映射的支持
两阶段的地址映射
GVA -> GPA -> HPA

虚拟机时钟中断
为了支持抢占式调度

问题：宿主环境失效问题
通过中断注入

第三阶段的时候学校事务相对来说比较忙，因此只简单地写了 print_with_color, hashmap 和 mmap 这几个较为简单的练习。

我当时参加了 lab1 挑战，通过针对测例优化内存分配器减少碎片来取得更高的分数。

因为 ArceOS 自带的 TLSF 分配器效率已经十分高了，因此一开始一度陷入僵局，后来偶然发现 Slab 分配器中内嵌一个 Buddy 分配器，想着能不能把它换成 TLSF 分配器，于是就开始了一系列的尝试。

将 Slab 中的 Buddy 分配器替换成 TLSF 分配器后，拿到了 260 分终于突破了 ArceOS TLSF 分配器的 170 分。

考虑到题目中的分配失败都是因为大量不连续的内存碎片导致的，通过观察测例的内存分配规律，于是我将 Slab 中最小 64 Bytes 的大小提高到了 96 Bytes，这样虽然有可能浪费一些内存（在所需内存小于 96 Bytes 的情况下），但是可以减少内存中不连续的碎片，最终拿到了 330 分，并得到了常规操作榜第 9 名的成绩。

通过第三阶段的学习，巩固了我对操作系统的了解，并提升了我对内存分配算法的理解；同时也让我了解到 Unikernel 和 Monolithic Kernel 的区别，Hypervisor 的原理，对操作系统的设计有了更深的认识。

第三阶段和第二阶段相比明显更加基础，虽然有一些第二阶段涉及过的内容，例如任务切换，地址空间等等，但是第三阶段重点在于ArceOS和组件化操作系统，强调了如何从裸机（或者qemu）上通过各层模块的调用实现一个完整的操作系统。

Unikernel

第一周的课程围绕着unikernel展开，讲解了使用各个组件来实现一个unikernel。包括内存分配，地址空间，任务与运行队列，调度，块设备驱动和文件系统。

以实验1为例，要求修改println的输出颜色。

不难发现println!基于ulib调用arceos_api,实现输出流调用抽象层axhal中的console::write_bytes进行不同platform的putchar()来操作sbi。所以在ulib处或者axhal处使用ANSI escape codes都可以起到目标的效果，并且在ulib处只作用于println!,而在axhal处作用于启动后的所有输出。

tour2同理，找到调用的modules/axalloc模块，发现其cargo.toml默认为未实现的lab，进行修改即可。

就这样，我们通过config，可以在rust便捷构建unikernel组件。接着的课程继续处理调度，总线，文件系统等来构建一个完整的unikernel。

Monolithic

接下来的课程带领我们从unikernel跨到宏内核，主要任务在于用户空间和内核空间的切换。

从Unikernel基础到目标最小化宏内核需要完成的增量工作：

1. 用户地址空间的创建和区域映射
2. 在异常中断响应的基础上增加系统调用
3. 复用Unikernel原来的调度机制，针对宏内核扩展Task属性
4. 在内核与用户两个特权级之间的切换机制

我了解了riscv下进入用户态的伪造现场机制，剩下的内容就是处理好用户态的地址空间，实现musl工具链。

这部分很有意思的内容有一个关于异构内核的讨论，也就是说实现异构内核的Task结构体来记录任务信息，但是在异构核上不同的task需要记录的信息是不一样的。

如果在task结构体上直接通过编译选项控制的话，不利于扩展性，使用基础属性和额外属性的关联索引则需要查找开销，所以引入类似TLS的指针扩展机制是一个折中的方案。

Hypervisor

第三周的内容就是关于RISCV的虚拟化了，虽然在之前了解过虚拟化的大致原理，但是深入了解RISCV硬件支持的hs和vs寄存器组和sv39的页表扩展，仍然感到这样的设计之精妙。

课程详细讲解了hyperv上抽象的VCPU结构体和如何实现VM_entry,VM_exit，接下来再介绍包括透传，中断等其他事项的处理。

End

受限于课业忙碌，笔者并没有对挑战任务做出贡献，也缺少对arceos的深入了解，但是课程提纲挈领的讲解令我收获良多。

前言

就组件化内核ArceOS来说，它是用于构建各种类型的操作系统的组件仓库。自然也能够支持微内核操作系统的构建，但是第三阶段中有unikernel、有monolithic-kernel、有Hyperisor，唯独没有微内核，有点遗憾。

本篇记录我对基于ArceOS构建微内核操作系统的方法的思考和实践。

需要的组件

硬件抽象层

底层硬件平台从支持aarch64开始。

• arm_pl031
• arm_gicv2

内核态

支持基本的特权操作。

• axstd
• axalloc
• paging
• axtask
• axsync

用户态

用户态主要支持块设备、网络和文件系统等。

• syscall
• axmm
• axvcpu
• vfs
• blk_drv
• fat32

内存分配器-字节分配器：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。

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

Unikernel 模式内核特点

应用与内核处于同一特权级，共享同一内存空间，编译形成一个 image 即是应用又是内核。
无隔离无切换，简单高效但安全性低。

U.1.0 Hello

输出信息到屏幕。

引导过程：axhal

• 暂存来自 openSBI 的两个参数
  • a0: hartid，当前 CPU 的 ID
  • a1: DTB 指针，设备树地址
• 设置栈
  • la sp, {boot_stack}
    • 将预设的栈地址加载到sp。
  • li t0, {boot_stack_size}
    • 将预设的栈大小加载到t0。
  • add sp, sp, t0
    • 将 sp 和 t0 的值相加并存回 sp，相当于栈指针下移 t0，为栈留出 t0 内存空间，完成栈的设置。
• 设置页表并开启 MMU
• 修正虚拟高地址
  • 由于开启 MMU 导致地址空间切换，需要将 sp 加上虚拟高地址的偏移量。
• 调用 rust_entry
  • mv a0, s0, mv a1, s1
    • 将 hartid 和 DTB指针 复制到寄存器 a0 和 a1。
  • la a2, {entry}
    • 将入口地址加载到a2寄存器。
  • add a2, a2, s2
    • 将 a2 寄存器加上虚拟高地址的偏移。
  • jalr a2
    • 跳转到 a2 地址，即执行 rust_entry 函数
  • j .
    • 无条件跳转到当前地址

引导过程：axruntime

• 打印 LOGO 和基本信息
• 初始化日志功能
• 日志打印物理内存地址信息
• #[cfg(feature = “xxx”)]
  • 按需执行各组件初始化，例如 alloc 组件需要初始化内存分配器。
• 打印 CPU 信息，原子操作使已初始化 CPU 数量加一，等待所有 CPU 初始化
• 进入 main 函数

运行过程：app:hello_world

• 没有 std 支持，不提供 main 入口
• axstd::println -> axstd::io::__print_impl -> axstd::io::Stdout::Write -> arceos_api::stdio::ax_console_write_bytes -> axhal::console::write_bytes -> riscv64_qemu_virt::putchar

U.2.0 Collections

组件：axalloc
目标：

1. 动态内存分配，支持 Vec 集合类型。
2. 动态内存分配框架和算法。

需要实现两类分配：

• Bytes Alloc
  • 支持：Rust Vec, String…
  • 接口：#[global_allocator] Trait
  • 框架：axalloc::byteAllocator
  • 算法：allocator::TlsfByteAllocator, BuddyByteAllocator, SlabByteAllocator
• Pages Alloc
  • 支持：驱动，页表自身
  • 接口：global_allocator() 全局函数
  • 框架：axalloc::pageAllocator
  • 算法：allocator::BitmapAllocator

GlobalAllocator 数据结构

使用 TlsfByteAllocator 作为字节分配器，BitmapPageAllocator 作为页分配器。

GlobalAllocator 接口

实现 #[global_allocator] Trait 和 global_allocator() 全局函数。

GlobalAllocator 框架

将字节分配器和页分配器组成一个简单的两级分配器。首先将全部内存区域分配给页分配器，然后分配一块小区域（32 KB）给字节分配器。当字节分配器分配时无可用内存时，会向页分配器请求追加内存。

U.3.0 ReadPFlash

组件：pagetable
目标：

1. 引入页表组件，通过地址空间重映射，支持设备 MMIO。
2. 地址空间概念，重映射意义，页表机制。

ArceOS 包括两阶段地址空间映射，Boot 阶段默认开启 1G 空间的恒等映射。如果需要支持 MMIO，需要指定 paging feature 实现重映射更大的空间。

PFlash

Qemu 的 PFlash 模拟闪存磁盘，启动时自动加载到固定的 MMIO 区域，读操作不需要驱动。Qemu 保留了 0 号 pflash 作为扩展固件使用， 1 号 pflash 提供给用户使用，地址是 0x2200_0000。

物理地址空间

• 0x8020_0000：kernel Image
  • .bss
  • .data
  • .rodata
  • .text
• 0x8000_0000：SBI
• 0x0C00_0000: MMIO

分页阶段 1 - 早期启用

开启分页，恒等映射 0x8000_0000 到 0xC000_0000 的 1GB 地址空间。切换前后地址范围不变，但从物理空间切换到虚拟空间。

分页阶段2 - 重建映射

新建一个空的内核地址空间，并通过页表申请一个新的页，随后通过axhal 体系无关操作将根页表地址写入到 satp 寄存器。

U.4.0 ChildTask

组件：axtask
目标：

1. 创建子任务，建立多任务基本框架。
2. 任务、运行队列。

数据结构

• entry：任务逻辑入口
• state：任务状态
• kstack：栈空间，ArceOS 任务相当于线程。
• ctx：任务调度上下文
• task_ext：扩展属性，用于宏内核和 Hypervisor 扩展。

接口

spawn & spawn_raw

生成一个新任务，加入 RUN_QUEUE。

yield_now

让出 CPU 控制权，切换到另一个已就绪任务。

sleep & sleep_until

睡眠指定时间。

exit

退出任务。

框架

初始化

运行队列初始化和定时器初始化。
初始两个任务，main是主线程任务，idle 是用于所有任务阻塞时执行的任务。

U.5.0 MsgQueue

组件：axsync
目标：

1. 任务切换机制，协作式调度算法。
2. 同步的方式，Mutex 的机制。

任务切换原理

保存当前任务上下文->切换->恢复下个任务上下文。上下文一般包含如下寄存器：

• ra：函数返回地址寄存器。
• sp：栈指针寄存器。
• s0-s11：函数调用相关寄存器。

算法

协作式调度算法 FIFO
较简单，略。

同步原语

自旋锁

单 CPU 只需关中断+关抢占。多 CPU 需要相互可见内存变量进行原子互斥操作。

互斥锁

自旋锁+等待队列

内存分配算法

TLSF，Buddy，Slab 算法。较复杂，可单独了解，略 。

U.6.0 FairSched

组件：timer
目标：

1. 抢占式调度，CFS 调度策略
2. 时钟中断机制

抢占时机

1. 内部条件：时间片耗尽
2. 外部条件：启用抢占
   内外条件都满足时，才发生抢占。

抢占式调度算法 ROUND_ROBIN

定时器递减当前任务的时间片，耗尽时允许调度。

抢占式调度算法 CFS

vruntime= init_vruntime + (delta / weight(nice))。

vruntime 最小的任务就是优先权最高的任务，即当前任务。

新任务 vruntime = min_runtime，设置优先级即设置 nice 值。

队列基于 BTreeMap，排序基于 vruntime，队首是 vruntime 最小的任务。

U.7.0 ReadBlock

组件：axdriver、drv_block、drv_virtio
目标：

1. 从磁盘块设备读数据，替换 PFlash
2. 发现设备关联驱动、块设备、VirtIO 设备

axruntime::rust_main -> axdriver::init_drivers -> AllDevices::probe -> probe_bus_devices

axruntime 在启动后期，调用 axdriver。axdriver 负责发现设备和初始化，核心结构是 AllDevices。probe 基于总线发现设备，逐个匹配驱动并初始化。

按照平台有两种总线：

1. PCI 总线，基于 PCI 总线协议。
2. MMIO 总线，一般基于 FDT 解析，目前采用两级循环探测。

Virtio 驱动和 virtio 设备交互：

1. Vring 环形队列，本质上是连续 page 页面。
2. 中断响应通道，主要用于等待读取大块数据。

U.8.0 LoadApp

组件：fatfs、axfs_vfs
目标：

1. 从文件系统加载应用和数据
2. 文件系统初始化和文件操作

文件系统 mount 的意义：把易于存储的扁平化结构目录树转为易于搜索遍历的立体化形态目录树。

本阶段忙于处理于学校的事情没有完全跟课。主要学习了Hypervisor虚拟化的内容，这也是我最感兴趣的部分。
通过实验学习，我了解到Hypervisor是如何模拟出多个虚拟机环境，让它们各自拥有独立的操作系统和硬件资，期望在后续的学习中对虚拟化技术有更深入的了解。

Arceos 总结

核心学习了arceos作为组件化设计的理念，抽象微内核、宏内核和VVM之间的共同点。

基于这些比如调度task,内存空间mmaddr,文件系统fs的底层组件，可以方便的完成需求。

lab1 内存分配挑战

通过lab1内存分配器的实现，对内存加深了理解，就是个大byte[],物理地址就是index。

lab1核心实现就是借用操作系统的分配思想，内存空间分堆区和栈区，堆区存放不需要回收的数据（一直增长，没有内存碎片），栈区放需要回收的，包括vec中间扩容的。这部分处理掉可以达到373，参考实现：

https://github.com/martin1847/oscamp/blob/lab1/arceos/labs/lab_allocator/src/lib.rs

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

# 每轮最小生存对象
>>> a = 262144 + 65536 + 16384 + 4096 + 1024 + 256 + 64 
# 每轮额外需要的临时空间
>>> tmp = sum([524288, 131072, 32768, 8192, 2048, 512, 128, 32])
699040
# [PA:0x8026f000, PA:0x88000000) free memory (READ | WRITE | FREE)
>>> total = 0x88000000 - 0x8026f000
131665920
>>> (total - tmp )/a
374.7221204907526
# 考虑每轮增加还有一部分额外内存，7 * sum[1..N]
>>> (total - tmp - 7 * sum(range(1,373)) )/a
373.33259132942686

2024 秋冬季开源操作系统训练营 项目基础阶段

进度情况：

由于忙于区域赛和大创申请书，三阶段的时间并不充足，作业仅仅做到hypervisor前的部分，仅阅读了部分源码。

Unikernel基础与框架

题1

只需要将

println!("[WithColor]: !");

改为
println!("\x1b[33m[WithColor]: Hello, Arceos!\x1b[0m");

可以打出黄色字体。

题2

要求实现HashMap，并且提供随机数，我还没办法理解随机数和HashMap的关系，所以写了一个简单的HashMap

1
2
3
4
5
6
7
8
9
10
11

struct KeyValue<K, V> {
    key: K,
    value: V,
}
pub struct HashMap<K, V> {
    buckets: Vec<Vec<Option<KeyValue<K, V>>>>,  
}
fn hash(&self, key: &K) -> usize {
    let key_ptr = key as *const _ as usize;
    key_ptr % self.buckets.len()
}

Unikernel地址空间与分页、多任务支持(协作式)

题目要求：

只能修改modules/bump_allocator组件的实现，支持bump内存分配算法。不能改其它部分。

Bumpallocator 结构体

1
2
3
4
5
6
7

pub struct EarlyAllocator<const PAGE_SIZE: usize> {
heap_start: usize,
heap_end: usize,
next: usize,
allocations: usize,
page_pos: usize,
}

Base allocator需要的init 与 add_memory

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

impl<const PAGE_SIZE: usize> BaseAllocator for EarlyAllocator<PAGE_SIZE> {
    fn add_memory(&mut self, start: usize, size: usize) -> AllocResult {
        
        self.heap_end = start + size;
        Ok(())
    }

    fn init(&mut self, start: usize, size: usize) {
        self.heap_start = start;
        self.heap_end = size + self.heap_start;
        self.next = self.heap_start;
    }
    
}

PageAllocator因没有dealloc所以未实现

1
2
3
4
5
6
7
8

fn alloc_pages(&mut self, num_pages: usize, align_pow2: usize) -> AllocResult<usize> {
let align_mask = (1 << align_pow2) - 1;
let required_size = num_pages * PAGE_SIZE;
let aligned_pos = (self.page_pos + align_mask) & !align_mask;
let allocated_pages = aligned_pos;
self.page_pos = aligned_pos + required_size;
Ok(allocated_pages)
}

ByteAllocator

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

impl<const PAGE_SIZE:usize> ByteAllocator for EarlyAllocator<PAGE_SIZE>{
    fn alloc(&mut self, layout: Layout) -> AllocResult<NonNull<u8>> {
        let alloc_start = self.next;
        self.next = alloc_start + layout.size();
        self.allocations += 1;
        Ok(unsafe { NonNull::new_unchecked(alloc_start as *mut u8) })

    }
    fn dealloc(&mut self, pos: NonNull<u8>, layout: Layout) {
        self.allocations -= 1;
        if self.allocations == 0 {
            self.next = self.heap_start;
    }
    }

从Unikernel到宏内核

题目要求：

需要补全缺页加载代码。

观察m1.0.0 task中代码，发现用 current().task_ext()可以得到TaskExt，然后TaskExt中包含一个AddSpace 结构体，该结构体实现了处理缺页加载的方法。于是按照该思路需要补充的代码如下

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

use axhal::{mem::VirtAddr,paging::MappingFlags};
use axhal::trap::{register_trap_handler,PAGE_FAULT};
#[register_trap_handler(PAGE_FAULT)]
fn handle_page_fault(vaddr: VirtAddr, access_flags: MappingFlags, is_user: bool) -> bool {
    if is_user {
        if !axtask::current()
            .task_ext()
            .aspace
            .lock()
            .handle_page_fault(vaddr, access_flags)
        {
            ax_println!("handle_page_fault failed, vaddr={:#x}", vaddr);
            axtask::exit(-1);
        } else {
            true
        }
        
    } 
    else{
        false
    }
    
}

感想：与 Rcore 相比，似乎 ArceOS显得更加复杂，因其为了实现模块之间的兼容性，采用了多层的封装、抽象和隔离机制。然而，从我的编程体验来看，从某个特定模块的视角来看，阅读 ArceOS 的代码反而比 Rcore 更加清晰。降低了局部代码阅读难度，是值得学习的编码习惯。同时，ArceOS 的课程内容十分丰富，极大地拓宽了我的操作系统视野。