Date: Fri, 24 Sep 2004 16:07:32 -0300 (ADT) From: "Marc G. Fournier" <scrappy@hub.org> To: Don Lewis <truckman@FreeBSD.org> Cc: Giorgos Keramidas <keramida@linux.gr> Subject: Re: what is fsck's "slowdown"? Message-ID: <20040924160535.N43964@ganymede.hub.org> In-Reply-To: <200409060133.i861Xafc035069@gw.catspoiler.org> References: <200409060133.i861Xafc035069@gw.catspoiler.org>
next in thread | previous in thread | raw e-mail | index | archive | help
Just curious as to whether or not this is going to get applied to the
source tree ... ? Just checked my -current, and it isn't there yet, just
wanted to see if maybe its been forgotten? :(
On Sun, 5 Sep 2004, Don Lewis wrote:
> 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;
>
> _______________________________________________
> freebsd-current@freebsd.org mailing list
> http://lists.freebsd.org/mailman/listinfo/freebsd-current
> To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
>
----
Marc G. Fournier Hub.Org Networking Services (http://www.hub.org)
Email: scrappy@hub.org Yahoo!: yscrappy ICQ: 7615664
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20040924160535.N43964>