-- Copyright (C) 1981, 1982, 1984, 1985  by Xerox Corporation. All rights reserved. 
-- VMCacheOps.mesa, HGM, 17-Sep-85  2:20:57

-- Last edited by Wobber:   2-Nov-82 10:30:47
-- Last edited by Levin:  30-Apr-81 14:27:42

DIRECTORY
  Heap USING [systemZone],
  Inline USING [BITXOR, HighByte, LowByte, LowHalf],
  VMDefs USING [
    CantReadBackingStore, CantWriteBackingStore, Page, PageAddress, PageNumber, Start],
  VMPrivate USING [
    AcquireCache, AcquirePage, AddressToPageIndex, AllocateCacheIndex, CacheIndex,
    FileHandle, FileObject, FinalizeVMCacheMgr, HandleTable, InitializeVMCacheMgr,
    PageIndex, nilCacheIndex, PageHandle, ReleaseCache,
    ReleasePage, ValidateFile, ValidatePageNumber, WaitUntilStable];

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

  BEGIN OPEN VMDefs, VMPrivate;


  -- Types and Related Constants --

  handles: LONG POINTER TO HandleTable;
  hashTable: PACKED ARRAY HashIndex OF CacheIndex;

  PageMap: TYPE = PACKED ARRAY PageIndex OF CacheIndex;
  pageMap: PageMap;

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



  -- 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, index];
    ReleaseCache[];
    RETURN[page.pointer]
    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 AND p.file = NIL THEN
      RemoveFromPageTable[p];
    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 {p.age ¬ old; ReleaseCache[]; VMDefs.Start[page]; AcquireCache[]};
      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, 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;
    page.useCount ¬ page.useCount + 1;
    MarkPageUsableAndRelease[page];
    RETURN[page.pointer]
    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;

  -- Procedures and Signals Exported to VMPrivate --

  -- Start/Stop --

  InitializeVMCache: PUBLIC PROCEDURE [min, max: CacheIndex, first: LONG POINTER] =
    BEGIN
    handles ¬ Heap.systemZone.NEW[HandleTable [max]];
    FOR index: CacheIndex IN [0..max) DO handles[index] ¬ NIL; ENDLOOP;
    FOR vmpage: PageIndex IN PageIndex DO
      pageMap[vmpage] ¬ nilCacheIndex; ENDLOOP;
    FOR bin: HashIndex IN HashIndex DO hashTable[bin] ¬ nilCacheIndex; ENDLOOP;
    InitializeVMCacheMgr[handles, min, max, first];
    END;

  FinalizeVMCache: PUBLIC PROCEDURE = {
    FinalizeVMCacheMgr[]; Heap.systemZone.FREE[@handles]};

  -- Handle Table Management --

  AddressToHandle: PUBLIC PROCEDURE [address: VMDefs.Page] RETURNS [PageHandle] =
    BEGIN
    RETURN[IndexToHandle[pageMap[AddressToPageIndex[address]]]];
    END;
    
  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;

  -- 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.index];
    IncrementFileUseCount[page.file];
    END;

  -- Page Table Management --

  BogusPageIndex: ERROR = CODE;
  EnterInPageTable: PUBLIC PROCEDURE [page: PageHandle, index: CacheIndex] =
    BEGIN
    IF index > PageIndex.LAST THEN ERROR BogusPageIndex;
    IF pageMap[page.index] # nilCacheIndex THEN ERROR AttemptToReusePageMapSlot;
    pageMap[page.index] ¬ 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.index];
    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
    XORBytes: PROCEDURE [word: UNSPECIFIED] RETURNS [UNSPECIFIED] = INLINE
      -- XORs the two bytes of 'word'.
      BEGIN
      RETURN[Inline.BITXOR[Inline.HighByte[word], Inline.LowByte[word]]];
      END;
    RETURN[XORBytes[Inline.BITXOR[Inline.LowHalf[addr.file], addr.page]] MOD hashBins]
    END;

  -- Page Table Management --

  RemoveFromPageTable: PROCEDURE [page: PageHandle] =
    -- destroys the correspondance between page 'page.pointer' and the page object.
    BEGIN
    IF IndexToHandle[pageMap[page.index]] # page THEN ERROR InconsistentPageMap;
    pageMap[page.index] ¬ nilCacheIndex;
    END;

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