How the Linux Kernel Maps Inode Numbers to Disk Sectors: An Axiomatic Derivation
The Core Axioms
To understand how a operating system translates a logical inode identifier into a physical sector and byte offset on hardware, we must start from the fundamental architectural axioms. No assumptions or abstractions are allowed.
The underlying storage medium reads and writes data exclusively in fixed-size blocks called sectors. On traditional filesystems, the sector size is exactly 512 bytes.
An inode is a static record structure residing on disk that describes a file's metadata. In the System V and Unix V6 designs, each inode structure occupies exactly 32 bytes.
Based on Axiom 1 and Axiom 2, exactly 16 inodes fit into a single disk sector, derived as:
512 bytes / 32 bytes = 16 inodes per sector.
The first block (sector 0) is reserved for boot-loader bootstrap routines. The second block (sector 1) is reserved for the superblock containing structural volume configurations. Consequently, the actual inode table physically begins at sector 2.
Right shifting an unsigned integer x by n bits (x >> n) is mathematically identical to integer division by 2^n (x / 2^n).
Bitwise-ANDing an unsigned integer x with a mask of (2^n - 1) (x & (2^n - 1)) is mathematically identical to taking the modulo remainder by 2^n (x % 2^n).
Derivation Step 1: Simulator Division/Modulo
Using our simulator constants derived from Axioms 3 and 4:
INODE_START_SECTOR = 2
INODES_PER_BLOCK = 16
To find the location of inumber = 100, we subtract 1 to establish a 0-indexed distance from the start of the table, then map it:
block_of_inode = 2 + (100 - 1) / 16 = 2 + (99 / 16) = 2 + 6 = 8
slot_in_block = (100 - 1) % 16 = 99 % 16 = 3
Thus, we read sector 8, and index the 4th struct inode slot (index 3).
Derivation Step 2: Linux Production Bitwise Map
Now let's examine the raw production code inside the 6.8.0 Linux kernel at fs/sysv/ialloc.c lines 56-69:
struct sysv_inode *
sysv_raw_inode(struct super_block *sb, unsigned ino, struct buffer_head **bh)
{
struct sysv_sb_info *sbi = SYSV_SB(sb);
struct sysv_inode *res;
int block = sbi->s_firstinodezone + sbi->s_block_base;
block += (ino-1) >> sbi->s_inodes_per_block_bits;
*bh = sb_bread(sb, block);
if (!*bh)
return NULL;
res = (struct sysv_inode *)(*bh)->b_data;
return res + ((ino-1) & sbi->s_inodes_per_block_1);
}
The Axiomatic Mapping
Let's map each kernel statement directly back to our core axioms, proving their mathematical equivalence:
In the kernel, sbi->s_firstinodezone + sbi->s_block_base calculates the dynamic starting sector of the inode table on the device. For our simulator disk layout, this matches Axiom 4 (value 2).
The kernel calculates block += (ino-1) >> sbi->s_inodes_per_block_bits.
Applying Axiom 5: Since 16 inodes fit per block, s_inodes_per_block_bits = 4 (as 2^4 = 16). The shift (ino-1) >> 4 is identical to the division (ino-1) / 16.
The kernel calculates res + ((ino-1) & sbi->s_inodes_per_block_1).
Applying Axiom 6: Since s_inodes_per_block_1 = 15 (which is 16 - 1, binary 00001111), the operation (ino-1) & 15 isolates the lower 4 bits. This is identical to the modulo operation (ino-1) % 16.