On Thu, Apr 07, 2011 at 11:08:05AM +0200, Otto Moerbeek wrote: > Hi, > > I got little feedeback on this diff posed in a rather long thread, so > I am posting it again. > > Please test this, it makes fsck_ffs much faster (especially with -p) > and less memory hungry in a lot of cases. > > Note that to force a check with -p you need to unmount the filesystem, > mosty practical is do it in single user mode: > > # shutdown now > .. > # umount -a > # fsck -pf > > (Don't forget the unmount!) > > Other way: pull the plug on a machine and let it reboot. That is a > more realistic check and it is safe because you already backup up all > your data, right?
I went the unplug route on the i386 box and amd64 box I have here, and the diff seems to work. Reads ok. I say go for it. .... Ken > > -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 4 Apr 2011 09:15:49 -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 4 Apr 2011 09:15:49 -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 4 Apr 2011 09:15:49 -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 4 Apr 2011 09:16:36 -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++) { > + SET_ISTATE(i, 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 4 Apr 2011 09:15:49 -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 4 Apr 2011 09:15:49 -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 4 Apr 2011 09:15:49 -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 4 Apr 2011 09:15:49 -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 4 Apr 2011 09:15:49 -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 4 Apr 2011 09:15:49 -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 4 Apr 2011 09:15:49 -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 4 Apr 2011 09:15:49 -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