<> <> <> <> DIRECTORY Basics USING [BITSHIFT], DragOpsCross USING [Half, Word, ZerosWord], DragOpsCrossUtils USING [AddDelta, HalfShift, HalfToCard, HalfXor, LowHalf, WordToHalves], CacheModel USING [CacheBase, CacheBaseRep, CacheFetchProc, CacheStoreProc, wordsPerPage]; CacheModelImpl: CEDAR PROGRAM IMPORTS Basics, DragOpsCrossUtils EXPORTS CacheModel = BEGIN OPEN DragOpsCross, DragOpsCrossUtils, CacheModel; <> <<>> <> <> <> <> <> <> <> <> <<];>> <<>> <> <> <> <> <<];>> <<>> <> <> <<>> <> <> <<>> <> <> <> <> <> <> <<];>> <> wordsPerQuad: NAT = 4; logWordsPerQuad: NAT = 2; maxQuadsPerLine: NAT = 8; wordsPerPage: CARDINAL = CacheModel.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 [ hashVector: HashVector _ NIL, pageEntryCount: INT _ 0, pageList: PageEntry _ NIL, freePageList: PageEntry _ NIL, victimIndex: CARDINAL _ 0, lru: BOOL _ FALSE, rover: NAT _ 0, quadsPerLine: NAT _ 2, lineTable: SEQUENCE linesInCache: NAT OF HashEntry ]; HashLim: CARDINAL = 512; HashVector: TYPE = REF HashVectorRep; HashVectorRep: TYPE = ARRAY [0..HashLim) OF HashEntry; NewCache: PUBLIC PROC [lines: [0..4096), quadsPerLine: [0..8), lru: BOOL _ FALSE] RETURNS [CacheBase] = { <> base: CacheBase _ NEW[CacheBaseRep _ [NIL, LocalFetch, LocalStore, NIL, []]]; private: CacheData _ NEW[CacheDataRep[lines] _ [quadsPerLine: quadsPerLine, lru: lru, lineTable: NULL]]; base.private _ private; ResetCache[base]; RETURN [base]; }; ResetCache: PUBLIC PROC [cache: CacheBase] = { <> 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; cache.stats _ []; -- zero out statistics }; FlushCache: PUBLIC PROC [cache: CacheBase] = { <> 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; }; LocalFetch: CacheFetchProc = { <<[base: CacheBase, addr: Word];>> private: CacheData = NARROW[base.private]; wordsPerLine: NAT = private.quadsPerLine * wordsPerQuad; indexInLine: NAT = HalfToCard[LowHalf[addr]] MOD wordsPerLine; chunk: QuadIndex = Basics.BITSHIFT[indexInLine, -logWordsPerQuad]; entry: HashEntry _ Access[base, AddDelta[addr, -INT[indexInLine]], chunk, fromJump]; entry _ entry; -- to have a place to set a breakpoint }; LocalStore: CacheStoreProc = { <<[base: CacheBase, addr: Word];>> private: CacheData = NARROW[base.private]; wordsPerLine: NAT = private.quadsPerLine * wordsPerQuad; indexInLine: NAT = HalfToCard[LowHalf[addr]] MOD wordsPerLine; chunk: QuadIndex = Basics.BITSHIFT[indexInLine, -logWordsPerQuad]; hashEntry: HashEntry; hashEntry _ Access[base, AddDelta[addr, -INT[indexInLine]], chunk, FALSE]; hashEntry.dirty[chunk] _ TRUE; }; Method: TYPE = {advanceOnMiss, shiftOnHit}; method: Method _ shiftOnHit; Access: PROC [cache: CacheBase, lineAddr: Word, chunk: QuadIndex, fromJump: BOOL] RETURNS [hashEntry: HashEntry] = { data: CacheData = NARROW[cache.private]; oldEntry: BOOL _ TRUE; victim: CARDINAL _ data.victimIndex; hashIndex: CARDINAL; halfHash: Half _ HalfXor[WordToHalves[lineAddr][0], WordToHalves[lineAddr][1]]; halfHash _ HalfXor[halfHash, HalfShift[halfHash, -8]]; hashIndex _ HalfToCard[halfHash] MOD HashLim; hashEntry _ data.hashVector[hashIndex]; cache.stats.probes _ cache.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 { <> victim _ victim + 1; data.victimIndex _ IF victim = data.linesInCache THEN 0 ELSE victim; }; IF ~hashEntry.chunkPresent[chunk] THEN { IF fromJump THEN cache.stats.jumpMisses _ cache.stats.jumpMisses + 1; cache.stats.chunkMisses _ cache.stats.chunkMisses + 1; hashEntry.chunkPresent[chunk] _ TRUE}; RETURN; }; hashEntry _ hashEntry.next; ENDLOOP; IF fromJump THEN cache.stats.jumpMisses _ cache.stats.jumpMisses + 1; cache.stats.lineMisses _ cache.stats.lineMisses + 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 cache.stats.dirtyWrites _ cache.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; 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; cache.stats.mapMisses _ cache.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; }; <> victim _ victim + 1; data.victimIndex _ IF victim = data.linesInCache THEN 0 ELSE victim; }; END.