addrspace.cpp

LINUX 下NACHOS 系统的页面调度算法的实现

// addrspace.cc 
//	Routines to manage address spaces (executing user programs).
//
//	In order to run a user program, you must:
//
//	1. link with the -N -T 0 option 
//	2. run coff2noff to convert the object file to Nachos format
//		(Nachos object code format is essentially just a simpler
//		version of the UNIX executable object code format)
//	3. load the NOFF file into the Nachos file system
//		(if you haven't implemented the file system yet, you
//		don't need to do this last step)
//
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "system.h"
#include "addrspace.h"
#include "memmanager.h"
#include <strings.h>

//----------------------------------------------------------------------
// SwapHeader
// 	Do little endian to big endian conversion on the bytes in the 
//	object file header, in case the file was generated on a little
//	endian machine, and we're now running on a big endian machine.
//----------------------------------------------------------------------

static void 
SwapHeader (NoffHeader *noffH)
{
	noffH->noffMagic = WordToHost(noffH->noffMagic);
	noffH->code.size = WordToHost(noffH->code.size);
	noffH->code.virtualAddr = WordToHost(noffH->code.virtualAddr);
	noffH->code.inFileAddr = WordToHost(noffH->code.inFileAddr);
	noffH->initData.size = WordToHost(noffH->initData.size);
	noffH->initData.virtualAddr = WordToHost(noffH->initData.virtualAddr);
	noffH->initData.inFileAddr = WordToHost(noffH->initData.inFileAddr);
	noffH->uninitData.size = WordToHost(noffH->uninitData.size);
	noffH->uninitData.virtualAddr = WordToHost(noffH->uninitData.virtualAddr);
	noffH->uninitData.inFileAddr = WordToHost(noffH->uninitData.inFileAddr);
}

//----------------------------------------------------------------------
// AddrSpace::AddrSpace
// 	Create an address space to run a user program.
//	Load the program from a file "executable", and set everything
//	up so that we can start executing user instructions.
//
//	Assumes that the object code file is in NOFF format.
//
//	First, set up the translation from program memory to physical 
//	memory.  For now, this is really simple (1:1), since we are
//	only uniprogramming, and we have a single unsegmented page table
//
//	"executable" is the file containing the object code to load into memory
//----------------------------------------------------------------------

AddrSpace::AddrSpace(OpenFile *fileDescriptor)
{
    executable = fileDescriptor;
    executable->ReadAt((char *)&noffH, sizeof(noffH), 0);
    if ((noffH.noffMagic != NOFFMAGIC) && 
		(WordToHost(noffH.noffMagic) == NOFFMAGIC))
    	SwapHeader(&noffH);
    ASSERT(noffH.noffMagic == NOFFMAGIC);

    // Locate the page-ranges of various segments.
    // Note that the ranges may overlap.
    unsigned int i;

    BeginCodePage = divRoundDown(noffH.code.virtualAddr, PageSize);
    EndCodeAddr = noffH.code.size + noffH.code.virtualAddr;
    EndCodePage = divRoundDown(EndCodeAddr, PageSize);
    BeginInitDataPage = divRoundDown(noffH.initData.virtualAddr, PageSize);
    EndInitDataAddr = noffH.initData.virtualAddr + noffH.initData.size;
    EndInitDataPage = divRoundDown(EndInitDataAddr, PageSize); 
    BeginUninitDataPage = divRoundDown(noffH.uninitData.virtualAddr, PageSize);
    EndUninitDataAddr = noffH.uninitData.virtualAddr + noffH.uninitData.size;
    EndUninitDataPage = divRoundDown(EndUninitDataAddr, PageSize);

    if (EndCodePage > EndInitDataPage)
      numPages = (EndCodePage > EndUninitDataPage) ? 
	                  EndCodePage : EndUninitDataPage;
    else
      numPages = (EndInitDataPage > EndUninitDataPage) ?
	                  EndInitDataPage : EndUninitDataPage;

    // Allocate space for stack segment
    BeginStackPage = ++numPages;
    EndStackPage = BeginStackPage + divRoundDown(UserStackSize, PageSize);

    numPages = EndStackPage + 1;
    DEBUG('t', "Initializing address space, num pages %d, size\n", 
					numPages, numPages*PageSize);

    // first, set up the translation table
    // Note that the table does not grow or shrink during execution.
    // This is because syscalls for dynamic memory allocation are not supported.

    pageTable = new TranslationEntry[numPages];

    for (i = BeginInitDataPage; i <= EndInitDataPage; i++)
    {
      pageTable[i].virtualPage = i;
      pageTable[i].valid = FALSE;
      pageTable[i].legal = TRUE;
      pageTable[i].readOnly = FALSE;
    }

    for (i = BeginUninitDataPage; i <= EndUninitDataPage; i++)
    {
      pageTable[i].virtualPage = i;
      pageTable[i].valid = FALSE;
      pageTable[i].legal = TRUE;
      pageTable[i].readOnly = FALSE;
    }

    for (i = BeginCodePage; i <= EndCodePage; i++)
    {
      pageTable[i].virtualPage = i;
      pageTable[i].valid = FALSE;
      pageTable[i].legal = TRUE;
      pageTable[i].readOnly = FALSE;
    }

    for (i = BeginStackPage; i <= EndStackPage; i++)
    {
      pageTable[i].virtualPage = i;
      pageTable[i].valid = FALSE;
      pageTable[i].legal = TRUE;
      pageTable[i].readOnly = FALSE;
    }


    if (BeginCodePage == EndInitDataPage || BeginCodePage == EndUninitDataPage)
      pageTable[BeginCodePage].readOnly = FALSE;
    if (EndCodePage == BeginInitDataPage || EndCodePage == BeginUninitDataPage)
      pageTable[EndCodePage].readOnly = FALSE;

    // References to other pages are all invalid
    for (i = 0; i < numPages; i++)
      if (!(i >= BeginCodePage && i <= EndCodePage) &&
	  !(i >= BeginInitDataPage && i <= EndInitDataPage) &&
	  !(i >= BeginUninitDataPage && i <= EndUninitDataPage)&&
	  !(i >= BeginStackPage && i <= EndStackPage) 
	 )
      {
	pageTable[i].virtualPage = i;
	pageTable[i].valid = FALSE;
	pageTable[i].legal = FALSE;
	pageTable[i].readOnly = FALSE;
      }
	

    // None of the pages is read in initially. So the process 
    // would page fault right away.

}


