Re: what is fsck's "slowdown"?

On  3 Sep, Marc G. Fournier wrote:
> 
> I'm running another fsck on a 4.x system ... I know 5.x brings in the 
> background mode for it, which would definitely make my life easier, *but* 
> ... when running fsck, it says its using up 99% of the CPU:
> 
> # ps aux | grep fsck
> root    67 99.0  5.0 184252 184284  p0  R+   12:46PM 254:16.68 fsck -y /vm
> 
> now, its a dual CPU system ... on an MP system, is it not possible to have 
> it parallelize on a file system, so that it makes use of all available 
> CPU?
> 
> For instance, right now, its in Phase 4 ... on a file system where ctl-t 
> shows:
> 
> load: 0.99  cmd: fsck 67 [running] 15192.26u 142.30s 99% 184284k
> /dev/da0s1h: phase 4: cyl group 408 of 866 (47%)
> 
> wouldn't it be possible, on a dual CPU system, to have group 434 and above 
> run on one process, while group 433 and below running on the second, in 
> parallel?  Its not like the drives are being beat up:

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.