#define SCCSID  "@(#)vmksh.c    6.8 91/10/30"

/*
 *       IBM/Microsoft Confidential
 *
 *       Copyright (c) IBM Corporation 1987, 1989
 *       Copyright (c) Microsoft Corporation 1987, 1989
 *
 *       All Rights Reserved
 */

#define INCL_DOSERRORS
#define INCL_OS2STD
#include <os2.h>
#define INCL_DOSP
#include <os2p.h>
#define FNO_NUM  FNO_VMKSH_C
#include <fnomem.h>
#include <osmac.h>
#include <vmowner.h>
#include <mi.h>
#include <pgexport.h>
#include <vmexport.h>
#include <vmlocal.h>
#include <tkexport.h>
#include <vmkh.h>            // must be after tkexport.h for KSEM definition
#include <string.h>

int vmSetupSpecialKSHB ( VMKSH *pksh, ulong_t fl, ulong_t cb, ulong_t *fused,
             VMKSHD  *pcr, VMKSHD  *ppv, VMKSHD  *pnw);

#define ksh_fALLOCATED_BMP        0
#define ksh_fNO_ALLOCATED_BMP     1
#define ksh_fBMP_USED             2
#define ksh_MIN_FREE_BLOCK_SIZE   16 // sizeof(VMKSHB)+MIN_BLOCK_SIZE
#define ksh_fNO_FIT               -1

/***LD+ Global Swappable Heap Data */

VMKSHD          *pkshdVMDescs;          /* Pointer to array of BMP32 managed
/*end*/




/***LP  vmAllocKSHB - Allocate kernel swappable heap block
 *
 *      This function allocates a block of memory from the specified
 *      kernel swappable heap.  Certain additional properties of the
 *      block are specifiable.
 *
 *      ENTRY           hkh             - Kernel swappable heap header handle
 *                                        created by VMCreateKH.  Special
 *                                        values map the public swappable
 *                                        heaps:
 *                                        - VM_HKH_PUB_SWAP_RW
 *                                          Public Swappable RW Heap
 *                                        - VM_HKH_PUB_SWAP_RO
 *                      cb              - Size of block requested in bytes
 *                      fl              - flags (optional)
 *                                      VMAC_ALIGNPAGE
 *                                        Page alignment requested
 *                                      VMAC_ALIGNPARA
 *                                        Paragraph alignment requested
 *                                      VMAC_NOXPAGE
 *                                        Block not to cross page boundary
 *                                        (header can start on preceding page)
 *                                      VMAC_MAYLLOCK
 *                                        Block may be long-term locked
 *                                          (advisory only, forces page align)
 *                                      PG_U
 *                                        Memory to be user addressible
 *                                        (via device driver init and sysinit)
 *
 *                      hobOwner        - Owner of heap block
 *                      pkhbi           - Address of location in which pointer
 *                                        to block will be returned
 *      RETURN          int             - Result code (NO_ERROR if successful)
 */
