-- Store>CachedRegion.mesa (last edited by Knutsen on July 31, 1980 10:50 AM)

-- This interface defines operations on regions and swap units and higher-level access to region descriptors. The reader is assumed to be familiar with Virtual Memory Management as described in the Pilot Functional Specification.

-- Definitions:

-- Swap units are the units of storage which are swapped in or out as a unit. They are of uniform size within a region, except that the last one may be short.

-- If a region hasSwapUnits, a swap unit is the subregion containing pageMember which starts on an even sizeSwapUnit boundary; if it does not, a swap unit is the whole region.

-- Invariants:

-- If any swap unit of a region is in, its descriptor is in the cache.

-- If a region is inPinned, at least one of its swap units are in.

-- If a swap unit is in, and its region is inPinned, the swap unit will be continuously present at its assigned address.

-- If a region is outDead, all of its swap units are outDead. Currently, if a region hasSwapUnits, we do not ever mark it outDead.

-- If a region is unMapped, all of its swap units are out.

-- If a region hasSwapUnits and its descriptor is absent from the cache, its state=unmapped.

-- If a region has ~writeProtected AND ~needsLogging, at least one of its swap units has the pageFlags set to allow writing.

-- If a region has protection=readOnly, at least one of its swap units has the pageFlags set to disallow writing.

-- If a region is beingFlushed, at least one of its swap units are out.

-- Caveats:

-- The proper operation of remap and unmap is dependent on there being only one client operating on a region at a time (exclusive of page faults).

-- For clean[andWriteProtect:TRUE], clean[andNeedsLogging:TRUE], flush, remap, and unmap the caller must Apply the particular operation (successfully) once for each swap unit in the region. In addition, in the case of flush, flush must be repetitively called in ascending order of swap unit.

-- The current implementation demands that there be only one space being remapped at any given time!

-- Notes:

-- If a space is being remapped, there are two possible windows in which each swap unit in the space may reside.

-- A swap unit which is In may nevertheless have zero real pages assigned, if is past the end of the mapping file.

DIRECTORY

CachedSpace USING [Desc, Level],

Utilities USING [BitIndex],

VM USING [Interval, PageCount, PageNumber];

CachedRegion: DEFINITIONS =

BEGIN

Desc: TYPE = RECORD [-- A Region Descriptor.

interval: VM.Interval,

level: CachedSpace.Level,-- level of most-deeply-nested containing space.

levelMapped: CachedSpace.Level,-- level of mapping space (assuming state IN Mapped).

hasSwapUnits: BOOLEAN,-- is region divided into uniform swap units?

dTemperature: DTemperature,-- for cache replacement algorithm state (private to impl.)

dPinned: BOOLEAN,-- descriptor ineligible for replacement?

dDirty: BOOLEAN,-- descriptor modified since cached? (actually, have any of the parts of the descriptor which are also in a projection STLeaf.Desc been modified since cached?)

state: State,

writeProtected: BOOLEAN,-- Does the client have permission to write into the region?

needsLogging: BOOLEAN,-- Some swap units of the region are pageMap-writeProtected because the region is part of a transaction and should be writable, but not all swap units have been saved in the TransactionLog yet.

beingFlushed: BOOLEAN ];-- "although the Desc is in the cache, it should be considered missing."

DTemperature: TYPE = [0..4);-- should have 2n values (assuming state IN Mapped).

State: TYPE = {

missing,-- descriptor is missing from cache (and therefore, the region from memory)

checkedOut,-- descriptor is in cache, but checked-out

-- Descriptor available:

unmapped,

-- Mapped:

outDead,-- contents of backing window may be ignored.

-- Alive:

-- AliveSwappable:

outAlive,

-- In:

inSwappableColdest, inSwappable2, inSwappable3, inSwappableWarmest,

inPinned};-- (only if space or ancestor is pinned)

-- If a region hasSwapUnits and region.state IN AliveSwappable, the specific value of state is meaningless. In this case, the State is determined from the page flags.

-- If a region hasSwapUnits and region.state = inPinned, outDead, or unMapped, region.state shows the target state for all of the swap units.

DescAvailable:TYPE = State[unmapped..inPinned];

Mapped:TYPE = DescAvailable[outDead..inPinned];

Out:TYPE = Mapped[outDead..outAlive];

Swappable:TYPE = Mapped[outDead..inSwappableWarmest];

Alive:TYPE = Mapped[outAlive..inPinned];

AliveSwappable:TYPE = Swappable[outAlive..inSwappableWarmest];

In:TYPE = Alive[inSwappableColdest..inPinned];

InSwappable:TYPE = In[inSwappableColdest..inSwappableWarmest];

-- The following type is not used in a Desc at present, but may be useful elsewhere:

-- (It reflects that fact that that the state writeProtected AND needsLogging does not occur.)

Protection: TYPE = {-- write-protected state of swap units of region.

writable,-- the client has permission to write into the region.

readOnly,-- the client does not have permission to write into the region.

needsLogging };-- some swap units of the region are pageMap-writeProtected because the region is part of a transaction and should be writable, but not all swap units have been saved in the TransactionLogFile yet.

