MIT 6.s081 Lab9: file system

本次 lab 感觉就是对 xv6 文件系统代码进行熟悉，我们要扩充 xv6 支持的最大文件大小并且给 xv6 实现软链接。

Large files (moderate)

xv6 原本支持的最大文件大小只有 12 + 256 个 block，也就是 inode 结构体中 addr 数组的前 12 个元素指出的 12 个 block加上最后一个元素指出的一个 block 中指出了 256 个 block。

如上图所示，最后一位 singly-indirect block num 指出了一个 block，里面又存储了 256 个 direct block num。一个 block 是 1024B，一个 block num 为 4B，所以正好存储 256 个 direct block num。

我们要做的就是将文件容量扩充为 11 + 256 + 256*256。改为将 addr 数组前 11 位作为 direct block num，第 12 位作为 singly-indirect block num，将第 13 位作为 doubly-indirect block num。doubly-indirect block num 指向一个 block，这个 block 里面的每个条目都是一个 singly-indirect block num，也就是说还需要再定位一次，才能取到真正的 block num。

代码实现

修改 kernel/fs.h 中的这几个宏：

#define NDIRECT 11
#define SINGLY_NINDIRECT (BSIZE / sizeof(uint))
#define DOUBLY_NINDIRECT SINGLY_NINDIRECT * SINGLY_NINDIRECT
#define MAXFILE (NDIRECT + SINGLY_NINDIRECT + DOUBLY_NINDIRECT)

并且记得将 struct inode 和 struct dinode 结构体中的 addrs 数组修改一下：

uint addrs[NDIRECT+1+1];   // Data block addresses

核心就是修改 bmap，仿照原来的代码，对 doubly-indirect block num 进行搜索即可。

