// IfsLeafVMemRes.bcpl - Leaf VMem - RESIDENT
// Copyright Xerox Corporation 1979

// Last modified by Wobber, April 9, 1981  2:51 PM
// Last modified by Butterfield, October 29, 1979  5:32 PM

get ecNoFileMap, ecLeafVMemPageMoved, ecLeafHashZero, ecLeafHashTableFull,
 ecLeafVMemFull, ecLeafHashTableBroken, ecBadLeafPageState, ecPageNotDirty,
 ecLeafMultiplePageIO, ecVPBIPageNumberWrong from "IfsLeafErrors.decl";
get SCB, vpbiReads, vpbiWrites, vpbiDiskReads, vpbiDiskWrites from
 "IfsSequin.decl";
get "IfsLeaf.decl";
get "IfsLeafVMem.decl";

external
[
//outgoing procedures
LeafGetPage; LeafDOPAGEIO; LeafPageType;
LeafPageGroupSize; LeafPageGroupBase; LeafPageGroupAlign;
LeafUndirtyPage; LeafUnlockPage;

//incoming procedures
Allocate; Block; CallProc; DoubleIncrement; DoubleDifference;
Free; IFSError; IndexedPageIO; LockCell; LockZero; MorePageIO;
MoveBlock; UnlockCell; @VRRP; @VWRP; Yield;

//incoming statics
LastLockedCell; leafVMI; sysZone; scb; vpbiLVMD;
]

// Top-level procedures to access a specified page of a file designated by
// a Leaf Virtual Memory Descriptor (LVMD).  File page numbers are used;
// i.e., page zero is the leader page, page 1 is the first data page, etc.

//----------------------------------------------------------------------------
let LeafGetPage(lvmd, filePage, op) = valof
//----------------------------------------------------------------------------
[
unless op<<GetPageOp.inCore do Yield();
if lvmd eq 0 then IFSError(ecNoFileMap);

// find old hash table entry
let leafPage = 0;
let page = LeafHash(lvmd, filePage);
test page eq 0
   ifso
      [
      // No hash table entry, make one if not inCoreOnly.
      if op<<GetPageOp.inCore then resultis 0;
      for lPage = lv leafVMI>>LeafVMI.pages↑1 to
       lv leafVMI>>LeafVMI.pages↑lastLeafPage by lenLeafPage do
        if lPage>>LeafPage.probe eq 0 then [ leafPage = lPage; break; ]
      if leafPage eq 0 then IFSError(ecLeafVMemFull);
      if leafPage>>LeafPage.flushLock ne 0 then IFSError(ecBadLeafPageState);
      let probe = leafVMI>>LeafVMI.lastFreeProbe;
      page = (leafPage-lv leafVMI>>LeafVMI.pages) rshift logLenLeafPage;
      leafPage>>LeafPage.lvmd = lvmd; leafPage>>LeafPage.page = filePage;
      leafPage>>LeafPage.flagByte = 0; leafPage>>LeafPage.probe = probe;
      leafPage>>LeafPage.readRefs = 1;   // Must be done before MorePageIO.
      LockCell(lv leafPage>>LeafPage.address, LeafLock);
      leafVMI>>LeafVMI.hashTable↑probe = page;
      ]
   ifnot
      [
      leafPage = lv leafVMI>>LeafVMI.pages↑page;
      if op<<GetPageOp.inCore & (leafPage>>LeafPage.writing %
       leafPage>>LeafPage.address eq 0) then resultis 0;

      // The code below insures that only the original reader may be
      //  inside the VMem and that there will be no simultaneous writing.
      //  Note that the page = 0 branch will also not allow writing.
      //  We reference count read accesses so that the page is not taken
      //  away until everyone gets a turn at it.
      let readRefs = leafPage>>LeafPage.readRefs;
      leafPage>>LeafPage.readRefs = readRefs + 1;
      while leafPage>>LeafPage.writing %
       (leafPage>>LeafPage.address eq 0 & readRefs ne 0) do Block();
      ]

// N.B.  This is so the IndexedPageIO inside LeafDoPageIO will NEVER
//  have to call MorePageIO.  This is a must since we always write a
//  full page on the last logical file page and therefore need an extra one!!
//  MorePageIO returns quickly if enough pages are known/allocated.
let dirty = op<<GetPageOp.dirty ne 0;
MorePageIO(lv lvmd>>LVMD.fmap, filePage, 0, (dirty? 2,1), -1);

let oldAddress = leafPage>>LeafPage.address;
leafPage>>LeafPage.dontRead = op<<GetPageOp.noRead;
if op<<GetPageOp.lock then leafPage>>LeafPage.locked = true;
let address = dirty?
 VWRP(leafVMI>>LeafVMI.vmd.base + page lshift logVPagesPerLeafPage),
  VRRP(leafVMI>>LeafVMI.vmd.base + page lshift logVPagesPerLeafPage);
if dirty then leafPage>>LeafPage.dirty = true;
test oldAddress eq 0
 ifso leafPage>>LeafPage.address = address;
 ifnot if address ne oldAddress then IFSError(ecLeafVMemPageMoved);
leafPage>>LeafPage.readRefs = leafPage>>LeafPage.readRefs - 1;
resultis address;
]

