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

[Paul E. McKenney]

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