Re: [LSF/MM/BPF TOPIC] The Maple Tree

[Chaitanya Kulkarni <chaitanyak@nvidia.com>]

On 2/1/22 7:06 AM, Liam Howlett wrote:
> External email: Use caution opening links or attachments
> 
> 
> Over the years, the tracking of VMAs has slowly gathered more refinement
> with added complexity.  Currently each MM has a linked list, a tree, and
> a cache to track a list of ranges. The current patch set adding the
> maple tree replaces all three of these data structures and is just as
> fast or faster - even without modifying the locking.  As more of the MM
> code is optimized to use the tree, the locking can be extracted and the
> RCU benefits will begin to show.
> 
> The maple tree is a RCU safe range based B-tree.  Many of the rules of a
> B-tree are kept such as each leaf being at the same height and being
> self-balancing.  There are also fundamental differences such as how to
> handle an insert operation that may cause one entry to become three or
> several entries to disappear all together.
> 
> I'd like to discuss how to use the maple tree efficiently in complicated
> scenarios such as those arising in the vma_adjust() scenarios. Also on
> the table is the possibility of a range-based b-tree for the file
> systems as it would seem to work well for file based scenarios.  If
> people are interested, I can also dive into how the internals of the
> tree operate.
> 
> 
> Thank you,
> Liam
> 



I'm interested in attending this topic, Since Matthew's presentation 
last time at conference it will be worth to discuss using maple tree
in different scenarios. I'm also interested in having a discussion
about how internals of the tree operate.

-ck