Linked List of Blocks - Linked Allocation | OneNoughtOne

0/236

Operating SystemsLinked Allocation

Linked Allocation

LevelIntermediate

Duration55 mins

TopicLinked Allocation

1 / 5

Linked List of Blocks

The Chain That Binds File Blocks Together

Imagine storing a book not as a continuous manuscript, but as individual pages scattered across a library, where each page contains a note pointing to the location of the next page. This analogy captures the essence of linked allocation—one of the fundamental methods for organizing file data on disk storage.

In earlier exploration of file system allocation strategies, we examined contiguous allocation, which required files to occupy consecutive disk blocks. While elegant in its simplicity and offering superb sequential read performance, contiguous allocation suffered from a fatal flaw: external fragmentation. As files were created and deleted, the disk became a patchwork of free space fragments, potentially leaving us unable to allocate space for new files even when total free space was abundant.

Linked allocation emerged as a direct solution to this fragmentation problem, introducing a fundamentally different approach to organizing file blocks on disk.

What You Will Learn

By the end of this page, you will understand how linked allocation works at a fundamental level, including how files are represented as chains of blocks, how the operating system traverses these chains, and why this approach elegantly solves the external fragmentation problem. You'll gain insight into the data structures underlying linked allocation and appreciate both its advantages and the challenges it introduces.

The Fundamental Concept of Linked Allocation

Linked allocation represents files as linked lists of disk blocks. Unlike contiguous allocation, where a file's blocks must be adjacent, linked allocation allows blocks to be scattered anywhere on the disk. Each block contains not only file data but also a pointer to the next block in the chain, creating a logical sequence from physically dispersed locations.

The core principle:

In linked allocation, the directory entry for a file contains the address of the first block (head) of the file. Each block then contains:

Data portion: The actual file content
Pointer portion: The address of the next block in the chain

The last block of the file contains a special null pointer (typically -1, 0, or a sentinel value) indicating the end of the file.

Converting Mermaid diagram...

Anatomy of a linked block:

Each disk block in a linked allocation scheme is divided into two logical sections:

+------------------------------------------+
|                                          |
|            FILE DATA                     |
|       (Block Size - Pointer Size)        |
|                                          |
+------------------------------------------+
|    NEXT BLOCK POINTER                    |
|    (typically 4 bytes)                   |
+------------------------------------------+

For a standard 4KB (4096 byte) block with a 4-byte pointer:

Data capacity: 4096 - 4 = 4092 bytes per block
Overhead: 4 bytes per block (approximately 0.1%)

While this overhead might seem negligible, it has profound implications for file organization and access patterns that we'll explore throughout this module.

Block Size Considerations

The non-power-of-two data capacity (4092 bytes instead of 4096) complicates address calculations compared to contiguous allocation. Programs expecting exactly 4096 bytes per block must account for this discrepancy, or the file system must introduce additional abstraction layers.

How Linked Allocation Works

Let's trace through the complete lifecycle of file operations under linked allocation to understand the mechanism in depth.

File Creation:

When creating a new file:

The file system allocates a free block from the free block list
The directory entry is created with the starting block pointer
Initial file length is set to 0 (or one block if pre-allocation occurs)
The allocated block's pointer is set to NULL (end of file)

Writing to a File:

When writing data that exceeds the current file size:

The file system traverses the chain to find the last block
Data is written to fill the remaining space in the last block
If more data remains, a new block is allocated from the free list
The previous last block's pointer is updated to point to the new block
The new block's pointer is set to NULL
This process repeats until all data is written

linked_allocation_write.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
// Simplified pseudocode for appending data with linked allocation
typedef struct {
    char data[BLOCK_SIZE - sizeof(uint32_t)];  // Data portion
    uint32_t next_block;                        // Pointer to next block
} LinkedBlock;
 
