File System Consistency Checker (xv6 fsck)

 1┌──────────────────────────────────────────┐
 2│ Block 0: Boot Sector                     │
 3├──────────────────────────────────────────┤
 4│ Block 1: Super Block (fs metadata)       │
 5│  - Total blocks, inode count, etc.       │
 6├──────────────────────────────────────────┤
 7│ Blocks 2-9: Inode Map (bitmap)           │
 8│  - Bit i=1 if inode i allocated          │
 9├──────────────────────────────────────────┤
10│ Blocks 10-22: Block Map (bitmap)         │
11│  - Bit j=1 if block j allocated          │
12├──────────────────────────────────────────┤
13│ Blocks 23-200: Inode Array               │
14│  - struct dinode[200]                    │
15│  - 64 bytes per inode; 8 per block       │
16├──────────────────────────────────────────┤
17│ Blocks 201+: Data Blocks                 │
18│  - File contents, directory entries      │
19└──────────────────────────────────────────┘

1struct dinode {
2    short type;           // T_DIR, T_FILE, T_DEV
3    short major, minor;   // Device major/minor
4    short nlink;          // Link count
5    uint size;            // Bytes in file
6    uint addrs[NDIRECT];  // Direct block pointers (12)
7    uint indirect;        // Single indirect block
8};

1For each inode i in inode array:
2    if (inode[i].type != 0):  // Allocated
3        if (inode_bitmap[i] != 1):
4            ERROR: Allocated inode not marked in bitmap
5            REPAIR: Set bitmap bit
6        if (inode[i].nlink < 0):
7            ERROR: Negative link count
8            REPAIR: Set to 0; move to lost+found

 1block_count[0...NBLOCKS] = 0  // Clear reference counts
 2
 3For each inode i:
 4    For each block b in inode[i].addrs:
 5        block_count[b]++
 6        if (block_count[b] > 1):
 7            ERROR: Block multiply allocated
 8            
 9For each block b in block_bitmap:
10    if (bitmap[b] == 1 && block_count[b] == 0):
11        ERROR: Allocated block has 0 references
12        REPAIR: Clear bitmap bit
13    if (bitmap[b] == 0 && block_count[b] > 0):
14        ERROR: Referenced block not in bitmap
15        REPAIR: Set bitmap bit

1For each directory d:
2    For each entry e in d:
3        inode_num = e.inum
4        if (inode_bitmap[inode_num] == 0):
5            ERROR: Directory references unallocated inode
6            REPAIR: Remove directory entry
7        if (inode[inode_num].type == 0):
8            ERROR: Directory entry points to freed inode
9            REPAIR: Remove entry; decrement link count

 1For each inode i:
 2    counted_links = 0
 3    
 4    // Count entries in parent directories
 5    For each directory d:
 6        For each entry e in d:
 7            if (e.inum == i):
 8                counted_links++
 9    
