OS2025 上机考试全攻略

关于题目和题解，出于助教身份的考虑，我不方便直接提供往年题目，还请大家能够谅解。目前大家只能看到所有问题的题解，你可以使用右侧的导航栏快速定位到想要查看的内容。

Lab 0 Exam

这几道题目都比较简单，但是主打一个量大管饱，要想全写完还是需要相当一些时间的。我们来一道一道破解：

首先是 Makefile Quiz 。对于 make check 命令，题目要求我们利用 gcc 将同目录下的 check.c 编译为未链接的 check.o ，并放在同目录下。

这里需要注意的是，注意题目要求生成的不是可执行文件，而是未链接的 .o 文件，所以我们需要加上 -c 选项：gcc -c ./check.c 。

接下来，我们使用 -o 选项来指定生成的文件：gcc -c ./check.c -o ./check.o 。将其填入 Makefile 中：

1
2
3
# Makefile
check:
    gcc -c ./check.c -o ./check.o

对于 make 命令，当 make 后没有任何内容时，默认执行 Makefile 中的第一个目标，我们通常将其取名为 all 。注意一定要将其放在 check 的前面，确保其是 Makefile 中的第一个目标！

题目要求我们在执行 make 前需要先完成 make check ，于是我们在 all 的冒号后面加上 check ，表示上述依赖关系：all: check 。

接下来，我们需要利用 gcc 将 src 目录下的 main.c output.c 编译成名为 main 的可执行文件，并放在 out 目录下。那么就是 gcc ./src/main.c ./src/output.c -o ./out/main 。

但是我们千万不要忘记了题目中给出的提示：在实现 make 时，可能需要指定头文件目录。我们观察 src/main.c 和 src/output.c 两个文件，发现二者均引用了 inter.h 头文件，而该文件位于 src/include/ 中，于是我们需要在编译时使用 -I 选项指定该目录作为头文件目录：gcc -I ./src/include ./src/main.c ./src/output.c -o ./out/main 。

于是我们可以得到如下的 Makefile ：

1
2
3
4
5
6
# Makefile
all: check
    gcc -I ./src/include ./src/main.c ./src/output.c -o ./out/main

check:
    gcc -c ./check.c -o ./check.o

对于 make run ，我们只需要执行 ./out/main 命令，即可运行可执行文件 out/main 。这里需要注意命令的前面必须有 ./ ，否则将无法定位到文件位置：

1
2
3
4
5
6
7
8
9
# Makefile
all: check
    gcc -I ./src/include ./src/main.c ./src/output.c -o ./out/main

check:
    gcc -c ./check.c -o ./check.o

run:
    ./out/main

最后是 make clean ，我们只需要使用 rm 指令即可。保险起见，我们可以为 rm 指令加上 -f 选项：

1
2
3
4
5
6
7
8
9
10
11
12
# Makefile
all: check
    gcc -I ./src/include ./src/main.c ./src/output.c -o ./out/main

check:
    gcc -c ./check.c -o ./check.o

run:
    ./out/main

clean:
    rm -f ./check.o ./out/main

这样我们就完成了 Makefile Quiz ！接下来是 Bash Quiz ：

Bash Quiz 题量更大，但是相对来说要简单一些。如果你有时间看一下执行脚本的话，可以发现脚本中是使用 bash xxx.sh 命令执行我们写的脚本的，它和使用 ./x.sh 执行脚本的区别就是，在前者的情况下，我们实际上不需要在我们的脚本开头加 Shebang ，也就是 #!/bin/bash 。不过加上当然也没错，保险起见的话，加上也是完全没问题的。

我们首先来看第一题，其实就是用 mkdir 命令创建 3 个目录：

1
2
3
4
# exam_1.sh
mkdir ./result
mkdir ./result/code
mkdir ./result/backup

第二题是一个非常简单的 grep 命令，不需要添加任何选项。顺带一提，如果不区分大小写，需要加上 -i 选项（当然，这些不需要死记硬背，在预习教程和指导书里都查得到）：

1
2
# exam_2.sh
grep "hello" ./origin/basic.c

第三题就是一个简单的 mv 命令，在这里也不多说了：

1
2
# exam_3.sh
mv ./origin/basic.c ./result/

第四题和第三题类似，只不过是使用 cp 命令。但是要注意在复制目录时要使用 -r 选项进行递归复制：

1
2
# exam_4.sh
cp -r ./origin/code/ ./result/backup/

第五题算是一个小 boss ，首先我们需要知道如何使用 sed 命令将文件中的 REPLACE 全部替换为文件名，我们以 ./origin/code/0.c 文件为例，即为 sed "s/REPLACE/0/g" ./origin/code/0.c 。这里的 g 代表将全部的 REPLACE 替换为 0 ，否则只会将每行中的第一个 REPLACE 替换为 0 。

另外，这里不需要加 -i 选项，因为我们不需要修改 ./origin/code/0.c 文件本身。但此时修改后的结果会输出在控制台上，为了将其输出到 ./result/code/0.c 文件中，我们还需要将标准输出流重定向至文件：sed "s/REPLACE/0/g" ./origin/code/0.c > ./result/code/0.c 。

接下来我们就需要处理循环了。bash 脚本的循环也是相当难写，不过你懂的，相信学过 Verilog 的你，一定想起了屡试不爽的那招：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# exam_5.sh
sed "s/REPLACE/0/g" ./origin/code/0.c > ./result/code/0.c
sed "s/REPLACE/1/g" ./origin/code/1.c > ./result/code/1.c
sed "s/REPLACE/2/g" ./origin/code/2.c > ./result/code/2.c
sed "s/REPLACE/3/g" ./origin/code/3.c > ./result/code/3.c
sed "s/REPLACE/4/g" ./origin/code/4.c > ./result/code/4.c
sed "s/REPLACE/5/g" ./origin/code/5.c > ./result/code/5.c
sed "s/REPLACE/6/g" ./origin/code/6.c > ./result/code/6.c
sed "s/REPLACE/7/g" ./origin/code/7.c > ./result/code/7.c
sed "s/REPLACE/8/g" ./origin/code/8.c > ./result/code/8.c
sed "s/REPLACE/9/g" ./origin/code/9.c > ./result/code/9.c
sed "s/REPLACE/10/g" ./origin/code/10.c > ./result/code/10.c
sed "s/REPLACE/11/g" ./origin/code/11.c > ./result/code/11.c
sed "s/REPLACE/12/g" ./origin/code/12.c > ./result/code/12.c
sed "s/REPLACE/13/g" ./origin/code/13.c > ./result/code/13.c
sed "s/REPLACE/14/g" ./origin/code/14.c > ./result/code/14.c
sed "s/REPLACE/15/g" ./origin/code/15.c > ./result/code/15.c
sed "s/REPLACE/16/g" ./origin/code/16.c > ./result/code/16.c
sed "s/REPLACE/17/g" ./origin/code/17.c > ./result/code/17.c
sed "s/REPLACE/18/g" ./origin/code/18.c > ./result/code/18.c
sed "s/REPLACE/19/g" ./origin/code/19.c > ./result/code/19.c
sed "s/REPLACE/20/g" ./origin/code/20.c > ./result/code/20.c

当然，在这里我还是给出一个使用 while 循环解决的模板，以供参考：

1
2
3
4
5
6
7
8
9
# exam_5.sh
n=20
i=0

while [ $i -le $n ]
do
    sed "s/REPLACE/$i/g" ./origin/code/$i.c > ./result/code/$i.c
    let i=i+1
done

这里细节很多，连空格都有严格要求，比如中括号的内部两端必须有空格，let 后面的表达式绝对不可以有空格，等等。即使照着抄也容易抄错，所以还是推荐上面循环展开的方法，丑陋但十分有用。

第六题难度又降下来了，是一个简单的使用 gcc 编译的问题。这里涉及到了全部 .c 文件，好在提示中给出了使用通配符 * 的方法，这样就没有任何问题了：

