Skip to contentSkip to conversation

btrfs: relocation: Refactor build_backref_tree()

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

lore
Share & tools
lore

Qu Wenruo

author
#0 lore raw

v2 cover btrfs: relocation: Refactor build_backref_tree()

This branch can be fetched from github:
https://github.com/adam900710/linux/tree/backref_cache_refactor

The basis is:
10f3586f65b0d0 (david/misc-next) btrfs: fix btrfs_calc_reclaim_metadata_size calculation

The main objective of this patchset is to refactor build_backref_tree() and get myself more familiar with the backref cache.

The refactor also add quite some comments explaining how the backref cache is built, but I'm also working on crafting a new dev doc for the backref cache.

As some more example would greatly help reader to go through the somewhat weird code.

Patch 1~8 haven already been sent to the mail list. This time they are included for a better review.

There are 3 main structures involved:
- backref_cache
The main cache structure, store all the existing cached map.

- backref_node
Represent one tree block.
It can have multiple parent and multiple children backref_edges related.

- backref_edge
Represent one parent-child relationship between two backref_node. Both parent (upper) and child (lower) backref_node can iterate through their list to locate the edge.

The objective build_backref_cache() is to build a map, starting from specified node, to reach all its parents. E.g:

build_backref_tree() is called on bytenr X, then the following map is added to backref_cache:

     Root 257   Root 258
	  A      B
          |    /
          |  /
	  |/  
	  C
	  |
	  X

We will have backref_nodes for X, A, B, C in the backref_cache, and 3 edges between (X, C), (C, A), (C, B).

The short workflow of build_backref_tree() is:

- Iterate through all parent nodes of the specified node (ITERATION)

Here we go breadth first search. We go through direct parent of current node. The iteration is bottom-up.

For how each backref item is handled, check handle_one_tree_backref() for details.

When a direct parent is found, we check if the direct parent is cached:
* Cached:
Allocate the edge between this node and parent. Call it a day, and process next parent.
* Not cached:
Allocate both edges and nodes. And queue the parent node for iteration.

During this stage, new nodes are only allocated, not yet added to cache, and new edges are only linked to lower nodes.

After this step, we have reached all roots referring to the specified node.
Some root nodes may be useless (reloc tree root), they will be queued for later cleanup.

- Finish the linkage between newly added nodes and edges. (WEAVING)
Since previous step only allocated new nodes, and only linked edges with its lower node, we still need to add the nodes to cache, and finish the linkage.

See finish_upper_links() for details.

- Cleanup the useless trees
(CLEANUP)
For reloc trees, we only cache the backref nodes for higher tree nodes. And don't keep any edges. So such backref nodes are marked detached.
Tree leaves for reloc trees are not cached.

Such behavior is to reduce memory usage for useless trees, but still allow backref cache hit, to avoid unnecessary cache search.

And also mark the useless nodes as processed for relocation.

With the refactor, only the CLEANUP part of build_backref_tree() is really coupled with relocation.
And now build_backref_tree() is only 125 lines, it's a pretty good start point for us to reuse backref_cache for other workload, like qgroups.

Changelog:
v2:
- Rebased to misc-next branch
There are some small conflicts due to Josef's root ref count patches. To make sure everything is fine, the main code move part is re-written from scratch to ensure no btrfs_put_fs_root() is missing

- Better handling mark_block_processed()
Now uses in_range() macro, and remove the set_extent_bit() wrapper which only get called in one location.

Qu Wenruo (10):
btrfs: backref: Introduce the skeleton of btrfs_backref_iter
btrfs: backref: Implement btrfs_backref_iter_next()
btrfs: relocation: Use btrfs_backref_iter infrastructure
btrfs: relocation: Rename mark_block_processed() and
__mark_block_processed()
btrfs: relocation: Refactor tree backref processing into its own
function
btrfs: relocation: Use wrapper to replace open-coded edge linking
btrfs: relocation: Specify essential members for alloc_backref_node()
btrfs: relocation: Remove the open-coded goto loop for breadth-first
search
btrfs: relocation: Refactor the finishing part of upper linkage into
finish_upper_links()
btrfs: relocation: Refactor the useless nodes handling into its own
function

 fs/btrfs/backref.c    | 145 +++++++
 fs/btrfs/backref.h    |  94 ++++
 fs/btrfs/relocation.c | 968 ++++++++++++++++++++++--------------------
 3 files changed, 749 insertions(+), 458 deletions(-)
Signature · 1 line
2.25.1
author
#1 lore raw

PATCH v2 1/10 btrfs: backref: Introduce the skeleton of btrfs_backref_iter

Due to the complex nature of btrfs extent tree, when we want to iterate all backrefs of one extent, it involves quite a lot of work, like searching the EXTENT_ITEM/METADATA_ITEM, iteration through inline and keyed backrefs.

Normally this would result pretty complex code, something like:
btrfs_search_slot()
/* Ensure we are at EXTENT_ITEM/METADATA_ITEM */
while (1) { /* Loop for extent tree items */

	while (ptr < end) { /* Loop for inlined items */
		/* REAL WORK HERE */
	}
  next:
  	ret = btrfs_next_item()
	/* Ensure we're still at keyed item for specified bytenr */

}

The idea of btrfs_backref_iter is to avoid such complex and hard to read code structure, but something like the following:

iter = btrfs_backref_iter_alloc();
ret = btrfs_backref_iter_start(iter, bytenr);
if (ret < 0)

	goto out;
  for (; ; ret = btrfs_backref_iter_next(iter)) {
	/* REAL WORK HERE */

}
out:
btrfs_backref_iter_free(iter);

This patch is just the skeleton + btrfs_backref_iter_start() code.

---
 fs/btrfs/backref.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/backref.h | 60 ++++++++++++++++++++++++++++++++
 2 files changed, 147 insertions(+)
fs/btrfs/backref.c +87 -0
index 327e4480957b..444cd5d31d87 100644
@@ -2299,3 +2299,90 @@ void free_ipath(struct inode_fs_paths *ipath)
 	kvfree(ipath->fspath);
 	kfree(ipath);
 }
+
+int btrfs_backref_iter_start(struct btrfs_backref_iter *iter, u64 bytenr)
+{
+	struct btrfs_fs_info *fs_info = iter->fs_info;
+	struct btrfs_path *path = iter->path;
+	struct btrfs_extent_item *ei;
+	struct btrfs_key key;
+	int ret;
+
+	key.objectid = bytenr;
+	key.type = BTRFS_METADATA_ITEM_KEY;
+	key.offset = (u64)-1;
+	iter->bytenr = bytenr;
+
+	ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, path, 0, 0);
+	if (ret < 0)
+		return ret;
+	if (ret == 0) {
+		ret = -EUCLEAN;
+		goto release;
+	}
+	if (path->slots[0] == 0) {
+		WARN_ON(IS_ENABLED(CONFIG_BTRFS_DEBUG));
+		ret = -EUCLEAN;
+		goto release;
+	}
+	path->slots[0]--;
+
+	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+	if (!(key.type == BTRFS_EXTENT_ITEM_KEY ||
+	      key.type == BTRFS_METADATA_ITEM_KEY) || key.objectid != bytenr) {
+		ret = -ENOENT;
+		goto release;
+	}
+	memcpy(&iter->cur_key, &key, sizeof(key));
+	iter->item_ptr = btrfs_item_ptr_offset(path->nodes[0],
+					       path->slots[0]);
+	iter->end_ptr = iter->item_ptr + btrfs_item_size_nr(path->nodes[0],
+							    path->slots[0]);
+	ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
+			    struct btrfs_extent_item);
+
+	/*
+	 * Only support iteration on tree backref yet.
+	 *
+	 * This is extra precaustion for non skinny-metadata, where
+	 * EXTENT_ITEM is also used for tree blocks, that we can only use
+	 * extent flags to determine if it's a tree block.
+	 */
+	if (btrfs_extent_flags(path->nodes[0], ei) & BTRFS_EXTENT_FLAG_DATA) {
+		ret = -ENOTTY;
+		goto release;
+	}
+	iter->cur_ptr = iter->item_ptr + sizeof(*ei);
+
+	/* If there is no inline backref, go search for keyed backref */
+	if (iter->cur_ptr >= iter->end_ptr) {
+		ret = btrfs_next_item(fs_info->extent_root, path);
+
+		/* No inline nor keyed ref */
+		if (ret > 0) {
+			ret = -ENOENT;
+			goto release;
+		}
+		if (ret < 0)
+			goto release;
+
+		btrfs_item_key_to_cpu(path->nodes[0], &iter->cur_key,
+				path->slots[0]);
+		if (iter->cur_key.objectid != bytenr ||
+		    (iter->cur_key.type != BTRFS_SHARED_BLOCK_REF_KEY &&
+		     iter->cur_key.type != BTRFS_TREE_BLOCK_REF_KEY)) {
+			ret = -ENOENT;
+			goto release;
+		}
+		iter->cur_ptr = btrfs_item_ptr_offset(path->nodes[0],
+						      path->slots[0]);
+		iter->item_ptr = iter->cur_ptr;
+		iter->end_ptr = iter->item_ptr + btrfs_item_size_nr(
+				path->nodes[0], path->slots[0]);
+	}
+
+	return 0;
+release:
+	btrfs_backref_iter_release(iter);
+	return ret;
+}
fs/btrfs/backref.h +60 -0

64 lines not on this page · raw message

Signature · 1 line
2.25.1
#2 lore raw

Re: [PATCH v2 01/10] btrfs: backref: Introduce the skeleton of btrfs_backref_iter

Quoted 88 lines · Qu Wenruo

Due to the complex nature of btrfs extent tree, when we want to iterate all backrefs of one extent, it involves quite a lot of work, like searching the EXTENT_ITEM/METADATA_ITEM, iteration through inline and keyed backrefs.

Normally this would result pretty complex code, something like:
btrfs_search_slot()
/* Ensure we are at EXTENT_ITEM/METADATA_ITEM */
while (1) { /* Loop for extent tree items */

	while (ptr < end) { /* Loop for inlined items */
		/* REAL WORK HERE */
	}
  next:
  	ret = btrfs_next_item()
	/* Ensure we're still at keyed item for specified bytenr */

}

The idea of btrfs_backref_iter is to avoid such complex and hard to read code structure, but something like the following:

iter = btrfs_backref_iter_alloc();
ret = btrfs_backref_iter_start(iter, bytenr);
if (ret < 0)

	goto out;
  for (; ; ret = btrfs_backref_iter_next(iter)) {
	/* REAL WORK HERE */

}
out:
btrfs_backref_iter_free(iter);

This patch is just the skeleton + btrfs_backref_iter_start() code.

---
 fs/btrfs/backref.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/backref.h | 60 ++++++++++++++++++++++++++++++++
 2 files changed, 147 insertions(+)
fs/btrfs/backref.c +41 -0
index 327e4480957b..444cd5d31d87 100644
@@ -2299,3 +2299,90 @@ void free_ipath(struct inode_fs_paths *ipath)
 	kvfree(ipath->fspath);
 	kfree(ipath);
 }
+
+int btrfs_backref_iter_start(struct btrfs_backref_iter *iter, u64 bytenr)
+{
+	struct btrfs_fs_info *fs_info = iter->fs_info;
+	struct btrfs_path *path = iter->path;
+	struct btrfs_extent_item *ei;
+	struct btrfs_key key;
+	int ret;
+
+	key.objectid = bytenr;
+	key.type = BTRFS_METADATA_ITEM_KEY;
+	key.offset = (u64)-1;
+	iter->bytenr = bytenr;
+
+	ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, path, 0, 0);
+	if (ret < 0)
+		return ret;
+	if (ret == 0) {
+		ret = -EUCLEAN;
+		goto release;
+	}
+	if (path->slots[0] == 0) {
+		WARN_ON(IS_ENABLED(CONFIG_BTRFS_DEBUG));
+		ret = -EUCLEAN;
+		goto release;
+	}
+	path->slots[0]--;
+
+	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+	if (!(key.type == BTRFS_EXTENT_ITEM_KEY ||
+	      key.type == BTRFS_METADATA_ITEM_KEY) || key.objectid != bytenr) {
+		ret = -ENOENT;
+		goto release;
+	}
+	memcpy(&iter->cur_key, &key, sizeof(key));
+	iter->item_ptr = btrfs_item_ptr_offset(path->nodes[0],
+					       path->slots[0]);
+	iter->end_ptr = iter->item_ptr + btrfs_item_size_nr(path->nodes[0],
+							    path->slots[0]);
+	ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
+			    struct btrfs_extent_item);

fs/btrfs/backref.c void free_ipath(struct inode_fs_paths *ipath) · line 2352

Quoted 10 lines
fs/btrfs/backref.c +10 -0
+
+	/*
+	 * Only support iteration on tree backref yet.
+	 *
+	 * This is extra precaustion for non skinny-metadata, where
+	 * EXTENT_ITEM is also used for tree blocks, that we can only use
+	 * extent flags to determine if it's a tree block.
+	 */
+	if (btrfs_extent_flags(path->nodes[0], ei) & BTRFS_EXTENT_FLAG_DATA) {
+		ret = -ENOTTY;

What's the reason for ENOTTY?

Quoted 51 lines
fs/btrfs/backref.c +36 -0
+		goto release;
+	}
+	iter->cur_ptr = iter->item_ptr + sizeof(*ei);
+
+	/* If there is no inline backref, go search for keyed backref */
+	if (iter->cur_ptr >= iter->end_ptr) {
+		ret = btrfs_next_item(fs_info->extent_root, path);
+
+		/* No inline nor keyed ref */
+		if (ret > 0) {
+			ret = -ENOENT;
+			goto release;
+		}
+		if (ret < 0)
+			goto release;
+
+		btrfs_item_key_to_cpu(path->nodes[0], &iter->cur_key,
+				path->slots[0]);
+		if (iter->cur_key.objectid != bytenr ||
+		    (iter->cur_key.type != BTRFS_SHARED_BLOCK_REF_KEY &&
+		     iter->cur_key.type != BTRFS_TREE_BLOCK_REF_KEY)) {
+			ret = -ENOENT;
+			goto release;
+		}
+		iter->cur_ptr = btrfs_item_ptr_offset(path->nodes[0],
+						      path->slots[0]);
+		iter->item_ptr = iter->cur_ptr;
+		iter->end_ptr = iter->item_ptr + btrfs_item_size_nr(
+				path->nodes[0], path->slots[0]);
+	}
+
+	return 0;
+release:
+	btrfs_backref_iter_release(iter);
+	return ret;
+}
fs/btrfs/backref.h +7 -0
index 777f61dc081e..8b1ec11d4b28 100644
@@ -74,4 +74,64 @@ struct prelim_ref {
 	u64 wanted_disk_byte;
 };
 
