/*
filename: bayles_hw03.cpp
author: Bo Bayles
assignment: CS 284 Assignment 3
description: This program simulates a virtual memory management system. See
  README for details on how to operate.
*/

/*/////////////////////////////////////////////////////////////////////////////
    Compiler Directives
/////////////////////////////////////////////////////////////////////////////*/
#include <iostream>
#include <fstream>
#include <stdlib.h> //For atoi
#include <iomanip>
using namespace std;

#define MEMORY_SIZE 512
/*/////////////////////////////////////////////////////////////////////////////
    Data type definitions
/////////////////////////////////////////////////////////////////////////////*/
class mainMemory
{
	public:
	    mainMemory( const unsigned int c, const unsigned int s );
	    ~mainMemory();
	    void showQueues( const char replacementPolicy );
	    unsigned int pageCount;
	    unsigned int pageSize;
	    unsigned int clockIndex;
	    int* memoryQueue;
	    bool* clockQueue;
};

struct pageTableEntry
{
    bool valid;
    unsigned int frameNumber;
};

struct process
{
    unsigned int programSize;
    unsigned int pageTableSize;
    unsigned int firstPage;
};

class pageTable
{
	public:
        pageTable::pageTable
            ( const unsigned int programCount, const unsigned int pageSize,
              process* &program);
        pageTable::~pageTable();
        unsigned int tableSize;
        pageTableEntry* table;
};

/*/////////////////////////////////////////////////////////////////////////////
    Function declarations
/////////////////////////////////////////////////////////////////////////////*/
bool checkUsage
    ( int &argc, char** argv, ifstream &programList, ifstream &commandList );

void displayUsage
    ( char** argv);

unsigned int getProgramCount
    ( ifstream &inFile );

void readPrograms
    ( ifstream &inFile, process* &program, unsigned int programCount );

void showDisk
    ( const unsigned int programCount, process* &program,pageTable &diskTable,
      mainMemory &memory );

void loadPage
    ( const unsigned int pageNumber, pageTable &diskTable,
      mainMemory &memory );

void doTrace
    ( ifstream &inFile,  process* &program, const char replacementPolicy,
      const char pagingType, unsigned int &faultCount, pageTable &diskTable,
      mainMemory &memory, const bool verbose );

bool checkFault
    ( const unsigned int pageNumber, pageTable &diskTable );

void clockHit
    ( const unsigned int pageNumber, pageTable &diskTable, 
      mainMemory &memory );

void lruHit
    ( const unsigned int pageNumber, pageTable &diskTable,
      mainMemory &memory );

int clockReplace
    ( const unsigned int pageNumber, pageTable &diskTable,
      mainMemory &memory );

void queueReplace
    ( const unsigned int pageNumber, pageTable &diskTable,
      mainMemory &memory );

/*/////////////////////////////////////////////////////////////////////////////
    Function definitions
/////////////////////////////////////////////////////////////////////////////*/

int main( int argc, char *argv[] )
{
    ifstream programList, commandList;
    //Declare file streams. The files get opened when checked for validity.

    if ( !checkUsage(argc, argv, programList, commandList) )
      return 1;
      //Bail out if the arguments were not good.

    unsigned int pageSize = atoi( argv[3] );
    char replacementPolicy = *argv[4];
    char pagingType = *argv[5];
    bool verbose = false;
    if ( argc == 7 )
        verbose = true;
    //Configure the argument options

    unsigned int pageCount = MEMORY_SIZE / pageSize;
    //The number of pages in main memory is the page size into the memory size.

    mainMemory memory(pageCount, pageSize);
    //Initialize main memory

    unsigned int programCount = getProgramCount(programList);
    //Read some of the file to get the number of programs for sizing arrays.

    process* program = new process[programCount];
    //Instantiate an array of processes

    programList.clear();
    programList.seekg(0, ios::beg);
    readPrograms( programList, program, programCount );
    //Reset the program list file, then read in the sizes of the programs for
    //  further array sizing.

    pageTable diskTable( programCount, memory.pageSize, program );
    //Instantiate the page table structure for the programs in memory

    //INITIAL LOAD:
    int k = 0;
    for(int i = 0; i < programCount; i++)
    //Loading some pages from each program...
    {
        for(int j = 0; j < (pageCount/programCount); j++)
        //...actually, an equal number of pages from each program
        {
            if ( replacementPolicy == 'c' )
            {
                memory.clockQueue[k] = true;
                memory.memoryQueue[k] = program[i].firstPage+j;
                diskTable.table[ program[i].firstPage+j ].valid = true;
                //Manually load in the appropriate pages for the clock policy
            }
            else
            {
              loadPage( program[i].firstPage+j, diskTable, memory );
              //Load in the pages properly for FIFO and LRU
            }
            k++;
            if( k == pageCount )
              break;
        }
    }
    //This won't break, but will behave a little strangely for programs with
    //  sizes that are smaller than the page size. Not a huge deal, since they
    //  would require at most one swap for the whole program, and won't affect
    //  the statistical results to any significant degree.

    //DEBUGGING MESSAGES
    if ( verbose )
    {
        cout << "\nMemory size: " << MEMORY_SIZE << endl
             << "Page size: " << pageSize << endl
             << "Number of memory pages: " << pageCount << endl
             << "Replacement policy: " << replacementPolicy << endl
             << "Paging Type: " << pagingType << endl;

        cout << "\nPROGRAM INFORMATION" << endl;
        for(int i = 0; i < programCount; i++)
        {
            cout << " Program " << i << endl
                 << "   Size : " << program[i].programSize << endl
		         << "   Page count: " << program[i].pageTableSize
		         << "  (Pages " << program[i].firstPage << " to "
                 << (program[i].firstPage)+(program[i].pageTableSize-1) << ")"
                 << endl;
		 }

        cout << "\nINITIAL LOAD" << endl;
        memory.showQueues( replacementPolicy );
    }

    unsigned int faultCount = 0;
    doTrace( commandList, program, replacementPolicy, pagingType,
             faultCount, diskTable, memory, verbose );

    cout << "Fault count was " << faultCount << endl;

    programList.close();
    commandList.close();
    delete [] program;
    //Clean up...

    cout << "\nExiting..." << endl;
    return 0;
}

