/*static char *SCCSID = "@(#)fix.c      6.4 92/02/19";*/
/*static char *SCCSID = "@(#)fix.c      6.4 92/02/19";*/
/***    FIX.C - Routines to fix minor file system problems
 *
 *      CHKDSK
 *      Gregory A. Jones
 *      Copyright 1988 Microsoft Corporation
 *
 *      Modification history:
 *      G.A. Jones      06/29/88    Derived from CHECK.C and RECOVER.C.
 *      P.A. Williams   05/22/89    B783383-in chk_sort_btree, we add a DIRENT
 *                                  to the newly contructed tree only if it
 *                                  has a valid name.
 *      P.A. Williams   07/12/89    Don't use PREMAPPED for checking name in
 *                                  chk_sort_btree. Also add memset to zero
 *                                  end DIRENT entry in chk_sort_directory
 *
 *      69658  06/15/93  rjp  Ported OS/2 1.3 fix from defect 5466:
 *                            Memory reduction. Reduce chk_disk_map and
 *                            chk_db_usemap from 8 bits per sector to 2 bits
 *                            per sector.
 * @d01 73790   93SEP03   GY        <Support V4FORMAT.  GHASSAN@AUSVM1>
 */

#include "ldefs.h"
#include "ltypes.h"
#include "globals.h"
#include <pr_chk.h>


/***    chk_no_writing - display reassuring message when an error is found
 *
 *      This function is called by each "fixing" routine.  It checks to
 *      see if command line parameters authorizing correction were given;
 *      if so, a zero value is returned.  Otherwise, the message
 *      which tells the user that the disk will not be changed is
 *      displayed, and a non-zero value is returned.  The global variable
 *      chk_error_found is set non-zero, so that the reassurance will only
 *      be printed on the first error.
 *
 *      The return value is FALSE if the disk can be changed so that
 *      the expression "if (chk_no_writing ()) don't write" makes sense.
 *
 *      If a non-zero first parameter is given, that message is displayed
 *      after the reassurance is given, in the style of the FAT CHKDSK.
 *
 *      The second parameter is a pointer to a pointer to a substitution
 *      string for computmsg to insert into the message.  It is not
 *      possible to substitute more than one string using chk_no_writing.
 *
 *      chk_no_writing (msg, varptr)
 *
 *      ENTRY           msg    - ID of informational message to be displayed
 *                      varptr - ptr to ptr to substitution string for msg
 *
 *      EXIT            Returns zero if the disk can be changed
 *
 *      CALLS           computmsg
 *
 *      WARNINGS        None
 *
 *      EFFECTS         Sets global variable chk_error_found to TRUE
 */
USHORT chk_no_writing (msg, varptr)
  USHORT msg;
  UCHAR **varptr;
{
  if (!chk_error_found) {               /* this is the first error */
#ifdef  V4FORMAT
    if (!chk_delete_inconsistency)      /* can we change the disk? */
      CHK_OUT_MSG( SYSTEM_MSG, CHK_NO_WRITING_STR, NULL);  /* no, reassure the user we won't */
    else
      chk_repair_disk++;                /* disk is being repaired */
#else
    if (!chk_delete_inconsistency)      /* can we change the disk? */
      CHK_OUT_MSG( SYSTEM_MSG, CHK_NO_WRITING_STR, NULL);  /* no, reassure the user we won't */
#endif
    chk_error_found = TRUE;             /* don't display msg on next error */
  }

  if (msg)
    CHK_COMPUTMSG( SYSTEM_MSG, varptr, (varptr != NULL) ? 1 : 0, msg, msgfilename, STDOUT_CODE,
               NO_RESPONSE,                     /* don't wait if not debugging */
               NULL, 0);   /* display informational message */

  return (!chk_delete_inconsistency);   /* return zero if fixes allowed */
}

/***    chk_fix_ccnt - patch an incorrect culChange value in a DIRBLK
 *
 *      This function is called to spot-fix the culChange field of a
 *      directory block.  It is passed a memory image of the DIRBLK
 *      and the correct value for the bottom bit of culChange.  The
 *      memory image will always be updated;  if command line parameters
 *      allow, the DIRBLK will be written back to the disk.
 *
 *      chk_fix_ccnt (mem, bit)
 *
 *      ENTRY           mem - memory image of the DIRBLK to be fixed
 *                      bit - correct value of culChange, bit 0
 *
 *      EXIT            No return value
 *
 *      CALLS           chk_no_writing
 *                      write_scratch
 *
 *      WARNINGS        Incorrect culChange values can cause major problems
 *                      in the filesystem's find/open/create/delete code.
 *
 *      EFFECTS         May update disk
 */
void chk_fix_ccnt (mem, bit)
  union blk *mem;
  USHORT bit;
{
#ifdef TRACE
  fprintf (stderr, "chk_fix_ccnt ()\n");
  fflush (stderr);
#endif

  if (bit)
    mem->d.culChange |= 1L;
  else
    mem->d.culChange &= ~1L;
  if (!chk_no_writing (CHK_FIX_CCNT_STR, NULL))
    write_scratch (mem->d.lsnThisDir, mem, SECTORS_PER_DIRBLK);
}

/***    chk_fix_dirflag - patch an incorrect DIR_FLAG value in a DIRENT
 *
 *      This function is called to spot-fix the DIR_FLAG field of a
 *      directory entry.  It is passed a memory image of the DIRBLK
 *      and a pointer to the entry that needs fixing.  If the name in
 *      the entry is "\001\001", DIR_FLAG should contain the DF_SPEC
 *      bit;  otherwise, the bit should be clear.  The memory image of
 *      the DIRBLK will always be updated;  if command line parameters
 *      allow, the DIRBLK will be written back to the disk.
 *
 *      chk_fix_dirflag (mem, entry)
 *
 *      ENTRY           mem   - memory image of the DIRBLK to be fixed
 *                      entry - pointer to the entry to be fixed
 *
 *      EXIT            No return value
 *
 *      CALLS           chk_no_writing
 *                      write_scratch
 *
 *      WARNINGS        Incorrect DIR_FLAG values (for DF_SPEC) can cause
 *                      strange results for findfirst/findnext operations.
 *
 *      EFFECTS         May update disk
 */
