// 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<<GetPageOp.lock = true;
let vPageAddr = GetVPBIPage(vpbiID<<VPBIID.page, op);
if vPageAddr eq 0 resultis 0;
let vpbiOffset = vPageAddr!(vpbiID<<VPBIID.index);
if vpbiOffset eq 0 then IFSError(ecNonExistantVPBI);
let vpbi = vPageAddr + vpbiOffset;
unless dontLock do
   [
   vPageAddr>>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);
]