//+----------------------------------------------------------------------+
//|								    DAPsim								 |
//| Dean Morrison												11/30/06 |
//| University of Florida												 |
//| Department of Electrical and Computer Engineering					 |
//+----------------------------------------------------------------------+
//| Description: DAPsim is a trace-driven simulator developed in C++ for |
//| the purpose of designing, testing, and evaluating demand prepaging 	 |
//| policies.  It currently implements my proposed concept of Dynamically|
//| Adaptive Prepaging, but may be modified to evaluate many other 		 |
//| policies.															 |
//|																		 |
//| Reuse Policy: Use of this software for personal or instructional	 |
//| purposes is granted without fee provided that the source bears a	 |
//| clear and complete citation.										 |
//+----------------------------------------------------------------------+

#include "main.h"
#include "VirtualMMU.h"

string predictionSchemes[] = {"Uninitialized","Address Local","Recency Local","Stride","Hybrid"};

// Global Variables
int debugMode = DEBUG_MODE;
int refNumber = 1;	// Cummulative Reference Number
int faultNumber = 1;// Cummulative Page Fault Number
int decayPeriod = DEFAULT_DECAY_PERIOD;					// Period at which histograms are decayed
int allocUpdatePeriod = DEFAULT_ALLOC_UPDATE_PERIOD;	// Period at which the prepaged target allocation is updated
double decayValue = (double)DEFAULT_DECAY_NUMERATOR/(double)DEFAULT_DECAY_DENOMINATOR;

VirtualMMU::VirtualMMU()
{
	MMSize = DEFAULT_MEM_SIZE;
	prepagedAlloc = DEFAULT_PREPAGED_TARGET_ALLOC;
	degree = DEFAULT_DEGREE;
	predictionScheme = DEFAULT_PREDICTION_SCHEME;

	usedPageQ.setMaxSize(MMSize - prepagedPageQ.getConsumedAlloc());
	usedPageQ.setMinSize(DEFAULT_MIN_USED_Q_SIZE);
	prepagedPageQ.setTargetAlloc(prepagedAlloc);

	initializePredictionHistograms();

	refNumber = 1;	// Cummulative Reference Number
	faultNumber = 1;// Cummulative Page Fault Number
}

VirtualMMU::VirtualMMU(int newMMSize, int newPrepagedAlloc, int newDegree, int newPredictionScheme)
{
	MMSize = newMMSize;
	prepagedAlloc = newPrepagedAlloc;
	degree = newDegree;
	predictionScheme = newPredictionScheme;

	usedPageQ.setMaxSize(MMSize - prepagedPageQ.getConsumedAlloc());
	usedPageQ.setMinSize(DEFAULT_MIN_USED_Q_SIZE);
	prepagedPageQ.setTargetAlloc(prepagedAlloc);

	initializePredictionHistograms();

	refNumber = 1;	// Cummulative Reference Number
	faultNumber = 1;// Cummulative Page Fault Number
}

void VirtualMMU::printVMMU()
{
	cout << "VMMU" << endl;
	cout << "--------" << endl;
	cout << "Main Memory Size: " << MMSize << endl;
	cout << "Prepaged Allocation: " << prepagedAlloc << endl;
	cout << "Degree: " << degree << endl;
	cout << "Prediciton Scheme: " << predictionScheme << endl;
	cout << "History Size: " << historySize << endl;
	usedPageQ.printQueueEntries();
	cout << endl << endl;
	prepagedPageQ.printQueueEntries();
}

void VirtualMMU::setMMSize(int newMMSize)
{
	MMSize = newMMSize;

	usedPageQ.setMaxSize(MMSize - prepagedPageQ.getConsumedAlloc());
}

void VirtualMMU::setPrepagedAlloc(int newPrepagedAlloc)
{
	if (newPrepagedAlloc > DEFAULT_MAX_PREPAGED_TARGET_ALLOC) {
		prepagedAlloc = DEFAULT_MAX_PREPAGED_TARGET_ALLOC;
	}
	else if (newPrepagedAlloc < DEFAULT_MIN_PREPAGED_TARGET_ALLOC) {
		prepagedAlloc = DEFAULT_MIN_PREPAGED_TARGET_ALLOC;
	}
	else {
		prepagedAlloc = newPrepagedAlloc;
	}

	usedPageQ.setMaxSize(MMSize - prepagedPageQ.getConsumedAlloc());
	prepagedPageQ.setTargetAlloc(prepagedAlloc);
}

