//
// Dragon cache coherency simulation
//
// Copyright © 2007 - 2007 alek.stevanovic@gmail.com


//
// 23/12/07 first version
// 23/11/08 second version, Djordje Jevdjic

//
// include files
//
#include "standard.vin"
#include "simpleButton.vin"

//
// set viewport
//
const int LOGICALW = 1024;
const int LOGICALH = 768;
setViewport(0, 0, LOGICALW, LOGICALH, 1);

//
// set background
//
bgbrush = SolidBrush(vellum);
setBgBrush(bgbrush);

//
// fonts
//
hintFont = Font("Times New Roman", 16, 0);
titleFont = Font("Times New Roman", 24, 0);
f12B = Font("Times New Roman", 12, 1);
fsmall = Font("Times New Roman", 14, 0);

//
// title
//
navybrush = SolidBrush(rgb(0, 0, 102));
title = Rectangle2(0, VCENTRE, 0, navybrush, 5, 5, LOGICALW/2, 30, whitebrush, titleFont, "Dragon Cache Coherency Protocol");
title.setTxtOff(2, 1);

//
// useage infomation
//
str =  "Like real hardware, the CPUs can operate\n";
str += "in parallel - try pressing a button on each\n";
str += "CPU \"simultaneously\".";
hint = Txt(0, HLEFT | VTOP, 5, 80, blackbrush, hintFont, str);

const int DIRTYBIT	= 1;		// 
const int SHAREDBIT	= 2;		// cache line states

const int NOTHING	= 0;
const int RECV		= 1;
const int SEND		= 2;
const int SND_RCV	= 3;
const int MEMORY	= 4;

const int ST_E		= 0;		// Exclusive
const int ST_M		= 1;		// Modified
const int ST_Sc		= 2;		// Shared clean
const int ST_Sm		= 3;		// Shared modified
const int ST_No		= 4;		// Beginner empty state

string statetxt[5]	= { "E", "M", "Sc", "Sm", "No" };

int wValue			= 0;		// value written into cache
int isdirty			= 0;		// indicates if there is a dirty cache
int isshared		= 0;		// indicates if cache line shared
int issharedstate	= 0;		// shared cache line state (all should be the same)
int isshareddata	= 0;		// shared cache line data (all should be the same)
int buglevel		= 0;		// buglevel (0 = bug free)
int isbusy			= 0;		// counter used to signify when any of the processors is busy
								// (with it representing the number of busy processors)
//
// Number of CPUs
//

const int NCPU		= 4;		// Set the number of CPUs in the simulation

for (int i=0; i<NCPU; i++)
	cpulock[i] = 0;
end;

buslock = 0;					// bus lock

SimpleButton lastButton[*];

//
// vertical double headed bus arrrow
//
// separate up, down and body objects to animate bus traffic
//
class BusArrow(int x, int y, int whead, int wbody, int l, Brush brush)

	arrow = Polygon(0, AAFILL | ABSOLUTE, 0, blackbrush, x,y, 0,0, whead,whead, wbody,whead, wbody,l-whead, whead,l-whead, 0,l, -whead,l-whead, -wbody,l-whead, -wbody,whead, -whead,whead);
	int largewhead = whead;
	int largewbody = wbody;
	body = Rectangle2(0, 0, 0, brush, x-wbody, y, 2*wbody+1, l);
	body.setOpacity(0);
	up = Polygon(0, AAFILL | ABSOLUTE, 0, brush, 0,0, largewhead,0, 2*largewhead,whead, 0,whead);
	up.setOpacity(0);
	down = Polygon(0, AAFILL | ABSOLUTE, 0, brush, 0,0, 0,0, 2*largewhead,0, largewhead,whead);
	down.setOpacity(0);

	//
	// reset bus arrow
	//
	function reset()
		arrow.setBrush(blackbrush);
		up.setOpacity(0);
		body.setOpacity(0);
		down.setOpacity(0);
		arrow.setOpacity(255);
	end;

	//
	// animate up movement on vertical bus arrow
	//
	// may be called with ticks = 0
	//
	function moveup(int ticks, int wflag)
		//
		// initial positions, size & opacity
		//
		up.setPos(x-largewhead, y+(l-largewhead));
		body.setPos(x-largewbody, y+l);
		body.setSize(2*largewbody+1, 0);
		up.setOpacity(255);
		body.setOpacity(255);

		//
		// final positions, size & opacity
		//
		up.setPos(x-largewhead, y, ticks, 1, 0);
		body.setPos(x-largewbody, y+largewhead, ticks, 1, 0);
		body.setSize(2*largewbody+1, l+1-largewhead, ticks, 1, 0);
		arrow.setOpacity(0, ticks, 1, wflag);

	end;

	//
	// animate down movement on vertical bus arrow
	//
	// may be called with ticks = 0
	//
	function movedown(int ticks, int wflag)

		//
		// initial positions, size & opacity
		//
		down.setPos(x-largewhead, y);
		body.setPos(x-largewbody, y);
		body.setSize(2*largewbody+1, 0);
		down.setOpacity(255);
		body.setOpacity(255);

		//
		// final positions, size & opacity
		//
		down.setPos(x-largewhead, y+l-largewhead, ticks, 1, 0);
		body.setSize(2*largewbody+1, l-largewhead+1, ticks, 1, 0);
		arrow.setOpacity(0, ticks, 1, wflag);

	end;

