Re: [PATCH] Introduces generic __list_splice_init_rcu();

Re: [PATCH] Introduces generic __list_splice_init_rcu();

[Paul E. McKenney]

On Thu, Oct 08, 2015 at 04:02:19PM -0400, Mimi Zohar wrote:
> On Tue, 2015-10-06 at 11:37 -0700, Paul E. McKenney wrote:
> > On Sun, Sep 27, 2015 at 06:10:28PM +0300, Petko Manolov wrote:
> > > __list_splice_init_rcu() can be used to splice lists forming both stack and
> > > queue structures, depending on its arguments.  It is based on the initial
> > > list_splice_init_rcu() with a few minor modifications to help abstracting it.
> > > 
> > > Signed-off-by: Petko Manolov <petkan@mip-labs.com>
> > 
> > At first glance, this looks sane.
> > 
> > But who is using the new list_splice_tail_init_rcu() function?
> 
> Hi, Paul.  Up to now a single policy was loaded,  normally in the
> initramfs, and never changed.  Petko is adding support to extend the
> policy rules.  The additional policies would be appended to the existing
> list, only after verifying the new set of rules are good.
> 
> list.h contains list_splice() and list_splice_tail(), but the RCU
> equivalent functions don't exist.

OK, I have queued Petko's patch, updating the subject and changelog
as shown below.  I added you as Cc.  If testing goes well, I will
submit this for v4.5 (the merge window after next).

							Thanx, Paul

------------------------------------------------------------------------

commit a7916adc2cc47e918ee66b9225c00d585ccd3a91
Author: Petko Manolov <petkan@mip-labs.com>
Date:   Sun Sep 27 18:10:28 2015 +0300

    Introduce generic list_splice_tail_init_rcu()
    
    The list_splice_init_rcu() can be used as a stack onto which full lists
    are pushed, but queue-like behavior is now needed by some security
    policies.  This requires a list_splice_tail_init_rcu().
    
    This commit therefore supplies a list_splice_tail_init_rcu() by
    pulling code common it and to list_splice_init_rcu() into a new
    __list_splice_init_rcu() function.  This new function is based on the
    existing list_splice_init_rcu() implementation.
    
    Signed-off-by: Petko Manolov <petkan@mip-labs.com>
    Cc: Mimi Zohar <zohar@linux.vnet.ibm.com>
    Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>

diff --git a/include/linux/rculist.h b/include/linux/rculist.h
index 5ed540986019..bbde2837d6be 100644
--- a/include/linux/rculist.h
+++ b/include/linux/rculist.h
@@ -178,33 +178,13 @@ static inline void list_replace_rcu(struct list_head *old,
 	old->prev = LIST_POISON2;
 }
 
