/*static char *SCCSID = "@(#)lde.c      6.3 92/01/31";*/
#define ASWAP1 ASWAP1
#define INCL_DOSERRORS
#include <os2def.h>
#include <bse.h>
#include <cdib.h>

#include "api.h"
#include "const.h"
#include "misc.h"
#include "chain.h"
#include "buf.h"
#include "dir.h"
#include "volume.h"
#include "storage.h"
#include "tables.h"
#include "fnode.h"
#include "ea.h"
#include "pb_ifs.h"
#include "lw.h"
#include "frame.h"
#include "mmphiseg.h"
#include "fsdata.h"
#include "pbmacros.h"
#include "codepage.h"
#include "log.h"
#include "pr_ALLOC.h"
#include "pr_BITMP.h"
#include "pr_CACHE.h"
#include "pr_DIR.h"
#include "pr_MISC.h"
#include "pr_MOVE.h"
#include "pr_debug.h"
#include "assert.h"
#include "mmph.h"

/*
 * This macro zeros fields in a new dirent.  When we do security don't
 * forget to zero out pmOwner, pmOther, uidOwner.
 */
#define ZERO_FIELDS(pdeX) {                             \
    pdeX->cchFSize = 0;                                 \
    pdeX->ulEALen = 0;                                  \
}

STATIC BOOL fSPDBufBusy = 0; /* LDEFlag byte flag indicating SPDBuf is busy */

STATIC PVOID pLDEWait = 0;   /* Wait chain for SPDBuf  */

/*  Substitute "\0." for zero length name:  */
PCHAR pszDot = "\03\01\01";

#ifndef MINIFSD
/*
 * These are the two temporary buffers needed by LDE to hold dir. entries when
 * dir. blocks are being split.
 */
STATIC BYTE     abBuf[MAX_DIRENT];      /* scratch buffer */
#endif

/*
 ***    LDE - Lookup Directory Entry
 *
 *      LDE searches a directory btree for an entry
 *
 *      Since the directories are in BTREE format, we know that we're
 *      always searching towards lexically greater names.
 *
 *      Note that if we are to create an entry, we don't allocate
 *      an FNODE or any data blocks for it; we let the caller do this
 *      so that he can allocate them together.
 *
 *      LDE is a pretty big routine, but it's broken down into logical
 *      sectors.  Flow is always downwards, except that the last section
 *      may loop.
 *
 * WARNING: This code assumes that there are assumes 4 sectors in a buffer
 * WARNING: This code assumes that a directory block is 2 sectors
 *
 *      BUGBUG - caller doesn't flush dir, I think.  Caller must
 *      allocate FNODE for creation!
 *
 *      Note that if a new leaf entry is created, the buffer sectors will
 *      be marked dirty but they won't be put on the lazywrite queue
 *      nor written-through if the write-through flag is set.  This
 *      is because the caller will be setting in more information and will
 *      have to do this work anyway, so if LDE did it and we were writting
 *      through there'd be extra, wasted disk writes.
 *
 *      If we had to do a directory split, the split directory blocks
 *      will be fully handled, placed on the lazywrite queue or written
 *      through.
 *
 *      Name Comparisons:
 *              When we compare name strings, we do the compare
 *              based upon the length of the string that we want,
 *              ignoring for the time being the length of the
 *              string in the directory.  If the names are identical,
 *              this is OK.  What we're worried about are three cases
 *              where the names aren't identical:
 *
 *              1) the names appear to be equal:
 *                 - the input string is shorter than the dir name.
 *                   since A comes before AA, this means that we've
 *                   overshot.  The "found name" handler will detect
 *                   this.
 *                 - the input string is longer, and we had lucky garbage.
 *                   This means that we undershot, and we keep looking
 *
 *              2) the input string appears greater than the dir string.
 *                 - this is OK, the input string is a superset of dirname
 *                   and therefore *is* greater
 *
 *              3) the input string appears less than the dir string
 *                 - this one is the problem, since the input string
 *                   is lexically greater, but compares less.
 *
 *      When LDE returns the directory block containing the entry or
 *      the location it should be (if missing) is in the cache, with the
 *      hold count incremented.
 *
 *      Note that a zero length name is taken as the "\0." entry.
 *
 *
 *      ENTRY   pdbTop = address of topmost directory block
 *              bAction = open action codes (OAC_*)
 *              fWrtThru = OPEN_WRITE_THROUGH set if to write through
 *              pbufTopDir = address of buffer hdr of topmost directory block
 *              pspName = pointer to Pascal string containing name
 *              EXTRA?   psd = address of SUBDIR struct, only required if
 *                                                              OAC_CF set
 *              SBDIR held.
 *
 *      RETURNS LDE_FOUND if entry found
 *              LDE_CREATED if entry created
 *              LDE_NOT_FOUND if not found
 *              LDE_CANT_SPLIT if create failed because out of disk space or
 *                             hard error
 *              LDE_READ_FAULT if error encountered
 *
 *                SBDIR is locked if LDE_CREATED
 *                *ppbufResult = address of buffer header for dirblk, HELD
 *                *ppdbResult = address of start of directory block
 *                *ppdeResult = address of entry
 *
 *              If LDE doesn't find or create the file, the returned
 *              *ppbuf, *ppdbResult, and *ppdeResult refer to the first
 *              found entry which is lexically greater than the desired
 *              entry.
 *
 *      BUGBUG - IMPORTANT BUG - if we have to block to lock the
 *      directory (at lde100?), when we get control, the directory
 *      may be mucked with.
 *
 *
 *      HISTORY
 *  @76193  23-Nov-1993 by D.Azzarito - Change holds for LOG support
 *          11-Jun-1993 by Doug Azzarito
 *              - Hold DirBlk bufnode during blocking operation  @58152
 *          15-May-1989 by John Rogers [JohnRo@Microsoft]
 *              - Changed names of rounding macros in <pbmacros.h>.
 *          27-Sep-1988 14:19:54 by Bill McJohn [t-billm]
 *                              brought up to date with 9/23/88 assembly code
 */

