On 6/16/20 2:48 PM, Steven Rostedt wrote: > On Tue, 16 Jun 2020 20:17:56 +0000 > Chaitanya Kulkarni <Chaitanya.Kulkarni@xxxxxxx> 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.