-/**
- * list_splice_init_rcu - splice an RCU-protected list into an existing list.
- * @list:	the RCU-protected list to splice
- * @head:	the place in the list to splice the first list into
- * @sync:	function to sync: synchronize_rcu(), synchronize_sched(), ...
- *
- * @head can be RCU-read traversed concurrently with this function.
- *
- * Note that this function blocks.
- *
- * Important note: the caller must take whatever action is necessary to
- *	prevent any other updates to @head.  In principle, it is possible
- *	to modify the list as soon as sync() begins execution.
- *	If this sort of thing becomes necessary, an alternative version
- *	based on call_rcu() could be created.  But only if -really-
- *	needed -- there is no shortage of RCU API members.
- */
-static inline void list_splice_init_rcu(struct list_head *list,
-					struct list_head *head,
-					void (*sync)(void))
+static inline void __list_splice_init_rcu(struct list_head *list,
+					  struct list_head *prev,
+					  struct list_head *next,
+					  void (*sync)(void))
 {
 	struct list_head *first = list->next;
 	struct list_head *last = list->prev;
-	struct list_head *at = head->next;
-
-	if (list_empty(list))
-		return;
 
 	/*
 	 * "first" and "last" tracking list, so initialize it.  RCU readers
@@ -231,10 +211,46 @@ static inline void list_splice_init_rcu(struct list_head *list,
 	 * this function.
 	 */
 
-	last->next = at;
-	rcu_assign_pointer(list_next_rcu(head), first);
-	first->prev = head;
-	at->prev = last;
+	last->next = next;
+	rcu_assign_pointer(list_next_rcu(prev), first);
+	first->prev = prev;
+	next->prev = last;
+}
+
+/**
+ * list_splice_init_rcu - splice an RCU-protected list into an existing list.
+ * @list:	the RCU-protected list to splice
+ * @head:	the place in the list to splice the first list into
+ * @sync:	function to sync: synchronize_rcu(), synchronize_sched(), ...
+ *
+ * @head can be RCU-read traversed concurrently with this function.
+ *
+ * Note that this function blocks.
+ *
+ * Important note: the caller must take whatever action is necessary to
+ *	prevent any other updates to @head.  In principle, it is possible
+ *	to modify the list as soon as sync() begins execution.
+ *	If this sort of thing becomes necessary, an alternative version
+ *	based on call_rcu() could be created.  But only if -really-
+ *	needed -- there is no shortage of RCU API members.
+ */
+static inline void list_splice_init_rcu(struct list_head *list,
+					struct list_head *head,
+					void (*sync)(void))
+{
+	if (!list_empty(list))
+		__list_splice_init_rcu(list, head, head->next, sync);
+}
+
+/**
+ * list_splice_tail_init_rcu - same as above, but creates a queue
+ */
+static inline void list_splice_tail_init_rcu(struct list_head *list,
+					     struct list_head *head,
+					     void (*sync)(void))
+{
+	if (!list_empty(list))
+		__list_splice_init_rcu(list, head->prev, head, sync);
 }
 
 /**

Re: [PATCH] Introduces generic __list_splice_init_rcu();

[Paul E. McKenney]

On Fri, Oct 09, 2015 at 11:26:38AM -0700, Paul E. McKenney wrote:
> On Thu, Oct 08, 2015 at 04:02:19PM -0400, Mimi Zohar wrote:
> > On Tue, 2015-10-06 at 11:37 -0700, Paul E. McKenney wrote:
> > > On Sun, Sep 27, 2015 at 06:10:28PM +0300, Petko Manolov wrote:
> > > > __list_splice_init_rcu() can be used to splice lists forming both stack and
> > > > queue structures, depending on its arguments.  It is based on the initial
> > > > list_splice_init_rcu() with a few minor modifications to help abstracting it.
> > > > 
> > > > Signed-off-by: Petko Manolov <petkan@mip-labs.com>
> > > 
> > > At first glance, this looks sane.
> > > 
> > > But who is using the new list_splice_tail_init_rcu() function?
> > 
> > Hi, Paul.  Up to now a single policy was loaded,  normally in the
> > initramfs, and never changed.  Petko is adding support to extend the
> > policy rules.  The additional policies would be appended to the existing
> > list, only after verifying the new set of rules are good.
> > 
> > list.h contains list_splice() and list_splice_tail(), but the RCU
> > equivalent functions don't exist.
> 
> OK, I have queued Petko's patch, updating the subject and changelog
> as shown below.  I added you as Cc.  If testing goes well, I will
> submit this for v4.5 (the merge window after next).

And reviewing the applied patch, this does need some help.  Please see
below, fix, and resubmit.

							Thanx, Paul

> ------------------------------------------------------------------------
> 
> commit a7916adc2cc47e918ee66b9225c00d585ccd3a91
> Author: Petko Manolov <petkan@mip-labs.com>
> Date:   Sun Sep 27 18:10:28 2015 +0300
> 
>     Introduce generic list_splice_tail_init_rcu()
>     
>     The list_splice_init_rcu() can be used as a stack onto which full lists
>     are pushed, but queue-like behavior is now needed by some security
>     policies.  This requires a list_splice_tail_init_rcu().
>     
>     This commit therefore supplies a list_splice_tail_init_rcu() by
>     pulling code common it and to list_splice_init_rcu() into a new
>     __list_splice_init_rcu() function.  This new function is based on the
>     existing list_splice_init_rcu() implementation.
>     
>     Signed-off-by: Petko Manolov <petkan@mip-labs.com>
>     Cc: Mimi Zohar <zohar@linux.vnet.ibm.com>
>     Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> 
> diff --git a/include/linux/rculist.h b/include/linux/rculist.h
> index 5ed540986019..bbde2837d6be 100644
> --- a/include/linux/rculist.h
> +++ b/include/linux/rculist.h
> @@ -178,33 +178,13 @@ static inline void list_replace_rcu(struct list_head *old,
>  	old->prev = LIST_POISON2;
>  }
>  
> -/**
> - * list_splice_init_rcu - splice an RCU-protected list into an existing list.
> - * @list:	the RCU-protected list to splice
> - * @head:	the place in the list to splice the first list into
> - * @sync:	function to sync: synchronize_rcu(), synchronize_sched(), ...
> - *
> - * @head can be RCU-read traversed concurrently with this function.
> - *
> - * Note that this function blocks.
> - *
> - * Important note: the caller must take whatever action is necessary to
> - *	prevent any other updates to @head.  In principle, it is possible
> - *	to modify the list as soon as sync() begins execution.
> - *	If this sort of thing becomes necessary, an alternative version
> - *	based on call_rcu() could be created.  But only if -really-
> - *	needed -- there is no shortage of RCU API members.
> - */
> -static inline void list_splice_init_rcu(struct list_head *list,
> -					struct list_head *head,
> -					void (*sync)(void))

