Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Digital systems, linear algebra, introduction to formal proof / 2

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.

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.

An access control list is attached to an object, such as a file, and lists which subjects or groups may perform which operations. Access requires checking the requesting identity against that object's list. A security capability is an unforgeable reference to an object carrying specified rights; possessing valid authority is what permits access. Protected storage or another integrity mechanism must prevent users manufacturing stronger security capabilities.

The traditional Unix owner/group/other read-write-execute permissions are a compact, restricted access control list: the inode records the owner, group and permission bits, and the operating system compares these against the caller's credentials.An already-open file descriptor can behave like a limited handle carrying rights, but that does not change the identity-based nature of the initial pathname permission check.

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.

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.

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.