DIRECTORY Booting USING[ CheckpointProc, RegisterProcs, RollbackProc ], DiskFace USING[ Label ], LoadState USING[ Handle, local ], Process USING[ Detach ], Rope USING[ Equal, ROPE ], WorldVM USING[ Address, AddressFault, Incarnation, ShortAddress ], WVMPrivate; WVMCache: MONITOR IMPORTS Booting, LoadState, Process, Rope, WorldVM, WVMPrivate EXPORTS WorldVM, WVMPrivate = BEGIN World: TYPE = REF WorldObject; WorldObject: PUBLIC TYPE = WVMPrivate.WorldObject; universe: LIST OF World _ NIL; localName: Rope.ROPE = "Local"; otherName: Rope.ROPE = "Outload"; created: CONDITION; EntryFindWorld: ENTRY PROC[type: WVMPrivate.WorldType, name: Rope.ROPE, host: WVMPrivate.Machine] RETURNS[new: World] = -- Delicately arranged not to talk to the world inside our monitor -- BEGIN ENABLE UNWIND => NULL; FOR w: LIST OF World _ universe, w.rest UNTIL w = NIL DO IF w.first.type = type AND ( WITH ww: w.first SELECT FROM remote => Rope.Equal[w.first.name, name, FALSE] AND ww.host = host, ENDCASE => TRUE ) THEN BEGIN WHILE w.first.state = creating DO WAIT created ENDLOOP; IF w.first.state = bad THEN w.first.state _ creating; RETURN[w.first]; END; ENDLOOP; SELECT type FROM local => new _ NEW[WorldObject _ [name: name, foo: local[] ]]; other => new _ NEW[WorldObject _ [name: name, foo: other[] ]]; remote => new _ NEW[WorldObject _ [name: name, foo: remote[host] ]]; ENDCASE => ERROR; universe _ CONS[rest: universe, first: new]; END; localWorld: World _ NIL; otherWorld: World _ NIL; EntryFindLocal: ENTRY PROC RETURNS[World] = INLINE -- This is only an optimisation -- { RETURN[localWorld] }; GetWorld: PUBLIC PROC[where: Rope.ROPE] RETURNS[world: World] = BEGIN EndCreation: ENTRY PROC = INLINE BEGIN BROADCAST created; SELECT type FROM local => localWorld _ world; other => otherWorld _ world; ENDCASE => NULL; END; host: WVMPrivate.Machine; type: WVMPrivate.WorldType; SELECT TRUE FROM Rope.Equal[where, localName, FALSE] => type _ local; Rope.Equal[where, otherName, FALSE] => type _ other; ENDCASE => { type _ remote; host _ WVMPrivate.LocateRemote[where] }; world _ EntryFindWorld[type, where, host]; IF world.state = creating THEN -- we're responsible for doing the work. -- BEGIN ENABLE UNWIND => { world.state _ bad; EndCreation[] }; IF world.type = other THEN WVMPrivate.LocateOther[]; -- causes outload, boot; returns after inload -- GetMaplog[world]; EndRun[world]; world.state _ created; IF world.type = other THEN Booting.RegisterProcs[c: MyCheckpoint, r: MyRollback]; EndCreation[]; END; END; OtherWorld: PUBLIC PROC RETURNS[world: World] = { RETURN[ GetWorld[otherName] ] }; LocalWorld: PUBLIC PROC RETURNS[world: World] = { IF (world _ EntryFindLocal[]) = NIL THEN world _ GetWorld[localName] }; none: World _ NIL; NoWorld: PUBLIC ENTRY PROC RETURNS[world: World] = BEGIN ENABLE UNWIND => NULL; IF none = NIL THEN none _ NEW[WorldObject _ [name: "NoWorld", running: FALSE, foo: none[]]]; RETURN[none] END; InvalidateWorld: PUBLIC ENTRY PROC[world: World] = BEGIN ENABLE UNWIND => NULL; IF world = NIL THEN RETURN WITH ERROR BadWorld[]; world^ _ [name: "InvalidWorld", running: world.running, foo: none[]]; END; CurrentIncarnation: PUBLIC ENTRY PROC[world: World] RETURNS[WorldVM.Incarnation] = BEGIN ENABLE UNWIND => NULL; IF world = NIL THEN RETURN WITH ERROR BadWorld[]; RETURN[world.incarnation] END; WorldName: PUBLIC ENTRY PROC[world: World] RETURNS[ Rope.ROPE ] = BEGIN ENABLE UNWIND => NULL; IF world = NIL THEN RETURN WITH ERROR BadWorld[]; RETURN[ world.name ] END; loadStateRead: CONDITION; Loadstate: PUBLIC ENTRY PROC[world: World] RETURNS[ LoadState.Handle ] = BEGIN ENABLE UNWIND => NULL; IF world = NIL THEN RETURN WITH ERROR BadWorld[]; IF world.type = local THEN RETURN[ LoadState.local ]; UNTIL world.loadStateValid DO WAIT loadStateRead ENDLOOP; RETURN[ world.loadState ] END; ValidLoadstate: ENTRY PROC[world: World] = BEGIN ENABLE UNWIND => NULL; world.loadStateValid _ TRUE; BROADCAST loadStateRead; END; unlocked: CONDITION; Lock: PUBLIC ENTRY PROC[world: World] = BEGIN ENABLE UNWIND => NULL; IF world = NIL THEN RETURN WITH ERROR BadWorld[]; WHILE world.running DO WAIT unlocked ENDLOOP; world.lock _ world.lock+1; END; Unlock: PUBLIC ENTRY PROC[world: World] = BEGIN ENABLE UNWIND => NULL; IF world = NIL THEN RETURN WITH ERROR BadWorld[]; world.lock _ world.lock-1; BROADCAST unlocked; END; StartRun: PUBLIC ENTRY PROC[world: World] = BEGIN waited: BOOLEAN _ FALSE; IF world = NIL THEN RETURN WITH ERROR BadWorld[]; DO FlushWorld[world]; WHILE world.lock > 0 OR world.running DO waited _ TRUE; WAIT unlocked ENDLOOP; IF NOT waited THEN EXIT; -- else we may need to flush again -- waited _ FALSE; ENDLOOP; world.loadStateValid _ FALSE; world.running _ TRUE; -- gives us exclusive access to the world -- world.incarnation _ world.incarnation+1; world.vmBackingMap _ NIL; END; EndRun: ENTRY PROC[world: World] = BEGIN IF world = NIL THEN RETURN WITH ERROR BadWorld[]; world.running _ FALSE; BROADCAST unlocked; END; Go: PUBLIC PROC[world: World] = BEGIN StartRun[world]; BEGIN ENABLE UNWIND => EndRun[world]; WITH w: world SELECT FROM remote => WVMPrivate.GoRemote[w.host]; other => WVMPrivate.GoOther[]; -- causes outload, client inload -- none => ERROR BadWorld[]; local => NULL; ENDCASE => ERROR; GetMaplog[world]; END; EndRun[world]; END; MyCheckpoint: Booting.CheckpointProc = TRUSTED {}; MyRollback: ENTRY Booting.RollbackProc = TRUSTED BEGIN ENABLE UNWIND => NULL; world: World = otherWorld; IF NOT world.running THEN BEGIN world.loadStateValid _ FALSE; world.running _ TRUE; world.incarnation _ world.incarnation+1; world.vmBackingMap _ NIL; Process.Detach[FORK BootedWorld[world]]; END; END; BootedWorld: PROC[world: World] = BEGIN GetMaplog[world ! UNWIND => EndRun[world]]; EndRun[world]; END; GetMaplog: PROC[world: World] = BEGIN ENABLE UNWIND => NULL; IF NOT world.running THEN ERROR; SELECT world.type FROM local => NULL; other, remote => BEGIN basic, real: WorldVM.Address; world.vmBackingMap _ NIL; world.vmBackingMap _ WVMPrivate.CreateVMBackingMap[world]; [basic, real] _ WVMPrivate.ReadVMBackingMap[world, world.vmBackingMap]; WVMPrivate.GetLoadState[world, basic, real]; ValidLoadstate[world]; END; ENDCASE => NULL; END; Long: PUBLIC PROC[world: World, addr: WorldVM.ShortAddress] RETURNS[WorldVM.Address] = { RETURN[ IF addr = 0 THEN 0 ELSE addr + world.mdsBase ] }; GetPage: PUBLIC PROC[world: World, mempage: WVMPrivate.PageNumber] RETURNS[ data: REF WVMPrivate.PageData, handle: PageHandle ] = BEGIN IF world = NIL THEN RETURN WITH ERROR BadWorld[]; handle _ FindPage[world, mempage]; IF handle.where.type = empty THEN ReadPage[handle ! UNWIND => { PageRead[handle, [empty[]]]; ReleasePage[handle] } ]; data _ handle.data; END; -- The page cache itself! -- PageInfo: PUBLIC TYPE = RECORD[ data: REF WVMPrivate.PageData _ NIL, LRUYounger, LRUOlder, hashNext, hashPrev: PageHandle _ NIL, users: CARDINAL _ 0, coming: BOOL _ FALSE, -- whether someone is reading it in -- mempage: WVMPrivate.PageNumber _ 0 -- "0" assumed in "Init" --, world: World _ NIL, where: Location ]; Location: TYPE = RECORD[ SELECT type: * FROM empty => NULL, outLd => NULL, localDisk => [addr: WVMPrivate.DiskAddress], remoteCore => [map: WVMPrivate.MapEntry], remoteDisk => [addr: WVMPrivate.DiskAddress, label: DiskFace.Label _ NULL], ENDCASE] _ [empty[]]; PageHandle: TYPE = REF PageInfo; cachePages: INT = 200; CacheIndex: TYPE = [0..501); cache: REF ARRAY CacheIndex OF PageHandle = NEW[ARRAY CacheIndex OF PageHandle _ ALL[NIL]]; pageReady: CONDITION; CacheFull: ERROR = CODE; LRUOld, LRUYoung: PageHandle _ NIL; hits: INT _ 0; -- number of cache lookup hits -- longSearches: INT _ 0; -- number of times lookup followed overflow chain -- misses: INT _ 0; -- number of cache lookup misses (hits + misses = requests)-- fullBuckets: INT _ 0; -- number of times hash bucket was already occupied when inserting -- FindPage: ENTRY PROC[world: World, mempage: WVMPrivate.PageNumber] RETURNS[ handle: PageHandle ] = BEGIN ENABLE UNWIND => NULL; hash: CacheIndex = mempage MOD (LAST[CacheIndex]+1); handle _ cache[hash]; UNTIL handle = NIL DO IF handle.world = world AND handle.mempage = mempage THEN BEGIN hits _ hits + 1; handle.users _ handle.users+1; -- Wait if someone else is reading it in for us -- WHILE handle.where.type = empty DO IF handle.coming THEN WAIT pageReady ELSE { handle.coming _ TRUE--we will read it in--; EXIT }; ENDLOOP; EXIT END; longSearches _ longSearches + 1; -- increment for each step along overflow chain -- handle _ handle.hashNext; ENDLOOP; IF handle = NIL THEN -- find and claim victim -- BEGIN misses _ misses + 1; handle _ LRUOld; DO IF handle = NIL THEN ERROR CacheFull[]; -- no victim -- IF handle.users = 0 THEN EXIT; handle _ handle.LRUYounger; ENDLOOP; -- remove from hash chain -- IF handle.hashPrev = NIL THEN cache[handle.mempage MOD (LAST[CacheIndex]+1)] _ handle.hashNext ELSE handle.hashPrev.hashNext _ handle.hashNext; IF handle.hashNext # NIL THEN handle.hashNext.hashPrev _ handle.hashPrev; -- mark as ours -- handle.where _ [empty[]]; -- cache is always clean -- handle.coming _ TRUE--we will read it in--; IF handle.data = NIL THEN handle.data _ NEW[WVMPrivate.PageData _ NULL]; handle.users _ 1; handle.mempage _ mempage; handle.world _ world; -- place in hash chain -- IF cache[hash] # NIL THEN { fullBuckets _ fullBuckets + 1; cache[hash].hashPrev _ handle }; handle.hashNext _ cache[hash]; handle.hashPrev _ NIL; cache[hash] _ handle; END; IF handle # LRUYoung THEN BEGIN -- remove from LRU chain -- IF handle.LRUOlder = NIL THEN LRUOld _ handle.LRUYounger ELSE handle.LRUOlder.LRUYounger _ handle.LRUYounger; IF handle.LRUYounger # NIL THEN handle.LRUYounger.LRUOlder _ handle.LRUOlder; -- add to LRU chain -- IF LRUYoung # NIL THEN LRUYoung.LRUYounger _ handle; handle.LRUOlder _ LRUYoung; handle.LRUYounger _ NIL; LRUYoung _ handle; END; -- Return with handle.where.type = empty iff caller should read page in -- END; Init: ENTRY PROC = BEGIN -- Initialise cache with all pages having mempage = 0, so all hash to cache[0]. -- LRUYoung _ LRUOld _ cache[0] _ NEW[PageInfo]; THROUGH [1..cachePages) DO handle: PageHandle _ NEW[PageInfo]; cache[0].hashPrev _ handle; handle.hashNext _ cache[0]; handle.hashPrev _ NIL; cache[0] _ handle; LRUYoung.LRUYounger _ handle; handle.LRUOlder _ LRUYoung; handle.LRUYounger _ NIL; LRUYoung _ handle; ENDLOOP; END; PageRead: ENTRY PROC[ handle: PageHandle, location: Location] = { ENABLE UNWIND => NULL; handle.where _ location; handle.coming _ FALSE; BROADCAST pageReady }; ReleasePage: PUBLIC ENTRY PROC[handle: PageHandle] = BEGIN ENABLE UNWIND => NULL; handle.users _ handle.users-1; BROADCAST pageReady; -- for FlushWorld and for FindPage -- END; FlushWorld: INTERNAL PROC[world: World] = BEGIN DO waited: BOOLEAN _ FALSE; FOR p: CacheIndex IN CacheIndex DO handle: PageHandle _ cache[p]; DO IF handle = NIL THEN EXIT; IF handle.world = world OR world = NIL THEN BEGIN WHILE handle.users > 0 DO waited _ TRUE; WAIT pageReady ENDLOOP; handle.world _ NIL; -- must leave handle.memPage intact for hash function -- END; handle _ handle.hashNext; ENDLOOP; ENDLOOP; IF NOT waited THEN EXIT -- else loop in case a page was added while we WAIT'ed -- ENDLOOP; END; -- Page transfers -- ReadPage: --EXTERNAL-- PROC[handle: PageHandle] = BEGIN IF NOT ReadCorePage[handle] THEN BEGIN addr: WVMPrivate.DiskAddress _ WVMPrivate.GetVMBackingMapEntry[handle.world.vmBackingMap, handle.mempage]; ReadDiskPage[handle, addr]; END; END; BadWorld: PUBLIC ERROR = CODE; ReadCorePage: --EXTERNAL-- PROC[handle: PageHandle] RETURNS[ok: BOOLEAN] = BEGIN ENABLE UNWIND => NULL; WITH w: handle.world SELECT FROM none => ERROR BadWorld[]; local => ERROR BadWorld[]; other => BEGIN ok _ WVMPrivate.ReadOtherCore[handle.data, handle.mempage]; IF ok THEN PageRead[ handle, [outLd[]] ]; END; remote => BEGIN m: WVMPrivate.MapEntry; [m, ok] _ WVMPrivate.ReadRemoteCore[w.host, handle.data, handle.mempage]; IF ok THEN PageRead[ handle, [remoteCore[m]] ]; END; ENDCASE => ERROR; END; ReadDiskPage: --EXTERNAL-- PROC[handle: PageHandle, addr: WVMPrivate.DiskAddress] = BEGIN ENABLE UNWIND => NULL; WITH w: handle.world SELECT FROM none => ERROR BadWorld[]; local => ERROR BadWorld[]; other => BEGIN WVMPrivate.MoveLocalDiskPage[handle.data, read, addr]; PageRead[ handle, [localDisk[addr]] ]; END; remote => BEGIN label: DiskFace.Label; WVMPrivate.ReadRemoteDisk[w.host, handle.data, addr, @label]; PageRead[ handle, [remoteDisk[addr,label]] ]; END; ENDCASE => ERROR; END; WriteAndReleasePage: PUBLIC --EXTERNAL-- PROC[handle: PageHandle] = BEGIN ENABLE UNWIND => NULL; Host: PROC RETURNS[ WVMPrivate.Machine] = BEGIN WITH w: handle.world SELECT FROM remote => RETURN[w.host]; ENDCASE => ERROR; END; WITH wh: handle.where SELECT FROM empty => ERROR; outLd => BEGIN readOnly: BOOL = WVMPrivate.WriteOtherCore[handle.data, handle.mempage]; IF readOnly THEN BEGIN -- patching read-only page: must also write backing page (sigh!) ENABLE WorldVM.AddressFault => CONTINUE; -- => no backing store addr: WVMPrivate.DiskAddress _ WVMPrivate.GetVMBackingMapEntry[handle.world.vmBackingMap, handle.mempage]; WVMPrivate.MoveLocalDiskPage[handle.data, write, addr]; END; END; localDisk => BEGIN WVMPrivate.MoveLocalDiskPage[handle.data, write, wh.addr]; END; remoteCore => BEGIN host: WVMPrivate.Machine = Host[]; readOnly: BOOL = WVMPrivate.WriteRemoteCore[host, handle.data, handle.mempage, wh.map]; IF readOnly THEN BEGIN -- patching read-only page: must also write backing page (sigh!) ENABLE WorldVM.AddressFault => CONTINUE; -- => no backing store addr: WVMPrivate.DiskAddress _ WVMPrivate.GetVMBackingMapEntry[handle.world.vmBackingMap, handle.mempage]; label: DiskFace.Label; WVMPrivate.ReadRemoteDisk[host, NIL, addr, @label];--to get the label! WVMPrivate.WriteRemoteDisk[host, handle.data, addr, @label]; END; END; remoteDisk => BEGIN label: DiskFace.Label _ wh.label; WVMPrivate.WriteRemoteDisk[Host[], handle.data, wh.addr, @label]; END; ENDCASE => ERROR; ReleasePage[handle]; END; Init[]; END. Cedar Remote Debugging: cache of client pages WVMCache.mesa Andrew Birrell December 2, 1983 1:19 pm Per-world synchronization. Public may call Lock and Unlock to freeze debuggee during access to debuggee data structures. StartRun and EndRun prevent running while locked, locking while running, and running while running. Ensures that world isn't running for someone else, isn't locked, and has no pages in cache The cache is organized as a hash table with chained overflow and LRU replacement. The hash overflow chains and the LRU chain are doubly linked to ease removal. The hash function is (mempage MOD number of buckets). The number of buckets is approximately twice the number of cache pages. The number of buckets is coprime with such numbers as 128, 256 to avoid clashes. Êê˜Jšœ-™-Jšœ ™ Jšœ(™(J˜šÏk ˜ Jšœœ0˜=Jšœ œ ˜Jšœ œ˜!Jšœœ ˜Jšœœ œ˜Jšœœ5˜BJ˜ —J˜šœ ˜Jšœ7˜>Jšœ˜—J˜š˜J˜—Jšœœœ ˜J˜Jšœ œœ˜2J˜Jšœ œœ œ˜Jšœœ ˜Jšœœ ˜!Jšœ œ˜J˜šÏnœœœ(œ˜aJšœ˜JšÏcE˜EJš˜Jšœœœ˜Jš œœœœ˜5šœœ˜šœœ œ˜"Jšœ)œœ˜CJšœœ˜—šœ˜ Jšœœœ œ˜7Jšœœ˜5Jšœ ˜Jšœ˜——Jšœ˜šœ˜Jšœœ,˜>Jšœœ,˜>Jšœœ1˜D—Jšœœ˜Jšœ œ˜,Jšœ˜J˜—Jšœœ˜Jšœœ˜J˜š žœœœœ ˜2JšŸ"˜"Jšœœ˜J˜—š žœœœ œœ˜?Jš˜šž œœœ˜ Jš˜Jš œ ˜šœ˜J˜J˜—Jšœœ˜Jšœ˜—J˜Jšœ˜šœœ˜Jšœœ˜4Jšœœ˜4—Jšœ=˜DJ˜*Jšœ˜šœŸ+˜0Jš˜Jšœœ)˜6Jšœ˜JšœŸ0˜OJ˜J˜J˜Jšœœ7˜QJ˜Jšœ˜—Jšœ˜J˜—šž œœœœ˜/Jšœœ˜"J˜—šž œœœœ˜/Jšœœœœ˜IJ˜—Jšœœ˜J˜š žœœœœœ˜2Jš˜Jšœœœ˜šœœœœ˜+Jšœœ˜0—Jšœ˜ Jšœ˜J˜—šžœœœœ˜2Jš˜Jšœœœ˜Jš œ œœœœœ ˜1J˜EJšœ˜J˜—šžœœœœ˜3Jšœ˜Jš˜Jšœœœ˜Jš œ œœœœœ ˜1Jšœ˜Jšœ˜J˜—š ž œœœœœœ˜AJš˜Jšœœœ˜Jš œ œœœœœ ˜1Jšœ˜Jšœ˜J˜—Jšœ œ˜J˜šž œœœœ˜*Jšœ˜Jš˜Jšœœœ˜Jš œ œœœœœ ˜1Jšœœœ˜5Jšœœœœ˜9Jšœ˜Jšœ˜J˜—šžœœœ˜*Jš˜Jšœœœ˜Jšœœ˜Jš œ˜Jšœ˜J˜—JšœN™NJšœO™OJšœ?™?J˜Jšœ œ˜J˜šžœœœœ˜'Jš˜Jšœœœ˜Jš œ œœœœœ ˜1Jšœœœ œ˜-J˜Jšœ˜J˜—šžœœœœ˜)Jš˜Jšœœœ˜Jš œ œœœœœ ˜1Jšœ œ ˜.Jšœ˜J˜—šžœœœœ˜+Jš˜JšœZ™ZJšœœœ˜Jš œ œœœœœ ˜1šœ˜Jšœœ˜%Jšœ œœ œ˜(Jš œœœœŸ%˜>Jšœ œ˜—Jšœ˜Jšœœ˜JšœœŸ,˜BJ˜(Jšœœ˜Jšœ˜J˜—šžœœœ˜"Jš˜Jš œ œœœœœ ˜1Jšœœ œ ˜*Jšœ˜J˜—šžœœœ˜Jš˜Jšœ˜š˜Jšœœ˜šœ œ˜J˜&Jšœ Ÿ#˜CJšœœ ˜Jšœ œ˜—Jšœœ˜J˜—Jšœ˜J˜Jšœ˜J˜—šœ'˜.Jšœ˜J˜—šœ œ˜0Jš˜Jšœœœ˜Jšœ˜Jšœœ˜šœ˜ Jšœœ˜Jšœœ˜J˜(Jšœœ˜Jšœœ˜(Jšœ˜—Jšœ˜—J˜šž œœ˜!Jš˜Jšœœ˜+Jšœ˜Jšœ˜—J˜šž œœ˜Jš˜Jšœœœ˜Jšœœœœ˜ šœ ˜˜Jšœ˜—˜Jš˜J˜Jšœœ˜J˜:J˜GJ˜,J˜Jšœ˜——Jšœœ˜Jšœ˜J˜—šžœœœ*˜;Jšœ˜Jš œœœ œœ˜;J˜—šžœœœ.˜BJšœœ,˜>Jš˜Jš œ œœœœœ ˜1J˜"Jšœ˜šœ˜Jšœ;˜A—J˜Jšœ˜J˜J˜J˜—JšŸ˜J˜JšœQ™QJšœM™MJšœ5™5JšœG™GJšœP™PJ˜šœ œœœ˜Jšœœœ˜$Jšœ7œ˜;Jšœœ˜JšœœœŸ&˜