/*static char *SCCSID = "@(#)clean.c	6.2 92/03/10";*/
/*static char *SCCSID = "@(#)clean.c	6.2 92/03/10";*/
/***	CLEAN.C - Routines to handle filesystem hotfix cleanup
 *
 *	CHKDSK
 *	Gregory A. Jones
 *	Copyright 1988 Microsoft Corporation
 *
 *	Modification history:
 *	G.A. Jones	10/12/88	Removed from FIX.C for space reasons.
 */

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


/***	chk_find_ab_ip - find insertion point in a list of ALNODE pointers
 *
 *	This function is called when chk_insert_into_tree needs to insert an
 *	ALNODE downpointer into a block.  It looks through the block for
 *	a record with the specified LOF field.	If found, a pointer to the
 *	record is returned;  otherwise, NULL.
 *
 *	BUGBUG - does this correctly find the last record?
 *
 *	chk_find_ab_ip (tree, lof)
 *
 *	ENTRY		tree - pointer to the block (FNODE or ALSEC) to search
 *			lof  - LOF to search for
 *
 *	EXIT		Returns pointer to insert point if found, or NULL
 *
 *	CALLS		None
 *
 *	WARNINGS	None
 *
 *	EFFECTS		None
 */
UCHAR *chk_find_ab_ip (tree, lof)
  union blk *tree;
  ULONG lof;
{
  USHORT i, top;
  ULONG *l;

/*
 * Determine whether this block is an FNODE or an ALSEC by its signature.
 */
  if (tree->f.sig == FNSIGVAL) {
    l = (ULONG *)&tree->f.fst.a;     /* get first record address */
    top = tree->f.fst.alb.cUsed;     /* number of records to check */
  }
  else {
    l = (ULONG *)((UCHAR *)&tree->a.a);
    top = tree->a.alb.cUsed;
  }

/*
 * Now look through all the ALNODEs for the LOF we want.
 */

  for (i=0; i<top; i++, l+=2)			/* for all ALNODEs */
    if (*l >= lof)				/* the LOF is correct or beyond */
      break;					/* stop looking */
  return ((i == top) ? NULL : (UCHAR *)l);	/* if found, return it */
}

/***	chk_ab_makeroom - open up a gap in an allocation block
 *
 *	This function is called to open a hole in an array of allocation
 *	blocks, so that a new leaf or node record can be inserted.  The
 *	caller actually copies the new data into the hole;  chk_ab_makeroom
 *	takes care of everything else, including updating the occupied
 *	and free counts and the free pointer.
 *
 *	If no more slots are available in the array (AB_OCNT is used for
 *	this), chk_ab_makeroom returns a FALSE value.
 *
 *	chk_ab_makeroom (tree, ip, size)
 *
 *	ENTRY		tree - structure (FNODE or ALSEC) containing the array
 *			ip   - place to open a hole
 *			size - how big (in bytes) the hole should be
 *
 *	EXIT		Returns TRUE if space available and hole made,
 *			FALSE otherwise
 *
 *	CALLS		memmove
 *
 *	WARNINGS cUsed should accurately reflect the amount of space
 *			left in the block.
 *
 *	EFFECTS		Opens a hole in an FNODE or ALSEC
 */
USHORT chk_ab_makeroom (tree, ip, size)
  union blk *tree;
  UCHAR *ip;
  USHORT size;
{
  UCHAR *end;
  ALBLK *a;

/*
 * First determine what kind of block this is, from its signature.
 * From there, get the ALBLK control structure.
 */
  if (tree->f.sig == FNSIGVAL)
    a = &tree->f.fst.alb;
  else
    a = &tree->a.alb;
/*
 * If there are no records free, return failure.
 */
  if (!a->cFree)
    return (FALSE);

/*
 * Calculate the end of the records from the free pointer, open a hole in
 * the array, and adjust the control structure.
 */
  end = (UCHAR *)a + a->oFree;
  memmove (ip+size, ip, end - ip);	/* open a hole */
  a->cUsed++;				/* we'll have 1 more occupied */
  a->cFree--;				/* 1 less free */
  a->oFree += size;			/* free space is this much later */
  return (TRUE);
}

/***	chk_insert_into_tree - insert a leaf or node into an allocation tree
 *
 *	This function is called to insert a leaf or node record into an
 *	allocation tree, splitting the tree if necessary.  If there is
 *	room in the specified block for the record, it is simply inserted.
 *	If there is no room, but the block is an FNODE, the entire FNODE
 *	array is moved into a new level in the tree (since an ALSEC is
 *	much bigger than the small part of the FNODE reserved for allocation,
 *	it will ALWAYS fit).  If there is no room and the block is an ALSEC,
 *	the block is split in half, the new record inserted in the proper
 *	half, and a new ALNODE inserted into the parent using this same
 *	algorithm.
 *
 *	The block should be present in the filesystem-style cache, held.
 *	When chk_insert_into_tree is done, all blocks involved are saved to
 *	disk.  The original block will remain in the cache, held, so that
 *	the caller can continue scanning it.
 *
 *	We don't flush the cache until we're certain that the entire split
 *	is successful.	If we have a bad problem in the middle of a split
 *	(unreadable parent, out of space, etc.) we just punt the whole cache
 *	and return immediately.
 *
 *	chk_insert_into_tree (tree, stuff, ip, size, cursec)
 *
 *	ENTRY		tree   - pointer to structure to insert into
 *				 (in cache, held)
 *			stuff  - ALLEAF or ALNODE to insert
 *			ip     - pointer into "tree" where "stuff" should
 *				 be inserted
 *			size   - how big (in bytes) "stuff" is
 *			cursec - where "tree" is on disk
 *
 *	EXIT		Returns 0 if simple insertion was done,
 *				1 if tree had to be split or a level was added,
 *				2 if insufficient disk space or read error
 *
 *	CALLS		chk_ab_makeroom
 *			_adr_to_bhdr
 *			memmove
 *			allocate_near
 *			readbuf
 *			chk_find_ab_ip
 *			flushcache
 *
 *	WARNINGS	None
 *
 *	EFFECTS		Uses filesystem cache
 *			Changes contents of "tree" and other allocation blocks
 *			Reads and writes to disk
 */
