Version 1.3 of ai05s/ai05-0275-1.txt

Unformatted version of ai05s/ai05-0275-1.txt version 1.3
Other versions for file ai05s/ai05-0275-1.txt

!standard C.6(16)          12-02-25 AI05-0275-1/03
!class binding interpretation 11-11-09
!status Amendment 2012 11-12-27
!status work item 12-02-13
!status ARG Approved 7-0-2 11-11-12
!status work item 11-11-09
!status received 11-10-01
!priority Low
!difficulty Easy
!qualifier Omission
!subject More issues with the definition of volatile
!summary
Atomic objects still must be used to ensure that actions are sequential before accessing volatile objects; nothing about the new version of C.6(16/3) is intended to imply that one can read shared volatile objects without some sort of synchronization.
!question
C.6(16/3) says:
All tasks of the program (on all processors) that read or update volatile variables see the same order of updates to the variables.
This wording is correct but seems misleading. Any concurrent accesses to shared variables (unless they are atomic) lead to erroneous execution, as clearly stated in 9.10(11). But C.6(16/3) because it seems to guarantee sequentially consistent behavior for concurrent accesses of non-atomic volatile variables, which is not the case.
Should this be clarified further? (Yes.)
!recommendation
(see summary.)
!wording
Modify C.6(16/3) and the following AARM note:
All tasks of the program (on all processors) that read or update volatile {@Redundant[and atomic]} variables see the same order of updates to the variables.{ A use of an atomic variable or other mechanism may be necessary to avoid erroneous execution and to ensure that access to volatile variables is sequential (see 9.10).}
AARM Implementation Note: To ensure this, on a multiprocessor, any read or update of {an atomic}[a volatile] object {may require}[should involve] the use of an appropriate memory barrier.
!discussion
From 9.10 it follows that (in non-erroneous programs) accesses to variables, including those shared by multiple tasks, are always sequential. This guarantees that no task will ever see partial updates of any variable. For volatile variables, C.6(16) additionally specifies that all tasks see the same order of updates.
If for a shared variable X, a read of X occurs sequentially after an update of X, then the read will return the updated value if X is volatile, but may or or may not return the updated value if X is non-volatile. For non-volatile accesses, a signaling action is needed in order to share the updated value.
Because accesses to the same atomic variable by different tasks establishes a sequential order between the actions of those tasks, implementations may be required to emit memory barriers around such updates or use atomic instructions that imply such barriers.
!example
The example given in AI05-0117-1 is wrong, as it does not require sequential access to the objects. The following example is correct, and will ensure that task 2 does get the value 42.
Data : Integer; pragma Volatile (Data);
Flag : Boolean := False; pragma Atomic (Flag);
in task 1:
Data := 42; Flag := True;
in task 2:
loop exit when Flag; end loop; Copy := Data;
!corrigendum C.6(16)
Replace the paragraph:
For a volatile object all reads and updates of the object as a whole are performed directly to memory.
by:
All tasks of the program (on all processors) that read or update volatile variables see the same order of updates to the variables. A use of an atomic variable or other mechanism may be necessary to avoid erroneous execution and to ensure that access to nonatomic volatile variables is sequential (see 9.10).
!ACATS Test
No additional ACATS test is required.
!ASIS
No ASIS effect.
!appendix

From: Geert Bosch
Sent: Tuesday, July 12, 2011  12:58 PM

As implementor, I would like to comment on AI-117.
The proposed new wording seeks to clarify, yet seems
slightly confused.

In particular, the example in the AI is incorrect:

!example
The following will ensure that task 2 does get the value 42.

 Data : Integer;
 pragma Volatile (Data);

 Flag : Boolean := False;
 pragma Volatile (Flag);

in task 1:
 Data := 42;
 Flag := True;

in task 2:
 loop
    exit when Flag;
 end loop;

 Copy := Data;

As written, the example will lead to erroneous execution, where
both task 1 and task 2 access shared variable Flag, at least one
of the accesses is a write, and the accesses are not sequential,
see RM 9.10(11).

The example requires flag to be Atomic, while Data can remain Volatile.