+/*
+ * Helper structure to help iterate backrefs of one extent.
+ *
+ * Now it only supports iteration for tree block in commit root.
+ */
+struct btrfs_backref_iter {
+	u64 bytenr;

fs/btrfs/backref.h struct prelim_ref { · line 93

Quoted 10 lines
fs/btrfs/backref.h +10 -0
+	struct btrfs_path *path;
+	struct btrfs_fs_info *fs_info;
+	struct btrfs_key cur_key;
+	unsigned long item_ptr;
+	unsigned long cur_ptr;
+	unsigned long end_ptr;
+};
+
+static inline struct btrfs_backref_iter *
+btrfs_backref_iter_alloc(struct btrfs_fs_info *fs_info, gfp_t gfp_flag)

This does not need to be static inline, and please keep the type and function name on the same line.

Quoted 21 lines
fs/btrfs/backref.h +21 -0
+{
+	struct btrfs_backref_iter *ret;
+
+	ret = kzalloc(sizeof(*ret), gfp_flag);
+	if (!ret)
+		return NULL;
+
+	ret->path = btrfs_alloc_path();
+	if (!ret) {
+		kfree(ret);
+		return NULL;
+	}
+
+	/* Current backref iterator only supports iteration in commit root */
+	ret->path->search_commit_root = 1;
+	ret->path->skip_locking = 1;
+	ret->path->reada = READA_FORWARD;
+	ret->fs_info = fs_info;
+
+	return ret;
+}
#3 lore raw

Re: [PATCH v2 01/10] btrfs: backref: Introduce the skeleton of btrfs_backref_iter

Quoted 93 lines · David Sterba
Quoted 92 lines · Qu Wenruo

Due to the complex nature of btrfs extent tree, when we want to iterate all backrefs of one extent, it involves quite a lot of work, like searching the EXTENT_ITEM/METADATA_ITEM, iteration through inline and keyed backrefs.

Normally this would result pretty complex code, something like:
btrfs_search_slot()
/* Ensure we are at EXTENT_ITEM/METADATA_ITEM */
while (1) { /* Loop for extent tree items */

	while (ptr < end) { /* Loop for inlined items */
		/* REAL WORK HERE */
	}
  next:
  	ret = btrfs_next_item()
	/* Ensure we're still at keyed item for specified bytenr */

}

The idea of btrfs_backref_iter is to avoid such complex and hard to read code structure, but something like the following:

iter = btrfs_backref_iter_alloc();
ret = btrfs_backref_iter_start(iter, bytenr);
if (ret < 0)

	goto out;
  for (; ; ret = btrfs_backref_iter_next(iter)) {
	/* REAL WORK HERE */

}
out:
btrfs_backref_iter_free(iter);

This patch is just the skeleton + btrfs_backref_iter_start() code.

---
 fs/btrfs/backref.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/backref.h | 60 ++++++++++++++++++++++++++++++++
 2 files changed, 147 insertions(+)
fs/btrfs/backref.c +45 -0
index 327e4480957b..444cd5d31d87 100644
@@ -2299,3 +2299,90 @@ void free_ipath(struct inode_fs_paths *ipath)
 	kvfree(ipath->fspath);
 	kfree(ipath);
 }
+
+int btrfs_backref_iter_start(struct btrfs_backref_iter *iter, u64 bytenr)
+{
+	struct btrfs_fs_info *fs_info = iter->fs_info;
+	struct btrfs_path *path = iter->path;
+	struct btrfs_extent_item *ei;
+	struct btrfs_key key;
+	int ret;
+
+	key.objectid = bytenr;
+	key.type = BTRFS_METADATA_ITEM_KEY;
+	key.offset = (u64)-1;
+	iter->bytenr = bytenr;
+
+	ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, path, 0, 0);
+	if (ret < 0)
+		return ret;
+	if (ret == 0) {
+		ret = -EUCLEAN;
+		goto release;
+	}
+	if (path->slots[0] == 0) {
+		WARN_ON(IS_ENABLED(CONFIG_BTRFS_DEBUG));
+		ret = -EUCLEAN;
+		goto release;
+	}
+	path->slots[0]--;
+
+	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+	if (!(key.type == BTRFS_EXTENT_ITEM_KEY ||
+	      key.type == BTRFS_METADATA_ITEM_KEY) || key.objectid != bytenr) {
+		ret = -ENOENT;
+		goto release;
+	}
+	memcpy(&iter->cur_key, &key, sizeof(key));
+	iter->item_ptr = btrfs_item_ptr_offset(path->nodes[0],
+					       path->slots[0]);
+	iter->end_ptr = iter->item_ptr + btrfs_item_size_nr(path->nodes[0],
+							    path->slots[0]);
+	ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
+			    struct btrfs_extent_item);
+
+	/*
+	 * Only support iteration on tree backref yet.
+	 *
Quoted 8 lines

fs/btrfs/backref.c void free_ipath(struct inode_fs_paths *ipath) · line 2352

Quoted 6 lines
fs/btrfs/backref.c +6 -0
+	 * This is extra precaustion for non skinny-metadata, where
+	 * EXTENT_ITEM is also used for tree blocks, that we can only use
+	 * extent flags to determine if it's a tree block.
+	 */
+	if (btrfs_extent_flags(path->nodes[0], ei) & BTRFS_EXTENT_FLAG_DATA) {
+		ret = -ENOTTY;

What's the reason for ENOTTY?

Because it's not supported yet.

Quoted 57 lines
Quoted 57 lines
fs/btrfs/backref.c +36 -0
+		goto release;
+	}
+	iter->cur_ptr = iter->item_ptr + sizeof(*ei);
+
+	/* If there is no inline backref, go search for keyed backref */
+	if (iter->cur_ptr >= iter->end_ptr) {
+		ret = btrfs_next_item(fs_info->extent_root, path);
+
+		/* No inline nor keyed ref */
+		if (ret > 0) {
+			ret = -ENOENT;
+			goto release;
+		}
+		if (ret < 0)
+			goto release;
+
+		btrfs_item_key_to_cpu(path->nodes[0], &iter->cur_key,
+				path->slots[0]);
+		if (iter->cur_key.objectid != bytenr ||
+		    (iter->cur_key.type != BTRFS_SHARED_BLOCK_REF_KEY &&
+		     iter->cur_key.type != BTRFS_TREE_BLOCK_REF_KEY)) {
+			ret = -ENOENT;
+			goto release;
+		}
+		iter->cur_ptr = btrfs_item_ptr_offset(path->nodes[0],
+						      path->slots[0]);
+		iter->item_ptr = iter->cur_ptr;
+		iter->end_ptr = iter->item_ptr + btrfs_item_size_nr(
+				path->nodes[0], path->slots[0]);
+	}
+
+	return 0;
+release:
+	btrfs_backref_iter_release(iter);
+	return ret;
+}
fs/btrfs/backref.h +12 -0
index 777f61dc081e..8b1ec11d4b28 100644
@@ -74,4 +74,64 @@ struct prelim_ref {
 	u64 wanted_disk_byte;
 };
 
