diff --git a/sbin/fsck_ffs/dir.c b/sbin/fsck_ffs/dir.c
--- a/sbin/fsck_ffs/dir.c
+++ b/sbin/fsck_ffs/dir.c
@@ -63,7 +63,6 @@
 static int chgino(struct inodesc *);
 static int dircheck(struct inodesc *, struct bufarea *, struct direct *);
 static int expanddir(struct inode *ip, char *name);
-static void freedir(ino_t ino, ino_t parent);
 static struct direct *fsck_readdir(struct inodesc *);
 static struct bufarea *getdirblk(ufs2_daddr_t blkno, long size);
 static int lftempname(char *bufp, ino_t ino);
@@ -517,7 +516,7 @@
 						if (preen)
 							printf(" (CREATED)\n");
 					} else {
-						freedir(lfdir, UFS_ROOTINO);
+						freedirino(lfdir, UFS_ROOTINO);
 						lfdir = 0;
 						if (preen)
 							printf("\n");
@@ -583,8 +582,7 @@
 		inoinfo(lfdir)->ino_linkcnt++;
 		pwarn("DIR I=%lu CONNECTED. ", (u_long)orphan);
 		inp = getinoinfo(parentdir);
-		if (parentdir != (ino_t)-1 && inp != NULL &&
-		    (inp->i_flags & INFO_NEW) == 0) {
+		if (parentdir != (ino_t)-1 && inp != NULL) {
 			printf("PARENT WAS I=%lu\n", (u_long)parentdir);
 			/*
 			 * If the parent directory did not have to
@@ -594,7 +592,8 @@
 			 * fixes the parent link count so that fsck does
 			 * not need to be rerun.
 			 */
-			inoinfo(parentdir)->ino_linkcnt++;
+			if ((inp->i_flags & INFO_NEW) == 0)
+				inoinfo(parentdir)->ino_linkcnt++;
 		}
 		if (preen == 0)
 			printf("\n");
@@ -837,13 +836,12 @@
 	DIP_SET(dp, di_nlink, 2);
 	inodirty(&ip);
 	if (ino == UFS_ROOTINO) {
-		inoinfo(ino)->ino_linkcnt = DIP(dp, di_nlink);
-		if ((inp = getinoinfo(ino)) == NULL)
-			inp = cacheino(dp, ino);
-		else
-			inp->i_flags = INFO_NEW;
+		inp = cacheino(dp, ino);
 		inp->i_parent = parent;
 		inp->i_dotdot = parent;
+		inp->i_flags |= INFO_NEW;
+		inoinfo(ino)->ino_type = DT_DIR;
+		inoinfo(ino)->ino_linkcnt = DIP(dp, di_nlink);
 		irelse(&ip);
 		return(ino);
 	}
@@ -855,6 +853,8 @@
 	inp = cacheino(dp, ino);
 	inp->i_parent = parent;
 	inp->i_dotdot = parent;
+	inp->i_flags |= INFO_NEW;
+	inoinfo(ino)->ino_type = DT_DIR;
 	inoinfo(ino)->ino_state = inoinfo(parent)->ino_state;
 	if (inoinfo(ino)->ino_state == DSTATE) {
 		inoinfo(ino)->ino_linkcnt = DIP(dp, di_nlink);
@@ -872,8 +872,8 @@
 /*
  * free a directory inode
  */
-static void
-freedir(ino_t ino, ino_t parent)
+void
+freedirino(ino_t ino, ino_t parent)
 {
 	struct inode ip;
 	union dinode *dp;
@@ -885,6 +885,7 @@
 		inodirty(&ip);
 		irelse(&ip);
 	}
+	removecachedino(ino);
 	freeino(ino);
 }
 
diff --git a/sbin/fsck_ffs/fsck.h b/sbin/fsck_ffs/fsck.h
--- a/sbin/fsck_ffs/fsck.h
+++ b/sbin/fsck_ffs/fsck.h
@@ -303,8 +303,8 @@
 /*
  * Inode cache data structures.
  */
-extern struct inoinfo {
-	struct	inoinfo *i_nexthash;	/* next entry in hash chain */
+struct inoinfo {
+	SLIST_ENTRY(inoinfo) i_hash;	/* hash list */
 	ino_t	i_number;		/* inode number of this entry */
 	ino_t	i_parent;		/* inode number of parent */
 	ino_t	i_dotdot;		/* inode number of `..' */
@@ -312,7 +312,9 @@
 	u_int	i_flags;		/* flags, see below */
 	u_int	i_numblks;		/* size of block array in bytes */
 	ufs2_daddr_t i_blks[1];		/* actually longer */
-} **inphead, **inpsort;
+};
+extern SLIST_HEAD(inohash, inoinfo) *inphash;
+extern struct inoinfo **inpsort;
 /*
  * flags for struct inoinfo
  */
@@ -480,6 +482,7 @@
 int		findname(struct inodesc *);
 void		flush(int fd, struct bufarea *bp);
 int		freeblock(struct inodesc *);
+void		freedirino(ino_t ino, ino_t parent);
 void		freeino(ino_t ino);
 void		freeinodebuf(void);
 void		fsckinit(void);
@@ -517,6 +520,7 @@
 void		prtinode(struct inode *);
 void		pwarn(const char *fmt, ...) __printflike(1, 2);
 int		readsb(void);
+int		removecachedino(ino_t);
 int		reply(const char *question);
 void		rwerror(const char *mesg, ufs2_daddr_t blk);
 void		sblock_init(void);
diff --git a/sbin/fsck_ffs/fsutil.c b/sbin/fsck_ffs/fsutil.c
--- a/sbin/fsck_ffs/fsutil.c
+++ b/sbin/fsck_ffs/fsutil.c
@@ -166,7 +166,7 @@
 struct inostat *
 inoinfo(ino_t inum)
 {
-	static struct inostat unallocated = { USTATE, 0, 0 };
+	static struct inostat unallocated = { USTATE, 0, 0, 0 };
 	struct inostatlist *ilp;
 	int iloff;
 
@@ -613,8 +613,7 @@
 ckfini(int markclean)
 {
 	struct bufarea *bp, *nbp;
-	struct inoinfo *inp, *ninp;
-	int ofsmodified, cnt, cg, i;
+	int ofsmodified, cnt, cg;
 
 	if (bkgrdflag) {
 		unlink(snapname);
@@ -782,19 +781,7 @@
 		free(inostathead);
 	}
 	inostathead = NULL;
-	if (inpsort != NULL)
-		free(inpsort);
-	inpsort = NULL;
-	if (inphead != NULL) {
-		for (i = 0; i < dirhash; i++) {
-			for (inp = inphead[i]; inp != NULL; inp = ninp) {
-				ninp = inp->i_nexthash;
-				free(inp);
-			}
-		}
-		free(inphead);
-	}
-	inphead = NULL;
+	inocleanup();
 	finalIOstats();
 	(void)close(fsreadfd);
 	(void)close(fswritefd);
@@ -1015,6 +1002,7 @@
 	struct cg *cgp = cgbp->b_un.b_cg;
 	uint32_t cghash, calchash;
 	static int prevfailcg = -1;
+	long start;
 	int error;
 
 	/*
@@ -1040,6 +1028,43 @@
 		CHK(cgp->cg_niblk, !=, sblock.fs_ipg, "%jd");
 		CHK(cgp->cg_initediblk, >, sblock.fs_ipg, "%jd");
 	}
+	if (cgbase(&sblock, cg) + sblock.fs_fpg < sblock.fs_size) {
+		CHK(cgp->cg_ndblk, !=, sblock.fs_fpg, "%jd");
+	} else {
+		CHK(cgp->cg_ndblk, !=, sblock.fs_size - cgbase(&sblock, cg),
+		    "%jd");
+	}
+	start = &cgp->cg_space[0] - (u_char *)(&cgp->cg_firstfield);
+	if (sblock.fs_magic == FS_UFS2_MAGIC) {
+		CHK(cgp->cg_iusedoff, !=, start, "%jd");
+	} else if (sblock.fs_magic == FS_UFS1_MAGIC) {
+		CHK(cgp->cg_niblk, !=, 0, "%jd");
+		CHK(cgp->cg_initediblk, !=, 0, "%jd");
+		CHK(cgp->cg_old_ncyl, !=, sblock.fs_old_cpg, "%jd");
+		CHK(cgp->cg_old_niblk, !=, sblock.fs_ipg, "%jd");
+		CHK(cgp->cg_old_btotoff, !=, start, "%jd");
+		CHK(cgp->cg_old_boff, !=, cgp->cg_old_btotoff +
+		    sblock.fs_old_cpg * sizeof(int32_t), "%jd");
+		CHK(cgp->cg_iusedoff, !=, cgp->cg_old_boff +
+		    sblock.fs_old_cpg * sizeof(u_int16_t), "%jd");
+	}
+	CHK(cgp->cg_freeoff, !=,
+	    cgp->cg_iusedoff + howmany(sblock.fs_ipg, CHAR_BIT), "%jd");
+	if (sblock.fs_contigsumsize == 0) {
+		CHK(cgp->cg_nextfreeoff, !=,
+		    cgp->cg_freeoff + howmany(sblock.fs_fpg, CHAR_BIT), "%jd");
+	} else {
+		CHK(cgp->cg_nclusterblks, !=, cgp->cg_ndblk / sblock.fs_frag,
+		    "%jd");
+		CHK(cgp->cg_clustersumoff, !=,
+		    roundup(cgp->cg_freeoff + howmany(sblock.fs_fpg, CHAR_BIT),
+		    sizeof(u_int32_t)) - sizeof(u_int32_t), "%jd");
+		CHK(cgp->cg_clusteroff, !=, cgp->cg_clustersumoff +
+		    (sblock.fs_contigsumsize + 1) * sizeof(u_int32_t), "%jd");
+		CHK(cgp->cg_nextfreeoff, !=, cgp->cg_clusteroff +
+		    howmany(fragstoblks(&sblock, sblock.fs_fpg), CHAR_BIT),
+		    "%jd");
+	}
 	if (error == 0)
 		return (1);
 	if (prevfailcg == cg)
@@ -1068,13 +1093,15 @@
 		cgp->cg_ndblk = sblock.fs_fpg;
 	else
 		cgp->cg_ndblk = sblock.fs_size - cgbase(&sblock, cg);
-	cgp->cg_iusedoff = &cgp->cg_space[0] - (u_char *)(&cgp->cg_firstfield);
-	if (sblock.fs_magic == FS_UFS1_MAGIC) {
+	start = &cgp->cg_space[0] - (u_char *)(&cgp->cg_firstfield);
+	if (sblock.fs_magic == FS_UFS2_MAGIC) {
+		cgp->cg_iusedoff = start;
+	} else if (sblock.fs_magic == FS_UFS1_MAGIC) {
 		cgp->cg_niblk = 0;
 		cgp->cg_initediblk = 0;
 		cgp->cg_old_ncyl = sblock.fs_old_cpg;
 		cgp->cg_old_niblk = sblock.fs_ipg;
-		cgp->cg_old_btotoff = cgp->cg_iusedoff;
+		cgp->cg_old_btotoff = start;
 		cgp->cg_old_boff = cgp->cg_old_btotoff +
 		    sblock.fs_old_cpg * sizeof(int32_t);
 		cgp->cg_iusedoff = cgp->cg_old_boff +
@@ -1112,7 +1139,7 @@
 	}
 	if (frags <= 0 || frags > sblock.fs_frag)
 		return (0);
-	for (blkno = cgdata(&sblock, startcg);
+	for (blkno = MAX(cgdata(&sblock, startcg), 0);
 	     blkno < maxfsblock - sblock.fs_frag;
 	     blkno += sblock.fs_frag) {
 		if ((newblk = (*checkblkavail)(blkno, frags)) == 0)
@@ -1122,7 +1149,7 @@
 		if (newblk < 0)
 			blkno = -newblk;
 	}
-	for (blkno = cgdata(&sblock, 0);
+	for (blkno = MAX(cgdata(&sblock, 0), 0);
 	     blkno < cgbase(&sblock, startcg) - sblock.fs_frag;
 	     blkno += sblock.fs_frag) {
 		if ((newblk = (*checkblkavail)(blkno, frags)) == 0)
@@ -1145,6 +1172,8 @@
 	ufs2_daddr_t j, k, baseblk;
 	long cg;
 
+	if ((u_int64_t)blkno > sblock.fs_size)
+		return (0);
 	for (j = 0; j <= sblock.fs_frag - frags; j++) {
 		if (testbmap(blkno + j))
 			continue;
diff --git a/sbin/fsck_ffs/inode.c b/sbin/fsck_ffs/inode.c
--- a/sbin/fsck_ffs/inode.c
+++ b/sbin/fsck_ffs/inode.c
@@ -1122,7 +1122,7 @@
 struct inoinfo *
 cacheino(union dinode *dp, ino_t inumber)
 {
-	struct inoinfo *inp, **inpp;
+	struct inoinfo *inp;
 	int i, blks;
 
 	if (getinoinfo(inumber) != NULL)
@@ -1138,9 +1138,7 @@
 		Malloc(sizeof(*inp) + (blks - 1) * sizeof(ufs2_daddr_t));
 	if (inp == NULL)
 		errx(EEXIT, "cannot increase directory list");
-	inpp = &inphead[inumber % dirhash];
-	inp->i_nexthash = *inpp;
-	*inpp = inp;
+	SLIST_INSERT_HEAD(&inphash[inumber % dirhash], inp, i_hash);
 	inp->i_flags = 0;
 	inp->i_parent = inumber == UFS_ROOTINO ? UFS_ROOTINO : (ino_t)0;
 	inp->i_dotdot = (ino_t)0;
@@ -1171,12 +1169,43 @@
 {
 	struct inoinfo *inp;
 
-	for (inp = inphead[inumber % dirhash]; inp; inp = inp->i_nexthash) {
+	SLIST_FOREACH(inp, &inphash[inumber % dirhash], i_hash) {
 		if (inp->i_number != inumber)
 			continue;
 		return (inp);
 	}
-	return ((struct inoinfo *)0);
+	return (NULL);
+}
+
+/*
+ * Remove an entry from the inode cache and disk-order sorted list.
+ * Return 0 on success and 1 on failure.
+ */
+int
+removecachedino(ino_t inumber)
+{
+	struct inoinfo *inp, **inpp;
+	char *listtype;
+
+	listtype = "hash";
+	SLIST_FOREACH(inp, &inphash[inumber % dirhash], i_hash) {
+		if (inp->i_number != inumber)
+			continue;
+		SLIST_REMOVE(&inphash[inumber % dirhash], inp, inoinfo, i_hash);
+		for (inpp = &inpsort[inplast - 1]; inpp >= inpsort; inpp--) {
+			if (*inpp != inp)
+				continue;
+			*inpp = inpsort[inplast - 1];
+			inplast--;
+			free(inp);
+			return (0);
+		}
+		listtype = "sort";
+		break;
+	}
+	pfatal("removecachedino: entry for ino %jd not found on %s list\n",
+	    (intmax_t)inumber, listtype);
+	return (1);
 }
 
 /*
@@ -1187,13 +1216,14 @@
 {
 	struct inoinfo **inpp;
 
-	if (inphead == NULL)
+	if (inphash == NULL)
 		return;
 	for (inpp = &inpsort[inplast - 1]; inpp >= inpsort; inpp--)
 		free((char *)(*inpp));
-	free((char *)inphead);
+	free((char *)inphash);
+	inphash = NULL;
 	free((char *)inpsort);
-	inphead = inpsort = NULL;
+	inpsort = NULL;
 }
 
 void
@@ -1310,8 +1340,8 @@
 		printf("%s: ", cdevname);
 	printf("SIZE=%ju ", (uintmax_t)DIP(dp, di_size));
 	t = DIP(dp, di_mtime);
-	p = ctime(&t);
-	printf("MTIME=%12.12s %4.4s ", &p[4], &p[20]);
+	if ((p = ctime(&t)) != NULL)
+		printf("MTIME=%12.12s %4.4s ", &p[4], &p[20]);
 }
 
 void
@@ -1428,7 +1458,7 @@
 	struct inode ip;
 
 	memset(&idesc, 0, sizeof(struct inodesc));
-	idesc.id_type = inoinfo(ino)->ino_idtype;
+	idesc.id_type = ADDR;
 	idesc.id_func = freeblock;
 	idesc.id_number = ino;
 	ginode(ino, &ip);
diff --git a/sbin/fsck_ffs/pass1.c b/sbin/fsck_ffs/pass1.c
--- a/sbin/fsck_ffs/pass1.c
+++ b/sbin/fsck_ffs/pass1.c
@@ -219,9 +219,10 @@
 		 * 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.
+		 * really found. Always leave map space in the first cylinder
+		 * group in case we need to a root or lost+found directory.
 		 */
-		if (inumber == lastino)
+		if (inumber == lastino || c == 0)
 			continue;
 		inostathead[c].il_numalloced = inosused;
 		if (inosused == 0) {
diff --git a/sbin/fsck_ffs/pass2.c b/sbin/fsck_ffs/pass2.c
--- a/sbin/fsck_ffs/pass2.c
+++ b/sbin/fsck_ffs/pass2.c
@@ -85,7 +85,7 @@
 	case DCLEAR:
 		pfatal("DUPS/BAD IN ROOT INODE");
 		if (reply("REALLOCATE")) {
-			freeino(UFS_ROOTINO);
+			freedirino(UFS_ROOTINO, UFS_ROOTINO);
 			if (allocdir(UFS_ROOTINO, UFS_ROOTINO, 0755) !=
 			    UFS_ROOTINO)
 				errx(EEXIT, "CANNOT ALLOCATE ROOT INODE");
diff --git a/sbin/fsck_ffs/setup.c b/sbin/fsck_ffs/setup.c
--- a/sbin/fsck_ffs/setup.c
+++ b/sbin/fsck_ffs/setup.c
@@ -58,10 +58,11 @@
 
 #include "fsck.h"
 
-struct inoinfo **inphead, **inpsort;	/* info about all inodes */
-struct inode snaplist[FSMAXSNAP + 1];	/* list of active snapshots */
-int snapcnt;				/* number of active snapshots */
-char *copybuf;				/* buffer to copy snapshot blocks */
+struct inohash *inphash;	       /* hash list of directory inode info */
+struct inoinfo **inpsort;	       /* disk order list of directory inodes */
+struct inode snaplist[FSMAXSNAP + 1];  /* list of active snapshots */
+int snapcnt;			       /* number of active snapshots */
+char *copybuf;			       /* buffer to copy snapshot blocks */
 
 static int sbhashfailed;
 #define POWEROF2(num)	(((num) & ((num) - 1)) == 0)
@@ -165,14 +166,14 @@
 		    (unsigned)(sizeof(struct inostatlist) * (sblock.fs_ncg)));
 		goto badsb;
 	}
-	numdirs = MAX(sblock.fs_cstotal.cs_ndir, 128);
-	dirhash = numdirs;
+	numdirs = sblock.fs_cstotal.cs_ndir;
+	dirhash = MAX(numdirs / 2, 1);
 	inplast = 0;
 	listmax = numdirs + 10;
 	inpsort = (struct inoinfo **)Calloc(listmax, sizeof(struct inoinfo *));
-	inphead = (struct inoinfo **)Calloc(numdirs, sizeof(struct inoinfo *));
-	if (inpsort == NULL || inphead == NULL) {
-		printf("cannot alloc %ju bytes for inphead\n",
+	inphash = (struct inohash *)Calloc(dirhash, sizeof(struct inohash));
+	if (inpsort == NULL || inphash == NULL) {
+		printf("cannot alloc %ju bytes for inphash\n",
 		    (uintmax_t)numdirs * sizeof(struct inoinfo *));
 		goto badsb;
 	}
diff --git a/sbin/fsck_ffs/suj.c b/sbin/fsck_ffs/suj.c
--- a/sbin/fsck_ffs/suj.c
+++ b/sbin/fsck_ffs/suj.c
@@ -393,6 +393,8 @@
 	ufs2_daddr_t j, k, baseblk;
 	long cg;
 
+	if ((u_int64_t)blkno > sblock.fs_size)
+		return (0);
 	cg = dtog(&sblock, blkno);
 	cgbp = cglookup(cg);
 	cgp = cgbp->b_un.b_cg;
diff --git a/sys/ufs/ffs/ffs_subr.c b/sys/ufs/ffs/ffs_subr.c
--- a/sys/ufs/ffs/ffs_subr.c
+++ b/sys/ufs/ffs/ffs_subr.c
@@ -347,6 +347,8 @@
 		    #lhs, (intmax_t)lhs, #op, #rhs, (intmax_t)rhs, wmsg);\
 		if (error == 0)						\
 			error = warnerr;				\
+		if (warnerr == 0)					\
+			lhs = rhs;					\
 	}
 #define FCHK2(lhs1, op1, rhs1, lhs2, op2, rhs2, fmt)			\
 	if (lhs1 op1 rhs1 && lhs2 op2 rhs2) {				\
@@ -360,16 +362,6 @@
 		if (error == 0)						\
 			error = ENOENT;					\
 	}
-#define WCHK2(lhs1, op1, rhs1, lhs2, op2, rhs2, fmt)			\
-	if (lhs1 op1 rhs1 && lhs2 op2 rhs2) {				\
-		MPRINT("UFS%d superblock failed: %s (" #fmt ") %s %s ("	\
-		    #fmt ") && %s (" #fmt ") %s %s (" #fmt ")%s\n",	\
-		    fs->fs_magic == FS_UFS1_MAGIC ? 1 : 2, #lhs1,	\
-		    (intmax_t)lhs1, #op1, #rhs1, (intmax_t)rhs1, #lhs2,	\
-		    (intmax_t)lhs2, #op2, #rhs2, (intmax_t)rhs2, wmsg);	\
-		if (error == 0)						\
-			error = warnerr;				\
-	}
 
 static int
 validate_sblock(struct fs *fs, int flags)
@@ -431,6 +423,7 @@
 		FCHK(fs->fs_sblkno, !=, roundup(
 		    howmany(fs->fs_sblockloc + SBLOCKSIZE, fs->fs_fsize),
 		    fs->fs_frag), %jd);
+		FCHK(CGSIZE(fs), >, fs->fs_bsize, %jd);
 		return (error);
 	}
 	if (fs->fs_magic == FS_UFS2_MAGIC) {
@@ -511,6 +504,7 @@
 	FCHK(fs->fs_old_cgoffset, <, 0, %jd);
 	FCHK2(fs->fs_old_cgoffset, >, 0, ~fs->fs_old_cgmask, <, 0, %jd);
 	FCHK(fs->fs_old_cgoffset * (~fs->fs_old_cgmask), >, fs->fs_fpg, %jd);
+	FCHK(CGSIZE(fs), >, fs->fs_bsize, %jd);
 	/*
 	 * If anything has failed up to this point, it is usafe to proceed
 	 * as checks below may divide by zero or make other fatal calculations.