The patch titled
Subject: maple_tree: try harder to keep active node with mas_prev()
has been added to the -mm mm-unstable branch. Its filename is
maple_tree-try-harder-to-keep-active-node-with-mas_prev.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-with-mas_prev.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 with mas_prev()
Date: Thu, 18 May 2023 10:55:33 -0400
Keep a reference to the node when possible with mas_prev(). This will
avoid re-walking the tree. In keeping a reference to the node, keep the
last/index accurate to the range being referenced. This means the limit
may be within the range, but the range may extend outside of the limit.
Also fix the single entry tree to respect the range (of 0), or set the
node to MAS_NONE in the case of shifting beyond 0.
Link: https://lkml.kernel.org/r/20230518145544.1722059-25-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 | 125 +++++++++++++++++++++++++++++----------------
1 file changed, 83 insertions(+), 42 deletions(-)
--- a/lib/maple_tree.c~maple_tree-try-harder-to-keep-active-node-with-mas_prev
+++ a/lib/maple_tree.c
@@ -4828,7 +4828,7 @@ static inline void *mas_prev_nentry(stru
unsigned long index)
{
unsigned long pivot, min;
- unsigned char offset;
+ unsigned char offset, count;
struct maple_node *mn;
enum maple_type mt;
unsigned long *pivots;
@@ -4842,29 +4842,42 @@ retry:
mn = mas_mn(mas);
mt = mte_node_type(mas->node);
offset = mas->offset - 1;
- if (offset >= mt_slots[mt])
- offset = mt_slots[mt] - 1;
-
slots = ma_slots(mn, mt);
pivots = ma_pivots(mn, mt);
+ count = ma_data_end(mn, mt, pivots, mas->max);
if (unlikely(ma_dead_node(mn))) {
mas_rewalk(mas, index);
goto retry;
}
- if (offset == mt_pivots[mt])
+ offset = mas->offset - 1;
+ if (offset >= mt_slots[mt])
+ offset = mt_slots[mt] - 1;
+
+ if (offset >= count) {
pivot = mas->max;
- else
+ offset = count;
+ } else {
pivot = pivots[offset];
+ }
if (unlikely(ma_dead_node(mn))) {
mas_rewalk(mas, index);
goto retry;
}
- while (offset && ((!mas_slot(mas, slots, offset) && pivot >= limit) ||
- !pivot))
+ while (offset && !mas_slot(mas, slots, offset)) {
pivot = pivots[--offset];
+ if (pivot >= limit)
+ break;
+ }
+
+ /*
+ * If the slot was null but we've shifted outside the limits, then set
+ * the range to the last NULL.
+ */
+ if (unlikely((pivot < limit) && (offset < mas->offset)))
+ pivot = pivots[++offset];
min = mas_safe_min(mas, pivots, offset);
entry = mas_slot(mas, slots, offset);
@@ -4873,32 +4886,33 @@ retry:
goto retry;
}
- if (likely(entry)) {
- mas->offset = offset;
- mas->last = pivot;
- mas->index = min;
- }
+ mas->offset = offset;
+ mas->last = pivot;
+ mas->index = min;
return entry;
}
static inline void *mas_prev_entry(struct ma_state *mas, unsigned long min)
{
void *entry;
+ struct maple_enode *prev_enode;
+ unsigned char prev_offset;
- if (mas->index < min) {
- mas->index = mas->last = min;
- mas->node = MAS_NONE;
+ if (mas->index < min)
return NULL;
- }
+
retry:
+ prev_enode = mas->node;
+ prev_offset = mas->offset;
while (likely(!mas_is_none(mas))) {
entry = mas_prev_nentry(mas, min, mas->index);
- if (unlikely(mas->last < min))
- goto not_found;
if (likely(entry))
return entry;
+ if (unlikely(mas->index <= min))
+ return NULL;
+
if (unlikely(mas_prev_node(mas, min))) {
mas_rewalk(mas, mas->index);
goto retry;
@@ -4907,9 +4921,8 @@ retry:
mas->offset++;
}
- mas->offset--;
-not_found:
- mas->index = mas->last = min;
+ mas->node = prev_enode;
+ mas->offset = prev_offset;
return NULL;
}
@@ -5952,15 +5965,8 @@ EXPORT_SYMBOL_GPL(mt_next);
*/
void *mas_prev(struct ma_state *mas, unsigned long min)
{
- if (!mas->index) {
- /* Nothing comes before 0 */
- mas->last = 0;
- mas->node = MAS_NONE;
- return NULL;
- }
-
- if (unlikely(mas_is_ptr(mas)))
- return NULL;
+ if (mas->index <= min)
+ goto none;
if (mas_is_none(mas) || mas_is_paused(mas))
mas->node = MAS_START;
@@ -5968,19 +5974,30 @@ void *mas_prev(struct ma_state *mas, uns
if (mas_is_start(mas)) {
mas_walk(mas);
if (!mas->index)
- return NULL;
+ goto none;
}
- if (mas_is_ptr(mas)) {
- if (!mas->index) {
- mas->last = 0;
- return NULL;
- }
-
+ if (unlikely(mas_is_ptr(mas))) {
+ if (!mas->index)
+ goto none;
mas->index = mas->last = 0;
- return mas_root_locked(mas);
+ return mas_root(mas);
+ }
+
+ if (mas_is_none(mas)) {
+ if (mas->index) {
+ /* Walked to out-of-range pointer? */
+ mas->index = mas->last = 0;
+ mas->node = MAS_ROOT;
+ return mas_root(mas);
+ }
+ return NULL;
}
return mas_prev_entry(mas, min);
+
+none:
+ mas->node = MAS_NONE;
+ return NULL;
}
EXPORT_SYMBOL_GPL(mas_prev);
@@ -6106,8 +6123,16 @@ EXPORT_SYMBOL_GPL(mas_find);
*/
void *mas_find_rev(struct ma_state *mas, unsigned long min)
{
+ if (unlikely(mas_is_none(mas))) {
+ if (mas->index <= min)
+ goto none;
+
+ mas->last = mas->index;
+ mas->node = MAS_START;
+ }
+
if (unlikely(mas_is_paused(mas))) {
- if (unlikely(mas->last == ULONG_MAX)) {
+ if (unlikely(mas->index <= min)) {
mas->node = MAS_NONE;
return NULL;
}
@@ -6127,14 +6152,30 @@ void *mas_find_rev(struct ma_state *mas,
return entry;
}
- if (unlikely(!mas_searchable(mas)))
- return NULL;
+ if (unlikely(!mas_searchable(mas))) {
+ if (mas_is_ptr(mas))
+ goto none;
+
+ if (mas_is_none(mas)) {
+ /*
+ * Walked to the location, and there was nothing so the
+ * previous location is 0.
+ */
+ mas->last = mas->index = 0;
+ mas->node = MAS_ROOT;
+ return mas_root(mas);
+ }
+ }
if (mas->index < min)
return NULL;
/* Retries on dead nodes handled by mas_prev_entry */
return mas_prev_entry(mas, min);
+
+none:
+ mas->node = MAS_NONE;
+ return NULL;
}
EXPORT_SYMBOL_GPL(mas_find_rev);
_
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
