btrfs-progs: print-tree: Minor enhancement along with --bfs/--dfs options
Subsystems (2)
v2 cover btrfs-progs: print-tree: Minor enhancement along with --bfs/--dfs options
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(-)
Signature · 1 line
2.19.0
PATCH v2 1/6 btrfs-progs: print-tree: Skip deprecated blockptr / nodesize output
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.
--- print-tree.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-)
print-tree.c +1 -2
@@ -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); }
Signature · 1 line
2.19.0
PATCH v2 2/6 btrfs-progs: Replace root parameter using fs_info for reada_for_search()
In reply to Qu WenruoAs the @root parameter is only used to get @fs_info, use fs_info directly instead.
--- cmds-restore.c | 4 ++-- ctree.c | 11 +++++------ ctree.h | 4 ++-- 3 files changed, 9 insertions(+), 10 deletions(-)
cmds-restore.c +2 -2
@@ -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;
ctree.c +5 -6
@@ -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 ;
ctree.h +2 -2
@@ -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,
Signature · 1 line
2.19.0
PATCH v2 3/6 btrfs-progs: Introduce function to find next sibling tree block
In reply to Qu WenruoIntroduce 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.
--- ctree.c | 14 +++++++++----- ctree.h | 15 ++++++++++++++- 2 files changed, 23 insertions(+), 6 deletions(-)
ctree.c +9 -5
@@ -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 );
ctree.h +14 -1
@@ -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) {
Signature · 1 line
2.19.0
PATCH v2 4/6 btrfs-progs: print-tree: Introduce breadth-first search
In reply to Qu WenruoIntroduce a new function, bfs_print_children(), to do breadth-first search to print a node.
--- print-tree.c | 72 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 72 insertions(+)
print-tree.c +72 -0
@@ -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;
Signature · 1 line
2.19.0
PATCH v2 5/6 btrfs-progs: print-tree: Introduce --bfs and --dfs options
In reply to Qu WenruoOriginally 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 GDFS 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.
--- 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(-)
Documentation/btrfs-inspect-internal.asciidoc +4 -0
@@ -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
cmds-inspect-dump-tree.c +22 -9
@@ -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);
print-tree.c +45 -28
99 lines not on this page · raw message
print-tree.h +13 -1
@@ -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);
Signature · 1 line
2.19.0
PATCH v2 6/6 btrfs-progs: print-tree: Use bool for @follow
In reply to Qu WenruoJust a minor cleanup to make the parameter easier to read.
--- cmds-inspect-dump-tree.c | 16 ++++++++-------- print-tree.c | 2 +- print-tree.h | 4 ++-- 3 files changed, 11 insertions(+), 11 deletions(-)
cmds-inspect-dump-tree.c +8 -8
@@ -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);
print-tree.c +1 -1
@@ -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;
print-tree.h +2 -2
@@ -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);
Signature · 1 line
2.19.0
Quoted 23 lines · Qu Wenruo
This patchset can be fetched from github:
https://github.com/adam900710/btrfs-progs/tree/dump_tree_enhanceThe 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_levelandbtrfs_next_sibling_tree_block()to iterate all
sibling tree blocks in a level.The 5th patch adds --bfs/--dfs options for dump-tree.
Quoted 7 lines
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.