mas_anode_descend() related cleanup
Subsystems (3)
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
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.
--- lib/maple_tree.c | 13 ++++++------- 1 file changed, 6 insertions(+), 7 deletions(-)
lib/maple_tree.c +6 -7
@@ -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
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.
Signed-off-by Wei Yang <[email protected]>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@@ -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
PATCH 2/3 maple_tree: not possible to be a root node after loop
In reply to Wei YangEmpty 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.
--- lib/maple_tree.c | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-)
lib/maple_tree.c +1 -4
@@ -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
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.
Signed-off-by Wei Yang <[email protected]>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@@ -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
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
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_MAXfor 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 nodeNot 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
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_MAXfor 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
Liam R. Howlett
Reviewed-byRe: [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_MAXfor 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 nodeQuoted 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,
PATCH 3/3 maple_tree: we don't set offset to MAPLE_NODE_SLOTS on error
In reply to Wei YangWhen mas_anode_descend() not find gap, it sets -EBUSY instead of setting offset to MAPLE_NODE_SLOTS.
--- lib/maple_tree.c | 7 ++----- 1 file changed, 2 insertions(+), 5 deletions(-)
lib/maple_tree.c +2 -5
@@ -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
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-EBUSYinstead of setting offset toMAPLE_NODE_SLOTS.
This is for mas_start(), which I think is not necessary anymore.
Quoted 37 lines
Signed-off-by Wei Yang <[email protected]>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@@ -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
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-EBUSYinstead of setting offset toMAPLE_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
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-EBUSYinstead of setting offset toMAPLE_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 toMAPLE_NODE_SLOTSonma_noneandma_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
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-EBUSYinstead of setting offset toMAPLE_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 toMAPLE_NODE_SLOTSonma_noneandma_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
Liam R. Howlett
Reviewed-byRe: [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-EBUSYinstead of setting offset toMAPLE_NODE_SLOTS.This is for
mas_start(), which I think is not necessary anymore.You mean
mas_start()would set offset toMAPLE_NODE_SLOTSonma_noneandma_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.