Lesson 9

The Xv6 File-system

The file-system for Xv6 is defined in the file fs.h. Each "block" in the file-system is 512 bytes (defined as BSIZE.) The layout of the file-system is the following:

┌────────────┬─────────────┬─────────┬──────────────────┬─────────────────┬─────────────────┐
│ Boot Block │ Super Block │ Log ... │ Inode Blocks ... │ Free Bitmap ... │ Data Blocks ... │
└────────────┴─────────────┴─────────┴──────────────────┴─────────────────┴─────────────────┘

Boot Block

The Boot block is the first block, normally this might contain a boot loader, but in the case of Xv6 does not seem to contain anything, so we can ignore it.

The Super Block

This block contains the following structure located at the beginning of the block:

struct superblock {
  uint size;         // Size of file system image (blocks)
  uint nblocks;      // Number of data blocks
  uint ninodes;      // Number of inodes.
  uint nlog;         // Number of log blocks
  uint logstart;     // Block number of first log block
  uint inodestart;   // Block number of first inode block
  uint bmapstart;    // Block number of first free map block
};

The unsigned integers are always stored in Intel byte order (little-endian) where the bytes of the integer are stored least significant byte to most significant byte. Since we're using Intel, we can access the data directly w/o having to convert the byte order.

Log

The log is a log of file operations (transactions). For now we will ignore it. Logs or Journals are useful to prevent data loss in the event of power failures as log entries are not removed until the changes to disk have been guaranteed.

The Inode Blocks

The file-system that mkfs.c sets the number of inodes to 200, but the number of inodes is defined by the super-block ninodes entry.

┌─────────┬─────────┬─────────┬─────────┬─────┐
│ Inode 0 │ Inode 1 │ Inode 2 │ Inode 3 │ ... │
└─────────┴─────────┴─────────┴─────────┴─────┘

Inode 0 appears to be unused. Inode 1 is reserved for the root directory. Each inode block is composed of IPB = (BSIZE / sizeof(struct dinode)) == 8 number of inodes. fs.h contains the following helper macros:

// Inodes per block.
#define IPB           (BSIZE / sizeof(struct dinode))

// Block containing inode i
#define IBLOCK(i, sb)     ((i) / IPB + sb.inodestart)

An Inode

An inode is the pointer to the actual data of a file. It defines all the meta-information of the file aside from the name of the file (a file can have multiple names, each pointing to the same inode.)

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

The file types are defined in the stat.h file and are:

#define T_DIR  1   // Directory
#define T_FILE 2   // File
#define T_DEV  3   // Device

The major and minor fields are for device files, which we won't worry about for now. The nlink is the count of the number of links to this file, when it is 0 then the inode is "free" and can be used for a new file. The size is the size of the file in bytes.

The addrs field is 13 unsigned integers in size and represents the block numbers for the first 12 (NDIRECT) blocks in the file. If the file requires more than 12 blocks the final entry in addrs (addrs[NDIRECT]) points to a "indirect" disk block that contains a further NDIRECT = BSIZE / sizeof(uint) == 128 number of block "pointers". That makes the maximum size of a file 128+12 number of 512 byte blocks in size (71680 bytes.)

To compute the block address of a particular byte in a file, the following logic could be used:

// Note: Not necessarily a function that you should need for anything.

uint dblock(uint byte, struct dinode di)
{
  uint indirect[NINDIRECT];
  uint bn = byte/BSIZE, addr;

  if (bn < NDIRECT) addr = di.addrs[bn];
  else {
    // rsect() is found in mkfs.c and will fetch the data in the indirect
    // block pointed to by di.addrs[NDIRECT] into the indirect array:
    rsect(di.addrs[NDIRECT], indirect);
    addr = indirect[bn-NDIRECT];
  }
  return addr;
}

The offset within the block of the byte would be byte & BSIZE (same as byte % BSIZE)

addrs[0 .. 11, 12]
      │ ..  │   │
    ┌─┘     │   └────────────────────┐
    │       └────────────┐           │
┌───────┬───────┬─────┬───────┬──────────────┐
│ blk 0 │ blk 1 │ ... │ blk11 │ Indirect blk │
└───────┴───────┴─────┴───────┴──────────────┘
    ┌──────────────────────────┘│      │
    │         ┌─────────────────┘      │
    │         │             ┌──────────┘
┌────────┬────────┬─────┬──────┐
│ blk 12 │ blk 13 │ ... │ blkN │
└────────┴────────┴─────┴──────┘

The Free Bitmap

The Free Bitmap marks all used blocks on the disk as used as 1 and unused blocks as 0's in a bitmap. Each byte in the bitmap marks 8 disk blocks, so an entire bitmap block can mark up to 4096 disk blocks as being used or free.

Assuming one block for the free bitmap, the bit value for a particular block would be:

bit = bitmap[block / 8] & (1 << (block % 8))

The Data Blocks

These are the where the data for files is stored. They are allocated by scanning the free bitmap for an un-allocated block. The newly allocated block is removed from the free bitmap:

bitmap[block / 8] |= (1 << (block % 8));

Then the block is added to the files block list, either directly in the addrs[] array (if it is one of the first 12 blocks, or the 13th if it is to be the files indirect block) or appended to the indirect block.