static uint
bmap(struct inode *ip, uint bn)
{
  uint addr, *a;
  struct buf *bp;

  if(bn < NDIRECT){
    if((addr = ip->addrs[bn]) == 0)
      ip->addrs[bn] = addr = balloc(ip->dev);
    return addr;
  }
  bn -= NDIRECT;

  if(bn < SINGLY_NINDIRECT){
    // Load indirect block, allocating if necessary.
    if((addr = ip->addrs[NDIRECT]) == 0)
      ip->addrs[NDIRECT] = addr = balloc(ip->dev);
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    if((addr = a[bn]) == 0){
      a[bn] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);
    return addr;
  }
  
  bn -= SINGLY_NINDIRECT;

  /**
    现在的 bn / 256 的值用于在第一级索引中定位一个 block num，取出这个 block 作为二级索引。
    
    bn % 256 的值用于在第二级索引中定位一个 block num，这个 block num 就是 data block num。
    
    所有的 block 都是按需申请，没有的话就创建一个。
  **/

  if(bn < DOUBLY_NINDIRECT){
    if((addr = ip->addrs[NDIRECT+1]) == 0)
      ip->addrs[NDIRECT+1] = addr = balloc(ip->dev);
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    uint idx = bn / (BSIZE / sizeof(uint));
    if((addr = a[idx]) == 0) {
      a[idx] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    idx = bn % (BSIZE / sizeof(uint));
    if((addr = a[idx]) == 0) {
      a[idx] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);
    return addr;
  }

  panic("bmap: out of range");
}

最后修改 itrunc 来释放一个文件的所有 block，跟 bmap 是差不多的，doubly-indirect blocks 多遍历一层就可以了。

void
itrunc(struct inode *ip)
{
  int i, j;
  struct buf *bp;
  uint *a;

  for(i = 0; i < NDIRECT; i++){
    if(ip->addrs[i]){
      bfree(ip->dev, ip->addrs[i]);
      ip->addrs[i] = 0;
    }
  }

  if(ip->addrs[NDIRECT]){
    bp = bread(ip->dev, ip->addrs[NDIRECT]);
    a = (uint*)bp->data;
    for(j = 0; j < SINGLY_NINDIRECT; j++){
      if(a[j])
        bfree(ip->dev, a[j]);
    }
    brelse(bp);
    bfree(ip->dev, ip->addrs[NDIRECT]);
    ip->addrs[NDIRECT] = 0;
  }

  if(ip->addrs[NDIRECT+1]){
    bp = bread(ip->dev, ip->addrs[NDIRECT+1]);
    a = (uint*)bp->data;
    for (j = 0; j < SINGLY_NINDIRECT; j++) {
      if(a[j]) {
        int k;
        struct buf *b = bread(ip->dev, a[j]);
        uint *data = (uint*)b->data;
        for (k = 0; k < SINGLY_NINDIRECT; k++) {
          if(data[k])
            bfree(ip->dev, data[k]);
        }
        brelse(b);
        bfree(ip->dev, a[j]);
      }
    }
    brelse(bp);
    bfree(ip->dev, ip->addrs[NDIRECT+1]);
    ip->addrs[NDIRECT+1] = 0;
  }

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

Symbolic links (moderate)

给 xv6 实现软连接（符号连接）。符号连接通过路径名连接到目标文件，也就是说在使用 open 系统调用的时候，如果打开的是一个符号连接，那么 file system 就会找到这个软连接指向的目标文件，再去打开目标文件（除非指定了 O_NOFOLLOW 标识，那么 fs 就会直接打开软连接，而不会去追踪到目标文件）。

代码实现

前面添加新的系统调用和这里就跳过了。

在 kernel/stat.h 中添加 T_SYMLINK 来标识一个 inode 类型是软连接，在 kernle/fcntl.h 中添加一个新的标识符 O_NOFOLLOW，以让 open 系统调用判断是要打开一个软连接还是追踪软连接的目标文件。

首先实现 kernel/sysfile.c#sys_symlink

这是一个系统调用函数，对应的用户空间的声明是 int symlink(char*, char*)；所以我们需要先将两个参数拿到。

接着开启一个事务，在事务中完成 inode 的创建和写入。调用 create 函数创建 inode，要注意 create 返回的时候已经持有了 inode 的锁，不需要再次获取锁了，并且在事务结束时要调用 iunlockput 函数来释放锁并且取消一次引用。

uint64
sys_symlink(void) {
  char path[MAXPATH], target[MAXPATH];

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

  begin_op();

  struct inode *ip;
  if((ip = create(path, T_SYMLINK, 0, 0)) == 0) {
    end_op();
    return -1;
  }

  int n = strlen(target);

  if(writei(ip, 0, (uint64)target, 0, n) < 0) {
    end_op();
    return -1;
  }

  iunlockput(ip); // 释放在 create 中获取的锁
  end_op();

  return 0;
}

修改 kernel/sysfile.c#sys_open 系统调用，新增判断当前 path 指向的 inode 是否是软连接，并且检查O_NOFOLLOW 标志位。Hints 中写到两点注意事项：

1. 如果一个软连接又指向一个软连接，那么要递归找出最终的目标文件；
2. 软连接可能会成环，这个时候就返回错误，hints 中的解决策略是限制递归次数为 10 次。

if(omode & O_CREATE){
  ip = create(path, T_FILE, 0, 0);
  if(ip == 0){
    end_op();
    return -1;
  }
} else {
  // 新增的代码在此处
  int symlinkdepth = 0;
  while (1) {
    symlinkdepth++;
    if (symlinkdepth > 10) {
      end_op();
      return -1;
    }
    if((ip = namei(path)) == 0){
      end_op();
      return -1;
    }
    ilock(ip);
    if (ip->type == T_SYMLINK && !(omode & O_NOFOLLOW)) {
      if(readi(ip, 0, (uint64)path, 0, MAXPATH) < 0) {
        iunlockput(ip);
        end_op();
        return -1;
      }
      iunlockput(ip);
    } else {
      break;
    }
  }
  if(ip->type == T_DIR && omode != O_RDONLY){
    iunlockput(ip);
    end_op();
    return -1;
  }
}

运行结果

不知道是代码写的太臭还是我这个台式捡垃圾捡的 CPU 太慢的原因，直接跑 make grade 是直接超时了，一会用笔记本跑一下。直接在 qemu 中跑 bigfile、symlinktest、usertests 都是没问题的。

总结

这次 lab 比上一个简单得多，在 symlink 部分需要好好读一下接口。我一开始没看清 create 中就已经获取了 inode 锁，并且没有释放，将 unlock(dp) 看成了 unlock(ip)，也卡了不少时间。