+/*
+ * Helper structure to help iterate backrefs of one extent.
+ *
+ * Now it only supports iteration for tree block in commit root.
+ */
+struct btrfs_backref_iter {
+	u64 bytenr;
+	struct btrfs_path *path;
+	struct btrfs_fs_info *fs_info;
+	struct btrfs_key cur_key;
+	unsigned long item_ptr;
+	unsigned long cur_ptr;
Quoted 8 lines

fs/btrfs/backref.h struct prelim_ref { · line 93

Quoted 5 lines
fs/btrfs/backref.h +5 -0
+	unsigned long end_ptr;
+};
+
+static inline struct btrfs_backref_iter *
+btrfs_backref_iter_alloc(struct btrfs_fs_info *fs_info, gfp_t gfp_flag)

This does not need to be static inline, and please keep the type and function name on the same line.

OK, that makes sense.

Thanks,
Qu

Quoted 22 lines
Quoted 22 lines
fs/btrfs/backref.h +21 -0
+{
+	struct btrfs_backref_iter *ret;
+
+	ret = kzalloc(sizeof(*ret), gfp_flag);
+	if (!ret)
+		return NULL;
+
+	ret->path = btrfs_alloc_path();
+	if (!ret) {
+		kfree(ret);
+		return NULL;
+	}
+
+	/* Current backref iterator only supports iteration in commit root */
+	ret->path->search_commit_root = 1;
+	ret->path->skip_locking = 1;
+	ret->path->reada = READA_FORWARD;
+	ret->fs_info = fs_info;
+
+	return ret;
+}
#4 lore raw

Re: [PATCH v2 01/10] btrfs: backref: Introduce the skeleton of btrfs_backref_iter

In reply to Qu Wenruo

fs/btrfs/backref.h struct prelim_ref { · line 89

Quoted 9 lines · Qu Wenruo
fs/btrfs/backref.h +8 -0
+struct btrfs_backref_iter {
+	u64 bytenr;
+	struct btrfs_path *path;
+	struct btrfs_fs_info *fs_info;
+	struct btrfs_key cur_key;
 
+	unsigned long item_ptr;
+	unsigned long cur_ptr;
+	unsigned long end_ptr;

I think these can be u32, only processing the leaf data, this would save some stack space consumed by the iterators.

#5 lore raw

Re: [PATCH v2 01/10] btrfs: backref: Introduce the skeleton of btrfs_backref_iter

Quoted 7 lines · David Sterba
Quoted 5 lines · Qu Wenruo
fs/btrfs/backref.h +5 -0
+struct btrfs_backref_iter {
+	u64 bytenr;
+	struct btrfs_path *path;
+	struct btrfs_fs_info *fs_info;
+	struct btrfs_key cur_key;
Quoted 7 lines

fs/btrfs/backref.h struct prelim_ref { · line 89

Quoted 3 lines
fs/btrfs/backref.h +3 -0
+	unsigned long item_ptr;
+	unsigned long cur_ptr;
+	unsigned long end_ptr;

I think these can be u32, only processing the leaf data, this would save some stack space consumed by the iterators.

The only reason is we need to do force type convert, as it needs to be converted to pointer.

But since it's all used inside backref iter functions, it shouldn't cause much trouble for callers.

So I'll update it to u32 in next version.

Thanks,
Qu

#6 lore raw

Re: [PATCH v2 01/10] btrfs: backref: Introduce the skeleton of btrfs_backref_iter

In reply to Qu Wenruo
Quoted 71 lines · Qu Wenruo

Due to the complex nature of btrfs extent tree, when we want to iterate all backrefs of one extent, it involves quite a lot of work, like searching the EXTENT_ITEM/METADATA_ITEM, iteration through inline and keyed backrefs.

Normally this would result pretty complex code, something like:
btrfs_search_slot()
/* Ensure we are at EXTENT_ITEM/METADATA_ITEM */
while (1) { /* Loop for extent tree items */

	while (ptr < end) { /* Loop for inlined items */
		/* REAL WORK HERE */
	}
  next:
  	ret = btrfs_next_item()
	/* Ensure we're still at keyed item for specified bytenr */

}

The idea of btrfs_backref_iter is to avoid such complex and hard to read code structure, but something like the following:

iter = btrfs_backref_iter_alloc();
ret = btrfs_backref_iter_start(iter, bytenr);
if (ret < 0)

	goto out;
  for (; ; ret = btrfs_backref_iter_next(iter)) {
	/* REAL WORK HERE */

}
out:
btrfs_backref_iter_free(iter);

This patch is just the skeleton + btrfs_backref_iter_start() code.

---
 fs/btrfs/backref.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/backref.h | 60 ++++++++++++++++++++++++++++++++
 2 files changed, 147 insertions(+)
fs/btrfs/backref.c +24 -0
index 327e4480957b..444cd5d31d87 100644
@@ -2299,3 +2299,90 @@ void free_ipath(struct inode_fs_paths *ipath)
 	kvfree(ipath->fspath);
 	kfree(ipath);
 }
+
+int btrfs_backref_iter_start(struct btrfs_backref_iter *iter, u64 bytenr)
+{
+	struct btrfs_fs_info *fs_info = iter->fs_info;
+	struct btrfs_path *path = iter->path;
+	struct btrfs_extent_item *ei;
+	struct btrfs_key key;
+	int ret;
+
+	key.objectid = bytenr;
+	key.type = BTRFS_METADATA_ITEM_KEY;
+	key.offset = (u64)-1;
+	iter->bytenr = bytenr;
+
+	ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, path, 0, 0);
+	if (ret < 0)
+		return ret;
+	if (ret == 0) {
+		ret = -EUCLEAN;
+		goto release;
+	}
+	if (path->slots[0] == 0) {
+		WARN_ON(IS_ENABLED(CONFIG_BTRFS_DEBUG));
+		ret = -EUCLEAN;

fs/btrfs/backref.c void free_ipath(struct inode_fs_paths *ipath) · line 2335

Quoted 10 lines
fs/btrfs/backref.c +10 -0
+		goto release;
+	}
+	path->slots[0]--;
+
+	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+	if (!(key.type == BTRFS_EXTENT_ITEM_KEY ||
+	      key.type == BTRFS_METADATA_ITEM_KEY) || key.objectid != bytenr) {
+		ret = -ENOENT;
+		goto release;
+	}

nit: Please keep the logic of the checks identical as it makes comprehending the code easier. What I mean is here you do !(type == COND1 || type == COND2) which really translates to type != COND && type != COND2. However, when checking for keyed items you use the second style. Yes, they are both identical in terms of semantics but one might wonder "why is this done in 2 different ways for no apparent reason" ?

Quoted 7 lines
fs/btrfs/backref.c +7 -0
+	memcpy(&iter->cur_key, &key, sizeof(key));
+	iter->item_ptr = btrfs_item_ptr_offset(path->nodes[0],
+					       path->slots[0]);
+	iter->end_ptr = iter->item_ptr + btrfs_item_size_nr(path->nodes[0],
+							    path->slots[0]);
+	ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
+			    struct btrfs_extent_item);

fs/btrfs/backref.c void free_ipath(struct inode_fs_paths *ipath) · line 2352

Quoted 10 lines
fs/btrfs/backref.c +10 -0
+
+	/*
+	 * Only support iteration on tree backref yet.
+	 *
+	 * This is extra precaustion for non skinny-metadata, where
+	 * EXTENT_ITEM is also used for tree blocks, that we can only use
+	 * extent flags to determine if it's a tree block.
+	 */
+	if (btrfs_extent_flags(path->nodes[0], ei) & BTRFS_EXTENT_FLAG_DATA) {
+		ret = -ENOTTY;

why not simply -ENOSUPP

Quoted 2 lines
fs/btrfs/backref.c +2 -0
+		goto release;
+	}

<snip>

author
#7 lore raw

PATCH v2 2/10 btrfs: backref: Implement btrfs_backref_iter_next()

In reply to Qu Wenruo

This function will go next inline/keyed backref for btrfs_backref_iter infrastructure.

---
 fs/btrfs/backref.c | 58 ++++++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/backref.h | 34 +++++++++++++++++++++++++++
 2 files changed, 92 insertions(+)
fs/btrfs/backref.c +58 -0
index 444cd5d31d87..01674be3beaa 100644
@@ -2386,3 +2386,61 @@ int btrfs_backref_iter_start(struct btrfs_backref_iter *iter, u64 bytenr)
 	btrfs_backref_iter_release(iter);
 	return ret;
 }
+
+/*
+ * Go to next backref item of current bytenr, can be either inlined or keyed.
+ *
+ * Caller need to check whether it's inline ref or not by iter->cur_key.
+ *
+ * Return 0 if we get next backref without problem.
+ * Return >0 if there is no extra backref for this bytenr.
+ * Return <0 if there is something wrong happened.
+ */
+int btrfs_backref_iter_next(struct btrfs_backref_iter *iter)
+{
+	struct extent_buffer *eb = btrfs_backref_get_eb(iter);
+	struct btrfs_path *path = iter->path;
+	struct btrfs_extent_inline_ref *iref;
+	int ret;
+	u32 size;
+
+	if (btrfs_backref_iter_is_inline_ref(iter)) {
+		/* We're still inside the inline refs */
+		ASSERT(iter->cur_ptr < iter->end_ptr);
+
+		if (btrfs_backref_has_tree_block_info(iter)) {
+			/* First tree block info */
+			size = sizeof(struct btrfs_tree_block_info);
+		} else {
+			/* Use inline ref type to determine the size */
+			int type;
+
+			iref = (struct btrfs_extent_inline_ref *)
+				(iter->cur_ptr);
+			type = btrfs_extent_inline_ref_type(eb, iref);
+
+			size = btrfs_extent_inline_ref_size(type);
+		}
+		iter->cur_ptr += size;
+		if (iter->cur_ptr < iter->end_ptr)
+			return 0;
+
+		/* All inline items iterated, fall through */
+	}
+	/* We're at keyed items, there is no inline item, just go next item */
+	ret = btrfs_next_item(iter->fs_info->extent_root, iter->path);
+	if (ret)
+		return ret;
+
+	btrfs_item_key_to_cpu(path->nodes[0], &iter->cur_key, path->slots[0]);
+	if (iter->cur_key.objectid != iter->bytenr ||
+	    (iter->cur_key.type != BTRFS_TREE_BLOCK_REF_KEY &&
+	     iter->cur_key.type != BTRFS_SHARED_BLOCK_REF_KEY))
+		return 1;
+	iter->item_ptr = btrfs_item_ptr_offset(path->nodes[0],
+					       path->slots[0]);
+	iter->cur_ptr = iter->item_ptr;
+	iter->end_ptr = iter->item_ptr + btrfs_item_size_nr(path->nodes[0],
+							    path->slots[0]);
+	return 0;
+}
fs/btrfs/backref.h +34 -0
index 8b1ec11d4b28..42fd76dfe553 100644
@@ -121,8 +121,42 @@ static inline void btrfs_backref_iter_free(struct btrfs_backref_iter *iter)
 	kfree(iter);
 }
 
+static inline struct extent_buffer *
+btrfs_backref_get_eb(struct btrfs_backref_iter *iter)
+{
+	if (!iter)
+		return NULL;
+	return iter->path->nodes[0];
+}
+
+/*
+ * For metadata with EXTENT_ITEM key (non-skinny) case, the first inline data
+ * is btrfs_tree_block_info, without a btrfs_extent_inline_ref header.
+ *
+ * This helper is here to determine if that's the case.
+ */
+static inline bool btrfs_backref_has_tree_block_info(
+		struct btrfs_backref_iter *iter)
+{
+	if (iter->cur_key.type == BTRFS_EXTENT_ITEM_KEY &&
+	    iter->cur_ptr - iter->item_ptr == sizeof(struct btrfs_extent_item))
+		return true;
+	return false;
+}
+
 int btrfs_backref_iter_start(struct btrfs_backref_iter *iter, u64 bytenr);
 
+int btrfs_backref_iter_next(struct btrfs_backref_iter *iter);
+
+static inline bool
+btrfs_backref_iter_is_inline_ref(struct btrfs_backref_iter *iter)
+{
+	if (iter->cur_key.type == BTRFS_EXTENT_ITEM_KEY ||
+	    iter->cur_key.type == BTRFS_METADATA_ITEM_KEY)
+		return true;
+	return false;
+}
+
 static inline void
 btrfs_backref_iter_release(struct btrfs_backref_iter *iter)
 {
Signature · 1 line
2.25.1
author
#8 lore raw

PATCH v2 3/10 btrfs: relocation: Use btrfs_backref_iter infrastructure

In reply to Qu Wenruo

In the core function of relocation, build_backref_tree, it needs to iterate all backref items of one tree block.

We don't really want to spend our code and reviewers' time to going through tons of supportive code just for the backref walk.

Use btrfs_backref_iter infrastructure to do the loop.

The backref items look would be much more easier to read:

	ret = btrfs_backref_iter_start(iter, cur->bytenr);
	for (; ret == 0; ret = btrfs_backref_iter_next(iter)) {
		/* The really important work */
	}
---
 fs/btrfs/relocation.c | 193 ++++++++++++++----------------------------
 1 file changed, 62 insertions(+), 131 deletions(-)
fs/btrfs/relocation.c +62 -131
index 6130ba69bc49..490d684002f9 100644
@@ -22,6 +22,7 @@
 #include "print-tree.h"
 #include "delalloc-space.h"
 #include "block-group.h"
+#include "backref.h"
 
 /*
  * Relocation overview
@@ -652,48 +653,6 @@ static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info,
 	return btrfs_get_fs_root(fs_info, &key, false);
 }
 
-static noinline_for_stack
-int find_inline_backref(struct extent_buffer *leaf, int slot,
-			unsigned long *ptr, unsigned long *end)
-{
-	struct btrfs_key key;
-	struct btrfs_extent_item *ei;
-	struct btrfs_tree_block_info *bi;
-	u32 item_size;
-
-	btrfs_item_key_to_cpu(leaf, &key, slot);
-
-	item_size = btrfs_item_size_nr(leaf, slot);
-	if (item_size < sizeof(*ei)) {
-		btrfs_print_v0_err(leaf->fs_info);
-		btrfs_handle_fs_error(leaf->fs_info, -EINVAL, NULL);
-		return 1;
-	}
-	ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
-	WARN_ON(!(btrfs_extent_flags(leaf, ei) &
-		  BTRFS_EXTENT_FLAG_TREE_BLOCK));
-
-	if (key.type == BTRFS_EXTENT_ITEM_KEY &&
-	    item_size <= sizeof(*ei) + sizeof(*bi)) {
-		WARN_ON(item_size < sizeof(*ei) + sizeof(*bi));
-		return 1;
-	}
-	if (key.type == BTRFS_METADATA_ITEM_KEY &&
-	    item_size <= sizeof(*ei)) {
-		WARN_ON(item_size < sizeof(*ei));
-		return 1;
-	}
-
-	if (key.type == BTRFS_EXTENT_ITEM_KEY) {
-		bi = (struct btrfs_tree_block_info *)(ei + 1);
-		*ptr = (unsigned long)(bi + 1);
-	} else {
-		*ptr = (unsigned long)(ei + 1);
-	}
-	*end = (unsigned long)ei + item_size;
-	return 0;
-}
-
 /*
  * build backref tree for a given tree block. root of the backref tree
  * corresponds the tree block, leaves of the backref tree correspond
@@ -713,10 +672,9 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 					struct btrfs_key *node_key,
 					int level, u64 bytenr)
 {
+	struct btrfs_backref_iter *iter;
 	struct backref_cache *cache = &rc->backref_cache;
-	struct btrfs_path *path1; /* For searching extent root */
-	struct btrfs_path *path2; /* For searching parent of TREE_BLOCK_REF */
-	struct extent_buffer *eb;
+	struct btrfs_path *path; /* For searching parent of TREE_BLOCK_REF */
 	struct btrfs_root *root;
 	struct backref_node *cur;
 	struct backref_node *upper;
@@ -725,9 +683,6 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 	struct backref_node *exist = NULL;
 	struct backref_edge *edge;
 	struct rb_node *rb_node;
-	struct btrfs_key key;
-	unsigned long end;
-	unsigned long ptr;
 	LIST_HEAD(list); /* Pending edge list, upper node needs to be checked */
 	LIST_HEAD(useless);
 	int cowonly;
@@ -735,14 +690,15 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 	int err = 0;
 	bool need_check = true;
 
-	path1 = btrfs_alloc_path();
-	path2 = btrfs_alloc_path();
-	if (!path1 || !path2) {
+	iter = btrfs_backref_iter_alloc(rc->extent_root->fs_info, GFP_NOFS);
+	if (!iter)
+		return ERR_PTR(-ENOMEM);
+	path = btrfs_alloc_path();
+	if (!path) {
 		err = -ENOMEM;
 		goto out;
 	}
-	path1->reada = READA_FORWARD;
-	path2->reada = READA_FORWARD;
+	path->reada = READA_FORWARD;
 
 	node = alloc_backref_node(cache);
 	if (!node) {
@@ -755,25 +711,28 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 	node->lowest = 1;
 	cur = node;
 again:
-	end = 0;
-	ptr = 0;
-	key.objectid = cur->bytenr;
-	key.type = BTRFS_METADATA_ITEM_KEY;
-	key.offset = (u64)-1;
-
-	path1->search_commit_root = 1;
-	path1->skip_locking = 1;
-	ret = btrfs_search_slot(NULL, rc->extent_root, &key, path1,
-				0, 0);
+	ret = btrfs_backref_iter_start(iter, cur->bytenr);
 	if (ret < 0) {
 		err = ret;
 		goto out;
 	}
-	ASSERT(ret);
-	ASSERT(path1->slots[0]);
-
-	path1->slots[0]--;
 
+	/*
+	 * 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) {
+			err = ret;
+			goto out;
+		}
+		/* No extra backref? This means the tree block is corrupted */
+		if (ret > 0) {
+			err = -EUCLEAN;
+			goto out;
+		}
+	}
 	WARN_ON(cur->checked);
 	if (!list_empty(&cur->upper)) {
 		/*
@@ -795,42 +754,20 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 		exist = NULL;
 	}
 
-	while (1) {
-		cond_resched();
-		eb = path1->nodes[0];
-
-		if (ptr >= end) {
-			if (path1->slots[0] >= btrfs_header_nritems(eb)) {
-				ret = btrfs_next_leaf(rc->extent_root, path1);
-				if (ret < 0) {
-					err = ret;
-					goto out;
-				}
-				if (ret > 0)
-					break;
-				eb = path1->nodes[0];
-			}
+	for (; ret == 0; ret = btrfs_backref_iter_next(iter)) {
+		struct extent_buffer *eb;
+		struct btrfs_key key;
+		int type;
 
-			btrfs_item_key_to_cpu(eb, &key, path1->slots[0]);
-			if (key.objectid != cur->bytenr) {
-				WARN_ON(exist);
-				break;
-			}
+		cond_resched();
+		eb = btrfs_backref_get_eb(iter);
 
-			if (key.type == BTRFS_EXTENT_ITEM_KEY ||
-			    key.type == BTRFS_METADATA_ITEM_KEY) {
-				ret = find_inline_backref(eb, path1->slots[0],
-							  &ptr, &end);
-				if (ret)
-					goto next;
-			}
-		}
+		key.objectid = iter->bytenr;
+		if (btrfs_backref_iter_is_inline_ref(iter)) {
+			struct btrfs_extent_inline_ref *iref;
 
-		if (ptr < end) {
 			/* update key for inline back ref */
-			struct btrfs_extent_inline_ref *iref;
-			int type;
-			iref = (struct btrfs_extent_inline_ref *)ptr;
+			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) {
@@ -839,9 +776,9 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 			}
 			key.type = type;
 			key.offset = btrfs_extent_inline_ref_offset(eb, iref);
-
-			WARN_ON(key.type != BTRFS_TREE_BLOCK_REF_KEY &&
-				key.type != BTRFS_SHARED_BLOCK_REF_KEY);
+		} else {
+			key.type = iter->cur_key.type;
+			key.offset = iter->cur_key.offset;
 		}
 
 		/*
@@ -854,7 +791,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 		     (key.type == BTRFS_SHARED_BLOCK_REF_KEY &&
 		      exist->bytenr == key.offset))) {
 			exist = NULL;
-			goto next;
+			continue;
 		}
 
 		/* SHARED_BLOCK_REF means key.offset is the parent bytenr */
@@ -900,7 +837,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 			edge->node[LOWER] = cur;
 			edge->node[UPPER] = upper;
 
-			goto next;
+			continue;
 		} else if (unlikely(key.type == BTRFS_EXTENT_REF_V0_KEY)) {
 			err = -EINVAL;
 			btrfs_print_v0_err(rc->extent_root->fs_info);
@@ -908,7 +845,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 					      NULL);
 			goto out;
 		} else if (key.type != BTRFS_TREE_BLOCK_REF_KEY) {
-			goto next;
+			continue;
 		}
 
 		/*
@@ -941,21 +878,21 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 		level = cur->level + 1;
 
 		/* Search the tree to find parent blocks referring the block. */
