Operating SystemsFile System Structures

Unix inode Structure

LevelIntermediate

Duration75 mins

TopicFile System Structures

5 / 5

Double/Triple Indirect

Scaling to Terabytes: Recursive Indirection

We've seen how 12 direct pointers address 48KB and a single indirect block extends this to about 4MB. But modern files can be vastly larger—database files spanning hundreds of gigabytes, virtual machine images measured in terabytes, scientific datasets that dwarf anything the original Unix designers imagined.

How does a small, fixed-size inode address files of essentially unlimited size?

The answer lies in the recursive application of indirection. Just as a single indirect block contains pointers to data blocks, a double indirect block contains pointers to single indirect blocks, and a triple indirect block contains pointers to double indirect blocks. This creates a tree structure capable of addressing astronomical amounts of data.

This is the final piece of the classic Unix block addressing scheme—and understanding it reveals both the elegance and the limitations that led to modern alternatives like extents.

What You Will Learn

By the end of this page, you will understand: how double and triple indirect blocks work as recursive tree structures; the complete mathematics of Unix file size limits; I/O costs and performance implications of deep indirection; why triple indirect is rarely used in practice; how modern extent-based designs improve upon this classic scheme; and when traditional block pointers still make sense.

Double Indirect Blocks

The 14th pointer in the inode's block array (index 13) is the double indirect pointer. It points to a block that contains pointers to single indirect blocks, each of which contains pointers to data blocks.

The hierarchy:

Inode block[13]
    ↓
Double Indirect Block (1024 pointers)
    ↓ ↓ ↓ ... ↓
1024 Single Indirect Blocks (each with 1024 pointers)
    ↓ ↓ ↓ ... ↓
1,048,576 Data Blocks

Capacity calculation (4KB blocks, 4-byte pointers):

Pointers per block (k) = 4096 / 4 = 1024

Double Indirect Capacity = k × k × block_size
                        = 1024 × 1024 × 4096
                        = 4,294,967,296 bytes
                        = 4 GB

A single double indirect pointer provides access to 4GB of file data—a thousand times more than single indirect.

Converting Mermaid diagram...

Accessing data through double indirect:

To read byte 100,000,000 (approximately 95.4 MB):

1. Calculate logical block:
   100,000,000 / 4096 = 24,414 (with remainder)

2. Determine addressing level:
   - Direct: blocks 0-11 (12 blocks)
   - Single indirect: blocks 12 - (12 + 1024 - 1) = 12-1035 (1024 blocks)
   - Double indirect: starts at block 1036
   
   24,414 > 1035, so we need double indirect

3. Calculate offset within double indirect:
   Offset = 24,414 - 12 - 1024 = 23,378

4. Navigate the tree:
   - First-level index: 23,378 / 1024 = 22 (which single indirect block)
   - Second-level index: 23,378 % 1024 = 850 (which entry in that single indirect)

5. I/O sequence:
   a. Read inode→block[13] → get double indirect block #
   b. Read double indirect block, get entry[22] → single indirect block #
   c. Read single indirect block, get entry[850] → data block #
   d. Read data block at calculated offset

Total I/O: 4 reads (inode + double + single + data)

Triple Indirect Blocks

The 15th and final pointer (index 14) is the triple indirect pointer. It adds another level of indirection, pointing to a block of double indirect pointers.

Capacity calculation (4KB blocks, 4-byte pointers):

Triple Indirect Capacity = k × k × k × block_size
                        = 1024 × 1024 × 1024 × 4096
                        = 4,398,046,511,104 bytes
                        = 4 TB

The triple indirect pointer alone can address 4 terabytes of file data.

Complete Unix File Addressing Capacity (4KB blocks, 4-byte pointers)
Level	Pointer Count	Capacity	Cumulative Max Size	I/O Depth
Direct	12	48 KB	48 KB	1
Single Indirect	1	4 MB	~4.05 MB	2
Double Indirect	1	4 GB	~4.004 GB	3
Triple Indirect	1	4 TB	~4.004 TB	4
Total Theoretical	15	—	~4 TB	4 max

Why no quadruple indirect?

With triple indirect providing 4TB capacity using 32-bit block pointers, the design already exceeds what most systems need. The reasons for stopping at three levels:

Sufficient capacity: 4TB addressed virtually any file in the ext2/ext3 era
I/O depth limit: 4 reads per access is already significant
Inode size budget: 15 pointers fit the target inode size
Diminishing returns: Each level adds I/O cost for rarely-accessed regions

Modern 64-bit filesystems with larger block pointers and extents address far larger files without needing more indirection levels.

The 4TB Limit's Historical Context

When ext2 was designed in the early 1990s, hard drives were measured in megabytes. A 4TB file seemed impossibly large. Today, consumer SSDs exceed 4TB. This is why ext4 introduced extents and 48-bit block addressing—the classic scheme's limits became real constraints.

