-- Copyright (C) 1981, 1984, 1985 by Xerox Corporation. All rights reserved.
-- Compactor.mesa, Transport Mechanism Filestore - heap compactor
-- HGM, 21-May-85 23:54:56
-- Randy Gobbel 19-May-81 13:24:41 --
-- Andrew Birrell 3-Jun-81 13:00:58 --
DIRECTORY
HeapDefs USING [Buffer, HeapReadData, objectStart, ReaderHandle],
HeapFileDefs USING [
FirstSegment, InsertFirstSegment, NextPage, NoMorePages, FreeSegment],
HeapXDefs USING [
PageHeader, ObjectHeader, ReaderData, StopAllReaders, RestartAllReaders],
LogDefs USING [ShowLine],
ObjectDirXDefs USING [
DOPC, ObjectNumber, gapObjectNumber, GetObjectState, MoveObject, ReportDofpc],
PolicyDefs USING [CompactorPause, CompactorStart],
Process USING [DisableTimeout, InitializeCondition, InitializeMonitor],
Storage USING [Node],
String USING [AppendLongDecimal, AppendString],
System USING [GetGreenwichMeanTime, GreenwichMeanTime],
VMDefs USING [
Deactivate, Page, PageIndex, ReadPage, MarkStartWait, UsePage, PageNumber,
PageAddress, FullAddress];
Compactor: PROGRAM
IMPORTS
HeapDefs, HeapFileDefs, HeapXDefs, LogDefs, ObjectDirXDefs, PolicyDefs, Process,
String, Storage, System, VMDefs
EXPORTS HeapDefs --Compactor-- =
BEGIN
OPEN HeapXDefs, ObjectDirXDefs;
Allocate: PROCEDURE [CARDINAL] RETURNS [POINTER] = Storage.Node;
-- Current state --
wPos: VMDefs.FullAddress;
wPage: VMDefs.Page;
flushedBefore: VMDefs.FullAddress;
reader: HeapXDefs.ReaderData;
readerHandle: HeapDefs.ReaderHandle = LOOPHOLE[@reader];
object: POINTER TO ObjectHeader;
dorpc: ObjectDirXDefs.DOPC ← 0; --see comments in ObjectDirXDefs
-- record of objects moved by compactor --
ObjRec: TYPE = RECORD [
obj: ObjectNumber, where: VMDefs.FullAddress, next: ObjPtr];
ObjPtr: TYPE = POINTER TO ObjRec;
endObj: ObjPtr = NIL;
freeChain: ObjPtr ← endObj;
moveChain: ObjPtr ← endObj;
freeCount: CARDINAL ← 0;
-- Statistics
freed, copied, firstGap: LONG CARDINAL;
startTime: System.GreenwichMeanTime;
waitSeconds, pauseSeconds: LONG CARDINAL;
GetObjRec: PROCEDURE [chain: POINTER TO ObjPtr] RETURNS [ptr: ObjPtr] = INLINE
BEGIN
IF freeChain = endObj THEN ptr ← Allocate[SIZE[ObjRec]]
ELSE {ptr ← freeChain; freeChain ← freeChain.next; freeCount ← freeCount - 1};
ptr.next ← chain↑;
chain↑ ← ptr;
END;
FreeObjRec: PROC [ptr: ObjPtr] = INLINE
BEGIN ptr.next ← freeChain; freeChain ← ptr; freeCount ← freeCount + 1; END;
Start: PROCEDURE =
BEGIN -- called before each compaction --
LogDefs.ShowLine["Compactor starting..."];
waitSeconds ← (System.GetGreenwichMeanTime[]-startTime);
startTime ← System.GetGreenwichMeanTime[];
freed ← copied ← 0;
firstGap ← LAST[LONG CARDINAL];
pauseSeconds ← 0;
reader.where ← HeapFileDefs.FirstSegment[];
reader.page ← VMDefs.ReadPage[reader.where.page, 0];
dorpc ← dorpc + 1;
reader.offset ← HeapDefs.objectStart;
reader.object ← ObjectDirXDefs.gapObjectNumber;
wPos ← HeapFileDefs.InsertFirstSegment[];
wPage ← NIL -- set later by SetHeader -- ;
flushedBefore ← wPos;
Flush[];
END;
Finish: PROCEDURE =
BEGIN
temp: STRING = [300];
runTime: LONG CARDINAL ← (System.GetGreenwichMeanTime[]-startTime);
startTime ← System.GetGreenwichMeanTime[];
String.AppendString[temp, "Compactor: Waited "L];
String.AppendLongDecimal[temp, waitSeconds];
String.AppendString[temp, ", ran "L];
String.AppendLongDecimal[temp, runTime];
String.AppendString[temp, ", paused "L];
String.AppendLongDecimal[temp, pauseSeconds];
String.AppendString[temp, " seconds. Reclaimed "L];
String.AppendLongDecimal[temp, freed];
String.AppendString[temp, " segments. Copied "L];
String.AppendLongDecimal[temp, copied];
String.AppendString[temp, " pages. First gap was at page "L];
String.AppendLongDecimal[temp, firstGap];
String.AppendString[temp, "."L];
LogDefs.ShowLine[temp];
END;
FindObject: PROCEDURE =
BEGIN -- skips until non-ignorable object --
-- If no more objects exist, HeapFileDefs.NextPage generates a signal. --
-- This should be caught by the caller of FindObject --
OPEN VMDefs;
reader.object ← gapObjectNumber --indicates "no current object"-- ;
reader.end ← FALSE;
DO -- Consider any page header --
IF reader.where.word = FIRST[PageIndex] THEN
BEGIN
pageHead: POINTER TO PageHeader =
LOOPHOLE[reader.page, POINTER] + reader.where.word;
reader.where.word ← reader.where.word + SIZE[PageHeader];
reader.offset ← pageHead.offset;
END
ELSE reader.offset ← HeapDefs.objectStart;
BEGIN -- read sub-object header --
object: POINTER TO ObjectHeader =
LOOPHOLE[reader.page, POINTER] + reader.where.word;
IF
(reader.object # gapObjectNumber
-- Inside an object, looking for continuation sub-object --
-- If a duplicate start is found, it may be non-ignorable --
AND object.number = reader.object
AND reader.offset = HeapDefs.objectStart)
OR
(object.number # gapObjectNumber
AND reader.offset = HeapDefs.objectStart) THEN
BEGIN -- start of a new object --
SELECT GetObjectState[object.number, reader.where, dorpc] FROM
inUse =>
BEGIN
ptr: ObjPtr = GetObjRec[@moveChain];
ptr.where ← wPos;
ptr.obj ← reader.object ← object.number;
EXIT
END;
unused => -- ignorable object, marked as deleted by ObjectDir --
NULL;
duplicate => NULL; -- ignorable object --
ENDCASE => ERROR;
reader.object ← object.number --now the current object-- ;
END
-- ELSE we have one of:
-- continuation of ignorable object,
-- imbedded object which should be ignored,
-- unexpected partial object,
-- gap object -- ;
reader.where.word ← reader.where.word + SIZE[ObjectHeader];
reader.where.word ← reader.where.word + object.size;
END;
-- check for end of page --
IF reader.where.word + SIZE[ObjectHeader] > LAST[PageIndex] THEN
BEGIN
start: System.GreenwichMeanTime ← System.GetGreenwichMeanTime[];
Deactivate[reader.page]; -- not "Release", for better cache -
PolicyDefs.CompactorPause[];
pauseSeconds ← pauseSeconds + (System.GetGreenwichMeanTime[]-start);
reader.where ← HeapFileDefs.NextPage[reader.where];
-- That may have generated a signal, terminating FindObject --
-- Note that there is no current page here. --
reader.page ← ReadPage[reader.where.page, 0];
dorpc ← dorpc + 1;
END
ELSE -- end of any current object --
reader.object ← gapObjectNumber;
ENDLOOP;
--the interlock with the readers occurs in TerminatePage --
END;
Flush: PROCEDURE =
BEGIN --write empty pages upto, but excluding, 'limit' --
WHILE flushedBefore.page.page # reader.where.page.page DO
EmptyPage[flushedBefore.page];
flushedBefore ← HeapFileDefs.NextPage[flushedBefore]
ENDLOOP;
ObjectDirXDefs.ReportDofpc[dorpc - 1];
END;
EmptyPage: PROCEDURE [where: VMDefs.PageAddress] =
BEGIN OPEN VMDefs;
page: Page = UsePage[where];
header: POINTER TO PageHeader = LOOPHOLE[page];
obj: POINTER TO ObjectHeader = LOOPHOLE[page, POINTER] + SIZE[PageHeader];
header.offset ← HeapDefs.objectStart;
obj.number ← ObjectDirXDefs.gapObjectNumber;
obj.size ← 1 + LAST[PageIndex] - (SIZE[PageHeader] + SIZE[ObjectHeader]);
MarkStartWait[page];
Deactivate[page];
END;
SetHeader: PROCEDURE [number: ObjectDirXDefs.ObjectNumber] =
BEGIN
-- Write page header, if needed --
IF wPos.word = FIRST[VMDefs.PageIndex] THEN
BEGIN
wPage ← VMDefs.UsePage[wPos.page];
BEGIN
header: POINTER TO PageHeader = LOOPHOLE[wPage, POINTER] + wPos.word;
header.offset ← reader.offset;
wPos.word ← wPos.word + SIZE[PageHeader];
END;
END;
-- Write object or sub-object header --
object ← LOOPHOLE[wPage, POINTER] + wPos.word;
wPos.word ← wPos.word + SIZE[ObjectHeader];
object.number ← number;
object.size ← 0;
END;
TerminatePage: PROCEDURE [current: ObjectDirXDefs.ObjectNumber] =
BEGIN --write wPage to disk and update object directory and free files--
VMDefs.MarkStartWait[wPage];
copied ← copied + 1;
VMDefs.Deactivate[wPage];
-- altering object directory is now ok, even although old copies of --
-- the objects in wPage still exist on other pages --
WHILE moveChain # endObj DO
BEGIN
ptr: ObjPtr = moveChain;
moveChain ← moveChain.next;
ObjectDirXDefs.MoveObject[ptr.obj, ptr.where];
--ensure the readers are not confused --
HeapXDefs.RestartAllReaders[ptr.obj];
FreeObjRec[ptr];
END;
ENDLOOP;
PolicyDefs.CompactorPause[];
HeapXDefs.StopAllReaders[stoppedObj ← current];
Flush[];
wPos ← HeapFileDefs.NextPage[wPos];
freed ← freed + HeapFileDefs.FreeSegment[wPos, reader.where];
-- leaves readers for "current" stopped --
IF freed # 0 THEN firstGap ← MIN[firstGap, copied-1];
END;
stoppedObj: ObjectDirXDefs.ObjectNumber ← ObjectDirXDefs.gapObjectNumber;
RestartStoppedObj: PROCEDURE =
BEGIN
IF stoppedObj # ObjectDirXDefs.gapObjectNumber THEN
HeapXDefs.RestartAllReaders[stoppedObj];
stoppedObj ← ObjectDirXDefs.gapObjectNumber;
END;
BufferNotFilled: ERROR = CODE;
ObjectNotDestroyed: ERROR = CODE;
RunCompactor: PROCEDURE =
BEGIN
startTime ← System.GetGreenwichMeanTime[];
-- Never returns --
DO
PolicyDefs.CompactorStart[];
Start[];
DO
FindObject[ ! HeapFileDefs.NoMorePages => EXIT];
BEGIN
objectEnded: BOOLEAN ← FALSE;
objectStartPage: VMDefs.PageNumber = reader.where.page.page;
SetHeader[reader.object];
UNTIL objectEnded DO -- copy data into wPage --
BEGIN
buffer: HeapDefs.Buffer;
buffer ← [wPage + wPos.word, 1 + LAST[VMDefs.PageIndex] - wPos.word];
[objectEnded, object.size] ← HeapDefs.HeapReadData[
readerHandle, buffer];
-- always 'objectEnded' and/or object.size=buffer.length --
wPos.word ← wPos.word + object.size;
END;
-- move to new page, if needed, even if objectEnded --
IF wPos.word + SIZE[ObjectHeader] > LAST[VMDefs.PageIndex] THEN
BEGIN
RestartStoppedObj[];
TerminatePage[reader.object];
SetHeader[reader.object];
END
ELSE IF NOT objectEnded THEN ERROR BufferNotFilled[];
ENDLOOP --for each object-- ;
RestartStoppedObj[];
IF reader.where.page.page # objectStartPage THEN -- HeapReadData moved us beyond last deleted object page --
dorpc ← dorpc + 1;
END;
ENDLOOP --end of last object-- ;
--pad last page with gap, and write to disk--
SetHeader[ObjectDirXDefs.gapObjectNumber];
object.size ← 1 + LAST[VMDefs.PageIndex] - wPos.word;
TerminatePage[ObjectDirXDefs.gapObjectNumber];
RestartStoppedObj[];
EmptyPage[reader.where.page];
ObjectDirXDefs.ReportDofpc[dorpc]; -- everything has been flushed --
Finish[];
ENDLOOP -- eternal loop of compactions -- ;
END --Compact-- ;
-- Main Program --
Process.InitializeMonitor[@reader.LOCK];
Process.InitializeCondition[@reader.canStart, 0];
Process.DisableTimeout[@reader.canStart];
reader.stopped ← FALSE;
RunCompactor[];
END.