Re: [PATCH tip/core/rcu 4/4] rcu: Document alternative RCU/reference-count algorithms

["Paul E. McKenney" <paulmck@linux.vnet.ibm.com>]

On Tue, Oct 30, 2012 at 12:21:03PM -0400, Mathieu Desnoyers wrote:
> * Paul E. McKenney (paulmck@linux.vnet.ibm.com) wrote:
> > From: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
> > 
> > The approach for mixing RCU and reference counting listed in the RCU
> > documentation only describes one possible approach.  This approach can
> > result in failure on the read side, which is nice if you want fresh data,
> > but not so good if you want simple code.  This commit therefore adds
> > two additional approaches that feature unconditional reference-count
> > acquisition by RCU readers.  These approaches are very similar to that
> > used in the security code.
> > 
> > Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > ---
> >  Documentation/RCU/rcuref.txt |   61 ++++++++++++++++++++++++++++++++++++++++-
> >  1 files changed, 59 insertions(+), 2 deletions(-)
> > 
> > diff --git a/Documentation/RCU/rcuref.txt b/Documentation/RCU/rcuref.txt
> > index 4202ad0..99ca662 100644
> > --- a/Documentation/RCU/rcuref.txt
> > +++ b/Documentation/RCU/rcuref.txt
> > @@ -20,7 +20,7 @@ release_referenced()			delete()
> >  {					{
> >      ...					    write_lock(&list_lock);
> >      atomic_dec(&el->rc, relfunc)	    ...
> > -    ...					    delete_element
> > +    ...					    remove_element
> >  }					    write_unlock(&list_lock);
> >   					    ...
> >  					    if (atomic_dec_and_test(&el->rc))
> > @@ -52,7 +52,7 @@ release_referenced()			delete()
> >  {					{
> >      ...					    spin_lock(&list_lock);
> >      if (atomic_dec_and_test(&el->rc))       ...
> > -        call_rcu(&el->head, el_free);       delete_element
> > +        call_rcu(&el->head, el_free);       remove_element
> >      ...                                     spin_unlock(&list_lock);
> >  } 					    ...
> >  					    if (atomic_dec_and_test(&el->rc))
> > @@ -64,3 +64,60 @@ Sometimes, a reference to the element needs to be obtained in the
> >  update (write) stream.  In such cases, atomic_inc_not_zero() might be
> >  overkill, since we hold the update-side spinlock.  One might instead
> >  use atomic_inc() in such cases.
> > +
> > +It is not always convenient to deal with "FAIL" in the
> > +search_and_reference() code path.  In such cases, the
> > +atomic_dec_and_test() may be moved from delete() to el_free()
> > +as follows:
> > +
> > +1.					2.
> > +add()					search_and_reference()
> > +{					{
> > +    alloc_object			    rcu_read_lock();
> > +    ...					    search_for_element
> > +    atomic_set(&el->rc, 1);		    atomic_inc(&el->rc);
> > +    spin_lock(&list_lock);		    ...
> > +				
> > +    add_element				    rcu_read_unlock();
> > +    ...					}
> 
> indentation looks wrong in my mail client for the two lines above (for
> the 2. block).

Ah, the "+" characters offset the tab stops.  Looks OK in the actual
file when the patch is applied.  (Though it would not hurt to check.)

							Thanx, Paul

> Otherwise, it looks good to me,
> 
> Thanks,
> 
> Mathieu
> 
> 
> > +    spin_unlock(&list_lock);		4.
> > +}					delete()
> > +3.					{
> > +release_referenced()			    spin_lock(&list_lock);
> > +{					    ...
> > +    ...					    remove_element
> > +    if (atomic_dec_and_test(&el->rc))       spin_unlock(&list_lock);
> > +        kfree(el);			    ...
> > +    ...                                     call_rcu(&el->head, el_free);
> > +} 					    ...
> > +5.					}
> > +void el_free(struct rcu_head *rhp)
> > +{
> > +    release_referenced();
> > +}
> > +
> > +The key point is that the initial reference added by add() is not removed
> > +until after a grace period has elapsed following removal.  This means that
> > +search_and_reference() cannot find this element, which means that the value
> > +of el->rc cannot increase.  Thus, once it reaches zero, there are no
> > +readers that can or ever will be able to reference the element.  The
> > +element can therefore safely be freed.  This in turn guarantees that if
> > +any reader finds the element, that reader may safely acquire a reference
> > +without checking the value of the reference counter.
> > +
> > +In cases where delete() can sleep, synchronize_rcu() can be called from
> > +delete(), so that el_free() can be subsumed into delete as follows:
> > +
> > +4.
> > +delete()
> > +{
> > +    spin_lock(&list_lock);
> > +    ...
> > +    remove_element
> > +    spin_unlock(&list_lock);
> > +    ...
> > +    synchronize_rcu();
> > +    if (atomic_dec_and_test(&el->rc))
> > +    	kfree(el);
> > +    ...
> > +}
> > -- 
> > 1.7.8
> > 
> 
> -- 
> Mathieu Desnoyers
> Operating System Efficiency R&D Consultant
> EfficiOS Inc.
> http://www.efficios.com
>