xv6-labs-2020.lab8.file system

Posted on Edited on In Views:
文件系统

lab8 file system

1. 作业链接

  • https://pdos.csail.mit.edu/6.828/2020/labs/fs.html

2. 实习内容

2.1 Large files

(1) 目标与描述

  • xv6 的一个文件有 13 个数据项，前 12 个数据项直接索引到数据块，第 13 个数据项通过一级索引索引到数据块（先找到索引表，通过索引表找到数据块地址）
    • 一个数据项大小为 \(4\) 字节，一个块的大小为 \(1024\) 字节，因此一个块中最多可以放 \(\dfrac{1024}{4}=256\) 个数据项
    • 因此支持的的文件最大为 \(12+256=268\) 块
  • 我们的目标是让 xv6 支持更大的文件，我们增加一个二级索引
    • 前 11 个数据项直接索引，第 12 个数据项一级索引，第 13 个数据项二级索引
    • 这样支持的最大文件为 \(11+256+256\times256=65803\)

  • 注意文件系统的每次修改代码都需要 make clean，否则 fs.img 中文件系统会出问题
    • 或者删除文件 fs.img

(2) 提示

  • fs.c 中的bmap() 函数建立起对数据块的索引
    • 读操作如果没找到数据块，则报错返回
    • 写操作如果没找到，则需要分配一块
  • bmap() 中的参数 bn 是逻辑序号（文件内从 0 开始标的序号）

(3) 实现

[1] 修改宏
1
2
3
4
5
6
7
8
// kernel/fs.h
#define NDIRECT 11
#define INDEX_NUM_1 (BSIZE/sizeof(uint))      // 一级索引表数据个数
#define INDEX_NUM_2 (INDEX_NUM_1*INDEX_NUM_1) // 二级索引表数据个数
#define INDEX_ENTRY_1 NDIRECT                 // 一级索引表位置
#define INDEX_ENTRY_2 (NDIRECT+1)             // 二级索引表位置
#define NINDIRECT (INDEX_NUM_1 + INDEX_NUM_2) // 不能删除!!!!有其他地方引用
#define MAXFILE (NDIRECT + NINDIRECT) // 最大文件个数
  • 注意所有的原来相关引用必须正确
    • NINDIRECT
      • mkfs/mkfs.c：iappend() 正确
    • NDIRECT
