Extent tree search cleanups
David Sterba
maintainercover Extent tree search cleanups
The extent_io_tree search helpers take return parameters and many callers pass just NULL, which are checked and add a conditionals to some paths. Reorganize helpers to suit what callers need and drop unnecessary parameters, open code rbtree search loops and clean up some other parameters.
This could improve performance in some cases but it's mostly micro optimizations and I haven't done any measurements.
David Sterba (9):
btrfs: open code rbtree search into split_state
btrfs: open code rbtree search in insert_state
btrfs: lift start and end parameters to callers of insert_state
btrfs: pass bits by value not pointer for extent_state helpers
btrfs: add fast path for extent_state insertion
btrfs: remove node and parent parameters from insert_state
btrfs: open code inexact rbtree search in tree_search
btrfs: make tree search for insert more generic and use it for
tree_search
btrfs: unify tree search helper returning prev and next nodes
fs/btrfs/ctree.h | 4 +- fs/btrfs/extent_io.c | 316 +++++++++++++++++++++++-------------------- fs/btrfs/inode.c | 24 ++-- 3 files changed, 183 insertions(+), 161 deletions(-)
Signature · 1 line
2.36.1
David Sterba
maintainerPATCH 1/9 btrfs: open code rbtree search into split_state
Preparatory work to remove tree_insert from extent_io.c, the rbtree search loop is a known and simple so it can be open coded.
--- fs/btrfs/extent_io.c | 28 ++++++++++++++++++++++------ 1 file changed, 22 insertions(+), 6 deletions(-)
fs/btrfs/extent_io.c +22 -6
@@ -607,7 +607,8 @@ static int insert_state(struct extent_io_tree *tree,static int split_state (struct extent_io_tree *tree,struct extent_state *orig,struct extent_state *prealloc,u64 split) { -struct rb_node *node; +struct rb_node *parent =NULL ; +struct rb_node **node;if (tree->private_data &&is_data_inode (tree->private_data))btrfs_split_delalloc_extent (tree->private_data, orig, split);
@@ -617,12 +618,27 @@ static int split_state(struct extent_io_tree *tree, struct extent_state *orig, prealloc->state = orig->state; orig->start = split; - node =tree_insert (&tree->state, &orig->rb_node, prealloc->end, - &prealloc->rb_node,NULL ,NULL ); -if (node) { -free_extent_state (prealloc); -return -EEXIST ; + parent = &orig->rb_node; + node = &parent; +while (*node) { +struct tree_entry *entry; + + parent = *node; + entry = rb_entry(parent, struct tree_entry, rb_node); + +if (prealloc->end < entry->start) { + node = &(*node)->rb_left; + }else if (prealloc->end > entry->end) { + node = &(*node)->rb_right; + }else { +free_extent_state (prealloc); +return -EEXIST ; + } } + +rb_link_node (&prealloc->rb_node, parent, node); +rb_insert_color (&prealloc->rb_node, &tree->state); +return 0 ; }
Signature · 1 line
2.36.1
David Sterba
maintainerPATCH 2/9 btrfs: open code rbtree search in insert_state
In reply to David SterbaThe rbtree search is a known pattern and can be open coded, allowing to remove the tree_insert and further cleanups.
--- fs/btrfs/extent_io.c | 80 ++++++++++++++++++-------------------------- 1 file changed, 33 insertions(+), 47 deletions(-)
fs/btrfs/extent_io.c +33 -47
@@ -368,42 +368,6 @@ void free_extent_state(struct extent_state *state) } } -static struct rb_node *tree_insert (struct rb_root *root, -struct rb_node *search_start, -u64 offset, -struct rb_node *node, -struct rb_node ***p_in, -struct rb_node **parent_in) -{ -struct rb_node **p; -struct rb_node *parent =NULL ; -struct tree_entry *entry; - -if (p_in && parent_in) { - p = *p_in; - parent = *parent_in; - goto do_insert; - } - - p = search_start ? &search_start : &root->rb_node; -while (*p) { - parent = *p; - entry = rb_entry(parent, struct tree_entry, rb_node); - -if (offset < entry->start) - p = &(*p)->rb_left; -else if (offset > entry->end) - p = &(*p)->rb_right; -else -return parent; - } - -do_insert: -rb_link_node (node, parent, p); -rb_insert_color (node, root); -return NULL ; -} -/** * Search @tree for an entry that contains @offset. Such entry would have * entry->start <= offset && entry->end >= offset.
@@ -561,11 +525,12 @@ static void set_state_bits(struct extent_io_tree *tree,*/ static int insert_state (struct extent_io_tree *tree,struct extent_state *state,u64 start,u64 end, -struct rb_node ***p, -struct rb_node **parent, +struct rb_node ***node_in, +struct rb_node **parent_in,u32 *bits,struct extent_changeset *changeset) { -struct rb_node *node; +struct rb_node **node; +struct rb_node *parent;if (end < start) { btrfs_err(tree->fs_info,
@@ -577,15 +542,36 @@ static int insert_state(struct extent_io_tree *tree,set_state_bits (tree, state, bits, changeset); - node =tree_insert (&tree->state,NULL , end, &state->rb_node, p, parent); -if (node) { -struct extent_state *found; - found = rb_entry(node, struct extent_state, rb_node); -btrfs_err (tree->fs_info, -"found node %llu %llu on insert of %llu %llu" , - found->start, found->end, start, end); -return -EEXIST ; +/* Caller provides the exact tree location */ +if (node_in && parent_in) { + node = *node_in; + parent = *parent_in; + goto insert_new; } + + node = &tree->state.rb_node; +while (*node) { +struct tree_entry *entry; + + parent = *node; + entry = rb_entry(parent, struct tree_entry, rb_node); + +if (end < entry->start) { + node = &(*node)->rb_left; + }else if (end > entry->end) { + node = &(*node)->rb_right; + }else { +btrfs_err (tree->fs_info, +"found node %llu %llu on insert of %llu %llu" , + entry->start, entry->end, start, end); +return -EEXIST ; + } + } + +insert_new: +rb_link_node (&state->rb_node, parent, node); +rb_insert_color (&state->rb_node, &tree->state); +merge_state (tree, state);return 0 ; }
Signature · 1 line
2.36.1
David Sterba
maintainerPATCH 3/9 btrfs: lift start and end parameters to callers of insert_state
In reply to David SterbaLet callers of insert_state to set up the extent state to allow further simplifications of the parameters.
--- fs/btrfs/extent_io.c | 33 +++++++++++++++------------------ 1 file changed, 15 insertions(+), 18 deletions(-)
fs/btrfs/extent_io.c +15 -18
@@ -524,21 +524,14 @@ static void set_state_bits(struct extent_io_tree *tree,* probably isn't what you want to call (see set/clear_extent_bit). */ static int insert_state (struct extent_io_tree *tree, -struct extent_state *state,u64 start,u64 end, +struct extent_state *state,struct rb_node ***node_in,struct rb_node **parent_in,u32 *bits,struct extent_changeset *changeset) {struct rb_node **node;struct rb_node *parent; - -if (end < start) { -btrfs_err (tree->fs_info, -"insert state: end < start %llu %llu" , end, start); -WARN_ON (1 ); - } - state->start = start; - state->end = end; +const u64 end = state->end;set_state_bits (tree, state, bits, changeset);
@@ -563,7 +556,7 @@ static int insert_state(struct extent_io_tree *tree, }else {btrfs_err (tree->fs_info,"found node %llu %llu on insert of %llu %llu" , - entry->start, entry->end, start, end); + entry->start, entry->end, state->start, end);return -EEXIST ; } }
@@ -1027,8 +1020,9 @@ int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bits,if (!node) { prealloc =alloc_extent_state_atomic (prealloc);BUG_ON (!prealloc); - err =insert_state (tree, prealloc, start, end, - &p, &parent, &bits, changeset); + prealloc->start = start; + prealloc->end = end; + err =insert_state (tree, prealloc, &p, &parent, &bits, changeset);if (err)extent_io_tree_panic (tree, err);
@@ -1144,8 +1138,9 @@ int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bits,* Avoid to free 'prealloc' if it can be merged with * the later extent. */ - err =insert_state (tree, prealloc, start, this_end, -NULL ,NULL , &bits, changeset); + prealloc->start = start; + prealloc->end = this_end; + err =insert_state (tree, prealloc,NULL ,NULL , &bits, changeset);if (err)extent_io_tree_panic (tree, err);
@@ -1268,8 +1263,9 @@ int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, err = -ENOMEM ; goto out; } - err =insert_state (tree, prealloc, start, end, - &p, &parent, &bits,NULL ); + prealloc->start = start; + prealloc->end = end; + err =insert_state (tree, prealloc, &p, &parent, &bits,NULL );if (err)extent_io_tree_panic (tree, err);cache_state (prealloc, cached_state);
@@ -1366,8 +1362,9 @@ int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,* Avoid to free 'prealloc' if it can be merged with * the later extent. */ - err =insert_state (tree, prealloc, start, this_end, -NULL ,NULL , &bits,NULL ); + prealloc->start = start; + prealloc->end = this_end; + err =insert_state (tree, prealloc,NULL ,NULL , &bits,NULL );if (err)extent_io_tree_panic (tree, err);cache_state (prealloc, cached_state);
Signature · 1 line
2.36.1
Re: [PATCH 3/9] btrfs: lift start and end parameters to callers of insert_state
Quoted 23 lines · David Sterba
Let callers of
insert_stateto set up the extent state to allow further simplifications of the parameters.Signed-off-by David Sterba <[email protected]>--- fs/btrfs/extent_io.c | 33 +++++++++++++++------------------ 1 file changed, 15 insertions(+), 18 deletions(-)fs/btrfs/extent_io.c +1
-1@@ -524,21 +524,14 @@ static void set_state_bits(struct extent_io_tree *tree,* probably isn't what you want to call (see set/clear_extent_bit). */ static int insert_state (struct extent_io_tree *tree, -struct extent_state *state,u64 start,u64 end, +struct extent_state *state,struct rb_node ***node_in,struct rb_node **parent_in,u32 *bits,struct extent_changeset *changeset) {struct rb_node **node;
fs/btrfs/extent_io.c static void set_state_bits(struct extent_io_tree *tree, · line 534
Quoted 10 lines
fs/btrfs/extent_io.c +1
-8struct rb_node *parent; - -if (end < start) { -btrfs_err (tree->fs_info, -"insert state: end < start %llu %llu" , end, start); -WARN_ON (1 ); - } - state->start = start; - state->end = end; +const u64 end = state->end;
Why do you need an explicit end when it's only used in the while loop and any possible changes actually come afterwards in case it's merged?
<snip>
Re: [PATCH 3/9] btrfs: lift start and end parameters to callers of insert_state
Quoted 31 lines · Nikolay Borisov
Quoted 28 lines · David Sterba
Let callers of
insert_stateto set up the extent state to allow further simplifications of the parameters.Signed-off-by David Sterba <[email protected]>--- fs/btrfs/extent_io.c | 33 +++++++++++++++------------------ 1 file changed, 15 insertions(+), 18 deletions(-)fs/btrfs/extent_io.c +1
-5@@ -524,21 +524,14 @@ static void set_state_bits(struct extent_io_tree *tree,* probably isn't what you want to call (see set/clear_extent_bit). */ static int insert_state (struct extent_io_tree *tree, -struct extent_state *state,u64 start,u64 end, +struct extent_state *state,struct rb_node ***node_in,struct rb_node **parent_in,u32 *bits,struct extent_changeset *changeset) {struct rb_node **node;struct rb_node *parent; - -if (end < start) { -btrfs_err (tree->fs_info, -"insert state: end < start %llu %llu" , end, start);
Quoted 8 lines
fs/btrfs/extent_io.c static void set_state_bits(struct extent_io_tree *tree, · line 534
Quoted 5 lines
fs/btrfs/extent_io.c +1
-4-WARN_ON (1 ); - } - state->start = start; - state->end = end; +const u64 end = state->end;Why do you need an explicit end when it's only used in the while loop and any possible changes actually come afterwards in case it's merged?
I think it's to minimize changes in the rest of the funciton, but you're right that end === state->end. Although caching the value in local variable could be a performance optimization for the tree search, I've compared both versions, the value is in a register in both and the non-cached also drops the stack allocation. So, I'll use state->end.
David Sterba
maintainerPATCH 4/9 btrfs: pass bits by value not pointer for extent_state helpers
In reply to David SterbaThe bits are passed to all extent state helpers for not apparent reason, the value only read and never updated so remove the indirection and pass directly. Also unify the type to u32 where needed.
--- fs/btrfs/ctree.h | 4 ++-- fs/btrfs/extent_io.c | 46 +++++++++++++++++++++----------------------- fs/btrfs/inode.c | 24 +++++++++++------------ 3 files changed, 36 insertions(+), 38 deletions(-)
fs/btrfs/ctree.h +2 -2
@@ -3320,9 +3320,9 @@ void btrfs_new_inode_args_destroy(struct btrfs_new_inode_args *args);struct inode *btrfs_new_subvol_inode (struct user_namespace *mnt_userns,struct inode *dir);void btrfs_set_delalloc_extent (struct inode *inode,struct extent_state *state, -unsigned *bits); +u32 bits);void btrfs_clear_delalloc_extent (struct inode *inode, -struct extent_state *state,unsigned *bits); +struct extent_state *state,u32 bits);void btrfs_merge_delalloc_extent (struct inode *inode,struct extent_state *new,struct extent_state *other); void btrfs_split_delalloc_extent(struct inode *inode,
fs/btrfs/extent_io.c +22 -24
154 lines not on this page · raw message
fs/btrfs/inode.c +12 -12
@@ -2274,18 +2274,18 @@ static void btrfs_del_delalloc_inode(struct btrfs_root *root,* list of inodes that have pending delalloc work to be done. */ void btrfs_set_delalloc_extent (struct inode *inode,struct extent_state *state, -unsigned *bits) +u32 bits) {struct btrfs_fs_info *fs_info =btrfs_sb (inode->i_sb); -if ((*bits &EXTENT_DEFRAG ) && !(*bits &EXTENT_DELALLOC )) +if ((bits &EXTENT_DEFRAG ) && !(bits &EXTENT_DELALLOC ))WARN_ON (1 );/* * set_bit and clear bit hooks normally require _irqsave/restore * but in this case, we are only testing for the DELALLOC * bit, which is only set or cleared with irqs on */ -if (!(state->state &EXTENT_DELALLOC ) && (*bits &EXTENT_DELALLOC )) { +if (!(state->state &EXTENT_DELALLOC ) && (bits &EXTENT_DELALLOC )) {struct btrfs_root *root =BTRFS_I (inode)->root;u64 len = state->end +1 - state->start;u32 num_extents =count_max_extents (len);
@@ -2303,7 +2303,7 @@ void btrfs_set_delalloc_extent(struct inode *inode, struct extent_state *state, fs_info->delalloc_batch);spin_lock (&BTRFS_I (inode)->lock);BTRFS_I (inode)->delalloc_bytes += len; -if (*bits &EXTENT_DEFRAG ) +if (bits &EXTENT_DEFRAG )BTRFS_I (inode)->defrag_bytes += len;if (do_list && !test_bit (BTRFS_INODE_IN_DELALLOC_LIST , &BTRFS_I (inode)->runtime_flags))
@@ -2312,7 +2312,7 @@ void btrfs_set_delalloc_extent(struct inode *inode, struct extent_state *state, }if (!(state->state &EXTENT_DELALLOC_NEW ) && - (*bits &EXTENT_DELALLOC_NEW )) { + (bits &EXTENT_DELALLOC_NEW )) {spin_lock (&BTRFS_I (inode)->lock);BTRFS_I (inode)->new_delalloc_bytes += state->end +1 - state->start;
@@ -2325,14 +2325,14 @@ void btrfs_set_delalloc_extent(struct inode *inode, struct extent_state *state,* accounting happens. */ void btrfs_clear_delalloc_extent (struct inode *vfs_inode, -struct extent_state *state,unsigned *bits) +struct extent_state *state,u32 bits) {struct btrfs_inode *inode =BTRFS_I (vfs_inode);struct btrfs_fs_info *fs_info =btrfs_sb (vfs_inode->i_sb);u64 len = state->end +1 - state->start;u32 num_extents =count_max_extents (len); -if ((state->state &EXTENT_DEFRAG ) && (*bits &EXTENT_DEFRAG )) { +if ((state->state &EXTENT_DEFRAG ) && (bits &EXTENT_DEFRAG )) {spin_lock (&inode->lock); inode->defrag_bytes -= len;spin_unlock (&inode->lock);
@@ -2343,7 +2343,7 @@ void btrfs_clear_delalloc_extent(struct inode *vfs_inode,* but in this case, we are only testing for the DELALLOC * bit, which is only set or cleared with irqs on */ -if ((state->state &EXTENT_DELALLOC ) && (*bits &EXTENT_DELALLOC )) { +if ((state->state &EXTENT_DELALLOC ) && (bits &EXTENT_DELALLOC )) {struct btrfs_root *root = inode->root;bool do_list = !btrfs_is_free_space_inode (inode);
@@ -2356,7 +2356,7 @@ void btrfs_clear_delalloc_extent(struct inode *vfs_inode,* don't need to call delalloc_release_metadata if there is an * error. */ -if (*bits &EXTENT_CLEAR_META_RESV && +if (bits &EXTENT_CLEAR_META_RESV && root != fs_info->tree_root)btrfs_delalloc_release_metadata (inode, len, false);
@@ -2366,7 +2366,7 @@ void btrfs_clear_delalloc_extent(struct inode *vfs_inode,if (!btrfs_is_data_reloc_root (root) && do_list && !(state->state &EXTENT_NORESERVE ) && - (*bits &EXTENT_CLEAR_DATA_RESV )) + (bits &EXTENT_CLEAR_DATA_RESV ))btrfs_free_reserved_data_space_noquota (fs_info, len); percpu_counter_add_batch(&fs_info->delalloc_bytes, -len,
@@ -2381,11 +2381,11 @@ void btrfs_clear_delalloc_extent(struct inode *vfs_inode, }if ((state->state &EXTENT_DELALLOC_NEW ) && - (*bits &EXTENT_DELALLOC_NEW )) { + (bits &EXTENT_DELALLOC_NEW )) {spin_lock (&inode->lock);ASSERT (inode->new_delalloc_bytes >= len); inode->new_delalloc_bytes -= len; -if (*bits &EXTENT_ADD_INODE_BYTES ) +if (bits &EXTENT_ADD_INODE_BYTES )inode_add_bytes (&inode->vfs_inode, len);spin_unlock (&inode->lock); }
Signature · 1 line
2.36.1
David Sterba
maintainerPATCH 5/9 btrfs: add fast path for extent_state insertion
In reply to David SterbaIn two cases the exact location where to insert the extent state is known at the call time so we don't need to pass it to insert_state that takes the fast path.
--- fs/btrfs/extent_io.c | 24 +++++++++++++++++------- 1 file changed, 17 insertions(+), 7 deletions(-)
fs/btrfs/extent_io.c +17 -7
@@ -569,6 +569,21 @@ static int insert_state(struct extent_io_tree *tree,return 0 ; } +/* +* Insert state to the tree to a location given by @p_ +*/ +static void insert_state_fast (struct extent_io_tree *tree, +struct extent_state *state, +struct rb_node **node, +struct rb_node *parent, +unsigned bits,struct extent_changeset *changeset) +{ +set_state_bits (tree, state, bits, changeset); +rb_link_node (&state->rb_node, parent, node); +rb_insert_color (&state->rb_node, &tree->state); +merge_state (tree, state); +} +/* * split a given extent state struct in two, inserting the preallocated * struct 'prealloc' as the newly created second half. 'split' indicates an
@@ -1021,10 +1036,7 @@ int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bits,BUG_ON (!prealloc); prealloc->start = start; prealloc->end = end; - err =insert_state (tree, prealloc, &p, &parent, bits, changeset); -if (err) -extent_io_tree_panic (tree, err); - +insert_state_fast (tree, prealloc, p, parent, bits, changeset);cache_state (prealloc, cached_state); prealloc =NULL ; goto out;
@@ -1264,9 +1276,7 @@ int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, } prealloc->start = start; prealloc->end = end; - err =insert_state (tree, prealloc, &p, &parent, bits,NULL ); -if (err) -extent_io_tree_panic (tree, err); +insert_state_fast (tree, prealloc, p, parent, bits,NULL );cache_state (prealloc, cached_state); prealloc =NULL ; goto out;
Signature · 1 line
2.36.1
Re: [PATCH 5/9] btrfs: add fast path for extent_state insertion
Quoted 14 lines · David Sterba
In two cases the exact location where to insert the extent state is known at the call time so we don't need to pass it to
insert_statethat takes the fast path.Signed-off-by David Sterba <[email protected]>--- fs/btrfs/extent_io.c | 24 +++++++++++++++++------- 1 file changed, 17 insertions(+), 7 deletions(-)fs/btrfs/extent_io.c +0
-0
fs/btrfs/extent_io.c static int insert_state(struct extent_io_tree *tree, · line 573
Quoted 5 lines
fs/btrfs/extent_io.c +2
-0@@ -569,6 +569,21 @@ static int insert_state(struct extent_io_tree *tree,return 0 ; } +/* +* Insert state to the tree to a location given by @p_
that @p_ seems incomplete?
<snip>
Re: [PATCH 5/9] btrfs: add fast path for extent_state insertion
Quoted 20 lines · Nikolay Borisov
Quoted 17 lines · David Sterba
In two cases the exact location where to insert the extent state is known at the call time so we don't need to pass it to
insert_statethat takes the fast path.Signed-off-by David Sterba <[email protected]>--- fs/btrfs/extent_io.c | 24 +++++++++++++++++------- 1 file changed, 17 insertions(+), 7 deletions(-)fs/btrfs/extent_io.c +0
-0@@ -569,6 +569,21 @@ static int insert_state(struct extent_io_tree *tree,return 0 ; }
Quoted 4 lines
fs/btrfs/extent_io.c static int insert_state(struct extent_io_tree *tree, · line 573
Quoted 2 lines
fs/btrfs/extent_io.c +2
-0+/* +* Insert state to the tree to a location given by @p_ that @p_ seems incomplete?
That's a typo and the variable got renamed to 'node', fixed.
David Sterba
maintainerPATCH 6/9 btrfs: remove node and parent parameters from insert_state
In reply to David SterbaThere's no caller left that would pass valid pointers to insert_state so we can drop them.
--- fs/btrfs/extent_io.c | 14 ++------------ 1 file changed, 2 insertions(+), 12 deletions(-)
fs/btrfs/extent_io.c +2 -12
@@ -525,8 +525,6 @@ static void set_state_bits(struct extent_io_tree *tree,*/ static int insert_state (struct extent_io_tree *tree,struct extent_state *state, -struct rb_node ***node_in, -struct rb_node **parent_in,u32 bits,struct extent_changeset *changeset) {struct rb_node **node;
@@ -535,13 +533,6 @@ static int insert_state(struct extent_io_tree *tree,set_state_bits (tree, state, bits, changeset); -/* Caller provides the exact tree location */ -if (node_in && parent_in) { - node = *node_in; - parent = *parent_in; - goto insert_new; - } - node = &tree->state.rb_node;while (*node) {struct tree_entry *entry;
@@ -561,7 +552,6 @@ static int insert_state(struct extent_io_tree *tree, } } -insert_new:rb_link_node (&state->rb_node, parent, node);rb_insert_color (&state->rb_node, &tree->state);
@@ -1151,7 +1141,7 @@ int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bits,*/ prealloc->start = start; prealloc->end = this_end; - err =insert_state (tree, prealloc,NULL ,NULL , bits, changeset); + err =insert_state (tree, prealloc, bits, changeset);if (err)extent_io_tree_panic (tree, err);
@@ -1372,7 +1362,7 @@ int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,*/ prealloc->start = start; prealloc->end = this_end; - err =insert_state (tree, prealloc,NULL ,NULL , bits,NULL ); + err =insert_state (tree, prealloc, bits,NULL );if (err)extent_io_tree_panic (tree, err);cache_state (prealloc, cached_state);
Signature · 1 line
2.36.1
David Sterba
maintainerPATCH 7/9 btrfs: open code inexact rbtree search in tree_search
In reply to David SterbaThe call chain from
tree_search
tree_search_for_insert
__etree_search
can be open coded and allow further simplifications, here we need a tree search with fallback to the next node in case it's not found. This is represented as __etree_search parameters next_ret=valid, prev_ret=NULL.
--- fs/btrfs/extent_io.c | 31 ++++++++++++++++++++++++++++--- 1 file changed, 28 insertions(+), 3 deletions(-)
fs/btrfs/extent_io.c +28 -3
@@ -453,10 +453,35 @@ tree_search_for_insert(struct extent_io_tree *tree,return ret; } -static inline struct rb_node *tree_search (struct extent_io_tree *tree, -u64 offset) +/* +* Inexact rb-tree search, return the next entry if @offset is not found +*/ +static inline struct rb_node *tree_search (struct extent_io_tree *tree,u64 offset) { -return tree_search_for_insert (tree, offset,NULL ,NULL ); +struct rb_root *root = &tree->state; +struct rb_node **node = &root->rb_node; +struct rb_node *prev =NULL ; +struct tree_entry *entry; + +while (*node) { + prev = *node; + entry = rb_entry(prev, struct tree_entry, rb_node); + +if (offset < entry->start) + node = &(*node)->rb_left; +else if (offset > entry->end) + node = &(*node)->rb_right; +else +return *node; + } + +/* Search neighbors until we find the first one past the end */ +while (prev && offset > entry->end) { + prev =rb_next (prev); + entry = rb_entry(prev, struct tree_entry, rb_node); + } + +return prev; }/*
Signature · 1 line
2.36.1
David Sterba
maintainerPATCH 8/9 btrfs: make tree search for insert more generic and use it for tree_search
In reply to David SterbaWith a slight extension of tree_search_for_insert (fill the return node and parent return parameters) we can avoid calling __etree_search from tree_search, that could be removed eventually in followup patches.
--- fs/btrfs/extent_io.c | 27 +++++++++++++-------------- 1 file changed, 13 insertions(+), 14 deletions(-)
fs/btrfs/extent_io.c +13 -14
@@ -443,20 +443,6 @@ tree_search_for_insert(struct extent_io_tree *tree,u64 offset, struct rb_node ***p_ret, struct rb_node **parent_ret) -{ - struct rb_node *next= NULL; -struct rb_node *ret; - - ret =__etree_search (tree, offset, &next,NULL , p_ret, parent_ret); -if (!ret) -return next; -return ret; -} - -/* -* Inexact rb-tree search, return the next entry if @offset is not found -*/ -static inline struct rb_node *tree_search (struct extent_io_tree *tree,u64 offset) { struct rb_root *root = &tree->state;struct rb_node **node = &root->rb_node;
@@ -475,6 +461,11 @@ static inline struct rb_node *tree_search(struct extent_io_tree *tree, u64 offsereturn *node; } +if (p_ret) + *p_ret = node; +if (parent_ret) + *parent_ret = prev; +/* Search neighbors until we find the first one past the end */ while (prev && offset > entry->end) { prev =rb_next (prev);
@@ -484,6 +475,14 @@ static inline struct rb_node *tree_search(struct extent_io_tree *tree, u64 offsereturn prev; } +/* +* Inexact rb-tree search, return the next entry if @offset is not found +*/ +static inline struct rb_node *tree_search (struct extent_io_tree *tree,u64 offset) +{ +return tree_search_for_insert (tree, offset,NULL ,NULL ); +} +/* * utility function to look for merge candidates inside a given range. * Any extents with matching state are merged together into a single
Signature · 1 line
2.36.1
David Sterba
maintainerPATCH 9/9 btrfs: unify tree search helper returning prev and next nodes
In reply to David SterbaSimplify helper to return only next and prev pointers, we don't need all the node/parent/prev/next pointers of __etree_search as there are now other specialized helpers. Rename parameters so they follow the naming.
--- fs/btrfs/extent_io.c | 113 ++++++++++++++++++++++--------------------- 1 file changed, 57 insertions(+), 56 deletions(-)
fs/btrfs/extent_io.c +57 -56
@@ -374,9 +374,7 @@ void free_extent_state(struct extent_state *state)* * @tree: the tree to search * @offset: offset that should fall within an entry in @tree -* @next_ret: pointer to the first entry whose range ends after @offset -* @prev_ret: pointer to the first entry whose range begins before @offset -* @p_ret: pointer where new node should be anchored (used when inserting an +* @node_ret: pointer where new node should be anchored (used when inserting an * entry in the tree) * @parent_ret: points to entry which would have been the parent of the entry, * containing @offset
@@ -386,69 +384,76 @@ void free_extent_state(struct extent_state *state)* pointer arguments to the function are filled, otherwise the found entry is * returned and other pointers are left untouched. */ -static struct rb_node *__etree_search (struct extent_io_tree *tree,u64 offset, -struct rb_node **next_ret, -struct rb_node **prev_ret, -struct rb_node ***p_ret, -struct rb_node **parent_ret) +static inline struct rb_node *tree_search_for_insert (struct extent_io_tree *tree, +u64 offset, +struct rb_node ***node_ret, +struct rb_node **parent_ret) {struct rb_root *root = &tree->state; -struct rb_node **n = &root->rb_node; +struct rb_node **node = &root->rb_node;struct rb_node *prev =NULL ; -struct rb_node *orig_prev =NULL ;struct tree_entry *entry; -struct tree_entry *prev_entry =NULL ; -while (*n) { - prev = *n; +while (*node) { + prev = *node; entry = rb_entry(prev, struct tree_entry, rb_node); - prev_entry = entry;if (offset < entry->start) - n = &(*n)->rb_left; + node = &(*node)->rb_left;else if (offset > entry->end) - n = &(*n)->rb_right; + node = &(*node)->rb_right;else -return *n; +return *node; } -if (p_ret) - *p_ret = n; +if (node_ret) + *node_ret = node;if (parent_ret) *parent_ret = prev; -if (next_ret) { - orig_prev = prev; -while (prev && offset > prev_entry->end) { - prev =rb_next (prev); - prev_entry = rb_entry(prev, struct tree_entry, rb_node); - } - *next_ret = prev; - prev = orig_prev; +/* Search neighbors until we find the first one past the end */ +while (prev && offset > entry->end) { + prev =rb_next (prev); + entry = rb_entry(prev, struct tree_entry, rb_node); } -if (prev_ret) { - prev_entry = rb_entry(prev, struct tree_entry, rb_node); -while (prev && offset < prev_entry->start) { - prev =rb_prev (prev); - prev_entry = rb_entry(prev, struct tree_entry, rb_node); - } - *prev_ret = prev; - } -return NULL ; +return prev; +} + +/* +* Inexact rb-tree search, return the next entry if @offset is not found +*/ +static inline struct rb_node *tree_search (struct extent_io_tree *tree,u64 offset) +{ +return tree_search_for_insert (tree, offset,NULL ,NULL ); } -static inline struct rb_node * -tree_search_for_insert (struct extent_io_tree *tree, -u64 offset, -struct rb_node ***p_ret, -struct rb_node **parent_ret) +/** +* Search offset in the tree or fill neighbor rbtree node pointers. +* +* @tree: the tree to search +* @offset: offset that should fall within an entry in @tree +* @next_ret: pointer to the first entry whose range ends after @offset +* @prev_ret: pointer to the first entry whose range begins before @offset +* +* Return a pointer to the entry that contains @offset byte address. If no +* such entry exists, then return NULL and fill @prev_ret and @next_ret. +* Otherwise return the found entry and other pointers are left untouched. +*/ +static struct rb_node *tree_search_prev_next (struct extent_io_tree *tree, +u64 offset, +struct rb_node **prev_ret, +struct rb_node **next_ret) {struct rb_root *root = &tree->state;struct rb_node **node = &root->rb_node;struct rb_node *prev =NULL ; +struct rb_node *orig_prev =NULL ;struct tree_entry *entry; +ASSERT (prev_ret); +ASSERT (next_ret); +while (*node) { prev = *node; entry = rb_entry(prev, struct tree_entry, rb_node);
@@ -461,26 +466,22 @@ tree_search_for_insert(struct extent_io_tree *tree,return *node; } -if (p_ret) - *p_ret = node; -if (parent_ret) - *parent_ret = prev; - -/* Search neighbors until we find the first one past the end */ + orig_prev = prev;while (prev && offset > entry->end) { prev =rb_next (prev); entry = rb_entry(prev, struct tree_entry, rb_node); } + *next_ret = prev; + prev = orig_prev; -return prev; -} + entry = rb_entry(prev, struct tree_entry, rb_node); +while (prev && offset < entry->start) { + prev =rb_prev (prev); + entry = rb_entry(prev, struct tree_entry, rb_node); + } + *prev_ret = prev; -/* -* Inexact rb-tree search, return the next entry if @offset is not found -*/ -static inline struct rb_node *tree_search (struct extent_io_tree *tree,u64 offset) -{ -return tree_search_for_insert (tree, offset,NULL ,NULL ); +return NULL ; }/*
@@ -1687,7 +1688,7 @@ void find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start,/* Find first extent with bits cleared */ while (1 ) { - node =__etree_search (tree, start, &next, &prev,NULL ,NULL ); + node =tree_search_prev_next (tree, start, &prev, &next);if (!node && !next && !prev) {/* * Tree is completely empty, send full range and let
Signature · 1 line
2.36.1
Re: [PATCH 9/9] btrfs: unify tree search helper returning prev and next nodes
Quoted 25 lines · David Sterba
Simplify helper to return only next and prev pointers, we don't need all the node/parent/prev/next pointers of
__etree_searchas there are now other specialized helpers. Rename parameters so they follow the naming.Signed-off-by David Sterba <[email protected]>--- fs/btrfs/extent_io.c | 113 ++++++++++++++++++++++--------------------- 1 file changed, 57 insertions(+), 56 deletions(-)fs/btrfs/extent_io.c +1
-3@@ -374,9 +374,7 @@ void free_extent_state(struct extent_state *state)* * @tree: the tree to search * @offset: offset that should fall within an entry in @tree -* @next_ret: pointer to the first entry whose range ends after @offset -* @prev_ret: pointer to the first entry whose range begins before @offset -* @p_ret: pointer where new node should be anchored (used when inserting an +* @node_ret: pointer where new node should be anchored (used when inserting an * entry in the tree) * @parent_ret: points to entry which would have been the parent of the entry, * containing @offset
fs/btrfs/extent_io.c void free_extent_state(struct extent_state *state) · line 386
Quoted 3 lines
fs/btrfs/extent_io.c +0
-0@@ -386,69 +384,76 @@ void free_extent_state(struct extent_state *state)* pointer arguments to the function are filled, otherwise the found entry is * returned and other pointers are left untouched. */
The comment should be changed as it's no longer valid. Currently it states:
If no such entry exists, then NULL is returned and the other
pointer arguments to the function are filled, otherwise the found entry is returned and other pointers are left untouched.
When no such entry exists, the other pointer arguments to the function are indeed filled, however the function now returns the first entry that ends _before_ the offset i.e this function can never return NULL.
So it return either the entry which contains 'offset' or the last entry before offset.
<snip>
Re: [PATCH 9/9] btrfs: unify tree search helper returning prev and next nodes
Quoted 38 lines · Nikolay Borisov
Quoted 25 lines · David Sterba
Simplify helper to return only next and prev pointers, we don't need all the node/parent/prev/next pointers of
__etree_searchas there are now other specialized helpers. Rename parameters so they follow the naming.Signed-off-by David Sterba <[email protected]>--- fs/btrfs/extent_io.c | 113 ++++++++++++++++++++++--------------------- 1 file changed, 57 insertions(+), 56 deletions(-)fs/btrfs/extent_io.c +1
-3@@ -374,9 +374,7 @@ void free_extent_state(struct extent_state *state)* * @tree: the tree to search * @offset: offset that should fall within an entry in @tree -* @next_ret: pointer to the first entry whose range ends after @offset -* @prev_ret: pointer to the first entry whose range begins before @offset -* @p_ret: pointer where new node should be anchored (used when inserting an +* @node_ret: pointer where new node should be anchored (used when inserting an * entry in the tree) * @parent_ret: points to entry which would have been the parent of the entry, * containing @offset fs/btrfs/extent_io.c void free_extent_state(struct extent_state *state) · line 386
Quoted 3 lines
fs/btrfs/extent_io.c +0
-0@@ -386,69 +384,76 @@ void free_extent_state(struct extent_state *state)* pointer arguments to the function are filled, otherwise the found entry is * returned and other pointers are left untouched. */ The comment should be changed as it's no longer valid. Currently it states:
If no such entry exists, then NULL is returned and the other pointer arguments to the function are filled, otherwise the found entry is returned and other pointers are left untouched.
Quoted 6 lines
When no such entry exists, the other pointer arguments to the function are indeed filled, however the function now returns the first entry that ends _before_ the offset i.e this function can never return NULL.
So it return either the entry which contains 'offset' or the last entry before offset.
Updated to:
+ * Return a pointer to the entry that contains @offset byte address and don't change + * @node_ret and @parent_ret. + * + * If no such entry exists, return pointer to entry that ends before @offset + * and fill parameters @node_ret and @parent_ret, ie. does not return NULL.
Quoted 9 lines · David Sterba
The
extent_io_treesearch helpers take return parameters and many callers pass just NULL, which are checked and add a conditionals to some paths. Reorganize helpers to suit what callers need and drop unnecessary parameters, open code rbtree search loops and clean up some other parameters.This could improve performance in some cases but it's mostly micro optimizations and I haven't done any measurements.
Quoted 11 lines
David Sterba (9):
btrfs: open code rbtree search intosplit_state
btrfs: open code rbtree search ininsert_state
btrfs: lift start and end parameters to callers ofinsert_state
btrfs: pass bits by value not pointer forextent_statehelpers
btrfs: add fast path forextent_stateinsertion
btrfs: remove node and parent parameters frominsert_state
btrfs: open code inexact rbtree search intree_search
btrfs: make tree search for insert more generic and use it for
tree_search
btrfs: unify tree search helper returning prev and next nodes
Added to misc-next.