Skip to contentSkip to conversation

btrfs: Move generic backref cache build functions to backref.c

PATCH In review Qu Wenruo 4 participants 25 messages Mar 3, 2020 – Mar 5, 2020 Btrfs file system

lore
Share & tools
lore

Qu Wenruo

author
#0 lore raw

cover btrfs: Move generic backref cache build functions to backref.c

The patchset is based on previous backref_cache_refactor branch, which is further based on misc-next.

The whole series can be fetched from github:
https://github.com/adam900710/linux/tree/backref_cache_code_move

All the patches in previous branch is not touched at all, thus they are not re-sent in this patchset.

Currently there are 3 major parts of build_backref_tree():
- ITERATION
This will do a breadth-first search, starts from the target bytenr, and queue all parents into the backref cache.
The result is a temporary map, which is only single-directional, and involved new backref nodes are not yet inserted into the cache.

- WEAVING
Finish the map to make it bi-directional, and insert new nodes into the cache.

- CLEANUP
Cleanup the useless nodes, either remove it completely or add them into the cache as detached.

For the ITERATION part, there are only limited locations coupled with relocation.
And WEAVING part is completely independent from relocation. While the CLEANUP part, although it has some relocation related code, it's not a big hunk of code after all.

So, this patchset will move the ITERATION part, extracted as backref_cache_add_one_tree_block(), and the WEAVING part, extracted as backref_cache_finish_upper_links(), to backref.c, as the basis for later reuse of backref_cache.

Qu Wenruo (19):
btrfs: Move backref node/edge/cache structure to backref.h
btrfs: Rename tree_entry to simple_node and export it
btrfs: relocation: Make reloc root search specific for relocation
backref cache
btrfs: relocation: Add backref_cache::pending_edge and
backref_cache::useless_node members
btrfs: relocation: Add backref_cache::fs_info member
btrfs: Move backref_cache_init() to backref.c
btrfs: Move alloc_backref_node() to backref.c
btrfs: Move alloc_backref_edge() to backref.c
btrfs: Move link_backref_edge() to backref.c
btrfs: Move free_backref_node() and free_backref_edge() to backref.h
btrfs: Move drop_backref_node() and needed facilities to backref.h
btrfs: Rename remove_backref_node() to cleanup_backref_node() and move
it to backref.c
btrfs: Move backref_cache_cleanup() to backref.c
btrfs: Rename backref_tree_panic() to backref_cache_panic(), and move
it to backref.c
btrfs: Rename should_ignore_root() to should_ignore_reloc_root() and
export it
btrfs: relocation: Open-code read_fs_root() for
handle_one_tree_backref()
btrfs: Rename handle_one_tree_block() to
backref_cache_add_one_tree_block() and move it to backref.c
btrfs: relocation: Move the target backref node insert code into
finish_upper_links()
btrfs: Rename finish_upper_links() to
backref_cache_finish_upper_links() and move it to backref.c

 fs/btrfs/backref.c    | 534 ++++++++++++++++++++++++++
 fs/btrfs/backref.h    | 226 +++++++++++
 fs/btrfs/ctree.h      |   3 +
 fs/btrfs/misc.h       |  54 +++
 fs/btrfs/relocation.c | 870 ++++--------------------------------------
 5 files changed, 892 insertions(+), 795 deletions(-)
Signature · 1 line
2.25.1
author
#1 lore raw

PATCH 1/19 btrfs: Move backref node/edge/cache structure to backref.h

These 3 structures are the main part of backref cache, move them to backref.h to build the basis for later reuse.

---
 fs/btrfs/backref.h    | 98 +++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/relocation.c | 93 +---------------------------------------
 2 files changed, 100 insertions(+), 91 deletions(-)
fs/btrfs/backref.h +98 -0
index 42fd76dfe553..3cf79fafdf07 100644
@@ -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
fs/btrfs/relocation.c +2 -91

105 lines not on this page · raw message

Signature · 1 line
2.25.1
author
#2 lore raw

PATCH 2/19 btrfs: Rename tree_entry to simple_node and export it

In reply to Qu Wenruo

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.

---
 fs/btrfs/backref.h    |   6 ++-
 fs/btrfs/misc.h       |  54 +++++++++++++++++++++
 fs/btrfs/relocation.c | 109 ++++++++++++++----------------------------
 3 files changed, 94 insertions(+), 75 deletions(-)
fs/btrfs/backref.h +4 -2
index 3cf79fafdf07..923788fa03ef 100644
@@ -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 */
fs/btrfs/misc.h +54 -0

