-- Copyright (C) 1981, 1982, 1984, 1985  by Xerox Corporation. All rights reserved. 
-- VMCacheMgr.mesa, HGM, 17-Sep-85  1:35:34

-- Last edited by Wobber:  2-Nov-82 10:19:21
-- Last edited by Gobbel: 18-May-81 17:27:32
-- Last edited by Levin:  30-Apr-81 13:04:02

DIRECTORY
  Heap USING [systemZone],
  Inline USING [LowHalf],
  Process USING [MsecToTicks, Yield],
  VMDefs USING [CantReadBackingStore, CantWriteBackingStore, Error, Page, pageSize],
  VMPrivate USING [
    AcquirePage, CacheIndex, FileHandle, FileObject,
    HandleTable, IndexToHandle, nilCacheIndex,
    Object, PageHandle, PageIndex, PageObject, RemovePageFromTables,
    WritePageToFS],
  VMStorage USING [AllocatePage, FreePage];

VMCacheMgr: MONITOR
  IMPORTS Heap, Inline, Process, VMDefs, VMPrivate, VMStorage
  EXPORTS VMDefs, VMPrivate =

  BEGIN OPEN VMPrivate;


  -- The VMCache manager synchronizes access to the cache data structures.  However,
  -- there is a subtlety involving the PruneCache procedure, which is invoked when
  -- storage is low.  This procedure may be invoked at essentially arbitrary times and
  -- must be able to acquire the cache.  To prevent deadlock, storage allocation
  -- requests generated by VMCacheOps must either be made outside the cache mutual
  -- exclusion or must temporarily disable the PruneCache.  Examples occur in
  -- EnsureBufferExists, which calls AllocatePage, and FillCacheSlot, which calls
  -- the node-level allocator.


  -- Types and Related Constants --

  CacheState: TYPE = {stable, unstable};

  VictimClass: TYPE = {
    available, nil, cleanOver, dirtyOver, cleanUnder, dirtyUnder, none};


  -- Global Variables --

  cacheState: CacheState;
  cacheStable: CONDITION;

  minCachePages, maxCachePages: CacheIndex;

  handles: LONG POINTER TO HandleTable;

  buffersInUse: CacheIndex;

  rover: CacheIndex;

  flushDisabled: BOOLEAN;


  -- Miscellaneous Declarations --

  hopeForStateChange: CONDITION;

  PageInUse: ERROR = CODE;


  -- Types Exported to VMDefs --

  FileObject: PUBLIC TYPE = VMPrivate.FileObject;


  -- Procedures and Signals Exported to VMSpecial
  -- Not Used, 15-Sep-85 16:26:55, HGM

  PruneCache: PUBLIC PROCEDURE [pages: CARDINAL] RETURNS [BOOLEAN] =
    BEGIN

    StealOneBuffer: PROCEDURE =
      -- releases a single page buffer.
      BEGIN
      victim: CacheIndex;
      page: PageHandle;
      [victim, ] ← LiberateCacheSlot[bufferRequired: TRUE];
      page ← IndexToHandle[victim];
      VMStorage.FreePage[page.pointer, page.index];
      page.pointer ← NIL;
      buffersInUse ← buffersInUse - 1;
      END;

    IF flushDisabled OR buffersInUse <= minCachePages THEN RETURN[FALSE];
    AcquireCache[];
    IF pages = 1 THEN StealOneBuffer[]
    ELSE UNTIL buffersInUse <= minCachePages DO StealOneBuffer[]; ENDLOOP;
    ReleaseCache[];
    RETURN[TRUE]
    END;


  -- Procedures and Signals Exported to VMPrivate --

  InitializeVMCacheMgr: PUBLIC PROCEDURE [
    h: LONG POINTER TO HandleTable, min, max: CacheIndex, first: LONG POINTER] =
    BEGIN
    handles ← h;
    minCachePages ← min;
    maxCachePages ← max;
    firstBuffer ← first;
    rover ← FIRST[CacheIndex];
    hopeForStateChange.timeout ← Process.MsecToTicks[100];
    flushDisabled ← FALSE;
    buffersInUse ← 0;
    cacheState ← stable;
    cacheStable.timeout ← 0;
    END;

  FinalizeVMCacheMgr: PUBLIC PROCEDURE =
    BEGIN
    FOR index: CacheIndex IN [0..handles.nHandles) DO
      page: PageHandle ← handles[index];
      IF page # NIL THEN
        BEGIN
        IF ~(page.useCount = 0 AND page.file = NIL) THEN ERROR PageInUse;
        IF page.pointer # NIL THEN VMStorage.FreePage[page.pointer, page.index];
        Heap.systemZone.FREE[@page];
        END;
      ENDLOOP;
    END;

  -- Cache Mutual Exclusion --

  AcquireCache: PUBLIC ENTRY PROCEDURE =
    BEGIN
    UNTIL cacheState = stable DO WAIT cacheStable; ENDLOOP;
    cacheState ← unstable;
    END;

  ReleaseCache: PUBLIC ENTRY PROCEDURE = {
    cacheState ← stable; NOTIFY cacheStable};

  -- Cache Management --

  AllocateCacheIndex: PUBLIC PROCEDURE RETURNS [CacheIndex] =
    BEGIN
    page: PageHandle;
    victim: CacheIndex;
    vc: VictimClass;
    AcquireCache[];
    [victim, vc] ← LiberateCacheSlot[bufferRequired: FALSE];
    IF vc = nil THEN FillCacheSlot[victim];
    page ← IndexToHandle[victim];
    page.state ← unstable;
    ReleaseCache[];
    EnsureBufferExists[victim];
    RETURN[victim]
    END;

  EnumerateCachePagesInFile: PUBLIC PROCEDURE [
    file: FileHandle,
    proc: PROCEDURE [page: PageHandle] RETURNS [found, unmap: BOOLEAN]]
    RETURNS [outcome: BOOLEAN] =
    BEGIN
    outcome ← FALSE;
    DO
      pagesBeingTaken: BOOLEAN ← FALSE;
      slot, last: CacheIndex;
      AcquireCache[];
      slot ← last ← rover;
      DO
        page: PageHandle = handles[slot];
        IF page # NIL AND page.file = file THEN
          IF page.beingTaken THEN pagesBeingTaken ← TRUE
          ELSE
            BEGIN
            unmap: BOOLEAN;
            page.useCount ← page.useCount + 1;
            [found: outcome, unmap: unmap] ← proc[
              page ! UNWIND => ReleaseCache[]];
            IF (page.useCount ← page.useCount - 1) = 0 AND unmap THEN
              RemovePageFromTables[page];
            IF outcome THEN {ReleaseCache[]; RETURN};
            END;
        slot ← IF slot = maxCachePages - 1 THEN FIRST[CacheIndex] ELSE slot + 1;
        IF slot = last THEN EXIT;
        ENDLOOP;
      ReleaseCache[];
      IF ~pagesBeingTaken THEN EXIT;
      Process.Yield[];
      ENDLOOP;
    END;


  -- Internal Procedures --

  -- Cache Management --

  EnumerateCacheSlots: PROCEDURE [
    proc: PROCEDURE [slot: CacheIndex] RETURNS [BOOLEAN]] RETURNS [BOOLEAN] =
    BEGIN
    slot: CacheIndex ← rover;
    last: CacheIndex ← rover;
    DO
      IF proc[slot] THEN RETURN[TRUE];
      slot ← IF slot = maxCachePages - 1 THEN FIRST[CacheIndex] ELSE slot + 1;
      IF slot = last THEN RETURN[FALSE];
      ENDLOOP;
    END;

  LiberateCacheSlot: PROCEDURE [bufferRequired: BOOLEAN]
    RETURNS [victim: CacheIndex, vc: VictimClass] =
    -- uses FindPotentialVictim to locate a candidate, writes the victim out to disk
    -- if dirty, and, if necessary, removes it from the mapping tables.
    BEGIN
    DO
      page: PageHandle;
      [victim, vc] ← FindPotentialVictim[bufferRequired];
      SELECT vc FROM nil, available => EXIT; ENDCASE;
      page ← IndexToHandle[victim];
      IF page.dirty THEN
        BEGIN OPEN VMDefs;
        AcquirePage[page];
        page.beingTaken ← TRUE;  -- ensure page doesn't disappear
        ReleaseCache[];
        WritePageToFS[
          page: page, wait: TRUE !
          CantReadBackingStore, CantWriteBackingStore, Error => CONTINUE];
        AcquireCache[];
        page.beingTaken ← FALSE;
        IF page.dirty OR page.useCount > 0 THEN LOOP;
        END;
      RemovePageFromTables[page];
      EXIT;
      ENDLOOP;
    END;

  FindPotentialVictim: PROCEDURE [bufferRequired: BOOLEAN]
    RETURNS [victim: CacheIndex, vc: VictimClass] =  -- INLINE --
    -- locates a candidate victim slot in the cache, using the replacement algorithm.
    -- For normal replacement purposes, 'bufferRequired' should be FALSE.  However, if
    -- the selected victim must have a buffer already allocated (e.g., as when returning
    -- buffer space to the Mesa runtime), then 'bufferRequired' should be TRUE.
    BEGIN

    CheckSlot: PROCEDURE [slot: CacheIndex] RETURNS [stopLooking: BOOLEAN] =
      -- classifies and potentially selects as a possible victim the page in cache
      -- slot 'slot'.  Returns TRUE when a "first-rate" victim has been found.
      BEGIN
      page: PageHandle = handles[slot];  -- don't use IndexToHandle, since NIL is OK.
      file: FileHandle;
      newvc: VictimClass;
      stopLooking ← FALSE;
      BEGIN  -- inner block permits 'MightBeDone' to access 'page' and 'newvc'
      IF page = NIL THEN {newvc ← nil; GO TO MightBeDone};
      IF page.useCount # 0 OR page.state = unstable OR page.beingTaken THEN
        RETURN;
      IF page.file = NIL THEN {newvc ← available; GO TO MightBeDone};
      IF page.age = new THEN RETURN;
      file ← page.file;
      newvc ←
        IF page.dirty THEN
        IF file.useCount <= file.cachePages THEN dirtyUnder ELSE dirtyOver
        ELSE IF file.useCount <= file.cachePages THEN cleanUnder ELSE cleanOver;
      IF newvc < vc THEN {vc ← newvc; victim ← slot};
      IF vc = cleanOver THEN stopLooking ← TRUE;
      EXITS
        MightBeDone =>
          BEGIN  -- newvc is either nil or available
          IF bufferRequired
            AND (newvc = nil OR (newvc = available AND page.pointer = NIL))
            THEN RETURN;
          victim ← slot;
          vc ← newvc;
          stopLooking ← TRUE;
          END;
      END;
      END;

    AgeSlot: PROCEDURE [slot: CacheIndex] RETURNS [BOOLEAN] =
      -- marks the indicated cache slot 'old', if it is legitimate to do so.  Note
      -- that we need not test for page.beingTaken, since such a page is already
      -- marked old.
      BEGIN
      page: PageHandle = handles[slot];  -- don't use IndexToHandle, since NIL is OK.
      IF page # NIL AND page.useCount = 0 AND page.file # NIL
        AND page.state = stable THEN page.age ← old;
      RETURN[FALSE]
      END;

    WaitForBetterTimes: ENTRY PROCEDURE = INLINE
      -- in desperation, we delay for a while.
      {WAIT hopeForStateChange};

    DO
      victim ← nilCacheIndex;
      vc ← none;
      [] ← EnumerateCacheSlots[CheckSlot];
      SELECT vc FROM
        available, nil => EXIT;
        none =>  -- no old, stealable pages are present in the cache
          BEGIN
          [] ← EnumerateCacheSlots[AgeSlot];  -- age everything
          [] ← EnumerateCacheSlots[CheckSlot];
          IF vc # none THEN EXIT;
          -- things are very grim...
          ReleaseCache[];
          WaitForBetterTimes[];
          AcquireCache[];
          END;
        ENDCASE =>  -- cleanOver, cleanUnder, dirtyOver, dirtyUnder
          BEGIN
          -- age all cache slots between 'rover' and 'victim', inclusive.
          -- Note: we expand EnumerateCacheSlots inline for efficiency.  See notes
          -- on AgeSlot, above.
          slot: CacheIndex ← rover;
          DO
            page: PageHandle = handles[slot];
            IF page # NIL AND page.useCount = 0 AND page.file # NIL
              AND page.state = stable THEN page.age ← old;
            IF slot = victim THEN EXIT;
            slot ←
              IF slot = maxCachePages - 1 THEN FIRST[CacheIndex] ELSE slot + 1;
            ENDLOOP;
          EXIT
          END;
      ENDLOOP;
    rover ← victim;
    END;

  FillCacheSlot: PROCEDURE [index: CacheIndex] = INLINE
    -- creates a page object and associated buffer, marks it 'available', and places
    -- it in cache slot 'index'.
    BEGIN
    page: PageHandle;
    flushDisabled ← TRUE;  -- tough break, Mesa
    handles[index] ← page ← Heap.systemZone.NEW[
      PageObject ← Object[ page[
        state: unstable, age:, dirty: FALSE, errorStatus:, pointer: NIL, index: 0,
        pageStable: [timeout: 0], file: NIL, beingTaken: FALSE, page:, hashLink:,
        recordNextVda:, useCount: 0]]];
    flushDisabled ← FALSE;
    END;

  BogusPageNumber: ERROR = CODE;
  EnsureBufferExists: PROCEDURE [index: CacheIndex] =
    -- ensures that the page in cache slot 'index' has an associated buffer.
    BEGIN
    page: PageHandle ← IndexToHandle[index];
    IF page.pointer = NIL THEN  {
      [page.pointer, page.index] ← VMStorage.AllocatePage[];
      buffersInUse ← buffersInUse + 1; };
    lastIndex ← MAX[lastIndex, page.index];
    END;

  firstBuffer: LONG POINTER ← NIL;
  lastIndex: PageIndex ← 0;
  
  BogusAddress: ERROR = CODE;
  AddressToPageIndex: PUBLIC PROCEDURE [address: VMDefs.Page] RETURNS [PageIndex] =
    BEGIN
    offset: LONG CARDINAL = LOOPHOLE[address - firstBuffer];
    pageNumber: LONG CARDINAL = offset/VMDefs.pageSize;
    index: PageIndex ← Inline.LowHalf[pageNumber];
    IF pageNumber > lastIndex THEN ERROR BogusAddress;
    RETURN[index];
    END;
    
  END.