void VirtualMMU::setDegree(int newDegree)
{
	degree = newDegree;
}

void VirtualMMU::setHistorySize(int newHistorySize)
{
	historySize = newHistorySize;
}

int VirtualMMU::getMMSize(void)
{
	return MMSize;
}

int VirtualMMU::getPrepagedAlloc(void)
{
	return prepagedAlloc;
}

int VirtualMMU::getDegree(void)
{
	return degree;
}

int VirtualMMU::incDegree(void)
{
	int newDegree = degree + 1;
	if (newDegree > DEFAULT_MAX_DEGREE) newDegree = DEFAULT_MAX_DEGREE;
	return newDegree;
}

int VirtualMMU::decDegree(void)
{
	int newDegree = degree - 1;
	if (newDegree < DEFAULT_MIN_DEGREE) newDegree = DEFAULT_MIN_DEGREE;
	return newDegree;
}

int VirtualMMU::getHistorySize(void)
{
	return historySize;
}

UsedPageQ * VirtualMMU::getUsedPageQ(void)
{
	return &usedPageQ;
}

PrepagedPageQ * VirtualMMU::getPrepagedPageQ(void)
{
	return &prepagedPageQ;
}

int VirtualMMU::handlePageRef(unsigned long int referencedPage, int preParamMode)
{
	if (debugMode == DEBUG_2) {
		cout << "----------------------------\n";
		cout << "Referencing Page #" << referencedPage << endl;
		cout << "----------------------------\n";
	}

	int refResult = PAGE_FAULT;
	LRU_pageQ_entry prepagedPage;
	vector<unsigned long int> prepageList;

	int prepageParameterMode = preParamMode;

	// Check if page fault //
	// Check Used Page Queue
	if (usedPageQ.referencePage(referencedPage)) {
		// Page hit in Used Page Queue, no further action required
		if (debugMode == DEBUG_2) cout << "Page hit in Used Page Queue\n";
		refResult = PAGE_HIT;
	}
	else { // Check Prepaged Page Queue
		prepagedPageQ.updateDegreeHistogram(referencedPage, degree);
		updatePredictionHistograms(referencedPage);
		prepagedPage = prepagedPageQ.referencePage(referencedPage);
		usedPageQ.setMaxSize(MMSize - prepagedPageQ.getConsumedAlloc());	//Update Used Page Q MaxSize
		// Check if page fault
		if (prepagedPage.getPageNumber() == NULL) {	// Page Fault in Prepaged Queue
			// PAGE FAULT //
			refResult = PAGE_FAULT;

			if (prepageParameterMode == DYNAMIC_PREPAGE_PARAMETERS || prepageParameterMode == DYNAMIC_PREPAGE_ALLOCATION) {	
				// Update Target Allocation
				if ((faultNumber % allocUpdatePeriod) == 0) {
					if (refNumber > DEFAULT_ALLOC_STARTUP_PERIOD) updatePrepagedAlloc();
				}
			}

			if (prepageParameterMode == DYNAMIC_PREPAGE_PARAMETERS || prepageParameterMode == DYNAMIC_PREDICTION_METHOD) {	
				// Update Prediction Scheme
				updatePredictionScheme();
			}
			
			if (prepageParameterMode == DYNAMIC_PREPAGE_PARAMETERS || prepageParameterMode == DYNAMIC_DEGREE) {	
				// Update Degree
				if (debugMode == DEBUG_5) prepagedPageQ.printDegreeQueue(degree);
				updateDegree();
			}

			// Generate Prepage List
			prepageList = generatePrepageList(referencedPage);

			// Add referenced page to Used Page Queue
			usedPageQ.addPage(referencedPage);
			++transfers;

			// Fetch Prepaged Pages
			fetchPrepages(prepageList);

			++faultNumber;
		}
		else {										// Push referenced page into Used Queue
			if (debugMode == DEBUG_2) {
				cout << "Page hit in Prepaged Page Queue\n";
				cout << "Transferring page from Prepaged Page Queue to Used Page Queue\n";
			}

			refResult = PAGE_HIT;
			usedPageQ.addPage(prepagedPage.getPageNumber());
		}
	}

	if (debugMode == DEBUG_2) {
		usedPageQ.printQueueEntries();
		cout << "\n\n";
		prepagedPageQ.printQueueEntries();
		cout << "\n\n";
	}

	// Periodically Decay Histogram
	if ((refNumber % decayPeriod) == 0) {
		// Perform Decay
		prepagedPageQ.decayHistogram(decayValue);
		usedPageQ.decayHistogram(decayValue);
	}
	refNumber++;


	return refResult;
}

