// Daniel Biller
// Computer Architecture - Spring 2020
// Project 2 - Virtual Memory Simulator

import java.util.*;
import java.lang.*;

class Translation
{
	public boolean valid;
	public boolean dirty;
	public boolean ref;
	public int tag;
	public int frame;
}

class Page
{
	public boolean valid;
	public boolean dirty;
	public boolean ref;
	public int frame;
}

class Results
{
	int tlbHit;
	int tlbMiss;
	double tlbHitRate;
	int tlbWrite;
	int tlbShootdown;

	int ptHit;
	int ptMiss;
	double ptHitRate;
	int ptWrite;
	int pageEviction;
	int ptAccess;
	
	int hdRead;
	int hdWrite;
}

// Translation Lookup Table
class TLB
{
	Translation [] entry;

	public TLB (int tlb_size)
	{
		entry = new Translation[tlb_size];
		for (int i = 0; i < tlb_size; i++)
			entry[i] = new Translation();
	}

	// Returns the TLB entry that corresponds to a virtual page
	// Returns -1 if the page's translation is not in the TLB
	public int TLB_lookup(int pageNum, Results results, int rw)
	{
		for (int i = 0; i < entry.length; i++)
			if (entry[i].valid && entry[i].tag == pageNum)
			{
				results.tlbHit++;
				if (rw == 1)
					entry[i].dirty = true;
				return i;
			}

		results.tlbMiss++;
		return -1;
	}

	// Returns the index of the first available TLB entry
	// Returns -1 if all TLB entries are used
	public int get_available_TLB_entry ()
	{
		for (int i = 0; i < entry.length; i++)
			if (!entry[i].valid)
				return i;

		return -1;
	}

	// Selects the TLB entry that will be evicted
	// Pre-condition: All TLB entries are full
	// Criteria: Select a random entry with ref.bit=0; if all ref.bit=1, 
	//			 select a random entry
	public int select_TLB_shootdown_candidate()
	{
		ArrayList<Integer> candidates = new ArrayList<Integer>();

		for (int i = 0; i < entry.length; i++)
			if (entry[i].ref == false)
				candidates.add(i);

		if (candidates.size() == 0)
			return (int)(Math.random() * entry.length);

		return (int)(Math.random() * candidates.size());
	}

	// Perform a TLB shootdown (set V=0, copy D,R bits to the page table)
	// Pre-condition: shootdown entry is currently valid
	// Parameter index is the TLB entry to shoot down
	public void TLB_shootdown (int index, PageTable pageTable, Results results)
	{
		results.tlbShootdown++;
		entry[index].valid = false;

		// Write back to page table
		pageTable.pages[entry[index].tag].dirty = entry[index].dirty;
		pageTable.pages[entry[index].tag].ref = entry[index].ref;
	}

	// Copies a translation from the Page Table to the TLB
	// The first available TLB entry is used; otherwise, a TLB shootdown is performed
	// It copies the D,R bits and the frame number from the page table
	// Parameter: virtual page number
	// Returns: (+1: shootdown performed)
	public int cache_translation_in_TLB (int pageNum, PageTable pageTable, Results results, int rw)
	{
		int index, penalty = 0;

		// Get entry, perform shootdown if needed
		if (-1 == (index = get_available_TLB_entry()))
		{
			index = select_TLB_shootdown_candidate();
			TLB_shootdown(index, pageTable, results);
			penalty++;
		}

		// Copy values
		entry[index].valid = true;
		entry[index].dirty = pageTable.pages[pageNum].dirty;
		entry[index].ref = true;
		entry[index].tag = pageNum;
		entry[index].frame = pageTable.pages[pageNum].frame;

		if (rw == 1)
			entry[index].dirty = true;

		results.tlbWrite++;
	
		return penalty;
	}

}

// Page Table
class PageTable
{
	Page [] pages;

	public PageTable (int numPages)
	{
		pages = new Page[numPages];
		for (int i = 0; i < numPages; i++)
			pages[i] = new Page();
	}
	
	// Returns the index of the first available frame
	// Returns -1 if all frames are allocated
	public int get_available_frame (boolean [] frameTable)
	{
		for (int i = 0; i < frameTable.length; i++)
			// Check for unallocated frame
			if (!frameTable[i])
				return i;

		return -1;
	}

