<> <<.. functions for Dragon Cache Rosemary simulations. For now it assumes that there is only virtual memory. Mapping and map operations are not yet implemented.>> <> <> <> DIRECTORY Atom, Basics, CacheOps, Convert, Dragon, FS, IO, RefText, Rope; CacheOpsImpl: CEDAR PROGRAM IMPORTS Atom, Basics, Convert, FS, IO, RefText, Rope EXPORTS CacheOps = BEGIN OPEN CacheOps; VMPage: TYPE = RECORD [ vAddr: Dragon.Word, writeProtect, dirty: BOOL, data: ARRAY [0..PageSize) OF Dragon.Word ]; VMPageRef: TYPE = REF VMPage; VMOb: TYPE = RECORD [ firstFreeCycle: INT _ 0, caches: LIST OF CacheObRef _ NIL, pages: LIST OF VMPageRef _ NIL ]; VMObRef: TYPE = REF VMOb; CacheLine: TYPE = RECORD [ addr: Dragon.Word _ 0, dirty, sharedMaster, valid: BOOL _ FALSE ]; CacheOb: TYPE = RECORD [ vm: VMObRef _ NIL, accesses, writes, misses, pageMisses, dirtyVictimWrites, pageFaults: INT _ 0, victim: NAT _ 0, lastLineTransportAddress: Dragon.Word _ 0, firstCycleAfterLastLineTransport: INT _ 0, firstFreeCycle: INT _ 0, lines: SEQUENCE nLines: NAT OF CacheLine ]; CacheObRef: TYPE = REF CacheOb; GetVM: PROC [ mem: REF ANY _ NIL ] RETURNS [ vm: VMObRef ] = BEGIN vmra: REF ANY; IF defaultVM = NIL THEN BEGIN defaultVM _ NewVirtualMemory[]; VirtualMemoryFromFile[defaultVM, "Default.DragonVM"]; END; vmra _ defaultVM; IF mem#NIL THEN WITH mem SELECT FROM pl: Atom.PropList => vmra _ GetVM[Atom.GetPropFromList[propList: pl, prop: $DragonVM]]; lora: LIST OF REF ANY => FOR le: LIST OF REF ANY _ lora, le.rest WHILE le#NIL DO vmra _ GetVM[le.first]; IF vmra # defaultVM THEN EXIT; ENDLOOP; c: CacheObRef => vmra _ c.vm; vmor: VMObRef => vmra _ vmor; rope: Rope.ROPE => vmra _ NewVirtualMemoryFromFile[rope]; text: REF TEXT => vmra _ NewVirtualMemoryFromFile[Rope.FromRefText[text]]; ENDCASE => NULL; RETURN[NARROW[vmra]]; END; NewCache: PUBLIC PROC [ mem: REF ANY _ NIL, nLines: NAT _ StdLinesPerCache ] RETURNS [ c: Cache ] = BEGIN cor: CacheObRef _ NIL; IF mem = NIL THEN mem _ defaultVM; WITH mem SELECT FROM c: CacheObRef => cor _ c; ENDCASE => BEGIN vm: VMObRef = GetVM[mem]; cor _ NEW[CacheOb[nLines]]; cor.vm _ vm; vm.caches _ CONS[cor, vm.caches]; END; cor.accesses _ cor.writes _ cor.misses _ cor.pageMisses _ cor.dirtyVictimWrites _ cor.pageFaults _ 0; cor.firstCycleAfterLastLineTransport _ cor.firstFreeCycle _ 0; cor.victim _ 0; FOR i: NAT IN [0..cor.nLines) DO cor.lines[i] _ [] ENDLOOP; lastCache _ cor; cor.vm.firstFreeCycle _ 0; RETURN[cor]; END; TransportOrderAdvance: PROC [first, next: [0..WordsPerLine)] RETURNS [advance: [0..WordsPerLine]] = BEGIN advance _ (SELECT first FROM 0 => (SELECT next FROM 0 => 3, 1=> 2, 2=> 1, 3 => 0, ENDCASE => ERROR), 1 => (SELECT next FROM 0 => 2, 1=> 3, 2=> 0, 3 => 1, ENDCASE => ERROR), 2 => (SELECT next FROM 0 => 1, 1=> 0, 2=> 3, 3 => 2, ENDCASE => ERROR), 3 => (SELECT next FROM 0 => 0, 1=> 1, 2=> 2, 3 => 3, ENDCASE => ERROR), ENDCASE => ERROR); END; Access: PUBLIC PROC [ c: Cache, address: Dragon.Word, purpose: AccessPurpose _ read, cycleNow: INT _ 0 ] RETURNS [ data: Dragon.Word, rejectCycles: NAT, pageFault, writeProtect: BOOL ] = BEGIN cor: CacheObRef = NARROW[c]; page: VMPageRef = FindVMPage[vm: cor.vm, address: address, allowNIL: TRUE]; cycles: NAT; cor.accesses _ cor.accesses+1; FOR line: NAT IN [0..cor.nLines) DO IF address-cor.lines[line].addr IN [0..WordsPerLine) AND cor.lines[line].valid THEN BEGIN cycles _ IF (cor.lastLineTransportAddress/WordsPerLine) = (address/WordsPerLine) AND cor.firstCycleAfterLastLineTransport > cycleNow AND cycleNow > 0 THEN -- this line's transport may not yet be finished -- MAX[cor.firstCycleAfterLastLineTransport-TransportOrderAdvance[address MOD WordsPerLine, cor.lastLineTransportAddress MOD WordsPerLine]-cycleNow, 0] ELSE 0; EXIT; END; REPEAT FINISHED => -- not a cache hit, will result in MBus operation BEGIN addrPage: Dragon.Word = address - (address MOD PageSize); cycles _ 3; <> cor.misses _ cor.misses+1; IF cor.lines[cor.victim].dirty THEN BEGIN -- Clean the victim cycles _ cycles+5; -- Write quad cor.dirtyVictimWrites _ cor.dirtyVictimWrites+1; cor.lines[cor.victim].dirty _ FALSE; END; FOR line: NAT IN [0..cor.nLines) DO IF cor.lines[line].addr-addrPage IN [0..PageSize) AND cor.lines[line].valid THEN EXIT; REPEAT FINISHED => -- not a page hit either BEGIN cycles _ cycles+3; -- Map operation .. 2+? cor.pageMisses _ cor.pageMisses+1; IF page=NIL THEN BEGIN cor.pageFaults _ cor.pageFaults+1; RETURN[data: 0, rejectCycles: RejectCycles[cor, cycleNow, cycles-3 -- just dirty victim write (if any) followed by mapping -- ], pageFault: TRUE, writeProtect: FALSE]; END; END; ENDLOOP; cycles _ RejectCycles[cor, cycleNow, cycles+3]-3; <<.. allows additional 3 cycles for remaining 3 words of quadword>> cor.lastLineTransportAddress _ address; cor.firstCycleAfterLastLineTransport _ cor.firstFreeCycle; cor.lines[cor.victim] _ [addr: address - (address MOD WordsPerLine), valid: TRUE]; cor.victim _ (cor.victim+1) MOD cor.nLines; END; ENDLOOP; IF page=NIL THEN ERROR; -- cache and VM disagree RETURN[data: page.data[address-page.vAddr], rejectCycles: cycles, pageFault: FALSE, writeProtect: page.writeProtect]; END; Write: PUBLIC PROC [ c: Cache, address, data: Dragon.Word ] = BEGIN cor: CacheObRef = NARROW[c]; page: VMPageRef = FindVMPage[vm: cor.vm, address: address, allowNIL: TRUE]; IF page=NIL THEN ERROR; page.data[address-page.vAddr] _ data; page.dirty _ TRUE; cor.writes _ cor.writes+1; FOR line: NAT IN [0..cor.nLines) DO IF address-cor.lines[line].addr IN [0..WordsPerLine) THEN {cor.lines[line].dirty _ TRUE; EXIT}; REPEAT FINISHED => ERROR; ENDLOOP; END; IORead: PUBLIC PROC [ c: Cache, address: Dragon.Word, cycleNow: INT _ 0 ] RETURNS [ data: Dragon.Word, rejectCycles: NAT ] = {RETURN[0, RejectCycles[NARROW[c], cycleNow, 10]]}; IOWrite: PUBLIC PROC [ c: Cache, address, data: Dragon.Word, cycleNow: INT _ 0 ] RETURNS [ rejectCycles: NAT ] = {RETURN[RejectCycles[NARROW[c], cycleNow, 10]]}; SetFlags: PUBLIC PROC [ c: Cache, address: Dragon.Word, writeProtect, dirty, mapped: BOOL ] = BEGIN cor: CacheObRef = NARROW[c]; page: VMPageRef _ FindVMPage[vm: cor.vm, address: address, allowNIL: NOT mapped]; SELECT TRUE FROM mapped => BEGIN page.writeProtect _ writeProtect; page.dirty _ dirty; END; page#NIL => UnmapVMPage[vm: cor.vm, page: page]; ENDCASE => NULL; END; SetIntervalFlags: PUBLIC PROC [ c: Cache, startAddress, endAddress -- [startAddress..endAddress] -- : Dragon.Word, writeProtect, dirty, mapped: BOOL ] = BEGIN FOR addr: Dragon.Word _ startAddress, addr+PageSize WHILE addr<=endAddress DO SetFlags[c, addr, writeProtect, dirty, mapped]; ENDLOOP; END; GetFlags: PUBLIC PROC [ c: Cache, address: Dragon.Word] RETURNS [ writeProtect, dirty, mapped: BOOL ] = BEGIN cor: CacheObRef = NARROW[c]; page: VMPageRef _ FindVMPage[vm: cor.vm, address: address, allowNIL: TRUE]; IF page=NIL THEN RETURN[writeProtect: FALSE, dirty: FALSE, mapped: FALSE] ELSE RETURN[writeProtect: page.writeProtect, dirty: page.dirty, mapped: TRUE]; END; FindVMPage: PROC [ vm: VMObRef, address: Dragon.Word, allowNIL: BOOL _ FALSE ] RETURNS [ page: VMPageRef ] = BEGIN FOR p: LIST OF VMPageRef _ vm.pages, p.rest WHILE p#NIL DO IF address IN [p.first.vAddr..p.first.vAddr+PageSize) THEN RETURN[p.first]; ENDLOOP; IF NOT allowNIL THEN BEGIN vm.pages _ CONS[ first: NEW[VMPage _ [ vAddr: address - (address MOD PageSize), writeProtect: FALSE, dirty: FALSE, data: ALL[0]]], rest: vm.pages]; RETURN[vm.pages.first]; END; RETURN[NIL]; END; UnmapVMPage: PROC [ vm: VMObRef, page: VMPageRef ] = BEGIN IF page=NIL OR vm.pages=NIL THEN ERROR; IF vm.pages.first=page THEN vm.pages _ vm.pages.rest ELSE FOR p: LIST OF VMPageRef _ vm.pages, p.rest WHILE p.rest#NIL DO IF page = p.rest.first THEN {p.rest _ p.rest.rest; EXIT}; ENDLOOP; END; RejectCycles: PROC [ cor: CacheObRef, startCycle: INT, busCycles: NAT ] RETURNS [ rej: NAT ] = BEGIN IF startCycle=0 THEN startCycle _ cor.vm.firstFreeCycle; rej _ IF busCycles>0 THEN rej _ MAX[cor.vm.firstFreeCycle-startCycle, 2]+busCycles ELSE 0; <> cor.vm.firstFreeCycle _ cor.firstFreeCycle _ startCycle+rej; END; Parity32: PUBLIC PROC [ n: Dragon.Word ] RETURNS [ odd: BOOL ] = {RETURN[Parity16[Basics.LowHalf[n]] # Parity16[Basics.HighHalf[n]]]}; Parity16: PUBLIC PROC [ m: CARDINAL ] RETURNS [ p: BOOL ] = BEGIN q: CARDINAL = Basics.BITXOR[m, Basics.BITSHIFT[m, -8]]; r: CARDINAL = Basics.BITXOR[q, Basics.BITSHIFT[q, -4]]; s: CARDINAL = Basics.BITXOR[r, Basics.BITSHIFT[r, -2]]; t: CARDINAL = Basics.BITXOR[s, Basics.BITSHIFT[s, -1]]; RETURN [Basics.BITAND[t, 1] # 0]; END; NewVirtualMemoryFromFile: PUBLIC PROC [ fileName: Rope.ROPE ] RETURNS [ m: VirtualMemory ] = {m _ NewVirtualMemory[]; VirtualMemoryFromFile[m, fileName]}; NewVirtualMemory: PUBLIC PROC RETURNS [ m: VirtualMemory ] = {m _ lastVM _ NEW[VMOb _ []]}; VMFileFormat: PUBLIC ERROR = CODE; VirtualMemoryFromFile: PUBLIC PROC [ m: VirtualMemory, fileName: Rope.ROPE ] = BEGIN vm: VMObRef = GetVM[m]; s: IO.STREAM _ NIL; s _ FS.StreamOpen[fileName ! FS.Error => CONTINUE]; VirtualMemoryFromStream[vm, s]; IF s#NIL THEN s.Close[]; END; VirtualMemoryFromStream: PUBLIC PROC [ m: VirtualMemory, s: IO.STREAM ] = BEGIN InitializeFromStream: PROC [ s: IO.STREAM ] = BEGIN buffer: REF TEXT = RefText.ObtainScratch[512]; expName: REF TEXT _ RefText.ObtainScratch[512]; expression: RECORD [ name: ATOM _ NIL, hasValue: BOOL _ FALSE, value: Dragon.Word _ 0 ]; tokenKind: IO.TokenKind; token: REF TEXT; NextLooksLikeExpression: PROC RETURNS [ BOOL ] = {RETURN[(tokenKind IN [tokenDECIMAL..tokenHEX]) OR (tokenKind = tokenSINGLE AND token[0]='-) OR (tokenKind = tokenATOM) OR (tokenKind = tokenID) OR (tokenKind = tokenEOF)]}; GetExpression: PROC RETURNS [ valid: BOOL ] = BEGIN valid _ TRUE; expName.length _ 0; SELECT TRUE FROM tokenKind IN [tokenDECIMAL..tokenHEX] => BEGIN expression _ [name: NIL, hasValue: TRUE, value: Convert.CardFromRope[RefText.TrustTextAsRope[token]]]; [tokenKind: tokenKind, token: token] _ IO.GetCedarToken[s, buffer, TRUE]; END; tokenKind = tokenSINGLE AND token[0]='- => BEGIN [tokenKind: tokenKind, token: token] _ IO.GetCedarToken[s, buffer, TRUE]; valid _ GetExpression[]; IF NOT expression.hasValue THEN ERROR VMFileFormat; TRUSTED {expression.value _ LOOPHOLE[-LOOPHOLE[expression.value, INT]]}; END; tokenKind = tokenID OR tokenKind = tokenATOM => BEGIN atom: ATOM; value: REF; WHILE tokenKind = tokenID OR tokenKind = tokenATOM DO expName _ RefText.Append[to: expName, from: token]; [tokenKind: tokenKind, token: token] _ IO.GetCedarToken[s, buffer, TRUE]; IF tokenKind=tokenSINGLE AND token[0]='. THEN BEGIN expName _ RefText.AppendChar[to: expName, from: '.]; [tokenKind: tokenKind, token: token] _ IO.GetCedarToken[s, buffer, TRUE]; END ELSE EXIT; ENDLOOP; atom _ Convert.AtomFromRope[RefText.TrustTextAsRope[expName]]; value _ Atom.GetProp[atom: atom, prop: $DragonValue]; expression _ [name: atom, hasValue: value#NIL, value: (IF value#NIL THEN NARROW[value, REF Dragon.Word]^ ELSE 0)]; END; ENDCASE => valid _ FALSE; END; [tokenKind: tokenKind, token: token] _ IO.GetCedarToken[s, buffer, TRUE]; [] _ GetExpression[]; DO SELECT tokenKind FROM tokenEOF => EXIT; tokenERROR => ERROR VMFileFormat; tokenSINGLE => BEGIN c: CHARACTER = token[0]; SELECT c FROM '| => EXIT; -- alternative EOF ': => -- store words into word addresses BEGIN wordAddress: Dragon.Word; IF NOT expression.hasValue THEN ERROR VMFileFormat; wordAddress _ expression.value; [tokenKind: tokenKind, token: token] _ IO.GetCedarToken[s, buffer, TRUE]; WHILE GetExpression[] AND NextLooksLikeExpression[] DO page: VMPageRef = FindVMPage[vm: vm, address: wordAddress]; SELECT expression.name FROM $WriteProtect, $ReadOnly => page.writeProtect _ TRUE; $Dirty => page.dirty _ TRUE; ENDCASE => BEGIN IF NOT expression.hasValue THEN ERROR VMFileFormat; page.data[wordAddress-page.vAddr] _ expression.value; wordAddress _ wordAddress+1; END; ENDLOOP; END; '/ => -- store bytes into byte addresses BEGIN byteAddress: Dragon.Word; IF NOT expression.hasValue THEN ERROR VMFileFormat; byteAddress _ expression.value; [tokenKind: tokenKind, token: token] _ IO.GetCedarToken[s, buffer, TRUE]; WHILE GetExpression[] AND NextLooksLikeExpression[] DO page: VMPageRef = FindVMPage[vm: vm, address: byteAddress/4]; SELECT expression.name FROM $WriteProtect => page.writeProtect _ TRUE; $Dirty => page.dirty _ TRUE; ENDCASE => BEGIN background: Basics.LongNumber; IF NOT expression.hasValue THEN ERROR VMFileFormat; background.lc _ page.data[byteAddress/4-page.vAddr]; SELECT byteAddress MOD 4 FROM 0 => background.hh _ expression.value; 1 => background.hl _ expression.value; 2 => background.lh _ expression.value; 3 => background.ll _ expression.value; ENDCASE => ERROR; page.data[byteAddress/4-page.vAddr] _ background.lc; byteAddress _ byteAddress+1; END; ENDLOOP; END; '= => -- define a symbol BEGIN definee: ATOM = expression.name; IF definee=NIL THEN ERROR VMFileFormat; [tokenKind: tokenKind, token: token] _ IO.GetCedarToken[s, buffer, TRUE]; IF NOT GetExpression[] THEN ERROR VMFileFormat; IF NOT expression.hasValue THEN ERROR VMFileFormat; Atom.PutProp[atom: definee, prop: $DragonValue, val: NEW[Dragon.Word _ expression.value]]; [] _ GetExpression[]; END; '@ => -- indirect to another code file BEGIN [tokenKind: tokenKind, token: token] _ IO.GetCedarToken[s, buffer, TRUE]; SELECT tokenKind FROM tokenROPE => BEGIN rope: Rope.ROPE = Rope.FromRefText[token]; innerS: IO.STREAM; innerS _ FS.StreamOpen[rope.Substr[start: 1, len: rope.Length-2] ! FS.Error => {innerS _ NIL; CONTINUE}]; IF innerS#NIL THEN {InitializeFromStream[innerS]; innerS.Close[]}; [tokenKind: tokenKind, token: token] _ IO.GetCedarToken[s, buffer, TRUE]; END; ENDCASE => ERROR VMFileFormat; END; ENDCASE => ERROR VMFileFormat; END; -- of tokenSingle ENDCASE => ERROR VMFileFormat; ENDLOOP; END; -- of InitializeFromStream vm: VMObRef = GetVM[m]; vm.pages _ NIL; vm.firstFreeCycle _ 0; FOR c: LIST OF CacheObRef _ vm.caches, c.rest WHILE c#NIL DO [] _ NewCache[c.first]; ENDLOOP; IF s#NIL THEN InitializeFromStream[s]; END; OutStateRep: TYPE = RECORD [ s: IO.STREAM, lastAddr: Dragon.Word, wordsThisLine: NAT ]; OutState: TYPE = REF OutStateRep; VirtualMemoryToStream: PUBLIC PROC [ m: VirtualMemory, s: IO.STREAM ] = BEGIN os: OutState = NEW[OutStateRep _ [s: s, lastAddr: 0, wordsThisLine: 0]]; s.PutRope["--VM\n"]; EnumerateVirtualMemory[m, PrintWord, os]; s.PutRope["|\n"]; END; PrintWord: PROC [ addr, data: Dragon.Word, readOnly, dirty: BOOL _ FALSE, privateData: REF _ NIL ] = BEGIN os: OutState = NARROW[privateData]; IF os.wordsThisLine>=8 OR (os.wordsThisLine>0 AND (data=0 OR addr # os.lastAddr+1 OR (addr MOD 256 = 0))) THEN {os.s.PutChar['\n]; os.wordsThisLine _ 0}; IF addr MOD 256 = 0 OR data # 0 THEN BEGIN IF os.wordsThisLine = 0 THEN os.s.PutF["0%xH:", IO.card[addr]]; IF addr MOD 256 = 0 THEN BEGIN IF readOnly THEN os.s.PutRope[" $WriteProtect"]; IF dirty THEN os.s.PutRope[" $Dirty"]; END; os.s.PutF[" 0%xH", IO.card[data]]; os.wordsThisLine _ os.wordsThisLine+1; os.lastAddr _ addr; END; END; EnumerateVirtualMemory: PUBLIC PROC [ m: VirtualMemory, wdProc: PROC [ addr, data: Dragon.Word, readOnly, dirty: BOOL _ FALSE, privateData: REF _ NIL ], privateData: REF _ NIL ] = BEGIN vm: VMObRef = GetVM[m]; FOR p: LIST OF VMPageRef _ vm.pages, p.rest WHILE p#NIL DO FOR i: NAT IN [0..PageSize) DO wdProc[addr: p.first.vAddr+i, data: p.first.data[i], privateData: privateData]; ENDLOOP; ENDLOOP; END; lastCache: PUBLIC Cache _ NIL; defaultVM, lastVM: PUBLIC VirtualMemory _ NIL; END.