Skip to contentSkip to conversation

rcu: Add necessary WRITE_ONCE()

PATCH In review Alan Huang 3 participants 7 messages Jun 20, 2023 – Jun 26, 2023 RCU

lore
Share & tools
lore

Alan Huang

author
#0 lore raw

PATCH v2 1/1 rcu: Add necessary WRITE_ONCE()

Commit c54a2744497d("list: Add hlist_unhashed_lockless()") and commit 860c8802ace1("rcu: Use WRITE_ONCE() for assignments to ->pprev for hlist_nulls") added various WRITE_ONCE() to pair with the READ_ONCE() in hlist_unhashed_lockless(), but there are still some places where WRITE_ONCE() was not added, this commit adds that.

Also add WRITE_ONCE() to pair with the READ_ONCE() in hlist_empty().

---
Changelog:
V1 -> V2:
Add WRITE_ONCE in hlist_del_init to pair with READ_ONCE in hlist_unhashed_lockless.

 include/linux/list.h          | 9 +++++----
 include/linux/list_nulls.h    | 2 +-
 include/linux/rculist_nulls.h | 2 +-
 3 files changed, 7 insertions(+), 6 deletions(-)
include/linux/list.h +5 -4
index ac366958ea..3a29b95bfe 100644
@@ -912,7 +912,7 @@ static inline void hlist_del(struct hlist_node *n)
 {
 	__hlist_del(n);
 	n->next = LIST_POISON1;
-	n->pprev = LIST_POISON2;
+	WRITE_ONCE(n->pprev, LIST_POISON2);
 }
 
 /**
@@ -925,7 +925,8 @@ static inline void hlist_del_init(struct hlist_node *n)
 {
 	if (!hlist_unhashed(n)) {
 		__hlist_del(n);
-		INIT_HLIST_NODE(n);
+		n->next = NULL;
+		WRITE_ONCE(n->pprev, NULL);
 	}
 }
 
@@ -1026,8 +1027,8 @@ static inline void hlist_move_list(struct hlist_head *old,
 {
 	new->first = old->first;
 	if (new->first)
-		new->first->pprev = &new->first;
-	old->first = NULL;
+		WRITE_ONCE(new->first->pprev, &new->first);
+	WRITE_ONCE(old->first, NULL);
 }
 
 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
include/linux/list_nulls.h +1 -1
index fa6e8471bd..b63b0589fa 100644
@@ -95,7 +95,7 @@ static inline void hlist_nulls_add_head(struct hlist_nulls_node *n,
 
 	n->next = first;
 	WRITE_ONCE(n->pprev, &h->first);
-	h->first = n;
+	WRITE_ONCE(h->first, n);
 	if (!is_a_nulls(first))
 		WRITE_ONCE(first->pprev, &n->next);
 }
include/linux/rculist_nulls.h +1 -1
index ba4c00dd80..c65121655b 100644
@@ -138,7 +138,7 @@ static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n,
 
 	if (last) {
 		n->next = last->next;
-		n->pprev = &last->next;
+		WRITE_ONCE(n->pprev, &last->next);
 		rcu_assign_pointer(hlist_nulls_next_rcu(last), n);
 	} else {
 		hlist_nulls_add_head_rcu(n, h);
Signature · 1 line
2.34.1
maintainer
#1 lore raw
Quoted 9 lines · Alan Huang

Commit c54a2744497d("list: Add hlist_unhashed_lockless()") and commit 860c8802ace1("rcu: Use WRITE_ONCE() for assignments to ->pprev for hlist_nulls") added various WRITE_ONCE() to pair with the READ_ONCE() in hlist_unhashed_lockless(), but there are still some places where WRITE_ONCE() was not added, this commit adds that.

Also add WRITE_ONCE() to pair with the READ_ONCE() in hlist_empty().

On hlist_nulls_add_tail_rcu(), good catch, thank you!

On the others, are there really cases where a lockless read races with the update? At first glance, that sounds like a usage bug. For example, as I understand it, when you use something like hlist_del(), you are supposed to ensure that there are no concurrent readers. Which is the point of the assignment of the special value LIST_POISON2, right?

Or is there some use case that I am missing?

If I am not missing something, then switching the non-RCU APIs to WRITE_ONCE() would be a step backwards, because it would make it harder for tools like KCSAN to find bugs.

Thanx, Paul

Quoted 74 lines

---
Changelog:
V1 -> V2:
Add WRITE_ONCE in hlist_del_init to pair with READ_ONCE in hlist_unhashed_lockless.

 include/linux/list.h          | 9 +++++----
 include/linux/list_nulls.h    | 2 +-
 include/linux/rculist_nulls.h | 2 +-
 3 files changed, 7 insertions(+), 6 deletions(-)
include/linux/list.h +5 -4
index ac366958ea..3a29b95bfe 100644
@@ -912,7 +912,7 @@ static inline void hlist_del(struct hlist_node *n)
 {
 	__hlist_del(n);
 	n->next = LIST_POISON1;
-	n->pprev = LIST_POISON2;
+	WRITE_ONCE(n->pprev, LIST_POISON2);
 }
 
 /**
@@ -925,7 +925,8 @@ static inline void hlist_del_init(struct hlist_node *n)
 {
 	if (!hlist_unhashed(n)) {
 		__hlist_del(n);
-		INIT_HLIST_NODE(n);
+		n->next = NULL;
+		WRITE_ONCE(n->pprev, NULL);
 	}
 }
 
@@ -1026,8 +1027,8 @@ static inline void hlist_move_list(struct hlist_head *old,
 {
 	new->first = old->first;
 	if (new->first)
-		new->first->pprev = &new->first;
-	old->first = NULL;
+		WRITE_ONCE(new->first->pprev, &new->first);
+	WRITE_ONCE(old->first, NULL);
 }
 
 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
include/linux/list_nulls.h +1 -1
index fa6e8471bd..b63b0589fa 100644
@@ -95,7 +95,7 @@ static inline void hlist_nulls_add_head(struct hlist_nulls_node *n,
 
 	n->next = first;
 	WRITE_ONCE(n->pprev, &h->first);
-	h->first = n;
+	WRITE_ONCE(h->first, n);
 	if (!is_a_nulls(first))
 		WRITE_ONCE(first->pprev, &n->next);
 }
include/linux/rculist_nulls.h +1 -1
index ba4c00dd80..c65121655b 100644
@@ -138,7 +138,7 @@ static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n,
 
 	if (last) {
 		n->next = last->next;
-		n->pprev = &last->next;
+		WRITE_ONCE(n->pprev, &last->next);
 		rcu_assign_pointer(hlist_nulls_next_rcu(last), n);
 	} else {
 		hlist_nulls_add_head_rcu(n, h);
Signature · 1 line
2.34.1
author
#2 lore raw
Quoted 14 lines

2023年6月21日 06:26,Paul E. McKenney <[email protected]> 写道:

Quoted 9 lines · Alan Huang

Commit c54a2744497d("list: Add hlist_unhashed_lockless()") and commit 860c8802ace1("rcu: Use WRITE_ONCE() for assignments to ->pprev for hlist_nulls") added various WRITE_ONCE() to pair with the READ_ONCE() in hlist_unhashed_lockless(), but there are still some places where WRITE_ONCE() was not added, this commit adds that.

Also add WRITE_ONCE() to pair with the READ_ONCE() in hlist_empty().

Quoted 7 lines

On hlist_nulls_add_tail_rcu(), good catch, thank you!

On the others, are there really cases where a lockless read races with the update? At first glance, that sounds like a usage bug. For example, as I understand it, when you use something like hlist_del(), you are supposed to ensure that there are no concurrent readers. Which is the point of the assignment of the special value LIST_POISON2, right?

Do you mean there are cases where a lockless read races with hlist_add_head/hlist_add_before hlist_add_behind/__hlist_del, but there is no real case where a lockless read races with the hlist_del_init/hlist_del hlist_move_list?

There may be no real case where a lockless read races with the hlist_del_init/hlist_del hlist_move_list. But for the sake of completeness, I added those WRITE_ONCE, after all, if there is WRITE_ONCE in __hlist_del, why not add WRITE_ONCE in its caller, like hlist_del()?

Thanks,
Alan

Quoted 83 lines

Or is there some use case that I am missing?

If I am not missing something, then switching the non-RCU APIs to WRITE_ONCE() would be a step backwards, because it would make it harder for tools like KCSAN to find bugs.

Thanx, Paul

Quoted 74 lines

---
Changelog:
V1 -> V2:
Add WRITE_ONCE in hlist_del_init to pair with READ_ONCE in hlist_unhashed_lockless.

include/linux/list.h          | 9 +++++----
include/linux/list_nulls.h    | 2 +-
include/linux/rculist_nulls.h | 2 +-
3 files changed, 7 insertions(+), 6 deletions(-)
include/linux/list.h +5 -4
index ac366958ea..3a29b95bfe 100644
@@ -912,7 +912,7 @@ static inline void hlist_del(struct hlist_node *n)
 {
 __hlist_del(n);
 n->next = LIST_POISON1;
- n->pprev = LIST_POISON2;
+ WRITE_ONCE(n->pprev, LIST_POISON2);
 }
 
 /**
@@ -925,7 +925,8 @@ static inline void hlist_del_init(struct hlist_node *n)
 {
 if (!hlist_unhashed(n)) {
 __hlist_del(n);
- INIT_HLIST_NODE(n);
+ n->next = NULL;
+ WRITE_ONCE(n->pprev, NULL);
 }
 }
 
@@ -1026,8 +1027,8 @@ static inline void hlist_move_list(struct hlist_head *old,
 {
 new->first = old->first;
 if (new->first)
- new->first->pprev = &new->first;
- old->first = NULL;
+ WRITE_ONCE(new->first->pprev, &new->first);
+ WRITE_ONCE(old->first, NULL);
 }
 
 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
include/linux/list_nulls.h +1 -1
index fa6e8471bd..b63b0589fa 100644
@@ -95,7 +95,7 @@ static inline void hlist_nulls_add_head(struct hlist_nulls_node *n,
 
 n->next = first;
 WRITE_ONCE(n->pprev, &h->first);
- h->first = n;
+ WRITE_ONCE(h->first, n);
 if (!is_a_nulls(first))
 WRITE_ONCE(first->pprev, &n->next);
 }
include/linux/rculist_nulls.h +1 -1
index ba4c00dd80..c65121655b 100644
@@ -138,7 +138,7 @@ static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n,
 
 if (last) {
 n->next = last->next;
- n->pprev = &last->next;
+ WRITE_ONCE(n->pprev, &last->next);
 rcu_assign_pointer(hlist_nulls_next_rcu(last), n);
 } else {
 hlist_nulls_add_head_rcu(n, h);
Signature · 1 line
2.34.1
maintainer
#3 lore raw
Quoted 22 lines · Alan Huang
Quoted 14 lines

2023年6月21日 06:26,Paul E. McKenney <[email protected]> 写道:

Quoted 9 lines · Alan Huang

Commit c54a2744497d("list: Add hlist_unhashed_lockless()") and commit 860c8802ace1("rcu: Use WRITE_ONCE() for assignments to ->pprev for hlist_nulls") added various WRITE_ONCE() to pair with the READ_ONCE() in hlist_unhashed_lockless(), but there are still some places where WRITE_ONCE() was not added, this commit adds that.

Also add WRITE_ONCE() to pair with the READ_ONCE() in hlist_empty().

Quoted 7 lines

On hlist_nulls_add_tail_rcu(), good catch, thank you!

On the others, are there really cases where a lockless read races with the update? At first glance, that sounds like a usage bug. For example, as I understand it, when you use something like hlist_del(), you are supposed to ensure that there are no concurrent readers. Which is the point of the assignment of the special value LIST_POISON2, right?

Quoted 7 lines

Do you mean there are cases where a lockless read races with hlist_add_head/hlist_add_before hlist_add_behind/__hlist_del, but there is no real case where a lockless read races with the hlist_del_init/hlist_del hlist_move_list?

There may be no real case where a lockless read races with the hlist_del_init/hlist_del hlist_move_list. But for the sake of completeness, I added those WRITE_ONCE, after all, if there is WRITE_ONCE in __hlist_del, why not add WRITE_ONCE in its caller, like hlist_del()?

You might well have located a larger issue. We want to be able to use KCSAN to find unintended data races, but as you noted, there might be different requirements for RCU-protected linked lists and for lock-protected linked lists. If there are, then there is probably existing linked-list code that is using the wrong primitive, for example, using (or failing to use) the one that Eric Dumazet provided. For example, mismatched API usage might be causing the differences in uses of _ONCE() primitives that you are calling out.

Would you be interested in digging into this?

You will of course need to be able to build and run kernels with KCSAN enabled, which is not hard to do given a laptop that can build a kernel and run a guest OS.

Thanx, Paul

Quoted 87 lines

Thanks,
Alan

Quoted 83 lines

Or is there some use case that I am missing?

If I am not missing something, then switching the non-RCU APIs to WRITE_ONCE() would be a step backwards, because it would make it harder for tools like KCSAN to find bugs.

Thanx, Paul

Quoted 74 lines

---
Changelog:
V1 -> V2:
Add WRITE_ONCE in hlist_del_init to pair with READ_ONCE in hlist_unhashed_lockless.

include/linux/list.h          | 9 +++++----
include/linux/list_nulls.h    | 2 +-
include/linux/rculist_nulls.h | 2 +-
3 files changed, 7 insertions(+), 6 deletions(-)
include/linux/list.h +5 -4
index ac366958ea..3a29b95bfe 100644
@@ -912,7 +912,7 @@ static inline void hlist_del(struct hlist_node *n)
 {
 __hlist_del(n);
 n->next = LIST_POISON1;
- n->pprev = LIST_POISON2;
+ WRITE_ONCE(n->pprev, LIST_POISON2);
 }
 
 /**
@@ -925,7 +925,8 @@ static inline void hlist_del_init(struct hlist_node *n)
 {
 if (!hlist_unhashed(n)) {
 __hlist_del(n);
- INIT_HLIST_NODE(n);
+ n->next = NULL;
+ WRITE_ONCE(n->pprev, NULL);
 }
 }
 
@@ -1026,8 +1027,8 @@ static inline void hlist_move_list(struct hlist_head *old,
 {
 new->first = old->first;
 if (new->first)
- new->first->pprev = &new->first;
- old->first = NULL;
+ WRITE_ONCE(new->first->pprev, &new->first);
+ WRITE_ONCE(old->first, NULL);
 }
 
 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
include/linux/list_nulls.h +1 -1
index fa6e8471bd..b63b0589fa 100644
@@ -95,7 +95,7 @@ static inline void hlist_nulls_add_head(struct hlist_nulls_node *n,
 
 n->next = first;
 WRITE_ONCE(n->pprev, &h->first);
- h->first = n;
+ WRITE_ONCE(h->first, n);
 if (!is_a_nulls(first))
 WRITE_ONCE(first->pprev, &n->next);
 }
include/linux/rculist_nulls.h +1 -1
index ba4c00dd80..c65121655b 100644
@@ -138,7 +138,7 @@ static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n,
 
 if (last) {
 n->next = last->next;
- n->pprev = &last->next;
+ WRITE_ONCE(n->pprev, &last->next);
 rcu_assign_pointer(hlist_nulls_next_rcu(last), n);
 } else {
 hlist_nulls_add_head_rcu(n, h);
Signature · 1 line
2.34.1
author
#4 lore raw
Quoted 34 lines

2023年6月23日 下午1:17,Paul E. McKenney <[email protected]> 写道:

Quoted 22 lines · Alan Huang
Quoted 14 lines

2023年6月21日 06:26,Paul E. McKenney <[email protected]> 写道:

Quoted 9 lines · Alan Huang

Commit c54a2744497d("list: Add hlist_unhashed_lockless()") and commit 860c8802ace1("rcu: Use WRITE_ONCE() for assignments to ->pprev for hlist_nulls") added various WRITE_ONCE() to pair with the READ_ONCE() in hlist_unhashed_lockless(), but there are still some places where WRITE_ONCE() was not added, this commit adds that.

Also add WRITE_ONCE() to pair with the READ_ONCE() in hlist_empty().

Quoted 7 lines

On hlist_nulls_add_tail_rcu(), good catch, thank you!

On the others, are there really cases where a lockless read races with the update? At first glance, that sounds like a usage bug. For example, as I understand it, when you use something like hlist_del(), you are supposed to ensure that there are no concurrent readers. Which is the point of the assignment of the special value LIST_POISON2, right?

Quoted 7 lines

Do you mean there are cases where a lockless read races with hlist_add_head/hlist_add_before hlist_add_behind/__hlist_del, but there is no real case where a lockless read races with the hlist_del_init/hlist_del hlist_move_list?

There may be no real case where a lockless read races with the hlist_del_init/hlist_del hlist_move_list. But for the sake of completeness, I added those WRITE_ONCE, after all, if there is WRITE_ONCE in __hlist_del, why not add WRITE_ONCE in its caller, like hlist_del()?

Quoted 8 lines

You might well have located a larger issue. We want to be able to use KCSAN to find unintended data races, but as you noted, there might be different requirements for RCU-protected linked lists and for lock-protected linked lists. If there are, then there is probably existing linked-list code that is using the wrong primitive, for example, using (or failing to use) the one that Eric Dumazet provided. For example, mismatched API usage might be causing the differences in uses of _ONCE() primitives that you are calling out.

I noticed a thread:

https://lore.kernel.org/lkml/[email protected]/

It seems like Will wanted to remove that hlist_unhashed_lockless()? But I can’t find any further updates.

Will: Can you tell me what happened later?

Quoted 2 lines

Would you be interested in digging into this?

I’d like to.

Quoted 4 lines

You will of course need to be able to build and run kernels with KCSAN enabled, which is not hard to do given a laptop that can build a kernel and run a guest OS.

I’ll do that, :)

Quoted 88 lines

Thanx, Paul

Quoted 85 lines

Thanks,
Alan

Quoted 82 lines

Or is there some use case that I am missing?

If I am not missing something, then switching the non-RCU APIs to WRITE_ONCE() would be a step backwards, because it would make it harder for tools like KCSAN to find bugs.

Thanx, Paul

Quoted 73 lines

---
Changelog:
V1 -> V2:
Add WRITE_ONCE in hlist_del_init to pair with READ_ONCE in hlist_unhashed_lockless.

include/linux/list.h          | 9 +++++----
include/linux/list_nulls.h    | 2 +-
include/linux/rculist_nulls.h | 2 +-
3 files changed, 7 insertions(+), 6 deletions(-)
include/linux/list.h +5 -4
index ac366958ea..3a29b95bfe 100644
@@ -912,7 +912,7 @@ static inline void hlist_del(struct hlist_node *n)
 {
 __hlist_del(n);
 n->next = LIST_POISON1;
- n->pprev = LIST_POISON2;
+ WRITE_ONCE(n->pprev, LIST_POISON2);
 }
 
 /**
@@ -925,7 +925,8 @@ static inline void hlist_del_init(struct hlist_node *n)
 {
 if (!hlist_unhashed(n)) {
 __hlist_del(n);
- INIT_HLIST_NODE(n);
+ n->next = NULL;
+ WRITE_ONCE(n->pprev, NULL);
 }
 }
 
@@ -1026,8 +1027,8 @@ static inline void hlist_move_list(struct hlist_head *old,
 {
 new->first = old->first;
 if (new->first)
- new->first->pprev = &new->first;
- old->first = NULL;
+ WRITE_ONCE(new->first->pprev, &new->first);
+ WRITE_ONCE(old->first, NULL);
 }
 
 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
include/linux/list_nulls.h +1 -1
index fa6e8471bd..b63b0589fa 100644
@@ -95,7 +95,7 @@ static inline void hlist_nulls_add_head(struct hlist_nulls_node *n,
 
 n->next = first;
 WRITE_ONCE(n->pprev, &h->first);
- h->first = n;
+ WRITE_ONCE(h->first, n);
 if (!is_a_nulls(first))
 WRITE_ONCE(first->pprev, &n->next);
 }
include/linux/rculist_nulls.h +1 -1
index ba4c00dd80..c65121655b 100644
@@ -138,7 +138,7 @@ static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n,
 
 if (last) {
 n->next = last->next;
- n->pprev = &last->next;
+ WRITE_ONCE(n->pprev, &last->next);
 rcu_assign_pointer(hlist_nulls_next_rcu(last), n);
 } else {
 hlist_nulls_add_head_rcu(n, h);
Signature · 1 line
2.34.1
maintainer
#5 lore raw
Quoted 43 lines · Alan Huang
Quoted 34 lines

2023年6月23日 下午1:17,Paul E. McKenney <[email protected]> 写道:

Quoted 22 lines · Alan Huang
Quoted 14 lines

2023年6月21日 06:26,Paul E. McKenney <[email protected]> 写道:

Quoted 9 lines · Alan Huang

Commit c54a2744497d("list: Add hlist_unhashed_lockless()") and commit 860c8802ace1("rcu: Use WRITE_ONCE() for assignments to ->pprev for hlist_nulls") added various WRITE_ONCE() to pair with the READ_ONCE() in hlist_unhashed_lockless(), but there are still some places where WRITE_ONCE() was not added, this commit adds that.

Also add WRITE_ONCE() to pair with the READ_ONCE() in hlist_empty().

Quoted 7 lines

On hlist_nulls_add_tail_rcu(), good catch, thank you!

On the others, are there really cases where a lockless read races with the update? At first glance, that sounds like a usage bug. For example, as I understand it, when you use something like hlist_del(), you are supposed to ensure that there are no concurrent readers. Which is the point of the assignment of the special value LIST_POISON2, right?

Quoted 7 lines

Do you mean there are cases where a lockless read races with hlist_add_head/hlist_add_before hlist_add_behind/__hlist_del, but there is no real case where a lockless read races with the hlist_del_init/hlist_del hlist_move_list?

There may be no real case where a lockless read races with the hlist_del_init/hlist_del hlist_move_list. But for the sake of completeness, I added those WRITE_ONCE, after all, if there is WRITE_ONCE in __hlist_del, why not add WRITE_ONCE in its caller, like hlist_del()?

Quoted 8 lines

You might well have located a larger issue. We want to be able to use KCSAN to find unintended data races, but as you noted, there might be different requirements for RCU-protected linked lists and for lock-protected linked lists. If there are, then there is probably existing linked-list code that is using the wrong primitive, for example, using (or failing to use) the one that Eric Dumazet provided. For example, mismatched API usage might be causing the differences in uses of _ONCE() primitives that you are calling out.

Quoted 6 lines

I noticed a thread:

https://lore.kernel.org/lkml/[email protected]/

It seems like Will wanted to remove that hlist_unhashed_lockless()? But I can’t find any further updates.

Indeed, the tricky part here is getting optimal data-race detection from KCSAN. You noted (I suspect correctly) that the _rcu() list_head functions want the ->next pointer marked with *_ONCE(), but that the other function might well instead want the ->prev or ->pprev pointer marked with *_ONCE(), with the ->next pointer accesses unmarked.

Working this out will require looking at the use cases. And running KCSAN. ;-)

Quoted 11 lines

Will: Can you tell me what happened later?

Quoted 1 line

Would you be interested in digging into this?

I’d like to.

Quoted 3 lines

You will of course need to be able to build and run kernels with KCSAN enabled, which is not hard to do given a laptop that can build a kernel and run a guest OS.

I’ll do that, :)

Very good, looking forward to seeing what you come up with!

Here are some LWN articles that should help, especially the last two:

https://lwn.net/Articles/793253/
"Who's afraid of a big bad optimizing compiler?"
https://lwn.net/Articles/799218/
"Calibrating your fear of big bad optimizing compilers"
https://lwn.net/Articles/816850/
"Concurrency bugs should fear the big bad data-race detector (part 1)"
https://lwn.net/Articles/816854/
"Concurrency bugs should fear the big bad data-race detector (part 2)"

Thanx, Paul

Quoted 86 lines
Quoted 85 lines
Quoted 85 lines

Thanks,
Alan

Quoted 82 lines

Or is there some use case that I am missing?

If I am not missing something, then switching the non-RCU APIs to WRITE_ONCE() would be a step backwards, because it would make it harder for tools like KCSAN to find bugs.

Thanx, Paul

Quoted 73 lines

---
Changelog:
V1 -> V2:
Add WRITE_ONCE in hlist_del_init to pair with READ_ONCE in hlist_unhashed_lockless.

include/linux/list.h          | 9 +++++----
include/linux/list_nulls.h    | 2 +-
include/linux/rculist_nulls.h | 2 +-
3 files changed, 7 insertions(+), 6 deletions(-)
include/linux/list.h +5 -4
index ac366958ea..3a29b95bfe 100644
@@ -912,7 +912,7 @@ static inline void hlist_del(struct hlist_node *n)
 {
 __hlist_del(n);
 n->next = LIST_POISON1;
- n->pprev = LIST_POISON2;
+ WRITE_ONCE(n->pprev, LIST_POISON2);
 }
 
 /**
@@ -925,7 +925,8 @@ static inline void hlist_del_init(struct hlist_node *n)
 {
 if (!hlist_unhashed(n)) {
 __hlist_del(n);
- INIT_HLIST_NODE(n);
+ n->next = NULL;
+ WRITE_ONCE(n->pprev, NULL);
 }
 }
 
@@ -1026,8 +1027,8 @@ static inline void hlist_move_list(struct hlist_head *old,
 {
 new->first = old->first;
 if (new->first)
- new->first->pprev = &new->first;
- old->first = NULL;
+ WRITE_ONCE(new->first->pprev, &new->first);
+ WRITE_ONCE(old->first, NULL);
 }
 
 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
include/linux/list_nulls.h +1 -1
index fa6e8471bd..b63b0589fa 100644
@@ -95,7 +95,7 @@ static inline void hlist_nulls_add_head(struct hlist_nulls_node *n,
 
 n->next = first;
 WRITE_ONCE(n->pprev, &h->first);
- h->first = n;
+ WRITE_ONCE(h->first, n);
 if (!is_a_nulls(first))
 WRITE_ONCE(first->pprev, &n->next);
 }
include/linux/rculist_nulls.h +1 -1
index ba4c00dd80..c65121655b 100644
@@ -138,7 +138,7 @@ static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n,
 
 if (last) {
 n->next = last->next;
- n->pprev = &last->next;
+ WRITE_ONCE(n->pprev, &last->next);
 rcu_assign_pointer(hlist_nulls_next_rcu(last), n);
 } else {
 hlist_nulls_add_head_rcu(n, h);
Signature · 1 line
2.34.1
#6 lore raw
In reply to Alan Huang
Quoted 43 lines · Alan Huang
Quoted 34 lines

2023年6月23日 下午1:17,Paul E. McKenney <[email protected]> 写道:

Quoted 22 lines · Alan Huang
Quoted 14 lines

2023年6月21日 06:26,Paul E. McKenney <[email protected]> 写道:

Quoted 9 lines · Alan Huang

Commit c54a2744497d("list: Add hlist_unhashed_lockless()") and commit 860c8802ace1("rcu: Use WRITE_ONCE() for assignments to ->pprev for hlist_nulls") added various WRITE_ONCE() to pair with the READ_ONCE() in hlist_unhashed_lockless(), but there are still some places where WRITE_ONCE() was not added, this commit adds that.

Also add WRITE_ONCE() to pair with the READ_ONCE() in hlist_empty().

Quoted 7 lines

On hlist_nulls_add_tail_rcu(), good catch, thank you!

On the others, are there really cases where a lockless read races with the update? At first glance, that sounds like a usage bug. For example, as I understand it, when you use something like hlist_del(), you are supposed to ensure that there are no concurrent readers. Which is the point of the assignment of the special value LIST_POISON2, right?

Quoted 7 lines

Do you mean there are cases where a lockless read races with hlist_add_head/hlist_add_before hlist_add_behind/__hlist_del, but there is no real case where a lockless read races with the hlist_del_init/hlist_del hlist_move_list?

There may be no real case where a lockless read races with the hlist_del_init/hlist_del hlist_move_list. But for the sake of completeness, I added those WRITE_ONCE, after all, if there is WRITE_ONCE in __hlist_del, why not add WRITE_ONCE in its caller, like hlist_del()?

Quoted 8 lines

You might well have located a larger issue. We want to be able to use KCSAN to find unintended data races, but as you noted, there might be different requirements for RCU-protected linked lists and for lock-protected linked lists. If there are, then there is probably existing linked-list code that is using the wrong primitive, for example, using (or failing to use) the one that Eric Dumazet provided. For example, mismatched API usage might be causing the differences in uses of _ONCE() primitives that you are calling out.

Quoted 8 lines

I noticed a thread:

https://lore.kernel.org/lkml/[email protected]/

It seems like Will wanted to remove that hlist_unhashed_lockless()? But I can’t find any further updates.

Will: Can you tell me what happened later?

IIRC, there were potential correctness issues with accesses being torn (possibly by the compiler) which meant that some additional surgery was needed to make some of the list accesses safe without locks.

I then ran into problems understanding how list_empty_careful() is supposed to work which weren't resolved. I think the best summary of where I got stuck (and moved onto more pressing things) is:

https://lore.kernel.org/lkml/20200424173932.GK21141@willie-the-truck/

Will