USHORT
LDE (pdbTop, bAction, fWrtThru, pbufTopDir, pspName,
        ppbufResult, ppdbResult, ppdeResult, fCmpType, pfrm)
PDIRBLK         pdbTop;         /* addr of topmost dir block */
BYTE            bAction;        /* action code (OAC_*) */
BOOL            fWrtThru;       /* boolean indicating whether to write thru */
PBUFNODE        pbufTopDir;     /* ptr to the bufnode of topmost dir block */
PPASCALSTRING   pspName;        /* ptr to Pascal string containing name */

PBUFNODE far    *ppbufResult;   /* ptr to dir blk buffer header */
PDIRBLK far     *ppdbResult;    /* ptr to dir block adr returned to caller */
PDIRENT far     *ppdeResult;    /* ptr to dir entry adr returned to caller */
BOOL            fCmpType;       /* boolean ==> type of dir name compare */
                                /* TRUE == use process code page    */
                                /* FALSE == use directory entry code page */
PFRAME          pfrm;
{
    INT         i;
    PCHAR       pcDirName;
    PDIRENT     pdeCandidate;   /*  ptr to next DIRENT to examine       */
    LDESTK      LDEstk;         /*  LDE's internal 'stack'              */
    UCHAR       cNameLen;       /*  Length of search name string        */
    USHORT      rc;

    MMPHPreLDE(); /* performance hook (3306) */

    ASSERT_DB (pdbTop);
    ASSERT_BUF (pbufTopDir);

    /*
     * Initialize
     */
    /*
     *  If the length of the incoming pascalstring file name is one,
     *  then it consists only of a length byte, i.e. it has a null
     *  file name.  Treat this as dot.
     *
     */
    if (pspName->c == 1)
        pspName = (PPASCALSTRING) pszDot;

    cNameLen = pspName -> c - (BYTE)1;

    /*
     * The code below fills the LDESTK structure from the arguments to LDE
     *
     */
    LDEstk.pdbCurrent = pdbTop;
    LDEstk.pbufCurrent = pbufTopDir;
    LDEstk.fbOAC = bAction;
    LDEstk.fWrtThru = fWrtThru;

    for (;;) {

        /* address of first dir entry record */
        pdeCandidate = (PDIRENT) & (pdbTop->bFirst);

        /*
         *      Search the block for the nearest record
         *
         *      pdeCandidate = address of directory entry we are examining
         *      pspName->b = address of name string
         *      pspName->c = string count (includes count byte)
         */

        for (pcDirName = & (pdeCandidate->bName[0]);
             ((i = (pdeCandidate->fFlags & DF_END) ? -1 :
                   NameUpCaseCmp (pspName->b, cNameLen,
                                  pcDirName, pdeCandidate->cchName,
                                  fCmpType ?
                                    &paCodePageEnt [pfrm->iCP] :
                                    &paCodePageEnt [pfrm->pvol->paiCodePage
                                                   [pdeCandidate->bCodePage]] )
                                                                      //#90495

              ) != 0) ||
             (cNameLen != pdeCandidate->cchName);
             pcDirName = &(pdeCandidate->bName[0])) {


             if (i == 0) {

        /*
         * Since the name we are looking for is shorter, we've
         * overshot.  Fall through to overshot code
         */
             } else if (i > 0) {

        /* not past it yet - or -
         * we appear to have overshot the spot where the name
         * would be (i.e., it's not there).  This may be
         * spurious if the target name was longer than the
         * compared name.  If we had compared more bytes than
         * are in the dir entry then we're really below, not
         * above, our spot.
         */
              pdeCandidate = NEXT_ENTRY (pdeCandidate);

              continue;
             }

             /*
              * We have overshot it ((i < 0) or
              * cNameLen < pdeCandidate->cchName)
              */
             if (pdeCandidate->fFlags & DF_BTP) {

               /*
                * We have a btree downpointer.  Get that guy and do
                * as we will.
                */
               LDEstk.pdbCurrent = RdBuf (BTP (pdeCandidate),
                                          BP_KEEP,
                                          ppbufResult,
                                          pfrm);

/* #if DIRBLKS != SPB * SECSIZE
 * #error LDE:  DIRBLK does not fill a cache block
 * #endif
 */

               if ( (*ppbufResult)->bBadMask != 0 ) {

                   /*  lde30: Hard error.  */
#ifdef DEBUG
                   dprintf ("LDE (lde30): got hard error\n");
#endif
                   IncrHoldsBUF( *ppbufResult );  // @76193

                   rc = LDE_READ_FAULT;
                   MMPHPostLDE(); /* performance hook (3386) */

                   return(LDE_READ_FAULT);
               }

               ASSERT_DB (LDEstk.pdbCurrent);
               ASSERT_BUF (*ppbufResult);

               LDEstk.pbufCurrent = *ppbufResult;
               pdeCandidate = (PDIRENT) &(LDEstk.pdbCurrent->bFirst);

#ifdef DEBUG
               /*
                * BUGBUG -- check parent pointer
                */
#endif

                } else {

                  /*
                   * (lde60)
                   * We overshot it; it is not here.  Create it or
                   * return LDE_NOT_FOUND
                   */
                  if (LDEstk.fbOAC & OAC_CF) {
#ifdef MINIFSD

                      rc = ERROR_NOT_SUPPORTED;
                      MMPHPostLDE(); /* performance hook (3386) */

                      return ERROR_NOT_SUPPORTED;
#else
                      PSUBDIR psbd;

                      /* Entry Missing.  Insert item in the leaf block
                       *
                       * The most common case of insert is when we're
                       * inserting into a leaf block and there is enough
                       * room.  (Do all of that work in-line instead of
                       * calling our helper subroutines, for optimal
                       * performance.)   The assy code does that,
                       * but we will call the helper subroutines for now.
                       *
                       * Before we can start our work, we have to obtain
                       * a lock on the directory.  NOTE that some callers
                       * (move) will have already locked the directory.
                       * If its locked when we were called then we know that
                       * it must be our thread that locked it, and we can
                       * just leave the lock set.
                       *
                       *  lde100:
                       */
                      if ((psbd = pfrm->psbd)->bFlags & SDF_LCK) {
                          goto lde110;
                      }

                      DecrHoldsSBD (psbd);

                      if ((psbd->cusHolds != 0) ||
                          ( (psbd->bFlags) &&
                            (psbd->bFlags != (SDF_PND | SDF_PSO)) ) ) {

                          LockDir (psbd,pfrm);
#ifdef DEBUG
                          SetLockSBD(psbd);
#endif
                          UnLockDir_ (psbd);
                          HoldDir (psbd,pfrm);

                          /*
                           *  Start the search over...
                           *  Go back to the top of the directory, reset
                           *  pdeCandidate to the first entry in the root
                           *  DIRBLK, and try again.
                           */
                          LDEstk.pdbCurrent =
                              LSDDB(&(psbd -> scpTopDirBlkHint),
                                   BP_KEEP, &LDEstk.pbufCurrent, pfrm);

                          if ( LDEstk.pdbCurrent == NULL ) {

                              /*  Hard error.  */
                              IncrHoldsBUF( LDEstk.pbufCurrent );  // @76193
                              *ppbufResult = LDEstk.pbufCurrent;

                              rc = LDE_READ_FAULT;
                              MMPHPostLDE(); /* performance hook (3386) */

                              return(LDE_READ_FAULT);
                          }

                          ASSERT_DB (LDEstk.pdbCurrent);

                          pdeCandidate = (PDIRENT)
                                         &((LDEstk.pdbCurrent)->bFirst);

                      } else {

                              /* Lock the subdir and create the entry. */
lde110:
                              SetLockSBD(psbd);


                              rc = LDECreate (pdeCandidate,
                                              pspName,
                                              &LDEstk,
                                              ppbufResult,
                                              ppdbResult,
                                              ppdeResult,
                                              pfrm);

                              MMPHPostLDE(); /* performance hook (3386) */

                              return (rc);

                      }
#endif /*** MINIFSD ***/
                    } else {

                        *ppbufResult = LDEstk.pbufCurrent;
                        IncrHoldsBUF (*ppbufResult);  // @76193
                        *ppdbResult = LDEstk.pdbCurrent;
                        *ppdeResult = pdeCandidate;

                        rc = LDE_NOT_FOUND;
                        MMPHPostLDE(); /* performance hook (3386) */

                        return LDE_NOT_FOUND;   /* Entry not found */
                    }
                }
        }

        *ppbufResult = LDEstk.pbufCurrent;
        IncrHoldsBUF (*ppbufResult);  // @76193
        *ppdbResult = LDEstk.pdbCurrent;
        *ppdeResult = pdeCandidate; /* propagate this up */

        rc = LDE_FOUND;
        MMPHPostLDE(); /* performance hook (3386) */

        return (LDE_FOUND);         /* found an existing item */
    }
}