We need a header comment saying what this does.  It should not be docbook,
but it does need to be there.

> +static inline void __list_splice_init_rcu(struct list_head *list,
> +					  struct list_head *prev,
> +					  struct list_head *next,
> +					  void (*sync)(void))
>  {
>  	struct list_head *first = list->next;
>  	struct list_head *last = list->prev;
> -	struct list_head *at = head->next;
> -
> -	if (list_empty(list))
> -		return;
>  
>  	/*
>  	 * "first" and "last" tracking list, so initialize it.  RCU readers
> @@ -231,10 +211,46 @@ static inline void list_splice_init_rcu(struct list_head *list,
>  	 * this function.
>  	 */
>  
> -	last->next = at;
> -	rcu_assign_pointer(list_next_rcu(head), first);
> -	first->prev = head;
> -	at->prev = last;
> +	last->next = next;
> +	rcu_assign_pointer(list_next_rcu(prev), first);
> +	first->prev = prev;
> +	next->prev = last;
> +}
> +
> +/**
> + * list_splice_init_rcu - splice an RCU-protected list into an existing list.
> + * @list:	the RCU-protected list to splice
> + * @head:	the place in the list to splice the first list into
> + * @sync:	function to sync: synchronize_rcu(), synchronize_sched(), ...
> + *
> + * @head can be RCU-read traversed concurrently with this function.
> + *
> + * Note that this function blocks.
> + *
> + * Important note: the caller must take whatever action is necessary to
> + *	prevent any other updates to @head.  In principle, it is possible
> + *	to modify the list as soon as sync() begins execution.
> + *	If this sort of thing becomes necessary, an alternative version
> + *	based on call_rcu() could be created.  But only if -really-
> + *	needed -- there is no shortage of RCU API members.
> + */
> +static inline void list_splice_init_rcu(struct list_head *list,
> +					struct list_head *head,
> +					void (*sync)(void))
> +{
> +	if (!list_empty(list))
> +		__list_splice_init_rcu(list, head, head->next, sync);
> +}
> +
> +/**
> + * list_splice_tail_init_rcu - same as above, but creates a queue
> + */

This is not sufficient.  We do need docbook, but we need filled-out
docbook.  The output of docbook is not guaranteed to always spit
out list_splice_init_rcu() and list_splice_tail_init_rcu() in that
order, after all.

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