/*static char *SCCSID = "@(#)semtools.c 6.2 91/01/30";*/
#define SCCSID  "@(#)semtools.c 6.2 91/01/30"

/*
 *      Semaphores - 32-bit Semaphore Utility Routines
 *
 *      This is an OS/2 2.x specific file
 *      IBM/Microsoft Confidential
 *
 *      Copyright (c) IBM Corporation 1987, 1989
 *      Copyright (c) Microsoft Corporation 1987, 1989
 *
 *      All Rights Reserved
 *
 *      Created: June 1989 - Julie Bennett
 *
 *      #115627 Chg Team - Modified 32-bit handle signature so it checks
 *                         for PM sems.
 *
 */


#define INCL_TYPES
#include <basedef.h>
#define FNO_NUM FNO_SEMTOOLS_C          /* for assertion macros */
#include <fnotask.h>                    /* MUST BE BEFORE osmac.h */
#include <osmac.h>
#include <osconst.h>
#include <ostypes.h>
#include <infoseg.h>
#include <mi.h>
#include <proc.h>
#include <error.h>
#include <error2.h>
#include <sigdef.h>
#include <except.h>
#include <dossymc.h>
#include <seldesc.h>
#include <pgexport.h>
#include <vmexport.h>
#include <vmowner.h>
#include <tkexport.h>
#include <sem.h>
#include <screen.h>
#include <curdir.h>
#include <dirent.h>
#include <find.h>
#include <selxport.h>
#include <ioexp.h>
#include <semxport.h>
#include <tkptda.h>
#include <bsetib.h>
#include <tklocal.h>
#include <semlocal.h>
#include <string.h>


/***LP  semChkSharedHdl - Check For An Invalid SHARED Handle
 *
 *      semChkSharedHdl checks the shared table for an invalid handle
 *      value.  If the handle is not valid, then ERROR_INVALID_HANDLE
 *      is returned.  Otherwise, NO_ERROR is returned.
 *
 *      ENTRY   HEV     - handle of handle to check  //98809
 *              ulType  - type of semaphore:
 *                   DCE_EVENT_SEM
 *                   DCM_MUTEX_SEM
 *                   DCMW_MUX_SEM
 *              pptda   - pointer to PTDA to use
 *
 *      EXIT    Success - NO_ERROR
 *              Failure - ERROR_INVALID_HANDLE
 *
 *      PSEUDO CODE
 *
 *      If (pptda == NULL)                 // device helper
 *        If ((ulIndex >= ulShTblSize) || (sem not open by device driver) ||
 *            (sem is not a shared event))
 *          return (ERROR_INVALID_HANDLE)
 *        Endif
 *      Else                               // not a device helper
 *        If ((ulIndex >= pPTDACur->ulShBmpSize) || (ulIndex >= ulShTblSize) ||
 *            (sem not open by current pid) || (sem is not of the correct type))
 *          return (ERROR_INVALID_HANDLE)
 *        Endif
 *      Endif
 *      return (NO_ERROR)
 */

ULONG semChkSharedHdl(HEV   hev,          /* handle to check */ //98809
                      ULONG ulType,       /* type of semaphore */
                      PPTDA pptda)        /* ptr to PTDA to use */

{
    ULONG    ulIndex;                      //98809
    register USHORT usFlags;              /* semaphore flags */

    ulIndex = semGetIndex(hev);            //98809

    if (pptda == NULL) {
      /*
       *  Device Helper - must validate that it's open for the DH and
       *  that the semaphore is of the type specified.
       */
      if ((ulIndex >= ulShTblSize) || ((PSHUN)pShSemTbl[ulIndex] == NULL) ||
          (!((usFlags = ((PSHUN)pShSemTbl[ulIndex])->SEvt.usFlags)
                        & DHO_SEM_OPEN)) ||
          (!(usFlags & (USHORT)ulType)))
        return (ERROR_INVALID_HANDLE);
    }
    else if (hev & SEM_PMSEMCALL) {                                     //98809
      //                                                                //98809
      //  Called via DosPMSem API, cannot check pShSemBMP               //98809
      //  Not a Device Helper - must validate that it's open for        //98809
      //  the given process and that the semaphore is of the type       //98809
      //  specified.                                                    //98809
      //                                                                //98809
      if ((ulIndex >= pptda->ulShBmpSize) || (ulIndex >= ulShTblSize) ||   //98809
          (!(((PSHUN)pShSemTbl[ulIndex])->SEvt.usFlags & (USHORT)ulType))) //98809
        return (ERROR_INVALID_HANDLE);                                  //98809
    }                                                                   //98809
    else {
      /*
       *  Not called via DosPMSem API, need to check pShSemBMP
       *  Not a Device Helper - must validate that it's open for the given
       *  process and that the semaphore is of the type specified.
       */
      if ((ulIndex >= pptda->ulShBmpSize) || (ulIndex >= ulShTblSize) ||
          (!semGetBit(ulIndex,pptda->pShSemBmp)) ||
          (!(((PSHUN)pShSemTbl[ulIndex])->SEvt.usFlags & (USHORT)ulType)))
        return (ERROR_INVALID_HANDLE);
    }
    return (NO_ERROR);
}


/***LP  semChkPrivateHdl - Check For An Invalid PRIVATE Handle
 *
 *      semChkPrivateHdl checks the private table for an invalid handle
 *      value.  If the handle is not valid, then ERROR_INVALID_HANDLE
 *      is returned.  Otherwise, NO_ERROR is returned.
 *
 *      ENTRY   ulIndex - index of handle to check
 *              ulType  - type of semaphore:
 *                   DCE_EVENT_SEM
 *                   DCM_MUTEX_SEM
 *                   DCMW_MUX_SEM
 *
 *      EXIT    Success - NO_ERROR
 *              Failure - ERROR_INVALID_HANDLE
 *
 *      PSEUDO CODE
 *
 *      If ((ulIndex >= pPTDACur->ulPrTblSize) ||
 *          (pPTDACur->pPrSemTbl[ulIndex] == NULL) ||
 *          (sem is not of the correct type))
 *        return (ERROR_INVALID_HANDLE)
 *      Endif
 *      return (NO_ERROR)
 */

ULONG semChkPrivateHdl(ULONG ulIndex,      /* index of handle to check */
                       ULONG ulType)       /* type of semaphore */

{
    if ((ulIndex >= pPTDACur->ulPrTblSize) ||
        (pPTDACur->pPrSemTbl[ulIndex] == NULL) ||
        (!(((PPRUN)pPTDACur->pPrSemTbl[ulIndex])->PEvt.usFlags &
                   (USHORT)ulType)))
      return (ERROR_INVALID_HANDLE);
    return (NO_ERROR);
}


/***LP  semChkHdl - Check For An Invalid Handle (Shared or Private)
 *
 *      semChkHdl checks the appropriate table for an invalid handle
 *      value.  If the handle is not valid, then ERROR_INVALID_HANDLE
 *      is returned.  Otherwise, NO_ERROR is returned.
 *
 *      This routine is only called by the verification layer.  This
 *      is only needed in the case where it is not known whether the
 *      semaphore handle is shared or private.  If a routine already
 *      knows what kind of semaphore it needs to check, then
 *      semChkSharedHdl or semChkPrivateHdl should be called directly.
 *
 *      ENTRY   ulHandle - semaphore handle to check
 *              ulType   - type of semaphore:
 *                           DCE_EVENT_SEM
 *                           DCM_MUTEX_SEM
 *                           DCMW_MUX_SEM
 *              pptda    - pointer to PTDA to use
 *
 *      EXIT    Success - NO_ERROR
 *              Failure - ERROR_INVALID_HANDLE
 *
 *      PSEUDO CODE
 *
 *      If (signature is wrong)
 *        return (ERROR_INVALID_HANDLE)
 *      If (ulHandle & SEM_SHAREDMASK)           // shared sem
 *        return ( call semChkSharedHdl )
 *      Else                                     // private sem
 *        return ( call semChkPrivateHdl )
 *      Endif
 */

ULONG semChkHdl(ULONG ulHandle,     /* handle to check */
                ULONG ulType,       /* type of semaphore */
                PPTDA pptda)        /* ptr to PTDA to use */

{
    ULONG ulIndex;                  /* array index */


    if (!(semVerifySigBits(ulHandle)))
      return (ERROR_INVALID_HANDLE);

    ulIndex = semGetIndex(ulHandle);
    if (semIfShared(ulHandle))                /* shared */
      return ( semChkSharedHdl(ulHandle,ulType,pptda) );  //98809
    else                                      /* private */
      return ( semChkPrivateHdl(ulIndex,ulType) );
}


