llvm dev - Feb 2016 - [isocpp-parallel] Proposal for new memory_order_consume definition

On Thu, Feb 25, 2016 at 04:46:50PM -0800, Hans Boehm
wrote:
> If carries_dependency affects semantics, then it should not be an
attribute.
I am not picky about the form of the marking.
> The original design, or at least my understanding of it, was that it not
> have semantics; it was only a suggestion to the compiler that it should
> preserve dependencies instead of inserting a fence at the call site.
> Dependency-based ordering would be preserved in either case.  But I think
> we're moving away from that view towards something that doesn't
quietly add
> fences.
Yes, we do need to allow typical implementations to avoid quiet fence
addition.
> I do not think we can quite get away with defining a dependency in a way
> that is unconditionally preserved by existing compilers, and thus I think
> that we do probably need annotations along the dependency path.  I just
> don't see a way to otherwise deal with the case in which a compiler
infers
> an equivalent pointer and dereferences that instead of the original.  This
> can happen under so many (unlikely but) hard-to-define conditions that it
> seems undefinable in an implementation-independent manner. "If the
> implementation is able then <the semantics change>" is, in my
opinion, not
> acceptable standards text.
Hmmm...

But we do already have something very similar with signed integer
overflow.  If the compiler can see a way to generate faster code that
does not handle the overflow case, then the semantics suddenly change
from twos-complement arithmetic to something very strange.  The standard
does not specify all the ways that the implementation might deduce that
faster code can be generated by ignoring the overflow case, it instead
simply says that signed integer overflow invoked undefined behavior.

And if that is a problem, you use unsigned integers instead of signed
integers.

So it seems that we should be able to do something very similar here.
If you don't use marking, and the compiler deduces that a given pointer
that carries a given dependency is equal to some other pointer not
carrying that same dependency, there is no dependency ordering.  And,
just as with the signed-integer-overflow case, if that is a problem for
you, you can mark the pointers that you intend to carry dependencies.

In both the signed-integer-overflow and pointer-value-deduction cases,
most use cases don't need to care.  In the integer case, this is because
most use cases have small integer values that don't overflow.  In the
pointer case, this is because when the data structure is composed of
lots of heap-allocated data items, the compiler really cannot deduce
anything.

Other safe pointer use cases involve statically allocated data items
whose contents are compile-time constants (thus avoiding the need for
any sort of ordering) and sentinel data items (as in the Linux kernel's
cicular linked lists) where there is no dereferencing.
> Thus I see no way to both avoid adding syntax to functions that preserve
> dependencies and continue to allow existing transformations that remove
> dependencies we care about, e.g. due to equality comparisons.  We can
> hopefully ensure that without annotations compilers break things with very
> low probability, so that there is a reasonable path forward for existing
> code relying on dependency ordering (which currently also breaks with very
> low probability unless you understand what the compiler is doing).  But I
> don't see a way for the standard to guarantee correctness without the
added
> syntax (or added optimization constraints that effectively assume all
> functions were annotated).
Your second sentence ("We can hopefully ensure...") does give me hope
that we might be able to reach agreement.  The intent of P0190R0 is
to define a subset of operations where dependencies will be carried.
Note that P0190R0 does call out comparisons as potentially unsafe.

							Thanx, Paul
