现在开始进入文件系统的阶段。
Preparation
切换到对应分支
1$ git fetch
2$ git checkout fs
3$ make clean
Task1: Large files
该任务要求我们为 inode 实现二级间接索引。
原本的 inode 含有 11 个直接索引和 1 个一级间接索引，已知一个 disk block 大小为 1024，一个块地址大小为 4B，那一个 block 内部可以容纳 256 条地址，即当前文件系统仅支持最大 (11+256)*BSIZE = 267KB 大小的文件。
这里，我们需要将 1 个直接索引拿来升级为二级间接索引（指向一个包含 256 个一级间接索引的 block）。那么首先要修改 inode 结构体。xv6 中，除了表示磁盘上的 inode struct dinode 外，内存中还包含磁盘 inode 的拷贝 struct inode，这两者分别位于 kernel/fs.h 与 kernel/file.h。同时，还要修改一些宏字段如 MAXFILE，以适配我们「升级」后的文件系统。
1...
2#define NDIRECT 11 // (!new)
3#define NINDIRECT (BSIZE / sizeof(uint))
4#define NDOUBLYINDIRECT ((BSIZE / sizeof(uint))*(BSIZE / sizeof(uint))) // (!new)
5#define MAXFILE (NDIRECT + NINDIRECT + NDOUBLYINDIRECT) // (!new)
6
7// On-disk inode structure
8struct dinode {
9 ...
10 uint addrs[NDIRECT+1+1]; // (!new)
11};
12...
1// in-memory copy of an inode
2struct inode {
3 ...
4 uint addrs[NDIRECT+1+1]; // (!new)
5};
修改完后，便可以通过 make fs.img 重构 qemu 的文件系统了。
现在，我们就能尝试创建更大的文件了。当然，最开始创建一个文件时，文件系统仅仅是为其分配了一个 inode，还没有分配任何 disk block，只有当对文件进行写入时，才根据写入文件的 offset 检查是否需要为其分配 block。我们查看写文件的 sys_write() 操作，会发现其调用了 filewrite()，然后进一步调用 writei()。writei() 里有个 for 循环，每次取文件中一个 block 的大小进行写入，那么第 i 次写入数据对应的文件偏移量为 i * BSIZE，相当于写入了 inode 对应的逻辑块号为 i 的 disk block。
bread() 函数就是根据 block number 找到 block cache 中对应的 block 的，那么 block number 怎么求？我们发现 bread() 的第二个参数是根据函数 bmap() 得来的，而这个 bmap() 就是根据 inode 中的逻辑块号获取物理块号的。进去看了一眼发现，当前 bmap() 仅支持一级间接索引，所以我们要做的就是修改该函数，令其支持二级间接索引。
bmap() 的基本思路很简单，首先查直接索引，然后查一级间接索引。如果某一逻辑块号没有对应的索引块，那就为其分配一个索引块。从这也能看出，索引块是按需分配的，即便支持了二级间接索引，也不会因此导致大量的磁盘块分配。
参考一级索引的查找方式，很容易能写出二级的：
1static uint
2bmap(struct inode *ip, uint bn)
3{
4 uint addr, *a;
5 struct buf *bp;
6
7 if(bn < NDIRECT){
8 ...
9 }
10 bn -= NDIRECT;
11
12 if(bn < NINDIRECT){
13 // Load indirect block, allocating if necessary.
14 ...
15 }
16 bn -= NINDIRECT;
17
18 // 在二级索引块中，包含了 256 个一级间接索引块号，相当于其 `addr[]` 中的每个下标都覆盖了 256 个物理块
19 // 由于这里逻辑块号 bn 已经被映射到 0~256*256-1 的范围，所以
20 // bn/NINDIRECT 为二级索引块的下标
21 // bn%NINDIRECT 为二级索引块指向的一级索引块的下标
22 if (bn < NDOUBLYINDIRECT) {
23 // Load doubly-indirect block, allocating if necessary.
24 if((addr = ip->addrs[NDIRECT+1]) == 0)
25 ip->addrs[NDIRECT+1] = addr = balloc(ip->dev);
26 bp = bread(ip->dev, addr);
27 a = (uint*)bp->data;
28
29 if ((addr = a[bn/NINDIRECT]) == 0) {
30 a[bn/NINDIRECT] = addr = balloc(ip->dev);
31 log_write(bp);
32 }
33 brelse(bp); // 在指向新的 block 前，释放原来的，下同
34
35 bp = bread(ip->dev, addr);
36 a = (uint*)bp->data;
37 bn %= NINDIRECT;
38
39 if((addr = a[bn]) == 0){
40 a[bn] = addr = balloc(ip->dev);
41 log_write(bp);
42 }
43 brelse(bp);
44 return addr;
45 }
46 panic("bmap: out of range");
47}
当然，有写操作，自然有相应的清空操作。什么时候要清空呢？我们这里写的都是位于内存的 block cache 中的数据，struct inode 也是位于内存的相对于磁盘的缓存。有 cache 那必然有 victim，当一个 cache-inode 要被 victim 时，会将其所有块的数据写入 disk，然后释放，从而实现内存复用。
inode 里有一个 ref 字段，表明该文件的引用计数。我们对 inode 的操作总是伴随着 ilock() 与 iunlock()，事实上还有一个函数叫 iunlockput()，它将 iunlock() 与 iput() 结合到一起。那么 iput() 是干嘛的？通过阅读函数原型，我们发现它就是将 inode.ref--，如果减到 0，并且 inode.nlink 也为 0，说明内存中不要这个文件了，磁盘里也不再需要该文件，此时就可以通过 itruc() 将 inode 所使用的所有块写入磁盘并释放。
同样的，我们现在支持了二级索引，那必然要对用到 inode 索引的所有函数进行修改。itrunc() 即是如此。
1void
2itrunc(struct inode *ip)
3{
4 ...
5 for(i = 0; i < NDIRECT; i++){
6 ...
7 }
8
9 if(ip->addrs[NDIRECT]){
10 ...
11 }
12
13 if (ip->addrs[NDIRECT+1]) {
14 bp = bread(ip->dev, ip->addrs[NDIRECT+1]);
15 a = (uint*)bp->data;
16 for (i = 0; i < NINDIRECT; i++) { // 释放二级索引下的所有一级索引
17 if (a[i]) {
18 struct buf *tmp = bread(ip->dev, a[i]);
19 uint *tmp_addr = (uint*)tmp->data;
20 for (j = 0; j < NINDIRECT; j++) {
21 if (tmp_addr[j]) {
22 bfree(ip->dev, tmp_addr[j]);
23 }
24 }
25 brelse(tmp);
26 bfree(ip->dev, a[i]);
27 }
28 }
29 brelse(bp);
30 bfree(ip->dev, ip->addrs[NDIRECT+1]);
31 ip->addrs[NDIRECT+1] = 0;
32 }
33
34 ip->size = 0;
35 iupdate(ip);
36}
Task2: Symbolic links
该任务要求我们实现创建符号链接的系统调用，也就是创建一个 SYMLINK 类型的 inode，其指向的磁盘块数据内容为某个文件/目录的路径。这里我们不用实现指向目录的符号链接，只需要实现对文件的符号链接即可。
新增系统调用需要修改的文件就不说了。首先要新增两个宏，一个是用于 inode 类型的 T_SYMLINK，在 kernel/stat.h 中修改，另一个是用于 open 操作的选项 O_NOFOLLOW，在 kernel/fcntl.h 中修改，表明如果传入的路径解析出来是一个符号链接，且设置了该 option，就不用进一步打开链接对象，而是直接打开文件。否则，要逐渐深入，直到某路径对应的文件不是符号链接。
接下来，我们已经创建了系统调用 sys_symlink()，那么该函数要做什么呢？只需要新建一个 inode，然后调用 writei() 将目标文件路径写入即可。对就这么简单。
1// Create the path with content target in block data.
2uint64
3sys_symlink(void)
4{
5 char target[MAXPATH], path[MAXPATH];
6 struct inode* ip;
7
8 if (argstr(0, target, MAXPATH) < 0 || argstr(1, path, MAXPATH) < 0) {
9 return -1;
10 }
11
12 begin_op();
13 {
14 if ((ip = create(path, T_FILE, 0, 0)) == 0) {
15 end_op();
16 return -1;
17 }
18 ip->type = T_SYMLINK;
19 writei(ip, 0, (uint64)target, 0, MAXPATH);
20 iunlockput(ip); // 调用
21 }
22 end_op();
23 return 0;
24}
还要改的是 sys_open() 函数，我们需要新增一条特性，以便打开 SYMLINK inode 时能打开其链接的目标文件。
1uint64
2sys_open(void)
3{
4 ...
5 if(ip->type == T_DEVICE){
6 ...
7 } else {
8 if (ip->type == T_SYMLINK && (omode & O_NOFOLLOW) == 0) { // 意味着要 follow 下去
9 char target[MAXPATH];
10 uint threshold = 10; // 以防出现 b->a->b->... 的循环链接
11 while (threshold) {
12 if (readi(ip, 0, (uint64)target, 0, MAXPATH) != MAXPATH) { // 读取 inode 存储的 target 文件路径
13 panic("link error");
14 }
15 iunlockput(ip); // ip 即将赋值为下一个 inode，记得释放
16
17 if ((ip = namei(target)) == 0) { // 根据路径获取相应的 inode
18 end_op();
19 return -1;
20 }
21
22 ilock(ip);
23 if (ip->type != T_SYMLINK) {
24 break;
25 }
26 threshold--;
27 }
28
29 if (threshold <= 0) { // 突破阈值，说明可能存在循环，直接报错
30 iunlockput(ip);
31 end_op();
32 return -1;
33 }
34 }
35 f->type = FD_INODE;
36 f->off = 0;
37 }
38 ...
39}
测试结果
1$ make grade
2...
3== Test running bigfile ==
4$ make qemu-gdb
5running bigfile: OK (106.6s)
6== Test running symlinktest ==
7$ make qemu-gdb
8(0.8s)
9== Test symlinktest: symlinks ==
10 symlinktest: symlinks: OK
11== Test symlinktest: concurrent symlinks ==
12 symlinktest: concurrent symlinks: OK
13== Test usertests ==
14$ make qemu-gdb
15usertests: OK (197.8s)
16== Test time ==
17time: OK
18Score: 100/100
最后的工作
git commit -am ""将所有修改提交到本地;- 执行
make handin。由于 lab0 保存了 APIKey，故直接成功提交；
可选的挑战再说吧，没有什么想做的欲望。
附录：软链接与硬链接的区别
unix 文件系统简述
文件数据存放在若干磁盘块中，unix fs 用索引节点(inode)来定位文件所对应的磁盘块号。C 语言实现中，inode 是一个结构体，存放若干文件属性，例如 xv6 完整的 inode 结构体如下所示：
1// On-disk inode structure
2struct dinode {
3 short type; // File type
4 short major; // Major device number (T_DEVICE only)
5 short minor; // Minor device number (T_DEVICE only)
6 short nlink; // Number of links to inode in file system
7 uint size; // Size of file (bytes)
8 uint addrs[NDIRECT+1+1]; // Data block addresses
9};
对于 unix fs 而言，根目录对应的 inode（unix 的万物皆文件理念）位置是全局可知的。一个目录文件对应的磁盘块数据中，有目录下所有子文件的 {文件名 => inode} 索引，根据此即可通过文件名到 inode cache 中拿到相应的数据。
所以对于路径 “/foo/bar/hello.c” 上的文件而言，需要经过多次定位 inode 与读盘操作将 hello.c 的数据读入内存。
软链接
ln -s target symlink
创建软链接相当于创建一个内容为目标文件路径的文件 symlink，为其分配一个全新的 inode 结构体与磁盘空间，通过 symlink 索引文件时只需获取盘块中的路径字符串，再对该路径进行递归访问。
删除 target 后不会影响 symlink，如果在原来的目录下继续新建一个名为 target 的新文件，访问 symlink 依然成功。继续强调一遍，软链接即文件路径，只不过存放在磁盘中，不需要我们手打。在 Linux 中，利用 PATH 创建用户自定义目录下的软链接十分好用，不必进行 cp/mv 等操作。同时，允许用户跨文件系统进行访问。根据「万物即文件」，软链接也可以对目录创建。
缺点是相比直接访问 target 多了一次（如果路径上的文件还是软链接类型文件则需要多次）读盘操作，同时存在一些创建文件的系统调用开销。
硬链接
ln target hardlink
创建硬链接相当于在目录文件中写入一个与 target 相同 inode 号的字段，访问 hardlink 时会定位到 target 同一 inode，不会额外分配空间。
此时需要在 inode 中维护一个 linkRef 的字段，当多个文件 f1,f2,… 在同一 inode 上创建硬链接时，只要有至少一个文件 fi 存在（即 linkRef>0），对应的 inode 就不会被释放；当且仅当链接到那个 inode 的所有文件被删除后（即 linkRef=0），才释放 inode 与磁盘。
根据上述特性，硬链接比较适合对于处于深层次目录下的 target 进行创建，这样可以省去很多目录的读盘开销。但与软链接不同，hardlink 与 target 只能在同一文件系统下，且不允许对目录创建硬链接。