-		path2->search_commit_root = 1;
-		path2->skip_locking = 1;
-		path2->lowest_level = level;
-		ret = btrfs_search_slot(NULL, root, node_key, path2, 0, 0);
-		path2->lowest_level = 0;
+		path->search_commit_root = 1;
+		path->skip_locking = 1;
+		path->lowest_level = level;
+		ret = btrfs_search_slot(NULL, root, node_key, path, 0, 0);
+		path->lowest_level = 0;
 		if (ret < 0) {
 			btrfs_put_root(root);
 			err = ret;
 			goto out;
 		}
-		if (ret > 0 && path2->slots[level] > 0)
-			path2->slots[level]--;
+		if (ret > 0 && path->slots[level] > 0)
+			path->slots[level]--;
 
-		eb = path2->nodes[level];
-		if (btrfs_node_blockptr(eb, path2->slots[level]) !=
+		eb = path->nodes[level];
+		if (btrfs_node_blockptr(eb, path->slots[level]) !=
 		    cur->bytenr) {
 			btrfs_err(root->fs_info,
 	"couldn't find block (%llu) (level %d) in tree (%llu) with key (%llu %u %llu)",
@@ -972,7 +909,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 
 		/* Add all nodes and edges in the path */
 		for (; level < BTRFS_MAX_LEVEL; level++) {
-			if (!path2->nodes[level]) {
+			if (!path->nodes[level]) {
 				ASSERT(btrfs_root_bytenr(&root->root_item) ==
 				       lower->bytenr);
 				if (should_ignore_root(root)) {
@@ -991,7 +928,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 				goto out;
 			}
 
-			eb = path2->nodes[level];
+			eb = path->nodes[level];
 			rb_node = tree_search(&cache->rb_root, eb->start);
 			if (!rb_node) {
 				upper = alloc_backref_node(cache);
@@ -1051,20 +988,14 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 			lower = upper;
 			upper = NULL;
 		}
-		btrfs_release_path(path2);
-next:
-		if (ptr < end) {
-			ptr += btrfs_extent_inline_ref_size(key.type);
-			if (ptr >= end) {
-				WARN_ON(ptr > end);
-				ptr = 0;
-				end = 0;
-			}
-		}
-		if (ptr >= end)
-			path1->slots[0]++;
+		btrfs_release_path(path);
+	}
+	if (ret < 0) {
+		err = ret;
+		goto out;
 	}
-	btrfs_release_path(path1);
+	ret = 0;
+	btrfs_backref_iter_release(iter);
 
 	cur->checked = 1;
 	WARN_ON(exist);
@@ -1182,8 +1113,8 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 		}
 	}
 out:
-	btrfs_free_path(path1);
-	btrfs_free_path(path2);
+	btrfs_backref_iter_free(iter);
+	btrfs_free_path(path);
 	if (err) {
 		while (!list_empty(&useless)) {
 			lower = list_entry(useless.next,
Signature · 1 line
2.25.1
author
#9 lore raw

PATCH v2 4/10 btrfs: relocation: Rename mark_block_processed() and __mark_block_processed()

In reply to Qu Wenruo

These two functions are weirdly named, mark_block_processed() in fact just mark a range dirty unconditionally, while __mark_block_processed() does extra check before doing the marking.

This patch will open code old mark_block_processed, and rename __mark_block_processed() to remove the "__" prefix.

Since we're here, also kill the forward declaration, which could also kill in_block_group() with in_range() macro.

---
 fs/btrfs/relocation.c | 55 +++++++++++++++++--------------------------
 1 file changed, 21 insertions(+), 34 deletions(-)
fs/btrfs/relocation.c +21 -34
index 490d684002f9..d1e1d613ab98 100644
@@ -236,8 +236,21 @@ struct reloc_control {
 
 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);
+
+static void mark_block_processed(struct reloc_control *rc,
+				 struct backref_node *node)
+{
+	u32 blocksize;
+	if (node->level == 0 ||
+	    in_range(node->bytenr, rc->block_group->start,
+		     rc->block_group->length)) {
+		blocksize = rc->extent_root->fs_info->nodesize;
+		set_extent_bits(&rc->processed_blocks, node->bytenr,
+				node->bytenr + blocksize - 1, EXTENT_DIRTY);
+	}
+	node->processed = 1;
+}
+
 
 static void mapping_tree_init(struct mapping_tree *tree)
 {
@@ -1103,7 +1116,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 			if (list_empty(&lower->upper))
 				list_add(&lower->list, &useless);
 		}
-		__mark_block_processed(rc, upper);
+		mark_block_processed(rc, upper);
 		if (upper->level > 0) {
 			list_add(&upper->list, &cache->detached);
 			upper->detached = 1;
@@ -1569,14 +1582,6 @@ static struct inode *find_next_inode(struct btrfs_root *root, u64 objectid)
 	return NULL;
 }
 
-static int in_block_group(u64 bytenr, struct btrfs_block_group *block_group)
-{
-	if (bytenr >= block_group->start &&
-	    bytenr < block_group->start + block_group->length)
-		return 1;
-	return 0;
-}
-
 /*
  * get new location of data
  */
@@ -1674,7 +1679,8 @@ int replace_file_extents(struct btrfs_trans_handle *trans,
 		num_bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
 		if (bytenr == 0)
 			continue;
-		if (!in_block_group(bytenr, rc->block_group))
+		if (!in_range(bytenr, rc->block_group->start,
+			      rc->block_group->length))
 			continue;
 
 		/*
@@ -2604,7 +2610,7 @@ struct btrfs_root *select_reloc_root(struct btrfs_trans_handle *trans,
 			ASSERT(next->root);
 			list_add_tail(&next->list,
 				      &rc->backref_cache.changed);
-			__mark_block_processed(rc, next);
+			mark_block_processed(rc, next);
 			break;
 		}
 
@@ -2954,25 +2960,6 @@ static int finish_pending_nodes(struct btrfs_trans_handle *trans,
 	return err;
 }
 
-static void mark_block_processed(struct reloc_control *rc,
-				 u64 bytenr, u32 blocksize)
-{
-	set_extent_bits(&rc->processed_blocks, bytenr, bytenr + blocksize - 1,
-			EXTENT_DIRTY);
-}
-
-static void __mark_block_processed(struct reloc_control *rc,
-				   struct backref_node *node)
-{
-	u32 blocksize;
-	if (node->level == 0 ||
-	    in_block_group(node->bytenr, rc->block_group)) {
-		blocksize = rc->extent_root->fs_info->nodesize;
-		mark_block_processed(rc, node->bytenr, blocksize);
-	}
-	node->processed = 1;
-}
-
 /*
  * mark a block and all blocks directly/indirectly reference the block
  * as processed.
@@ -2991,7 +2978,7 @@ static void update_processed_blocks(struct reloc_control *rc,
 			if (next->processed)
 				break;
 
-			__mark_block_processed(rc, next);
+			mark_block_processed(rc, next);
 
 			if (list_empty(&next->upper))
 				break;
@@ -4743,7 +4730,7 @@ int btrfs_reloc_cow_block(struct btrfs_trans_handle *trans,
 		}
 
 		if (first_cow)
-			__mark_block_processed(rc, node);
+			mark_block_processed(rc, node);
 
 		if (first_cow && level > 0)
 			rc->nodes_relocated += buf->len;
Signature · 1 line
2.25.1
Reviewed-by on v2 4/10
#10 lore raw

Re: [PATCH v2 04/10] btrfs: relocation: Rename mark_block_processed() and __mark_block_processed()

Quoted 11 lines · Qu Wenruo

These two functions are weirdly named, mark_block_processed() in fact just mark a range dirty unconditionally, while __mark_block_processed() does extra check before doing the marking.

This patch will open code old mark_block_processed, and rename __mark_block_processed() to remove the "__" prefix.

Since we're here, also kill the forward declaration, which could also kill in_block_group() with in_range() macro.

author
#11 lore raw

PATCH v2 5/10 btrfs: relocation: Refactor tree backref processing into its own function

In reply to Qu Wenruo

build_backref_tree() function is painfully long, as it has 3 big parts:
- Tree backref handling
- Weaving backref nodes
- Useless nodes pruning

This patch will move the tree backref handling into its own function, handle_one_tree_backref().

And inside that function, the main works are determined by the backref key:
- BTRFS_SHARED_BLOCK_REF_KEY
We know the parent node bytenr directly.
If the parent is cached, or it's root, call it a day.
If the parent is not cached, add it pending list.

- BTRFS_TREE_BLOCK_REF_KEY
The most complex work.
We need to grab the fs root, do a tree search to locate all its parent nodes, weaving all needed edges, and put all uncached edges to pending edge list.

---
 fs/btrfs/relocation.c | 395 +++++++++++++++++++++---------------------
 1 file changed, 202 insertions(+), 193 deletions(-)
fs/btrfs/relocation.c +202 -193
index d1e1d613ab98..04416489d87a 100644
@@ -666,6 +666,206 @@ 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,
+				   struct list_head *useless_node,
+				   struct list_head *pending_edge,
+				   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 backref_node *upper;
+	struct backref_node *lower;
+	struct backref_edge *edge;
+	struct extent_buffer *eb;
+	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) {
+			root = find_reloc_root(rc, cur->bytenr);
+			if (WARN_ON(!root))
+				return -ENOENT;
+			cur->root = root;
+			return 0;
+		}
+
+		edge = alloc_backref_edge(cache);
+		if (!edge)
+			return -ENOMEM;
+
+		rb_node = tree_search(&cache->rb_root, ref_key->offset);
+		if (!rb_node) {
+			/* Parent node not yet cached */
+			upper = alloc_backref_node(cache);
+			if (!upper) {
+				free_backref_edge(cache, edge);
+				return -ENOMEM;
+			}
+			upper->bytenr = ref_key->offset;
+			upper->level = cur->level + 1;
+
+			/*
+			 *  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]);
+		}
+		list_add_tail(&edge->list[LOWER], &cur->upper);
+		edge->node[LOWER] = cur;
+		edge->node[UPPER] = upper;
+		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 = read_fs_root(fs_info, ref_key->offset);
+	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_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_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 = tree_search(&cache->rb_root, eb->start);
+		if (!rb_node) {
+			upper = alloc_backref_node(cache);
+			if (!upper) {
+				btrfs_put_root(root);
+				free_backref_edge(cache, edge);
+				ret = -ENOMEM;
+				goto out;
+			}
+			upper->bytenr = eb->start;
+			upper->owner = btrfs_header_owner(eb);
+			upper->level = lower->level + 1;
+			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);
+		}
+		list_add_tail(&edge->list[LOWER], &lower->upper);
+		edge->node[LOWER] = lower;
+		edge->node[UPPER] = upper;
+
+		if (rb_node) {
+			btrfs_put_root(root);
+			break;
+		}
+		lower = upper;
+		upper = NULL;
+	}
+out:
+	btrfs_release_path(path);
+	return ret;
+}
+
 /*
  * build backref tree for a given tree block. root of the backref tree
  * corresponds the tree block, leaves of the backref tree correspond
@@ -688,7 +888,6 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 	struct btrfs_backref_iter *iter;
 	struct backref_cache *cache = &rc->backref_cache;
 	struct btrfs_path *path; /* For searching parent of TREE_BLOCK_REF */
-	struct btrfs_root *root;
 	struct backref_node *cur;
 	struct backref_node *upper;
 	struct backref_node *lower;
@@ -701,7 +900,6 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 	int cowonly;
 	int ret;
 	int err = 0;
-	bool need_check = true;
 
 	iter = btrfs_backref_iter_alloc(rc->extent_root->fs_info, GFP_NOFS);
 	if (!iter)
@@ -807,201 +1005,12 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 			continue;
 		}
 
-		/* SHARED_BLOCK_REF means key.offset is the parent bytenr */
-		if (key.type == BTRFS_SHARED_BLOCK_REF_KEY) {
-			if (key.objectid == key.offset) {
-				/*
-				 * Only root blocks of reloc trees use backref
-				 * pointing to itself.
-				 */
-				root = find_reloc_root(rc, cur->bytenr);
-				ASSERT(root);
-				cur->root = root;
-				break;
-			}
-
-			edge = alloc_backref_edge(cache);
-			if (!edge) {
-				err = -ENOMEM;
-				goto out;
-			}
-			rb_node = tree_search(&cache->rb_root, key.offset);
-			if (!rb_node) {
-				upper = alloc_backref_node(cache);
-				if (!upper) {
-					free_backref_edge(cache, edge);
-					err = -ENOMEM;
-					goto out;
-				}
-				upper->bytenr = key.offset;
-				upper->level = cur->level + 1;
-				/*
-				 *  backrefs for the upper level block isn't
-				 *  cached, add the block to pending list
-				 */
-				list_add_tail(&edge->list[UPPER], &list);
-			} else {
-				upper = rb_entry(rb_node, struct backref_node,
-						 rb_node);
-				ASSERT(upper->checked);
-				INIT_LIST_HEAD(&edge->list[UPPER]);
-			}
-			list_add_tail(&edge->list[LOWER], &cur->upper);
-			edge->node[LOWER] = cur;
-			edge->node[UPPER] = upper;
-
-			continue;
-		} else if (unlikely(key.type == BTRFS_EXTENT_REF_V0_KEY)) {
-			err = -EINVAL;
-			btrfs_print_v0_err(rc->extent_root->fs_info);
-			btrfs_handle_fs_error(rc->extent_root->fs_info, err,
-					      NULL);
-			goto out;
-		} else if (key.type != BTRFS_TREE_BLOCK_REF_KEY) {
-			continue;
-		}
-
-		/*
-		 * key.type == BTRFS_TREE_BLOCK_REF_KEY, inline ref offset
-		 * means the root objectid. We need to search the tree to get
-		 * its parent bytenr.
-		 */
-		root = read_fs_root(rc->extent_root->fs_info, key.offset);
-		if (IS_ERR(root)) {
-			err = PTR_ERR(root);
-			goto out;
-		}
-
-		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_root(root)) {
-				btrfs_put_root(root);
-				list_add(&cur->list, &useless);
-			} else {
-				cur->root = root;
-			}
-			break;
-		}
-
-		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, node_key, path, 0, 0);
-		path->lowest_level = 0;
+		ret = handle_one_tree_backref(rc, &useless, &list, path, &key,
+					      node_key, cur);
 		if (ret < 0) {
-			btrfs_put_root(root);
 			err = ret;
 			goto out;
 		}
-		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(root->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,
-				  node_key->objectid, node_key->type,
-				  node_key->offset);
-			btrfs_put_root(root);
-			err = -ENOENT;
-			goto out;
-		}
-		lower = cur;
-		need_check = true;
-
-		/* 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_root(root)) {
-					btrfs_put_root(root);
-					list_add(&lower->list, &useless);
-				} else {
-					lower->root = root;
-				}
-				break;
-			}
-
-			edge = alloc_backref_edge(cache);
-			if (!edge) {
-				btrfs_put_root(root);
-				err = -ENOMEM;
-				goto out;
-			}
-
-			eb = path->nodes[level];
-			rb_node = tree_search(&cache->rb_root, eb->start);
-			if (!rb_node) {
-				upper = alloc_backref_node(cache);
-				if (!upper) {
-					btrfs_put_root(root);
-					free_backref_edge(cache, edge);
-					err = -ENOMEM;
-					goto out;
-				}
-				upper->bytenr = eb->start;
-				upper->owner = btrfs_header_owner(eb);
-				upper->level = lower->level + 1;
-				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],
-						      &list);
-				} 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);
-			}
-			list_add_tail(&edge->list[LOWER], &lower->upper);
-			edge->node[LOWER] = lower;
-			edge->node[UPPER] = upper;
-
-			if (rb_node) {
-				btrfs_put_root(root);
-				break;
-			}
-			lower = upper;
-			upper = NULL;
-		}
-		btrfs_release_path(path);
 	}
 	if (ret < 0) {
 		err = ret;
Signature · 1 line
2.25.1
#12 lore raw

Re: [PATCH v2 05/10] btrfs: relocation: Refactor tree backref processing into its own function

Quoted 4 lines · Qu Wenruo

build_backref_tree() function is painfully long, as it has 3 big parts:
- Tree backref handling
- Weaving backref nodes
- Useless nodes pruning

So this is the first patch that mentions the 'useless' nodes. This seems like a misnomer or confusing at best but I haven't read enough code to see if it's really the right name.

Also the term 'weaving', that seems to be added by you. Did you mean splicing or merging?

#13 lore raw

Re: [PATCH v2 05/10] btrfs: relocation: Refactor tree backref processing into its own function

Quoted 9 lines · David Sterba
Quoted 4 lines · Qu Wenruo

build_backref_tree() function is painfully long, as it has 3 big parts:
- Tree backref handling
- Weaving backref nodes
- Useless nodes pruning

So this is the first patch that mentions the 'useless' nodes. This seems like a misnomer or confusing at best but I haven't read enough code to see if it's really the right name.

The 'useless' is from the original code, there is a list called 'useless'.

It's not that useless, those nodes are just ignored, but still cached to prevent extra lookup.

Hopes there would be a better name.

Quoted 4 lines

Also the term 'weaving', that seems to be added by you. Did you mean splicing or merging?

It's complex, but definitely not splicing or merge.

The overall workflow looks like this:

1) Iteration works build a map like this: (start point is X)

      A       B
       ^     ^
        \   /
          C
          ^
          |
          X

At this stage, it's single directional, means we can only go X->C, C->A, C->B

2) Weaving part makes the map bi-directional

      A       B
       ^     ^
        \   /
         v v
          C
          ^
          |
          v
          X

That's the weaving part.
Any better naming is welcomed.

Thanks,
Qu

#14 lore raw

Re: [PATCH v2 05/10] btrfs: relocation: Refactor tree backref processing into its own function

In reply to Qu Wenruo
Quoted 31 lines · Qu Wenruo

build_backref_tree() function is painfully long, as it has 3 big parts:
- Tree backref handling
- Weaving backref nodes
- Useless nodes pruning

This patch will move the tree backref handling into its own function, handle_one_tree_backref().

And inside that function, the main works are determined by the backref key:
- BTRFS_SHARED_BLOCK_REF_KEY
We know the parent node bytenr directly.
If the parent is cached, or it's root, call it a day.
If the parent is not cached, add it pending list.

- BTRFS_TREE_BLOCK_REF_KEY
The most complex work.
We need to grab the fs root, do a tree search to locate all its parent nodes, weaving all needed edges, and put all uncached edges to pending edge list.

---
 fs/btrfs/relocation.c | 395 +++++++++++++++++++++---------------------
 1 file changed, 202 insertions(+), 193 deletions(-)
fs/btrfs/relocation.c +0 -0
index d1e1d613ab98..04416489d87a 100644

fs/btrfs/relocation.c static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info, · line 675

Quoted 10 lines
fs/btrfs/relocation.c +7 -0
@@ -666,6 +666,206 @@ 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,
+				   struct list_head *useless_node,
+				   struct list_head *pending_edge,
+				   struct btrfs_path *path,
+				   struct btrfs_key *ref_key,
+				   struct btrfs_key *tree_key,
+				   struct backref_node *cur)

That function has 7 parameters and while @rc and @path are somewhat self-explanatory others are not. Also it's really doing 2 distinct things which, in my opinion, would be much better split across 2 functions - 1 handling BTRFS_SHARED_BLOCK_REF_KEY and the other handling BTRFS_TREE_BLOCK_REF_KEY. For example the @tree_key,@useless_node and @path are not used in BTRFS_SHARED_BLOCK_REF_KEY case. You'd have two functions named:

handle_(in)?direct_tree_backref

One will take only 4 parameters the other will have to, unfortunately, take all 7.

#15 lore raw

Re: [PATCH v2 05/10] btrfs: relocation: Refactor tree backref processing into its own function

Quoted 37 lines · Nikolay Borisov
Quoted 34 lines · Qu Wenruo

build_backref_tree() function is painfully long, as it has 3 big parts:
- Tree backref handling
- Weaving backref nodes
- Useless nodes pruning

This patch will move the tree backref handling into its own function, handle_one_tree_backref().

And inside that function, the main works are determined by the backref key:
- BTRFS_SHARED_BLOCK_REF_KEY
We know the parent node bytenr directly.
If the parent is cached, or it's root, call it a day.
If the parent is not cached, add it pending list.

- BTRFS_TREE_BLOCK_REF_KEY
The most complex work.
We need to grab the fs root, do a tree search to locate all its parent nodes, weaving all needed edges, and put all uncached edges to pending edge list.

---
 fs/btrfs/relocation.c | 395 +++++++++++++++++++++---------------------
 1 file changed, 202 insertions(+), 193 deletions(-)
fs/btrfs/relocation.c +0 -0
index d1e1d613ab98..04416489d87a 100644
@@ -666,6 +666,206 @@ static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info,
 	return btrfs_get_fs_root(fs_info, &key, false);
 }
 
Quoted 10 lines

fs/btrfs/relocation.c static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info, · line 675

Quoted 7 lines
fs/btrfs/relocation.c +7 -0
+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,
+				   struct backref_node *cur)

That function has 7 parameters and while @rc and @path are somewhat self-explanatory others are not.

That's exactly what I'm fixing in the 2nd patchset.
To kill 2 parameters by moving @useless_node and @pending_edge into backref_cache.

Since you're complaining about this, it looks like I'd better put that patch earlier.

Quoted 7 lines

Also it's really doing 2 distinct
things which, in my opinion, would be much better split across 2 functions - 1 handling BTRFS_SHARED_BLOCK_REF_KEY and the other handling BTRFS_TREE_BLOCK_REF_KEY. For example the @tree_key,@useless_node and @path are not used in BTRFS_SHARED_BLOCK_REF_KEY case. You'd have two functions named:

Quoted 5 lines

handle_(in)?direct_tree_backref

One will take only 4 parameters the other will have to, unfortunately, take all 7.

That looks reasonable.

I'll split them into two functions, and move the two lists into backref_cache in next version.

Thanks,
Qu

author
#16 lore raw

PATCH v2 6/10 btrfs: relocation: Use wrapper to replace open-coded edge linking

In reply to Qu Wenruo

Since backref_edge is used to connect upper and lower backref nodes, and need to access both nodes, some code can look pretty nasty:

		list_add_tail(&edge->list[LOWER], &cur->upper);

The above code will link @cur to the LOWER side of the edge, while both "LOWER" and "upper" words show up.
This can sometimes be very confusing for reader to grasp.

This patch introduce a new wrapper, link_backref_edge(), to handle the linking behavior.
Which also has extra ASSERT() to ensure caller won't pass wrong nodes in.

Also, this updates the comment of related lists of backref_node and backref_edge, to make it more clear that each list points to what.

---
 fs/btrfs/relocation.c | 53 ++++++++++++++++++++++++++++++-------------
 1 file changed, 37 insertions(+), 16 deletions(-)
fs/btrfs/relocation.c +37 -16
index 04416489d87a..c76849409c81 100644
@@ -91,10 +91,12 @@ struct backref_node {
 	u64 owner;
 	/* link to pending, changed or detached list */
 	struct list_head list;
-	/* list of upper level blocks reference this block */
+
+	/* List of upper level edges, which links this node to its parent(s) */
 	struct list_head upper;
-	/* list of child blocks in the cache */
+	/* 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 */
@@ -123,17 +125,26 @@ struct backref_node {
 	unsigned int detached:1;
 };
 
+#define LOWER	0
+#define UPPER	1
+#define RELOCATION_RESERVED_NODES	256
 /*
- * present a block pointer in the backref cache
+ * 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];
 };
 
-#define LOWER	0
-#define UPPER	1
-#define RELOCATION_RESERVED_NODES	256
 
 struct backref_cache {
 	/* red black tree of all backref nodes in the cache */
@@ -332,6 +343,22 @@ static struct backref_edge *alloc_backref_edge(struct backref_cache *cache)
 	return edge;
 }
 
+#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)
 {
@@ -729,9 +756,7 @@ static int handle_one_tree_backref(struct reloc_control *rc,
 			ASSERT(upper->checked);
 			INIT_LIST_HEAD(&edge->list[UPPER]);
 		}
-		list_add_tail(&edge->list[LOWER], &cur->upper);
-		edge->node[LOWER] = cur;
-		edge->node[UPPER] = upper;
+		link_backref_edge(edge, cur, upper, LINK_LOWER);
 		return 0;
 	}
 	/*
@@ -850,9 +875,7 @@ static int handle_one_tree_backref(struct reloc_control *rc,
 			if (!upper->owner)
 				upper->owner = btrfs_header_owner(eb);
 		}
-		list_add_tail(&edge->list[LOWER], &lower->upper);
-		edge->node[LOWER] = lower;
-		edge->node[UPPER] = upper;
+		link_backref_edge(edge, lower, upper, LINK_LOWER);
 
 		if (rb_node) {
 			btrfs_put_root(root);
@@ -1246,10 +1269,8 @@ static int clone_backref_node(struct btrfs_trans_handle *trans,
 			if (!new_edge)
 				goto fail;
 
-			new_edge->node[UPPER] = new_node;
-			new_edge->node[LOWER] = edge->node[LOWER];
-			list_add_tail(&new_edge->list[UPPER],
-				      &new_node->lower);
+			link_backref_edge(new_edge, edge->node[LOWER], new_node,
+					  LINK_UPPER);
 		}
 	} else {
 		list_add_tail(&new_node->lower, &cache->leaves);
Signature · 1 line
2.25.1
#17 lore raw

Re: [PATCH v2 06/10] btrfs: relocation: Use wrapper to replace open-coded edge linking

Quoted 73 lines · Qu Wenruo

Since backref_edge is used to connect upper and lower backref nodes, and need to access both nodes, some code can look pretty nasty:

		list_add_tail(&edge->list[LOWER], &cur->upper);

The above code will link @cur to the LOWER side of the edge, while both "LOWER" and "upper" words show up.
This can sometimes be very confusing for reader to grasp.

This patch introduce a new wrapper, link_backref_edge(), to handle the linking behavior.
Which also has extra ASSERT() to ensure caller won't pass wrong nodes in.

Also, this updates the comment of related lists of backref_node and backref_edge, to make it more clear that each list points to what.

---
 fs/btrfs/relocation.c | 53 ++++++++++++++++++++++++++++++-------------
 1 file changed, 37 insertions(+), 16 deletions(-)
fs/btrfs/relocation.c +17 -6
index 04416489d87a..c76849409c81 100644
@@ -91,10 +91,12 @@ struct backref_node {
 	u64 owner;
 	/* link to pending, changed or detached list */
 	struct list_head list;
-	/* list of upper level blocks reference this block */
+
+	/* List of upper level edges, which links this node to its parent(s) */
 	struct list_head upper;
-	/* list of child blocks in the cache */
+	/* 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 */
@@ -123,17 +125,26 @@ struct backref_node {
 	unsigned int detached:1;
 };
 
+#define LOWER	0
+#define UPPER	1
+#define RELOCATION_RESERVED_NODES	256
 /*
- * present a block pointer in the backref cache
+ * 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];
 };
 
-#define LOWER	0
-#define UPPER	1
-#define RELOCATION_RESERVED_NODES	256
 
 struct backref_cache {
 	/* red black tree of all backref nodes in the cache */

fs/btrfs/relocation.c static struct backref_edge *alloc_backref_edge(struct backref_cache *cache) · line 351

Quoted 9 lines
fs/btrfs/relocation.c +6 -0
@@ -332,6 +343,22 @@ static struct backref_edge *alloc_backref_edge(struct backref_cache *cache)
 	return edge;
 }
 
