[lttng-dev] question about the RCU variant in CITRUS tree paper

[Paul E. McKenney]

On Fri, May 12, 2017 at 02:41:23PM -0400, Yuxin Ren wrote:
> Hi Paul,
> 
> Thank you for your reply.
> 
> If I understand your reply correctly, the update-side lock you
> mentioned is the lock used in the tree deletion algorithm.

Yes.

> But their urcu_synchronize contains no lock.
> So I think the lock is kind of problem caused by their usage of RCU,
> not from their urcu_synchronize implementation.

Yes again.  They are worried about things like two different reader
threads disagreeing about the order in which two different updater threads
added elements to a linked RCU-protected data structure.  In theory,
this sort of disagreement is a huge problem, but in practice almost no
one cares.

If you do care, one way to avoid the problem is to hold your update-side
lock (in this case, the one in their deletion algorithm) across the
grace period.  If you don't care, which is almost always the case in
practice, you release the lock first, and only then wait for the
grace period.

> I want to compare their RCU implementation with the U-RCU
> implementation, because the authors argued their implementation
> performs better than U-RCU.
> Is it possible to use their new RCU implementation as a drop-in
> replacement for U-RCU?

Probably, but you should trust actually trying it more than you trust
my answer to that question.  ;-)

							Thanx, Paul

> I am relative new to RCU, so my question could be stupid.
> Many thanks for your time
> Yuxin
> 
> On Thu, May 11, 2017 at 4:23 PM, Paul E. McKenney
> <paulmck at linux.vnet.ibm.com> wrote:
> > On Thu, May 11, 2017 at 04:05:45PM -0400, Yuxin Ren wrote:
> >> Hi,
> >>
> >> I am learning U-RCU now.
> >> And I read paper Concurrent Updates with RCU: Search Tree as an Example
> >> ( https://pdfs.semanticscholar.org/73e4/cd29273cf9d98d35bc184330e694ba798987.pdf
> >> )
> >>
> >> In this paper, the authors present a variant RCU implementation, and
> >> argued their new RCU has better performance than default U-RCU.
> >>
> >> Do you think their argument and implementation is correct in all cases?
> >> If they are right, will you wan to integrate their improment to U-RCU
> >> implementation?
> >>
> >> For your convenience, I paste the related text from the paper here.
> >> "In our implementation, each thread has a counter and flag, the
> >> counter counts the number of critical sections executed by the thread
> >> and a flag indicates if the thread is currently inside its read-side
> >> critical section. The rcu_read_lock operation increments the counter
> >> and sets the flag to true, while the rcu_read_unlock operation sets
> >> the flag to false. When a thread executes a synchronize_rcu operation,
> >> it waits for every other thread, until one of two things occurs:
> >> either the thread has increased its counter or the thread’s flag is
> >> set to false. "
> >>
> >> One its implementation can be found from synchrobench
> >> https://github.com/gramoli/synchrobench/blob/master/c-cpp/src/trees/tree-lock/new_urcu.c
> >
> > I covered this one here:  https://lwn.net/Articles/667593/
> >
> > The short version is that they are working around what I consider to
> > be a design bug in their algorithm, namely that they are holding the
> > update-side lock across RCU grace periods.  They do this to achieve
> > linearizability, which is prized by many conference referees/reviewers,
> > but not as useful in practice as is commonly supposed.
> >
> > But it does have a broken URL to the paper, so I will send your working
> > version to the LWN editors CCing you.  Thank you for that!
> >
> >                                                         Thanx, Paul
> >
>