Re: [RFC] adding into middle of RCU list

Re: [RFC] adding into middle of RCU list

[Mathieu Desnoyers]

Hi Stephen,

* Stephen Hemminger (stephen@networkplumber.org) wrote:
> I needed to add into the middle of an RCU list, does this make sense.
> 

Yes, it makes sense. I'm adding a couple of comments below,

> 
> 
> From a45892b0d49ac5fe449ba7e19c646cb17f7cee57 Mon Sep 17 00:00:00 2001
> From: Stephen Hemminger <stephen@networkplumber.org>
> Date: Thu, 22 Aug 2013 21:27:04 -0700
> Subject: [PATCH] Add list_splice_init_rcu to allow insertion into a RCU list
> 
> Simplified version of the version in kernel.
> ---
>  urcu/rculist.h |   32 ++++++++++++++++++++++++++++++++
>  1 file changed, 32 insertions(+)
> 
> diff --git a/urcu/rculist.h b/urcu/rculist.h
> index 1fd2df3..2e8a5a0 100644
> --- a/urcu/rculist.h
> +++ b/urcu/rculist.h
> @@ -72,6 +72,38 @@ void cds_list_del_rcu(struct cds_list_head *elem)
>  	CMM_STORE_SHARED(elem->prev->next, elem->next);
>  }
>  
> +
> +/**
> + * Splice an RCU-protected list into an existing list.
> + *
> + * Note that this function blocks in synchronize_rcu()
> + *
> + * Important note: this function is not called concurrently

is not -> should not be

> + *       with other updates to the list.

We might also want to start documenting the parameters in the list
headers, since it's unclear to someone who want to use the API which of
list and head is the list we want to splice, and which is the target,
e.g.:

 * @list: RCU-protected list to splice into @head.
 * @head: existing and initialized list to splice into.

We might want to state more clearly that @head can be any node within a
target list, including the list head.

> + */
> +static inline void caa_list_splice_init_rcu(struct cds_list_head *list,
> +					    struct cds_list_head *head)
> +{
> +	struct cds_list_head *first = list->next;
> +	struct cds_list_head *last = list->prev;
> +	struct cds_list_head *at = head->next;
> +
> +	if (cds_list_empty(list))
> +		return;
> +
> +	/* "first" and "last" tracking list, so initialize it. */
> +	CDS_INIT_LIST_HEAD(list);
> +
> +	/* Wait for any readers to finish using the list before splicing */
> +	synchronize_rcu();
> +
> +	/* Readers are finished with the source list, so perform splice. */
> +	last->next = at;
> +	rcu_assign_pointer(head->next, first);
> +	first->prev = head;
> +	at->prev = last;
> +}

Comment about style for LGPL headers: we really want to keep the
functions at 10 lines or less, otherwise they will need to be moved into
a library call or split into two static inline functions. So here, I
recommend moving the comments into the comment above the function, and
split the part starting at "last->next = at;" (4 lines) into a helper
function. Along with merging the 3 lines of local variables declaration
into 2, and removing empty white spaces and comments, we should be able
to fit this in 10 lines for caa_list_splice_init_rcu().

Thoughts ?

Thanks,

Mathieu



> +
>  /*
>   * Iteration through all elements of the list must be done while rcu_read_lock()
>   * is held.
> -- 
> 1.7.10.4
> 

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Re: [RFC] adding into middle of RCU list

[Paul E. McKenney]

On Thu, Aug 22, 2013 at 09:33:18PM -0700, Stephen Hemminger wrote:
> I needed to add into the middle of an RCU list, does this make sense.
> 
> 
> 
> From a45892b0d49ac5fe449ba7e19c646cb17f7cee57 Mon Sep 17 00:00:00 2001
> From: Stephen Hemminger <stephen@networkplumber.org>
> Date: Thu, 22 Aug 2013 21:27:04 -0700
> Subject: [PATCH] Add list_splice_init_rcu to allow insertion into a RCU list
> 
> Simplified version of the version in kernel.
> ---
>  urcu/rculist.h |   32 ++++++++++++++++++++++++++++++++
>  1 file changed, 32 insertions(+)
> 
> diff --git a/urcu/rculist.h b/urcu/rculist.h
> index 1fd2df3..2e8a5a0 100644
> --- a/urcu/rculist.h
> +++ b/urcu/rculist.h
> @@ -72,6 +72,38 @@ void cds_list_del_rcu(struct cds_list_head *elem)
>  	CMM_STORE_SHARED(elem->prev->next, elem->next);
>  }
>  
> +
> +/**
> + * Splice an RCU-protected list into an existing list.
> + *
> + * Note that this function blocks in synchronize_rcu()
> + *
> + * Important note: this function is not called concurrently
> + *       with other updates to the list.
> + */
> +static inline void caa_list_splice_init_rcu(struct cds_list_head *list,
> +					    struct cds_list_head *head)
> +{
> +	struct cds_list_head *first = list->next;
> +	struct cds_list_head *last = list->prev;
> +	struct cds_list_head *at = head->next;
> +
> +	if (cds_list_empty(list))
> +		return;
> +
> +	/* "first" and "last" tracking list, so initialize it. */
> +	CDS_INIT_LIST_HEAD(list);

This change is happening in the presence of readers on the list, right?
For this to work reliably in the presence of mischievous compilers,
wouldn't CDS_INIT_LIST_HEAD() need to use CMM_ACCESS_ONCE() for its
pointer accesses?

Hmmm...  The kernel version seems to have the same issue...
Patch below, FWIW.

							Thanx, Paul

> +
> +	/* Wait for any readers to finish using the list before splicing */
> +	synchronize_rcu();
> +
> +	/* Readers are finished with the source list, so perform splice. */
> +	last->next = at;
> +	rcu_assign_pointer(head->next, first);
> +	first->prev = head;
> +	at->prev = last;
> +}
> +
>  /*
>   * Iteration through all elements of the list must be done while rcu_read_lock()
>   * is held.
> -- 
> 1.7.10.4

rcu: Make list_splice_init_rcu() account for RCU readers

The list_splice_init_rcu() function allows a list visible to RCU readers
to be spliced into another list visible to RCU readers.  This is OK,
except for the use of INIT_LIST_HEAD(), which does pointer updates
without doing anything to make those updates safe for concurrent readers.

Of course, most of the time INIT_LIST_HEAD() is being used in reader-free
contexts, such as initialization or cleanup, so it is OK for it to update
pointers in an unsafe-for-RCU-readers manner.  This commit therefore
creates an INIT_LIST_HEAD_RCU() that uses ACCESS_ONCE() to make the updates
reader-safe.  The reason that we can use ACCESS_ONCE() instead of the more
typical rcu_assign_pointer() is that list_splice_init_rcu() is updating the
pointers to reference something that is already visible to readers, so
that there is no problem with pre-initialized values.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>

diff --git a/include/linux/rculist.h b/include/linux/rculist.h
index 4106721..45a0a9e 100644
--- a/include/linux/rculist.h
+++ b/include/linux/rculist.h
@@ -19,6 +19,21 @@
  */
 
 /*
+ * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers
+ * @list: list to be initialized
+ *
+ * You should instead use INIT_LIST_HEAD() for normal initialization and
+ * cleanup tasks, when readers have no access to the list being initialized.
+ * However, if the list being initialized is visible to readers, you
+ * need to keep the compiler from being too mischievous.
+ */
+static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
+{
+	ACCESS_ONCE(list->next) = list;
+	ACCESS_ONCE(list->prev) = list;
+}
+
+/*
  * return the ->next pointer of a list_head in an rcu safe
  * way, we must not access it directly
  */
