restore/tree.c

/*
 * Copyright (c) 2000-2002 Silicon Graphics, Inc.
 * All Rights Reserved.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it would be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write the Free Software Foundation,
 * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/param.h>
#include <fcntl.h>
#include <sys/stat.h>
#include <sys/ioctl.h>
#include <utime.h>
#include <limits.h>
#include <time.h>
#include <xfs/handle.h>
#include <dirent.h>
#include <sys/ioctl.h>
#include <assert.h>
#include <string.h>
#include <uuid/uuid.h>
#include <xfs/xfs.h>

#include "config.h"

#include "types.h"
#include "exit.h"
#include "cldmgr.h"
#include "path.h"
#include "openutil.h"
#include "getopt.h"
#include "stream.h"
#include "mlog.h"
#include "dlog.h"
#include "global.h"
#include "drive.h"
#include "media.h"
#include "content.h"
#include "content_inode.h"
#include "inomap.h"
#include "namreg.h"
#include "dirattr.h"
#include "bag.h"
#include "node.h"
#include "tree.h"
#include "libgen.h"
#include "mmap.h"
#include "exit.h"

/* structure definitions used locally ****************************************/

/* name of persistent state file
 */
#define PERS_NAME	"tree"

/* orphanage specifics. ino must be otherwise unused in the dump source fs.
 * zero works.
 */
#define ORPH_INO	0
#define ORPH_NAME	"orphanage"


/* VM budgeting - give hash array one sixteenth, rest goes to node array
 */
#define HASHSZ_PERVM	16

/* reserve the first page for persistent state
 */
struct treePersStorage {
	xfs_ino_t p_rootino;
		/* ino of root
		 */
	nh_t p_rooth;
		/* handle of root node
		 */
	nh_t p_orphh;
		/* handle to orphanage node
		 */
	size64_t p_hashsz;
		/* size of hash array (private to hash abstraction)
		 */
	size_t p_hashmask;
		/* hash mask (private to hash abstraction)
		 */
	bool_t p_ownerpr;
		/* restore directory owner/group attributes
		 */
	bool_t p_fullpr;
		/* restoring a full level 0 non-resumed dump (can skip
		 * some steps)
		 */
	bool_t p_ignoreorphpr;
		/* set if positive subtree or interactive
		 */
	bool_t p_truncategenpr;
		/* truncate inode generation number (for compatibility
		 * with xfsdump format 2 and earlier)
		 */
};

typedef struct treePersStorage treepers_t;

#define PERSSZ	perssz


/* interactive dialog transient state
 */
#define INTER_ARGMAX	10	/* max number of args to interactive cmds */
struct inter {
	size_t i_argc;
	char *i_argv[INTER_ARGMAX];
	nh_t i_cwdh;
	char i_name[NAME_MAX + 1];
};

typedef struct inter inter_t;

/* transient state
 */
struct tran {
	bool_t t_toconlypr;
		/* just display table of contents; don't restore files
		 */
	char *t_hkdir;
		/* full absolute pathname of housekeeping directory
		 */
	char *t_dstdir;
		/* full absolute pathname of destination directory
		 */
	bool_t t_dstdirisxfspr;
		/* destination directory is an xfs filesystem; xfs-specific
		 * calls can be made when needed.
		 */
	char *t_orphdir;
		/* full absolute pathname of orphanage directory
		 */
	char *t_hksubtree;
		/* if non-NULL, is path of hkdir relative to dstdir.
		 * don't restore there.
		 */
	int t_persfd;
		/* file descriptor of the persistent state file
		 */
	nh_t *t_hashp;
		/* pointer to mapped hash array (private to hash abstraction)
		 */
	char t_namebuf[NAME_MAX + 1];
		/* to hold names temporarily retrieved from name registry
		 */
	inter_t t_inter;
		/* context for interactive subtree selection
		 */
};

typedef struct tran tran_t;


/* node structure. each node represents a directory entry
 */
#define NODESZ	56

struct node {
	xfs_ino_t n_ino;	/* 8  8 ino */
	nrh_t n_nrh;		/* 8 16 handle to name in name registry */
	dah_t n_dah;		/* 4 20 handle to directory attributes */
	nh_t n_hashh;		/* 4 24 hash array */
	nh_t n_parh;		/* 4 28 parent */
	nh_t n_sibh;		/* 4 32 sibling list */
	nh_t n_sibprevh;	/* 4 36 prev sibling list - dbl link list */
	nh_t n_cldh;		/* 4 40 children list */
	nh_t n_lnkh;		/* 4 44 hard link list */
	gen_t n_gen;		/* 4 48 generation count mod 0x10000 */
	u_char_t n_flags;	/* 1 49 action and state flags */
	u_char_t n_nodehkbyte;	/* 1 50 given to node abstraction */
	char n_pad[6];		/* 6 56 */
};

typedef struct node node_t;

#define NF_REAL		(1 << 0)
	/* set when the corresponding file/dir has been created in
	 * the restore destination.
	 */
#define NF_SUBTREE	(1 << 1)
	/* marks nodes in the selected subtrees.
	 */
#define NF_REFED	(1 << 2)
	/* indicates node is still referenced according to incremental/resumed
	 * dump. used to detect dirents no longer used. prior to restoring
	 * a dump session, this flag is cleared in all nodes. during the dirent
	 * restoral, it is set. it may also be set during the adjustment
	 * for referenced but undumped directories. NOTE: nodes in the
	 * orphanage NEVER have this flag set.
	 */
#define NF_WRITTEN	(1 << 3)
	/* set as soon as a non-dir node restore is begun. allows
	 * overwrite inhibit options to work with segmented files
	 */
#define NF_ISDIR	(1 << 4)
	/* indicates this node is a directory. set when a directory is taken
	 * from the dirdump.
	 */
#define NF_DUMPEDDIR	(1 << 5)
	/* indicates this node is a directory present in the current dirdump.
	 * at beginning of session, this flag is cleared in all nodes.
	 * then as each directory dump is read from media, the flag
	 * is set from the corresponding node. this allows adjustments to
	 * the NF_REFED flag: if a directory was not dumped, either it no
	 * longer exists or it has not changed. if it is referenced, we assume
	 * it exists, in which case if it is not dumped then all of its entries
	 * are referenced as well.
	 */
#define NF_NEWORPH	(1 << 6)
	/* cleared from all nodes in the orphanage before a dump is applied.
	 * set if a dir is seen in the dirdump but no node exists for it.
	 * cleared if that dir is adopted subsequently during the dirdump.
	 * set if a nondir is seen in the nondir dump but no node exists for
	 * it. in either case a node is created and placed in the orphanage.
	 * during rmdir/unlink processing, nodes so marked are left alone.
	 * since the flag is cleared at the beginning of the next increment,
	 * old orphans had better be adopted, otherwise they will be unlinked.
	 */

/* link list iterator context
 */
struct link_iter_context {
	nh_t li_headh;          /* head of hard link list */
	nh_t li_prevh;          /* next to last node returned by _next() */
	nh_t li_lasth;          /* last node returned by _next() */
	bool_t li_donepr;       /* set as soon as last.next null */
};
typedef struct link_iter_context link_iter_context_t;

/* used for caching parent pathname from previous Node2path result
 */
struct path_cache {
	nh_t nh;
	int len;
	char buf[MAXPATHLEN];
};
typedef struct path_cache path_cache_t;

/* declarations of externally defined global symbols *************************/

extern void usage(void);
extern size_t pgsz;
extern size_t pgmask;
extern bool_t restore_rootdir_permissions;
extern bool_t need_fixrootdir;

/* forward declarations of locally defined static functions ******************/

static nh_t Node_alloc(xfs_ino_t ino,
			gen_t gen,
			nrh_t nrh,
			dah_t dah,
			size_t flags);
static void Node_free(nh_t *nhp);
static node_t * Node_map(nh_t nh);
static void Node_unmap(nh_t nh, node_t **npp);
static int Node2path_recurse(nh_t nh, char *buf,
				   int bufsz, int level);
static void adopt(nh_t parh, nh_t cldh, nrh_t nrh);
static nrh_t disown(nh_t cldh);
static void selsubtree(nh_t nh, bool_t sensepr);
static void selsubtree_recurse_down(nh_t nh, bool_t sensepr);
static nh_t link_hardh(xfs_ino_t ino, gen_t gen);
static nh_t link_nexth(nh_t nh);
static nh_t link_matchh(nh_t hardh, nh_t parh, char *name);
static void link_in(nh_t nh);
static void link_out(nh_t nh);
static void link_headiter(bool_t (*cbfp)(void *contextp, nh_t hardh),
			   void *contextp);
static void link_iter_init(link_iter_context_t *link_iter_contextp,
			    nh_t hardheadh);
static nh_t link_iter_next(link_iter_context_t *link_iter_contextp);
void link_iter_unlink(link_iter_context_t *link_iter_contextp, nh_t nh);
static bool_t hash_init(size64_t vmsz,
			 size64_t dircnt,
			 size64_t nondircnt,
			 char *perspath);
static bool_t hash_sync(char *perspath);
static inline size_t hash_val(xfs_ino_t ino, size_t hashmask);
static void hash_in(nh_t nh);
static void hash_out(nh_t nh);
static nh_t hash_find(xfs_ino_t ino, gen_t gen);
static void hash_iter(bool_t (*cbfp)(void *contextp, nh_t hashh),
		       void *contextp);
static void setdirattr(dah_t dah, char *path);
static bool_t tsi_walkpath(char *arg, nh_t rooth, nh_t cwdh,
			    dlog_pcbp_t pcb, void *pctxp,
			    nh_t *namedhp, nh_t *parhp, nh_t *cldhp,
			    xfs_ino_t *inop, bool_t *isdirprp, bool_t *isselpr);
static bool_t Node2path(nh_t nh, char *path, char *errmsg);
static bool_t tree_setattr_recurse(nh_t parh, char *path);
static void tsi_cmd_pwd_recurse(void *ctxp,
				 dlog_pcbp_t pcb,
				 void *pctxp,
				 nh_t nh);
static int mkdir_r(char *path);
#ifdef TREE_CHK
static bool_t Node_chk(nh_t nh, nh_t *nexthashhp, nh_t *nextlnkhp);
static bool_t tree_chk2(void);
#endif /* TREE_CHK */

/* definition of locally defined global variables ****************************/


/* definition of locally defined static variables *****************************/

static treepers_t *persp = 0;
static tran_t *tranp = 0;
static char *persname = PERS_NAME;
static char *orphname = ORPH_NAME;
static xfs_ino_t orphino = ORPH_INO;
static nh_t orig_rooth = NH_NULL;


/* definition of locally defined global functions ****************************/

void
tree_fixroot(void)
{
	nh_t		rooth = persp->p_rooth;
	xfs_ino_t 	rootino;

	while (1) {
		nh_t	parh;
		node_t *rootp = Node_map(rooth);

		rootino = rootp->n_ino;
		parh = rootp->n_parh;
		Node_unmap(rooth, &rootp);

		if (parh == rooth ||
		/*
		 * since all new node (including non-parent)
		 * would be adopted into orphh
		 */
		    parh == persp->p_orphh ||
		    parh == NH_NULL)
			break;
		rooth = parh;
	}

	if (rooth != persp->p_rooth) {
		persp->p_rooth = rooth;
		persp->p_rootino = rootino;
		disown(rooth);
		adopt(persp->p_rooth, persp->p_orphh, NH_NULL);

		mlog(MLOG_NORMAL, _("fix root # to %llu (bind mount?)\n"),
		     rootino);
	}
}