Complete Address Space Mapping

Let's formalize the complete mapping from logical byte offset to block pointer path. This algorithm is at the heart of every Unix filesystem implementation:

block_address_resolution.c
C
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
/**
 * Resolve a logical file offset to a physical block number
 * This is the complete block addressing algorithm
 */
#define DIRECT_BLOCKS 12
#define BLOCK_SIZE 4096
#define PTRS_PER_BLOCK (BLOCK_SIZE / sizeof(u32))  // 1024
 
typedef struct {
    int level;          // 0=direct, 1=single, 2=double, 3=triple
    u32 offsets[4];     // indices at each level (max 4 levels)
} BlockPath;
 
BlockPath calculate_block_path(off_t byte_offset) {
    BlockPath path = {0};
    u64 logical_block = byte_offset / BLOCK_SIZE;
    
    // Capacity at each level
    const u64 direct_max = DIRECT_BLOCKS;                              // 12
    const u64 single_max = PTRS_PER_BLOCK;                             // 1024
    const u64 double_max = PTRS_PER_BLOCK * PTRS_PER_BLOCK;            // 1M
    const u64 triple_max = PTRS_PER_BLOCK * PTRS_PER_BLOCK * PTRS_PER_BLOCK; // 1G
    
    if (logical_block < direct_max) {
        // Direct block: block[logical_block]
        path.level = 0;
        path.offsets[0] = logical_block;
        return path;
    }
    logical_block -= direct_max;
    
    if (logical_block < single_max) {
        // Single indirect: block[12] -> indirect[logical_block]
        path.level = 1;
        path.offsets[0] = 12;  // inode->block[12]
        path.offsets[1] = logical_block;
        return path;
    }
    logical_block -= single_max;
    
    if (logical_block < double_max) {
        // Double indirect: block[13] -> double[i] -> single[j] -> data
        path.level = 2;
        path.offsets[0] = 13;
        path.offsets[1] = logical_block / PTRS_PER_BLOCK;
        path.offsets[2] = logical_block % PTRS_PER_BLOCK;
        return path;
    }
    logical_block -= double_max;
    
    if (logical_block < triple_max) {
        // Triple indirect: block[14] -> triple[i] -> double[j] -> single[k] -> data
        path.level = 3;
        path.offsets[0] = 14;
        path.offsets[1] = logical_block / (PTRS_PER_BLOCK * PTRS_PER_BLOCK);
        u64 remainder = logical_block % (PTRS_PER_BLOCK * PTRS_PER_BLOCK);
        path.offsets[2] = remainder / PTRS_PER_BLOCK;
        path.offsets[3] = remainder % PTRS_PER_BLOCK;
        return path;
    }
    
    // Beyond triple indirect - file too large for this addressing scheme
    path.level = -1;
    return path;
}
 
// Example usage:
// Byte 100,000,000 -> logical block 24,414
// Path: level=2, offsets=[13, 22, 850]
// Meaning: inode->block[13] -> double_indirect[22] -> single_indirect[850] -> data

Visual representation of the address space:

Logical Block Range          Addressing Level         I/O Reads
────────────────────────────────────────────────────────────────
0 - 11                       Direct                   1
12 - 1,035                   Single Indirect          2
1,036 - 1,049,611            Double Indirect          3
1,049,612 - 1,074,791,435    Triple Indirect          4
────────────────────────────────────────────────────────────────

Byte Range (4KB blocks)
────────────────────────────────────────────────────────────────
0 - 49,151                   Direct                   48 KB
49,152 - 4,243,455           Single Indirect          ~4 MB
4,243,456 - 4,299,161,599    Double Indirect          ~4 GB
4,299,161,600 - 4,402,345,713,663  Triple Indirect    ~4 TB

I/O Cost Analysis: The Price of Depth

Each level of indirection adds one disk read (unless cached). Let's analyze the impact:

I/O Operations by Indirection Level
Access Type	Direct	Single Ind.	Double Ind.	Triple Ind.
Cold read (nothing cached)	2	3	4	5
Warm read (inode cached)	1	2	3	4
Hot read (all indirect cached)	1	1	1	1
Sequential scan (amortized)	~1	~1	~1.001	~1.001

Random access worst case:

Accessing triple indirect with cold cache:

HDD (10ms seek per read):
5 reads × 10ms = 50ms latency

SSD (100μs random read):
5 reads × 100μs = 500μs latency

NVMe (20μs random read):
5 reads × 20μs = 100μs latency

This is why random access to large files on HDDs was historically painful—multiple seeks compound.

Sequential access amortization:

Reading 1GB sequentially:

Blocks read: 262,144
Indirect blocks touched:
- 1 single indirect
- 1 double indirect  
- 256 single indirects (in double)

Total reads: 262,144 + 258
Overhead: 258/262,144 = 0.1%

Sequential I/O amortizes indirect block reads across many data blocks.

