-- file SymbolCache.Mesa
-- last edited by Satterthwaite, October 23, 1978  9:15 AM

DIRECTORY
  AltoDefs: FROM "altodefs" USING [PageSize],
  SegmentDefs: FROM "segmentdefs" USING [
    FileSegmentAddress, FileSegmentHandle, InsufficientVM, InvalidFP, SwapIn,
    SwapOut, Unlock],
  Symbols: FROM "symbols" USING [HTIndex, HTRecord],
  SymbolPack: FROM "symbolpack" USING [
    bb, cacheInfo, ctxb, extb, fgTable, hashVec, ht, link, ltb, mdb, notifier,
    NullNotifier, seb, sourceFile, ssb, stHandle, tb],
  SymbolSegment: FROM "symbolsegment" USING [FGHeader, STHeader],
  SymbolTable: FROM "symboltable" USING [Base, Handle],
  SystemDefs: FROM "systemdefs" USING [AllocateHeapNode],
  Table: FROM "table" USING [Base];

SymbolCache: PROGRAM
    IMPORTS initial: SymbolPack, SegmentDefs, SystemDefs
    EXPORTS SymbolTable SHARES SymbolTable =
  BEGIN
  OPEN SegmentDefs;

  -- public interface

  Missing: PUBLIC ERROR [FileSegmentHandle] = CODE;

  TableForSegment: PUBLIC PROCEDURE [seg: FileSegmentHandle] RETURNS [SymbolTable.Handle] =
    BEGIN
    RETURN [SymbolTable.Handle[seg]]
    END;

  SegmentForTable: PUBLIC PROCEDURE [table: SymbolTable.Handle] RETURNS [FileSegmentHandle] =
    BEGIN
    RETURN [table.segment]
    END;


  IllegalBase: PUBLIC ERROR [base: SymbolTable.Base] = CODE;

  Acquire: PUBLIC PROCEDURE [handle: SymbolTable.Handle]
      RETURNS [base: SymbolTable.Base] =
    BEGIN
    node: CachePointer;
    IF freeTables = NIL
      THEN  BEGIN base _ NEW initial; START base END
      ELSE  BEGIN base _ freeTables; freeTables _ freeTables.link END;
    node _ MakeCacheEntry[handle];
    base.link _ busyTables;  busyTables _ base;
    InstallTable[base, node];
    END;

  Release: PUBLIC PROCEDURE [base: SymbolTable.Base] =
    BEGIN
    node: CachePointer;
    cacheNode: CachePointer = base.cacheInfo;
    prev, table: SymbolTable.Base;
    FOR node _ header.next, node.next UNTIL node = cacheNode
      DO
      IF node = free THEN ERROR IllegalBase[base];
      ENDLOOP;
    prev _ NIL;
    FOR table _ busyTables, table.link UNTIL table = NIL
      DO
      IF table = base THEN
        BEGIN
        IF prev # NIL
	  THEN prev.link _ table.link
	  ELSE busyTables _ table.link;
        EXIT
        END;
      prev _ table;
      REPEAT
        FINISHED => ERROR IllegalBase[base];
      ENDLOOP;
    FreeCacheEntry[cacheNode];
    base.link _ freeTables;  freeTables _ base;
    END;

  busyTables: SymbolTable.Base _ NIL;
  freeTables: SymbolTable.Base _ initial;


  cachePageLimit: CARDINAL _ 0;

  CacheSize: PUBLIC PROCEDURE RETURNS [pages: CARDINAL] =
    BEGIN
    RETURN [cachePageLimit]
    END;

  SetCacheSize: PUBLIC PROCEDURE [pages: CARDINAL] =
    BEGIN
    cachePageLimit _ pages;  TrimCache[cachePageLimit];
    END;


  suspended: BOOLEAN;

  SuspendCache: PUBLIC PROCEDURE =
    BEGIN
    node: CachePointer;
    WHILE unused # free DO ClearNode[unused _ unused.prev] ENDLOOP;
    suspended _ TRUE;
    FOR node _ header.next, node.next UNTIL node = free
      DO  Unlock[node.table];  SwapOut[node.table]  ENDLOOP;
    END;

  RestartCache: PUBLIC PROCEDURE =
    BEGIN
    node: CachePointer;
    base: SymbolTable.Base;
    IF ~suspended THEN ERROR;
    FOR node _ header.next, node.next UNTIL node = free
      DO  SwapIn[node.table]  ENDLOOP;
    FOR base _ busyTables, base.link UNTIL base = NIL
      DO  SetBases[base, base.cacheInfo];  base.notifier[base]  ENDLOOP;
    suspended _ FALSE;
    END;


