Operating SystemsIndexed Allocation

Indexed Allocation

LevelIntermediate

Duration60 mins

TopicIndexed Allocation

4 / 5

Index Block Overhead

The Cost of Flexibility

Every engineering choice involves tradeoffs. Indexed allocation provides O(1) random access and eliminates external fragmentation—but these benefits come at a cost: space overhead.

Every file, regardless of size, requires metadata to track its blocks. A file containing a single byte of data still needs an entire index block (or inode) to describe it. For file systems storing millions of small files—configuration files, cache entries, source code—this overhead can become significant.

In this page, we'll rigorously quantify index block overhead, identify when it matters most, and examine the sophisticated techniques modern file systems use to minimize wasted space while preserving indexed allocation's essential capabilities.

What You Will Learn

By the end of this page, you will be able to calculate exact overhead percentages for different file sizes, understand why small files are disproportionately affected, evaluate techniques like inline data and extent-based allocation that reduce overhead, and make informed decisions about file system parameters.

Defining Index Block Overhead

Index block overhead is the disk space consumed by file system metadata relative to actual file data. In indexed allocation, this primarily includes:

The Inode Itself — The structure containing file attributes and block pointers
Indirect Blocks — Additional blocks needed to address large files
Internal Fragmentation — Unused space in the last data block of a file

Formal Definition:

Overhead Formula

Overhead Percentage = (Metadata Space / Total Space Used) × 100%

Metadata Space = Inode Size + (Number of Indirect Blocks × Block Size)

Total Space Used = Metadata Space + Data Blocks Used

Overhead Components by File Size
File Size	Inode (256B)	Indirect Blocks	Data Blocks	Total Metadata	Overhead %
1 byte	256 B	0	4 KB	256 B	5.9%
1 KB	256 B	0	4 KB	256 B	5.9%
4 KB	256 B	0	4 KB	256 B	5.9%
48 KB	256 B	0	48 KB	256 B	0.5%
100 KB	256 B	4 KB	100 KB	~4.3 KB	4.1%
1 MB	256 B	4 KB	1 MB	~4.3 KB	0.4%
100 MB	256 B	~400 KB	100 MB	~400 KB	0.4%
1 GB	256 B	~4 MB	1 GB	~4 MB	0.4%

Key Observation:

Overhead percentage is highest for tiny files and decreases as files grow. A 1-byte file has ~6% overhead, while a 1GB file has ~0.4% overhead. This is because the inode's fixed cost is amortized across more data blocks as files grow.

The Small File Problem

The most significant overhead problem occurs with small files. Consider a file system with millions of small files—a common scenario in many environments:

Source code repositories: thousands of files averaging 2-10KB
Email servers: millions of individual message files
Web servers: countless HTML, CSS, and image files
Cache directories: numerous small cached objects

The Mathematics of Small File Overhead:

small_file_analysis.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
71
72
73
/*
 * Small File Overhead Analysis
 * 
 * Calculates the actual space used for files smaller than one block.
 */
 
#define BLOCK_SIZE      4096    /* 4KB blocks */
#define INODE_SIZE      256     /* Typical ext4 inode */
 
/*
 * Calculate real overhead for a small file
 */
struct overhead_analysis {
    size_t file_data_size;      /* Logical file size */
    size_t actual_disk_usage;   /* Physical space consumed */
    size_t wasted_space;        /* Space not holding user data */
    float  overhead_percent;    /* Overhead as percentage */
};
 
struct overhead_analysis analyze_small_file(size_t file_size) {
    struct overhead_analysis result;
    
    result.file_data_size = file_size;
    
    /*
     * For files < 1 block:
     * - 1 inode (256 bytes in inode table)
     * - 1 data block (4096 bytes, even for 1-byte file!)
     */
    size_t data_blocks = (file_size + BLOCK_SIZE - 1) / BLOCK_SIZE;
    if (data_blocks == 0) data_blocks = 1;  /* At least one for non-empty files */
    
    result.actual_disk_usage = INODE_SIZE + (data_blocks * BLOCK_SIZE);
    result.wasted_space = result.actual_disk_usage - file_size;
    result.overhead_percent = 
        (float)result.wasted_space / result.actual_disk_usage * 100.0f;
    
    return result;
}
 
/*
 * Examples:
 * 
 * File: 1 byte
 *   Disk usage: 256 + 4096 = 4352 bytes
 *   Wasted: 4351 bytes (99.98% overhead!)
 * 
 * File: 100 bytes
 *   Disk usage: 4352 bytes
 *   Wasted: 4252 bytes (97.7% overhead)
 * 
 * File: 1000 bytes (1KB)
 *   Disk usage: 4352 bytes
 *   Wasted: 3352 bytes (77.0% overhead)
 * 
 * File: 4000 bytes (~4KB)
 *   Disk usage: 4352 bytes
 *   Wasted: 352 bytes (8.1% overhead)
 * 
 * File: 4096 bytes (exactly 1 block)
 *   Disk usage: 4352 bytes
 *   Wasted: 256 bytes (5.9% overhead - just inode)
 */
 
