The patch titled
Subject: maple_tree: try harder to keep active node after mas_next()
has been added to the -mm mm-unstable branch. Its filename is
maple_tree-try-harder-to-keep-active-node-after-mas_next.patch
This patch will shortly appear at
https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/maple_tree-try-harder-to-keep-active-node-after-mas_next.patch
This patch will later appear in the mm-unstable branch at
git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next via the mm-everything
branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there every 2-3 working days
------------------------------------------------------
From: "Liam R. Howlett" <Liam.Howlett@xxxxxxxxxx>
Subject: maple_tree: try harder to keep active node after mas_next()
Date: Fri, 12 May 2023 14:20:24 -0400
Clean up the mas_next() call to try and keep a node reference when
possible. This will avoid re-walking the tree in most cases.
Also clean up the single entry tree handling to ensure index/last are
consistent with what one would expect. (returning NULL with limit of
1-oo).
Link: https://lkml.kernel.org/r/20230512182036.359030-24-Liam.Howlett@xxxxxxxxxx
Signed-off-by: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>
Cc: David Binderman <dcb314@xxxxxxxxxxx>
Cc: Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx>
Cc: Sergey Senozhatsky <senozhatsky@xxxxxxxxxxxx>
Cc: Vernon Yang <vernon2gm@xxxxxxxxx>
Cc: Wei Yang <richard.weiyang@xxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
lib/maple_tree.c | 89 +++++++++++++++++++++++----------------------
1 file changed, 47 insertions(+), 42 deletions(-)
--- a/lib/maple_tree.c~maple_tree-try-harder-to-keep-active-node-after-mas_next
+++ a/lib/maple_tree.c
@@ -4727,33 +4727,25 @@ static inline void *mas_next_nentry(stru
if (ma_dead_node(node))
return NULL;
+ mas->last = pivot;
if (entry)
- goto found;
+ return entry;
if (pivot >= max)
return NULL;
+ if (pivot >= mas->max)
+ return NULL;
+
mas->index = pivot + 1;
mas->offset++;
}
- if (mas->index > mas->max) {
- mas->index = mas->last;
- return NULL;
- }
-
- pivot = mas_safe_pivot(mas, pivots, mas->offset, type);
+ pivot = mas_logical_pivot(mas, pivots, mas->offset, type);
entry = mas_slot(mas, slots, mas->offset);
if (ma_dead_node(node))
return NULL;
- if (!pivot)
- return NULL;
-
- if (!entry)
- return NULL;
-
-found:
mas->last = pivot;
return entry;
}
@@ -4782,21 +4774,15 @@ retry:
static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit)
{
void *entry = NULL;
- struct maple_enode *prev_node;
struct maple_node *node;
- unsigned char offset;
unsigned long last;
enum maple_type mt;
- if (mas->index > limit) {
- mas->index = mas->last = limit;
- mas_pause(mas);
+ if (mas->last >= limit)
return NULL;
- }
+
last = mas->last;
retry:
- offset = mas->offset;
- prev_node = mas->node;
node = mas_mn(mas);
mt = mte_node_type(mas->node);
mas->offset++;
@@ -4815,12 +4801,10 @@ retry:
if (likely(entry))
return entry;
- if (unlikely((mas->index > limit)))
- break;
+ if (unlikely((mas->last >= limit)))
+ return NULL;
next_node:
- prev_node = mas->node;
- offset = mas->offset;
if (unlikely(mas_next_node(mas, node, limit))) {
mas_rewalk(mas, last);
goto retry;
@@ -4830,9 +4814,6 @@ next_node:
mt = mte_node_type(mas->node);
}
- mas->index = mas->last = limit;
- mas->offset = offset;
- mas->node = prev_node;
return NULL;
}
@@ -5914,6 +5895,8 @@ EXPORT_SYMBOL_GPL(mas_expected_entries);
*/
void *mas_next(struct ma_state *mas, unsigned long max)
{
+ bool was_none = mas_is_none(mas);
+
if (mas_is_none(mas) || mas_is_paused(mas))
mas->node = MAS_START;
@@ -5921,16 +5904,16 @@ void *mas_next(struct ma_state *mas, uns
mas_walk(mas); /* Retries on dead nodes handled by mas_walk */
if (mas_is_ptr(mas)) {
- if (!mas->index) {
- mas->index = 1;
- mas->last = ULONG_MAX;
+ if (was_none && mas->index == 0) {
+ mas->index = mas->last = 0;
+ return mas_root(mas);
}
+ mas->index = 1;
+ mas->last = ULONG_MAX;
+ mas->node = MAS_NONE;
return NULL;
}
- if (mas->last == ULONG_MAX)
- return NULL;
-
/* Retries on dead nodes handled by mas_next_entry */
return mas_next_entry(mas, max);
}
@@ -6054,17 +6037,25 @@ EXPORT_SYMBOL_GPL(mas_pause);
*/
void *mas_find(struct ma_state *mas, unsigned long max)
{
+ if (unlikely(mas_is_none(mas))) {
+ if (unlikely(mas->last >= max))
+ return NULL;
+
+ mas->index = mas->last;
+ mas->node = MAS_START;
+ }
+
if (unlikely(mas_is_paused(mas))) {
- if (unlikely(mas->last == ULONG_MAX)) {
- mas->node = MAS_NONE;
+ if (unlikely(mas->last >= max))
return NULL;
- }
+
mas->node = MAS_START;
mas->index = ++mas->last;
}
- if (unlikely(mas_is_none(mas)))
- mas->node = MAS_START;
+
+ if (unlikely(mas_is_ptr(mas)))
+ goto ptr_out_of_range;
if (unlikely(mas_is_start(mas))) {
/* First run or continue */
@@ -6076,13 +6067,27 @@ void *mas_find(struct ma_state *mas, uns
entry = mas_walk(mas);
if (entry)
return entry;
+
}
- if (unlikely(!mas_searchable(mas)))
+ if (unlikely(!mas_searchable(mas))) {
+ if (unlikely(mas_is_ptr(mas)))
+ goto ptr_out_of_range;
+
+ return NULL;
+ }
+
+ if (mas->index == max)
return NULL;
/* Retries on dead nodes handled by mas_next_entry */
return mas_next_entry(mas, max);
+
+ptr_out_of_range:
+ mas->node = MAS_NONE;
+ mas->index = 1;
+ mas->last = ULONG_MAX;
+ return NULL;
}
EXPORT_SYMBOL_GPL(mas_find);
@@ -6513,7 +6518,7 @@ retry:
if (entry)
goto unlock;
- while (mas_searchable(&mas) && (mas.index < max)) {
+ while (mas_searchable(&mas) && (mas.last < max)) {
entry = mas_next_entry(&mas, max);
if (likely(entry && !xa_is_zero(entry)))
break;
_
Patches currently in -mm which might be from Liam.Howlett@xxxxxxxxxx are
maple_tree-fix-static-analyser-cppcheck-issue.patch
maple_tree-avoid-unnecessary-ascending.patch
maple_tree-clean-up-mas_dfs_postorder.patch
maple_tree-add-debug-bug_on-and-warn_on-variants.patch
maple_tree-use-mas_bug_on-when-setting-a-leaf-node-as-a-parent.patch
maple_tree-use-mas_bug_on-in-mas_set_height.patch
maple_tree-use-mas_bug_on-from-mas_topiary_range.patch
maple_tree-use-mas_wr_bug_on-in-mas_store_prealloc.patch
maple_tree-use-mas_bug_on-prior-to-calling-mas_meta_gap.patch
maple_tree-return-error-on-mte_pivots-out-of-range.patch
maple_tree-make-test-code-work-without-debug-enabled.patch
mm-update-validate_mm-to-use-vma-iterator.patch
mm-update-vma_iter_store-to-use-mas_warn_on.patch
maple_tree-add-__init-and-__exit-to-test-module.patch
maple_tree-remove-unnecessary-check-from-mas_destroy.patch
maple_tree-mas_start-reset-depth-on-dead-node.patch
mm-mmap-change-do_vmi_align_munmap-for-maple-tree-iterator-changes.patch
maple_tree-try-harder-to-keep-active-node-after-mas_next.patch
maple_tree-try-harder-to-keep-active-node-with-mas_prev.patch
maple_tree-revise-limit-checks-in-mas_empty_area_rev.patch
maple_tree-fix-testing-mas_empty_area.patch
maple_tree-introduce-mas_next_slot-interface.patch
maple_tree-add-mas_next_range-and-mas_find_range-interfaces.patch
maple_tree-relocate-mas_rewalk-and-mas_rewalk_if_dead.patch
maple_tree-introduce-mas_prev_slot-interface.patch
maple_tree-add-mas_prev_range-and-mas_find_range_rev-interface.patch
maple_tree-clear-up-index-and-last-setting-in-single-entry-tree.patch
maple_tree-update-testing-code-for-mas_nextprevwalk.patch
mm-add-vma_iter_nextprev_range-to-vma-iterator.patch
mm-avoid-rewalk-in-mmap_region.patch
