[PATCH v2 0/6] btrfs-progs: print-tree: Minor enhancement along with --bfs/--dfs options

[PATCH v2 0/6] btrfs-progs: print-tree: Minor enhancement along with --bfs/--dfs options

[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 allow "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 4th patch implements BFS as bfs_print_children().

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.

The 5th patch adds --bfs/--dfs options for dump-tree.

The final patch changes @follow type from int to bool.

Changelog:
v2:
  Make bfs/dfs selectable by adding --bfs and --dfs options.
  Still keep dfs as default (although I really don't see any
  compatibility problem)
  Add a new patch to change @follow type.

Qu Wenruo (6):
  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: Introduce breadth-first search
  btrfs-progs: print-tree: Introduce --bfs and --dfs options
  btrfs-progs: print-tree: Use bool for @follow

 Documentation/btrfs-inspect-internal.asciidoc |   4 +
 cmds-inspect-dump-tree.c                      |  31 ++--
 cmds-restore.c                                |   4 +-
 ctree.c                                       |  25 +--
 ctree.h                                       |  19 ++-
 print-tree.c                                  | 146 ++++++++++++++----
 print-tree.h                                  |  14 +-
 7 files changed, 188 insertions(+), 55 deletions(-)

-- 
2.19.0

[PATCH v2 1/6] 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.19.0

[PATCH v2 2/6] 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.19.0

[PATCH v2 3/6] 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.19.0

[PATCH v2 4/6] btrfs-progs: print-tree: Introduce breadth-first search

[Qu Wenruo]

Introduce a new function, bfs_print_children(), to do breadth-first
search to print a node.

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

diff --git a/print-tree.c b/print-tree.c
index 31f6fa12522f..685d2be8c35a 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;
-- 
2.19.0

[PATCH v2 5/6] btrfs-progs: print-tree: Introduce --bfs and --dfs options

[Qu Wenruo]

Originally print-tree uses depth first search to print trees.
This works fine until we reach 3 level trees (root node level is 2).

For tall trees whose root level is 2 or higher, DFS will mix nodes and
leaves like the following example:

Level 2                       A
                             / \
Level 1                     B   C
                          / |   | \
Level 0                  D  E   F  G

DFS will cause the following output sequence:
A   B   D   E   C   F   G
Which in term of node/leave is:
N   N   L   L   N   L   L

Such mixed node/leave result is sometimes hard for human to read.

This patch will introduce 2 new options, --bfs and --dfs.
--dfs keeps the original output sequence, and to keep things compatible
it's the default behavior.

While --bfs uses breadth-first search, and will cause better output
sequence like:
A   B   C   D   E   F   G
Which in term of node/leave is:
N   N   N   L   L   L   L

Much better sorted for human.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 Documentation/btrfs-inspect-internal.asciidoc |  4 +
 cmds-inspect-dump-tree.c                      | 31 +++++---
 print-tree.c                                  | 73 ++++++++++++-------
 print-tree.h                                  | 14 +++-
 4 files changed, 84 insertions(+), 38 deletions(-)

diff --git a/Documentation/btrfs-inspect-internal.asciidoc b/Documentation/btrfs-inspect-internal.asciidoc
index e2db64660b9a..0abdb27ceb95 100644
--- a/Documentation/btrfs-inspect-internal.asciidoc
+++ b/Documentation/btrfs-inspect-internal.asciidoc
@@ -89,6 +89,10 @@ print only the uuid tree information, empty output if the tree does not exist
 print info of the specified block only
 --follow::::
 use with '-b', print all children tree blocks of '<block_num>'
+--dfs::::
+use depth-first search to print trees. (default)
+--bfs::::
+use breadth-first search to print trees.
 -t <tree_id>::::
 print only the tree with the specified ID, where the ID can be numerical or
 common name in a flexible human readable form
diff --git a/cmds-inspect-dump-tree.c b/cmds-inspect-dump-tree.c
index c8acd55a0c3a..d78fa14356de 100644
--- a/cmds-inspect-dump-tree.c
+++ b/cmds-inspect-dump-tree.c
@@ -221,6 +221,7 @@ int cmd_inspect_dump_tree(int argc, char **argv)
 	int uuid_tree_only = 0;
 	int roots_only = 0;
 	int root_backups = 0;
+	int traverse = BTRFS_PRINT_TREE_DEFAULT;
 	unsigned open_ctree_flags;
 	u64 block_only = 0;
 	struct btrfs_root *tree_root_scan;
@@ -238,7 +239,8 @@ int cmd_inspect_dump_tree(int argc, char **argv)
 	optind = 0;
 	while (1) {
 		int c;
-		enum { GETOPT_VAL_FOLLOW = 256 };
+		enum { GETOPT_VAL_FOLLOW = 256, GETOPT_VAL_DFS,
+		       GETOPT_VAL_BFS };
 		static const struct option long_options[] = {
 			{ "extents", no_argument, NULL, 'e'},
 			{ "device", no_argument, NULL, 'd'},
@@ -248,6 +250,8 @@ int cmd_inspect_dump_tree(int argc, char **argv)
 			{ "block", required_argument, NULL, 'b'},
 			{ "tree", required_argument, NULL, 't'},
 			{ "follow", no_argument, NULL, GETOPT_VAL_FOLLOW },
+			{ "bfs", no_argument, NULL, GETOPT_VAL_BFS },
+			{ "dfs", no_argument, NULL, GETOPT_VAL_DFS },
 			{ NULL, 0, NULL, 0 }
 		};
 
@@ -303,6 +307,12 @@ int cmd_inspect_dump_tree(int argc, char **argv)
 		case GETOPT_VAL_FOLLOW:
 			follow = true;
 			break;
+		case GETOPT_VAL_DFS:
+			traverse = BTRFS_PRINT_TREE_DFS;
+			break;
+		case GETOPT_VAL_BFS:
+			traverse = BTRFS_PRINT_TREE_BFS;
+			break;
 		default:
 			usage(cmd_inspect_dump_tree_usage);
 		}
@@ -341,7 +351,7 @@ int cmd_inspect_dump_tree(int argc, char **argv)
 				(unsigned long long)block_only);
 			goto close_root;
 		}
