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

[Yuxin Ren]

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.
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.

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?

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
>