/*static char *SCCSID = "@(#)rebuild.c  6.3 92/02/19";*/
/*static char *SCCSID = "@(#)rebuild.c  6.3 92/02/19";*/
/***    REBUILD.C - Routines to rebuild a badly trashed system.
 *
 *      CHKDSK
 *      Gregory A. Jones
 *      Copyright 1988 Microsoft Corporation
 *
 *      Modification history:
 *      G.A. Jones      07/12/88        Removed from RECOVER.C due to size.
 *
 *      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.
 */

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

USHORT chk_rebuilding_root = TRUE;    /* false once root dir is traced */

/***    chk_rebuild_tree -- rebuild a single file system tree
 *
 *      This function is called by chk_rebuild_system to recursively
 *      rebuild the entire file system.  It first allocates the
 *      structure it's working on in the bit maps and the global
 *      disk map, including all of its direct descendants;  then,
 *      for each descendant which is a tree itself, calls itself
 *      recursively.
 *
 *      If a block cannot be read, the tree is not processed below
 *      that block.  Of course, once the root FNODE and DIRBLK have
 *      been recovered, a more normal CHKDSK can be run, scanning
 *      free space, to recover any other data.
 *
 *      chk_rebuild_tree (lsn, type)
 *
 *      ENTRY           lsn  - where the structure is on disk
 *                      type - what kind of structure it is
 *
 *      EXIT            No return value
 *
 *      CALLS           clr_bit
 *                      chk_read_sectors
 *                      chk_rebuild_tree (recursive)
 *                      chk_check_eas
 *                      chk_check_acl
 *                      use_sectors
 *
 *      EFFECTS         Modifies bit map and global disk map
 *                      Allocates memory
 */

/*
 * The following macro equals the number of bytes used in each call to
 * chk_rebuild_tree, used by the stack checking routines.  If any local
 * variables or parameters are added, this macro should be updated.
 */

#define REBUILD_TREE_STACK 24

