/*-
 * SPDX-License-Identifier: BSD-3-Clause
 *
 * Copyright (c) 1980, 1986, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <sys/param.h>
#include <sys/sysctl.h>

#include <ufs/ufs/dinode.h>
#include <ufs/ufs/dir.h>
#include <ufs/ffs/fs.h>

#include <err.h>
#include <errno.h>
#include <stdint.h>
#include <string.h>

#include "fsck.h"

#define MINDIRSIZE	(sizeof (struct dirtemplate))

static int fix_extraneous(struct inoinfo *, struct inodesc *);
static int deleteentry(struct inodesc *);
static int blksort(const void *, const void *);
static int pass2check(struct inodesc *);

void
pass2(void)
{
	struct inode ip;
	union dinode *dp;
	struct inoinfo **inpp, *inp;
	struct inoinfo **inpend;
	struct inodesc curino;
	union dinode dino;
	int i;
	char pathbuf[MAXPATHLEN + 1];

	switch (inoinfo(UFS_ROOTINO)->ino_state) {

	case USTATE:
		pfatal("ROOT INODE UNALLOCATED");
		if (reply("ALLOCATE") == 0) {
			ckfini(0);
			exit(EEXIT);
		}
		if (allocdir(UFS_ROOTINO, UFS_ROOTINO, 0755) != UFS_ROOTINO)
			errx(EEXIT, "CANNOT ALLOCATE ROOT INODE");
		break;

	case DCLEAR:
		pfatal("DUPS/BAD IN ROOT INODE");
		if (reply("REALLOCATE")) {
			freedirino(UFS_ROOTINO, UFS_ROOTINO);
			if (allocdir(UFS_ROOTINO, UFS_ROOTINO, 0755) !=
			    UFS_ROOTINO)
				errx(EEXIT, "CANNOT ALLOCATE ROOT INODE");
			break;
		}
		if (reply("CONTINUE") == 0) {
			ckfini(0);
			exit(EEXIT);
		}
		break;

	case FSTATE:
	case FCLEAR:
	case FZLINK:
		pfatal("ROOT INODE NOT DIRECTORY");
		if (reply("REALLOCATE")) {
			freeino(UFS_ROOTINO);
			if (allocdir(UFS_ROOTINO, UFS_ROOTINO, 0755) !=
			    UFS_ROOTINO)
				errx(EEXIT, "CANNOT ALLOCATE ROOT INODE");
			break;
		}
		if (reply("FIX") == 0) {
			ckfini(0);
			exit(EEXIT);
		}
		ginode(UFS_ROOTINO, &ip);
		dp = ip.i_dp;
		DIP_SET(dp, di_mode, DIP(dp, di_mode) & ~IFMT);
		DIP_SET(dp, di_mode, DIP(dp, di_mode) | IFDIR);
		inodirty(&ip);
		irelse(&ip);
		break;

	case DSTATE:
	case DZLINK:
		break;

	default:
		errx(EEXIT, "BAD STATE %d FOR ROOT INODE",
		    inoinfo(UFS_ROOTINO)->ino_state);
	}
	inoinfo(UFS_ROOTINO)->ino_state = DFOUND;
	inoinfo(UFS_WINO)->ino_state = FSTATE;
	inoinfo(UFS_WINO)->ino_type = DT_WHT;
	/*
	 * Sort the directory list into disk block order.
	 */
	qsort((char *)inpsort, (size_t)inplast, sizeof *inpsort, blksort);
	/*
	 * Check the integrity of each directory.
	 */
	memset(&curino, 0, sizeof(struct inodesc));
	curino.id_type = DATA;
	curino.id_func = pass2check;
	inpend = &inpsort[inplast];
	for (inpp = inpsort; inpp < inpend; inpp++) {
		if (got_siginfo) {
			printf("%s: phase 2: dir %td of %d (%d%%)\n", cdevname,
			    inpp - inpsort, (int)inplast,
			    (int)((inpp - inpsort) * 100 / inplast));
			got_siginfo = 0;
		}
		if (got_sigalarm) {
			setproctitle("%s p2 %d%%", cdevname,
			    (int)((inpp - inpsort) * 100 / inplast));
			got_sigalarm = 0;
		}
		inp = *inpp;
		if (inp->i_isize == 0)
			continue;
		if (inp->i_isize < MINDIRSIZE) {
			direrror(inp->i_number, "DIRECTORY TOO SHORT");
			inp->i_isize = roundup(MINDIRSIZE, DIRBLKSIZ);
			if (reply("FIX") == 1) {
				ginode(inp->i_number, &ip);
				DIP_SET(ip.i_dp, di_size, inp->i_isize);
				inodirty(&ip);
				irelse(&ip);
			}
		} else if ((inp->i_isize & (DIRBLKSIZ - 1)) != 0) {
			getpathname(pathbuf, inp->i_number, inp->i_number);
			if (usedsoftdep)
				pfatal("%s %s: LENGTH %jd NOT MULTIPLE OF %d",
					"DIRECTORY", pathbuf,
					(intmax_t)inp->i_isize, DIRBLKSIZ);
			else
				pwarn("%s %s: LENGTH %jd NOT MULTIPLE OF %d",
					"DIRECTORY", pathbuf,
					(intmax_t)inp->i_isize, DIRBLKSIZ);
			if (preen)
				printf(" (ADJUSTED)\n");
			inp->i_isize = roundup(inp->i_isize, DIRBLKSIZ);
			if (preen || reply("ADJUST") == 1) {
				ginode(inp->i_number, &ip);
				DIP_SET(ip.i_dp, di_size,
				    roundup(inp->i_isize, DIRBLKSIZ));
				inodirty(&ip);
				irelse(&ip);
			}
		}
		dp = &dino;
		memset(dp, 0, sizeof(struct ufs2_dinode));
		DIP_SET(dp, di_mode, IFDIR);
		DIP_SET(dp, di_size, inp->i_isize);
		for (i = 0; i < MIN(inp->i_numblks, UFS_NDADDR); i++)
			DIP_SET(dp, di_db[i], inp->i_blks[i]);
		if (inp->i_numblks > UFS_NDADDR)
			for (i = 0; i < UFS_NIADDR; i++)
				DIP_SET(dp, di_ib[i],
				    inp->i_blks[UFS_NDADDR + i]);
		curino.id_number = inp->i_number;
		curino.id_parent = inp->i_parent;
		(void)ckinode(dp, &curino);
	}
	/*
	 * Now that the parents of all directories have been found,
	 * make another pass to verify the value of `..'
	 */
	for (inpp = inpsort; inpp < inpend; inpp++) {
		inp = *inpp;
		if (inp->i_parent == 0 || inp->i_isize == 0)
			continue;
		if (inoinfo(inp->i_parent)->ino_state == DFOUND &&
		    INO_IS_DUNFOUND(inp->i_number)) {
			inoinfo(inp->i_number)->ino_state = DFOUND;
			check_dirdepth(inp);
		}
		if (inp->i_dotdot == inp->i_parent ||
		    inp->i_dotdot == (ino_t)-1)
			continue;
		if (inp->i_dotdot == 0) {
			inp->i_dotdot = inp->i_parent;
			if (debug)
				fileerror(inp->i_parent, inp->i_number,
				    "DEFERRED MISSING '..' FIX");
			(void)makeentry(inp->i_number, inp->i_parent, "..");
			inoinfo(inp->i_parent)->ino_linkcnt--;
			continue;
		}
		/*
		 * Here we have:
		 *    inp->i_number is directory with bad ".." in it.
		 *    inp->i_dotdot is current value of "..".
		 *    inp->i_parent is directory to which ".." should point.
		 */
		getpathname(pathbuf, inp->i_parent, inp->i_number);
		printf("BAD INODE NUMBER FOR '..' in DIR I=%ju (%s)\n",
		    (uintmax_t)inp->i_number, pathbuf);
		getpathname(pathbuf, inp->i_dotdot, inp->i_dotdot);
		printf("CURRENTLY POINTS TO I=%ju (%s), ",
		    (uintmax_t)inp->i_dotdot, pathbuf);
		getpathname(pathbuf, inp->i_parent, inp->i_parent);
		printf("SHOULD POINT TO I=%ju (%s)",
		    (uintmax_t)inp->i_parent, pathbuf);
		if (cursnapshot != 0) {
			/*
			 * We need to:
			 *    setcwd(inp->i_number);
			 *    setdotdot(inp->i_dotdot, inp->i_parent);
			 */
			cmd.value = inp->i_number;
			if (sysctlbyname("vfs.ffs.setcwd", 0, 0,
			    &cmd, sizeof cmd) == -1) {
				/* kernel lacks support for these functions */
				printf(" (IGNORED)\n");
				continue;
			}
			cmd.value = inp->i_dotdot; /* verify same value */
			cmd.size = inp->i_parent;  /* new parent */
			if (sysctlbyname("vfs.ffs.setdotdot", 0, 0,
			    &cmd, sizeof cmd) == -1) {
				printf(" (FIX FAILED: %s)\n", strerror(errno));
				continue;
			}
			printf(" (FIXED)\n");
			inoinfo(inp->i_parent)->ino_linkcnt--;
			inp->i_dotdot = inp->i_parent;
			continue;
		}
		if (preen)
			printf(" (FIXED)\n");
		else if (reply("FIX") == 0)
			continue;
		inoinfo(inp->i_dotdot)->ino_linkcnt++;
		inoinfo(inp->i_parent)->ino_linkcnt--;
		inp->i_dotdot = inp->i_parent;
		(void)changeino(inp->i_number, "..", inp->i_parent,
		    getinoinfo(inp->i_parent)->i_depth  + 1);
	}
	/*
	 * Mark all the directories that can be found from the root.
	 */
	propagate();
}