/***LP  semGetTblHdl - Get Next Free Handle in Table
 *
 *      semGetTblHdl returns the next free handle in the
 *      given table and increments the free handle pointer.
 *
 *      ENTRY   pSemTbl     - pointer to the table to search
 *              ulTblSize   - current size of table
 *              pulNextFree - index of lowest free handle in table
 *              pulNextHdl  - pointer filled in with the next handle if found
 *
 *      EXIT    Success - NO_ERROR
 *              Failure - FAILURE
 *
 *      PSEUDO CODE
 *
 *      *pulNextHdl = free handle from pulNextFree
 *      For (each node in pSemTbl)
 *        If (empty spot)
 *          pulNextFree = index of empty spot
 *          return (NO_ERROR)
 *        Endif
 *      Endfor
 *      return (FAILURE)
 */

ULONG semGetTblHdl(PSEMTBL pSemTbl,           /* ptr to table to search */
                   register ULONG ulTblSize,  /* current size of table */
                   PULONG pulNextFree,        /* ptr to free handle index */
                   PULONG pulNextHdl)         /* ptr to next handle */

{
    register ULONG ulCt = 0;          /* counter for loop */
    register PSEMTBL pSem;            /* ptr to a position in sem table */


    TKBeginNoBlock();                  /* may NOT block */

    if (ulTblSize <= *pulNextFree) {
      TKEndNoBlock();
      return (FAILURE);
    }

    *pulNextHdl = *pulNextFree;
    for (ulCt = (*pulNextFree)+1, pSem = pSemTbl + ulCt;
         ulCt < ulTblSize; ulCt++, pSem++) {
      if (*pSem == NULL)
        break;
    }
    *pulNextFree = ulCt;
    TKEndNoBlock();
    return (NO_ERROR);
}


/***LP  semGetType - Get the Type of a Given Semaphore
 *
 *      semGetType returns the type of the given semaphore.
 *      It returns SEM_MTXTYPE for a mutex and SEM_EVTTYPE for
 *      an event.  It also assumes the handle is valid and is
 *      NOT a muxwait semaphore.
 *
 *      ENTRY   ulHandle - handle of the semaphore
 *
 *      EXIT    Success - SEM_MTXTYPE for mutex semaphore
 *                      - SEM_EVTTYPE for event semaphore
 *
 *      PSEUDO CODE
 *
 *      If (mutex semaphore)
 *        return (SEM_MTXTYPE)              // mutex
 *      return (SEM_EVTTYPE)                // event
 */

ULONG semGetType(ULONG ulHandle)        /* handle of semaphore */

{
    register PSEM pSem;                 /* ptr to a semaphore */
    ULONG ulIndex;                      /* array index */

    ulIndex = semGetIndex(ulHandle);
    if (semIfShared(ulHandle)) {                  /* shared */
      tkAssert(semChkSharedHdl(ulHandle,DCE_EVENT_SEM | DCM_MUTEX_SEM, //98809
                               pPTDACur) == NO_ERROR);  //98809
      pSem = pShSemTbl[ulIndex];
    }
    else {                                        /* private */
      tkAssert(semChkPrivateHdl(ulIndex,DCE_EVENT_SEM | DCM_MUTEX_SEM) == NO_ERROR);
      pSem = pPTDACur->pPrSemTbl[ulIndex];
    }

    tkAssert(!(((PSHUN)pSem)->SMux.usFlags & DCMW_MUX_SEM));
    if (((PSHUN)pSem)->SMtx.usFlags & DCM_MUTEX_SEM)
      return (SEM_MTXTYPE);
    return (SEM_EVTTYPE);
}


/***LP  semSlotToPidTid - Get PID and TID of Given Slot Number
 *
 *      semSlotToPidTid returns the process id and thread id of
 *      the thread with the given slot number.
 *
 *      ENTRY   usSlot - the slot number
 *              pPid   - pointer filled in with the pid
 *              pTid   - pointer filled in with the tid
 *
 *      EXIT    Success - NO_ERROR
 *              Failure - ERROR_INVALID_THREAD_ID
 *
 *      PSEUDO CODE
 *
 *      call rc = TKiSlotTo_pTCB with usSlot and get pTCB
 *      If (rc == no error)
 *        pPid = pTCB->TCBpPTDA->ptda_Pid
 *        pTid = pTCB->TCBOrdinal
 *      Endif
 *      return (rc)
 */

void semSlotToPidTid(USHORT usSlot,     /* slot number */
                     PPID pPid,         /* ptr to pid */
                     PTID pTid)         /* ptr to tid */

{
    PTCB pTCB;           /* ptr to a TCB */
    ULONG rc;            /* return code */


    if ((rc = TKiSlotTo_pTCB(usSlot,SSToDS(&pTCB))) == NO_ERROR) {
      tkAssert(pTCB != NULL);
      *pPid = pTCB->TCBpPTDA->ptda_Pid;
      *pTid = pTCB->TCBOrdinal;
    }
    tkAssert(rc == NO_ERROR);
}


/***LP  semGetOpenQNode - Get the Open Queue Node For Current Process
 *
 *      semGetOpenQNode gets the pointer to the OpenQ node of the
 *      semaphore for the current process.  It also returns the pointer
 *      to the previous node to make deletes faster.
 *
 *      This routine assumes that the open queue node for the current
 *      process exists for the given semaphore.  This routine will
 *      internal error if it does not exist.
 *
 *      ENTRY   pOpenN     - pointer to the start of the OpenQ to search
 *              ppCurOpenN - pointer filled in with the OpenQ node having
 *                           the correct process id
 *              ppPreOpenN - pointer filled in with the OpenQ node previous
 *                           to ppCurOpenN
 *              pidval     - process id to search for
 *
 *      EXIT    Success - open queue node is returned
 *
 *      PSEUDO CODE
 *
 *      ppPreOpenN = NULL
 *      ppCurOpenN = pOpenN
 *      While ((not end of list) && (cur thread's pid != cur node's pid))
 *        ppPreOpenN = ppCurOpenN
 *        ppCurOpenN = next node in list
 *      Endwhile
 */

void semGetOpenQNode(POPENQ pOpenN,                /* ptr to start of OpenQ */
                     register POPENQ *ppCurOpenN,  /* ptr to cur OpenQ node */
                     register POPENQ *ppPreOpenN,  /* ptr to prev OpenQ node */
                     register PID pidval)          /* process id to search for */

{
    *ppPreOpenN = NULL;
    *ppCurOpenN = pOpenN;
    while ((*ppCurOpenN != NULL) && (pidval != (*ppCurOpenN)->pidOpener)) {
      *ppPreOpenN = *ppCurOpenN;
      *ppCurOpenN = (*ppCurOpenN)->pNextOpen;
    }
    tkAssert(*ppCurOpenN != NULL);
}


/***LP  semSrchSnglForPid - Search Single Waiter TCB for Current PID
 *
 *      semSrchSnglForPid searches the list of threads waiting on
 *      a single mutex or event for the current process id.  If the
 *      process id is found, then a 1 is returned.  Otherwise, a 0 is
 *      returned.
 *
 *      ENTRY   pSem - pointer to the semaphore
 *
 *      EXIT    Success - NO_ERROR
 *              Failure - FAILURE
 *
 *      PSEUDO CODE
 *
 *      pTCB = call TKQueryWakeup
 *      For (each pTCB in list)
 *        If (pid of pTCB == current pid)
 *          return (NO_ERROR)                  // found it
 *        Endif
 *      Endfor
 *      return (FAILURE)                       // not found
 */

ULONG semSrchSnglForPid(PSEM pSem)       /* ptr to semaphore */

{
    register PTCB pTCB;                  /* ptr to a TCB node */


    pTCB = TKQueryWakeup(pSem,SEM_WAKE_ALL);    /* query TCB list */
    for (; pTCB != NULL; pTCB = pTCB->TCBpTCBWakeup) {
      if (pTCB->TCBpPTDA->ptda_Pid == pPTDACur->ptda_Pid)
        return (NO_ERROR);                 /* found it */
    }
    return (FAILURE);                      /* not found */
}