-		btrfs_print_tree(leaf, follow);
+		btrfs_print_tree(leaf, follow, BTRFS_PRINT_TREE_DEFAULT);
 		free_extent_buffer(leaf);
 		goto close_root;
 	}
@@ -368,17 +378,20 @@ int cmd_inspect_dump_tree(int argc, char **argv)
 		} else {
 			if (info->tree_root->node) {
 				printf("root tree\n");
-				btrfs_print_tree(info->tree_root->node, 1);
+				btrfs_print_tree(info->tree_root->node, 1,
+						 traverse);
 			}
 
 			if (info->chunk_root->node) {
 				printf("chunk tree\n");
-				btrfs_print_tree(info->chunk_root->node, 1);
+				btrfs_print_tree(info->chunk_root->node, 1,
+						 traverse);
 			}
 
 			if (info->log_root_tree) {
 				printf("log root tree\n");
-				btrfs_print_tree(info->log_root_tree->node, 1);
+				btrfs_print_tree(info->log_root_tree->node, 1,
+						 traverse);
 			}
 		}
 	}
@@ -398,7 +411,7 @@ again:
 			goto close_root;
 		}
 		printf("root tree\n");
-		btrfs_print_tree(info->tree_root->node, 1);
+		btrfs_print_tree(info->tree_root->node, 1, traverse);
 		goto close_root;
 	}
 
@@ -408,7 +421,7 @@ again:
 			goto close_root;
 		}
 		printf("chunk tree\n");
-		btrfs_print_tree(info->chunk_root->node, 1);
+		btrfs_print_tree(info->chunk_root->node, 1, traverse);
 		goto close_root;
 	}
 
@@ -418,7 +431,7 @@ again:
 			goto close_root;
 		}
 		printf("log root tree\n");
-		btrfs_print_tree(info->log_root_tree->node, 1);
+		btrfs_print_tree(info->log_root_tree->node, 1, traverse);
 		goto close_root;
 	}
 
@@ -564,7 +577,7 @@ again:
 					       btrfs_header_level(buf));
 				} else {
 					printf(" \n");
-					btrfs_print_tree(buf, 1);
+					btrfs_print_tree(buf, 1, traverse);
 				}
 			}
 			free_extent_buffer(buf);
diff --git a/print-tree.c b/print-tree.c
index 685d2be8c35a..118fe9531d7e 100644
--- a/print-tree.c
+++ b/print-tree.c
@@ -1438,7 +1438,8 @@ static void bfs_print_children(struct extent_buffer *root_eb)
 
 		/* Print all sibling tree blocks */
 		while (1) {
-			btrfs_print_tree(path.nodes[cur_level], 0);
+			btrfs_print_tree(path.nodes[cur_level], 0,
+					 BTRFS_PRINT_TREE_BFS);
 			ret = btrfs_next_sibling_tree_block(fs_info, &path);
 			if (ret < 0)
 				goto out;
@@ -1453,7 +1454,41 @@ out:
 	return;
 }
 
