Allocation Methods, Inodes & Journaling

By the end of this lesson you will be able to compare contiguous, linked and indexed allocation, calculate the largest file an inode can describe, and explain how a journal keeps a file system consistent after a power cut.

A disk or SSD is just a long row of numbered blocks, typically 4 KB each. The file system decides which blocks belong to which file and keeps track of the free ones. There are three classic ways to do it, and real file systems mix their ideas.

Contiguous allocation

Each file occupies one run of consecutive blocks. The directory entry stores only the start block and the length.

• Good: very fast, both for reading in order and for jumping to block n (it is simply start + n).
• Bad: the same external fragmentation you met with memory. Files also cannot grow easily if the next block is taken.

It is like booking a row of seats together in a cinema. Easy to find your group, but a big group may not fit even when many single seats are free. CD-ROM and DVD file systems used contiguous allocation because files there never change.

Linked allocation and the FAT

Each block holds a pointer to the next block of the file. The directory stores the first block, and you follow the chain like a treasure hunt where each clue tells you where the next one is hidden.

• Good: no external fragmentation; any free block can be used, and files grow easily.
• Bad: reaching block 500 means following 499 pointers. One damaged pointer loses the rest of the file.

The File Allocation Table (FAT) moves all the "next block" pointers out of the data blocks into one table at the start of the disk. The table is small enough to cache in RAM, so following a chain is fast. FAT32 and exFAT, used on pen drives and SD cards, work this way.

Step 1: run this tiny FAT disk. It writes two files, deletes one, then writes a longer file that has to use scattered blocks.

# A tiny FAT-style disk: fat[i] says which block comes after block i (-1 = end of file)
DISK_BLOCKS = 16
fat = [None] * DISK_BLOCKS            # None = free block
data = [""] * DISK_BLOCKS
directory = {}                        # file name -> first block

def write_file(name, chunks):
    free = [i for i in range(DISK_BLOCKS) if fat[i] is None][:len(chunks)]
    for this, nxt, chunk in zip(free, free[1:] + [-1], chunks):
        fat[this], data[this] = nxt, chunk
    directory[name] = free[0]
    print(f"{name}: blocks {free}")

def read_file(name):
    block, out = directory[name], []
    while block != -1:                 # follow the chain
        out.append(data[block]); block = fat[block]
    return "".join(out)

def delete_file(name):
    block = directory.pop(name)
    while block != -1:                 # walk the chain, freeing each block
        nxt = fat[block]
        fat[block] = None
        block = nxt
    print(f"{name}: deleted")

write_file("a.txt", ["Na", "ma", "st"])
write_file("b.txt", ["Ko", "ch", "i!"])
delete_file("a.txt")
write_file("c.txt", ["Pu", "ne", " R", "oh", "ta", "k"])
print("c.txt reads:", read_file("c.txt"))
print("FAT:", fat[:10])

a.txt: blocks [0, 1, 2]
b.txt: blocks [3, 4, 5]
a.txt: deleted
c.txt: blocks [0, 1, 2, 6, 7, 8]
c.txt reads: Pune Rohtak
FAT: [1, 2, 6, 4, 5, -1, 7, 8, -1, None]

Step 2: follow c.txt through the FAT by hand: block 0 says "next is 1", 1 says 2, 2 jumps over b.txt to 6, then 7, then 8, which says -1 (end). The file is in two pieces, and nothing was wasted.

Indexed allocation and inodes

Indexed allocation gives each file an index block: a list of all its block numbers, like a book's table of contents. To reach block n, read entry n of the index. Random access is fast and there is no external fragmentation. The cost is the extra index block, even for tiny files.

Unix and Linux file systems use a clever version called the inode (index node). Each file has one inode that stores its attributes (owner, permissions, size, timestamps, link count) and its block pointers. The file name is not in the inode; it lives in the directory entry, which maps a name to an inode number. That is exactly why hard links work.

A classic inode has:

• 12 direct pointers to data blocks (enough for small files).
• 1 single indirect pointer: to a block full of pointers to data blocks.
• 1 double indirect pointer: to a block of pointers to blocks of pointers.
• 1 triple indirect pointer: one more level.

Small files need no extra reads; huge files are still possible.

def max_file_size(block, pointer, direct=12):
    p = block // pointer                         # pointers that fit in one block
    blocks = direct + p + p**2 + p**3            # direct + single + double + triple indirect
    return p, blocks, blocks * block

for block, pointer, direct in [(4096, 4, 12), (1024, 4, 10)]:
    p, blocks, size = max_file_size(block, pointer, direct)
    print(f"block {block} B, {pointer}-byte pointers, {direct} direct:")
    print(f"  {p} pointers per block, {blocks:,} data blocks, max size {size:,} bytes"
          f" (about {size / 2**30:.1f} GiB)")

