Using Virtual Box to Run Configured Image of Ubuntu Linux
We will be using VirtualBox to run a fully configured image of Ubuntu Linux with all the development environment tools pre-installed. The image is 64-bit, so it is required to have a processor capable of 64-bit guest OS emulation. Note that the 64-bit requirement does not mean your host image has to be 64 bit. You can have Windows 7 32-bit and still have a 64-bit processor. VirtualBox is available for Windows, Linux, and Mac OS environments. Please find included a link to a zipped folder of the Ubuntu Linux image as well as for instructions for using the same.
Link: https://www.dropbox.com/s/r7i5dr8z5t4smpc/Setting%20up%20the%20Development%20Environment.zip?dl=0 The essence of this project is to first set up the page table correctly and then to implement the method PageTable::handlefault(), which will handle the page-fault exception of the CPU. This method will look up the appropriate entry in the page table and decide how to handle the page fault. If there is no physical memory (frame) associated with the page, an available frame is brought in and the page-table entry is updated. If a new page-table page has to be initialized, a frame is brought in for that, and the new page table page and the directory are updated accordingly.
Page table and Page-fault handler design
The implementation of the page table was done using the PageTable class definition in the page_table.H and the notes for the paging on the x86. The page table initialization saves the two memory pools available in the system, the kernel pool and the process pool and also saves the amount of shared memory in the system (lowest 4MB). Once the pools are set, we can create a PageTable object to start paging. The PageTable constructor allocates a frame in the kernel pool for saving the page directory. All the pages tables in the page directory are initialized as not present, with the exception of the first, which corresponds to the lowest 4MB in memory and is assumed to be always available. At the same time, a frame is allocated in the kernel pool in order to save the page table for the lowest 4MB. All the entries in this table are initialized to point to the corresponding consecutive addresses in memory. All these pages are also set as supervisor, read/write and present. The address for this page table is saved in the first entry of the page directory. Once the object is created, we load the newly allocated page directory to the cr3 register using the load() function, which also saves the current object in a static variable. The last initialization step is enabling paging, this is done in the function enable_paging(), which sets the corresponding bit in the cr0 register allowing the cpu to start using paging.
In order to hande the page faults, the function handle_fault() was implemented. The faulting address is read from the cr2 register and the kind of fault is taken from the REGS parameter given to the function. If a protection fault is detected, we print a message and abort. If the page is not present then we get the number of page table and the number of page from the faulting address. If the page table is not present, then we allocate a new frame in the kernel pool for the page table and initialize all entries to not present, we save the address of this frame in the corresponding position in the page directory and set its entry to present. Then, if the page is not present, we allocate another frame for the page, save its address in the corresponding position in the page table and set it to present. After all these steps the handler simply returns, allowing the cpu to retry loading the page.
Cont_frame Pool
/*--------------------------------------------------------------------------*/
/*
POSSIBLE IMPLEMENTATION
-----------------------
The class SimpleFramePool in file "simple_frame_pool.H/C" describes an
incomplete vanilla implementation of a frame pool that allocates
*single* frames at a time. Because it does allocate one frame at a time,
it does not guarantee that a sequence of frames is allocated contiguously.
This can cause problems.
The class ContFramePool has the ability to allocate either single frames,
or sequences of contiguous frames. This affects how we manage the
free frames. In SimpleFramePool it is sufficient to maintain the free
frames.
In ContFramePool we need to maintain free *sequences* of frames.
This can be done in many ways, ranging from extensions to bitmaps to
free-lists of frames etc.
IMPLEMENTATION:
One simple way to manage sequences of free frames is to add a minor
extension to the bitmap idea of SimpleFramePool: Instead of maintaining
whether a frame is FREE or ALLOCATED, which requires one bit per frame,
we maintain whether the frame is FREE, or ALLOCATED, or HEAD-OF-SEQUENCE.
The meaning of FREE is the same as in SimpleFramePool.
If a frame is marked as HEAD-OF-SEQUENCE, this means that it is allocated
and that it is the first such frame in a sequence of frames. Allocated
frames that are not first in a sequence are marked as ALLOCATED.
NOTE: If we use this scheme to allocate only single frames, then all
frames are marked as either FREE or HEAD-OF-SEQUENCE.
NOTE: In SimpleFramePool we needed only one bit to store the state of
each frame. Now we need two bits. In a first implementation you can choose
to use one char per frame. This will allow you to check for a given status
without having to do bit manipulations. Once you get this to work,
revisit the implementation and change it to using two bits. You will get
an efficiency penalty if you use one char (i.e., 8 bits) per frame when
two bits do the trick.
DETAILED IMPLEMENTATION:
How can we use the HEAD-OF-SEQUENCE state to implement a contiguous
allocator? Let's look a the individual functions:
Constructor: Initialize all frames to FREE, except for any frames that you
need for the management of the frame pool, if any.
get_frames(_n_frames): Traverse the "bitmap" of states and look for a
sequence of at least _n_frames entries that are FREE. If you find one,
mark the first one as HEAD-OF-SEQUENCE and the remaining _n_frames-1 as
ALLOCATED.
release_frames(_first_frame_no): Check whether the first frame is marked as
HEAD-OF-SEQUENCE. If not, something went wrong. If it is, mark it as FREE.
Traverse the subsequent frames until you reach one that is FREE or
HEAD-OF-SEQUENCE. Until then, mark the frames that you traverse as FREE.
mark_inaccessible(_base_frame_no, _n_frames): This is no different than
get_frames, without having to search for the free sequence. You tell the
allocator exactly which frame to mark as HEAD-OF-SEQUENCE and how many
frames after that to mark as ALLOCATED.
needed_info_frames(_n_frames): This depends on how many bits you need
to store the state of each frame. If you use a char to represent the state
of a frame, then you need one info frame for each FRAME_SIZE frames.
A WORD ABOUT RELEASE_FRAMES():
When we releae a frame, we only know its frame number. At the time
of a frame's release, we don't know necessarily which pool it came
from. Therefore, the function "release_frame" is static, i.e.,
not associated with a particular frame pool.
This problem is related to the lack of a so-called "placement delete" in
C++. For a discussion of this see Stroustrup's FAQ:
http://www.stroustrup.com/bs_faq2.html#placement-delete
*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/* DEFINES */
/*--------------------------------------------------------------------------*/
/* -- (none) -- */
/*--------------------------------------------------------------------------*/
/* INCLUDES */
/*--------------------------------------------------------------------------*/
#include "cont_frame_pool.H"
#include "console.H"
#include "utils.H"
#include "assert.H"
/*--------------------------------------------------------------------------*/
/* DATA STRUCTURES */
/*--------------------------------------------------------------------------*/
/* -- (none) -- */
/*--------------------------------------------------------------------------*/
/* CONSTANTS */
/*--------------------------------------------------------------------------*/
/* -- (none) -- */
/*--------------------------------------------------------------------------*/
/* FORWARDS */
/*--------------------------------------------------------------------------*/
/* -- (none) -- */
/*--------------------------------------------------------------------------*/
/* METHODS FOR CLASS C o n t F r a m e P o o l */
/*--------------------------------------------------------------------------*/
intContFramePool::npools = 0; // initialize number of saved pools to zero
ContFramePool* ContFramePool::pools[2] = {NULL, NULL}; // initialize pool pointers
ContFramePool::ContFramePool(unsigned long _base_frame_no,
unsigned long _n_frames,
unsigned long _info_frame_no,
unsigned long _n_info_frames)
{
ContFramePool::pools[ContFramePool::npools++] = this; // save pool
// initialize members
base_frame_no = _base_frame_no;
nframes = _n_frames;
nFreeFrames = _n_frames;
info_frame_no = _info_frame_no;
// If _info_frame_no is zero then we keep management info in the first
//frame, else we use the provided frame to keep management info
if(info_frame_no == 0) {
info_frame_no = base_frame_no;
_n_info_frames = needed_info_frames(nframes); // number of frames required
}
bitmap = (unsigned char *) (info_frame_no * FRAME_SIZE);
// Mark all frames as free (11)
for(inti=0; i*4
bitmap[i] = 0xFF;
}
// Mark the info frames as being used only if the info frames are not given
if (info_frame_no == base_frame_no)
mark_inaccessible(info_frame_no, _n_info_frames);
}
unsigned long ContFramePool::get_frames(unsigned int _n_frames)
{
// Any frames left to allocate?
assert(nFreeFrames> 0);
// Find a frame that is not being used and return its frame index.
// Mark that frame as being used in the bitmap.
unsignedintframe_no = base_frame_no;
int byte = 0;
int bit = 6; // bit number
intstart_byte = byte;
intstart_bit = bit;
intnfree = 0;
// Find a sequence of free frames
while (nfree != _n_frames&& byte*4
// find a free frame
while (((bitmap[byte] >> bit) & 3) != FREE && byte*4
bit -= 2; // advance to next bit pair
if (bit < 0) { // if we completed a byte
byte++; // advance to next byte
bit = 6; // use leftmost bit pair
}
}
start_byte = byte;
start_bit = bit;
// find free frames
while (((bitmap[byte] >> bit) & 3) == FREE && byte*4
bit -= 2; // advance to next bit pair
if (bit < 0) { // if we completed a byte
byte++; // advance to next byte
bit = 6; // use leftmost bit pair
}
nfree++;
if (nfree == _n_frames)
break;
}
}
assert(nfree == _n_frames);
frame_no += start_byte * 4 + (6 - start_bit) / 2;
// Mark the frames as being used
mark_inaccessible(frame_no, _n_frames);
nFreeFrames -= _n_frames;
return (frame_no);
}
voidContFramePool::mark_inaccessible(unsigned long _base_frame_no,
unsigned long _n_frames)
{
// Let's first do a range check.
assert ((_base_frame_no>= base_frame_no) && (_base_frame_no + _n_frames<= base_frame_no + nframes));
int byte = (_base_frame_no - base_frame_no) / 4;
int bit = 6 - ((_base_frame_no - base_frame_no) % 4) * 2; // bit number
// Is the frame being used already?
assert((bitmap[byte] >> bit) & 3 == FREE);
// Mark the frames as being used
for(inti = 0; i< _n_frames; i++) {
bitmap[byte] &= ~(3 << bit); // clear bits used by frame (mark as free)
if (i> 0) {
bitmap[byte] |= (ALLOCATED << bit); // set as allocated
}
bit -= 2; // advance to next bit pair
if (bit < 0) { // if we completed a byte
byte++; // advance to next byte
bit = 6; // use leftmost bit pair
// Is the frame being used already?
if (i< _n_frames - 1)
assert((bitmap[byte] >> bit) & 3 == FREE);
}
}
nFreeFrames -= _n_frames;
}
voidContFramePool::_release_frames(unsigned long _first_frame_no)
{
int byte = (_first_frame_no - base_frame_no) / 4;
int bit = 6 - ((_first_frame_no - base_frame_no) % 4) * 2; // bit number
assert(((bitmap[byte] >> bit) & 3) == HEAD_OF_SEQUENCE);
bitmap[byte] &= ~(3 << bit);
bitmap[byte] |= (ALLOCATED << bit); // change state to enter loop
// Mark frame sequence as free
while(byte*4
if (((bitmap[byte] >> bit) & 3) == FREE
|| ((bitmap[byte] >> bit) & 3) == HEAD_OF_SEQUENCE) {
break; // if we find a free frame or other sequence, end
}
bitmap[byte] |= (FREE << bit); // set frame bits as free
bit -= 2; // advance to next bit pair
if (bit < 0) { // if we completed a byte
byte++; // advance to next byte
bit = 6; // use leftmost bit pair
}
nFreeFrames++;
}
}
voidContFramePool::release_frames(unsigned long _first_frame_no)
{
// find pool
inti;
for (i = 0; i
if (_first_frame_no>= ContFramePool::pools[i]->base_frame_no&&
_first_frame_nobase_frame_no +
ContFramePool::pools[i]->nframes) {
break;
}
}
assert(i
// call corresponding pool's release function
pools[i]->_release_frames(_first_frame_no);
}
unsigned long ContFramePool::needed_info_frames(unsigned long _n_frames)
{
return ((_n_frames>> 2) - 1) / FRAME_SIZE + 1; // number of frames required
}
Page Table. C
#include "assert.H"
#include "exceptions.H"
#include "console.H"
#include "paging_low.H"
#include "page_table.H"
PageTable * PageTable::current_page_table = NULL;
unsignedintPageTable::paging_enabled = 0;
ContFramePool * PageTable::kernel_mem_pool = NULL;
ContFramePool * PageTable::process_mem_pool = NULL;
unsigned long PageTable::shared_size = 0;
voidPageTable::init_paging(ContFramePool * _kernel_mem_pool,
ContFramePool * _process_mem_pool,
const unsigned long _shared_size)
{
PageTable::kernel_mem_pool = _kernel_mem_pool;
PageTable::process_mem_pool = _process_mem_pool;
PageTable::shared_size = _shared_size;
Console::puts("Initialized Paging System\n");
}
PageTable::PageTable()
{
assert(PageTable::kernel_mem_pool != NULL);
unsigned long frame = PageTable::kernel_mem_pool->get_frames(1); // get frame for directory
page_directory = (unsigned long *) (frame * PAGE_SIZE);
frame = PageTable::kernel_mem_pool->get_frames(1); // get frame for first page
unsigned long *page_table = (unsigned long *) (frame * PAGE_SIZE);
// initialize first 4MB
for (inti = 0; i< ENTRIES_PER_PAGE; i++)
{
page_table[i] = i<< 12; // set frame number
page_table[i] |= 3; // mark as supervisory, present and read/write
}
page_directory[0] = frame << 12; // set page table frame
page_directory[0] |= 3; // mark as supervisory, present and read/write
// set all other entries in directory as not present, address 0
for (inti = 1; i< ENTRIES_PER_PAGE; i++)
{
page_directory[i] = 0 | 2; // mark as supervisory, not present and read/write
}
Console::puts("Constructed Page Table object\n");
}
voidPageTable::load()
{
assert(page_directory != NULL);
write_cr3((unsigned long) page_directory); // write our page directory
PageTable::current_page_table = this;
Console::puts("Loaded page table\n");
}
voidPageTable::enable_paging()
{
write_cr0(read_cr0() | 0x80000000); // set the paging bit in CR0 to 1
Console::puts("Enabled paging\n");
}
voidPageTable::handle_fault(REGS * _r)
{
unsigned long address = read_cr2(); // get faulting address
if (_r->err_code& 1) // protection error
{
Console::puts("MEMORY PROTECTION ERROR\n");
abort();
}
unsigned long table = address >> 22; // get page table number
unsigned long page = (address >> 12) & (ENTRIES_PER_PAGE - 1); // get page number
unsigned long *page_table;
if (!(current_page_table->page_directory[table] & 1)) // if page table is not present
{
// create new frame for page table
unsigned long frame = PageTable::kernel_mem_pool->get_frames(1); // get frame for page table
current_page_table->page_directory[table] = frame << 12; // save frame for page table
current_page_table->page_directory[table] |= 3; // mark as supervisory, present and read/write
page_table = (unsigned long *) (frame * PAGE_SIZE);
for (inti = 0; i< ENTRIES_PER_PAGE; i++)
{
page_table[i] = 0 | 6; // mark as user, not present and read/write
}
}
// get the page address from the page directory, clearing the lowest bits
page_table = (unsigned long *) (current_page_table->page_directory[table] & ~(PAGE_SIZE - 1));
if (!(page_table[page] & 1)) // if page is not present
{
// create new frame for page
unsigned long frame = PageTable::process_mem_pool->get_frames(1); // get frame for page
page_table[page] = frame << 12; // save frame for page
page_table[page] |= 1; // mark as present
}
}