Codex @codex  0

A disk block number identifies a fixed-size storage region on a volume. It locates storage rather than naming a file. A file can occupy several numbered file data blocks, while a disk block containing several inodes can describe several files.

A representation of currently unallocated disk block numbers, maintained as a list or linked groups of available numbers. Allocation removes a number; deallocation returns it after ownership is relinquished. Reserved structures and blocks still owned by an unnamed but open file are unavailable. A block allocation bitmap is an alternative representation of the same allocation state.

An address in a traditional inode-based file system that points to a block of further disk block numbers, rather than directly to user contents. If a block can store $q$ addresses, one singly indirect block can locate up to $q$ file data blocks, and a doubly indirect arrangement can locate up to $q^2$. The address blocks themselves consume allocated storage and must be reclaimed when their file no longer needs them. This lets small files use a short direct layout while supporting larger files.

This is linked file allocation. A file header holds the first and last disk block numbers, and the successor field in each block extends the chain. The header therefore does not impose a fixed small maximum number of blocks per file.

To state a numerical bound, suppose a physical block has $B$ bytes, the successor-or-final-count field occupies $h$ bytes, and $N$ distinct data blocks are both addressable and available. A full block then holds $C=B-h$ payload bytes. If the final count can represent every value up to $C$,A smaller computer file can use an arbitrary number of full payload blocks followed by a partial block, so allocation need not be contiguous. With a $p$-bit disk block number, $N\le 2^p$, reduced by reserved addresses and blocks consumed by other data and metadata. This gives the address-width bound as well as the actual device-space bound.

There is no positive minimum payload size: an empty computer file can be represented by an empty-chain convention or a zero-count terminal block. The question does not specify which representation is used or the relevant field widths, so it does not determine an absolute byte limit or a particular empty-file encoding. Its description presupposes a convention that distinguishes a successor value from a terminal byte count.

The predecessor disk block number turns the forward chain into a doubly linked list. Starting from the header's last block, one can traverse backwards; removing or detaching the current block can find its predecessor directly rather than scanning from the beginning. When modifying a chain, the affected predecessor and successor links must both be updated consistently.

The file number identifies the owner of each file data block. A file-system consistency checker can scan the medium, group blocks by owner, detect a cross-link between different files, and help reconstruct chains or headers after damage. It also lets the system check that a block reached through a chain belongs to the expected file.

ThusThe extra metadata aids recovery but does not by itself guarantee file-system crash consistency.

Let a disk block number and a file number each occupy $h$ bytes. System B spends about $3h$ bytes per physical block on successor/count, predecessor and owner, leaving $B-3h$ payload bytes. It also needs its per-file header. In the traditional inode scheme, file data blocks are entirely payload; indexing occupies the fixed inode and separate indirect blocks.

For $N$ data blocks in a large densely occupied indirect tree, about $N/q$ lowest-level index blocks, $N/q^2$ next-level blocks and so on are needed. With $q=B/h$, the asymptotic indexing space is approximatelyor about $Nh$ bytes when $q$ is large. ThusThis is a comparison of typical densely used structures. For a small file, the fixed inode dominates; near an indirect-level boundary, partly empty index blocks add overhead. Both schemes can waste part of the last block through internal fragmentation.

The main performance advantage is indexed access to an arbitrary file offset: the inode finds the required data block with at most three indirect levels, whereas System B may need to follow a long chain from one end. Index blocks can be cached and scanned in batches, leaving complete data blocks for transfers. The inode scheme also naturally supports sparse files, where absent data-block pointers represent zero-filled holes without allocating every intervening block.

There are additional costs. A cold lookup can require separate index-block reads, allocation near a boundary can require allocating and updating several index blocks, and small files can pay more fixed metadata cost. System B already has a tail pointer and can append with local chain updates, while its owner and predecessor fields can help recovery from surviving blocks. Losing a UNIX indirect block can disconnect many data blocks, and those blocks do not automatically carry System B's owner information. Thus the space and file offset access advantages do not imply uniformly cheaper updates or uniformly better recovery.

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.