Eliminate linked list used to track inodes with an initial link

count of zero and instead encode this information in the inode state.
Pass 4 performed a linear search of this list for each inode in
the file system, which performs poorly if the list is long.

Reviewed by:    sam & keramida (an earlier version of the patch), mckusick
MFC after:	1 month

10 files changed, 43 insertions, 60 deletions

diff --git a/sbin/fsck_ffs/dir.c b/sbin/fsck_ffs/dir.c
index a248c27..da838b0 100644
--- a/sbin/fsck_ffs/dir.c
+++ b/sbin/fsck_ffs/dir.c
@@ -90,7 +90,7 @@ propagate(void)
 			if (inp->i_parent == 0)
 				continue;
 			if (inoinfo(inp->i_parent)->ino_state == DFOUND &&
-			    inoinfo(inp->i_number)->ino_state == DSTATE) {
+			    INO_IS_DUNFOUND(inp->i_number)) {
 				inoinfo(inp->i_number)->ino_state = DFOUND;
 				change++;
 			}
@@ -639,8 +639,7 @@ allocdir(ino_t parent, ino_t request, int mode)
 		cacheino(dp, ino);
 		return(ino);
 	}
-	if (inoinfo(parent)->ino_state != DSTATE &&
-	    inoinfo(parent)->ino_state != DFOUND) {
+	if (!INO_IS_DVALID(parent)) {
 		freeino(ino);
 		return (0);
 	}
diff --git a/sbin/fsck_ffs/fsck.h b/sbin/fsck_ffs/fsck.h
index b654249..a2da788 100644
--- a/sbin/fsck_ffs/fsck.h
+++ b/sbin/fsck_ffs/fsck.h
@@ -78,12 +78,21 @@ struct inostat {
 /*
  * 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 */
+#define	USTATE	0x1		/* inode not allocated */
+#define	FSTATE	0x2		/* inode is file */
+#define	FZLINK	0x3		/* inode is file with a link count of zero */
+#define	DSTATE	0x4		/* inode is directory */
+#define	DZLINK	0x5		/* inode is directory with a zero link count  */
+#define	DFOUND	0x6		/* directory found during descent */
+/*     		0x7		   UNUSED - see S_IS_DVALID() definition */
+#define	DCLEAR	0x8		/* directory is to be cleared */
+#define	FCLEAR	0x9		/* file is to be cleared */
+/*     	DUNFOUND === (state == DSTATE || state == DZLINK) */
+#define	S_IS_DUNFOUND(state)	(((state) & ~0x1) == DSTATE)
+/*     	DVALID   === (state == DSTATE || state == DZLINK || state == DFOUND) */
+#define	S_IS_DVALID(state)	(((state) & ~0x3) == DSTATE)
+#define	INO_IS_DUNFOUND(ino)	S_IS_DUNFOUND(inoinfo(ino)->ino_state)
+#define	INO_IS_DVALID(ino)	S_IS_DVALID(inoinfo(ino)->ino_state)
 /*
  * Inode state information is contained on per cylinder group lists
  * which are described by the following structure.
@@ -205,15 +214,6 @@ struct dups *duplist;		/* head of dup list */
 struct dups *muldup;		/* end of unique duplicate dup block numbers */
 
 /*
- * Linked list of inodes with zero link counts.
- */
-struct zlncnt {
-	struct zlncnt *next;
-	ino_t zlncnt;
-};
-struct zlncnt *zlnhead;		/* head of zero link count list */
-
-/*
  * Inode cache data structures.
  */
 struct inoinfo {
diff --git a/sbin/fsck_ffs/fsutil.c b/sbin/fsck_ffs/fsutil.c
index 28d5399..6bb590e 100644
--- a/sbin/fsck_ffs/fsutil.c
+++ b/sbin/fsck_ffs/fsutil.c
@@ -523,9 +523,7 @@ getpathname(char *namebuf, ino_t curdir, ino_t ino)
 		(void)strcpy(namebuf, "/");
 		return;
 	}
-	if (busy ||
-	    (inoinfo(curdir)->ino_state != DSTATE &&
-	     inoinfo(curdir)->ino_state != DFOUND)) {
+	if (busy || !INO_IS_DVALID(curdir)) {
 		(void)strcpy(namebuf, "?");
 		return;
 	}
diff --git a/sbin/fsck_ffs/inode.c b/sbin/fsck_ffs/inode.c
index 729f25e..e470f99 100644
--- a/sbin/fsck_ffs/inode.c
+++ b/sbin/fsck_ffs/inode.c
@@ -576,10 +576,12 @@ blkerror(ino_t ino, const char *type, ufs2_daddr_t blk)
 	switch (inoinfo(ino)->ino_state) {
 
 	case FSTATE:
+	case FZLINK:
 		inoinfo(ino)->ino_state = FCLEAR;
 		return;
 
 	case DSTATE:
+	case DZLINK:
 		inoinfo(ino)->ino_state = DCLEAR;
 		return;
 
diff --git a/sbin/fsck_ffs/main.c b/sbin/fsck_ffs/main.c
index 1648b94..d102a9f 100644
--- a/sbin/fsck_ffs/main.c
+++ b/sbin/fsck_ffs/main.c
@@ -194,7 +194,6 @@ checkfilesys(char *filesys)
 	struct ufs_args args;
 	struct dups *dp;
 	struct statfs *mntp;
-	struct zlncnt *zlnp;
 	struct stat snapdir;
 	struct group *grp;
 	ufs2_daddr_t blks;
@@ -424,14 +423,7 @@ checkfilesys(char *filesys)
 				printf(" %lld,", (long long)dp->dup);
 			printf("\n");
 		}
-		if (zlnhead != NULL) {
-			printf("The following zero link count inodes remain:");
-			for (zlnp = zlnhead; zlnp; zlnp = zlnp->next)
-				printf(" %u,", zlnp->zlncnt);
-			printf("\n");
-		}
 	}
-	zlnhead = (struct zlncnt *)0;
 	duplist = (struct dups *)0;
 	muldup = (struct dups *)0;
 	inocleanup();
diff --git a/sbin/fsck_ffs/pass1.c b/sbin/fsck_ffs/pass1.c
index b4b3617..f728877 100644
--- a/sbin/fsck_ffs/pass1.c
+++ b/sbin/fsck_ffs/pass1.c
@@ -189,7 +189,6 @@ static void
 checkinode(ino_t inumber, struct inodesc *idesc)
 {
 	union dinode *dp;
-	struct zlncnt *zlnp;
 	off_t kernmaxfilesize;
 	ufs2_daddr_t ndb;
 	mode_t mode;
@@ -302,28 +301,18 @@ checkinode(ino_t inumber, struct inodesc *idesc)
 		goto unknown;
 	n_files++;
 	inoinfo(inumber)->ino_linkcnt = DIP(dp, di_nlink);
-	if (DIP(dp, di_nlink) <= 0) {
-		zlnp = (struct zlncnt *)malloc(sizeof *zlnp);
-		if (zlnp == NULL) {
-			pfatal("LINK COUNT TABLE OVERFLOW");
-			if (reply("CONTINUE") == 0) {
-				ckfini(0);
-				exit(EEXIT);
-			}
-		} else {
-			zlnp->zlncnt = inumber;
-			zlnp->next = zlnhead;
-			zlnhead = zlnp;
-		}
-	}
 	if (mode == IFDIR) {
 		if (DIP(dp, di_size) == 0)
 			inoinfo(inumber)->ino_state = DCLEAR;
+		else if (DIP(dp, di_nlink) <= 0)
+			inoinfo(inumber)->ino_state = DZLINK;
 		else
 			inoinfo(inumber)->ino_state = DSTATE;
 		cacheino(dp, inumber);
 		countdirs++;
-	} else
+	} else if (DIP(dp, di_nlink) <= 0)
+		inoinfo(inumber)->ino_state = FZLINK;
+	else
 		inoinfo(inumber)->ino_state = FSTATE;
 	inoinfo(inumber)->ino_type = IFTODT(mode);
 	badblk = dupblk = 0;
diff --git a/sbin/fsck_ffs/pass2.c b/sbin/fsck_ffs/pass2.c
index 096da92..c4fdd2a 100644
--- a/sbin/fsck_ffs/pass2.c
+++ b/sbin/fsck_ffs/pass2.c
@@ -91,6 +91,7 @@ pass2(void)
 
 	case FSTATE:
 	case FCLEAR:
+	case FZLINK:
 		pfatal("ROOT INODE NOT DIRECTORY");
 		if (reply("REALLOCATE")) {
 			freeino(ROOTINO);
@@ -109,6 +110,7 @@ pass2(void)
 		break;
 
 	case DSTATE:
+	case DZLINK:
 		break;
 
 	default:
@@ -196,7 +198,7 @@ pass2(void)
 		if (inp->i_parent == 0 || inp->i_isize == 0)
 			continue;
 		if (inoinfo(inp->i_parent)->ino_state == DFOUND &&
-		    inoinfo(inp->i_number)->ino_state == DSTATE)
+		    INO_IS_DUNFOUND(inp->i_number))
 			inoinfo(inp->i_number)->ino_state = DFOUND;
 		if (inp->i_dotdot == inp->i_parent ||
 		    inp->i_dotdot == (ino_t)-1)
@@ -405,6 +407,7 @@ again:
 			goto again;
 
 		case DSTATE:
+		case DZLINK:
 			if (inoinfo(idesc->id_number)->ino_state == DFOUND)
 				inoinfo(dirp->d_ino)->ino_state = DFOUND;
 			/* FALLTHROUGH */
@@ -435,6 +438,7 @@ again:
 			/* FALLTHROUGH */
 
 		case FSTATE:
+		case FZLINK:
 			if (dirp->d_type != inoinfo(dirp->d_ino)->ino_type) {
 				fileerror(idesc->id_number, dirp->d_ino,
 				    "BAD TYPE VALUE");
diff --git a/sbin/fsck_ffs/pass3.c b/sbin/fsck_ffs/pass3.c
index 644fd69..22309cb 100644
--- a/sbin/fsck_ffs/pass3.c
+++ b/sbin/fsck_ffs/pass3.c
@@ -69,7 +69,7 @@ pass3(void)
 		inp = inpsort[inpindex];
 		state = inoinfo(inp->i_number)->ino_state;
 		if (inp->i_number == ROOTINO ||
-		    (inp->i_parent != 0 && state != DSTATE))
+		    (inp->i_parent != 0 && !S_IS_DUNFOUND(state)))
 			continue;
 		if (state == DCLEAR)
 			continue;
@@ -80,7 +80,7 @@ pass3(void)
 		 * in pass 4.
 		 */
 		if ((preen || bkgrdflag) &&
-		    resolved && usedsoftdep && state == DSTATE) {
+		    resolved && usedsoftdep && S_IS_DUNFOUND(state)) {
 			if (inp->i_dotdot >= ROOTINO)
 				inoinfo(inp->i_dotdot)->ino_linkcnt++;
 			continue;
@@ -88,7 +88,7 @@ pass3(void)
 		for (loopcnt = 0; ; loopcnt++) {
 			orphan = inp->i_number;
 			if (inp->i_parent == 0 ||
-			    inoinfo(inp->i_parent)->ino_state != DSTATE ||
+			    !INO_IS_DUNFOUND(inp->i_parent) ||
 			    loopcnt > countdirs)
 				break;
 			inp = getinoinfo(inp->i_parent);
diff --git a/sbin/fsck_ffs/pass4.c b/sbin/fsck_ffs/pass4.c
index 411f3bd..8a426ea 100644
--- a/sbin/fsck_ffs/pass4.c
+++ b/sbin/fsck_ffs/pass4.c
@@ -49,7 +49,6 @@ void
 pass4(void)
 {
 	ino_t inumber;
-	struct zlncnt *zlnp;
 	union dinode *dp;
 	struct inodesc idesc;
 	int i, n, cg;
@@ -76,6 +75,14 @@ pass4(void)
 			idesc.id_number = inumber;
 			switch (inoinfo(inumber)->ino_state) {
 
+			case FZLINK:
+			case DZLINK:
+				if (inoinfo(inumber)->ino_linkcnt == 0) {
+					clri(&idesc, "UNREF", 1);
+					break;
+				}
+				/* fall through */
+
 			case FSTATE:
 			case DFOUND:
 				n = inoinfo(inumber)->ino_linkcnt;
@@ -83,16 +90,6 @@ pass4(void)
 					adjust(&idesc, (short)n);
 					break;
 				}
-				for (zlnp = zlnhead; zlnp; zlnp = zlnp->next) {
-					if (zlnp->zlncnt == inumber) {
-						zlnp->zlncnt = zlnhead->zlncnt;
-						zlnp = zlnhead;
-						zlnhead = zlnhead->next;
-						free((char *)zlnp);
-						clri(&idesc, "UNREF", 1);
-						break;
-					}
-				}
 				break;
 
 			case DSTATE:
diff --git a/sbin/fsck_ffs/pass5.c b/sbin/fsck_ffs/pass5.c
index 0d8275a..c3c564e 100644
--- a/sbin/fsck_ffs/pass5.c
+++ b/sbin/fsck_ffs/pass5.c
@@ -216,11 +216,13 @@ pass5(void)
 			case DSTATE:
 			case DCLEAR:
 			case DFOUND:
+			case DZLINK:
 				newcg->cg_cs.cs_ndir++;
 				/* FALLTHROUGH */
 
 			case FSTATE:
 			case FCLEAR:
+			case FZLINK:
 				newcg->cg_cs.cs_nifree--;
 				setbit(cg_inosused(newcg), i);
 				break;