static int
pass2check(struct inodesc *idesc)
{
	struct direct *dirp = idesc->id_dirp;
	char dirname[MAXPATHLEN + 1];
	struct inoinfo *inp;
	int n, entrysize, ret = 0;
	struct inode ip;
	union dinode *dp;
	const char *errmsg;
	struct direct proto, *newdirp;

	/*
	 * check for "."
	 */
	if (idesc->id_entryno != 0)
		goto chk1;
	if (dirp->d_ino != 0 && strcmp(dirp->d_name, ".") == 0) {
		if (dirp->d_ino != idesc->id_number) {
			direrror(idesc->id_number, "BAD INODE NUMBER FOR '.'");
			if (reply("FIX") == 1) {
				dirp->d_ino = idesc->id_number;
				ret |= ALTERED;
			}
		}
		if (dirp->d_type != DT_DIR) {
			direrror(idesc->id_number, "BAD TYPE VALUE FOR '.'");
			if (reply("FIX") == 1) {
				dirp->d_type = DT_DIR;
				ret |= ALTERED;
			}
		}
		goto chk1;
	}
	proto.d_ino = idesc->id_number;
	proto.d_type = DT_DIR;
	proto.d_namlen = 1;
	(void)strcpy(proto.d_name, ".");
	entrysize = DIRSIZ(0, &proto);
	direrror(idesc->id_number, "MISSING '.'");
	errmsg = "ADD '.' ENTRY";
	if (dirp->d_reclen < entrysize + DIRSIZ(0, dirp)) {
		/* Not enough space to add '.', replace first entry with '.' */
		if (dirp->d_ino != 0) {
			pwarn("\nFIRST ENTRY IN DIRECTORY CONTAINS %s\n",
			     dirp->d_name);
			errmsg = "REPLACE WITH '.'";
		}
		if (reply(errmsg) == 0)
			goto chk1;
		proto.d_reclen = dirp->d_reclen;
		memmove(dirp, &proto, (size_t)entrysize);
		ret |= ALTERED;
	} else {
		/* Move over first entry and add '.' entry */
		if (reply(errmsg) == 0)
			goto chk1;
		newdirp = (struct direct *)((char *)(dirp) + entrysize);
		dirp->d_reclen -= entrysize;
		memmove(newdirp, dirp, dirp->d_reclen);
		proto.d_reclen = entrysize;
		memmove(dirp, &proto, (size_t)entrysize);
		idesc->id_entryno++;
		inoinfo(idesc->id_number)->ino_linkcnt--;
		dirp = newdirp;
		ret |= ALTERED;
	}
chk1:
	if (idesc->id_entryno > 1)
		goto chk2;
	inp = getinoinfo(idesc->id_number);
	proto.d_ino = inp->i_parent;
	proto.d_type = DT_DIR;
	proto.d_namlen = 2;
	(void)strcpy(proto.d_name, "..");
	entrysize = DIRSIZ(0, &proto);
	if (idesc->id_entryno == 0) {
		n = DIRSIZ(0, dirp);
		if (dirp->d_reclen < n + entrysize)
			goto chk2;
		proto.d_reclen = dirp->d_reclen - n;
		dirp->d_reclen = n;
		idesc->id_entryno++;
		inoinfo(dirp->d_ino)->ino_linkcnt--;
		dirp = (struct direct *)((char *)(dirp) + n);
		memset(dirp, 0, (size_t)proto.d_reclen);
		dirp->d_reclen = proto.d_reclen;
	}
	if (dirp->d_ino != 0 && strcmp(dirp->d_name, "..") == 0) {
		if (dirp->d_ino >= maxino) {
			direrror(idesc->id_number, "BAD INODE NUMBER FOR '..'");
			/*
			 * If we know parent set it now, otherwise let it
			 * point to the root inode and it will get cleaned
			 * up later if that is not correct.
			 */
			if (inp->i_parent != 0)
				dirp->d_ino = inp->i_parent;
			else
				dirp->d_ino = UFS_ROOTINO;
			if (reply("FIX") == 1)
				ret |= ALTERED;
		}
		inp->i_dotdot = dirp->d_ino;
		if (dirp->d_type != DT_DIR) {
			direrror(idesc->id_number, "BAD TYPE VALUE FOR '..'");
			dirp->d_type = DT_DIR;
			if (reply("FIX") == 1)
				ret |= ALTERED;
		}
		goto chk2;
	}
	fileerror(inp->i_parent != 0 ? inp->i_parent : idesc->id_number,
	    idesc->id_number, "MISSING '..'");
	errmsg = "ADD '..' ENTRY";
	if (dirp->d_reclen < entrysize + DIRSIZ(0, dirp)) {
		/* No space to add '..', replace second entry with '..' */
		if (dirp->d_ino != 0) {
			pfatal("SECOND ENTRY IN DIRECTORY CONTAINS %s\n",
			    dirp->d_name);
			errmsg = "REPLACE WITH '..'";
		}
		if (reply(errmsg) == 0) {
			inp->i_dotdot = (ino_t)-1;
			goto chk2;
		}
		if (proto.d_ino == 0) {
			/* Defer processing until parent known */
			idesc->id_entryno++;
			if (debug)
				printf("(FIX DEFERRED)\n");
		}
		inp->i_dotdot = proto.d_ino;
		proto.d_reclen = dirp->d_reclen;
		memmove(dirp, &proto, (size_t)entrysize);
		ret |= ALTERED;
	} else {
		/* Move over second entry and add '..' entry */
		if (reply(errmsg) == 0) {
			inp->i_dotdot = (ino_t)-1;
			goto chk2;
		}
		if (proto.d_ino == 0) {
			/* Defer processing until parent known */
			idesc->id_entryno++;
			if (debug)
				printf("(FIX DEFERRED)\n");
		}
		inp->i_dotdot = proto.d_ino;
		if (dirp->d_ino == 0) {
			proto.d_reclen = dirp->d_reclen;
			memmove(dirp, &proto, (size_t)entrysize);
		} else {
			newdirp = (struct direct *)((char *)(dirp) + entrysize);
			dirp->d_reclen -= entrysize;
			memmove(newdirp, dirp, dirp->d_reclen);
			proto.d_reclen = entrysize;
			memmove(dirp, &proto, (size_t)entrysize);
			if (dirp->d_ino != 0) {
				idesc->id_entryno++;
				inoinfo(dirp->d_ino)->ino_linkcnt--;
			}
			dirp = newdirp;
		}
		ret |= ALTERED;
	}
chk2:
	if (dirp->d_ino == 0)
		return (ret|KEEPON);
	if (dirp->d_namlen <= 2 &&
	    dirp->d_name[0] == '.' &&
	    idesc->id_entryno >= 2) {
		if (dirp->d_namlen == 1) {
			direrror(idesc->id_number, "EXTRA '.' ENTRY");
			dirp->d_ino = 0;
			if (reply("FIX") == 1)
				ret |= ALTERED;
			return (KEEPON | ret);
		}
		if (dirp->d_name[1] == '.') {
			direrror(idesc->id_number, "EXTRA '..' ENTRY");
			dirp->d_ino = 0;
			if (reply("FIX") == 1)
				ret |= ALTERED;
			return (KEEPON | ret);
		}
	}
	idesc->id_entryno++;
	n = 0;
	if (dirp->d_ino >= maxino) {
		fileerror(idesc->id_number, dirp->d_ino, "I OUT OF RANGE");
		n = reply("REMOVE");
	} else if (((dirp->d_ino == UFS_WINO && dirp->d_type != DT_WHT) ||
		    (dirp->d_ino != UFS_WINO && dirp->d_type == DT_WHT))) {
		fileerror(idesc->id_number, dirp->d_ino, "BAD WHITEOUT ENTRY");
		dirp->d_ino = UFS_WINO;
		dirp->d_type = DT_WHT;
		if (reply("FIX") == 1)
			ret |= ALTERED;
	} else {
again:
		switch (inoinfo(dirp->d_ino)->ino_state) {
		case USTATE:
			if (idesc->id_entryno <= 2)
				break;
			fileerror(idesc->id_number, dirp->d_ino, "UNALLOCATED");
			n = reply("REMOVE");
			break;

		case DCLEAR:
		case FCLEAR:
			if (idesc->id_entryno <= 2)
				break;
			if (inoinfo(dirp->d_ino)->ino_state == FCLEAR)
				errmsg = "DUP/BAD";
			else if (!preen && !usedsoftdep)
				errmsg = "ZERO LENGTH DIRECTORY";
			else if (cursnapshot == 0) {
				n = 1;
				break;
			} else {
				getpathname(dirname, idesc->id_number,
				    dirp->d_ino);
				pwarn("ZERO LENGTH DIRECTORY %s I=%ju",
				    dirname, (uintmax_t)dirp->d_ino);
				/*
				 * We need to:
				 *    setcwd(idesc->id_parent);
				 *    rmdir(dirp->d_name);
				 */
				cmd.value = idesc->id_number;
				if (sysctlbyname("vfs.ffs.setcwd", 0, 0,
				    &cmd, sizeof cmd) == -1) {
					/* kernel lacks support */
					printf(" (IGNORED)\n");
					n = 1;
					break;
				}
				if (rmdir(dirp->d_name) == -1) {
					printf(" (REMOVAL FAILED: %s)\n",
					    strerror(errno));
					n = 1;
					break;
				}
				/* ".." reference to parent is removed */
				inoinfo(idesc->id_number)->ino_linkcnt--;
				printf(" (REMOVED)\n");
				break;
			}
			fileerror(idesc->id_number, dirp->d_ino, errmsg);
			if ((n = reply("REMOVE")) == 1)
				break;
			ginode(dirp->d_ino, &ip);
			dp = ip.i_dp;
			inoinfo(dirp->d_ino)->ino_state =
			   (DIP(dp, di_mode) & IFMT) == IFDIR ? DSTATE : FSTATE;
			inoinfo(dirp->d_ino)->ino_linkcnt = DIP(dp, di_nlink);
			irelse(&ip);
			goto again;

		case DSTATE:
		case DZLINK:
			if (inoinfo(idesc->id_number)->ino_state == DFOUND)
				inoinfo(dirp->d_ino)->ino_state = DFOUND;
			/* FALLTHROUGH */

		case DFOUND:
			inp = getinoinfo(dirp->d_ino);
			if (idesc->id_entryno > 2) {
				if (inp->i_parent == 0) {
					inp->i_parent = idesc->id_number;
					check_dirdepth(inp);
				} else if ((n = fix_extraneous(inp, idesc))) {
					break;
				}
			}
			/* FALLTHROUGH */

		case FSTATE:
		case FZLINK:
			if (dirp->d_type != inoinfo(dirp->d_ino)->ino_type) {
				fileerror(idesc->id_number, dirp->d_ino,
				    "BAD TYPE VALUE");
				dirp->d_type = inoinfo(dirp->d_ino)->ino_type;
				if (reply("FIX") == 1)
					ret |= ALTERED;
			}
			inoinfo(dirp->d_ino)->ino_linkcnt--;
			break;

		default:
			errx(EEXIT, "BAD STATE %d FOR INODE I=%ju",
			    inoinfo(dirp->d_ino)->ino_state,
			    (uintmax_t)dirp->d_ino);
		}
	}
	if (n == 0)
		return (ret|KEEPON);
	dirp->d_ino = 0;
	return (ret|KEEPON|ALTERED);
}

