WVMCache.mesa: cache of client pages
Copyright © 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
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] = {
Delicately arranged not to talk to the world inside our monitor
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 {
This is only an optimisation
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 {
we're responsible for doing the work.
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[];
};
};
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;
};
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] = {
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] = {
Ensures that world isn't running for someone else, isn't locked, and has no pages in cache
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;
};
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;
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;
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
};
longSearches ← longSearches + 1; -- increment for each step along overflow chain --
handle ← handle.hashNext;
ENDLOOP;
IF handle =
NIL
THEN {
find and claim victim
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;
};
IF handle # LRUYoung
THEN {
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;
};
Return with handle.where.type = empty iff caller should read page in
};
Init:
ENTRY
PROC [cachePages:
NAT] = {
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;
};
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
else loop in case a page was added while we WAIT'ed --
ENDLOOP;
};
Page transfers
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 {
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];
};
};
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 {
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];
};
};
remoteDisk => {
label: DiskFace.Label ← wh.label;
WVMPrivate.WriteRemoteDisk[Host[], handle.data, wh.addr, @label];
};
ENDCASE => ERROR;
ReleasePage[handle];
};
Init[32];
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!
}.