Re: [PATCH]: icount: Replace the icount list by a two-level tree

[Andreas Dilger <adilger.kernel@dilger.ca>]

On 2010-11-01, at 16:49, Mala Iyer wrote:
> We are trying to use e2fsck on a embedded system with almost 3GB of swap and
> 200MB of physical memory. e2fsck on a 16TB ext3 filesystem always appears to
> fail with the following error
> 
> Pass 1D: Reconciling multiply-claimed blocks
> e2fsck: Memory allocation failed while retrying to read bitmaps for /dev/sda1

As a general rule of thumb, expect to use 1 byte of RAM for every block in the filesystem.  For a 16TB filesystem (2^32 blocks) I would expect to need about 4GB of RAM, from past experience.

There is a considerable amount of RAM savings that could be had by implementing more efficient sparse bitmap support internal to libext2fs.  The code is structured and ready to do this, but nobody has had a real need to do it before now.

Some proposals were discussed in the past (see for example the brief description in https://bugzilla.lustre.org/show_bug.cgi?id=12202, and you can Google for the referenced thread in the archives) to use run-length-encoding of sparse bitmaps, or possibly rb-tree structures.  In most cases, the bitmaps will have long runs of either all-ones or all-zeroes, so I expect even simple RLE encoding could help significantly.  Since this is an internal implementation detail, the code can be changed in future releases without impacting interoperability.

Also, https://bugzilla.lustre.org/attachment.cgi?id=10088 has an out-of-date patch (see the "ebitmap.c" file) that you might consider using for reference, but I also believe the APIs in libext2fs have changed significantly, as has the desired implementation, so I doubt the patch is useful for anything except finding out which code to start changing.

Cheers, Andreas