-- 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.