* [LSF/MM/BPF TOPIC] The Maple Tree
@ 2022-02-01 15:06 Liam Howlett
2022-02-20 17:10 ` Chaitanya Kulkarni
0 siblings, 1 reply; 3+ messages in thread
From: Liam Howlett @ 2022-02-01 15:06 UTC (permalink / raw
To: lsf-pc@lists.linux-foundation.org, linux-mm@kvack.org,
linux-fsdevel@vger.kernel.org
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
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [LSF/MM/BPF TOPIC] The Maple Tree
2022-02-01 15:06 [LSF/MM/BPF TOPIC] The Maple Tree Liam Howlett
@ 2022-02-20 17:10 ` Chaitanya Kulkarni
0 siblings, 0 replies; 3+ messages in thread
From: Chaitanya Kulkarni @ 2022-02-20 17:10 UTC (permalink / raw
To: Liam Howlett, lsf-pc@lists.linux-foundation.org,
linux-mm@kvack.org, linux-fsdevel@vger.kernel.org
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
^ permalink raw reply [flat|nested] 3+ messages in thread
* [LSF/MM/BPF TOPIC] The Maple Tree
@ 2021-06-01 22:30 Liam Howlett
0 siblings, 0 replies; 3+ messages in thread
From: Liam Howlett @ 2021-06-01 22:30 UTC (permalink / raw
To: lsf-pc@lists.linux-foundation.org, linux-mm@kvack.org,
linux-fsdevel@vger.kernel.org
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
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2022-02-20 17:11 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2022-02-01 15:06 [LSF/MM/BPF TOPIC] The Maple Tree Liam Howlett
2022-02-20 17:10 ` Chaitanya Kulkarni
-- strict thread matches above, loose matches on Subject: below --
2021-06-01 22:30 Liam Howlett
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).