Skip to content
Tutorials Center
My learning

Topics

Lesson 50 of 55 ยท Real-World Projects

Project: A Mini File System

Build a tiny file system in JavaScript with directories, paths, inodes, disk blocks and a free-space map. Create, read and delete files, then check the disk.

When you save a document, a surprising amount of bookkeeping happens: free space is found, the bytes are split into blocks, a record is created that remembers where the blocks are, and a folder gets a new entry. In this project you will build all of that yourself. Your mini file system will live on a tiny pretend disk made of 24 blocks, and it will support directories, paths, creating, reading and deleting files, a free-space map, and a checker that finds corruption.

The project puts into practice the ideas of File Systems and Storage: HDD, SSD and Beyond, and it reuses the path rules from The Command Line: First Steps. Real file systems such as ext4 and NTFS are far more complex, but the ingredients you build here are the ones they all have.

The design

A disk is only an array of numbered blocks. Everything else is structure that we put on top. We need four things:

  1. Data blocks hold file contents (and, in real systems, directory contents).
  2. A free-space map (a bitmap) says which blocks are in use.
  3. Inodes are records, one per file or directory, with its type, size and list of blocks.
  4. Directories map names to inode numbers.
flowchart TD
  P["Path: /docs/note.txt"] --> R["Root directory (inode 0)"]
  R -->|"docs"| D["Directory docs (inode 1)"]
  D -->|"note.txt"| N["Inode 2: file, size 20, blocks 0 and 1"]
  N --> B0["Block 0: first 16 bytes"]
  N --> B1["Block 1: the rest"]
  M["Free map: blocks 0 and 1 used"] -.-> B0
  M -.-> B1

Following a path: the root directory leads to a directory, which leads to an inode, which leads to data blocks.

Our block size is only 16 characters so that you can see a file spread over several blocks. Real blocks are usually 4 KiB. To keep the code short, directories live in the inode (as a name-to-inode map) instead of occupying data blocks, which is a simplification we will mention again at the end.

Step 1: the disk and the free map

Start with the lowest layer: a disk that can read and write a block, and a bitmap that finds and releases blocks. Notice that we never write beyond a block's size and that we pick the first free block, which is exactly the simplest allocation policy.

JS Step 1: a disk with a free-space map

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

No output.

The map is # for used and . for free. When block 1 is released, its text is still there, and only the map changed. Only when a new file is written there are the old bytes replaced. This is the same "deleting only frees blocks" behavior described in File Systems.

Step 2: inodes, directories and paths

Now the file system layer. An inode holds type, size and blocks (the list of block numbers). A directory inode instead holds entries, a map from a name to an inode number. Inode 0 is the root directory.

To resolve a path such as /docs/note.txt, start at the root inode and look up each name in the current directory's entries. That is the whole algorithm, and it is how every file system turns names into data. A file is created by splitting its text into block-sized pieces, allocating a block for each, and adding a name to the parent directory.

JS Step 2: create, read, list and delete files

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

No output.

Study the output. The 26-character note needs two blocks, the 8-character todo needs one, and the 40-character readme needs three. After note.txt is removed, its two blocks (0 and 1) are free again, and the next large file's blocks are not contiguous: the file system happily places a file in whatever blocks are free. A file whose pieces are scattered is fragmented. That does not matter on an SSD but is slower on a spinning hard disk, where the head must move between pieces. Finally, the 200-character file needs 13 blocks and fits, but the next file asks for 10 when only 7 remain, so it fails with "not enough free space" and nothing is half-written, because we check the space before we allocate.

Step 3: a file system checker

Real file systems can be damaged by a power cut or a bug in the middle of an update. Programs like fsck (Linux) and chkdsk (Windows) walk the structures and look for contradictions. The simplest checks are the ones about blocks:

  • A block that is marked used but belongs to no file is a leak: it wastes space forever.
  • A block listed by two inodes is cross-linked: two files share the same bytes and one will overwrite the other.
  • A block used by a file but marked free in the map is dangerous: it could be handed out again to another file.

The stand-in below builds a healthy structure, damages it on purpose in three ways and runs the checker after each.

JS Step 3: finding leaks and cross-linked blocks

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

No output.

A checker does not only report: it repairs. A leak is fixed by freeing the block, a stale map entry by marking it used. Cross-linked blocks are harder and may need a copy for each file, and some data may be lost. Journaling (see File Systems) makes most such repairs unnecessary, because the file system records intended changes first and replays or discards them after a crash.

Ideas to extend it

  • Add rename and move: change only the directory entries and show that no block moves.
  • Add hard links: two names for one inode, with a link count, so blocks are released only when the count reaches zero.
  • Store directories in data blocks, as real systems do, so large directories use space.
  • Add permissions to inodes and check them on read, following File Systems.
  • Write a defragmenter that rewrites files into contiguous blocks.
  • Use this mini file system as the back end of the shell from The Command Line: First Steps.

What is real and what is the stand-in? The layers are real: blocks, a free-space bitmap, inodes with block lists, directories mapping names to inodes, path resolution and consistency checking. The stand-ins are simplifications: 16-character blocks instead of 4 KiB, a JavaScript array as the "disk", directories held in the inode instead of in data blocks, no timestamps, permissions or journal, and strings rather than raw bytes.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does the free-space map record?

    A bitmap or similar table marks each block used or free, so the allocator can find space quickly.
  2. 2. How does the mini file system find /docs/note.txt?

    Path resolution walks from the root, using each directory's name-to-inode map to find the next inode.
  3. 3. A 26-character file is stored with 16-character blocks. How many blocks does it need?

    26 / 16 rounded up is 2. The second block is only partly used, which is slack space.
  4. 4. What does the checker call a block that is marked used but belongs to no file?

    Such a block wastes space since nothing can free it until a repair marks it as free.
  5. 5. Why does create() check free space before allocating any blocks?

    Checking first keeps the operation all-or-nothing, which keeps the structures consistent.

Summary

  • A disk is numbered blocks; a file system adds a free-space map, inodes and directories on top.
  • An inode records a file's type, size and block list; the name lives in a directory entry that points to the inode.
  • Path resolution walks from the root, one name at a time.
  • Files can occupy scattered blocks (fragmentation), and the last block is often partly empty (slack space).
  • Deleting frees blocks and the directory entry; the bytes stay until they are reused.
  • A checker finds leaks, cross-linked blocks and stale maps, and journaling reduces how often repair is needed.

Finally, send data across a network: Project: Follow a Packet Across the Internet.