> I have no idea about the internals of fsck, but I can't conceptually
> see reasons why it cannot be made run linear or, at worse,
> O(N lg N): and even with N lg N would not make a *concrete*
> difference splitting the filesystem in smaller pieces.

If you take the case where there are no doubly allocated blocks
(they are unusual if the fs and disk are behaving) then you should
only need 1 bit per fragment to fix the allocation map.
You need that map to fit in memory - if it won't you have to 'go slow'.

You should then be able to (for each cylinder group):
- traverse the inode array and remember the blocks that are
  a) directories
  b) allocation maps
- traverse the directory blocks to check the reference counts
- traverse the alocation maps to find further maps and allocated blocks

The latter traverses can be done in sector order - since you don't actually
care (I think) which inode they belong to.

If you get any doubly allocated blocks, then you need to do a full rescan
to find them.  This time saving the inode number of each allocated block,
but you can ignore the blocks that aren't in error.

The lack of seeking should help no end...

	David

-- 
David Laight: david@l8s.co.uk