6.s081 Lab8 File System | 没什么看头的地方

lab

发布日期: 2023-11-02

现在开始进入文件系统的阶段。

Preparation

切换到对应分支

$ git fetch
$ git checkout fs
$ 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，以适配我们「升级」后的文件系统。

kernel/fs.h
...
#define NDIRECT 11                                                      // (!new)
#define NINDIRECT (BSIZE / sizeof(uint))
#define NDOUBLYINDIRECT ((BSIZE / sizeof(uint))*(BSIZE / sizeof(uint))) // (!new)
#define MAXFILE (NDIRECT + NINDIRECT + NDOUBLYINDIRECT)                 // (!new)

// On-disk inode structure
struct dinode {
  ...
  uint addrs[NDIRECT+1+1];  // (!new)
};
...

kernel/file.h
// in-memory copy of an inode
struct inode {
  ...
  uint addrs[NDIRECT+1+1];  // (!new)
};

修改完后，便可以通过 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() 的基本思路很简单，首先查直接索引，然后查一级间接索引。如果某一逻辑块号没有对应的索引块，那就为其分配一个索引块。从这也能看出，索引块是按需分配的，即便支持了二级间接索引，也不会因此导致大量的磁盘块分配。

参考一级索引的查找方式，很容易能写出二级的：

kernel/fs.c
static uint
bmap(struct inode *ip, uint bn)
{
  uint addr, *a;
  struct buf *bp;

  if(bn < NDIRECT){
    ...
  }
  bn -= NDIRECT;

  if(bn < NINDIRECT){
    // Load indirect block, allocating if necessary.
    ...
  }
  bn -= NINDIRECT;

  // 在二级索引块中，包含了 256 个一级间接索引块号，相当于其 `addr[]` 中的每个下标都覆盖了 256 个物理块
  // 由于这里逻辑块号 bn 已经被映射到 0~256*256-1 的范围，所以
  // bn/NINDIRECT 为二级索引块的下标
  // bn%NINDIRECT 为二级索引块指向的一级索引块的下标
  if (bn < NDOUBLYINDIRECT) {
    // Load doubly-indirect block, allocating if necessary.
    if((addr = ip->addrs[NDIRECT+1]) == 0)
      ip->addrs[NDIRECT+1] = addr = balloc(ip->dev);
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;

    if ((addr = a[bn/NINDIRECT]) == 0) {
      a[bn/NINDIRECT] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp); // 在指向新的 block 前，释放原来的，下同

    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    bn %= NINDIRECT;

    if((addr = a[bn]) == 0){
      a[bn] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);
    return addr;
  }
  panic("bmap: out of range");
}

当然，有写操作，自然有相应的清空操作。什么时候要清空呢？我们这里写的都是位于内存的 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() 即是如此。

kernel/fs.c
void
itrunc(struct inode *ip)
{
  ...
  for(i = 0; i < NDIRECT; i++){
    ...
  }

  if(ip->addrs[NDIRECT]){
    ...
  }

  if (ip->addrs[NDIRECT+1]) {
    bp = bread(ip->dev, ip->addrs[NDIRECT+1]);
    a = (uint*)bp->data;
    for (i = 0; i < NINDIRECT; i++) { // 释放二级索引下的所有一级索引
      if (a[i]) {
        struct buf *tmp = bread(ip->dev, a[i]);
        uint *tmp_addr = (uint*)tmp->data;
        for (j = 0; j < NINDIRECT; j++) {
          if (tmp_addr[j]) {
            bfree(ip->dev, tmp_addr[j]);
          }
        }
        brelse(tmp);
        bfree(ip->dev, a[i]);
      }
    }
    brelse(bp);
    bfree(ip->dev, ip->addrs[NDIRECT+1]);
    ip->addrs[NDIRECT+1] = 0;
  }

  ip->size = 0;
  iupdate(ip);
}

Task2: Symbolic links

该任务要求我们实现创建符号链接的系统调用，也就是创建一个 SYMLINK 类型的 inode，其指向的磁盘块数据内容为某个文件/目录的路径。这里我们不用实现指向目录的符号链接，只需要实现对文件的符号链接即可。