int append_to_file(FileEntry *file, void *data, size_t length) {
    // Find the last block by traversing the chain
    uint32_t current_block = file->start_block;
    LinkedBlock *block = read_block(current_block);
    
    // Traverse to end of chain
    while (block->next_block != NULL_BLOCK) {
        current_block = block->next_block;
        block = read_block(current_block);
    }
    
    size_t bytes_written = 0;
    size_t space_in_block = BLOCK_SIZE - sizeof(uint32_t) - file->size_in_last_block;
    
    while (bytes_written < length) {
        // Write data to current block
        size_t to_write = min(space_in_block, length - bytes_written);
        memcpy(block->data + file->size_in_last_block, 
               data + bytes_written, to_write);
        bytes_written += to_write;
        
        // If block is full and more data remains, allocate new block
        if (bytes_written < length) {
            uint32_t new_block = allocate_free_block();
            if (new_block == INVALID_BLOCK) {
                return -1;  // Disk full
            }
            
            block->next_block = new_block;
            write_block(current_block, block);
            
            current_block = new_block;
            block = read_block(current_block);
            block->next_block = NULL_BLOCK;
            space_in_block = BLOCK_SIZE - sizeof(uint32_t);
            file->size_in_last_block = 0;
        }
    }
    
    // Write final block and update file size
    write_block(current_block, block);
    file->size += length;
    return 0;
}

Reading from a File:

Sequential reading is straightforward:

Start at the first block (from directory entry)
Read data from the current block
Follow the pointer to the next block
Repeat until reaching the NULL pointer or requested bytes read

File Deletion:

Deleting a file involves:

Traverse the entire chain from start to end
Add each block back to the free block list
Remove the directory entry

Importantly, the blocks don't need to be zeroed or physically moved—only the free list metadata needs updating.

Linked Allocation Operations Summary
Operation	Algorithm	Complexity	Disk I/O Operations
Create File	Allocate one block, create directory entry	O(1)	2-3 writes
Append Data	Traverse to end, allocate new blocks as needed	O(n) where n = current blocks	n reads + m writes (m = new blocks)
Sequential Read	Follow pointer chain	O(blocks read)	1 read per block
Random Access (block k)	Traverse from start to block k	O(k)	k reads
Delete File	Traverse chain, return blocks to free list	O(n)	n reads + n writes to free list

The Linked List Data Structure on Disk

Understanding linked allocation requires appreciating how the familiar linked list data structure translates from memory to persistent storage.

In-Memory vs On-Disk Linked Lists:

In memory, a linked list node might contain:

struct Node {
    void *data;
    struct Node *next;  // Memory address
};

On disk, the "pointer" becomes a block address—an integer identifying the physical or logical block number:

struct DiskBlock {
    char data[BLOCK_DATA_SIZE];
    uint32_t next_block_number;  // Block address, not memory address
};

Key differences:

Aspect	Memory Linked List	Disk Linked List
Pointer type	Memory address	Block number
Traversal cost	Nanoseconds	Milliseconds (HDD) to microseconds (SSD)
Node size	Flexible	Fixed (block size)
Cache behavior	CPU cache friendly	Disk cache dependent
Failure impact	Process crash	Data loss risk

The Seek Time Catastrophe

On a traditional hard disk, each pointer traversal potentially triggers a disk seek—moving the read/write head to a different cylinder. A single seek takes 5-15ms. For a file with 1000 blocks scattered across the disk, random access could take 5-15 SECONDS, compared to milliseconds for contiguous allocation.

Block Address Formats:

Different file systems represent block addresses differently:

Absolute Block Number: A global index into the disk's block array
- Simple calculation: disk_offset = block_number × block_size
- Used in simpler file systems
Logical Block Address (LBA): Abstracts physical disk geometry
- Modern disks expose storage as a linear array of sectors
- The disk controller handles the mapping to cylinders/heads/sectors
Relative Block Number: Offset within a partition or volume
- Requires adding partition start offset for absolute disk access

Pointer Size Considerations:

The size of the next-block pointer determines the maximum disk size:

Pointer Size	Max Blocks Addressable	Max Disk Size (4KB blocks)
16-bit	65,536	256 MB
24-bit	16,777,216	64 GB
32-bit	4,294,967,296	16 TB
48-bit	281 trillion	1 EB (Exabyte)