void chk_fix_dirflag (mem, entry)
  union blk *mem;
  union dp entry;
{
#ifdef TRACE
  fprintf (stderr, "chk_fix_dirflag ()\n");
  fflush (stderr);
#endif

/*
 * If the entry is the ".." entry, set only the SPECIAL and DIRECTORY bits,
 * and leave the ACL bits alone.  Otherwise, mask out all illegal bits.
 */

  if (!memcmp (entry.d->bName, "\001\001", 2)) {
    entry.d->fFlags |= DF_SPEC;
    entry.d->fFlags &= (DF_ACL | DF_XACL | DF_SPEC);

    entry.d->fAttr  = ATTR_DIRECTORY;
  }
  else {
    entry.d->fFlags &= LEGAL_FLAG_BITS;
    entry.d->fAttr  &= LEGAL_ATTR_BITS;
  }

  if (!chk_no_writing (CHK_FIX_DIRFLAG_STR, NULL))
    write_scratch (mem->d.lsnThisDir, mem, SECTORS_PER_DIRBLK);
}


/***    chk_fix_new_name_bit - patch an incorrect DIR_FLAG value in a DIRENT
 *
 *      This function is called to set or clear the NEW_NAME bit
 *      in a directory entry's flags.  The memory image of
 *      the DIRBLK will always be updated;  if command line parameters
 *      allow, the DIRBLK will be written back to the disk.
 *
 *      chk_fix_new_name_bit (mem, entry, fState)
 *
 *      ENTRY           mem   - memory image of the DIRBLK to be fixed
 *                      entry - pointer to the entry to be fixed
 *                      fState - TRUE iff the flag should be set
 *
 *      EXIT            No return value
 *
 *      CALLS           chk_no_writing
 *                      write_scratch
 *
 *      WARNINGS        Incorrect NEW_NAME flag values can cause
 *                      strange results for findfirst/findnext operations.
 *
 *      EFFECTS         May update disk
 */
void chk_fix_new_name_bit (mem, entry, fState)
  union blk *mem;
  union dp entry;
  BOOL fState;
{
#ifdef TRACE
  fprintf (stderr, "chk_fix_name_bit ()\n");
  fflush (stderr);
#endif

  if( fState )
      entry.d->fAttr |= ATTR_NEWNAME;
  else
      entry.d->fAttr &= ~ATTR_NEWNAME;


  if (!chk_no_writing (CHK_FIX_DIRFLAG_STR, NULL))
    write_scratch (mem->d.lsnThisDir, mem, SECTORS_PER_DIRBLK);
}

/***    chk_fix_dir_codepage - patch a DIRENT's codepage field
 *
 *      This function is called to change the value of a
 *      directory entry's codepage field.  The memory image of
 *      the DIRBLK will always be updated;  if command line
 *      parameters allow, the DIRBLK will be written back to
 *      the disk.
 *
 *      chk_fix_dir_codepage (mem, entry, value)
 *
 *      ENTRY           mem   - memory image of the DIRBLK to be fixed
 *                      entry - pointer to the entry to be fixed
 *                      value - new value
 *
 *      EXIT            No return value
 *
 *      CALLS           chk_no_writing
 *                      write_scratch
 *
 *      EFFECTS         May update disk
 */
void chk_fix_dir_codepage (mem, entry, value)
  union blk *mem;
  union dp entry;
  UCHAR value;
{
#ifdef TRACE
  fprintf (stderr, "chk_fix_dir_codepage ()\n");
  fflush (stderr);
#endif


  entry.d->bCodePage = value;

  if (!chk_no_writing (CHK_FIX_DIRFLAG_STR, NULL))
    write_scratch (mem->d.lsnThisDir, mem, SECTORS_PER_DIRBLK);
}

/***    chk_fix_endrec - build a new end record for a DIRBLK
 *
 *      This function is called by validate_structure when a directory
 *      entry with conflicting length entries is found.  This includes
 *      a cchThisEntry which overflows the directory block or is less than
 *      the minimum size of a DIRENT, or if cchName is inconsistent
 *      with cchThisEntry (too large or too small).  Conflicting numbers
 *      like these will break the file creation and deletion code, as
 *      well as the simplest iterative loops in CHKDSK;  thus, they
 *      cannot be tolerated.  The solution is to force an end record
 *      at the conflict point.
 *
 *      At the entry indicated, a new end record will be installed.
 *      The offulFirstFree field of the DIRBLK is also fixed.
 *
 *      The memory image will always be updated;  if command line
 *      parameters allow, the DIRBLK will be written back to the disk.
 *
 *      chk_fix_endrec (mem, entry)
 *
 *      ENTRY           mem   - memory image of the DIRBLK to be fixed
 *                      entry - point to install new end record
 *
 *      EXIT            No return value
 *
 *      CALLS           chk_no_writing
 *                      write_scratch
 *
 *      EFFECTS         May update disk
 */
void chk_fix_endrec (mem, entry)
  union blk *mem;
  union dp entry;
{
#ifdef TRACE
  fprintf (stderr, "chk_fix_endrec ()\n");
  fflush (stderr);
#endif

  memset (entry.p, '\0', sizeof (DIRENT));
  entry.d->cchThisEntry = sizeof (DIRENT);
  entry.d->fFlags = DF_END;
  entry.d->fAttr  = 0;
  entry.d->cchName = 1;
  entry.d->bName[0] = 0xff;

  mem->d.offulFirstFree = (entry.p - (PUCHAR)mem) + sizeof (DIRENT);

  if (!chk_no_writing (CHK_FIX_ENDREC_STR, NULL))
    write_scratch (mem->d.lsnThisDir, mem, SECTORS_PER_DIRBLK);
}

#if 0
BUGBUG - remove proto
/***    chk_fix_size - patch an incorrect cchFSize value in a DIRENT
 *
 *      This function is called to spot-fix the cchFSize field of a
 *      directory entry.  It is passed a memory image of the DIRBLK,
 *      the entry to be updated, and the correct file size.  The memory
 *      image will always be updated;  if command line parameters allow,
 *      the DIRBLK will be written back to the disk.
 *
 *      chk_fix_size (mem, entry, size)
 *
 *      ENTRY           mem   - memory image of the DIRBLK to be fixed
 *                      entry - pointer to the entry to be fixed
 *                      size  - correct file size
 *
 *      EXIT            No return value
 *
 *      CALLS           chk_no_writing
 *                      write_scratch
 *
 *      WARNINGS        Incorrect cchFSize may confuse the file system
 *
 *      EFFECTS         May update disk
 */
