[PATCH 0/3] mas_anode_descend() related cleanup

[PATCH 0/3] mas_anode_descend() related cleanup

[Wei Yang]

Some cleanup related to mas_anode_descend().

Patch 1: remove an unnecessary check
Patch 2: won't hit root node
Patch 3: on error we don't set offset to MAPLE_NODE_SLOTS

Wei Yang (3):
  maple_tree: index has been checked to be smaller than pivot
  maple_tree: not possible to be a root node after loop
  maple_tree: we don't set offset to MAPLE_NODE_SLOTS on error

 lib/maple_tree.c | 23 ++++++++---------------
 1 file changed, 8 insertions(+), 15 deletions(-)

-- 
2.34.1

[PATCH 1/3] maple_tree: index has been checked to be smaller than pivot

[Wei Yang]

At the beginning of loop, it has checked the range is in lower bounds.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
CC: Liam R. Howlett <Liam.Howlett@Oracle.com>
CC: Lorenzo Stoakes <lorenzo.stoakes@oracle.com>
CC: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 13 ++++++-------
 1 file changed, 6 insertions(+), 7 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 667326717f35..63dccd7b9474 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4893,13 +4893,12 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size)
 				found = true;
 				goto done;
 			}
-			if (mas->index <= pivot) {
-				mas->node = mas_slot(mas, slots, offset);
-				mas->min = min;
-				mas->max = pivot;
-				offset = 0;
-				break;
-			}
+
+			mas->node = mas_slot(mas, slots, offset);
+			mas->min = min;
+			mas->max = pivot;
+			offset = 0;
+			break;
 		}
 next_slot:
 		min = pivot + 1;
-- 
2.34.1

Re: [PATCH 1/3] maple_tree: index has been checked to be smaller than pivot

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [241115 20:48]:
> At the beginning of loop, it has checked the range is in lower bounds.
> 
> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
> CC: Liam R. Howlett <Liam.Howlett@Oracle.com>
> CC: Lorenzo Stoakes <lorenzo.stoakes@oracle.com>
> CC: Sidhartha Kumar <sidhartha.kumar@oracle.com>

looks good.

Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

> ---
>  lib/maple_tree.c | 13 ++++++-------
>  1 file changed, 6 insertions(+), 7 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 667326717f35..63dccd7b9474 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -4893,13 +4893,12 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size)
>  				found = true;
>  				goto done;
>  			}
> -			if (mas->index <= pivot) {
> -				mas->node = mas_slot(mas, slots, offset);
> -				mas->min = min;
> -				mas->max = pivot;
> -				offset = 0;
> -				break;
> -			}
> +
> +			mas->node = mas_slot(mas, slots, offset);
> +			mas->min = min;
> +			mas->max = pivot;
> +			offset = 0;
> +			break;
>  		}
>  next_slot:
>  		min = pivot + 1;
> -- 
> 2.34.1
> 

[PATCH 2/3] maple_tree: not possible to be a root node after loop

[Wei Yang]

Empty tree and single entry tree is handled else whether, so the maple
tree here must be a tree with nodes.

If the height is 1 and we found the gap, it will jump to *done* since it
is also a leaf.
If the height is more than one, and there may be an available range, we
will descend the tree, which is not root anymore.

If there is no available range, we will set error and return.

This means the check for root node here is not necessary.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
CC: Liam R. Howlett <Liam.Howlett@Oracle.com>
CC: Lorenzo Stoakes <lorenzo.stoakes@oracle.com>
CC: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 63dccd7b9474..ab235d0194f7 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4891,7 +4891,7 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size)
 		if (gap >= size) {
 			if (ma_is_leaf(type)) {
 				found = true;
-				goto done;
+				break;
 			}
 
 			mas->node = mas_slot(mas, slots, offset);
@@ -4908,9 +4908,6 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size)
 		}
 	}
 
-	if (mte_is_root(mas->node))
-		found = true;
-done:
 	mas->offset = offset;
 	return found;
 }
-- 
2.34.1

Re: [PATCH 2/3] maple_tree: not possible to be a root node after loop

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [241115 20:48]:
> Empty tree and single entry tree is handled else whether, so the maple
> tree here must be a tree with nodes.
> 
> If the height is 1 and we found the gap, it will jump to *done* since it
> is also a leaf.
> If the height is more than one, and there may be an available range, we
> will descend the tree, which is not root anymore.
> 
> If there is no available range, we will set error and return.

Isn't this needed for the overflow case?  That is, if there is a range
that ends at ULONG_MAX, then we will break from the loop on the offset
limit, but not check for root, return false, and continue to loop.

