The following two windows contain the source code for a Multi-level page table which I used as part of my operating system for class. It implements a 2-dimensional array of pointers to page table entries. Since it is a page table, we can expand it only a page at a time. That is, the outer array grows by one element, and that one element will be a pointer to an array that is big enough to fit into one frame of memory. (That size is calculated at compile time.)
DISCLAIMER: To anyone who would like to use this code for their CS354 assignment: The school keeps all source code for a little while (i.e. as long as assignment specs are similar), and compares it to all new assignments. (They also check it with your classmates' assignments) You will receive the standard mark of MINUS ONE HUNDRED PERCENT for plagarism!

/*
 * A class that defines a multi-level page table, addressable as a flat table
 *
 * Written by Giovanni Bernardi
 */
#ifndef MLPTABLE_H
#define MLPTABLE_H

#include "PageTableEntry.h"
#include "machine.h"

class MLPTable
{
 public:
  MLPTable(int numPages);                 // construct a MLPT with numPages entries
  ~MLPTable();                            // destructor
  PageTableEntry * getPTE( int pageNum ); // return a pointer to a PTE
  PageTableEntry * operator[](int);       // same as above, using []
  int addEntry(int size);                 // we need to expand the virtual address space
  int numPages();                         // returns the number of allocated PTE's

 private:

  int innerLevelLength;   // the length of the outer page table
  int outerLevelLength;   // the length of the inner page table
  int lastUsedPage;       // the last page number that is used

  PageTableEntry *** outerLevel; // the outer page table

  void expandOuter();    // add another inner pageTable to the outer page table
};

#endif

         

/*
 * A class that defines a multi-level page table
 * Written by Giovanni Bernardi
 */

#include "MLPTable.h"

MLPTable::MLPTable(int numPages)    // construct a MLPT with numPages entries
{
  // the last used page will be the number of pages we are asked for
  lastUsedPage = numPages;
  
  // in a real OS, we would like each inner page table to fit into 
  // a frame, so here we calculate how many we could fit, and make that
  // the length of the inner page table
  //sizeof(PageTableEntry *) is used because the PTEs in this table are just pointers
  innerLevelLength = divRoundDown(PageSize, sizeof(PageTableEntry *));

  //cout << "Page size is " << PageSize << " and PTEsize is " << sizeof(PageTableEntry *) << endl;
  
  // we need enough outer level entries to handle all the inner page tables
  outerLevelLength = divRoundUp(numPages, innerLevelLength);
  
  // initialize the outer level pointer
  outerLevel = new (PageTableEntry**)[outerLevelLength];
  
  // initialize all the inner page tables, and their entries
  for( int i=0; i< outerLevelLength; i++)
    {
      // initialize the inner table
      outerLevel[i]=new (PageTableEntry*)[innerLevelLength];
      
      // fill the inner table with pointers to PageTableEntries
      for( int j=0; j< innerLevelLength; j++)
         {
            // create a new pageTableEntry
            outerLevel[i][j]=new PageTableEntry;
     
            // initialize all the values of the PageTableEntry
            outerLevel[i][j]->virtualPage  = i*innerLevelLength+j; // virtual memory is 0..n contiguous
            outerLevel[i][j]->physicalPage = -1;   // no physical address until demanded
            outerLevel[i][j]->swapDiskPtr  = -1;   // no swapPtr until we are moved to disk
            outerLevel[i][j]->valid        = false;
            outerLevel[i][j]->use          = false;
            outerLevel[i][j]->dirty        = false;
            outerLevel[i][j]->readOnly     = false; // nothing will be set to readonly until loaded
            outerLevel[i][j]->startSection = STACK;
            outerLevel[i][j]->endSection   = STACK;
            outerLevel[i][j]->nextFreeAddress = -1;
            outerLevel[i][j]->isOnSwap     = false;
         }
    }
  
}

// destructor
MLPTable::~MLPTable()
{
  // delete all the inner page tables, and their entries
  for( int i=0; i< outerLevelLength; i++)
    {
      
      // delete inner table 
      for( int j=0; j< innerLevelLength; j++)
      {
         // delete a pageTableEntry
         delete outerLevel[i][j];
      }
   
      // delete an inner array
      delete outerLevel[i];
    }

}

// return a pointer to a PTE
// return NULL if pageNum is not in the table
PageTableEntry * 
MLPTable::getPTE( int pageNum ) 
{
  // find the index for the outer table
  int outerIndex = pageNum/innerLevelLength;
  
  // if they gave us a bad address, return NULL
  if(outerIndex>outerLevelLength){ return NULL; }
  
  // find the indes of the page we need in the innerTable
  int innerIndex = pageNum%innerLevelLength;
  
  // return a pointer to the proper PTE
  return outerLevel[outerIndex][innerIndex];
}

PageTableEntry * 
MLPTable::operator[](int pageNum)
{
  return getPTE(pageNum);
}


/* This function is used to add more entries to the page table thus increasing the size of the 
 * logical address space.  Used for on-demand memory allocation
 * pre: size - number of bytes to allocate.
 * post: returns the address of where the memory was allocated. 0 if an error occured. The
 *       logical address space has also increased by size bytes.
 */
// NOTE: This function was not written by me, but by a group member.
int 
MLPTable::addEntry(int size)
{  
  PageTableEntry *tempPage;
  int pagesToAdd = 0;
  int logicalAddress;
  int oldLastUsedPage = lastUsedPage;
  int currentOffset = 0;
  int tempSize = 0;

  
  DEBUG('l', "Allocating " << size << " bytes" );

  if (size < 0) return 0;

  //round the size to the next 4 byte boundary
  if (size % 4 != 0) 
   {
     size += 4 - (size % 4);
     DEBUG('l', "Allocation rounded to next 4 byte boundary " << size);
   }

  tempSize = size;
  tempPage = getPTE(lastUsedPage);

  //check to see if we allocate more memory beginning on a page
  if (tempPage->nextFreeAddress != -1) 
  {
    size -= (PageSize - tempPage->nextFreeAddress);
    DEBUG('l', "Starting on page " << lastUsedPage << " and at offset " << tempPage->nextFreeAddress);
  }

  //check to see if allocation doesn't extend beyond end of page
  if (size < 0) 
  {
    size = tempSize;
    pagesToAdd = 0;
    currentOffset = tempPage->nextFreeAddress;
  }
  else 
  {
    pagesToAdd = divRoundUp(size, PageSize);
  }

  DEBUG('l',  "Number of pages to add is " << pagesToAdd);

  int outerIndex = lastUsedPage/innerLevelLength;

  // find the indes of the page we need in the innerTable
  int innerIndex = lastUsedPage%innerLevelLength;


  DEBUG('l', "last outerindex = " << outerIndex << " innerindex = " << innerIndex << " of "<< innerLevelLength - 1);

  //find current logical address of last page used so it can be returned to user
  if(tempPage->nextFreeAddress == -1)
    logicalAddress = (outerIndex * innerLevelLength) + (innerIndex * PageSize);
  else
    logicalAddress = (outerIndex * innerLevelLength) + (innerIndex * PageSize) + tempPage->nextFreeAddress;

  lastUsedPage += pagesToAdd;

  //check to see if the pages added extend beyond the end of the outerpage
  while (innerIndex + pagesToAdd >= innerLevelLength) 
  {
    pagesToAdd -= innerLevelLength - innerIndex;
    DEBUG('l', "Expanding outer page. Number of page to add left are "<< pagesToAdd );
    expandOuter();
    innerIndex = 0;
  }

  //set the next free address of the final page added to page table
  tempPage = getPTE(lastUsedPage);
  tempPage->nextFreeAddress = size % PageSize + 1 + currentOffset;

 //make sure there is space on swap disk for new pages
  int *tempAddr = new int[lastUsedPage - oldLastUsedPage];
  if (!kernel->vMemManager->reserveSectors(lastUsedPage - oldLastUsedPage, &tempAddr)) {
    //not enough swap space
    return 0;
  }

  for (int i = oldLastUsedPage + 1; i < lastUsedPage; i++ ) {
    getPTE(i)->swapDiskPtr = tempAddr[i - oldLastUsedPage - 1];
  }

  delete tempAddr;
  return logicalAddress;
}


/* private: */

// expand the outer page table and add a new array of PageTableEntries in
// that new space    
void
MLPTable::expandOuter()
{
   outerLevelLength++;  // increment the length of the outer table
   
   // create a new pointer which will point to the outer table
   PageTableEntry *** outerLevel2 = new (PageTableEntry**)[outerLevelLength];
   
   // copy all the pointers from the current outerLevel
   for( int i=0; i< outerLevelLength-1; i++)
   {
      outerLevel2[i]=outerLevel[i];
   }
   
   // create another inner table 
   outerLevel2[outerLevelLength-1]=new (PageTableEntry*)[innerLevelLength];
   

   // populate the new inner table
   for( int j=0; j< innerLevelLength; j++)
   {
      int i = outerLevelLength-1;
      
      outerLevel2[i][j]=new PageTableEntry;
      
      outerLevel2[i][j]->virtualPage  = i*innerLevelLength+j; // virtual mem is 0..n contiguous
      outerLevel2[i][j]->physicalPage = -1;    // no physical address until demanded
      outerLevel2[i][j]->swapDiskPtr  = -1;    // no swapPtr until moved to disk
      outerLevel2[i][j]->valid        = FALSE;
      outerLevel2[i][j]->use          = FALSE;
      outerLevel2[i][j]->dirty        = FALSE;
      outerLevel2[i][j]->readOnly     = FALSE; // not readonly until loaded
      outerLevel2[i][j]->startSection = STACK;
      outerLevel2[i][j]->endSection   = STACK;
    }
   
   // set the old pointer = new pointer;
   outerLevel = outerLevel2;
   
   // for good style, set the new pointer to NULL
   outerLevel2 = NULL;
}

int MLPTable::numPages() 
{
  return lastUsedPage;
}