[PATCH] btrfs-progs: dump-tree: Introduce --breadth-first option

[PATCH] btrfs-progs: dump-tree: Introduce --breadth-first option

[Qu Wenruo]

By default dump-tree does depth-first search.

For 2 level trees it's completely OK, but for 3 level trees, it would be
pretty hard to locate output of middle level tree nodes.

Introduce --breadth-first option to do breadth-first tree dump.
This is especially handy to inspect high level trees, e.g. comparing
tree reloc tree with its source tree.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 Documentation/btrfs-inspect-internal.asciidoc |  5 ++
 cmds-inspect-dump-tree.c                      | 26 ++++--
 print-tree.c                                  | 89 +++++++++++++++++++
 print-tree.h                                  |  1 +
 4 files changed, 112 insertions(+), 9 deletions(-)

diff --git a/Documentation/btrfs-inspect-internal.asciidoc b/Documentation/btrfs-inspect-internal.asciidoc
index e2db64660b9a..5435455fe099 100644
--- a/Documentation/btrfs-inspect-internal.asciidoc
+++ b/Documentation/btrfs-inspect-internal.asciidoc
@@ -69,6 +69,9 @@ readable equivalents where possible.
 This is useful for analyzing filesystem state or inconsistencies and has
 a positive educational effect on understanding the internal filesystem structure.
 +
+By default *dump-tree* will dump the tree using depth-first search, this behavior
+can be changed by '--breadth-first' option.
++
 NOTE: contains file names, consider that if you're asked to send the dump for
 analysis. Does not contain file data.
 +
@@ -89,6 +92,8 @@ 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>'
+--breadth-first::::
+use breadth-first search to dump trees instead of default depth-first search
 -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..ecda07d65ab6 100644
--- a/cmds-inspect-dump-tree.c
+++ b/cmds-inspect-dump-tree.c
@@ -200,6 +200,7 @@ const char * const cmd_inspect_dump_tree_usage[] = {
 	"-b|--block <block_num> print info from the specified block only",
 	"-t|--tree <tree_id>    print only tree with the given id (string or number)",
 	"--follow               use with -b, to show all children tree blocks of <block_num>",
+	"--breadth-first        do breadth-first search instead of default depth-first one",
 	NULL
 };
 
@@ -213,6 +214,7 @@ int cmd_inspect_dump_tree(int argc, char **argv)
 	struct extent_buffer *leaf;
 	struct btrfs_disk_key disk_key;
 	struct btrfs_key found_key;
+	void (*print_tree_func) (struct extent_buffer *, int follow);
 	char uuidbuf[BTRFS_UUID_UNPARSED_SIZE];
 	int ret;
 	int slot;
@@ -227,6 +229,7 @@ int cmd_inspect_dump_tree(int argc, char **argv)
 	u64 tree_id = 0;
 	bool follow = false;
 