/*
 * Real-world scenario: 1 million small files averaging 500 bytes
 * 
 * Logical data: 1,000,000 × 500 = 500 MB
 * Actual usage: 1,000,000 × 4,352 = 4.15 GB
 * 
 * Efficiency: only 12% of disk space holds actual data!
 * This is why small file optimization matters so much.
 */

The 4KB Minimum

With 4KB blocks, every file—even one containing a single byte—consumes at least 4KB of data space plus inode space. This internal fragmentation is unavoidable in block-based file systems and dominates overhead for small files.

Indirect Block Overhead

For larger files, the overhead picture shifts from internal fragmentation to indirect block consumption. Each level of indirection requires additional blocks that exist solely to hold pointers.

Indirect Block Consumption by File Size:

Indirect Block Requirements (4KB blocks, 8-byte pointers)
File Size Range	Addressing Method	Indirect Blocks Needed	Indirect Block Overhead
0 - 48 KB	Direct only	0	0 bytes
48 KB - 2 MB	Single indirect	1	4 KB (0.2-8.3%)
2 MB - 1 GB	Double indirect	2 - 513	8 KB - 2 MB (0.0002-0.1%)
1 GB - 512 GB	Triple indirect	514 - 262,657	2 MB - 1 GB (0.0002-0.2%)

indirect_overhead_calc.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
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
/*
 * Calculate Indirect Block Overhead for Large Files
 * 
 * This computes exactly how many indirect blocks are needed
 * and the resulting overhead percentage.
 */
 
#define BLOCK_SIZE          4096
#define POINTER_SIZE        8
#define PTRS_PER_BLOCK      (BLOCK_SIZE / POINTER_SIZE)  /* 512 */
#define DIRECT_BLOCKS       12
 
struct large_file_overhead {
    uint64_t file_size;
    uint64_t data_blocks;
    uint64_t single_indirect_blocks;
    uint64_t double_indirect_blocks;  /* Level 1 + Level 2 */
    uint64_t triple_indirect_blocks;  /* All 3 levels */
    uint64_t total_indirect_blocks;
    uint64_t indirect_overhead_bytes;
    float    overhead_percent;
};
 
struct large_file_overhead calculate_indirect_overhead(uint64_t file_size) {
    struct large_file_overhead result = {0};
    result.file_size = file_size;
    
    uint64_t total_blocks = (file_size + BLOCK_SIZE - 1) / BLOCK_SIZE;
    result.data_blocks = total_blocks;
    
    if (total_blocks <= DIRECT_BLOCKS) {
        /* No indirect blocks needed */
        result.overhead_percent = 0;
        return result;
    }
    
    uint64_t remaining = total_blocks - DIRECT_BLOCKS;
    
    /* Single indirect level */
    if (remaining > 0) {
        result.single_indirect_blocks = 1;  /* One block for up to 512 pointers */
        remaining = (remaining > PTRS_PER_BLOCK) ? 
                    remaining - PTRS_PER_BLOCK : 0;
    }
    
    /* Double indirect level */
    if (remaining > 0) {
        uint64_t double_data_blocks = MIN(remaining, 
                                          PTRS_PER_BLOCK * PTRS_PER_BLOCK);
        uint64_t level2_blocks = (double_data_blocks + PTRS_PER_BLOCK - 1) 
                                 / PTRS_PER_BLOCK;
        result.double_indirect_blocks = 1 + level2_blocks;  /* 1 L1 + n L2 */
        remaining = (remaining > PTRS_PER_BLOCK * PTRS_PER_BLOCK) ?
                    remaining - PTRS_PER_BLOCK * PTRS_PER_BLOCK : 0;
    }
    
    /* Triple indirect level */
    if (remaining > 0) {
        /* Complex calculation for 3-level tree */
        uint64_t l3_blocks = (remaining + PTRS_PER_BLOCK - 1) / PTRS_PER_BLOCK;
        uint64_t l2_blocks = (l3_blocks + PTRS_PER_BLOCK - 1) / PTRS_PER_BLOCK;
        result.triple_indirect_blocks = 1 + l2_blocks + l3_blocks;
    }
    
    result.total_indirect_blocks = result.single_indirect_blocks +
                                   result.double_indirect_blocks +
                                   result.triple_indirect_blocks;
    
    result.indirect_overhead_bytes = result.total_indirect_blocks * BLOCK_SIZE;
    
    uint64_t total_disk = (result.data_blocks + result.total_indirect_blocks) 
                          * BLOCK_SIZE;
    result.overhead_percent = (float)result.indirect_overhead_bytes / total_disk 
                              * 100.0f;
    
    return result;
}
 
/*
 * Example results:
 * 
 * 100 MB file:
 *   Data blocks: 25,600
 *   Indirect blocks: 1 (single) + 51 (double) = 52
 *   Overhead: 52 × 4KB = 208 KB (0.2%)
 * 
 * 10 GB file:
 *   Data blocks: 2,621,440
 *   Indirect blocks: Complex tree structure
 *   Overhead: ~20 MB (0.2%)
 * 
 * 100 GB file:
 *   Indirect overhead: ~200 MB (0.2%)
 * 
 * Observation: Indirect overhead stabilizes around 0.2% for large files!
 */

