These patches do the following:
001 - 002: Small cleanup to maple tree.
003 - 006: Improve the validation for maple tree.
007 - 008: Drop some functions that will no longer be used.
Thanks Liam for the review.
Changes since v1:
- Add fixes tag and the necessary Cc. [1/8]
- Add the verification that gaps beyond the node limit are zero. [3/8]
- Revise comment. [5/8]
- Reformat the code. [6/8]
Peng Zhang (8):
maple_tree: set the node limit when creating a new root node
maple_tree: don't use MAPLE_ARANGE64_META_MAX to indicate no gap
maple_tree: make mas_validate_gaps() to check metadata
maple_tree: fix mas_validate_child_slot() to check last missed slot
maple_tree: make mas_validate_limits() check root node and node limit
maple_tree: update mt_validate()
maple_tree: replace mas_logical_pivot() with mas_safe_pivot()
maple_tree: drop mas_first_entry()
include/linux/maple_tree.h | 2 -
lib/maple_tree.c | 258 ++++++++++++-------------------------
2 files changed, 79 insertions(+), 181 deletions(-)
--
2.20.1
Set the node limit of the root node so that the last pivot of all nodes
is the node limit (if the node is not full).
This patch also fixes a bug in mas_rev_awalk(). Effectively, always
setting a maximum makes mas_logical_pivot() behave as mas_safe_pivot().
Without this fix, it is possible that very small tasks would fail to
find the correct gap. Although this has not been observed with real
tasks, it has been reported to happen in m68k nommu running the maple
tree tests.
Link: https://lore.kernel.org/linux-mm/CAMuHMdV4T53fOw7VPoBgPR7fP6RYqf=CBhD_y_vOg53zZX_DnA@mail.gmail.com/
Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Signed-off-by: Peng Zhang <[email protected]>
Reviewed-by: Liam R. Howlett <[email protected]>
Cc: <[email protected]>
Cc: Geert Uytterhoeven <[email protected]>
---
lib/maple_tree.c | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index d3072858c280..f55e59bd9122 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3692,7 +3692,8 @@ static inline int mas_root_expand(struct ma_state *mas, void *entry)
mas->offset = slot;
pivots[slot] = mas->last;
if (mas->last != ULONG_MAX)
- slot++;
+ pivots[++slot] = ULONG_MAX;
+
mas->depth = 1;
mas_set_height(mas);
ma_set_meta(node, maple_leaf_64, 0, slot);
--
2.20.1
Instead of using mas_first_entry() to find the leftmost leaf, use a
simple loop instead. Remove an unneeded check for root node. To make
the error message more accurate, check pivots first and then slots,
because checking slots depend on the node limit pivot to break the loop.
Signed-off-by: Peng Zhang <[email protected]>
---
lib/maple_tree.c | 19 +++++++++----------
1 file changed, 9 insertions(+), 10 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 072532fa18ee..1ad11799e197 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -7270,21 +7270,20 @@ void mt_validate(struct maple_tree *mt)
if (!mas_searchable(&mas))
goto done;
- mas_first_entry(&mas, mas_mn(&mas), ULONG_MAX, mte_node_type(mas.node));
+ while (!mte_is_leaf(mas.node))
+ mas_descend(&mas);
+
while (!mas_is_none(&mas)) {
MAS_WARN_ON(&mas, mte_dead_node(mas.node));
- if (!mte_is_root(mas.node)) {
- end = mas_data_end(&mas);
- if (MAS_WARN_ON(&mas,
- (end < mt_min_slot_count(mas.node)) &&
- (mas.max != ULONG_MAX))) {
- pr_err("Invalid size %u of %p\n", end,
- mas_mn(&mas));
- }
+ end = mas_data_end(&mas);
+ if (MAS_WARN_ON(&mas, (end < mt_min_slot_count(mas.node)) &&
+ (mas.max != ULONG_MAX))) {
+ pr_err("Invalid size %u of %p\n", end, mas_mn(&mas));
}
+
mas_validate_parent_slot(&mas);
- mas_validate_child_slot(&mas);
mas_validate_limits(&mas);
+ mas_validate_child_slot(&mas);
if (mt_is_alloc(mt))
mas_validate_gaps(&mas);
mas_dfs_postorder(&mas, ULONG_MAX);
--
2.20.1
Hi Peng,
On Tue, Jul 11, 2023 at 5:56 AM Peng Zhang <[email protected]> wrote:
> These patches do the following:
> 001 - 002: Small cleanup to maple tree.
> 003 - 006: Improve the validation for maple tree.
> 007 - 008: Drop some functions that will no longer be used.
>
> Thanks Liam for the review.
>
> Changes since v1:
> - Add fixes tag and the necessary Cc. [1/8]
> - Add the verification that gaps beyond the node limit are zero. [3/8]
> - Revise comment. [5/8]
> - Reformat the code. [6/8]
>
> Peng Zhang (8):
> maple_tree: set the node limit when creating a new root node
> maple_tree: don't use MAPLE_ARANGE64_META_MAX to indicate no gap
> maple_tree: make mas_validate_gaps() to check metadata
> maple_tree: fix mas_validate_child_slot() to check last missed slot
> maple_tree: make mas_validate_limits() check root node and node limit
> maple_tree: update mt_validate()
> maple_tree: replace mas_logical_pivot() with mas_safe_pivot()
> maple_tree: drop mas_first_entry()
>
> include/linux/maple_tree.h | 2 -
> lib/maple_tree.c | 258 ++++++++++++-------------------------
> 2 files changed, 79 insertions(+), 181 deletions(-)
Thanks for your series!
I gave it a try with test_maple_tree on m68k/ARAnyM, and the net
impact is:
TEST STARTING
BUG at next_prev_test:2014 (1)
Pass: 3749128 Run:3749129
-BUG at check_empty_area_window:2655 (1)
-Pass: 3754275 Run:3754277
-BUG at check_empty_area_window:2656 (1)
-Pass: 3754275 Run:3754278
-BUG at check_empty_area_window:2657 (1)
-Pass: 3754275 Run:3754279
-BUG at check_empty_area_window:2661 (1)
-Pass: 3754275 Run:3754280
-BUG at check_empty_area_window:2662 (1)
-Pass: 3754275 Run:3754281
-maple_tree: 3804518 of 3804524 tests passed
+maple_tree: 3804523 of 3804524 tests passed
So only one bug left to squash ;-)
Tested-by: Geert Uytterhoeven <[email protected]>
Gr{oetje,eeting}s,
Geert
--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- [email protected]
In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
-- Linus Torvalds
* Peng Zhang <[email protected]> [230710 23:55]:
> Instead of using mas_first_entry() to find the leftmost leaf, use a
> simple loop instead. Remove an unneeded check for root node. To make
> the error message more accurate, check pivots first and then slots,
> because checking slots depend on the node limit pivot to break the loop.
>
> Signed-off-by: Peng Zhang <[email protected]>
Reviewed-by: Liam R. Howlett <[email protected]>
> ---
> lib/maple_tree.c | 19 +++++++++----------
> 1 file changed, 9 insertions(+), 10 deletions(-)
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 072532fa18ee..1ad11799e197 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -7270,21 +7270,20 @@ void mt_validate(struct maple_tree *mt)
> if (!mas_searchable(&mas))
> goto done;
>
> - mas_first_entry(&mas, mas_mn(&mas), ULONG_MAX, mte_node_type(mas.node));
> + while (!mte_is_leaf(mas.node))
> + mas_descend(&mas);
> +
> while (!mas_is_none(&mas)) {
> MAS_WARN_ON(&mas, mte_dead_node(mas.node));
> - if (!mte_is_root(mas.node)) {
> - end = mas_data_end(&mas);
> - if (MAS_WARN_ON(&mas,
> - (end < mt_min_slot_count(mas.node)) &&
> - (mas.max != ULONG_MAX))) {
> - pr_err("Invalid size %u of %p\n", end,
> - mas_mn(&mas));
> - }
> + end = mas_data_end(&mas);
> + if (MAS_WARN_ON(&mas, (end < mt_min_slot_count(mas.node)) &&
> + (mas.max != ULONG_MAX))) {
> + pr_err("Invalid size %u of %p\n", end, mas_mn(&mas));
> }
> +
> mas_validate_parent_slot(&mas);
> - mas_validate_child_slot(&mas);
> mas_validate_limits(&mas);
> + mas_validate_child_slot(&mas);
> if (mt_is_alloc(mt))
> mas_validate_gaps(&mas);
> mas_dfs_postorder(&mas, ULONG_MAX);
> --
> 2.20.1
>
>
> --
> maple-tree mailing list
> [email protected]
> https://lists.infradead.org/mailman/listinfo/maple-tree
* Geert Uytterhoeven <[email protected]> [230711 06:10]:
> Hi Peng,
>
> On Tue, Jul 11, 2023 at 5:56 AM Peng Zhang <[email protected]> wrote:
> > These patches do the following:
> > 001 - 002: Small cleanup to maple tree.
> > 003 - 006: Improve the validation for maple tree.
> > 007 - 008: Drop some functions that will no longer be used.
> >
> > Thanks Liam for the review.
> >
> > Changes since v1:
> > - Add fixes tag and the necessary Cc. [1/8]
> > - Add the verification that gaps beyond the node limit are zero. [3/8]
> > - Revise comment. [5/8]
> > - Reformat the code. [6/8]
> >
> > Peng Zhang (8):
> > maple_tree: set the node limit when creating a new root node
> > maple_tree: don't use MAPLE_ARANGE64_META_MAX to indicate no gap
> > maple_tree: make mas_validate_gaps() to check metadata
> > maple_tree: fix mas_validate_child_slot() to check last missed slot
> > maple_tree: make mas_validate_limits() check root node and node limit
> > maple_tree: update mt_validate()
> > maple_tree: replace mas_logical_pivot() with mas_safe_pivot()
> > maple_tree: drop mas_first_entry()
> >
> > include/linux/maple_tree.h | 2 -
> > lib/maple_tree.c | 258 ++++++++++++-------------------------
> > 2 files changed, 79 insertions(+), 181 deletions(-)
>
> Thanks for your series!
>
> I gave it a try with test_maple_tree on m68k/ARAnyM, and the net
> impact is:
>
> TEST STARTING
>
> BUG at next_prev_test:2014 (1)
> Pass: 3749128 Run:3749129
> -BUG at check_empty_area_window:2655 (1)
> -Pass: 3754275 Run:3754277
> -BUG at check_empty_area_window:2656 (1)
> -Pass: 3754275 Run:3754278
> -BUG at check_empty_area_window:2657 (1)
> -Pass: 3754275 Run:3754279
> -BUG at check_empty_area_window:2661 (1)
> -Pass: 3754275 Run:3754280
> -BUG at check_empty_area_window:2662 (1)
> -Pass: 3754275 Run:3754281
> -maple_tree: 3804518 of 3804524 tests passed
> +maple_tree: 3804523 of 3804524 tests passed
>
> So only one bug left to squash ;-)
That one is a bug for 32b in the test, I have two fixes and I'll send
them soon.
Thanks for re-testing.
Regards,
Liam