From a565971ff3e0f584ec163a32abf95196be623041 Mon Sep 17 00:00:00 2001 From: Howard McLauchlan Date: Wed, 18 Apr 2018 18:02:36 -0700 Subject: btrfs: optimize free space tree bitmap conversion Presently, convert_free_space_to_extents() does a linear scan of the bitmap. We can speed this up with find_next_{bit,zero_bit}_le(). This patch replaces the linear scan with find_next_{bit,zero_bit}_le(). Testing shows a 20-33% decrease in execution time for convert_free_space_to_extents(). Since we change bitmap to be unsigned long, we have to do some casting for the bitmap cursor. In le_bitmap_set() it makes sense to use u8, as we are doing bit operations. Everywhere else, we're just using it for pointer arithmetic and not directly accessing it, so char seems more appropriate. Suggested-by: Omar Sandoval Signed-off-by: Howard McLauchlan Reviewed-by: David Sterba Signed-off-by: David Sterba --- fs/btrfs/free-space-tree.c | 61 +++++++++++++++++----------------------------- 1 file changed, 23 insertions(+), 38 deletions(-) diff --git a/fs/btrfs/free-space-tree.c b/fs/btrfs/free-space-tree.c index e03830d83311..7019afe6e727 100644 --- a/fs/btrfs/free-space-tree.c +++ b/fs/btrfs/free-space-tree.c @@ -138,10 +138,11 @@ static inline u32 free_space_bitmap_size(u64 size, u32 sectorsize) return DIV_ROUND_UP((u32)div_u64(size, sectorsize), BITS_PER_BYTE); } -static u8 *alloc_bitmap(u32 bitmap_size) +static unsigned long *alloc_bitmap(u32 bitmap_size) { - u8 *ret; + unsigned long *ret; unsigned int nofs_flag; + u32 bitmap_rounded_size = round_up(bitmap_size, sizeof(unsigned long)); /* * GFP_NOFS doesn't work with kvmalloc(), but we really can't recurse @@ -152,14 +153,14 @@ static u8 *alloc_bitmap(u32 bitmap_size) * know that recursion is unsafe. */ nofs_flag = memalloc_nofs_save(); - ret = kvzalloc(bitmap_size, GFP_KERNEL); + ret = kvzalloc(bitmap_rounded_size, GFP_KERNEL); memalloc_nofs_restore(nofs_flag); return ret; } -static void le_bitmap_set(u8 *map, unsigned int start, int len) +static void le_bitmap_set(unsigned long *map, unsigned int start, int len) { - u8 *p = map + BIT_BYTE(start); + u8 *p = ((u8 *)map) + BIT_BYTE(start); const unsigned int size = start + len; int bits_to_set = BITS_PER_BYTE - (start % BITS_PER_BYTE); u8 mask_to_set = BITMAP_FIRST_BYTE_MASK(start); @@ -186,7 +187,8 @@ int convert_free_space_to_bitmaps(struct btrfs_trans_handle *trans, struct btrfs_free_space_info *info; struct btrfs_key key, found_key; struct extent_buffer *leaf; - u8 *bitmap, *bitmap_cursor; + unsigned long *bitmap; + char *bitmap_cursor; u64 start, end; u64 bitmap_range, i; u32 bitmap_size, flags, expected_extent_count; @@ -275,7 +277,7 @@ int convert_free_space_to_bitmaps(struct btrfs_trans_handle *trans, goto out; } - bitmap_cursor = bitmap; + bitmap_cursor = (char *)bitmap; bitmap_range = fs_info->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS; i = start; while (i < end) { @@ -324,13 +326,10 @@ int convert_free_space_to_extents(struct btrfs_trans_handle *trans, struct btrfs_free_space_info *info; struct btrfs_key key, found_key; struct extent_buffer *leaf; - u8 *bitmap; + unsigned long *bitmap; u64 start, end; - /* Initialize to silence GCC. */ - u64 extent_start = 0; - u64 offset; u32 bitmap_size, flags, expected_extent_count; - int prev_bit = 0, bit, bitnr; + unsigned long nrbits, start_bit, end_bit; u32 extent_count = 0; int done = 0, nr; int ret; @@ -368,7 +367,7 @@ int convert_free_space_to_extents(struct btrfs_trans_handle *trans, break; } else if (found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) { unsigned long ptr; - u8 *bitmap_cursor; + char *bitmap_cursor; u32 bitmap_pos, data_size; ASSERT(found_key.objectid >= start); @@ -378,7 +377,7 @@ int convert_free_space_to_extents(struct btrfs_trans_handle *trans, bitmap_pos = div_u64(found_key.objectid - start, fs_info->sectorsize * BITS_PER_BYTE); - bitmap_cursor = bitmap + bitmap_pos; + bitmap_cursor = ((char *)bitmap) + bitmap_pos; data_size = free_space_bitmap_size(found_key.offset, fs_info->sectorsize); @@ -412,32 +411,16 @@ int convert_free_space_to_extents(struct btrfs_trans_handle *trans, btrfs_mark_buffer_dirty(leaf); btrfs_release_path(path); - offset = start; - bitnr = 0; - while (offset < end) { - bit = !!le_test_bit(bitnr, bitmap); - if (prev_bit == 0 && bit == 1) { - extent_start = offset; - } else if (prev_bit == 1 && bit == 0) { - key.objectid = extent_start; - key.type = BTRFS_FREE_SPACE_EXTENT_KEY; - key.offset = offset - extent_start; - - ret = btrfs_insert_empty_item(trans, root, path, &key, 0); - if (ret) - goto out; - btrfs_release_path(path); + nrbits = div_u64(block_group->key.offset, block_group->fs_info->sectorsize); + start_bit = find_next_bit_le(bitmap, nrbits, 0); - extent_count++; - } - prev_bit = bit; - offset += fs_info->sectorsize; - bitnr++; - } - if (prev_bit == 1) { - key.objectid = extent_start; + while (start_bit < nrbits) { + end_bit = find_next_zero_bit_le(bitmap, nrbits, start_bit); + ASSERT(start_bit < end_bit); + + key.objectid = start + start_bit * block_group->fs_info->sectorsize; key.type = BTRFS_FREE_SPACE_EXTENT_KEY; - key.offset = end - extent_start; + key.offset = (end_bit - start_bit) * block_group->fs_info->sectorsize; ret = btrfs_insert_empty_item(trans, root, path, &key, 0); if (ret) @@ -445,6 +428,8 @@ int convert_free_space_to_extents(struct btrfs_trans_handle *trans, btrfs_release_path(path); extent_count++; + + start_bit = find_next_bit_le(bitmap, nrbits, end_bit); } if (extent_count != expected_extent_count) { -- cgit v1.2.3-55-g7522