[RFC,16/39] btrfs: Rename tree_entry to simple_node and export it

Message ID	20200317081125.36289-17-wqu@suse.com (mailing list archive)
State	New, archived
Headers	show Return-Path: <SRS0=Lj+Q=5C=vger.kernel.org=linux-btrfs-owner@kernel.org> 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 Message-Id: <20200317081125.36289-17-wqu@suse.com> In-Reply-To: <20200317081125.36289-1-wqu@suse.com> References: <20200317081125.36289-1-wqu@suse.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk
Series	btrfs: qgroup: Use backref cache based backref walk for commit roots \| expand [RFC,00/39] btrfs: qgroup: Use backref cache based backref walk for commit roots [RFC,01/39] btrfs: backref: Introduce the skeleton of btrfs_backref_iter [RFC,02/39] btrfs: backref: Implement btrfs_backref_iter_next() [RFC,03/39] btrfs: relocation: Use btrfs_backref_iter infrastructure [RFC,04/39] btrfs: relocation: Rename mark_block_processed() and __mark_block_processed() [RFC,05/39] btrfs: relocation: Add backref_cache::pending_edge and backref_cache::useless_node memb… [RFC,06/39] btrfs: relocation: Add backref_cache::fs_info member [RFC,07/39] btrfs: relocation: Make reloc root search specific for relocation backref cache [RFC,08/39] btrfs: relocation: Refactor direct tree backref processing into its own function [RFC,09/39] btrfs: relocation: Refactor indirect tree backref processing into its own function [RFC,10/39] btrfs: relocation: Use wrapper to replace open-coded edge linking [RFC,11/39] btrfs: relocation: Specify essential members for alloc_backref_node() [RFC,12/39] btrfs: relocation: Remove the open-coded goto loop for breadth-first search [RFC,13/39] btrfs: relocation: Refactor the finishing part of upper linkage into finish_upper_links… [RFC,14/39] btrfs: relocation: Refactor the useless nodes handling into its own function [RFC,15/39] btrfs: Move backref node/edge/cache structure to backref.h [RFC,16/39] btrfs: Rename tree_entry to simple_node and export it [RFC,17/39] btrfs: Move backref_cache_init() to backref.c [RFC,18/39] btrfs: Move alloc_backref_node() to backref.c [RFC,19/39] btrfs: Move alloc_backref_edge() to backref.c [RFC,20/39] btrfs: Move link_backref_edge() to backref.c [RFC,21/39] btrfs: Move free_backref_node() and free_backref_edge() to backref.h [RFC,22/39] btrfs: Move drop_backref_node() and needed facilities to backref.h [RFC,23/39] btrfs: Rename remove_backref_node() to cleanup_backref_node() and move it to backref.c [RFC,24/39] btrfs: Rename backref_cache_cleanup() to backref_cache_release() and move it to backref… [RFC,25/39] btrfs: Rename backref_tree_panic() to backref_cache_panic(), and move it to backref.c [RFC,26/39] btrfs: Rename should_ignore_root() to should_ignore_reloc_root() and export it [RFC,27/39] btrfs: relocation: Open-code read_fs_root() for handle_indirect_tree_backref() [RFC,28/39] btrfs: Rename handle_one_tree_block() to backref_cache_add_one_tree_block() and move it… [RFC,29/39] btrfs: Rename finish_upper_links() to backref_cache_finish_upper_links() and move it to… [RFC,30/39] btrfs: relocation: Move error handling of build_backref_tree() to backref.c [RFC,31/39] btrfs: relocation: Use btrfs_find_all_leaves() to locate parent tree leaves of a data e… [RFC,32/39] btrfs: backref: Only ignore reloc roots for indrect backref resolve if the backref cach… [RFC,33/39] btrfs: qgroup: Introduce qgroup backref cache [RFC,34/39] btrfs: qgroup: Introduce qgroup_backref_cache_build() function [RFC,35/39] btrfs: qgroup: Introduce a function to iterate through backref_cache to find all parent… [RFC,36/39] btrfs: qgroup: Introduce helpers to get needed tree block info [RFC,37/39] btrfs: qgroup: Introduce verification for function to ensure old roots ulist matches bt… [RFC,38/39] btrfs: qgroup: Introduce a new function to get old_roots ulist using backref cache [RFC,39/39] btrfs: qgroup: Use backref cache to speed up old_roots search

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

[RFC,16/39] btrfs: Rename tree_entry to simple_node and export it

Commit Message

Patch