CVS difference for ai12s/ai12-0267-1.txt

Differences between 1.3 and version 1.4
Log of other versions for file ai12s/ai12-0267-1.txt

--- ai12s/ai12-0267-1.txt	2018/06/16 01:19:39	1.3
+++ ai12s/ai12-0267-1.txt	2018/06/30 02:07:34	1.4
@@ -1,9 +1,9 @@
-!standard 5.1(1)                                      18-06-15  AI12-0267-1/03
-!standard 9.5(57/5)
+!standard 9.5(57/5)                                  18-06-23  AI12-0267-1/04
+!standard 9.5.1(7/4)
 !standard 9.10(11)
 !standard 9.10(15)
+!standard 9.10.1(0)
 !standard 11.5(19.2/2)
-!standard H.5(0)
 !standard H.5(1/2)
 !standard H.5(5/5)
 !standard H.5(6/2)
@@ -42,6 +42,19 @@
 it is semantically neutral (see 1.1.4(18) and 11.6(3/3)) or explicitly
 in the code as a task.
 
+We distinguish "data race" from the more general term "race condition"
+where "data race" refers to the case where two concurrent activities
+attempt to access the same data object without appropriate
+synchronization, where at least one of the accesses updates the object.
+Such "conflicting" concurrent activities are considered erroneous in
+Ada, per section 9.10 of the reference manual. The more general term
+"race condition" includes other kinds of situations where the effect
+depends on the precise ordering of the actions of concurrent activities.
+Race conditions can be benign, or even intentional, and cannot easily
+be detected in many cases. We make no particular attempt to prevent the
+more general notion of "race conditions," but we do hope to minimize
+data races.
+
 !proposal
 
 This proposal depends on the facilities for aspect Global (AI12-0079-1) and
@@ -74,13 +87,6 @@
 
 !wording
 
-Add a sentence to the end of 5.1(1):
-  A /parallel construct/ is a construct that introduces additional
-  logical threads of control without creating a new task, and includes a
-  parallel loop (see 5.5) and a parallel_block_statement (see 5.6.1).
-  [ed note: this particular new sentence probably deserves to be
-  specified in AI12-0119]
-
 Modify 9.5(57/5):
 
   A {parallel construct or a} nonblocking program unit shall not
@@ -89,6 +95,22 @@
   Nonblocking aspect is statically False, nor shall it contain any of
   the following:
 
+Add after 9.5.1(7/4):
+
+  If a parallel construct occurs within a protected action, no new logical
+  threads of control are created.  Instead, all parts of the parallel
+  construct execute using the same logical thread of control as that
+  of the protected action.
+
+  AARM Rationale: It would be feasible to allow multiple logical
+  threads of control within a protected action, but it would significantly
+  complicate the definition of "sequential" and "concurrent" actions,
+  since we generally presume that everthing occuring within protected
+  actions of a given protected object is sequential.  We could simply
+  disallow any use of parallel constructs, but that seems unnecessary,
+  particularly as a parallel construct might be buried within a
+  subprogram that is declared Nonblocking.
+
 Between 9.10(10) and 9.10(11):
   Remove "Erroneous Execution" subtitle (it will re-appear later).
 
@@ -106,41 +128,87 @@
   actions.
 
   Two actions are defined to /conflict/ if one action assigns to an
-  object, and the other action reads or updates a part of the same
+  object, and the other action reads or assigns to a part of the same
   object (or of a neighboring object if the two are not independently
   addressable).  The action comprising a call on a subprogram or an
   entry is defined to /potentially conflict/ with another action if the
   Global aspect (or Global'Class aspect in the case of a dispatching
   call) of the called subprogram or entry is such that a conflicting
