Latest version of fsck from the folks at EX-CSRG specifically Kirk Mckusick.

Don Lewis and Kirk have merges nearly all FreeBSD Fixes into Kirks sources
so there is very little that needs to be re-merged.

17 files changed, 1196 insertions, 345 deletions

diff --git a/sbin/fsck/Makefile b/sbin/fsck/Makefile
index 718656034575..694a48f1e147 100644
--- a/sbin/fsck/Makefile
+++ b/sbin/fsck/Makefile
@@ -5,6 +5,5 @@ MAN8=	fsck.0
 SRCS=	dir.c inode.c main.c pass1.c pass1b.c pass2.c pass3.c pass4.c \
 	pass5.c preen.c setup.c utilities.c ffs_subr.c ffs_tables.c
 CFLAGS+=-W
-.PATH:	${.CURDIR}/../../sys/ufs/ffs
 
 .include <bsd.prog.mk>
diff --git a/sbin/fsck/dir.c b/sbin/fsck/dir.c
index f9b8b63b68a4..ceb66e65f237 100644
--- a/sbin/fsck/dir.c
+++ b/sbin/fsck/dir.c
@@ -32,7 +32,7 @@
  */
 
 #ifndef lint
-static char sccsid[] = "@(#)dir.c	8.8 (Berkeley) 4/28/95";
+static const char sccsid[] = "@(#)dir.c	8.8 (Berkeley) 4/28/95";
 #endif /* not lint */
 
 #include <sys/param.h>
@@ -85,9 +85,9 @@ propagate()
 			inp = *inpp;
 			if (inp->i_parent == 0)
 				continue;
-			if (statemap[inp->i_parent] == DFOUND &&
-			    statemap[inp->i_number] == DSTATE) {
-				statemap[inp->i_number] = DFOUND;
+			if (inoinfo(inp->i_parent)->ino_state == DFOUND &&
+			    inoinfo(inp->i_number)->ino_state == DSTATE) {
+				inoinfo(inp->i_number)->ino_state = DFOUND;
 				change++;
 			}
 		}
@@ -120,6 +120,8 @@ dirscan(idesc)
 	idesc->id_loc = 0;
 	for (dp = fsck_readdir(idesc); dp != NULL; dp = fsck_readdir(idesc)) {
 		dsize = dp->d_reclen;
+		if (dsize > sizeof(dbuf))
+			dsize = sizeof(dbuf);
 		memmove(dbuf, dp, (size_t)dsize);
 #		if (BYTE_ORDER == LITTLE_ENDIAN)
 			if (!newinofmt) {
@@ -150,7 +152,7 @@ dirscan(idesc)
 			dirty(bp);
 			sbdirty();
 		}
-		if (n & STOP) 
+		if (n & STOP)
 			return (n);
 	}
 	return (idesc->id_filesize > 0 ? KEEPON : STOP);
@@ -232,8 +234,7 @@ dircheck(idesc, dp)
 	int spaceleft;
 
 	spaceleft = DIRBLKSIZ - (idesc->id_loc % DIRBLKSIZ);
