Fix memory orders description in atomic ops built-ins docs.

On Mon, 2015-05-18 at 17:36 +0100, Matthew Wahab wrote:
> Hello,
> 
> On 15/05/15 17:22, Torvald Riegel wrote:
> > This patch improves the documentation of the built-ins for atomic
> > operations.
> 
> The "memory model" to "memory order" change does improve things but I think that
> the patch has some problems. As it is now, it makes some of the descriptions
> quite difficult to understand and seems to assume more familiarity with details
> of the C++11 specification then might be expected.

I'd say that's a side effect of the C++11 memory model being the
reference specification of the built-ins.

> Generally, the memory order descriptions seem to be targeted towards language
> designers but don't provide for anybody trying to understand how to implement or
> to use the built-ins.

I agree that the current descriptions aren't a tutorial on the C++11
memory model.  However, given that the model is not GCC-specific, we
aren't really in a need to provide a tutorial, in the same way that we
don't provide a C++ tutorial.  Users can pick the C++11 memory model
educational material of their choice, and we need to document what's
missing to apply the C++11 knowledge to the built-ins we provide.

There are several resources for implementers, for example the mappings
maintained by the Cambridge research group.  I guess it would be
sufficient to have such material on the wiki.  Is there something
specific that you'd like to see documented for implementers?

> Adding a less formal, programmers view to some of the
> descriptions would help.