+#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)

Again not a static inline, but plain static function.

Quoted 9 lines
fs/btrfs/relocation.c +9 -0
+{
+	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);
+}
#18 lore raw

Re: [PATCH v2 06/10] btrfs: relocation: Use wrapper to replace open-coded edge linking

Quoted 77 lines · David Sterba
Quoted 76 lines · Qu Wenruo

Since backref_edge is used to connect upper and lower backref nodes, and need to access both nodes, some code can look pretty nasty:

		list_add_tail(&edge->list[LOWER], &cur->upper);

The above code will link @cur to the LOWER side of the edge, while both "LOWER" and "upper" words show up.
This can sometimes be very confusing for reader to grasp.

This patch introduce a new wrapper, link_backref_edge(), to handle the linking behavior.
Which also has extra ASSERT() to ensure caller won't pass wrong nodes in.

Also, this updates the comment of related lists of backref_node and backref_edge, to make it more clear that each list points to what.

---
 fs/btrfs/relocation.c | 53 ++++++++++++++++++++++++++++++-------------
 1 file changed, 37 insertions(+), 16 deletions(-)
fs/btrfs/relocation.c +17 -6
index 04416489d87a..c76849409c81 100644
@@ -91,10 +91,12 @@ struct backref_node {
 	u64 owner;
 	/* link to pending, changed or detached list */
 	struct list_head list;
-	/* list of upper level blocks reference this block */
+
+	/* List of upper level edges, which links this node to its parent(s) */
 	struct list_head upper;
-	/* list of child blocks in the cache */
+	/* 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 */
@@ -123,17 +125,26 @@ struct backref_node {
 	unsigned int detached:1;
 };
 
+#define LOWER	0
+#define UPPER	1
+#define RELOCATION_RESERVED_NODES	256
 /*
- * present a block pointer in the backref cache
+ * 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];
 };
 
-#define LOWER	0
-#define UPPER	1
-#define RELOCATION_RESERVED_NODES	256
 
 struct backref_cache {
 	/* red black tree of all backref nodes in the cache */
@@ -332,6 +343,22 @@ static struct backref_edge *alloc_backref_edge(struct backref_cache *cache)
 	return edge;
 }
 