/***LP  semSrchMuxForPid - Search Mux TCB for Current PID
 *
 *      semSrchMuxForPid searches a list of threads waiting on a
 *      particular mux for the current process id.  If the process id
 *      is found, then a 1 is returned.  Otherwise, a 0 is returned.
 *
 *      ENTRY   pSem - pointer to the semaphore
 *
 *      EXIT    Success - NO_ERROR
 *              Failure - FAILURE
 *
 *      PSEUDO CODE
 *
 *      For (each MuxQ node in list)
 *        call TKQueryWakeup on mux pointed to by MuxQ node
 *        For (each pTCB in list)
 *          If (pid of pTCB == current pid)
 *            return (NO_ERROR)
 *          Endif
 *        Endfor
 *      Endfor
 *      return (FAILURE)
 */

ULONG semSrchMuxForPid(PSEM pSem)     /* ptr to semaphore */

{
    register PMUXQ pMuxSrch;     /* ptr to search through MuxQ */
    register PTCB pTCB;          /* ptr to a TCB node */
    PSEM pMux;                   /* ptr to mux */


    for (pMuxSrch=((PSHUN)pSem)->SMtx.pMuxQ; pMuxSrch != NULL;
         pMuxSrch = pMuxSrch->pNextMux) {
      pMux = (PSEM)pMuxSrch->pMux;
      pTCB = TKQueryWakeup(pMux,SEM_WAKE_ALL);

      for (; pTCB != NULL; pTCB = pTCB->TCBpTCBWakeup) {
        if (pTCB->TCBpPTDA->ptda_Pid == pTCBCur->TCBpPTDA->ptda_Pid)
          return (NO_ERROR);
      }
    }
    return (FAILURE);
}


/***LP  semChkSigInMux - Check SemRecord Entries for Handle Signature
 *
 *      semChkSigInMux validates the signature of each entry in a SemRec
 *      If they are wrong it returns an error. After they are checked,
 *      they are stripped off. Note that cSemRec is assumed to be correct.
 *
 *      ENTRY   pSemRec - pointer to the list of semrecords
 *              cSemRec - number of semaphores in pSemRec
 *
 *      EXIT    Success - NO_ERROR
 *              Failure - ERROR_INVALID_HANDLE
 *
 *      PSEUDO CODE
 *
 *      For (each handle in the semrec)
 *        validate the signature
 *        remove the signature
 *      Endfor
 */

ULONG semChkSigInMux(register PSEMRECORD pSemRec,   /* ptr to semrec of mux */
                     USHORT cSemRec)                /* # of sems in pSemRec */
{
    register PSEMRECORD pEndSemRec;      /* ptr to last semrec */


    tkAssert(cSemRec < (USHORT)pSemRec[0].ulUser);

    pEndSemRec = pSemRec + cSemRec;
    pSemRec++;
    for (;pSemRec <= pEndSemRec; pSemRec++) {
      if (semVerifySigBits(pSemRec->hsemCur))
        pSemRec->hsemCur = semStripSigBits(pSemRec->hsemCur);
      else
        return (ERROR_INVALID_HANDLE);
    }
    return (NO_ERROR);
}


/***LP  semChkSRInMux - Check SemRecord Entries For Mux
 *
 *      semChkSRInMux checks the semrecord entries for a
 *      mux semaphore.  If an error is found, then the error is
 *      returned.  Otherwise, there is no problem.
 *
 *      ENTRY   pSemRec - pointer to the list of semrecords
 *              cSemRec - number of semaphores in pSemRec
 *              usFlags - flags field of mux semaphore
 *                          (CreateMux passes in 0 for private sem
 *                           and 1 for shared sem.  No flags have
 *                           been set yet at the allocation layer).
 *
 *      EXIT    Success - NO_ERROR
 *              Failure - ERROR_EMPTY_MUXWAIT
 *                        ERROR_INVALID_HANDLE
 *                        ERROR_SEM_OWNER_DIED
 *                        ERROR_WRONG_TYPE
 *
 *      PSEUDO CODE
 *
 *      If (no semaphores in mux)
 *        return (ERROR_EMPTY_MUXWAIT)
 *      Endif
 *      For (each semaphore in semrecord of mux)
 *        If (shared)
 *          call semChkSharedHdl to validate handle
 *          pSem = pShSemTbl[ulIndex]
 *        Else                                           // private
 *          call semChkPrivateHdl to validate handle
 *          If (shared mux)
 *            return (ERROR_WRONG_TYPE)
 *          Endif
 *          pSem = pPTDACur->pPrSemTbl[ulHandle]
 *        Endif
 *        If (mutex semaphore)
 *          If (event mux)
 *            return (ERROR_WRONG_TYPE)
 *          if (usFlags & DM_OWNER_DIED)
 *            return (ERROR_SEM_OWNER_DIED)
 *        Else If (event semaphore)
 *          If (mutex mux)
 *            return (ERROR_WRONG_TYPE)
 *        Else                                    // muxwait semaphore
 *          return (ERROR_WRONG_TYPE)
 *        Endif
 *      Endfor
 *      return (NO_ERROR)
 */

ULONG semChkSRInMux(PSEMRECORD pSemRec,   /* ptr to semrecord */
                    USHORT cSemRec,       /* number of sems in pSemRec */
                    USHORT usFlags)       /* flags field of mux semaphore */

{
    ULONG ulHandle;                    /* handle of a semaphore */
    USHORT usType;                     /* type of semaphores in mux */
    USHORT usShrMux;                   /* 0 = private sem, 1 = shared sem */
    register PSEMRECORD pEndSemRec;    /* ptr to last semrecord */
    ULONG ulIndex;                     /* array index */
    register PSEM pSem;                /* ptr to a mutex or event semaphore */


    if (cSemRec == 0)
      return (ERROR_EMPTY_MUXWAIT);
    tkAssert(pSemRec != NULL);
    tkAssert((ULONG)cSemRec < pSemRec[0].ulUser);

    /*
     *   Need to check the assumption that SEM_EVTTYPE and SEM_MTXTYPE
     *   remain as 0 and 1, respectively.  If these constants change, then
     *   the computation of usType must change.
     *
     *   Also, if the wait any or wait all flag become <= 1, then the
     *   usFlags parameter will have to change.  This procedure assumes
     *   that a valid mux flag will have a value greater than 1.
     */
    tkAssert((SEM_EVTTYPE == 0) && (SEM_MTXTYPE == 1));
    tkAssert((DCMW_WAIT_ANY > 1) && (DCMW_WAIT_ALL > 1));
    if (usFlags <= 1) {
      usShrMux = usFlags;
      if (semChkHdl(pSemRec[1].hsemCur,DCE_EVENT_SEM | DCM_MUTEX_SEM,
                    pPTDACur) != NO_ERROR)
        return (ERROR_INVALID_HANDLE);
      usType = (USHORT)semGetType(pSemRec[1].hsemCur);
    }
    else {
      usShrMux = usFlags & (USHORT)DC_SEM_SHARED; /* 0 = private, 1 = shared */
      usType = usFlags & (USHORT)DMW_MTX_MUX;     /* 0 = event, 1 = mutex */
    }

    pEndSemRec = pSemRec + cSemRec;
    pSemRec++;
    for (; pSemRec <= pEndSemRec; pSemRec++) {
      ulIndex = semGetIndex((ulHandle = pSemRec->hsemCur));
      if (semIfShared(ulHandle)) {                 /* shared */
        if (semChkSharedHdl(ulHandle,DCE_EVENT_SEM | DCM_MUTEX_SEM, //98809
                            pPTDACur) != NO_ERROR)
          return (ERROR_INVALID_HANDLE);
        pSem = pShSemTbl[ulIndex];
      }
      else {                                       /* private */
        if (semChkPrivateHdl(ulIndex,DCE_EVENT_SEM | DCM_MUTEX_SEM) != NO_ERROR)
          return (ERROR_INVALID_HANDLE);
        if (usShrMux)                /* private sem cannot be in shared mux */
          return (ERROR_WRONG_TYPE);
        pSem = pPTDACur->pPrSemTbl[ulIndex];
      }

      if (((PSHUN)pSem)->SMtx.usFlags & DCM_MUTEX_SEM) {         /* mutex */
        if (usType == SEM_EVTTYPE)
          return (ERROR_WRONG_TYPE);
        if (((PSHUN)pSem)->SMtx.usFlags & DM_OWNER_DIED)
          return (ERROR_SEM_OWNER_DIED);
      }
      else if (((PSHUN)pSem)->SEvt.usFlags & DCE_EVENT_SEM) {    /* event */
        if (usType == SEM_MTXTYPE)
          return (ERROR_WRONG_TYPE);
      }
      else                                                       /* muxwait */
        return (ERROR_WRONG_TYPE);
    }
    return (NO_ERROR);
}


