[Indigo]<Cedar>Pilot>VolFileMapImpl.mesa!1

-- VolFileMapImpl.mesa (last edited by: Luniewski on: September 17, 1980 5:15 PM)

DIRECTORY

Environment USING [wordsPerPage],

File USING [Capability, ID, lastPageNumber, nullCapability, PageNumber],

FileInternal USING [Descriptor, FilePtr, maxPermissions, PageGroup],

FMPrograms USING[],

Inline USING [LongCOPY],

KernelFile USING[],

LogicalVolume USING [Handle, Interval, Key, Level, maxKey, maxID, nullInterval, nullIntervals, nullKey, nullVolumePage, PageNumber, Vfm, VolumeAccess, VolumeAccessProc],

PilotFileTypes USING [tVolumeFileMap],

SimpleSpace USING [Create, ForceOut, Map, Page, Unmap],

Space USING [Handle],

Utilities USING [LongPointerFromPage],

VolAllocMap USING [AllocPageGroup, FreePageGroup],

VolFileMap USING[],

Volume USING [ID, NotOpen, nullID, Unknown];

VolFileMapImpl: MONITOR

IMPORTS Inline, LogicalVolume, SimpleSpace, Utilities, VolAllocMap, Volume

EXPORTS FMPrograms, KernelFile, VolFileMap

SHARES File =

BEGIN OPEN LogicalVolume;

-- data types for the vfm

-- fixed length, uncompressed indexes are stored now now but in the future compressed indexes will have variable lengths. Compressed format is defined by VolFileMap.PutNext and VolFileMap.ReadNext

Buffer: TYPE = RECORD [--This is a B-tree page

data: ARRAY [0..indexInBuffer) OF Index,

used: BufferPtr];

BufferPtr: TYPE = INTEGER;

GroupPtr: TYPE = POINTER TO FileInternal.PageGroup;

Index: TYPE = RECORD [

key: Key,

volumePage: PageNumber,

ptr: BufferPtr];

KeyPtr: TYPE = POINTER TO Key;

FindProc: TYPE = PROCEDURE;

XtraProc: TYPE = PROCEDURE;

indexInBuffer: CARDINAL = (Environment.wordsPerPage-SIZE[BufferPtr])/SIZE[Index];

maxReadPtr: CARDINAL = SIZE[Buffer]-SIZE[BufferPtr];

maxIndex: Index = Index[maxKey, nullVolumePage, 0];

nullIndex: Index = Index[nullKey, nullVolumePage, 0];

-- This is the monitor protected data. Someday, we may wish to have multiple sets of these beasts

currentID: Volume.ID ← Volume.nullID;

volumeHandle: LogicalVolume.Handle ← NIL;

-- Buffer used for most access; page#null => buffer is mapped

bufferPage: PageNumber ← LogicalVolume.nullVolumePage;

bufferHandle: Space.Handle = SimpleSpace.Create[1, hyperspace];

buffer: LONG POINTER TO Buffer = Utilities.LongPointerFromPage[SimpleSpace.Page[bufferHandle]];

-- Buffer used for splits/merges

xtraHandle: Space.Handle = SimpleSpace.Create[1, hyperspace];

xtraBuffer: LONG POINTER TO Buffer = Utilities.LongPointerFromPage[SimpleSpace.Page[xtraHandle]];

interval: Interval ← nullInterval;

old, low, high: Index ← nullIndex;

VolFileMapImplError: ERROR [{pagesMissingInFile, illegalReturnCode}] = CODE;

-- External Procedures

Close: PUBLIC ENTRY PROCEDURE [final: BOOLEAN] = BEGIN ContextFlush[final]; END;

-- deletes a pageGroup suffix (leaving zeroPageGroup unless explicitly asked) returns group deleted into groupPtr

DeletePageGroup: PUBLIC ENTRY PROCEDURE [vol: LogicalVolume.Handle, filePtr: FileInternal.FilePtr, groupPtr: GroupPtr] =

BEGIN

key: Key ← [filePtr.fileID, groupPtr.nextFilePage-(IF groupPtr.nextFilePage=0 THEN 0 ELSE 1)];

interval: Interval;

ContextSet[vol];

interval ← Get[@key, 0];

IF interval.key.fileID#filePtr.fileID OR interval.volumePage=nullVolumePage THEN ERROR VolFileMapImplError[pagesMissingInFile];