-void btrfs_print_tree(struct extent_buffer *eb, int follow)
+static void dfs_print_children(struct extent_buffer *root_eb)
+{
+	struct btrfs_fs_info *fs_info = root_eb->fs_info;
+	struct extent_buffer *next;
+	int nr = btrfs_header_nritems(root_eb);
+	int root_eb_level = btrfs_header_level(root_eb);
+	int i;
+
+	for (i = 0; i < nr; i++) {
+		next = read_tree_block(fs_info,
+				btrfs_node_blockptr(root_eb, i),
+				btrfs_node_ptr_generation(root_eb, i));
+		if (!extent_buffer_uptodate(next)) {
+			fprintf(stderr, "failed to read %llu in tree %llu\n",
+				btrfs_node_blockptr(root_eb, i),
+				btrfs_header_owner(root_eb));
+			continue;
+		}
+		if (btrfs_header_level(next) != root_eb_level - 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(root_eb), i,
+				root_eb_level,
+				btrfs_header_bytenr(next),
+				btrfs_header_level(next),
+				root_eb_level - 1);
+			free_extent_buffer(next);
+			continue;
+		}
+		btrfs_print_tree(next, 1, BTRFS_PRINT_TREE_DFS);
+		free_extent_buffer(next);
+	}
+}
+
+void btrfs_print_tree(struct extent_buffer *eb, int follow, int traverse)
 {
 	u32 i;
 	u32 nr;
@@ -1461,10 +1496,13 @@ 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;
+	if (traverse != BTRFS_PRINT_TREE_DFS &&
+	    traverse != BTRFS_PRINT_TREE_BFS)
+		traverse = BTRFS_PRINT_TREE_DEFAULT;
+
 	nr = btrfs_header_nritems(eb);
 	if (btrfs_is_leaf(eb)) {
 		btrfs_print_leaf(eb);
@@ -1503,30 +1541,9 @@ 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);
-	}
-
+	if (traverse == BTRFS_PRINT_TREE_DFS)
+		dfs_print_children(eb);
+	else
+		bfs_print_children(eb);
 	return;
 }
diff --git a/print-tree.h b/print-tree.h
index 62667d7f6195..1d8c8b09b0c5 100644
--- a/print-tree.h
+++ b/print-tree.h
@@ -20,7 +20,19 @@
 #define __PRINT_TREE_H__
 
 void btrfs_print_leaf(struct extent_buffer *l);
-void btrfs_print_tree(struct extent_buffer *t, int follow);
+
+/*
+ * Print a tree block (apply to both node and leaf).
+ *
+ * @t:		Tree block
+ * @follow:	Set non-zero to print all its children.
+ * @traverse:	The traverse order. Support DFS and BFS.
+ *		Will fallback to DFS for unknown order.
+ */
+#define BTRFS_PRINT_TREE_DFS		0
+#define BTRFS_PRINT_TREE_BFS		1
+#define BTRFS_PRINT_TREE_DEFAULT	BTRFS_PRINT_TREE_DFS
+void btrfs_print_tree(struct extent_buffer *t, int follow, int traverse);
 void btrfs_print_key(struct btrfs_disk_key *disk_key);
 void print_chunk_item(struct extent_buffer *eb, struct btrfs_chunk *chunk);
 void print_extent_item(struct extent_buffer *eb, int slot, int metadata);
-- 
2.19.0

[PATCH v2 6/6] btrfs-progs: print-tree: Use bool for @follow

[Qu Wenruo]

Just a minor cleanup to make the parameter easier to read.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 cmds-inspect-dump-tree.c | 16 ++++++++--------
 print-tree.c             |  2 +-
 print-tree.h             |  4 ++--
 3 files changed, 11 insertions(+), 11 deletions(-)

