PageFault

本 Lab 可以说是 CSAPP 的几个 Lab 中最为人津津乐道的一个，对应知识点为书中的第 3 章（程序的机器级表示），要求使用 GDB 调试器，对汇编语言进行调试，从而得出正确的“拆弹密码”。共分为 6 个关卡和一个隐藏关卡，每个关卡都分别考察了一种语法结构或数据结构的汇编表示，部分关卡逻辑比较复杂，要求对 x86 汇编有一定的熟悉度。 bomb.c1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980int 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 ru...

CSAPP 的第一个 Lab，对应知识点为书中的第 2 章（信息的表示与处理），要求使用受限制的运算符和表达式实现一些位操作。主要分为两个部分：整数部分和浮点数部分。其中整数部分限制较多，比较偏重技巧性，部分题个人认为很有难度。而浮点数部分则比较基础，主要考察对 IEEE 754 标准的熟悉程度，代码较长，但思路相对简单。 bitXor思路使用德-摩根定律进行推导，推导过程如下： 代码1234int bitXor(int x, int y) { // 德-摩根定律 return ~(~(x & ~y) & ~(~x & y));} tmin思路最小整数即最高位（负数权重）为 1，其余（正数权重）为 0。 代码123int tmin(void) { return 1 << 31;} isTmax思路由于不能使用左移运算符，因此没办法直接构造出 tmax，需要仔细考虑 tmax 的性质：tmax = 0x7fffffff ，而 tmax + 1 = 0x80000000 ，这两个数的二进制...

Large files思路xv6 文件系统的 inode 中地址域 addrs[] 由 12 个直接地址和 1 个一级间接地址组成，本实验要求将地址域更改为 11 个直接地址、1 个一级间接地址和 1 个二级间接地址组成，以支持更大文件的存储。 代码的实现有了直接地址和一级间接地址做参考，就很简单了，直接查看代码部分即可。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107diff --git a/kernel/file.h b/kernel/file.hindex b076d1d..5c4eb3a 100644--- a/kernel/file.h+++ b/kernel/file.h@@ -26,7 +...

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...

Implement copy-on write背景xv6 使用 fork() 系统调用创建子进程时，需要将父进程的地址空间进行 深拷贝 ，即将页表和实际物理空间同时进行拷贝，以实现父进程和子进程地址空间的独立性。但很多时候，如 shell 程序，fork() 通常与 exec() 搭配使用，首先使用 fork() 创建子进程，随后在子进程中使用 exec() 将指定的程序加载到当前地址空间，这样在 fork() 中进行的地址空间拷贝就白白浪费了。 本实现要求实现一个写时复制（copy-on write）的 fork() 系统调用。具体来说，在进行虚拟内存拷贝时，不直接进行物理内存的拷贝，只是将父进程的页表复制给子进程，这样子进程和父进程的每个虚拟页面都指向了同一个物理页面，当子进程需要对某个虚拟页面进行写入时，为了保证父进程和子进程之间的独立性，子进程此时将进行物理内存的分配和拷贝，再进行写入。 实现方案根据提示，可以将上述的写时复制的思路用 异常 的方式来实现。 首先可以利用页表项的 flags 中的 RSW 位来表示页表项是否为 COW 页，以便后续的异常处理。 修改 uvm...

使用gdb调试xv6内核从最近两个 Lab 开始，代码逻辑的复杂度明显上升，对内核进行调试可能是帮助理解操作系统机制的绝佳方法。因此在开始本 Lab 之前，我们先来配置一下针对 xv6 内核的 gdb 调试器。 安装 gdb-multiarch. 利用包管理工具进行安装，我使用的是 Ubuntu 系统，执行以下命令： 1sudo apt install gdb-multiarch 在 xv6 项目根目录下可以看到 .gdbinit 文件，其中已经写好了一些 gdb 的初始化选项，使用文本编辑器或 cat 命令查看： 123456set confirm off set architecture riscv:rv64 target remote 127.0.0.1:26000 symbol-fil...

Speed up system calls思路题目要求在每个进程初始化时为它的页表插入一个页表项，内核通过这样预先缓存页表项的操作，来加速特定系统调用的执行速度。 由于前不久刚过完一遍《OSTEP》，因此我认为自己对页表机制还算比较熟悉，应对本 Lab 理应比较轻松，但在真正上手的时候，还是觉得有些无所适从，无奈老老实实地把 xv6 手册的第 3 章对照着代码仔细研读了一番，从中提炼出了几个关键的函数： kernel/kalloc.c:kalloc 1void *kalloc(void); 遍历空闲链表，寻找一个可分配的物理页面。若找到，返回该页面的首（物理）地址；否则，返回 0 （空指针）。 kernel/kalloc.c:kfree 1void kfree(void *pa); 释放已分配的首地址为 pa 的物理页面，并更新空闲链表。 kernel/proc.c:allocproc 1static struct proc *allocproc(void); 遍历进程数组 proc，寻找未被使用的 struct proc。若找到，则初始化其状态，为创建一个新的页表，...

xv6系统调用实现不同于 Lab1 利用已实现的系统调用来实现一些用户态下的命令行程序，本 Lab 是要在内核层面实现一些系统调用。这其中难免涉及到一些对内核数据结构的操作，以及处理器体系结构（本系列 Lab 基于 RISCV）相关的内容，那么首先有必要梳理一下 xv6 下系统调用的实现过程。 xv6 系统调用的实现： 以 trace 系统调用为例，用户通过调用 user/user.h 中的函数 trace 进行系统调用。 通过调用 Perl 脚本 user/usys.pl 生成的一系列汇编代码，该汇编代码的作用是设置寄存器的内容并实现用户态到内核态的切换，内核后续针对寄存器中的内容执行相应的系统调用操作。以下是对 user/usys.pl 代码的逐行解析： #!/usr/bin/perl -w：这是一个Perl脚本的“shebang”行，指定使用/usr/bin/perl解释器执行此脚本，并开启警告（-w）选项。 print "# generated by usys.pl - do not edit\n";：打印注释说明此文件是由usys.pl脚本...

Boot xv6按照示例切换到 util 分支后，看到目录下包含 Makefile 文件，执行 make qemu 即可。 sleep思路借助系统调用 sleep 实现一个命令行程序，关键是要找到封装了系统调用的 C 函数的位置，根据提示： … user/user.h for the C definition of sleep callable from a user program … 可知该函数的声明位于 user.h 头文件中，声明方式很简单： 1int sleep(int); 将其“拷贝”（include）到需要编写的代码 user/sleep.c 中，调用 sleep(<睡眠时间>) 即可。 最后，按照提示，将编写的 sleep 代码添加到 Makefile 的 UPROGS 中，添加后如下所示： 123456789101112131415161718UPROGS=\ $U/_cat\ $U/_echo\ $U/_forktest\ $U/_grep\ $U/_init\ $U/_kill\ $U/_ln\ ...

本文将介绍操作系统导论（Operating Systems: Three Easy Pieces）作者所开源的操作系统相关课程项目 的 KV 部分，包含个人的代码实现和设计思路。 思路题目要求实现一个最简单的数据库，以支持数据的持久化。 每个操作由格式为 op,[arg1],[arg2] 的命令给出，那么首先要解决的问题就是参数的分离，再根据操作符 op 来对不同的操作进行特殊处理。字符串划分这里采用的是 strsep() 函数：该函数接收两个参数 char** stringp 和 const char* delim，stringp 是指向待分割字符串 string 的指针，delim 则是指定的分隔符，该函数的操作是查找 string 中第一个 delim 的位置 it，并将 stringp 指向 string 中 it + 1 的位置，同时返回string 开头到 it 所有字符所构成的子串（加上 '\0' 终结符）。 插入操作没什么好说的，直接使用 fprintf() 写入文件即可。对于查找和删除，则需要将数据从文件（数据库）中读取到内存，存储在特定的数...