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