Re: [PATCH 2/2] maple tree: Add and fix some comments

[Dev Jain <dev.jain@arm.com>]

On 03/07/25 11:24 am, Liam R. Howlett wrote:
> * Dev Jain <dev.jain@arm.com> [250628 07:57]:
>> On 27/06/25 1:34 am, Liam R. Howlett wrote:
>>> * Dev Jain <dev.jain@arm.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

Thanks for your reply, I have already seen all of the above mentioned resources : )