Date: Sat, 4 Sep 2004 01:16:28 +0300 From: Giorgos Keramidas <keramida@linux.gr> To: Don Lewis <truckman@freebsd.org> Cc: freebsd-current@freebsd.org Subject: Re: what is fsck's "slowdown"? Message-ID: <20040903221628.GA51595@gothmog.gr> In-Reply-To: <200409032158.i83LwdWg030214@gw.catspoiler.org> References: <20040903175434.A812@ganymede.hub.org> <200409032158.i83LwdWg030214@gw.catspoiler.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On 2004-09-03 14:58, Don Lewis <truckman@freebsd.org> wrote: > > Would the file system in question happen to be full of UNREF files that > fsck is deleting? > > I just took a look at the sparsely commented fsck code and it looks like > fsck builds a list of inodes that have a zero link count during pass 1. > During pass 4 fsck visits each inode that it has marked as being in > either the FSTATE or DFOUND states, and either adjusts the inodes link > count, or of the link count is zero, it removes the inode from the list > it constructed in pass 1 and clears the inode. > > Because this list is just a linear linked list and inodes are prepended > to the beginning in increasing inode order, and inodes are removed in > increasing inode order, it looks like the entire list needs to be > traversed each time an inode is removed. That would cause the run time > to increase as the square of the number of UNREF'ed inodes. > > Using two CPUs would give you at best a 2x speedup, and in this case it > would be quite a bit less since both CPUs would be trying to access and > modify the same data structure. Just using a better data structure is > likely to speed things up much more than 2x. Something as simple as > building the list in reverse order in pass 1 is likely to make a huge > difference. Holding both a head and tail pointer to the singly-linked list should probably make it easier to add nodes at the end of the list instead of the head. I haven't read the source of fsck_ffs at all though, so I don't know if I can come up with a working patch in a reasonable amount of time.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20040903221628.GA51595>