Version 1.8 of ais/ai-00165.txt

Unformatted version of ais/ai-00165.txt version 1.8
Other versions for file ais/ai-00165.txt

!standard C.7.2 (13)          00-06-19 AI95-00165/08
!standard C.7.2 (15)
!standard C.7.2 (16)
!class binding interpretation 96-10-04
!status Corrigendum 2000 99-07-28
!status WG9 approved 98-06-12
!status ARG Approved 10-0-0 98-04-01
!status work item 96-10-04
!status received 96-10-04
!priority Medium
!difficulty Medium
!qualifier Clarification
!subject Recursive use of task attributes
!summary
If the package Ada.Task_Attributes is instantiated with a controlled type and the controlled type has user-defined Adjust or Finalize operations that in turn access task attributes via instantiated interfaces of this generic package, then a call of Set_Value of the instantiated package constitutes a bounded error. The call may perform as expected or it may result in a deadlock of the calling task and subsequently of the entire partition or of other tasks accessing task attributes.
Accesses via an Attribute_Handle (as obtained by calling the function Reference) are not subject to the atomicity requirement of C.7.2(16). Such accesses, if concurrent with each other or with the execution of any of the subprograms provided by the package, are erroneous.
!question
Paragraph 16 of C.7.2 says, in full, "The implementation shall perform each of the above operations for a given attribute of a given task atomically with respect to any other of the above operations for the same attribute of the same task."
Let us call an (attribute, task) pair a 'cell' for convenience. The atomicity requirement cannot be met if an operation on a cell recursively invokes an operation on the same cell: an operation cannot be atomic with respect to another operation embedded within itself.
What is the intent?
These operations can be recursive, because they perform finalization and assignment, which might invoke a user-defined Finalize or Adjust procedure, which might then recursively call the operation in question.
Here is an example of a recursive call to Set_Value:
with Ada.Finalization; use Ada.Finalization; with Ada.Task_Attributes; package An_Attr is type Attr is new Controlled with record N : Integer; end record; procedure Adjust(X : in out Attr);
package Ops is new Ada.Task_Attributes(Attr, Initial_Value => (Controlled with 0));
end An_Attr;
with Ada.Text_IO; use Ada.Text_IO; package body An_Attr is Depth : Natural := 0;
procedure Adjust(X : in out Attr) is begin Put_Line((1..2*Depth => ' ') & "Adjust called"); Depth := Depth + 1; if Depth <= 3 then Put_Line((1..2*Depth => ' ') & "calling Set_Value..."); Ops.Set_Value((Controlled with Depth)); end if; end Adjust;
end An_Attr;
with Ada.Finalization; use Ada.Finalization; with An_Attr; procedure A_Prog is begin An_Attr.Ops.Set_Value((Controlled with 17)); -- One call end A_Prog;
Finally, what happens if one of the operations of the package is concurrently executed with an access via an attribute handle? Is there an atomicity requirement on the latter as well?
!recommendation
A deadlock cannot be sensibly avoided when a recursive access via one of the interfaces of the package occurs to the same task attribute of the same task. Accesses via an Attribute_Handle are not subjected to the same atomicity and hence locking requirement. Therefore there are already dangerous situations and it seems inappropriate to impose a major performance penalty on some implementations in order to narrow only the already sufficiently rare deadlocking cases as much as possible.
A more liberal interpretation is recommended that allows implementations to choose the most appropriate lock granularity. A nested access to a task attribute from within a Finalize or Adjust procedure becomes a bounded error. Depending on the lock granularity, the initiating call of Set_Value will either deadlock or perform its nested accesses as expected. Concurrent accesses via Attribute_Handles are deemed erroneous.
The summary of this issue specifies these semantics in more detail.
!wording
The wording of the dynamic semantics in C.7.2 should be expanded to advise the user of the bounded error situation, respectively the erroneousness of concurrent accesses via an Attribute_Handle, as described in the summary of this AI.
There should be an additional implementation permission to choose a coarser granularity of the lock than needed to keep the operations atomic for each individual task attribute of each individual task.
!discussion
The atomicity of the operations will require some locking mechanism to prevent concurrent accesses to the same task attribute of a given task. C.7.2(16) seems to imply that an individual lock is provided for each attribute of each task. However, obtaining a lock can be a rather expensive operation, particularly for implementations that utilize the locking primitives of an underlying operating system.
If the attribute does not involve controlled types with user-defined Adjust and Finalization routines, then a single run-time lock suffices to achieve the semantics of C.7.2(16).
If the attribute is of a controlled type or has components of a controlled type, then the implicitly invoked user-defined Adjust or Finalize routines are presently not forbidden to call on operations of this package for other task attributes or even, rather pathologically, for the same task attribute of the given task. Whatever locking strategy is applied, the latter will lead to a deadlock. The former can lead to a deadlock if the granularity of the lock is any larger than on single attributes of any task, e.g., a lock per task or a global run-time lock.
It seems unwise to require all implementations to provide a potentially expensive very fine-grained locking on attributes merely to guard against the fairly rare situation, in which
- a controlled type is chosen for a task attribute, and
- the Adjust or Finalize operation of the controlled type
calls on operations of this package in turn to read or modify task attributes.
Also, the case of a recursive access to the same attribute of the same task will deadlock anyway.
The use of attribute handles is not protected by any atomicity requirement in the RM, so that their concurrent use must be deemed erroneous.
!corrigendum C.7.2(13)
Insert after the paragraph:
For all the operations declared in this package, Tasking_Error is raised if the task identified by T is terminated. Program_Error is raised if the value of T is Null_Task_ID.
the new paragraph:
Bounded (Run-Time) Errors