Yes, probably.  However, I'm not aware of a good C++11 memory model
tutorial that we could link too (OTOH, I haven't really looked for one).
I don't plan to write one, and doing so would certainly take some time
and require *much* more text than what we have now.

> That implies the descriptions would be more than just
> illustrative, but I'd suggest that would be appropriate for the GCC manual.

The danger I see there is that if we claim to define semantics instead
of just illustrating them, then we need to do a really good job of
defining/explaining them.  I worry that we may end up replicating what's
in the standard or Batty et al.'s formalization of the memory model, and
having to give a tutorial too.  I'm not sure anyone is volunteering to
do that amount of work.

> I'm also not sure that the use of C++11 terms in the some of the
> descriptions. In particular, using happens-before seems wrong because
> happens-before isn't described anywhere in the GCC manual and because it has a
> specific meaning in the C++11 specification that doesn't apply to the GCC
> built-ins (which C++11 doesn't know about).

I agree it's not described in the manual, but we're implementing C++11.
However, I don't see why happens-before semantics wouldn't apply to
GCC's implementation of the built-ins; there may be cases where we
guarantee more, but if one uses the builtins in way allowed by the C++11
model, one certainly gets behavior and happens-before relationships as
specified by C++11.


> diff --git a/gcc/doc/extend.texi b/gcc/doc/extend.texi
> index 6004681..5b2ded8 100644
> --- a/gcc/doc/extend.texi
> +++ b/gcc/doc/extend.texi
> @@ -8853,19 +8853,19 @@ are not prevented from being speculated to before the barrier.
> 
>   [...]  If the data type size maps to one
> -of the integral sizes that may have lock free support, the generic
> -version uses the lock free built-in function.  Otherwise an
> +of the integral sizes that may support lock-freedom, the generic
> +version uses the lock-free built-in function.  Otherwise an
>   external call is left to be resolved at run time.
> 
> =====
> This is a slightly awkward sentence. Maybe it could be replaced with something
> on the lines of "The generic function uses the lock-free built-in function when
> the data-type size makes that possible, otherwise an external call is left to be
> resolved at run-time."
> =====

Changed to:
"It uses the lock-free built-in function if the specific data type size
makes that possible; otherwise, an external call is left to be resolved
at run time."

> 
> -The memory models integrate both barriers to code motion as well as
> -synchronization requirements with other threads.  They are listed here
> -in approximately ascending order of strength.
> +An atomic operation can both constrain code motion by the compiler and
> +be mapped to a hardware instruction for synchronization between threads
> +(e.g., a fence).  [...]
> 
> =====
> This is a little unclear (and inaccurate, aarch64 can use two instructions
> for fences). I also thought that atomic operations constrain code motion by the
> hardware. Maybe break the link with the compiler and hardware: "An atomic
> operation can both constrain code motion and act as a synchronization point
> between threads".
> =====

I removed "by the compiler" and used "hardware instruction_s_".

> 
>   @table  @code
>   @item __ATOMIC_RELAXED
> -No barriers or synchronization.
> +Implies no inter-thread ordering constraints.
> 
> ====
> It may be useful to be explicit that there are no restrctions on code motion.
> ====

But there are restrictions, for example those related to the forward
progress requirements or the coherency rules.

> 
>   @item __ATOMIC_CONSUME
> -Data dependency only for both barrier and synchronization with another
> -thread.
> +This is currently implemented using the stronger @code{__ATOMIC_ACQUIRE}
> +memory order because of a deficiency in C++11's semantics for
> +@code{memory_order_consume}.
> 
> =====
> It would be useful to have a description of what the __ATOMIC_CONSUME was
> meant to do, as well as the fact that it currently just maps to
> __ATOMIC_ACQUIRE. (Or maybe just drop it from the documentation until it's
> fixed.)
> =====

I'll leave what it was meant to do to the ISO C++ discussions.  I think
that it's implemented using mo_acquire is already clear from the text,
or not?

> 
>   @item __ATOMIC_ACQUIRE
> -Barrier to hoisting of code and synchronizes with release (or stronger)
> -semantic stores from another thread.
> +Creates an inter-thread happens-before constraint from the release (or
> +stronger) semantic store to this acquire load.  Can prevent hoisting
> +of code to before the operation.
> 
> =====
> As noted before, it's not clear what the "inter-thread happens-before"
> means in this context.

I don't see a way to make this truly freestanding without replicating
the specification of the C++11 memory model.

> Here and elsewhere:
> "Can prevent <motion> of code" is ambiguous: it doesn't say under what
> conditions code would or wouldn't be prevented from moving.

Yes, it's not a specification but just an illustration of what can
result from the specification.  Describing which code movement is
allowed or not, precisely, is way too much detail IMO.  There are full
ISO C++ papers about that (N4455), and even those aren't enumerations of
all allowed code transformations.

> =====
> 
> -Note that the scope of a C++11 memory model depends on whether or not
> -the function being called is a @emph{fence} (such as
> -@samp{__atomic_thread_fence}).  In a fence, all memory accesses are
> -subject to the restrictions of the memory model.  When the function is
> -an operation on a location, the restrictions apply only to those
> -memory accesses that could affect or that could depend on the
> -location.
> +Note that in the C++11 memory model, @emph{fences} (e.g.,
> +@samp{__atomic_thread_fence}) take effect in combination with other
> +atomic operations on specific memory locations (e.g., atomic loads);
> +operations on specific memory locations do not necessarily affect other
> +operations in the same way.
> 
> ====
> Its very unclear what this paragraph is saying. It seems to suggest that fences
> only work in combination with other operations. But that doesn't seem right
> since a __atomic_thread_fence (with appropriate memory order) can be dropped
> into any piece of code and will act in the way that memory barriers are commonly
> understood to work.

Not quite.  If you control the code generation around the fence (e.g.,
so you control which loads/stores a compiler generates), and know which
HW instruction the C++ fence maps too, you can try use it this way.

However, that's not what the built-in is specified to result in --
instead, it's specified to implement a C++ fence.  And those take effect
in combination with the reads-from relation etc., for which one needs to
use atomic operations that access specific memory locations.

> ====
> 
>   @@ -9131,5 +9135,5 @@ if (_atomic_always_lock_free (sizeof (long long), 0))
>   @deftypefn {Built-in Function} bool __atomic_is_lock_free (size_t size, void *ptr)
> 
>   This built-in function returns true if objects of @var{size} bytes always
> +generate lock-free atomic instructions for the target architecture.  If
> +it is not known to be lock-free, a call is made to a runtime routine named
> ====
> Probably unrelated to the point of this patch but does this mean
> "If this built-in function is not known to be lock-free .."?
> ====
> 

Yes, fixed.

I've also fixed s/model/order/ in the HLE built-ins docs and fixed a
typo there too.

Unless there are objections, I plan to commit the attached patch at the
end of this week.

On 19/05/15 20:20, Torvald Riegel wrote:
> On Mon, 2015-05-18 at 17:36 +0100, Matthew Wahab wrote:
>> Hello,
>>
>> On 15/05/15 17:22, Torvald Riegel wrote:
>>> This patch improves the documentation of the built-ins for atomic
>>> operations.
>>
>> The "memory model" to "memory order" change does improve things but I think that
>> the patch has some problems. As it is now, it makes some of the descriptions
>> quite difficult to understand and seems to assume more familiarity with details
>> of the C++11 specification then might be expected.
>
> I'd say that's a side effect of the C++11 memory model being the
> reference specification of the built-ins.
>
>> Generally, the memory order descriptions seem to be targeted towards language
>> designers but don't provide for anybody trying to understand how to implement or
>> to use the built-ins.
>
> I agree that the current descriptions aren't a tutorial on the C++11
> memory model.  However, given that the model is not GCC-specific, we
> aren't really in a need to provide a tutorial, in the same way that we
> don't provide a C++ tutorial.  Users can pick the C++11 memory model
> educational material of their choice, and we need to document what's
> missing to apply the C++11 knowledge to the built-ins we provide.
>

We seem to have different views about the purpose of the manual page. I'm treating it 
as a description of the built-in functions provided by gcc to generate the code 
needed to implement the C++11 model. That is, the built-ins are distinct from C++11 
and their descriptions should be, as far as possible, independent of the methods used 
in the C++11 specification to describe the C++11 memory model.

I understand of course that the __atomics were added in order to support C++11 but 
that doesn't make them part of C++11 and, since __atomic functions can be made 
available when C11/C++11 may not be, it seems to make sense to try for stand-alone 
descriptions.

I'm also concerned that the patch, by describing things in terms of formal C++11 
concepts, makes it more difficult for people to know what the built-ins can be 
expected to do and so make the built-in more difficult to use There is a danger that 
rather than take a risk with uncertainty about the behaviour of the __atomics, people 
will fall-back to the __sync functions simply because their expected behaviour is 
easier to work out.

I don't think that linking to external sites will help either, unless people already 
want to know C++11. Anybody who just wants to (e.g.) add a memory barrier will take 
one look at the __sync manual page and use the closest match from there instead.

Note that none of this requires a tutorial of any kind. I'm just suggesting that the 
manual should describe what behaviour should be expected of the code generated for 
the functions. For the memory orders, that would mean describing what constraints 
need to be met by the generated code. The requirement that the atomics should support 
C++11 could be met by making sure that the description of the expected behaviour is 
sufficient for C++11.

> There are several resources for implementers, for example the mappings
> maintained by the Cambridge research group.  I guess it would be
> sufficient to have such material on the wiki.  Is there something
> specific that you'd like to see documented for implementers?
> [...]
> I agree it's not described in the manual, but we're implementing C++11.

(As above) I believe we're supporting the implementation of C++11 and that the 
distinction is important.

> However, I don't see why happens-before semantics wouldn't apply to
> GCC's implementation of the built-ins; there may be cases where we
> guarantee more, but if one uses the builtins in way allowed by the C++11
> model, one certainly gets behavior and happens-before relationships as
> specified by C++11.
>

My understanding is that happens-before is a relation used in the C++11 specification 
for a specific meaning. I believe that it's used to decide whether something is or is 
not a data race so saying that it applies to a gcc built-in would be wrong. Using the 
gcc built-in rather than the equivalent C++11 library function would result in 
program that C++11 regards as invalid. (Again, as I understand it.)

>
>> diff --git a/gcc/doc/extend.texi b/gcc/doc/extend.texi
>> index 6004681..5b2ded8 100644
>> --- a/gcc/doc/extend.texi
>> +++ b/gcc/doc/extend.texi
>> @@ -8853,19 +8853,19 @@ are not prevented from being speculated to before the barrier.
>>
>>    [...]  If the data type size maps to one
>> -of the integral sizes that may have lock free support, the generic
>> -version uses the lock free built-in function.  Otherwise an
>> +of the integral sizes that may support lock-freedom, the generic
>> +version uses the lock-free built-in function.  Otherwise an
>>    external call is left to be resolved at run time.
>>
>> =====
>> This is a slightly awkward sentence. Maybe it could be replaced with something
>> on the lines of "The generic function uses the lock-free built-in function when
>> the data-type size makes that possible, otherwise an external call is left to be
>> resolved at run-time."
>> =====
>
> Changed to:
> "It uses the lock-free built-in function if the specific data type size
> makes that possible; otherwise, an external call is left to be resolved
> at run time."

Ok for me.

>> -The memory models integrate both barriers to code motion as well as
>> -synchronization requirements with other threads.  They are listed here
>> -in approximately ascending order of strength.
>> +An atomic operation can both constrain code motion by the compiler and
>> +be mapped to a hardware instruction for synchronization between threads
>> +(e.g., a fence).  [...]
>>
>> =====
>> This is a little unclear (and inaccurate, aarch64 can use two instructions
>> for fences). I also thought that atomic operations constrain code motion by the
>> hardware. Maybe break the link with the compiler and hardware: "An atomic
>> operation can both constrain code motion and act as a synchronization point
>> between threads".
>> =====
>
> I removed "by the compiler" and used "hardware instruction_s_".

Ok.

>>    @table  @code
>>    @item __ATOMIC_RELAXED
>> -No barriers or synchronization.
>> +Implies no inter-thread ordering constraints.
>>
>> ====
>> It may be useful to be explicit that there are no restrctions on code motion.
>> ====
>
> But there are restrictions, for example those related to the forward
> progress requirements or the coherency rules.

Those are C++11 restrictions, used in the formal description of the model. The 
expected behaviour of the HW insructions generated by the built-in doesn't require 
any restrictions to be imposed.

>>    @item __ATOMIC_CONSUME
>> -Data dependency only for both barrier and synchronization with another
>> -thread.
>> +This is currently implemented using the stronger @code{__ATOMIC_ACQUIRE}
>> +memory order because of a deficiency in C++11's semantics for
>> +@code{memory_order_consume}.
>>
>> =====
>> It would be useful to have a description of what the __ATOMIC_CONSUME was
>> meant to do, as well as the fact that it currently just maps to
>> __ATOMIC_ACQUIRE. (Or maybe just drop it from the documentation until it's
>> fixed.)
>> =====
>
> I'll leave what it was meant to do to the ISO C++ discussions.  I think
> that it's implemented using mo_acquire is already clear from the text,
> or not?

Yes, I just meant don't drop the link to __ATOMIC_CONSUME.

It's probably worth saying something to discourage people from using this though. 
Something on the lines of "This memory-order should not be used as the implementation 
is likely to change".

>>
>>    @item __ATOMIC_ACQUIRE
>> -Barrier to hoisting of code and synchronizes with release (or stronger)
>> -semantic stores from another thread.
>> +Creates an inter-thread happens-before constraint from the release (or
>> +stronger) semantic store to this acquire load.  Can prevent hoisting
>> +of code to before the operation.
>>
>> =====
>> As noted before, it's not clear what the "inter-thread happens-before"
>> means in this context.
>
> I don't see a way to make this truly freestanding without replicating
> the specification of the C++11 memory model.

(As above) I don't believe that the happens-before applies to the built-ins.

>> Here and elsewhere:
>> "Can prevent <motion> of code" is ambiguous: it doesn't say under what
>> conditions code would or wouldn't be prevented from moving.
>
> Yes, it's not a specification but just an illustration of what can
> result from the specification.

But it makes it difficult to know what behaviour to expect, making it difficult to use.

> [..] Describing which code movement is
> allowed or not, precisely, is way too much detail IMO.  There are full
> ISO C++ papers about that (N4455), and even those aren't enumerations of
> all allowed code transformations.

A gcc built-in reduces to a code sequence to be executed by a single thread; 
describing the expected behaviour of that code sequence shouldn't be so difficult 
that it needs a paper. Note that this doesn't need a formal (in the sense of formal 
methods) description, just the sort of description that is normal for a compiler 
built-in.

>> =====
>>
>> -Note that the scope of a C++11 memory model depends on whether or not
>> -the function being called is a @emph{fence} (such as
>> -@samp{__atomic_thread_fence}).  In a fence, all memory accesses are
>> -subject to the restrictions of the memory model.  When the function is
>> -an operation on a location, the restrictions apply only to those
>> -memory accesses that could affect or that could depend on the
>> -location.
>> +Note that in the C++11 memory model, @emph{fences} (e.g.,
>> +@samp{__atomic_thread_fence}) take effect in combination with other
>> +atomic operations on specific memory locations (e.g., atomic loads);
>> +operations on specific memory locations do not necessarily affect other
>> +operations in the same way.
>>
>> ====
>> Its very unclear what this paragraph is saying. It seems to suggest that fences
>> only work in combination with other operations. But that doesn't seem right
>> since a __atomic_thread_fence (with appropriate memory order) can be dropped
>> into any piece of code and will act in the way that memory barriers are commonly
>> understood to work.
>
> Not quite.  If you control the code generation around the fence (e.g.,
> so you control which loads/stores a compiler generates), and know which
> HW instruction the C++ fence maps too, you can try use it this way.
>
> However, that's not what the built-in is specified to result in --
> instead, it's specified to implement a C++ fence.  And those take effect
> in combination with the reads-from relation etc., for which one needs to
> use atomic operations that access specific memory locations.
>

As above.

>> ====
>>
>>    @@ -9131,5 +9135,5 @@ if (_atomic_always_lock_free (sizeof (long long), 0))
>>    @deftypefn {Built-in Function} bool __atomic_is_lock_free (size_t size, void *ptr)
>>
>>    This built-in function returns true if objects of @var{size} bytes always
>> +generate lock-free atomic instructions for the target architecture.  If
>> +it is not known to be lock-free, a call is made to a runtime routine named
>> ====
>> Probably unrelated to the point of this patch but does this mean
>> "If this built-in function is not known to be lock-free .."?
>> ====
>>
>
> Yes, fixed.
>
> I've also fixed s/model/order/ in the HLE built-ins docs and fixed a
> typo there too.
>
> Unless there are objections, I plan to commit the attached patch at the
> end of this week.

It's obvious that I have concerns. These come from an apparent difference of opinion 
about what the built-ins and the manual page are for so I won't object to the patch 
going in.

Matthew

On Thu, 2015-05-21 at 16:45 +0100, Matthew Wahab wrote:
> On 19/05/15 20:20, Torvald Riegel wrote:
> > On Mon, 2015-05-18 at 17:36 +0100, Matthew Wahab wrote:
> >> Hello,
> >>
> >> On 15/05/15 17:22, Torvald Riegel wrote:
> >>> This patch improves the documentation of the built-ins for atomic
> >>> operations.
> >>
> >> The "memory model" to "memory order" change does improve things but I think that
> >> the patch has some problems. As it is now, it makes some of the descriptions
> >> quite difficult to understand and seems to assume more familiarity with details
> >> of the C++11 specification then might be expected.
> >
> > I'd say that's a side effect of the C++11 memory model being the
> > reference specification of the built-ins.
> >
> >> Generally, the memory order descriptions seem to be targeted towards language
> >> designers but don't provide for anybody trying to understand how to implement or
> >> to use the built-ins.
> >
> > I agree that the current descriptions aren't a tutorial on the C++11
> > memory model.  However, given that the model is not GCC-specific, we
> > aren't really in a need to provide a tutorial, in the same way that we
> > don't provide a C++ tutorial.  Users can pick the C++11 memory model
> > educational material of their choice, and we need to document what's
> > missing to apply the C++11 knowledge to the built-ins we provide.
> >
> 
> We seem to have different views about the purpose of the manual page. I'm treating it 
> as a description of the built-in functions provided by gcc to generate the code 
> needed to implement the C++11 model. That is, the built-ins are distinct from C++11 
> and their descriptions should be, as far as possible, independent of the methods used 
> in the C++11 specification to describe the C++11 memory model.

OK.  But we'd need a *precise* specification of what they do if we'd
want to make them separate from the C++11 memory model.  And we don't
have that, would you agree?

It's also not a trivial task, so I wouldn't be optimistic that someone
would offer to write such a specification, and have it cross-checked.

> I understand of course that the __atomics were added in order to support C++11 but 
> that doesn't make them part of C++11 and, since __atomic functions can be made 
> available when C11/C++11 may not be, it seems to make sense to try for stand-alone 
> descriptions.

The compiler can very well provide the C++11 *memory model* without
creating any dependency on the other language/library pieces of C++11 or
C11.  Prior to C++11, multi-threaded executions were not defined by the
standard, so we're not conflicting with anything in prior language
standards, right?

Another way to see this is to say that we just *copy* the C++11 memory
model and use it as the memory model that specifies the behavior of the
atomic built-ins.  That additionally frees us from having to come up
with and maintain our GCC-specific specification of atomics and a memory
model.

> I'm also concerned that the patch, by describing things in terms of formal C++11 
> concepts, makes it more difficult for people to know what the built-ins can be 
> expected to do and so make the built-in more difficult to use There is a danger that 
> rather than take a risk with uncertainty about the behaviour of the __atomics, people 
> will fall-back to the __sync functions simply because their expected behaviour is 
> easier to work out.

I hadn't thought about that possible danger, but that would be right.
The way I would prefer to counter that is that we add a big fat warning
to the __sync built-ins that we don't have a precise specification for
them and that there are several corners of hand-waving and potentially
further issues, and that this is another reason to prefer the __atomic
built-ins.  PR 65697 etc. are enough indication for me that we indeed
lack a proper specification.

> I don't think that linking to external sites will help either, unless people already 
> want to know C++11. Anybody who just wants to (e.g.) add a memory barrier will take 
> one look at the __sync manual page and use the closest match from there instead.

Well, "just wants to add a memory barrier" is a the start of the
problem.  The same way one needs to understand a hardware memory model
to pick the right HW instruction(s), the same one needs to understand a
programming language memory model to pick a fence and understand its
semantics.

> Note that none of this requires a tutorial of any kind. I'm just suggesting that the 
> manual should describe what behaviour should be expected of the code generated for 
> the functions. For the memory orders, that would mean describing what constraints 
> need to be met by the generated code.

I'd bet that if one describes these constraints correctly, you'll get a
large document -- even if one removes any introductory or explanatory
parts that could make it a tutorial.

It's fairly straight-forward to describe several simple usage patterns
of the atomics (e.g., seq-cst ones, simple acquire/release pairs,
producer/consumer, etc.).  But describing the actual *constraints*
correctly ends up duplicating a specification.

You could certainly try to come up with a simple description of the
constraints, and we can iterate until I can't pick any holes in the
description anymore.  But I really don't think this would be a
worthwhile use of our time :)  It will certainly need more than a few
sentences to be bullet-proof.

