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