USHORT chk_insert_into_tree (tree, stuff, ip, size, cursec)
  union blk *tree;	/* structure to insert into (in cache, held) */
  UCHAR *stuff;		/* stuff to insert */
  UCHAR *ip;		/* place to insert */
  USHORT size;		/* amount of stuff to insert */
  ULONG cursec;		/* where "tree" is on disk */
{
  ULONG sec, lof;
  union blk *cblk;
  ALSEC *a, *block;
  ALNODE *node;
  BUFNODE *hdr1, *hdr2;
  UCHAR *end, *half, *p, *p2;
  USHORT i, rc;

  cblk = tree;			/* start at the specified block */
  rc = 0;			/* assume a simple insertion */

  while (TRUE) {
/*
 * Try to insert this object into the structure at the desired insertion point.
 * If we can, great -- we're done.
 */
    if (chk_ab_makeroom (cblk, ip, size)) {	/* made room! */
      hdr1 = _adr_to_bhdr ((DIRBLK *)cblk);	/* get buffer header */
      hdr1->bDirtMask = TRUE;			/* make him dirty */
      if (cblk != tree)				/* if he's not the original */
	hdr1->cusHolds = 0;			/* then unhold him */
      memmove (ip, stuff, size);		/* copy in our data */
      break;					/* all done! */
    }
/*
 * We couldn't insert the thing.  There's still a chance that it'll be
 * fairly simple -- if we're at the FNODE, we just push all the records
 * in the FNODE (including the new one) into a new allocation sector,
 * and the FNODE gets a single downpointer to that sector.
 */
    rc = 1;			/* it wasn't a simple insertion */

    if (cblk->f.sig == FNSIGVAL) {
      if (!(sec = allocate_near (cursec, SECTORS_PER_AB, SECTORS_PER_AB))) {
        chk_no_writing (CHK_NO_HOTFIX_SPACE_STR, NULL);
        return (2);
      }
	   use_sectors (sec, (ULONG)SECTORS_PER_AB, DISK_AB);         //PCR B734160
      a = (ALSEC *)readbuf (sec, &hdr1);	 /* get a memory area */

      if ( a == NULL ) {

	  /*  Can't read the allocation sector.  */
	  /*  BUGBUG -- print a message?  */
	  return( 2 );
      }

      hdr1->cusHolds++;				/* hold this sector */
      hdr1->bDirtMask = TRUE;			/* it'll be changed */
      a->sig = ABSIGVAL;			/* initialize the ALSEC */
      a->lsnSelf = sec;
      a->lsnRent = cursec;
      a->alb.bFlag = (UCHAR)(ABF_FNP | (cblk->f.fst.alb.bFlag & ABF_NODE));
      a->alb.cFree = (UCHAR)(sizeof(ALLEAF) * LEAFPERSEC / size -
			     cblk->f.fst.alb.cUsed);
      a->alb.cUsed = cblk->f.fst.alb.cUsed;
      a->alb.oFree = sizeof (ALBLK) + a->alb.cUsed * size;
/*
 * We've initialized the ALSEC's header and ALBLK control structure.  Copy
 * all records from the FNODE array into the ALSEC's data area.
 */
      end = ((UCHAR *)&a->a);
      memmove (end, (UCHAR *)&cblk->f.fst.a, cblk->f.fst.alb.cUsed * size);
/*
 * Recalculate the insertion point for the new record, and insert the record
 * there.
 */
      ip = ((UCHAR *)&a->alb) + (ip - (UCHAR *)&cblk->f.fst.alb);
      chk_ab_makeroom ((union blk *)a, ip, size);
      memmove (ip, stuff, size);

      /*
       *  If the data we moved out of the FNODE were downpointers,
       *  then we have to update the childrens' parent pointers and
       *  'parent is an FNODE' flags.  Read each child in and fix it.
       *  If we can't read the child, we can't update it--this will
       *  leave an inconsistency (which could be fixed by running
       *  chkdsk again).
       *
       *  BUGBUG -- should we print a message if the update is not done?
       */
      if (a->alb.bFlag & ABF_NODE) {
	node = (ALNODE *)end;		 /* point to the first rec */
	for (i=0; i<a->alb.cUsed; i++, node++) {

	  block = (ALSEC *)readbuf (node->lsnPhys, &hdr2);

	  if ( block != NULL ) {

	      /*
	       *  Update the flag and the parent pointer
	       *  and mark the block as dirty.
	       */
	      block->alb.bFlag &= ~ABF_FNP;
	      block->lsnRent	= sec;
	      hdr2->bDirtMask	= TRUE;
	  }
	}
      }
/*
 * Finally, change the FNODE to contain a single node pointer to the
 * new ALSEC.
 */
      cblk->f.fst.alb.bFlag |= ABF_NODE;
      cblk->f.fst.alb.cFree  = NODEPERFNODE - 1;
      cblk->f.fst.alb.cUsed  = 1;
      cblk->f.fst.alb.oFree  = sizeof (ALBLK) + sizeof (ALNODE);
      (cblk->f.fst.a.aaln)->lsnLog  = 0xffffffff;
      (cblk->f.fst.a.aaln)->lsnPhys = sec;
/*
 * Set the FNODE dirty (the ALSEC was made so earlier), and we're done.
 * Always unhold the new ALSEC;	 only unhold the FNODE if it wasn't the
 * block we were originally called with, since the caller may wish to
 * keep scanning that block.
 */
      hdr1->cusHolds = 0;
      hdr2 = _adr_to_bhdr ((DIRBLK *)cblk);
      hdr2->bDirtMask = TRUE;
      if (cblk != tree)
	hdr2->cusHolds = 0;
      break;
    }
/*
 * Rats.  We have to split an allocation sector.  We divide the sector
 * in two pieces, insert our object into the correct half, and then
 * insert a downpointer to the new half into our parent block.	That
 * will take the form of simply looping up to the top again.
 */
    if (!(sec = allocate_near (cursec, SECTORS_PER_AB, SECTORS_PER_AB))) {
      chk_no_writing (CHK_NO_HOTFIX_SPACE_STR, NULL);
      return (2);
    }
    use_sectors (sec, (ULONG)SECTORS_PER_AB, DISK_AB);         //PCR B734160
    a = (ALSEC *)readbuf (sec, &hdr1);

    if ( a == NULL ) {

	/* BUGBUG -- print a message? */
	return( 2 );
    }

    a->sig = ABSIGVAL;
    a->lsnSelf = sec;
    a->lsnRent = cblk->a.lsnRent;
    a->alb.bFlag = cblk->a.alb.bFlag;
    a->alb.cUsed = cblk->a.alb.cUsed / 2;
    a->alb.cFree = (UCHAR)(sizeof(ALLEAF) * LEAFPERSEC / size - a->alb.cUsed);
    a->alb.oFree = sizeof (ALBLK) + a->alb.cUsed * size;
/*
 * We've initialized the new ALSEC's header and ALBLK control structure.  Find
 * the half-way mark in the old ALSEC's records, and move the second half into
 * the new ALSEC.
 *
 * "end" will point to the start of the new ALSEC's data area.  "half" will
 * point halfway into the old ALSEC's data area.
 */
    end = ((UCHAR *)&a->a);
    half = ((UCHAR *)&cblk->a.a) +
	   (cblk->a.alb.cUsed - a->alb.cUsed) * size;
    memmove (end, half, a->alb.cUsed * size);
    *(ULONG *)half = 0xffffffff;	/* store -1 in LOF for end mark */
    cblk->a.alb.cUsed -= a->alb.cUsed;
    cblk->a.alb.cFree += a->alb.cUsed;
    cblk->a.alb.oFree -= a->alb.cUsed * size;
/*
 * Now determine whether our new record is supposed to go in the first or
 * the second half.  If the latter, adjust the insertion point to point into
 * the new ALSEC at the correct place.	Make a hole in the correct ALSEC,
 * copy our record in, and un-hold/make dirty both of the ALSECs.
 */
    if (ip >= half) {
      block = a;
      ip = (UCHAR *)&a->alb + sizeof (ALBLK) + (ip - half);
    }
    else
      block = (ALSEC *)cblk;

    chk_ab_makeroom ((union blk *)block, ip, size);
    memmove (ip, stuff, size);

    hdr1->cusHolds = 0;
    hdr1->bDirtMask = TRUE;
    hdr2 = _adr_to_bhdr ((DIRBLK *)cblk);
    if (cblk != tree)
      hdr2->cusHolds = 0;
    hdr2->bDirtMask = TRUE;

/*
 * Now all we have to do is insert a new downpointer into our parent record.
 * That's fairly easy -- we just build one, find out where it goes in the
 * parent block, and loop back to the top of this routine.
 *
 * The LOF for the new downpointer is determined differently depending on
 * whether the child is a node or leaf block.  If a node block, we just copy
 * the LOF field from the last occupied ALNODE in the block, since node LOFs
 * indicate the LOF which is beyond all children of the node.  If it's a leaf
 * block, we take the last leaf's LOF and add its LEN, since a leaf's LOF is
 * the LOF of the BEGINNING of that leaf.
 *
 * We also need to fix the downpointer to our old ALSEC, since its LOF field
 * is now incorrect.  We determine the correct value in a similar fashion to
 * the other LOF, except we examine the old block.
 */
    ((ALNODE *)stuff)->lsnPhys = sec;
    p = end + (a->alb.cUsed-1) * size;
    p2 = (UCHAR *)cblk + FIELDOFFSET (ALSEC, alb.bFlag) +
	 sizeof (ALBLK) + (cblk->a.alb.cUsed-1) * size;
    if (a->alb.bFlag & ABF_NODE) {
      ((ALNODE *)stuff)->lsnLog = ((ALNODE *)p)->lsnLog;
      lof = ((ALNODE *)p2)->lsnLog;
    }
    else {
      ((ALNODE *)stuff)->lsnLog = ((ALLEAF *)p)->lsnLog +
					 ((ALLEAF *)p)->csecRun;
      lof = ((ALLEAF *)p2)->lsnLog + ((ALLEAF *)p2)->csecRun;
    }
    size = sizeof (ALNODE);
    cblk = (union blk *)readbuf (cblk->a.lsnRent, &hdr2);

    if( cblk == NULL ) {

	/*
	 *  If we can't read the parent, we certainly can't
	 *  insert a downpointer into it.  Give up.
	 */
	return(2);
    }

    hdr2->cusHolds++;
    ip = chk_find_ab_ip (cblk, ((ALNODE *)stuff)->lsnLog);
    ((ALNODE *)ip)->lsnLog = lof;
    ip += sizeof (ALNODE);	 /* insert after that record */
/*
 * If the node we're inserting will be the last one in that block, its
 * LOF must be -1, a special end marker.
 */
    if (ip == (UCHAR *)(&cblk->a.alb) + cblk->a.alb.oFree)
      ((ALNODE *)stuff)->lsnLog = 0xffffffff;
/*
 * Loop up to the top, and try to insert the new downpointer into the parent.
 */
  }

/*
 * All done.   Flush all our changes to the disk.  Since the caller may
 * want to keep an FNODE or ALSEC around in the cache, we don't wipe it.
 */
  flushcache ();
  return (rc);
}