Modern file systems typically use 32-bit or larger block pointers to support large storage devices.

block_address.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
// Block address calculation and traversal
#define BLOCK_SIZE 4096
#define POINTER_SIZE 4
#define DATA_PER_BLOCK (BLOCK_SIZE - POINTER_SIZE)
 
// Structure representing directory entry
typedef struct {
    char filename[256];
    uint32_t first_block;
    uint64_t file_size;
    uint32_t permissions;
    time_t created;
    time_t modified;
} DirectoryEntry;
 
// Read a specific byte offset within a file
int read_file_at_offset(DirectoryEntry *entry, uint64_t offset, 
                        void *buffer, size_t length) {
    // Calculate which block contains the offset
    uint32_t block_index = offset / DATA_PER_BLOCK;
    uint32_t offset_in_block = offset % DATA_PER_BLOCK;
    
    // Traverse to the target block
    uint32_t current_block = entry->first_block;
    for (uint32_t i = 0; i < block_index; i++) {
        if (current_block == NULL_BLOCK) {
            return -1;  // Offset beyond file end
        }
        // Read block to get next pointer
        LinkedBlock *block = read_block(current_block);
        current_block = block->next_block;
    }
    
    // Now read data from current_block onwards
    size_t bytes_read = 0;
    while (bytes_read < length && current_block != NULL_BLOCK) {
        LinkedBlock *block = read_block(current_block);
        
        size_t available = DATA_PER_BLOCK - offset_in_block;
        size_t to_read = min(available, length - bytes_read);
        
        memcpy(buffer + bytes_read, block->data + offset_in_block, to_read);
        bytes_read += to_read;
        offset_in_block = 0;  // After first block, start at beginning
        
        current_block = block->next_block;
    }
    
    return bytes_read;
}

Directory Entry Structure for Linked Files

The directory entry in linked allocation is notably simpler than in contiguous allocation because we don't need to track contiguous extent lengths.

Minimal Linked Allocation Directory Entry:

+------------------+------------------+
| Filename         | First Block      |
| (variable/fixed) | (4 bytes)        |
+------------------+------------------+

The file size can be:

Stored in directory entry: Requires updating on every write
Calculated by traversal: Counting blocks × data per block (slow but always consistent)

Extended Directory Entry:

Modern implementations typically include additional metadata:

directory_entry.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
// Extended directory entry for linked allocation
typedef struct {
    // File identification
    char name[255];           // Null-terminated filename
    uint8_t name_length;      // Actual length of filename
    
    // Linked allocation specific
    uint32_t first_block;     // Starting block of file chain
    uint32_t last_block;      // Cached pointer to last block (optimization)
    uint64_t file_size;       // Total file size in bytes
    uint32_t block_count;     // Number of blocks allocated
    
    // Standard metadata
    uint16_t permissions;     // rwx for owner/group/other
    uint32_t owner_uid;       // Owner user ID
    uint32_t owner_gid;       // Owner group ID
    
    // Timestamps
    int64_t created_time;     // Creation timestamp
    int64_t modified_time;    // Last modification timestamp
    int64_t accessed_time;    // Last access timestamp
    
    // File type
    uint8_t file_type;        // Regular, directory, symlink, etc.
    
} LinkedDirectoryEntry;
 
// Size: approximately 320 bytes per entry

The Last Block Optimization:

Notice the last_block field above. This is a crucial optimization for append operations:

Without last_block cache: Appending requires traversing the entire chain to find the end
With last_block cache: Append directly accesses the final block

This transforms append from O(n) to O(1), making linked allocation practical for log files and other append-heavy workloads.

Consistency Challenge

Caching the last block pointer creates a consistency challenge: if a crash occurs after updating the chain but before updating the directory entry, the cache becomes stale. File systems must either recalculate on mount or use journaling to ensure consistency.

Advantages of Linked Allocation

Linked allocation offers several compelling advantages that made it a popular choice, particularly in early personal computer file systems:

1. Complete Elimination of External Fragmentation

Because files don't require contiguous blocks, any free block can satisfy any allocation request. There's no concept of "holes" being too small—every free block is equally useful.

