linux-ext4 - Re: [PATCH 2/4 v2] e2fsprogs: Add rbtree backend for bitmaps, use it instead of bitarrays

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.1103181046370.4087@dhcp-27-109.brq.redhat.com>
Date:	Fri, 18 Mar 2011 10:55:38 +0100 (CET)
From:	Lukas Czerner <lczerner@...hat.com>
To:	Andreas Dilger <adilger@...ger.ca>
cc:	Lukas Czerner <lczerner@...hat.com>, linux-ext4@...r.kernel.org,
	tytso@....edu, sandeen@...hat.com
Subject: Re: [PATCH 2/4 v2] e2fsprogs: Add rbtree backend for bitmaps, use
 it instead of bitarrays

On Thu, 17 Mar 2011, Andreas Dilger wrote:

> On 2011-03-17, at 12:50 PM, Lukas Czerner wrote:
> > +++ b/lib/ext2fs/blkmap64_rb.c
> > +struct bmap_rb_extent {
> > +	struct rb_node node;
> > +	__u64 start;
> > +	__u32 count;
> > +};
> 
> On 32-bit machines (where memory consumption is even more critical) this will pack better by arranging it with "count" aligned with rb_parent_color:
> 
> struct bmap_rb_extent {
> 	__u64 start;
> 	__u32 count;
> 	struct rb_node node;
> };
> 
> That will give a leaf size of 24 bytes on a 32-bit arch, instead of 32 bytes with padding.  On a 64-bit arch it won't make any difference.

Oh, of course, do not know how I missed that.

> 
> > static errcode_t rb_resize_bmap(ext2fs_generic_bitmap bmap,
> > +				__u64 new_end, __u64 new_real_end)
> > +{
> > +	struct ext2fs_rb_private *bp;
> > +
> > +	if (new_real_end >= bmap->real_end) {
> > +		bmap->end = new_end;
> > +		bmap->real_end = new_real_end;
> > +		return 0;
> > +	}
> > +
> > +	bp = (struct ext2fs_rb_private *) bmap->private;
> > +	*bp->rcursor = NULL;
> > +	*bp->wcursor = NULL;
> > +
> > +	/* truncate tree to new_real_end size */
> > +	rb_truncate(new_real_end, &bp->root);
> > +
> > +	bmap->end = new_end;
> > +	bmap->real_end = new_real_end;
> > +	return 0;
> > +
> > +}
> 
> This might be a bit better written as:
> 
> static errcode_t rb_resize_bmap(ext2fs_generic_bitmap bmap,
> 				__u64 new_end, __u64 new_real_end)
> {
> 	struct ext2fs_rb_private *bp;
> 
> 	if (new_real_end < bmap->real_end) {
> 		bp = (struct ext2fs_rb_private *)bmap->private;
> 		*bp->rcursor = NULL;
> 		*bp->wcursor = NULL;
> 
> 		/* truncate tree to new_real_end size */
> 		rb_truncate(new_real_end, &bp->root);
> 	}
> 
> 	bmap->end = new_end;
> 	bmap->real_end = new_real_end;
> 	return 0;
> 
> }

Right that's definitely better.

> 
> > +inline static int
> > +rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
> > +{
> > +	struct bmap_rb_extent *rcursor;
> > +	struct rb_node *parent = NULL;
> > +	struct rb_node **n = &bp->root.rb_node;
> > +	struct bmap_rb_extent *ext;
> > +	int i=0;
> > +
> > +	rcursor = *bp->rcursor;
> > +	if (!rcursor)
> > +		goto search_tree;
> > +
> > +	if (bit >= rcursor->start && bit < rcursor->start + rcursor->count)
> > +		return 1;
> > +
> > +	rcursor = *bp->wcursor;
> > +	if (!rcursor)
> > +		goto search_tree;
> > +
> > +	if (bit >= rcursor->start && bit < rcursor->start + rcursor->count)
> > +		return 1;
> > +
> > +search_tree:
> > +
> > +	while (*n) {
> > +		parent = *n;
> > +		ext = rb_entry(parent, struct bmap_rb_extent, node);
> > +		if (bit < ext->start)
> > +			n = &(*n)->rb_left;
> > +		else if (bit >= (ext->start + ext->count))
> > +			n = &(*n)->rb_right;
> > +		else {
> > +			*bp->rcursor = ext;
> > +			return 1;
> > +		}
> > +	}
> > +	return 0;
> > +}
> 
> This seems quite large for a static inline?  I guess it is only called by a single function, so maybe not a big deal.

It is actually called for two functions and since this is the most
called function, I think this it is worth it (there is approx. 1%
performance boost bound with this).

> 
> > +inline
> > +static int rb_test_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
> > +{
> > +	struct ext2fs_rb_private *bp;
> > +
> > +	bp = (struct ext2fs_rb_private *) bitmap->private;
> > +	arg -= bitmap->start;
> > +
> > +	return rb_test_bit(bp, arg);
> > +}
> 
> This definitely doesn't make sense to be static inline, since its only use is by ext2_bitmap_ops table, so it can't possibly be inline...

Right, I'll fix that.

> 
> > @@ -158,6 +161,7 @@ void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
> > 		bmap->description = 0;
> > 	}
> > 	bmap->magic = 0;
> > +	ext2fs_free_mem(&bmap);
> > }
> 
> This is really a defect in the original e2fsprogs, so it might make sense to submit it independently in case Ted isn't going to apply this patch right away.

Yes, somehow I forgot about that. Thanks.

> 
> Cheers, Andreas
> 

Thanks!
-Lukas
--
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