Tiny AFS - A Minimal Userspace Filesystem

Building a Tiny “AFS” Filesystem: A Toy Project in User Space

In a teaching-oriented operating-systems course, it’s common to learn the internals of a filesystem by writing one yourself. The AFS project is a minimal, single-level filesystem with:

• No journaling or write-back caching
• A fixed inode table and data region
• Support for files spanning multiple blocks via a simple indirect block

Even in this stripped-down form, you see all the classic pieces: a superblock, inodes, directory entries, and data blocks.

Format-On-Disk: What Happens When You First Create the FS

When you “format” a blank block device for AFS, you run a small program that:

1. Initializes the superblock

   • Sets a magic number and version
   • Records the total number of blocks
   • Marks the first few inodes/data blocks as “in use”

2. Writes the root directory inode

   • Inode 1, link count = 2 (“.” and “/”)
   • Points its single direct block to block 0 of the data region (disk block 2)

3. Creates one sample file

   • Inode 2 → a small hello.txt
   • Allocates one data block, writes "Hello world!\n" text content

4. Builds the root directory block

   • A directory entry (dentry) for hello.txt → Inode 2
   • Pads the rest of the block with zeroes

5. Flushes everything to stable storage

Pseudocode Sketch

def format_disk(device, N_blocks):
  open(device)
  sb = SuperBlock(
    magic = AFS_MAGIC,
    version = 1,
    disk_blocks = N_blocks,
    free_inodes = {2..},
    free_data = {2..}
  )
  write_block(0, sb)

  # Root inode (inode 1)
  root = Inode(
    type = DIR, mode = 0777,
    links = 2,
    direct_blocks = [DATA_BLOCK_0],
    size = BLOCK_SIZE
  )
  write_inode(1, root)

  # Sample file “hello.txt” (inode 2)
  hello = Inode(
    type = FILE, mode = 0666,
    links = 1,
    direct_blocks = [DATA_BLOCK_1],
    size = len("Hello world!\n")
  )
  write_inode(2, hello)

  # Directory block: [ “hello.txt” → inode 2 ]
  dblock = [ DirEntry(name="hello.txt", inode=2), …zeroes… ]
  write_block(DATA_BLOCK_0, dblock)

  # File data block
  write_block(DATA_BLOCK_1, "Hello world!\n")

  fsync_and_close()

On-Disk Layout: Block by Block

After formatting, the first few blocks look like:

Growing the Tree: Subdirectories and Larger Files

Once the basics work, you can experiment:

1. Add a subdirectory subdir/

   • Allocate a new Inode 3, direct → disk block 4
   • In the root dentry, add subdir → Inode 3

2. Create subdir/names.txt

   • Allocate a new Inode 4, direct → disk block 5
   • One subdir dentry for names.txt → Inode 4
   • Write the file data to disk block 5

     

Indirect Block Sketch

Inode: direct = [ ], indirect = (block) [ D1, D2, D3, ... ]
Block D1: data...
Block D2: data...
...

This simple mechanism mirrors how real Unix filesystems let files grow beyond their small array of direct pointers.

By using an indirect block, you can store a file larger than the number of direct pointers in the inode. So, let’s continue with the above example:

3. Store two big files subdir/big_* spanning many blocks
   • Use the inode’s indirect pointer:
     • Allocate one indirect block to hold a list of data-block numbers
     • Write your data across those blocks
       

       

Why This Matters

Even in a homework toy project, you touch:

• Metadata management (superblock, bitmaps)
• Inode layout (mode, size, timestamps, pointers)
• Directory structures (fixed-size entries, padding)
• Block allocation (direct vs. single-level indirect)

Reading and writing zeros, padding, and carefully tracking bitmaps are all things any production filesystem does—only at a far larger scale and with many optimizations (journaling, multi-level trees, caches).

Go Beyond: What’s Next?

For those eager to explore the real assignment and its full specifications, check out the official homework page: columbia-os.github.io/ezfs. In this project, you’ll first format a disk image as above, then implement the filesystem kernel module to mount it and provide a POSIX interface.