Inode Table Overhead

Beyond per-file overhead, traditional Unix file systems pre-allocate a fixed pool of inodes at file system creation time. This introduces a system-wide overhead that exists regardless of how many files are actually stored.

Inode Table Sizing:

When you create an ext4 file system, the mkfs command reserves space for a predetermined number of inodes. The default is typically one inode per 16KB of disk space, though this is configurable.

The Tradeoff:

Too few inodes: You can run out of inodes while having plenty of disk space ("No space left on device" with gigabytes free)
Too many inodes: Wasted space in the inode table that will never be used

Inode Table Sizing Examples
Disk Size	Default Inodes	Inode Table Size	% of Disk
100 GB	6,553,600	1.56 GB	1.56%
500 GB	32,768,000	7.81 GB	1.56%
1 TB	65,536,000	15.63 GB	1.52%
10 TB	655,360,000	156.25 GB	1.52%

Dynamic Inode Allocation

Some modern file systems (like XFS, Btrfs, and ext4 with certain options) can dynamically allocate inodes, eliminating the fixed inode table overhead. The inode structures are created on-demand within the normal block space.

inode_table_config.sh
Shell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Viewing inode allocation on an ext4 file system
$ df -i /dev/sda1
Filesystem      Inodes   IUsed   IFree IUse% Mounted on
/dev/sda1     65536000  847293 64688707    2% /home
 
# The file system was created with 65.5 million inode slots
# Only ~850K (1.3%) are actually used
# The rest represent "wasted" pre-allocated space
 
# Creating a file system with custom inode ratio
$ mkfs.ext4 -i 4096 /dev/sdb1   # 1 inode per 4KB (many small files)
$ mkfs.ext4 -i 65536 /dev/sdc1  # 1 inode per 64KB (few large files)
 
# Checking inode size
$ tune2fs -l /dev/sda1 | grep "Inode size"
Inode size:               256
 
# Total inode table size calculation:
# 65,536,000 inodes × 256 bytes = 16.78 GB

Minimizing Overhead: Inline Data

The most dramatic overhead reduction for small files comes from inline data (also called embedded data or resident data). Instead of allocating a separate data block for tiny files, the file's data is stored directly within the inode structure itself.

How Inline Data Works:

A standard inode contains space for block pointers (direct, indirect, etc.). For a 256-byte inode, this pointer space is typically 60-100 bytes. For very small files, we can repurpose this space to hold actual data instead of pointers.

Inline Data Benefits

•Zero data block overhead — Files under threshold use only inode space
•Faster access — Data is already loaded when inode is read
•Reduced fragmentation — Fewer tiny data blocks scattered on disk
•Cache efficiency — Inode cache also holds data

inline_data.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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/*
 * Inline Data Implementation
 * 
 * Small files store data directly in the inode's pointer space.
 */
 
#define INODE_SIZE          256
#define INODE_METADATA_SIZE 56      /* Mode, uid, timestamps, etc. */
#define INLINE_DATA_SPACE   (INODE_SIZE - INODE_METADATA_SIZE)  /* ~200 bytes */
 
/*
 * Inode with inline data support (ext4-style)
 */
struct inode_inline {
    /* Standard metadata */
    uint32_t    mode;           /* File type and permissions */
    uint32_t    uid;            /* Owner */
    uint32_t    gid;            /* Group */
    uint64_t    size;           /* File size */
    uint32_t    atime;          /* Access time */
    uint32_t    mtime;          /* Modification time */
    uint32_t    ctime;          /* Change time */
    uint32_t    links;          /* Hard link count */
    uint32_t    flags;          /* Extended flags */
    /* ... other metadata ... */
    
    /*
     * Union: either block pointers OR inline data
     * The EXT4_INLINE_DATA flag in 'flags' indicates which.
     */
    union {
        struct {
            block_ptr_t direct[12];
            block_ptr_t indirect;
            block_ptr_t double_indirect;
            block_ptr_t triple_indirect;
        } blocks;
        
        char inline_data[200];  /* Data stored directly in inode! */
    };
};
 
/*
 * Reading inline data
 */
ssize_t read_inline_file(struct inode_inline *inode, 
                         off_t offset, 
                         void *buf, 
                         size_t count) {
    if (offset >= inode->size) {
        return 0;  /* EOF */
    }
    
    size_t available = inode->size - offset;
    size_t to_read = MIN(count, available);
    
    if (inode->flags & EXT4_INLINE_DATA) {
        /* Data is right here in the inode! */
        memcpy(buf, inode->inline_data + offset, to_read);
        return to_read;
        /* No disk I/O for data - it was loaded with the inode */
    }
    
    /* Fall back to normal block-based read */
    return read_via_blocks(inode, offset, buf, count);
}
 
