0%

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 三个字段,其中 keybitset 是用来唤醒任务的重要字段。

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

任务等待队列存储在 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 需要的实现方案。

这部分的实现首先需要处理一个读取 mhartidcsrr 指令。我一开始曾希望直接解析指令后执行对应操作,来实现 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内存分配
分别为BaseAllocatorByteAllocatorPageAllocator实现特征即可

实现相关特征即可,注意在页分配的时候进行对齐,字节分配器下的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的原始应用直接在我们宏内核上直接运行

实现兼容页面,包含syscallprocfs & 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, hashmapmmap 这几个较为简单的练习。

我当时参加了 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