[PATCH 0/2] Documentation: maple_tree: Improve statements on reserved values

[PATCH 0/2] Documentation: maple_tree: Improve statements on reserved values

[Wei-Lin Chang]

Hi,

This is another version of [1], where I improved wording.

While using the maple tree and reading its documentation, I found a few
bits confusing, mainly about the reserved values. So here are some
changes hoping to make things clearer.

I am not familiar with the implementation, so if I got something wrong
please let me know.

While looking at the code I also found that although the doc claims the
normal API blocks reserved value stores, the code checks this using
xa_is_advanced(), which only blocks values up to 1026, not up to the max
maple tree reserved value 4094. For this part I am not sure whether the
code needs to be changed or we can also improve the doc.

Any feedback is appreciated, thanks!

[1]: https://lore.kernel.org/linux-mm/20260418204754.120405-1-weilin.chang@arm.com/

Wei-Lin Chang (2):
  Documentation: maple_tree: Point out constraint when using xa_{mk,
    to}_value
  Documentation: maple_tree: Clarify behavior when using reserved values

 Documentation/core-api/maple_tree.rst | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

-- 
2.43.0

[PATCH 1/2] Documentation: maple_tree: Point out constraint when using xa_{mk, to}_value

[Wei-Lin Chang]

Using xa_{mk, to}_value when storing values loses the information of
the top bit from the left shift, point that out in the doc.

Signed-off-by: Wei-Lin Chang <weilin.chang@arm.com>
---
 Documentation/core-api/maple_tree.rst | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/Documentation/core-api/maple_tree.rst b/Documentation/core-api/maple_tree.rst
index ccdd1615cf97..87020a30ba69 100644
--- a/Documentation/core-api/maple_tree.rst
+++ b/Documentation/core-api/maple_tree.rst
@@ -29,8 +29,9 @@ The Maple Tree can store values between ``0`` and ``ULONG_MAX``.  The Maple
 Tree reserves values with the bottom two bits set to '10' which are below 4096
 (ie 2, 6, 10 .. 4094) for internal use.  If the entries may use reserved
 entries then the users can convert the entries using xa_mk_value() and convert
-them back by calling xa_to_value().  If the user needs to use a reserved
-value, then the user can convert the value when using the
+them back by calling xa_to_value().  Note that xa_{mk, to}_value() bit shifts
+the given data, so the top bit will be lost.  If the user needs to use a
+reserved value, then the user can convert the value when using the
 :ref:`maple-tree-advanced-api`, but are blocked by the normal API.
 
 The Maple Tree can also be configured to support searching for a gap of a given
-- 
2.43.0

Re: [PATCH 1/2] Documentation: maple_tree: Point out constraint when using xa_{mk, to}_value

[Matthew Wilcox]

On Mon, May 04, 2026 at 05:57:45PM +0100, Wei-Lin Chang wrote:
> Using xa_{mk, to}_value when storing values loses the information of
> the top bit from the left shift, point that out in the doc.

I don't know if that's necessary ... it's obvious when looking at the
function:

static inline void *xa_mk_value(unsigned long v)
{
        WARN_ON((long)v < 0);
        return (void *)((v << 1) | 1);
}

and if you ignore it, you'll find out.  But if this needs to be
documented anywhere, it's in the kernel-doc for xa_mk_value()
and not in the maple tree docs.

Re: [PATCH 1/2] Documentation: maple_tree: Point out constraint when using xa_{mk, to}_value

[Wei-Lin Chang]

On Mon, May 04, 2026 at 09:32:38PM +0100, Matthew Wilcox wrote:
> On Mon, May 04, 2026 at 05:57:45PM +0100, Wei-Lin Chang wrote:
> > Using xa_{mk, to}_value when storing values loses the information of
> > the top bit from the left shift, point that out in the doc.
> 
> I don't know if that's necessary ... it's obvious when looking at the
> function:
> 
> static inline void *xa_mk_value(unsigned long v)
> {
>         WARN_ON((long)v < 0);
>         return (void *)((v << 1) | 1);
> }
> 
> and if you ignore it, you'll find out.  But if this needs to be
> documented anywhere, it's in the kernel-doc for xa_mk_value()
> and not in the maple tree docs.

