Skip to contentSkip to conversation

adding into middle of RCU list

RFC Applied Mathieu Desnoyers 4 participants 16 messages Aug 23, 2013 – Sep 2, 2013 6 messages not in the archive

Subsystems (2)
lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

Mathieu Desnoyers

author reviewer
#1 lore raw

Hi Stephen,

Quoted 2 lines · * Stephen Hemminger ([email protected]) 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,

Quoted 17 lines

From a45892b0d49ac5fe449ba7e19c646cb17f7cee57 Mon Sep 17 00:00:00 2001
From: Stephen Hemminger <[email protected]>
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(+)
urcu/rculist.h +0 -0
index 1fd2df3..2e8a5a0 100644

urcu/rculist.h void cds_list_del_rcu(struct cds_list_head *elem) · line 81

Quoted 10 lines
urcu/rculist.h +7 -0
@@ -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

urcu/rculist.h void cds_list_del_rcu(struct cds_list_head *elem) · line 82

Quoted 1 line
urcu/rculist.h +1 -0
+ *       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.

Quoted 13 lines
urcu/rculist.h +13 -0
+ */
+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);

urcu/rculist.h void cds_list_del_rcu(struct cds_list_head *elem) · line 105

Quoted 10 lines
urcu/rculist.h +10 -0
+
+	/* 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

Quoted 7 lines
urcu/rculist.h +1 -0
+
 /*
  * Iteration through all elements of the list must be done while rcu_read_lock()
  * is held.
Signature · 1 line
1.7.10.4
Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#2 lore raw
In reply to a message not in the archive
Quoted 33 lines · 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 <[email protected]>
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(+)
urcu/rculist.h +11 -0
index 1fd2df3..2e8a5a0 100644
@@ -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)

urcu/rculist.h void cds_list_del_rcu(struct cds_list_head *elem) · line 95

Quoted 10 lines
urcu/rculist.h +10 -0
+{
+	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

Quoted 16 lines
urcu/rculist.h +11 -0
+
+	/* 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.
Signature · 1 line
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.

include/linux/rculist.h +21 -2
index 4106721..45a0a9e 100644
@@ -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.

A message that is not in the archive (sent off-list or not yet received): [email protected]

author reviewer
#4 lore raw
Quoted 41 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 40 lines · 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 <[email protected]>
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(+)
urcu/rculist.h +18 -0
index 1fd2df3..2e8a5a0 100644
@@ -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;
Quoted 8 lines

urcu/rculist.h void cds_list_del_rcu(struct cds_list_head *elem) · line 95

Quoted 3 lines
urcu/rculist.h +3 -0
+
+	/* "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.

Quoted 2 lines

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

Quoted 82 lines

Patch below, FWIW.

Thanx, Paul

Quoted 16 lines
urcu/rculist.h +11 -0
+
+	/* 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.
Signature · 1 line
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.

include/linux/rculist.h +21 -2
index 4106721..45a0a9e 100644
@@ -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.
Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

A message that is not in the archive (sent off-list or not yet received): 20130823171653.GA16558@Krystal

#6 lore raw
Quoted 157 lines · On Fri, 23 Aug 2013 13:16:53 -0400 Mathieu Desnoyers…
Quoted 41 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 40 lines · 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 <[email protected]>
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(+)
urcu/rculist.h +18 -0
index 1fd2df3..2e8a5a0 100644
@@ -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;
Quoted 8 lines

urcu/rculist.h void cds_list_del_rcu(struct cds_list_head *elem) · line 95

Quoted 3 lines
urcu/rculist.h +3 -0
+
+	/* "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.

Quoted 2 lines

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

Quoted 76 lines

Patch below, FWIW.

Thanx, Paul

Quoted 16 lines
urcu/rculist.h +11 -0
+
+	/* 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.
Signature · 1 line
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.

include/linux/rculist.h +20 -1
index 4106721..45a0a9e 100644
@@ -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().
+	 */
 
Quoted 7 lines

