diff options
| author | Liam R. Howlett <Liam.Howlett@oracle.com> | 2023-05-18 10:55:12 -0400 |
|---|---|---|
| committer | Andrew Morton <akpm@linux-foundation.org> | 2023-06-09 16:25:27 -0700 |
| commit | 633769c9267fadadffd31e27655bf028538238ad (patch) | |
| tree | 7e087d5b6b6f0ef2fd27e46dc7993abec52200e4 /lib | |
| parent | afc754c651b87093cd3293954f09fae589402fb0 (diff) | |
| download | lwn-633769c9267fadadffd31e27655bf028538238ad.tar.gz lwn-633769c9267fadadffd31e27655bf028538238ad.zip | |
maple_tree: avoid unnecessary ascending
The maple tree node limits are implied by the parent. When walking up the
tree, the limit may not be known until a slot that does not have implied
limits are encountered. However, if the node is the left-most or
right-most node, the walking up to find that limit can be skipped.
This commit also fixes the debug/testing code that was not setting the
limit on walking down the tree as that optimization is not compatible with
this change.
Link: https://lkml.kernel.org/r/20230518145544.1722059-4-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Reviewed-by: Peng Zhang <zhangpeng.00@bytedance.com>
Cc: David Binderman <dcb314@hotmail.com>
Cc: Sergey Senozhatsky <senozhatsky@chromium.org>
Cc: Vernon Yang <vernon2gm@gmail.com>
Cc: Wei Yang <richard.weiyang@gmail.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/maple_tree.c | 11 |
1 files changed, 8 insertions, 3 deletions
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 0471215e5761..ccd834d624ed 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1103,7 +1103,6 @@ static int mas_ascend(struct ma_state *mas) enum maple_type a_type; unsigned long min, max; unsigned long *pivots; - unsigned char offset; bool set_max = false, set_min = false; a_node = mas_mn(mas); @@ -1115,8 +1114,9 @@ static int mas_ascend(struct ma_state *mas) p_node = mte_parent(mas->node); if (unlikely(a_node == p_node)) return 1; + a_type = mas_parent_type(mas, mas->node); - offset = mte_parent_slot(mas->node); + mas->offset = mte_parent_slot(mas->node); a_enode = mt_mk_node(p_node, a_type); /* Check to make sure all parent information is still accurate */ @@ -1124,7 +1124,6 @@ static int mas_ascend(struct ma_state *mas) return 1; mas->node = a_enode; - mas->offset = offset; if (mte_is_root(a_enode)) { mas->max = ULONG_MAX; @@ -1132,6 +1131,12 @@ static int mas_ascend(struct ma_state *mas) return 0; } + if (!mas->min) + set_min = true; + + if (mas->max == ULONG_MAX) + set_max = true; + min = 0; max = ULONG_MAX; do { |