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 = { 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] = { 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 { WHILE w.first.state = creating DO WAIT created ENDLOOP; IF w.first.state = bad THEN w.first.state _ creating; RETURN [w.first]; }; 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]; }; localWorld: World _ NIL; otherWorld: World _ NIL; EntryFindLocal: ENTRY PROC RETURNS [World] = INLINE { RETURN [localWorld]; }; GetWorld: PUBLIC PROC [where: Rope.ROPE] RETURNS [world: World] = { EndCreation: ENTRY PROC = INLINE { BROADCAST created; SELECT type FROM local => localWorld _ world; other => otherWorld _ world; ENDCASE => NULL; }; 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 { ENABLE UNWIND => { world.state _ bad; EndCreation[] }; IF world.type = other THEN WVMPrivate.LocateOther[]; GetMaplog[world]; EndRun[world]; world.state _ created; IF world.type = other THEN Booting.RegisterProcs[c: MyCheckpoint, r: MyRollback]; EndCreation[]; }; }; 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] = { ENABLE UNWIND => NULL; IF none = NIL THEN none _ NEW[WorldObject _ [name: "NoWorld", running: FALSE, foo: none[]]]; RETURN [none] }; InvalidateWorld: PUBLIC ENTRY PROC [world: World] = { ENABLE UNWIND => NULL; IF world = NIL THEN RETURN WITH ERROR BadWorld[]; world^ _ [name: "InvalidWorld", running: world.running, foo: none[]]; }; CurrentIncarnation: PUBLIC ENTRY PROC [world: World] RETURNS [WorldVM.Incarnation] = { ENABLE UNWIND => NULL; IF world = NIL THEN RETURN WITH ERROR BadWorld[]; RETURN [world.incarnation] }; WorldName: PUBLIC ENTRY PROC [world: World] RETURNS [ Rope.ROPE ] = { ENABLE UNWIND => NULL; IF world = NIL THEN RETURN WITH ERROR BadWorld[]; RETURN [ world.name ] }; loadStateRead: CONDITION; Loadstate: PUBLIC ENTRY PROC [world: World] RETURNS [ LoadState.Handle ] = { 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 ] }; ValidLoadstate: ENTRY PROC [world: World] = { ENABLE UNWIND => NULL; world.loadStateValid _ TRUE; BROADCAST loadStateRead; }; unlocked: CONDITION; Lock: PUBLIC ENTRY PROC [world: World] = { ENABLE UNWIND => NULL; IF world = NIL THEN RETURN WITH ERROR BadWorld[]; WHILE world.running DO WAIT unlocked ENDLOOP; world.lock _ world.lock+1; }; Unlock: PUBLIC ENTRY PROC [world: World] = { ENABLE UNWIND => NULL; IF world = NIL THEN RETURN WITH ERROR BadWorld[]; world.lock _ world.lock-1; BROADCAST unlocked; }; StartRun: PUBLIC ENTRY PROC [world: World] = { ENABLE UNWIND => NULL; waited: BOOL _ 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; }; EndRun: ENTRY PROC [world: World] = { IF world = NIL THEN RETURN WITH ERROR BadWorld[]; world.running _ FALSE; BROADCAST unlocked; }; Go: PUBLIC PROC [world: World] = { StartRun[world]; { 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]; }; EndRun[world]; }; MyCheckpoint: Booting.CheckpointProc = TRUSTED {}; MyRollback: ENTRY Booting.RollbackProc = TRUSTED { ENABLE UNWIND => NULL; world: World = otherWorld; IF NOT world.running THEN { world.loadStateValid _ FALSE; world.running _ TRUE; world.incarnation _ world.incarnation+1; world.vmBackingMap _ NIL; Process.Detach[FORK BootedWorld[world]]; }; }; BootedWorld: PROC [world: World] = { GetMaplog[world ! UNWIND => EndRun[world]]; EndRun[world]; }; GetMaplog: PROC [world: World] = { IF NOT world.running THEN ERROR; SELECT world.type FROM local => NULL; other, remote => { 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]; }; ENDCASE => NULL; }; 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 ] = { 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; }; 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; CacheIndex: TYPE = [0..101); 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 ] = { 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 { hits _ hits + 1; handle.users _ handle.users+1; WHILE handle.where.type = empty DO IF handle.coming THEN WAIT pageReady ELSE { handle.coming _ TRUE--we will read it in--; EXIT }; ENDLOOP; EXIT }; longSearches _ longSearches + 1; -- increment for each step along overflow chain -- handle _ handle.hashNext; ENDLOOP; IF handle = NIL THEN { misses _ misses + 1; handle _ LRUOld; DO IF handle = NIL THEN ERROR CacheFull[]; -- no victim -- IF handle.users = 0 THEN EXIT; handle _ handle.LRUYounger; ENDLOOP; 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; 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; IF cache[hash] # NIL THEN { fullBuckets _ fullBuckets + 1; cache[hash].hashPrev _ handle; }; handle.hashNext _ cache[hash]; handle.hashPrev _ NIL; cache[hash] _ handle; }; IF handle # LRUYoung THEN { IF handle.LRUOlder = NIL THEN LRUOld _ handle.LRUYounger ELSE handle.LRUOlder.LRUYounger _ handle.LRUYounger; IF handle.LRUYounger # NIL THEN handle.LRUYounger.LRUOlder _ handle.LRUOlder; IF LRUYoung # NIL THEN LRUYoung.LRUYounger _ handle; handle.LRUOlder _ LRUYoung; handle.LRUYounger _ NIL; LRUYoung _ handle; }; }; Init: ENTRY PROC [cachePages: NAT] = { 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; }; PageRead: ENTRY PROC [ handle: PageHandle, location: Location] = { ENABLE UNWIND => NULL; handle.where _ location; handle.coming _ FALSE; BROADCAST pageReady; }; ReleasePage: PUBLIC ENTRY PROC [handle: PageHandle] = { ENABLE UNWIND => NULL; handle.users _ handle.users-1; BROADCAST pageReady; -- for FlushWorld and for FindPage -- }; FlushWorld: INTERNAL PROC [world: World] = { DO waited: BOOL _ FALSE; FOR p: CacheIndex IN CacheIndex DO handle: PageHandle _ cache[p]; WHILE handle # NIL DO IF handle.world = world OR world = NIL THEN { WHILE handle.users > 0 DO waited _ TRUE; WAIT pageReady ENDLOOP; handle.world _ NIL; -- must leave handle.memPage intact for hash function -- }; handle _ handle.hashNext; ENDLOOP; ENDLOOP; IF NOT waited THEN EXIT ENDLOOP; }; ReadPage: PROC [handle: PageHandle] = { IF NOT ReadCorePage[handle] THEN { addr: WVMPrivate.DiskAddress _ WVMPrivate.GetVMBackingMapEntry[handle.world.vmBackingMap, handle.mempage]; ReadDiskPage[handle, addr]; }; }; BadWorld: PUBLIC ERROR = CODE; ReadCorePage: PROC [handle: PageHandle] RETURNS [ok: BOOL] = { ENABLE UNWIND => NULL; WITH w: handle.world SELECT FROM none => ERROR BadWorld[]; local => ERROR BadWorld[]; other => { ok _ WVMPrivate.ReadOtherCore[handle.data, handle.mempage]; IF ok THEN PageRead[ handle, [outLd[]] ]; }; remote => { m: WVMPrivate.MapEntry; [m, ok] _ WVMPrivate.ReadRemoteCore[w.host, handle.data, handle.mempage]; IF ok THEN PageRead[ handle, [remoteCore[m]] ]; }; ENDCASE => ERROR; }; ReadDiskPage: PROC [handle: PageHandle, addr: WVMPrivate.DiskAddress] = { ENABLE UNWIND => NULL; WITH w: handle.world SELECT FROM none => ERROR BadWorld[]; local => ERROR BadWorld[]; other => { WVMPrivate.MoveLocalDiskPage[handle.data, read, addr]; PageRead[ handle, [localDisk[addr]] ]; }; remote => { label: DiskFace.Label; WVMPrivate.ReadRemoteDisk[w.host, handle.data, addr, @label]; PageRead[ handle, [remoteDisk[addr,label]] ]; }; ENDCASE => ERROR; }; WriteAndReleasePage: PUBLIC PROC [handle: PageHandle] = { ENABLE UNWIND => NULL; Host: PROC RETURNS [ WVMPrivate.Machine] = { WITH w: handle.world SELECT FROM remote => RETURN [w.host]; ENDCASE => ERROR; }; WITH wh: handle.where SELECT FROM empty => ERROR; outLd => { readOnly: BOOL = WVMPrivate.WriteOtherCore[handle.data, handle.mempage]; IF readOnly THEN { ENABLE WorldVM.AddressFault => CONTINUE; -- => no backing store addr: WVMPrivate.DiskAddress _ WVMPrivate.GetVMBackingMapEntry[handle.world.vmBackingMap, handle.mempage]; WVMPrivate.MoveLocalDiskPage[handle.data, write, addr]; }; }; localDisk => { WVMPrivate.MoveLocalDiskPage[handle.data, write, wh.addr]; }; remoteCore => { host: WVMPrivate.Machine = Host[]; readOnly: BOOL = WVMPrivate.WriteRemoteCore[host, handle.data, handle.mempage, wh.map]; IF readOnly THEN { 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]; }; }; remoteDisk => { label: DiskFace.Label _ wh.label; WVMPrivate.WriteRemoteDisk[Host[], handle.data, wh.addr, @label]; }; ENDCASE => ERROR; ReleasePage[handle]; }; Init[32]; }. $WVMCache.mesa: cache of client pages Copyright c 1985 by Xerox Corporation. All rights reserved. Andrew Birrell December 2, 1983 1:19 pm Russ Atkinson (RRA) August 2, 1985 5:27:35 pm PDT Delicately arranged not to talk to the world inside our monitor This is only an optimisation we're responsible for doing the work. causes outload, boot; returns after inload 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 page cache itself! 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. Wait if someone else is reading it in for us -- find and claim victim remove from hash chain -- mark as ours place in hash chain remove from LRU chain add to LRU chain Return with handle.where.type = empty iff caller should read page in Initialise cache with all pages having mempage = 0, so all hash to cache[0]. else loop in case a page was added while we WAIT'ed -- Page transfers patching read-only page: must also write backing page (sigh!) patching read-only page: must also write backing page (sigh!) Initialize the cache with a (relatively) small number of pages (mostly to oblige users with a small amount of VM). If performance is really bad because of this, we can just call Init again via the interpreter with a higher number of pages! Κn˜codešœ$™$Kšœ Οmœ1™Kšžœ˜K˜—Kšœžœžœ ˜K˜Kšœ žœžœ˜2K˜Kšœ žœžœ žœ˜Kšœžœ ˜Kšœžœ ˜!Kšœ ž œ˜K˜š Οnœžœžœ)žœžœ˜{Kšœ?™?Kšžœžœžœ˜š žœžœžœžœž˜8šžœ˜šžœžœ žœž˜"Kšœ)žœžœ˜CKšžœžœ˜—šžœ˜Kšžœžœžœ žœ˜7Kšžœžœ˜5Kšžœ ˜Kšœ˜——Kšžœ˜—šžœž˜Kšœžœ,˜>Kšœžœ,˜>Kšœžœ1˜DKšžœžœ˜—Kšœ žœ˜,Kšœ˜K˜—Kšœžœ˜Kšœžœ˜K˜š Ÿœžœžœžœ žœ˜5Kšœ™Kšžœ˜Kšœ˜K˜—š Ÿœžœžœžœžœ˜CšŸ œžœžœžœ˜"Kšž œ ˜šžœž˜K˜K˜—Kšžœžœ˜Kšœ˜—K˜Kšœ˜šžœžœž˜Kšœžœ˜4Kšœžœ˜4šžœ˜ Kšœ˜Kšœ&˜&Kšœ˜——K˜*šžœžœ˜ Kšœ%™%Kšžœžœ)˜6šžœžœ˜4Kšœ*™*—K˜K˜K˜Kšžœžœ7˜QK˜Kšœ˜—Kšœ˜K˜—šŸ œžœžœžœ˜2Kšžœ˜Kšœ˜K˜—šŸ œžœžœžœ˜2Kšžœžœžœ˜EKšœ˜K˜—Kšœžœ˜K˜š Ÿœžœžœžœžœ˜5Kšžœžœžœ˜šžœžœž˜Kšœžœ*žœ˜I—Kšžœ˜ Kšœ˜K˜—šŸœžœžœžœ˜5Kšžœžœžœ˜Kš žœ žœžœžœžœžœ ˜1K˜EKšœ˜K˜—š Ÿœžœžœžœžœ˜VKšžœžœžœ˜Kš žœ žœžœžœžœžœ ˜1Kšžœ˜Kšœ˜K˜—š Ÿ œžœžœžœžœžœ˜EKšžœžœžœ˜Kš žœ žœžœžœžœžœ ˜1Kšžœ˜Kšœ˜K˜—Kšœž œ˜K˜š Ÿ œžœžœžœžœ˜LKšžœžœžœ˜Kš žœ žœžœžœžœžœ ˜1Kšžœžœžœ˜6Kšžœžœžœžœ˜9Kšžœ˜Kšœ˜K˜—šŸœžœžœ˜-Kšžœžœžœ˜Kšœžœ˜Kšž œ˜Kšœ˜K˜—Kšœή™ήK˜Kšœ ž œ˜K˜šŸœžœžœžœ˜*Kšžœžœžœ˜Kš žœ žœžœžœžœžœ ˜1Kšžœžœžœ žœ˜-K˜Kšœ˜K˜—šŸœžœžœžœ˜,Kšžœžœžœ˜Kš žœ žœžœžœžœžœ ˜1Kšœ˜Kšž œ ˜Kšœ˜K˜—šŸœžœžœžœ˜.KšœZ™ZKšžœžœžœ˜Kšœžœžœ˜Kš žœ žœžœžœžœžœ ˜1šž˜Kšœ˜Kšžœžœ˜%Kšžœ žœžœ žœ˜(Kš žœžœžœžœΟc%˜>Kšœ žœ˜Kšžœ˜—Kšœžœ˜Kšœžœ ,˜BK˜(Kšœžœ˜Kšœ˜K˜—šŸœžœžœ˜%Kš žœ žœžœžœžœžœ ˜1Kšœžœ˜Kšž œ ˜Kšœ˜K˜—šŸœžœžœ˜"Kšœ˜šœ˜Kšžœžœ˜šžœ žœž˜K˜&Kšœ  #˜CKšœžœ ˜Kšœ žœ˜—Kšžœžœ˜K˜Kšœ˜—K˜Kšœ˜K˜—šœ'žœ˜2K˜—šœ žœžœ˜2Kšžœžœžœ˜Kšœ˜šžœžœžœ˜Kšœžœ˜Kšœžœ˜K˜(Kšœžœ˜Kšœžœ˜(Kšœ˜—Kšœ˜—K˜šŸ œžœ˜$Kšœžœ˜+Kšœ˜Kšœ˜—K˜šŸ œžœ˜"Kšžœžœžœžœ˜ šžœ ž˜Kšœ žœ˜šœ˜K˜Kšœžœ˜K˜:K˜GK˜,K˜Kšœ˜—Kšžœžœ˜—Kšœ˜K˜—šŸœžœžœ,žœ˜ZKšžœžœ žœžœ˜8Kšœ˜K˜—š Ÿœžœžœ0žœ žœ.˜…Kš žœ žœžœžœžœžœ ˜1K˜"šžœžœ˜1Kšœžœ;˜C—K˜Kšœ˜K˜K˜—Kšœ™K˜Kšœς™ςK˜šœ žœžœžœ˜Kšœžœžœ˜$Kšœ7žœ˜;Kšœžœ˜Kšœžœžœ &˜Kšžœžœžœ˜šžœžœž˜ Kšœžœ ˜Kšœ žœ ˜šœ ˜ Kšœ;˜;Kšžœžœ˜)Kšœ˜—šœ ˜ K˜K˜IKšžœžœ%˜/Kšœ˜—Kšžœžœ˜—Kšœ˜K˜—šŸ œžœ7˜IKšžœžœžœ˜šžœžœž˜ Kšœžœ ˜Kšœ žœ ˜šœ ˜ K˜6K˜&Kšœ˜—šœ ˜ K˜K˜=K˜-Kšœ˜——Kšžœžœ˜Kšœ˜K˜—šŸœžœžœ˜9Kšžœžœžœ˜šŸœžœžœ˜,šžœžœž˜ Kšœ žœ ˜Kšžœžœ˜—Kšœ˜—šžœžœž˜!Kšœ žœ˜šœ ˜ Kšœ žœ:˜Hšžœ žœ˜Kšœ>™>Kšžœžœ ˜?K˜jK˜7Kšœ˜—Kšœ˜—šœ˜K˜:Kšœ˜—šœ˜Kšœ"˜"šœ žœ˜KšœF˜F—šžœ žœ˜Kšœ>™>Kšžœžœ ˜?K˜jK˜Kšœ žœ ˜FKšœ<˜