Cache effectiveness by level:

┌────────────────────────────────────────────────────────────────────┐
│  Indirect Block Caching Effectiveness                              │
├────────────────────────────────────────────────────────────────────┤
│                                                                    │
│  Single Indirect (1 block):                                        │
│  - Covers 4MB of file data                                         │
│  - 4KB cache entry serves 1024 data block accesses                 │
│  - Extremely cache-friendly                                        │
│                                                                    │
│  Double Indirect (1 + 1024 blocks):                                │
│  - Top level covers entire 4GB range                               │
│  - Each second-level block covers 4MB                              │
│  - Locality determines cache effectiveness                         │
│  - Random access across 4GB may thrash cache                       │
│                                                                    │
│  Triple Indirect (1 + 1024 + 1M blocks):                           │
│  - Top level covers entire 4TB range                               │
│  - Lower levels depend heavily on access pattern                   │
│  - Random access across 4TB definitely thrashes cache              │
│  - Sequential access still caches well due to locality             │
│                                                                    │
└────────────────────────────────────────────────────────────────────┘

Triple Indirect: Rarely Worth It

Files large enough to use triple indirect (>4GB) typically have poor random access performance regardless of caching. Modern systems handling such files usually use memory-mapped I/O, striping across drives, or extent-based filesystems that avoid deep indirection entirely.

Space Overhead of Deep Indirection

Indirect blocks consume disk space. Let's calculate the overhead for files of various sizes:

Indirect Block Space Overhead
File Size	Data Blocks	Indirect Blocks	Overhead	Notes
48 KB	12	0	0%	Direct only
4 MB	1,024	1	0.098%	1 single indirect
100 MB	25,600	26	0.10%	1 single + 1 double + 24 single
1 GB	262,144	258	0.098%	1+1+256 = 258 indirect blocks
4 GB	1,048,576	1,026	0.098%	1+1+1024 = 1,026 indirect
100 GB	26,214,400	25,857	0.099%	Deep into triple indirect
1 TB	268,435,456	262,657	0.098%	~1GB of indirect blocks

Key observation: The overhead is remarkably consistent at approximately 0.1% regardless of file size. This is because each level of indirection has the same fanout ratio:

Data blocks per indirect block level:
- Single: 1024 data blocks per 1 indirect block
- Double: 1024² data blocks per (1 + 1024) indirect blocks
- Triple: 1024³ data blocks per (1 + 1024 + 1024²) indirect blocks

As n → ∞:
Overhead ratio = 1/1023 ≈ 0.098%

Comparison with other schemes:

Metadata Overhead Comparison
Scheme	Overhead for 1GB File	Overhead for 4TB File	Random Access
Unix indirect	~0.1%	~0.1%	O(log₁₀₂₄ n) = O(1)
FAT linked list	~0.1%	~0.1%	O(n)
Extent list	~0.001% (typical)	~0.001%	O(log n)
B-tree extents	~0.01%	~0.01%	O(log n)

Fragmentation Matters More

The 0.1% overhead of indirect blocks is usually insignificant compared to fragmentation costs. A heavily fragmented file might have 10x the indirect blocks (if every data block requires its own pointer) but still only 1% overhead. The real cost is in I/O—seeking between scattered blocks dominates.

Implementation Details and Edge Cases

Implementing multi-level indirect blocks involves several subtle considerations:

Implementation Considerations

•Lazy allocation at every level — Indirect blocks are allocated only when the file grows into their range. A 1GB sparse file with data only at the end might need just a few indirect blocks.
•Zero-initialization is mandatory — New indirect blocks must be zeroed. Any garbage data would be interpreted as block pointers, causing corruption.
•Truncation must be bottom-up — When shrinking a file, first free data blocks, then their pointing indirect blocks. Otherwise, you'd lose the pointers needed to find data blocks.
•Hole handling at every level — A zero pointer in any indirect block indicates a hole. Walking the tree must check for zeros at each level.
•Transaction atomicity — Growing a file may require allocating multiple indirect blocks. All must be committed atomically via journaling.

truncate_indirect.c
C
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
/**
 * Truncate file: Free blocks from double indirect level
 * Demonstrates the complexity of multi-level cleanup
 */