void chk_fix_size (mem, entry, size)
  union blk *mem;
 PDIRENT entry;
  ULONG size;
{
  USHORT len;

#ifdef TRACE
  fprintf (stderr, "chk_fix_size ()\n");
  fflush (stderr);
#endif

  strcpy (scratchbuf, chk_curpath);
  len = strlen (scratchbuf);
  memcpy (scratchbuf + len, entry->bName, entry->cchName);
  scratchbuf [len + entry->cchName] = '\0';
  entry->cchFSize = size;
  if (!chk_no_writing (CHK_WRONG_SIZE_STR, &scratchptr))
    write_scratch (mem->d.lsnThisDir, mem, SECTORS_PER_DIRBLK);
}
#endif

/***    chk_fix_lof - patch an incorrect LOF value in a leaf or node record
 *
 *      This function is called when the LOF (logical offset) field of
 *      an allocation leaf or node entry is incorrect.  It is passed
 *      a memory image of the block containing the incorrect leaf or
 *      node, a pointer to the incorrect leaf or node itself, and the
 *      correct logical offset for that record. The memory image will
 *      always be updated;  if command line parameters allow, the structure
 *      (FNODE or ALSEC) will be written back to the disk.
 *
 *      chk_fix_lof (sec, mem, rec, lof)
 *
 *      ENTRY           sec - where the structure is on disk
 *                      mem - memory image of the structure to be fixed
 *                      rec - pointer to the record to be fixed
 *                      lof - correct logical offset
 *
 *      EXIT            No return value
 *
 *      CALLS           chk_no_writing
 *                      write_scratch
 *
 *      WARNINGS        Incorrect LOFs may confuse the file system
 *
 *      EFFECTS         May update disk
 */
void chk_fix_lof (sec, mem, rec, lof, flag)                     // CP13 B730753 - BJH OS/2 Change Team
  ULONG sec;
  union blk *mem;
  VOID *rec;
  ULONG lof;
  USHORT flag;                                                  // CP13 B730753 - BJH OS/2 Change Team
{
  LONG loferror;                                                // CP13 B730753 - BJH OS/2 Change Team
  PALNODE palnode;                                              // CP13 B730753 - BJH OS/2 Change Team
  PALLEAF palleaf;                                              // CP13 B730753 - BJH OS/2 Change Team

#ifdef TRACE
  fprintf (stderr, "chk_fix_lof ()\n");
  fflush (stderr);
#endif

  if ( flag & ABF_NODE )        // rec points to ALNODE record          // CP13 B730753 - BJH OS/2 Change Team
   {                                                                    // CP13 B730753 - BJH OS/2 Change Team
    palnode = (PALNODE)rec;                                             // CP13 B730753 - BJH OS/2 Change Team
    palnode->lsnLog = lof;      // correct lof in ALNODE                // CP13 B730753 - BJH OS/2 Change Team
   }                                                                    // CP13 B730753 - BJH OS/2 Change Team
  else                          // rec points to ALLEAF record          // CP13 B730753 - BJH OS/2 Change Team
   {                                                                    // CP13 B730753 - BJH OS/2 Change Team
    palleaf = (PALLEAF)rec;                                             // CP13 B730753 - BJH OS/2 Change Team
    loferror = lof - palleaf->lsnLog;                                   // CP13 B730753 - BJH OS/2 Change Team
                                                                        // CP13 B730753 - BJH OS/2 Change Team
    palleaf->lsnLog = lof;      // correct logical sector number        // CP13 B730753 - BJH OS/2 Change Team
                                                                        // CP13 B730753 - BJH OS/2 Change Team
    if ( ( loferror > 0 ) &&    // if physical sectors are hidden       // CP13 B730753 - BJH OS/2 Change Team
         ( loferror < palleaf->csecRun ) ) // and can be removed         // CP13 B730753 - BJH OS/2 Change Team
     {                                                                  // CP13 B730753 - BJH OS/2 Change Team
#ifdef TRACE
      fprintf (stderr, "chk_fix_lof (): corrected hidden sector problem\n");
      fflush (stderr);
#endif
      // move start of extent past hidden sectors                       // CP13 B730753 - BJH OS/2 Change Team
      palleaf->lsnPhys += loferror;                                      // CP13 B730753 - BJH OS/2 Change Team
      // remove hidden sectors from count                               // CP13 B730753 - BJH OS/2 Change Team
      palleaf->csecRun -= loferror;                                      // CP13 B730753 - BJH OS/2 Change Team
     }                                                                  // CP13 B730753 - BJH OS/2 Change Team
   }                                                                    // CP13 B730753 - BJH OS/2 Change Team

  if (!chk_no_writing (CHK_FIX_LOF_STR, NULL))
    write_scratch (sec, mem, (mem->f.sig == FNSIGVAL) ?
                   SECTORS_PER_FNODE : SECTORS_PER_AB);
}

/***    chk_fix_frep - patch an incorrect offulFirstFree pointer in a DIRBLK
 *
 *      This function is called to spot-fix the offulFirstFree field of a
 *      directory block.  It is passed a memory image of the DIRBLK
 *      and the correct offulFirstFree value.   The memory image will always
 *      be updated;  if command line parameters allow, the DIRBLK
 *      will be written back to the disk.
 *
 *      chk_fix_frep (mem, frep)
 *
 *      ENTRY           mem  - memory image of the DIRBLK to be fixed
 *                      frep - correct offulFirstFree value
 *
 *      EXIT            No return value
 *
 *      CALLS           chk_no_writing
 *                      write_scratch
 *
 *      WARNINGS        Incorrect offulFirstFree values can cause major problems
 *                      (such as GP faults) in creation/deletion code.
 *
 *      EFFECTS         May update disk
 */
