| Message ID | 20230707103036.5647-1-richard.henderson@linaro.org |
|---|---|
| State | New |
| Headers | show |
| Series | util/interval-tree: Avoid race conditions without optimization | expand |
On Fri, 7 Jul 2023 at 11:30, Richard Henderson <richard.henderson@linaro.org> wrote: > > Read the left and right trees once, so that the gating > tests are meaningful. This was only a problem at -O0, > where the compiler didn't CSE the two reads. > > Cc: qemu-stable@nongnu.org > Signed-off-by: Richard Henderson <richard.henderson@linaro.org> Reviewed-by: Peter Maydell <peter.maydell@linaro.org> If this data structure is intended to support operations being done on it while it's being mutated, shouldn't it be using the atomic accessors, though? That would make it clearer that you can't just undo the transformation made by this patch. thanks -- PMM
On 7/13/23 12:32, Peter Maydell wrote: > On Fri, 7 Jul 2023 at 11:30, Richard Henderson > <richard.henderson@linaro.org> wrote: >> >> Read the left and right trees once, so that the gating >> tests are meaningful. This was only a problem at -O0, >> where the compiler didn't CSE the two reads. >> >> Cc: qemu-stable@nongnu.org >> Signed-off-by: Richard Henderson <richard.henderson@linaro.org> > > Reviewed-by: Peter Maydell <peter.maydell@linaro.org> > > If this data structure is intended to support operations > being done on it while it's being mutated, shouldn't it > be using the atomic accessors, though? That would make > it clearer that you can't just undo the transformation > made by this patch. Yes, it probably should. I use qatomic_set() where the kernel used WRITE_ONCE, but there was no markup for the read side. r~
diff --git a/util/interval-tree.c b/util/interval-tree.c index 4c0baf108f..31978c32ac 100644 --- a/util/interval-tree.c +++ b/util/interval-tree.c @@ -741,12 +741,15 @@ static IntervalTreeNode *interval_tree_subtree_search(IntervalTreeNode *node, uint64_t last) { while (true) { + RBNode *rb_tmp; + /* * Loop invariant: start <= node->subtree_last * (Cond2 is satisfied by one of the subtree nodes) */ - if (node->rb.rb_left) { - IntervalTreeNode *left = rb_to_itree(node->rb.rb_left); + rb_tmp = node->rb.rb_left; + if (rb_tmp) { + IntervalTreeNode *left = rb_to_itree(rb_tmp); if (start <= left->subtree_last) { /* @@ -765,8 +768,10 @@ static IntervalTreeNode *interval_tree_subtree_search(IntervalTreeNode *node, if (start <= node->last) { /* Cond2 */ return node; /* node is leftmost match */ } - if (node->rb.rb_right) { - node = rb_to_itree(node->rb.rb_right); + + rb_tmp = node->rb.rb_right; + if (rb_tmp) { + node = rb_to_itree(rb_tmp); if (start <= node->subtree_last) { continue; }
Read the left and right trees once, so that the gating tests are meaningful. This was only a problem at -O0, where the compiler didn't CSE the two reads. Cc: qemu-stable@nongnu.org Signed-off-by: Richard Henderson <richard.henderson@linaro.org> --- util/interval-tree.c | 13 +++++++++---- 1 file changed, 9 insertions(+), 4 deletions(-)