* Re: [PATCH RESEND] maple: fix incorrect rewinding in mas_empty_area_rev
[not found] ` <76e0b252-ecbe-4d86-b210-79eb803e0fd7@foxido.dev>
@ 2025-09-19 18:43 ` Liam R. Howlett
0 siblings, 0 replies; 2+ messages in thread
From: Liam R. Howlett @ 2025-09-19 18:43 UTC (permalink / raw)
To: Gladyshev Ilya; +Cc: Andrew Morton, maple-tree, linux-mm, linux-kernel
* 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
>
^ permalink raw reply [flat|nested] 2+ messages in thread