btrfs: some free space cache fixes and updates
cover btrfs: some free space cache fixes and updates
From: Filipe Manana <[email protected]>
Several updates to the free space cache code (most of it to the in memory data structure, shared between the free space cache and the free space tree). A bug fix, some cleanups, minor optimizations and adding several asserts to verify we are holding the necessary lock(s) when udpating the in memory space cache - this was motivated by an attempt to debug an invalid memory access when manipulating the in memory free space cache, as I suspected we had some code path not taking a required lock before manipulating the in memory red black tree of free space entries.
Filipe Manana (9):
btrfs: fix space cache inconsistency after error loading it from disk
btrfs: avoid extra memory allocation when copying free space cache
btrfs: avoid searching twice for previous node when merging free space entries
btrfs: use precomputed end offsets at do_trimming()
btrfs: simplify arguments to tree_insert_offset()
btrfs: assert proper locks are held at tree_insert_offset()
btrfs: assert tree lock is held when searching for free space entries
btrfs: assert tree lock is held when linking free space
btrfs: assert tree lock is held when removing free space entries
fs/btrfs/free-space-cache.c | 111 +++++++++++++++++++++++------------- 1 file changed, 72 insertions(+), 39 deletions(-)
Signature · 1 line
2.35.1
PATCH 2/9 btrfs: avoid extra memory allocation when copying free space cache
From: Filipe Manana <[email protected]>
At copy_free_space_cache(), we add a new entry to the block group's ctl before we free the entry from the temporary ctl. Adding a new entry requires the allocation of a new struct btrfs_free_space, so we can avoid a temporary extra allocation by freeing the entry from the temporary ctl before we add a new entry to the main ctl, which possibly also reduces the chances for a memory allocation failure in case of very high memory pressure. So just do that.
--- fs/btrfs/free-space-cache.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)
fs/btrfs/free-space-cache.c +4 -2
@@ -923,10 +923,12 @@ static int copy_free_space_cache(struct btrfs_block_group *block_group,while (!ret && (n =rb_first (&ctl->free_space_offset)) !=NULL ) { info = rb_entry(n, struct btrfs_free_space, offset_index);if (!info->bitmap) { +const u64 offset = info->offset; +const u64 bytes = info->bytes; +unlink_free_space (ctl, info, true); - ret =btrfs_add_free_space (block_group, info->offset, - info->bytes);kmem_cache_free (btrfs_free_space_cachep, info); + ret =btrfs_add_free_space (block_group, offset, bytes); }else {u64 offset = info->offset;u64 bytes = ctl->unit;
Signature · 1 line
2.35.1
PATCH 1/9 btrfs: fix space cache inconsistency after error loading it from disk
In reply to [email protected]From: Filipe Manana <[email protected]>
When loading a free space cache from disk, at __load_free_space_cache(), if we fail to insert a bitmap entry, we still increment the number of total bitmaps in the btrfs_free_space_ctl structure, which is incorrect since we failed to add the bitmap entry. On error we then empty the cache by calling __btrfs_remove_free_space_cache(), which will result in getting the total bitmaps counter set to 1.
A failure to load a free space cache is not critical, so if a failure happens we just rebuild the cache by scanning the extent tree, which happens at block-group.c:caching_thread(). Yet the failure will result in having the total bitmaps of the btrfs_free_space_ctl always bigger by 1 then the number of bitmap entries we have. So fix this by having the total bitmaps counter be incremented only if we successfully added the bitmap entry.
--- fs/btrfs/free-space-cache.c | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-)
fs/btrfs/free-space-cache.c +4 -3
@@ -870,15 +870,16 @@ static int __load_free_space_cache(struct btrfs_root *root, struct inode *inode, }spin_lock (&ctl->tree_lock); ret =link_free_space (ctl, e); - ctl->total_bitmaps++; -recalculate_thresholds (ctl); -spin_unlock (&ctl->tree_lock);if (ret) { +spin_unlock (&ctl->tree_lock);btrfs_err (fs_info,"Duplicate entries in free space cache, dumping" );kmem_cache_free (btrfs_free_space_cachep, e); goto free_cache; } + ctl->total_bitmaps++; +recalculate_thresholds (ctl); +spin_unlock (&ctl->tree_lock);list_add_tail (&e->list, &bitmaps); }
Signature · 1 line
2.35.1
PATCH 4/9 btrfs: use precomputed end offsets at do_trimming()
In reply to [email protected]From: Filipe Manana <[email protected]>
The are two computations of end offsets at do_trimming() that are not necessary, as they were previously computed and stored in local const variables. So just use the variables instead, to make the source code shorter and easier to read.
--- fs/btrfs/free-space-cache.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
fs/btrfs/free-space-cache.c +1 -1
@@ -3677,7 +3677,7 @@ static int do_trimming(struct btrfs_block_group *block_group,__btrfs_add_free_space (block_group, reserved_start, start - reserved_start, reserved_trim_state); -if (start + bytes < reserved_start + reserved_bytes) +if (end < reserved_end)__btrfs_add_free_space (block_group, end, reserved_end - end, reserved_trim_state);__btrfs_add_free_space (block_group, start, bytes, trim_state);
Signature · 1 line
2.35.1
PATCH 3/9 btrfs: avoid searching twice for previous node when merging free space entries
In reply to [email protected]From: Filipe Manana <[email protected]>
At try_merge_free_space(), avoid calling twice rb_prev() to find the previous node, as that requires looping through the red black tree, so store the result of the rb_prev() call and then use it.
--- fs/btrfs/free-space-cache.c | 10 +++++++--- 1 file changed, 7 insertions(+), 3 deletions(-)
fs/btrfs/free-space-cache.c +7 -3
@@ -2449,6 +2449,7 @@ static bool try_merge_free_space(struct btrfs_free_space_ctl *ctl,u64 offset = info->offset;u64 bytes = info->bytes;const bool is_trimmed =btrfs_free_space_trimmed (info); +struct rb_node *right_prev =NULL ;/* * first we want to see if there is free space adjacent to the range we
@@ -2456,9 +2457,12 @@ static bool try_merge_free_space(struct btrfs_free_space_ctl *ctl,* cover the entire range */ right_info =tree_search_offset (ctl, offset + bytes,0 ,0 ); -if (right_info &&rb_prev (&right_info->offset_index)) - left_info =rb_entry (rb_prev (&right_info->offset_index), - struct btrfs_free_space, offset_index); +if (right_info) + right_prev =rb_prev (&right_info->offset_index); + +if (right_prev) + left_info = rb_entry(right_prev, struct btrfs_free_space, + offset_index);else if (!right_info) left_info =tree_search_offset (ctl, offset -1 ,0 ,0 );
Signature · 1 line
2.35.1
PATCH 6/9 btrfs: assert proper locks are held at tree_insert_offset()
In reply to [email protected]From: Filipe Manana <[email protected]>
There are multiple code paths leading to tree_insert_offset(), and each path takes the necessary locks before tree_insert_offset() is called, since they do other things that require those locks to be held. This makes it easy to miss the locking somewhere, so make tree_insert_offset() assert that the required locks are being held by the calling task.
--- fs/btrfs/free-space-cache.c | 25 +++++++++++++++++++------ 1 file changed, 19 insertions(+), 6 deletions(-)
fs/btrfs/free-space-cache.c +19 -6
@@ -1598,12 +1598,25 @@ static inline u64 offset_to_bitmap(struct btrfs_free_space_ctl *ctl,return bitmap_start; } -static int tree_insert_offset (struct rb_root *root, +static int tree_insert_offset (struct btrfs_free_space_ctl *ctl, +struct btrfs_free_cluster *cluster,struct btrfs_free_space *new_entry) { -struct rb_node **p = &root->rb_node; +struct rb_root *root; +struct rb_node **p;struct rb_node *parent =NULL ; +lockdep_assert_held (&ctl->tree_lock); + +if (cluster) { +lockdep_assert_held (&cluster->lock); + root = &cluster->root; + }else { + root = &ctl->free_space_offset; + } + + p = &root->rb_node; +while (*p) {struct btrfs_free_space *info;
@@ -1836,7 +1849,7 @@ static int link_free_space(struct btrfs_free_space_ctl *ctl,int ret =0 ;ASSERT (info->bytes || info->bitmap); - ret =tree_insert_offset (&ctl->free_space_offset, info); + ret =tree_insert_offset (ctl,NULL , info);if (ret)return ret;
@@ -3014,7 +3027,7 @@ static void __btrfs_return_cluster_to_free_space( entry->bytes; } } -tree_insert_offset (&ctl->free_space_offset, entry); +tree_insert_offset (ctl,NULL , entry);rb_add_cached (&entry->bytes_index, &ctl->free_space_bytes, entry_less); }
@@ -3388,7 +3401,7 @@ static int btrfs_bitmap_cluster(struct btrfs_block_group *block_group,*/ RB_CLEAR_NODE (&entry->bytes_index); - ret =tree_insert_offset (&cluster->root, entry); + ret =tree_insert_offset (ctl, cluster, entry);ASSERT (!ret);/* -EEXIST; Logic error */ trace_btrfs_setup_cluster(block_group, cluster,
@@ -3478,7 +3491,7 @@ setup_cluster_no_bitmap(struct btrfs_block_group *block_group,rb_erase (&entry->offset_index, &ctl->free_space_offset);rb_erase_cached (&entry->bytes_index, &ctl->free_space_bytes); - ret =tree_insert_offset (&cluster->root, entry); + ret =tree_insert_offset (ctl, cluster, entry); total_size += entry->bytes;ASSERT (!ret);/* -EEXIST; Logic error */ }while (node && entry != last);
Signature · 1 line
2.35.1
PATCH 5/9 btrfs: simplify arguments to tree_insert_offset()
In reply to [email protected]From: Filipe Manana <[email protected]>
For the in memory component of space caching (free space cache and free space tree), three of the arguments passed to tree_insert_offset() can always be taken from the new free space entry that we are about to add.
So simplify tree_insert_offset() to take the new entry instead of the 'offset', 'node' and 'bitmap' arguments. This will also allow to make further changes simpler.
--- fs/btrfs/free-space-cache.c | 37 ++++++++++++++++--------------------- 1 file changed, 16 insertions(+), 21 deletions(-)
fs/btrfs/free-space-cache.c +16 -21
@@ -1598,20 +1598,21 @@ static inline u64 offset_to_bitmap(struct btrfs_free_space_ctl *ctl,return bitmap_start; } -static int tree_insert_offset (struct rb_root *root,u64 offset, -struct rb_node *node,int bitmap) +static int tree_insert_offset (struct rb_root *root, +struct btrfs_free_space *new_entry) {struct rb_node **p = &root->rb_node;struct rb_node *parent =NULL ; -struct btrfs_free_space *info;while (*p) { +struct btrfs_free_space *info; + parent = *p; info = rb_entry(parent, struct btrfs_free_space, offset_index); -if (offset < info->offset) { +if (new_entry->offset < info->offset) { p = &(*p)->rb_left; - }else if (offset > info->offset) { + }else if (new_entry->offset > info->offset) { p = &(*p)->rb_right; }else {/*
@@ -1627,7 +1628,7 @@ static int tree_insert_offset(struct rb_root *root, u64 offset,* found a bitmap, we want to go left, or before * logically. */ -if (bitmap) { +if (new_entry->bitmap) {if (info->bitmap) {WARN_ON_ONCE (1 );return -EEXIST ;
@@ -1643,8 +1644,8 @@ static int tree_insert_offset(struct rb_root *root, u64 offset, } } -rb_link_node (node, parent, p); -rb_insert_color (node, root); +rb_link_node (&new_entry->offset_index, parent, p); +rb_insert_color (&new_entry->offset_index, root);return 0 ; }
@@ -1835,8 +1836,7 @@ static int link_free_space(struct btrfs_free_space_ctl *ctl,int ret =0 ;ASSERT (info->bytes || info->bitmap); - ret =tree_insert_offset (&ctl->free_space_offset, info->offset, - &info->offset_index, (info->bitmap !=NULL )); + ret =tree_insert_offset (&ctl->free_space_offset, info);if (ret)return ret;
@@ -2974,8 +2974,6 @@ static void __btrfs_return_cluster_to_free_space(struct btrfs_block_group *block_group, struct btrfs_free_cluster *cluster) { - struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; -struct btrfs_free_space *entry; struct rb_node *node;spin_lock (&cluster->lock);
@@ -2990,15 +2988,15 @@ static void __btrfs_return_cluster_to_free_space( node =rb_first (&cluster->root);while (node) { -bool bitmap; +struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; +struct btrfs_free_space *entry; entry = rb_entry(node, struct btrfs_free_space, offset_index); node =rb_next (&entry->offset_index);rb_erase (&entry->offset_index, &cluster->root);RB_CLEAR_NODE (&entry->offset_index); - bitmap = (entry->bitmap !=NULL ); -if (!bitmap) { +if (!entry->bitmap) {/* Merging treats extents as if they were new */ if (!btrfs_free_space_trimmed (entry)) { ctl->discardable_extents[BTRFS_STAT_CURR ]--;
@@ -3016,8 +3014,7 @@ static void __btrfs_return_cluster_to_free_space( entry->bytes; } } -tree_insert_offset (&ctl->free_space_offset, - entry->offset, &entry->offset_index, bitmap); +tree_insert_offset (&ctl->free_space_offset, entry);rb_add_cached (&entry->bytes_index, &ctl->free_space_bytes, entry_less); }
@@ -3391,8 +3388,7 @@ static int btrfs_bitmap_cluster(struct btrfs_block_group *block_group,*/ RB_CLEAR_NODE (&entry->bytes_index); - ret =tree_insert_offset (&cluster->root, entry->offset, - &entry->offset_index,1 ); + ret =tree_insert_offset (&cluster->root, entry);ASSERT (!ret);/* -EEXIST; Logic error */ trace_btrfs_setup_cluster(block_group, cluster,
@@ -3482,8 +3478,7 @@ setup_cluster_no_bitmap(struct btrfs_block_group *block_group,rb_erase (&entry->offset_index, &ctl->free_space_offset);rb_erase_cached (&entry->bytes_index, &ctl->free_space_bytes); - ret =tree_insert_offset (&cluster->root, entry->offset, - &entry->offset_index,0 ); + ret =tree_insert_offset (&cluster->root, entry); total_size += entry->bytes;ASSERT (!ret);/* -EEXIST; Logic error */ }while (node && entry != last);
Signature · 1 line
2.35.1
PATCH 7/9 btrfs: assert tree lock is held when searching for free space entries
In reply to [email protected]From: Filipe Manana <[email protected]>
When searching for a free space entry by offset, at tree_search_offset(), we are supposed to have the btrfs_free_space_ctl's 'tree_lock' held, so assert that. We have multiple callers of tree_search_offset(), and all currently hold the necessary lock before calling it.
--- fs/btrfs/free-space-cache.c | 2 ++ 1 file changed, 2 insertions(+)
fs/btrfs/free-space-cache.c +2 -0
@@ -1721,6 +1721,8 @@ tree_search_offset(struct btrfs_free_space_ctl *ctl,struct rb_node *n = ctl->free_space_offset.rb_node;struct btrfs_free_space *entry =NULL , *prev =NULL ; +lockdep_assert_held (&ctl->tree_lock); +/* find entry that is closest to the 'offset' */ while (n) { entry = rb_entry(n, struct btrfs_free_space, offset_index);
Signature · 1 line
2.35.1
PATCH 8/9 btrfs: assert tree lock is held when linking free space
In reply to [email protected]From: Filipe Manana <[email protected]>
When linking a free space entry, at link_free_space(), the caller should be holding the spinlock 'tree_lock' of the given btrfs_free_space_ctl argument, which is necessary for manipulating the red black tree of free space entries (done by tree_insert_offset(), which already asserts the lock is held) and for manipulating the 'free_space', 'free_extents', 'discardable_extents' and 'discardable_bytes' counters of the given struct btrfs_free_space_ctl.
So assert that the spinlock 'tree_lock' of the given btrfs_free_space_ctl is held by the current task. We have multiple code paths that end up calling link_free_space(), and all currently take the lock before calling it.
--- fs/btrfs/free-space-cache.c | 2 ++ 1 file changed, 2 insertions(+)
fs/btrfs/free-space-cache.c +2 -0
@@ -1850,6 +1850,8 @@ static int link_free_space(struct btrfs_free_space_ctl *ctl, {int ret =0 ; +lockdep_assert_held (&ctl->tree_lock); +ASSERT (info->bytes || info->bitmap); ret =tree_insert_offset (ctl,NULL , info);if (ret)
Signature · 1 line
2.35.1
PATCH 9/9 btrfs: assert tree lock is held when removing free space entries
In reply to [email protected]From: Filipe Manana <[email protected]>
Removing a free space entry from an in memory space cache requires having the corresponding btrfs_free_space_ctl's 'tree_lock' held. We have several code paths that remove an entry, so add assertions where appropriate to verify we are holding the lock, as the lock is acquired by some other function up in the call chain, which makes it easy to miss in the future.
Note: for this to work we need to lock the local btrfs_free_space_ctl at load_free_space_cache(), which was not being done because it's local, declared on the stack, so no other task has access to it.
--- fs/btrfs/free-space-cache.c | 34 ++++++++++++++++++++++++---------- 1 file changed, 24 insertions(+), 10 deletions(-)
fs/btrfs/free-space-cache.c +24 -10
@@ -927,25 +927,27 @@ static int copy_free_space_cache(struct btrfs_block_group *block_group,const u64 bytes = info->bytes;unlink_free_space (ctl, info, true); +spin_unlock (&ctl->tree_lock);kmem_cache_free (btrfs_free_space_cachep, info); ret =btrfs_add_free_space (block_group, offset, bytes); +spin_lock (&ctl->tree_lock); }else {u64 offset = info->offset;u64 bytes = ctl->unit; -while (search_bitmap (ctl, info, &offset, &bytes, - false) ==0 ) { + ret =search_bitmap (ctl, info, &offset, &bytes, false); +if (ret ==0 ) { +bitmap_clear_bits (ctl, info, offset, bytes, true); +spin_unlock (&ctl->tree_lock); ret =btrfs_add_free_space (block_group, offset, bytes); -if (ret) -break ; -bitmap_clear_bits (ctl, info, offset, bytes, true); - offset = info->offset; - bytes = ctl->unit; +spin_lock (&ctl->tree_lock); + }else { +free_bitmap (ctl, info); + ret =0 ; } -free_bitmap (ctl, info); } -cond_resched (); +cond_resched_lock (&ctl->tree_lock); }return ret; }
@@ -1039,7 +1041,9 @@ int load_free_space_cache(struct btrfs_block_group *block_group) block_group->bytes_super));if (matched) { +spin_lock (&tmp_ctl.tree_lock); ret =copy_free_space_cache (block_group, &tmp_ctl); +spin_unlock (&tmp_ctl.tree_lock);/* * ret == 1 means we successfully loaded the free space cache, * so we need to re-set it here.
@@ -1832,6 +1836,8 @@ static inline void unlink_free_space(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *info, bool update_stat) { +lockdep_assert_held (&ctl->tree_lock); +rb_erase (&info->offset_index, &ctl->free_space_offset);rb_erase_cached (&info->bytes_index, &ctl->free_space_bytes); ctl->free_extents--;
@@ -1881,6 +1887,8 @@ static void relink_bitmap_entry(struct btrfs_free_space_ctl *ctl,if (RB_EMPTY_NODE (&info->bytes_index))return ; +lockdep_assert_held (&ctl->tree_lock); +rb_erase_cached (&info->bytes_index, &ctl->free_space_bytes);rb_add_cached (&info->bytes_index, &ctl->free_space_bytes, entry_less); }
@@ -2991,8 +2999,11 @@ static void __btrfs_return_cluster_to_free_space(struct btrfs_block_group *block_group, struct btrfs_free_cluster *cluster) { + struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;struct rb_node *node; +lockdep_assert_held (&ctl->tree_lock); +spin_lock (&cluster->lock);if (cluster->block_group != block_group) {spin_unlock (&cluster->lock);
@@ -3005,7 +3016,6 @@ static void __btrfs_return_cluster_to_free_space( node =rb_first (&cluster->root);while (node) { -struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;struct btrfs_free_space *entry; entry = rb_entry(node, struct btrfs_free_space, offset_index);
@@ -3344,6 +3354,8 @@ static int btrfs_bitmap_cluster(struct btrfs_block_group *block_group,unsigned long total_found =0 ;int ret; +lockdep_assert_held (&ctl->tree_lock); + i =offset_to_bit (entry->offset, ctl->unit,max_t (u64, offset, entry->offset)); want_bits =bytes_to_bits (bytes, ctl->unit);
@@ -3433,6 +3445,8 @@ setup_cluster_no_bitmap(struct btrfs_block_group *block_group,u64 max_extent;u64 total_size =0 ; +lockdep_assert_held (&ctl->tree_lock); + entry =tree_search_offset (ctl, offset,0 ,1 );if (!entry)return -ENOSPC ;
Signature · 1 line
2.35.1
Re: [PATCH 1/9] btrfs: fix space cache inconsistency after error loading it from disk
In reply to [email protected]LGTM
Re: [PATCH 2/9] btrfs: avoid extra memory allocation when copying free space cache
In reply to [email protected]LGTM
Re: [PATCH 4/9] btrfs: use precomputed end offsets at do_trimming()
In reply to [email protected]LGTM
Re: [PATCH 7/9] btrfs: assert tree lock is held when searching for free space entries
In reply to [email protected]LGTM.
Re: [PATCH 8/9] btrfs: assert tree lock is held when linking free space
In reply to [email protected]LGTM.
Quoted 11 lines · On Thu, May 04, 2023 at 12:04:17PM +0100, [email protected] wrote:
From: Filipe Manana <[email protected]>
Several updates to the free space cache code (most of it to the in memory data structure, shared between the free space cache and the free space tree). A bug fix, some cleanups, minor optimizations and adding several asserts to verify we are holding the necessary lock(s) when udpating the in memory space cache - this was motivated by an attempt to debug an invalid memory access when manipulating the in memory free space cache, as I suspected we had some code path not taking a required lock before manipulating the in memory red black tree of free space entries.
Quoted 2 lines
Filipe Manana (9):
btrfs: fix space cache inconsistency after error loading it from disk
Oh, that was an old bug.
Quoted 8 lines
btrfs: avoid extra memory allocation when copying free space cache
btrfs: avoid searching twice for previous node when merging free space entries
btrfs: use precomputed end offsets atdo_trimming()
btrfs: simplify arguments totree_insert_offset()
btrfs: assert proper locks are held attree_insert_offset()
btrfs: assert tree lock is held when searching for free space entries
btrfs: assert tree lock is held when linking free space
btrfs: assert tree lock is held when removing free space entries
Added to misc-next, thanks.