The Inode
A directory does not contain files. It contains names, and beside each name a number. Everything a file actually is lives somewhere else, indexed by that number, and it does not know what it is called. Two consequences fall straight out of the structure and neither one is a decision anybody made: how large a file can be, and how much work it takes to reach a byte in the middle of it.
New to how a disk holds a file? Start here
A disk is a long row of fixed-size blocks and nothing else. It has no notion of a file, a name or a folder. Everything above that is built by writing bookkeeping into some of the blocks, and the bookkeeping is what a filesystem is.
Unix splits it in two. A directory holds names, each paired with a number. That number reaches a small record holding the file's permissions, its size and the addresses of the blocks its data lives in. The record has no name in it. Once you see that split, hard links and the maximum file size both stop being facts to memorise.
Fast and forgetful, or slow and permanent
Memory is quick and loses everything when the power goes. A disk keeps what it was given and is slower by a factor with several zeroes in it. No single part is both, and no amount of engineering has made one.
So nearly every design in this topic is buying one with the other. Keep it in the fast part and you are quick until the lights go out. Write it to the slow part first and you are safe but waiting. The machines here are the arrangements people found in between, and each of them is honest about which half it gave up.
The machine for this idea on its own is Write-Ahead Log, if you would rather press it than read about it.
The filename is not the file
1 An i-node's addresses, how deep each has to go, and the maximum file size they add up to
The addresses an i-node holds, and how deep each one goes. The First Edition structure is the one dated 1971; the familiar ten-direct-plus-three-indirect layout is Seventh Edition, eight years later, and is here to be compared rather than mistaken for it.
| kind | how many | reads to reach data | bytes reachable |
|---|
2 What reaching a byte costs, decided only by how far into the file it is
What it costs to reach a byte, by where the byte is. Each row is the first offset that costs one more read than the row above it.
| from byte | block reads |
|---|
3 Two names for one i-node, and the count that decides when anything is freed
A directory holding two names for one i-node. Removing a name is not removing a file: it decrements a count. Reaching zero is what allows the blocks to be freed, and it is not quite enough on its own.
| name | i-node |
|---|
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| a First Edition small file tops out at 4,096 bytes, and nobody chose that | yes | 8 addresses x 512-byte blocks = 4,096 bytes; the limit is the structure, not a policy |
| setting the large flag buys exactly one megabyte, for the same eight addresses | yes | 8 x 256 addresses per indirect block x 512 = 1,048,576 bytes |
| every maximum is computed twice, by different arithmetic, and agrees | yes | tier-sum in ordinary numbers against a BigInt block count multiplied at the end; 3 layouts checked |
| the last byte of a Seventh Edition file costs four reads and the first costs one | yes | byte 0 needs 1 block read; byte 1,082,201,087 needs 4, three of them just to find out where it is |
| reaching a later byte never costs fewer reads than an earlier one | yes | 2,164 offsets swept across the whole addressable range |
| the addressing agrees with the size, to the byte | yes | the last addressable byte resolves in 4 reads and the next one resolves at all: no |
| deleting a name does not delete the file, because the name was never in it | yes | two names for inode 12, one removed, link count 2 to 1; the data is still reachable as backup.txt |
| it is the count reaching zero that allows the blocks to be freed, not any delete | yes | the last name removed takes the count to 0, which is what lets them go; a real system also waits for the last process holding the file open, which this model does not have |
| the 1971 structure is drawn for 1971, and the familiar one is labelled 1979 | yes | First Edition has 8 addresses and a large flag; Seventh Edition has 13 with three depths of indirection, and is what almost every diagram shows |
What is real here, and what is not
The structure drawn for 1971 is First Edition, and it is not the one you have seen
Nearly every i-node diagram shows ten direct addresses followed by single, double and triple indirect blocks. That is Seventh Edition, 1979. First Edition has eight addresses and a flag deciding whether they point at data or at blocks of further addresses, with no mixing. Both are on this page and each is labelled, because drawing the familiar one under a 1971 date would be wrong about the only thing the date refers to.
Reads are counted, not timed
A block read costs whatever the disk, the cache and the queue ahead of it cost, none of which this page can measure. What it can do is count how many separate blocks must be fetched to reach a byte, which is the part that depends on the structure rather than the hardware.
Caching is ignored, and on a real system it is most of the story
The cost table assumes every indirect block is fetched afresh. A real kernel keeps them in memory, so reading sequentially through a large file pays the deep lookup once and then almost nothing. The numbers here are the worst case for a single isolated read, which is the case that shows what the structure does.
The maximum sizes are computed, and computed twice
Neither the 4,096-byte small file nor the megabyte large file is typed into this page. Both are the addresses multiplied out, and each is calculated a second time by different arithmetic to catch a mistake in the first. The point of the machine is that these limits are consequences, so quoting them would undercut it.
A real directory is not a two-column list
The panel shows names beside i-node numbers, which is what a directory entry means, but a First Edition directory is a file of fixed sixteen-byte records and later ones are more involved again. The simplification is in the storage, not in the relationship, and the relationship is what the panel is about.
A link count of zero is necessary to free the blocks, and not sufficient
This panel frees the blocks the moment the last name goes, and a real system has one more condition: a process may still hold the file open. Unlink every name while a program is reading it and the directory entries are gone, the count is zero, and the data stays exactly where it is until that program closes it. That is how a program can keep a file nobody can find, and how deleting a large file can free no space at all until something exits. An outside review caught this page claiming the count alone decides.