Re: Question about list_sort() RCU version.

["Paul E. McKenney" <paulmck@kernel.org>]

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