Heading:

Dragon memory bus protocol

Page Numbers: Yes X: 527 Y: 10.5"

Inter-Office Memorandum

ToDragonCore↑DateJuly 7, 1981

FromSuzukiLocationPalo Alto

SubjectDragon memory bus protocolOrganizationCSL

XEROX

Filed on: <YourName>FILENAME.memo

Issues

Locks in Cache Chip

There are two processes, Processor Interface process and Memory Bus Interface process in the cache chip. Both run asynchronously and share the cache mechanism. Therefore, I assume that there is a locking mechanism to let only one process use cache mechanism at a time.

This introduces the poissiblities of deadlocks between Processor Interface and Memory Bus Interface. Since Memory Bus Interface always holds memory bus when it tries to acquire the lock on the cache, we have to make sure that Processor Interface does not have the cache lock when it tries to acquire memory bus.

Memory Bus Protocol

Fetch: (3 phases)
1. Arg: ra
2. Data: RealMemory[ra]
3. Data: RealMemory[ra+1]
Exceptions: ParityError(Phases 2,3), RpOutOfRange(1)

Store: (3 phases)
1. Arg: ra
2. Data: Cache[loc].data[0] such that Cache[loc].rp=ra.rp and Cache[loc].b=ra.b
3. Data: Cache[loc].data[1]
Exceptions: ParityError(2,3), RpOutOfRange(1)

SFetch: (3 or 5 phases)
1. Arg: ra
2. Data: RealMemory[ra]
3. Data: RealMemory[ra+1]
4. Data: Cache[loc].data[0] such that Cache[loc].rp=ra.rp and Cache[loc].b=ra.b
5. Data: Cache[loc].data[1]
Exceptions: ParityError(2,3,4,5), RpOutOfRange(1)

WriteMap: (2 phases)
1. Arg: vp
2. Data: (flags, rp)
Exceptions: Denied(1)

ReadMap: (2 phases)
1. Arg: vp
2. Data: (flags, rp)
Exceptions: NotReady(1)

WriteMapFlags: (3 phases)
1. Arg: vp
2. Data: flags
3. Data: (oldFlags, rp)
Exceptions: NotReady(1)

SetMapDirty: (1 phase)
1. Arg: rp
Exceptions: Denied(1)

InvalidateVp: (1 phase)
1. Arg: rp

InvalidateRp: (1 phase)
1. Arg: rp.

MemoryBusType: TYPE = RECORD[
body: SELECT OVERLAID * FROM
Instruction => [Op: [0..377B], Arg: [0..77777777B]],
Data => [Data: [0..37777777777B]],
Exception => [ExceptionCode: [0..37777777777B]]];

IN Fetch, Store, SM, GMF, SMF, MemoryBus: MemoryBusType,
Shared
OUT MemoryBus, Shared
GUARDIAN <Errors when undefined opcode is used in MemoryBus>
STATE Cache: ARRAY [0..CacheSize) OF
RECORD [
data: ARRAY [0..DataSize) OF Word,
vp: VirtualPage,
b: PageOffset,
rp: RealPage,
flags: RECORD[
vaValid,
raValid,
ceDirty,
shared,
rpDirty: BOOLEAN]],
Master, MemoryBusSuccess: BOOLEAN,
Instruction, MemoryBusException,
fetchLoc, victimLoc, storeLoc: [0..CacheSize)
DATA FLOW
CONTROL
{
victimLoc ← 0;
REPEAT {
Fetch↑ -> FetchProc[] ||
Store↑ -> StoreProc[] ||
SM↑ -> SMProc[] ||
GMF↑ -> GMFProc[] ||
SMF↑ -> SMFProc[]}
//
{WHEN Init!:
REPEAT {
Shared ← FALSE;
IF Master THEN {
Master ← FALSE;
MemoryBus.Op ← instruction;
MemoryBus.Arg ← arg;
NewPhase ← TRUE;
NewPhase ← FALSE;
SELECT instruction FROM
Fetch => BusFetchMaster[];
Store => BusStoreMaster[];
SFetch => BusSFetchMaster[];
SetMapDirty => BusSetMapDirtyMaster[];
InvalidateVp => BusInvalidateVpMaster[];
InvalidateRp => BusInvalidateRpMaster[];
WriteMap => BusWriteMapMaster[];
ReadMap => BusReadMapMaster[];
WriteMapFlags => BusWriteMapFlagsMaster[];
ENDCASE}
ELSE {
WHEN NewPhase↑:;
SELECT MemoryBus.Op FROM
Fetch => BusFetchSlave[];
Store => BusStoreSlave[];
SFetch => BusSFetchSlave[];
SetMapDirty => BusSetMapDirtySlave[];
InvalidateVp => BusInvalidateVpSlave[];
InvalidateRp => BusInvalidateRpSlave[];
WriteMap => BusWriteMapSlave[];
ReadMap => BusReadMapSlave[];
WriteMapFlags => BusWriteMapFlagsSlave[];
ENDCASE}}}
}
PROCEDURES