/*
 * Space savings example:
 * 
 * WITHOUT inline data (100-byte file):
 *   Inode: 256 bytes
 *   Data block: 4096 bytes
 *   Total: 4352 bytes (3.5% efficient)
 * 
 * WITH inline data (100-byte file):
 *   Inode: 256 bytes (100 bytes is data)
 *   Data block: 0 bytes
 *   Total: 256 bytes (39% efficient - 17x improvement!)
 * 
 * For a directory with 1 million tiny files:
 *   Without inline: 4.15 GB disk usage
 *   With inline: 244 MB disk usage (17x savings!)
 */

File Systems with Inline Data Support
File System	Inline Data Support	Maximum Inline Size
ext4	Yes (with feature flag)	~60 bytes (or more with large inodes)
Btrfs	Yes	Up to ~2KB
XFS	No (but uses extents efficiently)	N/A
NTFS	Yes (resident attributes)	~700 bytes per MFT record
ZFS	Yes (metadata blocks)	Variable

Minimizing Overhead: Extent-Based Allocation

Traditional block pointers waste space when files are stored contiguously. If blocks 1000-2000 hold a file, we need 1001 individual pointers—even though a single (start, length) pair would suffice.

Extent-Based Allocation:

An extent is a contiguous run of blocks described by a tuple: (logical_start, physical_start, length). This dramatically reduces pointer overhead for files that are laid out sequentially on disk.

Converting Mermaid diagram...

extent_structure.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
/*
 * Extent-Based Allocation (ext4-style)
 * 
 * Extents replace individual block pointers with (start, length) tuples.
 */
 
/*
 * ext4 extent structure (12 bytes)
 */
struct ext4_extent {
    uint32_t    ee_block;       /* First logical block */
    uint16_t    ee_len;         /* Number of blocks */
    uint16_t    ee_start_hi;    /* High 16 bits of physical block */
    uint32_t    ee_start_lo;    /* Low 32 bits of physical block */
};
 
/*
 * Ext4 inode can hold 4 extents directly
 * For more, an extent tree is used (similar to indirect blocks)
 */
#define EXT4_EXTENTS_PER_INODE  4
 
struct ext4_extent_header {
    uint16_t    eh_magic;       /* Magic number: 0xF30A */
    uint16_t    eh_entries;     /* Number of valid entries */
    uint16_t    eh_max;         /* Maximum entries possible */
    uint16_t    eh_depth;       /* Tree depth (0 = leaf) */
    uint32_t    eh_generation;  /* Generation for checksums */
};
 
/*
 * Space comparison: 1GB contiguous file
 * 
 * Block pointers (4KB blocks, 8-byte pointers):
 *   Blocks needed: 262,144
 *   Pointers: 12 direct + 512 indirect + 261,620 via double indirect
 *   Indirect blocks: 1 + 511 = 512 blocks = 2 MB overhead
 * 
 * Extent-based (if contiguous):
 *   Extents needed: 1
 *   Extent size: 12 bytes
 *   Overhead: 12 bytes (0.0000012%)
 * 
 * That's a 174,000× reduction in metadata overhead!
 */
 
/*
 * Reading with extents
 */
block_ptr_t extent_lookup(struct ext4_extent *extents, 
                          int num_extents,
                          uint64_t logical_block) {
    for (int i = 0; i < num_extents; i++) {
        uint64_t start = extents[i].ee_block;
        uint64_t end = start + extents[i].ee_len;
        
        if (logical_block >= start && logical_block < end) {
            /* Found the extent containing this block */
            uint64_t offset = logical_block - start;
            uint64_t physical = ((uint64_t)extents[i].ee_start_hi << 32) |
                                extents[i].ee_start_lo;
            return physical + offset;
        }
    }
    
    return 0;  /* Block not found (hole) */
}

When Extents Don't Help

Extents are most beneficial for sequentially-written files. For highly fragmented files (many small writes scattered across the disk), extent overhead can approach or exceed block pointer overhead as multiple small extents are needed to describe the fragmented layout.

Block Size Tradeoffs

The block size is a fundamental file system parameter that directly impacts overhead. Larger blocks reduce pointer overhead but increase internal fragmentation for small files. Smaller blocks do the opposite.

Larger Blocks (8KB-64KB)

•Fewer pointers needed for large files
•Better sequential read performance
•Fewer disk I/O operations
•Higher internal fragmentation
•More wasted space for small files
•Best for: Media files, databases

Smaller Blocks (1KB-4KB)

•Less internal fragmentation
•Better space efficiency for small files
•More pointers needed (more overhead)
•More disk I/O for large files
•Lower sequential throughput
•Best for: Source code, configs

Block Size Impact on 500-byte Files (1 million files)
Block Size	Space per File	Total Disk Usage	Space Efficiency
512 bytes	768 B (+ inode)	732 MB	68%
1 KB	1.25 KB	1.19 GB	42%
4 KB	4.25 KB	4.05 GB	12%
8 KB	8.25 KB	7.86 GB	6%
64 KB	64.25 KB	61.2 GB	0.8%

Choosing Block Size

