-- File: VMCacheOps.mesa
-- Last edited by Levin:  12-Jul-82 16:50:17

DIRECTORY
  Inline USING [BITXOR],
  VMDefs USING [
    CantReadBackingStore, CantWriteBackingStore, Page, PageAddress, Start],
  VMPrivate USING [
    AcquireCache, AcquirePage, AddressToMDSPage, AllocateCacheIndex, CacheIndex,
    FileHandle, FileObject, FinalizeVMCacheMgr, HandleTable, InitializeVMCacheMgr,
    MDSPageNumber, MDSPageToAddress, nilCacheIndex, PageHandle, ReleaseCache,
    ReleasePage, ValidateFile, ValidatePageNumber, WaitUntilStable, WriteEnable,
    WriteProtect],
  VMStorage USING [longTerm];

VMCacheOps: PROGRAM
  IMPORTS Inline, VMDefs, VMPrivate, VMStorage
  EXPORTS VMDefs, VMPrivate =

  BEGIN OPEN VMDefs, VMPrivate;


  -- Types and Related Constants --

  PageMap: TYPE = PACKED ARRAY MDSPageNumber OF CacheIndex;

  HashIndex: TYPE = [0..HashBins);
  HashBins: CARDINAL = 97;


  -- Global Variables --

  handles: POINTER TO HandleTable;

  pageMap: PageMap;

  hashTable: PACKED ARRAY HashIndex OF CacheIndex;


  -- Miscellaneous Declarations --

  AttemptToReusePageMapSlot: ERROR = CODE;
  BadAddress: ERROR = CODE;
  IllegalCacheIndex: ERROR = CODE;
  IllegalPageState: ERROR = CODE;
  InconsistentHandleMap: ERROR = CODE;
  InconsistentHashTable: ERROR = CODE;
  InconsistentPageMap: ERROR = CODE;


  -- Procedures and Signals Exported to VMDefs --

  FileObject: PUBLIC TYPE = VMPrivate.FileObject;

  -- Page Object Allocation --

  AllocatePage: PUBLIC PROCEDURE RETURNS [Page] =
    BEGIN
    index: CacheIndex = AllocateCacheIndex[];
    page: PageHandle = IndexToHandle[index];
    page.useCount ← 1;
    page.file ← NIL;
    page.age ← new;
    page.dirty ← FALSE;
    page.state ← stable;
    AcquireCache[];
    EnterInPageTable[page.buffer, index];
    ReleaseCache[];
    RETURN[MDSPageToAddress[page.buffer]]
    END;

  Release: PUBLIC PROCEDURE [page: Page] =
    BEGIN
    p: PageHandle;
    AcquireCache[];
    p ← AddressToHandle[page];
    IF p.useCount = 0 THEN ERROR IllegalPageState;
    IF (p.useCount ← p.useCount - 1) = 0 THEN
      IF p.file = NIL THEN RemoveFromPageTable[p]
      ELSE WriteProtect[p.buffer];
    ReleaseCache[];
    END;

  Deactivate: PUBLIC PROCEDURE [page: Page] =
    BEGIN
    p: PageHandle;
    AcquireCache[];
    p ← AddressToHandle[page];
    SELECT p.useCount FROM
      0 => ERROR IllegalPageState;
      1 =>
	IF ~p.dirty THEN RemovePageFromTables[p]
	ELSE
	  BEGIN
	  p.age ← old;
	  ReleaseCache[];
	  VMDefs.Start[page];
	  AcquireCache[];
	  IF p.useCount = 1 THEN WriteProtect[p.buffer];
	  END;
      ENDCASE;
    p.useCount ← p.useCount - 1;
    ReleaseCache[];
    END;

  -- Core/Disk Mapping --

  UsePage: PUBLIC PROCEDURE [addr: PageAddress] RETURNS [Page] =
    BEGIN
    oldindex, newindex: CacheIndex;
    page: PageHandle;
    ValidateAddress[addr];
    AcquireCache[];
    IF (oldindex ← LookupInHashTable[addr]) = nilCacheIndex THEN
      BEGIN
      ReleaseCache[];
      page ← IndexToHandle[newindex ← AllocateCacheIndex[]];
      page.file ← addr.file;
      page.page ← addr.page;
      AcquireCache[];
      page.state ← stable;
      IF (oldindex ← LookupInHashTable[addr]) = nilCacheIndex THEN
	{EnterInPageTable[page.buffer, newindex]; EnterInHashTable[page]}
      ELSE
	-- someone slipped the requested page in ahead us; abandon our page
	{page.file ← NIL; page ← IndexToHandle[oldindex]};
      END
    ELSE page ← IndexToHandle[oldindex];
    AcquirePage[page];
    page.dirty ← FALSE;
    IF page.useCount = 0 THEN WriteEnable[page.buffer];
    page.useCount ← page.useCount + 1;
    MarkPageUsableAndRelease[page];
    RETURN[MDSPageToAddress[page.buffer]]
    END;

  RemapPage: PUBLIC PROCEDURE [page: Page, addr: PageAddress] =
    BEGIN
    p: PageHandle;
    index: CacheIndex;
    ValidateAddress[addr];
    AcquireCache[];
    p ← AddressToHandle[page];
    AcquirePage[p];
    IF p.useCount ~= 1 THEN ERROR IllegalPageState;
    index ← LookupInHashTable[addr];
    IF index ~= nilCacheIndex THEN
      BEGIN -- previous contents of 'addr' is in cache
      oldPage: PageHandle = IndexToHandle[index];
      IF oldPage = p THEN {MarkPageUsableAndRelease[p]; RETURN};
      oldPage.useCount ← oldPage.useCount + 1;
      ReleaseCache[];
      IF WaitUntilStable[oldPage, writing
	! CantReadBackingStore, CantWriteBackingStore => CONTINUE] = unstable
	THEN ReleasePage[oldPage];
      AcquireCache[];
      -- throw away old contents, even if dirty
      IF (oldPage.useCount ← oldPage.useCount - 1) = 0 THEN
	{IF ~oldPage.beingTaken THEN RemovePageFromTables[oldPage]}
      ELSE ERROR BadAddress;
      END;
    RemoveFromHashTable[p];
    p.file ← addr.file;
    p.page ← addr.page;
    p.dirty ← TRUE;
    EnterInHashTable[p];
    MarkPageUsableAndRelease[p];
    END;

  UnmapPage: PUBLIC PROCEDURE [page: Page] =
    BEGIN
    p: PageHandle;
    AcquireCache[];
    p ← AddressToHandle[page];
    AcquirePage[p];
    IF p.useCount ~= 1 THEN ERROR IllegalPageState;
    RemoveFromHashTable[p];
    p.file ← NIL;
    MarkPageUsableAndRelease[p];
    END;

  PageToPageAddress: PUBLIC PROCEDURE [page: Page] RETURNS [PageAddress] =
    BEGIN
    p: PageHandle;
    addr: PageAddress;
    AcquireCache[];
    p ← AddressToHandle[page];
    AcquirePage[p];
    IF p.useCount = 0 OR p.file = NIL THEN ERROR IllegalPageState;
    addr ← [p.file, p.page];
    ReleasePage[p];
    ReleaseCache[];
    RETURN[addr]
    END;

  PageInCache: PUBLIC PROCEDURE [addr: PageAddress] RETURNS [inCache: BOOLEAN] =
    BEGIN
    AcquireCache[];
    inCache ← LookupInHashTable[addr] ~= nilCacheIndex;
    ReleaseCache[];
    END;

  -- Procedures and Signals Exported to VMPrivate --

  -- Start/Stop --

  InitializeVMCache: PUBLIC PROCEDURE [min, max: CacheIndex] =
    BEGIN
    handles ← VMStorage.longTerm.NEW[HandleTable[max]];
    FOR index: CacheIndex IN [0..max) DO handles[index] ← NIL; ENDLOOP;
    FOR vmpage: MDSPageNumber IN MDSPageNumber DO
      pageMap[vmpage] ← nilCacheIndex;
      ENDLOOP;
    FOR bin: HashIndex IN HashIndex DO
      hashTable[bin] ← nilCacheIndex;
      ENDLOOP;
    InitializeVMCacheMgr[handles, min, max];
    END;

  FinalizeVMCache: PUBLIC PROCEDURE =
    {FinalizeVMCacheMgr[]; VMStorage.longTerm.FREE[@handles]};

  -- Handle Table Management --

  IndexToHandle: PUBLIC PROCEDURE [index: CacheIndex]
    RETURNS [handle: PageHandle] =
    BEGIN
    IF index = nilCacheIndex THEN ERROR IllegalCacheIndex;
    IF (handle ← handles[index]) = NIL THEN ERROR InconsistentHandleMap;
    RETURN
    END;

  AddressToHandle: PUBLIC PROCEDURE [address: Page] RETURNS [PageHandle] =
    {RETURN[IndexToHandle[AddressToIndex[address]]]};

  HandleToAddress: PUBLIC PROCEDURE [page: PageHandle] RETURNS [Page] =
    {RETURN[MDSPageToAddress[page.buffer]]};

  -- Hash Table Management --

  LookupInHashTable: PUBLIC PROCEDURE [addr: PageAddress] RETURNS [index: CacheIndex] =
    BEGIN
    index ← hashTable[Hash[addr]];
    UNTIL index = nilCacheIndex DO
      page: PageHandle ← IndexToHandle[index];
      IF page.file = addr.file AND page.page = addr.page THEN RETURN;
      index ← page.hashLink;
      ENDLOOP;
    RETURN
    END;

  EnterInHashTable: PUBLIC PROCEDURE [page: PageHandle] =
    BEGIN
    bin: HashIndex = Hash[PageAddress[page.file, page.page]];
    page.hashLink ← hashTable[bin];
    hashTable[bin] ← pageMap[page.buffer];
    IncrementFileUseCount[page.file];
    END;

  -- Page Table Management --

  EnterInPageTable: PUBLIC PROCEDURE [page: MDSPageNumber, index: CacheIndex] =
    BEGIN
    IF pageMap[page] ~= nilCacheIndex THEN ERROR AttemptToReusePageMapSlot;
    pageMap[page] ← index;
    END;

  -- Miscellaneous Procedures --

  RemovePageFromTables: PUBLIC PROCEDURE [page: PageHandle] =
    BEGIN
    RemoveFromHashTable[page];
    RemoveFromPageTable[page];
    page.file ← NIL;
    END;


  -- Internal Procedures --

  -- Hash Table Management --

  RemoveFromHashTable: PROCEDURE [page: PageHandle] =
    -- delinks the argument page from the hash table.
    BEGIN
    ci: CacheIndex = pageMap[page.buffer];
    bin: HashIndex;
    IF page.file = NIL THEN RETURN;
    bin ← Hash[PageAddress[page.file, page.page]];
    IF hashTable[bin] = nilCacheIndex THEN GO TO badTable;
    IF ci = hashTable[bin] THEN hashTable[bin] ← page.hashLink
    ELSE
      BEGIN
      prev: PageHandle ← IndexToHandle[hashTable[bin]];
      UNTIL prev.hashLink = nilCacheIndex DO
	IF prev.hashLink = ci THEN {prev.hashLink ← page.hashLink; EXIT};
	prev ← IndexToHandle[prev.hashLink];
	REPEAT FINISHED => GO TO badTable;
	ENDLOOP;
      END;
    DecrementFileUseCount[page.file];
    EXITS
      badTable => ERROR InconsistentHashTable;
    END;

  Hash: PROCEDURE [addr: PageAddress] RETURNS [HashIndex] =
    -- produces HashIndex for 'addr' into hashTable.
    BEGIN
    Bytes: TYPE = MACHINE DEPENDENT RECORD [high: [0..255], low: [0..255]];

    XORBytes: PROCEDURE [word: UNSPECIFIED] RETURNS [UNSPECIFIED] = INLINE
      -- XORs the two bytes of 'word'.
      BEGIN OPEN w: LOOPHOLE[word, Bytes];
      RETURN[Inline.BITXOR[w.low, w.high]];
      END;

    RETURN[XORBytes[Inline.BITXOR[addr.file, addr.page]] MOD HashBins]
    END;

  -- Page Table Management --

  RemoveFromPageTable: PROCEDURE [page: PageHandle] =
    -- destroys the correspondance between (MDS) page 'page.buffer' and the page object.
    BEGIN
    IF IndexToHandle[pageMap[page.buffer]] ~= page THEN ERROR InconsistentPageMap;
    pageMap[page.buffer] ← nilCacheIndex;
    END;

  -- Handle Table Management --

  AddressToIndex: PROCEDURE [address: Page] RETURNS [CacheIndex] = INLINE
    -- maps an (MDS) address to the CacheIndex for the corresponding page.
    {RETURN[pageMap[AddressToMDSPage[address]]]};

  -- Miscellaneous Procedures --

  ValidateAddress: PROCEDURE [addr: PageAddress] =
    BEGIN
    ValidateFile[addr.file];
    ValidatePageNumber[addr.page];
    END;

  MarkPageUsableAndRelease: PROCEDURE [page: PageHandle] =
    BEGIN
    page.age ← new;
    page.errorStatus ← ok;
    ReleasePage[page];
    ReleaseCache[];
    END;

  IncrementFileUseCount: PROCEDURE [file: FileHandle] = INLINE
    {file.useCount ← file.useCount + 1};

  DecrementFileUseCount: PROCEDURE [file: FileHandle] = INLINE
    {file.useCount ← file.useCount - 1};

  END.