end;

//
// memory object
//
// contains 4 memory locations a0, a1, a2 & a3
//
class Memory(int x, int y)

	// Draw the box

	r = Rectangle2(0, 0, blackpen, gray192brush, x, y, 150, 100);
	t = Txt(0, HLEFT | VTOP, x+160, y+40, redbrush, 0, "memory");
	abus = BusArrow(x+50, y+100, 10, 4, 70, bluebrush);
	dbus = BusArrow(x+100, y+100, 10, 4, 40, redbrush);
	
	// and all the textboxes inside

	for (int i = 0; i < 4; i++)
		mem[i] = 0;
		stale[i] = 0;
		memR[i] = Rectangle2(0, 0, blackpen, whitebrush, x+5, y+4+i*24, 140, 20, blackbrush, 0, "address: a%d data: %d", i, mem[i]);
		memR[i].setTxtOff(0, 1);
	end;
	
	// used to highlight the selected address

	function highlight(int addr, int flag)
		if (flag == 1)
			memR[addr].setBrush(greenbrush);
		else
			if (stale[addr])
				memR[addr].setBrush(gray192brush);
			else
				memR[addr].setBrush(whitebrush);
			end;
		end;
	end;
	
	// reset any highlights

	function reset()
		for (int i = 0; i < 4; i++)
			highlight(i, 0);
		end;
	end;

end;

//
// horizontal double headed bus object
//
class Bus(int x, int y, int whead, int wbody, int l, Brush brush)

	arrow = Polygon(0, AAFILL | ABSOLUTE, 0, blackbrush, x,y, 0,0, whead,-whead, whead,-wbody, l-whead,-wbody, l-whead,-whead, l,0, l-whead,whead, l-whead,wbody, whead,wbody, whead,whead);

	function highlight(int flag)
		if (flag == 0)
			arrow.setBrush(blackbrush);
		else
			arrow.setBrush(brush);
		end;
	end;
end;

//
// data, address and shared horizontal busses
//
ddbus = Bus(20, 215, 11, 5, LOGICALW-20, redbrush);
ddbusTxt = Txt(0,HLEFT | VTOP, 60, 194, redbrush, fsmall, "data bus");
aabus = Bus(30, 245, 11, 5, LOGICALW-40, bluebrush);
aabusTxt = Txt(0, HLEFT | VTOP, 70, 223, bluebrush, fsmall, "address bus");
sharedBus = Bus(40, 280, 7, 3, LOGICALW-60, magentabrush);
sharedTxt = Txt(0, HLEFT | VTOP, 200, 260, magentabrush, fsmall, "shared");
memory = Memory(LOGICALW/2-30, 70);

class Cache;		// forward declaration
Cache cache[NCPU];

