fsck_ffs patch testers wanted

Don Lewis truckman at FreeBSD.org
Thu Sep 30 12:59:06 PDT 2004


I posted an earlier version of the patch below to current@ for review a
few weeks ago.  This patch does not (or at least should not) change the
functional behaviour of fsck_ffs, and it is functionally equivalent to
the previous version of the patch.

The current implementation of fsck_ffs puts inodes with an initial link
count of zero on a linked list so that the inodes can be cleared later
if their link counts are not adjusted upwards.  This can cause fsck pass
4 to become glacially slow if this list becomes large because there is a
sequential search of the list as each inode is processed in pass 4 to
see if each inode is on the list.

This patch fixes the performance problem by eliminating the list and
encoding whether or not the initial link count was zero in the inode
state.

This patch has been reviewed, and I'm running it on my -CURRENT machine
(where fsck_ffs doesn't normally get much exercise), but due to the
critical nature of fsck_ffs, I'd like it to get more testing before I
commit it to -CURRENT.

Index: sbin/fsck_ffs/dir.c
===================================================================
RCS file: /home/ncvs/src/sbin/fsck_ffs/dir.c,v
retrieving revision 1.29
diff -u -r1.29 dir.c
--- sbin/fsck_ffs/dir.c	1 Sep 2004 05:48:06 -0000	1.29
+++ sbin/fsck_ffs/dir.c	29 Sep 2004 23:19:17 -0000
@@ -90,7 +90,7 @@
 			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 @@
 		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);
 	}
Index: sbin/fsck_ffs/fsck.h
===================================================================
RCS file: /home/ncvs/src/sbin/fsck_ffs/fsck.h,v
retrieving revision 1.32
diff -u -r1.32 fsck.h
--- sbin/fsck_ffs/fsck.h	1 Sep 2004 05:48:06 -0000	1.32
+++ sbin/fsck_ffs/fsck.h	29 Sep 2004 23:13:24 -0000
@@ -78,12 +78,21 @@
 /*
  * 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 *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 {
Index: sbin/fsck_ffs/fsutil.c
===================================================================
RCS file: /home/ncvs/src/sbin/fsck_ffs/fsutil.c,v
retrieving revision 1.24
diff -u -r1.24 fsutil.c
--- sbin/fsck_ffs/fsutil.c	18 May 2004 19:51:41 -0000	1.24
+++ sbin/fsck_ffs/fsutil.c	29 Sep 2004 23:16:24 -0000
@@ -523,9 +523,7 @@
 		(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;
 	}
Index: sbin/fsck_ffs/inode.c
===================================================================
RCS file: /home/ncvs/src/sbin/fsck_ffs/inode.c,v
retrieving revision 1.36
diff -u -r1.36 inode.c
--- sbin/fsck_ffs/inode.c	1 Sep 2004 05:48:06 -0000	1.36
+++ sbin/fsck_ffs/inode.c	5 Sep 2004 21:25:36 -0000
@@ -576,10 +576,12 @@
 	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;
 
Index: sbin/fsck_ffs/main.c
===================================================================
RCS file: /home/ncvs/src/sbin/fsck_ffs/main.c,v
retrieving revision 1.41
diff -u -r1.41 main.c
--- sbin/fsck_ffs/main.c	9 Apr 2004 19:58:28 -0000	1.41
+++ sbin/fsck_ffs/main.c	6 Sep 2004 00:41:47 -0000
@@ -194,7 +194,6 @@
 	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 @@
 				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();
Index: sbin/fsck_ffs/pass1.c
===================================================================
RCS file: /home/ncvs/src/sbin/fsck_ffs/pass1.c,v
retrieving revision 1.42
diff -u -r1.42 pass1.c
--- sbin/fsck_ffs/pass1.c	1 Sep 2004 05:48:06 -0000	1.42
+++ sbin/fsck_ffs/pass1.c	6 Sep 2004 00:42:11 -0000
@@ -189,7 +189,6 @@
 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 @@
 		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;
Index: sbin/fsck_ffs/pass2.c
===================================================================
RCS file: /home/ncvs/src/sbin/fsck_ffs/pass2.c,v
retrieving revision 1.25
diff -u -r1.25 pass2.c
--- sbin/fsck_ffs/pass2.c	1 Sep 2004 05:48:06 -0000	1.25
+++ sbin/fsck_ffs/pass2.c	29 Sep 2004 23:19:34 -0000
@@ -91,6 +91,7 @@
 
 	case FSTATE:
 	case FCLEAR:
+	case FZLINK:
 		pfatal("ROOT INODE NOT DIRECTORY");
 		if (reply("REALLOCATE")) {
 			freeino(ROOTINO);
@@ -109,6 +110,7 @@
 		break;
 
 	case DSTATE:
+	case DZLINK:
 		break;
 
 	default:
@@ -196,7 +198,7 @@
 		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 @@
 			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 @@
 			/* 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");
Index: sbin/fsck_ffs/pass3.c
===================================================================
RCS file: /home/ncvs/src/sbin/fsck_ffs/pass3.c,v
retrieving revision 1.14
diff -u -r1.14 pass3.c
--- sbin/fsck_ffs/pass3.c	9 Apr 2004 19:58:28 -0000	1.14
+++ sbin/fsck_ffs/pass3.c	29 Sep 2004 23:17:36 -0000
@@ -69,7 +69,7 @@
 		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 @@
 		 * 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 @@
 		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);
Index: sbin/fsck_ffs/pass4.c
===================================================================
RCS file: /home/ncvs/src/sbin/fsck_ffs/pass4.c,v
retrieving revision 1.14
diff -u -r1.14 pass4.c
--- sbin/fsck_ffs/pass4.c	9 Apr 2004 19:58:28 -0000	1.14
+++ sbin/fsck_ffs/pass4.c	6 Sep 2004 00:41:55 -0000
@@ -49,7 +49,6 @@
 pass4(void)
 {
 	ino_t inumber;
-	struct zlncnt *zlnp;
 	union dinode *dp;
 	struct inodesc idesc;
 	int i, n, cg;
@@ -76,6 +75,14 @@
 			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 @@
 					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:
Index: sbin/fsck_ffs/pass5.c
===================================================================
RCS file: /home/ncvs/src/sbin/fsck_ffs/pass5.c,v
retrieving revision 1.39
diff -u -r1.39 pass5.c
--- sbin/fsck_ffs/pass5.c	9 Apr 2004 19:58:28 -0000	1.39
+++ sbin/fsck_ffs/pass5.c	6 Sep 2004 00:34:10 -0000
@@ -216,11 +216,13 @@
 			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;



More information about the freebsd-current mailing list