-- SIGNALs

FetchFinished: SIGNAL = CODE;
StoreFinished: SIGNAL = CODE;
SFetchFinished: SIGNAL = CODE;
SetMapDirtyFinished: SIGNAL = CODE;
InvalidateVpFinished: SIGNAL = CODE;
InvalidateRpFinished: SIGNAL = CODE;
WriteMapFinished: SIGNAL = CODE;
ReadMapFinished: SIGNAL = CODE;
WriteMapFlagsFinished: SIGNAL = CODE;

--1) Bus Slave procedures

BusFetchSlave: PROC = {
success: BOOLEAN;
loc: [0..CacheSize);
LockCache[];
[success, loc] ← RpBMatch[MemoryBus.Arg];
UnlockCache[];
IF success THEN {
LockCache[];
Shared ← TRUE; WaitNewPhase[];
MemoryBus.Data ← Cache[loc].data[0]; WaitNewPhase[];
MemoryBus.Data ← Cache[loc].data[1]; Cache[loc].flags.shared ← TRUE; Done[];
UnlockCache[] }
ELSE {Done[]; DelayPhases[2]};
};

BusStoreSlave: PROC = {
success: BOOLEAN;
loc: [0..CacheSize);
LockCache[];
[success, loc] ← RpBMatch[MemoryBus.Arg];
IF success THEN Cache[loc].flags.ceDirty ← FALSE;
SetRpDirty[];
IF success THEN {
WaitNewPhase[];
Cache[loc].data[0] ← MemoryBus.Data; WaitNewPhase[];
Cache[loc].data[1] ← MemoryBus.Data; Done[];
UnlockCache[] }
ELSE {UnlockCache[]; Done[]; DelayPhases[2]};
};

BusSFetchSlave: PROC = {
success: BOOLEAN;
loc: [0..CacheSize);
LockCache[];
[success, loc] ← RpBMatch[MemoryBus.Arg];
SetRpDirty[];
IF success THEN {
Cache[loc].flags.ceDirty ← TRUE;
Shared ← TRUE; WaitNewPhase[];
MemoryBus ← Cache[loc].data[0]; WaitNewPhase[];
MemoryBus ← Cache[loc].data[1]; WaitNewPhase[];
Cache[loc].data[0] ← MemoryBus; WaitNewPhase[];
Cache[loc].data[1] ← MemoryBus; Done[];
UnlockCache[] }
ELSE {
UnlockCache[];
Done[];
DelayPhases[2];
IF Shared THEN DelayPhases[2]};
};

BusSetMapDirtySlave: PROC = {
Done[]
};

BusInvalidateVpSlave: PROC = {
i: [0..CacheSize);
LockCache[];
FOR i IN [0..CacheSize) DO
IF Cache[i].rp = MemoryBus.Arg THEN
Cache[i].flags.vaValid ← FALSE
UnlockCache[];
Done[]
};