/***	chk_fixup_leaf - reallocate runs referenced by a leaf
 *
 *	This function is called when a hotfix record needs cleaning and
 *	a leaf record in an FNODE or allocation block is found which
 *	references the bad sector in question.	The data will be reallocated
 *	elsewhere, and new leaf records may be inserted (depending on the
 *	length of the run containing the bad sector).
 *
 *	When the function returns, the "ret" parameter is filled in with
 *	a copy of the leaf record that contains the sectors to be replaced.
 *	This is done so that the caller can copy the replacement data into
 *	the newly allocated sectors.
 *
 *	chk_fixup_leaf (struc, leaf, tbl, idx, mask, ret, strucsec)
 *
 *	ENTRY		struc	 - pointer to the structure containing the leaf
 *			leaf	 - ALLEAF structure to check out
 *			tbl	 - pointer to the hotfix table
 *			idx	 - hotfix table entry we're looking for
 *			mask	 - address of a variable to set if sector fixed
 *			ret	 - leaf structure to fill with new run
 *			strucsec - where "struc" is on disk
 *
 *	EXIT		Returns 0 if a simple insertion was done,
 *				1 if the structure was split,
 *				2 if insufficient disk space.
 *			"ret" filled with new leaf structure -- only POF and
 *			  LEN are valid
 *
 *	CALLS		read_scratch
 *			chk_insert_into_tree
 *
 *	WARNINGS	None
 *
 *	EFFECTS		If bad sector found, inserts new allocation records
 *			Allocates disk space
 */
USHORT chk_fixup_leaf (struc, leaf, tbl, idx, mask, ret, strucsec)
  union blk *struc;
  ALLEAF *leaf;
  ULONG *tbl;
  USHORT idx;
  UCHAR *mask;
  ALLEAF *ret;
  ULONG strucsec;
{
  USHORT lead_sectors, trail_sectors, rc;
  ULONG sec, len;
  ALLEAF newrec, newrec2;

/*
 * Set flags to represent the position of the bad sector in this run.
 * "lead_sectors" is set TRUE if the run contains sectors before the
 * bad sector.	"trail_sectors" is set TRUE if the run contains sectors
 * after the bad one.
 */

  lead_sectors = (leaf->lsnPhys < tbl [idx]);
  trail_sectors = (leaf->lsnPhys + leaf->csecRun > tbl [idx] + 1);

/*
 * First, check for the easiest case:  the run consists of just one sector
 * (the bad one).  In this case, we simple allocate the sector elsewhere and
 * don't need to create any new runs.
 */
  if (!lead_sectors && !trail_sectors) {
    *mask = 0;			/* tell caller we fixed this entry */

    if (!(sec = allocate_near (leaf->lsnPhys, 1, 1))) {
      chk_no_writing (CHK_NO_HOTFIX_SPACE_STR, NULL);
      return (2);
    }

    if (chk_checking)
      use_sectors (sec, 1L, DISK_DATA);

    ret->lsnPhys = sec;
    ret->csecRun = 1L;
    leaf->lsnPhys = sec;
    return (0);			/* no split performed */
  }
/*
 * Next, check if the bad sector is on the end of the run.  If so, we
 * don't need to create a new trailing run;  we just change this run to
 * exclude the bad sector, and create a new run for the replaced sector.
 */
  else if (!trail_sectors) {
    *mask = 0;				/* tell caller we fixed this one */

    newrec.csecRun = 1L;		/* new run will be 1 sector */
    if (!(newrec.lsnPhys = allocate_near (tbl [idx], 1L, 1))) {
      chk_no_writing (CHK_NO_HOTFIX_SPACE_STR, NULL);
      return (2);
    }
    if (chk_checking)
      use_sectors (newrec.lsnPhys, 1L, DISK_DATA);
    newrec.lsnLog = leaf->lsnLog + leaf->csecRun - 1;	/* set its logical ofs */
    leaf->csecRun--;			/* old run is 1 sector shorter */
    ret->lsnPhys = newrec.lsnPhys;	/* return copy of new leaf */
    ret->csecRun = 1L;
    return (chk_insert_into_tree (struc, (UCHAR *)&newrec,
				  (UCHAR *)leaf+sizeof (ALLEAF),
				  sizeof (ALLEAF), strucsec));
  }
/*
 * Next, check if the bad sector is the start of the run.  If so, we
 * don't need to create a new leading run;  we just change this run to
 * reference the replaced sector, and make a new run for the rest of the
 * data.
 */
  else if (!lead_sectors) {
    *mask = 0;			/* tell caller we fixed this one */

    newrec.lsnPhys = leaf->lsnPhys + 1;	/* new record is old minus the first sec */
    newrec.csecRun = leaf->csecRun - 1;	/* it's one shorter */
    newrec.lsnLog = leaf->lsnLog + 1;	/* and one sector further into the file */
    leaf->csecRun = 1L;			/* make this leaf one sector */
    ret->csecRun = 1L;
    ret->lsnPhys = leaf->lsnPhys = allocate_near (tbl [idx], 1, 1);
    if (!ret->lsnPhys) {
      chk_no_writing (CHK_NO_HOTFIX_SPACE_STR, NULL);
      return (2);
    }
    if (chk_checking)
      use_sectors (leaf->lsnPhys, 1L, DISK_DATA);
    return (chk_insert_into_tree (struc, (UCHAR *)&newrec,
				  (UCHAR *)leaf+sizeof (ALLEAF),
				  sizeof (ALLEAF), strucsec));
  }
/*
 * In this case, the bad area is in the middle of the run, with good data
 * on both sides.  We truncate this run to reference just the sectors before
 * the bad area, and create two new runs:  one for the replaced sector, and
 * one for the data past the bad area.
 *
 * If the first new record caused a tree split, we would have to recalculate
 * the insertion point for the second record (which would make this routine
 * needlessly complex), so we first try just making one new record, containing
 * the bad sector and the good data after it.  If inserting that record
 * doesn't cause a split, we edit it and insert the second one.  Otherwise
 * we reset the bitmask and return a TRUE value, so that the caller will start
 * again from the top of the FNODE;  the second time through we will go through
 * the "!lead_sectors" case above, since we've already chopped off the leading
 * sectors.
 */
  else {
    *mask = 0;			/* assume the sector will be accounted for */

/*
 * First, edit the current run so that its length is just that of the
 * leading sectors.
 */
    len = leaf->csecRun;
    leaf->csecRun = tbl [idx] - leaf->lsnPhys;

/*
 * Now make a new run, containing the bad sector and the trailing sectors.
 */
    newrec.csecRun = len - leaf->csecRun;
    newrec.lsnPhys = tbl [idx];
    newrec.lsnLog = leaf->lsnLog + leaf->csecRun;

/*
 * Insert the first new record.  If we had to split, we'll need to re-find
 * the insertion point for the second new record.
 */
    if (rc=chk_insert_into_tree (struc, (UCHAR *)&newrec,
				 (UCHAR *)leaf+sizeof (ALLEAF),
				 sizeof (ALLEAF), strucsec)) {
      ret->csecRun = 0L;		/* didn't actually fix any data yet */
      *mask = 1;			/* make sure we keep looking */
      return (TRUE);			/* tell caller to start at the top */
    }

/*
 * Great.  The insert didn't cause a split -- we can insert the second
 * record easily.  Edit the one we inserted so that it just references
 * a replacement for the bad sectors, and insert a new record for the
 * trailing sectors.
 */
    leaf++;				/* point to the rec we inserted */
    len = leaf->csecRun;		/* save old length */
    leaf->csecRun = 1L;			/* replacement will be one sector */
    if (!(leaf->lsnPhys = allocate_near (tbl [idx], 1, 1))) {
      chk_no_writing (CHK_NO_HOTFIX_SPACE_STR, NULL);
      return (2);
    }
    if (chk_checking)
      use_sectors (leaf->lsnPhys, 1L, DISK_DATA);
    ret->lsnPhys = leaf->lsnPhys;	/* tell caller where to fix data to */
    ret->csecRun = 1L;

    newrec2.csecRun = len - 1L;		/* length of trailing sectors... */
    newrec2.lsnPhys = tbl [idx] + 1L;	/* starts right after bad sectors */
    newrec2.lsnLog = leaf->lsnLog + 1L;

    return (chk_insert_into_tree (struc, (UCHAR *)&newrec2,
				  (UCHAR *)leaf+sizeof (ALLEAF),
				  sizeof (ALLEAF), strucsec));
  }
}