/* ARGSUSED */
bool_t
tree_init(char *hkdir,
	   char *dstdir,
	   bool_t toconlypr,
	   bool_t ownerpr,
	   xfs_ino_t rootino,
	   xfs_ino_t firstino,
	   xfs_ino_t lastino,
	   size64_t dircnt,
	   size64_t nondircnt,
	   size64_t vmsz,
	   bool_t fullpr,
	   bool_t dstdirisxfspr,
	   uint32_t dumpformat,
	   bool_t truncategenpr)
{
	off64_t nodeoff;
	char *perspath;
	bool_t ok;
	int rval;

	/* sanity checks
	 */
	assert(!(PERSSZ % pgsz));
	assert(sizeof(persp) <= PERSSZ);
	assert(sizeof(node_t) <= NODESZ);
	assert(!persp);
	assert(!tranp);

	/* allocate transient state
	 */
	tranp = (tran_t *)calloc(1, sizeof(tran_t));
	assert(tranp);

	tranp->t_toconlypr = toconlypr;
	tranp->t_hkdir = hkdir;
	tranp->t_dstdir = dstdir;
	tranp->t_dstdirisxfspr = dstdirisxfspr;

	/* allocate a char string buffer to hold the abs. pathname
	 * of the orphanage directory file. load it with the pathname.
	 */
	tranp->t_orphdir = open_pathalloc(tranp->t_dstdir,
					   orphname,
					   0);

	/* determine if housekeeping dir is within the destination.
	 * generate a relative path containing the difference,
	 * else null. will not restore into there.
	 */
	if (strcmp(dstdir, ".")) {
		tranp->t_hksubtree = path_diff(hkdir, dstdir);
	} else {
		tranp->t_hksubtree = 0;
	}

	/* create an orphanage, if it already exists, complain.
	 * not needed if just a table-of-contents restore.
	 */
	if (!tranp->t_toconlypr) {
		rval = mkdir(tranp->t_orphdir, S_IRWXU);
		if (rval) {
			if (errno == EEXIST) {
				mlog(MLOG_NORMAL | MLOG_ERROR | MLOG_TREE, _(
				      "%s already exists: "
				      "rm -rf prior to initating restore\n"),
				      tranp->t_orphdir);
			} else {
				mlog(MLOG_NORMAL | MLOG_ERROR | MLOG_TREE, _(
				      "unable to create %s: %s\n"),
				      tranp->t_orphdir,
				      strerror(errno));
			}
			return BOOL_FALSE;
		}
	}

	/* build a full pathname to pers. state file
	 */
	perspath = open_pathalloc(tranp->t_hkdir, persname, 0);

	/* create the persistent state file
	 */
	(void)unlink(perspath);
	tranp->t_persfd = open(perspath,
				O_RDWR | O_CREAT,
				S_IRUSR | S_IWUSR);
	if (tranp->t_persfd < 0) {
		mlog(MLOG_NORMAL | MLOG_ERROR | MLOG_TREE, _(
		      "could not open %s: %s\n"),
		      perspath,
		      strerror(errno));
		return BOOL_FALSE;
	}

	/* mmap the persistent state
	 */
	assert(!(PERSSZ % pgsz));
	persp = (treepers_t *) mmap_autogrow(
				     PERSSZ,
				     tranp->t_persfd,
				     (off64_t)0);
	if (persp == (treepers_t *)-1) {
		mlog(MLOG_NORMAL | MLOG_ERROR | MLOG_TREE, _(
		      "unable to map %s: %s\n"),
		      perspath,
		      strerror(errno));
		return BOOL_FALSE;
	}

	/* create the hash abstraction. it will map more of the
	 * persistent state file.
	 */
	ok = hash_init(vmsz / HASHSZ_PERVM, dircnt, nondircnt, perspath);
	if (!ok) {
		return BOOL_FALSE;
	}

	/* initialize the node abstraction. let it's use of backing store
	 * begin immediately after the hash abstraction. give it the remainder
	 * of vm.
	 */
	assert(persp->p_hashsz <= (size64_t)(OFF64MAX - (off64_t)PERSSZ));
	nodeoff = (off64_t)PERSSZ + (off64_t)persp->p_hashsz;
	assert(vmsz > (size64_t)nodeoff);
	ok = node_init(tranp->t_persfd,
		        nodeoff,
		        NODESZ,
			 (ix_t)offsetofmember(node_t, n_nodehkbyte),
		        sizeof(size64_t), /* node alignment */
		        vmsz - (size64_t)nodeoff,
			dircnt + nondircnt);
	if (!ok) {
		return BOOL_FALSE;
	}

	/* extract the root ino and allocate a node for
	 * the root and for the orphanage. place both nodes
	 * in the hash list. make the orphanage a child of
	 * root, and indicate he is real.
	 *
	 * Note that we assume that the root inode always
	 * has a generation count of zero - which is true.
	 */
	persp->p_rootino = rootino;
	persp->p_rooth = Node_alloc(rootino,
				     0, /* gen cnt */
				     NRH_NULL,
				     DAH_NULL,
				     NF_ISDIR | NF_REAL);
	if (persp->p_rooth == NH_NULL)
		return BOOL_FALSE;
	link_in(persp->p_rooth);
	persp->p_orphh = Node_alloc(orphino,
				     0, /* gen cnt */
				     namreg_add(orphname, strlen(orphname)),
				     DAH_NULL,
				     NF_ISDIR | NF_REAL);
	if (persp->p_orphh == NH_NULL)
		return BOOL_FALSE;
	link_in(persp->p_orphh);
	adopt(persp->p_rooth, persp->p_orphh, NRH_NULL);

	/* record if we should attempt to restore original owner/group
	 */
	persp->p_ownerpr = ownerpr;

	/* record if this is a full dump. can skip link processing if so
	 */
	persp->p_fullpr = fullpr;

	/* record if truncated generation numbers are required
	 */
	if (dumpformat < GLOBAL_HDR_VERSION_3) {
		persp->p_truncategenpr = BOOL_TRUE;
		mlog(MLOG_NORMAL | MLOG_DEBUG | MLOG_TREE, _(
		      "dump format version %u used truncated inode generation numbers\n"),
			dumpformat);
	} else if (truncategenpr) {
		persp->p_truncategenpr = BOOL_TRUE;
		mlog(MLOG_NORMAL | MLOG_DEBUG | MLOG_TREE, _(
		      "forcing use of truncated inode generation numbers\n"));
	} else {
		persp->p_truncategenpr = BOOL_FALSE;
	}

	return BOOL_TRUE;
}

bool_t
tree_sync(char *hkdir,
	   char *dstdir,
	   bool_t toconlypr,
	   bool_t fullpr,
	   bool_t dstdirisxfspr)
{
	off64_t nodeoff;
	char *perspath;
	bool_t ok;
	int rval;

	if (persp) {
		return BOOL_TRUE;
	}

	/* sanity checks
	 */
	assert(!(PERSSZ % pgsz));
	assert(sizeof(persp) <= PERSSZ);
	assert(sizeof(node_t) <= NODESZ);
	assert(!persp);
	assert(!tranp);

	/* allocate transient state
	 */
	tranp = (tran_t *)calloc(1, sizeof(tran_t));
	assert(tranp);

	tranp->t_toconlypr = toconlypr;
	tranp->t_hkdir = hkdir;
	tranp->t_dstdir = dstdir;
	tranp->t_dstdirisxfspr = dstdirisxfspr;

	/* allocate a char string buffer to hold the abs. pathname
	 * of the orphanage directory file. load it with the pathname.
	 */
	tranp->t_orphdir = open_pathalloc(tranp->t_dstdir,
					   orphname,
					   0);

	/* determine if housekeeping dir is within the destination.
	 * generate a relative path containing the difference,
	 * else null. will not restore into there.
	 */
	if (strcmp(dstdir, ".")) {
		tranp->t_hksubtree = path_diff(hkdir, dstdir);
	} else {
		tranp->t_hksubtree = 0;
	}

	/* re-create the orphanage (in case someone rmdir'ed it)
	 */
	rval = mkdir(tranp->t_orphdir, S_IRWXU);
	if (rval && errno != EEXIST) {
		mlog(MLOG_NORMAL | MLOG_ERROR | MLOG_TREE, _(
		      "unable to recreate %s: %s\n"),
		      tranp->t_orphdir,
		      strerror(errno));
		return BOOL_FALSE;
	}

	/* build a full pathname to pers. state file
	 */
	perspath = open_pathalloc(tranp->t_hkdir, persname, 0);

	/* re-open the persistent state file
	 */
	tranp->t_persfd = open(perspath, O_RDWR);
	if (tranp->t_persfd < 0) {
		mlog(MLOG_NORMAL | MLOG_ERROR | MLOG_TREE, _(
		      "could not open %s: %s\n"),
		      perspath,
		      strerror(errno));
		return BOOL_FALSE;
	}

	/* mmap the persistent state
	 */
	assert(!(PERSSZ % pgsz));
	persp = (treepers_t *) mmap_autogrow(
				     PERSSZ,
				     tranp->t_persfd,
				     (off64_t)0);
	if (persp == (treepers_t *)-1) {
		mlog(MLOG_NORMAL | MLOG_ERROR | MLOG_TREE, _(
		      "unable to map %s: %s\n"),
		      perspath,
		      strerror(errno));
		return BOOL_FALSE;
	}

	/* update the fullpr field of the persistent state to match
	 * the input of our caller.
	 */
	persp->p_fullpr = fullpr;

	/* regardless of the format of this dump, if the previously applied
	 * dump used truncated generation numbers, then we need to as well.
	 */
	if (persp->p_truncategenpr) {
		mlog(MLOG_NORMAL | MLOG_DEBUG | MLOG_TREE, _(
		      "using truncated inode generation numbers for "
		      "compatibility with previously applied restore\n"));
	}

	/* rsynchronize with the hash abstraction. it will map more of the
	 * persistent state file.
	 */
	ok = hash_sync(perspath);
	if (!ok) {
		return BOOL_FALSE;
	}

	/* synchronize with the node abstraction.
	 */
	assert(persp->p_hashsz <= (size64_t)(OFF64MAX - (off64_t)PERSSZ));
	nodeoff = (off64_t)PERSSZ + (off64_t)persp->p_hashsz;
	ok = node_sync(tranp->t_persfd, nodeoff);
	if (!ok) {
		return BOOL_FALSE;
	}

	/* extract the root ino and allocate a node for
	 * the root and for the orphanage. place both nodes
	 * in the hash list. make the orphanage a child of
	 * root, and indicate he is real.
	 */
	return BOOL_TRUE;
}

bool_t
tree_check_dump_format(uint32_t dumpformat)
{
	if (dumpformat < GLOBAL_HDR_VERSION_3 && !persp->p_truncategenpr) {
		mlog(MLOG_NORMAL | MLOG_ERROR | MLOG_TREE, _(
		      "encountered dump format %d after a "
		      "restore of format %d or newer\n"),
			dumpformat, GLOBAL_HDR_VERSION_3);
		mlog(MLOG_NORMAL | MLOG_ERROR | MLOG_TREE, _(
		      "to restore this series of dumps, use the -%c "
		      "option on the first restore\n"),
			GETOPT_FMT2COMPAT);
		return BOOL_FALSE;
	}

	return BOOL_TRUE;
}

/* recursively descend the tree clearing REFED and DIRDUMPED and NEWORPH
 * flags. force the orphanage to be refed and dumped, so we won't try
 * to orphan it, and so things added to it won't look like they are
 * referenced during ref adj. also null dirattr handles, since they are
 * not retained across dump session restores.
 */
static void tree_marknoref_recurse(nh_t parh);

void
tree_marknoref(void)
{
	tree_marknoref_recurse(persp->p_rooth);

	{
		node_t *orphp;
		orphp = Node_map(persp->p_orphh);
		orphp->n_flags |= (NF_REFED | NF_DUMPEDDIR);
		assert(orphp->n_dah == DAH_NULL);
		Node_unmap(persp->p_orphh, &orphp);
	}
}

static void
tree_marknoref_recurse(nh_t parh)
{
	nh_t cldh;

	{
		node_t *parp;
		parp = Node_map(parh);
		parp->n_flags &= ~(NF_REFED | NF_DUMPEDDIR | NF_NEWORPH);

		parp->n_dah = DAH_NULL;
		cldh = parp->n_cldh;
		Node_unmap(parh, &parp);
	}
	while (cldh != NH_NULL) {
		node_t *cldp;
		nh_t nextcldh;
		tree_marknoref_recurse(cldh); /* RECURSION */
		cldp = Node_map(cldh);
		nextcldh = cldp->n_sibh;
		Node_unmap(cldh, &cldp);
		cldh = nextcldh;
	}
}

void
tree_markallsubtree(bool_t sensepr)
{
	if (!sensepr) {
		persp->p_ignoreorphpr = BOOL_TRUE;
	}
	selsubtree(persp->p_rooth, sensepr);
}

nh_t
tree_begindir(filehdr_t *fhdrp, dah_t *dahp)
{
	nh_t hardh;
	xfs_ino_t ino = fhdrp->fh_stat.bs_ino;
	gen_t gen = fhdrp->fh_stat.bs_gen;
	dah_t dah;

	if (persp->p_truncategenpr) {
		gen = BIGGEN2GEN(gen);
	}

	/* sanity check - orphino is supposed to be an unused ino!
	 */
	assert(ino != orphino);

	/* lookup head of hardlink list
	 */
	hardh = link_hardh(ino, gen);
	if (need_fixrootdir == BOOL_FALSE &&
	    !(ino != persp->p_rootino || hardh == persp->p_rooth)) {
		mlog(MLOG_ERROR | MLOG_TREE,
"%s:%d: %s: Assertion `ino != persp->p_rootino || hardh == persp->p_rooth` failed.\n",
			__FILE__, __LINE__, __func__);
		mlog(MLOG_ERROR | MLOG_TREE, _(
"False root detected. Recovery may be possible using the `-x` option\n"));
		return NH_NULL;
	}

	/* already present
	 */
	if (hardh != NH_NULL) {
		node_t *hardp;
		hardp = Node_map(hardh);
		if (!(hardp->n_flags & NF_ISDIR)) {
			/* case 1: previously seen as dirent, now know is dir
			 */
			mlog(MLOG_TRACE | MLOG_TREE,
			      "directory %llu %u (%u): "
			      "upgrading to dir\n",
			      ino,
			      gen,
			      fhdrp->fh_stat.bs_gen);
			if (!tranp->t_toconlypr) {
				assert(hardp->n_dah == DAH_NULL);
				hardp->n_dah = dirattr_add(fhdrp);
			}
		} else if (!tranp->t_toconlypr && hardp->n_dah == DAH_NULL) {
			/* case 2: node is a dir, but had thrown away dirattr
			 */
			mlog(MLOG_TRACE | MLOG_TREE,
			      "directory %llu %u (%u): "
			      "updating\n",
			      ino,
			      gen,
			      fhdrp->fh_stat.bs_gen);
			hardp->n_dah = dirattr_add(fhdrp);
		} else {
			/* case 3: already has dirattr; must be restart
			 */
			mlog(MLOG_TRACE | MLOG_TREE,
			      "directory %llu %u (%u): "
			      "retaining\n",
			      ino,
			      gen,
			      fhdrp->fh_stat.bs_gen);
		}
		hardp->n_flags |= NF_ISDIR;
		hardp->n_flags |= NF_DUMPEDDIR;
		*dahp = hardp->n_dah;
		Node_unmap(hardh, &hardp);
	} else {
		/* case 4: first time seen
		 */
		mlog(MLOG_TRACE | MLOG_TREE,
		      "directory %llu %u (%u): "
		      "new\n",
		      ino,
		      gen,
		      fhdrp->fh_stat.bs_gen);
		if (!tranp->t_toconlypr) {
			dah = dirattr_add(fhdrp);
		} else {
			dah = DAH_NULL;
		}
		hardh = Node_alloc(ino,
				    gen,
				    NRH_NULL,
				    dah,
				    NF_ISDIR | NF_NEWORPH);
		if (hardh == NH_NULL)
			return NH_NULL;
		link_in(hardh);
		adopt(persp->p_orphh, hardh, NRH_NULL);
		*dahp = dah;
	}
	return hardh;
}

rv_t
tree_addent(nh_t parh, xfs_ino_t ino, gen_t gen, char *name, size_t namelen)
{
	nh_t hardh;

	if (persp->p_truncategenpr) {
		gen = BIGGEN2GEN(gen);
	}

	/* sanity check - orphino is supposed to be an unused ino!
	 */
	assert(ino != orphino);

	/* don't allow entries named "orphanage" under root to be added
	 */
	if (parh == persp->p_rooth && !strcmp(name, orphname)) {
		mlog(MLOG_DEBUG | MLOG_TREE,
		      "dirent %s %llu %u: "
		      "skipping (reserved)\n",
		      name,
		      ino,
		      gen);
		return RV_OK;
	}

	/* if the parent is null, just ignore
	 */
	if (parh == NH_NULL) {
		mlog(MLOG_DEBUG | MLOG_TREE,
		      "dirent %s %llu %u: "
		      "skipping (null parent)\n",
		      name,
		      ino,
		      gen);
		return RV_OK;
	}

	/* see if one or more links to this ino already exist.
	 */
	hardh = link_hardh(ino, gen);

	if (hardh != NH_NULL) {
		node_t *hardp;
		hardp = Node_map(hardh);
		if (hardp->n_flags & NF_ISDIR) {
			nh_t renameh;
			node_t *renamep;
			/* REFERENCED */
			int namebuflen;

			hardp->n_flags |= NF_REFED;
			if (hardp->n_parh == persp->p_orphh) {
				/* dir now seen as entry
				 * if in orph but REAL, must be pending rename
				 */
				if ((hardp->n_flags & NF_REAL)
				     &&
				     hardp->n_lnkh == NH_NULL) {
					hardp->n_lnkh = Node_alloc(ino,
								    gen,
								    NRH_NULL,
								    DAH_NULL,
								    0);
					if (hardp->n_lnkh == NH_NULL)
						return RV_ERROR;
				}
				if (hardp->n_lnkh != NH_NULL) {
					assert(hardp->n_flags & NF_REAL);
					renameh = hardp->n_lnkh;
					renamep = Node_map(renameh);
					if (renamep->n_parh == NH_NULL) {
						mlog(MLOG_DEBUG | MLOG_TREE,
						      "dirent %s %llu %u: "
						      "adopting (dir par)\n",
						      name,
						      ino,
						      gen);
						renamep->n_parh = parh;
					}
					if (renamep->n_parh != parh) {
						mlog(MLOG_DEBUG | MLOG_TREE,
						      "dirent %s %llu %u: "
						      "re-adopting (dir par)\n",
						      name,
						      ino,
						      gen);
						renamep->n_parh = parh;
					}
					if (renamep->n_nrh != NRH_NULL) {
						namebuflen
						=
						namreg_get(renamep->n_nrh,
							    tranp->t_namebuf,
						    sizeof(tranp->t_namebuf));
						assert(namebuflen > 0);
						if (strcmp(name,
							   tranp->t_namebuf)) {
							mlog(MLOG_DEBUG
							      |
							      MLOG_TREE,
							      "dirent %s "
							      "%llu %u: "
							      "re-adopting "
							      "(dir name): "
							      "was %s\n",
							      name,
							      ino,
							      gen,
							     tranp->t_namebuf);
							namreg_del(
							       renamep->n_nrh);
							renamep->n_nrh =
								       NRH_NULL;
						}
					}
					if (renamep->n_nrh == NRH_NULL) {
						renamep->n_nrh
						=
						namreg_add(name, namelen);
						renamep->n_parh = parh;
					}
					Node_unmap(renameh, &renamep);
				} else {
					nrh_t nrh;

					hardp->n_flags &= ~NF_NEWORPH;
					assert(hardp->n_nrh == NRH_NULL);
					assert(hardp->n_parh != NH_NULL);
					nrh = disown(hardh);
					assert(nrh == NRH_NULL);
					nrh = namreg_add(name, namelen);
					adopt(parh, hardh, nrh);
					mlog(MLOG_DEBUG | MLOG_TREE,
					      "dirent %s %llu %u: "
					      "updating (dir)\n",
					      name,
					      ino,
					      gen);
				}
			} else {
				assert(hardp->n_nrh != NRH_NULL);

				namebuflen
				=
				namreg_get(hardp->n_nrh,
					    tranp->t_namebuf,
					    sizeof(tranp->t_namebuf));
				assert(namebuflen > 0);
				if (hardp->n_parh == parh
				     &&
				     !strcmp(tranp->t_namebuf, name)) {
					/* dir seen as entry again
					 */
					if (hardp->n_lnkh != NH_NULL) {
						/* rescind rename
						 */
						mlog(MLOG_DEBUG | MLOG_TREE,
						      "dirent %s %llu %u: "
						      "rescind rename (dir)\n",
						      name,
						      ino,
						      gen);
						Node_free(&hardp->n_lnkh);
					} else {
						mlog(MLOG_DEBUG | MLOG_TREE,
						      "dirent %s %llu %u: "
						      "retaining (dir)\n",
						      name,
						      ino,
						      gen);
					}
				} else {
					/* dir rename
					 */
					nh_t renameh;
					node_t *renamep;
					if (hardp->n_lnkh == NH_NULL) {
						renameh = Node_alloc(ino,
								      gen,
								      NRH_NULL,
								      DAH_NULL,
								      0);
						if (renameh == NH_NULL)
							return RV_ERROR;
						hardp->n_lnkh = renameh;
					} else {
						mlog(MLOG_DEBUG | MLOG_TREE,
						      "dirent %s %llu %u: "
						      "re-renaming\n",
						      name,
						      ino,
						      gen);
						renameh = hardp->n_lnkh;
						renamep = Node_map(renameh);
						renamep->n_parh = NH_NULL;
						if (renamep->n_nrh
						     !=
						     NRH_NULL) {
						   namreg_del(renamep->n_nrh);
						}
						renamep->n_nrh = NRH_NULL;
						Node_unmap(renameh, &renamep);
					}
					renamep = Node_map(renameh);
					assert(hardp->n_parh != NH_NULL);
					if (hardp->n_parh != parh) {
						/* different parent
						 */
						renamep->n_parh = parh;
						mlog(MLOG_DEBUG | MLOG_TREE,
						      "dirent %s %llu %u: "
						      "renaming (parent)\n",
						      name,
						      ino,
						      gen);
					}
					if (strcmp(tranp->t_namebuf, name)) {
						/* different name
						 */
						renamep->n_nrh =
						    namreg_add(name, namelen);
						mlog(MLOG_DEBUG | MLOG_TREE,
						      "dirent %s %llu %u: "
						      "renaming (name)\n",
						      name,
						      ino,
						      gen);
					}
					Node_unmap(renameh, &renamep);
				}
			}
		} else {
			nh_t matchh;
			matchh = link_matchh(hardh, parh, name);
			if (matchh != NH_NULL) {
				/* entry already exists
				 */
				node_t *matchp;
				matchp = Node_map(matchh);
				matchp->n_flags |= NF_REFED;
				Node_unmap(matchh, &matchp);
				mlog(MLOG_DEBUG | MLOG_TREE,
				      "dirent %s %llu %u: "
				      "retaining (nondir)\n",
				      name,
				      ino,
				      gen);
			} else {
				/* case 5: new hard link
				 */
				nrh_t nrh;
				nh_t linkh;
				nrh = namreg_add(name, namelen);
				linkh = Node_alloc(ino,
						    gen,
						    NRH_NULL,
						    DAH_NULL,
						    NF_REFED);
				if (linkh == NH_NULL)
					return RV_ERROR;
				link_in(linkh);
				adopt(parh, linkh, nrh);
				mlog(MLOG_DEBUG | MLOG_TREE,
				      "dirent %s %llu %u: "
				      "adding (link)\n",
				      name,
				      ino,
				      gen);
			}
		}
		Node_unmap(hardh, &hardp);
	} else {
		/* case 6: new entry
		 */
		nrh_t nrh;
		nrh = namreg_add(name, namelen);
		hardh = Node_alloc(ino,
				    gen,
				    NRH_NULL,
				    DAH_NULL,
				    NF_REFED);
		if (hardh == NH_NULL)
			return RV_ERROR;
		link_in(hardh);
		adopt(parh, hardh, nrh);
		mlog(MLOG_DEBUG | MLOG_TREE,
		      "dirent %s %llu %u: "
		      "adding (new)\n",
		      name,
		      ino,
		      gen);
	}
	/* found the fake rootino from subdir, need fix p_rooth. */
	if (need_fixrootdir == BOOL_TRUE &&
	    persp->p_rootino == ino && hardh != persp->p_rooth) {
		mlog(MLOG_NORMAL,
		     _("found fake rootino #%llu, will fix.\n"), ino);
		persp->p_rooth = hardh;
	}
	return RV_OK;
}

/* ARGSUSED */
void
tree_enddir(nh_t dirh)
{
}

bool_t
tree_subtree_parse(bool_t sensepr, char *path)
{
	nh_t namedh;
	nh_t parh;
	nh_t cldh;
	xfs_ino_t ino;
	bool_t isdirpr;
	bool_t isselpr;
	bool_t ok;

	/* walk the tree down this relative pathname from the root.
	 */
	ok = tsi_walkpath(path,
			   NH_NULL,
			   persp->p_rooth,
			   0,
			   0,
			   &namedh,
			   &parh,
			   &cldh,
			   &ino,
			   &isdirpr,
			   &isselpr);
	if (!ok) {
		return BOOL_FALSE;
	}

	/* set or clear flag in this node and all of its children,
	 * and ajust parentage flags.
	 */
	selsubtree(namedh, sensepr);

	return BOOL_TRUE;
}

/* tree_post - called after the dirdump has been applied.
 * first phase is to eliminate all unreferenced dirents.
 * done by recursive depth-wise descent of the tree. on the way
 * up, unlink or orphan unreferenced nondirs, unlink unreferenced
 * dirs, orphan dirs to be renamed. if a dir is unreferenced, but
 * contains referenced dirents, orphan those dirents. orphan unreferenced
 * nondirs if they are the last link to an inode referenced but not real
 * somewhere else in the tree. next, make new directories. then rename
 * directories. finally, create hardlinks from orphanage.
 */
static bool_t noref_elim_recurse(nh_t parh,
				  nh_t cldh,
				  bool_t parrefpr,
				  char *path1,
				  char *path2);

static bool_t mkdirs_recurse(nh_t parh,
			      nh_t cldh,
			      char *path);

static bool_t rename_dirs(nh_t cldh,
			   char *path1,
			   char *path2);

static bool_t proc_hardlinks(char *path1,
			      char *path2);

bool_t
tree_post(char *path1, char *path2)
{
	node_t *rootp;
	node_t *orphp;
	nh_t cldh;
	bool_t ok;

	/* eliminate unreferenced dirents
	 */
	if (!persp->p_fullpr) {
		mlog(MLOG_DEBUG | MLOG_TREE,
		      "eliminating unreferenced directory entries\n");
		rootp = Node_map(persp->p_rooth);
		cldh = rootp->n_cldh;
		Node_unmap(persp->p_rooth, &rootp);
		ok = noref_elim_recurse(persp->p_rooth,
					 cldh,
					 BOOL_TRUE,
					 path1,
					 path2);
		if (!ok) {
			return BOOL_FALSE;
		}
	}

	/* make new directories
	 */
	mlog(MLOG_DEBUG | MLOG_TREE,
	      "making new directories\n");
	rootp = Node_map(persp->p_rooth);
	cldh = rootp->n_cldh;
	Node_unmap(persp->p_rooth, &rootp);
	ok = mkdirs_recurse(persp->p_rooth, cldh, path1);
	if (!ok) {
		return BOOL_FALSE;
	}

#ifdef TREE_CHK
	assert(tree_chk());
#endif /* TREE_CHK */

	/* rename directories
	 */
	if (!persp->p_fullpr) {
		mlog(MLOG_DEBUG | MLOG_TREE,
		      "performing directory renames\n");
		orphp = Node_map(persp->p_orphh);
		cldh = orphp->n_cldh;
		Node_unmap(persp->p_orphh, &orphp);
		ok = rename_dirs(cldh, path1, path2);
		if (!ok) {
			return BOOL_FALSE;
		}
	}

#ifdef TREE_CHK
	assert(tree_chk());
#endif /* TREE_CHK */

	/* process hard links
	 */
	if (!persp->p_fullpr) {
		mlog(MLOG_DEBUG | MLOG_TREE,
		      "processing hard links\n");
		ok = proc_hardlinks(path1, path2);
		if (!ok) {
			return BOOL_FALSE;
		}
	}

	return BOOL_TRUE;
}

/* ARGSUSED */
static bool_t
noref_elim_recurse(nh_t parh,
		    nh_t cldh,
		    bool_t parrefpr,
		    char *path1,
		    char *path2)
{
	while (cldh != NH_NULL) {
		node_t *cldp;
		xfs_ino_t ino;
		gen_t gen;
		bool_t inorphanagepr;
		bool_t isdirpr;
		bool_t isrealpr;
		bool_t isrefpr;
		bool_t isrenamepr;
		nh_t renameh;
		nh_t grandcldh;
		nh_t nextcldh;
		int rval;
		bool_t ok;

		cldp = Node_map(cldh);
		ino = cldp->n_ino;
		gen = cldp->n_gen;
		inorphanagepr = cldp->n_parh == persp->p_orphh;
		isdirpr = (cldp->n_flags & NF_ISDIR);
		isrealpr = (cldp->n_flags & NF_REAL);
		isrefpr = (cldp->n_flags & NF_REFED);
		isrenamepr = (isdirpr && cldp->n_lnkh != NH_NULL);
		renameh = cldp->n_lnkh;
		grandcldh = cldp->n_cldh;
		nextcldh = cldp->n_sibh;

#ifdef TREE_DEBUG
		ok = Node2path(cldh, path1, _("noref debug"));
		mlog(MLOG_TRACE | MLOG_TREE,
		      "noref: %s: isdir = %d, isreal = %d, isref = %d, "
		      "isrenamedir = %d\n",
		      path1, isdirpr, isrealpr, isrefpr, isrenamepr);
#endif

		Node_unmap(cldh, &cldp);

		if (isdirpr) {
			bool_t ok;

			ok = noref_elim_recurse(cldh,
						 grandcldh,
						 isrefpr,
						 path1,
						 path2);
						/* RECURSION */
			if (!ok) {
				return BOOL_FALSE;
			}

			if (inorphanagepr) {
				cldh = nextcldh;
				continue;
			}

			if (!isrefpr) {
				nrh_t nrh;

				assert(!isrenamepr);
				if (isrealpr) {
					ok = Node2path(cldh, path1, _("rmdir"));
					if (!ok) {
						cldh = nextcldh;
						continue;
					}
					mlog(MLOG_TRACE | MLOG_TREE,
					      "rmdir %s\n",
					      path1);
					rval = rmdir(path1);
					if (rval) {
						mlog(MLOG_NORMAL
						      |
						      MLOG_WARNING
						      |
						      MLOG_TREE, _(
						    "unable to rmdir %s: %s\n"),
						     path1,
						     strerror(errno));
						cldh = nextcldh;
						continue;
					}
				}
				nrh = disown(cldh);
				assert(nrh != NRH_NULL);
				namreg_del(nrh);
				link_out(cldh);
				Node_free(&cldh);
			}

			if (isrenamepr) {
				nrh_t nrh;
				node_t *renamep;

				assert(isrefpr);
				assert(isrealpr);
				ok = Node2path(cldh,
						path1,
						_("tmp dir rename src"));
				if (!ok) {
					cldh = nextcldh;
					continue;
				}
				nrh = disown(cldh);
				assert(nrh != NRH_NULL);
				adopt(persp->p_orphh, cldh, NRH_NULL);
				ok = Node2path(cldh,
						path2,
						_("tmp dir rename dst"));
				if (!ok) {
					/* REFERENCED */
					nrh_t dummynrh;
					dummynrh = disown(cldh);
					assert(dummynrh == NRH_NULL);
					adopt(parh, cldh, nrh);
					cldh = nextcldh;
					continue;
				}
				mlog(MLOG_TRACE | MLOG_TREE,
				      "rename dir %s to %s\n",
				      path1,
				      path2);
				rval = rename(path1, path2);
				if (rval) {
					/* REFERENCED */
					nrh_t dummynrh;
					mlog(MLOG_NORMAL | MLOG_WARNING, _(
					      "unable to rename dir %s "
					      "to dir %s: %s\n"),
					      path1,
					      path2,
					      strerror(errno));
					dummynrh = disown(cldh);
					assert(dummynrh == NRH_NULL);
					adopt(parh, cldh, nrh);
					cldh = nextcldh;
					continue;
				}
				cldp = Node_map(cldh);
				renamep = Node_map(renameh);
				if (renamep->n_nrh == NRH_NULL) {
					renamep->n_nrh = nrh;
				} else {
					namreg_del(nrh);
				}
				if (renamep->n_parh == NH_NULL) {
					renamep->n_parh = parh;
				}
				cldp->n_flags |= NF_NEWORPH;
				Node_unmap(renameh, &renamep);
				Node_unmap(cldh, &cldp);
			}
		} else  {
			/* determine if we can unlink this node.
			 * if its not real, and not refed, simple.
			 * if real and not refed and there is at least
			 * one unreal refed node and no other real
			 * nodes around, must put this one in orphanage
			 * rather than unlinking it.
			 */
			bool_t mustorphpr;
			bool_t canunlinkpr;

			if (inorphanagepr) {
				cldh = nextcldh;
				continue;
			}

			mustorphpr = BOOL_FALSE;
			canunlinkpr = !isrefpr && !isrealpr;
			if (!isrefpr && isrealpr) {
				nh_t hardh;
				bool_t neededpr;
				hardh = link_hardh(ino, gen);
				assert(hardh != NH_NULL);
				canunlinkpr = BOOL_FALSE;
				neededpr = BOOL_FALSE;
				/* tes@sgi.com:
				 * This loop seems to assume that
				 * REAL files come before NON-REALs
				 * so that we will break out first
				 * if we find a REAL file.
				 */
				while (hardh != NH_NULL) {
					node_t *hardp;
					bool_t hardisrefpr;
					bool_t hardisrealpr;
					nh_t nexthardh;

					hardp = Node_map(hardh);
					hardisrefpr = hardp->n_flags & NF_REFED;
					hardisrealpr = hardp->n_flags & NF_REAL;
					nexthardh = hardp->n_lnkh;
					Node_unmap(hardh, &hardp);
					if (hardh != cldh && hardisrealpr) {
						break;
					}
					if (hardisrefpr && !hardisrealpr) {
						neededpr = BOOL_TRUE;
					}
					hardh = nexthardh;
				}
				if (neededpr) {
					mustorphpr = BOOL_TRUE;
				}
				else {
					canunlinkpr = BOOL_TRUE;
				}
			}

			if (mustorphpr) {
				/* rename file to orphanage */
				nrh_t nrh;
				assert(!canunlinkpr);
				ok = Node2path(cldh,
						path1,
						_("tmp nondir rename src"));
				if (!ok) {
					cldh = nextcldh;
					continue;
				}
				nrh = disown(cldh);
				assert(nrh != NRH_NULL);
				adopt(persp->p_orphh, cldh, NRH_NULL);
				ok = Node2path(cldh,
						path2,
						_("tmp nondir rename dst"));
				if (!ok) {
					/* REFERENCED */
					nrh_t dummynrh;
					dummynrh = disown(cldh);
					assert(dummynrh == NRH_NULL);
					adopt(parh, cldh, nrh);
					cldh = nextcldh;
					continue;
				}
				mlog(MLOG_TRACE | MLOG_TREE,
				      "rename nondir %s to %s\n",
				      path1,
				      path2);
				rval = rename(path1, path2);
				if (rval) {
					/* REFERENCED */
					nrh_t dummynrh;
					mlog(MLOG_NORMAL | MLOG_WARNING, _(
					      "unable to rename nondir %s "
					      "to nondir %s: %s\n"),
					      path1,
					      path2,
					      strerror(errno));
					dummynrh = disown(cldh);
					assert(dummynrh == NRH_NULL);
					adopt(parh, cldh, nrh);
					cldh = nextcldh;
					continue;
				}
				namreg_del(nrh);
				cldp = Node_map(cldh);
				cldp->n_flags |= NF_NEWORPH;
				Node_unmap(cldh, &cldp);
			}
			if (canunlinkpr) {
				/* REFERENCED */
				nrh_t nrh;

				assert(!mustorphpr);
				if (isrealpr) {
					ok = Node2path(cldh, path1, _("rmdir"));
					if (!ok) {
						cldh = nextcldh;
						continue;
					}
					mlog(MLOG_TRACE | MLOG_TREE,
					      "unlink %s\n",
					      path1);
					rval = unlink(path1);
					if (rval) {
						mlog(MLOG_NORMAL
						      |
						      MLOG_WARNING
						      |
						      MLOG_TREE, _(
						     "unable to unlink nondir "
						     "%s: %s\n"),
						     path1,
						     strerror(errno));
						cldh = nextcldh;
						continue;
					}
				}
				nrh = disown(cldh);
				assert(nrh != NRH_NULL);
				link_out(cldh);
				Node_free(&cldh);
			}
		}

		/* next!
		 */
		cldh = nextcldh;
	}

	return BOOL_TRUE;
}

/* ARGSUSED */
static bool_t
mkdirs_recurse(nh_t parh, nh_t cldh, char *path)
{
	while (cldh != NH_NULL) {
		node_t *cldp;
		bool_t isdirpr;
		bool_t isselpr;
		bool_t isrealpr;
		bool_t isrefpr;
		nh_t grandcldh;
		nh_t nextcldh;

		cldp = Node_map(cldh);
		isdirpr = (cldp->n_flags & NF_ISDIR);
		isrealpr = (cldp->n_flags & NF_REAL);
		isrefpr = (cldp->n_flags & NF_REFED);
		isselpr = (cldp->n_flags & NF_SUBTREE);
		grandcldh = cldp->n_cldh;
		nextcldh = cldp->n_sibh;
		Node_unmap(cldh, &cldp);

		/* if needed, create a directory and update real flag
		 */
		if (isdirpr && !isrealpr && isrefpr && isselpr) {
			int rval;

			if (!Node2path(cldh, path, _("makedir"))) {
				cldh = nextcldh;
				continue;
			}
			if (tranp->t_toconlypr) {
				rval = 0;
			} else {
				mlog(MLOG_TRACE | MLOG_TREE,
				      "mkdir %s\n",
				      path);
				rval = mkdir(path, S_IRWXU);
			}
			if (rval && errno != EEXIST) {
				mlog(MLOG_NORMAL | MLOG_WARNING | MLOG_TREE, _(
				      "mkdir %s failed: %s\n"),
				      path,
				      strerror(errno));

			} else {
				cldp = Node_map(cldh);
				cldp->n_flags |= NF_REAL;
				Node_unmap(cldh, &cldp);
				isrealpr = BOOL_TRUE;
			}
		}

		/* if a real selected directory, recurse
		 */
		if (isdirpr && isrealpr && isselpr) {
			bool_t ok;
			ok = mkdirs_recurse(cldh, grandcldh, path);
							/* RECURSION */
			if (!ok) {
				return BOOL_FALSE;
			}
		}

		/* next!
		 */
		cldh = nextcldh;
	}

	return BOOL_TRUE;
}

static bool_t
rename_dirs(nh_t cldh,
	     char *path1,
	     char *path2)
{
	while (cldh != NH_NULL) {
		node_t *cldp;
		/* REFERENCED */
		nh_t parh;
		bool_t isdirpr;
		nh_t renameh;
		bool_t isrenamepr;
		nh_t nextcldh;
		nh_t newparh;
		nh_t newnrh;

		cldp = Node_map(cldh);
		parh = cldp->n_parh;
		isdirpr = cldp->n_flags & NF_ISDIR;
		renameh = cldp->n_lnkh;
		isrenamepr = isdirpr && renameh != NH_NULL;
		nextcldh = cldp->n_sibh;
		Node_unmap(cldh, &cldp);
		assert(parh == persp->p_orphh);

		if (isrenamepr) {
			node_t *renamep;
			int rval;
			/* REFERENCED */
			nrh_t dummynrh;
			bool_t ok;

			renamep = Node_map(renameh);
			newparh = renamep->n_parh;
			newnrh = renamep->n_nrh;
			Node_unmap(renameh, &renamep);
			ok = Node2path(cldh, path1, _("rename dir"));
			if (!ok) {
				cldh = nextcldh;
				continue;
			}
			dummynrh = disown(cldh);
			assert(dummynrh == NRH_NULL);
			adopt(newparh, cldh, newnrh);
			ok = Node2path(cldh, path2, _("rename dir"));
			if (!ok) {
				dummynrh = disown(cldh);
				assert(dummynrh == newnrh);
				adopt(persp->p_orphh, cldh, NRH_NULL);
				cldp = Node_map(cldh);
				cldp->n_nrh = NRH_NULL;
				Node_unmap(cldh, &cldp);
				cldh = nextcldh;
				continue;
			}
			mlog(MLOG_TRACE | MLOG_TREE,
			      "rename dir %s to %s\n",
			      path1,
			      path2);
			rval = rename(path1, path2);
			if (rval) {
				mlog(MLOG_NORMAL | MLOG_WARNING, _(
				      "unable to rename dir %s "
				      "to dir %s: %s\n"),
				      path1,
				      path2,
				      strerror(errno));
				dummynrh = disown(cldh);
				assert(dummynrh == newnrh);
				adopt(persp->p_orphh, cldh, NRH_NULL);
				cldh = nextcldh;
				continue;
			}
			cldp = Node_map(cldh);
			cldp->n_flags &= ~NF_NEWORPH;
			cldp->n_lnkh = NH_NULL;
			Node_unmap(cldh, &cldp);
			Node_free(&renameh);
		}

		/* next!
		 */
		cldh = nextcldh;
	}

	return BOOL_TRUE;
}

/* will call funcp for all links to be created. will abort if funcp
 * ever returns FALSE;
 */
rv_t
tree_cb_links(xfs_ino_t ino,
	       gen_t gen,
	       int32_t ctime,
	       int32_t mtime,
	       bool_t (*funcp)(void *contextp,
				   bool_t linkpr,
				   char *path1,
				   char *path2),
	       void *contextp,
	       char *path1,
	       char *path2)
{
	nh_t hardh;
	nh_t nh;
	char *path;
	bool_t ok;
	int  rval;

	if (persp->p_truncategenpr) {
		gen = BIGGEN2GEN(gen);
	}

	/* find the hardhead
	 */
	hardh = link_hardh(ino, gen);

	/* loop through all hard links, attempting to restore/link
	 */
	path = path1;
	for (nh = hardh; nh != NH_NULL; nh = link_nexth(nh)) {
		node_t *np;
		u_char_t flags;
		char *reasonstr;

		/* get the node flags
		 */
		np = Node_map(nh);
		flags = np->n_flags;
		Node_unmap(nh, &np);

		/* build a pathname
		 */
		ok = Node2path(nh, path, _("restore"));
		if (!ok) {
			continue;
		}

		/* skip if not in selected subtree
		 */
		if (!(flags & NF_SUBTREE)) {
			mlog((MLOG_NITTY + 1) | MLOG_TREE,
			      "skipping %s (ino %llu gen %u): %s\n",
			      path,
			      ino,
			      gen,
			      "not in selected subtree");
			continue;
		}

		/* don't restore into the housekeeping directory
		 */
		if (path_beginswith(path, tranp->t_hkdir)) {
			mlog(MLOG_NORMAL | MLOG_WARNING | MLOG_TREE, _(
			      "cannot restore %s (ino %llu gen %u): "
			      "pathname contains %s\n"),
			      path,
			      ino,
			      gen,
			      tranp->t_hkdir);
			continue;
		}

		/* check if ok to overwrite: don't check if we've already
		 * been here and decided overwrite ok. if ok, set flag
		 * so we won't check again. in fact, can't check again
		 * since restore changes the answer.
		 */
		if (!(flags & NF_WRITTEN)) {
			bool_t exists;
			if (!content_overwrite_ok(path,
						     ctime,
						     mtime,
						     &reasonstr,
						     &exists)) {
				mlog(MLOG_TRACE | MLOG_TREE,
				      "skipping %s (ino %llu gen %u): %s\n",
				      path,
				      ino,
				      gen,
				      reasonstr);
				continue;
			} else {
				np = Node_map(nh);
				np->n_flags |= NF_WRITTEN;
				Node_unmap(nh, &np);

				/*
				 * We're the first stream to restore this file.
				 * Unlink it first to remove extended attributes
				 * that may have been set since the dump was
				 * taken.
				 */
				if (!tranp->t_toconlypr && exists) {
					rval = unlink(path);
					if (rval && errno != ENOENT) {
						mlog(MLOG_NORMAL |
						      MLOG_WARNING, _(
						      "unable to unlink "
						      "current file prior to "
						      "restore: "
						      "%s: %s: discarding\n"),
						      path,
						      strerror(errno));
						continue;
					}
				}
			}
		}

		/* call callback to restore file / create hard link.
		 * returns !ok if should abort.
		 */
		if (path == path2) {
			mlog(MLOG_TRACE | MLOG_TREE,
			      "link %s to %s (%llu %u)\n",
			      path1,
			      path2,
			      ino,
			      gen);
		} else {
			mlog(MLOG_TRACE | MLOG_TREE,
			      "restoring %s (%llu %u)\n",
			      path1,
			      ino,
			      gen);
		}
		ok = (*funcp)(contextp, path == path2, path1, path2);
		if (!ok) {
			return RV_NOTOK;
		}

		/* set flag, indicating node is now real
		 */
		np = Node_map(nh);
		np->n_flags |= NF_REAL;
		Node_unmap(nh, &np);

		/* switch to second path buffer, for link paths
		 */
		path = path2;
	}


	/* if not yet peeled from tape, do so: place in orphanage if
	 * no references found (i.e., hard link list empty).
	 */
	if (path == path1) {
		if (hardh != NH_NULL || persp->p_ignoreorphpr) {
			/*
			 * The file is referenced so the path is
			 * valid.  This means that if path begins
			 * with 'orphanage' the file is one of two
			 * things:
			 * 1) It's a file that really is an
			 * orphanage file from a previous restore
			 * that has now ended up on this dump tape.
			 * We don't really want to restore this file
			 * but, it's harmless to do so, it should
			 * happen rarely, and the path name is
			 * indistinguishable from ...
			 * 2) A file whose name was never resolved
			 * from root because of file corruption.
			 * Some granparent dir (parent dir of it's
			 * parent dir) was corrupted so the code that
			 * walks the trees was thus never able to set
			 * the NF_SUBTREE flag.  It then ends up here
			 * with a non-resolved name but a valid
			 * hard reference.  We really need to give
			 * the admin the opportunity to get this
			 * data since one corrupted dirnode would
			 * make the whole tree of data
			 * unreachable.  pv698761
			 */
			if (persp->p_ignoreorphpr || (strncmp(ORPH_NAME, path,
					    strlen(ORPH_NAME)) != 0)) {
				mlog(MLOG_DEBUG | MLOG_TREE,
				      "discarding %llu %u\n",
				      ino,
				      gen);
				ok = (*funcp)(contextp, BOOL_FALSE, 0, 0);
				if (!ok) {
					return RV_NOTOK;
				}
			} else {

				if (!tranp->t_toconlypr) {
					char *dir;
					char tmp[PATH_MAX];

					strcpy(tmp, path);
					dir = dirname(tmp);
					mkdir_r(dir);
				}

				mlog (MLOG_VERBOSE | MLOG_NOTE | MLOG_TREE, _(
				      "ino %llu salvaging file,"
				      " placing in %s\n"), ino, path1);
				ok = (*funcp)(contextp, path == path2,
					path1, path2);
				if (!ok) {
					return RV_NOTOK;
				}
			}
		} else {
			mlog(MLOG_VERBOSE | MLOG_NOTE | MLOG_TREE, _(
			      "ino %llu gen %u not referenced: "
			      "placing in orphanage\n"),
			      ino,
			      gen);
			nh = Node_alloc(ino,
					 gen,
					 NRH_NULL,
					 DAH_NULL,
					 NF_REAL | NF_NEWORPH);
			if (nh == NH_NULL) {
				mlog(MLOG_ERROR | MLOG_TREE, _(
				"node allocation failed when placing ino %llu"
				" in orphanage\n"), ino);
				return RV_ERROR; /* allocation failed */
			}
			link_in(nh);
			adopt(persp->p_orphh, nh, NRH_NULL);
			ok = Node2path(nh, path1, _("orphan"));
			assert(ok);
			(void)(*funcp)(contextp, BOOL_FALSE, path1, path2);
		}
	}
	return RV_OK;
}

/* uses flags cleared during directory restore (NF_DUMPEDDIR and NF_REFED)
 * to determine what directory entries are no longer needed. this can
 * be done because whenever a directory chenges, it and all of its current
 * entries are dumped. so if an entry is dumped which is a dir, but that
 * dir is not dumped, all of that directories entries are needed and so must
 * have their REFED flag cleared.
 *
 * does a recursive depth-wise descent of the tree, following this rule to
 * clear the REFED flags.
 */

static void tree_adjref_recurse(nh_t cldh,
				 bool_t pardumpedpr,
				 bool_t parrefedpr);

bool_t
tree_adjref(void)
{
	tree_adjref_recurse(persp->p_rooth, BOOL_FALSE, BOOL_TRUE);
	return BOOL_TRUE;
}

static void
tree_adjref_recurse(nh_t cldh,
		       bool_t pardumpedpr,
		       bool_t parrefedpr)
{
	nh_t grandcldh;
	bool_t clddumpedpr;
	bool_t cldrefedpr;
	{
		node_t *cldp;
		cldp = Node_map(cldh);
		if (!pardumpedpr && parrefedpr) {
			cldp->n_flags |= NF_REFED;
		}
		clddumpedpr = (int)cldp->n_flags & NF_DUMPEDDIR;
		cldrefedpr = (int)cldp->n_flags & NF_REFED;
		grandcldh = cldp->n_cldh;
		Node_unmap(cldh, &cldp);
	}
	while (grandcldh != NH_NULL) {
		node_t *grandcldp;
		nh_t nextgrandcldh;
		tree_adjref_recurse(grandcldh, clddumpedpr, cldrefedpr);
								/* RECURSION */
		grandcldp = Node_map(grandcldh);
		nextgrandcldh = grandcldp->n_sibh;
		Node_unmap(grandcldh, &grandcldp);
		grandcldh = nextgrandcldh;
	}
}

static bool_t tree_extattr_recurse(nh_t parh,
				    nh_t cldh,
				    bool_t (*cbfunc)(char *path,
							 dah_t dah),
				    char *path);

bool_t
tree_extattr(bool_t (*cbfunc)(char *path, dah_t dah), char *path)
{
	node_t *rootp;
	nh_t cldh;
	bool_t ok;

	rootp = Node_map(persp->p_rooth);
	cldh = rootp->n_cldh;
	Node_unmap(persp->p_rooth, &rootp);
	ok = tree_extattr_recurse(persp->p_rooth, cldh, cbfunc, path);

	return ok;
}

static bool_t
tree_extattr_recurse(nh_t parh,
		      nh_t cldh,
		      bool_t (*cbfunc)(char *path, dah_t dah),
		      char *path)
{
	node_t *parp;
	dah_t dah;
	bool_t ok;

	/* first update all children
	 */
	while (cldh != NH_NULL) {
		node_t *cldp;
		bool_t isdirpr;
		bool_t isselpr;
		bool_t isrealpr;
		nh_t grandcldh;
		nh_t nextcldh;

		cldp = Node_map(cldh);
		isdirpr = (cldp->n_flags & NF_ISDIR);
		isrealpr = (cldp->n_flags & NF_REAL);
		isselpr = (cldp->n_flags & NF_SUBTREE);
		grandcldh = cldp->n_cldh;
		nextcldh = cldp->n_sibh;
		Node_unmap(cldh, &cldp);

		/* if a real selected directory, recurse
		 */
		if (isdirpr && isrealpr && isselpr) {
			bool_t ok;
			ok = tree_extattr_recurse(cldh,
						   grandcldh,
						   cbfunc,
						   path);
							/* RECURSION */
			if (!ok) {
				return BOOL_FALSE;
			}
		}

		/* next!
		 */
		cldh = nextcldh;
	}

	/* now update self
	 */
	parp = Node_map(parh);
	dah = parp->n_dah;
	Node_unmap(parh, &parp);
	if (!Node2path(parh, path, _("set dir extattr"))) {
		mlog (MLOG_NORMAL | MLOG_WARNING | MLOG_TREE,  _(
		      "tree_extattr_recurse: Could not convert node to "
		      "path for %s\n"), path);
		return BOOL_TRUE;
	}
	if (dah != DAH_NULL) {
		ok = (*cbfunc)(path, dah);
	} else {
		ok = BOOL_TRUE;
	}

	return ok;
}

struct phcb {
	char *path1;
	char *path2;
	bool_t ok;
};

typedef struct phcb phcb_t;

static bool_t proc_hardlinks_cb(void *contextp, nh_t hardheadh);

static bool_t
proc_hardlinks(char *path1, char *path2)
{
	phcb_t phcb;

	/* have callback invoked for all hardheads
	 */
	phcb.path1 = path1;
	phcb.path2 = path2;
	phcb.ok = BOOL_TRUE;
	link_headiter(proc_hardlinks_cb, (void *)&phcb);
	return phcb.ok;
}

/* called for every hard head
 *
 * tes@sgi.com:
 * This code processes the hardlinks, extracting out a
 * src_list - real & !ref
 * dest_list - !real & ref
 * The src_list are the entries to delete and the dst_list
 * are the new_entries to create.
 * 1. If we have a src and a dst then we can do a rename.
 * 2. If we have extra src nodes then we can unlink them.
 * 3. If we have extra dst nodes then we can link them.
 * HOWEVER, the linking in of the new nodes is actually handled
 * in the restore_file_cb() code which on restoral creates
 * the file and all its hardlinks.
 * ALSO, I can not see how the src_list can have more than
 * 1 node in it, since in noref_elim_recurse() it unlinks all
 * extra deleted entries (real & !ref).
 * Thus, steps 2 and 3 are handled in noref_elim_recurse().
 */
static bool_t
proc_hardlinks_cb(void *contextp, nh_t hardheadh)
{
	phcb_t *phcbp = (phcb_t *)contextp;
	node_t *hardheadp;
	xfs_ino_t ino;
	gen_t gen;
	bool_t isdirpr;
	nh_t rnsrcheadh;
	nh_t rndstheadh;
	nh_t lnsrch;
	nh_t nh;
	link_iter_context_t link_iter_context;
	bool_t ok;
	int rval;

	/* skip directories
	 */
	hardheadp = Node_map(hardheadh);
	ino = hardheadp->n_ino;
	gen = hardheadp->n_gen;
	isdirpr = hardheadp->n_flags & NF_ISDIR;
	Node_unmap(hardheadh, &hardheadp);
	if (isdirpr) {
		return BOOL_TRUE;
	}

	mlog(MLOG_DEBUG | MLOG_TREE,
	      "processing hardlinks to %llu %u\n",
	      ino,
	      gen);

	/* first pass through hard link list: for each node, leave on
	 * list, unlink and place on rename src list, unlink and place on
	 * rename dst list, or unlink and discard. note a node available
	 * to link from, in case we need it.
	 */
	rnsrcheadh = NH_NULL;
	rndstheadh = NH_NULL;
	lnsrch = NH_NULL;
	link_iter_init(&link_iter_context, hardheadh);
	while ((nh = link_iter_next(&link_iter_context)) != NH_NULL) {

		node_t *np = Node_map(nh);
		bool_t isrealpr = np->n_flags & NF_REAL;
		bool_t isrefpr = np->n_flags & NF_REFED;
		bool_t isselpr = np->n_flags & NF_SUBTREE;

		/* if unrefed, unreal, free node etc. (sel doesn't matter)
		 */
		if (!isrealpr && !isrefpr) {
			mlog(MLOG_NITTY | MLOG_TREE,
			      "freeing node %x: not real, not referenced\n",
			      nh);
			link_iter_unlink(&link_iter_context, nh);
			Node_unmap(nh, &np);
			(void)disown(nh);
			Node_free(&nh);
			continue;
		}

		/* not real, refed, but not selected, can't help
		 */
		if (!isrealpr &&   isrefpr && !isselpr) {
			mlog(MLOG_NITTY | MLOG_TREE,
			      "skipping node %x: not selected\n",
			      nh);
			Node_unmap(nh, &np);
			continue;
		}

		/* if unreal, refed, sel, add to dst list,
		 */
		if (!isrealpr &&   isrefpr &&   isselpr) {
			mlog(MLOG_NITTY | MLOG_TREE,
			      "making node %x dst: "
			      "not real, refed, sel\n",
			      nh);
			link_iter_unlink(&link_iter_context, nh);
			np->n_lnkh = rndstheadh;
			rndstheadh = nh;
			Node_unmap(nh, &np);
			continue;
		}

		/* if real, unrefed, sel, add to src list
		 */
		if (isrealpr && !isrefpr &&   isselpr) {
			mlog(MLOG_NITTY | MLOG_TREE,
			      "making node %x src: real, not refed, sel\n",
			      nh);
			link_iter_unlink(&link_iter_context, nh);
			np->n_lnkh = rnsrcheadh;
			rnsrcheadh = nh;
			Node_unmap(nh, &np);
			continue;
		}

		/* would like to get rid of but not selected, or
		 * real and referenced, leave alone (sel doesn't matter).
		 * consider as a lnk src, since real and not going away.
		 */
		if (isrealpr && (isrefpr || !isselpr)) {
			mlog(MLOG_NITTY | MLOG_TREE,
			      "skipping node %x: %s\n",
			      nh,
			      isselpr ? "real and ref" : "real and not sel");
			Node_unmap(nh, &np);
			if (lnsrch == NH_NULL) {
				mlog(MLOG_NITTY | MLOG_TREE,
				      "node %x will be link src\n",
				      nh);
				lnsrch = nh;
			}
			continue;
		}
		assert(0);
	}

	/* now pass through dst list, doing renames if src list not empty,
	 * otherwise links if a lnk src available, otherwise put back in link
	 * list
	 */
	while (rndstheadh != NH_NULL) {
		nh_t dsth;
		node_t *dstp;
		bool_t successpr;

		dsth = rndstheadh;
		dstp = Node_map(dsth);
		rndstheadh = dstp->n_lnkh;
		dstp->n_lnkh = NH_NULL;
		Node_unmap(dsth, &dstp);

		/* build pathname to dst
		 */
		ok = Node2path(dsth, phcbp->path2, _("rename to"));
		if (!ok) {
			link_in(dsth);
			continue;
		}

		successpr = BOOL_FALSE;
		while (!successpr && rnsrcheadh != NH_NULL) {
			nh_t srch;
			nrh_t nrh;
			node_t *srcp;

			srch = rnsrcheadh;
			srcp = Node_map(srch);
			rnsrcheadh = srcp->n_lnkh;
			srcp->n_lnkh = NH_NULL;
			Node_unmap(srch, &srcp);

			/* build a path to src
			 */
			ok = Node2path(srch, phcbp->path1, _("rename from"));
			if (!ok) {
				link_in(srch);
				continue;
			}

			if (tranp->t_toconlypr) {
				rval = 0;
			} else {
				mlog(MLOG_TRACE | MLOG_TREE,
				      "rename nondir %s to %s\n",
				      phcbp->path1,
				      phcbp->path2);
				rval = rename(phcbp->path1,
					       phcbp->path2);
			}
			if (rval) {
				mlog(MLOG_NORMAL | MLOG_WARNING | MLOG_TREE, _(
				      "unable to rename nondir "
				      "%s to %s: %s\n"),
				      phcbp->path1,
				      phcbp->path2,
				      strerror(errno));
				link_in(srch);
				continue;
			}

			nrh = disown(srch);
			if (nrh != NRH_NULL) {
				namreg_del(nrh);
			}
			Node_free(&srch);

			successpr = BOOL_TRUE;
		}

		/* tes@sgi.com: note: loop of one iteration only
		 */
		while (!successpr && lnsrch != NH_NULL) {
			ok = Node2path(lnsrch, phcbp->path1, _("link"));

			if (!ok) {
				mlog(MLOG_NORMAL | MLOG_WARNING | MLOG_TREE, _(
				      "unable to use %s "
				      "as a hard link source\n"),
				      phcbp->path1);
				lnsrch = NH_NULL;
				continue;
			}

			if (tranp->t_toconlypr) {
				rval = 0;
			} else {
				mlog(MLOG_TRACE | MLOG_TREE,
				      "link nondir %s to %s\n",
				      phcbp->path1,
				      phcbp->path2);
				rval = link(phcbp->path1,
					     phcbp->path2);
			}
			if (rval) {
				mlog(MLOG_NORMAL | MLOG_WARNING | MLOG_TREE,
				      "unable to link nondir "
				      "%s to %s: %s\n",
				      phcbp->path1,
				      phcbp->path2,
				      strerror(errno));
				break;
			}
			successpr = BOOL_TRUE;
		}

		if (!successpr) {
			mlog(MLOG_NITTY | MLOG_TREE,
			      "no link src for node %x\n",
			      dsth);
		} else {
			dstp = Node_map(dsth);
			dstp->n_flags |= NF_REAL;
			Node_unmap(dsth, &dstp);
		}

		link_in(dsth);
	}

	/* finally, pass through remaining src list, unlinking/disowning.
	 * tes@sgi.com: don't believe this will happen as this step
	 * should now be done in noref_elim_recurse().
	 */
	while (rnsrcheadh != NH_NULL) {
		nh_t srch;
		node_t *srcp;
		bool_t ok;

		srch = rnsrcheadh;
		srcp = Node_map(srch);
		rnsrcheadh = srcp->n_lnkh;
		srcp->n_lnkh = NH_NULL;
		Node_unmap(srch, &srcp);

		ok = Node2path(srch, phcbp->path1, _("unlink"));
		if (!ok) {
			link_in(srch);
			continue;
		}

		if (tranp->t_toconlypr) {
			rval = 0;
		} else {
			mlog(MLOG_TRACE | MLOG_TREE,
			      "unlink nondir %s\n",
			      phcbp->path1);
			rval = unlink(phcbp->path1);
		}
		if (rval) {
			mlog(MLOG_NORMAL | MLOG_WARNING | MLOG_TREE, _(
			      "unable to unlink %s: %s\n"),
			      phcbp->path1,
			      strerror(errno));
			link_in(srch);
		} else {
			nrh_t nrh;
			nrh = disown(srch);
			if (nrh != NRH_NULL) {
				namreg_del(nrh);
			}
			Node_free(&srch);
		}
	}

	return BOOL_TRUE;
}