If you haven't, please just look at
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4455.html
and try to specify the constraints just for the valid optimizations
described there.  This should be a good indication of why I think
specifying the reordering / behavior constraints is nontrivial.

> The requirement that the atomics should support 
> C++11 could be met by making sure that the description of the expected behaviour is 
> sufficient for C++11.

We don't just want the semantics of __atomic* to be sufficient for C++11
but also want them to be *as weak as possible* to be still sufficient
for C++11 -- otherwise, we'll make C++11 code less efficient than it can
be.  Thus, we want semantics that have the same strength as what's
needed by C++11.

> > There are several resources for implementers, for example the mappings
> > maintained by the Cambridge research group.  I guess it would be
> > sufficient to have such material on the wiki.  Is there something
> > specific that you'd like to see documented for implementers?
> > [...]
> > I agree it's not described in the manual, but we're implementing C++11.
> 
> (As above) I believe we're supporting the implementation of C++11 and that the 
> distinction is important.
> 
> > However, I don't see why happens-before semantics wouldn't apply to
> > GCC's implementation of the built-ins; there may be cases where we
> > guarantee more, but if one uses the builtins in way allowed by the C++11
> > model, one certainly gets behavior and happens-before relationships as
> > specified by C++11.
> >
> 
> My understanding is that happens-before is a relation used in the C++11 specification 
> for a specific meaning. I believe that it's used to decide whether something is or is 
> not a data race

