-- Transport Mechanism Filestore - object directory --

-- [Juniper]<Grapevine>MS>ObjectDir.mesa

-- Andrew Birrell  10-Jun-81 10:46:42 --
-- M. D. Schroeder   7-Feb-83 15:34:06 --

DIRECTORY
HeapFileDefs	USING[ ObjectAbandoned ],
ObjectDirXDefs	USING[ DOPC, ObjectNumber, ObjectState ],
ObjectDirDefs	USING[ noObject, ObjectType ],
PolicyDefs	USING[ GapExists ],
VMDefs		USING[ Page, pageSize, PageNumber, FileHandle, PageIndex,
                       ReadPage, UsePage, Mark, MarkStart, Release,
                       FullAddress ];

ObjectDir: MONITOR
   IMPORTS HeapFileDefs, PolicyDefs, VMDefs
   EXPORTS ObjectDirDefs, ObjectDirXDefs
   SHARES  ObjectDirDefs =
BEGIN


-- Reference counts --

ObjectCount: TYPE = CARDINAL;

zeroCount: ObjectCount = 0;
oneCount:  ObjectCount = zeroCount+1;


-- Structure of object directory pages --

handle: VMDefs.FileHandle; -- set by HeapRestart --

-- Object directory is sequence of pages, each of type "DirPage"
-- Pages containing unused indexes are on "firstFreePage" chain
-- Unused indexes within page are in header.nextFreeIndex chain
-- Unused indexes are not usable until lastDofpc is high enough
-- See ObjectDirDefs comments about DOPC.
-- There may be pages on "firstFreePage" chain having no free indexes

-- Object directory page numbers (and markers) fit into 8 bits!

ObjDirPageSpace: TYPE = [0..255];
unchained: ObjDirPageSpace = LAST[ObjDirPageSpace];-- "not on free chain"
endOfChain:ObjDirPageSpace = PRED[unchained];-- "end of free chain"
ObjDirPageNumber: TYPE = [FIRST[ObjDirPageSpace]..PRED[endOfChain]];

DirData: TYPE = RECORD[ SELECT freedom: * --w0,b15-- FROM
      free => [ next:  VMDefs.PageIndex,--w0,b[7..0]--
                dopc:  ObjectDirXDefs.DOPC --w[1..2]-- ],
      used => [ type:  ObjectDirDefs.ObjectType,--w0,b[14..11]--
                word:  VMDefs.PageIndex,--w0,b[7..0]--
                page:  VMDefs.PageNumber,--w1--
                count: ObjectCount --w2-- ],
      ENDCASE];

DirPageHeader: TYPE = RECORD[ nextFreePage: ObjDirPageSpace,
                              nextFreeIndex: VMDefs.PageIndex ];

entriesPerPage: CARDINAL =
                   (VMDefs.pageSize-SIZE[DirPageHeader])/SIZE[DirData];

DirIndex:       TYPE = [ 0 .. entriesPerPage );
-- NOTE: DirIndex values must fit in the "index" field of an object number --

DirPage:        TYPE = RECORD[ header: DirPageHeader,
                               data: ARRAY DirIndex OF DirData ];

noFreeIndex: [0..LAST[VMDefs.PageIndex]] = SUCC[LAST[DirIndex]];

firstFreePage: ObjDirPageSpace _ endOfChain; -- first page containing free numbers --
nextVirginPage: ObjDirPageSpace; -- current size of file --

dpNumber: ObjDirPageNumber;
dpPage:   POINTER TO DirPage _ NIL;

GetDirPage: INTERNAL PROCEDURE[ reqd: ObjDirPageNumber ] =
   BEGIN
   IF dpPage = NIL OR dpNumber # reqd
   THEN BEGIN
        IF dpPage # NIL THEN VMDefs.Release[LOOPHOLE[dpPage, VMDefs.Page]];
        dpPage _
           LOOPHOLE[VMDefs.ReadPage[[handle,dpNumber_reqd],0--lookAhead--],
                    POINTER TO DirPage];
        END;
   END;


-- Allocation of object numbers --

InitPage: PROCEDURE =
   BEGIN
   -- initialize current page as empty and chain onto firstFreePage --
   index: DirIndex;
   dpPage.header _ [nextFreePage:firstFreePage,
                    nextFreeIndex:FIRST[DirIndex]];
   firstFreePage _ dpNumber;
   FOR index IN DirIndex
   DO dpPage.data[index] _ [free[next:SUCC[index],dopc:lastDofpc]] ENDLOOP
   END;

BadFreeObjChain: ERROR = CODE;
ObjectDirectoryFull: ERROR = CODE;

