Version 1.9 of ai12s/ai12-0064-1.txt

Unformatted version of ai12s/ai12-0064-1.txt version 1.9
Other versions for file ai12s/ai12-0064-1.txt

!standard 9.5.1(11)          15-10-07 AI12-0064-1/05
!standard 9.5.1(18)
!class Amendment 13-04-22
!status work item 13-04-22
!status received 13-04-22
!priority Medium
!difficulty Medium
!subject Nonblocking subprograms
!summary
Aspect Nonblocking is added.
!problem
During a protected action, it is a bounded error to invoke an operation that is potentially blocking. There is currently no mechanism (other than a comment) to specify that a given subprogram is intended to be safely callable during a protected action (i.e., that the subprogram will not invoke an operation that is potentially blocking). This seems like a useful part of a subprogram's "contract" that should be (optionally) specifiable at the point of a subprogram's declaration.
!proposal
Modify 9.5.1(11):
* an entry_call_statement{, or a call on a procedure that renames or is implemented by an entry};
Add after 9.5.1(18):
For a program unit other than a protected operation, for a formal package, formal subprogram, formal object of an anonymous access-to-subprogram type, and for a named access-to-subprogram type (including a formal type), the following language-defined representation aspect may be specified:
Nonblocking
The type of aspect Nonblocking is Boolean. When aspect Nonblocking is False for a program unit, the entity might contain a potentially blocking operation. If the aspect is True for a program unit, the program unit is said to be nonblocking. If directly specified, the aspect_definition shall be a static expression. This aspect is inherited by overridings of dispatching subprograms.
If not specified for a generic instantiation, the aspect is determined by the setting for the generic unit. For any other program unit, formal package, formal subprogram, formal object, or (formal) access-to-subprogram type, the aspect is determined by the setting for the innermost program unit enclosing the entity. For the purposes of this rule, at the point of an instantiation which has its own explicit specification of Nonblocking, the program unit enclosing the associated formal parameters is considered to be the instantiation, not the generic.
AARM Ramification: this allows an instantiation to override the default specified on the generic unit. However, this only establishes a default for the formal parameters; any explicit specification of Nonblocking on a formal must still be observed.
If not specified for a library unit, the default is True if the library unit is declared pure and is not a generic unit, and False otherwise.
A nonblocking program unit shall not contain, other than within nested units with Nonblocking specified as False, a call on a callable entity for which the Nonblocking aspect is False, nor shall it contain any of the following:
* a select_statement;
* an accept_statement;
* an entry_call_statement, or a call on a procedure that renames or is implemented by an entry;
* a delay_statement;
* an abort_statement;
* task creation or activation.
A subprogram shall be nonblocking if it overrides a nonblocking dispatching operation. An entry shall not implement a nonblocking procedure. In an Access attribute_reference for a nonblocking access-to-subprogram type, the subprogram denoted by the prefix shall be nonblocking. In a conversion (implicit or explicit) to a nonblocking access-to-subprogram type, the operand shall be of a nonblocking access-to-subprogram type.
In a generic instantiation:
* the actual subprogram corresponding to a nonblocking formal subprogram shall be nonblocking (an actual that is an entry is not permitted in this case);
* the actual type corresponding to a nonblocking formal access-to-subprogram type shall be nonblocking;
* the actual object corresponding to a formal object of a nonblocking access-to-subprogram type shall be of a nonblocking access-to-subprogram type;
* the actual instance corresponding to a nonblocking formal package shall be nonblocking.
In addition to the places where Legality Rules normally apply (see 12.3), the above rules apply also in the private part of an instance of a generic unit.
AARM Ramification: specifying Nonblocking is False imposes no requirements. Specifying Nonblocking is True imposes additional compile-time checks to prevent blocking, but does not prevent deadlock. pragma Detect_Blocking can be used to ensure that Program_Error is raised in a deadlock situation.
!discussion
We considered changing the aspect name from "Nonblocking" to "Potentially_Blocking," as that matches RM terminology better, but we ultimately concluded that would be a mistake. Furthermore, "nonblocking" is used in 9.5.1, albeit somewhat informally. Were we to switch to Potentially_Blocking, the default would be True rather than False, which is unlike other Boolean aspects. Furthermore, with Potentially_Blocking => True, we wouldn't require that it be potentially blocking, merely allow it. Perhaps Allow_Blocking would be better, but that doesn't match RM terminology at all, and still has the "wrong" default.
We initially modeled this aspect after No_Return, which has a somewhat similar purpose and presumably has already worked out some of the needed rules. However, we have gone beyond that, because we now have nonblocking access-to-subprogram types, nonblocking formal subprograms, etc.
The rules do not allow calling "normal" subprograms from a nonblocking subprogram. This allows detecting any potentially blocking operations used in a nonblocking subprogram statically. This is important if pragma Detect_Blocking is used, as such detection is required. (Otherwise, this is just a bounded error and the "mistake" can be ignored with the usual consequences.)
We have provided package-level defaults, given that many packages will have all of their subprograms non-blocking. We chose to make the default for a declared pure, non-generic library unit to be nonblocking, as that is almost always the case, since blocking typically implies the use of some kind of global lock. We do not foresee significant incompatibilities, since declared pure library units may only depend on other declared pure library units. For pure generic units we leave the default at False for compatibility reasons, because these might have existing instances where an actual subprogram (or access-to-subprogram type) is potentially blocking.
We did not specify that protected subprograms are by default Nonblocking=>True, since that would be incompatible, as they then could not call subprograms with a default Nonblocking aspect value of False. It might be possible to specify Nonblocking=>True as the default for protected subprograms in a future version of the standard (and clearly an implementation could at least provide a warning when a call is made to a subprogram with Nonblocking of False). Because of the confusion related to the fact that protected operations are always required to be nonblocking at run-time, we don't allow specifying the attribute directly on an individual protected operation. However, we allow specifying Nonblocking on a protected unit to determine the setting for all of the enclosed protected operations.
It will be necessary to sprinkle appropriate annotations throughout the language-defined packages to match the current blocking vs. potentially-blocking categorizations. We leave most of the details of that for the next revision of this AI, but here is our start:
The default of Nonblocking=>True for non-generic declared-pure library units helps a bit (but not much). We could reasonably apply Nonblocking=>True to all generic packages that have only scalar types and a few constants as formal parameters (e.g. the numerics packages).
Presumably the I/O packages are potentially blocking, but we could mark the Put/Get routines that put into a string or get from a string as Nonblocking (see the !example).
We could identify the Container packages as by default Nonblocking, including by default all of the formal functions Hash, Equivalent_Keys, "=", "<", etc. But we wouldn't want to presume that the access-to-subprogram parameters are nonblocking, so the operations taking them would be marked with Nonblocking=>False (e.g. Query_Element and Update_Element). We have proposed above that you can override the Nonblocking specification on a generic in an instance, so that remains a work-around if the user is desperate to pass in a Hash function that is potentially blocking.
!example
package Ada.Text_IO with Nonblocking => False is ... generic type Enum is (<>); package Enumeration_IO is -- implicitly Nonblocking => False
Default_Width : Field := 0; Default_Setting : Type_Set := Upper_Case;
procedure Get(File : in File_Type; -- implicitly Nonblocking => False ...
procedure Get(From : in String; Item : out Enum; Last : out Positive) with Nonblocking => True; -- explicitly Nonblocking => True
procedure Put(To : out String; Item : in Enum; Set : in Type_Set := Default_Setting) with Nonblocking => True; -- explicitly Nonblocking => True
end Enumeration_IO ... end Ada.Text_IO;
!ASIS
TBD.
!ACATS test
ACATS B-Tests and C-Tests.
!appendix

From: Tucker Taft
Sent: Monday, October 6, 2014  10:35 AM

Another section of the HILT paper related to a Potentially_Blocking aspect.
Below is that section.  As Randy and others have pointed out, we would need to
put a specification of the Potentially_Blocking aspect on each of the existing
Ada standard library packages, since the default implies blocking.

-Tuck
----------
Another important piece of knowledge the caller of a subprogram might need to
know is whether or not the call is potentially blocking. The Ada language
defines potentially blocking operations to include select statements, accept
statements, delay statements, abort statements, and task creation or activation,
among others. When executing parallel code, potentially blocking operations can
cause problems such as deadlocks. Currently there is no standard way in Ada to
specify that a subprogram is potentially blocking. If the compiler cannot
statically determine that a subprogram call is potentially blocking, the
programmer has to rely on run-time checking to detect these sorts of problems.
We propose the addition of a boolean Potentially_Blocking aspect that can be
applied to subprogram specifications to indicate whether they use constructs
that are potentially blocking or call other subprograms that have the
Potentially_Blocking aspect with a value of True. Such an aspect enhances he
safety of parallel calls, and also generally improves the safety of Ada, since
it allows the compiler to statically detect more problems involving calls on
potentially blocking subprograms. The default value for the Potentially_Blocking
aspect is True.

We also propose that these defaults can be overridden for a package by allowing
these aspects to be specified at package level, with the meaning that they
establish a default for all subprograms in the package. For example,

package My_Stuff
    with Global => (In_Out => Synchronized),
         Potentially_Blocking => False
is
    procedure Do_Something (X : in out T;
                            Y : in U);
    function Query_Something (A : T)
          return Z;
       ...
end My_Stuff;

Indicates that all subprograms in package My_Stuff involve access to
synchronized globals, and all of these calls are not potentially blocking calls
(in particular these cannot include entry calls, delays, select statements, etc.
[23, section 9.5.1]). Such an annotation would alleviate the need to repeat the
Global or Potentially_Blocking aspect on each subprogram, as long as the
package-level default is appropriate for that subprogram.

In the absence of such an explicit package-wide default, the default for
Potentially_Blocking would be True, and the default for Global would be (In_Out
=> all) in a normal package, and null in a declared-pure package.

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

From: Tucker Taft
Sent: Tuesday, October 14, 2014  12:04 PM

Here is a very modest update to AI-0064 on the Nonblocking aspect (or
Potentially_Blocking if you prefer).  I hadn't realized it was on my list of
homework until today...
[Editor's note: This is version /03 of the AI.]


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

From: Tucker Taft
Sent: Wednesday, June 17, 2015  6:46 AM

After going back and forth a couple of times, I settled on Nonblocking rather
than Potentially_Blocking for the name of the aspect.  See the !discussion for
an explanation. [This is version /04 of the AI - Editor.]

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

From: Randy Brukardt
Sent: Thursday, June 18, 2015  12:10 AM

Mostly looks good. A couple of comments:

...

> !proposal
>
> Add an aspect Nonblocking
>
> Add at the end of 9.5.1 (as continuation of bounded error section?)
>
>    For a callable entity, a generic subprogram, a package, a generic
>    package, or a protected unit, the following language-defined
>    representation aspect may be specified:
>
>        The type of aspect Nonblocking is Boolean. When aspect Nonblocking
...

Something wrong here, as there is no aspect name given. Based on the rest of the
text, "Nonblocking" needs to be inserted under the colon. I'll fix this in the
posted version.

-------

There doesn't seem to be an optional way to specify nonblocking for a formal
subprogram. I think that will be necessary if we want to require nonblocking on
container operations (for instance, in a future parallel container).

In particular, if we have an ordered map:

    generic
       type Key_Type is private;
       type Element_Type is private;
       with function "<" (Left, Right : Key_Type) return Boolean is <>;
       with function "=" (Left, Right : Element_Type) return Boolean is <>;
    package Ada.Containers.Nonblocking_Ordered_Maps is
       ...
       function Find (Container : Map; Key : Key_Type) return Cursor
          with Nonblocking;
       ...

The calls to "<" in Find would be illegal, as the function doesn't have
Nonblocking = True. One could imagine somehow deferring this check until the
instantiation, but of course Legality Rules aren't enforced in the body of an
instance. And I'm sure we don't want a runtime check here.

If one put the Nonblocking on the package as a whole, then the problem becomes
that we don't have any rule that would prevent instantiation with a function "<"
that isn't nonblocking. Again, the Legality Rule that would fail is in the body
of the generic, so it isn't rechecked (in that case, the body of Find would
compile successfully, but the promise would be violated).

What we want, I think, is two things: (1) the ability to specify the aspect on
the formal subprogram (its weird to only allow inheriting it, and if you wanted
two subprograms to have different setting you'd be out of luck); and (2)
matching rules for actuals of formal subprograms when Nonblocking = True (either
explicitly, or inherited from an outer package). [Specifically, it's an error if
the actual function has Nonblocking = False when the formal subprogram has
Nonblocking = True. Otherwise, it's OK.]

We don't have any aspects that can be specified on generic formals today, but
we've always planned that some would appear eventually. The main thing that each
one needs is a matching rule; this one seems simple.

No_Return doesn't have any such thing, because it doesn't really come up for
that. So I'm not surprised that it is missing.

(I'm dubious about not having a mechanism for access-to-subprogram as well, but
since I don't have a use case for that, I won't push there.)

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

From: Tucker Taft
Sent: Thursday, June 18, 2015  6:19 AM

> Something wrong here, as there is no aspect name given. Based on the
> rest of the text, "Nonblocking" needs to be inserted under the colon.
> I'll fix this in the posted version.

Good point.  Thanks for the quick fix.

> ... What we want, I think, is two things: (1) the ability to specify
> the aspect on the formal subprogram (its weird to only allow
> inheriting it, and if you wanted two subprograms to have different
> setting you'd be out of luck); and
> (2) matching rules for actuals of formal subprograms when Nonblocking
> = True (either explicitly, or inherited from an outer package).
> [Specifically, it's an error if the actual function has Nonblocking =
> False when the formal subprogram has Nonblocking = True. Otherwise,
> it's OK.]

Agreed.

> ... (I'm dubious about not having a mechanism for access-to-subprogram
> as well, but since I don't have a use case for that, I won't push
> there.)

We will probably want something on access-to-subprogram as well.  The matching
rules are analogous to that for formal subprograms.

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

From: Erhard Ploedereder
Sent: Thursday, June 18, 2015  12:14 PM

> Specifying Nonblocking is True imposes
>         additional compile-time checks to prevent blocking, but does not
>         prevent deadlock.

I am curious about the rationale of this statement. At first glance, the rules
now seem to ensure that there cannot a nested potentially-blocking call. So, how
could a deadlock (in the usual sense of deadly embrace) ever arise?

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

From: Tucker Taft
Sent: Thursday, June 18, 2015  2:07 PM

On a multiprocessor, I think this would do it:

     protected A is
        procedure Hello with Nonblocking;
     end A;

     protected B is
        procedure Goodbye with Nonblocking;
     end B;

     protected body A is
        procedure Hello is
        begin
           B.Goodbye;
        end Hello;
     end A;

     protected body B is
        procedure Goodbye is
        begin
           A.Hello;
        end Goodbye;
     end B;

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

From: Jean-Pierre Rosen
Sent: Thursday, June 18, 2015  2:52 PM

>     protected A is
>        procedure Hello with Nonblocking;
>     end A;

Why would you put a Nonblocking aspect on a protected procedure? It has to be
non-blocking anyway. The aspect shouldn't even be allowed on protected
operations.

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

From: Tucker Taft
Sent: Thursday, June 18, 2015  3:08 PM

The Nonblocking aspect provides *compile-time* enforcement of checks against use
of potentially blocking operations.  So the "with Nonblocking" on a protected
procedure causes these checks to be performed at compile-time, which in turn
requires that any non-protected subprogram it calls to be similarly marked
Nonblocking.  So the aspect does have a significance for protected operations,
as it says they may call only subprograms with Nonblocking => True.  The AI
allows the aspect to be specified on the protected unit as a whole, or on an
enclosing package, to set an appropriate default, so you don't have to specify
it individually on each operation.

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

From: Jean-Pierre Rosen
Sent: Thursday, June 18, 2015  3:23 PM

So it's really "with nonblocking_check". Nonblocking means that the procedure is
nonblocking, while here it means that the protected procedure does not call any
potentially blocking operation. Well, we can discuss whether it is important to
discuss ;-) at the meeting.

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

From: Erhard Ploedereder
Sent: Thursday, June 18, 2015  8:51 PM

So, if one expanded the rule that the Nonblocking entity may not
   - call a potentially blocking operation (such as any protected op)
   - call any entity that is not nonblocking we would get the desired
     deadlock-freeness, and we could compile-time check it. (??)

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

From: Randy Brukardt
Sent: Thursday, June 18, 2015  10:28 PM

> So, if one expanded the rule that the Nonblocking entity may not
>    - call a potentially blocking operation (such as any protected op)

Only protected entry calls and external calls *on the same object* are
potentially blocking. The vast majority of protected subprogram calls are *not*
potentially blocking. I don't see the point of rejecting all of them just
because there might be one that is "potentially blocking". (And you can't tell
statically if or if not a particular call is going to be "potentially
blocking".) Note that this particular case is *not* blocking (protected
subprograms never block), it's a bounded error (and it really should have been
an unconditional Program_Error).

Besides, the effect of such a rule would be to totally prohibit any use of
protected objects in a nonblocking operation. You don't need "nonblocking" to do
that (I'm sure AdaControl can ban any declaration of a protected object), and
making such a restriction would prevent the vast majority of shared data
structures from a nonblocking subprogram. That would throw out the baby with the
bathwater.

>    - call any entity that is not nonblocking we would get the desired
> deadlock-freeness, and we could compile-time check it. (??)

Finally, I don't see why you care about this obscure corner case. Approximately
0.0% of all deadlocks that happen in practice occur because of nested protected
actions. That's because most task runtimes detect that bounded error and raise
Program_Error (which prevents such a deadlock from happening) - at least in the
case when it actually happens - and a user can use pragma Detect_Blocking for
any runtime that doesn't.

Real deadlocks come from operations that by their nature are blocking, or from
task operations (that happens to us a lot in Claw). Nonblocking isn't going to
be of any help for that. The fact that there are a few unlikely cases which
should raise Program_Error (but might not in some brain-damaged system) doesn't
have any effect on the real causes of deadlocks.

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

From: Tucker Taft
Sent: Friday, June 19, 2015  1:35AM

> So, if one expanded the rule that the Nonblocking entity may not
>     - call a potentially blocking operation (such as any protected op)

As Randy points out, the only time a protected subprogram call is considered
"potentially blocking" by is when it will result in deadlock (see 9.5.1(15)).
It was really a misnomer to include this in the set of potentially blocking
operations, but as the AARM says in 9.5.1(15.a): "This is really a deadlock call
rather than a blocking call, but we include it here for simplicity."  In
retrospect, probably should have been a separate rule.  In any case, 9.5.1(15)
is not easily detectable statically (it requires looking at the global call
graph, and considering the possible value of access-to-protected-objects, etc.).
So this AI drops this kind of deadlock detection from the semantics of the
Nonblocking aspect, as it is not practical for the average Ada compiler to
perform.

>     - call any entity that is not nonblocking we would get the desired
> deadlock-freeness, and we could compile-time check it. (??)

No, as explained above.  Also Randy points out that there are two kinds of
deadlock, one involves a cyclic locking situation, which is relatively rare, and
is something that a static analysis tool could pretty easily detect (given a
global call graph).  The other relates to tasks waiting on entries for a
particular state to occur, and that particular state never occurring.  That
requires solving the halting problem to be completely precise... ;-)

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

From: Tucker Taft
Sent: Wednesday, October 7, 2015  5:32 PM

OK, here is a revision of this AI. [This is version /05 of the AI, editor.]

I have now allowed a specification of Nonblocking on almost anything *except*
a protected operation (because it was too confusing there).  If you want to
cause compile-time checks on the operations of a protected type, you put it
on the type, not on the individual operations.

I have also added support for access-to-subprogram, formal subprograms, etc.
It gets a bit hairy.

I have also allowed you to override the default setting established by a
generic in an instantiation, though it only affects the generic formals that
don't have their own explicit specification of Nonblocking.

I took a first stab at what language-defined units should have an explicit
Nonblocking.

I also made the default for non-generic declared-pure library units be
Nonblocking=>True. This should help somewhat.

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

Questions? Ask the ACAA Technical Agent