【MIT6.S081】Lab9 file system

Intro

在这个实验中，我们需要让xv6支持更大的文件和软链接。实验总体不是特别难，不过需要我们理解好文件系统是如何工作的。Lab8 lock中的Buffer Cache也是文件系统的一部分，不过它位于文件系统的下层，这里我们需要处理的更多在上层，偏应用层。

Large files

如何扩大单个文件的大小上限？

要求我们扩大单个文件的大小，实现机制就是通过修改inode的块索引，将原来的12个直接索引和一个一级间接索引变为11个直接索引、一个一级间接索引和一个二级间接索引。

在xv6中，一个数据块的大小为1KB，由于间接块中存放的是下一个块的地址（其实个人认为更准确的说是块号），使用的类型是uint，那么一个间接块能存放这样的地址共1KB / sizeof(uint) = 1KB / 4B = 256个。

这样的话，单个文件大小最大为12 * 1KB + 256 * 1KB = 268KB变为了11 * 1KB + 256 * 1KB + 256 * 256 * 1KB = 65803KB。

修改inode结构体

其数据块地址中：有11个直接块地址，1个一级间接块地址，1个二级间接块地址

在原本的代码中，表示直接块数量的宏为NDIRECT，其定义在fs.h中，我们需要修改其值为11，并且由于我们扩大了文件大小上限，所以也要修改对应的宏MAXFILE，扩大后的应该为：NDIRECT + NINDIRECT + NINDIRECT * NINDIRECT；同时还要修改inode结构体：

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

内存中保存的inode结构体也需要修改：

// 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函数

bmap函数会根据传入参数的数据块号来返回其对应的地址

我们在bmap中看到如果数据块还没有分配的时候，会使用balloc来分配，并返回分配的块的块号。

这个函数我一开始看的时候对于如何分配的比较奇怪，后来在AI的帮助下慢慢理解了。在xv6中的硬盘布局是这样的：

[ boot block | super block | log | inode blocks | free bit map | data blocks]

在学习操作系统时，我们有学到过一个叫位图的东西，将多个块合并作为一个位图，其中的每一位（bit）用来唯一表示一个数据块是否被使用了（例如0表示为使用，1表示使用）。在xv6中，我们在需要分配数据块时，会去位图中寻找可用的数据块的编号，在去获取对应的数据块：

static uint
balloc(uint dev)
{
  int b, bi, m;
  struct buf *bp;

  bp = 0;
  // 文件系统总共有 200000 个块（sb.size = 200000），且每个位图块可以管理 8192 个块（BPB = 8192）
  // 在第一次迭代中，b = 0，读取管理第 0 到第 8191 个块的位图块。
  // 内层循环遍历这 8192 个块，寻找空闲块。
  // 在第二次迭代中，b = 8192，读取管理第 8192 到第 16383 个块的位图块。
  for(b = 0; b < sb.size; b += BPB){
    bp = bread(dev, BBLOCK(b, sb)); // 获取在第n次迭代中管理一个BPB大小的位图块
    // 遍历这个位图块中的每一位，找到未使用的块号并返回
    for(bi = 0; bi < BPB && b + bi < sb.size; bi++){
      m = 1 << (bi % 8);
      if((bp->data[bi/8] & m) == 0){  // Is block free?
        bp->data[bi/8] |= m;  // Mark block in use.
        log_write(bp);
        brelse(bp);
        bzero(dev, b + bi);
        return b + bi;
      }
    }
    brelse(bp);
  }
  printf("balloc: out of blocks\n");
  return 0;
}

要实现大文件的bmap，我们可以仿照原本的bmap是如何处理一级间接块的：