1
2
# exam_6.sh
gcc ./result/code/*.c -o ./result/verify

第七题考察的是标准错误流的追加重定向。运行可执行文件就不说了，还是要记得在前面加上 ./ 。对于标准错误流的追加重定向，我们要记得在追加重定向 >> 的前面加上 2 ，这样就可以了：

1
2
# exam_7.sh
./result/verify 2>> ./stderr.txt

第八题考察的是 chmod 命令，要求我们为文件赋予 r--r----- 的权限。这里最简单的方式就是使用数字来表示。我们将权限拆成 3 个 3 位内容，即 r-- r-- --- ；接下来将每个非 - 位置 1 ，将每个 - 位置 0 ，即 100 100 000 ；然后我们将其视作 3 个二进制数，分别转换为十进制数，即 440 。于是我们就得到了权限位对应的数字，这样就得到了命令：

1
2
# exam_8.sh
chmod 440 ./stderr.txt

第九题就是最终 boss 了！这道题中再次出现了 sed 命令，不过在此之前，我们需要知道如何读取命令后参数的数量，以及如何获取到命令后的参数。

在 bash 脚本中，我们使用 $# 来获取参数的个数，使用 $1 和 $2 分别获取第 1 个参数和第 2 个参数的内容。结合 if - then - elif - then - else - fi 语句，我们可以实现根据不同参数个数执行不同命令：

1
2
3
4
5
6
7
8
9
10
# exam_9.sh
if [ $# -eq 0 ]
then
    ......
elif [ $# -eq 1 ]
then
    ......
else
    ......
fi

还是需要注意，这里的条件判断如果使用中括号，那么中括号内部两侧必须有空格，也就是不能写成 if [$# -eq 0] 。这里也可以使用双小括号，也就是 if (($# == 0)) 。

接下来我们分别处理不同参数下的情况。首先是 0 个参数，我们需要输出 stderr.txt 的所有内容。这种情况下，我们可以直接使用 cat 命令，而不需要使用复杂的 sed 命令：cat ./stderr.txt 。

然后是 1 个参数，我们需要输出 stderr.txt 从第 $1 行（包含）到结尾的内容，这个时候就需要用到 sed 命令了：sed -n "$1,\$p" ./stderr.txt 。

这条命令细节很多，非常值得我们深入研究。首先是 -n 选项，在使用 p 进行部分输出时，一般都要包含 -n 选项，否则会额外把整个文件多输出一遍，这肯定不是我们想要的。接下来是双引号，这里不能使用单引号，因为我们在引号内使用了变量 $1 。使用双引号的话，$1 能够被正确替换为它内部的值；而使用单引号的话，$1 会直接被认为是字符串的一部分，不进行任何转换。接下来是双引号内部，p 前面的两个数字分别表示输出开始的行号和输出结束的行号，使用逗号分割。逗号后面的字符 $ 可以看作一个特殊的数字，代表着最后一行，之所以写成 \$ 是因为它位于双引号内部，需要进行转义，否则会被认为是与后面的 p 连成的变量 $p ；如果字符 $ 位于单引号内部则不需要转义。

接下来是 2 个参数，我们需要输出 stderr.txt 从第 $1 行（包含）到第 $2 行（不包含）的内容。这个命令依然没有我们想象中的那么简单，因为 sed 命令中逗号前后的两个行号都是包含的，也就是说如果我们想实现不包含第 $2 行的效果，就需要手动将 $2 减去 1 ：sed -n "$1,$(($2 - 1))p" result.txt 。

这里的双小括号用于计算 $2 - 1 的值，在双小括号前再加上一个 $ 用于获取计算的结果。

我们将三种情况的命令填入分支中，就完成了这道最终 boss ：

1
2
3
4
5
6
7
8
9
10
# exam_9.sh
if [ $# -eq 0 ]
then
    cat ./stderr.txt
elif [ $# -eq 1 ]
then
    sed -n "$1,\$p" ./stderr.txt
else
    sed -n "$1,$(($2 - 1))p" result.txt
fi

这样，我们就完成了 exam 的所有题目！内容实在是太多了，如果对这部分内容不是很熟的话，可能要花到一个小时，纯折磨。不过接下来的 extra 才是真的坐牢 ——

Lab 0 Extra

相当变态的一道题，不知道有多少同学在那个深夜道心破碎，从此彻底告别 OS 这片领域。懒得喷。

总而言之，我们要实现的是 5 个脚本，每个脚本都相当有难度。其中不乏涉及到一些我们从未学过的知识，所以除非你是命令行领域大神，否则几乎没有做上的可能。

第一个脚本是 genCode.sh ，我们需要创建 codeSet 目录，遍历 code 目录下的所有 .sy 文件，进行处理后保存在 codeSet 目录下的同名 .c 文件中。其实处理文件这一步并不是特别复杂，在 exam 中我们已经使用过很多次 sed 命令了，关键问题在于我们该如何提取出文件名，并将其结尾的 .sy 替换为 .c 。

在题目结尾的提示中，我们学习到可以使用 for 循环 for file in $(ls dir/) ，此时 $file 是一个字符串，表示当前文件的文件名。那么，我们该如何将 $file 结尾的 .sy 替换为 .c 呢？一种我们学过的方法是将其保存在文件中，使用 sed 命令对其进行处理。然而每次处理字符串都要创建新文件还是太麻烦了，简化一点的操作是使用管道，我们可以将 echo $file 输出的结果通过管道直接传入 sed 命令中，即 echo $file | sed 's/.sy/.c/g' 。

实际上，Linux 中也提供了直接操作字符串的语法，相比 sed 命令难度更低，而且灵活性更高。对于值为 HelloWorld 的字符串 $str ，${str:2} 表示从下标为 2 的位置开始到结尾的字符串（从 0 开始计数），即 lloWorld ；${str:2:4} 表示从下标为 2 的位置开始长度为 4 的字符串，即 lloW 。这里的两个数字还可以是负数，${str:(-2)} 表示从倒数第 2 个字符开始到结尾的字符串，即 ld ；${str:4:(-2)} 表示从第 4 个字符开始去除结尾 2 个字符的字符串，即 lloWor 。这里要注意的是，在使用负数的时候，我们最好在负数的两侧加上括号，防止冒号和减号连接成 :- 从而产生歧义。虽然不加括号不一定会出问题，不过只能中午不加，因为早晚会出问题。

通过上面的知识，我们就可以使用 ${file:0:(-3)}.c 处理 $file ，即去除 $file 的结尾的 3 个字符，再加上 .c 就可以了。不过我在考场中上面两个方法都没有想出来，所以只能遗憾离场了：

1
2
3
4
5
6
7
# genCode.sh
mkdir ./codeSet/

for file in $(ls ./code/)
do
    sed -e '1i\#include"include/libsy.h"' -e 's/getInt/getint/g' "./code/$file" > "./codeSet/${file:0:(-3)}.c"
done

接下来是 selectCode.sh 脚本，这个脚本就比较简单了。题目下面的提示已经给出了软链接的创建方法，另外在 exam 中，我们也已经实现过带有头文件的编译了：

1
2
3
4
# selectCode.sh
rm -f ./testfile.c
ln -s "./codeSet/$1.c" ./testfile.c
gcc -I ./include ./testfile.c -o ./test.out

接下来是 selectData.sh 脚本，这个脚本的难点主要在于如何根据参数选出合适的测试集文件。提示中已经给出可以使用 if [ "$string1" = "$string2" ]; then 来进行字符串匹配。这里注意，如果要将 if 和 then 写在同一行，那么 then 前面就需要有分号 ; ；反之则不需要加分号。

首先我们使用 for 循环遍历 data 目录中所有的文件。如果参数 $1 是 all 的话，那么就直接将当前文件复制到 dataSet 目录中；否则就检查当前文件名的第一个字符与参数 $1 是否相同，这里就可以使用 ${file:0:1} 获取到文件名的第一个字符，如果满足条件的话就将当前文件复制到 dataSet 目录中：

1
2
3
4
5
6
7
8
9
10
11
12
13
# selectData.sh
mkdir ./dataSet/

for file in $(ls ./data/)
do
    if [ $1 = "all" ]; then
        cp "./data/$file" "./dataSet/$file"
    else
        if [ ${file:0:1} = $1 ]; then
            cp "./data/$file" "./dataSet/$file"
        fi
    fi
done

下面的 testProgram.sh 更是逆天至极，难点真是太多了。第一个难点就是如何清空 testRes.txt 文件中的内容。最容易想到的做法就是将这个文件删掉之后重新创建，不过我们也可以使用重定向直接向 testRes.txt 文件中写入滚木空串。这里要注意的是，使用 echo "" > testRes.txt 写入空串的做法是错误的，因为 echo 命令在输出的时候会自动在结尾加上一个换行符，我们可以使用 -n 选项取消结尾的换行符，即 echo -n "" > testRes.txt ，或者直接使用 > testRes.txt 即可。

接下来我们使用 for 循环遍历 dataSet 目录中的所有文件，对所有的 .in 文件进行操作，此时我们可以使用 ${file:(-3)} 取出文件名的后 3 个字符。

在对 .in 文件的操作中，我们需要频繁用到不含扩展名的文件名，于是我们可以将其存储在一个变量 basename 中，使用 basename=${file:0:(-3)} 即可实现对 basename 的赋值。这里需要注意的是，在这种赋值语句中，等号的两边绝对不能有空格！

在选中 .in 文件之后，我们将 dataSet/$basename.in 输入 test.out 中执行，并将执行结果保存在 output/$basename.out 中，这里只需要使用输入重定向和输出重定向就可以了：./test.out < "./dataSet/$basename.in" > "./output/$basename.out" 。

接下来又是一个难点，我们需要将 output/$basename.out 与 dataSet/$basename.out 进行比对，根据比对结果向 testRes.txt 中写入 1 或 0 。我们不难想到使用 diff 命令来查找两个文件之间的差异，不过我们该如何将这个结果应用到判断条件中呢？实际上，每条命令除了有输出内容之外，还都有一个返回值。我们可以直接将 diff 命令作为 if 语句的判断条件，如果两个文件不相同则满足判断条件，如果两个文件相同则不满足判断条件，这里注意不要写反了。顺带一提，我们还可以使用 $? 这个特殊的变量来获取上一条执行的命令的返回值。

在使用 if 语句判断正误之后，我们使用追加重定向 >> 向 testRes.txt 文件中写入比对结果。不仅如此，我们还需要在文件的第一行写入总体的比对结果，这就需要我们维护一个表示是否全部正确的变量 ak 。我们在初始时使用 ak=1 将其置为 1 ，只要比对结果为不相同，则使用 let ak=0 将其置为 0 即可。最后我们使用 sed 命令将 ak 插入 testRes.txt 文件的第一行即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# testProgram.sh
mkdir ./output/
> ./testRes.txt

ak=1
for file in $(ls ./dataSet/)
do
    if [ ${file:(-3)} = ".in" ]; then
        basename=${file:0:(-3)}
        ./test.out < "./dataSet/$basename.in" > "./output/$basename.out"
        if diff "./output/$basename.out" "./dataSet/$basename.out"; then
            echo "$basename 1" >> ./testRes.txt
        else
            echo "$basename 0" >> ./testRes.txt
            let ak=0
        fi
    fi
done

sed -i "1i$ak" ./testRes.txt

最后是 viewData.sh 脚本，这个脚本更是一道更比三道强。我们首先来完成 focus 模式，这里我们不能直接对 testRes.txt 进行排序，因为 testRes.txt 的第一行是总体的比对结果。我们需要先使用 sed 命令输出 testRes.txt 的第一行，接下来再对剩余行进行排序。这里我们可以将剩余行写入一个文件中，再对该文件使用 sort 命令，当然也可以使用管道，直接将剩余行从标准输入流输入 sort 命令中。根据提示中 sort 命令的使用方法，我们能够写出题目要求对应的选项 -k2n -k1r 。

接下来是 wrong 模式，这个更是阴到没边了。首先我们要选出 testRes.txt 中所有比对结果为错误的行，这里使用的是 grep 命令 grep " 0" testRes.txt ，实际上也可以使用 sed 命令 sed -n '/ 0/p' testRes.txt 来实现。这里注意识别符是一个空格加上 0 ，如果没有空格的话会把第一行也选取出来。接下来，我们将选取出来的内容通过管道传递给下一条命令，使用 sed 's/ 0//g' 命令将每行结尾的 0 替换为空串。最后，我们再将输出的内容通过管道传递，使用 sort -k1r 命令将其排序即可。

最后是 search 模式，这个就比较简单了，我们只需要使用 grep 命令查找文件中含有 $2 的行就可以了：

1
2
3
4
5
6
7
8
9
# viewData.sh
if [ $1 = "focus" ]; then
    sed -n '1p' testRes.txt
    sed -n '2, $p' testRes.txt | sort -k2n -k1r
elif [ $1 = "wrong" ]; then
    grep " 0" testRes.txt | sed 's/ 0//g' | sort -k1r
elif [ $1 = "search" ]; then
    grep "$2" testRes.txt
fi

这样，我们讲究完成了全部的 5 个脚本。这几道题实在是太离谱了，题目中给的提示还是不够，这种题只要是有一个步骤完全不会，基本上就只能干瞪眼了。理论上来说，OS 上机实在做不上是可以求助助教的。不过根据实战经验，助教一般都在忙着帮助做不上 exam 的同学，一般没时间管在做 extra 的同学。而且说实话，助教的业务水平实在是参差不齐，有的助教完全不验题的，他们自己都不知道怎么做，真的会告诉你一个错误的思考方向，到头来还是得靠自己。

Lab 1 Exam

我说这道题非常简单，没意见吧？实际上，这个所谓的 %k 只不过是 %s 和 %d 的合体罢了，我们只需要结合 %s 和 %d 的代码就可以将其轻松解决！

首先，我们将 %s 的代码复制进去：

1
2
3
4
5
6
7
8
9
// lib/print.c
void vprintfmt(fmt_callback_t out, void *data, const char *fmt, va_list ap) {
    ......
    case 'k':
        s = (char *)va_arg(ap, char *);
        print_str(out, data, s, width, ladjust);
        ......
    ......
}

接下来，我们固定输出 4 个字符 =>（注意两侧的空格），这里可以使用 %c 的逻辑，分四个字符输出，也可以使用 %s 的逻辑，直接输出一个字符串：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// lib/print.c
void vprintfmt(fmt_callback_t out, void *data, const char *fmt, va_list ap) {
    ......
    case 'k':
        s = (char *)va_arg(ap, char *);
        print_str(out, data, s, width, ladjust);

        c = ' ';
        print_char(out, data, c, 1, ladjust);
        c = '=';
        print_char(out, data, c, 1, ladjust);
        c = '>';
        print_char(out, data, c, 1, ladjust);
        c = ' ';
        print_char(out, data, c, 1, ladjust);
        ......
    ......
}

最后，我们将 %d 的代码复制进去，别忘了在结尾加上 break 语句：

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
// lib/print.c
void vprintfmt(fmt_callback_t out, void *data, const char *fmt, va_list ap) {
    ......
    case 'k':
        s = (char *)va_arg(ap, char *);
        print_str(out, data, s, width, ladjust);

        c = ' ';
        print_char(out, data, c, 1, ladjust);
        c = '=';
        print_char(out, data, c, 1, ladjust);
        c = '>';
        print_char(out, data, c, 1, ladjust);
        c = ' ';
        print_char(out, data, c, 1, ladjust);

        if (long_flag) {
            num = va_arg(ap, long int);
        } else {
            num = va_arg(ap, int);
        }
        neg_flag = 0;

        if (num < 0) {
            neg_flag = 1;
            num = -num;
        }

        print_num(out, data, num, 10, neg_flag, width, ladjust, padc, 0);

        break;
    ......
}

这样，我们就轻松完成了这道题，太简单了！如果你在这道题上花费了超过了 5 分钟，那就样衰了！哈哈！

Lab 1 Extra

这道题的难度还是比较大的，需要我们了解回调函数的机制，并且仔细阅读问题，同时对 C 语言的指针也有所考察。在本题中，我们需要修改 lib/string.c 文件，根据题目引入头文件之后，我们还需要实现 4 个函数。

首先是 fmemopen() 函数，题目描述得非常高大上，看起来有点困难。不过我们仔细分析题目要求，就会发现它实际上只实现了一个很简单的需求，那就是根据 mode 的内容，修改 stream 中的三个指针 ptr base end 的值。这个函数如果想比较优雅地实现的话，就需要灵活运用到我们已经实现过的 string.h 库中的函数了。

首先是判断当前 mode 的字符串是否是 "w" 或 "a" 。这里上来就拉了坨大的，很多同学就是错在了这里，到最后都想不明白。我们再仔细读题，就会发现需要检查的是整个 mode 字符串是不是（带双引号的）"w" 或 "a" ，所以很多同学直接使用 if (*mode == w) 或者 if (mode[0] == 'w') 之类的判断方法就错误了。惯性思维让我们觉得 mode 字符串中一定只有一个字符，然而事实并非如此。正确的写法应该是使用 strcmp() 函数，用 if (!strcmp(mode, "w")) 来进行判断。

分支内部对于 3 个指针的修改就比较简单了，如果想将指针 ptr 指向 buf 的首地址，直接使用 ptr = buf 即可；如果想将指针 ptr 指向 buf 中第一个 '\0' 的地址，这里有一个技巧，我们可以不使用 for 循环，而是直接使用 ptr = buf + strlen(buf) ，就可以快速秒掉了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// lib/string.c
FILE *fmemopen(FILE *stream, void *buf, const char *mode) {
    if (strcmp(mode, "w") == 0) {
        stream->ptr = buf;
        stream->base = buf;
        stream->end = buf;
        return stream;
    }
    else if (strcmp(mode, "a") == 0) {
        stream->ptr = buf + strlen(buf);
        stream->base = buf;
        stream->end = stream->ptr;
        return stream;
    }
    else {
        return NULL;
    }
}

接下来是 fmemprintf() 函数，这个函数应该是最难的了，因为它涉及到了回调函数相关的内容，以及指针类型之间的转换。

我们要实现的 fmemprintf() 函数和 printk() 函数的主要区别在于，两个函数将内容输出到的位置是不同的，而要输出的内容本身没有区别。所以我们需要作出改动的是传入的回调函数，它控制着内容最终输出到的位置；而控制输出内容的 vprintfmt() 函数本身不需要发生改变。

我们首先来实现回调函数，这里我们仿照 printk() 的回调函数 outputk() ，将 fmemprintf() 函数的回调函数命名为 outputmem() 。

outputk() 函数接收 3 个参数，分别是 void * 类型的 data ，const char * 类型的 buf ，以及 size_t 类型的 len 。它的作用是将 buf 中的前 len 个字符输出至标准控制流。如果我们阅读 outputk() 函数的代码，就会发现其中的 data 参数完全没有被使用过，那么这里为什么会有这样一个参数呢？实际上，它是 将回调函数作为参数的函数（在这里就是 printk() 函数） 传递给回调函数的参数。这里 printk() 函数没有需要传递给 outputk() 函数的参数，所以我们可以看到 printk() 函数在调用 vprintfmt() 函数时，data 参数被填入了 NULL 。然而在我们要实现的 fmemprintf() 函数和回调函数 outputmem() 函数中，outputmem() 函数需要得到 FILE * 类型的 stream ，才能将内容输出到文件中，所以就需要 fmemprintf() 函数将 stream 传入 vprintfmt() 函数的 data 参数，作为回调函数的参数。

这里我们还需要进行一下指针类型的转换。在 outputmem() 函数中，参数 data 是 void * 类型（这里必须设置成 void * 类型，因为 vprintfmt() 函数中的 data 参数就是 void * 类型，如果需要复用 vprintfmt() 函数的话，就不能修改 data 的 void * 类型）。于是我们需要在 outputmem() 函数的开头将 void * 类型的 data 转换为 FILE * 类型，即 FILE *stream = (FILE *)data; 。接下来，我们只需要将 buf 中的前 len 个字符写入 stream->ptr 的位置，并将 stream->ptr 移动到写入后的位置就可以了：

1
2
3
4
5
6
7
8
// lib/string.c
void outputmem(void *data, const char *buf, size_t len) {
    FILE *stream = (FILE *)data;
    for (int i = 0; i < len; i++) {
        *(stream->ptr) = buf[i];
        (stream->ptr)++;
    }
}

在实现完 outputmem() 函数之后，我们就可以来实现 fmemprintf() 函数了。我们仿照 outputk() 函数，创建 va_list 类型的 ap ，使用 va_start(ap, fmt) 读取变长参数，使用 vprintfmt(outputmem, stream, fmt, ap) 解析输出的内容（这里注意将回调函数修改为 outputmem ，并在 data 参数的位置传入 stream 作为参数），使用 va_end(ap) 结束变长参数的读取。

此外，我们还要按照题目要求完成一些小的功能。例如在输出完成之后，如果 stream->ptr 大于 stream->end ，则需要将 stream->end 置为 stream->ptr 。在函数的最后，我们还需要返回输出字符的个数，所以我们需要在调用 outputmem() 函数之前保存当时 stream->ptr 的值，在调用完 outputmem() 函数之后用当前 stream->ptr 的值减去调用前 stream->ptr 的值，即可得到输出字符的个数：

1
2
3
4
5
6
7
8
9
10
11
12
// lib/string.c
int fmemprintf(FILE *stream, const char *fmt, ...) {
    char *before_ptr = stream->ptr;
    va_list ap;
    va_start(ap, fmt);
    vprintfmt(outputmem, stream, fmt, ap);
    va_end(ap);
    if (stream->ptr > stream->end) {
        stream->end = stream->ptr;
    }
    return stream->ptr - before_ptr;
}

接下来的两个函数就简单了，我们首先来实现 fseek() 函数。这个函数唯一需要注意的点就是，当我们计算出的 stream->ptr 值不在正确范围内时，我们不应该修改 stream->ptr 的值，而是应该将其恢复为原值。除此之外就没有什么难点了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// lib/string.c
int fseek(FILE *stream, long offset, int fromwhere) {
    char *after_ptr = NULL;
    if (fromwhere == SEEK_SET) {
        after_ptr = stream->base + offset;
    }
    else if (fromwhere == SEEK_CUR) {
        after_ptr = stream->ptr + offset;
    }
    else if (fromwhere == SEEK_END) {
        after_ptr = stream->end + offset;
    }
    if (after_ptr >= stream->base && after_ptr <= stream->end) {
        stream->ptr = after_ptr;
        return 0;
    }
    else {
        return -1;
    }
}

最后就是 fclose() 函数了。我们只要在 stream->end 处写入 '\0' 就可以了。不过要注意这里的 stream->end 是一个 char 型指针，所以需要先对其解引用再赋值。在考场上我忘记解引用了，被硬控了 10 分钟（笑死）：

1
2
3
4
5
// lib/string.c
int fclose(FILE *stream) {
    *(stream->end) = '\0';
    return 0;
}

Lab 2 Exam

这道题看似有点上强度，实际上强度并不是很高，只要对页表操作有一丢丢的理解，即可轻松拿下。函数声明部分我们就不说了，照题目抄即可，我们主要来谈谈如何实现 kern/pmap.c 中的 page_conditional_remove() 函数：

说实话，它都叫这个名字了，我们第一时间就应该反应到，可以仿照同文件中的 page_remove() 函数来写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// kern/pmap.c
void page_remove(Pde *pgdir, u_int asid, u_long va) {
    Pte *pte;

    /* Step 1: Get the page table entry, and check if the page table entry is valid. */
    struct Page *pp = page_lookup(pgdir, va, &pte);
    if (pp == NULL) {
      return;
    }

    /* Step 2: Decrease reference count on 'pp'. */
    page_decref(pp);

    /* Step 3: Flush TLB. */
    *pte = 0;
    tlb_invalidate(asid, va);
    return;
}