@@ -191,9 +206,13 @@ static inline void list_splice_init_rcu(struct list_head *list,
 	if (list_empty(list))
 		return;
 
-	/* "first" and "last" tracking list, so initialize it. */
+	/*
+	 * "first" and "last" tracking list, so initialize it.  RCU readers
+	 * have access to this list, so we must use INIT_LIST_HEAD_RCU()
+	 * instead of INIT_LIST_HEAD().
+	 */
 
-	INIT_LIST_HEAD(list);
+	INIT_LIST_HEAD_RCU(list);
 
 	/*
 	 * At this point, the list body still points to the source list.

Re: [RFC] adding into middle of RCU list

[Mathieu Desnoyers]

* Paul E. McKenney (paulmck@linux.vnet.ibm.com) wrote:
> On Thu, Aug 22, 2013 at 09:33:18PM -0700, Stephen Hemminger wrote:
> > I needed to add into the middle of an RCU list, does this make sense.
> > 
> > 
> > 
> > From a45892b0d49ac5fe449ba7e19c646cb17f7cee57 Mon Sep 17 00:00:00 2001
> > From: Stephen Hemminger <stephen@networkplumber.org>
> > Date: Thu, 22 Aug 2013 21:27:04 -0700
> > Subject: [PATCH] Add list_splice_init_rcu to allow insertion into a RCU list
> > 
> > Simplified version of the version in kernel.
> > ---
> >  urcu/rculist.h |   32 ++++++++++++++++++++++++++++++++
> >  1 file changed, 32 insertions(+)
> > 
> > diff --git a/urcu/rculist.h b/urcu/rculist.h
> > index 1fd2df3..2e8a5a0 100644
> > --- a/urcu/rculist.h
> > +++ b/urcu/rculist.h
> > @@ -72,6 +72,38 @@ void cds_list_del_rcu(struct cds_list_head *elem)
> >  	CMM_STORE_SHARED(elem->prev->next, elem->next);
> >  }
> >  
> > +
> > +/**
> > + * Splice an RCU-protected list into an existing list.
> > + *
> > + * Note that this function blocks in synchronize_rcu()
> > + *
> > + * Important note: this function is not called concurrently
> > + *       with other updates to the list.
> > + */
> > +static inline void caa_list_splice_init_rcu(struct cds_list_head *list,
> > +					    struct cds_list_head *head)
> > +{
> > +	struct cds_list_head *first = list->next;
> > +	struct cds_list_head *last = list->prev;
> > +	struct cds_list_head *at = head->next;
> > +
> > +	if (cds_list_empty(list))
> > +		return;
> > +
> > +	/* "first" and "last" tracking list, so initialize it. */
> > +	CDS_INIT_LIST_HEAD(list);
> 
> This change is happening in the presence of readers on the list, right?
> For this to work reliably in the presence of mischievous compilers,
> wouldn't CDS_INIT_LIST_HEAD() need to use CMM_ACCESS_ONCE() for its
> pointer accesses?

Actually, we have rcu_assign_pointer()/rcu_set_pointer() exactly for
this. They even skip the memory barrier if they store a NULL pointer.

> 
> Hmmm...  The kernel version seems to have the same issue...

The compiler memory model of the Linux kernel AFAIK does not require an
ACCESS_ONCE() for stores to word-aligned, word-sized integers/pointers,
even if those are expected to be read concurrently. For reference, see:

#define __rcu_assign_pointer(p, v, space) \
        do { \
                smp_wmb(); \
                (p) = (typeof(*v) __force space *)(v); \
        } while (0)

In userspace RCU, we require to match CMM_LOAD_SHARED() with
CMM_STORE_SHARED() (which are used by
rcu_dereference()/rcu_{set,assign}_pointer) whenever we concurrently
access a variable shared between threads.

So I recommend using rcu_set_pointer() in userspace RCU, but I don't
think your patch is needed for Linux, given the Linux kernel compiler
memory model that is less strict than userspace RCU's model.

Thanks,

Mathieu


> Patch below, FWIW.
> 
> 							Thanx, Paul
> 
> > +
> > +	/* Wait for any readers to finish using the list before splicing */
> > +	synchronize_rcu();
> > +
> > +	/* Readers are finished with the source list, so perform splice. */
> > +	last->next = at;
> > +	rcu_assign_pointer(head->next, first);
> > +	first->prev = head;
> > +	at->prev = last;
> > +}
> > +
> >  /*
> >   * Iteration through all elements of the list must be done while rcu_read_lock()
> >   * is held.
> > -- 
> > 1.7.10.4
> 
> rcu: Make list_splice_init_rcu() account for RCU readers
> 
> The list_splice_init_rcu() function allows a list visible to RCU readers
> to be spliced into another list visible to RCU readers.  This is OK,
> except for the use of INIT_LIST_HEAD(), which does pointer updates
> without doing anything to make those updates safe for concurrent readers.
> 
> Of course, most of the time INIT_LIST_HEAD() is being used in reader-free
> contexts, such as initialization or cleanup, so it is OK for it to update
> pointers in an unsafe-for-RCU-readers manner.  This commit therefore
> creates an INIT_LIST_HEAD_RCU() that uses ACCESS_ONCE() to make the updates
> reader-safe.  The reason that we can use ACCESS_ONCE() instead of the more
> typical rcu_assign_pointer() is that list_splice_init_rcu() is updating the
> pointers to reference something that is already visible to readers, so
> that there is no problem with pre-initialized values.
> 
> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> 
> diff --git a/include/linux/rculist.h b/include/linux/rculist.h
> index 4106721..45a0a9e 100644
> --- a/include/linux/rculist.h
> +++ b/include/linux/rculist.h
> @@ -19,6 +19,21 @@
>   */
>  
>  /*
> + * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers
> + * @list: list to be initialized
> + *
> + * You should instead use INIT_LIST_HEAD() for normal initialization and
> + * cleanup tasks, when readers have no access to the list being initialized.
> + * However, if the list being initialized is visible to readers, you
> + * need to keep the compiler from being too mischievous.
> + */
> +static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
> +{
> +	ACCESS_ONCE(list->next) = list;
> +	ACCESS_ONCE(list->prev) = list;
> +}
> +
> +/*
>   * return the ->next pointer of a list_head in an rcu safe
>   * way, we must not access it directly
>   */
> @@ -191,9 +206,13 @@ static inline void list_splice_init_rcu(struct list_head *list,
>  	if (list_empty(list))
>  		return;
>  
> -	/* "first" and "last" tracking list, so initialize it. */
> +	/*
> +	 * "first" and "last" tracking list, so initialize it.  RCU readers
> +	 * have access to this list, so we must use INIT_LIST_HEAD_RCU()
> +	 * instead of INIT_LIST_HEAD().
> +	 */
>  
> -	INIT_LIST_HEAD(list);
> +	INIT_LIST_HEAD_RCU(list);
>  
>  	/*
>  	 * At this point, the list body still points to the source list.
> 

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Re: [RFC] adding into middle of RCU list

[Stephen Hemminger]

On Fri, 23 Aug 2013 13:16:53 -0400
Mathieu Desnoyers <mathieu.desnoyers@efficios.com> wrote:

> * Paul E. McKenney (paulmck@linux.vnet.ibm.com) wrote:
> > On Thu, Aug 22, 2013 at 09:33:18PM -0700, Stephen Hemminger wrote:
> > > I needed to add into the middle of an RCU list, does this make sense.
> > > 
> > > 
> > > 
> > > From a45892b0d49ac5fe449ba7e19c646cb17f7cee57 Mon Sep 17 00:00:00 2001
> > > From: Stephen Hemminger <stephen@networkplumber.org>
> > > Date: Thu, 22 Aug 2013 21:27:04 -0700
> > > Subject: [PATCH] Add list_splice_init_rcu to allow insertion into a RCU list
> > > 
> > > Simplified version of the version in kernel.
> > > ---
> > >  urcu/rculist.h |   32 ++++++++++++++++++++++++++++++++
> > >  1 file changed, 32 insertions(+)
> > > 
> > > diff --git a/urcu/rculist.h b/urcu/rculist.h
> > > index 1fd2df3..2e8a5a0 100644
> > > --- a/urcu/rculist.h
> > > +++ b/urcu/rculist.h
> > > @@ -72,6 +72,38 @@ void cds_list_del_rcu(struct cds_list_head *elem)
> > >  	CMM_STORE_SHARED(elem->prev->next, elem->next);
> > >  }
> > >  
> > > +
> > > +/**
> > > + * Splice an RCU-protected list into an existing list.
> > > + *
> > > + * Note that this function blocks in synchronize_rcu()
> > > + *
> > > + * Important note: this function is not called concurrently
> > > + *       with other updates to the list.
> > > + */
> > > +static inline void caa_list_splice_init_rcu(struct cds_list_head *list,
> > > +					    struct cds_list_head *head)
> > > +{
> > > +	struct cds_list_head *first = list->next;
> > > +	struct cds_list_head *last = list->prev;
> > > +	struct cds_list_head *at = head->next;
> > > +
> > > +	if (cds_list_empty(list))
> > > +		return;
> > > +
> > > +	/* "first" and "last" tracking list, so initialize it. */
> > > +	CDS_INIT_LIST_HEAD(list);
> > 
> > This change is happening in the presence of readers on the list, right?
> > For this to work reliably in the presence of mischievous compilers,
> > wouldn't CDS_INIT_LIST_HEAD() need to use CMM_ACCESS_ONCE() for its
> > pointer accesses?
> 
> Actually, we have rcu_assign_pointer()/rcu_set_pointer() exactly for
> this. They even skip the memory barrier if they store a NULL pointer.
> 
> > 
> > Hmmm...  The kernel version seems to have the same issue...
> 
> The compiler memory model of the Linux kernel AFAIK does not require an
> ACCESS_ONCE() for stores to word-aligned, word-sized integers/pointers,
> even if those are expected to be read concurrently. For reference, see:
> 
> #define __rcu_assign_pointer(p, v, space) \
>         do { \
>                 smp_wmb(); \
>                 (p) = (typeof(*v) __force space *)(v); \
>         } while (0)
> 
> In userspace RCU, we require to match CMM_LOAD_SHARED() with
> CMM_STORE_SHARED() (which are used by
> rcu_dereference()/rcu_{set,assign}_pointer) whenever we concurrently
> access a variable shared between threads.
> 
> So I recommend using rcu_set_pointer() in userspace RCU, but I don't
> think your patch is needed for Linux, given the Linux kernel compiler
> memory model that is less strict than userspace RCU's model.
> 
> Thanks,
> 
> Mathieu
> 
> 
> > Patch below, FWIW.
> > 
> > 							Thanx, Paul
> > 
> > > +
> > > +	/* Wait for any readers to finish using the list before splicing */
> > > +	synchronize_rcu();
> > > +
> > > +	/* Readers are finished with the source list, so perform splice. */
> > > +	last->next = at;
> > > +	rcu_assign_pointer(head->next, first);
> > > +	first->prev = head;
> > > +	at->prev = last;
> > > +}
> > > +
> > >  /*
> > >   * Iteration through all elements of the list must be done while rcu_read_lock()
> > >   * is held.
> > > -- 
> > > 1.7.10.4
> > 
> > rcu: Make list_splice_init_rcu() account for RCU readers
> > 
> > The list_splice_init_rcu() function allows a list visible to RCU readers
> > to be spliced into another list visible to RCU readers.  This is OK,
> > except for the use of INIT_LIST_HEAD(), which does pointer updates
> > without doing anything to make those updates safe for concurrent readers.
> > 
> > Of course, most of the time INIT_LIST_HEAD() is being used in reader-free
> > contexts, such as initialization or cleanup, so it is OK for it to update
> > pointers in an unsafe-for-RCU-readers manner.  This commit therefore
> > creates an INIT_LIST_HEAD_RCU() that uses ACCESS_ONCE() to make the updates
> > reader-safe.  The reason that we can use ACCESS_ONCE() instead of the more
> > typical rcu_assign_pointer() is that list_splice_init_rcu() is updating the
> > pointers to reference something that is already visible to readers, so
> > that there is no problem with pre-initialized values.
> > 
> > Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > 
> > diff --git a/include/linux/rculist.h b/include/linux/rculist.h
> > index 4106721..45a0a9e 100644
> > --- a/include/linux/rculist.h
> > +++ b/include/linux/rculist.h
> > @@ -19,6 +19,21 @@
> >   */
> >  
> >  /*
> > + * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers
> > + * @list: list to be initialized
> > + *
> > + * You should instead use INIT_LIST_HEAD() for normal initialization and
> > + * cleanup tasks, when readers have no access to the list being initialized.
> > + * However, if the list being initialized is visible to readers, you
> > + * need to keep the compiler from being too mischievous.
> > + */
> > +static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
> > +{
> > +	ACCESS_ONCE(list->next) = list;
> > +	ACCESS_ONCE(list->prev) = list;
> > +}
> > +
> > +/*
> >   * return the ->next pointer of a list_head in an rcu safe
> >   * way, we must not access it directly
> >   */
> > @@ -191,9 +206,13 @@ static inline void list_splice_init_rcu(struct list_head *list,
> >  	if (list_empty(list))
> >  		return;
> >  
> > -	/* "first" and "last" tracking list, so initialize it. */
> > +	/*
> > +	 * "first" and "last" tracking list, so initialize it.  RCU readers
> > +	 * have access to this list, so we must use INIT_LIST_HEAD_RCU()
> > +	 * instead of INIT_LIST_HEAD().
> > +	 */
> >  
> > -	INIT_LIST_HEAD(list);
> > +	INIT_LIST_HEAD_RCU(list);
> >  
> >  	/*
> >  	 * At this point, the list body still points to the source list.
> > 
> 

For what I need, it is probably simpler to do "insert in middle" rather
than a full splice, so I am checking how to do that.

Re: [RFC] adding into middle of RCU list

[Paul E. McKenney]

On Fri, Aug 23, 2013 at 12:09:56PM -0700, Stephen Hemminger wrote:
> On Fri, 23 Aug 2013 13:16:53 -0400
> Mathieu Desnoyers <mathieu.desnoyers@efficios.com> wrote:
> 
> > * Paul E. McKenney (paulmck@linux.vnet.ibm.com) wrote:
> > > On Thu, Aug 22, 2013 at 09:33:18PM -0700, Stephen Hemminger wrote:
> > > > I needed to add into the middle of an RCU list, does this make sense.
> > > > 
> > > > 
> > > > 
> > > > From a45892b0d49ac5fe449ba7e19c646cb17f7cee57 Mon Sep 17 00:00:00 2001
> > > > From: Stephen Hemminger <stephen@networkplumber.org>
> > > > Date: Thu, 22 Aug 2013 21:27:04 -0700
> > > > Subject: [PATCH] Add list_splice_init_rcu to allow insertion into a RCU list
> > > > 
> > > > Simplified version of the version in kernel.
> > > > ---
> > > >  urcu/rculist.h |   32 ++++++++++++++++++++++++++++++++
> > > >  1 file changed, 32 insertions(+)
> > > > 
> > > > diff --git a/urcu/rculist.h b/urcu/rculist.h
> > > > index 1fd2df3..2e8a5a0 100644
> > > > --- a/urcu/rculist.h
> > > > +++ b/urcu/rculist.h
> > > > @@ -72,6 +72,38 @@ void cds_list_del_rcu(struct cds_list_head *elem)
> > > >  	CMM_STORE_SHARED(elem->prev->next, elem->next);
> > > >  }
> > > >  
> > > > +
> > > > +/**
> > > > + * Splice an RCU-protected list into an existing list.
> > > > + *
> > > > + * Note that this function blocks in synchronize_rcu()
> > > > + *
> > > > + * Important note: this function is not called concurrently
> > > > + *       with other updates to the list.
> > > > + */
> > > > +static inline void caa_list_splice_init_rcu(struct cds_list_head *list,
> > > > +					    struct cds_list_head *head)
> > > > +{
> > > > +	struct cds_list_head *first = list->next;
> > > > +	struct cds_list_head *last = list->prev;
> > > > +	struct cds_list_head *at = head->next;
> > > > +
> > > > +	if (cds_list_empty(list))
> > > > +		return;
> > > > +
> > > > +	/* "first" and "last" tracking list, so initialize it. */
> > > > +	CDS_INIT_LIST_HEAD(list);
> > > 
> > > This change is happening in the presence of readers on the list, right?
> > > For this to work reliably in the presence of mischievous compilers,
> > > wouldn't CDS_INIT_LIST_HEAD() need to use CMM_ACCESS_ONCE() for its
> > > pointer accesses?
> > 
> > Actually, we have rcu_assign_pointer()/rcu_set_pointer() exactly for
> > this. They even skip the memory barrier if they store a NULL pointer.
> > 
> > > 
> > > Hmmm...  The kernel version seems to have the same issue...
> > 
> > The compiler memory model of the Linux kernel AFAIK does not require an
> > ACCESS_ONCE() for stores to word-aligned, word-sized integers/pointers,
> > even if those are expected to be read concurrently. For reference, see:
> > 
> > #define __rcu_assign_pointer(p, v, space) \
> >         do { \
> >                 smp_wmb(); \
> >                 (p) = (typeof(*v) __force space *)(v); \
> >         } while (0)
> > 
> > In userspace RCU, we require to match CMM_LOAD_SHARED() with
> > CMM_STORE_SHARED() (which are used by
> > rcu_dereference()/rcu_{set,assign}_pointer) whenever we concurrently
> > access a variable shared between threads.
> > 
> > So I recommend using rcu_set_pointer() in userspace RCU, but I don't
> > think your patch is needed for Linux, given the Linux kernel compiler
> > memory model that is less strict than userspace RCU's model.
> > 
> > Thanks,
> > 
> > Mathieu
> > 
> > 
> > > Patch below, FWIW.
> > > 
> > > 							Thanx, Paul
> > > 
> > > > +
> > > > +	/* Wait for any readers to finish using the list before splicing */
> > > > +	synchronize_rcu();
> > > > +
> > > > +	/* Readers are finished with the source list, so perform splice. */
> > > > +	last->next = at;
> > > > +	rcu_assign_pointer(head->next, first);
> > > > +	first->prev = head;
> > > > +	at->prev = last;
> > > > +}
> > > > +
> > > >  /*
> > > >   * Iteration through all elements of the list must be done while rcu_read_lock()
> > > >   * is held.
> > > > -- 
> > > > 1.7.10.4
> > > 
> > > rcu: Make list_splice_init_rcu() account for RCU readers
> > > 
> > > The list_splice_init_rcu() function allows a list visible to RCU readers
> > > to be spliced into another list visible to RCU readers.  This is OK,
> > > except for the use of INIT_LIST_HEAD(), which does pointer updates
> > > without doing anything to make those updates safe for concurrent readers.
> > > 
> > > Of course, most of the time INIT_LIST_HEAD() is being used in reader-free
> > > contexts, such as initialization or cleanup, so it is OK for it to update
> > > pointers in an unsafe-for-RCU-readers manner.  This commit therefore
> > > creates an INIT_LIST_HEAD_RCU() that uses ACCESS_ONCE() to make the updates
> > > reader-safe.  The reason that we can use ACCESS_ONCE() instead of the more
> > > typical rcu_assign_pointer() is that list_splice_init_rcu() is updating the
> > > pointers to reference something that is already visible to readers, so
> > > that there is no problem with pre-initialized values.
> > > 
> > > Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > > 
> > > diff --git a/include/linux/rculist.h b/include/linux/rculist.h
> > > index 4106721..45a0a9e 100644
> > > --- a/include/linux/rculist.h
> > > +++ b/include/linux/rculist.h
> > > @@ -19,6 +19,21 @@
> > >   */
> > >  
> > >  /*
> > > + * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers
> > > + * @list: list to be initialized
> > > + *
> > > + * You should instead use INIT_LIST_HEAD() for normal initialization and
> > > + * cleanup tasks, when readers have no access to the list being initialized.
> > > + * However, if the list being initialized is visible to readers, you
> > > + * need to keep the compiler from being too mischievous.
> > > + */
> > > +static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
> > > +{
> > > +	ACCESS_ONCE(list->next) = list;
> > > +	ACCESS_ONCE(list->prev) = list;
> > > +}
> > > +
> > > +/*
> > >   * return the ->next pointer of a list_head in an rcu safe
> > >   * way, we must not access it directly
> > >   */
> > > @@ -191,9 +206,13 @@ static inline void list_splice_init_rcu(struct list_head *list,
> > >  	if (list_empty(list))
> > >  		return;
> > >  
> > > -	/* "first" and "last" tracking list, so initialize it. */
> > > +	/*
> > > +	 * "first" and "last" tracking list, so initialize it.  RCU readers
> > > +	 * have access to this list, so we must use INIT_LIST_HEAD_RCU()
> > > +	 * instead of INIT_LIST_HEAD().
> > > +	 */
> > >  
> > > -	INIT_LIST_HEAD(list);
> > > +	INIT_LIST_HEAD_RCU(list);
> > >  
> > >  	/*
> > >  	 * At this point, the list body still points to the source list.
> > > 
> > 
> 
> For what I need, it is probably simpler to do "insert in middle" rather
> than a full splice, so I am checking how to do that.

If you are inserting a new element not accessible to readers in the
middle of the list, you should be able to use cds_list_add_rcu() treating
the predecessor cds_list_head as the list header.  Or am I missing
something here?

							Thanx, Paul

Re: [RFC] adding into middle of RCU list

[Stephen Hemminger]

On Fri, 23 Aug 2013 14:05:51 -0700
"Paul E. McKenney" <paulmck@linux.vnet.ibm.com> wrote:

> On Fri, Aug 23, 2013 at 12:09:56PM -0700, Stephen Hemminger wrote:
> > On Fri, 23 Aug 2013 13:16:53 -0400
> > Mathieu Desnoyers <mathieu.desnoyers@efficios.com> wrote:
> > 
> > > * Paul E. McKenney (paulmck@linux.vnet.ibm.com) wrote:
> > > > On Thu, Aug 22, 2013 at 09:33:18PM -0700, Stephen Hemminger wrote:
> > > > > I needed to add into the middle of an RCU list, does this make sense.
> > > > > 
> > > > > 
> > > > > 
> > > > > From a45892b0d49ac5fe449ba7e19c646cb17f7cee57 Mon Sep 17 00:00:00 2001
> > > > > From: Stephen Hemminger <stephen@networkplumber.org>
> > > > > Date: Thu, 22 Aug 2013 21:27:04 -0700
> > > > > Subject: [PATCH] Add list_splice_init_rcu to allow insertion into a RCU list
> > > > > 
> > > > > Simplified version of the version in kernel.
> > > > > ---
> > > > >  urcu/rculist.h |   32 ++++++++++++++++++++++++++++++++
> > > > >  1 file changed, 32 insertions(+)
> > > > > 
> > > > > diff --git a/urcu/rculist.h b/urcu/rculist.h
> > > > > index 1fd2df3..2e8a5a0 100644
> > > > > --- a/urcu/rculist.h
> > > > > +++ b/urcu/rculist.h
> > > > > @@ -72,6 +72,38 @@ void cds_list_del_rcu(struct cds_list_head *elem)
> > > > >  	CMM_STORE_SHARED(elem->prev->next, elem->next);
> > > > >  }
> > > > >  
> > > > > +
> > > > > +/**
> > > > > + * Splice an RCU-protected list into an existing list.
> > > > > + *
> > > > > + * Note that this function blocks in synchronize_rcu()
> > > > > + *
> > > > > + * Important note: this function is not called concurrently
> > > > > + *       with other updates to the list.
> > > > > + */
> > > > > +static inline void caa_list_splice_init_rcu(struct cds_list_head *list,
> > > > > +					    struct cds_list_head *head)
> > > > > +{
> > > > > +	struct cds_list_head *first = list->next;
> > > > > +	struct cds_list_head *last = list->prev;
> > > > > +	struct cds_list_head *at = head->next;
> > > > > +
> > > > > +	if (cds_list_empty(list))
> > > > > +		return;
> > > > > +
> > > > > +	/* "first" and "last" tracking list, so initialize it. */
> > > > > +	CDS_INIT_LIST_HEAD(list);
> > > > 
> > > > This change is happening in the presence of readers on the list, right?
> > > > For this to work reliably in the presence of mischievous compilers,
> > > > wouldn't CDS_INIT_LIST_HEAD() need to use CMM_ACCESS_ONCE() for its
> > > > pointer accesses?
> > > 
> > > Actually, we have rcu_assign_pointer()/rcu_set_pointer() exactly for
> > > this. They even skip the memory barrier if they store a NULL pointer.
> > > 
> > > > 
> > > > Hmmm...  The kernel version seems to have the same issue...
> > > 
> > > The compiler memory model of the Linux kernel AFAIK does not require an
> > > ACCESS_ONCE() for stores to word-aligned, word-sized integers/pointers,
> > > even if those are expected to be read concurrently. For reference, see:
> > > 
> > > #define __rcu_assign_pointer(p, v, space) \
> > >         do { \
> > >                 smp_wmb(); \
> > >                 (p) = (typeof(*v) __force space *)(v); \
> > >         } while (0)
> > > 
> > > In userspace RCU, we require to match CMM_LOAD_SHARED() with
> > > CMM_STORE_SHARED() (which are used by
> > > rcu_dereference()/rcu_{set,assign}_pointer) whenever we concurrently
> > > access a variable shared between threads.
> > > 
> > > So I recommend using rcu_set_pointer() in userspace RCU, but I don't
> > > think your patch is needed for Linux, given the Linux kernel compiler
> > > memory model that is less strict than userspace RCU's model.
> > > 
> > > Thanks,
> > > 
> > > Mathieu
> > > 
> > > 
> > > > Patch below, FWIW.
> > > > 
> > > > 							Thanx, Paul
> > > > 
> > > > > +
> > > > > +	/* Wait for any readers to finish using the list before splicing */
> > > > > +	synchronize_rcu();
> > > > > +
> > > > > +	/* Readers are finished with the source list, so perform splice. */
> > > > > +	last->next = at;
> > > > > +	rcu_assign_pointer(head->next, first);
> > > > > +	first->prev = head;
> > > > > +	at->prev = last;
> > > > > +}
> > > > > +
> > > > >  /*
> > > > >   * Iteration through all elements of the list must be done while rcu_read_lock()
> > > > >   * is held.
> > > > > -- 
> > > > > 1.7.10.4
> > > > 
> > > > rcu: Make list_splice_init_rcu() account for RCU readers
> > > > 
> > > > The list_splice_init_rcu() function allows a list visible to RCU readers
> > > > to be spliced into another list visible to RCU readers.  This is OK,
> > > > except for the use of INIT_LIST_HEAD(), which does pointer updates
> > > > without doing anything to make those updates safe for concurrent readers.
> > > > 
> > > > Of course, most of the time INIT_LIST_HEAD() is being used in reader-free
> > > > contexts, such as initialization or cleanup, so it is OK for it to update
> > > > pointers in an unsafe-for-RCU-readers manner.  This commit therefore
> > > > creates an INIT_LIST_HEAD_RCU() that uses ACCESS_ONCE() to make the updates
> > > > reader-safe.  The reason that we can use ACCESS_ONCE() instead of the more
> > > > typical rcu_assign_pointer() is that list_splice_init_rcu() is updating the
> > > > pointers to reference something that is already visible to readers, so
> > > > that there is no problem with pre-initialized values.
> > > > 
> > > > Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > > > 
> > > > diff --git a/include/linux/rculist.h b/include/linux/rculist.h
> > > > index 4106721..45a0a9e 100644
> > > > --- a/include/linux/rculist.h
> > > > +++ b/include/linux/rculist.h
> > > > @@ -19,6 +19,21 @@
> > > >   */
> > > >  
> > > >  /*
> > > > + * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers
> > > > + * @list: list to be initialized
> > > > + *
> > > > + * You should instead use INIT_LIST_HEAD() for normal initialization and
> > > > + * cleanup tasks, when readers have no access to the list being initialized.
> > > > + * However, if the list being initialized is visible to readers, you
> > > > + * need to keep the compiler from being too mischievous.
> > > > + */
> > > > +static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
> > > > +{
> > > > +	ACCESS_ONCE(list->next) = list;
> > > > +	ACCESS_ONCE(list->prev) = list;
> > > > +}
> > > > +
> > > > +/*
> > > >   * return the ->next pointer of a list_head in an rcu safe
> > > >   * way, we must not access it directly
> > > >   */
> > > > @@ -191,9 +206,13 @@ static inline void list_splice_init_rcu(struct list_head *list,
> > > >  	if (list_empty(list))
> > > >  		return;
> > > >  
> > > > -	/* "first" and "last" tracking list, so initialize it. */
> > > > +	/*
> > > > +	 * "first" and "last" tracking list, so initialize it.  RCU readers
> > > > +	 * have access to this list, so we must use INIT_LIST_HEAD_RCU()
> > > > +	 * instead of INIT_LIST_HEAD().
> > > > +	 */
> > > >  
> > > > -	INIT_LIST_HEAD(list);
> > > > +	INIT_LIST_HEAD_RCU(list);
> > > >  
> > > >  	/*
> > > >  	 * At this point, the list body still points to the source list.
> > > > 
> > > 
> > 
> > For what I need, it is probably simpler to do "insert in middle" rather
> > than a full splice, so I am checking how to do that.
> 
> If you are inserting a new element not accessible to readers in the
> middle of the list, you should be able to use cds_list_add_rcu() treating
> the predecessor cds_list_head as the list header.  Or am I missing
> something here?

Yeah, that is what I was thinking, as long as the ordering is correct.

Re: [RFC] adding into middle of RCU list

[Paul E. McKenney]

On Fri, Aug 23, 2013 at 01:16:53PM -0400, Mathieu Desnoyers wrote:
> * Paul E. McKenney (paulmck@linux.vnet.ibm.com) wrote:
> > On Thu, Aug 22, 2013 at 09:33:18PM -0700, Stephen Hemminger wrote:
> > > I needed to add into the middle of an RCU list, does this make sense.
> > > 
> > > 
> > > 
> > > From a45892b0d49ac5fe449ba7e19c646cb17f7cee57 Mon Sep 17 00:00:00 2001
> > > From: Stephen Hemminger <stephen@networkplumber.org>
> > > Date: Thu, 22 Aug 2013 21:27:04 -0700
> > > Subject: [PATCH] Add list_splice_init_rcu to allow insertion into a RCU list
> > > 
> > > Simplified version of the version in kernel.
> > > ---
> > >  urcu/rculist.h |   32 ++++++++++++++++++++++++++++++++
> > >  1 file changed, 32 insertions(+)
> > > 
> > > diff --git a/urcu/rculist.h b/urcu/rculist.h
> > > index 1fd2df3..2e8a5a0 100644
> > > --- a/urcu/rculist.h
> > > +++ b/urcu/rculist.h
> > > @@ -72,6 +72,38 @@ void cds_list_del_rcu(struct cds_list_head *elem)
> > >  	CMM_STORE_SHARED(elem->prev->next, elem->next);
> > >  }
> > >  
> > > +
> > > +/**
> > > + * Splice an RCU-protected list into an existing list.
> > > + *
> > > + * Note that this function blocks in synchronize_rcu()
> > > + *
> > > + * Important note: this function is not called concurrently
> > > + *       with other updates to the list.
> > > + */
> > > +static inline void caa_list_splice_init_rcu(struct cds_list_head *list,
> > > +					    struct cds_list_head *head)
> > > +{
> > > +	struct cds_list_head *first = list->next;
> > > +	struct cds_list_head *last = list->prev;
> > > +	struct cds_list_head *at = head->next;
> > > +
> > > +	if (cds_list_empty(list))
> > > +		return;
> > > +
> > > +	/* "first" and "last" tracking list, so initialize it. */
> > > +	CDS_INIT_LIST_HEAD(list);
> > 
> > This change is happening in the presence of readers on the list, right?
> > For this to work reliably in the presence of mischievous compilers,
> > wouldn't CDS_INIT_LIST_HEAD() need to use CMM_ACCESS_ONCE() for its
> > pointer accesses?
> 
> Actually, we have rcu_assign_pointer()/rcu_set_pointer() exactly for
> this. They even skip the memory barrier if they store a NULL pointer.
> 
> > 
> > Hmmm...  The kernel version seems to have the same issue...
> 
> The compiler memory model of the Linux kernel AFAIK does not require an
> ACCESS_ONCE() for stores to word-aligned, word-sized integers/pointers,
> even if those are expected to be read concurrently. For reference, see:
> 
> #define __rcu_assign_pointer(p, v, space) \
>         do { \
>                 smp_wmb(); \
>                 (p) = (typeof(*v) __force space *)(v); \
>         } while (0)

Or I need to fix this one as well.  ;-)

> In userspace RCU, we require to match CMM_LOAD_SHARED() with
> CMM_STORE_SHARED() (which are used by
> rcu_dereference()/rcu_{set,assign}_pointer) whenever we concurrently
> access a variable shared between threads.
> 
> So I recommend using rcu_set_pointer() in userspace RCU, but I don't
> think your patch is needed for Linux, given the Linux kernel compiler
> memory model that is less strict than userspace RCU's model.

Me, I trust compilers a lot less than I did some years back.  ;-)

							Thanx, Paul

> Thanks,
> 
> Mathieu
> 
> 
> > Patch below, FWIW.
> > 
> > 							Thanx, Paul
> > 
> > > +
> > > +	/* Wait for any readers to finish using the list before splicing */
> > > +	synchronize_rcu();
> > > +
> > > +	/* Readers are finished with the source list, so perform splice. */
> > > +	last->next = at;
> > > +	rcu_assign_pointer(head->next, first);
> > > +	first->prev = head;
> > > +	at->prev = last;
> > > +}
> > > +
> > >  /*
> > >   * Iteration through all elements of the list must be done while rcu_read_lock()
> > >   * is held.
> > > -- 
> > > 1.7.10.4
> > 
> > rcu: Make list_splice_init_rcu() account for RCU readers
> > 
> > The list_splice_init_rcu() function allows a list visible to RCU readers
> > to be spliced into another list visible to RCU readers.  This is OK,
> > except for the use of INIT_LIST_HEAD(), which does pointer updates
> > without doing anything to make those updates safe for concurrent readers.
> > 
> > Of course, most of the time INIT_LIST_HEAD() is being used in reader-free
> > contexts, such as initialization or cleanup, so it is OK for it to update
> > pointers in an unsafe-for-RCU-readers manner.  This commit therefore
> > creates an INIT_LIST_HEAD_RCU() that uses ACCESS_ONCE() to make the updates
> > reader-safe.  The reason that we can use ACCESS_ONCE() instead of the more
> > typical rcu_assign_pointer() is that list_splice_init_rcu() is updating the
> > pointers to reference something that is already visible to readers, so
> > that there is no problem with pre-initialized values.
> > 
> > Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > 
> > diff --git a/include/linux/rculist.h b/include/linux/rculist.h
> > index 4106721..45a0a9e 100644
> > --- a/include/linux/rculist.h
> > +++ b/include/linux/rculist.h
> > @@ -19,6 +19,21 @@
> >   */
> >  
> >  /*
> > + * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers
> > + * @list: list to be initialized
> > + *
> > + * You should instead use INIT_LIST_HEAD() for normal initialization and
> > + * cleanup tasks, when readers have no access to the list being initialized.
> > + * However, if the list being initialized is visible to readers, you
> > + * need to keep the compiler from being too mischievous.
> > + */
> > +static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
> > +{
> > +	ACCESS_ONCE(list->next) = list;
> > +	ACCESS_ONCE(list->prev) = list;
> > +}
> > +
> > +/*
> >   * return the ->next pointer of a list_head in an rcu safe
> >   * way, we must not access it directly
> >   */
> > @@ -191,9 +206,13 @@ static inline void list_splice_init_rcu(struct list_head *list,
> >  	if (list_empty(list))
> >  		return;
> >  
> > -	/* "first" and "last" tracking list, so initialize it. */
> > +	/*
> > +	 * "first" and "last" tracking list, so initialize it.  RCU readers
> > +	 * have access to this list, so we must use INIT_LIST_HEAD_RCU()
> > +	 * instead of INIT_LIST_HEAD().
> > +	 */
> >  
> > -	INIT_LIST_HEAD(list);
> > +	INIT_LIST_HEAD_RCU(list);
> >  
> >  	/*
> >  	 * At this point, the list body still points to the source list.
> > 
> 
> -- 
> Mathieu Desnoyers
> EfficiOS Inc.
> http://www.efficios.com
> 

Re: [RFC] adding into middle of RCU list

[Paul E. McKenney]

On Fri, Aug 23, 2013 at 02:08:22PM -0700, Paul E. McKenney wrote:
> On Fri, Aug 23, 2013 at 01:16:53PM -0400, Mathieu Desnoyers wrote:
> > * Paul E. McKenney (paulmck@linux.vnet.ibm.com) wrote:
> > > On Thu, Aug 22, 2013 at 09:33:18PM -0700, Stephen Hemminger wrote:

[ . . . ]

> > > > +
> > > > +/**
> > > > + * Splice an RCU-protected list into an existing list.
> > > > + *
> > > > + * Note that this function blocks in synchronize_rcu()
> > > > + *
> > > > + * Important note: this function is not called concurrently
> > > > + *       with other updates to the list.
> > > > + */
> > > > +static inline void caa_list_splice_init_rcu(struct cds_list_head *list,
> > > > +					    struct cds_list_head *head)
> > > > +{
> > > > +	struct cds_list_head *first = list->next;
> > > > +	struct cds_list_head *last = list->prev;
> > > > +	struct cds_list_head *at = head->next;
> > > > +
> > > > +	if (cds_list_empty(list))
> > > > +		return;
> > > > +
> > > > +	/* "first" and "last" tracking list, so initialize it. */
> > > > +	CDS_INIT_LIST_HEAD(list);
> > > 
> > > This change is happening in the presence of readers on the list, right?
> > > For this to work reliably in the presence of mischievous compilers,
> > > wouldn't CDS_INIT_LIST_HEAD() need to use CMM_ACCESS_ONCE() for its
> > > pointer accesses?
> > 
> > Actually, we have rcu_assign_pointer()/rcu_set_pointer() exactly for
> > this. They even skip the memory barrier if they store a NULL pointer.
> > 
> > > Hmmm...  The kernel version seems to have the same issue...
> > 
> > The compiler memory model of the Linux kernel AFAIK does not require an
> > ACCESS_ONCE() for stores to word-aligned, word-sized integers/pointers,
> > even if those are expected to be read concurrently. For reference, see:
> > 
> > #define __rcu_assign_pointer(p, v, space) \
> >         do { \
> >                 smp_wmb(); \
> >                 (p) = (typeof(*v) __force space *)(v); \
> >         } while (0)
> 
> Or I need to fix this one as well.  ;-)

In that vein...  Is there anything like typeof() that also preserves
sparse's notion of address space?  Wrapping an ACCESS_ONCE() around
"p" in the assignment above results in sparse errors.

							Thanx, Paul

							Thanx, Paul

Re: [RFC] adding into middle of RCU list

[Josh Triplett]

On Thu, Aug 29, 2013 at 05:57:33PM -0700, Paul E. McKenney wrote:
> On Fri, Aug 23, 2013 at 02:08:22PM -0700, Paul E. McKenney wrote:
> > On Fri, Aug 23, 2013 at 01:16:53PM -0400, Mathieu Desnoyers wrote:
> > > #define __rcu_assign_pointer(p, v, space) \
> > >         do { \
> > >                 smp_wmb(); \
> > >                 (p) = (typeof(*v) __force space *)(v); \
> > >         } while (0)
> > 
> > Or I need to fix this one as well.  ;-)
> 
> In that vein...  Is there anything like typeof() that also preserves
> sparse's notion of address space?  Wrapping an ACCESS_ONCE() around
> "p" in the assignment above results in sparse errors.

typeof() will preserve sparse's notion of address space as long as you
do typeof(p), not typeof(*p):

$ cat test.c
#define as(n) __attribute__((address_space(n),noderef))
#define __force __attribute__((force))

int main(void)
{
    int target = 0;
    int as(1) *foo = (__force typeof(target) as(1) *) ⌖
    typeof(foo) bar = foo;
    return *bar;
}
$ sparse test.c
test.c:9:13: warning: dereference of noderef expression

Notice that sparse didn't warn on the assignment of foo to bar (because
typeof propagated the address space of 1), and warned on the dereference
of bar (because typeof propagated noderef).

- Josh Triplett

Re: [RFC] adding into middle of RCU list

[Josh Triplett]

On Thu, Aug 29, 2013 at 05:57:33PM -0700, Paul E. McKenney wrote:
> On Fri, Aug 23, 2013 at 02:08:22PM -0700, Paul E. McKenney wrote:
> > On Fri, Aug 23, 2013 at 01:16:53PM -0400, Mathieu Desnoyers wrote:
> > > #define __rcu_assign_pointer(p, v, space) \
> > >         do { \
> > >                 smp_wmb(); \
> > >                 (p) = (typeof(*v) __force space *)(v); \
> > >         } while (0)
> > 
> > Or I need to fix this one as well.  ;-)
> 
> In that vein...  Is there anything like typeof() that also preserves
> sparse's notion of address space?  Wrapping an ACCESS_ONCE() around
> "p" in the assignment above results in sparse errors.

typeof() will preserve sparse's notion of address space as long as you
do typeof(p), not typeof(*p):

$ cat test.c
#define as(n) __attribute__((address_space(n),noderef))
#define __force __attribute__((force))

int main(void)
{
    int target = 0;
    int as(1) *foo = (__force typeof(target) as(1) *) ⌖
    typeof(foo) bar = foo;
    return *bar;
}
$ sparse test.c
test.c:9:13: warning: dereference of noderef expression

Notice that sparse didn't warn on the assignment of foo to bar (because
typeof propagated the address space of 1), and warned on the dereference
of bar (because typeof propagated noderef).

