Skip to contentSkip to conversation

btrfs: convert delayed head refs to xarray and cleanups

PATCH In review [email protected] 5 participants 31 messages Oct 24, 2024 – Oct 29, 2024 Btrfs file system

lore
Share & tools
lore
#0 lore raw

cover btrfs: convert delayed head refs to xarray and cleanups

From: Filipe Manana <[email protected]>

This converts the rb-tree that tracks delayed ref heads into an xarray, reducing memory used by delayed ref heads and making it more efficient to add/remove/find delayed ref heads. The rest are mostly cleanups and refactorings, removing some dead code, deduplicating code, move code around, etc. More details in the changelogs.

Filipe Manana (18):
btrfs: remove BUG_ON() at btrfs_destroy_delayed_refs()
btrfs: move btrfs_destroy_delayed_refs() to delayed-ref.c
btrfs: remove fs_info parameter from btrfs_destroy_delayed_refs()
btrfs: remove fs_info parameter from btrfs_cleanup_one_transaction()
btrfs: remove duplicated code to drop delayed ref during transaction abort
btrfs: use helper to find first ref head at btrfs_destroy_delayed_refs()
btrfs: remove num_entries atomic counter from delayed ref root
btrfs: change return type of btrfs_delayed_ref_lock() to boolean
btrfs: simplify obtaining a delayed ref head
btrfs: move delayed ref head unselection to delayed-ref.c
btrfs: pass fs_info to functions that search for delayed ref heads
btrfs: pass fs_info to btrfs_cleanup_ref_head_accounting
btrfs: assert delayed refs lock is held at find_ref_head()
btrfs: assert delayed refs lock is held at find_first_ref_head()
btrfs: assert delayed refs lock is held at add_delayed_ref_head()
btrfs: add comments regarding locking to struct btrfs_delayed_ref_root
btrfs: track delayed ref heads in an xarray
btrfs: remove no longer used delayed ref head search functionality

 fs/btrfs/backref.c     |   3 +-
 fs/btrfs/delayed-ref.c | 319 +++++++++++++++++++++++++----------------
 fs/btrfs/delayed-ref.h |  61 +++++---
 fs/btrfs/disk-io.c     |  79 +---------
 fs/btrfs/disk-io.h     |   3 +-
 fs/btrfs/extent-tree.c |  69 ++-------
 fs/btrfs/transaction.c |   8 +-
 7 files changed, 256 insertions(+), 286 deletions(-)
Signature · 1 line
2.43.0
#1 lore raw

PATCH 1/18 btrfs: remove BUG_ON() at btrfs_destroy_delayed_refs()

From: Filipe Manana <[email protected]>

At btrfs_destroy_delayed_refs() it's unexpected to not find the block group to which a delayed reference's extent belongs to, so we have this BUG_ON(), not just because it's highly unexpected but also because we don't know what to do there.

Since we are in the transaction abort path, there's nothing we can do other than proceed and cleanup all used resources we can. So remove the BUG_ON() and deal with a missing block group by logging an error message and continuing to cleanup all we can related to the current delayed ref head and moving to other delayed refs.

---
 fs/btrfs/disk-io.c | 37 ++++++++++++++++++++++++-------------
 1 file changed, 24 insertions(+), 13 deletions(-)
fs/btrfs/disk-io.c +24 -13
index bcf6e53bc2a7..47598e525ea5 100644
@@ -4571,19 +4571,30 @@ static void btrfs_destroy_delayed_refs(struct btrfs_transaction *trans,
 			struct btrfs_block_group *cache;
 
 			cache = btrfs_lookup_block_group(fs_info, head->bytenr);
-			BUG_ON(!cache);
-
-			spin_lock(&cache->space_info->lock);
-			spin_lock(&cache->lock);
-			cache->pinned += head->num_bytes;
-			btrfs_space_info_update_bytes_pinned(fs_info,
-				cache->space_info, head->num_bytes);
-			cache->reserved -= head->num_bytes;
-			cache->space_info->bytes_reserved -= head->num_bytes;
-			spin_unlock(&cache->lock);
-			spin_unlock(&cache->space_info->lock);
-
-			btrfs_put_block_group(cache);
+			if (WARN_ON_ONCE(cache == NULL)) {
+				/*
+				 * Unexpected and there's nothing we can do here
+				 * because we are in a transaction abort path,
+				 * so any errors can only be ignored or reported
+				 * while attempting to cleanup all resources.
+				 */
+				btrfs_err(fs_info,
+"block group for delayed ref at %llu was not found while destroying ref head",
+					  head->bytenr);
+			} else {
+				spin_lock(&cache->space_info->lock);
+				spin_lock(&cache->lock);
+				cache->pinned += head->num_bytes;
+				btrfs_space_info_update_bytes_pinned(fs_info,
+								     cache->space_info,
+								     head->num_bytes);
+				cache->reserved -= head->num_bytes;
+				cache->space_info->bytes_reserved -= head->num_bytes;
+				spin_unlock(&cache->lock);
+				spin_unlock(&cache->space_info->lock);
+
+				btrfs_put_block_group(cache);
+			}
 
 			btrfs_error_unpin_extent_range(fs_info, head->bytenr,
 				head->bytenr + head->num_bytes - 1);
Signature · 1 line
2.43.0
#2 lore raw

PATCH 2/18 btrfs: move btrfs_destroy_delayed_refs() to delayed-ref.c

In reply to [email protected]

From: Filipe Manana <[email protected]>

It's better suited at delayed-ref.c since it's about delayed refs and contains logic to iterate over them (using the red black tree, doing all the locking, freeing, etc), so move it from disk-io.c, which is pretty big, into delayed-ref.c, hidding implementation details of how delayed refs are tracked and managed. This also facilitates the next patches in the series.

This change moves the code between files but also does the following simple cleanups:

1) Rename the 'cache' variable to 'bg', since it's a block group (the 'cache' logic comes from old days where the block group structure was named 'btrfs_block_group_cache');

2) Move the 'ref' variable declaration to the scope of the inner while loop, since it's not used outside that loop.

---
 fs/btrfs/delayed-ref.c | 81 ++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/delayed-ref.h |  2 ++
 fs/btrfs/disk-io.c     | 80 -----------------------------------------
 3 files changed, 83 insertions(+), 80 deletions(-)
fs/btrfs/delayed-ref.c +81 -0
index 04586aa11917..3ac2000f394d 100644
@@ -9,6 +9,7 @@
 #include "messages.h"
 #include "ctree.h"
 #include "delayed-ref.h"
+#include "extent-tree.h"
 #include "transaction.h"
 #include "qgroup.h"
 #include "space-info.h"
@@ -1238,6 +1239,86 @@ bool btrfs_find_delayed_tree_ref(struct btrfs_delayed_ref_head *head,
 	return found;
 }
 
