Disk Access: Inode Traversal Arithmetic

The problem

The Tripos asks: how many disk accesses are needed to read a specific byte of a file, given the inode and block-pointer structure? The answer depends on the size and position of the byte, because larger files require traversing indirect blocks.

The inode structure (standard model)

Assume the Tripos-standard inode:

• 10 direct block pointers
• 1 single-indirect pointer
• 1 double-indirect pointer
• 1 triple-indirect pointer
• Block size = $B$ bytes
• Pointers are $P$ bytes (typically 4 or 8)
• Pointers per block = $B / P$

Counting disk accesses

To read the $n$-th byte of a file:

1. Read the inode: 1 disk access (unless cached). For the purposes of exam arithmetic, we usually count accesses from the inode in memory — i.e., we assume the inode has already been read. Check the question wording carefully.

2. Determine which pointer tier to use:

   • Bytes $0 \text{ to } 10 \times B - 1$: use a direct pointer → 1 access (the data block).
   • Bytes $10 \times B \text{ to } (10 + N) \times B - 1$ where $N = B/P$: single indirect → 2 accesses (read the indirect block, then the data block).
   • For double indirect: 3 accesses (double-indirect block, single-indirect block, data block).
   • For triple indirect: 4 accesses.

Worked example (2021 Paper 2 Q3(b))

A file system with 4 KB blocks and 4-byte block pointers. Inode has 10 direct pointers, 1 single, 1 double, 1 triple indirect. How many disk accesses to read byte 10,000,000?

1. Pointers per block: $4096 / 4 = 1024$.

2. Direct range: $10 \times 4096 = 40{,}960$ bytes (approximately 41 KB). Byte 10,000,000 is far beyond this.

3. Single-indirect range: $1024 \times 4096 = 4{,}194{,}304$ bytes (4 MB). $40{,}960 + 4{,}194{,}304 = 4{,}235{,}264$ bytes. Still below 10,000,000.

4. Double-indirect range: $1024^2 \times 4096 \approx 4 \text{ GB}$. $4{,}235{,}264 + 4 \text{ GB} \gg 10{,}000{,}000$. So the byte is in the double-indirect range.

5. Disk accesses:

   • 1: read the double-indirect block.
   • 1: read the single-indirect block (indexed by the double-indirect entry).
   • 1: read the data block.
   • Total: 3 disk accesses (plus the inode itself if not cached — typically 4 with the inode).

The general formula

For a byte at offset $O$:

• Let $D$ = direct pointers, $N$ = pointers per block, $B$ = block size.
• Direct range: $[0, D \times B)$.
• Single-indirect range: $[D \times B, (D + N) \times B)$.
• Double-indirect range: $[(D + N) \times B, (D + N + N^2) \times B)$.
• Triple-indirect range: beyond that.

The number of accesses is $1 + \text{indirection\_level}$, where level is 0 (direct), 1 (single indirect), 2 (double), 3 (triple). Add 1 for the inode itself if the question specifies it must be read.

Summary

• The inode stores direct, single-indirect, double-indirect, and triple-indirect block pointers.
• For small files (under ~48 KB), 1 disk access reaches the data.
• For medium files (up to ~4 MB), 2 accesses (single indirect + data).
• For large files (up to ~4 GB), 3 accesses (double indirect + single indirect + data).
• The arithmetic is mechanical: compute the byte range for each tier and count the levels of indirection.