DIRECTORY DragOpsCross USING [Half, TrapIndex, Word, wordsPerPage, ZerosWord], DragOpsCrossUtils USING [AddDelta, HalfShift, HalfToCard, HalfXor, LowHalf, 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; }; 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, EUPageFault, 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, EUPageFault, rejectCycles]; old _ hashEntry.words[indexInLine]; IF hashEntry.readOnly THEN RETURN [old, EUWriteFault, 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] = { 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; }; 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. LLizardCacheImpl.mesa Copyright c 1984, 1985 by Xerox Corporation. All rights reserved. Russ Atkinson (RRA) October 11, 1985 3:24:00 pm PDT TrapIndex: TYPE = DragOpsCross.TrapIndex; Word: TYPE = DragOpsCross.Word; CacheBase: TYPE = REF CacheBaseRep; CacheBaseRep: TYPE = RECORD [ sharedBase: SharedBase _ NIL, -- shared base data private: REF _ NIL, -- private data to the cache implementation fetch: CacheFetchProc _ NIL, -- this hook allows the user to intercept cache accesses store: CacheStoreProc _ NIL, -- this hook allows the user to intercept cache accesses data: REF _ NIL, -- private data for clients intercepting fetch & store stats: CacheStats _ [] -- maintained by the default fetch and store routines ]; SharedBase: TYPE = REF SharedBaseRep; SharedBaseRep: TYPE = RECORD [ mem: SparseMemory.Base _ NIL, busyUntil: INT _ 0 ]; CacheFetchProc: TYPE = PROC [base: CacheBase, addr: Word, cycle: INT, noEffect: BOOL _ FALSE] RETURNS [data: Word, status: TrapIndex, rejectCycles: INT]; This is the type of routine that is used to fetch words from the cache. If noEffect, then no change will be made to the cache state or statistics (useful for dumping memory). CacheStoreProc: TYPE = PROC [base: CacheBase, addr: Word, data: Word, cycle: INT] RETURNS [status: TrapIndex, rejectCycles: INT]; This is the type of routine that is used to store words into the cache. The old word is returned to facilitate memory tracing. CacheStats: TYPE = RECORD [ probes: INT _ 0, misses: INT _ 0, dirtyWrites: INT _ 0, rejectCycles: INT _ 0 ]; 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, noEffect: BOOL _ FALSE] RETURNS [data: Word, status: TrapIndex, rejectCycles: INT]; [base: CacheBase, addr: Word, data: Word, cycle: INT] 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. 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œ7™BK™3—K˜šΟk ˜ Kšœ žœ2˜DKšœžœC˜ZKšœ žœV˜gKšœ žœ˜+K˜—šœžœž˜Kšžœ ˜'Kšžœ ˜Kšœžœžœ.˜:—K˜Kšœ žœ™)Kšœžœ™K™Kšœ žœžœ™#–36 sp tabStopsšœžœžœ™K–36 sp tabStopsšœžœΟc™1K–36 sp tabStopsšœ žœžœŸ+™?K–36 sp tabStopsšœžœŸ8™UK–36 sp tabStopsšœžœŸ8™UK–36 sp tabStopsšœžœžœŸ6™GK–36 sp tabStopsšœŸ5™LK–36 sp tabStops™K–36 sp tabStops™—Kšœ žœžœ™%šœžœžœ™Kšœžœ™Kšœ žœ™K™K™—šΟnœžœž™Kšœ%žœ žœžœ™AKšžœ/žœ™;Kšœ―™―K™—š œžœž™Kšœ1žœ™5Kšžœ#žœ™/Kšœ™K™—šœ žœžœ™Kšœžœ™Kšœžœ™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™KKšœžœ˜(šžœžœžœž˜'Kšœ˜šžœ žœ˜Kšœ.˜.KšœE˜EKšœ žœ&žœ˜Lšžœžœž˜0Kšœ*˜*Kšžœ˜—K˜—Kšžœ˜—K˜K˜—šœ˜Kšœ%žœ žœžœ™AKšžœ/žœ™;Kšœ;žœ˜LKšœ˜Kšœ3žœ˜SKšžœ žœžœžœ(˜FKšžœ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žœ˜