int vmAllocKSHB(hkh, cb, fl, hobOwner, pkhbi)
VMHKH           hkh;                    /* Swappable heap header handle */
ulong_t         cb;                     /* Size of block requested */
ulong_t         fl;                     /* flags */
VMHOB           hobOwner;               /* Owner of heap block */
VMKHBI          *pkhbi;
{
    register VMKSHD  *pcurr;   /* pointer to current free block descriptor */
    VMKSHD  *pprev;   /* pointer to previous free block descriptor */
    VMKSHD  *pnew;    /* pointer to new free block descriptor */
    VMKSHB  *pkshb;
    ulong_t rc;             /* return code */
    ulong_t cbRound;
    ulong_t cbNewCommit;
    ulong_t hob_sel;
    ulong_t fkshd_used;
    VMKSH   *pksh;          /* Pointer to swappable heap header */

    /*
     *  Validate heap handle and convert to heap header pointer.
     */

    vmAssert(vmIsHKSH(hkh));
    pksh = apkh[hkh].kh_pksh;

    /*
     *  BUGBUG IDB 10/20/89 - Mask out memory type since it must be swappable.
     *  Later assert that callers have not spacefied a memory type.
     */

    fl &= ~PG_STATE;

    /*
     *  Validate flags.  Check only permitted flags given, request size
     *  non-zero and either crossing of page boundaries is allowed or
     *  request is not too large to avoid boundary crossing.
     */

    vmAssert((fl ==
      (fl & (VMAC_SELALLOC|VMAC_NOXPAGE|VMAC_ALIGNMASK|VMAC_MAYLLOCK|PG_U))) &&
      ((!(fl & VMAC_NOXPAGE)) || cb <= PAGESIZE));

   /***
    *  If PG_U specified, force page alignment because we cannot
    *  start the block on a page which does not have PG_U set.
    */

    if(fl & PG_U)
    {
        fl = (fl & ~VMAC_ALIGNMASK) | VMAC_ALIGNPAGE;
    }

  /*
   *  If paragraph alignment request, or block may be long-term locked, force
   *  page alignment.
   *  BUGBUG - IDB 03/09/90 - The swappable heap is due for a rewrite
   *  so for paragraph alignment this is a temporary hack.
   */
    if(vmAlignParaReq(fl) || (fl & VMAC_MAYLLOCK))   /* bugbug para to page */
    {

        fl = (fl & ~VMAC_ALIGNMASK) | VMAC_ALIGNPAGE;
    }

    rc=0;
    cbRound = kshRoundUp(cb);   /* round up request to multiple of 8      */

    /***
    *  If were going to need page or para or no cross page blocks
    *  pre-allocate a BMP32 record for the Block Descriptor, one for the new
    *  free block (if any)
    */
    if (fl & (VMAC_NOXPAGE|VMAC_ALIGNPAGE|VMAC_ALIGNPARA))
    {
       if((rc=BMPGet(pkshdVMDescs, SSToDS(&pnew))) != NO_ERROR)
       {
          return(rc);
       }
       fkshd_used = ksh_fALLOCATED_BMP;
    }
    else
    {
       fkshd_used = ksh_fNO_ALLOCATED_BMP;
    }

    rc = KSEMRequestMutex((HKSEM)&(pksh->ksh_ksem), -1);

    if (rc != NO_ERROR)
    {
        if (fkshd_used == ksh_fALLOCATED_BMP)  /* free kshd if allocated */
        {
           BMPFree(pkshdVMDescs, pnew);
        }
        return(rc);
    }

    /***
    *   if Size is greater than HintSize start with hint pointers
    *     since all preceeding free blocks are smaller than the hint size
    */
    if (pksh->ksh_HintSize <= cbRound)
    {
        pcurr  = pksh->ksh_pHint;
        pprev  = pksh->ksh_pHPrev;
    }
    else
    {
        pcurr  = &pksh->ksh_hdrEntry;
        pprev  = &pksh->ksh_hdrEntry;
    }

    /***
    *    - Search free block chain until a free block is found that is >= Size
    *         save the largest free block along the way
    */

    while (cbRound > pcurr->kshd_size && pcurr->kshd_pNext != KSHENDLIST)
    {
cont_loop:;
        pprev = pcurr;                              /* prev = curr           */
        pcurr = pcurr->kshd_pNext;                  /* curr = curr.nx        */
    }

    if (fl & (VMAC_NOXPAGE|VMAC_ALIGNPAGE|VMAC_ALIGNPARA))
    {
        rc=vmSetupSpecialKSHB(pksh,fl,cb,SSToDS(&fkshd_used),pcurr,pprev,pnew);

        if (rc == ksh_fNO_FIT)  {
            if (pcurr->kshd_pNext == KSHENDLIST)  {
                rc = ERROR_NOT_ENOUGH_MEMORY;     /*110210 - use meaningful rc*/
                goto exiterror;
            } else {
                goto cont_loop;
            }
        } else {
            if (fkshd_used == ksh_fBMP_USED)  {
               pprev = pnew;   /* we inserted new kshd so pprev now = pnew */
            }
        }
    }

    if (cbRound < pcurr->kshd_size) /*  SPLIT FIT : alloc partial free block */
    {
        /***
        *   A remaining size of 8 is worthless so tact it on to the caller's
        *   size and jump to the exact fit code
        */
        if ((cbRound+sizeof(VMKSHB)) == pcurr->kshd_size)
        {
            cbRound += sizeof(VMKSHB);
            goto exact_fit;
        }

        if (pcurr->kshd_pNext == KSHENDLIST)
        {
            cbNewCommit = kshPgRoundUp(((ulong_t)pcurr->kshd_pb+cbRound));
            if (cbNewCommit > (ulong_t) pksh->ksh_pbEndCom)
            {
                rc = VMSetMem((ulong_t) pksh->ksh_pbEndCom,
                                    cbNewCommit- (ulong_t)pksh->ksh_pbEndCom,
                                    HOBNULL,
                                    fl | pksh->ksh_fl,
                                    NA);
//              vmAssert(rc == NO_ERROR);
                if (rc == NO_ERROR)
                        pksh->ksh_pbEndCom = (char *)cbNewCommit;
                else
                        goto exiterror;
            }
        }

        /***
        *   set hints to new size and new free block
        */

        pksh->ksh_pHint    = pcurr;                       /* hintptr=new */
        pksh->ksh_HintSize = cbRound;                     /* hintsz = Size   */
        pksh->ksh_pHPrev   = pprev;                       /* hintPrev = prev */

        /***
        *   set kshb info
        */

        pkshb = (VMKSHB *)pcurr->kshd_pb;

        /***
        *  set return offset and redo free block links
        */

        pkhbi->khbi_pbData = pcurr->kshd_pb+sizeof(VMKSHB);

        pcurr->kshd_size   = pcurr->kshd_size - cbRound;
        pcurr->kshd_pb     = pcurr->kshd_pb + cbRound;
        KSEMReleaseMutex((HKSEM)&(pksh->ksh_ksem));
        kshWriteKSHB(pksh,pkshb,fl,pkhbi,kshbSetSize(cbRound),hobOwner,hob_sel);
    }
    else
    {
        if (cbRound == pcurr->kshd_size) /* EXACT FIT */
        {

exact_fit:
            if (pcurr->kshd_pNext == KSHENDLIST &&
                pksh->ksh_pbEndCom < pksh->ksh_pbEndRes)
            {
                rc = VMSetMem((ulong_t) pksh->ksh_pbEndCom,
                                    pksh->ksh_pbEndRes - pksh->ksh_pbEndCom,
                                    HOBNULL,
                                    fl | pksh->ksh_fl,
                                    NA);

                if (rc == NO_ERROR)
                    pksh->ksh_pbEndCom = pksh->ksh_pbEndRes;
                else
                    goto exiterror;
            }

            /***
            *  set return offset and redo free block links
            */

            pkhbi->khbi_pbData     = pcurr->kshd_pb+sizeof(VMKSHB);

            pprev->kshd_pNext = pcurr->kshd_pNext;  /* prev.next=curr.next */

            /***
            *   set kshb info
            */

            pkshb = (VMKSHB *)pcurr->kshd_pb;


            /***
            *   set hints to new size and new free block - if last block
            *   was allocated set hint ptrs to start to object,
            *   we must do this since the HintPrevPtr can not be set correctly
            */
            if (pcurr->kshd_pNext == KSHENDLIST)
            {
                pksh->ksh_pHint  = &pksh->ksh_hdrEntry;
                pksh->ksh_pHPrev = &pksh->ksh_hdrEntry;
            }
            else
            {
                pksh->ksh_pHint  = pprev->kshd_pNext;
                pksh->ksh_pHPrev = pprev;
            }

// bugbug   pksh->ksh_HintSize = cbRound;
// this might have been a jump to exact fit, if it was cbRound is off by 8

            pksh->ksh_HintSize = kshRoundUp(cb);

            BMPFree(pkshdVMDescs, pcurr);
            vmDecr_ksh_ckshds(pksh->ksh_ckshds);

            KSEMReleaseMutex((HKSEM)&(pksh->ksh_ksem));
            kshWriteKSHB(pksh,pkshb,fl,pkhbi,kshbSetSize(cbRound),hobOwner,hob_sel);
        }
        else  /* NO FIT - no free block can satisfy the request  */
        {
            rc = ERROR_NOT_ENOUGH_MEMORY;    /* Set return code  */
        }
    }
exiterror:;
    if (fkshd_used == ksh_fBMP_USED)
    {
        vmIncr_ksh_ckshds(pksh->ksh_ckshds);
    }
    else
    {
       if (fkshd_used == ksh_fALLOCATED_BMP)
            BMPFree(pkshdVMDescs, pnew);
    }

    /***
     *  clear semaphore here, if an error occurred
     */
    if (rc != NO_ERROR)  {
       KSEMReleaseMutex((HKSEM)&(pksh->ksh_ksem));
    } else {
       vmIncr_ksh_cAllocs(rc,pksh->ksh_cAllocs);
    }
    vmAssert(vmIsValidKSH(pksh));

    return(rc);
}





