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