Block Groups and the Cost of Metadata Locality

A naive filesystem is one flat array of blocks and one flat array of inodes. Allocation is then a scan for the next zero bit, and the first free block is whatever follows the last allocated one. That design is simple and it is what early filesystems effectively did, and it produces a volume whose data is laid out in creation order with no relation to how it will be read. The block group is the structure that fixes this by making locality a stored property rather than a hoped-for side effect of sequential allocation.

One block of bitmap, one table, one accounting record

A group is a contiguous run of blocks that carries its own allocation state. The superblock’s s_blocks_per_group and s_inodes_per_group fields, described in The Superblock: Magic Number, Geometry, and Feature Flags, bound the run, and each group holds:

• a block bitmap, one bit per block in the group;
• an inode bitmap, one bit per inode in the group;
• the slice of the inode table belonging to that group;
• a group descriptor, which records where those three regions live and how many free blocks and inodes remain.

The bitmap size follows from the block size. One 4 KiB block holds 32768 bits, so a group can track at most 32768 blocks; at 1 KiB blocks the limit is 8192. The inode table slice is s_inodes_per_group records of 128 bytes in the original format, larger when inode-size extensions are in use, and it is the largest of the three regions.

Descriptors are packed into a table that begins in the block after the superblock’s block. On a 1 KiB-block filesystem the superblock occupies block 1, so the table starts at block 2; with larger blocks the superblock shares block 0 with the boot area and the table starts at block 1. Each descriptor is 32 bytes in the original layout and 64 bytes with the 64-bit feature, which is why a filesystem with many groups and 64-bit descriptors may need more than one block for the table, and why the descriptor table itself is tracked as a reserved region rather than as ordinary metadata.

struct ext2_group_desc {
    __le32 bg_block_bitmap;      /* block number of the block bitmap */
    __le32 bg_inode_bitmap;      /* block number of the inode bitmap */
    __le32 bg_inode_table;       /* first block of this group's inode table */
    __le16 bg_free_blocks_count;
    __le16 bg_free_inodes_count;
    __le16 bg_used_dirs_count;   /* directories, for the Orlov heuristic */
    __le16 bg_pad;
    __le32 bg_reserved[3];
};

Note what a descriptor does not contain: no list of free blocks, no list of files. It holds pointers to the bitmaps and two counters. A driver that wants to allocate a block in group g reads that group’s bitmap, finds a zero bit, and flips it. The descriptor’s counter is an optimisation that avoids reading the bitmap when the count is already zero; it is not the authority on free space, and a mismatch between the counter and the bitmap is a repairable inconsistency rather than a structural failure.

Why the group exists at all

The original motivation was seek distance on rotating media. A file’s inode, its data blocks, and the directory entry naming it should be near each other, so that opening and then reading the file costs one short seek rather than three long ones. Making the group small enough that all three fit within a few cylinders achieves that for small files, which are the majority of files by count.

The second motivation is write amplification during allocation. Freeing and allocating within a group touches one bitmap block and one descriptor; spanning the whole volume would touch many. A group bounds the metadata dirtied per allocation.

The third is failure containment. A damaged bitmap or descriptor corrupts one group’s accounting rather than the volume’s. Repair tools can work group by group, and the format can carry redundant descriptor copies so that a damaged table is reconstructible.

The cost is that free space becomes fragmented at the group level. A group with 3 free blocks and a group with 20000 free blocks are both “free space” to a total-space calculation, but only one of them can satisfy a request for a contiguous extent. Allocation policy therefore has to choose between first-fit in a mostly-empty group and best-fit across groups, and the choice changes fragmentation more than any single block-selection rule.

The descriptor table’s second life

The table is itself metadata that must be allocated somewhere, and it grows with the number of groups, which grows with the volume size. In the original layout it is a contiguous array in the blocks immediately following the superblock’s block, and its size is groups × descriptor_size / block_size. With 32768 groups and 32-byte descriptors the array is 1 MiB, or 256 blocks at a 4 KiB block size, and a volume large enough to need that many groups reserves the run at creation time so it is never handed out as data space.

ext4’s meta block group feature takes a different approach. It groups several block groups into a meta group and places the superblock and a single descriptor block at the start of the first, second, and last group of each meta group. The descriptor table is therefore no longer one array at the front of the volume; it is a set of blocks scattered at computable positions, so finding the descriptors for group g means determining which meta group contains it and then reading the right block within that meta group. That removes the long reserved run at the front, which matters because the front of a volume is where the busiest metadata wants to live, but it makes descriptor access depend on a computation rather than a base pointer plus an index. A driver that expected the contiguous array would read group data where it expects descriptors, which is why the feature is an incompat bit.

A related feature, flexible block groups, attacks the same problem from the allocation side: it packs the bitmaps and inode tables of several groups into one contiguous run in the first group of the flex group, so a single read can bring in metadata for many groups. The two features are independent and can be enabled together.

Allocation policy as a heuristic over groups

The group layout enables policies that a flat allocator cannot express. For a new directory, a filesystem prefers to place it in a group with a low directory-to-inode ratio and above-average free space, so that the files under it have room nearby. For a new file, it prefers the group of the parent directory, so that the entry and the inode land together. For a new block of an existing file, it prefers the group of the previous block, so that sequential reads stay sequential.

Those preferences are heuristics with no correctness weight; the filesystem is valid regardless of which group anything lands in. What they buy is the difference between a file whose blocks are contiguous and one whose blocks are scattered across the volume. On rotating media that difference is the whole performance story. On flash it is smaller but not zero, because contiguity still reduces the number of mapping-table entries and the number of commands a device must handle.

The inode-number encoding makes the preference cheap to implement. Group g’s inodes occupy a contiguous range of inode numbers, so a driver holding an inode number can compute its group with one division and no lookup, as described in Inode Tables and the Arithmetic of Inode Numbers. The same arithmetic in reverse lets the allocator pick a group and then a free inode within it.

Where the grouping stops helping

Groups are a locality mechanism tuned to a disk whose seek cost is proportional to distance and whose capacity is measured in tens of gigabytes. On a device with hundreds of thousands of groups, the descriptor table becomes a metadata object in its own right, and on a device where seek cost is uniform, locality buys nothing but the allocator still pays the bookkeeping. The flexible-group feature addresses the first problem by bundling several groups under one set of bitmaps so the table shrinks; the second has no format-level answer, which is why allocation policy on flash tends toward writing sequentially into whatever is free rather than toward placing data near its inode.

The durable part of the design is the separation of authority: bitmaps say what is free, descriptors cache the count, and the superblock says how the groups are numbered. A driver that treats the counter as authoritative will eventually allocate a block that the bitmap marks in use, and the resulting corruption is one of the standard cases a repair tool has to handle.