Blend in some code from netbsd and freebsd that reduces memory consumption

and speeds things up in a lot of cases.
Prompted by Amit Kulkarni; ok krw@ on a slighly diffrenent incarnation

12 files changed, 200 insertions, 69 deletions

diff --git a/sbin/fsck_ffs/dir.c b/sbin/fsck_ffs/dir.c
index 1527aaa5127..39f3406352e 100644
--- a/sbin/fsck_ffs/dir.c
+++ b/sbin/fsck_ffs/dir.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: dir.c,v 1.24 2009/10/27 23:59:32 deraadt Exp $	*/
+/*	$OpenBSD: dir.c,v 1.25 2011/04/16 16:37:21 otto Exp $	*/
 /*	$NetBSD: dir.c,v 1.20 1996/09/27 22:45:11 christos Exp $	*/
 
 /*
@@ -443,8 +443,8 @@ linkup(ino_t orphan, ino_t parentdir)
 		idesc.id_type = ADDR;
 		idesc.id_func = pass4check;
 		idesc.id_number = oldlfdir;
-		adjust(&idesc, lncntp[oldlfdir] + 1);
-		lncntp[oldlfdir] = 0;
+		adjust(&idesc, ILNCOUNT(oldlfdir) + 1);
+		ILNCOUNT(oldlfdir) = 0;
 		dp = ginode(lfdir);
 	}
 	if (GET_ISTATE(lfdir) != DFOUND) {
@@ -457,7 +457,7 @@ linkup(ino_t orphan, ino_t parentdir)
 		printf("\n\n");
 		return (0);
 	}
-	lncntp[orphan]--;
+	ILNCOUNT(orphan)--;
 	if (lostdir) {
 		if ((changeino(orphan, "..", lfdir) & ALTERED) == 0 &&
 		    parentdir != (ino_t)-1)
@@ -465,7 +465,7 @@ linkup(ino_t orphan, ino_t parentdir)
 		dp = ginode(lfdir);
 		DIP_SET(dp, di_nlink, DIP(dp, di_nlink) + 1);
 		inodirty();
-		lncntp[lfdir]++;
+		ILNCOUNT(lfdir)++;
 		pwarn("DIR I=%u CONNECTED. ", orphan);
 		if (parentdir != (ino_t)-1) {
 			printf("PARENT WAS I=%u\n", parentdir);
@@ -476,7 +476,7 @@ linkup(ino_t orphan, ino_t parentdir)
 			 * fixes the parent link count so that fsck does
 			 * not need to be rerun.
 			 */
-			lncntp[parentdir]++;
+			ILNCOUNT(parentdir)++;
 		}
 		if (preen == 0)
 			printf("\n");
@@ -636,7 +636,7 @@ allocdir(ino_t parent, ino_t request, int mode)
 	DIP_SET(dp, di_nlink, 2);
 	inodirty();
 	if (ino == ROOTINO) {
-		lncntp[ino] = DIP(dp, di_nlink);
+		ILNCOUNT(ino) = DIP(dp, di_nlink);
 		cacheino(dp, ino);
 		return(ino);
 	}
@@ -650,8 +650,8 @@ allocdir(ino_t parent, ino_t request, int mode)
 	inp->i_dotdot = parent;
 	SET_ISTATE(ino, GET_ISTATE(parent));
 	if (GET_ISTATE(ino) == DSTATE) {
-		lncntp[ino] = DIP(dp, di_nlink);
-		lncntp[parent]++;
+		ILNCOUNT(ino) = DIP(dp, di_nlink);
+		ILNCOUNT(parent)++;
 	}
 	dp = ginode(parent);
 	DIP_SET(dp, di_nlink, DIP(dp, di_nlink) + 1);