NewObject: PUBLIC ENTRY PROCEDURE[ at: VMDefs.FullAddress,
                                   type: ObjectDirDefs.ObjectType ]
                          RETURNS[ obj: ObjectDirXDefs.ObjectNumber ] =
   BEGIN
   obj.page _ firstFreePage;
   DO --until we find a suitable page --
      IF obj.page = endOfChain
      THEN BEGIN -- allocate a new page by extending object dir file --
           obj.page _ nextVirginPage; nextVirginPage _ nextVirginPage+1;
           IF dpPage # NIL THEN VMDefs.Release[LOOPHOLE[dpPage,VMDefs.Page]];
           dpPage _ LOOPHOLE[VMDefs.UsePage[[handle,dpNumber_obj.page]],
                             POINTER TO DirPage];
           InitPage[] -- puts it on firstFreePage list --;
           VMDefs.MarkStart[LOOPHOLE[dpPage,VMDefs.Page]]; --to cause file extension--
           END
      ELSE GetDirPage[obj.page];
      IF obj.page > LAST[ObjDirPageNumber] THEN ERROR ObjectDirectoryFull[];
      IF dpPage.header.nextFreePage = unchained
      THEN ERROR BadFreeObjChain[];
      -- if page is empty and is start of free page list
      IF dpPage.header.nextFreeIndex = noFreeIndex
      AND obj.page = firstFreePage
      THEN BEGIN
           firstFreePage _ obj.page _ dpPage.header.nextFreePage;
           dpPage.header.nextFreePage _ unchained;
           ReleaseData[dirty];
           END
      ELSE BEGIN
         -- scan free chain on this page --
         prev: POINTER TO DirData _ NIL;
         possible: VMDefs.PageIndex _ dpPage.header.nextFreeIndex;
         UNTIL possible = noFreeIndex
         DO -- find re-usable object number on this page's free list --
            WITH data: dpPage.data[possible] SELECT FROM
              free => IF data.dopc <= lastDofpc
                      THEN BEGIN -- take it! --
                           obj.index _ possible;
                           IF prev = NIL
                           THEN dpPage.header.nextFreeIndex _ data.next
                           ELSE WITH prevData: prev SELECT FROM
                                  free => prevData.next _ data.next;
                                ENDCASE => ERROR;
                           GOTO found
                           END
                      ELSE BEGIN
                           prev _ @(dpPage.data[possible]);
                           possible _ data.next;
                           END;
            ENDCASE => ERROR BadFreeObjChain[];
         ENDLOOP;
         obj.page _ dpPage.header.nextFreePage;
         ReleaseData[clean];
      END;
   REPEAT
   found => NULL;
   ENDLOOP;
   dpPage.data[obj.index] _ [used[ page:  at.page.page,
                                   word:  at.word,
                                   type:  type,
                                   count: oneCount ]];
   ReleaseData[dirty];
   obj.fill _ 0; --to allow for expansion of type field--
   obj.type _ type;
   END;

CacheState: TYPE = { clean, dirty };

IllegalObjectNumber: ERROR = CODE;

FindData: INTERNAL PROCEDURE[ obj: ObjectDirXDefs.ObjectNumber ]
                     RETURNS[ data: POINTER TO DirData ] =
   BEGIN
   IF obj.index > LAST[DirIndex] THEN ERROR IllegalObjectNumber[];
   GetDirPage[ obj.page ];
   RETURN[ @(dpPage.data[obj.index]) ]
   END;

ReleaseData: INTERNAL PROCEDURE[ d: CacheState ] =
   BEGIN
   IF d=dirty THEN VMDefs.Mark[LOOPHOLE[dpPage,VMDefs.Page]];
   END;


-- Operations on individual object numbers --

ObjectWithZeroCount:  ERROR = CODE;
IllegalDestroyObject: ERROR = CODE;
ObjectNotInUse:       ERROR = CODE;
ObjectCountTooBig:    ERROR = CODE;

heapHandle: VMDefs.FileHandle; -- set by HeapRestart --

ObjectBase: PUBLIC ENTRY PROCEDURE[ obj: ObjectDirXDefs.ObjectNumber ]
                     RETURNS[ addr: VMDefs.FullAddress ] =
   BEGIN
   either: POINTER TO DirData = FindData[obj];
   WITH data: either SELECT FROM
     used => BEGIN
             IF data.count < oneCount THEN ERROR ObjectWithZeroCount;
             addr _ [ page: [heapHandle, data.page], word: data.word ];
             END;
   ENDCASE => ERROR ObjectNotInUse[];
   ReleaseData[clean];
   END;

UseObject: PUBLIC ENTRY PROCEDURE[ obj: ObjectDirXDefs.ObjectNumber ] =
   BEGIN
   either: POINTER TO DirData = FindData[obj];
   WITH data: either SELECT FROM
     used => BEGIN
             IF data.count < oneCount THEN ERROR ObjectWithZeroCount;
             IF data.count = LAST[ObjectCount] THEN ERROR ObjectCountTooBig;
             data.count _ data.count + 1;
             END;
   ENDCASE => ERROR ObjectNotInUse[];
   ReleaseData[dirty];
   END;

FreeObject: PUBLIC ENTRY PROCEDURE[ obj: ObjectDirXDefs.ObjectNumber ] =
   BEGIN
   either: POINTER TO DirData = FindData[obj];
   WITH data: either SELECT FROM
     used => BEGIN
             IF data.count < oneCount THEN ERROR ObjectWithZeroCount;
             IF ( data.count _ data.count - 1 ) = zeroCount
             THEN BEGIN
                  IF obj.type = temp
                  THEN BEGIN
                       HeapFileDefs.ObjectAbandoned[[heapHandle,data.page]];
                       AddToFreeList[obj,either,0];
                       END
                  ELSE PolicyDefs.GapExists[];
                  END;
             END;
   ENDCASE => ERROR ObjectNotInUse[];
   ReleaseData[dirty];
   END;