//----------------------------------------------------------------------------
and FreeLeafPage(leafPage) be
//----------------------------------------------------------------------------
[
let probe = leafPage>>LeafPage.probe; leafPage>>LeafPage.probe = 0;
leafVMI>>LeafVMI.hashTable↑probe = leafVMI>>LeafVMI.freePage;
leafVMI>>LeafVMI.freePageCount = leafVMI>>LeafVMI.freePageCount + 1;
UnlockCell(lv leafPage>>LeafPage.address);
]

//----------------------------------------------------------------------------
and LeafHash(lvmd, filePage, rehashFlag; numargs na) = valof
//----------------------------------------------------------------------------
// if successful, return Leaf VMem page number
// otherwise return 0 and store lastFreeProbe.
// if rehashFlag, don't stop on encountering an "empty" probe
[
let probe = lvmd>>LVMD.fileIndex + filePage + 1; //(the 1 helps avoid probe 0)
probe = probe rshift logLenLeafHashTable + probe & probeMask;
let firstProbe = probe; let increment =  - probe lshift 1 - 1;
let firstFree = noFree; let page = nil;
   [
   if probe eq 0 then loop;
   page = leafVMI>>LeafVMI.hashTable↑probe;
   if (page & freePageMask) ne 0 then
      [
      if page ne leafVMI>>LeafVMI.freePage & (na ls 3 % not rehashFlag) break;
      if firstFree eq noFree then firstFree = probe;
      DoubleIncrement(lv leafVMI>>LeafVMI.freeProbes); loop;
      ]
   if leafVMI>>LeafVMI.pages↑page.lvmd eq lvmd &
    leafVMI>>LeafVMI.pages↑page.page eq filePage then
      [
      if firstFree ne noFree then  // can we make it better?
         [
         leafVMI>>LeafVMI.hashTable↑probe = leafVMI>>LeafVMI.freePage;
         leafVMI>>LeafVMI.hashTable↑firstFree = page;
         leafVMI>>LeafVMI.pages↑page.probe = firstFree
         ]
      if page eq 0 then IFSError(ecLeafHashZero); resultis page
      ]
      DoubleIncrement(lv leafVMI>>LeafVMI.fullProbes);
   ] repeatwhile valof
      [
      probe = probe + increment & probeMask;
      if probe eq firstProbe test firstFree eq noFree
         ifso IFSError(ecLeafHashTableFull); ifnot break;
      resultis true;
      ]
leafVMI>>LeafVMI.lastFreeProbe = (firstFree ne noFree? firstFree, probe);
resultis 0;
]

//----------------------------------------------------------------------------
and LeafUndirtyPage(lvmd, filePage) be
//----------------------------------------------------------------------------
[
let page = LeafHash(lvmd, filePage);
if page eq 0 then IFSError(ecLeafHashZero);
leafVMI>>LeafVMI.pages↑page.dirty = false;
]