> On Sat, Feb 20, 2016 at 11:53 AM, Paul E. McKenney <
> paulmck at linux.vnet.ibm.com> wrote:
> 
> > On Fri, Feb 19, 2016 at 09:15:16PM -0500, Tony V E wrote:
> > > There's at least one easy answer in there:
> > >
> > > > ‎If implementations must support annotation, what form
should that
> > >       annotation take?  P0190R0 recommends the
[[carries_dependency]]
> > >       attribute, but I am not picky as long as it can be (1)
applied
> > >       to all relevant pointer-like objects and (2) used in C as
well
> > >       as C++.  ;-)
> > >
> > > If an implementation must support it, then it is not an
annotation but a
> > keyword. So no [[]]
> >
> > I would be good with that approach, especially if the WG14 continues
> > to stay away from annotations.
> >
> > For whatever it is worth, the introduction of intrinsics for
comparisons
> > that avoid breaking dependencies enables the annotation to remain
> > optional.
> >
> >                                                         Thanx, Paul
> >
> > > Sent from my BlackBerry portable Babbage Device
> > >   Original Message
> > > From: Paul E. McKenney
> > > Sent: Thursday, February 18, 2016 4:58 AM
> > > To: parallel at lists.isocpp.org; linux-kernel at
vger.kernel.org;
> > linux-arch at vger.kernel.org; gcc at gcc.gnu.org; llvm-dev at
lists.llvm.org
> > > Reply To: parallel at lists.isocpp.org
> > > Cc: peterz at infradead.org; j.alglave at ucl.ac.uk; will.deacon
at arm.com;
> > dhowells at redhat.com; Ramana.Radhakrishnan at arm.com; luc.maranget
at inria.fr;
> > akpm at linux-foundation.org; Peter.Sewell at cl.cam.ac.uk;
> > torvalds at linux-foundation.org; mingo at kernel.org
> > > Subject: [isocpp-parallel] Proposal for new memory_order_consume
> > definition
> > >
> > > Hello!
> > >
> > > A proposal (quaintly identified as P0190R0) for a new
> > memory_order_consume
> > > definition may be found here:
> > >
> > >
http://www2.rdrop.com/users/paulmck/submission/consume.2016.02.10b.pdf
> > >
> > > As requested at the October C++ Standards Committee meeting, this
> > > is a follow-on to P0098R1 that picks one alternative and
describes
> > > it in detail. This approach focuses on existing practice, with
the
> > > goal of supporting existing code with existing compilers. In the
last
> > > clang/LLVM patch I saw for basic support of this change, you
could count
> > > the changed lines and still have lots of fingers and toes left
over.
> > > Those who have been following this story will recognize that this
is
> > > a very happy contrast to work that would be required to implement
the
> > > definition in the current standard.
> > >
> > > I expect that P0190R0 will be discussed at the upcoming C++
Standards
> > > Committee meeting taking place the week of February 29th. Points
of
> > > discussion are likely to include:
> > >
> > > o     May memory_order_consume dependency ordering be used in
> > > unannotated code? I believe that this must be the case,
> > > especially given that this is our experience base. P0190R0
> > > therefore recommends this approach.
> > >
> > > o     If memory_order_consume dependency ordering can be used in
> > > unannotated code, must implementations support annotation?
> > > I believe that annotation support should be required, at the very
> > > least for formal verification, which can be quite difficult to
> > > carry out on unannotated code. In addition, it seems likely
> > > that annotations can enable much better diagnostics. P0190R0
> > > therefore recommends this approach.
> > >
> > > o     If implementations must support annotation, what form
should that
> > > annotation take? P0190R0 recommends the [[carries_dependency]]
> > > attribute, but I am not picky as long as it can be (1) applied
> > > to all relevant pointer-like objects and (2) used in C as well
> > > as C++. ;-)
> > >
> > > o     If memory_order_consume dependency ordering can be used in
> > > unannotated code, how best to define the situations where
> > > the compiler can determine the exact value of the pointer in
> > > question? (In current defacto implementations, this can
> > > defeat dependency ordering. Interestingly enough, this case
> > > is not present in the Linux kernel, but still needs to be
> > > defined.)
> > >
> > > Options include:
> > >
> > > o     Provide new intrinsics that carry out the
> > > comparisons, but guarantee to preserve dependencies,
> > > as recommended by P0190R0 (std::pointer_cmp_eq_dep(),
> > > std::pointer_cmp_ne_dep(), std::pointer_cmp_gt_dep(),
> > > std::pointer_cmp_ge_dep(), std::pointer_cmp_lt_dep(),
> > > and std::pointer_cmp_le_dep()).
> > >
> > > o     State that -any- comparison involving an unannotated
> > > pointer loses the dependency.
> > >
> > > o     How is the common idiom of marking pointers by setting
low-order
> > > bits to be supported when those pointers carry dependencies?
> > > At the moment, I believe that setting bits in pointers results in
> > > undefined behavior even without dependency ordering, so P0190R0
> > > kicks this particular can down the road. One option that
> > > has been suggested is to provide intrinsics for this purpose.
> > > (Sorry, but I forget who suggested this.)
> > >
> > > Thoughts?
> > >
> > > Thanx, Paul
> > >
> > > _______________________________________________
> > > Parallel mailing list
> > > Parallel at lists.isocpp.org
> > > Subscription:
http://lists.isocpp.org/mailman/listinfo.cgi/parallel
> > > Link to this post:
http://lists.isocpp.org/parallel/2016/02/0040.php
> > > _______________________________________________
> > > Parallel mailing list
> > > Parallel at lists.isocpp.org
> > > Subscription:
http://lists.isocpp.org/mailman/listinfo.cgi/parallel
> > > Link to this post:
http://lists.isocpp.org/parallel/2016/02/0045.php
> >
> > _______________________________________________
> > Parallel mailing list
> > Parallel at lists.isocpp.org
> > Subscription: http://lists.isocpp.org/mailman/listinfo.cgi/parallel
> > Link to this post: http://lists.isocpp.org/parallel/2016/02/0046.php
> _______________________________________________
> Parallel mailing list
> Parallel at lists.isocpp.org
> Subscription: http://lists.isocpp.org/mailman/listinfo.cgi/parallel
> Link to this post: http://lists.isocpp.org/parallel/2016/02/0049.php