+	print_tree_func = btrfs_print_tree;
 	/*
 	 * For debug-tree, we care nothing about extent tree (it's just backref
 	 * and usage accounting, only makes sense for RW operations).
@@ -238,7 +241,7 @@ 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_BREADTH_FIRST };
 		static const struct option long_options[] = {
 			{ "extents", no_argument, NULL, 'e'},
 			{ "device", no_argument, NULL, 'd'},
@@ -248,6 +251,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 },
+			{ "breadth-first", no_argument, NULL,
+				GETOPT_VAL_BREADTH_FIRST },
 			{ NULL, 0, NULL, 0 }
 		};
 
@@ -303,6 +308,9 @@ int cmd_inspect_dump_tree(int argc, char **argv)
 		case GETOPT_VAL_FOLLOW:
 			follow = true;
 			break;
+		case GETOPT_VAL_BREADTH_FIRST:
+			print_tree_func = btrfs_print_tree_breadth_first;
+			break;
 		default:
 			usage(cmd_inspect_dump_tree_usage);
 		}
@@ -341,7 +349,7 @@ int cmd_inspect_dump_tree(int argc, char **argv)
 				(unsigned long long)block_only);
 			goto close_root;
 		}
-		btrfs_print_tree(leaf, follow);
+		print_tree_func(leaf, follow);
 		free_extent_buffer(leaf);
 		goto close_root;
 	}
@@ -368,17 +376,17 @@ 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);
+				print_tree_func(info->tree_root->node, 1);
 			}
 
 			if (info->chunk_root->node) {
 				printf("chunk tree\n");
-				btrfs_print_tree(info->chunk_root->node, 1);
+				print_tree_func(info->chunk_root->node, 1);
 			}
 
 			if (info->log_root_tree) {
 				printf("log root tree\n");
-				btrfs_print_tree(info->log_root_tree->node, 1);
+				print_tree_func(info->log_root_tree->node, 1);
 			}
 		}
 	}
@@ -398,7 +406,7 @@ again:
 			goto close_root;
 		}
 		printf("root tree\n");
-		btrfs_print_tree(info->tree_root->node, 1);
+		print_tree_func(info->tree_root->node, 1);
 		goto close_root;
 	}
 
@@ -408,7 +416,7 @@ again:
 			goto close_root;
 		}
 		printf("chunk tree\n");
-		btrfs_print_tree(info->chunk_root->node, 1);
+		print_tree_func(info->chunk_root->node, 1);
 		goto close_root;
 	}
 
@@ -418,7 +426,7 @@ again:
 			goto close_root;
 		}
 		printf("log root tree\n");
-		btrfs_print_tree(info->log_root_tree->node, 1);
+		print_tree_func(info->log_root_tree->node, 1);
 		goto close_root;
 	}
 
@@ -564,7 +572,7 @@ again:
 					       btrfs_header_level(buf));
 				} else {
 					printf(" \n");
-					btrfs_print_tree(buf, 1);
+					print_tree_func(buf, 1);
 				}
 			}
 			free_extent_buffer(buf);
diff --git a/print-tree.c b/print-tree.c
index 31f6fa12522f..0717a2d882c5 100644
--- a/print-tree.c
+++ b/print-tree.c
@@ -1458,3 +1458,92 @@ void btrfs_print_tree(struct extent_buffer *eb, int follow)
 
 	return;
 }
+
+struct bfs_entry {
+	struct list_head list;
+	u64 bytenr;
+};
+
+/*
+ * breadth-first search version of btrfs_print_tree().
+ *
+ * Useful for high tree levels
+ */
+void btrfs_print_tree_breadth_first(struct extent_buffer *eb, int follow)
+{
+	LIST_HEAD(search_list);
+	struct bfs_entry *entry;
+
+	if (!eb)
+		return;
+	if (!follow) {
+		btrfs_print_tree(eb, follow);
+		return;
+	}
+	entry = malloc(sizeof(*entry));
+	if (!entry) {
+		error("failed to alloc memory for breadth-first search");
+		return;
+	}
+	entry->bytenr = eb->start;
+	list_add_tail(&entry->list, &search_list);
+	while (!list_empty(&search_list)) {
+		struct extent_buffer *current;
+		struct extent_buffer *child;
+		u64 bytenr;
+		int i;
+		int nr;
+
+		entry = list_entry(search_list.next, struct bfs_entry, list);
+		bytenr = entry->bytenr;
+		list_del(&entry->list);
+		free(entry);
+
+		current = read_tree_block(eb->fs_info, bytenr, 0);
+		btrfs_print_tree(current, 0);
+
+		if (!btrfs_header_level(current)) {
+			free_extent_buffer(current);
+			continue;
+		}
+
+		nr = btrfs_header_nritems(current);
+
+		/* Do child tree block check and queue them for later print */
+		for (i = 0; i < nr; i++) {
+			u64 blockptr = btrfs_node_blockptr(current, i);
+
+			/* read_tree_block will do transid check */
+			child = read_tree_block(eb->fs_info, blockptr,
+					btrfs_node_ptr_generation(current, i));
+			if (!extent_buffer_uptodate(child)) {
+				error("failed to read %llu in tree %llu\n",
+					blockptr,
+					btrfs_header_owner(current));
+				continue;
+			}
+			if (btrfs_header_level(current) !=
+			    btrfs_header_level(child) + 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(current), i,
+					btrfs_header_level(current),
+					btrfs_header_bytenr(child),
+					btrfs_header_level(child),
+					btrfs_header_level(current) + 1);
+				free_extent_buffer(child);
+				continue;
+			}
+			free_extent_buffer(child);
+			entry = malloc(sizeof(*entry));
+			if (!entry) {
+				error(
+			"failed to alloc memory for breadth-first search");
+				continue;
+			}
+			entry->bytenr = blockptr;
+			list_add_tail(&entry->list, &search_list);
+		}
+		free_extent_buffer(current);
+	}
+}
diff --git a/print-tree.h b/print-tree.h
index 62667d7f6195..1bf3906bacbd 100644
--- a/print-tree.h
+++ b/print-tree.h
@@ -21,6 +21,7 @@
 
 void btrfs_print_leaf(struct extent_buffer *l);
 void btrfs_print_tree(struct extent_buffer *t, int follow);