/***LP  semChkDupHandle - Check For Duplicate Handles in SemRecord Entries
 *
 *      semChkDupHandle checks the semrecord entries for a
 *      any duplicate handles.  If an error is found, then the error is
 *      returned.  Otherwise, no error is returned.
 *
 *      ENTRY   pSemRec - pointer to the list of semrecords
 *              cSemRec - number of semaphores in pSemRec
 *
 *      EXIT    Success - NO_ERROR
 *              Failure - ERROR_DUPLICATE_HANDLE
 *
 *      PSEUDO CODE
 *
 *      For (each semaphore in semrecord of mux)
 *        If (current handle == any other handle in semrecord)
 *          return (ERROR_DUPLICATE_HANDLE)
 */

ULONG semChkDupHandle(PSEMRECORD pSemRec,    /* ptr to semrecord */
                      USHORT cSemRec)        /* number of sems in pSemRec */

{
    register PSEMRECORD pEndSemRec;    /* ptr to last semrecord */
    register PSEMRECORD pSR;           /* ptr to search through semrecord */
    register ULONG ulHandle;           /* handle of a semaphore */


    if (cSemRec > 1) {
      tkAssert((ULONG)cSemRec < pSemRec[0].ulUser);

      pEndSemRec = pSemRec + cSemRec;
      pSemRec++;
      for (; pSemRec <= pEndSemRec; pSemRec++) {
        ulHandle = pSemRec->hsemCur;
        for (pSR=pSemRec+1; pSR <= pEndSemRec; pSR++) {
          if (ulHandle == pSR->hsemCur)
            return (ERROR_DUPLICATE_HANDLE);
        }
      }
    }
    return (NO_ERROR);
}


/***LP  semIfHdlInSR - Check If Handle Exists in Mux SemRecord
 *
 *      semIfHdlInSR checks to see if the given handle already
 *      exists in the mux semrecord list.  If the handle already exists, then
 *      a 1 is returned.  Otherwise a 0 is returned.
 *
 *      ENTRY   pMux     - pointer to the mux semaphore
 *              hsemChk  - handle of semaphore to check
 *              pulIndex - filled in with the index of the found entry
 *
 *      EXIT    Success - NO_ERROR
 *              Failure - FAILURE
 *
 *      PSEUDO CODE
 *
 *      For (each semaphore in semrecord of mux)
 *        If (handle in semrecord == hsemChk)
 *          If (pulIndex != NULL)
 *            pulIndex = index of found handle in semrecord
 *          Endif
 *          return (NO_ERROR)
 *        Endif
 *      Endfor
 *      return (FAILURE)
 */

ULONG semIfHdlInSR(register PSEM pMux,  /* ptr to the mux */
                   ULONG hsemChk,       /* handle to check */
                   PULONG pulIndex)     /* index of found entry */

{
    register ULONG ulCt;           /* loop counter */
    register ULONG ulEndCt;        /* number of times to reiterate in loop */
    register PSEMRECORD pSemRec;   /* ptr to semrecord of mux */


    pSemRec = ((PSHUN)pMux)->SMux.pSemRec;
    pSemRec++;
    ulEndCt = ((PSHUN)pMux)->SMux.cSemRec;
    for (ulCt=1; ulCt <= ulEndCt; ulCt++, pSemRec++) {
      if (pSemRec->hsemCur == hsemChk) {
        if (pulIndex != NULL)
          *pulIndex = ulCt;
        return (NO_ERROR);
      }
    }
    return (FAILURE);
}


/***LP  semIfAllEvtsPosted - Check If ALL Event Semaphores Posted
 *
 *      semIfAllEvtsPosted checks to see if ALL of the event
 *      semaphores in a particular mux are posted.  If all events are
 *      posted, then NO_ERROR is returned.  Otherwise, a FAILURE is returned.
 *
 *      ENTRY   pSemR   - pointer to the semrecord
 *              uscSemR - number of events in pSemR
 *
 *      EXIT    Success - NO_ERROR
 *              Failure - FAILURE
 *
 *      PSEUDO CODE
 *
 *      For (each event in mux)
 *        If (event is not posted)
 *          return (FAILURE)
 *        Endif
 *      Endfor
 *      return (NO_ERROR)
 */

ULONG semIfAllEvtsPosted(PSEMRECORD pSemR,     /* ptr to semrecord */
                         USHORT uscSemR)       /* number of events */

{
    ULONG ulHandle;                /* handle of event semaphore */
    ULONG ulIndex;                 /* array index */
    register ULONG ulCt;           /* loop counter */
    register PSEM pEvt;            /* ptr to an event semaphore */


    for (ulCt=1; ulCt <= uscSemR; ulCt++) {
      tkAssert(pSemR[ulCt].hsemCur != SEM_EMPTY_SEMREC);
      ulIndex = (semGetIndex((ulHandle = pSemR[ulCt].hsemCur)));
      if (semIfShared(ulHandle))
        pEvt = pShSemTbl[ulIndex];
      else
        pEvt = pPTDACur->pPrSemTbl[ulIndex];

      if (!(((PSHUN)pEvt)->SEvt.usFlags & DE_POSTED))
        return (FAILURE);
    }
    return (NO_ERROR);
}


/***LP  semIfAllMtxFree - Check If ALL Mutexes In Mux Are Free
 *
 *      semIfAllMtxFree checks to see if ALL of the mutex
 *      contained in a mux semaphore are unowned.  If all mutex are
 *      unowned, then a 1 is returned.  Otherwise, a 0 is returned.
 *
 *      ENTRY   pSemR   - pointer to the semrecord
 *              uscSemR - number of mutexes in pSemR
 *
 *      EXIT    Success - NO_ERROR
 *              Failure - FAILURE
 *
 *      PSEUDO CODE
 *
 *      For (each mutex in mux)
 *        If (mutex is owned)
 *          return (FAILURE)
 *        Endif
 *      Endfor
 *      return (NO_ERROR)
 */

ULONG semIfAllMtxFree(PSEMRECORD pSemR,    /* ptr to semrecord */
                      USHORT uscSemR)      /* number of mutexes */

{
    ULONG ulHandle;                /* handle of mutex semaphore */
    ULONG ulIndex;                 /* array index */
    register ULONG ulCt;           /* loop counter */
    register PSEM pMtx;            /* ptr to a mutex semaphore */


    for (ulCt=1; ulCt <= uscSemR; ulCt++) {
      tkAssert(pSemR[ulCt].hsemCur != SEM_EMPTY_SEMREC);
      ulIndex = (semGetIndex((ulHandle = pSemR[ulCt].hsemCur)));
      if (semIfShared(ulHandle))
        pMtx = pShSemTbl[ulIndex];
      else
        pMtx = pPTDACur->pPrSemTbl[ulIndex];

      if (((PSHUN)pMtx)->SMtx.usSlotNum != SEM_MUTEX_UNOWNED)
        return (FAILURE);
    }
    return (NO_ERROR);
}


/***LP  semOwnMtxInSR - Assign Ownership to Mutexes in SemRecord of Mux
 *
 *      semOwnMtxInSR assigns ownership to mutexes in the
 *      given semrecord.  The slot number of each mutex is set equal
 *      to the current slot number.
 *
 *      ENTRY   pSemR   - pointer to first semrecord to assign ownership
 *              pEndSR  - pointer to last semrecord to assign ownership
 *              pCurTCB - pointer to the TCB involved
 *
 *      EXIT    Success - appropriate ownership is assigned
 *
 *      PSEUDO CODE
 *
 *      For (each mutex from pSemR to pEndSR in mux)
 *        usSlotNum of mutex = pCurTCB's slot number
 *        usRequestCt = 1
 *        increment pCurPTDA->ulMtxOwned
 *      Endfor
 */

void semOwnMtxInSR(PSEMRECORD pSemR,      /* ptr to first semrecord */
                   PSEMRECORD pEndSR,     /* ptr to last semrecord */
                   PTCB pCurTCB)          /* ptr to TCB involved */

