Re: [GSoC 2013] Defragmentation for FFS

[Manuel Wiesinger <manuel%lungenarzt-wien.at@localhost>]

My mentors asked for a weekly status update, on the mailing list. So 
here it is (later than I said, writing code is just more fun than 
documenting what you do).


General information:

In total my tool will do three optimizations:
.) fragmented blocks optimization
Look for fragments and see if there is a more efficient ordering

.) the non-contiguous-file defragmentation
This is what Linux/Windows tools call defragmentation. Reordering of 
non-contiguous blocks.

.) Directory optimization
In every directory look for files that are not in the cylinder group 
like most other files in that directory, try to get files in the same 
cylinder group.

My implementation steps.

.) Analysis:
Iterate the whole whole filesystem, directory by directory and file by 
file. Save every file that has fragmented blocks in a list, the 
fragmentation list. Store each file that contains non-contiguous blocks 
or has fragments in a list, the file list. While iterating check every 
directory, if all files are in the same cylinder group. If not, add the 
directory to another list, the directory list.

.) Pre-Defragmentation:

step 1:
For every file that is in the fragmentation list, try to find space in 
the same cylinder group to get the fragments into fewer blocks.

step 2:
For every file in the file list, look for potential free contiguous 
blocks in a file's cylinder group. Include the results of step 1

step 3:
Iterate the directory list, try to find free space in the cylinder group 
the majority of file is saved in. If not enough space is found, try to 
find space for the whole directory in another cylinder group. Include 
the results of step 1+2.

Every finding of the above steps is simply stored in the list, which is 
constructed of structs. Also the metadata changes are stored to the list.

Defragmentation:
move the blocks and update the metadata in the order we spoke about 
before (copy datablocks, update meta-data, sync to disk).

Other things worth mentioning:
.) WAPBL support (see, if there the is a log)
.) crash safety (by the ordering of the operations, in the worst case 
fsck, can always fix it)
.) endianness is treated the way as in fsck (if it is wrong, change it 
in memory)

My status:
I'm still working on the analysis part. I'm making progress. My current 
code uses a lot of fsck's functions and statically links them. This is 
not the most finest way in my eyes. But anyway better than reinventing 
the wheel, while there is well tested code which does exactly what I 
need. Other tools (newfs, fsdb and a third one I forgot) do exactly the 
same.

Comments are very welcome!

Manuel