Contiguous Allocation

•Need contiguous space = size of file
•10MB file needs 10MB contiguous hole
•Fragmented disk may fail allocation
•Compaction required periodically
•Can't use scattered free blocks

Linked Allocation

•Any free block works for any file
•10MB file uses any 2,500 free blocks
•Allocation succeeds if ANY blocks free
•No compaction ever needed
•100% free space utilization

2. Dynamic File Growth

Files can grow indefinitely without pre-allocation or reservation:

No need to predict file size at creation
No wasted space from over-allocation
Growth limited only by total disk capacity

3. Simple Free Space Management

Free blocks form a simple pool:

Allocation: grab any block from the free list
Deallocation: return blocks to the free list
No searching for "best fit" or "first fit" in contiguous space

4. Efficient Deletion

Deleting a file only requires:

Traversing the chain once
Returning each block to the free list
Removing the directory entry

No data movement or space reclamation needed.

5. Natural Append Support

With the last-block optimization, appending is extremely efficient:

Find last block (O(1) with cache)
Link new block to chain
Update last-block pointer

This makes linked allocation excellent for log files, audit trails, and streaming data.

Real-World Success

The original FAT file system, which used linked allocation (with the FAT optimization), powered MS-DOS, early Windows, and remains in use today on USB drives, SD cards, and UEFI system partitions. Its success demonstrates that linked allocation, despite its limitations, fills an important niche.

Linked Allocation in Action

Let's visualize a concrete example of how linked allocation organizes files on a disk. Consider a small disk with 16 blocks (numbered 0-15) containing three files:

Converting Mermaid diagram...

File chains:

File	Block Chain	Total Blocks
report.txt	2 → 9 → 12 → NULL	3 blocks
photo.jpg	5 → 7 → 14 → NULL	3 blocks
config.ini	11 → NULL	1 block

Key observations:

Blocks are scattered: report.txt's blocks (2, 9, 12) are not contiguous
No wasted space: Free blocks (0, 1, 3, 4, 6, 8, 10, 13, 15) can be used by any new file
Each file has its own chain: Chains never overlap
Directory only stores start block: The rest discovered by traversal

Reading report.txt

To read report.txt sequentially:

Directory lookup → Start at block 2
Read block 2 → Data + pointer to block 9
Read block 9 → Data + pointer to block 12
Read block 12 → Data + NULL (end of file)

Total: 3 disk reads for 3 blocks of data. Compare this to contiguous allocation where a single multi-block read could fetch all data.

Historical Context and Evolution

Linked allocation has a rich history in computing, emerging as a practical solution to the limitations of early storage systems.

The Problem Space of the 1970s-1980s:

Disk drives were expensive and small (5-40MB)
Memory was severely limited (64KB-640KB)
Compaction operations were painfully slow
Users frequently created/deleted files
External fragmentation was a constant headache

Contiguous allocation, while offering excellent read performance, became increasingly impractical as:

Files couldn't grow without reallocation
Disk became fragmented after moderate use
Compaction required taking the system offline

Early File Systems Using Linked Allocation Concepts
System/Year	Approach	Notable Features
CTSS (1961)	Modified linked	One of first time-sharing systems
FAT (1977)	Centralized table	MS-DOS, Windows 3.x/9x
HFS (1985)	Extent-based variation	Macintosh file system
Amiga OFS (1985)	Pure linked blocks	Amiga Original File System

The MS-DOS Revolution:

When Microsoft and Seattle Computer Products designed the File Allocation Table (FAT) file system for 86-DOS (later MS-DOS), they chose linked allocation with a crucial optimization: moving all the pointers into a centralized table (the FAT). This preserved linked allocation's fragmentation advantages while improving random access—we'll explore this in depth in a later page.

Modern Relevance:

While modern file systems like ext4, NTFS, and APFS use more sophisticated allocation schemes (extent-based, copy-on-write), understanding linked allocation remains valuable because:

FAT is still ubiquitous: USB drives, SD cards, UEFI partitions
The concepts transfer: Understanding trade-offs aids in understanding modern systems
Interview knowledge: Allocation strategies are common system design topics
Embedded systems: Many resource-constrained systems still use linked approaches

