Bitmaps in the Linux Kernel

This text explains how Linux represents and manipulates bit arrays (bitmaps) as a compact, high-performance data structure for tracking many binary states. It argues that bitmaps are pervasive in the kernel because they store presence/availability flags very compactly and exploit machine-word operations for speed. Basic operations - set, clear, test and finding the first set/clear bit - are described, along with their benefits over arrays of booleans or linked lists. Common uses such as interrupt vector allocation and CPU masks illustrate why tight memory usage and bit-level parallelism matter in kernel code.

The implementation details show that a bitmap is simply an array of unsigned long, with DECLARE_BITMAP and BITS_TO_LONGS converting a required bit count into the needed number of words. Examples include a 256-entry interrupt vector bitmap that occupies four machine words and cpumask structures that embed a bitmap. Bit indexing is done by computing the word index and bit offset (using macros like BIT_WORD and BIT_MASK), and single-bit operations call architecture-specific primitives (arch_set_bit) often wrapped with sanitizer instrumentation (e.g., set_bit calls instrument_atomic_write). Whole-bitmap routines scan a word at a time to locate bits efficiently and leverage CPU instructions where available.