// Vivio MOESI cache coherency protocol animation

// 27/08/02 first version [based on Vivio Write-Once and Firefly animations]
// 04/12/02 read cache line from memory on a write miss
// 03/06/05 corrected URL link to MESIHelp.htm
// 23/01/06 Vivio 4.0
// 20/02/06 real x,y event parameters
// 07/11/06 added extra wait(1) after getting bus lock
// 11/01/07 added Vivio logo
// 20/11/08 revised by Djordje Jevdjic

#include "standard.vin"
#include "SimpleButton.vin"

const LOGICALW = 800;
const LOGICALH = 600;

setViewport(0, 0, LOGICALW, LOGICALH, 1);

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

//
// fonts
//
smallFont = Font("Times New Roman", 14, 0);
hintFont = Font("Times New Roman", 16, 0);
titleFont = Font("Times New Roman", 24, 0);

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

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

const int NCPU = 4;			// number of cpus

const int TICKS = 20;		// animation speed

const int INVALID = 0;		// MESI cache line states
const int SHARED = 1;	
const int EXCLUSIVE = 2;	
const int OWNED = 3;
const int MODIFIED = 4;

const int READ = 0;
const int WRITE = 1;
const int UPGRADE = 1;

int wValue		= 0;		// value written into cache
int buglevel	= 0;		// buglevel [0 = bugfree]

int dirtycpu	= -1;		// indicates CPU supplies dirty data
int isshared	= 0;		// indicates a shared read
int exclusivecpu= -1;
int watchcnt	= 0;		// count watch() completions
int varwatchcnt = 0;

buslock = 0;				// bus lock
int cpulock[*];

SimpleButton lastButton[*];	// remember last button pressed

//
// vertical double headed bus arrow object
//
// separate up, down and body objects used 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);
	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, whead,0, 2*whead,whead, 0,whead);
	up.setOpacity(0);
	down = Polygon(0, AAFILL | ABSOLUTE, 0, brush, 0,0, 0,0, 2*whead,0, whead,whead);
	down.setOpacity(0);

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

	//
	// animates 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-whead, y+(l-whead));
		body.setPos(x-wbody, y+l);
		body.setSize(2*wbody+1, 0);
		up.setOpacity(255);
		body.setOpacity(255);

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

	end;

	//
	// animates 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-whead, y);
		body.setPos(x-wbody, y);
		body.setSize(2*wbody+1, 0);
		down.setOpacity(255);
		body.setOpacity(255);

		//
		// final positions, size & opacity
		//
		down.setPos(x-whead, y+l-whead, ticks, 1, 0);
		body.setSize(2*wbody+1, l+1-whead, 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)

	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);

	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;

	function highlight(int addr, int flag)
		memR[addr].setBrush((flag) ? greenbrush : (stale[addr]) ? gray192brush : whitebrush);
	end;

	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)
		arrow.setBrush((flag) ? brush : blackbrush);
	end;
end;

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

