From owner-freebsd-current@FreeBSD.ORG Mon Sep 6 01:33:46 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 2DDB716A4CF for ; Mon, 6 Sep 2004 01:33:45 +0000 (GMT) Received: from gw.catspoiler.org (217-ip-163.nccn.net [209.79.217.163]) by mx1.FreeBSD.org (Postfix) with ESMTP id 5E74D43D2D for ; Mon, 6 Sep 2004 01:33:44 +0000 (GMT) (envelope-from truckman@FreeBSD.org) Received: from FreeBSD.org (mousie.catspoiler.org [192.168.101.2]) by gw.catspoiler.org (8.12.11/8.12.11) with ESMTP id i861Xafc035069; Sun, 5 Sep 2004 18:33:41 -0700 (PDT) (envelope-from truckman@FreeBSD.org) Message-Id: <200409060133.i861Xafc035069@gw.catspoiler.org> Date: Sun, 5 Sep 2004 18:33:36 -0700 (PDT) From: Don Lewis To: Giorgos Keramidas In-Reply-To: <200409041920.i84JKTKw032364@gw.catspoiler.org> MIME-Version: 1.0 Content-Type: TEXT/plain; charset=us-ascii cc: freebsd-current@FreeBSD.org Subject: Re: what is fsck's "slowdown"? 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: Mon, 06 Sep 2004 01:33:46 -0000 On 4 Sep, To: scrappy@hub.org wrote: > On 4 Sep, Don Lewis wrote: >> On 4 Sep, Marc G. Fournier wrote: >>> On Fri, 3 Sep 2004, Don Lewis wrote: >> >>>> Would the file system in question happen to be full of UNREF files that >>>> fsck is deleting? >>> >>> mostly 'ZERO LENGTH DIRECTORY' ... >> >> I'm pretty sure that I understand the problem now. During pass 4, fsck >> looks at each inode. It checks each inode in the FSTATE and DFOUND >> states to see if their link counts need to be adjusted. If the link >> count does not need to be adjusted, fsck checks to see if the inode is >> on the list of inodes whose initial link counts were zero, and if it >> finds the inode on this list, it clears the inode. >> >> The problem is that the zero length directories get added to this list >> if their initial link count is zero, and they also don't get removed >> from the list because they are in the DCLEAR state, so the list doesn't >> shrink. This bloats the list, which greatly slows down processing of >> normal files and directories. >> >> Deleting unreferenced files is not the biggest bottleneck, so reversing >> the order of the list isn't going to help much. Probably the biggest >> speedup could be gained by keeping the zero length directories off the >> list. > > An even better solution would be to dispense with the zln list entirely > and just set a bit for these inodes in their struct inostat. This > change is a bit more intrusive because of the need for some sort of > packing strategy because of the need to keep this structure small. My > initial inclination would be to add two new states, FZERO and DZERO, > that pass1() would use to mark inodes with a zero link count. Here's a patch that eliminates the zln list and adds two new inode states to tag zero files and directories that have a zero link count. It seems to work in the light testing that I have done, but it needs further and review before it gets committed. 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 5 Sep 2004 21:20:56 -0000 @@ -90,7 +90,8 @@ if (inp->i_parent == 0) continue; if (inoinfo(inp->i_parent)->ino_state == DFOUND && - inoinfo(inp->i_number)->ino_state == DSTATE) { + (inoinfo(inp->i_number)->ino_state == DSTATE || + inoinfo(inp->i_number)->ino_state == DZLINK)) { inoinfo(inp->i_number)->ino_state = DFOUND; change++; } @@ -640,7 +641,8 @@ return(ino); } if (inoinfo(parent)->ino_state != DSTATE && - inoinfo(parent)->ino_state != DFOUND) { + inoinfo(parent)->ino_state != DFOUND && + inoinfo(parent)->ino_state != DZLINK) { 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 6 Sep 2004 00:41:31 -0000 @@ -84,6 +84,8 @@ #define DFOUND 04 /* directory found during descent */ #define DCLEAR 05 /* directory is to be cleared */ #define FCLEAR 06 /* file is to be cleared */ +#define FZLINK 07 /* inode is file with a link count of zero */ +#define DZLINK 10 /* inode is directory with a zero link count */ /* * Inode state information is contained on per cylinder group lists * which are described by the following structure. @@ -205,15 +207,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 5 Sep 2004 21:24:41 -0000 @@ -525,7 +525,8 @@ } if (busy || (inoinfo(curdir)->ino_state != DSTATE && - inoinfo(curdir)->ino_state != DFOUND)) { + inoinfo(curdir)->ino_state != DFOUND && + inoinfo(curdir)->ino_state != DZLINK)) { (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 5 Sep 2004 21:36:06 -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,8 @@ 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) + (inoinfo(inp->i_number)->ino_state == DSTATE || + inoinfo(inp->i_number)->ino_state == DZLINK)) inoinfo(inp->i_number)->ino_state = DFOUND; if (inp->i_dotdot == inp->i_parent || inp->i_dotdot == (ino_t)-1) @@ -405,6 +408,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 +439,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 6 Sep 2004 00:25:50 -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 && state != DSTATE && state != DZLINK)) continue; if (state == DCLEAR) continue; @@ -80,7 +80,8 @@ * in pass 4. */ if ((preen || bkgrdflag) && - resolved && usedsoftdep && state == DSTATE) { + resolved && usedsoftdep && (state == DSTATE || + state == DZLINK)) { if (inp->i_dotdot >= ROOTINO) inoinfo(inp->i_dotdot)->ino_linkcnt++; continue; @@ -88,7 +89,8 @@ for (loopcnt = 0; ; loopcnt++) { orphan = inp->i_number; if (inp->i_parent == 0 || - inoinfo(inp->i_parent)->ino_state != DSTATE || + (inoinfo(inp->i_parent)->ino_state != DSTATE && + inoinfo(inp->i_parent)->ino_state != DZLINK) || 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;