void truncate_double_indirect(struct inode *inode, u64 new_block_count) {
    if (inode->block[13] == 0) return;  // No double indirect
    
    u32 *double_ind = read_block(inode->block[13]);
    bool double_empty = true;
    
    for (int i = PTRS_PER_BLOCK - 1; i >= 0; i--) {
        if (double_ind[i] == 0) continue;
        
        // Calculate which blocks this single indirect covers
        u64 start = DIRECT_BLOCKS + PTRS_PER_BLOCK + (i * PTRS_PER_BLOCK);
        u64 end = start + PTRS_PER_BLOCK;
        
        if (end <= new_block_count) {
            // Entire single indirect is still in use
            double_empty = false;
            continue;
        }
        
        // Need to process this single indirect
        u32 *single_ind = read_block(double_ind[i]);
        bool single_empty = true;
        
        for (int j = PTRS_PER_BLOCK - 1; j >= 0; j--) {
            u64 block_num = start + j;
            if (block_num >= new_block_count && single_ind[j] != 0) {
                // Free this data block
                free_block(single_ind[j]);
                single_ind[j] = 0;
                mark_buffer_dirty(single_ind);
            }
            if (single_ind[j] != 0) single_empty = false;
        }
        
        if (single_empty) {
            // Free the now-empty single indirect block
            free_block(double_ind[i]);
            double_ind[i] = 0;
            mark_buffer_dirty(double_ind);
        } else {
            double_empty = false;
        }
    }
    
    if (double_empty) {
        // Free the double indirect block itself
        free_block(inode->block[13]);
        inode->block[13] = 0;
    }
}

Truncation is Expensive

Truncating a 4TB file to zero requires freeing up to 1 billion+ blocks and 1 million+ indirect blocks. This can take minutes on mechanical drives. Some filesystems defer this work or perform it asynchronously to avoid blocking the truncate() call.

Modern Alternative: Extent-Based Addressing

The indirect block scheme, while elegant, has limitations that led to the development of extent-based addressing in modern filesystems:

Problems with indirect blocks:

One pointer per block — A contiguous 1GB region requires 262,144 pointers, one for each 4KB block
Fragmentation amplifies overhead — Many small extents = many indirect blocks
Fixed maximum depth — Triple indirect limits size (works around with 64-bit pointers)
Metadata not colocated — Indirect blocks may be scattered across disk

Indirect Blocks vs. Extents
Aspect	Indirect Blocks	Extents
Contiguous 1GB file	262,144 + 258 entries	1 extent entry
Maximum file size (32-bit)	~4TB	~16TB (typical)
Random access complexity	O(1) fixed levels	O(log n) tree search
Fragmentation handling	Works but verbose	Needs more extents
Space efficiency	~0.1% overhead always	Near-zero for contiguous
Implementation complexity	Simple arithmetic	B-tree or similar

Ext4's extent structure:

struct ext4_extent {
    __le32 ee_block;      // First logical block covered
    __le16 ee_len;        // Number of blocks (up to 32768)
    __le16 ee_start_hi;   // Physical start block (high bits)
    __le32 ee_start_lo;   // Physical start block (low bits)
};
// 12 bytes per extent

// A single extent can describe:
// - Up to 128MB of contiguous data (32768 × 4KB)
// - In 12 bytes, vs 32KB of indirect pointers for same range

Key insight: Extents map ranges, not individual blocks. A well-defragmented file might be described by a single extent, regardless of size.

Ext4's Hybrid Approach

Ext4 can use either indirect blocks OR extents per-file. It defaults to extents for new files but supports the old scheme for backward compatibility and for files with many small fragments. The inode flag EXT4_EXTENTS_FL indicates which scheme a file uses.

When Indirect Blocks Still Make Sense

Despite the advantages of extents, indirect blocks remain relevant in specific scenarios:

Scenarios Favoring Indirect Blocks

•Highly fragmented files — A file with thousands of single-block extents might use MORE space with extent metadata than indirect blocks.
•Small files — For files under 48KB, direct blocks in the inode are unbeatable. No separate extent tree needed.
•Sparse files with scattered holes — Indirect blocks naturally handle sparse regions with zero pointers at any level.
•Legacy compatibility — Older tools and recovery software often understand indirect blocks but not modern extent formats.
•Simplicity — For embedded systems or simple filesystem implementations, indirect blocks are easier to implement correctly.
•Predictable overhead — The ~0.1% overhead is consistent; extent overhead varies with fragmentation.

Best for indirect blocks:

Small filesystems
Many small files
Heavy fragmentation expected
Simple implementation needed
Legacy compatibility required
Embedded systems

Example: /tmp with many small temporary files

Best for extents:

Large sequential files
Database files
Media files
Virtual machine images
Well-defragmented storage
Modern hardware

Example: Database server with multi-GB data files

Know Your Workload

The choice between indirect blocks and extents should be driven by workload analysis. Run 'filefrag' on representative files to see fragmentation patterns. If most files are single extents, extents win. If files have hundreds of fragments, the difference is smaller.

Summary: The Complete Block Addressing Picture

We've completed our journey through Unix inode block addressing, from the simplest direct pointers to the depths of triple indirection. Let's consolidate everything:

Complete Block Addressing Summary (4KB blocks, 4-byte pointers)
Component	Capacity	I/O Depth	Use Case
12 Direct	48 KB	1	Most files (configs, source code)
1 Single Indirect	4 MB	2	Medium files (documents, small images)
1 Double Indirect	4 GB	3	Large files (videos, databases)
1 Triple Indirect	4 TB	4	Huge files (VM images, archives)
Combined	~4 TB	1-4	Any Unix file

