好的，这里是冰轩。

奇怪的 Hashmap implementation

在 Hashmap exercise 中，由于我一开始并未有实现此类数据类型的经验，参考 rust std 原有的库又有较大的心智负担，我最终选择参考《算法导论》一书中的对应部分来实现。

在 Hash 生成部分，由于我未能成功调用 rust 原有的 Hash 算法，并且我希望 Hash 算法能够相较简单，我选择了实现书中的乘法散列法算法。而至于 Hashmap 本身的实现就较为简单，其内部含有一个元素量为 Hash 最大值 + 1 的 List<Vec>，每个 Vec 存储一个包含了 Key 和元素的元组，每次添加时在 List[hash_of_key] 处推入元组，查找时从 List[hash_of_key] 处查找是否含有对应 key 完全相同的项。

虽然一开始因为 List 给的过大导致栈爆了，不过幸好，缩小以后，测例便成功过了。

带有遗憾的简易 Hypervisor

在根据根据课程逐渐熟悉框架代码以及根据课程真正了解一个 Hypervisor 的原理之后，剩下的就好说了。对两次指令的异常进行处理，然后返回正常的值，lab 就完成了…对吧？

然而我预计错了这个 lab 需要的实现方案。

这部分的实现首先需要处理一个读取 mhartid 的 csrr 指令。我一开始曾希望直接解析指令后执行对应操作，来实现 expected behavior，并确保这部分代码的鲁棒性。然而，我却想得复杂了，因为直到我开始考虑 mhartid 寄存器值的来源，以及发现其期望值为 0x6688，像是随便返回了一个数字，所以，我意识到，这题的实现很可能并不该如此复杂。最终，这部分我选择保留一部分之前解析并判断 Instruction 的代码，以及通过将 sepc 增加 4，并直接设置 A1 至 0x6688 的方式，直接针对结果实现。后续的 LoadGuestPageFault 我也如此实现。测试用例很轻松地过了，不出意外这个 lab 应该没太大问题了。

然而，意外还是出现了。第二天一早，我惊讶地发现它会在执行 Guest 指令时卡死。通过 LOG=trace，我发现它是在进行磁盘 io 的时候卡死。这牵扯到的问题实在太大，要进行大量的调试，更糟糕的是，这个问题触发很随机。然而，我没能在挂着调试器的情况下再见到过一次这个问题。最后，我还是放弃了解决这个问题。

简单快速的 h_2_0

这个 exercise 原有的 HV 框架已经给出了函数 load_vm_image，可以用于从磁盘读取文件并放置至地址空间，并且基本可以用于读取任何二进制文件，使得此 exercise 变得较为简单。

这个函数使得实现十分直接，我写出了一个简单的 write_pflash_img.sh ，用于生成带有 pfld Magic Number 的文件并放进磁盘镜像中。随后，注释掉原有直通模式代码，并取消注释模拟模式代码。最后，在每次缺页时，利用 load_vm_image 函数加载文件，并放到对应缺页的位置，这部分也就基本解决了。

与之前的简易 Hypervisor 不同，得益于对框架功能的有效复用，以及较为直接的实现，这次的实现并没有遇到随机卡死或调试困难的故障，测试用例也可以顺利通过。

你们好，我是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已经很难了，题目若再有压力，我会直接躺平。我承认我很脆弱。

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

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

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

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

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

我的回答是否定的。

第三阶段总结

第三阶段难度与前两阶段相比难度上升不少.
课程框架代码质量也是非常高的, 适配了常见CPU指令集, 是可以应用到实际生产系统中的代码框架.
尽管完成实验所需要的代码量不高, 但对题目和计算机结构的理解要求提高了非常多. 本阶段课程结束后我学到了 unikernel 模式和 Hypervisor 工作原理, 受益匪浅.
还参加了三阶段的 Allocator 排名竞赛, 锻炼了自己的意识和眼界.
四阶段已经选择了异步操作系统课题, 希望自己继续努力, 完成所有课程.

第一阶段总结

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 的意义：把易于存储的扁平化结构目录树转为易于搜索遍历的立体化形态目录树。