MIT 6.S081 Lab 9: File System

14 Mar 2023

I now deserve love, romance, and joy - and all the good that life has to offer me.

6.S081课程的第九个Lab，为 xv6 文件系统添加大文件读写与符号链接。

Large files

这个实验需要我们增加 xv6 文件大小上限。当前 xv6 文件限制在 268 个 blocks ，也就是 268 * BSIZE 字节（在 xv6 中 BSIZE==1024）。这个限制是由于 xv6 inode 包括 12 个 direct block number 与 1 个 singly-indirect block number，最后这个 block number 索引到一个包含 256 个 block number 的 block 。所以一个文件 inode 管理的数据块为 12 + 256 == 268 个。

具体见 xv6 书中这个图。

inode in disk

我们需要改变 xv6 文件系统代码让每个 inode 支持 doubly-indirect block ，其包含 256 个 singly-indirect blocks 的 block number 。所以在原来基础上，我们将 inode 的一个 direct block 改为 doubly-indirect block ，最后的数据块为 11 + 256 + 256*256 == 65803。因为限制不能改变 inode size 。

改变指示文件大小与 inode 中直接块数量的宏，与 struct inode struct dinode 的负责存储 block number 的字段，

// in file.h
// in-memory copy of an inode
struct inode {
  uint dev;           // Device number
  uint inum;          // Inode number
  int ref;            // Reference count
  struct sleeplock lock; // protects everything below here
  int valid;          // inode has been read from disk?

  short type;         // copy of disk inode
  short major;
  short minor;
  short nlink;
  uint size;
  uint addrs[NDIRECT+2];
};

// in fs.h
#define NDIRECT 11
#define NINDIRECT (BSIZE / sizeof(uint))
#define MAXFILE (NDIRECT + NINDIRECT + NINDIRECT * NINDIRECT)

// 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+2];   // Data block addresses
};

在磁盘上查找文件数据的代码在fs.c的 bmap()。在读取和写入文件时内核都调用 bmap()。写入时，bmap()会根据需要分配新的块来保存文件内容，如果需要，还会分配一个间接块来保存块地址。我们需要增加一个 doubly-indirect 块。

代码上需要小心，

确保每个数据块读写遵循使用后调用 brelse 与
索引变量 bn 代表的逻辑块号 a block number within the file 时，注意处理不同级别的 indirection 。

// Inode content
//
// The content (data) associated with each inode is stored
// in blocks on the disk. The first NDIRECT block numbers
// are listed in ip->addrs[].  The next NINDIRECT blocks are
// listed in block ip->addrs[NDIRECT]. The next blocks are 
// listed in block ip->addrs[NDIRECT+1].

// Return the disk block address of the nth block in inode ip.
// If there is no such block, bmap allocates one.
static uint
bmap(struct inode *ip, uint bn)
{
  uint addr, *a;
  struct buf *bp;
  uint ind;

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

  if(bn < 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;
  } else {
    bn -= NINDIRECT;

    // Load "doubly-indirect" block, allocating if necessary
    if(0 == (addr = ip->addrs[NDIRECT+1]))
      ip->addrs[NDIRECT+1] = addr = balloc(ip->dev);  
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;

    // get index of singly-indirect block
    ind = bn / NINDIRECT;

    // Load indirect block, allocating if necessary.
    if(0 == (addr = a[ind])) {
      a[ind] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);

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

    // get index of data block
    ind = bn % NINDIRECT;

    // Load data block, allocating if necessary.
    if(0 == (addr = a[ind])) {
      a[ind] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);

    return addr;
  }

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

同时，在释放 inode 持有的数据内容时，需要在 itrunc 函数中释放所有的数据块。

brelse 释放 block 的缓存块
bfree 释放 block 的磁盘块，在 bitmap 删除其占位，使其成为空闲块。

// Truncate inode (discard contents).
// Caller must hold ip->lock.
void
itrunc(struct inode *ip)
{
  int i, j;
  struct buf *bp, *tmpBp;
  uint *a, *tmpA;

  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 < 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(i = 0; i < NINDIRECT; i++) {
      if(a[i]) {
        tmpBp = bread(ip->dev, a[i]);
        tmpA = (uint*)tmpBp->data;
        
        for (j = 0; j < NINDIRECT; j++) {
          if(tmpA[j])
            bfree(ip->dev, tmpA[j]);
        }

        brelse(tmpBp);
        bfree(ip->dev, a[i]);
      }
    }

    brelse(bp);
    bfree(ip->dev, ip->addrs[NDIRECT+1]);
    ip->addrs[NDIRECT+1] = 0;
  }
  ip->size = 0;
  iupdate(ip);
}

Symbolic links

在这个实验中，我们将向xv6添加符号链接。符号链接(或软链接)是指通过路径名链接的文件；当一个符号链接被打开时，内核将按照该链接指向所引用的文件。符号链接类似于硬链接，但硬链接仅限于指向同一磁盘上的文件，而符号链接可以跨磁盘设备。硬链接本质是增加 inode 的链接数，链接与被链接文件本质不分彼此。软连接本质是一种特殊的文件，其内容是链接目标的路径。在 Linux 中使用可以看 Linux中硬连接(hard link)与软连接(symbolic link)的区别。

我们需要实现 symlink(char *target, char *path) 系统调用，它将在 path 处创建一个新的符号链接文件，该符号链接指向由target命名的文件。因为添加系统调用的内容之前课程有提及，具体见 MIT 6.S081 Lab: System calls。

我们需要增加软连接文件类型，

#define T_DIR     1   // Directory
#define T_FILE    2   // File
#define T_DEVICE  3   // Device
#define T_SYMLINK 4   // Symbolic link