Note the new wording of C.6(16):
> All tasks of the program (on all processors) that read or update
> volatile variables see the same order of updates to the variables.

This wording is correct, but only because any concurrent accesses
to shared variables (volatile or not) lead to erroneous execution,
as clearly stated in 9.10(11). On its own C.6(16) may be misleading,
because it seems to guarantee sequentially consistent behavior for
concurrent accesses of non-atomic volatile variables, which is not
the case.

Additionally, because only atomic accesses are by definition
sequential (see C.6(16)), there is in general no need for memory
barriers between accesses to volatile variables. Barriers are only
needed between two atomic accesses and between any atomic access and
an access to a (potentially) shared variable by the same task.
A barrier may be needed between an atomic access and an access of a
shared non-volatile variable, to ensure that either the old or the
new value will be read, see 9.10(15b). A typical implementation would
emit full barriers before and after atomic reads and writes, eliding
consecutive barriers without intervening shared variable accesses.

Please note that it would be impractical to allow non-sequential
read/write access to volatile variables, as without locking a partial
write would allow the reader to access the object while in an
inconsistent state, if it cannot be updated atomically. Consider
a 64-bit long float on a 32-bit system, or a record with discriminant.

So, to conclude, C.6(16) should have an additional note:

 Accesses to volatile variables must be sequential to avoid erroneous
 execution, see 9.10(11).

Additionally, Implementation Note C.6(16.a) should be replaced with:

 AARM Implementation Note: To ensure this, on a multiprocessor,
 any read or update of an atomic object should involve the use of
 appropriate memory barriers.

Here, I replaced "volatile" by "atomic" and did not say "a memory barrier"
but used the indefinite "memory barriers", as in the general case two
barriers may be needed per access.

****************************************************************

From: Ed Schonberg
Sent: Friday, November 11, 2011  1:11 PM

Dear Alan,

Geert Bosch has forwarded the following to the ARG, hoping for
comments. we are currently discussing his message, and all those
present confess to an insufficient depth of understanding of the issue.
Could you comment on Geert's remarks? In particular, he claims that on
multiprocessors memory barriers are needed eventually for access to atomic
variables, but not for access to volatile.

This would seem to make a substantial performance difference on an important
Ada2012 domain.  What is your expert opinion on this?

The ARG eagerly awaits, and hopes to dispose of the issue one way or
the other in the course of this meeting. No pressure, but we would love to
know by sunday!

****************************************************************

From: Alan Burns
Sent: Saturday, November 12, 2011  6:14 AM

I can give my opinion, but please do not take this as definitive, I am not
an expert on low level multiprocessor hardware.

The requirement is to be able to write algorithms using shared variables that do not
get screwed up by the reordering of assignments to these shared variables. The
objective is to do this in a way that is efficient.

We attempted to do this by focusing on volatile - but I guess we forgot that to use
shared variables at all then the variable must be atomic (9.10(15)) - unless some
other signal is used which we don't want.

I am not sure why 9.10(15) only grants 'atomic' the property of sequential updates.
It could be argued that 'volatile' should also ensure sequential updates
- as volatile and atomic are defined to have an external effect: 1.1.3.

If 9.10(15) was changed to include volatile then the issues raised below would largely
do away. We want 'volatile' to enable shared variables to be used consistently.
But if they also have to be atomic in order to be used at all then that limited the
use of 'volatile'.

I've embedded some other comments below

...
> As written, the example will lead to erroneous execution, where both
> task 1 and task 2 access shared variable Flag, at least one of the
> accesses is a write, and the accesses are not sequential, see RM
> 9.10(11).
>
> The example requires flag to be Atomic, while Data can remain Volatile.

Yes this would seem to be true.

So the 'style' here would be to use a simple flag that can be make atomic, but use
volatile for the arbitrary data that is being transferred.

...
> Additionally, Implementation Note C.6(16.a) should be replaced with:
>
>   AARM Implementation Note: To ensure this, on a multiprocessor,
>   any read or update of an atomic object should involve the use of
>   appropriate memory barriers.