- Josh Triplett

Re: [RFC] adding into middle of RCU list

[Paul E. McKenney]

On Thu, Aug 29, 2013 at 07:16:37PM -0700, Josh Triplett wrote:
> On Thu, Aug 29, 2013 at 05:57:33PM -0700, Paul E. McKenney wrote:
> > On Fri, Aug 23, 2013 at 02:08:22PM -0700, Paul E. McKenney wrote:
> > > On Fri, Aug 23, 2013 at 01:16:53PM -0400, Mathieu Desnoyers wrote:
> > > > #define __rcu_assign_pointer(p, v, space) \
> > > >         do { \
> > > >                 smp_wmb(); \
> > > >                 (p) = (typeof(*v) __force space *)(v); \
> > > >         } while (0)
> > > 
> > > Or I need to fix this one as well.  ;-)
> > 
> > In that vein...  Is there anything like typeof() that also preserves
> > sparse's notion of address space?  Wrapping an ACCESS_ONCE() around
> > "p" in the assignment above results in sparse errors.
> 
> typeof() will preserve sparse's notion of address space as long as you
> do typeof(p), not typeof(*p):
> 
> $ cat test.c
> #define as(n) __attribute__((address_space(n),noderef))
> #define __force __attribute__((force))
> 
> int main(void)
> {
>     int target = 0;
>     int as(1) *foo = (__force typeof(target) as(1) *) ⌖
>     typeof(foo) bar = foo;
>     return *bar;
> }
> $ sparse test.c
> test.c:9:13: warning: dereference of noderef expression
> 
> Notice that sparse didn't warn on the assignment of foo to bar (because
> typeof propagated the address space of 1), and warned on the dereference
> of bar (because typeof propagated noderef).

