CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 6 of 7 · 3 min read

Block groups

Block groups and running out of inodes

Think of a city divided into districts, each with its own post office, shops and a list of its houses. A family that lives in one district does its errands without crossing the city. The analogy stops in one place: a city can add new districts, while a file system fixes its number of inodes at the time it is made.

In plain words: A large disk is divided into block groups that each have their own bitmaps and part of the inode table. The OS tries to put a file's inode and data in the same group as its directory, so the arm moves less (Level 8, page 1). The number of inodes is chosen when the file system is made, from a ratio such as one inode for every 16 KiB of space. A file system cannot make more inodes than that. When all inodes are used, no new file can be created, even if many data blocks are free.

A worked example. With 4 KiB blocks, one bitmap block has 4,096 x 8 = 32,768 bits, so a group covers 32,768 blocks, which is 128 MiB. A 1 TiB disk then has 2^40 / 2^27 = 8,192 groups. At one inode per 16 KiB it has 2^40 / 16,384 = 67,108,864 inodes, and their 256-byte records need 67,108,864 x 256 = 16 GiB, 1.6% of the disk. A test made the point on a small image: mkfs.ext4 -N 128 on 16 MiB gave 128 inodes, and a loop that created empty files stopped after 117 files. df -i showed 128 of 128 inodes used (100%), while df showed 1% of the blocks used. The other 11 inodes are reserved for the system.

The key lines. When "no space left on device" appears while df shows free space, check df -i. Millions of tiny files can exhaust the inodes long before the blocks. Some file systems, such as XFS and Btrfs, create inodes on demand and have no such fixed limit.

Block group

A block group is a fixed-size range of consecutive blocks in a file system, with its own block bitmap, inode bitmap and share of the inode table. The OS places a file's inode and data near its directory, in the same group when it can.

Example: with 4 KiB blocks, each group covers 32,768 blocks (128 MiB).

Interview angle

A common question is "A disk shows free space but you cannot create files. Why?" A good answer says that the file system may have run out of inodes, and shows df -i to check. It also names the other causes: a quota, a reserved-blocks limit and a read-only mount.

Check yourself: 1. How many blocks does one group cover with 4 KiB blocks and one bitmap block? 2. What fixes the number of inodes in ext4? 3. Which command shows inode use?

Words you will meet

Word Meaning
Superblock Global facts about the file system.
Bitmap One bit for each block or inode: free or used.
Inode table Array of inode records, in order of number.
Extent A run of consecutive blocks: start and length.
Internal fragmentation Unused bytes at the end of a file's last block.

Quick notes

  • A file system has a superblock, group descriptors, bitmaps, an inode table and data blocks.
  • An inode holds type, mode, owner, size, times, link count and block pointers, and no name.
  • Inode N is at table start + (N - 1) x inode size. With 4 KiB blocks and 256-byte inodes: block (N - 1) / 16, offset ((N - 1) mod 16) x 256.
  • A directory entry holds an inode number, a length, a type and a name.
  • Deleting a file changes the entry, the inode and the bitmaps, which are three places.
  • The number of inodes is fixed at mkfs time. df -i shows it.