static uint
bmap(struct inode *ip, uint bn)
{
  ...
  // 块号（bn）减去11个，这样是为了方便之后可以按偏移值为0开始计算
  bn -= NDIRECT;
  
  // 如果bn超出了11个，也就说明需要通过一级间接块去获取
  if(bn < NINDIRECT){
    // Load indirect block, allocating if necessary.
    // ip->addrs[11]代表了一级间接块的地址
    if((addr = ip->addrs[NDIRECT]) == 0){
      // 此时还未分配一级间接块，分配
      addr = balloc(ip->dev);
      if(addr == 0)
        return 0;
      ip->addrs[NDIRECT] = addr;
    }
    // 从硬盘中读出这个块
    bp = bread(ip->dev, addr);
    // 获取这个块中的数据（不过这里只是通过指针来更好的操作）
    a = (uint*)bp->data;
    if((addr = a[bn]) == 0){
      // 如果还没有分配bn所表示的数据块，分配
      addr = balloc(ip->dev);
      if(addr){
        a[bn] = addr;
        log_write(bp);
      }
    }
    brelse(bp);
    return addr;
  }
  ...
}

同样的，二级间接块也是类似的操作手法：

static uint
bmap(struct inode *ip, uint bn)
{
  ...
  // 如果bn超出了11个，也就说明需要通过一级间接块去获取
  if(bn < NINDIRECT){
    ...
  }
  // 如果运行到了这里，说明要从二级间接块中寻找，这里减去NINDIRECT（256）也是像之前一样方便计算
  bn -= NINDIRECT;

  // 从二级间接块中找
  if (bn < NINDIRECT * NINDIRECT) {
    // inode的二级间接块还未分配
    if ((addr = ip->addrs[NDIRECT + 1]) == 0) {
      addr = balloc(ip->dev);
      if(addr == 0)
        return 0;
      ip->addrs[NDIRECT + 1] = addr;
    }

    int level1 = bn / NINDIRECT;
    int level2 = bn % NINDIRECT;

    // 读取二级间接块
    bp = bread(ip->dev, addr);
    a = (uint *)bp->data;
    if ((addr = a[level1]) == 0){
      a[level1] = addr = balloc(ip->dev);
      log_write(bp); // 修改了就要记录日志
    }
    brelse(bp);

    bp = bread(ip->dev, addr);
    a = (uint *)bp->data;
    if ((addr = a[level2]) == 0) {
      a[level2] = addr = balloc(ip->dev);
      log_write(bp); // 修改了就要记录日志
    }
    brelse(bp);

    return addr;
  }
}

多的步骤就是二级间接索引需要多一次读取数据块和查找：

假设传入bmap的块号为524，那么其不在直接块中，也不在一级间接块中，而是在二级间接块中。通过bmap中的前两个if之后对于bn的减法操作，此时的bn = 524 - 11 - 256 = 257。那么在二级间接块的第一层中（level1），索引为257 / 256 = 1，在第二层中（level2）索引为257 % 256 = 1 。如下图所示：

Symbolic links

首先要搞清楚软硬链接的区别：

软链接（符号链接）：
- 软链接是一种特殊的文件，它包含指向另一个文件或目录的路径。它类似于Windows中的快捷方式。
- 存储的是目标文件或目录的路径信息。
硬链接：
- 硬链接是文件系统中的一个普通文件名，只是它与其他文件名指向同一个物理文件数据块。
- 存储的是目标文件的数据本身，不包含路径信息。

那么要我们实现软链接，我们需要做的事情有两个：

实现软链接的系统调用
处理使用open打开一个软链接文件

系统调用的实现

实验中让我们实现的系统调用接受连个参数(char *target, char *path)，它在path处创建了一个软链接，该链接指向文件名为target的文件。

如何注册系统调用啥的这里就不赘述了。

首先我们需要准备一些宏：

// stat.h
#define T_SYMLINK 4 // symbolic link

// fcntl.h
#define O_NOFOLLOW 0x800

实现sys_symlink系统调用：

我们创建一个软链接时需要使用create新建一个inode，因为软链接也是一个文件；然后调用writei将目标路径的字符串target写入软链接文件的数据块。

需要注意的是在完成这两步之后需要使用iunlockput(ip)来释放在create中加上的锁。