vector<unsigned long int> VirtualMMU::generatePrepageList(unsigned long int referencedPage)
{
	if (debugMode == DEBUG_2) {
		cout << "Generating Prepage List using " << predictionSchemes[predictionScheme] << " prediciton ... \n";
		cout << "Referenced page = " << referencedPage << endl;
	}
	vector<unsigned long int> prepageList;
	vector<unsigned long int> degreeList;
	int predictionNumber;
	unsigned long int currentPrediction;

	// Address Local Prediction //
	vector<unsigned long int> addressLocalPredictionList;
	vector<unsigned long int> addressLocalDegreeList;
	for (predictionNumber = 1; predictionNumber <= (degree+2); predictionNumber++) {
		// Make predicitons
		if (predictionNumber == 1) currentPrediction = referencedPage + 1;
		else {
			if ((predictionNumber % 2) == 0) {	//If Even Prediction Number
				currentPrediction = currentPrediction - predictionNumber;
			}
			else {								//If Odd Prediction Number
				currentPrediction = currentPrediction + predictionNumber;
			}
		}
		//cout << "Adding prediction: " << currentPrediction << endl;
		if (predictionNumber <= degree) addressLocalPredictionList.push_back(currentPrediction);
		addressLocalDegreeList.push_back(currentPrediction);
	}
	addressLocalPredictions = addressLocalPredictionList;

	// Recency Local Prediction //
	vector<unsigned long int> recencyLocalPredictionList;
	vector<unsigned long int> recencyLocalDegreeList;
	for (predictionNumber = 1; predictionNumber <= (degree+2); predictionNumber++) {
		if (predictionNumber <= degree) recencyLocalPredictionList.push_back(0);
		recencyLocalDegreeList.push_back(0);
	}
	recencyLocalPredictions = recencyLocalPredictionList;

	// Stride Prediction //
	vector<unsigned long int> stridePredictionList;
	vector<unsigned long int> strideDegreeList;
	long int stride;
	//calcualate stride
	stride = referencedPage - usedPageQ.getMRUPageNumber();
	//make predictions
	currentPrediction = referencedPage;
	for (predictionNumber = 1; predictionNumber <= (degree+2); predictionNumber++) {
		// Make predicitons
		currentPrediction += stride;
		if (predictionNumber <= degree) stridePredictionList.push_back(currentPrediction);
		strideDegreeList.push_back(currentPrediction);
	}
	stridePredictions = stridePredictionList;

	// Hybrid Prediction //
	vector<unsigned long int> hybridPredictionList;
	vector<unsigned long int> hybridDegreeList;
	for (predictionNumber = 1; predictionNumber <= (degree+2); predictionNumber++) {
		if (predictionNumber <= degree) hybridPredictionList.push_back(0);
		hybridDegreeList.push_back(0);
	}
	hybridPredictions = hybridPredictionList;
	
	// Set Page Prediction //
	switch(predictionScheme) {
		case PREDICTION_UNINITIALIZED:
			break;
		case PREDICTION_ADDRESS_LOCAL:
			prepageList = addressLocalPredictionList;
			degreeList = addressLocalDegreeList;
			break;
		case PREDICTION_RECENCY_LOCAL:
			prepageList = recencyLocalPredictionList;
			degreeList = recencyLocalDegreeList;
			break;
		case PREDICTION_STRIDE:
			prepageList = stridePredictionList;
			degreeList = strideDegreeList;
			break;
		case PREDICTION_HYBRID:
			prepageList = hybridPredictionList;
			degreeList = hybridDegreeList;
			break;
		default:
			;
	}

	// Add degreeList to Degree Queue
	vector<unsigned long int>::iterator predictionNum;
	predictionNum = degreeList.end();
	--predictionNum;
	int predNumber;
    for (predNumber = (degree+2); predNumber > 0; --predNumber) {
		//cout << "Adding " << *predictionNum << " to degree list\n";
		prepagedPageQ.addDegreePage(*predictionNum); 

		if (predictionNum == degreeList.begin()) {
			break;
		}
		else {
			--predictionNum;
		}
	}

	// Check if predicted pages are already in main memory
    for (predictionNum = prepageList.begin(); predictionNum != prepageList.end(); ++predictionNum) {
        if (usedPageQ.pagePresentInResidentQ(*predictionNum) || prepagedPageQ.pagePresentInQ(*predictionNum)) {
			// Page is present in Main Mem, remove from prepageList
			if (debugMode == DEBUG_2) cout << "Erasing prediction: " << *predictionNum << endl;
			prepageList.erase(predictionNum);
			--predictionNum;
		}
	}

	printPrepageList(&prepageList);
	return prepageList;
}