Key Takeaways

•Recursive indirection scales exponentially — Each level multiplies capacity by the pointers-per-block factor (typically 1024).
•I/O cost increases linearly with depth — But caching makes this cost nearly invisible for common access patterns.
•Space overhead is consistently minimal — Approximately 0.1% regardless of file size.
•The design optimizes for common cases — Small files use direct blocks; larger files pay progressive indirection costs.
•Modern extents build on these principles — They trade per-block addressing for range-based addressing, improving contiguous file handling.
•Understanding this scheme is still essential — Even with extents, the principles of hierarchical addressing, caching, and space/time tradeoffs apply universally.

Module Complete:

You now have a complete understanding of the Unix inode structure—from the conceptual separation of metadata and data, through the rich contents of the inode, to the elegant multi-level block addressing scheme that has influenced decades of filesystem design.

This knowledge forms the foundation for understanding modern filesystems like ext4, XFS, Btrfs, and even non-Unix systems that have adopted inode-like concepts.

Module Complete: Unix inode Structure

Congratulations! You've mastered the Unix inode structure—one of the most influential designs in operating systems history. You understand how a small, fixed-size data structure can address files from bytes to terabytes, maintain rich metadata, and enable features like hard links and sparse files. This knowledge will serve you well in system administration, debugging, and understanding how storage systems work at their core.

5 / 5

Loading learning content...

Operating SystemsFile System Structures

Unix inode Structure

LevelIntermediate

Duration75 mins

TopicFile System Structures

5 / 5

Double/Triple Indirect

Scaling to Terabytes: Recursive Indirection

How does a small, fixed-size inode address files of essentially unlimited size?

This is the final piece of the classic Unix block addressing scheme—and understanding it reveals both the elegance and the limitations that led to modern alternatives like extents.

What You Will Learn

Double Indirect Blocks

The hierarchy:

Inode block[13]
    ↓
Double Indirect Block (1024 pointers)
    ↓ ↓ ↓ ... ↓
1024 Single Indirect Blocks (each with 1024 pointers)
    ↓ ↓ ↓ ... ↓
1,048,576 Data Blocks

Capacity calculation (4KB blocks, 4-byte pointers):

Pointers per block (k) = 4096 / 4 = 1024

Double Indirect Capacity = k × k × block_size
                        = 1024 × 1024 × 4096
                        = 4,294,967,296 bytes
                        = 4 GB

A single double indirect pointer provides access to 4GB of file data—a thousand times more than single indirect.

Converting Mermaid diagram...

Accessing data through double indirect:

To read byte 100,000,000 (approximately 95.4 MB):

1. Calculate logical block:
   100,000,000 / 4096 = 24,414 (with remainder)

2. Determine addressing level:
   - Direct: blocks 0-11 (12 blocks)
   - Single indirect: blocks 12 - (12 + 1024 - 1) = 12-1035 (1024 blocks)
   - Double indirect: starts at block 1036
   
   24,414 > 1035, so we need double indirect

3. Calculate offset within double indirect:
   Offset = 24,414 - 12 - 1024 = 23,378

4. Navigate the tree:
   - First-level index: 23,378 / 1024 = 22 (which single indirect block)
   - Second-level index: 23,378 % 1024 = 850 (which entry in that single indirect)

5. I/O sequence:
   a. Read inode→block[13] → get double indirect block #
   b. Read double indirect block, get entry[22] → single indirect block #
   c. Read single indirect block, get entry[850] → data block #
   d. Read data block at calculated offset

Total I/O: 4 reads (inode + double + single + data)

Triple Indirect Blocks

The 15th and final pointer (index 14) is the triple indirect pointer. It adds another level of indirection, pointing to a block of double indirect pointers.

Capacity calculation (4KB blocks, 4-byte pointers):

Triple Indirect Capacity = k × k × k × block_size
                        = 1024 × 1024 × 1024 × 4096
                        = 4,398,046,511,104 bytes
                        = 4 TB

The triple indirect pointer alone can address 4 terabytes of file data.

Complete Unix File Addressing Capacity (4KB blocks, 4-byte pointers)
Level	Pointer Count	Capacity	Cumulative Max Size	I/O Depth
Direct	12	48 KB	48 KB	1
Single Indirect	1	4 MB	~4.05 MB	2
Double Indirect	1	4 GB	~4.004 GB	3
Triple Indirect	1	4 TB	~4.004 TB	4
Total Theoretical	15	—	~4 TB	4 max

Why no quadruple indirect?

With triple indirect providing 4TB capacity using 32-bit block pointers, the design already exceeds what most systems need. The reasons for stopping at three levels:

Sufficient capacity: 4TB addressed virtually any file in the ext2/ext3 era
I/O depth limit: 4 reads per access is already significant
Inode size budget: 15 pointers fit the target inode size
Diminishing returns: Each level adds I/O cost for rarely-accessed regions

