6.1810 Lab - File System

Posted on In Views:

实验指导：Lab - File System

文件系统的实验包括两部分：实现大文件；实现符号链接（symbol link）。

Large Files

这个任务是给 xv6 实现大文件功能。

为了理解「大文件」，首先我们可以看看原来的 xv6 支持什么样的「小文件」。

这是 xv6 中 inode 的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
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 + 1];
};

inode 表示一个 regular file 或者 directory 的 metadata，包括这个文件的大小、设备号等信息。它还包含指向这个文件数据块（data blocks）的指针，也就是 inode::addrs 这个字段。它是一个长度是 NDIRECT + 1 的数组（NDIRECT = 12），前 NDIRECT 个元素是直接索引（「跳一次」索引），最后一个元素是间接索引（「跳两次」索引），如图 8.3 所示。间接索引指向一个 block，这个 block 1024 B （BSIZE = 1024）的逻辑扇区全部用来存对间接数据块的索引，一共 256 个。所以 xv6 一个 inode 可以索引的数据块的数量为 12 + 256 = 268 blocks。

而这个任务希望我们把它扩展到 11 + 256 + 256 * 256 个 blocks。从这个数字可以看出思路是在原来的基础上，把其中的一个「跳一次」索引变成「跳三次」索引。这里分级索引和 page table 的分级有异曲同工。

于是我们要修改这个「跳」的地方，修改它「跳」的策略。bmap 可以被想象成文件系统的 MMU，可以把一个文件内部按照 block 为单位的偏移转换成磁盘上的真实位置，这个「跳」就是在这里完成的，所以核心是修改 bmap。

首先我们先修改 fs.h 和 file.h 中关于 inode 和 addrs 的相关定义。

fs.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define NDIRECT 11
#define NINDIRECT (BSIZE / sizeof(uint))
#define N_DOUBLE_INDIRECT (NINDIRECT * NINDIRECT)
#define MAXFILE (NDIRECT + NINDIRECT + N_DOUBLE_INDIRECT)

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

接下来我们修改 bmap，在原来的逻辑后面加入二级间接的索引逻辑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
static uint
bmap(struct inode *ip, uint bn)
{
  uint addr, *a;
  struct buf *bp;
  if(bn < NDIRECT){
    if((addr = ip->addrs[bn]) == 0){
      addr = balloc(ip->dev);
      if(addr == 0)
        return 0;
      ip->addrs[bn] = addr;
    }
    return addr;
  }
  bn -= NDIRECT;
  if(bn < NINDIRECT){
    // Load indirect block, allocating if necessary.
    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){
      addr = balloc(ip->dev);
      if(addr){
        a[bn] = addr;
        log_write(bp);
      }
    }
    brelse(bp);
    return addr;
  }
  bn -= NINDIRECT;

  if (bn < N_DOUBLE_INDIRECT) {
    // Ensure the L1 index table is created.
    if ((addr = ip->addrs[NDIRECT + 1]) == 0) {
      addr = balloc(ip->dev);
      if (addr == 0)
        return 0;
      ip->addrs[NDIRECT + 1] = addr;
    }

    // Ensure the L2 index table is created.
    struct buf* bp_l1 = bread(ip->dev, addr);
    uint* a_l1 = (uint*)bp_l1->data;
    uint idx_l1 = bn / NINDIRECT;
    if ((addr = a_l1[idx_l1]) == 0) {
      addr = balloc(ip->dev);
      if (addr == 0) {
        brelse(bp_l1);
        return 0;
      }
      a_l1[idx_l1] = addr;
      log_write(bp_l1);
    }

    brelse(bp_l1);

    // Load the indirect block, allocating if necessary
    struct buf* bp_l2 = bread(ip->dev, addr);
    uint* a_l2 = (uint*)bp_l2->data;
    uint idx_l2 = bn % NINDIRECT;
    if ((addr = a_l2[idx_l2]) == 0) {
      addr = balloc(ip->dev);
      if (addr) {
        a_l2[idx_l2] = addr;
        log_write(bp_l2);
      }
    }

    brelse(bp_l2);
    return addr;
  }

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

