From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-11.6 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,INCLUDES_PATCH,MAILING_LIST_MULTI, SIGNED_OFF_BY,SPF_HELO_NONE,SPF_PASS,USER_AGENT_SANE_1 autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 3C5AAC55178 for ; Fri, 6 Nov 2020 21:04:16 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id D35E120B1F for ; Fri, 6 Nov 2020 21:04:15 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=default; t=1604696655; bh=hwQEv77hfg2ALYPp40IFvR42QifSfVT6ekrYmdYIs9o=; h=Date:From:To:Cc:Subject:Reply-To:References:In-Reply-To:List-ID: From; b=KID7aXC/T/60eqYansYZOw9fCklNJihMMibEwj7Ps6oiNV9P9YZ++j1Fbvo+IPdOd MQ1LP8TdtFYvBPEFaO/xSG3SNi7F+0zNJVr4+1vOMp3r/9m3iA3734o4pF64FctvVX Qg1JV5xeU9HilhZuk8Fnixxd9pxDAdCdGX7ImAws= Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728408AbgKFVEP (ORCPT ); Fri, 6 Nov 2020 16:04:15 -0500 Received: from mail.kernel.org ([198.145.29.99]:44722 "EHLO mail.kernel.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727129AbgKFVEP (ORCPT ); Fri, 6 Nov 2020 16:04:15 -0500 Received: from paulmck-ThinkPad-P72.home (50-39-104-11.bvtn.or.frontiernet.net [50.39.104.11]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPSA id 04EA92087E; Fri, 6 Nov 2020 21:04:14 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=default; t=1604696654; bh=hwQEv77hfg2ALYPp40IFvR42QifSfVT6ekrYmdYIs9o=; h=Date:From:To:Cc:Subject:Reply-To:References:In-Reply-To:From; b=sheCi9M9Xfkd8PO/lUaH1mIXhDcCYxmbn9DijjxDe5I6TO9tteoxGD883/SQFIrz/ Oj1z2of8cp8KLVY72fpSi2qlIUvAHEGYWQEDzrDyv2vWyYdMVKVOnJCtszoawrIdD9 /Ay9HdWByEUGZ9YihV3w6ZkP1SXzAfYSLxXXAnm8= Received: by paulmck-ThinkPad-P72.home (Postfix, from userid 1000) id 942CC352131F; Fri, 6 Nov 2020 13:04:13 -0800 (PST) Date: Fri, 6 Nov 2020 13:04:13 -0800 From: "Paul E. McKenney" To: Alan Stern Cc: linux-kernel@vger.kernel.org, linux-arch@vger.kernel.org, kernel-team@fb.com, mingo@kernel.org, parri.andrea@gmail.com, will@kernel.org, peterz@infradead.org, boqun.feng@gmail.com, npiggin@gmail.com, dhowells@redhat.com, j.alglave@ucl.ac.uk, luc.maranget@inria.fr, akiyks@gmail.com Subject: Re: [PATCH memory-model 5/8] tools/memory-model: Add a glossary of LKMM terms Message-ID: <20201106210413.GB3249@paulmck-ThinkPad-P72> Reply-To: paulmck@kernel.org References: <20201105215953.GA15309@paulmck-ThinkPad-P72> <20201105220017.15410-5-paulmck@kernel.org> <20201106165930.GC47039@rowland.harvard.edu> <20201106180445.GX3249@paulmck-ThinkPad-P72> <20201106192351.GA53131@rowland.harvard.edu> <20201106195912.GA3249@paulmck-ThinkPad-P72> <20201106204008.GA55521@rowland.harvard.edu> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20201106204008.GA55521@rowland.harvard.edu> User-Agent: Mutt/1.9.4 (2018-02-28) Precedence: bulk List-ID: X-Mailing-List: linux-arch@vger.kernel.org On Fri, Nov 06, 2020 at 03:40:08PM -0500, Alan Stern wrote: > On Fri, Nov 06, 2020 at 11:59:12AM -0800, Paul E. McKenney wrote: > > On Fri, Nov 06, 2020 at 02:23:51PM -0500, Alan Stern wrote: > > > On Fri, Nov 06, 2020 at 10:04:46AM -0800, Paul E. McKenney wrote: > > > > On Fri, Nov 06, 2020 at 11:59:30AM -0500, Alan Stern wrote: > > > > > > + See also "Control Dependency". > > > > > > > > > > There should also be an entry for "Data Dependency", linked from here > > > > > and from Control Dependency. > > > > > > > > > > > +Marked Access: An access to a variable that uses an special function or > > > > > > + macro such as "r1 = READ_ONCE()" or "smp_store_release(&a, 1)". > > > > > > > > > > How about "r1 = READ_ONCE(x)"? > > > > > > > > Good catches! I am planning to squash the commit below into the > > > > original. Does that cover it? > > > > > > No, because you didn't add a glossary entry for "Data Dependency" and > > > there's no link from "Control Dependency" to "Data Dependency". > > > > Sigh. I was thinking "entry in the list", and didn't even thing to > > check for an entry in the glossary as a whole. With the patch below > > (on top of the one sent earlier), are we good? > > > > Thanx, Paul > > > > ------------------------------------------------------------------------ > > > > commit 5a49c32551e83d30e304d6c3fbb660737ba2654e > > Author: Paul E. McKenney > > Date: Fri Nov 6 11:57:25 2020 -0800 > > > > fixup! tools/memory-model: Add a glossary of LKMM terms > > > > Signed-off-by: Paul E. McKenney > > > > diff --git a/tools/memory-model/Documentation/glossary.txt b/tools/memory-model/Documentation/glossary.txt > > index 471bf13..b2da636 100644 > > --- a/tools/memory-model/Documentation/glossary.txt > > +++ b/tools/memory-model/Documentation/glossary.txt > > @@ -64,7 +64,7 @@ Control Dependency: When a later store's execution depends on a test > > fragile, and can be easily destroyed by optimizing compilers. > > Please see control-dependencies.txt for more information. > > > > - See also "Address Dependency". > > + See also "Address Dependency" and "Data Dependency". > > > > Cycle: Memory-barrier pairing is restricted to a pair of CPUs, as the > > name suggests. And in a great many cases, a pair of CPUs is all > > @@ -85,6 +85,23 @@ Cycle: Memory-barrier pairing is restricted to a pair of CPUs, as the > > > > See also "Pairing". > > > > +Data Dependency: When the data written by a later store is computed based > > + on the value returned by an earlier load, a "data dependency" > > + extends from that load to that later store. For example: > > + > > + 1 r1 = READ_ONCE(x); > > + 2 WRITE_ONCE(y, r1 + 1); > > + > > + In this case, the data dependency extends from the READ_ONCE() > > + on line 1 to the WRITE_ONCE() on line 2. Data dependencies are > > + fragile and can be easily destroyed by optimizing compilers. > > + Because optimizing compilers put a great deal of effort into > > + working out what values integer variables might have, this is > > + especially true in cases where the dependency is carried through > > + an integer. > > + > > + See also "Address Dependency" and "Control Dependency". > > + > > From-Reads (fr): When one CPU's store to a given variable happened > > too late to affect the value returned by another CPU's > > load from that same variable, there is said to be a from-reads > > Yes, this is better. Thank you for bearing with me on this! > Is it really true that data dependencies are so easily destroyed? I > would expect that a true "semantic" dependency (i.e., one where the > value written really does vary according to the value read) would be > rather hard to second guess. The usual optimizations apply, for but one example: r1 = READ_ONCE(x); WRITE_ONCE(y, (r1 + 1) % MAX_ELEMENTS); If MAX_ELEMENTS is 1, so long, data dependency! With pointers, the compiler has fewer optimization opportunities, but there are still cases where it can break the dependency. Or transform it to a control dependency. Thanx, Paul