/* traverse tree depth-wise bottom-up for dirs no longer referenced.
 * if non-empty, move children to orphanage
 */
bool_t
tree_setattr(char *path)
{
	bool_t ok;
	node_t *rootp;

	ok = tree_setattr_recurse(persp->p_rooth, path);

	if (restore_rootdir_permissions && ok) {
		rootp = Node_map(persp->p_rooth);
		/* "." is cwd which is the destination dir */
		setdirattr(rootp->n_dah, ".");
		Node_unmap(persp->p_rooth, &rootp);
	}

	return ok;
}

static bool_t
tree_setattr_recurse(nh_t parh, char *path)
{
	node_t *parp = Node_map(parh);
	nh_t cldh = parp->n_cldh;
	Node_unmap(parh, &parp);
	while (cldh != NH_NULL) {
		nh_t nextcldh;

		/* get the node attributes
		 */
		node_t *cldp = Node_map(cldh);
		bool_t isdirpr = (cldp->n_flags & NF_ISDIR);
		bool_t isselpr = (cldp->n_flags & NF_SUBTREE);
		bool_t isrealpr = (cldp->n_flags & NF_REAL);
		dah_t dah = cldp->n_dah;

		/* get next cld
		 */
		nextcldh = cldp->n_sibh;
		Node_unmap(cldh, &cldp);

		/* if is a real selected dir, go ahead.
		 */
		if (isdirpr && isselpr && isrealpr) {
			bool_t ok;
			ok = tree_setattr_recurse(cldh, path); /* RECURSION */
			if (!ok) {
				Node_unmap(cldh, &cldp);
				return BOOL_FALSE;
			}
			if (dah != DAH_NULL) {
				bool_t ok;
				ok = Node2path(cldh, path, _("set dirattr"));
				if (ok) {
					setdirattr(dah, path);
				}
			}
		}

		cldh = nextcldh;
	}

	return BOOL_TRUE;
}

static void
setdirattr(dah_t dah, char *path)
{
	mode_t mode;
	struct utimbuf utimbuf;
	struct fsxattr fsxattr;
	int rval;
	size_t	hlen;
	void	*hanp;
	int fd = -1;

	if (dah == DAH_NULL)
		return;

	if (tranp->t_dstdirisxfspr) {
		if (path_to_handle(path, &hanp, &hlen)) {
			mlog(MLOG_NORMAL | MLOG_WARNING,
				_("path_to_handle of %s failed:%s\n"),
				path, strerror(errno));
		} else {
			fd = open_by_handle(hanp, hlen, O_RDONLY);
			if (fd < 0) {
				mlog(MLOG_NORMAL | MLOG_WARNING,
					_("open_by_handle of %s failed:%s\n"),
					path, strerror(errno));
			}
			free_handle(hanp, hlen);
		}
	}

	utimbuf.actime = dirattr_get_atime(dah);
	utimbuf.modtime = dirattr_get_mtime(dah);
	rval = utime(path, &utimbuf);
	if (rval) {
		mlog(MLOG_VERBOSE | MLOG_TREE, _(
		      "could not set access and modification times"
		      " of %s: %s\n"),
		      path,
		      strerror(errno));
	}
	mode = dirattr_get_mode(dah);
	if (persp->p_ownerpr) {
		rval = chown(path,
			      dirattr_get_uid(dah),
			      dirattr_get_gid(dah));
		if (rval) {
			mlog(MLOG_NORMAL | MLOG_TREE, _(
			      "chown (uid=%d, gid=%d) %s failed: %s\n"),
			      dirattr_get_uid(dah),
			      dirattr_get_gid(dah),
			      path,
			      strerror(errno));
		}
	}
	rval = chmod(path, mode);
	if (rval) {
		mlog(MLOG_NORMAL | MLOG_TREE, _(
		      "chmod %s failed: %s\n"),
		      path,
		      strerror(errno));
	}

	/* set the extended inode flags
	 */
	if (!tranp->t_dstdirisxfspr)
		return;

	memset((void *)&fsxattr, 0, sizeof(fsxattr));
	fsxattr.fsx_xflags = dirattr_get_xflags(dah);
	fsxattr.fsx_extsize = dirattr_get_extsize(dah);
	fsxattr.fsx_projid = dirattr_get_projid(dah);

	rval = ioctl(fd,
		      XFS_IOC_FSSETXATTR,
		      (void *)&fsxattr);
	if (rval < 0) {
		mlog(MLOG_NORMAL | MLOG_WARNING,
		     _("attempt to set "
		       "extended attributes "
		       "(xflags 0x%x, "
		       "extsize = 0x%x, "
		       "projid = 0x%x) "
		       "of %s failed: "
		       "%s\n"),
		     fsxattr.fsx_xflags,
		     fsxattr.fsx_extsize,
		     fsxattr.fsx_projid,
		     path,
		     strerror(errno));
	}
	(void)close(fd);
}

/* deletes orphanage if empty, else warns
 */
bool_t
tree_delorph(void)
{
	int rval;

	rval = rmdir(tranp->t_orphdir);
	if (rval) {
		if (errno == EEXIST) {
			mlog(MLOG_NORMAL | MLOG_WARNING | MLOG_TREE, _(
			     "unable to rmdir %s: not empty\n"),
			     tranp->t_orphdir);
		} else {
			mlog(MLOG_NORMAL | MLOG_WARNING | MLOG_TREE, _(
			     "unable to rmdir %s: %s\n"),
			     tranp->t_orphdir,
			     strerror(errno));
		}
	}

	return BOOL_TRUE;
}


/* definition of locally defined static functions ****************************/


/* interactive subtree abstraction *******************************************/

static void tsi_cmd_inst(void *, dlog_pcbp_t, void *);
static void tsi_cmd_pwd(void *, dlog_pcbp_t, void *);
static void tsi_cmd_ls(void *, dlog_pcbp_t, void *);
static void tsi_cmd_cd(void *, dlog_pcbp_t, void *);
static void tsi_cmd_add(void *, dlog_pcbp_t, void *);
static void tsi_cmd_delete(void *, dlog_pcbp_t, void *);
static void tsi_cmd_extract(void *, dlog_pcbp_t, void *);
static void tsi_cmd_quit(void *, dlog_pcbp_t, void *);
static void tsi_cmd_help(void *, dlog_pcbp_t, void *);
static void tsi_cmd_parse(char *);
static dlog_ucbp_t tsi_cmd_match(void);

#define PREAMBLEMAX	3
#define ACKMAX		3
#define POSTAMBLEMAX	3

bool_t
tree_subtree_inter(void)
{
	fold_t fold;
	char *preamblestr[PREAMBLEMAX];
	size_t preamblecnt;
	char *ackstr[ACKMAX];
	size_t ackcnt;
	char *postamblestr[POSTAMBLEMAX];
	size_t postamblecnt;

	dlog_ucbp_t cmdp;

restart:
	/* make the current working directory the root of the fs
	 */
	tranp->t_inter.i_cwdh = persp->p_rooth;

	/* begin the dialog
	 */
	preamblecnt = 0;
	fold_init(fold, _("subtree selection dialog"), '=');
	preamblestr[preamblecnt++ ] = "\n";
	preamblestr[preamblecnt++] = fold;
	preamblestr[preamblecnt++ ] = "\n\n";
	assert(preamblecnt <= PREAMBLEMAX);
	dlog_begin(preamblestr, preamblecnt);

	/* execute commands until time to extract or quit. always begin with
	 * an implicit instructions command. if see SIGINT, give main thread
	 * dialog a chance to decide if a session interrupt is wanted.
	 */
	cmdp = tsi_cmd_inst;
	do {
		char buf[MAXPATHLEN];
		const ix_t abortix = 1;
		const ix_t sigintix = 2;
		const ix_t okix = 3;
		ix_t responseix;

		/* execute command and get response
		 */
		responseix = dlog_string_query(cmdp,
					        0,
					        buf,
					        sizeof(buf),
					        0,
					        IXMAX,    /* timeout ix */
					        sigintix, /* sigint ix */
					        abortix,  /* sighup ix */
						abortix,  /* sigquit ix */
						okix);   /* ok ix */

		/* ack the response
		 */
		ackcnt = 0;
		if (responseix == sigintix) {
			ackstr[ackcnt++ ] = _("keyboard interrupt\n");
		} else if (responseix == abortix) {
			ackstr[ackcnt++ ] = _("abort\n");
		} else {
			assert(responseix == okix);
		}
		assert(ackcnt <= ACKMAX);
		dlog_string_ack(ackstr,
				 ackcnt);

		/* exception handling
		 */
		if (responseix != okix) {
			/* if exception, end the dialog. may restart
			 * if operator decidesd not to intr.
			 */
			postamblecnt = 0;
			fold_init(fold, _("end dialog"), '-');
			postamblestr[postamblecnt++ ] = "\n";
			postamblestr[postamblecnt++] = fold;
			postamblestr[postamblecnt++ ] = "\n\n";
			assert(postamblecnt <= POSTAMBLEMAX);
			dlog_end(postamblestr, postamblecnt);

			/* if sighup or sigquit, immediately quit
			 */
			if (responseix == abortix) {
				return BOOL_FALSE;
			}

			/* if sigint, allow main thread to decide if
			 * operator really wants to quit
			 */
			assert(responseix == sigintix);
			if (cldmgr_stop_requested()) {
				return BOOL_FALSE;
			}
			sleep(1); /* to allow main thread to begin dialog */
			mlog(MLOG_NORMAL | MLOG_BARE | MLOG_TREE,
			      ""); /* block until main thread dialog done */
			sleep(1); /* let main thread ask children to die */
			if (cldmgr_stop_requested()) {
				return BOOL_FALSE;
			}
			mlog(MLOG_DEBUG | MLOG_TREE,
			      "retrying interactive subtree selection dialog\n");
			goto restart;
		}


		tsi_cmd_parse(buf);
		cmdp = tsi_cmd_match();
		if (!cmdp) {
			cmdp = tsi_cmd_help;
		}
	} while (cmdp != tsi_cmd_quit && cmdp != tsi_cmd_extract);

	postamblecnt = 0;
	fold_init(fold, _("end dialog"), '-');
	postamblestr[postamblecnt++ ] = "\n";
	postamblestr[postamblecnt++] = fold;
	postamblestr[postamblecnt++ ] = "\n\n";
	assert(postamblecnt <= POSTAMBLEMAX);
	dlog_end(postamblestr, postamblecnt);

	/* pv 773569 - quit is not a reason to consider session
         * to be interrupted (we haven't started yet) so just unmark
         * any selected directories and return */
	if (cmdp == tsi_cmd_quit) {
		mlog(MLOG_NORMAL, _("Unmark and quit\n"));
		selsubtree(persp->p_rooth, BOOL_FALSE);
	}

	return BOOL_TRUE;
}

