[Bug 1203568] [NEW] dosfsck slow repairing thousands of identically named files

[Marcel Martin]

Public bug reported:

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.

** Affects: dosfstools (Ubuntu)
     Importance: Undecided
         Status: New

-- 
You received this bug notification because you are a member of Ubuntu
Foundations Bugs, which is subscribed to dosfstools in Ubuntu.
https://bugs.launchpad.net/bugs/1203568

Title:
  dosfsck slow repairing thousands of identically named files

Status in “dosfstools” package in Ubuntu:
  New

Bug description:
  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.

To manage notifications about this bug go to:
https://bugs.launchpad.net/ubuntu/+source/dosfstools/+bug/1203568/+subscriptions