tech-kern archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

Re: [GSoC 2013] Defragmentation for FFS



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



Home | Main Index | Thread Index | Old Index