-	if (dp->d_ino >= maxino ||
-	    dp->d_reclen == 0 ||
+	if (dp->d_reclen == 0 ||
 	    dp->d_reclen > spaceleft ||
 	    (dp->d_reclen & 0x3) != 0)
 		return (0);
@@ -303,24 +304,52 @@ adjust(idesc, lcnt)
 	register struct inodesc *idesc;
 	int lcnt;
 {
-	register struct dinode *dp;
+	struct dinode *dp;
+	int saveresolved;
 
 	dp = ginode(idesc->id_number);
 	if (dp->di_nlink == lcnt) {
-		if (linkup(idesc->id_number, (ino_t)0) == 0)
-			clri(idesc, "UNREF", 0);
-	} else {
+		/*
+		 * If we have not hit any unresolved problems, are running
+		 * in preen mode, and are on a filesystem using soft updates,
+		 * then just toss any partially allocated files.
+		 */
+		if (resolved && preen && usedsoftdep) {
+			clri(idesc, "UNREF", 1);
+			return;
+		} else {
+			/*
+			 * The filesystem can be marked clean even if
+			 * a file is not linked up, but is cleared.
+			 * Hence, resolved should not be cleared when
+			 * linkup is answered no, but clri is answered yes.
+			 */
+			saveresolved = resolved;
+			if (linkup(idesc->id_number, (ino_t)0, NULL) == 0) {
+				resolved = saveresolved;
+				clri(idesc, "UNREF", 0);
+				return;
+			}
+			/*
+			 * Account for the new reference created by linkup().
+			 */
+			dp = ginode(idesc->id_number);
+			lcnt--;
+		}
+	}
+	if (lcnt != 0) {
 		pwarn("LINK COUNT %s", (lfdir == idesc->id_number) ? lfname :
 			((dp->di_mode & IFMT) == IFDIR ? "DIR" : "FILE"));
 		pinode(idesc->id_number);
 		printf(" COUNT %d SHOULD BE %d",
 			dp->di_nlink, dp->di_nlink - lcnt);
-		if (preen) {
+		if (preen || usedsoftdep) {
 			if (lcnt < 0) {
 				printf("\n");
 				pfatal("LINK COUNT INCREASING");
 			}
-			printf(" (ADJUSTED)\n");
+			if (preen)
+				printf(" (ADJUSTED)\n");
 		}
 		if (preen || reply("ADJUST") == 1) {
 			dp->di_nlink -= lcnt;
@@ -351,7 +380,7 @@ mkentry(idesc)
 	dirp->d_ino = idesc->id_parent;	/* ino to be entered is in id_parent */
 	dirp->d_reclen = newent.d_reclen;
 	if (newinofmt)
-		dirp->d_type = typemap[idesc->id_parent];
+		dirp->d_type = inoinfo(idesc->id_parent)->ino_type;
 	else
 		dirp->d_type = 0;
 	dirp->d_namlen = newent.d_namlen;
@@ -384,23 +413,23 @@ chgino(idesc)
 		return (KEEPON);
 	dirp->d_ino = idesc->id_parent;
 	if (newinofmt)
-		dirp->d_type = typemap[idesc->id_parent];
+		dirp->d_type = inoinfo(idesc->id_parent)->ino_type;
 	else
 		dirp->d_type = 0;
 	return (ALTERED|STOP);
 }
 
 int
-linkup(orphan, parentdir)
+linkup(orphan, parentdir, name)
 	ino_t orphan;
 	ino_t parentdir;
+	char *name;
 {
 	register struct dinode *dp;
 	int lostdir;
 	ino_t oldlfdir;
 	struct inodesc idesc;
 	char tempname[BUFSIZ];
-	extern int pass4check();
 
 	memset(&idesc, 0, sizeof(struct inodesc));
 	dp = ginode(orphan);
@@ -428,6 +457,7 @@ linkup(orphan, parentdir)
 				lfdir = allocdir(ROOTINO, (ino_t)0, lfmode);
 				if (lfdir != 0) {
 					if (makeentry(ROOTINO, lfdir, lfname) != 0) {
+						numdirs++;
 						if (preen)
 							printf(" (CREATED)\n");
 					} else {
@@ -463,21 +493,21 @@ linkup(orphan, parentdir)
 		idesc.id_type = ADDR;
 		idesc.id_func = pass4check;
 		idesc.id_number = oldlfdir;
-		adjust(&idesc, lncntp[oldlfdir] + 1);
-		lncntp[oldlfdir] = 0;
+		adjust(&idesc, inoinfo(oldlfdir)->ino_linkcnt + 1);
+		inoinfo(oldlfdir)->ino_linkcnt = 0;
 		dp = ginode(lfdir);
 	}
-	if (statemap[lfdir] != DFOUND) {
+	if (inoinfo(lfdir)->ino_state != DFOUND) {
 		pfatal("SORRY. NO lost+found DIRECTORY\n\n");
 		return (0);
 	}
 	(void)lftempname(tempname, orphan);
-	if (makeentry(lfdir, orphan, tempname) == 0) {
+	if (makeentry(lfdir, orphan, (name ? name : tempname)) == 0) {
 		pfatal("SORRY. NO SPACE IN lost+found DIRECTORY");
 		printf("\n\n");
 		return (0);
 	}
-	lncntp[orphan]--;
+	inoinfo(orphan)->ino_linkcnt--;
 	if (lostdir) {
 		if ((changeino(orphan, "..", lfdir) & ALTERED) == 0 &&
 		    parentdir != (ino_t)-1)
@@ -485,10 +515,12 @@ linkup(orphan, parentdir)
 		dp = ginode(lfdir);
 		dp->di_nlink++;
 		inodirty();
-		lncntp[lfdir]++;
+		inoinfo(lfdir)->ino_linkcnt++;
 		pwarn("DIR I=%lu CONNECTED. ", orphan);
-		if (parentdir != (ino_t)-1)
-			printf("PARENT WAS I=%lu\n", parentdir);
+		if (parentdir != (ino_t)-1) {
+			printf("PARENT WAS I=%lu\n", (u_long)parentdir);
+			inoinfo(parentdir)->ino_linkcnt++;
+		}
 		if (preen == 0)
 			printf("\n");
 	}
@@ -527,7 +559,7 @@ makeentry(parent, ino, name)
 	struct dinode *dp;
 	struct inodesc idesc;
 	char pathbuf[MAXPATHLEN + 1];
-	
+
 	if (parent < ROOTINO || parent >= maxino ||
 	    ino < ROOTINO || ino >= maxino)
 		return (0);
@@ -645,19 +677,20 @@ allocdir(parent, request, mode)
 	dp->di_nlink = 2;
 	inodirty();
 	if (ino == ROOTINO) {
-		lncntp[ino] = dp->di_nlink;
+		inoinfo(ino)->ino_linkcnt = dp->di_nlink;
 		cacheino(dp, ino);
 		return(ino);
 	}
-	if (statemap[parent] != DSTATE && statemap[parent] != DFOUND) {
+	if (inoinfo(parent)->ino_state != DSTATE &&
+	    inoinfo(parent)->ino_state != DFOUND) {
 		freeino(ino);
 		return (0);
 	}
 	cacheino(dp, ino);
-	statemap[ino] = statemap[parent];
-	if (statemap[ino] == DSTATE) {
-		lncntp[ino] = dp->di_nlink;
-		lncntp[parent]++;
+	inoinfo(ino)->ino_state = inoinfo(parent)->ino_state;
+	if (inoinfo(ino)->ino_state == DSTATE) {
+		inoinfo(ino)->ino_linkcnt = dp->di_nlink;
+		inoinfo(parent)->ino_linkcnt++;
 	}
 	dp = ginode(parent);
 	dp->di_nlink++;
diff --git a/sbin/fsck/ffs_subr.c b/sbin/fsck/ffs_subr.c
new file mode 100644
index 000000000000..e0e19a2a6e64
--- /dev/null
+++ b/sbin/fsck/ffs_subr.c
@@ -0,0 +1,270 @@
+/*
+ * Copyright (c) 1982, 1986, 1989, 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. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. 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.
+ *
+ *	@(#)ffs_subr.c	8.5 (Berkeley) 3/21/95
+ */
+
+#include <sys/param.h>
+#ifndef KERNEL
+#include <sys/time.h>
+#include <ufs/ufs/dinode.h>
+#include <ufs/ffs/fs.h>
+#include "fsck.h"
+
+#else
+
+#include <sys/systm.h>
+#include <sys/vnode.h>
+#include <sys/buf.h>
+#include <ufs/ufs/quota.h>
+#include <ufs/ufs/inode.h>
+#include <ufs/ffs/fs.h>
+#include <ufs/ffs/ffs_extern.h>
+
+/*
+ * Return buffer with the contents of block "offset" from the beginning of
+ * directory "ip".  If "res" is non-zero, fill it in with a pointer to the
+ * remaining space in the directory.
+ */
+int
+ffs_blkatoff(ap)
+	struct vop_blkatoff_args /* {
+		struct vnode *a_vp;
+		off_t a_offset;
+		char **a_res;
+		struct buf **a_bpp;
+	} */ *ap;
+{
+	struct inode *ip;
+	register struct fs *fs;
+	struct buf *bp;
+	ufs_daddr_t lbn;
+	int bsize, error;
+
+	ip = VTOI(ap->a_vp);
+	fs = ip->i_fs;
+	lbn = lblkno(fs, ap->a_offset);
+	bsize = blksize(fs, ip, lbn);
+
+	*ap->a_bpp = NULL;
+	if ((error = bread(ap->a_vp, lbn, bsize, NOCRED, &bp)) != 0) {
+		brelse(bp);
+		return (error);
+	}
+	if (ap->a_res)
+		*ap->a_res = (char *)bp->b_data + blkoff(fs, ap->a_offset);
+	*ap->a_bpp = bp;
+	return (0);
+}
+#endif
+
+/*
+ * Update the frsum fields to reflect addition or deletion 
+ * of some frags.
+ */
+void
+ffs_fragacct(fs, fragmap, fraglist, cnt)
+	struct fs *fs;
+	int fragmap;
+	int32_t fraglist[];
+	int cnt;
+{
+	int inblk;
+	register int field, subfield;
+	register int siz, pos;
+
+	inblk = (int)(fragtbl[fs->fs_frag][fragmap]) << 1;
+	fragmap <<= 1;
+	for (siz = 1; siz < fs->fs_frag; siz++) {
+		if ((inblk & (1 << (siz + (fs->fs_frag % NBBY)))) == 0)
+			continue;
+		field = around[siz];
+		subfield = inside[siz];
+		for (pos = siz; pos <= fs->fs_frag; pos++) {
+			if ((fragmap & field) == subfield) {
+				fraglist[siz] += cnt;
+				pos += siz;
+				field <<= siz;
+				subfield <<= siz;
+			}
+			field <<= 1;
+			subfield <<= 1;
+		}
+	}
+}
+
+#if 0 /* defined(KERNEL) && defined(DIAGNOSTIC) */
+void
+ffs_checkoverlap(bp, ip)
+	struct buf *bp;
+	struct inode *ip;
+{
+	register struct buf *ebp, *ep;
+	register ufs_daddr_t start, last;
+	struct vnode *vp;
+
+	ebp = &buf[nbuf];
+	start = bp->b_blkno;
+	last = start + btodb(bp->b_bcount) - 1;
+	for (ep = buf; ep < ebp; ep++) {
+		if (ep == bp || (ep->b_flags & B_INVAL) ||
+		    ep->b_vp == NULL)
+			continue;
+		if (VOP_BMAP(ep->b_vp, (daddr_t)0, &vp, NULL, NULL))
+			continue;
+		if (vp != ip->i_devvp)
+			continue;
+		/* look for overlap */
+		if (ep->b_bcount == 0 || ep->b_blkno > last ||
+		    ep->b_blkno + btodb(ep->b_bcount) <= start)
+			continue;
+		vprint("Disk overlap", vp);
+		(void)printf("\tstart %d, end %d overlap start %d, end %d\n",
+			start, last, ep->b_blkno,
+			ep->b_blkno + btodb(ep->b_bcount) - 1);
+		panic("Disk buffer overlap");
+	}
+}
+#endif /* DIAGNOSTIC */
+
+/*
+ * block operations
+ *
+ * check if a block is available
+ */
+int
+ffs_isblock(fs, cp, h)
+	struct fs *fs;
+	unsigned char *cp;
+	ufs_daddr_t h;
+{
+	unsigned char mask;
+
+	switch ((int)fs->fs_frag) {
+	case 8:
+		return (cp[h] == 0xff);
+	case 4:
+		mask = 0x0f << ((h & 0x1) << 2);
+		return ((cp[h >> 1] & mask) == mask);
+	case 2:
+		mask = 0x03 << ((h & 0x3) << 1);
+		return ((cp[h >> 2] & mask) == mask);
+	case 1:
+		mask = 0x01 << (h & 0x7);
+		return ((cp[h >> 3] & mask) == mask);
+	default:
+		panic("ffs_isblock");
+		return (0);
+	}
+}
+
+/*
+ * check if a block is free
+ */
+int
+ffs_isfreeblock(fs, cp, h)
+	struct fs *fs;
+	unsigned char *cp;
+	ufs_daddr_t h;
+{
+
+	switch ((int)fs->fs_frag) {
+	case 8:
+		return (cp[h] == 0);
+	case 4:
+		return ((cp[h >> 1] & (0x0f << ((h & 0x1) << 2))) == 0);
+	case 2:
+		return ((cp[h >> 2] & (0x03 << ((h & 0x3) << 1))) == 0);
+	case 1:
+		return ((cp[h >> 3] & (0x01 << (h & 0x7))) == 0);
+	default:
+		panic("ffs_isfreeblock");
+		return (0);
+	}
+}
+
+/*
+ * take a block out of the map
+ */
+void
+ffs_clrblock(fs, cp, h)
+	struct fs *fs;
+	u_char *cp;
+	ufs_daddr_t h;
+{
+
+	switch ((int)fs->fs_frag) {
+	case 8:
+		cp[h] = 0;
+		return;
+	case 4:
+		cp[h >> 1] &= ~(0x0f << ((h & 0x1) << 2));
+		return;
+	case 2:
+		cp[h >> 2] &= ~(0x03 << ((h & 0x3) << 1));
+		return;
+	case 1:
+		cp[h >> 3] &= ~(0x01 << (h & 0x7));
+		return;
+	default:
+		panic("ffs_clrblock");
+	}
+}
+
+/*
+ * put a block into the map
+ */
+void
+ffs_setblock(fs, cp, h)
+	struct fs *fs;
+	unsigned char *cp;
+	ufs_daddr_t h;
+{
+
+	switch ((int)fs->fs_frag) {
+
+	case 8:
+		cp[h] = 0xff;
+		return;
+	case 4:
+		cp[h >> 1] |= (0x0f << ((h & 0x1) << 2));
+		return;
+	case 2:
+		cp[h >> 2] |= (0x03 << ((h & 0x3) << 1));
+		return;
+	case 1:
+		cp[h >> 3] |= (0x01 << (h & 0x7));
+		return;
+	default:
+		panic("ffs_setblock");
+	}
+}
diff --git a/sbin/fsck/ffs_tables.c b/sbin/fsck/ffs_tables.c
new file mode 100644
index 000000000000..8cf46b0150a5
--- /dev/null
+++ b/sbin/fsck/ffs_tables.c
@@ -0,0 +1,136 @@
+/*
+ * Copyright (c) 1982, 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. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. 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.
+ *
+ *	@(#)ffs_tables.c	8.1 (Berkeley) 6/11/93
+ */
+
+#include <sys/param.h>
+
+/*
+ * Bit patterns for identifying fragments in the block map
+ * used as ((map & around) == inside)
+ */
+int around[9] = {
+	0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff
+};
+int inside[9] = {
+	0x0, 0x2, 0x6, 0xe, 0x1e, 0x3e, 0x7e, 0xfe, 0x1fe
+};
+
+/*
+ * Given a block map bit pattern, the frag tables tell whether a
+ * particular size fragment is available. 
+ *
+ * used as:
+ * if ((1 << (size - 1)) & fragtbl[fs->fs_frag][map] {
+ *	at least one fragment of the indicated size is available
+ * }
+ *
+ * These tables are used by the scanc instruction on the VAX to
+ * quickly find an appropriate fragment.
+ */
+u_char fragtbl124[256] = {
+	0x00, 0x16, 0x16, 0x2a, 0x16, 0x16, 0x26, 0x4e,
+	0x16, 0x16, 0x16, 0x3e, 0x2a, 0x3e, 0x4e, 0x8a,
+	0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
+	0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
+	0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
+	0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
+	0x2a, 0x3e, 0x3e, 0x2a, 0x3e, 0x3e, 0x2e, 0x6e,
+	0x3e, 0x3e, 0x3e, 0x3e, 0x2a, 0x3e, 0x6e, 0xaa,
+	0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
+	0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
+	0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
+	0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
+	0x26, 0x36, 0x36, 0x2e, 0x36, 0x36, 0x26, 0x6e,
+	0x36, 0x36, 0x36, 0x3e, 0x2e, 0x3e, 0x6e, 0xae,
+	0x4e, 0x5e, 0x5e, 0x6e, 0x5e, 0x5e, 0x6e, 0x4e,
+	0x5e, 0x5e, 0x5e, 0x7e, 0x6e, 0x7e, 0x4e, 0xce,
+	0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
+	0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
+	0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
+	0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
+	0x16, 0x16, 0x16, 0x3e, 0x16, 0x16, 0x36, 0x5e,
+	0x16, 0x16, 0x16, 0x3e, 0x3e, 0x3e, 0x5e, 0x9e,
+	0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e,
+	0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e, 0xbe,
+	0x2a, 0x3e, 0x3e, 0x2a, 0x3e, 0x3e, 0x2e, 0x6e,
+	0x3e, 0x3e, 0x3e, 0x3e, 0x2a, 0x3e, 0x6e, 0xaa,
+	0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e,
+	0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x3e, 0x7e, 0xbe,
+	0x4e, 0x5e, 0x5e, 0x6e, 0x5e, 0x5e, 0x6e, 0x4e,
+	0x5e, 0x5e, 0x5e, 0x7e, 0x6e, 0x7e, 0x4e, 0xce,
+	0x8a, 0x9e, 0x9e, 0xaa, 0x9e, 0x9e, 0xae, 0xce,
+	0x9e, 0x9e, 0x9e, 0xbe, 0xaa, 0xbe, 0xce, 0x8a,
+};
+
+u_char fragtbl8[256] = {
+	0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04,
+	0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
+	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
+	0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
+	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
+	0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
+	0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06,
+	0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
+	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
+	0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
+	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
+	0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
+	0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06,
+	0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0a,
+	0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04,
+	0x08, 0x09, 0x09, 0x0a, 0x10, 0x11, 0x20, 0x40,
+	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
+	0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
+	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
+	0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
+	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05,
+	0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
+	0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07,
+	0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
+	0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06,
+	0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0a,
+	0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07,
+	0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0a, 0x12,
+	0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04,
+	0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0c,
+	0x08, 0x09, 0x09, 0x0a, 0x09, 0x09, 0x0a, 0x0c,
+	0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
+};
+
+/*
+ * The actual fragtbl array.
+ */
+u_char *fragtbl[MAXFRAG + 1] = {
+	0, fragtbl124, fragtbl124, 0, fragtbl124, 0, 0, 0, fragtbl8,
+};
diff --git a/sbin/fsck/fsck.8 b/sbin/fsck/fsck.8
index fd3ff07762ed..20c867fcf715 100644
--- a/sbin/fsck/fsck.8
+++ b/sbin/fsck/fsck.8
@@ -1,3 +1,4 @@
+.\"
 .\" Copyright (c) 1980, 1989, 1991, 1993
 .\"	The Regents of the University of California.  All rights reserved.
 .\"
@@ -31,7 +32,7 @@
 .\"
 .\"	@(#)fsck.8	8.4 (Berkeley) 5/9/95
 .\"
-.Dd May 9, 1995
+.Dd November 15, 1996
 .Dt FSCK 8
 .Os BSD 4
 .Sh NAME
@@ -40,13 +41,15 @@
 .Sh SYNOPSIS
 .Nm fsck
 .Fl p
+.Op Fl f
 .Op Fl m Ar mode
+.Op Ar filesystem
+.Ar ...
 .Nm fsck
+.Op Fl ny
 .Op Fl b Ar block#
 .Op Fl c Ar level
 .Op Fl l Ar maxparallel
-.Op Fl y
-.Op Fl n
 .Op Fl m Ar mode
 .Op Ar filesystem
 .Ar ...
@@ -81,7 +84,8 @@ runs on them successfully.
 The kernel takes care that only a restricted class of innocuous filesystem
 inconsistencies can happen unless hardware or software failures intervene.
 These are limited to the following:
-.Bl -item -compact
+.Pp
+.Bl -item -compact -offset indent
 .It
 Unreferenced inodes
 .It
@@ -157,32 +161,6 @@ The following flags are interpreted by
 Use the block specified immediately after the flag as
 the super block for the filesystem.  Block 32 is usually
 an alternate super block.
-.It Fl l
-Limit the number of parallel checks to the number specified in the following
-argument.
-By default, the limit is the number of disks, running one process per disk.
-If a smaller limit is given, the disks are checked round-robin, one filesystem
-at a time.
-.It Fl m
-Use the mode specified in octal immediately after the flag as the
-permission bits to use when creating the
-.Pa lost+found
-directory rather than the default 1777.
-In particular, systems that do not wish to have lost files accessible
-by all users on the system should use a more restrictive
-set of permissions such as 700.
-.It Fl y
-Assume a yes response to all questions asked by 
-.Nm fsck ;
-this should be used with great caution as this is a free license
-to continue after essentially unlimited trouble has been encountered.
-.It Fl n
-Assume a no response to all questions asked by 
-.Nm fsck
-except for
-.Ql CONTINUE? ,
-which is assumed to be affirmative;
-do not open the filesystem for writing.
 .It Fl c
 Convert the filesystem to the specified level.
 Note that the level of a filesystem can only be raised.
@@ -216,6 +194,40 @@ are being converted at once.
 The format of a filesystem can be determined from the
 first line of output from 
 .Xr dumpfs 8 .
+.It Fl f
+Force
+.Nm fsck
+to check
+.Sq clean
+filesystems when preening.
+.It Fl l
+Limit the number of parallel checks to the number specified in the following
+argument.
+By default, the limit is the number of disks, running one process per disk.
+If a smaller limit is given, the disks are checked round-robin, one filesystem
+at a time.
+.It Fl m
+Use the mode specified in octal immediately after the flag as the
+permission bits to use when creating the
+.Pa lost+found
+directory rather than the default 1777.
+In particular, systems that do not wish to have lost files accessible
+by all users on the system should use a more restrictive
+set of permissions such as 700.
+.It Fl n
+Assume a no response to all questions asked by 
+.Nm fsck
+except for
+.Ql CONTINUE? ,
+which is assumed to be affirmative;
+do not open the filesystem for writing.
+.It Fl p
+Preen filesystems (see above).
+.It Fl y
+Assume a yes response to all questions asked by 
+.Nm fsck ;
+this should be used with great caution as this is a free license
+to continue after essentially unlimited trouble has been encountered.
 .El
 .Pp
 If no filesystems are given to 
@@ -252,6 +264,8 @@ File pointing to unallocated inode.
 .It
 Inode number out of range.
 .It
+Directories with unallocated blocks (holes).
+.It
 Dot or dot-dot not the first two entries of a directory
 or having the wrong inode number.
 .El
@@ -295,7 +309,5 @@ are fully enumerated and explained in Appendix A of
 .Sh SEE ALSO
 .Xr fstab 5 ,
 .Xr fs 5 ,
-.Xr fsdb 8 ,
 .Xr newfs 8 ,
-.Xr mkfs 8 ,
 .Xr reboot 8
diff --git a/sbin/fsck/fsck.h b/sbin/fsck/fsck.h
index 21b36588b560..81b229268884 100644
--- a/sbin/fsck/fsck.h
+++ b/sbin/fsck/fsck.h
@@ -42,16 +42,35 @@
 #define	MAXBUFSPACE	40*1024	/* maximum space to allocate to buffers */
 #define	INOBUFSIZE	56*1024	/* size of buffer to read inodes in pass1 */
 
-#ifndef BUFSIZ
-#define BUFSIZ 1024
-#endif
-
+/*
+ * Each inode on the filesystem is described by the following structure.
+ * The linkcnt is initially set to the value in the inode. Each time it
+ * is found during the descent in passes 2, 3, and 4 the count is
+ * decremented. Any inodes whose count is non-zero after pass 4 needs to
+ * have its link count adjusted by the value remaining in ino_linkcnt.
+ */
+struct inostat {
+	char	ino_state;	/* state of inode, see below */
+	char	ino_type;	/* type of inode */
+	short	ino_linkcnt;	/* number of links not found */
+};
+/*
+ * Inode states.
+ */
 #define	USTATE	01		/* inode not allocated */
 #define	FSTATE	02		/* inode is file */
 #define	DSTATE	03		/* inode is directory */
 #define	DFOUND	04		/* directory found during descent */
 #define	DCLEAR	05		/* directory is to be cleared */
 #define	FCLEAR	06		/* file is to be cleared */
+/*
+ * Inode state information is contained on per cylinder group lists
+ * which are described by the following structure.
+ */
+struct inostatlist {
+	long	il_numalloced;	/* number of inodes allocated in this cg */
+	struct inostat *il_stat;/* inostat info for this cylinder group */
+} *inostathead;
 
 /*
  * buffer cache structure.
@@ -115,14 +134,14 @@ struct inodesc {
 
 /*
  * Linked list of duplicate blocks.
- * 
+ *
  * The list is composed of two parts. The first part of the
  * list (from duplist through the node pointed to by muldup)
- * contains a single copy of each duplicate block that has been 
+ * contains a single copy of each duplicate block that has been
  * found. The second part of the list (from muldup to the end)
  * contains duplicate blocks that have been found more than once.
  * To check if a block has been found as a duplicate it is only
- * necessary to search from duplist through muldup. To find the 
+ * necessary to search from duplist through muldup. To find the
  * total number of times that a block has been found as a duplicate
  * the entire list must be searched for occurences of the block
  * in question. The following diagram shows a sample list where
@@ -163,10 +182,12 @@ struct inoinfo {
 	ufs_daddr_t i_blks[1];		/* actually longer */
 } **inphead, **inpsort;
 long numdirs, listmax, inplast;
+long countdirs;			/* number of directories we actually found */
 
 char	*cdevname;		/* name of device being checked */
 long	dev_bsize;		/* computed value of DEV_BSIZE */
 long	secsize;		/* actual disk sector size */
+char	fflag;			/* force check, ignore clean flag */
 char	nflag;			/* assume a no response */
 char	yflag;			/* assume a yes response */
 int	bflag;			/* location of alternate super block */
@@ -175,7 +196,11 @@ int	cvtlevel;		/* convert to newer file system format */
 int	doinglevel1;		/* converting to new cylinder group format */
 int	doinglevel2;		/* converting to new inode format */
 int	newinofmt;		/* filesystem has new inode format */
+char	usedsoftdep;		/* just fix soft dependency inconsistencies */
 char	preen;			/* just fix normal inconsistencies */
+char	rerun;			/* rerun fsck. Only used in non-preen mode */
+int	returntosingle;		/* 1 => return to single user mode on exit */
+char	resolved;		/* cleared if unresolved changes => not clean */
 char	hotroot;		/* checking root device */
 char	havesb;			/* superblock has been read */
 int	fsmodified;		/* 1 => write done to file system */
@@ -185,10 +210,6 @@ int	fswritefd;		/* file descriptor for writing file system */
 ufs_daddr_t maxfsblock;		/* number of blocks in the file system */
 char	*blockmap;		/* ptr to primary blk allocation map */
 ino_t	maxino;			/* number of inodes in file system */
-ino_t	lastino;		/* last inode in use */
-char	*statemap;		/* ptr to inode state table */
-u_char	*typemap;		/* ptr to inode type table */
-short	*lncntp;		/* ptr to link count table */
 
 ino_t	lfdir;			/* lost & found directory inode number */
 char	*lfname;		/* lost & found directory name */
@@ -214,6 +235,7 @@ struct	dinode zino;
 
 struct fstab;
 
+
 void		adjust __P((struct inodesc *, int lcnt));
 ufs_daddr_t	allocblk __P((long frags));
 ino_t		allocdir __P((ino_t parent, ino_t request, int mode));
@@ -234,6 +256,7 @@ int		chkrange __P((ufs_daddr_t blk, int cnt));
 void		ckfini __P((int markclean));
 int		ckinode __P((struct dinode *dp, struct inodesc *));
 void		clri __P((struct inodesc *, char *type, int flag));
+int		clearentry __P((struct inodesc *));
 void		direrror __P((ino_t ino, char *errmesg));
 int		dirscan __P((struct inodesc *));
 int		dofix __P((struct inodesc *, char *msg));
@@ -257,7 +280,8 @@ void		getpathname __P((char *namebuf, ino_t curdir, ino_t ino));
 struct dinode  *ginode __P((ino_t inumber));
 void		inocleanup __P((void));
 void		inodirty __P((void));
-int		linkup __P((ino_t orphan, ino_t parentdir));
+struct inostat *inoinfo __P((ino_t inum));
+int		linkup __P((ino_t orphan, ino_t parentdir, char *name));
 int		makeentry __P((ino_t parent, ino_t ino, char *name));
 void		panic __P((const char *fmt, ...));
 void		pass1 __P((void));
@@ -273,6 +297,6 @@ void		pinode __P((ino_t ino));
 void		propagate __P((void));
 void		pwarn __P((const char *fmt, ...));
 int		reply __P((char *question));
-void		resetinodebuf __P((void));
+void		setinodebuf __P((ino_t));
 int		setup __P((char *dev));
 void		voidquit __P((int));
diff --git a/sbin/fsck/inode.c b/sbin/fsck/inode.c
index 1d40761cd72f..35840370ca6a 100644
--- a/sbin/fsck/inode.c
+++ b/sbin/fsck/inode.c
@@ -32,7 +32,7 @@
  */
 
 #ifndef lint
-static char sccsid[] = "@(#)inode.c	8.8 (Berkeley) 4/28/95";
+static const char sccsid[] = "@(#)inode.c	8.8 (Berkeley) 4/28/95";
 #endif /* not lint */
 
 #include <sys/param.h>
@@ -58,10 +58,12 @@ ckinode(dp, idesc)
 	register struct inodesc *idesc;
 {
 	ufs_daddr_t *ap;
-	long ret, n, ndb, offset;
+	int ret;
+	long n, ndb, offset;
 	struct dinode dino;
 	quad_t remsize, sizepb;
 	mode_t mode;
+	char pathbuf[MAXPATHLEN + 1];
 
 	if (idesc->id_fix != IGNORE)
 		idesc->id_fix = DONTKNOW;
@@ -69,7 +71,7 @@ ckinode(dp, idesc)
 	idesc->id_filesize = dp->di_size;
 	mode = dp->di_mode & IFMT;
 	if (mode == IFBLK || mode == IFCHR || (mode == IFLNK &&
-	    dp->di_size < sblock.fs_maxsymlinklen))
+	    dp->di_size < (unsigned)sblock.fs_maxsymlinklen))
 		return (KEEPON);
 	dino = *dp;
 	ndb = howmany(dino.di_size, sblock.fs_bsize);
@@ -79,8 +81,26 @@ ckinode(dp, idesc)
 				numfrags(&sblock, fragroundup(&sblock, offset));
 		else
 			idesc->id_numfrags = sblock.fs_frag;
-		if (*ap == 0)
+		if (*ap == 0) {
+			if (idesc->id_type == DATA && ndb >= 0) {
+				/* An empty block in a directory XXX */
+				getpathname(pathbuf, idesc->id_number,
+						idesc->id_number);
+                        	pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
+					pathbuf);
+                        	if (reply("ADJUST LENGTH") == 1) {
+					dp = ginode(idesc->id_number);
+                                	dp->di_size = (ap - &dino.di_db[0]) *
+					    sblock.fs_bsize;
+					printf(
+					    "YOU MUST RERUN FSCK AFTERWARDS\n");
+					rerun = 1;
+                                	inodirty();
+					
+                        	}
+			}
 			continue;
+		}
 		idesc->id_blkno = *ap;
 		if (idesc->id_type == ADDR)
 			ret = (*idesc->id_func)(idesc);
@@ -98,6 +118,24 @@ ckinode(dp, idesc)
 			ret = iblock(idesc, n, remsize);
 			if (ret & STOP)
 				return (ret);
+		} else {
+			if (idesc->id_type == DATA && remsize > 0) {
+				/* An empty block in a directory XXX */
+				getpathname(pathbuf, idesc->id_number,
+						idesc->id_number);
+                        	pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
+					pathbuf);
+                        	if (reply("ADJUST LENGTH") == 1) {
+					dp = ginode(idesc->id_number);
+                                	dp->di_size -= remsize;
+					remsize = 0;
+					printf(
+					    "YOU MUST RERUN FSCK AFTERWARDS\n");
+					rerun = 1;
+                                	inodirty();
+					break;
+                        	}
+			}
 		}
 		sizepb *= NINDIR(&sblock);
 		remsize -= sizepb;
@@ -117,6 +155,8 @@ iblock(idesc, ilevel, isize)
 	int i, n, (*func)(), nif;
 	quad_t sizepb;
 	char buf[BUFSIZ];
+	char pathbuf[MAXPATHLEN + 1];
+	struct dinode *dp;
 
 	if (idesc->id_type == ADDR) {
 		func = idesc->id_func;
@@ -139,7 +179,7 @@ iblock(idesc, ilevel, isize)
 			if (*ap == 0)
 				continue;
 			(void)sprintf(buf, "PARTIALLY TRUNCATED INODE I=%lu",
-				idesc->id_number);
+			    (u_long)idesc->id_number);
 			if (dofix(idesc, buf)) {
 				*ap = 0;
 				dirty(bp);
@@ -159,6 +199,25 @@ iblock(idesc, ilevel, isize)
 				bp->b_flags &= ~B_INUSE;
 				return (n);
 			}
+		} else {
+			if (idesc->id_type == DATA && isize > 0) {
+				/* An empty block in a directory XXX */
+				getpathname(pathbuf, idesc->id_number,
+						idesc->id_number);
+                        	pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
+					pathbuf);
+                        	if (reply("ADJUST LENGTH") == 1) {
+					dp = ginode(idesc->id_number);
+                                	dp->di_size -= isize;
+					isize = 0;
+					printf(
+					    "YOU MUST RERUN FSCK AFTERWARDS\n");
+					rerun = 1;
+                                	inodirty();
+					bp->b_flags &= ~B_INUSE;
+					return(STOP);
+                        	}
+			}
 		}
 		isize -= sizepb;
 	}
@@ -177,16 +236,25 @@ chkrange(blk, cnt)
 {
 	register int c;
 
-	if ((unsigned)(blk + cnt) > maxfsblock)
+	if (cnt <= 0 || blk <= 0 || blk > maxfsblock ||
+	    cnt - 1 > maxfsblock - blk)
 		return (1);
+	if (cnt > sblock.fs_frag ||
+	    fragnum(&sblock, blk) + cnt > sblock.fs_frag) {
+		if (debug)
+			printf("bad size: blk %ld, offset %ld, size %ld\n",
+				blk, fragnum(&sblock, blk), cnt);
+		return (1);
+	}
 	c = dtog(&sblock, blk);
 	if (blk < cgdmin(&sblock, c)) {
 		if ((blk + cnt) > cgsblock(&sblock, c)) {
 			if (debug) {
 				printf("blk %ld < cgdmin %ld;",
-				    blk, cgdmin(&sblock, c));
+				    (long)blk, (long)cgdmin(&sblock, c));
 				printf(" blk + cnt %ld > cgsbase %ld\n",
-				    blk + cnt, cgsblock(&sblock, c));
+				    (long)(blk + cnt),
+				    (long)cgsblock(&sblock, c));
 			}
 			return (1);
 		}
@@ -194,9 +262,9 @@ chkrange(blk, cnt)
 		if ((blk + cnt) > cgbase(&sblock, c+1)) {
 			if (debug)  {
 				printf("blk %ld >= cgdmin %ld;",
-				    blk, cgdmin(&sblock, c));
+				    (long)blk, (long)cgdmin(&sblock, c));
 				printf(" blk + cnt %ld > sblock.fs_fpg %ld\n",
-				    blk+cnt, sblock.fs_fpg);
+				    (long)(blk + cnt), (long)sblock.fs_fpg);
 			}
 			return (1);
 		}