//
// cache object
//
class Cache(int x, int y, int cpu)

	sharedbus = BusArrow(x+13, y-42, 7, 3, 42, magentabrush);
	abus = BusArrow(x+62, y-75, 10, 4, 75, bluebrush);
	dbus = BusArrow(x+117, y-105, 10, 4, 105, redbrush);
	cpuabus = BusArrow(x+50, y+50, 10, 4, 50, bluebrush);
	cpudbus = BusArrow(x+100, y+50, 10, 4, 50, redbrush);

	r = Rectangle2(0, 0, blackpen, gray192brush, x, y, 150, 50);
	t = Txt(0, HLEFT | VTOP, x+130, y-20, redbrush, 0, "cache %d", cpu);
	for (int i = 0; i < 2; i++)
		state[i] = ST_No;
		sharedR[i] = Rectangle2(0, 0, blackpen, whitebrush, x+5, y+6+i*20, 15+1, 17+1, blackbrush, f12B, "S");
		sharedX0[i] = Line2(0, AAFILL | ABSOLUTE, redpen, x+5,y+6+i*20, x+5+15+1,y+6+i*20+17+1);
		sharedX0[i].setOpacity(0);
		sharedX1[i] = Line2(0, AAFILL | ABSOLUTE, redpen, x+5,y+6+i*20+17, x+5+15+1,y+6+i*17+1);
		sharedX1[i].setOpacity(0);
		stateR[i] = Rectangle2(0, 0, blackpen, whitebrush, x+20, y+6+i*20, 15+1, 17+1, blackbrush, f12B, "");
		stateX0[i] = Line2(0, AAFILL | ABSOLUTE, redpen, x+20,y+6+i*20, x+20+15+1,y+6+i*20+17+1);
		stateX1[i] = Line2(0, AAFILL | ABSOLUTE, redpen, x+20,y+6+i*20+17, x+20+15+1,y+6+i*20);
		a[i] = i;
		aR[i] = Rectangle2(0, 0, blackpen, whitebrush, x+35, y+6+i*20, 55+1, 17+1, blackbrush, 0, "?");
		aR[i].setTxtOff(0, 1);
		d[i] = 0;
		dR[i] = Rectangle2(0, 0, blackpen, whitebrush, x+90, y+6+i*20, 55+1, 17+1, blackbrush, 0, "?");
		dR[i].setTxtOff(0, 1);
	end;

	//
	// state crosses
	//
	function statetext(int set)
		int opacity;
		opacity = (state[set] & SHAREDBIT) ? 0 : 255;
		sharedX0[set].setOpacity(opacity);
		sharedX1[set].setOpacity(opacity);
		opacity = (state[set] != ST_No) ? 0 : 255;
	
		stateR[set].setTxt(statetxt[state[set]]);
		stateX0[set].setOpacity(opacity);
		stateX1[set].setOpacity(opacity);
	end;
	
	// Highlight the current set

	function highlight(int set, int flag)
		if (flag == 1)
			sharedR[set].setBrush(greenbrush);
			stateR[set].setBrush(greenbrush);
			aR[set].setBrush(greenbrush);
			dR[set].setBrush(greenbrush);
		else
			sharedR[set].setBrush(whitebrush);
			stateR[set].setBrush(whitebrush);
			aR[set].setBrush(whitebrush);
			dR[set].setBrush(whitebrush);
		end;
	end;

	function resetbus()
		memory.abus.reset();
		memory.dbus.reset();
		ddbus.arrow.setBrush(blackbrush);
		aabus.arrow.setBrush(blackbrush);
		sharedBus.arrow.setBrush(blackbrush);
		memory.reset();
		for (int i = 0; i < NCPU; i++)
			cache[i].abus.reset();
			cache[i].dbus.reset();
			cache[i].sharedbus.reset();
		end;
	end;
	
	// Beginning reset procedure multithread friendly

	function resetStart()
		for (int i = 0; i < NCPU; i++)
			if ((cpulock[i] == 0) || (cpu == i))
				cache[i].cpuabus.reset();
				cache[i].cpudbus.reset();
				cache[i].highlight(0, 0);
				cache[i].highlight(1, 0);
				lastButton[i].setborderpen(blackpen);
			end;
		end;
		if (buslock == 0)
			resetbus();
		end;
	end;
	
	// Ending reset procedure multithread friendly

	function resetEnd()
		for (int i = 0; i < NCPU; i++)
			if (cpulock[i] == 0)
				cache[i].cpuabus.reset();
				cache[i].cpudbus.reset();
				cache[i].highlight(0, 0);
				cache[i].highlight(1, 0);
				lastButton[i].setborderpen(blackpen);
			end;
		end;
	end;
	
	// Main cache-protocol enforcing routine for adjacent processors

	function shared(int addr, int type, int data)
		int set = addr % 2;
		debug("shared call cpu=%d, state[set]=%d",cpu,state[set]);
		if (a[set] != addr || state[set] == ST_No)		// Are at the starting point or not addressed?
			isbusy = isbusy - 1;						// in that case I have done my work, return
			return;			
		end;
				
		debug("shared cpu=%d, addr=%d, type= %d, memory=%d, data=%d d[set]=%d", cpu, addr, type & 3, type & 4, data, d[set]);
				
		isshared = SHAREDBIT;
		
		if ((type & RECV) && (state[set] & DIRTYBIT))	// Sm or M should send
			isdirty = DIRTYBIT;
			abus.movedown(20, 1);
			dbus.moveup(20, 1);
			isshareddata = d[set];
		elseif (type & SEND)							// otherwise we are recieving input
			isdirty = DIRTYBIT;							// in case its a busupdate
			d[set] = data;			
			dbus.movedown(20, 0);
			abus.movedown(20, 1);
		else
			abus.movedown(20, 1);						// nope, its neither, do nothing
		end;
		
		state[set] |= SHAREDBIT;
		issharedstate = state[set];
		highlight(set, 1);
		
		if ((type & MEMORY) && (state[set] & DIRTYBIT))	// are we writing to memory as well?
			dbus.moveup(20, 0);
		end;
		
		if (type & SEND)								// if we have been sending, now its updated
			state[set] &= SHAREDBIT;					// clear dirty bit
		end;
				
		sharedbus.moveup(0, 1);
		sharedBus.highlight(1);
		dR[set].setTxt("%d", d[set]);
		statetext(set);
		isbusy = isbusy - 1;							// my job here is done
	end;

	function sharedwatch(int addr, int cpu, int type, int data)
		debug("sharedwatch addr=%d cpu=%d type=%d memory=%d data=%d", addr, cpu, type & 3, type & 4, data);
		isshared = 0;
		isdirty = 0;
		
		isbusy = NCPU - 1;									// there are NCPU-1 adjacent processor
		for (int i = 0; i < NCPU; i++)
			if (i != cpu)
				fork(cache[i].shared(addr, type, data));	// spawn a fork for every adjacent processor so they could do their job
			end;
		end;
		
		cache[cpu].sharedbus.movedown(20, 0);				// animate bus
		
		if (type & MEMORY)
			memory.dbus.moveup(20, 0);						// animate memory to bus link if necessery
		end;
					
		memory.abus.moveup(20, 1);	
		
		if ((isshared == SHAREDBIT) && !(type & MEMORY))	// wait additional 20 frames to synchronize with the rest in case
			wait(20);										// we are not working with memory and are sharing data
		end;
	end;

	// Used to output data from cache to memory

	function flush(int cpu, int addr, int mem)
		set = addr % 2;
		flushaddr = a[set];
		abus.moveup(20, 0);
		dbus.moveup(20, 1);
		aabus.highlight(1);
		ddbus.highlight(1);
		
		if (mem == 1)
			sharedwatch(addr, cpu, SEND | MEMORY, d[set]);	// if we are working with memory, pass the info to the sharedwatch member
		else
			sharedwatch(addr, cpu, SEND, d[set]);
		end;
		
		state[set] = state[set] & SHAREDBIT; 				// clear dirty bit ~SD
		statetext(set);
		
		if (mem == 1)										// update memory
			memory.stale[flushaddr] = 0;
			memory.memR[flushaddr].setBrush(whitebrush);
			memory.mem[flushaddr] = d[set];
			memory.memR[flushaddr].setTxt("address: a%d data: %d", flushaddr, memory.mem[flushaddr]);
		end;
		
		wait(10);											// synchronize
		resetbus();
	end;
	
	// Read operation on cache
	
	function read(int addr, int animatecpu)

		int set = addr % 2;

		if (animatecpu)										// is this a simulation or just a quick read?
			cpuabus.moveup(20, 1);
		end;
		
		if (((a[set] != addr) && (state[set] & DIRTYBIT))) 	// miss + old cache line in Sm or M
			while (buslock)
				wait(1);
			end;
			buslock = 1;									// bus locked for use
			wait(1); // {joj 7/11/06}
			resetbus();
			flush(cpu, a[set], 1);							// save current value to memory
			buslock = 0;									// free bus
			state[set] = ST_No;								// set initial state
		end;

		highlight(set, 1);
		aR[set].setTxt("a%d", addr);
		
		if (a[set] != addr || state[set]==ST_No) 			// miss
			while (buslock)
				wait(1);
			end;
			buslock = 1;
			wait(1); // {joj 7/11/06}
			resetbus();
			abus.moveup(20, 1);
			aabus.highlight(1);
			
			sharedwatch(addr, cpu, RECV, 0);				// Read in from an authoritarian member, valid value
			while (isbusy)									// Insert delay until everyone else are done
				wait(1);
			end;
			wait(1);
			
			// If shared 
			if (isdirty)
				debug("Shared data: %d",isshareddata);
				d[set] = isshareddata;						// We have read a valid value from another cache
				state[set] = ST_Sc;							// so we are now shared and clean
			else
				memory.highlight(addr, 1);
				memory.dbus.movedown(20, 1);
				d[set] = memory.mem[addr];
				if (isshared)								// If value read from memory and we are the only one, enter exclusive state
					state[set] = ST_Sc;						// otherwise we are still shared clean
				else
					state[set] = ST_E;
				end;
			end;
			ddbus.highlight(1);
			dbus.movedown(20, 1);
			a[set] = addr;
			dR[set].setTxt("%d", d[set]);					// updatevalues
			statetext(set);
		end;
		if (animatecpu)										// bus animation if needed
			cpudbus.movedown(20, 1);
		end;
		buslock = 0; // {joj 7/11/06}
	end;

	//
	// cpu write operation
	//
	function write(int addr)

		int set = addr % 2;
		cpudbus.moveup(20, 0);
		cpuabus.moveup(20, 1);
		highlight(set, 1);

		//
		// if cache miss and cache line dirty then flush line to memory
		//
		if ((a[set] != addr) && (state[set] & DIRTYBIT))
			while (buslock)
				wait(1);
			end;
			buslock = 1;
			wait(1); // {joj 7/11/06}
			resetbus();
			flush(cpu, a[set], 1); // write out dirty cache line
			buslock = 0;
			state[set] = ST_No;
		end;

		//
		// if a miss read memory first before writing
		//
		if (a[set] != addr || state[set]==ST_No)
			read(addr, 0);
			wait(20);
		end;

		//
		//
		// if shared then write through otherwise write-back
		//
		debug("write shared %d",state[set]);
		if ((state[set] & SHAREDBIT))								// if we are shared

			while (buslock)
				wait(1);
			end;
			buslock = 1;
			wait(1); // {joj 7/11/06}
			resetbus();

			a[set] = addr;
			aR[set].setTxt("a%d", addr);
			wValue++;												// set new value
			d[set] = wValue;
			dR[set].setTxt("%d", wValue);

			abus.moveup(20, 0);
			dbus.moveup(20, 1);
			aabus.highlight(1);
			ddbus.highlight(1);
			sharedwatch(addr, cpu, SEND, d[set]);					// animate other processors, we are doing busupdate
			
			state[set] = isshared | DIRTYBIT;						// we are now shared and dirty
			statetext(set);