Legacy Lives On

Every computer you use today likely has at least one FAT partition—the UEFI System Partition (ESP) that enables your computer to boot. Understanding linked allocation means understanding a technology that literally helps start every modern PC.

Summary: Linked List of Blocks

We've established the foundational understanding of linked allocation. Let's consolidate the key concepts:

Key Takeaways

•Linked allocation represents files as chains — Each block contains data plus a pointer to the next block, with the directory storing only the first block address.
•Completely eliminates external fragmentation — Any free block can satisfy any allocation, regardless of file size or existing fragmentation.
•Trades random access performance for space efficiency — Reading block n requires traversing blocks 0 through n-1, making random access O(n).
•Each block loses space to pointer overhead — Typically 4 bytes per block, reducing usable data capacity slightly.
•Append operations are naturally efficient — With last-block caching, appending is O(1) rather than O(n).
•Historical importance remains relevant — FAT file system principles are still used in billions of devices today.

What's next:

The next page examines the pointer structure in detail—how each block contains a pointer to its successor, the mechanics of pointer updates during file operations, and the implications of pointer corruption. Understanding these mechanics is essential for grasping both the strengths and vulnerabilities of linked allocation.

Page Complete

You now understand the fundamental concept of linked allocation—files as chains of blocks scattered across the disk, connected by pointers. This mental model will serve as the foundation for understanding pointer mechanics, fragmentation behavior, random access performance, and the revolutionary FAT optimization in the following pages.

Operating SystemsLinked Allocation

Linked Allocation

LevelIntermediate

Duration55 mins

TopicLinked Allocation

1 / 5

Linked List of Blocks

The Chain That Binds File Blocks Together

Linked allocation emerged as a direct solution to this fragmentation problem, introducing a fundamentally different approach to organizing file blocks on disk.

What You Will Learn

The Fundamental Concept of Linked Allocation

The core principle:

In linked allocation, the directory entry for a file contains the address of the first block (head) of the file. Each block then contains:

Data portion: The actual file content
Pointer portion: The address of the next block in the chain

The last block of the file contains a special null pointer (typically -1, 0, or a sentinel value) indicating the end of the file.

Converting Mermaid diagram...

Anatomy of a linked block:

Each disk block in a linked allocation scheme is divided into two logical sections:

+------------------------------------------+
|                                          |
|            FILE DATA                     |
|       (Block Size - Pointer Size)        |
|                                          |
+------------------------------------------+
|    NEXT BLOCK POINTER                    |
|    (typically 4 bytes)                   |
+------------------------------------------+

For a standard 4KB (4096 byte) block with a 4-byte pointer:

Data capacity: 4096 - 4 = 4092 bytes per block
Overhead: 4 bytes per block (approximately 0.1%)

While this overhead might seem negligible, it has profound implications for file organization and access patterns that we'll explore throughout this module.

Block Size Considerations

How Linked Allocation Works

Let's trace through the complete lifecycle of file operations under linked allocation to understand the mechanism in depth.

File Creation:

When creating a new file:

The file system allocates a free block from the free block list
The directory entry is created with the starting block pointer
Initial file length is set to 0 (or one block if pre-allocation occurs)
The allocated block's pointer is set to NULL (end of file)

Writing to a File:

When writing data that exceeds the current file size:

The file system traverses the chain to find the last block
Data is written to fill the remaining space in the last block
If more data remains, a new block is allocated from the free list
The previous last block's pointer is updated to point to the new block
The new block's pointer is set to NULL
This process repeats until all data is written

linked_allocation_write.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
// Simplified pseudocode for appending data with linked allocation
typedef struct {
    char data[BLOCK_SIZE - sizeof(uint32_t)];  // Data portion
    uint32_t next_block;                        // Pointer to next block
} LinkedBlock;
 