#ifndef MINIFSD
/*
 ***    LDECreate - Create and insert a dir. entry into the directory
 *
 *      Entry Missing.  Insert item in the leaf block
 *       (corresponds to assembly code beginning at lde110--however,
 *      lock on subdir is set before call to LDECreate.)
 *
 *      The most common case of insert is when we're inserting
 *      into a leaf block and there is enough room.  Do all of
 *      that work in-line instead of calling our helper subroutines,
 *      for optimal performance.
 *
 *      Before we can start wour work, we have to obtain a lock
 *      on the directory.
 *
 *      pspName points to the up-cased name.  We must get the original
 *      mixed-name through the pointer in the frame.
 *
 *      ENTRY
 *              pdeBeyond = address of entry which is too high
 *              pspName = ptr to Pascal string containing name
 *              pldestk = frame pointer
 *
 *      EXIT    Returns LDE_FOUND if entry found
 *              Returns LDE_CREATED if entry created
 *                *ppbufResult = address of buffer header for dirblk
 *                *ppdbResult = address of start of directory block, HELD
 *                *ppdeResult = address of entry
 *              Returns LDE_NOT_FOUND if not found
 *              Returns LDE_CANT_SPLIT if create failed because out of disk
 *                            space or hard error
 *
 */

USHORT
LDECreate (pdeBeyond, pspName, pldestk, ppbufResult,
                      ppdbResult, ppdeResult, pfrm)
PDIRENT         pdeBeyond;      /* ptr to dir entry after insertion point */
PPASCALSTRING   pspName;        /* the name we wish to insert */
PLDESTK         pldestk;        /* frame pointer (local variables from LDE) */