On Feb 27, 2016 09:06, "Paul E. McKenney" <paulmck at
linux.vnet.ibm.com>
wrote:
>
>
> But we do already have something very similar with signed integer
> overflow.  If the compiler can see a way to generate faster code that
> does not handle the overflow case, then the semantics suddenly change
> from twos-complement arithmetic to something very strange.  The standard
> does not specify all the ways that the implementation might deduce that
> faster code can be generated by ignoring the overflow case, it instead
> simply says that signed integer overflow invoked undefined behavior.
>
> And if that is a problem, you use unsigned integers instead of signed
> integers.
Actually, in the case of there Linux kernel we just tell the compiler to
not be an ass. We use

  -fno-strict-overflow

or something. I forget the exact compiler flag needed for "the standard is
as broken piece of shit and made things undefined for very bad reasons".

See also there idiotic standard C alias rules. Same deal.

So no, standards aren't that important. When the standards screw up, the
right answer is not to turn the other cheek.

And undefined behavior is pretty much *always* a sign of "the standard is
wrong".

     Linus
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160227/074cc591/attachment.html>

On Sat, Feb 27, 2016 at 11:16:51AM -0800, Linus Torvalds
wrote:
> On Feb 27, 2016 09:06, "Paul E. McKenney" <paulmck at
linux.vnet.ibm.com>
> wrote:
> >
> >
> > But we do already have something very similar with signed integer
> > overflow.  If the compiler can see a way to generate faster code that
> > does not handle the overflow case, then the semantics suddenly change
> > from twos-complement arithmetic to something very strange.  The
standard
> > does not specify all the ways that the implementation might deduce
that
> > faster code can be generated by ignoring the overflow case, it instead
> > simply says that signed integer overflow invoked undefined behavior.
> >
> > And if that is a problem, you use unsigned integers instead of signed
> > integers.
> 
> Actually, in the case of there Linux kernel we just tell the compiler to
> not be an ass. We use
> 
>   -fno-strict-overflow
That is the one!
> or something. I forget the exact compiler flag needed for "the
standard is
> as broken piece of shit and made things undefined for very bad
reasons".
> 
> See also there idiotic standard C alias rules. Same deal.
For which we use -fno-strict-aliasing.
> So no, standards aren't that important. When the standards screw up,
the
> right answer is not to turn the other cheek.
Agreed, hence my current (perhaps quixotic and insane) attempt to get
the standard to do something useful for dependency ordering.  But if
that doesn't work, yes, a fallback position is to get the relevant
compilers to provide flags to avoid problematic behavior, similar to
-fno-strict-overflow.

							Thanx, Paul
> And undefined behavior is pretty much *always* a sign of "the standard
is
> wrong".
> 
>      Linus

Hi,

On Sat, 27 Feb 2016, Paul E. McKenney wrote:
> But we do already have something very similar with signed integer
> overflow.  If the compiler can see a way to generate faster code that
> does not handle the overflow case, then the semantics suddenly change
> from twos-complement arithmetic to something very strange.  The standard
> does not specify all the ways that the implementation might deduce that
> faster code can be generated by ignoring the overflow case, it instead
> simply says that signed integer overflow invoked undefined behavior.
> 
> And if that is a problem, you use unsigned integers instead of signed
> integers.
> 
> So it seems that we should be able to do something very similar here.
For this case the important pice of information to convey one or the other 
meaning in source code is the _type_ of involved entities, not annotations 
on the operations.  signed type -> undefined overflow, unsigned type -> 
modulo arithmetic; easy, and it nicely carries automatically through 
operation chains (and pointers) without any annotations.

I feel much of the complexity in the memory order specifications, also 
with your recent (much better) wording to explain dependency chains, would 
be much easier if the 'carries-dependency' would be encoded into the
types
of operands.  For purpose of example, let's call the marker
"blaeh" (not
atomic to not confuse with existing use :) ):