/***	chk_fixup_node - reallocate runs referenced by a node
 *
 *	This function is called when a hotfix record needs cleaning and
 *	its FNODE referent contains allocation node pointers.  Fixup_node
 *	is called for each node pointer, to try to find the bad sector in
 *	one of the leaves.  This function may be recursive in the case of
 *	trees more than one level deep.
 *
 *	If the bad sector is eventually referenced by the specified node,
 *	the data is reallocated somewhere else, the leaf records are changed
 *	to point to the new location(s), and the bits corresponding to the
 *	fixed sectors are cleared in the bit mask.
 *
 *	chk_fixup_node (struc, node, tbl, first, last)
 *
 *	ENTRY		node  - ALNODE structure to check out
 *			tbl   - pointer to the hotfix table
 *			first - first hotfix table entry to examine
 *			last  - last hotfix table entry to examine
 *
 *	EXIT		Returns 0 if nothing happened or a simple insertion,
 *				1 if the tree had to be split,
 *				2 if insufficient disk space or read error
 *
 *	CALLS		read_scratch
 *			write_scratch
 *			insert_ab
 *
 *	WARNINGS	None
 *
 *	EFFECTS		If bad sector found, inserts new allocation records
 *			Allocates disk space
 */
USHORT chk_fixup_node (node, tbl, first, last)
  ALNODE *node;
  ULONG *tbl;
  USHORT first;
  USHORT last;
{
  ALNODE *curnode;
  ALLEAF *curleaf, leaf;
  register USHORT i, idx;
  USHORT rc;
  ALSEC *a;
  BUFNODE *hdr;
  UCHAR *tmp;

/*
 * First, read in the ALSEC and check what kind of records it contains.
 * If they're node pointers, recursively call for each one.
 */
  a = (ALSEC *)readbuf (node->lsnPhys, &hdr);	 /* read node */

  if ( a == NULL ) {

      /*  Read error  */
      return( 2 );
  }

  if ( a->alb.bFlag & ABF_NODE ) {


    /*
     *	It's a multilevel tree.  Recurse into the children.
     *	If one of the children fails, return the error
     *	(Caller restarts).
     */
    curnode = (ALNODE *)((UCHAR *)&a->alb + sizeof (ALBLK));
    for (i=0; i<a->alb.cUsed; i++, curnode++)
      if (rc=chk_fixup_node (curnode, tbl, first, last))
	return (rc);
  }
/*
 * This is the bottom level of the tree.  Check out each leaf;	if the leaf
 * contains one or more of the bad sectors, call chk_fixup_leaf to repair it.
 * If we have to split the tree, we have to start over from the top to make
 * sure we find all the bad sectors.
 */
  else {
    hdr->cusHolds++;
    curleaf = (ALLEAF *)((UCHAR *)&a->alb + sizeof (ALBLK));
    for (i=0; i<a->alb.cUsed; i++, curleaf++) {
      for (idx=first; idx<last; idx++) {
	if ((curleaf->lsnPhys <= tbl [idx]) &&
	    (curleaf->lsnPhys + curleaf->csecRun > tbl [idx])) {
	  rc=chk_fixup_leaf ((union blk *)a, curleaf, tbl, idx, &chk_hotfix_masks [idx], &leaf,
			     node->lsnPhys);
	  if (rc == 2) {			/* insufficient disk space? */
	    hdr->cusHolds--;			/* yes, get out immediately */
	    return (rc);
	  }
	  if (leaf.csecRun) {			/* did we fix anything */
	    if (tmp=chk_read_sectors (tbl [idx+spb.culMaxHotFixes],
				      (USHORT)leaf.csecRun))
	      chk_write_sectors (leaf.lsnPhys, tmp, (USHORT)leaf.csecRun);
	  }
	  if (rc) {				/* had to split */
	    hdr->cusHolds--;
	    return (rc);			/* stop doing leaves */
	  }
	}
      }
    }
    hdr->cusHolds--;
  }
  return (FALSE);
}