不过，我们要实现的函数和 page_remove() 函数有三点不同：一是解除映射是有条件的；二是我们要解除映射的虚拟地址由一个地址变成了一个区间；三是我们最后要返回解除映射的页面个数。我们接下来按照这三点对 page_remove() 函数进行修改：

首先，我们需要设置一个 count 变量，记录解除映射的页面个数，记得将 count 初始化为 0 ：

1
2
3
4
5
6
7
8
// kern/pmap.c
u_int page_conditional_remove(Pde *pgdir, u_int asid, u_int perm_mask, u_long begin_va, u_long end_va) {
    u_int count = 0;

    ......

    return count;
}

在上面的省略号部分，我们定义一个 for 循环，对其中的每个 va 进行解除映射的操作。这里需要我们注意的是，我们的循环变量 va 的步长应该是 PAGE_SIZE ，即 1 << 12 ，而不是 1 。这是因为我们在建立映射的时候是以页面为单位的，假设 va 能够被 PAGE_SIZE 整除，那么 [va, va + PAGE_SIZE) 的地址会被映射到同一个物理页面上，这是一次映射，而不是 PAGE_SIZE 次映射，即页面的 pp_ref 为 1 ，而不是 PAGE_SIZE 。在解除映射时，我们只需要使用 [va, va + PAGE_SIZE) 范围内的任意一个虚拟地址作为 page_remove() 函数的 va 参数，即可解除整个页面的所有映射。

另外，题目中规定了 begin_va 和 end_va 均能被 PAGE_SIZE 整除，所以我们直接以它们作为循环的起始值和终止值即可（否则就需要使用 ROUNDDOWN 宏向下取整一下了）：

1
2
3
4
5
6
7
8
// kern/pmap.c
u_int page_conditional_remove(Pde *pgdir, u_int asid, u_int perm_mask, u_long begin_va, u_long end_va) {
    u_int count = 0;
    for (u_long va = begin_va; va < end_va; va += PAGE_SIZE) {
        ......
    }
    return count;
}

接下来，我们对每个 va 进行解除映射的操作，仿照 page_remove() 函数，我们先取出 va 映射到的物理页面，并判断物理页面是否为空。这里要注意的是，我们在判断物理页面为空之后，不能直接 return ，而是要 continue 到下一个虚拟地址：

1
2
3
4
5
6
7
8
9
10
11
12
13
// kern/pmap.c
u_int page_conditional_remove(Pde *pgdir, u_int asid, u_int perm_mask, u_long begin_va, u_long end_va) {
    u_int count = 0;
    for (u_long va = begin_va; va < end_va; va += PAGE_SIZE) {
        Pte *pte;
        struct Page *pp = page_lookup(pgdir, va, &pte);
        if (pp == NULL) {
          continue;
        }
        ......
    }
    return count;
}

最后，我们判断页面的 perm 位是否满足条件，如果满足条件则解除映射。题目中给出的条件是检查页表项中是否含有 perm_mask 中的某些位。这里的页表项即为 page_lookup() 函数找到的 pte 解引用后的结果，pte 是页表项的地址，*pte 才是页表项的内容。

于是，我们将 *pte 和 perm_mask 进行按位与运算即可。题目中提到我们只需检查 PTE_D PTE_G PTE_LIBRARY PTE_COW 这 4 位即可，保险起见，我们再将结果按位与上这 4 位按位或的结果，过滤掉不需要检查的位即可。这里还是需要一些位运算功底的，不过下面的代码中给出的是最简洁的写法，为了准确性我们还可以选择一些更稳妥的写法，大家可以自由发挥~

最后的最后，不要忘了在解除映射之后将 count++ ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// kern/pmap.c
u_int page_conditional_remove(Pde *pgdir, u_int asid, u_int perm_mask, u_long begin_va, u_long end_va) {
    u_int count = 0;
    for (u_long va = begin_va; va < end_va; va += PAGE_SIZE) {
        Pte *pte;
        struct Page *pp = page_lookup(pgdir, va, &pte);
        if (pp == NULL) {
          continue;
        }
        if ((*pte) & perm_mask & (PTE_D | PTE_G | PTE_LIBRARY | PTE_COW)) {
            page_decref(pp);
            *pte = 0;
            tlb_invalidate(asid, va);
            count++;
        }
    }
    return count;
}

这样，我们就完成了 exam 的全部内容！可以说确实是有点难度，不过相比接下来这道题，那确实还是小巫见大巫了 ——

Lab 2 Extra

这道题也是相当有难度的一道题，实现的过程中会遇到许多致命的细节，稍有不慎就可能会导致满盘皆输。

首先最重要的一点就是要搞清楚题目中给出的数据结构是什么样的。其实最直观的还是题目中的那张图，一张图就足以说明很多问题了。

另外，我们还需要注意的是，和 Page 结构体的空闲链表不同，MBlock 结构体的链表不会移除已分配的 MBlock 结构体，而是根据 MBlock 结构体中的 free 字段判断其是否空闲。

我们首先来实现 malloc() 函数，跟随参考实现方案一步一步进行：

(1) 计算需要分配的 8 字节对齐的字节数。

首先，我们需要将 malloc() 函数的参数 size 向上取整至能够被 8 整除，这里可以使用课下代码中原有的 ROUND 宏：size_t realsize = ROUND(size, 8); ，当然也可以自行实现：size_t realsize = (size + 7) / 8 * 8; ，不过肯定还是使用宏更加保险一些，毕竟自己写还是有写错的风险：

1
2
3
4
5
6
7
// kern/pmap.c
void *malloc(size_t size) {
    /* Your Code Here (1/2) */
    size_t realsize = ROUND(size, 8);
    ......
}

(2) 从 0x80400000 处开始，遍历链表，直到找到剩余空间大于等于 size 的元数据。

我们可以使用课下代码中的链表宏 LIST_FOREACH(var, head, field) 来遍历链表。其中，var 是我们自定义的循环变量，类型为 struct MBlock * ；head 是指向链表头节点的指针，即 &mblock_list ；field 是链表节点中指向其它节点的指针组成的结构体，即 mb_link 。

（在考试的时候，如果你在调用接口时不知道参数怎么填，这个时候最好用的办法绝对不是去读接口的源代码，而是去模仿其它的接口调用！虽然 LIST_FOREACH 这个链表宏在课下代码中从来没有被调用过，但是其它链表宏的调用中也有 head 和 field 字段。所以这里我们就可以根据其它链表宏的调用，仿照 head 字段的 &page_free_list 填入 &mblock_list ，仿照 field 字段的 pp_link 填入 mb_link ）

接下来我们来判断当前 MBlock 的空间是否大于等于 size 。这里要注意两个细节，一是我们实际上应该与向上取整过的 realsize 进行比较；二是我们只能选中空闲的 MBlock ，而不能选中已分配的 MBlock ，所以需要检查当前 MBlock 的 free 字段是否为 1 。另外，当我们找不到符合要求的 MBlock 时，应当返回空指针 NULL 。这样我们就能够写出这部分的逻辑了：

1
2
3
4
5
6
7
8
9
10
11
12
// kern/pmap.c
void *malloc(size_t size) {
    /* Your Code Here (1/2) */
    size_t realsize = ROUND(size, 8);
    struct MBlock *var;
    LIST_FOREACH(var, &mblock_list, mb_link) {
        if (var->free == 1 && var->size >= realsize) {
            ......
        }
    }
    return NULL;
}

(3) 当需要分配的 size 小于等于剩余空间大小时：若剩余空间大小，除去分配给用户的内存空间 size，剩余大小不足分配一个新的的元数据与至少 8 字节的空闲空间，则剩余空间一齐分配给调用者；若剩余空间大小，除去分配给用户的内存空间 size，仍剩余一个元数据的空间与对应至少 8 字节的空闲空间可以使用，则在分配的数据空间 size 后，再建立新的元数据，并维护元数据。

我们首先来翻译判断条件，当前 MBlock 的剩余空间为 var->size ，除去我们要申请的空间大小 realsize ，剩余的空间大小为 var->size - realsize 。我们需要比较这个值是否大于等于一个新的 MBlock 结构体与 8 字节空间的大小。题目中已经帮我们计算好了 MBlock 结构体的大小为 24 字节，所以我们实际上只需要比较是否大于等于 32 即可。

如果 var->size - realsize 小于 32 ，我们将整个 MBlock 直接返回即可，也就是直接返回 var->ptr ，当然也可以返回 var->data ，这两者是等价的。（注意这里返回的不是 var 本身，也就是不是指向 MBlock 结构体的指针，而是指向 MBlock 结构体后面的分配空间的指针）此外，在返回之前，我们不要忘记了将当前 MBlock 的 free 字段置为 0 。

如果 var->size - realsize 大于等于 32 ，我们在进行上述操作之前，还需要在已分配的内存空间之后生成一个新的 MBlock 结构体，并将其插入链表。我们首先需要计算新结构体的位置，它位于 var->ptr 之后 realsize 个字节，于是我们有 struct MBlock *new = (struct MBlock *)(var->ptr + realsize); ，这样就计算出了新的 MBlock 结构体的地址。

（这里使用 struct MBlock *new = var + 24 + realsize; 计算是错误的，非常隐蔽的错误，你知道是为什么吗？其实这涉及到一个关于指针加法运算的知识点，你肯定会，只不过考场上一不小心就忘了。答案是因为 var 的变量类型为 struct MBlock * ，所以 var + 24 的值并不等于 var 的地址直接加上 24 ，而是等于 var 的地址加上 24 个 MBlock 结构体的大小，也就是 24 个 24 ！所以正确的做法是先将 var 转换为 void * 类型，在计算结束之后再将结果转换回 struct MBlock * 类型，也就是 struct MBlock *new = (struct MBlock *)((void *)var + 24 + realsize); ）

接下来就是修改 MBlock 结构体的相应字段了。对于新结构体 new ，它的 size 字段就等于 var->size - realsize 再减去 24 ，ptr 字段等于当前结构体的地址加上 24（如果你读懂了题目中关于柔性数组 data 的介绍，实际上我们可以直接使用 new->ptr = new->data 进行维护），free 字段当然等于 1 。此外，我们还需要修改原 MBlock 的 size 字段，将 var->size 改为 realsize 。

最后，我们将新的 MBlock 结构体插入链表中，这里我们可以直接使用链表宏 LIST_INSERT_AFTER(listelm, elm, field) 。这里的 listelm 和 elm 分别代表两个指向链表节点的指针，也就是 var 和 new ；field 则依旧是 mb_link 。这样，我们就得到了这部分的逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// kern/pmap.c
void *malloc(size_t size) {
    /* Your Code Here (1/2) */
    size_t realsize = ROUND(size, 8);
    struct MBlock *var;
    LIST_FOREACH(var, &mblock_list, mb_link) {
        if (var->free == 1 && var->size >= realsize) {
            if (var->size - realsize >= 32) {
                struct MBlock *new = (struct MBlock *)((void *)var + 24 + realsize);
                new->size = var->size - realsize - 24;
                new->ptr = (void *)(new) + 24;
                new->free = 1;
                var->size = realsize;
                LIST_INSERT_AFTER(var, new, mb_link);
            }
            var->free = 0;
            return var->ptr;
        }
    }
    return NULL;
}

后面的步骤（ return NULL 和 return var->ptr ）我们在之前就已经实现过了，这样我们就完成了 malloc() 函数！

接下来就是 free() 函数：

(1) 判断当前地址 p 是否在合理的范围内 [HEAP_BEGIN + MBLOCK_SIZE, HEAP_BEGIN + HEAP_SIZE]

这里的 HEAP_BEGIN MBLOCK_SIZE HEAP_SIZE 都是 include/malloc.h 中的宏，分别代表 0x80400000 sizeof(struct MBlock) 0x00400000 ，这里我们直接使用这几个宏即可，如果范围不对直接返回：

1
2
3
4
5
6
7
8
// kern/pmap.c
void free(void *p) {
    /* Your Code Here (2/2) */
    if (!(p >= HEAP_BEGIN + MBLOCK_SIZE && p <=  HEAP_BEGIN + HEAP_SIZE)) {
        return;
    }
    ......
}

(2) 通过当前地址 p 减去 MBLOCK_SIZE 得到 MBlock 应在位置。

这里因为 p 是 void * 类型，所以不会出现之前提过的指针加减法问题，不过要注意在减完之后将类型转换为 struct MBlock * ：

1
2
3
4
5
6
7
8
9
// kern/pmap.c
void free(void *p) {
    /* Your Code Here (2/2) */
    if (!(p >= HEAP_BEGIN + MBLOCK_SIZE && p <=  HEAP_BEGIN + HEAP_SIZE)) {
        return;
    }
    struct MBlock *nowp = (struct MBlock *)(p - MBLOCK_SIZE);
    ......
}

(3) 判断当前 MBlock 是否合法，可以通过元数据中指向首地址的指针 ptr == data 判断（保证测试中可以使用）。

这种判断方法实际上并不保险，不过题目中保证了一定可以使用，那就按题目说的做好了：

1
2
3
4
5
6
7
8
9
10
11
12
// kern/pmap.c
void free(void *p) {
    /* Your Code Here (2/2) */
    if (!(p >= HEAP_BEGIN + MBLOCK_SIZE && p <=  HEAP_BEGIN + HEAP_SIZE)) {
        return;
    }
    struct MBlock *nowp = (struct MBlock *)(p - MBLOCK_SIZE);
    if (nowp->ptr != nowp->data) {
        return;
    }
    ......
}

(4) 当需要释放空闲区间，且相邻存在空闲区间时：若后一个区间空闲，将后元数据清除，空间大小加到当前区间元数据中，修改指针位置，设为空闲；若前一个区间空闲，将当前元数据清除，空间大小加到前区间元数据中，修改指针位置。

这一步应该是最核心的步骤了。需要注意的是，即使当前的 MBlock 和前一个 MBlock 合并了，我们也需要将当前 MBlock 的 free 字段置为 1 。我不知道为什么，但是如果不这样做就无法通过测试，非常奇怪。

接下来，我们求出当前 MBlock 的前一个 MBlock 和后一个 MBlock ，我们分别可以用 MBLOCK_PREV(elm, field) 和 LIST_NEXT(elm, field) 两个链表宏分别实现。这里的 elm 即为指向当前 MBlock 结构体的指针 nowp ，field 依旧是 mb_link 。

求出前一个和后一个 MBlock 之后，我们就可以进行合并了。我们先判断是否能够与后一个 MBlock 合并，在判断 nextp->free 是否为 1 之前，我们还需要考虑 nextp 是否存在，因为当前的 MBlock 有可能是链表中的最后一个 MBlock 。如果满足条件的话，我们需要调整 nowp->size ，加上后一个 MBlock 结构体的大小 24 ，以及后一个 MBlock 的空闲空间大小 nextp->size 。接下来，我们使用 LIST_REMOVE(elm, field) 链表宏移除当前 MBlock 就可以了。

