]> www.infradead.org Git - users/jedix/linux-maple.git/commit
Maple Tree: Add new data structure
authorLiam R. Howlett <Liam.Howlett@Oracle.com>
Fri, 24 Jul 2020 17:02:52 +0000 (13:02 -0400)
committerLiam R. Howlett <Liam.Howlett@Oracle.com>
Thu, 24 Jun 2021 20:04:21 +0000 (16:04 -0400)
commitdb8c177ddacc826d0066522e2f5e7e4c58d6122d
tree67b90f20668defa88239e02ed026fa146d37aa5d
parent7a63d6258a7e014f615197de044bc379645684ee
Maple Tree: Add new data structure

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: Liam R. Howlett <Liam.Howlett@oracle.com>
Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
15 files changed:
Documentation/core-api/index.rst
Documentation/core-api/maple-tree.rst [new file with mode: 0644]
MAINTAINERS
include/linux/maple_tree.h [new file with mode: 0644]
include/trace/events/maple_tree.h [new file with mode: 0644]
lib/Kconfig.debug
lib/Makefile
lib/maple_tree.c [new file with mode: 0644]
lib/test_maple_tree.c [new file with mode: 0644]
tools/testing/radix-tree/.gitignore
tools/testing/radix-tree/Makefile
tools/testing/radix-tree/generated/autoconf.h
tools/testing/radix-tree/linux/maple_tree.h [new file with mode: 0644]
tools/testing/radix-tree/maple.c [new file with mode: 0644]
tools/testing/radix-tree/trace/events/maple_tree.h [new file with mode: 0644]