groupPtr.filePage ← key.filePage ← MAX[interval.key.filePage, groupPtr.filePage];

groupPtr.volumePage ← interval.volumePage + groupPtr.filePage - interval.key.filePage;

IF groupPtr.filePage #0 THEN

BEGIN

IF interval.key=key THEN Delete[@key, 0];

Insert[@key, nullVolumePage, 0];-- no check for merging since preceding is assumed present

END;

key.filePage ← groupPtr.nextFilePage;

Delete[@key, 0];-- no check for merging since following is assumed vacant

END;

-- Does this belong here???

GetNextFile: PUBLIC PROCEDURE [volume: Volume.ID, file: File.Capability] RETURNS [nextFile: File.Capability] =

BEGIN

fileD: local FileInternal.Descriptor ← [file.fID, volume, local[,,,]];

GetNextFileProc: ENTRY LogicalVolume.VolumeAccessProc =

BEGIN

key: Key ← Key[fileD.fileID, File.lastPageNumber];

updateMarkers ← FALSE;

ContextSet[volume];

fileD.fileID ← Get[@key, 0].nextKey.fileID;

IF fileD.fileID = LogicalVolume.maxID THEN fileD.fileID ← File.nullCapability.fID;-- end with null

END;

SELECT LogicalVolume.VolumeAccess[@volume, GetNextFileProc] FROM

ok => NULL;

volumeUnknown => ERROR Volume.Unknown[volume];

volumeNotOpen => ERROR Volume.NotOpen[volume];

ENDCASE => ERROR VolFileMapImplError[illegalReturnCode];

RETURN [[fileD.fileID, IF fileD.fileID=File.nullCapability.fID THEN 0 ELSE FileInternal.maxPermissions]]

END;

-- finds page group containing key (filePage=nextFilePage=size when off end of file)

GetPageGroup: PUBLIC ENTRY PROCEDURE [vol: LogicalVolume.Handle, filePtr: FileInternal.FilePtr, filePage: File.PageNumber] RETURNS [success: BOOLEAN, group: FileInternal.PageGroup] =

BEGIN

key: Key ← Key[filePtr.fileID, filePage];

interval: Interval;

ContextSet[vol];

interval ← Get[@key, 0];

RETURN[interval.key.fileID=filePtr.fileID, FileInternal.PageGroup[

filePage: interval.key.filePage,

volumePage: interval.volumePage,

nextFilePage: (IF interval.nextKey.fileID=filePtr.fileID THEN interval.nextKey ELSE interval.key).filePage]];--covers page zero and size requests

END;

-- inserts a pageGroup into B-tree (unordered inserts are merged for rebuild)

InsertPageGroup: PUBLIC ENTRY PROCEDURE [vol: LogicalVolume.Handle, filePtr: FileInternal.FilePtr, groupPtr: GroupPtr] =

BEGIN

key: Key ← [filePtr.fileID, groupPtr.filePage];

interval: Interval;

ContextSet[vol];

interval ←Get[@key, 0];

IF interval.key=key THEN BEGIN Delete[@key, 0]; interval ← Get[@key, 0]; END;

IF key.filePage-interval.key.filePage#groupPtr.volumePage-interval.volumePage OR key.fileID#interval.key.fileID THEN

Insert[@key, groupPtr.volumePage, 0];--merge with previous

key.filePage ← groupPtr.nextFilePage;

IF interval.nextKey#key AND groupPtr.filePage#groupPtr.nextFilePage THEN

Insert[@key, nullVolumePage, 0];

IF interval.nextKey=key AND Get[@key, 0].volumePage=interval.volumePage+interval.nextKey.filePage-interval.key.filePage THEN

Delete[@key, 0];--merge with following

END;

InitMap: PUBLIC ENTRY PROCEDURE[vol: LogicalVolume.Handle] =

BEGIN

level: LogicalVolume.Level;

nullKeyInstance: Key ← nullKey;

vol.interval ← LogicalVolume.nullIntervals;

ContextSet[vol];

vol.vfmStart ← CreateVPage[];

FOR level DECREASING IN [0..vol.treeLevel) DO--init the tree

Insert[@nullKeyInstance, (IF level = 0 THEN nullVolumePage ELSE CreateVPage[]), level];

ENDLOOP;

END;

-- INTERNAL PROCEDURES.........

-- ~~~~~ These Two Beasties Play with the variables in grand fashion