//			memory.mem[addr] = d[set];
//			memory.memR[addr].setTxt("address: a%d data: %d", addr, memory.mem[addr]);
//			memory.stale[addr] = 0;
//			memory.highlight(addr, 1);
			buslock = 0;
		
		else

			a[set] = addr;											// in case we are not shared, we are the only one
			aR[set].setTxt("a%d", addr);
			wValue++;
			d[set] = wValue;
			dR[set].setTxt("%d", wValue);

			state[set] = ST_M;										// revert to modified state
			statetext(set);
			memory.stale[addr] = 1;
			memory.memR[addr].setBrush(gray192brush);

		end;
	end;
end;

beg = LOGICALW/2-LOGICALW/NCPU*(NCPU-1)/2;
for (i=0; i<NCPU; i++)
	cache[i] = Cache(beg-70+i*LOGICALW/NCPU,325,i);					// calculate position of every cache set
end;

// event handling routine for a read
class readOp(int x, int y, int addr, int cpu, ref Rectangle r)

	b = SimpleButton(x, y, 65, 22, bgbrush, gray192brush, blackbrush, 0, "read");
	b.button.setTxt("read a%d", addr);

	when b.button.eventLB(int down, real xx, real yy)
		if ((down == 0) && cpulock[cpu] == 0)
			cpulock[cpu] = 1;
			r.setPen(greenpen);
			cache[cpu].resetStart();
			b.setborderpen(redpen);
			start();
			lastButton[cpu] = b;
			cache[cpu].read(addr, 1);
			r.setPen(blackpen);
			cache[cpu].resetEnd();
			cpulock[cpu] = 0;
			checkPoint();
		end;
	end;