/***	chk_fixup_fnode - fix hotfixed runs in an FNODE
 *
 *	This function is called from validate_structure to fix data runs
 *	that have been hotfixed by the file system.  It is passed the sector
 *	number where the FNODE is on disk, and examines all allocation
 *	information for that FNODE.  Any data runs that overlap any hotfixed
 *	blocks are replaced, possibly splitting into two or more separate runs.
 *
 *	The last two parameters specify the range of entries in the hotfix
 *	table to check for.  Clean_hotfixes passes the same number for both
 *	parameters, so that only that entry is searched for (to save time).
 *	When validate_structure finds a file that contains one or more hotfixed
 *	records, it passes the limits of the hotfix table, so that all blocks
 *	that have been hotfixed will be cleaned up.
 *
 *	chk_fixup_fnode (sect, first, last)
 *
 *	ENTRY		sect  - where the FNODE is on disk
 *			first - first hotfix table entry to examine
 *			last  - last hotfix table entry to examine
 *
 *	EXIT		No return value
 *
 *	CALLS		?
 *
 *	WARNINGS	None
 *
 *	EFFECTS		Allocates disk space
 *			Uses filesystem-style cache
 */
void chk_fixup_fnode (sect, first, last)
  ULONG sect;
  USHORT first, last;
{
  ULONG *fnodes, *replacements, *tbl;
  USHORT i, j, rc=0;
  FNODE *f;
  ALLEAF leaf;
  union {
      UCHAR *p;
      ALLEAF *l;
      ALNODE *n;
  } alrec;

  UCHAR *tmp;
  BUFNODE *hdr;

  for (i=first; i<last; i++)		/* mark all entries as "not fixed" */
    chk_hotfix_masks [i] = 1;

  tbl = hotfix_tbl;
  fnodes = tbl + (spb.culMaxHotFixes * 2);	/* point to the array of FNODE numbers */
  replacements = tbl + spb.culMaxHotFixes;	/* point to the array of replacements */

  while (TRUE) {				/* loop until no split */
    f = (FNODE *)readbuf (sect, &hdr);

    if( f == NULL ) {

	/*  Can't read the fnode--no point in trying to clean it up.  */
	return;
    }

    hdr->cusHolds++;				/* hold the FNODE */
    alrec.p = (UCHAR *)&f->fst.a;	      /* point to first record */
    if (f->fst.alb.bFlag & ABF_NODE) {		  /* records are downpointers */
      for (j=0; j<f->fst.alb.cUsed; j++) {	  /* for all nodes */
	if (rc=chk_fixup_node (alrec.n, tbl, first, last))   /* fix this node */
	  break;				/* we split -- restart */
	alrec.n++;				/* go to next node (2 dwords) */
      }
      if (rc == 1) {				/* we had to split */
	hdr->cusHolds--;				/* unhold the FNODE */
	continue;				/* redo whole FNODE, keep mask */
      }
      else
	break;					/* error or no split, all done! */
    }
    else {					/* records are leaves (runs) */
      for (j=0; j<f->fst.alb.cUsed; j++) {	  /* for all runs */
	for (i=first; i<last; i++) {		/* for the requested range... */
	  if ((alrec.l->lsnPhys <= tbl [i]) &&	 /* POF < replacement end */
	      (alrec.l->lsnPhys + alrec.l->csecRun > tbl [i])) {	/* POF+LEN > replacement start */
	    rc=chk_fixup_leaf ((union blk *)f, alrec.l, tbl, i, &chk_hotfix_masks [i], &leaf, sect);
	    if (leaf.csecRun) {			/* did we fix anything */
	      if (tmp=chk_read_sectors (replacements [i], (USHORT)leaf.csecRun))
		chk_write_sectors (leaf.lsnPhys, tmp, (USHORT)leaf.csecRun);
	    }
	    if (rc)				/* had to split */
	      break;				/* stop doing leaves */
	  }
	  else					/* not referenced, so no split */
	    rc = 0;
	}
	if (rc == 1)				/* had to split */
	  break;
	alrec.l++;				/* go to next LEAF (3 dwords) */
      }
      if (rc == 1) {				/* had to split */
	hdr->cusHolds--;				/* unhold the FNODE */
	continue;				/* re-process FNODE as nodes */
      }
      else
	break;					/* error or no split, all done! */
    }
  }

  rc = FALSE;				/* set TRUE if table should be saved */

  for (i=first; i<last; ) {
    if (chk_hotfix_masks [i])
      i++;
    else {
      chk_no_writing (CHK_HOTFIX_FIXED_STR, NULL);
      make_bad (tbl [i]);			/* mark bad sector in bad list */
      hdr->bDirtMask = TRUE;			/* fixed something - fn's dirty */
      rc = TRUE;
      last--;					/* adjust end record number */
      spb.culHotFixes--;				/* decrement record count */
      j = (USHORT)((spb.culMaxHotFixes - (i + 1)) * sizeof (ULONG));
      sect = replacements [i];			/* save replacement sector # */
      memmove (&tbl [i], &tbl [i+1], j);	/* remove that record */
      memmove (&fnodes [i], &fnodes [i+1], j);
      memmove (&replacements [i], &replacements [i+1], j);
      memmove (&chk_hotfix_masks [i], &chk_hotfix_masks [i+1],
	       j / sizeof (ULONG) * sizeof (chk_hotfix_masks [0]));
      replacements [spb.culMaxHotFixes - 1] = sect;	/* re-use sector number */
    }
  }
  if (rc) {
    write_scratch (spb.lsnHotFix, tbl, SPB);
    write_scratch ((ULONG)SEC_SPAREB, &spb, 1);
  }

  hdr->cusHolds = 0;
  wipecache ();
}

