File System Abstraction

The previous three lessons measured memory, and in all three, data vanished once the run ended. When a virtual page was evicted its content could be fetched back, but when the process terminated the address space disappeared entirely. Most of the data produced, though, has to outlive the run, and that requires a second abstraction: an arrangement where bytes are named, names are placed in a hierarchy, and content is split into fixed-size blocks.

This lesson models that arrangement and counts two of its costs. Commands for creating files, granting permissions, and navigating directories have already been used throughout this catalog; no command is taught here. What is measured is the mechanism — how many steps it takes to turn a byte into a block, a name into a number.

Three Separate Objects

The abstraction separates three objects from one another, and the separation itself is a design decision.

A file is a sequential byte sequence and has no name on its own. An inode carries everything about a file except its name: its size, permissions, timestamps, and the block list that says which blocks hold its content. A directory is itself a file; its content is a table mapping names to inode numbers.

The name living in the directory rather than the file produces two consequences. The same inode can be pointed to by more than one directory entry, meaning a file can have more than one name. And deleting a name is not the same as deleting the file — the file disappears only once the last entry pointing to it is also gone.

• BD19 — Six files come from the common definition: 120, 700, 1500, 40, 2048, and 333 bytes, totaling 4741 bytes. The default block size is 512 bytes.
• BD20 — An inode carries 8 direct block pointers. A file needing more blocks keeps their numbers in an indirect block; a block pointer is 4 bytes, so an indirect block carries block / 4 pointers.
• BD21 — The indirect block is single-level. None of the files in this model exceed a single level’s capacity.
• BD22 — One read step per block; looking up a pointer in the indirect block adds one more read. The disk’s own latency is not counted in this lesson.

"""M01/K05 common definition (excerpt): inode , block and internal fragmentation."""
BLOCK = 512
FILE = [120, 700, 1500, 40, 2048, 333]
DIRECT = 8            # direct block pointers an inode carries
POINTER = 4            # bytes per block pointer


