MIT 6.s081 Lab9 File system

根据《OSTEP》划分的三个部分，Lab9来到了持久性这一环节。本实验的内容是对文件系统进行一些研究。

通过阅读xv6book的Chapter 9，我们可以了解xv6的文件系统是如何实现的。本实验总共有两个任务。

Large Files

xv6中的 inode 有 12个直接索引（直接对应了 data 区域的磁盘块），1个一级索引（存放另一个指向 data 区域的索引）。因此，最多支持 12 + 256 = 268 个数据块。如下图所示：

因为这个设计，xv6 中存储文件的大小受到了限制，因此本实验的第一个任务就是通过实现二级索引扩大所支持的文件大小，使得其能够存放一个65803个块大小的文件。

因为一个一级索引会指向256块，所以如果我们增加二级索引，就会让文件系统能存储的大小增加256*256-1块，因为少了一块存放用的直接块。所以总共的大小就是256*256+256+11=65803块。根据实验提示，我们首先修改dinode和inode这两个结构体，减少NDIRECT的值，增加二级索引大小的宏定义，然后保持addrs大小不变。

// kernel/fs.h 

#define NDIRECT 11
#define NINDIRECT (BSIZE / sizeof(uint))
#define NDINDIRECT NINDIRECT * NINDIRECT
#define MAXFILE (NDIRECT + NINDIRECT + NDINDIRECT)

// 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
};

// kernel/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];
};

然后我们需要修改bmap，仿照已有的逻辑实现二级映射：

// kernel/fs.c

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 < 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 -= NINDIRECT;
  // 二级索引
  if(bn < NDINDIRECT)
  {
    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);

    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);

    return addr;
  }

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

最后通过itrunc来完成清理工作，同样是仿照bmap的逻辑进行释放：

// kernel/fs.c

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

  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(j = 0; j < NINDIRECT; j++){
      if(a[j])
      {
        bp2 = bread(ip->dev, a[j]);
        a2 = (uint*)bp2->data;
        for(i = 0; i < NINDIRECT; i++) {
          if(a2[i]) bfree(ip->dev, a2[i]);
        }
        brelse(bp2);
        bfree(ip->dev, a[j]);
      }
        
    }
    brelse(bp);
    bfree(ip->dev, ip->addrs[NDIRECT+1]);
    ip->addrs[NDIRECT] = 0;
  }
  ip->size = 0;
  iupdate(ip);
}

第一个任务完成。

Symbolic links

这个任务是让你实现符号链接，也就是软链接。

因为是通过系统调用的方式增加，所以还是老四样：

// user/usys.pl

entry("symlink");

// user/user.h

int symlink(const char*, const char*);

// kernel/syscall.h

#define SYS_symlink 22

// kernel/syscall.c

extern uint64 sys_symlink(void);

[SYS_symlink] sys_symlink,

声明了系统调用之后就是实现，先从寄存器中读取参数，然后开启事务，避免提交出错；为这个符号链接新建一个 inode；在符号链接的 data 中写入被链接的文件；最后，提交事务：

// kernel/sysfile.c

uint64
sys_symlink(void)
{  
  char path[MAXPATH], target[MAXPATH];
  struct inode *ip;
  // 读取参数
  if(argstr(0, target, MAXPATH) < 0)
    return -1;
  if(argstr(1, path, MAXPATH) < 0)
    return -1;
  // 开启事务
  begin_op();
  // 为这个符号链接新建一个 inode
  if((ip = create(path, T_SYMLINK, 0, 0)) == 0) {
    end_op();
    return -1;
  }
  // 在符号链接的 data 中写入被链接的文件
  if(writei(ip, 0, (uint64)target, 0, MAXPATH) < MAXPATH) {
    iunlockput(ip);
    end_op();
    return -1;
  }
  // 提交事务
  iunlockput(ip);
  end_op();
  return 0;
}

根据实验提示，我们需要增加一个新的文件类型宏定义T_SIMLINK和一个符号标志位O_NOFOLLOW，注意后者要进行与运算，所以位上不要有重叠。

// kernel/stat.h

#define T_SYMLINK 4

// kernel/fcntl.h

#define O_NOFOLLOW 0x010

接下来我们需要修改open系统调用并且要能支持递归查找，在这里设置了递归深度为20的上限：

// kernel/sysfile.c
// in sys_open()

int depth = 0;
...
 while(ip->type == T_SYMLINK && !(omode & O_NOFOLLOW)) {
    if (depth++ >= 20) {
      iunlockput(ip);
      end_op();
      return -1;
    }

    if(readi(ip, 0, (uint64)path, 0, MAXPATH) < MAXPATH) {
      iunlockput(ip);
      end_op();
      return -1;
    }
    iunlockput(ip);

    if((ip = namei(path)) == 0) {
      end_op();
      return -1;
    }
    ilock(ip);
  }
  ...

如果遇到了一些奇怪的编译错误，可能是对应的头文件没有加的原因。

总结

文件系统这方面的知识比较细碎，尤其是要理解 namei, readi, writei 等跟 inode 有关的函数，还有文件系统的事务这一概念等。