rculist: Made list_first_entry_rcu usable

PATCH In review Michel Machado 2 participants 6 messages Apr 3, 2012 – Apr 9, 2012 RCU

Share & tools

Michel Machado

author

2012-04-03 01:42 UTC #0 lore raw

PATCH 1/1 rculist: Made list_first_entry_rcu usable

The macro list_first_entry_rcu assumed that the passed list is not empty as its counterpart list_first_entry does. However, one can test that a list is not empty with list_empty before calling list_first_entry, whereas neither exists list_empty_rcu, nor is advisable to add it as the example below shows.

Assuming that list_empty_rcu is available, one could write the following snippet:

if (!list_empty_rcu(mylist)) {
	struct foo *bar = list_first_entry_rcu(mylist, struct foo,
		list_member);
	do_something(bar);
}

The problem with this snippet is the following racing condition: 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.

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 Dipankar Sarma <[email protected]>

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

---
Please CC my e-mail address while replying this message because I don't subscribe this mailing list due to its high volume; thanks.

include/linux/rculist.h +0 -0

index d079290..866d3ec 100644
@@ -233,13 +233,16 @@ static inline void list_splice_init_rcu(struct

list_head *list,
* @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)
+ ({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-09 21:25 UTC #1 lore raw

Quoted 15 lines · Michel Machado

The macro list_first_entry_rcu assumed that the passed list is not empty as its counterpart list_first_entry does. However, one can test that a list is not empty with list_empty before calling list_first_entry, whereas neither exists list_empty_rcu, nor is advisable to add it as the example below shows.
Assuming that list_empty_rcu is available, one could write the following snippet:
if (!list_empty_rcu(mylist)) {
	struct foo *bar = list_first_entry_rcu(mylist, struct foo,
		list_member);
	do_something(bar);
}

Quoted 7 lines

The problem with this snippet is the following racing condition: 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.
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.

Hello, Michel,

Interesting point!

Are you intending to use list_first_entry_rcu()? If not, perhaps the best thing to do is to remove it.

Thanx, Paul

Quoted 36 lines

Signed-off-by Michel Machado <[email protected]>
CC Dipankar Sarma <[email protected]>
CC "Paul E. McKenney" <[email protected]>
---
Please CC my e-mail address while replying this message because I don't subscribe this mailing list due to its high volume; thanks.
include/linux/rculist.h +1 -1
index d079290..866d3ec 100644
@@ -233,13 +233,16 @@ static inline void list_splice_init_rcu(struct
 list_head *list,
  * @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) \
include/linux/rculist.h +3 -1
-	list_entry_rcu((ptr)->next, 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 -0
+	})
 
 /**
  * list_for_each_entry_rcu	-	iterate over rcu list of given type

Michel Machado

author

2012-04-09 22:08 UTC #2 lore raw

Quoted 24 lines · Paul E. McKenney

Quoted 15 lines · Michel Machado
The macro list_first_entry_rcu assumed that the passed list is not empty as its counterpart list_first_entry does. However, one can test that a list is not empty with list_empty before calling list_first_entry, whereas neither exists list_empty_rcu, nor is advisable to add it as the example below shows.
Assuming that list_empty_rcu is available, one could write the following snippet:
if (!list_empty_rcu(mylist)) {
	struct foo *bar = list_first_entry_rcu(mylist, struct foo,
		list_member);
	do_something(bar);
}
Quoted 7 lines
The problem with this snippet is the following racing condition: 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.
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 8 lines

Hello, Michel,
Interesting point!
Are you intending to use list_first_entry_rcu()? If not, perhaps the best thing to do is to remove it.
Thanx, Paul

Hi Paul,

I'd rather keep list_first_entry_rcu(). I've already used it twice in
the project I'm working on
(https://github.com/AltraMayor/XIA-for-Linux), and I expect to submit this work upstream once it reaches reasonable quality as you can check in the roadmap available here:

https://github.com/AltraMayor/XIA-for-Linux/wiki/Roadmap#wiki-Making_into_Linus_source_tree

Not to mention that, given the subtlety of the problem, removing
list_first_entry_rcu() may introduce the same bug whenever someone tries to mimic list_first_entry(), and having it in the kernel helps to guide those with an example.

[ ]'s
Michel Machado

Quoted 38 lines

Quoted 37 lines
Signed-off-by Michel Machado <[email protected]>
CC Dipankar Sarma <[email protected]>
CC "Paul E. McKenney" <[email protected]>
---
Please CC my e-mail address while replying this message because I don't subscribe this mailing list due to its high volume; thanks.
include/linux/rculist.h +1 -1
index d079290..866d3ec 100644
@@ -233,13 +233,16 @@ static inline void list_splice_init_rcu(struct
 list_head *list,
  * @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) \
include/linux/rculist.h +3 -1
-	list_entry_rcu((ptr)->next, 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 -0
+	})
 
 /**
  * list_for_each_entry_rcu	-	iterate over rcu list of given type

Paul E. McKenney

2012-04-09 22:23 UTC #3 lore raw

Quoted 42 lines · Michel Machado

Quoted 24 lines · Paul E. McKenney
Quoted 15 lines · Michel Machado
The macro list_first_entry_rcu assumed that the passed list is not empty as its counterpart list_first_entry does. However, one can test that a list is not empty with list_empty before calling list_first_entry, whereas neither exists list_empty_rcu, nor is advisable to add it as the example below shows.
Assuming that list_empty_rcu is available, one could write the following snippet:
if (!list_empty_rcu(mylist)) {
	struct foo *bar = list_first_entry_rcu(mylist, struct foo,
		list_member);
	do_something(bar);
}
Quoted 7 lines
The problem with this snippet is the following racing condition: 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.
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 8 lines
Hello, Michel,
Interesting point!
Are you intending to use list_first_entry_rcu()? If not, perhaps the best thing to do is to remove it.
Thanx, Paul
Hi Paul,
I'd rather keep list_first_entry_rcu(). I've already used it twice in
the project I'm working on
(https://github.com/AltraMayor/XIA-for-Linux), and I expect to submit this work upstream once it reaches reasonable quality as you can check in the roadmap available here:

Quoted 6 lines

https://github.com/AltraMayor/XIA-for-Linux/wiki/Roadmap#wiki-Making_into_Linus_source_tree
Not to mention that, given the subtlety of the problem, removing
list_first_entry_rcu() may introduce the same bug whenever someone tries to mimic list_first_entry(), and having it in the kernel helps to guide those with an example.

Actually, list_first_entry_rcu() really does mimic list_first_entry() from what I can see. Both of them require that the list be non-empty, which can be checked via !list_empty().

Or is list_first_entry() being converted to check for an empty list?

We really do need both list_first_entry() and list_first_entry_rcu() to have the same semantics on empty lists, I am sure you would agree.

Thanx, Paul

Quoted 42 lines

[ ]'s
Michel Machado
Quoted 38 lines
Quoted 37 lines
Signed-off-by Michel Machado <[email protected]>
CC Dipankar Sarma <[email protected]>
CC "Paul E. McKenney" <[email protected]>
---
Please CC my e-mail address while replying this message because I don't subscribe this mailing list due to its high volume; thanks.
include/linux/rculist.h +1 -1
index d079290..866d3ec 100644
@@ -233,13 +233,16 @@ static inline void list_splice_init_rcu(struct
 list_head *list,
  * @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) \
include/linux/rculist.h +3 -1
-	list_entry_rcu((ptr)->next, 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 -0
+	})
 
 /**
  * list_for_each_entry_rcu	-	iterate over rcu list of given type

Michel Machado

author

2012-04-09 22:42 UTC #4 lore raw

Quoted 54 lines · Paul E. McKenney

Quoted 42 lines · Michel Machado
Quoted 24 lines · Paul E. McKenney
Quoted 15 lines · Michel Machado
The macro list_first_entry_rcu assumed that the passed list is not empty as its counterpart list_first_entry does. However, one can test that a list is not empty with list_empty before calling list_first_entry, whereas neither exists list_empty_rcu, nor is advisable to add it as the example below shows.
Assuming that list_empty_rcu is available, one could write the following snippet:
if (!list_empty_rcu(mylist)) {
	struct foo *bar = list_first_entry_rcu(mylist, struct foo,
		list_member);
	do_something(bar);
}
Quoted 7 lines
The problem with this snippet is the following racing condition: 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.
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 8 lines
Hello, Michel,
Interesting point!
Are you intending to use list_first_entry_rcu()? If not, perhaps the best thing to do is to remove it.
Thanx, Paul
Hi Paul,
I'd rather keep list_first_entry_rcu(). I've already used it twice in
the project I'm working on
(https://github.com/AltraMayor/XIA-for-Linux), and I expect to submit this work upstream once it reaches reasonable quality as you can check in the roadmap available here:
Quoted 6 lines
https://github.com/AltraMayor/XIA-for-Linux/wiki/Roadmap#wiki-Making_into_Linus_source_tree
Not to mention that, given the subtlety of the problem, removing
list_first_entry_rcu() may introduce the same bug whenever someone tries to mimic list_first_entry(), and having it in the kernel helps to guide those with an example.
Actually, list_first_entry_rcu() really does mimic list_first_entry() from what I can see. Both of them require that the list be non-empty, which can be checked via !list_empty().

Quoted 6 lines

Or is list_first_entry() being converted to check for an empty list?
We really do need both list_first_entry() and list_first_entry_rcu() to have the same semantics on empty lists, I am sure you would agree.
Thanx, Paul

Yes, the current list_first_entry_rcu() does mimic list_first_entry(), and that's the reason the problem is there. A list without RCU readers would have list_empty() _and_ list_first_entry() protected by a lock, so the reread of the ->next pointer isn't an issue there, but it's not the case for a list with RCU readers.

I agree that having the same semantics for both is the perfect solution, but list_first_entry() already has many users in the kernel. My patch is a compromise to not have this bug lurking around, but I see that the names may cause confusion. Would you be comfortable with removing the current list_first_entry_rcu(), and adding my version renamed to list_first_entry_if_not_empty_rcu() (or a shorter name)?

Quoted 44 lines

Quoted 43 lines
[ ]'s
Michel Machado
Quoted 38 lines
Quoted 37 lines
Signed-off-by Michel Machado <[email protected]>
CC Dipankar Sarma <[email protected]>
CC "Paul E. McKenney" <[email protected]>
---
Please CC my e-mail address while replying this message because I don't subscribe this mailing list due to its high volume; thanks.
include/linux/rculist.h +1 -1
index d079290..866d3ec 100644
@@ -233,13 +233,16 @@ static inline void list_splice_init_rcu(struct
 list_head *list,
  * @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) \
include/linux/rculist.h +3 -1
-	list_entry_rcu((ptr)->next, 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 -0
+	})
 
 /**
  * list_for_each_entry_rcu	-	iterate over rcu list of given type

Paul E. McKenney

2012-04-09 23:12 UTC #5 lore raw

Quoted 68 lines · Michel Machado

Quoted 54 lines · Paul E. McKenney
Quoted 42 lines · Michel Machado
Quoted 24 lines · Paul E. McKenney
Quoted 15 lines · Michel Machado
The macro list_first_entry_rcu assumed that the passed list is not empty as its counterpart list_first_entry does. However, one can test that a list is not empty with list_empty before calling list_first_entry, whereas neither exists list_empty_rcu, nor is advisable to add it as the example below shows.
Assuming that list_empty_rcu is available, one could write the following snippet:
if (!list_empty_rcu(mylist)) {
	struct foo *bar = list_first_entry_rcu(mylist, struct foo,
		list_member);
	do_something(bar);
}
Quoted 7 lines
The problem with this snippet is the following racing condition: 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.
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 8 lines
Hello, Michel,
Interesting point!
Are you intending to use list_first_entry_rcu()? If not, perhaps the best thing to do is to remove it.
Thanx, Paul
Hi Paul,
I'd rather keep list_first_entry_rcu(). I've already used it twice in
the project I'm working on
(https://github.com/AltraMayor/XIA-for-Linux), and I expect to submit this work upstream once it reaches reasonable quality as you can check in the roadmap available here:
Quoted 6 lines
https://github.com/AltraMayor/XIA-for-Linux/wiki/Roadmap#wiki-Making_into_Linus_source_tree
Not to mention that, given the subtlety of the problem, removing
list_first_entry_rcu() may introduce the same bug whenever someone tries to mimic list_first_entry(), and having it in the kernel helps to guide those with an example.
Actually, list_first_entry_rcu() really does mimic list_first_entry() from what I can see. Both of them require that the list be non-empty, which can be checked via !list_empty().
Quoted 6 lines
Or is list_first_entry() being converted to check for an empty list?
We really do need both list_first_entry() and list_first_entry_rcu() to have the same semantics on empty lists, I am sure you would agree.
Thanx, Paul
Yes, the current list_first_entry_rcu() does mimic list_first_entry(), and that's the reason the problem is there. A list without RCU readers would have list_empty() _and_ list_first_entry() protected by a lock, so the reread of the ->next pointer isn't an issue there, but it's not the case for a list with RCU readers.

Quoted 6 lines

I agree that having the same semantics for both is the perfect solution, but list_first_entry() already has many users in the kernel. My patch is a compromise to not have this bug lurking around, but I see that the names may cause confusion. Would you be comfortable with removing the current list_first_entry_rcu(), and adding my version renamed to list_first_entry_if_not_empty_rcu() (or a shorter name)?

Dropping list_first_entry_rcu() in favor of something that reliably checks for NULL makes sense, but yes, a shorter name would be good. ;-)

The comment headers should document the problem as well.

Thanx, Paul

Quoted 44 lines

Quoted 43 lines
Quoted 42 lines
[ ]'s
Michel Machado
Quoted 38 lines
Quoted 37 lines
Signed-off-by Michel Machado <[email protected]>
CC Dipankar Sarma <[email protected]>
CC "Paul E. McKenney" <[email protected]>
---
Please CC my e-mail address while replying this message because I don't subscribe this mailing list due to its high volume; thanks.
include/linux/rculist.h +1 -1
index d079290..866d3ec 100644
@@ -233,13 +233,16 @@ static inline void list_splice_init_rcu(struct
 list_head *list,
  * @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) \
include/linux/rculist.h +3 -1
-	list_entry_rcu((ptr)->next, 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 -0
+	})
 
 /**
  * list_for_each_entry_rcu	-	iterate over rcu list of given type