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: <alpine.LFD.2.00.1210081016160.25096@localhost>
Date:	Mon, 8 Oct 2012 10:25:19 +0200 (CEST)
From:	Lukáš Czerner <lczerner@...hat.com>
To:	Lukáš Czerner <lczerner@...hat.com>
cc:	"Theodore Ts'o" <tytso@....edu>,
	Ext4 Developers List <linux-ext4@...r.kernel.org>
Subject: Re: [PATCH 2/2] libext2fs: optimize rb_test_bit

On Mon, 8 Oct 2012, Lukáš Czerner wrote:

> Date: Mon, 8 Oct 2012 10:08:54 +0200 (CEST)
> From: Lukáš Czerner <lczerner@...hat.com>
> To: Theodore Ts'o <tytso@....edu>
> Cc: Ext4 Developers List <linux-ext4@...r.kernel.org>
> Subject: Re: [PATCH 2/2] libext2fs: optimize rb_test_bit
> 
> On Thu, 4 Oct 2012, Theodore Ts'o wrote:
> 
> > Date: Thu,  4 Oct 2012 23:44:55 -0400
> > From: Theodore Ts'o <tytso@....edu>
> > To: Ext4 Developers List <linux-ext4@...r.kernel.org>
> > Cc: Theodore Ts'o <tytso@....edu>
> > Subject: [PATCH 2/2] libext2fs: optimize rb_test_bit
> > 
> > Optimize testing for a bit in an rbtree-based bitmap for the case
> > where the calling application is scanning through the bitmap
> > sequentially.  Previously, we did this for a set of bits which were
> > inside an allocated extent, but we did not optimize the case where
> > there was a large number of bits after an allocated extents which were
> > not in use.
> > 
> >              1111111111111110000000000000000000
> >              ^ optimized    ^not optimized
> > 
> > In my tests of a roughly half-filled file system, the run time of
> > e2freefrag was halved, and the cpu time spent in userspace was during
> > e2fsck's pass 5 was reduced by a factor of 30%.
> 
> Hi Ted,
> 
> 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.

Thanks!
-Lukas

> 
> > 
> > Signed-off-by: "Theodore Ts'o" <tytso@....edu>
> > ---
> >  lib/ext2fs/blkmap64_rb.c | 16 ++++++++++++++--
> >  1 file changed, 14 insertions(+), 2 deletions(-)
> > 
> > diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c
> > index a83f8ac..c9006f8 100644
> > --- a/lib/ext2fs/blkmap64_rb.c
> > +++ b/lib/ext2fs/blkmap64_rb.c
> > @@ -314,8 +314,8 @@ static errcode_t rb_resize_bmap(ext2fs_generic_bitmap bmap,
> >  inline static int
> >  rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
> >  {
> > -	struct bmap_rb_extent *rcursor;
> > -	struct rb_node *parent = NULL;
> > +	struct bmap_rb_extent *rcursor, *next_ext;
> > +	struct rb_node *parent = NULL, *next;
> >  	struct rb_node **n = &bp->root.rb_node;
> >  	struct bmap_rb_extent *ext;
> >  
> > @@ -330,6 +330,18 @@ rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
> >  		return 1;
> >  	}
> >  
> > +	next = ext2fs_rb_next(&rcursor->node);
> > +	if (next) {
> > +		next_ext = ext2fs_rb_entry(next, struct bmap_rb_extent, node);
> > +		if ((bit >= rcursor->start + rcursor->count) &&
> > +		    (bit < next_ext->start)) {
> 
> 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.
> 
> So maybe something like this ?  (untested)
> 
> 	if (next && (bit >= rcursor->start + rcursor->count)) {
> 		next_ext = ext2fs_rb_entry(next, struct bmap_rb_extent, node);
> 		if (bit < next_ext->start)) {
> #ifdef BMAP_STATS_OPS
> 			bp->test_hit++;
> #endif
> 			return 0;
> 		} else if (bit < next_ext->start + next_ext->count) {
> #ifdef BMAP_STATS_OPS
> 			bp->test_hit++;
> #endif
> 			*bp->rcursor = next_ext;
> 			return 1;
> 		}
> 
> What do you think ? Maybe it is worth testing, whether
> the advantages are higher than additional condition ?
> 
> Thanks!
> -Lukas
> 
> 
> > +	}
> > +
> >  	rcursor = *bp->wcursor;
> >  	if (!rcursor)
> >  		goto search_tree;
> > 
> --
> 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
>