[PATCH] util/interval-tree: Avoid race conditions without optimization

[PATCH] util/interval-tree: Avoid race conditions without optimization

[Richard Henderson]

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

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;
                 }
-- 
2.34.1

Re: [PATCH] util/interval-tree: Avoid race conditions without optimization

[Peter Maydell]

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

Re: [PATCH] util/interval-tree: Avoid race conditions without optimization

[Richard Henderson]

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~