PBUFNODE far    *ppbufResult;   /* ptr to dir blk buffer header */
PDIRBLK far     *ppdbResult;    /* ptr to dir block adr returned to caller */
PDIRENT far     *ppdeResult;    /* ptr to dir entry adr returned to caller */
PFRAME          pfrm;
{
        PDIRBLK pdbFirstHalf;
        PDIRBLK pdbSecondHalf;
        PDIRENT pdeNewEntry;
        PDIRENT pdeInsertPoint;

        {  /*  Scope of cNameLen  */

        UCHAR   cNameLen;       /*  length of name to insert  */
        PDIRBLK pdbToInsert;

        cNameLen = pspName->c - (BYTE)1;

        /* Block into which we will insert */
        pdbToInsert = pldestk->pdbCurrent;

        ASSERT_DB (pdbToInsert);

        /*
         * If there is room in this block, just copy the fields into the DIRENT
         */
        if ((pdeNewEntry = MkRoom ((USHORT)
                                   ROUND_TO_POW_OF_2 (cNameLen + DIRSIZL, 4),
                                   pdeBeyond,
                                   pdbToInsert)) != NULL) {

                pdeNewEntry->cchName = cNameLen;        /* set name length */

                /* now move the name */
                BYTE_COPY (pfrm->pbLastName, pdeNewEntry->bName, cNameLen);

                /* Set the codepage index in the DirEnt */
                {
                    UINT cCodePage = pfrm->pvol->cCodePage;
                    PBYTE paiCodePage = pfrm->pvol->paiCodePage;
                    UINT iCPVol;

                    for (iCPVol = 0; iCPVol < cCodePage; iCPVol++) {
                        if (paiCodePage [iCPVol] == pfrm->iCP) {
                            break;
                        }
                    }

                    pdeNewEntry->bCodePage = (BYTE) iCPVol;
                }

                /*
                 * zero the fields we do not know about
                 */
                ZERO_FIELDS (pdeNewEntry);

                *ppdeResult = pdeNewEntry;           /* return DIRENT value */
                *ppbufResult = pldestk->pbufCurrent; /* return BUFNODE value */
                (*ppbufResult)->bDirtMask = SPBBITS; /* dirty the DIRBLK */
                IncrHoldsBUF (*ppbufResult);           /* hold this guy  @76193 */
                *ppdbResult = pldestk->pdbCurrent;   /* return DIRBLK value */
                return LDE_CREATED;                  /* entry was created */
        }

        /*
         * Split the Leaf Block
         *
         * There was not enough room in the block, so we must split it,
         * insert into one of the halves, and insert a new pointer and key
         * into the parent block. (Should it be full, we must split it, and
         * so on up to the top DIRBLK.
         *
         *      We'll start calling helper routines which simplify our
         *      code, because this is an unusual situation and a few extra
         *      instructions won't matter.
         *
         * Before we proceed with the split, though, we've got to reserve
         * enough DIRBLKs for a worst case upwards propagation.
         */

        /*
         * Get SPDBuf.  While bit 0 of fSPDBufBusy is set, block on
         * pLDEWait.  Then set that bit, indicating that this thread
         * now has possession of the split buffer.  If we block, hold
         * the data buffer so we don't lose it.
         */

        while (fSPDBufBusy & 0x01) {
                IncrHoldsBUF (pldestk->pbufCurrent);  // @76193
#ifdef DEBUG
                dprintf (__FILE__": Blocking on pLDEWait\n");
#endif
                BlockMisc ( &pLDEWait, LOB_LDE,pfrm );
                DecrHoldsBUF (pldestk->pbufCurrent);  // @76193
        }

        fSPDBufBusy |= 0x01;

        IncrHoldsBUF(pldestk->pbufCurrent);   /* @58152  @76193 */

        if ( VerifyDB(pfrm) == FALSE ) {

          DecrHoldsBUF (pldestk->pbufCurrent); /* @58152  @76193 */

           /*  We need to split this directory, but we can't--
            *  there aren't enough available DIRBLKS.
            *
            *  Directory locked.
            *
            *  fSPDBufBusy (LDEFlag) claimed
            *
            *  lde950:
            */
           /* release SPDBuf and wake any waiters */
          fSPDBufBusy = 0;
          if (pLDEWait != NULL) {
              WakeupSMisc (&pLDEWait, LOB_LDE);
          }

          *ppbufResult = pldestk->pbufCurrent;
          IncrHoldsBUF (*ppbufResult);  // @76193

          UnLockDir();
          HoldDir( pfrm->psbd,pfrm );

          *ppdbResult = pldestk->pdbCurrent;

          return (LDE_CANT_SPLIT);
        }

  /* note - the following line assumes we never exit from the above block */
   DecrHoldsBUF(pldestk->pbufCurrent); /* @58152  @76193 */

        /*
         * Split the block and guess that we will insert into the second half.
         *
         * abBuf will hold the DIRENT which acts as a key to choose between
         * the halves
         */

        #ifdef BUFZAP
        IncrHoldsBUF (pldestk->pbufCurrent);  // @76193
        DoZap();
        DecrHoldsBUF(pldestk->pbufCurrent);  // @76193
        #endif

        IncrHoldsBUF (pldestk->pbufCurrent);  // @76193

        pdbToInsert = pdbSecondHalf =
        SplitDir (pdbFirstHalf = pldestk->pdbCurrent,
                  pldestk->pbufCurrent,
                  (PDIRENT)abBuf,
                  pldestk->fWrtThru,
                  pfrm);

        DecrHoldsBUF (pldestk->pbufCurrent);  // @76193

        /*
         * If the name we want to insert is less than the key value
         * which separates the two halves, we will insert the name
         * into the first half
         */
        /*
         * NOTE: SplitDir will never return an end entry, so we don't have to
         *       check for it.
         */
        if (NameUpCaseCmp (pspName->b, cNameLen,
                           &(((PDIRENT) abBuf)->bName[0]),
                           ((PDIRENT)abBuf)->cchName,
                           &paCodePageEnt [pfrm->pvol->paiCodePage
                                           [((PDIRENT) abBuf)->bCodePage]]
                          ) < 0) {
            pdbToInsert = pdbFirstHalf;     /* insert in first half */

            ASSERT_DB (pdbToInsert);
        }

        /*
         * Do a linear search through the block for the insertion point
         * (while pspName->b > pdeInsertPoint, move pdeInsertPoint forward)
         */
        pdeInsertPoint = (PDIRENT) &(pdbToInsert->bFirst);

        while (((pdeInsertPoint->fFlags & DF_END) == 0) &&
               (NameUpCaseCmp (pspName->b, cNameLen,
                               &(pdeInsertPoint->bName[0]),
                               pdeInsertPoint->cchName,
                               &paCodePageEnt [pfrm->pvol->paiCodePage
                                              [pdeInsertPoint->bCodePage]]
                             ) > 0)) {

            pdeInsertPoint = NEXT_ENTRY (pdeInsertPoint);
        }

        /*
         * Prepare to return the directory block into which we will insert
         * the name
         */
        pldestk->pdbRetVal = pdbToInsert;

        /*
         * Open a space in the DIRBLK for the entry - (if we cannot, something
         * is very wrong (the situation should be impossible), so die with an
         * error.)  Also, set return value
         */
        if ((pldestk->pdeRetVal =
            MkRoom (ROUND_TO_POW_OF_2 (cNameLen + DIRSIZL, 4),
                    pdeInsertPoint,
                    pdbToInsert)) == NULL) {

#ifdef DEBUG
                dprintf ("LDECreate: MkRoom failed\n");
#endif
                goto LDECreateHardError;
        }


        /* Fill in the new entry */
        pldestk->pdeRetVal->cchName = cNameLen; /* set name length */

        /* now move the name */
        BYTE_COPY (pfrm->pbLastName, pldestk->pdeRetVal->bName, cNameLen);

        /* Set the codepage index in the DirEnt */
        {
            UINT cCodePage = pfrm->pvol->cCodePage;
            PBYTE paiCodePage = pfrm->pvol->paiCodePage;
            UINT iCPVol;

            for (iCPVol = 0; iCPVol < cCodePage; iCPVol++) {
                if (paiCodePage [iCPVol] == pfrm->iCP) {
                    break;
                }
            }

            pldestk->pdeRetVal->bCodePage = (BYTE) iCPVol;
        }


        /*
         * zero the fields we do not know about
         */
        ZERO_FIELDS (pldestk->pdeRetVal);

        /*
         * Set return values
         */
        *ppdbResult = pdbToInsert;
        *ppbufResult = BH (pdbToInsert);

        IncrHoldsBUF(*ppbufResult);  // @76193

        *ppdeResult = pldestk->pdeRetVal;

        /*
         * So, how about writing pdbToInsert?
         */
        SetDBDirt (*ppbufResult, pldestk->fWrtThru, pfrm);
        } /* block for pdbToInsert, cNameLen  */


        /*
         *      Promote new branch record to parent block
         *
         *      We've split a directory block and now we have to promote
         *      the middle record into the parent block.  We'll loop back here
         *      if the parent in turn has to split, etc.
         *
         *      The splitter guy comes back with a pointer to the topmost
         *      directory that didn't get split
         *
         *      The downpointer in the middle record points to the upper half.
         *      We want to insert the middle guy before the record which has
         *      the sector # of the upper half as it's down pointer, and then
         *      change that downpointer to the lower half.
         *
         *      pdbFirstHalf = address of upper half
         *      pdbSecondHalf = address of lower half
         *      abBuf or pdeMiddle = address of buffer holding middle
         *      pldestk = frame pointer
         */

        {
        PDIRENT pdeMiddle;
        LSN     lsnLowerHalf;
        LSN     lsnUpperHalf;
        BOOL    fTmp;

        /*
         * pdeMiddle is the DIRENT value which serves as a key to separate the
         * two halves of the DIRBLK we split.  It must be promoted to
         * (inserted into) the parent DIRBLK.
         */
        pdeMiddle = (PDIRENT) abBuf;


        /* sector #s of lower half and upper half */
        lsnLowerHalf = pdbSecondHalf->lsnThisDir;
        lsnUpperHalf = pdbFirstHalf->lsnThisDir;

        /*
         * If we had split the top DIRBLK block, the first half block's
         * cChange field would be 1
         */
        fTmp = (BOOL) pdbFirstHalf->culChange;

        /* clear low bit (zero change count) */
        pdbFirstHalf->culChange &= -2;

        /*
         * If we split the top DIRBLK, we must add a level to the tree
         * (and generate a new top DIRBLK)
         */
        if (fTmp & 0x01) {

          /*  corresponds to lde300  */
          if (LDEAddLevel(pdbFirstHalf,
                       pdbSecondHalf,
                       pdeMiddle,
                       pldestk->fWrtThru,
                       &(pldestk->pbufCurrent),
                       &(pldestk->pdbCurrent),
                       pfrm) != NO_ERROR) {

              /* Encountered a hard error creating a new root. */
#ifdef DEBUG
                dprintf ("LDECreate: LDEAddLevel failed\n");
#endif
                goto LDECreateHardError;
          }
                /*
                 * The code below was LDECleanup (lde900)
                 */
                fSPDBufBusy = 0;                /* clear the reservation */

                if (pLDEWait != NULL) {
                    WakeupSMisc (&pLDEWait, LOB_LDE);
                }

                /*  We no longer need reserved DIRBLKS  */
                RelVerDB(pfrm);

                /*
                 * Unhold buffer we worked on and mark it dirty
                 */
                DecrHoldsBUF (pldestk->pbufCurrent);  // @76193
                SetDBDirt(pldestk->pbufCurrent, pldestk->fWrtThru, pfrm);
                return LDE_CREATED;
        }

        /*
         * Unhold the subblocks, as we do not need them anymore
         */
        DecrHoldsBUF (BH (pdbSecondHalf));  // @76193
        DecrHoldsBUF (BH (pdbFirstHalf));  // @76193

        /*
         * Read the parent block into pldestk->pdbCurrent and prepare
         * to insert the key DIRENT (pdeMiddle)
         */
/* #if DIRBLKS != SPB * SECSIZE
 * #error LDECreate:  DIRBLK does not fill cache block
 * #endif
 */
        pldestk->pdbCurrent = RdBuf (pdbFirstHalf->lsnParent, BP_KEEP,
                                     &(pldestk->pbufCurrent),pfrm);

        if (pldestk->pbufCurrent->bBadMask != 0) {

#ifdef DEBUG
            dprintf ("LDECreate: RdBuf returns buf w/bad sectors in it\n");
#endif
            goto LDECreateHardError;
        }

        ASSERT_DB (pldestk -> pdbCurrent);

        /*
         * Hold the buffer while we work (from 7/21 assembly version)
         */
        IncrHoldsBUF (pldestk->pbufCurrent);  // @76193

        /*
         * Find the insertion point for the middle DIRENT in the parent
         * block.  If it is not there, the directory must be corrupted.
         */
        if ((pdeInsertPoint = FindIP (lsnUpperHalf, pldestk->pdbCurrent)) ==
                NULL) {

#ifdef DEBUG
            dprintf ("LDECreate: FindIP failed\n");
#endif
            goto LDECreateHardError;
        }

        /*
         * If we can make room for the middle DIRENT, just insert it
         * and change the pointer of the DIRENT following it to point
         * to the second (lower) half DIRBLK
         */
        if ((pdeNewEntry = MkRoom ((USHORT)pdeMiddle->cchThisEntry,
                                   pdeInsertPoint,
                                   pldestk->pdbCurrent)) != NULL) {
          /*
           * Move in the middle DIRENT into the space we created
           * BYTE_COPY does not alter its arguments
           */
          BYTE_COPY ((PULONG)pdeMiddle,
                     (PULONG)pdeNewEntry,
                     pdeMiddle->cchThisEntry );

          /*
           * Now change the BTree down pointer of the following
           * record (the one before which we inserted the middle
           * DIRENT) to point the the block we created (the second
           * half DIRBLK).
           */
          BTP ((NEXT_ENTRY (pdeNewEntry))) = lsnLowerHalf;
          ASSERTBTP (NEXT_ENTRY (pdeNewEntry));

          /*
           * We are done - clean up and set return values
           * The code below was LDECleanup (lde900)
           */

          fSPDBufBusy = 0;                /* clear the reservation */

          if (pLDEWait != NULL) {
              WakeupSMisc (&pLDEWait, LOB_LDE);
          }

          /*  We no longer need reserved DIRBLKS  */
          RelVerDB(pfrm);

          /*
           * Unhold buffer we worked on and mark it dirty
           */

          DecrHoldsBUF (pldestk->pbufCurrent);  // @76193

          SetDBDirt (pldestk->pbufCurrent,
                     pldestk->fWrtThru,pfrm);

          return LDE_CREATED;
        }

        /*
         * There is not enough room for the middle DIRENT in the parent
         * DIRBLK, so we split the parent (getting a new middle DIRENT
         * separating the two halves), insert the old middle DIRENT
         * into one half, and then attempt to insert the new middle
         * DIRENT into the new parent DIRBLK.  The process can continue
         * all the way to the top DIRBLK, where we add a new level if we
         * need to split (see LDEAddLevel as used above)
         * All this is done by insert.
         *
         * Corresponds to lde200.
         */

        if (insert(pldestk->pdbCurrent,
                   pldestk->pbufCurrent,
                   pdeMiddle,
                   lsnLowerHalf,pfrm) != NO_ERROR ) {

#ifdef DEBUG
            dprintf ("LDECreate: insert failed\n");
#endif
            goto LDECreateHardError;
        }

        } /* scope of fTmp, lsnLowerHalf, lsnUpperHalf, pdeMiddle */

        /*
         * The code below was LDECleanup (lde900)
         */
        fSPDBufBusy = 0;                /* clear the reservation */

        if (pLDEWait != NULL) {
            WakeupSMisc (&pLDEWait, LOB_LDE);
        }

        /*  Release our VerifyDB reservation and our work buffer,
         *  and mark the DIRBLK we've manipulated as dirty.
         *
         */
        RelVerDB(pfrm);

        DecrHoldsBUF (pldestk->pbufCurrent);  // @76193

        SetDBDirt (pldestk->pbufCurrent,
                   pldestk->fWrtThru,pfrm);

        return LDE_CREATED;


LDECreateHardError:

        /*
         *  Code from lde970: and lde980:
         *
         *  We got a hard error splitting this directory or
         *  detected structural inconsistancy(?).
         *
         *  We're going to mark it corrupted.
         */
#ifdef DEBUG
        dprintf ("LDECreate: hard error\n");
#endif

        fSPDBufBusy = 0;

        if (pLDEWait != NULL) {
            WakeupSMisc (&pLDEWait, LOB_LDE);
        }

        RelVerDB(pfrm);
        CorruptDir(pfrm);

        /* BUGBUG 21-Mar-1989 MarkH
         *
         * PIA 386 code has another call to RelVerDB at this point
         */

        /*  lde950: */
        *ppbufResult = pldestk->pbufCurrent;
        IncrHoldsBUF (*ppbufResult);  // @76193

        UnLockDir();
        HoldDir( pfrm->psbd,pfrm );

        *ppdbResult = pldestk->pdbCurrent;
        return (LDE_CANT_SPLIT);

}