static void
tsi_cmd_inst(void *ctxp,
	      dlog_pcbp_t pcb,
	      void *pctxp)
{
	tsi_cmd_help(ctxp, pcb, pctxp);
}

static void
tsi_cmd_pwd(void *ctxp,
	     dlog_pcbp_t pcb,
	     void *pctxp)
{
	/* special case root
	 */
	if (tranp->t_inter.i_cwdh == persp->p_rooth) {
		(*pcb )(pctxp, "cwd is fs root\n");
		return;
	}

	/* ascend tree recursively, print path on way back
	 */
	tsi_cmd_pwd_recurse(ctxp, pcb, pctxp, tranp->t_inter.i_cwdh);
	(*pcb )(pctxp, "\n");
}

static void
tsi_cmd_pwd_recurse(void *ctxp,
		     dlog_pcbp_t pcb,
		     void *pctxp,
		     nh_t nh)
{
	node_t *np;
	register nh_t parh;
	/* REFERENCED */
	register int namelen;
	nrh_t nrh;

	assert(nh != NH_NULL);

	np = Node_map(nh);
	nrh = np->n_nrh;
	parh = np->n_parh;
	Node_unmap(nh, &np);
	if (parh != persp->p_rooth) {
		tsi_cmd_pwd_recurse(ctxp, pcb, pctxp, parh);
			/* RECURSION */
		(*pcb )(pctxp, "/");
	}
	assert(nrh != NRH_NULL);
	namelen = namreg_get(nrh,
			      tranp->t_inter.i_name,
			      sizeof(tranp->t_inter.i_name));
	assert(namelen > 0);
	(*pcb)(pctxp, tranp->t_inter.i_name);
}

/* ARGSUSED */
static void
tsi_cmd_ls(void *ctxp,
	    dlog_pcbp_t pcb,
	    void *pctxp)
{
	size_t argc = tranp->t_inter.i_argc;
	char *arg = (argc > 1) ? tranp->t_inter.i_argv[1] : 0;
	bool_t ok;

	nh_t cldh;
	nh_t parh;
	nh_t namedh;
	xfs_ino_t ino;
	bool_t isdirpr;
	bool_t isselpr;

	/* walk the tree according to the path argument, to get
	 * the named node.
	 */
	ok = tsi_walkpath(arg,
			   persp->p_rooth,
			   tranp->t_inter.i_cwdh,
			   pcb,
			   pctxp,
			   &namedh,
			   &parh,
			   &cldh,
			   &ino,
			   &isdirpr,
			   &isselpr);
	if (!ok) {
		return;
	}

	/* if named is not a dir, just display named
	 */
	if (!isdirpr) {
		(*pcb)(pctxp,
			   "    %s %10llu %s%s\n",
			   isselpr ? "*" : " ",
			   ino,
			   tranp->t_inter.i_name,
			   isdirpr ? "/" : " ");

		return;
	}

	/* iterate through the directory, printing all matching entries.
	 * hide the orphanage.
	 */
	while (cldh != NH_NULL) {
		node_t *cldp;
		nrh_t nrh;
		nh_t nextcldh;
		cldp = Node_map(cldh);
		nrh = cldp->n_nrh;
		nextcldh = cldp->n_sibh;
		isdirpr = (cldp->n_flags & NF_ISDIR);
		isselpr = (cldp->n_flags & NF_SUBTREE);
		ino = cldp->n_ino;
		Node_unmap(cldh, &cldp);
		if (cldh != persp->p_orphh) {
			/* REFERENCED */
			int namelen;
			namelen = namreg_get(nrh,
					      tranp->t_inter.i_name,
					      sizeof(tranp->t_inter.i_name));
			assert(namelen > 0);
			(*pcb)(pctxp,
				   "    %s %10llu %s%s\n",
				   isselpr ? "*" : " ",
				   ino,
				   tranp->t_inter.i_name,
				   isdirpr ? "/" : " ");
		}
		cldh = nextcldh;
	}
}

/* ARGSUSED */
static void
tsi_cmd_cd(void *ctxp,
	    dlog_pcbp_t pcb,
	    void *pctxp)
{
	size_t argc = tranp->t_inter.i_argc;
	char *arg = (argc > 1) ? tranp->t_inter.i_argv[1] : 0;

	nh_t cldh;
	nh_t parh;
	nh_t namedh;
	xfs_ino_t ino;
	bool_t isdirpr;
	bool_t isselpr;
	bool_t ok;

	/* walk the tree according to the path argument, to get
	 * the named node.
	 */
	ok = tsi_walkpath(arg,
			   persp->p_rooth,
			   tranp->t_inter.i_cwdh,
			   pcb,
			   pctxp,
			   &namedh,
			   &parh,
			   &cldh,
			   &ino,
			   &isdirpr,
			   &isselpr);
	if (!ok) {
		return;
	}

	/* if named is not a dir, complain
	 */
	if (!isdirpr) {
		assert(arg);
		(*pcb)(pctxp,
			   _("%s is not a directory\n"),
			   arg);

		return;
	}

	/* change the current working directory
	 */
	tranp->t_inter.i_cwdh = namedh;
}

/* ARGSUSED */
static void
tsi_cmd_add(void *ctxp,
	     dlog_pcbp_t pcb,
	     void *pctxp)
{
	size_t argc = tranp->t_inter.i_argc;
	char *arg = (argc > 1) ? tranp->t_inter.i_argv[1] : 0;

	nh_t cldh;
	nh_t parh;
	nh_t namedh;
	xfs_ino_t ino;
	bool_t isdirpr;
	bool_t isselpr;
	bool_t ok;

	/* walk the tree according to the path argument, to get
	 * the named node.
	 */
	ok = tsi_walkpath(arg,
			   persp->p_rooth,
			   tranp->t_inter.i_cwdh,
			   pcb,
			   pctxp,
			   &namedh,
			   &parh,
			   &cldh,
			   &ino,
			   &isdirpr,
			   &isselpr);
	if (!ok) {
		return;
	}

	selsubtree(namedh, BOOL_TRUE);
}

/* ARGSUSED */
static void
tsi_cmd_delete(void *ctxp,
		dlog_pcbp_t pcb,
		void *pctxp)
{
	size_t argc = tranp->t_inter.i_argc;
	char *arg = (argc > 1) ? tranp->t_inter.i_argv[1] : 0;

	nh_t cldh;
	nh_t parh;
	nh_t namedh;
	xfs_ino_t ino;
	bool_t isdirpr;
	bool_t isselpr;
	bool_t ok;

	/* walk the tree according to the path argument, to get
	 * the named node.
	 */
	ok = tsi_walkpath(arg,
			   persp->p_rooth,
			   tranp->t_inter.i_cwdh,
			   pcb,
			   pctxp,
			   &namedh,
			   &parh,
			   &cldh,
			   &ino,
			   &isdirpr,
			   &isselpr);
	if (!ok) {
		return;
	}

	selsubtree(namedh, BOOL_FALSE);
}

/* ARGSUSED */
static void
tsi_cmd_extract(void *ctxp,
		 dlog_pcbp_t pcb,
		 void *pctxp)
{
}

/* ARGSUSED */
static void
tsi_cmd_quit(void *ctxp,
	      dlog_pcbp_t pcb,
	      void *pctxp)
{
}

static int parse(int slotcnt, char **slotbuf, char *string);

static void
tsi_cmd_parse(char *buf)
{
	int wordcnt;

	if (!buf) {
		tranp->t_inter.i_argc = 0;
		return;
	}

	wordcnt = parse(INTER_ARGMAX, tranp->t_inter.i_argv, buf);

	tranp->t_inter.i_argc = (size_t)min(max(0, wordcnt), INTER_ARGMAX);
}

struct tsi_cmd_tbl {
	char *tct_pattern;
	char *tct_help;
	dlog_ucbp_t tct_ucb;
	size_t tct_argcmin;
	size_t tct_argcmax;
};

typedef struct tsi_cmd_tbl tsi_cmd_tbl_t;

static tsi_cmd_tbl_t tsi_cmd_tbl[] = {
	{ "pwd",	"",				tsi_cmd_pwd,	1, 1 },
	{ "ls",		"[ <path> ]",			tsi_cmd_ls,	1, 2 },
	{ "cd",		"[ <path> ]",			tsi_cmd_cd,	1, 2 },
	{ "add",	"[ <path> ]",			tsi_cmd_add,	1, 2 },
	{ "delete",	"[ <path> ]",			tsi_cmd_delete,	1, 2 },
	{ "extract",	"",				tsi_cmd_extract,1, 1 },
	{ "quit",	"",				tsi_cmd_quit,	1, 1 },
	{ "help",	"",				tsi_cmd_help,	1, 1 },
};

static dlog_ucbp_t
tsi_cmd_match(void)
{
	tsi_cmd_tbl_t *tblp = tsi_cmd_tbl;
	tsi_cmd_tbl_t *tblendp = tsi_cmd_tbl
				 +
				 sizeof(tsi_cmd_tbl)
				 /
				 sizeof(tsi_cmd_tbl[0]);

	if (tranp->t_inter.i_argc == 0) {
		return 0;
	}

	for (; tblp < tblendp; tblp++) {
		if (!strncmp(tranp->t_inter.i_argv[0],
				tblp->tct_pattern,
				strlen(tranp->t_inter.i_argv[0]))) {
			break;
		}
	}

	if (tblp == tblendp) {
		return 0;
	}

	assert(tblp->tct_argcmin != 0);
	if (tranp->t_inter.i_argc < tblp->tct_argcmin) {
		return 0;
	}

	if (tranp->t_inter.i_argc > tblp->tct_argcmax) {
		return 0;
	}

	return tblp->tct_ucb;
}

/* ARGSUSED */
static void
tsi_cmd_help(void *ctxp,
	      dlog_pcbp_t pcb,
	      void *pctxp)
{
	tsi_cmd_tbl_t *tblp = tsi_cmd_tbl;
	tsi_cmd_tbl_t *tblendp = tsi_cmd_tbl
				 +
				 sizeof(tsi_cmd_tbl)
				 /
				 sizeof(tsi_cmd_tbl[0]);

	(*pcb )(pctxp, _("the following commands are available:\n"));
	for (; tblp < tblendp; tblp++) {
		(*pcb)(pctxp,
			   "\t%s %s\n",
			   tblp->tct_pattern,
			   tblp->tct_help);
	}
}

/* walks the tree following the given path.
 * returns FALSE if syntax error encountered.
 * returns by reference handles to the named node, its parent,
 * the first child in its cld list, its ino, if it is a directory,
 * and if it is selected.
 * optionally given a dlog print func and context, to be used for diag output.
 */
static bool_t
tsi_walkpath(char *arg, nh_t rooth, nh_t cwdh,
	      dlog_pcbp_t pcb, void *pctxp,
	      nh_t *namedhp, nh_t *parhp, nh_t *cldhp,
	      xfs_ino_t *inop, bool_t *isdirprp, bool_t *isselprp)
{
	nh_t namedh;
	nh_t parh;
	nh_t cldh;
	node_t *namedp;
	char *path;
	char nbuf[NAME_MAX + 1];
	xfs_ino_t ino;
	bool_t isdirpr;
	bool_t isselpr;


	/* correct arg if ends with slash (if arg is "/", ok)
	 */
	if (arg && strlen(arg) > 1 && arg[strlen(arg) - 1] == '/') {
		arg[strlen(arg) - 1] = 0;
	}

	/* use path to walk down the path argument
	 */
	path = arg;

	/* walk the tree beginning either at the root node
	 * or at the current working directory
	 */
	if (path && *path == '/') {
		assert(rooth != NH_NULL);
		namedh = rooth;
		path++;
	} else {
		assert(cwdh != NH_NULL);
		namedh = cwdh;
	}

	/* get the parent of the starting point, and its cld list
	 */
	namedp = Node_map(namedh);
	parh = namedp->n_parh;
	cldh = namedp->n_cldh;
	ino = namedp->n_ino;
	isselpr = (namedp->n_flags & NF_SUBTREE);
	assert(namedp