From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1762147AbdADAJB (ORCPT ); Tue, 3 Jan 2017 19:09:01 -0500 Received: from mx0a-001b2d01.pphosted.com ([148.163.156.1]:33331 "EHLO mx0a-001b2d01.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753169AbdADAIy (ORCPT ); Tue, 3 Jan 2017 19:08:54 -0500 Date: Tue, 3 Jan 2017 16:08:49 -0800 From: "Paul E. McKenney" To: Joel Fernandes Cc: linux-kernel@vger.kernel.org, Huang Ying , Mathieu Desnoyers , Ingo Molnar , Will Deacon Subject: Re: [PATCH v3] llist: Clarify comments about when locking is needed Reply-To: paulmck@linux.vnet.ibm.com References: <1481594505-2779-1-git-send-email-joelaf@google.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1481594505-2779-1-git-send-email-joelaf@google.com> User-Agent: Mutt/1.5.21 (2010-09-15) X-TM-AS-GCONF: 00 X-Content-Scanned: Fidelis XPS MAILER x-cbid: 17010400-0008-0000-0000-0000067989B0 X-IBM-SpamModules-Scores: X-IBM-SpamModules-Versions: BY=3.00006368; HX=3.00000240; KW=3.00000007; PH=3.00000004; SC=3.00000199; SDB=6.00803143; UDB=6.00390685; IPR=6.00580993; BA=6.00005028; NDR=6.00000001; ZLA=6.00000005; ZF=6.00000009; ZB=6.00000000; ZP=6.00000000; ZH=6.00000000; ZU=6.00000002; MB=3.00013815; XFM=3.00000011; UTC=2017-01-04 00:08:52 X-IBM-AV-DETECTION: SAVI=unused REMOTE=unused XFE=unused x-cbparentid: 17010400-0009-0000-0000-00003E587A3A Message-Id: <20170104000849.GC3742@linux.vnet.ibm.com> X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:,, definitions=2017-01-03_21:,, signatures=0 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 spamscore=0 suspectscore=0 malwarescore=0 phishscore=0 adultscore=0 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1612050000 definitions=main-1701040000 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Mon, Dec 12, 2016 at 06:01:45PM -0800, Joel Fernandes wrote: > 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 > Cc: Will Deacon > Cc: Paul McKenney > Acked-by: Huang Ying > Acked-by: Mathieu Desnoyers > Signed-off-by: Joel Fernandes Queued for 4.12, thank you all! Thanx, Paul > --- > Changes since before: > Minor changes to comment and commit message based on Mathieu's suggestions > (https://lkml.org/lkml/2016/12/10/39) > > 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 fd4ca0b..31822bb 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.8.0.rc3.226.g39d4020 >