int append_to_file(FileEntry *file, void *data, size_t length) {
    // Find the last block by traversing the chain
    uint32_t current_block = file->start_block;
    LinkedBlock *block = read_block(current_block);
    
    // Traverse to end of chain
    while (block->next_block != NULL_BLOCK) {
        current_block = block->next_block;
        block = read_block(current_block);
    }
    
    size_t bytes_written = 0;
    size_t space_in_block = BLOCK_SIZE - sizeof(uint32_t) - file->size_in_last_block;
    
    while (bytes_written < length) {
        // Write data to current block
        size_t to_write = min(space_in_block, length - bytes_written);
        memcpy(block->data + file->size_in_last_block, 
               data + bytes_written, to_write);
        bytes_written += to_write;
        
        // If block is full and more data remains, allocate new block
        if (bytes_written < length) {
            uint32_t new_block = allocate_free_block();
            if (new_block == INVALID_BLOCK) {
                return -1;  // Disk full
            }
            
            block->next_block = new_block;
            write_block(current_block, block);
            
            current_block = new_block;
            block = read_block(current_block);
            block->next_block = NULL_BLOCK;
            space_in_block = BLOCK_SIZE - sizeof(uint32_t);
            file->size_in_last_block = 0;
        }
    }
    
    // Write final block and update file size
    write_block(current_block, block);
    file->size += length;
    return 0;
}

Reading from a File:

Sequential reading is straightforward:

Start at the first block (from directory entry)
Read data from the current block
Follow the pointer to the next block
Repeat until reaching the NULL pointer or requested bytes read

File Deletion:

Deleting a file involves:

Traverse the entire chain from start to end
Add each block back to the free block list
Remove the directory entry

Importantly, the blocks don't need to be zeroed or physically moved—only the free list metadata needs updating.

Linked Allocation Operations Summary
Operation	Algorithm	Complexity	Disk I/O Operations
Create File	Allocate one block, create directory entry	O(1)	2-3 writes
Append Data	Traverse to end, allocate new blocks as needed	O(n) where n = current blocks	n reads + m writes (m = new blocks)
Sequential Read	Follow pointer chain	O(blocks read)	1 read per block
Random Access (block k)	Traverse from start to block k	O(k)	k reads
Delete File	Traverse chain, return blocks to free list	O(n)	n reads + n writes to free list

The Linked List Data Structure on Disk

Understanding linked allocation requires appreciating how the familiar linked list data structure translates from memory to persistent storage.

In-Memory vs On-Disk Linked Lists:

In memory, a linked list node might contain:

struct Node {
    void *data;
    struct Node *next;  // Memory address
};

On disk, the "pointer" becomes a block address—an integer identifying the physical or logical block number:

struct DiskBlock {
    char data[BLOCK_DATA_SIZE];
    uint32_t next_block_number;  // Block address, not memory address
};

Key differences:

Aspect	Memory Linked List	Disk Linked List
Pointer type	Memory address	Block number
Traversal cost	Nanoseconds	Milliseconds (HDD) to microseconds (SSD)
Node size	Flexible	Fixed (block size)
Cache behavior	CPU cache friendly	Disk cache dependent
Failure impact	Process crash	Data loss risk

The Seek Time Catastrophe

Block Address Formats:

Different file systems represent block addresses differently:

Absolute Block Number: A global index into the disk's block array
- Simple calculation: disk_offset = block_number × block_size
- Used in simpler file systems
Logical Block Address (LBA): Abstracts physical disk geometry
- Modern disks expose storage as a linear array of sectors
- The disk controller handles the mapping to cylinders/heads/sectors
Relative Block Number: Offset within a partition or volume
- Requires adding partition start offset for absolute disk access

Pointer Size Considerations:

The size of the next-block pointer determines the maximum disk size:

Pointer Size	Max Blocks Addressable	Max Disk Size (4KB blocks)
16-bit	65,536	256 MB
24-bit	16,777,216	64 GB
32-bit	4,294,967,296	16 TB
48-bit	281 trillion	1 EB (Exabyte)

Modern file systems typically use 32-bit or larger block pointers to support large storage devices.

block_address.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
// Block address calculation and traversal
#define BLOCK_SIZE 4096
#define POINTER_SIZE 4
#define DATA_PER_BLOCK (BLOCK_SIZE - POINTER_SIZE)
 
