Project 9: File System from Scratch

Design a small on-disk filesystem, implement mkfs/fsck, and mount it via FUSE.

Quick Reference

Attribute Value
Difficulty Advanced
Time Estimate 20-30 hours
Main Programming Language C
Alternative Programming Languages Rust, Go
Coolness Level Very High
Business Potential Medium (storage tooling)
Prerequisites block I/O, structs, bitmaps
Key Topics inodes, block allocation, crash consistency

1. Learning Objectives

By completing this project, you will:

  1. Define an on-disk layout with superblock, inode table, and data blocks.
  2. Implement file and directory operations with correct metadata updates.
  3. Write mkfs and fsck tools for formatting and verification.
  4. Mount the filesystem using FUSE and test with shell commands.

2. All Theory Needed (Per-Concept Breakdown)

On-Disk Layout, Inodes, and Crash Consistency

Fundamentals

A filesystem maps raw blocks to named files and directories. The on-disk layout defines where metadata and data live: a superblock describes global properties, an inode table stores file metadata, and data blocks hold file contents. A directory is just a file that maps names to inode numbers. Allocation uses bitmaps or free lists to track free blocks and inodes. Crash consistency is the guarantee that after a crash, the filesystem can recover to a consistent state. Simple filesystems rely on fsck to repair inconsistencies; journaling filesystems log updates to enable fast recovery.

Deep Dive into the concept

At the heart of a filesystem is a mapping from file offsets to disk blocks. Inode-based designs store per-file metadata (size, timestamps, block pointers). A small inode may contain direct pointers to data blocks and a single indirect block for larger files. This allows small files to be efficient while supporting larger ones. When a file grows, the filesystem allocates new blocks, updates the inode, and writes data to those blocks. Directories map filenames to inode numbers using fixed-size directory entries or variable-length entries. The path resolution algorithm walks each directory component, reading directory blocks and locating the next inode.

Allocation policy affects performance and fragmentation. A bitmap is simple: one bit per block indicates free or used. Finding free blocks requires scanning the bitmap, which can be optimized with cached hints. For inodes, you also need a free inode bitmap. When a file is deleted, the filesystem clears its inode bitmap and marks its data blocks free. Correct ordering of writes matters: if you free blocks before removing directory entries, you can end up with dangling references. If you update the directory entry before the inode is fully written, you can expose garbage to users. Real filesystems use journaling or copy-on-write to avoid these issues, but for a simple FS, you must choose a safe write order and provide fsck to recover.

Crash consistency is about invariants. The core invariants are: every allocated block is referenced by exactly one inode, every directory entry points to a valid inode, and inode sizes match the blocks it references. Your fsck can check these invariants and fix common errors: clearing unreferenced inodes, freeing blocks with no owner, and fixing directory entries that point to invalid inodes.

FUSE (Filesystem in Userspace) lets you implement the filesystem logic in user space. FUSE calls your handlers for open, read, write, mkdir, readdir, etc. Your job is to translate these into inode and block operations. This separation is powerful for learning: you can iterate quickly without kernel crashes, and you can use standard tools like ls and cat to validate behavior.

How this fit on projects

This concept drives Section 3.2 and Section 3.7. It connects to Project 10 (device files) and Project 12 (coreutils).

Definitions & key terms

  • Superblock: global filesystem metadata.
  • Inode: per-file metadata and block pointers.
  • Directory entry: name -> inode mapping.
  • fsck: filesystem checker for consistency.
  • FUSE: userspace filesystem framework.

Mental model diagram (ASCII)

Disk image:
[ super | inode bitmap | block bitmap | inode table | data blocks ]

How it works (step-by-step)

  1. mkfs writes superblock, bitmaps, empty inode table.
  2. Mount reads superblock and loads metadata.
  3. File create allocates inode + data blocks.
  4. Directory entry is created with inode number.
  5. fsck scans and repairs inconsistencies.

Minimal concrete example

struct inode {
    uint32_t size;
    uint32_t direct[8];
};

