DIRECTORY
Basics USING [BITSHIFT],
CacheModels,
Convert,
DragOpsCross USING [Half, Word, ZerosWord],
DragOpsCrossUtils USING [AddDelta, HalfShift, HalfToCard, HalfXor, LowHalf, WordToHalves],
IO, Rope;

StandardCache: CEDAR PROGRAM
IMPORTS Basics, Convert, DragOpsCrossUtils, IO, Rope = 

BEGIN OPEN DragOpsCross, DragOpsCrossUtils;


Cache: TYPE = CacheModels.Cache;

wordsPerQuad: NAT = 4;
logWordsPerQuad: NAT = 2;
maxQuadsPerLine: NAT = 8;
wordsPerPage: CARDINAL = CacheModels.wordsPerPage;
QuadIndex: TYPE =  [0..maxQuadsPerLine);

PageEntry: TYPE = REF PageEntryRep;
PageEntryRep: TYPE = RECORD [
next: PageEntry _ NIL,
pageAddr: Word _ ZerosWord,
useCount: INT _ 0
];

None: PACKED ARRAY QuadIndex OF BOOL = ALL[FALSE];

HashEntry: TYPE = REF HashEntryRep;
HashEntryRep: TYPE = RECORD [
next: HashEntry _ NIL,
lineAddr: Word _ ZerosWord,
index: NAT _,
chunkPresent: PACKED ARRAY QuadIndex OF BOOL _ None,
dirty: PACKED ARRAY QuadIndex OF BOOL _ None,
referenced: PACKED ARRAY QuadIndex OF BOOL _ None
];

CacheData: TYPE = REF CacheDataRep;
CacheDataRep: TYPE = RECORD [
stats: CacheStats _ [],
hashVector: HashVector _ NIL,
pageEntryCount: INT _ 0,
pageList: PageEntry _ NIL,
freePageList: PageEntry _ NIL,
victimIndex: CARDINAL _ 0,
lru: BOOL _ FALSE,
rover: NAT _ 0,
quadsPerLine: NAT _ 2,
realCache: CacheModels.Cache _ NIL,
lineTable: SEQUENCE linesInCache: NAT OF HashEntry
];

CacheStats: TYPE = RECORD [
probes: INT _ 0,
readProbes: INT _ 0,
writeProbes: INT _ 0,
writeMisses: INT _ 0,
writeClean: INT _ 0,
chunkMisses: INT _ 0,
lineMisses: INT _ 0,
jumpMisses: INT _ 0,
mapMisses: INT _ 0,
dirtyWrites: INT _ 0
];

HashLim: CARDINAL = 512;
HashVector: TYPE = REF HashVectorRep;
HashVectorRep: TYPE = ARRAY [0..HashLim) OF HashEntry;

NewCache: PUBLIC PROC [lines: [0..4096) _ 100, quadsPerLine: [0..8) _ 2, lru: BOOL _ FALSE, realCache: CacheModels.Cache] RETURNS [cache: CacheModels.Cache] = {
cache _ NEW[CacheModels.CacheRec _ [
private: NEW[CacheDataRep[lines] _ [quadsPerLine: quadsPerLine, lru: lru, realCache: realCache, lineTable: NULL]],
fetch: Fetch, store: Store, reset: Reset, flush: Flush, print: Print, 
data: NIL]];
Reset[cache];
};

Reset: CacheModels.CacheResetProc -- [cache: CacheModels.Cache] --  = {
private: CacheData = NARROW[cache.private];
private.pageList _ NIL;
private.hashVector _ NEW[HashVectorRep _ ALL[NIL]];
private.victimIndex _ 0;
private.pageEntryCount _ 0;
FOR i: NAT IN [0..private.linesInCache) DO
private[i] _ NEW[HashEntryRep _ [index: i]];
ENDLOOP;
private.stats _ []; -- zero out statistics
private.realCache.reset[private.realCache];
};

