OS2026上机真题解析

写在前面

我本人并不强，根本也没过几个extra（，写这篇博客的目的主要是闲想帮助别人嗯！

题目在另外一篇博客里（不过27年应该是用不到？毕竟有pre-exam/pre-extra，那可能28年能用到吧？

写这篇博客时意识到，好几次与extra失之交臂，当时其实就差那么一点点，结果上机时就总是有东西写不出来/de不出来bug。回看我也感到非常可惜，上机结束后一问ai忽然意识到哇去，原来这么简单！但是这些马后炮都已经晚了嗯（。这里也想告诉各位上机失利不要难过，跌跌绊绊才是常态。

接下来是一些使用跳板机的心得~
在vim中：
shift+g 可以直接跳到文件末尾
u是撤销上一步
斜杠可以查找，如/what可以在文件中查找what，点击N可以跳到下一处

在.vimrc可以加上

set tags=tags
set tags=./tags;/

set mouse=a

最后一条是可以使用鼠标操作。
前两条就是和ctags相关的，每次把变量、函数声明完之后，可以在你的学号的目录下使用
ctags -R .
最后就可以使用ctrl + ]跨文件跳进函数，ctrl + O返回了，非常方便~

lab0 exam

我们要动的实际只有msrc/Makefile一个文件，题目给的模板如下

include makefile.inc

COMMON_FILE = main.c post_calc.c common.h

run: casegen ver1 ver2
# TODO: fill the remaining commands
        ./casegen $(CASE_NUM) $(INPUT_FILE)

# TIPS: casegen, instead of casegen.c , is one of the dependencies, why?
all: casegen # TODO: fill the remaining dependency

ver1: $(COMMON_FILE) # TODO: fill the remaining dependency
# TODO: fill the remaining commands

ver2: # TODO: fill the remaining dependency
# TODO: fill the remaining commands

casegen: casegen.c 
        gcc casegen.c -o casegen

clean:
# TODO: fill the clean command

# TODO: setup PHONY rules

其实不难，一点一点来就可以了！我们就按照题目要求的来！

casegen：编译生成输入生成程序 casegen；
这个不用我们写，他已经写好了
ver1: 使用共同依赖，以及依赖 calc1.c，编译生成程序 ver1；
共同依赖，实际上就是COMMON_FILE这一堆

1 2	ver1: $(COMMON_FILE) calc1.c # TODO: fill the remaining dependency gcc $(COMMON_FILE) calc1.c -o ver1

ver2: 使用共同依赖，以及依赖 calc2.c，编译生成程序 ver2；
ver2也同理

1 2	ver2:$(COMMON_FILE) calc2.c # TODO: fill the remaining dependency gcc $(COMMON_FILE) calc2.c -o ver2

all: 编译生成上述所有程序 casegen, ver1, ver2；
只需要把ver1, ver2, $(COMMON_FILE)也作为all的目标就可以了！
即all: casegen ver1 ver2 $(COMMON_FILE)
run: 先执行 casegen 获取输入，再分别执行 ver1, ver2 获取输出；

题目中提到

程序 casegen, ver1, ver2 的使用方法如下。有关输入参数可通过 makefile.inc 中的定义得到，并在 Makefile 中引用：

1
2
3

casegen <case_num> <input_file> 
ver1 <input_file> 
ver2 <input_file>

所以只要这样就阔以了

run: casegen ver1 ver2
        ./casegen $(CASE_NUM) $(INPUT_FILE)
        ./ver1 $(INPUT_FILE)
        ./ver2 $(INPUT_FILE)

clean: 清理编译好的可执行文件 casegen, ver1, ver2，以及运行过程中产生的所有后缀为 .txt 的临时文件。
只需要

1 2	clean: rm -f casegen ver1 ver2 *.txt

注意，如果不加-f，那么将要删除的文件不存在时，会直接报错结束。加上-f如果要删除的文件，则会忽略继续执行。

此外，你需要保证 run 为 Makefile 的默认规则，即执行命令 make 与执行 make run 效果等价。

那就把run放在第一个目标的位置就好了。
题目还要求run 和 clean是伪规则，所以我们要加上.PHONY:clean run这一行

AC版本如下

include makefile.inc
.PHONY:clean run
COMMON_FILE = main.c post_calc.c common.h

run: casegen ver1 ver2
        ./casegen $(CASE_NUM) $(INPUT_FILE)
        ./ver1 $(INPUT_FILE)
        ./ver2 $(INPUT_FILE)

# TIPS: casegen, instead of casegen.c , is one of the dependencies, why?
all: casegen ver1 ver2 $(COMMON_FILE)# TODO: fill the remaining dependency

ver1: $(COMMON_FILE) calc1.c # TODO: fill the remaining dependency
        gcc $(COMMON_FILE) calc1.c -o ver1

ver2:$(COMMON_FILE) calc2.c # TODO: fill the remaining dependency
        gcc $(COMMON_FILE) calc2.c -o ver2

casegen: casegen.c 
        gcc casegen.c -o casegen

clean:
        rm -f casegen ver1 ver2 *.txt

lab0 extra

题目给了个参考代码框架，长这样

#!/bin/bash

LOG_DIR="logs"
REPORT_DIR="reports"

# 如果缺少参数
if [ ]; then
    # 打印消息，立即退出
fi

# 获取日期参数
DATE=

# 构建文件路径
error_src=
access_src=
error_dst=
access_dst=
summary_dst=

# 查找包含 ERROR 的行
errors=$(grep TODO "$error_src")
if [ ]; then
    # 仅当结果非空时保存
fi

# 思考如何处理特殊字符
sed TODO "$access_src"

# 思考综合使用提示命令
awk TODO "$access_src" | TODO | TODO | TODO | TODO

那就一点一点填吧。。

如果 日期 未给出，则打印 analyze.sh: No date provided 到标准输出，并立即退出。如果 日期 给出，则按如下要求分析对应日期（保证存在）的日志。

如果缺少时间参数，也就是参数的个数是0的话，输出并且直接退出。
可以用$#来表示参数的个数，所以用下面这种方式就阔以
如果$# -eq 0，echo然后退出就可以

