ext2

ext2 is a block-based filesystem built around dividing a volume into fixed-size block groups, each holding its own copy of the metadata needed to allocate space within it, rather than concentrating all of that bookkeeping in one place. The VFS layer already defines what a superblock, inode, and directory entry are in the abstract; this article covers what those same concepts look like as actual bytes on an ext2 volume, which is a different question from FAT’s linked-list allocation model covered separately.

Block groups

A volume is divided into consecutive block groups, each spanning a fixed number of blocks (a common choice is one group per 8,192 4 KB blocks, exactly the number of blocks a single block-sized bitmap can describe). Every group carries its own block bitmap and inode bitmap, one bit per block or inode in that group marking it used or free, its own slice of the inode table, and, for at least some groups, a backup copy of the superblock and group descriptor table. Splitting allocation bookkeeping this way keeps a bitmap search local to whichever group a file is being allocated in rather than scanning a single filesystem-wide structure, and keeping a file’s data blocks and its inode in the same group where possible reduces how far a disk’s read head has to seek between reading an inode and reading the data it points to.

The superblock

The superblock, stored at a fixed offset (1,024 bytes from the start of the volume, to leave room for a boot sector ahead of it) and mirrored in backup copies elsewhere, holds the volume-wide facts every other structure depends on.

struct ext2_superblock {
    uint32_t s_inodes_count;
    uint32_t s_blocks_count;
    uint32_t s_r_blocks_count;     // blocks reserved for the superuser
    uint32_t s_free_blocks_count;
    uint32_t s_free_inodes_count;
    uint32_t s_first_data_block;   // 0 for 1 KB blocks, 1 otherwise
    uint32_t s_log_block_size;     // block size = 1024 << s_log_block_size
    uint32_t s_blocks_per_group;
    uint32_t s_inodes_per_group;
    uint16_t s_mnt_count;
    uint16_t s_max_mnt_count;
    uint16_t s_magic;              // 0xEF53
    uint16_t s_state;
    uint16_t s_errors;
    uint32_t s_rev_level;
    uint32_t s_feature_compat;
    uint32_t s_feature_incompat;
    uint32_t s_feature_ro_compat;
    uint8_t  s_uuid[16];
    char     s_volume_name[16];
    // ...
} __attribute__((packed));

s_mnt_count and s_max_mnt_count track a mount count, incrementing the former on every mount and forcing a full filesystem check once it reaches the latter, an early defense against slow-accumulating corruption going unnoticed indefinitely between checks. A state field (s_state) distinguishes a cleanly unmounted filesystem from one still marked as mounted; finding the latter at mount time is exactly the signal that the system went down uncleanly last time (a crash or power loss) and a consistency check should run before trusting the volume further, the full-volume fsck scan journaling was later designed to avoid. A separate field, s_errors, governs what a driver does on discovering corruption during ordinary runtime operation rather than only at mount: continue and merely log the problem, remount the volume read-only to stop it from getting worse, or halt the system outright, the same last resort Kernel Panics covers in general.

Two revision levels change what the rest of the superblock actually contains. The original EXT2_GOOD_OLD_REV fixes every inode at 128 bytes and defines nothing past s_inodes_count and its immediate neighbors; EXT2_DYNAMIC_REV, recorded in s_rev_level, adds the fields listed above s_uuid onward, including a real, driver-visible inode size in place of the fixed 128 bytes, letting a newer volume grow inodes (to make room for nanosecond timestamps or extended attributes, for instance) without breaking a driver that only understands the older, fixed layout. s_feature_compat, s_feature_incompat, and s_feature_ro_compat refine that same negotiation bit by bit rather than as a single revision number: a bit set in s_feature_incompat that a given driver doesn’t recognize (compression, historically) means the driver has to refuse mounting the volume at all, since it has no way to know how data laid out under that feature is actually structured, while an unrecognized bit in s_feature_ro_compat (sparse superblock placement, for instance) only demotes the mount to read-only, safe because nothing about interpreting existing data on the volume changes, only the driver’s own ability to safely add new data to it does.

s_r_blocks_count reserves a percentage of the volume’s total blocks (5% by mke2fs’s own default) that only a process running as the superuser can allocate into: an ordinary user’s write past the effective free-space limit fails with ENOSPC while the superuser’s own write still succeeds, headroom specifically meant to keep a system-critical process (a logging daemon, for instance) able to write small amounts of data even after user-controlled processes have otherwise filled every block visible to them. s_uuid and s_volume_name serve identification rather than allocation: a bootloader configuration or /etc/fstab entry referencing a volume by either one keeps working after that volume moves to a different disk or partition number, which a reference to the device path itself would not survive.

Group descriptors and bitmaps

