Inodes and Metadata

The previous lesson counted the metadata ledger as a design axis: is it kept fixed, or does it grow as needed. This lesson takes the single record inside that ledger and shows that it is a resource — one that can be exhausted, and that produces a strange failure when it is.

The fictional server’s /data partition carries thirty thousand measurement files, and the partition’s usage is a bit over one percent. This lesson is going to try writing a new file to that partition, and the attempt is going to fail. The contradiction here is not a bug; it is two separate limits producing the same error message.

The Record an Inode Carries

An inode is the record that carries everything about a file except its name. The file system abstraction lesson in the Operating System Concepts course defined this record and showed that the name sits in the directory, not in the file; that definition is not repeated here. The only thing added here is what the operator can see.

The record is referred to by a number, and that number is unique within the file system. ls -i lists the number, stat opens the whole record, find can go back from a number to the file’s names. Among the record’s fields, the most often misread is the link count: how many directory entries point to this record. Once the link count drops to zero and no process is left holding the record open, the block list is released. Both conditions are required, and the second is the subject of this lesson’s second measurement.

The transcript below is a sample transcript showing the shape of stat’s output; it was not run, and no numeric claim in this lesson comes from it.

  File: /data/metrics/2f9c.data
  Size: 1731        Blocks: 8          IO Block: 4096   regular file
Device: 8,18        Inode: 1048604     Links: 1
Access: (0640/-rw-r-----)  Uid: (  997/ metrics)   Gid: (  997/ metrics)

In the transcript, Size and Blocks sit on separate lines and say two different things: the first is the byte count the file reports, the second is the space the file system actually allocated. This distinction will be the source of six wrong readings in the second measurement.

Two Limits, One Error Message

A file system consumes two separate resources. The first is blocks: where content is written. The second is inodes: one is needed per file, and in designs that keep a fixed table, the total count is fixed at format time. When either one runs out, a write is rejected with the same error message.

• ST14 — The shared definition’s file system carries 2,621,440 blocks and 32,768 inodes; a block is 4096 bytes. The numbers come from the model, not from any real device.
• ST15 — In the small-file workload, sizes range from 1 to 2000 bytes; every file holds one block. In the large-file workload, the upper bound is 2,000,000 bytes.
• ST16 — The warning rule looks at a 0.90 usage threshold. The rule is tested in three forms: block percentage only, inode percentage only, both together.
• ST17 — The diagnosis tested is a single question: can a new 1 KB file be written in this state.