Flush: CacheModels.CacheFlushProc -- [cache: CacheModels.Cache] --  = {
private: CacheData = NARROW[cache.private];
private.pageList _ NIL;
private.hashVector^ _ ALL[NIL];
private.victimIndex _ 0;
private.pageEntryCount _ 0;
FOR i: NAT IN [0..private.linesInCache) DO
private[i]^ _ [index: i];
ENDLOOP;
private.realCache.flush[private.realCache];
};

Print: CacheModels.CachePrintProc -- [cache: CacheModels.Cache, stream: STREAM, name: ROPE, resetStatistics: BOOL _ TRUE] --  = {
Realn: PROC [r: REAL, n: NAT] RETURNS [IO.Value] = {
RETURN [[rope[Convert.RopeFromReal[r, n]]]]};
private: CacheData = NARROW[cache.private];
quadMisses: INT _ private.stats.chunkMisses;
misses: INT _ quadMisses + private.stats.lineMisses;
probes: INT _ private.stats.probes;
rProbes: REAL _ probes;
rMisses: REAL _ misses;
stream.PutF[
"\nStats for %g (lines: %g, quads/line: %g)\n  probes: %g\n",
[rope[IF private.lru THEN Rope.Cat[name, " (pseudo-lru)"] ELSE name]], 
[integer[private.linesInCache]], [integer[private.quadsPerLine]], [integer[probes]]];
IF probes = 0 THEN RETURN;
stream.PutF[
"read probes: %g, write probes: %g\n",
[integer[private.stats.readProbes]], [integer[private.stats.writeProbes]]];
stream.PutF[
"write misses: %g, writes to clean quads: %g\n",
[integer[private.stats.writeMisses]], [integer[private.stats.writeClean]]];
stream.PutF[
"  misses: %g (%g (%g%%) existing line)\n",
[integer[misses]], [integer[private.stats.chunkMisses]], 
IF misses = 0 THEN [rope["-"]] ELSE Realn[(quadMisses/rMisses)*100, 3]];
IF private.stats.jumpMisses # 0 THEN stream.PutF[
"  misses caused by jumps: %g (%g%% of probes)\n",
[integer[private.stats.jumpMisses]], Realn[(private.stats.jumpMisses/rProbes)*100, 3]];
IF probes # 0 THEN stream.PutF[
"  miss rate: %g%%\n",
Realn[(misses/rProbes)*100, 3]];
stream.PutF[
"  map misses: %g\n  dirty writes: %g\n",
[integer[private.stats.mapMisses]], [integer[private.stats.dirtyWrites]]];
};

Fetch: CacheModels.CacheFetchProc -- [cache: CacheModels.Cache, addr: DragOpsCross.Word, fromJump: BOOL _ FALSE] --  = {
Access[cache, addr, fromJump, FALSE];
};

Store: CacheModels.CacheStoreProc -- [cache: CacheModels.Cache, addr: DragOpsCross.Word] --  = {
Access[cache, addr, FALSE, TRUE];
};

Method: TYPE = {advanceOnMiss, shiftOnHit};
method: Method _ advanceOnMiss;

