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]

Date:	Thu, 17 Mar 2011 13:56:42 -0600
From:	Andreas Dilger <adilger@...ger.ca>
To:	Lukas Czerner <lczerner@...hat.com>
Cc:	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 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.

> 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;

}

> +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.

> +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...

> @@ -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.

Cheers, Andreas





--
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