增加文件控制 flag 宏，用以 open 系统调用使用，

#define O_RDONLY  0x000
#define O_WRONLY  0x001
#define O_RDWR    0x002
#define O_CREATE  0x200
#define O_TRUNC   0x400
#define O_NOFOLLOW 0x800

实现 symlink(target, path) 系统调用，在指向目标的路径处创建一个新的符号链接文件。注意，系统调用不需要目标链接存在才能成功。我们需要选择一个位置来存储符号链接的目标路径，例如，在inode的数据块中。系统调用 symlink 应该返回一个整数，表示成功(0)或失败(-1)，类似于link和unlink。

uint64 
sys_symlink(void) 
{
  char target[MAXPATH], path[MAXPATH];
  struct inode *ip;
  int targetlen;
  
  if( (targetlen = argstr(0, target, MAXPATH)) < 0 || argstr(1, path, MAXPATH) < 0)
    return -1;

  begin_op();

  // Create synmlink inode, and holding ip lock
  if (0 == (ip = create(path, T_SYMLINK, 0, 0))) {
    end_op();
    return -1;
  }

  if( writei(ip, 0, (uint64)target, 0, targetlen) != targetlen ) {
    iunlockput(ip);
    end_op();
    return -1;
  }
  
  iunlockput(ip);
  end_op();
  return 0;
}

这里有几个值得注意的点，

文件系统的调用必须被 begin_op/end_op 包裹，其获取/释放 log 锁，提交事务，保证了文件系统事务的原子性。
读写 inode 时必须持有其锁，使用完后除了释放锁，还要调用 iput 及时释放资源(通过计数引用/链接，释放 in memory/disk inode)。使用 idiom 为 ilock - r/w - iunlock - iput 。
调用 create 函数创建 inode 时，成功返回的 inode 指针，其索引的 inode 是已经上锁的。不要重复上锁。p.s. 我开始写错了，这个睡眠锁不可重入导致一直 sleeping 。
调用 writei 向 inode 管理的数据块写目标路径时，是按照二进制接口写的。因为所有数据块的内容本质是二进制。是否需要添加末尾的 \0 需要注意。

有了软链接文件，还需要考虑在 open 系统调用中处理路径指向软链接文件的情况。

文件不存在，调用必须失败。
如果进程在 flag 中指定 O_NOFOLLOW 后，调用单纯打开这个软链接，并不 follow 这个链接。
如果没有指定，系统调用 open 必须 follow 这个软链接，即递归地打开链接目标文件，直到链接目标文件不是软链接。
- 如果软链接形成了循环，则必须返回错误码。
- 如果递归到达一定层数阈值，也需要返回错误码。

我通过一个调用一个 help function follow_symlink 来处理递归打开软链接的情况，(若指定 O_NOFOLLOW 则当文件打开)

// in sysfile.c:sys_open function
  if(ip->type == T_DEVICE && (ip->major < 0 || ip->major >= NDEV)){
    iunlockput(ip);
    end_op();
    return -1;
  }

  if(ip->type == T_SYMLINK && (omode & O_NOFOLLOW) == 0) {
    if(follow_symlink(&ip) != 0) {
      printf("follow_symlink encounters cycle or illegal inode or depth threshold\n");
      end_op();
      return -1;
    }
  }

而这个函数会通过 ip_addr 修改原 ip 内容，

// holding lock of ip at ip_addr, 
// searching the non-symlink inode 
static int 
follow_symlink(struct inode** ip_addr)
{
  struct inode* ip;
  uint cycle[DEPTHLINK];
  char linkPath[MAXPATH];
  int i, j;

  ip = *ip_addr;
  for(i = 0; i < DEPTHLINK; ++i ) {

    cycle[i] = ip->inum;
    // check cycle by inum
    for (j = 0; j < i; ++j) 
      if (cycle[j] == cycle[i])
        return -1;
    
    // set zeros to char array to avoid overlap
    memset(linkPath, 0, MAXPATH);
    if(0 == readi(ip, 0, (uint64)linkPath, 0, MAXPATH)) {
      printf("follow_symlink: fail to read inode %u\n", ip->inum);
      iunlockput(ip);
      return -1;
    }
    iunlockput(ip);

    if(0 == (ip = namei(linkPath))) {
      printf("follow_symlink: fail to call namei %s\n", linkPath);
      return -1;
    }
    
    ilock(ip);
    if(ip->type != T_SYMLINK) {
      *ip_addr = ip;
      return 0; 
    }
  }

  // up to DEPTHLINK
  iunlockput(ip);
  return -1;
}

这里需要注意的是，

判断递归成环的依据应当是 inum，因为这个是全局唯一的，用指针则不一定，因为不同指针可以指向同一个 inode 。
调用 readi 读取 inode 管理的数据内容时需注意，因为之前创建软连接时 writei 没有为字符串写 \0 ，所以应当保证 linkPath 一定有 \0 结尾，以后续正确调用 namei 查找 inode 。我这里通过 memset 保证。
查找的过程需要小心地为 inode 上锁/解锁/是否资源，即前文提到的 idiom 。

Conclusion

为文件系统修改代码，需要熟悉

何种数据在磁盘/内存上，如何存储的 (struct inode/dinode)
事务的log机制，事务的开始与提交。
buffer如何缓存
所有这些共享资源的锁，不同函数持有/释放锁的 pre/post condition 并保证 function invariant

总的看，文件系统是一个需要考虑并发安全/性能的程序，适合学习抽象/并发/持久化的知识。

Reference

system-programming