[PATCH 1/2] maple tree: Clean up mtree_range_walk()

[PATCH 1/2] maple tree: Clean up mtree_range_walk()

[Dev Jain]

The special casing for offset == 0 is being done because min will stay
mas->min in this case. So refactor the code to use the while loop for
setting the max and getting the corresponding offset, and only set the
min for offset > 0.

Signed-off-by: Dev Jain <dev.jain@arm.com>
---
 lib/maple_tree.c | 11 +++--------
 1 file changed, 3 insertions(+), 8 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 0e85e92c5375..6c89e6790fb5 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -2770,13 +2770,8 @@ static inline void *mtree_range_walk(struct ma_state *mas)
 		end = ma_data_end(node, type, pivots, max);
 		prev_min = min;
 		prev_max = max;
-		if (pivots[0] >= mas->index) {
-			offset = 0;
-			max = pivots[0];
-			goto next;
-		}
 
-		offset = 1;
+		offset = 0;
 		while (offset < end) {
 			if (pivots[offset] >= mas->index) {
 				max = pivots[offset];
@@ -2784,9 +2779,9 @@ static inline void *mtree_range_walk(struct ma_state *mas)
 			}
 			offset++;
 		}
+		if (likely(offset))
+			min = pivots[offset - 1] + 1;
 
-		min = pivots[offset - 1] + 1;
-next:
 		slots = ma_slots(node, type);
 		next = mt_slot(mas->tree, slots, offset);
 		if (unlikely(ma_dead_node(node)))
-- 
2.30.2

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

[Dev Jain]

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.

Add comment for mas_ascend() to explain, whose min and max we are
trying to find. Explain that, for example, if we are already on offset
zero, then the parent min is mas->min, otherwise we need to walk up
to find the implied pivot min.

Signed-off-by: Dev Jain <dev.jain@arm.com>
---
 include/linux/maple_tree.h | 4 ++--
 lib/maple_tree.c           | 9 +++++++--
 2 files changed, 9 insertions(+), 4 deletions(-)

diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index 9ef129038224..bafe143b1f78 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -75,8 +75,8 @@
  * searching for gaps or any other code that needs to find the end of the data.
  */
 struct maple_metadata {
-	unsigned char end;
-	unsigned char gap;
+	unsigned char end;	/* end of data */
+	unsigned char gap;	/* offset of largest gap */
 };
 
 /*
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 6c89e6790fb5..e4735ccd06f2 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -338,7 +338,7 @@ static inline void mte_set_node_dead(struct maple_enode *mn)
 	smp_wmb(); /* Needed for RCU */
 }
 
-/* Bit 1 indicates the root is a node */
+/* Bit 1 indicates the node is the root */
 #define MAPLE_ROOT_NODE			0x02
 /* maple_type stored bit 3-6 */
 #define MAPLE_ENODE_TYPE_SHIFT		0x03
@@ -1053,7 +1053,7 @@ static inline void mte_set_gap(const struct maple_enode *mn,
  * mas_ascend() - Walk up a level of the tree.
  * @mas: The maple state
  *
- * Sets the @mas->max and @mas->min to the correct values when walking up.  This
+ * Sets the @mas->max and @mas->min for the parent node of mas->node.  This
  * may cause several levels of walking up to find the correct min and max.
  * May find a dead node which will cause a premature return.
  * Return: 1 on dead node, 0 otherwise
@@ -1098,6 +1098,11 @@ static int mas_ascend(struct ma_state *mas)
 
 	min = 0;
 	max = ULONG_MAX;
+
+	/*
+	 * !mas->offset => parent node min == mas->min. mas->offset => need
+	 * to walk up to find the implied pivot min.
+	 */
 	if (!mas->offset) {
 		min = mas->min;
 		set_min = true;
-- 
2.30.2

Re: [PATCH 1/2] maple tree: Clean up mtree_range_walk()

[Liam R. Howlett]

* Dev Jain <dev.jain@arm.com> [250626 13:19]:
> The special casing for offset == 0 is being done because min will stay
> mas->min in this case. So refactor the code to use the while loop for
> setting the max and getting the corresponding offset, and only set the
> min for offset > 0.
> 
> Signed-off-by: Dev Jain <dev.jain@arm.com>
> ---
>  lib/maple_tree.c | 11 +++--------
>  1 file changed, 3 insertions(+), 8 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 0e85e92c5375..6c89e6790fb5 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -2770,13 +2770,8 @@ static inline void *mtree_range_walk(struct ma_state *mas)
>  		end = ma_data_end(node, type, pivots, max);
>  		prev_min = min;
>  		prev_max = max;
> -		if (pivots[0] >= mas->index) {
> -			offset = 0;
> -			max = pivots[0];
> -			goto next;
> -		}
>  

This new line should be dropped.

> -		offset = 1;
> +		offset = 0;
>  		while (offset < end) {

This should now be a do {} while();

>  			if (pivots[offset] >= mas->index) {
>  				max = pivots[offset];
> @@ -2784,9 +2779,9 @@ static inline void *mtree_range_walk(struct ma_state *mas)
>  			}
>  			offset++;
>  		}

There should be a new line here.

> +		if (likely(offset))
> +			min = pivots[offset - 1] + 1;
>  
> -		min = pivots[offset - 1] + 1;
> -next:
>  		slots = ma_slots(node, type);
>  		next = mt_slot(mas->tree, slots, offset);
>  		if (unlikely(ma_dead_node(node)))
> -- 
> 2.30.2
> 

The current way will check pivot 0, then skip the main loop.  Pivot 0
has an equal chance of being the range you are looking for, but that
probability increases based on a lower number of entries in the node.
The root node, which we always pass through, can have as little as two
entries, so then it's 50/50 you want pivot 0.

With the way you've written it, it will check offset < end (which will
always be the case for the first time), then do the same work as the
out-of-loop check, then check offset an extra time after the loop.

If it's written with a do {} while, the initial check of offset < end is
avoided, but you will end up checking offset an extra time to see if min
needs to be set.

If pivot 0 is NOT the entry you want, then the current code will check
pivot 0, then execute the loop one less time.  In the even of a root
node with 2 entries, it will not enter the loop at all.

So, the way it is written is less code execution by avoiding unnecessary
assignment of min and checks (of offset == 0 and offset < end).

Thanks,
Liam

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

[Liam R. Howlett]

* 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?


> 
> Add comment for mas_ascend() to explain, whose min and max we are
> trying to find. Explain that, for example, if we are already on offset
> zero, then the parent min is mas->min, otherwise we need to walk up
> to find the implied pivot min.
> 
> Signed-off-by: Dev Jain <dev.jain@arm.com>
> ---
>  include/linux/maple_tree.h | 4 ++--
>  lib/maple_tree.c           | 9 +++++++--
>  2 files changed, 9 insertions(+), 4 deletions(-)
> 
> diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
> index 9ef129038224..bafe143b1f78 100644
> --- a/include/linux/maple_tree.h
> +++ b/include/linux/maple_tree.h
> @@ -75,8 +75,8 @@
>   * searching for gaps or any other code that needs to find the end of the data.
>   */
>  struct maple_metadata {
> -	unsigned char end;
> -	unsigned char gap;
> +	unsigned char end;	/* end of data */
> +	unsigned char gap;	/* offset of largest gap */

Thanks.

>  };
>  
>  /*
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 6c89e6790fb5..e4735ccd06f2 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -338,7 +338,7 @@ static inline void mte_set_node_dead(struct maple_enode *mn)
>  	smp_wmb(); /* Needed for RCU */
>  }
>  
> -/* Bit 1 indicates the root is a node */
> +/* Bit 1 indicates the node is the root */
>  #define MAPLE_ROOT_NODE			0x02
>  /* maple_type stored bit 3-6 */
>  #define MAPLE_ENODE_TYPE_SHIFT		0x03
> @@ -1053,7 +1053,7 @@ static inline void mte_set_gap(const struct maple_enode *mn,
>   * mas_ascend() - Walk up a level of the tree.
>   * @mas: The maple state
>   *
> - * Sets the @mas->max and @mas->min to the correct values when walking up.  This
> + * Sets the @mas->max and @mas->min for the parent node of mas->node.  This
>   * may cause several levels of walking up to find the correct min and max.
>   * May find a dead node which will cause a premature return.
>   * Return: 1 on dead node, 0 otherwise
> @@ -1098,6 +1098,11 @@ static int mas_ascend(struct ma_state *mas)
>  
>  	min = 0;
>  	max = ULONG_MAX;
> +
> +	/*
> +	 * !mas->offset => parent node min == mas->min. mas->offset => need
> +	 * to walk up to find the implied pivot min.

The => arrows here are a bit hard to parse, especially mixed with ==.
Maybe use more words?

> +	 */
>  	if (!mas->offset) {
>  		min = mas->min;
>  		set_min = true;
> -- 
> 2.30.2
> 

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

[Dev Jain]

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.

>
>
>> Add comment for mas_ascend() to explain, whose min and max we are
>> trying to find. Explain that, for example, if we are already on offset
>> zero, then the parent min is mas->min, otherwise we need to walk up
>> to find the implied pivot min.
>>
>> Signed-off-by: Dev Jain <dev.jain@arm.com>
>> ---
>>   include/linux/maple_tree.h | 4 ++--
>>   lib/maple_tree.c           | 9 +++++++--
>>   2 files changed, 9 insertions(+), 4 deletions(-)
>>
>> diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
>> index 9ef129038224..bafe143b1f78 100644
>> --- a/include/linux/maple_tree.h
>> +++ b/include/linux/maple_tree.h
>> @@ -75,8 +75,8 @@
>>    * searching for gaps or any other code that needs to find the end of the data.
>>    */
>>   struct maple_metadata {
>> -	unsigned char end;
>> -	unsigned char gap;
>> +	unsigned char end;	/* end of data */
>> +	unsigned char gap;	/* offset of largest gap */
> Thanks.
>
>>   };
>>   
>>   /*
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index 6c89e6790fb5..e4735ccd06f2 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -338,7 +338,7 @@ static inline void mte_set_node_dead(struct maple_enode *mn)
>>   	smp_wmb(); /* Needed for RCU */
>>   }
>>   
>> -/* Bit 1 indicates the root is a node */
>> +/* Bit 1 indicates the node is the root */
>>   #define MAPLE_ROOT_NODE			0x02
>>   /* maple_type stored bit 3-6 */
>>   #define MAPLE_ENODE_TYPE_SHIFT		0x03
>> @@ -1053,7 +1053,7 @@ static inline void mte_set_gap(const struct maple_enode *mn,
>>    * mas_ascend() - Walk up a level of the tree.
>>    * @mas: The maple state
>>    *
>> - * Sets the @mas->max and @mas->min to the correct values when walking up.  This
>> + * Sets the @mas->max and @mas->min for the parent node of mas->node.  This
>>    * may cause several levels of walking up to find the correct min and max.
>>    * May find a dead node which will cause a premature return.
>>    * Return: 1 on dead node, 0 otherwise
>> @@ -1098,6 +1098,11 @@ static int mas_ascend(struct ma_state *mas)
>>   
>>   	min = 0;
>>   	max = ULONG_MAX;
>> +
>> +	/*
>> +	 * !mas->offset => parent node min == mas->min. mas->offset => need
>> +	 * to walk up to find the implied pivot min.
> The => arrows here are a bit hard to parse, especially mixed with ==.
> Maybe use more words?

Okay.

>
>> +	 */
>>   	if (!mas->offset) {
>>   		min = mas->min;
>>   		set_min = true;
>> -- 
>> 2.30.2
>>

Re: [PATCH 1/2] maple tree: Clean up mtree_range_walk()

[Dev Jain]

On 27/06/25 1:28 am, Liam R. Howlett wrote:
> * Dev Jain <dev.jain@arm.com> [250626 13:19]:
>> The special casing for offset == 0 is being done because min will stay
>> mas->min in this case. So refactor the code to use the while loop for
>> setting the max and getting the corresponding offset, and only set the
>> min for offset > 0.
>>
>> Signed-off-by: Dev Jain <dev.jain@arm.com>
>> ---
>>   lib/maple_tree.c | 11 +++--------
>>   1 file changed, 3 insertions(+), 8 deletions(-)
>>
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index 0e85e92c5375..6c89e6790fb5 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -2770,13 +2770,8 @@ static inline void *mtree_range_walk(struct ma_state *mas)
>>   		end = ma_data_end(node, type, pivots, max);
>>   		prev_min = min;
>>   		prev_max = max;
>> -		if (pivots[0] >= mas->index) {
>> -			offset = 0;
>> -			max = pivots[0];
>> -			goto next;
>> -		}
>>   
> This new line should be dropped.
>
>> -		offset = 1;
>> +		offset = 0;
>>   		while (offset < end) {
> This should now be a do {} while();
>
>>   			if (pivots[offset] >= mas->index) {
>>   				max = pivots[offset];
>> @@ -2784,9 +2779,9 @@ static inline void *mtree_range_walk(struct ma_state *mas)
>>   			}
>>   			offset++;
>>   		}
> There should be a new line here.
>
>> +		if (likely(offset))
>> +			min = pivots[offset - 1] + 1;
>>   
>> -		min = pivots[offset - 1] + 1;
>> -next:
>>   		slots = ma_slots(node, type);
>>   		next = mt_slot(mas->tree, slots, offset);
>>   		if (unlikely(ma_dead_node(node)))
>> -- 
>> 2.30.2
>>
> The current way will check pivot 0, then skip the main loop.  Pivot 0
> has an equal chance of being the range you are looking for, but that
> probability increases based on a lower number of entries in the node.
> The root node, which we always pass through, can have as little as two
> entries, so then it's 50/50 you want pivot 0.

My understanding of the tree currently is that ma_root is a single slot.
Or can it be a normal node with 31 slots?

>
> With the way you've written it, it will check offset < end (which will
> always be the case for the first time), then do the same work as the
> out-of-loop check, then check offset an extra time after the loop.
>
> If it's written with a do {} while, the initial check of offset < end is
> avoided, but you will end up checking offset an extra time to see if min
> needs to be set.
>
> If pivot 0 is NOT the entry you want, then the current code will check
> pivot 0, then execute the loop one less time.  In the even of a root
> node with 2 entries, it will not enter the loop at all.
>
> So, the way it is written is less code execution by avoiding unnecessary
> assignment of min and checks (of offset == 0 and offset < end).

Thank you for your detailed explanation. I will have to read more to
understand what you have written : )

>
> Thanks,
> Liam

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

[Wei Yang]

On Sat, Jun 28, 2025 at 05:26:18PM +0530, Dev Jain wrote:
>
>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.
>

Per my understanding, generally it is correct.

You may take a look at tools/testing/radix-tree/maple.c and use mt_dump() to
see how the tree changes.

>I am reading more to answer my own question.
>

-- 
Wei Yang
Help you, Help me

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

[Liam R. Howlett]

* 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

Re: [PATCH 1/2] maple tree: Clean up mtree_range_walk()

[Liam R. Howlett]

* Dev Jain <dev.jain@arm.com> [250628 07:59]:
> 
> On 27/06/25 1:28 am, Liam R. Howlett wrote:
> > * Dev Jain <dev.jain@arm.com> [250626 13:19]:
> > > The special casing for offset == 0 is being done because min will stay
> > > mas->min in this case. So refactor the code to use the while loop for
> > > setting the max and getting the corresponding offset, and only set the
> > > min for offset > 0.
> > > 
> > > Signed-off-by: Dev Jain <dev.jain@arm.com>
> > > ---
> > >   lib/maple_tree.c | 11 +++--------
> > >   1 file changed, 3 insertions(+), 8 deletions(-)
> > > 
> > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > > index 0e85e92c5375..6c89e6790fb5 100644
> > > --- a/lib/maple_tree.c
> > > +++ b/lib/maple_tree.c
> > > @@ -2770,13 +2770,8 @@ static inline void *mtree_range_walk(struct ma_state *mas)
> > >   		end = ma_data_end(node, type, pivots, max);
> > >   		prev_min = min;
> > >   		prev_max = max;
> > > -		if (pivots[0] >= mas->index) {
> > > -			offset = 0;
> > > -			max = pivots[0];
> > > -			goto next;
> > > -		}
> > This new line should be dropped.
> > 
> > > -		offset = 1;
> > > +		offset = 0;
> > >   		while (offset < end) {
> > This should now be a do {} while();
> > 
> > >   			if (pivots[offset] >= mas->index) {
> > >   				max = pivots[offset];
> > > @@ -2784,9 +2779,9 @@ static inline void *mtree_range_walk(struct ma_state *mas)
> > >   			}
> > >   			offset++;
> > >   		}
> > There should be a new line here.
> > 
> > > +		if (likely(offset))
> > > +			min = pivots[offset - 1] + 1;
> > > -		min = pivots[offset - 1] + 1;
> > > -next:
> > >   		slots = ma_slots(node, type);
> > >   		next = mt_slot(mas->tree, slots, offset);
> > >   		if (unlikely(ma_dead_node(node)))
> > > -- 
> > > 2.30.2
> > > 
> > The current way will check pivot 0, then skip the main loop.  Pivot 0
> > has an equal chance of being the range you are looking for, but that
> > probability increases based on a lower number of entries in the node.
> > The root node, which we always pass through, can have as little as two
> > entries, so then it's 50/50 you want pivot 0.
> 
> My understanding of the tree currently is that ma_root is a single slot.
> Or can it be a normal node with 31 slots?

Ah.. ma_root is a pointer which could be a node, null, or an entry.  We
won't get here with a NULL or an entry.. because we don't need to walk
those.

So at this point, we are entering with a node which could currently be
two types; arange64 or range64.

Cheers,
Liam

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

[Dev Jain]

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 : )