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 <[email protected]> --- 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