-  action would be allowed during the execution of the call.  Similarly
+  action would be possible during the execution of the call. Similarly
   two calls are considered to potentially conflict if they each have
   Global (or Global'Class in the case of a dispatching call) aspects
-  such that conflicting actions would be allowed during the execution
+  such that conflicting actions would be possible during the execution
   of the calls.
 
-      Legality Rules
+  A /synchronized/ object is an object of a task or protected type, an
+  atomic object (see C.6), a suspension object (see D.10), or a
+  synchronous barrier (see D.10.1). [Redundant: Operations on such
+  objects are necessarily sequential with respect to one another, and
+  hence are never considered to conflict.]
 
-  A parallel construct is illegal if two concurrent actions within the
-  construct are known to refer to the same object (see 6.4.1) with uses
-  that potentially conflict, and neither action is within the scope of a
-  Suppress pragma for the Conflict_Check (see 11.5).
-
       Erroneous Execution
 
   The execution of two concurrent actions is erroneous if the actions make
   conflicting uses of a shared variable (or neighboring variables that are
   not independently addressable).
+
+Add new section:
+
+9.10.1 Conflict Check Policies
+
+This subclause determines what checks are performed relating to possible
+concurrent conflicting actions (see 9.10).
+
+  The form of a Conflict_Check_Policy pragma is as follows:
+
+    pragma Conflict_Check_Policy (/policy_/identifier);
+
+  A pragma Conflict_Check_Policy is allowed only immediately within a
+  declarative_part or as a configuration pragma.
+
+    Legality Rules
+
+  The /policy_/identifier shall be either Unchecked, Known_Conflict_Checks,
+  Parallel_Conflict_Checks, All_Conflict_Checks, or an implementation-defined
+  conflict check policy.
+
+    Static Semantics
 
-Add after 11.5(19.2/2)
+  The conflict check policy in effect at any point is determined by
+  the pragma Conflict_Check_Policy in the nearest enclosing declarative
+  region or compilation unit having such a pragma, or if none, by the
+  default policy of Parallel_Conflict_Checks (see below).
 
-Conflict_Check
-  Check that two or more concurrent actions do not make potentially
-  conflicting uses of the same shared variable (or of neighboring
-  variables that are not independently addressable), within the scope of
-  a Detect_Conflicts pragma. See H.5.
+      Implementation Requirements
 
-Change H.5 title to: Pragmas Detect_Blocking and Detect_Conflicts
+  The implementation shall impose restrictions related to possible
+  concurrent conflicting actions, according to which conflict check
+  policies are in effect at the place where the action or actions occur,
+  as follows:
 
+  * Unchecked
+    This policy imposes no restrictions.
+
+  * Known_Conflict_Checks
+    If this policy applies to two concurrent actions, they are
+    disallowed if they are known to refer to the same object (see 6.4.1)
+    with uses that potentially conflict.
+
+  * Parallel_Conflict_Checks
+    This policy disallows a parallel construct from reading or
+    updating a variable that is global to the construct, unless
+    it is a synchronized object, or unless the construct is
+    a parallel loop, and the global variable is an element of
+    an array with an index that is the loop parameter of
+    the loop_parameter_specification or the chunk index
+    parameter of the parallel loop.
+
+  * All_Conflict_Checks
+    This policy includes the restrictions imposed by the
+    Parallel_Conflict_Checks policy, and in addition disalllows a task
+    body from reading or updating a variable that is global to the task
+    body, unless it is a synchronized object.
+
 Modify H.5(1/2):
   The following pragma [forces] {requires} an implementation to detect
   potentially blocking operations [within] {during the execution of} a
@@ -160,41 +228,6 @@
   subprogram{, or a parallel construct occurring within the compilation
   unit}.
 
-Add after H.5(6/2)
-
-  The following pragma requires an implementation to detect potentially
-  conflicting uses of shared variables by concurrent actions (see 9.10).
-
-Syntax
-  The form of a pragma Detect_Conflicts is as follows:
-
-    pragma Detect_Conflicts;
-
-Post-Compilation Rules
-
-  A pragma Detect_Conflicts is a configuration pragma.
-
-Dynamic Semantics
-
-  An implementation is required to detect that two concurrent actions
-  make potentially conflicting uses of the same shared variable (or of
-  neighboring variables that are not independently addressable) if the
-  actions occur within a compilation unit to which the pragma applies
-  (see 9.5). Program_Error is raised if such potentially conflicting
-  concurrent actions are detected.
-
-    AARM Ramification: Such uses are already statically illegal by rules
-    in 9.10 proposed above if the concurrent actions are "known to refer
-    to the same object" and the actions occur within a parallel
-    construct. This dynamic check covers tasking-related concurrency,
-    and cases in parallel constructs where the names used to refer to
-    the objects are dynamic (e.g. use variable array indices).
-
-    AARM Implementation Note: Implementing this can be expensive, both
-    in terms of time and space, if the references that use such dynamic
-    names are inside of loops. Hence, this is probably only appropriate
-    during testing of an application.
-
 !discussion
 
 It is important for the programmer to receive an indication from the
@@ -231,37 +264,22 @@
 apply no matter how the concurrency is introduced, so they apply
 to concurrency associated with "normal" Ada tasking.
 
-We are making data races illegal in parallel constructs when the
-concurrent actions are "known to refer to the same object" as defined in
-6.4.1. For more dynamic cases, we have proposed a Detect_Conflicts pragma
-to turn on data-race detection at run time. This is a configuration
-pragma, so it is straightforward to apply it to an entire program
-library. Suppressing Conflict_Check is a way to indicate that a "true"
-conflict is not believed to occur. At run-time, more exact checks using
-address comparison can be performed to determine whether a "true"
-conflict occurs, when array indexing or pointer dereferencing are
-involved. Note that for parallel constructs, this checking is always
-"local" since it is about potential conflicts, and the compiler can rely
-on the Global (or Global'Class) aspect to determine whether a call
-"action" potentially conflicts with some other concurrent action.
-
-A compiler that can go beyond what "known to refer to the same object"
-at compile-time could certainly produce a warning that a Conflict_Check
-was "certain to fail" at run-time. But we felt as far as specified
-compile-time checks, we should limit ourselves to what "known to refer
-to the same object" requires in terms of compile-time analysis.
-
-Note that Detect_Conflicts applies to data races associated with the
-concurrency introduced by "normal" Ada tasking as well as that
-associated with our newly proposed parallel constructs.
-
-We have defined the Detect_Conflicts pragma in the same subclause (H.5)
-as that for the Detect_Blocking pragma, as it is a potentially quite
-expensive check, and probably only appropriate during testing.
-Alternative places for this definition might be 9.10 Shared Variables or
-C.6 Shared Variable Control.  Since a "true" conflict is considered to
-be erroneous according to 9.10, even without H.5 the compiler can insert
-run-time checks to detect data races.
+We define four "conflict check policies" to control the level of checking
+that is performed to prevent data races.  The most restrictive policies
+ensure that individual actions do not read or update variables that
+are visible to other logical threads of control.  This is quite
+conservative, as it will complain even if the given variable is
+manipulated by only one logical thread of control.
+
+The Known_Conflict_Checks policy is less restrictive, and is intended
+to only disallow conflicts that are clearly unsafe.  The Unchecked
+policy imposes no restrictions whatsoever.
+
+It was felt that the default should be upward compatible with existing
+code, but completely safe for new uses of parallel constructs.  As such
+it disallows all uses of un-synchronized globals, unless the reference
+is to an element of an array using either the loop parameter or
+the chunk index as the index into the array.
 
 !ASIS
 
@@ -722,25 +740,205 @@
 From: Randy Brukardt
 Sent: Friday, June 15, 2018  8:17 PM
 
-> Here is a new version that attempts to address most of Randy's 
-> comments.  Both non-blocking checks and compile-time conflict checks 
+> Here is a new version that attempts to address most of Randy's
+> comments.  Both non-blocking checks and compile-time conflict checks
 > are on by default for parallel constructs.
 
 Thank you very much; I like this version much better.
 
-For the record, I deleted a couple of extra spaces and added a missing period 
+For the record, I deleted a couple of extra spaces and added a missing period
 when posting.
 
 There might be some value to describing the model of the data race checks for
 tasks, since it didn't seem obvious to me.
 
-Also, there might be value in describing the difference between a "data race" 
-and a "race condition" (you did this once for me in e-mail, which I happened 
-to re-read last night when working on AI12-0240-2; I doubt most people 
+Also, there might be value in describing the difference between a "data race"
+and a "race condition" (you did this once for me in e-mail, which I happened
+to re-read last night when working on AI12-0240-2; I doubt most people
 understand the difference). And in particular, that there is no detection of
 race conditions (which isn't really possible, and as you pointed out, aren't
 even erroneous in an Ada sense).
 
 No rush on those though.
+
+****************************************************************
+
+From: Erhard Ploederder
+Sent: Saturday, June 23, 2018  4:16 PM
+
+Here are a few relevant examples for determining data races. The AI should have
+good answers to the questions raised below.
+
+--------------
+
+Example 1: Are the rules really conservative?
+
+   type IP is access all Integer;
+   AP: IP;
+   A,B,C: aliased Integer;
+
+   procedure A_Read is    -- with Globals in: AP, Heap;  Globals out: C
+      begin
+         C := AP.all;
+      end;
+
+   procedure A_Write is -- with Globals out: A
+      begin
+         A := 42;
+      end;
+
+and somewhere in the universe:
+ if Random then AP := A'access; else AP := B'access; end if;
+
+There is a data race if Random=true. Is this data race detected?
+
+If so, what about the data-race-freeness of:
+
+   procedure C_Write is -- with Globals out: C
+      begin
+         C := 42;
+      end;
+
+--------------
+
+Example 1a:
+and, dropping the "aliased", I missed rules that handle the race between A_Write
+and Write(A) for
+   procedure Write(X: out Integer) is -- Globals = {}
+   begin X := 21; end Write;
+
+-----------------------------------------------
+
+Example 2: do the rules prevent legitimate programs?
+
+The following idiom (minus the B, which I added just for fun) to protect the
+uses of A gets taught in C++ classes:
+
+   Ready: Boolean := False with Atomic, Volatile;
+         -- I never remember which one implies the other in Ada
+   -- A and B of arbitrary type, here Integer
+   A, B: Integer := 0;
+
+     procedure Write is   -- Globals out: A
+                          -- Globals in: B
+                          -- Globals in out: Ready
+      begin
+         while Ready loop null; end loop;
+         A := 42 + B;
+         Ready := False;
+      end Write;
+
+      procedure Read is  -- with Globals out: B
+                         -- Globals in: A
+                         -- Globals in out: Ready
+      begin
+         while not Ready loop null; end loop;
+         B := A - 42;
+         Ready := True;
+      end;
+
+This code does not have a data race, not even a general race condition.
+Illegal in Ada? or legal only, if all ckecks are off ??? Neither will be good
+advertising for Ada.
+
+
+****************************************************************
+
+From: Tucker Taft
+Sent: Saturday, June 23, 2018  7:27 PM
+
+OK, here is a nearly complete re-write of AI12-0267 which checks for data races.
+The stuff relating to nonblocking is not particularly changed, though we did
+decide to say that a parallel construct inside a protected action is legal, but
+does not actually create any new logical threads of control. [This is version
+/04 of the AI - Editor.]
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Friday, June 29, 2018  8:52 PM
+
+> Here are a few relevant examples for determining data races.
+> The AI should have good answers to the questions raised below.
+
+My opinion is that examples writing global objects are nearly irrelevant. Only
+tasking gurus can figure out if such things are safe -- we don't even have tools
+that can do it. And our goal ought to be to make it possible for the largest
+number of programmers to write working parallel code. If that requires a tasking
+guru, we've gained nothing.
+
+It makes sense to have an "anything goes" mode so people that who think that
+they actually understand tasking can use these features unfettered -- that will
+be valuable for a few experts to write libraries for everyone else to use -- but
+it probably will cause countless others to shoot themselves in the foot.
+
+...
+> The following idiom (minus the B, which I added just for fun) to
+> protect the uses of A gets taught in C++ classes:
+
+This of course is precisely the problem I'm concerned about.
+
+>    Ready: Boolean := False with Atomic, Volatile;
+>          -- I never remember which one implies the other in Ada
+>    -- A and B of arbitrary type, here Integer
+>    A, B: Integer := 0;
+>
+>      procedure Write is   -- Globals out: A
+>                           -- Globals in: B
+>                           -- Globals in out: Ready
+>       begin
+>          while Ready loop null; end loop;
+>          A := 42 + B;
+>          Ready := False;
+>       end Write;
+>
+>       procedure Read is  -- with Globals out: B
+>                          -- Globals in: A
+>                          -- Globals in out: Ready
+>       begin
+>          while not Ready loop null; end loop;
+>          B := A - 42;
+>          Ready := True;
+>       end;
+>
+> This code does not have a data race, not even a general race
+> condition.
+
+No one but a true tasking guru can prove that. (It would likely take me 4 hours
+of reading rules and simulating code to verify that you wrote the above example
+correctly.) And using an "idiom" rather than simply using the language
+abstractions provided for that purpose to protect objects seems like a terrible
+inversion.
+
+In cases like this, A and B should be in a protected object. That does put
+pressure on vendors to provide multiple implementations of protected objects,
+especially lightweight ones to use when there are no queues. But using a safe
+abstraction will adapt better to whatever the next hardware innovation turns out
+to be, unlike depending on a particular implementation of a lock.
+
+> Illegal in Ada? or legal only, if all ckecks are off ???
+> Neither will be good advertising for Ada.
+
+Only among people who want to work a lot harder than necessary to get parallel
+code working. I'd expect it to be better advertising for Ada to tell them that
+they don't have to write "idioms" that are easy to get wrong, but rather can
+write simple, safe abstractions for inter-thread communication -- and the Ada
+compiler will check for most common mistakes.
+
+I know from experience that it is nearly impossible to get the simplest piece of
+code like the above correct, and even identifying problems to worry about is a
+difficult problem. That can never be the way for the majority of programmers to
+work. Ada is not going to grow if only a few elite programmers can use it!
+
+Even restricting usage to POs (and reading) isn't guaranteed to be perfect, but
+it seems to be the best that can be done statically. Perhaps by Ada 2028 we can
+give some help in the design and use of such POs.
+
+On one point I do agree with you: we're spending a lot of time getting these
+rules right, but they're not really going to help. I'd say that's because
+including atomic objects is going to allow a variety of badly designed code --
+personally, I'd ONLY allow writing of global POs in parallel operations, and no
+other writing. I want to put the work into allowing cases of reading that can't
+naturally be allowed (like cursor operations in the containers).
 
 ***************************************************************

Questions? Ask the ACAA Technical Agent