* [PATCH] rcu_nest: fix concurrency issues @ 2019-04-30 4:02 Junchang Wang 2019-05-02 14:59 ` Paul E. McKenney 0 siblings, 1 reply; 5+ messages in thread From: Junchang Wang @ 2019-04-30 4:02 UTC (permalink / raw) To: paulmck, akiyks; +Cc: perfbook, Junchang Wang Variable "rcu_gp_ctr" is incremented by the updater and is fetched by readers concurrently. So protect this variable by using READ_ONCE() and WRITE_ONCE(). Per-thread variable "rcu_read_gp" is updated by the reader and is read by the updater. So protect it by using READ_ONCE() and WRITE_ONCE(). The type of "rcu_gp_ctr" is changed to unsigned long because the behavior of the overflow of a signed long integer is not well defined in C yet. Refine the code snippet in "rcu_read_lock" that allows a reader to start over. In this version, we add micro MAX_GP_ADV_DISTANCE which is by default set to (RCU_GP_CTR_NEST_MASK << 8). Once a reader notices that MAX_GP_ADV_DISTANCE grace-periods have elapsed since fetching the value of "rcu_reader_gp", the reader starts over. Signed-off-by: Junchang Wang <junchangwang@gmail.com> --- CodeSamples/defer/rcu_nest.c | 5 +++-- CodeSamples/defer/rcu_nest.h | 25 +++++++++++++++++-------- 2 files changed, 20 insertions(+), 10 deletions(-) diff --git a/CodeSamples/defer/rcu_nest.c b/CodeSamples/defer/rcu_nest.c index 64e4087..362f466 100644 --- a/CodeSamples/defer/rcu_nest.c +++ b/CodeSamples/defer/rcu_nest.c @@ -35,7 +35,7 @@ void synchronize_rcu(void) /* Advance to a new grace-period number, enforce ordering. */ - rcu_gp_ctr += RCU_GP_CTR_BOTTOM_BIT; + WRITE_ONCE(rcu_gp_ctr, rcu_gp_ctr + RCU_GP_CTR_BOTTOM_BIT); smp_mb(); /* @@ -45,7 +45,8 @@ void synchronize_rcu(void) for_each_thread(t) { while (rcu_gp_ongoing(t) && - ((per_thread(rcu_reader_gp, t) - rcu_gp_ctr) < 0)) { + ((READ_ONCE(per_thread(rcu_reader_gp, t)) - + rcu_gp_ctr) < 0)) { /*@@@ poll(NULL, 0, 10); */ barrier(); } diff --git a/CodeSamples/defer/rcu_nest.h b/CodeSamples/defer/rcu_nest.h index bcc4cde..65ce203 100644 --- a/CodeSamples/defer/rcu_nest.h +++ b/CodeSamples/defer/rcu_nest.h @@ -24,8 +24,9 @@ DEFINE_SPINLOCK(rcu_gp_lock); #define RCU_GP_CTR_SHIFT 7 #define RCU_GP_CTR_BOTTOM_BIT (1 << RCU_GP_CTR_SHIFT) #define RCU_GP_CTR_NEST_MASK (RCU_GP_CTR_BOTTOM_BIT - 1) -long rcu_gp_ctr = 0; /* increment by RCU_GP_CTR_BOTTOM_BIT each gp. */ -DEFINE_PER_THREAD(long, rcu_reader_gp); +#define MAX_GP_ADV_DISTANCE (RCU_GP_CTR_NEST_MASK << 8) +unsigned long rcu_gp_ctr = 0; /* increment by RCU_GP_CTR_BOTTOM_BIT each gp. */ +DEFINE_PER_THREAD(unsigned long, rcu_reader_gp); static inline int rcu_gp_ongoing(int cpu) { @@ -39,8 +40,8 @@ static void rcu_init(void) static void rcu_read_lock(void) { - long tmp; - long *rrgp; + unsigned long tmp; + unsigned long *rrgp; /* * If this is the outermost RCU read-side critical section, @@ -52,13 +53,21 @@ static void rcu_read_lock(void) retry: tmp = *rrgp; if ((tmp & RCU_GP_CTR_NEST_MASK) == 0) - tmp = rcu_gp_ctr; + tmp = READ_ONCE(rcu_gp_ctr); tmp++; - *rrgp = tmp; + WRITE_ONCE(*rrgp, tmp); smp_mb(); + + /* + * A reader could be suspended in between fetching the value of *rrgp + * and writting the updated value back into *rrgp. During this + * time period, the grace-period counter might have advanced very far. + * In this case, we force the reader to start over. + */ + if (((tmp & RCU_GP_CTR_NEST_MASK) == 1) && - ((rcu_gp_ctr - tmp) > (RCU_GP_CTR_NEST_MASK << 8)) != 0) { - (*rrgp)--; + (READ_ONCE(rcu_gp_ctr) > tmp + MAX_GP_ADV_DISTANCE)) { + WRITE_ONCE(*rrgp, *rrgp - 1); goto retry; } } -- 2.7.4 ^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: [PATCH] rcu_nest: fix concurrency issues 2019-04-30 4:02 [PATCH] rcu_nest: fix concurrency issues Junchang Wang @ 2019-05-02 14:59 ` Paul E. McKenney 2019-05-05 13:16 ` Junchang Wang 0 siblings, 1 reply; 5+ messages in thread From: Paul E. McKenney @ 2019-05-02 14:59 UTC (permalink / raw) To: Junchang Wang; +Cc: akiyks, perfbook On Tue, Apr 30, 2019 at 12:02:39PM +0800, Junchang Wang wrote: > Variable "rcu_gp_ctr" is incremented by the updater and is fetched by > readers concurrently. So protect this variable by using READ_ONCE() > and WRITE_ONCE(). > > Per-thread variable "rcu_read_gp" is updated by the reader and is read > by the updater. So protect it by using READ_ONCE() and WRITE_ONCE(). > > The type of "rcu_gp_ctr" is changed to unsigned long because the behavior > of the overflow of a signed long integer is not well defined in C yet. > > Refine the code snippet in "rcu_read_lock" that allows a reader to start > over. In this version, we add micro MAX_GP_ADV_DISTANCE which is by > default set to (RCU_GP_CTR_NEST_MASK << 8). Once a reader notices that > MAX_GP_ADV_DISTANCE grace-periods have elapsed since fetching the value of > "rcu_reader_gp", the reader starts over. > > > Signed-off-by: Junchang Wang <junchangwang@gmail.com> First, thank you for doing this! Lots of good improvements!!! A few comments below. Thanx, Paul > --- > CodeSamples/defer/rcu_nest.c | 5 +++-- > CodeSamples/defer/rcu_nest.h | 25 +++++++++++++++++-------- > 2 files changed, 20 insertions(+), 10 deletions(-) > > diff --git a/CodeSamples/defer/rcu_nest.c b/CodeSamples/defer/rcu_nest.c > index 64e4087..362f466 100644 > --- a/CodeSamples/defer/rcu_nest.c > +++ b/CodeSamples/defer/rcu_nest.c > @@ -35,7 +35,7 @@ void synchronize_rcu(void) > > /* Advance to a new grace-period number, enforce ordering. */ > > - rcu_gp_ctr += RCU_GP_CTR_BOTTOM_BIT; > + WRITE_ONCE(rcu_gp_ctr, rcu_gp_ctr + RCU_GP_CTR_BOTTOM_BIT); > smp_mb(); > > /* > @@ -45,7 +45,8 @@ void synchronize_rcu(void) > > for_each_thread(t) { > while (rcu_gp_ongoing(t) && > - ((per_thread(rcu_reader_gp, t) - rcu_gp_ctr) < 0)) { > + ((READ_ONCE(per_thread(rcu_reader_gp, t)) - > + rcu_gp_ctr) < 0)) { > /*@@@ poll(NULL, 0, 10); */ > barrier(); > } > diff --git a/CodeSamples/defer/rcu_nest.h b/CodeSamples/defer/rcu_nest.h > index bcc4cde..65ce203 100644 > --- a/CodeSamples/defer/rcu_nest.h > +++ b/CodeSamples/defer/rcu_nest.h > @@ -24,8 +24,9 @@ DEFINE_SPINLOCK(rcu_gp_lock); > #define RCU_GP_CTR_SHIFT 7 > #define RCU_GP_CTR_BOTTOM_BIT (1 << RCU_GP_CTR_SHIFT) > #define RCU_GP_CTR_NEST_MASK (RCU_GP_CTR_BOTTOM_BIT - 1) > -long rcu_gp_ctr = 0; /* increment by RCU_GP_CTR_BOTTOM_BIT each gp. */ > -DEFINE_PER_THREAD(long, rcu_reader_gp); > +#define MAX_GP_ADV_DISTANCE (RCU_GP_CTR_NEST_MASK << 8) > +unsigned long rcu_gp_ctr = 0; /* increment by RCU_GP_CTR_BOTTOM_BIT each gp. */ > +DEFINE_PER_THREAD(unsigned long, rcu_reader_gp); > > static inline int rcu_gp_ongoing(int cpu) > { > @@ -39,8 +40,8 @@ static void rcu_init(void) > > static void rcu_read_lock(void) > { > - long tmp; > - long *rrgp; > + unsigned long tmp; > + unsigned long *rrgp; > > /* > * If this is the outermost RCU read-side critical section, > @@ -52,13 +53,21 @@ static void rcu_read_lock(void) > retry: > tmp = *rrgp; > if ((tmp & RCU_GP_CTR_NEST_MASK) == 0) > - tmp = rcu_gp_ctr; > + tmp = READ_ONCE(rcu_gp_ctr); > tmp++; > - *rrgp = tmp; > + WRITE_ONCE(*rrgp, tmp); > smp_mb(); > + > + /* > + * A reader could be suspended in between fetching the value of *rrgp > + * and writting the updated value back into *rrgp. During this s/writting/writing/ > + * time period, the grace-period counter might have advanced very far. > + * In this case, we force the reader to start over. > + */ > + > if (((tmp & RCU_GP_CTR_NEST_MASK) == 1) && > - ((rcu_gp_ctr - tmp) > (RCU_GP_CTR_NEST_MASK << 8)) != 0) { > - (*rrgp)--; > + (READ_ONCE(rcu_gp_ctr) > tmp + MAX_GP_ADV_DISTANCE)) { Does this work correctly if the value of tmp is just a bit less than ULONG_MAX? It looks to me like it does not. > + WRITE_ONCE(*rrgp, *rrgp - 1); > goto retry; > } > } > -- > 2.7.4 > ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] rcu_nest: fix concurrency issues 2019-05-02 14:59 ` Paul E. McKenney @ 2019-05-05 13:16 ` Junchang Wang 2019-05-06 18:14 ` Paul E. McKenney 0 siblings, 1 reply; 5+ messages in thread From: Junchang Wang @ 2019-05-05 13:16 UTC (permalink / raw) To: Paul E. McKenney; +Cc: akiyks, perfbook On Thu, May 02, 2019 at 07:59:51AM -0700, Paul E. McKenney wrote: >On Tue, Apr 30, 2019 at 12:02:39PM +0800, Junchang Wang wrote: >> Variable "rcu_gp_ctr" is incremented by the updater and is fetched by >> readers concurrently. So protect this variable by using READ_ONCE() >> and WRITE_ONCE(). >> >> Per-thread variable "rcu_read_gp" is updated by the reader and is read >> by the updater. So protect it by using READ_ONCE() and WRITE_ONCE(). >> >> The type of "rcu_gp_ctr" is changed to unsigned long because the behavior >> of the overflow of a signed long integer is not well defined in C yet. >> >> Refine the code snippet in "rcu_read_lock" that allows a reader to start >> over. In this version, we add micro MAX_GP_ADV_DISTANCE which is by >> default set to (RCU_GP_CTR_NEST_MASK << 8). Once a reader notices that >> MAX_GP_ADV_DISTANCE grace-periods have elapsed since fetching the value of >> "rcu_reader_gp", the reader starts over. >> >> >> Signed-off-by: Junchang Wang <junchangwang@gmail.com> > >First, thank you for doing this! Lots of good improvements!!! > >A few comments below. > > Thanx, Paul > >> --- >> CodeSamples/defer/rcu_nest.c | 5 +++-- >> CodeSamples/defer/rcu_nest.h | 25 +++++++++++++++++-------- >> 2 files changed, 20 insertions(+), 10 deletions(-) >> >> diff --git a/CodeSamples/defer/rcu_nest.c b/CodeSamples/defer/rcu_nest.c >> index 64e4087..362f466 100644 >> --- a/CodeSamples/defer/rcu_nest.c >> +++ b/CodeSamples/defer/rcu_nest.c >> @@ -35,7 +35,7 @@ void synchronize_rcu(void) >> >> /* Advance to a new grace-period number, enforce ordering. */ >> >> - rcu_gp_ctr += RCU_GP_CTR_BOTTOM_BIT; >> + WRITE_ONCE(rcu_gp_ctr, rcu_gp_ctr + RCU_GP_CTR_BOTTOM_BIT); >> smp_mb(); >> >> /* >> @@ -45,7 +45,8 @@ void synchronize_rcu(void) >> >> for_each_thread(t) { >> while (rcu_gp_ongoing(t) && >> - ((per_thread(rcu_reader_gp, t) - rcu_gp_ctr) < 0)) { >> + ((READ_ONCE(per_thread(rcu_reader_gp, t)) - >> + rcu_gp_ctr) < 0)) { >> /*@@@ poll(NULL, 0, 10); */ >> barrier(); >> } >> diff --git a/CodeSamples/defer/rcu_nest.h b/CodeSamples/defer/rcu_nest.h >> index bcc4cde..65ce203 100644 >> --- a/CodeSamples/defer/rcu_nest.h >> +++ b/CodeSamples/defer/rcu_nest.h >> @@ -24,8 +24,9 @@ DEFINE_SPINLOCK(rcu_gp_lock); >> #define RCU_GP_CTR_SHIFT 7 >> #define RCU_GP_CTR_BOTTOM_BIT (1 << RCU_GP_CTR_SHIFT) >> #define RCU_GP_CTR_NEST_MASK (RCU_GP_CTR_BOTTOM_BIT - 1) >> -long rcu_gp_ctr = 0; /* increment by RCU_GP_CTR_BOTTOM_BIT each gp. */ >> -DEFINE_PER_THREAD(long, rcu_reader_gp); >> +#define MAX_GP_ADV_DISTANCE (RCU_GP_CTR_NEST_MASK << 8) >> +unsigned long rcu_gp_ctr = 0; /* increment by RCU_GP_CTR_BOTTOM_BIT each gp. */ >> +DEFINE_PER_THREAD(unsigned long, rcu_reader_gp); >> >> static inline int rcu_gp_ongoing(int cpu) >> { >> @@ -39,8 +40,8 @@ static void rcu_init(void) >> >> static void rcu_read_lock(void) >> { >> - long tmp; >> - long *rrgp; >> + unsigned long tmp; >> + unsigned long *rrgp; >> >> /* >> * If this is the outermost RCU read-side critical section, >> @@ -52,13 +53,21 @@ static void rcu_read_lock(void) >> retry: >> tmp = *rrgp; >> if ((tmp & RCU_GP_CTR_NEST_MASK) == 0) >> - tmp = rcu_gp_ctr; >> + tmp = READ_ONCE(rcu_gp_ctr); >> tmp++; >> - *rrgp = tmp; >> + WRITE_ONCE(*rrgp, tmp); >> smp_mb(); >> + >> + /* >> + * A reader could be suspended in between fetching the value of *rrgp >> + * and writting the updated value back into *rrgp. During this > >s/writting/writing/ > >> + * time period, the grace-period counter might have advanced very far. >> + * In this case, we force the reader to start over. >> + */ >> + >> if (((tmp & RCU_GP_CTR_NEST_MASK) == 1) && >> - ((rcu_gp_ctr - tmp) > (RCU_GP_CTR_NEST_MASK << 8)) != 0) { >> - (*rrgp)--; >> + (READ_ONCE(rcu_gp_ctr) > tmp + MAX_GP_ADV_DISTANCE)) { > >Does this work correctly if the value of tmp is just a bit less than >ULONG_MAX? It looks to me like it does not. > Hi Paul, Thanks for reviewing the code. Yes, the statement you pointed out is buggy when both rcu_gp_ctr and tmp are close to ULONG_MAX. I was trying to rewrite to code to check for true overflow, but, as you have pointed out in a previous mail, that could make the code complex if we want to be exact. So I go back to the logic you used before. Please check the updated code below: + + /* + * A reader could be suspended in between fetching the value of *rrgp + * and writting the updated value back into *rrgp. During this + * time period, the grace-period counter might have advanced very far. + * In this case, we force the reader to start over. + */ + if (((tmp & RCU_GP_CTR_NEST_MASK) == 1) && - ((rcu_gp_ctr - tmp) > (RCU_GP_CTR_NEST_MASK << 8)) != 0) { - (*rrgp)--; + (READ_ONCE(rcu_gp_ctr) - (tmp-1)) > MAX_GP_ADV_DISTANCE) { + WRITE_ONCE(*rrgp, *rrgp - 1); goto retry; } } Note that if *rcu_gp_ctr* has not been changed since its value was first read and stored in *tmp*, then its value is less than *tmp* by 1. Since both *rcu_gp_ctr* and *tmp* are now unsigned long integers, (rcu_gp_ctr - tmp) will generate a very large integer number, so I replace that with (READ_ONCE(rcu_gp_ctr) - (tmp-1)). Please let me know if that looks OK. Thanks, --Junchang >> + WRITE_ONCE(*rrgp, *rrgp - 1); >> goto retry; >> } >> } >> -- >> 2.7.4 >> > ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] rcu_nest: fix concurrency issues 2019-05-05 13:16 ` Junchang Wang @ 2019-05-06 18:14 ` Paul E. McKenney 2019-05-08 13:46 ` Junchang Wang 0 siblings, 1 reply; 5+ messages in thread From: Paul E. McKenney @ 2019-05-06 18:14 UTC (permalink / raw) To: Junchang Wang; +Cc: akiyks, perfbook On Sun, May 05, 2019 at 09:16:53PM +0800, Junchang Wang wrote: > On Thu, May 02, 2019 at 07:59:51AM -0700, Paul E. McKenney wrote: > >On Tue, Apr 30, 2019 at 12:02:39PM +0800, Junchang Wang wrote: > >> Variable "rcu_gp_ctr" is incremented by the updater and is fetched by > >> readers concurrently. So protect this variable by using READ_ONCE() > >> and WRITE_ONCE(). > >> > >> Per-thread variable "rcu_read_gp" is updated by the reader and is read > >> by the updater. So protect it by using READ_ONCE() and WRITE_ONCE(). > >> > >> The type of "rcu_gp_ctr" is changed to unsigned long because the behavior > >> of the overflow of a signed long integer is not well defined in C yet. > >> > >> Refine the code snippet in "rcu_read_lock" that allows a reader to start > >> over. In this version, we add micro MAX_GP_ADV_DISTANCE which is by > >> default set to (RCU_GP_CTR_NEST_MASK << 8). Once a reader notices that > >> MAX_GP_ADV_DISTANCE grace-periods have elapsed since fetching the value of > >> "rcu_reader_gp", the reader starts over. > >> > >> > >> Signed-off-by: Junchang Wang <junchangwang@gmail.com> > > > >First, thank you for doing this! Lots of good improvements!!! > > > >A few comments below. > > > > Thanx, Paul > > > >> --- > >> CodeSamples/defer/rcu_nest.c | 5 +++-- > >> CodeSamples/defer/rcu_nest.h | 25 +++++++++++++++++-------- > >> 2 files changed, 20 insertions(+), 10 deletions(-) > >> > >> diff --git a/CodeSamples/defer/rcu_nest.c b/CodeSamples/defer/rcu_nest.c > >> index 64e4087..362f466 100644 > >> --- a/CodeSamples/defer/rcu_nest.c > >> +++ b/CodeSamples/defer/rcu_nest.c > >> @@ -35,7 +35,7 @@ void synchronize_rcu(void) > >> > >> /* Advance to a new grace-period number, enforce ordering. */ > >> > >> - rcu_gp_ctr += RCU_GP_CTR_BOTTOM_BIT; > >> + WRITE_ONCE(rcu_gp_ctr, rcu_gp_ctr + RCU_GP_CTR_BOTTOM_BIT); > >> smp_mb(); > >> > >> /* > >> @@ -45,7 +45,8 @@ void synchronize_rcu(void) > >> > >> for_each_thread(t) { > >> while (rcu_gp_ongoing(t) && > >> - ((per_thread(rcu_reader_gp, t) - rcu_gp_ctr) < 0)) { > >> + ((READ_ONCE(per_thread(rcu_reader_gp, t)) - > >> + rcu_gp_ctr) < 0)) { > >> /*@@@ poll(NULL, 0, 10); */ > >> barrier(); > >> } > >> diff --git a/CodeSamples/defer/rcu_nest.h b/CodeSamples/defer/rcu_nest.h > >> index bcc4cde..65ce203 100644 > >> --- a/CodeSamples/defer/rcu_nest.h > >> +++ b/CodeSamples/defer/rcu_nest.h > >> @@ -24,8 +24,9 @@ DEFINE_SPINLOCK(rcu_gp_lock); > >> #define RCU_GP_CTR_SHIFT 7 > >> #define RCU_GP_CTR_BOTTOM_BIT (1 << RCU_GP_CTR_SHIFT) > >> #define RCU_GP_CTR_NEST_MASK (RCU_GP_CTR_BOTTOM_BIT - 1) > >> -long rcu_gp_ctr = 0; /* increment by RCU_GP_CTR_BOTTOM_BIT each gp. */ > >> -DEFINE_PER_THREAD(long, rcu_reader_gp); > >> +#define MAX_GP_ADV_DISTANCE (RCU_GP_CTR_NEST_MASK << 8) > >> +unsigned long rcu_gp_ctr = 0; /* increment by RCU_GP_CTR_BOTTOM_BIT each gp. */ > >> +DEFINE_PER_THREAD(unsigned long, rcu_reader_gp); > >> > >> static inline int rcu_gp_ongoing(int cpu) > >> { > >> @@ -39,8 +40,8 @@ static void rcu_init(void) > >> > >> static void rcu_read_lock(void) > >> { > >> - long tmp; > >> - long *rrgp; > >> + unsigned long tmp; > >> + unsigned long *rrgp; > >> > >> /* > >> * If this is the outermost RCU read-side critical section, > >> @@ -52,13 +53,21 @@ static void rcu_read_lock(void) > >> retry: > >> tmp = *rrgp; > >> if ((tmp & RCU_GP_CTR_NEST_MASK) == 0) > >> - tmp = rcu_gp_ctr; > >> + tmp = READ_ONCE(rcu_gp_ctr); > >> tmp++; > >> - *rrgp = tmp; > >> + WRITE_ONCE(*rrgp, tmp); > >> smp_mb(); > >> + > >> + /* > >> + * A reader could be suspended in between fetching the value of *rrgp > >> + * and writting the updated value back into *rrgp. During this > > > >s/writting/writing/ > > > >> + * time period, the grace-period counter might have advanced very far. > >> + * In this case, we force the reader to start over. > >> + */ > >> + > >> if (((tmp & RCU_GP_CTR_NEST_MASK) == 1) && > >> - ((rcu_gp_ctr - tmp) > (RCU_GP_CTR_NEST_MASK << 8)) != 0) { > >> - (*rrgp)--; > >> + (READ_ONCE(rcu_gp_ctr) > tmp + MAX_GP_ADV_DISTANCE)) { > > > >Does this work correctly if the value of tmp is just a bit less than > >ULONG_MAX? It looks to me like it does not. > > > > Hi Paul, > > Thanks for reviewing the code. Yes, the statement you pointed out is buggy > when both rcu_gp_ctr and tmp are close to ULONG_MAX. I was trying to > rewrite to code to check for true overflow, but, as you have pointed out > in a previous mail, that could make the code complex if we want to be > exact. So I go back to the logic you used before. Please check the updated > code below: > > + > + /* > + * A reader could be suspended in between fetching the value of *rrgp > + * and writting the updated value back into *rrgp. During this > + * time period, the grace-period counter might have advanced very far. > + * In this case, we force the reader to start over. > + */ > + > if (((tmp & RCU_GP_CTR_NEST_MASK) == 1) && > - ((rcu_gp_ctr - tmp) > (RCU_GP_CTR_NEST_MASK << 8)) != 0) { > - (*rrgp)--; > + (READ_ONCE(rcu_gp_ctr) - (tmp-1)) > MAX_GP_ADV_DISTANCE) { > + WRITE_ONCE(*rrgp, *rrgp - 1); > goto retry; > } > } > > Note that if *rcu_gp_ctr* has not been changed since its value was first > read and stored in *tmp*, then its value is less than *tmp* by 1. > Since both *rcu_gp_ctr* and *tmp* are now unsigned long integers, > (rcu_gp_ctr - tmp) will generate a very large integer number, so I replace > that with (READ_ONCE(rcu_gp_ctr) - (tmp-1)). Please let me know if that looks OK. There are a couple of ways to make this work. One of them is as shown in time_after() in the Linux kernel, and another is as shown in ULONG_CMP_GE(). And yes, the C standard is less helpful than it might be in this area. You can thank old ones-complement machines and newer machines that trap on signed integer overflow. ;-) Thanx, Paul > Thanks, > --Junchang > > >> + WRITE_ONCE(*rrgp, *rrgp - 1); > >> goto retry; > >> } > >> } > >> -- > >> 2.7.4 > >> > > > ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] rcu_nest: fix concurrency issues 2019-05-06 18:14 ` Paul E. McKenney @ 2019-05-08 13:46 ` Junchang Wang 0 siblings, 0 replies; 5+ messages in thread From: Junchang Wang @ 2019-05-08 13:46 UTC (permalink / raw) To: Paul McKenney; +Cc: Akira Yokosawa, perfbook On Tue, May 7, 2019 at 2:14 AM Paul E. McKenney <paulmck@linux.ibm.com> wrote: > > On Sun, May 05, 2019 at 09:16:53PM +0800, Junchang Wang wrote: > > On Thu, May 02, 2019 at 07:59:51AM -0700, Paul E. McKenney wrote: > > >On Tue, Apr 30, 2019 at 12:02:39PM +0800, Junchang Wang wrote: > > >> Variable "rcu_gp_ctr" is incremented by the updater and is fetched by > > >> readers concurrently. So protect this variable by using READ_ONCE() > > >> and WRITE_ONCE(). > > >> > > >> Per-thread variable "rcu_read_gp" is updated by the reader and is read > > >> by the updater. So protect it by using READ_ONCE() and WRITE_ONCE(). > > >> > > >> The type of "rcu_gp_ctr" is changed to unsigned long because the behavior > > >> of the overflow of a signed long integer is not well defined in C yet. > > >> > > >> Refine the code snippet in "rcu_read_lock" that allows a reader to start > > >> over. In this version, we add micro MAX_GP_ADV_DISTANCE which is by > > >> default set to (RCU_GP_CTR_NEST_MASK << 8). Once a reader notices that > > >> MAX_GP_ADV_DISTANCE grace-periods have elapsed since fetching the value of > > >> "rcu_reader_gp", the reader starts over. > > >> > > >> > > >> Signed-off-by: Junchang Wang <junchangwang@gmail.com> > > > > > >First, thank you for doing this! Lots of good improvements!!! > > > > > >A few comments below. > > > > > > Thanx, Paul > > > > > >> --- > > >> CodeSamples/defer/rcu_nest.c | 5 +++-- > > >> CodeSamples/defer/rcu_nest.h | 25 +++++++++++++++++-------- > > >> 2 files changed, 20 insertions(+), 10 deletions(-) > > >> > > >> diff --git a/CodeSamples/defer/rcu_nest.c b/CodeSamples/defer/rcu_nest.c > > >> index 64e4087..362f466 100644 > > >> --- a/CodeSamples/defer/rcu_nest.c > > >> +++ b/CodeSamples/defer/rcu_nest.c > > >> @@ -35,7 +35,7 @@ void synchronize_rcu(void) > > >> > > >> /* Advance to a new grace-period number, enforce ordering. */ > > >> > > >> - rcu_gp_ctr += RCU_GP_CTR_BOTTOM_BIT; > > >> + WRITE_ONCE(rcu_gp_ctr, rcu_gp_ctr + RCU_GP_CTR_BOTTOM_BIT); > > >> smp_mb(); > > >> > > >> /* > > >> @@ -45,7 +45,8 @@ void synchronize_rcu(void) > > >> > > >> for_each_thread(t) { > > >> while (rcu_gp_ongoing(t) && > > >> - ((per_thread(rcu_reader_gp, t) - rcu_gp_ctr) < 0)) { > > >> + ((READ_ONCE(per_thread(rcu_reader_gp, t)) - > > >> + rcu_gp_ctr) < 0)) { > > >> /*@@@ poll(NULL, 0, 10); */ > > >> barrier(); > > >> } > > >> diff --git a/CodeSamples/defer/rcu_nest.h b/CodeSamples/defer/rcu_nest.h > > >> index bcc4cde..65ce203 100644 > > >> --- a/CodeSamples/defer/rcu_nest.h > > >> +++ b/CodeSamples/defer/rcu_nest.h > > >> @@ -24,8 +24,9 @@ DEFINE_SPINLOCK(rcu_gp_lock); > > >> #define RCU_GP_CTR_SHIFT 7 > > >> #define RCU_GP_CTR_BOTTOM_BIT (1 << RCU_GP_CTR_SHIFT) > > >> #define RCU_GP_CTR_NEST_MASK (RCU_GP_CTR_BOTTOM_BIT - 1) > > >> -long rcu_gp_ctr = 0; /* increment by RCU_GP_CTR_BOTTOM_BIT each gp. */ > > >> -DEFINE_PER_THREAD(long, rcu_reader_gp); > > >> +#define MAX_GP_ADV_DISTANCE (RCU_GP_CTR_NEST_MASK << 8) > > >> +unsigned long rcu_gp_ctr = 0; /* increment by RCU_GP_CTR_BOTTOM_BIT each gp. */ > > >> +DEFINE_PER_THREAD(unsigned long, rcu_reader_gp); > > >> > > >> static inline int rcu_gp_ongoing(int cpu) > > >> { > > >> @@ -39,8 +40,8 @@ static void rcu_init(void) > > >> > > >> static void rcu_read_lock(void) > > >> { > > >> - long tmp; > > >> - long *rrgp; > > >> + unsigned long tmp; > > >> + unsigned long *rrgp; > > >> > > >> /* > > >> * If this is the outermost RCU read-side critical section, > > >> @@ -52,13 +53,21 @@ static void rcu_read_lock(void) > > >> retry: > > >> tmp = *rrgp; > > >> if ((tmp & RCU_GP_CTR_NEST_MASK) == 0) > > >> - tmp = rcu_gp_ctr; > > >> + tmp = READ_ONCE(rcu_gp_ctr); > > >> tmp++; > > >> - *rrgp = tmp; > > >> + WRITE_ONCE(*rrgp, tmp); > > >> smp_mb(); > > >> + > > >> + /* > > >> + * A reader could be suspended in between fetching the value of *rrgp > > >> + * and writting the updated value back into *rrgp. During this > > > > > >s/writting/writing/ > > > > > >> + * time period, the grace-period counter might have advanced very far. > > >> + * In this case, we force the reader to start over. > > >> + */ > > >> + > > >> if (((tmp & RCU_GP_CTR_NEST_MASK) == 1) && > > >> - ((rcu_gp_ctr - tmp) > (RCU_GP_CTR_NEST_MASK << 8)) != 0) { > > >> - (*rrgp)--; > > >> + (READ_ONCE(rcu_gp_ctr) > tmp + MAX_GP_ADV_DISTANCE)) { > > > > > >Does this work correctly if the value of tmp is just a bit less than > > >ULONG_MAX? It looks to me like it does not. > > > > > > > Hi Paul, > > > > Thanks for reviewing the code. Yes, the statement you pointed out is buggy > > when both rcu_gp_ctr and tmp are close to ULONG_MAX. I was trying to > > rewrite to code to check for true overflow, but, as you have pointed out > > in a previous mail, that could make the code complex if we want to be > > exact. So I go back to the logic you used before. Please check the updated > > code below: > > > > + > > + /* > > + * A reader could be suspended in between fetching the value of *rrgp > > + * and writting the updated value back into *rrgp. During this > > + * time period, the grace-period counter might have advanced very far. > > + * In this case, we force the reader to start over. > > + */ > > + > > if (((tmp & RCU_GP_CTR_NEST_MASK) == 1) && > > - ((rcu_gp_ctr - tmp) > (RCU_GP_CTR_NEST_MASK << 8)) != 0) { > > - (*rrgp)--; > > + (READ_ONCE(rcu_gp_ctr) - (tmp-1)) > MAX_GP_ADV_DISTANCE) { > > + WRITE_ONCE(*rrgp, *rrgp - 1); > > goto retry; > > } > > } > > > > Note that if *rcu_gp_ctr* has not been changed since its value was first > > read and stored in *tmp*, then its value is less than *tmp* by 1. > > Since both *rcu_gp_ctr* and *tmp* are now unsigned long integers, > > (rcu_gp_ctr - tmp) will generate a very large integer number, so I replace > > that with (READ_ONCE(rcu_gp_ctr) - (tmp-1)). Please let me know if that looks OK. > > There are a couple of ways to make this work. One of them is as shown > in time_after() in the Linux kernel, and another is as shown in > ULONG_CMP_GE(). > Hi Paul, Thanks for referencing me to these functions, which look great. I will send a new patch soon. Thanks, --Junchang > And yes, the C standard is less helpful than it might be in this area. > You can thank old ones-complement machines and newer machines that > trap on signed integer overflow. ;-) > > Thanx, Paul > > > Thanks, > > --Junchang > > > > >> + WRITE_ONCE(*rrgp, *rrgp - 1); > > >> goto retry; > > >> } > > >> } > > >> -- > > >> 2.7.4 > > >> > > > > > ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2019-05-08 13:46 UTC | newest] Thread overview: 5+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2019-04-30 4:02 [PATCH] rcu_nest: fix concurrency issues Junchang Wang 2019-05-02 14:59 ` Paul E. McKenney 2019-05-05 13:16 ` Junchang Wang 2019-05-06 18:14 ` Paul E. McKenney 2019-05-08 13:46 ` Junchang Wang
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.