ContextFlush: INTERNAL PROCEDURE [final: BOOLEAN] = INLINE

BEGIN

IF bufferPage # LogicalVolume.nullVolumePage THEN

IF final THEN

BEGIN

SimpleSpace.Unmap[bufferHandle];

bufferPage ← LogicalVolume.nullVolumePage;

END

ELSE

SimpleSpace.ForceOut[bufferHandle];

IF final THEN currentID ← Volume.nullID;

END;

ContextSet: INTERNAL PROCEDURE [vol: LogicalVolume.Handle] =

BEGIN

IF currentID#vol.vID THEN

BEGIN

IF bufferPage#LogicalVolume.nullVolumePage THEN

BEGIN

SimpleSpace.Unmap[bufferHandle];

bufferPage ← LogicalVolume.nullVolumePage;

END;

currentID ← vol.vID;

END;

volumeHandle ← vol;

END;

-- merely calls VolAllocMap.AllocPageGroup to get a new page for the vfm B-tree

CreateVPage: INTERNAL PROCEDURE RETURNS [LogicalVolume.PageNumber] =

BEGIN OPEN volumeHandle↑;

group: FileInternal.PageGroup ← [0, 0, 1];

vfmFileD: FileInternal.Descriptor ← [LogicalVolume.Vfm[volumeHandle], vID, local[FALSE, FALSE, volumeSize, PilotFileTypes.tVolumeFileMap]];

VolAllocMap.AllocPageGroup[volumeHandle, @vfmFileD, @group, TRUE];

RETURN[group.volumePage];

END;

DeleteError: SIGNAL = CODE;

-- deletes the index <= the key, error if no index (merge is called from find)

Delete: INTERNAL PROCEDURE [key: KeyPtr, level: Level] =

BEGIN

firstFlag, lastFlag: BOOLEAN;

volumePage: LogicalVolume.PageNumber;-- page holding key (delete if firstFlag AND lastFlag)

nextKey: Key;-- the following key must be slid down over deleted key

Delete1: INTERNAL FindProc =

BEGIN

firstFlag ← (low.ptr=0);

lastFlag ← (high.ptr=buffer.used);

volumePage ← interval.volumePage;

nextKey ← high.key;

IF low.key~=key↑ THEN SIGNAL DeleteError;

IF firstFlag AND NOT lastFlag THEN Inline.LongCOPY[buffer+high.ptr, (buffer.used ← buffer.used - high.ptr), buffer];

END;

Delete2: INTERNAL FindProc =

BEGIN

tempBuffer: Buffer;

high ← Index[nextKey, low.volumePage, high.ptr];

low ← old;

Inline.LongCOPY[buffer+high.ptr, buffer.used - high.ptr, @tempBuffer];

PutNext[@high.key, high.volumePage, level];

Inline.LongCOPY[@tempBuffer, buffer.used - high.ptr, buffer+low.ptr];

buffer.used ← low.ptr + buffer.used - high.ptr;

END;

Find[key, level, Delete1];-- get the preceeding index

IF firstFlag THEN

BEGIN

Delete[key, level+1];

IF lastFlag THEN FreeVPage[volumePage] --free after remaping

ELSE Insert[@nextKey, volumePage, level+1];

END;

Find[key, level, Delete2];-- get the preceeding index

END;

-- executes proc with context (buffer, low, high) surrounding key (merges too)

Find: INTERNAL PROCEDURE [key: KeyPtr, level: Level, proc: FindProc] =

BEGIN

interval ← Get[key, level+1];

IF interval.volumePage#bufferPage THEN

BEGIN

IF bufferPage#LogicalVolume.nullVolumePage THEN SimpleSpace.Unmap[bufferHandle];

SimpleSpace.Map[bufferHandle, [[LogicalVolume.Vfm[volumeHandle], FileInternal.maxPermissions], interval.volumePage], FALSE];

bufferPage ← interval.volumePage;

END;

old ← low ← high ← Index[interval.key, nullVolumePage, 0];--init reader

UNTIL Lower[key, @high.key] DO ReadNext[]; ENDLOOP;--scan this page till key is passed

proc[];-- test before ’unmap’, Merge after; postpone Unmap until later to optimize out

IF buffer.used <= SIZE[Buffer]/3 AND interval.nextKey#maxKey THEN Merge[@old.key, level]; --is interval.key correct? (consider merge)