include/linux/rculist.h static inline void list_splice_init_rcu(struct list_head *list, · line 218

Quoted 6 lines
include/linux/rculist.h +1 -1
-	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.

A message that is not in the archive (sent off-list or not yet received): [email protected]

#8 lore raw
Quoted 163 lines · Stephen Hemminger
Quoted 160 lines · On Fri, 23 Aug 2013 13:16:53 -0400 Mathieu Desnoyers…
Quoted 41 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 40 lines · 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 <[email protected]>
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(+)
urcu/rculist.h +18 -0
index 1fd2df3..2e8a5a0 100644
@@ -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;
Quoted 8 lines

urcu/rculist.h void cds_list_del_rcu(struct cds_list_head *elem) · line 95

Quoted 3 lines
urcu/rculist.h +3 -0
+
+	/* "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.

Quoted 2 lines

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

Quoted 79 lines

Patch below, FWIW.

Thanx, Paul

Quoted 16 lines
urcu/rculist.h +11 -0
+
+	/* 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.
Signature · 1 line
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.

include/linux/rculist.h +21 -2
index 4106721..45a0a9e 100644
@@ -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);
 
Quoted 7 lines
Quoted 4 lines

include/linux/rculist.h static inline void list_splice_init_rcu(struct list_head *list, · line 218

Quoted 3 lines
include/linux/rculist.h +0 -0
 	/*
 	 * 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

A message that is not in the archive (sent off-list or not yet received): [email protected]

#10 lore raw
Quoted 169 lines · On Fri, 23 Aug 2013 14:05:51 -0700 "Paul E. McKenney"…
Quoted 168 lines · Stephen Hemminger
Quoted 164 lines · On Fri, 23 Aug 2013 13:16:53 -0400 Mathieu Desnoyers…
Quoted 41 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 40 lines · 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 <[email protected]>
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(+)
urcu/rculist.h +18 -0
index 1fd2df3..2e8a5a0 100644
@@ -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;
Quoted 8 lines

urcu/rculist.h void cds_list_del_rcu(struct cds_list_head *elem) · line 95

Quoted 3 lines
urcu/rculist.h +3 -0
+
+	/* "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.

Quoted 2 lines

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

Quoted 82 lines

Patch below, FWIW.

Thanx, Paul

Quoted 16 lines
urcu/rculist.h +11 -0
+
+	/* 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.
Signature · 1 line
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.

include/linux/rculist.h +21 -2
index 4106721..45a0a9e 100644
@@ -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.
Quoted 7 lines
Quoted 2 lines

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.

#11 lore raw
In reply to a message not in the archive
Quoted 61 lines · Mathieu Desnoyers
Quoted 41 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 40 lines · 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 <[email protected]>
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(+)
urcu/rculist.h +18 -0
index 1fd2df3..2e8a5a0 100644
@@ -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;
Quoted 8 lines

urcu/rculist.h void cds_list_del_rcu(struct cds_list_head *elem) · line 95

Quoted 3 lines
urcu/rculist.h +3 -0
+
+	/* "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.

Quoted 2 lines

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:

Quoted 5 lines
#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. ;-)

Quoted 8 lines

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

Quoted 93 lines

Thanks,

Mathieu

Quoted 82 lines

Patch below, FWIW.

Thanx, Paul

Quoted 16 lines
urcu/rculist.h +11 -0
+
+	/* 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.
Signature · 1 line
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.

include/linux/rculist.h +21 -2
index 4106721..45a0a9e 100644
@@ -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.
Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

A message that is not in the archive (sent off-list or not yet received): [email protected]

#13 lore raw
Quoted 3 lines · Paul E. McKenney
Quoted 2 lines · Mathieu Desnoyers
Quoted 1 line · * Paul E. McKenney ([email protected]) wrote:

On Thu, Aug 22, 2013 at 09:33:18PM -0700, Stephen Hemminger wrote:

[ . . . ]

Quoted 36 lines
Quoted 36 lines
Quoted 18 lines
Quoted 18 lines
(quoted diff) +18 -0
+
+/**
+ * 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;
Quoted 8 lines

Review

Quoted 3 lines
(quoted diff) +3 -0
+
+	/* "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.

Quoted 1 line

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:

Quoted 7 lines
Quoted 5 lines
#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

maintainer
#14 lore raw
Quoted 8 lines · Paul E. McKenney
Quoted 7 lines · Paul E. McKenney
Quoted 5 lines · Mathieu Desnoyers
#define __rcu_assign_pointer(p, v, space) \
        do { \
                smp_wmb(); \
                (p) = (typeof(*v) __force space *)(v); \
        } while (0)
Quoted 5 lines
Quoted 1 line

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) *) &target;
    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

#15 lore raw
Quoted 32 lines · Josh Triplett
Quoted 8 lines · Paul E. McKenney
Quoted 7 lines · Paul E. McKenney
Quoted 5 lines · Mathieu Desnoyers
#define __rcu_assign_pointer(p, v, space) \
        do { \
                smp_wmb(); \
                (p) = (typeof(*v) __force space *)(v); \
        } while (0)
Quoted 5 lines
Quoted 1 line

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) *) &target;
    typeof(foo) bar = foo;
    return *bar;
}
$ sparse test.c
test.c:9:13: warning: dereference of noderef expression
Quoted 3 lines

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

maintainer
#16 lore raw
Quoted 47 lines · Paul E. McKenney
Quoted 32 lines · Josh Triplett
Quoted 8 lines · Paul E. McKenney
Quoted 7 lines · Paul E. McKenney
Quoted 5 lines · Mathieu Desnoyers
#define __rcu_assign_pointer(p, v, space) \
        do { \
                smp_wmb(); \
                (p) = (typeof(*v) __force space *)(v); \
        } while (0)
Quoted 5 lines
Quoted 1 line

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) *) &target;
    typeof(foo) bar = foo;
    return *bar;
}
$ sparse test.c
test.c:9:13: warning: dereference of noderef expression
Quoted 3 lines

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)
Quoted 6 lines

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:

Quoted 2 lines

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

#17 lore raw
Quoted 240 lines · Josh Triplett
Quoted 47 lines · Paul E. McKenney
Quoted 32 lines · Josh Triplett
Quoted 8 lines · Paul E. McKenney
Quoted 7 lines · Paul E. McKenney
Quoted 5 lines · Mathieu Desnoyers
#define __rcu_assign_pointer(p, v, space) \
        do { \
                smp_wmb(); \
                (p) = (typeof(*v) __force space *)(v); \
        } while (0)
Quoted 5 lines
Quoted 1 line

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) *) &target;
    typeof(foo) bar = foo;
    return *bar;
}
$ sparse test.c
test.c:9:13: warning: dereference of noderef expression
Quoted 3 lines

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)
Quoted 6 lines

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.

Quoted 6 lines

So, that last approach meets all the criteria you mentioned:

Quoted 2 lines

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

maintainer
#18 lore raw
Quoted 245 lines · Paul E. McKenney
Quoted 244 lines · Josh Triplett
Quoted 47 lines · Paul E. McKenney
Quoted 32 lines · Josh Triplett
Quoted 8 lines · Paul E. McKenney
Quoted 7 lines · Paul E. McKenney
Quoted 5 lines · Mathieu Desnoyers
#define __rcu_assign_pointer(p, v, space) \
        do { \
                smp_wmb(); \
                (p) = (typeof(*v) __force space *)(v); \
        } while (0)
Quoted 5 lines
Quoted 1 line

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) *) &target;
    typeof(foo) bar = foo;
    return *bar;
}
$ sparse test.c
test.c:9:13: warning: dereference of noderef expression
Quoted 3 lines

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)
Quoted 6 lines

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:

Quoted 2 lines

something that (1) does sparse address-space checking, (2) does C type checking, and (3) forces the assignment to be volatile.

Quoted 7 lines
Quoted 2 lines

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

maintainer
#19 lore raw

PATCH 1/1 rcu: Make rcu_assign_pointer's assignment volatile and type-safe

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

---
 include/linux/rcupdate.h | 12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)
include/linux/rcupdate.h +11 -1
index 4b14bdc..3f62def 100644
@@ -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)
 
 
#20 lore raw

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

Quoted 9 lines · 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.

Quoted 8 lines

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

Queued for 3.13, thank you very much!

Thanx, Paul

Quoted 42 lines
---
 include/linux/rcupdate.h | 12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)
include/linux/rcupdate.h +11 -2
index 4b14bdc..3f62def 100644
@@ -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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

maintainer
#21 lore raw
In reply to Paul E. McKenney
Quoted 8 lines · Paul E. McKenney
Quoted 7 lines · Paul E. McKenney
Quoted 5 lines · Mathieu Desnoyers
#define __rcu_assign_pointer(p, v, space) \
        do { \
                smp_wmb(); \
                (p) = (typeof(*v) __force space *)(v); \
        } while (0)
Quoted 5 lines
Quoted 1 line

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) *) &target;
    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