StandardCache.mesa
Copyright © 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 15, 1985 4:59:03 pm PST
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;
Private types
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,
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] = {
Creates a new cache on the specified shared memory.
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] -- = {
Resets the given cache to its initial state (all empty).
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] -- = {
Resets the given cache to its initial state (all empty).
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[
" 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[
" hit rate: %g%%\n",
Realn[((probes - 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] = {
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]];
halfHash ← HalfXor[halfHash, HalfShift[halfHash, -8]];
hashIndex ← HalfToCard[halfHash] MOD HashLim;
hashEntry ← data.hashVector[hashIndex];
data.stats.probes ← data.stats.probes + 1;
WHILE hashEntry # NIL DO 
IF hashEntry.lineAddr = lineAddr THEN {
IF data.lru THEN hashEntry.referenced[chunk] ← TRUE;
IF hashEntry.index = victim AND method = shiftOnHit THEN {
We make the victim index point at the next cache entry
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 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;
hashEntry ← data.lineTable[victim];
{
The victim must be removed from the hash table and page table.
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];
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.
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;
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.
FOR pageEntry: PageEntry ← data.pageList, pageEntry.next WHILE pageEntry # NIL DO
IF pageEntry.pageAddr = oldPageAddr THEN {
Decrement the use count for this page (if an entry already exists)
IF (pageEntry.useCount ← pageEntry.useCount - 1) <= 0 THEN {
Remove this page entry from the list and put it on the free page list.
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;
};
};
At this point we need to read in the quad word from the memory.
{
indexInPage: CARDINAL = HalfToCard[LowHalf[lineAddr]] MOD wordsPerPage;
pageAddr: Word = AddDelta[lineAddr, -INT[indexInPage]];
pageEntry: PageEntry ← data.pageList;
Maintain the hash table
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 {
Increment the use count for this page (if an entry already exists). Then return.
pageEntry.useCount ← pageEntry.useCount + 1;
GO TO oldEntry;
};
pageEntry ← pageEntry.next;
ENDLOOP;
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.
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 hashEntry.dirty[chunk] ← TRUE;
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.
victim ← victim + 1;
data.victimIndex ← IF victim = data.linesInCache THEN 0 ELSE victim;
};
END.