Correct several bugs in fsck_ffs(8) triggered by corrupted filesystems.

If a directory entry has an illegal inode number (less than zero
or greater than the last inode in the filesystem) the entry is removed.
If a directory '.' or '..' entry had an illegal inode number they
were being removed. Since fsck_ffs knows what the correct value is
for these two entries fix them rather deleting them.

Add much more extensive cylinder group checks and use them to be
more careful about rebuilding a cylinder group.

Check for out-of-range block numbers before trying to free them.

When a directory is deleted also remove its cache entry created
in pass1 so that later passes do not try to operate on a deleted
directory.

Check for ctime(3) returning NULL before trying to use its return.

When freeing a directory inode, do not try to interpret it as a
directory.

Reserve space in the inostatlist to have room to allocate a
lost+found directory.

If an invalid block number is found past the end of an inode simply
remove it rather than clearing and removing the inode.

Modernize the inoinfo structure to use queue(3) LIST rather than a
handrolled linked list implementation.

Reported by:  Bob Prohaska, John-Mark Gurney, and Mark Millard
Tested by:    Peter Holm
Reviewed by:  Peter Holm
Sponsored by: The FreeBSD Foundation
Differential Revision: https://reviews.freebsd.org/D38668

(cherry picked from commit 52f9710412ee6a5bfacae125e24399634d71288d)

8 files changed, 174 insertions, 81 deletions

diff --git a/sbin/fsck_ffs/dir.c b/sbin/fsck_ffs/dir.c
index d09e6940f812..18229ab96fb6 100644
--- a/sbin/fsck_ffs/dir.c
+++ b/sbin/fsck_ffs/dir.c
@@ -63,7 +63,6 @@ static struct	dirtemplate dirhead = {
 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 @@ linkup(ino_t orphan, ino_t parentdir, char *name)
 						if (preen)
 							printf(" (CREATED)\n");
 					} else {
-						freedir(lfdir, UFS_ROOTINO);
+						freedirino(lfdir, UFS_ROOTINO);
 						lfdir = 0;
 						if (preen)
 							printf("\n");
@@ -583,8 +582,7 @@ linkup(ino_t orphan, ino_t parentdir, char *name)
 		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 @@ linkup(ino_t orphan, ino_t parentdir, char *name)
 			 * 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 @@ allocdir(ino_t parent, ino_t request, int mode)
 	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 @@ allocdir(ino_t parent, ino_t request, int mode)
 	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 @@ allocdir(ino_t parent, ino_t request, int mode)
 /*
  * 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 @@ freedir(ino_t ino, ino_t parent)
 		inodirty(&ip);
 		irelse(&ip);
 	}
+	removecachedino(ino);
 	freeino(ino);
 }
 
diff --git a/sbin/fsck_ffs/fsck.h b/sbin/fsck_ffs/fsck.h
index c70febdd4e80..94ec59004b86 100644
--- a/sbin/fsck_ffs/fsck.h
+++ b/sbin/fsck_ffs/fsck.h
@@ -303,8 +303,8 @@ extern struct dups *muldup;		/* end of unique duplicate dup block numbers */
 /*
  * 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 @@ extern struct inoinfo {
 	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
  */
@@ -481,6 +483,7 @@ int		findino(struct inodesc *);
 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);
@@ -518,6 +521,7 @@ void		prtbuf(struct bufarea *, const char *, ...) __printflike(2, 3);
 void		prtinode(struct inode *);
 void		pwarn(const char *fmt, ...) __printflike(1, 2);
 int		readsb(int listerr);
+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
index 277d50f87fb7..d8842e7d41f2 100644
--- a/sbin/fsck_ffs/fsutil.c
+++ b/sbin/fsck_ffs/fsutil.c
@@ -165,7 +165,7 @@ reply(const char *question)
 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;
 