# 如果缺少参数
if [ $# -eq 0 ]; then
    echo "analyze.sh: No date provided"
    exit
fi

一定要注意if的用法，左括号右边和右括号左边一定要加上空格！

不缺少时间参数的话，那么就可以把$1赋值给DATE了

新建报告根目录 reports ，与日志根目录同级，报告均保存在以对应日期命名的子目录中。

新建所有目录的权限为 rwxrwxr-x ，所有普通文件的权限为 rw-rw-r--

构建文件路径，那就按照题目的要求来，大家可以根据题目对照来填写这一段，即

error_src="$LOG_DIR/$DATE/error.log"
access_src="$LOG_DIR/$DATE/access.log"
error_dst="$REPORT_DIR/$DATE/error.log"
access_dst="$REPORT_DIR/$DATE/access.log"
summary_dst="$REPORT_DIR/$DATE/summary.txt"

随后，我们要新建report下的几个目录，题目要求新建所有目录的权限为 rwxrwxr-x ，所有普通文件的权限为 rw-rw-r-- 。
rwxrwxr-x是二进制的775，rw-rw-r--是二进制的664。

1
2
3

mkdir -p "$REPORT_DIR/$DATE"
chmod 775 "$REPORT_DIR"
chmod 775 "$REPORT_DIR/$DATE"

在指定日期的错误日志中检查是否存在含有 ERROR 字样的记录，如果有则将这类记录筛选出来，按原顺序保存到相应报告子目录下的 error.log ，否则不要创建此文件。

题干给的模板是这样

# 查找包含 ERROR 的行
errors=$(grep TODO "$error_src")
if [ ]; then
    # 仅当结果非空时保存
fi

也就是说我们要在这个if语句里判断errors是否为空，那么怎么判断一个字符串是否为空呢？

没错！判断一个字符串为空的方法是-n，我们只需要通过if [ -n "$errors" ]就可以判断$errors到底是不是空。但是这提莫谁会啊（于是我的第1次上机就挂在这里。。

会判断一个字符串为空，接下来就很简单啦。
我们只需要把echo输出的内容覆盖到$error_dst，并且给这个新生成的文件设置一下权限就好啦。

if [ -n "$errors" ]; then
    echo "$errors" > "$error_dst"
    chmod 664 "$error_dst"
fi

这个地方，如果$error_dst不存在，就会自动创建这个文件之后，再重定向把$errors的内容输出到里面。

在指定日期的访问日志中将 /127.0.0.1 字样全部替换为 /localhost ，其它内容保持不变，
全文保存到相应报告子目录下的 access.log ，不要更改原文件。

这里用到的是sed 's/a/b/g'语法，但是要注意sed的转义问题，/需要用\来进行转义，.也需要用\来进行转义！

1 2	sed 's/\/127\.0\.0\.1/\/localhost/g' "$access_src" > "$access_dst" chmod 664 "$access_dst"

在指定日期的访问日志中统计每个 IP地址 的总请求次数，并将结果按访问次数从高到低排序，
保存到相应报告子目录下的 summary.txt ，访问次数相同时的排序不做要求，每行格式如下：

IP地址 总访问次数

我们的思路是，先用awk把每个访问日志的ip分割出来，随后用uniq -c来数每个ip出现的次数，然后用sort -nr对于这些ip出现的次数进行大小排序

不过这里要注意，uniq只能对相同的元素挨在一起的才能进行数数，如果两个相同的ip中间隔了一个别的ip，这里uniq是不能正常运作的。所以uniq前还要sort一下。

随后sort -nr的结果会是总访问次数 IP地址，但我们想要的输出是IP地址总访问次数，于是我们还需要用awk来转换一下输出顺序，再重定向到$summary_dst就可以了。别忘了设置一下权限。

1 2	awk '{print $1}' "$access_src" \| sort \| uniq -c \| sort -nr \| awk '{print $2, $1}' > "$summary_dst" chmod 664 "$summary_dst"

AC版本

#!/bin/bash

LOG_DIR="logs"
REPORT_DIR="reports"

# 如果缺少参数
if [ $# -eq 0 ]; then
    echo "analyze.sh: No date provided"
    exit 0
fi

# 获取日期参数
DATE=$1

# 构建文件路径
error_src="$LOG_DIR/$DATE/error.log"
access_src="$LOG_DIR/$DATE/access.log"
error_dst="$REPORT_DIR/$DATE/error.log"
access_dst="$REPORT_DIR/$DATE/access.log"
summary_dst="$REPORT_DIR/$DATE/summary.txt"

mkdir -p "$REPORT_DIR/$DATE"
chmod 775 "$REPORT_DIR"
chmod 775 "$REPORT_DIR/$DATE"

# 查找包含 ERROR 的行
errors=$(grep "ERROR" "$error_src")
if [ -n "$errors" ]; then
    echo "$errors" > "$error_dst"
    chmod 664 "$error_dst"
fi

# 思考如何处理特殊字符
sed 's/\/127\.0\.0\.1/\/localhost/g' "$access_src" > "$access_dst"
chmod 664 "$access_dst"

# 思考综合使用提示命令
awk '{print $1}' "$access_src" | sort | uniq -c | sort -nr | awk '{print $2, $1}' > "$summary_dst"
chmod 664 "$summary_dst"

lab1 exam

我们需要补全int readelf64(const void *binary, size_t size) 这个函数
中文注释给的很详细！我们一步一步来

第一步，设置 ELF64 文件头 ehdr

这里涉及一个类型的强制转换，我们要把binary转换成Elf64_Ehdr类型才能被ehdr正确读取
ehdr = (Elf64_Ehdr *)binary;

第二步，读取节头总数 section_count

节头数那就是Elf64_Ehdr结构体的e_shnum啦，也就是只需要
section_count = ehdr->e_shnum;

第三步，在下方完成节名称字符串表的节头 shstrShdr 与节名称字符串表的内容字符串 shstrtab 的获取。

这个地方看起来有点复杂？但是题干描述的很详细，题干说

那么如何找到节名称字符串表，又如何借此获取某一节的节名称呢？

注意，ELF 文件头中的 e_shstrndx 表示 节名称字符串表 对应节头在 节头表 中的下标。

由此，给出获取某一节 节名称 的过程：

根据 e_shoff 找到节头表（ Elf64_Shdr *sh_table = ((char *)binary + ehdr->e_shoff)）；
取出下标为 e_shstrndx 的那个节头（Elf64_Shdr *shstrShdr = &sh_table[ehdr->e_shstrndx]）；
通过该节头的 sh_offset（内容在文件中的偏移），找到 节名称字符串表 的 内容字符串 的位置，存到 char *shstrtab（请大家参考 1. 中 e_shoff 的用法，完成相关代码）；
对于某一节（若其对应节头为 shdr），其节名可由 char *sectionName = shstrtab + shdr->sh_name 得到。

shstrShdr和shstrtab的获取方式只需要照抄上面的第1,2,3条就可以了。
上面用到了数组，当然我们也可以用另外一种不用数组而直接对地址加减的方式（），如下

1
2
3

shstrShdr = (const Elf64_Shdr *)((const void *)sh_table + ehdr->e_shstrndx * ehdr->e_shentsize);
   shstrtab = (const void *)binary + shstrShdr->sh_offset;

你可能疑惑，为什么对指针的加减要强转成void *？这涉及到了C语言指针运算的一些知识。
例如，对一个int *a的指针来说，假如a = 200，a+1实际上并不等于201,而是204(&a[1])，因为一个int是4个字节。所以我们如果想直接对字节(即让a+1==201)运算，就需要先把指针转换成char *或者void *，这两种都可以。
这是C语言的一个坑，上机的时候一定要注意！

第四步，判断当前节名称是否为 “.symtab”，如果是则matchSymtab为非0，否则为0

嗯就是简单的C语言，还记得怎么判断两个字符串是否相等吗？

if(strcmp(sectionName, ".symtab") == 0){
	matchSymtab = 1;
}else{
	matchSymtab = 0;
}

第五步，记录符号表.symtab的节头在节头表中的索引(下标)

if (matchSymtab) {
	// 记录符号表.symtab的节头在节头表中的索引(下标)
	// ----- Lab1-Exam: Your code here. (5/5) -----
	symtabIndex = i;
}

然后再按照注释要求，把printf的注释取消就好了！

AC代码如下

int readelf64(const void *binary, size_t size) {
    const Elf64_Ehdr *ehdr = NULL;
    // 设置 ELF64 文件头 ehdr
    // ----- Lab1-Exam: Your code here. (1/5) -----
    ehdr = (Elf64_Ehdr *)binary;
    // 检查文件头 ehdr，判断文件是否为 ELF64 文件
    if (!is_elf_format(ehdr, size)) {
        fputs("not an elf64 file\n", stderr);
        return 0;
    }

    unsigned int section_count;
    
    // 读取节头总数 section_count
    // ----- Lab1-Exam: Your code here. (2/5) -----
	section_count = ehdr->e_shnum;
	
    const Elf64_Shdr *sh_table;  // 节头表
    const Elf64_Shdr *shstrShdr; // 节名称字符串表的节头
    const char *shstrtab;        // 节名称字符串表的内容字符串

    // 获取节头表地址 sh_table
    sh_table = (const Elf64_Shdr *)((char *)binary + ehdr->e_shoff);

    // 【提示：请大家仔细阅读题面，理解 相关知识说明 中 C. 节名称字符串表 的知识点。】
    // 在下方完成 节名称字符串表的节头 shstrShdr 与 节名称字符串表的内容字符串 shstrtab 的获取。
    // ----- Lab1-Exam: Your code here. (3/5) -----
    shstrShdr = (const Elf64_Shdr *)((const char *)sh_table + ehdr->e_shstrndx * ehdr->e_shentsize);
    shstrtab = (const char *)binary + shstrShdr->sh_offset;
    const char *sectionName; // 提取节名称用的临时变量
    int symtabIndex = -1;    // 记录符号表.symtab的节头在节头表中的索引(下标)
    unsigned int i;
    printf("section_count=%u\n", section_count);

    // 输出每个节信息，并在遇到符号表.symtab时记录下标
    for (i = 0; i < section_count; i++) {
        sectionName = shstrtab + sh_table[i].sh_name;

        int matchSymtab;
        // 判断当前节名称是否为 ".symtab"，如果是则matchSymtab为非0，否则为0
        // ----- Lab1-Exam: Your code here. (4/5) -----
        if(strcmp(sectionName, ".symtab") == 0){
                matchSymtab = 1;
        }else{
                matchSymtab = 0;
        }
        if (matchSymtab) {
            // 记录符号表.symtab的节头在节头表中的索引(下标)
            // ----- Lab1-Exam: Your code here. (5/5) -----
            symtabIndex = i;
        }

        // 提示：请在【至少完成 Lab1-Exam: Your code here. (3/5)】后，
        // 取消下方 `printf(...);` 两行的注释，以输出每个节的信息（节名称、sh_offset、sh_size）；
        // 提前取消注释会访问非法内存地址而导致程序崩溃。
        printf("[%d]\tname=\"%s\"\toffset=0x%lx\tsize=%lu\n", i, sectionName,
             (unsigned long)sh_table[i].sh_offset, (unsigned long)sh_table[i].sh_size);
    }

    if (symtabIndex < 0) {
        fputs("No .symtab found\n", stderr);
        return 0;
    }

    printf("symtab_index=%d\n", symtabIndex);

    return 0;
}

lab1 extra

本次extra应该是最简单的一次？原因是这次的注释写的非常详细，补代码只需要逐句翻译就好了！

任务1：添加头文件声明，直接复制就行，一行代码都不用自己写，这里就不展开了
任务2：实现顶层包装函数

首先我们要实现的是scank函数，这个函数可以参考printk的方式来实现

int scank(const char *fmt, ...) {
    /* ---------------------------------- */
    /* Lab 1-extra: Your code here. (1/4)      */
    /* 提示：
       1. 仿照 printk 的实现，使用 va_list 处理可变参数。
       2. 调用 vscanfmt（传入刚写好的 inputk 回调函数）。
       3. 本函数的返回值 ret 应为 vscanfmt 的执行结果。
    */
    /* ---------------------------------- */
	va_list ap;
	va_start(ap, fmt);
	int ret = vscanfmt(inputk, NULL, fmt, ap);
	va_end(ap);
	return ret;
}

任务3：完成核心解析状态机
我们有两个辅助函数，一个是ensure_char(scan_callback_t in, void *data, char *ch, int *ch_valid)，用来确保缓冲区里有字符
一个是skip_whitespace(scan_callback_t in, void *data, char *ch, int *ch_valid)，用来跳过签到空白符

接下来，我们要做的就是翻译注释(不是我不想解释，真的是注释写的太详细了)

void scan_c(scan_callback_t in, void *data, char *ch, int *ch_valid, char *cp) {
    /* ---------------------------------- */
    /* Lab 1-extra: Your code here. (2/4)  */
    /* 提示：
       1. 使用辅助函数确保缓冲区里有字符（注意：%c 绝不能跳过空白符！）
       2. 将读取到的字符存入 cp 指向的内存。
       3. 核心：因为该字符已被 %c 实体吃掉，必须将 缓存标志位 置为无效(值为0)。
    */
    /* ---------------------------------- */
	ensure_char(in, data, ch, ch_valid);
	*cp = *ch;
	*ch_valid = 0;
}


void scan_s(scan_callback_t in, void *data, char *ch, int *ch_valid, char *cp) {
        
    /* ---------------------------------- */
    /* Lab 1-extra: Your code here. (3/4)  */
    /* 提示：
       1. 使用辅助函数跳过所有的前导空白符。
       2. 连续读取非空白字符并存入 cp(可以在循环内部使用 *cp++ = *ch 进行赋值)。
       3. 遇到空白符或 '\0' 时停止读取。
       4. 别忘了在字符串末尾添加 '\0' 封口。
       5. 停下时：ch 里必须正好握着导致停止的“空白符”，且保持 缓存标志位 置为有效(值为1)。
    */
    /* ---------------------------------- */
	skip_whitespace(in, data, ch, ch_valid);

	while(!(*ch == ' ' || *ch == '\t' || *ch == '\n' || *ch == '\r' || *ch == '\0')){
		*cp++ = *ch;
		in(data, ch, 1);
	}
	*cp = '\0';
	*ch_valid = 1;
}

void scan_u(scan_callback_t in, void *data, char *ch, int *ch_valid, int *ip) {
    
    /* ---------------------------------- */
    /* Lab 1-extra: Your code here. (4/4)  */
    /* 提示：
       1. 定义变量用于累加数字计算结果。
       2. 使用辅助函数跳过所有的前导空白符。
       3. 兼容可选的前导 '+' 号（至多1个）（如果有，调用 in() 越过它）。
       4. 如果遇到的第一个非空白字符就不是数字或 `+`，直接赋值为 `0` 并结束。
       5. 连续读取数字字符（'0'-'9'），并 计算 十进制数值。
       6. 遇到非数字字符时停止读取，并将结果存入 ip。
       7. 停下时：ch 里必须正好握着导致停止的“非数字字符”，且保持 缓存标志位 置为有效(值为1)。
    */
    /* ---------------------------------- */
	skip_whitespace(in, data, ch, ch_valid);
        int m = 0;

        if(*ch == '+'){
                in(data, ch, 1);
        }
        while(*ch >= '0' && *ch <= '9'){
                m = m * 10 + *ch - '0';
                in(data, ch, 1);
        }
        *ip = m;
        *ch_valid = 1;
}

BTW，++的优先级比*的优先级更高哦

lab2 exam

这次的exam一反常态，竟然考起了怎么写链表宏（成C语言上机了。

我们需要实现一个新的 C 语言宏 LIST_INSERT_AT，将指定的元素插入到给定链表的第 index 个位置

首先这里先复制一下提示的第3条，也就是C的宏的规范

注意 C 语言宏的安全编程规范：
- 宏的外部应使用 do { ... } while (0) 包裹以保证语法的安全性。
- 宏内部使用传入的参数时，建议加上括号（如 (index)），防止表达式优先级导致的逻辑错误。
- 宏内部声明临时变量时（如计数器变量或迭代指针），建议使用带有下划线前缀的命名（如 _cnt, _var），以防止与外部作用域的变量名发生冲突。

这里的第三条很好理解，毕竟不能让宏的局部变量和外部变量冲突
至于第一条和第二条，这些规范其实很有意思也很有意义，感兴趣的同学可以去AI一下，这里就不赘述了

代码的话，这里按照提示的第2条来写就可以了

可以组合使用已有的链表宏。例如：
- 当 index == 0 时，可以直接调用 LIST_INSERT_HEAD。
- 当 index > 0 时，可以使用 LIST_FOREACH 宏配合自定义的计数器遍历链表，找到对应的节点后使用 LIST_INSERT_AFTER 插入。

一个需要注意的点是，LIST_FOREACH(var, head, field)里的var变量是需要提前声明的

#define LIST_INSERT_AT(type, head, elm, field, index)\
	do{\
		if(index == 0){\
			LIST_INSERT_HEAD(head, elm, field);     \
		}else{\
			struct type* var;\
			int _i = 1; \
			\\_i表示遍历到了第几个元素\
			LIST_FOREACH(var, head, field){\
				if(_i == index){\
					LIST_INSERT_AFTER(var, elm, field);\
					break;  \
				}\
				if(LIST_NEXT(var, field) == NULL){\
					LIST_INSERT_AFTER(var, elm, field);\
					break; \
				}\
				_i++;\
			}\
		} \
	}while(0) \

lab2 extra

最惨的一次上机，AC的人只有个位数
这次上机考的是自映射

实际上，老师在上机前一定讲过自映射，并且强调过期中考试也一定会考自映射。但是，讲了我就一定会吗？？？

题干描述了半天，相信大多人都读不懂！我读了一个半小时也没读懂！
这里可以阅读一下我的另一篇博客（

题干说了那么多，我们需要知道的最关键最关键的是，在连续的以base开始的4MB地址空间里，页目录就是首地址是base >> PDX(base)的那张页！并且页目录的第一项存的是4MB里的第一个页的首地址，第二项存的是4MB里第二个页的首地址……即线性映射！

读题理解了这个点（or上课听课的话），最起码能实现两个查询函数，轻松拿下30分。

pte_va() 函数的功能为：给定自映射虚拟地址空间的首地址 base ，计算使用自映射访问第 pdeno 张页表的第 pteno 个页表项时，需要使用的虚拟地址。

pde_va() 函数的功能为：给定自映射虚拟地址空间的首地址 base ，计算使用自映射访问页目录中的第 pdeno 个页目录项时，需要使用的虚拟地址。

u_long pte_va(u_long base, u_int pdeno, u_int pteno) {
        /* Your Code Here (2/4) */
        return base + pdeno << 12 + pteno << 2;

}

u_long pde_va(u_long base, u_int pdeno) {
        /* Your Code Here (3/4) */
        return base + PDX(base) << 12 + pdeno << 2;
}

然后是自映射的建立

create_self_map() 函数的功能为：给定页目录首地址 pgdir 和 asid ，将所有页表自映射至 [base, base + 1024 * PAGE_SIZE) 的连续 4MB 虚拟地址空间。
题目给的实现流程可以翻译成这样。

首先我们要遍历每一个以base为起始地址的4MB地址空间的每一个页，用page_lookup检查其是否已经与物理页面建立了映射，如果建立了映射，那就用page_romove接触映射，并且count++。
随后，将所有页表自映射到这个4MB的地址区域，实际就是把这个页目录的用于自映射的那一个页表项来指向自己，并且设立权限为PTE_V。
随后返回count。

int create_self_map(Pde *pgdir, u_int asid, u_long base) {
	int count = 0;
	/* Your Code Here (1/4) */
	u_long va;
	u_int self_index = PDX(base);
	for(va = base; va < base + 1024 * PAGE_SIZE; va += PAGE_SIZE){
		if(page_lookup(pgdir, va, NULL) != NULL){
			page_remove(pgdir, asid, va);
			count++;
		}
	}
	pgdir[self_index] = PADDR(pgdir) | PTE_V;
	return count;
}

remove_all_self_map() 函数的功能为：给定页目录首地址 pgdir 和 asid ，解除当前已经建立的所有自映射。

remove_all_self_map()函数没有给base这个参数，所以我们需要自己找。
参考流程可以翻译成这样：

首先要页目录pgdir的每一个页表项，如果这个页表项是用来自映射的，即有PTE_ADDR(pgdir[i]) == pgdir_pa，我们就用pgdir[i] = 0来清空表项，随后count++。
那么我们就可以通过上一步得到的页表项找到base，我们知道用于实现自映射的页表项是base + PDX(base)，若我们知道了第i个页表项是用于自映射的，那么只需要i左移22位，得到的就是base的值了！
随后，我们遍历以base为起始地址的4MB地址空间的每一个页，清空其在TLB中的缓存
最后返回count

int remove_all_self_map(Pde *pgdir, u_int asid) {
	int count = 0;
	/* Your Code Here (4/4) */
	u_int i;
	u_long va;
	u_long base;
	u_long pgdir_pa = PADDR(pgdir);
	for(i = 0; i < 1024; i++){
		if((pgdir[i] & PTE_V) && PTE_ADDR(pgdir[i]) == pgdir_pa){
			base = i << PDSHIFT;
			pgdir[i] = 0;
			count++;

			for(va = base; va < base + 1024 * PAGE_SIZE; va += PAGE_SIZE){
					tlb_invalidate(asid, va);
			}
		}
	}
	return count;
}

lab3 exam

lab3-exam和之前一样考的是新增调度算法，还是有点难度的

在 include/env.h 中添加声明，复制粘贴

在 kern/env.c 中添加 env_srtf_sched_list 的定义，并在 env_init 函数中初始化 env_srtf_sched_list。

在kern/env.c添加
struct Env_srtf_sched_list env_srtf_sched_list; // SRTF 调度队列
然后再env_init()里加上
LIST_INIT(&env_srtf_sched_list);

在 include/env.h 的 Env 结构体中添加字段，也是复制粘贴

在 kern/env.c 中仿照 env_create 实现 env_create_srtf 函数

只需要在env_create的基础上，新加两个新增的字段的赋值就可以了

struct Env *env_create_srtf(const void *binary, size_t size, int runtime) {
	struct Env *e ;
	// 分配 env 并初始化
	try(env_alloc(&e, 0))
	// ...
	
	e->env_status = ENV_RUNNABLE ;
	// 处理新增的字段
	e->env_total_runtime = runtime ;
	e->env_runtime_left = runtime ;
	
	load_icode(e, binary, size);
	LIST_INSERT_HEAD(&env_srtf_sched_list, e, env_srtf_sched_link);
	
	return e;
}

修改 kern/sched.c 中的 schedule 函数，实现 SRTF 调度算法。

我们按照给的注释来

如果SRTF调度队列中存在尚未运行完所需时间片的进程，则遍历 SRTF 调度队列，选取剩余时间片最少的进程进行调度（如果有多个剩余时间片相同，则选取 env_id 最小的进程）。

struct Env *env, *min_env = NULL;
if(!LIST_EMPTY(&env_srtf_sched_list)){
	LIST_FOREACH(env, &env_srtf_sched_list, env_srtf_sched_link){
		if(min_env == NULL || (min_env != NULL && ( (env->env_runtime_left < min_env->env_runtime_left) || (env->env_runtime_left == min_env->env_runtime_left && env->env_id < min_env->env_id)))){
			if(env->env_runtime_left > 0 && env->env_status == ENV_RUNNABLE)
				min_env = env;
		}
	}
}

如果找到这样的进程，将其剩余时间片减 1，并调用 env_run 调度该进程。
如果此进程剩余时间片为0，则将其从 SRTF 调度队列中移除。

注意这个地方要先判断是否剩余时间片为0并将其移除链表，再执行env_run()，因为执行 env_run() 之后不会再返回到当前这次 schedule() 调用后续代码的！

if(min_env != NULL){
	min_env->env_runtime_left--;
	if(min_env->env_runtime_left <= 0)
		LIST_REMOVE(min_env, env_srtf_sched_link);
	env_run(min_env);
}

如果 SRTF 调度队列为空或所有进程的剩余时间片为 0，则使用 RR 调度算法调度 RR 调度队列中的进程

struct Env *e = curenv; // 请根据提示修改这行代码
注意题干是这个意思：SRTF 进程会中途抢占 RR 进程，但 SRTF 结束后，RR 调度必须从被抢占前的那个 RR 进程继续，而不是根据当前 curenv 重新判断。所以这个地方我们要把e设置成静态变量，就可以让之前被抢占的的进程继续执行了！
即
static struct Env *e = NULL;

下面是AC代码

void schedule(int yield) {
	struct Env *env, *min_env = NULL;
	if(!LIST_EMPTY(&env_srtf_sched_list)){
		LIST_FOREACH(env, &env_srtf_sched_list, env_srtf_sched_link){
			if(min_env == NULL || (min_env != NULL && ( (env->env_runtime_left < min_env->env_runtime_left) || (env->env_runtime_left == min_env->env_runtime_left && env->env_id < min_env->env_id)))){
				if(env->env_runtime_left > 0 && env->env_status == ENV_RUNNABLE)
					min_env = env;
			}
		}
	}
	if(min_env != NULL){
		min_env->env_runtime_left--;

		if(min_env->env_runtime_left <= 0)
		LIST_REMOVE( min_env, env_srtf_sched_link);
		env_run(min_env);

	}
        
	static int count = 0; // remaining time slices of current env
	static struct Env *e = NULL;
	count--;
	if(yield || count <= 0 || e == NULL || e->env_status != ENV_RUNNABLE){
		if(e != NULL && e->env_status == ENV_RUNNABLE){
				TAILQ_REMOVE(&env_sched_list, e, env_sched_link);
				TAILQ_INSERT_TAIL(&env_sched_list, e, env_sched_link);
		}
		if(TAILQ_FIRST(&env_sched_list) == NULL){
			panic("schedule: no runnable envs\n");
		}
		e = TAILQ_FIRST(&env_sched_list);
		count = e->env_pri;
	}
	env_run(e);
}

lab3 extra

这次extra也和往年一样是新加一个异常处理，难点主要在于地址的转换

为什么要有地址的转换？为什么不能直接直接动cp0_epc储存的值？

原因：
EPC 是用户程序代码段的虚拟地址。直接访问它会走 TLB 和页表权限检查，首先我们知道，.text可读不可写，写 .text 段会因为没有 PTE_D 而触发写权限异常，而且如果该地址当前没有 TLB 映射，还可能在异常处理过程中再次触发 TLB 缺失异常。

故我们需要将其通过页表转换为物理地址，再用 KADDR 转成 kseg0 内核直映地址，就可以绕开用户态 TLB 映射和写权限限制，直接访问并修改对应的物理内存。

所以我们要先完成int *va2instrAddr()，来实现kuseg段地址到kseg0段地址的转换。

int *va2instrAddr(unsigned long va) {  、
	/* 1. 查询 curenv 的页表获取虚拟地址对应页表项; */
	Pte *pte;  
	struct Page *pp;  
	pp = page_lookup(curenv->env_pgdir, va, &pte);  
	/* 2. 通过页表项和虚拟地址得到物理地址; */
	unsigned long pa = PTE_ADDR(*pte) | (va & 0xfff);  
	/* 3. 将该物理地址转化为 kseg0 区间中虚拟地址; */
	return (int *)KADDR(pa);  
}

完成了这最重要也是最难的一步，我们就可以轻松实现后面的内容了。

获取 break 指令及其 code

只需要取出tf->cp0_epc并将其转化成kseg0段的地址就可以了，随后取出其的25-6位

1
2
3

u_long va = tf->cp0_epc;
u_int *instr = (u_int *)va2instrAddr(va);
u_int code = (*instr >> 6) & 0xfffff;

如果是用户断点，只需要让tf->cp0_epc指向下一条指令，并加上题目要求的输出就可以了

case 0x0:
	// 用户断点：跳过 break 指令
	tf->cp0_epc += 4;
	printk("Break skip!\n");
	break;

如果是数组越界，我们需要先让epc指向下条指令，并且取出其对应的指令码。

case 0x6: 
	// 处理索引越界
	tf->cp0_epc += 4;
	instr = (u_int *)va2instrAddr(tf->cp0_epc);

这下instr就是lw/sw指令对应的指令码了
随后我们在4号寄存器（即$a0）中取出数组长度，再取出低16位的立即数，并将其右移两位取出索引，这里可以直接用16位的short来存
GCC的>>在作用在负数上时是算数右移（即保留符号位），所以大家可以放心移

1
2
3

int len = tf->regs[4];
short imm = (short)(*instr & 0xffff);
int index = imm >> 2;

如果索引是负数，则设置成0
如果索引是正数并且大于数组长度，则使索引为数组长度减1，随后将新索引写入到指令码里，并且给出对应输出

if (index < 0) {
		index = 0;
	} else if (index >= len) {
		index = len - 1;
	}

	short new_imm = (short)(index << 2);
	*instr = (*instr & 0xffff0000) | ((u_short)new_imm);
	printk("Out of bounds handled, new imm is : %04x!\n",
		   (u_short)new_imm);

lw/sw部分完整代码

case 0x6: 
	tf->cp0_epc += 4;
	instr = (u_int *)va2instrAddr(tf->cp0_epc);
	int len = tf->regs[4];
	short imm = (short)(*instr & 0xffff);
	int index = imm >> 2;

	if (index < 0) {
			index = 0;
	} else if (index >= len) {
			index = len - 1;
	}

	short new_imm = (short)(index << 2);
	*instr = (*instr & 0xffff0000) | ((u_short)new_imm);

	printk("Out of bounds handled, new imm is : %04x!\n",
		   (u_short)new_imm);
	break;

如果是除数为零，我们只要把除数（即rt寄存器）的值改成2就可以了

case 0x7: 
	tf->cp0_epc += 4;
	instr = (u_int *)va2instrAddr(tf->cp0_epc);
	int rt = (*instr >> 16) & 0x1f;
	if (tf->regs[rt] == 0) {
			tf->regs[rt] = 2;
	}
	printk("Divide by zero handled!\n");
	break;

AC代码如下

void do_bp(struct Trapframe *tf) {
	u_long va = tf->cp0_epc;
	u_int *instr = (u_int *)va2instrAddr(va);
	u_int code = (*instr >> 6) & 0xfffff;

	switch (code) {
	case 0x0: 
		tf->cp0_epc += 4;
		printk("Break skip!\n");
		break;
	
	case 0x6: 
		tf->cp0_epc += 4;
		instr = (u_int *)va2instrAddr(tf->cp0_epc);
		int len = tf->regs[4];
		short imm = (short)(*instr & 0xffff);

		int index = imm >> 2;

		if (index < 0) {
			index = 0;
		} else if (index >= len) {
			index = len - 1;
		}

		short new_imm = (short)(index << 2);
		*instr = (*instr & 0xffff0000) | ((u_short)new_imm);

		printk("Out of bounds handled, new imm is : %04x!\n",
			   (u_short)new_imm);
		break;
	

	case 0x7: 
		tf->cp0_epc += 4;

		instr = (u_int *)va2instrAddr(tf->cp0_epc);
		int rt = (*instr >> 16) & 0x1f;

		if (tf->regs[rt] == 0) {
			tf->regs[rt] = 2;
		}

		printk("Divide by zero handled!\n");
		break;
	}

	return;
}

lab4 exam

和往年一样，是新加一个系统调用，但是个人感觉略比去年的难一些，因为涉及到了对页表的一点操作

只需要复制粘贴的地方这里就不赘述了，这里只讲kern/syscall_all.c文件怎么编写

我们需要写一个辅助函数ref(x)

若 x 不属于当前进程的合法用户地址范围，则 ref(x) = -E_INVAL；
这里不能直接用is_illegal_va()函数，因为注意事项中提到：

判断地址是否合法时，可以结合 MOS 的地址空间布局来考虑，我们这里将小于 ULIM 的地址视为合法用户地址范围，其中 ULIM 是用户空间与内核空间的边界；因此，本题中合法用户地址的上界应当取为 ULIM；

所以写成这样
if(x >= ULIM) return -E_INVAL;
就可以了

若 x 属于合法用户地址范围，但其所在页在当前进程地址空间中不存在有效映射，则 ref(x) = 0；
若 x 对应页面已映射，则 ref(x) 等于该物理页的引用计数 pp_ref。
这个地方需要用到lab2的知识了（，我们可以用page_lookup函数来找地址x处是否存在有效映射，然后返回x所在页的page的pp_ref就可以了

struct Page *pp;
	pp = page_lookup(curenv->env_pgdir, x, NULL);
	if(pp == NULL) return 0;
	return pp->pp_ref;
}

系统调用sys_trace_ref2的返回值为ref(a) + 2 * ref(b)，用上面的辅助函数就很容易实现了
AC代码如下

int ref(u_int x){
	if(x >= ULIM) return -E_INVAL;
	struct Page *pp;
	pp = page_lookup(curenv->env_pgdir, x, NULL);
	if(pp == NULL) return 0;
	return pp->pp_ref;
}
int sys_trace_ref2(u_int a, u_int b) { 
	return ref(a) + 2 * ref(b);
}

lab4 extra

嗯我本以为lab2 extra已经够逆天。。没想到还有高手
实话说个人感觉这题难度应该比lab2 extra低，因为实际上要实现的每一步注释都写的很清楚。这题很容易拿到部分分，并且如果对页表操作熟练也不难
就是题干太太太太太太太提莫长了，做不完（。

只需要复制粘贴的地方这里就不赘述了。。

我们需要编写代码的第一处为

在初始化 Env 结构体时，初始化本题目所需的结构体字段，注意需要导入 dirtyqueue.h 头文件。（kern/env.c，env_alloc函数）

我们需要在kern/env.c中初始化log_enabled，log_queue，log_entry字段

log_enabled记录是否启用脏页记录，log_entry用户态脏页处理代码的地址，这两个直接初始化成0就可以了
log_queue我们需要用dirty_init函数来初始化一下，注意ditry_init函数传入的参数是struct DirtyPageQueue *queue，所以我们实际要传入的是队列的地址。

int env_alloc(struct Env **new, u_int parent_id) {
  ...
  // Lab4-Extra: Your code here. (1 / 19)
  // 1. 初始化 log_enabled 字段
  // 2. 初始化 log_queue 字段
  // HINT: 你可以使用 `dirty_init` 函数
  // 3. 初始化 log_entry 字段
	e->log_enabled = 0;
	dirty_init(&e->log_queue);
	e->log_entry = 0;
}

接下来的内容我们要将系统调用约定和注释反复切换来看
9. 在 kern/syscall_all.c 中，实现 sys_start_dirty_log 系统调用：

启动脏页追踪，将 [va, va + size) 范围内的所有已映射的可写页面加入脏页追踪，取消设置 PTE_D 标志，设置 PTE_LOG 标志，刷新 TLB，并返回设置了 PTE_LOG 标志的页面的数量。

要求 va、size 是 PAGE_SIZE 的整数倍，若不是，返回 -E_INVAL

// 1. 检查 `va`、`size` 是否是 `PAGE_SIZE` 的整数倍
// Lab4-Extra: Your code here. (2 / 19)
if(va % PAGE_SIZE != 0 || size % PAGE_SIZE != 0){
        return -E_INVAL;
}

要求 [va, va + size) 范围位于合法的用户态地址范围内（[UTEMP, UTOP)），否则返回 -E_INVAL。

// 2. 检查虚拟地址范围的合法性
   // HINT: 你可以使用 `is_illegal_va_range` 函数
   // Lab4-Extra: Your code here. (3 / 19)
   if(is_illegal_va_range(va, size)){
           return -E_INVAL;
   }

要求当前该用户进程并未启动脏页追踪（log_enabled == 0），否则返回 -E_DIRTY_BUSY。

// 3. 检查是否已经启动脏页记录
   // HINT: 可以使用 `curenv` 访问当前进程的进程控制块
   // Lab4-Extra: Your code here. (4 / 19)
   if(curenv->log_enabled != 0){
           return -E_DIRTY_BUSY;
   }

若成功执行，返回设置了 PTE_LOG 标志的页面的数量。

1
2
3

// 4. 标记启动脏页记录
   // Lab4-Extra: Your code here. (5 / 19)
curenv->log_enabled = 1;

上面的一些都比较机械，题干说什么干什么就行了。
而下面这一块又迎来了我们lab2的知识

注释可以翻译成如下：首先，遍历页表项，我们需要遍历给定范围的每一个页，用page_lookup()函数找出它所在页目录的页表项，然后，若页表项有效且可写，则取出PTE_D，加上PTE_LOG,随后log_page_count++并且使用tlb_invalidate将TLB中的旧映射无效化。

// 5. 遍历 [va, va + size) 范围内的页表项若映射有效且可写，则去除可写标记，加上追踪标记
// 不要忘记更新 `log_page_count`！
// 不要忘记维护 TLB：在更新页表项后，需要使用 `tlb_invalidate` 函数将 TLB 中的旧映射无效化
// Lab4-Extra: Your code here. (6 / 19)
for(u_long v = va; v < va + size; v += PAGE_SIZE){
	Pte *pte;
	struct Page *pp;
	pp = page_lookup(curenv->env_pgdir, v, &pte);
	if(pp == NULL) continue;
	if((*pte & PTE_V) && (*pte & PTE_D)){
		*pte = *pte & (~PTE_D);
		*pte |= PTE_LOG;
		log_page_count++;
		tlb_invalidate(curenv->env_asid, v);
	}
}

sys_start_dirty_log完整代码如下

int sys_start_dirty_log(u_long va, u_long size) {
    // 1. 检查 `va`、`size` 是否是 `PAGE_SIZE` 的整数倍
    // Lab4-Extra: Your code here. (2 / 19)
    if(va % PAGE_SIZE != 0 || size % PAGE_SIZE != 0){
            return -E_INVAL;
    }
    // 2. 检查虚拟地址范围的合法性
    // HINT: 你可以使用 `is_illegal_va_range` 函数
    // Lab4-Extra: Your code here. (3 / 19)
    if(is_illegal_va_range(va, size)){
            return -E_INVAL;
    }
    // 3. 检查是否已经启动脏页记录
    // HINT: 可以使用 `curenv` 访问当前进程的进程控制块
    // Lab4-Extra: Your code here. (4 / 19)
    if(curenv->log_enabled != 0){
            return -E_DIRTY_BUSY;
    }
    // 4. 标记启动脏页记录
    // Lab4-Extra: Your code here. (5 / 19)
        curenv->log_enabled = 1;
    // 记录设置了 `PTE_LOG` 标志的页面的数量
    int log_page_count = 0;

	// 5. 遍历 [va, va + size) 范围内的页表项���若映射有效且可写，则去除可写标记，加上追踪标记
	// 不要忘记更新 `log_page_count`！
	// 不要忘记维护 TLB：在更新页表项后，需要使用 `tlb_invalidate` 函数将 TLB 中的旧映射无效化
	// Lab4-Extra: Your code here. (6 / 19)

	for(u_long v = va; v < va + size; v += PAGE_SIZE){
		Pte *pte;
		struct Page *pp;
		pp = page_lookup(curenv->env_pgdir, v, &pte);
		if((*pte & PTE_V) && (*pte & PTE_D)){
				*pte = *pte & (~PTE_D);
				*pte |= PTE_LOG;
				log_page_count++;
				tlb_invalidate(curenv->env_asid, v);
		}
	}
    return log_page_count;
}

接下来是int sys_set_dirty_log_entry(u_long entry)函数

设置用户态脏页处理函数的入口点。无论当前是否启动了脏页都可以设置。若传入 0，表示取消设置。

这句话其实有点歧义，实际上这句话的意思是如果输入的entry，就把curenv->log_entry设置成0（不知道为啥。注意设置成功要返回0，函数的参数entry是0，也表示设置成功

if(entry == 0){
	curenv->log_entry = 0;
	return 0;
   }

若传入的参数不是 0，则要求其必须位于合法的用户态地址范围内（[UTEMP, UTOP)），否则返回 -E_INVAL。

这个同上个函数，不多赘述了

// 1. 判断 `entry` 对应的虚拟地址是否合法，判断 `entry` 是否为 `0` （表示取消设置）
// HINT: 你可以使用 `is_illegal_va` 函数
if(is_illegal_va(entry)){
	return -E_INVAL;
}

随后设置进程控制块的入口点，再返回0，表示设置成功

// 2. 在进程控制块中设置用户态脏页处理函数的入口点
   // HINT: 可以使用 `curenv` 访问当前进程的进程控制块
   // Lab4-Extra: Your code here. (8 / 19)
curenv->log_entry = entry;
   return 0;

该函数完整代码如下

int sys_set_dirty_log_entry(u_long entry) {
    // 1. 判断 `entry` 对应的虚拟地址是否合法，判断 `entry` 是否为 `0` （表示取消设置）
    // HINT: 你可以使用 `is_illegal_va` 函数
    if(entry == 0){
		curenv->log_entry = 0;
		return 0;
    }
    // Lab4-Extra: Your code here. (7 / 19)
	if(is_illegal_va(entry)){
		return -E_INVAL;
	}
    // 2. 在进程控制块中设置用户态脏页处理函数的入口点
    // HINT: 可以使用 `curenv` 访问当前进程的进程控制块
    // Lab4-Extra: Your code here. (8 / 19)
	curenv->log_entry = entry;
    return 0;
}

接下来是int sys_stop_dirty_log()

要求当前该用户进程已经启动脏页追踪（log_enabled == 1），否则返回 -E_DIRTY_OFF。

// 1. 检查是否已经启动脏页记录
   // HINT: 可以使用 `curenv` 访问当前进程的进程控制块
   // Lab4-Extra: Your code here. (9 / 19)
if(curenv->log_enabled != 1){
		return -E_DIRTY_OFF;
}

停止脏页追踪，停止追踪后，对应的追踪页应当能被正常写入，且不再产生脏页记录。

1
2
3

// 2. 标记停止脏页记录
   // Lab4-Extra: Your code here. (10 / 19)
curenv->log_enabled = 0;

需要遍历用户进程的地址空间（[UTEMP, UTOP)），对于已映射的页面，若其有 PTE_LOG 标志，则去除该标志，重新设置 PTE_D 标志，刷新 TLB，并返回取消设置 PTE_LOG 标志的页面的数量。不修改已经设置的用户态脏页处理函数的入口点。

这部分和sys_start_dirty_log是类似的，只需要把循环的上下界改一下，并且改一下标志位~这里就不多赘述了。

// 3. 遍历进程的页表项（`[UTEMP, UTOP)`），若映射有效且已标记为追踪页，则去除追踪标记，加上可写标记
   // 不要忘记更新 `log_page_count`！
   // 不要忘记维护 TLB：在更新页表项后，需要使用 `tlb_invalidate` 函数将 TLB 中的旧映射无效化
   // Lab4-Extra: Your code here. (11 / 19)
for(u_long va = UTEMP; va < UTOP; va += PAGE_SIZE){
	Pte *pte;
	struct Page *pp;
	pp = page_lookup(curenv->env_pgdir, va, &pte);
	if(pp == NULL) continue;
	if(*pte  & PTE_LOG){
		*pte = *pte & (~PTE_LOG);
		*pte |= PTE_D;
		log_page_count++;
		tlb_invalidate(curenv->env_asid, va);
	}
}

完整函数如下：

int sys_stop_dirty_log() {
    // 1. 检查是否已经启动脏页记录
    // HINT: 可以使用 `curenv` 访问当前进程的进程控制块
    // Lab4-Extra: Your code here. (9 / 19)
	if(curenv->log_enabled != 1){
			return -E_DIRTY_OFF;
	}
    // 2. 标记停止脏页记录
    // Lab4-Extra: Your code here. (10 / 19)
	curenv->log_enabled = 0;
    // 记录取消设置 `PTE_LOG` 标志的页面的数量
    int log_page_count = 0;

    // 3. 遍历进程的页表项（`[UTEMP, UTOP)`），若映射有效且已标记为追踪页，则去除追踪标记，加上可写标记
    // 不要忘记更新 `log_page_count`！
    // 不要忘记维护 TLB：在更新页表项后，需要使用 `tlb_invalidate` 函数将 TLB 中的旧映射无效化
    // Lab4-Extra: Your code here. (11 / 19)
	for(u_long va = UTEMP; va < UTOP; va += PAGE_SIZE){
			Pte *pte;
			struct Page *pp;
			pp = page_lookup(curenv->env_pgdir, va, &pte);
			if(pp == NULL) continue;
			if(*pte  & PTE_LOG){
					*pte = *pte & (~PTE_LOG);
					*pte |= PTE_D;
					log_page_count++;
					tlb_invalidate(curenv->env_asid, va);
			}
	}

    return log_page_count;
}

int sys_get_dirty_log(u_long *ptr)

要求 ptr 指针指向的内存必须位于合法的用户态地址范围内（[UTEMP, UTOP)），否则返回 -E_INVAL。

跟之前一样嗯。

// 1. 检查 `ptr` 指向的虚拟地址的合法性
    // HINT: 你可以使用 `is_illegal_va` 函数
    // Lab4-Extra: Your code here. (12 / 19)
	if(is_illegal_va(ptr)){
		return -E_INVAL;
	}

要求 ptr 指针指向的内存必须已经映射且可写，否则返回 -E_INVAL。

这里又要用到page_lookup函数了，无映射的话这个函数会返回0。
随后再判断一下pte的权限位就可以了

Pte *pte;
   if (page_lookup(cur_pgdir, (u_long)ptr, &pte) == NULL) {
       return -E_INVAL;
   }

   if (!((*pte & PTE_V) && (*pte & PTE_D))) {
       return -E_INVAL;
   }

获取本进程的一项脏页记录（先进先出），将该脏页的起始地址写入到 ptr 指针指向的内存中。已获取的脏页记录将从脏页队列中移除。

这里需要用到dirty_is_empty函数，还是要注意传入的是队列的地址

// 3. 检查脏页队列是否为空
    // Lab4-Extra: Your code here. (13 / 19)
	if(dirty_is_empty(&curenv->log_queue)){
			return -E_DIRTY_EMPTY;
	}

完整函数如下

int sys_get_dirty_log(u_long *ptr) {
    // 1. 检查 `ptr` 指向的虚拟地址的合法性
    // HINT: 你可以使用 `is_illegal_va` 函数
    // Lab4-Extra: Your code here. (12 / 19)
	if(is_illegal_va(ptr)){
			return -E_INVAL;
	}
    // 2. 检查 `ptr` 指向的虚拟地址是否已有映射，且可写
    Pte *pte;
    if (page_lookup(cur_pgdir, (u_long)ptr, &pte) == NULL) {
        return -E_INVAL;
    }

    if (!((*pte & PTE_V) && (*pte & PTE_D))) {
        return -E_INVAL;
    }

    // 3. 检查脏页队列是否为空
    // Lab4-Extra: Your code here. (13 / 19)
	if(dirty_is_empty(&curenv->log_queue)){
			return -E_DIRTY_EMPTY;
	}
    // 4. 从队列中出队一个脏页记录
    // Lab4-Extra: Your code here. (14 / 19)
    u_long dirty_page_addr = dirty_remove(&curenv->log_queue);

    // 5. 向 `ptr` 指向的位置写入取出的脏页记录
    *ptr = dirty_page_addr;

    return 0;
}

我们终于实现了四个巨长的系统调用，但是这还没有结束
我们还需要重写do_tlb_mod函数，不过这里我们只来翻译注释就可以了。
显示修改权限位

// 5. 去除触发页面的脏页追踪标志，重新添加可写标志
// Lab4-Extra: Your code here. (15 / 19)
*pte = *pte & (~PTE_LOG);
*pte |= PTE_D;

注意要无效化的虚拟地址被保存在了tf->cp0_badvaddr（还记得lab3的知识嘛

1
2
3

// 6. 刷新 TLB：在更新页表项后，需要使用 `tlb_invalidate` 函数将 TLB 中的旧映射无效化
// Lab4-Extra: Your code here. (16 / 19)
tlb_invalidate(curenv->env_asid, tf->cp0_badvaddr);

嗯下一条不多解释了。

// 7. 将脏页的起始地址添加到脏页队列中
// HINT: 使用 `ROUNDDOWN(a, n)` 宏，可以将整数 a 向下对齐到整数 n，该宏返回对齐后的值
// Lab4-Extra: Your code here. (17 / 19)
dirty_add(&curenv->log_queue, ROUNDDOWN(tf->cp0_badvaddr, PAGE_SIZE));

下面这个稍微复杂一点，我们需要在栈中给脏页预留出一定的空间，我们的目的是将脏页记录按照一维数组的形式复制到用户异常栈，而每个元素的大小为 sizeof(u_long)。那么我们一共只需要预留ENV_MAX_DIRTY_LOG_COUNT * sizeof(u_long)这么多空间就可以了

// 12. 在异常栈上分配保存脏页记录的空间
// HINT: 我们总是假定用户异常栈上有足够的空间来容纳陷阱帧和所有脏页记录
// HINT: 你可以参考“10. 在异常栈上分配保存陷阱帧的空间”的方式进行分配，注意分配的空间应当能保存下所有脏页
// HINT: 脏页队列的容量为 ENV_MAX_DIRTY_LOG_COUNT （dirtyqueue.h）
// HINT: 将脏页记录按照一维数组的形式复制到用户异常栈，每个元素的大小为 sizeof(u_long)
// Lab4-Extra: Your code here. (18 / 19)
tf->regs[29] -= ENV_MAX_DIRTY_LOG_COUNT * sizeof(u_long);

接下来，我们只需要把每个脏页记录移出队列，并且按照顺序讲这些脏页记录赋值到刚才在栈上预留出的一维数组上就行了
这里用到C语言的一些知识，我们先把tf->regs[29]转化成u_long *类型，其指向数组的首元素。
随后(u_long *)tf->regs[29] + i就指向数组的第i个元素了，再解引用就能复制啦

// 14. 逐一将脏页记录出队，并写入异常栈上分配的空间中
// HINT: 代码执行到此处，前提条件是脏页队列已满
// HINT: 脏页队列的容量为 ENV_MAX_DIRTY_LOG_COUNT （dirtyqueue.h）
// Lab4-Extra: Your code here. (19 / 19)
for(int i = 0; i < ENV_MAX_DIRTY_LOG_COUNT; i++){
	*((u_long *)tf->regs[29] + i) = dirty_remove(&curenv->log_queue);
}

完整do_tlb_mod()函数如下

void do_tlb_mod(struct Trapframe *tf) {
    // 1. 获取发生页写入异常的页面
    Pte *pte;
    page_lookup(cur_pgdir, tf->cp0_badvaddr, &pte);
    assert((pte != NULL));

    // 2. 保存异常现场（陷阱帧）
    struct Trapframe tmp_tf = *tf;

    if ((*pte & PTE_COW) != 0) {
        // 3. 处理 CoW 页面
        if (tf->regs[29] < USTACKTOP || tf->regs[29] >= UXSTACKTOP) {
            tf->regs[29] = UXSTACKTOP;
        }

        tf->regs[29] -= sizeof(struct Trapframe);
        *(struct Trapframe *)tf->regs[29] = tmp_tf;

        if (curenv->env_user_tlb_mod_entry) {
            tf->regs[4] = tf->regs[29];
            tf->regs[29] -= sizeof(tf->regs[4]);
            // Hint: Set 'cp0_epc' in the context 'tf' to 'curenv->env_user_tlb_mod_entry'.
            tf->cp0_epc = curenv->env_user_tlb_mod_entry;
        } else {
            panic("TLB Mod but no user handler registered");
        }
    } else if ((*pte & PTE_LOG) != 0) {
        // 4. 处理脏页追踪页面
        // Precondition: `log_queue` 非满
        assert(!dirty_is_full(&curenv->log_queue));

        // 5. 去除触发页面的脏页追踪标志，重新添加可写标志
        // Lab4-Extra: Your code here. (15 / 19)
        *pte = *pte & (~PTE_LOG);
        *pte |= PTE_D; 
        // 6. 刷新 TLB：在更新页表项后，需要使用 `tlb_invalidate` 函数将 TLB 中的旧映射无效化
        // Lab4-Extra: Your code here. (16 / 19)
        tlb_invalidate(curenv->env_asid, tf->cp0_badvaddr);
        // 7. 将脏页的起始地址添加到脏页队列中
        // HINT: 使用 `ROUNDDOWN(a, n)` 宏，可以将整数 a 向下对齐到整数 n，该宏返回对齐后的值
        // Lab4-Extra: Your code here. (17 / 19)
        dirty_add(&curenv->log_queue, ROUNDDOWN(tf->cp0_badvaddr, PAGE_SIZE));
        // 8. 若队列已满
        if (dirty_is_full(&curenv->log_queue)) {
            // 是否设置了用户态脏页处理程序？
            if (curenv->log_entry != 0) {
                // 若队列已满，且已经设置用户态脏页处理程序

                // 9. 设置异常栈指针
                if (tf->regs[29] < USTACKTOP || tf->regs[29] >= UXSTACKTOP) {
                    tf->regs[29] = UXSTACKTOP;
                }

                // 10. 在异常栈上分配保存陷阱帧的空间，并写入陷阱帧
                tf->regs[29] -= sizeof(struct Trapframe);
                *(struct Trapframe *)tf->regs[29] = tmp_tf;

                // 11. 记录保存的陷阱帧的起始地址
                u_long user_tf_addr = tf->regs[29];

                // 12. 在异常栈上分配保存脏页记录的空间
                // HINT: 我们总是假定用户异常栈上有足够的空间来容纳陷阱帧和所有脏页记录
                // HINT: 你可以参考“10. 在异常栈上分配保存陷阱帧的空间”的方式进行分配，注意分配的空间应当能保存下所有脏页
                // HINT: 脏页队列的容量为 ENV_MAX_DIRTY_LOG_COUNT （dirtyqueue.h）
                // HINT: 将脏页记录按照一维数组的形式复制到用户异常栈，每个元素的大小为 sizeof(u_long)
                // Lab4-Extra: Your code here. (18 / 19)
                tf->regs[29] -= ENV_MAX_DIRTY_LOG_COUNT * sizeof(u_long);
                // 13. 记录脏页记录的起始地址
                u_long user_log_addr = tf->regs[29];

                // 14. 逐一将脏页记录出队，并写入异常栈上分配的空间中
                // HINT: 代码执行到此处，前提条件是脏页队列已满
                // HINT: 脏页队列的容量为 ENV_MAX_DIRTY_LOG_COUNT （dirtyqueue.h）
                // Lab4-Extra: Your code here. (19 / 19)
                for(int i = 0; i < ENV_MAX_DIRTY_LOG_COUNT; i++){
                        *((u_long *)tf->regs[29] + i) = dirty_remove(&curenv->log_queue);
                }
                // 15. 设置陷阱帧的 a0 寄存器为保存的陷阱帧的起始地址
                tf->regs[4] = user_tf_addr;
                // 16. 设置陷阱帧的 a1 寄存器为脏页记录的起始地址
                tf->regs[5] = user_log_addr;

                tf->regs[29] -= 2 * sizeof(tf->regs[4]);
                // 17. 设置返回地址
                tf->cp0_epc = curenv->log_entry;
            } else {
                // 若队列已满，且未经设置用户态脏页处理程序
                // 18. 从脏页队列中出队一个脏页记录（并丢弃），保证返回时脏页队列非满
                dirty_remove(&curenv->log_queue);
            }
        }
        // Postcondition: `log_queue` 非满

    } else {
        panic("Unexpected TLB Mod for va = 0x%08lx, epc = 0x%08lx, pte = 0x%08lx", tf->cp0_badvaddr, tf->cp0_epc, *pte);
    }
}

上机+写博客感悟：求求助教下手轻点。。

lab5-exam

由于这一届由于机房的空调出了问题（什？，导致lab4上机延后了一周，而lab5没有顺延，所以大家要在一周时间内学习lab5，而学过lab5的都知道，这次实验东西实在是太太太多了。。
好在本次的题较去年来说简单了许多，感谢助教手下留情

那些只需要复制粘贴的内容这里就不赘述了，我们主要需要实现的是list_dir_entries函数，这个函数的主要作用就是把ls的结果加入到res中去

题干要求是这样：如果f是文件，那么直接把f->f_name加入到res里。
如果f是目录，那么还需要在加入到res后，在的末尾中加一个/
如果all == 1，我们需要让ls能显示以.开头的文件，即等价于ls -a

int list_dir_entries(struct File *ls_dir, u_int all, struct Ls_res *res) {
	u_int nblock;
	nblock = ls_dir->f_size / BLOCK_SIZE;

	for (int i = 0; i < nblock; i++) {
		void *blk;
		try(file_get_block(ls_dir, i, &blk));
		struct File *files = (struct File *)blk;

		for (struct File *f = files; f < files + FILE2BLK; ++f) {
			// 按照“行为规则”表述，对当前磁盘块中的每一个文件控制块 f，
			// 完成函数的核心功能。具体功能请参考题面要求。
			// lab5-exam: Your code here. (1/3)
			if((f->f_name[0] == '.' && all == 0) || f->f_name[0] == '\0'){
				continue;
			}else{
				strcpy(res->file_name[res->count], f->f_name);
				if(f->f_type == FTYPE_DIR){
						int l = strlen(res->file_name[res->count]);
						res->file_name[res->count][l] = '/';
						res->file_name[res->count][l + 1] = '\0';
				}
				res->count++;
			}
		}
	}
	return 0;
}

有一个坑很多人踩在这里！就是

strcpy(res->file_name[res->count], f->f_name);
if(f->f_type == FTYPE_DIR){
		int l = strlen(res->file_name[res->count]);
		res->file_name[res->count][l] = '/';
		res->file_name[res->count][l + 1] = '\0';
}

这几行，觉得这里要写四行代码太过麻烦（，于是选择直接更改f，如果f->f_type == FTYPE_DIR，那么直接将f的末尾加上一个/，再复制到加入到res里

实际上这个方法是错误的，只能拿到五十分！因为如果直接对f下手的话，那么每次ls都会更改目录的文件名，导致多次ls的结果和预期对不上！

list_files函数只需要先用walk_path找到对应的目录，然后调用list_dir_entries就可以了。调用walk_path中，由于我们只需要path对应的目录，所以剩下两个参数传入0即可。

int list_files(const char *path, u_int all, struct Ls_res *res) {
	struct File *ls_dir;
	char path1[MAXPATHLEN];
	strcpy(path1, path);  // 将 const char* 转为 char*

	// 找到 path 对应的目录。提示：可能会用到 walk_path。
	// lab5-exam: Your code here. (2/3)
	int r;
	if((r = walk_path(path, 0, &ls_dir, 0) < 0)){
			return r;
	}
	// 调用辅助函数，完成核心功能。
	// lab5-exam: Your code here. (3/3)

	list_dir_entries(ls_dir, all, res);
	return 0;
}

lab5-extra

这次extra难度不高（，主要就是需要来回翻题干，怪麻烦的（

首先我们要实现一个file_seal函数，实现对文件的密封
我们要计算文件的全文件摘要，通过全文件摘要填写文件的FileVerity结构体，然后填写对应的字段，照着提示内容翻译成C即可

int file_digest(struct File *f, uint32_t *hash_store) 用于计算文件 f 当前内容的全文件摘要。调用成功时返回 0，并把摘要写入第二个参数指向的变量；调用失败时返回对应错误码。你可以直接调用该函数来计算当前文件的全文件摘要。
可调用 file_verity(f) 得到该文件的 FileVerity 结构体；
v_size 应填写为当前文件大小 f_size；
若 file_digest() 返回错误，应直接返回该错误码。

int file_seal(char *path) {
        int r;
        struct File *f;

        if (path == 0 || path[0] == '\0' || strlen(path) >= MAXPATHLEN) {
                return -E_BAD_PATH;
        }
        if ((r = file_open(path, &f)) < 0) {
                return r;
        }
        if (!file_regular(f)) {
                return -E_INVAL;
        }

        // Lab5-Extra: Your code here. (1/6)
        // 调用 file_digest() 计算当前文件的全文件摘要。
        // 然后填写该文件的 FileVerity 结构体，
        // 需要填写的字段有：v_magic、v_flags、v_size 和 v_digest。
        uint32_t hash_store;
        if((r = file_digest(f, &hash_store) < 0)){
                return r;
        }
        struct FileVerity *v = file_verity(f);
        v->v_magic = FVERITY_MAGIC;
        v->v_flags |= FVERITY_SEALED;
        v->v_size = f->f_size;
        v->v_digest = hash_store;
        // Lab5-Extra: End (1/6).
        file_close(f);
        if (f->f_dir) {
                file_flush(f->f_dir);
        }
        return 0;
}

接下来是file_verity函数，需要满足下面几个要求，直接翻译即可

若重新计算摘要失败，应直接返回该错误码；
若重新计算出的摘要与 v->v_digest 不一致，返回 -E_VERIFY；
校验通过时返回 0。

int file_verify(struct File *f) {
        struct FileVerity *v;

        if (!file_regular(f) || !file_is_sealed(f)) {
                return -E_INVAL;
        }

        v = file_verity(f);
        if (f->f_size != v->v_size) {
                return -E_VERIFY;
        }

        // Lab5-Extra: Your code here. (2/6)
        // 调用 file_digest() 重新计算摘要，并与 v->v_digest 比较。
        uint32_t hash_store;
        int r;
        if((r = file_digest(f, &hash_store) < 0)){
                return r;
        }
        if(hash_store != v->v_digest){
                return -E_VERIFY;
        }

        // Lab5-Extra: End (2/6).
        return 0;
}

完成了上面两个函数，接下来我们要做的是完成调用这两个函数的链路

首先我们要先在user/include/fsreq.h中加入FSREQ_SEAL, FSREQ_VERIFY,两个请求号，注意新引入的请求号要在 MAX_FSREQNO 之前。

随后我们要加入所需的请求结构体，我们只需要req_path这一个参数，并且上面两个函数共用这一个请求结构体

struct Fsreq_path {
        // Lab5-Extra: Your code here. (3/6)
        // 只需要 req_path 参数。
        char req_path[MAXPATHLEN];
        // Lab5-Extra: End (3/6).
};

随后我们要在user/include/lib.h中加入fsipc函数声明和用户接口函数函数声明

// 函数声明 
// fsipc 函数
int fsipc_seal(const char *path); 
int fsipc_verify(const char *path);
// 用户接口函数
int fseal(const char *path); 
int fverify(const char *path);

接下来我们要在user/lib/fsipc.c中实现这两个fsipc函数，我们要做的实际上及时把fsipcbuf强转成刚才新加的请求结构体(struct Fsreq_path *)，随后调用fsipc函数

 int fsipc_seal(const char *path) {
        struct Fsreq_path *req;

        if (path == 0 || path[0] == '\0' || strlen(path) >= MAXPATHLEN) {
                return -E_BAD_PATH;
        }

        // Lab5-Extra: Your code here. (4/6)
        // 将 fsipcbuf 转为对应的结构体指针，填写 req_path，并调用 fsipc() 发送对应请求。
        req = (struct Fsreq_path *)fsipcbuf;
        strcpy((char *)req->req_path, path);
        return fsipc(FSREQ_SEAL, req, 0, 0);
        // Lab5-Extra: End (4/6).
}

int fsipc_verify(const char *path) {
        struct Fsreq_path *req;

        if (path == 0 || path[0] == '\0' || strlen(path) >= MAXPATHLEN) {
                return -E_BAD_PATH;
        }

        // Lab5-Extra: Your code here. (5/6)
        // 将 fsipcbuf 转为对应的结构体指针，填写 req_path，并调用 fsipc() 发送对应请求。
        req = (struct Fsreq_path *)fsipcbuf;
        strcpy((char *)req->req_path, path);
        return fsipc(FSREQ_VERIFY, req, 0, 0);
        // Lab5-Extra: End (5/6).
}

最后，我们要在fs/serv.c中修改serve_open()函数，
也是翻译注释即可，注意，判断文件的打开模式要用rq->req_omode & O_ACCMODE)，所以如果是只读打开时，我们要写的判断语句实际是if((rq->req_omode & O_ACCMODE) == O_RDONLY)，而不时if(rq->req_omode & O_RDONLY)，这条语句是错的！（我就在这卡了许久
由于我们不需要传页，所以ipc_send的后两个参数都传0就可以

// Save the file pointer.
o->o_file = f;

// Lab5-Extra: Your code here. (6/6)
// 若 f 已 sealed：
// 1. 遇到 O_TRUNC、O_WRONLY 或 O_RDWR，向请求进程返回 -E_SEALED 并 return；
// 2. 只读打开时调用 file_verify(f)，若返回错误则把该错误返回给请求进程并 return。
if(file_is_sealed(f)){
	if((rq->req_omode &  O_TRUNC) || (rq->req_omode & O_WRONLY) || (rq->req_omode & O_RDWR)){
		ipc_send(envid, -E_SEALED, 0, 0);
		return;
	}
	if((rq->req_omode & O_ACCMODE) == O_RDONLY){
		r = file_verify(f);
		if(r != 0){
				ipc_send(envid, r, 0, 0);
				return;
		}
	}
}
// Lab5-Extra: End (6/6).

lab6

可能更新（