dosfsck slow repairing thousands of identically named files

[Marcel Martin]

I have an image of a broken FAT file system that contains approx. 30000 identically named files. These were created by a GPS logger, which usually writes its track into a single file, but somehow managed to create a new file each second due to a broken SD card.

To salvage the files, I use "dosfsck -aw file.img". That is initially quite fast, renaming hundreds of files per second, but gets slower and slower until renaming a single file takes multiple seconds.

The problem seems to be that the function auto_rename in in src/check.c uses a loop to find an unused file name, starting with FSCK0000.000 and incrementing to FSCK0000.001 and so on if the file name is already in use. This is slow because, for each file, all the previous file names are checked again (quadratic time).

I have solved the problem for me by using a random file name instead:

--- a/src/check.c
+++ b/src/check.c
@@ -384,7 +384,7 @@ static void auto_rename(DOS_FILE * file)
- number = 0;
+ number = random() % 10000000;
@@ -403,7 +403,7 @@ static void auto_rename(DOS_FILE * file)
- number++;
+ number = random() % 10000000;

I cancelled my first attempt of repairing the image after 12 hours. With this patch, dosfsck was finished within 2 minutes.

[Marcel Martin (marcel)]

Any news on this? It's a one-line patch.

[Launchpad Janitor (janitor)]

Status changed to 'Confirmed' because the bug affects multiple users.

[[e-mail] (mike-papersolve)]

Thanks for this patch, I was having a quite similar problem and this helped me out immensely. :)

[Marcel Martin (marcel)]

Great to hear! I'm happy that at least someone is using it. Perhaps Daniel (the maintainer) is now willing to take a second look at the problem.