These are the notes for CS Fundamentals for Placements, episode 36. In episode 35 a file was a name, a set of attributes and a file descriptor. Today we open the file system's register: which disk blocks hold a file, and how does the OS find them? We invent the three allocation methods (contiguous, linked with the FAT, and indexed with multilevel indexes), the Unix inode with direct, single, double and triple indirect blocks, maximum file size numericals, free-space management (bitmap, free list, grouping, counting), and what real systems add: ext4 extents, NTFS's master file table, the virtual file system (VFS), journaling, fsck and the buffer/page cache. Every term is explained in plain words the first time it appears, and there is a full glossary at the end.
All program outputs below are real: every C program was compiled with gcc 13.3 -O2 (the SyntaxPilot compiler's flags: gcc -O2 -Wno-unused-result main.c -o main -lm) and run on Linux x86-64 (ext4) on 6 November 2026.
Quick recap
- A disk is a row of numbered blocks (fixed-size pieces, e.g. 4 KB), numbered 0, 1, 2, ...
- A file is a named collection of bytes; it needs one or more blocks.
- The inode is the on-disk record of a Unix file: size, owner, permissions, times, and where its blocks are.
- The allocation method is the rule that decides which blocks a file gets and how they're recorded. We judge each method by: speed of sequential access (reading in order), speed of direct access (jumping to block k), wasted space, and whether files can grow.
1. Contiguous allocation
The story: cinema seats
A family of five books seats 10-14, side by side. Contiguous allocation gives each file a run of consecutive blocks. The directory entry stores only the start block and the length. File block k is simply disk block start + k.
Live: 7 blocks free, a 5-block file fails
#include <stdio.h>
// A tiny disk of 20 blocks. Contiguous: every file needs blocks IN A ROW
char disk[21] = "....................";
int alloc(char name, int n) { // first fit
for (int s = 0; s + n <= 20; s++) {
int ok = 1;
for (int i = s; i < s + n; i++) if (disk[i] != '.') ok = 0;
if (ok) { for (int i = s; i < s + n; i++) disk[i] = name; return s; }
}
return -1; // no run of n free blocks
}
void del(char name) { for (int i = 0; i < 20; i++) if (disk[i] == name) disk[i] = '.'; }
int main(void) {
alloc('A', 4); alloc('B', 3); alloc('C', 5); alloc('D', 2); alloc('E', 4);
printf("disk: %s\n", disk);
del('B'); del('D'); // two files deleted
int free = 0; for (int i = 0; i < 20; i++) free += disk[i] == '.';
printf("disk: %s (%d blocks free)\n", disk, free);
int s = alloc('F', 5);
printf("file F needs 5 blocks: %s\n", s < 0 ? "FAILED, no 5 free in a row" : "ok");
}
disk: AAAABBBCCCCCDDEEEE..
disk: AAAA...CCCCC..EEEE.. (7 blocks free)
file F needs 5 blocks: FAILED, no 5 free in a row
allocuses first fit (the first gap big enough), from episode 30. Best fit and worst fit are other choices.- After deleting B and D there are 7 free blocks, but the largest gap is 3, so F (5 blocks) fails: external fragmentation, free space split into gaps too small to use.
- File A can't grow either: block 4 belongs to someone else.
| Contiguous allocation | |
|---|---|
| Sequential access | excellent (one smooth pass, little disk head movement) |
| Direct access | excellent: block k = start + k |
| Fragmentation | external fragmentation; fixed by compaction (moving files together), which is slow |
| Growth | hard; the final size must be known (or guessed) up front |
| Fits | files written once that never grow |
2. Linked allocation
The story: a treasure hunt
Clue 1 says where clue 2 is. In linked allocation, each block holds data plus the number of the next block of the file; the directory stores the first (and often the last) block. Any free block anywhere will do.
| Linked allocation | |
|---|---|
| External fragmentation | none: any free block can be used |
| Growth | easy: link one more block |
| Sequential access | fine |
| Direct access | slow: to reach block k, read blocks 0 to k-1 first |
| Reliability | one damaged pointer loses the rest of the file |
| Space | a few bytes of every block go to the pointer |
Improvement: link clusters (groups of, say, 4 blocks) instead of single blocks: fewer pointers and fewer jumps, at the cost of more internal fragmentation (a half-empty last cluster).
The File Allocation Table (FAT)
Move all the next-pointers out of the blocks into one table at the start of the disk: the File Allocation Table. There is one entry per disk block; it holds the next block of the same file, a special end-of-file value, or 0 for a free block. The directory entry stores the first block. The table is small enough to cache in RAM, so following a chain costs memory reads, not disk reads, and direct access is much faster than plain linked allocation. The FAT also doubles as the free-space record (the 0 entries).
#include <stdio.h>
#define EOFB -1
// FAT: one table entry per disk block = the NEXT block of the same file
int fat[32]; // 0 = free block
int main(void) {
fat[9] = 16; fat[16] = 1; fat[1] = 10; fat[10] = 25; fat[25] = EOFB;
int start = 9; // from the directory entry
printf("report.txt starts at block %d\nchain:", start);
for (int b = start; b != EOFB; b = fat[b]) printf(" %d", b);
printf(" -> end of file\n");
int want = 3, b = start, steps = 0; // read the file's block 3
for (int k = 0; k < want; k++) { b = fat[b]; steps++; }
printf("file block %d is disk block %d (%d steps through the FAT)\n", want, b, steps);
}
report.txt starts at block 9
chain: 9 16 1 10 25 -> end of file
file block 3 is disk block 10 (3 steps through the FAT)
FAT is still everywhere on removable media: its modern form exFAT is "a file system optimized for flash memory such as USB flash drives and SD cards", and the SD Association adopted it as the default for SDXC and SDUC cards larger than 32 GB. Plain FAT32 limits a single file to 4 GB.
3. Indexed allocation
The story: a book's table of contents
Chapter 7 → page 212: jump straight there. Indexed allocation puts all of a file's block numbers into one special block, the index block. Entry k of the index block is the disk block holding file block k. The directory (or inode) points to the index block.
| Indexed allocation | |
|---|---|
| External fragmentation | none |
| Direct access | fast: one lookup in the index |
| Growth | easy until the index block is full |
| Overhead | every file, even a 1-byte one, needs a whole index block |
When one index block isn't enough
With 4 KB blocks and 4-byte block numbers, one index block holds 4096 / 4 = 1024 entries: files up to 1024 × 4 KB = 4 MB. Fixes:
- Linked scheme: the last entry of an index block points to the next index block.
- Multilevel index: an outer index block points to inner index blocks, which point to data blocks (two levels: 1024 × 1024 blocks = 4 GB with 4 KB blocks).
- Combined scheme: a few direct pointers for small files plus single, double and triple indirect pointers for big ones: the Unix inode.
The Unix inode
The classic Unix inode (used by ext2 and ext3 on Linux) has 15 block pointers:
inode
├─ 12 direct pointers ─────────────────▶ 12 data blocks
├─ single indirect ──▶ [p pointers] ────▶ p data blocks
├─ double indirect ──▶ [p] ─▶ [p] each ─▶ p² data blocks
└─ triple indirect ──▶ [p] ─▶ [p] ─▶ [p] ▶ p³ data blocks
- Direct pointer: holds the number of a data block. With 4 KB blocks, the 12 direct pointers cover the first 48 KB: small files need nothing else.
- Single indirect pointer: points to a block full of data-block numbers (p of them).
- Double indirect: points to a block of single-indirect blocks (p × p data blocks).
- Triple indirect: one more level (p³ data blocks).
- p = block size / pointer size = pointers per block.
The Linux kernel's ext4 documentation ("The Contents of inode.i_block") describes exactly this layout for the ext2/3 block map with 4 KiB blocks: slots 0-11 map file blocks 0-11 directly, slot 12 (indirect) maps file blocks 12-1035, slot 13 (double-indirect) 1036-1,049,611, and slot 14 (triple-indirect) 1,049,612-1,074,791,436.
Live: maximum file size
#include <stdio.h>
// Unix inode: 12 direct pointers, 1 single, 1 double, 1 triple indirect
int main(void) {
long sizes[2] = {1024, 4096}; // block sizes in bytes
for (int i = 0; i < 2; i++) {
long B = sizes[i], p = B / 4; // 4-byte pointers per block
long direct = 12, single = p, dbl = p * p, triple = p * p * p;
long blocks = direct + single + dbl + triple;
printf("block %ld B: %ld pointers per block\n", B, p);
printf(" direct %ld + single %ld + double %ld + triple %ld\n",
direct, single, dbl, triple);
double gib = (double)blocks * B / (1L << 30);
printf(" = %ld blocks = %.1f GiB (%.2f TiB)\n", blocks, gib, gib / 1024);
}
}
block 1024 B: 256 pointers per block
direct 12 + single 256 + double 65536 + triple 16777216
= 16843020 blocks = 16.1 GiB (0.02 TiB)
block 4096 B: 1024 pointers per block
direct 12 + single 1024 + double 1048576 + triple 1073741824
= 1074791436 blocks = 4100.0 GiB (4.00 TiB)
Max blocks = 12 + p + p² + p³; max size = max blocks × block size. The 4 KB result, 1,074,791,436 blocks, matches the kernel documentation's last triple-indirect block number above. Real limits can be lower: the documentation notes the map "cannot be placed higher than 2^32 blocks" (block numbers are 32 bits), and the size field in the inode has its own limit.
Max file size by hand
block = 1 KB, pointer = 4 bytes → p = 1024 / 4 = 256
max blocks = 12 + 256 + 256² + 256³
= 12 + 256 + 65,536 + 16,777,216 = 16,843,020
max size = 16,843,020 × 1 KB = 16,843,020 KB ≈ 16 GB
Tips: compute p first; for a quick estimate the triple term dominates (≈ p³ × block size); questions sometimes change the number of direct pointers or leave out the triple pointer, so read carefully.
Live: which pointer holds byte x?
#include <stdio.h>
// Which inode pointer holds byte x? (4 KB blocks, 4-byte pointers)
void where(long x) {
long B = 4096, p = B / 4, blk = x / B; // file block number
printf("byte %11ld -> file block %7ld -> ", x, blk);
if (blk < 12) { printf("direct pointer %ld\n", blk); return; }
blk -= 12;
if (blk < p) { printf("single indirect, entry %ld\n", blk); return; }
blk -= p;
if (blk < p * p) {
printf("double indirect, entries %ld, %ld\n", blk / p, blk % p); return;
}
blk -= p * p;
printf("triple indirect\n");
}
int main(void) {
where(40000); // inside the first 48 KB
where(100000);
where(10000000);
where(5000000000L);
}
byte 40000 -> file block 9 -> direct pointer 9
byte 100000 -> file block 24 -> single indirect, entry 12
byte 10000000 -> file block 2441 -> double indirect, entries 1, 381
byte 5000000000 -> file block 1220703 -> triple indirect
Method: file block = x / block size. If < 12 → direct. Subtract 12; if < p → single indirect, entry = that value. Subtract p; if < p² → double indirect, outer entry = value / p, inner entry = value % p. Otherwise triple indirect. Each indirect level costs one extra block read (unless cached) before the data block.
| Range of file blocks (4 KB blocks, p = 1024) | Pointer | Extra reads |
|---|---|---|
| 0 - 11 (first 48 KB) | direct | 0 |
| 12 - 1035 (up to about 4 MB) | single indirect | 1 |
| 1036 - 1,049,611 (up to about 4 GB) | double indirect | 2 |
| 1,049,612 - 1,074,791,436 (up to about 4 TB) | triple indirect | 3 |
Live: a sparse file
#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/stat.h>
int main(void) {
int fd = open("big.dat", O_WRONLY | O_CREAT | O_TRUNC, 0644);
lseek(fd, 1L << 30, SEEK_SET); // jump 1 GiB ahead
write(fd, "!", 1); // write ONE byte there
close(fd);
struct stat s; stat("big.dat", &s);
printf("file size : %ld bytes (about 1 GiB)\n", (long)s.st_size);
printf("really on disk : %ld KB\n", (long)s.st_blocks * 512 / 1024);
}
file size : 1073741825 bytes (about 1 GiB)
really on disk : 4 KB
Indexed allocation only needs pointers for blocks that were written. The 1 GiB of blocks we skipped simply have no pointer (an empty slot), so they use no disk space. This is a sparse file (a file with holes); reading a hole returns zero bytes.
Comparing the three methods
| Contiguous | Linked (and FAT) | Indexed (inode) | |
|---|---|---|---|
| Directory/inode stores | start, length | first block | index block / pointers |
| Sequential access | best | good | good |
| Direct access | best (start + k) | slow (walk k steps; FAT: in RAM) | fast (1-4 lookups) |
| External fragmentation | yes | no | no |
| File growth | hard | easy | easy |
| Space overhead | none | a pointer per block (or the FAT) | index blocks |
| One bad block | loses one block | loses the rest of the file | loses what it points to |
Free-space management
To create or grow a file the OS needs free blocks. Four ways to track them:
- Bitmap (bit vector): one bit per block, 1 = free, 0 = used (some books use the opposite). Size = number of blocks / 8 bytes: a 1 TB disk with 4 KB blocks has 2⁴⁰ / 2¹² = 2²⁸ blocks → 2²⁸ bits = 32 MB. Finding a free block is fast with word-at-a-time tricks, and finding runs of free blocks (for contiguous files) is easy.
- Free list (linked list): each free block stores the number of the next free block; the OS keeps a pointer to the first. No extra space, but finding many free blocks means reading each one from disk.
- Grouping: the first free block stores the numbers of n free blocks; the last of those stores the next n, and so on. A whole batch of free block numbers comes from one disk read.
- Counting: free blocks often come in runs, so store (first free block, how many follow in a row) pairs. Short when space is in big runs.
Live: a bitmap and the counting form
#include <stdio.h>
// Free-space bitmap: bit i = 1 means block i is free (16 blocks here)
int main(void) {
unsigned short map = 0; // all used
int freeb[] = {3, 4, 5, 9, 13, 14};
for (int i = 0; i < 6; i++) map |= 1u << freeb[i];
printf("bitmap (block 0 on the left): ");
for (int i = 0; i < 16; i++) printf("%d", (map >> i) & 1);
int first = __builtin_ctz(map); // lowest set bit
printf("\nfirst free block: %d\n", first);
map &= ~(1u << first); // allocate it
printf("after allocating it, first free: %d\n", __builtin_ctz(map));
printf("counting form:"); // (start, length) pairs
for (int i = 0; i < 16; ) {
if (!((map >> i) & 1)) { i++; continue; }
int s = i; while (i < 16 && ((map >> i) & 1)) i++;
printf(" (%d,%d)", s, i - s);
}
printf("\n");
}
bitmap (block 0 on the left): 0001110001000110
first free block: 3
after allocating it, first free: 4
counting form: (4,2) (9,1) (13,2)
map |= 1u << bsets bit b (marks block b free);map &= ~(1u << b)clears it (allocates block b).__builtin_ctz(x)is a gcc built-in that counts trailing zeros: the position of the lowest 1 bit, i.e. the first free block. Most CPUs do it in one instruction, which is why bitmaps are fast to search. (It's undefined for x = 0, so real code checks for "no free block" first.)- Counting form:
(4,2) (9,1) (13,2)= blocks 4-5, 9 and 13-14.
What real file systems do
- ext4 (the usual Linux file system) replaced the block map with extents: an extent is a run, (first block, length), like the counting method. The kernel documentation says "the maximum length of a initialized extent is 32768 blocks", and the inode's 60-byte block area holds a header plus four extents directly; bigger files use an extent tree (at most 5 levels). A well-laid-out large file needs only a few extents instead of thousands of pointers.
- NTFS (Windows) keeps a master file table (MFT). Microsoft's documentation: "The master file table (MFT) stores the information required to retrieve files from an NTFS partition", and "A file may have one or more MFT records". The first 16 records are reserved for special files, including record 6, the volume cluster allocation file ($Bitmap), which tracks free space as a bitmap.
- FAT32 / exFAT: the FAT chain (removable media).
VFS: one interface for many file systems
A laptop may have ext4 on its disk and exFAT on a pen drive, mounted in one tree, yet programs call the same open, read, write. The virtual file system (VFS) is a common layer in the kernel: it defines the operations (open, read, write, lookup, ...) and each file system plugs in its own code for them. VFS also keeps the in-memory objects the kernel uses for open files and directory entries. Like a universal charger with different tips.
Crash consistency: fsck and journaling
Creating a file changes several blocks: the free-space bitmap, the inode, and the directory. If the power fails after only some of them are written, the file system is inconsistent: a block marked used that no file owns (leaked space), or an inode that points to a block still marked free (two files may later share it).
- fsck (file system check): after a crash, scan the whole file system and repair inconsistencies. Correct, but slow on a big disk (it reads all metadata).
- Journaling: before changing the real metadata, write a description of the changes to a log on disk, the journal. Steps: 1. write the changes (a transaction) to the journal; 2. write a commit record that says the transaction is complete; 3. write the changes to their real places (checkpoint); 4. free that part of the journal.
- After a crash: a transaction without a commit record is ignored (as if it never happened); one with a commit record is replayed. Recovery takes seconds, not a full scan.
The Linux kernel documentation says ext4 "employs a journal to protect the filesystem against metadata inconsistencies in the case of a system crash", with three modes: data=journal (all data and metadata through the journal, "slower but safest"), data=ordered (the default: only metadata goes through the journal) and data=writeback (weakest guarantees).
The story: the shopkeeper's rough book
Before updating the main ledger, the shopkeeper notes the change in a rough book: "Ravi paid 500, add it to his account". If the power fails halfway, the rough book says exactly what to finish.
The buffer cache and page cache
The OS keeps recently used disk blocks in RAM: the buffer cache, on Linux today the page cache (file data cached in page-sized pieces). The second read of a file comes from RAM. Writes usually go into the cache and reach the disk later (write-back), so write() can return before the data is on disk. A program that must not lose data calls fsync(fd), which waits until that file's data is really on disk. This is also why you eject a pen drive before pulling it out.
The whole chain
| Problem | Invention |
|---|---|
| Which blocks hold a file? | allocation methods |
| Blocks in a row | contiguous: fast, but external fragmentation, can't grow |
| Use any block | linked allocation: slow jumps, fragile chain |
| Chain pointers in one place | FAT |
| Fast jumps | indexed allocation, index block |
| Huge files | multilevel index, the inode (12 + p + p² + p³) |
| Which blocks are free? | bitmap, free list, grouping, counting |
| Fewer pointers for big files | ext4 extents |
| Many file systems, one API | VFS |
| Power cut mid-update | fsck, journaling |
| Disk is slow | buffer / page cache, fsync |
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| Using p = block size | a max size thousands of times too big | a block holds block size / pointer size pointers | p = 4096 / 4 = 1024 first |
| Forgetting the 12 direct blocks | answer off by 12 blocks | direct pointers count | 12 + p + p² + p³ |
| Mixing KB and KiB, GB and GiB | answers that look slightly off | 1 KB here means 1024 bytes | say which you use; textbooks use 1 KB = 1024 B |
| "Linked allocation has external fragmentation" | wrong theory answer | any free block can be used | only contiguous suffers it |
| "FAT is slow because the pointers are on disk" | wrong theory answer | the FAT is cached in RAM | the cost is walking k entries |
Assuming data is on disk after write() |
data lost after a power cut | it may still be in the page cache | fsync(fd) |
__builtin_ctz(0) on a full bitmap |
an undefined, garbage result | no bit is set | check map != 0 first |
Mini project: a toy file system
In one C program, simulate a 64-block disk:
- a bitmap for free blocks;
- an inode table where each inode has 4 direct pointers and 1 single-indirect pointer (a block holding up to 8 block numbers);
- functions
create(name),append(name, nbytes)(allocating blocks as needed),read_block(name, k)(printing which pointer was used), anddelete(name)(freeing blocks); - print the bitmap after every operation, and the maximum file size of your design.
Then add a journal: before each append, write the planned bitmap and inode changes to a log array with a commit flag, and add a crash_and_recover() that replays committed entries only.
Practice
1. Max file size: 8 KB blocks, 8-byte pointers, 12 direct + 1 single + 1 double + 1 triple indirect.
Solution
p = 8192 / 8 = 1024. Max blocks = 12 + 1024 + 1024² + 1024³ = 1,074,791,436 blocks. Size = 1,074,791,436 × 8 KB = 8,804,691,443,712 bytes ≈ 8 TiB. (Same block count as 4 KB blocks with 4-byte pointers, but each block is twice as big.)
2. Which pointer holds byte 60,000 (4 KB blocks, 4-byte pointers, 12 direct pointers)?
Solution
60,000 / 4096 = file block 14 (integer division). 14 ≥ 12, so subtract 12: 2 < 1024 → single indirect, entry 2. One extra block read.
3. Bitmap size for a 2 TB disk with 4 KB blocks.
Solution
2 TB = 2⁴¹ bytes; blocks = 2⁴¹ / 2¹² = 2²⁹ = 536,870,912 blocks → 2²⁹ bits = 2²⁶ bytes = 64 MB.
4. Why can reaching block 1000 of a FAT file be slow, and why is it still faster than plain linked allocation?
Solution
The FAT is a chain: to find block 1000 you follow 1000 entries from the first block. But the table is cached in RAM, so that's 1000 memory reads; plain linked allocation keeps the pointers inside the data blocks, so it would need 1000 disk reads.
5. Disk of 20 blocks: AAAA...CCCCC..EEEE.. (dots free). With contiguous first fit, can a 3-block file fit? A 4-block file?
Solution
Free runs: blocks 4-6 (3 blocks), 12-13 (2), 18-19 (2). A 3-block file fits at blocks 4-6. A 4-block file fails, although 7 blocks are free: external fragmentation.
6. A crash happens after the journal's commit record was written but before the checkpoint. What does recovery do? And if the crash happens before the commit record?
Solution
After commit: the transaction is complete in the journal, so recovery replays it (writes the changes to their real places). Before commit: the transaction is incomplete, so it is ignored; the real metadata was never touched, so the file system is still consistent (the operation simply didn't happen).
Quick quiz
block size = 2 KB
pointer size = 4 bytes
10 direct pointers + 1 single indirect
// max file size?
A. 1 MB + 20 KB B. 512 KB C. 2 MB D. 532 KB
Answer
A. p = 2048 / 4 = 512. Blocks = 10 + 512 = 522. Size = 522 × 2 KB = 1044 KB = 1024 KB + 20 KB = 1 MB + 20 KB.
Interview questions
- Compare contiguous, linked and indexed allocation. Contiguous: fast access, external fragmentation, hard growth. Linked: no fragmentation, easy growth, slow direct access, fragile. Indexed: fast direct access, no fragmentation, index overhead.
- What is the FAT? A table with one entry per disk block holding the next block of the same file (or EOF/free), cached in RAM; used by FAT32 and exFAT.
- Describe the Unix inode's block pointers. 12 direct, one single, one double and one triple indirect pointer.
- Compute the maximum file size for 4 KB blocks and 4-byte pointers. p = 1024; 12 + 1024 + 1024² + 1024³ = 1,074,791,436 blocks ≈ 4 TiB.
- What is a sparse file? A file with unallocated holes; size larger than the space used; holes read as zeros.
- How is free space managed? Bitmap, free linked list, grouping, counting (and extents / allocation groups in real systems).
- Bitmap vs free list? Bitmap: small, fast to find (runs of) free blocks, needs memory; free list: no extra space, slow to find many blocks.
- What are extents? (start block, length) runs that describe contiguous pieces of a file; ext4 uses them.
- What is the VFS? A kernel layer giving one interface (open, read, write, ...) over many file systems.
- What is journaling and why is it better than fsck? Write intended metadata changes to a log and commit before applying them; after a crash only the journal is replayed, instead of scanning the whole disk.
- What are ext4's journaling modes? data=journal, data=ordered (default; metadata only), data=writeback.
- What is the page cache? Why call fsync? RAM copies of file data; writes may sit there, so fsync forces them to disk.
Glossary
| Term | Meaning in plain words | Example |
|---|---|---|
| Block | A fixed-size piece of the disk | 4 KB |
| Allocation method | How a file's blocks are chosen and recorded | contiguous, linked, indexed |
| Contiguous allocation | A file gets consecutive blocks; store start and length | A = blocks 0-3 |
| First fit | Take the first free gap that is big enough | alloc |
| External fragmentation | Free space split into gaps too small to use | 7 free, no 5 in a row |
| Compaction | Moving files together to merge free gaps | defragmentation |
| Internal fragmentation | Unused space inside an allocated block or cluster | half-empty last block |
| Linked allocation | Each block stores the next block's number | treasure hunt |
| Cluster | A group of blocks allocated together | 4 blocks |
| FAT (File Allocation Table) | One table entry per block = the next block of the file | 9 → 16 → 1 → 10 → 25 |
| EOF marker | Special value meaning "last block of the file" | EOFB |
| exFAT / FAT32 | FAT-based file systems for removable media | SD cards |
| Indexed allocation | All of a file's block numbers in one index block | contents page |
| Index block | A block holding a file's block numbers | 1024 entries |
| Multilevel index | An index of index blocks | two levels → 4 GB |
| Inode | The Unix record of a file, with 15 block pointers | ext2/ext3 |
| Direct pointer | Holds a data block's number | first 48 KB |
| Single / double / triple indirect | Points to 1, 2 or 3 levels of pointer blocks | p, p², p³ blocks |
| p (pointers per block) | block size / pointer size | 4096 / 4 = 1024 |
| Sparse file | A file with unallocated holes | 1 GiB size, 4 KB on disk |
| Hole | A never-written region with no blocks; reads as zeros | the skipped 1 GiB |
| Free-space management | Tracking which blocks are free | bitmap |
| Bitmap (bit vector) | One bit per block: 1 = free | 0001110001000110 |
| Free list | Free blocks linked into a chain | head → 3 → 4 → ... |
| Grouping | A free block lists n free blocks; the last lists more | batches |
| Counting | (first free block, count) pairs | (4,2) (9,1) (13,2) |
__builtin_ctz |
gcc built-in: position of the lowest 1 bit | first free block 3 |
| Extent | A run of contiguous blocks: (start, length) | ext4, up to 32,768 blocks |
| ext4 | The usual Linux file system | extents, journal |
| NTFS | The Windows file system | MFT |
| MFT (master file table) | NTFS's table of file records | record 6 = $Bitmap |
| VFS (virtual file system) | Kernel layer giving one API over many file systems | ext4 + exFAT |
| Inconsistent file system | Metadata that disagrees after a crash | leaked block |
| fsck | Scan the whole file system and repair it | after a crash, no journal |
| Journaling | Log planned metadata changes, commit, then apply | ext4 |
| Journal | The on-disk log of planned changes | jbd2 |
| Transaction | A group of changes applied all-or-nothing | create a file |
| Commit record | Marks a journal transaction as complete | "complete" |
| Checkpoint | Writing journaled changes to their real places | step 3 |
| Replay | Re-applying committed journal transactions after a crash | recovery |
| data=ordered | ext4's default: journal metadata only | |
| Buffer cache / page cache | RAM copies of recently used disk data | second read is fast |
| Write-back | Writes go to the cache first, to disk later | write() returns early |
| fsync | Wait until a file's data is on disk | databases |
Summary
- Contiguous allocation (start + length) is the fastest but suffers external fragmentation and can't grow (live: 7 free blocks, a 5-block file failed).
- Linked allocation uses any block but jumps slowly; the FAT moves the chain into a RAM-cached table (live: 9 → 16 → 1 → 10 → 25; block 3 = 3 steps). exFAT is optimized for USB drives and SD cards.
- Indexed allocation lists the blocks in an index block; big files use multilevel indexes; the Unix inode combines 12 direct + single + double + triple indirect pointers: max blocks = 12 + p + p² + p³ (live: 16 GiB with 1 KB blocks, 4 TiB with 4 KB blocks, matching the kernel docs). Skipped blocks make sparse files (live: 1 GiB file, 4 KB on disk).
- Free space is tracked with a bitmap, free list, grouping or counting (live: first free block via
__builtin_ctz; counting form (4,2) (9,1) (13,2)). - ext4 uses extents, NTFS the MFT; VFS gives one API; journaling replaces slow fsck scans (ext4 default: data=ordered); the page cache speeds reads, and fsync forces data to disk.
Next episode: Disk structure, disk scheduling and RAID: tracks, sectors, seek time and rotational latency, FCFS, SSTF, SCAN, LOOK numericals, RAID levels and SSDs.