Understanding Linux Kernel Bitmap Data Structure and Its APIs

When using Linux, resource constraints and performance issues can often be addressed with the bitmap data structure, which provides a compact and efficient way to manage binary states of resources within the kernel.

1. Bitmap Overview

Bitmaps are widely used in driver development and the Linux kernel to manage resources. They represent availability with 0 (free) and 1 (used) and are supported by many kernel APIs for common operations.

Typical examples include used_vectors for interrupt handling and cpumask for CPU online status. Core bitmap files are include/linux/bitmap.h , lib/bitmap.c , lib/find_next_bit.c , include/linux/bitops.h , and architecture‑specific arch/x86/include/asm/bitops.h .

2. Bitmap Definition

2.1 Simple Declaration

A bitmap can be declared as an array of unsigned long , e.g., unsigned long my_bitmap[8]; , where each bit represents a resource.

2.2 Macro Declaration

The kernel provides the DECLARE_BITMAP(name, bits) macro, which expands to unsigned long name[BITS_TO_LONGS(bits)] . Supporting macros include:

#define BITS_PER_BYTE 8
#define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))
#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))

For example, DECLARE_BITMAP(my_bitmap, 64) results in a single unsigned long on a 32‑bit system.

3. Bitmap‑Related Assembly Instructions

Typical assembly snippets for bit manipulation include:

; set bit
mov eax, [bitmap_address]
or byte ptr [eax], 1 << ebx ; set bit ebx

; clear bit
mov eax, [bitmap_address]
and byte ptr [eax], ~(1 << ebx) ; clear bit ebx

; test bit
mov eax, [bitmap_address]
test byte ptr [eax], 1 << ebx ; check bit ebx
jz not_set

; toggle bit
mov eax, [bitmap_address]
xor byte ptr [eax], 1 << ebx ; flip bit ebx

4. Bitmap API Details

4.1 set_bit

Prototype: void set_bit(int nr, volatile unsigned long *addr); Sets the specified bit to 1.

#include <stdio.h>
#include <asm/types.h>
int main() {
    volatile unsigned long my_bitmap = 0;
    set_bit(2, &my_bitmap); // set third bit
    printf("The bitmap after setting bit: 0x%lx\n", my_bitmap);
    return 0;
}

4.2 test_bit

Prototype: int test_bit(int nr, const volatile unsigned long *addr); Returns non‑zero if the bit is set.

#include <stdio.h>
#include <asm/types.h>
int main() {
    volatile unsigned long process_bitmap = 0x10; // bit 4 set
    int result = test_bit(4, &process_bitmap);
    if (result) printf("The bit is set (value is 1).\n");
    else printf("The bit is not set (value is 0).\n");
    return 0;
}

4.3 Other Interfaces

Additional useful functions include clear_bit , change_bit , test_and_set_bit , test_and_clear_bit , test_and_change_bit , and traversal macros such as for_each_set_bit and for_each_clear_bit .

5. Bit Operations

Core inline functions:

__set_bit(int nr, volatile unsigned long *addr)

__clear_bit(int nr, volatile unsigned long *addr)

__change_bit(int nr, volatile unsigned long *addr)

test_bit(int nr, const volatile unsigned long *addr)

Traversal helpers include find_first_zero_bit , find_next_zero_bit , find_first_bit , and find_next_bit , each returning the index of the matching bit.

6. Bitmap Applications

6.1 PID Allocation

The kernel uses a bitmap to track allocated PIDs. Allocating a PID involves finding the first zero bit and setting it:

#include <linux/bitmap.h>
#include <linux/bitops.h>
#define PID_BITMAP_LEN 1024
DECLARE_BITMAP(pid_bitmap, PID_BITMAP_LEN);
int allocate_pid() {
    int index = find_first_zero_bit(pid_bitmap, PID_BITMAP_LEN);
    if (index < PID_BITMAP_LEN) {
        __set_bit(index, pid_bitmap);
        return index;
    }
    return -1;
}
void release_pid(int pid) {
    if (pid >= 0 && pid < PID_BITMAP_LEN) __clear_bit(pid, pid_bitmap);
}

6.2 Buddy System in Memory Management

The buddy allocator uses a bitmap to record the status of memory blocks. A zero bit indicates a free block that can be merged with its buddy.

typedef struct free_area_struct {
    struct list_head free_list;
    unsigned int *map; // bitmap of buddy blocks
} free_area_t;
int can_merge_buddies(free_area_t *area, int index) {
    int bit_status = test_bit(index, area->map);
    return bit_status == 0;
}

6.3 Debugging

A debug interface can expose a bitmap via sysfs to view and modify resource usage.

#include <linux/bitmap.h>
#include <linux/bitops.h>
#define BITMAP_LEN 128
DECLARE_BITMAP(Test, BITMAP_LEN);
static ssize_t bitmap_debug_get_usable_index(struct device *dev,
                                              struct device_attribute *attr,
                                              char *buf) {
    uint16 index = find_first_zero_bit(Test, 128);
    printk("\n   index:%d\r\n", index);
    return 0;
}
static ssize_t bitmap_debug_set_used_index(struct device *dev,
                                            struct device_attribute *attr,
                                            const char *buf, size_t count) {
    uint32 start, end, index, old;
    sscanf(buf, "%u%u", &start, &end);
    for (index = start; index <= end; index++)
        old = test_and_set_bit(index, Test);
    return count;
}

7. Real‑World Case Studies

7.1 Device Management in Data Centers

Each server is represented by a bit; set_bit marks a server as busy, clear_bit frees it, and find_first_zero_bit quickly finds an idle server.

7.2 Network Port Monitoring

Ports are tracked with a bitmap; setting a bit indicates an active connection, while testing and clearing bits detect disconnections.

7.3 File‑System Block and Inode Allocation

Ext2 uses block and inode bitmaps to allocate and free disk blocks and inodes efficiently.