Re: [LSF/MM TOPIC] Using XArray to manage the VMA

[Davidlohr Bueso <dave@stgolabs.net>]

On Wed, 13 Mar 2019, Matthew Wilcox wrote:

>It's probably worth listing the advantages of the Maple Tree over the
>rbtree.

I'm not familiar with maple trees, are they referred to by another name?
(is this some sort of B-tree?). Google just shows me real trees.

>
> - Shallower tree.  A 1000-entry rbtree is 10 levels deep.  A 1000-entry
>   Maple Tree is 5 levels deep (I did a more detailed analysis in an
>   earlier email thread with Laurent and I can present it if needed).

I'd be interested in reading on that.

> - O(1) prev/next
> - Lookups under the RCU lock
>
>There're some second-order effects too; by using externally allocated
>nodes, we avoid disturbing other VMAs when inserting/deleting, and we
>avoid bouncing cachelines around (eg the VMA which happens to end up
>at the head of the tree is accessed by every lookup in the tree because
>it's on the way to every other node).

How would maple trees deal with the augmented vma tree (vma gaps) trick
we use to optimize get_unmapped_area?

Thanks,
Davidlohr