void chk_rebuild_tree (lsn, type)
  ULONG lsn;
  USHORT type;
{
  union dp dp;
  union blk *b;
  register USHORT i;
  ULONG *ptr;

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

#ifdef TRACE
  fprintf (stderr, "chk_rebuild_tree (%lx, TYPE_%s)\n", lsn, chk_vstypes [type]);
  fflush (stderr);
#endif

  if ((b=chk_read_sectors (lsn, chk_sizes [type])) == NULL) {

    /*
     *  Can't read in the sector--update stack trace info and get out.
     */
    chk_exit_recursive (REBUILD_TREE_STACK);
    return;
  }

  switch (type) {

    case TYPE_DIRBLK:

      if ((b->d.sig != DBSIGVAL) ||             /* the block isn't a DIRBLK */
          (use_sectors (lsn, (ULONG)SECTORS_PER_DIRBLK, DISK_DIRBLK))) {
#ifdef TRACE
        fprintf (stderr, "chk_rebuild_tree: DIRBLK is corrupt or cross-linked\n");
        fflush (stderr);
#endif
        chk_exit_recursive (REBUILD_TREE_STACK);
        return;                                 /* or is cross-linked */
      }

      dp.p = DIR_START (b->d);                  /* offset of first DIRENT */

      while (TRUE) {                            /* break out manually */
        if (dp.d->fFlags & DF_BTP)            /* this entry has a downptr */
          chk_rebuild_tree (DOWN_PTR (dp), TYPE_DIRBLK); /* rebuild it */

        if (dp.d->fFlags & DF_END)            /* this entry is the end rec */
          break;                                /* we're all done! */

        if (memcmp (dp.d->bName, "\001\001", 2))  /* don't process ".." */
          chk_rebuild_tree (dp.d->lsnFNode,     /* rebuild this file or subdir */
                            (dp.d->fAttr & ATTR_DIRECTORY) ?
                             TYPE_SUBDIR : TYPE_FNODE);

        else if (chk_rebuilding_root) {
          chk_rebuilding_root = FALSE;
          if (dp.d->lsnFNode != root_fnode) {
            dp.d->lsnFNode = root_fnode;
            write_scratch (lsn, &b->d, SECTORS_PER_DIRBLK);
          }
        }

        GETNEXT_ENTRY (dp);                        /* move to next entry */
      }
      break;

    case TYPE_FNODE:
      if ((b->f.sig != FNSIGVAL) ||             /* this isn't an FNODE */
          (use_sectors (lsn, (ULONG)SECTORS_PER_FNODE, DISK_FNODE))) {
#ifdef TRACE
        fprintf (stderr, "chk_rebuild_tree: FNODE is corrupt or cross-linked\n");
        fflush (stderr);
#endif
        chk_exit_recursive (REBUILD_TREE_STACK);
        return;                                 /* or it's cross-linked */
      }

      ptr = &b->f.fst.a.aall [0].lsnLog;          /* point to first alloc rec */
      if (b->f.fst.alb.bFlag & ABF_NODE) {        /* FNODE contains downpointers */
        for (i=0; i<b->f.fst.alb.cUsed; i++) {    /* for each downpointer rec */
          chk_rebuild_tree (*ptr, TYPE_AB);     /* rebuild the alloc block */
          ptr += 2;                             /* each node rec is 2 dwords */
        }
      }

      else {                                    /* FNODE contains runs */
        for (i=0; i<b->f.fst.alb.cUsed; i++) {    /* for each run */
          use_sectors (*(ptr+2), *(ptr+1), DISK_DATA);  /* mark in diskmap */
          ptr += 3;                             /* each leaf rec is 3 dwords */
        }
      }
      chk_check_eas (lsn, &b->f);               /* rebuild any EAs */
      chk_check_acl (lsn, &b->f);               /* rebuild any ACL */

      break;

    case TYPE_SUBDIR:
      if ((b->f.sig != FNSIGVAL) ||             /* this isn't an FNODE */
          (use_sectors (lsn, (ULONG)SECTORS_PER_FNODE, DISK_SUBDIR))) {
#ifdef TRACE
        fprintf (stderr, "chk_rebuild_tree: subdir FNODE is corrupt or cross-linked\n");
        fflush (stderr);
#endif
        chk_exit_recursive (REBUILD_TREE_STACK);
        return;                                 /* or it's cross-linked */
      }

      chk_rebuild_tree (b->f.fst.a.aall [0].lsnPhys, TYPE_DIRBLK); /* rebuild subdir */

      chk_check_eas (lsn, &b->f);               /* rebuild any EAs */
      chk_check_acl (lsn, &b->f);               /* rebuild any ACL */
      break;

    case TYPE_AB:
      if ((b->a.sig != ABSIGVAL) ||             /* this isn't an alloc block */
          (use_sectors (lsn, (ULONG)SECTORS_PER_AB, DISK_AB))) {
#ifdef TRACE
        fprintf (stderr, "chk_rebuild_tree: AB is corrupt or cross-linked\n");
        fflush (stderr);
#endif
        chk_exit_recursive (REBUILD_TREE_STACK);
        return;                                 /* or it's cross-linked */
      }

      ptr = AB_START (b);                       /* point to the first record */

      if (b->a.alb.bFlag & ABF_NODE) {  /* pointers are downpointers */
        for (i=0; i<b->a.alb.cUsed; i++) {      /* for all records... */
          chk_rebuild_tree (*(ptr+1), TYPE_AB); /* rebuild recursively */
          ptr += 2;                             /* move to next record */
        }
      }

      else {                                            /* pointers are runs */
        for (i=0; i<b->a.alb.cUsed; i++) {      /* for all records... */
          use_sectors (*(ptr+2), *(ptr+1), DISK_DATA);  /* mark diskmap */
          ptr += 3;                                     /* move to next record */
        }
      }

      break;
  }

  FREE_BLOCK (b);                               /* deallocate this block */
  chk_exit_recursive (REBUILD_TREE_STACK);
}