@@ -254,20 +322,29 @@ getnextinode(inumber)
 			size = inobufsize;
 			lastinum += fullcnt;
 		}
-		(void)bread(fsreadfd, (char *)inodebuf, dblk, size); /* ??? */
+		/*
+		 * If bread returns an error, it will already have zeroed
+		 * out the buffer, so we do not need to do so here.
+		 */
+		(void)bread(fsreadfd, (char *)inodebuf, dblk, size);
 		dp = inodebuf;
 	}
 	return (dp++);
 }
 
 void
-resetinodebuf()
+setinodebuf(inum)
+	ino_t inum;
 {
 
+	if (inum % sblock.fs_ipg != 0)
+		errx(EEXIT, "bad inode number %d to setinodebuf", inum);
 	startinum = 0;
-	nextino = 0;
-	lastinum = 0;
+	nextino = inum;
+	lastinum = inum;
 	readcnt = 0;
+	if (inodebuf != NULL)
+		return;
 	inobufsize = blkroundup(&sblock, INOBUFSIZE);
 	fullcnt = inobufsize / sizeof(struct dinode);
 	readpercg = sblock.fs_ipg / fullcnt;
@@ -279,11 +356,8 @@ resetinodebuf()
 		partialcnt = fullcnt;
 		partialsize = inobufsize;
 	}
-	if (inodebuf == NULL &&
-	    (inodebuf = (struct dinode *)malloc((unsigned)inobufsize)) == NULL)
-		errx(EEXIT, "Cannot allocate space for inode buffer");
-	while (nextino < ROOTINO)
-		(void)getnextinode(nextino);
+	if ((inodebuf = (struct dinode *)malloc((unsigned)inobufsize)) == NULL)
+		errx(EEXIT, "cannot allocate space for inode buffer");
 }
 
 void
