On Wed, Feb 16, 2022 at 11:47:00AM -0800, Andrew Morton wrote: > On Tue, 15 Feb 2022 14:37:44 +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 > > 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. > > Has a path been chosen which gets us from here to significant reduction > in mmap_lock overhead? > > If so, what's the plan and what must be done? I would say there are still competing ideas for how that is to be done. First, the Maple Tree is independent (to a certain extent) of all the approaches to reducing mmap_lock overhead. It's a better data structure for VMA lookup than the rbtree. Set against that, it has higher overhead for modifications. That means that benchmarks which primarily measure modification overhead see worse performance. We believe this is not representative of real workloads, and indeed we see ~parity on workloads like git and make -jN. The advantage to this patch set is that we get rid of the vmacache entirely, we get rid of the doubly-linked list chaining VMAs together and we get rid of the rbtree usage. And we add a new generic data structure that hopefully I can point people towards instead of using the XArray inappropriately. Both of the approaches to avoiding taking the mmap_lock in the fault path will benefit from using the maple tree for VMAs. Fewer cache misses and RCU safety are things we all want. The maple tree will also benefit if/when either approach is merged; because modifications to the maple tree are more heavyweight than the rbtree, they block readers for longer. The SPF approach is further along. It has been tested in the past with the maple tree, but not in the most recent iteration of either. It doesn't rely on the maple tree, but it does benefit. The RCU-freeing-of-VMAs approach that I favour has not received much attention. I've been busy with other things ;-) It offers much more opportunity for performance improvement, but will take longer to arrive.
