2024开源操作系统训练营 rCore Chapter8练习
编程作业思路本实验要求为死锁和信号量机制实现死锁检测功能,并提供系统调用 enable_deadlock_detect,用以开启和关闭死锁检测功能。在开启死锁检测功能的情况下,用户使用 mutex_lock 或 semaphore_down 尝试获取互斥资源时,如果发现系统处于不安全状态(可能发生死锁)时拒绝对应的资源获取请求。
实验手册中介绍的死锁检测算法为银行家算法(Banker's Algorithm),由 Dijkstra 提出,算法的流程可以参照手册,这里不再详细介绍,代码实现如下:
/// Banker's Algoritm for dead lock check
fn deadlock_check(available: Vec<usize>, allocation: Vec<Vec<usize>>, need: Vec<Vec<usize>>) -> bool {
// n: thread count m: resources count
let (n, m) = (allocation.len(), al ...
2024开源操作系统训练营 rCore Chapter6练习
编程作业思路linkat本实验需要实现 3 个与文件系统相关的系统调用,首先是用来创建文件硬链接的 linkat.
首先介绍一下什么是硬链接,硬链接作为一种抽象概念,可以看作指向一个文件实体的指针,类似于 C++ 中的智能指针 shared_ptr。而从内核代码的角度来看,硬链接在文件系统中的实体就是 文件目录项 。每个硬链接对应一个目录项,这个目录项指向一个相同的索引节点(inode),每个 inode 存储了文件的实际数据块(的指针)及其元数据(文件大小、文件类型等)。
由于 rCore 的文件系统被简化为单级目录(只包含根目录),因此实现 linkat 的思路就很清晰了:根据文件名 old_name 查找其对应的 inode,获取 inode_id 并将引用计数加一,创建一个新的目录项 (new_name, inode_id),将其插入根目录的数据段末尾。
需要注意的是,rCore 文件系统的 inode 分为虚拟文件系统层的 Inode 和在持久化设备(硬盘)上实际存储的 DistInode,可以通过 Inode 所实现的 read_disk_inode 和 modify_di ...
2024开源操作系统训练营 rCore Chapter5练习
编程作业思路进程创建如果只是想根据特定程序来创建进程,而不需要 fork + exec 组合提供的灵活性(如文件重定位等),那么 spawn 将是一个更简洁且效率更高的选择,本实验要求便是实现它。
对于 spawn 的实现,确实可以简单地将 fork 和 exec 拼接起来。但需要注意的是,fork 首先拷贝父进程的地址空间,exec 再将该地址空间替换,二者融合后最开始地址空间的拷贝其实是徒劳的。如以下代码所示:
let memory_set = MemorySet::from_existed_user(&parent_inner.memory_set); // futile code!
...
let (memory_set, user_sp, entry_point) = MemorySet::from_elf(elf_data);
stride 调度算法实现一个简单的步长调度算法,由于算法思路比较简单,这里直接介绍实现方式。
首先,为了保存进程的“步长”和优先级信息,需要为进程控制块添加两个字段 stride 和 prio(不考虑性能,为了实现的简单,pass 字段 ...
2024开源操作系统训练营 rCore Chapter4练习
编程作业思路重写 sys_get_time 和 sys_task_info首先,第一个任务:由于引入了虚拟内存后,sys_get_time 和 sys_task_info 失效了,需要进行重写。
这里解释一下为什么会失效:以 sys_get_time 为例,用户在发起系统调用时,传入的参数 _ts 是用户态下的虚拟地址,它需要借助内核的软件地址转换机制,查找任务对应的页表,将 _ts 转换为物理地址,再对该地址处的值进行填充。这里可以使用 page_table.rs 中预先实现好的 translated_byte_buffer,它将一整个虚拟地址段翻译为一系列的物理地址段(每页一段),这样如果结构体 TimeVal 和 TaskInfo 横跨多个页面也同样适用。
注意,内核态代码中的地址仍然是虚拟地址,只不过在 rCore 中,内核态的低 256GB 为直接映射,因此好像内核代码在直接访问物理地址,其实还是虚拟地址。
实现 mmapPOSIX 标准中的 mmap 是将一个文件或其他对象的数据映射到进程的地址空间中,而本实验需实现的 mmap 则为简化版本,只是简单地向进程地址空间中 ...
2024开源操作系统训练营 rCore Chapter3练习
编程作业思路rCore 的第一个实验,主要是为了熟悉如何进行内核编程,实现起来比较简单。
要求实现一个系统调用,填充传入的 TaskInfo 结构体已获取当前任务的一些信息,包含三个字段:任务状态、任务使用的系统调用及调用次数、系统调用时刻距离任务第一次被调度时刻的时长(单位 ms)。
首先是任务状态,这个比较简单,直接查看当前任务的任务控制块的字段值即可。
对于系统调用次数,可以在任务控制块中添加新的字段来存储相关信息,例如按提示所说,一个长度为 MAX_SYSCALL_NUM 的整型数组。在函数 syscall/mod.rs:syscall 中,在内核对用户态传入的系统调用号进行分发处理前,增加对应的系统调用桶的计数。注意,由于本次系统调用 sys_task_info 也要进行计数,因此不能在执行了特定的系统调用后再来增加计数,否则本次 sys_task_info 系统调用次数将无法被统计。
最后是距离任务第一次被调度时刻的时长,一种实现方式是:为任务控制块添加新的字段:time,表示任务第一次被调度的时间。先为 time 设定一个初始值(例如 0),表示该值未被更改过,每当一个任 ...
CSAPP Attack Lab
个人感觉非常有意思的一个 Lab,涉及的知识面比较窄,主要关注 缓冲区溢出漏洞 这一个方面,并基于此进行代码攻击,体验一把做黑客的感觉,对应知识点为书中的 3.10 节内容。
这个 Lab 上手便给了我当头一棒,在环境配置上琢磨了好一阵。直接运行 ./ctarget -q ,程序没有让进行输入,而是直接触发了段错误,后来尝试在跑在学校的 Linux 服务器上得以正常运行,原因不明,推测是 WSL 的锅??
phase_1在倒腾好环境之后,终于可以开始着手完成实验了。
phase_1 要求我们在调用 getbuf 读取标准输入后,不返回到 test 函数接着执行 printf,而是转而执行 touch1.
void test()
{
int val;
val = getbuf();
printf("No exploit. Getbuf returned 0x%x\n", val);
}
可以利用书中 3.10.3 节提到的知识,向缓冲区中写入过量的数据,大到足以覆盖掉调用 getbuf 时压入栈中的返回地址,将其修改为我们想要跳转执行的 ...
CSAPP Bomb Lab
本 Lab 可以说是 CSAPP 的几个 Lab 中最为人津津乐道的一个,对应知识点为书中的第 3 章(程序的机器级表示),要求使用 GDB 调试器,对汇编语言进行调试,从而得出正确的“拆弹密码”。共分为 6 个关卡和一个隐藏关卡,每个关卡都分别考察了一种语法结构或数据结构的汇编表示,部分关卡逻辑比较复杂,要求对 x86 汇编有一定的熟悉度。
bomb.cint main(int argc, char *argv[])
{
char *input;
/* Note to self: remember to port this bomb to Windows and put a
* fantastic GUI on it. */
/* When run with no arguments, the bomb reads its input lines
* from standard input. */
if (argc == 1) {
infile = stdin;
}
...
CSAPP Data Lab
CSAPP 的第一个 Lab,对应知识点为书中的第 2 章(信息的表示与处理),要求使用受限制的运算符和表达式实现一些位操作。主要分为两个部分:整数部分和浮点数部分。其中整数部分限制较多,比较偏重技巧性,部分题个人认为很有难度。而浮点数部分则比较基础,主要考察对 IEEE 754 标准的熟悉程度,代码较长,但思路相对简单。
bitXor思路使用德-摩根定律进行推导,推导过程如下:
代码int bitXor(int x, int y) {
// 德-摩根定律
return ~(~(x & ~y) & ~(~x & y));
}
tmin思路最小整数即最高位(负数权重)为 1,其余(正数权重)为 0。
代码int tmin(void) {
return 1 << 31;
}
isTmax思路由于不能使用左移运算符,因此没办法直接构造出 tmax,需要仔细考虑 tmax 的性质:tmax = 0x7fffffff ,而 tmax + 1 = 0x80000000 ,这两个数的二进制位 ...
MIT6.s081 2021 Lab File system
Large files思路xv6 文件系统的 inode 中地址域 addrs[] 由 12 个直接地址和 1 个一级间接地址组成,本实验要求将地址域更改为 11 个直接地址、1 个一级间接地址和 1 个二级间接地址组成,以支持更大文件的存储。
代码的实现有了直接地址和一级间接地址做参考,就很简单了,直接查看代码部分即可。
代码diff --git a/kernel/file.h b/kernel/file.h
index b076d1d..5c4eb3a 100644
--- a/kernel/file.h
+++ b/kernel/file.h
@@ -26,7 +26,7 @@ struct inode {
short minor;
short nlink;
uint size;
- uint addrs[NDIRECT+1];
+ uint addrs[NDIRECT+2];
};
// map major device number to device functions.
diff --git a/kernel/fs.c b ...
MIT6.s081 2021 Lab Multithreading
Uthread: switching between threads思路xv6 已经实现了进程的切换机制,本实验要求参考进程的切换,实现一个用户态线程的切换。
要实现线程切换,必然涉及上下文,即寄存器的保存和恢复,那么需要保存哪些寄存器?实际上,只需要保存被调用者保存寄存器(callee-saved registers),而实现调用者保存寄存器(caller-saved registers)的保存与恢复的代码由编译器自动生成。关于调用者保存与被调用者保存寄存器有哪些可以参照下述 RISC-V 的 calling convention:
另外,根据 user/uthread_switch.S 的注释,thread_switch 最后通过 ret 指令将当前程序计数器的值切换为 ra 寄存器中存储的地址,实现进程的“切换”,因此 struct thread 中还需要保存每个线程对应程序的起始地址(即函数指针)。
在了解需要保存哪些寄存器之后以及如何进行线程切换之后,还有一个细节需要考虑,即栈指针寄存器(sp)的初始化。线程栈的存储位置为 struct thread 中的 stack 数组 ...