]> 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>
Tue, 8 Mar 2022 18:19:09 +0000 (13:19 -0500)
commitc1c94b4b6350d5f86e7310f1290c8b6671920f57
tree5068938f7ffa887a6d20bdcc3fa45b0fe8f1714b
parent33036bcfce014038e8f7116025ecba30046cb311
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: Matthew Wilcox (Oracle) <willy@infradead.org>
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Tested-by: David Howells <dhowells@redhat.com>
14 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]
init/main.c
lib/Kconfig.debug
lib/Makefile
lib/maple_tree.c [new file with mode: 0644]
tools/testing/radix-tree/.gitignore
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]