So here's an initial, only lightly tested diff.
Beware, this very well could eat your filesystems.
To note any difference, you should use the -p mode of fsck_ffs (rc
does that) and the fs should have been mounted with softdep.
I have seen very nice speedups already.
-Otto
Index: dir.c
===================================================================
RCS file: /cvs/src/sbin/fsck_ffs/dir.c,v
retrieving revision 1.24
diff -u -p -r1.24 dir.c
--- dir.c 27 Oct 2009 23:59:32 -0000 1.24
+++ dir.c 31 Mar 2011 08:30:36 -0000
@@ -443,8 +443,8 @@ linkup(ino_t orphan, ino_t parentdir)
idesc.id_type = ADDR;
idesc.id_func = pass4check;
idesc.id_number = oldlfdir;
- adjust(&idesc, lncntp[oldlfdir] + 1);
- lncntp[oldlfdir] = 0;
+ adjust(&idesc, ILNCOUNT(oldlfdir) + 1);
+ ILNCOUNT(oldlfdir) = 0;
dp = ginode(lfdir);
}
if (GET_ISTATE(lfdir) != DFOUND) {
@@ -457,7 +457,7 @@ linkup(ino_t orphan, ino_t parentdir)
printf("\n\n");
return (0);
}
- lncntp[orphan]--;
+ ILNCOUNT(orphan)--;
if (lostdir) {
if ((changeino(orphan, "..", lfdir) & ALTERED) == 0 &&
parentdir != (ino_t)-1)
@@ -465,7 +465,7 @@ linkup(ino_t orphan, ino_t parentdir)
dp = ginode(lfdir);
DIP_SET(dp, di_nlink, DIP(dp, di_nlink) + 1);
inodirty();
- lncntp[lfdir]++;
+ ILNCOUNT(lfdir)++;
pwarn("DIR I=%u CONNECTED. ", orphan);
if (parentdir != (ino_t)-1) {
printf("PARENT WAS I=%u\n", parentdir);
@@ -476,7 +476,7 @@ linkup(ino_t orphan, ino_t parentdir)
* fixes the parent link count so that fsck does
* not need to be rerun.
*/
- lncntp[parentdir]++;
+ ILNCOUNT(parentdir)++;
}
if (preen == 0)
printf("\n");
@@ -636,7 +636,7 @@ allocdir(ino_t parent, ino_t request, in
DIP_SET(dp, di_nlink, 2);
inodirty();
if (ino == ROOTINO) {
- lncntp[ino] = DIP(dp, di_nlink);
+ ILNCOUNT(ino) = DIP(dp, di_nlink);
cacheino(dp, ino);
return(ino);
}
@@ -650,8 +650,8 @@ allocdir(ino_t parent, ino_t request, in
inp->i_dotdot = parent;
SET_ISTATE(ino, GET_ISTATE(parent));
if (GET_ISTATE(ino) == DSTATE) {
- lncntp[ino] = DIP(dp, di_nlink);
- lncntp[parent]++;
+ ILNCOUNT(ino) = DIP(dp, di_nlink);
+ ILNCOUNT(parent)++;
}
dp = ginode(parent);
DIP_SET(dp, di_nlink, DIP(dp, di_nlink) + 1);
Index: extern.h
===================================================================
RCS file: /cvs/src/sbin/fsck_ffs/extern.h,v
retrieving revision 1.10
diff -u -p -r1.10 extern.h
--- extern.h 25 Jun 2007 19:59:55 -0000 1.10
+++ extern.h 31 Mar 2011 11:56:53 -0000
@@ -54,6 +54,7 @@ int ftypeok(union dinode *);
void getpathname(char *, size_t, ino_t, ino_t);
void inocleanup(void);
void inodirty(void);
+struct inostat *inoinfo(ino_t);
int linkup(ino_t, ino_t);
int makeentry(ino_t, ino_t, char *);
void pass1(void);
Index: fsck.h
===================================================================
RCS file: /cvs/src/sbin/fsck_ffs/fsck.h,v
retrieving revision 1.23
diff -u -p -r1.23 fsck.h
--- fsck.h 10 Jun 2008 23:10:29 -0000 1.23
+++ fsck.h 31 Mar 2011 11:55:42 -0000
@@ -66,6 +66,19 @@ union dinode {
#define BUFSIZ 1024
#endif
+/*
+ * Each inode on the file system is described by the following structure.
+ * The linkcnt is initially set to the value in the inode. Each time it
+ * is found during the descent in passes 2, 3, and 4 the count is
+ * decremented. Any inodes whose count is non-zero after pass 4 needs to
+ * have its link count adjusted by the value remaining in ino_linkcnt.
+ */
+struct inostat {
+ char ino_state; /* state of inode, see below */
+ char ino_type; /* type of inode */
+ short ino_linkcnt; /* number of links not found */
+};
+
#define USTATE 01 /* inode not allocated */
#define FSTATE 02 /* inode is file */
#define DSTATE 03 /* inode is directory */
@@ -73,12 +86,20 @@ union dinode {
#define DCLEAR 05 /* directory is to be cleared */
#define FCLEAR 06 /* file is to be cleared */
-#define GET_ISTATE(ino) (stmap[(ino)] & 0xf)
-#define GET_ITYPE(ino) (stmap[(ino)] >> 4)
-#define SET_ISTATE(ino, v) do { stmap[(ino)] = (stmap[(ino)] & 0xf0) | \
- ((v) & 0xf); } while (0)
-#define SET_ITYPE(ino, v) do { stmap[(ino)] = (stmap[(ino)] & 0x0f) | \
- ((v) << 4); } while (0)
+/*
+ * Inode state information is contained on per cylinder group lists
+ * which are described by the following structure.
+ */
+struct inostatlist {
+ long il_numalloced; /* number of inodes allocated in this cg */
+ struct inostat *il_stat;/* inostat info for this cylinder group */
+} *inostathead;
+
+#define GET_ISTATE(ino) (inoinfo(ino)->ino_state)
+#define GET_ITYPE(ino) (inoinfo(ino)->ino_type)
+#define SET_ISTATE(ino, v) do { GET_ISTATE(ino) = (v); } while (0)
+#define SET_ITYPE(ino, v) do { GET_ITYPE(ino) = (v); } while (0)
+#define ILNCOUNT(ino) (inoinfo(ino)->ino_linkcnt)
/*
* buffer cache structure.
@@ -233,8 +254,6 @@ daddr64_t maxfsblock; /* number of bloc
char *blockmap; /* ptr to primary blk allocation map */
ino_t maxino; /* number of inodes in file system */
ino_t lastino; /* last inode in use */
-u_char *stmap; /* ptr to inode state and type table */
-int16_t *lncntp; /* ptr to link count table */
ino_t lfdir; /* lost & found directory inode number */
char *lfname; /* lost & found directory name */
@@ -242,7 +261,6 @@ int lfmode; /* lost & found directory
daddr64_t n_blks; /* number of blocks in use */
daddr64_t n_files; /* number of files in use */
-long *cginosused; /* # of allocated inodes in each cg */
#define clearinode(dp) \
if (sblock.fs_magic == FS_UFS1_MAGIC) { \
Index: inode.c
===================================================================
RCS file: /cvs/src/sbin/fsck_ffs/inode.c,v
retrieving revision 1.33
diff -u -p -r1.33 inode.c
--- inode.c 27 Oct 2009 23:59:32 -0000 1.33
+++ inode.c 31 Mar 2011 16:34:27 -0000
@@ -309,7 +309,7 @@ getnextinode(ino_t inumber)
static caddr_t nextinop;
if (inumber != nextino++ || inumber > maxino)
- errexit("bad inode number %d to nextinode\n", inumber);
+ errexit("bad inode number %d to nextinode %d\n", inumber,
nextino);
if (inumber >= lastinum) {
readcnt++;
dblk = fsbtodb(&sblock, ino_to_fsba(&sblock, lastinum));
@@ -361,8 +361,6 @@ setinodebuf(ino_t inum)
if (inodebuf == NULL &&
(inodebuf = malloc((unsigned)inobufsize)) == NULL)
errexit("Cannot allocate space for inode buffer\n");
- while (nextino < ROOTINO)
- (void)getnextinode(nextino);
}
void
@@ -578,6 +576,7 @@ allocino(ino_t request, int type)
struct cg *cgp = &cgrp;
int cg;
time_t t;
+ struct inostat *info;
if (request == 0)
request = ROOTINO;
@@ -589,6 +588,28 @@ allocino(ino_t request, int type)
if (ino == maxino)
return (0);
cg = ino_to_cg(&sblock, ino);
+ /* If necessary, extend the inoinfo array. grow exponentially */
+ if ((ino % sblock.fs_ipg) >= (uint64_t)inostathead[cg].il_numalloced) {
+ unsigned long newalloced, i;
+ newalloced = MIN(sblock.fs_ipg,
+ MAX(2 * inostathead[cg].il_numalloced, 10));
+ info = calloc(newalloced, sizeof(struct inostat));
+ if (info == NULL) {
+ pwarn("cannot alloc %lu bytes to extend inoinfo\n",
+ sizeof(struct inostat) * newalloced);
+ return 0;
+ }
+ memmove(info, inostathead[cg].il_stat,
+ inostathead[cg].il_numalloced * sizeof(*info));
+ for (i = inostathead[cg].il_numalloced; i < newalloced; i++) {
+ info[i].ino_state = USTATE;
+ }
+ if (inostathead[cg].il_numalloced)
+ free(inostathead[cg].il_stat);
+ inostathead[cg].il_stat = info;
+ inostathead[cg].il_numalloced = newalloced;
+ info = inoinfo(ino);
+ }
getblk(&cgblk, cgtod(&sblock, cg), sblock.fs_cgsize);
if (!cg_chkmagic(cgp))
pfatal("CG %d: BAD MAGIC NUMBER\n", cg);
Index: main.c
===================================================================
RCS file: /cvs/src/sbin/fsck_ffs/main.c,v
retrieving revision 1.36
diff -u -p -r1.36 main.c
--- main.c 12 Aug 2010 15:26:34 -0000 1.36
+++ main.c 31 Mar 2011 12:18:08 -0000
@@ -282,12 +282,14 @@ checkfilesys(char *filesys, char *mntpt,
if (rerun)
resolved = 0;
ckfini(resolved); /* Don't mark fs clean if fsck needs to be re-run */
+
+ for (cylno = 0; cylno < sblock.fs_ncg; cylno++)
+ free(inostathead[cylno].il_stat);
+ free(inostathead);
+ inostathead = NULL;
+
free(blockmap);
blockmap = NULL;
- free(stmap);
- stmap = NULL;
- free(lncntp);
- lncntp = NULL;
free(sblock.fs_csp);
free(sblk.b_un.b_buf);
free(asblk.b_un.b_buf);
Index: pass1.c
===================================================================
RCS file: /cvs/src/sbin/fsck_ffs/pass1.c,v
retrieving revision 1.33
diff -u -p -r1.33 pass1.c
--- pass1.c 9 Jul 2010 06:41:17 -0000 1.33
+++ pass1.c 31 Mar 2011 12:13:26 -0000
@@ -61,10 +61,13 @@ pass1_info(char *buf, size_t buflen)
void
pass1(void)
{
- struct inodesc idesc;
- ino_t inumber, inosused;
+ ino_t inumber, inosused, ninosused;
+ size_t inospace;
+ struct inostat *info;
int c;
+ struct inodesc idesc;
daddr64_t i, cgd;
+ u_int8_t *cp;
/*
* Set file system reserved blocks in used block map.
@@ -101,13 +104,91 @@ pass1(void)
inosused = sblock.fs_ipg;
} else
inosused = sblock.fs_ipg;
- cginosused[c] = inosused;
+
+ /*
+ * If we are using soft updates, then we can trust the
+ * cylinder group inode allocation maps to tell us which
+ * inodes are allocated. We will scan the used inode map
+ * to find the inodes that are really in use, and then
+ * read only those inodes in from disk.
+ */
+ if (preen && usedsoftdep) {
+ cp = &cg_inosused(&cgrp)[(inosused - 1) / CHAR_BIT];
+ for ( ; inosused > 0; inosused -= CHAR_BIT, cp--) {
+ if (*cp == 0)
+ continue;
+ for (i = 1 << (CHAR_BIT - 1); i > 0; i >>= 1) {
+ if (*cp & i)
+ break;
+ inosused--;
+ }
+ break;
+ }
+ if (inosused < 0)
+ inosused = 0;
+ }
+ /*
+ * Allocate inoinfo structures for the allocated inodes.
+ */
+ inostathead[c].il_numalloced = inosused;
+ if (inosused == 0) {
+ inostathead[c].il_stat = 0;
+ continue;
+ }
+ info = calloc((unsigned)inosused, sizeof(struct inostat));
+ inospace = (unsigned)inosused * sizeof(struct inostat);
+ if (info == NULL)
+ errexit("cannot alloc %u bytes for inoinfo",
+ (unsigned)(sizeof(struct inostat) * inosused));
+ inostathead[c].il_stat = info;
+ /*
+ * Scan the allocated inodes.
+ */
for (i = 0; i < inosused; i++, inumber++) {
info_inumber = inumber;
- if (inumber < ROOTINO)
+ if (inumber < ROOTINO) {
+ (void)getnextinode(inumber);
continue;
+ }
checkinode(inumber, &idesc);
}
+ lastino += 1;
+ if (inosused < sblock.fs_ipg || inumber == lastino)
+ continue;
+ /*
+ * If we were not able to determine in advance which inodes
+ * were in use, then reduce the size of the inoinfo structure
+ * to the size necessary to describe the inodes that we
+ * really found.
+ */
+ if (lastino < (c * sblock.fs_ipg))
+ ninosused = 0;
+ else
+ ninosused = lastino - (c * sblock.fs_ipg);
+ inostathead[c].il_numalloced = ninosused;
+ if (ninosused == 0) {
+ free(inostathead[c].il_stat);
+ inostathead[c].il_stat = 0;
+ continue;
+ }
+ if (ninosused != inosused) {
+ struct inostat *ninfo;
+ size_t ninospace = ninosused * sizeof(*ninfo);
+ if (ninospace / sizeof(*info) != ninosused) {
+ pfatal("too many inodes %llu\n",
+ (unsigned long long)ninosused);
+ exit(8);
+ }
+ ninfo = realloc(info, ninospace);
+ if (ninfo == NULL) {
+ pfatal("cannot realloc %zu bytes to %zu "
+ "for inoinfo\n", inospace, ninospace);
+ exit(8);
+ }
+ if (ninosused > inosused)
+ (void)memset(&ninfo[inosused], 0, ninospace -
inospace);
+ inostathead[c].il_stat = ninfo;
+ }
}
info_fn = NULL;
freeinodebuf();
@@ -244,7 +325,7 @@ checkinode(ino_t inumber, struct inodesc
if (ftypeok(dp) == 0)
goto unknown;
n_files++;
- lncntp[inumber] = DIP(dp, di_nlink);
+ ILNCOUNT(inumber) = DIP(dp, di_nlink);
if (DIP(dp, di_nlink) <= 0) {
zlnp = malloc(sizeof *zlnp);
if (zlnp == NULL) {
Index: pass2.c
===================================================================
RCS file: /cvs/src/sbin/fsck_ffs/pass2.c,v
retrieving revision 1.29
diff -u -p -r1.29 pass2.c
--- pass2.c 27 Oct 2009 23:59:32 -0000 1.29
+++ pass2.c 31 Mar 2011 08:33:22 -0000
@@ -213,15 +213,15 @@ pass2(void)
if (reply("FIX") == 0)
continue;
(void)makeentry(inp->i_number, inp->i_parent, "..");
- lncntp[inp->i_parent]--;
+ ILNCOUNT(inp->i_parent)--;
continue;
}
fileerror(inp->i_parent, inp->i_number,
"BAD INODE NUMBER FOR '..'");
if (reply("FIX") == 0)
continue;
- lncntp[inp->i_dotdot]++;
- lncntp[inp->i_parent]--;
+ ILNCOUNT(inp->i_dotdot)++;
+ ILNCOUNT(inp->i_parent)--;
inp->i_dotdot = inp->i_parent;
(void)changeino(inp->i_number, "..", inp->i_parent);
}
@@ -318,7 +318,7 @@ pass2check(struct inodesc *idesc)
proto.d_reclen = entrysize;
memcpy(dirp, &proto, (size_t)entrysize);
idesc->id_entryno++;
- lncntp[dirp->d_ino]--;
+ ILNCOUNT(dirp->d_ino)--;
dirp = (struct direct *)((char *)(dirp) + entrysize);
memset(dirp, 0, (size_t)n);
dirp->d_reclen = n;
@@ -353,7 +353,7 @@ chk1:
proto.d_reclen = dirp->d_reclen - n;
dirp->d_reclen = n;
idesc->id_entryno++;
- lncntp[dirp->d_ino]--;
+ ILNCOUNT(dirp->d_ino)--;
dirp = (struct direct *)((char *)(dirp) + n);
memset(dirp, 0, (size_t)proto.d_reclen);
dirp->d_reclen = proto.d_reclen;
@@ -390,7 +390,7 @@ chk1:
}
idesc->id_entryno++;
if (dirp->d_ino != 0)
- lncntp[dirp->d_ino]--;
+ ILNCOUNT(dirp->d_ino)--;
return (ret|KEEPON);
chk2:
if (dirp->d_ino == 0)
@@ -446,7 +446,7 @@ again:
dp = ginode(dirp->d_ino);
SET_ISTATE(dirp->d_ino, (DIP(dp, di_mode) & IFMT) ==
IFDIR ? DSTATE : FSTATE);
- lncntp[dirp->d_ino] = DIP(dp, di_nlink);
+ ILNCOUNT(dirp->d_ino) = DIP(dp, di_nlink);
goto again;
case DSTATE:
@@ -481,7 +481,7 @@ again:
if (reply("FIX") == 1)
ret |= ALTERED;
}
- lncntp[dirp->d_ino]--;
+ ILNCOUNT(dirp->d_ino)--;
break;
default:
Index: pass3.c
===================================================================
RCS file: /cvs/src/sbin/fsck_ffs/pass3.c,v
retrieving revision 1.14
diff -u -p -r1.14 pass3.c
--- pass3.c 27 Oct 2009 23:59:32 -0000 1.14
+++ pass3.c 31 Mar 2011 08:31:35 -0000
@@ -73,7 +73,7 @@ pass3(void)
}
if (linkup(orphan, inp->i_dotdot)) {
inp->i_parent = inp->i_dotdot = lfdir;
- lncntp[lfdir]--;
+ ILNCOUNT(lfdir)--;
pinp = getinoinfo(inp->i_parent);
inp->i_parentp = pinp;
inp->i_sibling = pinp->i_child;
Index: pass4.c
===================================================================
RCS file: /cvs/src/sbin/fsck_ffs/pass4.c,v
retrieving revision 1.19
diff -u -p -r1.19 pass4.c
--- pass4.c 27 Oct 2009 23:59:32 -0000 1.19
+++ pass4.c 31 Mar 2011 12:15:18 -0000
@@ -66,7 +66,7 @@ pass4(void)
info_fn = pass4_info;
for (c = 0; c < sblock.fs_ncg; c++) {
inumber = c * sblock.fs_ipg;
- for (i = 0; i < cginosused[c]; i++, inumber++) {
+ for (i = 0; i < inostathead[c].il_numalloced; i++, inumber++) {
if (inumber < ROOTINO)
continue;
idesc.id_number = inumber;
@@ -74,7 +74,7 @@ pass4(void)
case FSTATE:
case DFOUND:
- n = lncntp[inumber];
+ n = ILNCOUNT(inumber);
if (n) {
adjust(&idesc, (short)n);
break;
Index: pass5.c
===================================================================
RCS file: /cvs/src/sbin/fsck_ffs/pass5.c,v
retrieving revision 1.39
diff -u -p -r1.39 pass5.c
--- pass5.c 9 Jul 2010 06:41:17 -0000 1.39
+++ pass5.c 31 Mar 2011 12:15:53 -0000
@@ -230,7 +230,7 @@ pass5(void)
if (fs->fs_postblformat == FS_42POSTBLFMT)
ocg->cg_magic = CG_MAGIC;
j = fs->fs_ipg * c;
- for (i = 0; i < cginosused[c]; j++, i++) {
+ for (i = 0; i < inostathead[c].il_numalloced; j++, i++) {
switch (GET_ISTATE(j)) {
case USTATE:
Index: setup.c
===================================================================
RCS file: /cvs/src/sbin/fsck_ffs/setup.c,v
retrieving revision 1.46
diff -u -p -r1.46 setup.c
--- setup.c 12 Aug 2010 15:26:34 -0000 1.46
+++ setup.c 31 Mar 2011 12:19:54 -0000
@@ -427,22 +427,11 @@ found:
(unsigned)bmapsize);
goto badsblabel;
}
- stmap = calloc((unsigned)(maxino + 1), sizeof(char));
- if (stmap == NULL) {
- printf("cannot alloc %u bytes for stmap\n",
- (unsigned)(maxino + 1));
- goto badsblabel;
- }
- lncntp = calloc((unsigned)(maxino + 1), sizeof(int16_t));
- if (lncntp == NULL) {
- printf("cannot alloc %zu bytes for lncntp\n",
- (maxino + 1) * sizeof(int16_t));
- goto badsblabel;
- }
- cginosused = calloc((unsigned)sblock.fs_ncg, sizeof(long));
- if (cginosused == NULL) {
- printf("cannot alloc %u bytes for cginosused\n",
- (unsigned)sblock.fs_ncg);
+ inostathead = calloc((unsigned)(sblock.fs_ncg),
+ sizeof(struct inostatlist));
+ if (inostathead == NULL) {
+ printf("cannot alloc %u bytes for inostathead\n",
+ (unsigned)(sizeof(struct inostatlist) * (sblock.fs_ncg)));
goto badsblabel;
}
numdirs = MAX(sblock.fs_cstotal.cs_ndir, 128);
Index: utilities.c
===================================================================
RCS file: /cvs/src/sbin/fsck_ffs/utilities.c,v
retrieving revision 1.37
diff -u -p -r1.37 utilities.c
--- utilities.c 10 Dec 2009 16:01:51 -0000 1.37
+++ utilities.c 31 Mar 2011 12:21:28 -0000
@@ -116,6 +116,25 @@ reply(char *question)
}
/*
+ * Look up state information for an inode.
+ */
+struct inostat *
+inoinfo(ino_t inum)
+{
+ static struct inostat unallocated = { USTATE, 0, 0 };
+ struct inostatlist *ilp;
+ int iloff;
+
+ if (inum > maxino)
+ errexit("inoinfo: inumber %d out of range", inum);
+ ilp = &inostathead[inum / sblock.fs_ipg];
+ iloff = inum % sblock.fs_ipg;
+ if (iloff >= ilp->il_numalloced)
+ return (&unallocated);
+ return (&ilp->il_stat[iloff]);
+}
+
+/*
* Malloc buffers and set up cache.
*/
void
