[PATCH 0/4] btrfs-progs: print-tree: breadth-first tree print order

[PATCH 0/4] btrfs-progs: print-tree: breadth-first tree print order

[Qu Wenruo]

This patchset can be fetched from github:
https://github.com/adam900710/btrfs-progs/tree/dump_tree_enhance

The main point of this patchset is to make "btrfs ins dump-tree" to
print tree blocks in breadth-first order when level is higher than 2.

The 1st patch is just a minor cleanup, to remove some unused and
meaningless output.

The 2nd patch does a root<->fs_info cleanup, provides the basis for
later btrfs_next_sibling_tree_block().

The 3rd patch implements a new function, btrfs_next_sibling_tree_block()
to find next sibling tree block, other than leaf.

The final patch will implement BFS for btrfs_print_tree().
The BFS search itself is implemented using path along with
 path::lowest_level and btrfs_next_sibling_tree_block() to iterate all
sibling tree blocks in a level.

Since BFS order is more human-friendly for higher trees, use BFS to
replace DFS order directly.

Qu Wenruo (4):
  btrfs-progs: print-tree: Skip deprecated blockptr / nodesize output
  btrfs-progs: Replace root parameter using fs_info for
    reada_for_search()
  btrfs-progs: Introduce function to find next sibling tree block
  btrfs-progs: print-tree: Use breadth-first search for
    btrfs_print_tree()

 cmds-restore.c |   4 +-
 ctree.c        |  25 ++++++------
 ctree.h        |  19 +++++++--
 print-tree.c   | 102 +++++++++++++++++++++++++++++++++++--------------
 4 files changed, 106 insertions(+), 44 deletions(-)

-- 
2.18.0

[PATCH 1/4] btrfs-progs: print-tree: Skip deprecated blockptr / nodesize output

[Qu Wenruo]

When printing tree nodes, we output slots like:
key (EXTENT_TREE ROOT_ITEM 0) block 73625600 (17975) gen 16

The number in the parentheses is blockptr / nodesize.

However this number doesn't really do any thing useful.
And in fact for unaligned metadata block group (block group start bytenr
is not aligned to 16K), the number doesn't even make sense as it's
rounded down.

In factor kernel doesn't ever output such divided result in its
print-tree.c

Remove it so later reader won't wonder what the number means.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 print-tree.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/print-tree.c b/print-tree.c
index a09ecfbb28f0..31f6fa12522f 100644
--- a/print-tree.c
+++ b/print-tree.c
@@ -1420,9 +1420,8 @@ void btrfs_print_tree(struct extent_buffer *eb, int follow)
 		btrfs_disk_key_to_cpu(&key, &disk_key);
 		printf("\t");
 		btrfs_print_key(&disk_key);
-		printf(" block %llu (%llu) gen %llu\n",
+		printf(" block %llu gen %llu\n",
 		       (unsigned long long)blocknr,
-		       (unsigned long long)blocknr / eb->len,
 		       (unsigned long long)btrfs_node_ptr_generation(eb, i));
 		fflush(stdout);
 	}
-- 
2.18.0

[PATCH 2/4] btrfs-progs: Replace root parameter using fs_info for reada_for_search()

[Qu Wenruo]

As the @root parameter is only used to get @fs_info, use fs_info
directly instead.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 cmds-restore.c |  4 ++--
 ctree.c        | 11 +++++------
 ctree.h        |  4 ++--
 3 files changed, 9 insertions(+), 10 deletions(-)

diff --git a/cmds-restore.c b/cmds-restore.c
index d12c1a924059..30ea8a7e93d1 100644
--- a/cmds-restore.c
+++ b/cmds-restore.c
@@ -259,7 +259,7 @@ again:
 		}
 
 		if (path->reada)
-			reada_for_search(root, path, level, slot, 0);
+			reada_for_search(fs_info, path, level, slot, 0);
 
 		next = read_node_slot(fs_info, c, slot);
 		if (extent_buffer_uptodate(next))
@@ -276,7 +276,7 @@ again:
 		if (!level)
 			break;
 		if (path->reada)
-			reada_for_search(root, path, level, 0, 0);
+			reada_for_search(fs_info, path, level, 0, 0);
 		next = read_node_slot(fs_info, next, 0);
 		if (!extent_buffer_uptodate(next))
 			goto again;