diff --git a/cmds-inspect-dump-tree.c b/cmds-inspect-dump-tree.c
index d78fa14356de..08b6de55218f 100644
--- a/cmds-inspect-dump-tree.c
+++ b/cmds-inspect-dump-tree.c
@@ -378,20 +378,20 @@ int cmd_inspect_dump_tree(int argc, char **argv)
 		} else {
 			if (info->tree_root->node) {
 				printf("root tree\n");
-				btrfs_print_tree(info->tree_root->node, 1,
+				btrfs_print_tree(info->tree_root->node, true,
 						 traverse);
 			}
 
 			if (info->chunk_root->node) {
 				printf("chunk tree\n");
-				btrfs_print_tree(info->chunk_root->node, 1,
+				btrfs_print_tree(info->chunk_root->node, true,
 						 traverse);
 			}
 
 			if (info->log_root_tree) {
 				printf("log root tree\n");
-				btrfs_print_tree(info->log_root_tree->node, 1,
-						 traverse);
+				btrfs_print_tree(info->log_root_tree->node,
+						 true, traverse);
 			}
 		}
 	}
@@ -411,7 +411,7 @@ again:
 			goto close_root;
 		}
 		printf("root tree\n");
-		btrfs_print_tree(info->tree_root->node, 1, traverse);
+		btrfs_print_tree(info->tree_root->node, true, traverse);
 		goto close_root;
 	}
 
@@ -421,7 +421,7 @@ again:
 			goto close_root;
 		}
 		printf("chunk tree\n");
-		btrfs_print_tree(info->chunk_root->node, 1, traverse);
+		btrfs_print_tree(info->chunk_root->node, true, traverse);
 		goto close_root;
 	}
 
@@ -431,7 +431,7 @@ again:
 			goto close_root;
 		}
 		printf("log root tree\n");
-		btrfs_print_tree(info->log_root_tree->node, 1, traverse);
+		btrfs_print_tree(info->log_root_tree->node, true, traverse);
 		goto close_root;
 	}
 
@@ -577,7 +577,7 @@ again:
 					       btrfs_header_level(buf));
 				} else {
 					printf(" \n");
-					btrfs_print_tree(buf, 1, traverse);
+					btrfs_print_tree(buf, true, traverse);
 				}
 			}
 			free_extent_buffer(buf);
diff --git a/print-tree.c b/print-tree.c
index 118fe9531d7e..ace8ca240f21 100644
--- a/print-tree.c
+++ b/print-tree.c
@@ -1488,7 +1488,7 @@ static void dfs_print_children(struct extent_buffer *root_eb)
 	}
 }
 
-void btrfs_print_tree(struct extent_buffer *eb, int follow, int traverse)
+void btrfs_print_tree(struct extent_buffer *eb, bool follow, int traverse)
 {
 	u32 i;
 	u32 nr;
diff --git a/print-tree.h b/print-tree.h
index 1d8c8b09b0c5..b7061ded062e 100644
--- a/print-tree.h
+++ b/print-tree.h
@@ -25,14 +25,14 @@ void btrfs_print_leaf(struct extent_buffer *l);
  * Print a tree block (apply to both node and leaf).
  *
  * @t:		Tree block
- * @follow:	Set non-zero to print all its children.
+ * @follow:	Set true to print all its children.
  * @traverse:	The traverse order. Support DFS and BFS.
  *		Will fallback to DFS for unknown order.
  */
 #define BTRFS_PRINT_TREE_DFS		0
 #define BTRFS_PRINT_TREE_BFS		1
 #define BTRFS_PRINT_TREE_DEFAULT	BTRFS_PRINT_TREE_DFS
-void btrfs_print_tree(struct extent_buffer *t, int follow, int traverse);
+void btrfs_print_tree(struct extent_buffer *t, bool follow, int traverse);
 void btrfs_print_key(struct btrfs_disk_key *disk_key);
 void print_chunk_item(struct extent_buffer *eb, struct btrfs_chunk *chunk);
 void print_extent_item(struct extent_buffer *eb, int slot, int metadata);
-- 
2.19.0

Re: [PATCH v2 0/6] btrfs-progs: print-tree: Minor enhancement along with --bfs/--dfs options

[David Sterba]

On Fri, Sep 28, 2018 at 10:04:40AM +0800, Qu Wenruo wrote:
> 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 allow "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 4th patch implements BFS as bfs_print_children().
> 
> 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.
> 
> The 5th patch adds --bfs/--dfs options for dump-tree.
> 
> The final patch changes @follow type from int to bool.
> 
> Changelog:
> v2:
>   Make bfs/dfs selectable by adding --bfs and --dfs options.
>   Still keep dfs as default (although I really don't see any
>   compatibility problem)

Let's do it in two steps: first introduce the bfs/dfs modes and switch
the default eventually if it proves more useful over time.

I'm going to apply the patches, with Nikolay's reviewed-by for patches
1-5 as the code is equivalent to what he acked in v1.