<> <> <> DIRECTORY DragOpsCross USING [Half, KernalLimit, TrapIndex, Word, wordsPerPage, ZerosWord], DragOpsCrossUtils USING [AddDelta, HalfShift, HalfToCard, HalfXor, LowHalf, WordToCard, WordToHalves], LizardCache USING [CacheBase, CacheBaseRep, CacheFetchProc, CacheStoreProc, SharedBase, SharedBaseRep], SparseMemory USING [Base, FetchPage, Page]; LizardCacheImpl: CEDAR PROGRAM IMPORTS DragOpsCrossUtils, SparseMemory EXPORTS LizardCache = BEGIN OPEN DragOpsCross, DragOpsCrossUtils, LizardCache; <> PageEntry: TYPE = REF PageEntryRep; PageEntryRep: TYPE = RECORD [ next: PageEntry _ NIL, pageAddr: Word _ ZerosWord, useCount: INT _ 0, readOnly: BOOL _ FALSE ]; HashEntry: TYPE = REF HashEntryRep; HashEntryRep: TYPE = RECORD [ next: HashEntry _ NIL, lineAddr: Word _ ZerosWord, words: ARRAY [0..wordsPerLine) OF Word _ ALL[ZerosWord], index: NAT _ 0, dirty, readOnly, shared: BOOL _ FALSE ]; CacheData: TYPE = REF CacheDataRep; CacheDataRep: TYPE = RECORD [ hashVector: HashVector _ NIL, pageEntryCount: INT _ 0, pageList: PageEntry _ NIL, freePageList: PageEntry _ NIL, victimIndex: CARDINAL _ 0, lineTable: SEQUENCE linesInCache: NAT OF HashEntry ]; HashVector: TYPE = REF HashVectorRep; HashVectorRep: TYPE = ARRAY [0..HashLim) OF HashEntry; HashLim: CARDINAL = 512; NoTrap: DragOpsCross.TrapIndex = ALUCondFalse; wordsPerLine: NAT = 4; wordsPerPage: CARDINAL = DragOpsCross.wordsPerPage; <> cyclesToArbitrate: NAT _ 3; cyclesToReadFirst: NAT _ 4; cyclesToReadRest: NAT _ 3; cyclesToWriteQuad: NAT _ 6; cyclesToReadMap: NAT _ 4; NewBase: PUBLIC PROC [mem: SparseMemory.Base] RETURNS [SharedBase] = { <> RETURN [NEW[SharedBaseRep _ [mem, 0]]]; }; <<>> NewCache: PUBLIC PROC [shared: SharedBase, lines: [0..4096) _ 0] RETURNS [CacheBase] = { <> base: CacheBase _ NEW[CacheBaseRep _ [NIL, NIL, LocalFetch, LocalStore, NIL, []]]; private: CacheData _ NEW[CacheDataRep[IF lines = 0 THEN 64 ELSE lines]]; base.private _ private; base.sharedBase _ shared; 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; cache.sharedBase.busyUntil _ 0; FOR i: NAT IN [0..private.linesInCache) DO private[i] _ NEW[HashEntryRep _ [index: i]]; ENDLOOP; cache.stats _ []; }; FlushCache: PUBLIC PROC [cache: CacheBase] = { <> data: CacheData = NARROW[cache.private]; FOR i: NAT IN [0..data.linesInCache) DO line: HashEntry = data[i]; IF line.dirty THEN { mem: SparseMemory.Base = cache.sharedBase.mem; page: SparseMemory.Page = SparseMemory.FetchPage[mem, line.lineAddr]; indexInPage: CARDINAL = HalfToCard[LowHalf[line.lineAddr]] MOD wordsPerPage; FOR i: [0..wordsPerLine) IN [0..wordsPerLine) DO page.words[indexInPage+i] _ line.words[i]; ENDLOOP; }; ENDLOOP; }; LocalFetch: CacheFetchProc = { <<[base: CacheBase, addr: Word, cycle: INT, userMode: BOOL, noEffect: BOOL _ FALSE]>> <> indexInLine: [0..wordsPerLine) = HalfToCard[LowHalf[addr]] MOD wordsPerLine; hashEntry: HashEntry; [hashEntry, rejectCycles] _ Access[base, AddDelta[-INT[indexInLine], addr], cycle]; IF hashEntry = NIL THEN RETURN [ZerosWord, MapFault, rejectCycles]; RETURN [hashEntry.words[indexInLine], NoTrap, rejectCycles]; }; LocalStore: CacheStoreProc = { <<[base: CacheBase, addr: Word, data: Word, cycle: INT, userMode: BOOL]>> <> indexInLine: [0..wordsPerLine) = HalfToCard[LowHalf[addr]] MOD wordsPerLine; hashEntry: HashEntry; [hashEntry, rejectCycles] _ Access[base, AddDelta[-INT[indexInLine], addr], cycle]; IF hashEntry = NIL THEN RETURN [ZerosWord, MapFault, rejectCycles]; IF userMode AND WordToCard[addr] < KernalLimit THEN RETURN [ZerosWord, MemAccessFault, rejectCycles]; old _ hashEntry.words[indexInLine]; IF hashEntry.readOnly THEN RETURN [old, MemAccessFault, rejectCycles]; hashEntry.words[indexInLine] _ data; hashEntry.dirty _ TRUE; status _ NoTrap; }; Method: TYPE = {advanceOnMiss, shiftOnHit}; method: Method _ shiftOnHit; Access: PROC [cache: CacheBase, lineAddr: Word, cycles: INT] RETURNS [hashEntry: HashEntry, rejectCycles: INT _ 0] = { BumpReject: PROC [n: CARDINAL] = INLINE { rejectCycles _ rejectCycles + n; busyUntil _ busyUntil + n; cache.sharedBase.busyUntil _ busyUntil; }; data: CacheData = NARROW[cache.private]; oldEntry: BOOL _ TRUE; victim: CARDINAL _ data.victimIndex; busyUntil: INT; 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 hashEntry.index = victim AND method = shiftOnHit THEN { <> victim _ victim + 1; data.victimIndex _ IF victim = data.linesInCache THEN 0 ELSE victim; }; RETURN; }; hashEntry _ hashEntry.next; ENDLOOP; busyUntil _ cache.sharedBase.busyUntil; cache.stats.misses _ cache.stats.misses + 1; hashEntry _ data.lineTable[victim]; IF busyUntil > cycles THEN { <> rejectCycles _ busyUntil - cycles; IF rejectCycles > 10000 THEN rejectCycles _ 10000; <> }; BumpReject[cyclesToArbitrate]; -- allow for bus arbitration cost { <> lag: PageEntry _ NIL; oldLineAddr: Word = hashEntry.lineAddr; oldIndexInPage: CARDINAL = HalfToCard[LowHalf[oldLineAddr]] MOD wordsPerPage; oldPageAddr: Word = AddDelta[-INT[oldIndexInPage], oldLineAddr]; IF oldEntry THEN { 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 THEN { <> mem: SparseMemory.Base = cache.sharedBase.mem; oldPage: SparseMemory.Page = SparseMemory.FetchPage[mem, oldPageAddr]; cache.stats.dirtyWrites _ cache.stats.dirtyWrites + 1; FOR i: [0..wordsPerLine) IN [0..wordsPerLine) DO oldPage.words[oldIndexInPage+i] _ hashEntry.words[i]; ENDLOOP; BumpReject[cyclesToWriteQuad]; hashEntry.dirty _ FALSE; }; }; <> { indexInPage: CARDINAL = HalfToCard[LowHalf[lineAddr]] MOD wordsPerPage; pageAddr: Word = AddDelta[-INT[indexInPage], lineAddr]; mem: SparseMemory.Base = cache.sharedBase.mem; page: SparseMemory.Page = SparseMemory.FetchPage[mem, lineAddr]; pageEntry: PageEntry _ data.pageList; IF page = NIL THEN RETURN [NIL, 3]; <> hashEntry.next _ data.hashVector[hashIndex]; data.hashVector[hashIndex] _ hashEntry; BumpReject[cyclesToReadFirst]; FOR i: [0..wordsPerLine) IN [0..wordsPerLine) DO hashEntry.words[i] _ page.words[indexInPage+i]; ENDLOOP; hashEntry.lineAddr _ lineAddr; 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, readOnly: FALSE]; data.pageList _ pageEntry; BumpReject[cyclesToReadMap]; EXITS oldEntry => {}; }; <> cache.sharedBase.busyUntil _ busyUntil + cyclesToReadRest; <> victim _ victim + 1; data.victimIndex _ IF victim = data.linesInCache THEN 0 ELSE victim; cache.stats.rejectCycles _ cache.stats.rejectCycles + rejectCycles; }; END.