-- VMMgr>STLeafImpl.mesa (last edited by Levin on August 3, 1982 4:08 pm)
DIRECTORY
Environment USING [Base, bitsPerWord, first64K],
File USING [Capability, Create, Delete, GetSize, ID, LimitPermissions,
MakePermanent, PageCount, PageNumber, read, SetSize, Unknown, write],
Inline USING [LowHalf],
KernelFile USING [GetRootFile],
PilotFileTypes USING [tAnonymousFile, tVMBackingFile],
PilotSwitches USING [switches --.v--],
ResidentHeap USING [MakeNode],
Runtime USING [CallDebugger],
SimpleSpace USING [Create, Page, Map],
Space USING [Handle, PageNumber, WindowOrigin],
StoragePrograms USING [LongPointerFromPage],
STLeaf,
Utilities USING [BitIndex],
Volume USING [ID, GetAttributes, SystemID],
VM USING [PageCount, PageNumber, PageOffset],
VMMgrStore,
VMMPrograms,
Zone USING [Status];
STLeafImpl: PROGRAM
-- logically, this should be a MONITOR, but at present all procedures (in STLeaf and VMMgrStore) in this module are only called from within the SpaceImpl monitor.
IMPORTS
File, Inline, KernelFile, PilotSwitches, ResidentHeap, Runtime, SimpleSpace,
StoragePrograms, Volume
EXPORTS STLeaf, VMMgrStore, VMMPrograms
SHARES File --USING[fID]-- =
BEGIN
Bug: PRIVATE --PROGRAMMING-- ERROR [BugType] = CODE;
BugType: TYPE = {bug0, bug1, bug2, bug3, bug4, bug5, bug6};
--
-- VMMgrStore
-- Layout of VM backing file:
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- | MapLog | Space B-trees | backing pool for Data Spaces |
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
countLog: VM.PageCount = 40;
countSpaceBTreesMax: VM.PageCount = 300; -- allows increasing countSpaceBTrees
-- from the debugger, if necessary
CountSpaceBTreesRange: TYPE = CARDINAL [0..countSpaceBTreesMax);
countSpaceBTrees: CountSpaceBTreesRange ← 250; -- must be big enough to satisfy
-- any Pilot client.
minCountDataPool: VM.PageCount = 250; -- enough space for a (Dolphin) bitmap.
maxCountDataPool: VM.PageCount = 1000; -- (arbitrary)
countDataPool: VM.PageCount; -- depends on space available on volume.
minBackFileSize: VM.PageCount = countLog + countSpaceBTrees + minCountDataPool;
-- minimum size for backing file.
backFileSize: File.PageCount;
pageLog: VM.PageNumber = 0;
pageSpaceBTrees: VM.PageNumber = pageLog + countLog;
pageDataPool: VM.PageNumber = pageSpaceBTrees + countSpaceBTrees;
systemVolume: Volume.ID;
backingFile: File.Capability;
-- data for Data Pool:
fractionThreshold: CARDINAL = 10; -- windows larger than countDataPool /
-- fractionThreshold will be allocated as separate files.
countThreshold: VM.PageCount;
pageDataPoolAvailable: LONG POINTER TO PACKED ARRAY [0..0) OF BOOLEAN;
nSatisfiedFromDataPool, nCreated, currentUtilization: CARDINAL ← 0; -- usage
-- statistics.
InitVMMgrStore: PROCEDURE =
BEGIN
volSize, freePages, desiredBackFileSize: File.PageCount;
systemVolume ← Volume.SystemID[];
[volSize, freePages, ] ← Volume.GetAttributes[volume: systemVolume];
desiredBackFileSize ← MAX[
minBackFileSize, MIN[maxCountDataPool, volSize/16, freePages/10]];
backingFile ← KernelFile.GetRootFile[
PilotFileTypes.tVMBackingFile, systemVolume];
BEGIN
backFileSize ← File.GetSize[backingFile ! File.Unknown => GO TO Create];
IF backFileSize < minBackFileSize THEN
File.SetSize[backingFile, backFileSize ← minBackFileSize];
EXITS
Create => {
backingFile ← File.Create[
systemVolume, backFileSize ← desiredBackFileSize,
PilotFileTypes.tVMBackingFile];
File.MakePermanent[backingFile];
}
END;
IF backFileSize > LAST[VM.PageCount] THEN ERROR Bug[bug0];
countDataPool ← Inline.LowHalf[backFileSize] - countLog - countSpaceBTrees;
-- initialize Data Pool:
BEGIN
size: CARDINAL =
(countDataPool + Environment.bitsPerWord - 1)/Environment.bitsPerWord;
node: Environment.Base RELATIVE POINTER;
s: Zone.Status;
k: CARDINAL;
[node, s] ← ResidentHeap.MakeNode[size];
IF s ~= okay THEN ERROR Bug[bug1];
pageDataPoolAvailable ← @Environment.first64K[node];
IF maxCountDataPool > LAST[Utilities.BitIndex] THEN ERROR Bug[bug2];
-- restriction of Mesa 6.
FOR k IN [0..countDataPool) DO pageDataPoolAvailable[k] ← TRUE ENDLOOP;
countThreshold ← countDataPool/fractionThreshold;
END;
END;
AllocateWindow: PUBLIC PROCEDURE [
pWindowResult: LONG POINTER TO Space.WindowOrigin, count: VM.PageCount] =
BEGIN
offsetPage: VM.PageCount; -- offset of first free page of current run.
offsetOffset: VM.PageCount; -- offset of current free page from offsetPage.
IF count <= countThreshold THEN
FOR offsetPage ← 0, offsetOffset + 1 WHILE offsetPage + count <=
countDataPool DO
-- scope of HoleTooSmall --
BEGIN
FOR offsetOffset IN [offsetPage..offsetPage + count) DO
-- search for big enough run of free pages..
IF ~pageDataPoolAvailable[offsetOffset] THEN GO TO HoleTooSmall;
-- (value of offsetOffset must survive loop exit.)
ENDLOOP;
FOR offsetOffset IN [offsetPage..offsetPage + count) DO
-- mark run busy..
pageDataPoolAvailable[offsetOffset] ← FALSE;
ENDLOOP;
nSatisfiedFromDataPool ← nSatisfiedFromDataPool + 1;
-- tally usage statistics.
currentUtilization ← currentUtilization + count;
pWindowResult↑ ←
[File.LimitPermissions[backingFile, File.read + File.write], LONG[
pageDataPool + offsetPage]];
RETURN;
EXITS HoleTooSmall => NULL;
END;
ENDLOOP;
-- contiguous space not available from Data Pool. Allocate a new file:
nCreated ← nCreated + 1; -- tally usage statistics.
pWindowResult↑ ←
[File.Create[systemVolume, count, PilotFileTypes.tAnonymousFile], 0];
END;
DeallocateWindow: PUBLIC PROCEDURE [
pWindow: LONG POINTER TO Space.WindowOrigin, count: VM.PageCount] =
BEGIN OPEN pWindow --USING[file, base]--;
IF file.fID = backingFile.fID THEN
BEGIN
offsetPage, offsetOffset: VM.PageOffset;
offsetPage ← Inline.LowHalf[base] - pageDataPool;
IF base > LAST[VM.PageOffset] OR ~(offsetPage IN [0..countDataPool)) OR
~(offsetPage + count IN [0..countDataPool]) THEN ERROR Bug[bug3];
FOR offsetOffset IN [offsetPage..offsetPage + count) DO
IF pageDataPoolAvailable[offsetOffset] THEN ERROR Bug[bug4];
pageDataPoolAvailable[offsetOffset] ← TRUE;
ENDLOOP;
currentUtilization ← currentUtilization - count;
END
ELSE File.Delete[file];
END;
AllocateMapLogFile: PUBLIC PROCEDURE [
pWindowResult: LONG POINTER TO Space.WindowOrigin]
RETURNS [size: VM.PageCount] = {
pWindowResult↑ ← Space.WindowOrigin[backingFile, pageLog]; RETURN[countLog]};
--
-- STLeaf
SpaceBTreeOverflow: PRIVATE --PROGRAMMING-- ERROR = CODE;
spaceBTree: Space.Handle;
pageBTree: Space.PageNumber; -- the starting page of the BTree area.
leafAvailable: PACKED ARRAY CountSpaceBTreesRange OF BOOLEAN;
InitSTLeaf: PROCEDURE =
BEGIN
IF countSpaceBTrees > countSpaceBTreesMax THEN ERROR; -- in case runtime checks are off
leafAvailable ← ALL[TRUE];
spaceBTree ← SimpleSpace.Create[
countSpaceBTrees, hyperspace, --sizeSwapUnit:--1];
SimpleSpace.Map[
handle: spaceBTree, window: [backingFile, pageSpaceBTrees], andPin: FALSE];
pageBTree ← SimpleSpace.Page[spaceBTree];
END;
Close: PUBLIC PROCEDURE [iLeaf: STLeaf.ILeaf] = BEGIN END;
-- this procedure is now functionless, and therefore obsolete.
Create: PUBLIC PROCEDURE RETURNS [iLeaf: STLeaf.ILeaf] =
BEGIN
k: CARDINAL;
FOR k IN [0..countSpaceBTrees) DO
IF leafAvailable[k] THEN {
leafAvailable[k] ← FALSE; RETURN[STLeaf.ILeaf[k]]};
ENDLOOP;
ERROR SpaceBTreeOverflow;
END;
Delete: PUBLIC PROCEDURE [iLeaf: STLeaf.ILeaf] =
BEGIN
IF leafAvailable[iLeaf] THEN ERROR Bug[bug5];
leafAvailable[iLeaf] ← TRUE;
END;
Open: PUBLIC PROCEDURE [iLeaf: STLeaf.ILeaf] RETURNS [STLeaf.PLeaf] =
BEGIN
IF leafAvailable[iLeaf] THEN ERROR Bug[bug6];
RETURN[StoragePrograms.LongPointerFromPage[pageBTree + iLeaf]];
END;
--
-- Initialization
IF PilotSwitches.switches.v = down THEN Runtime.CallDebugger["Key Stop V"L];
InitVMMgrStore[]; -- 1 of 2.
InitSTLeaf[]; -- 2 of 2.
END.
May 16, 1978 11:29 AM McJones Created file
June 20, 1978 2:26 PM McJones Added SimpleSpace calls
June 21, 1978 10:31 AM McJones Open didn't set rgBuff.open
June 21, 1978 10:46 AM McJones Close didn't stop searching when buffer found
June 26, 1978 5:43 PM McJones Added iBuffMru hack
August 2, 1978 10:09 AM McJones Enabled File.SetSize calls
August 9, 1978 1:42 AM Purcell Use new SimpleSpace
September 6, 1978 9:51 AM McJones Use GetRootFile
September 29, 1978 10:52 AM McJones CR20.42: Replaced MakePermanent with
PutRootFile
August 8, 1979 4:30 PM McJones SpecialFile => KernelFile
September 4, 1979 10:02 AM Forrest Changed to use PilotFileTYpes
September 6, 1979 3:07 PM Ladner Installed instrumentation in leaf cache
November 26, 1979 5:50 PM Knutsen Added VMMgrStore implementation.
November 27, 1979 12:41 PM Knutsen InitVMMgrStore forgot to set backFileSize
sometimes.
Approx May 15, 1980 Forrest Converted to Mesa 6.
May 29, 1980 3:20 PM Knutsen Use VM Backing File for Hierarchy and Projection.
Use packed booleans for bit operations. Named the ERRORs.
Moved Key Stop V here from VMMControl.
June 3, 1980 5:36 PM Knutsen Don't use VM Backing File for large spaces.
July 30, 1980 2:04 PM Knutsen Change MapLog from 20 to 40 pages.
August 15, 1980 5:39 PM McJones Add "= CODE" to Bug
August 16, 1980 4:26 PM McJones Change countSpaceBTrees from 40 to 60
September 15, 1980 2:46 PM Fay Change countSpaceBTrees from 60 to 150,
and make variable.
September 16, 1980 5:57 PM Knutsen Add forgotten =CODE to ERROR.
4-Feb-82 13:27:46 Levin Change countSpaceBTrees to 250 pages.
August 3, 1982 4:08 pm Levin Correct all occurrences of ~IN.