Question about the detection of overflow in rcu_nest:rcu_read_lock()

Question about the detection of overflow in rcu_nest:rcu_read_lock()

[Junchang Wang]

Hi list,

I was reading rcu_nest.h and the code snippet (lines 59 - 63), which I believe
is to detect the overflow of variable rcu_gp_ctr, confused me a lot. Can some
of you shed light on that?

Specifically, what's the goal of line 60? Why should we compare the value of
(rcu_gp_ctr - tmp) against "111 1111 0000 0000"? If I understand correctly,
line 60 is to detect the scenario where rcu_gp_ctr has wrapped around and is
currently smaller than variable tmp. If that is correct, should line 60 be the
following?

60             ((tmp - READ_ONCE(rcu_gp_ctr)) > RCU_GP_CTR_BOTTOM_BIT) {

Or did I misunderstand anything here? 

 40 static void rcu_read_lock(void)
 41 {
 42         long tmp;
 43         long *rrgp;
 44 
 45         /*
 46          * If this is the outermost RCU read-side critical section,
 47          * copy the global grace-period counter.  In either case,
 48          * increment the nesting count held in the low-order bits.
 49          */
 50 
 51         rrgp = &__get_thread_var(rcu_reader_gp);
 52 retry:
 53         tmp = *rrgp;
 54         if ((tmp & RCU_GP_CTR_NEST_MASK) == 0)
 55                 tmp = READ_ONCE(rcu_gp_ctr);
 56         tmp++;
 57         *rrgp = tmp;
 58         smp_mb();
 59         if (((tmp & RCU_GP_CTR_NEST_MASK) == 1) &&
 60             ((rcu_gp_ctr - tmp) > (RCU_GP_CTR_NEST_MASK << 8)) != 0) {
 61                 (*rrgp)--;
 62                 goto retry;
 63         }
 64 }

Thanks,
--Junchang

Re: Question about the detection of overflow in rcu_nest:rcu_read_lock()

[Paul E. McKenney]

On Thu, Apr 25, 2019 at 05:25:28PM +0800, Junchang Wang wrote:
> Hi list,
> 
> I was reading rcu_nest.h and the code snippet (lines 59 - 63), which I believe
> is to detect the overflow of variable rcu_gp_ctr, confused me a lot. Can some
> of you shed light on that?

The "!= 0" and the end does look strange, no two ways about it!
Though this is a no-op, it should be fixed one way or another.

And I did write this some time ago, it appears...

> Specifically, what's the goal of line 60? Why should we compare the value of
> (rcu_gp_ctr - tmp) against "111 1111 0000 0000"? If I understand correctly,
> line 60 is to detect the scenario where rcu_gp_ctr has wrapped around and is
> currently smaller than variable tmp. If that is correct, should line 60 be the
> following?
> 
> 60             ((tmp - READ_ONCE(rcu_gp_ctr)) > RCU_GP_CTR_BOTTOM_BIT) {
> 
> Or did I misunderstand anything here? 

What is happening here is that between line 55, where rcu_gp_ctr is
loaded and line 57 where the store to *rrgp is done, the grace-period
mechanism is not aware that this reader exists.  If the grace-period
counter has advanced very far (nowhere near overflow), we want to start
over.  Yes, we could check for true overflow, but given that this should
be a rare event, there is little benefit (and some risk) to trying to
be exact.

This might be more clear with a macro set up specifically for this
purpose.  The value you have chosen would retry on any change in
rcu_gp_ctr, which is too strict.  It should be OK for it to get ahead
by 100 or so, hence the value I chose earlier.

The type of "rcu_gp_ctr" should be unsigned as well.  Signed overflow
is still undefined behavior in C.

The store into *rrgp should of course be WRITE_ONCE() because this value
is being read by other threads.

Probably other issues as well.

And thank you for looking at this!

							Thanx, Paul

>  40 static void rcu_read_lock(void)
>  41 {
>  42         long tmp;
>  43         long *rrgp;
>  44 
>  45         /*
>  46          * If this is the outermost RCU read-side critical section,
>  47          * copy the global grace-period counter.  In either case,
>  48          * increment the nesting count held in the low-order bits.
>  49          */
>  50 
>  51         rrgp = &__get_thread_var(rcu_reader_gp);
>  52 retry:
>  53         tmp = *rrgp;
>  54         if ((tmp & RCU_GP_CTR_NEST_MASK) == 0)
>  55                 tmp = READ_ONCE(rcu_gp_ctr);
>  56         tmp++;
>  57         *rrgp = tmp;
>  58         smp_mb();
>  59         if (((tmp & RCU_GP_CTR_NEST_MASK) == 1) &&
>  60             ((rcu_gp_ctr - tmp) > (RCU_GP_CTR_NEST_MASK << 8)) != 0) {
>  61                 (*rrgp)--;
>  62                 goto retry;
>  63         }
>  64 }
> 
> Thanks,
> --Junchang
>