If the package Ada.Task_Attributes is instantiated with a controlled type and the controlled type has user-defined Adjust or Finalize operations that in turn access task attributes by any of the above operations, then a call of Set_Value of the instantiated package constitutes a bounded error. The call may perform as expected or may result in forever blocking the calling task and subsequently some or all tasks of the partition.
!corrigendum C.7.2(15)
Insert after the paragraph:
If a value of Task_ID is passed as a parameter to any of the operations declared in this package and the corresponding task object no longer exists, the execution of the program is erroneous.
the new paragraph:
Accesses to task attributes via a value of type Attribute_Handle are erroneous if executed concurrently with each other or with calls of any of the operations declared in package Task_Attributes.
!corrigendum C.7.2(16)
Replace the paragraph:
The implementation shall perform each of the above operations for a given attribute of a given task atomically with respect to any other of the above operations for the same attribute of the same task.
by:
For a given attribute of a given task, the implementation shall perform the operations declared in this package atomically with respect to any of these operations of the same attribute of the same task. The granularity of any locking mechanism necessary to achieve such atomicity is implementation defined.
!ACATS test
This ruling is not testable. It says that some operations are erroneous; erroneous programs are never testable (as they can do anything). It defines other cases as bounded errors. The bounded error case allows deadlock, which makes it untestable as well.
!appendix

!section C.7.2(16)
!subject Recursive use of task attributes isn't considered
!reference RM95-C.7.2(16)
!from Dr. Michael F. Yoder 96-09-25
!keywords task,attribute
!reference 96-5705.a MFY  96-9-25>>
!discussion

Paragraph 16 of C.7.2 says, in full, "The implementation shall perform each
of the above operations for a given attribute of a given task atomically
with respect to any other of the above operations for the same attribute of
the same task."

Let me call an (attribute, task) pair a 'cell' for convenience.  The
atomicity requirement cannot be met if an operation on a cell recursively
invokes an operation on the same cell: an operation cannot be atomic with
respect another operation embedded within itself.  Presumably this must
be an error condition.  Perhaps it should be a bounded error with the
possible results being deadlock, raising Program_Error, or a recursive
action proceeding (it will become evident that some implementations of
Task_Attributes are likely to want to take this option).

