SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 36
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

CS Fundamentals for Placements · Lesson 36 of 90

File systems 2: allocation methods and free-space management

contiguous allocationlinked allocationFATindexed allocationmultilevel indexUnix inode with directsingledouble and triple indirect blocksmaximum file size numericalsfree-space management (bitmap, linked list, grouping, counting)virtual file system (VFS)journaling file systemext4NTFS

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
  • alloc uses 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:

  1. Linked scheme: the last entry of an index block points to the next index block.
  2. 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).
  3. 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:

  1. 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.
  2. 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.
  3. 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.
  4. 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 << b sets 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:

  1. a bitmap for free blocks;
  2. an inode table where each inode has 4 direct pointers and 1 single-indirect pointer (a block holding up to 8 block numbers);
  3. functions create(name), append(name, nbytes) (allocating blocks as needed), read_block(name, k) (printing which pointer was used), and delete(name) (freeing blocks);
  4. 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

  1. 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.
  2. 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.
  3. Describe the Unix inode's block pointers. 12 direct, one single, one double and one triple indirect pointer.
  4. 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.
  5. What is a sparse file? A file with unallocated holes; size larger than the space used; holes read as zeros.
  6. How is free space managed? Bitmap, free linked list, grouping, counting (and extents / allocation groups in real systems).
  7. 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.
  8. What are extents? (start block, length) runs that describe contiguous pieces of a file; ext4 uses them.
  9. What is the VFS? A kernel layer giving one interface (open, read, write, ...) over many file systems.
  10. 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.
  11. What are ext4's journaling modes? data=journal, data=ordered (default; metadata only), data=writeback.
  12. 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.