-- internal cache management

  CacheNodes: CARDINAL = 15;
  MaxCacheNodes: CARDINAL = 255;
  LockTime: CARDINAL = 1;

  CacheNode: TYPE = RECORD[
    prev, next: CachePointer,
    table: SymbolTable.Handle,
    locked: BOOLEAN,
    timeLeft: [0..LockTime],
    refCount: [0..MaxCacheNodes]];

  CachePointer: TYPE = POINTER TO CacheNode;

  header, free, unused: CachePointer;
  lockedPages: CARDINAL;


  --    C A C H E   O R G A N I Z A T I O N

  -- The cache keeps track of segments in CacheNodes.  The CacheNodes are
  -- kept in a doubly-linked list and organized in three groups, separated
  -- by three pointers: header, free, and unused.  Ordered by the link
  -- next, the list is organized as follows:
  --   (header .. free)		nodes attached to frames,
  --   [free .. unused)		nodes with segment but no frame,
  --   [unused .. header)	empty and available,


  MakeCacheEntry: PROCEDURE [handle: SymbolTable.Handle] RETURNS [node: CachePointer] =
    BEGIN
    FOR node _ header.next, node.next UNTIL node = free
      DO
      IF node.table = handle THEN GO TO allocated;
      REPEAT
        allocated =>  NULL;
        FINISHED =>
          BEGIN
	  AgeNodes[];
          FOR node _ free, node.next UNTIL node = unused
	    DO
            IF node.table = handle THEN GO TO unflushed;
            REPEAT
              unflushed =>  Detach[node];
              FINISHED =>
                BEGIN  node _ GetEmptyNode[];  node.table _ handle  END;
	    ENDLOOP;
	  IF ~node.locked
	    THEN
	      BEGIN
	      retried: BOOLEAN _ FALSE;
	      TrimCache[MAX[cachePageLimit, handle.pages] - handle.pages];
	      SwapIn[handle !
		InvalidFP => ERROR Missing[handle];
		InsufficientVM =>
		  IF ~retried THEN
		    BEGIN
		    SuspendCache[]; RestartCache[]; retried _ TRUE; RESUME
		    END];
	      node.locked _ TRUE;
	      lockedPages _ lockedPages + handle.pages;
	      END;
          Insert[node, free];
          END;
      ENDLOOP;
    node.refCount _ node.refCount+1;  RETURN
    END;

  FreeCacheEntry: PROCEDURE [node: CachePointer] =
    BEGIN
    IF (node.refCount _ node.refCount-1) = 0
      THEN
        BEGIN
	Detach[node];  node.timeLeft _ LockTime;
	Insert[node, free];  free _ node;
        END;
    END;

  GetEmptyNode: PROCEDURE RETURNS [node: CachePointer] =
    BEGIN
    IF free = header
      THEN  node _ SystemDefs.AllocateHeapNode[SIZE[CacheNode]]
      ELSE
	BEGIN
	IF unused = header THEN ClearNode[unused _ unused.prev];
	node _ unused;  Detach[node];
	END;
    node.refCount _ 0;  node.locked _ FALSE;
    RETURN
    END;

  Detach: PROCEDURE [node: CachePointer] =
    BEGIN
    IF node = free THEN free _ free.next;
    IF node = unused THEN unused _ unused.next;
    node.prev.next _ node.next;  node.next.prev _ node.prev;
    END;

  Insert: PROCEDURE [node, position: CachePointer] =
    BEGIN
    node.prev _ position.prev;  node.prev.next _ node;
    node.next _ position;  position.prev _ node;
    END;

  TrimCache: PROCEDURE [size: CARDINAL] =
    BEGIN
    WHILE (lockedPages > size OR size = 0) AND unused # free
      DO ReleaseLock[unused _ unused.prev] ENDLOOP;
    END;

  AgeNodes: PROCEDURE =
    BEGIN
    node: CachePointer;
    FOR node _ free, node.next UNTIL node = unused OR node.timeLeft = 0
      DO
      IF (node.timeLeft _ node.timeLeft-1) = 0 THEN  ReleaseLock[node];
      ENDLOOP;
    END;

  ReleaseLock: PROCEDURE [node: CachePointer] =
    BEGIN
    IF node.locked
      THEN
	BEGIN
	Unlock[node.table];  node.locked _ FALSE;
	lockedPages _ lockedPages - node.table.pages;
	END;
    END;

  ClearNode: PROCEDURE [node: CachePointer] =
    BEGIN
    ReleaseLock[node];  -- SwapOut[node.table];
    END;