+void btrfs_print_tree_breadth_first(struct extent_buffer *eb, int follow);
 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.18.0

Re: [PATCH] btrfs-progs: dump-tree: Introduce --breadth-first option

[Nikolay Borisov]

On 23.08.2018 10:31, Qu Wenruo wrote:
> Introduce --breadth-first option to do breadth-first tree dump.
> This is especially handy to inspect high level trees, e.g. comparing
> tree reloc tree with its source tree.

Will it make sense instead of exposing another option to just have a
heuristics check that will switch to the BFS if the tree is higher than,
say, 2 levels?

Re: [PATCH] btrfs-progs: dump-tree: Introduce --breadth-first option

[Qu Wenruo]

On 2018/8/23 下午3:36, Nikolay Borisov wrote:
> 
> 
> On 23.08.2018 10:31, Qu Wenruo wrote:
>> Introduce --breadth-first option to do breadth-first tree dump.
>> This is especially handy to inspect high level trees, e.g. comparing
>> tree reloc tree with its source tree.
> 
> Will it make sense instead of exposing another option to just have a
> heuristics check that will switch to the BFS if the tree is higher than,
> say, 2 levels?

BFS has one obvious disadvantage here, so it may not be a good idea to
use it for default.

>> More memory usage <<
   It needs to alloc heap memory, and this can be pretty large for
   leaves.
   At level 1, it will need to alloc nr_leaves * sizeof(bfs_entry)
   memory at least.
   Compared to DFS, it only needs to iterate at most 8 times, and all of
   its memory usage is function call stack memory.

It only makes sense for my niche use case (compare tree reloc tree with
its source).
For real world use case the default DFS should works fine without all
the memory allocation burden.

So I still prefer to keep DFS as default and only provides BFS as a
niche option for weird guys like me.

Thanks,
Qu

Re: [PATCH] btrfs-progs: dump-tree: Introduce --breadth-first option

[Su Yue]

On 08/23/2018 03:31 PM, Qu Wenruo wrote:
> By default dump-tree does depth-first search.
> 
> For 2 level trees it's completely OK, but for 3 level trees, it would be
> pretty hard to locate output of middle level tree nodes.
> 
> Introduce --breadth-first option to do breadth-first tree dump.
> This is especially handy to inspect high level trees, e.g. comparing
> tree reloc tree with its source tree.
> 
> Signed-off-by: Qu Wenruo <wqu@suse.com>

LGTM.

