1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

/*
 * Direct Pointer: Anatomy and Addressing
 * 
 * A direct pointer is a disk block address that points
 * immediately to file data (no intermediate index blocks).
 */
 
#include <stdint.h>
 
/* Pointer size determines addressable space */
typedef uint64_t block_ptr_t;  /* 64-bit for modern systems */
typedef uint32_t block_ptr32_t; /* 32-bit for legacy systems */
 
#define BLOCK_SIZE      4096    /* 4KB blocks */
#define NULL_BLOCK_PTR  0       /* Indicates unallocated/hole */
 
/*
 * Addressing Calculation:
 * 
 * disk_offset = block_pointer × block_size
 * 
 * Example: Pointer value 1000 with 4KB blocks
 *   disk_offset = 1000 × 4096 = 4,096,000 bytes
 *   This is where the data block starts on disk.
 */
uint64_t block_ptr_to_disk_offset(block_ptr_t ptr) {
    return (uint64_t)ptr * BLOCK_SIZE;
}
 
/*
 * Memory Layout of Direct Pointers in an Inode
 * 
 * Traditional Unix: 12 direct pointers, each 4 or 8 bytes
 * 
 *  Byte Offset    Contents
 *  -----------    --------
 *  [0-7]          direct_block[0]   → File bytes 0-4095
 *  [8-15]         direct_block[1]   → File bytes 4096-8191
 *  [16-23]        direct_block[2]   → File bytes 8192-12287
 *  ...
 *  [88-95]        direct_block[11]  → File bytes 45056-49151
 *  [96-103]       indirect_block    → (for larger files)
 *  [104-111]      double_indirect   → (for even larger files)
 *  [112-119]      triple_indirect   → (for massive files)
 */
 
#define NUM_DIRECT_POINTERS  12
 
struct inode_pointers {
    block_ptr_t direct[NUM_DIRECT_POINTERS];  /* 12 × 8 = 96 bytes */
    block_ptr_t indirect;                      /* 8 bytes */
    block_ptr_t double_indirect;               /* 8 bytes */
    block_ptr_t triple_indirect;               /* 8 bytes */
};  /* Total: 120 bytes for block pointers */
 
/*
 * Maximum file size addressable by direct pointers only:
 * 
 * 12 pointers × 4096 bytes/block = 49,152 bytes = 48 KB
 * 
 * This covers the vast majority of files on typical systems!
 */
#define MAX_DIRECT_FILE_SIZE  (NUM_DIRECT_POINTERS * BLOCK_SIZE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

/*
 * File System Capacity Calculations
 * 
 * Understanding the math behind indexed allocation capacity
 */
 
#include <stdio.h>
#include <stdint.h>
 
/* Configuration parameters */
#define BLOCK_SIZE_BYTES    4096
#define POINTER_SIZE_BYTES  8
#define NUM_DIRECT_PTRS     12
 
/* Derived values */
#define PTRS_PER_INDIRECT_BLOCK  (BLOCK_SIZE_BYTES / POINTER_SIZE_BYTES)
 
void calculate_file_system_limits() {
    /* Direct pointer capacity */
    uint64_t direct_capacity = NUM_DIRECT_PTRS * BLOCK_SIZE_BYTES;
    printf("Direct pointers only: %lu bytes (%.1f KB)
", 
           direct_capacity, (double)direct_capacity / 1024);
    
    /* Single indirect adds another level */
    uint64_t single_indirect = PTRS_PER_INDIRECT_BLOCK * BLOCK_SIZE_BYTES;
    printf("Single indirect block: %lu bytes (%.1f MB)
",
           single_indirect, (double)single_indirect / (1024 * 1024));
    
    /* Double indirect: pointer to block of pointers to data */
    uint64_t double_indirect = (uint64_t)PTRS_PER_INDIRECT_BLOCK * 
                               PTRS_PER_INDIRECT_BLOCK * 
                               BLOCK_SIZE_BYTES;
    printf("Double indirect block: %lu bytes (%.1f GB)
",
           double_indirect, (double)double_indirect / (1024 * 1024 * 1024));
    
    /* Triple indirect: one more level of indirection */
    uint64_t triple_indirect = (uint64_t)PTRS_PER_INDIRECT_BLOCK * 
                               PTRS_PER_INDIRECT_BLOCK *
                               PTRS_PER_INDIRECT_BLOCK * 
                               BLOCK_SIZE_BYTES;
    printf("Triple indirect block: %lu bytes (%.1f TB)
",
           triple_indirect, (double)triple_indirect / (1024.0 * 1024 * 1024 * 1024));
    
    /* Total maximum file size */
    uint64_t max_file_size = direct_capacity + 
                             single_indirect + 
                             double_indirect + 
                             triple_indirect;
    printf("Maximum file size: ~%.1f TB
",
           (double)max_file_size / (1024.0 * 1024 * 1024 * 1024));
}
 
