Re: [PATCH v7 07/70] Maple Tree: Add new data structure

[Liam Howlett <liam.howlett@oracle.com>]

[-- Attachment #1: Type: text/plain, Size: 2628 bytes --]

* Liam Howlett <liam.howlett@oracle.com> [220404 10:45]:
> From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
> 
> 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@infradead.org>
> Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
> Tested-by: David Howells <dhowells@redhat.com>
> ---
>  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

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-maple_tree-Fix-potential-insufficient-nodes-on-mas_s.patch --]
[-- Type: text/x-diff; name="0001-maple_tree-Fix-potential-insufficient-nodes-on-mas_s.patch", Size: 1181 bytes --]

From 0773dfda2194064a88d5331876a24882ceec6d03 Mon Sep 17 00:00:00 2001
From: "Liam R. Howlett" <Liam.Howlett@oracle.com>
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@oracle.com>
---
 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