@@ -309,7 +383,7 @@ cacheino(dp, inumber)
 {
 	register struct inoinfo *inp;
 	struct inoinfo **inpp;
-	unsigned int blks;
+	int blks;
 
 	blks = howmany(dp->di_size, sblock.fs_bsize);
 	if (blks > NDADDR)
@@ -317,14 +391,11 @@ cacheino(dp, inumber)
 	inp = (struct inoinfo *)
 		malloc(sizeof(*inp) + (blks - 1) * sizeof(ufs_daddr_t));
 	if (inp == NULL)
-		return;
+		errx(EEXIT, "cannot increase directory list");
 	inpp = &inphead[inumber % numdirs];
 	inp->i_nexthash = *inpp;
 	*inpp = inp;
-	if (inumber == ROOTINO)
-		inp->i_parent = ROOTINO;
-	else
-		inp->i_parent = (ino_t)0;
+	inp->i_parent = inumber == ROOTINO ? ROOTINO : (ino_t)0;
 	inp->i_dotdot = (ino_t)0;
 	inp->i_number = inumber;
 	inp->i_isize = dp->di_size;
@@ -374,11 +445,11 @@ inocleanup()
 	free((char *)inpsort);
 	inphead = inpsort = NULL;
 }
-	
+
 void
 inodirty()
 {
-	
+
 	dirty(pbp);
 }
 
@@ -402,7 +473,7 @@ clri(idesc, type, flag)
 		n_files--;
 		(void)ckinode(dp, idesc);
 		clearinode(dp);
-		statemap[idesc->id_number] = USTATE;
+		inoinfo(idesc->id_number)->ino_state = USTATE;
 		inodirty();
 	}
 }
@@ -413,8 +484,10 @@ findname(idesc)
 {
 	register struct direct *dirp = idesc->id_dirp;
 
-	if (dirp->d_ino != idesc->id_parent)
+	if (dirp->d_ino != idesc->id_parent || idesc->id_entryno < 2) {
+		idesc->id_entryno++;
 		return (KEEPON);
+	}
 	memmove(idesc->id_name, dirp->d_name, (size_t)dirp->d_namlen + 1);
 	return (STOP|FOUND);
 }
@@ -435,6 +508,20 @@ findino(idesc)
 	return (KEEPON);
 }
 
+int
+clearentry(idesc)
+	struct inodesc *idesc;
+{
+	register struct direct *dirp = idesc->id_dirp;
+
+	if (dirp->d_ino != idesc->id_parent || idesc->id_entryno < 2) {
+		idesc->id_entryno++;
+		return (KEEPON);
+	}
+	dirp->d_ino = 0;
+	return (STOP|FOUND|ALTERED);
+}
+
 void
 pinode(ino)
 	ino_t ino;
@@ -442,9 +529,9 @@ pinode(ino)
 	register struct dinode *dp;
 	register char *p;
 	struct passwd *pw;
-	char *ctime();
+	time_t t;
 
-	printf(" I=%lu ", ino);
+	printf(" I=%lu ", (u_long)ino);
 	if (ino < ROOTINO || ino > maxino)
 		return;
 	dp = ginode(ino);
@@ -457,7 +544,8 @@ pinode(ino)
 	if (preen)
 		printf("%s: ", cdevname);
 	printf("SIZE=%qu ", dp->di_size);
-	p = ctime(&dp->di_mtime);
+	t = dp->di_mtime.tv_sec;
+	p = ctime(&t);
 	printf("MTIME=%12.12s %4.4s ", &p[4], &p[20]);
 }
 
@@ -470,14 +558,14 @@ blkerror(ino, type, blk)
 
 	pfatal("%ld %s I=%lu", blk, type, ino);
 	printf("\n");
-	switch (statemap[ino]) {
+	switch (inoinfo(ino)->ino_state) {
 
 	case FSTATE:
-		statemap[ino] = FCLEAR;
+		inoinfo(ino)->ino_state = FCLEAR;
 		return;
 
 	case DSTATE:
-		statemap[ino] = DCLEAR;
+		inoinfo(ino)->ino_state = DCLEAR;
 		return;
 
 	case FCLEAR:
@@ -485,7 +573,7 @@ blkerror(ino, type, blk)
 		return;
 
 	default:
-		errx(EEXIT, "BAD STATE %d TO BLKERR", statemap[ino]);
+		errx(EEXIT, "BAD STATE %d TO BLKERR", inoinfo(ino)->ino_state);
 		/* NOTREACHED */
 	}
 }
@@ -500,42 +588,54 @@ allocino(request, type)
 {
 	register ino_t ino;
 	register struct dinode *dp;
+	struct cg *cgp = &cgrp;
+	int cg;
 
 	if (request == 0)
 		request = ROOTINO;
-	else if (statemap[request] != USTATE)
+	else if (inoinfo(request)->ino_state != USTATE)
 		return (0);
 	for (ino = request; ino < maxino; ino++)
-		if (statemap[ino] == USTATE)
+		if (inoinfo(ino)->ino_state == USTATE)
 			break;
 	if (ino == maxino)
 		return (0);
+	cg = ino_to_cg(&sblock, ino);
+	getblk(&cgblk, cgtod(&sblock, cg), sblock.fs_cgsize);
+	if (!cg_chkmagic(cgp))
+		pfatal("CG %d: BAD MAGIC NUMBER\n", cg);
+	setbit(cg_inosused(cgp), ino % sblock.fs_ipg);
+	cgp->cg_cs.cs_nifree--;
 	switch (type & IFMT) {
 	case IFDIR:
-		statemap[ino] = DSTATE;
+		inoinfo(ino)->ino_state = DSTATE;
+		cgp->cg_cs.cs_ndir++;
 		break;
 	case IFREG:
 	case IFLNK:
-		statemap[ino] = FSTATE;
+		inoinfo(ino)->ino_state = FSTATE;
 		break;
 	default:
 		return (0);
 	}
+	cgdirty();
 	dp = ginode(ino);
 	dp->di_db[0] = allocblk((long)1);
 	if (dp->di_db[0] == 0) {
-		statemap[ino] = USTATE;
+		inoinfo(ino)->ino_state = USTATE;
 		return (0);
 	}
 	dp->di_mode = type;
-	(void)time(&dp->di_atime);
+	dp->di_flags = 0;
+	dp->di_atime.tv_sec = time(NULL);
+	dp->di_atime.tv_nsec = 0;
 	dp->di_mtime = dp->di_ctime = dp->di_atime;
 	dp->di_size = sblock.fs_fsize;
 	dp->di_blocks = btodb(sblock.fs_fsize);
 	n_files++;
 	inodirty();
 	if (newinofmt)
-		typemap[ino] = IFTODT(type);
+		inoinfo(ino)->ino_type = IFTODT(type);
 	return (ino);
 }
 
@@ -557,6 +657,6 @@ freeino(ino)
 	(void)ckinode(dp, &idesc);
 	clearinode(dp);
 	inodirty();
-	statemap[ino] = USTATE;
+	inoinfo(ino)->ino_state = USTATE;
 	n_files--;
 }
diff --git a/sbin/fsck/main.c b/sbin/fsck/main.c
index f719ac9fc88c..681ee6dcc086 100644
--- a/sbin/fsck/main.c
+++ b/sbin/fsck/main.c
@@ -32,50 +32,47 @@
  */
 
 #ifndef lint
-static char copyright[] =
+static const char copyright[] =
 "@(#) Copyright (c) 1980, 1986, 1993\n\
 	The Regents of the University of California.  All rights reserved.\n";
 #endif /* not lint */
 
 #ifndef lint
-static char sccsid[] = "@(#)main.c	8.6 (Berkeley) 5/14/95";
+static const char sccsid[] = "@(#)main.c	8.6 (Berkeley) 5/14/95";
 #endif /* not lint */
 
 #include <sys/param.h>
 #include <sys/time.h>
 #include <sys/mount.h>
+#include <sys/resource.h>
 
 #include <ufs/ufs/dinode.h>
 #include <ufs/ufs/ufsmount.h>
 #include <ufs/ffs/fs.h>
 
-#include <ctype.h>
 #include <err.h>
 #include <fstab.h>
 #include <string.h>
 
 #include "fsck.h"
 
-int	returntosingle;
-
 static int argtoi __P((int flag, char *req, char *str, int base));
 static int docheck __P((struct fstab *fsp));
 static int checkfilesys __P((char *filesys, char *mntpt, long auxdata,
 		int child));
-void main __P((int argc, char *argv[]));
+int main __P((int argc, char *argv[]));
 
