From 78abfd32f0f68e14f413541b1f360e4c166045a5 Mon Sep 17 00:00:00 2001 From: truckman Date: Fri, 8 Oct 2004 20:44:47 +0000 Subject: Eliminate linked list used to track inodes with an initial link count of zero and instead encode this information in the inode state. Pass 4 performed a linear search of this list for each inode in the file system, which performs poorly if the list is long. Reviewed by: sam & keramida (an earlier version of the patch), mckusick MFC after: 1 month --- sbin/fsck_ffs/dir.c | 5 ++--- sbin/fsck_ffs/fsck.h | 30 +++++++++++++++--------------- sbin/fsck_ffs/fsutil.c | 4 +--- sbin/fsck_ffs/inode.c | 2 ++ sbin/fsck_ffs/main.c | 8 -------- sbin/fsck_ffs/pass1.c | 21 +++++---------------- sbin/fsck_ffs/pass2.c | 6 +++++- sbin/fsck_ffs/pass3.c | 6 +++--- sbin/fsck_ffs/pass4.c | 19 ++++++++----------- sbin/fsck_ffs/pass5.c | 2 ++ 10 files changed, 43 insertions(+), 60 deletions(-) (limited to 'sbin/fsck_ffs') diff --git a/sbin/fsck_ffs/dir.c b/sbin/fsck_ffs/dir.c index a248c27..da838b0 100644 --- a/sbin/fsck_ffs/dir.c +++ b/sbin/fsck_ffs/dir.c @@ -90,7 +90,7 @@ propagate(void) 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 @@ allocdir(ino_t parent, ino_t request, int mode) 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); } diff --git a/sbin/fsck_ffs/fsck.h b/sbin/fsck_ffs/fsck.h index b654249..a2da788 100644 --- a/sbin/fsck_ffs/fsck.h +++ b/sbin/fsck_ffs/fsck.h @@ -78,12 +78,21 @@ struct inostat { /* * 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 *duplist; /* head of dup list */ 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 { diff --git a/sbin/fsck_ffs/fsutil.c b/sbin/fsck_ffs/fsutil.c index 28d5399..6bb590e 100644 --- a/sbin/fsck_ffs/fsutil.c +++ b/sbin/fsck_ffs/fsutil.c @@ -523,9 +523,7 @@ getpathname(char *namebuf, ino_t curdir, ino_t ino) (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; } diff --git a/sbin/fsck_ffs/inode.c b/sbin/fsck_ffs/inode.c index 729f25e..e470f99 100644 --- a/sbin/fsck_ffs/inode.c +++ b/sbin/fsck_ffs/inode.c @@ -576,10 +576,12 @@ blkerror(ino_t ino, const char *type, ufs2_daddr_t blk) 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; diff --git a/sbin/fsck_ffs/main.c b/sbin/fsck_ffs/main.c index 1648b94..d102a9f 100644 --- a/sbin/fsck_ffs/main.c +++ b/sbin/fsck_ffs/main.c @@ -194,7 +194,6 @@ checkfilesys(char *filesys) 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 @@ checkfilesys(char *filesys) 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(); diff --git a/sbin/fsck_ffs/pass1.c b/sbin/fsck_ffs/pass1.c index b4b3617..f728877 100644 --- a/sbin/fsck_ffs/pass1.c +++ b/sbin/fsck_ffs/pass1.c @@ -189,7 +189,6 @@ static void 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 @@ checkinode(ino_t inumber, struct inodesc *idesc) 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; diff --git a/sbin/fsck_ffs/pass2.c b/sbin/fsck_ffs/pass2.c index 096da92..c4fdd2a 100644 --- a/sbin/fsck_ffs/pass2.c +++ b/sbin/fsck_ffs/pass2.c @@ -91,6 +91,7 @@ pass2(void) case FSTATE: case FCLEAR: + case FZLINK: pfatal("ROOT INODE NOT DIRECTORY"); if (reply("REALLOCATE")) { freeino(ROOTINO); @@ -109,6 +110,7 @@ pass2(void) break; case DSTATE: + case DZLINK: break; default: @@ -196,7 +198,7 @@ pass2(void) 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 @@ again: 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 @@ again: /* 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"); diff --git a/sbin/fsck_ffs/pass3.c b/sbin/fsck_ffs/pass3.c index 644fd69..22309cb 100644 --- a/sbin/fsck_ffs/pass3.c +++ b/sbin/fsck_ffs/pass3.c @@ -69,7 +69,7 @@ pass3(void) 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 @@ pass3(void) * 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 @@ pass3(void) 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); diff --git a/sbin/fsck_ffs/pass4.c b/sbin/fsck_ffs/pass4.c index 411f3bd..8a426ea 100644 --- a/sbin/fsck_ffs/pass4.c +++ b/sbin/fsck_ffs/pass4.c @@ -49,7 +49,6 @@ void pass4(void) { ino_t inumber; - struct zlncnt *zlnp; union dinode *dp; struct inodesc idesc; int i, n, cg; @@ -76,6 +75,14 @@ pass4(void) 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 @@ pass4(void) 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: diff --git a/sbin/fsck_ffs/pass5.c b/sbin/fsck_ffs/pass5.c index 0d8275a..c3c564e 100644 --- a/sbin/fsck_ffs/pass5.c +++ b/sbin/fsck_ffs/pass5.c @@ -216,11 +216,13 @@ pass5(void) 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; -- cgit v1.1