* Liam Howlett <liam.howlett@xxxxxxxxxx> [220404 10:45]:
> From: "Liam R. Howlett" <Liam.Howlett@xxxxxxxxxx>
>
> The maple tree is an RCU-safe range based B-tree designed to use modern
> processor cache efficiently. There are a number of places in the kernel
> that a non-overlapping range-based tree would be beneficial, especially
> one with a simple interface. The first user that is covered in this
> patch set is the vm_area_struct, where three data structures are
> replaced by the maple tree: the augmented rbtree, the vma cache, and the
> linked list of VMAs in the mm_struct. The long term goal is to reduce
> or remove the mmap_sem contention.
>
> The tree has a branching factor of 10 for non-leaf nodes and 16 for leaf
> nodes. With the increased branching factor, it is significantly shorter than
> the rbtree so it has fewer cache misses. The removal of the linked list
> between subsequent entries also reduces the cache misses and the need to pull
> in the previous and next VMA during many tree alterations.
>
> Signed-off-by: Matthew Wilcox (Oracle) <willy@xxxxxxxxxxxxx>
> Signed-off-by: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>
> Tested-by: David Howells <dhowells@xxxxxxxxxx>
> ---
> Documentation/core-api/index.rst | 1 +
> Documentation/core-api/maple_tree.rst | 218 +
> MAINTAINERS | 12 +
> include/linux/maple_tree.h | 682 ++
> include/trace/events/maple_tree.h | 123 +
> init/main.c | 2 +
> lib/Kconfig.debug | 15 +
> lib/Makefile | 3 +-
> lib/maple_tree.c | 6979 +++++++++++++++++
> tools/testing/radix-tree/.gitignore | 2 +
> tools/testing/radix-tree/generated/autoconf.h | 1 +
> tools/testing/radix-tree/linux/maple_tree.h | 7 +
> tools/testing/radix-tree/maple.c | 59 +
> .../radix-tree/trace/events/maple_tree.h | 3 +
> 14 files changed, 8106 insertions(+), 1 deletion(-)
> create mode 100644 Documentation/core-api/maple_tree.rst
> create mode 100644 include/linux/maple_tree.h
> create mode 100644 include/trace/events/maple_tree.h
> create mode 100644 lib/maple_tree.c
> create mode 100644 tools/testing/radix-tree/linux/maple_tree.h
> create mode 100644 tools/testing/radix-tree/maple.c
> create mode 100644 tools/testing/radix-tree/trace/events/maple_tree.h
>
...
Andrew,
Please add this fix to the maple tree patch.
Thanks,
Liam
From 0773dfda2194064a88d5331876a24882ceec6d03 Mon Sep 17 00:00:00 2001
From: "Liam R. Howlett" <Liam.Howlett@xxxxxxxxxx>
Date: Wed, 20 Apr 2022 09:36:02 -0400
Subject: [PATCH] maple_tree: Fix potential insufficient nodes on
mas_spanning_rebalance()
When a spanning store occurs at a non-root node but causes an
insufficient leave, mas_spanning_rebalance() was not detecting it as a
non-root node. This only happened when the spanning write was detected
at the root node.
Signed-off-by: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>
---
lib/maple_tree.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 3c78e63efaec..d6a10216521e 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -2894,7 +2894,7 @@ static int mas_spanning_rebalance(struct ma_state *mas,
mast->free = &free;
mast->destroy = &destroy;
l_mas.node = r_mas.node = m_mas.node = MAS_NONE;
- if (!mas_is_root_limits(mas) &&
+ if (!mas_is_root_limits(mast->orig_l) &&
unlikely(mast->bn->b_end <= mt_min_slots[mast->bn->type])) {
/*
* Do not free the current node as it may be freed in a bulk
--
2.34.1