{
    register ULONG ulHandle;          /* handle of event or mutex */
    ULONG ulIndex;                    /* array index */
    register PSEM pMtx;               /* ptr to a mutex semaphore */
    PPTDA pCurPTDA;                   /* ptr to PTDA involved */


    pCurPTDA = pCurTCB->TCBpPTDA;
    for (; pSemR <= pEndSR; pSemR++) {
      tkAssert(pSemR->hsemCur != SEM_EMPTY_SEMREC);

      ulIndex = semGetIndex((ulHandle = pSemR->hsemCur));
      if (semIfShared(ulHandle))
        pMtx = pShSemTbl[ulIndex];
      else
        pMtx = pPTDACur->pPrSemTbl[ulIndex];

      tkAssert(((PSHUN)pMtx)->SMtx.usFlags & DCM_MUTEX_SEM);
      tkAssert(((PSHUN)pMtx)->SMtx.usSlotNum == SEM_MUTEX_UNOWNED);
      tkAssert(((PSHUN)pMtx)->SMtx.usRequestCt == 0);
      ((PSHUN)pMtx)->SMtx.usSlotNum = pCurTCB->TCBNumber;
      ((PSHUN)pMtx)->SMtx.usRequestCt = 1;
      pCurPTDA->ulMtxOwned++;
    }
}


/***LP  semAddToMuxQ - Add Node To MuxQ of Event or Mutex
 *
 *      semAddToMuxQ adds a MuxQ node to a given MuxQ list.
 *
 *      ENTRY   ulHandle - handle of the mutex/event
 *              pMuxQN   - pointer to the MuxQ node to add
 *
 *      EXIT    Success - mux queue node added to mux queue
 *
 *      PSEUDO CODE
 *
 *      If (ulHandle is shared)
 *        add pMuxQN to front of MuxQ of mutex/event in pShSemTbl
 *      Else
 *        add pMuxQN to front of MuxQ of mutex/event in pPTDACur->pPrSemTbl
 *      Endif
 */

void semAddToMuxQ(ULONG ulHandle,   /* handle of mutex or event */
                  PMUXQ pMuxQN)     /* ptr to MuxQ node to add */

{
    ULONG ulIndex;                  /* array index */
    register PSEM pSem;             /* ptr to mutex or event */


    ulIndex = semGetIndex(ulHandle);
    if (semIfShared(ulHandle))
      pSem = pShSemTbl[ulIndex];
    else
      pSem = pPTDACur->pPrSemTbl[ulIndex];

    pMuxQN->pNextMux = ((PSHUN)pSem)->SMtx.pMuxQ;
    ((PSHUN)pSem)->SMtx.pMuxQ = pMuxQN;
}


/***LP  semDelFromMuxQ - Delete MuxQ Node from Event or Mutex
 *
 *      semDelFromMuxQ deletes a node from the MuxQ of the
 *      given event or mutex.
 *
 *      ENTRY   ulHandle - handle of the mutex/event to update
 *              pMux     - ptr to mux containing mutex/event
 *
 *      EXIT    Success - mux queue node is deleted from mux queue
 *
 *      PSEUDO CODE
 *
 *      If (pMuxQ of mutex/event is empty)
 *        return
 *      Endif
 *      search MuxQ of mutex/event for pointer to mux
 *      If (not found)
 *        return
 *      Endif
 *      If (first one in list)
 *        remove first node
 *      Else                     // in middle or end of list
 *        remove from middle or end of list
 *      Endif
 *      free node from memory
 */

void semDelFromMuxQ(ULONG ulHandle,     /* handle of mutex or event */
                    PMUXUN pMux)        /* ptr to mux */

{
    PMUXQ pFirstPtr;                  /* ptr to 1st MuxQ node in mux queue */
    register PMUXQ pPrePtr = NULL;    /* ptr to previous mux queue node */
    register PMUXQ pCurPtr;           /* ptr to current mux queue node */
    register PSEM pSem;               /* ptr to mutex or event semaphore */
    ULONG ulIndex;                    /* array index */


    /*
     *  Get the pointer to the shared or private semaphore.
     */
    ulIndex = semGetIndex(ulHandle);
    if (semIfShared(ulHandle))
      pSem = pShSemTbl[ulIndex];
    else
      // The following line caused a fatal page fault when semDelFromMuxQ
      // was called under the context of the process that cleared a shared
      // semaphore within a private mux and not under the context of the
      // process that owned the private mux.  Now a private mux has a PTDA
      // associated with it for locating its private semaphores from a
      // different process.
      //
      //    pSem = pPTDACur->pPrSemTbl[ulIndex];
      pSem = pMux->PrMux.pPTDA->pPrSemTbl[ulIndex];

    /*
     *  If the semaphore does not exist, or if the mutex is owner died, or
     *  if the semaphore is a mux, then return.
     */
    if ((pSem == NULL) || (((PSHUN)pSem)->SMtx.usFlags & DM_OWNER_DIED) ||
        (((PSHUN)pSem)->SMux.usFlags & DCMW_MUX_SEM))
      return;

    /*
     *  Search down the list until the correct mux queue node is found.
     *  Delete the mux queue node from the list.
     */
    pFirstPtr = ((PSHUN)pSem)->SMtx.pMuxQ;
    if (pFirstPtr != NULL) {
      pCurPtr = pFirstPtr;
      while ((pCurPtr != NULL) && (pCurPtr->pMux != pMux)) {
        pPrePtr = pCurPtr;
        pCurPtr = pCurPtr->pNextMux;
      }
      if (pCurPtr == NULL)                         /* not found */
        return;
      if (pPrePtr == NULL)                         /* first one in list */
        ((PSHUN)pSem)->SMtx.pMuxQ = pCurPtr->pNextMux;
      else                                         /* in middle of list */
        pPrePtr->pNextMux = pCurPtr->pNextMux;
      pCurPtr->pNextMux = pFreeMux;
      pFreeMux = pCurPtr;
      ulFreeMuxCount++;
    }
}


/***LP  semUpdateAllMuxQ - Decrement WaitCt and Update MuxQ Nodes
 *
 *      semUpdateAllMuxQ decrements the wait count for the
 *      muxwait semaphore.  It then calls semDelAllMuxQ for all
 *      semaphores that are part of a mux if the wait count of
 *      the muxwait has gone to zero.
 *
 *      ENTRY   pMux - pointer to the mux structure
 *
 *      EXIT    Success - wait count is decremented
 *
 *      PSEUDO CODE
 *
 *      decrement the wait count
 *      If (mux wait count == 0)
 *        For (each entry in semrecord of mux)
 *          delete appropriate mux queue node
 *        Endfor
 *      Endif
 */

void semUpdateAllMuxQ(PMUXUN pMux)       /* ptr to the mux */

{
    tkAssert(pMux->ShMux.usWaitCt > 0);
    if (--(pMux->ShMux.usWaitCt) == 0)
      semDelAllMuxQ(pMux);
}


/***LP  semDelAllMuxQ - Remove All MuxQ Nodes In Mux From Semaphore
 *
 *      semDelAllMuxQ removes all MuxQ nodes from the events or
 *      mutexes contained in the given mux.  If there are no mutexes
 *      or events in the mux, then this routine simply returns.
 *      Otherwise, the appropriate mux queue nodes are removed.
 *
 *      ENTRY   pMux - pointer to the muxwait semaphore
 *
 *      EXIT    Success - all appropriate mux queue nodes are removed
 *
 *      PSEUDO CODE
 *
 *      If (semrecord list of mux is not empty)
 *        For (each event/mutex in semrecord list of mux)
 *          delete appropriate mux queue node
 *        Endfor
 *      Endif
 */

void semDelAllMuxQ(register PMUXUN pMux)   /* ptr to the mux semaphore */

{
    register PSEMRECORD pSRPtr;       /* ptr to the SEMRECORD array of mux */
    register ULONG ulCt;              /* loop counter */


    pMux->ShMux.usWaitCt = 0;
    if ((pSRPtr = pMux->ShMux.pSemRec) != NULL) {
      for (ulCt=1; ulCt <= pMux->ShMux.cSemRec; ulCt++)
        semDelFromMuxQ((++pSRPtr)->hsemCur,pMux);
    }
}


/***LP  semUpdateFreeMuxQ - Free Extra MuxQ Nodes
 *
 *      semUpdateFreeMuxQ frees any MuxQ nodes in the free pool.
 *
 *      ENTRY   ulFlag - 0 = Free until < SEM_MAXSEMS
 *                      ~0 = Free all
 *
 *      EXIT    Success  - Nodes are freed
 *
 *      PSEUDO CODE
 *
 *      While (too many nodes in pool)
 *        free node
 *      Endwhile
 */

void semUpdateFreeMuxQ(ULONG ulFlag)        /* flag of how many to free */