bool checkUsage
    ( int &argc, char** argv, ifstream &programList, ifstream &commandList )
{
    if(argc != 6 && argc != 7)
    //Not even close to the right usage, so print help message.
    {
        displayUsage(argv);

        return false;
    }
    else //Closer...
    {
        programList.open(argv[1]);
        commandList.open(argv[2]);
        unsigned int pageSize = atoi(argv[3]);
        char replacementPolicy = *argv[4];
        char pagingType = *argv[5];

        char verbosity = 'n';
        if ( argc == 7 )
            verbosity = *argv[6];

        if( programList.fail() || commandList.fail() )
        {
        //But it only makes sense to continue if the first two arguments are
        //  files that can be successfully opened.
            cout << "Error opening files." << endl;

            return false;
        }
        if( pageSize != 2 && pageSize != 4 && pageSize != 8 &&
            pageSize != 16 && pageSize != 32 )
        {
		    cout << "Invalid page size." << endl;
		    displayUsage(argv);

		    return false;
		}
        if( replacementPolicy != 'f' && replacementPolicy != 'l' &&
            replacementPolicy != 'c' )
        {
            cout << "Invalid replacement policy." << endl;
            displayUsage(argv);

            return false;
        }
        if( pagingType != 'd' && pagingType != 'p' )
        {
            cout << "Invalid paging type." << endl;
            displayUsage(argv);

            return false;
        }
        if( argc == 7 && verbosity != 'v' )
        {
		    cout << "Invalid option." << endl;
		    displayUsage(argv);

		    return false;
		}
    }

    return true;
}

void displayUsage( char** argv )
{
    cout << "Virtual memory simulator" << endl
         << "\nUsage: " << argv[0] << " programList commandList pageSize "
         << "replacementPolicy pagingType [v]" << endl
         << "\nprogramlist - file containing a list of programs and "
         << "sizes" << endl
         << "commandList - file containing a list of memory accesses "
         << endl
         << "pageSize - integer that is a power of 2 from 2 to 32" << endl
         << "replacementPolicy - either f for FIFO, l for LRU, or c for clock"
         << endl
         << "pagingType - either d for demand paging or p for pre-paging."
         << endl
         << "[v] - be verbose. This will slow the program execution "
         << "dramatically." << endl;

    return;
}

unsigned int getProgramCount( ifstream &inFile )
{
    unsigned int programNumber, programSize;
    while( !inFile.eof() )
    {
        inFile >> programNumber;
        inFile >> programSize;

        if ( inFile.eof() )
          break;
    }
  return programNumber+1;
}
//getProgramCount really just reads the program list in, looking for the
//  largest program number. There are more graceful ways to do this, but
//  to use the dynamic arrays the way I want to set them up, this works.

void readPrograms( ifstream &inFile, process* &program,
                   unsigned int programCount )
{
    int programNumber;
    for (int i = 0; i < programCount; i++)
    {
        inFile >> programNumber;
        inFile >> program[i].programSize;
    }

    return;
}
//readPrograms reads the program list in for real, storing the program sizes.