判断是否能够与前一个 MBlock 合并基本上是相同的，这里就不赘述了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// kern/pmap.c
void free(void *p) {
    /* Your Code Here (2/2) */
    if (!(p >= HEAP_BEGIN + MBLOCK_SIZE && p <=  HEAP_BEGIN + HEAP_SIZE)) {
        return;
    }
    struct MBlock *nowp = (struct MBlock *)(p - MBLOCK_SIZE);
    if (nowp->ptr != nowp->data) {
        return;
    }
    nowp->free = 1;
    struct MBlock *lastp = MBLOCK_PREV(nowp, mb_link);
    struct MBlock *nextp = LIST_NEXT(nowp, mb_link);
    if (nextp != NULL && nextp->free == 1) {
        nowp->size = nowp->size + 24 + nextp->size;
        LIST_REMOVE(nextp, mb_link);
    }
    if (lastp != NULL && lastp->free == 1) {
        lastp->size = lastp->size + 24 + nowp->size;
        LIST_REMOVE(nowp, mb_link);
    }
}

到了这里，前后区间均占用的情况我们其实已经实现完了，至此我们就完成了本次 extra ！这次 extra 确实还是有些困难的，主要是细节比较多，已喜提 0 分（悲），希望大家能够得到比我更高的分数。

Lab 3 Exam

题目中已经帮我们实现好了全部的定义，将题目中给出的代码复制好后，我们就只需要实现两个内容：一是仿照 env_create() 函数补全 env_create_edf() 函数；二是根据代码中的注释修改 schedule() 函数。

我们首先进行第一步，将 env_create() 函数中为新进程的属性赋值部分替换为题目中给出的内容，再将插入 env_sched_list 队列改为插入 env_edf_sched_list 队列即可（这里需要注意两个队列的类型是不同的，插入时要改用 LIST_INSERT_HEAD ）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// kern/env.c
struct Env *env_create_edf(const void *binary, size_t size, int runtime, int period) {
    struct Env *e;

    env_alloc(&e, 0);

    e->env_edf_runtime = runtime;
    e->env_edf_period = period;
    e->env_period_deadline = 0; // 初始化为 0，使进程在首次调用 schedule 函数时触发条件判断，进入首个运行周期
    e->env_status = ENV_RUNNABLE;

    load_icode(e, binary, size);
    LIST_INSERT_HEAD(&env_edf_sched_list, e, env_edf_sched_link);

    return e; 
}

接下来就是本次 exam 的重难点，即修改 schedule() 函数。在动手操作之前，请一定确保自己完全了解了题目中的调度规则。如果有疑惑的话，可以参考一下题目描述中的“示例”一节，我个人觉得这一节的讲解是最清楚的。

接下来我们跟着注释一步一步完成代码：

(1) 遍历 env_edf_sched_list，如果进程进入了新的运行周期（可通过 clock == env_period_deadline 判断），则更新 env_period_deadline，并将 env_runtime_left 设置为 env_edf_runtime。

关于如何更新 env_period_deadline ，从题目描述的示例可以总结出，env_period_deadline 是 env_edf_period 的倍数，每当进程到达截止时间时，将截止时间再加上一倍即可：

1
2
3
4
5
6
7
8
9
10
// kern/sched.c
struct Env *env; // 循环变量

LIST_FOREACH (env, &env_edf_sched_list, env_edf_sched_link) {
    // 这里可以根据提示，使用 LIST_FOREACH 来循环
    if (clock == env->env_period_deadline) {
        env->env_period_deadline += env->env_edf_period;
        env->env_runtime_left = env->env_edf_runtime;
    }
}

(2) 遍历 env_edf_sched_list，选取 env_runtime_left 大于 0 且 env_period_deadline 最小的进程调度（若相同，则选择 env_id 最小的进程）。如果不存在这样的进程，则不进行调度。

首先，我们需要通过遍历找出需要调度的 edf 进程。下一步，我们还需要判断进程是否存在。若存在，我们需要调用 env_run() 来运行该进程，同时注意维护 env_runtime_left 变量的值，减去一个时间片：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// kern/sched.c
u_int min = -1; // 截止时间最小的进程的截止时间
struct Env *wheremin = NULL; // 截止时间最小的进程

LIST_FOREACH (env, &env_edf_sched_list, env_edf_sched_link) {
    if (env->env_runtime_left > 0) { // 这里注意判断当前进程是否执行完
        if (min == -1) {
            min = env->env_period_deadline;
            wheremin = env;
        }
        else {
            if (env->env_period_deadline < min || (env->env_period_deadline == min && env->env_id < wheremin->env_id)) {
                min = env->env_period_deadline;
                wheremin = env;
            }
        }
    }
}

if (wheremin != NULL && wheremin->env_status == ENV_RUNNABLE) {
    // 不是很确定是否要判断 status 是否为 ENV_RUNNABLE ，感觉可能不太用
    wheremin->env_runtime_left--;
    env_run(wheremin);
}

(3) 使用课下实现的 RR 算法调度 env_sched_list 中的进程。

到这一步有些同学就看不太懂了，不知道有什么可改的地方，其实有两处是要修改的，当然这就需要我们对本题的调度规则有比较清晰的理解了。

第一处，不知道你有没有怀疑过注释 (3) 的表述，根据上面的规则和示例，显然只有在 edf 队列中没有找到要调度的 edf 进程时，才会从 RR 队列中选取进程调度，也就是说 (3) 中的调度不是无条件的，这就需要我们将整个 RR 调度的逻辑放在上一步的分支判断中。

第二处，根据代码中的注释和后文的提示都可以看出，我们需要将 RR 调度中的 e 由当前进程 curenv 改为上次执行的 RR 进程。这里我们需要新开一个 static 变量 struct Env *lastRRenv ，每次进行 RR 调度时将当前进程存储进去即可：

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
// kern/sched.c
if (wheremin != NULL && wheremin->env_status == ENV_RUNNABLE) {
    wheremin->env_runtime_left--;
    env_run(wheremin);
}
else {
    static int count = 0;
    static struct Env *lastRRenv = NULL; 
    // 这里必须为静态变量 static ，否则每次调用 schedule() 函数时 lastRRenv 都会被重新定义
    // 仿照 curenv 的定义，初值赋为 NULL
    // struct Env *e = curenv;
    struct Env *e = lastRRenv; // 删去 e 的原定义，改为 lastRRenv

    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);
        }
        e = TAILQ_FIRST(&env_sched_list);
        lastRRenv = e; // 此时新的 e 已经确定，更新 lastRRenv 的值
        if (e == NULL) {
            panic("schedule: no runnable envs\n");
        }
        count = e->env_pri;
    }
    count--;
    env_run(e);
}

到这里我们就将本次 exam 全部解决了！总的来说，本次 exam 还是非常吃细节的，只有将题目中的调度规则完全搞清楚，并且在做题时不断思考实现细节，时刻记得维护属性值，才能顺利通过测试。

Lab 3 Extra

事实上，Lab 3 extra 的题目虽然总是异常处理，但和 CO P7 的关系真的不是特别大，毕竟还要照顾一下 CO 没学过异常的同学们。其实只要对 MIPS 指令结构和作用有稍微的了解，就足以拿下这道问题了。

异常的注册在提示部分就已经全部给出了，我们只需要实现 do_adel() 和 do_ades() 两个函数即可。其实只要通读一遍题目，稍作思考就可以发现，这两个函数是一模一样的，除了最后的输出以外没有任何区别。

题目中没有给出具体的实现步骤，现在我们就来拆解一下函数的实现流程：首先我们需要取出当前出现异常的指令，然后对指令进行修改，最后将指令写回原来的位置。接下来我们一步一步实现上面的流程：

第一步其实是最难的一步，很多没看过往年博客的同学直接被硬控到死，到最后家门都没出去。而机智如我发现往年总这么考，直接把这段代码抄在纸上，考试时无脑爆抄，直接助我拿下全考场手刹，所以同学们知道该怎么做了吧（笑）
↑以防大家不知道，再次提醒一下，这门课是开卷考试，可以携带纸质资料入场，下回记得带~

题目的提示部分提过，我们从 tf->cp0_epc 中获取到的地址并不是存放当前指令的真实地址，而是它的虚拟地址。我们需要通过一顿猛如虎的操作将其转化为物理地址，才能将当前指令取出。如果你不能理解下面的代码，记住抄下来就对了！祖传代码，屡试不爽：

1
2
3
4
5
6
7
// kern/traps.c
u_int badva = tf->cp0_epc; // 获取虚拟地址
Pde *pgdir = curenv->env_pgdir; // 获取页目录的基地址
struct Page *p = page_lookup(pgdir, badva, NULL); // 查找虚拟地址所在的页
u_int badpa = page2pa(p) + (badva & 0xfff); // 将页转换为物理地址（不含页内偏移），再加上虚拟地址中的页内偏移部分，构成完整物理地址
u_int *badk0va = 0x80000000 | badpa; // 转换为 kseg0 的虚拟地址（kseg0 起始地址为 0x80000000）
u_int code = *badk0va; // code 的值即为 32 位 MIPS 指令的内容

接下来，我们就需要按照题目中的要求来更改指令了。这一步比较简单，但也有几个需要注意的地方：

首先我们需要注意，这里的修改绝不是直接将当前指令的 offset 低 2 位置 0 。回忆 lw 和 sw 指令的用法，我们可以发现，需要能被 4 整除的并不是最后的 offset 值，而是 GPR[base] + offset 的结果。所以我们需要先计算出这个值，然后根据它对 4 取模的结果调整 offset 。

于是就出现了另外一个问题，就是在计算 GPR[base] 的时候，该如何从寄存器中取值。其实只需要用一步 int gpr_base = (int)tf->regs[base]; 即可取到，但这一步或许也难住了许多英雄汉，属实可惜。

最后就是要时刻注意其中不断变化的数据长度和有无符号问题了。整个代码中涉及到 int u_int signed short 类型的反复转换，虽然写法多种多样（比如我就是乱写的，我也不知道哪些有用哪些没用），但还是要尽量避免类型的隐式转换，让整个计算过程都在我们的可控范围之内。同时也一定要格外注意长度转换带来的有无符号拓展问题，确保 offset 在计算时将 signed short 类型转换为 int 类型：

1
2
3
4
5
6
7
8
9
10
11
// kern/traps.c
u_int base = ((code & 0x03e00000) >> 21); // 取出指令的 21 ~ 25 位作为寄存器的编号
u_int u_offset = (code & 0x0000ffff); // 取出指令的 0 ~ 15 位作为偏移值

int gpr_base = (int)tf->regs[base]; // 从寄存器中取出基地址值
signed short offset = (signed short)u_offset; // 我也不知道这步有没有用，但总之这么写是对的
int now_res = gpr_base + (int)offset; // 算出 GPR[base] + offset 的值
int fix_res = (now_res & ~0x3); // 将上述值的低 2 位置 0
int sub = now_res - fix_res; // 算出置 0 前后的差值
offset = offset - (signed short)sub; // 在 offset 上减去上述差值
code = ((code & 0xffff0000) | ((u_int)offset & 0x0000ffff)); // 将 offset 放回原来的位置

最后一步就是把修复好的指令放回原位置了，因为我们刚才已经算出指令在 kseg0 的虚拟地址了，怎么把它取出来就怎么把它放回去即可。最后别忘了按照题目要求输出：

1
2
3
4
5
6
7
8
// kern/tras.c
*badk0va = code;

// in do_adel():
printk("AdEL handled, new imm is : %04x\n", code & 0xffff);

// in do_ades():
printk("AdES handled, new imm is : %04x\n", code & 0xffff);

最后还是总结一下，毕竟是 extra ，难度还是有一些的，我觉得涉及到地址转换的题目都还挺难的。不过把上面那段八股抄下来直接可秒，后面难度就不太大了，可能涉及到一些位运算的知识，不过我相信大家都能 hold 住。总而言之，多看看往年题，多看看往届博客，好处还是大大的有。大家认真准备，千万不要裸考口牙！

Lab 4 Exam

这道题主要考察的是如何添加新的 syscall ，这也是每年必出的经典考点。接下来，我们根据“实现参考”部分的思路走一遍整个流程：

(1) 在 include/syscall.h 中新增一个枚举值 SYS_get_ppid，注意，需要将它放在 MAX_SYSNO 之前！

这一步没什么好说的，我们只需要将 SYS_get_ppid 放在 MAX_SYSNO 之前的任意位置即可：

1
2
3
4
5
6
7
8
9
// include/syscall.h
enum {
    SYS_putchar,
    SYS_print_cons,
    SYS_getenvid,
    ......
    SYS_get_ppid,
    MAX_SYSNO,
};

(2) 在 kern/syscall_all.c 中增加一个系统调用实现 int sys_get_ppid(void) { ... }，并将其添加到 syscall_table 中。注意，实现函数的位置应该在系统调用表之前。

在这一步，我们首先填写 syscall_table ，其中数组下标为我们刚才填入的枚举值 SYS_get_ppid ，数组值为该文件中实现 syscall 的函数名 sys_get_ppid 。

接下来，我们来完成 sys_get_ppid() 函数。kenn/syscall_all.c 中 sys 开头的函数负责 syscall 的最终实现，所以没有固定的格式，需要我们根据题目要求自行编写。题目中要求我们返回当前进程的父进程的 env_id ，非常幸运的是，这个内容正好就写在了当前进程的 PCB 中，于是我们只需要调用 curenv->env_parent_id ，即可得到我们想要的结果。

顺带一提，题目中提到了如果当前进程没有父进程，需要返回 0 ，然而实际上在我们的操作系统中，当一个进程没有父进程时，它的 env_parent_id 字段本身就是 0 ，所以不需要特判。不过如果题目中规定没有父进程的时候需要返回一些其它的值，我们也需要会使用 env_parent_id 字段是否为 0 进行判断。（不用担心父进程的 env_id 刚好等于 0 的情况，如果你研究过代码，就会发现一个进程的 env_id 不可能是 0 ！）

1
2
3
4
5
6
7
8
9
10
11
// kern/syscall_all.c
int sys_get_ppid(void) {
    return curenv->env_parent_id;
}

void *syscall_table[MAX_SYSNO] = {
    [SYS_putchar] = sys_putchar,
    [SYS_print_cons] = sys_print_cons,
    ......
    [SYS_get_ppid] = sys_get_ppid,
};

(3) 在 user/include/lib.h 中增加一个用户态的系统调用声明：int syscall_get_parent_envid(void);。

这一步也是简单到爆，直接将 int syscall_get_parent_envid(void); 写进文件中就可以了，这里就不贴代码了。

(4) 在 user/lib/syscall_lib.c 中增加它的具体实现，你可以通过 msyscall 发起系统调用。

我们可以仿照 user/lib/syscall_lib.c 中的其它函数来实现 syscall_get_parent_envid() 函数。这个函数也是固定套路了，我们只需要写上一行 return 语句，返回 msyscall() 函数的执行结果。其中，msyscall() 的第一个参数为之前填入的枚举值，接下来的参数为 kern/syscall_all.c 中 sys 开头的函数所需要的参数。这里 sys_get_ppid() 函数不需要参数，所以我们只需要向 msyscall() 函数传入一个枚举值 SYS_get_ppid 即可：

1
2
3
4
// user/lib/syscall_lib.c
int syscall_get_parent_envid(void) {
    return msyscall(SYS_get_ppid);
}

这样，我们就完成了 exam 的第一部分，练习了如何添加一个新的 syscall ！接下来我们来挑战一下非常简单的第二部分：

在这一部分，我们需要实现一个新的页表项标志位 PTE_PROTECT 。同时，在 fork 子进程，将子进程的虚拟地址与物理页面进行映射时，我们不应该映射具有 PTE_PROTECT 项的物理页面。