memory = Memory(325, 70);

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

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

	sharedbus = BusArrow(x+14, y-42, 7, 3, 42, magentabrush);
	abus = BusArrow(x+58, y-75, 10, 4, 74, bluebrush);
	dbus = BusArrow(x+116, y-105, 10, 4, 104, redbrush);
	cpuabus = BusArrow(x+45, y+50, 10, 4, 50, bluebrush);
	cpudbus = BusArrow(x+115, 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] = INVALID;
		stateR[i] = Rectangle2(0, 0, blackpen, whitebrush, x+5, y+6+i*20, 20+1, 17+1, blackbrush, 0, "I");
		stateR[i].setTxtOff(0, 1);
		a[i] = 0;
		aR[i] = Rectangle2(0, 0, blackpen, whitebrush, x+25, y+6+i*20, 60+1, 17+1);
		aR[i].setTxtOff(0, 1);
		d[i] = 0;
		dR[i] = Rectangle2(0, 0, blackpen, whitebrush, x+85, y+6+i*20, 60+1, 17+1);
		dR[i].setTxtOff(0, 1);
	end;

	//
	// helper function to set values
	//
	function setvalues(int set, int addr, int data)
		a[set] = addr;
		aR[set].setTxt("a%d", addr);
		d[set] = data;
		dR[set].setTxt("%d", data);
	end;

	//
	// highlight cache line
	//
	function highlight(int set, int flag)
		brush = (flag) ? greenbrush : whitebrush;
		stateR[set].setBrush(brush);
		aR[set].setBrush(brush);
		dR[set].setBrush(brush);
	end;

	//
	// reset cache lines, cpu address and data busses
	//
	function reset(int i)
		cache[i].cpuabus.reset();
		cache[i].cpudbus.reset();
		cache[i].highlight(0, 0);
		cache[i].highlight(1, 0);
	end;

	//
	// reset ALL busses
	//
	function resetbus()
		memory.abus.reset();
		memory.dbus.reset();
		ddbus.arrow.setBrush(blackbrush);
		aabus.arrow.setBrush(blackbrush);
		ddbus.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;

	//
	// reset objects at start of a read or write operation
	//
	function resetStart()
		for (int i = 0; i < NCPU; i++)
			if ((cpulock[i] == 0) || (cpu == i))
				reset(i);
				lastButton[i].setborderpen(blackpen);
			end;
		end;
		if (buslock == 0)
			resetbus();
		end;
	end;

	//
	// reset objects at end of a read or write operation
	//
	function resetEnd()
		for (int i = 0; i < NCPU; i++)
			if (cpulock[i] == 0)
				reset(i);
				lastButton[i].setborderpen(blackpen);
			end;
		end;
	end;

	//
	// flush data from cache line to memory
	//
	function flush(int addr)
		set = addr % 2;
		flushaddr = a[set];
		abus.moveup(TICKS, 0);
		dbus.moveup(TICKS, 1);
		aabus.highlight(1);
		ddbus.highlight(1);
		memory.abus.moveup(TICKS, 0);
		memory.dbus.moveup(TICKS, 1);
		state[set] = INVALID;
		stateR[set].setTxt("I");
		memory.stale[flushaddr] = 0;
		memory.memR[flushaddr].setBrush(greenbrush);
		memory.mem[flushaddr] = d[set];
		memory.memR[flushaddr].setTxt("address: a%d data: %d", flushaddr, memory.mem[flushaddr]);
		resetbus();
	end;

	//
	// each cache must watch the bus and update its state according to the protocol
	//
	// if addr NOT in cache then no action need be taken
	//
	// bus read: must assert shared line & update state to SHARED
	//		  	 if cache line MODIFIED must intervene and place data on bus
	// bus write: must set state to INVALID
	//
	
	function watch(int addr, int operation)

		int set = addr % 2;

		//
		// test if address in cache
		// 
		int hit = (a[set] == addr) && (state[set] != INVALID);
		
		abus.movedown(TICKS, 1);
	
		//
		// return if address not in cache
		//
		if (!hit)
			varwatchcnt++;
			watchcnt++;
			return;
		end;
		
		//
		// calculate isshared, dirtycpu & exclusivecpu here
		//
		isshared = 1;
		if (state[set] == MODIFIED || state[set] == OWNED)
    		dirtycpu = cpu;
		end; 
		if (state[set] == EXCLUSIVE)
    		exclusivecpu = cpu;
		end; 

		
		if (operation == READ) 
			//
			// read    ---Probe Read Hit
			//			
			
			sharedbus.moveup(TICKS, 0);			
			if (state[set] == OWNED)
				highlight(set, 1);
				dbus.moveup(TICKS, 0);
			end;
			if (state[set] == MODIFIED)
				state[set] = OWNED;
				stateR[set].setTxt("O");
				highlight(set, 1);
				dbus.moveup(TICKS, 0);
			end;
			if (state[set] == EXCLUSIVE)
				state[set] = SHARED;
	  			stateR[set].setTxt("S");
				highlight(set, 1);
				dbus.moveup(TICKS, 0);
			end;
			varwatchcnt++;
			wait(TICKS);
		else

			//
			// write or upgrade  --probe write hit
			//
			state[set] = INVALID;
			stateR[set].setTxt("I");
			highlight(set, 1);
			varwatchcnt++;
		end;
		watchcnt++;

	end;

	//
	// initiate bus watching on other CPUs
	//
	function buswatch(int addr, int cpu, int operation)
		int set=addr%2;
		dirtycpu = -1;
		exclusivecpu=-1;
		isshared = 0;
		varwatchcnt = 0;
		watchcnt = 0;

		memory.abus.moveup(TICKS,0);
		
		for (int i = 0; i < NCPU; i++)
			if (i != cpu)
				fork(cache[i].watch(addr, operation));
			end;
		end;
				
		
		//
		// wait for the NCPU-1 forked watch() functions to finish generating vars
		// in order to know whether to animate memory data read
		//
		int aniwaitcount=0;
		while (varwatchcnt < NCPU-1)
			wait(1);
			aniwaitcount++;
		end;
		

		if ((dirtycpu<0) && (exclusivecpu<0) && (operation==READ))
			memory.highlight(addr,1);
			memory.dbus.movedown(TICKS*2-aniwaitcount,1);
			ddbus.highlight(1);
		end;

		
					
		
		//
		// wait for the NCPU-1 forked watch() functions to finish
		//
		while (watchcnt < NCPU-1)
			wait(1);
		end;
		//cache[cpu].sharedbus.movedown(5, 1);
		if (isshared && operation == READ)
				sharedBus.highlight(1);
		end;
	end;

			
	//
	// CPU cache read
	//
	// miss: read data from memory or another cache
	// hit:  read from cache locally
	//
	function read(int addr, int animatecpu, int updateMemory)
		int set = addr % 2;
		int fromcpu;
		
		if (animatecpu)
			cpuabus.moveup(TICKS, 1);
		end;
		

		//
		// check for hit
		//
		if ((a[set] == addr) && (state[set] != INVALID))
			highlight(set, 1);
			if (animatecpu)
				cpudbus.movedown(TICKS, 1);
			end;
			return;
		end;

		//
		// miss
		//	
		while (buslock)
			wait(1);
		end;
		buslock = 1;
		wait(1); // {joj 7/11/06}
		resetbus();
		
		//
		// flush cache line if MODIFIED or OWNED since we need the cache line (replacement)
		//
		if ((state[set] == MODIFIED) || (state[set] == OWNED) )  // write out dirty cache line
			flush(addr);
		end;
		
		state[set] = INVALID;
		stateR[set].setTxt("I");
	
		highlight(set, 1);
		abus.moveup(TICKS, 1);
		aabus.highlight(1);
		buswatch(addr, cpu, 0);
		
		
		if (dirtycpu >= 0) 
		    fromcpu=dirtycpu;
		else
		    fromcpu=exclusivecpu;
		end;
		
		
		if(updateMemory && fromcpu>=0)
			ddbus.highlight(1);
			memory.dbus.moveup(TICKS,0);
			memory.stale[addr]=0;		
			memory.mem[addr] = cache[fromcpu].d[set];
   			memory.memR[addr].setTxt("address: a%d data: %d", addr, memory.mem[addr]);
			memory.highlight(addr,1);
		end;
		
		
		//
		// read data from another cache or memory
		//				
		
	
		
		if (isshared==1)
			sharedbus.movedown(TICKS,0);
		end;
		
		if (dirtycpu >= 0) 
		    fromcpu=dirtycpu;
		else
		    fromcpu=exclusivecpu;
		end;
		
		ddbus.highlight(1);
		dbus.movedown(TICKS, 1);
				
		a[set] = addr;
		aR[set].setTxt("a%d", addr);
		d[set]=fromcpu>=0 ? cache[fromcpu].d[set] : memory.mem[addr];
		dR[set].setTxt("%d", d[set]);
		state[set] = isshared ? SHARED : EXCLUSIVE;
		stateR[set].setTxt(isshared ? "S" : "E");
		highlight(set,1);
		
		if (animatecpu)
			cpudbus.movedown(TICKS, 1);
		end;
		buslock = 0;

	end;

	//
	// CPU cache write
	//
	// flush cache line if MODIFIED
	//
	// miss: read data from memory or another cache if it intervenes
	//
	// hit:  if EXCLUSIVE or MODIFIED local write
	//		 if INVALID or SHARED write and enter MODIFIED state [other caches will invalidate]
	//
	function write(int addr)

		int set = addr % 2;
		int miss = ((state[set] == INVALID) || (a[set] != addr));
		cpudbus.moveup(TICKS, 0);
		cpuabus.moveup(TICKS, 1);
		highlight(set, 1);

		
		//
		// write miss
		//
		if (miss)
			//
			// flush if cache line dirty (MODIFIED or OWNED) - replacement
			//
			if ((state[set] == MODIFIED) || (state[set] == OWNED))
			
				//
				// need to get bus lock
				//
				while (buslock)
					wait(1);
				end;
				buslock = 1;
				wait(1); // {joj 7/11/06}
				resetbus();
				flush(addr);
				buslock = 0;

			end;
		
			//
			// write-allocate - read data from memory or other cache first
			//
			read(addr, 0, 1);
			wait(TICKS);
			
			if(state[set]==SHARED)
				while (buslock)
					wait(1);
				end;
				buslock = 1;
				wait(1); 
				resetbus();

				wValue += 1;
				setvalues(set, addr, wValue);
		
				abus.moveup(TICKS, 0);
				aabus.highlight(1);
				buswatch(addr, cpu, UPGRADE);
				state[set] = MODIFIED;
				stateR[set].setTxt("M");
				memory.stale[addr] = 1;
				memory.memR[addr].setBrush(gray192brush);
				buslock = 0;
			end;
			
			if(state[set]==EXCLUSIVE)
				wValue += 1;
				setvalues(set, addr, wValue);
				state[set] = MODIFIED;
				stateR[set].setTxt("M");
				memory.stale[addr] = 1;
				memory.memR[addr].setBrush(gray192brush);
			end;
			return;
		end;
		
		// write hit
		
	   if ((state[set] == MODIFIED) || (state[set] == EXCLUSIVE))
			wValue += 1;
			setvalues(set, addr, wValue);
			state[set] = MODIFIED;
			stateR[set].setTxt("M");
			memory.stale[addr] = 1;
			memory.memR[addr].setBrush(gray192brush);
	   
	   else  // SHARED or OWNED
			while (buslock)
				wait(1);
			end;
			buslock = 1;
			wait(1); 
			resetbus();

			wValue += 1;
			setvalues(set, addr, wValue);

			abus.moveup(TICKS, 0);
			aabus.highlight(1);
			buswatch(addr, cpu, UPGRADE);
			state[set] = MODIFIED;
			stateR[set].setTxt("M");
			memory.stale[addr] = 1;
			memory.memR[addr].setBrush(gray192brush);
			buslock = 0;
		end;
	end;
end;



//
// CPU read button
//
class readOp(int x, int y, int addr, int cpu, 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(1);
			lastButton[cpu] = b;
			cache[cpu].read(addr, 1, 0);
			r.setPen(blackpen);
			cache[cpu].resetEnd();
			cpulock[cpu] = 0;
			checkPoint();
		end;
	end;
end;

//
// CPU write button
//
class writeOp(int x, int y, int addr, int cpu, Rectangle r)

	b = SimpleButton(x, y, 65, 22, bgbrush, gray192brush, blackbrush, 0, "write");
	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(1);
			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;


for (int j=0;j<NCPU;j++)
	int margin=50;
	int xstep=(800-2*margin)/NCPU;
	cache[j] = Cache(margin+j*xstep+(xstep-150)/2, 325, j);
	//
	// CPUs
	//
	cpu[j] = CPU(margin+j*xstep+(xstep-150)/2, 425, j);

	//
	// remember last button pressed on each CPU
	//
	lastButton[j] = cpu[j].rb[0].b;
	
	cpulock[j] = 0;				// CPU locks


end;

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

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