END;

-- calls VolAllocMap.FreePageGroup to free a page of the vfm B-tree

FreeVPage: INTERNAL PROCEDURE [volumePage: LogicalVolume.PageNumber] =

BEGIN

group: FileInternal.PageGroup ← [volumePage, volumePage, volumePage+1];

vfmFileD: FileInternal.Descriptor ← [LogicalVolume.Vfm[volumeHandle], volumeHandle.vID, local[FALSE, FALSE, volumeHandle.volumeSize, PilotFileTypes.tVolumeFileMap]];

VolAllocMap.FreePageGroup[volumeHandle, @vfmFileD, @group, TRUE];

END;

Get: INTERNAL PROCEDURE [key: KeyPtr, level: Level] RETURNS [interval: Interval]=

BEGIN-- returns value without reading a page when possible

Get1: INTERNAL FindProc =

BEGIN

volumeHandle.interval[level] ← Interval[low.key, high.volumePage, high.key];

END;

IF level > volumeHandle.treeLevel OR level > LAST[Level] THEN ERROR;

IF level=volumeHandle.treeLevel THEN RETURN[Interval[nullKey, volumeHandle.vfmStart, maxKey]];

interval ← volumeHandle.interval[level];-- try the cached intry

IF Lower[key, @interval.key] OR ~Lower[key, @interval.nextKey] THEN Find[key, level, Get1];

RETURN[volumeHandle.interval[level]];

END;

