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