I posted an earlier version of the patch below to current_at_ 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 _at__at_ -90,7 +90,7 _at__at_ 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++; } _at__at_ -639,8 +639,7 _at__at_ 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 _at__at_ -78,12 +78,21 _at__at_ /* * 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. _at__at_ -205,15 +214,6 _at__at_ 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 _at__at_ -523,9 +523,7 _at__at_ (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 _at__at_ -576,10 +576,12 _at__at_ 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 _at__at_ -194,7 +194,6 _at__at_ struct ufs_args args; struct dups *dp; struct statfs *mntp; - struct zlncnt *zlnp; struct stat snapdir; struct group *grp; ufs2_daddr_t blks; _at__at_ -424,14 +423,7 _at__at_ 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 _at__at_ -189,7 +189,6 _at__at_ checkinode(ino_t inumber, struct inodesc *idesc) { union dinode *dp; - struct zlncnt *zlnp; off_t kernmaxfilesize; ufs2_daddr_t ndb; mode_t mode; _at__at_ -302,28 +301,18 _at__at_ 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 _at__at_ -91,6 +91,7 _at__at_ case FSTATE: case FCLEAR: + case FZLINK: pfatal("ROOT INODE NOT DIRECTORY"); if (reply("REALLOCATE")) { freeino(ROOTINO); _at__at_ -109,6 +110,7 _at__at_ break; case DSTATE: + case DZLINK: break; default: _at__at_ -196,7 +198,7 _at__at_ 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) _at__at_ -405,6 +407,7 _at__at_ goto again; case DSTATE: + case DZLINK: if (inoinfo(idesc->id_number)->ino_state == DFOUND) inoinfo(dirp->d_ino)->ino_state = DFOUND; /* FALLTHROUGH */ _at__at_ -435,6 +438,7 _at__at_ /* 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 _at__at_ -69,7 +69,7 _at__at_ 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; _at__at_ -80,7 +80,7 _at__at_ * 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; _at__at_ -88,7 +88,7 _at__at_ 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 _at__at_ -49,7 +49,6 _at__at_ pass4(void) { ino_t inumber; - struct zlncnt *zlnp; union dinode *dp; struct inodesc idesc; int i, n, cg; _at__at_ -76,6 +75,14 _at__at_ 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; _at__at_ -83,16 +90,6 _at__at_ 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 _at__at_ -216,11 +216,13 _at__at_ 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;Received on Thu Sep 30 2004 - 17:59:06 UTC
This archive was generated by hypermail 2.4.0 : Wed May 19 2021 - 11:38:14 UTC