void chk_fix_frep (mem, frep)
  union blk *mem;
  USHORT frep;
{
#ifdef TRACE
  fprintf (stderr, "chk_fix_frep ()\n");
  fflush (stderr);
#endif

  mem->d.offulFirstFree = frep;
  if (!chk_no_writing (CHK_FIX_FREP_STR, NULL))
    write_scratch (mem->d.lsnThisDir, mem, SECTORS_PER_DIRBLK);
}

/***    chk_fix_parent - patch an incorrect parent pointer in a structure
 *
 *      This function is called to spot-fix a parent pointer which is
 *      incorrect.  It is passed the sector number where the structure
 *      was found, a memory image of the structure, and the correct
 *      parent pointer.  The memory image will always be updated;  if
 *      command line parameters allow, the structure will be written
 *      back to the disk.
 *
 *      chk_fix_parent (lsn, mem, parent)
 *
 *      ENTRY           lsn    - where the structure is on disk
 *                      mem    - memory image of the structure
 *                      parent - what the parent pointer should be
 *
 *      EXIT            No return value
 *
 *      CALLS           chk_no_writing
 *                      write_scratch
 *
 *      EFFECTS         May update disk
 */
void chk_fix_parent (lsn, mem, parent)
  ULONG lsn;
  union blk *mem;
  ULONG parent;
{
#ifdef TRACE
  fprintf (stderr, "chk_fix_parent ()\n");
  fflush (stderr);
#endif

  if (mem->d.sig == DBSIGVAL) {
    mem->d.lsnParent = parent;
    if (!chk_no_writing (CHK_FIX_PARENT_STR, NULL))
      write_scratch (lsn, mem, SECTORS_PER_DIRBLK);
  }

  else if (mem->d.sig == FNSIGVAL) {
    mem->f.lsnContDir = parent;
    if (!chk_no_writing (CHK_FIX_PARENT_STR, NULL))
      write_scratch (lsn, mem, SECTORS_PER_FNODE);
  }

  else if (mem->d.sig == ABSIGVAL) {
    mem->a.lsnRent = parent;
    if (!chk_no_writing (CHK_FIX_PARENT_STR, NULL))
      write_scratch (lsn, mem, SECTORS_PER_AB);
  }
}

/***    chk_fix_current - patch an incorrect self-pointer in a DIRBLK or ALSEC
 *
 *      This function is called to spot-fix a pointer which is supposed
 *      to point to the DIRBLK or allocation block which contains it,
 *      but is incorrect.  It is passed the sector number where the block
 *      belongs (which is also the correct pointer value), and a memory
 *      image of the block.  The memory image will always be updated;
 *      if command line parameters allow, the block will be written
 *      back to the disk.
 *
 *      chk_fix_current (lsn, mem)
 *
 *      ENTRY           lsn - where the block is on disk
 *                      mem - memory image of the block
 *
 *      EXIT            No return value
 *
 *      CALLS           chk_no_writing
 *                      write_scratch
 *
 *      EFFECTS         May update disk
 */
void chk_fix_current (lsn, mem)
  ULONG lsn;
  union blk *mem;
{
#ifdef TRACE
  fprintf (stderr, "chk_fix_current ()\n");
  fflush (stderr);
#endif

  if (mem->d.sig == DBSIGVAL) {
    mem->d.lsnThisDir = lsn;
    if (!chk_no_writing (CHK_FIX_CURRENT_STR, NULL))
      write_scratch (lsn, mem, SECTORS_PER_DIRBLK);
  }
  else if (mem->d.sig == ABSIGVAL) {
    mem->a.lsnSelf = lsn;
    if (!chk_no_writing (CHK_FIX_CURRENT_STR, NULL))
      write_scratch (lsn, mem, SECTORS_PER_AB);
  }
}

/***    chk_sort_btree - sort filenames in a directory node
 *
 *      This function is called by chk_sort_directory to sort the names
 *      in a single BTREE node.  Each entry in the node is added to
 *      to the new directory, and then all downpointers are processed.
 *      This ordering is used to avoid adding names in mostly-sorted
 *      order, which might produce a less-than-optimal BTREE.
 *
 *      chk_sort_btree (db, lsn, name)
 *
 *      ENTRY           db   - memory image of new top-level DIRBLK
 *                      lsn  - sector number of BTREE node
 *                      name - pointer to cchName of directory's parent DIRENT,
 *                             NULL if sorting root directory
 *
 *      EXIT            No return value
 *
 *      CALLS           chk_add_dirent
 *                      clr_bit
 *                      chk_read_sectors
 *                      chk_sort_btree (recursive)
 */

/*
 * This macro is equal to the number of bytes in parameters and local
 * variables for one call to chk_sort_btree.  It is used by the stack checking
 * routines.  If parameters or local variables are added to this routine,
 * the macro should be updated.
 */

#define SORT_BTREE_STACK 28