> 
> This means the check for root node here is not necessary.
> 
> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
> CC: Liam R. Howlett <Liam.Howlett@Oracle.com>
> CC: Lorenzo Stoakes <lorenzo.stoakes@oracle.com>
> CC: Sidhartha Kumar <sidhartha.kumar@oracle.com>
> ---
>  lib/maple_tree.c | 5 +----
>  1 file changed, 1 insertion(+), 4 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 63dccd7b9474..ab235d0194f7 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -4891,7 +4891,7 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size)
>  		if (gap >= size) {
>  			if (ma_is_leaf(type)) {
>  				found = true;
> -				goto done;
> +				break;
>  			}
>  
>  			mas->node = mas_slot(mas, slots, offset);
> @@ -4908,9 +4908,6 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size)
>  		}
>  	}
>  
> -	if (mte_is_root(mas->node))
> -		found = true;
> -done:
>  	mas->offset = offset;
>  	return found;
>  }
> -- 
> 2.34.1
> 

Re: [PATCH 2/3] maple_tree: not possible to be a root node after loop

[Wei Yang]

On Mon, Nov 18, 2024 at 03:49:55PM -0500, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@gmail.com> [241115 20:48]:
>> Empty tree and single entry tree is handled else whether, so the maple
>> tree here must be a tree with nodes.
>> 
>> If the height is 1 and we found the gap, it will jump to *done* since it
>> is also a leaf.
>> If the height is more than one, and there may be an available range, we
>> will descend the tree, which is not root anymore.
>> 
>> If there is no available range, we will set error and return.
>
>Isn't this needed for the overflow case?  That is, if there is a range
>that ends at ULONG_MAX, then we will break from the loop on the offset
>limit, but not check for root, return false, and continue to loop.
>

I may not follow you correctly.

If there is an available range that ends at ULONG_MAX for a root node, we
break the loop with two conditions:

  * the root node is a leaf node, then we will set found to true
  * the root node has children, then descend to a non-root node

Not sure this is the case you mentioned.

-- 
Wei Yang
Help you, Help me

Re: [PATCH 2/3] maple_tree: not possible to be a root node after loop

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [241118 21:10]:
> On Mon, Nov 18, 2024 at 03:49:55PM -0500, Liam R. Howlett wrote:
> >* Wei Yang <richard.weiyang@gmail.com> [241115 20:48]:
> >> Empty tree and single entry tree is handled else whether, so the maple
> >> tree here must be a tree with nodes.
> >> 
> >> If the height is 1 and we found the gap, it will jump to *done* since it
> >> is also a leaf.
> >> If the height is more than one, and there may be an available range, we
> >> will descend the tree, which is not root anymore.
> >> 
> >> If there is no available range, we will set error and return.
> >
> >Isn't this needed for the overflow case?  That is, if there is a range
> >that ends at ULONG_MAX, then we will break from the loop on the offset
> >limit, but not check for root, return false, and continue to loop.
> >
> 
> I may not follow you correctly.
> 
> If there is an available range that ends at ULONG_MAX for a root node, we
> break the loop with two conditions:
> 
>   * the root node is a leaf node, then we will set found to true
>   * the root node has children, then descend to a non-root node
> 
> Not sure this is the case you mentioned.

I am concerned of the case where there isn't a gap in the last slot of a
leaf root node.  Examining it, I think we are okay.

next_slot:
                min = pivot + 1; <-----min = 0, overflow.
                if (mas->last <= pivot) { <-- still okay.
                        mas_set_err(mas, -EBUSY);
                        return true;
                }

Re: [PATCH 2/3] maple_tree: not possible to be a root node after loop

[Wei Yang]

On Tue, Nov 19, 2024 at 09:12:31AM -0500, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@gmail.com> [241118 21:10]:
>> On Mon, Nov 18, 2024 at 03:49:55PM -0500, Liam R. Howlett wrote:
>> >* Wei Yang <richard.weiyang@gmail.com> [241115 20:48]:
>> >> Empty tree and single entry tree is handled else whether, so the maple
>> >> tree here must be a tree with nodes.
>> >> 
>> >> If the height is 1 and we found the gap, it will jump to *done* since it
>> >> is also a leaf.
>> >> If the height is more than one, and there may be an available range, we
>> >> will descend the tree, which is not root anymore.
>> >> 
>> >> If there is no available range, we will set error and return.
>> >
>> >Isn't this needed for the overflow case?  That is, if there is a range
>> >that ends at ULONG_MAX, then we will break from the loop on the offset
>> >limit, but not check for root, return false, and continue to loop.
>> >
>> 
>> I may not follow you correctly.
>> 
>> If there is an available range that ends at ULONG_MAX for a root node, we
>> break the loop with two conditions:
>> 
>>   * the root node is a leaf node, then we will set found to true
>>   * the root node has children, then descend to a non-root node
>> 
>> Not sure this is the case you mentioned.
>
>I am concerned of the case where there isn't a gap in the last slot of a
>leaf root node.  Examining it, I think we are okay.
>
>next_slot:
>                min = pivot + 1; <-----min = 0, overflow.