Insert: PROCEDURE [desc: Desc] RETURNS [descVictim: Desc];

-- inserts a region descriptor into the region cache.

-- desc.dPinned and desc.dDirty are significant; desc.dTemperature is ignored.

-- If descVictim.dDirty, then descVictim must be written through to the higher level database.

Apply: PROCEDURE [pageMember: VM.PageNumber, operation: Operation]
RETURNS [outcome: Outcome, pageNext: VM.PageNumber];

-- Sets pageNext to the start of the next swap unit (or next region if this is the last swap unit of the region) if a descriptor for the region containing pageMember is in the region descriptor cache; else sets pageNext to start of the next region in the cache (possibly having state=missing); if no next region, sets pageNext to pageTop.

-- operation acts on the swap unit containing pageMember, except that createSwapUnits, deleteSwapUnits, get, map, and unpin act on the entire region (and return pageNext = the start of the next region).

pageTop: VM.PageNumber;

Outcome: TYPE = RECORD [SELECT kind: * FROM

ok => NULL,

notePinned => [levelMax: CachedSpace.Level], -- the region was pinned on entry. Only from unpin. (The requested action was done).

regionDMissing => NULL, -- region desc not in region cache. (The requested action was not done.)

regionDDirty => NULL, -- only from flush. (The requested action was not done.)

retry => NULL, -- Please try again! Only from copyIn and copyOut. (The requested action was not done.)

spaceDMissing => [level: CachedSpace.Level], -- space desc not in space cache. (The requested action was not done.)

error => [state: CachedRegion.State], -- (The requested action was not done.)

ENDCASE];

ActivatePagefault: TYPE = {activate, pagefault};

BackFileType: TYPE = {file, data, none};

ReportSkip: TYPE = {report, skip};

ReturnWait: TYPE = {return, wait};

maxRemapSpaceSize: CARDINAL = LAST[Utilities.BitIndex]-FIRST[Utilities.BitIndex]+1;

PageLocationInSpace: TYPE = LONG DESCRIPTOR FOR ARRAY [0..0) OF WORD; -- (one bit per page of space being remapped. Currenly limited to maxRemapSpaceSize bits maximum.)

pageLocationInSpace: PageLocationInSpace; -- supplied to Apply by caller of remap for the duration of the Space.Remap operation.

oldSpaceCountMapped: VM.PageCount; -- supplied to Apply by caller of remap for the duration of the Space.Remap operation.

Operation: TYPE = RECORD [

ifMissing: ReportSkip, -- "if descriptor is missing from region desc cache"

ifCheckedOut: ReturnWait, -- "if someone else is operating on region"

afterForking: ReturnWait, -- wait if any i/o started?

vp: SELECT action: * FROM

activate => [why: ActivatePagefault], -- get swap unit in. activate[why:activate] is a hint and is legal on unmapped regions.

age => NULL, -- make swap unit older. If old enough, swap it out.

clean => [andWriteProtect: BOOLEAN, andNeedsLogging: BOOLEAN], -- make sure contents of window reflect current content of region. A no-op on pinned regions. The caller must call clean once successfully (outcome=[ok[]]) for each swap unit of the region!

copyIn => [from: POINTER TO CachedSpace.Desc], -- input from other than the normal backing file. Sets needsLogging to FALSE.

copyOut => [to: POINTER TO CachedSpace.Desc], -- output to other than the normal backing file.

createSwapUnits => NULL, -- mark the (whole) region "has swap units".

deactivate => NULL, -- write this swap unit out. This is a hint.

flush => NULL, -- flush all swap units of the region from memory and the region descriptor from the cache. If outcome=[regionDDirty]], no action was taken. The caller must, in ascending order, call flush once successfully (outcome=[ok[]]) for each swap unit of the region!

get => [andResetDDirty: BOOLEAN, pDescResult: POINTER TO Desc], -- "get (whole) region descriptor"

kill => [andDeallocate: BOOLEAN], -- mark swap unit contents "of no value". This is a hint. If andDeallocate, deallocate any memory now behind the swap unit. This part is not a hint: it is always done.

makeWritable => NULL, -- turn off write protect. The caller should have write access to the backing file. Sets needsLogging to FALSE.

map => [level: CachedSpace.Level, backFileType: BackFileType, andWriteProtect: BOOLEAN, andNeedsLogging: BOOLEAN], -- map the (whole) region. If backFileType=none, allocates real memory and pins it.

noOp => NULL,

pin => NULL, -- get the swap unit in, then pin into memory all swap units of the region which are in. OK to pin a swap unit of an already pinned region.

remapA => [firstClean: BOOLEAN], -- (implicit parameter: pageLocationInSpace.) Mark the location of the swap unit to be "in old window". The caller must call remapA once successfully (outcome=[ok[]]) for each swap unit of the region! The current implementation demands that there be only one space being remapped at any given time!

remapB => [from: POINTER TO CachedSpace.Desc], -- (implicit parameter: pageLocationInSpace.) Make sure that the swap unit is in the new window, or is In and dirty. Sets needsLogging to FALSE. The caller must call remapB once successfully (outcome=[ok[]]) for each swap unit of the region!