/***    chk_rebuild_root -- create a new root directory
 *
 *      This function is called if there are no directories on the disk
 *      to rebuild the system from.  We just allocate a new DIRBLK and
 *      FNODE and hope that we don't land on an important file.  The user
 *      must run CHKDSK /F to recover his files.
 *
 *      chk_rebuild_root (void)
 *
 *      ENTRY           No parameters
 *
 *      EXIT            Returns sector number of new FNODE, 0L if failure
 *
 *      CALLS           write_scratch
 *                      allocate_near
 *                      allocate_middle_sectors
 *
 *      WARNINGS        None
 *
 *      EFFECTS         Allocates disk space
 *                      Allocates and deallocates memory
 *                      Writes to disk
 */
ULONG chk_rebuild_root (void)
{
  ULONG sec, fnsec;
  union dp dp;
  union blk *blk;

  if (!(blk=ALLOCATE_BLOCK (SECTORS_PER_DIRBLK)))
    return (0L);

  if (!(sec=chk_write_data (number_of_sectors / 2, blk, SECTORS_PER_DIRBLK, TRUE))) {
    FREE_BLOCK (blk);
    return (0L);
  }

  if (!(fnsec=chk_write_data (sec, blk, SECTORS_PER_FNODE, TRUE))) {
    for (fnsec = sec; fnsec < sec + SECTORS_PER_DIRBLK; fnsec++)
      set_bit (fnsec);
    FREE_BLOCK (blk);
    return (0L);
  }

  memset (blk, '\0', sizeof (union blk));       /* clear out the DIRBLK */
  blk->d.sig = DBSIGVAL;                        /* fill in DIRBLK header */
  blk->d.culChange = 1;
  blk->d.lsnParent = fnsec;
  blk->d.lsnThisDir = sec;
  dp.p = &blk->d.bFirst;

/*
 * Create basic DIRBLK entries:  .  ..  <end>
 */

#ifdef DOT_ENTRY
  dp.d->fFlags = DF_SPEC;
  dp.d->fAttr  = ATTR_DIRECTORY;
  dp.d->lsnFNode = fnsec;
  dp.d->cchFSize = 5;
  dp.d->timLastMod = get_time ();
  dp.d->timCreate = get_time ();
  dp.d->timLastAccess = get_time ();
  dp.d->cchThisEntry = (sizeof ( DIRENT)+1+3) & 0xfc;
  dp.d->cchName = 1;
  dp.d->bName[0] = '.';
  GETNEXT_ENTRY (dp);
#endif
  dp.d->fFlags   = DF_SPEC;
  dp.d->fAttr    = ATTR_DIRECTORY;
  dp.d->lsnFNode = fnsec;
  dp.d->cchFSize = 5;
  dp.d->timLastMod = get_time ();
  dp.d->timCreate = get_time ();
  dp.d->timLastAccess = get_time ();
  dp.d->cchThisEntry = (sizeof ( DIRENT)+2+3) & 0xfc;
  dp.d->cchName = 2;
  strcpy (dp.d->bName, "\001\001");
  GETNEXT_ENTRY (dp);

  dp.d->fFlags = DF_END;
  dp.d->fAttr  = 0;
  dp.d->lsnFNode = 0;
  dp.d->cchFSize = 0;
  dp.d->cchThisEntry = sizeof ( DIRENT);
  dp.d->cchName = 1;
  dp.d->bName[0] = 0xff;
  GETNEXT_ENTRY (dp);
  blk->d.offulFirstFree = dp.p - (UCHAR *)blk;

  write_scratch (sec, blk, SECTORS_PER_DIRBLK); /* save the DIRBLK */

/*
 * Create the FNODE
 */

  memset (blk, '\0', sizeof ( FNODE));    /* clear out for an FNODE */
  blk->f.sig = FNSIGVAL;
  blk->f.bFlag = FNF_DIR;
  blk->f.lsnContDir = fnsec;

  blk->f.fst.alb.cFree = LEAFPERFNODE - 1;
  blk->f.fst.alb.cUsed = 1;
  blk->f.fst.alb.oFree = 0x14;

  blk->f.fst.a.aall [0].lsnPhys = sec;    /* other leaf fields are all 0L */
  blk->f.fst.a.aall [1].lsnLog = -1L;
  write_scratch (fnsec, blk, SECTORS_PER_FNODE);
  return (fnsec);
}