Oh, this overflow.

>                if (mas->last <= pivot) { <-- still okay.
>                        mas_set_err(mas, -EBUSY);
>                        return true;
>                }

Thanks.

So it looks good to you ?

-- 
Wei Yang
Help you, Help me

Re: [PATCH 2/3] maple_tree: not possible to be a root node after loop

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [241121 02:13]:
> On Tue, Nov 19, 2024 at 09:12:31AM -0500, Liam R. Howlett wrote:
> >* Wei Yang <richard.weiyang@gmail.com> [241118 21:10]:
> >> On Mon, Nov 18, 2024 at 03:49:55PM -0500, Liam R. Howlett wrote:
> >> >* Wei Yang <richard.weiyang@gmail.com> [241115 20:48]:
> >> >> Empty tree and single entry tree is handled else whether, so the maple
> >> >> tree here must be a tree with nodes.
> >> >> 
> >> >> If the height is 1 and we found the gap, it will jump to *done* since it
> >> >> is also a leaf.
> >> >> If the height is more than one, and there may be an available range, we
> >> >> will descend the tree, which is not root anymore.
> >> >> 
> >> >> If there is no available range, we will set error and return.
> >> >
> >> >Isn't this needed for the overflow case?  That is, if there is a range
> >> >that ends at ULONG_MAX, then we will break from the loop on the offset
> >> >limit, but not check for root, return false, and continue to loop.
> >> >
> >> 
> >> I may not follow you correctly.
> >> 
> >> If there is an available range that ends at ULONG_MAX for a root node, we
> >> break the loop with two conditions:
> >> 
> >>   * the root node is a leaf node, then we will set found to true
> >>   * the root node has children, then descend to a non-root node
> >> 
> >> Not sure this is the case you mentioned.
> >
> >I am concerned of the case where there isn't a gap in the last slot of a
> >leaf root node.  Examining it, I think we are okay.
> >
> >next_slot:
> >                min = pivot + 1; <-----min = 0, overflow.
> 
> Oh, this overflow.
> 
> >                if (mas->last <= pivot) { <-- still okay.
> >                        mas_set_err(mas, -EBUSY);
> >                        return true;
> >                }
> 
> Thanks.
> 
> So it looks good to you ?

Yes,

Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

[PATCH 3/3] maple_tree: we don't set offset to MAPLE_NODE_SLOTS on error

[Wei Yang]

When mas_anode_descend() not find gap, it sets -EBUSY instead of setting
offset to MAPLE_NODE_SLOTS.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
CC: Liam R. Howlett <Liam.Howlett@Oracle.com>
CC: Lorenzo Stoakes <lorenzo.stoakes@oracle.com>
CC: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 7 ++-----
 1 file changed, 2 insertions(+), 5 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index ab235d0194f7..b67dae356182 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5011,8 +5011,8 @@ static inline void mas_awalk(struct ma_state *mas, unsigned long size)
 	 * There are 4 options:
 	 * go to child (descend)
 	 * go back to parent (ascend)