/***LP  vmReallocKSHB - Realloc Kernel Swappable Heap Block
 *
 *      This function reallocates a block allocated from the specified kernel
 *      swappable heap.  If the new block size is larger than the original,
 *      a new block is created, the data copied and the original block is
 *      freed.
 *
 *      int vmReallocKSHB(VMHKH hkh, void **ppb, ulong_t cb, ulong_t fl);
 *
 *      ENTRY           hkh             - Kernel swappable heap header handle
 *                                        created by VMCreateKH.  Special
 *                                        values map the public swappable
 *                                        heaps:
 *                                        - VM_HKH_PUB_SWAP_RW
 *                                          Public Swappable RW Heap
 *                                        - VM_HKH_PUB_SWAP_RO
 *                      ppbData         - Pointer to location containing
 *                                        address of block to be reallocated.
 *                                        This address changes if the block is
 *                                        being grown.
 *                      cb              - New size of block data wanted
 *                      fl              - Allocation flags.  These must be
 *                                        specified if the block is being grown
 *                                        but have no effect on shrinkage of
 *                                        blocks.
 *
 *      RETURN          void            - Function internal errors if an error
 *                                        is detected.
 */

int vmReallocKSHB(hkh, ppbData, cb, fl)
VMHKH                   hkh;            /* Heap header handle */
char                    **ppbData;      /* Pointer to heap block info */
register ulong_t        cb;             /* New size of data wanted */
ulong_t                 fl;             /* Allocation flags */
{
  VMKSH                 *pksh;          /* Pointer to heap header */
  VMKSHB                *pkshb;         /* Pointer to heap block */
  ulong_t               cbOld;          /* Original size of block */
  ulong_t               cbRound;        /* Requested rounded size */
  int                   rc;             /* Result code */
  VMKHBI                khbi;           /* Heap block info */
  VMKHBI                *pkhbi;
  char                  *pbNewData;
  char                  *pbOldData = *ppbData;


    pkhbi = (VMKHBI *) SSToDS(&khbi);
    khbi.khbi_pbData = *ppbData;

    /*
     *  Validate heap handle and convert to heap header pointer.
     */

    vmAssert(vmIsHKSH(hkh));
    pksh = apkh[hkh].kh_pksh;

    pkshb = (VMKSHB *)(pbOldData - sizeof(VMKSHB));

    /*
     *  If new block size is less than old, shrink block in situ.
     */

    cbOld = kshbSize(pkshb);
    cbRound = kshRoundUp(cb);

    rc = NO_ERROR;
    if(cbRound < cbOld)
    {
        vmShrinkKSHB(hkh, pbOldData, cb);
    }

    /*
     *  Else if new block size > old, allocate new block, copy old to new and
     *  free old.
     */

    else if(cbRound > cbOld)
    {
        khbi.khbi_sel = pkshb->kshb_sel;
        if(khbi.khbi_sel > 3)
        {
            fl |= VMAC_SELALLOC;
        }
        if((rc = vmAllocKSHB(hkh, cb, fl, pkshb->kshb_hobowner,
              pkhbi)) == NO_ERROR)
        {
            pbNewData = pkhbi->khbi_pbData;
            rc = vmCopyKHB(pbNewData,
                           pbOldData,
                           cbOld - sizeof(VMKSHB),
                           (pksh->ksh_fl | fl) & (PG_MODIFIER | PG_PERM));

            if(rc == NO_ERROR)
            {
                vmFreeKSHB(hkh, pbOldData);
                *ppbData = pbNewData;
            }
            else
            {
                vmFreeKSHB(hkh, pbNewData);
                *ppbData = NA;
            }
        }
    }
    return(rc);
}


/***LP  vmFreeKSHB - Free Kernel Swappable Heap Block
 *
 *      This function frees a block from a specified kernel swappable
 *      heap.
 *
 *      vmFreeKSHB(VMHKH hkh, char *pbData)
 *
 *      ENTRY           hkh             - Kernel swappable heap header handle
 *                                        created by VMCreateKH.  Special
 *                                        values map the public swappable
 *                                        heaps:
 *                                        - VM_HKH_PUB_SWAP_RW
 *                                          Public Swappable RW Heap
 *                                        - VM_HKH_PUB_SWAP_RO
 *                      pbData          - Address of block to free
 *      EXIT            NONE
 */
