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 = { 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 = { 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. LizardCacheImpl.mesa Copyright c 1984, 1985, 1986 by Xerox Corporation. All rights reserved. Russ Atkinson (RRA) April 21, 1987 3:25:32 pm PDT Private types Cost (in reject cycles) for various operations; these are all estimates Creates a new cache on the specified sparse memory. Creates a new cache on the specified shared memory. Resets the given cache to its initial state (all empty). Makes the underlying memory agree with the current entry. No stats update. [base: CacheBase, addr: Word, cycle: INT, userMode: BOOL, noEffect: BOOL _ FALSE] RETURNS [data: Word, status: TrapIndex, rejectCycles: INT]; [base: CacheBase, addr: Word, data: Word, cycle: INT, userMode: BOOL] RETURNS [old: Word, status: TrapIndex, rejectCycles: INT]; We make the victim index point at the next cache entry Allow for bus to become available. Note that we should NOT bump busyUntil, since we are really just trying to get the cycle counter up to busyUntil. Just in case things get weird 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. The victim is dirty, so we need to write it back to its home page. 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. Finally, show that the bus is tied up until the read is finished. 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. Κ =˜codešœ™Kšœ Οmœ=™HK™1—˜šΟk ˜ Kšœ žœ?˜QKšœžœO˜fKšœ žœV˜gKšœ žœ˜+K˜——šΟnœžœž˜Kšžœ ˜'Kšžœ ˜Kšœžœžœ.˜:—K˜šœ ™ K˜Kšœ žœžœ˜#šœžœžœ˜Kšœžœ˜K˜Kšœ žœ˜Kšœ žœž˜K˜K˜—Kšœ žœžœ˜#šœžœžœ˜Kšœžœ˜K˜Kšœžœžœžœ ˜8Kšœžœ˜Kšœžœž˜%K˜K˜—Kšœ žœžœ˜#šœžœžœ˜Kšœžœ˜Kšœžœ˜Kšœžœ˜Kšœžœ˜Kšœ žœ˜Kšœ žœžœžœ ˜2K˜K˜—Kšœ žœžœ˜%Kšœžœžœžœ ˜6Kšœ žœ˜K˜Kšœ.˜.Kšœžœ˜Kšœžœ˜3K˜šœG™GKšœžœ˜šœžœ˜Kšœžœ˜—Kšœžœ˜Kšœžœ˜K˜——šŸœžœžœžœ˜FKšœ3™3Kšžœžœ˜'K˜K™—šŸœžœžœ,žœ˜XKšœ3™3Kš œžœžœžœžœ˜RKš œžœžœ žœžœ ˜HKšœ˜Kšœ˜Kšœ˜Kšžœ˜K˜—K˜šŸ œžœžœ˜.Kšœ8™8Kšœžœ˜+Kšœžœ˜Kšœžœžœžœ˜3Kšœ˜K˜Kšœ˜šžœžœžœž˜*Kšœ žœ˜,Kšžœ˜—Kšœ˜K˜K˜—šŸ œžœžœ˜.KšœK™KKšœžœ˜(šžœžœžœž˜'Kšœ˜šžœ žœ˜Kšœ.˜.KšœE˜EKšœ žœ&žœ˜Lšžœžœž˜0Kšœ*˜*Kšžœ˜—K˜—Kšžœ˜—K˜K˜—šŸ œ˜Kš œ%žœ žœ žœžœ™QKšžœ/žœ™;Kšœ;žœ˜LKšœ˜Kšœ3žœ˜Sšžœ žœž˜Kšžœ%˜+—Kšžœ6˜Kšœžœ˜Kšœ'˜'Kšœžœ$žœ˜MKšœžœ˜@šžœ žœ˜Kšœ˜Kšœžœ˜šœ˜Kšœ<˜<—Kšœ?˜?Kšœ'žœ ˜3Kšœ.˜.K˜KšœŸ™Ÿšžœ˜Kšžœ/˜3šžœžœžœž˜!šžœ žœ˜(Kšœ$˜$Kšžœ˜—Kšœ"˜"Kšžœ˜——K˜Kšœˆ™ˆšžœ6žœ žœž˜Qšžœ"žœ˜*KšœB™Bšžœ4žœ˜