MIT 6.828 - 8. Lab 08: File System

Tags: MIT 6.828

🕯 今日凌晨听说武汉肺炎的 Whistleblower 李文亮因为不治去世了，再次缅怀。

要是中国也有 Whistleblower Protection Act 就好了，至少使英雄配得上被人们缅怀？

实验总结

  1. 本次实验用时约 3 个小时。
  2. 收获是对类 UNIX 文件系统的多层抽象认识更深入了。

实验结束后的全部代码在：https://github.com/monkey2000/xv6-riscv/tree/fs/

测试结果： 

1
2
3
4
5
6
7
8
9
10
11
12
13
running bigfile: 
$ make qemu-gdb
OK (98.2s) 
running symlinktest: 
$ make qemu-gdb
(0.7s) 
  symlinktest: symlinks: OK 
  symlinktest: concurrent symlinks: OK 
usertests: 
$ make qemu-gdb
OK (160.6s) 
time: OK 
Score: 100/100

0. 实验准备

实验指导链接

上来直接：

1
2
$ cd xv6-riscv-fall19
$ git checkout fs

1. Large files

这块是要给 inode 层实现 doubly indirect block 。

这里我简述一下 xv6-rv 的 inode 层模型：

原始系统中，每个 inode 表示一个文件，这个文件有 13 个 entry 表示前 12 个 direct block 在磁盘上的位置和 1 个 indirect block 的位置。 indirect block 有 1024 (block size) / 4 (uint) = 256 个 entry，表示除 12 个 direct block 以外的 data block。这样每个文件最多有 256 + 13 = 269 个 data block，还是太小了。

doubly indirect block 即实现一个通过两个中间层寻址找到 data block，故可以扩展 256 * 256 = 65536 个 data block 。故总计每个文件的最大大小达到 64.26MB （通过牺牲一个 direct block entry）。

关键代码在 kernel/fs.c > 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
static uint
bmap(struct inode *ip, uint bn)
{
  uint addr, *a, *a2;
  struct buf *bp, *bp2;

  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 < NDOUBLE_INDIRECT) {
    uint bn_level_1 = bn / NINDIRECT;
    uint bn_level_2 = bn % NINDIRECT;
    // Load level-1 indirect block, allocating if necessary.
    if((addr = ip->addrs[NDIRECT + 1]) == 0)
      ip->addrs[NDIRECT + 1] = addr = balloc(ip->dev);
    
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    // Load level-2 indirect block, allocating if necessary.
    if((addr = a[bn_level_1]) == 0){
      a[bn_level_1] = addr = balloc(ip->dev);
      // level-1 indirect block modified, write back
      log_write(bp);
    }
    brelse(bp);

    bp2 = bread(ip->dev, addr);
    a2 = (uint*)bp2->data;
    // Load data block, allocating if necessary.
    if((addr = a2[bn_level_2]) == 0){
      a2[bn_level_2] = addr = balloc(ip->dev);
      // level-2 block modified, write back
      log_write(bp2);
    }
    brelse(bp2);
    return addr;
  }

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

2. Symbolic links

这个是给 file 层实现一个简单的 symbolic link，需要注意被链接的文件未必存在，可以把这个 path 存到 symbolic link 文件中。

关键代码在 kernel/sysfile.c >> sys_open() 和 kernel/sysfile.c >> sys_symlink()

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
101
102
103
104
105
106
107
108
109
110
uint64
sys_open(void)
{
  char path[MAXPATH];
  int fd, omode;
  struct file *f;
  struct inode *ip;
  int n;

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

  begin_op(ROOTDEV);

  if(omode & O_CREATE){
    ip = create(path, T_FILE, 0, 0);
    if(ip == 0){
      end_op(ROOTDEV);
      return -1;
    }
  } else {
    if((ip = namei(path)) == 0){
      end_op(ROOTDEV);
      return -1;
    }
    ilock(ip);
    if(ip->type == T_DIR && omode != O_RDONLY){
      iunlockput(ip);
      end_op(ROOTDEV);
      return -1;
    }
  }

  if(ip->type == T_DEVICE && (ip->major < 0 || ip->major >= NDEV)){
    iunlockput(ip);
    end_op(ROOTDEV);
    return -1;
  }

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

  // printf("open: path=%s; no_follow=%d\n", path, !!(omode & O_NOFOLLOW));

  // resolve symlink
  if(!(omode & O_NOFOLLOW)) {
    uint cnt = 0;
    while(ip->type == T_SYMLINK && cnt < 10) {
      int len = 0;
      readi(ip, 0, (uint64)&len, 0, sizeof(int));
      
      if(len > MAXPATH)
        panic("open: corrupted symlink inode");
      
      readi(ip, 0, (uint64)path, sizeof(int), len + 1);
      iunlockput(ip);

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

      ilock(ip);
      
      if(ip->type == T_DIR && omode != O_RDONLY){
        iunlockput(ip);
        end_op(ROOTDEV);
        return -1;
      }

      if(ip->type == T_DEVICE && (ip->major < 0 || ip->major >= NDEV)){
        iunlockput(ip);
        end_op(ROOTDEV);
        return -1;
      }

      // printf("open: resolve symlink -> %s len=%d\n", path, len);

      cnt++;
    }

    if(cnt >= 10) {
      iunlockput(ip);
      end_op(ROOTDEV);
      return -1;
    }
  }

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

  iunlock(ip);
  end_op(ROOTDEV);

  return fd;
}
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
uint64 sys_symlink(void) {
  char target[MAXPATH], path[MAXPATH];
  int fd;
  struct file *f;
  struct inode *ip;

  if(argstr(0, target, MAXPATH) < 0 || argstr(1, path, MAXPATH) < 0)
    return -1;
  
  begin_op(ROOTDEV);

  // Create symlink inode
  ip = create(path, T_SYMLINK, 0, 0);
  if(ip == 0){
    end_op(ROOTDEV);
    return -1;
  }

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

  f->type = FD_INODE;
  f->ip = ip;
  f->off = 0;
  f->readable = 0;
  f->writable = 0;

  int len = strlen(target);
  // printf("symlink: symlink %s -> %s len=%d\n", path, target, len);
  writei(ip, 0, (uint64)&len, 0, sizeof(int));
  writei(ip, 0, (uint64)target, sizeof(int), len + 1);
  iupdate(ip);
  iunlockput(ip);

  end_op(ROOTDEV);

  return 0;
}
知识共享许可协议 2000 - 2099 MonKey's Blog | 自豪地采用 Hexo + Pandoc + KaTeX + Highlight.js