void vmFreeKSHB(hkh, pbData)
VMHKH                   hkh;            /* Swappable heap header handle */
char                    *pbData;
{
register VMKSHD *pcurr;            /* pointer to current free block descriptor   */
register VMKSHD *pprev;            /* pointer to previous free block descriptor  */
VMKSH  *pksh;          /* Pointer to Swappable Heap Header */
VMKSHD *pprev2;           /* pointer to previous previous free blk      */
ulong_t tfree;             /* top of this free block                     */
ulong_t tprev;             /* top of previous free block                 */
ulong_t cbRound;
VMKSHD *pnew;             /* pointer to current free block descriptor   */
VMKSHB *pkshb;
ulong_t fkshd_used;
ulong_t rc;

    /***
    *   Validate heap handle and convert to heap header pointer.
    */

    vmAssert(vmIsHKSH(hkh));
    pksh = apkh[hkh].kh_pksh;

    /***
    *  Pre-allocate BMP32 records for Block Descriptors, one for the new
    *  end marker block (if any)
    */

    if((BMPGet(pkshdVMDescs, SSToDS(&pnew))) != NO_ERROR)
    {
         return;
    }
    fkshd_used = 0;

    /***
    *  Take the heap semaphore, ignoring interrupts since we are freeing
    *  resources.
    */
   while ( (KSEMRequestMutex((HKSEM)&(pksh->ksh_ksem), -1)) != NO_ERROR);

    /***
    *   get kshb information
    */
    pkshb   = (VMKSHB *)(pbData- sizeof(VMKSHB));
    cbRound = kshbSize(pkshb);

    /***
    *   if BlockOffset >= HintPtr start with hint pointers
    */
    if ((char *)pkshb >= pksh->ksh_pHint->kshd_pb)
    {
        pprev  = pksh->ksh_pHPrev;
        pcurr  = pksh->ksh_pHint;
    }
    else
    {
        pprev  = &pksh->ksh_hdrEntry;
        pcurr  = &pksh->ksh_hdrEntry;
    }

    /***
    *   search the free chain. This loop locates the current and
    *      previous pointers in the free chain around the block to be freed.
    */
    while ((pcurr->kshd_pNext != KSHENDLIST) &&
           (char *)pkshb > (pcurr->kshd_pNext)->kshd_pb)
    {
        pprev = pcurr;
        pcurr = pcurr->kshd_pNext;
    }
    /***
    *  Set Pointers, top of previous and top of new free block
    */
    pprev2= pprev;                              /* prev prev = prev          */
    pprev = pcurr;                              /* Prev      = Curr          */
    pcurr = pcurr->kshd_pNext;                  /* Curr      = Curr.Nx       */
    tprev = (ULONG)pprev->kshd_pb + pprev->kshd_size;    /* set top of previous       */
    tfree = (ULONG)pkshb + cbRound;        /* set top of block to free  */

    /***
    *  if (BlockOffset < end of old free block)
    *  or if Top of FreeBlock > Bottom of Current then overlap error
    *  Test for BlockOffset = start of old free block : error if true
    */

    if (tprev == (ULONG)pkshb)  /* top of a free block = BlockOffset   */
    {
        if ((pcurr != KSHENDLIST) && pcurr->kshd_pb == (char *)tfree) /* PERFECT FIT */
        {
            /***
            *   coalesce prev, new and current into 1 free block
            */
            pprev->kshd_size  = pprev->kshd_size + pcurr->kshd_size + cbRound;
            pprev->kshd_pNext = pcurr->kshd_pNext;

            if ( (pprev->kshd_size+(ulong_t)pprev->kshd_pb) >=
                        (ulong_t)pksh->ksh_pbEndCom) {

                rc = VMSetMem( kshPgRoundUp((ulong_t)pprev->kshd_pb),
                               ((ulong_t)pksh->ksh_pbEndCom) -
                                 (kshPgRoundUp((ulong_t)pprev->kshd_pb)),
                                HOBNULL,
                                VMS_DECOMMIT,
                                NA);
                if (rc == 0)  /* part of the heap could be locked */
                {
                    pksh->ksh_pbEndCom = (char *)
                          (kshPgRoundUp((ulong_t)pprev->kshd_pb));
                }
            }



            /***
            *  update hint ptrs if new free block size > HintSize or
            *  when the free block is between the two hint free blocks
            *  also test for the new free block being inserted just in front
            *  of the HPrev free block, modify only the HPrevPtr if true
            */
            if ((char *)pkshb < pksh->ksh_pHint->kshd_pb)
            {
                if (pprev->kshd_size >= pksh->ksh_HintSize)  /* test HintSize */
                {
                    pksh->ksh_pHint  = pprev;
                    pksh->ksh_pHPrev = pprev2;
                }
                else   /* test for new free block inbetween hint ptrs */
                {
                    if (pcurr == pksh->ksh_pHint)
                    {
                        vmAssert(pprev == pksh->ksh_pHPrev);
                        pksh->ksh_pHint  = pprev;
                        pksh->ksh_pHPrev = pprev2;
                    }
                    else    /* if new block inserted in front of HPrevPtr */
                    {
                        if (pcurr == pksh->ksh_pHPrev)
                        {
                            vmAssert(pcurr->kshd_pNext == pksh->ksh_pHint);
                            pksh->ksh_pHPrev = pprev;
                        }
                    }
                }
            }
            /***
            *   since the new block was inserted between the prev
            *   and curr blocks and all 3 were coalesced into the prev block
            *   free the curr kshd
            */
            BMPFree(pkshdVMDescs, pcurr);
            vmDecr_ksh_ckshds(pksh->ksh_ckshds);

        }
        else  /*  COALESCE TO LOWER FREE BLOCK  */
        {
            pprev->kshd_size += cbRound;    /* add Size to existing free block */

            /***
            *  update hint ptrs if new free block size > HintSize
            */
            if ((char *)pkshb < pksh->ksh_pHint->kshd_pb)
            {
                if (pprev->kshd_size >= pksh->ksh_HintSize)  /* test HintSize */
                {
                    pksh->ksh_pHint  = pprev;
                    pksh->ksh_pHPrev = pprev2;
                }
            }
        }
    }
    else
    {
        if ((pcurr != KSHENDLIST) && (char *)tfree == pcurr->kshd_pb)
        {                                 /*  COALESCE TO HIGHER FREE BLOCK  */
            /***
            *  update higher free blocks size and pb field
            */
            pcurr->kshd_size  += cbRound;
            pcurr->kshd_pb    -= cbRound;

            if ( (pcurr->kshd_size+(ulong_t)pcurr->kshd_pb) >=
                          (ulong_t)pksh->ksh_pbEndCom) {

                rc = VMSetMem( kshPgRoundUp((ulong_t)pcurr->kshd_pb),
                               ((ulong_t)pksh->ksh_pbEndCom) -
                                 (kshPgRoundUp((ulong_t)pcurr->kshd_pb)),
                                HOBNULL,
                                VMS_DECOMMIT,
                                NA);
                if (rc == 0)  /* part of the heap could be locked */
                {
                    pksh->ksh_pbEndCom = (char *)
                          (kshPgRoundUp((ulong_t)pcurr->kshd_pb));
                }
            }
            /***
            *  update hint ptrs if new free block size > HintSize
            */
            if ((char *)pkshb < pksh->ksh_pHint->kshd_pb)
            {
                if (pcurr->kshd_size >= pksh->ksh_HintSize)
                {
                    pksh->ksh_pHint  = pprev;
                    pksh->ksh_pHPrev = pprev2;
                }
            }
        }
        else  /* NEW FREE BLOCK BETWEEN TWO OLD FREE BLOCKS */
        {
            /***
            *  make new free block descriptor and redo links
            */
            fkshd_used = 1;

            pnew->kshd_size = cbRound;
            pnew->kshd_pNext= pprev->kshd_pNext;
            pnew->kshd_pb   = (char *)pkshb;
            pprev->kshd_pNext = pnew;

            /***
            *  update hint ptrs if new free block size > HintSize or
            *  update HPrevPtr if new free block is inserted between
            *  the hint ptrs
            */
            if ((char *)pkshb < pksh->ksh_pHint->kshd_pb)
            {
                if (pnew->kshd_size >= pksh->ksh_HintSize) /* test hintsize */
                {
                    pksh->ksh_pHint  = pnew;
                    pksh->ksh_pHPrev = pprev;
                }
                else
                {
                    /***
                    *   test if new kshd_pb is between Hints
                    *   if so set HintPrev = new
                    */
                    if ((char *)pkshb > pksh->ksh_pHPrev->kshd_pb)
                        pksh->ksh_pHPrev = pnew;

                }
            }
        }
    }

    if (fkshd_used == 0)
    {
        BMPFree(pkshdVMDescs, pnew);
    }
    else
    {
        vmIncr_ksh_ckshds(pksh->ksh_ckshds);
    }

    vmIncr_ksh_cFrees(pksh->ksh_cFrees);

    vmAssert(vmIsValidKSH(pksh));
    KSEMReleaseMutex((HKSEM)&(pksh->ksh_ksem));
}


