From: James Huang <jamesclhuang@yahoo.com>
To: linux-kernel@vger.kernel.org, paulmck@linux.vnet.ibm.com
Subject: real-time preemption and RCU
Date: Thu, 11 Jun 2009 15:57:52 -0700 (PDT) [thread overview]
Message-ID: <38569.31214.qm@web83816.mail.sp1.yahoo.com> (raw)
Hi Paul,
I have read through your year 2005 document on real-time preemption and RCU.
It was very interesting and your approach to the problem (by gradual improvement in each new implementation) make the idea very clear.
However, I am baffled by the following potential race condition that exists in implementation 2 through 5.
To keep the case simple, let's choose implementation 2 to illustrate:
CPU0 |<-- delete M1 -->| || |<---- delete M2 --->| <------ delete M3 ---->|
||
||
CPU1 |<----- read M1--------->| || |<------------------------- read M2 --------------------------------------->|
||
||
CPU2 time T: execute synchronize_kernel: rcu_ctrlblk.batch++
Assume initially
rcu_data[cpu0].batch = 1
rcu_data[cpu1].batch = 1
rcu_data[cpu2].batch = 1
rcu_ctrlblk.batch = 1
The following steps are executed:
(1) cpu1 read-locked rcu_ctrlblk.lock, read M1, read-unlocked rcu_ctrlblk.lock
(2) cpu0 deleted M1
(3) At time T (marked by || ), cpu2 executed synchronize_kernel: write-locked rcu_ctrlblk.lock, incremented rcu_ctrlblk.batch to 2, and write-unlocked rcu_ctrlblk.lock
(4) cpu1 read-locked rcu_ctrlblk.lock, spent a long time in its rcu read-side critical section, read M2, read-unlocked rcu_ctrlblk.lock
(5) cpu0 deleted M2. But when it executed run_rcu(), cpu0 DID NOT see the most up-to-date value of rcu_ctrlblk.batch.
So cpu0 just inserted M2 into cpu0's waitlist, but did not free up M1 and did not update rcu_data[cpu0].batch (i.e. it was still equal to 1).
(6) cpu0 deleted M3. At this time cpu0 saw the most up-to-date value of rcu_ctrlblk.batch (2).
Since rcu_ctrlblk.batch (2) is larger than rcu_data[cpu0].batch (1), cpu0 freed up memory blocks in its waitlist.
So both M1 and M2 were freed up by cpu0. But if cpu1 was still accessing M2, this will be a problem.
Am I missing something here? Does the smp_mb() within run_do_my_batch() has anything to do with this issue?
-- James Huang
next reply other threads:[~2009-06-11 23:04 UTC|newest]
Thread overview: 58+ messages / expand[flat|nested] mbox.gz Atom feed top
2009-06-11 22:57 James Huang [this message]
-- strict thread matches above, loose matches on Subject: below --
2005-03-18 0:20 Real-Time Preemption and RCU Paul E. McKenney
2005-03-18 7:49 ` Ingo Molnar
2005-03-18 16:43 ` Paul E. McKenney
2005-03-18 17:11 ` Ingo Molnar
2005-03-18 17:29 ` Paul E. McKenney
2005-03-18 20:35 ` Paul E. McKenney
2005-03-18 22:22 ` Paul E. McKenney
2005-03-19 0:48 ` Paul E. McKenney
2005-03-18 8:44 ` Ingo Molnar
2005-03-18 9:04 ` Ingo Molnar
2005-03-18 9:38 ` Ingo Molnar
2005-03-18 9:13 ` Ingo Molnar
2005-03-18 9:28 ` Ingo Molnar
2005-03-18 9:53 ` Ingo Molnar
2005-03-18 15:33 ` Paul E. McKenney
2005-03-19 5:03 ` Manfred Spraul
2005-03-19 16:26 ` Ingo Molnar
2005-03-20 6:36 ` Manfred Spraul
2005-03-20 9:25 ` Thomas Gleixner
2005-03-20 16:57 ` Manfred Spraul
2005-03-20 21:38 ` Bill Huey
2005-03-20 21:59 ` Bill Huey
2005-03-18 10:03 ` Ingo Molnar
2005-03-18 11:30 ` Ingo Molnar
2005-03-18 16:48 ` Esben Nielsen
2005-03-18 17:19 ` Ingo Molnar
2005-03-20 13:29 ` Esben Nielsen
2005-03-20 22:38 ` Paul E. McKenney
2005-03-20 23:23 ` Esben Nielsen
2005-03-22 5:53 ` Paul E. McKenney
2005-03-22 8:55 ` Esben Nielsen
2005-03-22 9:20 ` Ingo Molnar
2005-03-22 10:19 ` Esben Nielsen
2005-03-23 5:40 ` Paul E. McKenney
2005-03-23 11:44 ` Esben Nielsen
2005-03-24 7:02 ` Paul E. McKenney
2005-03-22 10:56 ` Ingo Molnar
2005-03-22 11:39 ` Esben Nielsen
2005-03-22 13:10 ` Ingo Molnar
2005-03-22 15:08 ` Esben Nielsen
2005-03-18 15:48 ` Paul E. McKenney
2005-03-18 11:38 ` Ingo Molnar
2005-03-18 12:56 ` Bill Huey
2005-03-18 13:17 ` Bill Huey
2005-03-18 15:57 ` Paul E. McKenney
2005-03-18 16:02 ` Ingo Molnar
2005-03-18 16:55 ` Esben Nielsen
2005-03-22 10:04 ` Bill Huey
2005-03-22 10:17 ` Bill Huey
2005-03-22 10:34 ` Bill Huey
2005-03-22 10:38 ` Esben Nielsen
2005-03-18 22:26 ` Herbert Xu
2005-03-19 16:31 ` Ingo Molnar
2005-03-20 8:01 ` Kyle Moffett
2005-03-22 8:08 ` Ingo Molnar
2005-03-18 15:54 ` Paul E. McKenney
2005-03-18 15:58 ` Ingo Molnar
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=38569.31214.qm@web83816.mail.sp1.yahoo.com \
--to=jamesclhuang@yahoo.com \
--cc=linux-kernel@vger.kernel.org \
--cc=paulmck@linux.vnet.ibm.com \
/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
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).