//----------------------------------------------------------------------------
and LeafUnlockPage(lvmd, filePage) be
//----------------------------------------------------------------------------
[
let page = LeafHash(lvmd, filePage);
if page eq 0 then IFSError(ecLeafHashZero);
leafVMI>>LeafVMI.pages↑page.locked = false;
]

//----------------------------------------------------------------------------
and LeafLock(leafPage, newAddress, flag) = valof
//----------------------------------------------------------------------------
[
unless flag do resultis (leafPage>>LeafPage.flushLock eq 0);
let page = LeafHash(leafPage>>LeafPage.lvmd, leafPage>>LeafPage.page);
let probe = leafPage>>LeafPage.probe;
if page ne leafVMI>>LeafVMI.hashTable↑probe %
 page ne (leafPage - lv leafVMI>>LeafVMI.pages) rshift logLenLeafPage then
 IFSError(ecLeafHashTableBroken);  //*
if leafPage>>LeafPage.flushLock ne 0 then IFSError(ecBadLeafPageState);
if newAddress ne 0 then resultis true;
test leafPage>>LeafPage.dirty
   ifso leafPage>>LeafPage.writing = true;
   ifnot FreeLeafPage(leafPage);
//N.B. freePageCount is a deletion count, not a count of free's
if leafVMI>>LeafVMI.freePageCount ge maxFreePageCount then
   [
   leafVMI>>LeafVMI.freePageCount = 0;
   leafVMI>>LeafVMI.freePage = leafVMI>>LeafVMI.freePage + 1;
   if (leafVMI>>LeafVMI.freePage & freePageMask) eq 0 then
    leafVMI>>LeafVMI.freePage = firstFreePage;
   for leafPage = lv leafVMI>>LeafVMI.pages↑1 to
    lv leafVMI>>LeafVMI.pages↑lastLeafPage by lenLeafPage do
     if leafPage>>LeafPage.probe ne 0 then
      if LeafHash(leafPage>>LeafPage.lvmd, leafPage>>LeafPage.page, true)
       ne (leafPage - lv leafVMI>>LeafVMI.pages) rshift logLenLeafPage then
       IFSError(ecLeafHashTableBroken);  //*
   ]
resultis true;  // (let the VMem package zero address)
]

// Underlying procedures called by VMEM

//----------------------------------------------------------------------------
and LeafPageType(vmd, vPage) = 1;
//----------------------------------------------------------------------------
and LeafPageGroupSize(vmd, vPage) = -1 lshift leafPageGroupSize;
//----------------------------------------------------------------------------
and LeafPageGroupBase(vmd, vPage) = vPage & (-1 lshift leafPageGroupSize);
//----------------------------------------------------------------------------
and LeafPageGroupAlign(vmd, vPage) = (1 lshift leafPageGroupSize) - 1;
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
and LeafDOPAGEIO(vmd, vPage, core, np, wflag) be
//----------------------------------------------------------------------------
[
//assumes np is non-zero and an even number of disk pages
let leafPage = lv leafVMI>>LeafVMI.pages↑
 ((vPage - leafVMI>>LeafVMI.vmd.base) rshift logVPagesPerLeafPage);

// This assumes that if LeafLock(true) was called and the page wasn't
// dirty, (for Leaf,) then LeafDOPageIO was called immediately thereafter.
// If another process ran in between, then all hell breaks loose.
if leafPage>>LeafPage.probe eq 0 then return;

let lvmd = leafPage>>LeafPage.lvmd; let page = leafPage>>LeafPage.page;
if np rshift logVPagesPerLeafPage ne 1 then IFSError(ecLeafMultiplePageIO);
//if wflag & not leafPage>>LeafPage.dirty then IFSError(ecPageNotDirty);
if lvmd eq vpbiLVMD then
   [
   if wflag & page ne core!8 then IFSError(ecVPBIPageNumberWrong);
   DoubleIncrement(wflag? lv scb>>SCB.vpbiWrites, lv scb>>SCB.vpbiReads);
   ]

let cleaningVMem = false;
if leafPage>>LeafPage.address ne 0 then
   [
   //*** N.B. The following assumes that no lock cells are used for Leaf
   //  other than those in the LeafVMI.  This is necessary because
   //  when we are here, the VMem package is 'cleaning' the page without
   //  invalidating the LockCell entry.  We must know if the page is
   //  locked by someone other than the LeafPage with which we were called.
   //  By prohibiting other LockCells, LeafPage.locked will reflect the
   //  dirty state after cleaning since that's what we told it in LeafLock.
   //  ...We should not already be writing the page since the VMem package
   //  will remove the page from the chain in that event.
   unless wflag do IFSError(ecBadLeafPageState);
   unless leafPage>>LeafPage.dirty do return;
   leafPage>>LeafPage.dirty = leafPage>>LeafPage.locked;
   cleaningVMem = true;
   ]

if not wflag & leafPage>>LeafPage.dontRead then
   [ leafPage>>LeafPage.dontRead = false; return; ] 

if lvmd eq vpbiLVMD do DoubleIncrement(wflag? lv scb>>SCB.vpbiDiskWrites,
 lv scb>>SCB.vpbiDiskReads)
CallProc(IndexedPageIO, lv lvmd>>LVMD.fmap, page, core, 1, (wflag? -1, 0));

if wflag & not cleaningVMem then
   [
   leafPage>>LeafPage.writing = false;
   test leafPage>>LeafPage.readRefs eq 0
      ifso FreeLeafPage(leafPage);
      ifnot leafPage>>LeafPage.dirty = false;
   ]
]