-void
+int
 main(argc, argv)
 	int	argc;
 	char	*argv[];
 {
 	int ch;
 	int ret, maxrun = 0;
-	extern char *optarg;
-	extern int optind;
+	struct rlimit rlimit;
 
 	sync();
-	while ((ch = getopt(argc, argv, "dpnNyYb:c:l:m:")) != EOF) {
+	while ((ch = getopt(argc, argv, "dfpnNyYb:c:l:m:")) != -1) {
 		switch (ch) {
 		case 'p':
 			preen++;
@@ -89,11 +86,15 @@ main(argc, argv)
 		case 'c':
 			cvtlevel = argtoi('c', "conversion level", optarg, 10);
 			break;
-		
+
 		case 'd':
 			debug++;
 			break;
 
+		case 'f':
+			fflag++;
+			break;
+
 		case 'l':
 			maxrun = argtoi('l', "number", optarg, 10);
 			break;
@@ -127,9 +128,24 @@ main(argc, argv)
 		(void)signal(SIGINT, catch);
 	if (preen)
 		(void)signal(SIGQUIT, catchquit);
+	/*
+	 * Push up our allowed memory limit so we can cope
+	 * with huge filesystems.
+	 */
+	if (getrlimit(RLIMIT_DATA, &rlimit) == 0) {
+		rlimit.rlim_cur = rlimit.rlim_max;
+		(void)setrlimit(RLIMIT_DATA, &rlimit);
+	}
 	if (argc) {
-		while (argc-- > 0)
-			(void)checkfilesys(blockcheck(*argv++), 0, 0L, 0);
+		while (argc-- > 0) {
+			char *path = blockcheck(*argv);
+
+			if (path == NULL)
+				pfatal("Can't check %s\n", *argv);
+			else
+				(void)checkfilesys(path, 0, 0L, 0);
+			++argv;
+		}
 		exit(0);
 	}
 	ret = checkfstab(preen, maxrun, docheck, checkfilesys);
@@ -198,6 +214,11 @@ checkfilesys(filesys, mntpt, auxdata, child)
 		return (0);
 	}
 	/*
+	 * Cleared if any questions answered no. Used to decide if
+	 * the superblock should be marked clean.
+	 */
+	resolved = 1;
+	/*
 	 * 1: scan inodes tallying blocks used
 	 */
 	if (preen == 0) {
@@ -212,7 +233,7 @@ checkfilesys(filesys, mntpt, auxdata, child)
 	 * 1b: locate first references to duplicates, if any
 	 */
 	if (duplist) {
-		if (preen)
+		if (preen || usedsoftdep)
 			pfatal("INTERNAL ERROR: dups with -p");
 		printf("** Phase 1b - Rescan For More DUPS\n");
 		pass1b();
@@ -253,29 +274,28 @@ checkfilesys(filesys, mntpt, auxdata, child)
 	n_bfree = sblock.fs_cstotal.cs_nbfree;
 	pwarn("%ld files, %ld used, %ld free ",
 	    n_files, n_blks, n_ffree + sblock.fs_frag * n_bfree);
-	printf("(%ld frags, %ld blocks, %d.%d%% fragmentation)\n",
-	    n_ffree, n_bfree, (n_ffree * 100) / sblock.fs_dsize,
-	    ((n_ffree * 1000 + sblock.fs_dsize / 2) / sblock.fs_dsize) % 10);
+	printf("(%d frags, %d blocks, %.1f%% fragmentation)\n",
+	    n_ffree, n_bfree, n_ffree * 100.0 / sblock.fs_dsize);
 	if (debug &&
 	    (n_files -= maxino - ROOTINO - sblock.fs_cstotal.cs_nifree))
-		printf("%ld files missing\n", n_files);
+		printf("%d files missing\n", n_files);
 	if (debug) {
 		n_blks += sblock.fs_ncg *
 			(cgdmin(&sblock, 0) - cgsblock(&sblock, 0));
 		n_blks += cgsblock(&sblock, 0) - cgbase(&sblock, 0);
 		n_blks += howmany(sblock.fs_cssize, sblock.fs_fsize);
 		if (n_blks -= maxfsblock - (n_ffree + sblock.fs_frag * n_bfree))
-			printf("%ld blocks missing\n", n_blks);
+			printf("%d blocks missing\n", n_blks);
 		if (duplist != NULL) {
 			printf("The following duplicate blocks remain:");
 			for (dp = duplist; dp; dp = dp->next)
-				printf(" %ld,", dp->dup);
+				printf(" %d,", dp->dup);
 			printf("\n");
 		}
 		if (zlnhead != NULL) {
 			printf("The following zero link count inodes remain:");
 			for (zlnp = zlnhead; zlnp; zlnp = zlnp->next)
-				printf(" %lu,", zlnp->zlncnt);
+				printf(" %u,", zlnp->zlncnt);
 			printf("\n");
 		}
 	}
@@ -284,37 +304,41 @@ checkfilesys(filesys, mntpt, auxdata, child)
 	muldup = (struct dups *)0;
 	inocleanup();
 	if (fsmodified) {
-		(void)time(&sblock.fs_time);
+		sblock.fs_time = time(NULL);
 		sbdirty();
 	}
 	if (cvtlevel && sblk.b_dirty) {
-		/* 
+		/*
 		 * Write out the duplicate super blocks
 		 */
 		for (cylno = 0; cylno < sblock.fs_ncg; cylno++)
 			bwrite(fswritefd, (char *)&sblock,
 			    fsbtodb(&sblock, cgsblock(&sblock, cylno)), SBSIZE);
 	}
-	if (!hotroot) {
-		ckfini(1);
-	} else {
+	if (rerun)
+		resolved = 0;
+	flags = 0;
+	if (hotroot) {
 		struct statfs stfs_buf;
 		/*
 		 * Check to see if root is mounted read-write.
 		 */
 		if (statfs("/", &stfs_buf) == 0)
 			flags = stfs_buf.f_flags;
-		else
-			flags = 0;
-		ckfini(flags & MNT_RDONLY);
+		if ((flags & MNT_RDONLY) == 0)
+			resolved = 0;
 	}
-	free(blockmap);
-	free(statemap);
-	free((char *)lncntp);
-	if (!fsmodified)
-		return (0);
-	if (!preen)
+	ckfini(resolved);
+
+	for (cylno = 0; cylno < sblock.fs_ncg; cylno++)
+		if (inostathead[cylno].il_stat != NULL)
+			free((char *)inostathead[cylno].il_stat);
+	free((char *)inostathead);
+	inostathead = NULL;
+	if (fsmodified && !preen)
 		printf("\n***** FILE SYSTEM WAS MODIFIED *****\n");
+	if (rerun)
+		printf("\n***** PLEASE RERUN FSCK *****\n");
 	if (hotroot) {
 		struct ufs_args args;
 		int ret;
@@ -331,6 +355,8 @@ checkfilesys(filesys, mntpt, auxdata, child)
 			if (ret == 0)
 				return (0);
 		}
+		if (!fsmodified)
+			return (0);
 		if (!preen)
 			printf("\n***** REBOOT NOW *****\n");
 		sync();
diff --git a/sbin/fsck/pass1.c b/sbin/fsck/pass1.c
index 1169adbbd59d..1ce447193fc6 100644
--- a/sbin/fsck/pass1.c
+++ b/sbin/fsck/pass1.c
@@ -32,7 +32,7 @@
  */
 
 #ifndef lint
-static char sccsid[] = "@(#)pass1.c	8.6 (Berkeley) 4/28/95";
+static const char sccsid[] = "@(#)pass1.c	8.6 (Berkeley) 4/28/95";
 #endif /* not lint */
 
 #include <sys/param.h>
@@ -49,13 +49,17 @@ static char sccsid[] = "@(#)pass1.c	8.6 (Berkeley) 4/28/95";
 
 static ufs_daddr_t badblk;
 static ufs_daddr_t dupblk;
+static ino_t lastino;		/* last inode in use */
+
 static void checkinode __P((ino_t inumber, struct inodesc *));
 
 void
 pass1()
 {
+	u_int8_t *cp;
 	ino_t inumber;
-	int c, i, cgd;
+	int c, i, cgd, inosused;
+	struct inostat *info;
 	struct inodesc idesc;
 
 	/*
@@ -77,15 +81,84 @@ pass1()
 	memset(&idesc, 0, sizeof(struct inodesc));
 	idesc.id_type = ADDR;
 	idesc.id_func = pass1check;
-	inumber = 0;
 	n_files = n_blks = 0;
-	resetinodebuf();
 	for (c = 0; c < sblock.fs_ncg; c++) {
-		for (i = 0; i < sblock.fs_ipg; i++, inumber++) {
-			if (inumber < ROOTINO)
+		inumber = c * sblock.fs_ipg;
+		setinodebuf(inumber);
+		inosused = sblock.fs_ipg;
+		/*
+		 * If we are using soft updates, then we can trust the
+		 * cylinder group inode allocation maps to tell us which
+		 * inodes are allocated. We will scan the used inode map
+		 * to find the inodes that are really in use, and then
+		 * read only those inodes in from disk.
+		 */
+		if (preen && usedsoftdep) {
+			getblk(&cgblk, cgtod(&sblock, c), sblock.fs_cgsize);
+			if (!cg_chkmagic(&cgrp))
+				pfatal("CG %d: BAD MAGIC NUMBER\n", c);
+			cp = &cg_inosused(&cgrp)[(sblock.fs_ipg - 1) / NBBY];
+			for ( ; inosused > 0; inosused -= NBBY, cp--) {
+				if (*cp == 0)
+					continue;
+				for (i = 1 << (NBBY - 1); i > 0; i >>= 1) {
+					if (*cp & i)
+						break;
+					inosused--;
+				}
+				break;
+			}
+			if (inosused < 0)
+				inosused = 0;
+		}
+		/*
+		 * Allocate inoinfo structures for the allocated inodes.
+		 */
+		inostathead[c].il_numalloced = inosused;
+		if (inosused == 0) {
+			inostathead[c].il_stat = 0;
+			continue;
+		}
+		info = calloc((unsigned)inosused, sizeof(struct inostat));
+		if (info == NULL)
+			pfatal("cannot alloc %u bytes for inoinfo\n",
+			    (unsigned)(sizeof(struct inostat) * inosused));
+		inostathead[c].il_stat = info;
+		/*
+		 * Scan the allocated inodes.
+		 */
+		for (i = 0; i < inosused; i++, inumber++) {
+			if (inumber < ROOTINO) {
+				(void)getnextinode(inumber);
 				continue;
+			}
 			checkinode(inumber, &idesc);
 		}
+		lastino += 1;
+		if (inosused < sblock.fs_ipg || inumber == lastino)
+			continue;
+		/*
+		 * If we were not able to determine in advance which inodes
+		 * were in use, then reduce the size of the inoinfo structure
+		 * to the size necessary to describe the inodes that we
+		 * really found.
+		 */
+		inosused = lastino - (c * sblock.fs_ipg);
+		if (inosused < 0)
+			inosused = 0;
+		inostathead[c].il_numalloced = inosused;
+		if (inosused == 0) {
+			free(inostathead[c].il_stat);
+			inostathead[c].il_stat = 0;
+			continue;
+		}
+		info = calloc((unsigned)inosused, sizeof(struct inostat));
+		if (info == NULL)
+			pfatal("cannot alloc %u bytes for inoinfo\n",
+			    (unsigned)(sizeof(struct inostat) * inosused));
+		memmove(info, inostathead[c].il_stat, inosused * sizeof(*info));
+		free(inostathead[c].il_stat);
+		inostathead[c].il_stat = info;
 	}
 	freeinodebuf();
 }
@@ -116,7 +189,7 @@ checkinode(inumber, idesc)
 				inodirty();
 			}
 		}
-		statemap[inumber] = USTATE;
+		inoinfo(inumber)->ino_state = USTATE;
 		return;
 	}
 	lastino = inumber;
@@ -153,8 +226,8 @@ checkinode(inumber, idesc)
 				errx(EEXIT, "cannot read symlink");
 			if (debug) {
 				symbuf[dp->di_size] = 0;
-				printf("convert symlink %d(%s) of size %d\n",
-					inumber, symbuf, (long)dp->di_size);
+				printf("convert symlink %lu(%s) of size %ld\n",
+				    (u_long)inumber, symbuf, (long)dp->di_size);
 			}
 			dp = ginode(inumber);
 			memmove(dp->di_shortlink, symbuf, (long)dp->di_size);
@@ -178,7 +251,8 @@ checkinode(inumber, idesc)
 	for (j = ndb; j < NDADDR; j++)
 		if (dp->di_db[j] != 0) {
 			if (debug)
-				printf("bad direct addr: %ld\n", dp->di_db[j]);
+				printf("bad direct addr: %ld\n",
+				    (long)dp->di_db[j]);
 			goto unknown;
 		}
 	for (j = 0, ndb -= NDADDR; ndb > 0; j++)
@@ -187,19 +261,21 @@ checkinode(inumber, idesc)
 		if (dp->di_ib[j] != 0) {
 			if (debug)
 				printf("bad indirect addr: %ld\n",
-					dp->di_ib[j]);
+				    (long)dp->di_ib[j]);
 			goto unknown;
 		}
 	if (ftypeok(dp) == 0)
 		goto unknown;
 	n_files++;
-	lncntp[inumber] = dp->di_nlink;
+	inoinfo(inumber)->ino_linkcnt = dp->di_nlink;
 	if (dp->di_nlink <= 0) {
 		zlnp = (struct zlncnt *)malloc(sizeof *zlnp);
 		if (zlnp == NULL) {
 			pfatal("LINK COUNT TABLE OVERFLOW");
-			if (reply("CONTINUE") == 0)
+			if (reply("CONTINUE") == 0) {
+				ckfini(0);
 				exit(EEXIT);
+			}
 		} else {
 			zlnp->zlncnt = inumber;
 			zlnp->next = zlnhead;
@@ -208,13 +284,14 @@ checkinode(inumber, idesc)
 	}
 	if (mode == IFDIR) {
 		if (dp->di_size == 0)
-			statemap[inumber] = DCLEAR;
+			inoinfo(inumber)->ino_state = DCLEAR;
 		else
-			statemap[inumber] = DSTATE;
+			inoinfo(inumber)->ino_state = DSTATE;
 		cacheino(dp, inumber);
+		countdirs++;
 	} else
-		statemap[inumber] = FSTATE;
-	typemap[inumber] = IFTODT(mode);
+		inoinfo(inumber)->ino_state = FSTATE;
+	inoinfo(inumber)->ino_type = IFTODT(mode);
 	if (doinglevel2 &&
 	    (dp->di_ouid != (u_short)-1 || dp->di_ogid != (u_short)-1)) {
 		dp = ginode(inumber);
@@ -242,9 +319,9 @@ checkinode(inumber, idesc)
 	return;
 unknown:
 	pfatal("UNKNOWN FILE TYPE I=%lu", inumber);
-	statemap[inumber] = FCLEAR;
+	inoinfo(inumber)->ino_state = FCLEAR;
 	if (reply("CLEAR") == 1) {
-		statemap[inumber] = USTATE;
+		inoinfo(inumber)->ino_state = USTATE;
 		dp = ginode(inumber);
 		clearinode(dp);
 		inodirty();
@@ -268,8 +345,10 @@ pass1check(idesc)
 				idesc->id_number);
 			if (preen)
 				printf(" (SKIPPING)\n");
-			else if (reply("CONTINUE") == 0)
+			else if (reply("CONTINUE") == 0) {
+				ckfini(0);
 				exit(EEXIT);
+			}
 			return (STOP);
 		}
 	}
@@ -286,15 +365,19 @@ pass1check(idesc)
 					idesc->id_number);
 				if (preen)
 					printf(" (SKIPPING)\n");
-				else if (reply("CONTINUE") == 0)
+				else if (reply("CONTINUE") == 0) {
+					ckfini(0);
 					exit(EEXIT);
+				}
 				return (STOP);
 			}
 			new = (struct dups *)malloc(sizeof(struct dups));
 			if (new == NULL) {
 				pfatal("DUP TABLE OVERFLOW.");
-				if (reply("CONTINUE") == 0)
+				if (reply("CONTINUE") == 0) {
+					ckfini(0);
 					exit(EEXIT);
+				}
 				return (STOP);
 			}
 			new->dup = blkno;
diff --git a/sbin/fsck/pass1b.c b/sbin/fsck/pass1b.c
index 203fb53c37d6..65ff49c7560a 100644
--- a/sbin/fsck/pass1b.c
+++ b/sbin/fsck/pass1b.c
@@ -32,7 +32,7 @@
  */
 
 #ifndef lint
-static char sccsid[] = "@(#)pass1b.c	8.4 (Berkeley) 4/28/95";
+static const char sccsid[] = "@(#)pass1b.c	8.4 (Berkeley) 4/28/95";
 #endif /* not lint */
 
 #include <sys/param.h>
@@ -69,7 +69,7 @@ pass1b()
 			if (dp == NULL)
 				continue;
 			idesc.id_number = inumber;
-			if (statemap[inumber] != USTATE &&
+			if (inoinfo(inumber)->ino_state != USTATE &&
 			    (ckinode(dp, &idesc) & STOP))
 				return;
 		}
diff --git a/sbin/fsck/pass2.c b/sbin/fsck/pass2.c
index 27490feafa28..7a61d1d48e3a 100644
--- a/sbin/fsck/pass2.c
+++ b/sbin/fsck/pass2.c
@@ -32,7 +32,7 @@
  */
 
 #ifndef lint
-static char sccsid[] = "@(#)pass2.c	8.9 (Berkeley) 4/28/95";
+static const char sccsid[] = "@(#)pass2.c	8.9 (Berkeley) 4/28/95";
 #endif /* not lint */
 
 #include <sys/param.h>
@@ -62,12 +62,14 @@ pass2()
 	struct dinode dino;
 	char pathbuf[MAXPATHLEN + 1];
 
-	switch (statemap[ROOTINO]) {
+	switch (inoinfo(ROOTINO)->ino_state) {
 
 	case USTATE:
 		pfatal("ROOT INODE UNALLOCATED");
-		if (reply("ALLOCATE") == 0)
+		if (reply("ALLOCATE") == 0) {
+			ckfini(0);
 			exit(EEXIT);
+		}
 		if (allocdir(ROOTINO, ROOTINO, 0755) != ROOTINO)
 			errx(EEXIT, "CANNOT ALLOCATE ROOT INODE");
 		break;
@@ -80,8 +82,10 @@ pass2()
 				errx(EEXIT, "CANNOT ALLOCATE ROOT INODE");
 			break;
 		}
-		if (reply("CONTINUE") == 0)
+		if (reply("CONTINUE") == 0) {
+			ckfini(0);
 			exit(EEXIT);
+		}
 		break;
 
 	case FSTATE:
@@ -93,8 +97,10 @@ pass2()
 				errx(EEXIT, "CANNOT ALLOCATE ROOT INODE");
 			break;
 		}
-		if (reply("FIX") == 0)
+		if (reply("FIX") == 0) {
+			ckfini(0);
 			exit(EEXIT);
+		}
 		dp = ginode(ROOTINO);
 		dp->di_mode &= ~IFMT;
 		dp->di_mode |= IFDIR;