听起来还是比较复杂的，不过我们只要跟着“实现参考”中的思路走，就会发现这其实是一个非常简单的问题！首先，我们需要在 include/mmu.h 中添加一行定义 #define PTE_PROTECT 0x0004 。这里直接添加即可，我们来看下一步。

接下来的提示可以说是差点把答案写脸上了，我们需要在 user/lib/fork.c 中 duppage() 函数的 Step 1 和 Step 2 之间检查当前页面是否具有 PTE_PROTECT 标志位，如果具有则直接结束函数。于是我们直接使用 Step 1 中计算出的 perm ，与 PTE_PROTECT 进行按位与，检查该结果是否为 0 即可：

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
// user/lib/fork.c
static void duppage(u_int envid, u_int vpn) {
    int r;
    u_int addr;
    u_int perm;

    /* Step 1: Get the permission of the page. */
    /* Hint: Use 'vpt' to find the page table entry. */
    /* Exercise 4.10: Your code here. (1/2) */

    addr = vpn << PGSHIFT;
    perm = vpt[vpn] & 0xfff;

    if (perm & PTE_PROTECT) {
      return;
    }

    /* Step 2: If the page is writable, and not shared with children, and not marked as COW yet,
    * then map it as copy-on-write, both in the parent (0) and the child (envid). */
    /* Hint: The page should be first mapped to the child before remapped in the parent. (Why?)
    */
    /* Exercise 4.10: Your code here. (2/2) */

    ......
}

不过说实话，即使是这么简单的第二部分，我还是被硬控了好一阵，因为我一开始把判断条件写成了这样：if (perm & PTE_PROTECT != 0) 。发现哪里有问题了吗？答案是在 C 语言中，!= 的运算优先级要高于 & ，于是整个就全错了！大家千万补药在考场上犯这种错误口牙！

Lab 4 Extra

这道题目看起来还是非常仁慈的，已经给出了完整的 syscall 的实现过程，我们只需要实现内核态中的 4 个函数即可。

首先我们来快速完成一下 user/lib/syscall_lib.c 中的函数封装，我们只需要返回正确的 msyscall() 函数调用即可。仿照该文件中的其它函数，我们在 msyscall() 函数的第一个参数中，填入每个 syscall 在 kern/syscall_all.c 的 syscall_table 中对应的下标；接下来，我们再向 msyscall() 函数传递一些参数，作为 kern/syscall_all.c 中 sys 开头的函数的参数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// user/lib/syscall_lib.c
int syscall_shm_new(u_int npage) {
    // Lab4-Extra: Your code here. (1/8)
    return msyscall(SYS_shm_new, npage);
}

int syscall_shm_bind(int key, u_int va, u_int perm) {
    // Lab4-Extra: Your code here. (2/8)
    return msyscall(SYS_shm_bind, key, va, perm);
}

int syscall_shm_unbind(int key, u_int va) {
    // Lab4-Extra: Your code here. (3/8)
    return msyscall(SYS_shm_unbind, key, va);
}

int syscall_shm_free(int key) {
    // Lab4-Extra: Your code here. (4/8)
    return msyscall(SYS_shm_free, key);
}

接下来就是实现 4 个内核态函数的部分了，这里我们千万不要被题目中的 Shm 结构体给唬住了，我们只要观察 Shm 结构体的属性，就会发现 Shm 结构体只不过是装着几个物理页面的容器，我们只需要对这些物理页面进行申请页面、添加映射、解除映射、释放页面这四个操作即可。这些操作在 kern/pmap.c 中都给出了相应的函数，就看我们能否调用正确了！

话虽如此，实际上要想做对这道题还是比较有难度的，因为它和一般的页面分配流程不太一样，你发现哪里有问题了吗？关键就在于释放页面这一步。在这道题中，我们需要通过调用 sys_shm_free() 函数实现手动释放页面，这和 kern/pmap.c 中原有函数的设计是冲突的。

在原有的设计中，我们在使用 page_insert() 函数添加映射时会使物理页面的 pp_ref 字段增加 1 ，使用 page_remove() 函数解除映射时会通过调用 page_decref() 函数使物理页面的 pp_ref 字段减少 1 。在 page_decref() 函数中，当 pp_ref 减少到 0 时，会自动调用 page_free() 函数将页面释放掉，这样就实现了页面的自动释放。

而在本道题中，对于 Shm 结构体中的物理页面，即使所有的映射都被解除，我们也不应该释放这些页面，而是应该保证在此之后依然能够对相同的页面进行映射。那么我们该如何在不改变原有函数的情况下实现这样的操作呢？实际上题目中已经给出了提示：你可以通过在创建共享内存时，增加页面的 pp_ref 记录，并在销毁共享内存时使用 page_decref() 函数释放页面。

也就是说，我们在使用 sys_shm_new() 函数申请页面的时候，就将每个页面的 pp_ref++ ，这样即使所有的映射都被解除，页面的 pp_ref 依然有 1 ，不会触发自动释放；而我们在 sys_shm_free() 函数中，只需要调用一次 page_decref() 函数，即可将页面的 pp_ref 减少至 0 ，并且自动释放页面。非常巧妙的写法！

解决了最关键的问题之后，我们就不难完成这道题了。首先是 sys_shm_new() 函数。我们首先遍历所有的 Shm 结构体，直到找到一个 open 字段为 0 的结构体；如果没有找到，则返回 -E_SHM_INVALID 。接下来，我们使用 page_alloc() 函数申请 npage 个页面，将其写入当前 Shm 结构体的 pages 字段中，并将页面的 pp_ref++ 。如果页面申请失败，即 page_alloc() 函数的返回值小于 0 ，那么我们就需要将之前所有已申请的页面释放掉，此时只需要对之前的每个页面调用 decref() 函数，并将其从 Shm 结构体的 pages 字段中删除即可。最后，我们维护当前 Shm 结构体的 npage 和 open 字段，这样就完成了 sys_shm_new() 函数：

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
// kern/syscall_all.c
int sys_shm_new(u_int npage) {
    if (npage == 0 || npage > N_SHM_PAGE) {
        return -E_SHM_INVALID;
    }

    // Lab4-Extra: Your code here. (5/8)
    int whichShm = -1;
    for (int i = 0; i < N_SHM; i++) {
        if (shm_pool[i].open == 0) {
            whichShm = i;
            break;
        }
    }
    if (whichShm == -1) {
        return -E_SHM_INVALID;
    }

    for (int i = 0; i < npage; i++) {
        struct Page *p;
        int r = page_alloc(&p);
        if (r != 0) {
            for (int j = 0; j < i; j++) {
                struct Page *pp = shm_pool[whichShm].pages[j];
                page_decref(pp);
                shm_pool[whichShm].pages[j] = NULL;
            }
            return r;
        }
        p->pp_ref++;
        shm_pool[whichShm].pages[i] = p;
    }

    shm_pool[whichShm].npage = npage;
    shm_pool[whichShm].open = 1;

    return whichShm;
}

接下来是 sys_shm_bind() 函数。我们首先检查 shm_pool[key] 的 open 字段是否为 1 ，如果为 0 则返回 -E_SHM_NOT_OPEN 。接下来，我们使用 page_insert() 函数，将从 va 开始连续 shm_pool[key].npage 个页面的虚拟地址分别映射到 shm_pool[key].pages 中的前 shm_pool[key].npage 个页面上：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// kern/syscall_all.c
int sys_shm_bind(int key, u_int va, u_int perm) {
    if (key < 0 || key >= N_SHM) {
        return -E_SHM_INVALID;
    }

    // Lab4-Extra: Your code here. (6/8)
    if (shm_pool[key].open == 0) {
        return -E_SHM_NOT_OPEN;
    }

    for (int i = 0; i < shm_pool[key].npage; i++) {
        u_int nowva = va + i * PAGE_SIZE;
        page_insert(curenv->env_pgdir, curenv->env_asid, shm_pool[key].pages[i], nowva, perm);
    }

    return 0;
}

sys_shm_unbind() 函数也是同样的操作，这一次我们使用 page_remove() 函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// kern/syscall_all.c
int sys_shm_unbind(int key, u_int va) {
    if (key < 0 || key >= N_SHM) {
        return -E_SHM_INVALID;
    }

    // Lab4-Extra: Your code here. (7/8)    
    if (shm_pool[key].open == 0) {
        return -E_SHM_NOT_OPEN;
    }

    for (int i = 0; i < shm_pool[key].npage; i++) {
        u_int nowva = va + i * PAGE_SIZE;
        page_remove(curenv->env_pgdir, curenv->env_asid, nowva);
    }

    return 0;
}

最后是 sys_shm_free() 函数，我们同样需要检查 shm_pool[key] 的 open 字段，并且需要将 open 字段置为 0 ，这样才能保证当前的 Shm 结构体能够被重新分配。接下来，我们对 shm_pool[key].pages 中的 shm_pool[key].npage 个页面，使用 page_decref() 函数进行释放，并将这些页面从 shm_pool[key].pages 中移除：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// kern/syscall_all.c
int sys_shm_free(int key) {
    if (key < 0 || key >= N_SHM) {
        return -E_SHM_INVALID;
    }

    // Lab4-Extra: Your code here. (8/8)
    if (shm_pool[key].open == 0) {
        return -E_SHM_NOT_OPEN;
    }

    shm_pool[key].open = 0;
    for (int i = 0; i < shm_pool[key].npage; i++) {
        struct Page *p = shm_pool[key].pages[i];
        // printk("%d\n", pp->pp_ref);
        page_decref(p);
        shm_pool[key].pages[i] = NULL;
    }

    return 0;
}

这样我们就完成了整道问题！实际上，如果能够想明白在申请页面和释放页面是分别进行 pp_ref++ 和 pp_ref-- ，那这道题就没有什么难度了。然而在考场上我硬是研究了好久，一是那个时候确实对代码不够熟悉，二是没有仔细看题目中的提示。实际上题目中已经明晃晃地给出了解决方案，所以千万别看题干长就不读了，救赎之道，就在其中！

Lab 5 Exam

文件系统服务的添加流程还是非常复杂的，虽然 exam 中已经给出了全部流程，将题目中给的代码复制一下即可，但 extra 就不会给出太详细的流程了，建议大家还是对照着题目中“实现思路”一节好好捋顺一下整个流程，对以后写挑战性任务也很有帮助。

将题目中的代码复制完成之后，我们需要完成的就只剩下 fs/fs.c 中的 find_files() 和 traverse_file() 两个函数了。

首先我们来完成 find_files() 函数，需要调用 walk_path() 函数找到路径名 path 对应的文件，这就需要我们充分了解 walk_path() 函数的构成。

walk_path() 函数定义为 int walk_path(char *path, struct File **pdir, struct File **pfile, char *lastelem) ，其中 char *path 为要寻找的文件的路径，其余三个参数用来存储返回值。若成功找到文件，则 struct File **pdir 为该文件所在的文件夹，struct File **pfile 为该文件本身；若未成功找到文件，但找到了该文件所在的文件夹，则 struct File **pdir 为该文件所在的文件夹， char *lastelem 为该文件的名称。除成功找到文件函数返回 0 以外，其它未找到文件的情况函数均返回负值错误码。

我们现在可以发现，在 find_files() 函数中调用 walk_path() 函数时，是完全用不到第二和第四个参数的，只需要保证在 path 对应的文件存在的情况下能够将文件本身取出就可以了。当然，为了防止访问空指针的情况，我们还是在这些参数的位置塞一些东西进去为好，虽然我们拿到这些数据以后也会转手把它们扔掉。

最后按照题目中定义调用 traverse_file() 函数即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// fs/fs.c
int find_files(const char *path, const char *name, struct Find_res *res) {
    struct File *file = NULL;
    // Lab5-Exam: Your code here. (1/2)
    struct File *pdir = NULL; // actually no use
    char nname[MAXNAMELEN]; // actually no use
    int r = walk_path(path, &pdir, &file, nname); // 只需把 file 取出即可
    if (r < 0) {
        return r;
    }
    // Lab5-Exam: Your code here. (2/2)
    traverse_file(path, file, name, res); // 按定义调用 traverse_file() 函数
    return 0;
}

接下来我们来完成 traverse_file() 函数，根据注释一步一步完成：

1. 检查路径长度是否符合要求，如不符合，直接返回

根据注释提示，若 path 的长度为零或不小于最大路径长度，则返回 -E_BAD_PATH 错误码，使用 strlen() 函数即可：

1
2
3
4
5
// fs/fs.c
if (strlen(path) == 0 || strlen(path) >= MAXPATHLEN /* path 的长度为零或不小于最大路径长度*/) {
    /*返回*/
    return -E_BAD_PATH;
}

2. 比较当前文件名是否等于 name，如果相等则更改 res

观察 res 的结构，我们知道 int 型变量 res->count 存储着查找到的文件的总数量，而字符串数组 res->file_path[] 存储着每个查找到的文件的路径。所以只需要更新这两个变量即可：

1
2
3
4
5
6
7
// fs/fs.c
if (!strcmp(file->f_name, name) /*file 的名字等于 name*/) {
    /*增加 res->count*/
    /*添加 res 的路径*/
    strcpy(res->file_path[res->count], path);
    res->count++;
}

3. 把 path 和 name 拼接起来得到下一层文件路径，注意结尾的 '\0'
提示：我们没有实现 strcat 工具函数，你可以用 strcpy 实现拼接

这一步看似十分简单，实则却暗藏玄机。就因为这一步，我在考场上被硬控了 70 分钟，甚至有好多同学直接被硬控两个半小时（是的，这次考试延时了半小时，也是这一届唯一一次 OS 上机延时），最后连 exam 都没做上。

本质原因其实是：我们在拼接的时候并不知道 path 的结尾到底有没有 / ！

你或许会问，题目中不是已经保证了 path 均以 / 结尾吗？实际上，traverse_file() 是一个递归函数，这里 path 的值不仅可能是最初输入的 path ，还可能是其中任意一个文件夹的路径，所以无法保证 path 的结尾一定有 / 。

为此，在拼接的时候，我们需要检查当前 path 的结尾是不是 / 。如果不是的话，就需要在当前 path 的结尾补一个 / ：

1
2
3
4
5
6
7
8
9
10
11
// fs/fs.c
strcpy(curpath, path);
int curlen = strlen(curpath);
// 如果 path 不以 '/' 结尾，在后面加一个 '/'
if (curpath[curlen - 1] != '/') {
    curpath[curlen] = '/';
    curlen++; // 别忘了 len++
}
strcpy(curpath + curlen, f->f_name);
int flen = strlen(f->f_name);
curpath[curlen + flen] = '\0'; // 别忘了最后加 '\0'

4. 递归调用 traverse_file 函数

最后按照定义递归调用 traverse_file() 函数，这道题就全部做完了：

1
2
// fs/fs.c
traverse_file(curpath, f, name, res);

还是总结一下吧，这场 exam 对我来说实在是一场苦战，导致最后也没有太多时间做 extra 了，即使续费了半个小时也还是没写完，实在是太痛苦了。考场上确实很容易钻牛角尖，在高压状况下大脑很容易宕机，还是祝愿各位能够保持一个稳定平和的心态，以冷静的头脑和灵活的思维面对层出不穷的突发状况。

Lab 5 Extra

可怜的贾爹因为这道题让人唠一辈子，其实这个题或许真的没有大家想象中那么难，除了题量大了点以外真没啥毛病，只要是认真研读了 Lab 5 的代码，都大有做上的希望。

