/*static char *SCCSID = "@(#)save.c	6.2 92/02/19";*/
/*static char *SCCSID = "@(#)save.c	6.2 92/02/19";*/
/***	SAVE.C - Routines to save recovered file system structures.
 *
 *	CHKDSK
 *	Gregory A. Jones
 *	Copyright 1988 Microsoft Corporation
 *
 *	Modification history:
 *	G.A. Jones	10/12/88	Removed from RECOVER.C.
 *	P.A. Williams	06/08/89	Initialized new fields fFlex
 *					and bCodePage in dirents, usACLBase
 *					and ulRefCount in fnodes.
 *					chk_save_structures
 *	P.A. Williams	06/22/89	Removed uninitialized ref to dp.d in
 *	P.A. Williams	07/11/89	The cchThisEntry for the FOUND.xxx dir
 *					was set 4 bytes too big.
 *	P.A. Williams	08/10/89	Make sure that the FN_VLEN parameter
 *					is getting set correctly when creating
 *					fnodes.
 *	W.lsnMain. McJohn	10/2/89		Scan recovered directories to
 *					ensure they're well-ordered
 */

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


/***	chk_write_bitmaps -- write bitmaps to disk
 *
 *	This function is called to write the bitmap to disk.  It is passed
 *	a pointer to the map;  that memory image is used for both copies
 *	of the bit map.  The existing bitmap indirect lists are used.
 *
 *	If the disk addresses of the indirect blocks themselves or
 *	any of the bitmap blocks are unwritable, new sectors are
 *	allocated and the appropriate structures (superblock or
 *	indirect block) are updated.
 *
 *	This function also writes db_bitmap to sector sb.lsnDirBlkMap.
 *
 *	chk_write_bitmaps (map)
 *
 *	ENTRY		map - pointer to memory image of bit map
 *
 *	EXIT		No return value
 *
 *	CALLS		allocate_early_sectors
 *			allocate_middle_sectors
 *			chk_exit_error
 *			read_scratch
 *			write_scratch
 *
 *	EFFECTS		Allocates and deallocates memory
 *			Updates bit maps on disk
 */
void chk_write_bitmaps (map)
  UCHAR huge *map;
{
  ULONG *scratch;
  UCHAR huge *p;
  USHORT i, update_indirect=0;
  ULONG sec;

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

  read_scratch ((ULONG)SEC_SUPERB, &sb, 1);

  if ((scratch=ALLOCATE_BLOCK (SPB)) == NULL)
    chk_exit_error (INSF_MEM_ERROR);

/*
 * Read the primary bitmap indirect block.  If we can't read it,
 * allocate new disk space until we can write it, and update the
 * superblock accordingly.
 */

  if (read_scratch (sb.rspBitMapIndBlk.lsnMain, scratch, SPB)) {
    if (!(sb.rspBitMapIndBlk.lsnMain = chk_write_data (number_of_sectors / 2, scratch, SPB, TRUE)))
      chk_exit_error (INSF_DISK_ERROR);
    write_scratch ((ULONG)SEC_SUPERB, &sb, 1);	/* save new superblock */
  }

/*
 * Save the bitmap blocks according to the bitmap indirect block.
 * If there are any bad sectors, relocate the bitmap blocks.  Since
 * there could be several bad blocks, we'll only save the indirect
 * block after the whole bitmap is written.
 */

/*
 * BUGBUG - make sure that our hotfixing doesn't invalidate
 * the bitmaps we're writing!
 */

  p = map;
  for (i=0; (i < (SPB*SECSIZE)/4) && scratch [i]; i++) {
    if ((sec=chk_write_data (scratch [i], p, SPB, FALSE)) != scratch [i]) {
      scratch [i] = sec;
      update_indirect = TRUE;
    }
    p += SPB * SECSIZE;
  }
  if (update_indirect)
    write_scratch (sb.rspBitMapIndBlk.lsnMain, scratch, SPB);

  FREE_BLOCK (scratch);

  if ((sec=chk_write_data (sb.lsnDirBlkMap, db_bitmap, SPB, FALSE)) !=	sb.lsnDirBlkMap) {
    sb.lsnDirBlkMap = sec;
    write_scratch ((ULONG)SEC_SUPERB, &sb, 1);
  }
}

USHORT chk_level = 0;

/***	chk_dump_lost - dump contents of a lost structure tree
 *
 *	This function displays the contents of a lost structure tree.
 *	For each node along the "next" list of the node, it displays
 *	a message indicating the block's type, and descends that block's
 *	child list recursively.
 *
 *	This function is necessary even in non-debug builds to make sure
 *	that all edits to recovered data get saved to disk.  The display
 *	code is only enabled #ifdef DEBUG, though.
 *
 *	chk_dump_lost (mem)
 *
 *	ENTRY		mem - pointer to node to dump
 *
 *	EXIT		No return value
 *
 *	CALLS		fprintf
 */
void chk_dump_lost (mem)
   mem_blk *mem;
{
   mem_blk *p;

  chk_level += 2;
  for (p=mem; p; p=p->next) {
    if (p->psn)
      write_scratch (p->psn, &p->blk, (p->blk.d.sig == DBSIGVAL) ?
		     SECTORS_PER_DIRBLK : (p->blk.d.sig == FNSIGVAL) ?
		     SECTORS_PER_FNODE : SECTORS_PER_AB);
#ifdef DEBUG
    printf ("%-*s", chk_level, " ");
    if (p->blk.d.sig == DBSIGVAL)
      printf ("DIRBLK ");
    else if (p->blk.d.sig == FNSIGVAL)
      printf ("FNODE  ");
    else
      printf ("AB     ");
    printf ("at sector %08lx\n", p->psn);
#endif
    if (p->childlist)
      chk_dump_lost (p->childlist);
  }
  chk_level -= 2;
}

/***	chk_make_fnode -- build an FNODE for recovering a DIRBLK or ALSEC
 *
 *	This function is called to build an FNODE to recover a data
 *	item which needs one.  The FNODE is filled in according to
 *	the last parameter, which describes the purpose for the FNODE.
 *
 *	The new FNODE will be placed as close to the recovered data
 *	as possible.
 *
 *	chk_make_fnode (mem, sec, len, contfn, type, pbFileSize)
 *
 *	ENTRY		mem    - reconstruction-tree node of child
 *			sec    - where the recovered object is on disk
 *			contfn - containing subdirectory's FNODE number
 *			type   - what type of data is being recovered
 *			pbFileSize - returns size of recovered file
 *				     (only computed if mem is an
 *				      orphaned allocation sector.)
 *
 *	EXIT		Returns sector number of FNODE, 0L if no space
 *
 *	CALLS		allocate_near
 *			write_scratch
 *
 *	WARNINGS	Writes to disk
 *
 *	EFFECTS		Allocates disk space in bitmap
 */
ULONG chk_make_fnode (mem, sec, contfn, type, pbFileSize)
	 mem_blk *mem;
	ULONG sec;
	ULONG contfn;
	USHORT type;
	PULONG pbFileSize;
{
	ULONG fnsec;
	FNODE fn;	/* on the stack since we may have exhausted the heap */
 PFNODE f=&fn;

	memset ((char *)f, '\0', sizeof ( FNODE));
	f->sig	   = FNSIGVAL;
	f->lsnContDir  = contfn;
	f->usACLBase = FIELDOFFSET( FNODE, abFree[0]);
	f->ulRefCount  = 0L;
	f->fst.alb.cUsed = 1;
	if (type == DISK_DIRBLK) {
		f->bFlag = FNF_DIR;
		f->fst.alb.cFree = LEAFPERFNODE - 1;
		f->fst.alb.oFree = sizeof (ALBLK) + sizeof ( ALLEAF);
		f->fst.a.aall [0].lsnPhys = sec;
	}
	else {
		f->fst.alb.bFlag = ABF_NODE;
		f->fst.alb.cFree = NODEPERFNODE - 1;
		f->fst.alb.oFree = sizeof ( ALBLK) + sizeof ( ALNODE);
		f->fst.a.aaln[0].lsnLog	 = 0xffffffff;
		f->fst.a.aaln[0].lsnPhys = sec;
	}

	if (type == DISK_DIRBLK) {
	    f->bFlag = FNF_DIR;
	    f->fst.alb.cFree = LEAFPERFNODE - 1;
	    f->fst.alb.oFree = sizeof (ALBLK) + sizeof (ALLEAF);
	    f->fst.a.aall [0].lsnPhys = sec;
	}
	else { /* DISK_AB */
	    f->fst.alb.bFlag = ABF_NODE;
	    f->fst.alb.cFree = NODEPERFNODE - 1;
	    f->fst.alb.oFree = sizeof (ALBLK) + sizeof (ALNODE);
	    f->fst.a.aaln[0].lsnLog  = 0xffffffff;
	    f->fst.a.aaln[0].lsnPhys = sec;

	    f->fst.ulVLen = chk_calc_file_size (mem) * (ULONG)SECSIZE;
	    *pbFileSize = f->fst.ulVLen;
	}

	if (!(fnsec = allocate_near (sec, SECTORS_PER_FNODE, 1)))
		return (0L);

	use_sectors (fnsec, (ULONG)SECTORS_PER_FNODE, DISK_SUBDIR);
	write_scratch (fnsec, f, SECTORS_PER_FNODE);
	return (fnsec);
}

/***	chk_consistent_db -- make a subdirectory consistent
 *
 *	This function is called when recovering a DIRBLK.  Since a new
 *	FNODE is allocated to point to the DIRBLK, and in all likelihood
 *	its location will be different than the old FNODE, all files
 *	contained in this DIRBLK have incorrect lsnContDir pointers.
 *	We have to recursively traverse the memory tree, fixing the
 *	pointers for all the FNODEs.  However, we fix the FNODEs for
 *	subdirectories but do not recurse into them;  since those sub-
 *	directories will be recovered entirely, their parent pointers
 *	are correct.
 *
 *	We will use the memory images in the childlist to update the
 *	disk, thus removing the necessity of allocating and deallocating
 *	memory for the FNODEs.
 *
 *	chk_consistent_db (mem, contfn)
 *
 *	ENTRY		mem    - mem_blk containing DIRBLK pointing to files
 *			contfn - correct lsnContDir pointer
 *
 *	EXIT		No return value
 *
 *	CALLS		write_scratch
 *			chk_consistent_db (recursive)
 *
 *	WARNINGS	None
 *
 *	EFFECTS		Modifies disk, lost memory tree
 */
void chk_consistent_db (mem, contfn)
   mem_blk *mem;
  ULONG contfn;
{
   mem_blk *p;

  for (p=mem->childlist; p; p=p->next) {
    if (p->blk.d.sig == DBSIGVAL)
      chk_consistent_db (p, contfn);
    else if (p->blk.d.sig == FNSIGVAL) {
      p->blk.f.lsnContDir = contfn;
      write_scratch (p->psn, &p->blk, SECTORS_PER_FNODE);
    }
  }
}

/***	chk_calc_file_size -- calculate file size
 *
 *	This function calculates the total size of a file's data.
 *	It does so by finding the last ALLEAF record in the file and
 *	adding that leaf's LOF and length.
 *
 *	The parameter to this function may be an FNODE or an allocation
 *	sector.  The signature is used to determine the difference.
 *
 *	Any ALNODEs required are assumed to be under the passed block's
 *	childlist.
 *
 *	chk_calc_file_size (p)
 *
 *	ENTRY		p - pointer to root mem_blk of allocation tree
 *
 *	EXIT		Returns data size in sectors
 *
 *	CALLS		None
 *
 *	WARNINGS	None
 *
 *	EFFECTS		None
 */
ULONG chk_calc_file_size (p)
   mem_blk *p;
{
   mem_blk *child;
  USHORT i;
 PALNODE node;
 PALLEAF leaf;

/*
 * First check simple cases:  the block passed contains ALLEAF records.
 * In such a case we simply find the last ALLEAF and calculate from it.
 * If the block contains ALNODE records, we point "node" at the last
 * ALNODE in the block.
 */

  if (p->blk.f.sig == FNSIGVAL) {
    if (!(p->blk.f.fst.alb.bFlag & ABF_NODE)) {
      i = p->blk.f.fst.alb.cUsed - 1;
      return (p->blk.f.fst.a.aall[i].lsnLog + p->blk.f.fst.a.aall[i].csecRun);
    }
    else
      node = &p->blk.f.fst.a.aaln[p->blk.f.fst.alb.cUsed - 1];
  }
  else {
    if (!(p->blk.a.alb.bFlag & ABF_NODE)) {
      i = p->blk.a.alb.cUsed - 1;
      leaf = (( ALLEAF *)AB_START (&p->blk)) + i;
      return (leaf->lsnLog + leaf->csecRun);
    }
    else
      node = ((PALNODE)AB_START (&p->blk)) + p->blk.a.alb.cUsed - 1;
  }
  child = p;

/*
 * In the following loop, we first point "child" at its own descendant
 * list, and search for the mem_blk that has the same sector as the ALNODE
 * we want.  If that descendant is a node block, we point "node" at the
 * last ALNODE in the block and keep looking, otherwise we stop looking
 * and calculate the file size from the last ALLEAF.
 */
  while (TRUE) {
    for (child=child->childlist; child && (child->psn != node->lsnPhys);
	 child=child->next)
      ;
    if (!child)				/* no child found */
      return (0L);			/* let next CHKDSK fix it */
    if (child->blk.a.alb.bFlag & ABF_NODE)
      node = ((PALNODE)AB_START (&child->blk)) +
	     child->blk.a.alb.cUsed - 1;
    else				/* found a leaf block */
      break;				/* stop traversing */
  }
  leaf = ((PALLEAF)AB_START (&child->blk)) +
	 child->blk.a.alb.cUsed - 1;
  return (leaf->lsnLog + leaf->csecRun);
}



/*
 ***	chk_badly_ordered -- see if a recovered directory is badly ordered
 *
 *
 *	This function is called after a directory has been reconstructed
 *	from an orphaned DIRBLK.  It traverses the directory tree rooted
 *	at lsn, testing to see that it is ordered.  It also recursively
 *	checks all subdirectories of the subtree, sorting them if
 *	necessary.
 *
 *	Note that, since it must check subdirectories,
 *	chk_badly_ordered cannot simply stop when it
 *	discovers that the directory is indeed badly ordered.
 *
 *	ENTRY lsn = lsn of root of sub-tree to check
 *
 *	      pdePrev = pointer to _copy_ of last dirent
 *			preceding this subtree.  (Initialized
 *			to a DIRENT with cchThisEntry == 0.)
 *
 *	      *pfSeenDotDot is TRUE iff we've already seen the
 *			'..' entry for this directory.
 *
 *
 *	RETURNS TRUE if directory is badly ordered, FALSE if
 *	    names are well-ordered.
 *
 *
 */
/*  Size of local variables for chk_badly_ordered  */
#define BADLY_ORDERED_STACK 32

BOOL
chk_badly_ordered( ULONG lsn, PCHAR pszPrevName, BOOL * pfSeenDotDot )
{

 PDIRBLK pdb;	/*  pointer to DIRBLK being checked */
 PDIRENT pdeCur;	/*  pointer to current dirent	    */
    PCHAR pszBuf;	/*  pde buffer to check children    */
 PFNODE pfn;	/*  ptr to child's FNODE            */
    BOOL fHaveBTP;	/*  TRUE iff first entry has BTP    */
    BOOL retcode;
    BOOL fChild;	/*  Used for recursion		    */


    if (chk_enter_recursive (BADLY_ORDERED_STACK)) {

	/*
	 *  We're too low on stack space to risk continuing;
	 *  display a message and assume that everything from
	 *  here down is OK--i.e. that it's not badly ordered.
	 */
	CHK_ERROR_MSG( CHK_INSF_MEM_CONTINUING_STR);
	chk_exit_recursive (BADLY_ORDERED_STACK);
	return (FALSE);
    }



    /*
     *	The hypothesis we will test is that the
     *	directory is not badly ordered.
     */
    retcode = FALSE;


    /*
     *	Allocate a block and read the lsn into it.
     */
    pdb = malloc( sizeof( DIRBLK ) );

    if( pdb == NULL ) {

	/*
	 *  Well, we're out of memory, so we'll
	 *  just assume that the subtree isn't
	 *  badly-ordered.
	 */
	CHK_ERROR_MSG( CHK_INSF_MEM_CONTINUING_STR);
	chk_exit_recursive (BADLY_ORDERED_STACK);
	return( FALSE );
    }

    if( read_scratch( lsn, pdb, SECTORS_PER_DIRBLK ) != 0 ) {

	/*
	 *  Ouch, couldn't read the DIRBLK--this means
	 *  there's a problem; let's say it's badly
	 *  ordered and let chk_resort_directory fix it.
	 */
	free( pdb );
	chk_exit_recursive (BADLY_ORDERED_STACK);
	return( TRUE );
    }

    if( pdb->sig != DBSIGVAL ) {

	/*
	 *  The sector isn't even a DIRBLK--much
	 *  less a well-ordered DIRBLK.
	 */
	free( pdb );
	chk_exit_recursive (BADLY_ORDERED_STACK);
	return( TRUE );
    }


    /*
     *	Get a pointer to the first DIRENT and initialize
     *	fHaveBTP on the basis of that dirent.
     */
    pdeCur = (PDIRENT)DIR_START( *pdb );


    if( pdeCur->fFlags & DF_BTP ) {
	fHaveBTP = TRUE;
    } else {
	fHaveBTP = FALSE;
    }


    while( TRUE ) {

	/*
	 *  Do a quick sanity check on the length of
	 *  the DIRENT, to save ourselves some grief later.
	 *  This should be unneccessary--this DIRBLK passed
	 *  chk_gather_structure--but it's easy to do...
	 */

	if ( (pdeCur->cchThisEntry == 0) ||
	     (pdeCur->cchThisEntry > MAX_DIRENT) ) {

	    /*
	     *	This dirent is screwed up--the
	     *	directory cannot be well-ordered.
	     *	In fact, this dirent is so screwed
	     *	up, we can't even reasonably continue
	     *	checking subdirectories, so free
	     *	the work area and return TRUE.
	     */
	    free( pdb );
	    chk_exit_recursive (BADLY_ORDERED_STACK);
	    return( TRUE );

	}


	if( (pdeCur->cchName == 2) &&
	    (memcmp(pdeCur->bName, "\001\001", 2) == 0) ) {

	    /*
	     *	This is the '..' entry, which must be the
	     *	first entry in the directory.  This means
	     *	that we should not have	a previous dirent,
	     *	and that the current dirent should not have
	     *	a down pointer.
	     *
	     *	Other forbidden things are that _any_ entry
	     *	in this DIRBLK has a down pointer, or that
	     *	this entry also thinks it's the end entry.
	     */
	    *pfSeenDotDot = TRUE;
	    if( (pdeCur->fFlags & DF_BTP) ||
		(pdeCur->fFlags & DF_END) ||
		( fHaveBTP ) ||
		(pszPrevName[0] != '\0') ) {

		/*
		 *  The directory is badly ordered.
		 */
		retcode = TRUE;
	    }

	    /*
	     *	That's all we need to check for '..'--
	     *	Go to the next dirent.
	     */
	    pdeCur = (PDIRENT)( (PCHAR)pdeCur + pdeCur->cchThisEntry );
	    continue;
	}


	if( pdeCur->fFlags & DF_BTP ) {

	    /*
	     *	This entry has a down-pointer.	If the
	     *	first entry didn't, the directory is
	     *	not well-formed.
	     *
	     *	If it's OK that it has a down-pointer,
	     *	recurse into the child.  If the subtree
	     *	is badly ordered, then (obviously) the
	     *	current tree is badly ordered.
	     */

	    if( (!fHaveBTP) ||
		chk_badly_ordered(BTP(pdeCur),
				  pszPrevName,
				  pfSeenDotDot) ) {


		retcode = TRUE;
	    }

	} else if( fHaveBTP ) {

	    /*
	     *	This entry does not have a down-pointer,
	     *	but the first entry in the block did.
	     *	The directory tree is not well-formed.
	     */
	    retcode = TRUE;
	}

	if( pdeCur->fFlags & DF_END ) {

	    /*
	     *	Finished processing this DIRLBK.
	     *
	     */
	    free( pdb );
	    chk_exit_recursive (BADLY_ORDERED_STACK);
	    return retcode;
	}



	/*
	 *  Compare the current DIRENT's name with
	 *  the name of the previous DIRENT (if we
	 *  have one)
	 */
	if( pszPrevName[0] != '\0' ) {

	    if( chk_strnicmp( pdeCur->bName, pdeCur->bCodePage,
			      pszPrevName, PREMAPPED,
			      pdeCur->cchName ) <= 0 ) {

		/*
		 *  The current name is not greater than
		 *  the previous name--the directory is
		 *  badly ordered.
		 */
		retcode = TRUE;
	    }

	} else {

	    if( !*pfSeenDotDot ) {

		/*
		 *  We haven't seen the ".." entry yet,
		 *  so either it doesn't exist or it isn't
		 *  the first entry.  In either case, the
		 *  directory is badly ordered!
		 */
		retcode = TRUE;
	    }
	}


	if ( pdeCur->fAttr & ATTR_DIRECTORY) {

	    /*
	     *	The current DIRENT represents a
	     *	subdirectory.  We need to check to
	     *	see if that subdirectory is badly ordered.
	     */
	    pfn = malloc( sizeof( FNODE ) );

	    if( pfn != NULL ) {

		if( (read_scratch( pdeCur->lsnFNode,
				   pfn,
				   SECTORS_PER_FNODE ) == 0) ||
		    (pfn->sig == FNSIGVAL) ||
		    (pfn->bFlag & FNF_DIR) ) {


		    /*
		     *	OK, we read the FNODE, and it
		     *	is indeed the FNODE of a subdirectory,
		     *	so let's recurse into that subdirectory.
		     */
		    pszBuf = malloc( MAX_DIRENT );

		    if( pszBuf != NULL ) {

			pszBuf[0] = '\0';
			fChild = FALSE;

			if( chk_badly_ordered( pfn->fst.a.aall[0].lsnPhys,
					       pszBuf,
					       &fChild ) ) {

			    /*
			     *	The recovered directory is not
			     *	lexicographically sorted.  Resort it.
			     *	Note that chk_sort_directory will
			     *	silently fail if the object to be sorted
			     *	is not in fact a directory.
			     */
			    chk_sort_directory( pdeCur->lsnFNode, NULL );

			}

			free( pszBuf );
		    } /* pszBuf != NULL */
		} /*  successfully read FNODE  */

		free( pfn );

	    }  /*  pfn != NULL */
	}


	/*
	 *  Copy and upcase the name of the current DIRENT
	 *  for comparison against the next DIRENT.
	 */
	memcpy( pszPrevName, pdeCur->bName, pdeCur->cchName );
	pszPrevName[pdeCur->cchName] = '\0';

	chk_strnupr(pszPrevName, pdeCur->bCodePage, pdeCur->cchName);


	/*
	 *  Go on to the next DIRENT.  Since
	 *  this DIRBLK passed chk_recover_structure,
	 *  we don't need to worry about falling
	 *  off the end of the DIRBLK--but we
	 *  check for it anyway.
	 */
	pdeCur = (PDIRENT)( (PCHAR)pdeCur + pdeCur->cchThisEntry );

	if( (PCHAR)pdeCur - (PCHAR)pdb > sizeof( DIRBLK ) ) {

	    /*	Fell off the end.  */
	    free( pdb );
	    chk_exit_recursive (BADLY_ORDERED_STACK);
	    return( TRUE );
	}
    } /* while */
}


/*
 ***	chk_traverse_alloc_tree -- check and fix an allocation tree's LOF's
 *
 *	ENTRY	mem -- memory node for allocation sector
 *		pclsn -- ptr to ordinal value of first
 *			     file logical sector number in
 *			     this allocation tree.
 */
#define TRAVERSE_ALLOC_STACK 24

void
chk_traverse_alloc_tree ( mem_blk *mem, PULONG pclsn )
{

     mem_blk *pmemChild;
 PALLEAF pall;	/*  ptr to traverse leaf block	*/
 PALNODE paln;	/*  ptr to traverse node block	*/
    int i;		/*  Generic index		*/
    BOOL fChanged = FALSE;


    if (chk_enter_recursive (TRAVERSE_ALLOC_STACK)) {

	/*
	 *  We're too low on stack space to risk continuing;
	 *  display a message and assume that everything from
	 *  here down is OK--i.e. that it's not badly ordered.
	 */
	CHK_ERROR_MSG( CHK_INSF_MEM_CONTINUING_STR);
	chk_exit_recursive (TRAVERSE_ALLOC_STACK);
	return;
    }




    if( mem->blk.a.sig != ABSIGVAL ) {

	chk_exit_recursive (TRAVERSE_ALLOC_STACK);
	return;
    }

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


	/*
	 *  The entries are pointers to other allocation
	 *  blocks.  These children will all be in the
	 *  reconstruction tree, so they're already in
	 *  memory.
	 */
	paln = (PALNODE) AB_START (&mem->blk);


	for ( i = 0; i < mem->blk.a.alb.cUsed; i++ ) {

	    /*
	     *	Find the child that corresponds to this
	     *	node and process it.  Since the childlist
	     *	is in no particular order, we search the
	     *	whole list from the beginning each time.
	     */
	    pmemChild = mem->childlist;
	    while( (pmemChild != NULL) &&
		   (pmemChild->psn != paln->lsnPhys) ){

		pmemChild = pmemChild->next;
	    }

	    if ( pmemChild == NULL ) {

		/*
		 *  After all our work, the allocation tree
		 *  is still inconsistent.  Just return,
		 *  and hope the user runs chkdsk again before
		 *  trying to access this file!
		 */
		chk_exit_recursive (TRAVERSE_ALLOC_STACK);
		return;
	    }

	    chk_traverse_alloc_tree( pmemChild, pclsn );

	    /*
	     *	Update the node entry's LOF and move
	     *	on to the next entry.
	     */
	    if( (paln->lsnLog != *pclsn) &&
		(paln->lsnLog != 0xffffffff) ) {

		fChanged = TRUE;
		paln->lsnLog = *pclsn;
	    }
	    paln += 1;
	}

    } else {

	/*
	 *  The entries are leaves.
	 */
	pall = ( ALLEAF *)AB_START (&mem->blk);

	for ( i = 0; i < mem->blk.a.alb.cUsed; i++ ) {

	    if (pall->lsnLog != *pclsn ) {

		fChanged = TRUE;
		pall->lsnLog = *pclsn;
	    }

	    *pclsn += pall->csecRun;
	    pall += 1;
	}
    }


    if( fChanged ) {

	/*
	 *  We changed this allocation block, so we'll write
	 *  it.  This write may be redundant but we do it anyhow.
	 */
	write_scratch (mem->psn, &mem->blk, SECTORS_PER_AB);
    }

    chk_exit_recursive (TRAVERSE_ALLOC_STACK);
    return;

}