void chk_sort_btree (db, lsn, name)
 PDIRBLK db;
  ULONG lsn;
  PUCHAR name;
{
  union dp dp;
 PDIRBLK this_db;
  register USHORT btp, i;

  if (chk_enter_recursive (SORT_BTREE_STACK)) {
    chk_exit_recursive (SORT_BTREE_STACK);
    return;
  }

#ifdef TRACE
  fprintf (stderr, "chk_sort_btree ()\n");
  fflush (stderr);
#endif

  if ((this_db=chk_read_sectors (lsn, SECTORS_PER_DIRBLK)) == NULL) {
    chk_exit_recursive (SORT_BTREE_STACK);
    return;
  }

  /*  If the sector is not a DIRBLK, then we don't sort it.  */
  if ( this_db->sig != DBSIGVAL ) {
        return;
  }


/* Go through all entries adding them.  For now, since we're not
 * adding the BTREE pointers (and since they'll change anyway)
 * we remove BTREE pointers before adding them, and restore them
 * after adding the entry so that the second loop will get them.
 * Since the end record has no valid name, a simple WHILE loop works.
 */

  dp.p = DIR_START (*this_db);          /* start at the first DIRENT */

  while (!(dp.d->fFlags & DF_END)) {  /* while not at the end */
    if (dp.d->fFlags & DF_BTP) {      /* don't add with BTP */
      btp = TRUE;                       /* indicate we're deleting temporarily */
      dp.d->fFlags &= ~DF_BTP;        /* clear the BTREE flag */
      dp.d->cchThisEntry -= sizeof (long);      /* delete pointer from entry's length */
    }
    else
      btp = FALSE;

/*
 * Try to add the DIRENT to the new directory. We check if the name is
 * valid and only add DIRENTs with good names. If a DIRENT name is bad, we
 * would have found this earlier and asked to sort the directory. We in
 * effect delete the DIRENT at this point by not adding it to the tree
 * being built. If we can't add the name, it must
 * be a duplicate name, so we mark the FNODE of the entry "deleted"
 * for later recovery and pitch the entry.
 *
 * The dirent is only added if it has a valid name and a non-zero FNode lsn.
 */

 if (chk_check_name (dp.d->bName, &dp.d->bCodePage,
                             dp.d->cchName) &&
                     dp.d->lsnFNode != 0 )

    if (chk_add_dirent (dp.d, db)) {    /* add this DIRENT to the new tree */
      if (name) {
        strcpy (scratchbuf, chk_curpath);
        strncat (scratchbuf, name+1, *name);
        strcpy (&scratchbuf [strlen (chk_curpath) + *name], "\\");
      }
      else
        strcpy (scratchbuf, "\\");

      i = strlen (scratchbuf);
      strncat (scratchbuf, dp.d->bName, dp.d->cchName);
      scratchbuf [i + dp.d->cchName] = 0;
      if (!chk_no_writing (CHK_DELETE_FILE_STR, &scratchptr))
        chk_mark_deleted (dp.d->lsnFNode, 1L);
    }

    while (!(db->culChange & 1))                /* make sure db is the topmost dirblk */
      if (read_scratch (db->lsnParent, db, SECTORS_PER_DIRBLK)) {
        chk_exit_recursive (SORT_BTREE_STACK);  /* hard error; just get out */
        FREE_BLOCK (this_db);
        return;
      }

    if (btp) {
      dp.d->fFlags |= DF_BTP;         /* set BTREE flag again */
      dp.d->cchThisEntry += sizeof (long);      /* add the pointer back to the length */
    }

    GETNEXT_ENTRY (dp);                    /* go to next entry */
  }

/* Now go through the block again, looking for downpointers to
 * process.  When we find one, we call ourselves recursively to
 * process the sub-node and all its children.  Here a WHILE loop
 * does not suffice, because the end record can have a valid BTREE
 * downpointer.  We check for the downpointer BEFORE checking for
 * end-of-directory.
 */

  dp.p = DIR_START (*this_db);          /* start at beginning again */

  while (TRUE) {                        /* now do all the downpointers */
    if (dp.d->fFlags & DF_BTP)        /* this entry has a BTREE */
      chk_sort_btree (db, DOWN_PTR (dp), name); /* sort the subtree */

    while (!(db->culChange & 1))                /* make sure db is the topmost dirblk */
      if (read_scratch (db->lsnParent, db, SECTORS_PER_DIRBLK)) {
        chk_exit_recursive (SORT_BTREE_STACK);  /* hard error; just get out */
        FREE_BLOCK (this_db);
        return;
      }

    if (dp.d->fFlags & DF_END)        /* this was the end record */
      break;                            /* but it might have had a BTP */

    GETNEXT_ENTRY (dp);                    /* go to next entry */
  }

/* We're done with this block.  If it was the top-level block,
 * its space is being re-used as the top level block.  Otherwise,
 * we'll be allocating space elsewhere, so we should free this
 * block in the bitmap.  Thus, there's a good chance that we'll
 * reallocate it anyway.
 */

  if (!(this_db->culChange & 1)) {      /* we're not doing the top level */
    if ((lsn >= sb.lsnFirstDirBlk) && (lsn <= sb.lsnLastDirBlk)) {
      set_db_bit ((lsn - sb.lsnFirstDirBlk) / SECTORS_PER_DIRBLK);
      for (i=0; i<SECTORS_PER_DIRBLK; i++)
        SetUseMapBits ( chk_db_usemap, lsn-sb.lsnFirstDirBlk+i, DISK_UNKNOWN );  /* 69658 -rjp */
    }
    else {
      for (i=0; i<SECTORS_PER_DIRBLK; i++) {
        SetHugeUseMapBits ( chk_disk_map, lsn+i, DISK_UNKNOWN );  /* mark as no longer a DIRBLK */ /* 69658 -rjp */
        set_bit (lsn+i);                  /* mark as free in bitmap */
      }
    }
    this_db->sig &= 0xffff0000L;        /* wipe his signature */
    write_scratch (this_db->lsnThisDir, this_db, SECTORS_PER_DIRBLK);
  }

  FREE_BLOCK (this_db);                 /* deallocate our scratch block */
  chk_exit_recursive (SORT_BTREE_STACK);
}

/***    chk_sort_directory - sort filenames in a subdirectory
 *
 *      This function is called by validate_structure when a directory
 *      is found which has one or more entries which are not in
 *      lexical order.  A new directory is created and the damaged
 *      one is passed through in order.  Entries from the old directory
 *      are added to the new one following standard file system rules.
 *      Finally, the old directory is deallocated and the sector number
 *      of the new one is returned.
 *
 *      It also called, to the same effect, when an orphaned directory
 *      recovered off disk is found to be out of order.
 *
 *
 *      If possible, the new directory will be allocated on top of
 *      the old one, to minimize disk space usage.
 *
 *      chk_sort_directory (lsn, name)
 *
 *      ENTRY           lsn  - sector number of FNODE for damaged directory
 *                      name - pointer to cchName of directory's parent DIRENT,
 *                             NULL if sorting root directory or if sorting
 *                             recovered directory
 *
 *      EXIT            No return value
 *
 *      CALLS           chk_no_writing
 *                      chk_read_sectors
 *                      chk_sort_btree
 *
 *      EFFECTS         Allocates and deallocates memory
 *                      Changes bit maps and disk map
 *                      May change disk contents
 */
