# MIT6.s081-2020 Lab9 File System

lab 9 文档 (opens new window)

文件系统作为组织和存储数据的方式，通常支持共享用户和应用程序之间的数据，以及持久化，以便数据重新引导。在本模块将向 xv6 文件系统中大文件支持和符号链接出发，带你领悟文件系统的魅力。

# 准备

git fetch
git checkout fs
make clean
1
2
3

# Large files

引言

目前 xv6 文件限制为 268 个块，或 268 * BSIZE 字节（在 xv6 中 BSIZE 为 1024）。这个限制来自这样一个事实：一个 xv6 inode 包含 12 个direct块号和一个singly-indirect块号，这是指一个块最多可以容纳 256 个块号，总共 12+256=268块。因此，本小节的目标是增加 xv6 文件的最大大小，以满足能够创建一个包含 65803 个块的文件。

实现

本小节需要借助doubly-indirect块的方式，其中包含 256 个singly-indirect地址，每个块最多可包含 256 个数据块地址，以此来实现对大文件的支持。最多可以包含 65803 个块，或 256*256+256+11 个块（11 个而不是 12 个，因为我们会为doubly-indirect块牺牲一个direct块号）。参考所给的HINT，即可顺利实现。

HINT1：需要修改NDIRECT的定义，前 11 个元素ip->addrs[]应该是直接块；第 12 个应该是一个单独的间接块（就像现在的块一样）；第 13 个应该是你新的双重间接块。

kernel/fs.h

#define NDIRECT 11
#define NINDIRECT (BSIZE / sizeof(uint))
#define NDINDIRECT (NINDIRECT * NINDIRECT)  //double-indirect
#define MAXFILE (NDIRECT + NINDIRECT + NDINDIRECT)
// On-disk inode structure
struct dinode {
//...
  uint addrs[NDIRECT+2];   // Data block addresses
};
1
2
3
4
5
6
7
8
9
10

修改在file.h中声明struct inode的属性addrs[] ，确保 struct inode和struct dinode它们的元素个数相同addrs[]数组。

kernel/file.h

// in-memory copy of an inode
struct inode {
//...
  uint addrs[NDIRECT+2];
};
1
2
3
4
5

HINT2：修改bmap()函数，参考indirect block的加载方式，确保使用逻辑块编号索引双重间接块及其指向的间接块。

static uint
bmap(struct inode *ip, uint bn)
{
//...
  bn -=NINDIRECT;
  if(bn < NDINDIRECT){
    // Load double 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;
    uint idx = bn / (BSIZE / sizeof(uint));
    bn %= (BSIZE / sizeof(uint));
    if((addr = a[idx]) == 0){
      a[idx] = addr = balloc(ip->dev);
      log_write(bp);
    }
    bp2 = bread(ip->dev, addr);
    a = (uint*)bp2->data;
    if((addr = a[bn]) == 0){
      a[bn] = addr = balloc(ip->dev);
      log_write(bp2);
    }
    brelse(bp2);
    brelse(bp);
    return addr;
  }
  panic("bmap: out of range");
}
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

HINT3：修改itrunc，参考indirect block的释放方式，确保其能够正确的释放文件doubly-indirect的所有块。

void
itrunc(struct inode *ip)
{
//...
  if(ip->addrs[NDIRECT + 1]){
    bp = bread(ip->dev, ip->addrs[NDIRECT + 1]);
    a = (uint*)bp->data;
    for(j = 0; j < NINDIRECT; j++){
      if(a[j]) {
        bp2 = bread(ip->dev, a[j]);
        a2 = (uint*)bp2->data;
        for(k = 0; k < NINDIRECT; k++){
          if(a2[k])
            bfree(ip->dev, a2[k]);
          }
        bfree(ip->dev, a[j]);
        brelse(bp2);
      }
    }
    brelse(bp);
    bfree(ip->dev, ip->addrs[NDIRECT + 1]);
    ip->addrs[NDIRECT + 1] = 0;
  }
  ip->size = 0;
  iupdate(ip);
}
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

结果

启动xv6内核，运行bigfile，可以顺利通过测试。

image-lab9-1.jpg

引言