Immediately following the superblock (or its backup, in groups that carry one) sits the group descriptor table, one 32-byte descriptor per block group, present in full in every group that has a superblock backup rather than split up. Each descriptor holds the block numbers of that group’s own block bitmap, inode bitmap, and inode table, plus a few summary counts (free blocks, free inodes, and directories in that group) kept for quick reporting without walking the bitmaps directly. Finding a free block for allocation is then a matter of locating a group with free space via the descriptor’s summary count, then scanning that group’s block bitmap for a clear bit, flipping it, and decrementing both the group descriptor’s and the superblock’s free-block counts to keep both levels of bookkeeping consistent.

Inodes and the block-pointer tree

An ext2 inode (128 bytes in the original format) stores a file’s metadata (owner, permissions, size, timestamps) and, distinct from how FAT locates data through a single chain, an array of fifteen block pointers, i_block[15], that together locate every block the file occupies. The first twelve entries are direct pointers, each naming one data block outright, which is enough by itself for the large majority of ordinary small files without any further indirection. Entry twelve is a singly indirect pointer: rather than pointing at data, it points at a block that is itself entirely filled with more direct pointers, extending reach by one block’s worth of additional pointers (1,024 more direct blocks with a 4 KB block size, since each pointer is 4 bytes). Entry thirteen is a doubly indirect pointer, pointing at a block full of singly-indirect pointers, each of which points at a block full of direct pointers; entry fourteen is triply indirect, adding one more such level. Reading byte offset N of a file is therefore a matter of dividing by the block size to get a logical block number, then deciding which of the four tiers that block number falls into and walking however many indirection levels that tier requires before reaching an actual data block pointer.

uint32_t block_from_offset(struct ext2_inode *inode, uint32_t block_size, uint32_t logical_block) {
    uint32_t ptrs_per_block = block_size / 4;

    if (logical_block < 12)
        return inode->i_block[logical_block];

    logical_block -= 12;
    if (logical_block < ptrs_per_block) {
        uint32_t *indirect = read_block(inode->i_block[12]);
        return indirect[logical_block];
    }

    logical_block -= ptrs_per_block;
    if (logical_block < ptrs_per_block * ptrs_per_block) {
        uint32_t *dbl = read_block(inode->i_block[13]);
        uint32_t *indirect = read_block(dbl[logical_block / ptrs_per_block]);
        return indirect[logical_block % ptrs_per_block];
    }

    // triple indirection follows the same pattern one level deeper
    return 0;
}

This structure means a file’s maximum size is bounded by how many blocks fifteen pointers with up to triple indirection can ultimately address, roughly two tebibytes with a 4 KB block size, but it also means locating a byte far into a large file costs more block reads than locating one near the start, since reaching triple-indirect territory means reading three indirection blocks before the actual data block pointer is even known.

Directory entries

A directory in ext2 is, structurally, an ordinary file: its data blocks, reached through the exact same i_block mechanism described above, hold a sequence of directory entry records rather than arbitrary file content. Each entry carries the inode number it names, a record length (rec_len) spanning from the start of this entry to the start of the next, a name length, a file type hint, and the name itself, stored inline rather than at a fixed offset. Record length being separate from name length is what lets a directory entry be deleted cheaply: removing an entry just extends the previous entry’s rec_len to swallow the deleted one’s space, leaving the underlying bytes untouched and avoiding having to shift every subsequent entry down to close a gap. A directory lookup walks these records linearly comparing names, which is simple but means a directory with a very large number of entries has no better than linear-time lookup by name, a limitation later ext2-derived filesystems addressed by optionally indexing large directories with a hashed B-tree instead.

Implementation notes

A group descriptor’s free-block and free-inode counts are a cache of information the bitmaps already contain in full, and an implementation that updates one without the other, or crashes between the two updates, produces an inconsistent volume where the fast summary counts disagree with a direct bitmap scan; this is one of the specific things a full fsck-style pass detects by recomputing counts from the bitmaps directly rather than trusting the cached summaries. Determining a new file’s block-allocation strategy well, allocating a file’s blocks from the same group as its inode where free space allows rather than wherever the first free block happens to be, is not required for correctness at all, but noticeably affects performance on rotating media, where nearby blocks cost far less seek time than blocks scattered across distant groups. Finally, indirect blocks are themselves ordinary allocated blocks tracked in the same bitmaps as data blocks, so a large file with several layers of indirection consumes noticeably more of a volume’s total block budget than its own data size would suggest, entirely in pointer bookkeeping rather than file content.

References

^ The Second Extended File System (Dave Poirier’s long-maintained on-disk format reference)
^ OSDev Wiki, “Ext2” (a hobbyist implementation reference with worked byte-offset examples)

ext2

Block groups

The superblock

Group descriptors and bitmaps

Inodes and the block-pointer tree

Directory entries

Implementation notes

References

See also