int foo;
blaeh int global;
int *somep;
blae int *blaehp;
f () {
  blaehp = &foo;  // might be okay, adds restrictions on accesses through 
                  // blaehp, but not through 'foo' directly
  blaehp = &global;
  if (somep == blaehp)
    {
      /* Even though the value is equal ... */
      ... *blaehp ... /* ... a compiler can't rewrite this into *somep */
    }
}

A "carries-dependency" on some operation (e.g. a call) would be added
by
using a properly typed pointer at those arguments (or return type) where 
it matters.  You can't give a blaeh pointer to something only accepting 
non-blaeh pointers (without cast).

Pointer addition and similar transformations involving a blaeh pointer and 
some integer would still give a blaeh pointer, and hence by default also 
solve the problem of cancellations.

Such marking via types would not solve all problems in an optimal way if 
you had two overlapping but independend dependency chains (all of them 
would collapse to one chain and hence made dependend, which still is 
conservatively correct).

OTOH introducing new type qualifiers is a much larger undertaking, so I 
can understand one wants to avoid this.  I think it'd ultimately be 
clearer, though.


Ciao,
Michael.

On Mon, Feb 29, 2016 at 07:17:55PM +0100, Michael Matz
wrote:
> Hi,
> 
> On Sat, 27 Feb 2016, Paul E. McKenney wrote:
> 
> > But we do already have something very similar with signed integer
> > overflow.  If the compiler can see a way to generate faster code that
> > does not handle the overflow case, then the semantics suddenly change
> > from twos-complement arithmetic to something very strange.  The
standard
> > does not specify all the ways that the implementation might deduce
that
> > faster code can be generated by ignoring the overflow case, it instead
> > simply says that signed integer overflow invoked undefined behavior.
> > 
> > And if that is a problem, you use unsigned integers instead of signed
> > integers.
> > 
> > So it seems that we should be able to do something very similar here.
> 
> For this case the important pice of information to convey one or the other 
> meaning in source code is the _type_ of involved entities, not annotations 
> on the operations.  signed type -> undefined overflow, unsigned type
->
> modulo arithmetic; easy, and it nicely carries automatically through 
> operation chains (and pointers) without any annotations.
> 
> I feel much of the complexity in the memory order specifications, also 
> with your recent (much better) wording to explain dependency chains, would 
> be much easier if the 'carries-dependency' would be encoded into
the types
> of operands.  For purpose of example, let's call the marker
"blaeh" (not
> atomic to not confuse with existing use :) ):
> 
> int foo;
> blaeh int global;
> int *somep;
> blae int *blaehp;
> f () {
>   blaehp = &foo;  // might be okay, adds restrictions on accesses
through
>                   // blaehp, but not through 'foo' directly
>   blaehp = &global;
>   if (somep == blaehp)
>     {
>       /* Even though the value is equal ... */
>       ... *blaehp ... /* ... a compiler can't rewrite this into *somep
*/
>     }
> }
> 
> A "carries-dependency" on some operation (e.g. a call) would be
added by
> using a properly typed pointer at those arguments (or return type) where 
> it matters.  You can't give a blaeh pointer to something only accepting
> non-blaeh pointers (without cast).
> 
> Pointer addition and similar transformations involving a blaeh pointer and 
> some integer would still give a blaeh pointer, and hence by default also 
> solve the problem of cancellations.
> 
> Such marking via types would not solve all problems in an optimal way if 
> you had two overlapping but independend dependency chains (all of them 
> would collapse to one chain and hence made dependend, which still is 
> conservatively correct).
> 
> OTOH introducing new type qualifiers is a much larger undertaking, so I 
> can understand one wants to avoid this.  I think it'd ultimately be 
> clearer, though.
As has been stated in this thread, we do need the unmarked variant.

For the marked variant, there are quite a few possible solutions with
varying advantages and disadvantages:

o	Attribute already exists, but is not carried by the type system.
	Could be enforced by external tools.

o	Storage class could be added with fewer effects on the type
	system, but the reaction to this suggestion in October was
	not all that positive.

o	Non-type keywords for objects has been suggested, might be worth
	revisiting.

o	Adding to the type system allows type enforcement on the one
	hand, but makes it harder to write code that can be used for
	both RCU-protected and not-RCU-protected data structures.
	(This sort of thing is not uncommon in the Linux kernel.)

There are probably others, but those are the ones I recall at the
moment.

							Thanx, Paul