"""M03/K03 shared definition (Section 6): two separate limits, one error message."""
SEED = 20260218
BLOCK = 4096


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def file_system(seed=SEED, files=30000, upper=2000,
                 inode_count=32768, block_count=2621440):
    r = generator(seed)
    sizes = [r(upper) + 1 for _ in range(files)]
    used_blocks = sum(-(-s // BLOCK) for s in sizes)
    return {"files": files, "used_blocks": used_blocks,
            "total_blocks": block_count,
            "block_usage": round(used_blocks / block_count, 4),
            "used_inodes": files, "total_inodes": inode_count,
            "inode_usage": round(files / inode_count, 4)}


def attempt_write(fs, size):
    """Can a new file be written. Two separate limits, one error message."""
    blocks_ok = fs["used_blocks"] + -(-size // BLOCK) <= fs["total_blocks"]
    inodes_ok = fs["used_inodes"] + 1 <= fs["total_inodes"]
    return blocks_ok and inodes_ok


for n in (30000, 32768):
    fs = file_system(files=n)
    print(f"{n:6d} files | block usage {fs['block_usage']:.4f}"
          f" | inode usage {fs['inode_usage']:.4f}"
          f" | new 1 KB file: {attempt_write(fs, 1024)}")
print()
SMALL = [(n, 2000) for n in (4096, 12288, 20480, 28672, 32000, 32768)]
LARGE = [(n, 2000000) for n in (2000, 4000, 6000, 8000, 10000, 12000)]
RULE = {"block percentage only": lambda f: f["block_usage"] < 0.90,
        "inode percentage only": lambda f: f["inode_usage"] < 0.90,
        "both together": lambda f: f["block_usage"] < 0.90
        and f["inode_usage"] < 0.90}

print("workload  files  block usage  inode usage  writable")
for name, load in (("small", SMALL), ("large", LARGE)):
    for n, upper in load:
        fs = file_system(files=n, upper=upper)
        print(f"{name:7s} {n:6d} {fs['block_usage']:13.4f} {fs['inode_usage']:14.4f}"
              f"  {attempt_write(fs, 1024)}")
print()
print("rule                    missed  false alarm  wrong diagnosis")
for name, k in RULE.items():
    missed = false_alarm = 0
    for _, load in (("small", SMALL), ("large", LARGE)):
        for n, upper in load:
            fs = file_system(files=n, upper=upper)
            safe, actual = k(fs), attempt_write(fs, 1024)
            missed += safe and not actual
            false_alarm += (not safe) and actual
    print(f"  {name:20s} {missed:9d}  {false_alarm:12d}  {missed + false_alarm:11d}")
print()
for seed in (SEED, 20260219):
    row = []
    for name, k in RULE.items():
        y = 0
        for _, load in (("small", SMALL), ("large", LARGE)):
            for n, upper in load:
                fs = file_system(seed, n, upper)
                y += k(fs) != attempt_write(fs, 1024)
        row.append(f"{name} {y}")
    print(f"seed {seed}: " + " | ".join(row) + " / 12")

 30000 files | block usage 0.0114 | inode usage 0.9155 | new 1 KB file: True
 32768 files | block usage 0.0125 | inode usage 1.0000 | new 1 KB file: False

workload  files  block usage  inode usage  writable
small     4096        0.0016         0.1250  True
small    12288        0.0047         0.3750  True
small    20480        0.0078         0.6250  True
small    28672        0.0109         0.8750  True
small    32000        0.0122         0.9766  True
small    32768        0.0125         1.0000  False
large     2000        0.1894         0.0610  True
large     4000        0.3693         0.1221  True
large     6000        0.5553         0.1831  True
large     8000        0.7416         0.2441  True
large    10000        0.9283         0.3052  True
large    12000        1.1168         0.3662  False

rule                    missed  false alarm  wrong diagnosis
  block percentage only         1             1            2
  inode percentage only         1             1            2
  both together                0             2            2

seed 20260218: block percentage only 2 | inode percentage only 2 | both together 2 / 12
seed 20260219: block percentage only 2 | inode percentage only 2 | both together 2 / 12

Three numbers side by side. The oracle: in the 32,768-file case, the inode table is completely full and 98.75 percent of the blocks are empty; the write fails. The tool’s output: the number that comes back when usage is asked is 0.0125 — one percent. Wrong diagnosis: the warning rule is mistaken in two of twelve cases, and these two mistakes are not eliminated by changing the rule.

The shared definition’s two lines are the course’s cleanest example. At thirty thousand files, block usage is 0.0114, inode usage is 0.9155, and the write succeeds; at 32,768 files, block usage is 0.0125, inode usage is 1.0000, and the write fails. The difference between them is 2768 files, and a thousandth of the total space. The disk is one percent full and the system is full.

The rule table pays off the second claim. The rule that looks only at the block percentage misses one failure and raises one false alarm. The rule that looks only at the inode percentage gives the same number — while blocks fill up in the large-file workload, the inode percentage stays at 0.3662. When both are used together, the missed count drops to zero, but the false alarm count rises to two, and the total is again 2. Adding a column changed the type of the wrong diagnosis, not its count. In the second seed, all three rules again give 2; the result depends not on the fiction but on the two limits being independent of each other.

The File With No Name

The second measurement counts the space allocated in the same file system using three separate methods. df reads the file system’s own ledger, du walks the directory tree and sums the blocks of the files it finds, and the total from a file listing sums the reported bytes. All three answer the same question, and the three do not give the same number.

• ST18 — Five moments pass in sequence: the start, giving 200 second names to the same files, writing 40 sparse files, deleting a 120,000-block log file, and closing the handle that kept that file open.
• ST19 — A second name given to the same inode is called a hard link. A sparse file reports a size of 25,600 blocks, and actually allocates 8. The space the metadata itself takes up is not counted in this measurement; the oracle is data blocks alone.

"""How many blocks are really allocated, and which tool sees how many."""
SEED = 20260218
BLOCK = 4096
FILES = 30000
SPARSE_COUNT = 40           # number of sparse files
SPARSE_LOGICAL = 25600      # reported size, in blocks
SPARSE_ALLOCATED = 8        # actually allocated blocks
LOG_BLOCKS = 120000         # large log file
HARD_LINKS = 200            # second names given to the same file


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def base(seed=SEED):
    r = generator(seed)
    return [r(2000) + 1 for _ in range(FILES)]


def state(moment, sizes):
    """moment 0..4 . Oracle: the data blocks the file system really allocated."""
    sparse = moment >= 2
    log_exists = moment < 4                  # deleted at moment 3, handle open
    allocated = FILES + LOG_BLOCKS * log_exists + SPARSE_COUNT * SPARSE_ALLOCATED * sparse
    # du: walks only NAMED files, counts a hard link once
    du = FILES + LOG_BLOCKS * (moment < 3) + SPARSE_COUNT * SPARSE_ALLOCATED * sparse
    # file-listing total: reported bytes, every NAME counted separately
    ls = sum(sizes) + sum(sizes[:HARD_LINKS]) * (moment >= 1)
    ls += LOG_BLOCKS * BLOCK * (moment < 3)
    ls += SPARSE_COUNT * SPARSE_LOGICAL * BLOCK * sparse
    return {"oracle": allocated, "df": allocated, "du": du, "ls": ls // BLOCK}


MOMENT = ("t0 start", "t1 hard link", "t2 sparse files",
          "t3 log deleted", "t4 handle closed")
SIZES = base()
print("moment               oracle       df       du       ls total")
for i, name in enumerate(MOMENT):
    d = state(i, SIZES)
    print(f"{name:18s} {d['oracle']:8d} {d['df']:8d} {d['du']:8d} {d['ls']:15d}")
print()
print("tool         correct reads  wrong reads")
for tool in ("df", "du", "ls"):
    wrong = sum(state(i, SIZES)[tool] != state(i, SIZES)["oracle"] for i in range(5))
    print(f"  {tool:9s} {5 - wrong:11d}  {wrong:12d}")
print("wrong diagnosis:", sum(state(i, SIZES)[a] != state(i, SIZES)["oracle"]
                              for i in range(5) for a in ("df", "du", "ls")), "/ 15")
print()
for seed in (SEED, 20260219):
    s = base(seed)
    print(f"seed {seed}: t0 oracle {state(0, s)['oracle']} ls {state(0, s)['ls']}"
          f" | t3 oracle {state(3, s)['oracle']} du {state(3, s)['du']}"
          f" | t4 oracle {state(4, s)['oracle']} ls {state(4, s)['ls']}")

moment               oracle       df       du       ls total
t0 start             150000   150000   150000          127313
t1 hard link         150000   150000   150000          127361
t2 sparse files      150320   150320   150320         1151361
t3 log deleted       150320   150320    30320         1031361
t4 handle closed      30320    30320    30320         1031361

tool         correct reads  wrong reads
  df                  5             0
  du                  4             1
  ls                  0             5
wrong diagnosis: 6 / 15

seed 20260218: t0 oracle 150000 ls 127313 | t3 oracle 150320 du 30320 | t4 oracle 30320 ls 1031361
seed 20260219: t0 oracle 150000 ls 127292 | t3 oracle 150320 du 30320 | t4 oracle 30320 ls 1031339

Three numbers side by side. The oracle: what has really been allocated at the third moment is 150,320 blocks. The tool’s output: du sees 30,320 blocks at the same moment. Wrong diagnosis: six of fifteen readings are wrong — five from the file-listing total, one from du’s output.

The third moment is the trap the operator falls into most often. The log file has been deleted, du’s output has dropped by 120,000 blocks, and that file is not in the directory tree; but because the process holding it open is still running, the blocks have not been released even though the link count has dropped to zero. df keeps telling the truth, and until the 120,000-block gap between the two tools is explained, an attempt to free space goes nowhere. The fix is not deleting; it is restarting the process holding the file open, and which process is holding it is found with a tool that lists open handles.

The file-listing total is wrong at all five of the five moments, and wrong in two separate directions. At the start it undercounts: the byte total reported by thirty thousand small files corresponds to 127,313 blocks, while in reality 150,000 blocks are allocated, because even a 1731-byte file takes up a full block. Once the sparse files are written, it overcounts: 40 files report a size of 1,024,000 blocks, while in reality they hold 320 blocks. In the second seed, these two numbers come out to 127,292 and 1,031,339; the direction does not change.

Repairing an Exhausted Table

When inodes run out, there are three things that can be done, and all three have a cost. The first is deleting files; this gives the record in the table back, and collecting single-line measurement files into an archive is usually the fastest fix. The second is enlarging the file system; in designs that keep a fixed table, enlarging can extend the table too, but the ratio depends on the decision made at format time. The third is reformatting, and this irreversibly erases everything on the partition.

The third way is not given in a runnable, complete form in this lesson. When the formatting command, written together with the option that sets the inode count, is run with the wrong partition name, it erases all the data without producing a warning, and it is irreversible. The safe way to test it is three steps: verifying the target partition’s identity with blkid, doing the trial on a file mounted as a loop device, and taking a snapshot of the partition before running it for real.

The precaution itself is measuring. Unless inode usage is asked as often as block usage, the moment the table fills becomes not a warning but a failure; and when the failure arrives, the only number in the output will still read one percent.

Summary

• An inode is the record that carries everything about a file except its name; a link count dropping to zero does not by itself free space, no process holding the record open may remain either.
• A file system consumes two separate resources, and both produce the same error message: at 30,000 files, with block usage 0.0114 and inode usage 0.9155, the write succeeds; at 32,768 files, with 0.0125 and 1.0000, it fails.
• The warning rule gives 2 wrong diagnoses in twelve cases when it looks only at the block percentage; also 2 when it looks only at the inode percentage, and also 2 when both are used together. The missed count drops to zero, the false-alarm count rises to two.
• When allocated space is counted three ways, six of fifteen readings are wrong: the file-listing total is wrong at all five of the five moments, and du cannot see the 120,000 blocks of a file whose name is deleted but whose handle stays open.
• One of the three ways to repair an exhausted table is reformatting, and it is irreversible; this lesson does not give that command in complete form, the safe way to test it is identity verification, a loop device, and a snapshot.

Next Step

This lesson’s measurements rested on a single assumption: that the directory being looked at really is that file system’s directory. Yet a file system is mounted at a point in the tree, and that point is a writable directory both before and after mounting. The next lesson measures the mount point and counts where data written there before a file system is mounted goes, and which tools cannot see it once it is mounted.