It appears in the data-race definition, right.  More generally, it is
the program-wide partial order regarding what virtually happens-before
what (as-if applies of cause) in a particular execution of a program.
It's at the core of actually describing how a multi-threaded program
behaves.

> so saying that it applies to a gcc built-in would be wrong.

Simplified, we can map 1:1 between an __atomic built-in and an
equivalent atomic operation.  The exception is basically the data
definitions for an atomic type (e.g., atomic<T>): While C++11 hides the
data and data type required for an atomically accessible variable, the
built-ins assume that the caller will target a suitable memory location.

> Using the 
> gcc built-in rather than the equivalent C++11 library function would result in 
> program that C++11 regards as invalid. (Again, as I understand it.)

It wouldn't be invalid but simply not defined by C++11.  But that's fine
because the built-ins are a GCC-specific extension (which is compatible
with C++11 atomics, of course).

> >
> >>    @table  @code
> >>    @item __ATOMIC_RELAXED
> >> -No barriers or synchronization.
> >> +Implies no inter-thread ordering constraints.
> >>
> >> ====
> >> It may be useful to be explicit that there are no restrctions on code motion.
> >> ====
> >
> > But there are restrictions, for example those related to the forward
> > progress requirements or the coherency rules.
> 
> Those are C++11 restrictions, used in the formal description of the model. The 
> expected behaviour of the HW insructions generated by the built-in doesn't require 
> any restrictions to be imposed.