diff --git a/ctree.c b/ctree.c
index d8a6883aa85f..042fae19344d 100644
--- a/ctree.c
+++ b/ctree.c
@@ -1000,10 +1000,9 @@ static int noinline push_nodes_for_insert(struct btrfs_trans_handle *trans,
 /*
  * readahead one full node of leaves
  */
-void reada_for_search(struct btrfs_root *root, struct btrfs_path *path,
-			     int level, int slot, u64 objectid)
+void reada_for_search(struct btrfs_fs_info *fs_info, struct btrfs_path *path,
+		      int level, int slot, u64 objectid)
 {
-	struct btrfs_fs_info *fs_info = root->fs_info;
 	struct extent_buffer *node;
 	struct btrfs_disk_key disk_key;
 	u32 nritems;
@@ -1203,7 +1202,7 @@ again:
 				break;
 
 			if (should_reada)
-				reada_for_search(root, p, level, slot,
+				reada_for_search(fs_info, p, level, slot,
 						 key->objectid);
 
 			b = read_node_slot(fs_info, b, slot);
@@ -2902,7 +2901,7 @@ int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
 		}
 
 		if (path->reada)
-			reada_for_search(root, path, level, slot, 0);
+			reada_for_search(fs_info, path, level, slot, 0);
 
 		next = read_node_slot(fs_info, c, slot);
 		if (!extent_buffer_uptodate(next))
@@ -2919,7 +2918,7 @@ int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
 		if (!level)
 			break;
 		if (path->reada)
-			reada_for_search(root, path, level, 0, 0);
+			reada_for_search(fs_info, path, level, 0, 0);
 		next = read_node_slot(fs_info, next, 0);
 		if (!extent_buffer_uptodate(next))
 			return -EIO;
diff --git a/ctree.h b/ctree.h
index 4719962df67d..6df6075865c2 100644
--- a/ctree.h
+++ b/ctree.h
@@ -2562,8 +2562,8 @@ btrfs_check_node(struct btrfs_root *root, struct btrfs_disk_key *parent_key,
 enum btrfs_tree_block_status
 btrfs_check_leaf(struct btrfs_root *root, struct btrfs_disk_key *parent_key,
 		 struct extent_buffer *buf);
-void reada_for_search(struct btrfs_root *root, struct btrfs_path *path,
-			     int level, int slot, u64 objectid);
+void reada_for_search(struct btrfs_fs_info *fs_info, struct btrfs_path *path,
+		      int level, int slot, u64 objectid);
 struct extent_buffer *read_node_slot(struct btrfs_fs_info *fs_info,
 				   struct extent_buffer *parent, int slot);
 int btrfs_previous_item(struct btrfs_root *root,
-- 
2.18.0

[PATCH 3/4] btrfs-progs: Introduce function to find next sibling tree block

[Qu Wenruo]

Introduce a new function, btrfs_next_sibling_tree_block(), which could
find any sibling tree blocks at path->lowest_level, unlike level 0
limited btrfs_next_leaf().

Since this function is more generic than btrfs_next_leaf(), also make
btrfs_next_leaf() a wrapper of btrfs_next_sibling_tree_block(), to keep
the interface the same as kernel.

This would provide the basis for later breadth-first search print-tree.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 ctree.c | 14 +++++++++-----
 ctree.h | 15 ++++++++++++++-
 2 files changed, 23 insertions(+), 6 deletions(-)

diff --git a/ctree.c b/ctree.c
index 042fae19344d..43d47f19c9cd 100644
--- a/ctree.c
+++ b/ctree.c
@@ -2875,18 +2875,22 @@ int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
 }
 
 /*
- * walk up the tree as far as required to find the next leaf.
+ * walk up the tree as far as required to find the next sibling tree block.
+ * more generic version of btrfs_next_leaf(), as it could find sibling nodes
+ * if @path->lowest_level is not 0.
+ *
  * returns 0 if it found something or 1 if there are no greater leaves.
  * returns < 0 on io errors.
  */
-int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
+int btrfs_next_sibling_tree_block(struct btrfs_fs_info *fs_info,
+				  struct btrfs_path *path)
 {
 	int slot;
-	int level = 1;
+	int level = path->lowest_level + 1;
 	struct extent_buffer *c;
 	struct extent_buffer *next = NULL;
-	struct btrfs_fs_info *fs_info = root->fs_info;
 
+	BUG_ON(path->lowest_level + 1 >= BTRFS_MAX_LEVEL);
 	while(level < BTRFS_MAX_LEVEL) {
 		if (!path->nodes[level])
 			return 1;
@@ -2915,7 +2919,7 @@ int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
 		free_extent_buffer(c);
 		path->nodes[level] = next;
 		path->slots[level] = 0;
-		if (!level)
+		if (level == path->lowest_level)
 			break;
 		if (path->reada)
 			reada_for_search(fs_info, path, level, 0, 0);
diff --git a/ctree.h b/ctree.h
index 6df6075865c2..939c584d0301 100644
--- a/ctree.h
+++ b/ctree.h
@@ -2633,7 +2633,20 @@ static inline int btrfs_insert_empty_item(struct btrfs_trans_handle *trans,
 	return btrfs_insert_empty_items(trans, root, path, key, &data_size, 1);
 }
 
-int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path);
+int btrfs_next_sibling_tree_block(struct btrfs_fs_info *fs_info,
+				  struct btrfs_path *path);
+/*
+ * walk up the tree as far as required to find the next leaf.
+ * returns 0 if it found something or 1 if there are no greater leaves.
+ * returns < 0 on io errors.
+ */
+static inline int btrfs_next_leaf(struct btrfs_root *root,
+				  struct btrfs_path *path)
+{
+	path->lowest_level = 0;
+	return btrfs_next_sibling_tree_block(root->fs_info, path);
+}
+
 static inline int btrfs_next_item(struct btrfs_root *root,
 				  struct btrfs_path *p)
 {
-- 
2.18.0

[PATCH 4/4] btrfs-progs: print-tree: Use breadth-first search for btrfs_print_tree()

[Qu Wenruo]

btrfs_print_tree() uses depth-first search to print a subtree, it works
fine until we have 3 level tree.

In that case, leaves and nodes will be printed in a depth-first order,
making it pretty hard to locate level 1 nodes.

This patch will use breadth-first search for btrfs_print_tree().
It will use btrfs_path::lowest_level to indicate current level, and
print out tree blocks level by level (breadth-first).

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 print-tree.c | 99 ++++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 73 insertions(+), 26 deletions(-)

diff --git a/print-tree.c b/print-tree.c
index 31f6fa12522f..0509ec3da46e 100644
--- a/print-tree.c
+++ b/print-tree.c
@@ -1381,6 +1381,78 @@ void btrfs_print_leaf(struct extent_buffer *eb)
 	}
 }
 
+/* Helper function to reach the most left tree block at @path->lowest_level */
+static int search_leftmost_tree_block(struct btrfs_fs_info *fs_info,
+				      struct btrfs_path *path, int root_level)
+{
+	int i;
+	int ret = 0;
+
+	/* Release all nodes expect path->nodes[root_level] */
+	for (i = 0; i < root_level; i++) {
+		path->slots[i] = 0;
+		if (!path->nodes[i])
+			continue;
+		free_extent_buffer(path->nodes[i]);
+	}
+
+	/* Reach the leftmost tree block by always reading out slot 0 */
+	for (i = root_level; i > path->lowest_level; i--) {
+		struct extent_buffer *eb;
+
+		path->slots[i] = 0;
+		eb = read_node_slot(fs_info, path->nodes[i], 0);
+		if (!extent_buffer_uptodate(eb)) {
+			ret = -EIO;
+			goto out;
+		}
+		path->nodes[i - 1] = eb;
+	}
+out:
+	return ret;
+}
+
+static void bfs_print_children(struct extent_buffer *root_eb)
+{
+	struct btrfs_fs_info *fs_info = root_eb->fs_info;
+	struct btrfs_path path;
+	int root_level = btrfs_header_level(root_eb);
+	int cur_level;
+	int ret;
+
+	if (root_level < 1)
+		return;
+
+	btrfs_init_path(&path);
+	/* For path */
+	extent_buffer_get(root_eb);
+	path.nodes[root_level] = root_eb;
+
+	for (cur_level = root_level - 1; cur_level >= 0; cur_level--) {
+		path.lowest_level = cur_level;
+
+		/* Use the leftmost tree block as start point */
+		ret = search_leftmost_tree_block(fs_info, &path, root_level);
+		if (ret < 0)
+			goto out;
+
+		/* Print all sibling tree blocks */
+		while (1) {
+			btrfs_print_tree(path.nodes[cur_level], 0);
+			ret = btrfs_next_sibling_tree_block(fs_info, &path);
+			if (ret < 0)
+				goto out;
+			if (ret > 0) {
+				ret = 0;
+				break;
+			}
+		}
+	}
+out:
+	btrfs_release_path(&path);
+	return;
+}
+
 void btrfs_print_tree(struct extent_buffer *eb, int follow)
 {
 	u32 i;
@@ -1389,7 +1461,6 @@ void btrfs_print_tree(struct extent_buffer *eb, int follow)
 	struct btrfs_fs_info *fs_info = eb->fs_info;
 	struct btrfs_disk_key disk_key;
 	struct btrfs_key key;
-	struct extent_buffer *next;
 
 	if (!eb)
 		return;
@@ -1431,30 +1502,6 @@ void btrfs_print_tree(struct extent_buffer *eb, int follow)
 	if (follow && !fs_info)
 		return;
 
-	for (i = 0; i < nr; i++) {
-		next = read_tree_block(fs_info,
-				btrfs_node_blockptr(eb, i),
-				btrfs_node_ptr_generation(eb, i));
-		if (!extent_buffer_uptodate(next)) {
-			fprintf(stderr, "failed to read %llu in tree %llu\n",
-				(unsigned long long)btrfs_node_blockptr(eb, i),
-				(unsigned long long)btrfs_header_owner(eb));
-			continue;
-		}
-		if (btrfs_header_level(next) != btrfs_header_level(eb) - 1) {
-			warning(
-"eb corrupted: parent bytenr %llu slot %d level %d child bytenr %llu level has %d expect %d, skipping the slot",
-				btrfs_header_bytenr(eb), i,
-				btrfs_header_level(eb),
-				btrfs_header_bytenr(next),
-				btrfs_header_level(next),
-				btrfs_header_level(eb) - 1);
-			free_extent_buffer(next);
-			continue;
-		}
-		btrfs_print_tree(next, 1);
-		free_extent_buffer(next);
-	}
-
+	bfs_print_children(eb);
 	return;
 }
-- 
2.18.0

Re: [PATCH 1/4] btrfs-progs: print-tree: Skip deprecated blockptr / nodesize output

[Nikolay Borisov]

On  5.09.2018 09:29, Qu Wenruo wrote:
> When printing tree nodes, we output slots like:
> key (EXTENT_TREE ROOT_ITEM 0) block 73625600 (17975) gen 16
> 
> The number in the parentheses is blockptr / nodesize.
> 
> However this number doesn't really do any thing useful.
> And in fact for unaligned metadata block group (block group start bytenr
> is not aligned to 16K), the number doesn't even make sense as it's
> rounded down.
> 
> In factor kernel doesn't ever output such divided result in its
> print-tree.c
> 
> Remove it so later reader won't wonder what the number means.
> 
> Signed-off-by: Qu Wenruo <wqu@suse.com>

Reviewed-by: Nikolay Borisov <nborisov@suse.com>

> ---
>  print-tree.c | 3 +--
>  1 file changed, 1 insertion(+), 2 deletions(-)
> 
> diff --git a/print-tree.c b/print-tree.c
> index a09ecfbb28f0..31f6fa12522f 100644
> --- a/print-tree.c
> +++ b/print-tree.c
> @@ -1420,9 +1420,8 @@ void btrfs_print_tree(struct extent_buffer *eb, int follow)
>  		btrfs_disk_key_to_cpu(&key, &disk_key);
>  		printf("\t");
>  		btrfs_print_key(&disk_key);
> -		printf(" block %llu (%llu) gen %llu\n",
> +		printf(" block %llu gen %llu\n",
>  		       (unsigned long long)blocknr,
> -		       (unsigned long long)blocknr / eb->len,
>  		       (unsigned long long)btrfs_node_ptr_generation(eb, i));
>  		fflush(stdout);
>  	}
> 

Re: [PATCH 2/4] btrfs-progs: Replace root parameter using fs_info for reada_for_search()

[Nikolay Borisov]

On  5.09.2018 09:29, Qu Wenruo wrote:
> As the @root parameter is only used to get @fs_info, use fs_info
> directly instead.
> 
> Signed-off-by: Qu Wenruo <wqu@suse.com>

Reviewed-by: Nikolay Borisov <nborisov@suse.com>

> ---
>  cmds-restore.c |  4 ++--
>  ctree.c        | 11 +++++------
>  ctree.h        |  4 ++--
>  3 files changed, 9 insertions(+), 10 deletions(-)
> 
> diff --git a/cmds-restore.c b/cmds-restore.c
> index d12c1a924059..30ea8a7e93d1 100644
> --- a/cmds-restore.c
> +++ b/cmds-restore.c
> @@ -259,7 +259,7 @@ again:
>  		}
>  
>  		if (path->reada)
> -			reada_for_search(root, path, level, slot, 0);
> +			reada_for_search(fs_info, path, level, slot, 0);
>  
>  		next = read_node_slot(fs_info, c, slot);
>  		if (extent_buffer_uptodate(next))
> @@ -276,7 +276,7 @@ again:
>  		if (!level)
>  			break;
>  		if (path->reada)
> -			reada_for_search(root, path, level, 0, 0);
> +			reada_for_search(fs_info, path, level, 0, 0);
>  		next = read_node_slot(fs_info, next, 0);
>  		if (!extent_buffer_uptodate(next))
>  			goto again;
> diff --git a/ctree.c b/ctree.c
> index d8a6883aa85f..042fae19344d 100644
> --- a/ctree.c
> +++ b/ctree.c
> @@ -1000,10 +1000,9 @@ static int noinline push_nodes_for_insert(struct btrfs_trans_handle *trans,
>  /*
>   * readahead one full node of leaves
>   */
> -void reada_for_search(struct btrfs_root *root, struct btrfs_path *path,
> -			     int level, int slot, u64 objectid)
> +void reada_for_search(struct btrfs_fs_info *fs_info, struct btrfs_path *path,
> +		      int level, int slot, u64 objectid)
>  {
> -	struct btrfs_fs_info *fs_info = root->fs_info;
>  	struct extent_buffer *node;
>  	struct btrfs_disk_key disk_key;
>  	u32 nritems;
> @@ -1203,7 +1202,7 @@ again:
>  				break;
>  
>  			if (should_reada)
> -				reada_for_search(root, p, level, slot,
> +				reada_for_search(fs_info, p, level, slot,
>  						 key->objectid);
>  
>  			b = read_node_slot(fs_info, b, slot);
> @@ -2902,7 +2901,7 @@ int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
>  		}
>  
>  		if (path->reada)
> -			reada_for_search(root, path, level, slot, 0);
> +			reada_for_search(fs_info, path, level, slot, 0);
>  
>  		next = read_node_slot(fs_info, c, slot);
>  		if (!extent_buffer_uptodate(next))
> @@ -2919,7 +2918,7 @@ int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
>  		if (!level)
>  			break;
>  		if (path->reada)
> -			reada_for_search(root, path, level, 0, 0);
> +			reada_for_search(fs_info, path, level, 0, 0);
>  		next = read_node_slot(fs_info, next, 0);
>  		if (!extent_buffer_uptodate(next))
>  			return -EIO;
> diff --git a/ctree.h b/ctree.h
> index 4719962df67d..6df6075865c2 100644
> --- a/ctree.h
> +++ b/ctree.h
> @@ -2562,8 +2562,8 @@ btrfs_check_node(struct btrfs_root *root, struct btrfs_disk_key *parent_key,
>  enum btrfs_tree_block_status
>  btrfs_check_leaf(struct btrfs_root *root, struct btrfs_disk_key *parent_key,
>  		 struct extent_buffer *buf);
> -void reada_for_search(struct btrfs_root *root, struct btrfs_path *path,
> -			     int level, int slot, u64 objectid);
> +void reada_for_search(struct btrfs_fs_info *fs_info, struct btrfs_path *path,
> +		      int level, int slot, u64 objectid);
>  struct extent_buffer *read_node_slot(struct btrfs_fs_info *fs_info,
>  				   struct extent_buffer *parent, int slot);
>  int btrfs_previous_item(struct btrfs_root *root,
> 

Re: [PATCH 3/4] btrfs-progs: Introduce function to find next sibling tree block

[Nikolay Borisov]

On  5.09.2018 09:29, Qu Wenruo wrote:
> Introduce a new function, btrfs_next_sibling_tree_block(), which could
> find any sibling tree blocks at path->lowest_level, unlike level 0
> limited btrfs_next_leaf().
> 
> Since this function is more generic than btrfs_next_leaf(), also make
> btrfs_next_leaf() a wrapper of btrfs_next_sibling_tree_block(), to keep
> the interface the same as kernel.
> 
> This would provide the basis for later breadth-first search print-tree.
> 
> Signed-off-by: Qu Wenruo <wqu@suse.com>

Reviewed-by: Nikolay Borisov <nborisov@suse.com>

> ---
>  ctree.c | 14 +++++++++-----
>  ctree.h | 15 ++++++++++++++-
>  2 files changed, 23 insertions(+), 6 deletions(-)
> 
> diff --git a/ctree.c b/ctree.c
> index 042fae19344d..43d47f19c9cd 100644
> --- a/ctree.c
> +++ b/ctree.c
> @@ -2875,18 +2875,22 @@ int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
>  }
>  
>  /*
> - * walk up the tree as far as required to find the next leaf.
> + * walk up the tree as far as required to find the next sibling tree block.
> + * more generic version of btrfs_next_leaf(), as it could find sibling nodes
> + * if @path->lowest_level is not 0.
> + *
>   * returns 0 if it found something or 1 if there are no greater leaves.
>   * returns < 0 on io errors.
>   */
> -int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
> +int btrfs_next_sibling_tree_block(struct btrfs_fs_info *fs_info,
> +				  struct btrfs_path *path)
>  {
>  	int slot;
> -	int level = 1;
> +	int level = path->lowest_level + 1;
>  	struct extent_buffer *c;
>  	struct extent_buffer *next = NULL;
> -	struct btrfs_fs_info *fs_info = root->fs_info;
>  
> +	BUG_ON(path->lowest_level + 1 >= BTRFS_MAX_LEVEL);
>  	while(level < BTRFS_MAX_LEVEL) {
>  		if (!path->nodes[level])
>  			return 1;
> @@ -2915,7 +2919,7 @@ int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
>  		free_extent_buffer(c);
>  		path->nodes[level] = next;
>  		path->slots[level] = 0;
> -		if (!level)
> +		if (level == path->lowest_level)
>  			break;
>  		if (path->reada)
>  			reada_for_search(fs_info, path, level, 0, 0);
> diff --git a/ctree.h b/ctree.h
> index 6df6075865c2..939c584d0301 100644
> --- a/ctree.h
> +++ b/ctree.h
> @@ -2633,7 +2633,20 @@ static inline int btrfs_insert_empty_item(struct btrfs_trans_handle *trans,
>  	return btrfs_insert_empty_items(trans, root, path, key, &data_size, 1);
>  }
>  
> -int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path);
> +int btrfs_next_sibling_tree_block(struct btrfs_fs_info *fs_info,
> +				  struct btrfs_path *path);
> +/*
> + * walk up the tree as far as required to find the next leaf.
> + * returns 0 if it found something or 1 if there are no greater leaves.
> + * returns < 0 on io errors.
> + */
> +static inline int btrfs_next_leaf(struct btrfs_root *root,
> +				  struct btrfs_path *path)
> +{
> +	path->lowest_level = 0;
> +	return btrfs_next_sibling_tree_block(root->fs_info, path);
> +}
> +
>  static inline int btrfs_next_item(struct btrfs_root *root,
>  				  struct btrfs_path *p)
>  {
> 

Re: [PATCH 4/4] btrfs-progs: print-tree: Use breadth-first search for btrfs_print_tree()

[Nikolay Borisov]

On  5.09.2018 09:29, Qu Wenruo wrote:
> btrfs_print_tree() uses depth-first search to print a subtree, it works
> fine until we have 3 level tree.
> 
> In that case, leaves and nodes will be printed in a depth-first order,
> making it pretty hard to locate level 1 nodes.
> 
> This patch will use breadth-first search for btrfs_print_tree().
> It will use btrfs_path::lowest_level to indicate current level, and
> print out tree blocks level by level (breadth-first).
> 
> Signed-off-by: Qu Wenruo <wqu@suse.com>

Reviewed-by: Nikolay Borisov <nborisov@suse.com>

> ---
>  print-tree.c | 99 ++++++++++++++++++++++++++++++++++++++--------------
>  1 file changed, 73 insertions(+), 26 deletions(-)
> 
> diff --git a/print-tree.c b/print-tree.c
> index 31f6fa12522f..0509ec3da46e 100644
> --- a/print-tree.c
> +++ b/print-tree.c
> @@ -1381,6 +1381,78 @@ void btrfs_print_leaf(struct extent_buffer *eb)
>  	}
>  }
>  
> +/* Helper function to reach the most left tree block at @path->lowest_level */
> +static int search_leftmost_tree_block(struct btrfs_fs_info *fs_info,
> +				      struct btrfs_path *path, int root_level)
> +{
> +	int i;
> +	int ret = 0;
> +
> +	/* Release all nodes expect path->nodes[root_level] */
> +	for (i = 0; i < root_level; i++) {
> +		path->slots[i] = 0;
> +		if (!path->nodes[i])
> +			continue;
> +		free_extent_buffer(path->nodes[i]);
> +	}
> +
> +	/* Reach the leftmost tree block by always reading out slot 0 */
> +	for (i = root_level; i > path->lowest_level; i--) {
> +		struct extent_buffer *eb;
> +
> +		path->slots[i] = 0;
> +		eb = read_node_slot(fs_info, path->nodes[i], 0);
> +		if (!extent_buffer_uptodate(eb)) {
> +			ret = -EIO;
> +			goto out;
> +		}
> +		path->nodes[i - 1] = eb;
> +	}
> +out:
> +	return ret;
> +}
> +
> +static void bfs_print_children(struct extent_buffer *root_eb)
> +{
> +	struct btrfs_fs_info *fs_info = root_eb->fs_info;
> +	struct btrfs_path path;
> +	int root_level = btrfs_header_level(root_eb);
> +	int cur_level;
> +	int ret;
> +
> +	if (root_level < 1)
> +		return;
> +
> +	btrfs_init_path(&path);
> +	/* For path */
> +	extent_buffer_get(root_eb);
> +	path.nodes[root_level] = root_eb;
> +
> +	for (cur_level = root_level - 1; cur_level >= 0; cur_level--) {
> +		path.lowest_level = cur_level;
> +
> +		/* Use the leftmost tree block as start point */
> +		ret = search_leftmost_tree_block(fs_info, &path, root_level);

So what you do here is really get the leftmost item at until level
'cur_level'.

> +		if (ret < 0)
> +			goto out;
> +
> +		/* Print all sibling tree blocks */
> +		while (1) {
> +			btrfs_print_tree(path.nodes[cur_level], 0);
Then you print the block.

> +			ret = btrfs_next_sibling_tree_block(fs_info, &path);
And this just loads the next block at level 'cur_level', representing
the "breadth" portion.

> +			if (ret < 0)
> +				goto out;
> +			if (ret > 0) {
> +				ret = 0;
> +				break;
> +			}
> +		}
> +	}
> +out:
> +	btrfs_release_path(&path);
> +	return;
> +}
> +
>  void btrfs_print_tree(struct extent_buffer *eb, int follow)
>  {
>  	u32 i;
> @@ -1389,7 +1461,6 @@ void btrfs_print_tree(struct extent_buffer *eb, int follow)
>  	struct btrfs_fs_info *fs_info = eb->fs_info;
>  	struct btrfs_disk_key disk_key;
>  	struct btrfs_key key;
> -	struct extent_buffer *next;
>  
>  	if (!eb)
>  		return;
> @@ -1431,30 +1502,6 @@ void btrfs_print_tree(struct extent_buffer *eb, int follow)
>  	if (follow && !fs_info)
>  		return;
>  
> -	for (i = 0; i < nr; i++) {
> -		next = read_tree_block(fs_info,
> -				btrfs_node_blockptr(eb, i),
> -				btrfs_node_ptr_generation(eb, i));
> -		if (!extent_buffer_uptodate(next)) {
> -			fprintf(stderr, "failed to read %llu in tree %llu\n",
> -				(unsigned long long)btrfs_node_blockptr(eb, i),
> -				(unsigned long long)btrfs_header_owner(eb));
> -			continue;
> -		}
> -		if (btrfs_header_level(next) != btrfs_header_level(eb) - 1) {
> -			warning(
> -"eb corrupted: parent bytenr %llu slot %d level %d child bytenr %llu level has %d expect %d, skipping the slot",
> -				btrfs_header_bytenr(eb), i,
> -				btrfs_header_level(eb),
> -				btrfs_header_bytenr(next),
> -				btrfs_header_level(next),
> -				btrfs_header_level(eb) - 1);
> -			free_extent_buffer(next);
> -			continue;
> -		}
> -		btrfs_print_tree(next, 1);
> -		free_extent_buffer(next);
> -	}
> -
> +	bfs_print_children(eb);
>  	return;
>  }
>