From patchwork Thu Aug 30 18:18:33 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Paul E. McKenney" X-Patchwork-Id: 11050 Return-Path: X-Original-To: patchwork@peony.canonical.com Delivered-To: patchwork@peony.canonical.com Received: from fiordland.canonical.com (fiordland.canonical.com [91.189.94.145]) by peony.canonical.com (Postfix) with ESMTP id 975D723EFE for ; Thu, 30 Aug 2012 18:19:47 +0000 (UTC) Received: from mail-iy0-f180.google.com (mail-iy0-f180.google.com [209.85.210.180]) by fiordland.canonical.com (Postfix) with ESMTP id 3F83DA1818E for ; Thu, 30 Aug 2012 18:19:11 +0000 (UTC) Received: by mail-iy0-f180.google.com with SMTP id j25so3403526iaf.11 for ; Thu, 30 Aug 2012 11:19:47 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=x-forwarded-to:x-forwarded-for:delivered-to:received-spf:from:to:cc :subject:date:message-id:x-mailer:in-reply-to:references :x-content-scanned:x-cbid:x-ibm-iss-spamdetectors :x-ibm-iss-detailinfo:x-gm-message-state; bh=DUgXpcUqBHvyJ5LYK/yK7tCETD/nvWWa2q7kSGt7x4A=; b=hImQmTj0Hk/4VVsN1rUxg9D5fhUZUMuSi/ea0/9a7rozBa4IKYD0c9sKRh1N0ir1in e7UZpPhdkeJB7GPC6JhGNRQju/qIULcn3pZEEc2FBx2Wrr4Hw5TcVpgDEYlxnqLFv6qS 5VYZzJYUENuIcD6PeNJaVUpcleCd1FgFQrfo7yZ0NxODE/oSsPkGn5vKIMDEcJmLWytb zaUHeclIHnnkkP2kg4BEDzCM6XRy+yrkyDFf29WWGrGJDI9r8H5lurbIbRqaJXvrpbey MfF00PhqT5ziRZhChEYf4jhj7bRNx7zma+P21bsTnvqHdr4P9v0YSoZE04HMKsQ/L5YZ 7+5Q== Received: by 10.50.242.3 with SMTP id wm3mr1906553igc.0.1346350786882; Thu, 30 Aug 2012 11:19:46 -0700 (PDT) X-Forwarded-To: linaro-patchwork@canonical.com X-Forwarded-For: patch@linaro.org linaro-patchwork@canonical.com Delivered-To: patches@linaro.org Received: by 10.50.184.232 with SMTP id ex8csp24733igc; Thu, 30 Aug 2012 11:19:46 -0700 (PDT) Received: by 10.60.7.33 with SMTP id g1mr5584797oea.113.1346350786415; Thu, 30 Aug 2012 11:19:46 -0700 (PDT) Received: from e33.co.us.ibm.com (e33.co.us.ibm.com. [32.97.110.151]) by mx.google.com with ESMTPS id t3si3106764oet.7.2012.08.30.11.19.45 (version=TLSv1/SSLv3 cipher=OTHER); Thu, 30 Aug 2012 11:19:46 -0700 (PDT) Received-SPF: pass (google.com: domain of paulmck@linux.vnet.ibm.com designates 32.97.110.151 as permitted sender) client-ip=32.97.110.151; Authentication-Results: mx.google.com; spf=pass (google.com: domain of paulmck@linux.vnet.ibm.com designates 32.97.110.151 as permitted sender) smtp.mail=paulmck@linux.vnet.ibm.com Received: from /spool/local by e33.co.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Thu, 30 Aug 2012 12:19:44 -0600 Received: from d03dlp02.boulder.ibm.com (9.17.202.178) by e33.co.us.ibm.com (192.168.1.133) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; Thu, 30 Aug 2012 12:19:42 -0600 Received: from d03relay04.boulder.ibm.com (d03relay04.boulder.ibm.com [9.17.195.106]) by d03dlp02.boulder.ibm.com (Postfix) with ESMTP id 646723E4007C for ; Thu, 30 Aug 2012 12:19:40 -0600 (MDT) Received: from d03av01.boulder.ibm.com (d03av01.boulder.ibm.com [9.17.195.167]) by d03relay04.boulder.ibm.com (8.13.8/8.13.8/NCO v10.0) with ESMTP id q7UIJdqG137476 for ; Thu, 30 Aug 2012 12:19:40 -0600 Received: from d03av01.boulder.ibm.com (loopback [127.0.0.1]) by d03av01.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVout) with ESMTP id q7UIIkwd019194 for ; Thu, 30 Aug 2012 12:18:57 -0600 Received: from paulmck-ThinkPad-W500 (sig-9-77-132-62.mts.ibm.com [9.77.132.62]) by d03av01.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVin) with ESMTP id q7UIIhYB018869; Thu, 30 Aug 2012 12:18:44 -0600 Received: by paulmck-ThinkPad-W500 (Postfix, from userid 1000) id DA016EA838; Thu, 30 Aug 2012 11:18:40 -0700 (PDT) From: "Paul E. McKenney" To: linux-kernel@vger.kernel.org Cc: mingo@elte.hu, laijs@cn.fujitsu.com, dipankar@in.ibm.com, akpm@linux-foundation.org, mathieu.desnoyers@polymtl.ca, josh@joshtriplett.org, niv@us.ibm.com, tglx@linutronix.de, peterz@infradead.org, rostedt@goodmis.org, Valdis.Kletnieks@vt.edu, dhowells@redhat.com, eric.dumazet@gmail.com, darren@dvhart.com, fweisbec@gmail.com, sbw@mit.edu, patches@linaro.org, "Paul E. McKenney" Subject: [PATCH tip/core/rcu 18/23] rcu: Add random PROVE_RCU_DELAY to grace-period initialization Date: Thu, 30 Aug 2012 11:18:33 -0700 Message-Id: <1346350718-30937-18-git-send-email-paulmck@linux.vnet.ibm.com> X-Mailer: git-send-email 1.7.8 In-Reply-To: <1346350718-30937-1-git-send-email-paulmck@linux.vnet.ibm.com> References: <20120830181811.GA29154@linux.vnet.ibm.com> <1346350718-30937-1-git-send-email-paulmck@linux.vnet.ibm.com> X-Content-Scanned: Fidelis XPS MAILER x-cbid: 12083018-2398-0000-0000-000009EA0156 X-IBM-ISS-SpamDetectors: X-IBM-ISS-DetailInfo: BY=3.00000293; HX=3.00000196; KW=3.00000007; PH=3.00000001; SC=3.00000007; SDB=6.00169857; UDB=6.00038507; UTC=2012-08-30 18:19:43 X-Gm-Message-State: ALoCoQlwHWt0mDC0eT8tu3Uoup8vuWU5YcidbH+EkwVT0zATGGFDtxq8/Qy01r0j1yrq9d/yz1PM From: "Paul E. McKenney" There are some additional potential grace-period initialization races on systems with more than one rcu_node structure, for example: 1. CPU 0 completes a grace period, but needs an additional grace period, so starts initializing one, initializing all the non-leaf rcu_node strcutures and the first leaf rcu_node structure. Because CPU 0 is both completing the old grace period and starting a new one, it marks the completion of the old grace period and the start of the new grace period in a single traversal of the rcu_node structures. Therefore, CPUs corresponding to the first rcu_node structure can become aware that the prior grace period has ended, but CPUs corresponding to the other rcu_node structures cannot yet become aware of this. 2. CPU 1 passes through a quiescent state, and therefore informs the RCU core. Because its leaf rcu_node structure has already been initialized, so this CPU's quiescent state is applied to the new (and only partially initialized) grace period. 3. CPU 1 enters an RCU read-side critical section and acquires a reference to data item A. Note that this critical section will not block the new grace period. 4. CPU 16 exits dyntick-idle mode. Because it was in dyntick-idle mode, some other CPU informed the RCU core of its extended quiescent state for the past several grace periods. This means that CPU 16 is not yet aware that these grace periods have ended. 5. CPU 16 on the second leaf rcu_node structure removes data item A from its enclosing data structure and passes it to call_rcu(), which queues a callback in the RCU_NEXT_TAIL segment of the callback queue. 6. CPU 16 enters the RCU core, possibly because it has taken a scheduling-clock interrupt, or alternatively because it has more than 10,000 callbacks queued. It notes that the second most recent grace period has ended (recall that it cannot yet become aware that the most recent grace period has completed), and therefore advances its callbacks. The callback for data item A is therefore in the RCU_NEXT_READY_TAIL segment of the callback queue. 7. CPU 0 completes initialization of the remaining leaf rcu_node structures for the new grace period, including the structure corresponding to CPU 16. 8. CPU 16 again enters the RCU core, again, possibly because it has taken a scheduling-clock interrupt, or alternatively because it now has more than 10,000 callbacks queued. It notes that the most recent grace period has ended, and therefore advances its callbacks. The callback for data item A is therefore in the RCU_NEXT_TAIL segment of the callback queue. 9. All CPUs other than CPU 1 pass through quiescent states, so that the new grace period completes. Note that CPU 1 is still in its RCU read-side critical section, still referencing data item A. 10. Suppose that CPU 2 is the last CPU to pass through a quiescent state for the new grace period, and suppose further that CPU 2 does not have any callbacks queued. It therefore traverses all of the rcu_node structures, marking the new grace period as completed, but does not initialize a new grace period. 11. CPU 16 yet again enters the RCU core, yet again possibly because it has taken a scheduling-clock interrupt, or alternatively because it now has more than 10,000 callbacks queued. It notes that the new grace period has ended, and therefore advances its callbacks. The callback for data item A is therefore in the RCU_DONE_TAIL segment of the callback queue. This means that this callback is now considered ready to be invoked. 12. CPU 16 invokes the callback, freeing data item A while CPU 1 is still referencing it. This sort of scenario represents a day-one bug for TREE_RCU, however, the recent changes that permit RCU grace-period initialization to be preempted made it much more probable. Still, it is sufficiently improbable to make validation lengthy and inconvenient, so this commit adds an anti-heisenbug to greatly increase the collision cross section, also known as the probability of occurrence. Signed-off-by: Paul E. McKenney Reviewed-by: Josh Triplett --- kernel/rcutree.c | 5 +++++ 1 files changed, 5 insertions(+), 0 deletions(-) diff --git a/kernel/rcutree.c b/kernel/rcutree.c index 4cfe488..1373388 100644 --- a/kernel/rcutree.c +++ b/kernel/rcutree.c @@ -52,6 +52,7 @@ #include #include #include +#include #include "rcutree.h" #include @@ -1105,6 +1106,10 @@ static int rcu_gp_init(struct rcu_state *rsp) rnp->level, rnp->grplo, rnp->grphi, rnp->qsmask); raw_spin_unlock_irqrestore(&rnp->lock, flags); +#ifdef CONFIG_PROVE_RCU_DELAY + if ((random32() % (rcu_num_nodes * 8)) == 0) + schedule_timeout_uninterruptible(2); +#endif /* #ifdef CONFIG_PROVE_RCU_DELAY */ cond_resched(); }