	// Search the PageTable for VDR values passed as parameters
	// Return -1 if not found; otherwise, return the index of one such
	// randomized entry (using rand function)
	// Pre-condition: VDR are 0 or 1
	public int search_PageTable_by_VDR(boolean valid, boolean dirty, boolean ref)
	{
		ArrayList<Integer> matches = new ArrayList<Integer>();

		for (int i = 0; i < pages.length; i++)
		{
			if (pages[i].valid == valid && 
				pages[i].dirty == dirty &&
				pages[i].ref == ref)
			{
				matches.add(i);
			}
		}

		// Check if any matching pages were found
		if (matches.size() == 0)
			return -1;

		// Get random index of matches list
		int temp = (int)(Math.random() * (matches.size()));

		// Return random entry
		return matches.get(temp);
	}

	// Selects the virtual page that will be replaced
	// Pre-condition: All the frames are allocated
	// Criteria: Valid must be 1; choose in order as below
	//     VDR.bits: 100   110   101   111
	// Between pages with the same category, randomize (using rand)
	public int select_page_eviction_candidate()
	{
		int temp; // Stores result so we only run function once
		
		if (-1 != (temp = search_PageTable_by_VDR(true, false, false)))
			return temp;
		if (-1 != (temp = search_PageTable_by_VDR(true, true, false)))
			return temp;
		if (-1 != (temp = search_PageTable_by_VDR(true, false, true)))
			return temp;
		return search_PageTable_by_VDR(true, true, true);

	}

	// Evict a page from RAM to the hard disk
	// If its translation is in the TLB, perform a TLB shootdown
	// If the page is dirty, write it to hard disk
	// Update the Frame Table and the page table
	// Pre-condition: the page is currently allocated in the RAM
	// Returns (+1: TLB shootdown performed) (+10: hard disk write performed)
	public int page_evict (int pageNum, TLB tlb, boolean [] frameTable, Results results)
	{
		int penalty = 0;

		results.pageEviction++;
		
		// Look for entry in TLB
		for (int i = 0; i < tlb.entry.length; i++)
		{
			if (tlb.entry[i].tag == pageNum)
			{
				// Perform Shootdown
				tlb.TLB_shootdown(i, this, results);
				penalty++;
			}
		}

		// Write back to storage
		if (pages[pageNum].dirty)
		{
			results.hdWrite++;
			penalty += 10;
		}

		// Update page table
		pages[pageNum].valid = false;

		// Update frame table
		frameTable[pages[pageNum].frame] = false;

		return penalty;
	}

	// Copies a page from the hard disk to the RAM 
	// Pre-conditions: Page currently not in RAM; page's translation is not in the TLB
	// Find a frame for the page; if all the frames are used, performa a page eviction
	// Find a TLB entry for the page; if the TLB is full, perform a TLB shootdown
	// Returns (+1: TLB shootdown performed) (+10: hard disk write performed) (+100: page eviction performed)
	// Parameter read_write: indicates read access or write access
	public int cache_page_in_RAM (int pageNum, TLB tlb, boolean [] frameTable, int rw, Results results)
	{
		int frame, penalty = 0;

		results.ptWrite++;

		frame = get_available_frame(frameTable);

		// Get empty frame
		if (frame == -1)
		{
			// Evict a page
			penalty += page_evict(select_page_eviction_candidate(), tlb, frameTable, results);
			penalty += 100;
		}

		frame = get_available_frame(frameTable);

		// Set values
		frameTable[frame] = true;
		pages[pageNum].valid = true;
		pages[pageNum].dirty = false;
		pages[pageNum].ref = true;
		pages[pageNum].frame = frame;

		if (rw == 1)
			pages[pageNum].dirty = true;

		// Send to tlb
		penalty += tlb.cache_translation_in_TLB(pageNum, this, results, rw);

		return penalty;
	}
}

public class VirtualMemory
{
	TLB tlb;	// Instance of TLB object
	PageTable pageTable;	// Instance of PageTable class
	boolean [] frameTable;	// Array showing what frames are allocated
	Results results;
	int tlb_size; // Number of translations in TLB
	int vpages;	// Number of virtual pages
	int frames;	// Number of frames in RAM
	int time;

	public VirtualMemory ()
	{
		this(1024, 8, 256);
	}

