linux-btrfs.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Qu Wenruo <wqu@suse.com>
To: linux-btrfs@vger.kernel.org
Subject: [PATCH RFC 16/39] btrfs: Rename tree_entry to simple_node and export it
Date: Tue, 17 Mar 2020 16:11:02 +0800	[thread overview]
Message-ID: <20200317081125.36289-17-wqu@suse.com> (raw)
In-Reply-To: <20200317081125.36289-1-wqu@suse.com>

Structure tree_entry provides a very simple rb_tree which only uses
bytenr as search index.

That tree_entry is used in 3 structures: backref_node, mapping_node and
tree_block.

Since we're going to make backref_node independnt from relocation, it's
a good time to extract the tree_entry into simple_node, and export it
into misc.h.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 fs/btrfs/backref.h    |   6 ++-
 fs/btrfs/misc.h       |  54 +++++++++++++++++++++
 fs/btrfs/relocation.c | 109 ++++++++++++++----------------------------
 3 files changed, 94 insertions(+), 75 deletions(-)

diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index 1eb771627e26..f119fc7022ab 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -158,8 +158,10 @@ btrfs_backref_iter_release(struct btrfs_backref_iter *iter)
  * present a tree block in the backref cache
  */
 struct backref_node {
-	struct rb_node rb_node;
-	u64 bytenr;
+	struct {
+		struct rb_node rb_node;
+		u64 bytenr;
+	}; /* Use simple_node for search/insert */
 
 	u64 new_bytenr;
 	/* objectid of tree block owner, can be not uptodate */
diff --git a/fs/btrfs/misc.h b/fs/btrfs/misc.h
index 72bab64ecf60..d199bfdb210e 100644
--- a/fs/btrfs/misc.h
+++ b/fs/btrfs/misc.h
@@ -6,6 +6,7 @@
 #include <linux/sched.h>
 #include <linux/wait.h>
 #include <asm/div64.h>
+#include <linux/rbtree.h>
 
 #define in_range(b, first, len) ((b) >= (first) && (b) < (first) + (len))
 
@@ -58,4 +59,57 @@ static inline bool has_single_bit_set(u64 n)
 	return is_power_of_two_u64(n);
 }
 
+/*
+ * Simple bytenr based rb_tree relate structures
+ *
+ * Any structure wants to use bytenr as single search index should have their
+ * structure start with these members.
+ */
+struct simple_node {
+	struct rb_node rb_node;
+	u64 bytenr;
+};
+
+static inline struct rb_node *simple_search(struct rb_root *root, u64 bytenr)
+{
+	struct rb_node *n = root->rb_node;
+	struct simple_node *entry;
+
+	while (n) {
+		entry = rb_entry(n, struct simple_node, rb_node);
+
+		if (bytenr < entry->bytenr)
+			n = n->rb_left;
+		else if (bytenr > entry->bytenr)
+			n = n->rb_right;
+		else
+			return n;
+	}
+	return NULL;
+}
+
+static inline struct rb_node *simple_insert(struct rb_root *root, u64 bytenr,
+					    struct rb_node *node)
+{
+	struct rb_node **p = &root->rb_node;
+	struct rb_node *parent = NULL;
+	struct simple_node *entry;
+
+	while (*p) {
+		parent = *p;
+		entry = rb_entry(parent, struct simple_node, rb_node);
+
+		if (bytenr < entry->bytenr)
+			p = &(*p)->rb_left;
+		else if (bytenr > entry->bytenr)
+			p = &(*p)->rb_right;
+		else
+			return parent;
+	}
+
+	rb_link_node(node, parent, p);
+	rb_insert_color(node, root);
+	return NULL;
+}
+
 #endif
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 1264bd5c067d..41723b0fc512 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -23,6 +23,7 @@
 #include "delalloc-space.h"
 #include "block-group.h"
 #include "backref.h"
+#include "misc.h"
 
 #define RELOCATION_RESERVED_NODES	256
 
@@ -85,8 +86,10 @@ struct tree_entry {
  * map address of tree root to tree
  */
 struct mapping_node {
-	struct rb_node rb_node;
-	u64 bytenr;
+	struct {
+		struct rb_node rb_node;
+		u64 bytenr;
+	}; /* Use simle_node for search_insert */
 	void *data;
 };
 
@@ -99,8 +102,10 @@ struct mapping_tree {
  * present a tree block to process
  */
 struct tree_block {
-	struct rb_node rb_node;
-	u64 bytenr;
+	struct {
+		struct rb_node rb_node;
+		u64 bytenr;
+	}; /* Use simple_node for search/insert */
 	struct btrfs_key key;
 	unsigned int level:8;
 	unsigned int key_ready:1;
@@ -291,48 +296,6 @@ static void free_backref_edge(struct backref_cache *cache,
 	}
 }
 
-static struct rb_node *tree_insert(struct rb_root *root, u64 bytenr,
-				   struct rb_node *node)
-{
-	struct rb_node **p = &root->rb_node;
-	struct rb_node *parent = NULL;
-	struct tree_entry *entry;
-
-	while (*p) {
-		parent = *p;
-		entry = rb_entry(parent, struct tree_entry, rb_node);
-
-		if (bytenr < entry->bytenr)
-			p = &(*p)->rb_left;
-		else if (bytenr > entry->bytenr)
-			p = &(*p)->rb_right;
-		else
-			return parent;
-	}
-
-	rb_link_node(node, parent, p);
-	rb_insert_color(node, root);
-	return NULL;
-}
-
-static struct rb_node *tree_search(struct rb_root *root, u64 bytenr)
-{
-	struct rb_node *n = root->rb_node;
-	struct tree_entry *entry;
-
-	while (n) {
-		entry = rb_entry(n, struct tree_entry, rb_node);
-
-		if (bytenr < entry->bytenr)
-			n = n->rb_left;
-		else if (bytenr > entry->bytenr)
-			n = n->rb_right;
-		else
-			return n;
-	}
-	return NULL;
-}
-
 static void backref_tree_panic(struct rb_node *rb_node, int errno, u64 bytenr)
 {
 
@@ -471,7 +434,7 @@ static void update_backref_node(struct backref_cache *cache,
 	struct rb_node *rb_node;
 	rb_erase(&node->rb_node, &cache->rb_root);
 	node->bytenr = bytenr;
-	rb_node = tree_insert(&cache->rb_root, node->bytenr, &node->rb_node);
+	rb_node = simple_insert(&cache->rb_root, node->bytenr, &node->rb_node);
 	if (rb_node)
 		backref_tree_panic(rb_node, -EEXIST, bytenr);
 }
@@ -596,7 +559,7 @@ struct btrfs_root *find_reloc_root(struct btrfs_fs_info *fs_info, u64 bytenr)
 
 	ASSERT(rc);
 	spin_lock(&rc->reloc_root_tree.lock);
-	rb_node = tree_search(&rc->reloc_root_tree.rb_root, bytenr);
+	rb_node = simple_search(&rc->reloc_root_tree.rb_root, bytenr);
 	if (rb_node) {
 		node = rb_entry(rb_node, struct mapping_node, rb_node);
 		root = (struct btrfs_root *)node->data;
@@ -664,7 +627,7 @@ static int handle_direct_tree_backref(struct backref_cache *cache,
 	if (!edge)
 		return -ENOMEM;
 
-	rb_node = tree_search(&cache->rb_root, ref_key->offset);
+	rb_node = simple_search(&cache->rb_root, ref_key->offset);
 	if (!rb_node) {
 		/* Parent node not yet cached */
 		upper = alloc_backref_node(cache, ref_key->offset,
@@ -787,7 +750,7 @@ static int handle_indirect_tree_backref(struct backref_cache *cache,
 		}
 
 		eb = path->nodes[level];
-		rb_node = tree_search(&cache->rb_root, eb->start);
+		rb_node = simple_search(&cache->rb_root, eb->start);
 		if (!rb_node) {
 			upper = alloc_backref_node(cache, eb->start,
 						   lower->level + 1);
@@ -991,8 +954,8 @@ static int finish_upper_links(struct backref_cache *cache,
 
 	/* Insert this node to cache if it's not cowonly */
 	if (!start->cowonly) {
-		rb_node = tree_insert(&cache->rb_root, start->bytenr,
-				      &start->rb_node);
+		rb_node = simple_insert(&cache->rb_root, start->bytenr,
+					&start->rb_node);
 		if (rb_node)
 			backref_tree_panic(rb_node, -EEXIST, start->bytenr);
 		list_add_tail(&start->lower, &cache->leaves);
@@ -1059,8 +1022,8 @@ static int finish_upper_links(struct backref_cache *cache,
 
 		/* Only cache non-cowonly (subvolume trees) tree blocks */
 		if (!upper->cowonly) {
-			rb_node = tree_insert(&cache->rb_root, upper->bytenr,
-					      &upper->rb_node);
+			rb_node = simple_insert(&cache->rb_root, upper->bytenr,
+						&upper->rb_node);
 			if (rb_node) {
 				backref_tree_panic(rb_node, -EEXIST,
 						   upper->bytenr);
@@ -1305,7 +1268,7 @@ static int clone_backref_node(struct btrfs_trans_handle *trans,
 	if (cache->last_trans > 0)
 		update_backref_cache(trans, cache);
 
-	rb_node = tree_search(&cache->rb_root, src->commit_root->start);
+	rb_node = simple_search(&cache->rb_root, src->commit_root->start);
 	if (rb_node) {
 		node = rb_entry(rb_node, struct backref_node, rb_node);
 		if (node->detached)
@@ -1315,8 +1278,8 @@ static int clone_backref_node(struct btrfs_trans_handle *trans,
 	}
 
 	if (!node) {
-		rb_node = tree_search(&cache->rb_root,
-				      reloc_root->commit_root->start);
+		rb_node = simple_search(&cache->rb_root,
+					reloc_root->commit_root->start);
 		if (rb_node) {
 			node = rb_entry(rb_node, struct backref_node,
 					rb_node);
@@ -1349,8 +1312,8 @@ static int clone_backref_node(struct btrfs_trans_handle *trans,
 		list_add_tail(&new_node->lower, &cache->leaves);
 	}
 
-	rb_node = tree_insert(&cache->rb_root, new_node->bytenr,
-			      &new_node->rb_node);
+	rb_node = simple_insert(&cache->rb_root, new_node->bytenr,
+				&new_node->rb_node);
 	if (rb_node)
 		backref_tree_panic(rb_node, -EEXIST, new_node->bytenr);
 
@@ -1390,8 +1353,8 @@ static int __must_check __add_reloc_root(struct btrfs_root *root)
 	node->data = root;
 
 	spin_lock(&rc->reloc_root_tree.lock);
-	rb_node = tree_insert(&rc->reloc_root_tree.rb_root,
-			      node->bytenr, &node->rb_node);
+	rb_node = simple_insert(&rc->reloc_root_tree.rb_root,
+				node->bytenr, &node->rb_node);
 	spin_unlock(&rc->reloc_root_tree.lock);
 	if (rb_node) {
 		btrfs_panic(fs_info, -EEXIST,
@@ -1416,8 +1379,8 @@ static void __del_reloc_root(struct btrfs_root *root)
 
 	if (rc && root->node) {
 		spin_lock(&rc->reloc_root_tree.lock);
-		rb_node = tree_search(&rc->reloc_root_tree.rb_root,
-				      root->node->start);
+		rb_node = simple_search(&rc->reloc_root_tree.rb_root,
+					root->node->start);
 		if (rb_node) {
 			node = rb_entry(rb_node, struct mapping_node, rb_node);
 			rb_erase(&node->rb_node, &rc->reloc_root_tree.rb_root);
@@ -1446,8 +1409,8 @@ static int __update_reloc_root(struct btrfs_root *root, u64 new_bytenr)
 	struct reloc_control *rc = fs_info->reloc_ctl;
 
 	spin_lock(&rc->reloc_root_tree.lock);
-	rb_node = tree_search(&rc->reloc_root_tree.rb_root,
-			      root->node->start);
+	rb_node = simple_search(&rc->reloc_root_tree.rb_root,
+				root->node->start);
 	if (rb_node) {
 		node = rb_entry(rb_node, struct mapping_node, rb_node);
 		rb_erase(&node->rb_node, &rc->reloc_root_tree.rb_root);
@@ -1460,8 +1423,8 @@ static int __update_reloc_root(struct btrfs_root *root, u64 new_bytenr)
 
 	spin_lock(&rc->reloc_root_tree.lock);
 	node->bytenr = new_bytenr;
-	rb_node = tree_insert(&rc->reloc_root_tree.rb_root,
-			      node->bytenr, &node->rb_node);
+	rb_node = simple_insert(&rc->reloc_root_tree.rb_root,
+				node->bytenr, &node->rb_node);
 	spin_unlock(&rc->reloc_root_tree.lock);
 	if (rb_node)
 		backref_tree_panic(rb_node, -EEXIST, node->bytenr);
@@ -3548,7 +3511,7 @@ static int add_tree_block(struct reloc_control *rc,
 	block->level = level;
 	block->key_ready = 0;
 
-	rb_node = tree_insert(blocks, block->bytenr, &block->rb_node);
+	rb_node = simple_insert(blocks, block->bytenr, &block->rb_node);
 	if (rb_node)
 		backref_tree_panic(rb_node, -EEXIST, block->bytenr);
 
@@ -3571,7 +3534,7 @@ static int __add_tree_block(struct reloc_control *rc,
 	if (tree_block_processed(bytenr, rc))
 		return 0;
 
-	if (tree_search(blocks, bytenr))
+	if (simple_search(blocks, bytenr))
 		return 0;
 
 	path = btrfs_alloc_path();
@@ -3775,7 +3738,7 @@ static int find_data_references(struct reloc_control *rc,
 		counted = 0;
 	else
 		counted = 1;
-	rb_node = tree_search(blocks, leaf->start);
+	rb_node = simple_search(blocks, leaf->start);
 	if (rb_node) {
 		if (counted)
 			added = 1;
@@ -3801,7 +3764,7 @@ static int find_data_references(struct reloc_control *rc,
 				counted = 0;
 			else
 				counted = 1;
-			rb_node = tree_search(blocks, leaf->start);
+			rb_node = simple_search(blocks, leaf->start);
 			if (rb_node) {
 				if (counted)
 					added = 1;
@@ -3845,8 +3808,8 @@ static int find_data_references(struct reloc_control *rc,
 			btrfs_item_key_to_cpu(leaf, &block->key, 0);
 			block->level = 0;
 			block->key_ready = 1;
-			rb_node = tree_insert(blocks, block->bytenr,
-					      &block->rb_node);
+			rb_node = simple_insert(blocks, block->bytenr,
+						&block->rb_node);
 			if (rb_node)
 				backref_tree_panic(rb_node, -EEXIST,
 						   block->bytenr);
-- 
2.25.1


  parent reply	other threads:[~2020-03-17  8:12 UTC|newest]

Thread overview: 57+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-03-17  8:10 [PATCH RFC 00/39] btrfs: qgroup: Use backref cache based backref walk for commit roots Qu Wenruo
2020-03-17  8:10 ` [PATCH RFC 01/39] btrfs: backref: Introduce the skeleton of btrfs_backref_iter Qu Wenruo
2020-03-19 14:46   ` Josef Bacik
2020-03-17  8:10 ` [PATCH RFC 02/39] btrfs: backref: Implement btrfs_backref_iter_next() Qu Wenruo
2020-03-19 15:05   ` Josef Bacik
2020-03-17  8:10 ` [PATCH RFC 03/39] btrfs: relocation: Use btrfs_backref_iter infrastructure Qu Wenruo
2020-03-19 15:16   ` Josef Bacik
2020-03-17  8:10 ` [PATCH RFC 04/39] btrfs: relocation: Rename mark_block_processed() and __mark_block_processed() Qu Wenruo
2020-03-19 15:18   ` Josef Bacik
2020-03-17  8:10 ` [PATCH RFC 05/39] btrfs: relocation: Add backref_cache::pending_edge and backref_cache::useless_node members Qu Wenruo
2020-03-19 15:21   ` Josef Bacik
2020-03-17  8:10 ` [PATCH RFC 06/39] btrfs: relocation: Add backref_cache::fs_info member Qu Wenruo
2020-03-19 15:21   ` Josef Bacik
2020-03-17  8:10 ` [PATCH RFC 07/39] btrfs: relocation: Make reloc root search specific for relocation backref cache Qu Wenruo
2020-03-19 15:27   ` Josef Bacik
2020-03-19 15:28   ` Josef Bacik
2020-03-19 15:30   ` Josef Bacik
2020-03-17  8:10 ` [PATCH RFC 08/39] btrfs: relocation: Refactor direct tree backref processing into its own function Qu Wenruo
2020-03-19 15:31   ` Josef Bacik
2020-03-17  8:10 ` [PATCH RFC 09/39] btrfs: relocation: Refactor indirect " Qu Wenruo
2020-03-19 15:36   ` Josef Bacik
2020-03-17  8:10 ` [PATCH RFC 10/39] btrfs: relocation: Use wrapper to replace open-coded edge linking Qu Wenruo
2020-03-17  8:10 ` [PATCH RFC 11/39] btrfs: relocation: Specify essential members for alloc_backref_node() Qu Wenruo
2020-03-17  8:10 ` [PATCH RFC 12/39] btrfs: relocation: Remove the open-coded goto loop for breadth-first search Qu Wenruo
2020-03-19 15:42   ` Josef Bacik
2020-03-17  8:10 ` [PATCH RFC 13/39] btrfs: relocation: Refactor the finishing part of upper linkage into finish_upper_links() Qu Wenruo
2020-03-19 17:19   ` Josef Bacik
2020-03-17  8:11 ` [PATCH RFC 14/39] btrfs: relocation: Refactor the useless nodes handling into its own function Qu Wenruo
2020-03-19 17:21   ` Josef Bacik
2020-03-17  8:11 ` [PATCH RFC 15/39] btrfs: Move backref node/edge/cache structure to backref.h Qu Wenruo
2020-03-19 17:26   ` Josef Bacik
2020-03-17  8:11 ` Qu Wenruo [this message]
2020-03-17  8:11 ` [PATCH RFC 17/39] btrfs: Move backref_cache_init() to backref.c Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 18/39] btrfs: Move alloc_backref_node() " Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 19/39] btrfs: Move alloc_backref_edge() " Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 20/39] btrfs: Move link_backref_edge() " Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 21/39] btrfs: Move free_backref_node() and free_backref_edge() to backref.h Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 22/39] btrfs: Move drop_backref_node() and needed facilities " Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 23/39] btrfs: Rename remove_backref_node() to cleanup_backref_node() and move it to backref.c Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 24/39] btrfs: Rename backref_cache_cleanup() to backref_cache_release() " Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 25/39] btrfs: Rename backref_tree_panic() to backref_cache_panic(), " Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 26/39] btrfs: Rename should_ignore_root() to should_ignore_reloc_root() and export it Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 27/39] btrfs: relocation: Open-code read_fs_root() for handle_indirect_tree_backref() Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 28/39] btrfs: Rename handle_one_tree_block() to backref_cache_add_one_tree_block() and move it to backref.c Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 29/39] btrfs: Rename finish_upper_links() to backref_cache_finish_upper_links() " Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 30/39] btrfs: relocation: Move error handling of build_backref_tree() " Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 31/39] btrfs: relocation: Use btrfs_find_all_leaves() to locate parent tree leaves of a data extent Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 32/39] btrfs: backref: Only ignore reloc roots for indrect backref resolve if the backref cache is for reloction purpose Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 33/39] btrfs: qgroup: Introduce qgroup backref cache Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 34/39] btrfs: qgroup: Introduce qgroup_backref_cache_build() function Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 35/39] btrfs: qgroup: Introduce a function to iterate through backref_cache to find all parents for specified node Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 36/39] btrfs: qgroup: Introduce helpers to get needed tree block info Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 37/39] btrfs: qgroup: Introduce verification for function to ensure old roots ulist matches btrfs_find_all_roots() result Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 38/39] btrfs: qgroup: Introduce a new function to get old_roots ulist using backref cache Qu Wenruo
2020-03-17  8:11 ` [PATCH RFC 39/39] btrfs: qgroup: Use backref cache to speed up old_roots search Qu Wenruo
2020-03-19 17:26 ` [PATCH RFC 00/39] btrfs: qgroup: Use backref cache based backref walk for commit roots Josef Bacik
2020-03-25 18:30 ` David Sterba

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20200317081125.36289-17-wqu@suse.com \
    --to=wqu@suse.com \
    --cc=linux-btrfs@vger.kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).