void chk_sort_directory (lsn, name)
  ULONG lsn;
  PUCHAR name;
{
 PFNODE f;
 PDIRBLK db, new_db;
  union dp dp;
  USHORT i;

#ifdef TRACE
  fprintf (stderr, "chk_sort_directory ()\n");
  fflush (stderr);
#endif

/*
 * Make sure that we're allowed to change the disk.
 */

  if (chk_no_writing (CHK_UNSORTED_DIR_STR, NULL))
    return;

/*
 * Read in the FNODE for this directory and the top-level DIRBLK,
 * and allocate memory for a new top-level DIRBLK.
 */

  if ((f=chk_read_sectors (lsn, SECTORS_PER_FNODE)) == NULL)
    return;

  if( f->sig != FNSIGVAL ) {

    /*  Paranoia pays.  The supposed fnode is not an fnode.  */
    FREE_BLOCK(f);
    return;
  }

  if ((db=chk_read_sectors (f->fst.a.aall [0].lsnPhys, SECTORS_PER_DIRBLK)) == NULL) {
    FREE_BLOCK (f);
    return;
  }

  if ( db->sig != DBSIGVAL ) {

    /*  The supposed root DIRBLK is not a DIRBLK.  */
    FREE_BLOCK( f );
    FREE_BLOCK( db );
    return;
  }

  if ((new_db=ALLOCATE_BLOCK (SECTORS_PER_DIRBLK)) == NULL) {
    FREE_BLOCK (f);
    FREE_BLOCK (db);
    return;
  }

/*
 * Initialize the new DIRBLK's header
 */

  new_db->sig = DBSIGVAL;               /* set new block's signature */
  new_db->offulFirstFree = 20 + sizeof (DIRENT);  /* points after end rec */
  new_db->culChange = 1L;               /* topmost block */
  new_db->lsnParent = lsn;              /* parent is the FNODE */
  if (!(new_db->lsnThisDir = chk_write_data (lsn, new_db, SECTORS_PER_DIRBLK, TRUE))) {
    CHK_ERROR_MSG( CHK_INSF_MEM_CONTINUING_STR);
    FREE_BLOCK (f);
    FREE_BLOCK (db);
    FREE_BLOCK (new_db);
    return;
  }

  use_sectors (new_db->lsnThisDir, (ULONG)SECTORS_PER_DIRBLK, DISK_DIRBLK);
  f->fst.a.aall [0].lsnPhys = new_db->lsnThisDir;
  write_scratch (lsn, f, SECTORS_PER_FNODE);

/*
 * Initialize the new DIRBLK's end DIRENT
 */

  dp.p = DIR_START (*new_db);           /* point to first DIRENT     */

  memset (dp.p, '\0', sizeof(DIRENT));  /* This will zero bCodePage  */
                                        /* and everything else       */

  dp.d->cchThisEntry = sizeof (DIRENT);     /* minimum DIRENT w/o BTP    */
  dp.d->fFlags = DF_END;               /* mark as end record        */
  dp.d->fAttr  = 0;                    /* mark as end record        */
  dp.d->cchName = 0x01;                /* name is one character     */
  dp.d->bName[0] = 0xff;               /* last possible name        */
  write_scratch (new_db->lsnThisDir, new_db, SECTORS_PER_DIRBLK);

/*
 * Recursively descend the old directory tree, adding the entries to
 * the new directory.  Then make sure that there's a ".." entry in the
 * directory by trying to add one.  If there was no ".." entry, the
 * addition will succeed;  if there was, it'll just fail, no harm done.
 */

  chk_sort_btree (new_db, db->lsnThisDir, name);        /* sort the entire BTREE */

  dp.p = scratchbuf;                            /* point to scratch area */
  memset (scratchbuf, '\0', sizeof (DIRENT) + 4);  /* set up DIRENT */
  dp.d->cchThisEntry = (sizeof (DIRENT) + 4) & 0xfc;
  dp.d->fFlags  = DF_SPEC;          /* special ".." entry */
  dp.d->fAttr   = ATTR_DIRECTORY;
  dp.d->lsnFNode = lsn;
  dp.d->timLastMod  = get_time ();
  dp.d->timLastAccess = dp.d->timLastMod;
  dp.d->timCreate    = dp.d->timLastMod;
  dp.d->cchName = 2;
  memcpy (dp.d->bName, "\001\001", 2);
  read_scratch (lsn, f, SECTORS_PER_FNODE);
  read_scratch (f->fst.a.aall [0].lsnPhys, new_db, SECTORS_PER_DIRBLK);
  chk_add_dirent (dp.d, new_db);                /* throw in ".." entry */

/*
 * All done.  Free the old DIRBLK in the bitmap and deallocate our memory areas.
 */

  if ((db->lsnThisDir >= sb.lsnFirstDirBlk) && (db->lsnThisDir <= sb.lsnLastDirBlk)) {
    set_db_bit ((db->lsnThisDir - sb.lsnFirstDirBlk) / SECTORS_PER_DIRBLK);
    for (i=0; i<SECTORS_PER_DIRBLK; i++)
      SetUseMapBits ( chk_db_usemap, db->lsnThisDir-sb.lsnFirstDirBlk+(ULONG)i, DISK_UNKNOWN );  /* 69658 -rjp */
  }
  else {
    for (i=0; i<SECTORS_PER_DIRBLK; i++) {
      if (set_bit (db->lsnThisDir+(ULONG)i) != 2)
        SetHugeUseMapBits ( chk_disk_map, db->lsnThisDir+(ULONG)i, DISK_UNKNOWN );  /* 69658 -rjp */
    }
  }

  db->sig &= 0xffff0000L;  /* wipe his signature so we don't recover him */
  write_scratch (db->lsnThisDir, db, SECTORS_PER_DIRBLK);

  FREE_BLOCK (new_db);
  FREE_BLOCK (db);
  FREE_BLOCK (f);
}

