linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [RFC] llist: Fix code comments about llist_del_first locking
@ 2016-12-08 21:54 Joel Fernandes
  2016-12-09  0:35 ` Huang, Ying
  0 siblings, 1 reply; 7+ messages in thread
From: Joel Fernandes @ 2016-12-08 21:54 UTC (permalink / raw)
  To: linux-kernel
  Cc: Joel Fernandes, Huang Ying, Ingo Molnar, Will Deacon, Paul McKenney

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.

Cc: Huang Ying <ying.huang@intel.com>
Cc: Ingo Molnar <mingo@kernel.org>
Cc: Will Deacon <will.deacon@arm.com>
Cc: Paul McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Joel Fernandes <joelaf@google.com>
---
 include/linux/llist.h | 19 ++++++++++---------
 1 file changed, 10 insertions(+), 9 deletions(-)

diff --git a/include/linux/llist.h b/include/linux/llist.h
index fd4ca0b..15e4949 100644
--- a/include/linux/llist.h
+++ b/include/linux/llist.h
@@ -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   |          |           |     -
  *
-- 
2.8.0.rc3.226.g39d4020

^ permalink raw reply related	[flat|nested] 7+ messages in thread

* Re: [RFC] llist: Fix code comments about llist_del_first locking
  2016-12-08 21:54 [RFC] llist: Fix code comments about llist_del_first locking Joel Fernandes
@ 2016-12-09  0:35 ` Huang, Ying
  2016-12-09  0:42   ` Joel Fernandes
  0 siblings, 1 reply; 7+ messages in thread
From: Huang, Ying @ 2016-12-09  0:35 UTC (permalink / raw)
  To: Joel Fernandes
  Cc: linux-kernel, Huang Ying, Ingo Molnar, Will Deacon, Paul McKenney

Joel Fernandes <joelaf@google.com> writes:

> 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.
>
> Cc: Huang Ying <ying.huang@intel.com>
> Cc: Ingo Molnar <mingo@kernel.org>
> Cc: Will Deacon <will.deacon@arm.com>
> Cc: Paul McKenney <paulmck@linux.vnet.ibm.com>
> Signed-off-by: Joel Fernandes <joelaf@google.com>
> ---
>  include/linux/llist.h | 19 ++++++++++---------
>  1 file changed, 10 insertions(+), 9 deletions(-)
>
> diff --git a/include/linux/llist.h b/include/linux/llist.h
> index fd4ca0b..15e4949 100644
> --- a/include/linux/llist.h
> +++ b/include/linux/llist.h
> @@ -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     |     -

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

>   * del_first |          |     L     |     L
>   * del_all   |          |           |     -
>   *

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [RFC] llist: Fix code comments about llist_del_first locking
  2016-12-09  0:35 ` Huang, Ying
@ 2016-12-09  0:42   ` Joel Fernandes
  2016-12-09  0:43     ` Joel Fernandes
  0 siblings, 1 reply; 7+ messages in thread
From: Joel Fernandes @ 2016-12-09  0:42 UTC (permalink / raw)
  To: Huang, Ying; +Cc: LKML, Ingo Molnar, Will Deacon, Paul McKenney

