Message-ID: <5ujw5k7z7ybboxoks5idc4cwxxmafsig32spmh7wddi6334ami@qpf7dm3sacsa>
Date: Thu, 3 Jul 2025 01:54:57 -0400
From: "Liam R. Howlett" <Liam.Howlett@...cle.com>
To: Dev Jain <dev.jain@....com>
Cc: akpm@...ux-foundation.org, richard.weiyang@...il.com,
        maple-tree@...ts.infradead.org, linux-mm@...ck.org,
        linux-kernel@...r.kernel.org
Subject: Re: [PATCH 2/2] maple tree: Add and fix some comments

* Dev Jain <dev.jain@....com> [250628 07:57]:
> 
> On 27/06/25 1:34 am, Liam R. Howlett wrote:
> > * Dev Jain <dev.jain@....com> [250626 13:19]:
> > > Add comments explaining the fields for maple_metadata, since "end" is
> > > ambiguous and "gap" can be confused as the largest gap, whereas it
> > > is actually the offset of the largest gap.
> > > 
> > > MAPLE_ROOT_NODE is used for mt_mk_root() and mt_safe_root(), indicating
> > > that it is used to mark the node as root. So fix the comment.
> > That's not quite the entire story here.
> > 
> > The first pointer in the tree may not be a node at all, and may be an
> > entry.  So having that bit set tells us the root of the tree is a node,
> > so the comment is correct but maybe you have a better way of expressing
> > this information?
> 
> Hmm. Can you please correct me on my understanding - when we have an
> empty tree, then we insert a root and can store a value there. Now when
> we store the second entry, we allocate a node and make the root a node,
> the root points to that node, and we store the values at offsets 0 and 1.
> 
> I am reading more to answer my own question.

Not quite.

If we store to 0 of size 1, then we can just have a pointer without a
node at all.  There are a few scenarios which can play out when storing
the first entry to the tree:

Nothing stored, root is NULL, representing 0 - ULONG_MAX => NULL

There is a value only at zero, root is the entry, representing 0.
1 - ULONG_MAX => NULL.  To ensure that the root entry isn't detected as
a node, there are restrictions on the entry value.

There is a value only at zero which would be confused with a node.  A
node is allocated and the ranges are stored in the node. 0 => entry and
1 - ULONG_MAX => NULL.

There is a value that is not just zero (and may not include zero in the
range), then a node is stored at root.

Read mas_store_root() for details.

As the tree grows and shrinks, the type of node stored in the root may
change.  The root may return to just a pointer or NULL.

Once there is a node at root, each slot either contains an entry/NULL or
a child node.  Each pivot defines a maximum for the range while the
previous pivot (or the minimum of that node, starting at 0) defines the
minimum.  So the [minimum] = start of range 0, pivot[0] = end of range
zero, pivot[0] + 1 = start of range 1, etc.

Nodes do not store the minimum and may not store the maximum (if there
isn't enough pivots the maximum is just inherited from the parent node).

All ranges are represented and present at the child node.  This means
that ever range will walk to the leaf node and have an entry or NULL.
B-trees require everything to be at the same height.

So, the entries at offsets 0 and 1 depend on the ranges stored.

You can see a diagram of a node in ascii at the top of lib/maple_tree.c
as well as terminology used.

I have tried to keep the developer documentation in the .c and .h files,
while the user documentation is in Documentation/core-api/maple_tree.rst

If you read the start of the .c, it runs through a node layout.

I've also posted an overview of the tree on the Oracle Blog [1] and
given a talk about some of the way the tree worked for the Linux
Foundation [2].  You can also find talks at OSS 2019 by willy, and lpc
2019 by myself as well as 2022, and lsf/mm if you search for 'maple tree
linux' on youtube.

Hopefully that helps.

[1] https://blogs.oracle.com/linux/post/maple-tree-storing-ranges
[2] https://www.linuxfoundation.org/webinars/the-maple-tree-structure-and-algorithms?hsLang=en

Thanks,
Liam

Powered by blists - more mailing lists