MIT 6.828 - Lab - File system

课程主页：https://pdos.csail.mit.edu/6.828/2023/index.html

Large files

xv6 的 inode 中默认包含 12 个直接块，和一个间接块，间接块能记录 255 个块，因此一个 inode 最大可以记录 12 + 256 = 268 个块。一个块的大小为 1KB，因此在 xv6 中文件最大只能是 268KB，本实验的目的是支持更大的文件。要支持更大的文件，可以使用二级间接索引。

本实验中，使用 11 个直接索引块，1 个间接索引块，1 个二级间接索引块，最终可以记录 11 + 256 + (256 * 256) = 65803 个块。

修改宏定义，微调 dinode 的定义如下：

#define NDIRECT 11
#define INDIRECT_INDEX NDIRECT
#define DOUBLE_INDIRECT_INDEX (INDIRECT_INDEX + 1)
#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
};

file.h 中 inode 结构也需要做些调整：

struct inode {
   short minor;
   short nlink;
   uint size;
-  uint addrs[NDIRECT+1];
+  uint addrs[NDIRECT+2];
 };

在 bmap 中处理二级索引：

static uint
bmap(struct inode *ip, uint bn)
{
  // ...

  bn -= NINDIRECT;
  addr = double_indirect_bmap(ip, bn);
  if (addr != 0) {
    return addr;
  }

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

double_indirect_bmap 定义如下：

static uint
double_indirect_bmap(struct inode *ip, uint bn) {
  if (bn >= NDINDIRECT) {
    return 0;
  }
  // 读一级索引
  int first_level_addr = ip->addrs[DOUBLE_INDIRECT_INDEX];
  if (first_level_addr == 0) {
    first_level_addr = balloc(ip->dev);
    if (first_level_addr == 0)
      return 0;
    ip->addrs[DOUBLE_INDIRECT_INDEX] = first_level_addr;
  }

  // 读二级索引
  struct buf *bp = bread(ip->dev, first_level_addr);
  uint *addrs = (uint*)bp->data;
  int second_level_addr = addrs[bn >> 8];
  if (second_level_addr == 0) {
    second_level_addr = balloc(ip->dev);
    if (second_level_addr == 0)
      return 0;
    addrs[bn >> 8] = second_level_addr;
    log_write(bp);
  }
  brelse(bp);

  // 从二级索引读数据块
  bp = bread(ip->dev, second_level_addr);
  addrs = (uint*)bp->data;
  int addr = addrs[bn & 0xff];
  if (addr == 0) {
    addr = balloc(ip->dev);
    if (addr) {
      addrs[bn & 0xff] = addr;
      log_write(bp);
    }
  }
  brelse(bp);
  return addr;
}

在 itrunc 中需要对删除文件内容的逻辑做处理，需要将二级间接索引中的内容也删掉：

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

  // ...

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

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

Symbolic links

实验目的

实现 symlink(char *target, char *path) 系统调用，给 xv6 添加符号链接功能。符号链接也是一种特殊的文件，其内容存储的是另一个文件的路径。下面的例子会创建一个符号链接：

symlink("/tmp/foo.txt", "/tmp/bar.txt")

这里文件 /tmp/foo.txt 是 /tmp/bar.txt 的符号链接，在打开 /tmp/foo.txt 的时候，会读取 /tmp/foo.txt 中的内容 /tmp/bar.txt，然后再去读取 /tmp/bar.txt 的内容。

/tmp/foo.txt
+---------------+
| /tmp/bar.txt  |
+---------------+

/tmp/bar.txt
+---------------+
| #@$%#$%&^%$.  |
+---------------+

实现思路：

可以创建一种类型为符号链接的 inode 类型，其内容为待链接的文件的路径。因此这里需要做的就是创建一个 inode，并给其中写入内容。另外在打开文件的时候，需要在 open 中处理符号链接。

实现

首先添加必要的宏定义，并添加 symlink 系统调用：

//fcntl.h
#define O_NOFOLLOW 0x800

//syscall.h
#define SYS_symlink 22

//syscall.c
extern uint64 sys_symlink(void);

[SYS_symlink]   sys_symlink,

//usys.pl
entry("symlink");

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

symlink 的实现如下：

• 读取 path 和 target 路径
• 在 path 上创建一个类型为符号链接的 inode
• 将 target 路径写入

uint64
sys_symlink(void)
{
  char target[MAXPATH];
  char path[MAXPATH];
  struct inode *ip;

  if (argstr(0, target, MAXPATH) < 0) {
    return -1;
  }
  if (argstr(1, path, MAXPATH) < 0) {
    return -1;
  }
  if ((ip = namei(path)) != 0) {
    return -1;
  }
  begin_op();
  if ((ip = create(path, T_SYMLINK, 0, 0)) == 0) {
    end_op();
    return -1;
  }
  int len = strlen(target);
  if (writei(ip, 0, (uint64)target, 0, len) != len) {
    panic("symbolic link");
  }
  iunlockput(ip);
  end_op();
  return 0;
}

在 open 中需要处理符号链接，当读取到符号链接时，根据是否设置了 O_NOFOLLOW 选项决定是否跟随符号链接：

uint64
sys_open(void)
{
    // ...
    if(ip->type == T_DIR && omode != O_RDONLY){
      iunlockput(ip);
      end_op();
      return -1;
    }

    // 新增代码开始

    int depth = 0;
    int MAX_DEPTH = 10;
    while (ip && ip->type == T_SYMLINK && !(omode & O_NOFOLLOW)) {
      depth++;
      if (depth >= MAX_DEPTH) {
        iunlockput(ip);
        end_op();
        return -1;
      }
      char linkpath[MAXPATH];
      int n = readi(ip, 0, (uint64)linkpath, 0, MAXPATH);
      if (n <= 0) {
        iunlockput(ip);
        end_op();
        return -1;
      }
      linkpath[n] = '\0';
      iunlockput(ip);
      if ((ip = namei(linkpath)) == 0) {
        end_op();
        return -1;
      }
      ilock(ip);
    }
    // 新增代码终止
  
  }
 
  if(ip->type == T_DEVICE && (ip->major < 0 || ip->major >= NDEV)){
    iunlockput(ip);
    end_op();
    return -1;
  }

  // ...
}