最后需要修改 itrunc。itrunc 的作用是吧一个文件的大小变成 0，并释放它占用的所有磁盘块。那么我们在 itrunc 的时候也需要遍历所有的被 inode 索引到的 blocks。我们需要在原有的释放一级间接块的逻辑后面加上释放二级间接块的逻辑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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 < 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]) {
    struct buf* bp_l1 = bread(ip->dev, ip->addrs[NDIRECT + 1]);
    uint* a_l1 = (uint*)bp_l1->data;

    for (i = 0; i < NINDIRECT; ++i) {
      if (a_l1[i] == 0) {
        continue;
      }

      struct buf* bp_l2 = bread(ip->dev, a_l1[i]);
      uint* a_l2 = (uint*)bp_l2->data;
      for (j = 0; j < NINDIRECT; ++j) {
        if (a_l2[j] == 0) {
          continue;
        }

        bfree(ip->dev, a_l2[j]);
      }

      brelse(bp_l2);
      bfree(ip->dev, a_l1[i]);
    }

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

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

Symbolic Links

这个任务需要实现一个符号连接。

其实我一直没太搞懂为什么会同时存在硬链接和软链接。我问了下 Gemini，它说：

  • 硬链接是为了数据的安全和坚固。它保证了只要有一个链接还在，文件数据就不会丢，可以用在备份系统。
  • 软链接是为了用户的方便和灵活。它允许跨盘、链接目录、重组文件结构，可以用作快捷方式、灵活跳转。

好吧。这个 task 让我们实现软链接，大致的思路是加一个系统调用 sys_symlink，负责把用户制定的 path 链接到 target_path，以便于用户从 path 所在的目录跳转到 target_path。有两个事情要做：

  • 为了跳转，我们需要把 target_path 以某种形式存在用户制定的 path 的 inode 里，我们可以就存在这个 inode 的 data blocks 里。
  • 在做 open 系统调用的时候，如果 open 的是一个 symlink，我们需要跳转到它真正的 inode。这里要注意 symlink 有可能会套娃，所以我们要递归地跳转，一直到跳转到的位置不是一个 symlink 为止。

那么首先按照 guidance 上的提示加一个新的 syscall：sys_symlink。接着我们来实现这个 syscall。

  • 可以参考 sys_open / sys_mkdir 等系统调用。它们的结构和我们要实现的 sys_symlink 都相似，逻辑都包在一个 transaction 里，并且都有创建新的 inode 的步骤。
  • 要注意 createi 创建出来的 inode 是被锁住的，最后需要 unlock 交出这个 inode 的使用权。最后也需要 put 掉这个 inode，维护引用计数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
uint64 sys_symlink(void)
{
  char target[MAXPATH]; // The target that the symlink refers to.
  char path[MAXPATH];   // The path where the symlink is created.
  
  argstr(0, target, MAXPATH);
  argstr(1, path, MAXPATH);

  int target_strlen = strlen(target); 

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

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

  iunlockput(ip);
  end_op();

  return 0;
}

下面我们来让 open 支持跳转。这个地方要注意对于 symlink 我们也是可以直接读 data block 文本的，即之前存的 target_path 的内容，而不跳转，只需要在调用 open 的时候加上 O_NOFOLLOW 这个 flag。

我们在 read 中实现的思路就是，当我们打开的 inode 是 T_SYMLINK 并且没有 O_NOFOLLOW 这个 flag 的时候，就做 inode 的跳转。Guidance 中提到如果递归深度超过一定次数，说明这里可能存在一个 symlink 的环，就返回 error（文中提到的是深度是 10）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
uint64
sys_open(void)
{
  char path[MAXPATH];
  int fd, omode;
  struct file *f;
  struct inode *ip;
  int n;

  argint(1, &omode);
  if((n = argstr(0, path, MAXPATH)) < 0)
    return -1;

  begin_op();

  // Create a new inode; or open an existing inode
  // with the path specified.
  if(omode & O_CREATE){
    ip = create(path, T_FILE, 0, 0);
    if(ip == 0){
      end_op();
      return -1;
    }
  } else {
    if((ip = namei(path)) == 0){
      end_op();
      return -1;
    }
    ilock(ip);
    if(ip->type == T_DIR && omode != O_RDONLY){
      iunlockput(ip);
      end_op();
      return -1;
    }
  }
  
  if(ip->type == T_DEVICE && (ip->major < 0 || ip->major >= NDEV)){
    iunlockput(ip);
    end_op();
    return -1;
  }

  // Redirect to the real inode, if the path is a symlink
  // and opened without a O_NOFOLLOW.
  // For symlink path opened with O_NOFOLLOW, we won't recursively step into the inode
  // that said symlink refers to.
  if (ip->type == T_SYMLINK && !(omode & O_NOFOLLOW)) {
    for (int dep = 0; dep < 10 && ip->type == T_SYMLINK; ++dep) {
      char path[MAXPATH];
      memset(path, 0, sizeof path);
      readi(ip, 0, (uint64)path, 0, MAXPATH);
      
      // Release the current inode since we'll go ahead.
      iunlockput(ip);
      
      // Try to look up the next inode.
      if ((ip = namei(path)) == 0) {
        end_op();
        return -1;
      }

      ilock(ip);
    }

    // Returns an error code if the depth of links reaches some threshold (10).
    if (ip->type == T_SYMLINK) {
      iunlockput(ip);
      end_op();
      return -1;
    }
  }

  if((f = filealloc()) == 0 || (fd = fdalloc(f)) < 0){
    if(f)
      fileclose(f);
    iunlockput(ip);
    end_op();
    return -1;
  }

  if(ip->type == T_DEVICE){
    f->type = FD_DEVICE;
    f->major = ip->major;
  } else {
    f->type = FD_INODE;
    f->off = 0;
  }
  f->ip = ip;
  f->readable = !(omode & O_WRONLY);
  f->writable = (omode & O_WRONLY) || (omode & O_RDWR);

  if((omode & O_TRUNC) && ip->type == T_FILE){
    itrunc(ip);
  }

  iunlock(ip);
  end_op();

  return fd;
}

实验结果