rculist: Replaced list_first_entry_rcu() with list_first_or_null_rcu()

PATCH In review Michel Machado 2 participants 3 messages Apr 10, 2012 – Apr 12, 2012 RCU

Share & tools

Michel Machado

author

2012-04-10 18:07 UTC #0 lore raw

PATCH 1/1 rculist: Replaced list_first_entry_rcu() with list_first_or_null_rcu()

Replaced list_first_entry_rcu() with list_first_or_null_rcu() because list_first_entry_rcu() is not safe as one can find in the comment that this patch also adds.

This patch incorporated Paul's suggestions to the previous version of this patch available here:

https://lkml.org/lkml/2012/4/2/536

This patch cannot break any upstream code because list_first_entry_rcu is not being used anywhere in the kernel (tested with grep(1)), and external code that uses it is probably broken already.

Signed-off-by Michel Machado <[email protected]>

CC "Paul E. McKenney" <[email protected]>

CC Dipankar Sarma <[email protected]>

---

include/linux/rculist.h +0 -0

index d079290..ef5da30 100644
@@ -228,18 +228,43 @@ static inline void list_splice_init_rcu(struct

list_head *list,
})

/**
- * list_first_entry_rcu - get the first element from a list
+ * Where are list_empty_rcu() and list_first_entry_rcu()?
+ *
+ * Implementing those functions following their counterparts list_empty() and
+ * list_first_entry() is not advisable because they lead to subtle race
+ * conditions as the following snippet shows:
+ *
+ * if (!list_empty_rcu(mylist)) {
+ * struct foo *bar = list_first_entry_rcu(mylist, struct foo,
list_member);
+ * do_something(bar);
+ * }
+ *
+ * The list may not be empty when list_empty_rcu checks it, but it may be when
+ * list_first_entry_rcu rereads the ->next pointer.
+ *
+ * Rereading the ->next pointer is not a problem for list_empty() and
+ * list_first_entry() because they would be protected by a lock that blocks
+ * writers.
+ *
+ * See list_first_or_null_rcu for an alternative.
+ */
+
+/**
+ * list_first_or_null_rcu - get the first element from a list

  * @ptr:        the list head to take the element from.
  * @type:       the type of the struct this is embedded in.
  * @member:     the name of the list_struct within the struct.

*
- * Note, that list is expected to be not empty.
+ * Note that if the list is empty, it returns NULL.
*
* This primitive may safely run concurrently with the _rcu
list-mutation
* primitives such as list_add_rcu() as long as it's guarded by
rcu_read_lock().
*/
-#define list_first_entry_rcu(ptr, type, member) \
- list_entry_rcu((ptr)->next, type, member)
+#define list_first_or_null_rcu(ptr, type, member) \
+ ({struct list_head *__ptr = (ptr); \
+ struct list_head __rcu *__next = list_next_rcu(__ptr); \
+ likely(__ptr != __next) ? container_of(__next, type, member) : NULL;
\
+ })