BusInvalidateRpSlave: PROC = {
i: [0..CacheSize);
LockCache[];
FOR i IN [0..CacheSize) DO
IF Cache[i].rp = MemoryBus.Arg THEN
Cache[i].flags.raValid ← FALSE
UnlockCache[];
Done[]
};

BusWriteMapSlave: PROC = {
Done[];
IF Exception THEN RETURN;
DealyPhases[1];
};

BusReadMapSlave: PROC = {
Done[];
IF Exception THEN RETURN;
DealyPhases[1];
};

BusWriteMapFlagsSlave: PROC = {
Done[];
};

--2) Bus Master procedures

BusFetchMaster: PROC = {
WHEN EverybodyDone↑: ;
IF Exception THEN GOTO Failed;
LockCache[];
IF Shared THEN Cache[fetchLoc].flags.shared ← TRUE;
Cache[fetchLoc].data[0] ← MemoryBus.Data;
BeginNewPhase[!ANY => GOTO Failed];
Cache[fetchLoc].data[1] ← MemoryBus.Data;
BeginNewPhase[!ANY => GOTO Failed];
UnlockCache[];
MemoryBusSuccess ← TRUE;
NOTIFY FetchFinished;
EXITS
Failed => {
MemoryBusExcpetion ← MemoryBus.ExceptionCode;
MemoryBusSuccess ← FALSE;
NOTIFY FetchFinished}
};

BusStoreMaster: PROC = {
WHEN EverybodyDone↑: ;
IF Exception THEN GOTO Failed;
LockCache[];
Cache[storeLoc].flags.ceDirty ← FALSE;
SetDirty[];
MemoryBus.Data ← Cache[storeLoc].data[0];
BeginNewPhase[!ANY => GOTO Failed];
MemoryBus.Data ← Cache[storeLoc].data[1];
BeginNewPhase[!ANY => GOTO Failed];
UnlockCache[];
MemoryBusSuccess ← TRUE;
NOTIFY StoreFinished;
EXITS
Failed => {
MemoryBusExcpetion ← MemoryBus.ExceptionCode;
MemoryBusSuccess ← FALSE;
NOTIFY StoreFinished}
};

BusSFetchMaster: PROC = {
WHEN EverybodyDone↑: ;
IF Exception THEN GOTO Failed;
LockCache[];
IF Shared THEN Cache[fetchLoc].flags.shared ← TRUE;
Cache[fetchLoc].data[0] ← MemoryBus.Data;
BeginNewPhase[!ANY => GOTO Failed];
Cache[fetchLoc].data[1] ← MemoryBus.Data;
BeginNewPhase[!ANY => GOTO Failed];
IF Shared THEN {
Cache[fetchLoc].flags.ceDirty ← FALSE;
SetDirty[];
MemoryBus.Data ← Cache[fetchLoc].data[0];
BeginNewPhase[!ANY => GOTO Failed];
MemoryBus.Data ← Cache[fetchLoc].data[1];
BeginNewPhase[!ANY => GOTO Failed];
};
UnlockCache[];
MemoryBusSuccess ← TRUE;
NOTIFY SFetchFinished;
EXITS
Failed => {
MemoryBusExcpetion ← MemoryBus.ExceptionCode;
MemoryBusSuccess ← FALSE;
NOTIFY SFetchFinished}
};

BusSetMapDirtyMaster: PROC = {
WHEN EverybodyDone↑:;
IF Exception THEN GOTO Failed;
MemoryBusSuccess ← TRUE;
NOTIFY SetMapDirtyFinished;
EXITS
Failed => {
MemoryBusExcpetion ← MemoryBus.ExceptionCode;
MemoryBusSuccess ← FALSE;
NOTIFY SetMapDirtyFinished}
};

BusInvalidateVpMaster: PROC = {
WHEN EverybodyDone↑:;
MemoryBusSuccess ← TRUE;
NOTIFY InvalidateVpFinished
};

