From nobody Fri May 17 20:48:46 2024 Delivered-To: importer@patchew.org Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=pass(p=none dis=none) header.from=linaro.org ARC-Seal: i=1; a=rsa-sha256; t=1690062366; cv=none; d=zohomail.com; s=zohoarc; b=Ut87PXpmC6NKi8NTSLurnbTH2BrLL9dcCRcOo4tsh4x0ExBZxw4ea8tcNov7ZboAru5scIHGLyV5M++jiGL1qN+EA2+QMACli+xSsAs2i5kIBXnp0htcBqizSDw6SbJsatvsGUKpXpxAro9UREwHf7xTm3KIJf/HpkKOYmDDx2Q= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1690062366; h=Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=qG/YzCM95hrWGxKPyq8mYT9sLVAwD8vgBndl4G8LDU8=; b=C+n11VxXj5yXTj1lnQlRMxtXI7p/GOXxEM5wRYVfwvuUUnEncRq2dGmgD+X2OKHZcyQDLLm3tMN03QWARlSCf2jAUB+1Ubc096NwgySBiRrpy498n5b94pNUKnIAA8eQm0V0v+OY9GSqPL2nUrSsbWIEpeflcFcweXjpopz8N0I= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=pass header.from= (p=none dis=none) Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1690062366036276.4532886069827; Sat, 22 Jul 2023 14:46:06 -0700 (PDT) Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1qNKOx-0000IA-UE; Sat, 22 Jul 2023 17:44:36 -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 1qNKOw-0000HL-Ik for qemu-devel@nongnu.org; Sat, 22 Jul 2023 17:44:34 -0400 Received: from mail-wm1-x32d.google.com ([2a00:1450:4864:20::32d]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1qNKOo-000336-OI for qemu-devel@nongnu.org; Sat, 22 Jul 2023 17:44:34 -0400 Received: by mail-wm1-x32d.google.com with SMTP id 5b1f17b1804b1-3fbd33a57b6so29116425e9.2 for ; Sat, 22 Jul 2023 14:44:26 -0700 (PDT) Received: from stoup.acentic.lan (179.181-106-213.static.virginmediabusiness.co.uk. [213.106.181.179]) by smtp.gmail.com with ESMTPSA id v22-20020a7bcb56000000b003fbb9339b29sm8846384wmj.42.2023.07.22.14.44.24 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 22 Jul 2023 14:44:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1690062264; x=1690667064; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=qG/YzCM95hrWGxKPyq8mYT9sLVAwD8vgBndl4G8LDU8=; b=FnJSUEIylQCXrnkMbG/R/eKgzZm/VtYXdix7AAUvAWjf6mm2ghDWnDJ7TZkevjQBks cS1hx8c96NJ59BRH/BriT2xVOArZII1UghK05PD2+pTeA09090ASHLTR8Acig5PkZgsy Ax3dh/Y6MKln0mCnR+sjQkZHITjn6mohF+L6HyA4edZfChqKm7sPm+UuHjSI3XSmMyE/ DB9juBOwT2phhrwxcXTbJgJjcUhWW6RNYHbW0HzQpaPf90fyjim64zfIdnKmxRPXBOuY Z27KQ3YIVJ6I3hX2RCJyu4OzCANFcxztfXevBDu4l72WwCSHbLo1l8LrMcLFIpzHYjqT 8viw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690062264; x=1690667064; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=qG/YzCM95hrWGxKPyq8mYT9sLVAwD8vgBndl4G8LDU8=; b=aZL6RNy7IW9aLuziYcFLw3LZlysOCL3QZpepRYG1gFmBfQz3e1hbaDeSf21FYEFA0u JBASxE2CzDgZASUrmlRDqC7+wa0o7pVjlsGk9x7tR0xl+vBWY+0oq/U3rJXQvQV2DcSb EH68rnTJrczB6H0ppJwqEYQotI9dFqNHk3i8ibxL9GvFor42YRciuHV9U8t6ivZhcQZ6 n7B7BmsDIthFqc5lxuOUmtRG4uO5Hze9odbd2sMNBvB09a2UTd5wol+nc6bEeLG7mAOh COS4n/NZFwGEawhseA0CoTB7w4nDmJ9uDIs8PN88BXxuyCnwtXg8s5aG58BerONDY/rq oJKg== X-Gm-Message-State: ABy/qLbl6/pbLwarPjrIU+kZGNsNbUnPE0lpPpiPyuZvMQLrW9H5ATjR s0VYh7wO1B8CRoW5QaRxEnYwFZU5iQ6t94gvVqRRiw== X-Google-Smtp-Source: APBJJlHKH1K4Ta04G1njxJGDETANnYgY5mkIPGtrmXaLDQ1gjNlZ9shAhA2LHRAdpUwuVQ6rxlY7eg== X-Received: by 2002:a7b:c4d3:0:b0:3fd:2e28:655e with SMTP id g19-20020a7bc4d3000000b003fd2e28655emr1720045wmk.9.1690062264432; Sat, 22 Jul 2023 14:44:24 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Cc: peter.maydell@linaro.org, qemu-stable@nongnu.org Subject: [PATCH for-8.1 v2 1/4] util/interval-tree: Use qatomic_read for left/right while searching Date: Sat, 22 Jul 2023 22:44:19 +0100 Message-Id: <20230722214422.118743-2-richard.henderson@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230722214422.118743-1-richard.henderson@linaro.org> References: <20230722214422.118743-1-richard.henderson@linaro.org> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Received-SPF: pass client-ip=2a00:1450:4864:20::32d; envelope-from=richard.henderson@linaro.org; helo=mail-wm1-x32d.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 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+importer=patchew.org@nongnu.org Sender: qemu-devel-bounces+importer=patchew.org@nongnu.org X-ZohoMail-DKIM: pass (identity @linaro.org) X-ZM-MESSAGEID: 1690062368088100003 Content-Type: text/plain; charset="utf-8" Fixes a race condition (generally without optimization) in which the subtree is re-read after the protecting if condition. Cc: qemu-stable@nongnu.org Signed-off-by: Richard Henderson Reviewed-by: Peter Maydell --- util/interval-tree.c | 15 +++++++++------ 1 file changed, 9 insertions(+), 6 deletions(-) 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(I= ntervalTreeNode *node, * Loop invariant: start <=3D node->subtree_last * (Cond2 is satisfied by one of the subtree nodes) */ - if (node->rb.rb_left) { - IntervalTreeNode *left =3D rb_to_itree(node->rb.rb_left); + RBNode *tmp =3D qatomic_read(&node->rb.rb_left); + if (tmp) { + IntervalTreeNode *left =3D rb_to_itree(tmp); =20 if (start <=3D left->subtree_last) { /* @@ -765,8 +766,9 @@ static IntervalTreeNode *interval_tree_subtree_search(I= ntervalTreeNode *node, if (start <=3D node->last) { /* Cond2 */ return node; /* node is leftmost match */ } - if (node->rb.rb_right) { - node =3D rb_to_itree(node->rb.rb_right); + tmp =3D qatomic_read(&node->rb.rb_right); + if (tmp) { + node =3D rb_to_itree(tmp); if (start <=3D node->subtree_last) { continue; } @@ -814,8 +816,9 @@ IntervalTreeNode *interval_tree_iter_first(IntervalTree= Root *root, IntervalTreeNode *interval_tree_iter_next(IntervalTreeNode *node, uint64_t start, uint64_t last) { - RBNode *rb =3D node->rb.rb_right, *prev; + RBNode *rb, *prev; =20 + rb =3D qatomic_read(&node->rb.rb_right); while (true) { /* * Loop invariants: @@ -840,7 +843,7 @@ IntervalTreeNode *interval_tree_iter_next(IntervalTreeN= ode *node, } prev =3D &node->rb; node =3D rb_to_itree(rb); - rb =3D node->rb.rb_right; + rb =3D qatomic_read(&node->rb.rb_right); } while (prev =3D=3D rb); =20 /* Check if the node intersects [start;last] */ --=20 2.34.1 From nobody Fri May 17 20:48:46 2024 Delivered-To: importer@patchew.org Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=pass(p=none dis=none) header.from=linaro.org ARC-Seal: i=1; a=rsa-sha256; t=1690062363; cv=none; d=zohomail.com; s=zohoarc; b=TQbDEWxRxrXxfOzn03j4dTuI+14a4CRn26vtMXF4KdCRmksu+VGcxPp2IU7G2tlu4nHLQQODo4pkrtsXiIvD92aEgHs7hTQadDZ3MO7d1sUdkkhaJnhywYd8HJAo2a8y+yp8gNi45Jnf8AN+2O+OCp/jqjHzHKf4S7zOdFWLj3Y= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1690062363; h=Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=RIXdZdL1FiTxhzgwxu6CqaY5btcznVXT/yw1VVMrSHI=; b=n1zJAhffgrx1h3su0/ltbbYYAJBgC1BciMAi6BFIE6k9f2EYNfwvDZ63/barK/PT2qxMBiGCGZnbjl7xXBe0+XLOrWb08NFxREOP0rl/2mMRTLTDHg6k5RxeGVnXesCTmp78CBzECeqPvdasEIAQ4o6uzmIMWY65T0euKct5+iU= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=pass header.from= (p=none dis=none) Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1690062363447241.56956804791264; Sat, 22 Jul 2023 14:46:03 -0700 (PDT) Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1qNKOx-0000I7-Rd; Sat, 22 Jul 2023 17:44:35 -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 1qNKOw-0000HK-H1 for qemu-devel@nongnu.org; Sat, 22 Jul 2023 17:44:34 -0400 Received: from mail-wm1-x32a.google.com ([2a00:1450:4864:20::32a]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1qNKOo-00033F-Ob for qemu-devel@nongnu.org; Sat, 22 Jul 2023 17:44:34 -0400 Received: by mail-wm1-x32a.google.com with SMTP id 5b1f17b1804b1-3fbc244d384so25481715e9.0 for ; Sat, 22 Jul 2023 14:44:26 -0700 (PDT) Received: from stoup.acentic.lan (179.181-106-213.static.virginmediabusiness.co.uk. [213.106.181.179]) by smtp.gmail.com with ESMTPSA id v22-20020a7bcb56000000b003fbb9339b29sm8846384wmj.42.2023.07.22.14.44.24 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 22 Jul 2023 14:44:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1690062265; x=1690667065; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=RIXdZdL1FiTxhzgwxu6CqaY5btcznVXT/yw1VVMrSHI=; b=M96gN/5DHwpuCZVjhRfoYzlfy4pqbWMZ1ssy3loBVh9cXoaD+nyp8Bga6sH53i74CJ IgK7kC215BXga+AJ0psvTBZNPlWf+dnQadMVzv+CT6hrh9OKPfi1TgKj5X+VfjqNNuYf cK9lrsVFES8w0HYF32jp9c+Ssdes27tIyDBP4YZLlDQdYjQlO+KonH15fLaqrPRI/i5Q 2qJ03QL2vJdUphEs60Tb62aaqNG7+SM8uhGjwk4mktaK69buETpJkLTyw/BKtJKe2Daa uyUpTWSEpuBSo4niE6H3a8R1ZQKUPoGPFrJwq6QwYQt6ICPvTVsx5DpvlfgqkpULloUW BSWA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690062265; x=1690667065; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=RIXdZdL1FiTxhzgwxu6CqaY5btcznVXT/yw1VVMrSHI=; b=g6ah6D0IAdzgVjOTLraX98p51sS642yfGTVRsGwKWrfJNlVfHdqCZtYvb2q8psa/7I 8bxu6yaa2PEHIpjvTh3fglYArBcFCSmlam6wA7Aok3+viQu6qoUMaNDUfJgWp+7SDGdr E9DGpo4wCf43FDg38FmLAEd71+9kcADlBXnavrmyHB2zWjLAP/UPGiN0BUtCo71Pymty WmNfPgSIHcAr6F8Lq5u7nFHhuBp8SNjD52AW5qx89oKBmPhZlOKSDEf3tiFwQ1V4Uv8t i4YQ0fLW5QfaRaz8V4UDt5jrrQsRs/MOtYClz40BldhTLpFqENm1vseM09bosm/uphvi 5BIQ== X-Gm-Message-State: ABy/qLYSJ3DHwKv+hWoa/lXCEY950r5M0QVVklM+a1pqY+/GMoomuNrD ix/7EW90BKu1HyR3TNnJcKZxxtwT9uaQKnskSNPxgQ== X-Google-Smtp-Source: APBJJlGu7nQ5xywulv/CIhLVX3CZPaZbPFRANn4lyLKhfa2hogojc2XxOeB0vUWTHEdpCKY+JWKuXg== X-Received: by 2002:a7b:cd0c:0:b0:3fc:7d2:e0c0 with SMTP id f12-20020a7bcd0c000000b003fc07d2e0c0mr4916595wmj.27.1690062265096; Sat, 22 Jul 2023 14:44:25 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Cc: peter.maydell@linaro.org, qemu-stable@nongnu.org Subject: [PATCH for-8.1 v2 2/4] util/interval-tree: Use qatomic_set_mb in rb_link_node Date: Sat, 22 Jul 2023 22:44:20 +0100 Message-Id: <20230722214422.118743-3-richard.henderson@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230722214422.118743-1-richard.henderson@linaro.org> References: <20230722214422.118743-1-richard.henderson@linaro.org> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Received-SPF: pass client-ip=2a00:1450:4864:20::32a; envelope-from=richard.henderson@linaro.org; helo=mail-wm1-x32a.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=unavailable 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+importer=patchew.org@nongnu.org Sender: qemu-devel-bounces+importer=patchew.org@nongnu.org X-ZohoMail-DKIM: pass (identity @linaro.org) X-ZM-MESSAGEID: 1690062364063100003 Content-Type: text/plain; charset="utf-8" Ensure that the stores to rb_left and rb_right are complete before inserting the new node into the tree. Otherwise a concurrent reader could see garbage in the new leaf. Cc: qemu-stable@nongnu.org Signed-off-by: Richard Henderson Reviewed-by: Peter Maydell --- util/interval-tree.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) diff --git a/util/interval-tree.c b/util/interval-tree.c index 5a0ad21b2d..759562db7d 100644 --- a/util/interval-tree.c +++ b/util/interval-tree.c @@ -128,7 +128,11 @@ static inline void rb_link_node(RBNode *node, RBNode *= parent, RBNode **rb_link) node->rb_parent_color =3D (uintptr_t)parent; node->rb_left =3D node->rb_right =3D NULL; =20 - qatomic_set(rb_link, node); + /* + * Ensure that node is initialized before insertion, + * as viewed by a concurrent search. + */ + qatomic_set_mb(rb_link, node); } =20 static RBNode *rb_next(RBNode *node) --=20 2.34.1 From nobody Fri May 17 20:48:46 2024 Delivered-To: importer@patchew.org Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=pass(p=none dis=none) header.from=linaro.org ARC-Seal: i=1; a=rsa-sha256; t=1690062355; cv=none; d=zohomail.com; s=zohoarc; b=OBJWg0ZNWQLN7H9jh1t7i+3+/IILgdAPu9R1Z1G6yy7pqqJQLB8j4W9qDppj0Bmi9DhBPJ0y56AGtsJw2aHs0bjdr3bn8orX+l7OhcNuXt11FJWS+zhsNq8FgVfpy97dSN9HZ7sY2yn2SRb1eUCoPT3r9VMJb2+HUCY4iY2LgmE= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1690062355; h=Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=Sf2hbqGSfpDYzrcF3FbPVWShzpIjn+H1soor9634WcY=; b=TUdsk+XZJm/TzD4zno3sY7ZwUdy8n2o6AsLVEqKmMiyqZORl/BgZNfNa1gw1bKIOOFbBa/4732ljMG/m15LjmCdwi2XsbTShdK01aDYN94s5lUWsHXW2MmG7vm/NaNHPSov/thP25ZsJ/uiYb3HujTgLJ/FkPp/Ow0hKo2qGXoo= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=pass header.from= (p=none dis=none) Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1690062355019346.35290663760634; Sat, 22 Jul 2023 14:45:55 -0700 (PDT) Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1qNKP1-0000JJ-07; Sat, 22 Jul 2023 17:44:40 -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 1qNKOx-0000Hw-H7 for qemu-devel@nongnu.org; Sat, 22 Jul 2023 17:44:35 -0400 Received: from mail-wm1-x330.google.com ([2a00:1450:4864:20::330]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1qNKOp-00033o-UP for qemu-devel@nongnu.org; Sat, 22 Jul 2023 17:44:35 -0400 Received: by mail-wm1-x330.google.com with SMTP id 5b1f17b1804b1-3fbc6ab5ff5so24863615e9.1 for ; Sat, 22 Jul 2023 14:44:27 -0700 (PDT) Received: from stoup.acentic.lan (179.181-106-213.static.virginmediabusiness.co.uk. [213.106.181.179]) by smtp.gmail.com with ESMTPSA id v22-20020a7bcb56000000b003fbb9339b29sm8846384wmj.42.2023.07.22.14.44.25 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 22 Jul 2023 14:44:25 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1690062265; x=1690667065; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=Sf2hbqGSfpDYzrcF3FbPVWShzpIjn+H1soor9634WcY=; b=VCmsbwMm/pC5uJgYalCqjoBmRknXJNdWpUOXF1a9Ad5oWyXV9lwji4ZUJyzCNVpJh1 ktaxM3rAv7ONxjQsPl1Ba6Ia0foHIzcRAKhR/5MZtq1iQKq9Cw0Hoisgzxo/JXqcupqE o/6MjE5GJWCeBR5f9Dj5Ammaf6wkt2qSanEmG8j0ZFf7wu5a77KE68+mw2suiUeDT1mX Pp7wmIrhXJ2o1VMPJgPIBpCIJjoGV+5o8AuTazLIV3jT5XbtrBRDy2+0iFEXcMNDlVqk M6KbKWBibpQGHL02F2wBH2mbeCOysHdeS04IT65OGpV0QzWP79Wh82HIePEUfmDNOMEA ALIA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690062265; x=1690667065; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Sf2hbqGSfpDYzrcF3FbPVWShzpIjn+H1soor9634WcY=; b=XFIuUEyynvBxXEEVgAM2wLzn5uIycf+Z7Z4mD6UJoBa0EnZNBxCPNajbHpfgr5MUIg oR0F/o5JPlXHLwbuq8WworuuYCoX1VuTub0olXzSSW03NUnuSeKKBRSyoHCgRjCFAJ16 yhZCgdsCel5bt8KuLWWCfBTfsvWCV70XQrYsG8TwonbsdZv4VRHKpLJ6VsepQpx1WXTZ P5O+ByIak37NbgCuLXQ/FZv/1N9s29pD1zL2DMh5zzfiLzlEK2cSkgu67o3PklFaTc1P hFj4Vf4A2uk17NLKHX7/JZgV7cAbuYPMhyi8TVybvh+iy8XKkqk8MoLYy63ezLQrPWVo PYfw== X-Gm-Message-State: ABy/qLYpjSIkCnMHEktnn3kmZehwkvoyVFT+rG4yU1oSoVHQUoaAM8lc rNXNyffUXgeCRq5wgXD2l9vqpvgNPmTr0ZEPb4/JHw== X-Google-Smtp-Source: APBJJlEuuDikT2pJiQlXFgHFavPM2qNz+7vucpNbWRone/0NB6AnHa97gwoLAe6/C3oCBcDR4Lom3A== X-Received: by 2002:a05:600c:2187:b0:3fb:d68d:4c6f with SMTP id e7-20020a05600c218700b003fbd68d4c6fmr4341570wme.14.1690062265599; Sat, 22 Jul 2023 14:44:25 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Cc: peter.maydell@linaro.org Subject: [PATCH for-8.2? v2 3/4] util/interval-tree: Introduce pc_parent Date: Sat, 22 Jul 2023 22:44:21 +0100 Message-Id: <20230722214422.118743-4-richard.henderson@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230722214422.118743-1-richard.henderson@linaro.org> References: <20230722214422.118743-1-richard.henderson@linaro.org> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Received-SPF: pass client-ip=2a00:1450:4864:20::330; envelope-from=richard.henderson@linaro.org; helo=mail-wm1-x330.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 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+importer=patchew.org@nongnu.org Sender: qemu-devel-bounces+importer=patchew.org@nongnu.org X-ZohoMail-DKIM: pass (identity @linaro.org) X-ZM-MESSAGEID: 1690062356512100003 Content-Type: text/plain; charset="utf-8" Signed-off-by: Richard Henderson Reviewed-by: Peter Maydell --- 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 759562db7d..d86c0752db 100644 --- a/util/interval-tree.c +++ b/util/interval-tree.c @@ -68,9 +68,14 @@ typedef struct RBAugmentCallbacks { void (*rotate)(RBNode *old, RBNode *new); } RBAugmentCallbacks; =20 +static inline RBNode *pc_parent(uintptr_t pc) +{ + return (RBNode *)(pc & ~1); +} + static inline RBNode *rb_parent(const RBNode *n) { - return (RBNode *)(n->rb_parent_color & ~1); + return pc_parent(n->rb_parent_color); } =20 static inline RBNode *rb_red_parent(const RBNode *n) @@ -532,7 +537,7 @@ static void rb_erase_augmented(RBNode *node, RBRoot *ro= ot, * so as to bypass rb_erase_color() later on. */ pc =3D node->rb_parent_color; - parent =3D rb_parent(node); + parent =3D pc_parent(pc); rb_change_child(node, child, parent, root); if (child) { child->rb_parent_color =3D pc; @@ -544,7 +549,7 @@ static void rb_erase_augmented(RBNode *node, RBRoot *ro= ot, } else if (!child) { /* Still case 1, but this time the child is node->rb_left */ pc =3D node->rb_parent_color; - parent =3D rb_parent(node); + parent =3D pc_parent(pc); tmp->rb_parent_color =3D pc; rb_change_child(node, tmp, parent, root); rebalance =3D NULL; @@ -600,7 +605,7 @@ static void rb_erase_augmented(RBNode *node, RBRoot *ro= ot, rb_set_parent(tmp, successor); =20 pc =3D node->rb_parent_color; - tmp =3D rb_parent(node); + tmp =3D pc_parent(pc); rb_change_child(node, successor, tmp, root); =20 if (child2) { --=20 2.34.1 From nobody Fri May 17 20:48:46 2024 Delivered-To: importer@patchew.org Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=pass(p=none dis=none) header.from=linaro.org ARC-Seal: i=1; a=rsa-sha256; t=1690062380; cv=none; d=zohomail.com; s=zohoarc; b=WOHN7iDSL5PJGkWkdsWazziU6yIe5hc8DBDWZZ7zj3jZvr5wEqxoIIGF1pPESwlvls5c0P2LyOlobHdF+lGp4bKhWmpxePDxMt4XEY5oK/RKgV1a/hO1Q9eBHDWz2YNqscyTIw5pG5HquvlmpOTuyUuSh65TUYOoZXxIrf7WoKY= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1690062380; h=Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=fNV9KjzEsBoviNOMWq+gTDNaJIuDvwgsDMpOIIStNx8=; b=I6u3NJF9pUp/fqWTZVNqP9+Saa261wlBFkmEBkjt48kb2oVLbrsW7kqPZx/K+UOnPao3o2wXMIsjjtYt+Z6tJwVFUz41YktlorhaRM0rmhEqDy0TZkgqlFGTUh5uMRi0XjBNJzOiVOWs+lae4xaPnCT6RSU0QzLB8m5L9ljWRsE= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=pass header.from= (p=none dis=none) Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 169006238000349.16239474675058; Sat, 22 Jul 2023 14:46:20 -0700 (PDT) Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1qNKP0-0000J4-E5; Sat, 22 Jul 2023 17:44:38 -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 1qNKOx-0000ID-U2 for qemu-devel@nongnu.org; Sat, 22 Jul 2023 17:44:35 -0400 Received: from mail-wm1-x32e.google.com ([2a00:1450:4864:20::32e]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1qNKOp-00033l-W4 for qemu-devel@nongnu.org; Sat, 22 Jul 2023 17:44:35 -0400 Received: by mail-wm1-x32e.google.com with SMTP id 5b1f17b1804b1-3fd190065a7so24704985e9.2 for ; Sat, 22 Jul 2023 14:44:27 -0700 (PDT) Received: from stoup.acentic.lan (179.181-106-213.static.virginmediabusiness.co.uk. [213.106.181.179]) by smtp.gmail.com with ESMTPSA id v22-20020a7bcb56000000b003fbb9339b29sm8846384wmj.42.2023.07.22.14.44.25 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 22 Jul 2023 14:44:25 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1690062266; x=1690667066; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=fNV9KjzEsBoviNOMWq+gTDNaJIuDvwgsDMpOIIStNx8=; b=gF5+FZ4INNFjFYpokp0BOEpjXOwZkfBxeCN36Lv7QoDkAvLudkOP5YGFMQquycS3H3 TMoHlvQegdVDS+QlyvHUTQztzDByyavfiQoGtwvjrn+t1AtfpjRF8RMzJ2hJXGkGlLPK xbBOD+8PALel8Ck/VXByfgk8nS7/cMch+j0yMIiS3z3LKnKrsaAveqK8a0b9LK5mHD8R JUeeHC/pNKbpIUi0akQf6JyH31MyaxdRQkoZRV8WkCcvGF3C4oKCjUodGer4sp9d7bTg 3pC22pbdfh8M+1fywz4kPUsBjIbPDBfOox0600We/IBvMv7W9IDagU2bT+7GTPYKcRw2 F1Pw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690062266; x=1690667066; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=fNV9KjzEsBoviNOMWq+gTDNaJIuDvwgsDMpOIIStNx8=; b=gEAYkaCiXzMSG6YADlC0IQit5Q50mxwEPRD28Qglu0+HQfXzBUF7f9WQ24pQS4cRMT KmQEDvfJnLxGoXAwFbN8RQxuOgP18ylUPab82ckDZLVv3WELp94vVlNboL8gR7IGTmMA 4omCLVoh6fPJkmHYFFU+gn7QBkp62yjlOAPKDeV0Vt3/kFZxxPFS8Nf52YGcu5J3m2ZC vCvn4IFJ8S9uVQgZ0UHB8evX7wF7KLXdtiCAnErS4xv7FOU+VydCf8XG4es+BLyupbdW HA+w3U1HH3QckoqDZR0KoCXJGZMhkyHqECufi0cyXxxqItqeexSIfZw+HqEyNBFT44Yg 9OYQ== X-Gm-Message-State: ABy/qLYxlml+6ydMkqLs+XyjnxhNP5R1aVWCPn2knOj4g7X+8pgP30ru +8vTuX7U+HilfAMREXZkn+JKFU8hw8pon2W/EJV8gQ== X-Google-Smtp-Source: APBJJlHhh6UrK0Odvo0F1qf04Ihrd8WlphlH9qcGHkfdUqddx+zdQ2IzXt9wQoypaafBnUvMN9qVRw== X-Received: by 2002:a05:600c:155:b0:3fc:10:b25b with SMTP id w21-20020a05600c015500b003fc0010b25bmr4344821wmm.21.1690062266052; Sat, 22 Jul 2023 14:44:26 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Cc: peter.maydell@linaro.org Subject: [PATCH for-8.2? v2 4/4] util/interval-tree: Use qatomic_read/set for rb_parent_color Date: Sat, 22 Jul 2023 22:44:22 +0100 Message-Id: <20230722214422.118743-5-richard.henderson@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230722214422.118743-1-richard.henderson@linaro.org> References: <20230722214422.118743-1-richard.henderson@linaro.org> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Received-SPF: pass client-ip=2a00:1450:4864:20::32e; envelope-from=richard.henderson@linaro.org; helo=mail-wm1-x32e.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 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+importer=patchew.org@nongnu.org Sender: qemu-devel-bounces+importer=patchew.org@nongnu.org X-ZohoMail-DKIM: pass (identity @linaro.org) X-ZM-MESSAGEID: 1690062382197100001 Content-Type: text/plain; charset="utf-8" While less susceptible to optimization problems than left and right, interval_tree_iter_next also reads rb_parent(), so make sure that stores and loads are atomic. This goes further than technically required, changing all loads to be atomic, rather than simply the ones in the iteration side. But it doesn't really affect the code generation on the rebalance side and is cleaner to handle everything the same. Signed-off-by: Richard Henderson Reviewed-by: Peter Maydell --- util/interval-tree.c | 47 ++++++++++++++++++++++++-------------------- 1 file changed, 26 insertions(+), 21 deletions(-) diff --git a/util/interval-tree.c b/util/interval-tree.c index d86c0752db..f2866aa7d3 100644 --- a/util/interval-tree.c +++ b/util/interval-tree.c @@ -48,12 +48,6 @@ * * It also guarantees that if the lookup returns an element it is the 'cor= rect' * one. But not returning an element does _NOT_ mean it's not present. - * - * NOTE: - * - * Stores to __rb_parent_color are not important for simple lookups so tho= se - * are left undone as of now. Nor did I check for loops involving parent - * pointers. */ =20 typedef enum RBColor @@ -68,6 +62,16 @@ typedef struct RBAugmentCallbacks { void (*rotate)(RBNode *old, RBNode *new); } RBAugmentCallbacks; =20 +static inline uintptr_t rb_pc(const RBNode *n) +{ + return qatomic_read(&n->rb_parent_color); +} + +static inline void rb_set_pc(RBNode *n, uintptr_t pc) +{ + qatomic_set(&n->rb_parent_color, pc); +} + static inline RBNode *pc_parent(uintptr_t pc) { return (RBNode *)(pc & ~1); @@ -75,12 +79,12 @@ static inline RBNode *pc_parent(uintptr_t pc) =20 static inline RBNode *rb_parent(const RBNode *n) { - return pc_parent(n->rb_parent_color); + return pc_parent(rb_pc(n)); } =20 static inline RBNode *rb_red_parent(const RBNode *n) { - return (RBNode *)n->rb_parent_color; + return (RBNode *)rb_pc(n); } =20 static inline RBColor pc_color(uintptr_t pc) @@ -100,27 +104,27 @@ static inline bool pc_is_black(uintptr_t pc) =20 static inline RBColor rb_color(const RBNode *n) { - return pc_color(n->rb_parent_color); + return pc_color(rb_pc(n)); } =20 static inline bool rb_is_red(const RBNode *n) { - return pc_is_red(n->rb_parent_color); + return pc_is_red(rb_pc(n)); } =20 static inline bool rb_is_black(const RBNode *n) { - return pc_is_black(n->rb_parent_color); + return pc_is_black(rb_pc(n)); } =20 static inline void rb_set_black(RBNode *n) { - n->rb_parent_color |=3D RB_BLACK; + rb_set_pc(n, rb_pc(n) | RB_BLACK); } =20 static inline void rb_set_parent_color(RBNode *n, RBNode *p, RBColor color) { - n->rb_parent_color =3D (uintptr_t)p | color; + rb_set_pc(n, (uintptr_t)p | color); } =20 static inline void rb_set_parent(RBNode *n, RBNode *p) @@ -186,9 +190,10 @@ static inline void rb_change_child(RBNode *old, RBNode= *new, static inline void rb_rotate_set_parents(RBNode *old, RBNode *new, RBRoot *root, RBColor color) { - RBNode *parent =3D rb_parent(old); + uintptr_t pc =3D rb_pc(old); + RBNode *parent =3D pc_parent(pc); =20 - new->rb_parent_color =3D old->rb_parent_color; + rb_set_pc(new, pc); rb_set_parent_color(old, new, color); rb_change_child(old, new, parent, root); } @@ -536,11 +541,11 @@ static void rb_erase_augmented(RBNode *node, RBRoot *= root, * and node must be black due to 4). We adjust colors locally * so as to bypass rb_erase_color() later on. */ - pc =3D node->rb_parent_color; + pc =3D rb_pc(node); parent =3D pc_parent(pc); rb_change_child(node, child, parent, root); if (child) { - child->rb_parent_color =3D pc; + rb_set_pc(child, pc); rebalance =3D NULL; } else { rebalance =3D pc_is_black(pc) ? parent : NULL; @@ -548,9 +553,9 @@ static void rb_erase_augmented(RBNode *node, RBRoot *ro= ot, tmp =3D parent; } else if (!child) { /* Still case 1, but this time the child is node->rb_left */ - pc =3D node->rb_parent_color; + pc =3D rb_pc(node); parent =3D pc_parent(pc); - tmp->rb_parent_color =3D pc; + rb_set_pc(tmp, pc); rb_change_child(node, tmp, parent, root); rebalance =3D NULL; tmp =3D parent; @@ -604,7 +609,7 @@ static void rb_erase_augmented(RBNode *node, RBRoot *ro= ot, qatomic_set(&successor->rb_left, tmp); rb_set_parent(tmp, successor); =20 - pc =3D node->rb_parent_color; + pc =3D rb_pc(node); tmp =3D pc_parent(pc); rb_change_child(node, successor, tmp, root); =20 @@ -614,7 +619,7 @@ static void rb_erase_augmented(RBNode *node, RBRoot *ro= ot, } else { rebalance =3D rb_is_black(successor) ? parent : NULL; } - successor->rb_parent_color =3D pc; + rb_set_pc(successor, pc); tmp =3D successor; } =20 --=20 2.34.1