Quoted 8 lines

fs/btrfs/relocation.c static struct backref_edge *alloc_backref_edge(struct backref_cache *cache) · line 351

Quoted 6 lines
fs/btrfs/relocation.c +6 -0
+#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)

Again not a static inline, but plain static function.

Oh, I mixed my further plan with my current code...

It would be moved to backref.h, which have to be static inline.

Will remove the inline prefix in next version.

Thanks,
Qu

Quoted 10 lines
Quoted 10 lines
fs/btrfs/relocation.c +9 -0
+{
+	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);
+}
Reviewed-by on v2 6/10
#19 lore raw

Re: [PATCH v2 06/10] btrfs: relocation: Use wrapper to replace open-coded edge linking

In reply to Qu Wenruo
Quoted 14 lines · Qu Wenruo

Since backref_edge is used to connect upper and lower backref nodes, and need to access both nodes, some code can look pretty nasty:

		list_add_tail(&edge->list[LOWER], &cur->upper);

The above code will link @cur to the LOWER side of the edge, while both "LOWER" and "upper" words show up.
This can sometimes be very confusing for reader to grasp.

This patch introduce a new wrapper, link_backref_edge(), to handle the linking behavior.
Which also has extra ASSERT() to ensure caller won't pass wrong nodes in.

Quoted 4 lines

Also, this updates the comment of related lists of backref_node and backref_edge, to make it more clear that each list points to what.

Apart from David's comment I don't have anything else to add and also the code is functionally the same so:

author
#20 lore raw

PATCH v2 7/10 btrfs: relocation: Specify essential members for alloc_backref_node()

In reply to Qu Wenruo

Bytenr and level are essential parameters for backref_node, thus it makes sense to initial them at alloc time.

---
 fs/btrfs/relocation.c | 25 ++++++++++++-------------
 1 file changed, 12 insertions(+), 13 deletions(-)
fs/btrfs/relocation.c +12 -13
index c76849409c81..67a4a61eb86a 100644
@@ -308,10 +308,12 @@ static void backref_cache_cleanup(struct backref_cache *cache)
 	ASSERT(!cache->nr_edges);
 }
 
-static struct backref_node *alloc_backref_node(struct backref_cache *cache)
+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);
@@ -319,6 +321,9 @@ static struct backref_node *alloc_backref_node(struct backref_cache *cache)
 		INIT_LIST_HEAD(&node->lower);
 		RB_CLEAR_NODE(&node->rb_node);
 		cache->nr_nodes++;
+
+		node->level = level;
+		node->bytenr = bytenr;
 	}
 	return node;
 }
@@ -736,13 +741,12 @@ static int handle_one_tree_backref(struct reloc_control *rc,
 		rb_node = tree_search(&cache->rb_root, ref_key->offset);
 		if (!rb_node) {
 			/* Parent node not yet cached */
-			upper = alloc_backref_node(cache);
+			upper = alloc_backref_node(cache, ref_key->offset,
+						   cur->level + 1);
 			if (!upper) {
 				free_backref_edge(cache, edge);
 				return -ENOMEM;
 			}
-			upper->bytenr = ref_key->offset;
-			upper->level = cur->level + 1;
 
 			/*
 			 *  backrefs for the upper level block isn't
@@ -833,16 +837,15 @@ static int handle_one_tree_backref(struct reloc_control *rc,
 		eb = path->nodes[level];
 		rb_node = tree_search(&cache->rb_root, eb->start);
 		if (!rb_node) {
-			upper = alloc_backref_node(cache);
+			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->bytenr = eb->start;
 			upper->owner = btrfs_header_owner(eb);
-			upper->level = lower->level + 1;
 			if (!test_bit(BTRFS_ROOT_REF_COWS, &root->state))
 				upper->cowonly = 1;
 
@@ -934,14 +937,12 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 	}
 	path->reada = READA_FORWARD;
 
-	node = alloc_backref_node(cache);
+	node = alloc_backref_node(cache, bytenr, level);
 	if (!node) {
 		err = -ENOMEM;
 		goto out;
 	}
 
-	node->bytenr = bytenr;
-	node->level = level;
 	node->lowest = 1;
 	cur = node;
 again:
@@ -1252,12 +1253,10 @@ static int clone_backref_node(struct btrfs_trans_handle *trans,
 	if (!node)
 		return 0;
 
-	new_node = alloc_backref_node(cache);
+	new_node = alloc_backref_node(cache, dest->node->start, node->level);
 	if (!new_node)
 		return -ENOMEM;
 
-	new_node->bytenr = dest->node->start;
-	new_node->level = node->level;
 	new_node->lowest = node->lowest;
 	new_node->checked = 1;
 	new_node->root = btrfs_grab_root(dest);
Signature · 1 line
2.25.1
Reviewed-by on v2 7/10
#21 lore raw

Re: [PATCH v2 07/10] btrfs: relocation: Specify essential members for alloc_backref_node()

Quoted 4 lines · Qu Wenruo

Bytenr and level are essential parameters for backref_node, thus it makes sense to initial them at alloc time.

Quoted 23 lines
---
 fs/btrfs/relocation.c | 25 ++++++++++++-------------
 1 file changed, 12 insertions(+), 13 deletions(-)
fs/btrfs/relocation.c +3 -1
index c76849409c81..67a4a61eb86a 100644
@@ -308,10 +308,12 @@ static void backref_cache_cleanup(struct backref_cache *cache)
 	ASSERT(!cache->nr_edges);
 }
 
-static struct backref_node *alloc_backref_node(struct backref_cache *cache)
+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);

fs/btrfs/relocation.c static struct backref_node *alloc_backref_node(struct backref_cache *cache) · line 327

Quoted 7 lines
fs/btrfs/relocation.c +3 -0
@@ -319,6 +321,9 @@ static struct backref_node *alloc_backref_node(struct backref_cache *cache)
 		INIT_LIST_HEAD(&node->lower);
 		RB_CLEAR_NODE(&node->rb_node);
 		cache->nr_nodes++;
+
+		node->level = level;
+		node->bytenr = bytenr;
 	}

nit: One suggestion for this function, feel free to ignore:

What if you do it:
if (!node)
return NULL

and then have the initialization happen with just 1 level of nesting inside the function and not 2. That function is short and easy to understand but it might be a good time to refactor like that. If you think it's redundant then don't bother.

Quoted 2 lines
fs/btrfs/relocation.c +0 -0
 	return node;
 }

<snip>

#22 lore raw

Re: [PATCH v2 07/10] btrfs: relocation: Specify essential members for alloc_backref_node()

Quoted 43 lines · Nikolay Borisov
Quoted 4 lines · Qu Wenruo

Bytenr and level are essential parameters for backref_node, thus it makes sense to initial them at alloc time.

Quoted 23 lines
---
 fs/btrfs/relocation.c | 25 ++++++++++++-------------
 1 file changed, 12 insertions(+), 13 deletions(-)
fs/btrfs/relocation.c +3 -1
index c76849409c81..67a4a61eb86a 100644
@@ -308,10 +308,12 @@ static void backref_cache_cleanup(struct backref_cache *cache)
 	ASSERT(!cache->nr_edges);
 }
 
-static struct backref_node *alloc_backref_node(struct backref_cache *cache)
+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);

fs/btrfs/relocation.c static struct backref_node *alloc_backref_node(struct backref_cache *cache) · line 327

Quoted 7 lines
fs/btrfs/relocation.c +3 -0
@@ -319,6 +321,9 @@ static struct backref_node *alloc_backref_node(struct backref_cache *cache)
 		INIT_LIST_HEAD(&node->lower);
 		RB_CLEAR_NODE(&node->rb_node);
 		cache->nr_nodes++;
+
+		node->level = level;
+		node->bytenr = bytenr;
 	}

nit: One suggestion for this function, feel free to ignore:

Quoted 3 lines

What if you do it:
if (!node)
return NULL

I didn't notice we can do that.

Looks like the style I prefer too.

I'll use that style in next version.

Thanks,
Qu

Quoted 11 lines

and then have the initialization happen with just 1 level of nesting inside the function and not 2. That function is short and easy to understand but it might be a good time to refactor like that. If you think it's redundant then don't bother.

Quoted 2 lines
fs/btrfs/relocation.c +0 -0
 	return node;
 }

<snip>

author
#23 lore raw

PATCH v2 8/10 btrfs: relocation: Remove the open-coded goto loop for breadth-first search

In reply to Qu Wenruo

build_backref_tree() uses "goto again;" to implement a breadth-first search to build backref cache.

This patch will extract most of its work into a wrapper, handle_one_tree_block(), and use a while() loop to implement the same thing.

---
 fs/btrfs/relocation.c | 167 +++++++++++++++++++++++-------------------
 1 file changed, 91 insertions(+), 76 deletions(-)
fs/btrfs/relocation.c +91 -76
index 67a4a61eb86a..26089694b3b5 100644
@@ -892,65 +892,21 @@ static int handle_one_tree_backref(struct reloc_control *rc,
 	return ret;
 }
 
-/*
- * build backref tree for a given tree block. root of the backref tree
- * corresponds the tree block, leaves of the backref tree correspond
- * roots of b-trees that reference the tree block.
- *
- * the basic idea of this function is check backrefs of a given block
- * to find upper level blocks that reference the block, and then check
- * backrefs of these upper level blocks recursively. the recursion stop
- * when tree root is reached or backrefs for the block is cached.
- *
- * NOTE: if we find backrefs for a block are cached, we know backrefs
- * for all upper level blocks that directly/indirectly reference the
- * block are also cached.
- */
-static noinline_for_stack
-struct backref_node *build_backref_tree(struct reloc_control *rc,
-					struct btrfs_key *node_key,
-					int level, u64 bytenr)
+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 btrfs_backref_iter *iter;
-	struct backref_cache *cache = &rc->backref_cache;
-	struct btrfs_path *path; /* For searching parent of TREE_BLOCK_REF */
-	struct backref_node *cur;
-	struct backref_node *upper;
-	struct backref_node *lower;
-	struct backref_node *node = NULL;
-	struct backref_node *exist = 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 cowonly;
+	struct backref_node *exist;
 	int ret;
-	int err = 0;
-
-	iter = btrfs_backref_iter_alloc(rc->extent_root->fs_info, GFP_NOFS);
-	if (!iter)
-		return ERR_PTR(-ENOMEM);
-	path = btrfs_alloc_path();
-	if (!path) {
-		err = -ENOMEM;
-		goto out;
-	}
-	path->reada = READA_FORWARD;
-
-	node = alloc_backref_node(cache, bytenr, level);
-	if (!node) {
-		err = -ENOMEM;
-		goto out;
-	}
 
-	node->lowest = 1;
-	cur = node;
-again:
 	ret = btrfs_backref_iter_start(iter, cur->bytenr);
-	if (ret < 0) {
-		err = ret;
-		goto out;
-	}
+	if (ret < 0)
+		return ret;
 
 	/*
 	 * We skip the first btrfs_tree_block_info, as we don't use the key
@@ -958,13 +914,11 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 	 */
 	if (btrfs_backref_has_tree_block_info(iter)) {
 		ret = btrfs_backref_iter_next(iter);
-		if (ret < 0) {
-			err = ret;
+		if (ret < 0)
 			goto out;
-		}
 		/* No extra backref? This means the tree block is corrupted */
 		if (ret > 0) {
-			err = -EUCLEAN;
+			ret = -EUCLEAN;
 			goto out;
 		}
 	}
@@ -984,7 +938,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 		 * check its backrefs
 		 */
 		if (!exist->checked)
-			list_add_tail(&edge->list[UPPER], &list);
+			list_add_tail(&edge->list[UPPER], pending_edge);
 	} else {
 		exist = NULL;
 	}
@@ -1006,7 +960,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 			type = btrfs_get_extent_inline_ref_type(eb, iref,
 							BTRFS_REF_TYPE_BLOCK);
 			if (type == BTRFS_REF_TYPE_INVALID) {
-				err = -EUCLEAN;
+				ret = -EUCLEAN;
 				goto out;
 			}
 			key.type = type;
@@ -1029,29 +983,90 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 			continue;
 		}
 