-- inserts (key, volumePage (including duplicates) calling split if necessary

Insert: INTERNAL PROCEDURE [key: KeyPtr, volumePage: PageNumber, level: Level] =

BEGIN

splitFlag: BOOLEAN;

Insert1: INTERNAL FindProc =

BEGIN

tempBuffer: Buffer;

IF (splitFlag ← (buffer.used > maxReadPtr-SIZE[Index])) THEN RETURN;

Inline.LongCOPY[buffer+high.ptr, buffer.used - high.ptr, @tempBuffer];

IF low.ptr < buffer.used THEN PutNext[key, high.volumePage, level];

PutNext[@high.key, volumePage, level];

Inline.LongCOPY[@tempBuffer, buffer.used - high.ptr, buffer+low.ptr];

buffer.used ← low.ptr + buffer.used - high.ptr;

END;

Find[key, level, Insert1];

IF splitFlag THEN BEGIN Split[key, level]; Find[key, level, Insert1]; END;

END;

-- compares two keys for ordering

Lower: INTERNAL PROCEDURE [a, b: KeyPtr] RETURNS [BOOLEAN] =

BEGIN

x: POINTER TO ARRAY [0..SIZE[File.ID]) OF CARDINAL = LOOPHOLE[@a.fileID];

y: POINTER TO ARRAY [0..SIZE[File.ID]) OF CARDINAL = LOOPHOLE[@b.fileID];

i: [0..SIZE[File.ID]);

FOR i IN [0..SIZE[File.ID]) DO

SELECT TRUE FROM

(x[i] < y[i]) => RETURN[TRUE];

(x[i] > y[i]) => RETURN[FALSE];

ENDCASE;-- if equal keep checking

ENDLOOP;

RETURN[a.filePage < b.filePage OR b↑=maxKey];-- maxKey < maxKey, to close key space

END;

-- tries to merge page of oldInterval with next page at same level or with root

-- cannot merge last page of any level except rootLevel

Merge: INTERNAL PROCEDURE [key: KeyPtr, level: Level]=

BEGIN

mergeFlag: BOOLEAN;

leftInterval, rightInterval: Interval;

Merge1: INTERNAL FindProc =

BEGIN

Merge2: INTERNAL XtraProc =

BEGIN

xtraBufferUsed: INTEGER ← xtraBuffer.used;-- used to solve stack modeling error

IF level=volumeHandle.treeLevel-1 THEN xtraBuffer.used ← 0;--clear now instead of deleteing later

IF (mergeFlag ← (buffer.used+xtraBuffer.used < SIZE[Buffer])) THEN --is merging possible

BEGIN--merge pages

Inline.LongCOPY[buffer, buffer.used, xtraBuffer + xtraBufferUsed];--merge buffer with xtra

xtraBuffer.used ← xtraBuffer.used + buffer.used;

-- buffer.used remains to prevent Find from attempting a merge

--interval.volumePage ← ??Interval.volumePage;----update cache with new page for deleted contents

END

ELSE

BEGIN--balance pages simply to provide hysteresis against futil merge attempts

WHILE low.ptr < (buffer.used-xtraBuffer.used)/2 DO ReadNext[]; ENDLOOP;--find middle

Inline.LongCOPY[buffer, low.ptr, xtraBuffer + xtraBufferUsed];--move first of buffer to xtra

Inline.LongCOPY[buffer+low.ptr, buffer.used-low.ptr, buffer];--slide down the rest of buffer

xtraBuffer.used ← xtraBuffer.used + low.ptr;

buffer.used ← buffer.used - low.ptr;--use low to insert while it is still valid

rightInterval.key ← low.key;

END;

rightInterval ← interval;

Xtra[leftInterval.volumePage, Merge2];

END;

leftInterval ← Get[key, level+1];-- so as to get a valid volumePage

Find[@leftInterval.nextKey, level, Merge1];--beware the merging

Delete[@leftInterval.nextKey, level+1];

IF mergeFlag THEN FreeVPage[rightInterval.volumePage]

ELSE Insert[@rightInterval.key, rightInterval.volumePage, level+1];-- insert new index;

END;

-- compresses item in the context of low

-- Note the side effect on low but not on high ! !

-- no compression is implemented in this version, but useful one would include:

-- front compression (especially to shrink page groups back to 2 fields)

PutNext: INTERNAL PROCEDURE [key: KeyPtr, volumePage: PageNumber, level: Level] =

BEGIN -- merge page groups when possible

old ← low;

low ← (LOOPHOLE[buffer+low.ptr, LONG POINTER TO Index]↑ ← Index[key↑, volumePage, SIZE[Index]]);--.ptr is just an increment

low.ptr ← low.ptr + old.ptr;--low.ptr was just an increment

volumeHandle.interval[level] ← Interval[old.key, low.volumePage, low.key];-- keep cache up to date in the face of changes

END;

-- decompresses item at high to become low & bumps high

-- Note the side effect on low and high ! !

-- no compression is implemented in this version

ReadNext: INTERNAL PROCEDURE =

BEGIN

IF high.ptr > buffer.used THEN ERROR;

old ← low;

low ← high;

high ← (IF high.ptr < buffer.used

THEN LOOPHOLE[buffer+high.ptr, LONG POINTER TO Index]↑

ELSE Index[maxKey, nullVolumePage, 0]);

high.ptr ← high.ptr + low.ptr;--high.ptr was just an increment

END;

-- moves half of buffer (or root) to xtraBuffer, creating new page of tree

Split: INTERNAL PROCEDURE [key: KeyPtr, level: Level] =

BEGIN

keyStone: Key;-- half way mark

page: PageNumber ← CreateVPage[];

Split1: INTERNAL FindProc =

BEGIN

Split2: INTERNAL XtraProc=

BEGIN

high ← Index[interval.key, nullVolumePage, 0];-- quick readReset

UNTIL high.ptr > buffer.used/2 DO ReadNext[]; ENDLOOP;

Inline.LongCOPY[buffer+low.ptr, (xtraBuffer.used ← buffer.used-low.ptr), xtraBuffer];--split

buffer.used ← low.ptr;

--volume.interval[level+1].nextKey ← low.key;---- interval of buffer is smaller (must keep high key above right)????

keyStone ← low.key;

END;

Xtra[page, Split2];

END;

Find[key, level, Split1];

Insert[@keyStone, page, level+1];

END;

Xtra: INTERNAL PROCEDURE [page: LogicalVolume.PageNumber, proc: XtraProc] =

-- maps, operates, unmaps xtraBuffer

BEGIN

SimpleSpace.Map[xtraHandle, [[LogicalVolume.Vfm[volumeHandle], FileInternal.maxPermissions], page], FALSE];

proc[];

SimpleSpace.Unmap[xtraHandle];

END;

END.

LOG

Log trimmed to Teak

Time: March 7, 1980 7:53 PMBy: ForrestAction: Moved in GetNextFile; deleted Handle from Close. Named the error in Delete.

Time: July 25, 1980 2:42 PMBy: LuniewskiAction: Deleted use of SpecialVolume.

Time: September 17, 1980 5:15 PMBy: LuniewskiAction: Modified GetNextFile.GetNextFileProc to return a BOOLEAN value as required by VolumeAccess.