def inode(sizes, block=BLOCK):
    used = sum(-(-b // block) for b in sizes)
    return {"files": len(sizes), "bytes": sum(sizes), "blocks": used,
            "internal_fragmentation": used * block - sum(sizes)}


def indirect(sizes, block):
    """Extra indirect blocks and read steps needed for blocks that exceed the direct pointers."""
    extra, reads = 0, 0
    for b in sizes:
        data = -(-b // block)
        reads += data
        if data > DIRECT:
            extra += -(-(data - DIRECT) // (block // POINTER))
            reads += data - DIRECT          # each indirect pointer is one more read
    return extra, reads


print("common definition:", inode(FILE))
print()
print("block  data blocks  indirect  total blocks  disk bytes  int. frag.  read steps")
for block in (64, 128, 256, 512, 1024, 4096):
    d = inode(FILE, block)
    extra, reads = indirect(FILE, block)
    total = d["blocks"] + extra
    print(f"{block:4d}  {d['blocks']:11d}  {extra:8d}  {total:12d}  {total * block:10d}"
          f"  {d['internal_fragmentation']:11d}  {reads:10d}")

common definition: {'files': 6, 'bytes': 4741, 'blocks': 12, 'internal_fragmentation': 1403}

block  data blocks  indirect  total blocks  disk bytes  int. frag.  read steps
  64           76         4            80        5120          123         119
 128           39         2            41        5248          251          51
 256           21         0            21        5376          635          21
 512           12         0            12        6144         1403          12
1024            8         0             8        8192         3451           8
4096            6         0             6       24576        19835           6

Three numbers sit side by side. Baseline: the content of six files is 4741 bytes, and laid out contiguously it would hold 4741 bytes on disk; the inode would carry a single start address and a length. Setup: 512-byte blocks, 12 blocks, 6144 bytes on disk. Cost: 1403 bytes of internal fragmentation — 22.8 percent of what is written to disk carries no data at all — and 12 block pointers in the inode instead of a single pair.

Why contiguous placement was abandoned can be read from the previous lesson. A file growing requires the bytes behind it to be free, and when they are not, the whole file must be moved. A block list removes that requirement: a new block gets appended to the list wherever it lands on disk. So internal fragmentation is the price paid to escape external fragmentation.

What Happens as the Block Shrinks

The table sweeps the block size, and two columns move in opposite directions.

Internal fragmentation shrinks with the block: 19,835 bytes at a 4096-byte block, 1403 at 512, only 123 bytes at 64. The reason is direct — every file’s last block wastes half a block on average, and for six files that is roughly three times the block size. As the block shrinks, so does the wasted share.

Read steps move the other way: 6 reads at a 4096-byte block, 12 at 512, 119 reads at 64. Reading the same 4741 bytes takes twenty times as many requests. Indirect blocks add to this: at 128 bytes and below, some files no longer fit within eight direct pointers, and part of the block list moves into a separate block. Looking up every pointer in that block is one extra read, which is why the read column jumps to 51 for 39 data blocks.

Total disk bytes do not move in a straight line either. At a 64-byte block, including indirect blocks, it is 5120 bytes; at 512, 6144 bytes; at 4096, 24,576 bytes. The smallest block uses space most efficiently and makes reads most expensive. Block size is a budget decision, not a correctness decision, and the budget’s two line items move in opposite directions.

Turning a Name into a Number

The name a program uses is a path; the name the file system uses is an inode number. The translation between the two is one directory read per path component.

• BD23 — Six files are spread across three directories; the names stand in for measurement and log data, and their sizes match the list above.
• BD24 — Reading one directory is one step; how many entries the directory carries does not change the step count.

"""Directory resolution: how many reads a name translates to."""
TREE = {                                   # directory -> name: (kind , inode number)
    "/":            {"measurement": ("D", 1), "log": ("D", 2)},
    "/measurement": {"raw.data": ("F", 10), "summary.data": ("F", 11), "old": ("D", 3)},
    "/measurement/old": {"history.data": ("F", 12)},
    "/log":         {"day.record": ("F", 13), "week.record": ("F", 14),
                      "month.record": ("F", 15)},
}
PATH = ["/measurement/raw.data", "/measurement/summary.data",
        "/measurement/old/history.data",
        "/log/day.record", "/log/week.record", "/log/month.record"]


def resolve(path):
    """Returns: inode number , read steps.
    Every path component reads one directory , the end reads one inode."""
    current, steps, no = "/", 0, None
    for part in path.strip("/").split("/"):
        steps += 1                          # directory carrying the component is read
        kind, no = TREE[current][part]
        if kind == "D":
            current = ("" if current == "/" else current) + "/" + part
    return no, steps + 1                    # inode read at the end


total = 0
for y in PATH:
    no, steps = resolve(y)
    total += steps
    print(f"{y:32s} inode {no:3d}  resolution steps {steps}")
print("total resolution steps for six files:", total)
print()
ACCESS = 20
y = "/measurement/old/history.data"
_, steps = resolve(y)
print(f"{y} , {ACCESS} accesses")
print("  re-resolving on every access:", ACCESS * steps, "steps")
print("  resolve once , then use a descriptor:", steps + ACCESS, "steps")

/measurement/raw.data            inode  10  resolution steps 3
/measurement/summary.data        inode  11  resolution steps 3
/measurement/old/history.data    inode  12  resolution steps 4
/log/day.record                  inode  13  resolution steps 3
/log/week.record                 inode  14  resolution steps 3
/log/month.record                inode  15  resolution steps 3
total resolution steps for six files: 19

/measurement/old/history.data , 20 accesses
  re-resolving on every access: 80 steps
  resolve once , then use a descriptor: 24 steps

Resolution steps grow linearly with path depth: a two-component path takes 3 steps, a three-component path takes 4. All six files together cost 19 steps, and none of that reads data — all of it is name lookup.

The last two lines show what a file descriptor buys. Twenty accesses to the same file, each resolving the path from scratch, cost 80 steps; resolving the path once and then using the resulting descriptor costs 24. A descriptor is a shortcut that caches the result of resolution and makes its cost payable once. It has a cost too: a descriptor holds an inode, not a name, so if the file is renamed or its name is deleted in between, it keeps reading the same content anyway.

One Update, Three Writes

Appending a block to a file is not a single write. The data block itself is written, that block is marked occupied in the block bitmap, and the inode’s size and block list are updated. Which state remains on disk if the machine halts between these three writes is the file system’s most expensive question.

• BD25 — One update carries three writes, and a crash can land between any two of them. Since write order depends on the implementation, all six orderings are counted.
• BD26 — The invariant is this: if an inode points to a block, that block must be marked occupied in the bitmap and its data written. A block that appears occupied in the bitmap but that no inode points to is an orphaned block — not inconsistent, but unrecoverable space.

"""Crash consistency: journal-less and journaled layouts , every crash point."""
from itertools import permutations

WRITE = ("data", "bitmap", "inode")        # data block , block bitmap , inode


def check(on_disk):
    """Invariant: if the inode points to the block , the bitmap must be occupied and data written."""
    consistent = ("inode" not in on_disk) or {"bitmap", "data"} <= on_disk
    orphaned = "bitmap" in on_disk and "inode" not in on_disk
    return consistent, orphaned


states = inconsistent = orphaned_count = 0
for order in permutations(WRITE):
    for k in range(len(WRITE) + 1):
        c, orphan = check(set(order[:k]))
        states += 1
        inconsistent += not c
        orphaned_count += orphan
print("journal-less: writes", len(WRITE), "| order x crash point", states,
      "| inconsistent", inconsistent, "| orphaned blocks", orphaned_count)

# Journaled layout: first to the journal , then a commit record , last in place.
STEP = [("to journal", a) for a in WRITE] + [("commit", None)] \
       + [("in place", a) for a in WRITE]
states = inconsistent = 0
for k in range(len(STEP) + 1):
    committed = ("commit", None) in STEP[:k]
    # recovery: if no commit , the journal is discarded (old state) , if committed , it is replayed
    on_disk = set(WRITE) if committed else set()
    c, _ = check(on_disk)
    states += 1
    inconsistent += not c
print("journaled:  writes", len(STEP), "| crash points", states,
      "| inconsistent", inconsistent, "| write multiplier", round(len(STEP) / len(WRITE), 2))

journal-less: writes 3 | order x crash point 24 | inconsistent 6 | orphaned blocks 4
journaled:  writes 7 | crash points 8 | inconsistent 0 | write multiplier 2.33

Six orderings times four crash points give 24 possible end states. 6 of these are inconsistent: the inode points to a block, but that block either appears free in the bitmap or has nothing written into it. In four of them there is an orphaned block — space is allocated, nothing points to it, and it cannot be reclaimed either. Only in 14 states is the disk sound.

A journaling file system drops this number to zero. The three writes go first to a separate journal area, then a single commit record is written, and only after that are the data applied in place. Recovery follows one rule: if there is no commit record, the journal is discarded and the disk stays in its old state; if there is one, the writes in the journal are replayed and the disk moves to its new state. All eight crash points fall into one of these two consistent states.

The cost is right there in the table: 7 writes instead of 3, that is, 2.33 times. Every byte goes to disk twice. Part of this is recoverable — a setup that journals only structures like the inode and the bitmap while writing data blocks directly lowers the multiplier, in exchange for bringing back the possibility of data loss. This trade-off between the disk staying sound and the amount written cannot be removed; only where it is placed can be chosen.

It is also worth noting what the journal does not remove. The journal keeps the on-disk structures consistent with one another at the moment of a crash; it does not prevent data being written from getting lost. An update that crashes before its commit record looks, after recovery, as if it never happened, and that is the correct outcome by definition. The gap between a program saying “I wrote it” and the data actually being on disk is a related but separate matter that falls outside this lesson’s model: a write request can be accepted while the byte is not yet on disk.

Summary

• A file is a sequential byte sequence, an inode carries everything about it besides its name along with the block list, and a directory is a table mapping a name to an inode number; a name is a property of the directory, not the file.
• The 4741 bytes of six files fit into 12 blocks of 512 bytes and take up 6144 bytes on disk; 1403 bytes, that is, 22.8 percent of what is written, is internal fragmentation.
• Sweeping the block size moves two costs in opposite directions: at a 64-byte block, internal fragmentation drops to 123 bytes but read steps climb to 119; at a 4096-byte block, reads drop to 6 but internal fragmentation climbs to 19,835 bytes.
• An inode carries eight direct pointers; as the block shrinks, some files exceed that limit and the block list moves into an indirect block, adding one more read per access.
• Translating a path name into an inode number is one directory read per path component; 20 accesses to the same file cost 80 steps if resolved every time, 24 steps if resolved once and then used through a descriptor.
• A single block append carries three writes; of the 24 states produced by six orderings and four crash points, 6 are inconsistent and 4 leave an orphaned block. A journaled layout drops this to zero, in exchange for raising the write count from 3 to 7, that is, 2.33 times.

Next Step

This lesson assumed reading a block is one step and never asked how long that step takes. Yet a disk request takes thirty times as long as one of the processor’s compute steps, and during that time the processor either waits, asks, or does other work. The course’s last lesson counts all three options on the same workload and ends on a surprising result: the model that keeps the processor one hundred percent busy does not finish its work any sooner at all.