Modern 64-bit filesystems with larger block pointers and extents address far larger files without needing more indirection levels.

The 4TB Limit's Historical Context

Complete Address Space Mapping

Let's formalize the complete mapping from logical byte offset to block pointer path. This algorithm is at the heart of every Unix filesystem implementation:

block_address_resolution.c
C
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
/**
 * Resolve a logical file offset to a physical block number
 * This is the complete block addressing algorithm
 */
#define DIRECT_BLOCKS 12
#define BLOCK_SIZE 4096
#define PTRS_PER_BLOCK (BLOCK_SIZE / sizeof(u32))  // 1024
 
typedef struct {
    int level;          // 0=direct, 1=single, 2=double, 3=triple
    u32 offsets[4];     // indices at each level (max 4 levels)
} BlockPath;
 
BlockPath calculate_block_path(off_t byte_offset) {
    BlockPath path = {0};
    u64 logical_block = byte_offset / BLOCK_SIZE;
    
    // Capacity at each level
    const u64 direct_max = DIRECT_BLOCKS;                              // 12
    const u64 single_max = PTRS_PER_BLOCK;                             // 1024
    const u64 double_max = PTRS_PER_BLOCK * PTRS_PER_BLOCK;            // 1M
    const u64 triple_max = PTRS_PER_BLOCK * PTRS_PER_BLOCK * PTRS_PER_BLOCK; // 1G
    
    if (logical_block < direct_max) {
        // Direct block: block[logical_block]
        path.level = 0;
        path.offsets[0] = logical_block;
        return path;
    }
    logical_block -= direct_max;
    
    if (logical_block < single_max) {
        // Single indirect: block[12] -> indirect[logical_block]
        path.level = 1;
        path.offsets[0] = 12;  // inode->block[12]
        path.offsets[1] = logical_block;
        return path;
    }
    logical_block -= single_max;
    
    if (logical_block < double_max) {
        // Double indirect: block[13] -> double[i] -> single[j] -> data
        path.level = 2;
        path.offsets[0] = 13;
        path.offsets[1] = logical_block / PTRS_PER_BLOCK;
        path.offsets[2] = logical_block % PTRS_PER_BLOCK;
        return path;
    }
    logical_block -= double_max;
    
    if (logical_block < triple_max) {
        // Triple indirect: block[14] -> triple[i] -> double[j] -> single[k] -> data
        path.level = 3;
        path.offsets[0] = 14;
        path.offsets[1] = logical_block / (PTRS_PER_BLOCK * PTRS_PER_BLOCK);
        u64 remainder = logical_block % (PTRS_PER_BLOCK * PTRS_PER_BLOCK);
        path.offsets[2] = remainder / PTRS_PER_BLOCK;
        path.offsets[3] = remainder % PTRS_PER_BLOCK;
        return path;
    }
    
    // Beyond triple indirect - file too large for this addressing scheme
    path.level = -1;
    return path;
}
 
// Example usage:
// Byte 100,000,000 -> logical block 24,414
// Path: level=2, offsets=[13, 22, 850]
// Meaning: inode->block[13] -> double_indirect[22] -> single_indirect[850] -> data

Visual representation of the address space:

Logical Block Range          Addressing Level         I/O Reads
────────────────────────────────────────────────────────────────
0 - 11                       Direct                   1
12 - 1,035                   Single Indirect          2
1,036 - 1,049,611            Double Indirect          3
1,049,612 - 1,074,791,435    Triple Indirect          4
────────────────────────────────────────────────────────────────

Byte Range (4KB blocks)
────────────────────────────────────────────────────────────────
0 - 49,151                   Direct                   48 KB
49,152 - 4,243,455           Single Indirect          ~4 MB
4,243,456 - 4,299,161,599    Double Indirect          ~4 GB
4,299,161,600 - 4,402,345,713,663  Triple Indirect    ~4 TB

I/O Cost Analysis: The Price of Depth

Each level of indirection adds one disk read (unless cached). Let's analyze the impact:

I/O Operations by Indirection Level
Access Type	Direct	Single Ind.	Double Ind.	Triple Ind.
Cold read (nothing cached)	2	3	4	5
Warm read (inode cached)	1	2	3	4
Hot read (all indirect cached)	1	1	1	1
Sequential scan (amortized)	~1	~1	~1.001	~1.001

Random access worst case:

Accessing triple indirect with cold cache:

HDD (10ms seek per read):
5 reads × 10ms = 50ms latency

SSD (100μs random read):
5 reads × 100μs = 500μs latency

NVMe (20μs random read):
5 reads × 20μs = 100μs latency

This is why random access to large files on HDDs was historically painful—multiple seeks compound.

Sequential access amortization:

Reading 1GB sequentially:

Blocks read: 262,144
Indirect blocks touched:
- 1 single indirect
- 1 double indirect  
- 256 single indirects (in double)