/***LP  vmShrinkKSHB - Shrink Kernel Resident Heap Block
 *
 *      This function shrinks a block allocated from the specified kernel
 *      swappable heap.  If there is sufficient space freed up to create
 *      a new free block and a block descriptor can be allocated, a
 *      residual free block will be created, otherwise no shrinkage
 *      takes place.  The block start address remains unchanged after
 *       shrinking.
 *
 *      void vmShrinkKSHB(VMHKH hkh, char *pbData, ulong_t cb)
 *
 *      ENTRY           hkh             - Kernel swappable heap header handle
 *                                        created by VMCreateKH.  Special
 *                                        values map the public swappable
 *                                        heaps:
 *                                        - VM_HKH_PUB_SWAP_RW
 *                                          Public Swappable RW Heap
 *                                        - VM_HKH_PUB_SWAP_RO
 *                      pbData          - Pointer to block to be freed
 *                      cb              - New block size (excluding header)
 *
 *      RETURN          void            - Function internal errors if an error
 *                                        is detected.
 */

void                    vmShrinkKSHB(hkh, pbData, cb)
VMHKH                   hkh;            /* Pointer to swappable heap header */
char                    *pbData;        /* Pointer to block to free */
ulong_t                 cb;             /* New size of block */
{
    register VMKSH        *pksh;          /* Pointer to Swappable Heap Header */
    register VMKSHB       *pkshb;         /* Pointer to Heap Block Header */
    register VMKSHB       *pbfree;        /* Pointer to Heap Block Header */
    ulong_t               cbOld;          /* Original block size in bytes */
    ulong_t               cbNewFree;      /* size of new free block */
    ulong_t               cbRound;        /* Rounded size */

    /*
    *  Validate heap handle and convert to heap header pointer.
    */
    vmAssert(vmIsHKSH(hkh));
    pksh = apkh[hkh].kh_pksh;

    pkshb = (VMKSHB *)(pbData - sizeof(VMKSHB));
    cbOld = kshbSize(pkshb);
    cbRound = kshRoundUp(cb);
    cbNewFree = cbOld - cbRound;

    if (cbNewFree >= (sizeof(VMKSHB)+8))  /* bugbug 8 */
    {
        /* set the users ksbh header to the new size */

// perf - mem reduction : for retail and hstrict builds combine
//                        swappable r/o heap with swappable r/w heap
//                        therefore don't use ReadOnly macro
#ifdef VMSTRICT
        if(pksh->ksh_fl & PG_W)
        {
            pkshb->kshb_size = kshbSetSize(cbRound);
        }
        else
        {
            VMSetReadOnlyUL(&(pkshb->kshb_size), cbRound);
        }
#else
        pkshb->kshb_size = kshbSetSize(cbRound);
#endif
        /*  set the size of the bogus free block */

        pbfree = (VMKSHB *)((char *)pkshb+cbRound);

// perf - mem reduction : for retail and hstrict builds combine
//                        swappable r/o heap with swappable r/w heap
//                        therefore don't use ReadOnly macro
#ifdef VMSTRICT
        if(pksh->ksh_fl & PG_W)
        {
            pbfree->kshb_size = kshbSetSize(cbNewFree);
        }
        else
        {
            VMSetReadOnlyUL(&(pbfree->kshb_size), cbNewFree);
        }
#else
        pbfree->kshb_size = kshbSetSize(cbNewFree);
#endif
        /* must incr allocs to offset bogus free */
        vmIncr_ksh_cAllocs(0,pksh->ksh_cAllocs);

        /***
        *   Since vmFreeKSHB takes the offset returned to the user
        *   as input reset pbfree to point at the bogus block tobe freed
        */
        vmFreeKSHB(hkh,(char *)((ulong_t)pbfree+sizeof(VMKSHB)));

    }
}