Reviewed-by: Su Yue <suy.fnst@cn.fujitsu.com>
> ---
>   Documentation/btrfs-inspect-internal.asciidoc |  5 ++
>   cmds-inspect-dump-tree.c                      | 26 ++++--
>   print-tree.c                                  | 89 +++++++++++++++++++
>   print-tree.h                                  |  1 +
>   4 files changed, 112 insertions(+), 9 deletions(-)
> 
> diff --git a/Documentation/btrfs-inspect-internal.asciidoc b/Documentation/btrfs-inspect-internal.asciidoc
> index e2db64660b9a..5435455fe099 100644
> --- a/Documentation/btrfs-inspect-internal.asciidoc
> +++ b/Documentation/btrfs-inspect-internal.asciidoc
> @@ -69,6 +69,9 @@ readable equivalents where possible.
>   This is useful for analyzing filesystem state or inconsistencies and has
>   a positive educational effect on understanding the internal filesystem structure.
>   +
> +By default *dump-tree* will dump the tree using depth-first search, this behavior
> +can be changed by '--breadth-first' option.
> ++
>   NOTE: contains file names, consider that if you're asked to send the dump for
>   analysis. Does not contain file data.
>   +
> @@ -89,6 +92,8 @@ 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>'
> +--breadth-first::::
> +use breadth-first search to dump trees instead of default depth-first search
>   -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..ecda07d65ab6 100644
> --- a/cmds-inspect-dump-tree.c
> +++ b/cmds-inspect-dump-tree.c
> @@ -200,6 +200,7 @@ const char * const cmd_inspect_dump_tree_usage[] = {
>   	"-b|--block <block_num> print info from the specified block only",
>   	"-t|--tree <tree_id>    print only tree with the given id (string or number)",
>   	"--follow               use with -b, to show all children tree blocks of <block_num>",
> +	"--breadth-first        do breadth-first search instead of default depth-first one",
>   	NULL
>   };
>   
> @@ -213,6 +214,7 @@ int cmd_inspect_dump_tree(int argc, char **argv)
>   	struct extent_buffer *leaf;
>   	struct btrfs_disk_key disk_key;
>   	struct btrfs_key found_key;
> +	void (*print_tree_func) (struct extent_buffer *, int follow);
>   	char uuidbuf[BTRFS_UUID_UNPARSED_SIZE];
>   	int ret;
>   	int slot;
> @@ -227,6 +229,7 @@ int cmd_inspect_dump_tree(int argc, char **argv)
>   	u64 tree_id = 0;
>   	bool follow = false;
>   
> +	print_tree_func = btrfs_print_tree;
>   	/*
>   	 * For debug-tree, we care nothing about extent tree (it's just backref
>   	 * and usage accounting, only makes sense for RW operations).
> @@ -238,7 +241,7 @@ 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_BREADTH_FIRST };
>   		static const struct option long_options[] = {
>   			{ "extents", no_argument, NULL, 'e'},
>   			{ "device", no_argument, NULL, 'd'},
> @@ -248,6 +251,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 },
> +			{ "breadth-first", no_argument, NULL,
> +				GETOPT_VAL_BREADTH_FIRST },
>   			{ NULL, 0, NULL, 0 }
>   		};
>   
> @@ -303,6 +308,9 @@ int cmd_inspect_dump_tree(int argc, char **argv)
>   		case GETOPT_VAL_FOLLOW:
>   			follow = true;
>   			break;
> +		case GETOPT_VAL_BREADTH_FIRST:
> +			print_tree_func = btrfs_print_tree_breadth_first;
> +			break;
>   		default:
>   			usage(cmd_inspect_dump_tree_usage);
>   		}
> @@ -341,7 +349,7 @@ int cmd_inspect_dump_tree(int argc, char **argv)
>   				(unsigned long long)block_only);
>   			goto close_root;
>   		}
> -		btrfs_print_tree(leaf, follow);
> +		print_tree_func(leaf, follow);
>   		free_extent_buffer(leaf);
>   		goto close_root;
>   	}
> @@ -368,17 +376,17 @@ 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);
> +				print_tree_func(info->tree_root->node, 1);
>   			}
>   
>   			if (info->chunk_root->node) {
>   				printf("chunk tree\n");
> -				btrfs_print_tree(info->chunk_root->node, 1);
> +				print_tree_func(info->chunk_root->node, 1);
>   			}
>   
>   			if (info->log_root_tree) {
>   				printf("log root tree\n");
> -				btrfs_print_tree(info->log_root_tree->node, 1);
> +				print_tree_func(info->log_root_tree->node, 1);
>   			}
>   		}
>   	}
> @@ -398,7 +406,7 @@ again:
>   			goto close_root;
>   		}
>   		printf("root tree\n");
> -		btrfs_print_tree(info->tree_root->node, 1);
> +		print_tree_func(info->tree_root->node, 1);
>   		goto close_root;
>   	}
>   
> @@ -408,7 +416,7 @@ again:
>   			goto close_root;
>   		}
>   		printf("chunk tree\n");
> -		btrfs_print_tree(info->chunk_root->node, 1);
> +		print_tree_func(info->chunk_root->node, 1);
>   		goto close_root;
>   	}
>   
> @@ -418,7 +426,7 @@ again:
>   			goto close_root;
>   		}
>   		printf("log root tree\n");
> -		btrfs_print_tree(info->log_root_tree->node, 1);
> +		print_tree_func(info->log_root_tree->node, 1);
>   		goto close_root;
>   	}
>   
> @@ -564,7 +572,7 @@ again:
>   					       btrfs_header_level(buf));
>   				} else {
>   					printf(" \n");
> -					btrfs_print_tree(buf, 1);
> +					print_tree_func(buf, 1);
>   				}
>   			}
>   			free_extent_buffer(buf);
> diff --git a/print-tree.c b/print-tree.c
> index 31f6fa12522f..0717a2d882c5 100644
> --- a/print-tree.c
> +++ b/print-tree.c
> @@ -1458,3 +1458,92 @@ void btrfs_print_tree(struct extent_buffer *eb, int follow)
>   
>   	return;
>   }
> +
> +struct bfs_entry {
> +	struct list_head list;
> +	u64 bytenr;
> +};
> +
> +/*
> + * breadth-first search version of btrfs_print_tree().
> + *
> + * Useful for high tree levels
> + */
> +void btrfs_print_tree_breadth_first(struct extent_buffer *eb, int follow)
> +{
> +	LIST_HEAD(search_list);
> +	struct bfs_entry *entry;
> +
> +	if (!eb)
> +		return;
> +	if (!follow) {
> +		btrfs_print_tree(eb, follow);
> +		return;
> +	}
> +	entry = malloc(sizeof(*entry));
> +	if (!entry) {
> +		error("failed to alloc memory for breadth-first search");
> +		return;
> +	}
> +	entry->bytenr = eb->start;
> +	list_add_tail(&entry->list, &search_list);
> +	while (!list_empty(&search_list)) {
> +		struct extent_buffer *current;
> +		struct extent_buffer *child;
> +		u64 bytenr;
> +		int i;
> +		int nr;
> +
> +		entry = list_entry(search_list.next, struct bfs_entry, list);
> +		bytenr = entry->bytenr;
> +		list_del(&entry->list);
> +		free(entry);
> +
> +		current = read_tree_block(eb->fs_info, bytenr, 0);
> +		btrfs_print_tree(current, 0);
> +
> +		if (!btrfs_header_level(current)) {
> +			free_extent_buffer(current);
> +			continue;
> +		}
> +
> +		nr = btrfs_header_nritems(current);
> +
> +		/* Do child tree block check and queue them for later print */
> +		for (i = 0; i < nr; i++) {
> +			u64 blockptr = btrfs_node_blockptr(current, i);
> +
> +			/* read_tree_block will do transid check */
> +			child = read_tree_block(eb->fs_info, blockptr,
> +					btrfs_node_ptr_generation(current, i));
> +			if (!extent_buffer_uptodate(child)) {
> +				error("failed to read %llu in tree %llu\n",
> +					blockptr,
> +					btrfs_header_owner(current));
> +				continue;
> +			}
> +			if (btrfs_header_level(current) !=
> +			    btrfs_header_level(child) + 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(current), i,
> +					btrfs_header_level(current),
> +					btrfs_header_bytenr(child),
> +					btrfs_header_level(child),
> +					btrfs_header_level(current) + 1);
> +				free_extent_buffer(child);
> +				continue;
> +			}
> +			free_extent_buffer(child);
> +			entry = malloc(sizeof(*entry));
> +			if (!entry) {
> +				error(
> +			"failed to alloc memory for breadth-first search");
> +				continue;
> +			}
> +			entry->bytenr = blockptr;
> +			list_add_tail(&entry->list, &search_list);
> +		}
> +		free_extent_buffer(current);
> +	}
> +}
> diff --git a/print-tree.h b/print-tree.h
> index 62667d7f6195..1bf3906bacbd 100644
> --- a/print-tree.h
> +++ b/print-tree.h
> @@ -21,6 +21,7 @@
>   
>   void btrfs_print_leaf(struct extent_buffer *l);
>   void btrfs_print_tree(struct extent_buffer *t, int follow);
> +void btrfs_print_tree_breadth_first(struct extent_buffer *eb, int follow);
>   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);
> 

