linux-ext4 - Re: [PATCH 2/2] libext2fs: optimize rb_test

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <20121008181753.GA20682@thunk.org>
Date:	Mon, 8 Oct 2012 14:17:53 -0400
From:	Theodore Ts'o <tytso@....edu>
To:	Lukáš Czerner <lczerner@...hat.com>
Cc:	Ext4 Developers List <linux-ext4@...r.kernel.org>
Subject: Re: [PATCH 2/2] libext2fs: optimize rb_test_bit

On Mon, Oct 08, 2012 at 10:25:19AM +0200, Lukáš Czerner wrote:
> > the patch and the idea behind it look fine, especially when we're
> > walking the bitmap sequentially not modifying it simultaneously, but
> > I have one question/suggestion below.
> 
> Also for this kind of usage it might actually make sense to have
> something like:
> 
> get_next_zero_bit
> get_next_set_bit
> 
> which would be much more effective than testing single bits, but it
> would require actually using this in e2fsprogs tools.

Yes, I thought about that, and in fact we already have find_first_zero
(which takes a starting offset, so works for both find_first and
find_next).  When we introduced this, though, we accidentally
introduced a bug at first.

At some point I agree it would be good to implement find_first_set(),
and writing new unit tests, and then modify e2freefrag, e2fsck, and
dumpe2fs to use it.  But in the applications is actually pretty
tricky, and I didn't have the time I figured would be necessary to
really do the changes right, and validate/test them properly.

So yes, I agree this would be much more effective, and ultimately
would result in further speedups in e2fsck and e2freefrag in
particular.  It would also allow us to take out the test_bit
optimizations which do have a slight cost for random access reads ---
and this is measurable when looking at the results of the CPU time for
e2fsck pass 4 in particular.  It's just that the performance hit for
the random access test_bit case is very tiny compared with the huge
wins in the sequential scan case.

> > what about using the next_ext once we're holding it to check the bit
> > ? On sequential walk this shout make sense to do so since we
> > actually should hit this if we're not in rcursor nor between rcursor
> > and next_ext.

Yes, I implemented that in the 2/3 commit in the follow-on patch
series.

Cheers!

						 - 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