Similarly, it seems evident that the intent was to allow cell-level
parallelism of the operations, but this opens up the possibility of
deadlock if an operation on cell C1 tries to recursively operate on C2
while a parallel operation on C2 tries to recursively operate on C1.
Presumably this too should be a bounded error (but in this case there
should be no question of a recursive action proceeding, the outcomes
should presumably be deadlock or Program_Error).

If recursion without these problems is deemed to be benign and legal, this
constrains implementers in at least the following way: that if they
implement their locking on a per-task or per-attribute basis rather than a
per-cell basis, they must then make these locks "recursive mutexes" so
that a task operating on one cell of a task won't deadlock if it tries to
recursively modify a different one.

Nevertheless, if implementations are allowed to use other than per-cell
locking, there are some patterns of recursion which are harmless in a
per-cell implementation which will deadlock in implementations which lock
cells by groups.  So to preserve portability, if recursion isn't simply
forbidden, it would be best to set rules for what can be assumed to be
legal.

There are four obvious possible styles of locking: a single global lock,
per-cell locking, per-task locking, and per-attribute locking.  With the
global lock, the deadlocks can't happen, so it won't be considered.  Any
deadlock with cell-level locking will also create a deadlock in an
implementation with per-task locking if the cells are from different tasks,
or with per-attribute locking if from different attributes (and one of
these two must obtain).

So one possibility would be to state that recursive use of the operations
is legal only if, roughly speaking, it doesn't deadlock on either a task or
an attribute basis.  This would in practical terms constrain implementors
to use one of the four styles mentioned, but that's probably not a major
consideration.

A more extreme option would be to forbid recursive use entirely.  Detecting
such use could be done at a cost of one bit per task.


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

!section C.7.2(16)
!subject Recursive use of task attributes isn't considered
!reference RM95-C.7.2(16)
!keywords task,attribute
!reference as 96-5705.a MFY  96-9-25
!from Ted Baker 96-09-26
!reference 96-5706.a Ted Baker  96-9-26>>
!discussion

| ...The atomicity requirement cannot be met if an operation on a cell
| recursively invokes an operation on the same cell...

I don't see how a user could arrange for these operations (VAlue,
Reference, Set_Value, Reinitialize) to invoke each other in any
recursive way, nor why an implementor would want to do so.

[By the way, we currently implement these with task-level locking,
which seems very natural and not too inefficient.]

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

!section 7.2(16)
!subject recursive use of task attributes
!reference C.7.2(16)
!from Dr. Michael F. Yoder
!keywords task,attribute
!reference 96-5708.a MFY  96-9-26>>
!discussion

This is to specify the "how" of recursive task attribute use.  I had thought
it was obvious, but apparently I was mistaken.

Recursive use of attributes can come about if the attribute is a controlled
type, or has components that are such, through the Initialize, Adjust, or
Finalize routines for the attribute type.  Since C.7.2(17) explicitly
mentions finalization of task attributes, it presumably wasn't intended to
forbid the use of attributes of controlled types.  So the question is
how to deal with the potential problems this creates.  (Recursive use can
come about even if there is just one attribute and one task.)

A simple example of how recursion might be useful is to imagine an
attribute which consisted of forward and back links in a ring of tasks.
It would be useful to have the finalization code for this attribute modify
the attributes of the near neighbors of the task whose attribute is being
finalized, with appropriate synchronization of course.

Useful intratask recursion seems less likely, but suppose you wish to cache
values of a difficult-to-compute function of existing attributes.  A simple
solution if available is to make the cached value (together with, say, a
bit indicating validity) a new attribute.  Now, the Adjust routines of the
existing attributes can invalidate the bit (requiring recursive use), and
the evaluation routine for the cached attribute must of course fetch the
other attribute values when the cached value isn't valid.