-	 * no gap found. (return, slot == MAPLE_NODE_SLOTS)
-	 * found the gap. (return, slot != MAPLE_NODE_SLOTS)
+	 * no gap found. (return, error == -EBUSY)
+	 * found the gap. (return)
 	 */
 	while (!mas_is_err(mas) && !mas_anode_descend(mas, size)) {
 		if (last == mas->node)
@@ -5097,9 +5097,6 @@ int mas_empty_area(struct ma_state *mas, unsigned long min,
 		return xa_err(mas->node);
 
 	offset = mas->offset;
-	if (unlikely(offset == MAPLE_NODE_SLOTS))
-		return -EBUSY;
-
 	node = mas_mn(mas);
 	mt = mte_node_type(mas->node);
 	pivots = ma_pivots(node, mt);
-- 
2.34.1

Re: [PATCH 3/3] maple_tree: we don't set offset to MAPLE_NODE_SLOTS on error

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [241115 20:48]:
> When mas_anode_descend() not find gap, it sets -EBUSY instead of setting
> offset to MAPLE_NODE_SLOTS.

This is for mas_start(), which I think is not necessary anymore.

> 
> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
> CC: Liam R. Howlett <Liam.Howlett@Oracle.com>
> CC: Lorenzo Stoakes <lorenzo.stoakes@oracle.com>
> CC: Sidhartha Kumar <sidhartha.kumar@oracle.com>
> ---
>  lib/maple_tree.c | 7 ++-----
>  1 file changed, 2 insertions(+), 5 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index ab235d0194f7..b67dae356182 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5011,8 +5011,8 @@ static inline void mas_awalk(struct ma_state *mas, unsigned long size)
>  	 * There are 4 options:
>  	 * go to child (descend)
>  	 * go back to parent (ascend)
> -	 * no gap found. (return, slot == MAPLE_NODE_SLOTS)
> -	 * found the gap. (return, slot != MAPLE_NODE_SLOTS)
> +	 * no gap found. (return, error == -EBUSY)
> +	 * found the gap. (return)
>  	 */
>  	while (!mas_is_err(mas) && !mas_anode_descend(mas, size)) {
>  		if (last == mas->node)
> @@ -5097,9 +5097,6 @@ int mas_empty_area(struct ma_state *mas, unsigned long min,
>  		return xa_err(mas->node);
>  
>  	offset = mas->offset;
> -	if (unlikely(offset == MAPLE_NODE_SLOTS))
> -		return -EBUSY;
> -
>  	node = mas_mn(mas);
>  	mt = mte_node_type(mas->node);
>  	pivots = ma_pivots(node, mt);
> -- 
> 2.34.1
> 

Re: [PATCH 3/3] maple_tree: we don't set offset to MAPLE_NODE_SLOTS on error

[Wei Yang]

On Mon, Nov 18, 2024 at 03:50:49PM -0500, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@gmail.com> [241115 20:48]:
>> When mas_anode_descend() not find gap, it sets -EBUSY instead of setting
>> offset to MAPLE_NODE_SLOTS.
>
>This is for mas_start(), which I think is not necessary anymore.

You mean mas_start() would set offset to MAPLE_NODE_SLOTS on ma_none and
ma_root?

Thanks for the information, I didn't realize this.

These two cases are handled by mas_sparse_area().

-- 
Wei Yang
Help you, Help me

Re: [PATCH 3/3] maple_tree: we don't set offset to MAPLE_NODE_SLOTS on error

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [241118 21:15]:
> On Mon, Nov 18, 2024 at 03:50:49PM -0500, Liam R. Howlett wrote:
> >* Wei Yang <richard.weiyang@gmail.com> [241115 20:48]:
> >> When mas_anode_descend() not find gap, it sets -EBUSY instead of setting
> >> offset to MAPLE_NODE_SLOTS.
> >
> >This is for mas_start(), which I think is not necessary anymore.
> 
> You mean mas_start() would set offset to MAPLE_NODE_SLOTS on ma_none and
> ma_root?
> 
> Thanks for the information, I didn't realize this.
> 
> These two cases are handled by mas_sparse_area().

Yeah, I'm not sure that needing this lived to the released code.

Re: [PATCH 3/3] maple_tree: we don't set offset to MAPLE_NODE_SLOTS on error

[Wei Yang]

On Tue, Nov 19, 2024 at 08:58:06AM -0500, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@gmail.com> [241118 21:15]:
>> On Mon, Nov 18, 2024 at 03:50:49PM -0500, Liam R. Howlett wrote:
>> >* Wei Yang <richard.weiyang@gmail.com> [241115 20:48]:
>> >> When mas_anode_descend() not find gap, it sets -EBUSY instead of setting
>> >> offset to MAPLE_NODE_SLOTS.
>> >
>> >This is for mas_start(), which I think is not necessary anymore.
>> 
>> You mean mas_start() would set offset to MAPLE_NODE_SLOTS on ma_none and
>> ma_root?
>> 
>> Thanks for the information, I didn't realize this.
>> 
>> These two cases are handled by mas_sparse_area().
>
>Yeah, I'm not sure that needing this lived to the released code.

I don't get you clearly.

What should I do next?

-- 
Wei Yang
Help you, Help me

Re: [PATCH 3/3] maple_tree: we don't set offset to MAPLE_NODE_SLOTS on error

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [241121 02:15]:
> On Tue, Nov 19, 2024 at 08:58:06AM -0500, Liam R. Howlett wrote:
> >* Wei Yang <richard.weiyang@gmail.com> [241118 21:15]:
> >> On Mon, Nov 18, 2024 at 03:50:49PM -0500, Liam R. Howlett wrote:
> >> >* Wei Yang <richard.weiyang@gmail.com> [241115 20:48]:
> >> >> When mas_anode_descend() not find gap, it sets -EBUSY instead of setting
> >> >> offset to MAPLE_NODE_SLOTS.
> >> >
> >> >This is for mas_start(), which I think is not necessary anymore.
> >> 
> >> You mean mas_start() would set offset to MAPLE_NODE_SLOTS on ma_none and
> >> ma_root?
> >> 
> >> Thanks for the information, I didn't realize this.
> >> 
> >> These two cases are handled by mas_sparse_area().
> >
> >Yeah, I'm not sure that needing this lived to the released code.
> 
> I don't get you clearly.
> 
> What should I do next?

This looks good.

Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>