新增系统调用需要修改的文件就不说了。首先要新增两个宏，一个是用于 inode 类型的 T_SYMLINK，在 kernel/stat.h 中修改，另一个是用于 open 操作的选项 O_NOFOLLOW，在 kernel/fcntl.h 中修改，表明如果传入的路径解析出来是一个符号链接，且设置了该 option，就不用进一步打开链接对象，而是直接打开文件。否则，要逐渐深入，直到某路径对应的文件不是符号链接。

接下来，我们已经创建了系统调用 sys_symlink()，那么该函数要做什么呢？只需要新建一个 inode，然后调用 writei() 将目标文件路径写入即可。对就这么简单。

kernel/sysfile.c
// Create the path with content target in block data.
uint64
sys_symlink(void)
{
  char target[MAXPATH], path[MAXPATH];
  struct inode* ip;

  if (argstr(0, target, MAXPATH) < 0 || argstr(1, path, MAXPATH) < 0) {
    return -1;
  }

  begin_op();
  {
    if ((ip = create(path, T_FILE, 0, 0)) == 0) {
      end_op();
      return -1;
    }
    ip->type = T_SYMLINK;
    writei(ip, 0, (uint64)target, 0, MAXPATH);
    iunlockput(ip); // 调用
  }
  end_op();
  return 0;
}

还要改的是 sys_open() 函数，我们需要新增一条特性，以便打开 SYMLINK inode 时能打开其链接的目标文件。

kernel/sysfile.c
uint64
sys_open(void)
{
  ...
  if(ip->type == T_DEVICE){
    ...
  } else {
    if (ip->type == T_SYMLINK && (omode & O_NOFOLLOW) == 0) { // 意味着要 follow 下去
      char target[MAXPATH];
      uint threshold = 10; // 以防出现 b->a->b->... 的循环链接
      while (threshold) {
        if (readi(ip, 0, (uint64)target, 0, MAXPATH) != MAXPATH) { // 读取 inode 存储的 target 文件路径
          panic("link error");
        }
        iunlockput(ip); // ip 即将赋值为下一个 inode，记得释放

        if ((ip = namei(target)) == 0) { // 根据路径获取相应的 inode
          end_op();
          return -1;
        }

        ilock(ip);
        if (ip->type != T_SYMLINK) {
          break;
        }
        threshold--;
      }

      if (threshold <= 0) { // 突破阈值，说明可能存在循环，直接报错
        iunlockput(ip);
        end_op();
        return -1;
      }
    }
    f->type = FD_INODE;
    f->off = 0;
  }
  ...
}

测试结果

$ make grade
...
== Test running bigfile ==
$ make qemu-gdb
running bigfile: OK (106.6s)
== Test running symlinktest ==
$ make qemu-gdb
(0.8s)
== Test   symlinktest: symlinks ==
  symlinktest: symlinks: OK
== Test   symlinktest: concurrent symlinks ==
  symlinktest: concurrent symlinks: OK
== Test usertests ==
$ make qemu-gdb
usertests: OK (197.8s)
== Test time ==
time: OK
Score: 100/100

最后的工作

git commit -am "" 将所有修改提交到本地;
执行 make handin。由于 lab0 保存了 APIKey，故直接成功提交；

可选的挑战再说吧，没有什么想做的欲望。

附录：软链接与硬链接的区别

unix 文件系统简述

文件数据存放在若干磁盘块中，unix fs 用索引节点(inode)来定位文件所对应的磁盘块号。C 语言实现中，inode 是一个结构体，存放若干文件属性，例如 xv6 完整的 inode 结构体如下所示：

// On-disk inode structure
struct dinode {
  short type;               // File type
  short major;              // Major device number (T_DEVICE only)
  short minor;              // Minor device number (T_DEVICE only)
  short nlink;              // Number of links to inode in file system
  uint size;                // Size of file (bytes)
  uint addrs[NDIRECT+1+1];  // Data block addresses
};

对于 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 只能在同一文件系统下，且不允许对目录创建硬链接。

MIT 6.s081

6.s081 Lab9 Mmap

最后一个，也是最有挑战性的一项 coding 任务，是所有前置 lab 的知识综合。

2023-11-04 lab

MIT 6.s081

6.s081 Lab7 Lock

这个 lab 就是对原先的并发控制进行优化。

2023-11-01 lab

MIT6.s081