Btrfs: fix to search one more bitmap for cluster setup
PATCH 1/2 Btrfs: fix to search one more bitmap for cluster setup
Suppose there are two bitmaps [0, 256], [256, 512] and one extent [100, 120] in the free space cache, and we want to setup a cluster with offset=50, bytes=50.
In this case, there will be only one bitmap [256, 512] in the temporary bitmaps list, and then setup_cluster_bitmap() won't search bitmap [0, 256].
The cause is, the list is constructed in setup_cluster_no_bitmap(), and only bitmaps with bitmap_entry->offset >= offset will be added into the list, and the very bitmap that convers offset has bitmap_entry->offset <= offset.
This is currently fine, since the caller always set offset=0 when calling btrfs_find_space_cluster(), but it may change in the future, for example to improve for SSD_SPREAD.
--- fs/btrfs/free-space-cache.c | 12 ++++++++++++ 1 files changed, 12 insertions(+), 0 deletions(-)
fs/btrfs/free-space-cache.c +12 -0
@@ -2453,11 +2453,23 @@ setup_cluster_bitmap(struct btrfs_block_group_cache *block_group,struct btrfs_free_space *entry;struct rb_node *node;int ret = -ENOSPC ; +u64 bitmap_offset =offset_to_bitmap (ctl, offset);if (ctl->total_bitmaps ==0 )return -ENOSPC ;/* +* The bitmap that covers offset won't be in the list unless offset +* is just its start offset. +*/ + entry = list_first_entry(bitmaps, struct btrfs_free_space, list); +if (entry->offset != bitmap_offset) { + entry =tree_search_offset (ctl, bitmap_offset,1 ,0 ); +if (list_empty (&entry->list)) +list_add (&entry->list, bitmaps); + } + +/* * First check our cached list of bitmaps and see if there is an entry * here that will work. */
-- 1.7.3.1
PATCH 2/2 Btrfs: avoid unnecessary bitmap search for cluster setup
setup_cluster_no_bitmap() searches all the extents and bitmaps starting from offset. Therefore if it returns -ENOSPC, all the bitmaps starting from offset are in the bitmaps list, so it's sufficient to search from this list in setup_cluser_bitmap().
--- fs/btrfs/free-space-cache.c | 42 ++++-------------------------------------- 1 files changed, 4 insertions(+), 38 deletions(-)
fs/btrfs/free-space-cache.c +4 -38
@@ -2451,7 +2451,6 @@ setup_cluster_bitmap(struct btrfs_block_group_cache *block_group, {struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;struct btrfs_free_space *entry; -struct rb_node *node;int ret = -ENOSPC ;u64 bitmap_offset =offset_to_bitmap (ctl, offset);
@@ -2469,10 +2468,6 @@ setup_cluster_bitmap(struct btrfs_block_group_cache *block_group,list_add (&entry->list, bitmaps); } -/* -* First check our cached list of bitmaps and see if there is an entry -* here that will work. -*/ list_for_each_entry (entry, bitmaps, list) {if (entry->bytes < min_bytes)continue ;
@@ -2483,38 +2478,10 @@ setup_cluster_bitmap(struct btrfs_block_group_cache *block_group, }/* -* If we do have entries on our list and we are here then we didn't find -* anything, so go ahead and get the next entry after the last entry in -* this list and start the search from there. +* The bitmaps list has all the bitmaps that record free space +* starting after offset, so no more search is required. */ -if (!list_empty (bitmaps)) { - entry = list_entry(bitmaps->prev, struct btrfs_free_space, - list); - node =rb_next (&entry->offset_index); -if (!node) -return -ENOSPC ; - entry = rb_entry(node, struct btrfs_free_space, offset_index); - goto search; - } - - entry =tree_search_offset (ctl,offset_to_bitmap (ctl, offset),0 ,1 ); -if (!entry) -return -ENOSPC ; - -search: - node = &entry->offset_index; -do { - entry = rb_entry(node, struct btrfs_free_space, offset_index); - node =rb_next (&entry->offset_index); -if (!entry->bitmap) -continue ; -if (entry->bytes < min_bytes) -continue ; - ret =btrfs_bitmap_cluster (block_group, entry, cluster, offset, - bytes, min_bytes); - }while (ret && node); - -return ret; +return -ENOSPC ; }/*
@@ -2532,8 +2499,8 @@ int btrfs_find_space_cluster(struct btrfs_trans_handle *trans, u64 offset, u64 bytes, u64 empty_size) { struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; -struct list_head bitmaps;struct btrfs_free_space *entry, *tmp; +LIST_HEAD (bitmaps);u64 min_bytes;int ret;
@@ -2572,7 +2539,6 @@ int btrfs_find_space_cluster(struct btrfs_trans_handle *trans, goto out; } -INIT_LIST_HEAD (&bitmaps); ret =setup_cluster_no_bitmap (block_group, cluster, &bitmaps, offset, bytes, min_bytes);if (ret)
-- 1.7.3.1
PATCH v2 1/2 Btrfs: fix to search one more bitmap for cluster setup
In reply to Li ZefanSuppose there are two bitmaps [0, 256], [256, 512] and one extent [100, 120] in the free space cache, and we want to setup a cluster with offset=100, bytes=50.
In this case, there will be only one bitmap [256, 512] in the temporary bitmaps list, and then setup_cluster_bitmap() won't search bitmap [0, 256].
The cause is, the list is constructed in setup_cluster_no_bitmap(), and only bitmaps with bitmap_entry->offset >= offset will be added into the list, and the very bitmap that convers offset has bitmap_entry->offset <= offset.
---
v2: fix a NULL pointer deref.
--- fs/btrfs/free-space-cache.c | 12 ++++++++++++ 1 files changed, 12 insertions(+), 0 deletions(-)
fs/btrfs/free-space-cache.c +12 -0
@@ -2453,11 +2453,23 @@ setup_cluster_bitmap(struct btrfs_block_group_cache *block_group,struct btrfs_free_space *entry;struct rb_node *node;int ret = -ENOSPC ; +u64 bitmap_offset =offset_to_bitmap (ctl, offset);if (ctl->total_bitmaps ==0 )return -ENOSPC ;/* +* The bitmap that covers offset won't be in the list unless offset +* is just its start offset. +*/ + entry = list_first_entry(bitmaps, struct btrfs_free_space, list); +if (entry->offset != bitmap_offset) { + entry =tree_search_offset (ctl, bitmap_offset,1 ,0 ); +if (entry &&list_empty (&entry->list)) +list_add (&entry->list, bitmaps); + } + +/* * First check our cached list of bitmaps and see if there is an entry * here that will work. */
Signature · 1 line
1.7.3.1