本 Lab 需要实现一个内存分配器，技巧性较强，对应知识点为书中的第 9 章的第 9.9 节。个人认为是所有 Lab 中难度最高的一个，我这里也是时间所迫，只参照教材实现了隐式空闲链表，显式空闲链表的实现尚存在一些 bug，在本文暂不介绍。 思路实验要求实现 mm_init, mm_malloc, mm_free, mm_realloc。 mm_malloc 需要返回 8 字节对齐的指针。 mm_realloc: 返回一个指向至少 size 字节的内存区域指针。 如果 ptr 为空，作用等同于 mm_malloc(size)。 如果 size 等于 0，作用等用于 mm_free(ptr)。 如果 ptr 非空，将 ptr 指向区域的大小更改为 size 字节，并返回新区域的内存地址。 隐式空闲链表首先介绍一下书中介绍的隐式空闲链表的设计，主要分为两个方面：空闲块的设计和空闲链表的组织。 空闲块的设计 一个空闲块由三部分组成：首部、载荷（可能包含填充）和尾部。头部和尾部的内容完全一致，之所以要引入这样的冗余信息，是为了实现常数时间复杂度的反向访问。因为内存载荷大小的不确定性，因此 ...

本 Lab 需要实现一个简易的 shell，主要考察对进程和信号的理解，以及对与其相关的 POSIX API 的使用，对应知识点为书中的第 8 章内容。 思路实验要求实现一个简单的 shell，要求支持如下特性： 输入 ctrl-c 触发 SIGINT 信号，输入 ctrl-z 触发 SIGTSTP 信号，发送给给前台运行的任务和依赖于这些任务的子任务（子进程）。 如果命令行以 & 结尾，那么本次作业将被置于后台运行，否则置于前台运行。 每个作业可以通过 PID（process id）或 JID（job id）来指定，其中 JID 需要加上前缀 %。 支持下列内建命令： quit：终止 shell 的运行。 jobs：列出所有的后台作业。 bg <job>：重启 <job>（PID 或者 JID），通过发出 SIGCONT 信号，然后将其运行在后台。 fg <job>：重启 <job>（PID 或者 JID），通过发出 SIGCONT 信号，然后将其运行在前台。 回收所有的僵尸进程。 命令行解释执行eval 函数的作用是 ...

本 Lab 主要考察对计算机高速缓存（Cache）机制的理解，以及如何针对 Cache 进行程序的优化，对应知识点为书中的 6.4 ~ 6.6 节内容。 Part A: Writing a Cache Simulator思路基本流程Part A 需要实现一个 Cache 模拟器，能够根据 valgrind 工具所生成的访存跟踪数据，模拟在特定参数的 Cache 环境下的命中（hits）次数、不命中（misses）次数和置换（evictions）次数，目标是实现与 csim-ref 同等的功能。模拟器需要具备的几个功能模块如下： 对命令行参数进行参数解析。 读取 trace 文件并解析为地址访问流。 定义 Cache 模拟器数据结构，以及相关的函数操作，包括初始化和地址访问。 遍历解析出来的地址访问流，依次进行访问模拟，计算得到命中次数等信息。 接下来分别对它们进行介绍。 命令行参数解析根据实验手册的提示，可以使用 getopt 函数进行命令行参数的解析。另外，如果需要支持长选项（形如 --opt arg），则可以使用 GNU C 库提供的扩展版本 getopt_long ...

编程作业思路本实验要求为死锁和信号量机制实现死锁检测功能，并提供系统调用 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(), alloc ...

编程作业思路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 ...

编程作业思路进程创建如果只是想根据特定程序来创建进程，而不需要 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 字段省 ...

编程作业思路重写 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 则为简化版本，只是简单地向进程地址空间中 ...

编程作业思路rCore 的第一个实验，主要是为了熟悉如何进行内核编程，实现起来比较简单。 要求实现一个系统调用，填充传入的 TaskInfo 结构体已获取当前任务的一些信息，包含三个字段：任务状态、任务使用的系统调用及调用次数、系统调用时刻距离任务第一次被调度时刻的时长（单位 ms）。 首先是任务状态，这个比较简单，直接查看当前任务的任务控制块的字段值即可。 对于系统调用次数，可以在任务控制块中添加新的字段来存储相关信息，例如按提示所说，一个长度为 MAX_SYSCALL_NUM 的整型数组。在函数 syscall/mod.rs:syscall 中，在内核对用户态传入的系统调用号进行分发处理前，增加对应的系统调用桶的计数。注意，由于本次系统调用 sys_task_info 也要进行计数，因此不能在执行了特定的系统调用后再来增加计数，否则本次 sys_task_info 系统调用次数将无法被统计。 最后是距离任务第一次被调度时刻的时长，一种实现方式是：为任务控制块添加新的字段：time，表示任务第一次被调度的时间。先为 time 设定一个初始值（例如 0），表示该值未被更改过，每当一个任 ...

个人感觉非常有意思的一个 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 时压入栈中的返回地址，将其修改为我们想要跳转执行的程序 ...

本 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; } ...