Re: [PATCH RFCv2 2/8] rcu: More rcu-variants for list manipulation

["Jan Schönherr" <schnhrr@cs.tu-berlin.de>]

Am 27.07.2011 21:10, schrieb Jan H. Schönherr:
>  /**
> + * list_add_tail_nobackref - add element to list without setting up
> + *			     back references
> + * @new: element to add
> + * @head: list to add the element to
> + *
> + * @new is appended to @head.
> + *
> + * In contrast to list_add_tail(), this function does not maintain the
> + * references back to @head. So, neither @new->next will be changed, nor
> + * -- in case @new becomes the first entry of @head -- @new->pref.
> + *
> + * This is useful when reorganizing deleted elements of a RCU-protected
> + * list as concurrent readers must always find their way back to the list.
> + * When used in this context, special care must be taken in order to not
> + * disturb concurrent readers on @head (or @new):
> + * a) @new->next must lead back to the list
> + * b) @new->next must not lead to any node already on @head
> + * c) @new must be already known to existing readers on @head

This might actually race with physical deletion. Consider a list:

   HEAD --> A --> B --> C --> D --> HEAD

1. Remove C from list, then D:

   HEAD --> A --> B --------------> HEAD
                        C --> D ----^

2. Attempt to physically delete D by using call_rcu() or similar.
   This is delayed until all already running readers have finished.

3. Let a new reader begin to traverse the list, advancing until A.

4. Remove A.

   HEAD --------> B --------------> HEAD
            A ----^      C --> D ----^

5. Call list_add_tail_nobackref() for A, then C.

   HEAD --------> B --------------> HEAD
   LIST --> A ---------> C --> D ----^

6. Finish step 2, really deleting D.

7. Let the new reader continue its traversal.

This reader will hit D, which is obviously bad.


I think, we can avoid this by modifying the next pointers
of the deleted elements and letting them point to HEAD.
That is:

5a. Call list_add_tail_nobackref() for A.

   HEAD --------> B --------------> HEAD
                        C --> D ----^
   LIST --> A -----------------------^

5b. Call list_add_tail_nobackref() for C.

   HEAD --------> B --------------> HEAD
                              D ----^
   LIST --> A --------> C -----------^



However, this (and also the previous version) might
cause readers to skip elements that are on the list
(B in the example above). Can we tolerate that?

My current guess would be: no.

Thinking more about that, we already have that case:


   HEAD --> A --> B --> C --> HEAD

1. Let a reader traverse until A.

2. Remove A.

   HEAD --------> B --> C --> HEAD
            A ----^

3. Add A after B.

   HEAD --------> B     C --> HEAD
                  +> A -^

4. Let reader continue traversal, skipping B.

(Similarly, if we had removed C and re-added it between A and B,
we could have traversed B twice.)

So either the presented solution in this patch series
is valid, or -- when we are not allowed to re-add
elements which might still have readers -- the current
handling of CFS leaf runqueues has an additional problem
besides mixing up the order sometimes...

Paul? [Both of you, actually. :)]

Regards
Jan