	public VirtualMemory (int vpages, int tlb_size, int frames)
	{
		this.tlb_size = tlb_size;
		this.vpages = vpages;
		this.frames = frames;

		tlb = new TLB(tlb_size);
		pageTable = new PageTable(vpages);
		frameTable = new boolean[frames];
		results = new Results();

	}

	// Clears the reference bits of the TLB and the Page Table
	public void reset_reference_bits ()
	{
		// Reset tlb reference bits
		for (int i = 0; i < tlb.entry.length; i++)
			tlb.entry[i].ref = false;

		// Reset Page table reference bits
		for (int i = 0; i < pageTable.pages.length; i++)
			pageTable.pages[i].ref = false;
	}

	// Simulates a memory access; updates all the data and statistics
	public void memory_access (int address, int read_write)
	{
		int page = address / 1024;
		int entry, penalty = 0;

		time++;

		printMemoryAccess(read_write, address, page);

		// First search in TLB
		entry = tlb.TLB_lookup(page, results, read_write);

		if (entry == -1)
		{
			// Not in TLB
			// Search Page table
			results.ptAccess++;

			if (pageTable.pages[page].valid)
			{
				// Count pt hit
				results.ptHit++;

				// Update dirty bit
				if (read_write == 1)
				{
					pageTable.pages[page].dirty = true;
				}

				// Update ref
				pageTable.pages[page].ref = true;
				
				// Cache translation to TLB
				results.tlbShootdown += tlb.cache_translation_in_TLB(page, pageTable, results, read_write);
			}
			else
			{
				// count pt miss
				results.ptMiss++;

				// count hard disk read
				results.hdRead++;

				// Cache page to ram
				penalty = pageTable.cache_page_in_RAM(page, tlb, frameTable, read_write, results);
			}
		}
	}

	public void printMemoryAccess(int r_w, int address, int page)
	{
		System.out.println("T: " + time + "	Address: " + 
							((r_w == 0) ? "r" : "w") + "	" + 
							address + "	VPN: " + page);
	}

	public static void main(String [] args)
	{
		VirtualMemory vMem = new VirtualMemory();

		// Print header
		System.out.println("-----------------------------------------\n" + 
						   "	VIRTUAL MEMORY SIMULATION\n" + 
						   "-----------------------------------------");

		// =====================================================================
		// Make memory access calls
		// =====================================================================


		for (int i = 0; i < 1000; i++)
		{
			vMem.memory_access((int)(Math.random() * 1024 * 9), 
							   (int)(Math.random() * 2));
		}
		

		// =====================================================================
		// =====================================================================

		// Print Results header
		System.out.println("\n------------------------------------------" + 
						   "-----------------------------------\n" + 
						   "			SIMULATION RESULTS\n" + 
						   "------------------------------------------" + 
						   "-----------------------------------");
		// Calculate results
		vMem.results.tlbHitRate = (double)(vMem.results.tlbHit * 100) / 
								  (vMem.results.tlbHit + vMem.results.tlbMiss);

		vMem.results.ptHitRate = (double)(vMem.results.ptHit * 100) / 
								 (vMem.results.ptHit + vMem.results.ptMiss);

		// Print results
		System.out.print("TLB hits: " + vMem.results.tlbHit);
		System.out.print("\t\tTLB misses: " + vMem.results.tlbMiss);
		System.out.println("\t\tTLB hit rate: " + vMem.results.tlbHitRate + "%");
		System.out.print("TLB Shootdowns: " + vMem.results.tlbShootdown);
		System.out.println("\tTLB Writes: " + vMem.results.tlbWrite);
		
		System.out.println("\nPg Table accesses: " + vMem.results.ptAccess);
		System.out.print("Pg Table hits: " + vMem.results.ptHit);
		System.out.print("\tPg faults: " + vMem.results.ptMiss);
		System.out.println("\t\tPg Table hit rate: " + vMem.results.ptHitRate + "%");
		System.out.print("Pg evictions: " + vMem.results.pageEviction);
		System.out.print((vMem.results.pageEviction < 10) ? "\t" : ""); // Fixes alignement
		System.out.println("\tPg Table writes: " + vMem.results.ptWrite);
		
		System.out.print("\nHard disk reads: " + vMem.results.hdRead);
		System.out.println("\tHard disk writes: " + vMem.results.hdWrite);
	}
}