From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-yh0-f49.google.com (mail-yh0-f49.google.com [209.85.213.49]) by kanga.kvack.org (Postfix) with ESMTP id 97B746B0099 for ; Tue, 26 Nov 2013 14:28:17 -0500 (EST) Received: by mail-yh0-f49.google.com with SMTP id z20so4281827yhz.8 for ; Tue, 26 Nov 2013 11:28:17 -0800 (PST) Received: from e37.co.us.ibm.com (e37.co.us.ibm.com. [32.97.110.158]) by mx.google.com with ESMTPS id d49si25157438yhn.105.2013.11.26.11.28.15 for (version=TLSv1 cipher=RC4-SHA bits=128/128); Tue, 26 Nov 2013 11:28:16 -0800 (PST) Received: from /spool/local by e37.co.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Tue, 26 Nov 2013 12:28:15 -0700 Received: from b03cxnp08028.gho.boulder.ibm.com (b03cxnp08028.gho.boulder.ibm.com [9.17.130.20]) by d03dlp02.boulder.ibm.com (Postfix) with ESMTP id 707283E4005B for ; Tue, 26 Nov 2013 12:28:12 -0700 (MST) Received: from d03av06.boulder.ibm.com (d03av06.boulder.ibm.com [9.17.195.245]) by b03cxnp08028.gho.boulder.ibm.com (8.13.8/8.13.8/NCO v10.0) with ESMTP id rAQHQNeG37617800 for ; Tue, 26 Nov 2013 18:26:23 +0100 Received: from d03av06.boulder.ibm.com (loopback [127.0.0.1]) by d03av06.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVout) with ESMTP id rAQJV6hR014244 for ; Tue, 26 Nov 2013 12:31:08 -0700 Date: Tue, 26 Nov 2013 11:28:07 -0800 From: "Paul E. McKenney" Subject: Re: [PATCH v6 4/5] MCS Lock: Barrier corrections Message-ID: <20131126192807.GC4137@linux.vnet.ibm.com> Reply-To: paulmck@linux.vnet.ibm.com References: <20131122215208.GD4138@linux.vnet.ibm.com> <20131123002542.GF4138@linux.vnet.ibm.com> <20131123013654.GG4138@linux.vnet.ibm.com> <20131123040507.GI4138@linux.vnet.ibm.com> <20131123112450.GA26801@gmail.com> <20131123170603.GL4138@linux.vnet.ibm.com> <20131126120218.GB6103@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20131126120218.GB6103@gmail.com> Sender: owner-linux-mm@kvack.org List-ID: To: Ingo Molnar Cc: Linus Torvalds , Tim Chen , Will Deacon , Ingo Molnar , Andrew Morton , Thomas Gleixner , "linux-kernel@vger.kernel.org" , linux-mm , "linux-arch@vger.kernel.org" , Waiman Long , Andrea Arcangeli , Alex Shi , Andi Kleen , Michel Lespinasse , Davidlohr Bueso , Matthew R Wilcox , Dave Hansen , Peter Zijlstra , Rik van Riel , Peter Hurley , Raghavendra K T , George Spelvin , "H. Peter Anvin" , Arnd Bergmann , Aswin Chandramouleeswaran , Scott J Norton , "Figo.zhang" On Tue, Nov 26, 2013 at 01:02:18PM +0100, Ingo Molnar wrote: > > * Paul E. McKenney wrote: > > > On Sat, Nov 23, 2013 at 12:24:50PM +0100, Ingo Molnar wrote: > > > > > > * Paul E. McKenney wrote: > > > > > > > > x86 does have that extra "Memory ordering obeys causality (memory > > > > > ordering respects transitive visibility)." rule, and the example > > > > > in the architecture manual (section 8.2.3.6 "Stores Are > > > > > Transitively Visible") seems to very much about this, but your > > > > > particular example is subtly different, so.. > > > > > > > > Indeed, my example needs CPU 1's -load- from y to be transitively > > > > visible, so I am nervous about this one as well. > > > > > > > > > I will have to ruminate on this. > > > > > > > > The rules on the left-hand column of page 5 of the below URL apply > > > > to this example more straightforwardly, but I don't know that Intel > > > > and AMD stand behind them: > > > > > > > > http://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf > > > > > > > > My guess is that x86 does guarantee this ordering, but at this point > > > > I would have to ask someone from Intel and AMD. > > > > > > An additional option might be to create a user-space testcase > > > engineered to hit all the exotic ordering situations, one that > > > might disprove any particular assumptions we have about the > > > behavior of hardware. (Back a decade ago when the x86 space first > > > introduced quad core CPUs with newfangled on-die cache coherency I > > > managed to demonstrate a causality violation by simulating kernel > > > locks in user-space, which turned out to be a hardware bug. Also, > > > when Hyperthreading/SMT was new it demonstrated many interesting > > > bugs never seen in practice before. So running stuff on real > > > hardware is useful.) > > > > > > And a cache coherency (and/or locking) test suite would be very > > > useful anyway, for so many other purposes as well: such as a new > > > platform/CPU bootstrap, or to prove the correctness of some fancy > > > new locking scheme people want to add. Maybe as an extension to > > > rcutorture, or a generalization of it? > > > > I have the locking counterpart of rcutorture on my todo list. ;-) > > > > Of course, we cannot prove locks correct via testing, but a quick > > test can often find a bug faster and more reliably than manual > > inspection. > > We cannot prove them correct via testing, but we can test our > hypothesis about how the platform works and chances are that if the > tests are smart enough then we will be proven wrong via an actual > failure if our assumptions are wrong. There actually is an open-source program designed to test this sort of hypothesis... http://diy.inria.fr/ Don't miss the advertisement at the bottom of the page. That said, you do need some machine time. Some of the invalid hypotheses have failure rates in the 1-in-a-billion range. ;-) Or you can read some of the papers that this group has written, some of which include failure rates from empirical testing. Here is the one for ARM and Power: http://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test7.pdf Thanx, Paul -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org