diff --git a/sbin/fsck_ffs/extern.h b/sbin/fsck_ffs/extern.h
index fea3f42337c..8bcefe836c3 100644
--- a/sbin/fsck_ffs/extern.h
+++ b/sbin/fsck_ffs/extern.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: extern.h,v 1.10 2007/06/25 19:59:55 otto Exp $	*/
+/*	$OpenBSD: extern.h,v 1.11 2011/04/16 16:37:21 otto Exp $	*/
 /*	$NetBSD: extern.h,v 1.6 1996/09/27 22:45:12 christos Exp $	*/
 
 /*
@@ -54,6 +54,7 @@ int	ftypeok(union dinode *);
 void	getpathname(char *, size_t, ino_t, ino_t);
 void	inocleanup(void);
 void	inodirty(void);
+struct inostat *inoinfo(ino_t);
 int	linkup(ino_t, ino_t);
 int	makeentry(ino_t, ino_t, char *);
 void	pass1(void);
diff --git a/sbin/fsck_ffs/fsck.h b/sbin/fsck_ffs/fsck.h
index b6dad9649a8..21351b9ba2b 100644
--- a/sbin/fsck_ffs/fsck.h
+++ b/sbin/fsck_ffs/fsck.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: fsck.h,v 1.23 2008/06/10 23:10:29 otto Exp $	*/
+/*	$OpenBSD: fsck.h,v 1.24 2011/04/16 16:37:21 otto Exp $	*/
 /*	$NetBSD: fsck.h,v 1.13 1996/10/11 20:15:46 thorpej Exp $	*/
 
 /*
@@ -66,6 +66,19 @@ union dinode {
 #define BUFSIZ 1024
 #endif
 
+/*
+ * Each inode on the file system 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 */
+};
+
 #define	USTATE	01		/* inode not allocated */
 #define	FSTATE	02		/* inode is file */
 #define	DSTATE	03		/* inode is directory */
@@ -73,12 +86,20 @@ union dinode {
 #define	DCLEAR	05		/* directory is to be cleared */
 #define	FCLEAR	06		/* file is to be cleared */
 
-#define GET_ISTATE(ino)		(stmap[(ino)] & 0xf)
-#define GET_ITYPE(ino)		(stmap[(ino)] >> 4)
-#define SET_ISTATE(ino, v)	do { stmap[(ino)] = (stmap[(ino)] & 0xf0) | \
-				    ((v) & 0xf); } while (0)
-#define SET_ITYPE(ino, v)	do { stmap[(ino)] = (stmap[(ino)] & 0x0f) | \
-				    ((v) << 4); } while (0)
+/*
+ * 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;
+
+#define GET_ISTATE(ino)		(inoinfo(ino)->ino_state)
+#define GET_ITYPE(ino)		(inoinfo(ino)->ino_type)
+#define SET_ISTATE(ino, v)	do { GET_ISTATE(ino) = (v); } while (0)
+#define SET_ITYPE(ino, v)	do { GET_ITYPE(ino) = (v); } while (0)
+#define ILNCOUNT(ino)		(inoinfo(ino)->ino_linkcnt)
 
 /*
  * buffer cache structure.
@@ -233,8 +254,6 @@ daddr64_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 */
-u_char	*stmap;			/* ptr to inode state and type table */
-int16_t	*lncntp;		/* ptr to link count table */
 
 ino_t	lfdir;			/* lost & found directory inode number */
 char	*lfname;		/* lost & found directory name */
@@ -242,7 +261,6 @@ int	lfmode;			/* lost & found directory creation mode */
 
 daddr64_t	n_blks;			/* number of blocks in use */
 daddr64_t	n_files;		/* number of files in use */