Uses for more scattered varieties of recursion are harder to contrive, but
one could imagine an attribute which was, say, the summed values of another
attribute over all child tasks.

However, I don't want to advocate programming along these lines, merely
point out that they are plausible uses of the facility.  My desire is to
clarify whether they are legal and, if not, what are the rules for legal
recursive use of attributes.

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

!section C.7.2(16)
!subject Recursive use of task attributes isn't considered
!reference RM95-C.7.2(16)
!from Erhard Ploedereder 96-9-26
!keywords task,attribute
!reference 96-5705.a MFY  96-9-25
!reference 96-5709.a Erhard Ploedereder  96-9-26>>
!discussion

Michael Yoder writes:
...
> Let me call an (attribute, task) pair a 'cell' for convenience.  The
> atomicity requirement cannot be met if an operation on a cell recursively
> invokes an operation on the same cell: an operation cannot be atomic with
> respect another operation embedded within itself.  Presumably this must
> be an error condition.  Perhaps it should be a bounded error with the
> possible results being deadlock, raising Program_Error, or a recursive
> action proceeding (it will become evident that some implementations of
> Task_Attributes are likely to want to take this option).
> Similarly, it seems evident that the intent was to allow cell-level
> parallelism of the operations, but this opens up the possibility of
> deadlock if an operation on cell C1 tries to recursively operate on C2
> while a parallel operation on C2 tries to recursively operate on C1.

I fail to see the problem, since the stated premise appears to be false (or,
at least, extremely unlikely):
The package Ada_Task_Attributes is predefined. Nowhere in its semantics is
there any indication of (and hence no need for) recursive operations, let
alone access to attributes of tasks other than the actual parameter task.
The provider of the predefined package will hopefully refrain from including
extraneous unnecessary attribute accesses in its implementation (along with
unnecessary potentially blocking calls, infinite loops, etc. etc.).

So, if an implementation were actually to deadlock on any operation declared
in this package or fail to function in any other fashion contrary to the
stated semantics, I would regard that implementation as plain wrong and in
violation of the standard.

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

!section C.7.2(16)
!subject Recursive use of task attributes isn't considered
!reference RM95-C.7.2(16)
!reference Dr. Michael F. Yoder 96-09-25
!keywords task,attribute
!reference 96-5705.a MFY  96-9-25
!from Offer Pazy 96-9-28
!reference 96-5710.a Offer Pazy  96-9-28>>
!discussion

> Paragraph 16 of C.7.2 says, in full, "The implementation shall perform eac
> of the above operations for a given attribute of a given task atomically
> with respect to any other of the above operations for the same attribute o
> the same task."
>
> Let me call an (attribute, task) pair a 'cell' for convenience.  The
> atomicity requirement cannot be met if an operation on a cell recursively
> invokes an operation on the same cell: an operation cannot be atomic with
> respect another operation embedded within itself.  Presumably this must
> be an error condition.  Perhaps it should be a bounded error with the
> possible results being deadlock, raising Program_Error, or a recursive
> action proceeding (it will become evident that some implementations of
> Task_Attributes are likely to want to take this option).

I am confused about this question. Could you please explain how recursion
can occur? The operations that you are refering too are those (and only
those) that are specified in the pre-defined package, they are not
user-defined. Why, and how would one operation on task T1 internally invoke
another operation on T1 (or t2 for that matter)? Are you worried about the
implementation (by the RTS) of these operations? i.e. that in order to
implement one operation the RTS must use one of the other operations
internally? I don't see why this would be needed or even be the prefered
implementation model. I don't see where and why this would be necessary. But
even if so, the implementation is free to use the per-task lock to avoid
deadlocks. But again, I don't see where such a problem would arise unless I
am missing something major.

Please clarify.

Offer Pazy
48 Be'eri St.
Tel-Aviv 64233
Israel
972-3-695-1923
pazy@world.std.com

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

