// IfsLeafVPBIUtil.bcpl - Virtual PBI Utilities // Copyright Xerox Corporation 1979 // Last modified by Wobber, March 26, 1981 11:25 AM get ecPreallocateBroken, ecMalformedVPBIPage, ecNonExistantVPBI, ecUnlockedVPBI, ecBadVPBILock, ecNoFreeVPBIPages, ecLeafAnswerTooLong, ecVPBIBackChain, ecVPBIPageZero, ecBadFreeVPageCall, ecOutOfSequence from "IfsLeafErrors.decl"; get "IfsLeaf.decl"; get "IfsSequin.decl"; external [ //outgoing procedures GetVPBI; ReadVPBI; ReleaseVPBI; ShortenVPBI; UnlockVPBI; AllocateVPBIPage; ScanVPBIPage; //incoming procedures IFSError; LeafGetPage; LeafUndirtyPage; LeafUnlockPage; SequinKickReaper; SetTimer; TimerHasExpired; Zero; //incoming statics scb; lenPup; vpbiLVMD; ] //---------------------------------------------------------------------------- let GetVPBI(alloc) = valof //---------------------------------------------------------------------------- [ // Allocate a new vpbi, using alloc as the allocation info block... let vPage = alloc>>AllocInfo.vPageQ.tail; let vpbiIndex = alloc>>AllocInfo.nextVPBI; if vPage eq 0 % vpbiIndex ge vpbiPerPage % alloc>>AllocInfo.nextOffset + lenVPBIOverhead + lenPup gr wordsPerPage then [ vPage = alloc>>AllocInfo.nextVPage; if vPage eq 0 then IFSError(ecPreallocateBroken); alloc>>AllocInfo.nextVPage = AllocateVPBIPage(); alloc>>AllocInfo.vPageQ.tail = vPage; vpbiIndex = 0; ] // Set allocLock, (the upper byte of allocWord,) so that the reaper may // not deallocate this page before the allocation is finished. alloc>>AllocInfo.allocLock = true; let vPageAddr = GetVPBIPage(vPage, dirtyPage + lockOp + ((vpbiIndex eq 0)? dontReadOp, 0)); // It is intentional to pick up nextVPBI and nextOffset here because // GetVPBIPage may block allowing the whole current VPBI page to be reused. if alloc>>AllocInfo.nextVPBI eq 0 then vpbiIndex = 0; let vpbiOffset = alloc>>AllocInfo.nextOffset; if vpbiIndex eq 0 then [ vpbiOffset = offset VPageHeader.vpbis/16; Zero(vPageAddr,lenVPageHeader); vPageAddr>>VPageHeader.vPage = vPage; vPageAddr>>VPageHeader.allocInfo = alloc; vPageAddr>>VPageHeader.link = alloc>>AllocInfo.nextVPage; ] let vpbi = vPageAddr + vpbiOffset; Zero(vpbi, lenVPBIOverhead + pupOvWords); vpbi>>VPBI.pbi.pup.length = pupOvBytes; vpbi>>VPBI.locked = true; vpbi>>VPBI.vpbiID.index = vpbiIndex; vpbi>>VPBI.vpbiID.page = vPage; vPageAddr!vpbiIndex = vpbiOffset; vpbi>>VPBI.pageOffset = vpbiOffset; // Set nextVPBI and clear allocLock. alloc>>AllocInfo.allocWord = vpbiIndex + 1; alloc>>AllocInfo.nextOffset = vpbiOffset + lenVPBIOverhead + lenPup; vPageAddr>>VPageHeader.vpbiCount = vPageAddr>>VPageHeader.vpbiCount + 1; vPageAddr>>VPageHeader.lockCount = vPageAddr>>VPageHeader.lockCount + 1; SetTimer(lv vPageAddr>>VPageHeader.time, reaperInterval); scb>>SCB.normalScan = true; resultis vpbi; ] //---------------------------------------------------------------------------- and ShortenVPBI(vpbi) be //---------------------------------------------------------------------------- [ let length = vpbi>>VPBI.pbi.pup.length; if vpbi>>VPBI.output & length - pupOvBytes gr (vpbi>>VPBI.sequin)>>Sequin.pupDataBytes then IFSError(ecLeafAnswerTooLong); let pageOffset = vpbi>>VPBI.pageOffset; let alloc = (vpbi - pageOffset)>>VPageHeader.allocInfo; if vpbi>>VPBI.vpbiID.page eq alloc>>AllocInfo.vPageQ.tail & vpbi>>VPBI.vpbiID.index eq alloc>>AllocInfo.nextVPBI - 1 then alloc>>AllocInfo.nextOffset = pageOffset + lenVPBIOverhead + (length+1)/2; ] //---------------------------------------------------------------------------- and ReleaseVPBI(vpbi) = valof //---------------------------------------------------------------------------- [ let vpbiOffset = vpbi>>VPBI.pageOffset; let vPageAddr = vpbi - vpbiOffset; let index = vpbi>>VPBI.vpbiID.index; if vPageAddr!index ne vpbiOffset then IFSError(ecMalformedVPBIPage); let sequin = vpbi>>VPBI.sequin; unless sequin eq 0 % vpbi>>VPBI.released do [ let reapState = vpbi>>VPBI.output? lv sequin>>Sequin.ackedState, lv sequin>>Sequin.inputState; if vpbi>>VPBI.sequence ne reapState>>ReapState.reaped then IFSError(ecOutOfSequence); reapState>>ReapState.reaped = reapState>>ReapState.reaped + 1; sequin>>Sequin.ancientVPBIs = vpbi>>VPBI.ancient; ] if vpbi>>VPBI.locked then [ vpbi>>VPBI.released = true; resultis false; ] vPageAddr!index = 0; let vpbiCount = vPageAddr>>VPageHeader.vpbiCount - 1; vPageAddr>>VPageHeader.vpbiCount = vpbiCount; if vpbiCount ne 0 resultis false // Now update the queue. let alloc = vPageAddr>>VPageHeader.allocInfo; let vPage = vPageAddr>>VPageHeader.vPage; if vPage eq alloc>>AllocInfo.vPageQ.tail then [ alloc>>AllocInfo.nextVPBI = 0; alloc>>AllocInfo.nextOffset = 0; LeafUndirtyPage(vpbiLVMD, vPage); resultis true; ] if vPage eq alloc>>AllocInfo.vPageQ.head then [ FreeVPBIPage(vPage); alloc>>AllocInfo.vPageQ.head = vPageAddr>>VPageHeader.link; ] resultis true; ] //---------------------------------------------------------------------------- and ScanVPBIPage(vPage, alloc, lvLinkPage) = valof //---------------------------------------------------------------------------- [ // This procedure scans a vpbi page and releases it if possible. // If the page cannot be freed, the virtual page number is linked // into the page described by @lvLinkPage. If this is zero, the // ancient queue for 'alloc' is assumed empty and the head of that // queue is used for the link. After this linking is accomplished // @lvLinkPage and the ancient queue tail are updated to refer to // new queue entry. // The procedure always returns zero upon finding a vPage that is // not yet 5 seconds old. The same is true if the vPage queue tail // is encountered and that page either has no vpbis or is locked due // to a concurrent vpbi allocation on that page. Otherwise, the // page is scanned and the number of next vPage in the queue is // returned. let vPageAddr = GetVPBIPage(vPage, dirtyPage); unless vPageAddr>>VPageHeader.ancient % TimerHasExpired(lv vPageAddr>>VPageHeader.time) do resultis 0; if vPage eq alloc>>AllocInfo.vPageQ.tail then // Note that allocWord < 0 means locked, 0 means no vpbis. test alloc>>AllocInfo.allocWord le 0 ifso resultis 0; ifnot alloc>>AllocInfo.vPageQ.tail = 0; for i = 0 to vpbiPerPage-1 do if vPageAddr!i ne 0 then [ let vpbi = vPageAddr + vPageAddr!i; if vPageAddr!i ne vpbi>>VPBI.pageOffset then IFSError(ecMalformedVPBIPage); let sequin = vpbi>>VPBI.sequin; // The only time this can be zero is when a vpbi // has been allocated and not put or released yet. if sequin eq 0 then [ vpbi>>VPBI.ancient = true; loop; ] let output = vpbi>>VPBI.output ne 0; let reapState = output? lv sequin>>Sequin.ackedState, lv sequin>>Sequin.inputState; // The following assumes that 2^^15 vpbis would represent a large // space compared with total vpbi buffering capacity. // If the sequence number is less than the current sequence, // (ie. acked), the vpbi should be releasable. ReleaseVPBI will // catch the error if we are freeing a sequence # less than reaped. // ReleaseVPBI will never affect the vPageQ here because the vPageQ // head and tail have been zeroed. if (vpbi>>VPBI.sequence - reapState>>ReapState.reaped) le 0 & not (output & sequin>>Sequin.retransmitting) & (vpbi>>VPBI.sequence - reapState>>ReapState.current ls 0 % sequin>>Sequin.state eq destroyedState) then if ReleaseVPBI(vpbi) break; sequin>>Sequin.ancientVPBIs = true; vpbi>>VPBI.ancient = true; ] // Now remove from the queue pages that have been cleaned up.. // AND pages that had no vpbis on entry. let nextPage = vPageAddr>>VPageHeader.link; test vPageAddr>>VPageHeader.vpbiCount eq 0 ifso FreeVPBIPage(vPage); ifnot [ // if vPageLock is zero here we must get the link page. vPageAddr>>VPageHeader.ancient = true; test @lvLinkPage eq 0 ifso alloc>>AllocInfo.ancientQ.head = vPage; ifnot [ let linkPageAddr = GetVPBIPage(@lvLinkPage, dirtyPage); linkPageAddr>>VPageHeader.link = vPage; ] @lvLinkPage = vPage; alloc>>AllocInfo.ancientQ.tail = vPage; ] resultis nextPage; ] //---------------------------------------------------------------------------- and ReadVPBI(vpbiID, op, dontLock; numargs na) = valof //---------------------------------------------------------------------------- [ if na ls 3 then dontLock = false; unless dontLock do op<>VPageHeader.lockCount = vPageAddr>>VPageHeader.lockCount + 1; vpbi>>VPBI.locked = true; ] resultis vpbi; ] //---------------------------------------------------------------------------- and UnlockVPBI(vpbi) be //---------------------------------------------------------------------------- [ // Decrements lock count and frees up lock if possible. unless vpbi>>VPBI.locked return; let vPageAddr = vpbi - vpbi>>VPBI.pageOffset; let lockCount = vPageAddr>>VPageHeader.lockCount - 1; if lockCount ls 0 then IFSError(ecUnlockedVPBI); vPageAddr>>VPageHeader.lockCount = lockCount; vpbi>>VPBI.locked = false; if lockCount eq 0 then LeafUnlockPage(vpbiLVMD, vPageAddr>>VPageHeader.vPage); if vpbi>>VPBI.released then ReleaseVPBI(vpbi); ] //---------------------------------------------------------------------------- and AllocateVPBIPage() = valof //---------------------------------------------------------------------------- [ // Allocate VPBI page from supplied bit map. // Search bitmap for free page for next allocation. let wordIndex = -1; let bitMap = lv scb>>SCB.vpbiPageBitMap; for i = 0 to lenVPBIPageBitMap-1 if bitMap!i ne -1 then [ wordIndex = i; break; ] if wordIndex eq -1 then IFSError(ecNoFreeVPBIPages); let bitWord = bitMap!wordIndex; let bitMask = #100000; let pageNumber = wordIndex lshift 4 + 1; until (bitWord & bitMask) eq 0 do [ pageNumber = pageNumber + 1; bitMask = bitMask rshift 1; ] bitMap!wordIndex = bitWord % bitMask; resultis pageNumber ] //---------------------------------------------------------------------------- and FreeVPBIPage(vPage) be //---------------------------------------------------------------------------- [ LeafUndirtyPage(vpbiLVMD, vPage); vPage = vPage - 1; let wordIndex = vPage rshift 4; let bitMap = lv scb>>SCB.vpbiPageBitMap; let bitWord = bitMap!wordIndex; let bitMask = #100000 rshift (vPage & #17); if (bitWord & bitMask) eq 0 then IFSError(ecBadFreeVPageCall); bitMap!wordIndex = bitWord & not bitMask; ] //---------------------------------------------------------------------------- and GetVPBIPage(vPage, op) = valof //---------------------------------------------------------------------------- [ if vPage eq 0 then IFSError(ecVPBIPageZero); resultis LeafGetPage(vpbiLVMD, vPage, op); ]