If we stay with the current definition of volatile then the above suggestions appear
to be needed and valid. But I am not sure that the right approach is not to change
9.10(15) to include volatile

****************************************************************

From: Randy Brukardt
Sent: Tuesday, December 27, 2011  11:22 PM

In Denver, we modified C.6(16/3) to read as follows:

All tasks of the program (on all processors) that read or update volatile variables
see the same order of updates to the variables. A use of an atomic variable or other
mechanism may be necessary to avoid erroneous execution and to ensure that access to
volatile variables is sequential (see 9.10).

I find that there is a clash in this wording. The first sentence is talking about
"volatile variables" to mean "volatile and atomic variables" (since "volatile" includes
"atomic"). The second sentence is talking about "volatile variables" to mean "volatile
but not atomic variables" (since nothing special is needed for atomic variables).

Probably the easiest way to fix this clash is to add "and atomic" to the first sentence
(giving "volatile @Redundant[and atomic] variables"). It would be better to somehow
exclude atomic from the second sentence, but everything I tried is really clunky, and
since C.6(17) talks about sequential actions of atomic objects, we're probably OK here.

Any better ideas are welcome.

****************************************************************

From: Geert Bosch
Sent: Wednesday, December 28, 2011  8:55 PM

> All tasks of the program (on all processors) that read or update
> volatile variables see the same order of updates to the variables.
> A use of an atomic variable or other mechanism may be necessary to
> avoid erroneous execution and to ensure that access to volatile
> variables is sequential (see 9.10).

You could just write:
> All tasks of the program (on all processors) that read or update
> volatile variables see the same order of updates to the variables.
> Synchronization may be necessary to avoid erroneous execution and to
> ensure that access to volatile variables is sequential (see 9.10).

After all, 9.10 also uses the term synchronization in its first paragraph, and
clearly lists all the situations that establish a sequential order.

****************************************************************

From: Randy Brukardt
Sent: Thursday, December 29, 2011  12:10 AM

I don't think this rewrite does anything to eliminate my original objection.
"Volatile variables" still means two different things in the two sentences
(unless you mean to cover atomic variables in the second sentence, in which case
I would object that it is misleading and unhelpful to talk about needing to make
something sequential that is already sequential by definition).

In addition, we thought that it was important to mention that using atomic
objects is the easiest way to get sequential execution. If you have to
understand 9.10 in detail to be able to use volatile, the game is lost. I read
this section and its AARM notes in detail last night, and now I'm far more
confused than I was previously. I would expect that the same would be true of
90% of Ada programmers!

****************************************************************

From: Tullio Vardanega
Sent: Thursday, December 29, 2011  10:11 AM

Yes clause C.6(16/3) is poor.
As volatile implies atomic, the use of volatile in the second sentence is just
inappropriate. What about (limited to the second sentence): "For variables that
were not explicitly marked volatile, the  use of atomic variables or other
mechanisms may be necessary to avoid erroneous execution and to ensure that
access those variables is sequential (see 9.10)."

Not sure that "marking" is an RM-qualified term, but I guess you see my meaning.

****************************************************************

From: Randy Brukardt
Sent: Thursday, December 29, 2011  2:59 PM

> Yes clause C.6(16/3) is poor.
> As volatile implies atomic, the use of volatile in the second sentence
> is just inappropriate.

No, that's backwards. Atomic implies volatile, not the other way around.
Thus there are no atomic objects that are not volatile, but there are plenty of
volatile objects that are not atomic.

The sentence in question is trying to talk about volatile variables that are not
atomic. The point is that it is not enough to mark such objects as volatile, you
also have to do something to make the updates sequential.

****************************************************************

From: Bob Duff
Sent: Thursday, December 29, 2011  3:11 PM

> The sentence in question is trying to talk about volatile variables
> that are not atomic.

So why not use the phrase "non-atomic volatile variables"?

****************************************************************

From: Randy Brukardt
Sent: Thursday, December 29, 2011  3:27 PM

Because I didn't think of it? Because I don't like inventing non-words? (Pun
definitely intended.) Thanks for the suggestion.

****************************************************************

