Cedar Remote Debugging: cache of client pages
WVMCache.mesa
Andrew Birrell December 2, 1983 1:19 pm
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;
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.
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
Ensures that world isn't running for someone else, isn't locked, and has no pages in cache
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! --
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.
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.