1
2
3
4
5
// kernel/file.h
struct inode {
    // ...
    uint addrs[NDIRECT+2];
};
1
2
3
4
5
// kernel/fs.h
struct dinode {
    // ...
    uint addrs[NDIRECT+2];   // Data block addresses
};
[2] 二级索引表
  • 以下的代码修改都是 kernel/fs.c
  • 可以 ctrl-f 找找需要修改的地方（addr）
  • 修改 bmap()，建立起新的映射关系
    • 判断如果是二级索引的话，需要先读入二级索引表，再读入一级索引表，最后读入数据块地址
    • 最后需要释放二级索引表
  • 注意修改了内容就需要调用 log_write() 写到磁盘（write through）
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
static uint bmap(struct inode *ip, uint bn) {
    uint addr, *a;
    struct buf *bp;

    // 前 11 块直接索引
    if(bn < NDIRECT){
        if((addr = ip->addrs[bn]) == 0)
            ip->addrs[bn] = addr = balloc(ip->dev);
        return addr;
    }
    bn -= NDIRECT;

    // 一级索引
    if(bn < INDEX_NUM_1){
        // Load indirect block, allocating if necessary.
        if((addr = ip->addrs[INDEX_ENTRY_1]) == 0)
            ip->addrs[INDEX_ENTRY_1] = 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 -= INDEX_NUM_1;

    // 二级索引
    if(bn < INDEX_NUM_2) {
        uint addr2, *a2, index;
        struct buf* bp2;

        // 加载二级索引, 如果必要的话则为其分配空间
        if((addr2 = ip->addrs[INDEX_ENTRY_2]) == 0)
            ip->addrs[INDEX_ENTRY_2] = addr2 = balloc(ip->dev);

        bp2 = bread(ip->dev, addr2);
        a2 = (uint*)bp2->data;
        // 计算出第几个索引项
        index = bn / INDEX_NUM_1;
        bn %= INDEX_NUM_1;
        // 加载一级索引
        if((addr = a2[index]) == 0) {
            a2[index] = addr = balloc(ip->dev);
            log_write(bp2);
        }
        brelse(bp2);

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

    panic("bmap: out of range");
}
  • itrunc() 丢弃 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
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
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[INDEX_ENTRY_1]){
        bp = bread(ip->dev, ip->addrs[INDEX_ENTRY_1]);
        a = (uint*)bp->data;
        for(j = 0; j < INDEX_NUM_1; j++){
            if(a[j])
                bfree(ip->dev, a[j]);
        }
        brelse(bp);
        bfree(ip->dev, ip->addrs[INDEX_ENTRY_1]);
        ip->addrs[INDEX_ENTRY_1] = 0;
    }

    // 二级索引
    if(ip->addrs[INDEX_ENTRY_2]) {
        struct buf* bp2;
        uint* a2;
        bp2 = bread(ip->dev, ip->addrs[INDEX_ENTRY_2]);
        a2 = (uint*)bp2->data;

        // 逐个查看一级索引
        for(int k = 0; k < INDEX_NUM_1; k++) {
            if(a2[k]) {
                bp = bread(ip->dev, a2[k]);
                a = (uint*)bp->data;
                for(j = 0; j < INDEX_NUM_1; j++) {
                    if(a[j])
                        bfree(ip->dev, a[j]);
                }
                brelse(bp);
                bfree(ip->dev, a2[k]);
                // a2[k] = 0; 有 bfree()
            }
        }

        // 回收二级索引表
        brelse(bp2);
        bfree(ip->dev, ip->addrs[INDEX_ENTRY_2]);
        ip->addrs[INDEX_ENTRY_2] = 0;
    }

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

(1) 目标与描述

  • 实现软链接
1
void symlink(char *target, char *path);
  • 软链接可以跨盘，硬链接不能跨盘

(2) 提示

  • 一部分提示（准备工作）放在实现中
  • symlink(target, path) 的 target 不存在也能成功
    • 你需要有一个地方保存 target 位置，可以保存在 inode 的数据块中
    • 需要有返回值，0 成功，-1 失败（和 link/unlink 一致）
  • 修改系统调用 open() 实现对软链接文件的处理
    • 如果文件不存在，则 open 失败
    • 如果文件打开的 flag 中有 O_NOFOLLOW，则不需要打开软链接对应的文件
  • 如果软链接文件对应的文件还是软链接文件，需要递归打开，直至找到一个不是软链接的文件
    • 如果成环，则需要报错（简单使用一个递归深度阈值判断即可，10）
  • 其他系统调用（例如链接和取消链接）不需要打开到软链接最终链接的文件，只需要打开软链接文件本身即可
  • 不需要处理软链接指向文件夹的情况
    • 不允许指向文件夹

(3) 实现

  • Makefile
1
2
3
4
5
ifeq ($(LAB),fs)
UPROGS += \
    $U/_bigfile\
    $U/_symlinktest
endif
  • user/usys.pl
1
entry("symlink");
  • user/user.h
1
int symlink(const char *, const char*);
  • kernel/sysfile.c
1
2
3
uint64 sys_symlink (void){
    // ...
}
  • kernel/syscall.c
1
2
3
4
5
extern uint64 sys_symlink(void);
static uint64 (*syscalls[])(void) = {
    // ...
    [SYS_symlink] sys_symlink,
};
  • kernel/syscall.h
1
#define SYS_symlink 22
  • kernel/stat.h 中添加文件类型，表示软链接（symbolic link）
1
#define T_SYMLINK 4
  • kernel/fcntl.h 添加新的 flag，用于 open 系统调用，注意文件打开的 flag 是是使用 or 进行组合的，因此不能和已有的 flag 重合
1
#define O_NOFOLLOW 0x004
  • 注意一些小问题即可
    • symlink 的 path 是可以存在的，测试数据中那个有这样的内容
      • 这个人感觉很不合理
      • 没有做一些其他的处理，例如释放原来的文件数据块（感觉应该是要做，但是在这个lab中没有实现）
    • namei() 返回 ip 不为 0 的情况下，ip 是不带锁，但是引用计数+1
      • 因此需要注意 iput() 的调用
    • 将 target 保存在 data 段的开始
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
// 仿照 sys_link 实现即可
// 效果是将 old 指向 new
uint64 sys_symlink (void) {
    char name[DIRSIZ], target[MAXPATH], path[MAXPATH];
    struct inode *dp, *ip;

    // 获取参数
    if(argstr(0, target, MAXPATH) < 0 || argstr(1, path, MAXPATH) < 0)
        return -1;

    begin_op();

    // target 可以不存在
    // if((ip = namei(path)) == 0){
    //   end_op();
    //   return -1;
    // }

    // target 的引用计数增加
    if((ip = namei(target)) != 0) {
        ilock(ip);
        // 不能是文件夹
        // 测试数据中没有文件夹的数据
        if(ip->type == T_DIR) {
            iunlockput(ip);
            end_op();
            return -1;
        }
        ip->nlink++;
        iupdate(ip);
        iunlockput(ip);
    }

    // link 的实现是 new 文件不存在, 因此直接使用 dirlink 即可
    // 在测试数据中, symlink 的 path 文件可以存在, 因此方法不太一样

    // 先检查 path 节点是否存在, 不存在则新建一个
    if((dp = namei(path)) == 0) {
        // path 的父节点得存在
        if((dp = nameiparent(path, name)) == 0) {
            goto bad;
        }
        else {
            iput(dp);
            // 新建一个 path 节点
            // 返回的 dp 带锁且引用计数 +1
            if((dp = create(path, T_SYMLINK, 0, 0)) == 0) {
                goto bad;
            }
            iunlock(dp);
        }
    }

    ilock(dp);
    // 把 target 写入 dp 的 data 字段中
    writei(dp, 0, (uint64)target, 0, MAXPATH);
    // 设置 dp 类型
    // dp->type = T_SYMLINK;(已经设置了)
    iunlockput(dp);
    // iput(ip); 之前调用 iunlockput() 了
    end_op();
    return 0;

    bad:
    ilock(ip);
    ip->nlink--;
    iupdate(ip);
    iunlockput(ip);
    end_op();
    return -1;
}
[3] sys_open() 的实现
  • 在打开文件的时候进行一个判断，如果是软链接同时没有 O_NOFOLLOW flag 的话，就打开软链接对应的文件即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
uint64 sys_open(void) {
    // ...

    // if((ip = namei(path)) == 0){
    //   end_op();
    //   return -1;
    // }
    if((ip = namei_check_symlink(path , 0, omode)) == 0) {
        end_op();
        return -1;
    }

    // ...
}
  • namei_check_symlink() 如下
    • 显式的递归深度检测
    • 注意细节 iput()，因为切换到下一个文件，因此将引用计数-1
    • 读取 target 的时候，注意是在 data 段的开头
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
// 返回如果不为 0, 计数 +1
static struct inode* namei_check_symlink(char *path, uint depth, int omode) {
    // 利用一个显式的递归深度检测环
    if(depth > 10) {
        return 0;
    }
    struct inode *ip;
    // 文件不存在(symlink 允许 target 不存在)
    if((ip = namei(path)) == 0){
        return 0;
    }
    ilock(ip);
    // 如果带有 O_NOFOLLOW flag, 则只需要打开软链接文件本身
    if(!(omode & O_NOFOLLOW) && ip->type == T_SYMLINK) {
        char next[MAXPATH];
        // 保存在 data 的开始
        if(readi(ip, 0, (uint64)next, 0, MAXPATH) == 0) {
            iunlock(ip);
            return 0;
        }
        iunlock(ip);
        iput(ip); // 接着下一个文件了, 因此当前文件的引用计数-1
        return namei_check_symlink(next, depth + 1 ,omode);
    }
    iunlock(ip);
    return ip;
}

3. 实验结果

  • bigfile 和 usertests 不能在规定时间内完成任务（电脑性能问题）
  • 修改了 timeout
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@test(40, "running bigfile")
def test_bigfile():
    r.run_qemu(shell_script([
        'bigfile'
    ]), timeout=500) # 原来是 360, 最终耗时 381
    r.match('^wrote 65803 blocks$')
    r.match('^bigfile done; ok$')


@test(19, "usertests")
def test_usertests():
    r.run_qemu(shell_script([
        'usertests'
    ]), timeout=1000) # 原来是 360, 最终耗时 566.5
    r.match('^ALL TESTS PASSED$')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
$ make qemu-gdb
running bigfile: OK (381.0s)
    (Old xv6.out.bigfile failure log removed)
== Test running symlinktest ==
$ make qemu-gdb
(3.0s)
== Test   symlinktest: symlinks ==
  symlinktest: symlinks: OK
== Test   symlinktest: concurrent symlinks ==
  symlinktest: concurrent symlinks: OK
== Test usertests ==
$ make qemu-gdb
  usertests: OK (566.5s)
    (Old xv6.out.usertests failure log removed)
== Test time ==
time: OK
Score: 100/100

4. 遇到的困难以及收获

  • 第一部分修改宏的时候，没有把所有引用宏的地方都对应上，因此报了奇怪的错误
1
panic : virtio_disk_intr status
  • 以后得注意，在修改已有代码段的时候，需要注意所有引用在修改后还是正确的
  • 文件系统的设计确实很巧妙，函数之间的相互调用需要符合一定的规范
    • 例如引用计数以及锁的设计，感觉都得好好思考才能做出答案
  • 感觉 symlink 的 path 可以存在这个设定确实不太合理

5. 对课程或 lab 的意见和建议

  • 建议提供一些关于 lab 的 debug 功能的指导

6. 参考文献

  • https://pdos.csail.mit.edu/6.828/2019/xv6/book-riscv-rev1.pdf