Operating System Slides 📂 Introduction · 20 of 22 47 min read

File Allocation Methods: Contiguous, Linked & Indexed

How the file system places a file's blocks on disk — and why the choice shapes speed, fragmentation and even ransomware recovery. Covers contiguous (start+length), linked chains and FAT, indexed blocks and the UNIX i-node (48 KB to 4 TB), seek-cost maths, a comparison table, and real cybersecurity cases — with fully animated disk diagrams.

🗂️

File Allocation Methods — Contiguous, Linked & Indexed

How the file system decides where a file's blocks live on disk — and how that choice shapes speed, fragmentation, growth and even how a ransomware attack plays out. Three classical methods, the UNIX i-node, seek-cost maths, and real cybersecurity cases — with fully animated disk diagrams.
Contiguous Linked / FAT Indexed / i-node Security Cases
Press Next → or use ← → arrow keys
SECTION 01

The Problem — 100,000 Lockers

🧳 REAL-WORLD ANALOGY · THE BAGGAGE LOCKERS
Where Do You Put a Big Bag?
An airport has 100,000 identical lockers and a bag too big for one. Three handlers propose plans. The first insists on a run of adjacent lockers — fast to collect, but you need that many in a row. The second scatters the bag and leaves a note in each locker pointing to the next — flexible, but you must walk the chain. The third keeps one index card listing every locker used — one lookup, then straight to any piece.
🧠
Three Ways to Place a File

Those are exactly the three file allocation methods: contiguous (a consecutive run), linked (a chain of pointers), and indexed (one index block listing all the data blocks). Each trades speed against flexibility — and, as we'll see, against how a disk survives an attack.

SECTION 02

Three Classical Families

📏
Contiguous
block N, N+1, N+2…
A file occupies one consecutive run of blocks. The directory stores just a start block + length. Blazing random access, but suffers external fragmentation and painful growth.
🔗
Linked
chain of pointers
Blocks scatter anywhere; each holds a pointer to the next. No external fragmentation and easy growth, but random access is slow and one lost pointer breaks the file. FAT centralises the pointers.
📇
Indexed
one index block
A dedicated index block lists every data block's address. Fast random access and easy growth; costs one index block per file. The UNIX i-node is the classic design.
🎯
One Question, Three Answers

Every method answers the same question — "given a file and a block number, which physical disk block do I read?" — differently. The rest of this tutorial traces that lookup through each design and counts the disk seeks it costs.

SECTION 03 · DIAGRAM

Contiguous — One Run Per File

0 1 5 6 7 8 9 16 17 18 23 24 25 26 27 28 29 count2 count3 count4 mail10 mail11 mail12 mail13 mail14 mail15 list19 list20 list21 list22 Directory filestartlen count23 mail106 list194
📏
Start + Length Is the Whole Recipe

Each file is a consecutive run, so the directory needs only a start block and a length: count at 2 (len 3), mail at 10 (len 6), list at 19 (len 4). Block k of a file is simply start + k — one seek to reach any byte.

SECTION 03

Contiguous — The Trade-offs

# Reach block k of a contiguous file — one calculation, one seek
physical_block = start + k          # e.g. start=100, k=2 → block 102
✅
Strengths
Excellent random access — any block by arithmetic, one seek. Tiny directory entry. Sequential reads stream off adjacent tracks at full speed. Ideal for write-once media like CD-ROMs and DVDs.
⚠️
Weaknesses
External fragmentation: free space scatters into runs too short to hold a new file. Growth is painful — a file can't expand into an occupied neighbour without being moved wholesale.
🔬
A Forensic Gift

Because a file's blocks sit together, investigators can carve a deleted file straight off the raw disk by scanning for its signature bytes — no directory needed. Tools like PhotoRec and Autopsy lean on exactly this property.

SECTION 04 · DIAGRAM

Linked — A Chain of Pointers

dir: jeepstart = 9 blk 9next → 16 blk 16next → 1 blk 1next → 10 blk 10next → 25 blk 25next → NULL the blocks are physically scattered — the pointers impose the order
🔗
Each Block Points to the Next

The directory records only the start block (9); every block then stores the address of the next, ending at NULL. Files grow by appending a block anywhere free — no external fragmentation. But reaching block k means walking k+1 blocks, and one corrupt pointer orphans the entire tail.

SECTION 04

FAT — Pull the Pointers Into a Table

Storing the "next" pointer inside each block wastes space and forces a seek per hop. The File Allocation Table gathers every pointer into one table the OS caches in RAM.

# Pointer overhead in a classic 512-byte block
4 bytes pointer  +  508 bytes data  =  512-byte block   # ~0.8% overhead
4 BPointer per block
508 BUsable data / block
FAT12/16/32The variants
exFATModern flash/SD
💾
The Table That Ran the PC Era

FAT debuted with MS-DOS (1981) and carried Windows 95/98/ME. Caching the whole table in memory turns chain-walking into fast in-RAM lookups. Its descendants — FAT32 and exFAT — still format nearly every USB stick, SD card and camera today.

SECTION 05 · DIAGRAM

Indexed — One Block Lists Them All

dir entryindex → 19 index blk 19 [0]9 [1]16 [2]1 [3]10 [4]25 [5]−1 data blk 9 data blk 16 data blk 1 data blk 10 data blk 25 −1 = end of file
📇
Random Access Without the Fragmentation

One index block (here block 19) holds an array of every data-block address — [9, 16, 1, 10, 25, −1]. To read block k, look up index[k] and seek there: fast random access and easy growth, at the cost of one index block per file.