end;

// event handling routine for a write
class writeOp(int x, int y, int addr, int cpu, ref Rectangle r)

	b = SimpleButton(x, y, 65, 22, bgbrush, gray192brush, blackbrush, 0, "read");
	b.button.setTxt("write a%d", addr);

	when b.button.eventLB(int down, real xx, real yy)
		if (down == 0 && cpulock[cpu] == 0)
			cpulock[cpu] = 1;
			r.setPen(greenpen);
			cache[cpu].resetStart();
			b.setborderpen(redpen);
			start();
			lastButton[cpu] = b;
			cache[cpu].write(addr);
			r.setPen(blackpen);
			cache[cpu].resetEnd();
			cpulock[cpu] = 0;
			checkPoint();
		end;
	end;
end;

//
// cpu object
//
class CPU(int x, int y, int cpu)
	r = Rectangle2(0, 0, blackpen, gray192brush, x, y, 150, 100);
	t = Txt(0, HLEFT | VTOP, x+130, y-20, redbrush, 0, "CPU %d", cpu);
	for (int i = 0; i < 4; i++)
		rb[i] = readOp(x+5, y+5+i*23, i, cpu, r);
		wb[i] = writeOp(x+80, y+5+i*23, i, cpu, r);
	end;
end;

beg = LOGICALW/2-LOGICALW/NCPU*(NCPU-1)/2;
for (i=0; i<NCPU; i++)
	cpu[i] = CPU(beg-70+i*LOGICALW/NCPU,425,i);
	lastButton[i] = cpu[i].rb[0].b;
end;

//
// user buttons and their event handlers
//
resetButton = SimpleButton(LOGICALW-275, LOGICALH-35, 75, 25, bgbrush, gray192brush, blackbrush, 0, "reset");
helpButton = SimpleButton(LOGICALW-115, LOGICALH-35, 75, 25, bgbrush, gray192brush, blackbrush, 0, "help");

//
// Vivio logo
//
// getURL
//
//	in Browser: hyperlinks to URL specified by 1st parameter
//	in Vivio IDE: hyperlinks to URL specified by 2nd parameter if present otherwise 1st paramter
//


when resetButton.button.eventLB(int down, real x, real y)
	if (down == 0)
		reset();
	end;
end;

when helpButton.button.eventLB(int down, real x, real y)
	if (down == 0)
		getURL("fireflyHelp.htm", "../../www/caches/fireflyHelp.htm");
	end;
end;

// eof