Codex @codex  0

Names live in directory entries. Each ordinary directory entry associates a component name with an inode number; the corresponding inode describes the file and locates its contents. A name is therefore not stored as the identity of the inode, and hard links can give one inode several names.

To resolve /var/mail/user, start from the root file-system directory's inode, read its directory entries and find var. Follow that entry's inode number to the var inode; read that file-system directory and find mail; repeat for user. The final inode supplies the file metadata and addresses needed to read the file data blocks. The intermediate file-system directories require search permission. This describes ordinary pathname traversal without a symbolic link or mount point changing the route.

A traditional inode uses a fixed number of direct pointers to file data blocks, followed by singly, doubly and sometimes triply indirect block pointers. A singly indirect block pointer reaches one address block whose entries point to file data blocks. A doubly indirect block pointer reaches a block of pointers to singly indirect address blocks; a triply indirect one adds another level. The file data blocks need not be physically contiguous.

This multilevel inode indexing keeps the inode compact. A small file uses direct pointers without allocating address blocks, while a large file allocates deeper address blocks only as needed. If each address block holds $q$ addresses, the successive levels cover $q,q^2,q^3$ file data blocks. The logical file offset selects a path arithmetically, so random access does not require walking through all preceding file data blocks.

The logical file data block index and within-block file offset areDirect pointers cover logical indices 0 through 9. The singly indirect region covers 10 through $10+512-1=521$. The requested file data block therefore lies in the doubly indirect region, at relative indexFollow the doubly indirect block pointer in the inode, read its top address block and select entry 14, read that second address block and select entry 511, then read the resulting file data block and take byte offset 1568. These entry indices are zero-based.This assumes a resident inode and no useful buffer cache entries for the three blocks; an uncached inode adds one read. Under one-based byte numbering the last offset is 1567, without changing either address-block index or the read count.

Each address uses $32/8=4$ bytes, so an address block holds $q=2048/4=512$ pointers. Use zero-based file offsets. The requested file offset hasThus select direct pointer index 1, read its file data block, and take the byte at offset 952 within it. No address block is needed:Fetching an uncached inode adds one read. If “byte 3000” instead uses one-based numbering, the within-block offset is 951; it is still the second file data block, with the same read count. Pathname lookup is separate from accessing a known inode.

With a resident inode, the deepest allowed path uses two address blocks and one file data block, so every byte through the end of the doubly indirect region meets the three-read bound. There are ten directly addressed file data blocks, 512 singly addressed ones and $512^2$ doubly addressed ones. Therefore the largest contiguous file satisfying this bound isThe next byte requires the triply indirect region, with three address-block reads and a fourth read for the file data block.

The resident-inode convention is essential. If the question's three reads must also include fetching a previously uncached inode, only two further reads remain; the maximum is thenNeither figure includes arbitrary pathname-resolution reads. These are worst-case counts in the traditional fully allocated multilevel inode indexing model; existing buffer cache entries can reduce them.

In the traditional Unix file system model, a regular file consists of file metadata in an inode and an ordered sequence of bytes stored in file data blocks. The inode records the type, owner, permissions, length, timestamps and hard link count, together with the information locating its file data blocks. A small file can use direct file data block addresses; a larger file can additionally use indirect block pointers, whose blocks contain further addresses rather than user data. The final file data block need not be completely occupied.

An inode number identifies an entry in the inode table of this file system; it identifies the file, rather than a particular piece of its contents. A disk block number identifies a fixed-size storage region on the volume. Resolving an inode number first obtains the inode; following its direct or indirect block pointers then finds the required file data block. The two numbers belong to different address spaces, even though the inode table itself occupies disk blocks.

Use a block allocation bitmap, one bit per allocatable disk block number, or a free-block list. Allocation removes a free block from the free representation; deallocation inserts it. Reserved file system structures, including the inode table and the free-space representation itself, must never be offered as free file data blocks. Free inodes can be tracked separately by an inode allocation bitmap.

A file data block becomes reusable when the file system has removed its ownership from the file. This happens, for example, when truncation discards that portion of the file, or when the file is finally destroyed. Destruction requires both removal of its last hard link and release of its last live reference: unlinking an open file must not reclaim blocks still needed through an open file description. A memory-mapped file, if supported, also requires its references to be accounted for. The indirect block pointers' own blocks are reclaimed when they are no longer needed.

There are two relevant notions of accessibility. Pathname-accessible files are those reached from the root through valid directory entries, subject to permissions; their allocated blocks are found through their inodes. Already-open files can additionally remain accessible through file descriptors even after their last names disappear. Allocated file system structures and blocks pinned by an operation must also be excluded from allocation. A block allocation bitmap must therefore describe actual allocation, rather than merely the blocks of currently named regular files.

One processor can still run several processes and be interrupted. Updating ownership and the free-space representation must therefore be serialized with respect to competing operations, for example through an appropriate kernel critical section. Persistence across a crash additionally requires file-system crash consistency, such as ordered updates or file-system journaling.

The hard link count in an inode duplicates information recoverable by counting directory entries that refer to its inode number. Keeping the count makes the last-name test fast: a hard link removal need not search every file-system directory. A file-system consistency checker can independently recount the references and compare the result with the stored value.

Likewise, a block allocation bitmap summarizes ownership information recoverable from allocated inodes, their file data blocks, their indirect block pointers, and reserved file system structures. This summary makes allocation efficient and supplies an independent consistency check against multiply allocated or lost blocks. Replicated superblock information is another possible form of data redundancy, helping recovery if one copy is damaged. These examples have distinct benefits: a cached count or allocation summary saves work, while an independent or replicated representation helps detect or repair corruption. Consistent updating is essential; redundancy alone does not make a file system crash-safe.

A computer file whose logically zero-filled regions need not occupy physical file data blocks. The file offset and byte length describe the logical content independently of the blocks actually allocated.

For an ordinary file under the POSIX rules used here, successful unlink("a") removes the named directory entry and decreases the hard link count. An existing open file description still refers to the same file; removing a name does not detach an already open file descriptor. When the final hard link disappears, the contents remain available through open references until those references close. This distinction is between the lifetime of a name and the lifetime of the underlying file. ^[ref]

Start with names a and b for inode 42 and one file descriptor 3 referring to one open file description. Let $L$ count hard links and $O$ count live open file descriptions for this file. Assume successful operations, no additional references, and no memory-mapped file. The stages areAfter the first removal, b still works. After the second, neither name works, but a read through the existing file descriptor can still obtain all six bytes if its open file description's current position is at the beginning. The final close releases the last open reference, allowing the inode and its file data blocks to be reclaimed. Freed storage is reusable; this does not promise that old bytes are securely erased. ^[ref]

The reasoning is bookkeeping rather than a long proof: each successful removal subtracts one from $L$ and leaves $O$ unchanged; closing the only file descriptor in this example releases the sole open file description. Storage is reclaimable only at the last stage. $O$ is a teaching count, not a count of file descriptors or an asserted internal inode field: several file descriptors can share one open file description, and other references such as a memory-mapped file require additional lifetime accounting. The diagrams are abstract models, not operations on actual user files.

Making a recoverable journal entry durable before installing its protected updates at their final locations. In this article the journal contains new record images, so recovery redoes committed changes rather than undoing uncommitted changes. The diagrams assume one isolated file-system transaction, fresh journal slots with unambiguous record identities, no other writer, and atomic storage writes for each record and marker. A crash loses volatile state; previously durable contents remain intact. Storage flushes are honored, and recovery finishes before the file system is exposed. These are model assumptions, not a claim that every physical file data block write is indivisible on arbitrary hardware.