void VirtualMMU::printPrepageList(vector<unsigned long int> *prepageList)
{
	if (debugMode == DEBUG_2) {
		cout << "Prepage List:\n";
		cout << "Prediciton List size = " << (*prepageList).size() << endl;
	}
	vector<unsigned long int>::iterator predictionNum;
	int predictionNumber = 1;
    for (predictionNum = (*prepageList).begin(); predictionNum != (*prepageList).end(); ++predictionNum) {
        if (debugMode == DEBUG_2) cout << predictionNumber << ": " << *predictionNum << endl;
		predictionNumber++;
	}

	if (debugMode == DEBUG_2) cout << "Front = " << (*prepageList).front() << endl;
}

void VirtualMMU::fetchPrepages(vector<unsigned long int> prepageList)
{
	vector<unsigned long int>::iterator predictionNum;
	predictionNum = prepageList.end();
	--predictionNum;
	int predNumber;
    for (predNumber = degree; predNumber > 0; --predNumber) {
        
		// Add page to Prepaged Page Q
		prepagedPageQ.addPage(*predictionNum);
		++transfers;

		// Remove page from Non-Resident Queue if present
		prepagedPageQ.removeNonResidentPage(*predictionNum);

		if (predictionNum == prepageList.begin()) {
			break;
		}
		else {
			--predictionNum;
		}
	}
	// Update Used Page Queue Max Size
	usedPageQ.setMaxSize(MMSize - prepagedPageQ.getConsumedAlloc());
}

void VirtualMMU::updatePrepagedAlloc(void)
{
	int newPrepagedAlloc = getPrepagedAlloc();
	int tempPrepagedAlloc;
	int currentNetReduction = 0;
	int maxNetReduction = 0;
	int currentPrepagedAlloc = getPrepagedAlloc();
	if (debugMode == DEBUG_1) cout << "Old Prepaged Allocation: " << prepagedAlloc << endl;

	// Determine new prepage allocation
	unsigned int benefit = 0;
	unsigned int cost = 0;
	for (tempPrepagedAlloc = 0; tempPrepagedAlloc < (MMSize - usedPageQ.getMinSize()); ++tempPrepagedAlloc) {
		currentNetReduction = calculateBenefit(tempPrepagedAlloc) - calculateCost(tempPrepagedAlloc);
		if (currentNetReduction > maxNetReduction) {
			maxNetReduction = currentNetReduction;
			newPrepagedAlloc = tempPrepagedAlloc;
		}
	}
	
	setPrepagedAlloc(newPrepagedAlloc);
	if (debugMode == DEBUG_4) cout << "Setting prepaged allocation to: " << prepagedAlloc << endl;
	//if (debugMode == DEBUG_4) {
	//	usedPageQ.printHistogram();
	//	prepagedPageQ.printHistogram();
	//}
	if (debugMode == DEBUG_1) cout << "New Prepaged Allocation: " << prepagedAlloc << endl;
}

