Skip to content
Tutorials Center
My learning

Topics

Lesson 63 of 66 ยท Projects and Practice

Project: Build a Mini File System

Build a tiny file system in Python with a block device, free-space bitmap, inodes, directories, hard links and an fsck checker, and see how crashes leave orphan inodes and leaked blocks.

You have read about blocks, bitmaps, inodes, directories and links. In this project you assemble them into a working mini file system, a few dozen lines of Python that behave like a miniature ext2. It is small enough to read in one sitting and complete enough to create directories, store files across blocks, make hard links, free space and detect corruption with an fsck.

The building blocks (all introduced earlier in this chapter) are:

flowchart LR
    P["Path: /home/ana/notes.txt"] --> D["Directories<br/>name -> inode number"]
    D --> I["Inode table<br/>size, link count, block list"]
    I --> B["Block device"]
    BM["Free-space bitmap"] -.->|"tracks"| B

A path is translated to an inode by walking directories, and the inode leads to the data blocks. The bitmap records which blocks are taken.

Step 1: a block device with a bitmap

Start at the bottom. The device stores blocks of 16 bytes, has a bitmap and counts how many reads and writes it performs. Writing text that is longer than a block shows how a file is split and how much is wasted in the last block (internal fragmentation).

Python Step 1: blocks, bitmap and a file split across blocks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The 45-byte text needed three 16-byte blocks, so 3 bytes were wasted at the end of the last one. The list [0, 1, 2] is exactly what an inode stores.

Now the whole thing. Read the code from top to bottom; each method is short.

  • _new_inode and _alloc_block hand out resources, failing with "no space" when they run out.
  • _lookup resolves a path by walking directory tables, as in the Unix file system lesson.
  • write truncates an existing file or creates a new inode and name, then allocates blocks and fills them.
  • link adds a second name and bumps the link count; unlink removes a name and frees the inode only when the count reaches zero.
  • fsck cross-checks the three structures against each other. This is exactly what a real fsck does after a crash.
Python Step 2: a complete mini file system with fsck

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last two lines simulate what a crash in the middle of a file creation can leave behind: an inode that no directory names, and a block marked used that no file owns. fsck finds both. On a real system, orphan inodes go to a lost+found directory and leaked blocks are returned to the free list. A journal would have prevented the inconsistency in the first place.

What is simplified

This is a teaching model. Compared with a real file system:

Real file systems Our mini FS
Directories are stored in data blocks Directories are Python dicts in memory
Inodes have direct and indirect pointers One plain list of blocks
Metadata is written to the disk All metadata is in memory
A superblock holds the global parameters Constants at the top
Permissions, timestamps, owners Not modeled
Caching and journaling None

Extensions

  1. Serialize the metadata. Store the bitmap and inode table in reserved blocks, so a "mount" can rebuild the file system from the block array alone.
  2. Store directories in blocks. Encode each entry as name:ino lines inside the directory's own data blocks.
  3. Indirect blocks. Limit an inode to 4 direct pointers and add a single indirect block.
  4. Journal. Log each operation to a reserved area before applying it, and write recover() that replays committed operations.
  5. Free-space policy. Replace first-fit with an allocator that prefers blocks next to the file's last block, and measure fragmentation.
  6. Symbolic links and a rename that works across directories.
  7. rm -r and df reporting the percentage used.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does the inode, not the directory entry, hold the link count?

    A directory entry is only a name pointing to an inode. The inode knows how many such names exist and when to free the data.
  2. 2. What does fsck report when a block is marked used in the bitmap but no inode lists it?

    The bitmap and the inodes disagree. The space is lost until fsck frees it.
  3. 3. What is internal fragmentation in this model?

    Files occupy whole blocks, so the final partially filled block wastes the rest of its space.
  4. 4. In the model, when is a file's data really freed?

    Unlinking one name just decrements the count. The inode and blocks are released only at zero.

Summary

  • A file system is three cooperating structures: a free-space bitmap over the block device, inodes describing each file, and directories mapping names to inodes.
  • Paths are resolved by walking directories; hard links share an inode and use a link count.
  • A consistency checker compares the structures; crashes between updates leave orphan inodes, leaked blocks or double-owned blocks.
  • Extending the model with serialization, indirect blocks and a journal brings it closer to a real file system.

Next: Project: Disk Scheduling Benchmark