Skip to contentSkip to conversation

btrfs-progs: dump-tree: Introduce --breadth-first option

PATCH In review Qu Wenruo 5 participants 7 messages Aug 23, 2018 – Sep 12, 2018

Subsystems (2)
lore
Share & tools
lore

Qu Wenruo

author
#0 lore raw

PATCH 1/1 btrfs-progs: dump-tree: Introduce --breadth-first option

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.

---
 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(-)
Documentation/btrfs-inspect-internal.asciidoc +5 -0
index e2db64660b9a..5435455fe099 100644
@@ -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
cmds-inspect-dump-tree.c +17 -9
index c8acd55a0c3a..ecda07d65ab6 100644
@@ -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);
print-tree.c +89 -0

92 lines not on this page · raw message

print-tree.h +1 -0
index 62667d7f6195..1bf3906bacbd 100644
@@ -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);
Signature · 1 line
2.18.0
#1 lore raw
Quoted 3 lines · Qu Wenruo

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?

#2 lore raw
Quoted 10 lines · Nikolay Borisov
Quoted 3 lines · Qu Wenruo

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.

Quoted 1 line
Quoted 1 line

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

#3 lore raw
Quoted 10 lines · Qu Wenruo
Quoted 7 lines · Nikolay Borisov
Quoted 3 lines · Qu Wenruo

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.

Quoted 6 lines
Quoted 3 lines

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.

Quoted 9 lines
Quoted 2 lines
Quoted 2 lines

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.

Quoted 4 lines

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

Quoted 7 lines

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

Thanks,
Qu

#4 lore raw
Quoted 38 lines · Qu Wenruo
Quoted 10 lines · Qu Wenruo
Quoted 7 lines · Nikolay Borisov
Quoted 3 lines · Qu Wenruo

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.

Quoted 6 lines
Quoted 3 lines

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.

Quoted 9 lines
Quoted 2 lines
Quoted 2 lines

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.

Quoted 4 lines

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.

Quoted 5 lines

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.

#5 lore raw
Quoted 39 lines · David Sterba
Quoted 38 lines · Qu Wenruo
Quoted 10 lines · Qu Wenruo
Quoted 7 lines · Nikolay Borisov
Quoted 3 lines · Qu Wenruo

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.

Quoted 6 lines
Quoted 3 lines

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.

Quoted 13 lines
Quoted 2 lines
Quoted 2 lines

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.

Quoted 7 lines
Quoted 5 lines

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

Quoted 6 lines

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.

Reviewed-by on v1 1/1
#6 lore raw
In reply to Qu Wenruo
Quoted 10 lines · 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.

LGTM.

Quoted 262 lines
---
  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(-)
Documentation/btrfs-inspect-internal.asciidoc +5 -0
index e2db64660b9a..5435455fe099 100644
@@ -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
cmds-inspect-dump-tree.c +17 -9
index c8acd55a0c3a..ecda07d65ab6 100644
@@ -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);
print-tree.c +89 -0
index 31f6fa12522f..0717a2d882c5 100644
@@ -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);
+	}
+}
print-tree.h +1 -0
index 62667d7f6195..1bf3906bacbd 100644
@@ -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);