64 lines not on this page · raw message

fs/btrfs/relocation.c +36 -73

241 lines not on this page · raw message

Signature · 1 line
2.25.1
author
#3 lore raw

PATCH 3/19 btrfs: relocation: Make reloc root search specific for relocation backref cache

In reply to Qu Wenruo

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.

---
 fs/btrfs/backref.h    | 14 ++++++++++++++
 fs/btrfs/ctree.h      |  2 ++
 fs/btrfs/relocation.c | 23 +++++++++++++++--------
 3 files changed, 31 insertions(+), 8 deletions(-)
fs/btrfs/backref.h +14 -0
index 923788fa03ef..fbb08b5429ca 100644
@@ -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
fs/btrfs/ctree.h +2 -0
index ea5d0675465a..b57bb3e5f1f2 100644
@@ -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,
fs/btrfs/relocation.c +15 -8
index 50348a58bb43..374efb117387 100644
@@ -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);
Signature · 1 line
2.25.1
author
#4 lore raw

PATCH 4/19 btrfs: relocation: Add backref_cache::pending_edge and backref_cache::useless_node members

In reply to Qu Wenruo

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.

---
 fs/btrfs/backref.h    |  6 ++++
 fs/btrfs/relocation.c | 64 ++++++++++++++++++++++++-------------------
 2 files changed, 42 insertions(+), 28 deletions(-)
fs/btrfs/backref.h +6 -0
index fbb08b5429ca..4ad1193c78e0 100644
@@ -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
fs/btrfs/relocation.c +36 -28

190 lines not on this page · raw message

Signature · 1 line
2.25.1
author
#5 lore raw

PATCH 5/19 btrfs: relocation: Add backref_cache::fs_info member

In reply to Qu Wenruo

Add this member so that we can grab fs_info without the help from reloc_control.

---
 fs/btrfs/backref.h    |  2 ++
 fs/btrfs/relocation.c | 18 +++++++++---------
 2 files changed, 11 insertions(+), 9 deletions(-)
fs/btrfs/backref.h +2 -0
index 4ad1193c78e0..e1438425cf59 100644
@@ -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
fs/btrfs/relocation.c +9 -9
index 413a83d1d9f1..0fb9ceb2665e 100644
@@ -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);
Signature · 1 line
2.25.1
author
#6 lore raw

PATCH 6/19 btrfs: Move backref_cache_init() to backref.c

In reply to Qu Wenruo
---
 fs/btrfs/backref.c    | 16 ++++++++++++++++
 fs/btrfs/backref.h    |  2 ++
 fs/btrfs/relocation.c | 16 ----------------
 3 files changed, 18 insertions(+), 16 deletions(-)
fs/btrfs/backref.c +16 -0
index 01674be3beaa..8fc1d520695e 100644
@@ -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);
+}
fs/btrfs/backref.h +2 -0
index e1438425cf59..65e886fb2008 100644
@@ -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
fs/btrfs/relocation.c +0 -16
index 0fb9ceb2665e..4ec2946f95ae 100644
@@ -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;
Signature · 1 line
2.25.1
author
#7 lore raw

PATCH 7/19 btrfs: Move alloc_backref_node() to backref.c

In reply to Qu Wenruo
---
 fs/btrfs/backref.c    | 20 ++++++++++++++++++++
 fs/btrfs/backref.h    |  2 ++
 fs/btrfs/relocation.c | 20 --------------------
 3 files changed, 22 insertions(+), 20 deletions(-)
fs/btrfs/backref.c +20 -0
index 8fc1d520695e..b6183cb7c60b 100644
@@ -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;
+}
fs/btrfs/backref.h +2 -0
index 65e886fb2008..b7aad5f116ae 100644
@@ -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
fs/btrfs/relocation.c +0 -20
index 4ec2946f95ae..f97ff88dba21 100644
@@ -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)
 {
Signature · 1 line
2.25.1
author
#8 lore raw

PATCH 8/19 btrfs: Move alloc_backref_edge() to backref.c

In reply to Qu Wenruo
---
 fs/btrfs/backref.c    | 10 ++++++++++
 fs/btrfs/backref.h    |  1 +
 fs/btrfs/relocation.c | 10 ----------
 3 files changed, 11 insertions(+), 10 deletions(-)
fs/btrfs/backref.c +10 -0
index b6183cb7c60b..7511ce8447e8 100644
@@ -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;
+}
fs/btrfs/backref.h +1 -0
index b7aad5f116ae..04efc9d44bb8 100644
@@ -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
fs/btrfs/relocation.c +0 -10
index f97ff88dba21..1f4fccd973d1 100644
@@ -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,
Signature · 1 line
2.25.1
author
#9 lore raw

