From patchwork Fri Aug 4 19:16:24 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Michael Tokarev X-Patchwork-Id: 710234 Delivered-To: patch@linaro.org Received: by 2002:a05:6359:d30:b0:129:c516:61db with SMTP id gp48csp162683rwb; Fri, 4 Aug 2023 12:19:06 -0700 (PDT) X-Google-Smtp-Source: AGHT+IFRmYPRIW9chIjyp3nq9CBJixNiUL+PGQS8ZPiVGZHEfC3myNZq2mzO6gJXepAqxEsQ1rDC X-Received: by 2002:a05:622a:15d3:b0:40f:d849:5b19 with SMTP id d19-20020a05622a15d300b0040fd8495b19mr3735543qty.22.1691176746044; Fri, 04 Aug 2023 12:19:06 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1691176746; cv=none; d=google.com; s=arc-20160816; b=DMJDIsDY5qwds2wOIrqdPXabhgFf1JIp4Y6a2UTHpJ50nSGyUTR8DvfBS1pYhO7rNj hZM8TtrDl+1QYIO+clV2QDmMwaqwoF+axu+A9dWRoVwjBWj/g+PU1reWfMnb2F9uiPhN goD6XTIhJC//EH/A58nj3adc8PFGi+SyCL2N60MB/JqPFtcP75m+sLTAS3lnt9HX4t2d 4aRPdLKw166uOX4xt0f1/+JgzbPawUhHRn9XhAqWB/TOZ8CeKFXHvV9k8LVfswt1QGlq rPLED2AWSY1P7dOpEEKRpYL/EUj2uIlJOOlsCL/Fa9gckyasVBvuY+gj23NRrR10CW3g bqUw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:references:in-reply-to:message-id:date:subject:cc:to :from; bh=rfwL6c6jAIK//ovZvYw4PQAE19TbiMppmZMkjWPMQtc=; fh=Xkin6fdEYjnaOLU5AKa5pmdx6bOMlQ5vBl3viP607iU=; b=BcFDSSt81VCdqZdJ7enHAZAmfPWVeufoKa227VuvVUPYUl+dZX86UueBMOabUZFuPA VluuQigcitLatFmZ3NI1EPkoryBVXp59QJzNT8rDzE3Vqyo1xpj0x11Z0Nyk+aJqCif+ nSH9PJG5rEH42zqlONj0y1HkTdLjpJotbSqU6Yofz2/+u/XJlID0o3S/mIlNq/kvktem QJQggAnd/Ac5OcT9gj+U/4jS/yV+pMEFYZLSr0r5+anYwdQmgcIw1tuywyAFTzEvr91m oLDBuYRn/I1Lt8WdwKf9OGZgjDPBfh1vF/Lo35cQGJ1FWyqsPE0+P3OwOSEHMztrgi/t SceQ== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org" Return-Path: Received: from lists.gnu.org (lists.gnu.org. [209.51.188.17]) by mx.google.com with ESMTPS id 1-20020ac85941000000b00403676c96e8si1737193qtz.136.2023.08.04.12.19.05 for (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Fri, 04 Aug 2023 12:19:06 -0700 (PDT) Received-SPF: pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; Authentication-Results: mx.google.com; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org" Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1qS0IR-0000OZ-K6; Fri, 04 Aug 2023 15:17:11 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1qS0IP-0000Nw-VJ; Fri, 04 Aug 2023 15:17:10 -0400 Received: from isrv.corpit.ru ([86.62.121.231]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1qS0IO-0006xV-CZ; Fri, 04 Aug 2023 15:17:09 -0400 Received: from tsrv.corpit.ru (tsrv.tls.msk.ru [192.168.177.2]) by isrv.corpit.ru (Postfix) with ESMTP id AACE81845B; Fri, 4 Aug 2023 22:17:11 +0300 (MSK) Received: from tls.msk.ru (mjt.wg.tls.msk.ru [192.168.177.130]) by tsrv.corpit.ru (Postfix) with SMTP id 2BA031B89E; Fri, 4 Aug 2023 22:16:51 +0300 (MSK) Received: (nullmailer pid 1875714 invoked by uid 1000); Fri, 04 Aug 2023 19:16:49 -0000 From: Michael Tokarev To: qemu-devel@nongnu.org Cc: qemu-stable@nongnu.org, Richard Henderson , Peter Maydell , Michael Tokarev Subject: [Stable-8.0.4 41/63] util/interval-tree: Use qatomic_read for left/right while searching Date: Fri, 4 Aug 2023 22:16:24 +0300 Message-Id: <20230804191647.1875608-10-mjt@tls.msk.ru> X-Mailer: git-send-email 2.39.2 In-Reply-To: References: MIME-Version: 1.0 Received-SPF: pass client-ip=86.62.121.231; envelope-from=mjt@tls.msk.ru; helo=isrv.corpit.ru X-Spam_score_int: -68 X-Spam_score: -6.9 X-Spam_bar: ------ X-Spam_report: (-6.9 / 5.0 requ) BAYES_00=-1.9, RCVD_IN_DNSWL_HI=-5, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+patch=linaro.org@nongnu.org Sender: qemu-devel-bounces+patch=linaro.org@nongnu.org From: Richard Henderson Fixes a race condition (generally without optimization) in which the subtree is re-read after the protecting if condition. Cc: qemu-stable@nongnu.org Reviewed-by: Peter Maydell Signed-off-by: Richard Henderson (cherry picked from commit 055b86e0f0b4325117055d8d31c49011258f4af3) Signed-off-by: Michael Tokarev diff --git a/util/interval-tree.c b/util/interval-tree.c index 4c0baf108f..5a0ad21b2d 100644 --- a/util/interval-tree.c +++ b/util/interval-tree.c @@ -745,8 +745,9 @@ static IntervalTreeNode *interval_tree_subtree_search(IntervalTreeNode *node, * 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); + RBNode *tmp = qatomic_read(&node->rb.rb_left); + if (tmp) { + IntervalTreeNode *left = rb_to_itree(tmp); if (start <= left->subtree_last) { /* @@ -765,8 +766,9 @@ 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); + tmp = qatomic_read(&node->rb.rb_right); + if (tmp) { + node = rb_to_itree(tmp); if (start <= node->subtree_last) { continue; } @@ -814,8 +816,9 @@ IntervalTreeNode *interval_tree_iter_first(IntervalTreeRoot *root, IntervalTreeNode *interval_tree_iter_next(IntervalTreeNode *node, uint64_t start, uint64_t last) { - RBNode *rb = node->rb.rb_right, *prev; + RBNode *rb, *prev; + rb = qatomic_read(&node->rb.rb_right); while (true) { /* * Loop invariants: @@ -840,7 +843,7 @@ IntervalTreeNode *interval_tree_iter_next(IntervalTreeNode *node, } prev = &node->rb; node = rb_to_itree(rb); - rb = node->rb.rb_right; + rb = qatomic_read(&node->rb.rb_right); } while (prev == rb); /* Check if the node intersects [start;last] */