<> <> <> <> 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]; <> }.