PATCH 9/19 btrfs: Move link_backref_edge() to backref.c

In reply to Qu Wenruo
---
 fs/btrfs/backref.h    | 16 ++++++++++++++++
 fs/btrfs/relocation.c | 16 ----------------
 2 files changed, 16 insertions(+), 16 deletions(-)
fs/btrfs/backref.h +16 -0
index 04efc9d44bb8..431c8a15c5f9 100644
@@ -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
fs/btrfs/relocation.c +0 -16
index 1f4fccd973d1..dfcedd7824bc 100644
@@ -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)
 {
Signature · 1 line
2.25.1
author
#10 lore raw

PATCH 10/19 btrfs: Move free_backref_node() and free_backref_edge() to backref.h

In reply to Qu Wenruo
---
 fs/btrfs/backref.h    | 20 ++++++++++++++++++++
 fs/btrfs/relocation.c | 19 -------------------
 2 files changed, 20 insertions(+), 19 deletions(-)
fs/btrfs/backref.h +20 -0
index 431c8a15c5f9..d8492846a961 100644
@@ -8,6 +8,7 @@
 
 #include <linux/btrfs.h>
 #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
fs/btrfs/relocation.c +0 -19
index dfcedd7824bc..43b1bab2f51f 100644
@@ -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)
 {
 
Signature · 1 line
2.25.1
author
#11 lore raw

PATCH 11/19 btrfs: Move drop_backref_node() and needed facilities to backref.h

In reply to Qu Wenruo

With extra comment for drop_backref_node() as it has some similarity with remove_backref_node(), thus we need extra comment explaining the difference.

---
 fs/btrfs/backref.h    | 37 +++++++++++++++++++++++++++++++++++++
 fs/btrfs/relocation.c | 31 -------------------------------
 2 files changed, 37 insertions(+), 31 deletions(-)
fs/btrfs/backref.h +37 -0
index d8492846a961..7b8bf4e13d99 100644
@@ -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
fs/btrfs/relocation.c +0 -31
index 43b1bab2f51f..1c038428990c 100644
@@ -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
  */
Signature · 1 line
2.25.1
author
#12 lore raw

PATCH 12/19 btrfs: Rename remove_backref_node() to cleanup_backref_node() and move it to backref.c

In reply to Qu Wenruo

Also add comment explaining the cleanup progress, to differ it from drop_backref_node().

---
 fs/btrfs/backref.c    | 38 ++++++++++++++++++++++++++++++++
 fs/btrfs/backref.h    |  9 ++++++++
 fs/btrfs/relocation.c | 51 ++++---------------------------------------
 3 files changed, 51 insertions(+), 47 deletions(-)
fs/btrfs/backref.c +38 -0
index 7511ce8447e8..4f0e8ab1d9cf 100644
@@ -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);
+}
fs/btrfs/backref.h +9 -0
index 7b8bf4e13d99..1c34a8dbee2f 100644
@@ -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
fs/btrfs/relocation.c +4 -47

86 lines not on this page · raw message

Signature · 1 line
2.25.1
author
#13 lore raw

PATCH 13/19 btrfs: Move backref_cache_cleanup() to backref.c

In reply to Qu Wenruo
---
 fs/btrfs/backref.c    | 30 ++++++++++++++++++++++++++++++
 fs/btrfs/backref.h    |  1 +
 fs/btrfs/relocation.c | 30 ------------------------------
 3 files changed, 31 insertions(+), 30 deletions(-)