mainMemory::mainMemory( const unsigned int c, const unsigned int s )
{
    memoryQueue = new int[c];
    clockQueue = new bool[c];
    for(int i = 0; i < c; i++)
    {
        memoryQueue[i] = -1;
        clockQueue[i] = false;
    }
    pageCount = c;
    pageSize = s;
    clockIndex = 0;

    return;
}
//Main memory constructor

mainMemory::~mainMemory()
{
	delete [] memoryQueue;
    delete [] clockQueue;

    return;
}
//mainMemory destructor


pageTable::pageTable
    ( const unsigned int programCount, const unsigned int pageSize,
      process* &program)
{
    unsigned int firstLocation = 0;
    for(int i = 0; i < programCount; i++)
    {
        program[i].pageTableSize =
            (program[i].programSize / pageSize) + 1;
        //Use integer division and the fact that array indexes start at 0
        //  to determine the number of pages needed for each program given
        //  the specified page size.
        program[i].firstPage = firstLocation;

        firstLocation += program[i].pageTableSize;
    }

    unsigned int totalPages = 0;
    for(int i = 0; i < programCount; i++)
      totalPages += program[i].pageTableSize;
      
    table = new pageTableEntry[ totalPages ];
    tableSize = totalPages;
    //Initialize the table of pages for each process

    unsigned int k = 0;
    for(int i = 0; i < tableSize; i++)
    {
        table[i].valid = false;
        table[i].frameNumber = k;
        k++;
    }

    return;
}
//pageTable constructor

pageTable::~pageTable()
{
    delete [] table;

	return;
}
//pageTable's destructor


void showDisk
    ( const unsigned int programCount, process* &program,pageTable &diskTable )
{
    int k = 0;
    for(int i = 0; i < programCount; i++)
    {
        cout << "\nProgram " << i << endl;
        for(int j = 0; j < program[i].pageTableSize; j++)
        {
            cout << "[ " << (int) diskTable.table[k].valid << " | "
                 << diskTable.table[k].frameNumber << " ] " << endl;
            k++;
        }
    }

    return;
}
// A sweet visualization routine for debugging. Not called now, but it shows
//  whether the pages in memory correspond to the pages on disk

void mainMemory::showQueues( const char replacementPolicy )
{

    cout << "Main Memory:" << endl << "[";
    for(int i = 0; i < pageCount; i++)
        cout << setw(4) << memoryQueue[i];
    cout << "]" << endl;

    if( replacementPolicy == 'c')
    {
        cout << "Clock Queue:" << endl << "[";
        for(int i = 0; i < pageCount; i++)
            cout << setw(4) << clockQueue[i];
        cout << "]" << endl;
    }

    return;
}
// Another sweet visualization routine for debugging. Call by turning on
//  verbosity.

void loadPage
    ( const unsigned int pageNumber, pageTable &diskTable, mainMemory &memory )
{
    diskTable.table[pageNumber].valid = true;
    //Find the page where the memory location resides; tell it it's in memory

    unsigned int temp[memory.pageCount];
    for(int i = 1; i < memory.pageCount; i++)
        temp[i] = memory.memoryQueue[i-1];

    for(int i = 0; i < memory.pageCount; i++)
        memory.memoryQueue[i] = temp[i];

    memory.memoryQueue[0] = diskTable.table[pageNumber].frameNumber;
    //Standard queue operation: shove out the last location, move the rest up,
    //  then set the new value to be at the front of the queue.

    return;
}
//loadPage works for both FIFO and LRU.