static int
fix_extraneous(struct inoinfo *inp, struct inodesc *idesc)
{
	char *cp;
	struct inode ip;
	struct inodesc dotdesc;
	char oldname[MAXPATHLEN + 1];
	char newname[MAXPATHLEN + 1];

	/*
	 * If we have not yet found "..", look it up now so we know
	 * which inode the directory itself believes is its parent.
	 */
	if (inp->i_dotdot == 0) {
		memset(&dotdesc, 0, sizeof(struct inodesc));
		dotdesc.id_type = DATA;
		dotdesc.id_number = idesc->id_dirp->d_ino;
		dotdesc.id_func = findino;
		dotdesc.id_name = strdup("..");
		ginode(dotdesc.id_number, &ip);
		if ((ckinode(ip.i_dp, &dotdesc) & FOUND))
			inp->i_dotdot = dotdesc.id_parent;
		irelse(&ip);
		free(dotdesc.id_name);
	}
	/*
	 * We have the previously found old name (inp->i_parent) and the
	 * just found new name (idesc->id_number). We have five cases:
	 * 1)  ".." is missing - can remove either name, choose to delete
	 *     new one and let fsck create ".." pointing to old name.
	 * 2) Both new and old are in same directory, choose to delete
	 *    the new name and let fsck fix ".." if it is wrong.
	 * 3) ".." does not point to the new name, so delete it and let
	 *    fsck fix ".." to point to the old one if it is wrong.
	 * 4) ".." points to the old name only, so delete the new one.
	 * 5) ".." points to the new name only, so delete the old one.
	 *
	 * For cases 1-4 we eliminate the new name;
	 * for case 5 we eliminate the old name.
	 */
	if (inp->i_dotdot == 0 ||		    /* Case 1 */
	    idesc->id_number == inp->i_parent ||    /* Case 2 */
	    inp->i_dotdot != idesc->id_number ||    /* Case 3 */
	    inp->i_dotdot == inp->i_parent) {	    /* Case 4 */
		getpathname(newname, idesc->id_number, idesc->id_number);
		if (strcmp(newname, "/") != 0)
			strcat (newname, "/");
		strcat(newname, idesc->id_dirp->d_name);
		getpathname(oldname, inp->i_number, inp->i_number);
		pwarn("%s IS AN EXTRANEOUS HARD LINK TO DIRECTORY %s",
		    newname, oldname);
		if (cursnapshot != 0) {
			/*
			 * We need to
			 *    setcwd(idesc->id_number);
			 *    unlink(idesc->id_dirp->d_name);
			 */
			cmd.value = idesc->id_number;
			if (sysctlbyname("vfs.ffs.setcwd", 0, 0,
			    &cmd, sizeof cmd) == -1) {
				printf(" (IGNORED)\n");
				return (0);
			}
			cmd.value = (intptr_t)idesc->id_dirp->d_name;
			cmd.size = inp->i_number; /* verify same name */
			if (sysctlbyname("vfs.ffs.unlink", 0, 0,
			    &cmd, sizeof cmd) == -1) {
				printf(" (UNLINK FAILED: %s)\n",
				    strerror(errno));
				return (0);
			}
			printf(" (REMOVED)\n");
			return (0);
		}
		if (preen) {
			printf(" (REMOVED)\n");
			return (1);
		}
		return (reply("REMOVE"));
	}
	/*
	 * None of the first four cases above, so must be case (5).
	 * Eliminate the old name and make the new the name the parent.
	 */
	getpathname(oldname, inp->i_parent, inp->i_number);
	getpathname(newname, inp->i_number, inp->i_number);
	pwarn("%s IS AN EXTRANEOUS HARD LINK TO DIRECTORY %s", oldname,
	    newname);
	if (cursnapshot != 0) {
		/*
		 * We need to
		 *    setcwd(inp->i_parent);
		 *    unlink(last component of oldname pathname);
		 */
		cmd.value = inp->i_parent;
		if (sysctlbyname("vfs.ffs.setcwd", 0, 0,
		    &cmd, sizeof cmd) == -1) {
			printf(" (IGNORED)\n");
			return (0);
		}
		if ((cp = strchr(oldname, '/')) == NULL) {
			printf(" (IGNORED)\n");
			return (0);
		}
		cmd.value = (intptr_t)(cp + 1);
		cmd.size = inp->i_number; /* verify same name */
		if (sysctlbyname("vfs.ffs.unlink", 0, 0,
		    &cmd, sizeof cmd) == -1) {
			printf(" (UNLINK FAILED: %s)\n",
			    strerror(errno));
			return (0);
		}
		printf(" (REMOVED)\n");
		inp->i_parent = idesc->id_number;  /* reparent to correct dir */
		return (0);
	}
	if (!preen && !reply("REMOVE"))
		return (0);
	memset(&dotdesc, 0, sizeof(struct inodesc));
	dotdesc.id_type = DATA;
	dotdesc.id_number = inp->i_parent; /* directory in which name appears */
	dotdesc.id_parent = inp->i_number; /* inode number in entry to delete */
	dotdesc.id_func = deleteentry;
	ginode(dotdesc.id_number, &ip);
	if ((ckinode(ip.i_dp, &dotdesc) & FOUND) && preen)
		printf(" (REMOVED)\n");
	irelse(&ip);
	inp->i_parent = idesc->id_number;  /* reparent to correct directory */
	inoinfo(inp->i_number)->ino_linkcnt++; /* name gone, return reference */
	return (0);
}

static int
deleteentry(struct inodesc *idesc)
{
	struct direct *dirp = idesc->id_dirp;

	if (idesc->id_entryno++ < 2 || dirp->d_ino != idesc->id_parent)
		return (KEEPON);
	dirp->d_ino = 0;
	return (ALTERED|STOP|FOUND);
}

/*
 * Routine to sort disk blocks.
 */
static int
blksort(const void *arg1, const void *arg2)
{

	return ((*(struct inoinfo * const *)arg1)->i_blks[0] -
		(*(struct inoinfo * const *)arg2)->i_blks[0]);
}