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.
next prev parent reply other threads:[~2020-06-16 22:26 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-06-16 20:17 Question about list_sort() RCU version Chaitanya Kulkarni
2020-06-16 20:24 ` Mathieu Desnoyers
2020-06-16 20:45 ` Chaitanya Kulkarni
2020-06-16 21:47 ` Steven Rostedt
2020-06-16 22:26 ` Chaitanya Kulkarni [this message]
2020-06-16 22:29 ` Paul E. McKenney
2020-06-16 23:21 ` Chaitanya Kulkarni
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=BYAPR04MB4965A882732B601EE63AA8DA869D0@BYAPR04MB4965.namprd04.prod.outlook.com \
--to=chaitanya.kulkarni@wdc.com \
--cc=jiangshanlai@gmail.com \
--cc=josh@joshtriplett.org \
--cc=mathieu.desnoyers@efficios.com \
--cc=paulmck@kernel.org \
--cc=rcu@vger.kernel.org \
--cc=rostedt@goodmis.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).