lib/maple_tree.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-)
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.
Signed-off-by: Gladyshev Ilya <foxido@foxido.dev>
---
lib/maple_tree.c | 10 +++++-----
1 file changed, 5 insertions(+), 5 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index b4ee2d29d7a9..c7790fff4825 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -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
--
2.51.0
* Gladyshev Ilya <foxido@foxido.dev> [250918 14:26]: > 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. 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. > > This patch unifies the rewind logic between mas_empty_area_rev and > mas_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? > > Signed-off-by: Gladyshev Ilya <foxido@foxido.dev> > --- > lib/maple_tree.c | 10 +++++----- > 1 file changed, 5 insertions(+), 5 deletions(-) > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > index b4ee2d29d7a9..c7790fff4825 100644 > --- a/lib/maple_tree.c > +++ b/lib/maple_tree.c > @@ -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 This does not make sense to me by inspection. > + 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? > + 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? > + else if (!mas_skip_node(mas)) > + return -EBUSY; Go to the next node, which would be larger addresses or return -EBUSY? > > > /* 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. > * Gladyshev Ilya <foxido@foxido.dev> [250918 14:26]: >> 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. > > 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. > >> >> This patch unifies the rewind logic between mas_empty_area_rev and >> mas_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 <foxido@foxido.dev> Date: Fri, 19 Sep 2025 20:00:26 +0300 Subject: [PATCH] maple: fix incorrect rewinding in empty_area functions todo: full description Signed-off-by: Gladyshev Ilya <foxido@foxido.dev> --- lib/maple_tree.c | 40 ++++++++++++++-------- tools/testing/radix-tree/maple.c | 57 ++++++++++++++++++++++++++++++++ 2 files changed, 84 insertions(+), 13 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index b4ee2d29d7a9..3cc1596e231b 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -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)) diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index 172700fb7784..bb424f94de1b 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -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::offset is too incorrect. + * 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: cbf658dd09419f1ef9de11b9604e950bdd5c170b -- 2.51.0
* Gladyshev Ilya <foxido@foxido.dev> [250919 13:14]: > 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. > > 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. > > > * Gladyshev Ilya <foxido@foxido.dev> [250918 14:26]: > >> 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. > > > > 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. > > > >> > >> This patch unifies the rewind logic between mas_empty_area_rev and > >> mas_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 <foxido@foxido.dev> > Date: Fri, 19 Sep 2025 20:00:26 +0300 > Subject: [PATCH] maple: fix incorrect rewinding in empty_area functions > > todo: full description > Signed-off-by: Gladyshev Ilya <foxido@foxido.dev> > --- > lib/maple_tree.c | 40 ++++++++++++++-------- > tools/testing/radix-tree/maple.c | 57 ++++++++++++++++++++++++++++++++ > 2 files changed, 84 insertions(+), 13 deletions(-) > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > index b4ee2d29d7a9..3cc1596e231b 100644 > --- a/lib/maple_tree.c > +++ b/lib/maple_tree.c > @@ -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)) > diff --git a/tools/testing/radix-tree/maple.c > b/tools/testing/radix-tree/maple.c > index 172700fb7784..bb424f94de1b 100644 > --- a/tools/testing/radix-tree/maple.c > +++ b/tools/testing/radix-tree/maple.c > @@ -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::offset is too incorrect. > + * 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: cbf658dd09419f1ef9de11b9604e950bdd5c170b > -- > 2.51.0 >
© 2016 - 2025 Red Hat, Inc.