No, those show up at the HW level as well.  Consider examples of
spin-loops with memory_order_relaxed loads, or the coherency rule.  For
example:
  foo.store(1, memory_order_relaxed);
  foo.store(2, memory_order_relaxed);
  r = foo.load(memory_order_relaxed);
In absence of other stores, r must never equal 1 (according to one of
the coherency rules).  If there'd be "no restrictions on code motion",
the load could be moved to before the stores, which isn't allowed.
Likewise, the assumption is that no hardware will do that either (or the
generated code has to enforce this through specific HW instructions).

> >> Here and elsewhere:
> >> "Can prevent <motion> of code" is ambiguous: it doesn't say under what
> >> conditions code would or wouldn't be prevented from moving.
> >
> > Yes, it's not a specification but just an illustration of what can
> > result from the specification.
> 
> But it makes it difficult to know what behaviour to expect, making it difficult to use.
> 
> > [..] Describing which code movement is
> > allowed or not, precisely, is way too much detail IMO.  There are full
> > ISO C++ papers about that (N4455), and even those aren't enumerations of
> > all allowed code transformations.
> 
> A gcc built-in reduces to a code sequence to be executed by a single thread; 
> describing the expected behaviour of that code sequence shouldn't be so difficult 
> that it needs a paper. Note that this doesn't need a formal (in the sense of formal 
> methods) description, just the sort of description that is normal for a compiler 
> built-in.