On Thu, Dec 8, 2016 at 4:35 PM, Huang, Ying <ying.huang@intel.com> wrote:
> Joel Fernandes <joelaf@google.com> writes:
>
>> 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.
>>
>> Cc: Huang Ying <ying.huang@intel.com>
>> Cc: Ingo Molnar <mingo@kernel.org>
>> Cc: Will Deacon <will.deacon@arm.com>
>> Cc: Paul McKenney <paulmck@linux.vnet.ibm.com>
>> Signed-off-by: Joel Fernandes <joelaf@google.com>
>> ---
>>  include/linux/llist.h | 19 ++++++++++---------
>>  1 file changed, 10 insertions(+), 9 deletions(-)
>>
>> diff --git a/include/linux/llist.h b/include/linux/llist.h
>> index fd4ca0b..15e4949 100644
>> --- a/include/linux/llist.h
>> +++ b/include/linux/llist.h
>> @@ -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     |     -
>
> 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.

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

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [RFC] llist: Fix code comments about llist_del_first locking
  2016-12-09  0:42   ` Joel Fernandes
@ 2016-12-09  0:43     ` Joel Fernandes
  2016-12-09  2:12       ` Huang, Ying
  0 siblings, 1 reply; 7+ messages in thread
From: Joel Fernandes @ 2016-12-09  0:43 UTC (permalink / raw)
  To: Huang, Ying; +Cc: LKML, Ingo Molnar, Will Deacon, Paul McKenney

On Thu, Dec 8, 2016 at 4:42 PM, Joel Fernandes <joelaf@google.com> wrote:
> On Thu, Dec 8, 2016 at 4:35 PM, Huang, Ying <ying.huang@intel.com> wrote:
>> Joel Fernandes <joelaf@google.com> writes:
>>
>>> 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.
>>>
>>> Cc: Huang Ying <ying.huang@intel.com>
>>> Cc: Ingo Molnar <mingo@kernel.org>
>>> Cc: Will Deacon <will.deacon@arm.com>
>>> Cc: Paul McKenney <paulmck@linux.vnet.ibm.com>
>>> Signed-off-by: Joel Fernandes <joelaf@google.com>
>>> ---
>>>  include/linux/llist.h | 19 ++++++++++---------
>>>  1 file changed, 10 insertions(+), 9 deletions(-)
>>>
>>> diff --git a/include/linux/llist.h b/include/linux/llist.h
>>> index fd4ca0b..15e4949 100644
>>> --- a/include/linux/llist.h
>>> +++ b/include/linux/llist.h
>>> @@ -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     |     -
>>
>> 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.
>
> 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

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [RFC] llist: Fix code comments about llist_del_first locking
  2016-12-09  0:43     ` Joel Fernandes
@ 2016-12-09  2:12       ` Huang, Ying
  2016-12-09  2:22         ` Joel Fernandes
  0 siblings, 1 reply; 7+ messages in thread
From: Huang, Ying @ 2016-12-09  2:12 UTC (permalink / raw)
  To: Joel Fernandes; +Cc: Huang, Ying, LKML, Ingo Molnar, Will Deacon, Paul McKenney

Joel Fernandes <joelaf@google.com> writes:

> On Thu, Dec 8, 2016 at 4:42 PM, Joel Fernandes <joelaf@google.com> wrote:
>> On Thu, Dec 8, 2016 at 4:35 PM, Huang, Ying <ying.huang@intel.com> wrote:
>>> Joel Fernandes <joelaf@google.com> writes:
>>>
>>>> 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.
>>>>
>>>> Cc: Huang Ying <ying.huang@intel.com>
>>>> Cc: Ingo Molnar <mingo@kernel.org>
>>>> Cc: Will Deacon <will.deacon@arm.com>
>>>> Cc: Paul McKenney <paulmck@linux.vnet.ibm.com>
>>>> Signed-off-by: Joel Fernandes <joelaf@google.com>
>>>> ---
>>>>  include/linux/llist.h | 19 ++++++++++---------
>>>>  1 file changed, 10 insertions(+), 9 deletions(-)
>>>>
>>>> diff --git a/include/linux/llist.h b/include/linux/llist.h
>>>> index fd4ca0b..15e4949 100644
>>>> --- a/include/linux/llist.h
>>>> +++ b/include/linux/llist.h
>>>> @@ -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     |     -
>>>
>>> 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.
>>
>> 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

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [RFC] llist: Fix code comments about llist_del_first locking
  2016-12-09  2:12       ` Huang, Ying
@ 2016-12-09  2:22         ` Joel Fernandes
  2016-12-09  2:26           ` Huang, Ying
  0 siblings, 1 reply; 7+ messages in thread
From: Joel Fernandes @ 2016-12-09  2:22 UTC (permalink / raw)
  To: Huang, Ying; +Cc: LKML, Ingo Molnar, Will Deacon, Paul McKenney

On Thu, Dec 8, 2016 at 6:12 PM, Huang, Ying <ying.huang@intel.com> wrote:
> Joel Fernandes <joelaf@google.com> writes:
>
>> On Thu, Dec 8, 2016 at 4:42 PM, Joel Fernandes <joelaf@google.com> wrote:
>>> On Thu, Dec 8, 2016 at 4:35 PM, Huang, Ying <ying.huang@intel.com> wrote:
>>>> Joel Fernandes <joelaf@google.com> writes:
>>>>
>>>>> 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.
>>>>>
>>>>> Cc: Huang Ying <ying.huang@intel.com>
>>>>> Cc: Ingo Molnar <mingo@kernel.org>
>>>>> Cc: Will Deacon <will.deacon@arm.com>
>>>>> Cc: Paul McKenney <paulmck@linux.vnet.ibm.com>
>>>>> Signed-off-by: Joel Fernandes <joelaf@google.com>
>>>>> ---
>>>>>  include/linux/llist.h | 19 ++++++++++---------
>>>>>  1 file changed, 10 insertions(+), 9 deletions(-)
>>>>>
>>>>> diff --git a/include/linux/llist.h b/include/linux/llist.h
>>>>> index fd4ca0b..15e4949 100644
>>>>> --- a/include/linux/llist.h
>>>>> +++ b/include/linux/llist.h
>>>>> @@ -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     |     -
>>>>
>>>> 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.
>>>
>>> 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.

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

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [RFC] llist: Fix code comments about llist_del_first locking
  2016-12-09  2:22         ` Joel Fernandes
