-- VMMgr>HierarchyImpl.mesa (last edited by Knutsen on July 30, 1980 4:35 PM)
-- If there is an entry in the space cache, it is the truth. Information in the Hierarchy is 100% valid only if there is no entry in the cache.
DIRECTORY
CachedSpace USING [Delete, Desc, Get, Handle, handleNull, Insert, Level, PDesc, State, Update],
Hierarchy,
STree USING [Delete, Desc, Get, Insert, Key, Update],
Space USING [defaultWindow],
Transaction USING [nullHandle],
VM USING [Interval, PageCount, PageNumber],
VMMPrograms USING [];
HierarchyImpl: PROGRAM -- logically, this should be a MONITOR, but it is protected by the monitor lock of SpaceImpl, which is the only caller of this program.
IMPORTS CachedSpace, STree, Transaction EXPORTS Hierarchy, VMMPrograms =
BEGIN OPEN Hierarchy;
NotFound: PUBLIC ERROR = CODE;
pDescBuff: CachedSpace.PDesc -- must point to pinned storage because of CachedSpace calls
--residentFrames-- = @desc;
desc: CachedSpace.Desc; -- must be in pinned storage (see above).
LoadDesc: PROCEDURE [handle: CachedSpace.Handle] RETURNS [isSpaceHandle, isSwapUnitHandle: BOOLEAN] =
-- Loads matching space descriptor into global variable pDescBuff↑. handle may be a space handle or a swap unit handle. Returns [FALSE, FALSE] (and pDescBuff↑.state=missing) if not found. isSpaceHandle and isSwapUnitHandle are mutually exclusive. Handles are not required to fall exactly on the appropriate boundaries.
BEGIN
descVictim: CachedSpace.Desc;
-- Must try the cache first
IF handle.level<=LAST[CachedSpace.Level] THEN -- (don’t look for space if this must be a swap unit handle)
BEGIN
CachedSpace.Get[pDescBuff, handle]; -- look for a space handle in cache (must try cache before full Hierarchy).
IF pDescBuff.state~=missing THEN
RETURN[TRUE, FALSE];
END;
CachedSpace.Get[pDescBuff, CachedSpace.Handle[handle.level-1, handle.page]]; -- look for a swap unit handle in cache.
IF pDescBuff.state~=missing AND pDescBuff.hasSwapUnits THEN
RETURN[FALSE, TRUE];
-- Try full Hierarchy second
[] ← STree.Get[@LOOPHOLE[pDescBuff↑, STree.Desc], [hierarchy[handle]]]; -- look for a space handle in Hierarchy.
IF pDescBuff.state~=missing THEN
BEGIN isSpaceHandle ← TRUE; isSwapUnitHandle ← FALSE; END
ELSE
BEGIN
[] ← STree.Get[@LOOPHOLE[pDescBuff↑, STree.Desc], [hierarchy[CachedSpace.Handle[handle.level-1, handle.page]]]]; -- look for a swap unit handle in Hierarchy.
IF pDescBuff.state=missing THEN
RETURN[FALSE, FALSE]
ELSE
BEGIN
isSpaceHandle ← FALSE; isSwapUnitHandle ← pDescBuff.hasSwapUnits;
IF ~isSwapUnitHandle THEN RETURN[FALSE, FALSE]
-- (don’t cache unwanted desc)
END;
END;
-- Cache this (clean) descriptor, possibly displacing a dirty descriptor from the cache
pDescBuff.dPinned ← FALSE; pDescBuff.dDirty ← FALSE;
CachedSpace.Insert[@descVictim, pDescBuff];
IF descVictim.dDirty THEN STree.Update[@LOOPHOLE[descVictim, STree.Desc]];
RETURN[isSpaceHandle, isSwapUnitHandle];
END;
Delete: PUBLIC PROCEDURE [handle: CachedSpace.Handle] =
BEGIN
CachedSpace.Delete[handle];
STree.Delete[[hierarchy[handle]]]
END;
FindFirstWithin: PUBLIC PROCEDURE [handle: CachedSpace.Handle, count: VM.PageCount] RETURNS [CachedSpace.Handle] =
-- Bypasses cache
BEGIN
desc: STree.Desc;
keyNext: STree.Key = STree.Get[@desc, [hierarchy[handle]]];
IFcount=0 THEN RETURN[CachedSpace.handleNull]
ELSE IFdesc.descH.state~=missing THEN RETURN[[handle.level, desc.descH.interval.page]]
ELSE IFkeyNext.handleH.level=handle.level AND keyNext.handleH.page<handle.page+count THEN RETURN[keyNext.handleH]
ELSERETURN[CachedSpace.handleNull]
END;
GetDescriptor: PUBLIC PROCEDURE [pDescResult: POINTER TO CachedSpace.Desc, handle: CachedSpace.Handle]
RETURNS [validSpace, validSwapUnit: BOOLEAN] =
BEGIN
[validSpace, validSwapUnit] ← LoadDesc[handle];
pDescResult↑ ← pDescBuff↑; -- return copy of descriptor to caller (state=missing if not found).
IF validSpace THEN
RETURN[handle.page=pDescBuff.interval.page, FALSE]
ELSE IF validSwapUnit THEN
RETURN[FALSE, (handle.page-pDescBuff.interval.page) MOD pDescBuff.sizeSwapUnit = 0]
ELSE RETURN[validSpace, validSwapUnit]; -- = [FALSE, FALSE] (but space desc may have been found).
END;
GetInterval: PUBLIC PROCEDURE [handle: CachedSpace.Handle] RETURNS [validSpace, validSwapUnit: BOOLEAN, interval: VM.Interval] =
BEGIN
[validSpace, validSwapUnit] ← LoadDesc[handle];
IF validSpace THEN
RETURN[handle.page=pDescBuff.interval.page, FALSE, pDescBuff.interval]
ELSE IF validSwapUnit THEN
BEGIN
remainder: CARDINAL = (handle.page-pDescBuff.interval.page) MOD pDescBuff.sizeSwapUnit;
startPage: VM.PageNumber = handle.page-remainder;
RETURN[FALSE,
remainder = 0,
[startPage, MIN[pDescBuff.sizeSwapUnit, (pDescBuff.interval.page+pDescBuff.interval.count)-startPage]]];
END
ELSE
RETURN[validSpace, validSwapUnit, [0, 0]]; -- = [FALSE, FALSE, ...]
END;
ValidSpaceOrSwapUnit: PUBLIC PROCEDURE [handle: CachedSpace.Handle] RETURNS [BOOLEAN] =
BEGIN
validSpaceHandle, validSwapUnitHandle: BOOLEAN;
[validSpaceHandle, validSwapUnitHandle] ← LoadDesc[handle];
IF (validSpaceHandle AND handle.page=pDescBuff.interval.page) OR
(validSwapUnitHandle AND (handle.page-pDescBuff.interval.page) MOD pDescBuff.sizeSwapUnit = 0) THEN
RETURN[TRUE]
ELSE RETURN[FALSE];
END;
Insert: PUBLIC PROCEDURE [handle: CachedSpace.Handle, count: VM.PageCount] =
BEGIN
desc: STree.Desc ← [ hierarchy[ CachedSpace.Desc[
interval: [handle.page, count],
level: handle.level,
dPinned: FALSE, -- don’t care
dDirty: FALSE, -- don’t care
pinned: FALSE,
state: unmapped,
writeProtected: FALSE, -- don’t care
hasSwapUnits: FALSE,
sizeSwapUnit: 1, -- don’t care
dataOrFile: data, -- don’t care
pageRover: handle.page,
vp: long[
window: Space.defaultWindow, -- don’t care
countMapped: 0, -- don’t care
transaction: Transaction.nullHandle ] ] ] ]; -- not part of a transaction yet.
STree.Insert[@desc];
END;
Touch: PUBLIC PROCEDURE [handle: CachedSpace.Handle] =
BEGIN
[] ← LoadDesc[handle];
IF pDescBuff.state=missing THEN ERROR NotFound;
END;
Update: PUBLIC PROCEDURE [pDesc: POINTER TO CachedSpace.Desc] =
BEGIN
pDescBuff↑ ← pDesc↑;
IF ~CachedSpace.Update[pDescBuff].found THEN STree.Update[@LOOPHOLE[pDescBuff↑, STree.Desc]];
END;
END.
LOG
Time: May 23, 1978 9:45 AMBy: McJonesAction: Created file
Time: June 27, 1978 6:35 PMBy: McJonesAction: Didn’t set dPinned to FALSE before calling CachedSpace.Insert, .Update
Time: August 29, 1978 6:04 PMBy: McJonesAction: Clear dDirty before calling CachedSpace.Insert
Time: September 3, 1978 1:25 PMBy: McJonesAction: FindFirstWithin ignored keyNext.levelH
Time: September 10, 1978 1:38 PMBy: McJonesAction: Added pinned to constructor in Insert, etc.
Time: February 1, 1979 2:00 PMBy: McJonesCR20.169: Added pageRover to CachedSpace.Desc
Time: February 20, 1979 10:51 AMBy: McJonesCR20.177: Changed Update to preserve dPinned (!)
Time: September 7, 1979 10:24 AMBy: McJonesAction: FindFirstWithin ignored count=0
Time: October 1, 1979 9:42 AMBy: KnutsenAction: Made compatible with new CachedSpace.Desc.
Time: November 8, 1979 11:36 AMBy: KnutsenAction: Use Swap Unit Handles as well as Space Handles. Procedures return validSpace and validSwapUnit instead of validHandle. GetState replaced by ValidSpaceOrSwapUnit.
Time: November 9, 1979 11:47 AMBy: KnutsenAction: Make Touch not require a strict handle.
Time: November 14, 1979 2:08 PMBy: KnutsenAR2832: Make LoadDesc not cache an unrequested descriptor.
Time: July 30, 1980 4:34 PMBy: KnutsenAction: Insert must initialize desc with nullTransaction.