Access: PROC [cache: Cache, addr: Word, fromJump, write: BOOL] = {
directMapped: BOOL = FALSE;
data: CacheData = NARROW[cache.private];
oldEntry: BOOL _ TRUE;
victim: CARDINAL _ data.victimIndex;
wordsPerLine: NAT = data.quadsPerLine * wordsPerQuad;
indexInLine: NAT = HalfToCard[LowHalf[addr]] MOD wordsPerLine;
chunk: QuadIndex = Basics.BITSHIFT[indexInLine, -logWordsPerQuad];
lineAddr: Word = AddDelta[addr, -INT[indexInLine]];
hashIndex: CARDINAL;
hashEntry: HashEntry;
halfHash: Half _ HalfXor[WordToHalves[lineAddr][0], WordToHalves[lineAddr][1]];
data.stats.probes _ data.stats.probes + 1;
IF write THEN data.stats.writeProbes _ data.stats.writeProbes + 1 ELSE data.stats.readProbes _ data.stats.readProbes + 1;
IF directMapped THEN {
hashIndex _ (HalfToCard[LowHalf[lineAddr]] / wordsPerQuad) MOD data.linesInCache;
hashEntry _ data.lineTable[hashIndex];
IF hashEntry.lineAddr # lineAddr THEN {
IF fromJump THEN data.stats.jumpMisses _ data.stats.jumpMisses + 1;
data.stats.lineMisses _ data.stats.lineMisses + 1;
IF write THEN data.stats.writeMisses _ data.stats.writeMisses + 1;
IF hashEntry.dirty # None THEN {
FOR i: NAT IN [0..data.quadsPerLine) DO
IF hashEntry.dirty[i] THEN {
data.realCache.store[data.realCache, AddDelta[hashEntry.lineAddr, i]];
data.stats.dirtyWrites _ data.stats.dirtyWrites + 1;
};
ENDLOOP;
hashEntry.dirty _ None;
};
data.realCache.fetch[data.realCache, addr];
hashEntry.lineAddr _ lineAddr;
};
IF write THEN {
IF NOT hashEntry.dirty[chunk] THEN data.stats.writeClean _ data.stats.writeClean + 1;
hashEntry.dirty[chunk] _ TRUE;
};
RETURN;
};
halfHash _ HalfXor[halfHash, HalfShift[halfHash, -8]];
hashIndex _ HalfToCard[halfHash] MOD HashLim;
hashEntry _ data.hashVector[hashIndex];
WHILE hashEntry # NIL DO	
IF hashEntry.lineAddr = lineAddr THEN {
IF data.lru THEN hashEntry.referenced[chunk] _ TRUE;
IF write THEN {
IF NOT hashEntry.dirty[chunk] THEN data.stats.writeClean _ data.stats.writeClean + 1;
hashEntry.dirty[chunk] _ TRUE;
};
IF hashEntry.index = victim AND method = shiftOnHit THEN {
victim _ victim + 1;
data.victimIndex _ IF victim = data.linesInCache THEN 0 ELSE victim;
};
IF ~hashEntry.chunkPresent[chunk] THEN {
data.realCache.fetch[data.realCache, addr];
IF write THEN data.stats.writeMisses _ data.stats.writeMisses + 1;
IF fromJump THEN data.stats.jumpMisses _ data.stats.jumpMisses + 1;
data.stats.chunkMisses _ data.stats.chunkMisses + 1;
hashEntry.chunkPresent[chunk] _  TRUE};
RETURN;
};
hashEntry _ hashEntry.next;
ENDLOOP;
IF fromJump THEN data.stats.jumpMisses _ data.stats.jumpMisses + 1;
data.stats.lineMisses _ data.stats.lineMisses + 1;
IF write THEN data.stats.writeMisses _ data.stats.writeMisses + 1;
hashEntry _ data.lineTable[victim];

{
lag: PageEntry _ NIL;
oldLineAddr: Word = hashEntry.lineAddr;
oldIndexInPage: CARDINAL = HalfToCard[LowHalf[oldLineAddr]] MOD wordsPerPage;
oldPageAddr: Word = AddDelta[oldLineAddr, -INT[oldIndexInPage]];
headHashEntry: HashEntry;
oldHashIndex: CARDINAL;
oldHalfHash: Half _ HalfXor[
WordToHalves[oldLineAddr][0], WordToHalves[oldLineAddr][1]];
oldHalfHash _ HalfXor[oldHalfHash, HalfShift[oldHalfHash, -8]];
oldHashIndex _ HalfToCard[oldHalfHash] MOD HashLim;
headHashEntry _ data.hashVector[oldHashIndex];

IF headHashEntry = hashEntry
THEN data.hashVector[oldHashIndex] _ hashEntry.next
ELSE WHILE headHashEntry # NIL DO
IF hashEntry = headHashEntry.next THEN {
headHashEntry.next _ hashEntry.next;
EXIT};
headHashEntry _ headHashEntry.next
ENDLOOP;

FOR pageEntry: PageEntry _ data.pageList, pageEntry.next WHILE pageEntry # NIL DO
IF pageEntry.pageAddr = oldPageAddr THEN {
IF (pageEntry.useCount _ pageEntry.useCount - 1) <= 0 THEN {
IF lag = NIL THEN data.pageList _ pageEntry.next ELSE lag.next _ pageEntry.next;
data.pageEntryCount _ data.pageEntryCount - 1;
pageEntry.next _ data.freePageList;
data.freePageList _ pageEntry;
};
EXIT
};
lag _ pageEntry;
ENDLOOP;

IF hashEntry.dirty # None THEN {
FOR i: NAT IN [0..data.quadsPerLine) DO
IF hashEntry.dirty[i] THEN {
data.realCache.store[data.realCache, AddDelta[oldLineAddr, i]];
data.stats.dirtyWrites _ data.stats.dirtyWrites + 1;
};
ENDLOOP;
hashEntry.dirty _ None;
};
};

