
<<CacheSim.mesa>>
<<Don Curry February 11, 1988 11:05:38 am PST>>

DIRECTORY IO;

CacheSim: CEDAR PROGRAM
IMPORTS IO
= BEGIN
<<Types and Constants>>
wdsPerBlk:        CARDINAL = 8;
blksPerSLn:        CARDINAL = 4;
sLnsPerBLn:        CARDINAL = 8;
blksPerBLn:        CARDINAL = blksPerSLn*sLnsPerBLn;
sLnsPerSCache:    CARDINAL = 64;
SCPerBC:            CARDINAL = 8;
bLnsPerBC:        CARDINAL = sLnsPerSCache * SCPerBC;

AddrPageIdx:        TYPE = [0..4194304);            -- 22 bits
PageWdIdx:        TYPE = [0..1024);                -- 10 bits
BCLineIdx:        TYPE = [0..bLnsPerBC);
BlkWdIdx:        TYPE = [0..wdsPerBlk);
DeviceID:            TYPE = [0..1024);
DynaBusCmd:    TYPE = {
RBRqst,    RBRply,
WSRqst,    WSRply,
CWSRqst,    CWSRply,
WBRqst,    WBRply,    -- WBRply not used
FBRqst,    FBRply,
IORRqst,    IORRply,
IOWRqst,    IOWRply,
BIORqst,    BIORply, 
MapRqst,    MapRply,
DMRqst,    DMRply};

Word:            TYPE = LONG CARDINAL;
AddressRec:    TYPE = RECORD[page: AddrPageIdx_0, wd: PageWdIdx_0];
Data:            TYPE = REF DataAry;
DataAry:        TYPE = ARRAY WdIndex OF Word _ ALL[0];
BlockAry:    TYPE = RECORD[
victim:        BlkIndex    _ 0,
victimLock:    BOOL        _ FALSE,
blks:            ARRAY BlkIndex OF BlockRec];
BlockRec:         TYPE = RECORD[
owner:    BOOL            _ FALSE,        -- Owner
shared:    BOOL            _ FALSE,        -- Shared
rpValid:    BOOL            _ FALSE,        -- Real        page valid
vpValid:    BOOL            _ FALSE,        -- Virtual    page valid
rAddr:    AddressRec    _ [ ],            -- Real        address
vAddr:    AddressRec    _ [ ],            -- Virtual    address
data:        Data            _ NIL ];
SnoopRec:    TYPE = RECORD[
enabled:    BOOL            _ FALSE,        -- Enable snooping of the outstanding address
shared:    BOOL            _ FALSE,        -- Shared Accumulator
rplyStale:    BOOL            _ FALSE,        -- RplyStale
addr:        AddressRec    _ [ ] ];        -- Outstanding address
PacketRec:    TYPE = RECORD[
valid:        BOOL            _ FALSE,
head:        HeaderRec    _ [],
data:        Data            _ NIL ];
HeaderRec:    TYPE = RECORD[
id:                DeviceID            _ 0,
cmd:            DynaBusCmd    _ RBRqst,
shared:        BOOL                _ FALSE,
rAddr:        AddressRec        _ [ ] ];
FifoRec:    TYPE = RECORD[    
count:    INT _ 0,
ary:    SEQUENCE size: CARDINAL OF PacketRec ];

CacheRec:    TYPE = RECORD[
id:                DeviceID        _ 0,                        -- this caches id
p:                PacketRec    _ [],                        -- received packet
snoop:            SnoopRec        _ [],                        -- state of the snooper
array:            CacheAry    _ [],                        -- main cache arrary
fifoHi5:        REF FifoRec    _ NEW[FifoRec[4]],        -- Hi priority port for 5 cycle requests
fifoLo2:        REF FifoRec    _ NEW[FifoRec[1]],        -- Lo priority port for 2 cycle requests
tipFB:            BOOL            _ FALSE,                    -- a flush block request is outstanding
tipNFB:        BOOL            _ FALSE,                    -- non flush block request is outstanding
pAddr:        AddressRec    _ [ ],                        -- processor side address
pWord:        Word            _ 0,                        -- processor side data
];
c: Cache _ NewCache[];
<<Utils>>
NewCache: PROC RETURNS[c: Cache] _ {
c _ NEW[CacheRec];
c.p.data _ NEW[DataRec];
FOR blk IN BlkIndex DO
IF c.array[blk].data _ NEW[DataRec] ENDLOOP};

VirtualMatch: PROC[c: Cache]
RETURNS[found: BOOL _ FALSE, blk: BlkIndex _ 0] = {
FOR blk IN BlkIndex DO
IF c.array[blk].vAddr = c.pAddr THEN RETURN[TRUE, blk] ENDLOOP};

MatchPacketReal: PROC[c: Cache]
RETURNS[found: BOOL _ FALSE, blk: BlkIndex _ 0] = {
FOR blk IN BlkIndex DO
IF c.array[blk].rAddr = c.p.head.rAddr THEN RETURN[TRUE, blk] ENDLOOP};

