Message-ID: <20140227175021.GT8264@linux.vnet.ibm.com>
Date:	Thu, 27 Feb 2014 09:50:21 -0800
From:	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
To:	Torvald Riegel <triegel@...hat.com>
Cc:	Linus Torvalds <torvalds@...ux-foundation.org>,
	Will Deacon <will.deacon@....com>,
	Peter Zijlstra <peterz@...radead.org>,
	Ramana Radhakrishnan <Ramana.Radhakrishnan@....com>,
	David Howells <dhowells@...hat.com>,
	"linux-arch@...r.kernel.org" <linux-arch@...r.kernel.org>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
	"akpm@...ux-foundation.org" <akpm@...ux-foundation.org>,
	"mingo@...nel.org" <mingo@...nel.org>,
	"gcc@....gnu.org" <gcc@....gnu.org>
Subject: Re: [RFC][PATCH 0/5] arch: atomic rework

On Thu, Feb 27, 2014 at 04:37:33PM +0100, Torvald Riegel wrote:
> xagsmtp2.20140227154925.3851@...dvm9.vnet.ibm.com
> 
> On Mon, 2014-02-24 at 11:54 -0800, Linus Torvalds wrote:
> > On Mon, Feb 24, 2014 at 10:53 AM, Paul E. McKenney
> > <paulmck@...ux.vnet.ibm.com> wrote:
> > >
> > > Good points.  How about the following replacements?
> > >
> > > 3.      Adding or subtracting an integer to/from a chained pointer
> > >         results in another chained pointer in that same pointer chain.
> > >         The results of addition and subtraction operations that cancel
> > >         the chained pointer's value (for example, "p-(long)p" where "p"
> > >         is a pointer to char) are implementation defined.
> > >
> > > 4.      Bitwise operators ("&", "|", "^", and I suppose also "~")
> > >         applied to a chained pointer and an integer for the purposes
> > >         of alignment and pointer translation results in another
> > >         chained pointer in that same pointer chain.  Other uses
> > >         of bitwise operators on chained pointers (for example,
> > >         "p|~0") are implementation defined.
> > 
> > Quite frankly, I think all of this language that is about the actual
> > operations is irrelevant and wrong.
> > 
> > It's not going to help compiler writers, and it sure isn't going to
> > help users that read this.
> > 
> > Why not just talk about "value chains" and that any operations that
> > restrict the value range severely end up breaking the chain. There is
> > no point in listing the operations individually, because every single
> > operation *can* restrict things. Listing individual operations and
> > depdendencies is just fundamentally wrong.
> 
> [...]
> 
> > The *only* thing that matters for all of them is whether they are
> > "value-preserving", or whether they drop so much information that the
> > compiler might decide to use a control dependency instead. That's true
> > for every single one of them.
> > 
> > Similarly, actual true control dependencies that limit the problem
> > space sufficiently that the actual pointer value no longer has
> > significant information in it (see the above example) are also things
> > that remove information to the point that only a control dependency
> > remains. Even when the value itself is not modified in any way at all.
> 
> I agree that just considering syntactic properties of the program seems
> to be insufficient.  Making it instead depend on whether there is a
> "semantic" dependency due to a value being "necessary" to compute a
> result seems better.  However, whether a value is "necessary" might not
> be obvious, and I understand Paul's argument that he does not want to
> have to reason about all potential compiler optimizations.  Thus, I
> believe we need to specify when a value is "necessary".
> 
> I have a suggestion for a somewhat different formulation of the feature
> that you seem to have in mind, which I'll discuss below.  Excuse the
> verbosity of the following, but I'd rather like to avoid
> misunderstandings than save a few words.

Thank you very much for putting this forward!  I must confess that I was
stuck, and my earlier attempt now enshrined in the C11 and C++11 standards
is quite clearly way bogus.

One possible saving grace:  From discussions at the standards committee
meeting a few weeks ago, there is a some chance that the committee will
be willing to do a rip-and-replace on the current memory_order_consume
wording, without provisions for backwards compatibility with the current
bogosity.

> What we'd like to capture is that a value originating from a mo_consume
> load is "necessary" for a computation (e.g., it "cannot" be replaced
> with value predictions and/or control dependencies); if that's the case
> in the program, we can reasonably assume that a compiler implementation
> will transform this into a data dependency, which will then lead to
> ordering guarantees by the HW.
> 
> However, we need to specify when a value is "necessary".  We could say
> that this is implementation-defined, and use a set of litmus tests
> (e.g., like those discussed in the thread) to roughly carve out what a
> programmer could expect.  This may even be practical for a project like
> the Linux kernel that follows strict project-internal rules and pays a
> lot of attention to what the particular implementations of compilers
> expected to compile the kernel are doing.  However, I think this
> approach would be too vague for the standard and for many other
> programs/projects.

I agree that a number of other projects would have more need for this than
might the kernel.  Please understand that this is in no way denigrating
the intelligence of other projects' members.  It is just that many of
them have only recently started seriously thinking about concurrency.
In contrast, the Linux kernel community has been doing concurrency since
the mid-1990s.  Projects with less experience with concurrency will
probably need more help, from the compiler and from elsewhere as well.

Your proposal looks quite promising at first glance.  But rather than
try and comment on it immediately, I am going to take a number of uses of
RCU from the Linux kernel and apply your proposal to them, then respond
with the results

Fair enough?

							Thanx, Paul

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists