| Message ID | 20241116014805.11547-3-richard.weiyang@gmail.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | mas_anode_descend() related cleanup | expand |
* 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 >
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 <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; }
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 ?
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; }
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(-)