From: Bob Duff
Sent: Thursday, December 29, 2011  3:39 PM

;-)

I guess it should really be "nonatomic volatile variables"; I think the hyphen
is wrong.

****************************************************************

From: Gary Dismukes
Sent: Thursday, December 29, 2011  6:42 PM

> I guess it should really be "nonatomic volatile variables";

Yes.

> I think the hyphen is wrong.

So do I.  (And it's nonword, not non-word.:-))

****************************************************************

From: Randy Brukardt
Sent: Friday, December 30, 2011  1:57 AM

I asked Geert Bosch to comment on a draft of the AI that was a response to his
query last summer. The AI encapsulates the discussion we had in Denver on this
topic.

Geert had issues with part of the !discussion of the AI, which was pretty much a
direct transcription of my notes of the ARG meeting. For the most part, the
problem is the definition (or lack thereof) for what Volatile means. Eventually,
he tried to explain to me his model for what Volatile means. It makes quite a
bit of sense, except for one problem: I cannot find any support whatsoever for
his (high-level) model for Volatile in the Standard or AARM. (The actual rules
being much lower level.)

At this point, I've reached my limit of knowledge about Atomic and Volatile, and
it seems like a good idea to bring everyone else into the discussion. (And put
the discussion on the record.)

So following is a summary of our (private) discussion. It's edited for brevity,
especially my responses. Any and all comments are welcome, including "Randy is
an idiot" :-)

----

I originally sent Geert an AI that contained the following passage (AI05-0275-1,
which will be posted sometime in the next week or so):

C.6(16/3) is not about sequential actions at all, but rather about the view of
updates that tasks have of the objects. The updates (especially of objects with
multiple parts) may occur in any order, but all tasks will see the same order.
In particular, it cannot be the case that task T1 sees the new version of part 1
of a volatile object V and the old version of part 2 of V, while task T2 sees
the old version of part 1 of V and the new version of part 2 of V. Any other
view of old and new versions of V is allowed (in the absence of other
synchronization, of course).

---

Geert responded to this:

The difference between sequential actions and views of updates being ordered is
really an implementation detail. Implementations are always allowed to do
arbitrary optimizations, including reordering or omitting operations, as long as
the observable semantics are correct. I don't understand the comment about
objects with multiple parts. Either the parts are independently addressable, in
which case there is no synchronization issue, or the parts are not. In the last
case, as all tasks either see a complete update of the object or none at all.
This last case can only happen for non-volatile (regular) shared variables, when
two actions are sequential but not signaling.

In all cases, the requirement of actions being sequential is what avoids one to
see partial updates.

I think that trying to explaining things at a lower level than that of
sequential actions is a bit of a minefield.

---

I responded to Geert:

This paragraph is almost directly taken from my notes of the Denver ARG meeting.
The portion of about parts of an volatile object comes directly from a quote
from Tucker, and he said it twice (so I'm pretty sure that I have it recorded
right).

Following is an attempt to reconstruct what the thinking was...

Remember that C.6(16/3) is the *only* interesting semantic definition for
Volatile (this replaces the old "written directly to memory" wording, which
clearly is too strong). If it is only an "implementation detail", then there is
no visible difference between a volatile object and a normal object -- in which
case, there is no need at all for Volatile. (Volatile does not have either the
atomic operation nor the sequential action semantics of Atomic, which leaves
nothing at all.)

Moreover, when you say "Implementations are always allowed to do arbitrary
optimizations, including reordering or omitting operations, as long as the
observable semantics are correct.", you're right, but the entire point is that
the sequence of operations of a volatile object is part of the "observable
effect". We don't want to require immediate writing to memory, but we do want
all tasks to see the same sequence of updates -- including to parts
(independently addressable, as you note) of a volatile object. This is stated
explicitly by 1.1.3(13) -- which is claimed to be "redundant", meaning it is
formally defined elsewhere. C.6(16) is that elsewhere.

Remember that the original semantics is that volatile objects always have to be
read/written to memory; keeping values in registers and the like is not allowed
as it is for 'normal' objects. That's too fierce in the sense that we don't want
to be requiring that caches be dumped or the like, but otherwise we still want
that sort of semantics. That's the intent of this wording, and as Tucker said,
it has nothing to do with sequential actions.

> In all cases, the requirement of actions being sequential is what
> avoids one to see partial updates.

We're not trying to avoid it, we're trying to define what is and is not allowed
for a volatile object. If the actions are not sequential on a volatile object,
its possible to observe partial updates, and the point is that not all possible
orders are allowable.

> I think that trying to explaining things at a lower level than that of
> sequential actions is a bit of a minefield.

I agree with this; this section has been a long-time problem, because of the
need to describe what is happening at the machine level. There is nothing
high-level about this description, nor can there be. This is the Systems
Programming Annex, after all, the high-level semantics are in 9.10.

---

Geert responded this evening:

...
> Remember that C.6(16/3) is the *only* interesting semantic definition
> for Volatile (this replaces the old "written directly to memory"
> wording, which clearly is too strong). If it is only an
> "implementation detail", then there is no visible difference between a
> volatile object and a normal object -- in which case, there is no need
> at all for Volatile. (Volatile does not have either the atomic
> operation nor the sequential action semantics of Atomic, which leaves
> nothing at all.)

If, for a shared variable X, a read of X occurs sequentially after an update of
X, then the read will return the updated value if X is volatile, but may or or
may not return the updated value if X is non-volatile. For non-volatile
accesses, a signaling action is needed in order to share the updated value.

...
> Remember that the original semantics is that volatile objects always
> have to be read/written to memory; keeping values in registers and the
> like is not allowed as it is for 'normal' objects. That's too fierce
> in the sense that we don't want to be requiring that caches be dumped
> or the like, but otherwise we still want that sort of semantics.
> That's the intent of this wording, and as Tucker said, it has nothing
> to do with sequential actions.

See above, the point is that for Volatile variables there is a global order for
reads and writes, assuming all accesses are sequential. For non-volatile shared
variables that is not the case. So, task T1 and T2 may see A updated before B,
and T3 and T4 may see B updated before A, even if all accesses are made
sequentially. Informally, copies of regular variables may be stored in local
temporaries, including caches and registers, while that is not allowed for
volatile variables.

>> In all cases, the requirement of actions being sequential is what
>> avoids one to see partial updates.
>
> We're not trying to avoid it, we're trying to define what is and is
> not allowed for a volatile object. If the actions are not sequential
> on a volatile object, its possible to observe partial updates, and the
> point is that not all possible orders are allowable.

If actions on any object are not sequential, execution is erroneous.

---

I responded to the above:
> If, for a shared variable X, a read of X occurs sequentially after an
> update of X, then the read will return the updated value if X is
> volatile, but may or or may not return the updated value if X is
> non-volatile. For non-volatile accesses, a signaling action is needed
> in order to share the updated value.

This sounds like a fine model. The only problem is that there isn't a word in
the AARM (or any older version, either) that implies that this is the model, or
from which I can derive this model. Perhaps I've missed something, but unless
you can show a derivation based on the normative wording actually in the
Standard, we can't use this model. (Or, of course, we can change the normative
wording to meet this model.)

The high-level semantics of "volatile" does not exist in the Standard; the word
"volatile" does not appear in 9.10 of the RM at all, and only appears in one
solitary AARM note in that clause.

So I'd like to see how you derive the above from the Standard. Or should the
Standard be changed to explicitly make this the model??

> See above, the point is that for Volatile variables there is a global
> order for reads and writes, assuming all accesses are sequential. For
> non-volatile shared variables that is not the case. So, task T1 and T2
> may see A updated before B, and
> T3 and T4 may see B updated before A, even if all accesses are made
> sequentially. Informally, copies of regular variables may be stored in
> local temporaries, including caches and registers, while that is not
> allowed for volatile variables.

Again, a fine model, but not backed up by any words in the Standard (at least
any that I can find). How best to achieve that model??

--------

And then I've moved the discussion to the ARG list. Enjoy. ;-)

****************************************************************

Questions? Ask the ACAA Technical Agent