lkml.org 
[lkml]   [2017]   [Jan]   [14]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH tip/core/rcu 18/20] llist: Clarify comments about when locking is needed
    Date
    From: Joel Fernandes <joelaf@google.com>

    llist.h comments are confusing about when locking is needed versus when it
    isn't. Clarify these comments by being more descriptive about why locking is
    needed for llist_del_first.

    Cc: Ingo Molnar <mingo@kernel.org>
    Cc: Will Deacon <will.deacon@arm.com>
    Cc: Paul McKenney <paulmck@linux.vnet.ibm.com>
    Acked-by: Huang Ying <ying.huang@intel.com>
    Acked-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
    Signed-off-by: Joel Fernandes <joelaf@google.com>
    Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
    ---
    include/linux/llist.h | 37 +++++++++++++++++++++----------------
    1 file changed, 21 insertions(+), 16 deletions(-)

    diff --git a/include/linux/llist.h b/include/linux/llist.h
    index fd4ca0b4fe0f..171baa90f6f6 100644
    --- a/include/linux/llist.h
    +++ b/include/linux/llist.h
    @@ -3,28 +3,33 @@
    /*
    * 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 one consumer, llist_add can be
    - * used in producers and llist_del_all or llist_del_first can be used
    - * in the consumer.
    - *
    - * This can be summarized as follow:
    + * Cases where locking is not needed:
    + * If there are multiple producers and multiple consumers, llist_add can be
    + * used in producers and llist_del_all can be used in consumers simultaneously
    + * without locking. Also a single consumer can use llist_del_first while
    + * multiple producers simultaneously use llist_add, without any locking.
    + *
    + * Cases where locking is needed:
    + * If we have multiple consumers with llist_del_first used in one consumer, and
    + * llist_del_first or llist_del_all used in other consumers, then a lock is
    + * needed. This is because llist_del_first depends on list->first->next not
    + * changing, but without lock protection, there's no way to be sure about that
    + * if a preemption happens in the middle of the delete operation and on being
    + * preempted back, the list->first is the same as before causing the cmpxchg in
    + * llist_del_first to succeed. For example, while a llist_del_first operation
    + * is in progress in one consumer, then a llist_del_first, llist_add,
    + * llist_add (or llist_del_all, llist_add, llist_add) sequence in another
    + * consumer may cause violations.
    + *
    + * This can be summarized as follows:
    *
    * | add | del_first | del_all
    * add | - | - | -
    * del_first | | L | L
    * del_all | | | -
    *
    - * Where "-" stands for no lock is needed, while "L" stands for lock
    - * is needed.
    + * Where, a particular row's operation can happen concurrently with a column's
    + * operation, with "-" being no lock needed, while "L" being lock is needed.
    *
    * The list entries deleted via llist_del_all can be traversed with
    * traversing function such as llist_for_each etc. But the list
    --
    2.5.2
    \
     
     \ /
      Last update: 2017-01-14 10:14    [W:2.868 / U:0.464 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site