{
   register ULONG ulMaxNodes;               /* max # to remain in pool */
   register PMUXQ pMux;                     /* ptr to mux queue node */


   if (ulFlag)
     ulMaxNodes = 0;
   else
     ulMaxNodes = SEM_MAXSEMS;

   while (ulFreeMuxCount > ulMaxNodes) {
     pMux = pFreeMux;
     pFreeMux = pFreeMux->pNextMux;
     --ulFreeMuxCount;
     semAssertMuxQSig(pMux);
     freeKRHB(pMux);
   }
}


/***LP  semFreeMuxQList - Free Entire List of MuxQ Nodes
 *
 *      semFreeMuxQList frees the entire list of mux queue nodes.
 *
 *      ENTRY   pMuxQN - pointer to the first MuxQ node
 *
 *      EXIT    Success - all mux queue nodes are freed
 *
 *      PSEUDO CODE
 *
 *      For (each MuxQ node in linked list)
 *        if (<= SEM_MAXSEM nodes in free pool)
 *          add to free pool
 *        else
 *          free node
 *        endif
 *      Endfor
 */

void semFreeMuxQList(register PMUXQ pMuxQN)   /* ptr to first MuxQ node */

{
    register PMUXQ pPreMuxQ;               /* ptr to previous MuxQ node */


    while (pMuxQN != NULL) {
      pPreMuxQ = pMuxQN;
      pMuxQN = pMuxQN->pNextMux;
      pPreMuxQ->pNextMux = pFreeMux;
      pFreeMux = pPreMuxQ;
      ulFreeMuxCount++;
    }
}


/***LP  semHash - Hash a Semaphore String
 *
 *      semHash hashes a string of even DWORD length and returns a
 *      ULONG hash value.
 *
 *      ENTRY   iLen - length of the string
 *              psz  - the string to hash
 *
 *      EXIT    hash value
 */

ULONG semHash(register INT iLen,        /* length of the string */
              PSZ psz)                  /* the string to hash */

{
    register INT i,i2;
    register ULONG ulHash = 0;
    char ach[4];


    ((ULONG*)ach)[0] = 0;
    for (i=0; i < (iLen & ~3); i += 4)
      ulHash += ((ULONG*)psz)[i/4];
    if (iLen & 3) {
      for (i2=0; psz[i]; i++, i2++)
        ach[i2] = psz[i];
    }
    return (ulHash + ((ULONG*)ach)[0]);
}


/***LP  semGetStr - Get String in Shared Table
 *
 *      semGetStr returns the index of the handle of the shared
 *      semaphore containing the given pszName.  If the pszName is
 *      in the table, it returns 1.  Otherwise, it returns 0.
 *
 *      ENTRY   pszName  - the string to find
 *              pulIndex - pointer filled in with the index
 *
 *      EXIT    Success - NO_ERROR
 *              Failure - FAILURE
 *
 *      PSEUDO CODE
 *
 *      call TKFuBuffLenz to get length of pszName
 *      call semStrTblSrch
 *      For (each string node with same hash value)
 *        If (strings are the same)
 *          *pulIndex = pStrNode->hsem
 *          return (NO_ERROR)
 *        Endif
 *      Endfor
 *      return (FAILURE)
 */

ULONG semGetStr(PSZ pszName,          /* string to find */
                PULONG pulIndex)      /* ptr to index */

{
    PSEMTBLNODE pNode;                /* ptr to table node */
    register PSEMSTRNODE pStrNode;    /* ptr to string node */


    tkAssert(pszName > (PSZ)SEL_512MEG);
    KSEMRequestMutex(hksStrTbl,SEM_INDEFINITE_WAIT);
    if (semStrTblSrch(semHash(strlen(pszName),pszName),SSToDS(&pNode))
                     != NO_ERROR) {
      KSEMReleaseMutex(hksStrTbl);
      return (FAILURE);
    }
    pStrNode = pNode->pStrNode;

    while (pStrNode) {
      tkAssert(pStrNode->psz != NULL);
      if (!strcmp(pszName,pStrNode->psz)) {
        *pulIndex = pStrNode->hsem;
        KSEMReleaseMutex(hksStrTbl);
        return (NO_ERROR);
      }
      else
        pStrNode = pStrNode->pNext;
    }
    KSEMReleaseMutex(hksStrTbl);
    return (FAILURE);
}


/***LP  semStoreStr - Store a String In Internal Semaphore Format
 *
 *      semStoreStr allocates space for, hashes, and stores a string
 *      in system name space.
 *
 *      ENTRY   pszSource - pointer to the source string
 *              pphsem    - address of pointer to semaphore handle
 *
 *      EXIT    Success - NO_ERROR
 *              Failure - ERROR_DUPLICATE_NAME
 *
 *      PSEUDO CODE
 *
 *      get size of pszSource
 *      zero end of destination space so hash functions on the
 *         equivalent space will be the same
 *      store string
 *      hash string
 *      return (NO_ERROR)
 */

ULONG semStoreStr(PSZ pszSource,       /* ptr to source string */
                  PULONG *pphsem)      /* ptr to semaphore handle */
{
    PSEMSTRNODE pStrNode;       /* ptr to a string node */
    ULONG rc;                   /* return code */


    if ((rc = VMAllocKHB(VM_HKH_PUB_SWAPRW,sizeof(SEMSTRNODE),(VMHOB)SEMSTROWNER,NA,
                         SSToDS(&pStrNode))) != NO_ERROR) {
      return (rc);
    }
    semInitSNodeSig(pStrNode);

    *pphsem = &(pStrNode->hsem);
#ifdef MISCSTRICT
    /* Big (legal) value will likely cause error if hsem not filled in. */
    pStrNode->hsem = 0xffff;
#endif
    /*
       I moved the sem acquistion around the table lookup, it had been
       just prior to the insert. This way there's less (no?) chance of
       this getting stepped on.  defect 67077
     */
    KSEMRequestMutex(hksStrTbl,SEM_INDEFINITE_WAIT);

    if (semGetStr(pszSource,*pphsem) == NO_ERROR) {
      VMFreeKHB(VM_HKH_PUB_SWAPRW,pStrNode);
      KSEMReleaseMutex(hksStrTbl);
      return (ERROR_DUPLICATE_NAME);
    }

    pStrNode->psz = pszSource;

    if ((rc = semStrTblInsert(semHash(strlen(pszSource),pszSource),
       pStrNode)) != NO_ERROR) {
      VMFreeKHB(VM_HKH_PUB_SWAPRW,pStrNode);
      KSEMReleaseMutex(hksStrTbl);
      return (rc);
    }
    KSEMReleaseMutex(hksStrTbl);
    return (NO_ERROR);
}


/***LP  semStrTblSrch - Search Shared String table For Key
 *
 *      semStrTblSrch searches through the shared string table
 *      for a matching key.
 *
 *      ENTRY   ulKey  - key to search for
 *              ppNode - pointer to matching table entry
 *
 *      EXIT    Success - NO_ERROR
 *              Failure - ERROR_INVALID_HANDLE
 *
 *      PSEUDO CODE
 *
 *      initialize pNode to the middle of the string table
 *      While (TRUE)
 *        If (pNode contains a valid entry)
 *          If (it's the right one)
 *            return (NO_ERROR)
 *          Else If (pNode->ulKey is too big)
 *            set pNode to midway between its current value and
 *            the next lowest value that has been read
 *          Else
 *            set pNode to midway between it current value and
 *            the next highest value that has been read
 *          Endif
 *        Else
 *          find the boundaries of the 'hole'
 *          If (pHigh->ulKey is < ulKey)
 *            set pNode to midway between its current value and
 *            the next highest value that has been used
 *          Else If (pHigh is the right node)
 *            return (NO_ERROR)
 *          Endif
 *          If (pLow->ulKey is > ulKey)
 *            set pNode to midway between its current value and
 *            the next lowest value that has been read
 *          Else If (pLow->ulKey is the right node)
 *            return (NO_ERROR)
 *          Endif
 *        Endif
 *      Endwhile
 */

ULONG semStrTblSrch(ULONG ulKey,            /* key to search for */
                    PSEMTBLNODE *ppNode)    /* ptr to found table entry */