Yeah this makes sense, thanks for having a look.

Thanks,
Wei-Lin Chang

[PATCH 2/2] Documentation: maple_tree: Clarify behavior when using reserved values

[Wei-Lin Chang]

It doesn't matter whether the normal or the advanced API is used if the
user uses xa_{mk, to}_value when storing and retrieving the values. Just
specify that the normal API blocks usages of reserved values while the
advanced API does not.

Signed-off-by: Wei-Lin Chang <weilin.chang@arm.com>
---
 Documentation/core-api/maple_tree.rst | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/Documentation/core-api/maple_tree.rst b/Documentation/core-api/maple_tree.rst
index 87020a30ba69..e5ccafb84804 100644
--- a/Documentation/core-api/maple_tree.rst
+++ b/Documentation/core-api/maple_tree.rst
@@ -30,9 +30,9 @@ Tree reserves values with the bottom two bits set to '10' which are below 4096
 (ie 2, 6, 10 .. 4094) for internal use.  If the entries may use reserved
 entries then the users can convert the entries using xa_mk_value() and convert
 them back by calling xa_to_value().  Note that xa_{mk, to}_value() bit shifts
-the given data, so the top bit will be lost.  If the user needs to use a
-reserved value, then the user can convert the value when using the
-:ref:`maple-tree-advanced-api`, but are blocked by the normal API.
+the given data, so the top bit will be lost.  Usage of reserved values is
+blocked by the normal API, and will cause undefined behavior if used with the
+:ref:`maple-tree-advanced-api`.
 
 The Maple Tree can also be configured to support searching for a gap of a given
 size (or larger).
-- 
2.43.0

Re: [PATCH 2/2] Documentation: maple_tree: Clarify behavior when using reserved values

[Liam R. Howlett]

On 26/05/04 05:57PM, Wei-Lin Chang wrote:
> It doesn't matter whether the normal or the advanced API is used if the
> user uses xa_{mk, to}_value when storing and retrieving the values. Just
> specify that the normal API blocks usages of reserved values while the
> advanced API does not.

Your comment above is incorrect.

The normal API will filter out reserved values on return while the
advanced API will return whatever is stored there regardless of the
value.

Meaning, if you store a reserved value with the advanced API, it will
not be returned by the normal API.

> 
> Signed-off-by: Wei-Lin Chang <weilin.chang@arm.com>
> ---
>  Documentation/core-api/maple_tree.rst | 6 +++---
>  1 file changed, 3 insertions(+), 3 deletions(-)
> 
> diff --git a/Documentation/core-api/maple_tree.rst b/Documentation/core-api/maple_tree.rst
> index 87020a30ba69..e5ccafb84804 100644
> --- a/Documentation/core-api/maple_tree.rst
> +++ b/Documentation/core-api/maple_tree.rst
> @@ -30,9 +30,9 @@ Tree reserves values with the bottom two bits set to '10' which are below 4096
>  (ie 2, 6, 10 .. 4094) for internal use.  If the entries may use reserved
>  entries then the users can convert the entries using xa_mk_value() and convert
>  them back by calling xa_to_value().  Note that xa_{mk, to}_value() bit shifts
> -the given data, so the top bit will be lost.  If the user needs to use a
> -reserved value, then the user can convert the value when using the
> -:ref:`maple-tree-advanced-api`, but are blocked by the normal API.
> +the given data, so the top bit will be lost.  Usage of reserved values is
> +blocked by the normal API, and will cause undefined behavior if used with the
> +:ref:`maple-tree-advanced-api`.

Which behaviour is undefined?

>  
>  The Maple Tree can also be configured to support searching for a gap of a given
>  size (or larger).
> -- 
> 2.43.0
> 
> 
> -- 
> maple-tree mailing list
> maple-tree@lists.infradead.org
> https://lists.infradead.org/mailman/listinfo/maple-tree