Thank you for the info!

Suppose that I want to do something like this:

#define __rcu_assign_pointer(p, v, space) \
        do { \
                smp_wmb(); \
                ACCESS_ONCE(p) = (typeof(*v) __force space *)(v); \
        } while (0)

Now, this does typeof(*p), so as you noted above sparse complains about
address-space mismatches.  Thus far, I haven't been able to come up with
something that (1) does sparse address-space checking, (2) does C type
checking, and (3) forces the assignment to be volatile.

Any thoughts on how to do this?

							Thanx, Paul

Re: [RFC] adding into middle of RCU list

[Josh Triplett]

On Sat, Aug 31, 2013 at 02:32:28PM -0700, Paul E. McKenney wrote:
> On Thu, Aug 29, 2013 at 07:16:37PM -0700, Josh Triplett wrote:
> > On Thu, Aug 29, 2013 at 05:57:33PM -0700, Paul E. McKenney wrote:
> > > On Fri, Aug 23, 2013 at 02:08:22PM -0700, Paul E. McKenney wrote:
> > > > On Fri, Aug 23, 2013 at 01:16:53PM -0400, Mathieu Desnoyers wrote:
> > > > > #define __rcu_assign_pointer(p, v, space) \
> > > > >         do { \
> > > > >                 smp_wmb(); \
> > > > >                 (p) = (typeof(*v) __force space *)(v); \
> > > > >         } while (0)
> > > > 
> > > > Or I need to fix this one as well.  ;-)
> > > 
> > > In that vein...  Is there anything like typeof() that also preserves
> > > sparse's notion of address space?  Wrapping an ACCESS_ONCE() around
> > > "p" in the assignment above results in sparse errors.
> > 
> > typeof() will preserve sparse's notion of address space as long as you
> > do typeof(p), not typeof(*p):
> > 
> > $ cat test.c
> > #define as(n) __attribute__((address_space(n),noderef))
> > #define __force __attribute__((force))
> > 
> > int main(void)
> > {
> >     int target = 0;
> >     int as(1) *foo = (__force typeof(target) as(1) *) ⌖
> >     typeof(foo) bar = foo;
> >     return *bar;
> > }
> > $ sparse test.c
> > test.c:9:13: warning: dereference of noderef expression
> > 
> > Notice that sparse didn't warn on the assignment of foo to bar (because
> > typeof propagated the address space of 1), and warned on the dereference
> > of bar (because typeof propagated noderef).
> 
> Thank you for the info!
> 
> Suppose that I want to do something like this:
> 
> #define __rcu_assign_pointer(p, v, space) \
>         do { \
>                 smp_wmb(); \
>                 ACCESS_ONCE(p) = (typeof(*v) __force space *)(v); \
>         } while (0)
> 
> Now, this does typeof(*p), so as you noted above sparse complains about
> address-space mismatches.  Thus far, I haven't been able to come up with
> something that (1) does sparse address-space checking, (2) does C type
> checking, and (3) forces the assignment to be volatile.
> 
> Any thoughts on how to do this?

