linux-ext4 - Re: resize2fs memory footprint

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <20100215215012.GO5337@thunk.org>
Date:	Mon, 15 Feb 2010 16:50:12 -0500
From:	tytso@....edu
To:	Ulrich Bauer <u.bauer@...ay.de>
Cc:	linux-ext4@...r.kernel.org
Subject: Re: resize2fs memory footprint

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
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html