6.828/2018 Homework: Bigger files for xv6

$ big
…………………………………………………………………………………………………………………………………………………
wrote 16523 sectors
done; ok
$

Noice.

---

big.c tries to create a file as large as possible. The while loop breaks when write() fails.

  while(1){
    *(int*)buf = sectors;
    int cc = write(fd, buf, sizeof(buf));
    if(cc <= 0)
      break;
    sectors++;
	if (sectors % 100 == 0)
		printf(2, ".");
  }

writei() checks for file size:

  if(off + n > MAXFILE*BSIZE)
    return -1;

MAXFILE (defined in fs.h) is currently (NDIRECT + NINDIRECT), which expands into 140 (12 + 128). This means we can’t create a file larger than 140 sectors. Our goal is to make it 16523. How?

bmap() is a function that maps a “logical” block index into a “physical” one. It works like pgdir_walk() with the create flag enabled.

A dinode contains an array, addrs[13]. The indexes of the first 12 blocks of a dinode are directly stored in addrs. Addresses of block number 13 to 140, however, are stored in a separate block (512 bytes per block, 4 bytes per entry, therefore 128 of them), whose physical index is stored in the last entry of addrs.

This is very similar to how we break up page tables into different layers: We don’t want these metadata to eat up too much resources. A block index is 4-byte long, which means if we simply use a long flat array to describe all the 140 sectors, the metadata itself occupies 560 bytes, which is a huge overhead for small files. Instead we reserve the last entry in addrs for the index of a “block table”, and only allocate the table when we really need it.

Now we need the same array to be able to represent even more blocks. The solution is simple: Introducing yet another layer of indirection. Previously, addrs contains 12 direct indexes and 1 indirect index. Now, we change it to: 11 direct indexes, 1 singly-indirect index, and 1 doubly-indirect index. The new addrs array will be able to describe a file as large as 11 + 128 + (128 * 128) = 16523 sectors.

That’s the plan! For that to work, we first need to change some macro definitions in fs.h:

#define NDINDIRECT (NINDIRECT * NINDIRECT)
#define MAXFILE (NDIRECT + NINDIRECT + NDINDIRECT)

And more importantly, modify bmap() to make it support doubly-indirect indexing:

// Return the disk block address of the nth block in inode ip.
// If there is no such block, bmap allocates one.
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;

  // Time to introduce some new terms, like PD and PT.
  // Let's call them BD (Block Directory) and BT (Block Table)...

  if(bn < NINDIRECT){
    if((addr = ip->addrs[NDIRECT]) == 0)      // BT is not allocated yet.
      ip->addrs[NDIRECT] = addr = balloc(ip->dev);
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    if((addr = a[bn]) == 0){                  // Block is not allocated yet.
      a[bn] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);
    return addr;
  }
  bn -= NINDIRECT;

  if(bn < NDINDIRECT){
    if((addr = ip->addrs[NDIRECT+1]) == 0)    // BD is not allocated yet.
      ip->addrs[NDIRECT+1] = addr = balloc(ip->dev);
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    if((addr = a[bn / NINDIRECT]) == 0){      // BT is not allocated yet.
      a[bn / NINDIRECT] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);

    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    if((addr = a[bn % NINDIRECT]) == 0){      // Block is not allocated yet.
      a[bn % NINDIRECT] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);
    return addr;
  }

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

That’s it! It took my machine about one minute to create then read that big file, though… 🙁