The built-ins represent constraints for the *both* generic code
transformations and arch-specific code generation.  They are not just
fancy ways to get certain instruction sequences.  Thus, what's discussed
in N4455 is very much relevant.

On 21/05/15 19:26, Torvald Riegel wrote:
> On Thu, 2015-05-21 at 16:45 +0100, Matthew Wahab wrote:
>> On 19/05/15 20:20, Torvald Riegel wrote:
>>> On Mon, 2015-05-18 at 17:36 +0100, Matthew Wahab wrote:
>>>> Hello,
>>>>
>>>> On 15/05/15 17:22, Torvald Riegel wrote:
>>>>> This patch improves the documentation of the built-ins for atomic
>>>>> operations.
>>>>

I think we're talking at cross-purposes and not really getting anywhere. I've replied 
to some of your comments below, but it's mostly a restatement of points already made.

I'll repeat that, although I have concerns about the patch, I don't object to it 
going in. Maybe wait a few days to see if anybody else wants to comment but, at this 
point and, since it's a documentation patch and won't break anything, it's better to 
just commit and deal with any problems come up.

>> We seem to have different views about the purpose of the manual page. I'm treating it
>> as a description of the built-in functions provided by gcc to generate the code
>> needed to implement the C++11 model. That is, the built-ins are distinct from C++11
>> and their descriptions should be, as far as possible, independent of the methods used
>> in the C++11 specification to describe the C++11 memory model.
>
> OK.  But we'd need a *precise* specification of what they do if we'd
> want to make them separate from the C++11 memory model.  And we don't
> have that, would you agree?