Most general-purpose systems use 4KB blocks as a balance. Specialized systems may use smaller blocks (mail servers with millions of tiny files) or larger blocks (video storage). The default is almost never changed in practice.

Summary: Managing the Overhead Tax

Index block overhead is the price we pay for the flexibility of indexed allocation. Understanding this overhead enables informed decisions about file system configuration and design.

Key Takeaways

•Small files suffer most — A 1-byte file can use 4KB+ of disk space due to minimum block allocation.
•Large files are efficient — Overhead percentages decrease as file sizes increase, stabilizing around 0.2-0.5%.
•Inode tables are pre-allocated — Traditional file systems reserve fixed inode space, wasting capacity if unused.
•Inline data helps small files — Storing tiny files in the inode itself eliminates data block overhead entirely.
•Extents reduce pointer overhead — Contiguous files described by (start, length) tuples use far less metadata.
•Block size is a tradeoff — Larger blocks reduce pointers but increase internal fragmentation.

What's Next:

We've seen how indexed allocation handles the extreme ends—tiny files and massive files—but left a gap in the middle. How do we efficiently address files larger than direct pointers can handle, but without the full complexity of triple indirect blocks? In the final page of this module, we'll explore multi-level indexing schemes that elegantly scale from kilobytes to terabytes through hierarchical pointer structures.

Page Complete

You now understand the space overhead costs of indexed allocation and the techniques used to minimize them. This knowledge is essential for capacity planning, file system selection, and understanding why different file systems perform differently for various workloads.

4 / 5

Loading learning content...

Operating SystemsIndexed Allocation

Indexed Allocation

LevelIntermediate

Duration60 mins

TopicIndexed Allocation

4 / 5

Index Block Overhead

The Cost of Flexibility

Every engineering choice involves tradeoffs. Indexed allocation provides O(1) random access and eliminates external fragmentation—but these benefits come at a cost: space overhead.

What You Will Learn

Defining Index Block Overhead

Index block overhead is the disk space consumed by file system metadata relative to actual file data. In indexed allocation, this primarily includes:

The Inode Itself — The structure containing file attributes and block pointers
Indirect Blocks — Additional blocks needed to address large files
Internal Fragmentation — Unused space in the last data block of a file

Formal Definition:

Overhead Formula

Overhead Percentage = (Metadata Space / Total Space Used) × 100%

Metadata Space = Inode Size + (Number of Indirect Blocks × Block Size)

Total Space Used = Metadata Space + Data Blocks Used

Overhead Components by File Size
File Size	Inode (256B)	Indirect Blocks	Data Blocks	Total Metadata	Overhead %
1 byte	256 B	0	4 KB	256 B	5.9%
1 KB	256 B	0	4 KB	256 B	5.9%
4 KB	256 B	0	4 KB	256 B	5.9%
48 KB	256 B	0	48 KB	256 B	0.5%
100 KB	256 B	4 KB	100 KB	~4.3 KB	4.1%
1 MB	256 B	4 KB	1 MB	~4.3 KB	0.4%
100 MB	256 B	~400 KB	100 MB	~400 KB	0.4%
1 GB	256 B	~4 MB	1 GB	~4 MB	0.4%

Key Observation:

The Small File Problem

The most significant overhead problem occurs with small files. Consider a file system with millions of small files—a common scenario in many environments:

Source code repositories: thousands of files averaging 2-10KB
Email servers: millions of individual message files
Web servers: countless HTML, CSS, and image files
Cache directories: numerous small cached objects

The Mathematics of Small File Overhead:

small_file_analysis.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
71
72
73
/*
 * Small File Overhead Analysis
 * 
 * Calculates the actual space used for files smaller than one block.
 */
 
#define BLOCK_SIZE      4096    /* 4KB blocks */
#define INODE_SIZE      256     /* Typical ext4 inode */
 
/*
 * Calculate real overhead for a small file
 */
struct overhead_analysis {
    size_t file_data_size;      /* Logical file size */
    size_t actual_disk_usage;   /* Physical space consumed */
    size_t wasted_space;        /* Space not holding user data */
    float  overhead_percent;    /* Overhead as percentage */
};
 
struct overhead_analysis analyze_small_file(size_t file_size) {
    struct overhead_analysis result;
    
    result.file_data_size = file_size;
    
    /*
     * For files < 1 block:
     * - 1 inode (256 bytes in inode table)
     * - 1 data block (4096 bytes, even for 1-byte file!)
     */
    size_t data_blocks = (file_size + BLOCK_SIZE - 1) / BLOCK_SIZE;
    if (data_blocks == 0) data_blocks = 1;  /* At least one for non-empty files */
    
    result.actual_disk_usage = INODE_SIZE + (data_blocks * BLOCK_SIZE);
    result.wasted_space = result.actual_disk_usage - file_size;
    result.overhead_percent = 
        (float)result.wasted_space / result.actual_disk_usage * 100.0f;
    
    return result;
}
 
