// 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<>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<>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<>LVMD.fmap, filePage, 0, (dirty? 2,1), -1); let oldAddress = leafPage>>LeafPage.address; leafPage>>LeafPage.dontRead = op<>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