fs/btrfs/backref.c +30 -0
index 4f0e8ab1d9cf..02455b3bbc35 100644
@@ -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);
+}
fs/btrfs/backref.h +1 -0
index 1c34a8dbee2f..2fb854b1d5f0 100644
@@ -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
fs/btrfs/relocation.c +0 -30
index 2050414884fb..71df172b70bb 100644
@@ -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)
 {
 
Signature · 1 line
2.25.1
author
#14 lore raw

PATCH 14/19 btrfs: Rename backref_tree_panic() to backref_cache_panic(), and move it to backref.c

In reply to Qu Wenruo

Also change the parameter, since all callers can easily grab an fs_info, there is no need for all the dancing.

---
 fs/btrfs/backref.h    |  8 ++++++++
 fs/btrfs/relocation.c | 33 +++++++++++----------------------
 2 files changed, 19 insertions(+), 22 deletions(-)
fs/btrfs/backref.h +8 -0
index 2fb854b1d5f0..4a4c9070a38b 100644
@@ -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
fs/btrfs/relocation.c +11 -22
index 71df172b70bb..349e8e761e8d 100644
@@ -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;
Signature · 1 line
2.25.1
author
#15 lore raw

PATCH 15/19 btrfs: Rename should_ignore_root() to should_ignore_reloc_root() and export it

In reply to Qu Wenruo

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.

---
 fs/btrfs/ctree.h      | 1 +
 fs/btrfs/relocation.c | 9 +++++----
 2 files changed, 6 insertions(+), 4 deletions(-)
fs/btrfs/ctree.h +1 -0
index b57bb3e5f1f2..e45aad90b45e 100644
@@ -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,
fs/btrfs/relocation.c +5 -4
index 349e8e761e8d..2230ea8a3698 100644
@@ -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 {
Signature · 1 line
2.25.1
author
#16 lore raw

PATCH 16/19 btrfs: relocation: Open-code read_fs_root() for handle_one_tree_backref()

In reply to Qu Wenruo

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.

---
 fs/btrfs/relocation.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)
fs/btrfs/relocation.c +5 -1
index 2230ea8a3698..441d2b28d8e7 100644
@@ -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))
Signature · 1 line
2.25.1
author
#17 lore raw

PATCH 17/19 btrfs: Rename handle_one_tree_block() to backref_cache_add_one_tree_block() and move it to backref.c

In reply to Qu Wenruo

This function is the major part of backref cache build process, move it to backref.c so we can reuse it later.

---
 fs/btrfs/backref.c    | 305 +++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/backref.h    |   6 +
 fs/btrfs/relocation.c | 307 +-----------------------------------------
 3 files changed, 313 insertions(+), 305 deletions(-)
fs/btrfs/backref.c +305 -0
index 02455b3bbc35..e1a271c1e9f3 100644
@@ -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;
+}
fs/btrfs/backref.h +6 -0
index 4a4c9070a38b..6b8b48bf6958 100644
@@ -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
fs/btrfs/relocation.c +2 -305

319 lines not on this page · raw message

Signature · 1 line
2.25.1
author
#18 lore raw

PATCH 18/19 btrfs: relocation: Move the target backref node insert code into finish_upper_links()

In reply to Qu Wenruo

The snippet of code can be easily merged into finish_upper_links(), thus make related code more reuseable.

---
 fs/btrfs/relocation.c | 30 +++++++++++++++---------------
 1 file changed, 15 insertions(+), 15 deletions(-)
fs/btrfs/relocation.c +15 -15
index 4cb61165d852..ac3ac0c7ac9e 100644
@@ -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) {
Signature · 1 line
2.25.1
author
#19 lore raw

PATCH 19/19 btrfs: Rename finish_upper_links() to backref_cache_finish_upper_links() and move it to backref.c

In reply to Qu Wenruo

This the the 2nd major part of generic backref cache. Move it to backref.c so we can reuse it.

---
 fs/btrfs/backref.c    | 115 +++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/backref.h    |   2 +
 fs/btrfs/relocation.c | 117 +-----------------------------------------
 3 files changed, 118 insertions(+), 116 deletions(-)
fs/btrfs/backref.c +115 -0
index e1a271c1e9f3..db0d9bc8d7b6 100644
@@ -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;
+}
fs/btrfs/backref.h +2 -0
index 6b8b48bf6958..99d61922bf6c 100644
@@ -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
fs/btrfs/relocation.c +1 -116

129 lines not on this page · raw message

Signature · 1 line
2.25.1
#20 lore raw
In reply to Qu Wenruo
Quoted 8 lines · Qu Wenruo

The patchset is based on previous backref_cache_refactor branch, which is further based on misc-next.

The whole series can be fetched from github:
https://github.com/adam900710/linux/tree/backref_cache_code_move

All the patches in previous branch is not touched at all, thus they are not re-sent in this patchset.

The patches are cleanups and code moving, please fix the coding style issues you find.

* missing lines between declarations and statements
* exported functions need btrfs_ prefix
* comments should start with an upper case letter unless it's an identifier, formatted to 80 columns

As this patchset depends on another one I'm not sure if it's right time to update it now, before the other one is merged as I think the same code is touched and this would cause extra work.

Overall it makes sensed to add more to backref.[hc] and export that as an internal API.

#21 lore raw
Quoted 7 lines · David Sterba
Quoted 6 lines · Qu Wenruo

The patchset is based on previous backref_cache_refactor branch, which is further based on misc-next.