Re: [PATCH] btrfs-progs: dump-tree: Introduce --breadth-first option

[Qu Wenruo]

On 2018/8/23 下午3:45, Qu Wenruo wrote:
> 
> 
> On 2018/8/23 下午3:36, Nikolay Borisov wrote:
>>
>>
>> On 23.08.2018 10:31, Qu Wenruo wrote:
>>> Introduce --breadth-first option to do breadth-first tree dump.
>>> This is especially handy to inspect high level trees, e.g. comparing
>>> tree reloc tree with its source tree.
>>
>> Will it make sense instead of exposing another option to just have a
>> heuristics check that will switch to the BFS if the tree is higher than,
>> say, 2 levels?
> 
> BFS has one obvious disadvantage here, so it may not be a good idea to
> use it for default.

Well, this is only true for my implementation.

But there are other solutions to do BFS without that heavy memory usage.

> 
>>> More memory usage <<
>    It needs to alloc heap memory, and this can be pretty large for
>    leaves.
>    At level 1, it will need to alloc nr_leaves * sizeof(bfs_entry)
>    memory at least.
>    Compared to DFS, it only needs to iterate at most 8 times, and all of
>    its memory usage is function call stack memory.
> 
> It only makes sense for my niche use case (compare tree reloc tree with
> its source).
> For real world use case the default DFS should works fine without all
> the memory allocation burden.

