CVS difference for ai05s/ai05-0111-3.txt
--- ai05s/ai05-0111-3.txt 2010/11/18 07:07:35 1.6
+++ ai05s/ai05-0111-3.txt 2011/01/15 07:51:41 1.7
@@ -1,4 +1,4 @@
-!standard 4.8(2) 10-11-15 AI05-0111-3/05
+!standard 4.8(2) 11-01-15 AI05-0111-3/06
!standard 4.8(3/2)
!standard 4.8(10.3/2)
!standard 13.11(16/3)
@@ -243,8 +243,10 @@
has no effect. Otherwise, a call on Unchecked_Deallocate_Subpool has
the following effects:
-* Any tasks allocated from the subpool desigated by Subpool that are
- waiting at an open terminate alternative are completed (see 9.2);
+* Any task allocated from the subpool designated by Subpool that is
+ waiting at an open terminate alternative and having all of its subtasks
+ (if any) either completed or similarly waiting at an open terminate
+ alternative, is completed;
* Next, the call waits for any completed tasks allocated from that subpool
(including ones completed by the previous bullet) to complete their
@@ -259,10 +261,10 @@
* Finally, Subpool is set to null.
-It is a bounded error if tasks that are neither completed nor waiting at
-a terminate alternative were allocated from the
-subpool being deallocated. The possible effects are as given for the
-unchecked deallocation of an object with a task part (see 13.11.2).
+It is a bounded error if there are any tasks allocated from the subpool
+that are not terminated when the call to Deallocate_Subpool is made. The
+possible effects are as given for the unchecked deallocation of an object with a
+task part (see 13.11.2).
Example
@@ -519,7 +521,7 @@
exist, for instance because it was destroyed by a call to an instance of
Unchecked_Deallocation. We don't need special rules to handle these cases,
as a subpool handle is a normal Ada access type, and the implementation
-of the pool is written by the programmer in Ada. Thus the existing rules
+of the pool is written by some programmer in Ada. Thus the existing rules
for access types cover all needed rules.
However, those rules just mean that execution may become erroneous. To help
@@ -537,12 +539,48 @@
pool in the right place).
+TASK TERMINATION MODEL
+
+The basic model of task termination is unaltered; the tasks allocated from a
+subpool belong to the master of the access type. This works because of the
+accessibility check on the pool object - the pool object has to be in the same
+scope as the access type. Moreover, all tasks for a given scope terminate
+together, so it isn't possible to differentiate between them "belonging" to
+the pool object or the access type.
+
+Unchecked_Deallocation has no effect on task termination. This means that
+server tasks embedded in a deallocated object may continue to wait at terminate
+alternatives, even though they are no longer accessible. It is felt that it is
+not a hardship for the client to call a 'shutdown' routine before deallocating
+them (although such a requirement damages encapsulation).
+
+However, this model does not work for subpools. In order to call a shutdown
+entry on each object, it would be necessary to enumerate all of the contained
+objects (or at least those that need a shutdown routine called). That would
+defeat the purpose of subpools (which is to support a mass deallocation of all
+of the related objects without having to enumerate them).
+
+Therefore, we adopt rules that have tasks allocated from a subpool that are
+waiting at a terminate alternative (with the same requirements as 9.3(3-6))
+become completed, and then the finalization of all completed tasks is waited
+for. This means that it is safe to deallocate a subpool containing tasks
+-- even if those tasks have discriminants -- so long as the tasks are completed.
+For other tasks, this is a bounded error as it is for Unchecked_Deallocation.
+
+We considered adopting this rule for Unchecked_Deallocation as well, as it
+would reduce the cases of bounded errors and the associated bugs. Unfortunately,
+it could be inconsistent with the behavior of Ada 95 and Ada 2005 programs,
+as the finalization could take a long time or even block. In extreme cases,
+deadlock is possible. That seems like too much of an inconsistency to allow,
+so we do not change the behavior of Unchecked_Deallocation.
+
+
FINALIZATION MODEL
The model used here is that subpools are really part of the pool object;
-they are finalized when the pool is finalized. The objects may be created
-directly as part of the pool object, or may be separately allocated and
-managed by the pool.
+they are finalized when the pool is finalized. The subpool objects may be
+created directly as part of the pool object, or may be separately allocated
+and managed by the pool.
Objects allocated into a subpool will be finalized when the subpool is
explicitly deallocated. If that never happens, the objects can be finalized
@@ -558,41 +596,41 @@
Alternatives
-This accessibility check does put restrictions on the location of access types that
-use subpools. We considered doing without the check by adding an additional runtime
-rule that the finalization of a collection for an access type also finalizes any
-objects allocated from a subpool for that access type. (Along with a similar rule
-for task dependence.)
+This accessibility check does put restrictions on the location of access types
+that use subpools. We considered doing without the check by adding an additional
+runtime rule that the finalization of a collection for an access type also
+finalizes any objects allocated from a subpool for that access type. (Along with
+a similar rule for task dependence.)
This eliminates the static restrictions and would allow subpools to be used
on access types with nested designated types and the like.
However, the implementation would be complex. An obvious implementation would
-put subpool allocated objects on both a chain for the collection and a chain
-for the subpool (removing it from both when it is finalized). However, this
-would appear to have a distributed space overhead, as there would need to be
-links to put an object on two lists for any controlled type that could be allocated
-(which would seem to be any such type), as well as a small distributed time overhead
-to initialize the second set of pointers and to remove the object from the second
-list when it is finalized.
-
-However, it is possible to do better (with some complexity). If the subpool keeps
-a separate finalization list for each access type, then only the subpool need
-be put on the access type's collection list. This would complicate finalization
-somewhat, but only when subpools are used. This would require some unique way
-to identify the access type to the subpool; this could be done by assigning at
-elaboration time a unique serial number to each access type that uses a storage pool
-that supports subpools.
-
-Similar implementation complexity would also apply to task dependence. Because of
-this complexity, we chose the simpler model.
-
-The other alternative would be to decouple subpools from the underlying pool. The
-subpool could be required to have a shorter lifetime than the access type (or the
-designated type), which eliminates the finalization problem. However, it makes
-dangling subpool handles much more likely. That could be solved with reference
-counting -- but of course that brings us back to the more complex proposal of
-AI05-0111-2. So this option was rejected.
+put subpool allocated objects on both a chain for the collection and a chain for
+the subpool (removing it from both when it is finalized). However, this would
+appear to have a distributed space overhead, as there would need to be links to
+put an object on two lists for any controlled type that could be allocated
+(which would seem to be any such type), as well as a small distributed time
+overhead to initialize the second set of pointers and to remove the object from
+the second list when it is finalized.
+
+However, it is possible to do better (with some complexity). If the subpool
+keeps a separate finalization list for each access type, then only the subpool
+need be put on the access type's collection list. This would complicate
+finalization somewhat, but only when subpools are used. This would require some
+unique way to identify the access type to the subpool; this could be done by
+assigning at elaboration time a unique serial number to each access type that
+uses a storage pool that supports subpools.
+
+Similar implementation complexity would also apply to task dependence. Because
+of this complexity, we chose the simpler model.
+
+The other alternative would be to decouple subpools from the underlying pool.
+The subpool could be required to have a shorter lifetime than the access type
+(or the designated type), which eliminates the finalization problem. However, it
+makes dangling subpool handles much more likely. That could be solved with
+reference counting -- but of course that brings us back to the more complex
+proposal of AI05-0111-2. So this option was rejected.
USE AS A BUILDING BLOCK
@@ -876,5 +914,285 @@
The "likeliness" issue is merely based on the vagaries of reusing storage, etc.,
and as Randy points out, is in (partial) control of the subpool implementor, not
the Ada implementor.
+
+****************************************************************
+
+Following a a summary of a private conversation in November 2010 about the
+termination semantics of subpool deallocation.
+
+Randy Brukardt:
+
+Let me remind you where we are.
+
+The big change to the AI that we decided on was to drop all of the master stuff
+from the AI.
+
+(The following discussion will ignore Unchecked_Deallocate_Subpool; I'll get to
+that in a moment...)
+
+This works because all of the tasks and controlled objects allocated for an
+access type will "belong" to the master of the scope in which the access type is
+declared. Because of the accessibility check on a storage pool, this is the same
+master as that of the storage pool. Therefore, any tasks and controlled objects
+allocated from subpools will "belong" to the same master whether they are
+implemented as belonging to the subpool object or whether they are implemented
+as belonging to the access type.
+
+For tasks, the ordering of the elaboration of the entities is irrelevant; all
+tasks "belonging" to a master are awaited at once. So we need do nothing special
+for this case.
+
+For controlled objects, they are finalized in the reverse order of their
+elaboration. The collections of the access types are deemed to have elaborated
+at the freezing point of the type. The storage pool object is finalized at the
+point of its elaboration (which necessarily must be before the freezing point of
+the access type; therefore it must finalize later). As noted previously, these
+both have to be as part of the same master.
+
+In order to allow the controlled objects to finalize with the storage pool
+rather than the access type's collection, we add the following Implementation
+Permission (added after 7.61(20)):
+
+The implementation may finalize objects created by allocators for an access type
+whose storage pool supports subpools (see 13.11.4) as if the objects were
+created (in an arbitrary object) at the point where the storage pool was
+elaborated rather instead of the first freezing point of the access type.
+
+AARM Ramification: This allows the finalization of such objects to occur later
+than they otherwise would, but still as part of the finalization of the same
+master.
+
+AARM Implementation Note: This permission is intended to allow the allocated
+objects to "belong" to the subpool objects and to allow those objects to be
+finalized at the time that the storage pool is finalized (if they are not
+finalized earlier).
+
+==============
+
+The above is the easy part. The other issue is any special termination semantics
+for tasks in for Unchecked_Deallocate_Subpool. Let me start with some Bairdian
+free association.
+
+(1) Steve was worried about nested tasks of a task that is waiting on a
+ terminate alternative. These are not a (language) problem (or no more so
+ than they are in other Ada code). The selection of a terminate alternative
+ makes a task immediately completed (NOT terminated). After the task is
+ completed (whether by the selection of a terminate alternative or simply by
+ reaching the end of the code), task waiting and other finalizations proceeds
+ normally.
+
+(2) Because tasks that are waiting on a terminate alternative have to wait on
+ tasks and finalize, they can take arbitrarily long to actually terminate. Of
+ course, this is under control of the user; they don't have to write nested
+ tasks and finalization that blocks. ;-)
+
+(3) It seems to me that if we are going to do something special for
+ Unchecked_Deallocate_Subpool, we ought to consider doing the same for
+ Unchecked_Deallocation. After all, these are essentially the same. Moreover,
+ in both cases, access to the tasks from outside of themselves is erroneous
+ (it has to be accomplished through a dangling pointer), so there can be no
+ correct code that depends on such tasks continuing to wait and/or run.
+
+(4) A task that is completed is essentially in the same state as one waiting on
+ a terminate alternative (in that both have to complete finalization before
+ terminating), other than the former is not waiting. Depending on the purpose
+ of the rule, we may want to include completed tasks in it. Specifically, if
+ the purpose is to allow implementations to free task memory sooner, then the
+ same rule ought to be applied to both. (I admit I don't know what the
+ purpose of this rule is, other than to make allocated tasks work more like
+ you would expect.)
+
+(5) I wonder if we need some sort of bounded error for all non-terminated tasks
+ in subpools. That's because in the case of subpools, there is no way to
+ suppress the deallocation of memory (doing it for the entire subpool would
+ prevent the memory from getting freed until the pool goes away -- uggh). Or
+ are we requiring that tasks are allocated independently of any other
+ allocated memory? That seems limiting (especially as it means that tasks
+ never get freed at all -- at least not until their master goes away). I
+ recall a number of "bug" reports on this for Janus/Ada 83; I had to explain
+ to people that the tasks continue to exist until the master goes away, and
+ on 640K MS-DOS, you could run out of space for TCB's in a hurry. One hopes
+ that we are not continuing that mistake...
+
+OK, enough free association. Here's the latest version of the rule that Tucker
+has proposed; this would appear in the Unchecked_Deallocate_Subpool text (I've
+left the original Tucker text as alone as possible):
+
+Otherwise, a call on Unchecked_Deallocate_Subpool causes following actions on
+the subpool designated by Subpool:
+
+* Any tasks allocated from the subpool that are waiting at an open terminate
+ alternative are completed, then waiting for their termination;
+
+* Then any of the objects allocated from the subpool that still exist are
+ finalized in an arbitrary order;
+
+* Finally, Subpool is set to null.
+
+The first thing that strikes me about this rule is that it waits for the
+termination (read finalization) of any tasks with open terminate alternatives.
+But it *doesn't* wait for any tasks that are already completed but have not yet
+finished their finalization. I don't see any good reason for the difference.
+Either not waiting for finalization is harmless, in which case neither ought to
+do that; or it *does* eliminate problems, in which case both ought to do it. I
+don't see any justification for a difference. Thus I suggest replacing the above
+by:
+
+Otherwise, a call on Unchecked_Deallocate_Subpool causes following actions on
+the subpool designated by Subpool:
+
+* Any tasks allocated from the subpool that are waiting at an open terminate
+ alternative are completed;
+
+* Next, the call waits for any completed tasks (including ones completed by the
+ previous bullet) to complete their finalization;
+
+* Then any of the objects allocated from the subpool that still exist are
+ finalized in an arbitrary order;
+
+* Finally, Subpool is set to null.
+
+(If we decide to never wait, the second bullet can just be deleted.) I think I'm
+in favor of waiting, because it definitely would reduce the bounded error
+possibilities (the bounded error occurs when a nonterminated task with
+discriminants is deallocated), and would allow the task storage to be freed in
+more cases.
+
+The question of whether to change the rules for Unchecked_Deallocation also come
+up here. Waiting definitely would be an execution inconsistency (although almost
+exclusively in terms of time). Making server tasks complete would also be
+inconsistent, but only to the extent that the task's finalization does something
+"interesting"; the interesting thing would happen earlier than it does now.
+
+Either way, the main advantage to this rule would be to allow allocated server
+tasks to shut down once they no longer can be accessed. That seems to be an
+important thing to allow no matter how the tasks are deallocated. Waiting for
+them to finalize is secondary and seems less important.
+
+One could argue that for Unchecked_Deallocation, it would be easy enough to wait
+for a task to terminate before freeing it (just write a loop on termination),
+and it also would be easy enough to add a shutdown entry to call before
+deallocating an object containing a task. That seems true, but it also seems to
+mess up designs.
+
+Also note that using the same semantics for both would make it easier to convert
+from single deallocations to the use of a subpool or vice versa (much less
+likely for there to be trouble).
+
+Finally, it is clear that not having any termination semantics for subpools
+would make it hard to deallocate memory. We seem to need something.
+
+Summarizing the questions:
+
+(1) What is the purpose of special rules for task termination?
+
+(2) Do the special rules apply to both Unchecked_Deallocation and
+ Unchecked_Deallocate_Subpool, or just the latter?
+
+(3) Do the special rules apply to completed but not yet terminated tasks? To
+ tasks waiting on a terminate alternative? To already terminated tasks?
+
+(4) Do the special rules involve waiting for the completion of the finalization
+ of the tasks (that is, the termination of the tasks)?
+
+---
+
+Tucker Taft:
+
+One of the original goals was to support a mark/release approach to memory
+management that properly handled finalization. Clearly task waiting is tied up
+with finalization, so I am reluctant to ignore the problem just because
+Unchecked_Deallocation did so. With Unchecked_Deallocation, you are freeing just
+one object, so it is feasible to do some amount of checking of the state, etc.,
+if there might be an embedded task involved. When freeing a whole subpool, that
+isn't very practical.
+
+So I don't feel a strong need to make these two kinds of deallocation consistent
+as far as task waiting.
+
+Another thing to mention is that the rules in 9.3(6-9) require that the tasks
+not only be waiting at a terminate alternative, but that they be dependent on a
+completed master all of whose dependents are either terminated or waiting on a
+terminate alternative. That means there can't be any subtasks that will need to
+be awaited -- all that remains is finalization for the tasks waiting at
+terminate alternatives.
+
+So I think I would suggest we try to match the requirements of 9.3(6-9) in
+AI05-0111-3. Here are the current bullets from 111:
+
+ * Any tasks allocated from the subpool desigated by Subpool that are
+ waiting at an open terminate alternative are completed (see 9.2);
+
+ * Next, the call waits for any completed tasks allocated from that subpool
+ (including ones completed by the previous bullet) to complete their
+ finalization;
+
+ * Then any of the objects allocated from the subpool that still exist
+ are finalized in an arbitrary order;
+
+I would suggest the following:
+
+ * Any task allocated from the subpool designated by Subpool that is
+ waiting at an open terminate alternative and having all of its subtasks
+ (if any) either completed or similarly waiting at an open terminate
+ alternative, is completed;
+
+ * Next, the call waits for any completed tasks allocated from that subpool
+ (including ones completed by the previous bullet) to complete their
+ finalization;
+
+ * Then any of the objects allocated from the subpool that still exist
+ are finalized in an arbitrary order;
+
+ It is a bounded error if there are any tasks allocated from the subpool
+ that are not terminated at this point (with the same bounds as
+ for Unchecked_Deallocation).
+
+This is actually pretty consistent with Unchecked_Deallocation, in that it only
+waits for finalization to complete. It doesn't wait for a task to complete that
+isn't already "ready" to complete. In practice, presumably you would throw in a
+"delay 1.0" or something before doing an Unchecked_Deallocate_Subpool if there
+were tasks involved, to give them a chance to reach their terminate
+alternatives. The nice thing is it allows terminate alternatives to "work" for
+such tasks, which Unchecked_Deallocation doesn't allow. But again, with
+individual Unchecked_Deallocation, you could pretty easily call some "Shut_Down"
+entry of the task before deallocating it.
+
+---
+
+Randy Brukardt:
+
+> One of the original goals was to support a mark/release approach to
+> memory management that properly handled finalization. Clearly task
+> waiting is tied up with finalization, so I am reluctant to ignore the
+> problem just because Unchecked_Deallocation did so.
+> With Unchecked_Deallocation, you are freeing just one object, so it is
+> feasible to do some amount of checking of the state, etc., if there
+> might be an embedded task involved. When freeing a whole subpool,
+> that isn't very practical.
+
+Right, although if your have properly encapsulated types, it isn't very feasible
+in either case (you'd have to export a "Before_UD_Call_This" operation, which is
+nasty to an abstraction and doesn't work well when used as a component).
+
+> So I don't feel a strong need to make these two kinds of deallocation
+> consistent as far as task waiting.
+
+I did think about that, but I came to the opposite conclusion. For me, the
+current rules for Unchecked_Deallocation are not very good, and the only reason
+for *not* fixing it is to avoid runtime inconsistency.
+
+However, waiting for termination means waiting for finalization, and that
+can block. (Note that finalization that blocks is not that unusual; finalization
+of some Claw objects need to seize an exclusion lock, which can take a long time
+if the program is incorrectly structured [Claw does have deadlock-breaking
+timeouts on many entry calls, but those raise exceptions and only serve to
+highlight a problem.])
+
+That means that we probably can't apply the rules to Unchecked_Deallocation
+(simply because there is a chance of deadlock, as might happen in Claw, and that
+is too much inconsistency to stomach). I don't buy your rationalization for not
+fixing Unchecked_Deallocation, but the inconsistency with Ada 95 and 2005 is a
+sufficient reason.
****************************************************************
Questions? Ask the ACAA Technical Agent