maple: fix incorrect rewinding in mas_empty_area_rev
Subsystems (4)
PATCH RESEND 1/1 maple: fix incorrect rewinding in mas_empty_area_rev
Previously, mas_empty_area_rev was rewinding to the previous node if some offset was cached. This could lead to incorrect results because a useful gap could be skipped. However, this was never triggered in the kernel because mm subsystem calls mas_empty_area_rev on non cached mas.
This patch unifies the rewind logic between mas_empty_area_rev and mas_empty_area, so they both rewind in their correct directions.
--- lib/maple_tree.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-)
lib/maple_tree.c +5 -5
@@ -5138,15 +5138,15 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,if (mas_is_start (mas))mas_start (mas); -else if ((mas->offset <2 ) && (!mas_rewind_node (mas))) -return -EBUSY ;if (unlikely (mas_is_none (mas) ||mas_is_ptr (mas)))return mas_sparse_area (mas, min, max, size, false); -else if (mas->offset >=2 ) - mas->offset -=2 ; -else +else if (!mas->offset) mas->offset =mas_data_end (mas); +else if (mas->offset <=mas_data_end (mas) -2 ) + mas->offset = mas->offset +2 ; +else if (!mas_skip_node (mas)) +return -EBUSY ;/* The start of the window can only be within these values. */
base-commit: cbf658dd09419f1ef9de11b9604e950bdd5c170b
Signature · 1 line
2.51.0
Quoted 4 lines · Gladyshev Ilya
Previously,
mas_empty_area_revwas rewinding to the previous node if some offset was cached. This could lead to incorrect results because a useful gap could be skipped. However, this was never triggered in the kernel because mm subsystem callsmas_empty_area_revon non cached mas.
Can you please produce a test case, ideally in lib/test_maple_tree.c or tools/testing/radix_tree/maple.c that triggers your issue? I add all new tests to one of these places so the error does not return.
You can build maple in tools/testing/radix_tree/ and run it to run the tests.
It also helps understand the issue.
Quoted 3 lines
This patch unifies the rewind logic between
mas_empty_area_revandmas_empty_area, so they both rewind in their correct directions.
How are these unified? They are still different functions..? What is the correct direction, in your opinion?
Quoted 12 lines
Signed-off-by Gladyshev Ilya <[email protected]>--- lib/maple_tree.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-)lib/maple_tree.c +0
-0@@ -5138,15 +5138,15 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
lib/maple_tree.c int mas_empty_area_rev(struct ma_state *mas, unsigned long min, · line 5148
Quoted 10 lines
lib/maple_tree.c +0
-5if (mas_is_start (mas))mas_start (mas); -else if ((mas->offset <2 ) && (!mas_rewind_node (mas))) -return -EBUSY ;if (unlikely (mas_is_none (mas) ||mas_is_ptr (mas)))return mas_sparse_area (mas, min, max, size, false); -else if (mas->offset >=2 ) - mas->offset -=2 ; -else
This does not make sense to me by inspection.
lib/maple_tree.c int mas_empty_area_rev(struct ma_state *mas, unsigned long min, · line 5145
Quoted 2 lines
lib/maple_tree.c +1
-0+else if (!mas->offset) mas->offset =mas_data_end (mas);
If we are at the start of the node, go to the end of the node. If we are continuing the search, why are we restarting the same node?
lib/maple_tree.c int mas_empty_area_rev(struct ma_state *mas, unsigned long min, · line 5147
Quoted 2 lines
lib/maple_tree.c +2
-0+else if (mas->offset <=mas_data_end (mas) -2 ) + mas->offset = mas->offset +2 ;
If we are at the offset less than or equal 2 of the end of the node, we advance two slots. This is supposed to be going down but you are going up?
lib/maple_tree.c int mas_empty_area_rev(struct ma_state *mas, unsigned long min, · line 5149
Quoted 2 lines
lib/maple_tree.c +2
-0+else if (!mas_skip_node (mas)) +return -EBUSY ;
Go to the next node, which would be larger addresses or return -EBUSY?
Quoted 5 lines
lib/maple_tree.c +0
-0/* The start of the window can only be within these values. */ base-commit:
cbf658dd09419f1ef9de11b9604e950bdd5c170b
This function is to find a gap from top (highest) down (to lower) addresses. On entry, it needs to decrement the offset or go to the previous node. You are resetting to start from the end of the node or incrementing two slots. Failing that (which will only happen when we are within two of the end of a node), you will go to the NEXT node which seems the wrong direction?
Can you produce a test case that shows that we are skipping a gap?
Thanks,
Liam
On 9/18/25 23:20, Liam R. Howlett wrote:
Sorry, I kinda overrushed with this patch and it turned out it wasn't complete. I apologize for that
Below you can find new patch with regression tests. I'll ignore some of your comments (and some of them are fixed) for now, so we can find common ground about semantics of empty_area* functions and later, if it's really is a bug and not my misunderstanding, I will send v2 for review.
Quoted 13 lines · Gladyshev Ilya
Quoted 4 lines
Previously,
mas_empty_area_revwas rewinding to the previous node if some offset was cached. This could lead to incorrect results because a useful gap could be skipped. However, this was never triggered in the kernel because mm subsystem callsmas_empty_area_revon non cached mas.Can you please produce a test case, ideally in
lib/test_maple_tree.cortools/testing/radix_tree/maple.cthat triggers your issue? I add all new tests to one of these places so the error does not return.You can build maple in
tools/testing/radix_tree/and run it to run the tests.
Quoted 8 lines
It also helps understand the issue.
Quoted 3 lines
This patch unifies the rewind logic between
mas_empty_area_revandmas_empty_area, so they both rewind in their correct directions.How are these unified? They are still different functions..? What is the correct direction, in your opinion?
For mas_empty_area we should move towards first slot, for mas_empty_area_rev we should move towards last slot. In both cases empty_area function will rescan last saved child / gap and won't miss anything. From 17707e1117a4d4be23f257c3b911c0a36f55b116 Mon Sep 17 00:00:00 2001
From: Gladyshev Ilya <[email protected]>
Date: Fri, 19 Sep 2025 20:00:26 +0300
Subject: [PATCH] maple: fix incorrect rewinding in empty_area functions
todo: full description
--- lib/maple_tree.c | 40 ++++++++++++++-------- tools/testing/radix-tree/maple.c | 57 ++++++++++++++++++++++++++++++++ 2 files changed, 84 insertions(+), 13 deletions(-)
lib/maple_tree.c +17 -4
@@ -4985,13 +4985,10 @@ static inline bool mas_rewind_node(struct ma_state *mas)*/ static inline bool mas_skip_node (struct ma_state *mas) { -if (mas_is_err (mas)) -return false; - do { if (mte_is_root(mas->node)) { if (mas->offset >= mas_data_end(mas)) { - mas_set_err(mas, -EBUSY); + mas->offset = mas_data_end(mas); return false; } } else {
@@ -5003,6 +5000,22 @@ static inline bool mas_skip_node(struct ma_state *mas)return true; } +/* +* mas_skip_node_err() - Wraps mas_skip_node and errors if there is no next node +*/ +static inline bool mas_skip_node_err (struct ma_state *mas) +{ +if (mas_is_err (mas)) +return false; + +if (!mas_skip_node (mas)) { +mas_set_err (mas, -EBUSY ); +return false; + } + +return true; +} +/* * mas_awalk() - Allocation walk. Search from low address to high,
for a gap of
* @size
@@ -5024,7 +5037,7 @@ static inline void mas_awalk(struct ma_state *mas, unsigned long size)
*/
while (!mas_is_err(mas) && !mas_anode_descend(mas, size)) {
if (last == mas->node)
- mas_skip_node(mas);
+ mas_skip_node_err(mas);
else
last = mas->node;
}
@@ -5089,8 +5102,8 @@ int mas_empty_area(struct ma_state *mas, unsigned long min,
mas_start(mas);
else if (mas->offset >= 2)
mas->offset -= 2;
- else if (!mas_skip_node(mas))
- return -EBUSY;
+ else
+ mas_rewind_node(mas);
/* Empty set */
if (mas_is_none(mas) || mas_is_ptr(mas))
@@ -5128,7 +5141,7 @@ EXPORT_SYMBOL_GPL(mas_empty_area);
int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
unsigned long max, unsigned long size)
{
- struct maple_enode *last = mas->node;
+ struct maple_enode *last;
if (min > max)
return -EINVAL;
@@ -5138,21 +5151,22 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
if (mas_is_start(mas))
mas_start(mas);
- else if ((mas->offset < 2) && (!mas_rewind_node(mas)))
- return -EBUSY;
if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
return mas_sparse_area(mas, min, max, size, false);
- else if (mas->offset >= 2)
- mas->offset -= 2;
- else
+ else if (!mas->offset)
mas->offset = mas_data_end(mas);
+ else if (mas->offset <= mas_data_end(mas) - 2)
+ mas->offset = mas->offset + 2;
+ else
+ mas_skip_node(mas);
/* The start of the window can only be within these values. */ mas->index = min;
mas->last = max;
+ last = mas->node;
while (!mas_rev_awalk(mas, size, &min, &max)) {
if (last == mas->node) {
if (!mas_rewind_node(mas))
tools/testing/radix-tree/maple.c +57 -0
66 lines not on this page · raw message
base-commit: cbf658dd09419f1ef9de11b9604e950bdd5c170b
Signature · 1 line
2.51.0
Quoted 4 lines · Gladyshev Ilya
On 9/18/25 23:20, Liam R. Howlett wrote:
Sorry, I kinda overrushed with this patch and it turned out it wasn't complete. I apologize for that
Well, don't expect me to spend much time on this either, then.
Your testcases are wrong. You are not using the interface correctly and have broken the tree with this patch to pass an invalid test.
Quoted 227 lines
Below you can find new patch with regression tests. I'll ignore some of your comments (and some of them are fixed) for now, so we can find common ground about semantics of empty_area* functions and later, if it's really is a bug and not my misunderstanding, I will send v2 for review.
Quoted 13 lines · Gladyshev Ilya
Quoted 4 lines
Previously,
mas_empty_area_revwas rewinding to the previous node if some offset was cached. This could lead to incorrect results because a useful gap could be skipped. However, this was never triggered in the kernel because mm subsystem callsmas_empty_area_revon non cached mas.Can you please produce a test case, ideally in
lib/test_maple_tree.cortools/testing/radix_tree/maple.cthat triggers your issue? I add all new tests to one of these places so the error does not return.You can build maple in
tools/testing/radix_tree/and run it to run the tests.Quoted 8 lines
It also helps understand the issue.
Quoted 3 lines
This patch unifies the rewind logic between
mas_empty_area_revandmas_empty_area, so they both rewind in their correct directions.How are these unified? They are still different functions..? What is the correct direction, in your opinion?
For
mas_empty_areawe should move towards first slot, formas_empty_area_revwe should move towards last slot. In both casesempty_areafunction will rescan last saved child / gap and won't miss anything.
From17707e1117a4d4be23f257c3b911c0a36f55b116Mon Sep 17 00:00:00 2001
From: Gladyshev Ilya <[email protected]>
Date: Fri, 19 Sep 2025 20:00:26 +0300
Subject: [PATCH] maple: fix incorrect rewinding inempty_areafunctionstodo: full description
Signed-off-by Gladyshev Ilya <[email protected]>--- lib/maple_tree.c | 40 ++++++++++++++-------- tools/testing/radix-tree/maple.c | 57 ++++++++++++++++++++++++++++++++ 2 files changed, 84 insertions(+), 13 deletions(-)lib/maple_tree.c +1
-4@@ -4985,13 +4985,10 @@ static inline bool mas_rewind_node(struct ma_state*mas) */ static inline bool mas_skip_node (struct ma_state *mas) { -if (mas_is_err (mas)) -return false; - do { if (mte_is_root(mas->node)) { if (mas->offset >= mas_data_end(mas)) { - mas_set_err(mas, -EBUSY); + mas->offset = mas_data_end(mas); return false; }lib/maple_tree.c +2
-0}else {@@ -5003,6 +5000,22 @@ static inline bool mas_skip_node(struct ma_state *mas)return true; } +/* +* mas_skip_node_err() - Wraps mas_skip_node and errors if there is no next node
+ */lib/maple_tree.c +13
-0+static inline bool mas_skip_node_err (struct ma_state *mas) +{ +if (mas_is_err (mas)) +return false; + +if (!mas_skip_node (mas)) { +mas_set_err (mas, -EBUSY ); +return false; + } + +return true; +} +/* * mas_awalk() - Allocation walk. Search from low address to high, for a gap of
* @sizelib/maple_tree.c +1
-1@@ -5024,7 +5037,7 @@ static inline void mas_awalk(struct ma_state *mas,unsigned long size) */ while (!mas_is_err (mas) && !mas_anode_descend (mas, size)) {if (last == mas->node) -mas_skip_node (mas); +mas_skip_node_err (mas);else last = mas->node;lib/maple_tree.c +2
-2}@@ -5089,8 +5102,8 @@ int mas_empty_area(struct ma_state *mas, unsigned long min,mas_start (mas); else if (mas->offset >= 2) mas->offset -= 2; - else if (!mas_skip_node(mas)) - return -EBUSY; + else +mas_rewind_node (mas );/* Empty set */ lib/maple_tree.c +7
-6if (mas_is_none (mas) ||mas_is_ptr (mas))@@ -5128,7 +5141,7 @@ EXPORT_SYMBOL_GPL(mas_empty_area);int mas_empty_area_rev (struct ma_state *mas,unsigned long min,unsigned long max,unsigned long size) { -struct maple_enode *last = mas->node; +struct maple_enode *last;if (min > max)return -EINVAL ;@@ -5138,21 +5151,22 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min, if (mas_is_start(mas)) mas_start(mas); - else if ((mas->offset < 2) && (!mas_rewind_node(mas))) -return -EBUSY ;if (unlikely (mas_is_none (mas) ||mas_is_ptr (mas)))return mas_sparse_area (mas, min, max, size, false); -else if (mas->offset >=2 ) - mas->offset -=2 ; -else +else if (!mas->offset) mas->offset =mas_data_end (mas); +else if (mas->offset <=mas_data_end (mas) -2 ) + mas->offset = mas->offset +2 ; +else +mas_skip_node (mas);/* The start of the window can only be within these values. */ mas->index = min; mas->last = max; + last = mas->node;while (!mas_rev_awalk (mas, size, &min, &max)) {if (last == mas->node) {lib/maple_tree.c +0
-0if (!mas_rewind_node (mas))tools/testing/radix-tree/maple.c +14
-0@@ -36655,9 +36655,66 @@ static void test_spanning_store_regression(void)__mt_destroy (&tree); } +static void test_cached_empty_area_rev_regression (void ) +{ +struct maple_tree tree =MTREE_INIT (&tree,MT_FLAGS_ALLOC_RANGE ); +MA_STATE (mas, &tree,0 ,0 ); +void *const dataptr = (void *)0x13370 ; + +for (int i =1 ; i <=10 ; ++i) { +unsigned long start = i *10000 ; +unsigned long end = start +1000 ; +mas_set_range (&mas, start, end); +mas_store_gfp (&mas, dataptr,GFP_KERNEL ); + } + +/* NOTE: Still looks unneccecarry for me, but without it cached offset in
mas::offsetis too incorrect.tools/testing/radix-tree/maple.c +43
-0+* Probably couldn't be allowed without disabling caching at all +*/ +mas_reset (&mas); + +for (int i =1 ; i <10 ; ++i) { +/* NOTE: Wasn't working here without mas_reset */ +// mas_reset(&mas); +mas_empty_area_rev (&mas,0 ,200000 ,10 ); +BUG_ON (mas.index !=199991 ); + } + +/* Cleanup. */ +__mt_destroy (&tree); +} + +static void test_cached_empty_area_regression (void ) +{ +struct maple_tree tree =MTREE_INIT (&tree,MT_FLAGS_ALLOC_RANGE ); +MA_STATE (mas, &tree,0 ,0 ); +void *const dataptr = (void *)0x13370 ; + +for (int i =1 ; i <=10 ; ++i) { +unsigned long start = i *10000 ; +unsigned long end = start +1000 ; +mas_set_range (&mas, start, end); +mas_store_gfp (&mas, dataptr,GFP_KERNEL ); + } + +mas_reset (&mas); + +for (int i =1 ; i <10 ; ++i) { +/* NOTE: Wasn't working here without mas_reset */ +// mas_reset(&mas); +int res =mas_empty_area (&mas,0 ,200000 ,10 ); +BUG_ON (mas.index !=0 ); +BUG_ON (res); + } + +/* Cleanup. */ +__mt_destroy (&tree); +}static void regression_tests (void ) {test_spanning_store_regression (); +test_cached_empty_area_regression (); +test_cached_empty_area_rev_regression (); }void maple_tree_tests (void )base-commit:
cbf658dd09419f1ef9de11b9604e950bdd5c170bSignature · 1 line
2.51.0