Arceos 训练营总结

转眼间两个多月的训练营要进入尾声了。
还记得国庆回山东的高铁上，在刷rustlings的算法题，小根堆的实现。

从二阶段的rCore到组件化的arceos,一路下来，对OS几大部件CPU虚拟化、内存虚拟化和文件系统虚拟化有了更深刻的理解。

下面我也从这几个方面来分别做个总结。

mocklibc

ELF结构

ELF Header

描述整个文件的组织。

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 struct Elf32_Ehdr {
    // Magic、Class（32-bit vs 64-bit）、Data（2's complement、endian）、ELF Version、OS/ABI、ABI Version
    pub e_ident: [u8; abi::EI_NIDENT],
    // Relocatable file、Executable file、Shared object file、Core file
    pub e_type: u16,
    // CPU 平台属性
    pub e_machine: u16,
    // ELF 版本号，通常为1
    pub e_version: u32,
    pub e_entry: u32,
    pub e_phoff: u32,
    pub e_shoff: u32,
    pub e_flags: u32,
    // Size of elf header
    pub e_ehsize: u16,
    // Size of ph entry
    pub e_phentsize: u16,
    // Number of ph
    pub e_phnum: u16,
    // Size of sh entry
    pub e_shentsize: u16,
    // Number of ph
    pub e_shnum: u16,
    // Section header string table index
    pub e_shstrndx: u16,
}

pub struct Elf64_Ehdr {
    ...
    pub e_entry: u64,
    pub e_phoff: u64,
    pub e_shoff: u64,
    ...
}

Sections 和 Segments

segments是从运行的角度来描述elf文件，sections是从链接的角度来描述elf文件，在链接阶段，可以忽略program header table来处理此文件，在运行阶段可以忽略section header table来处理此程序（所以很多加固手段删除了section header table）。一个segment包含若干个section。

Program Header Table

描述文件中的各种segments，用来告诉系统如何创建进程映像的。

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

pub struct ProgramHeader {
    /// Program segment type
    pub p_type: u32,
    /// Offset into the ELF file where this segment begins
    pub p_offset: u64,
    /// Virtual adress where this segment should be loaded
    pub p_vaddr: u64,
    /// Physical address where this segment should be loaded
    pub p_paddr: u64,
    /// Size of this segment in the file
    pub p_filesz: u64,
    /// Size of this segment in memory
    pub p_memsz: u64,
    /// Flags for this segment
    pub p_flags: u32,
    /// file and memory alignment
    pub p_align: u64,
}

p_type

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

/// Program header table entry unused
pub const PT_NULL: u32 = 0;
/// Loadable program segment
pub const PT_LOAD: u32 = 1;
/// Dynamic linking information
pub const PT_DYNAMIC: u32 = 2;
/// Program interpreter
pub const PT_INTERP: u32 = 3;
/// Auxiliary information
pub const PT_NOTE: u32 = 4;
/// Unused
pub const PT_SHLIB: u32 = 5;
/// The program header table
pub const PT_PHDR: u32 = 6;
/// Thread-local storage segment
pub const PT_TLS: u32 = 7;
/// GCC .eh_frame_hdr segment
pub const PT_GNU_EH_FRAME: u32 = 0x6474e550;
/// Indicates stack executability
pub const PT_GNU_STACK: u32 = 0x6474e551;
/// Read-only after relocation
pub const PT_GNU_RELRO: u32 = 0x6474e552;
/// The segment contains .note.gnu.property section
pub const PT_GNU_PROPERTY: u32 = 0x6474e553;
/// Values between [PT_LOOS, PT_HIOS] in this inclusive range are reserved for
/// operating system-specific semantics.
pub const PT_LOOS: u32 = 0x60000000;
/// Values between [PT_LOOS, PT_HIOS] in this inclusive range are reserved for
/// operating system-specific semantics.
pub const PT_HIOS: u32 = 0x6fffffff;
/// Values between [PT_LOPROC, PT_HIPROC] in this inclusive range are reserved
/// for processor-specific semantics.
pub const PT_LOPROC: u32 = 0x70000000;
/// Values between [PT_LOPROC, PT_HIPROC] in this inclusive range are reserved
/// for processor-specific semantics.
pub const PT_HIPROC: u32 = 0x7fffffff;

Section Header Table

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

pub struct SectionHeader {
    /// Section Name,对应字符串在string table段中的偏移
    pub sh_name: u32,
    /// Section Type
    pub sh_type: u32,
    /// Section Flags
    pub sh_flags: u64,
    /// in-memory address where this section is loaded
    pub sh_addr: u64,
    /// Byte-offset into the file where this section starts
    pub sh_offset: u64,
    /// Section size in bytes
    pub sh_size: u64,
    /// Defined by section type
    pub sh_link: u32,
    /// Defined by section type
    pub sh_info: u32,
    /// address alignment
    pub sh_addralign: u64,
    /// size of an entry if section data is an array of entries
    pub sh_entsize: u64,
}

自定义加载ELF

静态链接

编译选项：

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

STATIC_FLAG = \
-nostdlib \
-nostartfiles \
-nodefaultlibs \
-ffreestanding \
-O0 \
-mcmodel=medany \
-static \
-no-pie \
-L./target/riscv64gc-unknown-linux-musl/release/ -lmocklibc

riscv64-linux-musl-gcc hello.c $(STATIC_FLAG) -o hello

静态编译的可执行文件加载比较简单，直接将其加载到内存中的一块连续空间即可。

唯一要注意的是同时开启-static和-no-pie选项才能生产类型为EXEC (Executable file)的ELF文件，同时还需要通过linker.ld链接脚本正确设置起始地址。

动态链接

编译选项：

1
2
3
4
5
6
7
8
9
10

DYNAMIC_FLAG = \
-nostdlib \
-nostartfiles \
-nodefaultlibs \
-ffreestanding \
-O0 \
-mcmodel=medany \
-L./target/riscv64gc-unknown-linux-musl/release/ -lmocklibc

riscv64-linux-musl-gcc hello.c $(DYNAMIC_FLAG) -o hello -Wl,-dynamic-linker /path/to/ld-musl-riscv64.so.1

linux加载动态链接的可执行文件流程比较复杂，一方面是系统在执行应用前有很多额外的处理，另一方面是加载器本身不提供函数，需要加载一系列的动态链接库。而在我们当前的Unikernel框架下，并不存在动态链接库，系统启动时所有函数都加载到了内存中，因此可以大幅简化加载流程。

首先解析program header将elf文件中类型为PT_LOAD的segment加载到内存中，然后解析.dynsym、.rela.plt节的信息可以知道需要动态链接的函数名，以及重定位条目在内存中的位置。在内核中建立了函数名到对于函数地址的映射，根据这些信息修改重定位条目就能让程序正确执行。

参与方向：宏内核，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 周了，看着自己从对操作系统毫无概念一步步到现在还是很感慨的。感谢老师的辛勤付出，感谢训练营能给我一个这样的平台。

好的，这里是冰轩。

奇怪的 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的深入了解，但是课程提纲挈领的讲解令我收获良多。