Since we have btrfs_path to show where our parents are, it's possible to
use btrfs_path and avoid current memory burden.

And in that case, your idea of using BFS default for tree higher than 2
levels completely make sense.

I'll update the patchset to use a new (while a little more complex) to
implement BFS with less memory usage.

Thank your again for the idea,
Qu

> 
> So I still prefer to keep DFS as default and only provides BFS as a
> niche option for weird guys like me.
> 
> Thanks,
> Qu
> 

Re: [PATCH] btrfs-progs: dump-tree: Introduce --breadth-first option

[David Sterba]

On Tue, Sep 04, 2018 at 08:39:55PM +0800, Qu Wenruo wrote:
> 
> 
> On 2018/8/23 下午3:45, Qu Wenruo wrote:
> > 
> > 
> > On 2018/8/23 下午3:36, Nikolay Borisov wrote:
> >>
> >>
> >> On 23.08.2018 10:31, Qu Wenruo wrote:
> >>> Introduce --breadth-first option to do breadth-first tree dump.
> >>> This is especially handy to inspect high level trees, e.g. comparing
> >>> tree reloc tree with its source tree.
> >>
> >> Will it make sense instead of exposing another option to just have a
> >> heuristics check that will switch to the BFS if the tree is higher than,
> >> say, 2 levels?
> > 
> > BFS has one obvious disadvantage here, so it may not be a good idea to
> > use it for default.
> 
> Well, this is only true for my implementation.
> 
> But there are other solutions to do BFS without that heavy memory usage.
> 
> > 
> >>> More memory usage <<
> >    It needs to alloc heap memory, and this can be pretty large for
> >    leaves.
> >    At level 1, it will need to alloc nr_leaves * sizeof(bfs_entry)
> >    memory at least.
> >    Compared to DFS, it only needs to iterate at most 8 times, and all of
> >    its memory usage is function call stack memory.
> > 
> > It only makes sense for my niche use case (compare tree reloc tree with
> > its source).
> > For real world use case the default DFS should works fine without all
> > the memory allocation burden.
> 
> Since we have btrfs_path to show where our parents are, it's possible to
> use btrfs_path and avoid current memory burden.
> 
> And in that case, your idea of using BFS default for tree higher than 2
> levels completely make sense.

