* [PATCH 0/4] btrfs-progs: print-tree: breadth-first tree print order @ 2018-09-05 6:29 Qu Wenruo 2018-09-05 6:29 ` [PATCH 1/4] btrfs-progs: print-tree: Skip deprecated blockptr / nodesize output Qu Wenruo ` (3 more replies) 0 siblings, 4 replies; 9+ messages in thread From: Qu Wenruo @ 2018-09-05 6:29 UTC (permalink / raw) To: linux-btrfs 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 make "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 final patch will implement BFS for btrfs_print_tree(). 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. Since BFS order is more human-friendly for higher trees, use BFS to replace DFS order directly. Qu Wenruo (4): 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: Use breadth-first search for btrfs_print_tree() cmds-restore.c | 4 +- ctree.c | 25 ++++++------ ctree.h | 19 +++++++-- print-tree.c | 102 +++++++++++++++++++++++++++++++++++-------------- 4 files changed, 106 insertions(+), 44 deletions(-) -- 2.18.0 ^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH 1/4] btrfs-progs: print-tree: Skip deprecated blockptr / nodesize output 2018-09-05 6:29 [PATCH 0/4] btrfs-progs: print-tree: breadth-first tree print order Qu Wenruo @ 2018-09-05 6:29 ` Qu Wenruo 2018-09-05 7:42 ` Nikolay Borisov 2018-09-05 6:29 ` [PATCH 2/4] btrfs-progs: Replace root parameter using fs_info for reada_for_search() Qu Wenruo ` (2 subsequent siblings) 3 siblings, 1 reply; 9+ messages in thread From: Qu Wenruo @ 2018-09-05 6:29 UTC (permalink / raw) To: linux-btrfs 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.18.0 ^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [PATCH 1/4] btrfs-progs: print-tree: Skip deprecated blockptr / nodesize output 2018-09-05 6:29 ` [PATCH 1/4] btrfs-progs: print-tree: Skip deprecated blockptr / nodesize output Qu Wenruo @ 2018-09-05 7:42 ` Nikolay Borisov 0 siblings, 0 replies; 9+ messages in thread From: Nikolay Borisov @ 2018-09-05 7:42 UTC (permalink / raw) To: Qu Wenruo, linux-btrfs On 5.09.2018 09:29, Qu Wenruo wrote: > 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> Reviewed-by: Nikolay Borisov <nborisov@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); > } > ^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH 2/4] btrfs-progs: Replace root parameter using fs_info for reada_for_search() 2018-09-05 6:29 [PATCH 0/4] btrfs-progs: print-tree: breadth-first tree print order Qu Wenruo 2018-09-05 6:29 ` [PATCH 1/4] btrfs-progs: print-tree: Skip deprecated blockptr / nodesize output Qu Wenruo @ 2018-09-05 6:29 ` Qu Wenruo 2018-09-05 7:42 ` Nikolay Borisov 2018-09-05 6:29 ` [PATCH 3/4] btrfs-progs: Introduce function to find next sibling tree block Qu Wenruo 2018-09-05 6:29 ` [PATCH 4/4] btrfs-progs: print-tree: Use breadth-first search for btrfs_print_tree() Qu Wenruo 3 siblings, 1 reply; 9+ messages in thread From: Qu Wenruo @ 2018-09-05 6:29 UTC (permalink / raw) To: linux-btrfs 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.18.0 ^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [PATCH 2/4] btrfs-progs: Replace root parameter using fs_info for reada_for_search() 2018-09-05 6:29 ` [PATCH 2/4] btrfs-progs: Replace root parameter using fs_info for reada_for_search() Qu Wenruo @ 2018-09-05 7:42 ` Nikolay Borisov 0 siblings, 0 replies; 9+ messages in thread From: Nikolay Borisov @ 2018-09-05 7:42 UTC (permalink / raw) To: Qu Wenruo, linux-btrfs On 5.09.2018 09:29, Qu Wenruo wrote: > As the @root parameter is only used to get @fs_info, use fs_info > directly instead. > > Signed-off-by: Qu Wenruo <wqu@suse.com> Reviewed-by: Nikolay Borisov <nborisov@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, > ^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH 3/4] btrfs-progs: Introduce function to find next sibling tree block 2018-09-05 6:29 [PATCH 0/4] btrfs-progs: print-tree: breadth-first tree print order Qu Wenruo 2018-09-05 6:29 ` [PATCH 1/4] btrfs-progs: print-tree: Skip deprecated blockptr / nodesize output Qu Wenruo 2018-09-05 6:29 ` [PATCH 2/4] btrfs-progs: Replace root parameter using fs_info for reada_for_search() Qu Wenruo @ 2018-09-05 6:29 ` Qu Wenruo 2018-09-05 8:46 ` Nikolay Borisov 2018-09-05 6:29 ` [PATCH 4/4] btrfs-progs: print-tree: Use breadth-first search for btrfs_print_tree() Qu Wenruo 3 siblings, 1 reply; 9+ messages in thread From: Qu Wenruo @ 2018-09-05 6:29 UTC (permalink / raw) To: linux-btrfs 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.18.0 ^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [PATCH 3/4] btrfs-progs: Introduce function to find next sibling tree block 2018-09-05 6:29 ` [PATCH 3/4] btrfs-progs: Introduce function to find next sibling tree block Qu Wenruo @ 2018-09-05 8:46 ` Nikolay Borisov 0 siblings, 0 replies; 9+ messages in thread From: Nikolay Borisov @ 2018-09-05 8:46 UTC (permalink / raw) To: Qu Wenruo, linux-btrfs On 5.09.2018 09:29, Qu Wenruo wrote: > 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> Reviewed-by: Nikolay Borisov <nborisov@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) > { > ^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH 4/4] btrfs-progs: print-tree: Use breadth-first search for btrfs_print_tree() 2018-09-05 6:29 [PATCH 0/4] btrfs-progs: print-tree: breadth-first tree print order Qu Wenruo ` (2 preceding siblings ...) 2018-09-05 6:29 ` [PATCH 3/4] btrfs-progs: Introduce function to find next sibling tree block Qu Wenruo @ 2018-09-05 6:29 ` Qu Wenruo 2018-09-05 12:46 ` Nikolay Borisov 3 siblings, 1 reply; 9+ messages in thread From: Qu Wenruo @ 2018-09-05 6:29 UTC (permalink / raw) To: linux-btrfs btrfs_print_tree() uses depth-first search to print a subtree, it works fine until we have 3 level tree. In that case, leaves and nodes will be printed in a depth-first order, making it pretty hard to locate level 1 nodes. This patch will use breadth-first search for btrfs_print_tree(). It will use btrfs_path::lowest_level to indicate current level, and print out tree blocks level by level (breadth-first). Signed-off-by: Qu Wenruo <wqu@suse.com> --- print-tree.c | 99 ++++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 73 insertions(+), 26 deletions(-) diff --git a/print-tree.c b/print-tree.c index 31f6fa12522f..0509ec3da46e 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; @@ -1389,7 +1461,6 @@ 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; @@ -1431,30 +1502,6 @@ 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); - } - + bfs_print_children(eb); return; } -- 2.18.0 ^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [PATCH 4/4] btrfs-progs: print-tree: Use breadth-first search for btrfs_print_tree() 2018-09-05 6:29 ` [PATCH 4/4] btrfs-progs: print-tree: Use breadth-first search for btrfs_print_tree() Qu Wenruo @ 2018-09-05 12:46 ` Nikolay Borisov 0 siblings, 0 replies; 9+ messages in thread From: Nikolay Borisov @ 2018-09-05 12:46 UTC (permalink / raw) To: Qu Wenruo, linux-btrfs On 5.09.2018 09:29, Qu Wenruo wrote: > btrfs_print_tree() uses depth-first search to print a subtree, it works > fine until we have 3 level tree. > > In that case, leaves and nodes will be printed in a depth-first order, > making it pretty hard to locate level 1 nodes. > > This patch will use breadth-first search for btrfs_print_tree(). > It will use btrfs_path::lowest_level to indicate current level, and > print out tree blocks level by level (breadth-first). > > Signed-off-by: Qu Wenruo <wqu@suse.com> Reviewed-by: Nikolay Borisov <nborisov@suse.com> > --- > print-tree.c | 99 ++++++++++++++++++++++++++++++++++++++-------------- > 1 file changed, 73 insertions(+), 26 deletions(-) > > diff --git a/print-tree.c b/print-tree.c > index 31f6fa12522f..0509ec3da46e 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); So what you do here is really get the leftmost item at until level 'cur_level'. > + if (ret < 0) > + goto out; > + > + /* Print all sibling tree blocks */ > + while (1) { > + btrfs_print_tree(path.nodes[cur_level], 0); Then you print the block. > + ret = btrfs_next_sibling_tree_block(fs_info, &path); And this just loads the next block at level 'cur_level', representing the "breadth" portion. > + 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; > @@ -1389,7 +1461,6 @@ 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; > @@ -1431,30 +1502,6 @@ 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); > - } > - > + bfs_print_children(eb); > return; > } > ^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2018-09-05 17:16 UTC | newest] Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2018-09-05 6:29 [PATCH 0/4] btrfs-progs: print-tree: breadth-first tree print order Qu Wenruo 2018-09-05 6:29 ` [PATCH 1/4] btrfs-progs: print-tree: Skip deprecated blockptr / nodesize output Qu Wenruo 2018-09-05 7:42 ` Nikolay Borisov 2018-09-05 6:29 ` [PATCH 2/4] btrfs-progs: Replace root parameter using fs_info for reada_for_search() Qu Wenruo 2018-09-05 7:42 ` Nikolay Borisov 2018-09-05 6:29 ` [PATCH 3/4] btrfs-progs: Introduce function to find next sibling tree block Qu Wenruo 2018-09-05 8:46 ` Nikolay Borisov 2018-09-05 6:29 ` [PATCH 4/4] btrfs-progs: print-tree: Use breadth-first search for btrfs_print_tree() Qu Wenruo 2018-09-05 12:46 ` Nikolay Borisov
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.