#ifdef VMSTRICT

/***LP  vmIsValidKSH - Check integrity of swappable heap
 *
 *      This function checks that all the linkages in a swappable
 *      heap are consistent.  It is normally used only when debugging the
 *      heap.
 *
 *      int vmIsValidKSH(pksh)
 *
 *      ENTRY           pksh            - Swappable heap header pointer
 */

int     vmIsValidKSH(pksh)
VMKSH           *pksh;          /* Pointer to resident heap header */
{
    VMKSHD *pcurr;
    VMKSHB *pkshb;
    ulong_t ckshbs;
    ulong_t ckshds;

    if (vmkhGflags == 0)    return(TRUE);

    ckshbs =0;
    ckshds =0;

    pcurr = &(pksh->ksh_hdrEntry);
    pcurr = pcurr->kshd_pNext;



    /***
    *   test hint ptrs before scanning the list
    */
    if (pksh->ksh_pHint != pksh->ksh_pHPrev)
    {
        if (pksh->ksh_pHPrev->kshd_pNext != pksh->ksh_pHint)
        {
            panic("VMKSH: invalid hint pointers.");
            return(FALSE);
        }
    }


    if ((pcurr->kshd_pNext == KSHENDLIST)  &&
        (pcurr->kshd_pb == pksh->ksh_pbStart))
    {
        panic("VMKSH: invalid hint pointers.");
        return(TRUE);
    }

    if (pcurr->kshd_pb != pksh->ksh_pbStart)
    {
        pkshb = (VMKSHB *)(pksh->ksh_pbStart);
        goto restart2;
    }

    if (pcurr->kshd_pb == pksh->ksh_pbStart)
    {
        pkshb = (VMKSHB *)(pcurr->kshd_pb+pcurr->kshd_size);
        ckshds++;
        pcurr = pcurr->kshd_pNext;
        goto restart2;
    }

restart1:;

    ckshds++;
    if (ckshds > pksh->ksh_ckshds)
    {
        panic("VMKSH: invalid number of ksh descriptors.");
        return(FALSE);
    }

    if (pcurr->kshd_pNext == KSHENDLIST)
    {
        if ((pksh->ksh_ckshds == ckshds)     &&
            ((pksh->ksh_cAllocs - pksh->ksh_cFrees) == ckshbs) )
           return(TRUE);
        else
        {
           panic("VMKSH: invalid number of ksh blocks.");
           return(FALSE);
        }
    }

    pkshb = (VMKSHB *)(pcurr->kshd_pb+pcurr->kshd_size);
    pcurr = pcurr->kshd_pNext;

restart2:;

    ckshbs++;
    if (ckshbs > pksh->ksh_cAllocs - pksh->ksh_cFrees)
    {
        return(FALSE);
    }

    pkshb = (VMKSHB *)((char *)pkshb+kshbSize(pkshb));

    if ((char *)pkshb == pcurr->kshd_pb)
    {
        goto restart1;
    }
    else
    {
        goto restart2;
    }
}
#endif


/***LP  vmFindKSHB - Find Kernel Swappable Heap Block
 *
 *      Given a linear address within the data of a kernel swappable heap
 *      block, this function finds the linear address of the block that
 *      contains the given address.  An error is returned if the given
 *      address does not reside within the data portion of a heap block.
 *
 *      int vmFindKSHB(VMKHBI *pkhbi)
 *
 *      ENTRY           pkhbi           - Pointer to heap block info
 *                                        containing heap handle and
 *                                        linear address
 *      EXIT            pkhbi           - linear address is updated
 *                                        to point at start of block's data
 */

int vmFindKSHB(pkhbi)
VMKHBI                  *pkhbi;         /* Pointer to heap block info */
{
    VMKSH  *pksh;          /* Pointer to heap header */
    VMKSHD *pcurr;
    VMKSHB *pkshb;

    vmAssert(0);   // this is a VERY expensive call and should be
                   //    avoided if possible

    pksh = apkh[pkhbi->khbi_hkh].kh_pksh;

    pcurr = &(pksh->ksh_hdrEntry);
    pcurr = pcurr->kshd_pNext;

    if (pcurr->kshd_pb != pksh->ksh_pbStart)
    {
        pkshb = (VMKSHB *)(pksh->ksh_pbStart);
        goto restart2;
    }

    if (pcurr->kshd_pb == pksh->ksh_pbStart)
    {
        pkshb = (VMKSHB *)(pcurr->kshd_pb+pcurr->kshd_size);
        pcurr = pcurr->kshd_pNext;
        goto restart2;
    }

restart1:;

    if (pcurr->kshd_pNext == KSHENDLIST)
    {
         return(ERROR_INVALID_ADDRESS);
    }

    pkshb = (VMKSHB *)(pcurr->kshd_pb+pcurr->kshd_size);
    pcurr = pcurr->kshd_pNext;

restart2:;

    pkshb = (VMKSHB *)((char *)pkshb+kshbSize(pkshb));

    if ((char *)pkshb == pcurr->kshd_pb)
    {
        goto restart1;
    }
    else
    {
        goto restart2;
    }
}



