-- Transport Mechanism Filestore - heap restart --
-- [Indigo]<Grapevine>MS>HeapRestart.mesa
-- Andrew Birrell September 9, 1982 3:25 pm --
DIRECTORY
BitMapDefs USING [Create, MapIndex, Set],
HeapFile, -- Beware of re-compilation constraints --
Inline USING[ COPY ],
ObjectDir, -- Beware of re-compilation constraints --
HeapDefs USING[ ObjectOffset, objectStart ],
HeapXDefs USING[ PageHeader, ObjectHeader ],
LogDefs USING[ WriteLine, WriteLogEntry ],
ObjectDirDefs--EXPORT only--,
ObjectDirXDefs USING[ ObjectNumber, gapObjectNumber ],
Storage USING[ Node ],
VMDefs USING[ CantOpen, DestroyFile, FileHandle, FullAddress, GetFileLength, MarkStart,
OpenFile, Page, PageAddress,
PageIndex, PageNumber, pageSize, ReadPage,
Release, SetFileLength, UsePage, WaitFile ];
HeapRestart: MONITOR RETURNS [ initHeap: BOOLEAN ]
LOCKS ObjectDir.LOCK --for RestartObject--
IMPORTS BitMapDefs, HeapFile, Inline, LogDefs, ObjectDir, Storage, VMDefs
EXPORTS ObjectDirDefs --RestartObject--, HeapDefs --HeapRestart--
SHARES HeapFile, ObjectDir, ObjectDirDefs =
BEGIN
-- Opens files concerned with heap:
-- "Heap.ObjectDir" The object directory; initialised on every restart
-- and extended dynamically as needed during run.
-- "Heap.Data" The file containing the heap objects is considered
-- as a sequence of separate segments, numbered
-- [FIRST[HeapFile.Segment]..LAST[HeapFile.Segment]]
-- These segments are of equal size. Heap.Data should
-- be pre-allocated on consecutive pages of physical
-- disk.
-- "Heap.Segments" Ordering for segments of Heap.Data; two pages only. If
-- this file is size 0 on entry, then 'initHeap' is set
-- to TRUE and all files are initialised to a state
-- corresponding to there being no message bodies.
-- The object directory and ancillary variables are set to correspond to
-- the heap objects found to exist in the heap file, read in the
-- order given by "Heap.Chain", with their reference counts set to zero
-- pending restart of steering list queues and mailboxes. After restart of
-- steering list queues and mailboxes, the Compactor should be STARTed, and
-- will then run as an asynchronous activity.
RestartObject: PUBLIC ENTRY PROCEDURE[ obj: ObjectDirXDefs.ObjectNumber ] =
BEGIN -- executes inside the ObjectDir monitor --
OPEN ObjectDir;
either: POINTER TO DirData = FindData[obj];
WITH data: either SELECT FROM
used => BEGIN
IF data.count = LAST[ObjectCount] THEN ERROR ObjectCountTooBig;
data.count ← data.count + 1;
END;
ENDCASE => ERROR ObjectNotInUse[];
ReleaseData[dirty];
END;
BadChainSize: ERROR = CODE;
NoWrittenHeapSegment: ERROR = CODE;
InitialisingHeap: SIGNAL = CODE; -- resume if you really mean it!--
HeapDataTooSmall: ERROR = CODE;
ReadChain: PROCEDURE =
BEGIN
OPEN HeapFile, client;
chainPages: CARDINAL;
handle ← VMDefs.OpenFile[options: old,
name: "Heap.Data"L, cacheFraction: 40];
IF VMDefs.GetFileLength[handle].page = 0 THEN ERROR HeapDataTooSmall[];
segmentCount ← VMDefs.GetFileLength[handle].page / segmentSize;
chainPages ← (segmentCount+segmentsPerPage-1) / segmentsPerPage;
segmentCeiling ← segmentCount + chainPages*headerSize - 1;
chainHandle ← VMDefs.OpenFile[
options: oldOrNew, name: "Heap.Segments"L, cacheFraction: 0];
chain ← Storage.Node[(segmentCeiling+1)*SIZE[SegmentIndex]];
TranslateOldFormat[chainPages];
IF VMDefs.GetFileLength[chainHandle].page = 0
THEN BEGIN
SIGNAL InitialisingHeap[];
InitChain[chainPages]; InitData[];
END
ELSE BEGIN
initHeap ← FALSE;
IF VMDefs.GetFileLength[chainHandle].page # chainPages*2
THEN ERROR BadChainSize;
FOR page: CARDINAL IN [0..chainPages)
DO seg: SegmentIndex = page*VMDefs.pageSize;
chain0: POINTER TO SerialAndHead
= LOOPHOLE[VMDefs.ReadPage[[chainHandle, page*2], 3]];
chain1: POINTER TO SerialAndHead
= LOOPHOLE[VMDefs.ReadPage[[chainHandle, page*2+1], 3]];
from: POINTER TO SerialAndHead =
IF chain1.serialNumber > chain0.serialNumber
THEN chain1
ELSE chain0;
Inline.COPY[from: from, to: @chain.header[page],
nwords: MIN[1+segmentCeiling-seg, VMDefs.pageSize] ];
VMDefs.Release[LOOPHOLE[chain0]];
VMDefs.Release[LOOPHOLE[chain1]];
ENDLOOP;
END;
IF chain.header[0].chainHead = noSegment THEN ERROR NoWrittenHeapSegment[];
InitFreeMap[chainPages];
END;
InitChain: PROCEDURE[chainPages: CARDINAL] =
BEGIN OPEN HeapFile, client;
initHeap ← TRUE;
LogDefs.WriteLogEntry["Initialising Heap.segments"L];
LogDefs.WriteLine["Initialising Heap.segments"L];
VMDefs.SetFileLength[chainHandle, [chainPages*2, 0]];
FOR index: CARDINAL IN [0..chainPages)
DO chain.header[index].serialNumber ← 0;
IF index = 0 -- set up one-page written list --
THEN { chain.header[index].chainHead ← headerSize;
chain.next[headerSize] ← noSegment };
RecordAllocation[index*VMDefs.pageSize];
RecordAllocation[index*VMDefs.pageSize];
ENDLOOP;
END;
InitData: PROCEDURE =
BEGIN OPEN HeapFile, client;
LogDefs.WriteLogEntry["Initialising Heap.data"L];
LogDefs.WriteLine["Initialising Heap.data"L];
FOR page: VMDefs.PageNumber DECREASING IN [0..VMDefs.GetFileLength[handle].page)
DO EmptyPage[ [handle, page] ] ENDLOOP;
VMDefs.WaitFile[handle];
END;
InitFreeMap: PROCEDURE[chainPages: CARDINAL] =
BEGIN OPEN HeapFile, client;
freeCount ← segmentCount;
freeMap ← BitMapDefs.Create[segmentCeiling+1];
FOR index: CARDINAL IN [0..chainPages) DO
-- make nonexistent seg indices look 'busy'
firstBit: BitMapDefs.MapIndex = index * VMDefs.pageSize;
FOR j: CARDINAL IN [0..headerSize) DO
BitMapDefs.Set[freeMap, firstBit+j] ENDLOOP;
ENDLOOP;
FOR s: CARDINAL ← chain.header[0].chainHead, chain.next[s]
UNTIL s = noSegment DO
BitMapDefs.Set[freeMap, s]; freeCount ← freeCount - 1;
ENDLOOP;
NotifyFreeCount[];
END;
HardLuck: ERROR = CODE; -- incorrect old segment size --
TranslateOldFormat: PROC[chainPages: CARDINAL] =
BEGIN
-- Translate from Heap.chain (fixed segment size) format to new (6 page) format --
NewSeg: PROC[oldSeg: SegmentPtr] RETURNS[HeapFile.SegmentIndex] =
{ RETURN[ HeapFile.Segment[oldSeg * oldSize] ] };
Succ: PROC[a: HeapFile.SegmentIndex] RETURNS[HeapFile.SegmentIndex] =
{ RETURN[ IF (a+1) MOD VMDefs.pageSize < HeapFile.headerSize
THEN a + HeapFile.headerSize+1 ELSE a+1] };
segmentCount: CARDINAL = 200;
Segment: TYPE = [0..segmentCount);
SegmentPtr: TYPE = [ FIRST[Segment] .. 1+LAST[Segment] ];
noSegment: SegmentPtr = LAST[SegmentPtr];
PageType: TYPE = RECORD[
written: ARRAY[0..0]OF SegmentPtr --for alignment--,
free: ARRAY[0..0]OF SegmentPtr --for alignment--,
ser: LONG INTEGER,
next: ARRAY Segment OF SegmentPtr];
oldFile: VMDefs.FileHandle = VMDefs.OpenFile[
options: old, name: "Heap.chain"L, cacheFraction: 0 ! VMDefs.CantOpen =>
IF reason = notFound THEN GOTO newOnly];
oldSize: CARDINAL =
VMDefs.GetFileLength[HeapFile.client.handle].page / segmentCount;
page0: POINTER TO PageType = LOOPHOLE[VMDefs.ReadPage[[oldFile,0],0]];
page1: POINTER TO PageType = LOOPHOLE[VMDefs.ReadPage[[oldFile,1],0]];
page: POINTER TO PageType = IF page0.ser > page1.ser THEN page0 ELSE page1;
IF VMDefs.GetFileLength[oldFile].page # 2 THEN ERROR;
IF oldSize # HeapFile.segmentSize * 4 THEN ERROR HardLuck[];
InitChain[chainPages];
BEGIN
prev: HeapFile.SegmentIndex ←
HeapFile.client.chain.header[0].chainHead ← NewSeg[page.written[0]];
THROUGH [1..3]
DO HeapFile.client.chain.next[prev] ← Succ[prev];
prev ← HeapFile.client.chain.next[prev];
ENDLOOP;
FOR oldSeg: SegmentPtr ← page.next[page.written[0]], page.next[oldSeg]
UNTIL oldSeg = noSegment
DO new: HeapFile.SegmentIndex = NewSeg[oldSeg];
HeapFile.client.chain.next[prev] ← new; prev ← new;
THROUGH [1..3]
DO HeapFile.client.chain.next[prev] ← Succ[prev];
prev ← HeapFile.client.chain.next[prev];
ENDLOOP;
ENDLOOP;
HeapFile.client.chain.next[prev] ← HeapFile.noSegment;
END;
FOR index: CARDINAL IN [0..chainPages)
DO HeapFile.RecordAllocation[index*VMDefs.pageSize] ENDLOOP;
VMDefs.Release[LOOPHOLE[page0]];
VMDefs.Release[LOOPHOLE[page1]];
FOR index: VMDefs.PageNumber
IN [segmentCount*oldSize..
VMDefs.GetFileLength[HeapFile.client.handle].page)
DO EmptyPage[[HeapFile.client.handle, index]] ENDLOOP;
VMDefs.DestroyFile[oldFile];
EXITS newOnly => NULL;
END;
EmptyPage: PROCEDURE[ where: VMDefs.PageAddress ] =
BEGIN
OPEN VMDefs, HeapXDefs;
page: Page = ReadPage[where,6]; -- faster than UsePage --
header: POINTER TO PageHeader = LOOPHOLE[page,POINTER]+FIRST[PageIndex];
obj: POINTER TO ObjectHeader =
LOOPHOLE[page,POINTER]+FIRST[PageIndex]+SIZE[PageHeader];
header.offset ← HeapDefs.objectStart;
obj.number ← ObjectDirXDefs.gapObjectNumber;
obj.size ← 1+LAST[PageIndex]-
(FIRST[PageIndex]+SIZE[PageHeader]+SIZE[ObjectHeader]);
MarkStart[page];
Release[page];
END;
InitObjectDir: ENTRY PROCEDURE =
BEGIN -- after InitHeapFile, to get HeapFile.handle --
OPEN ObjectDir;
handle ← VMDefs.OpenFile[options:oldOrNew,
name: "Heap.ObjectDir", cacheFraction: 10];
ObjectDir.heapHandle ← HeapFile.client.handle;
nextVirginPage ← VMDefs.GetFileLength[handle].page;
IF nextVirginPage = FIRST[VMDefs.PageNumber]
THEN nextVirginPage ← nextVirginPage+1;
-- initialize each page with unchained "free" indexes,
-- and put each page on free page chain.
firstFreePage ← endOfChain;
FOR reqd: VMDefs.PageNumber IN [ 0 .. nextVirginPage )
DO IF dpPage # NIL THEN VMDefs.Release[LOOPHOLE[dpPage,VMDefs.Page]];
dpPage ← LOOPHOLE[VMDefs.UsePage[[handle,dpNumber←reqd]]];
FOR index: DirIndex IN DirIndex
DO dpPage.data[index] ← [free[next:0,dopc:0]] ENDLOOP;
dpPage.header ←
[nextFreePage: unchained,
nextFreeIndex: noFreeIndex];
VMDefs.MarkStart[LOOPHOLE[dpPage,VMDefs.Page]];--may cause file extension for page 0--
ReleaseData[dirty];
ENDLOOP;
END;
ReadSegments: PROCEDURE =
BEGIN
OPEN HeapFile, client;
page: VMDefs.Page;
usedSegment: SegmentIndex ← lastChained ← chain.header[0].chainHead;
pos: VMDefs.FullAddress ← Address[lastChained];
usedPos: VMDefs.FullAddress ← pos;
offset: HeapDefs.ObjectOffset;
current: ObjectDirXDefs.ObjectNumber ← ObjectDirXDefs.gapObjectNumber;
DefineObject: ENTRY PROCEDURE[ obj: ObjectDirXDefs.ObjectNumber ] =
BEGIN
OPEN ObjectDir;
data: POINTER TO DirData = FindData[obj];
data↑ ← [used[page: pos.page.page,
word: pos.word,
type: obj.type,
count: zeroCount ] ];
ReleaseData[dirty];
END;
DefineObject[ObjectDirXDefs.gapObjectNumber];
DO -- Consider any page header --
IF pos.word = FIRST[VMDefs.PageIndex]
THEN BEGIN
pageHead: POINTER TO HeapXDefs.PageHeader;
page ← VMDefs.ReadPage[pos.page,2];
pageHead ← LOOPHOLE[page,POINTER]+pos.word;
pos.word ← pos.word+SIZE[HeapXDefs.PageHeader];
offset ← pageHead.offset;
END
ELSE offset ← HeapDefs.objectStart;
BEGIN
object: POINTER TO HeapXDefs.ObjectHeader =
LOOPHOLE[page,POINTER]+pos.word;
-- check for non-empty segment --
IF object.number # ObjectDirXDefs.gapObjectNumber
THEN BEGIN usedPos ← pos; usedSegment ← lastChained; END;
IF ( current # ObjectDirXDefs.gapObjectNumber
--Inside an object, looking for continuation sub-object--
-- If a duplicate start is found for an object, then the
-- later start is chosen, so that all earlier starts are
-- overwritten before the object number is freed by the
-- compactor. Otherwise, confusion could arise by the
-- object number being re-used and a restart occuring
-- before the duplicate start has been overwritten.
AND object.number = current AND offset=HeapDefs.objectStart )
OR ( object.number # ObjectDirXDefs.gapObjectNumber
AND offset = HeapDefs.objectStart )
THEN BEGIN -- start of a new object --
DefineObject[object.number]; current←object.number;
END
-- ELSE we have one of:
-- continuation of ignorable object,
-- imbedded object which should be ignored,
-- unexpected partial object,
-- gap object --;
pos.word ← pos.word + SIZE[HeapXDefs.ObjectHeader];
pos.word ← pos.word + object.size;
END;
IF pos.word + SIZE[HeapXDefs.ObjectHeader] > LAST[VMDefs.PageIndex]
THEN BEGIN
VMDefs.Release[page];
-- similar to HeapFileDefs.NextPage, but different --
IF pos.page.page MOD segmentSize < segmentSize-1
THEN BEGIN
pos.page.page ← pos.page.page+1;
pos.word ← FIRST[VMDefs.PageIndex];
END
ELSE IF chain.next[lastChained] # noSegment
THEN BEGIN
old: SegmentIndex = lastChained;
pos ← Address[lastChained←chain.next[old]];
IF usedSegment # old
THEN BEGIN -- 'old' is entirely empty --
chain.next[usedSegment] ← lastChained;
AddToFreeList[old];
END
END
ELSE EXIT -- note "pos" is last page in chain.written--;
END
ELSE -- end of any current object --
current ← ObjectDirXDefs.gapObjectNumber;
ENDLOOP;
lastPage ← pos.page;
lastWritten ← lastChained;
END;
TidyObjectDir: ENTRY PROCEDURE =
-- Construct object directory page free chains --
-- Add pages with non-empty free chains to page free chain
BEGIN
OPEN ObjectDir;
FOR p: ObjDirPageNumber DECREASING IN [ 0 .. nextVirginPage )
DO GetDirPage[p];
dpPage.header.nextFreeIndex ← noFreeIndex;
FOR index: DirIndex IN DirIndex
DO WITH data: dpPage.data[index] SELECT FROM
free => BEGIN
dpPage.data[index] ←
[free[ next: dpPage.header.nextFreeIndex,
dopc: lastDofpc ]];
dpPage.header.nextFreeIndex ← index;
END;
ENDCASE => NULL;
ENDLOOP;
IF dpPage.header.nextFreeIndex # noFreeIndex
THEN{ dpPage.header.nextFreePage ← firstFreePage;
firstFreePage ← dpNumber };
ReleaseData[dirty];
ENDLOOP;
END;
Go: PROCEDURE =
BEGIN
LogDefs.WriteLine["Restarting heap storage"L];
START HeapFile; ReadChain[];
START ObjectDir; InitObjectDir[];
ReadSegments[]; TidyObjectDir[];
END;
Go[];
END.