/***    chk_hotfix - fix a partially corrupt sector
 *
 *      This function is called when a read fails.  It attempts to
 *      repeatedly read the bad sector.  If an attempt finally succeeds,
 *      sectors elsewhere are allocated and the data is stored there,
 *      and the new sector number is returned.  If the data cannot be
 *      read, a value of 0 is returned.  In any case, the sector is
 *      added to the bad block list and marked as in use in the bitmap
 *      and the global disk map.
 *
 *      If the read succeeds the first time, the same sector number is
 *      returned immediately, and no fixing is done.
 *
 *      It is the responsibility of the caller to store the return
 *      value of this function in all references to the structure
 *      being hotfixed.
 *
 *      If there are still sectors in the file system's hotfix table that
 *      are unaccounted for, this function will check that table to see
 *      whether the specified sectors have been hotfixed.  If so, chk_hotfix()
 *      allocates new sectors, copies the data, and returns the new sector
 *      where the stuff is.
 *
 *      The caller should allocate a buffer big enough to hold "nsect"
 *      sectors of data, and pass it to chk_hotfix to use to read the
 *      data into.  chk_hotfix will not deallocate the buffer.
 *
 *      chk_hotfix (lsn, nsect, mem)
 *
 *      ENTRY           lsn   - sector to be hotfixed
 *                      nsect - number of sectors in the structure to be moved
 *                      mem   - address of a memory area to read data into
 *
 *      EXIT            Returns new lsn if successfully fixed, 0 otherwise
 *
 *      CALLS           allocate_near
 *                      make_bad
 *                      read_scratch
 *                      write_scratch
 *
 *      EFFECTS         Changes disk
 *                      Changes bit maps and disk map
 */
ULONG chk_hotfix (lsn, nsect, mem)
  ULONG lsn;
  USHORT nsect;
  PUCHAR mem;
{
  USHORT i, j, mask;
  ULONG l, sect;
  USHORT repls [16];

  if ((lsn >= number_of_sectors) || (lsn + (ULONG)nsect > number_of_sectors))
    return (0L);                        /* run goes out-of-band, fail */

  if (spb.culHotFixes) {                        /* there are unreferenced hotfix sects */
    mask = (1 << nsect) - 1;            /* set a bit for each sector */
    for (i=0; i < (USHORT)spb.culHotFixes; i++) {
      if ((lsn <= hotfix_tbl [i]) && (lsn+nsect > hotfix_tbl [i])) {
        mask &= ~(1 << (hotfix_tbl [i] - lsn)); /* this sector is fixed */
        repls [hotfix_tbl [i] - lsn] = i;       /* remember which one it was */
      }
    }
    if (mask != (1 << nsect) - 1) {             /* something was fixed */
      if (chk_delete_inconsistency) {           /* if we'll be reallocating */
        if (!(l = allocate_near (lsn, nsect, nsect)))   /* get some sectors */
          CHK_OUT_MSG( SYSTEM_MSG, CHK_NO_HOTFIX_SPACE_STR, NULL);      /* no space-tell user */
      }
      for (i=0; i<nsect; i++) {                 /* check each sector */
        if (mask & (1 << i)) {                  /* this one wasn't fixed */
          read_scratch (lsn+i, mem + (i * SECSIZE), 1); /* get original sector */
          if (chk_delete_inconsistency)         /* if we're really fixing... */
            if (lsn < sb.lsnFirstDirBlk || lsn > sb.lsnLastDirBlk)
              set_bit (lsn+i);                  /* we won't use it anymore */
        }
        else {
          read_scratch (hotfix_tbl [repls [i] + spb.culMaxHotFixes],
                        mem + (i * SECSIZE), 1);        /* get replacement */
          if (chk_delete_inconsistency && l) {  /* can realloc, and have space */
            chk_no_writing (CHK_HOTFIX_FIXED_STR, NULL);
            sect = hotfix_tbl [i];

            make_bad (sect);                    /* mark bad sector in bad list */
            use_sectors (hotfix_tbl [i], 1L, DISK_BAD);

            spb.culHotFixes--;                  /* decrement record count */
            j = (USHORT)((spb.culMaxHotFixes - (i + 1)) * sizeof (ULONG));
            sect = hotfix_tbl [i+spb.culMaxHotFixes];  /* save replacement sector # */
            memmove (&hotfix_tbl [i], &hotfix_tbl [i+1], j); /* remove entry */
            memmove (&hotfix_tbl [i+spb.culMaxHotFixes],             /* from hotfix tbl */
                     &hotfix_tbl [i+1+spb.culMaxHotFixes], j);
            memmove (&hotfix_tbl [i+spb.culMaxHotFixes*2],
                     &hotfix_tbl [i+1+spb.culMaxHotFixes*2], j);
            hotfix_tbl [spb.culMaxHotFixes * 2 - 1] = sect;     /* re-use sector number */
            memmove (&chk_hotfix_masks [i], &chk_hotfix_masks [i+1],
                     j / sizeof (ULONG));
          }
        }
      }
      if (!chk_delete_inconsistency) {
        chk_no_writing (CHK_HOTFIX_STR, NULL);  /* can we fix the disk? */
        return (lsn);                   /* no, but at least we got the data */
      }
      else if (l) {
        write_scratch (l, mem, nsect);          /* save our accumulated data */
        write_scratch ((ULONG)SEC_SPAREB, &spb, 1);     /* save spareblock */
        write_scratch (spb.lsnHotFix, hotfix_tbl, SPB); /* and hotfix tbl */
        return (l);                             /* return new sector number */
      }
      else                                      /* no space to hotfix */
        return (lsn);                           /* return old sector number */
    }
  }

  for (i=0; i<10; i++)                  /* try ten times to read it */
    if (!read_scratch (lsn, mem, nsect))  /* read the sectors */
      break;                            /* got them - stop trying */

  if (!i)                               /* got it the first time */
    return (lsn);

/*
 * Make sure we're authorized to change the disk.
 */

  if (chk_no_writing (CHK_HOTFIX_STR, NULL))
    return (lsn);                       /* can't fix - just return same number */

#ifdef TRACE
  fprintf (stderr, "chk_hotfix (%lx, %x)\n", lsn, nsect);
  fflush (stderr);
#endif

  for (j=0; j<nsect; j++)               /* for all these sectors... */
    make_bad (lsn+j);                   /* add to bad list, mark in bit map */

  if (i == 10) {                        /* ten times wasn't enough */
#ifdef TRACE
    fprintf (stderr, "chk_hotfix: sectors completely unreadable.\n");
    fflush (stderr);
#endif
    return (0L);                        /* return failure code */
  }
  else {                                /* got the sectors - move them */
    do {                                /* do this until we're ok */
      l = allocate_near (lsn, nsect, nsect);    /* get some fresh sectors */
      if (!l) {                         /* no space left! */
#ifdef TRACE
        fprintf (stderr, "chk_hotfix: out of disk space.\n");
        fflush (stderr);
#endif
        return (0L);                    /* return failure code */
      }
      use_sectors (l, (ULONG)nsect, DISK_DATA);
      if (i=write_scratch (l, mem, nsect)) /* write failed - these are bad */
        for (j=0; j<nsect; j++)         /* for all these sectors... */
          make_bad (l+j);               /* add to bad list, mark in bit map */
    } while (i);                        /* while write didn't work */
#ifdef TRACE
    fprintf (stderr, "chk_hotfix: sectors hotfixed to %lx.\n", l);
    fflush (stderr);
#endif
    return (l);                         /* return where we put the data */
  }
}