void doTrace
    ( ifstream &inFile,  process* &program, const char replacementPolicy,
      const char pagingType, unsigned int &faultCount, pageTable &diskTable,
      mainMemory &memory, const bool verbose )
{
    unsigned int programNumber, memoryLocation;
    int j = -1; //For pre-paging, see below.
    int i; //Ditto

    while( !inFile.eof() )
    {
        inFile >> programNumber;
        inFile >> memoryLocation;
        //Read the commands

        unsigned int pageNumber = program[programNumber].firstPage +
            (memoryLocation / memory.pageSize);
        //Translate memory locations to page locations

        if ( checkFault( pageNumber, diskTable ) ) //Fault
        {
            faultCount++; //Log the fault

            if( replacementPolicy == 'c' ) //Clock has its own replacement
            {
              
              i = clockReplace( pageNumber, diskTable, memory );
              if ( j != -1)
                  memory.clockQueue[j] = true;
                  //For pre-paging, don't un-set the last page loaded.

              if( pagingType == 'p' )//If pre-paging is turned on...
              {
                  if( pageNumber+1 < program[programNumber].firstPage+
                                     program[programNumber].pageTableSize )
                  //...and the requested program has another page after it...
                  {
                      j=clockReplace(pageNumber+1, diskTable, memory);
                      //...load that page too.
                      memory.clockQueue[i] = true;
                      //Also set the use bit on the page just before.
                  }    
              }
            }

            else //FIFO and LRU share a replacement
            {
              queueReplace( pageNumber, diskTable, memory );
              //Find a page to replace and load in a new one.

              if( pagingType == 'p' )//If pre-paging is turned on...
              {
                  if( pageNumber+1 < program[programNumber].firstPage+
                                     program[programNumber].pageTableSize )
                  //...and the requested program has another page after it...
                    queueReplace( pageNumber+1, diskTable, memory );
                    //...load that page too.
              }
            }
            
            if ( verbose )
              cout << "\nMiss on page " << pageNumber << endl;
        }
        else //Hit
        {
            if( replacementPolicy == 'c' )
                clockHit( pageNumber, diskTable, memory );
            else if( replacementPolicy == 'l' )
                lruHit( pageNumber, diskTable, memory );
            //Nothing special happens on hits for FIFO
            
            if ( verbose )
              cout << "\nHit on page " << pageNumber << endl;
        }

        if( verbose )
        {
		    memory.showQueues(replacementPolicy);
		    cout << "Press enter to continue." << endl;
            cin.get();
            //Output an absurd amount of debugging information
	    }

        if ( inFile.eof() ) //Stop at the end of the file
          break;
    }

  return;
}

bool checkFault
    ( const unsigned int pageNumber, pageTable &diskTable )
{

    if ( diskTable.table[pageNumber].valid ) //Page hit
        return false;
    else //Page fault
        return true;
}

void clockHit
    ( const unsigned int pageNumber, pageTable &diskTable, mainMemory &memory )
{
    int i;
    for(i = 0; i < memory.pageCount; i++)
    {
        if(memory.memoryQueue[i] == diskTable.table[pageNumber].frameNumber)
        {
            memory.clockQueue[i] = true;
            //Look for the page in memory that was just hit, and mark it as
            //  recently used.
            break;
        }
    }
    
    if ( (i+1) != memory.pageCount )
    {
        if ( i == memory.clockIndex )
            memory.clockIndex = i+1;
    }
    else
        memory.clockIndex = 0;

    return;
}

void lruHit
    ( const unsigned int pageNumber, pageTable &diskTable, mainMemory &memory )
{
    int replacementIndex = 0;
    for(int i = 0; i < memory.pageCount; i++)
    {
        replacementIndex = i;
        if( memory.memoryQueue[i] == diskTable.table[pageNumber].frameNumber )
            break;
        //Look for the page in memory that was just hit, and mark it as
        //  recently used.
    }

    unsigned int temp[memory.pageCount];
    for(int i = 1; i <= replacementIndex; i++)
        temp[i] = memory.memoryQueue[i-1];

    for(int i = 0; i <= replacementIndex; i++)
        memory.memoryQueue[i] = temp[i];

    memory.memoryQueue[0] = diskTable.table[pageNumber].frameNumber;
    //Similar queue operation to loadPage, but this time put the hit page at
    //  the front of the queue.

    return;
}

int clockReplace
    ( const unsigned int pageNumber, pageTable &diskTable, mainMemory &memory )
{
    unsigned int i, replacedIndex;
    for(i = memory.clockIndex; i < memory.pageCount; i++)
    {
        if( memory.clockQueue[i] == true ) //Look for a spot to replace...
        {
            memory.clockQueue[i] = false;
            //If the current spot is not ready, mark it for next time
        }
        else
        {
            if( memory.memoryQueue[i] != -1 )
            {
                diskTable.table[ memory.memoryQueue[i] ].valid = false;
                //Unload the old page
            }
            memory.memoryQueue[i] = diskTable.table[pageNumber].frameNumber;
            memory.clockQueue[i] = true;
            replacedIndex = i;
            //Load its frame number into memory
            diskTable.table[pageNumber].valid = true;
            //Tell the page it's in memory
            break;
        }
        if(i == memory.pageCount-1 )
            i = 0; //Wrap around
    }
    memory.clockIndex = i;
    
    return replacedIndex;
}

void queueReplace
    ( const unsigned int pageNumber, pageTable &diskTable,
      mainMemory &memory )
{
    unsigned int location = memory.memoryQueue[ memory.pageCount - 1 ];
    if(location != -1 )
        diskTable.table[location].valid = false;
    //For LRU and FIFO, mark the last item in the queue as no longer in memory,
    //  but not if it was never allocated.

    loadPage( pageNumber, diskTable, memory );
    //Then load in the requested page

    return;
}