-- symbol table setup

  InstallTable: PROCEDURE [base: SymbolTable.Base, node: CachePointer] =
    BEGIN
    SetBases[base, node];  base.notifier _ base.NullNotifier;  RETURN
    END;

  SetBases: PROCEDURE [base: SymbolTable.Base, node: CachePointer] =
    BEGIN
    b: POINTER = FileSegmentAddress[node.table];
    tB: Table.Base = LOOPHOLE[b];
    p: POINTER TO SymbolSegment.STHeader = b;
    q: POINTER TO SymbolSegment.FGHeader;
    base.cacheInfo _ node;
    base.hashVec _
      DESCRIPTOR[b+p.hvBlock.offset, p.hvBlock.size/SIZE[Symbols.HTIndex]];
    base.ht _
      DESCRIPTOR[b+p.htBlock.offset, p.htBlock.size/SIZE[Symbols.HTRecord]];
    base.ssb _ b + p.ssBlock.offset;
    base.seb _ tB + p.seBlock.offset;
    base.ctxb _ tB + p.ctxBlock.offset;
    base.mdb _ tB + p.mdBlock.offset;
    base.bb _ tB + p.bodyBlock.offset;
    base.tb _ tB + p.treeBlock.offset;
    base.ltb _ tB + p.litBlock.offset;
    base.extb _ tB + p.extBlock.offset;
    base.stHandle _ p;
    IF p.fgRelPgBase = 0 THEN  base.sourceFile _ NIL
    ELSE
      BEGIN
      q _ b + p.fgRelPgBase*AltoDefs.PageSize;
      base.sourceFile _ LOOPHOLE[@q.sourceFile];
      base.fgTable _ DESCRIPTOR[
        b + p.fgRelPgBase*AltoDefs.PageSize + q.offset, q.length];
      END;
    END;

-- initialization

  CacheEntries: ARRAY [0..CacheNodes] OF CacheNode;

  Init: PROCEDURE =
    BEGIN
    j: INTEGER [0..CacheNodes];
    START initial;  initial.link _ NIL;
    FOR j IN [0..CacheNodes]
      DO
      CacheEntries[j].next _ @CacheEntries[IF j=CacheNodes THEN 0 ELSE j+1];
      CacheEntries[j].prev _ @CacheEntries[IF j=0 THEN CacheNodes ELSE j-1];
      ENDLOOP;
    header _ @CacheEntries[0];
    free _ unused _ header.next;
    lockedPages _ 0;  suspended _ FALSE;
    END;

  Init[];

  END.