First of all, if p and v had compatible types *including* address
spaces, you wouldn't need the "space" argument; the following
self-contained test case passes both sparse and GCC typechecking:

#define as(n) __attribute__((address_space(n),noderef))
#define __force __attribute__((force))
#define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
extern void smp_wmb(void);

#define rcu_assign_pointer(p, v) \
    do { \
        smp_wmb(); \
        ACCESS_ONCE(p) = (v); \
    } while (0)

struct foo;

int main(void)
{
    struct foo as(1) *dest;
    struct foo as(1) *src = (void *)0;

    rcu_assign_pointer(dest, src);

    return 0;
}



But in this case, you want dest and src to have compatible types except
that dest must have the __rcu address space and src might not.  So,
let's change the types of dest and src, and add the appropriate cast.
The following also passes both GCC and sparse:

#define __rcu __attribute__((address_space(4),noderef))
#define __force __attribute__((force))
#define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
extern void smp_wmb(void);

#define rcu_assign_pointer(p, v) \
    do { \
        smp_wmb(); \
        ACCESS_ONCE(p) = (typeof(*(v)) __rcu __force *)(v); \
    } while (0)

struct foo { int x; };

int main(void)
{
    struct foo __rcu *dest;
    struct foo *src = (void *)0;

    rcu_assign_pointer(dest, src);

    return 0;
}


