Lab 9 file system

file system 的 Optional challenge 比较简单
前面的题解可以参考这篇博客： https://blog.csdn.net/LostUnravel/article/details/121431163

Support triple-indirect blocks.

首先这部分的代码 其实和原要求中的第一题非常类似。只是要额外实现1层，这样就可以支持更大的文件。
理论上最大可以支持256*256*256+256*256+256+10 个block， 一个block 是1KB的情况下，那么可以支持16.8G的文件。
远远超过了这个LAB文件系统的总容量。
根据param.h, 我们可以发现我们的文件系统是在200MB的大小。

#ifdef LAB_FS
#define FSSIZE       200000  // size of file system in blocks
#else

那么其实支持了3层的结构，其实第3层页只要使用前2个条目即可。（256 * 256 * 3 < 200 MB）

为了让代码更加简洁，来让我们更容易的拓展到3层。我做了如下改动：

1708080722486.png
那么当我们需要变为3层的时候，我们只要更改
#define INDIR_LAYERS 2这个变量即可，当然要更改MAXFILE的大小去看到效果。

下面变更bmap 和 itrunc 为递归写法，来避免复制黏贴 重复的代码逻辑。

static uint
bmap(struct inode *ip, uint bn)
{
  uint addr, *a;
  struct buf *bp;

  if(bn < NDIRECT){
    if((addr = ip->addrs[bn]) == 0){
      addr = balloc(ip->dev);
      if(addr == 0)
        return 0;
      ip->addrs[bn] = addr;
    }
    return addr;
  }
  bn -= NDIRECT;

  uint prev_base = 1;
  for (int in_layer = 0, base = NINDIRECT; in_layer < INDIR_LAYERS; in_layer++, base *= NINDIRECT) {
    if (bn < base) {
      uint idx = NDIRECT + in_layer;
      if((addr = ip->addrs[idx]) == 0){
        if ((ip->addrs[idx] = addr = balloc(ip->dev)) == 0)
          return 0;
      }
      for (int j = 0; j <= in_layer; j++, bn %= prev_base, prev_base /= NINDIRECT) {
        bp = bread(ip->dev, addr);
        a = (uint*)bp->data;
        idx = bn / prev_base;
        if((addr = a[idx]) == 0){
          if((addr = balloc(ip->dev))){
            a[idx] = addr;
            log_write(bp);
          }
        }
        brelse(bp);
      }
      return addr;
    }
    bn -= base;
    prev_base = base;
  }
  panic("bmap: out of range");
}

// Truncate inode (discard contents).
// Caller must hold ip->lock.
void 
turnc_recur(uint dev, uint *addr, int layer)
{
  struct buf *bp;
  uint *a;

  bp = bread(dev, *addr);
  a = (uint*)bp->data;
  int last_layer = (layer == 0);
  for(int j = 0; j < NINDIRECT; j++){
    if(!a[j]) continue;
    if (!last_layer) turnc_recur(dev, &a[j], layer - 1);
    else bfree(dev, a[j]);
  }
  brelse(bp);
  bfree(dev, *addr);
  *addr = 0;
}
void
itrunc(struct inode *ip)
{
  for(int i = 0; i < NDIRECT; i++){
    if(ip->addrs[i]){
      bfree(ip->dev, ip->addrs[i]);
      ip->addrs[i] = 0;
    }
  }
  for (int in_layer = 0, base = NINDIRECT; in_layer < INDIR_LAYERS; in_layer++, base *= NINDIRECT) {
    int idx = NDIRECT + in_layer;
    if(ip->addrs[idx]){
      turnc_recur(ip->dev, &ip->addrs[idx], in_layer);
    }
  }

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

到这里，我们进行测试，确保LAB 9的用例 依然可以通过。

1708081135087.png

下面，我们只需要做一些小改动，就可以支持triple-indirect blocks.

1708081201612.png

下面进行usertests -q测试，
我们会发现在test writebig:时会报 panic: bget: no buffers

原因是因为我们这边单个文件SIZE达到200MB，那么这里会用到valid bit的block 数为 (200000 / 8096） = 25
也就是这些block, 都会在bfree的时候 调用logwrite 写进log里，但是我们这里是1个unlock的txn， 所以这些LOG，会被bpin,这样就造成这些block bit map 位置在45-69，25个完全被保留在bcache里

32 (root dir inode)
45 (bit map)
70 (root dir content)
33 (bigfile inode)
46 (bit map)
47 (bit map)
48 (bit map)
49 (bit map)
50 (bit map)
51 (bit map)
52 (bit map)
53 (bit map)
66910 (1st indirect block)
54 (bit map)
55 (bit map)
56 (bit map)
57 (bit map)
58 (bit map)
59 (bit map)
60 (bit map)
61 (bit map)
132704 (2rd indirect block)
62 (bit map)
63 (bit map)
64 (bit map)
65 (bit map)
66 (bit map)
67 (bit map)
68 (bit map)
196441 (3rd direct block)
alloc: 69 (bit map)

根据上述发现，我们需要把log size 和 buf size 分别调大1.应该就可以跑过测试。

#define LOGSIZE      31 // max data blocks in on-disk log
#define NBUF         31  // size of disk block cache

改大1格后测试顺利通过。基于上述情况，正确的做法是要把MAXOPBLOCKS改大

1708095573089.png
综上，我们再跑一次usertests 1708096984710.png