From owner-freebsd-current@FreeBSD.ORG Thu Sep 30 19:59:06 2004 Return-Path: Delivered-To: freebsd-current@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 23D4F16A4CE for ; Thu, 30 Sep 2004 19:59:06 +0000 (GMT) Received: from gw.catspoiler.org (217-ip-163.nccn.net [209.79.217.163]) by mx1.FreeBSD.org (Postfix) with ESMTP id 3311243D1D for ; Thu, 30 Sep 2004 19:59:05 +0000 (GMT) (envelope-from truckman@FreeBSD.org) Received: from FreeBSD.org (mousie.catspoiler.org [192.168.101.2]) by gw.catspoiler.org (8.13.1/8.13.1) with ESMTP id i8UJwwst041810 for ; Thu, 30 Sep 2004 12:59:02 -0700 (PDT) (envelope-from truckman@FreeBSD.org) Message-Id: <200409301959.i8UJwwst041810@gw.catspoiler.org> Date: Thu, 30 Sep 2004 12:58:58 -0700 (PDT) From: Don Lewis To: current@FreeBSD.org MIME-Version: 1.0 Content-Type: TEXT/plain; charset=us-ascii Subject: fsck_ffs patch testers wanted X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 30 Sep 2004 19:59:06 -0000 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;