Oracle Continues Working On The Maple Tree For The Linux Kernel

Oracle engineers have continued working on the "Maple Tree" data structure for the Linux kernel as an RCU-safe, range-based B-tree designed to make efficient use of modern processor caches.

Sent out last year was the RFC patch series of Maple Tree for the Linux kernel to introduce this new data structure and make initial use of it. Sent out last week was the latest 94 patches in a post-RFC state for introducing this 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.

At this point the performance of using Maple Tree is showing similar real-world performance to the existing code but some micro-benchmarks are seeing better performance out of it. Below is a video back from the Open-Source Summit North America 2019 about the Maple Tree:

The latest 94 patches working on Maple Tree are out for review and even with a week passing since sending them out there hasn't been much comment yet on this Oracle undertaking for the Linux kernel.