// Structure representing directory entry
typedef struct {
    char filename[256];
    uint32_t first_block;
    uint64_t file_size;
    uint32_t permissions;
    time_t created;
    time_t modified;
} DirectoryEntry;
 
// Read a specific byte offset within a file
int read_file_at_offset(DirectoryEntry *entry, uint64_t offset, 
                        void *buffer, size_t length) {
    // Calculate which block contains the offset
    uint32_t block_index = offset / DATA_PER_BLOCK;
    uint32_t offset_in_block = offset % DATA_PER_BLOCK;
    
    // Traverse to the target block
    uint32_t current_block = entry->first_block;
    for (uint32_t i = 0; i < block_index; i++) {
        if (current_block == NULL_BLOCK) {
            return -1;  // Offset beyond file end
        }
        // Read block to get next pointer
        LinkedBlock *block = read_block(current_block);
        current_block = block->next_block;
    }
    
    // Now read data from current_block onwards
    size_t bytes_read = 0;
    while (bytes_read < length && current_block != NULL_BLOCK) {
        LinkedBlock *block = read_block(current_block);
        
        size_t available = DATA_PER_BLOCK - offset_in_block;
        size_t to_read = min(available, length - bytes_read);
        
        memcpy(buffer + bytes_read, block->data + offset_in_block, to_read);
        bytes_read += to_read;
        offset_in_block = 0;  // After first block, start at beginning
        
        current_block = block->next_block;
    }
    
    return bytes_read;
}

Directory Entry Structure for Linked Files

The directory entry in linked allocation is notably simpler than in contiguous allocation because we don't need to track contiguous extent lengths.

Minimal Linked Allocation Directory Entry:

+------------------+------------------+
| Filename         | First Block      |
| (variable/fixed) | (4 bytes)        |
+------------------+------------------+

The file size can be:

Stored in directory entry: Requires updating on every write
Calculated by traversal: Counting blocks × data per block (slow but always consistent)

Extended Directory Entry:

Modern implementations typically include additional metadata:

directory_entry.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
// Extended directory entry for linked allocation
typedef struct {
    // File identification
    char name[255];           // Null-terminated filename
    uint8_t name_length;      // Actual length of filename
    
    // Linked allocation specific
    uint32_t first_block;     // Starting block of file chain
    uint32_t last_block;      // Cached pointer to last block (optimization)
    uint64_t file_size;       // Total file size in bytes
    uint32_t block_count;     // Number of blocks allocated
    
    // Standard metadata
    uint16_t permissions;     // rwx for owner/group/other
    uint32_t owner_uid;       // Owner user ID
    uint32_t owner_gid;       // Owner group ID
    
    // Timestamps
    int64_t created_time;     // Creation timestamp
    int64_t modified_time;    // Last modification timestamp
    int64_t accessed_time;    // Last access timestamp
    
    // File type
    uint8_t file_type;        // Regular, directory, symlink, etc.
    
} LinkedDirectoryEntry;
 
// Size: approximately 320 bytes per entry

The Last Block Optimization:

Notice the last_block field above. This is a crucial optimization for append operations:

Without last_block cache: Appending requires traversing the entire chain to find the end
With last_block cache: Append directly accesses the final block

This transforms append from O(n) to O(1), making linked allocation practical for log files and other append-heavy workloads.

Consistency Challenge

Advantages of Linked Allocation

Linked allocation offers several compelling advantages that made it a popular choice, particularly in early personal computer file systems:

1. Complete Elimination of External Fragmentation

Because files don't require contiguous blocks, any free block can satisfy any allocation request. There's no concept of "holes" being too small—every free block is equally useful.

Contiguous Allocation

•Need contiguous space = size of file
•10MB file needs 10MB contiguous hole
•Fragmented disk may fail allocation
•Compaction required periodically
•Can't use scattered free blocks

Linked Allocation

•Any free block works for any file
•10MB file uses any 2,500 free blocks
•Allocation succeeds if ANY blocks free
•No compaction ever needed
•100% free space utilization

