!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) @dinsa 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. @dinst @i<@s8>@hr 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) @dinsa 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. @dinst 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) @drepl 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. @dby 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 <> !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 <> !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 <> !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. ****************************************************************