BusInvalidateRpMaster: PROC = {
WHEN EverybodyDone↑:;
MemoryBusSuccess ← TRUE;
NOTIFY InvalidateRpFinished
};

BusWriteMapMaster: PROC = {
WHEN EverybodyDone↑:;
IF Exception THEN GOTO Failed;
MasterPhases[1]
MemoryBusSuccess ← TRUE;
NOTIFY WriteMapFinished;
EXITS
Failed => {
MemoryBusExcpetion ← MemoryBus.ExceptionCode;
MemoryBusSuccess ← FALSE;
NOTIFY WriteMapFinished}
};

BusReadMapMaster: PROC = {
WHEN EverybodyDone↑:;
IF Exception THEN GOTO Failed;
MasterPhases[1];
MemoryBusSuccess ← TRUE;
NOTIFY ReadMapFinished;
EXITS
Failed => {
MemoryBusExcpetion ← MemoryBus.ExceptionCode;
MemoryBusSuccess ← FALSE;
NOTIFY ReadMapFinished}
};

BusWriteMapFlagsMaster: PROC = {
WHEN EverybodyDone↑:;
IF Exception THEN GOTO Failed;
MasterPhases[2];
MemoryBusSuccess ← TRUE;
NOTIFY WriteMapFlagsFinished;
EXITS
Failed => {
MemoryBusExcpetion ← MemoryBus.ExceptionCode;
MemoryBusSuccess ← FALSE;
NOTIFY WriteMapFlagsFinished}
};

--3) Processor Interface procedures