-		ret = handle_one_tree_backref(rc, &useless, &list, path, &key,
-					      node_key, cur);
-		if (ret < 0) {
-			err = ret;
+		ret = handle_one_tree_backref(rc, useless_node, pending_edge, path,
+					      &key, node_key, cur);
+		if (ret < 0)
 			goto out;
-		}
 	}
-	if (ret < 0) {
-		err = ret;
+	if (ret < 0)
 		goto out;
-	}
 	ret = 0;
-	btrfs_backref_iter_release(iter);
-
 	cur->checked = 1;
 	WARN_ON(exist);
+out:
+	btrfs_backref_iter_release(iter);
+	return ret;
+}
 
-	/* 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]);
-		list_del_init(&edge->list[UPPER]);
-		cur = edge->node[UPPER];
-		goto again;
+/*
+ * build backref tree for a given tree block. root of the backref tree
+ * corresponds the tree block, leaves of the backref tree correspond
+ * roots of b-trees that reference the tree block.
+ *
+ * the basic idea of this function is check backrefs of a given block
+ * to find upper level blocks that reference the block, and then check
+ * backrefs of these upper level blocks recursively. the recursion stop
+ * when tree root is reached or backrefs for the block is cached.
+ *
+ * NOTE: if we find backrefs for a block are cached, we know backrefs
+ * for all upper level blocks that directly/indirectly reference the
+ * block are also cached.
+ */
+static noinline_for_stack
+struct backref_node *build_backref_tree(struct reloc_control *rc,
+					struct btrfs_key *node_key,
+					int level, u64 bytenr)
+{
+	struct btrfs_backref_iter *iter;
+	struct backref_cache *cache = &rc->backref_cache;
+	struct btrfs_path *path; /* For searching parent of TREE_BLOCK_REF */
+	struct backref_node *cur;
+	struct backref_node *upper;
+	struct backref_node *lower;
+	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 cowonly;
+	int ret;
+	int err = 0;
+
+	iter = btrfs_backref_iter_alloc(rc->extent_root->fs_info, GFP_NOFS);
+	if (!iter)
+		return ERR_PTR(-ENOMEM);
+	path = btrfs_alloc_path();
+	if (!path) {
+		err = -ENOMEM;
+		goto out;
+	}
+	path->reada = READA_FORWARD;
+
+	node = alloc_backref_node(cache, bytenr, level);
+	if (!node) {
+		err = -ENOMEM;
+		goto out;
+	}
+
+	node->lowest = 1;
+	cur = node;
+
+	/* Breadth-first search to build backref cache */
+	while (1) {
+		ret = handle_one_tree_block(rc, &useless, &list, 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]);
+			list_del_init(&edge->list[UPPER]);
+			cur = edge->node[UPPER];
+		} else {
+			break;
+		}
 	}
 
 	/*
Signature · 1 line
2.25.1
#24 lore raw

Re: [PATCH v2 08/10] btrfs: relocation: Remove the open-coded goto loop for breadth-first search

Quoted 188 lines · Qu Wenruo

build_backref_tree() uses "goto again;" to implement a breadth-first search to build backref cache.

This patch will extract most of its work into a wrapper, handle_one_tree_block(), and use a while() loop to implement the same thing.

---
 fs/btrfs/relocation.c | 167 +++++++++++++++++++++++-------------------
 1 file changed, 91 insertions(+), 76 deletions(-)
fs/btrfs/relocation.c +49 -76
index 67a4a61eb86a..26089694b3b5 100644
@@ -892,65 +892,21 @@ static int handle_one_tree_backref(struct reloc_control *rc,
 	return ret;
 }
 
-/*
- * build backref tree for a given tree block. root of the backref tree
- * corresponds the tree block, leaves of the backref tree correspond
- * roots of b-trees that reference the tree block.
- *
- * the basic idea of this function is check backrefs of a given block
- * to find upper level blocks that reference the block, and then check
- * backrefs of these upper level blocks recursively. the recursion stop
- * when tree root is reached or backrefs for the block is cached.
- *
- * NOTE: if we find backrefs for a block are cached, we know backrefs
- * for all upper level blocks that directly/indirectly reference the
- * block are also cached.
- */
-static noinline_for_stack
-struct backref_node *build_backref_tree(struct reloc_control *rc,
-					struct btrfs_key *node_key,
-					int level, u64 bytenr)
+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 btrfs_backref_iter *iter;
-	struct backref_cache *cache = &rc->backref_cache;
-	struct btrfs_path *path; /* For searching parent of TREE_BLOCK_REF */
-	struct backref_node *cur;
-	struct backref_node *upper;
-	struct backref_node *lower;
-	struct backref_node *node = NULL;
-	struct backref_node *exist = 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 cowonly;
+	struct backref_node *exist;
 	int ret;
-	int err = 0;
-
-	iter = btrfs_backref_iter_alloc(rc->extent_root->fs_info, GFP_NOFS);
-	if (!iter)
-		return ERR_PTR(-ENOMEM);
-	path = btrfs_alloc_path();
-	if (!path) {
-		err = -ENOMEM;
-		goto out;
-	}
-	path->reada = READA_FORWARD;
-
-	node = alloc_backref_node(cache, bytenr, level);
-	if (!node) {
-		err = -ENOMEM;
-		goto out;
-	}
 
-	node->lowest = 1;
-	cur = node;
-again:
 	ret = btrfs_backref_iter_start(iter, cur->bytenr);
-	if (ret < 0) {
-		err = ret;
-		goto out;
-	}
+	if (ret < 0)
+		return ret;
 
 	/*
 	 * We skip the first btrfs_tree_block_info, as we don't use the key
@@ -958,13 +914,11 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 	 */
 	if (btrfs_backref_has_tree_block_info(iter)) {
 		ret = btrfs_backref_iter_next(iter);
-		if (ret < 0) {
-			err = ret;
+		if (ret < 0)
 			goto out;
-		}
 		/* No extra backref? This means the tree block is corrupted */
 		if (ret > 0) {
-			err = -EUCLEAN;
+			ret = -EUCLEAN;
 			goto out;
 		}
 	}
@@ -984,7 +938,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 		 * check its backrefs
 		 */
 		if (!exist->checked)
-			list_add_tail(&edge->list[UPPER], &list);
+			list_add_tail(&edge->list[UPPER], pending_edge);
 	} else {
 		exist = NULL;
 	}
@@ -1006,7 +960,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 			type = btrfs_get_extent_inline_ref_type(eb, iref,
 							BTRFS_REF_TYPE_BLOCK);
 			if (type == BTRFS_REF_TYPE_INVALID) {
-				err = -EUCLEAN;
+				ret = -EUCLEAN;
 				goto out;
 			}
 			key.type = type;
@@ -1029,29 +983,90 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 			continue;
 		}
 
-		ret = handle_one_tree_backref(rc, &useless, &list, path, &key,
-					      node_key, cur);
-		if (ret < 0) {
-			err = ret;
+		ret = handle_one_tree_backref(rc, useless_node, pending_edge, path,
+					      &key, node_key, cur);
+		if (ret < 0)
 			goto out;
-		}
 	}
-	if (ret < 0) {
-		err = ret;
+	if (ret < 0)
 		goto out;
-	}
 	ret = 0;
-	btrfs_backref_iter_release(iter);
-
 	cur->checked = 1;
 	WARN_ON(exist);
+out:
+	btrfs_backref_iter_release(iter);
+	return ret;
+}
 
-	/* 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]);
-		list_del_init(&edge->list[UPPER]);
-		cur = edge->node[UPPER];
-		goto again;
+/*
+ * build backref tree for a given tree block. root of the backref tree
+ * corresponds the tree block, leaves of the backref tree correspond
+ * roots of b-trees that reference the tree block.
+ *
+ * the basic idea of this function is check backrefs of a given block
+ * to find upper level blocks that reference the block, and then check
+ * backrefs of these upper level blocks recursively. the recursion stop
+ * when tree root is reached or backrefs for the block is cached.
+ *
+ * NOTE: if we find backrefs for a block are cached, we know backrefs
+ * for all upper level blocks that directly/indirectly reference the
+ * block are also cached.
+ */
+static noinline_for_stack
+struct backref_node *build_backref_tree(struct reloc_control *rc,
+					struct btrfs_key *node_key,
+					int level, u64 bytenr)
+{
+	struct btrfs_backref_iter *iter;
+	struct backref_cache *cache = &rc->backref_cache;
+	struct btrfs_path *path; /* For searching parent of TREE_BLOCK_REF */
+	struct backref_node *cur;
+	struct backref_node *upper;
+	struct backref_node *lower;
+	struct backref_node *node = NULL;
+	struct backref_edge *edge;

fs/btrfs/relocation.c struct backref_node *build_backref_tree(struct reloc_control *rc, · line 1037

Quoted 10 lines
fs/btrfs/relocation.c +10 -0
+	struct rb_node *rb_node;
+	LIST_HEAD(list); /* Pending edge list, upper node needs to be checked */
+	LIST_HEAD(useless);
+	int cowonly;
+	int ret;
+	int err = 0;
+
+	iter = btrfs_backref_iter_alloc(rc->extent_root->fs_info, GFP_NOFS);
+	if (!iter)
+		return ERR_PTR(-ENOMEM);

This iterator can be made private to handle_one_tree_block as I don't see it being used outside of that function.

fs/btrfs/relocation.c struct backref_node *build_backref_tree(struct reloc_control *rc, · line 1042

Quoted 5 lines
fs/btrfs/relocation.c +5 -0
+	path = btrfs_alloc_path();
+	if (!path) {
+		err = -ENOMEM;
+		goto out;
+	}

Same thing with this path. Overall this will reduce the argument to handle_one_tree_block by 2.

Quoted 12 lines
fs/btrfs/relocation.c +12 -0
+	path->reada = READA_FORWARD;
+
+	node = alloc_backref_node(cache, bytenr, level);
+	if (!node) {
+		err = -ENOMEM;
+		goto out;
+	}
+
+	node->lowest = 1;
+	cur = node;
+
+	/* Breadth-first search to build backref cache */

fs/btrfs/relocation.c struct backref_node *build_backref_tree(struct reloc_control *rc, · line 1064

Quoted 10 lines
fs/btrfs/relocation.c +10 -0
+	while (1) {
+		ret = handle_one_tree_block(rc, &useless, &list, 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]);

Use list_first_entry_or_null or it would become:

edge = list_first_entry_or_null();
if (edge) {
list_del_init(&edge->list[UPPER]);
cur = edge->node[UPPER]
} else {
breakl
}

or simply if (!edge)
break;

Also this loop can be rewritten as a do {} while() and it will look:

        /* Breadth-first search to build backref cache */                       
        do {                                                                    
                ret = handle_one_tree_block(rc, &useless, &list, path, iter,    
                                            node_key, cur);                     
                if (ret < 0) {                                                  
                        err = ret;                                              
                        goto out;                                               
                }                                                               
                edge = list_first_entry_or_null(&list, struct backref_edge,     
                                                list[UPPER]);                   
                /* the pending list isn't empty, take the first block to process */
                if (edge) {                                                     
                        list_del_init(&edge->list[UPPER]);                      
                        cur = edge->node[UPPER];                                
                }                                                               
        } while (edge)

IMO this is shorter than the original version and it's very expicit about it's terminating conditions:
a). handle_one_tree_block returns an error
b) list becomes empty.

Alternatively list being empty is really a proxy for "is cur a valid inode". We know it's always valid on the first iteration since it's passed form the caller, subsequent iterations assign cur to edge->node[UPPER] so it could even be

while(cur) {}

In my opinion reducing while(1) loops where it makes sense (as in this case) is preferable.

NB: I've only compile-tested it.

Quoted 9 lines
fs/btrfs/relocation.c +5 -0
+			list_del_init(&edge->list[UPPER]);
+			cur = edge->node[UPPER];
+		} else {
+			break;
+		}
 	}
 
 	/*
#25 lore raw

Re: [PATCH v2 08/10] btrfs: relocation: Remove the open-coded goto loop for breadth-first search

Quoted 1 line · Nikolay Borisov

[...]

Quoted 7 lines

fs/btrfs/relocation.c struct backref_node *build_backref_tree(struct reloc_control *rc, · line 1037

Quoted 5 lines
fs/btrfs/relocation.c +5 -0
+	int err = 0;
+
+	iter = btrfs_backref_iter_alloc(rc->extent_root->fs_info, GFP_NOFS);
+	if (!iter)
+		return ERR_PTR(-ENOMEM);

This iterator can be made private to handle_one_tree_block as I don't see it being used outside of that function.

It's kinda a performance optimization.

Instead of allocating memory for each loop, we allocate the memory just once, and reuse it until the whole backref map for the bytenr is built.

Quoted 8 lines

fs/btrfs/relocation.c struct backref_node *build_backref_tree(struct reloc_control *rc, · line 1042

Quoted 6 lines
fs/btrfs/relocation.c +5 -0
+	path = btrfs_alloc_path();
+	if (!path) {
+		err = -ENOMEM;
+		goto out;
+	}

Same thing with this path. Overall this will reduce the argument to handle_one_tree_block by 2.

Same performance optimization here.

Quoted 26 lines
Quoted 13 lines
fs/btrfs/relocation.c +12 -0
+	path->reada = READA_FORWARD;
+
+	node = alloc_backref_node(cache, bytenr, level);
+	if (!node) {
+		err = -ENOMEM;
+		goto out;
+	}
+
+	node->lowest = 1;
+	cur = node;
+
+	/* Breadth-first search to build backref cache */