-long   *cginosused;		/* # of allocated inodes in each cg */
 
 #define	clearinode(dp)	\
 	if (sblock.fs_magic == FS_UFS1_MAGIC) {	\
diff --git a/sbin/fsck_ffs/inode.c b/sbin/fsck_ffs/inode.c
index 7478ff0dd39..65b2cc48349 100644
--- a/sbin/fsck_ffs/inode.c
+++ b/sbin/fsck_ffs/inode.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: inode.c,v 1.33 2009/10/27 23:59:32 deraadt Exp $	*/
+/*	$OpenBSD: inode.c,v 1.34 2011/04/16 16:37:21 otto Exp $	*/
 /*	$NetBSD: inode.c,v 1.23 1996/10/11 20:15:47 thorpej Exp $	*/
 
 /*
@@ -309,7 +309,7 @@ getnextinode(ino_t inumber)
 	static caddr_t nextinop;
 
 	if (inumber != nextino++ || inumber > maxino)
-		errexit("bad inode number %d to nextinode\n", inumber);
+		errexit("bad inode number %d to nextinode %d\n", inumber, nextino);
 	if (inumber >= lastinum) {
 		readcnt++;
 		dblk = fsbtodb(&sblock, ino_to_fsba(&sblock, lastinum));
@@ -361,8 +361,6 @@ setinodebuf(ino_t inum)
 	if (inodebuf == NULL &&
 	    (inodebuf = malloc((unsigned)inobufsize)) == NULL)
 		errexit("Cannot allocate space for inode buffer\n");
-	while (nextino < ROOTINO)
-		(void)getnextinode(nextino);
 }
 
 void
@@ -578,6 +576,7 @@ allocino(ino_t request, int type)
 	struct cg *cgp = &cgrp;
 	int cg;
 	time_t t;
+	struct inostat *info;
 
 	if (request == 0)
 		request = ROOTINO;
@@ -589,6 +588,28 @@ allocino(ino_t request, int type)
 	if (ino == maxino)
 		return (0);
 	cg = ino_to_cg(&sblock, ino);
+	/* If necessary, extend the inoinfo array. grow exponentially */
+	if ((ino % sblock.fs_ipg) >= (uint64_t)inostathead[cg].il_numalloced) {
+		unsigned long newalloced, i;
+		newalloced = MIN(sblock.fs_ipg,
+			MAX(2 * inostathead[cg].il_numalloced, 10));
+		info = calloc(newalloced, sizeof(struct inostat));
+		if (info == NULL) {
+			pwarn("cannot alloc %lu bytes to extend inoinfo\n",
+				sizeof(struct inostat) * newalloced);
+			return 0;
+		}
+		memmove(info, inostathead[cg].il_stat,
+			inostathead[cg].il_numalloced * sizeof(*info));
+		for (i = inostathead[cg].il_numalloced; i < newalloced; i++) {
+			info[i].ino_state = USTATE;
+		}
+		if (inostathead[cg].il_numalloced)
+			free(inostathead[cg].il_stat);
+		inostathead[cg].il_stat = info;
+		inostathead[cg].il_numalloced = newalloced;
+		info = inoinfo(ino);
+	}
 	getblk(&cgblk, cgtod(&sblock, cg), sblock.fs_cgsize);
 	if (!cg_chkmagic(cgp))
 		pfatal("CG %d: BAD MAGIC NUMBER\n", cg);
diff --git a/sbin/fsck_ffs/main.c b/sbin/fsck_ffs/main.c
index b4817ce9626..ff585478f3a 100644
--- a/sbin/fsck_ffs/main.c
+++ b/sbin/fsck_ffs/main.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: main.c,v 1.36 2010/08/12 15:26:34 jsing Exp $	*/
+/*	$OpenBSD: main.c,v 1.37 2011/04/16 16:37:21 otto Exp $	*/
 /*	$NetBSD: main.c,v 1.22 1996/10/11 20:15:48 thorpej Exp $	*/
 
 /*
@@ -282,12 +282,14 @@ checkfilesys(char *filesys, char *mntpt, long auxdata, int child)
 	if (rerun)
 		resolved = 0;
 	ckfini(resolved); /* Don't mark fs clean if fsck needs to be re-run */
+
+	for (cylno = 0; cylno < sblock.fs_ncg; cylno++)
+		free(inostathead[cylno].il_stat);
+	free(inostathead);
+	inostathead = NULL;
+
 	free(blockmap);
 	blockmap = NULL;
-	free(stmap);
-	stmap = NULL;
-	free(lncntp);
-	lncntp = NULL;
 	free(sblock.fs_csp);
 	free(sblk.b_un.b_buf);
 	free(asblk.b_un.b_buf);
diff --git a/sbin/fsck_ffs/pass1.c b/sbin/fsck_ffs/pass1.c
index 37df200352f..52e2c9af228 100644
--- a/sbin/fsck_ffs/pass1.c
+++ b/sbin/fsck_ffs/pass1.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pass1.c,v 1.33 2010/07/09 06:41:17 otto Exp $	*/
+/*	$OpenBSD: pass1.c,v 1.34 2011/04/16 16:37:21 otto Exp $	*/
 /*	$NetBSD: pass1.c,v 1.16 1996/09/27 22:45:15 christos Exp $	*/
 
 /*
@@ -61,10 +61,13 @@ pass1_info(char *buf, size_t buflen)
 void
 pass1(void)
 {
-	struct inodesc idesc;
-	ino_t inumber, inosused;
+	ino_t inumber, inosused, ninosused;
+	size_t inospace;
+	struct inostat *info;
 	int c;
+	struct inodesc idesc;
 	daddr64_t i, cgd;
+	u_int8_t *cp;
 
 	/*
 	 * Set file system reserved blocks in used block map.
@@ -101,13 +104,91 @@ pass1(void)
 				inosused = sblock.fs_ipg;
 		} else
 			inosused = sblock.fs_ipg;
-		cginosused[c] = inosused;
+
+		/*
+		 * 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) {
+			cp = &cg_inosused(&cgrp)[(inosused - 1) / CHAR_BIT];
+			for ( ; inosused > 0; inosused -= CHAR_BIT, cp--) {
+				if (*cp == 0)
+					continue;
+				for (i = 1 << (CHAR_BIT - 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));
+		inospace = (unsigned)inosused * sizeof(struct inostat);
+		if (info == NULL)
+			errexit("cannot alloc %u bytes for inoinfo",
+			    (unsigned)(sizeof(struct inostat) * inosused));
+		inostathead[c].il_stat = info;
+		/*
+		 * Scan the allocated inodes.
+		 */
 		for (i = 0; i < inosused; i++, inumber++) {
 			info_inumber = inumber;
-			if (inumber < ROOTINO)
+			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.
+		 */
+		if (lastino < (c * sblock.fs_ipg))
+			ninosused = 0;
+		else
+			ninosused = lastino - (c * sblock.fs_ipg);
+		inostathead[c].il_numalloced = ninosused;
+		if (ninosused == 0) {
+			free(inostathead[c].il_stat);
+			inostathead[c].il_stat = 0;
+			continue;
+		}
+		if (ninosused != inosused) {
+			struct inostat *ninfo;
+			size_t ninospace = ninosused * sizeof(*ninfo);
+			if (ninospace / sizeof(*info) != ninosused) {
+				pfatal("too many inodes %llu\n",
+				    (unsigned long long)ninosused);
+				exit(8);
+			}
+			ninfo = realloc(info, ninospace);
+			if (ninfo == NULL) {
+				pfatal("cannot realloc %zu bytes to %zu "
+				    "for inoinfo\n", inospace, ninospace);
+				exit(8);
+			}
+			if (ninosused > inosused)
+				(void)memset(&ninfo[inosused], 0, ninospace - inospace);
+			inostathead[c].il_stat = ninfo;
+		}
 	}
 	info_fn = NULL;
 	freeinodebuf();
@@ -244,7 +325,7 @@ checkinode(ino_t inumber, struct inodesc *idesc)
 	if (ftypeok(dp) == 0)
 		goto unknown;
 	n_files++;
-	lncntp[inumber] = DIP(dp, di_nlink);
+	ILNCOUNT(inumber) = DIP(dp, di_nlink);
 	if (DIP(dp, di_nlink) <= 0) {
 		zlnp =  malloc(sizeof *zlnp);
 		if (zlnp == NULL) {
diff --git a/sbin/fsck_ffs/pass2.c b/sbin/fsck_ffs/pass2.c
index 92afe5ad48c..07261ec59d2 100644
--- a/sbin/fsck_ffs/pass2.c
+++ b/sbin/fsck_ffs/pass2.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pass2.c,v 1.29 2009/10/27 23:59:32 deraadt Exp $	*/
+/*	$OpenBSD: pass2.c,v 1.30 2011/04/16 16:37:21 otto Exp $	*/
 /*	$NetBSD: pass2.c,v 1.17 1996/09/27 22:45:15 christos Exp $	*/
 
 /*
@@ -213,15 +213,15 @@ pass2(void)
 			if (reply("FIX") == 0)
 				continue;
 			(void)makeentry(inp->i_number, inp->i_parent, "..");
-			lncntp[inp->i_parent]--;
+			ILNCOUNT(inp->i_parent)--;
 			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]--;
+		ILNCOUNT(inp->i_dotdot)++;
+		ILNCOUNT(inp->i_parent)--;
 		inp->i_dotdot = inp->i_parent;
 		(void)changeino(inp->i_number, "..", inp->i_parent);
 	}
@@ -318,7 +318,7 @@ pass2check(struct inodesc *idesc)
 		proto.d_reclen = entrysize;
 		memcpy(dirp, &proto, (size_t)entrysize);
 		idesc->id_entryno++;
-		lncntp[dirp->d_ino]--;
+		ILNCOUNT(dirp->d_ino)--;
 		dirp = (struct direct *)((char *)(dirp) + entrysize);
 		memset(dirp, 0, (size_t)n);
 		dirp->d_reclen = n;
@@ -353,7 +353,7 @@ chk1:
 		proto.d_reclen = dirp->d_reclen - n;
 		dirp->d_reclen = n;
 		idesc->id_entryno++;
-		lncntp[dirp->d_ino]--;
+		ILNCOUNT(dirp->d_ino)--;
 		dirp = (struct direct *)((char *)(dirp) + n);
 		memset(dirp, 0, (size_t)proto.d_reclen);
 		dirp->d_reclen = proto.d_reclen;
@@ -390,7 +390,7 @@ chk1:
 	}
 	idesc->id_entryno++;
 	if (dirp->d_ino != 0)
-		lncntp[dirp->d_ino]--;
+		ILNCOUNT(dirp->d_ino)--;
 	return (ret|KEEPON);
 chk2:
 	if (dirp->d_ino == 0)
@@ -446,7 +446,7 @@ again:
 			dp = ginode(dirp->d_ino);
 			SET_ISTATE(dirp->d_ino, (DIP(dp, di_mode) & IFMT) ==
 			    IFDIR ? DSTATE : FSTATE);
-			lncntp[dirp->d_ino] = DIP(dp, di_nlink);
+			ILNCOUNT(dirp->d_ino) = DIP(dp, di_nlink);
 			goto again;
 
 		case DSTATE:
@@ -481,7 +481,7 @@ again:
 				if (reply("FIX") == 1)
 					ret |= ALTERED;
 			}
-			lncntp[dirp->d_ino]--;
+			ILNCOUNT(dirp->d_ino)--;
 			break;
 
 		default:
diff --git a/sbin/fsck_ffs/pass3.c b/sbin/fsck_ffs/pass3.c
index 4d42c7be468..472e296d97a 100644
--- a/sbin/fsck_ffs/pass3.c
+++ b/sbin/fsck_ffs/pass3.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pass3.c,v 1.14 2009/10/27 23:59:32 deraadt Exp $	*/
+/*	$OpenBSD: pass3.c,v 1.15 2011/04/16 16:37:21 otto Exp $	*/
 /*	$NetBSD: pass3.c,v 1.8 1995/03/18 14:55:54 cgd Exp $	*/
 
 /*
@@ -73,7 +73,7 @@ pass3(void)
 		}
 		if (linkup(orphan, inp->i_dotdot)) {
 			inp->i_parent = inp->i_dotdot = lfdir;
-			lncntp[lfdir]--;
+			ILNCOUNT(lfdir)--;
 			pinp = getinoinfo(inp->i_parent);
 			inp->i_parentp = pinp;
 			inp->i_sibling = pinp->i_child;
diff --git a/sbin/fsck_ffs/pass4.c b/sbin/fsck_ffs/pass4.c
index dd576af00f9..ec99740487e 100644
--- a/sbin/fsck_ffs/pass4.c
+++ b/sbin/fsck_ffs/pass4.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pass4.c,v 1.19 2009/10/27 23:59:32 deraadt Exp $	*/
+/*	$OpenBSD: pass4.c,v 1.20 2011/04/16 16:37:21 otto Exp $	*/
 /*	$NetBSD: pass4.c,v 1.11 1996/09/27 22:45:17 christos Exp $	*/
 
 /*
@@ -66,7 +66,7 @@ pass4(void)
 	info_fn = pass4_info;
 	for (c = 0; c < sblock.fs_ncg; c++) {
 		inumber = c * sblock.fs_ipg;
-		for (i = 0; i < cginosused[c]; i++, inumber++) {
+		for (i = 0; i < inostathead[c].il_numalloced; i++, inumber++) {
 			if (inumber < ROOTINO)
 				continue;
  			idesc.id_number = inumber;
@@ -74,7 +74,7 @@ pass4(void)
 
 			case FSTATE:
 			case DFOUND:
-				n = lncntp[inumber];
+				n = ILNCOUNT(inumber);
 				if (n) {
 					adjust(&idesc, (short)n);
 					break;
diff --git a/sbin/fsck_ffs/pass5.c b/sbin/fsck_ffs/pass5.c
index 6db07feb217..f7a2ffbf3ce 100644
--- a/sbin/fsck_ffs/pass5.c
+++ b/sbin/fsck_ffs/pass5.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pass5.c,v 1.39 2010/07/09 06:41:17 otto Exp $	*/
+/*	$OpenBSD: pass5.c,v 1.40 2011/04/16 16:37:21 otto Exp $	*/
 /*	$NetBSD: pass5.c,v 1.16 1996/09/27 22:45:18 christos Exp $	*/
 
 /*
@@ -230,7 +230,7 @@ pass5(void)
 		if (fs->fs_postblformat == FS_42POSTBLFMT)
 			ocg->cg_magic = CG_MAGIC;
 		j = fs->fs_ipg * c;
-		for (i = 0; i < cginosused[c]; j++, i++) {
+		for (i = 0; i < inostathead[c].il_numalloced; j++, i++) {
 			switch (GET_ISTATE(j)) {
 
 			case USTATE:
diff --git a/sbin/fsck_ffs/setup.c b/sbin/fsck_ffs/setup.c
index 590c3ea105a..1bcd85aa62a 100644
--- a/sbin/fsck_ffs/setup.c
+++ b/sbin/fsck_ffs/setup.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: setup.c,v 1.46 2010/08/12 15:26:34 jsing Exp $	*/
+/*	$OpenBSD: setup.c,v 1.47 2011/04/16 16:37:21 otto Exp $	*/
 /*	$NetBSD: setup.c,v 1.27 1996/09/27 22:45:19 christos Exp $	*/
 
 /*
@@ -427,22 +427,11 @@ found:
 		    (unsigned)bmapsize);
 		goto badsblabel;
 	}
-	stmap = calloc((unsigned)(maxino + 1), sizeof(char));
-	if (stmap == NULL) {
-		printf("cannot alloc %u bytes for stmap\n",
-		    (unsigned)(maxino + 1));
-		goto badsblabel;
-	}
-	lncntp = calloc((unsigned)(maxino + 1), sizeof(int16_t));
-	if (lncntp == NULL) {
-		printf("cannot alloc %zu bytes for lncntp\n",
-		    (maxino + 1) * sizeof(int16_t));
-		goto badsblabel;
-	}
-	cginosused = calloc((unsigned)sblock.fs_ncg, sizeof(long));
-	if (cginosused == NULL) {
-		printf("cannot alloc %u bytes for cginosused\n",
-		    (unsigned)sblock.fs_ncg);
+	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 badsblabel;
 	}
 	numdirs = MAX(sblock.fs_cstotal.cs_ndir, 128);
diff --git a/sbin/fsck_ffs/utilities.c b/sbin/fsck_ffs/utilities.c
index e4a33b184ad..22653cef2f5 100644
--- a/sbin/fsck_ffs/utilities.c
+++ b/sbin/fsck_ffs/utilities.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: utilities.c,v 1.37 2009/12/10 16:01:51 deraadt Exp $	*/
+/*	$OpenBSD: utilities.c,v 1.38 2011/04/16 16:37:21 otto Exp $	*/
 /*	$NetBSD: utilities.c,v 1.18 1996/09/27 22:45:20 christos Exp $	*/
 
 /*
@@ -116,6 +116,25 @@ reply(char *question)
 }
 
 /*
+ * Look up state information for an inode.
+ */
+struct inostat *
+inoinfo(ino_t inum)
+{
+	static struct inostat unallocated = { USTATE, 0, 0 };
+	struct inostatlist *ilp;
+	int iloff;
+
+	if (inum > maxino)
+		errexit("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