Patchwork [1/6] libext2fs: optimize rb_set_bmap_range()

login
register
mail settings
Submitter Theodore Ts'o
Date Nov. 25, 2012, 12:36 a.m.
Message ID <1353803794-11593-2-git-send-email-tytso@mit.edu>
Download mbox | patch
Permalink /patch/201496/
State Superseded
Headers show

Comments

Theodore Ts'o - Nov. 25, 2012, 12:36 a.m.
This speeds up reading bitmaps from disk for very large (and full)
disks by significant amounts (i.e., up to two CPU minutes for a 4T
file system).

Addresses-Google-Bug: #7534813

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 lib/ext2fs/blkmap64_rb.c | 32 +++++++++++++++++++++++++++++---
 1 file changed, 29 insertions(+), 3 deletions(-)
Lukas Czerner - Nov. 26, 2012, 9:40 a.m.
On Sat, 24 Nov 2012, Theodore Ts'o wrote:

> Date: Sat, 24 Nov 2012 19:36:29 -0500
> From: Theodore Ts'o <tytso@mit.edu>
> To: Ext4 Developers List <linux-ext4@vger.kernel.org>
> Cc: Theodore Ts'o <tytso@mit.edu>
> Subject: [PATCH 1/6] libext2fs: optimize rb_set_bmap_range()
> 
> This speeds up reading bitmaps from disk for very large (and full)
> disks by significant amounts (i.e., up to two CPU minutes for a 4T
> file system).
> 
> Addresses-Google-Bug: #7534813
> 
> Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
> ---
>  lib/ext2fs/blkmap64_rb.c | 32 +++++++++++++++++++++++++++++---
>  1 file changed, 29 insertions(+), 3 deletions(-)
> 
> diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c
> index a42eda1..816f44f 100644
> --- a/lib/ext2fs/blkmap64_rb.c
> +++ b/lib/ext2fs/blkmap64_rb.c
> @@ -674,16 +674,42 @@ static errcode_t rb_set_bmap_range(ext2fs_generic_bitmap bitmap,
>  				     __u64 start, size_t num, void *in)
>  {
>  	struct ext2fs_rb_private *bp;
> +	unsigned char *cp;
>  	size_t i;
> +	int first_set = -1;
>  	int ret;
>  
>  	bp = (struct ext2fs_rb_private *) bitmap->private;
>  
>  	for (i = 0; i < num; i++) {
> -		ret = ext2fs_test_bit(i, in);
> -		if (ret)
> -			rb_insert_extent(start + i - bitmap->start, 1, bp);
> +		if (i & 7 == 0) {
> +			unsigned char c = cp[i/8];

I do not see cp initialized anywhere. I suppose it should map to the
'in' bitmap ?

I guess that 8 will always be aliquot part of 'num', by maybe we
could explicitly check for that to avoid access to uninitialized
memory ?

> +			if (c == 0xFF) {
> +				if (first_set == -1)
> +					first_set = i;
> +				i += 7;
> +				continue;
> +			}
> +			if ((c == 0x00) && (first_set == -1)) {
> +				i += 7;
> +				continue;
> +			}
> +		}
> +		if (ext2fs_test_bit(i, in)) {
> +			if (first_set == -1)
> +				first_set = i;
> +			continue;
> +		}
> +		if (first_set == -1)
> +			continue;
> +
> +		rb_insert_extent(start + first_set - bitmap->start,
> +				 i - first_set, bp);
> +		first_set = -1;
>  	}
> +	if (first_set != -1)
> +		rb_insert_extent(start + first_set - bitmap->start,
> +				 num - first_set, bp);
>  
>  	return 0;
>  }
> 
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Theodore Ts'o - Nov. 26, 2012, 1:36 p.m.
On Mon, Nov 26, 2012 at 10:40:28AM +0100, Lukáš Czerner wrote:
> I do not see cp initialized anywhere. I suppose it should map to the
> 'in' bitmap ?

Oops, I missed this when moving the patch over.  Thanks for pointing
this out!  Yes, it should have been initialized:

	unsigned char *cp = in;

> I guess that 8 will always be aliquot part of 'num', by maybe we
> could explicitly check for that to avoid access to uninitialized
> memory ?

It is true that ext2fs_[sg]et_bmap_range() always gets called with num
as a multiple of 8, but it should work correctly even if it isn't
here, since when we check the uninitialized bits in the last byte in
the memory range, the optimization will just fail, and then we'll fall
back to the old slow path for the last bits in the bitmap.

     	    	     	      	       - Ted
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Patch

diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c
index a42eda1..816f44f 100644
--- a/lib/ext2fs/blkmap64_rb.c
+++ b/lib/ext2fs/blkmap64_rb.c
@@ -674,16 +674,42 @@  static errcode_t rb_set_bmap_range(ext2fs_generic_bitmap bitmap,
 				     __u64 start, size_t num, void *in)
 {
 	struct ext2fs_rb_private *bp;
+	unsigned char *cp;
 	size_t i;
+	int first_set = -1;
 	int ret;
 
 	bp = (struct ext2fs_rb_private *) bitmap->private;
 
 	for (i = 0; i < num; i++) {
-		ret = ext2fs_test_bit(i, in);
-		if (ret)
-			rb_insert_extent(start + i - bitmap->start, 1, bp);
+		if (i & 7 == 0) {
+			unsigned char c = cp[i/8];
+			if (c == 0xFF) {
+				if (first_set == -1)
+					first_set = i;
+				i += 7;
+				continue;
+			}
+			if ((c == 0x00) && (first_set == -1)) {
+				i += 7;
+				continue;
+			}
+		}
+		if (ext2fs_test_bit(i, in)) {
+			if (first_set == -1)
+				first_set = i;
+			continue;
+		}
+		if (first_set == -1)
+			continue;
+
+		rb_insert_extent(start + first_set - bitmap->start,
+				 i - first_set, bp);
+		first_set = -1;
 	}
+	if (first_set != -1)
+		rb_insert_extent(start + first_set - bitmap->start,
+				 num - first_set, bp);
 
 	return 0;
 }