MESI Caching work start (was Re: caching and userapi)

[Antonio Vargas]

On Sat, Jul 19, 2003 at 01:20:18PM -0700, Matthew Dillon wrote:
> 
> :Matt, looking by my books, I've found out references to MESI protocol
> :on the PowerPC 604 manual (page 3-11), which it uses for it's caches.


[ snip ]

I've been coding a bit of this MESI protocol. Unfinished test code attached.

Greets, Antonio.

-- 

1. Dado un programa, siempre tiene al menos un fallo.
2. Dadas varias lineas de codigo, siempre se pueden acortar a menos lineas.
3. Por induccion, todos los programas se pueden
   reducir a una linea que no funciona.


#include <stdio.h>


#define NCPU 8
#define NMEM 10
#define NBUS 50


#define STATE_MODIFIED   0
#define STATE_EXCLUSIVE  1
#define STATE_SHARED     2
#define STATE_INVALID    3


#define BUS_READ       0
#define BUS_READW      1
#define BUS_INVALIDATE 2
#define BUS_PUSH       3


#define PROC_READ           0
#define PROC_READW          1
#define PROC_WRITE          2
#define PROC_INVALIDATE     3
#define PROC_COUNT          4


struct busentry{
	int addr;
	int data;
	int status;
};


struct busentry bus[NBUS];
struct busentry cache[NCPU][NMEM];

int readp[NCPU];
int writep;

int rnddata[3];


int rnd(void)
{
	int a,b,c;

	a = rnddata[0];
	rnddata[0] = b = rnddata[1];
	rnddata[1] = c = rnddata[2];
	rnddata[2] = a + b;

	return a * b + c;
}


void init(void)
{
	struct busentry *b;
	int i,j;

	for(i = 0 ; i < NCPU ; i++){

		readp[i] = -1;

		for(j = 0 ; j < NMEM ; j++){
			b = &cache[i][j];
			b->addr   = j;
			b->data   = i ? 999           : j;
			b->status = i ? STATE_INVALID : STATE_EXCLUSIVE;
		}
	}

	writep = 0;

	rnddata[0] = 2;
	rnddata[1] = 5;
	rnddata[2] = 9;
}


void dump(void)
{
	char a;
	int i,j;
	char s1[3 * NCPU + 1];
	char s2[3 * NCPU + 1];
	struct busentry *b;

	for(j = 0 ; j < NMEM ; j++){

		for(i = 0 ; i < NCPU ; i++){

			b = &cache[i][j];

			switch(b->status){
			case STATE_MODIFIED:  a = 'm'; break;
			case STATE_EXCLUSIVE: a = 'e'; break;
			case STATE_SHARED:    a = 's'; break;
			case STATE_INVALID:   a = 'i'; break;
			}

			sprintf(&s1[i],   "%c",    a);
			sprintf(&s2[i*3], " %02d", b->data);

		}

		s1[i] = 0;
		s2[i*3 - 2] = 0;
		printf("dump: %s %s %02d\n", s1, s2);
	}
}


void bus_process(int cpu)
{
	struct busentry *b,*c;
	int i,j;

	if(cpu >= NCPU) return;

	b = &bus[++readp[cpu]];
	c = &cache[cpu][b->addr];

	bus_process(cpu + 1);
}


void bus_send(int addr, int data, int status)
{
	struct busentry *b = &bus[writep];

	b->addr   = addr;
	b->data   = data;
	b->status = status;

	++writep;

	bus_process(0);
}


void bus_read_invalid(struct busentry *b, int addr){};
void bus_readw_shared(struct busentry *b, int addr){};
void bus_readw_invalid(struct busentry *b, int addr){};
void bus_write_shared(struct busentry *b, int addr, int data){};
void bus_write_invalid(struct busentry *b, int addr, int data){};
void bus_invalidate_modified(struct busentry *b, int addr){};
void bus_invalidate_exclusive(struct busentry *b, int addr){};
void bus_invalidate_shared(struct busentry *b, int addr){};

void proc(int cpu, struct busentry *b)
{
	struct busentry *c = &cache[cpu][b->addr];

	int cc = c->status;
	int addr = b->addr;
	int data = b->data;

	switch(b->status){
	case PROC_READ:
		switch(cc){
		case STATE_MODIFIED:                             break;
		case STATE_EXCLUSIVE:                            break;
		case STATE_SHARED:                               break;
		case STATE_INVALID:   bus_read_invalid(c, addr); break;
		}
		break;

	case PROC_READW:
		switch(cc){
		case STATE_MODIFIED:                              break;
		case STATE_EXCLUSIVE:                             break;
		case STATE_SHARED:    bus_readw_shared(c, addr);  break;
		case STATE_INVALID:   bus_readw_invalid(c, addr); break;
		}
		break;

	case PROC_WRITE:
		switch(cc){
		case STATE_MODIFIED:                                    break;
		case STATE_EXCLUSIVE: c->status = STATE_MODIFIED;       break;
		case STATE_SHARED:    bus_write_shared(c, addr, data);  break;
		case STATE_INVALID:   bus_write_invalid(c, addr, data); break;
		}
		break;

	case PROC_INVALIDATE:
		switch(cc){
		case STATE_MODIFIED:  bus_invalidate_modified(c, addr);  break;
		case STATE_EXCLUSIVE: bus_invalidate_exclusive(c, addr); break;
		case STATE_SHARED:    bus_invalidate_shared(c, addr);    break;
		case STATE_INVALID:                                      break;
		}
		break;
	}
}


int main(int argc, char **argv)
{
	int cpu;
	struct busentry b;

	init();
	dump();

	cpu      = rnd() % NCPU;
	b.addr   = rnd() % NMEM;
	b.data   = rnd() % (NCPU * NMEM % 99);
	b.status = rnd() % PROC_COUNT;

	proc(cpu, &b);

	return 0;
}