Total reads: 262,144 + 258
Overhead: 258/262,144 = 0.1%

Sequential I/O amortizes indirect block reads across many data blocks.

Cache effectiveness by level:

┌────────────────────────────────────────────────────────────────────┐
│  Indirect Block Caching Effectiveness                              │
├────────────────────────────────────────────────────────────────────┤
│                                                                    │
│  Single Indirect (1 block):                                        │
│  - Covers 4MB of file data                                         │
│  - 4KB cache entry serves 1024 data block accesses                 │
│  - Extremely cache-friendly                                        │
│                                                                    │
│  Double Indirect (1 + 1024 blocks):                                │
│  - Top level covers entire 4GB range                               │
│  - Each second-level block covers 4MB                              │
│  - Locality determines cache effectiveness                         │
│  - Random access across 4GB may thrash cache                       │
│                                                                    │
│  Triple Indirect (1 + 1024 + 1M blocks):                           │
│  - Top level covers entire 4TB range                               │
│  - Lower levels depend heavily on access pattern                   │
│  - Random access across 4TB definitely thrashes cache              │
│  - Sequential access still caches well due to locality             │
│                                                                    │
└────────────────────────────────────────────────────────────────────┘

Triple Indirect: Rarely Worth It

Space Overhead of Deep Indirection

Indirect blocks consume disk space. Let's calculate the overhead for files of various sizes:

Indirect Block Space Overhead
File Size	Data Blocks	Indirect Blocks	Overhead	Notes
48 KB	12	0	0%	Direct only
4 MB	1,024	1	0.098%	1 single indirect
100 MB	25,600	26	0.10%	1 single + 1 double + 24 single
1 GB	262,144	258	0.098%	1+1+256 = 258 indirect blocks
4 GB	1,048,576	1,026	0.098%	1+1+1024 = 1,026 indirect
100 GB	26,214,400	25,857	0.099%	Deep into triple indirect
1 TB	268,435,456	262,657	0.098%	~1GB of indirect blocks

Key observation: The overhead is remarkably consistent at approximately 0.1% regardless of file size. This is because each level of indirection has the same fanout ratio:

Data blocks per indirect block level:
- Single: 1024 data blocks per 1 indirect block
- Double: 1024² data blocks per (1 + 1024) indirect blocks
- Triple: 1024³ data blocks per (1 + 1024 + 1024²) indirect blocks

As n → ∞:
Overhead ratio = 1/1023 ≈ 0.098%

Comparison with other schemes:

Metadata Overhead Comparison
Scheme	Overhead for 1GB File	Overhead for 4TB File	Random Access
Unix indirect	~0.1%	~0.1%	O(log₁₀₂₄ n) = O(1)
FAT linked list	~0.1%	~0.1%	O(n)
Extent list	~0.001% (typical)	~0.001%	O(log n)
B-tree extents	~0.01%	~0.01%	O(log n)

Fragmentation Matters More

Implementation Details and Edge Cases

Implementing multi-level indirect blocks involves several subtle considerations:

Implementation Considerations

•Lazy allocation at every level — Indirect blocks are allocated only when the file grows into their range. A 1GB sparse file with data only at the end might need just a few indirect blocks.
•Zero-initialization is mandatory — New indirect blocks must be zeroed. Any garbage data would be interpreted as block pointers, causing corruption.
•Truncation must be bottom-up — When shrinking a file, first free data blocks, then their pointing indirect blocks. Otherwise, you'd lose the pointers needed to find data blocks.
•Hole handling at every level — A zero pointer in any indirect block indicates a hole. Walking the tree must check for zeros at each level.
•Transaction atomicity — Growing a file may require allocating multiple indirect blocks. All must be committed atomically via journaling.

truncate_indirect.c
C
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
/**
 * Truncate file: Free blocks from double indirect level
 * Demonstrates the complexity of multi-level cleanup
 */
void truncate_double_indirect(struct inode *inode, u64 new_block_count) {
    if (inode->block[13] == 0) return;  // No double indirect
    
    u32 *double_ind = read_block(inode->block[13]);
    bool double_empty = true;
    
    for (int i = PTRS_PER_BLOCK - 1; i >= 0; i--) {
        if (double_ind[i] == 0) continue;
        
        // Calculate which blocks this single indirect covers
        u64 start = DIRECT_BLOCKS + PTRS_PER_BLOCK + (i * PTRS_PER_BLOCK);
        u64 end = start + PTRS_PER_BLOCK;
        
        if (end <= new_block_count) {
            // Entire single indirect is still in use
            double_empty = false;
            continue;
        }
        
        // Need to process this single indirect
        u32 *single_ind = read_block(double_ind[i]);
        bool single_empty = true;
        
        for (int j = PTRS_PER_BLOCK - 1; j >= 0; j--) {
            u64 block_num = start + j;
            if (block_num >= new_block_count && single_ind[j] != 0) {
                // Free this data block
                free_block(single_ind[j]);
                single_ind[j] = 0;
                mark_buffer_dirty(single_ind);
            }
            if (single_ind[j] != 0) single_empty = false;
        }
        
        if (single_empty) {
            // Free the now-empty single indirect block
            free_block(double_ind[i]);
            double_ind[i] = 0;
            mark_buffer_dirty(double_ind);
        } else {
            double_empty = false;
        }
    }
    
    if (double_empty) {
        // Free the double indirect block itself
        free_block(inode->block[13]);
        inode->block[13] = 0;
    }
}