10    // Add . (self-reference) if directory
11    if (i.type == T_DIR):
12        counted_links++
13    
14    if (counted_links != i.nlink):
15        ERROR: Link count mismatch (counted %d, recorded %d)
16        REPAIR: Set i.nlink = counted_links

 1int check_inode_allocation(struct fsck_context *ctx) {
 2    int errors = 0;
 3    
 4    for (uint inum = 0; inum < ctx->sb.ninodes; inum++) {
 5        struct dinode *ip = iget_disk(ctx, inum);
 6        
 7        // Check if type indicates allocation
 8        if (ip->type != 0) {  // Allocated
 9            // Verify bitmap
10            if (!bitmap_get(ctx->inode_bitmap, inum)) {
11                printf("ERROR: Inode %d allocated but not in bitmap\n", inum);
12                bitmap_set(ctx->inode_bitmap, inum);
13                errors++;
14            }
15            
16            // Sanity checks
17            if (ip->nlink < 0) {
18                printf("ERROR: Inode %d has negative link count\n", inum);
19                ip->nlink = 0;
20                errors++;
21            }
22            
23            if (ip->size > MAXSIZE) {
24                printf("ERROR: Inode %d has invalid size %d\n", inum, ip->size);
25                ip->size = 0;
26                errors++;
27            }
28        } else {  // Unallocated
29            // Verify bitmap
30            if (bitmap_get(ctx->inode_bitmap, inum)) {
31                printf("ERROR: Inode %d unallocated but in bitmap\n", inum);
32                bitmap_clear(ctx->inode_bitmap, inum);
33                errors++;
34            }
35        }
36    }
37    
38    return errors;
39}

 1int check_block_allocation(struct fsck_context *ctx) {
 2    uint block_count[NBLOCKS] = {0};
 3    int errors = 0;
 4    
 5    // Count references from all inodes
 6    for (uint inum = 0; inum < ctx->sb.ninodes; inum++) {
 7        struct dinode *ip = iget_disk(ctx, inum);
 8        if (ip->type == 0) continue;  // Unallocated
 9        
10        // Count direct blocks
11        for (int i = 0; i < NDIRECT; i++) {
12            if (ip->addrs[i] > 0) {
13                if (ip->addrs[i] >= ctx->sb.nblocks) {
14                    printf("ERROR: Block %d out of range\n", ip->addrs[i]);
15                    ip->addrs[i] = 0;
16                    errors++;
17                } else {
18                    block_count[ip->addrs[i]]++;
19                }
20            }
21        }
22        
23        // Count indirect blocks
24        if (ip->indirect > 0) {
25            uint *indirect_addrs = read_block(ctx, ip->indirect);
26            for (int i = 0; i < NINDIRECT; i++) {
27                if (indirect_addrs[i] > 0) {
28                    if (indirect_addrs[i] >= ctx->sb.nblocks) {
29                        printf("ERROR: Indirect block %d out of range\n", 
30                               indirect_addrs[i]);
31                        errors++;
32                    } else {
33                        block_count[indirect_addrs[i]]++;
34                    }
35                }
36            }
37            free(indirect_addrs);
38        }
39    }
40    
41    // Verify bitmap matches reference count
42    for (uint b = 0; b < ctx->sb.nblocks; b++) {
43        int in_bitmap = bitmap_get(ctx->block_bitmap, b);
44        int in_use = (block_count[b] > 0);
45        
46        if (in_bitmap && !in_use) {
47            printf("ERROR: Block %d allocated but not referenced\n", b);
48            bitmap_clear(ctx->block_bitmap, b);
49            errors++;
50        }
51        
52        if (!in_bitmap && in_use) {
53            printf("ERROR: Block %d referenced but not allocated\n", b);
54            bitmap_set(ctx->block_bitmap, b);
55            errors++;
56        }
57        
58        if (block_count[b] > 1) {
59            printf("ERROR: Block %d referenced %d times (multiply allocated)\n", 
60                   b, block_count[b]);
61            errors++;
62        }
63    }
64    
65    return errors;
66}

 1int check_directory_entries(struct fsck_context *ctx) {
 2    int errors = 0;
 3    
 4    for (uint inum = 0; inum < ctx->sb.ninodes; inum++) {
 5        struct dinode *ip = iget_disk(ctx, inum);
 6        if (ip->type != T_DIR) continue;
 7        
 8        uint nents = ip->size / sizeof(struct dirent);
 9        struct dirent *entries = read_dir(ctx, inum);
10        
11        for (uint i = 0; i < nents; i++) {
12            struct dirent *de = &entries[i];
13            if (de->inum == 0) continue;  // Empty slot
14            
15            // Verify referenced inode exists
16            if (de->inum >= ctx->sb.ninodes) {
17                printf("ERROR: Dir %d references invalid inode %d\n", 
18                       inum, de->inum);
19                de->inum = 0;
20                errors++;
21                continue;
22            }
23            
24            struct dinode *ref_inode = iget_disk(ctx, de->inum);
25            if (ref_inode->type == 0) {
26                printf("ERROR: Dir %d references freed inode %d\n", 
27                       inum, de->inum);
28                de->inum = 0;
29                errors++;
30            }
31        }
32        
33        free(entries);
34    }
35    
36    return errors;
37}

 1int fix_link_counts(struct fsck_context *ctx) {
 2    uint link_count[ctx->sb.ninodes];
 3    memset(link_count, 0, sizeof(link_count));
 4    
 5    // Count directory references
 6    for (uint inum = 0; inum < ctx->sb.ninodes; inum++) {
 7        struct dinode *ip = iget_disk(ctx, inum);
 8        if (ip->type != T_DIR) continue;
 9        
10        struct dirent *entries = read_dir(ctx, inum);
11        uint nents = ip->size / sizeof(struct dirent);
12        
13        for (uint i = 0; i < nents; i++) {
14            if (entries[i].inum > 0) {
15                link_count[entries[i].inum]++;
16            }
17        }
18        
19        free(entries);
20    }
21    
22    // Add self-reference for directories
23    for (uint inum = 0; inum < ctx->sb.ninodes; inum++) {
24        struct dinode *ip = iget_disk(ctx, inum);
25        if (ip->type == T_DIR) {
26            link_count[inum]++;  // . entry
27        }
28    }
29    
30    // Repair mismatches
31    int errors = 0;
32    for (uint inum = 0; inum < ctx->sb.ninodes; inum++) {
33        struct dinode *ip = iget_disk(ctx, inum);
34        if (ip->type == 0) continue;
35        
36        if (ip->nlink != link_count[inum]) {
37            printf("ERROR: Inode %d nlink mismatch (was %d, should be %d)\n",
38                   inum, ip->nlink, link_count[inum]);
39            ip->nlink = link_count[inum];
40            
41            if (link_count[inum] == 0) {
42                // Orphaned inode; move to lost+found
43                move_to_lost_found(ctx, inum);
44            }
45            
46            errors++;
47        }
48    }
49    
50    return errors;
51}

 1Test Suite: 100 randomly corrupted filesystem images
 2
 3Detection Rate:
 4  - Orphaned inodes: 100% (5/5 detected)
 5  - Block reference errors: 98% (49/50)
 6  - Directory corruption: 95% (19/20)
 7  - Link count mismatches: 100% (26/26)
 8
 9Repair Success Rate:
10  - Successful repairs: 87/100 (87%)
11  - Data loss (orphan recovery): 13/100 (13%)
12  - Unexpected failures: 0/100
13
14I/O Operations:
15  - Bitmap scans: ~500 ops per fs check
16  - Inode traversal: ~200 ops
17  - Directory verification: ~800 ops
18  - Total: ~1500 disk I/O ops
19  - Time: ~2-3 seconds on simulated disk

1ERROR: Block 15 referenced 2 times
2Repair? (y/n): y
3  Option 1: Mark first reference as bad block
4  Option 2: Duplicate file content to new block
5  Select [1-2]: 1

 1# Setup xv6-riscv
 2git clone https://github.com/mit-pdos/xv6-riscv.git
 3cd xv6-riscv
 4
 5# Create filesystem with corruption
 6make fs.img
 7./corrupt_fs.py fs.img  # Inject random corruption
 8
 9# Build fsck tool
10cd fs_checker
11make
12
13# Run fsck
14./fsck ../fs.img
15# Output: Detailed error report + repair recommendations
16
17# Apply repairs (with confirmation)
18./fsck ../fs.img -y  # Auto-repair all

1# Test individual corruption types
2./test_fsck.sh --corrupt-orphans --count=10
3./test_fsck.sh --corrupt-bitmap --count=5
4./test_fsck.sh --corrupt-directories --count=20
5
6# Full regression suite
7make test
8# Runs 100+ corruption scenarios; generates coverage report

 1# Clone and build
 2git clone https://github.com/[user]/xv6-fsck
 3cd xv6-fsck
 4
 5# Build xv6 + fsck
 6make
 7
 8# Create corrupted filesystem
 9python3 corrupt_fs.py xv6.img
10
11# Run fsck
12./fsck xv6.img -verbose
13
14# View results
15cat fsck.report