2. Dynamic File Growth

Files can grow indefinitely without pre-allocation or reservation:

No need to predict file size at creation
No wasted space from over-allocation
Growth limited only by total disk capacity

3. Simple Free Space Management

Free blocks form a simple pool:

Allocation: grab any block from the free list
Deallocation: return blocks to the free list
No searching for "best fit" or "first fit" in contiguous space

4. Efficient Deletion

Deleting a file only requires:

Traversing the chain once
Returning each block to the free list
Removing the directory entry

No data movement or space reclamation needed.

5. Natural Append Support

With the last-block optimization, appending is extremely efficient:

Find last block (O(1) with cache)
Link new block to chain
Update last-block pointer

This makes linked allocation excellent for log files, audit trails, and streaming data.

Real-World Success

Linked Allocation in Action

Let's visualize a concrete example of how linked allocation organizes files on a disk. Consider a small disk with 16 blocks (numbered 0-15) containing three files:

Converting Mermaid diagram...

File chains:

File	Block Chain	Total Blocks
report.txt	2 → 9 → 12 → NULL	3 blocks
photo.jpg	5 → 7 → 14 → NULL	3 blocks
config.ini	11 → NULL	1 block

Key observations:

Blocks are scattered: report.txt's blocks (2, 9, 12) are not contiguous
No wasted space: Free blocks (0, 1, 3, 4, 6, 8, 10, 13, 15) can be used by any new file
Each file has its own chain: Chains never overlap
Directory only stores start block: The rest discovered by traversal

Reading report.txt

To read report.txt sequentially:

Directory lookup → Start at block 2
Read block 2 → Data + pointer to block 9
Read block 9 → Data + pointer to block 12
Read block 12 → Data + NULL (end of file)

Total: 3 disk reads for 3 blocks of data. Compare this to contiguous allocation where a single multi-block read could fetch all data.

Historical Context and Evolution

Linked allocation has a rich history in computing, emerging as a practical solution to the limitations of early storage systems.

The Problem Space of the 1970s-1980s:

Disk drives were expensive and small (5-40MB)
Memory was severely limited (64KB-640KB)
Compaction operations were painfully slow
Users frequently created/deleted files
External fragmentation was a constant headache

Contiguous allocation, while offering excellent read performance, became increasingly impractical as:

Files couldn't grow without reallocation
Disk became fragmented after moderate use
Compaction required taking the system offline

Early File Systems Using Linked Allocation Concepts
System/Year	Approach	Notable Features
CTSS (1961)	Modified linked	One of first time-sharing systems
FAT (1977)	Centralized table	MS-DOS, Windows 3.x/9x
HFS (1985)	Extent-based variation	Macintosh file system
Amiga OFS (1985)	Pure linked blocks	Amiga Original File System

The MS-DOS Revolution:

Modern Relevance:

While modern file systems like ext4, NTFS, and APFS use more sophisticated allocation schemes (extent-based, copy-on-write), understanding linked allocation remains valuable because:

FAT is still ubiquitous: USB drives, SD cards, UEFI partitions
The concepts transfer: Understanding trade-offs aids in understanding modern systems
Interview knowledge: Allocation strategies are common system design topics
Embedded systems: Many resource-constrained systems still use linked approaches

Legacy Lives On

Summary: Linked List of Blocks

We've established the foundational understanding of linked allocation. Let's consolidate the key concepts:

Key Takeaways

•Linked allocation represents files as chains — Each block contains data plus a pointer to the next block, with the directory storing only the first block address.
•Completely eliminates external fragmentation — Any free block can satisfy any allocation, regardless of file size or existing fragmentation.
•Trades random access performance for space efficiency — Reading block n requires traversing blocks 0 through n-1, making random access O(n).
•Each block loses space to pointer overhead — Typically 4 bytes per block, reducing usable data capacity slightly.
•Append operations are naturally efficient — With last-block caching, appending is O(1) rather than O(n).
•Historical importance remains relevant — FAT file system principles are still used in billions of devices today.

What's next:

Page Complete