void VirtualMMU::updatePredictionScheme(void)
{
	int tempPredictionScheme = predictionScheme;
	if (debugMode == DEBUG_1) cout << "Old Prediction Scheme: " << predictionSchemes[predictionScheme] << endl;

	// Determine new prediction scheme
	int mostEffectivePrediciton = predictionScheme;
	int maxTotal = 0;
	int currentTotal = 0;
	currentTotal = calculateHistTotal(addressLocalHistogram);
	if (currentTotal > maxTotal) {
		maxTotal = currentTotal;
		mostEffectivePrediciton = PREDICTION_ADDRESS_LOCAL;
	}
	currentTotal = calculateHistTotal(recencyLocalHistogram);
	if (currentTotal > maxTotal) {
		maxTotal = currentTotal;
		mostEffectivePrediciton = PREDICTION_RECENCY_LOCAL;
	}
	currentTotal = calculateHistTotal(strideHistogram);
	if (currentTotal > maxTotal) {
		maxTotal = currentTotal;
		mostEffectivePrediciton = PREDICTION_STRIDE;
	}
	currentTotal = calculateHistTotal(hybridHistogram);
	if (currentTotal > maxTotal) {
		maxTotal = currentTotal;
		mostEffectivePrediciton = PREDICTION_HYBRID;
	}
	
	predictionScheme = mostEffectivePrediciton;

	if (predictionScheme != tempPredictionScheme){
		if (debugMode == DEBUG_8) {
			cout << "Old Prediction Scheme: " << predictionSchemes[tempPredictionScheme] << endl;
			cout << "New Prediction Scheme: " << predictionSchemes[predictionScheme] << endl;

			printPredictionHistograms();
			//printPredictionLists();
		}
	}

	clearPredictionHistograms();
}

void VirtualMMU::updateDegree(void)	
{
	int oldDegree = degree;
	if (debugMode == DEBUG_1) cout << "Old Degree: " << oldDegree << endl;

	// Get Histogram Entires for Current and Next Degree in Degree Queue
	int valAtCurrentDegree = prepagedPageQ.getDegreeHistogramEntry(degree-1);
	if (debugMode == DEBUG_1) cout << "Histogram value at current degree: " << valAtCurrentDegree << endl;
	int valAtDegreePlusOne = prepagedPageQ.getDegreeHistogramEntry(degree);
	if (debugMode == DEBUG_1) cout << "Histogram value at current degree + 1: " << valAtDegreePlusOne << endl;
	int valAtDegreePlusTwo = prepagedPageQ.getDegreeHistogramEntry(degree+1);
	if (debugMode == DEBUG_1) cout << "Histogram value at current degree + 2: " << valAtDegreePlusTwo << endl;

	// Determine New Degree
	if (valAtDegreePlusTwo > 0) {
		degree = incDegree();
		degree = incDegree();
	}
	else if (valAtDegreePlusOne > 0) degree = incDegree();
	else if (valAtCurrentDegree == 0) degree = decDegree();
	
	if (debugMode == DEBUG_5) {
		if (degree != oldDegree) {
			cout << "New Degree: " << degree << endl;
			prepagedPageQ.printDegreeQueue(oldDegree);
			cout << endl;
		}
	}
	if (debugMode == DEBUG_1) cout << "New Degree: " << degree << endl;

	prepagedPageQ.clearDegreeHistogram();
}

unsigned int VirtualMMU::calculateBenefit(int targetAlloc)
{
	unsigned int benefit = 0;
	
	int index;

	for (index = 0; index < targetAlloc; ++index) {
		benefit += prepagedPageQ.getHistogramEntry(index);
	}

	return benefit;
}

