what is fsck's "slowdown"?
Giorgos Keramidas
keramida at linux.gr
Fri Sep 3 15:31:17 PDT 2004
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.
More information about the freebsd-current
mailing list