From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751183AbdAXB5Z (ORCPT ); Mon, 23 Jan 2017 20:57:25 -0500 Received: from mx0a-001b2d01.pphosted.com ([148.163.156.1]:37305 "EHLO mx0a-001b2d01.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750708AbdAXB5Y (ORCPT ); Mon, 23 Jan 2017 20:57:24 -0500 Date: Mon, 23 Jan 2017 17:57:15 -0800 From: "Paul E. McKenney" To: Lance Roy Cc: linux-kernel@vger.kernel.org, mingo@kernel.org, jiangshanlai@gmail.com, dipankar@in.ibm.com, akpm@linux-foundation.org, mathieu.desnoyers@efficios.com, josh@joshtriplett.org, tglx@linutronix.de, peterz@infradead.org, rostedt@goodmis.org, dhowells@redhat.com, edumazet@google.com, dvhart@linux.intel.com, fweisbec@gmail.com, oleg@redhat.com, bobby.prani@gmail.com Subject: Re: [PATCH] srcu: Implement more-efficient reader counts Reply-To: paulmck@linux.vnet.ibm.com References: <20170123133359.2d69756a@gmail.com> <20170123213518.7200-1-ldr709@gmail.com> <20170124004252.GZ28085@linux.vnet.ibm.com> <20170123165334.6873e47f@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20170123165334.6873e47f@gmail.com> User-Agent: Mutt/1.5.21 (2010-09-15) X-TM-AS-GCONF: 00 X-Content-Scanned: Fidelis XPS MAILER x-cbid: 17012401-0004-0000-0000-0000115E5A18 X-IBM-SpamModules-Scores: X-IBM-SpamModules-Versions: BY=3.00006487; HX=3.00000240; KW=3.00000007; PH=3.00000004; SC=3.00000200; SDB=6.00811784; UDB=6.00395825; IPR=6.00589201; BA=6.00005084; NDR=6.00000001; ZLA=6.00000005; ZF=6.00000009; ZB=6.00000000; ZP=6.00000000; ZH=6.00000000; ZU=6.00000002; MB=3.00014019; XFM=3.00000011; UTC=2017-01-24 01:57:20 X-IBM-AV-DETECTION: SAVI=unused REMOTE=unused XFE=unused x-cbparentid: 17012401-0005-0000-0000-00007C6C4AAC Message-Id: <20170124015715.GD28085@linux.vnet.ibm.com> X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:,, definitions=2017-01-23_22:,, 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-1701240020 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Mon, Jan 23, 2017 at 04:53:34PM -0800, Lance Roy wrote: > On Mon, 23 Jan 2017 16:42:52 -0800 > "Paul E. McKenney" wrote: > > > On Mon, Jan 23, 2017 at 01:35:18PM -0800, Lance Roy wrote: > > > SRCU uses two per-cpu counters: a nesting counter to count the number of > > > active critical sections, and a sequence counter to ensure that the nesting > > > counters don't change while they are being added together in > > > srcu_readers_active_idx_check(). > > > > > > This patch instead uses per-cpu lock and unlock counters. Because both > > > counters only increase and srcu_readers_active_idx_check() reads the unlock > > > counter before the lock counter, this achieves the same end without having > > > to increment two different counters in srcu_read_lock(). This also saves a > > > smp_mb() in srcu_readers_active_idx_check(). > > > > > > Possible bug: There is no guarantee that the lock counter won't overflow > > > during srcu_readers_active_idx_check(), as there are no memory barriers > > > around srcu_flip() (see comment in srcu_readers_active_idx_check() for > > > details). However, this problem was already present before this patch. > > > > > > Suggested-by: Mathieu Desnoyers > > > Signed-off-by: Lance Roy > > > Cc: Paul E. McKenney > > > Cc: Lai Jiangshan > > > Cc: Peter Zijlstra > > > > OK, this only has differences only in the comments, so I can reasonably > > substitute it, even this near the next merge window. > > > > But let's talk about the potential overflow. If I understand correctly, > > for this to happen, there needs to be ULONG_MAX/2 or thereabouts > > srcu_read_lock() calls without matching srcu_read_unlock() calls. > > Let's focus on 32-bit systems for the moment. > > > > Lockdep allows at most 48 locks held at a given time by any single task, > > and RCU does not pass in a non-NULL nest_lock -- if you acquire more than > > that, a lockdep kernel will splat. Each task has at least one 4K page of > > kernel stack, so there can be at most 1,048,576 tasks (actually quite a > > bit fewer due to the size of the task_struct and so on). This allows > > at most 50,331,648 unmatched srcu_read_lock() calls in the system, > > which is not sufficient to cause overflow. > > > > Or am I missing something here? > > > > Thanx, Paul > > It isn't the nest that is the problem. Here is a previous email I wrote > describing the problem: > > > The trouble is that disabling preemption is not enough to ensure that there > is at most one srcu_read_lock() call per CPU that missed the srcu_flip(). > > Define a reader to be an SRCU lock+unlock pair. A reader is called active if it > has incremented ->lock_count[] but hasn't incremented ->unlock_count[] yet, and > completed if it has incremented ->unlock_count[]. I think that we only want to > limit the number of active readers and the number of CPUs. In particular, I > don't think there should be a limit on the rate of completion of read side > critical section. > > The goal of srcu_readers_active_idx_check() is to verify that there were zero > active readers on the inactive index at some time during its execution. To do > this, it totals the unlock counts, executes a memory barrier, totals the lock > counts, and takes the difference. This difference counts the readers that are > active when srcu_readers_lock_idx() gets to their CPU, plus the readers that > completed after srcu_readers_unlock_idx() and before srcu_readers_lock_idx(). > If the true (infinite precision) value of the difference is zero, then there > were no active readers at some point while srcu_readers_lock_idx() is running. > However, the difference is only stored in a long, so there is a potential for > overflow if too many readers complete during srcu_readers_active_idx_check(). > > For example, let's say there are three threads, each running on their own CPU: > > int data, flag; > struct srcu_struct *sp = /* ... */; > > Thread 0: > data = 1; > synchronize_srcu(sp); > flag = 1; > > Thread 1: > int data_r, flag_r; > int idx = srcu_read_lock(sp); > data_r = data; > flag_r = flag; > srcu_read_unlock(sp, idx); > BUG_ON(flag_r == 1 && data_r == 0); > > Thread 2: > while (true) { > int idx = srcu_read_lock(sp); > srcu_read_unlock(sp, idx); > } > > Let's take the following execution order. Thread 1 increments > the CPU 1 version of sp->lock_count[0], sets idx to zero, and loads data (0) > into data_r. Thread 0 then sets data to be 1, verifies that there are no > readers on index 1, and increments sp->completed, but the CPU actually doesn't > preform the last operation, putting it off until the next memory barrier. Thread > 0 then calls srcu_readers_active_idx_check() on index 0, which runs > srcu_readers_unlock_idx() (returning 0). Right after srcu_readers_unlock_idx() > completes, thread 2 starts running. Since Thread 0 hasn't actually incremented > sp->completed in any way that is visible to thread 2, srcu_read_lock() will > still return 0. Thread 2 can then run for ULONG_MAX iterations, setting > the CPU 2 version of sp->unlock_count[0] to ULONG_MAX. CPU 0 then finally gets > around to incrementing sp->completed, runs its memory barrier, and then reads > the lock counts: 1, 0, ULONG_MAX. The total of ULONG_MAX+1 will overflow to 0 > and compare equal with earlier unlock count. Thread 0 will then think that the > grace period is over and set flag to one. Thread 1 can then read flag (1) into > flag_r and run srcu_read_unlock(). The BUG_ON statement will then fail. > > Although ULONG_MAX readers completed during srcu_readers_active_idx_check(), > there were at most 2 active readers at any time, so this program doesn't run > into any limit. > > I hope that was clear enough. Yeah, we did have this same conversation awhile back, didn't we? Back then, did I think to ask if this could be minimized or even prevented by adding memory barriers appropriately? ;-) Thanx, Paul