/***	chk_bad2replace - find the replacement for a sector in the hotfix table
 *
 *	This function is called by the hotfix cleanup routines to find
 *	the sector that a defective sector has been mapped to.	It looks
 *	through the hotfix table for a bad sector equal to the desired
 *	sector.  It then returns the corresponding replacement sector,
 *	where the desired data can be found.  If the requested sector
 *	has not been hotfixed, the sector number is passed back unchanged.
 *
 *	chk_bad2replace (bad, tbl, nhot)
 *
 *	ENTRY		bad  - sector number to look for
 *			tbl  - pointer to the hotfix table
 *			nhot - number of hotfix entries to look through
 *
 *	EXIT		Returns replacement sector, or ==bad if not found
 *
 *	CALLS		None
 *
 *	WARNINGS	None
 *
 *	EFFECTS		None
 */
ULONG chk_bad2replace (bad, tbl, nhot)
  ULONG bad;
  ULONG *tbl;
  USHORT nhot;
{
  USHORT i;

  for (i=0; i<nhot; i++) {
    if (tbl [i] == bad)
      return (tbl [i+nhot]);
  }
  return (bad);
}

/***	chk_clean_hotfixes - clean up after file system's hotfixing
 *
 *	This function is called when some of the file system's replacement
 *	sectors are in use.  This means that one or more files contained
 *	defective sectors and had to be temporarily reallocated.  This
 *	function finds the files that use the hotfix sectors, reallocates
 *	the run(s) containing replacement sectors, and returns the replacements
 *	to the free hotfix list.
 *
 *	The hotfix table contains the FNODE numbers of the files which
 *	use replacement sectors.  However, since replacements occur on
 *	objects other than data runs, this FNODE number may not be present
 *	or may be invalid.  If the FNODE recorded does not account for the
 *	sector in question, it will be hotfixed later, when the file system
 *	is checked.
 *
 *	chk_clean_hotfixes (s, tbl)
 *
 *	ENTRY		s   - pointer to memory image of the super block
 *			tbl - pointer to memory image of the hotfix table
 *
 *	EXIT		No return value
 *
 *	CALLS		hotfix
 *			read_scratch
 *			write_scratch
 *
 *	WARNINGS	None
 *
 *	EFFECTS		Sets global variable "find_hot" if not all replacements
 *			accounted for
 */