@@ -612,8 +612,7 @@ void
 ckfini(int markclean)
 {
 	struct bufarea *bp, *nbp;
-	struct inoinfo *inp, *ninp;
-	int ofsmodified, cnt, cg, i;
+	int ofsmodified, cnt, cg;
 
 	if (bkgrdflag) {
 		unlink(snapname);
@@ -781,19 +780,7 @@ ckfini(int markclean)
 		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);
@@ -1014,6 +1001,7 @@ check_cgmagic(int cg, struct bufarea *cgbp, int request_rebuild)
 	struct cg *cgp = cgbp->b_un.b_cg;
 	uint32_t cghash, calchash;
 	static int prevfailcg = -1;
+	long start;
 	int error;
 
 	/*
@@ -1039,6 +1027,43 @@ check_cgmagic(int cg, struct bufarea *cgbp, int request_rebuild)
 		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)
@@ -1067,13 +1092,15 @@ check_cgmagic(int cg, struct bufarea *cgbp, int request_rebuild)
 		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 +
@@ -1111,7 +1138,7 @@ allocblk(long startcg, long frags,
 	}
 	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)
@@ -1121,7 +1148,7 @@ allocblk(long startcg, long frags,
 		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)
@@ -1144,6 +1171,8 @@ std_checkblkavail(blkno, frags)
 	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
index 82338f4f8c08..057d49a1ea18 100644
--- a/sbin/fsck_ffs/inode.c
+++ b/sbin/fsck_ffs/inode.c
@@ -661,9 +661,8 @@ freeblock(struct inodesc *idesc)
 	struct bufarea *cgbp;
 	struct cg *cgp;
 	ufs2_daddr_t blkno;
-	long size, nfrags, res;
+	long size, nfrags;
 
-	res = KEEPON;
 	blkno = idesc->id_blkno;
 	if (idesc->id_type == SNAP) {
 		pfatal("clearing a snapshot dinode\n");
@@ -672,10 +671,10 @@ freeblock(struct inodesc *idesc)
 	size = lfragtosize(&sblock, idesc->id_numfrags);
 	if (snapblkfree(&sblock, blkno, size, idesc->id_number,
 	    std_checkblkavail))
-		return (res);
+		return (KEEPON);
 	for (nfrags = idesc->id_numfrags; nfrags > 0; blkno++, nfrags--) {
 		if (chkrange(blkno, 1)) {
-			res = SKIP;
+			return (SKIP);
 		} else if (testbmap(blkno)) {
 			for (dlp = duplist; dlp; dlp = dlp->next) {
 				if (dlp->dup != blkno)
@@ -704,7 +703,7 @@ freeblock(struct inodesc *idesc)
 			cgp->cg_cs.cs_nffree += idesc->id_numfrags;
 		cgdirty(cgbp);
 	}
-	return (res);
+	return (KEEPON);
 }
 
 /*
@@ -1122,7 +1121,7 @@ freeinodebuf(void)
 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 +1137,7 @@ cacheino(union dinode *dp, ino_t inumber)
 		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 +1168,43 @@ getinoinfo(ino_t inumber)
 {
 	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 +1215,14 @@ inocleanup(void)
 {
 	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 +1339,8 @@ prtinode(struct inode *ip)
 		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 +1457,7 @@ freeino(ino_t ino)
 	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
index 49418ec38e4b..5f1ad8ecb686 100644
--- a/sbin/fsck_ffs/pass1.c
+++ b/sbin/fsck_ffs/pass1.c
@@ -219,9 +219,10 @@ pass1(void)
 		 * 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) {
@@ -348,24 +349,38 @@ checkinode(ino_t inumber, struct inodesc *idesc, int rebuildcg)
 			}
 		}
 	}
-	for (j = ndb; ndb < UFS_NDADDR && j < UFS_NDADDR; j++)
-		if (DIP(dp, di_db[j]) != 0) {
-			if (debug)
-				printf("invalid direct addr[%d]: %ju\n", j,
-				    (uintmax_t)DIP(dp, di_db[j]));
-			pfatal("INVALID DIRECT BLOCK");
-			goto unknown;
+	for (j = ndb; ndb < UFS_NDADDR && j < UFS_NDADDR; j++) {
+		if (DIP(dp, di_db[j]) == 0)
+			continue;
+		if (debug)
+			printf("invalid direct addr[%d]: %ju\n", j,
+			    (uintmax_t)DIP(dp, di_db[j]));
+		pfatal("INVALID DIRECT BLOCK");
+		ginode(inumber, &ip);
+		prtinode(&ip);
+		if (reply("CLEAR") == 1) {
+			DIP_SET(ip.i_dp, di_db[j], 0);
+			inodirty(&ip);
 		}
+		irelse(&ip);
+	}
 	for (j = 0, ndb -= UFS_NDADDR; ndb > 0; j++)
 		ndb /= NINDIR(&sblock);
-	for (; j < UFS_NIADDR; j++)
-		if (DIP(dp, di_ib[j]) != 0) {
-			if (debug)
-				printf("invalid indirect addr: %ju\n",
-				    (uintmax_t)DIP(dp, di_ib[j]));
-			pfatal("INVALID INDIRECT BLOCK");
-			goto unknown;
+	for (; j < UFS_NIADDR; j++) {
+		if (DIP(dp, di_ib[j]) == 0)
+			continue;
+		if (debug)
+			printf("invalid indirect addr: %ju\n",
+			    (uintmax_t)DIP(dp, di_ib[j]));
+		pfatal("INVALID INDIRECT BLOCK");
+		ginode(inumber, &ip);
+		prtinode(&ip);
+		if (reply("CLEAR") == 1) {
+			DIP_SET(ip.i_dp, di_ib[j], 0);
+			inodirty(&ip);
 		}
+		irelse(&ip);
+	}
 	if (ftypeok(dp) == 0) {
 		pfatal("UNKNOWN FILE TYPE");
 		goto unknown;
diff --git a/sbin/fsck_ffs/pass2.c b/sbin/fsck_ffs/pass2.c
index 78815493fba8..4e17863ef04c 100644
--- a/sbin/fsck_ffs/pass2.c
+++ b/sbin/fsck_ffs/pass2.c
@@ -85,7 +85,7 @@ pass2(void)
 	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");
@@ -294,8 +294,6 @@ pass2check(struct inodesc *idesc)
 	/*
 	 * check for "."
 	 */
-	if (dirp->d_ino > maxino)
-		goto chk2;
 	if (idesc->id_entryno != 0)
 		goto chk1;
 	if (dirp->d_ino != 0 && strcmp(dirp->d_name, ".") == 0) {
@@ -370,6 +368,20 @@ chk1:
 		dirp->d_reclen = proto.d_reclen;
 	}
 	if (dirp->d_ino != 0 && strcmp(dirp->d_name, "..") == 0) {
+		if (dirp->d_ino > maxino) {
+			direrror(idesc->id_number, "BAD INODE NUMBER FOR '..'");
+			/*
+			 * If we know parent set it now, otherwise let it
+			 * point to the root inode and it will get cleaned
+			 * up later if that is not correct.
+			 */
+			if (inp->i_parent != 0)
+				dirp->d_ino = inp->i_parent;
+			else
+				dirp->d_ino = UFS_ROOTINO;
+			if (reply("FIX") == 1)
+				ret |= ALTERED;
+		}
 		inp->i_dotdot = dirp->d_ino;
 		if (dirp->d_type != DT_DIR) {
 			direrror(idesc->id_number, "BAD TYPE VALUE FOR '..'");
diff --git a/sbin/fsck_ffs/setup.c b/sbin/fsck_ffs/setup.c
index f06424558cf4..1442e5da77d2 100644
--- a/sbin/fsck_ffs/setup.c
+++ b/sbin/fsck_ffs/setup.c
@@ -58,10 +58,11 @@ __FBSDID("$FreeBSD$");
 
 #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 */
 
 #define POWEROF2(num)	(((num) & ((num) - 1)) == 0)
 
@@ -188,14 +189,14 @@ setup(char *dev)
 		    (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
index 7e7ffbd2b038..e9f5bbd421b1 100644
--- a/sbin/fsck_ffs/suj.c
+++ b/sbin/fsck_ffs/suj.c
@@ -391,6 +391,8 @@ suj_checkblkavail(blkno, frags)
 	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;