/*
 * Examples:
 * 
 * File: 1 byte
 *   Disk usage: 256 + 4096 = 4352 bytes
 *   Wasted: 4351 bytes (99.98% overhead!)
 * 
 * File: 100 bytes
 *   Disk usage: 4352 bytes
 *   Wasted: 4252 bytes (97.7% overhead)
 * 
 * File: 1000 bytes (1KB)
 *   Disk usage: 4352 bytes
 *   Wasted: 3352 bytes (77.0% overhead)
 * 
 * File: 4000 bytes (~4KB)
 *   Disk usage: 4352 bytes
 *   Wasted: 352 bytes (8.1% overhead)
 * 
 * File: 4096 bytes (exactly 1 block)
 *   Disk usage: 4352 bytes
 *   Wasted: 256 bytes (5.9% overhead - just inode)
 */
 
/*
 * Real-world scenario: 1 million small files averaging 500 bytes
 * 
 * Logical data: 1,000,000 × 500 = 500 MB
 * Actual usage: 1,000,000 × 4,352 = 4.15 GB
 * 
 * Efficiency: only 12% of disk space holds actual data!
 * This is why small file optimization matters so much.
 */

The 4KB Minimum

Indirect Block Overhead

For larger files, the overhead picture shifts from internal fragmentation to indirect block consumption. Each level of indirection requires additional blocks that exist solely to hold pointers.

Indirect Block Consumption by File Size:

Indirect Block Requirements (4KB blocks, 8-byte pointers)
File Size Range	Addressing Method	Indirect Blocks Needed	Indirect Block Overhead
0 - 48 KB	Direct only	0	0 bytes
48 KB - 2 MB	Single indirect	1	4 KB (0.2-8.3%)
2 MB - 1 GB	Double indirect	2 - 513	8 KB - 2 MB (0.0002-0.1%)
1 GB - 512 GB	Triple indirect	514 - 262,657	2 MB - 1 GB (0.0002-0.2%)

indirect_overhead_calc.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
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
/*
 * Calculate Indirect Block Overhead for Large Files
 * 
 * This computes exactly how many indirect blocks are needed
 * and the resulting overhead percentage.
 */
 
#define BLOCK_SIZE          4096
#define POINTER_SIZE        8
#define PTRS_PER_BLOCK      (BLOCK_SIZE / POINTER_SIZE)  /* 512 */
#define DIRECT_BLOCKS       12
 
struct large_file_overhead {
    uint64_t file_size;
    uint64_t data_blocks;
    uint64_t single_indirect_blocks;
    uint64_t double_indirect_blocks;  /* Level 1 + Level 2 */
    uint64_t triple_indirect_blocks;  /* All 3 levels */
    uint64_t total_indirect_blocks;
    uint64_t indirect_overhead_bytes;
    float    overhead_percent;
};
 
struct large_file_overhead calculate_indirect_overhead(uint64_t file_size) {
    struct large_file_overhead result = {0};
    result.file_size = file_size;
    
    uint64_t total_blocks = (file_size + BLOCK_SIZE - 1) / BLOCK_SIZE;
    result.data_blocks = total_blocks;
    
    if (total_blocks <= DIRECT_BLOCKS) {
        /* No indirect blocks needed */
        result.overhead_percent = 0;
        return result;
    }
    
    uint64_t remaining = total_blocks - DIRECT_BLOCKS;
    
    /* Single indirect level */
    if (remaining > 0) {
        result.single_indirect_blocks = 1;  /* One block for up to 512 pointers */
        remaining = (remaining > PTRS_PER_BLOCK) ? 
                    remaining - PTRS_PER_BLOCK : 0;
    }
    
    /* Double indirect level */
    if (remaining > 0) {
        uint64_t double_data_blocks = MIN(remaining, 
                                          PTRS_PER_BLOCK * PTRS_PER_BLOCK);
        uint64_t level2_blocks = (double_data_blocks + PTRS_PER_BLOCK - 1) 
                                 / PTRS_PER_BLOCK;
        result.double_indirect_blocks = 1 + level2_blocks;  /* 1 L1 + n L2 */
        remaining = (remaining > PTRS_PER_BLOCK * PTRS_PER_BLOCK) ?
                    remaining - PTRS_PER_BLOCK * PTRS_PER_BLOCK : 0;
    }
    
    /* Triple indirect level */
    if (remaining > 0) {
        /* Complex calculation for 3-level tree */
        uint64_t l3_blocks = (remaining + PTRS_PER_BLOCK - 1) / PTRS_PER_BLOCK;
        uint64_t l2_blocks = (l3_blocks + PTRS_PER_BLOCK - 1) / PTRS_PER_BLOCK;
        result.triple_indirect_blocks = 1 + l2_blocks + l3_blocks;
    }
    
    result.total_indirect_blocks = result.single_indirect_blocks +
                                   result.double_indirect_blocks +
                                   result.triple_indirect_blocks;
    
    result.indirect_overhead_bytes = result.total_indirect_blocks * BLOCK_SIZE;
    
    uint64_t total_disk = (result.data_blocks + result.total_indirect_blocks) 
                          * BLOCK_SIZE;
    result.overhead_percent = (float)result.indirect_overhead_bytes / total_disk 
                              * 100.0f;
    
