[PATCH 00/18] btrfs: convert delayed head refs to xarray and cleanups

[PATCH 00/18] btrfs: convert delayed head refs to xarray and cleanups

[fdmanana]

From: Filipe Manana <fdmanana@suse.com>

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(-)

-- 
2.43.0

[PATCH 01/18] btrfs: remove BUG_ON() at btrfs_destroy_delayed_refs()

[fdmanana]

From: Filipe Manana <fdmanana@suse.com>

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.

Signed-off-by: Filipe Manana <fdmanana@suse.com>
---
 fs/btrfs/disk-io.c | 37 ++++++++++++++++++++++++-------------
 1 file changed, 24 insertions(+), 13 deletions(-)

diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index bcf6e53bc2a7..47598e525ea5 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -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);
-- 
2.43.0

[PATCH 02/18] btrfs: move btrfs_destroy_delayed_refs() to delayed-ref.c

[fdmanana]

From: Filipe Manana <fdmanana@suse.com>

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.

Signed-off-by: Filipe Manana <fdmanana@suse.com>
---
 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(-)

diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
index 04586aa11917..3ac2000f394d 100644
--- a/fs/btrfs/delayed-ref.c
+++ b/fs/btrfs/delayed-ref.c
@@ -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);
diff --git a/fs/btrfs/delayed-ref.h b/fs/btrfs/delayed-ref.h
index 352921e76c74..ccc040f94264 100644
--- a/fs/btrfs/delayed-ref.h
+++ b/fs/btrfs/delayed-ref.h
@@ -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)
 {
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index 47598e525ea5..f5d30c04ba66 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -4529,86 +4529,6 @@ static void btrfs_destroy_all_ordered_extents(struct btrfs_fs_info *fs_info)
 	btrfs_wait_ordered_roots(fs_info, U64_MAX, NULL);
 }
 
-static 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;
-	struct btrfs_delayed_ref_node *ref;
-
-	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) {
-			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 *cache;
-
-			cache = btrfs_lookup_block_group(fs_info, head->bytenr);
-			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);
-		}
-		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);
-}
-
 static void btrfs_destroy_delalloc_inodes(struct btrfs_root *root)
 {
 	struct btrfs_inode *btrfs_inode;
-- 
2.43.0

[PATCH 03/18] btrfs: remove fs_info parameter from btrfs_destroy_delayed_refs()

[fdmanana]

From: Filipe Manana <fdmanana@suse.com>

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.

Signed-off-by: Filipe Manana <fdmanana@suse.com>
---
 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(-)

diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
index 3ac2000f394d..4dfb7e44507f 100644
--- a/fs/btrfs/delayed-ref.c
+++ b/fs/btrfs/delayed-ref.c
@@ -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) {
diff --git a/fs/btrfs/delayed-ref.h b/fs/btrfs/delayed-ref.h
index ccc040f94264..cc78395f2fcd 100644
--- a/fs/btrfs/delayed-ref.h
+++ b/fs/btrfs/delayed-ref.h
@@ -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)
 {
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index f5d30c04ba66..2e15afa9e04c 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -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);
-- 
2.43.0

[PATCH 04/18] btrfs: remove fs_info parameter from btrfs_cleanup_one_transaction()

[fdmanana]

From: Filipe Manana <fdmanana@suse.com>

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.

Signed-off-by: Filipe Manana <fdmanana@suse.com>
---
 fs/btrfs/disk-io.c     | 8 ++++----
 fs/btrfs/disk-io.h     | 3 +--
 fs/btrfs/transaction.c | 2 +-
 3 files changed, 6 insertions(+), 7 deletions(-)

diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index 2e15afa9e04c..814320948645 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -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)
diff --git a/fs/btrfs/disk-io.h b/fs/btrfs/disk-io.h
index 127e31e08347..a7051e2570c1 100644
--- a/fs/btrfs/disk-io.h
+++ b/fs/btrfs/disk-io.h
@@ -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);
diff --git a/fs/btrfs/transaction.c b/fs/btrfs/transaction.c
index 0fc873af891f..e580c566f033 100644
--- a/fs/btrfs/transaction.c
+++ b/fs/btrfs/transaction.c
@@ -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)
-- 
2.43.0

[PATCH 05/18] btrfs: remove duplicated code to drop delayed ref during transaction abort

[fdmanana]

From: Filipe Manana <fdmanana@suse.com>

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.

Signed-off-by: Filipe Manana <fdmanana@suse.com>
---
 fs/btrfs/delayed-ref.c | 8 +-------
 1 file changed, 1 insertion(+), 7 deletions(-)

diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
index 4dfb7e44507f..db834268faef 100644
--- a/fs/btrfs/delayed-ref.c
+++ b/fs/btrfs/delayed-ref.c
@@ -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;
-- 
2.43.0

[PATCH 06/18] btrfs: use helper to find first ref head at btrfs_destroy_delayed_refs()

[fdmanana]

From: Filipe Manana <fdmanana@suse.com>

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.

Signed-off-by: Filipe Manana <fdmanana@suse.com>
---
 fs/btrfs/delayed-ref.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
index db834268faef..2b2273296246 100644
--- a/fs/btrfs/delayed-ref.c
+++ b/fs/btrfs/delayed-ref.c
@@ -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;
 
-- 
2.43.0

[PATCH 07/18] btrfs: remove num_entries atomic counter from delayed ref root

[fdmanana]

From: Filipe Manana <fdmanana@suse.com>

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.

Signed-off-by: Filipe Manana <fdmanana@suse.com>
---
 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(-)

diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
index 2b2273296246..2e14cfcb152e 100644
--- a/fs/btrfs/delayed-ref.c
+++ b/fs/btrfs/delayed-ref.c
@@ -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;
diff --git a/fs/btrfs/delayed-ref.h b/fs/btrfs/delayed-ref.h
index cc78395f2fcd..a97c9df19ea0 100644
--- a/fs/btrfs/delayed-ref.h
+++ b/fs/btrfs/delayed-ref.h
@@ -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;
 
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index e29024c66edb..9b588ce19a74 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -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
diff --git a/fs/btrfs/transaction.c b/fs/btrfs/transaction.c
index e580c566f033..9ccf68ab53f9 100644
--- a/fs/btrfs/transaction.c
+++ b/fs/btrfs/transaction.c
@@ -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,
-- 
2.43.0

[PATCH 08/18] btrfs: change return type of btrfs_delayed_ref_lock() to boolean

[fdmanana]

From: Filipe Manana <fdmanana@suse.com>

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.

Signed-off-by: Filipe Manana <fdmanana@suse.com>
---
 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(-)

diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
index 2e14cfcb152e..2bfece87bcda 100644
--- a/fs/btrfs/delayed-ref.c
+++ b/fs/btrfs/delayed-ref.c
@@ -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);
diff --git a/fs/btrfs/delayed-ref.h b/fs/btrfs/delayed-ref.h
index a97c9df19ea0..04730c650212 100644
--- a/fs/btrfs/delayed-ref.h
+++ b/fs/btrfs/delayed-ref.h
@@ -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);
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 9b588ce19a74..95d749cec49e 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -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;
-- 
2.43.0

[PATCH 09/18] btrfs: simplify obtaining a delayed ref head

[fdmanana]

From: Filipe Manana <fdmanana@suse.com>

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.

Signed-off-by: Filipe Manana <fdmanana@suse.com>
---
 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(-)

diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
index 2bfece87bcda..9174c6dbbce5 100644
--- a/fs/btrfs/delayed-ref.c
+++ b/fs/btrfs/delayed-ref.c
@@ -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;
 }
 
diff --git a/fs/btrfs/delayed-ref.h b/fs/btrfs/delayed-ref.h
index 04730c650212..956fbe5d6984 100644
--- a/fs/btrfs/delayed-ref.h
+++ b/fs/btrfs/delayed-ref.h
@@ -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);
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 95d749cec49e..f5320a9cdf8f 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -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;
-- 
2.43.0

[PATCH 10/18] btrfs: move delayed ref head unselection to delayed-ref.c

[fdmanana]

From: Filipe Manana <fdmanana@suse.com>

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()).

Signed-off-by: Filipe Manana <fdmanana@suse.com>
---
 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(-)

diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
index 9174c6dbbce5..ffa06f931fa8 100644
--- a/fs/btrfs/delayed-ref.c
+++ b/fs/btrfs/delayed-ref.c
@@ -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)
 {
diff --git a/fs/btrfs/delayed-ref.h b/fs/btrfs/delayed-ref.h
index 956fbe5d6984..d70de7ee63e5 100644
--- a/fs/btrfs/delayed-ref.h
+++ b/fs/btrfs/delayed-ref.h
@@ -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);
 
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index f5320a9cdf8f..2e00267ad362 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -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;
 		}
-- 
2.43.0

[PATCH 11/18] btrfs: pass fs_info to functions that search for delayed ref heads

[fdmanana]

From: Filipe Manana <fdmanana@suse.com>

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().