@@ -105,12 +111,13 @@ pass2()
 		break;
 
 	default:
-		errx(EEXIT, "BAD STATE %d FOR ROOT INODE", statemap[ROOTINO]);
+		errx(EEXIT, "BAD STATE %d FOR ROOT INODE",
+		    inoinfo(ROOTINO)->ino_state);
 	}
-	statemap[ROOTINO] = DFOUND;
+	inoinfo(ROOTINO)->ino_state = DFOUND;
 	if (newinofmt) {
-		statemap[WINO] = FSTATE;
-		typemap[WINO] = DT_WHT;
+		inoinfo(WINO)->ino_state = FSTATE;
+		inoinfo(WINO)->ino_type = DT_WHT;
 	}
 	/*
 	 * Sort the directory list into disk block order.
@@ -139,8 +146,14 @@ pass2()
 			}
 		} else if ((inp->i_isize & (DIRBLKSIZ - 1)) != 0) {
 			getpathname(pathbuf, inp->i_number, inp->i_number);
-			pwarn("DIRECTORY %s: LENGTH %d NOT MULTIPLE OF %d",
-				pathbuf, inp->i_isize, DIRBLKSIZ);
+			if (usedsoftdep)
+				pfatal("%s %s: LENGTH %d NOT MULTIPLE OF %d",
+					"DIRECTORY", pathbuf, inp->i_isize,
+					DIRBLKSIZ);
+			else
+				pwarn("%s %s: LENGTH %d NOT MULTIPLE OF %d",
+					"DIRECTORY", pathbuf, inp->i_isize,
+					DIRBLKSIZ);
 			if (preen)
 				printf(" (ADJUSTED)\n");
 			inp->i_isize = roundup(inp->i_isize, DIRBLKSIZ);
@@ -167,9 +180,9 @@ pass2()
 		inp = *inpp;
 		if (inp->i_parent == 0 || inp->i_isize == 0)
 			continue;
-		if (statemap[inp->i_parent] == DFOUND &&
-		    statemap[inp->i_number] == DSTATE)
-			statemap[inp->i_number] = DFOUND;
+		if (inoinfo(inp->i_parent)->ino_state == DFOUND &&
+		    inoinfo(inp->i_number)->ino_state == DSTATE)
+			inoinfo(inp->i_number)->ino_state = DFOUND;
 		if (inp->i_dotdot == inp->i_parent ||
 		    inp->i_dotdot == (ino_t)-1)
 			continue;
@@ -179,15 +192,15 @@ pass2()
 			if (reply("FIX") == 0)
 				continue;
 			(void)makeentry(inp->i_number, inp->i_parent, "..");
-			lncntp[inp->i_parent]--;
+			inoinfo(inp->i_parent)->ino_linkcnt--;
 			continue;
 		}
 		fileerror(inp->i_parent, inp->i_number,
 		    "BAD INODE NUMBER FOR '..'");
 		if (reply("FIX") == 0)
 			continue;
-		lncntp[inp->i_dotdot]++;
-		lncntp[inp->i_parent]--;
+		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);
 	}
@@ -214,10 +227,10 @@ pass2check(idesc)
 	 * If converting, set directory entry type.
 	 */
 	if (doinglevel2 && dirp->d_ino > 0 && dirp->d_ino < maxino) {
-		dirp->d_type = typemap[dirp->d_ino];
+		dirp->d_type = inoinfo(dirp->d_ino)->ino_type;
 		ret |= ALTERED;
 	}
-	/* 
+	/*
 	 * check for "."
 	 */
 	if (idesc->id_entryno != 0)
@@ -270,7 +283,7 @@ pass2check(idesc)
 		proto.d_reclen = entrysize;
 		memmove(dirp, &proto, (size_t)entrysize);
 		idesc->id_entryno++;
-		lncntp[dirp->d_ino]--;
+		inoinfo(dirp->d_ino)->ino_linkcnt--;
 		dirp = (struct direct *)((char *)(dirp) + entrysize);
 		memset(dirp, 0, (size_t)n);
 		dirp->d_reclen = n;
@@ -305,7 +318,7 @@ chk1:
 		proto.d_reclen = dirp->d_reclen - n;
 		dirp->d_reclen = n;
 		idesc->id_entryno++;
-		lncntp[dirp->d_ino]--;
+		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;
@@ -342,7 +355,7 @@ chk1:
 	}
 	idesc->id_entryno++;
 	if (dirp->d_ino != 0)
-		lncntp[dirp->d_ino]--;
+		inoinfo(dirp->d_ino)->ino_linkcnt--;
 	return (ret|KEEPON);
 chk2:
 	if (dirp->d_ino == 0)
@@ -380,7 +393,7 @@ chk2:
 			ret |= ALTERED;
 	} else {
 again:
-		switch (statemap[dirp->d_ino]) {
+		switch (inoinfo(dirp->d_ino)->ino_state) {
 		case USTATE:
 			if (idesc->id_entryno <= 2)
 				break;
@@ -392,9 +405,9 @@ again:
 		case FCLEAR:
 			if (idesc->id_entryno <= 2)
 				break;
-			if (statemap[dirp->d_ino] == FCLEAR)
+			if (inoinfo(dirp->d_ino)->ino_state == FCLEAR)
 				errmsg = "DUP/BAD";
-			else if (!preen)
+			else if (!preen && !usedsoftdep)
 				errmsg = "ZERO LENGTH DIRECTORY";
 			else {
 				n = 1;
@@ -404,14 +417,14 @@ again:
 			if ((n = reply("REMOVE")) == 1)
 				break;
 			dp = ginode(dirp->d_ino);
-			statemap[dirp->d_ino] =
+			inoinfo(dirp->d_ino)->ino_state =
 			    (dp->di_mode & IFMT) == IFDIR ? DSTATE : FSTATE;
-			lncntp[dirp->d_ino] = dp->di_nlink;
+			inoinfo(dirp->d_ino)->ino_linkcnt = dp->di_nlink;
 			goto again;
 
 		case DSTATE:
-			if (statemap[idesc->id_number] == DFOUND)
-				statemap[dirp->d_ino] = DFOUND;
+			if (inoinfo(idesc->id_number)->ino_state == DFOUND)
+				inoinfo(dirp->d_ino)->ino_state = DFOUND;
 			/* fall through */
 
 		case DFOUND:
@@ -423,9 +436,12 @@ again:
 				pwarn("%s %s %s\n", pathbuf,
 				    "IS AN EXTRANEOUS HARD LINK TO DIRECTORY",
 				    namebuf);
-				if (preen)
-					printf(" (IGNORED)\n");
-				else if ((n = reply("REMOVE")) == 1)
+				if (preen) {
+					printf(" (REMOVED)\n");
+					n = 1;
+					break;
+				}
+				if ((n = reply("REMOVE")) == 1)
 					break;
 			}
 			if (idesc->id_entryno > 2)
@@ -433,19 +449,20 @@ again:
 			/* fall through */
 
 		case FSTATE:
-			if (newinofmt && dirp->d_type != typemap[dirp->d_ino]) {
+			if (newinofmt &&
+			    dirp->d_type != inoinfo(dirp->d_ino)->ino_type) {
 				fileerror(idesc->id_number, dirp->d_ino,
 				    "BAD TYPE VALUE");
-				dirp->d_type = typemap[dirp->d_ino];
+				dirp->d_type = inoinfo(dirp->d_ino)->ino_type;
 				if (reply("FIX") == 1)
 					ret |= ALTERED;
 			}
-			lncntp[dirp->d_ino]--;
+			inoinfo(dirp->d_ino)->ino_linkcnt--;
 			break;
 
 		default:
 			errx(EEXIT, "BAD STATE %d FOR INODE I=%d",
-			    statemap[dirp->d_ino], dirp->d_ino);
+			    inoinfo(dirp->d_ino)->ino_state, dirp->d_ino);
 		}
 	}
 	if (n == 0)
diff --git a/sbin/fsck/pass3.c b/sbin/fsck/pass3.c
index e8c94467bdc5..6320755d4236 100644
--- a/sbin/fsck/pass3.c
+++ b/sbin/fsck/pass3.c
@@ -32,43 +32,84 @@
  */
 
 #ifndef lint
-static char sccsid[] = "@(#)pass3.c	8.2 (Berkeley) 4/27/95";
+static const char sccsid[] = "@(#)pass3.c	8.2 (Berkeley) 4/27/95";
 #endif /* not lint */
 
 #include <sys/param.h>
 #include <sys/time.h>
 
 #include <ufs/ufs/dinode.h>
+#include <ufs/ufs/dir.h>
 #include <ufs/ffs/fs.h>
 
+#include <string.h>
+
 #include "fsck.h"
 
 void
 pass3()
 {
-	register struct inoinfo **inpp, *inp;
+	struct inoinfo *inp;
+	int loopcnt, inpindex, state;
 	ino_t orphan;
-	int loopcnt;
+	struct inodesc idesc;
+	char namebuf[MAXNAMLEN+1];
 
-	for (inpp = &inpsort[inplast - 1]; inpp >= inpsort; inpp--) {
-		inp = *inpp;
+	for (inpindex = inplast - 1; inpindex >= 0; inpindex--) {
+		inp = inpsort[inpindex];
+		state = inoinfo(inp->i_number)->ino_state;
 		if (inp->i_number == ROOTINO ||
-		    !(inp->i_parent == 0 || statemap[inp->i_number] == DSTATE))
+		    (inp->i_parent != 0 && state != DSTATE))
+			continue;
+		if (state == DCLEAR)
 			continue;
-		if (statemap[inp->i_number] == DCLEAR)
+		/*
+		 * If we are running with soft updates and we come
+		 * across unreferenced directories, we just leave
+		 * them in DSTATE which will cause them to be pitched
+		 * in pass 4.
+		 */
+		if (preen && resolved && usedsoftdep && state == DSTATE) {
+			if (inp->i_dotdot >= ROOTINO)
+				inoinfo(inp->i_dotdot)->ino_linkcnt++;
 			continue;
+		}
 		for (loopcnt = 0; ; loopcnt++) {
 			orphan = inp->i_number;
 			if (inp->i_parent == 0 ||
-			    statemap[inp->i_parent] != DSTATE ||
-			    loopcnt > numdirs)
+			    inoinfo(inp->i_parent)->ino_state != DSTATE ||
+			    loopcnt > countdirs)
 				break;
 			inp = getinoinfo(inp->i_parent);
 		}
-		(void)linkup(orphan, inp->i_dotdot);
-		inp->i_parent = inp->i_dotdot = lfdir;
-		lncntp[lfdir]--;
-		statemap[orphan] = DFOUND;
+		if (loopcnt <= countdirs) {
+			if (linkup(orphan, inp->i_dotdot, NULL)) {
+				inp->i_parent = inp->i_dotdot = lfdir;
+				inoinfo(lfdir)->ino_linkcnt--;
+			}
+			inoinfo(orphan)->ino_state = DFOUND;
+			propagate();
+			continue;
+		}
+		pfatal("ORPHANED DIRECTORY LOOP DETECTED I=%lu", orphan);
+		if (reply("RECONNECT") == 0)
+			continue;
+		memset(&idesc, 0, sizeof(struct inodesc));
+		idesc.id_type = DATA;
+		idesc.id_number = inp->i_parent;
+		idesc.id_parent = orphan;
+		idesc.id_func = findname;
+		idesc.id_name = namebuf;
+		if ((ckinode(ginode(inp->i_parent), &idesc) & FOUND) == 0)
+			pfatal("COULD NOT FIND NAME IN PARENT DIRECTORY");
+		if (linkup(orphan, inp->i_parent, namebuf)) {
+			idesc.id_func = clearentry;
+			if (ckinode(ginode(inp->i_parent), &idesc) & FOUND)
+				inoinfo(orphan)->ino_linkcnt++;
+			inp->i_parent = inp->i_dotdot = lfdir;
+			inoinfo(lfdir)->ino_linkcnt--;
+		}
+		inoinfo(orphan)->ino_state = DFOUND;
 		propagate();
 	}
 }
diff --git a/sbin/fsck/pass4.c b/sbin/fsck/pass4.c
index 97bc7d01ac44..48c5090ae522 100644
--- a/sbin/fsck/pass4.c
+++ b/sbin/fsck/pass4.c
@@ -32,7 +32,7 @@
  */
 
 #ifndef lint
-static char sccsid[] = "@(#)pass4.c	8.4 (Berkeley) 4/28/95";
+static const char sccsid[] = "@(#)pass4.c	8.4 (Berkeley) 4/28/95";
 #endif /* not lint */
 
 #include <sys/param.h>
@@ -53,22 +53,27 @@ pass4()
 	register struct zlncnt *zlnp;
 	struct dinode *dp;
 	struct inodesc idesc;
-	int n;
+	int i, n, cg;
 
 	memset(&idesc, 0, sizeof(struct inodesc));
 	idesc.id_type = ADDR;
 	idesc.id_func = pass4check;