/***    chk_new_root - create a new root DIRBLK
 *
 *      This function is called by check_system when structure validation
 *      indicates that the root directory is bad.  This may occur if, for
 *      example, the root DIRBLK's signature is erased, or if the root
 *      FNODE contains an invalid sector pointer.  In this case, we have
 *      to build a new root directory for the user.  He can run CHKDSK /F
 *      to recover his files.
 *
 *      chk_new_root (lsn)
 *
 *      ENTRY           lsn - sector number of root FNODE
 *
 *      EXIT            No return value
 *
 *      CALLS           allocate_near
 *                      read_scratch
 *                      write_scratch
 *
 *      WARNINGS        Files will have to be recovered
 *
 *      EFFECTS         Creates a new root DIRBLK
 *                      Allocates and deallocates memory
 *                      Allocates disk space
 */
void chk_new_root (lsn)
  ULONG lsn;
{
 PDIRBLK db;
 PFNODE f;
  ULONG dbsec;
  union dp dp;

  if (chk_no_writing (CHK_ELEM_STRUC_INV_STR, NULL))
    return;

  if ((db=ALLOCATE_BLOCK (SECTORS_PER_DIRBLK)) == NULL)
    return;

  if (!(dbsec=chk_write_data (lsn, db, SECTORS_PER_DIRBLK, TRUE))) {
    FREE_BLOCK (db);
    return;
  }
  use_sectors (dbsec, (ULONG)SECTORS_PER_DIRBLK, DISK_DIRBLK);

  f = ALLOCATE_BLOCK (SECTORS_PER_FNODE);
  if ((lsn < number_of_sectors) && !read_scratch (lsn, f, SECTORS_PER_FNODE) &&
      (f->sig == FNSIGVAL)) {
    f->sig &= 0xffff0000;                       /* wipe old FNODE's sig */
    write_scratch (lsn, f, SECTORS_PER_FNODE);  /* and save it */
  }

  memset (f, '\0', sizeof (FNODE));
  if (!(f->lsnContDir=chk_write_data (lsn, f, SECTORS_PER_FNODE, TRUE))) {
    read_scratch (lsn, f, SECTORS_PER_FNODE);   /* no space - use old FNODE */
    f->lsnContDir = lsn;                        /* make parent ptr correct */
    f->fst.a.aall [0].lsnPhys = dbsec;            /* and hope it's good */
  }
  else {
    use_sectors (f->lsnContDir, (ULONG)SECTORS_PER_FNODE, DISK_FNODE);
    f->sig = FNSIGVAL;                  /* init new FNODE */
    f->fst.alb.cFree = LEAFPERFNODE - 1;
    f->fst.alb.cUsed = 1;
    f->fst.alb.oFree = FIELDOFFSET (FNODE, fst.a.aall [1].lsnLog) -
                       FIELDOFFSET (FNODE, fst.alb.bFlag);
    f->fst.a.aall [0].lsnPhys = dbsec;

    if (lsn < number_of_sectors) {              /* free the old FNODE */
      SetHugeUseMapBits ( chk_disk_map, lsn, DISK_UNKNOWN ); /* no longer used in diskmap */ /* 69658 -rjp */
      set_bit (lsn);                            /* mark free in bitmap */
    }
    root_fnode = f->lsnContDir;                 /* save FNODE addr for later use */
  }
  sb.lsnRootFNode = f->lsnContDir;                      /* point superblock at the FNODE */
  chk_write_sectors (f->lsnContDir, f, SECTORS_PER_FNODE);

/*
 * FNODE has been saved.  Build a fresh DIRBLK.
 */

  memset ((PUCHAR)db, '\0', sizeof (DIRBLK));

/*
 * Fill in the DIRBLK header.
 */

  db->sig = DBSIGVAL;
  db->culChange = 1;
  db->lsnParent = f->lsnContDir;
  db->lsnThisDir = dbsec;
  dp.p = DIR_START (*db);

#ifdef DOT_ENTRY
/*
 * Build the "." entry.
 */

  dp.d->cchThisEntry = sizeof (DIRENT);
  dp.d->fAttr = ATTR_DIRECTORY;
  dp.d->fFlags = 0x00;
  dp.d->lsnFNode = sb.lsnRootFNode;
  dp.d->cchName = 1;
  dp.d->bName[0] = '.';
  GETNEXT_ENTRY (dp);
#endif

/*
 * Build the ".." entry.
 */

  dp.d->cchThisEntry = sizeof (DIRENT) + 4;
  dp.d->fFlags = DF_SPEC;
  dp.d->fAttr  = ATTR_DIRECTORY;
  dp.d->lsnFNode = lsn;
  dp.d->timLastMod = get_time ();
  dp.d->timLastAccess = dp.d->timLastMod;
  dp.d->timCreate = dp.d->timLastMod;
  dp.d->cchName = 2;
  memcpy (dp.d->bName, "\001\001", 2);
  GETNEXT_ENTRY (dp);

/*
 * Build the end record.
 */

  dp.d->cchThisEntry = sizeof (DIRENT);
  dp.d->fFlags = DF_END;
  dp.d->fAttr  = 0;
  dp.d->cchName = 1;
  dp.d->bName[0] = 0xff;
  GETNEXT_ENTRY (dp);
  db->offulFirstFree = dp.p - (PUCHAR)db;

/*
 * Save the new DIRBLK and the superblock.
 */

  chk_write_sectors (dbsec, db, SECTORS_PER_DIRBLK);

  write_scratch ((ULONG)SEC_SUPERB, &sb, 1);    /* save the superblock */
}