No such games please, keep the default predictable.

As DFS and BFS are quite well-known abbreviations, I'd rather add 2
options to set the the mode, ie --dfs and --bfs. Alternatively there
could be a --traverse=bfs --traverse=dfs but for now I think the two
options should be sufficient.

Re: [PATCH] btrfs-progs: dump-tree: Introduce --breadth-first option

[Qu Wenruo]

On 2018/9/11 下午11:52, David Sterba wrote:
> On Tue, Sep 04, 2018 at 08:39:55PM +0800, Qu Wenruo wrote:
>>
>>
>> On 2018/8/23 下午3:45, Qu Wenruo wrote:
>>>
>>>
>>> On 2018/8/23 下午3:36, Nikolay Borisov wrote:
>>>>
>>>>
>>>> On 23.08.2018 10:31, Qu Wenruo wrote:
>>>>> Introduce --breadth-first option to do breadth-first tree dump.
>>>>> This is especially handy to inspect high level trees, e.g. comparing
>>>>> tree reloc tree with its source tree.
>>>>
>>>> Will it make sense instead of exposing another option to just have a
>>>> heuristics check that will switch to the BFS if the tree is higher than,
>>>> say, 2 levels?
>>>
>>> BFS has one obvious disadvantage here, so it may not be a good idea to
>>> use it for default.
>>
>> Well, this is only true for my implementation.
>>
>> But there are other solutions to do BFS without that heavy memory usage.
>>
>>>
>>>>> More memory usage <<
>>>    It needs to alloc heap memory, and this can be pretty large for
>>>    leaves.
>>>    At level 1, it will need to alloc nr_leaves * sizeof(bfs_entry)
>>>    memory at least.
>>>    Compared to DFS, it only needs to iterate at most 8 times, and all of
>>>    its memory usage is function call stack memory.
>>>
>>> It only makes sense for my niche use case (compare tree reloc tree with
>>> its source).
>>> For real world use case the default DFS should works fine without all
>>> the memory allocation burden.
>>
>> Since we have btrfs_path to show where our parents are, it's possible to
>> use btrfs_path and avoid current memory burden.
>>
>> And in that case, your idea of using BFS default for tree higher than 2
>> levels completely make sense.
> 
> No such games please, keep the default predictable.

The problem I found using dump-tree for high trees is, default dfs is
rather unpredictable.

For 2 level trees, it's pretty OK as it's the same as BFS, showing high
level tree blocks first, then leaves.
But for 3 level trees, it's nearly impossible to locate level 1 nodes.

It makes searching for the same level tree blocks pretty hard.

And since the output of each tree block is still the same, changing the
order won't really affect cases using grep.

So, I really like to replace the DFS with BFS.

Thanks,
Qu

> 
> As DFS and BFS are quite well-known abbreviations, I'd rather add 2
> options to set the the mode, ie --dfs and --bfs. Alternatively there
> could be a --traverse=bfs --traverse=dfs but for now I think the two
> options should be sufficient.
>