However, that cast forces the source to have the __rcu address space
without checking what address space it started out with.  If you want to
verify that the source has the kernel address space, you can cast to
that address space first, *without* __force, which will warn if the
source doesn't start out with that address space:

#define __kernel __attribute__((address_space(0)))
#define __user __attribute__((address_space(1),noderef))
#define __rcu __attribute__((address_space(4),noderef))
#define __force __attribute__((force))
#define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
extern void smp_wmb(void);

#define rcu_assign_pointer(p, v) \
    do { \
        smp_wmb(); \
        ACCESS_ONCE(p) = (typeof(*(v)) __rcu __force *)(typeof(*(v)) __kernel *)(v); \
    } while (0)

struct foo { int x; };

int main(void)
{
    struct foo __rcu *dest;
    struct foo *src = (void *)0;
    struct foo __user *badsrc = (void *)0;

    rcu_assign_pointer(dest, src);
    rcu_assign_pointer(dest, badsrc);

    return 0;
}


This produces a warning on the line using badsrc:

test.c:23:5: warning: cast removes address space of expression

However, that doesn't seem like the most obvious warning, since
rcu_assign_pointer doesn't look like a cast, and since it doesn't print
the full types involved like most address space warnings do.  So,
instead, let's add and use a __chk_kernel_ptr function, similar to
__chk_user_ptr in compiler.h:

#define __kernel __attribute__((address_space(0)))
#define __user __attribute__((address_space(1),noderef))
#define __rcu __attribute__((address_space(4),noderef))
#define __force __attribute__((force))
#define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
extern void __chk_kernel_ptr(const volatile void *);
extern void smp_wmb(void);

#define rcu_assign_pointer(p, v) \
    do { \
        smp_wmb(); \
        __chk_kernel_ptr(v); \
        ACCESS_ONCE(p) = (typeof(*(v)) __rcu __force *)(v); \
    } while (0)

struct foo { int x; };

int main(void)
{
    struct foo __rcu *dest;
    struct foo *src = (void *)0;
    struct foo __user *badsrc = (void *)0;

    rcu_assign_pointer(dest, src);
    rcu_assign_pointer(dest, badsrc);

    return 0;
}


This produces a somewhat better warning:

test.c:25:5: warning: incorrect type in argument 1 (different address spaces)
test.c:25:5:    expected void const volatile *<noident>
test.c:25:5:    got struct foo [noderef] <asn:1>*badsrc

That at least shows the full type of badsrc, but it still seems
suboptimal for two reasons: it says it expects "void const volatile *"
rather than the actual type it wants, and it says "in argument 1" (of
__chk_kernel_ptr), which seems unnecessarily confusing when the type
error actually applies to argument 2 of rcu_assign_pointer.  We can do
better by declaring a fake local function for checking, instead:

#define __kernel __attribute__((address_space(0)))
#define __user __attribute__((address_space(1),noderef))
#define __rcu __attribute__((address_space(4),noderef))
#define __force __attribute__((force))
#define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
extern void smp_wmb(void);

#define rcu_assign_pointer(p, v) \
    do { \
        smp_wmb(); \
        extern void __rcu_assign_pointer_typecheck(int, typeof(*(v)) __kernel *); \
        __rcu_assign_pointer_typecheck(0, v); \
        ACCESS_ONCE(p) = (typeof(*(v)) __rcu __force *)(v); \
    } while (0)

struct foo { int x; };

int main(void)
{
    struct foo __rcu *dest;
    struct foo *src = (void *)0;
    struct foo __user *badsrc = (void *)0;

    rcu_assign_pointer(dest, src);
    rcu_assign_pointer(dest, badsrc);

    return 0;
}


This last approach produces a very clear warning:

test.c:25:5: warning: incorrect type in argument 2 (different address spaces)
test.c:25:5:    expected struct foo *<noident>
test.c:25:5:    got struct foo [noderef] <asn:1>*badsrc

If you want, you can even add an argument name for the second argument
of __rcu_assign_pointer_typecheck, and it'll replace the <noident> in
the second line of the warning.

So, that last approach meets all the criteria you mentioned:
> something that (1) does sparse address-space checking, (2) does C type
> checking, and (3) forces the assignment to be volatile.

Will that work for all the use cases you have in mind?  If so, I'll
submit a patch changing rcu_assign_pointer to use that approach.

- Josh Triplett

Re: [RFC] adding into middle of RCU list

[Paul E. McKenney]

On Sun, Sep 01, 2013 at 01:42:10PM -0700, Josh Triplett wrote:
> On Sat, Aug 31, 2013 at 02:32:28PM -0700, Paul E. McKenney wrote:
> > On Thu, Aug 29, 2013 at 07:16:37PM -0700, Josh Triplett wrote:
> > > On Thu, Aug 29, 2013 at 05:57:33PM -0700, Paul E. McKenney wrote:
> > > > On Fri, Aug 23, 2013 at 02:08:22PM -0700, Paul E. McKenney wrote:
> > > > > On Fri, Aug 23, 2013 at 01:16:53PM -0400, Mathieu Desnoyers wrote:
> > > > > > #define __rcu_assign_pointer(p, v, space) \
> > > > > >         do { \
> > > > > >                 smp_wmb(); \
> > > > > >                 (p) = (typeof(*v) __force space *)(v); \
> > > > > >         } while (0)
> > > > > 
> > > > > Or I need to fix this one as well.  ;-)
> > > > 
> > > > In that vein...  Is there anything like typeof() that also preserves
> > > > sparse's notion of address space?  Wrapping an ACCESS_ONCE() around
> > > > "p" in the assignment above results in sparse errors.
> > > 
> > > typeof() will preserve sparse's notion of address space as long as you
> > > do typeof(p), not typeof(*p):
> > > 
> > > $ cat test.c
> > > #define as(n) __attribute__((address_space(n),noderef))
> > > #define __force __attribute__((force))
> > > 
> > > int main(void)
> > > {
> > >     int target = 0;
> > >     int as(1) *foo = (__force typeof(target) as(1) *) ⌖
> > >     typeof(foo) bar = foo;
> > >     return *bar;
> > > }
> > > $ sparse test.c
> > > test.c:9:13: warning: dereference of noderef expression
> > > 
> > > Notice that sparse didn't warn on the assignment of foo to bar (because
> > > typeof propagated the address space of 1), and warned on the dereference
> > > of bar (because typeof propagated noderef).
> > 
> > Thank you for the info!
> > 
> > Suppose that I want to do something like this:
> > 
> > #define __rcu_assign_pointer(p, v, space) \
> >         do { \
> >                 smp_wmb(); \
> >                 ACCESS_ONCE(p) = (typeof(*v) __force space *)(v); \
> >         } while (0)
> > 
> > Now, this does typeof(*p), so as you noted above sparse complains about
> > address-space mismatches.  Thus far, I haven't been able to come up with
> > something that (1) does sparse address-space checking, (2) does C type
> > checking, and (3) forces the assignment to be volatile.
> > 
> > Any thoughts on how to do this?
> 
> First of all, if p and v had compatible types *including* address
> spaces, you wouldn't need the "space" argument; the following
> self-contained test case passes both sparse and GCC typechecking:
> 
> #define as(n) __attribute__((address_space(n),noderef))
> #define __force __attribute__((force))
> #define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
> extern void smp_wmb(void);
> 
> #define rcu_assign_pointer(p, v) \
>     do { \
>         smp_wmb(); \
>         ACCESS_ONCE(p) = (v); \
>     } while (0)
> 
> struct foo;
> 
> int main(void)
> {
>     struct foo as(1) *dest;
>     struct foo as(1) *src = (void *)0;
> 
>     rcu_assign_pointer(dest, src);
> 
>     return 0;
> }
> 
> 
> 
> But in this case, you want dest and src to have compatible types except
> that dest must have the __rcu address space and src might not.  So,
> let's change the types of dest and src, and add the appropriate cast.
> The following also passes both GCC and sparse:
> 
> #define __rcu __attribute__((address_space(4),noderef))
> #define __force __attribute__((force))
> #define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
> extern void smp_wmb(void);
> 
> #define rcu_assign_pointer(p, v) \
>     do { \
>         smp_wmb(); \
>         ACCESS_ONCE(p) = (typeof(*(v)) __rcu __force *)(v); \
>     } while (0)
> 
> struct foo { int x; };
> 
> int main(void)
> {
>     struct foo __rcu *dest;
>     struct foo *src = (void *)0;
> 
>     rcu_assign_pointer(dest, src);
> 
>     return 0;
> }
> 
> 
> However, that cast forces the source to have the __rcu address space
> without checking what address space it started out with.  If you want to
> verify that the source has the kernel address space, you can cast to
> that address space first, *without* __force, which will warn if the
> source doesn't start out with that address space:
> 
> #define __kernel __attribute__((address_space(0)))
> #define __user __attribute__((address_space(1),noderef))
> #define __rcu __attribute__((address_space(4),noderef))
> #define __force __attribute__((force))
> #define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
> extern void smp_wmb(void);
> 
> #define rcu_assign_pointer(p, v) \
>     do { \
>         smp_wmb(); \
>         ACCESS_ONCE(p) = (typeof(*(v)) __rcu __force *)(typeof(*(v)) __kernel *)(v); \
>     } while (0)
> 
> struct foo { int x; };
> 
> int main(void)
> {
>     struct foo __rcu *dest;
>     struct foo *src = (void *)0;
>     struct foo __user *badsrc = (void *)0;
> 
>     rcu_assign_pointer(dest, src);
>     rcu_assign_pointer(dest, badsrc);
> 
>     return 0;
> }
> 
> 
> This produces a warning on the line using badsrc:
> 
> test.c:23:5: warning: cast removes address space of expression
> 
> However, that doesn't seem like the most obvious warning, since
> rcu_assign_pointer doesn't look like a cast, and since it doesn't print
> the full types involved like most address space warnings do.  So,
> instead, let's add and use a __chk_kernel_ptr function, similar to
> __chk_user_ptr in compiler.h:
> 
> #define __kernel __attribute__((address_space(0)))
> #define __user __attribute__((address_space(1),noderef))
> #define __rcu __attribute__((address_space(4),noderef))
> #define __force __attribute__((force))
> #define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
> extern void __chk_kernel_ptr(const volatile void *);
> extern void smp_wmb(void);
> 
> #define rcu_assign_pointer(p, v) \
>     do { \
>         smp_wmb(); \
>         __chk_kernel_ptr(v); \
>         ACCESS_ONCE(p) = (typeof(*(v)) __rcu __force *)(v); \
>     } while (0)
> 
> struct foo { int x; };
> 
> int main(void)
> {
>     struct foo __rcu *dest;
>     struct foo *src = (void *)0;
>     struct foo __user *badsrc = (void *)0;
> 
>     rcu_assign_pointer(dest, src);
>     rcu_assign_pointer(dest, badsrc);
> 
>     return 0;
> }
> 
> 
> This produces a somewhat better warning:
> 
> test.c:25:5: warning: incorrect type in argument 1 (different address spaces)
> test.c:25:5:    expected void const volatile *<noident>
> test.c:25:5:    got struct foo [noderef] <asn:1>*badsrc
> 
> That at least shows the full type of badsrc, but it still seems
> suboptimal for two reasons: it says it expects "void const volatile *"
> rather than the actual type it wants, and it says "in argument 1" (of
> __chk_kernel_ptr), which seems unnecessarily confusing when the type
> error actually applies to argument 2 of rcu_assign_pointer.  We can do
> better by declaring a fake local function for checking, instead:
> 
> #define __kernel __attribute__((address_space(0)))
> #define __user __attribute__((address_space(1),noderef))
> #define __rcu __attribute__((address_space(4),noderef))
> #define __force __attribute__((force))
> #define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
> extern void smp_wmb(void);
> 
> #define rcu_assign_pointer(p, v) \
>     do { \
>         smp_wmb(); \
>         extern void __rcu_assign_pointer_typecheck(int, typeof(*(v)) __kernel *); \
>         __rcu_assign_pointer_typecheck(0, v); \
>         ACCESS_ONCE(p) = (typeof(*(v)) __rcu __force *)(v); \
>     } while (0)
> 
> struct foo { int x; };
> 
> int main(void)
> {
>     struct foo __rcu *dest;
>     struct foo *src = (void *)0;
>     struct foo __user *badsrc = (void *)0;
> 
>     rcu_assign_pointer(dest, src);
>     rcu_assign_pointer(dest, badsrc);
> 
>     return 0;
> }
> 
> 
> This last approach produces a very clear warning:
> 
> test.c:25:5: warning: incorrect type in argument 2 (different address spaces)
> test.c:25:5:    expected struct foo *<noident>
> test.c:25:5:    got struct foo [noderef] <asn:1>*badsrc
> 
> If you want, you can even add an argument name for the second argument
> of __rcu_assign_pointer_typecheck, and it'll replace the <noident> in
> the second line of the warning.
> 
> So, that last approach meets all the criteria you mentioned:
> > something that (1) does sparse address-space checking, (2) does C type
> > checking, and (3) forces the assignment to be volatile.
> 
> Will that work for all the use cases you have in mind?  If so, I'll
> submit a patch changing rcu_assign_pointer to use that approach.

