CVS difference for ai05s/ai05-0275-1.txt

--- ai05s/ai05-0275-1.txt	2011/12/28 05:55:26	1.1
+++ ai05s/ai05-0275-1.txt	2012/02/14 03:57:53	1.2
@@ -1,6 +1,7 @@
-!standard C.6(16)                                            11-12-27  AI05-0275-1/01
+!standard C.6(16)                                     12-02-13  AI05-0275-1/02
 !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
@@ -47,17 +48,27 @@
 
 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. 
+memory barrier.
 
 !discussion
 
-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).
+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).
+
+[*** Editor's note: Geert Bosch objects to the above discussion, and gives a
+very different model of what Volatile means. See the e-mail of December 30th. I
+actually prefer it to the wording in the Standard, but cannot derive his model
+from anything in the Standard. Most importantly, his higher-level model offers
+the possibility of describing the meaning of Volatile in semantic terms, which
+would be a big improvement over the current version of C.6(16/3). He, OTOH,
+seems content with C.6(16/3), but perhaps that's because he isn't planning on
+paying any attention to it. :-) ***]
 
 
 Memory barriers are only needed between sequential actions involving shared variables.
@@ -106,10 +117,9 @@
 performed directly to memory.
 @dby
 All tasks of the program (on all processors) that read or update volatile
-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).
+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
 
@@ -174,15 +184,15 @@
 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 
+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 
+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:
@@ -207,8 +217,8 @@
 
 Dear Alan,
 
-Geert Bosch has forwarded the following to the ARG, hoping for 
-comments. we are currently discussing his message, and all those 
+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
@@ -217,7 +227,7 @@
 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 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!
 
@@ -249,9 +259,9 @@
 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 
+> 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.
@@ -295,5 +305,311 @@
 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. ;-)
 
 ****************************************************************