On Tue, 26 Apr 2022 15:06:19 +0000 Liam Howlett <liam.howlett@xxxxxxxxxx> wrote: > 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 I think it would be helpful to expand on "a number of places". Specifically which places? > 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. "mmap_lock" ;) > > 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. Do we have any quantitative testing results? What's the plan on utilizing this to further reduce mmap_lock contention?
