Inode Tables and the Arithmetic of Inode Numbers

An inode number is not a key into a hash table and it is not an address. It is an index into a set of fixed-size records that were laid out when the filesystem was created, and the mapping from number to byte offset is a division and a multiplication. That is the whole reason the interface exposes a stable integer where a pointer would have been more natural: the number survives a remount, a repair, and a change of machine, because it is derivable from the volume’s geometry alone.

Fixed records make lookup constant time

The inode table is an array of records, each the same size. The original ext2 record is 128 bytes; later revisions extend it to 256 bytes and beyond so that extra fields can be appended without moving the original ones. A group holds s_inodes_per_group consecutive records starting at the block named in its descriptor’s bg_inode_table.

Given a number n, the group is (n - 1) / s_inodes_per_group and the position within the group is (n - 1) % s_inodes_per_group. The byte offset is the group’s table start, times the block size, plus the position times the record size. Two divisions and two multiplications, no I/O beyond reading the block that contains the record.

/* Locate an inode record from its number. No cache, no directory walk. */
struct inode_rec *inode_at(struct fs *fs, uint32_t n)
{
        uint32_t per_group = fs->inodes_per_group;
        uint32_t group     = (n - 1) / per_group;   /* numbers start at 1 */
        uint32_t index     = (n - 1) % per_group;
        uint64_t byte_off  = (uint64_t)fs->desc[group].inode_table_block *
                             fs->block_size +
                             (uint64_t)index * fs->inode_size;
        return read_bytes(fs->dev, byte_off, fs->inode_size);
}

Two details in that fragment carry weight. The subtraction of one is because inode numbers start at 1, not 0; inode 0 is never allocated and serves as a null value in directory entries that need to represent a deleted or empty slot. The record size is read from the superblock rather than assumed, because a filesystem created with 256-byte inodes has records twice as long as one created with the original 128, and a driver that hard-codes 128 will read the first half of inode n and believe it is inode 2n.

Preallocation is the point

The table is not grown. Its total size is s_inodes_count × inode_size, and it is reserved at format time, distributed across the groups. Creating a filesystem therefore commits a fraction of the volume to inode storage before a single file exists, and the fraction is chosen from an estimate of the average file size the volume is expected to hold.

The estimate is expressed as a ratio of bytes of space per inode. A value of 16384 means one inode per 16 KiB of volume, which suits a filesystem holding many small files; a much larger value suits a volume holding a few large ones. mke2fs exposes the choice, and it is the single most consequential decision made at format time, because it cannot be revised afterwards without rebuilding the filesystem.

The consequence of getting it wrong is asymmetric. Too many inodes wastes space: each unallocated record still occupies its bytes in the table, so a volume sized for a million small files and used for a hundred large ones carries megabytes of unused records. Too few inodes produces ENOSPC on a volume that reports free blocks, which is the failure that surprises people: df shows space available, du shows nothing unusual, and file creation fails.

The diagnostic is df -i, which reports inode usage separately from block usage: a filesystem whose IFree column has reached zero will refuse to create a file regardless of what the block columns say. Free blocks and free inodes are separate resources, and the second is fixed at format time while the first is not.

What lives in the record and what does not

The 128-byte core of the record holds the mode word, the owner and group ids, the size, the three timestamps, the link count, the block count, the flags, the generation number, and the pointers to data. In the original layout those pointers are fifteen 32-bit block numbers: twelve direct, one single-indirect, one double-indirect, one triple-indirect. The scheme is covered from the data side in Extent Trees and the Replacement of Indirect Block Maps; from the inode’s point of view what matters is that the pointer area is a fixed 60 bytes.

Sixty bytes is small, and the format has since redefined that area. With the extent feature, the indirect pointers are replaced by an extent tree header and four extent records in the inode itself, so a file whose blocks are contiguous needs no external metadata at all. The redefinition is legal because the feature is an incompat bit: a driver that understands extents knows to parse the area as a tree, and a driver that does not will refuse the mount rather than read the area as pointers.

The record also holds an extended-attribute block pointer. Attributes too large for the inode’s spare space are stored in a separate block, and the inode names that block. This is why an inode can be larger than the attributes it appears to hold, and why getfattr on a file with many attributes may read a block that the file’s own data pointers never reference.

Why the interface exposes a number

The inode number appears in stat, in directory entries, and in the d_ino field of readdir results. It has to be stable across mounts because programs cache it: a backup tool records the numbers it has seen, an indexer keys on them, and a mail server stores them to detect hard links to the same message.

Stability has a cost. Numbers are reused after an inode is freed, so a program that cached a number and later resolves it may find a different file. Filesystems that export over NFS carry a generation number in the inode for exactly this reason: the file handle pairs the inode number with the generation, and a handle whose generation no longer matches fails to resolve instead of resolving to the new occupant. The generation field is 32 bits and changes when the record is reused, so a stale handle is rejected rather than silently redirected.

Hard links make the number meaningful in a second way. Two directory entries with the same number are the same file, and no path-based comparison can establish that as cheaply as comparing two integers. The link count in the record is what makes reclamation correct: the inode is freed when the count reaches zero and the last open file description closes, an interaction described in VFS Objects and the Operation Vector.

Boundaries the arithmetic imposes

The number is a 32-bit field in the superblock, so a filesystem tops out at roughly four billion inodes, a limit no realistic volume approaches before other limits bind. The per-group count is bounded by the inode bitmap, which is one block and therefore holds 8 × block_size bits: 32768 inodes per group at a 4 KiB block size. A volume with more inodes than groups × 32768 cannot express them, which is one of the reasons the ratio of inodes to space has a floor.

The record size must divide the block size, since the table is a whole number of blocks. Sizes of 128, 256, 512, and 1024 bytes satisfy that; an odd size would leave a partial record at each block boundary and force every lookup to span two blocks. The power-of-two constraint is not a coincidence of the current implementations but a requirement of the addressing arithmetic.

The last boundary is the one that makes repair possible. Because the table’s location is derivable from the superblock and the descriptor table, a repair tool can enumerate every inode on the volume without trusting any directory. It reads each record, checks that the mode word names a legal type, and follows the data pointers to find blocks that the bitmaps do not claim. That traversal is the core of the consistency check described in fsck and the Ordering of Repairs, and it works only because inode lookup needs nothing but arithmetic.