The whole series can be fetched from github:
https://github.com/adam900710/linux/tree/backref_cache_code_move

Quoted 8 lines
Quoted 2 lines

All the patches in previous branch is not touched at all, thus they are not re-sent in this patchset.

The patches are cleanups and code moving, please fix the coding style issues you find.

* missing lines between declarations and statements
* exported functions need btrfs_ prefix

I have some question about this.
Sometimes the "btrfs_" prefix requirement looks too mechanical.

Some functions, like backref_cache_init() is very obvious related to backref cache.
I can't see any special benefit from adding a "btrfs_" prefix.

Thanks,
Qu

Quoted 10 lines

* comments should start with an upper case letter unless it's an identifier, formatted to 80 columns

As this patchset depends on another one I'm not sure if it's right time to update it now, before the other one is merged as I think the same code is touched and this would cause extra work.

Overall it makes sensed to add more to backref.[hc] and export that as an internal API.

#22 lore raw
In reply to Qu Wenruo
Quoted 17 lines · Qu Wenruo

The patchset is based on previous backref_cache_refactor branch, which is further based on misc-next.

The whole series can be fetched from github:
https://github.com/adam900710/linux/tree/backref_cache_code_move

All the patches in previous branch is not touched at all, thus they are not re-sent in this patchset.

Currently there are 3 major parts of build_backref_tree():
- ITERATION
This will do a breadth-first search, starts from the target bytenr, and queue all parents into the backref cache.
The result is a temporary map, which is only single-directional, and involved new backref nodes are not yet inserted into the cache.

Quoted 8 lines

- WEAVING
Finish the map to make it bi-directional, and insert new nodes into the cache.

- CLEANUP
Cleanup the useless nodes, either remove it completely or add them into the cache as detached.

I've found a bunch of bugs in the backref code while fixing Zygo's problem, you are probably going to want to wait for my patches to go in before you start moving things around, because it's going to conflict a bunch. Thanks,

Josef

#23 lore raw
Quoted 27 lines · Josef Bacik
Quoted 17 lines · Qu Wenruo

The patchset is based on previous backref_cache_refactor branch, which is further based on misc-next.

The whole series can be fetched from github:
https://github.com/adam900710/linux/tree/backref_cache_code_move

All the patches in previous branch is not touched at all, thus they are not re-sent in this patchset.

Currently there are 3 major parts of build_backref_tree():
- ITERATION
   This will do a breadth-first search, starts from the target bytenr, and queue all parents into the backref cache.
   The result is a temporary map, which is only single-directional, and involved new backref nodes are not yet inserted into the cache.

Quoted 8 lines

- WEAVING
   Finish the map to make it bi-directional, and insert new nodes into the cache.

- CLEANUP
   Cleanup the useless nodes, either remove it completely or add them into the cache as detached.

Quoted 4 lines

I've found a bunch of bugs in the backref code while fixing Zygo's problem, you are probably going to want to wait for my patches to go in before you start moving things around, because it's going to conflict a bunch.  Thanks,

No problem, it's expected to have some comments even for previous patchset.

So rebasing is expected.

Thanks,
Qu

Quoted 2 lines

Josef

#24 lore raw
Quoted 30 lines · Qu Wenruo
Quoted 27 lines · Josef Bacik
Quoted 25 lines · Qu Wenruo

The patchset is based on previous backref_cache_refactor branch, which is further based on misc-next.

The whole series can be fetched from github:
https://github.com/adam900710/linux/tree/backref_cache_code_move

All the patches in previous branch is not touched at all, thus they are not re-sent in this patchset.

Currently there are 3 major parts of build_backref_tree():
- ITERATION
   This will do a breadth-first search, starts from the target bytenr, and queue all parents into the backref cache.
   The result is a temporary map, which is only single-directional, and involved new backref nodes are not yet inserted into the cache.

- WEAVING
   Finish the map to make it bi-directional, and insert new nodes into the cache.

- CLEANUP
   Cleanup the useless nodes, either remove it completely or add them into the cache as detached.

Quoted 8 lines
Quoted 4 lines

I've found a bunch of bugs in the backref code while fixing Zygo's problem, you are probably going to want to wait for my patches to go in before you start moving things around, because it's going to conflict a bunch.  Thanks,

No problem, it's expected to have some comments even for previous patchset.

So rebasing is expected.

The fixes get merged first so they can be applied to older stable trees, the cleanups that move code are best done as the last thing in the patch queue. So this depends on timing and the amount of conflicts but we have like 2 rcs to go.