/***    chk_rebuild_system -- rebuild a file system from scratch
 *
 *      This function is called when chk_validate_elementary reports that
 *      the file system is too badly damaged to recover in the usual
 *      way;  for example, if the super block is trashed, bit maps are
 *      unreadable, the root FNODE is trashed, etc.  We scan the disk
 *      for an FNODE, starting near the middle of the disk where FORMAT
 *      is most likely to put the root FNODE.  When we find an FNODE,
 *      we trace it upward through parent pointers until we reach the
 *      root FNODE or a garbage pointer.  When we've gone as far as we
 *      can, we trace the whole tree recursively.  New bitmaps will
 *      be built and stored in places on the disk which don't have
 *      recognizable signatures.
 *
 *      It is recommended that, immediately after this type of
 *      recovery is performed, the user use CHKDSK /F to search
 *      the entire disk for lost structures, in case we couldn't
 *      get back the whole tree recursively.
 *
 *      chk_rebuild_system (void)
 *
 *      ENTRY           No parameters
 *
 *      EXIT            No return value
 *
 *      CALLS           chk_exit_error
 *                      chk_parent
 *                      read_scratch
 *                      chk_rebuild_bitmaps
 *                      chk_rebuild_tree
 *                      write_scratch
 *
 *      EFFECTS         Allocates memory
 *                      Writes new bitmaps to disk
 */
