Skip to contentSkip to conversation

mas_anode_descend() related cleanup

PATCH Applied Wei Yang 2 participants 15 messages Nov 16, 2024 – Nov 22, 2024

Subsystems (3)
lore
Share & tools
lore

Wei Yang

author
#0 lore raw

cover mas_anode_descend() related cleanup

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(-)
Signature · 1 line
2.34.1
author
#1 lore raw

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

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

CC Liam R. Howlett <[email protected]>
CC Lorenzo Stoakes <[email protected]>
CC Sidhartha Kumar <[email protected]>
---
 lib/maple_tree.c | 13 ++++++-------
 1 file changed, 6 insertions(+), 7 deletions(-)
lib/maple_tree.c +6 -7
index 667326717f35..63dccd7b9474 100644
@@ -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;
Signature · 1 line
2.34.1
Reviewed-by on v1 1/3
#2 lore raw

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

Quoted 6 lines · Wei Yang

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

CC Liam R. Howlett <[email protected]>
CC Lorenzo Stoakes <[email protected]>
CC Sidhartha Kumar <[email protected]>

looks good.

Quoted 31 lines
---
 lib/maple_tree.c | 13 ++++++-------
 1 file changed, 6 insertions(+), 7 deletions(-)
lib/maple_tree.c +6 -7
index 667326717f35..63dccd7b9474 100644
@@ -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;
Signature · 1 line
2.34.1
author
#3 lore raw

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

In reply to 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.

CC Liam R. Howlett <[email protected]>
CC Lorenzo Stoakes <[email protected]>
CC Sidhartha Kumar <[email protected]>
---
 lib/maple_tree.c | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)
lib/maple_tree.c +1 -4
index 63dccd7b9474..ab235d0194f7 100644
@@ -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;
 }
Signature · 1 line
2.34.1
#4 lore raw

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

Quoted 9 lines · 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.

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.

Quoted 37 lines

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

CC Liam R. Howlett <[email protected]>
CC Lorenzo Stoakes <[email protected]>
CC Sidhartha Kumar <[email protected]>
---
 lib/maple_tree.c | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)
lib/maple_tree.c +1 -4
index 63dccd7b9474..ab235d0194f7 100644
@@ -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;
 }
Signature · 1 line
2.34.1
author
#5 lore raw

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

Quoted 9 lines · Liam R. Howlett
Quoted 8 lines · 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.

Quoted 6 lines
Quoted 1 line

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.

Signature · 2 lines
Wei Yang
Help you, Help me
#6 lore raw

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

Quoted 19 lines · Wei Yang
Quoted 9 lines · Liam R. Howlett
Quoted 8 lines · 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.

Quoted 6 lines
Quoted 1 line

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.

Quoted 7 lines

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;
                }
author
#7 lore raw

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

Quoted 26 lines · Liam R. Howlett
Quoted 25 lines · Wei Yang
Quoted 9 lines · Liam R. Howlett
Quoted 8 lines · 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.

Quoted 6 lines
Quoted 1 line

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

Quoted 7 lines
Quoted 1 line

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.

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

Thanks.

So it looks good to you ?

Signature · 2 lines
Wei Yang
Help you, Help me
Reviewed-by
#8 lore raw

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

Quoted 37 lines · Wei Yang
Quoted 26 lines · Liam R. Howlett
Quoted 25 lines · Wei Yang
Quoted 9 lines · Liam R. Howlett
Quoted 8 lines · 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.

Quoted 6 lines
Quoted 1 line

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

Quoted 7 lines
Quoted 1 line

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.

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

Thanks.

So it looks good to you ?

Yes,

author
#9 lore raw

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

In reply to Wei Yang

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

CC Liam R. Howlett <[email protected]>
CC Lorenzo Stoakes <[email protected]>
CC Sidhartha Kumar <[email protected]>
---
 lib/maple_tree.c | 7 ++-----
 1 file changed, 2 insertions(+), 5 deletions(-)
lib/maple_tree.c +2 -5
index ab235d0194f7..b67dae356182 100644
@@ -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);
Signature · 1 line
2.34.1
#10 lore raw

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

Quoted 2 lines · Wei Yang

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.

Quoted 37 lines
CC Liam R. Howlett <[email protected]>
CC Lorenzo Stoakes <[email protected]>
CC Sidhartha Kumar <[email protected]>
---
 lib/maple_tree.c | 7 ++-----
 1 file changed, 2 insertions(+), 5 deletions(-)
lib/maple_tree.c +2 -5
index ab235d0194f7..b67dae356182 100644
@@ -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);
Signature · 1 line
2.34.1
author
#11 lore raw

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

Quoted 5 lines · Liam R. Howlett
Quoted 2 lines · Wei Yang

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().

Signature · 2 lines
Wei Yang
Help you, Help me
#12 lore raw

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

Quoted 5 lines · Wei Yang
Quoted 4 lines · Liam R. Howlett
Quoted 2 lines · Wei Yang

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

Quoted 8 lines
Quoted 1 line

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.

author
#13 lore raw

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

Quoted 8 lines · Liam R. Howlett
Quoted 7 lines · Wei Yang
Quoted 5 lines · Liam R. Howlett
Quoted 2 lines · Wei Yang

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.

Quoted 8 lines
Quoted 6 lines

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?

Signature · 2 lines
Wei Yang
Help you, Help me
Reviewed-by
#14 lore raw

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

Quoted 14 lines · Wei Yang
Quoted 13 lines · Liam R. Howlett
Quoted 12 lines · Wei Yang
Quoted 5 lines · Liam R. Howlett
Quoted 2 lines · Wei Yang

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.

Quoted 7 lines
Quoted 3 lines
Quoted 1 line

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.