Common misconceptions

  • “Directories are special objects”: they are files with name->inode entries.
  • “fsck is optional”: without journaling, you need it.

Check-your-understanding questions

  1. Why are inodes useful?
  2. What must be updated when a file is deleted?
  3. Why does write order matter for crash safety?

Check-your-understanding answers

  1. They separate metadata from directory structure.
  2. Directory entry removed, inode freed, blocks freed.
  3. Crashes can leave dangling pointers or leaked blocks.

Real-world applications

  • Ext2-like file systems and embedded storage formats.

Where you’ll apply it

  • This project: Section 3.2, Section 3.7, Section 5.10 Phase 2.
  • Also used in: Project 10, Project 12.

References

  • “OSTEP” Ch. 39-45
  • “Understanding the Linux Kernel” Ch. 12

Key insights

A filesystem is a careful mapping from names to blocks, guarded by invariants.

Summary

By implementing an inode-based filesystem, you make storage abstractions concrete.

Homework/Exercises to practice the concept

  1. Add an indirect block for large files.
  2. Add a directory entry checksum.
  3. Implement a simple journaling log (write-ahead).

Solutions to the homework/exercises

  1. Add one level of indirection and update read/write.
  2. Store checksum in each entry and validate on read.
  3. Log metadata updates and replay on mount.

3. Project Specification

3.1 What You Will Build

A simple inode-based filesystem with mkfs and fsck tools, mountable via FUSE. It supports create/read/write/delete for files and directories.

3.2 Functional Requirements

  1. mkfs creates a valid disk image with superblock, bitmaps, inode table.
  2. FUSE mount supports read/write/create/delete.
  3. Directory traversal and path resolution work.
  4. fsck detects and repairs common inconsistencies.

3.3 Non-Functional Requirements

  • Performance: reasonable for small files (<1MB).
  • Reliability: metadata remains consistent under clean unmount.
  • Usability: simple CLI for mkfs/fsck.

3.4 Example Usage / Output

$ ./mkfs.myfs disk.img 10M
Created myfs: 10 MB, 256 inodes
$ ./myfs_fuse disk.img /mnt/myfs
$ echo "hello" > /mnt/myfs/notes.txt
$ ./fsck.myfs disk.img
myfs: clean

3.5 Data Formats / Schemas / Protocols

  • Superblock: magic, block size, inode count, block count.
  • Directory entry: inode number + name (fixed length).

3.6 Edge Cases

  • Disk full (no free blocks).
  • Too many inodes (inode bitmap full).
  • Deleting open files.

3.7 Real World Outcome

3.7.1 How to Run (Copy/Paste)

./mkfs.myfs disk.img 10M
./myfs_fuse disk.img /mnt/myfs

3.7.2 Golden Path Demo (Deterministic)

  • Use fixed disk size and fixed test operations.

3.7.3 If CLI: exact terminal transcript

$ ./mkfs.myfs disk.img 10M
Created myfs: 10 MB, 256 inodes
$ ./myfs_fuse disk.img /mnt/myfs
$ echo "hello" > /mnt/myfs/notes.txt
$ cat /mnt/myfs/notes.txt
hello
$ ./fsck.myfs disk.img
myfs: clean

Failure demo (deterministic):

$ ./mkfs.myfs disk.img 0M
error: size must be > 0

Exit codes:

  • 0 success
  • 2 invalid args
  • 3 I/O error or corrupted image

4. Solution Architecture

4.1 High-Level Design

Disk image -> Superblock + Bitmaps -> Inodes -> Data blocks

4.2 Key Components

| Component | Responsibility | Key Decisions | |———–|—————-|—————| | mkfs | initialize metadata | fixed block size | | FUSE layer | map ops to inodes | simple inode table | | fsck | verify invariants | bitmap + inode scan |

4.3 Data Structures (No Full Code)

struct superblock {
    uint32_t magic;
    uint32_t block_size;
    uint32_t inode_count;
    uint32_t block_count;
};

