]> 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>
Fri, 11 Feb 2022 03:38:05 +0000 (22:38 -0500)
commitcd644fad30538e876bd421b1d04dc2734d481679
treef8185720017231d804a1c6069888d899ba6ea9c3
parentc63efe0a0695d53860d010b6b60b7562bbfacc41
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>
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]
lib/Kconfig.debug
lib/Makefile
lib/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]