@ 2016-12-09  2:26           ` Huang, Ying
  0 siblings, 0 replies; 7+ messages in thread
From: Huang, Ying @ 2016-12-09  2:26 UTC (permalink / raw)
  To: Joel Fernandes; +Cc: Huang, Ying, LKML, Ingo Molnar, Will Deacon, Paul McKenney

Joel Fernandes <joelaf@google.com> writes:

> On Thu, Dec 8, 2016 at 6:12 PM, Huang, Ying <ying.huang@intel.com> wrote:
>> Joel Fernandes <joelaf@google.com> writes:
>>
>>> On Thu, Dec 8, 2016 at 4:42 PM, Joel Fernandes <joelaf@google.com> wrote:
>>>> On Thu, Dec 8, 2016 at 4:35 PM, Huang, Ying <ying.huang@intel.com> wrote:
>>>>> Joel Fernandes <joelaf@google.com> writes:
>>>>>
>>>>>> 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.
>>>>>>
>>>>>> Cc: Huang Ying <ying.huang@intel.com>
>>>>>> Cc: Ingo Molnar <mingo@kernel.org>
>>>>>> Cc: Will Deacon <will.deacon@arm.com>
>>>>>> Cc: Paul McKenney <paulmck@linux.vnet.ibm.com>
>>>>>> Signed-off-by: Joel Fernandes <joelaf@google.com>
>>>>>> ---
>>>>>>  include/linux/llist.h | 19 ++++++++++---------
>>>>>>  1 file changed, 10 insertions(+), 9 deletions(-)
>>>>>>
>>>>>> diff --git a/include/linux/llist.h b/include/linux/llist.h
>>>>>> index fd4ca0b..15e4949 100644
>>>>>> --- a/include/linux/llist.h
>>>>>> +++ b/include/linux/llist.h
>>>>>> @@ -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     |     -
>>>>>
>>>>> 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.
>>>>
>>>> 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.
>
> 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

^ permalink raw reply	[flat|nested] 7+ messages in thread

end of thread, other threads:[~2016-12-09  2:26 UTC | newest]

Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-12-08 21:54 [RFC] llist: Fix code comments about llist_del_first locking Joel Fernandes
2016-12-09  0:35 ` Huang, Ying
2016-12-09  0:42   ` Joel Fernandes
2016-12-09  0:43     ` Joel Fernandes
2016-12-09  2:12       ` Huang, Ying
2016-12-09  2:22         ` Joel Fernandes
2016-12-09  2:26           ` Huang, Ying

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).