Re: [PATCH RFC tip/core/rcu] rcu: direct algorithmic SRCU implementation

[Mathieu Desnoyers <compudj@krystal.dyndns.org>]

* Mathieu Desnoyers (mathieu.desnoyers@polymtl.ca) wrote:
> * Paul E. McKenney (paulmck@linux.vnet.ibm.com) wrote:
> [...]
> > +/*
> > + * To be called from the update side after an index flip.  Returns true
> > + * if the modulo sum of the counters is stably zero, false if there is
> > + * some possibility of non-zero.
> > + */
> > +static bool srcu_readers_active_idx_check(struct srcu_struct *sp, int idx)
> >  {
> >  	int cpu;
> > -	int sum;
> >  
> > -	sum = 0;
> > +	/*
> > +	 * Note that srcu_readers_active_idx() can incorrectly return
> > +	 * zero even though there is a pre-existing reader throughout.
> > +	 * To see this, suppose that task A is in a very long SRCU
> > +	 * read-side critical section that started on CPU 0, and that
> > +	 * no other reader exists, so that the modulo sum of the counters
> > +	 * is equal to one.  Then suppose that task B starts executing
> > +	 * srcu_readers_active_idx(), summing up to CPU 1, and then that
> > +	 * task C starts reading on CPU 0, so that its increment is not
> > +	 * summed, but finishes reading on CPU 2, so that its decrement
> > +	 * -is- summed.  Then when task B completes its sum, it will
> > +	 * incorrectly get zero, despite the fact that task A has been
> > +	 * in its SRCU read-side critical section the whole time.
> > +	 *
> > +	 * We therefore do a validation step should srcu_readers_active_idx()
> > +	 * return zero.
> > +	 */
> > +	if (srcu_readers_active_idx(sp, idx) != 0)
> > +		return false;
> > +
> > +	/*
> > +	 * Since the caller recently flipped ->completed, we can see at
> > +	 * most one increment of each CPU's counter from this point
> > +	 * forward.  The reason for this is that the reader CPU must have
> > +	 * fetched the index before srcu_readers_active_idx checked
> > +	 * that CPU's counter, but not yet incremented its counter.
> > +	 * Its eventual counter increment will follow the read in
> > +	 * srcu_readers_active_idx(), and that increment is immediately
> > +	 * followed by smp_mb() B.  Because smp_mb() D is between
> > +	 * the ->completed flip and srcu_readers_active_idx()'s read,
> > +	 * that CPU's subsequent load of ->completed must see the new
> > +	 * value, and therefore increment the counter in the other rank.
> > +	 */
> > +	smp_mb(); /* A */
> > +
> > +	/*
> > +	 * Now, we check the ->snap array that srcu_readers_active_idx()
> > +	 * filled in from the per-CPU counter values.  Since both
> > +	 * __srcu_read_lock() and __srcu_read_unlock() increment the
> > +	 * upper bits of the per-CPU counter, an increment/decrement
> > +	 * pair will change the value of the counter.  Since there is
> > +	 * only one possible increment, the only way to wrap the counter
> > +	 * is to have a huge number of counter decrements, which requires
> > +	 * a huge number of tasks and huge SRCU read-side critical-section
> > +	 * nesting levels, even on 32-bit systems.
> > +	 *
> > +	 * All of the ways of confusing the readings require that the scan
> > +	 * in srcu_readers_active_idx() see the read-side task's decrement,
> > +	 * but not its increment.  However, between that decrement and
> > +	 * increment are smb_mb() B and C.  Either or both of these pair
> > +	 * with smp_mb() A above to ensure that the scan below will see
> > +	 * the read-side tasks's increment, thus noting a difference in
> > +	 * the counter values between the two passes.
> 
> Hi Paul,
> 
> I think the implementation is correct, but the explanation above might
> be improved. Let's consider the following a scenario, where a reader is
> migrated between increment of the counter and issuing the memory barrier
> in the read lock:
> 
> A,B,C are readers
> D is synchronize_rcu (one flip'n'wait)
> 
> CPU A               CPU B           CPU C         CPU D
>                                     c[1]++
>                                     smp_mb(1)
>                                                   read c[0] -> 0
> c[0]++
> (implicit smp_mb (2))
>       -> migrated ->
>                     (implicit smp_mb (3))
>                     smp_mb (4)
>                     smp_mb (5)
>                     c[1]--
>                                                   read c[1] -> -1
>                                                   read c[2] -> 1
>                                                   (false 0 sum)
>                                                   smp_mb (6)
>                                                   re-check each.
>                                     c[1]--
> 
> re-check: because we observed c[1] == -1, thanks to the implicit memory
> barriers within thread migration (2 and 3), we can assume that we _will_
> observe the updated value of c[0] after smp_mb (6).
> 
> The current explanation states that memory barriers 4 and 5, along with  
> 6, are responsible for ensuring that the increment will be observed by 
> the re-check. However, I doubt they have anything to do with it: it's 
> rather the implicit memory barriers in thread migration, along with
> program order guarantees on writes to the same address, that seems to be
> the reason why we can do this ordering assumption.

Please disregard the part about program order: CPU A writes to c[0], and
CPU B writes to c[1], which are two different memory locations. The rest
of my discussion stands though.

Simply reasoning about write to c[0], memory barriers 2-3, write to
c[1], along with c[1] read, memory barrier 6, and then c[0] read is
enough to explain the ordering guarantees you need, without invoking
program order.

Thanks,

Mathieu

> 
> Does it make sense, or shall I get another coffee to wake myself up ?
> ;)
> 
> Thanks,
> 
> Mathieu
> 
> > +	 *
> > +	 * Therefore, if srcu_readers_active_idx() returned zero, and
> > +	 * none of the counters changed, we know that the zero was the
> > +	 * correct sum.
> > +	 *
> > +	 * Of course, it is possible that a task might be delayed
> > +	 * for a very long time in __srcu_read_lock() after fetching
> > +	 * the index but before incrementing its counter.  This
> > +	 * possibility will be dealt with in __synchronize_srcu().
> > +	 */
> >  	for_each_possible_cpu(cpu)
> > -		sum += per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx];
> > -	return sum;
> > +		if (sp->snap[cpu] !=
> > +		    ACCESS_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx]))
> > +			return false;  /* False zero reading! */
> > +	return true;
> >  }
> 
> 
> -- 
> Mathieu Desnoyers
> Operating System Efficiency R&D Consultant
> EfficiOS Inc.
> http://www.efficios.com

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com