符号链接（或软链接）是指通过路径名链接的文件；当一个符号链接被打开时，内核会跟随链接指向被引用的文件。符号链接类似于硬链接，但硬链接仅限于指向同一磁盘上的文件，而符号链接可以跨磁盘设备。本小节的目标是实现符号链接，即使得在路径上创建一个新的符号链接，该链接指向由目标命名的文件。参考所给的HINT，即可顺利实现。

实现

HINT1：首先，为symlink创建一个新的系统调用号，在user/usys.pl，user/user.h中添加一个入口，在kernel/syscall.h，kernel/syscall.c中添加一个系统调用声明，将 symlinktest 添加到 Makefile。

user/usys.pl

entry("uptime");
entry("symlink");
1
2

user/user.h

// system calls
//...
int uptime(void);
int symlink(char *, char *);
1
2
3
4

Makefile

    $U/_zombie\
    $U/_symlinktest\
1
2

kernel/syscall.h

#define SYS_close  21
#define SYS_symlink 22
1
2

kernel/syscall.c

extern uint64 sys_symlink(void);
static uint64 (*syscalls[])(void) = {
//...
[SYS_close]   sys_close,
[SYS_symlink] sys_symlink,
};
1
2
3
4
5
6

HINT2：添加新的文件类型（T_SYMLINK) 到 kernel/stat.h 来表示一个符号链接，

kernel/stat.h

#define T_DEVICE  3   // Device
#define T_SYMLINK 4   //SYM link
1
2

HINT3：在kernel/sysfile.c中实现一个sys_symlink以来在指向目标的路径上创建新的符号链接。请注意，系统调用成功时不需要存在目标。需要选择某个位置来存储符号链接的目标路径，例如，在 inode 的数据块中。symlink应该返回一个表示成功 (0) 或失败 (-1) 的整数，类似于link和unlink。

kernel/sysfile.c

uint64
sys_symlink(void) {
  char target[MAXPATH], path[MAXPATH];
  struct inode *ip;
  if(argstr(0, target, MAXPATH) < 0 || argstr(1, path, MAXPATH) < 0)
    return -1;
  begin_op();
  if((ip = create(path, T_SYMLINK, 0, 0)) == 0){
    end_op();
    return -1;
  }
  if(writei(ip, 0, (uint64)target, 0, MAXPATH) != MAXPATH) {
    iunlockput(ip);
    end_op();
    return -1;
  }
  //printf("symlink %p\n",ip->addrs[NDIRECT + 1]);
  iunlockput(ip);
  end_op();
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

HINT4：修改open系统调用来处理路径引用符号链接的情况。并向 kernel/fcntl.h 添加一个新标志(O_NOFOLLOW)，以提供给open系统调用使用。

uint64
sys_open(void)
{
//...
    ilock(ip);
    if(ip->type == T_SYMLINK && (omode & O_NOFOLLOW) == 0) {
      char target[MAXPATH];
      for(int i = 0; i < MAXFOLLOWDEPTH; i++) {
          if(readi(ip, 0, (uint64)target, 0, MAXPATH) < 0) {
            iunlockput(ip);
            end_op();
            return -1;
        }
        iunlockput(ip);
        if((ip = namei(target)) == 0){
          end_op();
          return -1;
        }
        ilock(ip);
        if(ip->type != T_SYMLINK)
          break;
      }
      if(ip->type == T_SYMLINK){
        iunlockput(ip);
        end_op();
        return -1;
      }
      //printf("path: %s,target: %s\n",path,target);
    }
    if(ip->type == T_DIR && omode != O_RDONLY){
      iunlockput(ip);
      end_op();
      return -1;
    }
//...
}
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

[注]：链接的深度达到某个阈值（例如，10），需要通过返回错误代码来近似此值。

kernel/param.h

#define MAXPATH      128   // maximum file path name
#define MAXFOLLOWDEPTH 10 //maximum depth of links
1
2

结果

启动xv6内核，运行symlinktest，可以顺利通过测试。

image-lab9-2.jpg

运行make grade，可以通过所有的测试用例。

image-lab9-3.jpg

# 总结

总的来说，本模块涉及的文件系统实现并不难，但受益匪浅。

就大文件支持而言，其核心需要把握的是对inode、dinode数据结构的设计，把握好原始定义，解决起来不算难。

就符号链接而言，其核心还是设计一个系统调用，整个流程和lab1相差不多，难点在于sys_open函数里添加打开符号链接文件时的处理。需要读者多加思考并总结。