| Message ID | 1353803794-11593-2-git-send-email-tytso@mit.edu |
|---|---|
| State | Superseded, archived |
| Headers | show |
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
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
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; }
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(-)