    return result;
}
 
/*
 * Example results:
 * 
 * 100 MB file:
 *   Data blocks: 25,600
 *   Indirect blocks: 1 (single) + 51 (double) = 52
 *   Overhead: 52 × 4KB = 208 KB (0.2%)
 * 
 * 10 GB file:
 *   Data blocks: 2,621,440
 *   Indirect blocks: Complex tree structure
 *   Overhead: ~20 MB (0.2%)
 * 
 * 100 GB file:
 *   Indirect overhead: ~200 MB (0.2%)
 * 
 * Observation: Indirect overhead stabilizes around 0.2% for large files!
 */

Inode Table Overhead

Inode Table Sizing:

When you create an ext4 file system, the mkfs command reserves space for a predetermined number of inodes. The default is typically one inode per 16KB of disk space, though this is configurable.

The Tradeoff:

Too few inodes: You can run out of inodes while having plenty of disk space ("No space left on device" with gigabytes free)
Too many inodes: Wasted space in the inode table that will never be used

Inode Table Sizing Examples
Disk Size	Default Inodes	Inode Table Size	% of Disk
100 GB	6,553,600	1.56 GB	1.56%
500 GB	32,768,000	7.81 GB	1.56%
1 TB	65,536,000	15.63 GB	1.52%
10 TB	655,360,000	156.25 GB	1.52%

Dynamic Inode Allocation

inode_table_config.sh
Shell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Viewing inode allocation on an ext4 file system
$ df -i /dev/sda1
Filesystem      Inodes   IUsed   IFree IUse% Mounted on
/dev/sda1     65536000  847293 64688707    2% /home
 
# The file system was created with 65.5 million inode slots
# Only ~850K (1.3%) are actually used
# The rest represent "wasted" pre-allocated space
 
# Creating a file system with custom inode ratio
$ mkfs.ext4 -i 4096 /dev/sdb1   # 1 inode per 4KB (many small files)
$ mkfs.ext4 -i 65536 /dev/sdc1  # 1 inode per 64KB (few large files)
 
# Checking inode size
$ tune2fs -l /dev/sda1 | grep "Inode size"
Inode size:               256
 
# Total inode table size calculation:
# 65,536,000 inodes × 256 bytes = 16.78 GB

Minimizing Overhead: Inline Data

How Inline Data Works:

Inline Data Benefits

•Zero data block overhead — Files under threshold use only inode space
•Faster access — Data is already loaded when inode is read
•Reduced fragmentation — Fewer tiny data blocks scattered on disk
•Cache efficiency — Inode cache also holds data

inline_data.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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/*
 * Inline Data Implementation
 * 
 * Small files store data directly in the inode's pointer space.
 */
 
#define INODE_SIZE          256
#define INODE_METADATA_SIZE 56      /* Mode, uid, timestamps, etc. */
#define INLINE_DATA_SPACE   (INODE_SIZE - INODE_METADATA_SIZE)  /* ~200 bytes */
 
/*
 * Inode with inline data support (ext4-style)
 */
struct inode_inline {
    /* Standard metadata */
    uint32_t    mode;           /* File type and permissions */
    uint32_t    uid;            /* Owner */
    uint32_t    gid;            /* Group */
    uint64_t    size;           /* File size */
    uint32_t    atime;          /* Access time */
    uint32_t    mtime;          /* Modification time */
    uint32_t    ctime;          /* Change time */
    uint32_t    links;          /* Hard link count */
    uint32_t    flags;          /* Extended flags */
    /* ... other metadata ... */
    
    /*
     * Union: either block pointers OR inline data
     * The EXT4_INLINE_DATA flag in 'flags' indicates which.
     */
    union {
        struct {
            block_ptr_t direct[12];
            block_ptr_t indirect;
            block_ptr_t double_indirect;
            block_ptr_t triple_indirect;
        } blocks;
        
        char inline_data[200];  /* Data stored directly in inode! */
    };
};
 
/*
 * Reading inline data
 */
ssize_t read_inline_file(struct inode_inline *inode, 
                         off_t offset, 
                         void *buf, 
                         size_t count) {
    if (offset >= inode->size) {
        return 0;  /* EOF */
    }
    
    size_t available = inode->size - offset;
    size_t to_read = MIN(count, available);
    
    if (inode->flags & EXT4_INLINE_DATA) {
        /* Data is right here in the inode! */
        memcpy(buf, inode->inline_data + offset, to_read);
        return to_read;
        /* No disk I/O for data - it was loaded with the inode */
    }
    
    /* Fall back to normal block-based read */
    return read_via_blocks(inode, offset, buf, count);
}
 
/*
 * Space savings example:
 * 
 * WITHOUT inline data (100-byte file):
 *   Inode: 256 bytes
 *   Data block: 4096 bytes
 *   Total: 4352 bytes (3.5% efficient)
 * 
 * WITH inline data (100-byte file):
 *   Inode: 256 bytes (100 bytes is data)
 *   Data block: 0 bytes
 *   Total: 256 bytes (39% efficient - 17x improvement!)
 * 
 * For a directory with 1 million tiny files:
 *   Without inline: 4.15 GB disk usage
 *   With inline: 244 MB disk usage (17x savings!)
 */

