xv6 文件系统的扩容

发表于 | 分类于
树形存储的开始：Inode

准备措施

  根据指导书里的内容，将文件 Makefile 下的 CPUS 改为 1 并在 QEMUOPTS 前添加语句 QEMUEXTRA $=-$snapshot 以加快xv6创建大文件的速率

1
2
3
4
ifndef CPUS
CPUS := 1
endif
QEMUEXTRA = -snapshot

  mkfs.c 文件在初始化文件系统时通过参数 FSSIZE 指定分配数据块的数量

1
int nbitmap = FSSIZE / (BSIZE * 8) + 1;

  所以我们需要将预定义在头文件 param.h 里的 FSSIZE 从 1000 修改为 20000

1
#define FSSIZE       20000  // size of file system in blocks

  下载 big.c 并将big命令添加至 Makefile 下的 UPROGS 列表；在 xv6 的 shell 里运行 big 观察结果；目前 xv6 的文件系统可分配 140 个数据块

1
2
3
4
5
6
UPROGS=\
	_cat\
	_echo\
	......\
	_zombie\
	_big\

1
2
3
4
$ big
.
wrote 140 sectors
done; ok

fs.c/fs.h 相关项解读

  inode 定义于头文件 fs.h 内，初始的文件系统含有 13 个直接指针 NDIRECT 和 1 个一级间接指针 NINDIRECT，addrs 数组的最后一项就是间接块的地址；参数 MAXFILE 表征该文件系统所能指向的数据块数目的最大值，当前为12 + 512 / 4 = 140

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

// On-disk inode structure
struct dinode {
  short type;           // File type
  short major;          // Major device number (T_DEV only)
  short minor;          // Minor device number (T_DEV only)
  short nlink;          // Number of links to inode in file system
  uint size;            // Size of file (bytes)
  uint addrs[NDIRECT + 1];   // Data block addresses
};

  函数 bmap(ip, bn) 负责建立inode与磁盘上存储的数据块间的映射，返回 inode ip 中的第 bn 个数据块号；如果没有这样一个数据块，bmap 就会分配一个；未申请的块用块号 0 表示，当 bmap 遇到 0 时就将它们替换为新的块号

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
static uint
bmap(struct inode *ip, uint bn)
{
  uint addr, *a;
  struct buf *bp;

  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.
    // ip->addrs[NDIRECT]指向第一个间接块
    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;
  }

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

  我们的主要改动在于 fs.h 指针的重新分配，然后对 bmap 做相应的修改即可

相关修改

  首先改动 fs.h 内的指针分配，把一个直接指针替换为二级间接指针 DNINDIRECT，此时文件系统有 11 个直接指针，一个一级间接指针和一个二级间接指针，addrs 数组的倒数第二项是第一个间接块的地址，最后一项为第二个间接块的地址。此时 MAXFILE 的值为 11 + 512 / 4 + (512 / 4)^2 = 16523

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

// On-disk inode structure
struct dinode {
  short type;           // File type
  short major;          // Major device number (T_DEV only)
  short minor;          // Minor device number (T_DEV only)
  short nlink;          // Number of links to inode in file system
  uint size;            // Size of file (bytes)
  uint addrs[NDIRECT + 2];   // Data block addresses
};

  然后为 fs.c 添加二级间接指针的映射关系，这里唯一需要注意的就是如何计算二级间接指针的逻辑坐标

os.png

  如图，记 bn 为逻辑上我们需要的数据块号（比如 5000），我们需要知道该块对应的一级间接指针坐标以及逻辑上的二级间接指针坐标，只需要进行如下简单的运算：

  • 一级间接指针坐标：bn / 128
  • 二级间接指针坐标：bn % 128

  以 5000 为例，经计算得到bn位于第 39 个一级间接指针指向的指针块，在该块上的下标为 8。补充完整的 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
static uint
bmap(struct inode *ip, uint bn)
{
  uint addr, *a, *p1, p1_addr, *p2, p2_addr;
  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.
    // ip->addrs[NDIRECT]指向第一个间接块
    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 < DINDIRECT){
    // Load double indirect block, allocating if necessary
    // ip->addrs[NDIRECT + 1]指向第二个间接块
    if((addr = ip->addrs[NDIRECT + 1]) == 0)
      ip->addrs[NDIRECT + 1] = addr = balloc(ip->dev);
    bp = bread(ip->dev, addr); // 读第二个间接块指向的指针块
    p1 = (uint*)bp->data;
    p1_addr = bn / NINDIRECT; // 计算bn对应的指针块的位置，取值范围为(0, 127)
    if((addr = p1[p1_addr]) == 0){
      p1[p1_addr] = addr = balloc(ip->dev);
      log_write(bp);
    }

    bp2 = bread(ip->dev, addr);
    p2 = (uint*)bp2->data;
    p2_addr = bn % NINDIRECT; // 计算指针块上bn的下标
    if((addr = p2[p2_addr]) == 0){
      p2[p2_addr] = addr = balloc(ip->dev);
      log_write(bp2);
    }

    brelse(bp2);
    brelse(bp);
    return addr;
  }

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

  完成修改后重新执行 make qemu，键入 big 命令得到以下结果，可见文件系统成功得到扩充，现在最大可指向 16523 个数据块，大小约为 8.46MB

1
2
3
4
5
6
7
$ big
..................................................
..................................................
..................................................
...............
wrote 16523 sectors
done; ok