uint64 sys_symlink(void) {
  char target[MAXPATH], path[MAXPATH];
  if (argstr(0, target, MAXPATH) < 0 || argstr(1, path, MAXPATH) < 0) {
    return -1;
  }

  begin_op();

  // 软链接是一个特殊的文件，其存储的数据为目标文件的路径信息，因此我们在创建软链接时需要创建一个新的inode
  struct inode *ip = create(path, T_SYMLINK, 0, 0);
  if (ip == 0) {
    end_op();
    return -1;
  }

  // 将target字符串写入inode的第一个直接块中
  if (writei(ip, 0, (uint64)target, 0, strlen(target)) < 0) {
    end_op();
    return -1;
  }

  iunlockput(ip);

  end_op();
  return 0;
}

处理open一个软链接的情况

这里可能是这个lab的一个难点了。为什么我们需要处理这样的情况呢？

还记得我们刚刚准备的一个宏O_NOFOLLOW吗，在Linux中，它有这样些特点：

符号链接检查：当O_NOFOLLOW标志被设置时，如果指定的文件名是一个软链接，打开操作将不会跟随这个链接，而是会失败，并返回一个错误。
错误返回：如果尝试打开一个软链接，并且O_NOFOLLOW标志被设置，系统会返回ELOOP错误，表示遇到了太多的符号链接。
用途：这个标志通常用于安全目的，防止应用程序无意中打开一个软链接，这可能被恶意用户用来绕过安全限制。

例如：

int fd = open("/path/to/symlink", O_RDONLY | O_NOFOLLOW);

如果/path/to/symlink是一个软链接，这个调用将失败。

我们需要在sys_open中处理：当需要打开的文件类型是软链接类型并且没有使用O_NOFOLLOW标志时，递归找到最终的目标文件。为什么说是“递归”呢，因为可能有这样一种情况：一个软链接指向了另一个软链接，甚至如此以往。为了避免“子子孙孙无穷无尽”的情况，我们需要设置一个递归层数的限制，当然，我们这里使用循环来代替递归。

uint64
sys_open(void)
{
  ...
  
  if(ip->type == T_DEVICE && (ip->major < 0 || ip->major >= NDEV)){
    ...
  }
  
  // 文件的类型是软链接，且没有使用O_NOFOLLOW标志，就递归地查找，直到找到最终的目标文件的inode
  // 否则，就当作是正常的文件进行打开
  if (ip->type == T_SYMLINK && !(omode & O_NOFOLLOW)) {
    // 如果循环10次后找到的文件类型还是软链接，那么说明有错误了
    for (int i = 0; i < 10; i++) {
      // 从软链接文件的inode中读取目标文件的路径字符串
      // 注意，在这一步之前已经对ip上锁，因此这里操作完后需要解锁
      if (readi(ip, 0, (uint64)path, 0, strlen(path)) < 0) {
        iunlockput(ip);
        end_op();
        return -1;
      }
      iunlockput(ip);

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

      ilock(ip);

      if (ip->type != T_SYMLINK) {
        break;
      }
    }
    if (ip->type == T_SYMLINK) {
      iunlockput(ip);
      end_op();
      return -1;
    }
  }

  if((f = filealloc()) == 0 || (fd = fdalloc(f)) < 0){
    ...
  }

  ...
}

Code Detail

代码实现详情请见Github：

Reference

Summary

文件系统是一个有意思的东西，同时也很复杂，xv6中设计了一个简化的文件系统，并采用了分层的设计。虽然这里将实验做完了，但是我觉得自己还有很多细节没有搞懂。例如其中的日志层，其是如何实现crash之后能恢复过来的代码是如何设计编写的，还有其中的锁的获取与释放等等。希望之后能结合实际再分析分析。

Intro#

Large files#

如何扩大单个文件的大小上限？#

修改inode结构体#

修改bmap函数#

Symbolic links#

系统调用的实现#

处理open一个软链接的情况#

Code Detail#

Reference#

Summary#