Date: Sun, 5 Sep 2004 18:33:36 -0700 (PDT) From: Don Lewis <truckman@FreeBSD.org> To: Giorgos Keramidas <keramida@linux.gr> Cc: freebsd-current@FreeBSD.org Subject: Re: what is fsck's "slowdown"? Message-ID: <200409060133.i861Xafc035069@gw.catspoiler.org> In-Reply-To: <200409041920.i84JKTKw032364@gw.catspoiler.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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;
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200409060133.i861Xafc035069>