SECTION 05 · DIAGRAM

The UNIX i-node — Indexing That Scales

i-nodesize · owner · perms · times direct [0..11]12 pointers single indirect double indirect triple indirect 12 blocks→ 48 KB 1,024 ptrs→ 4 MB 1,024² ptrs→ 4 GB 1,024³ ptrs→ 4 TB
🐧
Small Files Free, Huge Files Possible

The i-node's 12 direct pointers reach a 48 KB file in one seek — most files are small, so this is the common case. Single, double and triple indirect pointers add index-of-index levels, scaling to 4 MB, 4 GB and 4 TB. Tiny files pay nothing for the machinery big files need.

SECTION 06 · WORKED

Reading Byte 10,240 — Count the Seeks

byte offset 10,240block size 4,096 B k = 10,240 ÷ 4,096 = 2 d = 10,240 mod 4,096 = 2,048 block 2+ offset 2,048
MethodHow block 2 is foundSeeks
Contiguousstart 100 + 2 = block 1021 seek
Indexedread index block, then index[2]2 seeks
Linkedwalk block 0 → 1 → 2 in the chaink+1 = 3 seeks
🧮
Same Byte, Very Different Cost

Every method first splits the offset into block 2, offset 2,048. From there contiguous needs one seek, indexed a fixed two, and linked k+1 — growing with the block number. That single difference is why random-access workloads avoid linked allocation.

SECTION 07

The Three Methods, Side by Side

PropertyContiguousLinkedIndexed
Sequential accessExcellentGoodGood
Random accessExcellentPoorGood
External fragmentationYesNoneNone
Internal fragmentationMinimalMinimalSmall
File growthPainfulEasyEasy
Overhead per fileNone1 ptr / block1 index / file
Fault toleranceMediumVery lowLow
Real-world useCD-ROM / DVDFAT32 / exFAText2/3/4
⚖️
No Universal Winner

Contiguous wins on read-only media; linked survives fragmentation but crawls on random access; indexed balances both and powers modern Linux file systems. The right choice depends on the workload and the medium.

SECTION 08

When Allocation Meets Attackers

💥
NotPetya · 2017
> $10 billion
Overwrote the NTFS Master File Table and MBR. The data blocks survived but were unreachable — kill the index, lose the file.
🔒
WannaCry · 2017
200k machines · 150 countries
Encrypted files in place, leaving allocation metadata intact — so recovery hinged on backups, not carving.
📄
Panama Papers · 2016
11.5M documents
File carving scanned raw disk for JPEG/PDF/DOCX signatures — recovery that leans on contiguous layout.
⛽
Colonial Pipeline · 2021
6-day shutdown
DarkSide ransomware; forensics later reconstructed events from i-node and MFT records.
🎬
Sony Pictures · 2014
Shamoon-family wiper
Destroyed partition tables at disk level; only tape backups brought the data back.
🕵️
Vault 7 · 2017
spoofed i-nodes
Implants forged i-node timestamps, permissions and block pointers; detection cross-checks chains against on-disk reality.
SECTION 09

Forensics — Reading the Disk Directly

🔬 The Digital-Forensics Playbook
1 · ImageCopy the disk read-only (dd, dc3dd, FTK Imager) so the evidence is never altered.
2 · IdentifyInspect the boot sector to find the allocation method and file-system type.
3 · ParseRead metadata with Autopsy, X-Ways, Sleuth Kit — i-nodes, MFT records, directories.
4 · CarveSignature-scan for file headers — JPEG FF D8 FF, PDF %PDF- — to recover deleted files.
5 · TimelineCross-reference the journal ($LogFile, ext4 journal) to reconstruct what happened when.
🕳️
Where Malware Hides

NTFS Alternate Data Streams let extra hidden streams ride along with a file — a classic malware hiding spot, surfaced with dir /R or streams.exe. Journaling ($LogFile, ext4 journal) both protects integrity and leaves a trail investigators can follow.

SECTION 10

Eight Rules for File Allocation

🗂️ FILE ALLOCATION · CHECKLIST
1
Three families: contiguous, linked, indexed — each answers "which physical block?" differently.
2
Contiguous stores start + length; block k = start + k; superb access but external fragmentation and hard growth.
3
Linked chains a next-pointer in each block; easy growth, no external fragmentation, but k+1 seeks and fragile.
4
FAT centralises the pointers into one cached table — the design behind FAT32 and exFAT.
5
Indexed keeps one index block per file — fast random access and easy growth at a small overhead.
6
The UNIX i-node mixes 12 direct pointers with single/double/triple indirection — 48 KB to 4 TB.
7
Kill the index (MFT / i-node) and intact data becomes unreachable — a favourite ransomware tactic.
8
Carving, journaling and redundant tables are the forensic and hardening defences against that.
FINAL

Where a File's Blocks Live

start + kContiguous
k+1 seeksLinked chain
index[k]Indexed
12 + 3 lvlsi-node pointers
MFTRansomware target
🎯
You Now Understand File Allocation

From contiguous runs, linked chains and index blocks, through the UNIX i-node and seek-cost maths, to the security cases where destroying an index destroys access — you can map any file to its physical blocks and reason about how a disk survives failure and attack.

📚
Where To Go Next

Allocation decides where blocks go; next comes free-space management (bitmaps and free lists) and disk scheduling (FCFS, SSTF, SCAN, C-SCAN) — how the OS chooses which pending disk request to serve first.

🗂️ End of tutorial · Press ← to review, or click Restart

1 / 15