Filesystems: Derive the Address Before Following It

A file's byte offset is not a physical disk address. First locate its logical block, then follow the inode's mapping to a physical data block. The inode stores direct pointers; the data blocks themselves live elsewhere.

From a byte offset to a data block

For block size B, byte offset x gives logical = x / B and offset = x % B, using integer division. Mapping changes the block number, not the byte offset. With 512-byte blocks, byte 6,731 lies in logical block 13, offset 75. If logical block 13 maps to physical block 901, its simplified byte address is 901*512 + 75 = 461387.

The exercise has four direct entries and four pointers per indirect table. Its slices hold already-decoded pointers; you do not read metadata blocks from disk. More generally, if a pointer occupies P bytes, a full block can hold F = B/P pointers, assuming divisibility and no other table metadata. With D direct entries, one single-indirect root and one double-indirect root cover:

direct: D data blocks
single: F data blocks
double: F*F data blocks
total: D + F + F*F

These are data capacities; they exclude blocks occupied by the pointer tables. The historical ext2/3 mapping uses these levels (and triple indirection), while ext4 commonly uses extents. The exercise's tiny tables are a teaching layout, not an ext4 parser. Linux inode block mapping

Subtract the ranges before dividing

With D=4 and F=4:

Logical block L	Region	Index computation
0–3	Direct	Direct[L]
4–7	Single indirect	Indirect[L-4]
8–23	Double indirect	k=L-8, Double[k/4][k%4]
otherwise	Outside capacity	-1

For logical block 13, subtract both earlier regions: k=13-4-4=5. Division picks table 5/4=1; remainder picks entry 5%4=1. Thus return Double[1][1]. Dividing the original 13 instead gives row 3, silently selecting the wrong block.

Trace the seams explicitly: block 3 is Direct[3], 4 is Indirect[0], 7 is Indirect[3], 8 is Double[0][0], 11 is Double[0][3], 12 is Double[1][0], and 23 is Double[3][3]. Block 24 is invalid even if an oversized input slice contains another entry.

Missing storage is not block zero

A stored -1 is missing. A short slice, a missing double-indirect row, or a short row also means missing. Check both row and column before indexing. Zero is a valid physical block number in this exercise; treating it as an absent pointer changes the contract. A lookup neither allocates storage nor mutates the inode. Real sparse-file reads can synthesize zeros for holes; this API only returns the -1 sentinel.

For Double = [[60,61], [], [80]], logical block 9 returns 61; 10 is missing; 12 is missing because row 1 is empty; 16 returns 80. Ragged input does not compress the address space: row 2 still begins at logical block 16.

Metadata cost is separate from capacity

With all 24 data slots populated, our layout needs one single-indirect table plus one double-indirect root plus four tables under that root: six metadata blocks, in addition to the inode and 24 data blocks. With no cache, a direct lookup needs no pointer-table read; a single lookup needs one; a double lookup needs two before reading the data. The provided slices hide these I/O costs.

LOOK scheduling: a second mapping problem

The disk exercise models seek distance on a rotating disk. It omits rotational latency, transfer time, request arrivals, and SSD behavior. LOOK serves requests along the initial direction, reverses at the last pending request in that direction, then serves the other side. SCAN instead travels to the disk boundary. Neither policy is universally fastest.

Start at track 40, moving upward, with requests [15,55,25,70,55]. Sort the upper side ascending and lower side descending: service [55,55,70,25,15]. Seek distance is 15+0+15+45+10=85; repeated requests remain distinct but add no movement between equal tracks. A request at the current head is served immediately in either direction with zero movement. If the initial side is empty, reverse immediately rather than inventing a trip to the disk edge. Under this finite batch model every request finishes; fairness under continuing arrivals is a different question. OSTEP: Hard Disk Drives

Check your reconstruction

1. Logical block 18 maps where? k=10, row 2, column 2.
2. A double table has three rows. Is logical block 23 present? No: it needs row 3.
3. For the LOOK example, what changes if direction is downward? Order [25,15,55,55,70], seek 15+10+40+0+15=80. Direction changes the answer even with the same sorted requests.