Looks like it does the right thing, thank you!

Would it also be possible for the call to __rcu_assign_pointer_typecheck()
to be only present when building under sparse?

							Thanx, Paul

Re: [RFC] adding into middle of RCU list

[Josh Triplett]

On Sun, Sep 01, 2013 at 03:26:19PM -0700, Paul E. McKenney wrote:
> On Sun, Sep 01, 2013 at 01:42:10PM -0700, Josh Triplett wrote:
> > On Sat, Aug 31, 2013 at 02:32:28PM -0700, Paul E. McKenney wrote:
> > > On Thu, Aug 29, 2013 at 07:16:37PM -0700, Josh Triplett wrote:
> > > > On Thu, Aug 29, 2013 at 05:57:33PM -0700, Paul E. McKenney wrote:
> > > > > On Fri, Aug 23, 2013 at 02:08:22PM -0700, Paul E. McKenney wrote:
> > > > > > On Fri, Aug 23, 2013 at 01:16:53PM -0400, Mathieu Desnoyers wrote:
> > > > > > > #define __rcu_assign_pointer(p, v, space) \
> > > > > > >         do { \
> > > > > > >                 smp_wmb(); \
> > > > > > >                 (p) = (typeof(*v) __force space *)(v); \
> > > > > > >         } while (0)
> > > > > > 
> > > > > > Or I need to fix this one as well.  ;-)
> > > > > 
> > > > > In that vein...  Is there anything like typeof() that also preserves
> > > > > sparse's notion of address space?  Wrapping an ACCESS_ONCE() around
> > > > > "p" in the assignment above results in sparse errors.
> > > > 
> > > > typeof() will preserve sparse's notion of address space as long as you
> > > > do typeof(p), not typeof(*p):
> > > > 
> > > > $ cat test.c
> > > > #define as(n) __attribute__((address_space(n),noderef))
> > > > #define __force __attribute__((force))
> > > > 
> > > > int main(void)
> > > > {
> > > >     int target = 0;
> > > >     int as(1) *foo = (__force typeof(target) as(1) *) ⌖
> > > >     typeof(foo) bar = foo;
> > > >     return *bar;
> > > > }
> > > > $ sparse test.c
> > > > test.c:9:13: warning: dereference of noderef expression
> > > > 
> > > > Notice that sparse didn't warn on the assignment of foo to bar (because
> > > > typeof propagated the address space of 1), and warned on the dereference
> > > > of bar (because typeof propagated noderef).
> > > 
> > > Thank you for the info!
> > > 
> > > Suppose that I want to do something like this:
> > > 
> > > #define __rcu_assign_pointer(p, v, space) \
> > >         do { \
> > >                 smp_wmb(); \
> > >                 ACCESS_ONCE(p) = (typeof(*v) __force space *)(v); \
> > >         } while (0)
> > > 
> > > Now, this does typeof(*p), so as you noted above sparse complains about
> > > address-space mismatches.  Thus far, I haven't been able to come up with
> > > something that (1) does sparse address-space checking, (2) does C type
> > > checking, and (3) forces the assignment to be volatile.
> > > 
> > > Any thoughts on how to do this?
> > 
> > First of all, if p and v had compatible types *including* address
> > spaces, you wouldn't need the "space" argument; the following
> > self-contained test case passes both sparse and GCC typechecking:
> > 
> > #define as(n) __attribute__((address_space(n),noderef))
> > #define __force __attribute__((force))
> > #define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
> > extern void smp_wmb(void);
> > 
> > #define rcu_assign_pointer(p, v) \
> >     do { \
> >         smp_wmb(); \
> >         ACCESS_ONCE(p) = (v); \
> >     } while (0)
> > 
> > struct foo;
> > 
> > int main(void)
> > {
> >     struct foo as(1) *dest;
> >     struct foo as(1) *src = (void *)0;
> > 
> >     rcu_assign_pointer(dest, src);
> > 
> >     return 0;
> > }
> > 
> > 
> > 
> > But in this case, you want dest and src to have compatible types except
> > that dest must have the __rcu address space and src might not.  So,
> > let's change the types of dest and src, and add the appropriate cast.
> > The following also passes both GCC and sparse:
> > 
> > #define __rcu __attribute__((address_space(4),noderef))
> > #define __force __attribute__((force))
> > #define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
> > extern void smp_wmb(void);
> > 
> > #define rcu_assign_pointer(p, v) \
> >     do { \
> >         smp_wmb(); \
> >         ACCESS_ONCE(p) = (typeof(*(v)) __rcu __force *)(v); \
> >     } while (0)
> > 
> > struct foo { int x; };
> > 
> > int main(void)
> > {
> >     struct foo __rcu *dest;
> >     struct foo *src = (void *)0;
> > 
> >     rcu_assign_pointer(dest, src);
> > 
> >     return 0;
> > }
> > 
> > 
> > However, that cast forces the source to have the __rcu address space
> > without checking what address space it started out with.  If you want to
> > verify that the source has the kernel address space, you can cast to
> > that address space first, *without* __force, which will warn if the
> > source doesn't start out with that address space:
> > 
> > #define __kernel __attribute__((address_space(0)))
> > #define __user __attribute__((address_space(1),noderef))
> > #define __rcu __attribute__((address_space(4),noderef))
> > #define __force __attribute__((force))
> > #define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
> > extern void smp_wmb(void);
> > 
> > #define rcu_assign_pointer(p, v) \
> >     do { \
> >         smp_wmb(); \
> >         ACCESS_ONCE(p) = (typeof(*(v)) __rcu __force *)(typeof(*(v)) __kernel *)(v); \
> >     } while (0)
> > 
> > struct foo { int x; };
> > 
> > int main(void)
> > {
> >     struct foo __rcu *dest;
> >     struct foo *src = (void *)0;
> >     struct foo __user *badsrc = (void *)0;
> > 
> >     rcu_assign_pointer(dest, src);
> >     rcu_assign_pointer(dest, badsrc);
> > 
> >     return 0;
> > }
> > 
> > 
> > This produces a warning on the line using badsrc:
> > 
> > test.c:23:5: warning: cast removes address space of expression
> > 
> > However, that doesn't seem like the most obvious warning, since
> > rcu_assign_pointer doesn't look like a cast, and since it doesn't print
> > the full types involved like most address space warnings do.  So,
> > instead, let's add and use a __chk_kernel_ptr function, similar to
> > __chk_user_ptr in compiler.h:
> > 
> > #define __kernel __attribute__((address_space(0)))
> > #define __user __attribute__((address_space(1),noderef))
> > #define __rcu __attribute__((address_space(4),noderef))
> > #define __force __attribute__((force))
> > #define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
> > extern void __chk_kernel_ptr(const volatile void *);
> > extern void smp_wmb(void);
> > 
> > #define rcu_assign_pointer(p, v) \
> >     do { \
> >         smp_wmb(); \
> >         __chk_kernel_ptr(v); \
> >         ACCESS_ONCE(p) = (typeof(*(v)) __rcu __force *)(v); \
> >     } while (0)
> > 
> > struct foo { int x; };
> > 
> > int main(void)
> > {
> >     struct foo __rcu *dest;
> >     struct foo *src = (void *)0;
> >     struct foo __user *badsrc = (void *)0;
> > 
> >     rcu_assign_pointer(dest, src);
> >     rcu_assign_pointer(dest, badsrc);
> > 
> >     return 0;
> > }
> > 
> > 
> > This produces a somewhat better warning:
> > 
> > test.c:25:5: warning: incorrect type in argument 1 (different address spaces)
> > test.c:25:5:    expected void const volatile *<noident>
> > test.c:25:5:    got struct foo [noderef] <asn:1>*badsrc
> > 
> > That at least shows the full type of badsrc, but it still seems
> > suboptimal for two reasons: it says it expects "void const volatile *"
> > rather than the actual type it wants, and it says "in argument 1" (of
> > __chk_kernel_ptr), which seems unnecessarily confusing when the type
> > error actually applies to argument 2 of rcu_assign_pointer.  We can do
> > better by declaring a fake local function for checking, instead:
> > 
> > #define __kernel __attribute__((address_space(0)))
> > #define __user __attribute__((address_space(1),noderef))
> > #define __rcu __attribute__((address_space(4),noderef))
> > #define __force __attribute__((force))
> > #define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
> > extern void smp_wmb(void);
> > 
> > #define rcu_assign_pointer(p, v) \
> >     do { \
> >         smp_wmb(); \
> >         extern void __rcu_assign_pointer_typecheck(int, typeof(*(v)) __kernel *); \
> >         __rcu_assign_pointer_typecheck(0, v); \
> >         ACCESS_ONCE(p) = (typeof(*(v)) __rcu __force *)(v); \
> >     } while (0)
> > 
> > struct foo { int x; };
> > 
> > int main(void)
> > {
> >     struct foo __rcu *dest;
> >     struct foo *src = (void *)0;
> >     struct foo __user *badsrc = (void *)0;
> > 
> >     rcu_assign_pointer(dest, src);
> >     rcu_assign_pointer(dest, badsrc);
> > 
> >     return 0;
> > }
> > 
> > 
> > This last approach produces a very clear warning:
> > 
> > test.c:25:5: warning: incorrect type in argument 2 (different address spaces)
> > test.c:25:5:    expected struct foo *<noident>
> > test.c:25:5:    got struct foo [noderef] <asn:1>*badsrc
> > 
> > If you want, you can even add an argument name for the second argument
> > of __rcu_assign_pointer_typecheck, and it'll replace the <noident> in
> > the second line of the warning.
> > 
> > So, that last approach meets all the criteria you mentioned:
> > > something that (1) does sparse address-space checking, (2) does C type
> > > checking, and (3) forces the assignment to be volatile.
> > 
> > Will that work for all the use cases you have in mind?  If so, I'll
> > submit a patch changing rcu_assign_pointer to use that approach.
> 
> Looks like it does the right thing, thank you!
> 
> Would it also be possible for the call to __rcu_assign_pointer_typecheck()
> to be only present when building under sparse?

