// virtualMemoryLRU.c -- functions for simulating virtual memory
// this version uses a global least recently used strategy
// Philip Machanick
// 15 April 2005

// Version 2.0 (actually first version but numbered in synch with older code)

// a list is maintained of recency of use. Whenever a page is referenced, it
// is moved to the front of the list if not already there. The last page on the list
// is the victim. To make additions to the front and removals from the end efficient
// a doubly-linked list is used. A simple hack to use a singly-linked list would be
// to keep a pointer to the last element in the header of the list and rely on this
// value rather than a null pointer to detect that you were at the end of the list.
// While this strategy would save memory, it would require greater care in coding.
// A practical implementation could however use the more memory-efficient approach.
// If a TLB was used, the LRU status of TLB entries could be maintained in the TLB
// and only flushed when a TLB entry was evicted.

// This implementation does not use a separate list structure but stores the next
// and previous pointers in the PhysicalStatus table entry. To find which table
// entry a specific element refers to when it's reached via pointers (when you
// reach it via an array index, you have the index) pointer arithmetic is used.
// This saves an extra pointer or index value which would otherwise have to be stored
// in the table entry.

#include "virtualMemory.h"
#include "generalTypes.h"
#include <stdio.h>

// types, functions and data for use only in this file

static const Byte unused = 0x0, used = 0x1;

typedef struct PhysicalStatus {
	int ownerPID;
	void * PTentry; // keep general for different page tables
	Byte status;	// for LRU algorithm, only need 1 bit
	struct PhysicalStatus *previous, *next;	// easily find in LRU order to move to front
} PhysicalStatus;

typedef struct LRUList {
	PhysicalStatus * first,
		* last;
} LRUList;

// move the just referenced page to the front of the LRU list
static void moveToFront (LRUList *list, PhysicalStatus * moving);
// initialise LRU list (null pointers)
static void initLRUList (LRUList *list);
// remove from LRU list
static void removeFromLRUList (LRUList *list, PhysicalStatus *removing);
// add to LRU list
static void addToLRUList (LRUList *list, PhysicalStatus * newElement);
// intitialise an entry in the physical frame table
static void initPFrame (PhysicalStatus *newFrame);
// select the least recently used page as a victim
// use the location relative to the memory table to find which element it is
static Address reclaimLRU (LRUList *list, PhysicalStatus *memoryTable);

// translate between index into free memory table and frame
// number -- here just >> or << DISPLACEMENTBITS, but should
// allow for space used up by OS
static Address freeMemoryFrame (int index);
static int freeMemoryIndex (Address pFrame);

static PhysicalStatus * memoryState;
static int numberOfFrames;
static LRUList pageOrder;

//-----------local function implementations-------------

// assume the element is actually on the list ... could do some sanity checks
// like are the pointers set? Is previous == NULL a match to element being at
// the front of the list?
void moveToFront (LRUList *list, PhysicalStatus * moving) {
	if (moving->previous) {   // not already at front
		moving->previous->next = moving->next;
		if (moving->next){  // not at end of list
			moving->next->previous = moving->previous;
		} else {
			list->last = moving->previous;
		}
		// at least 2 items in list otherwise we'd already be at the front
		moving->previous = NULL;
		list->first->previous = moving;
		moving->next = list->first;
		list->first = moving;
	}
}

// initialise LRU list (null pointers)
static void initLRUList (LRUList *list) {
	first = last = NULL;
}

// remove from LRU list
// sanity checks also an option here: is it actually on the list etc. ...
static void removeFromLRUList (LRUList *list, PhysicalStatus *removing) {
	if (removing->previous) {   // not at front
		removing->previous->next = removing->next;
	} else {
		list->first = removing->next;
		if (list->first)
			list->first->previous = NULL;
		else	// emptied the list
			list->last = NULL;
	}
	if (removing->next){  // not at end of list
		removing->next->previous = removing->previous;
	} else {
		list->last = removing->previous;
		// at least 2 items in list otherwise we'd already be at the front
		removing->previous = NULL;
		list->first->previous = removing;
		removing->next = list->first;
		list->first = removing;
	}
}


// add to LRU list
static void addToLRUList (LRUList *list, PhysicalStatus * newElement) {
	newElement->previous = NULL;
	if (list->first) {
		list->first->previous = newElement;
	} else {
		newElement->next = NULL;
		list->last = newElement;
	}
	newElement->next = list->first;
	list->first=newElement;
}