/*
 ***    LDEAddLevel - Splits the top dir. block and adds a level to the B Tree.
 *
 *      Add a new level to the tree, at the top, and point the FNODE to
 *      it.
 *
 *      We've split all of the way up to the top most block, so we'll
 *      add a new level to the tree, at the top, by creating a new
 *      top level block with just the two down pointers and the
 *      middle record.  We'll adjust the fnode to point to this
 *      block.
 *
 *      Note that both `child' DIRBLKs have lsnParent pointing to the fnode,
 *      before we fix this we learn the FNODE sector #.
 *
 *      pdbUpperHalf = address of upper/first half DIRBLK, block held
 *      pdbLowerHalf = address of lower/last half DIRBLK, block held
 *      pdeToPromote = address of record to promote.
 *
 *      EXIT    returns NO_ERROR if successful
 *                *ppbufResult = address of buffer header for dirblk
 *                *ppdbResult = address of start of directory block, HELD
 *                               (NOT marked as dirty)
 *              Returns LDE_READ_FAULT if error encountered
 *
 * @75229 Make this a FAR call
 */

USHORT far
LDEAddLevel (pdbUpperHalf, pdbLowerHalf, pdeToPromote, fWrtThru,
             ppbufNewTop, ppdbNewTop, pfrm)
PDIRBLK         pdbUpperHalf;
PDIRBLK         pdbLowerHalf;
PDIRENT         pdeToPromote;
BOOL            fWrtThru;       /*  write through flag  */

