* Question about list_sort() RCU version. @ 2020-06-16 20:17 Chaitanya Kulkarni 2020-06-16 20:24 ` Mathieu Desnoyers 2020-06-16 21:47 ` Steven Rostedt 0 siblings, 2 replies; 7+ messages in thread From: Chaitanya Kulkarni @ 2020-06-16 20:17 UTC (permalink / raw) To: paulmck, Josh Triplett; +Cc: rcu, rostedt, mathieu.desnoyers, jiangshanlai 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 ?) 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 ? Regards, -CK ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Question about list_sort() RCU version. 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 1 sibling, 1 reply; 7+ messages in thread From: Mathieu Desnoyers @ 2020-06-16 20:24 UTC (permalink / raw) To: Chaitanya Kulkarni; +Cc: paulmck, Josh Triplett, rcu, rostedt, Lai Jiangshan ----- On Jun 16, 2020, at 4:17 PM, 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. Why do you need list_sort() ? Is there any way you could simply insert your new elements into the list in already-sorted order ? This would ensure that the list is always in a sorted state, which I suspect will be expected by RCU readers. Thanks, Mathieu > > 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 ?) > > 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 ? -- Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Question about list_sort() RCU version. 2020-06-16 20:24 ` Mathieu Desnoyers @ 2020-06-16 20:45 ` Chaitanya Kulkarni 0 siblings, 0 replies; 7+ messages in thread From: Chaitanya Kulkarni @ 2020-06-16 20:45 UTC (permalink / raw) To: Mathieu Desnoyers; +Cc: paulmck, Josh Triplett, rcu, rostedt, Lai Jiangshan On 6/16/20 1:24 PM, Mathieu Desnoyers wrote: > ----- On Jun 16, 2020, at 4:17 PM, 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. > > Why do you need list_sort() ? Is there any way you could simply insert your > new elements into the list in already-sorted order ? This would ensure that > the list is always in a sorted state, which I suspect will be expected by > RCU readers. > > Thanks, > > Mathieu > It is not expected to be in the order by the readers in this case. For the list to be populated in sorted order it needs to be traversed every time in the fast-path which is costly based on the current design, so we add it to the tail and sort it later in the work-queue context when it is actually needed after we complete the scan. The sorting also takes care of the stale entries. (kind of entangled). Changing the design is always the last options, I'm trying to port the code without having to do that so future users also can user the RCU list_sort() version, unless having this absolutely not makes any sense. > >> >> 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 ?) >> >> 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 ? ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Question about list_sort() RCU version. 2020-06-16 20:17 Question about list_sort() RCU version Chaitanya Kulkarni 2020-06-16 20:24 ` Mathieu Desnoyers @ 2020-06-16 21:47 ` Steven Rostedt 2020-06-16 22:26 ` Chaitanya Kulkarni 2020-06-16 22:29 ` Paul E. McKenney 1 sibling, 2 replies; 7+ messages in thread From: Steven Rostedt @ 2020-06-16 21:47 UTC (permalink / raw) To: Chaitanya Kulkarni Cc: paulmck, Josh Triplett, rcu, mathieu.desnoyers, jiangshanlai 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 ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Question about list_sort() RCU version. 2020-06-16 21:47 ` Steven Rostedt @ 2020-06-16 22:26 ` Chaitanya Kulkarni 2020-06-16 22:29 ` Paul E. McKenney 1 sibling, 0 replies; 7+ messages in thread From: Chaitanya Kulkarni @ 2020-06-16 22:26 UTC (permalink / raw) To: Steven Rostedt Cc: paulmck, Josh Triplett, rcu, mathieu.desnoyers, jiangshanlai 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. ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Question about list_sort() RCU version. 2020-06-16 21:47 ` Steven Rostedt 2020-06-16 22:26 ` Chaitanya Kulkarni @ 2020-06-16 22:29 ` Paul E. McKenney 2020-06-16 23:21 ` Chaitanya Kulkarni 1 sibling, 1 reply; 7+ messages in thread From: Paul E. McKenney @ 2020-06-16 22:29 UTC (permalink / raw) To: Steven Rostedt Cc: Chaitanya Kulkarni, Josh Triplett, rcu, mathieu.desnoyers, jiangshanlai On Tue, Jun 16, 2020 at 05:47:56PM -0400, 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. If you want things sorted, why not a search tree? Or, depending on the purpose of the sorting, a hash table? It actually is kind-of sort-of possible to do an in-place sort of a linked list in the presence of readers, but the simpler ways of doing this are not at all pretty. Or efficient while the sort is in progress. o Find the largest element in the yet-to-be-sorted portion of the list. Pull that largest element to the front of the list as follows: o Set its ->next pointer to reference the first element of the list. (Yes, the list is now looped, and readers looking for later elements will follow that loop. Readers must do loop detection, and restart their traversal after momentarily exiting their read-side critical sections.) o Set the header pointer to reference the element being moved. The list is still looped. o Wait for a grace period. This is why looping readers must momentarily exit their read-side critical sections. o Make the moved item's predecessor point to the moved item's successor. o Repeat until the list is sorted. Another approach is similar to Steven's suggestion, but uses a separate set of pointers to do the sorting, then switches the readers to the sorted set. This allows better sorting algorithms to be used. But why not just insert each element into its proper place in the list to start with? If the list is too long for this to be efficient, you most likely should be using some other data structure. Thanx, Paul ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Question about list_sort() RCU version. 2020-06-16 22:29 ` Paul E. McKenney @ 2020-06-16 23:21 ` Chaitanya Kulkarni 0 siblings, 0 replies; 7+ messages in thread From: Chaitanya Kulkarni @ 2020-06-16 23:21 UTC (permalink / raw) To: paulmck, Steven Rostedt Cc: Josh Triplett, rcu, mathieu.desnoyers, jiangshanlai On 6/16/20 3:29 PM, Paul E. McKenney wrote: > If you want things sorted, why not a search tree? Or, depending on the > purpose of the sorting, a hash table? That was my first question but the way code is written right not which uses linked list and then it calls list_sort() which is not a ideal data structure to start with. > > It actually is kind-of sort-of possible to do an in-place sort of a > linked list in the presence of readers, but the simpler ways of doing > this are not at all pretty. Or efficient while the sort is in progress. > That is what I felt after reading a code and I'm not an expert in this area. > o Find the largest element in the yet-to-be-sorted portion of > the list. Pull that largest element to the front of the list > as follows: > > o Set its ->next pointer to reference the first > element of the list. (Yes, the list is now > looped, and readers looking for later elements > will follow that loop. Readers must do loop > detection, and restart their traversal after > momentarily exiting their read-side critical > sections.) > > o Set the header pointer to reference the element > being moved. The list is still looped. > > o Wait for a grace period. This is why looping > readers must momentarily exit their read-side > critical sections. > > o Make the moved item's predecessor point to the > moved item's successor. > > o Repeat until the list is sorted. > > Another approach is similar to Steven's suggestion, but uses a > separate set of pointers to do the sorting, then switches the > readers to the sorted set. This allows better sorting algorithms > to be used. > This is the most easy approach with high memory usage. > But why not just insert each element into its proper place in the list > to start with? If the list is too long for this to be efficient, you > most likely should be using some other data structure. > Agree, again not my design, and after these emails I do have questions on the data structure since with an efficient data structure set of the items are also be cached that will furthermore improve the performance given that size of the ids is cacheline friendly. > Thanx, Paul Thanks again everyone for replying promptly and in detailed manner. ^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2020-06-16 23:22 UTC | newest] Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 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 2020-06-16 22:29 ` Paul E. McKenney 2020-06-16 23:21 ` Chaitanya Kulkarni
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).