Project 3: Persistent Block-Based Filesystem

Project Overview

Attribute	Details
Difficulty	Intermediate-Advanced (Level 4)
Time Estimate	3-4 weeks
Language	C
Knowledge Area	Filesystems / Storage
Software	Block Devices, FUSE
Main Book	“Operating Systems: Three Easy Pieces” by Arpaci-Dusseau
Prerequisites	Project 2 (In-Memory FUSE Filesystem) completed

What You’ll Build

Extend your FUSE filesystem to persist data to a file (simulating a disk). Implement proper block allocation with bitmaps, inode structures, and data blocks—a mini ext2. You’ll also build mkfs and fsck utilities.

Real World Output:

$ ./mkfs.myfs -s 100M disk.img    # Create 100MB filesystem
Creating filesystem with 25600 blocks (4KB each)...
Writing superblock...
Initializing bitmaps...
Creating root directory (inode 1)...
Filesystem created successfully.

$ ./myfs disk.img /mnt/myfs       # Mount it
$ cp -r ~/Documents/* /mnt/myfs/  # Copy real files
$ echo "Hello persistent world!" > /mnt/myfs/greeting.txt
$ ls -la /mnt/myfs
total 16
drwxr-xr-x 3 user user 4096 Dec 29 10:00 .
drwxr-xr-x 3 root root 4096 Dec 29 09:59 ..
drwxr-xr-x 2 user user 4096 Dec 29 10:00 Documents
-rw-r--r-- 1 user user   24 Dec 29 10:01 greeting.txt

$ fusermount -u /mnt/myfs         # Unmount
$ ./myfs disk.img /mnt/myfs       # Remount - files persist!
$ cat /mnt/myfs/greeting.txt
Hello persistent world!

$ ./fsck.myfs disk.img            # Your own filesystem checker
=== MYFS Filesystem Check ===
Checking superblock... OK (magic 0xDEADBEEF)
Checking inode bitmap... OK
Checking block bitmap... OK
Verifying directory structure... OK
Free inodes: 6371/6400
Free blocks: 24531/25600
Filesystem is consistent.

Learning Objectives

By completing this project, you will:

Design on-disk data structures that survive power cycles and reboots
Implement bitmap-based block allocation with efficient free space tracking
Manage indirect block pointers for large file support (single, double, triple indirection)
Build filesystem utilities (mkfs for creation, fsck for verification)
Handle the persistence challenge: writing structured data to disk correctly
Understand crash consistency issues and why they matter (preparation for Project 4: Journaling)
Debug persistent data structures using hex dumps and custom dump tools
Calculate filesystem capacity limits from first principles

The Core Question You’re Answering

“How do you turn ephemeral bits in RAM into persistent data on disk that survives crashes and reboots?”

This is the fundamental question that separates toy filesystems from real ones. Your in-memory filesystem from Project 2 was elegant, but the moment you unmounted it, everything vanished. Now you’re solving the real problem: persistence.

Every file you’ve ever saved went through this exact process. The PDF you downloaded, the code you wrote yesterday—all exist as carefully managed blocks on disk. You’re about to build that magic yourself.

The complexity explosion:

In-memory: Store data anywhere in RAM
Persistent: Every byte has a fixed disk location that must be calculated
In-memory: Allocate with malloc()
Persistent: Track free space with bitmaps, handle fragmentation
In-memory: No size limits beyond RAM
Persistent: Indirect pointers needed for large files
In-memory: Data disappears on exit
Persistent: Data survives, but crashes can corrupt it

Theoretical Foundation

1. Why Block-Based Storage?

Disks (HDDs and SSDs) operate on fixed-size units, not individual bytes:

Physical Storage Layers:
┌────────────────────────────────────────────────────────────────┐
│  Application: "Write 100 bytes to offset 5000"                 │
└───────────────────────┬────────────────────────────────────────┘
                        │
                        ▼
┌────────────────────────────────────────────────────────────────┐
│  Filesystem: "Write block 1 (containing offset 5000)"          │
│             Block = 4096 bytes, offset 5000 is in block 1      │
└───────────────────────┬────────────────────────────────────────┘
                        │
                        ▼
┌────────────────────────────────────────────────────────────────┐
│  Block Device: "Write LBA (Logical Block Address) sector"      │
│               Sector = 512 or 4096 bytes                       │
└───────────────────────┬────────────────────────────────────────┘
                        │
                        ▼
┌────────────────────────────────────────────────────────────────┐
│  Physical: HDD platter sectors or SSD flash pages              │
└────────────────────────────────────────────────────────────────┘

Why not byte-addressable storage?

Disk controllers are optimized for block transfers
Metadata overhead would be enormous for byte-level tracking
Caching works better with fixed-size units
Write amplification would destroy SSDs

Block size tradeoffs:

Block Size	Pros	Cons
1KB	Less wasted space for small files	More blocks to track, slower large file I/O
4KB	Matches page size, good balance	~2KB average waste per small file
64KB	Excellent sequential performance	Huge waste for small files

Our choice: 4KB blocks - This matches the Linux page size, provides good performance, and is the most common choice in modern filesystems.

2. On-Disk Layout Design

A typical Unix filesystem organizes disk space in a structured layout:

┌─────────────────────────────────────────────────────────────────────────────┐
│                         MYFS On-Disk Layout                                  │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                              │
│   Block 0        ┌─────────────────────────────────────────────────────┐    │
│   (4096 bytes)   │                    SUPERBLOCK                        │    │
│                  │  - Magic number (0xDEADBEEF)                         │    │
│                  │  - Version, block size, total blocks                 │    │
│                  │  - Free block/inode counts                           │    │
│                  │  - Bitmap and inode table locations                  │    │
│                  │  - Mount time, write time, UUID                      │    │
│                  └─────────────────────────────────────────────────────┘    │
│                                                                              │
│   Block 1-N      ┌─────────────────────────────────────────────────────┐    │
│                  │                  INODE BITMAP                        │    │
│                  │  - 1 bit per inode (0=free, 1=used)                  │    │
│                  │  - For 6400 inodes: 6400/8 = 800 bytes = 1 block    │    │
│                  └─────────────────────────────────────────────────────┘    │
│                                                                              │
│   Block N+1-M    ┌─────────────────────────────────────────────────────┐    │
│                  │                  BLOCK BITMAP                        │    │
│                  │  - 1 bit per data block (0=free, 1=used)             │    │
│                  │  - For 25600 blocks: 25600/8 = 3200 bytes = 1 block │    │
│                  └─────────────────────────────────────────────────────┘    │
│                                                                              │
│   Block M+1-P    ┌─────────────────────────────────────────────────────┐    │
│                  │                  INODE TABLE                         │    │
│                  │  - Array of fixed-size inode structures              │    │
│                  │  - 6400 inodes × 128 bytes = 800KB = 200 blocks     │    │
│                  └─────────────────────────────────────────────────────┘    │
│                                                                              │
│   Block P+1      ┌─────────────────────────────────────────────────────┐    │
│   to End         │                   DATA BLOCKS                        │    │
│                  │  - File contents                                     │    │
│                  │  - Directory entries                                 │    │
│                  │  - Indirect block pointer arrays                     │    │
│                  └─────────────────────────────────────────────────────┘    │
│                                                                              │
└─────────────────────────────────────────────────────────────────────────────┘

Layout calculation for a 100MB filesystem:

Total size:     100 MB = 104,857,600 bytes
Block size:     4096 bytes
Total blocks:   104,857,600 / 4096 = 25,600 blocks

Superblock:     1 block (block 0)
Inode count:    25,600 / 4 = 6,400 inodes (1 inode per 4 blocks is common)
Inode bitmap:   ceil(6,400 / (8 * 4096)) = 1 block
Block bitmap:   ceil(25,600 / (8 * 4096)) = 1 block
Inode table:    ceil(6,400 * 128 / 4096) = 200 blocks

Metadata total: 1 + 1 + 1 + 200 = 203 blocks
Data blocks:    25,600 - 203 = 25,397 available for file data

3. Superblock Design

The superblock is the filesystem’s master record. If it’s corrupted, the filesystem is unreadable.

#define MYFS_MAGIC      0xDEADBEEF
#define MYFS_VERSION    1
#define BLOCK_SIZE      4096
#define INODE_SIZE      128

struct myfs_superblock {
    // Identification
    uint32_t s_magic;              // Magic number (0xDEADBEEF)
    uint32_t s_version;            // Filesystem version
    uint8_t  s_uuid[16];           // Unique filesystem ID

    // Geometry
    uint32_t s_block_size;         // Block size in bytes (4096)
    uint32_t s_blocks_count;       // Total blocks in filesystem
    uint32_t s_inodes_count;       // Total inodes

    // Free space tracking
    uint32_t s_free_blocks_count;  // Free blocks remaining
    uint32_t s_free_inodes_count;  // Free inodes remaining
    uint32_t s_first_free_block;   // Hint: first free block number
    uint32_t s_first_free_inode;   // Hint: first free inode number

    // Layout pointers (block numbers)
    uint32_t s_inode_bitmap_block; // Start of inode bitmap
    uint32_t s_block_bitmap_block; // Start of block bitmap
    uint32_t s_inode_table_block;  // Start of inode table
    uint32_t s_first_data_block;   // First usable data block

    // Derived counts
    uint32_t s_inode_bitmap_blocks;// Number of inode bitmap blocks
    uint32_t s_block_bitmap_blocks;// Number of block bitmap blocks
    uint32_t s_inode_table_blocks; // Number of inode table blocks

    // Timestamps
    uint64_t s_mount_time;         // Last mount timestamp
    uint64_t s_write_time;         // Last write timestamp
    uint64_t s_create_time;        // Filesystem creation time

    // State
    uint16_t s_mount_count;        // Number of mounts since fsck
    uint16_t s_state;              // Clean/dirty flag

    // Label
    char     s_label[64];          // Volume label

    // Padding to fill block
    uint8_t  s_reserved[3880];     // Pad to exactly 4096 bytes
} __attribute__((packed));

// Verify size at compile time
_Static_assert(sizeof(struct myfs_superblock) == BLOCK_SIZE,
               "Superblock must be exactly one block");

Why each field matters:

s_magic: Identifies this as a MYFS filesystem, not random data
s_uuid: Uniquely identifies this specific filesystem instance
s_free_*_count: Avoids full bitmap scans for every allocation
s_first_free_*: Optimization hints for faster allocation
s_state: Detect unclean unmounts (dirty = crashed)

4. Bitmap-Based Block Allocation

Bitmaps provide efficient free space tracking with O(1) status checks:

Block Bitmap Example (first 64 blocks):
┌────────────────────────────────────────────────────────────────────────────┐
│ Byte 0:  11111111  (blocks 0-7 used - metadata)                            │
│ Byte 1:  11111111  (blocks 8-15 used - metadata)                           │
│ Byte 2:  11111111  (blocks 16-23 used - metadata)                          │
│ Byte 3:  11111111  (blocks 24-31 used - metadata)                          │
│ ...                                                                         │
│ Byte 25: 11111111  (blocks 200-207 used - metadata ends around here)       │
│ Byte 26: 00000111  (blocks 208-215: 208-210 used, 211-215 free)            │
│ Byte 27: 00000000  (blocks 216-223: all free)                              │
│ ...                                                                         │
└────────────────────────────────────────────────────────────────────────────┘

Legend: 1 = block used, 0 = block free
Bit order: LSB first (bit 0 = lowest block number in byte)

Bitmap operations:

// Check if bit N is set (block N is used)
#define BITMAP_GET(bitmap, n) \
    ((bitmap[(n) / 8] >> ((n) % 8)) & 1)

// Set bit N (mark block N as used)
#define BITMAP_SET(bitmap, n) \
    (bitmap[(n) / 8] |= (1 << ((n) % 8)))

// Clear bit N (mark block N as free)
#define BITMAP_CLR(bitmap, n) \
    (bitmap[(n) / 8] &= ~(1 << ((n) % 8)))

// Find first free bit (first free block)
int bitmap_find_free(uint8_t *bitmap, uint32_t total_bits) {
    uint32_t total_bytes = (total_bits + 7) / 8;

    for (uint32_t byte_idx = 0; byte_idx < total_bytes; byte_idx++) {
        // Skip fully used bytes (all 1s)
        if (bitmap[byte_idx] == 0xFF) {
            continue;
        }

        // Found a byte with at least one free bit
        for (int bit = 0; bit < 8; bit++) {
            uint32_t block_num = byte_idx * 8 + bit;
            if (block_num >= total_bits) {
                return -1;  // Past end of valid blocks
            }
            if (!(bitmap[byte_idx] & (1 << bit))) {
                return block_num;  // Found free block
            }
        }
    }
    return -1;  // No free blocks
}

// Optimized: find free starting from hint
int bitmap_find_free_from(uint8_t *bitmap, uint32_t hint,
                          uint32_t total_bits) {
    // Search from hint to end
    uint32_t start_byte = hint / 8;
    uint32_t total_bytes = (total_bits + 7) / 8;

    for (uint32_t i = start_byte; i < total_bytes; i++) {
        if (bitmap[i] == 0xFF) continue;

        for (int bit = 0; bit < 8; bit++) {
            uint32_t block_num = i * 8 + bit;
            if (block_num < hint) continue;  // Skip before hint
            if (block_num >= total_bits) return -1;
            if (!BITMAP_GET(bitmap, block_num)) {
                return block_num;
            }
        }
    }

    // Wrap around: search from beginning to hint
    for (uint32_t i = 0; i < start_byte; i++) {
        if (bitmap[i] == 0xFF) continue;

        for (int bit = 0; bit < 8; bit++) {
            uint32_t block_num = i * 8 + bit;
            if (block_num >= hint) break;
            if (!BITMAP_GET(bitmap, block_num)) {
                return block_num;
            }
        }
    }

    return -1;  // Filesystem full
}

5. Inode Structure for Persistence

On-disk inodes must be fixed-size for direct addressing:

#define DIRECT_BLOCKS   12
#define INDIRECT_BLOCKS 3   // Single, double, triple indirect
#define TOTAL_BLOCK_PTRS (DIRECT_BLOCKS + INDIRECT_BLOCKS)

struct myfs_inode {
    // File type and permissions (uses standard Unix mode bits)
    uint16_t i_mode;              // S_IFREG, S_IFDIR, permissions

    // Ownership
    uint16_t i_uid;               // Owner user ID
    uint16_t i_gid;               // Owner group ID

    // Link count (for hard links)
    uint16_t i_links_count;       // Number of hard links

    // Size (64-bit for large files)
    uint32_t i_size_lo;           // File size, lower 32 bits
    uint32_t i_size_hi;           // File size, upper 32 bits

    // Timestamps (Unix epoch seconds)
    uint32_t i_atime;             // Last access time
    uint32_t i_mtime;             // Last modification time
    uint32_t i_ctime;             // Last status change time
    uint32_t i_crtime;            // Creation time

    // Block count (in 512-byte units for compatibility)
    uint32_t i_blocks;            // Number of 512-byte sectors used

    // Flags (for future extensions)
    uint32_t i_flags;             // Immutable, append-only, etc.

    // Block pointers
    uint32_t i_block[15];         // Block pointers:
                                  // [0-11]:  Direct blocks
                                  // [12]:    Single indirect
                                  // [13]:    Double indirect
                                  // [14]:    Triple indirect

    // Generation (for NFS)
    uint32_t i_generation;        // File version for NFS

    // Reserved for future use
    uint32_t i_reserved[6];       // Padding to 128 bytes
} __attribute__((packed));

_Static_assert(sizeof(struct myfs_inode) == INODE_SIZE,
               "Inode must be exactly 128 bytes");

Inode addressing:

// Calculate disk location of inode N
off_t inode_offset(struct myfs_state *fs, uint32_t ino) {
    // Inodes are numbered from 1 (inode 0 is reserved/invalid)
    if (ino < 1 || ino > fs->sb.s_inodes_count) {
        return -1;  // Invalid inode number
    }

    uint32_t inode_index = ino - 1;  // Convert to 0-based index
    uint32_t block_in_table = inode_index / (BLOCK_SIZE / INODE_SIZE);
    uint32_t offset_in_block = (inode_index % (BLOCK_SIZE / INODE_SIZE)) * INODE_SIZE;

    uint32_t abs_block = fs->sb.s_inode_table_block + block_in_table;
    return (off_t)abs_block * BLOCK_SIZE + offset_in_block;
}

6. Indirect Block Pointers

For files larger than 12 x 4KB = 48KB, we need indirection:

┌──────────────────────────────────────────────────────────────────────────────┐
│                        INDIRECT BLOCK POINTER STRUCTURE                       │
├──────────────────────────────────────────────────────────────────────────────┤
│                                                                               │
│  INODE                                                                        │
│  ┌────────────────────────────────────────────────────────────────────────┐  │
│  │ i_block[0]   ──────────────►  Data Block 0                              │  │
│  │ i_block[1]   ──────────────►  Data Block 1                              │  │
│  │ i_block[2]   ──────────────►  Data Block 2                              │  │
│  │    ...                          ...                                      │  │
│  │ i_block[11]  ──────────────►  Data Block 11                             │  │
│  │                                                                          │  │
│  │              DIRECT: 12 blocks × 4KB = 48 KB                            │  │
│  └────────────────────────────────────────────────────────────────────────┘  │
│                                                                               │
│  ┌────────────────────────────────────────────────────────────────────────┐  │
│  │ i_block[12]  ──────►  [Indirect Block]                                  │  │
│  │                        ┌─────────────────────────────────────────┐      │  │
│  │                        │ ptr[0]   ──────►  Data Block 12         │      │  │
│  │                        │ ptr[1]   ──────►  Data Block 13         │      │  │
│  │                        │ ptr[2]   ──────►  Data Block 14         │      │  │
│  │                        │   ...                                   │      │  │
│  │                        │ ptr[1023]──────►  Data Block 1035       │      │  │
│  │                        └─────────────────────────────────────────┘      │  │
│  │                                                                          │  │
│  │              SINGLE INDIRECT: 1024 blocks × 4KB = 4 MB                  │  │
│  └────────────────────────────────────────────────────────────────────────┘  │
│                                                                               │
│  ┌────────────────────────────────────────────────────────────────────────┐  │
│  │ i_block[13]  ──────►  [Double Indirect Block]                          │  │
│  │                        ┌─────────────────────────────────────────┐      │  │
│  │                        │ ptr[0]   ──────►  [Indirect Block 0]    │      │  │
│  │                        │                    ├─► Data Block 1036  │      │  │
│  │                        │                    ├─► Data Block 1037  │      │  │
│  │                        │                    └─► ...              │      │  │
│  │                        │ ptr[1]   ──────►  [Indirect Block 1]    │      │  │
│  │                        │   ...                                   │      │  │
│  │                        │ ptr[1023]──────►  [Indirect Block 1023] │      │  │
│  │                        └─────────────────────────────────────────┘      │  │
│  │                                                                          │  │
│  │              DOUBLE INDIRECT: 1024² blocks × 4KB = 4 GB                 │  │
│  └────────────────────────────────────────────────────────────────────────┘  │
│                                                                               │
│  ┌────────────────────────────────────────────────────────────────────────┐  │
│  │ i_block[14]  ──────►  [Triple Indirect Block]                          │  │
│  │                        ┌─────────────────────────────────────────┐      │  │
│  │                        │ ptr[0] ──► [Double Indirect 0]          │      │  │
│  │                        │            └──► [Indirect 0]            │      │  │
│  │                        │                  └──► Data Blocks       │      │  │
│  │                        │ ptr[1] ──► [Double Indirect 1]          │      │  │
│  │                        │   ...                                   │      │  │
│  │                        └─────────────────────────────────────────┘      │  │
│  │                                                                          │  │
│  │              TRIPLE INDIRECT: 1024³ blocks × 4KB = 4 TB                 │  │
│  └────────────────────────────────────────────────────────────────────────┘  │
│                                                                               │
│  TOTAL MAXIMUM FILE SIZE: 48KB + 4MB + 4GB + 4TB ≈ 4 TB                      │
│                                                                               │
└──────────────────────────────────────────────────────────────────────────────┘

Maximum file size calculation (4KB blocks, 4-byte pointers):

Level	Formula	Blocks	Size
Direct	12	12	48 KB
Single Indirect	4096/4 = 1024	1,024	4 MB
Double Indirect	1024²	1,048,576	4 GB
Triple Indirect	1024³	1,073,741,824	4 TB
Total		~1 billion	~4 TB

Block mapping implementation:

#define PTRS_PER_BLOCK (BLOCK_SIZE / sizeof(uint32_t))  // 1024 for 4KB blocks

// Map logical block number to physical block number
// Returns 0 if block is not allocated (sparse file hole)
uint32_t inode_get_block(struct myfs_state *fs, struct myfs_inode *inode,
                         uint32_t logical_block) {
    // Direct blocks (0-11)
    if (logical_block < DIRECT_BLOCKS) {
        return inode->i_block[logical_block];
    }
    logical_block -= DIRECT_BLOCKS;

    // Single indirect (next 1024 blocks)
    if (logical_block < PTRS_PER_BLOCK) {
        if (inode->i_block[12] == 0) return 0;  // Hole

        uint32_t indirect[PTRS_PER_BLOCK];
        read_block(fs, inode->i_block[12], indirect);
        return indirect[logical_block];
    }
    logical_block -= PTRS_PER_BLOCK;

    // Double indirect (next 1024² blocks)
    if (logical_block < PTRS_PER_BLOCK * PTRS_PER_BLOCK) {
        if (inode->i_block[13] == 0) return 0;  // Hole

        uint32_t dbl_indirect[PTRS_PER_BLOCK];
        read_block(fs, inode->i_block[13], dbl_indirect);

        uint32_t idx1 = logical_block / PTRS_PER_BLOCK;
        uint32_t idx2 = logical_block % PTRS_PER_BLOCK;

        if (dbl_indirect[idx1] == 0) return 0;  // Hole

        uint32_t indirect[PTRS_PER_BLOCK];
        read_block(fs, dbl_indirect[idx1], indirect);
        return indirect[idx2];
    }
    logical_block -= PTRS_PER_BLOCK * PTRS_PER_BLOCK;

    // Triple indirect (remaining blocks up to 4TB)
    if (logical_block < PTRS_PER_BLOCK * PTRS_PER_BLOCK * PTRS_PER_BLOCK) {
        if (inode->i_block[14] == 0) return 0;  // Hole

        uint32_t triple[PTRS_PER_BLOCK];
        read_block(fs, inode->i_block[14], triple);

        uint32_t idx1 = logical_block / (PTRS_PER_BLOCK * PTRS_PER_BLOCK);
        uint32_t rem = logical_block % (PTRS_PER_BLOCK * PTRS_PER_BLOCK);
        uint32_t idx2 = rem / PTRS_PER_BLOCK;
        uint32_t idx3 = rem % PTRS_PER_BLOCK;

        if (triple[idx1] == 0) return 0;

        uint32_t dbl_indirect[PTRS_PER_BLOCK];
        read_block(fs, triple[idx1], dbl_indirect);

        if (dbl_indirect[idx2] == 0) return 0;

        uint32_t indirect[PTRS_PER_BLOCK];
        read_block(fs, dbl_indirect[idx2], indirect);
        return indirect[idx3];
    }

    return 0;  // Beyond maximum file size
}

7. Directory Entry Format

Directories are files containing variable-length entries:

#define MAX_FILENAME_LEN 255

struct myfs_dirent {
    uint32_t d_ino;           // Inode number (0 = deleted entry)
    uint16_t d_rec_len;       // Total record length (for traversal)
    uint8_t  d_name_len;      // Actual filename length
    uint8_t  d_file_type;     // File type hint (for readdir optimization)
    char     d_name[];        // Filename (NOT null-terminated on disk)
} __attribute__((packed));

// File type values
#define MYFS_FT_UNKNOWN  0
#define MYFS_FT_REG_FILE 1
#define MYFS_FT_DIR      2
#define MYFS_FT_SYMLINK  7

Directory entry layout:

┌──────────────────────────────────────────────────────────────────────────────┐
│                        DIRECTORY DATA BLOCK                                   │
├──────────────────────────────────────────────────────────────────────────────┤
│                                                                               │
│  Offset 0:                                                                    │
│  ┌────────┬────────┬────────┬────────┬───────────────────────┐               │
│  │ d_ino  │d_rec   │d_name  │d_file  │ d_name               │               │
│  │  (4)   │_len(2) │_len(1) │_type(1)│ (d_name_len bytes)   │               │
│  ├────────┼────────┼────────┼────────┼───────────────────────┤               │
│  │   2    │   12   │   1    │   2    │  "."                 │               │
│  └────────┴────────┴────────┴────────┴───────────────────────┘               │
│        ^                                                                      │
│        └── d_rec_len (12) = 8 header + 1 name + 3 padding to 4-byte align   │
│                                                                               │
│  Offset 12:                                                                   │
│  ┌────────┬────────┬────────┬────────┬───────────────────────┐               │
│  │   2    │   12   │   2    │   2    │  ".."                │               │
│  └────────┴────────┴────────┴────────┴───────────────────────┘               │
│                                                                               │
│  Offset 24:                                                                   │
│  ┌────────┬────────┬────────┬────────┬───────────────────────┐               │
│  │   15   │   20   │   9    │   1    │  "hello.txt"         │               │
│  └────────┴────────┴────────┴────────┴───────────────────────┘               │
│                                                                               │
│  Offset 44:                                                                   │
│  ┌────────┬────────┬────────┬────────┬───────────────────────┐               │
│  │   16   │  4052  │   6    │   2    │  "subdir"            │               │
│  └────────┴────────┴────────┴────────┴───────────────────────┘               │
│        ^                                                                      │
│        └── Last entry has d_rec_len extending to end of block               │
│                                                                               │
└──────────────────────────────────────────────────────────────────────────────┘

8. The Crash Consistency Problem

What happens if power fails during a write?

Consider creating a new file:

Steps to create "/newfile.txt":
Allocate inode (mark bit in inode bitmap)
Initialize inode (set mode, size, timestamps)
Allocate data block (mark bit in block bitmap)
Write data to block
Update inode block pointers
Add directory entry in parent
Update parent inode (mtime, size)
Update superblock (free counts)

Crash scenarios:

Crash After Step	State	Problem
1	Inode bit set, no inode data	Orphaned inode, bitmap says used
3	Block bit set, no data	Orphaned block, bitmap says used
5	Inode points to block	Data exists but no directory entry
6	Directory has entry	File accessible, might have stale data
7	All done except superblock	Free counts wrong, minor issue

This project intentionally doesn’t solve crash consistency. You’ll add journaling in Project 4 to make writes atomic. For now, your filesystem may be inconsistent after crashes.

Project Specification

Functional Requirements

1. mkfs.myfs Utility

Create a formatted filesystem image:

$ ./mkfs.myfs --help
Usage: mkfs.myfs [OPTIONS] <image_file>
Options:
  -s, --size SIZE     Filesystem size (e.g., 10M, 1G, default: 100M)
  -b, --block-size N  Block size in bytes (1024, 2048, 4096, default: 4096)
  -i, --inodes N      Number of inodes (default: blocks/4)
  -L, --label LABEL   Volume label (max 63 chars)
  -h, --help          Show this help

$ ./mkfs.myfs -s 100M disk.img
Creating filesystem with 25600 blocks of 4096 bytes...
  Superblock at block 0
  Inode bitmap at block 1 (1 block)
  Block bitmap at block 2 (1 block)
  Inode table at blocks 3-202 (200 blocks, 6400 inodes)
  First data block: 203
  Data blocks available: 25397
Creating root directory (inode 1)...
Writing superblock...
Filesystem created successfully.

mkfs Requirements:

Create sparse file of specified size
Initialize superblock with correct values
Set up zeroed bitmaps
Create root directory inode with “.” and “..” entries
Mark metadata blocks as used in block bitmap
Calculate layout based on filesystem size

2. FUSE Filesystem (myfs)

Mount and operate on filesystem images:

$ ./myfs disk.img /mnt/myfs
Mounted MYFS filesystem (25397 blocks free)
# Runs in background, use -f for foreground, -d for debug

Required FUSE Operations:

Operation	Description
`getattr`	Return file/directory attributes (stat)
`readdir`	List directory contents
`open`	Open file for reading/writing
`read`	Read file data
`write`	Write file data
`create`	Create new file
`unlink`	Delete file
`mkdir`	Create directory
`rmdir`	Remove empty directory
`rename`	Rename file or directory
`truncate`	Change file size
`utimens`	Update timestamps
`chmod`	Change permissions
`chown`	Change ownership
`statfs`	Return filesystem statistics
`fsync`	Flush file data to disk
`destroy`	Clean shutdown on unmount

3. Block Allocation

Track free/used blocks with bitmap
Allocate blocks on write
Free blocks on truncate/unlink
Update superblock free counts
Handle ENOSPC when full

4. Large File Support

Direct blocks for files up to 48KB
Single indirect for files up to 4MB
Double indirect for files up to 4GB
(Optional) Triple indirect for files up to 4TB

5. fsck.myfs Utility

Verify filesystem consistency:

$ ./fsck.myfs disk.img
=== MYFS Filesystem Check ===
Phase 1: Checking superblock...
  Magic: 0xDEADBEEF OK
  Version: 1 OK
  Block size: 4096 OK
  Blocks: 25600 OK
  Inodes: 6400 OK

Phase 2: Checking inode bitmap...
  Used inodes: 29
  Free inodes: 6371
  Bitmap consistent: OK

Phase 3: Checking block bitmap...
  Used blocks: 1069
  Free blocks: 24531
  Bitmap consistent: OK

Phase 4: Verifying directory structure...
  Root inode (1): OK
  Directories checked: 5
  Files checked: 24
  All entries valid: OK

Phase 5: Checking reference counts...
  All link counts correct: OK

Summary:
  Free inodes: 6371/6400
  Free blocks: 24531/25600
  Filesystem is CONSISTENT

fsck Checks:

Superblock magic and values
Bitmap matches actual allocations
Directory entries point to valid inodes
No orphaned blocks (allocated but unreferenced)
Link counts match actual directory references
Root directory exists and is valid

Non-Functional Requirements

Support filesystems from 1MB to 1TB
Support individual files up to 4GB (with double indirect)
Handle thousands of files
Mount time under 1 second
Reasonable throughput (>10 MB/s sequential)

Solution Architecture

Component Design

┌─────────────────────────────────────────────────────────────────────────────┐
│                              USER SPACE                                      │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                              │
│   ┌─────────────────┐  ┌─────────────────┐  ┌─────────────────┐            │
│   │    mkfs.myfs    │  │      myfs       │  │   fsck.myfs     │            │
│   │   (standalone)  │  │  (FUSE daemon)  │  │  (standalone)   │            │
│   └────────┬────────┘  └────────┬────────┘  └────────┬────────┘            │
│            │                    │                    │                      │
│            └────────────────────┼────────────────────┘                      │
│                                 │                                           │
│                    ┌────────────▼────────────┐                              │
│                    │    FUSE Callbacks       │                              │
│                    │  (myfs_getattr, etc.)   │                              │
│                    └────────────┬────────────┘                              │
│                                 │                                           │
│                    ┌────────────▼────────────┐                              │
│                    │    Filesystem Core      │                              │
│                    │                         │                              │
│  ┌─────────────────┴─────────────────────────┴─────────────────────┐       │
│  │                                                                   │       │
│  │  ┌─────────────┐  ┌─────────────┐  ┌─────────────┐              │       │
│  │  │  Superblock │  │   Bitmap    │  │   Inode     │              │       │
│  │  │   Manager   │  │   Manager   │  │   Manager   │              │       │
│  │  │             │  │             │  │             │              │       │
│  │  │ read_sb()   │  │ alloc_blk() │  │ read_ino()  │              │       │
│  │  │ write_sb()  │  │ free_blk()  │  │ write_ino() │              │       │
│  │  │ sync_sb()   │  │ alloc_ino() │  │ get_block() │              │       │
│  │  │             │  │ free_ino()  │  │ set_block() │              │       │
│  │  └─────────────┘  └─────────────┘  └─────────────┘              │       │
│  │                                                                   │       │
│  │  ┌─────────────┐  ┌─────────────┐  ┌─────────────┐              │       │
│  │  │  Directory  │  │    File     │  │    Path     │              │       │
│  │  │   Manager   │  │   Manager   │  │   Resolver  │              │       │
│  │  │             │  │             │  │             │              │       │
│  │  │ dir_lookup()│  │ file_read() │  │ resolve()   │              │       │
│  │  │ dir_add()   │  │ file_write()│  │ parent()    │              │       │
│  │  │ dir_remove()│  │ truncate()  │  │ basename()  │              │       │
│  │  └─────────────┘  └─────────────┘  └─────────────┘              │       │
│  │                                                                   │       │
│  └───────────────────────────┬───────────────────────────────────────┘       │
│                              │                                               │
│                    ┌─────────▼─────────┐                                    │
│                    │   Block I/O Layer │                                    │
│                    │                   │                                    │
│                    │   read_block()    │                                    │
│                    │   write_block()   │                                    │
│                    │   sync_all()      │                                    │
│                    └─────────┬─────────┘                                    │
│                              │                                               │
├──────────────────────────────┼──────────────────────────────────────────────┤
│                              │          DISK IMAGE FILE                      │
│                    ┌─────────▼─────────────────────────────────┐            │
│                    │  [SB][Inode BM][Block BM][Inode Table][Data...]        │
│                    └───────────────────────────────────────────┘            │
│                                                                              │
└─────────────────────────────────────────────────────────────────────────────┘

Key Data Structures

// Filesystem runtime state (in-memory)
struct myfs_state {
    int                     disk_fd;           // Open file descriptor for image
    char                   *disk_path;         // Path to disk image
    struct myfs_superblock  sb;                // Cached superblock
    uint8_t                *inode_bitmap;      // Cached inode bitmap
    uint8_t                *block_bitmap;      // Cached block bitmap
    int                     sb_dirty;          // Superblock needs write
    int                     ino_bm_dirty;      // Inode bitmap needs write
    int                     blk_bm_dirty;      // Block bitmap needs write
    pthread_mutex_t         lock;              // Global filesystem lock
};

// For caching frequently accessed inodes (optional optimization)
struct inode_cache_entry {
    uint32_t            ino;
    struct myfs_inode   inode;
    int                 dirty;
    time_t              last_access;
};

// Block buffer for I/O
struct block_buffer {
    uint32_t block_num;
    uint8_t  data[BLOCK_SIZE];
    int      dirty;
    int      pin_count;
};

Core Functions API

// === Block I/O Layer ===
int  read_block(struct myfs_state *fs, uint32_t blk_num, void *buf);
int  write_block(struct myfs_state *fs, uint32_t blk_num, const void *buf);
int  zero_block(struct myfs_state *fs, uint32_t blk_num);
int  sync_all(struct myfs_state *fs);

// === Superblock Manager ===
int  sb_read(struct myfs_state *fs);
int  sb_write(struct myfs_state *fs);
void sb_update_free_counts(struct myfs_state *fs);

// === Bitmap Manager ===
int      alloc_inode(struct myfs_state *fs);
void     free_inode(struct myfs_state *fs, uint32_t ino);
int      alloc_block(struct myfs_state *fs);
void     free_block(struct myfs_state *fs, uint32_t blk);
int      bitmap_sync(struct myfs_state *fs);

// === Inode Manager ===
int      read_inode(struct myfs_state *fs, uint32_t ino, struct myfs_inode *inode);
int      write_inode(struct myfs_state *fs, uint32_t ino, struct myfs_inode *inode);
uint32_t inode_get_block(struct myfs_state *fs, struct myfs_inode *inode,
                         uint32_t logical_blk);
int      inode_set_block(struct myfs_state *fs, struct myfs_inode *inode,
                         uint32_t ino, uint32_t logical_blk, uint32_t phys_blk);
int      inode_truncate(struct myfs_state *fs, struct myfs_inode *inode,
                        uint32_t ino, off_t new_size);

// === Directory Manager ===
int      dir_lookup(struct myfs_state *fs, struct myfs_inode *dir,
                    const char *name, uint32_t *ino_out);
int      dir_add_entry(struct myfs_state *fs, struct myfs_inode *dir,
                       uint32_t dir_ino, const char *name, uint32_t ino, uint8_t type);
int      dir_remove_entry(struct myfs_state *fs, struct myfs_inode *dir,
                          uint32_t dir_ino, const char *name);
int      dir_iterate(struct myfs_state *fs, struct myfs_inode *dir,
                     int (*callback)(const char *name, uint32_t ino, uint8_t type, void *ctx),
                     void *ctx);

// === File Manager ===
ssize_t  file_read(struct myfs_state *fs, struct myfs_inode *inode,
                   char *buf, size_t size, off_t offset);
ssize_t  file_write(struct myfs_state *fs, struct myfs_inode *inode, uint32_t ino,
                    const char *buf, size_t size, off_t offset);

// === Path Resolver ===
int      resolve_path(struct myfs_state *fs, const char *path, uint32_t *ino_out);
int      resolve_parent(struct myfs_state *fs, const char *path,
                        uint32_t *parent_ino_out, char *name_out);

Implementation Guide

Phase 1: mkfs Utility (Days 1-4)

Goals:

Create disk image file of specified size
Initialize all on-disk structures
Create root directory

Steps:

Parse command-line arguments

int main(int argc, char *argv[]) {
 char *image_path = NULL;
 size_t size = 100 * 1024 * 1024;  // Default 100MB
 uint32_t block_size = 4096;
 char label[64] = "myfs";

 // Parse -s, -b, -L options with getopt
 // ...

 return mkfs_main(image_path, size, block_size, label);
}

Calculate filesystem layout

int mkfs_main(const char *path, size_t total_size, uint32_t block_size,
           const char *label) {
 // Calculate layout
 uint32_t total_blocks = total_size / block_size;
 uint32_t inode_count = total_blocks / 4;  // 1 inode per 4 blocks

 // Bitmap sizes
 uint32_t ino_bitmap_blocks = (inode_count + block_size * 8 - 1) / (block_size * 8);
 uint32_t blk_bitmap_blocks = (total_blocks + block_size * 8 - 1) / (block_size * 8);

 // Inode table size (128 bytes per inode)
 uint32_t inodes_per_block = block_size / INODE_SIZE;
 uint32_t inode_table_blocks = (inode_count + inodes_per_block - 1) / inodes_per_block;

 // Layout
 uint32_t superblock_blk = 0;
 uint32_t ino_bitmap_blk = 1;
 uint32_t blk_bitmap_blk = ino_bitmap_blk + ino_bitmap_blocks;
 uint32_t inode_table_blk = blk_bitmap_blk + blk_bitmap_blocks;
 uint32_t first_data_blk = inode_table_blk + inode_table_blocks;

 printf("Creating filesystem with %u blocks of %u bytes...\n",
        total_blocks, block_size);
 printf("  Superblock at block %u\n", superblock_blk);
 printf("  Inode bitmap at block %u (%u blocks)\n", ino_bitmap_blk, ino_bitmap_blocks);
 printf("  Block bitmap at block %u (%u blocks)\n", blk_bitmap_blk, blk_bitmap_blocks);
 printf("  Inode table at blocks %u-%u (%u blocks, %u inodes)\n",
        inode_table_blk, inode_table_blk + inode_table_blocks - 1,
        inode_table_blocks, inode_count);
 printf("  First data block: %u\n", first_data_blk);
 printf("  Data blocks available: %u\n", total_blocks - first_data_blk);

 // ... continue with creation
}

Create and initialize disk image

 // Create file
 int fd = open(path, O_RDWR | O_CREAT | O_TRUNC, 0644);
 if (fd < 0) {
     perror("open");
     return 1;
 }

 // Set size (sparse file)
 if (ftruncate(fd, total_size) < 0) {
     perror("ftruncate");
     close(fd);
     return 1;
 }

 // Initialize superblock
 struct myfs_superblock sb = {0};
 sb.s_magic = MYFS_MAGIC;
 sb.s_version = MYFS_VERSION;
 sb.s_block_size = block_size;
 sb.s_blocks_count = total_blocks;
 sb.s_inodes_count = inode_count;
 sb.s_free_blocks_count = total_blocks - first_data_blk - 1;  // -1 for root dir
 sb.s_free_inodes_count = inode_count - 1;  // -1 for root inode
 sb.s_first_free_block = first_data_blk + 1;
 sb.s_first_free_inode = 2;
 sb.s_inode_bitmap_block = ino_bitmap_blk;
 sb.s_block_bitmap_block = blk_bitmap_blk;
 sb.s_inode_table_block = inode_table_blk;
 sb.s_first_data_block = first_data_blk;
 sb.s_inode_bitmap_blocks = ino_bitmap_blocks;
 sb.s_block_bitmap_blocks = blk_bitmap_blocks;
 sb.s_inode_table_blocks = inode_table_blocks;
 sb.s_create_time = time(NULL);
 sb.s_write_time = sb.s_create_time;
 strncpy(sb.s_label, label, sizeof(sb.s_label) - 1);
 uuid_generate(sb.s_uuid);  // Or use random bytes

 // Write superblock
 pwrite(fd, &sb, sizeof(sb), 0);

Initialize bitmaps

 // Allocate and initialize block bitmap
 size_t blk_bitmap_size = blk_bitmap_blocks * block_size;
 uint8_t *block_bitmap = calloc(1, blk_bitmap_size);

 // Mark metadata blocks as used (0 to first_data_blk-1)
 for (uint32_t i = 0; i < first_data_blk; i++) {
     BITMAP_SET(block_bitmap, i);
 }
 // Mark root directory data block as used
 BITMAP_SET(block_bitmap, first_data_blk);

 // Write block bitmap
 pwrite(fd, block_bitmap, blk_bitmap_size, blk_bitmap_blk * block_size);

 // Initialize inode bitmap
 size_t ino_bitmap_size = ino_bitmap_blocks * block_size;
 uint8_t *inode_bitmap = calloc(1, ino_bitmap_size);

 // Mark inode 0 as reserved, inode 1 as used (root)
 BITMAP_SET(inode_bitmap, 0);  // Reserved
 BITMAP_SET(inode_bitmap, 1);  // Root directory

 // Write inode bitmap
 pwrite(fd, inode_bitmap, ino_bitmap_size, ino_bitmap_blk * block_size);

Create root directory inode

 // Create root inode
 struct myfs_inode root_inode = {0};
 root_inode.i_mode = S_IFDIR | 0755;
 root_inode.i_uid = getuid();
 root_inode.i_gid = getgid();
 root_inode.i_links_count = 2;  // . and parent (which is itself for root)
 root_inode.i_size_lo = block_size;  // One block for directory entries
 root_inode.i_atime = root_inode.i_mtime = root_inode.i_ctime =
     root_inode.i_crtime = time(NULL);
 root_inode.i_blocks = block_size / 512;  // In 512-byte units
 root_inode.i_block[0] = first_data_blk;  // First direct block

 // Write root inode (inode 1, at index 0 in inode table)
 off_t root_inode_off = inode_table_blk * block_size;
 // Skip inode 0 (reserved)
 pwrite(fd, &root_inode, sizeof(root_inode), root_inode_off);

 // Create root directory entries (. and ..)
 uint8_t *dir_block = calloc(1, block_size);
 struct myfs_dirent *dot = (struct myfs_dirent *)dir_block;
 dot->d_ino = 1;  // Root is inode 1
 dot->d_rec_len = 12;  // Minimum size for "."
 dot->d_name_len = 1;
 dot->d_file_type = MYFS_FT_DIR;
 dot->d_name[0] = '.';

 struct myfs_dirent *dotdot = (struct myfs_dirent *)(dir_block + 12);
 dotdot->d_ino = 1;  // Parent of root is itself
 dotdot->d_rec_len = block_size - 12;  // Extends to end of block
 dotdot->d_name_len = 2;
 dotdot->d_file_type = MYFS_FT_DIR;
 dotdot->d_name[0] = '.';
 dotdot->d_name[1] = '.';

 // Write root directory data block
 pwrite(fd, dir_block, block_size, first_data_blk * block_size);

 // Cleanup
 free(block_bitmap);
 free(inode_bitmap);
 free(dir_block);
 close(fd);

 printf("Filesystem created successfully.\n");
 return 0;
}

Testing mkfs:

$ ./mkfs.myfs -s 10M test.img
$ hexdump -C test.img | head -20  # Check superblock magic
$ hexdump -C -s 4096 -n 64 test.img  # Check inode bitmap

Phase 2: Block I/O Layer (Days 4-6)

Goals:

Read/write blocks from disk image
Handle errors properly
Implement sync for durability

// Block I/O with error handling
int read_block(struct myfs_state *fs, uint32_t blk_num, void *buf) {
    if (blk_num >= fs->sb.s_blocks_count) {
        return -EINVAL;
    }

    off_t offset = (off_t)blk_num * fs->sb.s_block_size;
    ssize_t ret = pread(fs->disk_fd, buf, fs->sb.s_block_size, offset);

    if (ret < 0) {
        return -errno;
    }
    if (ret != fs->sb.s_block_size) {
        return -EIO;  // Short read
    }

    return 0;
}

int write_block(struct myfs_state *fs, uint32_t blk_num, const void *buf) {
    if (blk_num >= fs->sb.s_blocks_count) {
        return -EINVAL;
    }

    off_t offset = (off_t)blk_num * fs->sb.s_block_size;
    ssize_t ret = pwrite(fs->disk_fd, buf, fs->sb.s_block_size, offset);

    if (ret < 0) {
        return -errno;
    }
    if (ret != fs->sb.s_block_size) {
        return -EIO;  // Short write
    }

    return 0;
}

int zero_block(struct myfs_state *fs, uint32_t blk_num) {
    uint8_t zeros[fs->sb.s_block_size];
    memset(zeros, 0, sizeof(zeros));
    return write_block(fs, blk_num, zeros);
}

int sync_all(struct myfs_state *fs) {
    int ret = 0;

    pthread_mutex_lock(&fs->lock);

    // Write dirty bitmaps
    if (fs->ino_bm_dirty) {
        off_t offset = fs->sb.s_inode_bitmap_block * fs->sb.s_block_size;
        size_t size = fs->sb.s_inode_bitmap_blocks * fs->sb.s_block_size;
        if (pwrite(fs->disk_fd, fs->inode_bitmap, size, offset) != size) {
            ret = -EIO;
        }
        fs->ino_bm_dirty = 0;
    }

    if (fs->blk_bm_dirty) {
        off_t offset = fs->sb.s_block_bitmap_block * fs->sb.s_block_size;
        size_t size = fs->sb.s_block_bitmap_blocks * fs->sb.s_block_size;
        if (pwrite(fs->disk_fd, fs->block_bitmap, size, offset) != size) {
            ret = -EIO;
        }
        fs->blk_bm_dirty = 0;
    }

    // Write dirty superblock
    if (fs->sb_dirty) {
        fs->sb.s_write_time = time(NULL);
        if (pwrite(fs->disk_fd, &fs->sb, sizeof(fs->sb), 0) != sizeof(fs->sb)) {
            ret = -EIO;
        }
        fs->sb_dirty = 0;
    }

    // Sync to disk
    fsync(fs->disk_fd);

    pthread_mutex_unlock(&fs->lock);
    return ret;
}

Phase 3: Bitmap Management (Days 6-8)

Goals:

Load bitmaps into memory on mount
Implement alloc/free for blocks and inodes
Keep superblock free counts updated

int alloc_block(struct myfs_state *fs) {
    pthread_mutex_lock(&fs->lock);

    if (fs->sb.s_free_blocks_count == 0) {
        pthread_mutex_unlock(&fs->lock);
        return -ENOSPC;
    }

    // Start from hint
    int blk = bitmap_find_free_from(fs->block_bitmap,
                                     fs->sb.s_first_free_block,
                                     fs->sb.s_blocks_count);

    if (blk < 0 || blk < fs->sb.s_first_data_block) {
        pthread_mutex_unlock(&fs->lock);
        return -ENOSPC;
    }

    BITMAP_SET(fs->block_bitmap, blk);
    fs->sb.s_free_blocks_count--;
    fs->sb.s_first_free_block = blk + 1;
    fs->blk_bm_dirty = 1;
    fs->sb_dirty = 1;

    pthread_mutex_unlock(&fs->lock);
    return blk;
}

void free_block(struct myfs_state *fs, uint32_t blk) {
    if (blk < fs->sb.s_first_data_block || blk >= fs->sb.s_blocks_count) {
        return;  // Invalid block
    }

    pthread_mutex_lock(&fs->lock);

    if (BITMAP_GET(fs->block_bitmap, blk)) {
        BITMAP_CLR(fs->block_bitmap, blk);
        fs->sb.s_free_blocks_count++;

        // Update hint if this block is before current hint
        if (blk < fs->sb.s_first_free_block) {
            fs->sb.s_first_free_block = blk;
        }

        fs->blk_bm_dirty = 1;
        fs->sb_dirty = 1;
    }

    pthread_mutex_unlock(&fs->lock);
}

int alloc_inode(struct myfs_state *fs) {
    pthread_mutex_lock(&fs->lock);

    if (fs->sb.s_free_inodes_count == 0) {
        pthread_mutex_unlock(&fs->lock);
        return -ENOSPC;
    }

    // Start from hint (inodes start at 1)
    int ino = bitmap_find_free_from(fs->inode_bitmap,
                                     fs->sb.s_first_free_inode,
                                     fs->sb.s_inodes_count);

    if (ino < 1) {  // Inode 0 is reserved
        pthread_mutex_unlock(&fs->lock);
        return -ENOSPC;
    }

    BITMAP_SET(fs->inode_bitmap, ino);
    fs->sb.s_free_inodes_count--;
    fs->sb.s_first_free_inode = ino + 1;
    fs->ino_bm_dirty = 1;
    fs->sb_dirty = 1;

    pthread_mutex_unlock(&fs->lock);
    return ino;
}

void free_inode(struct myfs_state *fs, uint32_t ino) {
    if (ino < 1 || ino >= fs->sb.s_inodes_count) {
        return;
    }

    pthread_mutex_lock(&fs->lock);

    if (BITMAP_GET(fs->inode_bitmap, ino)) {
        BITMAP_CLR(fs->inode_bitmap, ino);
        fs->sb.s_free_inodes_count++;

        if (ino < fs->sb.s_first_free_inode) {
            fs->sb.s_first_free_inode = ino;
        }

        fs->ino_bm_dirty = 1;
        fs->sb_dirty = 1;
    }

    pthread_mutex_unlock(&fs->lock);
}

Phase 4: Inode Operations (Days 8-11)

Goals:

Read/write inodes from disk
Implement block mapping with indirection
Handle inode allocation for block pointers

int read_inode(struct myfs_state *fs, uint32_t ino, struct myfs_inode *inode) {
    if (ino < 1 || ino >= fs->sb.s_inodes_count) {
        return -EINVAL;
    }

    uint32_t inodes_per_block = fs->sb.s_block_size / INODE_SIZE;
    uint32_t block_idx = (ino - 1) / inodes_per_block;
    uint32_t inode_idx = (ino - 1) % inodes_per_block;

    uint8_t block[fs->sb.s_block_size];
    int ret = read_block(fs, fs->sb.s_inode_table_block + block_idx, block);
    if (ret < 0) return ret;

    memcpy(inode, block + inode_idx * INODE_SIZE, INODE_SIZE);
    return 0;
}

int write_inode(struct myfs_state *fs, uint32_t ino, struct myfs_inode *inode) {
    if (ino < 1 || ino >= fs->sb.s_inodes_count) {
        return -EINVAL;
    }

    uint32_t inodes_per_block = fs->sb.s_block_size / INODE_SIZE;
    uint32_t block_idx = (ino - 1) / inodes_per_block;
    uint32_t inode_idx = (ino - 1) % inodes_per_block;

    uint8_t block[fs->sb.s_block_size];
    int ret = read_block(fs, fs->sb.s_inode_table_block + block_idx, block);
    if (ret < 0) return ret;

    memcpy(block + inode_idx * INODE_SIZE, inode, INODE_SIZE);

    return write_block(fs, fs->sb.s_inode_table_block + block_idx, block);
}

// Set a block pointer, allocating indirect blocks as needed
int inode_set_block(struct myfs_state *fs, struct myfs_inode *inode,
                    uint32_t ino, uint32_t logical_blk, uint32_t phys_blk) {

    uint32_t ptrs_per_block = fs->sb.s_block_size / sizeof(uint32_t);

    // Direct blocks
    if (logical_blk < DIRECT_BLOCKS) {
        inode->i_block[logical_blk] = phys_blk;
        return write_inode(fs, ino, inode);
    }
    logical_blk -= DIRECT_BLOCKS;

    // Single indirect
    if (logical_blk < ptrs_per_block) {
        // Allocate indirect block if needed
        if (inode->i_block[12] == 0) {
            int ind_blk = alloc_block(fs);
            if (ind_blk < 0) return ind_blk;

            zero_block(fs, ind_blk);
            inode->i_block[12] = ind_blk;
            write_inode(fs, ino, inode);
        }

        uint32_t indirect[ptrs_per_block];
        read_block(fs, inode->i_block[12], indirect);
        indirect[logical_blk] = phys_blk;
        return write_block(fs, inode->i_block[12], indirect);
    }
    logical_blk -= ptrs_per_block;

    // Double indirect
    if (logical_blk < ptrs_per_block * ptrs_per_block) {
        // Allocate double indirect block if needed
        if (inode->i_block[13] == 0) {
            int dbl_blk = alloc_block(fs);
            if (dbl_blk < 0) return dbl_blk;

            zero_block(fs, dbl_blk);
            inode->i_block[13] = dbl_blk;
            write_inode(fs, ino, inode);
        }

        uint32_t dbl_indirect[ptrs_per_block];
        read_block(fs, inode->i_block[13], dbl_indirect);

        uint32_t idx1 = logical_blk / ptrs_per_block;
        uint32_t idx2 = logical_blk % ptrs_per_block;

        // Allocate indirect block if needed
        if (dbl_indirect[idx1] == 0) {
            int ind_blk = alloc_block(fs);
            if (ind_blk < 0) return ind_blk;

            zero_block(fs, ind_blk);
            dbl_indirect[idx1] = ind_blk;
            write_block(fs, inode->i_block[13], dbl_indirect);
        }

        uint32_t indirect[ptrs_per_block];
        read_block(fs, dbl_indirect[idx1], indirect);
        indirect[idx2] = phys_blk;
        return write_block(fs, dbl_indirect[idx1], indirect);
    }

    // Triple indirect would go here (similar pattern)

    return -EFBIG;  // File too large
}

Phase 5: Directory Operations (Days 11-14)

Goals:

Parse directory entries
Add/remove entries
Handle variable-length records

int dir_lookup(struct myfs_state *fs, struct myfs_inode *dir,
               const char *name, uint32_t *ino_out) {

    if (!S_ISDIR(dir->i_mode)) {
        return -ENOTDIR;
    }

    size_t name_len = strlen(name);
    uint64_t size = ((uint64_t)dir->i_size_hi << 32) | dir->i_size_lo;
    uint32_t num_blocks = (size + fs->sb.s_block_size - 1) / fs->sb.s_block_size;

    uint8_t block[fs->sb.s_block_size];

    for (uint32_t blk_idx = 0; blk_idx < num_blocks; blk_idx++) {
        uint32_t phys_blk = inode_get_block(fs, dir, blk_idx);
        if (phys_blk == 0) continue;  // Sparse

        read_block(fs, phys_blk, block);

        uint32_t offset = 0;
        while (offset < fs->sb.s_block_size) {
            struct myfs_dirent *de = (struct myfs_dirent *)(block + offset);

            if (de->d_rec_len == 0) break;  // Invalid entry

            if (de->d_ino != 0 &&
                de->d_name_len == name_len &&
                memcmp(de->d_name, name, name_len) == 0) {
                *ino_out = de->d_ino;
                return 0;
            }

            offset += de->d_rec_len;
        }
    }

    return -ENOENT;
}

int dir_add_entry(struct myfs_state *fs, struct myfs_inode *dir,
                  uint32_t dir_ino, const char *name, uint32_t ino, uint8_t type) {

    size_t name_len = strlen(name);
    if (name_len > MAX_FILENAME_LEN) {
        return -ENAMETOOLONG;
    }

    // Size needed for new entry (aligned to 4 bytes)
    uint16_t needed = (8 + name_len + 3) & ~3;

    uint64_t size = ((uint64_t)dir->i_size_hi << 32) | dir->i_size_lo;
    uint32_t num_blocks = (size + fs->sb.s_block_size - 1) / fs->sb.s_block_size;

    uint8_t block[fs->sb.s_block_size];

    // Search existing blocks for space
    for (uint32_t blk_idx = 0; blk_idx < num_blocks; blk_idx++) {
        uint32_t phys_blk = inode_get_block(fs, dir, blk_idx);
        if (phys_blk == 0) continue;

        read_block(fs, phys_blk, block);

        uint32_t offset = 0;
        while (offset < fs->sb.s_block_size) {
            struct myfs_dirent *de = (struct myfs_dirent *)(block + offset);

            if (de->d_rec_len == 0) break;

            // Calculate actual size of this entry
            uint16_t actual = (8 + de->d_name_len + 3) & ~3;

            // Check if there's room after this entry
            if (de->d_rec_len - actual >= needed) {
                // Split this entry
                uint16_t old_rec_len = de->d_rec_len;
                de->d_rec_len = actual;

                // Add new entry
                struct myfs_dirent *new_de =
                    (struct myfs_dirent *)(block + offset + actual);
                new_de->d_ino = ino;
                new_de->d_rec_len = old_rec_len - actual;
                new_de->d_name_len = name_len;
                new_de->d_file_type = type;
                memcpy(new_de->d_name, name, name_len);

                write_block(fs, phys_blk, block);
                return 0;
            }

            offset += de->d_rec_len;
        }
    }

    // No space in existing blocks, allocate new block
    int new_blk = alloc_block(fs);
    if (new_blk < 0) return new_blk;

    zero_block(fs, new_blk);

    // Set block pointer
    int ret = inode_set_block(fs, dir, dir_ino, num_blocks, new_blk);
    if (ret < 0) {
        free_block(fs, new_blk);
        return ret;
    }

    // Create entry in new block
    memset(block, 0, fs->sb.s_block_size);
    struct myfs_dirent *de = (struct myfs_dirent *)block;
    de->d_ino = ino;
    de->d_rec_len = fs->sb.s_block_size;  // Extends to end
    de->d_name_len = name_len;
    de->d_file_type = type;
    memcpy(de->d_name, name, name_len);

    write_block(fs, new_blk, block);

    // Update directory size
    uint64_t new_size = (num_blocks + 1) * fs->sb.s_block_size;
    dir->i_size_lo = new_size & 0xFFFFFFFF;
    dir->i_size_hi = new_size >> 32;
    dir->i_mtime = dir->i_ctime = time(NULL);
    write_inode(fs, dir_ino, dir);

    return 0;
}

Phase 6: File Read/Write (Days 14-18)

Goals:

Read data from files
Write data, allocating blocks as needed
Handle sparse files and size updates

ssize_t file_read(struct myfs_state *fs, struct myfs_inode *inode,
                  char *buf, size_t size, off_t offset) {

    uint64_t file_size = ((uint64_t)inode->i_size_hi << 32) | inode->i_size_lo;

    // Check bounds
    if (offset >= file_size) {
        return 0;  // EOF
    }
    if (offset + size > file_size) {
        size = file_size - offset;
    }

    size_t bytes_read = 0;
    uint8_t block[fs->sb.s_block_size];

    while (bytes_read < size) {
        uint32_t logical_blk = (offset + bytes_read) / fs->sb.s_block_size;
        uint32_t blk_offset = (offset + bytes_read) % fs->sb.s_block_size;
        size_t to_read = fs->sb.s_block_size - blk_offset;

        if (to_read > size - bytes_read) {
            to_read = size - bytes_read;
        }

        uint32_t phys_blk = inode_get_block(fs, inode, logical_blk);

        if (phys_blk == 0) {
            // Sparse hole - return zeros
            memset(buf + bytes_read, 0, to_read);
        } else {
            read_block(fs, phys_blk, block);
            memcpy(buf + bytes_read, block + blk_offset, to_read);
        }

        bytes_read += to_read;
    }

    return bytes_read;
}

ssize_t file_write(struct myfs_state *fs, struct myfs_inode *inode, uint32_t ino,
                   const char *buf, size_t size, off_t offset) {

    size_t bytes_written = 0;
    uint8_t block[fs->sb.s_block_size];

    while (bytes_written < size) {
        uint32_t logical_blk = (offset + bytes_written) / fs->sb.s_block_size;
        uint32_t blk_offset = (offset + bytes_written) % fs->sb.s_block_size;
        size_t to_write = fs->sb.s_block_size - blk_offset;

        if (to_write > size - bytes_written) {
            to_write = size - bytes_written;
        }

        uint32_t phys_blk = inode_get_block(fs, inode, logical_blk);

        if (phys_blk == 0) {
            // Need to allocate new block
            int new_blk = alloc_block(fs);
            if (new_blk < 0) {
                if (bytes_written > 0) break;  // Return partial write
                return new_blk;
            }

            // If partial block write, zero the new block first
            if (blk_offset > 0 || to_write < fs->sb.s_block_size) {
                zero_block(fs, new_blk);
            }

            int ret = inode_set_block(fs, inode, ino, logical_blk, new_blk);
            if (ret < 0) {
                free_block(fs, new_blk);
                if (bytes_written > 0) break;
                return ret;
            }

            phys_blk = new_blk;
            inode->i_blocks += fs->sb.s_block_size / 512;
        }

        // Read-modify-write for partial blocks
        if (blk_offset > 0 || to_write < fs->sb.s_block_size) {
            read_block(fs, phys_blk, block);
        }

        memcpy(block + blk_offset, buf + bytes_written, to_write);
        write_block(fs, phys_blk, block);

        bytes_written += to_write;
    }

    // Update inode size if file grew
    uint64_t new_end = offset + bytes_written;
    uint64_t old_size = ((uint64_t)inode->i_size_hi << 32) | inode->i_size_lo;

    if (new_end > old_size) {
        inode->i_size_lo = new_end & 0xFFFFFFFF;
        inode->i_size_hi = new_end >> 32;
    }

    inode->i_mtime = inode->i_ctime = time(NULL);
    write_inode(fs, ino, inode);

    return bytes_written;
}

Phase 7: FUSE Integration (Days 18-22)

Goals:

Connect all components to FUSE callbacks
Handle path resolution
Implement all required operations

#define FUSE_USE_VERSION 31
#include <fuse.h>

static struct myfs_state *get_state() {
    return (struct myfs_state *)fuse_get_context()->private_data;
}

static int myfs_getattr(const char *path, struct stat *stbuf,
                        struct fuse_file_info *fi) {
    struct myfs_state *fs = get_state();
    memset(stbuf, 0, sizeof(struct stat));

    uint32_t ino;
    int ret = resolve_path(fs, path, &ino);
    if (ret < 0) return ret;

    struct myfs_inode inode;
    ret = read_inode(fs, ino, &inode);
    if (ret < 0) return ret;

    stbuf->st_ino = ino;
    stbuf->st_mode = inode.i_mode;
    stbuf->st_nlink = inode.i_links_count;
    stbuf->st_uid = inode.i_uid;
    stbuf->st_gid = inode.i_gid;
    stbuf->st_size = ((uint64_t)inode.i_size_hi << 32) | inode.i_size_lo;
    stbuf->st_blocks = inode.i_blocks;
    stbuf->st_blksize = fs->sb.s_block_size;
    stbuf->st_atime = inode.i_atime;
    stbuf->st_mtime = inode.i_mtime;
    stbuf->st_ctime = inode.i_ctime;

    return 0;
}

static int myfs_readdir(const char *path, void *buf, fuse_fill_dir_t filler,
                        off_t offset, struct fuse_file_info *fi,
                        enum fuse_readdir_flags flags) {
    struct myfs_state *fs = get_state();

    uint32_t ino;
    int ret = resolve_path(fs, path, &ino);
    if (ret < 0) return ret;

    struct myfs_inode inode;
    ret = read_inode(fs, ino, &inode);
    if (ret < 0) return ret;

    if (!S_ISDIR(inode.i_mode)) {
        return -ENOTDIR;
    }

    // Callback for dir_iterate
    struct fill_ctx {
        void *buf;
        fuse_fill_dir_t filler;
    } ctx = {buf, filler};

    int fill_callback(const char *name, uint32_t ino, uint8_t type, void *c) {
        struct fill_ctx *ctx = c;
        ctx->filler(ctx->buf, name, NULL, 0, 0);
        return 0;
    }

    return dir_iterate(fs, &inode, fill_callback, &ctx);
}

static int myfs_create(const char *path, mode_t mode,
                       struct fuse_file_info *fi) {
    struct myfs_state *fs = get_state();

    // Get parent directory
    uint32_t parent_ino;
    char name[256];
    int ret = resolve_parent(fs, path, &parent_ino, name);
    if (ret < 0) return ret;

    struct myfs_inode parent;
    ret = read_inode(fs, parent_ino, &parent);
    if (ret < 0) return ret;

    // Check if file already exists
    uint32_t existing;
    if (dir_lookup(fs, &parent, name, &existing) == 0) {
        return -EEXIST;
    }

    // Allocate new inode
    int new_ino = alloc_inode(fs);
    if (new_ino < 0) return new_ino;

    // Initialize inode
    struct myfs_inode new_inode = {0};
    new_inode.i_mode = S_IFREG | (mode & 0777);
    new_inode.i_uid = fuse_get_context()->uid;
    new_inode.i_gid = fuse_get_context()->gid;
    new_inode.i_links_count = 1;
    new_inode.i_atime = new_inode.i_mtime = new_inode.i_ctime =
        new_inode.i_crtime = time(NULL);

    ret = write_inode(fs, new_ino, &new_inode);
    if (ret < 0) {
        free_inode(fs, new_ino);
        return ret;
    }

    // Add directory entry
    ret = dir_add_entry(fs, &parent, parent_ino, name, new_ino, MYFS_FT_REG_FILE);
    if (ret < 0) {
        free_inode(fs, new_ino);
        return ret;
    }

    return 0;
}

static int myfs_read(const char *path, char *buf, size_t size,
                     off_t offset, struct fuse_file_info *fi) {
    struct myfs_state *fs = get_state();

    uint32_t ino;
    int ret = resolve_path(fs, path, &ino);
    if (ret < 0) return ret;

    struct myfs_inode inode;
    ret = read_inode(fs, ino, &inode);
    if (ret < 0) return ret;

    return file_read(fs, &inode, buf, size, offset);
}

static int myfs_write(const char *path, const char *buf, size_t size,
                      off_t offset, struct fuse_file_info *fi) {
    struct myfs_state *fs = get_state();

    uint32_t ino;
    int ret = resolve_path(fs, path, &ino);
    if (ret < 0) return ret;

    struct myfs_inode inode;
    ret = read_inode(fs, ino, &inode);
    if (ret < 0) return ret;

    return file_write(fs, &inode, ino, buf, size, offset);
}

static void myfs_destroy(void *private_data) {
    struct myfs_state *fs = private_data;
    sync_all(fs);
    close(fs->disk_fd);
    free(fs->inode_bitmap);
    free(fs->block_bitmap);
    free(fs->disk_path);
}

static struct fuse_operations myfs_oper = {
    .getattr    = myfs_getattr,
    .readdir    = myfs_readdir,
    .open       = myfs_open,
    .read       = myfs_read,
    .write      = myfs_write,
    .create     = myfs_create,
    .unlink     = myfs_unlink,
    .mkdir      = myfs_mkdir,
    .rmdir      = myfs_rmdir,
    .rename     = myfs_rename,
    .truncate   = myfs_truncate,
    .utimens    = myfs_utimens,
    .chmod      = myfs_chmod,
    .chown      = myfs_chown,
    .statfs     = myfs_statfs,
    .fsync      = myfs_fsync,
    .destroy    = myfs_destroy,
};

Phase 8: fsck Utility (Days 22-25)

Goals:

Verify filesystem consistency
Detect and report errors
(Optional) Repair simple issues

int fsck_main(const char *image_path) {
    printf("=== MYFS Filesystem Check ===\n\n");

    // Open image
    int fd = open(image_path, O_RDONLY);
    if (fd < 0) {
        perror("open");
        return 1;
    }

    // Read and verify superblock
    printf("Phase 1: Checking superblock...\n");
    struct myfs_superblock sb;
    pread(fd, &sb, sizeof(sb), 0);

    if (sb.s_magic != MYFS_MAGIC) {
        printf("  ERROR: Invalid magic number (expected 0x%X, got 0x%X)\n",
               MYFS_MAGIC, sb.s_magic);
        close(fd);
        return 1;
    }
    printf("  Magic: 0x%X OK\n", sb.s_magic);
    printf("  Version: %u OK\n", sb.s_version);
    printf("  Block size: %u OK\n", sb.s_block_size);
    printf("  Blocks: %u OK\n", sb.s_blocks_count);
    printf("  Inodes: %u OK\n", sb.s_inodes_count);

    // Load bitmaps
    size_t ino_bm_size = sb.s_inode_bitmap_blocks * sb.s_block_size;
    size_t blk_bm_size = sb.s_block_bitmap_blocks * sb.s_block_size;

    uint8_t *inode_bitmap = malloc(ino_bm_size);
    uint8_t *block_bitmap = malloc(blk_bm_size);

    pread(fd, inode_bitmap, ino_bm_size, sb.s_inode_bitmap_block * sb.s_block_size);
    pread(fd, block_bitmap, blk_bm_size, sb.s_block_bitmap_block * sb.s_block_size);

    // Count used inodes from bitmap
    printf("\nPhase 2: Checking inode bitmap...\n");
    uint32_t used_inodes = 0;
    for (uint32_t i = 0; i < sb.s_inodes_count; i++) {
        if (BITMAP_GET(inode_bitmap, i)) {
            used_inodes++;
        }
    }
    printf("  Used inodes: %u\n", used_inodes);
    printf("  Free inodes: %u\n", sb.s_inodes_count - used_inodes);

    if (sb.s_free_inodes_count != sb.s_inodes_count - used_inodes) {
        printf("  WARNING: Superblock free count mismatch (%u vs %u)\n",
               sb.s_free_inodes_count, sb.s_inodes_count - used_inodes);
    } else {
        printf("  Bitmap consistent: OK\n");
    }

    // Count used blocks from bitmap
    printf("\nPhase 3: Checking block bitmap...\n");
    uint32_t used_blocks = 0;
    for (uint32_t i = 0; i < sb.s_blocks_count; i++) {
        if (BITMAP_GET(block_bitmap, i)) {
            used_blocks++;
        }
    }
    printf("  Used blocks: %u\n", used_blocks);
    printf("  Free blocks: %u\n", sb.s_blocks_count - used_blocks);

    if (sb.s_free_blocks_count != sb.s_blocks_count - used_blocks) {
        printf("  WARNING: Superblock free count mismatch (%u vs %u)\n",
               sb.s_free_blocks_count, sb.s_blocks_count - used_blocks);
    } else {
        printf("  Bitmap consistent: OK\n");
    }

    // Verify directory structure (simplified)
    printf("\nPhase 4: Verifying directory structure...\n");
    // Check that root inode exists and is a directory
    struct myfs_inode root_inode;
    off_t root_off = sb.s_inode_table_block * sb.s_block_size;
    pread(fd, &root_inode, sizeof(root_inode), root_off);

    if (!S_ISDIR(root_inode.i_mode)) {
        printf("  ERROR: Root inode is not a directory\n");
    } else {
        printf("  Root inode (1): OK\n");
    }

    // TODO: Recursively check all directories, count files, verify link counts

    printf("\nPhase 5: Checking reference counts...\n");
    // TODO: Build reference count map, compare with i_links_count
    printf("  (Detailed check not implemented)\n");

    printf("\nSummary:\n");
    printf("  Free inodes: %u/%u\n", sb.s_free_inodes_count, sb.s_inodes_count);
    printf("  Free blocks: %u/%u\n", sb.s_free_blocks_count, sb.s_blocks_count);
    printf("  Filesystem is CONSISTENT\n");

    free(inode_bitmap);
    free(block_bitmap);
    close(fd);
    return 0;
}

Phase 9: Testing and Debugging (Days 25-28)

See Testing Strategy section below.

Testing Strategy

Unit Tests

// test_bitmap.c
void test_bitmap_operations() {
    uint8_t bitmap[16] = {0};

    // Test SET/GET
    assert(BITMAP_GET(bitmap, 0) == 0);
    BITMAP_SET(bitmap, 0);
    assert(BITMAP_GET(bitmap, 0) == 1);

    // Test across byte boundary
    BITMAP_SET(bitmap, 7);
    BITMAP_SET(bitmap, 8);
    assert(BITMAP_GET(bitmap, 7) == 1);
    assert(BITMAP_GET(bitmap, 8) == 1);
    assert(bitmap[0] == 0x81);  // bits 0 and 7
    assert(bitmap[1] == 0x01);  // bit 8

    // Test CLR
    BITMAP_CLR(bitmap, 0);
    assert(BITMAP_GET(bitmap, 0) == 0);

    // Test find_free
    int free_bit = bitmap_find_free(bitmap, 128);
    assert(free_bit == 0);  // bit 0 was cleared

    BITMAP_SET(bitmap, 0);
    free_bit = bitmap_find_free(bitmap, 128);
    assert(free_bit == 1);  // first truly free bit

    printf("Bitmap tests passed\n");
}

// test_inode_addressing.c
void test_inode_block_mapping() {
    // Test with 4KB blocks
    // Direct: 0-11, Single indirect: 12-1035, Double indirect: 1036+

    assert(block_level(0) == DIRECT);
    assert(block_level(11) == DIRECT);
    assert(block_level(12) == SINGLE_INDIRECT);
    assert(block_level(1035) == SINGLE_INDIRECT);
    assert(block_level(1036) == DOUBLE_INDIRECT);

    printf("Inode addressing tests passed\n");
}

Integration Tests

#!/bin/bash
# test_persistence.sh

set -e

DISK=/tmp/test_disk.img
MNT=/tmp/test_mnt
TESTFILE="test_data.txt"

cleanup() {
    fusermount -u $MNT 2>/dev/null || true
    rm -f $DISK
    rmdir $MNT 2>/dev/null || true
}
trap cleanup EXIT

# Create filesystem
./mkfs.myfs -s 10M $DISK

# Mount
mkdir -p $MNT
./myfs $DISK $MNT

# Write test data
echo "Persistent test data: $(date)" > $MNT/$TESTFILE
CHECKSUM1=$(md5sum $MNT/$TESTFILE | awk '{print $1}')

# Create nested directories
mkdir -p $MNT/a/b/c/d
echo "Nested file" > $MNT/a/b/c/d/nested.txt

# Unmount
fusermount -u $MNT

echo "Remounting filesystem..."

# Remount
./myfs $DISK $MNT

# Verify persistence
if [ -f $MNT/$TESTFILE ]; then
    CHECKSUM2=$(md5sum $MNT/$TESTFILE | awk '{print $1}')
    if [ "$CHECKSUM1" = "$CHECKSUM2" ]; then
        echo "PASS: File content persisted correctly"
    else
        echo "FAIL: File content corrupted"
        exit 1
    fi
else
    echo "FAIL: File not found after remount"
    exit 1
fi

# Verify nested structure
if [ -f $MNT/a/b/c/d/nested.txt ]; then
    echo "PASS: Nested directories persisted"
else
    echo "FAIL: Nested directories not found"
    exit 1
fi

# Run fsck
./fsck.myfs $DISK
echo "PASS: fsck reports consistent filesystem"

# Large file test
dd if=/dev/urandom of=$MNT/large.bin bs=1M count=5 2>/dev/null
LARGE_SUM=$(md5sum $MNT/large.bin | awk '{print $1}')

fusermount -u $MNT
./myfs $DISK $MNT

LARGE_SUM2=$(md5sum $MNT/large.bin | awk '{print $1}')
if [ "$LARGE_SUM" = "$LARGE_SUM2" ]; then
    echo "PASS: Large file (5MB) persisted correctly"
else
    echo "FAIL: Large file corrupted"
    exit 1
fi

echo "All persistence tests passed!"

Stress Tests

#!/bin/bash
# stress_test.sh

DISK=/tmp/stress_disk.img
MNT=/tmp/stress_mnt

./mkfs.myfs -s 100M $DISK
mkdir -p $MNT
./myfs $DISK $MNT

# Create many files
echo "Creating 1000 files..."
for i in $(seq 1 1000); do
    echo "file $i content" > $MNT/file_$i.txt
done

# Verify count
COUNT=$(ls $MNT | wc -l)
if [ "$COUNT" -eq "1000" ]; then
    echo "PASS: Created 1000 files"
else
    echo "FAIL: Only found $COUNT files"
fi

# Create large file approaching double indirect
echo "Creating 50MB file..."
dd if=/dev/urandom of=$MNT/huge.bin bs=1M count=50 2>/dev/null

# Verify with fsck
./fsck.myfs $DISK

# Fill filesystem
echo "Filling filesystem..."
dd if=/dev/zero of=$MNT/fill.bin bs=1M count=1000 2>/dev/null || true
# Should eventually fail with ENOSPC

fusermount -u $MNT

Common Pitfalls and Debugging

Pitfall 1: Off-by-One in Inode Numbers

Problem: Inodes are numbered from 1, but arrays are indexed from 0.

// WRONG
offset = ino * INODE_SIZE;

// CORRECT
offset = (ino - 1) * INODE_SIZE;

Pitfall 2: Not Zeroing New Indirect Blocks

Problem: Garbage data in newly allocated indirect blocks causes random block pointers.

// WRONG
int ind_blk = alloc_block(fs);
inode->i_block[12] = ind_blk;

// CORRECT
int ind_blk = alloc_block(fs);
zero_block(fs, ind_blk);  // Zero before use!
inode->i_block[12] = ind_blk;

Pitfall 3: Not Syncing on Unmount

Problem: Data written to cache but lost on unmount.

static void myfs_destroy(void *private_data) {
    struct myfs_state *fs = private_data;
    sync_all(fs);  // CRITICAL - flush all dirty data
    close(fs->disk_fd);
}

Pitfall 4: Directory Entry rec_len Corruption

Problem: Last entry’s rec_len must extend to block end.

// When adding to directory, the last entry gets remaining space
new_entry->d_rec_len = block_size - current_offset;

Pitfall 5: Block vs Byte Offsets

Problem: Mixing block numbers and byte offsets.

// WRONG
pread(fd, buf, BLOCK_SIZE, block_num);

// CORRECT
pread(fd, buf, BLOCK_SIZE, (off_t)block_num * BLOCK_SIZE);

Debugging Techniques

1. Hex dump verification:

# Check superblock
hexdump -C disk.img | head -10

# Check specific block (e.g., block 5)
hexdump -C -s $((5 * 4096)) -n 256 disk.img

2. Custom dump tool:

// myfs-dump.c
int main(int argc, char *argv[]) {
    if (argc < 3) {
        printf("Usage: myfs-dump disk.img [superblock|inode N|block N]\n");
        return 1;
    }

    // Implement dump commands
}

3. FUSE debug mode:

./myfs -f -d disk.img /mnt/myfs
# Shows every operation in real-time

4. Add extensive logging:

#define DEBUG 1

#if DEBUG
#define LOG(fmt, ...) fprintf(stderr, "[myfs:%s:%d] " fmt "\n", \
                              __func__, __LINE__, ##__VA_ARGS__)
#else
#define LOG(fmt, ...)
#endif

int alloc_block(struct myfs_state *fs) {
    LOG("Allocating block, %u free", fs->sb.s_free_blocks_count);
    // ...
    LOG("Allocated block %u", blk);
    return blk;
}

Extensions and Challenges

Extension 1: fsck Repair Mode

Add --fix flag to repair common issues:

Orphaned blocks (allocated but unreferenced)
Wrong free counts in superblock
Directory entries pointing to unallocated inodes
Missing . and .. entries

Extension 2: Sparse File Support

Properly handle files with holes:

Don’t allocate blocks for write-seeking past EOF
Return zeros for reads from unallocated regions
Use fallocate() to pre-allocate sparse files

Extension 3: Block Group Locality

Like ext2, divide filesystem into block groups:

Keep file data near its inode
Reduce fragmentation
Enable per-group bitmaps

Extension 4: File Extent Support

Instead of indirect blocks, use extents:

Extent = (start_block, length)
More efficient for contiguous files
Similar to ext4 extents

Extension 5: Quotas

Track per-user resource usage:

Block count per user
Inode count per user
Enforce soft and hard limits

Real-World Connections

How Production Filesystems Differ

Feature	Your MYFS	ext4	XFS	Btrfs
Block allocation	Bitmap	Bitmap + Extents	B-tree	CoW B-tree
Max file size	4TB	16TB	8EB	16EB
Journaling	None	Metadata	Metadata	CoW
Snapshots	None	None	None	Native
Checksums	None	Metadata	None	All data
Defrag	None	Online	Online	Online

Where This Knowledge Applies

Database storage engines - Same block management concepts
Object storage - Similar metadata tracking
Virtual disk images - QCOW2, VMDK use similar structures
Container layer filesystems - OverlayFS, AUFS
Network filesystems - NFS, CIFS use local FS concepts

Interview Questions

Conceptual

“Why do filesystems use bitmaps for free space tracking?”
- Expected: O(1) lookup, compact representation, simple implementation
- Follow-up: What are alternatives? (Free lists, B-trees for extents)
“Explain how indirect block pointers work.”
- Expected: Direct (12), single indirect (1 level), double (2 levels), triple (3 levels)
- Show calculation for max file size
“What happens when you delete a file?”
- Expected: Remove directory entry, decrement link count, if links=0: free inode and all data blocks, update bitmaps
“Why is inode 0 reserved?”
- Expected: Used as NULL/invalid marker in directory entries and block pointers

Implementation

“How do you calculate an inode’s disk location?”
- Expected: inode_table_start + (ino - 1) * inode_size
“What’s the difference between internal and external fragmentation?”
- Expected: Internal = wasted space within allocated block; External = wasted space between allocations
“Why might a filesystem show ‘no space left’ when there’s free space?”
- Expected: Out of inodes (common with many small files)
“How would you implement hard links?”
- Expected: Multiple directory entries pointing to same inode, increment link count

Self-Assessment Checklist

Before considering this project complete, verify:

Resources

Primary References

Topic	Resource
Filesystem implementation	“Operating Systems: Three Easy Pieces” Ch. 39-41
ext2/ext3 design	“Understanding the Linux Kernel” Ch. 12, 18
File I/O syscalls	“The Linux Programming Interface” Ch. 4-5, 14
ext2 specification	nongnu.org ext2 docs
FUSE tutorial	NMSU FUSE Tutorial
ext2 implementation guide	OSDev Wiki - Ext2

Tools

hexdump / xxd - Binary inspection
dumpe2fs - ext2/3/4 superblock dump
debugfs - Interactive ext2 explorer
e2fsck - ext2/3/4 filesystem checker

Code References

What’s Next

After completing this project, you’ve built a real persistent filesystem. But it has a fatal flaw: crashes can corrupt it. If power fails between updating the bitmap and the directory entry, you’ll have orphaned blocks or dangling references.

Project 4: Journaling Layer solves this by implementing write-ahead logging. You’ll record operations to a journal before applying them, enabling crash recovery. This is how ext3/ext4 can mount instantly after power failures without running fsck.

The progression:

P02: In-memory (fast, volatile)
P03: Persistent (durable, corruptible)
P04: Journaled (durable, crash-consistent)
P06: Copy-on-Write (durable, crash-consistent, snapshotable)

Each project adds a new layer of sophistication matching real filesystem evolution.