/*
 * Output with typical 4KB blocks, 8-byte pointers:
 * 
 * Direct pointers only: 49152 bytes (48.0 KB)
 * Single indirect block: 2097152 bytes (2.0 MB)
 * Double indirect block: 1073741824 bytes (1.0 GB)
 * Triple indirect block: 549755813888 bytes (512.0 GB)
 * Maximum file size: ~514.0 TB
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

/*
 * Direct Pointer Access: Step-by-Step Implementation
 * 
 * This function reads data from a file using only direct pointers.
 * It demonstrates the efficient O(1) mapping from file offset to disk location.
 */
 
#define BLOCK_SIZE          4096
#define NUM_DIRECT_POINTERS 12
 
struct file_context {
    struct inode    *inode;         /* Cached inode */
    uint64_t        position;       /* Current file position */
    int             flags;          /* Open flags */
};
 
/*
 * Read bytes from a file at the current position.
 * 
 * This version handles only direct pointers (first 48KB of file).
 * Real implementations extend this to handle indirect pointers.
 */
ssize_t read_via_direct_pointers(struct file_context *ctx, 
                                  void *buffer, 
                                  size_t count) {
    struct inode *inode = ctx->inode;
    char *buf = (char *)buffer;
    size_t total_read = 0;
    
    /* Don't read past end of file */
    if (ctx->position >= inode->size) {
        return 0;  /* EOF */
    }
    if (ctx->position + count > inode->size) {
        count = inode->size - ctx->position;
    }
    
    while (total_read < count) {
        /*
         * Step 1: Calculate which logical block contains this position
         * 
         * With 4KB blocks:
         *   Position 0-4095    → Block 0
         *   Position 4096-8191 → Block 1
         *   Position 5000      → Block 1 (5000 / 4096 = 1)
         */
        uint64_t logical_block = ctx->position / BLOCK_SIZE;
        
        /* Check if we've exceeded direct pointer range */
        if (logical_block >= NUM_DIRECT_POINTERS) {
            /* Would need indirect pointer handling here */
            break;
        }
        
        /*
         * Step 2: Look up the physical block in the inode
         * 
         * This is O(1) - just an array access!
         * The direct pointer tells us exactly where on disk.
         */
        block_ptr_t physical_block = inode->direct[logical_block];
        
        if (physical_block == 0) {
            /* Hole in sparse file - return zeros */
            size_t hole_size = MIN(BLOCK_SIZE, count - total_read);
            memset(buf + total_read, 0, hole_size);
            total_read += hole_size;
            ctx->position += hole_size;
            continue;
        }
        
        /*
         * Step 3: Calculate offset within the block
         * 
         * Position 5000 in block 1:
         *   offset_in_block = 5000 % 4096 = 904
         */
        uint64_t offset_in_block = ctx->position % BLOCK_SIZE;
        
        /*
         * Step 4: Calculate disk location
         * 
         * disk_offset = physical_block × block_size + offset_in_block
         *             = 2847 × 4096 + 904
         *             = 11,662,216
         */
        uint64_t disk_offset = (physical_block * BLOCK_SIZE) + offset_in_block;
        
        /*
         * Step 5: Calculate how many bytes to read from this block
         * 
         * We might not read the entire block if:
         *   - We started in the middle (offset_in_block > 0)
         *   - We only need a few more bytes to complete the request
         */
        size_t bytes_available_in_block = BLOCK_SIZE - offset_in_block;
        size_t bytes_remaining = count - total_read;
        size_t bytes_to_read = MIN(bytes_available_in_block, bytes_remaining);
        
        /*
         * Step 6: Perform the actual disk read
         * 
         * Most systems use block caching here - if the block is in
         * the buffer cache, no disk I/O is needed at all!
         */
        disk_read(disk_offset, buf + total_read, bytes_to_read);
        
        total_read += bytes_to_read;
        ctx->position += bytes_to_read;
    }
    
    /* Update access time (if not mounted with 'noatime') */
    inode->atime = current_time();
    
    return total_read;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

/*
 * Managing Direct Pointers During File Growth
 * 
 * This demonstrates how direct pointers are populated as a file
 * grows from 0 bytes to beyond the direct pointer limit.
 */
 
#define BLOCK_SIZE          4096
#define NUM_DIRECT_POINTERS 12
 
struct inode {
    uint64_t        size;
    block_ptr_t     direct[NUM_DIRECT_POINTERS];
    block_ptr_t     indirect;
    block_ptr_t     double_indirect;
    block_ptr_t     triple_indirect;
    /* ... other metadata ... */
};
 
/*
 * Allocate blocks to extend a file.
 * 
 * Returns the physical block allocated, or 0 on failure.
 * This function handles only the direct pointer range.
 */
int extend_file_direct(struct inode *inode, size_t new_size) {
    /* Calculate current and needed logical blocks */
    uint64_t current_blocks = (inode->size + BLOCK_SIZE - 1) / BLOCK_SIZE;
    uint64_t needed_blocks = (new_size + BLOCK_SIZE - 1) / BLOCK_SIZE;
    
    if (needed_blocks <= current_blocks) {
        /* File isn't actually growing in block count */
        inode->size = new_size;
        return 0;
    }
    
    /* Allocate each new block needed */
    for (uint64_t block = current_blocks; block < needed_blocks; block++) {
        if (block >= NUM_DIRECT_POINTERS) {
            /*
             * Exceeded direct pointer range!
             * Would need to allocate indirect block here.
             * 
             * Real implementation would:
             * 1. Allocate a block for the indirect pointer
             * 2. Set inode->indirect to point to it
             * 3. Continue allocating via indirect block
             */
            return -EFBIG;  /* "File too big" for this simple impl */
        }
        
        /* Allocate a new data block from free space */
        block_ptr_t new_block = allocate_block();
        if (new_block == 0) {
            return -ENOSPC;  /* No space left */
        }
        
        /* Update direct pointer */
        inode->direct[block] = new_block;
        
        /*
         * Visualization of inode after growing from 0 to 20KB:
         *
         *   direct[0]  = Block 500   ← 0-4095 bytes
         *   direct[1]  = Block 501   ← 4096-8191 bytes
         *   direct[2]  = Block 502   ← 8192-12287 bytes
         *   direct[3]  = Block 503   ← 12288-16383 bytes
         *   direct[4]  = Block 504   ← 16384-20479 bytes
         *   direct[5]  = 0           ← Not yet allocated
         *   ...
         *   direct[11] = 0           ← Not yet allocated
         *   indirect   = 0           ← Not needed yet
         */
    }
    
    inode->size = new_size;
    return 0;
}
 
/*
 * Example: Writing to a new file
 * 
 * File starts with size = 0, all direct pointers = 0.
 * 
 * write(fd, "Hello World", 11);
 * → allocate block (say, block 100)
 * → set direct[0] = 100
 * → write "Hello World" to block 100, offset 0
 * → set size = 11
 * 
 * write(fd, data, 5000);  /* Now at offset 11, writing 5000 bytes */
 * → Direct[0] block 100 has room for 4096 - 11 = 4085 more bytes
 * → Write 4085 bytes to block 100
 * → Need 5000 - 4085 = 915 more bytes
 * → Allocate block (say, block 101) 
 * → Set direct[1] = 101
 * → Write remaining 915 bytes to block 101
 * → Set size = 5011
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

/*
 * Sparse Files: Physical vs Logical Size
 * 
 * A sparse file's logical size (what stat reports) can be much
 * larger than its physical size (actual disk blocks used).
 */
 
/*
 * Creating a sparse file:
 * 
 * 1. Create file (size = 0)
 * 2. Seek to offset 1,000,000
 * 3. Write "X" (1 byte)
 * 4. File is now 1,000,001 bytes logical but uses only 1 block!
 */
void create_sparse_file(const char *path) {
    int fd = open(path, O_WRONLY | O_CREAT | O_TRUNC, 0644);
    
    /* Seek to 1MB offset without writing intervening bytes */
    lseek(fd, 1000000, SEEK_SET);
    
    /* Write a single byte */
    write(fd, "X", 1);
    
    close(fd);
    
    /*
     * Resulting inode state (with 4KB blocks):
     * 
     * Logical file size: 1,000,001 bytes
     * Physical blocks used: 1 (block for offset 997,376 - 1,001,471)
     * 
     * Block 244 is the only block containing data (1MB / 4096 = 244)
     * 
     * direct[0] through direct[11] = 0  (holes)
     * indirect points to block with:
     *   pointer[0] through pointer[243] = 0  (holes)
     *   pointer[244] = some_block_number  (contains "X" at offset 928)
     *   pointer[245+] = 0  (beyond EOF)
     */
}
 
/*
 * Reading from a sparse file hole:
 */
ssize_t read_with_hole_support(struct inode *inode, 
                               uint64_t offset, 
                               void *buf, 
                               size_t count) {
    uint64_t logical_block = offset / BLOCK_SIZE;
    uint64_t block_offset = offset % BLOCK_SIZE;
    
    block_ptr_t physical = inode->direct[logical_block];
    
    if (physical == 0) {
        /*
         * This is a hole - return zeros.
         * No disk I/O needed!
         */
        size_t hole_bytes = MIN(count, BLOCK_SIZE - block_offset);
        memset(buf, 0, hole_bytes);
        return hole_bytes;
    }
    
    /* Normal read from physical block */
    return disk_read(physical * BLOCK_SIZE + block_offset, buf, count);
}
 
/*
 * Detecting sparse files:
 * 
 * $ ls -ls sparse_file
 * 4 -rw-r--r-- 1 user user 1000001 Jan 15 10:00 sparse_file
 * ^                        ^^^^^^^
 * |                        Logical size: 1MB
 * Physical blocks: 4KB (1 block)
 * 
 * st.st_blocks reports 512-byte sectors (8 sectors = 4KB block)
 */