Sure; it just needs to go in a separate macro that only gets a non-empty
definition ifdef __CHECKER__.

Patch momentarily.

- Josh Triplett

[PATCH] rcu: Make rcu_assign_pointer's assignment volatile and type-safe

[Josh Triplett]

rcu_assign_pointer needs to use ACCESS_ONCE to make the assignment to
the destination pointer volatile, to protect against compilers too
clever for their own good.

In addition, since rcu_assign_pointer force-casts the source pointer to
add the __rcu address space (overriding any existing address space), add
an explicit check that the source pointer has the __kernel address space
to start with.

This new check produces warnings like this, when attempting to assign
from a __user pointer:

test.c:25:9: warning: incorrect type in argument 2 (different address spaces)
test.c:25:9:    expected struct foo *<noident>
test.c:25:9:    got struct foo [noderef] <asn:1>*badsrc

Signed-off-by: Josh Triplett <josh@joshtriplett.org>
---
 include/linux/rcupdate.h | 12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)

diff --git a/include/linux/rcupdate.h b/include/linux/rcupdate.h
index 4b14bdc..3f62def 100644
--- a/include/linux/rcupdate.h
+++ b/include/linux/rcupdate.h
@@ -510,8 +510,17 @@ static inline void rcu_preempt_sleep_check(void)
 #ifdef __CHECKER__
 #define rcu_dereference_sparse(p, space) \
 	((void)(((typeof(*p) space *)p) == p))
+/* The dummy first argument in __rcu_assign_pointer_typecheck makes the
+ * typechecked pointer the second argument, matching rcu_assign_pointer itself;
+ * this avoids confusion about argument numbers in warning messages. */
+#define __rcu_assign_pointer_check_kernel(v) \
+	do { \
+		extern void __rcu_assign_pointer_typecheck(int, typeof(*(v)) __kernel *); \
+		__rcu_assign_pointer_typecheck(0, v); \
+	} while (0)
 #else /* #ifdef __CHECKER__ */
 #define rcu_dereference_sparse(p, space)
+#define __rcu_assign_pointer_check_kernel(v) do { } while (0)
 #endif /* #else #ifdef __CHECKER__ */
 
 #define __rcu_access_pointer(p, space) \
@@ -555,7 +564,8 @@ static inline void rcu_preempt_sleep_check(void)
 #define __rcu_assign_pointer(p, v, space) \
 	do { \
 		smp_wmb(); \
-		(p) = (typeof(*v) __force space *)(v); \
+		__rcu_assign_pointer_check_kernel(v); \
+		ACCESS_ONCE(p) = (typeof(*(v)) __force space *)(v); \
 	} while (0)
 
 

Re: [PATCH] rcu: Make rcu_assign_pointer's assignment volatile and type-safe

[Paul E. McKenney]

On Sun, Sep 01, 2013 at 04:42:52PM -0700, Josh Triplett wrote:
> rcu_assign_pointer needs to use ACCESS_ONCE to make the assignment to
> the destination pointer volatile, to protect against compilers too
> clever for their own good.
> 
> In addition, since rcu_assign_pointer force-casts the source pointer to
> add the __rcu address space (overriding any existing address space), add
> an explicit check that the source pointer has the __kernel address space
> to start with.
> 
> This new check produces warnings like this, when attempting to assign
> from a __user pointer:
> 
> test.c:25:9: warning: incorrect type in argument 2 (different address spaces)
> test.c:25:9:    expected struct foo *<noident>
> test.c:25:9:    got struct foo [noderef] <asn:1>*badsrc
> 
> Signed-off-by: Josh Triplett <josh@joshtriplett.org>

Queued for 3.13, thank you very much!

							Thanx, Paul

> ---
>  include/linux/rcupdate.h | 12 +++++++++++-
>  1 file changed, 11 insertions(+), 1 deletion(-)
> 
> diff --git a/include/linux/rcupdate.h b/include/linux/rcupdate.h
> index 4b14bdc..3f62def 100644
> --- a/include/linux/rcupdate.h
> +++ b/include/linux/rcupdate.h
> @@ -510,8 +510,17 @@ static inline void rcu_preempt_sleep_check(void)
>  #ifdef __CHECKER__
>  #define rcu_dereference_sparse(p, space) \
>  	((void)(((typeof(*p) space *)p) == p))
> +/* The dummy first argument in __rcu_assign_pointer_typecheck makes the
> + * typechecked pointer the second argument, matching rcu_assign_pointer itself;
> + * this avoids confusion about argument numbers in warning messages. */
> +#define __rcu_assign_pointer_check_kernel(v) \
> +	do { \
> +		extern void __rcu_assign_pointer_typecheck(int, typeof(*(v)) __kernel *); \
> +		__rcu_assign_pointer_typecheck(0, v); \
> +	} while (0)
>  #else /* #ifdef __CHECKER__ */
>  #define rcu_dereference_sparse(p, space)
> +#define __rcu_assign_pointer_check_kernel(v) do { } while (0)
>  #endif /* #else #ifdef __CHECKER__ */
> 
>  #define __rcu_access_pointer(p, space) \
> @@ -555,7 +564,8 @@ static inline void rcu_preempt_sleep_check(void)
>  #define __rcu_assign_pointer(p, v, space) \
>  	do { \
>  		smp_wmb(); \
> -		(p) = (typeof(*v) __force space *)(v); \
> +		__rcu_assign_pointer_check_kernel(v); \
> +		ACCESS_ONCE(p) = (typeof(*(v)) __force space *)(v); \
>  	} while (0)
> 
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
> 

[RFC] adding into middle of RCU list

[Stephen Hemminger]

I needed to add into the middle of an RCU list, does this make sense.



From a45892b0d49ac5fe449ba7e19c646cb17f7cee57 Mon Sep 17 00:00:00 2001
From: Stephen Hemminger <stephen@networkplumber.org>
Date: Thu, 22 Aug 2013 21:27:04 -0700
Subject: [PATCH] Add list_splice_init_rcu to allow insertion into a RCU list

Simplified version of the version in kernel.
---
 urcu/rculist.h |   32 ++++++++++++++++++++++++++++++++
 1 file changed, 32 insertions(+)

diff --git a/urcu/rculist.h b/urcu/rculist.h
index 1fd2df3..2e8a5a0 100644
--- a/urcu/rculist.h
+++ b/urcu/rculist.h
@@ -72,6 +72,38 @@ void cds_list_del_rcu(struct cds_list_head *elem)
 	CMM_STORE_SHARED(elem->prev->next, elem->next);
 }
 
+
+/**
+ * Splice an RCU-protected list into an existing list.
+ *
+ * Note that this function blocks in synchronize_rcu()
+ *
+ * Important note: this function is not called concurrently
+ *       with other updates to the list.
+ */
+static inline void caa_list_splice_init_rcu(struct cds_list_head *list,
+					    struct cds_list_head *head)
+{
+	struct cds_list_head *first = list->next;
+	struct cds_list_head *last = list->prev;
+	struct cds_list_head *at = head->next;
+
+	if (cds_list_empty(list))
+		return;
+
+	/* "first" and "last" tracking list, so initialize it. */
+	CDS_INIT_LIST_HEAD(list);
+
+	/* Wait for any readers to finish using the list before splicing */
+	synchronize_rcu();
+
+	/* Readers are finished with the source list, so perform splice. */
+	last->next = at;
+	rcu_assign_pointer(head->next, first);
+	first->prev = head;
+	at->prev = last;
+}
+
 /*
  * Iteration through all elements of the list must be done while rcu_read_lock()
  * is held.
-- 
1.7.10.4