From patchwork Tue Mar 3 07:13:51 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 11417279 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 67266930 for ; Tue, 3 Mar 2020 07:14:24 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 5046820CC7 for ; Tue, 3 Mar 2020 07:14:24 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727587AbgCCHOX (ORCPT ); Tue, 3 Mar 2020 02:14:23 -0500 Received: from mx2.suse.de ([195.135.220.15]:56536 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727580AbgCCHOX (ORCPT ); Tue, 3 Mar 2020 02:14:23 -0500 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 7E21BB135 for ; Tue, 3 Mar 2020 07:14:20 +0000 (UTC) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH 01/19] btrfs: Move backref node/edge/cache structure to backref.h Date: Tue, 3 Mar 2020 15:13:51 +0800 Message-Id: <20200303071409.57982-2-wqu@suse.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20200303071409.57982-1-wqu@suse.com> References: <20200303071409.57982-1-wqu@suse.com> MIME-Version: 1.0 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org These 3 structures are the main part of backref cache, move them to backref.h to build the basis for later reuse. Signed-off-by: Qu Wenruo --- fs/btrfs/backref.h | 98 +++++++++++++++++++++++++++++++++++++++++++ fs/btrfs/relocation.c | 93 +--------------------------------------- 2 files changed, 100 insertions(+), 91 deletions(-) diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h index 42fd76dfe553..3cf79fafdf07 100644 --- a/fs/btrfs/backref.h +++ b/fs/btrfs/backref.h @@ -168,4 +168,102 @@ btrfs_backref_iter_release(struct btrfs_backref_iter *iter) memset(&iter->cur_key, 0, sizeof(iter->cur_key)); } +/* + * Backref cache related structures. + * + * The whole objective of backref_cache is to build a bi-directional map + * of tree blocks (represented by backref_node) and all their parents. + */ + +/* + * present a tree block in the backref cache + */ +struct backref_node { + struct rb_node rb_node; + u64 bytenr; + + u64 new_bytenr; + /* objectid of tree block owner, can be not uptodate */ + u64 owner; + /* link to pending, changed or detached list */ + struct list_head list; + + /* List of upper level edges, which links this node to its parent(s) */ + struct list_head upper; + /* List of lower level edges, which links this node to its child(ren) */ + struct list_head lower; + + /* NULL if this node is not tree root */ + struct btrfs_root *root; + /* extent buffer got by COW the block */ + struct extent_buffer *eb; + /* level of tree block */ + unsigned int level:8; + /* is the block in non-reference counted tree */ + unsigned int cowonly:1; + /* 1 if no child node in the cache */ + unsigned int lowest:1; + /* is the extent buffer locked */ + unsigned int locked:1; + /* has the block been processed */ + unsigned int processed:1; + /* have backrefs of this block been checked */ + unsigned int checked:1; + /* + * 1 if corresponding block has been cowed but some upper + * level block pointers may not point to the new location + */ + unsigned int pending:1; + /* + * 1 if the backref node isn't connected to any other + * backref node. + */ + unsigned int detached:1; +}; + +#define LOWER 0 +#define UPPER 1 + +/* + * present an edge connecting upper and lower backref nodes. + */ +struct backref_edge { + /* + * list[LOWER] is linked to backref_node::upper of lower level node, + * and list[UPPER] is linked to backref_node::lower of upper level node. + * + * Also, build_backref_tree() uses list[UPPER] for pending edges, before + * linking list[UPPER] to its upper level nodes. + */ + struct list_head list[2]; + + /* Two related nodes */ + struct backref_node *node[2]; +}; + + +struct backref_cache { + /* red black tree of all backref nodes in the cache */ + struct rb_root rb_root; + /* for passing backref nodes to btrfs_reloc_cow_block */ + struct backref_node *path[BTRFS_MAX_LEVEL]; + /* + * list of blocks that have been cowed but some block + * pointers in upper level blocks may not reflect the + * new location + */ + struct list_head pending[BTRFS_MAX_LEVEL]; + /* list of backref nodes with no child node */ + struct list_head leaves; + /* list of blocks that have been cowed in current transaction */ + struct list_head changed; + /* list of detached backref node. */ + struct list_head detached; + + u64 last_trans; + + int nr_nodes; + int nr_edges; +}; + #endif diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c index 93364eb07a61..8d939c7837c8 100644 --- a/fs/btrfs/relocation.c +++ b/fs/btrfs/relocation.c @@ -24,6 +24,8 @@ #include "block-group.h" #include "backref.h" +#define RELOCATION_RESERVED_NODES 256 + /* * Relocation overview * @@ -79,97 +81,6 @@ struct tree_entry { u64 bytenr; }; -/* - * present a tree block in the backref cache - */ -struct backref_node { - struct rb_node rb_node; - u64 bytenr; - - u64 new_bytenr; - /* objectid of tree block owner, can be not uptodate */ - u64 owner; - /* link to pending, changed or detached list */ - struct list_head list; - - /* List of upper level edges, which links this node to its parent(s) */ - struct list_head upper; - /* List of lower level edges, which links this node to its child(ren) */ - struct list_head lower; - - /* NULL if this node is not tree root */ - struct btrfs_root *root; - /* extent buffer got by COW the block */ - struct extent_buffer *eb; - /* level of tree block */ - unsigned int level:8; - /* is the block in non-reference counted tree */ - unsigned int cowonly:1; - /* 1 if no child node in the cache */ - unsigned int lowest:1; - /* is the extent buffer locked */ - unsigned int locked:1; - /* has the block been processed */ - unsigned int processed:1; - /* have backrefs of this block been checked */ - unsigned int checked:1; - /* - * 1 if corresponding block has been cowed but some upper - * level block pointers may not point to the new location - */ - unsigned int pending:1; - /* - * 1 if the backref node isn't connected to any other - * backref node. - */ - unsigned int detached:1; -}; - -#define LOWER 0 -#define UPPER 1 -#define RELOCATION_RESERVED_NODES 256 -/* - * present an edge connecting upper and lower backref nodes. - */ -struct backref_edge { - /* - * list[LOWER] is linked to backref_node::upper of lower level node, - * and list[UPPER] is linked to backref_node::lower of upper level node. - * - * Also, build_backref_tree() uses list[UPPER] for pending edges, before - * linking list[UPPER] to its upper level nodes. - */ - struct list_head list[2]; - - /* Two related nodes */ - struct backref_node *node[2]; -}; - - -struct backref_cache { - /* red black tree of all backref nodes in the cache */ - struct rb_root rb_root; - /* for passing backref nodes to btrfs_reloc_cow_block */ - struct backref_node *path[BTRFS_MAX_LEVEL]; - /* - * list of blocks that have been cowed but some block - * pointers in upper level blocks may not reflect the - * new location - */ - struct list_head pending[BTRFS_MAX_LEVEL]; - /* list of backref nodes with no child node */ - struct list_head leaves; - /* list of blocks that have been cowed in current transaction */ - struct list_head changed; - /* list of detached backref node. */ - struct list_head detached; - - u64 last_trans; - - int nr_nodes; - int nr_edges; -}; - /* * map address of tree root to tree */ From patchwork Tue Mar 3 07:13:52 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 11417281 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id A8E96930 for ; Tue, 3 Mar 2020 07:14:30 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 7CF4120CC7 for ; Tue, 3 Mar 2020 07:14:30 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727588AbgCCHO3 (ORCPT ); Tue, 3 Mar 2020 02:14:29 -0500 Received: from mx2.suse.de ([195.135.220.15]:56568 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727520AbgCCHO3 (ORCPT ); Tue, 3 Mar 2020 02:14:29 -0500 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 5D44AB19C for ; Tue, 3 Mar 2020 07:14:26 +0000 (UTC) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH 02/19] btrfs: Rename tree_entry to simple_node and export it Date: Tue, 3 Mar 2020 15:13:52 +0800 Message-Id: <20200303071409.57982-3-wqu@suse.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20200303071409.57982-1-wqu@suse.com> References: <20200303071409.57982-1-wqu@suse.com> MIME-Version: 1.0 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org 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 --- 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 3cf79fafdf07..923788fa03ef 100644 --- a/fs/btrfs/backref.h +++ b/fs/btrfs/backref.h @@ -179,8 +179,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 #include #include +#include #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 8d939c7837c8..50348a58bb43 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; @@ -284,48 +289,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) { @@ -464,7 +427,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); } @@ -588,7 +551,7 @@ static struct btrfs_root *find_reloc_root(struct reloc_control *rc, struct btrfs_root *root = NULL; 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; @@ -649,7 +612,7 @@ static int handle_one_tree_backref(struct reloc_control *rc, 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, @@ -746,7 +709,7 @@ static int handle_one_tree_backref(struct reloc_control *rc, } 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); @@ -988,8 +951,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); @@ -1158,8 +1121,8 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, */ ASSERT(node->checked); if (!node->cowonly) { - 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, node->bytenr); list_add_tail(&node->lower, &cache->leaves); @@ -1247,7 +1210,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) @@ -1257,8 +1220,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); @@ -1291,8 +1254,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); @@ -1332,8 +1295,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, @@ -1358,8 +1321,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); @@ -1388,8 +1351,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); @@ -1402,8 +1365,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); @@ -3490,7 +3453,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); @@ -3513,7 +3476,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(); @@ -3717,7 +3680,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; @@ -3743,7 +3706,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; @@ -3787,8 +3750,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); From patchwork Tue Mar 3 07:13:53 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 11417283 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id C57D817E0 for ; Tue, 3 Mar 2020 07:14:32 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id AF9092146E for ; Tue, 3 Mar 2020 07:14:32 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727591AbgCCHOb (ORCPT ); Tue, 3 Mar 2020 02:14:31 -0500 Received: from mx2.suse.de ([195.135.220.15]:56578 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727520AbgCCHOb (ORCPT ); Tue, 3 Mar 2020 02:14:31 -0500 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id E9AE9B135 for ; Tue, 3 Mar 2020 07:14:29 +0000 (UTC) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH 03/19] btrfs: relocation: Make reloc root search specific for relocation backref cache Date: Tue, 3 Mar 2020 15:13:53 +0800 Message-Id: <20200303071409.57982-4-wqu@suse.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20200303071409.57982-1-wqu@suse.com> References: <20200303071409.57982-1-wqu@suse.com> MIME-Version: 1.0 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org find_reloc_root() searches reloc_control::reloc_root_tree to find the reloc root. This behavior is only useful for relocation backref cache. For the incoming more generic purposed backref cache, we don't care about who owns the reloc root, but only care if it's a reloc root. So this patch makes the following modifications to make the reloc root search more specific to relocation backref: - Add backref_node::is_reloc_root This will be an extra indicator for generic purposed backref cache. User doesn't need to read root key from backref_node::root to determine if it's a reloc root. - Add backref_cache::is_reloc This will allow backref cache code to do different behavior for generic purposed backref cache and relocation backref cache. - Make find_reloc_root() to accept fs_info Just a personal taste. - Export find_reloc_root() So backref.c can utilize this function. Signed-off-by: Qu Wenruo --- fs/btrfs/backref.h | 14 ++++++++++++++ fs/btrfs/ctree.h | 2 ++ fs/btrfs/relocation.c | 23 +++++++++++++++-------- 3 files changed, 31 insertions(+), 8 deletions(-) diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h index 923788fa03ef..fbb08b5429ca 100644 --- a/fs/btrfs/backref.h +++ b/fs/btrfs/backref.h @@ -221,6 +221,12 @@ struct backref_node { * backref node. */ unsigned int detached:1; + + /* + * For generic purpose backref cache, where we only care if it's a reloc + * root, doesn't care the source subvolid. + */ + unsigned int is_reloc_root:1; }; #define LOWER 0 @@ -266,6 +272,14 @@ struct backref_cache { int nr_nodes; int nr_edges; + + /* + * Whether this cache is for relocation + * + * Reloction backref cache require more info for reloc root compared + * to generic backref cache. + */ + unsigned int is_reloc; }; #endif diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h index ea5d0675465a..b57bb3e5f1f2 100644 --- a/fs/btrfs/ctree.h +++ b/fs/btrfs/ctree.h @@ -3381,6 +3381,8 @@ void btrfs_reloc_pre_snapshot(struct btrfs_pending_snapshot *pending, u64 *bytes_to_reserve); int btrfs_reloc_post_snapshot(struct btrfs_trans_handle *trans, struct btrfs_pending_snapshot *pending); +struct btrfs_root *find_reloc_root(struct btrfs_fs_info *fs_info, + u64 bytenr); /* scrub.c */ int btrfs_scrub_dev(struct btrfs_fs_info *fs_info, u64 devid, u64 start, diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c index 50348a58bb43..374efb117387 100644 --- a/fs/btrfs/relocation.c +++ b/fs/btrfs/relocation.c @@ -185,7 +185,7 @@ static void mapping_tree_init(struct mapping_tree *tree) spin_lock_init(&tree->lock); } -static void backref_cache_init(struct backref_cache *cache) +static void backref_cache_init(struct backref_cache *cache, int is_reloc) { int i; cache->rb_root = RB_ROOT; @@ -194,6 +194,7 @@ static void backref_cache_init(struct backref_cache *cache) INIT_LIST_HEAD(&cache->changed); INIT_LIST_HEAD(&cache->detached); INIT_LIST_HEAD(&cache->leaves); + cache->is_reloc = is_reloc; } static void backref_cache_cleanup(struct backref_cache *cache) @@ -543,13 +544,15 @@ static int should_ignore_root(struct btrfs_root *root) /* * find reloc tree by address of tree root */ -static struct btrfs_root *find_reloc_root(struct reloc_control *rc, - u64 bytenr) +struct btrfs_root *find_reloc_root(struct btrfs_fs_info *fs_info, + u64 bytenr) { + struct reloc_control *rc = fs_info->reloc_ctl; struct rb_node *rb_node; struct mapping_node *node; struct btrfs_root *root = NULL; + ASSERT(rc); spin_lock(&rc->reloc_root_tree.lock); rb_node = simple_search(&rc->reloc_root_tree.rb_root, bytenr); if (rb_node) { @@ -601,10 +604,14 @@ static int handle_one_tree_backref(struct reloc_control *rc, /* Only reloc root uses backref pointing to itself */ if (ref_key->objectid == ref_key->offset) { - root = find_reloc_root(rc, cur->bytenr); - if (WARN_ON(!root)) - return -ENOENT; - cur->root = root; + cur->is_reloc_root = 1; + /* Only reloc backref cache cares exact root */ + if (cache->is_reloc) { + root = find_reloc_root(fs_info, cur->bytenr); + if (WARN_ON(!root)) + return -ENOENT; + cur->root = root; + } return 0; } @@ -4292,7 +4299,7 @@ static struct reloc_control *alloc_reloc_control(struct btrfs_fs_info *fs_info) INIT_LIST_HEAD(&rc->reloc_roots); INIT_LIST_HEAD(&rc->dirty_subvol_roots); - backref_cache_init(&rc->backref_cache); + backref_cache_init(&rc->backref_cache, 1); mapping_tree_init(&rc->reloc_root_tree); extent_io_tree_init(fs_info, &rc->processed_blocks, IO_TREE_RELOC_BLOCKS, NULL); From patchwork Tue Mar 3 07:13:54 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 11417285 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 00FE4924 for ; Tue, 3 Mar 2020 07:15:16 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id D4BDC2146E for ; Tue, 3 Mar 2020 07:15:15 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727531AbgCCHPP (ORCPT ); Tue, 3 Mar 2020 02:15:15 -0500 Received: from mx2.suse.de ([195.135.220.15]:56750 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727507AbgCCHPP (ORCPT ); Tue, 3 Mar 2020 02:15:15 -0500 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 1145CAC53 for ; Tue, 3 Mar 2020 07:15:10 +0000 (UTC) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH 04/19] btrfs: relocation: Add backref_cache::pending_edge and backref_cache::useless_node members Date: Tue, 3 Mar 2020 15:13:54 +0800 Message-Id: <20200303071409.57982-5-wqu@suse.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20200303071409.57982-1-wqu@suse.com> References: <20200303071409.57982-1-wqu@suse.com> MIME-Version: 1.0 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org These two new members will act the same as the existing local lists, @useless and @list in build_backref_tree(). This would kill two parameters for handle_one_tree_backref(), handle_one_tree_block(), finish_upper_links() and handle_useless_nodes(). Currently build_backref_tree() is only executed serially, thus moving such local list into backref_cache is still safe. Signed-off-by: Qu Wenruo --- fs/btrfs/backref.h | 6 ++++ fs/btrfs/relocation.c | 64 ++++++++++++++++++++++++------------------- 2 files changed, 42 insertions(+), 28 deletions(-) diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h index fbb08b5429ca..4ad1193c78e0 100644 --- a/fs/btrfs/backref.h +++ b/fs/btrfs/backref.h @@ -280,6 +280,12 @@ struct backref_cache { * to generic backref cache. */ unsigned int is_reloc; + + /* The list of unchecked backref edges during backref cache build */ + struct list_head pending_edge; + + /* The list of useless backref nodes during backref cache build */ + struct list_head useless_node; }; #endif diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c index 374efb117387..413a83d1d9f1 100644 --- a/fs/btrfs/relocation.c +++ b/fs/btrfs/relocation.c @@ -195,6 +195,8 @@ static void backref_cache_init(struct backref_cache *cache, int is_reloc) INIT_LIST_HEAD(&cache->detached); INIT_LIST_HEAD(&cache->leaves); cache->is_reloc = is_reloc; + INIT_LIST_HEAD(&cache->pending_edge); + INIT_LIST_HEAD(&cache->useless_node); } static void backref_cache_cleanup(struct backref_cache *cache) @@ -218,6 +220,8 @@ static void backref_cache_cleanup(struct backref_cache *cache) for (i = 0; i < BTRFS_MAX_LEVEL; i++) ASSERT(list_empty(&cache->pending[i])); + ASSERT(list_empty(&cache->pending_edge)); + ASSERT(list_empty(&cache->useless_node)); ASSERT(list_empty(&cache->changed)); ASSERT(list_empty(&cache->detached)); ASSERT(RB_EMPTY_ROOT(&cache->rb_root)); @@ -576,8 +580,6 @@ static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info, } static int handle_one_tree_backref(struct reloc_control *rc, - struct list_head *useless_node, - struct list_head *pending_edge, struct btrfs_path *path, struct btrfs_key *ref_key, struct btrfs_key *tree_key, @@ -585,6 +587,8 @@ static int handle_one_tree_backref(struct reloc_control *rc, { struct btrfs_fs_info *fs_info = rc->extent_root->fs_info; struct backref_cache *cache = &rc->backref_cache; + struct list_head *useless_node = &cache->useless_node; + struct list_head *pending_edge = &cache->pending_edge; struct backref_node *upper; struct backref_node *lower; struct backref_edge *edge; @@ -774,13 +778,12 @@ static int handle_one_tree_backref(struct reloc_control *rc, } static int handle_one_tree_block(struct reloc_control *rc, - struct list_head *useless_node, - struct list_head *pending_edge, struct btrfs_path *path, struct btrfs_backref_iter *iter, struct btrfs_key *node_key, struct backref_node *cur) { + struct backref_cache *cache = &rc->backref_cache; struct backref_edge *edge; struct backref_node *exist; int ret; @@ -819,7 +822,7 @@ static int handle_one_tree_block(struct reloc_control *rc, * check its backrefs */ if (!exist->checked) - list_add_tail(&edge->list[UPPER], pending_edge); + list_add_tail(&edge->list[UPPER], &cache->pending_edge); } else { exist = NULL; } @@ -864,8 +867,7 @@ static int handle_one_tree_block(struct reloc_control *rc, continue; } - ret = handle_one_tree_backref(rc, useless_node, pending_edge, path, - &key, node_key, cur); + ret = handle_one_tree_backref(rc, path, &key, node_key, cur); if (ret < 0) goto out; } @@ -891,9 +893,9 @@ static int handle_one_tree_block(struct reloc_control *rc, * Also, this will add the nodes to backref cache for next run. */ static int finish_upper_links(struct backref_cache *cache, - struct backref_node *start, - struct list_head *useless_node) + struct backref_node *start) { + struct list_head *useless_node = &cache->useless_node; struct backref_edge *edge; LIST_HEAD(pending_edge); @@ -992,10 +994,10 @@ static int finish_upper_links(struct backref_cache *cache, * Return true if @node is in the @useless_nodes list. */ static bool handle_useless_nodes(struct reloc_control *rc, - struct list_head *useless_nodes, struct backref_node *node) { struct backref_cache *cache = &rc->backref_cache; + struct list_head *useless_nodes = &cache->useless_node; bool ret = false; while (!list_empty(useless_nodes)) { @@ -1080,11 +1082,12 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, struct backref_node *node = NULL; struct backref_edge *edge; struct rb_node *rb_node; - LIST_HEAD(list); /* Pending edge list, upper node needs to be checked */ - LIST_HEAD(useless); int ret; int err = 0; + ASSERT(list_empty(&cache->useless_node) && + list_empty(&cache->pending_edge)); + iter = btrfs_backref_iter_alloc(rc->extent_root->fs_info, GFP_NOFS); if (!iter) return ERR_PTR(-ENOMEM); @@ -1106,15 +1109,15 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, /* Breadth-first search to build backref cache */ while (1) { - ret = handle_one_tree_block(rc, &useless, &list, path, iter, - node_key, cur); + ret = handle_one_tree_block(rc, path, iter, node_key, cur); if (ret < 0) { err = ret; goto out; } /* the pending list isn't empty, take the first block to process */ - if (!list_empty(&list)) { - edge = list_entry(list.next, struct backref_edge, list[UPPER]); + if (!list_empty(&cache->pending_edge)) { + edge = list_entry(cache->pending_edge.next, + struct backref_edge, list[UPPER]); list_del_init(&edge->list[UPPER]); cur = edge->node[UPPER]; } else { @@ -1136,26 +1139,26 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, } /* Finish the upper linkage of newly added edges/nodes */ - ret = finish_upper_links(cache, node, &useless); + ret = finish_upper_links(cache, node); if (ret < 0) { err = ret; goto out; } - if (handle_useless_nodes(rc, &useless, node)) + if (handle_useless_nodes(rc, node)) node = NULL; out: btrfs_backref_iter_free(iter); btrfs_free_path(path); if (err) { - while (!list_empty(&useless)) { - lower = list_entry(useless.next, + while (!list_empty(&cache->useless_node)) { + lower = list_first_entry(&cache->useless_node, struct backref_node, list); list_del_init(&lower->list); } - while (!list_empty(&list)) { - edge = list_first_entry(&list, struct backref_edge, - list[UPPER]); + while (!list_empty(&cache->pending_edge)) { + edge = list_first_entry(&cache->pending_edge, + struct backref_edge, list[UPPER]); list_del(&edge->list[UPPER]); list_del(&edge->list[LOWER]); lower = edge->node[LOWER]; @@ -1168,20 +1171,21 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, */ if (list_empty(&lower->upper) && RB_EMPTY_NODE(&lower->rb_node)) - list_add(&lower->list, &useless); + list_add(&lower->list, &cache->useless_node); if (!RB_EMPTY_NODE(&upper->rb_node)) continue; /* Add this guy's upper edges to the list to process */ list_for_each_entry(edge, &upper->upper, list[LOWER]) - list_add_tail(&edge->list[UPPER], &list); + list_add_tail(&edge->list[UPPER], + &cache->pending_edge); if (list_empty(&upper->upper)) - list_add(&upper->list, &useless); + list_add(&upper->list, &cache->useless_node); } - while (!list_empty(&useless)) { - lower = list_entry(useless.next, + while (!list_empty(&cache->useless_node)) { + lower = list_entry(cache->useless_node.next, struct backref_node, list); list_del_init(&lower->list); if (lower == node) @@ -1190,9 +1194,13 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, } free_backref_node(cache, node); + ASSERT(list_empty(&cache->useless_node) && + list_empty(&cache->pending_edge)); return ERR_PTR(err); } ASSERT(!node || !node->detached); + ASSERT(list_empty(&cache->useless_node) && + list_empty(&cache->pending_edge)); return node; } From patchwork Tue Mar 3 07:13:55 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 11417287 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id C3B3214BC for ; Tue, 3 Mar 2020 07:15:17 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id AC2F92146E for ; Tue, 3 Mar 2020 07:15:17 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727563AbgCCHPQ (ORCPT ); Tue, 3 Mar 2020 02:15:16 -0500 Received: from mx2.suse.de ([195.135.220.15]:56788 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726846AbgCCHPQ (ORCPT ); Tue, 3 Mar 2020 02:15:16 -0500 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id E5D39ADC9 for ; Tue, 3 Mar 2020 07:15:13 +0000 (UTC) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH 05/19] btrfs: relocation: Add backref_cache::fs_info member Date: Tue, 3 Mar 2020 15:13:55 +0800 Message-Id: <20200303071409.57982-6-wqu@suse.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20200303071409.57982-1-wqu@suse.com> References: <20200303071409.57982-1-wqu@suse.com> MIME-Version: 1.0 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org Add this member so that we can grab fs_info without the help from reloc_control. Signed-off-by: Qu Wenruo --- fs/btrfs/backref.h | 2 ++ fs/btrfs/relocation.c | 18 +++++++++--------- 2 files changed, 11 insertions(+), 9 deletions(-) diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h index 4ad1193c78e0..e1438425cf59 100644 --- a/fs/btrfs/backref.h +++ b/fs/btrfs/backref.h @@ -286,6 +286,8 @@ struct backref_cache { /* The list of useless backref nodes during backref cache build */ struct list_head useless_node; + + struct btrfs_fs_info *fs_info; }; #endif diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c index 413a83d1d9f1..0fb9ceb2665e 100644 --- a/fs/btrfs/relocation.c +++ b/fs/btrfs/relocation.c @@ -185,10 +185,12 @@ static void mapping_tree_init(struct mapping_tree *tree) spin_lock_init(&tree->lock); } -static void backref_cache_init(struct backref_cache *cache, int is_reloc) +static void backref_cache_init(struct btrfs_fs_info *fs_info, + struct backref_cache *cache, int is_reloc) { int i; cache->rb_root = RB_ROOT; + cache->fs_info = fs_info; for (i = 0; i < BTRFS_MAX_LEVEL; i++) INIT_LIST_HEAD(&cache->pending[i]); INIT_LIST_HEAD(&cache->changed); @@ -579,14 +581,13 @@ static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info, return btrfs_get_fs_root(fs_info, &key, false); } -static int handle_one_tree_backref(struct reloc_control *rc, +static int handle_one_tree_backref(struct backref_cache *cache, struct btrfs_path *path, struct btrfs_key *ref_key, struct btrfs_key *tree_key, struct backref_node *cur) { - struct btrfs_fs_info *fs_info = rc->extent_root->fs_info; - struct backref_cache *cache = &rc->backref_cache; + struct btrfs_fs_info *fs_info = cache->fs_info; struct list_head *useless_node = &cache->useless_node; struct list_head *pending_edge = &cache->pending_edge; struct backref_node *upper; @@ -777,13 +778,12 @@ static int handle_one_tree_backref(struct reloc_control *rc, return ret; } -static int handle_one_tree_block(struct reloc_control *rc, +static int handle_one_tree_block(struct backref_cache *cache, struct btrfs_path *path, struct btrfs_backref_iter *iter, struct btrfs_key *node_key, struct backref_node *cur) { - struct backref_cache *cache = &rc->backref_cache; struct backref_edge *edge; struct backref_node *exist; int ret; @@ -867,7 +867,7 @@ static int handle_one_tree_block(struct reloc_control *rc, continue; } - ret = handle_one_tree_backref(rc, path, &key, node_key, cur); + ret = handle_one_tree_backref(cache, path, &key, node_key, cur); if (ret < 0) goto out; } @@ -1109,7 +1109,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, /* Breadth-first search to build backref cache */ while (1) { - ret = handle_one_tree_block(rc, path, iter, node_key, cur); + ret = handle_one_tree_block(cache, path, iter, node_key, cur); if (ret < 0) { err = ret; goto out; @@ -4307,7 +4307,7 @@ static struct reloc_control *alloc_reloc_control(struct btrfs_fs_info *fs_info) INIT_LIST_HEAD(&rc->reloc_roots); INIT_LIST_HEAD(&rc->dirty_subvol_roots); - backref_cache_init(&rc->backref_cache, 1); + backref_cache_init(fs_info, &rc->backref_cache, 1); mapping_tree_init(&rc->reloc_root_tree); extent_io_tree_init(fs_info, &rc->processed_blocks, IO_TREE_RELOC_BLOCKS, NULL); From patchwork Tue Mar 3 07:13:56 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 11417289 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 9567214BC for ; Tue, 3 Mar 2020 07:15:18 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 73B022146E for ; Tue, 3 Mar 2020 07:15:18 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727571AbgCCHPS (ORCPT ); Tue, 3 Mar 2020 02:15:18 -0500 Received: from mx2.suse.de ([195.135.220.15]:56794 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727507AbgCCHPR (ORCPT ); Tue, 3 Mar 2020 02:15:17 -0500 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id BD2D8AC53 for ; Tue, 3 Mar 2020 07:15:15 +0000 (UTC) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH 06/19] btrfs: Move backref_cache_init() to backref.c Date: Tue, 3 Mar 2020 15:13:56 +0800 Message-Id: <20200303071409.57982-7-wqu@suse.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20200303071409.57982-1-wqu@suse.com> References: <20200303071409.57982-1-wqu@suse.com> MIME-Version: 1.0 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org Signed-off-by: Qu Wenruo --- fs/btrfs/backref.c | 16 ++++++++++++++++ fs/btrfs/backref.h | 2 ++ fs/btrfs/relocation.c | 16 ---------------- 3 files changed, 18 insertions(+), 16 deletions(-) diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index 01674be3beaa..8fc1d520695e 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -2444,3 +2444,19 @@ int btrfs_backref_iter_next(struct btrfs_backref_iter *iter) path->slots[0]); return 0; } + +void backref_cache_init(struct btrfs_fs_info *fs_info, + struct backref_cache *cache, int is_reloc) +{ + int i; + cache->rb_root = RB_ROOT; + cache->fs_info = fs_info; + for (i = 0; i < BTRFS_MAX_LEVEL; i++) + INIT_LIST_HEAD(&cache->pending[i]); + INIT_LIST_HEAD(&cache->changed); + INIT_LIST_HEAD(&cache->detached); + INIT_LIST_HEAD(&cache->leaves); + cache->is_reloc = is_reloc; + INIT_LIST_HEAD(&cache->pending_edge); + INIT_LIST_HEAD(&cache->useless_node); +} diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h index e1438425cf59..65e886fb2008 100644 --- a/fs/btrfs/backref.h +++ b/fs/btrfs/backref.h @@ -290,4 +290,6 @@ struct backref_cache { struct btrfs_fs_info *fs_info; }; +void backref_cache_init(struct btrfs_fs_info *fs_info, + struct backref_cache *cache, int is_reloc); #endif diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c index 0fb9ceb2665e..4ec2946f95ae 100644 --- a/fs/btrfs/relocation.c +++ b/fs/btrfs/relocation.c @@ -185,22 +185,6 @@ static void mapping_tree_init(struct mapping_tree *tree) spin_lock_init(&tree->lock); } -static void backref_cache_init(struct btrfs_fs_info *fs_info, - struct backref_cache *cache, int is_reloc) -{ - int i; - cache->rb_root = RB_ROOT; - cache->fs_info = fs_info; - for (i = 0; i < BTRFS_MAX_LEVEL; i++) - INIT_LIST_HEAD(&cache->pending[i]); - INIT_LIST_HEAD(&cache->changed); - INIT_LIST_HEAD(&cache->detached); - INIT_LIST_HEAD(&cache->leaves); - cache->is_reloc = is_reloc; - INIT_LIST_HEAD(&cache->pending_edge); - INIT_LIST_HEAD(&cache->useless_node); -} - static void backref_cache_cleanup(struct backref_cache *cache) { struct backref_node *node; From patchwork Tue Mar 3 07:13:57 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 11417291 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 9D5D3924 for ; Tue, 3 Mar 2020 07:15:20 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 7C59A20CC7 for ; Tue, 3 Mar 2020 07:15:20 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727594AbgCCHPT (ORCPT ); Tue, 3 Mar 2020 02:15:19 -0500 Received: from mx2.suse.de ([195.135.220.15]:56808 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727507AbgCCHPT (ORCPT ); Tue, 3 Mar 2020 02:15:19 -0500 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 64D4AB016 for ; Tue, 3 Mar 2020 07:15:17 +0000 (UTC) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH 07/19] btrfs: Move alloc_backref_node() to backref.c Date: Tue, 3 Mar 2020 15:13:57 +0800 Message-Id: <20200303071409.57982-8-wqu@suse.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20200303071409.57982-1-wqu@suse.com> References: <20200303071409.57982-1-wqu@suse.com> MIME-Version: 1.0 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org Signed-off-by: Qu Wenruo --- fs/btrfs/backref.c | 20 ++++++++++++++++++++ fs/btrfs/backref.h | 2 ++ fs/btrfs/relocation.c | 20 -------------------- 3 files changed, 22 insertions(+), 20 deletions(-) diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index 8fc1d520695e..b6183cb7c60b 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -2460,3 +2460,23 @@ void backref_cache_init(struct btrfs_fs_info *fs_info, INIT_LIST_HEAD(&cache->pending_edge); INIT_LIST_HEAD(&cache->useless_node); } + +struct backref_node *alloc_backref_node(struct backref_cache *cache, + u64 bytenr, int level) +{ + struct backref_node *node; + + ASSERT(level >= 0 && level < BTRFS_MAX_LEVEL); + node = kzalloc(sizeof(*node), GFP_NOFS); + if (node) { + INIT_LIST_HEAD(&node->list); + INIT_LIST_HEAD(&node->upper); + INIT_LIST_HEAD(&node->lower); + RB_CLEAR_NODE(&node->rb_node); + cache->nr_nodes++; + + node->level = level; + node->bytenr = bytenr; + } + return node; +} diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h index 65e886fb2008..b7aad5f116ae 100644 --- a/fs/btrfs/backref.h +++ b/fs/btrfs/backref.h @@ -292,4 +292,6 @@ struct backref_cache { void backref_cache_init(struct btrfs_fs_info *fs_info, struct backref_cache *cache, int is_reloc); +struct backref_node *alloc_backref_node(struct backref_cache *cache, + u64 bytenr, int level); #endif diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c index 4ec2946f95ae..f97ff88dba21 100644 --- a/fs/btrfs/relocation.c +++ b/fs/btrfs/relocation.c @@ -215,26 +215,6 @@ static void backref_cache_cleanup(struct backref_cache *cache) ASSERT(!cache->nr_edges); } -static struct backref_node *alloc_backref_node(struct backref_cache *cache, - u64 bytenr, int level) -{ - struct backref_node *node; - - ASSERT(level >= 0 && level < BTRFS_MAX_LEVEL); - node = kzalloc(sizeof(*node), GFP_NOFS); - if (node) { - INIT_LIST_HEAD(&node->list); - INIT_LIST_HEAD(&node->upper); - INIT_LIST_HEAD(&node->lower); - RB_CLEAR_NODE(&node->rb_node); - cache->nr_nodes++; - - node->level = level; - node->bytenr = bytenr; - } - return node; -} - static void free_backref_node(struct backref_cache *cache, struct backref_node *node) { From patchwork Tue Mar 3 07:13:58 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 11417293 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id EE89214BC for ; Tue, 3 Mar 2020 07:15:23 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id CDFF520CC7 for ; Tue, 3 Mar 2020 07:15:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727604AbgCCHPW (ORCPT ); Tue, 3 Mar 2020 02:15:22 -0500 Received: from mx2.suse.de ([195.135.220.15]:56816 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727573AbgCCHPW (ORCPT ); Tue, 3 Mar 2020 02:15:22 -0500 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 125E5AC53 for ; Tue, 3 Mar 2020 07:15:21 +0000 (UTC) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH 08/19] btrfs: Move alloc_backref_edge() to backref.c Date: Tue, 3 Mar 2020 15:13:58 +0800 Message-Id: <20200303071409.57982-9-wqu@suse.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20200303071409.57982-1-wqu@suse.com> References: <20200303071409.57982-1-wqu@suse.com> MIME-Version: 1.0 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org Signed-off-by: Qu Wenruo --- fs/btrfs/backref.c | 10 ++++++++++ fs/btrfs/backref.h | 1 + fs/btrfs/relocation.c | 10 ---------- 3 files changed, 11 insertions(+), 10 deletions(-) diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index b6183cb7c60b..7511ce8447e8 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -2480,3 +2480,13 @@ struct backref_node *alloc_backref_node(struct backref_cache *cache, } return node; } + +struct backref_edge *alloc_backref_edge(struct backref_cache *cache) +{ + struct backref_edge *edge; + + edge = kzalloc(sizeof(*edge), GFP_NOFS); + if (edge) + cache->nr_edges++; + return edge; +} diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h index b7aad5f116ae..04efc9d44bb8 100644 --- a/fs/btrfs/backref.h +++ b/fs/btrfs/backref.h @@ -294,4 +294,5 @@ void backref_cache_init(struct btrfs_fs_info *fs_info, struct backref_cache *cache, int is_reloc); struct backref_node *alloc_backref_node(struct backref_cache *cache, u64 bytenr, int level); +struct backref_edge *alloc_backref_edge(struct backref_cache *cache); #endif diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c index f97ff88dba21..1f4fccd973d1 100644 --- a/fs/btrfs/relocation.c +++ b/fs/btrfs/relocation.c @@ -225,16 +225,6 @@ static void free_backref_node(struct backref_cache *cache, } } -static struct backref_edge *alloc_backref_edge(struct backref_cache *cache) -{ - struct backref_edge *edge; - - edge = kzalloc(sizeof(*edge), GFP_NOFS); - if (edge) - cache->nr_edges++; - return edge; -} - #define LINK_LOWER (1 << 0) #define LINK_UPPER (1 << 1) static inline void link_backref_edge(struct backref_edge *edge, From patchwork Tue Mar 3 07:13:59 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 11417295 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 00F2C14BC for ; Tue, 3 Mar 2020 07:15:26 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id D488520CC7 for ; Tue, 3 Mar 2020 07:15:25 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727600AbgCCHPZ (ORCPT ); Tue, 3 Mar 2020 02:15:25 -0500 Received: from mx2.suse.de ([195.135.220.15]:56822 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727573AbgCCHPY (ORCPT ); Tue, 3 Mar 2020 02:15:24 -0500 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 83C3BAC53 for ; Tue, 3 Mar 2020 07:15:23 +0000 (UTC) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH 09/19] btrfs: Move link_backref_edge() to backref.c Date: Tue, 3 Mar 2020 15:13:59 +0800 Message-Id: <20200303071409.57982-10-wqu@suse.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20200303071409.57982-1-wqu@suse.com> References: <20200303071409.57982-1-wqu@suse.com> MIME-Version: 1.0 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org Signed-off-by: Qu Wenruo --- fs/btrfs/backref.h | 16 ++++++++++++++++ fs/btrfs/relocation.c | 16 ---------------- 2 files changed, 16 insertions(+), 16 deletions(-) diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h index 04efc9d44bb8..431c8a15c5f9 100644 --- a/fs/btrfs/backref.h +++ b/fs/btrfs/backref.h @@ -295,4 +295,20 @@ void backref_cache_init(struct btrfs_fs_info *fs_info, struct backref_node *alloc_backref_node(struct backref_cache *cache, u64 bytenr, int level); struct backref_edge *alloc_backref_edge(struct backref_cache *cache); + +#define LINK_LOWER (1 << 0) +#define LINK_UPPER (1 << 1) +static inline void link_backref_edge(struct backref_edge *edge, + struct backref_node *lower, + struct backref_node *upper, + int link_which) +{ + ASSERT(upper && lower && upper->level == lower->level + 1); + edge->node[LOWER] = lower; + edge->node[UPPER] = upper; + if (link_which & LINK_LOWER) + list_add_tail(&edge->list[LOWER], &lower->upper); + if (link_which & LINK_UPPER) + list_add_tail(&edge->list[UPPER], &upper->lower); +} #endif diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c index 1f4fccd973d1..dfcedd7824bc 100644 --- a/fs/btrfs/relocation.c +++ b/fs/btrfs/relocation.c @@ -225,22 +225,6 @@ static void free_backref_node(struct backref_cache *cache, } } -#define LINK_LOWER (1 << 0) -#define LINK_UPPER (1 << 1) -static inline void link_backref_edge(struct backref_edge *edge, - struct backref_node *lower, - struct backref_node *upper, - int link_which) -{ - ASSERT(upper && lower && upper->level == lower->level + 1); - edge->node[LOWER] = lower; - edge->node[UPPER] = upper; - if (link_which & LINK_LOWER) - list_add_tail(&edge->list[LOWER], &lower->upper); - if (link_which & LINK_UPPER) - list_add_tail(&edge->list[UPPER], &upper->lower); -} - static void free_backref_edge(struct backref_cache *cache, struct backref_edge *edge) { From patchwork Tue Mar 3 07:14:00 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 11417297 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 89B5E924 for ; Tue, 3 Mar 2020 07:15:30 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 72C76215A4 for ; Tue, 3 Mar 2020 07:15:30 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727608AbgCCHP3 (ORCPT ); Tue, 3 Mar 2020 02:15:29 -0500 Received: from mx2.suse.de ([195.135.220.15]:56838 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727522AbgCCHP3 (ORCPT ); Tue, 3 Mar 2020 02:15:29 -0500 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id DE463B016 for ; Tue, 3 Mar 2020 07:15:27 +0000 (UTC) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH 10/19] btrfs: Move free_backref_node() and free_backref_edge() to backref.h Date: Tue, 3 Mar 2020 15:14:00 +0800 Message-Id: <20200303071409.57982-11-wqu@suse.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20200303071409.57982-1-wqu@suse.com> References: <20200303071409.57982-1-wqu@suse.com> MIME-Version: 1.0 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org Signed-off-by: Qu Wenruo --- fs/btrfs/backref.h | 20 ++++++++++++++++++++ fs/btrfs/relocation.c | 19 ------------------- 2 files changed, 20 insertions(+), 19 deletions(-) diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h index 431c8a15c5f9..d8492846a961 100644 --- a/fs/btrfs/backref.h +++ b/fs/btrfs/backref.h @@ -8,6 +8,7 @@ #include #include "ulist.h" +#include "disk-io.h" #include "extent_io.h" struct inode_fs_paths { @@ -311,4 +312,23 @@ static inline void link_backref_edge(struct backref_edge *edge, if (link_which & LINK_UPPER) list_add_tail(&edge->list[UPPER], &upper->lower); } +static inline void free_backref_node(struct backref_cache *cache, + struct backref_node *node) +{ + if (node) { + cache->nr_nodes--; + btrfs_put_root(node->root); + kfree(node); + } +} + +static inline void free_backref_edge(struct backref_cache *cache, + struct backref_edge *edge) +{ + if (edge) { + cache->nr_edges--; + kfree(edge); + } +} + #endif diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c index dfcedd7824bc..43b1bab2f51f 100644 --- a/fs/btrfs/relocation.c +++ b/fs/btrfs/relocation.c @@ -215,25 +215,6 @@ static void backref_cache_cleanup(struct backref_cache *cache) ASSERT(!cache->nr_edges); } -static void free_backref_node(struct backref_cache *cache, - struct backref_node *node) -{ - if (node) { - cache->nr_nodes--; - btrfs_put_root(node->root); - kfree(node); - } -} - -static void free_backref_edge(struct backref_cache *cache, - struct backref_edge *edge) -{ - if (edge) { - cache->nr_edges--; - kfree(edge); - } -} - static void backref_tree_panic(struct rb_node *rb_node, int errno, u64 bytenr) { From patchwork Tue Mar 3 07:14:01 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 11417299 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 01CF9924 for ; Tue, 3 Mar 2020 07:15:36 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id DF31020CC7 for ; Tue, 3 Mar 2020 07:15:35 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727634AbgCCHPf (ORCPT ); Tue, 3 Mar 2020 02:15:35 -0500 Received: from mx2.suse.de ([195.135.220.15]:56864 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727522AbgCCHPe (ORCPT ); Tue, 3 Mar 2020 02:15:34 -0500 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 9E000AC53 for ; Tue, 3 Mar 2020 07:15:32 +0000 (UTC) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH 11/19] btrfs: Move drop_backref_node() and needed facilities to backref.h Date: Tue, 3 Mar 2020 15:14:01 +0800 Message-Id: <20200303071409.57982-12-wqu@suse.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20200303071409.57982-1-wqu@suse.com> References: <20200303071409.57982-1-wqu@suse.com> MIME-Version: 1.0 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org With extra comment for drop_backref_node() as it has some similarity with remove_backref_node(), thus we need extra comment explaining the difference. Signed-off-by: Qu Wenruo --- fs/btrfs/backref.h | 37 +++++++++++++++++++++++++++++++++++++ fs/btrfs/relocation.c | 31 ------------------------------- 2 files changed, 37 insertions(+), 31 deletions(-) diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h index d8492846a961..7b8bf4e13d99 100644 --- a/fs/btrfs/backref.h +++ b/fs/btrfs/backref.h @@ -331,4 +331,41 @@ static inline void free_backref_edge(struct backref_cache *cache, } } +static inline void unlock_node_buffer(struct backref_node *node) +{ + if (node->locked) { + btrfs_tree_unlock(node->eb); + node->locked = 0; + } +} + +static inline void drop_node_buffer(struct backref_node *node) +{ + if (node->eb) { + unlock_node_buffer(node); + free_extent_buffer(node->eb); + node->eb = NULL; + } +} + +/* + * Drop the backref node from cache without cleaning up its children + * edges. + * + * This can only be called on node without parent edges. + * The children edges are still kept as is. + */ +static inline void drop_backref_node(struct backref_cache *tree, + struct backref_node *node) +{ + BUG_ON(!list_empty(&node->upper)); + + drop_node_buffer(node); + list_del(&node->list); + list_del(&node->lower); + if (!RB_EMPTY_NODE(&node->rb_node)) + rb_erase(&node->rb_node, &tree->rb_root); + free_backref_node(tree, node); +} + #endif diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c index 43b1bab2f51f..1c038428990c 100644 --- a/fs/btrfs/relocation.c +++ b/fs/btrfs/relocation.c @@ -275,37 +275,6 @@ static struct backref_node *walk_down_backref(struct backref_edge *edges[], *index = 0; return NULL; } - -static void unlock_node_buffer(struct backref_node *node) -{ - if (node->locked) { - btrfs_tree_unlock(node->eb); - node->locked = 0; - } -} - -static void drop_node_buffer(struct backref_node *node) -{ - if (node->eb) { - unlock_node_buffer(node); - free_extent_buffer(node->eb); - node->eb = NULL; - } -} - -static void drop_backref_node(struct backref_cache *tree, - struct backref_node *node) -{ - BUG_ON(!list_empty(&node->upper)); - - drop_node_buffer(node); - list_del(&node->list); - list_del(&node->lower); - if (!RB_EMPTY_NODE(&node->rb_node)) - rb_erase(&node->rb_node, &tree->rb_root); - free_backref_node(tree, node); -} - /* * remove a backref node from the backref cache */ From patchwork Tue Mar 3 07:14:02 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 11417301 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 8E6E614BC for ; Tue, 3 Mar 2020 07:15:39 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 77A9120CC7 for ; Tue, 3 Mar 2020 07:15:39 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727609AbgCCHPi (ORCPT ); Tue, 3 Mar 2020 02:15:38 -0500 Received: from mx2.suse.de ([195.135.220.15]:56880 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727522AbgCCHPi (ORCPT ); Tue, 3 Mar 2020 02:15:38 -0500 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 63A90ADC9 for ; Tue, 3 Mar 2020 07:15:36 +0000 (UTC) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH 12/19] btrfs: Rename remove_backref_node() to cleanup_backref_node() and move it to backref.c Date: Tue, 3 Mar 2020 15:14:02 +0800 Message-Id: <20200303071409.57982-13-wqu@suse.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20200303071409.57982-1-wqu@suse.com> References: <20200303071409.57982-1-wqu@suse.com> MIME-Version: 1.0 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org Also add comment explaining the cleanup progress, to differ it from drop_backref_node(). Signed-off-by: Qu Wenruo --- fs/btrfs/backref.c | 38 ++++++++++++++++++++++++++++++++ fs/btrfs/backref.h | 9 ++++++++ fs/btrfs/relocation.c | 51 ++++--------------------------------------- 3 files changed, 51 insertions(+), 47 deletions(-) diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index 7511ce8447e8..4f0e8ab1d9cf 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -2490,3 +2490,41 @@ struct backref_edge *alloc_backref_edge(struct backref_cache *cache) cache->nr_edges++; return edge; } + +void cleanup_backref_node(struct backref_cache *cache, + struct backref_node *node) +{ + struct backref_node *upper; + struct backref_edge *edge; + + if (!node) + return; + + BUG_ON(!node->lowest && !node->detached); + while (!list_empty(&node->upper)) { + edge = list_entry(node->upper.next, struct backref_edge, + list[LOWER]); + upper = edge->node[UPPER]; + list_del(&edge->list[LOWER]); + list_del(&edge->list[UPPER]); + free_backref_edge(cache, edge); + + if (RB_EMPTY_NODE(&upper->rb_node)) { + BUG_ON(!list_empty(&node->upper)); + drop_backref_node(cache, node); + node = upper; + node->lowest = 1; + continue; + } + /* + * add the node to leaf node list if no other + * child block cached. + */ + if (list_empty(&upper->lower)) { + list_add_tail(&upper->lower, &cache->leaves); + upper->lowest = 1; + } + } + + drop_backref_node(cache, node); +} diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h index 7b8bf4e13d99..1c34a8dbee2f 100644 --- a/fs/btrfs/backref.h +++ b/fs/btrfs/backref.h @@ -368,4 +368,13 @@ static inline void drop_backref_node(struct backref_cache *tree, free_backref_node(tree, node); } +/* + * Drop the backref node from cache, also cleaning up all its + * upper edges and any uncached nodes in the path. + * + * This cleanup happens bottom up, thus the node should either + * be the lowest node in the cache or detached node. + */ +void cleanup_backref_node(struct backref_cache *cache, + struct backref_node *node); #endif diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c index 1c038428990c..2050414884fb 100644 --- a/fs/btrfs/relocation.c +++ b/fs/btrfs/relocation.c @@ -161,9 +161,6 @@ struct reloc_control { #define MOVE_DATA_EXTENTS 0 #define UPDATE_DATA_PTRS 1 -static void remove_backref_node(struct backref_cache *cache, - struct backref_node *node); - static void mark_block_processed(struct reloc_control *rc, struct backref_node *node) { @@ -193,13 +190,13 @@ static void backref_cache_cleanup(struct backref_cache *cache) while (!list_empty(&cache->detached)) { node = list_entry(cache->detached.next, struct backref_node, list); - remove_backref_node(cache, node); + cleanup_backref_node(cache, node); } while (!list_empty(&cache->leaves)) { node = list_entry(cache->leaves.next, struct backref_node, lower); - remove_backref_node(cache, node); + cleanup_backref_node(cache, node); } cache->last_trans = 0; @@ -275,46 +272,6 @@ static struct backref_node *walk_down_backref(struct backref_edge *edges[], *index = 0; return NULL; } -/* - * remove a backref node from the backref cache - */ -static void remove_backref_node(struct backref_cache *cache, - struct backref_node *node) -{ - struct backref_node *upper; - struct backref_edge *edge; - - if (!node) - return; - - BUG_ON(!node->lowest && !node->detached); - while (!list_empty(&node->upper)) { - edge = list_entry(node->upper.next, struct backref_edge, - list[LOWER]); - upper = edge->node[UPPER]; - list_del(&edge->list[LOWER]); - list_del(&edge->list[UPPER]); - free_backref_edge(cache, edge); - - if (RB_EMPTY_NODE(&upper->rb_node)) { - BUG_ON(!list_empty(&node->upper)); - drop_backref_node(cache, node); - node = upper; - node->lowest = 1; - continue; - } - /* - * add the node to leaf node list if no other - * child block cached. - */ - if (list_empty(&upper->lower)) { - list_add_tail(&upper->lower, &cache->leaves); - upper->lowest = 1; - } - } - - drop_backref_node(cache, node); -} static void update_backref_node(struct backref_cache *cache, struct backref_node *node, u64 bytenr) @@ -352,7 +309,7 @@ static int update_backref_cache(struct btrfs_trans_handle *trans, while (!list_empty(&cache->detached)) { node = list_entry(cache->detached.next, struct backref_node, list); - remove_backref_node(cache, node); + cleanup_backref_node(cache, node); } while (!list_empty(&cache->changed)) { @@ -2989,7 +2946,7 @@ static int relocate_tree_block(struct btrfs_trans_handle *trans, } out: if (ret || node->level == 0 || node->cowonly) - remove_backref_node(&rc->backref_cache, node); + cleanup_backref_node(&rc->backref_cache, node); return ret; } From patchwork Tue Mar 3 07:14:03 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 11417303 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id E411714BC for ; Tue, 3 Mar 2020 07:15:40 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id CC76C20CC7 for ; Tue, 3 Mar 2020 07:15:40 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727637AbgCCHPk (ORCPT ); Tue, 3 Mar 2020 02:15:40 -0500 Received: from mx2.suse.de ([195.135.220.15]:56892 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727635AbgCCHPj (ORCPT ); Tue, 3 Mar 2020 02:15:39 -0500 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 33484B016 for ; Tue, 3 Mar 2020 07:15:38 +0000 (UTC) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH 13/19] btrfs: Move backref_cache_cleanup() to backref.c Date: Tue, 3 Mar 2020 15:14:03 +0800 Message-Id: <20200303071409.57982-14-wqu@suse.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20200303071409.57982-1-wqu@suse.com> References: <20200303071409.57982-1-wqu@suse.com> MIME-Version: 1.0 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org Signed-off-by: Qu Wenruo --- fs/btrfs/backref.c | 30 ++++++++++++++++++++++++++++++ fs/btrfs/backref.h | 1 + fs/btrfs/relocation.c | 30 ------------------------------ 3 files changed, 31 insertions(+), 30 deletions(-) diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index 4f0e8ab1d9cf..02455b3bbc35 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -2528,3 +2528,33 @@ void cleanup_backref_node(struct backref_cache *cache, drop_backref_node(cache, node); } + +void backref_cache_cleanup(struct backref_cache *cache) +{ + struct backref_node *node; + int i; + + while (!list_empty(&cache->detached)) { + node = list_entry(cache->detached.next, + struct backref_node, list); + cleanup_backref_node(cache, node); + } + + while (!list_empty(&cache->leaves)) { + node = list_entry(cache->leaves.next, + struct backref_node, lower); + cleanup_backref_node(cache, node); + } + + cache->last_trans = 0; + + for (i = 0; i < BTRFS_MAX_LEVEL; i++) + ASSERT(list_empty(&cache->pending[i])); + ASSERT(list_empty(&cache->pending_edge)); + ASSERT(list_empty(&cache->useless_node)); + ASSERT(list_empty(&cache->changed)); + ASSERT(list_empty(&cache->detached)); + ASSERT(RB_EMPTY_ROOT(&cache->rb_root)); + ASSERT(!cache->nr_nodes); + ASSERT(!cache->nr_edges); +} diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h index 1c34a8dbee2f..2fb854b1d5f0 100644 --- a/fs/btrfs/backref.h +++ b/fs/btrfs/backref.h @@ -377,4 +377,5 @@ static inline void drop_backref_node(struct backref_cache *tree, */ void cleanup_backref_node(struct backref_cache *cache, struct backref_node *node); +void backref_cache_cleanup(struct backref_cache *cache); #endif diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c index 2050414884fb..71df172b70bb 100644 --- a/fs/btrfs/relocation.c +++ b/fs/btrfs/relocation.c @@ -182,36 +182,6 @@ static void mapping_tree_init(struct mapping_tree *tree) spin_lock_init(&tree->lock); } -static void backref_cache_cleanup(struct backref_cache *cache) -{ - struct backref_node *node; - int i; - - while (!list_empty(&cache->detached)) { - node = list_entry(cache->detached.next, - struct backref_node, list); - cleanup_backref_node(cache, node); - } - - while (!list_empty(&cache->leaves)) { - node = list_entry(cache->leaves.next, - struct backref_node, lower); - cleanup_backref_node(cache, node); - } - - cache->last_trans = 0; - - for (i = 0; i < BTRFS_MAX_LEVEL; i++) - ASSERT(list_empty(&cache->pending[i])); - ASSERT(list_empty(&cache->pending_edge)); - ASSERT(list_empty(&cache->useless_node)); - ASSERT(list_empty(&cache->changed)); - ASSERT(list_empty(&cache->detached)); - ASSERT(RB_EMPTY_ROOT(&cache->rb_root)); - ASSERT(!cache->nr_nodes); - ASSERT(!cache->nr_edges); -} - static void backref_tree_panic(struct rb_node *rb_node, int errno, u64 bytenr) { From patchwork Tue Mar 3 07:14:04 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 11417305 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 4AB9D924 for ; Tue, 3 Mar 2020 07:15:43 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 346B92146E for ; Tue, 3 Mar 2020 07:15:43 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727642AbgCCHPm (ORCPT ); Tue, 3 Mar 2020 02:15:42 -0500 Received: from mx2.suse.de ([195.135.220.15]:56912 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727635AbgCCHPl (ORCPT ); Tue, 3 Mar 2020 02:15:41 -0500 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id D00BEAC53 for ; Tue, 3 Mar 2020 07:15:39 +0000 (UTC) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH 14/19] btrfs: Rename backref_tree_panic() to backref_cache_panic(), and move it to backref.c Date: Tue, 3 Mar 2020 15:14:04 +0800 Message-Id: <20200303071409.57982-15-wqu@suse.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20200303071409.57982-1-wqu@suse.com> References: <20200303071409.57982-1-wqu@suse.com> MIME-Version: 1.0 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org Also change the parameter, since all callers can easily grab an fs_info, there is no need for all the dancing. Signed-off-by: Qu Wenruo --- fs/btrfs/backref.h | 8 ++++++++ fs/btrfs/relocation.c | 33 +++++++++++---------------------- 2 files changed, 19 insertions(+), 22 deletions(-) diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h index 2fb854b1d5f0..4a4c9070a38b 100644 --- a/fs/btrfs/backref.h +++ b/fs/btrfs/backref.h @@ -378,4 +378,12 @@ static inline void drop_backref_node(struct backref_cache *tree, void cleanup_backref_node(struct backref_cache *cache, struct backref_node *node); void backref_cache_cleanup(struct backref_cache *cache); + +static inline void backref_cache_panic(struct btrfs_fs_info *fs_info, + u64 bytenr, int errno) +{ + btrfs_panic(fs_info, errno, + "Inconsistency in backref cache found at offset %llu", + bytenr); +} #endif diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c index 71df172b70bb..349e8e761e8d 100644 --- a/fs/btrfs/relocation.c +++ b/fs/btrfs/relocation.c @@ -182,19 +182,6 @@ static void mapping_tree_init(struct mapping_tree *tree) spin_lock_init(&tree->lock); } -static void backref_tree_panic(struct rb_node *rb_node, int errno, u64 bytenr) -{ - - struct btrfs_fs_info *fs_info = NULL; - struct backref_node *bnode = rb_entry(rb_node, struct backref_node, - rb_node); - if (bnode->root) - fs_info = bnode->root->fs_info; - btrfs_panic(fs_info, errno, - "Inconsistency in backref cache found at offset %llu", - bytenr); -} - /* * walk up backref nodes until reach node presents tree root */ @@ -251,7 +238,7 @@ static void update_backref_node(struct backref_cache *cache, node->bytenr = bytenr; rb_node = simple_insert(&cache->rb_root, node->bytenr, &node->rb_node); if (rb_node) - backref_tree_panic(rb_node, -EEXIST, bytenr); + backref_cache_panic(cache->fs_info, bytenr, -EEXIST); } /* @@ -778,8 +765,8 @@ static int finish_upper_links(struct backref_cache *cache, rb_node = simple_insert(&cache->rb_root, upper->bytenr, &upper->rb_node); if (rb_node) { - backref_tree_panic(rb_node, -EEXIST, - upper->bytenr); + backref_cache_panic(cache->fs_info, + upper->bytenr, -EEXIST); return -EUCLEAN; } } @@ -949,7 +936,8 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, rb_node = simple_insert(&cache->rb_root, node->bytenr, &node->rb_node); if (rb_node) - backref_tree_panic(rb_node, -EEXIST, node->bytenr); + backref_cache_panic(cache->fs_info, node->bytenr, + -EEXIST); list_add_tail(&node->lower, &cache->leaves); } @@ -1087,7 +1075,7 @@ static int clone_backref_node(struct btrfs_trans_handle *trans, 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); + backref_cache_panic(trans->fs_info, new_node->bytenr, -EEXIST); if (!new_node->lowest) { list_for_each_entry(new_edge, &new_node->lower, list[UPPER]) { @@ -1199,7 +1187,7 @@ static int __update_reloc_root(struct btrfs_root *root, u64 new_bytenr) node->bytenr, &node->rb_node); spin_unlock(&rc->reloc_root_tree.lock); if (rb_node) - backref_tree_panic(rb_node, -EEXIST, node->bytenr); + backref_cache_panic(fs_info, node->bytenr, -EEXIST); return 0; } @@ -3285,7 +3273,8 @@ static int add_tree_block(struct reloc_control *rc, rb_node = simple_insert(blocks, block->bytenr, &block->rb_node); if (rb_node) - backref_tree_panic(rb_node, -EEXIST, block->bytenr); + backref_cache_panic(rc->extent_root->fs_info, block->bytenr, + -EEXIST); return 0; } @@ -3583,8 +3572,8 @@ static int find_data_references(struct reloc_control *rc, rb_node = simple_insert(blocks, block->bytenr, &block->rb_node); if (rb_node) - backref_tree_panic(rb_node, -EEXIST, - block->bytenr); + backref_cache_panic(fs_info, block->bytenr, + -EEXIST); } if (counted) added = 1; From patchwork Tue Mar 3 07:14:05 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 11417307 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 15A1514BC for ; Tue, 3 Mar 2020 07:15:47 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 0002F2146E for ; Tue, 3 Mar 2020 07:15:46 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727653AbgCCHPo (ORCPT ); Tue, 3 Mar 2020 02:15:44 -0500 Received: from mx2.suse.de ([195.135.220.15]:56926 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727635AbgCCHPn (ORCPT ); Tue, 3 Mar 2020 02:15:43 -0500 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 0BF3CB016 for ; Tue, 3 Mar 2020 07:15:42 +0000 (UTC) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH 15/19] btrfs: Rename should_ignore_root() to should_ignore_reloc_root() and export it Date: Tue, 3 Mar 2020 15:14:05 +0800 Message-Id: <20200303071409.57982-16-wqu@suse.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20200303071409.57982-1-wqu@suse.com> References: <20200303071409.57982-1-wqu@suse.com> MIME-Version: 1.0 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org This function is mostly single purpose to relocation backref cache, but since we're moving the main part of backref cache to backref.c, we need to export such function. And to avoid confusing, rename the function to should_ignore_reloc_root() make the name a little more clear. Signed-off-by: Qu Wenruo --- fs/btrfs/ctree.h | 1 + fs/btrfs/relocation.c | 9 +++++---- 2 files changed, 6 insertions(+), 4 deletions(-) diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h index b57bb3e5f1f2..e45aad90b45e 100644 --- a/fs/btrfs/ctree.h +++ b/fs/btrfs/ctree.h @@ -3383,6 +3383,7 @@ int btrfs_reloc_post_snapshot(struct btrfs_trans_handle *trans, struct btrfs_pending_snapshot *pending); struct btrfs_root *find_reloc_root(struct btrfs_fs_info *fs_info, u64 bytenr); +int should_ignore_reloc_root(struct btrfs_root *root); /* scrub.c */ int btrfs_scrub_dev(struct btrfs_fs_info *fs_info, u64 devid, u64 start, diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c index 349e8e761e8d..2230ea8a3698 100644 --- a/fs/btrfs/relocation.c +++ b/fs/btrfs/relocation.c @@ -312,7 +312,7 @@ static bool reloc_root_is_dead(struct btrfs_root *root) * * Reloc tree after swap is considered dead, thus not considered as valid. * This is enough for most callers, as they don't distinguish dead reloc root - * from no reloc root. But should_ignore_root() below is a special case. + * from no reloc root. But should_ignore_reloc_root() below is a special case. */ static bool have_reloc_root(struct btrfs_root *root) { @@ -323,7 +323,7 @@ static bool have_reloc_root(struct btrfs_root *root) return true; } -static int should_ignore_root(struct btrfs_root *root) +int should_ignore_reloc_root(struct btrfs_root *root) { struct btrfs_root *reloc_root; @@ -349,6 +349,7 @@ static int should_ignore_root(struct btrfs_root *root) */ return 1; } + /* * find reloc tree by address of tree root */ @@ -465,7 +466,7 @@ static int handle_one_tree_backref(struct backref_cache *cache, /* tree root */ ASSERT(btrfs_root_bytenr(&root->root_item) == cur->bytenr); - if (should_ignore_root(root)) { + if (should_ignore_reloc_root(root)) { btrfs_put_root(root); list_add(&cur->list, useless_node); } else { @@ -506,7 +507,7 @@ static int handle_one_tree_backref(struct backref_cache *cache, if (!path->nodes[level]) { ASSERT(btrfs_root_bytenr(&root->root_item) == lower->bytenr); - if (should_ignore_root(root)) { + if (should_ignore_reloc_root(root)) { btrfs_put_root(root); list_add(&lower->list, useless_node); } else { From patchwork Tue Mar 3 07:14:06 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 11417309 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id C03EF14BC for ; Tue, 3 Mar 2020 07:15:48 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id A93AD206D5 for ; Tue, 3 Mar 2020 07:15:48 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727667AbgCCHPr (ORCPT ); Tue, 3 Mar 2020 02:15:47 -0500 Received: from mx2.suse.de ([195.135.220.15]:56948 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727652AbgCCHPq (ORCPT ); Tue, 3 Mar 2020 02:15:46 -0500 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 42EABAC53 for ; Tue, 3 Mar 2020 07:15:45 +0000 (UTC) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH 16/19] btrfs: relocation: Open-code read_fs_root() for handle_one_tree_backref() Date: Tue, 3 Mar 2020 15:14:06 +0800 Message-Id: <20200303071409.57982-17-wqu@suse.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20200303071409.57982-1-wqu@suse.com> References: <20200303071409.57982-1-wqu@suse.com> MIME-Version: 1.0 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org The backref code is going to be moved to backref.c, and read_fs_root() is just a simple wrapper, open-code it to prepare to the incoming code move. Signed-off-by: Qu Wenruo --- fs/btrfs/relocation.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c index 2230ea8a3698..441d2b28d8e7 100644 --- a/fs/btrfs/relocation.c +++ b/fs/btrfs/relocation.c @@ -397,6 +397,7 @@ static int handle_one_tree_backref(struct backref_cache *cache, struct backref_node *lower; struct backref_edge *edge; struct extent_buffer *eb; + struct btrfs_key root_key; struct btrfs_root *root; struct rb_node *rb_node; bool need_check = true; @@ -456,7 +457,10 @@ static int handle_one_tree_backref(struct backref_cache *cache, * ref_key.type == BTRFS_TREE_BLOCK_REF_KEY, ref_key->offset means the * root objectid. We need to search the tree to get its parent bytenr. */ - root = read_fs_root(fs_info, ref_key->offset); + root_key.objectid = ref_key->offset; + root_key.type = BTRFS_ROOT_ITEM_KEY; + root_key.offset = (u64)-1; + root = btrfs_get_fs_root(fs_info, &root_key, false); if (IS_ERR(root)) return PTR_ERR(root); if (!test_bit(BTRFS_ROOT_REF_COWS, &root->state)) From patchwork Tue Mar 3 07:14:07 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 11417313 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id BBB2C924 for ; Tue, 3 Mar 2020 07:15:53 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 8780C206D5 for ; Tue, 3 Mar 2020 07:15:53 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727675AbgCCHPw (ORCPT ); Tue, 3 Mar 2020 02:15:52 -0500 Received: from mx2.suse.de ([195.135.220.15]:57018 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727588AbgCCHPw (ORCPT ); Tue, 3 Mar 2020 02:15:52 -0500 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 7B4C4ADC9 for ; Tue, 3 Mar 2020 07:15:48 +0000 (UTC) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH 17/19] btrfs: Rename handle_one_tree_block() to backref_cache_add_one_tree_block() and move it to backref.c Date: Tue, 3 Mar 2020 15:14:07 +0800 Message-Id: <20200303071409.57982-18-wqu@suse.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20200303071409.57982-1-wqu@suse.com> References: <20200303071409.57982-1-wqu@suse.com> MIME-Version: 1.0 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org This function is the major part of backref cache build process, move it to backref.c so we can reuse it later. Signed-off-by: Qu Wenruo --- fs/btrfs/backref.c | 305 +++++++++++++++++++++++++++++++++++++++++ fs/btrfs/backref.h | 6 + fs/btrfs/relocation.c | 307 +----------------------------------------- 3 files changed, 313 insertions(+), 305 deletions(-) diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index 02455b3bbc35..e1a271c1e9f3 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -13,6 +13,7 @@ #include "transaction.h" #include "delayed-ref.h" #include "locking.h" +#include "misc.h" /* Just an arbitrary number so we can be sure this happened */ #define BACKREF_FOUND_SHARED 6 @@ -2558,3 +2559,307 @@ void backref_cache_cleanup(struct backref_cache *cache) ASSERT(!cache->nr_nodes); ASSERT(!cache->nr_edges); } + +static int handle_one_tree_backref(struct backref_cache *cache, + struct btrfs_path *path, + struct btrfs_key *ref_key, + struct btrfs_key *tree_key, + struct backref_node *cur) +{ + struct btrfs_fs_info *fs_info = cache->fs_info; + struct list_head *useless_node = &cache->useless_node; + struct list_head *pending_edge = &cache->pending_edge; + struct backref_node *upper; + struct backref_node *lower; + struct backref_edge *edge; + struct extent_buffer *eb; + struct btrfs_key root_key; + struct btrfs_root *root; + struct rb_node *rb_node; + bool need_check = true; + int level; + int ret = 0; + + if (ref_key->type != BTRFS_TREE_BLOCK_REF_KEY && + ref_key->type != BTRFS_SHARED_BLOCK_REF_KEY) + return -EUCLEAN; + + /* SHARED_BLOCK_REF means key.offset is the parent bytenr */ + if (ref_key->type == BTRFS_SHARED_BLOCK_REF_KEY) { + + /* Only reloc root uses backref pointing to itself */ + if (ref_key->objectid == ref_key->offset) { + cur->is_reloc_root = 1; + /* Only reloc backref cache cares exact root */ + if (cache->is_reloc) { + root = find_reloc_root(fs_info, cur->bytenr); + if (WARN_ON(!root)) + return -ENOENT; + cur->root = root; + } + return 0; + } + + edge = alloc_backref_edge(cache); + if (!edge) + return -ENOMEM; + + 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, + cur->level + 1); + if (!upper) { + free_backref_edge(cache, edge); + return -ENOMEM; + } + + /* + * backrefs for the upper level block isn't + * cached, add the block to pending list + */ + list_add_tail(&edge->list[UPPER], pending_edge); + } else { + /* Parent node already cached */ + upper = rb_entry(rb_node, struct backref_node, + rb_node); + ASSERT(upper->checked); + INIT_LIST_HEAD(&edge->list[UPPER]); + } + link_backref_edge(edge, cur, upper, LINK_LOWER); + return 0; + } + /* + * ref_key.type == BTRFS_TREE_BLOCK_REF_KEY, ref_key->offset means the + * root objectid. We need to search the tree to get its parent bytenr. + */ + root_key.objectid = ref_key->offset; + root_key.type = BTRFS_ROOT_ITEM_KEY; + root_key.offset = (u64)-1; + root = btrfs_get_fs_root(fs_info, &root_key, false); + if (IS_ERR(root)) + return PTR_ERR(root); + if (!test_bit(BTRFS_ROOT_REF_COWS, &root->state)) + cur->cowonly = 1; + + if (btrfs_root_level(&root->root_item) == cur->level) { + /* tree root */ + ASSERT(btrfs_root_bytenr(&root->root_item) == + cur->bytenr); + if (should_ignore_reloc_root(root)) { + btrfs_put_root(root); + list_add(&cur->list, useless_node); + } else { + cur->root = root; + } + return 0; + } + + level = cur->level + 1; + + /* Search the tree to find parent blocks referring the block. */ + path->search_commit_root = 1; + path->skip_locking = 1; + path->lowest_level = level; + ret = btrfs_search_slot(NULL, root, tree_key, path, 0, 0); + path->lowest_level = 0; + if (ret < 0) { + btrfs_put_root(root); + return ret; + } + if (ret > 0 && path->slots[level] > 0) + path->slots[level]--; + + eb = path->nodes[level]; + if (btrfs_node_blockptr(eb, path->slots[level]) != cur->bytenr) { + btrfs_err(fs_info, +"couldn't find block (%llu) (level %d) in tree (%llu) with key (%llu %u %llu)", + cur->bytenr, level - 1, root->root_key.objectid, + tree_key->objectid, tree_key->type, tree_key->offset); + btrfs_put_root(root); + ret = -ENOENT; + goto out; + } + lower = cur; + + /* Add all nodes and edges in the path */ + for (; level < BTRFS_MAX_LEVEL; level++) { + if (!path->nodes[level]) { + ASSERT(btrfs_root_bytenr(&root->root_item) == + lower->bytenr); + if (should_ignore_reloc_root(root)) { + btrfs_put_root(root); + list_add(&lower->list, useless_node); + } else { + lower->root = root; + } + break; + } + + edge = alloc_backref_edge(cache); + if (!edge) { + btrfs_put_root(root); + ret = -ENOMEM; + goto out; + } + + eb = path->nodes[level]; + rb_node = simple_search(&cache->rb_root, eb->start); + if (!rb_node) { + upper = alloc_backref_node(cache, eb->start, + lower->level + 1); + if (!upper) { + btrfs_put_root(root); + free_backref_edge(cache, edge); + ret = -ENOMEM; + goto out; + } + upper->owner = btrfs_header_owner(eb); + if (!test_bit(BTRFS_ROOT_REF_COWS, &root->state)) + upper->cowonly = 1; + + /* + * if we know the block isn't shared we can void + * checking its backrefs. + */ + if (btrfs_block_can_be_shared(root, eb)) + upper->checked = 0; + else + upper->checked = 1; + + /* + * add the block to pending list if we need check its + * backrefs, we only do this once while walking up a + * tree as we will catch anything else later on. + */ + if (!upper->checked && need_check) { + need_check = false; + list_add_tail(&edge->list[UPPER], pending_edge); + } else { + if (upper->checked) + need_check = true; + INIT_LIST_HEAD(&edge->list[UPPER]); + } + } else { + upper = rb_entry(rb_node, struct backref_node, rb_node); + ASSERT(upper->checked); + INIT_LIST_HEAD(&edge->list[UPPER]); + if (!upper->owner) + upper->owner = btrfs_header_owner(eb); + } + link_backref_edge(edge, lower, upper, LINK_LOWER); + + if (rb_node) { + btrfs_put_root(root); + break; + } + lower = upper; + upper = NULL; + } +out: + btrfs_release_path(path); + return ret; +} + +int backref_cache_add_one_tree_block(struct backref_cache *cache, + struct btrfs_path *path, + struct btrfs_backref_iter *iter, + struct btrfs_key *node_key, + struct backref_node *cur) +{ + struct backref_edge *edge; + struct backref_node *exist; + int ret; + + ret = btrfs_backref_iter_start(iter, cur->bytenr); + if (ret < 0) + return ret; + + /* + * We skip the first btrfs_tree_block_info, as we don't use the key + * stored in it, but fetch it from the tree block. + */ + if (btrfs_backref_has_tree_block_info(iter)) { + ret = btrfs_backref_iter_next(iter); + if (ret < 0) + goto out; + /* No extra backref? This means the tree block is corrupted */ + if (ret > 0) { + ret = -EUCLEAN; + goto out; + } + } + WARN_ON(cur->checked); + if (!list_empty(&cur->upper)) { + /* + * the backref was added previously when processing + * backref of type BTRFS_TREE_BLOCK_REF_KEY + */ + ASSERT(list_is_singular(&cur->upper)); + edge = list_entry(cur->upper.next, struct backref_edge, + list[LOWER]); + ASSERT(list_empty(&edge->list[UPPER])); + exist = edge->node[UPPER]; + /* + * add the upper level block to pending list if we need + * check its backrefs + */ + if (!exist->checked) + list_add_tail(&edge->list[UPPER], &cache->pending_edge); + } else { + exist = NULL; + } + + for (; ret == 0; ret = btrfs_backref_iter_next(iter)) { + struct extent_buffer *eb; + struct btrfs_key key; + int type; + + cond_resched(); + eb = btrfs_backref_get_eb(iter); + + key.objectid = iter->bytenr; + if (btrfs_backref_iter_is_inline_ref(iter)) { + struct btrfs_extent_inline_ref *iref; + + /* update key for inline back ref */ + iref = (struct btrfs_extent_inline_ref *)iter->cur_ptr; + type = btrfs_get_extent_inline_ref_type(eb, iref, + BTRFS_REF_TYPE_BLOCK); + if (type == BTRFS_REF_TYPE_INVALID) { + ret = -EUCLEAN; + goto out; + } + key.type = type; + key.offset = btrfs_extent_inline_ref_offset(eb, iref); + } else { + key.type = iter->cur_key.type; + key.offset = iter->cur_key.offset; + } + + /* + * Parent node found and matches current inline ref, no need to + * rebuild this node for this inline ref. + */ + if (exist && + ((key.type == BTRFS_TREE_BLOCK_REF_KEY && + exist->owner == key.offset) || + (key.type == BTRFS_SHARED_BLOCK_REF_KEY && + exist->bytenr == key.offset))) { + exist = NULL; + continue; + } + + ret = handle_one_tree_backref(cache, path, &key, node_key, cur); + if (ret < 0) + goto out; + } + if (ret < 0) + goto out; + ret = 0; + cur->checked = 1; + WARN_ON(exist); +out: + btrfs_backref_iter_release(iter); + return ret; +} diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h index 4a4c9070a38b..6b8b48bf6958 100644 --- a/fs/btrfs/backref.h +++ b/fs/btrfs/backref.h @@ -386,4 +386,10 @@ static inline void backref_cache_panic(struct btrfs_fs_info *fs_info, "Inconsistency in backref cache found at offset %llu", bytenr); } + +int backref_cache_add_one_tree_block(struct backref_cache *cache, + struct btrfs_path *path, + struct btrfs_backref_iter *iter, + struct btrfs_key *node_key, + struct backref_node *cur); #endif diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c index 441d2b28d8e7..4cb61165d852 100644 --- a/fs/btrfs/relocation.c +++ b/fs/btrfs/relocation.c @@ -384,310 +384,6 @@ static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info, return btrfs_get_fs_root(fs_info, &key, false); } -static int handle_one_tree_backref(struct backref_cache *cache, - struct btrfs_path *path, - struct btrfs_key *ref_key, - struct btrfs_key *tree_key, - struct backref_node *cur) -{ - struct btrfs_fs_info *fs_info = cache->fs_info; - struct list_head *useless_node = &cache->useless_node; - struct list_head *pending_edge = &cache->pending_edge; - struct backref_node *upper; - struct backref_node *lower; - struct backref_edge *edge; - struct extent_buffer *eb; - struct btrfs_key root_key; - struct btrfs_root *root; - struct rb_node *rb_node; - bool need_check = true; - int level; - int ret = 0; - - if (ref_key->type != BTRFS_TREE_BLOCK_REF_KEY && - ref_key->type != BTRFS_SHARED_BLOCK_REF_KEY) - return -EUCLEAN; - - /* SHARED_BLOCK_REF means key.offset is the parent bytenr */ - if (ref_key->type == BTRFS_SHARED_BLOCK_REF_KEY) { - - /* Only reloc root uses backref pointing to itself */ - if (ref_key->objectid == ref_key->offset) { - cur->is_reloc_root = 1; - /* Only reloc backref cache cares exact root */ - if (cache->is_reloc) { - root = find_reloc_root(fs_info, cur->bytenr); - if (WARN_ON(!root)) - return -ENOENT; - cur->root = root; - } - return 0; - } - - edge = alloc_backref_edge(cache); - if (!edge) - return -ENOMEM; - - 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, - cur->level + 1); - if (!upper) { - free_backref_edge(cache, edge); - return -ENOMEM; - } - - /* - * backrefs for the upper level block isn't - * cached, add the block to pending list - */ - list_add_tail(&edge->list[UPPER], pending_edge); - } else { - /* Parent node already cached */ - upper = rb_entry(rb_node, struct backref_node, - rb_node); - ASSERT(upper->checked); - INIT_LIST_HEAD(&edge->list[UPPER]); - } - link_backref_edge(edge, cur, upper, LINK_LOWER); - return 0; - } - /* - * ref_key.type == BTRFS_TREE_BLOCK_REF_KEY, ref_key->offset means the - * root objectid. We need to search the tree to get its parent bytenr. - */ - root_key.objectid = ref_key->offset; - root_key.type = BTRFS_ROOT_ITEM_KEY; - root_key.offset = (u64)-1; - root = btrfs_get_fs_root(fs_info, &root_key, false); - if (IS_ERR(root)) - return PTR_ERR(root); - if (!test_bit(BTRFS_ROOT_REF_COWS, &root->state)) - cur->cowonly = 1; - - if (btrfs_root_level(&root->root_item) == cur->level) { - /* tree root */ - ASSERT(btrfs_root_bytenr(&root->root_item) == - cur->bytenr); - if (should_ignore_reloc_root(root)) { - btrfs_put_root(root); - list_add(&cur->list, useless_node); - } else { - cur->root = root; - } - return 0; - } - - level = cur->level + 1; - - /* Search the tree to find parent blocks referring the block. */ - path->search_commit_root = 1; - path->skip_locking = 1; - path->lowest_level = level; - ret = btrfs_search_slot(NULL, root, tree_key, path, 0, 0); - path->lowest_level = 0; - if (ret < 0) { - btrfs_put_root(root); - return ret; - } - if (ret > 0 && path->slots[level] > 0) - path->slots[level]--; - - eb = path->nodes[level]; - if (btrfs_node_blockptr(eb, path->slots[level]) != cur->bytenr) { - btrfs_err(fs_info, -"couldn't find block (%llu) (level %d) in tree (%llu) with key (%llu %u %llu)", - cur->bytenr, level - 1, root->root_key.objectid, - tree_key->objectid, tree_key->type, tree_key->offset); - btrfs_put_root(root); - ret = -ENOENT; - goto out; - } - lower = cur; - - /* Add all nodes and edges in the path */ - for (; level < BTRFS_MAX_LEVEL; level++) { - if (!path->nodes[level]) { - ASSERT(btrfs_root_bytenr(&root->root_item) == - lower->bytenr); - if (should_ignore_reloc_root(root)) { - btrfs_put_root(root); - list_add(&lower->list, useless_node); - } else { - lower->root = root; - } - break; - } - - edge = alloc_backref_edge(cache); - if (!edge) { - btrfs_put_root(root); - ret = -ENOMEM; - goto out; - } - - eb = path->nodes[level]; - rb_node = simple_search(&cache->rb_root, eb->start); - if (!rb_node) { - upper = alloc_backref_node(cache, eb->start, - lower->level + 1); - if (!upper) { - btrfs_put_root(root); - free_backref_edge(cache, edge); - ret = -ENOMEM; - goto out; - } - upper->owner = btrfs_header_owner(eb); - if (!test_bit(BTRFS_ROOT_REF_COWS, &root->state)) - upper->cowonly = 1; - - /* - * if we know the block isn't shared we can void - * checking its backrefs. - */ - if (btrfs_block_can_be_shared(root, eb)) - upper->checked = 0; - else - upper->checked = 1; - - /* - * add the block to pending list if we need check its - * backrefs, we only do this once while walking up a - * tree as we will catch anything else later on. - */ - if (!upper->checked && need_check) { - need_check = false; - list_add_tail(&edge->list[UPPER], pending_edge); - } else { - if (upper->checked) - need_check = true; - INIT_LIST_HEAD(&edge->list[UPPER]); - } - } else { - upper = rb_entry(rb_node, struct backref_node, rb_node); - ASSERT(upper->checked); - INIT_LIST_HEAD(&edge->list[UPPER]); - if (!upper->owner) - upper->owner = btrfs_header_owner(eb); - } - link_backref_edge(edge, lower, upper, LINK_LOWER); - - if (rb_node) { - btrfs_put_root(root); - break; - } - lower = upper; - upper = NULL; - } -out: - btrfs_release_path(path); - return ret; -} - -static int handle_one_tree_block(struct backref_cache *cache, - struct btrfs_path *path, - struct btrfs_backref_iter *iter, - struct btrfs_key *node_key, - struct backref_node *cur) -{ - struct backref_edge *edge; - struct backref_node *exist; - int ret; - - ret = btrfs_backref_iter_start(iter, cur->bytenr); - if (ret < 0) - return ret; - - /* - * We skip the first btrfs_tree_block_info, as we don't use the key - * stored in it, but fetch it from the tree block. - */ - if (btrfs_backref_has_tree_block_info(iter)) { - ret = btrfs_backref_iter_next(iter); - if (ret < 0) - goto out; - /* No extra backref? This means the tree block is corrupted */ - if (ret > 0) { - ret = -EUCLEAN; - goto out; - } - } - WARN_ON(cur->checked); - if (!list_empty(&cur->upper)) { - /* - * the backref was added previously when processing - * backref of type BTRFS_TREE_BLOCK_REF_KEY - */ - ASSERT(list_is_singular(&cur->upper)); - edge = list_entry(cur->upper.next, struct backref_edge, - list[LOWER]); - ASSERT(list_empty(&edge->list[UPPER])); - exist = edge->node[UPPER]; - /* - * add the upper level block to pending list if we need - * check its backrefs - */ - if (!exist->checked) - list_add_tail(&edge->list[UPPER], &cache->pending_edge); - } else { - exist = NULL; - } - - for (; ret == 0; ret = btrfs_backref_iter_next(iter)) { - struct extent_buffer *eb; - struct btrfs_key key; - int type; - - cond_resched(); - eb = btrfs_backref_get_eb(iter); - - key.objectid = iter->bytenr; - if (btrfs_backref_iter_is_inline_ref(iter)) { - struct btrfs_extent_inline_ref *iref; - - /* update key for inline back ref */ - iref = (struct btrfs_extent_inline_ref *)iter->cur_ptr; - type = btrfs_get_extent_inline_ref_type(eb, iref, - BTRFS_REF_TYPE_BLOCK); - if (type == BTRFS_REF_TYPE_INVALID) { - ret = -EUCLEAN; - goto out; - } - key.type = type; - key.offset = btrfs_extent_inline_ref_offset(eb, iref); - } else { - key.type = iter->cur_key.type; - key.offset = iter->cur_key.offset; - } - - /* - * Parent node found and matches current inline ref, no need to - * rebuild this node for this inline ref. - */ - if (exist && - ((key.type == BTRFS_TREE_BLOCK_REF_KEY && - exist->owner == key.offset) || - (key.type == BTRFS_SHARED_BLOCK_REF_KEY && - exist->bytenr == key.offset))) { - exist = NULL; - continue; - } - - ret = handle_one_tree_backref(cache, path, &key, node_key, cur); - if (ret < 0) - goto out; - } - if (ret < 0) - goto out; - ret = 0; - cur->checked = 1; - WARN_ON(exist); -out: - btrfs_backref_iter_release(iter); - return ret; -} - /* * In handle_one_tree_backref(), we have only linked the lower node to the edge, * but the upper node hasn't been linked to the edge. @@ -916,7 +612,8 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, /* Breadth-first search to build backref cache */ while (1) { - ret = handle_one_tree_block(cache, path, iter, node_key, cur); + ret = backref_cache_add_one_tree_block(cache, path, iter, + node_key, cur); if (ret < 0) { err = ret; goto out; From patchwork Tue Mar 3 07:14:08 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 11417311 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 0CA6A924 for ; Tue, 3 Mar 2020 07:15:53 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id DE68D206D5 for ; Tue, 3 Mar 2020 07:15:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727671AbgCCHPw (ORCPT ); Tue, 3 Mar 2020 02:15:52 -0500 Received: from mx2.suse.de ([195.135.220.15]:57048 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727647AbgCCHPv (ORCPT ); Tue, 3 Mar 2020 02:15:51 -0500 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 41871B0BD for ; Tue, 3 Mar 2020 07:15:50 +0000 (UTC) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH 18/19] btrfs: relocation: Move the target backref node insert code into finish_upper_links() Date: Tue, 3 Mar 2020 15:14:08 +0800 Message-Id: <20200303071409.57982-19-wqu@suse.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20200303071409.57982-1-wqu@suse.com> References: <20200303071409.57982-1-wqu@suse.com> MIME-Version: 1.0 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org The snippet of code can be easily merged into finish_upper_links(), thus make related code more reuseable. Signed-off-by: Qu Wenruo --- fs/btrfs/relocation.c | 30 +++++++++++++++--------------- 1 file changed, 15 insertions(+), 15 deletions(-) diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c index 4cb61165d852..ac3ac0c7ac9e 100644 --- a/fs/btrfs/relocation.c +++ b/fs/btrfs/relocation.c @@ -400,8 +400,23 @@ static int finish_upper_links(struct backref_cache *cache, { struct list_head *useless_node = &cache->useless_node; struct backref_edge *edge; + struct rb_node *rb_node; LIST_HEAD(pending_edge); + /* + * everything goes well, connect backref nodes and insert backref nodes + * into the cache. + */ + ASSERT(start->checked); + if (!start->cowonly) { + rb_node = simple_insert(&cache->rb_root, start->bytenr, + &start->rb_node); + if (rb_node) + backref_cache_panic(cache->fs_info, start->bytenr, + -EEXIST); + list_add_tail(&start->lower, &cache->leaves); + } + /* * Use breadth first search to iterate all related edges. * @@ -584,7 +599,6 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, struct backref_node *lower; struct backref_node *node = NULL; struct backref_edge *edge; - struct rb_node *rb_node; int ret; int err = 0; @@ -629,20 +643,6 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, } } - /* - * everything goes well, connect backref nodes and insert backref nodes - * into the cache. - */ - ASSERT(node->checked); - if (!node->cowonly) { - rb_node = simple_insert(&cache->rb_root, node->bytenr, - &node->rb_node); - if (rb_node) - backref_cache_panic(cache->fs_info, node->bytenr, - -EEXIST); - list_add_tail(&node->lower, &cache->leaves); - } - /* Finish the upper linkage of newly added edges/nodes */ ret = finish_upper_links(cache, node); if (ret < 0) { From patchwork Tue Mar 3 07:14:09 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 11417315 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id E9BEF14BC for ; Tue, 3 Mar 2020 07:15:56 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id C9F61215A4 for ; Tue, 3 Mar 2020 07:15:56 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727677AbgCCHP4 (ORCPT ); Tue, 3 Mar 2020 02:15:56 -0500 Received: from mx2.suse.de ([195.135.220.15]:57088 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727672AbgCCHPz (ORCPT ); Tue, 3 Mar 2020 02:15:55 -0500 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 2D44CAC53 for ; Tue, 3 Mar 2020 07:15:52 +0000 (UTC) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH 19/19] btrfs: Rename finish_upper_links() to backref_cache_finish_upper_links() and move it to backref.c Date: Tue, 3 Mar 2020 15:14:09 +0800 Message-Id: <20200303071409.57982-20-wqu@suse.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20200303071409.57982-1-wqu@suse.com> References: <20200303071409.57982-1-wqu@suse.com> MIME-Version: 1.0 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org This the the 2nd major part of generic backref cache. Move it to backref.c so we can reuse it. Signed-off-by: Qu Wenruo --- fs/btrfs/backref.c | 115 +++++++++++++++++++++++++++++++++++++++++ fs/btrfs/backref.h | 2 + fs/btrfs/relocation.c | 117 +----------------------------------------- 3 files changed, 118 insertions(+), 116 deletions(-) diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index e1a271c1e9f3..db0d9bc8d7b6 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -2863,3 +2863,118 @@ int backref_cache_add_one_tree_block(struct backref_cache *cache, btrfs_backref_iter_release(iter); return ret; } + +/* + * In handle_one_tree_backref(), we have only linked the lower node to the edge, + * but the upper node hasn't been linked to the edge. + * This means we can only iterate through backref_node::upper to reach parent + * edges, but not through backref_node::lower to reach children edges. + * + * This function will finish the backref_node::lower to related edges, so that + * backref cache can be bi-directionally iterated. + * + * Also, this will add the nodes to backref cache for next run. + */ +int backref_cache_finish_upper_links(struct backref_cache *cache, + struct backref_node *start) +{ + struct list_head *useless_node = &cache->useless_node; + struct backref_edge *edge; + struct rb_node *rb_node; + LIST_HEAD(pending_edge); + + /* + * everything goes well, connect backref nodes and insert backref nodes + * into the cache. + */ + ASSERT(start->checked); + if (!start->cowonly) { + rb_node = simple_insert(&cache->rb_root, start->bytenr, + &start->rb_node); + if (rb_node) + backref_cache_panic(cache->fs_info, start->bytenr, + -EEXIST); + list_add_tail(&start->lower, &cache->leaves); + } + + /* + * Use breadth first search to iterate all related edges. + * + * The start point is all the edges of this node + */ + list_for_each_entry(edge, &start->upper, list[LOWER]) + list_add_tail(&edge->list[UPPER], &pending_edge); + + while (!list_empty(&pending_edge)) { + struct backref_node *upper; + struct backref_node *lower; + struct rb_node *rb_node; + + edge = list_entry(pending_edge.next, struct backref_edge, + list[UPPER]); + list_del_init(&edge->list[UPPER]); + upper = edge->node[UPPER]; + lower = edge->node[LOWER]; + + /* Parent is detached, no need to keep any edges */ + if (upper->detached) { + list_del(&edge->list[LOWER]); + free_backref_edge(cache, edge); + + /* Lower node is orphan, queue for cleanup */ + if (list_empty(&lower->upper)) + list_add(&lower->list, useless_node); + continue; + } + + /* + * All new nodes added in current build_backref_tree() haven't + * been linked to the cache rb tree. + * So if we have upper->rb_node populated, this means a cache + * hit. We only need to link the edge, as @upper and all its + * parent have already been linked. + */ + if (!RB_EMPTY_NODE(&upper->rb_node)) { + if (upper->lowest) { + list_del_init(&upper->lower); + upper->lowest = 0; + } + + list_add_tail(&edge->list[UPPER], &upper->lower); + continue; + } + + /* Sanity check, we shouldn't have any unchecked nodes */ + if (!upper->checked) { + ASSERT(0); + return -EUCLEAN; + } + + /* Sanity check, cowonly node has non-cowonly parent */ + if (start->cowonly != upper->cowonly) { + ASSERT(0); + return -EUCLEAN; + } + + /* Only cache non-cowonly (subvolume trees) tree blocks */ + if (!upper->cowonly) { + rb_node = simple_insert(&cache->rb_root, upper->bytenr, + &upper->rb_node); + if (rb_node) { + backref_cache_panic(cache->fs_info, + upper->bytenr, -EEXIST); + return -EUCLEAN; + } + } + + list_add_tail(&edge->list[UPPER], &upper->lower); + + /* + * Also queue all the parent edges of this uncached node + * to finish the upper linkage + */ + list_for_each_entry(edge, &upper->upper, list[LOWER]) + list_add_tail(&edge->list[UPPER], &pending_edge); + } + return 0; +} diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h index 6b8b48bf6958..99d61922bf6c 100644 --- a/fs/btrfs/backref.h +++ b/fs/btrfs/backref.h @@ -392,4 +392,6 @@ int backref_cache_add_one_tree_block(struct backref_cache *cache, struct btrfs_backref_iter *iter, struct btrfs_key *node_key, struct backref_node *cur); +int backref_cache_finish_upper_links(struct backref_cache *cache, + struct backref_node *start); #endif diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c index ac3ac0c7ac9e..67691c56ce99 100644 --- a/fs/btrfs/relocation.c +++ b/fs/btrfs/relocation.c @@ -384,121 +384,6 @@ static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info, return btrfs_get_fs_root(fs_info, &key, false); } -/* - * In handle_one_tree_backref(), we have only linked the lower node to the edge, - * but the upper node hasn't been linked to the edge. - * This means we can only iterate through backref_node::upper to reach parent - * edges, but not through backref_node::lower to reach children edges. - * - * This function will finish the backref_node::lower to related edges, so that - * backref cache can be bi-directionally iterated. - * - * Also, this will add the nodes to backref cache for next run. - */ -static int finish_upper_links(struct backref_cache *cache, - struct backref_node *start) -{ - struct list_head *useless_node = &cache->useless_node; - struct backref_edge *edge; - struct rb_node *rb_node; - LIST_HEAD(pending_edge); - - /* - * everything goes well, connect backref nodes and insert backref nodes - * into the cache. - */ - ASSERT(start->checked); - if (!start->cowonly) { - rb_node = simple_insert(&cache->rb_root, start->bytenr, - &start->rb_node); - if (rb_node) - backref_cache_panic(cache->fs_info, start->bytenr, - -EEXIST); - list_add_tail(&start->lower, &cache->leaves); - } - - /* - * Use breadth first search to iterate all related edges. - * - * The start point is all the edges of this node - */ - list_for_each_entry(edge, &start->upper, list[LOWER]) - list_add_tail(&edge->list[UPPER], &pending_edge); - - while (!list_empty(&pending_edge)) { - struct backref_node *upper; - struct backref_node *lower; - struct rb_node *rb_node; - - edge = list_entry(pending_edge.next, struct backref_edge, - list[UPPER]); - list_del_init(&edge->list[UPPER]); - upper = edge->node[UPPER]; - lower = edge->node[LOWER]; - - /* Parent is detached, no need to keep any edges */ - if (upper->detached) { - list_del(&edge->list[LOWER]); - free_backref_edge(cache, edge); - - /* Lower node is orphan, queue for cleanup */ - if (list_empty(&lower->upper)) - list_add(&lower->list, useless_node); - continue; - } - - /* - * All new nodes added in current build_backref_tree() haven't - * been linked to the cache rb tree. - * So if we have upper->rb_node populated, this means a cache - * hit. We only need to link the edge, as @upper and all its - * parent have already been linked. - */ - if (!RB_EMPTY_NODE(&upper->rb_node)) { - if (upper->lowest) { - list_del_init(&upper->lower); - upper->lowest = 0; - } - - list_add_tail(&edge->list[UPPER], &upper->lower); - continue; - } - - /* Sanity check, we shouldn't have any unchecked nodes */ - if (!upper->checked) { - ASSERT(0); - return -EUCLEAN; - } - - /* Sanity check, cowonly node has non-cowonly parent */ - if (start->cowonly != upper->cowonly) { - ASSERT(0); - return -EUCLEAN; - } - - /* Only cache non-cowonly (subvolume trees) tree blocks */ - if (!upper->cowonly) { - rb_node = simple_insert(&cache->rb_root, upper->bytenr, - &upper->rb_node); - if (rb_node) { - backref_cache_panic(cache->fs_info, - upper->bytenr, -EEXIST); - return -EUCLEAN; - } - } - - list_add_tail(&edge->list[UPPER], &upper->lower); - - /* - * Also queue all the parent edges of this uncached node - * to finish the upper linkage - */ - list_for_each_entry(edge, &upper->upper, list[LOWER]) - list_add_tail(&edge->list[UPPER], &pending_edge); - } - return 0; -} - /* * For useless nodes, do two major clean ups: * - Cleanup the children edges and nodes @@ -644,7 +529,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc, } /* Finish the upper linkage of newly added edges/nodes */ - ret = finish_upper_links(cache, node); + ret = backref_cache_finish_upper_links(cache, node); if (ret < 0) { err = ret; goto out;