llist: Fix code comments about llist_del_first locking
RFC 1/1 llist: Fix code comments about llist_del_first locking
Usage llist_del_first needs lock protection, however the table in the comments of llist.h show a '-'. Correct this, and also add better comments on top.
--- include/linux/llist.h | 19 ++++++++++--------- 1 file changed, 10 insertions(+), 9 deletions(-)
include/linux/llist.h +10 -9
@@ -3,14 +3,15 @@/* * Lock-less NULL terminated single linked list * -* If there are multiple producers and multiple consumers, llist_add -* can be used in producers and llist_del_all can be used in -* consumers. They can work simultaneously without lock. But -* llist_del_first can not be used here. Because llist_del_first -* depends on list->first->next does not changed if list->first is not -* changed during its operation, but llist_del_first, llist_add, -* llist_add (or llist_del_all, llist_add, llist_add) sequence in -* another consumer may violate that. +* If there are multiple producers and multiple consumers, llist_add can be +* used in producers and llist_del_all can be used in consumers. They can work +* simultaneously without lock. But llist_del_first will need to use a lock +* with any other operation (ABA problem). This is because llist_del_first +* depends on list->first->next not changing but there's no way to be sure +* about that and the cmpxchg in llist_del_first may succeed if list->first is +* the same after concurrent operations. For example, a llist_del_first, +* llist_add, llist_add (or llist_del_all, llist_add, llist_add) sequence in +* another consumer may cause violations. * * If there are multiple producers and one consumer, llist_add can be * used in producers and llist_del_all or llist_del_first can be used
@@ -19,7 +20,7 @@* This can be summarized as follow: * * | add | del_first | del_all -* add | - | - | - +* add | - | L | - * del_first | | L | L * del_all | | | - *
Signature · 1 line
2.8.0.rc3.226.g39d4020
Quoted 42 lines · Joel Fernandes
Usage
llist_del_firstneeds lock protection, however the table in the comments ofllist.hshow a '-'. Correct this, and also add better comments on top.Cc Huang Ying <[email protected]>Cc Ingo Molnar <[email protected]>Cc Will Deacon <[email protected]>Cc Paul McKenney <[email protected]>Signed-off-by Joel Fernandes <[email protected]>--- include/linux/llist.h | 19 ++++++++++--------- 1 file changed, 10 insertions(+), 9 deletions(-)include/linux/llist.h +9
-8@@ -3,14 +3,15 @@/* * Lock-less NULL terminated single linked list * -* If there are multiple producers and multiple consumers, llist_add -* can be used in producers and llist_del_all can be used in -* consumers. They can work simultaneously without lock. But -* llist_del_first can not be used here. Because llist_del_first -* depends on list->first->next does not changed if list->first is not -* changed during its operation, but llist_del_first, llist_add, -* llist_add (or llist_del_all, llist_add, llist_add) sequence in -* another consumer may violate that. +* If there are multiple producers and multiple consumers, llist_add can be +* used in producers and llist_del_all can be used in consumers. They can work +* simultaneously without lock. But llist_del_first will need to use a lock +* with any other operation (ABA problem). This is because llist_del_first +* depends on list->first->next not changing but there's no way to be sure +* about that and the cmpxchg in llist_del_first may succeed if list->first is +* the same after concurrent operations. For example, a llist_del_first, +* llist_add, llist_add (or llist_del_all, llist_add, llist_add) sequence in +* another consumer may cause violations. * * If there are multiple producers and one consumer, llist_add can be * used in producers and llist_del_all or llist_del_first can be used
include/linux/llist.h line 23
Quoted 5 lines
include/linux/llist.h +1
-1@@ -19,7 +20,7 @@* This can be summarized as follow: * * | add | del_first | del_all -* add | - | - | - +* add | - | L | -
If there are only one consumer which only calls llist_del_first(), lock is unnecessary. So '-' is shown here originally. But if there are multiple consumers which call llist_del_first() or llist_del_all(), lock is needed.
Best Regards,
Huang, Ying
Quoted 3 lines
include/linux/llist.h +0
-0* del_first | | L | L * del_all | | | - *
Quoted 46 lines · Ying
Quoted 44 lines · Joel Fernandes
Usage
llist_del_firstneeds lock protection, however the table in the comments ofllist.hshow a '-'. Correct this, and also add better comments on top.Cc Huang Ying <[email protected]>Cc Ingo Molnar <[email protected]>Cc Will Deacon <[email protected]>Cc Paul McKenney <[email protected]>Signed-off-by Joel Fernandes <[email protected]>--- include/linux/llist.h | 19 ++++++++++--------- 1 file changed, 10 insertions(+), 9 deletions(-)include/linux/llist.h +9
-8@@ -3,14 +3,15 @@/* * Lock-less NULL terminated single linked list * -* If there are multiple producers and multiple consumers, llist_add -* can be used in producers and llist_del_all can be used in -* consumers. They can work simultaneously without lock. But -* llist_del_first can not be used here. Because llist_del_first -* depends on list->first->next does not changed if list->first is not -* changed during its operation, but llist_del_first, llist_add, -* llist_add (or llist_del_all, llist_add, llist_add) sequence in -* another consumer may violate that. +* If there are multiple producers and multiple consumers, llist_add can be +* used in producers and llist_del_all can be used in consumers. They can work +* simultaneously without lock. But llist_del_first will need to use a lock +* with any other operation (ABA problem). This is because llist_del_first +* depends on list->first->next not changing but there's no way to be sure +* about that and the cmpxchg in llist_del_first may succeed if list->first is +* the same after concurrent operations. For example, a llist_del_first, +* llist_add, llist_add (or llist_del_all, llist_add, llist_add) sequence in +* another consumer may cause violations. * * If there are multiple producers and one consumer, llist_add can be * used in producers and llist_del_all or llist_del_first can be used @@ -19,7 +20,7 @@* This can be summarized as follow: *
Quoted 8 lines
include/linux/llist.h line 23
Quoted 3 lines
include/linux/llist.h +1
-1* | add | del_first | del_all -* add | - | - | - +* add | - | L | - If there are only one consumer which only calls
llist_del_first(), lock is unnecessary. So '-' is shown here originally. But if there are multiple consumers which callllist_del_first()orllist_del_all(), lock is needed.
I think this needs to be made more clear in the table. The table doesn't clear say whether it describes the preceding paragraph (multiple producers and one consumer), or if it describes the multiple producers and one consumer case. So either we should have 2 tables, or just have one table for both cases and make it clear in the comments. Like Instead of '-', say L* where * means locking is optional if there's only one consumer.
Regards,
Joel
Quoted 56 lines · Joel Fernandes
Quoted 46 lines · Ying
Quoted 44 lines · Joel Fernandes
Usage
llist_del_firstneeds lock protection, however the table in the comments ofllist.hshow a '-'. Correct this, and also add better comments on top.Cc Huang Ying <[email protected]>Cc Ingo Molnar <[email protected]>Cc Will Deacon <[email protected]>Cc Paul McKenney <[email protected]>Signed-off-by Joel Fernandes <[email protected]>--- include/linux/llist.h | 19 ++++++++++--------- 1 file changed, 10 insertions(+), 9 deletions(-)include/linux/llist.h +9
-8@@ -3,14 +3,15 @@/* * Lock-less NULL terminated single linked list * -* If there are multiple producers and multiple consumers, llist_add -* can be used in producers and llist_del_all can be used in -* consumers. They can work simultaneously without lock. But -* llist_del_first can not be used here. Because llist_del_first -* depends on list->first->next does not changed if list->first is not -* changed during its operation, but llist_del_first, llist_add, -* llist_add (or llist_del_all, llist_add, llist_add) sequence in -* another consumer may violate that. +* If there are multiple producers and multiple consumers, llist_add can be +* used in producers and llist_del_all can be used in consumers. They can work +* simultaneously without lock. But llist_del_first will need to use a lock +* with any other operation (ABA problem). This is because llist_del_first +* depends on list->first->next not changing but there's no way to be sure +* about that and the cmpxchg in llist_del_first may succeed if list->first is +* the same after concurrent operations. For example, a llist_del_first, +* llist_add, llist_add (or llist_del_all, llist_add, llist_add) sequence in +* another consumer may cause violations. * * If there are multiple producers and one consumer, llist_add can be * used in producers and llist_del_all or llist_del_first can be used @@ -19,7 +20,7 @@* This can be summarized as follow: * Quoted 8 lines
include/linux/llist.h line 23
Quoted 3 lines
include/linux/llist.h +1
-1* | add | del_first | del_all -* add | - | - | - +* add | - | L | - If there are only one consumer which only calls
llist_del_first(), lock is unnecessary. So '-' is shown here originally. But if there are multiple consumers which callllist_del_first()orllist_del_all(), lock is needed.
Quoted 4 lines
I think this needs to be made more clear in the table. The table doesn't clear say whether it describes the preceding paragraph (multiple producers and one consumer), or if it describes the multiple producers and one consumer case. So either we should have 2 tables, or
Sorry, I meant "or if it describes the multiple producer and multiple consumer case".
Regards,
Joel
Quoted 57 lines · Joel Fernandes
Quoted 56 lines · Joel Fernandes
Quoted 54 lines · Ying
Quoted 42 lines · Joel Fernandes
Usage
llist_del_firstneeds lock protection, however the table in the comments ofllist.hshow a '-'. Correct this, and also add better comments on top.Cc Huang Ying <[email protected]>Cc Ingo Molnar <[email protected]>Cc Will Deacon <[email protected]>Cc Paul McKenney <[email protected]>Signed-off-by Joel Fernandes <[email protected]>--- include/linux/llist.h | 19 ++++++++++--------- 1 file changed, 10 insertions(+), 9 deletions(-)include/linux/llist.h +9
-8@@ -3,14 +3,15 @@/* * Lock-less NULL terminated single linked list * -* If there are multiple producers and multiple consumers, llist_add -* can be used in producers and llist_del_all can be used in -* consumers. They can work simultaneously without lock. But -* llist_del_first can not be used here. Because llist_del_first -* depends on list->first->next does not changed if list->first is not -* changed during its operation, but llist_del_first, llist_add, -* llist_add (or llist_del_all, llist_add, llist_add) sequence in -* another consumer may violate that. +* If there are multiple producers and multiple consumers, llist_add can be +* used in producers and llist_del_all can be used in consumers. They can work +* simultaneously without lock. But llist_del_first will need to use a lock +* with any other operation (ABA problem). This is because llist_del_first +* depends on list->first->next not changing but there's no way to be sure +* about that and the cmpxchg in llist_del_first may succeed if list->first is +* the same after concurrent operations. For example, a llist_del_first, +* llist_add, llist_add (or llist_del_all, llist_add, llist_add) sequence in +* another consumer may cause violations. * * If there are multiple producers and one consumer, llist_add can be * used in producers and llist_del_all or llist_del_first can be used include/linux/llist.h line 23
Quoted 5 lines
include/linux/llist.h +1
-1@@ -19,7 +20,7 @@* This can be summarized as follow: * * | add | del_first | del_all -* add | - | - | - +* add | - | L | - If there are only one consumer which only calls
llist_del_first(), lock is unnecessary. So '-' is shown here originally. But if there are multiple consumers which callllist_del_first()orllist_del_all(), lock is needed.
Quoted 7 lines
Quoted 4 lines
I think this needs to be made more clear in the table. The table doesn't clear say whether it describes the preceding paragraph (multiple producers and one consumer), or if it describes the multiple producers and one consumer case. So either we should have 2 tables, or
Sorry, I meant "or if it describes the multiple producer and multiple consumer case".
I tried to describe both cases in the original table.
* | add | del_first | del_all * add | - | - | - * del_first | | L | L * del_all | | | -
The 'L' for "del_first * del_first" means multiple consumers uses llist_del_first() need lock. And the 'L' for 'del_first * del_all' means multiple consumers uses llist_del_first() and llist_del_all() need lock.
Best Regards,
Huang, Ying
Quoted 74 lines · Ying
Quoted 57 lines · Joel Fernandes
Quoted 56 lines · Joel Fernandes
Quoted 54 lines · Ying
Quoted 42 lines · Joel Fernandes
Usage
llist_del_firstneeds lock protection, however the table in the comments ofllist.hshow a '-'. Correct this, and also add better comments on top.Cc Huang Ying <[email protected]>Cc Ingo Molnar <[email protected]>Cc Will Deacon <[email protected]>Cc Paul McKenney <[email protected]>Signed-off-by Joel Fernandes <[email protected]>--- include/linux/llist.h | 19 ++++++++++--------- 1 file changed, 10 insertions(+), 9 deletions(-)include/linux/llist.h +9
-8@@ -3,14 +3,15 @@/* * Lock-less NULL terminated single linked list * -* If there are multiple producers and multiple consumers, llist_add -* can be used in producers and llist_del_all can be used in -* consumers. They can work simultaneously without lock. But -* llist_del_first can not be used here. Because llist_del_first -* depends on list->first->next does not changed if list->first is not -* changed during its operation, but llist_del_first, llist_add, -* llist_add (or llist_del_all, llist_add, llist_add) sequence in -* another consumer may violate that. +* If there are multiple producers and multiple consumers, llist_add can be +* used in producers and llist_del_all can be used in consumers. They can work +* simultaneously without lock. But llist_del_first will need to use a lock +* with any other operation (ABA problem). This is because llist_del_first +* depends on list->first->next not changing but there's no way to be sure +* about that and the cmpxchg in llist_del_first may succeed if list->first is +* the same after concurrent operations. For example, a llist_del_first, +* llist_add, llist_add (or llist_del_all, llist_add, llist_add) sequence in +* another consumer may cause violations. * * If there are multiple producers and one consumer, llist_add can be * used in producers and llist_del_all or llist_del_first can be used include/linux/llist.h line 23
Quoted 5 lines
include/linux/llist.h +1
-1@@ -19,7 +20,7 @@* This can be summarized as follow: * * | add | del_first | del_all -* add | - | - | - +* add | - | L | - If there are only one consumer which only calls
llist_del_first(), lock is unnecessary. So '-' is shown here originally. But if there are multiple consumers which callllist_del_first()orllist_del_all(), lock is needed.Quoted 7 lines
Quoted 4 lines
I think this needs to be made more clear in the table. The table doesn't clear say whether it describes the preceding paragraph (multiple producers and one consumer), or if it describes the multiple producers and one consumer case. So either we should have 2 tables, or
Sorry, I meant "or if it describes the multiple producer and multiple consumer case".
I tried to describe both cases in the original table.
* | add | del_first | del_all * add | - | - | - * del_first | | L | L * del_all | | | -
Quoted 4 lines
The 'L' for "
del_first*del_first" means multiple consumers usesllist_del_first()need lock. And the 'L' for 'del_first*del_all' means multiple consumers usesllist_del_first()andllist_del_all()need lock.
Ok, now I get it - so basically the table describes one producer/consumer vs another producer/consumer, in other words you are just describing contention between any 2 operations. Thanks for clarifying. I will respin the comments to explain this a bit better if that's Ok with you.
Regards,
Joel
Quoted 80 lines · Joel Fernandes
Quoted 74 lines · Ying
Quoted 57 lines · Joel Fernandes
Quoted 56 lines · Joel Fernandes
Quoted 54 lines · Ying
Quoted 42 lines · Joel Fernandes
Usage
llist_del_firstneeds lock protection, however the table in the comments ofllist.hshow a '-'. Correct this, and also add better comments on top.Cc Huang Ying <[email protected]>Cc Ingo Molnar <[email protected]>Cc Will Deacon <[email protected]>Cc Paul McKenney <[email protected]>Signed-off-by Joel Fernandes <[email protected]>--- include/linux/llist.h | 19 ++++++++++--------- 1 file changed, 10 insertions(+), 9 deletions(-)include/linux/llist.h +9
-8@@ -3,14 +3,15 @@/* * Lock-less NULL terminated single linked list * -* If there are multiple producers and multiple consumers, llist_add -* can be used in producers and llist_del_all can be used in -* consumers. They can work simultaneously without lock. But -* llist_del_first can not be used here. Because llist_del_first -* depends on list->first->next does not changed if list->first is not -* changed during its operation, but llist_del_first, llist_add, -* llist_add (or llist_del_all, llist_add, llist_add) sequence in -* another consumer may violate that. +* If there are multiple producers and multiple consumers, llist_add can be +* used in producers and llist_del_all can be used in consumers. They can work +* simultaneously without lock. But llist_del_first will need to use a lock +* with any other operation (ABA problem). This is because llist_del_first +* depends on list->first->next not changing but there's no way to be sure +* about that and the cmpxchg in llist_del_first may succeed if list->first is +* the same after concurrent operations. For example, a llist_del_first, +* llist_add, llist_add (or llist_del_all, llist_add, llist_add) sequence in +* another consumer may cause violations. * * If there are multiple producers and one consumer, llist_add can be * used in producers and llist_del_all or llist_del_first can be used include/linux/llist.h line 23
Quoted 5 lines
include/linux/llist.h +1
-1@@ -19,7 +20,7 @@* This can be summarized as follow: * * | add | del_first | del_all -* add | - | - | - +* add | - | L | - If there are only one consumer which only calls
llist_del_first(), lock is unnecessary. So '-' is shown here originally. But if there are multiple consumers which callllist_del_first()orllist_del_all(), lock is needed.Quoted 7 lines
Quoted 4 lines
I think this needs to be made more clear in the table. The table doesn't clear say whether it describes the preceding paragraph (multiple producers and one consumer), or if it describes the multiple producers and one consumer case. So either we should have 2 tables, or
Sorry, I meant "or if it describes the multiple producer and multiple consumer case".
I tried to describe both cases in the original table.
* | add | del_first | del_all * add | - | - | - * del_first | | L | L * del_all | | | -Quoted 4 lines
The 'L' for "
del_first*del_first" means multiple consumers usesllist_del_first()need lock. And the 'L' for 'del_first*del_all' means multiple consumers usesllist_del_first()andllist_del_all()need lock.
Quoted 5 lines
Ok, now I get it - so basically the table describes one producer/consumer vs another producer/consumer, in other words you are just describing contention between any 2 operations. Thanks for clarifying. I will respin the comments to explain this a bit better if that's Ok with you.
It is good for me to improve the comments.
Best Regards,
Huang, Ying