FetchProc: PROC = {
rp: [0..77777777B];
mapModified, rpDirty, success: BOOLEAN;
entryLoc: [0..CacheSize);
LockCache[];
DO
[success, entryLoc] ← VpBMatch[vp, b];
IF success THEN
{out ← Cache[entryLoc].data[w]; UnlockCache[]; RETURN};
[success, rp, rpDirty] ← VpMatch[vp];
SelectVictim[];
IF Cache[victimLoc].flags.ceDirty THEN VictimStore[victimLoc];
IF success THEN {
Cache[victimLoc] ← [vp: vp, b: b, rp: rp, flags: [vaValid: TRUE,
raValid: TRUE, ceDirty: FALSE, shared: FALSE, rpDirty: rpDirty]}
ELSE {
[flags, rp] ← ReadMap[vp];
Cache[victimLoc] ← [vp: vp, b: b, rp: rp, flags: [vaValid: TRUE,
raValid: FALSE, ceDirty: FALSE, shared: FALSE, rpDirty: flags.dirty]};
mapModified ← MemoryFetch[vp, victimLoc, rp, b];
IF ~mapModified THEN EXIT;
ENDLOOP;
out ← Cache[victimLoc].data[w];
UnlockCache[];
};

StoreProc: [vp: VirtualPage, b: PageOffset, w: WordOffset,
sData: Word] = {
savedRp: RealPage;
savedRpDirty, success: BOOLEAN;
entryLoc: [0..CacheSize);
LockCache[];
DO
[success, entryLoc] ← VpBMatch[vp, b];
IF ~success THEN {
[success, savedRp, savedRpDirty] ← VpMatch[vp];
IF ~success THEN
{[flags, savedRp] ← ReadMap[vp]; savedRpDirty ← flags.dirty};
SelectVictim[];
IF Cache[victimLoc].flags.ceDirty THEN VictimStore[victimLoc];
Cache[victimLoc] ← [vp: vp, b: b, rp: savedRp, flags: [vaValid: TRUE,
raValid: FALSE, ceDirty: FALSE, shared: FALSE, rpDirty: savedRpDirty]];
IF ~savedRpDirty THEN mapModified ← SetMapDirty[victimLoc, vp, savedRp];
IF mapModified THEN LOOP;
mapModified ← SFetch[victimLoc, vp, savedRp]
IF mapModified THEN LOOP;
UnlockCache[];
RETURN };
Cache[entryLoc].data[w] ← sData;
IF ~Cache[entryLoc].flags.rpDirty THEN {
mapModified ← SetMapDirty[entryLoc, vp, savedRp];
Cache[entryLoc].flags.reDirty ← TRUE};
IF mapModified THEN LOOP;
IF Cache[entryLoc].flags.shared
THEN mapModified ← MemoryStore[vp, entryLoc];
IF ~mapModified THEN EXIT;
ENDLOOP;
UnlockCache[];
};

SM: PROC [mf: MapFlags, rp: RealPageNumber,
vp: VirtualPageNumber] = {
success: BOOLEAN;
InvalidateVp[rp];
DO
success ← WriteMap[mf, rp, vp]
IF success THEN EXIT;
ENDLOOP
};

GMF: PROC [vp: VirtualPageNumber] RETURNS [mf: MapFlags, rp: RealPageNumber] = {
[mf, rp] ← ReadMap[vp];
};

SMF: PROC [newMf: MapFlags, vp: VirtualPageNumber]
RETURNS [mf: MapFlags, rp: RealPageNumber] = {
DO
[success, mf, rp] ← WriteMapFlags[newMf, vp];
IF success THEN EXIT;
ENDLOOP};

--4) Processor Interface to Bus Interface communication

VictimStore: PROC[victimLoc: [0..CacheSize)] = {
UnlockCache[];
RequestArbiter ← TRUE;
WHEN GrantArbiter↑: {
RequestArbiter ← FALSE;
instruction ← Store;
arg ← rp;
storeLoc ← victimLoc;
Master ← TRUE};
WAIT StoreFinished
LockCache[];
};

MemoryFetch: PROC[vp: [0..77777777B], victimLoc: [0..CacheSize), rp: [0..77777777B],
b: [0..377B]] RETURNS [BOOLEAN] = {
UnlockCache[];
RequestArbiter ← TRUE;
WHEN GrantArbiter↑: {
RequestArbiter ← FALSE;
LockCache[];
IF ~(Cache[victimLoc].flags.vaValid AND Cache[victimLoc].vp=vp) THEN RETURN[TRUE];
UnlockCache[];
fetchLoc ← victimLoc;
instruction ← Fetch;
arg ← rp;
Master ← TRUE};
WAIT FetchFinished
LockCache[];
RETURN[FALSE]
};

MemoryStore: PROC[vp: [0..77777777B], entryLoc: [0..CacheSize)] = {
UnlockCache[];
RequestArbiter ← TRUE;
WHEN GrantArbiter↑: {
RequestArbiter ← FALSE;
LockCache[];
IF ~(Cache[entryLoc].flags.vaValid AND Cache[entryLoc].vp=vp) THEN RETURN[TRUE];
UnlockCache[];
storeLoc ← entryLoc;
instruction ← Store;
arg ← Cache[entryLoc].rp;
Master ← TRUE};
WAIT StoreAndCheckMapFinished
LockCache[];
RETURN[FALSE]
};

SetMapDirty: PROC[loc: [0..CacheSize), vp, rp: [0..77777777B] RETURN[BOOLEAN] = {
UnlockCache[];
RequestArbiter ← TRUE;
WHEN GrantArbiter↑: {
RequestArbiter ← FALSE;
LockCache[];
IF ~(Cache[loc].flags.vaValid AND Cache[loc].vp=vp) THEN {
RETURN[TRUE]};
UnlockCache[];
instruction ← SetMapDirty;
arg ← rp;
Master ← TRUE};
WAIT StoreAndCheckMapFinished
LockCache[];
RETURN[FALSE]
};

InvalidateVp: PROC [rp: [0..77777777B]] = {
UnlockCache[];
RequestArbiter ← TRUE;
WHEN GrantArbiter↑: {
RequestArbiter ← FALSE;
instruction ← InvalidateVp;
arg ← rp;
Master ← TRUE};
WAIT StoreAndCheckMapFinished
LockCache[];
};

WriteMap: PROC[mf: MapFlags, rp: RealPageNumber, vp: VirtualPageNumber] RETURNS[BOOLEAN] = {
UnlockCache[];
RequestArbiter ← TRUE;
WHEN GrantArbiter↑: {
RequestArbiter ← FALSE;
instruction ← WriteMap;
arg ← rp;
Master ← TRUE};
WAIT WriteMapFinished
LockCache[];
RETURN[MemoryBusSuccess]
};

ReadMap: PROC[vp: VirtualPageNumber] RETURNS [mf: MapFlags, rp: RealPageNumber] = {
UnlockCache[];
DO
RequestArbiter ← TRUE;
WHEN GrantArbiter↑: {
RequestArbiter ← FALSE;
instruction ← ReadMap;
arg ← rp;
Master ← TRUE};
WAIT ReadMapFinished
IF MemoryBusSuccess THEN EXIT;
ENDLOOP;
LockCache[];
RETURN[MapFlags, MapRp]
};

WriteMapFlags: PROC[newMf: MapFlags, vp: VirtualPageNumber] RETURNS [success: BOOLEAN, mf: MapFlags, rp: RealPageNumber] = {
UnlockCache[];
RequestArbiter ← TRUE;
WHEN GrantArbiter↑: {
RequestArbiter ← FALSE;
instruction ← WriteMapFlags;
arg ← rp;
Master ← TRUE};
WAIT WriteMapFlagsFinished
LockCache[];
RETURN[MemoryBusSuccess, MapFlags, MapRp]
};

--5) Cache operations

RpBMatch: PROC [ra: [0..77777777B]] RETURNS [BOOLEAN, [0..CacheSize)] = {
i: CARDINAL;
rp: RealPage ← LOOPHOLE[ra, Ra].rp;
b: PageOffset ← LOOPHOLE[ra, Ra].b;
FOR i IN [0..CacheSize) DO
IF Cache[i].rp=rp AND Cache[i].flags.raValid AND Cache[i].b=b
THEN RETURN[TRUE,i];
ENDLOOP;
RETURN[FALSE,0]
};

VpBMatch: PROC [vp: VirtualPage, b: PageOffset] RETURNS [BOOLEAN, [0..CacheSize)] = {
i: CARDINAL;
FOR i IN [0..CacheSize) DO
IF Cache[i].vp=vp AND Cache[i].flags.vaValid AND Cache[i].b=b
THEN RETURN[TRUE,i];
ENDLOOP;
RETURN[FALSE,0]
};

VpMatch: PROC [vp: VirtualPage] RETURNS [BOOLEAN, RealPage, BOOLEAN -- rpDirty --] = {
i: CARDINAL;
FOR i IN [0..CacheSize) DO
IF Cache[i].vp=vp AND Cache[i].flags.raValid AND Cache[i].flags.vaValid
THEN RETURN[TRUE,Cache[i].rp, Cache[i].flags.rpDirty];
ENDLOOP;
RETURN[FALSE,0,FALSE]
};

SetRpDirty: PROC [rp: RealPage] = {
i: [0..CacheSize);
FOR i IN [0..CacheSize) DO
IF Cache[i].rp=rp THEN Cache[i].flags.rpDirty ← TRUE
ENDLOOP;
};

SelectVictim: PROC = {
victimLoc ← (victimLoc + 1) MOD CacheSize
};

--6) Synchronization

MasterPhases: PROC[number: CARDINAL] = {
THROUGH [0..number) DO
WHEN EverybodyDone↑:;
NewPhase ← TRUE; NewPhase ← FALSE
ENDLOOP
};

DelayPhases: PROC[number: CARDINAL] = {
THROUGH [0..number) DO
WHEN NewPhase↑: Done[]
ENDLOOP
};

BeginNewPhase: PROC = {
NewPhase ← TRUE; NewPhase ← FALSE;
WHEN EverybodyDone↑:;
IF Exception THEN ERROR
};

WaitNewPhase: PROC = {
Done[]; WHEN NewPhase↑:
};