void chk_rebuild_system (void)
{
  ULONG lsn, cur, par, i;
  ULONG dblow, dbhigh, dbsize;
  union blk *p;
  ULONG ulDiskMapSize = ( number_of_sectors >> 2 ) + 1;                              /* 69658 -rjp */
  USHORT usDBUseMapSize = ( ( MAX_DBS_PER_DIRBAND * SECTORS_PER_DIRBLK ) >> 2 ) + 1; /* 69658 -rjp */

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

/*
 * Tell the user that the filesystem has serious problems.  If he didn't
 * authorize us to change the disk, reassure him that we won't, then return
 * immediately.
 */

  if (chk_no_writing (CHK_ELEM_STRUC_INV_STR, NULL))
    return;

/*
 * Zap the disk maps since we're rebuilding from scratch.
 */

  memset (&sb, '\0', sizeof (sb));
  memset (&spb, '\0', sizeof (spb));

  for (i=0L; i + 32768L < ulDiskMapSize; i += 32768L)          /* clear out the map */               /* 69658 -rjp */
    memset (&chk_disk_map [i], DISK_UNKNOWN, 32768U);   /* in 32K chunks */
  if (ulDiskMapSize - i)                                                                             /* 69658 -rjp */
    memset (&chk_disk_map [i], DISK_UNKNOWN, (size_t)(ulDiskMapSize - i)); /* clear last fraction */ /* 69658 -rjp */
  memset (chk_db_usemap, DISK_UNKNOWN, usDBUseMapSize );                                             /* 69658 -rjp */

  use_sectors (0L, (ULONG)SEC_SUPERB + SPB, DISK_CONTROL); // "use" boot, sb, spb

  p = ALLOCATE_BLOCK (SECTORS_PER_DIRBLK);      /* get memory for an FS block */

/*
 * Look for an FNODE, starting at the place where FORMAT is likely to
 * put it in the first place.  It may not be there anymore -- if that
 * sector goes bad, the file system will hotfix it and put it somewhere
 * else.  We just start at the middle so that, in the common case, we'll
 * find the root FNODE right away.
 */

  cur = (number_of_sectors / (8L * 2048L)) / 2L;  /* cur = middle band number */
  lsn = (cur) ? cur * 8L * SPB * SECSIZE - 8L : ((number_of_sectors / 2L) & ~7L);

  for (; lsn < number_of_sectors; lsn++)
    if (!read_scratch (lsn, p, 1) && (p->d.sig == FNSIGVAL) &&
        (p->f.bFlag & FNF_DIR))
      break;                            /* found a directory's FNODE! */

/*
 * Didn't find *any* FNODEs at all in the second half of the disk.
 * Start again at the beginning and search forward.
 */

  if (lsn == number_of_sectors)         /* didn't find - start at beginning */
    for (lsn=0L; lsn < (number_of_sectors >> 1); lsn++)
      if (!read_scratch (lsn, p, 1) && (p->d.sig == FNSIGVAL) &&
          (p->f.bFlag & FNF_DIR))
        break;                          /* found one! */

/*
 * If we didn't find any FNODEs on the disk, we'll have to build a brand
 * new root directory later.
 */

  if (p->d.sig != FNSIGVAL)
    root_fnode = 0L;

/*
 * Use the FNODE parent pointers to chain upward until we find a self-
 * referential one.  That's the root FNODE.  If we encounter an error
 * before then, we'll just have to rebuild the system from there down.
 * Of course, the user can still run CHKDSK /F:3 to get back the rest of
 * the system.
 */

  else {
    cur = lsn;                          /* start at the FNODE we found */
    while ((par=chk_parent (p)) != cur) { /* while no self-reference */

      /*
       *  Read the parent.  If we can't read the parent,
       *  or if the parent is not an fnode, we'll stop
       *  with the current, and make it the root fnode.
       */
      if ( read_scratch (par, p, 1) ||
           (p->f.sig != FNSIGVAL) ) {

        /*
         *  OK, the current will have to do.
         *  Re-read it.
         */
        read_scratch (cur, p, 1);
        break;
      }
      cur = par;                        /* chain to parent pointer */
    }
    root_fnode = cur;                   /* save this for rebuilding superblock */

/*
 * Now "p" points to an image of the highest FNODE we could get to.
 * Zap the DIRBLK band information in the superblock (since we don't
 * know where the DIRBLK band is yet) and trace the file system from
 * there down.
 */
    if (!read_scratch (p->f.fst.a.aall[0].lsnPhys,
                       scratchbuf, SECTORS_PER_DIRBLK) &&
        *(ULONG *)scratchbuf == DBSIGVAL) {

      /*  save DIRBLK band information for later  */
      dblow = sb.lsnFirstDirBlk;
      dbhigh = sb.lsnLastDirBlk;
      dbsize = sb.clsnDirBlkBand;

      sb.lsnFirstDirBlk = 0L;
      sb.lsnLastDirBlk = 1L;
      sb.clsnDirBlkBand = 0L;

      chk_rebuild_tree (cur, TYPE_SUBDIR); /* recursively trace the whole system */

      /*  restore DIRBLK band information  */
      sb.lsnFirstDirBlk = dblow;
      sb.lsnLastDirBlk = dbhigh;
      sb.clsnDirBlkBand = dbsize;
    }
    else
      root_fnode = 0L;   /* tell chk_rebuild_bitmaps to do a new root dir  */

  }

  FREE_BLOCK(p);

/*
 * We've found all filesystem objects that we know about.  Reconstruct
 * the bit maps and superblock from what we know.
 */

  chk_rebuild_bitmaps ();               /* reallocate and save bitmaps */

}