Signed-off-by: Filipe Manana <fdmanana@suse.com>
---
 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(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index f8e1d5b2c512..04f53ca548e1 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -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);
diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
index ffa06f931fa8..81f7a515dd0e 100644
--- a/fs/btrfs/delayed-ref.c
+++ b/fs/btrfs/delayed-ref.c
@@ -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)
diff --git a/fs/btrfs/delayed-ref.h b/fs/btrfs/delayed-ref.h
index d70de7ee63e5..acd142b01c12 100644
--- a/fs/btrfs/delayed-ref.h
+++ b/fs/btrfs/delayed-ref.h
@@ -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);
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 2e00267ad362..40f16deb1c0f 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -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)) {
-- 
2.43.0

[PATCH 12/18] btrfs: pass fs_info to btrfs_cleanup_ref_head_accounting

[fdmanana]

From: Filipe Manana <fdmanana@suse.com>

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.

Signed-off-by: Filipe Manana <fdmanana@suse.com>
---
 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(-)

diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
index 81f7a515dd0e..e81aa112d137 100644
--- a/fs/btrfs/delayed-ref.c
+++ b/fs/btrfs/delayed-ref.c
@@ -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);
diff --git a/fs/btrfs/delayed-ref.h b/fs/btrfs/delayed-ref.h
index acd142b01c12..c3749e6cc374 100644
--- a/fs/btrfs/delayed-ref.h
+++ b/fs/btrfs/delayed-ref.h
@@ -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(
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 40f16deb1c0f..33f911476a4d 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -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;
-- 
2.43.0

[PATCH 13/18] btrfs: assert delayed refs lock is held at find_ref_head()

[fdmanana]

From: Filipe Manana <fdmanana@suse.com>

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()).

Signed-off-by: Filipe Manana <fdmanana@suse.com>
---
 fs/btrfs/delayed-ref.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
index e81aa112d137..3aeb2c79c1ae 100644
--- a/fs/btrfs/delayed-ref.c
+++ b/fs/btrfs/delayed-ref.c
@@ -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);
 }
 
-- 
2.43.0

[PATCH 14/18] btrfs: assert delayed refs lock is held at find_first_ref_head()

[fdmanana]

From: Filipe Manana <fdmanana@suse.com>

The delayed refs lock must be held when calling find_first_ref_head(), so
assert that it's being held.

Signed-off-by: Filipe Manana <fdmanana@suse.com>
---
 fs/btrfs/delayed-ref.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
index 3aeb2c79c1ae..a8cf76f44b2b 100644
--- a/fs/btrfs/delayed-ref.c
+++ b/fs/btrfs/delayed-ref.c
@@ -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;
-- 
2.43.0

[PATCH 15/18] btrfs: assert delayed refs lock is held at add_delayed_ref_head()

[fdmanana]

From: Filipe Manana <fdmanana@suse.com>

The delayed refs lock must be held when calling add_delayed_ref_head(),
so assert that it's being held.

Signed-off-by: Filipe Manana <fdmanana@suse.com>
---
 fs/btrfs/delayed-ref.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