{
indexInPage: CARDINAL = HalfToCard[LowHalf[lineAddr]] MOD wordsPerPage;
pageAddr: Word = AddDelta[lineAddr, -INT[indexInPage]];
pageEntry: PageEntry _ data.pageList;

hashEntry.next _ data.hashVector[hashIndex];
data.hashVector[hashIndex] _ hashEntry;
hashEntry.lineAddr _ lineAddr;
hashEntry.chunkPresent _ None; hashEntry.chunkPresent[chunk] _ TRUE;

data.realCache.fetch[data.realCache, addr];
WHILE pageEntry # NIL DO
IF pageEntry.pageAddr = pageAddr THEN {
pageEntry.useCount _ pageEntry.useCount + 1;
GO TO oldEntry;
};
pageEntry _ pageEntry.next;
ENDLOOP;
data.pageEntryCount _ data.pageEntryCount + 1;
data.stats.mapMisses _ data.stats.mapMisses + 1;
pageEntry _ data.freePageList;
IF pageEntry = NIL
THEN pageEntry _ NEW[PageEntryRep]
ELSE data.freePageList _ pageEntry.next; 
pageEntry^ _ [next: data.pageList, pageAddr: pageAddr, useCount: 1];
data.pageList _ pageEntry;

EXITS oldEntry => NULL;
};

IF write THEN {
IF NOT hashEntry.dirty[chunk] THEN data.stats.writeClean _ data.stats.writeClean + 1;
hashEntry.dirty[chunk] _ TRUE;
};

victim _ victim + 1;
data.victimIndex _ IF victim = data.linesInCache THEN 0 ELSE victim;
};

END.

