exercise for g1n

bitmap_pfa.c

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

// pretend for a moment we have a system with 4096 contiguous pages
#define NPAGES 4096U

// we are using uint32_t for our bitmap entries, so each entry has 32 bits
#define ENTRY_WIDTH 32U

// we are working with 4KiB pages
#define PAGE_SIZE 0x1000U

// so we make an array of 4096 bits, that is 128 elements of 32 bits
static uint32_t bitmap[NPAGES/ENTRY_WIDTH];

// addresses are also 32 bits, but they could be something else. so abstract it away
typedef uint32_t page_addr;

// allocating a page now
page_addr alloc_page(void)
{
  // step 1: we need to find an element in the array that indexes an available page
  size_t bitmap_index;
  size_t element_index;
  size_t page_frame_number;
  
  for (bitmap_index = 0; bitmap_index < NPAGES/ENTRY_WIDTH; bitmap_index++)
  {
    // we have found an entry in the bitmap that indexes at least 1 available page.
    if (bitmap[bitmap_index] != 0) break;
  }
  // step 2: we need to scan the element for its first set bit
  for (element_index = 0; element_index < ENTRY_WIDTH; element_index++)
  {
    // we have found a set bit, this represents the next available page
    if (bitmap[bitmap_index] & (1U << element_index) != 0) break;
  }
  // step 3: unset the corresponding bit to mark it used.
  bitmap[bitmap_index] &= ~(1U << element_index);
  // step 4: calculate the page frame number
  page_frame_number = bitmap_index * ENTRY_WIDTH + element_index;
  // step 5: calculate the address for the page frame number and return.
  return page_frame_number * PAGE_SIZE;
}