{
    ULONG ulInc;                        /* increment/decrement for search */
    register PSEMTBLNODE pNode;         /* for speed, mirrors *ppNode */
    register PSEMTBLNODE pTmp1, pTmp2;  /* for speed on boundary searches */
#ifdef MISCSTRICT
    KSEMSTATE sKState;                  /* For KSEMQuery */
    PSEMSTRNODE pStrNode;               /* For table integrity verification */

    KSEMQuery(hksStrTbl,SSToDS(&sKState));
    tkAssert(sKState.kss_fOwned && (sKState.kss_tid == pTCBCur->TCBNumber));

    /* Verify table Integrity */
    for (ulInc = 0; ulInc < ulShSemStrTblSize; ulInc++) {
       if ((pStrNode = pShSemStrTbl[ulInc].pStrNode) != NULL) {
          for (;pStrNode != NULL; pStrNode = pStrNode->pNext) {
             tkAssert(pStrNode->psz != NULL);
             tkAssert(pStrNode->hsem < SEM_MAXTBLSIZE);
          }
       }
    }
#endif

    ulInc = ulShSemStrTblSize/2;
    pNode = pShSemStrTbl + ulInc;
    ulInc /= 2;
    while (1) {
      if (pNode->pStrNode) {
        if (ulKey < pNode->ulKey) {
          if (ulInc > 0) {
            pNode -= ulInc;
            ulInc /= 2;
            continue;
          }
          else if ((pNode == pShSemStrTbl+1) && (ulInc == 0)) {
            pNode--;
            continue;
          }
          else {
            *ppNode = pNode;
            return (ERROR_INVALID_HANDLE);
          }
        }
        else if (ulKey > pNode->ulKey) {
          if (ulInc > 0) {
            pNode += ulInc;
            ulInc /= 2;
            continue;
          }
          else {
            *ppNode = pNode;
            return (ERROR_INVALID_HANDLE);
          }
        }
        else {
          *ppNode = pNode;
          return (NO_ERROR);
        }
      }
      else {
        /* Find the boundaries for valid nodes. Reg tmps for speed */
        /* First, the low end */
        pTmp1 = pShSemStrTbl;
        for (pTmp2 = pNode; pTmp2 > pTmp1; pTmp2--) {
          if (pTmp2->pStrNode)
            break;
        }
        if (pTmp2->pStrNode) {
          if (pTmp2->ulKey > ulKey) {
            if (ulInc > 0) {
              pNode -= ulInc;
              ulInc /= 2;
              continue;
            }
            else if ((pNode == pShSemStrTbl+1) && (ulInc == 0)) {
              pNode--;
              continue;
            }
            else {
              *ppNode = pNode;
              return (ERROR_INVALID_HANDLE);
            }
          }
          else if (pTmp2->ulKey == ulKey) {
            *ppNode = pTmp2;
            return (NO_ERROR);
          }
        }
        /* Now the high end */
        pTmp1 = pTmp1 + ulShSemStrTblSize - 1;
        for (pTmp2 = pNode; pTmp2 < pTmp1; pTmp2++) {
          if (pTmp2->pStrNode)
            break;
        }
        if (pTmp2->pStrNode) {
          if (pTmp2->ulKey < ulKey) {
            if (ulInc > 0) {
              pNode += ulInc;
              ulInc /= 2;
              continue;
            }
            else {
              *ppNode = pNode;
              return (ERROR_INVALID_HANDLE);
            }
          }
          else if (pTmp2->ulKey == ulKey) {
            *ppNode = pTmp2;
            return (NO_ERROR);
          }
        }
        /* If neither of those worked, then insert. */
        *ppNode = pNode;
        return (ERROR_INVALID_HANDLE);
      }
    }
}


/***LP  semStrTblInsert - Insert Node In String Table
 *
 *      semStrTblInsert inserts a SEMSTRNODE in the string table. If
 *      necessary, the table is grown.
 *
 *      ENTRY   ulKey    - hash value
 *              pStrNode - node to be inserted.
 *
 *      EXIT    Success - NO_ERROR
 *              Failure - ULONG, error code
 *
 *      PSEUDO CODE
 *
 *      If (table is full)
 *        grow table
 *      Endif
 *      search for entry
 *      If (entry is found)
 *        add pStrNode to linked list
 *      Else
 *        insert node
 *      Endif
 *      return (NO_ERROR)
 */

ULONG semStrTblInsert(ULONG ulKey,              /* hash value */
                      PSEMSTRNODE pStrNode)     /* node to be inserted */

{
    PSEMTBLNODE pNode;                          /* ptr to table node */
    register PSEMTBLNODE pNodeLow, pNodeHigh;   /* search nodes */
    register PSEMTBLNODE pTmp;                  /* for speed */
    ULONG rc;                                   /* return code */

#ifdef MISCSTRICT
    KSEMSTATE sKState;                  /* For KSEMQuery */

    KSEMQuery(hksStrTbl,SSToDS(&sKState));
    /*
     *  Current thread must have hksStrTbl kernel semaphore at this point.
     */
    tkAssert(sKState.kss_fOwned && (sKState.kss_tid == pTCBCur->TCBNumber));
#endif


    if (ulShSemStrTblUsed == ulShSemStrTblSize) {
      if ((rc = VMReallocKHB(VM_HKH_PUB_RESRW,&pShSemStrTbl,
                        ulShSemStrTblSize * SEM_TBLINCR * sizeof(SEMTBLNODE),
                        0)) != NO_ERROR)
          return (rc);
      memset(&(pShSemStrTbl[ulShSemStrTblSize]),'\0',
             ulShSemStrTblSize * sizeof(SEMTBLNODE) * (SEM_TBLINCR-1));
      ulShSemStrTblSize *= SEM_TBLINCR;
    }
    pStrNode->pNext = NULL;

    if (semStrTblSrch(ulKey,SSToDS(&pNode)) == NO_ERROR) {
      tkAssert((pNode != NULL) && (pNode->ulKey == ulKey) &&
               (pNode->pStrNode != NULL));
      pStrNode->pNext = pNode->pStrNode;
      pNode->pStrNode = pStrNode;
      return (NO_ERROR);
    }
    else {
      if (pNode->pStrNode == NULL) {
        pNode->ulKey = ulKey;
        pNode->pStrNode = pStrNode;
        ulShSemStrTblUsed++;
        return (NO_ERROR);
      }
      else {
        /*
         *  Find the nearest blank space.
         */
        pTmp = pShSemStrTbl;
        for (pNodeLow = pNodeHigh = pNode; (pNodeLow->pStrNode &&
          pNodeHigh->pStrNode);) {
          if (pNodeHigh < pTmp + ulShSemStrTblSize-1)
            pNodeHigh++;
          if (pNodeLow > pTmp)
            pNodeLow--;
        }
        pTmp = pNode;
        if (pNodeHigh->pStrNode == NULL) {
          if (pTmp->ulKey < ulKey)
            ++pTmp;
          for (;pNodeHigh > pTmp; pNodeHigh--) {
            pNodeHigh->ulKey = (pNodeHigh-1)->ulKey;
            pNodeHigh->pStrNode = (pNodeHigh-1)->pStrNode;
          }
        }
        else {
          if (pTmp->ulKey > ulKey)
               --pTmp;
          for (;pNodeLow < pTmp; pNodeLow++) {
            pNodeLow->ulKey = (pNodeLow+1)->ulKey;
            pNodeLow->pStrNode = (pNodeLow+1)->pStrNode;
          }
        }
        pTmp->ulKey = ulKey;
        pTmp->pStrNode = pStrNode;
        ulShSemStrTblUsed++;
        return (NO_ERROR);
      }
    }
}


/***LP  semStrTblDelete - Delete An Entry From The String Table
 *
 *      semStrTblDelete frees up the space associated with a given entry
 *      in the string table. It is used during the close of named semaphores
 *      and during process death.
 *
 *      ENTRY   pszName - name of entry to delete
 *
 *      EXIT    Success - NO_ERROR
 *              Failure - FAILURE
 *
 *      PSEUDO CODE
 *
 *      find entry
 *      delete it
 */

ULONG semStrTblDelete(PSZ pszName)       /* name of entry to delete */