Re: [PATCH 2/2] Documentation: maple_tree: Clarify behavior when using reserved values

[Wei-Lin Chang]

On Thu, May 07, 2026 at 05:24:11AM +0200, Liam R. Howlett wrote:
> On 26/05/04 05:57PM, Wei-Lin Chang wrote:
> > It doesn't matter whether the normal or the advanced API is used if the
> > user uses xa_{mk, to}_value when storing and retrieving the values. Just
> > specify that the normal API blocks usages of reserved values while the
> > advanced API does not.
> 
> Your comment above is incorrect.
> 
> The normal API will filter out reserved values on return while the
> advanced API will return whatever is stored there regardless of the
> value.
> 
> Meaning, if you store a reserved value with the advanced API, it will
> not be returned by the normal API.

This is valuable information, thanks for explaining.
However, I'm confused how this shows my comment incorrect?

From the original doc:

<quote>
If the user needs to use a reserved value, then the user can convert the
value when using the :ref:`maple-tree-advanced-api`, but are blocked by
the normal API.
</quote>

To me this is conveying the following points:

1. User can convert the value with xa_{mk, to}_value() when using the
   advanced API if reserved values are being stored. This works because
   those functions transform the reserved values into non-reserved ones.
2. User can not use reserved values with or without xa_{mk, to}_value()
   with the normal API.
3. What happens when reserved values are stored is not clearly stated,
   but the normal API will block it.

In my understanding 2. is incorrect because if xa_{mk, to}_value() are
deployed, it doesn't matter whether the normal or advanced API is used,
they both work since the values stored aren't reserved.

Please do you mind pointing out what I am getting wrong here?

I was genuinely confused when I was reading the doc and trying to use
this data structure.

> 
> > 
> > Signed-off-by: Wei-Lin Chang <weilin.chang@arm.com>
> > ---
> >  Documentation/core-api/maple_tree.rst | 6 +++---
> >  1 file changed, 3 insertions(+), 3 deletions(-)
> > 
> > diff --git a/Documentation/core-api/maple_tree.rst b/Documentation/core-api/maple_tree.rst
> > index 87020a30ba69..e5ccafb84804 100644
> > --- a/Documentation/core-api/maple_tree.rst
> > +++ b/Documentation/core-api/maple_tree.rst
> > @@ -30,9 +30,9 @@ Tree reserves values with the bottom two bits set to '10' which are below 4096
> >  (ie 2, 6, 10 .. 4094) for internal use.  If the entries may use reserved
> >  entries then the users can convert the entries using xa_mk_value() and convert
> >  them back by calling xa_to_value().  Note that xa_{mk, to}_value() bit shifts
> > -the given data, so the top bit will be lost.  If the user needs to use a
> > -reserved value, then the user can convert the value when using the
> > -:ref:`maple-tree-advanced-api`, but are blocked by the normal API.
> > +the given data, so the top bit will be lost.  Usage of reserved values is
> > +blocked by the normal API, and will cause undefined behavior if used with the
> > +:ref:`maple-tree-advanced-api`.
> 
> Which behaviour is undefined?

I originally thought storing reserved values could break the tree
because of its internal use (see 3. above).

Thanks,
Wei-Lin Chang

> 
> >  
> >  The Maple Tree can also be configured to support searching for a gap of a given
> >  size (or larger).
> > -- 
> > 2.43.0
> > 
> > 
> > -- 
> > maple-tree mailing list
> > maple-tree@lists.infradead.org
> > https://lists.infradead.org/mailman/listinfo/maple-tree

Re: [PATCH 2/2] Documentation: maple_tree: Clarify behavior when using reserved values

[Liam R. Howlett]

On 26/05/07 11:09PM, Wei-Lin Chang wrote:
> On Thu, May 07, 2026 at 05:24:11AM +0200, Liam R. Howlett wrote:
> > On 26/05/04 05:57PM, Wei-Lin Chang wrote:
> > > It doesn't matter whether the normal or the advanced API is used if the
> > > user uses xa_{mk, to}_value when storing and retrieving the values. Just
> > > specify that the normal API blocks usages of reserved values while the
> > > advanced API does not.
> > 
> > Your comment above is incorrect.
> > 
> > The normal API will filter out reserved values on return while the
> > advanced API will return whatever is stored there regardless of the
> > value.
> > 
> > Meaning, if you store a reserved value with the advanced API, it will
> > not be returned by the normal API.
> 
> This is valuable information, thanks for explaining.