题目就不带大家重新读了，简单来说，除了题目中已经完全给出的代码，我们还需要完成 fs/serv.c 中的 serve_key_set() serve_key_unset() serve_key_isset() 3 个函数，user/lib/fsipc.c 中的 fsipc_key_set() fsipc_key_unset() fsipc_key_isset() 3 个函数，user/lib/file.c 中的 fskey_set() fskey_unset() fskey_isset() 3 个函数，以及修改 fs/serv.c 中的 serve_map() serve_close() 2 个函数。不过不要太害怕，在这 11 个函数中，有 5 个函数都只需要一行就可以解决，当然这属于是未卜先知了，我们下面正式开始解题：

首先是题目中的第 4 步，我们需要根据注释中的提示，完成 fs/serv.c 中的 3 个 serv 函数。fs/serv.c 中有两个全局变量，分别是 int 类型的 encrypt_key_set 和 unsigned char[BLOCK_SIZE] 类型的 encrypt_key 。encrypt_key_set 用于判断密钥是否加载到了缓存中，或者说当前密钥是否可用。根据题目中的定义，当密钥加载到缓存中时，我们需要返回 1 ，否则返回 0 ，于是我们在两种情况下将 encrypt_key_set 分别置为 1 或 0 即可。encrypt_key 记录着密钥的内容，大小为一个磁盘块。对于每个需要加密或解密的磁盘块，我们都将其与 encrypt_key 按位异或，即可完成加密或解密。

我们首先来看 serve_key_set() 函数。我们首先需要判断密钥是否已加载，只需要判断 encrypt_key_set 是否为 1 即可。这里需要注意的是返回值的方式，我们不能直接使用 return 语句，因为我们要将返回值传递给用户进程，所以需要使用 ipc_send() 函数来返回。ipc_send() 函数可以返回一个值和一个页面，在整个这道题中，我们都不涉及到返回页面，只需要返回一个值即可，此时我们使用 ipc_send(envid, -E_BAD_KEY, 0, 0) ，即可将 -E_BAD_KEY 返回到 envid 对应的进程中，ipc_send() 后面的两个参数置 0 即可。在使用 ipc_send() 函数返回之后，切记要使用 return; 直接返回，否则会继续往下执行。

接下来我们使用 open_lookup() 函数找到对应的 Open 结构体，既然已经给出要使用的函数了，那就比较简单了。我们直接向 open_lookup() 函数输入 envid 和 fileid ，即可得到与 fileid 对应的 Open 结构体。或许你会有疑问，fileid 何时来的，实际上，只需要看一下参数中的请求 rq 的结构，就可以发现这个结构体中唯一包含的就是 rq_fileid 字段，代表着密钥文件的 fileid 。

接下来，我们需要对刚才得到的密钥文件的 Open 结构体进行检查，检查文件大小是否大于 2 个磁盘块，以及第一个磁盘块中的第一个字是否为 FS_MAGIC 。首先是文件大小，Open 结构体中有一个 struct File * 类型的 o_file 字段，指向该文件的文件控制块；文件控制块里又有一个 uint32_t 类型的 f_size 字段，表示该文件的大小。接下来是文件的第一个磁盘块，我们根据注释中的提示，使用 fs/fs.c 中的 file_get_block() 函数，输入文件的文件控制块 f 和磁盘块序号 filebno（这里注意第一个磁盘块的序号是 0 ），即可将对应的磁盘块读出到块缓存中，返回的 *blk 即为该磁盘块的虚拟地址。在得到了第一个磁盘块的虚拟地址之后，我们只需要将 void * 类型的 blk 强制转换为 u_int * 类型（其实 int * 类型也可以，无所谓），再使用 blk[0] 即可读取出该地址下的第一个字，与 FS_MAGIC 这个魔数进行比较即可。

接下来我们如法炮制，读取出密钥文件中的第二个磁盘块（注意序号是 1 ），将该磁盘块中的内容复制到 encrypt_key 中，这里可以使用 for 循环，也可以使用 memcpy() 函数。最后，我们将当前状态标记为已加载密钥，即将 encrypt_key_set 置为 1 ，然后使用 ipc_send(envid, 0, 0, 0) 返回 0 即可：

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
// fs/serv.c
void serve_key_set(u_int envid, struct Fsreq_key_set *rq) {
    // 判断当前状态是否已加载密钥，如果已加载密钥， IPC 返回 -E_BAD_KEY
    if (encrypt_key_set) {
        ipc_send(envid, -E_BAD_KEY, 0, 0);
        return;
    }

    // 利用 open_lookup 找到对应的 Open 结构体，判断文件大小是否至少有两个磁盘块大小
    int r;
    struct Open *pOpen;
    if ((r = open_lookup(envid, rq->req_fileid, &pOpen)) < 0) {
        ipc_send(envid, r, 0, 0);
        return;
    }
    if (pOpen->o_file->f_size < 2 * BLOCK_SIZE) {
        ipc_send(envid, -E_INVALID_KEY_FILE, 0, 0);
        return;
    }

    // 利用 file_get_block 读取文件的第一个磁盘块，判断第一个字是否为 FS_MAGIC
    void *blk;
    if ((r = file_get_block(pOpen->o_file, 0, &blk)) < 0) {
        ipc_send(envid, r, 0, 0);
        return;
    }

    // 如果密钥文件不合法， IPC 返回 -E_INVALID_KEY_FILE
    if (((int *)blk)[0] != FS_MAGIC) {
        ipc_send(envid, -E_INVALID_KEY_FILE, 0, 0);
        return;
    }

    // 利用 file_get_block 读取文件的第二个磁盘块，将密钥复制到 encrypt_key 中
    void *anoblk;
    if ((r = file_get_block(pOpen->o_file, 1, &anoblk)) < 0) {
        ipc_send(envid, r, 0, 0);
        return;
    }
    memcpy(encrypt_key, (unsigned char *)anoblk, BLOCK_SIZE);

    // 将当前状态标记为已加载密钥
    encrypt_key_set = 1;

    // IPC 返回 0
    ipc_send(envid, 0, 0, 0);
}

接下来是 serve_key_unset() 函数。首先判断当前是否已加载密钥，并将当前状态标记为未加载密钥，这一步仿照刚才去做即可。接下来将 encrypt_key 清零，这里依然可以使用 for 循环，当然也可以使用 memset() 函数实现。最后我们使用 ipc_send() 返回 0 即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// fs/serv.c
void serve_key_unset(u_int envid) {
    // 判断当前状态是否已加载密钥，如果未加载密钥， IPC 返回 -E_BAD_KEY
    if (!encrypt_key_set) {
        ipc_send(envid, -E_BAD_KEY, 0, 0);
        return;
    }
    
    // 将当前状态标记为未加载密钥
    encrypt_key_set = 0;
    
    // 将密钥缓存 encrypt_key 清零
    memset((void *)encrypt_key, 0, BLOCK_SIZE);

    // IPC 返回 0
    ipc_send(envid, 0, 0, 0);
}

然后是 serve_key_isset() 函数。这个函数只需要直接返回当前密钥的加载状态，即 encrypt_key_set 即可：

1
2
3
4
5
// fs/serv.c
void serve_key_isset(u_int envid) {
    // IPC 返回当前状态
    ipc_send(envid, encrypt_key_set, 0, 0);
}

接下来是第 6 步和第 7 步，我们继续在 fs/serv.c 中修改 serve_map() 函数和 serve_close() 函数。

在 serve_map() 函数中，当打开文件的 mode 中含有 O_ENCRYPT 时，我们需要检查当前是否加载了密钥，如果加载了密钥，我们就需要对当前的磁盘块进行加密。首先，我们需要获取当前打开文件的 mode ，在 Open 结构体 pOpen 中有一个 o_mode 字段，我们只要将其与 O_ENCRYPT 进行按位与运算，即可判断出该文件是否以加密形式打开。

如果以加密形式打开，我们就需要将当前磁盘块的内容 blk 与密钥内容 encrypt_key 按位异或，这样就完成了 serve_map() 函数：

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
// fs/serv.c
void serve_map(u_int envid, struct Fsreq_map *rq) {
    struct Open *pOpen;
    u_int filebno;
    void *blk;
    int r;

    if ((r = open_lookup(envid, rq->req_fileid, &pOpen)) < 0) {
        ipc_send(envid, r, 0, 0);
        return;
    }

    filebno = rq->req_offset / BLOCK_SIZE;

    if ((r = file_get_block(pOpen->o_file, filebno, &blk)) < 0) {
        ipc_send(envid, r, 0, 0);
        return;
    }

    if (pOpen->o_mode & O_ENCRYPT) {
        if (!encrypt_key_set) {
            ipc_send(envid, -E_BAD_KEY, 0, 0);
            return;
        }
        else {
            for (int i = 0; i < BLOCK_SIZE; i++) {
                *((unsigned char *)(blk + i)) = (*((unsigned char *)(blk + i)) ^ *(encrypt_key + i));
            }
        }
    }

    ipc_send(envid, 0, blk, PTE_D | PTE_LIBRARY);
}

serve_close() 函数的修改略微有些难度，当打开文件的 mode 中含有 O_ENCRYPT 时，我们需要检查当前是否加载了密钥，如果加载了密钥，我们就需要对文件中的所有磁盘块进行解密。和之前不同的是，我们需要加密或解密的不只是一个磁盘块，而是文件中的所有磁盘块，这就需要我们根据 Open 结构体 pOpen 依次找到所有的磁盘块 blk 。根据提示，我们可以参考 fs/fs.c 中的 file_flush() 函数，通过文件大小计算文件的磁盘块数，根据文件的磁盘块数遍历磁盘块序号，使用 fs/fs.c 中的 file_get_block() 函数即可遍历到所有的磁盘块。

刚才已经介绍过了，我们可以通过 pOpen->o_file->f_size 获取到文件的大小。接下来参考 file_flush() 函数中的 u_int nblocks = ROUND(f->f_size, BLOCK_SIZE) / BLOCK_SIZE; 即可得到文件的磁盘块数 nblocks 。将磁盘块序号从 0 遍历到 nblocks - 1 ，将文件控制块 pOpen->o_file 和磁盘块序号输入 file_get_block() 函数中，即可得到当前磁盘块序号对应的磁盘块：

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
// fs/serv.c
void serve_close(u_int envid, struct Fsreq_close *rq) {
    struct Open *pOpen;

    int r;

    if ((r = open_lookup(envid, rq->req_fileid, &pOpen)) < 0) {
        ipc_send(envid, r, 0, 0);
        return;
    }

    if (pOpen->o_mode & O_ENCRYPT) {
        if (!encrypt_key_set) {
            ipc_send(envid, -E_BAD_KEY, 0, 0);
            return;
        }
        else {
            struct File *f = pOpen->o_file;
            u_int nblocks = ROUND(f->f_size, BLOCK_SIZE) / BLOCK_SIZE;
            for (u_int bno = 0; bno < nblocks; bno++) {
                void *blk;
                if ((r = file_get_block(f, bno, &blk)) < 0) {
                    continue;
                }
                for (int i = 0; i < BLOCK_SIZE; i++) {
                    *((unsigned char *)(blk + i)) = (*((unsigned char *)(blk + i)) ^ *(encrypt_key + i));
                }
            }
        }
    }

    file_close(pOpen->o_file);
    ipc_send(envid, 0, 0, 0);
}

最后我们来完成第 8 步，完成 user/lib/fsipc.c 和 user/lib/file.c 中的 6 个函数。我们首先来看 user/lib/fsipc.c 中的 3 个函数，这些函数的实现方式非常固定，主要作用就是将参数打包进 req 结构体中，作为传递给文件进程 serv 服务的参数，并且在 return 语句中调用 fsipc() 函数。

对于 fsipc_key_set() 函数，我们仿照同文件中的其它有参数的函数，例如 fsipc_close() fsipc_dirty() fsipc_remove() ，先将 fsipcbuf 强制转换为对应的 req 结构体，即 struct Fsreq_key_set * 类型，再将参数中的 fileid 写入 req 结构体中即可。最后，我们在 return 语句中调用 fsipc() 函数，第一个参数是函数对应的服务，第二个参数为 req 。由于我们只需要通过 ipc 从文件进程接收一个值，而不需要接收页面，所以将 fsipc() 函数的第三个和第四个参数置 0 即可。

对于 fsipc_key_unset() 和 fsipc_key_isset() 两个函数，它们没有参数需要传递给文件进程，所以实际上不需要 req 参数，我们仿照同文件中的 fsipc_sync() 函数，在调用 fsipc() 函数时在第二个参数的位置直接填入 fsipcbuf 即可，实际上这个 fsipcbuf 并不会被文件进程使用到：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// user/lib/fsipc.c
int fsipc_key_set(u_int fileid) {
    // 合理调用 fsipc 函数
    struct Fsreq_key_set *req = (struct Fsreq_key_set *)fsipcbuf;
    req->req_fileid = fileid;
    return fsipc(FSREQ_KEY_SET, req, 0, 0);
}

int fsipc_key_unset(void) {
    // 合理调用 fsipc 函数
    return fsipc(FSREQ_KEY_UNSET, fsipcbuf, 0, 0);
}

int fsipc_key_isset(void) {
    // 合理调用 fsipc 函数
    return fsipc(FSREQ_KEY_ISSET, fsipcbuf, 0, 0);
}

最后，我们再来看 user/lib/file.c 中的 3 个函数。首先是 fskey_set() 函数。根据提示，我们需要先使用 fd_lookup() 函数找到密钥文件的文件描述符，我们向 fd_lookup() 函数输入函数的参数 fdnum ，即可得到文件描述符 fd 。

接下来我们需要检查密钥文件的打开模式，文件描述符 fd 中同样有一个字段 fd_omode ，记录着当前文件的打开模式。首先密钥文件不能够以加密模式打开，于是我们可以通过 fd->fd_omode 与 O_ENCRYPT 按位异或来判断。另外，密钥文件必须通过允许读的模式打开，这里需要注意的是，允许读写模式的判断方式比较特殊，这里有一个比较奇怪的设计：在宏定义中，只读模式 O_RDONLY 为 0x0000，只写模式 O_WRONLY 为 0x0001 ，读写模式 O_RDWR 为 0x0002 ，所以通过直接按位与的方式来判断模式的方法在这里是错误的，例如 fd->fd_omode 与 0x0000 按位与的结果显然是恒为 0 ；正确的做法是将 fd->fd_omode 与 O_ACCMODE（即 0x0003）进行按位与，判断按位与的结果分别与 O_RDONLY O_WRONLY O_RDWR 是否相等，具体做法可以参考 user/lib/fd.c 中的 read() 函数和 write() 函数，注意双等于号 == 的优先级高于按位与 & ，所以必须为按位与表达式加上括号！回到题目，使用 O_RDONLY 模式或 O_RDWR 模式打开密钥文件都是可以的，只有使用 O_WRONLY 模式打开密钥文件是错误的。

在 return 语句中，我们需要调用相应的 IPC 函数，即 fsipc_key_set() 函数。这个函数需要一个名为 fileid 的参数。然而我们能够发现，f_fileid 字段并不位于 Fd 结构体中，而是位于 Filefd 中。不过没关系，我们知道这两种结构体可以互相转换，我们直接将当前的文件描述符 fd 强制转换为 struct Filefd * 类型，即可获得其中的 f_fileid 字段了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// user/lib/file.c
int fskey_set(int fdnum) {
    // 使用 fd_lookup 找到对应的 Fd 结构体。判断传入的文件描述符是否合法
    // 如果不合法返回 fd_lookup 函数的返回值（该函数除了0之外，只会返回 -E_INVAL 错误码，符合系统行为要求）
    int r;
    struct Fd *fd;
    if ((r = fd_lookup(fdnum, &fd)) < 0) {
        return r;
    }


    // 判断文件是否以加密方式打开，判断打开方式是否为只写
    // 密钥文件要求以非加密且允许读的方式打开，不满足则返回 -E_INVAL
    if (fd->fd_omode & O_ENCRYPT) {
        return -E_INVAL;
    }
    if ((fd->fd_omode & O_ACCMODE) == O_WRONLY) {
        return -E_INVAL;
    }

    // 通过对 Fd 结构体进行处理获得 fileid ，合理调用相应文件系统 IPC 函数
    struct Filefd *ffd = (struct Filefd *)fd;
    return fsipc_key_set(ffd->f_fileid);
}

