| Message ID | 20230310140848.94485-2-zhangpeng.00@bytedance.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | Some fixes and cleanup for maple tree. | expand |
* Peng Zhang <zhangpeng.00@bytedance.com> [230310 09:09]: > if (likely(offset > end)) > max = pivots[offset]; > > The above code should be changed to if (likely(offset < end)), which is > correct. This affects the correctness of ma_data_end(). No. The way it is written is correct. If we are not at the last slot, then we take the pivot as the max for the next level of the tree. If we are at the last slot, then the max is already the correct value. >Now it seems > that the final result will not be wrong, but it is best to change it. Why is it best to change it? > This patch does not change the code as above, because it simplifies the > code by the way. > > Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com> > --- > lib/maple_tree.c | 15 +++++---------- > 1 file changed, 5 insertions(+), 10 deletions(-) > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > index 646297cae5d1..b3164266cfde 100644 > --- a/lib/maple_tree.c > +++ b/lib/maple_tree.c > @@ -3875,18 +3875,13 @@ static inline void *mtree_lookup_walk(struct ma_state *mas) > end = ma_data_end(node, type, pivots, max); > if (unlikely(ma_dead_node(node))) > goto dead_node; > - > - if (pivots[offset] >= mas->index) > - goto next; > - > do { > - offset++; > - } while ((offset < end) && (pivots[offset] < mas->index)); > - > - if (likely(offset > end)) > - max = pivots[offset]; > + if (pivots[offset] >= mas->index) { > + max = pivots[offset]; You can overflow the pivots array here because offset can actually be larger than the array. I am surprised this passes the maple tree test program, but with a full node and walking to the end, it will address the pivots array out of bounds. I wrote it the way I did to minimize the instructions in the loop by avoiding the overflow check. > + break; > + } > + } while (++offset < end); > > -next: > slots = ma_slots(node, type); > next = mt_slot(mas->tree, slots, offset); > if (unlikely(ma_dead_node(node))) > -- > 2.20.1 >
在 2023/3/11 01:58, Liam R. Howlett 写道: > * Peng Zhang <zhangpeng.00@bytedance.com> [230310 09:09]: >> if (likely(offset > end)) >> max = pivots[offset]; >> >> The above code should be changed to if (likely(offset < end)), which is >> correct. This affects the correctness of ma_data_end(). > No. The way it is written is correct. If we are not at the last slot, > then we take the pivot as the max for the next level of the tree. If we > are at the last slot, then the max is already the correct value. As you said, If we are not at the last slot, we take the pivot as the max for the next level of the tree. At this time, “offset < end” is satisfied, but in the original code, when offset > end, take the pivot as the max. Please *think again*, it is wrong. The code may have been written incorrectly by mistake, not what you said it was written. >> Now it seems >> that the final result will not be wrong, but it is best to change it. > Why is it best to change it? > >> This patch does not change the code as above, because it simplifies the >> code by the way. >> >> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com> >> --- >> lib/maple_tree.c | 15 +++++---------- >> 1 file changed, 5 insertions(+), 10 deletions(-) >> >> diff --git a/lib/maple_tree.c b/lib/maple_tree.c >> index 646297cae5d1..b3164266cfde 100644 >> --- a/lib/maple_tree.c >> +++ b/lib/maple_tree.c >> @@ -3875,18 +3875,13 @@ static inline void *mtree_lookup_walk(struct ma_state *mas) >> end = ma_data_end(node, type, pivots, max); >> if (unlikely(ma_dead_node(node))) >> goto dead_node; >> - >> - if (pivots[offset] >= mas->index) >> - goto next; >> - >> do { >> - offset++; >> - } while ((offset < end) && (pivots[offset] < mas->index)); >> - >> - if (likely(offset > end)) >> - max = pivots[offset]; >> + if (pivots[offset] >= mas->index) { >> + max = pivots[offset]; > You can overflow the pivots array here because offset can actually be > larger than the array. I am surprised this passes the maple tree test > program, but with a full node and walking to the end, it will address > the pivots array out of bounds. > > I wrote it the way I did to minimize the instructions in the loop by > avoiding the overflow check. It is not possible overflow pivots array, because only when "while (++offset < end)" is satisfied, we enter the loop body. So if we access pivots[offset], “offset < end” must be satisfied. Maybe you need to read the code to know, instead of looking at the diff. The modified code looks like this: do { if (pivots[offset] >= mas->index) { max = pivots[offset]; break; } } while (++offset < end); >> + break; >> + } >> + } while (++offset < end); >> >> -next: >> slots = ma_slots(node, type); >> next = mt_slot(mas->tree, slots, offset); >> if (unlikely(ma_dead_node(node))) >> -- >> 2.20.1 >>
* Peng Zhang <zhangpeng.00@bytedance.com> [230310 13:53]: > > 在 2023/3/11 01:58, Liam R. Howlett 写道: > > * Peng Zhang <zhangpeng.00@bytedance.com> [230310 09:09]: > > > if (likely(offset > end)) > > > max = pivots[offset]; > > > > > > The above code should be changed to if (likely(offset < end)), which is > > > correct. This affects the correctness of ma_data_end(). > > No. The way it is written is correct. If we are not at the last slot, > > then we take the pivot as the max for the next level of the tree. If we > > are at the last slot, then the max is already the correct value. > > As you said, If we are not at the last slot, we take the pivot as the max > for the next level of the tree. At this time, “offset < end” is satisfied, > but in the original code, when offset > end, take the pivot as the max. > Please *think again*, it is wrong. The code may have been written > incorrectly > by mistake, not what you said it was written. Sorry, yes. That does look like a bug. > > > > Now it seems > > > that the final result will not be wrong, but it is best to change it. > > Why is it best to change it? > > > > > This patch does not change the code as above, because it simplifies the > > > code by the way. > > > > > > Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com> > > > --- > > > lib/maple_tree.c | 15 +++++---------- > > > 1 file changed, 5 insertions(+), 10 deletions(-) > > > > > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > > > index 646297cae5d1..b3164266cfde 100644 > > > --- a/lib/maple_tree.c > > > +++ b/lib/maple_tree.c > > > @@ -3875,18 +3875,13 @@ static inline void *mtree_lookup_walk(struct ma_state *mas) > > > end = ma_data_end(node, type, pivots, max); > > > if (unlikely(ma_dead_node(node))) > > > goto dead_node; > > > - > > > - if (pivots[offset] >= mas->index) > > > - goto next; > > > - > > > do { > > > - offset++; > > > - } while ((offset < end) && (pivots[offset] < mas->index)); > > > - > > > - if (likely(offset > end)) > > > - max = pivots[offset]; > > > + if (pivots[offset] >= mas->index) { > > > + max = pivots[offset]; > > You can overflow the pivots array here because offset can actually be > > larger than the array. I am surprised this passes the maple tree test > > program, but with a full node and walking to the end, it will address > > the pivots array out of bounds. > > > > I wrote it the way I did to minimize the instructions in the loop by > > avoiding the overflow check. > > It is not possible overflow pivots array, because only when > "while (++offset < end)" is satisfied, we enter the loop body. > So if we access pivots[offset], “offset < end” must be satisfied. > Maybe you need to read the code to know, instead of looking at > the diff. > > The modified code looks like this: > > do { > if (pivots[offset] >= mas->index) { > max = pivots[offset]; > break; > } > } while (++offset < end); > Yes, you are right. It will terminate before overflowing. Since this is a fix, it needs a fixes tag in the commit log. Can you come up with a test case for this one as well? Fixes: 54a611b60590 ("Maple Tree: add new data structure") Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com> > > > + break; > > > + } > > > + } while (++offset < end); > > > -next: > > > slots = ma_slots(node, type); > > > next = mt_slot(mas->tree, slots, offset); > > > if (unlikely(ma_dead_node(node))) > > > -- > > > 2.20.1 > > >
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 646297cae5d1..b3164266cfde 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3875,18 +3875,13 @@ static inline void *mtree_lookup_walk(struct ma_state *mas) end = ma_data_end(node, type, pivots, max); if (unlikely(ma_dead_node(node))) goto dead_node; - - if (pivots[offset] >= mas->index) - goto next; - do { - offset++; - } while ((offset < end) && (pivots[offset] < mas->index)); - - if (likely(offset > end)) - max = pivots[offset]; + if (pivots[offset] >= mas->index) { + max = pivots[offset]; + break; + } + } while (++offset < end); -next: slots = ma_slots(node, type); next = mt_slot(mas->tree, slots, offset); if (unlikely(ma_dead_node(node)))
if (likely(offset > end)) max = pivots[offset]; The above code should be changed to if (likely(offset < end)), which is correct. This affects the correctness of ma_data_end(). Now it seems that the final result will not be wrong, but it is best to change it. This patch does not change the code as above, because it simplifies the code by the way. Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com> --- lib/maple_tree.c | 15 +++++---------- 1 file changed, 5 insertions(+), 10 deletions(-)