Re: what is fsck's "slowdown"?

On 2004-09-03 14:58, Don Lewis <truckman_at_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.