Truncation is Expensive

Modern Alternative: Extent-Based Addressing

The indirect block scheme, while elegant, has limitations that led to the development of extent-based addressing in modern filesystems:

Problems with indirect blocks:

One pointer per block — A contiguous 1GB region requires 262,144 pointers, one for each 4KB block
Fragmentation amplifies overhead — Many small extents = many indirect blocks
Fixed maximum depth — Triple indirect limits size (works around with 64-bit pointers)
Metadata not colocated — Indirect blocks may be scattered across disk

Indirect Blocks vs. Extents
Aspect	Indirect Blocks	Extents
Contiguous 1GB file	262,144 + 258 entries	1 extent entry
Maximum file size (32-bit)	~4TB	~16TB (typical)
Random access complexity	O(1) fixed levels	O(log n) tree search
Fragmentation handling	Works but verbose	Needs more extents
Space efficiency	~0.1% overhead always	Near-zero for contiguous
Implementation complexity	Simple arithmetic	B-tree or similar

Ext4's extent structure:

struct ext4_extent {
    __le32 ee_block;      // First logical block covered
    __le16 ee_len;        // Number of blocks (up to 32768)
    __le16 ee_start_hi;   // Physical start block (high bits)
    __le32 ee_start_lo;   // Physical start block (low bits)
};
// 12 bytes per extent

// A single extent can describe:
// - Up to 128MB of contiguous data (32768 × 4KB)
// - In 12 bytes, vs 32KB of indirect pointers for same range

Key insight: Extents map ranges, not individual blocks. A well-defragmented file might be described by a single extent, regardless of size.

Ext4's Hybrid Approach

When Indirect Blocks Still Make Sense

Despite the advantages of extents, indirect blocks remain relevant in specific scenarios:

Scenarios Favoring Indirect Blocks

•Highly fragmented files — A file with thousands of single-block extents might use MORE space with extent metadata than indirect blocks.
•Small files — For files under 48KB, direct blocks in the inode are unbeatable. No separate extent tree needed.
•Sparse files with scattered holes — Indirect blocks naturally handle sparse regions with zero pointers at any level.
•Legacy compatibility — Older tools and recovery software often understand indirect blocks but not modern extent formats.
•Simplicity — For embedded systems or simple filesystem implementations, indirect blocks are easier to implement correctly.
•Predictable overhead — The ~0.1% overhead is consistent; extent overhead varies with fragmentation.

Best for indirect blocks:

Small filesystems
Many small files
Heavy fragmentation expected
Simple implementation needed
Legacy compatibility required
Embedded systems

Example: /tmp with many small temporary files

Best for extents:

Large sequential files
Database files
Media files
Virtual machine images
Well-defragmented storage
Modern hardware

Example: Database server with multi-GB data files

Know Your Workload

Summary: The Complete Block Addressing Picture

We've completed our journey through Unix inode block addressing, from the simplest direct pointers to the depths of triple indirection. Let's consolidate everything:

Complete Block Addressing Summary (4KB blocks, 4-byte pointers)
Component	Capacity	I/O Depth	Use Case
12 Direct	48 KB	1	Most files (configs, source code)
1 Single Indirect	4 MB	2	Medium files (documents, small images)
1 Double Indirect	4 GB	3	Large files (videos, databases)
1 Triple Indirect	4 TB	4	Huge files (VM images, archives)
Combined	~4 TB	1-4	Any Unix file

Key Takeaways

•Recursive indirection scales exponentially — Each level multiplies capacity by the pointers-per-block factor (typically 1024).
•I/O cost increases linearly with depth — But caching makes this cost nearly invisible for common access patterns.
•Space overhead is consistently minimal — Approximately 0.1% regardless of file size.
•The design optimizes for common cases — Small files use direct blocks; larger files pay progressive indirection costs.
•Modern extents build on these principles — They trade per-block addressing for range-based addressing, improving contiguous file handling.
•Understanding this scheme is still essential — Even with extents, the principles of hierarchical addressing, caching, and space/time tradeoffs apply universally.

Module Complete:

This knowledge forms the foundation for understanding modern filesystems like ext4, XFS, Btrfs, and even non-Unix systems that have adopted inode-like concepts.

Module Complete: Unix inode Structure

5 / 5