Re: resize2fs memory footprint

[tytso@mit.edu]

On Mon, Feb 15, 2010 at 08:56:09AM +0100, Ulrich Bauer wrote:
> A quick observation of
> resize2fs' source revealed that the latest git tree already has a
> bitmap interface that allows for different implementations of the
> bitmap manipulation algorithms. To solve the memory usage problem,
> two solutions seem to be feasible:
> 
> - For the huge bitmaps that already exist on the volume, we could
> create a disk-backed bitmap implementation that would only cache a
> small working set of the entire bitmap. My guess is that we can
> implement this efficiently enough to not loose too much performance.
> - For the all-zero bitmaps, we could implement a dummy bitmap that
> forces all bits to zero and spawns a real bitmap as soon as any bits
> are set to one. An alternative would be a tree-based aproach that
> works especially well when the bitmap is just sparsely set.

What I would recommend is a run-length encoded tree-based approached.
This should work well regardless of whether the bitmap is sparsely set
or not, because most of the time blocks are allocated contiguously.

> I'd be glad if one of the developers involved in the ext4
> development could tell me if these thoughts make sense and if yes,
> are there any plans to incorporate these approaches into the ext
> library anytime soon or does it make sense if I would have a deeper
> look into these issues and implement them? Thanks in advance for any
> thoughts about this.

There are plans to incorporate the RLE tree-based implementation, but
it's been relatively low on the priority list given all of the other
things.  If you'd be interested in implementing it, that would be
great.

							- Ted