-- File: VMCacheMgr.mesa
-- Last edited by Levin:  12-Jul-82 15:27:57

DIRECTORY
  LogDefs USING [DisplayNumber],
  ProcessDefs USING [MsecToTicks, Yield],
  VMDefs USING [CantReadBackingStore, CantWriteBackingStore, Error],
  VMPrivate USING [
    AcquirePage, AddressToMDSPage, CacheIndex, FileHandle, FileObject, HandleTable,
    IndexToHandle, loggingEnabled, MDSPageToAddress, nilCacheIndex, nilMDSPage,
    Object, PageHandle, PageObject, RemovePageFromTables, WriteEnable,
    WritePageToFS, WriteProtect],
  VMSpecial USING [],
  VMStorage USING [AllocatePage, FreePage, longTerm];

VMCacheMgr: MONITOR LOCKS lock↑
  IMPORTS LogDefs, ProcessDefs, VMDefs, VMPrivate, VMStorage
  EXPORTS VMDefs, VMPrivate, VMSpecial =

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

  lock: POINTER TO MONITORLOCK;
  LOCK: MONITORLOCK;
  
  cacheState: CacheState;
  cacheStable: CONDITION;

  minCachePages, maxCachePages: CacheIndex;

  handles: 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 --

  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[MDSPageToAddress[page.buffer]];
      page.buffer ← nilMDSPage;
      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: POINTER TO HandleTable, min, max: CacheIndex] =
    BEGIN
    lock ← @LOCK;
    handles ← h;
    minCachePages ← min;
    maxCachePages ← max;
    rover ← FIRST[CacheIndex];
    hopeForStateChange.timeout ← ProcessDefs.MsecToTicks[100];
    flushDisabled ← FALSE;
    buffersInUse ← 0;
    cacheState ← stable;
    cacheStable.timeout ← 0;
    IF loggingEnabled THEN
      LogDefs.DisplayNumber["VM Cache Pages"L, [short[@buffersInUse]]];
    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.buffer ~= nilMDSPage THEN
	  BEGIN
	  WriteEnable[page.buffer];
	  VMStorage.FreePage[MDSPageToAddress[page.buffer]];
	  END;
	VMStorage.longTerm.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 OR page.state = unstable 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 THEN
	      IF unmap THEN RemovePageFromTables[page]
	      ELSE WriteProtect[page.buffer];
	    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;
      ProcessDefs.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.buffer = nilMDSPage)) 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 ← VMStorage.longTerm.NEW[PageObject ← Object[page[
      state: unstable, age: , dirty: FALSE, errorStatus: , buffer: nilMDSPage,
      pageStable: [timeout: 0], file: NIL, beingTaken: FALSE, page: , hashLink: ,
      recordNextVda: , useCount: 0]]];
    flushDisabled ← FALSE;
    END;

  EnsureBufferExists: PROCEDURE [index: CacheIndex] =
    -- ensures that the page in cache slot 'index' has an associated buffer.
    BEGIN
    page: PageHandle ← IndexToHandle[index];
    IF page.buffer = nilMDSPage THEN
      BEGIN
      page.buffer ← AddressToMDSPage[VMStorage.AllocatePage[]];
      buffersInUse ← buffersInUse + 1;
      END
    ELSE WriteEnable[page.buffer];
    END;

  END.