PBUFNODE far    *ppbufNewTop;   /* ptr to dir blk buffer header */
PDIRBLK far     *ppdbNewTop;    /* ptr to dir block adr returned to caller */
PFRAME          pfrm;
{
        LSN     lsnTemp;
        LSN     lsnFirstFound;
        PDIRENT pdeNewEnd;

        ASSERT_DB (pdbLowerHalf);

        /*
         * Get a new DIRBLK.  The first sector will be lsnFirstFound.
         * Note that we are guaranteed to get one, although it may
         * have to come from the emergency store.
         */
        AllocDB (pdbUpperHalf->lsnParent, &lsnFirstFound, pfrm);
                                                   //#85759
        if (lsnFirstFound == LSN_BOGUS) {
          return( LDE_READ_FAULT );
        }

        /*
         * Allocate a new DIRBLK and put it in *ppdbNewTop
         */
        {

        /*
         * Start a new block that defines pdb.  This is a stack win because
         * the block ends before the tail end of the function at which
         * point a new block is started that defines a new stack var.
         */
        PDIRBLK pdb;
#ifdef DEBUG_DIR
        pdb = *ppdbNewTop = RdBuf(lsnFirstFound, BP_KEEP, ppbufNewTop, pfrm);

        if (pdb->sig == DBSIGVAL) {
            dprintf (__FILE__": New DirBlk (lsn = %lx) already has signature\n",
                     lsnFirstFound);
            Int3 ();
        }

        if (pdb->sig == FNSIGVAL) {
            dprintf (__FILE__": New DirBlk (lsn = %x) is an FNode\n",
                     lsnFirstFound);
            Int3 ();
        }

        {
            PDIRBLK pdbTemp;

            pdbTemp = (PDIRBLK) ((PBYTE) pdb + 512);
            if (pdbTemp->sig == FNSIGVAL) {
                dprintf (__FILE__": New DirBlk contains an FNode (lsn = %x)\n",
                         lsnFirstFound+1);
                Int3 ();
            }
            pdbTemp = (PDIRBLK) ((PBYTE) pdbTemp + 512);
            if (pdbTemp->sig == FNSIGVAL) {
                dprintf (__FILE__": New DirBlk contains an FNode (lsn = %x)\n",
                         lsnFirstFound+2);
                Int3 ();
            }

            pdbTemp = (PDIRBLK) ((PBYTE) pdbTemp + 512);
            if (pdbTemp->sig == FNSIGVAL) {
                dprintf (__FILE__": New DirBlk contains an FNode (lsn = %x)\n",
                         lsnFirstFound+3);
                Int3 ();
            }
        }
#else
        pdb = *ppdbNewTop = GetInBuf (lsnFirstFound, DIRBLKS / SECSIZE,
                                      BP_KEEP, ppbufNewTop, pfrm);

        if (pdb == NULL) {
          return( LDE_READ_FAULT );
        }

        if ( (*ppbufNewTop)->bBadMask != 0 ) {

#ifdef DEBUG
            dprintf ("LDEAddLevel: got read fault\n");
#endif
            CorruptDir(pfrm);
            return( LDE_READ_FAULT );
        }

#endif

        /*
         * Hold the new top block until SetDirt
         */
        IncrHoldsBUF (*ppbufNewTop);  // @76193

        /*
         * Set top DIRBLK hint in SUBDIR struct to point to the new DIRBLK
         */
        pfrm->psbd->scpTopDirBlkHint.lsn =
                ( (*ppbufNewTop)->lsnSec & ~SECMASK ) | lsnFirstFound;
        pfrm->psbd->scpTopDirBlkHint.pbufHint = *ppbufNewTop;

        /*
         * Set the new DIRBLK's signature to indicate it is a DIRBLK
         */
        pdb->sig = DBSIGVAL;

        /*
         * The first free byte in the new top DIRBLK will be after the DIRENT
         * we are inserting (DIRSIZP + pdeToPromote->cchThisEntry + 1
         * which is at the first DIRENT location in the DIRBLK
         * &(pldestk->pdbCurrent->bFirst) - pldestk->pdbCurrent
         */
        pdb->offulFirstFree = pdeToPromote->cchThisEntry + 1 +
                                        DIRSIZP +
                                        ((PBYTE) &(pdb->bFirst) -
                                        (PBYTE) pdb);

        /*
         * Set change count to one to indicate that this is the top DIRBLK
         * The assembly code uses the leftover first free byte value as
         * a starting 'garbage value'
         */
        pdb->culChange = 1;

        /*
         * Store the lsn of the FNODE
         */
        pdb->lsnParent = pdbUpperHalf->lsnParent;

        /*
         * Set the top DIRBLK's LSN
         */
        pdb->lsnThisDir = lsnFirstFound;

        /*
         * Copy in the DIRENT which will act as key to the DIRBLKs we
         * split from the old top DIRBLK
         */
        /*  BYTE_COPY does not change its arguments  */
        BYTE_COPY (((PULONG) pdeToPromote),
                    ((PULONG) &(pdb->bFirst)),
                    (pdeToPromote->cchThisEntry) );


        /*
         * Create the end DIRENT after the one we just copied in.
         */

        pdeNewEnd = NEXT_ENTRY (((PDIRENT) &(pdb->bFirst)));
        }

        /*
         *  Set up the new end marker.  Its size is one plus the size of
         *  a DIRENT with BTree pointer;  set flags to show that it is
         *  end marker and has BTree down pointer.  It has the lexically
         *  greatest name of length one.
         *
         */
        pdeNewEnd->cchThisEntry = DIRSIZP + 1 * sizeof (CHAR);
        pdeNewEnd->fFlags = DF_BTP | DF_END;
        pdeNewEnd->cchName = 1;
        pdeNewEnd->bName[0] = CH_LASTNAME;
        pdeNewEnd->bCodePage = 0;

        /*
         * Set the two split halves to point to the new top DIRBLK
         * Set the parent pointers of the two split halves to point
         * at the new root DIRBLK, release their holds, and set them
         * dirty (with write-through forced).
         */

        /*  The first half:  */
        pdbUpperHalf->lsnParent = lsnFirstFound;
        DecrHoldsBUF (BH (pdbUpperHalf));  // @76193

        SetDirt((PBYTE) pdbUpperHalf, BH (pdbUpperHalf), fWrtThru, pfrm);

        /* save the old top DIRBLK's parent pointer */
        lsnTemp = pdbLowerHalf->lsnParent;

        /* The second half:  */
        pdbLowerHalf->lsnParent = lsnFirstFound;

        /* set sector # of END record's descendent */
        /* BUGBUG -- where do we set BTP for first entry???  */
        BTP (pdeNewEnd) = pdbLowerHalf->lsnThisDir;
        ASSERTBTP (pdeNewEnd);

        DecrHoldsBUF (BH (pdbLowerHalf));  // @76193
        SetDirt ((PBYTE) pdbLowerHalf, BH (pdbLowerHalf), fWrtThru, pfrm);

        /*
         * Read the root FNODE, change it to point to the new
         * root DIRBLK, and mark it as dirty, with write-through forced.
         *
         * NOTE:  if FNODES were suppressed for directories (ifndef FULLNODE)
         * we'd need to do some fancier footwork.
         */
        {
        PBUFNODE        pbuf;
        PFNODE          pfn;

//#127671 changed BP_NOOPINION to BP_KEEP
        pfn = RdBuf(lsnTemp, BP_KEEP, &pbuf, pfrm);

/* #if DIRBLKS != SPB * SECSIZE
 * #error LDEAddLevel:  DIRBLK does not fill cache block
 * #endif
 */

        if ( pbuf->bBadMask != 0 ) {

#ifdef DEBUG
            dprintf ("LDEAddLevel: got read fault\n");
#endif
            CorruptDir(pfrm);
            return( LDE_READ_FAULT );
        }

//#114986
        if (pbuf->fFlag & BFL_LZREAD) {
          if (LazyRead (pbuf, pfrm))
            return( LDE_READ_FAULT );
        }

        ASSERT_FN (pfn);
        pfn->fst.a.aall[0].lsnPhys = lsnFirstFound;
        SetDirt ((PBYTE) pfn, pbuf, fWrtThru, pfrm);
        }

        return( NO_ERROR );
}
#endif /*** MINIFSD ***/
