btrfs: convert delayed head refs to xarray and cleanups
cover btrfs: convert delayed head refs to xarray and cleanups
From: Filipe Manana <[email protected]>
This converts the rb-tree that tracks delayed ref heads into an xarray, reducing memory used by delayed ref heads and making it more efficient to add/remove/find delayed ref heads. The rest are mostly cleanups and refactorings, removing some dead code, deduplicating code, move code around, etc. More details in the changelogs.
Filipe Manana (18):
btrfs: remove BUG_ON() at btrfs_destroy_delayed_refs()
btrfs: move btrfs_destroy_delayed_refs() to delayed-ref.c
btrfs: remove fs_info parameter from btrfs_destroy_delayed_refs()
btrfs: remove fs_info parameter from btrfs_cleanup_one_transaction()
btrfs: remove duplicated code to drop delayed ref during transaction abort
btrfs: use helper to find first ref head at btrfs_destroy_delayed_refs()
btrfs: remove num_entries atomic counter from delayed ref root
btrfs: change return type of btrfs_delayed_ref_lock() to boolean
btrfs: simplify obtaining a delayed ref head
btrfs: move delayed ref head unselection to delayed-ref.c
btrfs: pass fs_info to functions that search for delayed ref heads
btrfs: pass fs_info to btrfs_cleanup_ref_head_accounting
btrfs: assert delayed refs lock is held at find_ref_head()
btrfs: assert delayed refs lock is held at find_first_ref_head()
btrfs: assert delayed refs lock is held at add_delayed_ref_head()
btrfs: add comments regarding locking to struct btrfs_delayed_ref_root
btrfs: track delayed ref heads in an xarray
btrfs: remove no longer used delayed ref head search functionality
fs/btrfs/backref.c | 3 +- fs/btrfs/delayed-ref.c | 319 +++++++++++++++++++++++++---------------- fs/btrfs/delayed-ref.h | 61 +++++--- fs/btrfs/disk-io.c | 79 +--------- fs/btrfs/disk-io.h | 3 +- fs/btrfs/extent-tree.c | 69 ++------- fs/btrfs/transaction.c | 8 +- 7 files changed, 256 insertions(+), 286 deletions(-)
Signature · 1 line
2.43.0
PATCH 1/18 btrfs: remove BUG_ON() at btrfs_destroy_delayed_refs()
From: Filipe Manana <[email protected]>
At btrfs_destroy_delayed_refs() it's unexpected to not find the block group to which a delayed reference's extent belongs to, so we have this BUG_ON(), not just because it's highly unexpected but also because we don't know what to do there.
Since we are in the transaction abort path, there's nothing we can do other than proceed and cleanup all used resources we can. So remove the BUG_ON() and deal with a missing block group by logging an error message and continuing to cleanup all we can related to the current delayed ref head and moving to other delayed refs.
--- fs/btrfs/disk-io.c | 37 ++++++++++++++++++++++++------------- 1 file changed, 24 insertions(+), 13 deletions(-)
fs/btrfs/disk-io.c +24 -13
@@ -4571,19 +4571,30 @@ static void btrfs_destroy_delayed_refs(struct btrfs_transaction *trans,struct btrfs_block_group *cache; cache =btrfs_lookup_block_group (fs_info, head->bytenr); -BUG_ON (!cache); - -spin_lock (&cache->space_info->lock); -spin_lock (&cache->lock); - cache->pinned += head->num_bytes; -btrfs_space_info_update_bytes_pinned (fs_info, - cache->space_info, head->num_bytes); - cache->reserved -= head->num_bytes; - cache->space_info->bytes_reserved -= head->num_bytes; -spin_unlock (&cache->lock); -spin_unlock (&cache->space_info->lock); - -btrfs_put_block_group (cache); +if (WARN_ON_ONCE (cache ==NULL )) { +/* +* Unexpected and there's nothing we can do here +* because we are in a transaction abort path, +* so any errors can only be ignored or reported +* while attempting to cleanup all resources. +*/ +btrfs_err (fs_info, +"block group for delayed ref at %llu was not found while destroying ref head" , + head->bytenr); + }else { +spin_lock (&cache->space_info->lock); +spin_lock (&cache->lock); + cache->pinned += head->num_bytes; +btrfs_space_info_update_bytes_pinned (fs_info, + cache->space_info, + head->num_bytes); + cache->reserved -= head->num_bytes; + cache->space_info->bytes_reserved -= head->num_bytes; +spin_unlock (&cache->lock); +spin_unlock (&cache->space_info->lock); + +btrfs_put_block_group (cache); + }btrfs_error_unpin_extent_range (fs_info, head->bytenr, head->bytenr + head->num_bytes -1 );
Signature · 1 line
2.43.0
PATCH 2/18 btrfs: move btrfs_destroy_delayed_refs() to delayed-ref.c
In reply to [email protected]From: Filipe Manana <[email protected]>
It's better suited at delayed-ref.c since it's about delayed refs and contains logic to iterate over them (using the red black tree, doing all the locking, freeing, etc), so move it from disk-io.c, which is pretty big, into delayed-ref.c, hidding implementation details of how delayed refs are tracked and managed. This also facilitates the next patches in the series.
This change moves the code between files but also does the following simple cleanups:
1) Rename the 'cache' variable to 'bg', since it's a block group (the 'cache' logic comes from old days where the block group structure was named 'btrfs_block_group_cache');
2) Move the 'ref' variable declaration to the scope of the inner while loop, since it's not used outside that loop.
--- fs/btrfs/delayed-ref.c | 81 ++++++++++++++++++++++++++++++++++++++++++ fs/btrfs/delayed-ref.h | 2 ++ fs/btrfs/disk-io.c | 80 ----------------------------------------- 3 files changed, 83 insertions(+), 80 deletions(-)
fs/btrfs/delayed-ref.c +81 -0
@@ -9,6 +9,7 @@#include "messages.h" #include "ctree.h" #include "delayed-ref.h" +#include "extent-tree.h" #include "transaction.h" #include "qgroup.h" #include "space-info.h"
@@ -1238,6 +1239,86 @@ bool btrfs_find_delayed_tree_ref(struct btrfs_delayed_ref_head *head,return found; } +void btrfs_destroy_delayed_refs (struct btrfs_transaction *trans, +struct btrfs_fs_info *fs_info) +{ +struct rb_node *node; +struct btrfs_delayed_ref_root *delayed_refs = &trans->delayed_refs; + +spin_lock (&delayed_refs->lock); +while ((node =rb_first_cached (&delayed_refs->href_root)) !=NULL ) { +struct btrfs_delayed_ref_head *head; +struct rb_node *n; +bool pin_bytes = false; + + head = rb_entry(node, struct btrfs_delayed_ref_head, + href_node); +if (btrfs_delayed_ref_lock (delayed_refs, head)) +continue ; + +spin_lock (&head->lock); +while ((n =rb_first_cached (&head->ref_tree)) !=NULL ) { +struct btrfs_delayed_ref_node *ref; + + ref = rb_entry(n, struct btrfs_delayed_ref_node, ref_node); +rb_erase_cached (&ref->ref_node, &head->ref_tree); +RB_CLEAR_NODE (&ref->ref_node); +if (!list_empty (&ref->add_list)) +list_del (&ref->add_list); +atomic_dec (&delayed_refs->num_entries); +btrfs_put_delayed_ref (ref); +btrfs_delayed_refs_rsv_release (fs_info,1 ,0 ); + } +if (head->must_insert_reserved) + pin_bytes = true; +btrfs_free_delayed_extent_op (head->extent_op); +btrfs_delete_ref_head (delayed_refs, head); +spin_unlock (&head->lock); +spin_unlock (&delayed_refs->lock); +mutex_unlock (&head->mutex); + +if (pin_bytes) { +struct btrfs_block_group *bg; + + bg =btrfs_lookup_block_group (fs_info, head->bytenr); +if (WARN_ON_ONCE (bg ==NULL )) { +/* +* Unexpected and there's nothing we can do here +* because we are in a transaction abort path, +* so any errors can only be ignored or reported +* while attempting to cleanup all resources. +*/ +btrfs_err (fs_info, +"block group for delayed ref at %llu was not found while destroying ref head" , + head->bytenr); + }else { +spin_lock (&bg->space_info->lock); +spin_lock (&bg->lock); + bg->pinned += head->num_bytes; +btrfs_space_info_update_bytes_pinned (fs_info, + bg->space_info, + head->num_bytes); + bg->reserved -= head->num_bytes; + bg->space_info->bytes_reserved -= head->num_bytes; +spin_unlock (&bg->lock); +spin_unlock (&bg->space_info->lock); + +btrfs_put_block_group (bg); + } + +btrfs_error_unpin_extent_range (fs_info, head->bytenr, + head->bytenr + head->num_bytes -1 ); + } +btrfs_cleanup_ref_head_accounting (fs_info, delayed_refs, head); +btrfs_put_delayed_ref_head (head); +cond_resched (); +spin_lock (&delayed_refs->lock); + } +btrfs_qgroup_destroy_extent_records (trans); + +spin_unlock (&delayed_refs->lock); +} +void __cold btrfs_delayed_ref_exit (void ) {kmem_cache_destroy (btrfs_delayed_ref_head_cachep);
fs/btrfs/delayed-ref.h +2 -0
@@ -399,6 +399,8 @@ int btrfs_delayed_refs_rsv_refill(struct btrfs_fs_info *fs_info,bool btrfs_check_space_for_delayed_refs (struct btrfs_fs_info *fs_info);bool btrfs_find_delayed_tree_ref (struct btrfs_delayed_ref_head *head,u64 root,u64 parent); +void btrfs_destroy_delayed_refs (struct btrfs_transaction *trans, +struct btrfs_fs_info *fs_info);static inline u64 btrfs_delayed_ref_owner (struct btrfs_delayed_ref_node *node) {
fs/btrfs/disk-io.c +0 -80
86 lines not on this page · raw message
Signature · 1 line
2.43.0
PATCH 3/18 btrfs: remove fs_info parameter from btrfs_destroy_delayed_refs()
In reply to [email protected]From: Filipe Manana <[email protected]>
The fs_info parameter is redundant because it can be extracted from the transaction given as another parameter. So remove it and use the fs_info accessible from the transaction.
--- fs/btrfs/delayed-ref.c | 4 ++-- fs/btrfs/delayed-ref.h | 3 +-- fs/btrfs/disk-io.c | 2 +- 3 files changed, 4 insertions(+), 5 deletions(-)
fs/btrfs/delayed-ref.c +2 -2
@@ -1239,11 +1239,11 @@ bool btrfs_find_delayed_tree_ref(struct btrfs_delayed_ref_head *head,return found; } -void btrfs_destroy_delayed_refs (struct btrfs_transaction *trans, -struct btrfs_fs_info *fs_info) +void btrfs_destroy_delayed_refs (struct btrfs_transaction *trans) {struct rb_node *node;struct btrfs_delayed_ref_root *delayed_refs = &trans->delayed_refs; +struct btrfs_fs_info *fs_info = trans->fs_info;spin_lock (&delayed_refs->lock);while ((node =rb_first_cached (&delayed_refs->href_root)) !=NULL ) {
fs/btrfs/delayed-ref.h +1 -2
@@ -399,8 +399,7 @@ int btrfs_delayed_refs_rsv_refill(struct btrfs_fs_info *fs_info,bool btrfs_check_space_for_delayed_refs (struct btrfs_fs_info *fs_info);bool btrfs_find_delayed_tree_ref (struct btrfs_delayed_ref_head *head,u64 root,u64 parent); -void btrfs_destroy_delayed_refs (struct btrfs_transaction *trans, -struct btrfs_fs_info *fs_info); +void btrfs_destroy_delayed_refs (struct btrfs_transaction *trans);static inline u64 btrfs_delayed_ref_owner (struct btrfs_delayed_ref_node *node) {
fs/btrfs/disk-io.c +1 -1
@@ -4748,7 +4748,7 @@ void btrfs_cleanup_one_transaction(struct btrfs_transaction *cur_trans,list_del_init (&dev->post_commit_list); } -btrfs_destroy_delayed_refs (cur_trans, fs_info); +btrfs_destroy_delayed_refs (cur_trans); cur_trans->state =TRANS_STATE_COMMIT_START ;wake_up (&fs_info->transaction_blocked_wait);
Signature · 1 line
2.43.0
PATCH 4/18 btrfs: remove fs_info parameter from btrfs_cleanup_one_transaction()
In reply to [email protected]From: Filipe Manana <[email protected]>
The fs_info parameter is redundant because it can be extracted from the transaction given as another parameter. So remove it and use the fs_info accessible from the transaction.
--- fs/btrfs/disk-io.c | 8 ++++---- fs/btrfs/disk-io.h | 3 +-- fs/btrfs/transaction.c | 2 +- 3 files changed, 6 insertions(+), 7 deletions(-)
fs/btrfs/disk-io.c +4 -4
@@ -4183,7 +4183,7 @@ static void warn_about_uncommitted_trans(struct btrfs_fs_info *fs_info)btrfs_warn (fs_info,"transaction %llu (with %llu dirty metadata bytes) is not committed" , trans->transid, dirty_bytes); -btrfs_cleanup_one_transaction (trans, fs_info); +btrfs_cleanup_one_transaction (trans);if (trans == fs_info->running_transaction) fs_info->running_transaction =NULL ;
@@ -4734,9 +4734,9 @@ static void btrfs_free_all_qgroup_pertrans(struct btrfs_fs_info *fs_info)spin_unlock (&fs_info->fs_roots_radix_lock); } -void btrfs_cleanup_one_transaction (struct btrfs_transaction *cur_trans, -struct btrfs_fs_info *fs_info) +void btrfs_cleanup_one_transaction (struct btrfs_transaction *cur_trans) { +struct btrfs_fs_info *fs_info = cur_trans->fs_info;struct btrfs_device *dev, *tmp;btrfs_cleanup_dirty_bgs (cur_trans, fs_info);
@@ -4794,7 +4794,7 @@ static int btrfs_cleanup_transaction(struct btrfs_fs_info *fs_info) }else {spin_unlock (&fs_info->trans_lock); } -btrfs_cleanup_one_transaction (t, fs_info); +btrfs_cleanup_one_transaction (t);spin_lock (&fs_info->trans_lock);if (t == fs_info->running_transaction)
fs/btrfs/disk-io.h +1 -2
@@ -126,8 +126,7 @@ int btrfs_add_log_tree(struct btrfs_trans_handle *trans, struct btrfs_root *root);void btrfs_cleanup_dirty_bgs (struct btrfs_transaction *trans,struct btrfs_fs_info *fs_info); -void btrfs_cleanup_one_transaction (struct btrfs_transaction *trans, -struct btrfs_fs_info *fs_info); +void btrfs_cleanup_one_transaction (struct btrfs_transaction *trans);struct btrfs_root *btrfs_create_tree (struct btrfs_trans_handle *trans,u64 objectid);int btrfs_get_num_tolerated_disk_barrier_failures (u64 flags);
fs/btrfs/transaction.c +1 -1
@@ -2052,7 +2052,7 @@ static void cleanup_transaction(struct btrfs_trans_handle *trans, int err)spin_unlock (&fs_info->trans_lock); -btrfs_cleanup_one_transaction (trans->transaction, fs_info); +btrfs_cleanup_one_transaction (trans->transaction);spin_lock (&fs_info->trans_lock);if (cur_trans == fs_info->running_transaction)
Signature · 1 line
2.43.0
PATCH 5/18 btrfs: remove duplicated code to drop delayed ref during transaction abort
In reply to [email protected]From: Filipe Manana <[email protected]>
When destroying delayed refs during a transaction abort, we have open coded the removal of a delayed ref, which is also done by the static helper function drop_delayed_ref(). So remove that duplicated code and use drop_delayed_ref() instead.
--- fs/btrfs/delayed-ref.c | 8 +------- 1 file changed, 1 insertion(+), 7 deletions(-)
fs/btrfs/delayed-ref.c +1 -7
@@ -1261,13 +1261,7 @@ void btrfs_destroy_delayed_refs(struct btrfs_transaction *trans)struct btrfs_delayed_ref_node *ref; ref = rb_entry(n, struct btrfs_delayed_ref_node, ref_node); -rb_erase_cached (&ref->ref_node, &head->ref_tree); -RB_CLEAR_NODE (&ref->ref_node); -if (!list_empty (&ref->add_list)) -list_del (&ref->add_list); -atomic_dec (&delayed_refs->num_entries); -btrfs_put_delayed_ref (ref); -btrfs_delayed_refs_rsv_release (fs_info,1 ,0 ); +drop_delayed_ref (fs_info, delayed_refs, head, ref); }if (head->must_insert_reserved) pin_bytes = true;
Signature · 1 line
2.43.0
PATCH 6/18 btrfs: use helper to find first ref head at btrfs_destroy_delayed_refs()
In reply to [email protected]From: Filipe Manana <[email protected]>
Instead of open coding it, use the find_first_ref_head() helper at btrfs_destroy_delayed_refs(). This avoids duplicating the logic, specially with the upcoming changes in subsequent patches.
--- fs/btrfs/delayed-ref.c | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-)
fs/btrfs/delayed-ref.c +5 -4
@@ -1241,18 +1241,19 @@ bool btrfs_find_delayed_tree_ref(struct btrfs_delayed_ref_head *head,void btrfs_destroy_delayed_refs (struct btrfs_transaction *trans) { -struct rb_node *node;struct btrfs_delayed_ref_root *delayed_refs = &trans->delayed_refs;struct btrfs_fs_info *fs_info = trans->fs_info;spin_lock (&delayed_refs->lock); -while ((node =rb_first_cached (&delayed_refs->href_root)) !=NULL ) { +while (true) {struct btrfs_delayed_ref_head *head;struct rb_node *n;bool pin_bytes = false; - head = rb_entry(node, struct btrfs_delayed_ref_head, - href_node); + head =find_first_ref_head (delayed_refs); +if (!head) +break ; +if (btrfs_delayed_ref_lock (delayed_refs, head))continue ;
Signature · 1 line
2.43.0
PATCH 7/18 btrfs: remove num_entries atomic counter from delayed ref root
In reply to [email protected]From: Filipe Manana <[email protected]>
The atomic counter 'num_entries' is not used anymore, we increment it and decrement it but then we don't ever read it to use for any logic. Its last use was removed with commit 61a56a992fcf ("btrfs: delayed refs pre-flushing should only run the heads we have"). So remove it.
--- fs/btrfs/delayed-ref.c | 4 ---- fs/btrfs/delayed-ref.h | 5 ----- fs/btrfs/extent-tree.c | 1 - fs/btrfs/transaction.c | 1 - 4 files changed, 11 deletions(-)
fs/btrfs/delayed-ref.c +0 -4
@@ -463,7 +463,6 @@ static inline void drop_delayed_ref(struct btrfs_fs_info *fs_info,if (!list_empty (&ref->add_list))list_del (&ref->add_list);btrfs_put_delayed_ref (ref); -atomic_dec (&delayed_refs->num_entries);btrfs_delayed_refs_rsv_release (fs_info,1 ,0 ); }
@@ -604,7 +603,6 @@ void btrfs_delete_ref_head(struct btrfs_delayed_ref_root *delayed_refs,rb_erase_cached (&head->href_node, &delayed_refs->href_root);RB_CLEAR_NODE (&head->href_node); -atomic_dec (&delayed_refs->num_entries); delayed_refs->num_heads--;if (!head->processing) delayed_refs->num_heads_ready--;
@@ -630,7 +628,6 @@ static bool insert_delayed_ref(struct btrfs_trans_handle *trans,if (!exist) {if (ref->action ==BTRFS_ADD_DELAYED_REF )list_add_tail (&ref->add_list, &href->ref_add_list); -atomic_inc (&root->num_entries);spin_unlock (&href->lock); trans->delayed_ref_updates++;return false;
@@ -901,7 +898,6 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans, } delayed_refs->num_heads++; delayed_refs->num_heads_ready++; -atomic_inc (&delayed_refs->num_entries); }if (qrecord_inserted_ret) *qrecord_inserted_ret = qrecord_inserted;
fs/btrfs/delayed-ref.h +0 -5
@@ -216,11 +216,6 @@ struct btrfs_delayed_ref_root {/* this spin lock protects the rbtree and the entries inside */ spinlock_t lock; -/* how many delayed ref updates we've queued, used by the -* throttling code -*/ -atomic_t num_entries; -/* total number of head nodes in tree */ unsigned long num_heads;
fs/btrfs/extent-tree.c +0 -1
@@ -2009,7 +2009,6 @@ static int btrfs_run_delayed_refs_for_head(struct btrfs_trans_handle *trans,default :WARN_ON (1 ); } -atomic_dec (&delayed_refs->num_entries);/* * Record the must_insert_reserved flag before we drop the
fs/btrfs/transaction.c +0 -1
@@ -351,7 +351,6 @@ static noinline int join_transaction(struct btrfs_fs_info *fs_info, cur_trans->delayed_refs.href_root =RB_ROOT_CACHED ;xa_init (&cur_trans->delayed_refs.dirty_extents); -atomic_set (&cur_trans->delayed_refs.num_entries,0 );/* * although the tree mod log is per file system and not per transaction,
Signature · 1 line
2.43.0
PATCH 8/18 btrfs: change return type of btrfs_delayed_ref_lock() to boolean
In reply to [email protected]From: Filipe Manana <[email protected]>
The function only returns 0, meaning it was able to lock the delayed ref head, or -EAGAIN in case it wasn't able to lock it. So simplify this and use a boolean return type instead, returning true if it was able to lock and false otherwise.
--- fs/btrfs/delayed-ref.c | 12 ++++++------ fs/btrfs/delayed-ref.h | 4 ++-- fs/btrfs/extent-tree.c | 6 +++--- 3 files changed, 11 insertions(+), 11 deletions(-)
fs/btrfs/delayed-ref.c +6 -6
@@ -431,12 +431,12 @@ static struct btrfs_delayed_ref_head *find_ref_head(return NULL ; } -int btrfs_delayed_ref_lock (struct btrfs_delayed_ref_root *delayed_refs, -struct btrfs_delayed_ref_head *head) +bool btrfs_delayed_ref_lock (struct btrfs_delayed_ref_root *delayed_refs, +struct btrfs_delayed_ref_head *head) {lockdep_assert_held (&delayed_refs->lock);if (mutex_trylock (&head->mutex)) -return 0 ; +return true;refcount_inc (&head->refs);spin_unlock (&delayed_refs->lock);
@@ -446,10 +446,10 @@ int btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,if (RB_EMPTY_NODE (&head->href_node)) {mutex_unlock (&head->mutex);btrfs_put_delayed_ref_head (head); -return -EAGAIN ; +return false; }btrfs_put_delayed_ref_head (head); -return 0 ; +return true; } static inline void drop_delayed_ref(struct btrfs_fs_info *fs_info,
@@ -1250,7 +1250,7 @@ void btrfs_destroy_delayed_refs(struct btrfs_transaction *trans)if (!head)break ; -if (btrfs_delayed_ref_lock (delayed_refs, head)) +if (!btrfs_delayed_ref_lock (delayed_refs, head))continue ;spin_lock (&head->lock);
fs/btrfs/delayed-ref.h +2 -2
@@ -369,8 +369,8 @@ void btrfs_merge_delayed_refs(struct btrfs_fs_info *fs_info,struct btrfs_delayed_ref_head *btrfs_find_delayed_ref_head (struct btrfs_delayed_ref_root *delayed_refs,u64 bytenr); -int btrfs_delayed_ref_lock (struct btrfs_delayed_ref_root *delayed_refs, -struct btrfs_delayed_ref_head *head); +bool btrfs_delayed_ref_lock (struct btrfs_delayed_ref_root *delayed_refs, +struct btrfs_delayed_ref_head *head);static inline void btrfs_delayed_ref_unlock (struct btrfs_delayed_ref_head *head) {mutex_unlock (&head->mutex);
fs/btrfs/extent-tree.c +3 -3
@@ -1939,7 +1939,7 @@ static struct btrfs_delayed_ref_head *btrfs_obtain_ref_head(struct btrfs_delayed_ref_root *delayed_refs = &trans->transaction->delayed_refs;struct btrfs_delayed_ref_head *head =NULL ; -int ret; +bool locked;spin_lock (&delayed_refs->lock); head =btrfs_select_ref_head (delayed_refs);
@@ -1952,7 +1952,7 @@ static struct btrfs_delayed_ref_head *btrfs_obtain_ref_head(* Grab the lock that says we are going to process all the refs for * this head */ - ret =btrfs_delayed_ref_lock (delayed_refs, head); + locked =btrfs_delayed_ref_lock (delayed_refs, head);spin_unlock (&delayed_refs->lock);/*
@@ -1960,7 +1960,7 @@ static struct btrfs_delayed_ref_head *btrfs_obtain_ref_head(* that might have given someone else time to free the head. If that's * true, it has been removed from our list and we can move on. */ -if (ret == -EAGAIN ) +if (!locked) head =ERR_PTR (-EAGAIN );return head;
Signature · 1 line
2.43.0
PATCH 9/18 btrfs: simplify obtaining a delayed ref head
In reply to [email protected]From: Filipe Manana <[email protected]>
Instead of doing it in two steps outside of delayed-ref.c, leaking low level details such as locking, move the logic entirely to delayed-ref.c under btrfs_select_ref_head(), reducing code and making things simpler for the caller.
--- fs/btrfs/delayed-ref.c | 27 ++++++++++++++++++++++----- fs/btrfs/delayed-ref.h | 2 -- fs/btrfs/extent-tree.c | 35 +---------------------------------- 3 files changed, 23 insertions(+), 41 deletions(-)
fs/btrfs/delayed-ref.c +22 -5
@@ -431,8 +431,8 @@ static struct btrfs_delayed_ref_head *find_ref_head(return NULL ; } -bool btrfs_delayed_ref_lock (struct btrfs_delayed_ref_root *delayed_refs, -struct btrfs_delayed_ref_head *head) +static bool btrfs_delayed_ref_lock (struct btrfs_delayed_ref_root *delayed_refs, +struct btrfs_delayed_ref_head *head) {lockdep_assert_held (&delayed_refs->lock);if (mutex_trylock (&head->mutex))
@@ -561,8 +561,9 @@ struct btrfs_delayed_ref_head *btrfs_select_ref_head( struct btrfs_delayed_ref_root *delayed_refs) {struct btrfs_delayed_ref_head *head; +bool locked; -lockdep_assert_held (&delayed_refs->lock); +spin_lock (&delayed_refs->lock); again: head =find_ref_head (delayed_refs, delayed_refs->run_delayed_start, true);
@@ -570,16 +571,20 @@ struct btrfs_delayed_ref_head *btrfs_select_ref_head( delayed_refs->run_delayed_start =0 ; head =find_first_ref_head (delayed_refs); } -if (!head) +if (!head) { +spin_unlock (&delayed_refs->lock);return NULL ; + }while (head->processing) {struct rb_node *node; node =rb_next (&head->href_node);if (!node) { -if (delayed_refs->run_delayed_start ==0 ) +if (delayed_refs->run_delayed_start ==0 ) { +spin_unlock (&delayed_refs->lock);return NULL ; + } delayed_refs->run_delayed_start =0 ; goto again; }
@@ -592,6 +597,18 @@ struct btrfs_delayed_ref_head *btrfs_select_ref_head( delayed_refs->num_heads_ready--; delayed_refs->run_delayed_start = head->bytenr + head->num_bytes; + + locked =btrfs_delayed_ref_lock (delayed_refs, head); +spin_unlock (&delayed_refs->lock); + +/* +* We may have dropped the spin lock to get the head mutex lock, and +* that might have given someone else time to free the head. If that's +* true, it has been removed from our list and we can move on. +*/ +if (!locked) +return ERR_PTR (-EAGAIN ); +return head; }
fs/btrfs/delayed-ref.h +0 -2
@@ -369,8 +369,6 @@ void btrfs_merge_delayed_refs(struct btrfs_fs_info *fs_info,struct btrfs_delayed_ref_head *btrfs_find_delayed_ref_head (struct btrfs_delayed_ref_root *delayed_refs,u64 bytenr); -bool btrfs_delayed_ref_lock (struct btrfs_delayed_ref_root *delayed_refs, -struct btrfs_delayed_ref_head *head);static inline void btrfs_delayed_ref_unlock (struct btrfs_delayed_ref_head *head) {mutex_unlock (&head->mutex);
fs/btrfs/extent-tree.c +1 -34
@@ -1933,39 +1933,6 @@ static int cleanup_ref_head(struct btrfs_trans_handle *trans,return ret; } -static struct btrfs_delayed_ref_head *btrfs_obtain_ref_head ( -struct btrfs_trans_handle *trans) -{ -struct btrfs_delayed_ref_root *delayed_refs = - &trans->transaction->delayed_refs; -struct btrfs_delayed_ref_head *head =NULL ; -bool locked; - -spin_lock (&delayed_refs->lock); - head =btrfs_select_ref_head (delayed_refs); -if (!head) { -spin_unlock (&delayed_refs->lock); -return head; - } - -/* -* Grab the lock that says we are going to process all the refs for -* this head -*/ - locked =btrfs_delayed_ref_lock (delayed_refs, head); -spin_unlock (&delayed_refs->lock); - -/* -* We may have dropped the spin lock to get the head mutex lock, and -* that might have given someone else time to free the head. If that's -* true, it has been removed from our list and we can move on. -*/ -if (!locked) - head =ERR_PTR (-EAGAIN ); - -return head; -} -static int btrfs_run_delayed_refs_for_head (struct btrfs_trans_handle *trans,struct btrfs_delayed_ref_head *locked_ref,u64 *bytes_released)
@@ -2072,7 +2039,7 @@ static noinline int __btrfs_run_delayed_refs(struct btrfs_trans_handle *trans, do { if (!locked_ref) { - locked_ref = btrfs_obtain_ref_head(trans); + locked_ref = btrfs_select_ref_head(delayed_refs); if (IS_ERR_OR_NULL(locked_ref)) { if (PTR_ERR(locked_ref) == -EAGAIN) { continue;
Signature · 1 line
2.43.0
PATCH 10/18 btrfs: move delayed ref head unselection to delayed-ref.c
In reply to [email protected]From: Filipe Manana <[email protected]>
The unselect_delayed_ref_head() at extent-tree.c doesn't really belong in that file as it's a delayed refs specific detail and therefore should be at delayed-ref.c. Further its inverse, btrfs_select_ref_head(), is at delayed-ref.c, so it only makes sense to have it there too.
So move unselect_delayed_ref_head() into delayed-ref.c and rename it to btrfs_unselect_ref_head() so that its name closely matches its inverse (btrfs_select_ref_head()).
--- fs/btrfs/delayed-ref.c | 10 ++++++++++ fs/btrfs/delayed-ref.h | 2 ++ fs/btrfs/extent-tree.c | 16 +++------------- 3 files changed, 15 insertions(+), 13 deletions(-)
fs/btrfs/delayed-ref.c +10 -0
@@ -612,6 +612,16 @@ struct btrfs_delayed_ref_head *btrfs_select_ref_head(return head; } +void btrfs_unselect_ref_head (struct btrfs_delayed_ref_root *delayed_refs, +struct btrfs_delayed_ref_head *head) +{ +spin_lock (&delayed_refs->lock); + head->processing = false; + delayed_refs->num_heads_ready++; +spin_unlock (&delayed_refs->lock); +btrfs_delayed_ref_unlock (head); +} +void btrfs_delete_ref_head (struct btrfs_delayed_ref_root *delayed_refs,struct btrfs_delayed_ref_head *head) {
fs/btrfs/delayed-ref.h +2 -0
@@ -378,6 +378,8 @@ void btrfs_delete_ref_head(struct btrfs_delayed_ref_root *delayed_refs,struct btrfs_delayed_ref_head *btrfs_select_ref_head (struct btrfs_delayed_ref_root *delayed_refs); +void btrfs_unselect_ref_head (struct btrfs_delayed_ref_root *delayed_refs, +struct btrfs_delayed_ref_head *head);int btrfs_check_delayed_seq (struct btrfs_fs_info *fs_info,u64 seq);
fs/btrfs/extent-tree.c +3 -13
@@ -1807,16 +1807,6 @@ select_delayed_ref(struct btrfs_delayed_ref_head *head)return ref; } -static void unselect_delayed_ref_head (struct btrfs_delayed_ref_root *delayed_refs, -struct btrfs_delayed_ref_head *head) -{ -spin_lock (&delayed_refs->lock); - head->processing = false; - delayed_refs->num_heads_ready++; -spin_unlock (&delayed_refs->lock); -btrfs_delayed_ref_unlock (head); -} -static struct btrfs_delayed_extent_op *cleanup_extent_op (struct btrfs_delayed_ref_head *head) {
@@ -1891,7 +1881,7 @@ static int cleanup_ref_head(struct btrfs_trans_handle *trans, ret =run_and_cleanup_extent_op (trans, head);if (ret <0 ) { -unselect_delayed_ref_head (delayed_refs, head); +btrfs_unselect_ref_head (delayed_refs, head);btrfs_debug (fs_info,"run_delayed_extent_op returned %d" , ret);return ret; }else if (ret) {
@@ -1953,7 +1943,7 @@ static int btrfs_run_delayed_refs_for_head(struct btrfs_trans_handle *trans,if (ref->seq &&btrfs_check_delayed_seq (fs_info, ref->seq)) {spin_unlock (&locked_ref->lock); -unselect_delayed_ref_head (delayed_refs, locked_ref); +btrfs_unselect_ref_head (delayed_refs, locked_ref);return -EAGAIN ; }
@@ -2001,7 +1991,7 @@ static int btrfs_run_delayed_refs_for_head(struct btrfs_trans_handle *trans,btrfs_free_delayed_extent_op (extent_op);if (ret) { -unselect_delayed_ref_head (delayed_refs, locked_ref); +btrfs_unselect_ref_head (delayed_refs, locked_ref);btrfs_put_delayed_ref (ref);return ret; }
Signature · 1 line
2.43.0
PATCH 11/18 btrfs: pass fs_info to functions that search for delayed ref heads
In reply to [email protected]From: Filipe Manana <[email protected]>
One of the following patches in the series will need to access fs_info in the function find_ref_head(), so pass a fs_info argument to it as well as to the functions btrfs_select_ref_head() and btrfs_find_delayed_ref_head() which call find_ref_head().
--- fs/btrfs/backref.c | 3 ++- fs/btrfs/delayed-ref.c | 12 ++++++++---- fs/btrfs/delayed-ref.h | 4 +++- fs/btrfs/extent-tree.c | 10 +++++----- 4 files changed, 18 insertions(+), 11 deletions(-)
fs/btrfs/backref.c +2 -1
@@ -1442,7 +1442,8 @@ static int find_parent_nodes(struct btrfs_backref_walk_ctx *ctx,*/ delayed_refs = &ctx->trans->transaction->delayed_refs;spin_lock (&delayed_refs->lock); - head =btrfs_find_delayed_ref_head (delayed_refs, ctx->bytenr); + head =btrfs_find_delayed_ref_head (ctx->fs_info, delayed_refs, + ctx->bytenr);if (head) {if (!mutex_trylock (&head->mutex)) {refcount_inc (&head->refs);
fs/btrfs/delayed-ref.c +8 -4
@@ -399,6 +399,7 @@ static struct btrfs_delayed_ref_head *find_first_ref_head(* is given, the next bigger entry is returned if no exact match is found. */ static struct btrfs_delayed_ref_head *find_ref_head ( +struct btrfs_fs_info *fs_info,struct btrfs_delayed_ref_root *dr,u64 bytenr,bool return_bigger) {
@@ -558,6 +559,7 @@ int btrfs_check_delayed_seq(struct btrfs_fs_info *fs_info, u64 seq) }struct btrfs_delayed_ref_head *btrfs_select_ref_head ( +struct btrfs_fs_info *fs_info,struct btrfs_delayed_ref_root *delayed_refs) {struct btrfs_delayed_ref_head *head;
@@ -565,8 +567,8 @@ struct btrfs_delayed_ref_head *btrfs_select_ref_head(spin_lock (&delayed_refs->lock); again: - head =find_ref_head (delayed_refs, delayed_refs->run_delayed_start, - true); + head =find_ref_head (fs_info, delayed_refs, + delayed_refs->run_delayed_start, true);if (!head && delayed_refs->run_delayed_start !=0 ) { delayed_refs->run_delayed_start =0 ; head =find_first_ref_head (delayed_refs);
@@ -1188,11 +1190,13 @@ void btrfs_put_delayed_ref(struct btrfs_delayed_ref_node *ref)* head node if found, or NULL if not. */ struct btrfs_delayed_ref_head * -btrfs_find_delayed_ref_head (struct btrfs_delayed_ref_root *delayed_refs,u64 bytenr) +btrfs_find_delayed_ref_head (struct btrfs_fs_info *fs_info, +struct btrfs_delayed_ref_root *delayed_refs, +u64 bytenr) {lockdep_assert_held (&delayed_refs->lock); -return find_ref_head (delayed_refs, bytenr, false); +return find_ref_head (fs_info, delayed_refs, bytenr, false); }static int find_comp (struct btrfs_delayed_ref_node *entry,u64 root,u64 parent)
fs/btrfs/delayed-ref.h +3 -1
@@ -367,7 +367,8 @@ void btrfs_merge_delayed_refs(struct btrfs_fs_info *fs_info, struct btrfs_delayed_ref_head *head);struct btrfs_delayed_ref_head * -btrfs_find_delayed_ref_head (struct btrfs_delayed_ref_root *delayed_refs, +btrfs_find_delayed_ref_head (struct btrfs_fs_info *fs_info, +struct btrfs_delayed_ref_root *delayed_refs,u64 bytenr);static inline void btrfs_delayed_ref_unlock (struct btrfs_delayed_ref_head *head) {
@@ -377,6 +378,7 @@ void btrfs_delete_ref_head(struct btrfs_delayed_ref_root *delayed_refs, struct btrfs_delayed_ref_head *head);struct btrfs_delayed_ref_head *btrfs_select_ref_head ( +struct btrfs_fs_info *fs_info,struct btrfs_delayed_ref_root *delayed_refs);void btrfs_unselect_ref_head (struct btrfs_delayed_ref_root *delayed_refs,struct btrfs_delayed_ref_head *head);
fs/btrfs/extent-tree.c +5 -5
@@ -182,7 +182,7 @@ int btrfs_lookup_extent_info(struct btrfs_trans_handle *trans, delayed_refs = &trans->transaction->delayed_refs;spin_lock (&delayed_refs->lock); - head =btrfs_find_delayed_ref_head (delayed_refs, bytenr); + head =btrfs_find_delayed_ref_head (fs_info, delayed_refs, bytenr);if (head) {if (!mutex_trylock (&head->mutex)) {refcount_inc (&head->refs);
@@ -2029,7 +2029,7 @@ static noinline int __btrfs_run_delayed_refs(struct btrfs_trans_handle *trans, do { if (!locked_ref) { - locked_ref = btrfs_select_ref_head(delayed_refs); + locked_ref = btrfs_select_ref_head(fs_info, delayed_refs); if (IS_ERR_OR_NULL(locked_ref)) { if (PTR_ERR(locked_ref) == -EAGAIN) { continue;
@@ -2231,7 +2231,7 @@ static noinline int check_delayed_ref(struct btrfs_root *root, delayed_refs = &cur_trans->delayed_refs;spin_lock (&delayed_refs->lock); - head =btrfs_find_delayed_ref_head (delayed_refs, bytenr); + head =btrfs_find_delayed_ref_head (root->fs_info, delayed_refs, bytenr);if (!head) {spin_unlock (&delayed_refs->lock);btrfs_put_transaction (cur_trans);
@@ -3339,7 +3339,7 @@ static noinline int check_ref_cleanup(struct btrfs_trans_handle *trans, delayed_refs = &trans->transaction->delayed_refs;spin_lock (&delayed_refs->lock); - head =btrfs_find_delayed_ref_head (delayed_refs, bytenr); + head =btrfs_find_delayed_ref_head (trans->fs_info, delayed_refs, bytenr);if (!head) goto out_delayed_unlock;
@@ -5474,7 +5474,7 @@ static int check_ref_exists(struct btrfs_trans_handle *trans,*/ delayed_refs = &trans->transaction->delayed_refs;spin_lock (&delayed_refs->lock); - head =btrfs_find_delayed_ref_head (delayed_refs, bytenr); + head =btrfs_find_delayed_ref_head (root->fs_info, delayed_refs, bytenr);if (!head) goto out;if (!mutex_trylock (&head->mutex)) {
Signature · 1 line
2.43.0
PATCH 12/18 btrfs: pass fs_info to btrfs_cleanup_ref_head_accounting
In reply to [email protected]From: Filipe Manana <[email protected]>
One of the following patches in the series will need to access fs_info at btrfs_cleanup_ref_head_accounting(), so pass a fs_info argument to it.
--- fs/btrfs/delayed-ref.c | 5 +++-- fs/btrfs/delayed-ref.h | 3 ++- fs/btrfs/extent-tree.c | 9 +++++---- 3 files changed, 10 insertions(+), 7 deletions(-)
fs/btrfs/delayed-ref.c +3 -2
@@ -624,7 +624,8 @@ void btrfs_unselect_ref_head(struct btrfs_delayed_ref_root *delayed_refs,btrfs_delayed_ref_unlock (head); } -void btrfs_delete_ref_head (struct btrfs_delayed_ref_root *delayed_refs, +void btrfs_delete_ref_head (struct btrfs_fs_info *fs_info, +struct btrfs_delayed_ref_root *delayed_refs,struct btrfs_delayed_ref_head *head) {lockdep_assert_held (&delayed_refs->lock);
@@ -1294,7 +1295,7 @@ void btrfs_destroy_delayed_refs(struct btrfs_transaction *trans)if (head->must_insert_reserved) pin_bytes = true;btrfs_free_delayed_extent_op (head->extent_op); -btrfs_delete_ref_head (delayed_refs, head); +btrfs_delete_ref_head (fs_info, delayed_refs, head);spin_unlock (&head->lock);spin_unlock (&delayed_refs->lock);mutex_unlock (&head->mutex);
fs/btrfs/delayed-ref.h +2 -1
@@ -374,7 +374,8 @@ static inline void btrfs_delayed_ref_unlock(struct btrfs_delayed_ref_head *head) {mutex_unlock (&head->mutex); } -void btrfs_delete_ref_head (struct btrfs_delayed_ref_root *delayed_refs, +void btrfs_delete_ref_head (struct btrfs_fs_info *fs_info, +struct btrfs_delayed_ref_root *delayed_refs,struct btrfs_delayed_ref_head *head); struct btrfs_delayed_ref_head *btrfs_select_ref_head(
fs/btrfs/extent-tree.c +5 -4
@@ -1900,7 +1900,7 @@ static int cleanup_ref_head(struct btrfs_trans_handle *trans,spin_unlock (&delayed_refs->lock);return 1 ; } -btrfs_delete_ref_head (delayed_refs, head); +btrfs_delete_ref_head (fs_info, delayed_refs, head);spin_unlock (&head->lock);spin_unlock (&delayed_refs->lock);
@@ -3333,13 +3333,14 @@ static int __btrfs_free_extent(struct btrfs_trans_handle *trans, static noinline int check_ref_cleanup(struct btrfs_trans_handle *trans,u64 bytenr) { +struct btrfs_fs_info *fs_info = trans->fs_info;struct btrfs_delayed_ref_head *head;struct btrfs_delayed_ref_root *delayed_refs;int ret =0 ; delayed_refs = &trans->transaction->delayed_refs;spin_lock (&delayed_refs->lock); - head =btrfs_find_delayed_ref_head (trans->fs_info, delayed_refs, bytenr); + head =btrfs_find_delayed_ref_head (fs_info, delayed_refs, bytenr);if (!head) goto out_delayed_unlock;
@@ -3357,7 +3358,7 @@ static noinline int check_ref_cleanup(struct btrfs_trans_handle *trans,if (!mutex_trylock (&head->mutex)) goto out; -btrfs_delete_ref_head (delayed_refs, head); +btrfs_delete_ref_head (fs_info, delayed_refs, head); head->processing = false;spin_unlock (&head->lock);
@@ -3367,7 +3368,7 @@ static noinline int check_ref_cleanup(struct btrfs_trans_handle *trans,if (head->must_insert_reserved) ret =1 ; -btrfs_cleanup_ref_head_accounting (trans->fs_info, delayed_refs, head); +btrfs_cleanup_ref_head_accounting (fs_info, delayed_refs, head);mutex_unlock (&head->mutex);btrfs_put_delayed_ref_head (head);return ret;
Signature · 1 line
2.43.0
PATCH 13/18 btrfs: assert delayed refs lock is held at find_ref_head()
In reply to [email protected]From: Filipe Manana <[email protected]>
We have 3 callers for find_ref_head() so assert at find_ref_head() that we have the delayed refs lock held, removing the assertion from one of its callers (btrfs_find_delayed_ref_head()).
--- fs/btrfs/delayed-ref.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
fs/btrfs/delayed-ref.c +2 -2
@@ -407,6 +407,8 @@ static struct btrfs_delayed_ref_head *find_ref_head(struct rb_node *n;struct btrfs_delayed_ref_head *entry; +lockdep_assert_held (&dr->lock); + n = root->rb_node; entry =NULL ;while (n) {
@@ -1195,8 +1197,6 @@ btrfs_find_delayed_ref_head(struct btrfs_fs_info *fs_info,struct btrfs_delayed_ref_root *delayed_refs, u64 bytenr) { -lockdep_assert_held (&delayed_refs->lock); - return find_ref_head(fs_info, delayed_refs, bytenr, false); }
Signature · 1 line
2.43.0
PATCH 14/18 btrfs: assert delayed refs lock is held at find_first_ref_head()
In reply to [email protected]From: Filipe Manana <[email protected]>
The delayed refs lock must be held when calling find_first_ref_head(), so assert that it's being held.
--- fs/btrfs/delayed-ref.c | 2 ++ 1 file changed, 2 insertions(+)
fs/btrfs/delayed-ref.c +2 -0
@@ -384,6 +384,8 @@ static struct btrfs_delayed_ref_head *find_first_ref_head(struct rb_node *n;struct btrfs_delayed_ref_head *entry; +lockdep_assert_held (&dr->lock); + n =rb_first_cached (&dr->href_root);if (!n)return NULL ;
Signature · 1 line
2.43.0
PATCH 15/18 btrfs: assert delayed refs lock is held at add_delayed_ref_head()
In reply to [email protected]From: Filipe Manana <[email protected]>
The delayed refs lock must be held when calling add_delayed_ref_head(), so assert that it's being held.
--- fs/btrfs/delayed-ref.c | 1 + 1 file changed, 1 insertion(+)
fs/btrfs/delayed-ref.c +1 -0
@@ -886,6 +886,7 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,bool qrecord_inserted = false; delayed_refs = &trans->transaction->delayed_refs; +lockdep_assert_held (&delayed_refs->lock);/* Record qgroup extent info if provided */ if (qrecord) {
Signature · 1 line
2.43.0
PATCH 16/18 btrfs: add comments regarding locking to struct btrfs_delayed_ref_root
In reply to [email protected]From: Filipe Manana <[email protected]>
Add some comments to struct btrfs_delayed_ref_root's fields to mention what its spinlock protects.
--- fs/btrfs/delayed-ref.h | 20 +++++++++++++++++--- 1 file changed, 17 insertions(+), 3 deletions(-)
fs/btrfs/delayed-ref.h +17 -3
@@ -213,19 +213,33 @@ struct btrfs_delayed_ref_root {*/ struct xarray dirty_extents; -/* this spin lock protects the rbtree and the entries inside */ +/* +* Protects the rbtree href_root, its entries and the following fields: +* num_heads, num_heads_ready, pending_csums and run_delayed_start. +*/ spinlock_t lock; -/* total number of head nodes in tree */ +/* Total number of head refs, protected by the spinlock 'lock'. */ unsigned long num_heads; -/* total number of head nodes ready for processing */ +/* +* Total number of head refs ready for processing, protected by the +* spinlock 'lock'. +*/ unsigned long num_heads_ready; +/* +* Track space reserved for deleting csums of data extents. +* Protected by the spinlock 'lock'. +*/ u64 pending_csums;unsigned long flags; +/* +* Track from which bytenr to start searching ref heads. +* Protected by the spinlock 'lock'. +*/ u64 run_delayed_start;/*
Signature · 1 line
2.43.0
PATCH 17/18 btrfs: track delayed ref heads in an xarray
In reply to [email protected]From: Filipe Manana <[email protected]>
Currently we use a red black tree (rb-tree) to track the delayed ref heads (in struct btrfs_delayed_ref_root::href_root). This however is not very efficient when the number of delayed ref heads is large (and it's very common to be at least in the order of thousands) since rb-trees are binary trees. For example for 10K delayed ref heads, the tree has a depth of 13. Besides that, inserting into the tree requires navigating through it and pulling useless cache lines in the process since the red black tree nodes are embedded within the delayed ref head structure - on the other hand, by being embedded, it requires no extra memory allocations.
We can improve this by using an xarray instead which has a much higher branching factor than a red black tree (binary balanced tree) and is more cache friendly and behaves like a resizable array, with a much better search and insertion complexity than a red black tree. This only has one small disadvantage which is that insertion will sometimes require allocating memory for the xarray - which may fail (not that often since it uses a kmem_cache) - but on the other hand we can reduce the delayed ref head structure size by 24 bytes (from 152 down to 128 bytes) after removing the embedded red black tree node, meaning than we can now fit 32 delayed ref heads per 4K page instead of 26, and that gain compensates for the occasional memory allocations needed for the xarray nodes. We also end up using only 2 cache lines instead of 3 per delayed ref head.
Running the following fs_mark test showed some improvements:
$ cat test.sh
#!/bin/bash DEV=/dev/nullb0
MNT=/mnt/nullb0
MOUNT_OPTIONS="-o ssd"
FILES=100000
THREADS=$(nproc --all)
echo "performance" | \
tee /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
mkfs.btrfs -f $DEV
mount $MOUNT_OPTIONS $DEV $MNT
OPTS="-S 0 -L 5 -n $FILES -s 0 -t $THREADS -k"
for ((i = 1; i <= $THREADS; i++)); do
OPTS="$OPTS -d $MNT/d$i"
done
fs_mark $OPTS
umount $MNTBefore this patch:
FSUse% Count Size Files/sec App Overhead
10 1200000 0 171845.7 12253839
16 2400000 0 230898.7 12308254
23 3600000 0 212292.9 12467768
30 4800000 0 195737.8 12627554
46 6000000 0 171055.2 12783329After this patch:
FSUse% Count Size Files/sec App Overhead
10 1200000 0 173835.0 12246131
16 2400000 0 233537.8 12271746
23 3600000 0 220398.7 12307737
30 4800000 0 204483.6 12392318
40 6000000 0 182923.3 12771843--- fs/btrfs/delayed-ref.c | 192 +++++++++++++++++++---------------------- fs/btrfs/delayed-ref.h | 26 +++--- fs/btrfs/extent-tree.c | 2 +- fs/btrfs/transaction.c | 5 +- 4 files changed, 106 insertions(+), 119 deletions(-)
fs/btrfs/delayed-ref.c +88 -104
@@ -314,39 +314,6 @@ static int comp_refs(struct btrfs_delayed_ref_node *ref1,return 0 ; } -/* insert a new ref to head ref rbtree */ -static struct btrfs_delayed_ref_head *htree_insert (struct rb_root_cached *root, -struct rb_node *node) -{ -struct rb_node **p = &root->rb_root.rb_node; -struct rb_node *parent_node =NULL ; -struct btrfs_delayed_ref_head *entry; -struct btrfs_delayed_ref_head *ins; -u64 bytenr; -bool leftmost = true; - - ins = rb_entry(node, struct btrfs_delayed_ref_head, href_node); - bytenr = ins->bytenr; -while (*p) { - parent_node = *p; - entry = rb_entry(parent_node, struct btrfs_delayed_ref_head, - href_node); - -if (bytenr < entry->bytenr) { - p = &(*p)->rb_left; - }else if (bytenr > entry->bytenr) { - p = &(*p)->rb_right; - leftmost = false; - }else { -return entry; - } - } - -rb_link_node (node, parent_node, p); -rb_insert_color_cached (node, root, leftmost); -return NULL ; -} -static struct btrfs_delayed_ref_node *tree_insert (struct rb_root_cached *root,struct btrfs_delayed_ref_node *ins) {
@@ -381,18 +348,11 @@ static struct btrfs_delayed_ref_node* tree_insert(struct rb_root_cached *root,static struct btrfs_delayed_ref_head *find_first_ref_head (struct btrfs_delayed_ref_root *dr) { -struct rb_node *n; -struct btrfs_delayed_ref_head *entry; +unsigned long from =0 ;lockdep_assert_held (&dr->lock); - n =rb_first_cached (&dr->href_root); -if (!n) -return NULL ; - - entry = rb_entry(n, struct btrfs_delayed_ref_head, href_node); - -return entry; +return xa_find (&dr->head_refs, &from,ULONG_MAX ,XA_PRESENT ); }/*
@@ -405,35 +365,22 @@ static struct btrfs_delayed_ref_head *find_ref_head( struct btrfs_delayed_ref_root *dr, u64 bytenr, bool return_bigger) { - struct rb_root *root = &dr->href_root.rb_root; -struct rb_node *n; + const unsigned long target_index = (bytenr >> fs_info->sectorsize_bits); +unsigned long found_index = target_index;struct btrfs_delayed_ref_head *entry;lockdep_assert_held (&dr->lock); - n = root->rb_node; - entry =NULL ; -while (n) { - entry = rb_entry(n, struct btrfs_delayed_ref_head, href_node); + entry =xa_find (&dr->head_refs, &found_index,ULONG_MAX ,XA_PRESENT ); +if (!entry) +return NULL ; + +ASSERT (found_index >= target_index); -if (bytenr < entry->bytenr) - n = n->rb_left; -else if (bytenr > entry->bytenr) - n = n->rb_right; -else -return entry; - } -if (entry && return_bigger) { -if (bytenr > entry->bytenr) { - n =rb_next (&entry->href_node); -if (!n) -return NULL ; - entry = rb_entry(n, struct btrfs_delayed_ref_head, - href_node); - } -return entry; - } -return NULL ; +if (found_index != target_index && !return_bigger) +return NULL ; + +return entry; } static bool btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,
@@ -448,7 +395,7 @@ static bool btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,mutex_lock (&head->mutex);spin_lock (&delayed_refs->lock); -if (RB_EMPTY_NODE (&head->href_node)) { +if (!head->tracked) {mutex_unlock (&head->mutex);btrfs_put_delayed_ref_head (head);return false;
@@ -567,35 +514,27 @@ struct btrfs_delayed_ref_head *btrfs_select_ref_head( struct btrfs_delayed_ref_root *delayed_refs) {struct btrfs_delayed_ref_head *head; +unsigned long start_index; +unsigned long found_index; +bool found_head = false;bool locked;spin_lock (&delayed_refs->lock); again: - head =find_ref_head (fs_info, delayed_refs, - delayed_refs->run_delayed_start, true); -if (!head && delayed_refs->run_delayed_start !=0 ) { - delayed_refs->run_delayed_start =0 ; - head =find_first_ref_head (delayed_refs); - } -if (!head) { -spin_unlock (&delayed_refs->lock); -return NULL ; + start_index = (delayed_refs->run_delayed_start >> fs_info->sectorsize_bits); +xa_for_each_start (&delayed_refs->head_refs, found_index, head, start_index) { +if (!head->processing) { + found_head = true; +break ; + } } - -while (head->processing) { -struct rb_node *node; - - node =rb_next (&head->href_node); -if (!node) { -if (delayed_refs->run_delayed_start ==0 ) { -spin_unlock (&delayed_refs->lock); -return NULL ; - } - delayed_refs->run_delayed_start =0 ; - goto again; +if (!found_head) { +if (delayed_refs->run_delayed_start ==0 ) { +spin_unlock (&delayed_refs->lock); +return NULL ; } - head = rb_entry(node, struct btrfs_delayed_ref_head, - href_node); + delayed_refs->run_delayed_start =0 ; + goto again; } head->processing = true;
@@ -632,11 +571,13 @@ void btrfs_delete_ref_head(struct btrfs_fs_info *fs_info, struct btrfs_delayed_ref_root *delayed_refs, struct btrfs_delayed_ref_head *head) { +const unsigned long index = (head->bytenr >> fs_info->sectorsize_bits); +lockdep_assert_held (&delayed_refs->lock);lockdep_assert_held (&head->lock); -rb_erase_cached (&head->href_node, &delayed_refs->href_root); -RB_CLEAR_NODE (&head->href_node); +xa_erase (&delayed_refs->head_refs, index); + head->tracked = false; delayed_refs->num_heads--;if (!head->processing) delayed_refs->num_heads_ready--;
@@ -845,7 +786,7 @@ static void init_delayed_ref_head(struct btrfs_delayed_ref_head *head_ref, head_ref->is_system = (generic_ref->ref_root ==BTRFS_CHUNK_TREE_OBJECTID ); head_ref->ref_tree =RB_ROOT_CACHED ;INIT_LIST_HEAD (&head_ref->ref_add_list); -RB_CLEAR_NODE (&head_ref->href_node); + head_ref->tracked = false; head_ref->processing = false; head_ref->total_ref_mod = count_mod;spin_lock_init (&head_ref->lock);
@@ -883,11 +824,24 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,struct btrfs_fs_info *fs_info = trans->fs_info;struct btrfs_delayed_ref_head *existing;struct btrfs_delayed_ref_root *delayed_refs; +const unsigned long index = (head_ref->bytenr >> fs_info->sectorsize_bits);bool qrecord_inserted = false; delayed_refs = &trans->transaction->delayed_refs;lockdep_assert_held (&delayed_refs->lock); +#if BITS_PER_LONG ==32 +if (head_ref->bytenr >=MAX_LFS_FILESIZE ) { +if (qrecord) +xa_release (&delayed_refs->dirty_extents, index); +btrfs_err_rl (fs_info, +"delayed ref head %llu is beyond 32bit page cache and xarray index limit" , + head_ref->bytenr); +btrfs_err_32bit_limit (fs_info); +return ERR_PTR (-EOVERFLOW ); + } +#endif +/* Record qgroup extent info if provided */ if (qrecord) {int ret;
@@ -896,8 +850,7 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans, head_ref->bytenr);if (ret) {/* Clean up if insertion fails or item exists. */ -xa_release (&delayed_refs->dirty_extents, - head_ref->bytenr >> fs_info->sectorsize_bits); +xa_release (&delayed_refs->dirty_extents, index);/* Caller responsible for freeing qrecord on error. */ if (ret <0 )return ERR_PTR (ret);
@@ -909,8 +862,7 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,trace_add_delayed_ref_head (fs_info, head_ref, action); - existing =htree_insert (&delayed_refs->href_root, - &head_ref->href_node); + existing =xa_load (&delayed_refs->head_refs, index);if (existing) {update_existing_head_ref (trans, existing, head_ref);/*
@@ -920,6 +872,19 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,kmem_cache_free (btrfs_delayed_ref_head_cachep, head_ref); head_ref = existing; }else { + existing =xa_store (&delayed_refs->head_refs, index, head_ref,GFP_ATOMIC ); +if (xa_is_err (existing)) { +/* Memory was preallocated by the caller. */ +ASSERT (xa_err (existing) != -ENOMEM ); +return ERR_CAST (existing); + }else if (WARN_ON (existing)) { +/* +* Shouldn't happen we just did a lookup before under +* delayed_refs->lock. +*/ +return ERR_PTR (-EEXIST ); + } + head_ref->tracked = true;/* * We reserve the amount of bytes needed to delete csums when * adding the ref head and not when adding individual drop refs
@@ -1040,6 +1005,8 @@ static int add_delayed_ref(struct btrfs_trans_handle *trans,struct btrfs_delayed_ref_head *new_head_ref;struct btrfs_delayed_ref_root *delayed_refs;struct btrfs_qgroup_extent_record *record =NULL ; +const unsigned long index = (generic_ref->bytenr >> fs_info->sectorsize_bits); +bool qrecord_reserved = false;bool qrecord_inserted;int action = generic_ref->action;bool merged;
@@ -1055,25 +1022,32 @@ static int add_delayed_ref(struct btrfs_trans_handle *trans, goto free_node; } + delayed_refs = &trans->transaction->delayed_refs; +if (btrfs_qgroup_full_accounting (fs_info) && !generic_ref->skip_qgroup) { record =kzalloc (sizeof (*record),GFP_NOFS );if (!record) { ret = -ENOMEM ; goto free_head_ref; } -if (xa_reserve (&trans->transaction->delayed_refs.dirty_extents, - generic_ref->bytenr >> fs_info->sectorsize_bits, -GFP_NOFS )) { +if (xa_reserve (&delayed_refs->dirty_extents, index,GFP_NOFS )) { ret = -ENOMEM ; goto free_record; } + qrecord_reserved = true; + } + + ret =xa_reserve (&delayed_refs->head_refs, index,GFP_NOFS ); +if (ret) { +if (qrecord_reserved) +xa_release (&delayed_refs->dirty_extents, index); + goto free_record; }init_delayed_ref_common (fs_info, node, generic_ref);init_delayed_ref_head (head_ref, generic_ref, record, reserved); head_ref->extent_op = extent_op; - delayed_refs = &trans->transaction->delayed_refs;spin_lock (&delayed_refs->lock);/*
@@ -1083,6 +1057,7 @@ static int add_delayed_ref(struct btrfs_trans_handle *trans, new_head_ref =add_delayed_ref_head (trans, head_ref, record, action, &qrecord_inserted);if (IS_ERR (new_head_ref)) { +xa_release (&delayed_refs->head_refs, index);spin_unlock (&delayed_refs->lock); ret =PTR_ERR (new_head_ref); goto free_record;
@@ -1145,6 +1120,7 @@ int btrfs_add_delayed_extent_op(struct btrfs_trans_handle *trans, u64 bytenr, u64 num_bytes, u8 level, struct btrfs_delayed_extent_op *extent_op) { + const unsigned long index = (bytenr >> trans->fs_info->sectorsize_bits);struct btrfs_delayed_ref_head *head_ref;struct btrfs_delayed_ref_head *head_ref_ret;struct btrfs_delayed_ref_root *delayed_refs;
@@ -1155,6 +1131,7 @@ int btrfs_add_delayed_extent_op(struct btrfs_trans_handle *trans, .num_bytes = num_bytes, .tree_ref.level = level, }; +int ret; head_ref =kmem_cache_alloc (btrfs_delayed_ref_head_cachep,GFP_NOFS );if (!head_ref)
@@ -1164,16 +1141,23 @@ int btrfs_add_delayed_extent_op(struct btrfs_trans_handle *trans, head_ref->extent_op = extent_op; delayed_refs = &trans->transaction->delayed_refs; -spin_lock (&delayed_refs->lock); + ret =xa_reserve (&delayed_refs->head_refs, index,GFP_NOFS ); +if (ret) { +kmem_cache_free (btrfs_delayed_ref_head_cachep, head_ref); +return ret; + } + +spin_lock (&delayed_refs->lock); head_ref_ret =add_delayed_ref_head (trans, head_ref,NULL ,BTRFS_UPDATE_DELAYED_HEAD ,NULL ); -spin_unlock (&delayed_refs->lock); -if (IS_ERR (head_ref_ret)) { +xa_release (&delayed_refs->head_refs, index); +spin_unlock (&delayed_refs->lock);kmem_cache_free (btrfs_delayed_ref_head_cachep, head_ref);return PTR_ERR (head_ref_ret); } +spin_unlock (&delayed_refs->lock);/* * Need to update the delayed_refs_rsv with any changes we may have
fs/btrfs/delayed-ref.h +15 -11
@@ -122,12 +122,6 @@ struct btrfs_delayed_extent_op {struct btrfs_delayed_ref_head {u64 bytenr;u64 num_bytes; -/* -* For insertion into struct btrfs_delayed_ref_root::href_root. -* Keep it in the same cache line as 'bytenr' for more efficient -* searches in the rbtree. -*/ -struct rb_node href_node;/* * the mutex is held while running the refs, and it is also * held when checking the sum of reference modifications.
@@ -191,6 +185,11 @@ struct btrfs_delayed_ref_head {bool is_data;bool is_system;bool processing; +/* +* Indicate if it's currently in the data structure that tracks head +* refs (struct btrfs_delayed_ref_root::head_refs). +*/ +bool tracked; };enum btrfs_delayed_ref_flags {
@@ -199,22 +198,27 @@ enum btrfs_delayed_ref_flags { };struct btrfs_delayed_ref_root { -/* head ref rbtree */ -struct rb_root_cached href_root; -/* -* Track dirty extent records. +* Track head references. * The keys correspond to the logical address of the extent ("bytenr") * right shifted by fs_info->sectorsize_bits. This is both to get a more * dense index space (optimizes xarray structure) and because indexes in * xarrays are of "unsigned long" type, meaning they are 32 bits wide on * 32 bits platforms, limiting the extent range to 4G which is too low * and makes it unusable (truncated index values) on 32 bits platforms. +* Protected by the spinlock 'lock' defined below. +*/ +struct xarray head_refs; + +/* +* Track dirty extent records. +* The keys correspond to the logical address of the extent ("bytenr") +* right shifted by fs_info->sectorsize_bits, for same reasons as above. */ struct xarray dirty_extents;/* -* Protects the rbtree href_root, its entries and the following fields: +* Protects the xarray head_refs, its entries and the following fields: * num_heads, num_heads_ready, pending_csums and run_delayed_start. */ spinlock_t lock;
fs/btrfs/extent-tree.c +1 -1
@@ -2176,7 +2176,7 @@ int btrfs_run_delayed_refs(struct btrfs_trans_handle *trans, u64 min_bytes)btrfs_create_pending_block_groups (trans);spin_lock (&delayed_refs->lock); -if (RB_EMPTY_ROOT (&delayed_refs->href_root.rb_root)) { +if (xa_empty (&delayed_refs->head_refs)) {spin_unlock (&delayed_refs->lock);return 0 ; }
fs/btrfs/transaction.c +2 -3
@@ -141,8 +141,7 @@ void btrfs_put_transaction(struct btrfs_transaction *transaction)WARN_ON (refcount_read (&transaction->use_count) ==0 );if (refcount_dec_and_test (&transaction->use_count)) {BUG_ON (!list_empty (&transaction->list)); -WARN_ON (!RB_EMPTY_ROOT ( - &transaction->delayed_refs.href_root.rb_root)); +WARN_ON (!xa_empty (&transaction->delayed_refs.head_refs));WARN_ON (!xa_empty (&transaction->delayed_refs.dirty_extents));if (transaction->delayed_refs.pending_csums) btrfs_err(transaction->fs_info,
@@ -349,7 +348,7 @@ static noinline int join_transaction(struct btrfs_fs_info *fs_info,memset (&cur_trans->delayed_refs,0 ,sizeof (cur_trans->delayed_refs)); - cur_trans->delayed_refs.href_root =RB_ROOT_CACHED ; +xa_init (&cur_trans->delayed_refs.head_refs);xa_init (&cur_trans->delayed_refs.dirty_extents);/*
Signature · 1 line
2.43.0
Re: [PATCH 17/18] btrfs: track delayed ref heads in an xarray
Quoted 12 lines · On Thu, Oct 24, 2024 at 05:24:25PM +0100, [email protected] wrote:
From: Filipe Manana <[email protected]>
Currently we use a red black tree (rb-tree) to track the delayed ref heads (in struct
btrfs_delayed_ref_root::href_root). This however is not very efficient when the number of delayed ref heads is large (and it's very common to be at least in the order of thousands) since rb-trees are binary trees. For example for 10K delayed ref heads, the tree has a depth of 13. Besides that, inserting into the tree requires navigating through it and pulling useless cache lines in the process since the red black tree nodes are embedded within the delayed ref head structure - on the other hand, by being embedded, it requires no extra memory allocations.
Quoted 12 lines
We can improve this by using an xarray instead which has a much higher branching factor than a red black tree (binary balanced tree) and is more cache friendly and behaves like a resizable array, with a much better search and insertion complexity than a red black tree. This only has one small disadvantage which is that insertion will sometimes require allocating memory for the xarray - which may fail (not that often since it uses a
kmem_cache) - but on the other hand we can reduce the delayed ref head structure size by 24 bytes (from 152 down to 128 bytes) after removing the embedded red black tree node, meaning than we can now fit 32 delayed ref heads per 4K page instead of 26, and that gain compensates for the occasional memory allocations needed for the xarray nodes. We also end up using only 2 cache lines instead of 3 per delayed ref head.
The explanation makes sense to me, and I don't think the new allocation is particularly risky, since the paths calling add_delayed_ref_head are already allocating and can return ENOMEM.
With that said, just curious, have you tried hammering this under memory pressure? Have you been able to create conditions where the new allocation fails?
Quoted 443 lines
Running the following
fs_marktest showed some improvements:$ cat test.sh #!/bin/bashDEV=/dev/nullb0 MNT=/mnt/nullb0 MOUNT_OPTIONS="-o ssd" FILES=100000 THREADS=$(nproc --all) echo "performance" | \ tee /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor mkfs.btrfs -f $DEV mount $MOUNT_OPTIONS $DEV $MNT OPTS="-S 0 -L 5 -n $FILES -s 0 -t $THREADS -k" for ((i = 1; i <= $THREADS; i++)); do OPTS="$OPTS -d $MNT/d$i" done fs_mark $OPTS umount $MNTBefore this patch:
FSUse% Count Size Files/sec App Overhead 10 1200000 0 171845.7 12253839 16 2400000 0 230898.7 12308254 23 3600000 0 212292.9 12467768 30 4800000 0 195737.8 12627554 46 6000000 0 171055.2 12783329After this patch:
FSUse% Count Size Files/sec App Overhead 10 1200000 0 173835.0 12246131 16 2400000 0 233537.8 12271746 23 3600000 0 220398.7 12307737 30 4800000 0 204483.6 12392318 40 6000000 0 182923.3 12771843Signed-off-by Filipe Manana <[email protected]>--- fs/btrfs/delayed-ref.c | 192 +++++++++++++++++++---------------------- fs/btrfs/delayed-ref.h | 26 +++--- fs/btrfs/extent-tree.c | 2 +- fs/btrfs/transaction.c | 5 +- 4 files changed, 106 insertions(+), 119 deletions(-)fs/btrfs/delayed-ref.c +88
-104@@ -314,39 +314,6 @@ static int comp_refs(struct btrfs_delayed_ref_node *ref1,return 0 ; } -/* insert a new ref to head ref rbtree */ -static struct btrfs_delayed_ref_head *htree_insert (struct rb_root_cached *root, -struct rb_node *node) -{ -struct rb_node **p = &root->rb_root.rb_node; -struct rb_node *parent_node =NULL ; -struct btrfs_delayed_ref_head *entry; -struct btrfs_delayed_ref_head *ins; -u64 bytenr; -bool leftmost = true; - - ins = rb_entry(node, struct btrfs_delayed_ref_head, href_node); - bytenr = ins->bytenr; -while (*p) { - parent_node = *p; - entry = rb_entry(parent_node, struct btrfs_delayed_ref_head, - href_node); - -if (bytenr < entry->bytenr) { - p = &(*p)->rb_left; - }else if (bytenr > entry->bytenr) { - p = &(*p)->rb_right; - leftmost = false; - }else { -return entry; - } - } - -rb_link_node (node, parent_node, p); -rb_insert_color_cached (node, root, leftmost); -return NULL ; -} -static struct btrfs_delayed_ref_node *tree_insert (struct rb_root_cached *root,struct btrfs_delayed_ref_node *ins) {@@ -381,18 +348,11 @@ static struct btrfs_delayed_ref_node* tree_insert(struct rb_root_cached *root,static struct btrfs_delayed_ref_head *find_first_ref_head (struct btrfs_delayed_ref_root *dr) { -struct rb_node *n; -struct btrfs_delayed_ref_head *entry; +unsigned long from =0 ;lockdep_assert_held (&dr->lock); - n =rb_first_cached (&dr->href_root); -if (!n) -return NULL ; - - entry = rb_entry(n, struct btrfs_delayed_ref_head, href_node); - -return entry; +return xa_find (&dr->head_refs, &from,ULONG_MAX ,XA_PRESENT ); }/* @@ -405,35 +365,22 @@ static struct btrfs_delayed_ref_head *find_ref_head( struct btrfs_delayed_ref_root *dr, u64 bytenr, bool return_bigger) { - struct rb_root *root = &dr->href_root.rb_root; -struct rb_node *n; + const unsigned long target_index = (bytenr >> fs_info->sectorsize_bits); +unsigned long found_index = target_index;struct btrfs_delayed_ref_head *entry;lockdep_assert_held (&dr->lock); - n = root->rb_node; - entry =NULL ; -while (n) { - entry = rb_entry(n, struct btrfs_delayed_ref_head, href_node); + entry =xa_find (&dr->head_refs, &found_index,ULONG_MAX ,XA_PRESENT ); +if (!entry) +return NULL ; + +ASSERT (found_index >= target_index); -if (bytenr < entry->bytenr) - n = n->rb_left; -else if (bytenr > entry->bytenr) - n = n->rb_right; -else -return entry; - } -if (entry && return_bigger) { -if (bytenr > entry->bytenr) { - n =rb_next (&entry->href_node); -if (!n) -return NULL ; - entry = rb_entry(n, struct btrfs_delayed_ref_head, - href_node); - } -return entry; - } -return NULL ; +if (found_index != target_index && !return_bigger) +return NULL ; + +return entry; } static bool btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,@@ -448,7 +395,7 @@ static bool btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,mutex_lock (&head->mutex);spin_lock (&delayed_refs->lock); -if (RB_EMPTY_NODE (&head->href_node)) { +if (!head->tracked) {mutex_unlock (&head->mutex);btrfs_put_delayed_ref_head (head);return false;@@ -567,35 +514,27 @@ struct btrfs_delayed_ref_head *btrfs_select_ref_head( struct btrfs_delayed_ref_root *delayed_refs) {struct btrfs_delayed_ref_head *head; +unsigned long start_index; +unsigned long found_index; +bool found_head = false;bool locked;spin_lock (&delayed_refs->lock); again: - head =find_ref_head (fs_info, delayed_refs, - delayed_refs->run_delayed_start, true); -if (!head && delayed_refs->run_delayed_start !=0 ) { - delayed_refs->run_delayed_start =0 ; - head =find_first_ref_head (delayed_refs); - } -if (!head) { -spin_unlock (&delayed_refs->lock); -return NULL ; + start_index = (delayed_refs->run_delayed_start >> fs_info->sectorsize_bits); +xa_for_each_start (&delayed_refs->head_refs, found_index, head, start_index) { +if (!head->processing) { + found_head = true; +break ; + } } - -while (head->processing) { -struct rb_node *node; - - node =rb_next (&head->href_node); -if (!node) { -if (delayed_refs->run_delayed_start ==0 ) { -spin_unlock (&delayed_refs->lock); -return NULL ; - } - delayed_refs->run_delayed_start =0 ; - goto again; +if (!found_head) { +if (delayed_refs->run_delayed_start ==0 ) { +spin_unlock (&delayed_refs->lock); +return NULL ; } - head = rb_entry(node, struct btrfs_delayed_ref_head, - href_node); + delayed_refs->run_delayed_start =0 ; + goto again; } head->processing = true;@@ -632,11 +571,13 @@ void btrfs_delete_ref_head(struct btrfs_fs_info *fs_info, struct btrfs_delayed_ref_root *delayed_refs, struct btrfs_delayed_ref_head *head) { +const unsigned long index = (head->bytenr >> fs_info->sectorsize_bits); +lockdep_assert_held (&delayed_refs->lock);lockdep_assert_held (&head->lock); -rb_erase_cached (&head->href_node, &delayed_refs->href_root); -RB_CLEAR_NODE (&head->href_node); +xa_erase (&delayed_refs->head_refs, index); + head->tracked = false; delayed_refs->num_heads--;if (!head->processing) delayed_refs->num_heads_ready--;@@ -845,7 +786,7 @@ static void init_delayed_ref_head(struct btrfs_delayed_ref_head *head_ref, head_ref->is_system = (generic_ref->ref_root ==BTRFS_CHUNK_TREE_OBJECTID ); head_ref->ref_tree =RB_ROOT_CACHED ;INIT_LIST_HEAD (&head_ref->ref_add_list); -RB_CLEAR_NODE (&head_ref->href_node); + head_ref->tracked = false; head_ref->processing = false; head_ref->total_ref_mod = count_mod;spin_lock_init (&head_ref->lock);@@ -883,11 +824,24 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,struct btrfs_fs_info *fs_info = trans->fs_info;struct btrfs_delayed_ref_head *existing;struct btrfs_delayed_ref_root *delayed_refs; +const unsigned long index = (head_ref->bytenr >> fs_info->sectorsize_bits);bool qrecord_inserted = false; delayed_refs = &trans->transaction->delayed_refs;lockdep_assert_held (&delayed_refs->lock); +#if BITS_PER_LONG ==32 +if (head_ref->bytenr >=MAX_LFS_FILESIZE ) { +if (qrecord) +xa_release (&delayed_refs->dirty_extents, index); +btrfs_err_rl (fs_info, +"delayed ref head %llu is beyond 32bit page cache and xarray index limit" , + head_ref->bytenr); +btrfs_err_32bit_limit (fs_info); +return ERR_PTR (-EOVERFLOW ); + } +#endif +/* Record qgroup extent info if provided */ if (qrecord) {int ret;@@ -896,8 +850,7 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans, head_ref->bytenr);if (ret) {/* Clean up if insertion fails or item exists. */ -xa_release (&delayed_refs->dirty_extents, - head_ref->bytenr >> fs_info->sectorsize_bits); +xa_release (&delayed_refs->dirty_extents, index);/* Caller responsible for freeing qrecord on error. */ if (ret <0 )return ERR_PTR (ret);@@ -909,8 +862,7 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,trace_add_delayed_ref_head (fs_info, head_ref, action); - existing =htree_insert (&delayed_refs->href_root, - &head_ref->href_node); + existing =xa_load (&delayed_refs->head_refs, index);if (existing) {update_existing_head_ref (trans, existing, head_ref);/* @@ -920,6 +872,19 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,kmem_cache_free (btrfs_delayed_ref_head_cachep, head_ref); head_ref = existing; }else { + existing =xa_store (&delayed_refs->head_refs, index, head_ref,GFP_ATOMIC ); +if (xa_is_err (existing)) { +/* Memory was preallocated by the caller. */ +ASSERT (xa_err (existing) != -ENOMEM ); +return ERR_CAST (existing); + }else if (WARN_ON (existing)) { +/* +* Shouldn't happen we just did a lookup before under +* delayed_refs->lock. +*/ +return ERR_PTR (-EEXIST ); + } + head_ref->tracked = true;/* * We reserve the amount of bytes needed to delete csums when * adding the ref head and not when adding individual drop refs @@ -1040,6 +1005,8 @@ static int add_delayed_ref(struct btrfs_trans_handle *trans,struct btrfs_delayed_ref_head *new_head_ref;struct btrfs_delayed_ref_root *delayed_refs;struct btrfs_qgroup_extent_record *record =NULL ; +const unsigned long index = (generic_ref->bytenr >> fs_info->sectorsize_bits); +bool qrecord_reserved = false;bool qrecord_inserted;int action = generic_ref->action;bool merged;@@ -1055,25 +1022,32 @@ static int add_delayed_ref(struct btrfs_trans_handle *trans, goto free_node; } + delayed_refs = &trans->transaction->delayed_refs; +if (btrfs_qgroup_full_accounting (fs_info) && !generic_ref->skip_qgroup) { record =kzalloc (sizeof (*record),GFP_NOFS );if (!record) { ret = -ENOMEM ; goto free_head_ref; } -if (xa_reserve (&trans->transaction->delayed_refs.dirty_extents, - generic_ref->bytenr >> fs_info->sectorsize_bits, -GFP_NOFS )) { +if (xa_reserve (&delayed_refs->dirty_extents, index,GFP_NOFS )) { ret = -ENOMEM ; goto free_record; } + qrecord_reserved = true; + } + + ret =xa_reserve (&delayed_refs->head_refs, index,GFP_NOFS ); +if (ret) { +if (qrecord_reserved) +xa_release (&delayed_refs->dirty_extents, index); + goto free_record; }init_delayed_ref_common (fs_info, node, generic_ref);init_delayed_ref_head (head_ref, generic_ref, record, reserved); head_ref->extent_op = extent_op; - delayed_refs = &trans->transaction->delayed_refs;spin_lock (&delayed_refs->lock);/* @@ -1083,6 +1057,7 @@ static int add_delayed_ref(struct btrfs_trans_handle *trans, new_head_ref =add_delayed_ref_head (trans, head_ref, record, action, &qrecord_inserted);if (IS_ERR (new_head_ref)) { +xa_release (&delayed_refs->head_refs, index);spin_unlock (&delayed_refs->lock); ret =PTR_ERR (new_head_ref); goto free_record;@@ -1145,6 +1120,7 @@ int btrfs_add_delayed_extent_op(struct btrfs_trans_handle *trans, u64 bytenr, u64 num_bytes, u8 level, struct btrfs_delayed_extent_op *extent_op) { + const unsigned long index = (bytenr >> trans->fs_info->sectorsize_bits);struct btrfs_delayed_ref_head *head_ref;struct btrfs_delayed_ref_head *head_ref_ret;struct btrfs_delayed_ref_root *delayed_refs;@@ -1155,6 +1131,7 @@ int btrfs_add_delayed_extent_op(struct btrfs_trans_handle *trans, .num_bytes = num_bytes, .tree_ref.level = level, }; +int ret; head_ref =kmem_cache_alloc (btrfs_delayed_ref_head_cachep,GFP_NOFS );if (!head_ref)@@ -1164,16 +1141,23 @@ int btrfs_add_delayed_extent_op(struct btrfs_trans_handle *trans, head_ref->extent_op = extent_op; delayed_refs = &trans->transaction->delayed_refs; -spin_lock (&delayed_refs->lock); + ret =xa_reserve (&delayed_refs->head_refs, index,GFP_NOFS ); +if (ret) { +kmem_cache_free (btrfs_delayed_ref_head_cachep, head_ref); +return ret; + } + +spin_lock (&delayed_refs->lock); head_ref_ret =add_delayed_ref_head (trans, head_ref,NULL ,BTRFS_UPDATE_DELAYED_HEAD ,NULL ); -spin_unlock (&delayed_refs->lock); -if (IS_ERR (head_ref_ret)) { +xa_release (&delayed_refs->head_refs, index); +spin_unlock (&delayed_refs->lock);kmem_cache_free (btrfs_delayed_ref_head_cachep, head_ref);return PTR_ERR (head_ref_ret); } +spin_unlock (&delayed_refs->lock);/* * Need to update the delayed_refs_rsv with any changes we may have fs/btrfs/delayed-ref.h +5
-6@@ -122,12 +122,6 @@ struct btrfs_delayed_extent_op {struct btrfs_delayed_ref_head {u64 bytenr;u64 num_bytes; -/* -* For insertion into struct btrfs_delayed_ref_root::href_root. -* Keep it in the same cache line as 'bytenr' for more efficient -* searches in the rbtree. -*/ -struct rb_node href_node;/* * the mutex is held while running the refs, and it is also * held when checking the sum of reference modifications. @@ -191,6 +185,11 @@ struct btrfs_delayed_ref_head {bool is_data;bool is_system;bool processing; +/* +* Indicate if it's currently in the data structure that tracks head +* refs (struct btrfs_delayed_ref_root::head_refs). +*/ +bool tracked; };enum btrfs_delayed_ref_flags {@@ -199,22 +198,27 @@ enum btrfs_delayed_ref_flags { };
fs/btrfs/delayed-ref.h enum btrfs_delayed_ref_flags { · line 204
Quoted 10 lines
fs/btrfs/delayed-ref.h +1
-4struct btrfs_delayed_ref_root { -/* head ref rbtree */ -struct rb_root_cached href_root; -/* -* Track dirty extent records. +* Track head references. * The keys correspond to the logical address of the extent ("bytenr") * right shifted by fs_info->sectorsize_bits. This is both to get a more
This comment is great.
I also think a named function or macro computing the index would be beneficial.
Quoted 60 lines
fs/btrfs/delayed-ref.h +9
-1* dense index space (optimizes xarray structure) and because indexes in * xarrays are of "unsigned long" type, meaning they are 32 bits wide on * 32 bits platforms, limiting the extent range to 4G which is too low * and makes it unusable (truncated index values) on 32 bits platforms. +* Protected by the spinlock 'lock' defined below. +*/ +struct xarray head_refs; + +/* +* Track dirty extent records. +* The keys correspond to the logical address of the extent ("bytenr") +* right shifted by fs_info->sectorsize_bits, for same reasons as above. */ struct xarray dirty_extents;/* -* Protects the rbtree href_root, its entries and the following fields: +* Protects the xarray head_refs, its entries and the following fields: * num_heads, num_heads_ready, pending_csums and run_delayed_start. */ spinlock_t lock;fs/btrfs/extent-tree.c +1
-1@@ -2176,7 +2176,7 @@ int btrfs_run_delayed_refs(struct btrfs_trans_handle *trans, u64 min_bytes)btrfs_create_pending_block_groups (trans);spin_lock (&delayed_refs->lock); -if (RB_EMPTY_ROOT (&delayed_refs->href_root.rb_root)) { +if (xa_empty (&delayed_refs->head_refs)) {spin_unlock (&delayed_refs->lock);return 0 ; }fs/btrfs/transaction.c +2
-3@@ -141,8 +141,7 @@ void btrfs_put_transaction(struct btrfs_transaction *transaction)WARN_ON (refcount_read (&transaction->use_count) ==0 );if (refcount_dec_and_test (&transaction->use_count)) {BUG_ON (!list_empty (&transaction->list)); -WARN_ON (!RB_EMPTY_ROOT ( - &transaction->delayed_refs.href_root.rb_root)); +WARN_ON (!xa_empty (&transaction->delayed_refs.head_refs));WARN_ON (!xa_empty (&transaction->delayed_refs.dirty_extents));if (transaction->delayed_refs.pending_csums) btrfs_err(transaction->fs_info,@@ -349,7 +348,7 @@ static noinline int join_transaction(struct btrfs_fs_info *fs_info,memset (&cur_trans->delayed_refs,0 ,sizeof (cur_trans->delayed_refs)); - cur_trans->delayed_refs.href_root =RB_ROOT_CACHED ; +xa_init (&cur_trans->delayed_refs.head_refs);xa_init (&cur_trans->delayed_refs.dirty_extents);/* Signature · 1 line
2.43.0
Re: [PATCH 17/18] btrfs: track delayed ref heads in an xarray
Quoted 27 lines · Boris Burkov
Quoted 12 lines · On Thu, Oct 24, 2024 at 05:24:25PM +0100, [email protected] wrote:
From: Filipe Manana <[email protected]>
Currently we use a red black tree (rb-tree) to track the delayed ref heads (in struct
btrfs_delayed_ref_root::href_root). This however is not very efficient when the number of delayed ref heads is large (and it's very common to be at least in the order of thousands) since rb-trees are binary trees. For example for 10K delayed ref heads, the tree has a depth of 13. Besides that, inserting into the tree requires navigating through it and pulling useless cache lines in the process since the red black tree nodes are embedded within the delayed ref head structure - on the other hand, by being embedded, it requires no extra memory allocations.Quoted 12 lines
We can improve this by using an xarray instead which has a much higher branching factor than a red black tree (binary balanced tree) and is more cache friendly and behaves like a resizable array, with a much better search and insertion complexity than a red black tree. This only has one small disadvantage which is that insertion will sometimes require allocating memory for the xarray - which may fail (not that often since it uses a
kmem_cache) - but on the other hand we can reduce the delayed ref head structure size by 24 bytes (from 152 down to 128 bytes) after removing the embedded red black tree node, meaning than we can now fit 32 delayed ref heads per 4K page instead of 26, and that gain compensates for the occasional memory allocations needed for the xarray nodes. We also end up using only 2 cache lines instead of 3 per delayed ref head.
Quoted 7 lines
The explanation makes sense to me, and I don't think the new allocation is particularly risky, since the paths calling
add_delayed_ref_headare already allocating and can return ENOMEM.With that said, just curious, have you tried hammering this under memory pressure? Have you been able to create conditions where the new allocation fails?
I haven't been able to, but I haven't tried hard for that either. It's as likely to happen as for other (critical) places where we use xarrays or radix trees (like the one to track extent buffers).
Thanks.
Quoted 520 lines
Quoted 444 lines
Running the following
fs_marktest showed some improvements:$ cat test.sh #!/bin/bashDEV=/dev/nullb0 MNT=/mnt/nullb0 MOUNT_OPTIONS="-o ssd" FILES=100000 THREADS=$(nproc --all) echo "performance" | \ tee /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor mkfs.btrfs -f $DEV mount $MOUNT_OPTIONS $DEV $MNT OPTS="-S 0 -L 5 -n $FILES -s 0 -t $THREADS -k" for ((i = 1; i <= $THREADS; i++)); do OPTS="$OPTS -d $MNT/d$i" done fs_mark $OPTS umount $MNTBefore this patch:
FSUse% Count Size Files/sec App Overhead 10 1200000 0 171845.7 12253839 16 2400000 0 230898.7 12308254 23 3600000 0 212292.9 12467768 30 4800000 0 195737.8 12627554 46 6000000 0 171055.2 12783329After this patch:
FSUse% Count Size Files/sec App Overhead 10 1200000 0 173835.0 12246131 16 2400000 0 233537.8 12271746 23 3600000 0 220398.7 12307737 30 4800000 0 204483.6 12392318 40 6000000 0 182923.3 12771843Signed-off-by Filipe Manana <[email protected]>--- fs/btrfs/delayed-ref.c | 192 +++++++++++++++++++---------------------- fs/btrfs/delayed-ref.h | 26 +++--- fs/btrfs/extent-tree.c | 2 +- fs/btrfs/transaction.c | 5 +- 4 files changed, 106 insertions(+), 119 deletions(-)fs/btrfs/delayed-ref.c +88
-104@@ -314,39 +314,6 @@ static int comp_refs(struct btrfs_delayed_ref_node *ref1,return 0 ; } -/* insert a new ref to head ref rbtree */ -static struct btrfs_delayed_ref_head *htree_insert (struct rb_root_cached *root, -struct rb_node *node) -{ -struct rb_node **p = &root->rb_root.rb_node; -struct rb_node *parent_node =NULL ; -struct btrfs_delayed_ref_head *entry; -struct btrfs_delayed_ref_head *ins; -u64 bytenr; -bool leftmost = true; - - ins = rb_entry(node, struct btrfs_delayed_ref_head, href_node); - bytenr = ins->bytenr; -while (*p) { - parent_node = *p; - entry = rb_entry(parent_node, struct btrfs_delayed_ref_head, - href_node); - -if (bytenr < entry->bytenr) { - p = &(*p)->rb_left; - }else if (bytenr > entry->bytenr) { - p = &(*p)->rb_right; - leftmost = false; - }else { -return entry; - } - } - -rb_link_node (node, parent_node, p); -rb_insert_color_cached (node, root, leftmost); -return NULL ; -} -static struct btrfs_delayed_ref_node *tree_insert (struct rb_root_cached *root,struct btrfs_delayed_ref_node *ins) {@@ -381,18 +348,11 @@ static struct btrfs_delayed_ref_node* tree_insert(struct rb_root_cached *root,static struct btrfs_delayed_ref_head *find_first_ref_head (struct btrfs_delayed_ref_root *dr) { -struct rb_node *n; -struct btrfs_delayed_ref_head *entry; +unsigned long from =0 ;lockdep_assert_held (&dr->lock); - n =rb_first_cached (&dr->href_root); -if (!n) -return NULL ; - - entry = rb_entry(n, struct btrfs_delayed_ref_head, href_node); - -return entry; +return xa_find (&dr->head_refs, &from,ULONG_MAX ,XA_PRESENT ); }/* @@ -405,35 +365,22 @@ static struct btrfs_delayed_ref_head *find_ref_head( struct btrfs_delayed_ref_root *dr, u64 bytenr, bool return_bigger) { - struct rb_root *root = &dr->href_root.rb_root; -struct rb_node *n; + const unsigned long target_index = (bytenr >> fs_info->sectorsize_bits); +unsigned long found_index = target_index;struct btrfs_delayed_ref_head *entry;lockdep_assert_held (&dr->lock); - n = root->rb_node; - entry =NULL ; -while (n) { - entry = rb_entry(n, struct btrfs_delayed_ref_head, href_node); + entry =xa_find (&dr->head_refs, &found_index,ULONG_MAX ,XA_PRESENT ); +if (!entry) +return NULL ; + +ASSERT (found_index >= target_index); -if (bytenr < entry->bytenr) - n = n->rb_left; -else if (bytenr > entry->bytenr) - n = n->rb_right; -else -return entry; - } -if (entry && return_bigger) { -if (bytenr > entry->bytenr) { - n =rb_next (&entry->href_node); -if (!n) -return NULL ; - entry = rb_entry(n, struct btrfs_delayed_ref_head, - href_node); - } -return entry; - } -return NULL ; +if (found_index != target_index && !return_bigger) +return NULL ; + +return entry; } static bool btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,@@ -448,7 +395,7 @@ static bool btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,mutex_lock (&head->mutex);spin_lock (&delayed_refs->lock); -if (RB_EMPTY_NODE (&head->href_node)) { +if (!head->tracked) {mutex_unlock (&head->mutex);btrfs_put_delayed_ref_head (head);return false;@@ -567,35 +514,27 @@ struct btrfs_delayed_ref_head *btrfs_select_ref_head( struct btrfs_delayed_ref_root *delayed_refs) {struct btrfs_delayed_ref_head *head; +unsigned long start_index; +unsigned long found_index; +bool found_head = false;bool locked;spin_lock (&delayed_refs->lock); again: - head =find_ref_head (fs_info, delayed_refs, - delayed_refs->run_delayed_start, true); -if (!head && delayed_refs->run_delayed_start !=0 ) { - delayed_refs->run_delayed_start =0 ; - head =find_first_ref_head (delayed_refs); - } -if (!head) { -spin_unlock (&delayed_refs->lock); -return NULL ; + start_index = (delayed_refs->run_delayed_start >> fs_info->sectorsize_bits); +xa_for_each_start (&delayed_refs->head_refs, found_index, head, start_index) { +if (!head->processing) { + found_head = true; +break ; + } } - -while (head->processing) { -struct rb_node *node; - - node =rb_next (&head->href_node); -if (!node) { -if (delayed_refs->run_delayed_start ==0 ) { -spin_unlock (&delayed_refs->lock); -return NULL ; - } - delayed_refs->run_delayed_start =0 ; - goto again; +if (!found_head) { +if (delayed_refs->run_delayed_start ==0 ) { +spin_unlock (&delayed_refs->lock); +return NULL ; } - head = rb_entry(node, struct btrfs_delayed_ref_head, - href_node); + delayed_refs->run_delayed_start =0 ; + goto again; } head->processing = true;@@ -632,11 +571,13 @@ void btrfs_delete_ref_head(struct btrfs_fs_info *fs_info, struct btrfs_delayed_ref_root *delayed_refs, struct btrfs_delayed_ref_head *head) { +const unsigned long index = (head->bytenr >> fs_info->sectorsize_bits); +lockdep_assert_held (&delayed_refs->lock);lockdep_assert_held (&head->lock); -rb_erase_cached (&head->href_node, &delayed_refs->href_root); -RB_CLEAR_NODE (&head->href_node); +xa_erase (&delayed_refs->head_refs, index); + head->tracked = false; delayed_refs->num_heads--;if (!head->processing) delayed_refs->num_heads_ready--;@@ -845,7 +786,7 @@ static void init_delayed_ref_head(struct btrfs_delayed_ref_head *head_ref, head_ref->is_system = (generic_ref->ref_root ==BTRFS_CHUNK_TREE_OBJECTID ); head_ref->ref_tree =RB_ROOT_CACHED ;INIT_LIST_HEAD (&head_ref->ref_add_list); -RB_CLEAR_NODE (&head_ref->href_node); + head_ref->tracked = false; head_ref->processing = false; head_ref->total_ref_mod = count_mod;spin_lock_init (&head_ref->lock);@@ -883,11 +824,24 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,struct btrfs_fs_info *fs_info = trans->fs_info;struct btrfs_delayed_ref_head *existing;struct btrfs_delayed_ref_root *delayed_refs; +const unsigned long index = (head_ref->bytenr >> fs_info->sectorsize_bits);bool qrecord_inserted = false; delayed_refs = &trans->transaction->delayed_refs;lockdep_assert_held (&delayed_refs->lock); +#if BITS_PER_LONG ==32 +if (head_ref->bytenr >=MAX_LFS_FILESIZE ) { +if (qrecord) +xa_release (&delayed_refs->dirty_extents, index); +btrfs_err_rl (fs_info, +"delayed ref head %llu is beyond 32bit page cache and xarray index limit" , + head_ref->bytenr); +btrfs_err_32bit_limit (fs_info); +return ERR_PTR (-EOVERFLOW ); + } +#endif +/* Record qgroup extent info if provided */ if (qrecord) {int ret;@@ -896,8 +850,7 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans, head_ref->bytenr);if (ret) {/* Clean up if insertion fails or item exists. */ -xa_release (&delayed_refs->dirty_extents, - head_ref->bytenr >> fs_info->sectorsize_bits); +xa_release (&delayed_refs->dirty_extents, index);/* Caller responsible for freeing qrecord on error. */ if (ret <0 )return ERR_PTR (ret);@@ -909,8 +862,7 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,trace_add_delayed_ref_head (fs_info, head_ref, action); - existing =htree_insert (&delayed_refs->href_root, - &head_ref->href_node); + existing =xa_load (&delayed_refs->head_refs, index);if (existing) {update_existing_head_ref (trans, existing, head_ref);/* @@ -920,6 +872,19 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,kmem_cache_free (btrfs_delayed_ref_head_cachep, head_ref); head_ref = existing; }else { + existing =xa_store (&delayed_refs->head_refs, index, head_ref,GFP_ATOMIC ); +if (xa_is_err (existing)) { +/* Memory was preallocated by the caller. */ +ASSERT (xa_err (existing) != -ENOMEM ); +return ERR_CAST (existing); + }else if (WARN_ON (existing)) { +/* +* Shouldn't happen we just did a lookup before under +* delayed_refs->lock. +*/ +return ERR_PTR (-EEXIST ); + } + head_ref->tracked = true;/* * We reserve the amount of bytes needed to delete csums when * adding the ref head and not when adding individual drop refs @@ -1040,6 +1005,8 @@ static int add_delayed_ref(struct btrfs_trans_handle *trans,struct btrfs_delayed_ref_head *new_head_ref;struct btrfs_delayed_ref_root *delayed_refs;struct btrfs_qgroup_extent_record *record =NULL ; +const unsigned long index = (generic_ref->bytenr >> fs_info->sectorsize_bits); +bool qrecord_reserved = false;bool qrecord_inserted;int action = generic_ref->action;bool merged;@@ -1055,25 +1022,32 @@ static int add_delayed_ref(struct btrfs_trans_handle *trans, goto free_node; } + delayed_refs = &trans->transaction->delayed_refs; +if (btrfs_qgroup_full_accounting (fs_info) && !generic_ref->skip_qgroup) { record =kzalloc (sizeof (*record),GFP_NOFS );if (!record) { ret = -ENOMEM ; goto free_head_ref; } -if (xa_reserve (&trans->transaction->delayed_refs.dirty_extents, - generic_ref->bytenr >> fs_info->sectorsize_bits, -GFP_NOFS )) { +if (xa_reserve (&delayed_refs->dirty_extents, index,GFP_NOFS )) { ret = -ENOMEM ; goto free_record; } + qrecord_reserved = true; + } + + ret =xa_reserve (&delayed_refs->head_refs, index,GFP_NOFS ); +if (ret) { +if (qrecord_reserved) +xa_release (&delayed_refs->dirty_extents, index); + goto free_record; }init_delayed_ref_common (fs_info, node, generic_ref);init_delayed_ref_head (head_ref, generic_ref, record, reserved); head_ref->extent_op = extent_op; - delayed_refs = &trans->transaction->delayed_refs;spin_lock (&delayed_refs->lock);/* @@ -1083,6 +1057,7 @@ static int add_delayed_ref(struct btrfs_trans_handle *trans, new_head_ref =add_delayed_ref_head (trans, head_ref, record, action, &qrecord_inserted);if (IS_ERR (new_head_ref)) { +xa_release (&delayed_refs->head_refs, index);spin_unlock (&delayed_refs->lock); ret =PTR_ERR (new_head_ref); goto free_record;@@ -1145,6 +1120,7 @@ int btrfs_add_delayed_extent_op(struct btrfs_trans_handle *trans, u64 bytenr, u64 num_bytes, u8 level, struct btrfs_delayed_extent_op *extent_op) { + const unsigned long index = (bytenr >> trans->fs_info->sectorsize_bits);struct btrfs_delayed_ref_head *head_ref;struct btrfs_delayed_ref_head *head_ref_ret;struct btrfs_delayed_ref_root *delayed_refs;@@ -1155,6 +1131,7 @@ int btrfs_add_delayed_extent_op(struct btrfs_trans_handle *trans, .num_bytes = num_bytes, .tree_ref.level = level, }; +int ret; head_ref =kmem_cache_alloc (btrfs_delayed_ref_head_cachep,GFP_NOFS );if (!head_ref)@@ -1164,16 +1141,23 @@ int btrfs_add_delayed_extent_op(struct btrfs_trans_handle *trans, head_ref->extent_op = extent_op; delayed_refs = &trans->transaction->delayed_refs; -spin_lock (&delayed_refs->lock); + ret =xa_reserve (&delayed_refs->head_refs, index,GFP_NOFS ); +if (ret) { +kmem_cache_free (btrfs_delayed_ref_head_cachep, head_ref); +return ret; + } + +spin_lock (&delayed_refs->lock); head_ref_ret =add_delayed_ref_head (trans, head_ref,NULL ,BTRFS_UPDATE_DELAYED_HEAD ,NULL ); -spin_unlock (&delayed_refs->lock); -if (IS_ERR (head_ref_ret)) { +xa_release (&delayed_refs->head_refs, index); +spin_unlock (&delayed_refs->lock);kmem_cache_free (btrfs_delayed_ref_head_cachep, head_ref);return PTR_ERR (head_ref_ret); } +spin_unlock (&delayed_refs->lock);/* * Need to update the delayed_refs_rsv with any changes we may have fs/btrfs/delayed-ref.h +5
-6@@ -122,12 +122,6 @@ struct btrfs_delayed_extent_op {struct btrfs_delayed_ref_head {u64 bytenr;u64 num_bytes; -/* -* For insertion into struct btrfs_delayed_ref_root::href_root. -* Keep it in the same cache line as 'bytenr' for more efficient -* searches in the rbtree. -*/ -struct rb_node href_node;/* * the mutex is held while running the refs, and it is also * held when checking the sum of reference modifications. @@ -191,6 +185,11 @@ struct btrfs_delayed_ref_head {bool is_data;bool is_system;bool processing; +/* +* Indicate if it's currently in the data structure that tracks head +* refs (struct btrfs_delayed_ref_root::head_refs). +*/ +bool tracked; };enum btrfs_delayed_ref_flags {@@ -199,22 +198,27 @@ enum btrfs_delayed_ref_flags { };fs/btrfs/delayed-ref.h enum btrfs_delayed_ref_flags { · line 204
Quoted 10 lines
fs/btrfs/delayed-ref.h +1
-4struct btrfs_delayed_ref_root { -/* head ref rbtree */ -struct rb_root_cached href_root; -/* -* Track dirty extent records. +* Track head references. * The keys correspond to the logical address of the extent ("bytenr") * right shifted by fs_info->sectorsize_bits. This is both to get a more This comment is great.
I also think a named function or macro computing the index would be beneficial.
Quoted 60 lines
fs/btrfs/delayed-ref.h +9
-1* dense index space (optimizes xarray structure) and because indexes in * xarrays are of "unsigned long" type, meaning they are 32 bits wide on * 32 bits platforms, limiting the extent range to 4G which is too low * and makes it unusable (truncated index values) on 32 bits platforms. +* Protected by the spinlock 'lock' defined below. +*/ +struct xarray head_refs; + +/* +* Track dirty extent records. +* The keys correspond to the logical address of the extent ("bytenr") +* right shifted by fs_info->sectorsize_bits, for same reasons as above. */ struct xarray dirty_extents;/* -* Protects the rbtree href_root, its entries and the following fields: +* Protects the xarray head_refs, its entries and the following fields: * num_heads, num_heads_ready, pending_csums and run_delayed_start. */ spinlock_t lock;fs/btrfs/extent-tree.c +1
-1@@ -2176,7 +2176,7 @@ int btrfs_run_delayed_refs(struct btrfs_trans_handle *trans, u64 min_bytes)btrfs_create_pending_block_groups (trans);spin_lock (&delayed_refs->lock); -if (RB_EMPTY_ROOT (&delayed_refs->href_root.rb_root)) { +if (xa_empty (&delayed_refs->head_refs)) {spin_unlock (&delayed_refs->lock);return 0 ; }fs/btrfs/transaction.c +2
-4@@ -141,8 +141,7 @@ void btrfs_put_transaction(struct btrfs_transaction *transaction)WARN_ON (refcount_read (&transaction->use_count) ==0 );if (refcount_dec_and_test (&transaction->use_count)) {BUG_ON (!list_empty (&transaction->list)); -WARN_ON (!RB_EMPTY_ROOT ( - &transaction->delayed_refs.href_root.rb_root)); +WARN_ON (!xa_empty (&transaction->delayed_refs.head_refs));WARN_ON (!xa_empty (&transaction->delayed_refs.dirty_extents));if (transaction->delayed_refs.pending_csums) btrfs_err(transaction->fs_info,@@ -349,7 +348,7 @@ static noinline int join_transaction(struct btrfs_fs_info *fs_info,memset (&cur_trans->delayed_refs,0 ,sizeof (cur_trans->delayed_refs)); - cur_trans->delayed_refs.href_root =RB_ROOT_CACHED ; +xa_init (&cur_trans->delayed_refs.head_refs);xa_init (&cur_trans->delayed_refs.dirty_extents);/* -- 2.43.0
Re: [PATCH 17/18] btrfs: track delayed ref heads in an xarray
In reply to Boris BurkovQuoted 26 lines · Boris Burkov
Quoted 12 lines · On Thu, Oct 24, 2024 at 05:24:25PM +0100, [email protected] wrote:
From: Filipe Manana <[email protected]>
Currently we use a red black tree (rb-tree) to track the delayed ref heads (in struct
btrfs_delayed_ref_root::href_root). This however is not very efficient when the number of delayed ref heads is large (and it's very common to be at least in the order of thousands) since rb-trees are binary trees. For example for 10K delayed ref heads, the tree has a depth of 13. Besides that, inserting into the tree requires navigating through it and pulling useless cache lines in the process since the red black tree nodes are embedded within the delayed ref head structure - on the other hand, by being embedded, it requires no extra memory allocations.Quoted 12 lines
We can improve this by using an xarray instead which has a much higher branching factor than a red black tree (binary balanced tree) and is more cache friendly and behaves like a resizable array, with a much better search and insertion complexity than a red black tree. This only has one small disadvantage which is that insertion will sometimes require allocating memory for the xarray - which may fail (not that often since it uses a
kmem_cache) - but on the other hand we can reduce the delayed ref head structure size by 24 bytes (from 152 down to 128 bytes) after removing the embedded red black tree node, meaning than we can now fit 32 delayed ref heads per 4K page instead of 26, and that gain compensates for the occasional memory allocations needed for the xarray nodes. We also end up using only 2 cache lines instead of 3 per delayed ref head.
Quoted 7 lines
The explanation makes sense to me, and I don't think the new allocation is particularly risky, since the paths calling
add_delayed_ref_headare already allocating and can return ENOMEM.With that said, just curious, have you tried hammering this under memory pressure? Have you been able to create conditions where the new allocation fails?
Under normal condtions this will not fail as it's using GFP_NOFS which still acts as no-fail. It could fail on a system with configured cgroup memory limits and syzbot sometimes does that. But as long as the error is handled we're fine.
PATCH 18/18 btrfs: remove no longer used delayed ref head search functionality
In reply to [email protected]From: Filipe Manana <[email protected]>
After the previous patch, which converted the rb-tree used to track delayed ref heads into an xarray, the find_ref_head() function is now used only by one caller which always passes false to the 'return_bigger' argument. So remove the 'return_bigger' logic, simplifying the function, and move all the function code to the single caller.
--- fs/btrfs/delayed-ref.c | 34 +++++----------------------------- 1 file changed, 5 insertions(+), 29 deletions(-)
fs/btrfs/delayed-ref.c +5 -29
@@ -355,34 +355,6 @@ static struct btrfs_delayed_ref_head *find_first_ref_head(return xa_find (&dr->head_refs, &from,ULONG_MAX ,XA_PRESENT ); } -/* -* Find a head entry based on bytenr. This returns the delayed ref head if it -* was able to find one, or NULL if nothing was in that spot. If return_bigger -* is given, the next bigger entry is returned if no exact match is found. -*/ -static struct btrfs_delayed_ref_head *find_ref_head ( -struct btrfs_fs_info *fs_info, -struct btrfs_delayed_ref_root *dr,u64 bytenr, -bool return_bigger) -{ -const unsigned long target_index = (bytenr >> fs_info->sectorsize_bits); -unsigned long found_index = target_index; -struct btrfs_delayed_ref_head *entry; - -lockdep_assert_held (&dr->lock); - - entry =xa_find (&dr->head_refs, &found_index,ULONG_MAX ,XA_PRESENT ); -if (!entry) -return NULL ; - -ASSERT (found_index >= target_index); - -if (found_index != target_index && !return_bigger) -return NULL ; - -return entry; -} -static bool btrfs_delayed_ref_lock (struct btrfs_delayed_ref_root *delayed_refs,struct btrfs_delayed_ref_head *head) {
@@ -1184,7 +1156,11 @@ btrfs_find_delayed_ref_head(struct btrfs_fs_info *fs_info, struct btrfs_delayed_ref_root *delayed_refs, u64 bytenr) { - return find_ref_head(fs_info, delayed_refs, bytenr, false); +const unsigned long index = (bytenr >> fs_info->sectorsize_bits); + +lockdep_assert_held (&delayed_refs->lock); + +return xa_load (&delayed_refs->head_refs, index); }static int find_comp (struct btrfs_delayed_ref_node *entry,u64 root,u64 parent)
Signature · 1 line
2.43.0
Quoted 7 lines · On Thu, Oct 24, 2024 at 05:24:08PM +0100, [email protected] wrote:
From: Filipe Manana <[email protected]>
This converts the rb-tree that tracks delayed ref heads into an xarray, reducing memory used by delayed ref heads and making it more efficient to add/remove/find delayed ref heads. The rest are mostly cleanups and refactorings, removing some dead code, deduplicating code, move code around, etc. More details in the changelogs.
The cleanup patches all look perfectly reasonable to me, and the risks (new tracked variable, new allocation) with the xarray patches seem well considered.
Thanks for making this improvement, I think xarray is a good fit for delayed refs.
Quoted 33 lines
Filipe Manana (18):
btrfs: removeBUG_ON()atbtrfs_destroy_delayed_refs()
btrfs: movebtrfs_destroy_delayed_refs()todelayed-ref.c
btrfs: removefs_infoparameter frombtrfs_destroy_delayed_refs()
btrfs: removefs_infoparameter frombtrfs_cleanup_one_transaction()
btrfs: remove duplicated code to drop delayed ref during transaction abort
btrfs: use helper to find first ref head atbtrfs_destroy_delayed_refs()
btrfs: removenum_entriesatomic counter from delayed ref root
btrfs: change return type ofbtrfs_delayed_ref_lock()to boolean
btrfs: simplify obtaining a delayed ref head
btrfs: move delayed ref head unselection todelayed-ref.c
btrfs: passfs_infoto functions that search for delayed ref heads
btrfs: passfs_infotobtrfs_cleanup_ref_head_accounting
btrfs: assert delayed refs lock is held atfind_ref_head()
btrfs: assert delayed refs lock is held atfind_first_ref_head()
btrfs: assert delayed refs lock is held atadd_delayed_ref_head()
btrfs: add comments regarding locking to structbtrfs_delayed_ref_root
btrfs: track delayed ref heads in an xarray
btrfs: remove no longer used delayed ref head search functionalityfs/btrfs/backref.c | 3 +- fs/btrfs/delayed-ref.c | 319 +++++++++++++++++++++++++---------------- fs/btrfs/delayed-ref.h | 61 +++++--- fs/btrfs/disk-io.c | 79 +--------- fs/btrfs/disk-io.h | 3 +- fs/btrfs/extent-tree.c | 69 ++------- fs/btrfs/transaction.c | 8 +- 7 files changed, 256 insertions(+), 286 deletions(-)Signature · 1 line
2.43.0
Quoted 7 lines · On 24.10.24 18:24, [email protected] wrote:
From: Filipe Manana <[email protected]>
This converts the rb-tree that tracks delayed ref heads into an xarray, reducing memory used by delayed ref heads and making it more efficient to add/remove/find delayed ref heads. The rest are mostly cleanups and refactorings, removing some dead code, deduplicating code, move code around, etc. More details in the changelogs.
Stupid question (and by that I literally mean, it's a stupid question, I have no idea): looking at other places where we're heavily relying on rb-trees is ordered-extents. Would it make sense to move them over to xarrays as well?
Quoted 10 lines · Johannes Thumshirn
Quoted 7 lines · On 24.10.24 18:24, [email protected] wrote:
From: Filipe Manana <[email protected]>
This converts the rb-tree that tracks delayed ref heads into an xarray, reducing memory used by delayed ref heads and making it more efficient to add/remove/find delayed ref heads. The rest are mostly cleanups and refactorings, removing some dead code, deduplicating code, move code around, etc. More details in the changelogs.
Quoted 4 lines
Stupid question (and by that I literally mean, it's a stupid question, I have no idea): looking at other places where we're heavily relying on rb-trees is ordered-extents. Would it make sense to move them over to xarrays as well?
For ordered extents I wouldn't consider it, because I don't think it's common to have thousands of them per inode.
Same for delayed refs inside a delayed ref head for example. For delayed ref heads, for every cow operation we get one to delete the old extent and another one for the new extent, so these can easily be thousands even for small filesystems with moderate and even low workloads.
It may still be worth just to reduce structure sizes and memory usage, though it would have to be analyzed on a case by case basis.
Quoted 25 lines · Filipe Manana
Quoted 10 lines · Johannes Thumshirn
Quoted 7 lines · On 24.10.24 18:24, [email protected] wrote:
From: Filipe Manana <[email protected]>
This converts the rb-tree that tracks delayed ref heads into an xarray, reducing memory used by delayed ref heads and making it more efficient to add/remove/find delayed ref heads. The rest are mostly cleanups and refactorings, removing some dead code, deduplicating code, move code around, etc. More details in the changelogs.
Quoted 4 lines
Stupid question (and by that I literally mean, it's a stupid question, I have no idea): looking at other places where we're heavily relying on rb-trees is ordered-extents. Would it make sense to move them over to xarrays as well?
For ordered extents I wouldn't consider it, because I don't think it's common to have thousands of them per inode.
Same for delayed refs inside a delayed ref head for example. For delayed ref heads, for every cow operation we get one to delete the old extent and another one for the new extent, so these can easily be thousands even for small filesystems with moderate and even low workloads.
Quoted 3 lines
It may still be worth just to reduce structure sizes and memory usage, though it would have to be analyzed on a case by case basis.
Thanks for the info :)
Quoted 25 lines · Filipe Manana
Quoted 10 lines · Johannes Thumshirn
Quoted 7 lines · On 24.10.24 18:24, [email protected] wrote:
From: Filipe Manana <[email protected]>
This converts the rb-tree that tracks delayed ref heads into an xarray, reducing memory used by delayed ref heads and making it more efficient to add/remove/find delayed ref heads. The rest are mostly cleanups and refactorings, removing some dead code, deduplicating code, move code around, etc. More details in the changelogs.
Quoted 4 lines
Stupid question (and by that I literally mean, it's a stupid question, I have no idea): looking at other places where we're heavily relying on rb-trees is ordered-extents. Would it make sense to move them over to xarrays as well?
For ordered extents I wouldn't consider it, because I don't think it's common to have thousands of them per inode.
Same for delayed refs inside a delayed ref head for example. For delayed ref heads, for every cow operation we get one to delete the old extent and another one for the new extent, so these can easily be thousands even for small filesystems with moderate and even low workloads.
Quoted 3 lines
It may still be worth just to reduce structure sizes and memory usage, though it would have to be analyzed on a case by case basis.
Another question related to this is, if we switch ordered extent or extent map to XArray, how do we find such structure that covers a bytenr?
For delayed ref and extent buffer (which uses radix tree) we are working with the exact bytenr, but for OE/EM we do a lot of search using a bytenr.
Or do I miss some XArray feature that can do that?
Thanks,
Qu
Quoted 29 lines · Qu Wenruo
Quoted 25 lines · Filipe Manana
Quoted 10 lines · Johannes Thumshirn
Quoted 7 lines · On 24.10.24 18:24, [email protected] wrote:
From: Filipe Manana <[email protected]>
This converts the rb-tree that tracks delayed ref heads into an xarray, reducing memory used by delayed ref heads and making it more efficient to add/remove/find delayed ref heads. The rest are mostly cleanups and refactorings, removing some dead code, deduplicating code, move code around, etc. More details in the changelogs.
Quoted 4 lines
Stupid question (and by that I literally mean, it's a stupid question, I have no idea): looking at other places where we're heavily relying on rb-trees is ordered-extents. Would it make sense to move them over to xarrays as well?
For ordered extents I wouldn't consider it, because I don't think it's common to have thousands of them per inode.
Same for delayed refs inside a delayed ref head for example. For delayed ref heads, for every cow operation we get one to delete the old extent and another one for the new extent, so these can easily be thousands even for small filesystems with moderate and even low workloads.
Quoted 6 lines
Quoted 3 lines
It may still be worth just to reduce structure sizes and memory usage, though it would have to be analyzed on a case by case basis.
Another question related to this is, if we switch ordered extent or extent map to XArray, how do we find such structure that covers a bytenr?
You don't, not without doing something like xa_for_each() and iterate the xarray until either:
1) we find a matching entry (within the ragne of an element in the xarray);
2) we find the first entry that starts beyond the offset/range we are looking for and stop, meaning there's no entry covering the range we want;
3) we reach the end of the array.
The rbtree based search is more practical for that.
Quoted 5 lines
For delayed ref and extent buffer (which uses radix tree) we are working with the exact bytenr, but for OE/EM we do a lot of search using a bytenr.
Or do I miss some XArray feature that can do that?
There isn't any. There are ranges for xarray but they basically mean having a range of indexes point to the same value, which doesn't help in these cases.
For extent maps and states for example, beside the range search, there's also the detail of merging adjacent entries, which is not doable in a practical and efficient way with xarrays, especially to find the previous entry.
Quoted 3 lines
Thanks,
Qu
Quoted 19 lines · On Thu, Oct 24, 2024 at 05:24:08PM +0100, [email protected] wrote:
From: Filipe Manana <[email protected]>
This converts the rb-tree that tracks delayed ref heads into an xarray, reducing memory used by delayed ref heads and making it more efficient to add/remove/find delayed ref heads. The rest are mostly cleanups and refactorings, removing some dead code, deduplicating code, move code around, etc. More details in the changelogs.
Filipe Manana (18):
btrfs: removeBUG_ON()atbtrfs_destroy_delayed_refs()
btrfs: movebtrfs_destroy_delayed_refs()todelayed-ref.c
btrfs: removefs_infoparameter frombtrfs_destroy_delayed_refs()
btrfs: removefs_infoparameter frombtrfs_cleanup_one_transaction()
btrfs: remove duplicated code to drop delayed ref during transaction abort
btrfs: use helper to find first ref head atbtrfs_destroy_delayed_refs()
btrfs: removenum_entriesatomic counter from delayed ref root
btrfs: change return type ofbtrfs_delayed_ref_lock()to boolean
btrfs: simplify obtaining a delayed ref head
btrfs: move delayed ref head unselection todelayed-ref.c
Quoted 8 lines
btrfs: pass
fs_infoto functions that search for delayed ref heads
btrfs: passfs_infotobtrfs_cleanup_ref_head_accounting
btrfs: assert delayed refs lock is held atfind_ref_head()
btrfs: assert delayed refs lock is held atfind_first_ref_head()
btrfs: assert delayed refs lock is held atadd_delayed_ref_head()
btrfs: add comments regarding locking to structbtrfs_delayed_ref_root
btrfs: track delayed ref heads in an xarray
btrfs: remove no longer used delayed ref head search functionality
Thank you, nice cleanups and I like another conversion to xarray.
Quoted 7 lines · 在 2024/10/25 02:54, [email protected] 写道:
From: Filipe Manana <[email protected]>
This converts the rb-tree that tracks delayed ref heads into an xarray, reducing memory used by delayed ref heads and making it more efficient to add/remove/find delayed ref heads. The rest are mostly cleanups and refactorings, removing some dead code, deduplicating code, move code around, etc. More details in the changelogs.
Thanks,
Qu
Quoted 30 lines
Filipe Manana (18):
btrfs: removeBUG_ON()atbtrfs_destroy_delayed_refs()
btrfs: movebtrfs_destroy_delayed_refs()todelayed-ref.c
btrfs: removefs_infoparameter frombtrfs_destroy_delayed_refs()
btrfs: removefs_infoparameter frombtrfs_cleanup_one_transaction()
btrfs: remove duplicated code to drop delayed ref during transaction abort
btrfs: use helper to find first ref head atbtrfs_destroy_delayed_refs()
btrfs: removenum_entriesatomic counter from delayed ref root
btrfs: change return type ofbtrfs_delayed_ref_lock()to boolean
btrfs: simplify obtaining a delayed ref head
btrfs: move delayed ref head unselection todelayed-ref.c
btrfs: passfs_infoto functions that search for delayed ref heads
btrfs: passfs_infotobtrfs_cleanup_ref_head_accounting
btrfs: assert delayed refs lock is held atfind_ref_head()
btrfs: assert delayed refs lock is held atfind_first_ref_head()
btrfs: assert delayed refs lock is held atadd_delayed_ref_head()
btrfs: add comments regarding locking to structbtrfs_delayed_ref_root
btrfs: track delayed ref heads in an xarray
btrfs: remove no longer used delayed ref head search functionalityfs/btrfs/backref.c | 3 +- fs/btrfs/delayed-ref.c | 319 +++++++++++++++++++++++++---------------- fs/btrfs/delayed-ref.h | 61 +++++--- fs/btrfs/disk-io.c | 79 +--------- fs/btrfs/disk-io.h | 3 +- fs/btrfs/extent-tree.c | 69 ++------- fs/btrfs/transaction.c | 8 +- 7 files changed, 256 insertions(+), 286 deletions(-)
Quoted 5 lines · Qu Wenruo
Quoted 2 lines · 在 2024/10/25 02:54, [email protected] 写道:
From: Filipe Manana <[email protected]>
Quoted 7 lines
Quoted 5 lines
This converts the rb-tree that tracks delayed ref heads into an xarray, reducing memory used by delayed ref heads and making it more efficient to add/remove/find delayed ref heads. The rest are mostly cleanups and refactorings, removing some dead code, deduplicating code, move code around, etc. More details in the changelogs.
Reviewed-by Qu Wenruo <[email protected]>
For the record, rev-by added to the whole series in for-next.