{
    PSEMTBLNODE pNode;                   /* ptr to table node */
    register PSEMSTRNODE pStrNode;       /* search node */
    register PSEMSTRNODE pPrevStrNode;   /* search node */


    tkAssert(pszName > (PSZ)SEL_512MEG);         /* Kernel space only */
    KSEMRequestMutex(hksStrTbl,SEM_INDEFINITE_WAIT);
    if (semStrTblSrch(semHash(strlen(pszName),pszName),SSToDS(&pNode))
                     != NO_ERROR) {
      KSEMReleaseMutex(hksStrTbl);
      return (FAILURE);
    }
    tkAssert(pNode != NULL);
    pStrNode = pNode->pStrNode;
    pPrevStrNode = NULL;

    while (pStrNode) {
      tkAssert(pStrNode->psz != NULL);
      if (!strcmp(pszName,pStrNode->psz)) {
        if (pPrevStrNode)
         pPrevStrNode->pNext = pStrNode->pNext;
        else {
         /*
            Before this logic basically threw away the subsequent hash
            leaves. This caused subsequent Opens for the sems to fail.
            Also, only decrement table used count if no more leaves are
            present.    defect 67077
         */
#if 0
         ulShSemStrTblUsed--;
         pNode->pStrNode = NULL;
#else
         pNode->pStrNode = pStrNode->pNext;
         if ( pNode->pStrNode == NULL )
            ulShSemStrTblUsed--;
#endif
        }
        semAssertSNodeSig(pStrNode);
        VMFreeKHB(VM_HKH_PUB_SWAPRW,pStrNode);
        KSEMReleaseMutex(hksStrTbl);
        return (NO_ERROR);
      }
      else {
        pPrevStrNode = pStrNode;
        pStrNode = pStrNode->pNext;
      }
    }
    KSEMReleaseMutex(hksStrTbl);
    return (FAILURE);
}


/***LP  semValidateName - Validate Semaphore Name
 *
 *      semValidateName checks that a semahore name is valid and then
 *      stores it in the name table. The return name in pszKName has
 *      been uppercased and stripped of the \SEM32\ prefix.
 *
 *      ENTRY   pszName   - pointer to name in User space
 *              ppszKName - pointer to name in Kernel space
 *
 *      EXIT    Success - NO_ERROR
 *              Failure - ERROR_INVALID_NAME
 */

ULONG semValidateName(PSZ pszName,      /* ptr to user name */
                      PSZ *ppszKName)   /* ptr to kernel name */
{
    INT iLen;           /* length of string */
    SEL sel;            /* Temporary selector */
    ULONG rc;           /* return code */


    if ((rc = TKFuBuffLenz(SSToDS(&iLen),pszName,SEM_MAXNAME,
                           TK_UM_FATAL)) != NO_ERROR) {
      if (rc == ERROR_TERMINATOR_NOT_FOUND)
        return (ERROR_INVALID_NAME);
      else
        return (rc);
    }
    if ((iLen < SEM_PREFIXLEN) || (iLen > SEM_MAXNAME))
      return (ERROR_INVALID_NAME);

    /*
     *  Get a selector.
     */
    if ((rc = SELAllocGDT(SSToDS(&sel))) != NO_ERROR)
      return (rc);

    /*
     *  Allocate a chunk of memory.
     */
    if ((rc = VMAllocKHB(VM_HKH_PUB_SWAPRW,SEM_MAXNAME,(VMHOB)SEMSTROWNER,NA,
                         ppszKName)) != NO_ERROR) {
      SELFreeGDT(sel);
      return (rc);
    }

    /*
     *  Map it into the selector.
     */
    SELSetDescInfo(SELSD_ALL,SELAL_W | SELAL_R | D_DATA0 | D_SEG
                 | D_PRES,sel,SEM_MAXNAME,(ULONG)*ppszKName,0,0,0);

    /*
     *  Copy string from user space to kernel space.
     */
    if ((rc = TKFuBuffz(SSToDS(&iLen),*ppszKName,pszName,(iLen+1),
                        TK_UM_FATAL)) != NO_ERROR) {
      SELFreeGDT(sel);
      VMFreeKHB(VM_HKH_PUB_SWAPRW,*ppszKName);
      return (rc);
    }

    /*
     *  Translate path chars.
     */
    PathCharTrans(*ppszKName);

    /*
     *  Canonicalize the string.
     */
    if ((rc = Canon(sel,0L,0L,(ULONG)iLen,2L)) != NO_ERROR) {
      SELFreeGDT(sel);
      VMFreeKHB(VM_HKH_PUB_SWAPRW,*ppszKName);
      return (rc);
    }
    if (strncmp(SEM_PREFIX,*ppszKName,SEM_PREFIXLEN)) {
      SELFreeGDT(sel);
      VMFreeKHB(VM_HKH_PUB_SWAPRW,*ppszKName);
      return (ERROR_INVALID_NAME);
    }
    /*
     *  Remove the '\SEM32\'.
     */
    memcpy(*ppszKName,(((PSZ)(*ppszKName))+SEM_PREFIXLEN),iLen-SEM_PREFIXLEN+1);

    /*
     *  Adjust the block size.
     */
    VMReallocKHB(VM_HKH_PUB_SWAPRW,ppszKName,iLen-SEM_PREFIXLEN+1,0);

    /*
     *  Free the selector.
     */
    SELFreeGDT(sel);
    return (NO_ERROR);
}


/***EP  SEMMuxWait16 - Make Semaphore Part Of 16-bit Muxwait
 *
 *      SEMMuxWait16 OR's in the DCE_16BIT_MW flag to Event semaphores.
 *      It is called from 16-bit MuxWait code.
 *
 *      ENTRY   hev - event semaphore handle
 *
 *      EXIT    Success - NO_ERROR
 *              Failure - ERROR_INVALID_HANDLE
 */

ULONG SEMMuxWait16(HEV hev)            /* event handle */

{
    ULONG ulIndex;                     /* array index */


    if (semChkHdl(hev,DCE_EVENT_SEM,pPTDACur) != NO_ERROR)
      return (ERROR_INVALID_HANDLE);
    ulIndex = semGetIndex(hev);
    if (semIfShared(hev))                        /* shared */
      ((PSEVENT)(pShSemTbl[ulIndex]))->usFlags |= DE_16BIT_MW;
    else                                         /* private */
      ((PPEVENT)(pPTDACur->pPrSemTbl[ulIndex]))->usFlags |= DE_16BIT_MW;

    return (NO_ERROR);
}


/***EP  SEMFindType - Return The Type Of The Given Semaphore
 *
 *      SEMFindType returns the type of semaphore and whether the
 *      semaphore is shared or private.  First it validates the
 *      handle.  If an invalid 32-bit semaphore handle is passed in,
 *      a 0 (meaning error) is returned.  Otherwise, it will return
 *      the type of the semaphore and whether it's shared or private
 *      in the form of flags.  The flags are:
 *
 *          Type:  DCE_EVENT_SEM      Shared:  DC_SEM_SHARED
 *                 DCM_MUTEX_SEM
 *                 DCMW_MUX_SEM       Private: DC_SEM_SHARED bit not set
 *
 *      NOTE: THIS ROUTINE RETURNS A 0 WHEN THERE IS AN ERROR!
 *
 *      ENTRY   hSem - semaphore handle
 *
 *      EXIT    Success - returns sem type and shared/private
 *              Failure - 0 (zero)
 *
 *      PSEUDO CODE
 *
 *      If (not a valid 32-bit sem handle)
 *        return ( 0 )                                 // ERROR!
 *      return ( sem type and shared/private flags )   // No Error
 */

ULONG SEMFindType(HSEM hSem)    /* semaphore handle */

{
    ULONG ulIndex;              /* array index */
    register PSEM pSem;         /* ptr to the semaphore */
    HSEM tmpSem;


    tkAssertTasktime();        /* call NOT allowed at interrupt time */

/* Defect 66837 - Virginia Romero   OS/2 CHANGE TEAM */
/* First make sure that IT IS a 32 bit semaphore.... */

//115627    tmpSem = hSem & SEM_HANDLESIG;                  //98809
    tmpSem = hSem & SEM_SIGBITS;                  //115627
    if (!(tmpSem == SEM_HANDLESIG)) return (0);

    ulIndex = semGetIndex(hSem);
    if (semIfShared(hSem)) {
      /*
       *  Shared semaphore.  Make sure index is less than the shared
       *  table size and that the table entry is not null.
       */
      if ((ulIndex >= ulShTblSize) || ((pSem = pShSemTbl[ulIndex]) == NULL))
        return (0);
      tkAssert(((PSHUN)pSem)->SEvt.usFlags & DC_ALL_SEMS);
    }
    else {
      /*
       *  Private semaphore.  Make sure index is less than the private
       *  table size and that the table entry is not null.
       */
      if ((ulIndex >= pPTDACur->ulPrTblSize) ||
          ((pSem = pPTDACur->pPrSemTbl[ulIndex]) == NULL))
        return (0);
      tkAssert(((PPRUN)pSem)->PEvt.usFlags & DC_ALL_SEMS);
    }

    /*
     *  Return the flag to denote the type of semaphore and whether or not
     *  the semaphore is shared.
     */
    return ( ((PSHUN)pSem)->SEvt.usFlags & (DC_ALL_SEMS | DC_SEM_SHARED) );
}