unmap => NULL, -- writes out the swap unit. If it is the last swap unit of the region, also marks the region unmapped. If region was pinned on entry, does the work and returns outcome=[notePinned[...]]. The caller must call unmap once successfully (outcome=[ok[]] or [notePinned[...]]) for each swap unit of the region!

unpin => NULL, -- unpin the whole region. OK to unpin an unpinned region.

ENDCASE];

-- Standard region operations

-- name:mumble Operation= [ifMissing,ifCkdOut,afterForking,action[other parameters]]

activate:activate Operation= [report,return,return,activate[why: activate]];

age:age Operation= [skip,return,return,age[]];

createSwapUnits:createSwapUnits Operation= [report,wait,wait,createSwapUnits[]];

deactivate:deactivate Operation= [skip,return,return,deactivate[]];

flush:flush Operation= [skip,wait,wait,flush[]];

forceOut:clean Operation= [skip,wait,wait,clean[andWriteProtect: FALSE, andNeedsLogging: FALSE]];

invalidate:kill Operation= [report,wait,return,kill[andDeallocate: TRUE]];

kill:kill Operation= [report,wait,return,kill[andDeallocate: FALSE]];

needsLogging:clean Operation= [report,wait,wait,clean[andWriteProtect: TRUE, andNeedsLogging: TRUE]];

makeWritable:makeWritable Operation= [report,wait,wait,makeWritable[]];

pin:pin Operation= [report,wait,wait,pin[]];

pagefault:activate Operation= [report,return,return,activate[why: pagefault]];

-- Note that pagefault.ifCheckedOut=return. In this case, the faulting process is left sleeping by the pageFault handling process. This requires that, whenever any Desc is checked in, processes waiting on pageFaults on that region must be restarted.

startForceOut:clean Operation= [skip,wait,return,clean[andWriteProtect: FALSE, andNeedsLogging: FALSE]];

startUnmap:unmap Operation= [report,wait,return,unmap[]];

unmap:unmap Operation= [report,wait,wait,unmap[]];

unpin:unpin Operation= [report,wait,return,unpin[]]; -- actually, ifMissing => error

writeProtect:clean Operation= [report,wait,wait,clean[andWriteProtect: TRUE, andNeedsLogging: FALSE]];

wait:noOp Operation= [skip,wait,wait,noOp[]];

END.

Notes

The level and levelMapped fields can be more compactly encoded by observing that if state IN Mapped, levelMapped is IN (1..level]; we can define the following:

LM: TYPE = {l0, l1m1, l2m1, l2m2, l3m1, l3m2, l3m3, . . .};

So 4 levels requires only 3 bits; the 4 bits currently used for level and levelMapped would allow 6 levels.

To complete the scheme, we define:

LevelFromLM: ARRAY LM OF Level = [0, 1, 2, 2, 3, 3, 3, . . .]; and

LevelMappedFromLM: ARRAY LM OF Level = [dontcare, 1, 1, 2, 1, 2, 3, . . .];

LOG

Time: March 1978By: McJonesAction: Created file

Time: June 7, 1978 12:22 PMBy: McJonesAction: DTemperature had closed upper bound

Time: June 20, 1978 1:16 PMBy: McJonesAction: Added get, getResetDDirty operations

Time: June 23, 1978 4:34 PMBy: McJonesAction: Dropped CheckOut/CheckIn

Time: August 1, 1978 4:00 PMBy: McJonesAction: Removed pageNext from Outcome; dropped probe, added unusedXX

Time: August 4, 1978 1:32 PMBy: McJonesAction: Added beingRemapped; remap => remapA+remapB

Time: September 10, 1978 1:20 PMBy: McJonesAction: Added Swappable, notePinned

Time: March 7, 1979 1:24 PMBy: McJonesCR20.48: Added andWriteProtect to clean Operation

Time: August 30, 1979 1:46 PMBy: KnutsenAdded backFileType to map operation. Added writeProtect to Desc (not utilized yet). Added noOp, startOut, startUnmap, and wait Operations.

Time: October 15, 1979 4:05 PMBy: KnutsenAction: Added hasSwapUnits and beingFlushed to Desc. Added createSwapUnits and deleteSwapUnits. Modified parameters of remapA. Added pageLocationInSpace and remapOldSpaceD. Documented the interface.

Time: January 21, 1980 10:13 AMBy: KnutsenAction: Replaced remapOldSpaceD with oldSpaceCountMapped. Improved documentation.

Time: March 28, 1980 3:11 PMBy: KnutsenAction: Deleted deleteSwapUnits. Added outputSpecial.

Time: May 20, 1980 4:50 PMBy: GobbelAction: Added needsToBeLogged field to Desc, retry to Outcome, from field to outputSpecial variant of Operation.

Time: July 31, 1980 10:50 AMBy: KnutsenAction: Added needsLogging parameter to Desc and various operations. Added andDeallocate to kill and invalidate operation. Added Protection.