fs/btrfs/relocation.c struct backref_node *build_backref_tree(struct reloc_control *rc, · line 1064

Quoted 10 lines
fs/btrfs/relocation.c +10 -0
+	while (1) {
+		ret = handle_one_tree_block(rc, &useless, &list, 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]);

Use list_first_entry_or_null or it would become:

Quoted 7 lines

edge = list_first_entry_or_null();
if (edge) {
list_del_init(&edge->list[UPPER]);
cur = edge->node[UPPER]
} else {
breakl
}

That's an interesting wrapper. Would go that way.

Quoted 5 lines

or simply if (!edge)
break;

Also this loop can be rewritten as a do {} while() and it will look:

Yep, but I'm not sure if such do {} while() loop is preferred. IIRC there are some docs saying to avoid such loop?

If there is no such restriction, I would be pretty happy to go that way.

Thanks,
Qu

Quoted 41 lines
        /* Breadth-first search to build backref cache */
        do {
                ret = handle_one_tree_block(rc, &useless, &list, path, iter,
                                            node_key, cur);
                if (ret < 0) {
                        err = ret;
                        goto out;
                }
                edge = list_first_entry_or_null(&list, struct backref_edge,
                                                list[UPPER]);
                /* the pending list isn't empty, take the first block to process */
                if (edge) {
                        list_del_init(&edge->list[UPPER]);
                        cur = edge->node[UPPER];
                }
        } while (edge)

IMO this is shorter than the original version and it's very expicit about it's terminating conditions:
a). handle_one_tree_block returns an error
b) list becomes empty.

Alternatively list being empty is really a proxy for "is cur a valid inode". We know it's always valid on the first iteration since it's passed form the caller, subsequent iterations assign cur to edge->node[UPPER] so it could even be

while(cur) {}

In my opinion reducing while(1) loops where it makes sense (as in this case) is preferable.

NB: I've only compile-tested it.

Quoted 9 lines
fs/btrfs/relocation.c +5 -0
+			list_del_init(&edge->list[UPPER]);
+			cur = edge->node[UPPER];
+		} else {
+			break;
+		}
 	}
 
 	/*
#26 lore raw

Re: [PATCH v2 08/10] btrfs: relocation: Remove the open-coded goto loop for breadth-first search

Quoted 26 lines · Qu Wenruo
Quoted 1 line · Nikolay Borisov

[...]

Quoted 7 lines

fs/btrfs/relocation.c struct backref_node *build_backref_tree(struct reloc_control *rc, · line 1037

Quoted 5 lines
fs/btrfs/relocation.c +5 -0
+	int err = 0;
+
+	iter = btrfs_backref_iter_alloc(rc->extent_root->fs_info, GFP_NOFS);
+	if (!iter)
+		return ERR_PTR(-ENOMEM);

This iterator can be made private to handle_one_tree_block as I don't see it being used outside of that function.

It's kinda a performance optimization.

Instead of allocating memory for each loop, we allocate the memory just once, and reuse it until the whole backref map for the bytenr is built.

Quoted 8 lines

fs/btrfs/relocation.c struct backref_node *build_backref_tree(struct reloc_control *rc, · line 1042

Quoted 6 lines
fs/btrfs/relocation.c +5 -0
+	path = btrfs_alloc_path();
+	if (!path) {
+		err = -ENOMEM;
+		goto out;
+	}

Same thing with this path. Overall this will reduce the argument to handle_one_tree_block by 2.

Quoted 1 line

Same performance optimization here.

Ok, fair point.

Quoted 2 lines
Quoted 2 lines

<snip>

Quoted 8 lines
Quoted 5 lines

or simply if (!edge)
break;

Also this loop can be rewritten as a do {} while() and it will look:

Yep, but I'm not sure if such do {} while() loop is preferred. IIRC there are some docs saying to avoid such loop?

I'm not aware of any such docs, can you point me to them?

Quoted 6 lines

If there is no such restriction, I would be pretty happy to go that way.

Thanks,
Qu

<snip>

#27 lore raw

Re: [PATCH v2 08/10] btrfs: relocation: Remove the open-coded goto loop for breadth-first search

Quoted 41 lines · Nikolay Borisov
Quoted 26 lines · Qu Wenruo
Quoted 1 line · Nikolay Borisov

[...]

Quoted 7 lines

fs/btrfs/relocation.c struct backref_node *build_backref_tree(struct reloc_control *rc, · line 1037

Quoted 5 lines
fs/btrfs/relocation.c +5 -0
+	int err = 0;
+
+	iter = btrfs_backref_iter_alloc(rc->extent_root->fs_info, GFP_NOFS);
+	if (!iter)
+		return ERR_PTR(-ENOMEM);

This iterator can be made private to handle_one_tree_block as I don't see it being used outside of that function.

It's kinda a performance optimization.

Instead of allocating memory for each loop, we allocate the memory just once, and reuse it until the whole backref map for the bytenr is built.

Quoted 8 lines

fs/btrfs/relocation.c struct backref_node *build_backref_tree(struct reloc_control *rc, · line 1042

Quoted 6 lines
fs/btrfs/relocation.c +5 -0
+	path = btrfs_alloc_path();
+	if (!path) {
+		err = -ENOMEM;
+		goto out;
+	}

Same thing with this path. Overall this will reduce the argument to handle_one_tree_block by 2.

Quoted 1 line

Same performance optimization here.

Ok, fair point.

Quoted 2 lines
Quoted 2 lines

<snip>

Quoted 4 lines
Quoted 4 lines

or simply if (!edge)
break;

Quoted 6 lines
Quoted 4 lines
Quoted 1 line

Also this loop can be rewritten as a do {} while() and it will look:

Yep, but I'm not sure if such do {} while() loop is preferred. IIRC there are some docs saying to avoid such loop?

I'm not aware of any such docs, can you point me to them?

Then I guess it's not a problem. Pretty happy to utilize do {} while () loop in the future.

Thanks,
Qu

Quoted 10 lines
Quoted 7 lines

If there is no such restriction, I would be pretty happy to go that way.

Thanks,
Qu

<snip>

author
#28 lore raw

PATCH v2 9/10 btrfs: relocation: Refactor the finishing part of upper linkage into finish_upper_links()

In reply to Qu Wenruo

After handle_one_tree_backref(), all newly added (not cached) edges and nodes have the following features:

- Only backref_edge::list[LOWER] is linked.
This means, we can only iterate from botton to top, not the other direction.

- Newly added nodes are not added to cache rb_tree yet

So to finish the backref cache, we still need to finish the links and add all nodes into backref cache rb_tree.

This patch will refactor the existing code into finish_upper_links(), add more comments of each branch, and why we need to do all these works.

---
 fs/btrfs/relocation.c | 163 +++++++++++++++++++++++++++---------------
 1 file changed, 107 insertions(+), 56 deletions(-)
fs/btrfs/relocation.c +107 -56
index 26089694b3b5..b42c3d088be4 100644
@@ -998,6 +998,106 @@ static int handle_one_tree_block(struct reloc_control *rc,
 	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.
+ */
+static int finish_upper_links(struct backref_cache *cache,
+			      struct backref_node *start,
+			      struct list_head *useless_node)
+{
+	struct backref_edge *edge;
+	LIST_HEAD(pending_edge);
+
+	/*
+	 * 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 = tree_insert(&cache->rb_root, upper->bytenr,
+					      &upper->rb_node);
+			if (rb_node) {
+				backref_tree_panic(rb_node, -EEXIST,
+						   upper->bytenr);
+				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;
+}
+
 /*
  * build backref tree for a given tree block. root of the backref tree
  * corresponds the tree block, leaves of the backref tree correspond
@@ -1028,7 +1128,6 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 	struct rb_node *rb_node;
 	LIST_HEAD(list); /* Pending edge list, upper node needs to be checked */
 	LIST_HEAD(useless);
-	int cowonly;
 	int ret;
 	int err = 0;
 
@@ -1074,8 +1173,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 	 * into the cache.
 	 */
 	ASSERT(node->checked);
-	cowonly = node->cowonly;
-	if (!cowonly) {
+	if (!node->cowonly) {
 		rb_node = tree_insert(&cache->rb_root, node->bytenr,
 				      &node->rb_node);
 		if (rb_node)
@@ -1083,60 +1181,13 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 		list_add_tail(&node->lower, &cache->leaves);
 	}
 
-	list_for_each_entry(edge, &node->upper, list[LOWER])
-		list_add_tail(&edge->list[UPPER], &list);
-
-	while (!list_empty(&list)) {
-		edge = list_entry(list.next, struct backref_edge, list[UPPER]);
-		list_del_init(&edge->list[UPPER]);
-		upper = edge->node[UPPER];
-		if (upper->detached) {
-			list_del(&edge->list[LOWER]);
-			lower = edge->node[LOWER];
-			free_backref_edge(cache, edge);
-			if (list_empty(&lower->upper))
-				list_add(&lower->list, &useless);
-			continue;
-		}
-
-		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;
-		}
-
-		if (!upper->checked) {
-			/*
-			 * Still want to blow up for developers since this is a
-			 * logic bug.
-			 */
-			ASSERT(0);
-			err = -EINVAL;
-			goto out;
-		}
-		if (cowonly != upper->cowonly) {
-			ASSERT(0);
-			err = -EINVAL;
-			goto out;
-		}
-
-		if (!cowonly) {
-			rb_node = tree_insert(&cache->rb_root, upper->bytenr,
-					      &upper->rb_node);
-			if (rb_node)
-				backref_tree_panic(rb_node, -EEXIST,
-						   upper->bytenr);
-		}
-
-		list_add_tail(&edge->list[UPPER], &upper->lower);
-
-		list_for_each_entry(edge, &upper->upper, list[LOWER])
-			list_add_tail(&edge->list[UPPER], &list);
+	/* Finish the upper linkage of newly added edges/nodes */
+	ret = finish_upper_links(cache, node, &useless);
+	if (ret < 0) {
+		err = ret;
+		goto out;
 	}
+
 	/*
 	 * process useless backref nodes. backref nodes for tree leaves
 	 * are deleted from the cache. backref nodes for upper level
Signature · 1 line
2.25.1
author
#29 lore raw

PATCH v2 10/10 btrfs: relocation: Refactor the useless nodes handling into its own function

In reply to Qu Wenruo

This patch will also add some comment for the cleanup up.

---
 fs/btrfs/relocation.c | 111 ++++++++++++++++++++++++++++--------------
 1 file changed, 75 insertions(+), 36 deletions(-)
fs/btrfs/relocation.c +75 -36
index b42c3d088be4..93364eb07a61 100644
@@ -1098,6 +1098,79 @@ static int finish_upper_links(struct backref_cache *cache,
 	return 0;
 }
 
+/*
+ * For useless nodes, do two major clean ups:
+ * - Cleanup the children edges and nodes
+ *   If child node is also orphan (no parent) during cleanup, then the
+ *   child node will also be cleaned up.
+ *
+ * - Freeing up leaves (level 0), keeps nodes detached
+ *   For nodes, the node is still cached as "detached"
+ *
+ * Return false if @node is not in the @useless_nodes list.
+ * 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;
+	bool ret = false;
+
+	while (!list_empty(useless_nodes)) {
+		struct backref_node *cur;
+
+		cur = list_entry(useless_nodes->next, struct backref_node,
+				 list);
+		list_del_init(&cur->list);
+
+		/* Only tree root nodes can be added to @useless_nodes */
+		ASSERT(list_empty(&cur->upper));
+
+		if (cur == node)
+			ret = true;
+
+		/* The node is the lowest node */
+		if (cur->lowest) {
+			list_del_init(&cur->lower);
+			cur->lowest = 0;
+		}
+
+		/* Cleanup the lower edges */
+		while (!list_empty(&cur->lower)) {
+			struct backref_edge *edge;
+			struct backref_node *lower;
+
+			edge = list_entry(cur->lower.next,
+					  struct backref_edge, list[UPPER]);
+			list_del(&edge->list[UPPER]);
+			list_del(&edge->list[LOWER]);
+			lower = edge->node[LOWER];
+			free_backref_edge(cache, edge);
+
+			/* Child node is also orphan, queue for cleanup */
+			if (list_empty(&lower->upper))
+				list_add(&lower->list, useless_nodes);
+		}
+		/* Mark this block processed for relocation */
+		mark_block_processed(rc, cur);
+
+		/*
+		 * Backref nodes for tree leaves are deleted from the cache.
+		 * Backref nodes for upper level tree blocks are left in the
+		 * cache to avoid unnecessary backref lookup.
+		 */
+		if (cur->level > 0) {
+			list_add(&cur->list, &cache->detached);
+			cur->detached = 1;
+		} else {
+			rb_erase(&cur->rb_node, &cache->rb_root);
+			free_backref_node(cache, cur);
+		}
+	}
+	return ret;
+}
+
 /*
  * build backref tree for a given tree block. root of the backref tree
  * corresponds the tree block, leaves of the backref tree correspond
@@ -1188,42 +1261,8 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 		goto out;
 	}
 
-	/*
-	 * process useless backref nodes. backref nodes for tree leaves
-	 * are deleted from the cache. backref nodes for upper level
-	 * tree blocks are left in the cache to avoid unnecessary backref
-	 * lookup.
-	 */
-	while (!list_empty(&useless)) {
-		upper = list_entry(useless.next, struct backref_node, list);
-		list_del_init(&upper->list);
-		ASSERT(list_empty(&upper->upper));
-		if (upper == node)
-			node = NULL;
-		if (upper->lowest) {
-			list_del_init(&upper->lower);
-			upper->lowest = 0;
-		}
-		while (!list_empty(&upper->lower)) {
-			edge = list_entry(upper->lower.next,
-					  struct backref_edge, list[UPPER]);
-			list_del(&edge->list[UPPER]);
-			list_del(&edge->list[LOWER]);
-			lower = edge->node[LOWER];
-			free_backref_edge(cache, edge);
-
-			if (list_empty(&lower->upper))
-				list_add(&lower->list, &useless);
-		}
-		mark_block_processed(rc, upper);
-		if (upper->level > 0) {
-			list_add(&upper->list, &cache->detached);
-			upper->detached = 1;
-		} else {
-			rb_erase(&upper->rb_node, &cache->rb_root);
-			free_backref_node(cache, upper);
-		}
-	}
+	if (handle_useless_nodes(rc, &useless, node))
+		node = NULL;
 out:
 	btrfs_backref_iter_free(iter);
 	btrfs_free_path(path);
Signature · 1 line
2.25.1