ExtractWd: PROC[d: Data, addr: AddressRec] RETURNS[wd: Word] =
{RETURN[data[addr.wd MOD wdsPerBlk]]};

InsertWd: PROC[d: Data, addr: AddressRec, wd: Word] =
{data[addr.wd MOD wdsPerBlk] _ wd};
<<Hi slave controller - Read and Write>>
ReceivePacket: PROC[c: Cache] = {
SELECT c.p.head.cmd FROM
RBRqst    => {
IF myRequest
THEN {
InitSnooper[snoop, rAddr];
array[array.victim].rpValid _ F;
array[array.victim].vpValid _ F}
ELSE {
[aMatch, blk]    _ MatchPacketReal[c];
sMatch            _ SnoopMatch[snoop, rAddr];
IF aMatch THEN array[blk].shared _ T;
IF sMatch THEN snoop.shared _ T;
busShared _ aMatch OR sMatch;
busOwner _ aMatch AND array[blk].owner;
IF aMatch AND array[blk].owner THEN
EnQOut[fifo: fifoHi5, cmd:RBRply, shared: T, addr: rAddr, data: array[blk].data]}};
RBRply    => 
IF myRequest THEN {
[aMatch, blk]        _ MatchPacketReal[c];
snoop.enabled        _ F;
tipNonFB                _ F;
array.victimLock    _ F;
IF aMatch    THEN array[blk].vAddr        _ vAddr;
IF ~aMatch    THEN array[array.victim]    _ [
owner:    F,
shared:    snoop.shared OR p.shared,
rpValid:    T,
vpValid:    ~snoop.RplyStale,
vAddr:    vAddr,
rAddr:    rAddr,
data:        data ]};

WSRqst, CWSRqst    => {
IF myRequest
THEN InitSnooper[snoop, rAddr]
ELSE {
[aMatch, blk]    _ MatchPacketReal[c];
sMatch            _ SnoopMatch[snoop, rAddr];
busShared        _ aMatch OR sMatch} };
WSRply, CWSRply    => {
IF myRequest
THEN    {snoop.enabled _ F;    tipNonFB _ F}
ELSE    {sMatch _ SnoopMatch[snoop, rAddr];    IF sMatch THEN snoop.rplyStale _ T};
[aMatch, blk]    _ MatchPacketReal[c];
IF aMatch THEN {
array[blk].shared    _ p.shared OR myRequest AND snoop.shared;
array[blk].owner    _ myRequest;
word _ ExtractWd[array[blk].data. rAddr];
IF cmd=CWSRply AND word=old THEN word _ new;
array[blk].data _ InsertWd[array[blk].data, rAddr, word]} };

WBRqst    => {
IF myRequest
THEN InitSnooper[snoop, rAddr]
ELSE {
[aMatch, blk]    _ MatchPacketReal[c];
sMatch            _ SnoopMatch[snoop, rAddr];
IF sMatch THEN    snoop.rplyStale        _ T;
IF aMatch THEN array[blk].data        _ data;
IF aMatch THEN array[blk].owner    _ F} };
WBRply    => IF myRequest THEN {snoop.enabled _ F;    tipNonFB _ F};
FBRqst    => IF myRequest    THEN snoop.enabled _ F;
FBRply    => IF myRequest    THEN                         tipFB _ F;
<<Hi slave controller - IO>>

IORRqst    => {
[ioMatch, blk]        _ IOMatch[array, ioAddr];
IF ioMatch THEN {
wd: Word _ ExtractWd[array[blk].data, ioAddr];
EnQOut[fifo: fifoHi5, cmd: IORRply, addr: ioAddr, wd: wd]} };
IORRply    => IF myPacket THEN tipNonFB _ F;
IOWRqst    => {
[ioMatch, blk]        _ IOMatch[array, ioAddr];
IF ioMatch THEN {
array[blk].data _ InsertWd[array[blk].data, ioAddr, data];
EnQOut[fifo: fifoHi5, cmd: IOWRply, addr: ioAddr, data: data]} };
IOWRply    => IF myPacket THEN tipNonFB _ F;
BIORqst    => NoOp[];
BIORply    => {
blk:        BlkIndex;
ioMatch:    BOOL;
IF myPacket THEN    tipNonFB _ F;
[ioMatch, blk]        _ IOMatch[array, ioAddr];
IF ioMatch THEN
array[blk].data _ InsertWd[array[blk].data, ioAddr, data]};

MapRqst    => NoOp[];
MapRply    => {
myPacket: BOOL _ requestorId=myId;
IF myPacket THEN tipNonFB _ F;
IF myPacket THEN array[mapBlk] _ [
shared:    snoop.shared OR p.shared,
owner:    F,
vpValid:    ~snoop.RplyStale,
rpValid:    T,
vAddr:    vAddr,
rAddr:    rAddr ]};
DMRqst    => NoOp[];
DMRply    => { };    -- Clear vpValid on all matching real pages
ENDCASE;
<<Lo slave controller>>
SELECT cmd FROM
RBRqst    => {
reply            _ busOwner; -- After Wait[dso]
rplyShared    _ busShared; -- After Wait[dso]
IF ~ownedBelow THEN
EnQOut[fifo: fifoHi5, cmd: RBRply, shared: sharedBelow, addr: rAddr, data: mem[rAddr]]};
RBRply    => NoOP[];
WBRqst    => {
MemStore[mem, rAddr, data];
EnQOut[fifo: fifoHi5, cmd: WBRply, shared: F, addr: rAddr]};
WBRply    => NoOP[];
FBRqst    => {
MemStore[mem, rAddr, data];
EnQOut[fifo: fifoHi5, cmd: FBRply, shared: F, addr: rAddr]};
FBRply    => NoOP[];
WSRqst    => {
p.shared _ busShared; -- After Wait[dso];
EnQOut[fifo: fifoHi5, cmd: WSRply, shared: p.shared, addr: rAddr, data: data]};
WSRply    => NoOP[];
CWSRqst    => {
p.shared _ busShared; -- After Wait[dso];
EnQOut[fifo: fifoHi5, cmd: CWSRply, shared: p.shared, addr: rAddr, new: new, old: old]};
CWSRply    => NoOP[];
IORRqst    => {
wd:        Word;
ioMatch:    BOOL;
[ioMatch, wd]        _ IOMatch[array, ioAddr];
IF ioMatch THEN {
data _ RdIOReg[ioAddr];
EnQOut[fifo: fifoHi5, cmd: IORRply, addr: ioAddr, data: data]}};
IORRply    => NoOP[];
IOWRqst    => {
wd:        Word;
ioMatch:    BOOL;
[ioMatch, wd]        _ IOMatch[array, ioAddr];
IF ioMatch THEN {
WtIOReg[ioAddr, data];
EnQOut[fifo: fifoHi5, cmd: IOWRply, addr: ioAddr, data: data]}};
IOWRply    => NoOP[];
BIORqst    => EnQOut[fifo: fifoHi5, cmd: BIOWRply, addr: ioAddr, data: data];
BIORply    => NoOp[];
MapRqst    => NoOp[];
MapRply    => NoOp[];
DMRqst    => EnQOut[fifo: fifoHi5, cmd: DeMapRply, addr: rAddr];
DMRply    => NoOp[];
ENDCASE};
<<Cache processor side>>
PFetch: PROC[c: Cache] = {
aMatch:    BOOL;
blk:        BlkIndex;
[aMatch, blk]    _ VirtualMatch[c];
IF ~aMatch THEN {
HandleMiss[c];
[aMatch, blk]    _ VirtualMatch[c]};
c.pWord _ ExtractWd[ c.array[blk].data[c.pAddr MOD wdsPerBlk] ] };