4.4 Algorithm Overview

Key Algorithm: Path resolution

  1. Start at root inode.
  2. For each path component, search directory entries.
  3. Load next inode and continue.

Complexity Analysis:

  • Time: O(depth * entries)
  • Space: O(1) additional

5. Implementation Guide

5.1 Development Environment Setup

sudo apt-get install libfuse-dev

5.2 Project Structure

project-root/
|-- myfs.c
|-- mkfs.myfs.c
|-- fsck.myfs.c
`-- Makefile

5.3 The Core Question You’re Answering

“How do raw blocks become durable, named files that survive crashes?”

5.4 Concepts You Must Understand First

  1. Inode layout and block pointers.
  2. Bitmaps for allocation.
  3. Crash consistency and fsck invariants.

5.5 Questions to Guide Your Design

  1. What block size will you choose and why?
  2. How many inodes will you allocate by default?
  3. What is your safe write order?

5.6 Thinking Exercise

Design a 1MB FS with 4KB blocks. How many inodes fit if each is 128 bytes and you reserve 10% metadata?

5.7 The Interview Questions They’ll Ask

  1. What is the purpose of an inode?
  2. How does path resolution work?
  3. Why does journaling improve crash recovery?

5.8 Hints in Layers

Hint 1: Start with a flat file table.

Hint 2: Add inode table + directory entries.

Hint 3: Implement bitmap allocation.

5.9 Books That Will Help

| Topic | Book | Chapter | |——-|——|———| | File systems | OSTEP | 39-45 | | Inodes | Understanding the Linux Kernel | 12 |

5.10 Implementation Phases

Phase 1: mkfs + superblock (4-6 hours)

Goals: create valid disk image.

Phase 2: read/write files (6-10 hours)

Goals: basic file operations.

Phase 3: directories + fsck (8-12 hours)

Goals: path traversal and consistency checks.

5.11 Key Implementation Decisions

| Decision | Options | Recommendation | Rationale | |———-|———|—————-|———–| | Block size | 1K/4K | 4K | matches common FS | | Directory entries | fixed vs variable | fixed | simpler parsing |

6. Testing Strategy

6.1 Test Categories

| Category | Purpose | Examples | |———-|———|———-| | Unit | inode ops | allocate/free inode | | Integration | FUSE mount | create/read/write | | Consistency | fsck | corrupted bitmap |

6.2 Critical Test Cases

  1. Create file, unmount, remount, verify persistence.
  2. Delete file and ensure blocks freed.
  3. Corrupt bitmap and ensure fsck fixes.

6.3 Test Data

Create: /a/b/c.txt
Content: "hello"

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

| Pitfall | Symptom | Solution | |——–|———|———-| | Bad inode offsets | missing files | verify inode table math | | Unflushed metadata | files disappear | flush inodes/superblock | | Directory parse errors | ls fails | validate entry sizes |

7.2 Debugging Strategies

  • Dump raw blocks with hexdump.
  • Add a debug tool that prints inode table.

7.3 Performance Traps

  • Scanning bitmaps linearly for every alloc.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add file permissions.

8.2 Intermediate Extensions

  • Add indirect blocks for larger files.

8.3 Advanced Extensions

  • Add a write-ahead log for metadata.

9. Real-World Connections

9.1 Industry Applications

  • Embedded storage and custom formats.
  • ext2 (reference design).

9.3 Interview Relevance

  • File system internals questions.

10. Resources

10.1 Essential Reading

  • OSTEP Ch. 39-45

10.2 Video Resources

  • File system lectures

10.3 Tools & Documentation

  • FUSE documentation

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain inode layout.
  • I can explain fsck invariants.

11.2 Implementation

  • FUSE mount works and passes tests.

11.3 Growth

  • I can explain path resolution in interviews.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • mkfs + mount + read/write.

Full Completion:

  • fsck with basic repairs.

Excellence (Going Above & Beyond):

  • Journaling or copy-on-write.