File Systems with Inline Data Support
File System	Inline Data Support	Maximum Inline Size
ext4	Yes (with feature flag)	~60 bytes (or more with large inodes)
Btrfs	Yes	Up to ~2KB
XFS	No (but uses extents efficiently)	N/A
NTFS	Yes (resident attributes)	~700 bytes per MFT record
ZFS	Yes (metadata blocks)	Variable

Minimizing Overhead: Extent-Based Allocation

Traditional block pointers waste space when files are stored contiguously. If blocks 1000-2000 hold a file, we need 1001 individual pointers—even though a single (start, length) pair would suffice.

Extent-Based Allocation:

Converting Mermaid diagram...

extent_structure.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
/*
 * Extent-Based Allocation (ext4-style)
 * 
 * Extents replace individual block pointers with (start, length) tuples.
 */
 
/*
 * ext4 extent structure (12 bytes)
 */
struct ext4_extent {
    uint32_t    ee_block;       /* First logical block */
    uint16_t    ee_len;         /* Number of blocks */
    uint16_t    ee_start_hi;    /* High 16 bits of physical block */
    uint32_t    ee_start_lo;    /* Low 32 bits of physical block */
};
 
/*
 * Ext4 inode can hold 4 extents directly
 * For more, an extent tree is used (similar to indirect blocks)
 */
#define EXT4_EXTENTS_PER_INODE  4
 
struct ext4_extent_header {
    uint16_t    eh_magic;       /* Magic number: 0xF30A */
    uint16_t    eh_entries;     /* Number of valid entries */
    uint16_t    eh_max;         /* Maximum entries possible */
    uint16_t    eh_depth;       /* Tree depth (0 = leaf) */
    uint32_t    eh_generation;  /* Generation for checksums */
};
 
/*
 * Space comparison: 1GB contiguous file
 * 
 * Block pointers (4KB blocks, 8-byte pointers):
 *   Blocks needed: 262,144
 *   Pointers: 12 direct + 512 indirect + 261,620 via double indirect
 *   Indirect blocks: 1 + 511 = 512 blocks = 2 MB overhead
 * 
 * Extent-based (if contiguous):
 *   Extents needed: 1
 *   Extent size: 12 bytes
 *   Overhead: 12 bytes (0.0000012%)
 * 
 * That's a 174,000× reduction in metadata overhead!
 */
 
/*
 * Reading with extents
 */
block_ptr_t extent_lookup(struct ext4_extent *extents, 
                          int num_extents,
                          uint64_t logical_block) {
    for (int i = 0; i < num_extents; i++) {
        uint64_t start = extents[i].ee_block;
        uint64_t end = start + extents[i].ee_len;
        
        if (logical_block >= start && logical_block < end) {
            /* Found the extent containing this block */
            uint64_t offset = logical_block - start;
            uint64_t physical = ((uint64_t)extents[i].ee_start_hi << 32) |
                                extents[i].ee_start_lo;
            return physical + offset;
        }
    }
    
    return 0;  /* Block not found (hole) */
}

When Extents Don't Help

Block Size Tradeoffs

Larger Blocks (8KB-64KB)

•Fewer pointers needed for large files
•Better sequential read performance
•Fewer disk I/O operations
•Higher internal fragmentation
•More wasted space for small files
•Best for: Media files, databases

Smaller Blocks (1KB-4KB)

•Less internal fragmentation
•Better space efficiency for small files
•More pointers needed (more overhead)
•More disk I/O for large files
•Lower sequential throughput
•Best for: Source code, configs

Block Size Impact on 500-byte Files (1 million files)
Block Size	Space per File	Total Disk Usage	Space Efficiency
512 bytes	768 B (+ inode)	732 MB	68%
1 KB	1.25 KB	1.19 GB	42%
4 KB	4.25 KB	4.05 GB	12%
8 KB	8.25 KB	7.86 GB	6%
64 KB	64.25 KB	61.2 GB	0.8%

Choosing Block Size

Summary: Managing the Overhead Tax

Index block overhead is the price we pay for the flexibility of indexed allocation. Understanding this overhead enables informed decisions about file system configuration and design.

Key Takeaways

•Small files suffer most — A 1-byte file can use 4KB+ of disk space due to minimum block allocation.
•Large files are efficient — Overhead percentages decrease as file sizes increase, stabilizing around 0.2-0.5%.
•Inode tables are pre-allocated — Traditional file systems reserve fixed inode space, wasting capacity if unused.
•Inline data helps small files — Storing tiny files in the inode itself eliminates data block overhead entirely.
•Extents reduce pointer overhead — Contiguous files described by (start, length) tuples use far less metadata.
•Block size is a tradeoff — Larger blocks reduce pointers but increase internal fragmentation.

What's Next:

Page Complete

4 / 5