Re: Question about list_sort() RCU version.

From: Chaitanya Kulkarni <Chaitanya.Kulkarni@wdc.com>
To: Steven Rostedt <rostedt@goodmis.org>
Cc: "paulmck@kernel.org" <paulmck@kernel.org>,
	Josh Triplett <josh@joshtriplett.org>,
	"rcu@vger.kernel.org" <rcu@vger.kernel.org>,
	"mathieu.desnoyers@efficios.com" <mathieu.desnoyers@efficios.com>,
	"jiangshanlai@gmail.com" <jiangshanlai@gmail.com>
Subject: Re: Question about list_sort() RCU version.
Date: Tue, 16 Jun 2020 22:26:14 +0000	[thread overview]
Message-ID: <BYAPR04MB4965A882732B601EE63AA8DA869D0@BYAPR04MB4965.namprd04.prod.outlook.com> (raw)
In-Reply-To: 20200616174756.53309ed0@oasis.local.home

On 6/16/20 2:48 PM, Steven Rostedt wrote:
> On Tue, 16 Jun 2020 20:17:56 +0000
> Chaitanya Kulkarni <Chaitanya.Kulkarni@wdc.com> wrote:
> 
>> Hi RCU maintainers and experts,
>>
>> I'm working on a linux kernel upstream project which is in the tree.
>> With the POC I can already see that significant performance improvement
>> with RCU in the fast path which are replacing rw semaphore, but not
>> having list_sort() rcu variant is blocking the developement and getting
>> code upstream.
>>
>> I was not able to find the such helper implemented for the RCU flavor of
>> list.
>>
>> Can someone provide information about :-
>>
>> 1. Is there any plan to have list_sort_rcu() ? if so when can we expect
>>      that ? (Also how can I help ?)
> 
> I'm pretty sure there isn't any plan.
> 
>>
>> 2. In case there is no plan what are design considerations if someone
>>      wants to implement the code and submit it upstream ?
>>      (Also how can I help here ?
>>
> 
> Good luck! For RCU to work, you basically need two states where both
> are "valid" for a time. You have an initial state, and then you have
> the state you want to get to. In the transition period, readers will
> see one of either those states, until the last reader is finished with
> the initial state, all new readers will only see the second state after
> a quiescent point in time.
> 
> To sort a list, you will need to modify it in such a case that the list
> is valid for all readers. This requires moving a list item. The problem
> is, this will require two modifications, where the list will not be
> valid in between. How would you move an item where the list is valid
> for ever change? Say you want to move the last element up. To do so,
> you need to remove the pointer to that element, make another element
> point to it, and in the mean time you need to update that last
> element's pointer as well. You can't do all that at once, and doing any
> of those without the other two will make the list invalid.
> 
> One answer is to make a copy of the entire list, sort it, and then make
> it the new list. That's the only way I can see this work.
> 
> -- Steve
> 

Thanks a lot for the reply and detailed explanation, it doesn't make
sense to go thorough all the development effort and make it generic for
one use case.