* [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.