最后，我们完成 fskey_unset() 和 fskey_isset() 两个函数，只需要直接调用相关的 IPC 函数，也就是 fsipc_key_unset() 和 fsipc_key_isset() 就可以了：

1
2
3
4
5
6
7
8
9
10
// user/lib/file.c
int fskey_unset() {
    // 合理调用相应文件系统 IPC 函数
    return fsipc_key_unset();
}

int fskey_isset() {
    // 合理调用相应文件系统 IPC 函数
    return fsipc_key_isset();
}

这样，我们就完成这道史诗级的 Lab 5 extra ！其实这道题的难度并没有拉满，甚至完全没有出现需要传递页面的 IPC ，不过有很多细节还是需要我们对课下代码比较全面的理解才能够写对，比如之前提到的读写模式的检测，所以实际上能够做出来的同学依然是寥寥无几。这也提醒我们课下如果不认真读代码，不做好全面的准备，甚至完全不读代码，直接抄开源代码，想要在考试中答对所有问题肯定是不可能的（当然如果你本来就没打算做 extra 那当我没说哈哈）。文件系统这一章的内容非常之多，函数调用错综复杂，还是希望大家能够仔细研读，加油！

Lab 6 Exam

由于题目中没有给出代码的已知部分，这里先贴一下 user/myawk.c 未实现版本的代码：

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
// user/myawk.c
#include <lib.h>

#define MAXLINE 1024
#define MAXFIELD 10

char line_buf[MAXLINE]; // current line (include \n)
char raw_buf[MAXLINE];    // original line content, equal to $0
char *fields[MAXFIELD]; // $1 ~ $9
int NR = 0;        // current line num

struct Command {
    char print_is_string[MAXFIELD]; // 1 if string literal
    char print_str[MAXFIELD][32];    // string or [ "$n" | NR | NF]
    int print_count;
};

// prefix check
int starts_with(const char *s, const char *prefix) {
    while (*prefix) {
        if (*s != *prefix) {
            return 0;
        }
        s++;
        prefix++;
    }
    return 1;
}

void parse_command(const char *s, struct Command *cmd) {
    memset(cmd, 0, sizeof(*cmd));

    // jump to print
    while (*s && !starts_with(s, "print")) {
        s++;
    }
    if (starts_with(s, "print")) {
        s += 5;
    }

    // skip space
    while (*s == ' ' || *s == '\t') {
        s++;
    }

    // parse print list
    while (*s && cmd->print_count < MAXFIELD) {
        while (*s == ',' || *s == ' ' || *s == '\t') {
            s++;
        }

        if (*s == '"') {
            // read content in " "
            s++;
            int j = 0;
            while (*s && *s != '"' && j < 31) {
                cmd->print_str[cmd->print_count][j++] = *s++;
            }
            cmd->print_str[cmd->print_count][j] = '\0';
            if (*s == '"') {
                s++;
            }
            cmd->print_is_string[cmd->print_count] = 1;
            cmd->print_count++;
        } else if (*s == '$') {
            // read $n
            /* BLANK 1 :你需要完成对$n的读取 */

            /* BLANK 1 :END */
        } else if (*s == 'N') {
            // read NF | NR
            /* BLANK 2 :你需要完成对特殊变量NF和NR的读取 */

            /* BLANK 2 :END */
        } else {
            // skip unrecognizable content
            while (*s && *s != ',' && *s != ' ' && *s != '\t') {
                s++;
            }
        }
    }
}

void execute_cmd(struct Command *cmd, char **fields, int nf) {
    for (int i = 0; i < cmd->print_count; i++) {
        if (cmd->print_is_string[i]) {
            // string
            printf("%s", cmd->print_str[i]);
        } else {
            // $n, NF, NR

            /* BLANK 3 :执行命令，打印$n, NF, NR的情况 */

            /* BLANK 3 :END */
        }

        if (i < cmd->print_count - 1) {
            printf(" ");
        }
    }

    printf("\n");
}

void process_line(char *line, const char *delim, struct Command *cmd) {
    int NF = 0;
    int i = 0;
    char ch = delim[0];

    strcpy(raw_buf, line);
    for (i = 0; line[i]; i++) {
        if (line[i] == '\n') {
            line[i] = '\0';
            break;
        }
    }

    i = 0;
    while (line[i]) {
        /* BLANK 4 :分割该行，注意这是逐字符处理，注意递增NF，请阅读参考实现完成本空 */

        /* BLANK 4 :END */
    }

    // printf("NR=%d, NF=%d\n", NR, NF);
    // for (i = 0; i <= NF; i++) {
    //     printf("$%d = %s\n", i, fields[i]);
    // }
    // printf("------\n");

    execute_cmd(cmd, fields, NF);
}

void read_input_lines(int fd, const char *delim, struct Command *cmd) {
    char c;
    long n;
    char buf[MAXLINE];
    int line_pos = 0;

    while ((n = read(fd, &c, 1)) > 0) {
        if (c == '\n' || line_pos == MAXLINE - 1) {
            buf[line_pos] = '\0';
            NR++;
            process_line(buf, delim, cmd);
            line_pos = 0;
        } else {
            buf[line_pos++] = c;
        }
    }

    if (n < 0) {
        user_panic("read error");
    }
}

int main(int argc, char **argv) {
    fields[0] = raw_buf;

    // printf("argc = %d\n", argc);
    // for (int i = 0; i < argc; i++) {
    //     printf("arg = %s\n", argv[i]);
    // }

    // for safety
    if (argc != 4 || strcmp(argv[1], "-F") != 0) {
        // exit
        return 1;
    }
    char *delim = argv[2]; // spliter
    char *prog = argv[3];  // processor

    struct Command cmd;
    parse_command(prog, &cmd);
    read_input_lines(0, delim, &cmd); // read from stdin

    return 0;
}

这道题需要填写的部分并不是很多，但是需要阅读的内容比较多，再加上比较复杂的字符串处理逻辑，要想做对还是相当有难度的，起码要花一大把时间。Lab 1 请假来考这个的那可真是有福了。

myawk 命令的执行流程主要分为两个部分，一是将命令从一堆字符串解析为 Command 结构体，即 parse_command() 函数；二是读取要处理的内容，处理后进行输出，即 read_input_lines() 函数。

我们首先来看 parse_command() 函数，我们向其输入 prog ，即命令中单引号内部的全部内容 { print $M [, $K , "STRING"...] } ，我们需要解析这部分内容，将相关信息写入输出的 Command 结构体中。

在这个函数中，我们首先使用 starts_with() 函数找到其中的第一个 print 字样，接下来跳过空白字符，将指针 s 指向 print 字样之后的下一个词语。当这个词语的第一个字符为双引号 " 时，这个词语为字符串，此时我们将双引号中的内容写入 cmd->print_str[cmd->print_count] 中，并在结尾加上 '\0' 。接下来将 cmd->print_is_string[cmd->print_count] 置为 1 ，表示当前输出的内容是字符串。最后将 cmd->print_count++ 。这里要注意的是，在读取完当前词语之后，我们需要确保指针 s 位于词语之后的逗号 , 处。如果在读取完之后，指针 s 还停留在词语内部，就会出现解析问题。

当词语的第一个字符为 $ 时，代表当前词语为 $0 - $9 ，这一部分需要我们自行填写。这里我们如何记录当前词语，也就是向 cmd->print_str[cmd->print_count] 写入什么，其实并没有严格的规定，只要我们在执行命令时能够根据其中的内容选择出正确的操作即可。为了方便，我们在写入时可以省略前面的 $ ，直接向其中写入一个数字即可。对于 cmd->print_is_string[cmd->print_count] ，我们需要将其置为 0 ，以免在执行时和要输出的字符串混淆。最后将 cmd->print_count++ 。当然，我们还是要注意维护指针 s 的位置，确保其指向了词语之后的逗号 , 。

当词语的第一个字符为 N 时，代表当前词语为 NF 或 NR ，我们进行和上述相同的操作即可，这一次我们可以向 cmd->print_str[cmd->print_count] 中写入 F 或 R 。这样就完成了 parse_command() 函数：

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
// user/myawk.c
void parse_command(const char *s, struct Command *cmd) {
    memset(cmd, 0, sizeof(*cmd));

    // jump to print
    while (*s && !starts_with(s, "print")) {
        s++;
    }
    if (starts_with(s, "print")) {
        s += 5;
    }

    // skip space
    while (*s == ' ' || *s == '\t') {
        s++;
    }

    // parse print list
    while (*s && cmd->print_count < MAXFIELD) {
        while (*s == ',' || *s == ' ' || *s == '\t') {
            s++;
        }

        if (*s == '"') {
            // read content in " "
            s++;
            int j = 0;
            while (*s && *s != '"' && j < 31) {
                cmd->print_str[cmd->print_count][j++] = *s++;
            }
            cmd->print_str[cmd->print_count][j] = '\0';
            if (*s == '"') {
                s++;
            }
            cmd->print_is_string[cmd->print_count] = 1;
            cmd->print_count++;
        } else if (*s == '$') {
            // read $n
            /* BLANK 1 :你需要完成对$n的读取 */
            s++;
            cmd->print_str[cmd->print_count][0] = *s;
            s++;
            cmd->print_is_string[cmd->print_count] = 0;
            cmd->print_count++;
            /* BLANK 1 :END */
        } else if (*s == 'N') {
            // read NF | NR
            /* BLANK 2 :你需要完成对特殊变量NF和NR的读取 */
            s++;
            cmd->print_str[cmd->print_count][0] = *s;
            s++;
            cmd->print_is_string[cmd->print_count] = 0;
            cmd->print_count++;
            /* BLANK 2 :END */
        } else {
            // skip unrecognizable content
            while (*s && *s != ',' && *s != ' ' && *s != '\t') {
                s++;
            }
        }
    }
}

接下来是 read_input_lines() 函数，我们将要被处理的文件的文件描述符（这里的 0 代表从标准输入流中读取），分隔符 delim ，以及我们刚才解析得到的 Command 结构体输入其中。需要注意的是，虽然题目中规定分隔符只能是一个字符，但是 delim 仍然是一个字符串，只不过字符串中只有一个字符而已。

read_input_lines() 函数的主体是一个 while 循环，它不断地使用 read() 函数从标准输入流读取一个字符 c 。若 c 不是换行符，则将其写入 buf 中；否则在 buf 的结尾添加 '\0' ，将当前行数 NR++ ，并执行 process_line() 函数。

在 process_line() 函数中，我们对刚才得到的一整行内容进行分割，将每部分的指针填入 fields 中。这里要格外注意的是，fields 的类型是 char *[MAXFIELD] ，也就是一个长度为 MAXFIELD 的数组，数组内元素为 char * 类型的指针。它和二维数组有着本质上的区别，当我们访问 fields[i] 时，我们实际上是在访问指针指向的其它字符串，例如 fields[0] 实际上就是 raw_buf（在 main() 函数的第一行定义），其它的 fields[i] 实际上是指向 line 字符串中不同位置的指针。这也就是为什么我们需要根据提示，将 line 字符串中所有的分隔符都替换为 '\0' ，如果不替换的话，在打印时会将当前列后面的所有列都一并打印出来。

在这个函数中，我们需要格外注意维护当前列 NF 以及当前列指针 fields[NF] 的值，需要注意 NF 是从 1 开始计数的。我们将 line 本身作为 fields 中的第一个指针，即 fields[1] ；在此之后，每当我们读到分隔符 ch ，都将下一个字符的位置作为 fields 中的下一个指针，并将当前的分隔符替换为 '\0' ，这样就能够实现对每行的正确切分了：

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
// user/myawk.c
void process_line(char *line, const char *delim, struct Command *cmd) {
    int NF = 0;
    int i = 0;
    char ch = delim[0];

    strcpy(raw_buf, line);
    for (i = 0; line[i]; i++) {
        if (line[i] == '\n') {
            line[i] = '\0';
            break;
        }
    }

    i = 0;
    NF++;
    fields[NF] = line + i;
    while (line[i]) {
        /* BLANK 4 :分割该行，注意这是逐字符处理，注意递增NF，请阅读参考实现完成本空 */
        if (line[i] == ch) {
            line[i] = '\0';
            i++;
            NF++;
            fields[NF] = line + i;
        }
        else {
            i++;
        }
        /* BLANK 4 :END */
    }

    // printf("NR=%d, NF=%d\n", NR, NF);
    // for (i = 0; i <= NF; i++) {
    //     printf("$%d = %s\n", i, fields[i]);
    // }
    // printf("------\n");

    execute_cmd(cmd, fields, NF);
}

最后，我们调用 execute_cmd() 函数，使用 fields 中切分好的输入，将当前行按照 cmd 中的命令内容进行输出。我们循环遍历 cmd 中的 cmd->print_count 个输出要求，如果当前要输出的是字符串，我们直接输出 cmd->print_str[i] 中的内容即可。如果当前要输出的不是字符串，我们就需要根据我们刚才填入 cmd->print_str[i] 的内容来判断要输出的是什么，比如我们刚才在 cmd->print_str[i][0] 中填入了 0 - 9 代表了 $0 - $9 ，填入了 F 代表 NF ，填入了 R 代表 NR 。

如果 cmd->print_str[i][0] 是 0 - 9 的话，我们就需要输出 fields 中对应的切分好的内容，注意这里的 0 - 9 是 char 类型的字符，如果要转换为数组下标的话需要减去一个 '0' ，即 printf("%s", fields[cmd->print_str[i][0] - '0']); 。

如果 cmd->print_str[i][0] 是 F 或 R 的话，我们直接输出 nf 或 NR 即可。这个变量名设计的真的很搞，一个是小写一个是大写：

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
// user/myawk.c
void execute_cmd(struct Command *cmd, char **fields, int nf) {
    for (int i = 0; i < cmd->print_count; i++) {
        if (cmd->print_is_string[i]) {
            // string
            printf("%s", cmd->print_str[i]);
        } else {
            // $n, NF, NR

            /* BLANK 3 :执行命令，打印$n, NF, NR的情况 */
            if (cmd->print_str[i][0] >= '0' && cmd->print_str[i][0] <= '9') {
                printf("%s", fields[cmd->print_str[i][0] - '0']);
            }
            else if (cmd->print_str[i][0] == 'F') {
                printf("%d", nf);
            }
            else if (cmd->print_str[i][0] == 'R') {
                printf("%d", NR);
            }
            /* BLANK 3 :END */
        }

        if (i < cmd->print_count - 1) {
            printf(" ");
        }
    }

    printf("\n");
}

这样我们就完成了 user/myawk.c 中的全部内容！不过题目中还需要对 user/sh.c 进行一些修改，实现对单引号和双引号中内容的整体读取。举个例子，也就是对于命令 echo "aaa bbb" ，我们需要将其解析成 echo 和 "aaa bbb" 这两个 Token ，而不是 echo "aaa bbb" 三个 Token 。

实际上，题目中已经完全给出这部分的做法，只有 parsecmd() 的 switch 语句中留了空，不过提示也写得非常清楚了，参照 case 'w' 的实现即可，实际上就是把 case 'w' 中的内容完全复制过来，这样就可以了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// user/sh.c
case '\"':
    if (argc >= MAXARGS) {
        debugf("too many arguments\n");
        exit();
    }
    argv[argc++] = t;
    break;