/**
* list_for_each_entry_rcu - iterate over rcu list of given type

Paul E. McKenney

2012-04-12 00:30 UTC #1 lore raw

Quoted 4 lines · Michel Machado

Replaced list_first_entry_rcu() with list_first_or_null_rcu() because list_first_entry_rcu() is not safe as one can find in the comment that this patch also adds.

Quoted 8 lines

This patch incorporated Paul's suggestions to the previous version of this patch available here:
https://lkml.org/lkml/2012/4/2/536
This patch cannot break any upstream code because list_first_entry_rcu is not being used anywhere in the kernel (tested with grep(1)), and external code that uses it is probably broken already.

Thank you, Michel, I have queued this.

However, in the future, could you please configure your email client to avoid breaking lines and could you please also run scripts/checkpatch.pl on future patches? Applying your patch took some hand-editing to merge the broken lines and to remove trailing spaces on lines.

Thanx, Paul

Quoted 72 lines

Signed-off-by Michel Machado <[email protected]>
CC "Paul E. McKenney" <[email protected]>
CC Dipankar Sarma <[email protected]>
---
include/linux/rculist.h +3 -1
index d079290..ef5da30 100644
@@ -228,18 +228,43 @@ static inline void list_splice_init_rcu(struct
 list_head *list,
 	})
 
 /**
- * list_first_entry_rcu - get the first element from a list
+ * Where are list_empty_rcu() and list_first_entry_rcu()?
+ *
+ * Implementing those functions following their counterparts
list_empty() and
+ * list_first_entry() is not advisable because they lead to subtle race
+ * conditions as the following snippet shows:
+ *
+ * if (!list_empty_rcu(mylist)) {
+ * struct foo *bar = list_first_entry_rcu(mylist, struct foo,
list_member);
+ * do_something(bar);
+ * }
+ *
+ * The list may not be empty when list_empty_rcu checks it, but it may be when
+ * list_first_entry_rcu rereads the ->next pointer.
+ *
+ * Rereading the ->next pointer is not a problem for list_empty() and
+ * list_first_entry() because they would be protected by a lock that blocks
+ * writers.
+ *
+ * See list_first_or_null_rcu for an alternative.
+ */
include/linux/rculist.h +4 -1
+
+/**
+ * list_first_or_null_rcu - get the first element from a list
  * @ptr:        the list head to take the element from.
  * @type:       the type of the struct this is embedded in.
  * @member:     the name of the list_struct within the struct.
  *
- * Note, that list is expected to be not empty.
+ * Note that if the list is empty, it returns NULL.
  *
  * This primitive may safely run concurrently with the _rcu
list-mutation
* primitives such as list_add_rcu() as long as it's guarded by
rcu_read_lock().
*/
include/linux/rculist.h +4 -2
-#define list_first_entry_rcu(ptr, type, member) \
-	list_entry_rcu((ptr)->next, type, member)
+#define list_first_or_null_rcu(ptr, type, member) \
+	({struct list_head *__ptr = (ptr); \
+	  struct list_head __rcu *__next = list_next_rcu(__ptr); \
+	  likely(__ptr != __next) ? container_of(__next, type, member) : NULL;
\
include/linux/rculist.h +1 -1
+	})
 
 /**
  * list_for_each_entry_rcu	-	iterate over rcu list of given type
 
--
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/

Michel Machado

author

2012-04-12 01:16 UTC #2 lore raw

Quoted 14 lines · Paul E. McKenney

Quoted 4 lines · Michel Machado
Replaced list_first_entry_rcu() with list_first_or_null_rcu() because list_first_entry_rcu() is not safe as one can find in the comment that this patch also adds.
Quoted 8 lines
This patch incorporated Paul's suggestions to the previous version of this patch available here:
https://lkml.org/lkml/2012/4/2/536
This patch cannot break any upstream code because list_first_entry_rcu is not being used anywhere in the kernel (tested with grep(1)), and external code that uses it is probably broken already.

Quoted 9 lines

Thank you, Michel, I have queued this.
However, in the future, could you please configure your email client to avoid breaking lines and could you please also run scripts/checkpatch.pl on future patches? Applying your patch took some hand-editing to merge the broken lines and to remove trailing spaces on lines.
Thanx, Paul

Sorry for the extra work, I'll pay more attention next time.

[ ]'s
Michel Machado

Quoted 73 lines

Quoted 72 lines
Signed-off-by Michel Machado <[email protected]>
CC "Paul E. McKenney" <[email protected]>
CC Dipankar Sarma <[email protected]>
---
include/linux/rculist.h +3 -1
index d079290..ef5da30 100644
@@ -228,18 +228,43 @@ static inline void list_splice_init_rcu(struct
 list_head *list,
 	})
 
 /**
- * list_first_entry_rcu - get the first element from a list
+ * Where are list_empty_rcu() and list_first_entry_rcu()?
+ *
+ * Implementing those functions following their counterparts
list_empty() and
+ * list_first_entry() is not advisable because they lead to subtle race
+ * conditions as the following snippet shows:
+ *
+ * if (!list_empty_rcu(mylist)) {
+ * struct foo *bar = list_first_entry_rcu(mylist, struct foo,
list_member);
+ * do_something(bar);
+ * }
+ *
+ * The list may not be empty when list_empty_rcu checks it, but it may be when
+ * list_first_entry_rcu rereads the ->next pointer.
+ *
+ * Rereading the ->next pointer is not a problem for list_empty() and
+ * list_first_entry() because they would be protected by a lock that blocks
+ * writers.
+ *
+ * See list_first_or_null_rcu for an alternative.
+ */
include/linux/rculist.h +4 -1
+
+/**
+ * list_first_or_null_rcu - get the first element from a list
  * @ptr:        the list head to take the element from.
  * @type:       the type of the struct this is embedded in.
  * @member:     the name of the list_struct within the struct.
  *
- * Note, that list is expected to be not empty.
+ * Note that if the list is empty, it returns NULL.
  *
  * This primitive may safely run concurrently with the _rcu
list-mutation
* primitives such as list_add_rcu() as long as it's guarded by
rcu_read_lock().
*/
include/linux/rculist.h +4 -2
-#define list_first_entry_rcu(ptr, type, member) \
-	list_entry_rcu((ptr)->next, type, member)
+#define list_first_or_null_rcu(ptr, type, member) \
+	({struct list_head *__ptr = (ptr); \
+	  struct list_head __rcu *__next = list_next_rcu(__ptr); \
+	  likely(__ptr != __next) ? container_of(__next, type, member) : NULL;
\
include/linux/rculist.h +1 -1
+	})
 
 /**
  * list_for_each_entry_rcu	-	iterate over rcu list of given type
 
--
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/