There is a difference between the sort of description that is needed for a formal 
specification and the sort that would be needed for a programmers manual. The best 
example of this that I can think of is the Standard ML definition 
(http://sml-family.org). That is a mathematical (so precise) definition that is 
invaluable if you want an unambiguous specification of the language. But its useless 
for anybody who just wants to use Standard ML to write programs. For that, you need 
go to the imprecise descriptions that are given in books about SML and in the 
documentation for SML compilers and libraries.

The problem with using the formal SML definition is the same as with using the formal 
C++11 definition: most of it is detail needed to make things in the formal 
specification come out the right way. That detail, about things that are internal to 
the definition of the specification, makes it difficult to understand what is 
intended to be available for the user.

The GCC manual seems to me to be aimed more at the people who want to use GCC to 
write code and I don't think that the patch makes much allowance for them. I do think 
that more precise statements about the relationship to C++11 are useful to have. Its 
the sort of constraint that ought to be documented somewhere. But it seems to be more 
of interest to compiler writers or, at least, to users who are as knowledgeable as 
compiler writers. A document targeting that group, such as the GCC internals or a GCC 
wiki-page, would seem to be a better place for the information.

(Another example of the distinction may be the Intel Itanium ABI documentation which 
has a programmers description of the synchronization primitives and a separate, 
formal description of their behaviour.)

For what it's worth, my view of how C++11, the __atomics and the machine code line up 
is that each is a distinct layer. Each layer implements the requirements of the 
higher (more abstract) layer but is otherwise entirely independent. That's why I 
think that a description of the __atomic built-in, aimed at compiler users rather 
than writers and that doesn't expect knowledge of C++11 is desirable and possible.

>> I'm also concerned that the patch, by describing things in terms of formal C++11
>> concepts, makes it more difficult for people to know what the built-ins can be
>> expected to do and so make the built-in more difficult to use[..]
>
> I hadn't thought about that possible danger, but that would be right.
> The way I would prefer to counter that is that we add a big fat warning
> to the __sync built-ins that we don't have a precise specification for
> them and that there are several corners of hand-waving and potentially
> further issues, and that this is another reason to prefer the __atomic
> built-ins.  PR 65697 etc. are enough indication for me that we indeed
> lack a proper specification.

Increasing uncertainty about the __sync built-ins wouldn't make people move to 
equally uncertain __atomic built-ins. There's enough knowledge and use of the __sync 
builtins to make them a more comfortable choice then the C++11 atomics and in the 
worst case it would push people to roll their own synchronization functions with 
assembler or system calls.

> Well, "just wants to add a memory barrier" is a the start of the
> problem.  The same way one needs to understand a hardware memory model
> to pick the right HW instruction(s), the same one needs to understand a
> programming language memory model to pick a fence and understand its
> semantics.

Sometimes you just want the hardware instructions and don't care about the 
programming language semantics.

I suspect that for most people using GCC, the only time that the programming language 
specification matters is when their bug-report gets rejected as invalid code. Which 
is to say that you may be expecting more knowledge of the C++11 specification than 
most people actually have.

>> Note that none of this requires a tutorial of any kind. I'm just suggesting that the
>> manual should describe what behaviour should be expected of the code generated for
>> the functions. For the memory orders, that would mean describing what constraints
>> need to be met by the generated code.
>
> I'd bet that if one describes these constraints correctly, you'll get a
> large document -- even if one removes any introductory or explanatory
> parts that could make it a tutorial.

Agreed. It's possible to get an arbitrarily large, precise definition for even the 
more trivial programming language. It depends on how far you want to go with "precise".

That said, my point was that, for user documentation, it's usual to abstract 
sufficiently to be able to give (a good approximation to) a correct, useful and 
succinct description. Completeness isn't necessary, that belongs in the compiler 
writer's docs.

> If you haven't, please just look at
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4455.html
> and try to specify the constraints just for the valid optimizations
> described there.  This should be a good indication of why I think
> specifying the reordering / behavior constraints is nontrivial.

I don't remember seeing this, it's an interesting paper. It deals with things that 
matter to compiler writers though so I don't think it's relevant to point I was 
trying to make (that there's a distinction between documentation for compiler users 
and compiler writers).

>
>> The requirement that the atomics should support
>> C++11 could be met by making sure that the description of the expected behaviour is
>> sufficient for C++11.
>
> We don't just want the semantics of __atomic* to be sufficient for C++11
> but also want them to be *as weak as possible* to be still sufficient
> for C++11 -- otherwise, we'll make C++11 code less efficient than it can
> be.

Yes, that's implied by 'sufficient'.

>> My understanding is that happens-before is a relation used in the C++11 specification
>> for a specific meaning.[..]
>> so saying that it applies to a gcc built-in would be wrong.
>
> Simplified, we can map 1:1 between an __atomic built-in and an
> equivalent atomic operation.  The exception is basically the data
> definitions for an atomic type (e.g., atomic<T>): While C++11 hides the
> data and data type required for an atomically accessible variable, the
> built-ins assume that the caller will target a suitable memory location.
>
>> Using the
>> gcc built-in rather than the equivalent C++11 library function would result in
>> program that C++11 regards as invalid. (Again, as I understand it.)
>
> It wouldn't be invalid but simply not defined by C++11.  But that's fine
> because the built-ins are a GCC-specific extension (which is compatible
> with C++11 atomics, of course).
>

But the distinction between the GCC built-ins and the C++11 library functions is 
still there. As far as the C++11 specification is concerned, the GCC __atomic would 
not establish the same relationships, such as inter-thread happens-before, as the 
equivalent C+++11 atomic function. As far as the C++11 specification is concerned, 
the GCC built-in is just another function.

> [...]

Apologies if I missed anything important. As I said, I doubt we'll come to agreement 
on this so I think that the best way to make progress is to see if anybody else has 
objections and commit if not.

Matthew

On Fri, 2015-05-22 at 17:41 +0100, Matthew Wahab wrote:
> On 21/05/15 19:26, Torvald Riegel wrote:
> > On Thu, 2015-05-21 at 16:45 +0100, Matthew Wahab wrote:
> >> On 19/05/15 20:20, Torvald Riegel wrote:
> >>> On Mon, 2015-05-18 at 17:36 +0100, Matthew Wahab wrote:
> >>>> Hello,
> >>>>
> >>>> On 15/05/15 17:22, Torvald Riegel wrote:
> >>>>> This patch improves the documentation of the built-ins for atomic
> >>>>> operations.
> >>>>
> 
> I think we're talking at cross-purposes and not really getting anywhere. I've replied 
> to some of your comments below, but it's mostly a restatement of points already made.

OK.  I have a few more comments below.

> >> We seem to have different views about the purpose of the manual page. I'm treating it
> >> as a description of the built-in functions provided by gcc to generate the code
> >> needed to implement the C++11 model. That is, the built-ins are distinct from C++11
> >> and their descriptions should be, as far as possible, independent of the methods used
> >> in the C++11 specification to describe the C++11 memory model.
> >
> > OK.  But we'd need a *precise* specification of what they do if we'd
> > want to make them separate from the C++11 memory model.  And we don't
> > have that, would you agree?
> 
> There is a difference between the sort of description that is needed for a formal 
> specification and the sort that would be needed for a programmers manual. The best 
> example of this that I can think of is the Standard ML definition 
> (http://sml-family.org). That is a mathematical (so precise) definition that is 
> invaluable if you want an unambiguous specification of the language. But its useless 
> for anybody who just wants to use Standard ML to write programs. For that, you need 
> go to the imprecise descriptions that are given in books about SML and in the 
> documentation for SML compilers and libraries.
> 
> The problem with using the formal SML definition is the same as with using the formal 
> C++11 definition: most of it is detail needed to make things in the formal 
> specification come out the right way. That detail, about things that are internal to 
> the definition of the specification, makes it difficult to understand what is 
> intended to be available for the user.

A relation like happens-before is "user-facing".  It is how one reasons
about ordering in a multi-threaded execution.  This isn't internal or
for a corner-case like additional-synchronizes-with or one of the
consistency rules.

> The GCC manual seems to me to be aimed more at the people who want to use GCC to 
> write code and I don't think that the patch makes much allowance for them. I do think 
> that more precise statements about the relationship to C++11 are useful to have. Its 
> the sort of constraint that ought to be documented somewhere. But it seems to be more 
> of interest to compiler writers or, at least, to users who are as knowledgeable as 
> compiler writers. A document targeting that group, such as the GCC internals or a GCC 
> wiki-page, would seem to be a better place for the information.
> 
> (Another example of the distinction may be the Intel Itanium ABI documentation which 
> has a programmers description of the synchronization primitives and a separate, 
> formal description of their behaviour.)
> 
> For what it's worth, my view of how C++11, the __atomics and the machine code line up 
> is that each is a distinct layer. Each layer implements the requirements of the 
> higher (more abstract) layer but is otherwise entirely independent. That's why I 
> think that a description of the __atomic built-in, aimed at compiler users rather 
> than writers and that doesn't expect knowledge of C++11 is desirable and possible.
> 
> >> I'm also concerned that the patch, by describing things in terms of formal C++11
> >> concepts, makes it more difficult for people to know what the built-ins can be
> >> expected to do and so make the built-in more difficult to use[..]
> >
> > I hadn't thought about that possible danger, but that would be right.
> > The way I would prefer to counter that is that we add a big fat warning
> > to the __sync built-ins that we don't have a precise specification for
> > them and that there are several corners of hand-waving and potentially
> > further issues, and that this is another reason to prefer the __atomic
> > built-ins.  PR 65697 etc. are enough indication for me that we indeed
> > lack a proper specification.
> 
> Increasing uncertainty about the __sync built-ins wouldn't make people move to 
> equally uncertain __atomic built-ins. There's enough knowledge and use of the __sync 
> builtins to make them a more comfortable choice then the C++11 atomics and in the 
> worst case it would push people to roll their own synchronization functions with 
> assembler or system calls.

I don't buy that.  Sure, some people will be uncomfortable with
anything.  But I don't see how "specified in C++11 and C11" is the same
level of uncertainty as "we don't have a tight specification".  Users
can pick their favorite source of education on the C++11 memory model.
And over time, C++11 / C11 will become commonly known...

> > Well, "just wants to add a memory barrier" is a the start of the
> > problem.  The same way one needs to understand a hardware memory model
> > to pick the right HW instruction(s), the same one needs to understand a
> > programming language memory model to pick a fence and understand its
> > semantics.
> 
> Sometimes you just want the hardware instructions and don't care about the 
> programming language semantics.

If you tightly control code generation around those uses, that can work.
But compilers will optimize concurrent code, so in general, one can't
pretend the compiler isn't there or is just a fancy assembler.

I'm stressing this point because I think that it's critical that users
understand that in most cases, they have to consider both the compiler
and the hardware when writing concurrent C/C++ code.

> > If you haven't, please just look at
> > http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4455.html
> > and try to specify the constraints just for the valid optimizations
> > described there.  This should be a good indication of why I think
> > specifying the reordering / behavior constraints is nontrivial.
> 
> I don't remember seeing this, it's an interesting paper. It deals with things that 
> matter to compiler writers though so I don't think it's relevant to point I was 
> trying to make (that there's a distinction between documentation for compiler users 
> and compiler writers).

Well, it's optimizations that the compiler is allowed to do.  So if we
give imprecise definitions of the semantics of __atomic* to users, it
can lead to differences between what users think __atomic* provides and
what it actually does.

I pointed to this paper because it shows examples of optimizations that
would be disallowed by simple definitions of __atomic but are allowed by
the standard.

> >
> >> The requirement that the atomics should support
> >> C++11 could be met by making sure that the description of the expected behaviour is
> >> sufficient for C++11.
> >
> > We don't just want the semantics of __atomic* to be sufficient for C++11
> > but also want them to be *as weak as possible* to be still sufficient
> > for C++11 -- otherwise, we'll make C++11 code less efficient than it can
> > be.
> 
> Yes, that's implied by 'sufficient'.

I disagree.  If condition C1 is sufficient to yield condition C2, then
C1 implies C2 -- but they are not necessarily equal.  "Sufficient and
necessary" would be what we want for the mapping.  (For example, it
would be *sufficient* to make all __atomic* to have seq-cst behavior,
irrespective of the memory order argument -- but it wouldn't be
*necessary*, and it would be less efficient.)