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