/***	chk_save_structures -- get back lost structures
 *
 *	This function is called after the "in use" space (or optionally
 *	the entire disk) is scanned for lost structures.  Any structures
 *	found are chained to the "lost" tree.  This function walks that
 *	tree, creating files or directories to contain the lost data.
 *	As the tree is walked, nodes are deallocated from memory after
 *	being written.
 *
 *	Update_bit_maps should be called before this function is called,
 *	so that the file system has a completely consistent system to
 *	create files with.
 *
 *	chk_save_structures (void)
 *
 *	ENTRY		No parameters
 *			"lost" points to a linked list of structures
 *
 *	EXIT		No return value
 *
 *	CALLS		File system API's
 *
 *	EFFECTS		Lost data written to disk
 *			Files and/or directories created
 */
void chk_save_structures ( PULONG plsnFoundRoot )
{
   mem_blk *p;
  BOOL fSeenDotDot;
  UCHAR pszPrevName [CCHMAXPATH];
  UCHAR direntbufs [sizeof ( DIRENT) * 2 + 20];
   DIRENT *d=(PDIRENT)direntbufs;
   DIRENT *dotdot=(PDIRENT)&direntbufs [sizeof ( DIRENT)+16];
   DIRBLK *db = &dbstruc;
  union dp dp;
  UCHAR *cp;
  UCHAR codepage;
  USHORT fno=0, dirno=0, isdir;
  ULONG foundfn, l, curtime, sig, cbFileSize;
  ULONG clsn;	    /*	Used to count logical sectors in a file	 */


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

#ifdef DEBUG
  printf ("Lost tree contents:\n");
#endif

  chk_dump_lost (chk_lost);

  curtime = get_time ();

/*
 * Allocate a directory entry structure.  Allocate enough for the DIRENT
 * header plus a twelve-character (FILExxxx.CHK) name, plus a downpointer.
 * Point our character pointer at the name field.
 */

  memset (dotdot, '\0', sizeof ( DIRENT) + 4);
  dotdot->cchThisEntry = sizeof ( DIRENT) + 4;
  dotdot->fFlags   = DF_SPEC;
  dotdot->fAttr	   = ATTR_DIRECTORY;
  dotdot->timLastMod = dotdot->timLastAccess = dotdot->timCreate = curtime;
  dotdot->cchName = 2;
  memcpy (dotdot->bName, "\001\001", 2);

  cp = d->bName;
  d->timLastMod	= d->timLastAccess = d->timCreate = curtime;
  d->cchName	= 9;
				/* we round up cchThisEntry to a multiple of 4 */
  d->cchThisEntry	= (sizeof ( DIRENT) + d->cchName + 2) & ~3;
  d->cchFSize	= 0L;
  d->ulEALen	= 0L;
  d->fFlex	= 0;

  /*  Set the DIRENT's codepage to the first valid codepage found  */

  for (codepage=0; (USHORT)codepage<chk_cp_count; codepage++)
    if (chk_valid_cps [codepage])
      break;

  d->bCodePage	= codepage;

/*
 * Now allocate an FNODE for the new FOUND.xxx directory, a DIRBLK for
 * that directory, and attempt to create the directory manually.
 */

  d->fFlags = 0;
  d->fAttr  = ATTR_DIRECTORY;
  if (!(l=chk_write_data (root_fnode, db, SECTORS_PER_DIRBLK, TRUE))) {
    CHK_ERROR_MSG( CHK_INSF_DISK_STR);
    return;
  }
  use_sectors (l, (ULONG)SECTORS_PER_DIRBLK, DISK_DIRBLK);
  if (!(foundfn = chk_make_fnode (NULL, l, root_fnode, DISK_DIRBLK, &cbFileSize))) {
    CHK_ERROR_MSG( CHK_INSF_DISK_STR);
    for (foundfn = l; foundfn < l + SECTORS_PER_DIRBLK; foundfn++)
      set_bit (foundfn);			/* unallocate the DIRBLK */
    return;					/* no space for the FNODE */
  }

  d->lsnFNode = foundfn;				/* store FNODE sec in DIRENT */

  memset ((PUCHAR)db, '\0', sizeof (DIRBLK));
  db->sig = DBSIGVAL;
  db->culChange = 1;
  db->lsnParent = foundfn;
  db->lsnThisDir = l;

  dp.p = DIR_START (*db);

#ifdef DOT_ENTRY
  dp.d->cchThisEntry = sizeof (DIRENT) - 4;
  dp.d->fFlags = 0;
  dp.d->fAttr  = ATTR_DIRECTORY;
  dp.d->timLastMod = dp.d->timLastAccess = dp.d->timCreate = curtime;
  dp.d->lsnFNode = foundfn;
  dp.d->cchName = 1;
  dp.d->bName[0] = '.';
  GETNEXT_ENTRY (dp);
#endif

  memcpy (dp.p, (PUCHAR)dotdot, sizeof (DIRENT) + 4);
  GETNEXT_ENTRY (dp);

  dp.d->cchThisEntry = sizeof (DIRENT);
  dp.d->fFlags = DF_END;
  dp.d->fAttr  = 0;
  dp.d->timLastMod = dp.d->timLastAccess = dp.d->timCreate = curtime;
  dp.d->cchName = 1;
  dp.d->bName[0] = 0xff;
  GETNEXT_ENTRY (dp);

  db->offulFirstFree = dp.p - (PUCHAR)db;
  write_scratch (l, db, SECTORS_PER_DIRBLK);

/*
 * Read in the root FNODE, and from there get the top-level root DIRBLK.
 */

  if (read_scratch (root_fnode, &chk_scratch_blk, SECTORS_PER_FNODE) ||
      read_scratch (chk_scratch_blk.f.fst.a.aall[0].lsnPhys, db, SECTORS_PER_DIRBLK))
    return;

/*
 * Add the DIRENT for FOUND.xxx to the root directory.
 */

  do {
    sprintf (cp, "FOUND.%03d", fno++);
  } while (chk_add_dirent (d, db));	/* add the DIRENT to the root */

  CHK_OUT_MSG( SYSTEM_MSG, CHK_FOUND_NAME_STR, cp);	/* tell user which FOUND.mmm to look in */

/*
 * Now create new entries in the FOUND.xxx directory for the lost files, after
 * reading in the DIRBLK for the new directory we just made.
 */

  read_scratch (l, db, SECTORS_PER_DIRBLK);

  fno = 0;

  for (p=chk_lost; p; p=p->next) {

    while (!(db->culChange & 1))		/* make sure db contains top-level blk */
      read_scratch (db->lsnParent, db, SECTORS_PER_DIRBLK);

    sig = p->blk.f.sig;



    /*
     *	Prepare to recover an allocation block.  First, we
     *	traverse the block and its children, making sure that
     *	the various leaf entries have consistent logical file
     *	sector numbers.  Then we build an FNODE to point at the
     *	block, and compute the total size of this recovered file.
     */
    if (sig == ABSIGVAL) {

      p->blk.a.lsnSelf = p->psn;
      isdir = FALSE;
      d->fFlags = d->fAttr = 0;

      clsn = 0;

      chk_traverse_alloc_tree( p, &clsn );

      /*
       *  If this is a ALSEC, we need to set the very last
       * lsnLog to 0xffffffff, to indicate the end of file.
       */
      if ( p->blk.a.alb.bFlag & ABF_NODE ) {

	( (PALNODE)AB_START(&p->blk)
		+ p->blk.a.alb.cUsed - 1 ) ->lsnLog = 0xffffffff;
      }


      if (!(l=chk_make_fnode (p, p->psn, foundfn, DISK_AB, &cbFileSize))) {
		CHK_ERROR_MSG( CHK_INSF_DISK_STR);
		continue;
      }

      p->blk.a.lsnRent = l;
      write_scratch (p->psn, &p->blk, SECTORS_PER_AB);
      d->lsnFNode = l;
      d->cchFSize = cbFileSize;
      d->ulEALen = 0L;
    }

/*
 * Prepare to recover a DIRBLK.  To do this, we build an FNODE which points
 * to the lost DIRBLK, then set up our new DIRENT with the subdirectory flag
 * and pointing to the new FNODE.
 *
 * We also need to go through the DIRBLK, reading each FNODE referenced by
 * it and changing that FNODE's lsnContDir field to the correct value.  The
 * DIRBLK's lsnParent field also needs to be corrected.
 *
 * We also have to make sure that the DIRBLK contains a ".." entry, so that
 * it's a valid subdirectory.  We do this by calling chk_add_dirent after
 * making the DIRBLK otherwise consistent.
 */

    else if (sig == DBSIGVAL) {
      isdir = TRUE;
      if (!(l=chk_make_fnode (NULL, p->psn, foundfn, DISK_DIRBLK, &cbFileSize))) {
	CHK_ERROR_MSG( CHK_INSF_DISK_STR);
	continue;
      }
      d->fFlags	  = 0;
      d->fAttr	  = ATTR_DIRECTORY;
      d->lsnFNode = l;
      d->cchFSize = 0L;
      d->ulEALen  = 0L;

      if (!(p->blk.d.culChange & 1L)) {	/* this wasn't a "topmost" dirblk */
	p->blk.d.culChange |= 1L;	/* it is now, mark it so */
	write_scratch (p->psn, &p->blk, SECTORS_PER_DIRBLK);	/* save it */
      }

      p->blk.d.lsnParent = l;
      write_scratch (p->psn, &p->blk, SECTORS_PER_DIRBLK);

      /*
       *  BUGBUG -- is this in the right order?
       */
      pszPrevName [0] = '\0';
      fSeenDotDot = FALSE;
      if (chk_badly_ordered (p->psn, pszPrevName, &fSeenDotDot))
	chk_sort_directory (l, NULL);	/* resort directory since it's bogus */


      chk_consistent_db (p, l);		/* make this DIRBLK consistent */
      chk_add_dirent (dotdot, &p->blk.d);	/* add a ".." entry just in case */

    }

/*
 * Prepare to recover an FNODE.  To do this, we first modify the FNODE to
 * contain the correct parent pointer;	then we fill in the new DIRENT
 * with the correct flags, FNODE number, and size.
 */

    else {
      if (!sig) {			/* this is a raw data run */
		p->blk.f.sig = FNSIGVAL;	/* set its signature correctly */
		if (!(p->psn = allocate_near (p->blk.f.fst.a.aall[0].lsnPhys,
				      SECTORS_PER_FNODE, 1))) {
		CHK_ERROR_MSG( CHK_INSF_DISK_STR);
		continue;			/* no disk space for FNODE */
		}
      }

      p->blk.f.lsnContDir = foundfn;


      /*
       *  If the FNF_DIR flag is set in the FNODE, then it's the
       *  FNODE of a directory.
       */
      if (p->blk.f.bFlag & FNF_DIR) {

		d->fFlags = 0;
		d->fAttr  = ATTR_DIRECTORY;
		isdir	  = TRUE;

		if (p->childlist) {

			if (p->childlist->blk.d.lsnParent != p->psn ||
			    p->childlist->blk.d.lsnThisDir != p->childlist->psn ||
			    !(p->childlist->blk.d.culChange & 1L)) {
				p->childlist->blk.d.lsnParent = p->psn;
				p->childlist->blk.d.lsnThisDir = p->childlist->psn;
				p->childlist->blk.d.culChange |= 1L;
				write_scratch (p->childlist->psn,
					       &p->childlist->blk.d,
					       SECTORS_PER_DIRBLK);
			}
			chk_add_dirent (dotdot, &p->childlist->blk.d); /* add a ".." entry */
		}
      }
      else {
		isdir = FALSE;
		d->fFlags = d->fAttr = 0;
      }

      d->lsnFNode = p->psn;
      d->cchFSize = p->blk.f.fst.ulVLen = chk_calc_file_size (p) * (ULONG)SECSIZE;

      if (p->blk.f.aiEA.usFNL)
	d->ulEALen = p->blk.f.aiEA.usFNL;
      else if (p->blk.f.aiEA.sp.cbRun)
	d->ulEALen = p->blk.f.aiEA.sp.cbRun;
      else
	d->ulEALen = 0L;

      write_scratch (p->psn, &p->blk.f, SECTORS_PER_FNODE);

    }

/*
 * Our DIRENT is correctly filled in.  Now try different names of the form
 * FILExxxx.CHK or DIRxxxx.CHK until we can successfully create one.
 */

    do {
      if (isdir) {
	d->cchName = 11;
	sprintf (cp, "DIR%04d.CHK", dirno++);
      }
      else {
	d->cchName = 12;
	sprintf (cp, "FILE%04d.CHK", fno++);
      }
      d->cchThisEntry = (sizeof ( DIRENT) + d->cchName + 3) & ~3;
    } while (chk_add_dirent (d, db));	/* add the DIRENT to FOUND.xxx */

    CHK_OUT_MSG( SYSTEM_MSG, (isdir) ? CHK_DIR_RECOVERED_STR : CHK_FILE_RECOVERED_STR, cp);
  }

  /*
   *  Set *plsnFoundRoot to the LSN of the root dirblk of
   *  the newly-created found.xxx directory.  Make
   *  sure that it's the top-level dirblk!
   */
  while (!(db->culChange & 1))
   read_scratch (db->lsnParent, db, SECTORS_PER_DIRBLK);


  *plsnFoundRoot = db->lsnThisDir;

}