static void initPFrame (PhysicalStatus *newFrame) {
		newFrame.ownerPID = -1;
		newFrame.PTentry = NULL;
		newFrame.status = unused;
		newFrame.previous = NULL;
		newFrame.next = NULL;
}

// use the location relative to the memory table to find which element it is
static Address reclaimLRU (LRUList *list, PhysicalStatus *memoryTable) {
	PhysicalStatus *victim = list->last;
	Address returnValue = 0;
	if (list->first)
		if (victim) {
			if (list->first == victim) // only 1 physical page ...
				list->first = list->last = NULL;
			else {
				returnValue = victim - memoryTable; // magic of pointer arithmetic
				victim->previous->next = NULL;
				list->last = victim->previous;
			}
		}
		else   // ERROR -- shouldn't be here if list->first defined
			handleError ("LRUlist inconsistent: first defined but last NULL", EXIT, VMSTATECORRUPT);
			
	else   // ERROR -- shouldn't be here if no unallocated pages
        handleError ("memory full yet LRUlist empty", EXIT, VMSTATECORRUPT);
	return returnValue;  // error handler kills program if shouldn't get here
}

//-----------function implementations-------------

// set up status of physical frames, all originally unused, unallocated
void initVM (Address maxPage) {
	int i;
	// physical pages numbered 0..maxPage (displacement bits included)
	// must add 1 to allow highest page number as an array index
	numberOfFrames = freeMemoryIndex (maxPage) + 1;  // should resize to subtract OS memory
	memoryState = (struct PhysicalStatus*) malloc (sizeof(struct PhysicalStatus)*numberOfFrames);
	for (i = 0; i < numberOfFrames; i++) {
		initPFrame (&memoryState [i]);
	}
	initLRUList (&pageOrder);
}

// tell VM a page has been added: mark as used and add it to the front of the LRU list
void informVMNewPage (int pid, Address vAddress, Address pAddress, void *entryInPT) {
	Address pFrame = freeMemoryIndex (pAddress);
	if (pFrame <  numberOfFrames) {
		LRUListElement *newElement = newLRUListElement (memoryState [pFrame]);
		memoryState [pFrame].ownerPID = pid;
		memoryState [pFrame].PTentry = entryInPT;
		addToLRUList (&pageOrder, &memoryState [pFrame]);
	} else
	{
        char message [80];
        sprintf (message,
				 "attempt to use frame 0x%x bigger than largest physical frame 0x%x",
					(unsigned) pAddress, numberOfFrames);
        handleError (message, EXIT, PHYSFRAMETOOBIG);
	}
}

// tell VM a page has been used -- assume owner etc. correct, but could check
void informVMPageUsed (int pid, Address vAddress, Address pAddress, void *entryInPT) {
	Address pFrame = freeMemoryIndex (pAddress);
	if (pFrame <  numberOfFrames)
		moveToFront (&pageOrder, &memoryState[pFrame]);
	else
	{
        char message [80];
        sprintf (message,
				 "attempt to use frame 0x%x bigger than largest physical frame 0x%x",
				 (unsigned) pAddress, numberOfFrames);
        handleError (message, EXIT, PHYSFRAMETOOBIG);
	}
}

void freeFrame (Address frame) {
	Address pFrame = freeMemoryIndex (frame);
	if (memoryState[pFrame].ownerPID == -1 || memoryState [pFrame].PTentry == NULL) {
        char message [80];
        sprintf (message,
				 "attempt to use deallocate unused page frame 0x%x", (int) pFrame);
        handleError (message, EXIT, FREEUNUSEDMEM);
	}
	initPFrame (&memoryState [pFrame]);
}

// find a replacement victim for a page fault for process pid
// in the case of a global replacement policy, ignore pid
// for a local policy, we will need to have one physical memory
// table per process
// return the page number: in this simple implementation, just
// the index to the table left-shifted DISPLACEMENTBITS
// SHOULD ONLY BE CALLED IF ALL PHYSICAL FRAMES ALLOCATED
// otherwise the free memory handler will instead provide
// a free frame
Address selectVictim (int pid) {
	Address victim = reclaimLRU (pageOrder, memoryState);
	invalidate (memoryState [victim].PTentry);
	// freeFrame called when memory deallocated in case more stats needed
	addVictimToStats (pid);
	return freeMemoryFrame (victim);
}

//-----------local function implementations-------------

// pid not used in global clock algorithm


static int freeMemoryIndex (Address pFrame) {
	return pFrame >> DISPLACEMENTBITS;
}

static Address freeMemoryFrame (int index) {
	return index << DISPLACEMENTBITS;
}