/***LP  vmSetupSpecialKSHB - setup for a "special" kshb allocation request
 *
 *      Special requests are one's that specify some type of alignment
 *      ie page, paragraph etc.   This routine is passed a free block and
 *      then, if the block can satify the request, breaks it down into two
 *      free blocks with the second free block satifing the special request.
 *
 *      int vmSetupSpecialKSHB(hkh,fl, cb, fused, pcr, ppv, pnw)
 *
 *      ENTRY      VMKSH   *pksh;        - Pointer to swappable heap header
 *                 ulong_t fl;           - flags passed in by caller
 *                 ulong_t cb;           - size passed in by caller
 *                 ulong_t *fused;       - address of flag for kshd allocation
 *                 VMKSHD  *pcr;         - pointer to the current free block
 *                 VMKSHD  *ppv;         - pointer to the pprev free block
 *                 VMKSHD  *pnw;         - pointer to new kshd (if needed)
 *
 *      EXIT  rc = NO_ERROR              - block found to satify request
 *                 ksh_fNO_FIT           - block could not satify request
 *
 *            fused = ksh_fBMP_USED      - kshd was used, only set if block
 *                                           was ok and we had to use the
 *                                           the passed in kshd
 *
 * On Input:  pcr->size ------------+
 *            pcr->pb               |
 *              |                   |
 *              |<------------------+-------------------->|
 *              V                                         V
 *          --+-----------+-----------+-----------+-----------+--
 *            |    4K     |    4K     |    4K     |    4K     |
 *          --+-----------+-----------+-----------+-----------+--
 *              A         A                               A
 * On Output:   |<---+--->|<---------------+------------->|
 *              |    |    |                |
 *     pnw->pb -+    |    +-- pcr->pb      |
 *     pnw->size ----+        pcr->size ---+
 *
 *
 */
int vmSetupSpecialKSHB(pksh,fl, cb, fused, pcr, ppv, pnw)
VMKSH   *pksh;       /* Pointer to swappable heap header */
ulong_t fl;          /* flags passed in by caller */
ulong_t cb;          /* size passed in by caller */
ulong_t *fused;      /* address of flag for kshd allocation */
VMKSHD  *pcr;        /* pointer to the current free block */
VMKSHD  *ppv;        /* pointer to the pprev free block */
VMKSHD  *pnw;        /* pointer to new kshd (if needed) */
{
ulong_t cbOldFree2;
char    *pcurrpgalign;  /* pointer to ???? free block descriptor  */
ulong_t rc;

   *fused = 0;

   if ((fl & VMAC_NOXPAGE) &&
         (vmCrossesPgBdry(((ulong_t)pcr->kshd_pb+sizeof(VMKSHB)),cb)))
   {
      return(NO_ERROR);
   }

   /* if current free block addr (plue header size) is page aligned
    *    found perfect fix return no error
    */
   if ( (((ulong_t)pcr->kshd_pb + sizeof(VMKSHB)) & (PAGESIZE-1)) == 0)
       goto found_okblk;

   /* round up free block to next page boundary, saving room for kshb
    */
   pcurrpgalign  = (char *)
          ((kshPgRoundUp ( (ulong_t)(pcr->kshd_pb+sizeof(VMKSHB)) ) )
                         -sizeof(VMKSHB));
   /* make sure that the round up didn't take us past the end
    *  of the free block
    */
   if ((ulong_t)pcurrpgalign >= ((ulong_t)pcr->kshd_pb+pcr->kshd_size))
       return(ksh_fNO_FIT);

   cbOldFree2 = (ulong_t)(((ulong_t)pcr->kshd_pb+pcr->kshd_size) -
                         ((ulong_t)pcurrpgalign));

   if ( (cbOldFree2-sizeof(VMKSHB)) < cb)
       return(ksh_fNO_FIT);

   /*  make sure that new free block is usable, ie larger than the size
    *   of a kshb header and the min size allocation
    */

//    BUGBUG - screw the free block, the amount of code to prevent
//             this is very expensive and dangerous

       pnw->kshd_size  = (ulong_t) (pcurrpgalign - pcr->kshd_pb);
//     if (pnw->kshd_size <  (sizeof(VMKSHB)+ksh_MIN_FREE_BLOCK_SIZE))
//         return(ksh_fNO_FIT);

   // found block to satify request, setup pointers and return
   *fused = ksh_fBMP_USED;

   //  setup the new kshd, size already done above
   pnw->kshd_pb    = pcr->kshd_pb;
   pnw->kshd_pNext = pcr;

   //  fix the current kshd pb and size field
   pcr->kshd_pb    = pcurrpgalign;
   pcr->kshd_size  = cbOldFree2;

   //  pointer previous kshd pNext field to the new kshd
   ppv->kshd_pNext = pnw;


found_okblk:;
  /*
   * if uvirt or executable and not at end of object, must set flags
   */
   if (fl & (PG_U | PG_X))
   {
      if ( ((ulong_t)pcr->kshd_pb + sizeof(VMKSHB))
                          < (ulong_t)pksh->ksh_pbEndCom)
      {
           rc=PGSetAccess(((ulong_t)pcr->kshd_pb+sizeof(VMKSHB))>>PAGESHIFT,
                       pPTDACur,
                       kshPgRoundUp(cb) >> PAGESHIFT,
                       (fl | pksh->ksh_fl) & ~VMS_COMMIT);
           vmAssert(rc == NO_ERROR);
      }
   }
   return(NO_ERROR);
}


#pragma code_seg("CINIT_TEXT", "CODE")      /* This section goes to INIT code */