Hmm, maybe I answered too quickly here.  We filter out XA_ZERO_ENTRY on
normal API searches, which is in the reserved range.

> However, I'm confused how this shows my comment incorrect?

It matters if you use the xa_(mk, to}_value since the top bit will be
lost.  Re-reading your comment, you don't specifically say that though,
you said 'if the user uses..', so I was confused by your wording of what
you were saying.

> 
> From the original doc:
> 
> <quote>
> If the user needs to use a reserved value, then the user can convert the
> value when using the :ref:`maple-tree-advanced-api`, but are blocked by
> the normal API.
> </quote>
> 
> To me this is conveying the following points:
> 
> 1. User can convert the value with xa_{mk, to}_value() when using the
>    advanced API if reserved values are being stored. This works because
>    those functions transform the reserved values into non-reserved ones.
> 2. User can not use reserved values with or without xa_{mk, to}_value()
>    with the normal API.
> 3. What happens when reserved values are stored is not clearly stated,
>    but the normal API will block it.
> 
> In my understanding 2. is incorrect because if xa_{mk, to}_value() are
> deployed, it doesn't matter whether the normal or advanced API is used,
> they both work since the values stored aren't reserved.
> 
> Please do you mind pointing out what I am getting wrong here?

I think you are missing the part where the top bit may be lost?

I also don't think the reserved values will matter if you use the
advanced API exclusively.  You would have to filter the special cases or
whatever you want - that is, if you mix the interfaces then you may see
odd behaviour in regards to the special cases in the normal API while
the advanced API would return the reserved items and need to be filtered
at a higher level than the maple tree code.

> 
> I was genuinely confused when I was reading the doc and trying to use
> this data structure.

Then we need to rework the wording somehow.  Thanks.

> 
> > 
> > > 
> > > Signed-off-by: Wei-Lin Chang <weilin.chang@arm.com>
> > > ---
> > >  Documentation/core-api/maple_tree.rst | 6 +++---
> > >  1 file changed, 3 insertions(+), 3 deletions(-)
> > > 
> > > diff --git a/Documentation/core-api/maple_tree.rst b/Documentation/core-api/maple_tree.rst
> > > index 87020a30ba69..e5ccafb84804 100644
> > > --- a/Documentation/core-api/maple_tree.rst
> > > +++ b/Documentation/core-api/maple_tree.rst
> > > @@ -30,9 +30,9 @@ Tree reserves values with the bottom two bits set to '10' which are below 4096
> > >  (ie 2, 6, 10 .. 4094) for internal use.  If the entries may use reserved
> > >  entries then the users can convert the entries using xa_mk_value() and convert
> > >  them back by calling xa_to_value().  Note that xa_{mk, to}_value() bit shifts
> > > -the given data, so the top bit will be lost.  If the user needs to use a
> > > -reserved value, then the user can convert the value when using the
> > > -:ref:`maple-tree-advanced-api`, but are blocked by the normal API.
> > > +the given data, so the top bit will be lost.  Usage of reserved values is
> > > +blocked by the normal API, and will cause undefined behavior if used with the
> > > +:ref:`maple-tree-advanced-api`.
> > 
> > Which behaviour is undefined?
> 
> I originally thought storing reserved values could break the tree
> because of its internal use (see 3. above).

You can't break the tree by storing reserved values.  The normal API
will outright not allow storing it while the advanced API will store and
return it.

The issue comes from when you mix and match - if you store a reserved
value using the advanced api and then iterate through with the normal
api, some values may be lost.  Today, that's XA_ZERO_ENTRY only, but we
reserve the right to change that if it is necessary for some tree
version.

Does that make sense?

Thanks,
Liam