-	for (inumber = ROOTINO; inumber <= lastino; inumber++) {
-		idesc.id_number = inumber;
-		switch (statemap[inumber]) {
+	for (cg = 0; cg < sblock.fs_ncg; cg++) {
+		inumber = cg * sblock.fs_ipg;
+		for (i = 0; i < inostathead[cg].il_numalloced; i++, inumber++) {
+			if (inumber < ROOTINO)
+				continue;
+			idesc.id_number = inumber;
+			switch (inoinfo(inumber)->ino_state) {
 
-		case FSTATE:
-		case DFOUND:
-			n = lncntp[inumber];
-			if (n)
-				adjust(&idesc, (short)n);
-			else {
-				for (zlnp = zlnhead; zlnp; zlnp = zlnp->next)
+			case FSTATE:
+			case DFOUND:
+				n = inoinfo(inumber)->ino_linkcnt;
+				if (n) {
+					adjust(&idesc, (short)n);
+					break;
+				}
+				for (zlnp = zlnhead; zlnp; zlnp = zlnp->next) {
 					if (zlnp->zlncnt == inumber) {
 						zlnp->zlncnt = zlnhead->zlncnt;
 						zlnp = zlnhead;
@@ -77,30 +82,31 @@ pass4()
 						clri(&idesc, "UNREF", 1);
 						break;
 					}
-			}
-			break;
+				}
+				break;
 
-		case DSTATE:
-			clri(&idesc, "UNREF", 1);
-			break;
+			case DSTATE:
+				clri(&idesc, "UNREF", 1);
+				break;
 
-		case DCLEAR:
-			dp = ginode(inumber);
-			if (dp->di_size == 0) {
-				clri(&idesc, "ZERO LENGTH", 1);
+			case DCLEAR:
+				dp = ginode(inumber);
+				if (dp->di_size == 0) {
+					clri(&idesc, "ZERO LENGTH", 1);
+					break;
+				}
+				/* fall through */
+			case FCLEAR:
+				clri(&idesc, "BAD/DUP", 1);
 				break;
-			}
-			/* fall through */
-		case FCLEAR:
-			clri(&idesc, "BAD/DUP", 1);
-			break;
 
-		case USTATE:
-			break;
+			case USTATE:
+				break;
 
-		default:
-			errx(EEXIT, "BAD STATE %d FOR INODE I=%d",
-			    statemap[inumber], inumber);
+			default:
+				errx(EEXIT, "BAD STATE %d FOR INODE I=%d",
+				    inoinfo(inumber)->ino_state, inumber);
+			}
 		}
 	}
 }
diff --git a/sbin/fsck/pass5.c b/sbin/fsck/pass5.c
index 27509d3936e9..d492a189fff0 100644
--- a/sbin/fsck/pass5.c
+++ b/sbin/fsck/pass5.c
@@ -32,7 +32,7 @@
  */
 
 #ifndef lint
-static char sccsid[] = "@(#)pass5.c	8.9 (Berkeley) 4/28/95";
+static const char sccsid[] = "@(#)pass5.c	8.9 (Berkeley) 4/28/95";
 #endif /* not lint */
 
 #include <sys/param.h>
@@ -49,12 +49,13 @@ static char sccsid[] = "@(#)pass5.c	8.9 (Berkeley) 4/28/95";
 void
 pass5()
 {
-	int c, blk, frags, basesize, sumsize, mapsize, savednrpos;
+	int c, blk, frags, basesize, sumsize, mapsize, savednrpos = 0;
+	int inomapsize, blkmapsize;
 	struct fs *fs = &sblock;
 	struct cg *cg = &cgrp;
 	ufs_daddr_t dbase, dmax;
 	ufs_daddr_t d;
-	long i, j;
+	long i, j, k;
 	struct csum *cs;
 	struct csum cstotal;
 	struct inodesc idesc[3];
@@ -62,7 +63,7 @@ pass5()
 	register struct cg *newcg = (struct cg *)buf;
 	struct ocg *ocg = (struct ocg *)buf;
 
-	statemap[WINO] = USTATE;
+	inoinfo(WINO)->ino_state = USTATE;
 	memset(newcg, 0, (size_t)fs->fs_cgsize);
 	newcg->cg_niblk = fs->fs_ipg;
 	if (cvtlevel >= 3) {
@@ -112,6 +113,8 @@ pass5()
 		sumsize = &ocg->cg_iused[0] - (u_int8_t *)(&ocg->cg_btot[0]);
 		mapsize = &ocg->cg_free[howmany(fs->fs_fpg, NBBY)] -
 			(u_char *)&ocg->cg_iused[0];
+		blkmapsize = howmany(fs->fs_fpg, NBBY);
+		inomapsize = &ocg->cg_free[0] - (u_char *)&ocg->cg_iused[0];
 		ocg->cg_magic = CG_MAGIC;
 		savednrpos = fs->fs_nrpos;
 		fs->fs_nrpos = 8;
@@ -121,22 +124,22 @@ pass5()
 		newcg->cg_btotoff =
 		     &newcg->cg_space[0] - (u_char *)(&newcg->cg_firstfield);
 		newcg->cg_boff =
-		    newcg->cg_btotoff + fs->fs_cpg * sizeof(long);
-		newcg->cg_iusedoff = newcg->cg_boff + 
-		    fs->fs_cpg * fs->fs_nrpos * sizeof(short);
+		    newcg->cg_btotoff + fs->fs_cpg * sizeof(int32_t);
+		newcg->cg_iusedoff = newcg->cg_boff +
+		    fs->fs_cpg * fs->fs_nrpos * sizeof(u_int16_t);
 		newcg->cg_freeoff =
 		    newcg->cg_iusedoff + howmany(fs->fs_ipg, NBBY);
-		if (fs->fs_contigsumsize <= 0) {
-			newcg->cg_nextfreeoff = newcg->cg_freeoff +
-			    howmany(fs->fs_cpg * fs->fs_spc / NSPF(fs), NBBY);
-		} else {
-			newcg->cg_clustersumoff = newcg->cg_freeoff +
-			    howmany(fs->fs_cpg * fs->fs_spc / NSPF(fs), NBBY) -
-			    sizeof(long);
+		inomapsize = newcg->cg_freeoff - newcg->cg_iusedoff;
+		newcg->cg_nextfreeoff = newcg->cg_freeoff +
+		    howmany(fs->fs_cpg * fs->fs_spc / NSPF(fs), NBBY);
+		blkmapsize = newcg->cg_nextfreeoff - newcg->cg_freeoff;
+		if (fs->fs_contigsumsize > 0) {
+			newcg->cg_clustersumoff = newcg->cg_nextfreeoff -
+			    sizeof(u_int32_t);
 			newcg->cg_clustersumoff =
-			    roundup(newcg->cg_clustersumoff, sizeof(long));
+			    roundup(newcg->cg_clustersumoff, sizeof(u_int32_t));
 			newcg->cg_clusteroff = newcg->cg_clustersumoff +
-			    (fs->fs_contigsumsize + 1) * sizeof(long);
+			    (fs->fs_contigsumsize + 1) * sizeof(u_int32_t);
 			newcg->cg_nextfreeoff = newcg->cg_clusteroff +
 			    howmany(fs->fs_cpg * fs->fs_spc / NSPB(fs), NBBY);
 		}
@@ -148,7 +151,7 @@ pass5()
 		break;
 
 	default:
-		sumsize = 0;	/* keep lint happy */
+		inomapsize = blkmapsize = sumsize = 0;	/* keep lint happy */
 		errx(EEXIT, "UNKNOWN ROTATIONAL TABLE FORMAT %d",
 			fs->fs_postblformat);
 	}
@@ -201,8 +204,8 @@ pass5()
 		if (fs->fs_postblformat == FS_42POSTBLFMT)
 			ocg->cg_magic = CG_MAGIC;
 		j = fs->fs_ipg * c;
-		for (i = 0; i < fs->fs_ipg; j++, i++) {
-			switch (statemap[j]) {
+		for (i = 0; i < inostathead[c].il_numalloced; j++, i++) {
+			switch (inoinfo(j)->ino_state) {
 
 			case USTATE:
 				break;
@@ -222,8 +225,8 @@ pass5()
 			default:
 				if (j < ROOTINO)
 					break;
-				errx(EEXIT, "BAD STATE %d FOR INODE I=%d",
-				    statemap[j], j);
+				errx(EEXIT, "BAD STATE %d FOR INODE I=%ld",
+				    inoinfo(j)->ino_state, j);
 			}
 		}
 		if (c == 0)
@@ -299,13 +302,6 @@ pass5()
 			cgdirty();
 			continue;
 		}
-		if (memcmp(cg_inosused(newcg),
-			 cg_inosused(cg), mapsize) != 0 &&
-		    dofix(&idesc[1], "BLK(S) MISSING IN BIT MAPS")) {
-			memmove(cg_inosused(cg), cg_inosused(newcg),
-			      (size_t)mapsize);
-			cgdirty();
-		}
 		if ((memcmp(newcg, cg, basesize) != 0 ||
 		     memcmp(&cg_blktot(newcg)[0],
 			  &cg_blktot(cg)[0], sumsize) != 0) &&
@@ -315,6 +311,40 @@ pass5()
 			       &cg_blktot(newcg)[0], (size_t)sumsize);
 			cgdirty();
 		}
+		if (usedsoftdep) {
+			for (i = 0; i < inomapsize; i++) {
+				j = cg_inosused(newcg)[i];
+				if ((cg_inosused(cg)[i] & j) == j)
+					continue;
+				for (k = 0; k < NBBY; k++) {
+					if ((j & (1 << k)) == 0)
+						continue;
+					if (cg_inosused(cg)[i] & (1 << k))
+						continue;
+					pwarn("ALLOCATED INODE %d MARKED FREE\n",
+					    c * fs->fs_ipg + i * NBBY + k);
+				}
+			}
+			for (i = 0; i < blkmapsize; i++) {
+				j = cg_blksfree(cg)[i];
+				if ((cg_blksfree(newcg)[i] & j) == j)
+					continue;
+				for (k = 0; k < NBBY; k++) {
+					if ((j & (1 << k)) == 0)
+						continue;
+					if (cg_blksfree(newcg)[i] & (1 << k))
+						continue;
+					pwarn("ALLOCATED FRAG %d MARKED FREE\n",
+					    c * fs->fs_fpg + i * NBBY + k);
+				}
+			}
+		}
+		if (memcmp(cg_inosused(newcg), cg_inosused(cg), mapsize) != 0 &&
+		    dofix(&idesc[1], "BLK(S) MISSING IN BIT MAPS")) {
+			memmove(cg_inosused(cg), cg_inosused(newcg),
+			      (size_t)mapsize);
+			cgdirty();
+		}
 	}
 	if (fs->fs_postblformat == FS_42POSTBLFMT)
 		fs->fs_nrpos = savednrpos;
diff --git a/sbin/fsck/preen.c b/sbin/fsck/preen.c
index b5fae6b24f7d..ba0140b54b3a 100644
--- a/sbin/fsck/preen.c
+++ b/sbin/fsck/preen.c
@@ -32,7 +32,7 @@
  */
 
 #ifndef lint
-static char sccsid[] = "@(#)preen.c	8.5 (Berkeley) 4/28/95";
+static const char sccsid[] = "@(#)preen.c	8.5 (Berkeley) 4/28/95";
 #endif /* not lint */
 
 #include <sys/param.h>
@@ -42,6 +42,7 @@ static char sccsid[] = "@(#)preen.c	8.5 (Berkeley) 4/28/95";
 #include <ufs/ufs/dinode.h>
 
 #include <ctype.h>
+#include <errno.h>
 #include <fstab.h>
 #include <string.h>
 
@@ -206,12 +207,13 @@ finddisk(name)
 	register char *p;
 	size_t len;
 
-	for (len = strlen(name), p = name + len - 1; p >= name; --p)
-		if (isdigit(*p)) {
-			len = p - name + 1;
-			break;
-		}
-
+	p = strrchr(name, '/');
+	p = p == NULL ? name : p + 1;
+	while (*p != '\0' && !isdigit((u_char)*p))
+		p++;
+	while (isdigit((u_char)*p))
+		p++;
+	len = (size_t)(p - name);
 	for (dk = disks, dkp = &disks; dk; dkp = &dk->next, dk = dk->next) {
 		if (strncmp(dk->name, name, len) == 0 &&
 		    dk->name[len] == 0)
@@ -291,19 +293,18 @@ blockcheck(origname)
 {
 	struct stat stslash, stblock, stchar;
 	char *newname, *raw;
-	int retried = 0;
+	struct fstab *fsinfo;
+	int retried = 0, len;
 
 	hotroot = 0;
 	if (stat("/", &stslash) < 0) {
-		perror("/");
-		printf("Can't stat root\n");
+		printf("Can't stat /: %s\n", strerror(errno));
 		return (origname);
 	}
 	newname = origname;
 retry:
 	if (stat(newname, &stblock) < 0) {
-		perror(newname);
-		printf("Can't stat %s\n", newname);
+		printf("Can't stat %s: %s\n", newname, strerror(errno));
 		return (origname);
 	}
 	if ((stblock.st_mode & S_IFMT) == S_IFBLK) {
@@ -311,8 +312,7 @@ retry:
 			hotroot++;
 		raw = rawname(newname);
 		if (stat(raw, &stchar) < 0) {
-			perror(raw);
-			printf("Can't stat %s\n", raw);
+			printf("Can't stat %s: %s\n", raw, strerror(errno));
 			return (origname);
 		}
 		if ((stchar.st_mode & S_IFMT) == S_IFCHR) {
@@ -325,6 +325,19 @@ retry:
 		newname = unrawname(newname);
 		retried++;
 		goto retry;
+	} else if ((stblock.st_mode & S_IFMT) == S_IFDIR && !retried) {
+		len = strlen(origname) - 1;
+		if (len > 0 && origname[len] == '/')
+			/* remove trailing slash */
+			origname[len] = '\0';
+		if ((fsinfo = getfsfile(origname)) == NULL) {
+			printf("Can't resolve %s to character special device",
+			    origname);
+			return (0);
+		}
+		newname = fsinfo->fs_spec;
+		retried++;
+		goto retry;
 	}
 	/*
 	 * Not a block or character device, just return name and
diff --git a/sbin/fsck/setup.c b/sbin/fsck/setup.c
index a9ab99416613..5a842f4ec770 100644
--- a/sbin/fsck/setup.c
+++ b/sbin/fsck/setup.c
@@ -32,12 +32,11 @@
  */
 
 #ifndef lint
-static char sccsid[] = "@(#)setup.c	8.10 (Berkeley) 5/9/95";
+static const char sccsid[] = "@(#)setup.c	8.10 (Berkeley) 5/9/95";
 #endif /* not lint */
 
 #define DKTYPENAMES
 #include <sys/param.h>
-#include <sys/time.h>
 #include <sys/stat.h>
 #include <sys/ioctl.h>
 #include <sys/disklabel.h>
@@ -80,7 +79,7 @@ setup(dev)
 
 	havesb = 0;
 	fswritefd = -1;
-	skipclean = preen;
+	skipclean = fflag ? 0 : preen;
 	if (stat(dev, &statb) < 0) {
 		printf("Can't stat %s: %s\n", dev, strerror(errno));
 		return (0);
@@ -112,7 +111,7 @@ setup(dev)
 	asblk.b_un.b_buf = malloc(SBSIZE);
 	if (sblk.b_un.b_buf == NULL || asblk.b_un.b_buf == NULL)
 		errx(EEXIT, "cannot allocate space for superblock");
-	if (lp = getdisklabel(NULL, fsreadfd))
+	if ((lp = getdisklabel(NULL, fsreadfd)))
 		dev_bsize = secsize = lp->d_secsize;
 	else
 		dev_bsize = secsize = DEV_BSIZE;
@@ -138,9 +137,11 @@ setup(dev)
 				"LOCATION OF AN ALTERNATE",
 				"SUPER-BLOCK TO SUPPLY NEEDED",
 				"INFORMATION; SEE fsck(8).");
+			bflag = 0;
 			return(0);
 		}
 		pwarn("USING ALTERNATE SUPERBLOCK AT %d\n", bflag);
+		bflag = 0;
 	}
 	if (skipclean && sblock.fs_clean) {
 		pwarn("FILESYSTEM CLEAN; SKIPPING CHECKS\n");
@@ -166,7 +167,7 @@ setup(dev)
 			sbdirty();
 		}
 	}
-	if (sblock.fs_interleave < 1 || 
+	if (sblock.fs_interleave < 1 ||
 	    sblock.fs_interleave > sblock.fs_nsect) {
 		pwarn("IMPOSSIBLE INTERLEAVE=%d IN SUPERBLOCK",
 			sblock.fs_interleave);
@@ -178,7 +179,7 @@ setup(dev)
 			dirty(&asblk);
 		}
 	}
-	if (sblock.fs_npsect < sblock.fs_nsect || 
+	if (sblock.fs_npsect < sblock.fs_nsect ||
 	    sblock.fs_npsect > sblock.fs_nsect*2) {
 		pwarn("IMPOSSIBLE NPSECT=%d IN SUPERBLOCK",
 			sblock.fs_npsect);
@@ -256,8 +257,10 @@ setup(dev)
 		    fsbtodb(&sblock, sblock.fs_csaddr + j * sblock.fs_frag),
 		    size) != 0 && !asked) {
 			pfatal("BAD SUMMARY INFORMATION");
-			if (reply("CONTINUE") == 0)
+			if (reply("CONTINUE") == 0) {
+				ckfini(0);
 				exit(EEXIT);
+			}
 			asked++;
 		}
 	}
@@ -271,25 +274,18 @@ setup(dev)
 		    (unsigned)bmapsize);
 		goto badsb;
 	}
