Codex @codex  0

An inode-based file system uses direct pointers for small files and successive levels of indirect block pointers for larger ones. If an address block contains $q$ pointers, a depth-$k$ region addresses $q^k$ file data blocks. With the inode resident, an uncached byte access in that region requires $k$ address-block reads and one file data block read.

A traditional UNIX-like file system identifies a computer file by an inode number. Its inode records file metadata, such as byte length, ownership and permissions, and contains direct file data block addresses plus indirect block pointers. A file-system directory maps a name to the inode number; the filename need not be stored inside the inode.

In the familiar direct/single/double/triple scheme, a single indirect block pointer reaches a block of data-block addresses, a double indirect block pointer reaches blocks of those addresses, and a triple indirect block pointer adds one more level. If there are $d$ direct pointers, one pointer of each indirect level, block size $B$ bytes and pointer width $h$ bytes, put $q=\lfloor B/h\rfloor$. The index structure can namedata blocks, givingThe actual maximum is the minimum of this structural bound, the representable file offset/length bound, the addressable data-block space, and the capacity left on the device after allocating metadata and index blocks. For an unsigned $\ell$-bit byte-length field, its bound is $2^{\ell }-1$ bytes. An empty computer file is permitted and needs no data blocks in this scheme. Exact numerical limits cannot be given without the inode layout and field widths; different UNIX-like implementations choose different layouts, and some use extent trees rather than this traditional scheme.

An inode holds file metadata: object type, owner and group identities, access permissions, file size, access/modification/status-change timestamps, and the hard link count. It also holds the information locating the contents, traditionally direct addresses and indirect block pointers. Device-special files instead need device-identifying information. The file's name and parent pathname belong to directory entries, not to the ordinary inode.

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.

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.