unsigned int VirtualMMU::calculateCost(int targetAlloc)
{
	unsigned int cost = 0;
	
	int index;

	for (index = (DEFAULT_MEM_SIZE - targetAlloc); index < DEFAULT_MEM_SIZE; ++index) {
		cost += usedPageQ.getHistogramEntry(index);
	}

	return cost;
}

void VirtualMMU::initializePredictionHistograms(void)
{
	int index;
	for (index = 0; index < DEFAULT_MAX_DEGREE; index++) {
		addressLocalHistogram[index] = 0;
		recencyLocalHistogram[index] = 0;
		strideHistogram[index] = 0;
		hybridHistogram[index] = 0;
	}
}

void VirtualMMU::clearPredictionHistograms(void)
{
	int index;
	for (index = 0; index < degree; index++) {
		addressLocalHistogram[index] = 0;
		recencyLocalHistogram[index] = 0;
		strideHistogram[index] = 0;
		hybridHistogram[index] = 0;
	}
}

int VirtualMMU::calculateHistTotal(int histogram[])
{
	int total = 0;

	int index;
	for (index = 0; index < degree; index++) {
		total += histogram[index];
	}

	return total;
}

void VirtualMMU::updatePredictionHistograms(unsigned long int referencedPage)
{
	int predictionNum = 1;
	vector<unsigned long int>::iterator prediction;
	for (prediction = addressLocalPredictions.begin(); prediction != addressLocalPredictions.end(); ++prediction) {
		if (predictionNum > degree) break;
		else if (*prediction == referencedPage) {
			addressLocalHistogram[predictionNum - 1] += 1;
		}
		else predictionNum++;
    }

	predictionNum = 1;
	for (prediction = recencyLocalPredictions.begin(); prediction != recencyLocalPredictions.end(); ++prediction) {
		if (predictionNum > degree) break;
		else if (*prediction == referencedPage) {
			recencyLocalHistogram[predictionNum - 1] += 1;
		}
		else predictionNum++;
    }

	predictionNum = 1;
	for (prediction = stridePredictions.begin(); prediction != stridePredictions.end(); ++prediction) {
		if (predictionNum > degree) break;
		else if (*prediction == referencedPage) {
			strideHistogram[predictionNum - 1] += 1;
		}
		else predictionNum++;
    }

	predictionNum = 1;
	for (prediction = hybridPredictions.begin(); prediction != hybridPredictions.end(); ++prediction) {
		if (predictionNum > degree) break;
		else if (*prediction == referencedPage) {
			hybridHistogram[predictionNum - 1] += 1;
		}
		else predictionNum++;
    }
}

void VirtualMMU::printPredictionHistograms()
{
	int index;

	cout << "Address Local Prediction Histogram:\n";
	for (index = 0; index < degree; index++) {
		cout << addressLocalHistogram[index] << endl;
	}
	cout << endl;

	cout << "Recency Local Prediction Histogram:\n";
	for (index = 0; index < degree; index++) {
		cout << recencyLocalHistogram[index] << endl;
	}
	cout << endl;

	cout << "Stride Prediction Histogram:\n";
	for (index = 0; index < degree; index++) {
		cout << strideHistogram[index] << endl;
	}
	cout << endl;

	cout << "Hybrid Prediction Histogram:\n";
	for (index = 0; index < degree; index++) {
		cout << hybridHistogram[index] << endl;
	}
	cout << endl;

}

void VirtualMMU::printPredictionLists()
{
	int index;

	cout << "Address Local Prediction Histogram:\n";
	for (index = 0; index < degree; index++) {
		cout << addressLocalPredictions[index] << endl;
	}
	cout << endl;

	cout << "Recency Local Prediction Histogram:\n";
	for (index = 0; index < degree; index++) {
		cout << recencyLocalPredictions[index] << endl;
	}
	cout << endl;

	cout << "Stride Prediction Histogram:\n";
	for (index = 0; index < degree; index++) {
		cout << stridePredictions[index] << endl;
	}
	cout << endl;

	cout << "Hybrid Prediction Histogram:\n";
	for (index = 0; index < degree; index++) {
		cout << hybridPredictions[index] << endl;
	}
	cout << endl;

}