+void btrfs_destroy_delayed_refs(struct btrfs_transaction *trans,
+				struct btrfs_fs_info *fs_info)
+{
+	struct rb_node *node;
+	struct btrfs_delayed_ref_root *delayed_refs = &trans->delayed_refs;
+
+	spin_lock(&delayed_refs->lock);
+	while ((node = rb_first_cached(&delayed_refs->href_root)) != NULL) {
+		struct btrfs_delayed_ref_head *head;
+		struct rb_node *n;
+		bool pin_bytes = false;
+
+		head = rb_entry(node, struct btrfs_delayed_ref_head,
+				href_node);
+		if (btrfs_delayed_ref_lock(delayed_refs, head))
+			continue;
+
+		spin_lock(&head->lock);
+		while ((n = rb_first_cached(&head->ref_tree)) != NULL) {
+			struct btrfs_delayed_ref_node *ref;
+
+			ref = rb_entry(n, struct btrfs_delayed_ref_node, ref_node);
+			rb_erase_cached(&ref->ref_node, &head->ref_tree);
+			RB_CLEAR_NODE(&ref->ref_node);
+			if (!list_empty(&ref->add_list))
+				list_del(&ref->add_list);
+			atomic_dec(&delayed_refs->num_entries);
+			btrfs_put_delayed_ref(ref);
+			btrfs_delayed_refs_rsv_release(fs_info, 1, 0);
+		}
+		if (head->must_insert_reserved)
+			pin_bytes = true;
+		btrfs_free_delayed_extent_op(head->extent_op);
+		btrfs_delete_ref_head(delayed_refs, head);
+		spin_unlock(&head->lock);
+		spin_unlock(&delayed_refs->lock);
+		mutex_unlock(&head->mutex);
+
+		if (pin_bytes) {
+			struct btrfs_block_group *bg;
+
+			bg = btrfs_lookup_block_group(fs_info, head->bytenr);
+			if (WARN_ON_ONCE(bg == NULL)) {
+				/*
+				 * Unexpected and there's nothing we can do here
+				 * because we are in a transaction abort path,
+				 * so any errors can only be ignored or reported
+				 * while attempting to cleanup all resources.
+				 */
+				btrfs_err(fs_info,
+"block group for delayed ref at %llu was not found while destroying ref head",
+					  head->bytenr);
+			} else {
+				spin_lock(&bg->space_info->lock);
+				spin_lock(&bg->lock);
+				bg->pinned += head->num_bytes;
+				btrfs_space_info_update_bytes_pinned(fs_info,
+								     bg->space_info,
+								     head->num_bytes);
+				bg->reserved -= head->num_bytes;
+				bg->space_info->bytes_reserved -= head->num_bytes;
+				spin_unlock(&bg->lock);
+				spin_unlock(&bg->space_info->lock);
+
+				btrfs_put_block_group(bg);
+			}
+
+			btrfs_error_unpin_extent_range(fs_info, head->bytenr,
+				head->bytenr + head->num_bytes - 1);
+		}
+		btrfs_cleanup_ref_head_accounting(fs_info, delayed_refs, head);
+		btrfs_put_delayed_ref_head(head);
+		cond_resched();
+		spin_lock(&delayed_refs->lock);
+	}
+	btrfs_qgroup_destroy_extent_records(trans);
+
+	spin_unlock(&delayed_refs->lock);
+}
+
 void __cold btrfs_delayed_ref_exit(void)
 {
 	kmem_cache_destroy(btrfs_delayed_ref_head_cachep);
fs/btrfs/delayed-ref.h +2 -0
index 352921e76c74..ccc040f94264 100644
@@ -399,6 +399,8 @@ int btrfs_delayed_refs_rsv_refill(struct btrfs_fs_info *fs_info,
 bool btrfs_check_space_for_delayed_refs(struct btrfs_fs_info *fs_info);
 bool btrfs_find_delayed_tree_ref(struct btrfs_delayed_ref_head *head,
 				 u64 root, u64 parent);
+void btrfs_destroy_delayed_refs(struct btrfs_transaction *trans,
+				struct btrfs_fs_info *fs_info);
 
 static inline u64 btrfs_delayed_ref_owner(struct btrfs_delayed_ref_node *node)
 {
fs/btrfs/disk-io.c +0 -80

86 lines not on this page · raw message

Signature · 1 line
2.43.0
#3 lore raw

PATCH 3/18 btrfs: remove fs_info parameter from btrfs_destroy_delayed_refs()

In reply to [email protected]

From: Filipe Manana <[email protected]>

The fs_info parameter is redundant because it can be extracted from the transaction given as another parameter. So remove it and use the fs_info accessible from the transaction.

---
 fs/btrfs/delayed-ref.c | 4 ++--
 fs/btrfs/delayed-ref.h | 3 +--
 fs/btrfs/disk-io.c     | 2 +-
 3 files changed, 4 insertions(+), 5 deletions(-)
fs/btrfs/delayed-ref.c +2 -2
index 3ac2000f394d..4dfb7e44507f 100644
@@ -1239,11 +1239,11 @@ bool btrfs_find_delayed_tree_ref(struct btrfs_delayed_ref_head *head,
 	return found;
 }
 
-void btrfs_destroy_delayed_refs(struct btrfs_transaction *trans,
-				struct btrfs_fs_info *fs_info)
+void btrfs_destroy_delayed_refs(struct btrfs_transaction *trans)
 {
 	struct rb_node *node;
 	struct btrfs_delayed_ref_root *delayed_refs = &trans->delayed_refs;
+	struct btrfs_fs_info *fs_info = trans->fs_info;
 
 	spin_lock(&delayed_refs->lock);
 	while ((node = rb_first_cached(&delayed_refs->href_root)) != NULL) {
fs/btrfs/delayed-ref.h +1 -2
index ccc040f94264..cc78395f2fcd 100644
@@ -399,8 +399,7 @@ int btrfs_delayed_refs_rsv_refill(struct btrfs_fs_info *fs_info,
 bool btrfs_check_space_for_delayed_refs(struct btrfs_fs_info *fs_info);
 bool btrfs_find_delayed_tree_ref(struct btrfs_delayed_ref_head *head,
 				 u64 root, u64 parent);
-void btrfs_destroy_delayed_refs(struct btrfs_transaction *trans,
-				struct btrfs_fs_info *fs_info);
+void btrfs_destroy_delayed_refs(struct btrfs_transaction *trans);
 
 static inline u64 btrfs_delayed_ref_owner(struct btrfs_delayed_ref_node *node)
 {
fs/btrfs/disk-io.c +1 -1
index f5d30c04ba66..2e15afa9e04c 100644
@@ -4748,7 +4748,7 @@ void btrfs_cleanup_one_transaction(struct btrfs_transaction *cur_trans,
 		list_del_init(&dev->post_commit_list);
 	}
 
-	btrfs_destroy_delayed_refs(cur_trans, fs_info);
+	btrfs_destroy_delayed_refs(cur_trans);
 
 	cur_trans->state = TRANS_STATE_COMMIT_START;
 	wake_up(&fs_info->transaction_blocked_wait);
Signature · 1 line
2.43.0
#4 lore raw

PATCH 4/18 btrfs: remove fs_info parameter from btrfs_cleanup_one_transaction()

In reply to [email protected]

From: Filipe Manana <[email protected]>

The fs_info parameter is redundant because it can be extracted from the transaction given as another parameter. So remove it and use the fs_info accessible from the transaction.

---
 fs/btrfs/disk-io.c     | 8 ++++----
 fs/btrfs/disk-io.h     | 3 +--
 fs/btrfs/transaction.c | 2 +-
 3 files changed, 6 insertions(+), 7 deletions(-)
fs/btrfs/disk-io.c +4 -4
index 2e15afa9e04c..814320948645 100644
@@ -4183,7 +4183,7 @@ static void warn_about_uncommitted_trans(struct btrfs_fs_info *fs_info)
 		btrfs_warn(fs_info,
 	"transaction %llu (with %llu dirty metadata bytes) is not committed",
 			   trans->transid, dirty_bytes);
-		btrfs_cleanup_one_transaction(trans, fs_info);
+		btrfs_cleanup_one_transaction(trans);
 
 		if (trans == fs_info->running_transaction)
 			fs_info->running_transaction = NULL;
@@ -4734,9 +4734,9 @@ static void btrfs_free_all_qgroup_pertrans(struct btrfs_fs_info *fs_info)
 	spin_unlock(&fs_info->fs_roots_radix_lock);
 }
 
-void btrfs_cleanup_one_transaction(struct btrfs_transaction *cur_trans,
-				   struct btrfs_fs_info *fs_info)
+void btrfs_cleanup_one_transaction(struct btrfs_transaction *cur_trans)
 {
+	struct btrfs_fs_info *fs_info = cur_trans->fs_info;
 	struct btrfs_device *dev, *tmp;
 
 	btrfs_cleanup_dirty_bgs(cur_trans, fs_info);
@@ -4794,7 +4794,7 @@ static int btrfs_cleanup_transaction(struct btrfs_fs_info *fs_info)
 		} else {
 			spin_unlock(&fs_info->trans_lock);
 		}
-		btrfs_cleanup_one_transaction(t, fs_info);
+		btrfs_cleanup_one_transaction(t);
 
 		spin_lock(&fs_info->trans_lock);
 		if (t == fs_info->running_transaction)
fs/btrfs/disk-io.h +1 -2
index 127e31e08347..a7051e2570c1 100644
@@ -126,8 +126,7 @@ int btrfs_add_log_tree(struct btrfs_trans_handle *trans,
 		       struct btrfs_root *root);
 void btrfs_cleanup_dirty_bgs(struct btrfs_transaction *trans,
 			     struct btrfs_fs_info *fs_info);
-void btrfs_cleanup_one_transaction(struct btrfs_transaction *trans,
-				  struct btrfs_fs_info *fs_info);
+void btrfs_cleanup_one_transaction(struct btrfs_transaction *trans);
 struct btrfs_root *btrfs_create_tree(struct btrfs_trans_handle *trans,
 				     u64 objectid);
 int btrfs_get_num_tolerated_disk_barrier_failures(u64 flags);
fs/btrfs/transaction.c +1 -1
index 0fc873af891f..e580c566f033 100644
@@ -2052,7 +2052,7 @@ static void cleanup_transaction(struct btrfs_trans_handle *trans, int err)
 
 	spin_unlock(&fs_info->trans_lock);
 
-	btrfs_cleanup_one_transaction(trans->transaction, fs_info);
+	btrfs_cleanup_one_transaction(trans->transaction);
 
 	spin_lock(&fs_info->trans_lock);
 	if (cur_trans == fs_info->running_transaction)
Signature · 1 line
2.43.0
#5 lore raw

PATCH 5/18 btrfs: remove duplicated code to drop delayed ref during transaction abort

In reply to [email protected]

From: Filipe Manana <[email protected]>

When destroying delayed refs during a transaction abort, we have open coded the removal of a delayed ref, which is also done by the static helper function drop_delayed_ref(). So remove that duplicated code and use drop_delayed_ref() instead.

---
 fs/btrfs/delayed-ref.c | 8 +-------
 1 file changed, 1 insertion(+), 7 deletions(-)
fs/btrfs/delayed-ref.c +1 -7
index 4dfb7e44507f..db834268faef 100644
@@ -1261,13 +1261,7 @@ void btrfs_destroy_delayed_refs(struct btrfs_transaction *trans)
 			struct btrfs_delayed_ref_node *ref;
 
 			ref = rb_entry(n, struct btrfs_delayed_ref_node, ref_node);
-			rb_erase_cached(&ref->ref_node, &head->ref_tree);
-			RB_CLEAR_NODE(&ref->ref_node);
-			if (!list_empty(&ref->add_list))
-				list_del(&ref->add_list);
-			atomic_dec(&delayed_refs->num_entries);
-			btrfs_put_delayed_ref(ref);
-			btrfs_delayed_refs_rsv_release(fs_info, 1, 0);
+			drop_delayed_ref(fs_info, delayed_refs, head, ref);
 		}
 		if (head->must_insert_reserved)
 			pin_bytes = true;
Signature · 1 line
2.43.0
#6 lore raw

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

In reply to [email protected]

From: Filipe Manana <[email protected]>

Instead of open coding it, use the find_first_ref_head() helper at btrfs_destroy_delayed_refs(). This avoids duplicating the logic, specially with the upcoming changes in subsequent patches.

---
 fs/btrfs/delayed-ref.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)
fs/btrfs/delayed-ref.c +5 -4
index db834268faef..2b2273296246 100644
@@ -1241,18 +1241,19 @@ bool btrfs_find_delayed_tree_ref(struct btrfs_delayed_ref_head *head,
 
 void btrfs_destroy_delayed_refs(struct btrfs_transaction *trans)
 {
-	struct rb_node *node;
 	struct btrfs_delayed_ref_root *delayed_refs = &trans->delayed_refs;
 	struct btrfs_fs_info *fs_info = trans->fs_info;
 
 	spin_lock(&delayed_refs->lock);
-	while ((node = rb_first_cached(&delayed_refs->href_root)) != NULL) {
+	while (true) {
 		struct btrfs_delayed_ref_head *head;
 		struct rb_node *n;
 		bool pin_bytes = false;
 
-		head = rb_entry(node, struct btrfs_delayed_ref_head,
-				href_node);
+		head = find_first_ref_head(delayed_refs);
+		if (!head)
+			break;
+
 		if (btrfs_delayed_ref_lock(delayed_refs, head))
 			continue;
 
Signature · 1 line
2.43.0
#7 lore raw

PATCH 7/18 btrfs: remove num_entries atomic counter from delayed ref root

In reply to [email protected]

From: Filipe Manana <[email protected]>

The atomic counter 'num_entries' is not used anymore, we increment it and decrement it but then we don't ever read it to use for any logic. Its last use was removed with commit 61a56a992fcf ("btrfs: delayed refs pre-flushing should only run the heads we have"). So remove it.

---
 fs/btrfs/delayed-ref.c | 4 ----
 fs/btrfs/delayed-ref.h | 5 -----
 fs/btrfs/extent-tree.c | 1 -
 fs/btrfs/transaction.c | 1 -
 4 files changed, 11 deletions(-)
fs/btrfs/delayed-ref.c +0 -4
index 2b2273296246..2e14cfcb152e 100644
@@ -463,7 +463,6 @@ static inline void drop_delayed_ref(struct btrfs_fs_info *fs_info,
 	if (!list_empty(&ref->add_list))
 		list_del(&ref->add_list);
 	btrfs_put_delayed_ref(ref);
-	atomic_dec(&delayed_refs->num_entries);
 	btrfs_delayed_refs_rsv_release(fs_info, 1, 0);
 }
 
@@ -604,7 +603,6 @@ void btrfs_delete_ref_head(struct btrfs_delayed_ref_root *delayed_refs,
 
 	rb_erase_cached(&head->href_node, &delayed_refs->href_root);
 	RB_CLEAR_NODE(&head->href_node);
-	atomic_dec(&delayed_refs->num_entries);
 	delayed_refs->num_heads--;
 	if (!head->processing)
 		delayed_refs->num_heads_ready--;
@@ -630,7 +628,6 @@ static bool insert_delayed_ref(struct btrfs_trans_handle *trans,
 	if (!exist) {
 		if (ref->action == BTRFS_ADD_DELAYED_REF)
 			list_add_tail(&ref->add_list, &href->ref_add_list);
-		atomic_inc(&root->num_entries);
 		spin_unlock(&href->lock);
 		trans->delayed_ref_updates++;
 		return false;
@@ -901,7 +898,6 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,
 		}
 		delayed_refs->num_heads++;
 		delayed_refs->num_heads_ready++;
-		atomic_inc(&delayed_refs->num_entries);
 	}
 	if (qrecord_inserted_ret)
 		*qrecord_inserted_ret = qrecord_inserted;
fs/btrfs/delayed-ref.h +0 -5
index cc78395f2fcd..a97c9df19ea0 100644
@@ -216,11 +216,6 @@ struct btrfs_delayed_ref_root {
 	/* this spin lock protects the rbtree and the entries inside */
 	spinlock_t lock;
 
-	/* how many delayed ref updates we've queued, used by the
-	 * throttling code
-	 */
-	atomic_t num_entries;
-
 	/* total number of head nodes in tree */
 	unsigned long num_heads;
 
fs/btrfs/extent-tree.c +0 -1
index e29024c66edb..9b588ce19a74 100644
@@ -2009,7 +2009,6 @@ static int btrfs_run_delayed_refs_for_head(struct btrfs_trans_handle *trans,
 		default:
 			WARN_ON(1);
 		}
-		atomic_dec(&delayed_refs->num_entries);
 
 		/*
 		 * Record the must_insert_reserved flag before we drop the
fs/btrfs/transaction.c +0 -1
index e580c566f033..9ccf68ab53f9 100644
@@ -351,7 +351,6 @@ static noinline int join_transaction(struct btrfs_fs_info *fs_info,
 
 	cur_trans->delayed_refs.href_root = RB_ROOT_CACHED;
 	xa_init(&cur_trans->delayed_refs.dirty_extents);
-	atomic_set(&cur_trans->delayed_refs.num_entries, 0);
 
 	/*
 	 * although the tree mod log is per file system and not per transaction,
Signature · 1 line
2.43.0
#8 lore raw

PATCH 8/18 btrfs: change return type of btrfs_delayed_ref_lock() to boolean

In reply to [email protected]

From: Filipe Manana <[email protected]>

The function only returns 0, meaning it was able to lock the delayed ref head, or -EAGAIN in case it wasn't able to lock it. So simplify this and use a boolean return type instead, returning true if it was able to lock and false otherwise.

---
 fs/btrfs/delayed-ref.c | 12 ++++++------
 fs/btrfs/delayed-ref.h |  4 ++--
 fs/btrfs/extent-tree.c |  6 +++---
 3 files changed, 11 insertions(+), 11 deletions(-)
fs/btrfs/delayed-ref.c +6 -6
index 2e14cfcb152e..2bfece87bcda 100644
@@ -431,12 +431,12 @@ static struct btrfs_delayed_ref_head *find_ref_head(
 	return NULL;
 }
 
-int btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,
-			   struct btrfs_delayed_ref_head *head)
+bool btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,
+			    struct btrfs_delayed_ref_head *head)
 {
 	lockdep_assert_held(&delayed_refs->lock);
 	if (mutex_trylock(&head->mutex))
-		return 0;
+		return true;
 
 	refcount_inc(&head->refs);
 	spin_unlock(&delayed_refs->lock);
@@ -446,10 +446,10 @@ int btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,
 	if (RB_EMPTY_NODE(&head->href_node)) {
 		mutex_unlock(&head->mutex);
 		btrfs_put_delayed_ref_head(head);
-		return -EAGAIN;
+		return false;
 	}
 	btrfs_put_delayed_ref_head(head);
-	return 0;
+	return true;
 }
 
 static inline void drop_delayed_ref(struct btrfs_fs_info *fs_info,
@@ -1250,7 +1250,7 @@ void btrfs_destroy_delayed_refs(struct btrfs_transaction *trans)
 		if (!head)
 			break;
 
-		if (btrfs_delayed_ref_lock(delayed_refs, head))
+		if (!btrfs_delayed_ref_lock(delayed_refs, head))
 			continue;
 
 		spin_lock(&head->lock);
fs/btrfs/delayed-ref.h +2 -2
index a97c9df19ea0..04730c650212 100644
@@ -369,8 +369,8 @@ void btrfs_merge_delayed_refs(struct btrfs_fs_info *fs_info,
 struct btrfs_delayed_ref_head *
 btrfs_find_delayed_ref_head(struct btrfs_delayed_ref_root *delayed_refs,
 			    u64 bytenr);
-int btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,
-			   struct btrfs_delayed_ref_head *head);
+bool btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,
+			    struct btrfs_delayed_ref_head *head);
 static inline void btrfs_delayed_ref_unlock(struct btrfs_delayed_ref_head *head)
 {
 	mutex_unlock(&head->mutex);
fs/btrfs/extent-tree.c +3 -3
index 9b588ce19a74..95d749cec49e 100644
@@ -1939,7 +1939,7 @@ static struct btrfs_delayed_ref_head *btrfs_obtain_ref_head(
 	struct btrfs_delayed_ref_root *delayed_refs =
 		&trans->transaction->delayed_refs;
 	struct btrfs_delayed_ref_head *head = NULL;
-	int ret;
+	bool locked;
 
 	spin_lock(&delayed_refs->lock);
 	head = btrfs_select_ref_head(delayed_refs);
@@ -1952,7 +1952,7 @@ static struct btrfs_delayed_ref_head *btrfs_obtain_ref_head(
 	 * Grab the lock that says we are going to process all the refs for
 	 * this head
 	 */
-	ret = btrfs_delayed_ref_lock(delayed_refs, head);
+	locked = btrfs_delayed_ref_lock(delayed_refs, head);
 	spin_unlock(&delayed_refs->lock);
 
 	/*
@@ -1960,7 +1960,7 @@ static struct btrfs_delayed_ref_head *btrfs_obtain_ref_head(
 	 * that might have given someone else time to free the head.  If that's
 	 * true, it has been removed from our list and we can move on.
 	 */
-	if (ret == -EAGAIN)
+	if (!locked)
 		head = ERR_PTR(-EAGAIN);
 
 	return head;
Signature · 1 line
2.43.0
#9 lore raw

PATCH 9/18 btrfs: simplify obtaining a delayed ref head

In reply to [email protected]

From: Filipe Manana <[email protected]>

Instead of doing it in two steps outside of delayed-ref.c, leaking low level details such as locking, move the logic entirely to delayed-ref.c under btrfs_select_ref_head(), reducing code and making things simpler for the caller.

---
 fs/btrfs/delayed-ref.c | 27 ++++++++++++++++++++++-----
 fs/btrfs/delayed-ref.h |  2 --
 fs/btrfs/extent-tree.c | 35 +----------------------------------
 3 files changed, 23 insertions(+), 41 deletions(-)
fs/btrfs/delayed-ref.c +22 -5
index 2bfece87bcda..9174c6dbbce5 100644
@@ -431,8 +431,8 @@ static struct btrfs_delayed_ref_head *find_ref_head(
 	return NULL;
 }
 
-bool btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,
-			    struct btrfs_delayed_ref_head *head)
+static bool btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,
+				   struct btrfs_delayed_ref_head *head)
 {
 	lockdep_assert_held(&delayed_refs->lock);
 	if (mutex_trylock(&head->mutex))
@@ -561,8 +561,9 @@ struct btrfs_delayed_ref_head *btrfs_select_ref_head(
 		struct btrfs_delayed_ref_root *delayed_refs)
 {
 	struct btrfs_delayed_ref_head *head;
+	bool locked;
 
-	lockdep_assert_held(&delayed_refs->lock);
+	spin_lock(&delayed_refs->lock);
 again:
 	head = find_ref_head(delayed_refs, delayed_refs->run_delayed_start,
 			     true);
@@ -570,16 +571,20 @@ struct btrfs_delayed_ref_head *btrfs_select_ref_head(
 		delayed_refs->run_delayed_start = 0;
 		head = find_first_ref_head(delayed_refs);
 	}
-	if (!head)
+	if (!head) {
+		spin_unlock(&delayed_refs->lock);
 		return NULL;
+	}
 
 	while (head->processing) {
 		struct rb_node *node;
 
 		node = rb_next(&head->href_node);
 		if (!node) {
-			if (delayed_refs->run_delayed_start == 0)
+			if (delayed_refs->run_delayed_start == 0) {
+				spin_unlock(&delayed_refs->lock);
 				return NULL;
+			}
 			delayed_refs->run_delayed_start = 0;
 			goto again;
 		}
@@ -592,6 +597,18 @@ struct btrfs_delayed_ref_head *btrfs_select_ref_head(
 	delayed_refs->num_heads_ready--;
 	delayed_refs->run_delayed_start = head->bytenr +
 		head->num_bytes;
+
+	locked = btrfs_delayed_ref_lock(delayed_refs, head);
+	spin_unlock(&delayed_refs->lock);
+
+	/*
+	 * We may have dropped the spin lock to get the head mutex lock, and
+	 * that might have given someone else time to free the head.  If that's
+	 * true, it has been removed from our list and we can move on.
+	 */
+	if (!locked)
+		return ERR_PTR(-EAGAIN);
+
 	return head;
 }
 
fs/btrfs/delayed-ref.h +0 -2
index 04730c650212..956fbe5d6984 100644
@@ -369,8 +369,6 @@ void btrfs_merge_delayed_refs(struct btrfs_fs_info *fs_info,
 struct btrfs_delayed_ref_head *
 btrfs_find_delayed_ref_head(struct btrfs_delayed_ref_root *delayed_refs,
 			    u64 bytenr);
-bool btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,
-			    struct btrfs_delayed_ref_head *head);
 static inline void btrfs_delayed_ref_unlock(struct btrfs_delayed_ref_head *head)
 {
 	mutex_unlock(&head->mutex);
fs/btrfs/extent-tree.c +1 -34
index 95d749cec49e..f5320a9cdf8f 100644
@@ -1933,39 +1933,6 @@ static int cleanup_ref_head(struct btrfs_trans_handle *trans,
 	return ret;
 }
 
-static struct btrfs_delayed_ref_head *btrfs_obtain_ref_head(
-					struct btrfs_trans_handle *trans)
-{
-	struct btrfs_delayed_ref_root *delayed_refs =
-		&trans->transaction->delayed_refs;
-	struct btrfs_delayed_ref_head *head = NULL;
-	bool locked;
-
-	spin_lock(&delayed_refs->lock);
-	head = btrfs_select_ref_head(delayed_refs);
-	if (!head) {
-		spin_unlock(&delayed_refs->lock);
-		return head;
-	}
-
-	/*
-	 * Grab the lock that says we are going to process all the refs for
-	 * this head
-	 */
-	locked = btrfs_delayed_ref_lock(delayed_refs, head);
-	spin_unlock(&delayed_refs->lock);
-
-	/*
-	 * We may have dropped the spin lock to get the head mutex lock, and
-	 * that might have given someone else time to free the head.  If that's
-	 * true, it has been removed from our list and we can move on.
-	 */
-	if (!locked)
-		head = ERR_PTR(-EAGAIN);
-
-	return head;
-}
-
 static int btrfs_run_delayed_refs_for_head(struct btrfs_trans_handle *trans,
 					   struct btrfs_delayed_ref_head *locked_ref,
 					   u64 *bytes_released)
@@ -2072,7 +2039,7 @@ static noinline int __btrfs_run_delayed_refs(struct btrfs_trans_handle *trans,
 
 	do {
 		if (!locked_ref) {
-			locked_ref = btrfs_obtain_ref_head(trans);
+			locked_ref = btrfs_select_ref_head(delayed_refs);
 			if (IS_ERR_OR_NULL(locked_ref)) {
 				if (PTR_ERR(locked_ref) == -EAGAIN) {
 					continue;
Signature · 1 line
2.43.0
#10 lore raw

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

In reply to [email protected]

From: Filipe Manana <[email protected]>

The unselect_delayed_ref_head() at extent-tree.c doesn't really belong in that file as it's a delayed refs specific detail and therefore should be at delayed-ref.c. Further its inverse, btrfs_select_ref_head(), is at delayed-ref.c, so it only makes sense to have it there too.

So move unselect_delayed_ref_head() into delayed-ref.c and rename it to btrfs_unselect_ref_head() so that its name closely matches its inverse (btrfs_select_ref_head()).

---
 fs/btrfs/delayed-ref.c | 10 ++++++++++
 fs/btrfs/delayed-ref.h |  2 ++
 fs/btrfs/extent-tree.c | 16 +++-------------
 3 files changed, 15 insertions(+), 13 deletions(-)
fs/btrfs/delayed-ref.c +10 -0
index 9174c6dbbce5..ffa06f931fa8 100644
@@ -612,6 +612,16 @@ struct btrfs_delayed_ref_head *btrfs_select_ref_head(
 	return head;
 }
 
+void btrfs_unselect_ref_head(struct btrfs_delayed_ref_root *delayed_refs,
+			     struct btrfs_delayed_ref_head *head)
+{
+	spin_lock(&delayed_refs->lock);
+	head->processing = false;
+	delayed_refs->num_heads_ready++;
+	spin_unlock(&delayed_refs->lock);
+	btrfs_delayed_ref_unlock(head);
+}
+
 void btrfs_delete_ref_head(struct btrfs_delayed_ref_root *delayed_refs,
 			   struct btrfs_delayed_ref_head *head)
 {
fs/btrfs/delayed-ref.h +2 -0
index 956fbe5d6984..d70de7ee63e5 100644
@@ -378,6 +378,8 @@ void btrfs_delete_ref_head(struct btrfs_delayed_ref_root *delayed_refs,
 
 struct btrfs_delayed_ref_head *btrfs_select_ref_head(
 		struct btrfs_delayed_ref_root *delayed_refs);
+void btrfs_unselect_ref_head(struct btrfs_delayed_ref_root *delayed_refs,
+			     struct btrfs_delayed_ref_head *head);
 
 int btrfs_check_delayed_seq(struct btrfs_fs_info *fs_info, u64 seq);
 
fs/btrfs/extent-tree.c +3 -13
index f5320a9cdf8f..2e00267ad362 100644
@@ -1807,16 +1807,6 @@ select_delayed_ref(struct btrfs_delayed_ref_head *head)
 	return ref;
 }
 
-static void unselect_delayed_ref_head(struct btrfs_delayed_ref_root *delayed_refs,
-				      struct btrfs_delayed_ref_head *head)
-{
-	spin_lock(&delayed_refs->lock);
-	head->processing = false;
-	delayed_refs->num_heads_ready++;
-	spin_unlock(&delayed_refs->lock);
-	btrfs_delayed_ref_unlock(head);
-}
-
 static struct btrfs_delayed_extent_op *cleanup_extent_op(
 				struct btrfs_delayed_ref_head *head)
 {
@@ -1891,7 +1881,7 @@ static int cleanup_ref_head(struct btrfs_trans_handle *trans,
 
 	ret = run_and_cleanup_extent_op(trans, head);
 	if (ret < 0) {
-		unselect_delayed_ref_head(delayed_refs, head);
+		btrfs_unselect_ref_head(delayed_refs, head);
 		btrfs_debug(fs_info, "run_delayed_extent_op returned %d", ret);
 		return ret;
 	} else if (ret) {
@@ -1953,7 +1943,7 @@ static int btrfs_run_delayed_refs_for_head(struct btrfs_trans_handle *trans,
 		if (ref->seq &&
 		    btrfs_check_delayed_seq(fs_info, ref->seq)) {
 			spin_unlock(&locked_ref->lock);
-			unselect_delayed_ref_head(delayed_refs, locked_ref);
+			btrfs_unselect_ref_head(delayed_refs, locked_ref);
 			return -EAGAIN;
 		}
 
@@ -2001,7 +1991,7 @@ static int btrfs_run_delayed_refs_for_head(struct btrfs_trans_handle *trans,
 
 		btrfs_free_delayed_extent_op(extent_op);
 		if (ret) {
-			unselect_delayed_ref_head(delayed_refs, locked_ref);
+			btrfs_unselect_ref_head(delayed_refs, locked_ref);
 			btrfs_put_delayed_ref(ref);
 			return ret;
 		}
Signature · 1 line
2.43.0
#11 lore raw

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

In reply to [email protected]

From: Filipe Manana <[email protected]>

One of the following patches in the series will need to access fs_info in the function find_ref_head(), so pass a fs_info argument to it as well as to the functions btrfs_select_ref_head() and btrfs_find_delayed_ref_head() which call find_ref_head().

---
 fs/btrfs/backref.c     |  3 ++-
 fs/btrfs/delayed-ref.c | 12 ++++++++----
 fs/btrfs/delayed-ref.h |  4 +++-
 fs/btrfs/extent-tree.c | 10 +++++-----
 4 files changed, 18 insertions(+), 11 deletions(-)
fs/btrfs/backref.c +2 -1
index f8e1d5b2c512..04f53ca548e1 100644
@@ -1442,7 +1442,8 @@ static int find_parent_nodes(struct btrfs_backref_walk_ctx *ctx,
 		 */
 		delayed_refs = &ctx->trans->transaction->delayed_refs;
 		spin_lock(&delayed_refs->lock);
-		head = btrfs_find_delayed_ref_head(delayed_refs, ctx->bytenr);
+		head = btrfs_find_delayed_ref_head(ctx->fs_info, delayed_refs,
+						   ctx->bytenr);
 		if (head) {
 			if (!mutex_trylock(&head->mutex)) {
 				refcount_inc(&head->refs);
fs/btrfs/delayed-ref.c +8 -4
index ffa06f931fa8..81f7a515dd0e 100644
@@ -399,6 +399,7 @@ static struct btrfs_delayed_ref_head *find_first_ref_head(
  * is given, the next bigger entry is returned if no exact match is found.
  */
 static struct btrfs_delayed_ref_head *find_ref_head(
+		struct btrfs_fs_info *fs_info,
 		struct btrfs_delayed_ref_root *dr, u64 bytenr,
 		bool return_bigger)
 {
@@ -558,6 +559,7 @@ int btrfs_check_delayed_seq(struct btrfs_fs_info *fs_info, u64 seq)
 }
 
 struct btrfs_delayed_ref_head *btrfs_select_ref_head(
+		struct btrfs_fs_info *fs_info,
 		struct btrfs_delayed_ref_root *delayed_refs)
 {
 	struct btrfs_delayed_ref_head *head;
@@ -565,8 +567,8 @@ struct btrfs_delayed_ref_head *btrfs_select_ref_head(
 
 	spin_lock(&delayed_refs->lock);
 again:
-	head = find_ref_head(delayed_refs, delayed_refs->run_delayed_start,
-			     true);
+	head = find_ref_head(fs_info, delayed_refs,
+			     delayed_refs->run_delayed_start, true);
 	if (!head && delayed_refs->run_delayed_start != 0) {
 		delayed_refs->run_delayed_start = 0;
 		head = find_first_ref_head(delayed_refs);
@@ -1188,11 +1190,13 @@ void btrfs_put_delayed_ref(struct btrfs_delayed_ref_node *ref)
  * head node if found, or NULL if not.
  */
 struct btrfs_delayed_ref_head *
-btrfs_find_delayed_ref_head(struct btrfs_delayed_ref_root *delayed_refs, u64 bytenr)
+btrfs_find_delayed_ref_head(struct btrfs_fs_info *fs_info,
+			    struct btrfs_delayed_ref_root *delayed_refs,
+			    u64 bytenr)
 {
 	lockdep_assert_held(&delayed_refs->lock);
 
-	return find_ref_head(delayed_refs, bytenr, false);
+	return find_ref_head(fs_info, delayed_refs, bytenr, false);
 }
 
 static int find_comp(struct btrfs_delayed_ref_node *entry, u64 root, u64 parent)
fs/btrfs/delayed-ref.h +3 -1
index d70de7ee63e5..acd142b01c12 100644
@@ -367,7 +367,8 @@ void btrfs_merge_delayed_refs(struct btrfs_fs_info *fs_info,
 			      struct btrfs_delayed_ref_head *head);
 
 struct btrfs_delayed_ref_head *
-btrfs_find_delayed_ref_head(struct btrfs_delayed_ref_root *delayed_refs,
+btrfs_find_delayed_ref_head(struct btrfs_fs_info *fs_info,
+			    struct btrfs_delayed_ref_root *delayed_refs,
 			    u64 bytenr);
 static inline void btrfs_delayed_ref_unlock(struct btrfs_delayed_ref_head *head)
 {
@@ -377,6 +378,7 @@ void btrfs_delete_ref_head(struct btrfs_delayed_ref_root *delayed_refs,
 			   struct btrfs_delayed_ref_head *head);
 
 struct btrfs_delayed_ref_head *btrfs_select_ref_head(
+		struct btrfs_fs_info *fs_info,
 		struct btrfs_delayed_ref_root *delayed_refs);
 void btrfs_unselect_ref_head(struct btrfs_delayed_ref_root *delayed_refs,
 			     struct btrfs_delayed_ref_head *head);
fs/btrfs/extent-tree.c +5 -5
index 2e00267ad362..40f16deb1c0f 100644
@@ -182,7 +182,7 @@ int btrfs_lookup_extent_info(struct btrfs_trans_handle *trans,
 
 	delayed_refs = &trans->transaction->delayed_refs;
 	spin_lock(&delayed_refs->lock);
-	head = btrfs_find_delayed_ref_head(delayed_refs, bytenr);
+	head = btrfs_find_delayed_ref_head(fs_info, delayed_refs, bytenr);
 	if (head) {
 		if (!mutex_trylock(&head->mutex)) {
 			refcount_inc(&head->refs);
@@ -2029,7 +2029,7 @@ static noinline int __btrfs_run_delayed_refs(struct btrfs_trans_handle *trans,
 
 	do {
 		if (!locked_ref) {
-			locked_ref = btrfs_select_ref_head(delayed_refs);
+			locked_ref = btrfs_select_ref_head(fs_info, delayed_refs);
 			if (IS_ERR_OR_NULL(locked_ref)) {
 				if (PTR_ERR(locked_ref) == -EAGAIN) {
 					continue;
@@ -2231,7 +2231,7 @@ static noinline int check_delayed_ref(struct btrfs_root *root,
 
 	delayed_refs = &cur_trans->delayed_refs;
 	spin_lock(&delayed_refs->lock);
-	head = btrfs_find_delayed_ref_head(delayed_refs, bytenr);
+	head = btrfs_find_delayed_ref_head(root->fs_info, delayed_refs, bytenr);
 	if (!head) {
 		spin_unlock(&delayed_refs->lock);
 		btrfs_put_transaction(cur_trans);
@@ -3339,7 +3339,7 @@ static noinline int check_ref_cleanup(struct btrfs_trans_handle *trans,
 
 	delayed_refs = &trans->transaction->delayed_refs;
 	spin_lock(&delayed_refs->lock);
-	head = btrfs_find_delayed_ref_head(delayed_refs, bytenr);
+	head = btrfs_find_delayed_ref_head(trans->fs_info, delayed_refs, bytenr);
 	if (!head)
 		goto out_delayed_unlock;
 
@@ -5474,7 +5474,7 @@ static int check_ref_exists(struct btrfs_trans_handle *trans,
 	 */
 	delayed_refs = &trans->transaction->delayed_refs;
 	spin_lock(&delayed_refs->lock);
-	head = btrfs_find_delayed_ref_head(delayed_refs, bytenr);
+	head = btrfs_find_delayed_ref_head(root->fs_info, delayed_refs, bytenr);
 	if (!head)
 		goto out;
 	if (!mutex_trylock(&head->mutex)) {
Signature · 1 line
2.43.0
#12 lore raw

PATCH 12/18 btrfs: pass fs_info to btrfs_cleanup_ref_head_accounting

In reply to [email protected]

From: Filipe Manana <[email protected]>

One of the following patches in the series will need to access fs_info at btrfs_cleanup_ref_head_accounting(), so pass a fs_info argument to it.

---
 fs/btrfs/delayed-ref.c | 5 +++--
 fs/btrfs/delayed-ref.h | 3 ++-
 fs/btrfs/extent-tree.c | 9 +++++----
 3 files changed, 10 insertions(+), 7 deletions(-)
fs/btrfs/delayed-ref.c +3 -2
index 81f7a515dd0e..e81aa112d137 100644
@@ -624,7 +624,8 @@ void btrfs_unselect_ref_head(struct btrfs_delayed_ref_root *delayed_refs,
 	btrfs_delayed_ref_unlock(head);
 }
 
-void btrfs_delete_ref_head(struct btrfs_delayed_ref_root *delayed_refs,
+void btrfs_delete_ref_head(struct btrfs_fs_info *fs_info,
+			   struct btrfs_delayed_ref_root *delayed_refs,
 			   struct btrfs_delayed_ref_head *head)
 {
 	lockdep_assert_held(&delayed_refs->lock);
@@ -1294,7 +1295,7 @@ void btrfs_destroy_delayed_refs(struct btrfs_transaction *trans)
 		if (head->must_insert_reserved)
 			pin_bytes = true;
 		btrfs_free_delayed_extent_op(head->extent_op);
-		btrfs_delete_ref_head(delayed_refs, head);
+		btrfs_delete_ref_head(fs_info, delayed_refs, head);
 		spin_unlock(&head->lock);
 		spin_unlock(&delayed_refs->lock);
 		mutex_unlock(&head->mutex);
fs/btrfs/delayed-ref.h +2 -1
index acd142b01c12..c3749e6cc374 100644
@@ -374,7 +374,8 @@ static inline void btrfs_delayed_ref_unlock(struct btrfs_delayed_ref_head *head)
 {
 	mutex_unlock(&head->mutex);
 }
-void btrfs_delete_ref_head(struct btrfs_delayed_ref_root *delayed_refs,
+void btrfs_delete_ref_head(struct btrfs_fs_info *fs_info,
+			   struct btrfs_delayed_ref_root *delayed_refs,
 			   struct btrfs_delayed_ref_head *head);
 
 struct btrfs_delayed_ref_head *btrfs_select_ref_head(
fs/btrfs/extent-tree.c +5 -4
index 40f16deb1c0f..33f911476a4d 100644
@@ -1900,7 +1900,7 @@ static int cleanup_ref_head(struct btrfs_trans_handle *trans,
 		spin_unlock(&delayed_refs->lock);
 		return 1;
 	}
-	btrfs_delete_ref_head(delayed_refs, head);
+	btrfs_delete_ref_head(fs_info, delayed_refs, head);
 	spin_unlock(&head->lock);
 	spin_unlock(&delayed_refs->lock);
 
@@ -3333,13 +3333,14 @@ static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
 static noinline int check_ref_cleanup(struct btrfs_trans_handle *trans,
 				      u64 bytenr)
 {
+	struct btrfs_fs_info *fs_info = trans->fs_info;
 	struct btrfs_delayed_ref_head *head;
 	struct btrfs_delayed_ref_root *delayed_refs;
 	int ret = 0;
 
 	delayed_refs = &trans->transaction->delayed_refs;
 	spin_lock(&delayed_refs->lock);
-	head = btrfs_find_delayed_ref_head(trans->fs_info, delayed_refs, bytenr);
+	head = btrfs_find_delayed_ref_head(fs_info, delayed_refs, bytenr);
 	if (!head)
 		goto out_delayed_unlock;
 
@@ -3357,7 +3358,7 @@ static noinline int check_ref_cleanup(struct btrfs_trans_handle *trans,
 	if (!mutex_trylock(&head->mutex))
 		goto out;
 
-	btrfs_delete_ref_head(delayed_refs, head);
+	btrfs_delete_ref_head(fs_info, delayed_refs, head);
 	head->processing = false;
 
 	spin_unlock(&head->lock);
@@ -3367,7 +3368,7 @@ static noinline int check_ref_cleanup(struct btrfs_trans_handle *trans,
 	if (head->must_insert_reserved)
 		ret = 1;
 
-	btrfs_cleanup_ref_head_accounting(trans->fs_info, delayed_refs, head);
+	btrfs_cleanup_ref_head_accounting(fs_info, delayed_refs, head);
 	mutex_unlock(&head->mutex);
 	btrfs_put_delayed_ref_head(head);
 	return ret;
Signature · 1 line
2.43.0
#13 lore raw

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

In reply to [email protected]

From: Filipe Manana <[email protected]>

We have 3 callers for find_ref_head() so assert at find_ref_head() that we have the delayed refs lock held, removing the assertion from one of its callers (btrfs_find_delayed_ref_head()).

---
 fs/btrfs/delayed-ref.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
fs/btrfs/delayed-ref.c +2 -2
index e81aa112d137..3aeb2c79c1ae 100644
@@ -407,6 +407,8 @@ static struct btrfs_delayed_ref_head *find_ref_head(
 	struct rb_node *n;
 	struct btrfs_delayed_ref_head *entry;
 
+	lockdep_assert_held(&dr->lock);
+
 	n = root->rb_node;
 	entry = NULL;
 	while (n) {
@@ -1195,8 +1197,6 @@ btrfs_find_delayed_ref_head(struct btrfs_fs_info *fs_info,
 			    struct btrfs_delayed_ref_root *delayed_refs,
 			    u64 bytenr)
 {
-	lockdep_assert_held(&delayed_refs->lock);
-
 	return find_ref_head(fs_info, delayed_refs, bytenr, false);
 }
 
Signature · 1 line
2.43.0
#14 lore raw

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

In reply to [email protected]

From: Filipe Manana <[email protected]>

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

---
 fs/btrfs/delayed-ref.c | 2 ++
 1 file changed, 2 insertions(+)
fs/btrfs/delayed-ref.c +2 -0
index 3aeb2c79c1ae..a8cf76f44b2b 100644
@@ -384,6 +384,8 @@ static struct btrfs_delayed_ref_head *find_first_ref_head(
 	struct rb_node *n;
 	struct btrfs_delayed_ref_head *entry;
 
+	lockdep_assert_held(&dr->lock);
+
 	n = rb_first_cached(&dr->href_root);
 	if (!n)
 		return NULL;
Signature · 1 line
2.43.0
#15 lore raw

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

In reply to [email protected]

From: Filipe Manana <[email protected]>

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

---
 fs/btrfs/delayed-ref.c | 1 +
 1 file changed, 1 insertion(+)
fs/btrfs/delayed-ref.c +1 -0
index a8cf76f44b2b..2b6a636ba4b5 100644
@@ -886,6 +886,7 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,
 	bool qrecord_inserted = false;
 
 	delayed_refs = &trans->transaction->delayed_refs;
+	lockdep_assert_held(&delayed_refs->lock);
 
 	/* Record qgroup extent info if provided */
 	if (qrecord) {
Signature · 1 line
2.43.0
#16 lore raw

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

In reply to [email protected]

From: Filipe Manana <[email protected]>

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

---
 fs/btrfs/delayed-ref.h | 20 +++++++++++++++++---
 1 file changed, 17 insertions(+), 3 deletions(-)
fs/btrfs/delayed-ref.h +17 -3
index c3749e6cc374..0a9f4d7dd87b 100644
@@ -213,19 +213,33 @@ struct btrfs_delayed_ref_root {
 	 */
 	struct xarray dirty_extents;
 
-	/* this spin lock protects the rbtree and the entries inside */
+	/*
+	 * Protects the rbtree href_root, its entries and the following fields:
+	 * num_heads, num_heads_ready, pending_csums and run_delayed_start.
+	 */
 	spinlock_t lock;
 
-	/* total number of head nodes in tree */
+	/* Total number of head refs, protected by the spinlock 'lock'. */
 	unsigned long num_heads;
 
-	/* total number of head nodes ready for processing */
+	/*
+	 * Total number of head refs ready for processing, protected by the
+	 * spinlock 'lock'.
+	 */
 	unsigned long num_heads_ready;
 
+	/*
+	 * Track space reserved for deleting csums of data extents.
+	 * Protected by the spinlock 'lock'.
+	 */
 	u64 pending_csums;
 
 	unsigned long flags;
 
+	/*
+	 * Track from which bytenr to start searching ref heads.
+	 * Protected by the spinlock 'lock'.
+	 */
 	u64 run_delayed_start;
 
 	/*
Signature · 1 line
2.43.0
#17 lore raw

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

In reply to [email protected]

From: Filipe Manana <[email protected]>

Currently we use a red black tree (rb-tree) to track the delayed ref heads (in struct btrfs_delayed_ref_root::href_root). This however is not very efficient when the number of delayed ref heads is large (and it's very common to be at least in the order of thousands) since rb-trees are binary trees. For example for 10K delayed ref heads, the tree has a depth of 13. Besides that, inserting into the tree requires navigating through it and pulling useless cache lines in the process since the red black tree nodes are embedded within the delayed ref head structure - on the other hand, by being embedded, it requires no extra memory allocations.

We can improve this by using an xarray instead which has a much higher branching factor than a red black tree (binary balanced tree) and is more cache friendly and behaves like a resizable array, with a much better search and insertion complexity than a red black tree. This only has one small disadvantage which is that insertion will sometimes require allocating memory for the xarray - which may fail (not that often since it uses a kmem_cache) - but on the other hand we can reduce the delayed ref head structure size by 24 bytes (from 152 down to 128 bytes) after removing the embedded red black tree node, meaning than we can now fit 32 delayed ref heads per 4K page instead of 26, and that gain compensates for the occasional memory allocations needed for the xarray nodes. We also end up using only 2 cache lines instead of 3 per delayed ref head.

Running the following fs_mark test showed some improvements:

    $ cat test.sh
    #!/bin/bash
    DEV=/dev/nullb0
    MNT=/mnt/nullb0
    MOUNT_OPTIONS="-o ssd"
    FILES=100000
    THREADS=$(nproc --all)

    echo "performance" | \
        tee /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor

    mkfs.btrfs -f $DEV
    mount $MOUNT_OPTIONS $DEV $MNT

    OPTS="-S 0 -L 5 -n $FILES -s 0 -t $THREADS -k"
    for ((i = 1; i <= $THREADS; i++)); do
        OPTS="$OPTS -d $MNT/d$i"
    done

    fs_mark $OPTS

    umount $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
---
 fs/btrfs/delayed-ref.c | 192 +++++++++++++++++++----------------------
 fs/btrfs/delayed-ref.h |  26 +++---
 fs/btrfs/extent-tree.c |   2 +-
 fs/btrfs/transaction.c |   5 +-
 4 files changed, 106 insertions(+), 119 deletions(-)
fs/btrfs/delayed-ref.c +88 -104
index 2b6a636ba4b5..e4ca5285e614 100644
@@ -314,39 +314,6 @@ static int comp_refs(struct btrfs_delayed_ref_node *ref1,
 	return 0;
 }
 
-/* insert a new ref to head ref rbtree */
-static struct btrfs_delayed_ref_head *htree_insert(struct rb_root_cached *root,
-						   struct rb_node *node)
-{
-	struct rb_node **p = &root->rb_root.rb_node;
-	struct rb_node *parent_node = NULL;
-	struct btrfs_delayed_ref_head *entry;
-	struct btrfs_delayed_ref_head *ins;
-	u64 bytenr;
-	bool leftmost = true;
-
-	ins = rb_entry(node, struct btrfs_delayed_ref_head, href_node);
-	bytenr = ins->bytenr;
-	while (*p) {
-		parent_node = *p;
-		entry = rb_entry(parent_node, struct btrfs_delayed_ref_head,
-				 href_node);
-
-		if (bytenr < entry->bytenr) {
-			p = &(*p)->rb_left;
-		} else if (bytenr > entry->bytenr) {
-			p = &(*p)->rb_right;
-			leftmost = false;
-		} else {
-			return entry;
-		}
-	}
-
-	rb_link_node(node, parent_node, p);
-	rb_insert_color_cached(node, root, leftmost);
-	return NULL;
-}
-
 static struct btrfs_delayed_ref_node* tree_insert(struct rb_root_cached *root,
 		struct btrfs_delayed_ref_node *ins)
 {
@@ -381,18 +348,11 @@ static struct btrfs_delayed_ref_node* tree_insert(struct rb_root_cached *root,
 static struct btrfs_delayed_ref_head *find_first_ref_head(
 		struct btrfs_delayed_ref_root *dr)
 {
-	struct rb_node *n;
-	struct btrfs_delayed_ref_head *entry;
+	unsigned long from = 0;
 
 	lockdep_assert_held(&dr->lock);
 
-	n = rb_first_cached(&dr->href_root);
-	if (!n)
-		return NULL;
-
-	entry = rb_entry(n, struct btrfs_delayed_ref_head, href_node);
-
-	return entry;
+	return xa_find(&dr->head_refs, &from, ULONG_MAX, XA_PRESENT);
 }
 
 /*
@@ -405,35 +365,22 @@ static struct btrfs_delayed_ref_head *find_ref_head(
 		struct btrfs_delayed_ref_root *dr, u64 bytenr,
 		bool return_bigger)
 {
-	struct rb_root *root = &dr->href_root.rb_root;
-	struct rb_node *n;
+	const unsigned long target_index = (bytenr >> fs_info->sectorsize_bits);
+	unsigned long found_index = target_index;
 	struct btrfs_delayed_ref_head *entry;
 
 	lockdep_assert_held(&dr->lock);
 
-	n = root->rb_node;
-	entry = NULL;
-	while (n) {
-		entry = rb_entry(n, struct btrfs_delayed_ref_head, href_node);
+	entry = xa_find(&dr->head_refs, &found_index, ULONG_MAX, XA_PRESENT);
+	if (!entry)
+		return NULL;
+
+	ASSERT(found_index >= target_index);
 
-		if (bytenr < entry->bytenr)
-			n = n->rb_left;
-		else if (bytenr > entry->bytenr)
-			n = n->rb_right;
-		else
-			return entry;
-	}
-	if (entry && return_bigger) {
-		if (bytenr > entry->bytenr) {
-			n = rb_next(&entry->href_node);
-			if (!n)
-				return NULL;
-			entry = rb_entry(n, struct btrfs_delayed_ref_head,
-					 href_node);
-		}
-		return entry;
-	}
-	return NULL;
+	if (found_index != target_index && !return_bigger)
+		return NULL;
+
+	return entry;
 }
 
 static bool btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,
@@ -448,7 +395,7 @@ static bool btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,
 
 	mutex_lock(&head->mutex);
 	spin_lock(&delayed_refs->lock);
-	if (RB_EMPTY_NODE(&head->href_node)) {
+	if (!head->tracked) {
 		mutex_unlock(&head->mutex);
 		btrfs_put_delayed_ref_head(head);
 		return false;
@@ -567,35 +514,27 @@ struct btrfs_delayed_ref_head *btrfs_select_ref_head(
 		struct btrfs_delayed_ref_root *delayed_refs)
 {
 	struct btrfs_delayed_ref_head *head;
+	unsigned long start_index;
+	unsigned long found_index;
+	bool found_head = false;
 	bool locked;
 
 	spin_lock(&delayed_refs->lock);
 again:
-	head = find_ref_head(fs_info, delayed_refs,
-			     delayed_refs->run_delayed_start, true);
-	if (!head && delayed_refs->run_delayed_start != 0) {
-		delayed_refs->run_delayed_start = 0;
-		head = find_first_ref_head(delayed_refs);
-	}
-	if (!head) {
-		spin_unlock(&delayed_refs->lock);
-		return NULL;
+	start_index = (delayed_refs->run_delayed_start >> fs_info->sectorsize_bits);
+	xa_for_each_start(&delayed_refs->head_refs, found_index, head, start_index) {
+		if (!head->processing) {
+			found_head = true;
+			break;
+		}
 	}
-
-	while (head->processing) {
-		struct rb_node *node;
-
-		node = rb_next(&head->href_node);
-		if (!node) {
-			if (delayed_refs->run_delayed_start == 0) {
-				spin_unlock(&delayed_refs->lock);
-				return NULL;
-			}
-			delayed_refs->run_delayed_start = 0;
-			goto again;
+	if (!found_head) {
+		if (delayed_refs->run_delayed_start == 0) {
+			spin_unlock(&delayed_refs->lock);
+			return NULL;
 		}
-		head = rb_entry(node, struct btrfs_delayed_ref_head,
-				href_node);
+		delayed_refs->run_delayed_start = 0;
+		goto again;
 	}
 
 	head->processing = true;
@@ -632,11 +571,13 @@ void btrfs_delete_ref_head(struct btrfs_fs_info *fs_info,
 			   struct btrfs_delayed_ref_root *delayed_refs,
 			   struct btrfs_delayed_ref_head *head)
 {
+	const unsigned long index = (head->bytenr >> fs_info->sectorsize_bits);
+
 	lockdep_assert_held(&delayed_refs->lock);
 	lockdep_assert_held(&head->lock);
 
-	rb_erase_cached(&head->href_node, &delayed_refs->href_root);
-	RB_CLEAR_NODE(&head->href_node);
+	xa_erase(&delayed_refs->head_refs, index);
+	head->tracked = false;
 	delayed_refs->num_heads--;
 	if (!head->processing)
 		delayed_refs->num_heads_ready--;
@@ -845,7 +786,7 @@ static void init_delayed_ref_head(struct btrfs_delayed_ref_head *head_ref,
 	head_ref->is_system = (generic_ref->ref_root == BTRFS_CHUNK_TREE_OBJECTID);
 	head_ref->ref_tree = RB_ROOT_CACHED;
 	INIT_LIST_HEAD(&head_ref->ref_add_list);
-	RB_CLEAR_NODE(&head_ref->href_node);
+	head_ref->tracked = false;
 	head_ref->processing = false;
 	head_ref->total_ref_mod = count_mod;
 	spin_lock_init(&head_ref->lock);
@@ -883,11 +824,24 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,
 	struct btrfs_fs_info *fs_info = trans->fs_info;
 	struct btrfs_delayed_ref_head *existing;
 	struct btrfs_delayed_ref_root *delayed_refs;
+	const unsigned long index = (head_ref->bytenr >> fs_info->sectorsize_bits);
 	bool qrecord_inserted = false;
 
 	delayed_refs = &trans->transaction->delayed_refs;
 	lockdep_assert_held(&delayed_refs->lock);
 
+#if BITS_PER_LONG == 32
+	if (head_ref->bytenr >= MAX_LFS_FILESIZE) {
+		if (qrecord)
+			xa_release(&delayed_refs->dirty_extents, index);
+		btrfs_err_rl(fs_info,
+"delayed ref head %llu is beyond 32bit page cache and xarray index limit",
+			     head_ref->bytenr);
+		btrfs_err_32bit_limit(fs_info);
+		return ERR_PTR(-EOVERFLOW);
+	}
+#endif
+
 	/* Record qgroup extent info if provided */
 	if (qrecord) {
 		int ret;
@@ -896,8 +850,7 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,
 						       head_ref->bytenr);
 		if (ret) {
 			/* Clean up if insertion fails or item exists. */
-			xa_release(&delayed_refs->dirty_extents,
-				   head_ref->bytenr >> fs_info->sectorsize_bits);
+			xa_release(&delayed_refs->dirty_extents, index);
 			/* Caller responsible for freeing qrecord on error. */
 			if (ret < 0)
 				return ERR_PTR(ret);
@@ -909,8 +862,7 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,
 
 	trace_add_delayed_ref_head(fs_info, head_ref, action);
 
-	existing = htree_insert(&delayed_refs->href_root,
-				&head_ref->href_node);
+	existing = xa_load(&delayed_refs->head_refs, index);
 	if (existing) {
 		update_existing_head_ref(trans, existing, head_ref);
 		/*
@@ -920,6 +872,19 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,
 		kmem_cache_free(btrfs_delayed_ref_head_cachep, head_ref);
 		head_ref = existing;
 	} else {
+		existing = xa_store(&delayed_refs->head_refs, index, head_ref, GFP_ATOMIC);
+		if (xa_is_err(existing)) {
+			/* Memory was preallocated by the caller. */
+			ASSERT(xa_err(existing) != -ENOMEM);
+			return ERR_CAST(existing);
+		} else if (WARN_ON(existing)) {
+			/*
+			 * Shouldn't happen we just did a lookup before under
+			 * delayed_refs->lock.
+			 */
+			return ERR_PTR(-EEXIST);
+		}
+		head_ref->tracked = true;
 		/*
 		 * We reserve the amount of bytes needed to delete csums when
 		 * adding the ref head and not when adding individual drop refs
@@ -1040,6 +1005,8 @@ static int add_delayed_ref(struct btrfs_trans_handle *trans,
 	struct btrfs_delayed_ref_head *new_head_ref;
 	struct btrfs_delayed_ref_root *delayed_refs;
 	struct btrfs_qgroup_extent_record *record = NULL;
+	const unsigned long index = (generic_ref->bytenr >> fs_info->sectorsize_bits);
+	bool qrecord_reserved = false;
 	bool qrecord_inserted;
 	int action = generic_ref->action;
 	bool merged;
@@ -1055,25 +1022,32 @@ static int add_delayed_ref(struct btrfs_trans_handle *trans,
 		goto free_node;
 	}
 
+	delayed_refs = &trans->transaction->delayed_refs;
+
 	if (btrfs_qgroup_full_accounting(fs_info) && !generic_ref->skip_qgroup) {
 		record = kzalloc(sizeof(*record), GFP_NOFS);
 		if (!record) {
 			ret = -ENOMEM;
 			goto free_head_ref;
 		}
-		if (xa_reserve(&trans->transaction->delayed_refs.dirty_extents,
-			       generic_ref->bytenr >> fs_info->sectorsize_bits,
-			       GFP_NOFS)) {
+		if (xa_reserve(&delayed_refs->dirty_extents, index, GFP_NOFS)) {
 			ret = -ENOMEM;
 			goto free_record;
 		}
+		qrecord_reserved = true;
+	}
+
+	ret = xa_reserve(&delayed_refs->head_refs, index, GFP_NOFS);
+	if (ret) {
+		if (qrecord_reserved)
+			xa_release(&delayed_refs->dirty_extents, index);
+		goto free_record;
 	}
 
 	init_delayed_ref_common(fs_info, node, generic_ref);
 	init_delayed_ref_head(head_ref, generic_ref, record, reserved);
 	head_ref->extent_op = extent_op;
 
-	delayed_refs = &trans->transaction->delayed_refs;
 	spin_lock(&delayed_refs->lock);
 
 	/*
@@ -1083,6 +1057,7 @@ static int add_delayed_ref(struct btrfs_trans_handle *trans,
 	new_head_ref = add_delayed_ref_head(trans, head_ref, record,
 					    action, &qrecord_inserted);
 	if (IS_ERR(new_head_ref)) {
+		xa_release(&delayed_refs->head_refs, index);
 		spin_unlock(&delayed_refs->lock);
 		ret = PTR_ERR(new_head_ref);
 		goto free_record;
@@ -1145,6 +1120,7 @@ int btrfs_add_delayed_extent_op(struct btrfs_trans_handle *trans,
 				u64 bytenr, u64 num_bytes, u8 level,
 				struct btrfs_delayed_extent_op *extent_op)
 {
+	const unsigned long index = (bytenr >> trans->fs_info->sectorsize_bits);
 	struct btrfs_delayed_ref_head *head_ref;
 	struct btrfs_delayed_ref_head *head_ref_ret;
 	struct btrfs_delayed_ref_root *delayed_refs;
@@ -1155,6 +1131,7 @@ int btrfs_add_delayed_extent_op(struct btrfs_trans_handle *trans,
 		.num_bytes = num_bytes,
 		.tree_ref.level = level,
 	};
+	int ret;
 
 	head_ref = kmem_cache_alloc(btrfs_delayed_ref_head_cachep, GFP_NOFS);
 	if (!head_ref)
@@ -1164,16 +1141,23 @@ int btrfs_add_delayed_extent_op(struct btrfs_trans_handle *trans,
 	head_ref->extent_op = extent_op;
 
 	delayed_refs = &trans->transaction->delayed_refs;
-	spin_lock(&delayed_refs->lock);
 
+	ret = xa_reserve(&delayed_refs->head_refs, index, GFP_NOFS);
+	if (ret) {
+		kmem_cache_free(btrfs_delayed_ref_head_cachep, head_ref);
+		return ret;
+	}
+
+	spin_lock(&delayed_refs->lock);
 	head_ref_ret = add_delayed_ref_head(trans, head_ref, NULL,
 					    BTRFS_UPDATE_DELAYED_HEAD, NULL);
-	spin_unlock(&delayed_refs->lock);
-
 	if (IS_ERR(head_ref_ret)) {
+		xa_release(&delayed_refs->head_refs, index);
+		spin_unlock(&delayed_refs->lock);
 		kmem_cache_free(btrfs_delayed_ref_head_cachep, head_ref);
 		return PTR_ERR(head_ref_ret);
 	}
+	spin_unlock(&delayed_refs->lock);
 
 	/*
 	 * Need to update the delayed_refs_rsv with any changes we may have
fs/btrfs/delayed-ref.h +15 -11
index 0a9f4d7dd87b..c7c4d62744b4 100644
@@ -122,12 +122,6 @@ struct btrfs_delayed_extent_op {
 struct btrfs_delayed_ref_head {
 	u64 bytenr;
 	u64 num_bytes;
-	/*
-	 * For insertion into struct btrfs_delayed_ref_root::href_root.
-	 * Keep it in the same cache line as 'bytenr' for more efficient
-	 * searches in the rbtree.
-	 */
-	struct rb_node href_node;
 	/*
 	 * the mutex is held while running the refs, and it is also
 	 * held when checking the sum of reference modifications.
@@ -191,6 +185,11 @@ struct btrfs_delayed_ref_head {
 	bool is_data;
 	bool is_system;
 	bool processing;
+	/*
+	 * Indicate if it's currently in the data structure that tracks head
+	 * refs (struct btrfs_delayed_ref_root::head_refs).
+	 */
+	bool tracked;
 };
 
 enum btrfs_delayed_ref_flags {
@@ -199,22 +198,27 @@ enum btrfs_delayed_ref_flags {
 };
 
 struct btrfs_delayed_ref_root {
-	/* head ref rbtree */
-	struct rb_root_cached href_root;
-
 	/*
-	 * Track dirty extent records.
+	 * Track head references.
 	 * The keys correspond to the logical address of the extent ("bytenr")
 	 * right shifted by fs_info->sectorsize_bits. This is both to get a more
 	 * dense index space (optimizes xarray structure) and because indexes in
 	 * xarrays are of "unsigned long" type, meaning they are 32 bits wide on
 	 * 32 bits platforms, limiting the extent range to 4G which is too low
 	 * and makes it unusable (truncated index values) on 32 bits platforms.
+	 * Protected by the spinlock 'lock' defined below.
+	 */
+	struct xarray head_refs;
+
+	/*
+	 * Track dirty extent records.
+	 * The keys correspond to the logical address of the extent ("bytenr")
+	 * right shifted by fs_info->sectorsize_bits, for same reasons as above.
 	 */
 	struct xarray dirty_extents;
 
 	/*
-	 * Protects the rbtree href_root, its entries and the following fields:
+	 * Protects the xarray head_refs, its entries and the following fields:
 	 * num_heads, num_heads_ready, pending_csums and run_delayed_start.
 	 */
 	spinlock_t lock;
fs/btrfs/extent-tree.c +1 -1
index 33f911476a4d..1571b5a1d905 100644
@@ -2176,7 +2176,7 @@ int btrfs_run_delayed_refs(struct btrfs_trans_handle *trans, u64 min_bytes)
 		btrfs_create_pending_block_groups(trans);
 
 		spin_lock(&delayed_refs->lock);
-		if (RB_EMPTY_ROOT(&delayed_refs->href_root.rb_root)) {
+		if (xa_empty(&delayed_refs->head_refs)) {
 			spin_unlock(&delayed_refs->lock);
 			return 0;
 		}
fs/btrfs/transaction.c +2 -3
index 9ccf68ab53f9..dc0b837efd5d 100644
@@ -141,8 +141,7 @@ void btrfs_put_transaction(struct btrfs_transaction *transaction)
 	WARN_ON(refcount_read(&transaction->use_count) == 0);
 	if (refcount_dec_and_test(&transaction->use_count)) {
 		BUG_ON(!list_empty(&transaction->list));
-		WARN_ON(!RB_EMPTY_ROOT(
-				&transaction->delayed_refs.href_root.rb_root));
+		WARN_ON(!xa_empty(&transaction->delayed_refs.head_refs));
 		WARN_ON(!xa_empty(&transaction->delayed_refs.dirty_extents));
 		if (transaction->delayed_refs.pending_csums)
 			btrfs_err(transaction->fs_info,
@@ -349,7 +348,7 @@ static noinline int join_transaction(struct btrfs_fs_info *fs_info,
 
 	memset(&cur_trans->delayed_refs, 0, sizeof(cur_trans->delayed_refs));
 
-	cur_trans->delayed_refs.href_root = RB_ROOT_CACHED;
+	xa_init(&cur_trans->delayed_refs.head_refs);
 	xa_init(&cur_trans->delayed_refs.dirty_extents);
 
 	/*
Signature · 1 line
2.43.0
#21 lore raw

PATCH 18/18 btrfs: remove no longer used delayed ref head search functionality

In reply to [email protected]

From: Filipe Manana <[email protected]>

After the previous patch, which converted the rb-tree used to track delayed ref heads into an xarray, the find_ref_head() function is now used only by one caller which always passes false to the 'return_bigger' argument. So remove the 'return_bigger' logic, simplifying the function, and move all the function code to the single caller.

---
 fs/btrfs/delayed-ref.c | 34 +++++-----------------------------
 1 file changed, 5 insertions(+), 29 deletions(-)
fs/btrfs/delayed-ref.c +5 -29
index e4ca5285e614..7399be5fddaf 100644
@@ -355,34 +355,6 @@ static struct btrfs_delayed_ref_head *find_first_ref_head(
 	return xa_find(&dr->head_refs, &from, ULONG_MAX, XA_PRESENT);
 }
 
-/*
- * Find a head entry based on bytenr. This returns the delayed ref head if it
- * was able to find one, or NULL if nothing was in that spot.  If return_bigger
- * is given, the next bigger entry is returned if no exact match is found.
- */
-static struct btrfs_delayed_ref_head *find_ref_head(
-		struct btrfs_fs_info *fs_info,
-		struct btrfs_delayed_ref_root *dr, u64 bytenr,
-		bool return_bigger)
-{
-	const unsigned long target_index = (bytenr >> fs_info->sectorsize_bits);
-	unsigned long found_index = target_index;
-	struct btrfs_delayed_ref_head *entry;
-
-	lockdep_assert_held(&dr->lock);
-
-	entry = xa_find(&dr->head_refs, &found_index, ULONG_MAX, XA_PRESENT);
-	if (!entry)
-		return NULL;
-
-	ASSERT(found_index >= target_index);
-
-	if (found_index != target_index && !return_bigger)
-		return NULL;
-
-	return entry;
-}
-
 static bool btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,
 				   struct btrfs_delayed_ref_head *head)
 {
@@ -1184,7 +1156,11 @@ btrfs_find_delayed_ref_head(struct btrfs_fs_info *fs_info,
 			    struct btrfs_delayed_ref_root *delayed_refs,
 			    u64 bytenr)
 {
-	return find_ref_head(fs_info, delayed_refs, bytenr, false);
+	const unsigned long index = (bytenr >> fs_info->sectorsize_bits);
+
+	lockdep_assert_held(&delayed_refs->lock);
+
+	return xa_load(&delayed_refs->head_refs, index);
 }
 
 static int find_comp(struct btrfs_delayed_ref_node *entry, u64 root, u64 parent)
Signature · 1 line
2.43.0
#18 lore raw

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

In reply to [email protected]
Quoted 12 lines · On Thu, Oct 24, 2024 at 05:24:25PM +0100, [email protected] wrote:

From: Filipe Manana <[email protected]>

Currently we use a red black tree (rb-tree) to track the delayed ref heads (in struct btrfs_delayed_ref_root::href_root). This however is not very efficient when the number of delayed ref heads is large (and it's very common to be at least in the order of thousands) since rb-trees are binary trees. For example for 10K delayed ref heads, the tree has a depth of 13. Besides that, inserting into the tree requires navigating through it and pulling useless cache lines in the process since the red black tree nodes are embedded within the delayed ref head structure - on the other hand, by being embedded, it requires no extra memory allocations.

Quoted 12 lines

We can improve this by using an xarray instead which has a much higher branching factor than a red black tree (binary balanced tree) and is more cache friendly and behaves like a resizable array, with a much better search and insertion complexity than a red black tree. This only has one small disadvantage which is that insertion will sometimes require allocating memory for the xarray - which may fail (not that often since it uses a kmem_cache) - but on the other hand we can reduce the delayed ref head structure size by 24 bytes (from 152 down to 128 bytes) after removing the embedded red black tree node, meaning than we can now fit 32 delayed ref heads per 4K page instead of 26, and that gain compensates for the occasional memory allocations needed for the xarray nodes. We also end up using only 2 cache lines instead of 3 per delayed ref head.

The explanation makes sense to me, and I don't think the new allocation is particularly risky, since the paths calling add_delayed_ref_head are already allocating and can return ENOMEM.

With that said, just curious, have you tried hammering this under memory pressure? Have you been able to create conditions where the new allocation fails?

Quoted 443 lines

Running the following fs_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
---
 fs/btrfs/delayed-ref.c | 192 +++++++++++++++++++----------------------
 fs/btrfs/delayed-ref.h |  26 +++---
 fs/btrfs/extent-tree.c |   2 +-
 fs/btrfs/transaction.c |   5 +-
 4 files changed, 106 insertions(+), 119 deletions(-)
fs/btrfs/delayed-ref.c +88 -104
index 2b6a636ba4b5..e4ca5285e614 100644
@@ -314,39 +314,6 @@ static int comp_refs(struct btrfs_delayed_ref_node *ref1,
 	return 0;
 }
 
-/* insert a new ref to head ref rbtree */
-static struct btrfs_delayed_ref_head *htree_insert(struct rb_root_cached *root,
-						   struct rb_node *node)
-{
-	struct rb_node **p = &root->rb_root.rb_node;
-	struct rb_node *parent_node = NULL;
-	struct btrfs_delayed_ref_head *entry;
-	struct btrfs_delayed_ref_head *ins;
-	u64 bytenr;
-	bool leftmost = true;
-
-	ins = rb_entry(node, struct btrfs_delayed_ref_head, href_node);
-	bytenr = ins->bytenr;
-	while (*p) {
-		parent_node = *p;
-		entry = rb_entry(parent_node, struct btrfs_delayed_ref_head,
-				 href_node);
-
-		if (bytenr < entry->bytenr) {
-			p = &(*p)->rb_left;
-		} else if (bytenr > entry->bytenr) {
-			p = &(*p)->rb_right;
-			leftmost = false;
-		} else {
-			return entry;
-		}
-	}
-
-	rb_link_node(node, parent_node, p);
-	rb_insert_color_cached(node, root, leftmost);
-	return NULL;
-}
-
 static struct btrfs_delayed_ref_node* tree_insert(struct rb_root_cached *root,
 		struct btrfs_delayed_ref_node *ins)
 {
@@ -381,18 +348,11 @@ static struct btrfs_delayed_ref_node* tree_insert(struct rb_root_cached *root,
 static struct btrfs_delayed_ref_head *find_first_ref_head(
 		struct btrfs_delayed_ref_root *dr)
 {
-	struct rb_node *n;
-	struct btrfs_delayed_ref_head *entry;
+	unsigned long from = 0;
 
 	lockdep_assert_held(&dr->lock);
 
-	n = rb_first_cached(&dr->href_root);
-	if (!n)
-		return NULL;
-
-	entry = rb_entry(n, struct btrfs_delayed_ref_head, href_node);
-
-	return entry;
+	return xa_find(&dr->head_refs, &from, ULONG_MAX, XA_PRESENT);
 }
 
 /*
@@ -405,35 +365,22 @@ static struct btrfs_delayed_ref_head *find_ref_head(
 		struct btrfs_delayed_ref_root *dr, u64 bytenr,
 		bool return_bigger)
 {
-	struct rb_root *root = &dr->href_root.rb_root;
-	struct rb_node *n;
+	const unsigned long target_index = (bytenr >> fs_info->sectorsize_bits);
+	unsigned long found_index = target_index;
 	struct btrfs_delayed_ref_head *entry;
 
 	lockdep_assert_held(&dr->lock);
 
-	n = root->rb_node;
-	entry = NULL;
-	while (n) {
-		entry = rb_entry(n, struct btrfs_delayed_ref_head, href_node);
+	entry = xa_find(&dr->head_refs, &found_index, ULONG_MAX, XA_PRESENT);
+	if (!entry)
+		return NULL;
+
+	ASSERT(found_index >= target_index);
 
-		if (bytenr < entry->bytenr)
-			n = n->rb_left;
-		else if (bytenr > entry->bytenr)
-			n = n->rb_right;
-		else
-			return entry;
-	}
-	if (entry && return_bigger) {
-		if (bytenr > entry->bytenr) {
-			n = rb_next(&entry->href_node);
-			if (!n)
-				return NULL;
-			entry = rb_entry(n, struct btrfs_delayed_ref_head,
-					 href_node);
-		}
-		return entry;
-	}
-	return NULL;
+	if (found_index != target_index && !return_bigger)
+		return NULL;
+
+	return entry;
 }
 
 static bool btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,
@@ -448,7 +395,7 @@ static bool btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,
 
 	mutex_lock(&head->mutex);
 	spin_lock(&delayed_refs->lock);
-	if (RB_EMPTY_NODE(&head->href_node)) {
+	if (!head->tracked) {
 		mutex_unlock(&head->mutex);
 		btrfs_put_delayed_ref_head(head);
 		return false;
@@ -567,35 +514,27 @@ struct btrfs_delayed_ref_head *btrfs_select_ref_head(
 		struct btrfs_delayed_ref_root *delayed_refs)
 {
 	struct btrfs_delayed_ref_head *head;
+	unsigned long start_index;
+	unsigned long found_index;
+	bool found_head = false;
 	bool locked;
 
 	spin_lock(&delayed_refs->lock);
 again:
-	head = find_ref_head(fs_info, delayed_refs,
-			     delayed_refs->run_delayed_start, true);
-	if (!head && delayed_refs->run_delayed_start != 0) {
-		delayed_refs->run_delayed_start = 0;
-		head = find_first_ref_head(delayed_refs);
-	}
-	if (!head) {
-		spin_unlock(&delayed_refs->lock);
-		return NULL;
+	start_index = (delayed_refs->run_delayed_start >> fs_info->sectorsize_bits);
+	xa_for_each_start(&delayed_refs->head_refs, found_index, head, start_index) {
+		if (!head->processing) {
+			found_head = true;
+			break;
+		}
 	}
-
-	while (head->processing) {
-		struct rb_node *node;
-
-		node = rb_next(&head->href_node);
-		if (!node) {
-			if (delayed_refs->run_delayed_start == 0) {
-				spin_unlock(&delayed_refs->lock);
-				return NULL;
-			}
-			delayed_refs->run_delayed_start = 0;
-			goto again;
+	if (!found_head) {
+		if (delayed_refs->run_delayed_start == 0) {
+			spin_unlock(&delayed_refs->lock);
+			return NULL;
 		}
-		head = rb_entry(node, struct btrfs_delayed_ref_head,
-				href_node);
+		delayed_refs->run_delayed_start = 0;
+		goto again;
 	}
 
 	head->processing = true;
@@ -632,11 +571,13 @@ void btrfs_delete_ref_head(struct btrfs_fs_info *fs_info,
 			   struct btrfs_delayed_ref_root *delayed_refs,
 			   struct btrfs_delayed_ref_head *head)
 {
+	const unsigned long index = (head->bytenr >> fs_info->sectorsize_bits);
+
 	lockdep_assert_held(&delayed_refs->lock);
 	lockdep_assert_held(&head->lock);
 
-	rb_erase_cached(&head->href_node, &delayed_refs->href_root);
-	RB_CLEAR_NODE(&head->href_node);
+	xa_erase(&delayed_refs->head_refs, index);
+	head->tracked = false;
 	delayed_refs->num_heads--;
 	if (!head->processing)
 		delayed_refs->num_heads_ready--;
@@ -845,7 +786,7 @@ static void init_delayed_ref_head(struct btrfs_delayed_ref_head *head_ref,
 	head_ref->is_system = (generic_ref->ref_root == BTRFS_CHUNK_TREE_OBJECTID);
 	head_ref->ref_tree = RB_ROOT_CACHED;
 	INIT_LIST_HEAD(&head_ref->ref_add_list);
-	RB_CLEAR_NODE(&head_ref->href_node);
+	head_ref->tracked = false;
 	head_ref->processing = false;
 	head_ref->total_ref_mod = count_mod;
 	spin_lock_init(&head_ref->lock);
@@ -883,11 +824,24 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,
 	struct btrfs_fs_info *fs_info = trans->fs_info;
 	struct btrfs_delayed_ref_head *existing;
 	struct btrfs_delayed_ref_root *delayed_refs;
+	const unsigned long index = (head_ref->bytenr >> fs_info->sectorsize_bits);
 	bool qrecord_inserted = false;
 
 	delayed_refs = &trans->transaction->delayed_refs;
 	lockdep_assert_held(&delayed_refs->lock);
 
+#if BITS_PER_LONG == 32
+	if (head_ref->bytenr >= MAX_LFS_FILESIZE) {
+		if (qrecord)
+			xa_release(&delayed_refs->dirty_extents, index);
+		btrfs_err_rl(fs_info,
+"delayed ref head %llu is beyond 32bit page cache and xarray index limit",
+			     head_ref->bytenr);
+		btrfs_err_32bit_limit(fs_info);
+		return ERR_PTR(-EOVERFLOW);
+	}
+#endif
+
 	/* Record qgroup extent info if provided */
 	if (qrecord) {
 		int ret;
@@ -896,8 +850,7 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,
 						       head_ref->bytenr);
 		if (ret) {
 			/* Clean up if insertion fails or item exists. */
-			xa_release(&delayed_refs->dirty_extents,
-				   head_ref->bytenr >> fs_info->sectorsize_bits);
+			xa_release(&delayed_refs->dirty_extents, index);
 			/* Caller responsible for freeing qrecord on error. */
 			if (ret < 0)
 				return ERR_PTR(ret);
@@ -909,8 +862,7 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,
 
 	trace_add_delayed_ref_head(fs_info, head_ref, action);
 
-	existing = htree_insert(&delayed_refs->href_root,
-				&head_ref->href_node);
+	existing = xa_load(&delayed_refs->head_refs, index);
 	if (existing) {
 		update_existing_head_ref(trans, existing, head_ref);
 		/*
@@ -920,6 +872,19 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,
 		kmem_cache_free(btrfs_delayed_ref_head_cachep, head_ref);
 		head_ref = existing;
 	} else {
+		existing = xa_store(&delayed_refs->head_refs, index, head_ref, GFP_ATOMIC);
+		if (xa_is_err(existing)) {
+			/* Memory was preallocated by the caller. */
+			ASSERT(xa_err(existing) != -ENOMEM);
+			return ERR_CAST(existing);
+		} else if (WARN_ON(existing)) {
+			/*
+			 * Shouldn't happen we just did a lookup before under
+			 * delayed_refs->lock.
+			 */
+			return ERR_PTR(-EEXIST);
+		}
+		head_ref->tracked = true;
 		/*
 		 * We reserve the amount of bytes needed to delete csums when
 		 * adding the ref head and not when adding individual drop refs
@@ -1040,6 +1005,8 @@ static int add_delayed_ref(struct btrfs_trans_handle *trans,
 	struct btrfs_delayed_ref_head *new_head_ref;
 	struct btrfs_delayed_ref_root *delayed_refs;
 	struct btrfs_qgroup_extent_record *record = NULL;
+	const unsigned long index = (generic_ref->bytenr >> fs_info->sectorsize_bits);
+	bool qrecord_reserved = false;
 	bool qrecord_inserted;
 	int action = generic_ref->action;
 	bool merged;
@@ -1055,25 +1022,32 @@ static int add_delayed_ref(struct btrfs_trans_handle *trans,
 		goto free_node;
 	}
 
+	delayed_refs = &trans->transaction->delayed_refs;
+
 	if (btrfs_qgroup_full_accounting(fs_info) && !generic_ref->skip_qgroup) {
 		record = kzalloc(sizeof(*record), GFP_NOFS);
 		if (!record) {
 			ret = -ENOMEM;
 			goto free_head_ref;
 		}
-		if (xa_reserve(&trans->transaction->delayed_refs.dirty_extents,
-			       generic_ref->bytenr >> fs_info->sectorsize_bits,
-			       GFP_NOFS)) {
+		if (xa_reserve(&delayed_refs->dirty_extents, index, GFP_NOFS)) {
 			ret = -ENOMEM;
 			goto free_record;
 		}
+		qrecord_reserved = true;
+	}
+
+	ret = xa_reserve(&delayed_refs->head_refs, index, GFP_NOFS);
+	if (ret) {
+		if (qrecord_reserved)
+			xa_release(&delayed_refs->dirty_extents, index);
+		goto free_record;
 	}
 
 	init_delayed_ref_common(fs_info, node, generic_ref);
 	init_delayed_ref_head(head_ref, generic_ref, record, reserved);
 	head_ref->extent_op = extent_op;
 
-	delayed_refs = &trans->transaction->delayed_refs;
 	spin_lock(&delayed_refs->lock);
 
 	/*
@@ -1083,6 +1057,7 @@ static int add_delayed_ref(struct btrfs_trans_handle *trans,
 	new_head_ref = add_delayed_ref_head(trans, head_ref, record,
 					    action, &qrecord_inserted);
 	if (IS_ERR(new_head_ref)) {
+		xa_release(&delayed_refs->head_refs, index);
 		spin_unlock(&delayed_refs->lock);
 		ret = PTR_ERR(new_head_ref);
 		goto free_record;
@@ -1145,6 +1120,7 @@ int btrfs_add_delayed_extent_op(struct btrfs_trans_handle *trans,
 				u64 bytenr, u64 num_bytes, u8 level,
 				struct btrfs_delayed_extent_op *extent_op)
 {
+	const unsigned long index = (bytenr >> trans->fs_info->sectorsize_bits);
 	struct btrfs_delayed_ref_head *head_ref;
 	struct btrfs_delayed_ref_head *head_ref_ret;
 	struct btrfs_delayed_ref_root *delayed_refs;
@@ -1155,6 +1131,7 @@ int btrfs_add_delayed_extent_op(struct btrfs_trans_handle *trans,
 		.num_bytes = num_bytes,
 		.tree_ref.level = level,
 	};
+	int ret;
 
 	head_ref = kmem_cache_alloc(btrfs_delayed_ref_head_cachep, GFP_NOFS);
 	if (!head_ref)
@@ -1164,16 +1141,23 @@ int btrfs_add_delayed_extent_op(struct btrfs_trans_handle *trans,
 	head_ref->extent_op = extent_op;
 
 	delayed_refs = &trans->transaction->delayed_refs;
-	spin_lock(&delayed_refs->lock);
 
+	ret = xa_reserve(&delayed_refs->head_refs, index, GFP_NOFS);
+	if (ret) {
+		kmem_cache_free(btrfs_delayed_ref_head_cachep, head_ref);
+		return ret;
+	}
+
+	spin_lock(&delayed_refs->lock);
 	head_ref_ret = add_delayed_ref_head(trans, head_ref, NULL,
 					    BTRFS_UPDATE_DELAYED_HEAD, NULL);
-	spin_unlock(&delayed_refs->lock);
-
 	if (IS_ERR(head_ref_ret)) {
+		xa_release(&delayed_refs->head_refs, index);
+		spin_unlock(&delayed_refs->lock);
 		kmem_cache_free(btrfs_delayed_ref_head_cachep, head_ref);
 		return PTR_ERR(head_ref_ret);
 	}
+	spin_unlock(&delayed_refs->lock);
 
 	/*
 	 * Need to update the delayed_refs_rsv with any changes we may have
fs/btrfs/delayed-ref.h +5 -6
index 0a9f4d7dd87b..c7c4d62744b4 100644
@@ -122,12 +122,6 @@ struct btrfs_delayed_extent_op {
 struct btrfs_delayed_ref_head {
 	u64 bytenr;
 	u64 num_bytes;
-	/*
-	 * For insertion into struct btrfs_delayed_ref_root::href_root.
-	 * Keep it in the same cache line as 'bytenr' for more efficient
-	 * searches in the rbtree.
-	 */
-	struct rb_node href_node;
 	/*
 	 * the mutex is held while running the refs, and it is also
 	 * held when checking the sum of reference modifications.
@@ -191,6 +185,11 @@ struct btrfs_delayed_ref_head {
 	bool is_data;
 	bool is_system;
 	bool processing;
+	/*
+	 * Indicate if it's currently in the data structure that tracks head
+	 * refs (struct btrfs_delayed_ref_root::head_refs).
+	 */
+	bool tracked;
 };
 
 enum btrfs_delayed_ref_flags {
@@ -199,22 +198,27 @@ enum btrfs_delayed_ref_flags {
 };

fs/btrfs/delayed-ref.h enum btrfs_delayed_ref_flags { · line 204

Quoted 10 lines
fs/btrfs/delayed-ref.h +1 -4
 
 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.

Quoted 60 lines
fs/btrfs/delayed-ref.h +9 -1
 	 * dense index space (optimizes xarray structure) and because indexes in
 	 * xarrays are of "unsigned long" type, meaning they are 32 bits wide on
 	 * 32 bits platforms, limiting the extent range to 4G which is too low
 	 * and makes it unusable (truncated index values) on 32 bits platforms.
+	 * Protected by the spinlock 'lock' defined below.
+	 */
+	struct xarray head_refs;
+
+	/*
+	 * Track dirty extent records.
+	 * The keys correspond to the logical address of the extent ("bytenr")
+	 * right shifted by fs_info->sectorsize_bits, for same reasons as above.
 	 */
 	struct xarray dirty_extents;
 
 	/*
-	 * Protects the rbtree href_root, its entries and the following fields:
+	 * Protects the xarray head_refs, its entries and the following fields:
 	 * num_heads, num_heads_ready, pending_csums and run_delayed_start.
 	 */
 	spinlock_t lock;
fs/btrfs/extent-tree.c +1 -1
index 33f911476a4d..1571b5a1d905 100644
@@ -2176,7 +2176,7 @@ int btrfs_run_delayed_refs(struct btrfs_trans_handle *trans, u64 min_bytes)
 		btrfs_create_pending_block_groups(trans);
 
 		spin_lock(&delayed_refs->lock);
-		if (RB_EMPTY_ROOT(&delayed_refs->href_root.rb_root)) {
+		if (xa_empty(&delayed_refs->head_refs)) {
 			spin_unlock(&delayed_refs->lock);
 			return 0;
 		}
fs/btrfs/transaction.c +2 -3
index 9ccf68ab53f9..dc0b837efd5d 100644
@@ -141,8 +141,7 @@ void btrfs_put_transaction(struct btrfs_transaction *transaction)
 	WARN_ON(refcount_read(&transaction->use_count) == 0);
 	if (refcount_dec_and_test(&transaction->use_count)) {
 		BUG_ON(!list_empty(&transaction->list));
-		WARN_ON(!RB_EMPTY_ROOT(
-				&transaction->delayed_refs.href_root.rb_root));
+		WARN_ON(!xa_empty(&transaction->delayed_refs.head_refs));
 		WARN_ON(!xa_empty(&transaction->delayed_refs.dirty_extents));
 		if (transaction->delayed_refs.pending_csums)
 			btrfs_err(transaction->fs_info,
@@ -349,7 +348,7 @@ static noinline int join_transaction(struct btrfs_fs_info *fs_info,
 
 	memset(&cur_trans->delayed_refs, 0, sizeof(cur_trans->delayed_refs));
 
-	cur_trans->delayed_refs.href_root = RB_ROOT_CACHED;
+	xa_init(&cur_trans->delayed_refs.head_refs);
 	xa_init(&cur_trans->delayed_refs.dirty_extents);
 
 	/*
Signature · 1 line
2.43.0
Reviewed-by on the v1 series
#22 lore raw
In reply to [email protected]
Quoted 7 lines · On Thu, Oct 24, 2024 at 05:24:08PM +0100, [email protected] wrote:

From: Filipe Manana <[email protected]>

This converts the rb-tree that tracks delayed ref heads into an xarray, reducing memory used by delayed ref heads and making it more efficient to add/remove/find delayed ref heads. The rest are mostly cleanups and refactorings, removing some dead code, deduplicating code, move code around, etc. More details in the changelogs.

The cleanup patches all look perfectly reasonable to me, and the risks (new tracked variable, new allocation) with the xarray patches seem well considered.

Thanks for making this improvement, I think xarray is a good fit for delayed refs.

Quoted 33 lines

Filipe Manana (18):
btrfs: remove BUG_ON() at btrfs_destroy_delayed_refs()
btrfs: move btrfs_destroy_delayed_refs() to delayed-ref.c
btrfs: remove fs_info parameter from btrfs_destroy_delayed_refs()
btrfs: remove fs_info parameter from btrfs_cleanup_one_transaction()
btrfs: remove duplicated code to drop delayed ref during transaction abort
btrfs: use helper to find first ref head at btrfs_destroy_delayed_refs()
btrfs: remove num_entries atomic counter from delayed ref root
btrfs: change return type of btrfs_delayed_ref_lock() to boolean
btrfs: simplify obtaining a delayed ref head
btrfs: move delayed ref head unselection to delayed-ref.c
btrfs: pass fs_info to functions that search for delayed ref heads
btrfs: pass fs_info to btrfs_cleanup_ref_head_accounting
btrfs: assert delayed refs lock is held at find_ref_head()
btrfs: assert delayed refs lock is held at find_first_ref_head()
btrfs: assert delayed refs lock is held at add_delayed_ref_head()
btrfs: add comments regarding locking to struct btrfs_delayed_ref_root
btrfs: track delayed ref heads in an xarray
btrfs: remove no longer used delayed ref head search functionality

 fs/btrfs/backref.c     |   3 +-
 fs/btrfs/delayed-ref.c | 319 +++++++++++++++++++++++++----------------
 fs/btrfs/delayed-ref.h |  61 +++++---
 fs/btrfs/disk-io.c     |  79 +---------
 fs/btrfs/disk-io.h     |   3 +-
 fs/btrfs/extent-tree.c |  69 ++-------
 fs/btrfs/transaction.c |   8 +-
 7 files changed, 256 insertions(+), 286 deletions(-)
Signature · 1 line
2.43.0
#19 lore raw

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

In reply to Boris Burkov
Quoted 27 lines · Boris Burkov
Quoted 12 lines · On Thu, Oct 24, 2024 at 05:24:25PM +0100, [email protected] wrote:

From: Filipe Manana <[email protected]>

Currently we use a red black tree (rb-tree) to track the delayed ref heads (in struct btrfs_delayed_ref_root::href_root). This however is not very efficient when the number of delayed ref heads is large (and it's very common to be at least in the order of thousands) since rb-trees are binary trees. For example for 10K delayed ref heads, the tree has a depth of 13. Besides that, inserting into the tree requires navigating through it and pulling useless cache lines in the process since the red black tree nodes are embedded within the delayed ref head structure - on the other hand, by being embedded, it requires no extra memory allocations.

Quoted 12 lines

We can improve this by using an xarray instead which has a much higher branching factor than a red black tree (binary balanced tree) and is more cache friendly and behaves like a resizable array, with a much better search and insertion complexity than a red black tree. This only has one small disadvantage which is that insertion will sometimes require allocating memory for the xarray - which may fail (not that often since it uses a kmem_cache) - but on the other hand we can reduce the delayed ref head structure size by 24 bytes (from 152 down to 128 bytes) after removing the embedded red black tree node, meaning than we can now fit 32 delayed ref heads per 4K page instead of 26, and that gain compensates for the occasional memory allocations needed for the xarray nodes. We also end up using only 2 cache lines instead of 3 per delayed ref head.

Quoted 7 lines

The explanation makes sense to me, and I don't think the new allocation is particularly risky, since the paths calling add_delayed_ref_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.

Quoted 520 lines
Quoted 444 lines

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
---
 fs/btrfs/delayed-ref.c | 192 +++++++++++++++++++----------------------
 fs/btrfs/delayed-ref.h |  26 +++---
 fs/btrfs/extent-tree.c |   2 +-
 fs/btrfs/transaction.c |   5 +-
 4 files changed, 106 insertions(+), 119 deletions(-)
fs/btrfs/delayed-ref.c +88 -104
index 2b6a636ba4b5..e4ca5285e614 100644
@@ -314,39 +314,6 @@ static int comp_refs(struct btrfs_delayed_ref_node *ref1,
      return 0;
 }
 
-/* insert a new ref to head ref rbtree */
-static struct btrfs_delayed_ref_head *htree_insert(struct rb_root_cached *root,
-                                                struct rb_node *node)
-{
-     struct rb_node **p = &root->rb_root.rb_node;
-     struct rb_node *parent_node = NULL;
-     struct btrfs_delayed_ref_head *entry;
-     struct btrfs_delayed_ref_head *ins;
-     u64 bytenr;
-     bool leftmost = true;
-
-     ins = rb_entry(node, struct btrfs_delayed_ref_head, href_node);
-     bytenr = ins->bytenr;
-     while (*p) {
-             parent_node = *p;
-             entry = rb_entry(parent_node, struct btrfs_delayed_ref_head,
-                              href_node);
-
-             if (bytenr < entry->bytenr) {
-                     p = &(*p)->rb_left;
-             } else if (bytenr > entry->bytenr) {
-                     p = &(*p)->rb_right;
-                     leftmost = false;
-             } else {
-                     return entry;
-             }
-     }
-
-     rb_link_node(node, parent_node, p);
-     rb_insert_color_cached(node, root, leftmost);
-     return NULL;
-}
-
 static struct btrfs_delayed_ref_node* tree_insert(struct rb_root_cached *root,
              struct btrfs_delayed_ref_node *ins)
 {
@@ -381,18 +348,11 @@ static struct btrfs_delayed_ref_node* tree_insert(struct rb_root_cached *root,
 static struct btrfs_delayed_ref_head *find_first_ref_head(
              struct btrfs_delayed_ref_root *dr)
 {
-     struct rb_node *n;
-     struct btrfs_delayed_ref_head *entry;
+     unsigned long from = 0;
 
      lockdep_assert_held(&dr->lock);
 
-     n = rb_first_cached(&dr->href_root);
-     if (!n)
-             return NULL;
-
-     entry = rb_entry(n, struct btrfs_delayed_ref_head, href_node);
-
-     return entry;
+     return xa_find(&dr->head_refs, &from, ULONG_MAX, XA_PRESENT);
 }
 
 /*
@@ -405,35 +365,22 @@ static struct btrfs_delayed_ref_head *find_ref_head(
              struct btrfs_delayed_ref_root *dr, u64 bytenr,
              bool return_bigger)
 {
-     struct rb_root *root = &dr->href_root.rb_root;
-     struct rb_node *n;
+     const unsigned long target_index = (bytenr >> fs_info->sectorsize_bits);
+     unsigned long found_index = target_index;
      struct btrfs_delayed_ref_head *entry;
 
      lockdep_assert_held(&dr->lock);
 
-     n = root->rb_node;
-     entry = NULL;
-     while (n) {
-             entry = rb_entry(n, struct btrfs_delayed_ref_head, href_node);
+     entry = xa_find(&dr->head_refs, &found_index, ULONG_MAX, XA_PRESENT);
+     if (!entry)
+             return NULL;
+
+     ASSERT(found_index >= target_index);
 
-             if (bytenr < entry->bytenr)
-                     n = n->rb_left;
-             else if (bytenr > entry->bytenr)
-                     n = n->rb_right;
-             else
-                     return entry;
-     }
-     if (entry && return_bigger) {
-             if (bytenr > entry->bytenr) {
-                     n = rb_next(&entry->href_node);
-                     if (!n)
-                             return NULL;
-                     entry = rb_entry(n, struct btrfs_delayed_ref_head,
-                                      href_node);
-             }
-             return entry;
-     }
-     return NULL;
+     if (found_index != target_index && !return_bigger)
+             return NULL;
+
+     return entry;
 }
 
 static bool btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,
@@ -448,7 +395,7 @@ static bool btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,
 
      mutex_lock(&head->mutex);
      spin_lock(&delayed_refs->lock);
-     if (RB_EMPTY_NODE(&head->href_node)) {
+     if (!head->tracked) {
              mutex_unlock(&head->mutex);
              btrfs_put_delayed_ref_head(head);
              return false;
@@ -567,35 +514,27 @@ struct btrfs_delayed_ref_head *btrfs_select_ref_head(
              struct btrfs_delayed_ref_root *delayed_refs)
 {
      struct btrfs_delayed_ref_head *head;
+     unsigned long start_index;
+     unsigned long found_index;
+     bool found_head = false;
      bool locked;
 
      spin_lock(&delayed_refs->lock);
 again:
-     head = find_ref_head(fs_info, delayed_refs,
-                          delayed_refs->run_delayed_start, true);
-     if (!head && delayed_refs->run_delayed_start != 0) {
-             delayed_refs->run_delayed_start = 0;
-             head = find_first_ref_head(delayed_refs);
-     }
-     if (!head) {
-             spin_unlock(&delayed_refs->lock);
-             return NULL;
+     start_index = (delayed_refs->run_delayed_start >> fs_info->sectorsize_bits);
+     xa_for_each_start(&delayed_refs->head_refs, found_index, head, start_index) {
+             if (!head->processing) {
+                     found_head = true;
+                     break;
+             }
      }
-
-     while (head->processing) {
-             struct rb_node *node;
-
-             node = rb_next(&head->href_node);
-             if (!node) {
-                     if (delayed_refs->run_delayed_start == 0) {
-                             spin_unlock(&delayed_refs->lock);
-                             return NULL;
-                     }
-                     delayed_refs->run_delayed_start = 0;
-                     goto again;
+     if (!found_head) {
+             if (delayed_refs->run_delayed_start == 0) {
+                     spin_unlock(&delayed_refs->lock);
+                     return NULL;
              }
-             head = rb_entry(node, struct btrfs_delayed_ref_head,
-                             href_node);
+             delayed_refs->run_delayed_start = 0;
+             goto again;
      }
 
      head->processing = true;
@@ -632,11 +571,13 @@ void btrfs_delete_ref_head(struct btrfs_fs_info *fs_info,
                         struct btrfs_delayed_ref_root *delayed_refs,
                         struct btrfs_delayed_ref_head *head)
 {
+     const unsigned long index = (head->bytenr >> fs_info->sectorsize_bits);
+
      lockdep_assert_held(&delayed_refs->lock);
      lockdep_assert_held(&head->lock);
 
-     rb_erase_cached(&head->href_node, &delayed_refs->href_root);
-     RB_CLEAR_NODE(&head->href_node);
+     xa_erase(&delayed_refs->head_refs, index);
+     head->tracked = false;
      delayed_refs->num_heads--;
      if (!head->processing)
              delayed_refs->num_heads_ready--;
@@ -845,7 +786,7 @@ static void init_delayed_ref_head(struct btrfs_delayed_ref_head *head_ref,
      head_ref->is_system = (generic_ref->ref_root == BTRFS_CHUNK_TREE_OBJECTID);
      head_ref->ref_tree = RB_ROOT_CACHED;
      INIT_LIST_HEAD(&head_ref->ref_add_list);
-     RB_CLEAR_NODE(&head_ref->href_node);
+     head_ref->tracked = false;
      head_ref->processing = false;
      head_ref->total_ref_mod = count_mod;
      spin_lock_init(&head_ref->lock);
@@ -883,11 +824,24 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,
      struct btrfs_fs_info *fs_info = trans->fs_info;
      struct btrfs_delayed_ref_head *existing;
      struct btrfs_delayed_ref_root *delayed_refs;
+     const unsigned long index = (head_ref->bytenr >> fs_info->sectorsize_bits);
      bool qrecord_inserted = false;
 
      delayed_refs = &trans->transaction->delayed_refs;
      lockdep_assert_held(&delayed_refs->lock);
 
+#if BITS_PER_LONG == 32
+     if (head_ref->bytenr >= MAX_LFS_FILESIZE) {
+             if (qrecord)
+                     xa_release(&delayed_refs->dirty_extents, index);
+             btrfs_err_rl(fs_info,
+"delayed ref head %llu is beyond 32bit page cache and xarray index limit",
+                          head_ref->bytenr);
+             btrfs_err_32bit_limit(fs_info);
+             return ERR_PTR(-EOVERFLOW);
+     }
+#endif
+
      /* Record qgroup extent info if provided */
      if (qrecord) {
              int ret;
@@ -896,8 +850,7 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,
                                                     head_ref->bytenr);
              if (ret) {
                      /* Clean up if insertion fails or item exists. */
-                     xa_release(&delayed_refs->dirty_extents,
-                                head_ref->bytenr >> fs_info->sectorsize_bits);
+                     xa_release(&delayed_refs->dirty_extents, index);
                      /* Caller responsible for freeing qrecord on error. */
                      if (ret < 0)
                              return ERR_PTR(ret);
@@ -909,8 +862,7 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,
 
      trace_add_delayed_ref_head(fs_info, head_ref, action);
 
-     existing = htree_insert(&delayed_refs->href_root,
-                             &head_ref->href_node);
+     existing = xa_load(&delayed_refs->head_refs, index);
      if (existing) {
              update_existing_head_ref(trans, existing, head_ref);
              /*
@@ -920,6 +872,19 @@ add_delayed_ref_head(struct btrfs_trans_handle *trans,
              kmem_cache_free(btrfs_delayed_ref_head_cachep, head_ref);
              head_ref = existing;
      } else {
+             existing = xa_store(&delayed_refs->head_refs, index, head_ref, GFP_ATOMIC);
+             if (xa_is_err(existing)) {
+                     /* Memory was preallocated by the caller. */
+                     ASSERT(xa_err(existing) != -ENOMEM);
+                     return ERR_CAST(existing);
+             } else if (WARN_ON(existing)) {
+                     /*
+                      * Shouldn't happen we just did a lookup before under
+                      * delayed_refs->lock.
+                      */
+                     return ERR_PTR(-EEXIST);
+             }
+             head_ref->tracked = true;
              /*
               * We reserve the amount of bytes needed to delete csums when
               * adding the ref head and not when adding individual drop refs
@@ -1040,6 +1005,8 @@ static int add_delayed_ref(struct btrfs_trans_handle *trans,
      struct btrfs_delayed_ref_head *new_head_ref;
      struct btrfs_delayed_ref_root *delayed_refs;
      struct btrfs_qgroup_extent_record *record = NULL;
+     const unsigned long index = (generic_ref->bytenr >> fs_info->sectorsize_bits);
+     bool qrecord_reserved = false;
      bool qrecord_inserted;
      int action = generic_ref->action;
      bool merged;
@@ -1055,25 +1022,32 @@ static int add_delayed_ref(struct btrfs_trans_handle *trans,
              goto free_node;
      }
 
+     delayed_refs = &trans->transaction->delayed_refs;
+
      if (btrfs_qgroup_full_accounting(fs_info) && !generic_ref->skip_qgroup) {
              record = kzalloc(sizeof(*record), GFP_NOFS);
              if (!record) {
                      ret = -ENOMEM;
                      goto free_head_ref;
              }
-             if (xa_reserve(&trans->transaction->delayed_refs.dirty_extents,
-                            generic_ref->bytenr >> fs_info->sectorsize_bits,
-                            GFP_NOFS)) {
+             if (xa_reserve(&delayed_refs->dirty_extents, index, GFP_NOFS)) {
                      ret = -ENOMEM;
                      goto free_record;
              }
+             qrecord_reserved = true;
+     }
+
+     ret = xa_reserve(&delayed_refs->head_refs, index, GFP_NOFS);
+     if (ret) {
+             if (qrecord_reserved)
+                     xa_release(&delayed_refs->dirty_extents, index);
+             goto free_record;
      }
 
      init_delayed_ref_common(fs_info, node, generic_ref);
      init_delayed_ref_head(head_ref, generic_ref, record, reserved);
      head_ref->extent_op = extent_op;
 
-     delayed_refs = &trans->transaction->delayed_refs;
      spin_lock(&delayed_refs->lock);
 
      /*
@@ -1083,6 +1057,7 @@ static int add_delayed_ref(struct btrfs_trans_handle *trans,
      new_head_ref = add_delayed_ref_head(trans, head_ref, record,
                                          action, &qrecord_inserted);
      if (IS_ERR(new_head_ref)) {
+             xa_release(&delayed_refs->head_refs, index);
              spin_unlock(&delayed_refs->lock);
              ret = PTR_ERR(new_head_ref);
              goto free_record;
@@ -1145,6 +1120,7 @@ int btrfs_add_delayed_extent_op(struct btrfs_trans_handle *trans,
                              u64 bytenr, u64 num_bytes, u8 level,
                              struct btrfs_delayed_extent_op *extent_op)
 {
+     const unsigned long index = (bytenr >> trans->fs_info->sectorsize_bits);
      struct btrfs_delayed_ref_head *head_ref;
      struct btrfs_delayed_ref_head *head_ref_ret;
      struct btrfs_delayed_ref_root *delayed_refs;
@@ -1155,6 +1131,7 @@ int btrfs_add_delayed_extent_op(struct btrfs_trans_handle *trans,
              .num_bytes = num_bytes,
              .tree_ref.level = level,
      };
+     int ret;
 
      head_ref = kmem_cache_alloc(btrfs_delayed_ref_head_cachep, GFP_NOFS);
      if (!head_ref)
@@ -1164,16 +1141,23 @@ int btrfs_add_delayed_extent_op(struct btrfs_trans_handle *trans,
      head_ref->extent_op = extent_op;
 
      delayed_refs = &trans->transaction->delayed_refs;
-     spin_lock(&delayed_refs->lock);
 
+     ret = xa_reserve(&delayed_refs->head_refs, index, GFP_NOFS);
+     if (ret) {
+             kmem_cache_free(btrfs_delayed_ref_head_cachep, head_ref);
+             return ret;
+     }
+
+     spin_lock(&delayed_refs->lock);
      head_ref_ret = add_delayed_ref_head(trans, head_ref, NULL,
                                          BTRFS_UPDATE_DELAYED_HEAD, NULL);
-     spin_unlock(&delayed_refs->lock);
-
      if (IS_ERR(head_ref_ret)) {
+             xa_release(&delayed_refs->head_refs, index);
+             spin_unlock(&delayed_refs->lock);
              kmem_cache_free(btrfs_delayed_ref_head_cachep, head_ref);
              return PTR_ERR(head_ref_ret);
      }
+     spin_unlock(&delayed_refs->lock);
 
      /*
       * Need to update the delayed_refs_rsv with any changes we may have
fs/btrfs/delayed-ref.h +5 -6
index 0a9f4d7dd87b..c7c4d62744b4 100644
@@ -122,12 +122,6 @@ struct btrfs_delayed_extent_op {
 struct btrfs_delayed_ref_head {
      u64 bytenr;
      u64 num_bytes;
-     /*
-      * For insertion into struct btrfs_delayed_ref_root::href_root.
-      * Keep it in the same cache line as 'bytenr' for more efficient
-      * searches in the rbtree.
-      */
-     struct rb_node href_node;
      /*
       * the mutex is held while running the refs, and it is also
       * held when checking the sum of reference modifications.
@@ -191,6 +185,11 @@ struct btrfs_delayed_ref_head {
      bool is_data;
      bool is_system;
      bool processing;
+     /*
+      * Indicate if it's currently in the data structure that tracks head
+      * refs (struct btrfs_delayed_ref_root::head_refs).
+      */
+     bool tracked;
 };
 
 enum btrfs_delayed_ref_flags {
@@ -199,22 +198,27 @@ enum btrfs_delayed_ref_flags {
 };

fs/btrfs/delayed-ref.h enum btrfs_delayed_ref_flags { · line 204

Quoted 10 lines
fs/btrfs/delayed-ref.h +1 -4
 
 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.

Quoted 60 lines
fs/btrfs/delayed-ref.h +9 -1
       * dense index space (optimizes xarray structure) and because indexes in
       * xarrays are of "unsigned long" type, meaning they are 32 bits wide on
       * 32 bits platforms, limiting the extent range to 4G which is too low
       * and makes it unusable (truncated index values) on 32 bits platforms.
+      * Protected by the spinlock 'lock' defined below.
+      */
+     struct xarray head_refs;
+
+     /*
+      * Track dirty extent records.
+      * The keys correspond to the logical address of the extent ("bytenr")
+      * right shifted by fs_info->sectorsize_bits, for same reasons as above.
       */
      struct xarray dirty_extents;
 
      /*
-      * Protects the rbtree href_root, its entries and the following fields:
+      * Protects the xarray head_refs, its entries and the following fields:
       * num_heads, num_heads_ready, pending_csums and run_delayed_start.
       */
      spinlock_t lock;
fs/btrfs/extent-tree.c +1 -1
index 33f911476a4d..1571b5a1d905 100644
@@ -2176,7 +2176,7 @@ int btrfs_run_delayed_refs(struct btrfs_trans_handle *trans, u64 min_bytes)
              btrfs_create_pending_block_groups(trans);
 
              spin_lock(&delayed_refs->lock);
-             if (RB_EMPTY_ROOT(&delayed_refs->href_root.rb_root)) {
+             if (xa_empty(&delayed_refs->head_refs)) {
                      spin_unlock(&delayed_refs->lock);
                      return 0;
              }
fs/btrfs/transaction.c +2 -4
index 9ccf68ab53f9..dc0b837efd5d 100644
@@ -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

#23 lore raw
In reply to [email protected]
Quoted 7 lines · On 24.10.24 18:24, [email protected] wrote:

From: Filipe Manana <[email protected]>

This converts the rb-tree that tracks delayed ref heads into an xarray, reducing memory used by delayed ref heads and making it more efficient to add/remove/find delayed ref heads. The rest are mostly cleanups and refactorings, removing some dead code, deduplicating code, move code around, etc. More details in the changelogs.

Stupid question (and by that I literally mean, it's a stupid question, I have no idea): looking at other places where we're heavily relying on rb-trees is ordered-extents. Would it make sense to move them over to xarrays as well?

#24 lore raw
Quoted 10 lines · Johannes Thumshirn
Quoted 7 lines · On 24.10.24 18:24, [email protected] wrote:

From: Filipe Manana <[email protected]>

This converts the rb-tree that tracks delayed ref heads into an xarray, reducing memory used by delayed ref heads and making it more efficient to add/remove/find delayed ref heads. The rest are mostly cleanups and refactorings, removing some dead code, deduplicating code, move code around, etc. More details in the changelogs.

Quoted 4 lines

Stupid question (and by that I literally mean, it's a stupid question, I have no idea): looking at other places where we're heavily relying on rb-trees is ordered-extents. Would it make sense to move them over to xarrays as well?

For ordered extents I wouldn't consider it, because I don't think it's common to have thousands of them per inode.
Same for delayed refs inside a delayed ref head for example. For delayed ref heads, for every cow operation we get one to delete the old extent and another one for the new extent, so these can easily be thousands even for small filesystems with moderate and even low workloads.

It may still be worth just to reduce structure sizes and memory usage, though it would have to be analyzed on a case by case basis.

#25 lore raw
Quoted 25 lines · Filipe Manana
Quoted 10 lines · Johannes Thumshirn
Quoted 7 lines · On 24.10.24 18:24, [email protected] wrote:

From: Filipe Manana <[email protected]>

This converts the rb-tree that tracks delayed ref heads into an xarray, reducing memory used by delayed ref heads and making it more efficient to add/remove/find delayed ref heads. The rest are mostly cleanups and refactorings, removing some dead code, deduplicating code, move code around, etc. More details in the changelogs.

Quoted 4 lines

Stupid question (and by that I literally mean, it's a stupid question, I have no idea): looking at other places where we're heavily relying on rb-trees is ordered-extents. Would it make sense to move them over to xarrays as well?

For ordered extents I wouldn't consider it, because I don't think it's common to have thousands of them per inode.
Same for delayed refs inside a delayed ref head for example. For delayed ref heads, for every cow operation we get one to delete the old extent and another one for the new extent, so these can easily be thousands even for small filesystems with moderate and even low workloads.

Quoted 3 lines

It may still be worth just to reduce structure sizes and memory usage, though it would have to be analyzed on a case by case basis.

Thanks for the info :)

Reviewed-by on the v1 series
#28 lore raw
In reply to [email protected]
Quoted 19 lines · On Thu, Oct 24, 2024 at 05:24:08PM +0100, [email protected] wrote:

From: Filipe Manana <[email protected]>

This converts the rb-tree that tracks delayed ref heads into an xarray, reducing memory used by delayed ref heads and making it more efficient to add/remove/find delayed ref heads. The rest are mostly cleanups and refactorings, removing some dead code, deduplicating code, move code around, etc. More details in the changelogs.

Filipe Manana (18):
btrfs: 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

Quoted 8 lines

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

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

#20 lore raw

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

In reply to Boris Burkov
Quoted 26 lines · Boris Burkov
Quoted 12 lines · On Thu, Oct 24, 2024 at 05:24:25PM +0100, [email protected] wrote:

From: Filipe Manana <[email protected]>

Currently we use a red black tree (rb-tree) to track the delayed ref heads (in struct btrfs_delayed_ref_root::href_root). This however is not very efficient when the number of delayed ref heads is large (and it's very common to be at least in the order of thousands) since rb-trees are binary trees. For example for 10K delayed ref heads, the tree has a depth of 13. Besides that, inserting into the tree requires navigating through it and pulling useless cache lines in the process since the red black tree nodes are embedded within the delayed ref head structure - on the other hand, by being embedded, it requires no extra memory allocations.

Quoted 12 lines

We can improve this by using an xarray instead which has a much higher branching factor than a red black tree (binary balanced tree) and is more cache friendly and behaves like a resizable array, with a much better search and insertion complexity than a red black tree. This only has one small disadvantage which is that insertion will sometimes require allocating memory for the xarray - which may fail (not that often since it uses a kmem_cache) - but on the other hand we can reduce the delayed ref head structure size by 24 bytes (from 152 down to 128 bytes) after removing the embedded red black tree node, meaning than we can now fit 32 delayed ref heads per 4K page instead of 26, and that gain compensates for the occasional memory allocations needed for the xarray nodes. We also end up using only 2 cache lines instead of 3 per delayed ref head.

Quoted 7 lines

The explanation makes sense to me, and I don't think the new allocation is particularly risky, since the paths calling add_delayed_ref_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.

#26 lore raw
In reply to Filipe Manana
Quoted 25 lines · Filipe Manana
Quoted 10 lines · Johannes Thumshirn
Quoted 7 lines · On 24.10.24 18:24, [email protected] wrote:

From: Filipe Manana <[email protected]>

This converts the rb-tree that tracks delayed ref heads into an xarray, reducing memory used by delayed ref heads and making it more efficient to add/remove/find delayed ref heads. The rest are mostly cleanups and refactorings, removing some dead code, deduplicating code, move code around, etc. More details in the changelogs.

Quoted 4 lines

Stupid question (and by that I literally mean, it's a stupid question, I have no idea): looking at other places where we're heavily relying on rb-trees is ordered-extents. Would it make sense to move them over to xarrays as well?

For ordered extents I wouldn't consider it, because I don't think it's common to have thousands of them per inode.
Same for delayed refs inside a delayed ref head for example. For delayed ref heads, for every cow operation we get one to delete the old extent and another one for the new extent, so these can easily be thousands even for small filesystems with moderate and even low workloads.

Quoted 3 lines

It may still be worth just to reduce structure sizes and memory usage, though it would have to be analyzed on a case by case basis.

Another question related to this is, if we switch ordered extent or extent map to XArray, how do we find such structure that covers a bytenr?

For delayed ref and extent buffer (which uses radix tree) we are working with the exact bytenr, but for OE/EM we do a lot of search using a bytenr.

Or do I miss some XArray feature that can do that?

Thanks,
Qu

#27 lore raw
Quoted 29 lines · Qu Wenruo
Quoted 25 lines · Filipe Manana
Quoted 10 lines · Johannes Thumshirn
Quoted 7 lines · On 24.10.24 18:24, [email protected] wrote:

From: Filipe Manana <[email protected]>

This converts the rb-tree that tracks delayed ref heads into an xarray, reducing memory used by delayed ref heads and making it more efficient to add/remove/find delayed ref heads. The rest are mostly cleanups and refactorings, removing some dead code, deduplicating code, move code around, etc. More details in the changelogs.

Quoted 4 lines

Stupid question (and by that I literally mean, it's a stupid question, I have no idea): looking at other places where we're heavily relying on rb-trees is ordered-extents. Would it make sense to move them over to xarrays as well?

For ordered extents I wouldn't consider it, because I don't think it's common to have thousands of them per inode.
Same for delayed refs inside a delayed ref head for example. For delayed ref heads, for every cow operation we get one to delete the old extent and another one for the new extent, so these can easily be thousands even for small filesystems with moderate and even low workloads.

Quoted 6 lines
Quoted 3 lines

It may still be worth just to reduce structure sizes and memory usage, though it would have to be analyzed on a case by case basis.

Another question related to this is, if we switch ordered extent or extent map to XArray, how do we find such structure that covers a bytenr?

You don't, not without doing something like xa_for_each() and iterate the xarray until either:

1) we find a matching entry (within the ragne of an element in the xarray);
2) we find the first entry that starts beyond the offset/range we are looking for and stop, meaning there's no entry covering the range we want;
3) we reach the end of the array.

The rbtree based search is more practical for that.

Quoted 5 lines

For delayed ref and extent buffer (which uses radix tree) we are working with the exact bytenr, but for OE/EM we do a lot of search using a bytenr.

Or do I miss some XArray feature that can do that?

There isn't any. There are ranges for xarray but they basically mean having a range of indexes point to the same value, which doesn't help in these cases.

For extent maps and states for example, beside the range search, there's also the detail of merging adjacent entries, which is not doable in a practical and efficient way with xarrays, especially to find the previous entry.

Quoted 3 lines

Thanks,
Qu

Reviewed-by on the v1 series
#29 lore raw
In reply to [email protected]
Quoted 7 lines · 在 2024/10/25 02:54, [email protected] 写道:

From: Filipe Manana <[email protected]>

This converts the rb-tree that tracks delayed ref heads into an xarray, reducing memory used by delayed ref heads and making it more efficient to add/remove/find delayed ref heads. The rest are mostly cleanups and refactorings, removing some dead code, deduplicating code, move code around, etc. More details in the changelogs.

Thanks,
Qu

Quoted 30 lines

Filipe Manana (18):
btrfs: 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(-)
#30 lore raw
Quoted 5 lines · Qu Wenruo
Quoted 2 lines · 在 2024/10/25 02:54, [email protected] 写道:

From: Filipe Manana <[email protected]>

Quoted 7 lines
Quoted 5 lines

This converts the rb-tree that tracks delayed ref heads into an xarray, reducing memory used by delayed ref heads and making it more efficient to add/remove/find delayed ref heads. The rest are mostly cleanups and refactorings, removing some dead code, deduplicating code, move code around, etc. More details in the changelogs.

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