ΊStandardCache.mesa
Copyright c 1985 by Xerox Corporation.  All rights reversed.
Bertrand Serlet, April 11, 1985 5:24:49 pm PST, stolen from CacheModelImpl.mesa
Last Edited by: Serlet, April 12, 1985 2:39:09 pm PST
Last Edited by: Barth, April 16, 1985 3:58:10 pm PST
Private types
Creates a new cache on the specified shared memory.
Resets the given cache to its initial state (all empty).
Resets the given cache to its initial state (all empty).
We make the victim index point at the next cache entry
The victim must be removed from the hash table and page table.
Maintain the hash table by removing the victim from the table.  We must be prepared for the entry to not be in the hash table at all if the entry is brand new.
Now we need to maintain the page table.  We must be prepared for the entry to not be in the hash table at all if the entry is brand new.
Decrement the use count for this page (if an entry already exists)
Remove this page entry from the list and put it on the free page list.
At this point we need to read in the quad word from the memory.
Maintain the hash table
Increment the use count for this page (if an entry already exists).  Then return.
This entry is brand new, so add it to the list and bump the reject cycles to show that we got a map miss.  Note that at this point pageEntry = NIL.
At this point we have to advance the victim pointer, since in either method this newly retrieved entry clearly should not be the new victim.
Κ
œ˜š
œ™Jšœ
Οm
œ1™<Jš
œO™OJš
œ5™5Jš
œ4™4—J˜š
Οk	˜	Jšœžœžœ˜Jš
œ˜J˜Jšœ
žœ˜+JšœžœC˜ZJšžœ˜	J˜—šΟb
œžœ
ž˜Jšžœ%žœ	˜7J˜Jšžœ
žœ!˜+J˜š
œ
™
J˜Jšœžœ˜ J˜Jšœžœ˜Jšœžœ˜Jšœžœ˜Jšœžœ˜2Jšœžœ˜(J˜Jšœžœžœ˜#šœžœžœ˜Jšœžœ
˜J˜Jšœ
žœ˜J˜J˜—š
œžœ
žœžœ
žœžœ
žœ˜2J˜—Jšœžœžœ˜#šœžœžœ˜Jšœžœ
˜J˜Jšœžœ˜
Jš	œžœ
žœžœ
žœ˜4Jš	œžœ
žœžœ
žœ˜-Jš	œžœ
žœžœ
žœ˜1J˜J˜—Jšœžœžœ˜#šœžœžœ˜Jš
œ˜Jšœžœ
˜Jšœžœ˜Jšœžœ
˜Jšœžœ
˜Jšœ
žœ˜Jšœžœžœ
˜Jšœžœ˜Jšœžœ˜Jšœžœ
˜#Jšœžœžœ
žœ
˜2J˜—J˜šœžœžœ˜Jšœžœ˜Jšœžœ˜Jšœ
žœ˜Jšœ
žœ˜Jšœžœ˜Jšœ
žœ˜Jšœžœ˜Jšœžœ˜Jšœžœ˜Jšœ
žœ˜J˜—J˜Jšœ	žœ˜Jšœžœžœ˜%Jšœžœžœžœ˜6—J˜šΟnœžœ
žœ9žœžœ žœ˜ 
Jš
œ3™3šœžœ˜$Jšœ	žœ_žœ˜rJš
œF˜FJšœžœ˜—Jš
œ
˜
J˜—J˜•StartOfExpansion" -- [cache: CacheModels.Cache] -- š œ
ž
œΠck!œ˜GJš
œ8™8Jšœžœ˜+Jšœžœ
˜Jšœžœžœ
žœ˜3Jš
œ˜J˜šžœžœ
žœž˜*Jšœ
žœ˜,Jšžœ
˜—JšœΟc˜*Jš
œ+˜+J˜J˜—–" -- [cache: CacheModels.Cache] -- š œ
ž
œ‘!œ˜GJš
œ8™8Jšœžœ˜+Jšœžœ
˜Jšœžœ
žœ˜Jš
œ˜J˜šžœžœ
žœž˜*Jš
œ˜Jšžœ
˜—Jš
œ+˜+J˜—J˜
code–\ -- [cache: CacheModels.Cache, stream: STREAM, name: ROPE, resetStatistics: BOOL _ TRUE] -- š œ‘\œ˜
š œžœžœžœžœžœ˜4Kšžœ'˜-—Kšœžœ˜+Kšœžœ˜,Kšœžœ)˜4Kšœžœ˜#Kšœ	žœ
˜Kšœ	žœ
˜š
œ˜K˜=Kšœžœ
žœ!žœ	˜GKš
œU˜U—Kšžœžœ
žœ
˜š
œ˜K˜&Kš
œK˜K—š
œ˜K˜0Kš
œK˜K—š
œ˜K˜+Kš
œ9˜9Kšžœžœ
žœ%˜H—šžœžœ
˜1Kš
œ2˜2Kš
œW˜W—šžœžœ
˜K˜Kš
œ ˜ —š
œ˜Kš
œ)˜)Kš
œJ˜J—K˜K˜—–S -- [cache: CacheModels.Cache, addr: DragOpsCross.Word, fromJump: BOOL _ FALSE] -- šŸœ‘Rœ˜xJšœžœ˜%J˜J˜—–; -- [cache: CacheModels.Cache, addr: DragOpsCross.Word] -- šŸœ‘:œ˜`Jšœžœ˜!J˜J˜—Jšœžœ˜+š
œ˜J˜—š œžœ-žœ˜BJšœžœžœ
˜Jšœžœ˜(Jšœ
žœžœ
˜Jšœžœ˜$Jšœžœ$˜5Jšœ
žœžœ˜>Jšœžœ ˜BJšœ!žœ˜3Jšœžœ
˜Jš
œ˜Jš
œO˜OJš
œ*˜*Jšžœžœ5žœ3˜yšžœžœ˜Jšœ;žœ˜QJš
œ&˜&šžœžœ˜'Jšžœ
žœ3˜CJš
œ2˜2Jšžœžœ5˜Bšžœžœ˜ šžœžœ
žœž˜'šžœžœ˜Jš
œF˜FJš
œ4˜4J˜—Jšžœ
˜—Jš
œ˜J˜—J˜+Jš
œ˜J˜—šžœžœ˜Jšžœ
žœžœ3˜UJšœžœ
˜J˜—Jšžœ
˜Jš
œ˜—Jš
œ6˜6Jšœ!žœ	˜-Jš
œ'˜'šžœ
žœ
žœ
˜šžœžœ˜'Jšžœ
žœžœ
˜4šžœžœ˜Jšžœ
žœžœ3˜UJšœžœ
˜J˜—šžœžœžœ˜:Jš
œ6™6Jš
œ˜Jšœžœžœžœ˜DJ˜—šžœ žœ˜(J˜+Jšžœžœ5˜BJšžœ
žœ3˜CJš
œ4˜4Jšœ!žœ˜'—Jšžœ
˜J˜—Jš
œ˜Jšžœ
˜—Jšžœ
žœ3˜CJš
œ2˜2Jšžœžœ5˜BJš
œ#˜#J˜š
œ
˜
J™>Jšœžœ
˜Jš
œ'˜'Jšœžœ$žœ˜MJšœ+žœ˜@Jš
œ˜Jšœžœ
˜š
œ˜Jš
œ<˜<—Jš
œ?˜?Jšœ'žœ	˜3Jš
œ.˜.J˜Jš
œŸ
™Ÿ
šžœ˜Jšžœ/˜3šžœ
žœžœ
ž˜!šžœ žœ˜(Jš
œ$˜$Jšžœ˜—Jš
œ"˜"Jšžœ
˜——J˜Jš
œˆ
™ˆ
šžœ6žœ
žœ
ž˜Qšžœ"žœ˜*Jš
œB™Bšžœ4žœ˜<Jš
œF™FJšžœžœ
žœ žœ˜PJš
œ.˜.Jš
œ#˜#Jš
œ˜J˜—Jš
ž˜Jš
œ˜—J˜Jšžœ
˜—J˜šžœžœ˜ šžœžœ
žœž˜'šžœžœ˜Jš
œ?˜?Jš
œ4˜4J˜—Jšžœ
˜—Jš
œ˜J˜—J˜—J˜Jš
œ?™?š
œ
˜
Jšœ
žœ!žœ˜GJšœ%žœ˜7Jš
œ%˜%J˜Jš
œ™Jš
œ,˜,Jš
œ'˜'Jš
œ˜Jšœ?žœ
˜DJ˜J˜+šžœ
žœ
ž˜šžœžœ˜'Jš
œQ™QJš
œ,˜,Jšžœ
žœ
˜Jš
œ˜—J˜Jšžœ
˜—Jšœ
žœ
™“
Jš
œ.˜.Jš
œ0˜0Jš
œ˜šžœ
ž˜Jšžœ
žœ˜"Jšžœ%˜)—Jš
œD˜DJš
œ˜J˜Jšžœ
žœ
˜J˜J˜—šžœžœ˜Jšžœ
žœžœ3˜UJšœžœ
˜J˜—J˜Jš
œŒ
™Œ
Jš
œ˜Jšœžœžœžœ˜D˜J˜——Jšžœ
˜—J˜—…—'ή;4