memory saving patch to dosfsck

To get your fix included in Ubuntu, try transforming it into a debdiff (http://wiki.ubuntu.com/PackagingGuide/Recipes/Debdiff) and submitting it for review (http://wiki.ubuntu.com/SponsorshipProcess).

Marking 'incomplete' for now.

Setting to In Progress.

This bug was fixed in the package dosfstools - 2.11-2.3ubuntu1

---------------
dosfstools (2.11-2.3ubuntu1) hardy; urgency=low

  * Patch from Eero Tamminen <email address hidden> to improve memory
    efficiency when checking filesystems. (LP: #189184)

 -- Luke Yelavich <email address hidden> Wed, 12 Mar 2008 22:34:51 +1100

We found a memory alignment problem from the patch. It was an issue in ARM platform (tested in Nokia N800). Here's a bug-fixed version.

The bugfix consists of these lines:
+ /* dosfsck doesn't use doubles, so it's safe to align just to 4 */
+ size = (size+3) & ~3;

Ignore the last comment, the bug is only in this newer version of the patch... Here're some additional comments and measurements from Eero about the new patch.

-----
Here are patches for reducing the huge dosfsck memory usage to something
slightly more reasonable. Except for the dosfsck.h bitfield change,
they should be easy/straightforward to verify/review. As far as I could
see, the bitfield change is also safe.

In common.c:
* By using special block allocator, the 8 byte qalloc() and 8 byte
  C-library malloc() overhead can be avoided. According to Valgrind
  Massif, this reduces dosfsck memory usage from over 120MB[1] to
 slightly over 80MB with a 8GB FAT file system full of files
* Changed common.h function prototypes to use size_t like malloc does

[1] full 8GB file system, before:
  n time(i) total(B) useful-heap(B) extra-heap(B)
  ------------------------------------------------------------------
   79 22,339,620,705 121,351,024 91,858,713 29,492,311
   80 22,368,083,813 121,487,936 91,958,709 29,529,227
 75.69% (91,958,709B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
    ->75.69% (91,958,002B) 0x804CC40: alloc (common.c:52)
    | ->64.91% (78,855,324B) 0x804CC8E: qalloc (common.c:65)
    | | ->50.09% (60,851,840B) 0x804C1B2: add_file (check.c:787)
    | | | ->50.09% (60,851,784B) 0x804C9EA: subdirs (check.c:824)
    | | | | ->50.08% (60,840,584B) 0x804CA5F: subdirs (check.c:833)
    | | | | | ->49.65% (60,316,424B) 0x804CA5F: subdirs (check.c:833)
    | | | | | | ->35.85% (43,554,504B) 0x804CA5F: subdirs (check.c:833)
    | | | | | | | ->35.85% (43,554,504B) 0x804CB67: scan_root (check.c:869)
    | | | | | | | ->35.85% (43,554,504B) 0x804D2AC: main (dosfsck.c:166)

After optimizations:
  n time(i) total(B) useful-heap(B) extra-heap(B)
  -----------------------------------------------------------------
  55 22,411,187,114 81,472,072 81,203,278 268,794
 99.67% (81,203,278B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
 ->99.67% (81,203,278B) 0x804CC40: alloc (common.c:63)
   ->84.08% (68,498,528B) 0x804CCB5: qalloc (common.c:86)
     | ->82.07% (66,863,328B) 0x804C1B2: add_file (check.c:787)
     | | ->82.06% (66,859,240B) 0x804C9EA: subdirs (check.c:824)
     | | | ->82.05% (66,851,064B) 0x804CA5F: subdirs (check.c:833)
     | | | | ->81.43% (66,340,064B) 0x804CA5F: subdirs (check.c:833)
     | | | | | ->54.36% (44,289,392B) 0x804CA5F: subdirs (check.c:833)
     | | | | | | ->54.36% (44,289,392B) 0x804CB67: scan_root (check.c:869)
     | | | | | | ->54.36% (44,289,392B) 0x804D1FD: main (dosfsck.c:166)

For another full, 2GB filesystem:

* Before:
        alloc size: count: total: + overhead:
               8 248917 1991336 1991336
              56 186687 10454472 1493496
              94 4427 416138 35416
              95 43824 4163280 350592
              96 13978 1341888 111824
          752556 1 752556 8
  total of a...

Any reason why the last patch from half a year ago wasn't applied?

It has three separate optimization:
- Allocation overhead reduction (in my full 8GB file system case, reduced total memory usage from 120MB to 80MB)
- FAT entry size reduction by changing 32+32 bits to bitfield (thing that needs to be checked most closely)
- Keeping only one FAT entry in memory once FATs are checked to match (with tens of GB sized file systems, saves tens of MBs of RAM)

First two optimizations help more with full file systems, the last (already applied as that was in the first patch) one has most significance when the file system is fairly empty and less memory needs to be used for checking directory contents.

Huh?

In Comment #4 you would see that your patch was included in dosfstools 2.11-2.3ubuntu1, the bug was marked "fix released" on 12 Mar 08 - 11:45

If that is not what you mean, then can you please elaborate?

> In Comment #4 you would see that your patch was included in dosfstools 2.11-2.3ubuntu1,
> the bug was marked "fix released" on 12 Mar 08 - 11:45 If that is not what you mean, then
> can you please elaborate?

I was referring to the much updated patch in comment 5.