!section C.7.2(16)
!subject Recursive use of task attributes isn't considered
!reference RM95-C.7.2(16)
!from Dr. Michael F. Yoder 96-09-25
!keywords task,attribute
!reference 96-5705.a MFY  96-9-25
!from Bob Duff
!reference 96-5715.a Robert A Duff 96-10-3>>
!discussion

Hi, Mike.

> Paragraph 16 of C.7.2 says, in full, "The implementation shall perform each
> of the above operations for a given attribute of a given task atomically
> with respect to any other of the above operations for the same attribute of
> the same task."
>
> Let me call an (attribute, task) pair a 'cell' for convenience.  The
> atomicity requirement cannot be met if an operation on a cell recursively
> invokes an operation on the same cell: an operation cannot be atomic with
> respect another operation embedded within itself. ...

I don't see how any operation in Ada.Task_Attributes can be recursive.
Am I missing the point of your comment?

- Bob

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

!section C.7.2(16)
!subject Recursive use of task attributes
!reference RM95-C.7.2(16)
!from Dr. Michael F. Yoder
!keywords task,attribute
!reference 96-5717.a MFY  96-10-3>>
!discussion

Here's a program (legal by the current rules, as far as I know) which
shows recursive use of Set_Value.  The program has only one
(library-level) attribute, and only the environment task.

with Ada.Finalization; use Ada.Finalization;
with Ada.Task_Attributes;
package An_Attr is
  type Attr is new Controlled with record
      N : Integer;
    end record;
  procedure Adjust(X : in out Attr);

  package Ops is new Ada.Task_Attributes(Attr,
        Initial_Value => (Controlled with 0));

end An_Attr;

with Ada.Text_IO; use Ada.Text_IO;
package body An_Attr is
  Depth : Natural := 0;

  procedure Adjust(X : in out Attr) is
  begin
    Put_Line((1..2*Depth => ' ') & "Adjust called");
    Depth := Depth + 1;
    if Depth <= 3 then
      Put_Line((1..2*Depth => ' ') & "calling Set_Value...");
      Ops.Set_Value((Controlled with Depth));
    end if;
  end Adjust;

end An_Attr;

with Ada.Finalization; use Ada.Finalization;
with An_Attr;
procedure A_Prog is
begin
  An_Attr.Ops.Set_Value((Controlled with 17)); -- One call
end A_Prog;

****************************************************************
!topic AI-165
!reference 1998-15845.a Erhard Ploedereder  1998-3-20
!from Michael Yoder 1998-04-15
!keywords task attribute,recursion
<<reference as: 1998-15853.a MFY  1998-4-15>>
!discussion

There is a minor error in this paragraph:

"If the attribute is of a controlled type or has components of a controlled
type, then the implicitly invoked user-defined Adjust or Finalize routines
are presently not forbidden to call on operations of this package for other
task attributes or even, rather pathologically, for the same task attribute
of the given task. Whatever locking strategy is applied, the latter will lead
to a deadlock. The former can lead to a deadlock if the granularity of the
lock is any larger than on single attributes of any task, e.g., a lock per
task or a global run-time lock."

There are no deadlocks when a single global lock is used in the former case above.  Perhaps
what was intended was "... or a lock per attribute."  Also, deadlocks are possible even
with maximally fine-grained locking, which makes the premise of the following paragraph
somewhat unclear:

"It seems unwise to require all implementations to provide a potentially
expensive very fine-grained locking on attributes merely to guard against
the fairly rare situation..."

This seems to suggest that fine-grained locking guards against deadlocks, but this is only
partly true: what makes deadlocks possible is allowing a lock granularity less than that of
a single global lock.  The implementation permission being considered is to allow some
deadlocks *in addition* to the ones that are present for cell-level locking, so as to
permit implementations to lock by groups.