PStore: PROC[c: Cache] = {
aMatch:    BOOL;
blk:        BlkIndex;
[aMatch, blk]    _ VirtualMatch[c];
IF ~aMatch THEN {
HandleMiss[];
[aMatch, blk]    _ VirtualMatch[c];
IF ~array[blk].shared
THEN {
InsertWd[array[blk].data, vAddr, c.pWord];
array[blk].owner _ T}
ELSE {
EnQOut[fifo: bufLo2, cmd: WSRqst, shared: F, addr: rAddr, wd: c.pWord];
tipNonFB _ T;    WHILE tipNonFB DO NoOp[] ENDLOOP}}};

HandleMiss: PROC[c: Cache] = {
aMatch:    BOOL;
blk:        BlkIndex;
rAddr:    AddressRec;
WHILE tipFB DO NoOp[] ENDLOOP; -- tipFB must be cleared on Reset
[aMatch, blk] _ VirtualPageMatch[c];
<<Multiple Matches Possible>>
IF aMatch
THEN rAddr _ array[blk].rAddr
ELSE {
EnQOut[fifo: bufLo2, cmd: MapRqst, shared: F, addr: vAddr];
tipNonFB _ T;    WHILE tipNonFB DO NoOp[] ENDLOOP};
<<Somthing funny to make rAddr from vAddr and rPage>>
FreezeVictim[];
victimAddr _ array[array.victim].rAddr;
IF array[array.victim].owner THEN {
InitSnooper[snoop, array[array.victim].raddr]; -- do this before owner can change
EnQOut[fifo: fifoHi5, cmd: FBRqst, addr: rAddr, data: array[array.victim].data];
tipFB _ 1};  -- Snooper must abort FB if stale data (WSRply, CWSRply, WB)
EnQOut[fifo: bufLo2, cmd: RBRqst, shared: F, addr: rAddr, data: victimAddr];
tipNonFB _ T;    WHILE tipNonFB DO NoOp[] ENDLOOP};
<<Note that we don't wait for the FBRply. Its checked for before the next processor reference!>>

END.