From: "Paul E. McKenney" <firstname.lastname@example.org> To: Peter Zijlstra <email@example.com> Cc: firstname.lastname@example.org, email@example.com, firstname.lastname@example.org, email@example.com, firstname.lastname@example.org, email@example.com, firstname.lastname@example.org, email@example.com, firstname.lastname@example.org, email@example.com, Valdis.Kletnieks@vt.edu, firstname.lastname@example.org, email@example.com, firstname.lastname@example.org, email@example.com, firstname.lastname@example.org, email@example.com Subject: Re: [PATCH tip/core/rcu 18/23] rcu: Add random PROVE_RCU_DELAY to grace-period initialization Date: Thu, 6 Sep 2012 11:25:11 -0700 [thread overview] Message-ID: <20120906182511.GQ2448@linux.vnet.ibm.com> (raw) In-Reply-To: <1346941673.18408.21.camel@twins> On Thu, Sep 06, 2012 at 04:27:53PM +0200, Peter Zijlstra wrote: > On Thu, 2012-08-30 at 11:18 -0700, Paul E. McKenney wrote: > > > > 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 is the same scenario as the previous patch (17), right? Yep. That one fixed the race, this one makes the race more probable. > However did you find a 12-stage race like that, is that PROMELA goodness > or are you training to beat some chess champion? I saw actual test failures after introducing the patch moving the grace-period initialization process to a kthread. After chopping the original single patch into pieces and seeing that failures appeared at the point where I introduced preemption, it was clear what the overall form of the failure had to be. That said, it did take a few tries to work out the exact failure scenario. And I need to fix a few typos in it. :-/ RCU's state space is -way- too big for Promela to handle in one shot. So I have been working on three approaches: 1. Simplify RCU, or perhaps more accurately, introduce more invariants. 2. Work with various formal-methods people in the hope that we can come up with something that actually can (in)validate the Linux-kernel RCU implementation in one go. One of them did send me a draft paper formalizing RCU's semantics in a variant of separation logic, so progress is being made! 3. Do line-by-line documentation of the current implementation. This has resulted in some bug fixes and some of #1 above. But it is going quite slowly, especially given that I keep changing RCU. ;-) It is really cool seeing some formal-methods people willing to take on something like RCU! In addition, others in the same group have been working on taking the entire Linux kernel as written as input to their tools, in one case handling about a million lines of the kernel. Lots more work left to do, but meaningful progress! Thanx, Paul
next prev parent reply other threads:[~2012-09-06 18:25 UTC|newest] Thread overview: 85+ messages / expand[flat|nested] mbox.gz Atom feed top 2012-08-30 18:18 [PATCH tip/core/rcu 0/23] Improvements to RT response on big systems and expedited functions Paul E. McKenney 2012-08-30 18:18 ` [PATCH tip/core/rcu 01/23] rcu: Move RCU grace-period initialization into a kthread Paul E. McKenney 2012-08-30 18:18 ` [PATCH tip/core/rcu 02/23] rcu: Allow RCU grace-period initialization to be preempted Paul E. McKenney 2012-09-02 1:09 ` Josh Triplett 2012-09-05 1:22 ` Paul E. McKenney 2012-08-30 18:18 ` [PATCH tip/core/rcu 03/23] rcu: Move RCU grace-period cleanup into kthread Paul E. McKenney 2012-09-02 1:22 ` Josh Triplett 2012-09-06 13:34 ` Peter Zijlstra 2012-09-06 17:29 ` Paul E. McKenney 2012-08-30 18:18 ` [PATCH tip/core/rcu 04/23] rcu: Allow RCU grace-period cleanup to be preempted Paul E. McKenney 2012-09-02 1:36 ` Josh Triplett 2012-08-30 18:18 ` [PATCH tip/core/rcu 05/23] rcu: Prevent offline CPUs from executing RCU core code Paul E. McKenney 2012-09-02 1:45 ` Josh Triplett 2012-08-30 18:18 ` [PATCH tip/core/rcu 06/23] rcu: Break up rcu_gp_kthread() into subfunctions Paul E. McKenney 2012-09-02 2:11 ` Josh Triplett 2012-09-06 13:39 ` Peter Zijlstra 2012-09-06 17:32 ` Paul E. McKenney 2012-09-06 18:49 ` Josh Triplett 2012-09-06 19:09 ` Peter Zijlstra 2012-09-06 20:30 ` Paul E. McKenney 2012-09-06 20:30 ` Paul E. McKenney 2012-08-30 18:18 ` [PATCH tip/core/rcu 07/23] rcu: Provide OOM handler to motivate lazy RCU callbacks Paul E. McKenney 2012-09-02 2:13 ` Josh Triplett 2012-09-03 9:08 ` Lai Jiangshan 2012-09-05 17:45 ` Paul E. McKenney 2012-09-06 13:46 ` Peter Zijlstra 2012-09-06 13:52 ` Steven Rostedt 2012-09-06 17:41 ` Paul E. McKenney 2012-09-06 17:46 ` Peter Zijlstra 2012-09-06 20:32 ` Paul E. McKenney 2012-08-30 18:18 ` [PATCH tip/core/rcu 08/23] rcu: Segregate rcu_state fields to improve cache locality Paul E. McKenney 2012-09-02 2:51 ` Josh Triplett 2012-08-30 18:18 ` [PATCH tip/core/rcu 09/23] rcu: Move quiescent-state forcing into kthread Paul E. McKenney 2012-08-30 18:18 ` [PATCH tip/core/rcu 10/23] rcu: Allow RCU quiescent-state forcing to be preempted Paul E. McKenney 2012-09-02 5:23 ` Josh Triplett 2012-08-30 18:18 ` [PATCH tip/core/rcu 11/23] rcu: Adjust debugfs tracing for kthread-based quiescent-state forcing Paul E. McKenney 2012-09-02 6:05 ` Josh Triplett 2012-08-30 18:18 ` [PATCH tip/core/rcu 12/23] rcu: Prevent force_quiescent_state() memory contention Paul E. McKenney 2012-09-02 10:47 ` Josh Triplett 2012-08-30 18:18 ` [PATCH tip/core/rcu 13/23] rcu: Control grace-period duration from sysfs Paul E. McKenney 2012-09-03 9:30 ` Josh Triplett 2012-09-03 9:31 ` Josh Triplett 2012-09-06 14:15 ` Peter Zijlstra 2012-09-06 17:53 ` Paul E. McKenney 2012-09-06 18:28 ` Peter Zijlstra 2012-09-06 20:37 ` Paul E. McKenney 2012-08-30 18:18 ` [PATCH tip/core/rcu 14/23] rcu: Remove now-unused rcu_state fields Paul E. McKenney 2012-09-03 9:31 ` Josh Triplett 2012-09-06 14:17 ` Peter Zijlstra 2012-09-06 18:02 ` Paul E. McKenney 2012-08-30 18:18 ` [PATCH tip/core/rcu 15/23] rcu: Make rcutree module parameters visible in sysfs Paul E. McKenney 2012-09-03 9:32 ` Josh Triplett 2012-08-30 18:18 ` [PATCH tip/core/rcu 16/23] rcu: Prevent initialization-time quiescent-state race Paul E. McKenney 2012-09-03 9:37 ` Josh Triplett 2012-09-05 18:19 ` Paul E. McKenney 2012-09-05 18:55 ` Josh Triplett 2012-09-05 19:49 ` Paul E. McKenney 2012-09-06 14:21 ` Peter Zijlstra 2012-09-06 16:18 ` Paul E. McKenney 2012-09-06 16:22 ` Peter Zijlstra 2012-08-30 18:18 ` [PATCH tip/core/rcu 17/23] rcu: Fix day-zero grace-period initialization/cleanup race Paul E. McKenney 2012-09-03 9:39 ` Josh Triplett 2012-09-06 14:24 ` Peter Zijlstra 2012-09-06 18:06 ` Paul E. McKenney 2012-08-30 18:18 ` [PATCH tip/core/rcu 18/23] rcu: Add random PROVE_RCU_DELAY to grace-period initialization Paul E. McKenney 2012-09-03 9:41 ` Josh Triplett 2012-09-06 14:27 ` Peter Zijlstra 2012-09-06 18:25 ` Paul E. McKenney [this message] 2012-08-30 18:18 ` [PATCH tip/core/rcu 19/23] rcu: Adjust for unconditional ->completed assignment Paul E. McKenney 2012-09-03 9:42 ` Josh Triplett 2012-08-30 18:18 ` [PATCH tip/core/rcu 20/23] rcu: Remove callback acceleration from grace-period initialization Paul E. McKenney 2012-09-03 9:42 ` Josh Triplett 2012-08-30 18:18 ` [PATCH tip/core/rcu 21/23] rcu: Eliminate signed overflow in synchronize_rcu_expedited() Paul E. McKenney 2012-09-03 9:43 ` Josh Triplett 2012-08-30 18:18 ` [PATCH tip/core/rcu 22/23] rcu: Reduce synchronize_rcu_expedited() latency Paul E. McKenney 2012-09-03 9:46 ` Josh Triplett 2012-08-30 18:18 ` [PATCH tip/core/rcu 23/23] rcu: Simplify quiescent-state detection Paul E. McKenney 2012-09-03 9:56 ` Josh Triplett 2012-09-06 14:36 ` Peter Zijlstra 2012-09-06 20:01 ` Paul E. McKenney 2012-09-06 21:18 ` Mathieu Desnoyers 2012-09-06 21:31 ` Paul E. McKenney 2012-09-02 1:04 ` [PATCH tip/core/rcu 01/23] rcu: Move RCU grace-period initialization into a kthread Josh Triplett 2012-09-06 13:32 ` Peter Zijlstra 2012-09-06 17:00 ` Paul E. McKenney
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20120906182511.GQ2448@linux.vnet.ibm.com \ --firstname.lastname@example.org \ --cc=Valdis.Kletnieks@vt.edu \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --subject='Re: [PATCH tip/core/rcu 18/23] rcu: Add random PROVE_RCU_DELAY to grace-period initialization' \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: link
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).