index a8cf76f44b2b..2b6a636ba4b5 100644
--- a/fs/btrfs/delayed-ref.c
+++ b/fs/btrfs/delayed-ref.c
@@ -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) {
-- 
2.43.0

[PATCH 16/18] btrfs: add comments regarding locking to struct btrfs_delayed_ref_root

[fdmanana]

From: Filipe Manana <fdmanana@suse.com>

Add some comments to struct btrfs_delayed_ref_root's fields to mention
what its spinlock protects.

Signed-off-by: Filipe Manana <fdmanana@suse.com>
---
 fs/btrfs/delayed-ref.h | 20 +++++++++++++++++---
 1 file changed, 17 insertions(+), 3 deletions(-)

diff --git a/fs/btrfs/delayed-ref.h b/fs/btrfs/delayed-ref.h
index c3749e6cc374..0a9f4d7dd87b 100644
--- a/fs/btrfs/delayed-ref.h
+++ b/fs/btrfs/delayed-ref.h
@@ -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;
 
 	/*
-- 
2.43.0

[PATCH 17/18] btrfs: track delayed ref heads in an xarray

[fdmanana]

From: Filipe Manana <fdmanana@suse.com>

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 $MNT

Before 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         12783329

After 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

Signed-off-by: Filipe Manana <fdmanana@suse.com>
---
 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(-)

diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
index 2b6a636ba4b5..e4ca5285e614 100644
--- a/fs/btrfs/delayed-ref.c
+++ b/fs/btrfs/delayed-ref.c
@@ -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
diff --git a/fs/btrfs/delayed-ref.h b/fs/btrfs/delayed-ref.h
index 0a9f4d7dd87b..c7c4d62744b4 100644
--- a/fs/btrfs/delayed-ref.h
+++ b/fs/btrfs/delayed-ref.h
@@ -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;
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 33f911476a4d..1571b5a1d905 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -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;
 		}
diff --git a/fs/btrfs/transaction.c b/fs/btrfs/transaction.c
index 9ccf68ab53f9..dc0b837efd5d 100644
--- a/fs/btrfs/transaction.c
+++ b/fs/btrfs/transaction.c
@@ -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

[Boris Burkov]

On Thu, Oct 24, 2024 at 05:24:25PM +0100, fdmanana@kernel.org wrote:
> From: Filipe Manana <fdmanana@suse.com>
> 
> 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.

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?

> 
> 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 $MNT
> 
> Before 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         12783329
> 
> After 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
> 
> Signed-off-by: Filipe Manana <fdmanana@suse.com>
> ---
>  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(-)
> 
> diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
> index 2b6a636ba4b5..e4ca5285e614 100644
> --- a/fs/btrfs/delayed-ref.c
> +++ b/fs/btrfs/delayed-ref.c
> @@ -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
> diff --git a/fs/btrfs/delayed-ref.h b/fs/btrfs/delayed-ref.h
> index 0a9f4d7dd87b..c7c4d62744b4 100644
> --- a/fs/btrfs/delayed-ref.h
> +++ b/fs/btrfs/delayed-ref.h
> @@ -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

This comment is great.

I also think a named function or macro computing the index would be
beneficial.

>  	 * 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;
> diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
> index 33f911476a4d..1571b5a1d905 100644
> --- a/fs/btrfs/extent-tree.c
> +++ b/fs/btrfs/extent-tree.c
> @@ -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;
>  		}
> diff --git a/fs/btrfs/transaction.c b/fs/btrfs/transaction.c
> index 9ccf68ab53f9..dc0b837efd5d 100644
> --- a/fs/btrfs/transaction.c
> +++ b/fs/btrfs/transaction.c
> @@ -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

[Filipe Manana]

On Thu, Oct 24, 2024 at 7:56 PM Boris Burkov <boris@bur.io> wrote:
>
> On Thu, Oct 24, 2024 at 05:24:25PM +0100, fdmanana@kernel.org wrote:
> > From: Filipe Manana <fdmanana@suse.com>
> >
> > 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.
>
> 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?

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.

>
> >
> > 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 $MNT
> >
> > Before 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         12783329
> >
> > After 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
> >
> > Signed-off-by: Filipe Manana <fdmanana@suse.com>
> > ---
> >  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(-)
> >
> > diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
> > index 2b6a636ba4b5..e4ca5285e614 100644
> > --- a/fs/btrfs/delayed-ref.c
> > +++ b/fs/btrfs/delayed-ref.c
> > @@ -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
> > diff --git a/fs/btrfs/delayed-ref.h b/fs/btrfs/delayed-ref.h
> > index 0a9f4d7dd87b..c7c4d62744b4 100644
> > --- a/fs/btrfs/delayed-ref.h
> > +++ b/fs/btrfs/delayed-ref.h
> > @@ -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
>
> This comment is great.
>
> I also think a named function or macro computing the index would be
> beneficial.
>
> >        * 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;
> > diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
> > index 33f911476a4d..1571b5a1d905 100644
> > --- a/fs/btrfs/extent-tree.c
> > +++ b/fs/btrfs/extent-tree.c
> > @@ -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;
> >               }
> > diff --git a/fs/btrfs/transaction.c b/fs/btrfs/transaction.c
> > index 9ccf68ab53f9..dc0b837efd5d 100644
> > --- a/fs/btrfs/transaction.c
> > +++ b/fs/btrfs/transaction.c
> > @@ -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

[David Sterba]

On Thu, Oct 24, 2024 at 11:55:31AM -0700, Boris Burkov wrote:
> On Thu, Oct 24, 2024 at 05:24:25PM +0100, fdmanana@kernel.org wrote:
> > From: Filipe Manana <fdmanana@suse.com>
> > 
> > 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.
> 
> 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?

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

[fdmanana]

From: Filipe Manana <fdmanana@suse.com>

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.

Signed-off-by: Filipe Manana <fdmanana@suse.com>
---
 fs/btrfs/delayed-ref.c | 34 +++++-----------------------------
 1 file changed, 5 insertions(+), 29 deletions(-)

diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
index e4ca5285e614..7399be5fddaf 100644
--- a/fs/btrfs/delayed-ref.c
+++ b/fs/btrfs/delayed-ref.c
@@ -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)
-- 
2.43.0

Re: [PATCH 00/18] btrfs: convert delayed head refs to xarray and cleanups

[Boris Burkov]

On Thu, Oct 24, 2024 at 05:24:08PM +0100, fdmanana@kernel.org wrote:
> From: Filipe Manana <fdmanana@suse.com>
> 
> 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.

Reviewed-by: Boris Burkov <boris@bur.io>

> 
> 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(-)
> 
> -- 
> 2.43.0
> 

Re: [PATCH 00/18] btrfs: convert delayed head refs to xarray and cleanups

[Johannes Thumshirn]

On 24.10.24 18:24, fdmanana@kernel.org wrote:
> From: Filipe Manana <fdmanana@suse.com>
> 
> 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?

Re: [PATCH 00/18] btrfs: convert delayed head refs to xarray and cleanups

[Filipe Manana]

On Fri, Oct 25, 2024 at 2:19 PM Johannes Thumshirn
<Johannes.Thumshirn@wdc.com> wrote:
>
> On 24.10.24 18:24, fdmanana@kernel.org wrote:
> > From: Filipe Manana <fdmanana@suse.com>
> >
> > 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?

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.

Re: [PATCH 00/18] btrfs: convert delayed head refs to xarray and cleanups

[Johannes Thumshirn]

On 25.10.24 15:36, Filipe Manana wrote:
> On Fri, Oct 25, 2024 at 2:19 PM Johannes Thumshirn
> <Johannes.Thumshirn@wdc.com> wrote:
>>
>> On 24.10.24 18:24, fdmanana@kernel.org wrote:
>>> From: Filipe Manana <fdmanana@suse.com>
>>>
>>> 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?
> 
> 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.
> 

Thanks for the info :)

Re: [PATCH 00/18] btrfs: convert delayed head refs to xarray and cleanups

[Qu Wenruo]

在 2024/10/26 00:05, Filipe Manana 写道:
> On Fri, Oct 25, 2024 at 2:19 PM Johannes Thumshirn
> <Johannes.Thumshirn@wdc.com> wrote:
>>
>> On 24.10.24 18:24, fdmanana@kernel.org wrote:
>>> From: Filipe Manana <fdmanana@suse.com>
>>>
>>> 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?
>
> 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.
>

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

Re: [PATCH 00/18] btrfs: convert delayed head refs to xarray and cleanups

[Filipe Manana]

On Fri, Oct 25, 2024 at 10:18 PM Qu Wenruo <quwenruo.btrfs@gmx.com> wrote:
>
>
>
> 在 2024/10/26 00:05, Filipe Manana 写道:
> > On Fri, Oct 25, 2024 at 2:19 PM Johannes Thumshirn
> > <Johannes.Thumshirn@wdc.com> wrote:
> >>
> >> On 24.10.24 18:24, fdmanana@kernel.org wrote:
> >>> From: Filipe Manana <fdmanana@suse.com>
> >>>
> >>> 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?
> >
> > 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.
> >
>
> 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.

>
> 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.

>
> Thanks,
> Qu

Re: [PATCH 00/18] btrfs: convert delayed head refs to xarray and cleanups

[David Sterba]

On Thu, Oct 24, 2024 at 05:24:08PM +0100, fdmanana@kernel.org wrote:
> From: Filipe Manana <fdmanana@suse.com>
> 
> 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

Reviewed-by: David Sterba <dsterba@suse.com>

Thank you, nice cleanups and I like another conversion to xarray.

Re: [PATCH 00/18] btrfs: convert delayed head refs to xarray and cleanups

[Qu Wenruo]

在 2024/10/25 02:54, fdmanana@kernel.org 写道:
> From: Filipe Manana <fdmanana@suse.com>
>
> 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 <wqu@suse.com>

Thanks,
Qu

>
> 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(-)
>

Re: [PATCH 00/18] btrfs: convert delayed head refs to xarray and cleanups

[David Sterba]

On Tue, Oct 29, 2024 at 07:25:35AM +1030, Qu Wenruo wrote:
> 
> 
> 在 2024/10/25 02:54, fdmanana@kernel.org 写道:
> > From: Filipe Manana <fdmanana@suse.com>
> >
> > 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 <wqu@suse.com>

For the record, rev-by added to the whole series in for-next.