Re: [PATCH RFC 2/3] rcu: More rcu-variants for list manipulation

[Paul E. McKenney]

On Thu, Jul 21, 2011 at 03:20:22PM +0200, Jan H. Schönherr wrote:
> From: Jan H. Schönherr <schnhrr@xxxxxxxxxxxxxxx>
> 
> This commit introduces some more *_rcu variants of some list
> manipulation functions:
> 
> __list_link_rcu()
> __list_splice_rcu()
> list_splice_tail_init_rcu()
> 
> An important difference of the new rcu-splice functions
> compared to the existing function is that they require
> that there are either no concurrent readers on the list to
> be spliced or that these readers are still from the list
> where the list is spliced into.

Please see below for some comments on issues you are probably already
well aware of -- just commenting, the code itself looks OK.  Once this
patch is in good shape, it should probably go with the following patch
(which uses it) rather than up -rcu.

						Thanx, Paul

> Signed-off-by: Jan H. Schönherr <schnhrr@xxxxxxxxxxxxxxx>
> 
> ---
> TODO:
> - add comments
> - rephrase existing splice function using __list_splice_rcu()
>   and probably add "_sync" to the name
> ---
>  include/linux/rculist.h |   26 ++++++++++++++++++++++++++
>  1 files changed, 26 insertions(+), 0 deletions(-)
> 
> diff --git a/include/linux/rculist.h b/include/linux/rculist.h
> index 748401b..56385c8 100644
> --- a/include/linux/rculist.h
> +++ b/include/linux/rculist.h
> @@ -24,6 +24,15 @@
>   */
>  #define list_next_rcu(list)	(*((struct list_head __rcu **)(&(list)->next)))
> 

Badly need a header comment here!!!  This needs to include locking
constraints and RCU reader constraints.

Including why you have "prev" then "next" rather than the other
way around.  (Which I believe I figured out below.)

> +static inline void __list_link_rcu(struct list_head *prev,
> +					struct list_head *next)
> +{
> +	rcu_assign_pointer(list_next_rcu(prev), next);
> +	next->prev = prev;
> +}

OK, so this one links a single list element to another single list
element.  You therefore need two calls to this to splice a pair of list
together, right?  If so, there will be a time when you have a "6" shaped
list, so that readers from one of the list heads will never come back
to that list head.  This is probably what you are getting at with your
"require that there are either no concurrent readers on the list to be
spliced or that these readers are still from the list where the list is
spliced into".

However, this is quite subtle and needs to be spelled out carefully.

As I understand it, when you splice together a list A and a list B,
then list A cannot have any concurrent readers, but list B can.
And then you have to do the __list_link_rcu() operations (along maybe
with __list_link() operations) in a particular order.  These constraints
need to be carefully documented, and uses need to be commented.

> +
> +
>  /*
>   * Insert a new entry between two known consecutive entries.
>   *
> @@ -158,6 +167,23 @@ static inline void list_replace_rcu(struct list_head *old,
>  	old->prev = LIST_POISON2;
>  }

Really badly need a header comment here!!!  Which of these lists can
tolerate concurrent readers?  Why are there three arguments?  My guess
from the code is that "list" is the list being spliced, and it cannot
tolerate concurrent readers, while "prev" is one end of the place to
splice into the list and "next" is the other.  I believe that both "prev"
and "next" can tolerate concurrent readers.

Did I get it right?

Of course, if I got it wrong, that just proves how important the
documentation is!  ;-)

And I still don't understand why the argument order isn't list, next,
then prev -- after all, isn't that the order that the elements will
appear on the spliced list?  Ah, you are worried about the local order
at the splice point...  OK, then please include this in the comment.

Yeah, I know, the include/linux/list.h comments aren't all that detailed.
On the other hand, the include/linux/list.h primitives don't have to
worry about concurrent readers.  So please add detailed comments.  ;-)

> +static inline void __list_splice_rcu(struct list_head *list,
> +					struct list_head *prev,
> +					struct list_head *next)
> +{
> +	__list_link(list->prev, next);

At this point, RCU readers traversing the list containing "prev" and
"next" see no change, which is why it is OK to use __list_link() rather
than __list_link_rcu().  If there are readers traversing "list", they
will loop infinitely failing to find the old list header.

> +	__list_link_rcu(prev, list->next);

At this point, new RCU readers traversing the list containing
"next" and "prev" suddenly see the new elements from "list".  The
rcu_assign_pointer() in __lists_link_rcu() should force proper ordering.

OK, so looks reasonable.  Assuming that my guesses about what this is
supposed to do are correct, anyway.

> +}

And badly need a comment here, especially regarding which list is
being spliced into which.  The usual convention would be that
list is being spliced into head.

> +static inline void list_splice_tail_init_rcu(struct list_head *list,
> +						struct list_head *head)
> +{
> +	if (!list_empty(list)) {
> +		__list_splice_rcu(list, head->prev, head);
> +		INIT_LIST_HEAD(list);
> +	}
> +}

OK, so if "list" is non-empty, we splice its elements to precede
"head".

							Thanx, Paul

>  /**
>   * list_splice_init_rcu - splice an RCU-protected list into an existing list.
>   * @list:	the RCU-protected list to splice
> -- 
> 1.7.6
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@xxxxxxxxxxxxxxx
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/