void AddrSpace::ReadSourcePage(char *buffer, unsigned int virtualPage)
{
  unsigned virtualAddr = virtualPage*PageSize;
  int displacement, numBytes, seek, startAddr;

  if ((virtualPage > BeginStackPage && virtualPage < EndStackPage) ||
      (virtualPage > BeginUninitDataPage && virtualPage < EndUninitDataPage)) 
  {
    return;
  }

  if (virtualPage > BeginCodePage && virtualPage < EndCodePage)
  {
    seek = noffH.code.inFileAddr + virtualAddr - noffH.code.virtualAddr;
    executable->ReadAt(buffer, PageSize, seek);
    return;
  }
  
  if (virtualPage > BeginInitDataPage && virtualPage < EndInitDataPage)
  {
    seek = noffH.initData.inFileAddr + virtualAddr - noffH.initData.virtualAddr;
    executable->ReadAt(buffer, PageSize, seek);
    return;
  }


  if (virtualPage == BeginCodePage)
  {
    displacement = noffH.code.virtualAddr%PageSize;
    if (EndCodePage > BeginCodePage)
      numBytes = PageSize - displacement; 
    else
      numBytes = noffH.code.size;
    seek = noffH.code.inFileAddr;
    executable->ReadAt(buffer+displacement, numBytes, seek);  
  }
  else if (virtualPage == EndCodePage)
  {
    displacement = 0;
    numBytes = EndCodeAddr%PageSize + 1;
    seek = noffH.code.inFileAddr + virtualAddr - noffH.code.virtualAddr;
    executable->ReadAt(buffer+displacement, numBytes, seek);  
  }


  if (virtualPage == BeginInitDataPage)
  {
    displacement = noffH.initData.virtualAddr%PageSize;
    if (EndInitDataPage > BeginInitDataPage)
      numBytes = PageSize - displacement; 
    else
      numBytes = noffH.initData.size;
    seek = noffH.initData.inFileAddr;
    executable->ReadAt(buffer+displacement, numBytes, seek);
  }
  else if (virtualPage == EndInitDataPage)
  {
    displacement = 0;
    numBytes = EndInitDataAddr%PageSize + 1;
    seek = noffH.initData.inFileAddr + virtualAddr - noffH.initData.virtualAddr;
    executable->ReadAt(buffer+displacement, numBytes, seek);
  }

  return;
}

//----------------------------------------------------------------------
// AddrSpace::~AddrSpace
// 	Dealloate an address space. 
//      Also inform the MemoryManager, which did not keep track of
//         which process owned which pages, that this process is dead
//         and its pages should be cleaned up.
//----------------------------------------------------------------------

AddrSpace::~AddrSpace()
{
  machine->memManager->clear(pageTable, numPages);
  delete pageTable;
}


//----------------------------------------------------------------------
// AddrSpace::InitRegisters
// 	Set the initial values for the user-level register set.
//
// 	We write these directly into the "machine" registers, so
//	that we can immediately jump to user code.  Note that these
//	will be saved/restored into the currentThread->userRegisters
//	when this thread is context switched out.
//----------------------------------------------------------------------

void
AddrSpace::InitRegisters()
{
    int i;

    for (i = 0; i < NumTotalRegs; i++)
	machine->WriteRegister(i, 0);

    // Initial program counter -- must be location of "Start"
    machine->WriteRegister(PCReg, 0);	

    // Need to also tell MIPS where next instruction is, because
    // of branch delay possibility
    machine->WriteRegister(NextPCReg, 4);

    // Set the stack register to the end of the address space, where we
    // allocated the stack; but subtract off a bit, to make sure we don't
    // accidentally reference off the end!

    machine->WriteRegister(StackReg, (EndStackPage+1)* PageSize - 16);
    DEBUG('t', "Initializing stack register to %d\n", (EndStackPage+1)* PageSize - 16);
}


//----------------------------------------------------------------------
// AddrSpace::SaveState
// 	On a context switch, save any machine state, specific
//	to this address space, that needs saving.
//
//----------------------------------------------------------------------

void AddrSpace::SaveState() 
{
  pageTable = machine->pageTable;
  numPages = machine->pageTableSize;
}


//----------------------------------------------------------------------
// AddrSpace::RestoreState
// 	On a context switch, restore the machine state so that
//	this address space can run.
//
//      For now, tell the machine where to find the page table.
//----------------------------------------------------------------------

void AddrSpace::RestoreState() 
{
    machine->pageTable = pageTable;
    machine->pageTableSize = numPages;
}