-	statemap = calloc((unsigned)(maxino + 1), sizeof(char));
-	if (statemap == NULL) {
-		printf("cannot alloc %u bytes for statemap\n",
-		    (unsigned)(maxino + 1));
-		goto badsb;
-	}
-	typemap = calloc((unsigned)(maxino + 1), sizeof(char));
-	if (typemap == NULL) {
-		printf("cannot alloc %u bytes for typemap\n",
-		    (unsigned)(maxino + 1));
+	inostathead = calloc((unsigned)(sblock.fs_ncg),
+	    sizeof(struct inostatlist));
+	if (inostathead == NULL) {
+		printf("cannot alloc %u bytes for inostathead\n",
+		    (unsigned)(sizeof(struct inostatlist) * (sblock.fs_ncg)));
 		goto badsb;
 	}
-	lncntp = (short *)calloc((unsigned)(maxino + 1), sizeof(short));
-	if (lncntp == NULL) {
-		printf("cannot alloc %u bytes for lncntp\n", 
-		    (unsigned)(maxino + 1) * sizeof(short));
+	numdirs = sblock.fs_cstotal.cs_ndir;
+	if (numdirs == 0) {
+		printf("numdirs is zero, try using an alternate superblock\n");
 		goto badsb;
 	}
-	numdirs = sblock.fs_cstotal.cs_ndir;
 	inplast = 0;
 	listmax = numdirs + 10;
 	inpsort = (struct inoinfo **)calloc((unsigned)listmax,
@@ -297,11 +293,15 @@ setup(dev)
 	inphead = (struct inoinfo **)calloc((unsigned)numdirs,
 	    sizeof(struct inoinfo *));
 	if (inpsort == NULL || inphead == NULL) {
-		printf("cannot alloc %u bytes for inphead\n", 
+		printf("cannot alloc %u bytes for inphead\n",
 		    (unsigned)numdirs * sizeof(struct inoinfo *));
 		goto badsb;
 	}
 	bufinit();
+	if (sblock.fs_flags & FS_DOSOFTDEP)
+		usedsoftdep = 1;
+	else
+		usedsoftdep = 0;
 	return (1);
 
 badsb:
@@ -398,7 +398,8 @@ readsb(listerr)
 			for ( ; olp < endlp; olp++, nlp++) {
 				if (*olp == *nlp)
 					continue;
-				printf("offset %d, original %d, alternate %d\n",
+				printf(
+				    "offset %d, original %ld, alternate %ld\n",
 				    olp - (long *)&sblock, *olp, *nlp);
 			}
 		}
@@ -456,6 +457,13 @@ calcsb(dev, devfd, fs)
 			fstypenames[pp->p_fstype] : "unknown");
 		return (0);
 	}
+	if (pp->p_fsize == 0 || pp->p_frag == 0 ||
+	    pp->p_cpg == 0 || pp->p_size == 0) {
+		pfatal("%s: %s: type %s fsize %d, frag %d, cpg %d, size %d\n",
+		    dev, "INCOMPLETE LABEL", fstypenames[pp->p_fstype],
+		    pp->p_fsize, pp->p_frag, pp->p_cpg, pp->p_size);
+		return (0);
+	}
 	memset(fs, 0, sizeof(struct fs));
 	fs->fs_fsize = pp->p_fsize;
 	fs->fs_frag = pp->p_frag;
diff --git a/sbin/fsck/utilities.c b/sbin/fsck/utilities.c
index a5c56da04d04..5ea02b6053fa 100644
--- a/sbin/fsck/utilities.c
+++ b/sbin/fsck/utilities.c
@@ -32,7 +32,7 @@
  */
 
 #ifndef lint
-static char sccsid[] = "@(#)utilities.c	8.6 (Berkeley) 5/19/95";
+static const char sccsid[] = "@(#)utilities.c	8.6 (Berkeley) 5/19/95";
 #endif /* not lint */
 
 #include <sys/param.h>
@@ -42,7 +42,6 @@ static char sccsid[] = "@(#)utilities.c	8.6 (Berkeley) 5/19/95";
 #include <ufs/ufs/dir.h>
 #include <ufs/ffs/fs.h>
 
-#include <ctype.h>
 #include <err.h>
 #include <string.h>
 
@@ -87,6 +86,7 @@ reply(question)
 	printf("\n");
 	if (!persevere && (nflag || fswritefd < 0)) {
 		printf("%s? no\n\n", question);
+		resolved = 0;
 		return (0);
 	}
 	if (yflag || (persevere && nflag)) {
@@ -97,17 +97,41 @@ reply(question)
 		printf("%s? [yn] ", question);
 		(void) fflush(stdout);
 		c = getc(stdin);
-		while (c != '\n' && getc(stdin) != '\n')
-			if (feof(stdin))
+		while (c != '\n' && getc(stdin) != '\n') {
+			if (feof(stdin)) {
+				resolved = 0;
 				return (0);
+			}
+		}
 	} while (c != 'y' && c != 'Y' && c != 'n' && c != 'N');
 	printf("\n");
 	if (c == 'y' || c == 'Y')
 		return (1);
+	resolved = 0;
 	return (0);
 }
 
 /*
+ * Look up state information for an inode.
+ */
+struct inostat *
+inoinfo(inum)
+	ino_t inum;
+{
+	static struct inostat unallocated = { USTATE, 0, 0 };
+	struct inostatlist *ilp;
+	int iloff;
+
+	if (inum > maxino)
+		errx(EEXIT, "inoinfo: inumber %d out of range", inum);
+	ilp = &inostathead[inum / sblock.fs_ipg];
+	iloff = inum % sblock.fs_ipg;
+	if (iloff >= ilp->il_numalloced)
+		return (&unallocated);
+	return (&ilp->il_stat[iloff]);
+}
+
+/*
  * Malloc buffers and set up cache.
  */
 void
@@ -264,14 +288,21 @@ ckfini(markclean)
 	if (bufhead.b_size != cnt)
 		errx(EEXIT, "Panic: lost %d buffers", bufhead.b_size - cnt);
 	pbp = pdirbp = (struct bufarea *)0;
-	if (markclean && sblock.fs_clean == 0) {
-		sblock.fs_clean = 1;
+	if (sblock.fs_clean != markclean) {
+		sblock.fs_clean = markclean;
 		sbdirty();
 		ofsmodified = fsmodified;
 		flush(fswritefd, &sblk);
 		fsmodified = ofsmodified;
-		if (!preen)
-			printf("\n***** FILE SYSTEM MARKED CLEAN *****\n");
+		if (!preen) {
+			printf("\n***** FILE SYSTEM MARKED %s *****\n",
+			    markclean ? "CLEAN" : "DIRTY");
+			if (!markclean)
+				rerun = 1;
+		}
+	} else if (!preen && !markclean) {
+		printf("\n***** FILE SYSTEM STILL DIRTY *****\n");
+		rerun = 1;
 	}
 	if (debug)
 		printf("cache missed %ld of %ld (%d%%)\n", diskreads,
@@ -316,6 +347,8 @@ bread(fd, buf, blk, size)
 		}
 	}
 	printf("\n");
+	if (errs)
+		resolved = 0;
 	return (errs);
 }
 
@@ -340,6 +373,7 @@ bwrite(fd, buf, blk, size)
 		fsmodified = 1;
 		return;
 	}
+	resolved = 0;
 	rwerror("WRITE", blk);
 	if (lseek(fd, offset, 0) < 0)
 		rwerror("SEEK", blk);
@@ -360,7 +394,8 @@ ufs_daddr_t
 allocblk(frags)
 	long frags;
 {
-	register int i, j, k;
+	int i, j, k, cg, baseblk;
+	struct cg *cgp = &cgrp;
 
 	if (frags <= 0 || frags > sblock.fs_frag)
 		return (0);
@@ -375,9 +410,21 @@ allocblk(frags)
 				j += k;
 				continue;
 			}
-			for (k = 0; k < frags; k++)
+			cg = dtog(&sblock, i + j);
+			getblk(&cgblk, cgtod(&sblock, cg), sblock.fs_cgsize);
+			if (!cg_chkmagic(cgp))
+				pfatal("CG %d: BAD MAGIC NUMBER\n", cg);
+			baseblk = dtogd(&sblock, i + j);
+			for (k = 0; k < frags; k++) {
 				setbmap(i + j + k);
+				clrbit(cg_blksfree(cgp), baseblk + k);
+			}
 			n_blks += frags;
+			if (frags == sblock.fs_frag)
+				cgp->cg_cs.cs_nbfree--;
+			else
+				cgp->cg_cs.cs_nffree -= frags;
+			cgdirty();
 			return (i + j);
 		}
 	}
@@ -411,14 +458,14 @@ getpathname(namebuf, curdir, ino)
 	register char *cp;
 	struct inodesc idesc;
 	static int busy = 0;
-	extern int findname();
 
 	if (curdir == ino && ino == ROOTINO) {
 		(void)strcpy(namebuf, "/");
 		return;
 	}
 	if (busy ||
-	    (statemap[curdir] != DSTATE && statemap[curdir] != DFOUND)) {
+	    (inoinfo(curdir)->ino_state != DSTATE &&
+	     inoinfo(curdir)->ino_state != DFOUND)) {
 		(void)strcpy(namebuf, "?");
 		return;
 	}
@@ -477,7 +524,6 @@ void
 catchquit(sig)
 	int sig;
 {
-	extern returntosingle;
 
 	printf("returning to single-user after filesystem check\n");
 	returntosingle = 1;
@@ -548,7 +594,8 @@ dofix(idesc, msg)
 
 /*
  * An unexpected inconsistency occured.
- * Die if preening, otherwise just print message and continue.
+ * Die if preening or filesystem is running with soft dependency protocol,
+ * otherwise just print message and continue.
  */
 void
 #if __STDC__
@@ -568,19 +615,25 @@ pfatal(fmt, va_alist)
 	if (!preen) {
 		(void)vfprintf(stderr, fmt, ap);
 		va_end(ap);
+		if (usedsoftdep)
+			(void)fprintf(stderr,
+			    "\nUNEXPECTED SOFT UPDATE INCONSISTENCY\n");
 		return;
 	}
+	if (cdevname == NULL)
+		cdevname = "fsck";
 	(void)fprintf(stderr, "%s: ", cdevname);
 	(void)vfprintf(stderr, fmt, ap);
 	(void)fprintf(stderr,
-	    "\n%s: UNEXPECTED INCONSISTENCY; RUN fsck MANUALLY.\n",
-	    cdevname);
+	    "\n%s: UNEXPECTED%sINCONSISTENCY; RUN fsck MANUALLY.\n",
+	    cdevname, usedsoftdep ? " SOFT UPDATE " : " ");
+	ckfini(0);
 	exit(EEXIT);
 }
 
 /*
- * Pwarn just prints a message when not preening,
- * or a warning (preceded by filename) when preening.
+ * Pwarn just prints a message when not preening or running soft dependency
+ * protocol, or a warning (preceded by filename) when preening.
  */
 void
 #if __STDC__