case '\'':
    if (argc >= MAXARGS) {
        debugf("too many arguments\n");
        exit();
    }
    argv[argc++] = t;
    break;

这样我们就完成了这道 exam ！说实话，这个题量感觉完全不符合 exam 的难度，考场上遇到这种题，只能说祝君好运吧！

Lab 6 Extra

非常诡异的是，这道题的难度明显低于 exam ，不知道是不是出反了。但可能是上一道题花费了大家太多时间和精力，导致这道题出现了全员挂零的逆天情况，真是没招了。

这道题把要实现的指令读懂了，其实就已经赢了一半了。对于我们要实现的 xargs 指令，如果不加 -I 选项，那么就将标准输入流中的内容加到 xargs 后面的命令之后，并执行这个命令。例如 xargs echo aaa 命令，我们从标准输入流中输入 bbb\nccc ，经过空白字符切分后会变为 bbb 和 ccc 两个词语，我们将这两个词语按顺序加在 echo 命令之后，那么实际上执行的就是 echo aaa bbb ccc 命令。

如果添加 -I 选项，那么就将 xargs 后面的命令中所有的 replace-char 替换为标准输入流中的第一个词语，执行一次命令；接下来替换为标准输入流中的第二个词语，执行一次命令，以此类推。例如 xargs -I . echo aaa ... 命令，我们从标准输入流中输入 bbb\nccc ，经过空白字符切分后会变为 bbb 和 ccc 两个词语。第一次我们将所有的 . 替换为 bbb ，执行 echo aaa bbbbbbbbb 命令；第二次我们将所有的 . 替换为 ccc ，执行 echo aaa ccccccccc 命令。这个过程中，我们执行了两次命令，和标准输入流中输入的词语数是相同的。

这样我们就理解了我们要实现的 xargs 命令的全部用法，接下来我们还是贴上 user/xargs.c 未实现版的代码：

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
// user/xargs.c
#include "lib.h"

#define MAX_ARG_NUM 64
#define MAX_ARG_LEN 128
#define INT_MAX 2147483647 // according to glibc-2.39
#define EOF ((char)-1)

int iflag = 0;
char replace_char;

char proc_args[MAX_ARG_NUM][MAX_ARG_LEN];
char *proc_argv[MAX_ARG_NUM];
int proc_argc = 0;

char input_args[MAX_ARG_NUM][MAX_ARG_LEN];
int input_argc;

int usage() {
    printf("usage: xargs.b [-I <replace-char>] "
           "<cmd-name> [cmd-args]\n");
    return 1;
}

void spawn_fail(int ret_val) {
    printf("spawn %08d failed: %d\n", syscall_getenvid(), ret_val);
}

int isblank(char ch) {
    return ch == '\r' || ch == '\n' || ch == ' ' || ch == '\t';
}

char getchar() {
    char ch;
    static int r = 1;
    if (!r) {
        return EOF;
    }
    r = read(0, &ch, 1);
    if (r) {
        return ch;
    } else {
        return EOF;
    }
}

char get_non_blank_char() {
    char ch;
    while (1) {
        ch = getchar();
        if (ch == EOF) {
            return EOF;
        } else if (!isblank(ch)) {
            return ch;
        }
    }
    return ch;
}

void parse_input() {
    int i = 0;
    char ch;

    // skip blank char first.
    ch = get_non_blank_char();
    if (ch == EOF) {
        input_argc = 0;
        return;
    }

    do {
        i = 0;
        input_args[input_argc][i++] = ch;
        while (1) {
            ch = getchar();
            if (isblank(ch) || ch == EOF) {
                break;
            }
            input_args[input_argc][i++] = ch;
        }
        input_args[input_argc++][i] = '\0';
        ch = get_non_blank_char();
    } while (ch != EOF);
}

void gen_replaced_arg(int proc_index, int arg_index, char *cmd_argv[]) {
    char *p = proc_args[arg_index];
    char *q = cmd_argv[arg_index];
    /* Set proc_argv to the correct value. Replace the `replace-char`
     * with certain input argument. */
    /* Lab6-Extra: Your code here (6/7) */
}

void gen_argv(int proc_index, int cmd_argc, char *cmd_argv[]) {
    int i;
    proc_argv[0] = cmd_argv[0]; // copy cmd name
    if (iflag) {
        /* Call `gen_replaced_arg` for `cmd_argc` times to generate each
         * argument for this process. */
        /* Lab6-Extra: Your code here (4/7) */
    } else {
        /* Put cmd_argv and input_args sequentially into proc_argv. */
        /* Lab6-Extra: Your code here (5/7) */
    }
}

int spawn_proc(char *cmd_name, char *argv[]) {
    int child;
    /* Spawn a child process and wait for it to finish.
     * Return the error code if spawn faild. */
    /* Lab6-Extra: Your code here (7/7) */
}

int xargs(int cmd_argc, char *cmd_argv[]) {
    parse_input();

    if (iflag) {
        /* If iflag is set, call `gen_argv` and `spawn_proc` for `input_argc` times. */
        /* Lab6-Extra: Your code here (2/7) */

    } else {
        /* Otherwise, call gen_argv and spawn_proc once. */
        /* Lab6-Extra: Your code here (3/7) */
    }
    return 0;
}

int main(int argc, char *argv[]) {
    if (argc <= 1) {
        return usage();
    }

    ARGBEGIN {
    case 'I':
        iflag = 1;
        replace_char = *ARGF();
        break;
    default:
        return usage();
    }
    ARGEND

    /* Call `xargs` if arg is valid, else print usage. */
    /* Lab6-Extra: Your code here (1/7) */
}

我们首先从 main() 函数开始，根据题目中的描述我们可以得知，在 ARGEND 结束之后，argv 会被调整为指向要执行的命令名，同时 argc 也会作出相应变化，从 argv 的位置开始计数。接下来是我们要补充的部分，根据题目中的提示，当要执行的指令名不存在，即 argc 的值为 0 时，我们需要返回 usage() 抛出异常，否则调用 xargs() 函数。调用 xargs() 函数时，我们直接将调整后的 argc 和 argv 传入其中即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// user/xargs.c
int main(int argc, char *argv[]) {
    if (argc <= 1) {
        return usage();
    }

    ARGBEGIN {
    case 'I':
        iflag = 1;
        replace_char = *ARGF();
        break;
    default:
        return usage();
    }
    ARGEND

    /* Call `xargs` if arg is valid, else print usage. */
    /* Lab6-Extra: Your code here (1/7) */
    if (argc == 0) {
        return usage();
    }
    return xargs(argc, argv);
}

在 xargs() 函数中，我们首先调用了 parse_input() 函数，这个函数我们就不详细展开了。总而言之，这个函数是从标准输入流中读取内容，并以空白符作为分隔符切分成词语，将每个词语存储在全局变量 input_args[i] 中，词语的总数为全局变量 input_argc 。

接下来就是分头行动了，我们首先处理简单的一边，也就是没有 -I 参数的情况。我们要做的有两件事，一是使用 gen_argv() 函数，生成出我们要执行的命令，使用全局变量 proc_argc 和 proc_argv 存储；二是使用 spawn_proc() 函数，通过调用 spawn() 函数来执行命令。

对于 gen_argv() 函数，题目中提到，我们在没有开启 -I 选项时，不需要考虑它的第一个函数 proc_index ，于是我们向其中随便传入一个值，比如 0 。接下来，我们将当前的 cmd_argc 和 cmd_argv 传入其中即可。在 gen_argv() 函数中，我们首先将 cmd_argv 中的指针装入 proc_argv 中，接下来将 input_args 中的词语的指针装入 proc_argv ，位于 cmd_argv 内容的后面，这样就实现了将标准输入流中的内容插入原命令之后的操作。最后，我们千万不要忘记根据提示，在 proc_argv[proc_argc] 的位置加上 NULL ，否则会导致 spawn() 函数解析错误！

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
// user/xargs.c
int xargs(int cmd_argc, char *cmd_argv[]) {
    parse_input();

    if (iflag) {
        /* If iflag is set, call `gen_argv` and `spawn_proc` for `input_argc` times. */
        /* Lab6-Extra: Your code here (2/7) */
        ......
    } else {
        /* Otherwise, call gen_argv and spawn_proc once. */
        /* Lab6-Extra: Your code here (3/7) */
        gen_argv(0, cmd_argc, cmd_argv);
        ......
    }
    return 0;
}

void gen_argv(int proc_index, int cmd_argc, char *cmd_argv[]) {
    int i;
    proc_argv[0] = cmd_argv[0]; // copy cmd name
    if (iflag) {
        /* Call `gen_replaced_arg` for `cmd_argc` times to generate each
         * argument for this process. */
        /* Lab6-Extra: Your code here (4/7) */
        ......
    } else {
        /* Put cmd_argv and input_args sequentially into proc_argv. */
        /* Lab6-Extra: Your code here (5/7) */
        for (i = 0; i < cmd_argc; i++) {
            proc_argv[i] = cmd_argv[i];
        }
        for (i = 0; i < input_argc; i++) {
            proc_argv[cmd_argc + i] = input_args[i];
        }
        proc_argc = cmd_argc + input_argc;
        proc_argv[proc_argc] = NULL;
    }
}

接下来是 spawn_proc() 函数。spawn() 函数比较特殊，它不是通过传入 argc 和 argv 来执行的。spawn() 函数没有 argc 参数，这也就意味着它不知道 argv 中一共有多少个元素，所以我们才需要在 argv 的末尾加上 NULL 来告诉 spawn() 函数它的结尾在哪里。同时，原本 argc 的位置取而代之的是 cmd_name ，即要执行的命令的名称。一般来说命令名都是 argv 中的第一个单词，所以我们传入 argv[0] 即可。这同样也是我们需要向 spawn_proc() 函数传入的参数。

在 spawn_proc() 函数内部，我们使用 child = spawn(cmd_name, argv); 来 spawn 出一个执行命令的进程，这个步骤可以模仿 user/sh.c 中的 spawn 操作来实现。通过 child 是否大于等于 0 ，我们可以判断 spawn 操作是否成功。如果成功，我们就根据题目中的提示调用 wait(child) 来等待子进程结束；如果失败，我们就调用 spawn_fail(child) 来输出错误信息。最后的返回值不重要，反正也用不上，随便返回一个 child 就可以：

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
// user/xargs.c
int xargs(int cmd_argc, char *cmd_argv[]) {
    parse_input();

    if (iflag) {
        /* If iflag is set, call `gen_argv` and `spawn_proc` for `input_argc` times. */
        /* Lab6-Extra: Your code here (2/7) */
        ......
    } else {
        /* Otherwise, call gen_argv and spawn_proc once. */
        /* Lab6-Extra: Your code here (3/7) */
        gen_argv(0, cmd_argc, cmd_argv);
        spawn_proc(proc_argv[0], proc_argv);
    }
    return 0;
}

int spawn_proc(char *cmd_name, char *argv[]) {
    int child;
    /* Spawn a child process and wait for it to finish.
     * Return the error code if spawn faild. */
    /* Lab6-Extra: Your code here (7/7) */
    child = spawn(cmd_name, argv);
    if (child >= 0) {
        wait(child);
    }
    else {
        spawn_fail(child);
    }
    return child;
}

这样我们就完成了没有 -I 选项的情况，接下来是更复杂一些的有 -I 选项的情况。我们还是回到 xargs() 函数，这一次我们要重复执行 input_argc 次命令，所以我们根据注释中的提示，使用 for (int i = 0; i < input_argc; i++) 写一个 input_argc 次的循环，在循环中不断调用 gen_argv() 函数和 spawn_proc() 函数。这一次在调用 gen_argv() 函数时，我们需要将 i 传入其第一个参数 proc_index ，表示这次循环要将指定字符替换为从标准输入流中输入的第几个词语。

在 gen_argv() 函数中，我们需要对 argv 中的每个词语，将其中需要替换的字符替换为 input_args[proc_index] 。需要格外注意的是，我们不可以替换命令名，所以 proc_argv[0] 应该直接等于 cmd_argv[0] 。接下来，对于 cmd_argv[1] 到 cmd_argv[cmd_argc - 1] ，我们都需要调用 gen_replaced_arg() 函数对其进行替换。对 cmd_argv[i] 替换的结果被写入 proc_args[i] 中，我们只需要在调用 gen_replaced_arg() 函数后，令 proc_argv[i] 等于 proc_args[i] 即可。最后还是不要忘记将 proc_argv[proc_argc] 赋值为 NULL ：

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
// user/xargs.c
int xargs(int cmd_argc, char *cmd_argv[]) {
    parse_input();

    if (iflag) {
        /* If iflag is set, call `gen_argv` and `spawn_proc` for `input_argc` times. */
        /* Lab6-Extra: Your code here (2/7) */
        for (int i = 0; i < input_argc; i++) {
            gen_argv(i, cmd_argc, cmd_argv);
            spawn_proc(proc_argv[0], proc_argv);
        }
    } else {
        /* Otherwise, call gen_argv and spawn_proc once. */
        /* Lab6-Extra: Your code here (3/7) */
        gen_argv(0, cmd_argc, cmd_argv);
        spawn_proc(proc_argv[0], proc_argv);
    }
    return 0;
}

void gen_argv(int proc_index, int cmd_argc, char *cmd_argv[]) {
    int i;
    proc_argv[0] = cmd_argv[0]; // copy cmd name
    if (iflag) {
        /* Call `gen_replaced_arg` for `cmd_argc` times to generate each
         * argument for this process. */
        /* Lab6-Extra: Your code here (4/7) */
        proc_argv[0] = cmd_argv[0];
        for (i = 1; i < cmd_argc; i++) {
            gen_replaced_arg(proc_index, i, cmd_argv);
            proc_argv[i] = proc_args[i];
        }
        proc_argc = cmd_argc;
        proc_argv[proc_argc] = NULL;
    } else {
        /* Put cmd_argv and input_args sequentially into proc_argv. */
        /* Lab6-Extra: Your code here (5/7) */
        for (i = 0; i < cmd_argc; i++) {
            proc_argv[i] = cmd_argv[i];
        }
        for (i = 0; i < input_argc; i++) {
            proc_argv[cmd_argc + i] = input_args[i];
        }
        proc_argc = cmd_argc + input_argc;
        proc_argv[proc_argc] = NULL;
    }
}

最后是 gen_replaced_arg() 函数，它的作用是处理要执行的命令中的第 arg_index 个词，将其中的指定字符替换为标准输入流中的第 proc_index 个词，将结果保存在 proc_args[arg_index] 中。这里用到的是一个双指针的字符串处理，数据结构学得比较好的同学做起来应该会轻松一些。不过即使不会这种方法，只要是清楚实现目标，相信大家都各有神通，一定能找到一种适合自己的解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void gen_replaced_arg(int proc_index, int arg_index, char *cmd_argv[]) {
    char *p = proc_args[arg_index];
    char *q = cmd_argv[arg_index];
    /* Set proc_argv to the correct value. Replace the `replace-char`
     * with certain input argument. */
    /* Lab6-Extra: Your code here (6/7) */
    while (*q) {
        if (*q != replace_char) {
            *p++ = *q;
        }
        else {
            char *s = input_args[proc_index];
            while (*s) {
                *p++ = *s++;
            }
        }
        q++;
    }
    *p = '\0';
}

这样，我们就完成了最后一道 OS 的上机题目！不过我们的实验课程还尚未结束，接下来到达战场的是 —— 挑战性任务！（快去看我 Shell 挑战性任务的那篇文章吧！）