void chk_clean_hotfixes (s, tbl)
  SPAREB *s;
  ULONG *tbl;
{
  ULONG fnsec;
  USHORT i;
  FNODE *f;
  BUFNODE *hdr;

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

  for (i=0; i < (USHORT)s->culHotFixes; ) {	 /* process each used hotfix record */
    use_sectors (tbl [i], 1L, DISK_FIXED);
    fnsec = chk_bad2replace (tbl [i+spb.culMaxHotFixes*2], tbl, (USHORT)s->culHotFixes);
    f = (FNODE *)readbuf (fnsec, &hdr);		 /* read the FNODE */
    if ( (f == NULL) || (f->sig != FNSIGVAL) ) {

      /*
       *  This sector is unreadable, or it's not an FNODE.
       *  Set the hotfix mask entry to 1 (not fixed) and
       *  go onto the next entry without checking this FNODE.
       */
      chk_hotfix_masks [i] = 1;
      i++;
      continue;
    }

    chk_fixup_fnode (fnsec, i, i+1);		/* fix up this FNODE */
  }

  if ((fnsec=chk_write_data (s->lsnHotFix, tbl, SPB, FALSE)) != s->lsnHotFix)
    s->lsnHotFix = fnsec;

  write_scratch ((ULONG)SEC_SPAREB, s, 1);

  chk_checking = TRUE;			/* done with preliminary cleaning */
}

/***	chk_verify_hfmax - verify that culMaxHotFixes is correct
 *
 *	This function is called if culMaxHotFixes is not equal to what
 *	FORMAT sets it to (1% of disk space, up to a maximum of
 *	100 sectors).  We use the hotfix table itself to make sure
 *	that culMaxHotFixes is correct.
 *
 * culMaxHotFixes is determined by finding the beginning of the
 *	second array in the hotfix table (the hotfix replacement
 *	sectors).  In most cases this array will begin after a
 *	series of null sector numbers (unused entries in the bad
 *	sector list).  In the rare case where all hotfix entries
 *	are in use, we take the maximum value for culMaxHotFixes (the
 *	number of entries which would cause the hotfix table to
 *	completely fill a cache block) and scan backwards until
 *	we find an unreadable sector.  That must be the end of the
 *	first array.
 *
 *	If culMaxHotFixes is found to be incorrect, it is reset to the
 *	correct value and, command line parameters permitting, the
 *	updated spareblock is saved to the disk.
 *
 *	chk_verify_hfmax (void)
 *
 *	ENTRY		No parameters
 *
 *	EXIT		No return value
 *
 *	CALLS		read_scratch
 *			write_scratch
 *
 *	WARNINGS	Assumes that spb and hotfix_tbl have been read
 *
 *	EFFECTS		Modifies spareblock
 */
void chk_verify_hfmax (void)
{
  ULONG *p;

  for (p=hotfix_tbl;
       *p && (p < hotfix_tbl + (SPB * SECSIZE) / 12);
       p++)
    ;

  if (*p) {
    for (; (p != hotfix_tbl) && read_scratch (*p, scratchbuf, 1); p--)
      ;
    p++;
  }
  else {

    /*
     *	p now points at the first null in first array
     *	in the HotFix sector.  Scan forward until we
     *	have find a non-zero entry (the first replacement
     *	sector) or have gone too far.
     */
    for (; !*p && (p < hotfix_tbl + (SPB * SECSIZE) / 12) ; p++)
      ;

    if ( !*p ) {

    }
  }

  /*
   *  If we found the first replacement LSN, p now points at it.
   *  If p is pointing at a null, we don't have any replacement
   *  sectors, so we'll set culMaxHotFixes to some reasonable number.
   *  The caller will have to allocate new replacement sectors.
   */
  if ( !*p ) {
       if ((ULONG)(p - hotfix_tbl) != spb.culMaxHotFixes) {
	 spb.culMaxHotFixes = p - hotfix_tbl;
	 if (!chk_no_writing (CHK_BAD_HFMAX_STR, NULL))
	   write_scratch ((ULONG)SEC_SPAREB, &spb, 1);
       }

  } else {

    spb.culMaxHotFixes = ((number_of_sectors > 40000L) ?
				  100L :
				  number_of_sectors / 400L);
    if (!chk_no_writing (CHK_BAD_HFMAX_STR, NULL))
      write_scratch ((ULONG)SEC_SPAREB, &spb, 1);
  }
}