//find the per insertion cost for varying rehashing intervals
//let size be the table size
//let frees be the number of free markers
//let insertions be the number of insertions which separate rehashes
//let entries be the average number of entries in the table
//note that deletions equal insertions to within entries
//let full be the probabilty that an entry is full
// full = entries / size
//let fullsum = full + full↑2 + full↑3 ... = 1 / (1 / full - 1)
//let reads be the number of reads which separate rehashes
//let useage = reads / (reads + insertions)
//let rehashfree be the number of free that are generated by rehashing
// rehashfree = entries * (1 - useage) * fullsum
//let oldfree be the number of free that remain from the last use of this free
// oldfree = (oldfree + rehashfree + insertions)
//  * (1 - 1 / size) ↑ (frees * insertions)
//let free be the probability that an entry is free;
// free = (oldfree + rehashfree + deletions) / size
//let extra be the probability that an entry is not empty;
// extra = full + free
//let extrasum = extra + extra↑2 + extra↑3 ... = 1 / (1 / extra - 1)
//let extratotal be the sum of extrasum for all the insertions
//let insertone be the cost to insert with one probe
//let probe be the cost of an extra probe
//let inserttotal be the cost to insert
// inserttotal = insertions * insertone + probe * extrasumtotal
//let rehashone be the cost to rehash one entry with one probe
//let rehashprobe be the cost of an extra rehash probe
//let rehash be the cost to rehash
// rehash = entries * (rehashone + rehashprobe * (useage * fullsum
//  + (1 - useage) * extrasum)
//note that extrasum is for worst case, i.e. largest, free
//let total be the total cost per rehash
// total = rehash + inserttotal
//let average = total / insertions
//
//plug in some numbers
//size = 256, frees = 128
//
//simplify
//with insertions > 10, oldfree becomes < 1 even with old oldfree = size 
// oldfree = 0
//with useage = 0
// rehashfree = entries * fullsum 
// rehash = entries * (rehashone + rehashprobe * extrasum)
//
//try it
//let entries = 32, i.e. it stays full
// full = 1/8, fullsum = 1/7, rehashfree = 32/7
// extrasum(i) = 1 / (1 / ((256 + 7 * i) / 1792) - 1)
//
//HP-21 results
// rehashone = insertone, rehashprobe = probe, probe * n = insertone
// n=2: insertions = 95, n=3: insertions = 106, n=4: insertions = 115
//N.B. The above does not consider the possibility of overwriting frees