Create a FAT32 Defragmenter

[Multit4sker]

Hi guys !

In order to learn low level programming, I started to create a FAT32 defragmenter and for the moment it learned me a lot (the structure of FAT32, how it works, how datas are structured using clusters that are mapped on the Fat table etc.. etc...).

I succeeded to parse the boot sector using C++. I have all my informations (bytes per sector, sectors per cluster etc...).
Using these informations, I parsed the root directory and I listed the files and directories.

What's next ?

I don't know what I have to do next to achieve my defragmenter.

Any help ? :p

Thank you.

[mariuszp]

You have to relocate the data in each file such that it is consecutive.

If a file is made up of blocks A, B and C, and their indices are 0, 1 and 5, you must move block C to be in position 2.

A way to do this would be to figure which file's data (if any) is in block 2, then SWAP it with block 5. If position 2 is already free, just move the block in position 5 to position 2, a free position 5 instead.

Repeat until either all files are consecutive, or no more swaps are possible for whatever reason (though i can't imagine why they wouldn't be).

Remember to update the file metadata when updating its positions on disk!

[Multit4sker]

Ok, so if I understand.
I have first to create a data structure that contains each file and its associated clusters.
Then using that data structure, I loop for each file and move the clusters such as they are consecutive. And repeat for each file.

[mariuszp]

Yes, while ensuring you're not destroying other files. When swapping clusters, make sure the information on each file reflects its cluster bieng moved.

[~]

You could make a FAT32 image from one of your real disks or SD cards.

You could take a SHA-512 or MD5Sum snapshot of all present files. You can use RHash for that.

Then you could make a copy of this disk image, mount it, and test your defragmenter.

I think that you can also defragment directories as if they were files with the indexes of the files they contain.

With this you can repeat the defragmentation process until it is completely bug-free and until no files or directories become corrupted.

[Boris]

A good defragmentation algorithm may take the physical geometry of the disk into account: remember that your goal is to reduce the time lost during seek ( moving the head from center to border of the disk, or reverse thing) and latency ( time you let the disk spin to reach desired sector).
Remember that the border of the disk moves faster than the center.

[MichaelFarthing]

A good defragmentation algorithm may take the physical geometry of the disk into account: remember that your goal is to reduce the time lost during seek ( moving the head from center to border of the disk, or reverse thing) and latency ( time you let the disk spin to reach desired sector).
Remember that the border of the disk moves faster than the center.

Lets not forget that Multitasker's (yeah I know there's a 4 in there somewhere, but as this is a quick reply I can't see where) purpose is to complete the task as an exercise in low level progamming. Lets not divert him into practicing 4 octaves with both hands in D flat minor when he's set out to play C major with one hand. Good luck Multitasker. Stick at at. You'll make millions of mistakes. You'll spend hours scratching your head and pulling your hair out. You'll manage it. You'll feel great. You'll move on to the next harder project. You'll make millions of mistakes. You'll spend hours scratching your head and pulling your hair out... This is a fantastic hobby!

[Boris]

For this particular job ( defragmentation ) I recommend to avoid doing it low level; As ~ said it, you can work with file images. Do it. Just use fread and fwrite calls instead of writing on the disk for now. Experiment moving files inside your image before doing it on disk, checking errors, avoiding bad sectors..
Unlike this is what you really like !

[Multit4sker]

Thanks guys !
It's effectively the hard and better way to learn :p

I succeeded to write a method that list all the clusters of all the files of my usb key root directory ( and root directories of directories etc...).
So now I have a vector of File structure and each File structure contains a vector of DWORD clusters.

Now I'm trying to create the method to swap 2 clusters.
I managed to swap 2 data cluster (in the data region) and now I have to do the same thing in the fat table (change values of previous clusters by updating them with the new cluster value).
I think I have to check if the swapped cluster isn't a first cluster of some file, cause in that case, I don't have to update the fat but change the first_cluster property of the file in root directory.

[Kevin]

One thing to consider if you ever want to use this code on real disks with valuable data is that you want to make sure that the file system is as consistent as possible at any point during the operation (for FAT this probably means that there can be some leaked clusters, but any cluster that is in use has the correct data). The reason is that you can never predict power outage or other crashes and you don't want to lose data or corrupt the file system in such cases. For getting the right I/O ordering, you need to flush the disk in the right places (fsync if you're implementing this as a Linux program), otherwise caches could change the order of requests.

[rdos]

The most useful property of such a tool is to recover lost clusters and find and fix errors in the filesystem. The optimization really is secondary to fixing corrupt file systems.

[StephanvanSchaik]

The most useful property of such a tool is to recover lost clusters and find and fix errors in the filesystem. The optimization really is secondary to fixing corrupt file systems.

Having written a utility for checking FAT12/16/32 filesystems back in 2011, I agree with this. You will not only learn about the structure behind the FAT filesystem, but you will also learn what kind of problems can occur with a FAT filesystem, whether they can be solved and how to actually solve them. I also agree with writing such a tool in your favourite language of choice for your favourite OS of choice, as it is much easier to do this in userspace, but do feel free to approach it differently.

Anyway, I've got a few recommendations for you if you are willing to write a utility that is capable of identifying and resolving issues with any existing FAT filesystem:

• Create and format an image with a few directories and files on it.
• Try to think what kind of issues this image could end up with and create modified copies with these issues in-place (most of the issues will have to do with cluster chains, for example, a cluster may end up being shared by more than one file, a cluster chain may contain an infinite loop or there may be dangling clusters that originally belonged to a file). Also make sure that you create a few test images with a corrupted copy of the file allocation table.
• Since you can have more than one file allocation table, it is worth evaluating each of them and assigning a score to each of them that essentially tells you how many issues you have found with each of the file allocation tables and to pick the best one to use.
• A more advanced approach would be to try and figure out what issues only exist with one of the file allocation tables but not with the other, so that you can pick the best of both. As I have not implemented this before, I am not really certain how viable this approach is.
• As I have mentioned before most of the issues will have to do with the cluster chain. In most cases the simplest option would be to truncate the cluster chain up to the point where you found a faulty cluster. Unfortunately, if that happens, it means that the data may be lost. A better approach may be to support user intervention where your utility essentially offers a shell that allows you to introspect dangling clusters and fix cluster chains by hand.

I think that once you have written such a utility, reasoning and implementing the defragmentation part may end being a lot easier.


Yours sincerely,
Stephan.

[rdos]

I've decided to build fail-safe operation into the FAT FS driver rather than trying to defragment or correct errors. It's possible to schedule FS updates in such a way that you will only loose clusters during power failures / random restarts, and invalid cross-links will never happen. Typically, a few lost clusters will not be a problem. In production systems, I also locate application code and data on a separate partition that I can recreate under fatal conditions (although this very rarely happens).

Still, a defragmenter and error corrector could be interesting too.