Physical page frame allocation with bitmap algorithms

by @Jonathan Salwan - 2013-02-03

In this short note, we will see how to an Operating System can manage its physical pages frame. When OS needs to allocate a physical page in memory, it needs to know which pages are used or not. We can find a several algorithms for manage these pages.

List
Classical table
Bits map
Others...

The list take up alot of place in memory, the classical table take N bytes to N pages and the bitmap takes up very little space (N/8 bytes to N pages). In the bitmap, when a bit is set to 1, the page is used and 0 the page is free. With 1 octet the OS can manage 8 pages.

The following diagram represents the bitmap design.

With the bitmap it's easy to manage our physical pages. Check the following functions and diagram. These functions are not optimized but can give you ideas.

/* 32 bytes = 256 pages monitoring */
static char pageBitMap[32];


/* Return 0 to FREE, otherwise 1 to USED */
int getPageStatus(int pageNumber)
{
  if (pageNumber < 8)
    return ((pageBitMap[0] >> pageNumber) & 1);
  return ((pageBitMap[pageNumber/8] >> pageNumber % 8) & 1);
}


/*
** Return page number and set USED flag,
** if FREE page isn't available, -1 is returned
*/
int getFreePage(void)
{
  int i, x;

  for (i = 0; i < sizeof(pageBitMap) ; i++)
    for (x = 0 ; x < 8 ; x++)
      if (!((pageBitMap[i] >> x) & 1))
        return ((i * 8) + x);
  return -1;
}


/* Set USED flag on pageNumber, -1 is returned if page is already USED */
int setPageIsUsed(int pageNumber)
{
  if (getPageStatus(pageNumber))
    return -1;
  pageBitMap[pageNumber/8] |= 1 << (pageNumber % 8);
  return 0;
}


/* Set FREE flag on pageNumber, -1 is returned if page is already FREE */
int setPageIsFree(int pageNumber)
{
  if (!getPageStatus(pageNumber))
    return -1;
  pageBitMap[pageNumber/8] &= ~(1 << (pageNumber % 8));
  return 0;
}


/* Return number of pages which is Used */
int howManyPagesIsUsed(void)
{
  int i, x, cpt = 0;

  for (i = 0; i < sizeof(pageBitMap) ; i++)
    for (x = 0 ; x < 8 ; x++)
      cpt += (pageBitMap[i] >> x) & 1;
  return cpt;
}


/* Return number of pages which is Free */
int howManyPagesIsFree(void)
{
  int i, x, cpt = 0;

  for (i = 0; i < sizeof(pageBitMap) ; i++)
    for (x = 0 ; x < 8 ; x++)
      cpt += !((pageBitMap[i] >> x) & 1);
  return cpt;
}

There are algorithms (O(1)) which counts number of bit set to 1 in 32 bit value. See the following Java code.

/**
 * Counts number of 1 bits in a 32 bit unsigned number.
 *
 * @param x unsigned 32 bit number whose bits you wish to count.
 *
 * @return number of 1 bits in x.
 * @author Roedy Green email
 */
public static int countBits( int x )
{
   // collapsing partial parallel sums method
   // collapse 32x1 bit counts to 16x2 bit counts, mask 01010101
   x = (x >>> 1 & 0x55555555) + (x & 0x55555555);

   // collapse 16x2 bit counts to 8x4 bit counts, mask 00110011
   x = (x >>> 2 & 0x33333333) + (x & 0x33333333);

   // collapse 8x4 bit counts to 4x8 bit counts, mask 00001111
   x = (x >>> 4 & 0x0f0f0f0f) + (x & 0x0f0f0f0f);

   // collapse 4x8 bit counts to 2x16 bit counts
   x = (x >>> 8 & 0x00ff00ff) + (x & 0x00ff00ff);

   // collapse 2x16 bit counts to 1x32 bit count
   return (x >>> 16) + (x & 0x0000ffff);
}

If your Operating System is running on Intel x86 with SSE4, you can use POPCNT instruction to optimize your algorithms. This instruction calculates of number of bits set to 1 in the second operand (source) and returns the count in the first operand (a destination register).