/***LP  vmCreateKSH - Create a kernel swappable heap
 *
 *      This function creates an empty kernel swappable heap.  A header
 *      is allocated (from the public kernel resident heap), virtual address
 *      space is allocated and an initial linked list of Block Descriptors
 *      containing one Block Descriptor for a zero-length block, and an end
 *      marker is created.
 *
 *      vmCreateKSH(cb, fl, hobowner, phkh)
 *
 *      ENTRY   ulong_t cb              - Max virtual size of heap
 *              ulong_t fl              - flags
 *              VMHOB hobowner          - heap owner
 *              VMHKH *phkh             - where to return heap header handle
 *      RETURN  rc
 *
 *      EXIT    pkshdVMDescs = address of first swappable heap
 *                                      Block Descriptor
 */

int vmCreateKSH(cb, fl, hobowner, phkh)
ulong_t         cb;                     /* Maximum Swappable Heap Size */
ulong_t         fl;                     /* flags (not yet used) */
VMHOB           hobowner;               /* swappable heap's owner */
VMHKH           *phkh;                  /* Where to return header handle */
{
   VMAC          ac;                     /* VMAllocMem return buffer */
   VMKSH         *pksh;                  /* Pointer to swappable heap hdr */
   VMHKH         hkh;                    /* Heap Header Handle */
   int           rc;                     /* Result code */
   VMKSHD        *pkshd;

  /*
   *  Validate flags (BUBUG IDB 4/20/90 - PG_U temporarily allowed)
   */

   vmAssert(fl == (fl & (PG_STATE | PG_R | PG_U | PG_W | PG_X)));
   vmAssert((fl & PG_RESIDENT) == 0);

  /*
   *  Check that the limit on the number of heaps in the system
   *  will not be exceeded.  Find available slot and reserve it.
   */

   for(hkh = hkh_MIN; hkh <= hkh_MAX; hkh++)
   {
      if(apkh[hkh].kh_fl == NA)
      {
         if(hkh > hkhCurrMax)
         {
            hkhCurrMax = hkh;
         }
         break;
      }
   }
   vmAssert(hkh <= hkh_MAX);
   apkh[hkh].kh_fl = fl;

  /*
   *  Allocate a swappable heap header (from the Public Read/Write Resident
   *  heap).
   */

   if((rc = VMAllocKHB(VM_HKH_PUB_RESRW, sizeof(VMKSH), VMKSHDOWNER, NA,
      (char **) SSToDS(&pksh))) == NO_ERROR)
   {
      /*
       *  Allocate a Block Descriptor to mark the end of the list.  Initialize
       *  it to have a null next-pointer and a zero size.  If error, free
       *  the swappable heap header.
       */

      if((rc = BMPGet(pkshdVMDescs, SSToDS(&pkshd))) == NO_ERROR)
      {
          /*
           *  Create swappable object for the heap.  We need to
           *  commit one page so that the first free heap block can
           *  be allocated.
           */

         if((rc = VMAllocMem(cb,           /* Max size of heap */
                              PAGESIZE,     /* Initially one page */
              VMAC_ALIGNDIR | fl | ksh_CREATE, /* Allocation flags */
                              HOBNULL,      /* No PTDA since system arena */
                              hobowner,     /* Owned by specified owner */
                              HOBNULL,      /* Not an MTE object */
                              NA,           /* No Selector Manager flags */
                              NA,           /* No loader block number */
                              SSToDS(&ac))) == NO_ERROR)
         {
            /*
             *  All resources successfully allocated for the
             *  new swappable heap.  Initialize data structures.
             *  and Initialize the swappable heap header.
             */

            pksh->ksh_hdrEntry.kshd_size =0;
            pksh->ksh_hdrEntry.kshd_pNext=pkshd;
            pksh->ksh_hdrEntry.kshd_pb = NULL;
            pksh->ksh_pHint    = pkshd;
            pksh->ksh_pHPrev   = &(pksh->ksh_hdrEntry);
            pksh->ksh_HintSize = cb - sizeof(VMKSHB);

            pksh->ksh_pbEndRes = (char *)(ac.ac_va + vmPageCeil(cb));
            pksh->ksh_pbEndCom = (char *)(ac.ac_va + PAGESIZE);
//          pksh->ksh_cMods = 0L;
            pksh->ksh_hob = ac.ac_hob;
            pksh->ksh_fl = fl | ksh_COMMIT;
            pksh->ksh_pbStart  = (char *)ac.ac_va;
            KSEMInit((HKSEM)&(pksh->ksh_ksem), KRNL_MUTEXSEM, 0);
#ifdef VMSTRICT
            pksh->ksh_ckshds   = 0;
            pksh->ksh_cFrees   = 0;
            pksh->ksh_cAllocs  = 0;
            vmIncr_ksh_ckshds(pksh->ksh_ckshds);
#endif
            pkshd->kshd_size = cb - sizeof(VMKSHB);
            pkshd->kshd_pNext= KSHENDLIST;
            pkshd->kshd_pb   = (char *) ac.ac_va;

           /*
            *  Update minimum and maximum heap region (all heaps).
            */
            if (vmladdrMinKH > ac.ac_va) {
               vmladdrMinKH = ac.ac_va;
            }
            if (vmladdrMaxKH < (ac.ac_va + vmPageCeil(cb)) ) {
               vmladdrMaxKH = ac.ac_va + vmPageCeil(cb);
            }

           /*
            *  Return heap header handle and success to caller.
            */
            apkh[hkh].kh_pksh = pksh;
            *phkh = hkh;
            return(NO_ERROR);
         }
         /*
         *  Failure to allocate BMP32 record for Block Descriptor
         *  preceding end marker.  Free BMP32 record for end marker
         *  and drop through to free other resources.
         */
         BMPFree(pkshdVMDescs, pkshd);
      }
     /*
      *  Failure to allocate BMP32 record for end marker.  Free swappable
      *  heap header.
      */
      VMFreeKHB(VM_HKH_PUB_RESRW, pksh);
   }
  /*
   *  Some failure occurred. Return result code to caller.
   */
   apkh[hkh].kh_fl = NA;
   vmAssert(0);
   return(rc);
}

#pragma code_seg()

