Project 3: Persistent Block-Based Filesystem
Project 3: Persistent Block-Based Filesystem
Project Overview
| Attribute | Details |
|---|---|
| Difficulty | Expert |
| Time Estimate | 3-4 weeks |
| Language | C |
| Knowledge Area | Filesystems / Storage |
| Main Book | “Operating Systems: Three Easy Pieces” by Arpaci-Dusseau |
| Prerequisites | Project 2 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.
Real World Output:
$ ./mkfs.myfs -s 100M disk.img # Create 100MB filesystem
$ ./myfs disk.img /mnt/myfs # Mount it
$ cp -r ~/Documents/* /mnt/myfs/ # Copy real files
$ umount /mnt/myfs # Unmount
$ ./myfs disk.img /mnt/myfs # Remount - files persist!
$ ls /mnt/myfs
Documents report.pdf photos/
$ ./fsck.myfs disk.img # Your own filesystem checker
Checking superblock... OK
Checking inode bitmap... OK
Checking block bitmap... OK
Free blocks: 24531/25600
Learning Objectives
By completing this project, you will:
- Design on-disk data structures that survive restarts
- Implement block allocation using bitmaps
- Manage indirect block pointers for large file support
- Handle the persistence challenge: writing structured data to disk
- Build filesystem utilities (mkfs, fsck)
- Understand crash consistency issues (preparation for Project 4)
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. In-memory filesystems are elegant, but the moment you need persistence, you enter a world of complexity: block allocation, fragmentation, indirect pointers, and the eternal “what if the power fails during a write?” problem.
Every file you’ve ever saved went through this exact process. You’re about to build that magic yourself.
Deep Theoretical Foundation
1. Why Block-Based Storage?
Disks (HDDs and SSDs) operate on fixed-size units:
- Sectors: Hardware unit (512 bytes or 4096 bytes)
- Blocks: Filesystem unit (typically 1KB, 2KB, or 4KB)
Why not byte-addressable storage?
- Disk controllers are optimized for block transfers
- Metadata overhead would be enormous for byte tracking
- Caching works better with fixed-size units
Block size tradeoffs:
| Block Size | Pros | Cons |
|---|---|---|
| 1KB | Less wasted space for small files | More blocks to track, slower for large files |
| 4KB | Matches page size, faster I/O | ~2KB average waste per small file |
| 64KB | Excellent sequential performance | Huge waste for small files |
2. On-Disk Layout Design
A typical Unix filesystem organizes disk space like this:
┌──────────────────────────────────────────────────────────────┐
│ Block 0 │ Superblock │
│ │ - Magic number, version │
│ │ - Total blocks, free blocks │
│ │ - Inode count, block size │
├─────────────┼────────────────────────────────────────────────┤
│ Block 1-2 │ Inode Bitmap │
│ │ - 1 bit per inode (used/free) │
├─────────────┼────────────────────────────────────────────────┤
│ Block 3-4 │ Block Bitmap │
│ │ - 1 bit per data block (used/free) │
├─────────────┼────────────────────────────────────────────────┤
│ Block 5-N │ Inode Table │
│ │ - Fixed-size inode structures │
├─────────────┼────────────────────────────────────────────────┤
│ Block N+1 │ Data Blocks │
│ to End │ - File and directory contents │
└─────────────┴────────────────────────────────────────────────┘
3. Superblock Design
The superblock is the filesystem’s master record:
struct myfs_superblock {
uint32_t s_magic; // Magic number (e.g., 0xDEADBEEF)
uint32_t s_version; // Filesystem version
uint32_t s_block_size; // Block size in bytes
uint32_t s_blocks_count; // Total blocks in filesystem
uint32_t s_free_blocks; // Free block count
uint32_t s_inodes_count; // Total inodes
uint32_t s_free_inodes; // Free inode count
uint32_t s_inode_bitmap; // Block number of inode bitmap
uint32_t s_block_bitmap; // Block number of block bitmap
uint32_t s_inode_table; // First block of inode table
uint32_t s_first_data; // First data block
uint32_t s_root_inode; // Inode number of root directory
uint64_t s_mount_time; // Last mount timestamp
uint64_t s_write_time; // Last write timestamp
uint8_t s_uuid[16]; // Filesystem UUID
char s_label[64]; // Volume label
} __attribute__((packed));
Why these fields?
s_magic: Verify this is your filesystem types_free_*: Avoid scanning bitmaps for every allocations_first_data: Know where file data startss_uuid: Identify filesystem across mounts
4. Bitmap-Based Allocation
Bitmaps provide O(1) check for individual blocks and O(n) search for free blocks:
// Block bitmap operations
#define BITMAP_GET(bitmap, n) ((bitmap[(n)/8] >> ((n)%8)) & 1)
#define BITMAP_SET(bitmap, n) (bitmap[(n)/8] |= (1 << ((n)%8)))
#define BITMAP_CLR(bitmap, n) (bitmap[(n)/8] &= ~(1 << ((n)%8)))
// Find first free block
int bitmap_find_free(uint8_t *bitmap, size_t size) {
for (size_t i = 0; i < size; i++) {
if (bitmap[i] != 0xFF) { // At least one free bit
for (int j = 0; j < 8; j++) {
if (!(bitmap[i] & (1 << j))) {
return i * 8 + j;
}
}
}
}
return -1; // No free blocks
}
Optimization: Next-Free Hint
Store “next free” pointer in superblock to avoid scanning from start:
uint32_t alloc_block(struct fs_state *fs) {
// Start scanning from hint
int blk = bitmap_find_free_from(fs->block_bitmap,
fs->sb.s_next_free_block,
fs->sb.s_blocks_count);
if (blk < 0) {
// Wrap around to start
blk = bitmap_find_free(fs->block_bitmap, fs->sb.s_next_free_block);
}
if (blk >= 0) {
BITMAP_SET(fs->block_bitmap, blk);
fs->sb.s_free_blocks--;
fs->sb.s_next_free_block = blk + 1;
}
return blk;
}
5. Inode Structure for Persistence
On-disk inodes must be fixed-size and carefully designed:
#define DIRECT_BLOCKS 12
#define INODE_SIZE 128
struct myfs_inode {
uint16_t i_mode; // File type + permissions
uint16_t i_uid; // Owner user ID
uint16_t i_gid; // Owner group ID
uint16_t i_links_count; // Hard link count
uint32_t i_size; // File size (lower 32 bits)
uint32_t i_size_high; // File size (upper 32 bits for >4GB)
uint32_t i_atime; // Access time
uint32_t i_mtime; // Modification time
uint32_t i_ctime; // Status change time
uint32_t i_blocks; // Number of 512-byte blocks
uint32_t i_block[15]; // Block pointers:
// [0-11]: Direct blocks
// [12]: Single indirect
// [13]: Double indirect
// [14]: Triple indirect
uint32_t i_generation; // File version (for NFS)
uint32_t i_reserved[2]; // Future expansion
} __attribute__((packed));
_Static_assert(sizeof(struct myfs_inode) == INODE_SIZE, "Inode size mismatch");
6. Indirect Block Pointers
For files larger than 12 × block_size, use indirection:
┌─────────────────────────────────────────────────────────────────┐
│ Inode │
├─────────────────────────────────────────────────────────────────┤
│ i_block[0] → Data Block 0 │
│ i_block[1] → Data Block 1 │
│ ... │
│ i_block[11] → Data Block 11 (48KB direct) │
│ i_block[12] → Indirect Block → [ptr0, ptr1, ...ptr1023] │
│ ↓ ↓ ↓ │
│ Data Data ... Data │
│ (4MB with 4KB blocks) │
│ i_block[13] → Double Indirect Block → [ind0, ind1, ...] │
│ ↓ │
│ Indirect → [data blocks] │
│ (4GB with 4KB blocks) │
│ i_block[14] → Triple Indirect │
│ (4TB with 4KB blocks) │
└─────────────────────────────────────────────────────────────────┘
Calculating maximum file size (4KB blocks, 4-byte pointers):
| Level | Blocks | Bytes |
|---|---|---|
| Direct (12) | 12 | 48 KB |
| Single Indirect | 1024 | 4 MB |
| Double Indirect | 1024² = 1M | 4 GB |
| Triple Indirect | 1024³ = 1G | 4 TB |
| Total | ~1 billion | ~4 TB |
7. Directory Entry Format
Directories are files containing entries:
struct myfs_dirent {
uint32_t d_ino; // Inode number (0 = deleted)
uint16_t d_rec_len; // Total entry length
uint8_t d_name_len; // Name length
uint8_t d_file_type; // File type hint
char d_name[]; // Filename (variable length)
} __attribute__((packed));
Variable-length entries:
┌────────┬────────┬────────┬────┬─────────────┐
│ inode │rec_len │name_len│type│ name... │
│ (4) │ (2) │ (1) │(1) │ (name_len) │
└────────┴────────┴────────┴────┴─────────────┘
↑
d_rec_len includes padding to 4-byte boundary
8. The Write Path
When writing data to disk, multiple structures need updating:
write("/myfile", data, 100)
│
▼
┌─────────────────────────────────────────────────────────────┐
│ 1. Resolve path → inode │
│ 2. If new file: allocate inode, add directory entry │
│ 3. If extending file: allocate new blocks │
│ 4. Write data to block(s) │
│ 5. Update inode (size, mtime, block pointers) │
│ 6. Update bitmaps if blocks allocated │
│ 7. Update superblock (free counts) │
└─────────────────────────────────────────────────────────────┘
Critical insight: If power fails mid-write, any of these steps might be incomplete. This is the crash consistency problem (solved in Project 4).
Project Specification
Functional Requirements
- mkfs.myfs utility
- Create formatted filesystem image
- Configurable size (1MB - 1TB)
- Initialize superblock, bitmaps, root directory
- FUSE filesystem
- Mount existing filesystem images
- All file operations from Project 2
- Data persists across unmount/remount
- Block allocation
- Bitmap-based free space tracking
- Allocate/free data blocks
- Track in superblock
- Large file support
- Direct blocks for small files
- Single indirect for larger files
- Double indirect for very large files
- fsck.myfs utility
- Verify superblock integrity
- Check bitmap consistency
- Report orphaned blocks/inodes
Non-Functional Requirements
- Support filesystems up to 1TB
- Support files up to 4GB minimum
- Handle thousands of files
- Mount time < 1 second
Solution Architecture
Component Design
┌─────────────────────────────────────────────────────────────────┐
│ mkfs.myfs │
│ (Create new filesystem) │
└────────────────────────┬────────────────────────────────────────┘
│ Creates disk.img
▼
┌─────────────────────────────────────────────────────────────────┐
│ Disk Image (disk.img) │
│ [Superblock][Bitmaps][Inode Table][Data Blocks] │
└────────────────────────┬────────────────────────────────────────┘
│
┌────────────────────────┼────────────────────────────────────────┐
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ Block I/O Layer │ │
│ │ (read_block, write_block, sync) │ │
│ └─────────────────────────┬───────────────────────────────┘ │
│ │ │
│ ┌─────────────────────────┼───────────────────────────────┐ │
│ │ ▼ │ │
│ │ ┌───────────────┐ ┌───────────────┐ ┌───────────────┐ │ │
│ │ │ Superblock │ │ Bitmap │ │ Inode │ │ │
│ │ │ Manager │ │ Manager │ │ Manager │ │ │
│ │ └───────────────┘ └───────────────┘ └───────────────┘ │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ ┌─────────────────────────────────────────────────┐ │ │
│ │ │ Directory Manager │ │ │
│ │ │ (parse/update dir entries) │ │ │
│ │ └─────────────────────────────────────────────────┘ │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ ┌─────────────────────────────────────────────────┐ │ │
│ │ │ File Manager │ │ │
│ │ │ (handle indirect blocks, data I/O) │ │ │
│ │ └─────────────────────────────────────────────────┘ │ │
│ │ │ │
│ │ Filesystem Core │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ FUSE Callbacks │ │
│ │ (myfs_getattr, myfs_read, myfs_write, ...) │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │
│ myfs (FUSE daemon) │
└──────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ fsck.myfs │
│ (Check filesystem integrity) │
└─────────────────────────────────────────────────────────────────┘
Key Data Structures
// Filesystem runtime state
struct myfs_state {
int disk_fd; // Open file descriptor for image
struct myfs_superblock sb; // Cached superblock
uint8_t *inode_bitmap; // Cached inode bitmap
uint8_t *block_bitmap; // Cached block bitmap
struct myfs_inode *inode_cache; // LRU inode cache
size_t cache_size;
pthread_mutex_t lock;
int dirty; // Need to sync?
};
// Block I/O buffer
struct block_buffer {
uint32_t block_num;
uint8_t data[BLOCK_SIZE];
int dirty;
int pin_count;
};
// Indirect block (for reading block pointer arrays)
struct indirect_block {
uint32_t ptrs[BLOCK_SIZE / sizeof(uint32_t)];
};
Key Functions
// Block I/O
int read_block(struct myfs_state *fs, uint32_t blk, void *buf);
int write_block(struct myfs_state *fs, uint32_t blk, const void *buf);
int sync_all(struct myfs_state *fs);
// Bitmap operations
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);
// Inode operations
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_block);
int inode_set_block(struct myfs_state *fs, struct myfs_inode *inode,
uint32_t logical_block, uint32_t physical_block);
// Directory operations
int dir_lookup(struct myfs_state *fs, struct myfs_inode *dir,
const char *name, uint32_t *ino_out);
int dir_add(struct myfs_state *fs, struct myfs_inode *dir,
const char *name, uint32_t ino, uint8_t type);
int dir_remove(struct myfs_state *fs, struct myfs_inode *dir,
const char *name);
// File data operations
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,
const char *buf, size_t size, off_t offset);
int file_truncate(struct myfs_state *fs, struct myfs_inode *inode,
off_t new_size);
Implementation Guide
Phase 1: mkfs Utility (Days 1-3)
Goals:
- Create disk image of specified size
- Initialize superblock with correct values
- Set up empty bitmaps
- Create root directory inode
Steps:
- Parse command-line arguments (size, block size)
- Calculate layout (how many blocks for bitmaps, inodes, data)
- Write superblock
- Initialize bitmaps (mark metadata blocks as used)
- Create root inode (inode 1)
int mkfs_main(const char *image_path, size_t size_mb) {
int fd = open(image_path, O_RDWR | O_CREAT | O_TRUNC, 0644);
ftruncate(fd, size_mb * 1024 * 1024);
uint32_t block_size = 4096;
uint32_t total_blocks = (size_mb * 1024 * 1024) / block_size;
// Calculate layout
uint32_t inode_count = total_blocks / 4; // 1 inode per 4 blocks
uint32_t inode_bitmap_blocks = (inode_count + block_size*8 - 1) / (block_size*8);
uint32_t block_bitmap_blocks = (total_blocks + block_size*8 - 1) / (block_size*8);
uint32_t inode_table_blocks = (inode_count * INODE_SIZE) / block_size;
// Fill in superblock
struct myfs_superblock sb = {
.s_magic = MYFS_MAGIC,
.s_block_size = block_size,
.s_blocks_count = total_blocks,
.s_inodes_count = inode_count,
.s_inode_bitmap = 1,
.s_block_bitmap = 1 + inode_bitmap_blocks,
.s_inode_table = 1 + inode_bitmap_blocks + block_bitmap_blocks,
.s_first_data = 1 + inode_bitmap_blocks + block_bitmap_blocks + inode_table_blocks,
.s_root_inode = 1,
// ...
};
// Write superblock
write_at(fd, 0, &sb, sizeof(sb));
// Initialize bitmaps (all zeros = all free)
// Mark metadata blocks as used in block bitmap
// Create root directory inode
close(fd);
return 0;
}
Testing:
./mkfs.myfs -s 10M test.img
hexdump -C test.img | head -20 # Should see magic number
Phase 2: Block I/O Layer (Days 3-5)
Goals:
- Read/write blocks from disk image
- Cache frequently accessed blocks
- Implement sync for durability
Steps:
- Open disk image file
- Implement
read_block()with seek + read - Implement
write_block()with seek + write - Add simple write-back cache
int read_block(struct myfs_state *fs, uint32_t blk, void *buf) {
if (blk >= fs->sb.s_blocks_count)
return -EINVAL;
off_t offset = (off_t)blk * fs->sb.s_block_size;
if (pread(fs->disk_fd, buf, fs->sb.s_block_size, offset) != fs->sb.s_block_size)
return -EIO;
return 0;
}
int write_block(struct myfs_state *fs, uint32_t blk, const void *buf) {
if (blk >= fs->sb.s_blocks_count)
return -EINVAL;
off_t offset = (off_t)blk * fs->sb.s_block_size;
if (pwrite(fs->disk_fd, buf, fs->sb.s_block_size, offset) != fs->sb.s_block_size)
return -EIO;
return 0;
}
Phase 3: Bitmap Management (Days 5-7)
Goals:
- Load bitmaps into memory
- Allocate/free inodes
- Allocate/free data blocks
Steps:
- Load bitmaps on mount
- Implement
alloc_inode()andfree_inode() - Implement
alloc_block()andfree_block() - Update superblock free counts
- Flush bitmaps on sync/unmount
int alloc_inode(struct myfs_state *fs) {
pthread_mutex_lock(&fs->lock);
for (uint32_t i = 1; i < fs->sb.s_inodes_count; i++) {
if (!BITMAP_GET(fs->inode_bitmap, i)) {
BITMAP_SET(fs->inode_bitmap, i);
fs->sb.s_free_inodes--;
fs->dirty = 1;
pthread_mutex_unlock(&fs->lock);
return i;
}
}
pthread_mutex_unlock(&fs->lock);
return -ENOSPC;
}
Phase 4: Inode Operations (Days 7-10)
Goals:
- Read/write inodes from inode table
- Calculate inode disk location
- Handle inode caching
Steps:
- Calculate inode offset:
inode_table_start + (ino - 1) * INODE_SIZE - Read inode from disk
- Update and write back
- Add simple cache for hot inodes
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 block = fs->sb.s_inode_table +
((ino - 1) * INODE_SIZE) / fs->sb.s_block_size;
uint32_t offset = ((ino - 1) * INODE_SIZE) % fs->sb.s_block_size;
uint8_t buf[fs->sb.s_block_size];
int ret = read_block(fs, block, buf);
if (ret < 0) return ret;
memcpy(inode, buf + offset, sizeof(*inode));
return 0;
}
Phase 5: Indirect Block Support (Days 10-14)
Goals:
- Map logical block numbers to physical blocks
- Allocate indirect blocks as needed
- Support files up to 4GB+
Steps:
inode_get_block(): Given logical block N, return physical block- Handle direct blocks (0-11)
- Handle single indirect (12-1035)
- Handle double indirect (1036+)
- Allocate indirect blocks on write
uint32_t inode_get_block(struct myfs_state *fs, struct myfs_inode *inode,
uint32_t logical) {
uint32_t ptrs_per_block = fs->sb.s_block_size / sizeof(uint32_t);
// Direct blocks
if (logical < DIRECT_BLOCKS) {
return inode->i_block[logical];
}
logical -= DIRECT_BLOCKS;
// Single indirect
if (logical < ptrs_per_block) {
if (inode->i_block[12] == 0) return 0;
struct indirect_block ind;
read_block(fs, inode->i_block[12], &ind);
return ind.ptrs[logical];
}
logical -= ptrs_per_block;
// Double indirect
if (logical < ptrs_per_block * ptrs_per_block) {
if (inode->i_block[13] == 0) return 0;
struct indirect_block dbl;
read_block(fs, inode->i_block[13], &dbl);
uint32_t ind_idx = logical / ptrs_per_block;
uint32_t ptr_idx = logical % ptrs_per_block;
if (dbl.ptrs[ind_idx] == 0) return 0;
struct indirect_block ind;
read_block(fs, dbl.ptrs[ind_idx], &ind);
return ind.ptrs[ptr_idx];
}
// Triple indirect (implement similarly)
return 0;
}
Phase 6: Directory Operations (Days 14-18)
Goals:
- Parse directory entry format
- Add/remove entries
- Handle entry reclamation
Steps:
- Read directory data blocks
- Parse variable-length entries
- Search for name match
- Add new entries (find space or extend)
- Remove entries (mark inode=0, merge with previous)
int dir_lookup(struct myfs_state *fs, struct myfs_inode *dir,
const char *name, uint32_t *ino_out) {
uint8_t buf[fs->sb.s_block_size];
off_t pos = 0;
while (pos < dir->i_size) {
uint32_t blk = inode_get_block(fs, dir, pos / fs->sb.s_block_size);
if (blk == 0) break;
read_block(fs, blk, buf);
uint32_t offset = pos % fs->sb.s_block_size;
while (offset < fs->sb.s_block_size && offset + pos < dir->i_size) {
struct myfs_dirent *de = (struct myfs_dirent *)(buf + offset);
if (de->d_ino != 0 && de->d_name_len == strlen(name) &&
memcmp(de->d_name, name, de->d_name_len) == 0) {
*ino_out = de->d_ino;
return 0;
}
offset += de->d_rec_len;
}
pos = (pos / fs->sb.s_block_size + 1) * fs->sb.s_block_size;
}
return -ENOENT;
}
Phase 7: File Read/Write (Days 18-22)
Goals:
- Read data from file blocks
- Write data, allocating blocks as needed
- Handle sparse files
Steps:
- Calculate which blocks contain requested range
- For reads: handle holes (return zeros)
- For writes: allocate blocks, handle growth
- Update inode size and times
Phase 8: Integration and Testing (Days 22-28)
Goals:
- Connect all components to FUSE
- Build fsck utility
- Test persistence across mounts
Testing scenarios:
# Basic persistence test
./mkfs.myfs -s 100M test.img
./myfs test.img /tmp/myfs
echo "test data" > /tmp/myfs/file.txt
fusermount -u /tmp/myfs
./myfs test.img /tmp/myfs
cat /tmp/myfs/file.txt # Should show "test data"
# Large file test
dd if=/dev/urandom of=/tmp/myfs/large.bin bs=1M count=50
md5sum /tmp/myfs/large.bin > checksum.txt
fusermount -u /tmp/myfs
./myfs test.img /tmp/myfs
md5sum -c checksum.txt # Should pass
# fsck test
./fsck.myfs test.img
Testing Strategy
Unit Tests
// Test bitmap operations
void test_bitmap() {
uint8_t bitmap[16] = {0};
BITMAP_SET(bitmap, 0);
assert(BITMAP_GET(bitmap, 0) == 1);
assert(BITMAP_GET(bitmap, 1) == 0);
BITMAP_SET(bitmap, 100);
assert(BITMAP_GET(bitmap, 100) == 1);
BITMAP_CLR(bitmap, 100);
assert(BITMAP_GET(bitmap, 100) == 0);
int free = bitmap_find_free(bitmap, sizeof(bitmap));
assert(free == 1); // 0 is still set
}
// Test inode block mapping
void test_block_mapping() {
// Mock filesystem with 4KB blocks
// Test direct block access
// Test indirect block access
// Test boundary conditions
}
Integration Tests
#!/bin/bash
# Test filesystem persistence
DISK=/tmp/test_disk.img
MNT=/tmp/test_mnt
cleanup() {
fusermount -u $MNT 2>/dev/null
rm -f $DISK
rmdir $MNT 2>/dev/null
}
trap cleanup EXIT
# Create filesystem
./mkfs.myfs -s 50M $DISK
mkdir -p $MNT
./myfs $DISK $MNT
# Write test data
echo "persistent data" > $MNT/test.txt
mkdir $MNT/subdir
echo "nested" > $MNT/subdir/nested.txt
# Get checksums
md5sum $MNT/test.txt > /tmp/checksums.txt
md5sum $MNT/subdir/nested.txt >> /tmp/checksums.txt
# Unmount and remount
fusermount -u $MNT
./myfs $DISK $MNT
# Verify persistence
md5sum -c /tmp/checksums.txt && echo "PASS: Data persisted" || echo "FAIL"
# Verify fsck
./fsck.myfs $DISK && echo "PASS: Filesystem consistent" || echo "FAIL"
Common Pitfalls and Debugging
Pitfall 1: Off-by-One in Inode Numbers
Problem: Inodes are numbered from 1, not 0.
// WRONG
offset = ino * INODE_SIZE;
// CORRECT
offset = (ino - 1) * INODE_SIZE;
Pitfall 2: Not Syncing on Unmount
Problem: Data lost because writes were cached.
Solution: Implement FUSE destroy callback:
static void myfs_destroy(void *private_data) {
struct myfs_state *fs = private_data;
sync_all(fs);
close(fs->disk_fd);
}
Pitfall 3: Indirect Block Allocation
Problem: Forgetting to allocate and zero indirect blocks.
// When setting a single indirect pointer
if (inode->i_block[12] == 0) {
int blk = alloc_block(fs);
if (blk < 0) return blk;
// Zero the indirect block
uint8_t zeros[fs->sb.s_block_size];
memset(zeros, 0, sizeof(zeros));
write_block(fs, blk, zeros);
inode->i_block[12] = blk;
}
Debugging Techniques
1. Hexdump verification:
# Check superblock
hexdump -C disk.img | head -10
# Check inode table
hexdump -C -s 4096 -n 128 disk.img
2. Add extensive logging:
#define DEBUG 1
#if DEBUG
#define LOG(fmt, ...) fprintf(stderr, "[myfs] " fmt "\n", ##__VA_ARGS__)
#else
#define LOG(fmt, ...)
#endif
LOG("alloc_block: returning block %u", blk);
3. Create debugging dump tool:
./myfs-dump disk.img superblock
./myfs-dump disk.img inode 5
./myfs-dump disk.img block 100
Extensions and Challenges
Extension 1: fsck Repair Mode
Add --fix flag to repair common issues:
- Orphaned blocks (allocated but not referenced)
- Wrong free counts in superblock
- Unreachable inodes
Extension 2: Defragmentation Tool
Identify fragmented files and relocate blocks for contiguous storage.
Extension 3: Sparse File Support
Properly handle files with holes (unallocated regions that read as zeros).
Extension 4: Quotas
Track per-user block and inode usage, enforce limits.
Interview Questions
Conceptual
- “Explain the difference between an inode and a directory entry.”
- Expected: Inode = metadata + block pointers. Directory entry = name → inode mapping.
- “Why do filesystems use indirect pointers?”
- Expected: Fixed inode size, support large files, small files stay efficient.
- “What happens when you delete a file?”
- Expected: Decrement nlink, if 0: free inode, free data blocks, update bitmaps.
Implementation
- “How do you calculate an inode’s disk location?”
- Expected:
inode_table_start + (ino - 1) * inode_size
- Expected:
- “What’s the maximum file size with 12 direct + 1 indirect + 1 double indirect?”
- Expected: Calculate based on block size and pointer size.
- “Why might you find allocated but unreferenced blocks after a crash?”
- Expected: Crash between block allocation and directory entry write.
Self-Assessment Checklist
- mkfs creates valid filesystem with correct layout
- Files persist across unmount/remount
- Large files (>48KB) work correctly
- Directories with many entries work
- fsck reports no errors on clean filesystem
- Free counts in superblock are accurate
- Indirect blocks are properly managed
- Can copy real files (cp, tar) to filesystem
Resources
Books
- “Operating Systems: Three Easy Pieces” Ch. 40-41 - File System Implementation
- “Understanding the Linux Kernel” Ch. 18 - ext2/ext3 Implementation
- “The C Programming Language” Ch. 8.7 - Storage Allocator
Online
- ext2 Design - Official design document
- OSDev Ext2 - Implementation details
- FUSE Tutorial