IllegalRelease: ERROR = CODE;

ReleaseObject: PUBLIC ENTRY PROCEDURE [ obj: ObjectDirXDefs.ObjectNumber ] =
   BEGIN
   either: POINTER TO DirData = FindData[obj];
   IF obj.type = temp THEN ERROR IllegalRelease[];
   WITH data: either SELECT FROM
     used => IF data.count # zeroCount
             THEN ERROR IllegalRelease[]
             ELSE {AddToFreeList[obj, either, 0]; ReleaseData[dirty]};
   ENDCASE => ERROR IllegalRelease[];
   END; -- ReleaseObject --
             

IllegalEnumerate: ERROR = CODE;

Enumerate: PUBLIC PROCEDURE[type: ObjectDirDefs.ObjectType,
             proc: PROCEDURE[ObjectDirXDefs.ObjectNumber]RETURNS[BOOLEAN] ]
                    RETURNS[ObjectDirXDefs.ObjectNumber] =
   BEGIN
   Check: ENTRY PROCEDURE[ obj: ObjectDirXDefs.ObjectNumber ]
                  RETURNS[ wanted: BOOLEAN ] = INLINE
      BEGIN
      either: POINTER TO DirData = FindData[obj];
      WITH data: either SELECT FROM
        used => BEGIN
                wanted _ data.type = obj.type;
                IF wanted THEN data.count _ data.count+1;
                END;
      ENDCASE => wanted _ FALSE;
      ReleaseData[IF wanted THEN dirty ELSE clean];
      END;
   IF type = temp THEN ERROR IllegalEnumerate[];
   FOR page: VMDefs.PageNumber _ 0, page+1
   DO Last: ENTRY PROCEDURE RETURNS[ BOOLEAN] = INLINE
         BEGIN RETURN[ page = nextVirginPage ] END;
      IF Last[] THEN EXIT;
      FOR index: DirIndex IN [ FIRST[DirIndex] .. LAST[DirIndex] ]
      DO BEGIN
         obj: ObjectDirXDefs.ObjectNumber =
                 [page:page, fill:0, type:type, index:index];
         IF Check[obj]
         THEN BEGIN
              result: BOOLEAN _ proc[obj ! UNWIND => FreeObject[obj]];
              FreeObject[obj];
              IF result THEN RETURN[obj];
              END;
         END;
      ENDLOOP;
   ENDLOOP;
   RETURN[ObjectDirDefs.noObject];
   END;


-- Compactor interface --

lastDofpc: ObjectDirXDefs.DOPC _ 0;

ReportDofpc: PUBLIC ENTRY PROCEDURE[ dofpc: ObjectDirXDefs.DOPC ] =
   { lastDofpc _ dofpc };

MoveObject: PUBLIC ENTRY PROCEDURE[ obj: ObjectDirXDefs.ObjectNumber,
                                    where: VMDefs.FullAddress ] =
   BEGIN
   either: POINTER TO DirData = FindData[obj];
   -- the compactor may occasionally move objects whose count has --
   -- decreased to zero after the compactor called 'ObjectInUse'  --
   WITH data: either SELECT FROM
     used => BEGIN
             data.page _ where.page.page;
             data.word _ where.word;
             END;
   ENDCASE => ERROR ObjectNotInUse[];
   ReleaseData[dirty];
   END;

GetObjectState: PUBLIC ENTRY PROCEDURE[ obj: ObjectDirXDefs.ObjectNumber,
                                        where: VMDefs.FullAddress,
                                        dorpc: ObjectDirXDefs.DOPC ]
                           RETURNS[ state: ObjectDirXDefs.ObjectState ] =
   BEGIN
   either: POINTER TO DirData = FindData[obj];
   -- TRUE iff non-zero count and on appropriate page --
   -- Word position within page is not relevant: position is considered --
   -- only to eliminate duplicates left behind by compactor crashes --
   WITH data: either SELECT FROM
     used => BEGIN
             IF data.page # where.page.page
             THEN { state _ duplicate; ReleaseData[clean] }
             ELSE IF data.count = zeroCount
                  THEN BEGIN
                       AddToFreeList[obj,either,dorpc];
                       state _ unused; ReleaseData[dirty];
                       END
                  ELSE { state _ inUse; ReleaseData[clean] };
             END;
   ENDCASE => ERROR ObjectNotInUse[];
   END;

AddToFreeList: PROC[obj: ObjectDirXDefs.ObjectNumber,
                    either: POINTER TO DirData,
                    dorpc: ObjectDirXDefs.DOPC] =
   BEGIN
   IF dpPage.header.nextFreePage = unchained
   THEN { dpPage.header.nextFreePage_firstFreePage;
          firstFreePage _ dpNumber };
   either^ _ [free[dpPage.header.nextFreeIndex,dorpc]];
   dpPage.header.nextFreeIndex _ obj.index;
   END;

END.