This counterintuitive aspect of the situation comes from there being a special case: with a
single global lock, there cannot be a deadlock, barring circular use; in all other
situations, the finer the lock granularity the fewer the potential deadlocks.

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

!topic AI-165
!reference 1998-15845.a Erhard Ploedereder  1998-3-20
!keywords task attribute,recursion
!reference 1998-15853.a MFY  1998-4-15
!from Ted Baker 1998-04-16
<<reference as: 1998-15854.a Ted Baker  1998-4-16>>
!discussion

| There is a minor error in this paragraph:

| "If the attribute is of a controlled type or has components of a
| controlled type, then the implicitly invoked user-defined Adjust
| or Finalize routines are presently not forbidden to call on
| operations of this package for other task attributes or even,
| rather pathologically, for the same task attribute of the given
| task. Whatever locking strategy is applied, the latter will lead
| to a deadlock. The former can lead to a deadlock if the
| granularity of the lock is any larger than on single attributes of
| any task, e.g., a lock per task or a global run-time lock."

| There are no deadlocks when a single global lock is used in the
| former case above.

The above sentence does not make sense to me.  As I read it, it is
saying that if there is a single global run-time lock, there would
be no deadlock if a task that is holding that lock tries to lock
the same lock.  I suppose you are assuming that if there is a
single global lock for the whole runtime system, the problem of
avoiding eadlock on that lock will necessarily already have been
solved by some other means?

| Perhaps what was intended was "... or a lock
| per attribute."  Also, deadlocks are possible even with maximally
| fine-grained locking, which makes the premise of the following
| paragraph somewhat unclear:

| "It seems unwise to require all implementations to provide a
| potentially expensive very fine-grained locking on attributes
| merely to guard against the fairly rare situation..."

| This seems to suggest that fine-grained locking guards against
| deadlocks, but this is only partly true: what makes deadlocks
| possible is allowing a lock granularity less than that of a single
| global lock.  The implementation permission being considered is to
| allow some deadlocks *in addition* to the ones that are present
| for cell-level locking, so as to permit implementations to lock by
| groups.

| This counterintuitive aspect of the situation comes from there
| being a special case: with a single global lock, there cannot be a
| deadlock, barring circular use; in all other situations, the finer
            ^^^^^^^^^^^^^^^^^^^^
            RTS "recursion" via finalizers and attributes leads to such
            circularity.

| the lock granularity the fewer the potential deadlocks.

--Ted

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

!topic AI-165
!reference 1998-15845.a Erhard Ploedereder  1998-3-20
!keywords task attribute,recursion
!reference 1998-15853.a MFY  1998-4-15
!from Ted Baker 1998-04-16
<<reference as: 1998-15855.a MFY  1998-4-16>>
!discussion

MY: "There is a minor error in this paragraph:

 'If the attribute is of a controlled type or has components of a
 controlled type, then the implicitly invoked user-defined Adjust
 or Finalize routines are presently not forbidden to call on
 operations of this package for other task attributes or even,
 rather pathologically, for the same task attribute of the given
 task. Whatever locking strategy is applied, the latter will lead
 to a deadlock. The former can lead to a deadlock if the
 granularity of the lock is any larger than on single attributes of
 any task, e.g., a lock per task or a global run-time lock.'

 There are no deadlocks when a single global lock is used in the
 former case above."

TB: "The above sentence does not make sense to me.  As I read it, it is
saying that if there is a single global run-time lock, there would
be no deadlock if a task that is holding that lock tries to lock
the same lock.  I suppose you are assuming that if there is a
single global lock for the whole runtime system, the problem of
avoiding [d]eadlock on that lock will necessarily already have been
solved by some other means?"

Sorry, I now realize I was making an implicit assumption.  I was assuming
that an implementation that used one global lock would choose to make it a
recursive mutex.  This isn't a warranted assumption in the context of
the discussion, so I'm willing to simply withdraw the comment.

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




Questions? Ask the ACAA Technical Agent