block 4096 B, 4-byte pointers, 12 direct:
  1024 pointers per block, 1,074,791,436 data blocks, max size 4,402,345,721,856 bytes (about 4100.0 GiB)
block 1024 B, 4-byte pointers, 10 direct:
  256 pointers per block, 16,843,018 data blocks, max size 17,247,250,432 bytes (about 16.1 GiB)

This is a favourite GATE calculation. The triple indirect part dominates: p^3 blocks. Remember that real file systems may also limit file size in other ways, so this number is the limit of the pointer scheme only.

Modern ext4 replaced long lists of block pointers with extents: each entry says "start at block 20,000 and use the next 3,000 blocks". One extent can describe a large contiguous region, so big files need far less metadata. NTFS keeps similar run lists in its Master File Table (MFT), which has one record per file.

Comparing the three methods

Tracking free space

The file system also needs to know which blocks are free.

• Bitmap: one bit per block, 1 for used and 0 for free (or the reverse). Compact and easy to search for runs of free blocks. ext4 uses block bitmaps.
• Free list: link all free blocks together. No extra space needed, but finding many contiguous free blocks is slow.
• Grouping and counting: store "the next n blocks starting at b are free", which is compact when free space comes in runs.

A 1 TB disk with 4 KB blocks has about 244 million blocks, so its bitmap needs about 30 MB.

Journaling: surviving a power cut

Creating one file changes several places on disk: the free-space bitmap, the inode and the directory. If power fails between these writes, the file system can be left inconsistent, for example with a block marked used that no file owns. Old systems fixed this with a slow full scan (fsck on Linux, chkdsk on Windows).

A journaling file system writes its intended changes to a special area, the journal, first. Only after a commit record is safely in the journal does it update the real locations. After a crash it replays committed transactions and ignores incomplete ones. This idea is called write-ahead logging.

disk = {"bitmap": "free", "inode": "empty", "dir": "no entry"}
journal = []

def transaction(updates, crash_before_commit=False):
    journal.append(("begin", None))
    for key, value in updates.items():
        journal.append(("write", (key, value)))     # 1. write intentions to the journal
    if crash_before_commit:
        print("CRASH before commit!")
        return
    journal.append(("commit", None))                # 2. commit record
    for key, value in updates.items():              # 3. now update the real places
        disk[key] = value

def recover():
    pending, committed = [], []
    for kind, item in journal:                      # replay only committed transactions
        if kind == "begin": pending = []
        elif kind == "write": pending.append(item)
        elif kind == "commit": committed += pending
    for key, value in committed:
        disk[key] = value
    print("recovery replayed", len(committed), "writes; incomplete transaction ignored")

transaction({"bitmap": "block 9 used", "inode": "size 4 KB", "dir": "photo.jpg"})
print("after first file:", disk)
transaction({"bitmap": "block 10 used", "inode": "size 8 KB", "dir": "video.mp4"}, crash_before_commit=True)
recover()
print("after recovery:  ", disk)

after first file: {'bitmap': 'block 9 used', 'inode': 'size 4 KB', 'dir': 'photo.jpg'}
CRASH before commit!
recovery replayed 3 writes; incomplete transaction ignored
after recovery:   {'bitmap': 'block 9 used', 'inode': 'size 4 KB', 'dir': 'photo.jpg'}

The half-finished video file simply never happened, and the disk stays consistent. Recovery takes seconds instead of a full scan.

ext4 journals metadata by default (its "ordered" mode also makes sure file data reaches the disk before the metadata that points to it). NTFS keeps a log file for its metadata changes too. A different approach is copy-on-write file systems such as Btrfs, ZFS and APFS: they never overwrite live data, but write new versions elsewhere and then switch one pointer, which also makes cheap snapshots possible.

Common mistakes

• Saying the inode stores the file name. Names live in directory entries; the inode holds attributes and block pointers.
• Forgetting the direct pointers in size questions. Add direct + single + double + triple indirect blocks.
• Thinking journaling protects your data from deletion. It protects the file system's consistency after a crash, not against mistakes; you still need backups.

Key points

• Contiguous allocation is fast but fragments; linked allocation (FAT) avoids fragmentation but is slow for random access.
• Indexed allocation keeps a list of a file's blocks; Unix inodes use direct, single, double and triple indirect pointers.
• Max blocks per inode = direct + p + p^2 + p^3, where p = block size / pointer size.
• ext4 uses extents; NTFS uses the Master File Table.
• Free space is tracked with bitmaps, free lists or run counts.
• Journaling writes changes to a log first, so recovery after a crash replays only committed work.

p, blocks, size = max_file_size(2048, 8, direct=8)
print(p, f"{blocks:,}", f"{size / 2**30:.1f} GiB")
print("blocks for 100 KB:", -(-100 * 1024 // 2048))

256 16,843,016 32.1 GiB
blocks for 100 KB: 50