Managing Physical Memory Frames Using Bit Arrays in C

This article explains how an operating system kernel tracks and manages physical memory frames using bit arrays, commonly known as bitmaps, in the C programming language. It details the memory-efficient representation of physical frame states, the mathematical mapping between memory addresses and bit locations, and the core implementation logic for allocating and freeing physical memory pages.

The Role of Physical Memory Frames and Bitmaps

Physical memory (RAM) is partitioned by the CPU and kernel into fixed-size contiguous blocks called page frames, usually 4 KiB (4,096 bytes) in size. The kernel's physical memory manager (PMM) must keep track of which frames are currently free and which are allocated to processes or kernel subsystems.

Using a full byte or a pointer to track each 4 KiB frame introduces unnecessary memory overhead. A bit array, or bitmap, optimizes this by using a single bit to represent each frame:

  • 0 indicates that the frame is free.
  • 1 indicates that the frame is allocated.

For example, to manage 4 GiB of RAM divided into 4 KiB frames, the system contains \(1,048,576\) frames (\(2^{32} / 4096\)). Tracking these with a bit array requires \(1,048,576\) bits, which equals exactly 128 KiB of memory overhead.

Core Data Structures in C

A kernel implements a bitmap using standard unsigned integer arrays, such as uint32_t or uint64_t. Each array element holds 32 or 64 individual frame states.

#include <stdint.h>
#include <stddef.h>
#include <stdbool.h>

#define PAGE_SIZE 4096
#define BITS_PER_WORD 32

static uint32_t *frame_bitmap;
static size_t total_frames;
static size_t bitmap_size_words;

Mapping Frames to Bitmap Indices

To manipulate a specific frame, the kernel calculates two values:

  1. Word Index: The position in the integer array where the bit resides.
  2. Bit Offset: The specific bit within that integer.

Given a frame number:

  • word_index = frame / BITS_PER_WORD (or frame >> 5 for 32-bit words)
  • bit_offset = frame % BITS_PER_WORD (or frame & 31)

To convert between a physical address and a frame index:

  • frame_index = physical_address / PAGE_SIZE
  • physical_address = frame_index * PAGE_SIZE

Basic Bit Manipulation Functions

The kernel alters and queries state using standard bitwise operators:

static inline void bitmap_set(size_t frame) {
    frame_bitmap[frame / BITS_PER_WORD] |= (1U << (frame % BITS_PER_WORD));
}

static inline void bitmap_clear(size_t frame) {
    frame_bitmap[frame / BITS_PER_WORD] &= ~(1U << (frame % BITS_PER_WORD));
}

static inline bool bitmap_test(size_t frame) {
    return (frame_bitmap[frame / BITS_PER_WORD] & (1U << (frame % BITS_PER_WORD))) != 0;
}

Frame Allocation Logic

When the kernel needs a physical frame, it searches the bitmap for the first bit set to 0.

To maximize performance, the search scans word by word instead of bit by bit. If a word equals 0xFFFFFFFF, all 32 frames in that block are occupied and the loop skips to the next word immediately. When a word with at least one free frame is found, a built-in function like __builtin_ctz (Count Trailing Zeros) rapidly locates the first unset bit.

intptr_t allocate_frame(void) {
    for (size_t i = 0; i < bitmap_size_words; i++) {
        // Skip fully allocated 32-frame blocks
        if (frame_bitmap[i] == 0xFFFFFFFF) {
            continue;
        }

        // Find the first free bit (0) in the word
        uint32_t inverted = ~frame_bitmap[i];
        int bit = __builtin_ctz(inverted);
        size_t frame_index = (i * BITS_PER_WORD) + bit;

        if (frame_index >= total_frames) {
            return -1; // Out of memory
        }

        bitmap_set(frame_index);
        return (intptr_t)(frame_index * PAGE_SIZE);
    }

    return -1; // Out of memory
}

Frame Deallocation Logic

Deallocating a frame is an \(O(1)\) operation. The kernel translates the physical base address back to its frame number, verifies bounds, and clears the corresponding bit.

void free_frame(intptr_t physical_address) {
    size_t frame_index = physical_address / PAGE_SIZE;

    if (frame_index < total_frames) {
        bitmap_clear(frame_index);
    }
}

Performance Characteristics

  • Space Complexity: The bitmap approach achieves theoretical maximum density for single-bit states, requiring only 1 bit per page.
  • Deallocation Time: Deallocation is strictly \(O(1)\) through direct arithmetic indexing.
  • Allocation Time: Allocation is \(O(N)\) in the worst case, as linear scanning is required when memory becomes fragmented. To mitigate this overhead, kernels often maintain a cursor indicating the last known free position, or transition to buddy allocators for larger contiguous allocations.