Version 1.12 of ais/ai-00280.txt

Unformatted version of ais/ai-00280.txt version 1.12
Other versions for file ais/ai-00280.txt

!standard 9.04 (20)          05-12-05 AI95-00280/08
!standard 4.08 (11)
!standard 7.06.01 (11)
!standard 11.05 (20)
!standard 11.05 (21)
!class binding interpretation 01-12-21
!status Amendment 200Y 04-07-02
!status WG9 approved 04-11-18
!status ARG Approved 8-0-0 04-06-17
!status work item 01-12-21
!status received 01-12-04
!qualifier Omission
!priority High
!difficulty Medium
!subject Allocation, deallocation, and use of objects after finalization
!summary
Calling an entry or subprogram of a protected object after the object is finalized is a bounded error, either raising Program_Error or working normally.
Evaluating an allocator for an access type whose designated type has a task part after the master has completed waiting for dependent tasks raises Program_Error.
When evaluating an allocator after the finalization of the collection for an access type has begun:
If the designated type has a controlled or protected part, Program_Error is raised. Otherwise, a bounded error occurs, either raising Program_Error
or working normally.
!question
What is the effect of calling an entry or subprogram of a protected object after the object is finalized?
What is the effect of evaluating an allocator after the access type's collection of objects has been finalized (by the rule in 7.6.1(11))?
What is the effect of calling an instance of Unchecked_Deallocation after the access type's collection of objects has been finalized (by the rule in 7.6.1(11))?
What is the effect of evaluating an allocator for an access type whose designated type has a task part after the master of the access type has completed waiting for dependent tasks?
!recommendation
(See summary.)
!wording
(See corrigendum.)
!discussion
All Ada objects may be accessed after they have been finalized, as the object continues to exist until the master is left. In general, it is the programmer's responsibility to insure that this does not cause problems (for instance, by including a not_valid bit in the type).
For protected types, however, it is the language requirements of mutual exclusion and queuing that may cause problems. A programmer cannot insure that these do not cause problems.
Since an implementation should be able to return locks or other resources to the underlying operating system when the object is finalized, we do not want to require that calls after finalization work normally. We also do not want to mandate the overhead of checks for a relatively rare case. Thus, we declare this case to be a bounded error.
If an implementation allows calls to proceed normally, it is possible that a task may be queued on the object forever.
There are analogous problems with access types.
The finalization associated with a non-derived access type is described in 7.6.1(11).
This "collection finalization" consists of iterating over the set of allocated objects and finalizing them in some order.
The RM states that each allocated object "that still exists" at the point of collection finalization is finalized. This says nothing about objects which are allocated after the collection finalization is finished, and it seems to imply that allocations that occur after the collection finalization has started are not included, either.
Note that "still exists" does not imply a fixed, unchanging set of objects. If an object in the set ceases to exist (because of a call to an instance of Unchecked_Deallocation), obviously it is not finalized by collection finalization. Any other interpretation would be nonsense, as the object does not exist. If an already finalized object is deallocated, Finalize is called again (as specified in 13.11.2(9)). This does not cause a problem, as correct Finalize implementations need to be prepared to be called "extra" times (see AARM 7.6.1(24-24.b) for the reasons).
There are also problems with tasks which are allocated after the master of the access type has completed the first step of its finalization, waiting for the termination of any tasks dependent on the master (9.3(5)).
To demonstrate that these scenarios are possible, consider the following example:
with Ada.Finalization; with Ada.Unchecked_Deallocation; package P is type T1 is new Ada.Finalization.Controlled with null record; procedure Finalize (X : in out T1);
type T2 is new Ada.Finalization.Controlled with null record; procedure Finalize (X : in out T2);
task type Tsk; type Tsk_Ref is access Tsk;
X1 : T1;
type T2_Ref is access T2;
procedure Free is new Ada.Unchecked_Deallocation (T2, T2_Ref); end P;
Assuming that P.T2_Ref's finalization is non-null (i.e. that the set of allocated objects to be iterated over is non-empty), P.T2's Finalize procedure will be invoked during P.T2_Ref's collection finalization.
P.T1's finalize procedure will be invoked after P.T2_Ref's collection finalization is complete (because P.X1 is declared before P.T2_Ref).
Either of these two procedures might contain allocators of type P.T2_Ref or P.Tsk_Ref, or calls to P.Free.
As the RM is currently defined, there could exist objects which never would be finalized by the program. This would break the invariant that every object in Ada is finalized at some point. Breaking this invariant would make it impossible to make bullet-proof abstractions, and such a result cannot be tolerated.
To fix this problem, we must mandate checks. Where and when should these checks be inserted?
Deallocations need to be allowed at least until the end of the collection finalization. Finalizing one member of the set may cause the deallocation of another member. Consider, for instance, a window system where child windows are destroyed when the parent is. Since windows are finalized in an arbitrary order, if the parent is finalized first, it will destroy and deallocate the child. We certainly do not want to outlaw such program designs. A deallocation after the collection finalization is only possible if we allow an allocation at that point; thus we do not have to handle it specially. Therefore, no check is necessary for deallocations.
On the other hand, allocating an object from the collection after it has started collection finalization seems to be a bug. The items are being destroyed, not created. In addition, if we do not allow allocation once the collection finalization begins, we avoid having to define when it gets finalized. Moreover, it is easier to design correct behavior of a collection if allocations are not allowed during collection finalization.
Thus, we define a check to occur on allocation - Program_Error is raised if an allocation occurs after collection finalization has started. However, this check is a distributed overhead on allocations, and provides no benefit for types with a trivial finalization. Thus, we require this check only for access objects that have a non-trivial finalization. For other objects, this case is declared to be a bounded error, allowing implementations to make the check if they wish, or ignore the problem (as there is no ill effect). This minimizes the overhead.
Since we only require the check when the object has non-trivial finalization, it is possible for objects (with trivial finalization) to be allocated for a collection which has other objects with non-trivial finalization. This can happen for an access to a class-wide type, where some extensions have non-trivial finalization. If allowing the allocation of such objects is a problem for an implementation, the implementation can always detect the bounded error (that is, make the check) for all allocators for that collection.
Similarly, an allocation of a task for a master which has completed waiting for dependent tasks raises Program_Error. Otherwise, the task would never be waited for.
!corrigendum 04.08(11)
Replace the paragraph:
If the created object contains any tasks, they are activated (see 9.2). Finally, an access value that designates the created object is returned.
by:
If the object to be created by an allocator has a controlled or protected part, and the finalization of the collection of the type of the allocator (see 7.6.1) has started, Program_Error is raised.
If the object to be created by an allocator contains any tasks, and the master of the type of the allocator is completed, and all of the dependent tasks of the master are terminated (see 9.3), then Program_Error is raised.
If the created object contains any tasks, they are activated (see 9.2). Finally, an access value that designates the created object is returned.
Bounded (Run-Time) Errors
It is a bounded error if the finalization of the collection of the type (see 7.6.1) of the allocator has started. If the error is detected, Program_Error is raised. Otherwise, the allocation proceeds normally.
!corrigendum 07.06.01(11)
Replace the paragraph:
The order in which the finalization of a master performs finalization of objects is as follows: Objects created by declarations in the master are finalized in the reverse order of their creation. For objects that were created by allocators for an access type whose ultimate ancestor is declared in the master, this rule is applied as though each such object that still exists had been created in an arbitrary order at the first freezing point (see 13.14) of the ultimate ancestor type.
by:
The order in which the finalization of a master performs finalization of objects is as follows: Objects created by declarations in the master are finalized in the reverse order of their creation. For objects that were created by allocators for an access type whose ultimate ancestor is declared in the master, this rule is applied as though each such object that still exists had been created in an arbitrary order at the first freezing point (see 13.14) of the ultimate ancestor type; the finalization of these objects is called the finalization of the collection. After the finalization of a master is complete, the objects finalized as part of its finalization cease to exist, as do any types and subtypes defined and created within the master.
!corrigendum 09.04(20)
Insert after the paragraph:
As the first step of the finalization of a protected object, each call remaining on any entry queue of the object is removed from its queue and Program_Error is raised at the place of the corresponding entry_call_statement.
the new paragraph:
Bounded (Run-Time) Errors
It is a bounded error to call an entry or subprogram of a protected object after that object is finalized. If the error is detected, Program_Error is raised. Otherwise, the call proceeds normally, which may leave a task queued forever.
!corrigendum 11.05(20)
Insert before the paragraph:
Elaboration_Check
When a subprogram or protected entry is called, a task activation is accomplished, or a generic instantiation is elaborated, check that the body of the corresponding unit has already been elaborated.
the new paragraphs:
Accessibility_Check
Check the accessibility level of an entity or view.
Allocation_Check
For an allocator, check that the master of any tasks to be created by the allocator is not yet completed or some dependents have not yet terminated, and that the finalization of the collection has not started.
!corrigendum 11.05(21)
!comment This item is out of order, thus it has been moved.
@ddel @xhang<@xterm<Accessibility_Check> Check the accessibility level of an entity or view.>
!ACATS test
Create a C-Test to check that either Program_Error is raised or that the calls proceed normally for protected objects. (We check this to insure that this case does not cause erroneous behavior.)
Create a C-Test to check that Program_Error is raised if an allocator is evaluated after the finalization of the collection has started, and the object has a controlled or protected part. (We check this to insure that the implementation does not leave unfinalized objects around).
!appendix

!topic Calls to finalized protected objects
!reference RM95-9.4(20)
!from Gary Dismukes 01-12-04
!discussion

We recently had a semantic issue arise with two separate customers
having to do with what happens when an already-finalized protected
object is referenced as part of the finalization of another object.

The question comes down to the following: what is the effect of calling
an entry of a protected object after the object has been finalized?
This can occur when one controlled object has an access component
designating a protected object and the protected object is finalized
before the controlled object.

The finalization of protected objects includes the normal semantics
of finalization of its protected components, plus the additional
actions defined in paragraph 9.4(20), which states:

20   As the first step of the finalization of a protected object, each call
remaining on any entry queue of the object is removed from its queue and
Program_Error is raised at the place of the corresponding entry_call_statement.

Note that this is similar to the treatment given to queued callers of
a task entry when the task completes (raising Tasking_Error).  However,
in the case of tasks, an exception is also raised when attempting to call
a completed task.

The rule of 9.4(20) only deals with entry calls that are currently suspended
on a protected entry when the associated object is finalized, and it doesn't
address the case of calls to the protected object that occur after the object
is finalized.  It seems to us that such calls should also be considered in
error (e.g., the implementation may have performed certain clean-up actions
as a part of finalizing the object that would make later calls problematic).
What are the intended semantics of such an entry call?  Is it really required
to support post-finalization calls with normal call semantics, or is this an
oversight in the RM and the call should raise Program_Error?

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

!topic Calls to finalized protected objects
!reference RM95-9.4(20)
!reference Gary Dismukes 01-12-04
!from Ted Baker 01-12-05
!discussion

| ... what is the effect of calling an entry of a protected object
| after the object has been finalized? ...
| ... It seems to us that such calls should also be considered in
| error (e.g., the implementation may have performed certain clean-up actions
| as a part of finalizing the object that would make later calls problematic).
| What are the intended semantics of such an entry call?  Is it really required
| to support post-finalization calls with normal call semantics, or is this an
| oversight in the RM and the call should raise Program_Error?

I believe this was an oversight.  Perhaps we thought that other semantic
restrictions would make it impossible for a call to a protected entry to
occur after finalization.

An intent of protected object finalization is to clean up dangling
references both to and from the object.  That intent would not be
served if an implementation were to permit further calls to be
queued on the object.

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

From: Robert Dewar
Date: Thursday, December 6, 2001  1:29 AM

I agree with Ted's assessment.

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

From: Tucker Taft
Date: Wednesday, December 5, 2001  9:17 AM

I would agree that all subsequent calls are bounded errors, and
program_error is the best possible response.  On the other hand,
I would be reluctant to have implementors go out of their way
to raise Program_Error.  I don't think it should be erroneous,
unless the object no longer "exists" from the language point of
view.

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

From: Robert Dewar
Date: Thursday, December 6, 2001  1:29 AM

What are other non-best possibilities for the bounded error?

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

From: Steve Baird
Date: Wednesday, December 5, 2001  3:12 PM

Isn't there a similar problem with allocating an object after the
"collection" has been finalized (i.e. after the finalization of allocated
objects that is associated with the first freezing point of the ultimate
ancestor access type has been performed)?

One way that this can occur is if the finalization routine for one
type, T1, allocates an object of another type, T2. If the declaration
of some object, X1, of type T1 precedes the declaration of the
non-derived access type of the allocator, then X1's finalization will
take place after the finalization of the access type's "collection"
of allocated objects.

It appears that the resulting allocated object is never finalized.

An allocator which is evaluated *during* collection finalization may
also be problematic.

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

From: Gary Dismukes
Date: Wednesday, December 5, 2001  3:28 PM

I agree.  These are additional gaps in the finalization semantics.
It seems that an attempt to do any such allocation should also be
defined as a bounded error.

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

From: Cyrille Comar
Date: Thursday, December 6, 2001  3:57 AM

Tucker Taft writes:
 > I would agree that all subsequent calls are bounded errors, and
 > program_error is the best possible response.

I also agree.

 > On the other hand, I would be reluctant to have implementors go out
 > of their way to raise Program_Error.  I don't think it should be
 > erroneous, unless the object no longer "exists" from the language
 > point of view.

But if Program_Error is not guaranteed to be raised, is it still a
bounded error? if it is not erroneous, what would be the status?

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

From: Tucker Taft
Date: Thursday, December 6, 2001  3:19 PM

A bounded error may always raise program_error, but it need not.
The RM needs to specify in the case of a bounded error what
are the allowed results.  In this case, I would permit a call
on a finalized protected object to either raise program_error
or to behave "normally", getting the lock, waiting on a queue, etc.
If noone ever wakes the caller up before the protected object
goes away, it would seem you could end up with an indefinitely
blocked task.

> ... if it is not erroneous, what would be the status?

I don't see any need to make it erroneous, since the possible results
seem pretty easily specifiable.  They are pretty similar to what
happens if you violate the no-potentially-blocking-operations rule.

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

From: Robert Dewar
Date: Thursday, December 6, 2001  7:15 PM

OK, but Tuck's rules certainly require an extra test, his possibilities
for bounded error are not the natural possibilities in the absence of a
check, given that finalization is likely to return the lock resources
to the system etc.

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

From: Tucker Taft
Date: Thursday, December 6, 2001  7:33 PM

I am certainly not wed to my list.  I was simply making the
point that it can be a bounded error without requiring
that program error be raised in all cases.  Given your
suggestion, an additional possibility would be that
no lock is acquired, but otherwise the call proceeds
normally.  I would think that by the time it is finalized,
there can be no subtasks hanging around, meaning
that there is no possibility of multi-threaded access
to the object, implying that getting a lock is irrelevant
anyway.

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

From: Cyrille Comar
Date: Friday, December 7, 2001  3:58 AM

Tucker Taft writes:
 > I am certainly not wed to my list.  I was simply making the
 > point that it can be a bounded error without requiring
 > that program error be raised in all cases.

From the user point of view, it is better to have a predicable
behavior and the only reasonnable one is to raise Program_Error. I
understand (very well) the point about not putting too much pressure on
the implementors but if this case is not erroneous, I am not sure it
is simpler to guarantee proper behavior than to raise
Program_Error. So the "user-friendly" behavior may be the best.

 > Given your suggestion, an additional possibility would be that no
 > lock is acquired, but otherwise the call proceeds normally.  I
 > would think that by the time it is finalized, there can be no
 > subtasks hanging around, meaning that there is no possibility of
 > multi-threaded access to the object, implying that getting a lock
 > is irrelevant anyway.

I am afraid this is not the case unfortunately. The scenario given by
Steve Baird in this thread concerning 2 collections shows that it is
relatively easy to access objects after they have been finalized. If
the object type of the first collection has a protected type
component, and the type of the second has task components, then you
may have to deal with concurrent access to the finalized protected
object.

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

From: Ted Baker
Date: Sunday, December 9, 2001  3:32 PM

| But if Program_Error is not guaranteed to be raised, is it still a
| bounded error? if it is not erroneous, what would be the status?

Raising Program_Error seems like the right thing to do, assuming
you want it to be a bounded error strongly enough to pay the
overhead of checking for this condition.

If you don't want to bother checking, I would expect the effects
not to be bounded (maybe enqueuing a block of storage that has
been freed and is likely to be reallocated for another purpose).
Hence, you fall into the erronous category.

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

From: Gary Dismukes
Date: Monday, December 10, 2001  2:30 PM

It either needs to be defined as a bounded error or as erroneous,
we can't have it both ways.  If it's a bounded error then you have
to define the behavior in the case where P_E is not raised, but
it's not a choice for the behavior to be erroneous.

I think it would be really undesirable for this to be treated as an
erroneous condition.  My preference would be to require Program_Error,
but I can live with it being a bounded error with choices being
Program_Error or having the call work if vendors prefer implementation
flexibility over portable behavior.

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

From: Randy Brukardt
Date: Monday, December 10, 2001  7:27 PM

The problem is, there appear to be cases where it has to be erroneous.
However, I think if we separate the memory and protected object problems, we
can have it be "raise Program_Error" for the protected object case, and
erroneous for the memory case.

Confused? Let me try to show some examples.

This problem happened to us in Claw once some years ago. Some compiler's
programs crashed mysteriously, others worked. We eventually realized that
the locks were getting finalized before the objects. The code looked
something like:

   package Claw is
       ...
       type Root_Window_Type is new Ada.Finalization.Controlled with private;
       type Any_Window_Access_Type is access all Root_Window_Type;
       ...
   private
       ...
       procedure Finalize (Object : in out Root_Window_Type);
       ...
   end Claw;

   package body Claw is
       protected type Lock_Type is
           entry Get_Lock;
	   procedure Free_Lock;
       ...
       end Lock_Type;

       Window_Lock : Lock_Type;

       procedure Finalize (Object : in out Root_Window_Type) is
       begin
           Window_Lock.Get_Lock;
           ...
           Window_Lock.Free_Lock;
       end Finalize;

	 ...
   end Claw;

Now, if there are allocated objects of Root_Window_Type hanging around at
finalization, what happens is that the Window_Lock object is finalized, and
then (sometime later), the Any_Window_Access_Type objects are finalized.
That finalization would access the Window_Lock, which is now finalized. Some
compilers generated code which faulted in this case, others worked fine.
(None raised an exception!). (Most of the ones that worked failed to
finalize objects allocated from Any_Window_Access_Type at all, meaning they
had another bug covering up this one.)

Anyway, if the implementation marked the Window_Lock object as being
finalized (somehow), then it is no problem to raise Program_Error here.

----

Now, however, consider an implementation where there are multiple locks, and
those locks are chained together in order to be able to detect deadlocks.
Further assume that these objects are allocated from a storage pool, which
frees all of its memory when it is finalized. This would look something
like:

   package Claw is
       ...
       type Root_Window_Type is new Ada.Finalization.Controlled with private;
       type Any_Window_Access_Type is access all Root_Window_Type;
       ...
   private
       ...
       Lock_Pool : My_Pool; -- Frees memory when finalized.
       type Lock_Type;
       type Lock_Access is access all Lock_Type;
       for Lock_Access'Storage_Pool use Lock_Pool;
       type Root_Window_Type is new Ada.Finalization.Controlled with record
	   My_Lock : Lock_Access;
	   ...
       end record;

       procedure Finalize (Object : in out Root_Window_Type);
       ...
   end Claw;

   package body Claw is
       protected type P_Lock_Type is
           entry Get_Lock;
	   procedure Free_Lock;
       ...
       end P_Lock_Type;
       type Lock_Type is limited record
	   Next : Lock_Access;
	   Lock : P_Lock_Type;
       end record;

       procedure Finalize (Object : in out Root_Window_Type) is
       begin
           Object.My_Lock.Get_Lock;
           ...
           Object.My_Lock.Free_Lock;
       end Finalize;

       ...
   end Claw;

In this program, objects allocated from Lock_Access would be finalized,
followed by Lock_Pool (freeing the memory holding the locks), followed by
objects allocated from Any_Window_Access_Type.

That means that the access Object.My_Lock is now accessing memory that no
longer exists. Thus, we cannot insist on Program_Error being raised in this
case: we cannot be sure of the contents of the memory that is accessed.

Luckily, this problem is not really with access to the finalized protected
object, but rather to the deallocated memory. As long as access to the
deallocated memory (for *any* reason) is erroneous, it probably is OK to
insist on always raising Program_Error when accessing a finalized protected
object. (Can anyone find a counter-example?)

However, I'm not sure that all of the deallocated memory cases are handled
by the standard. If the memory in Lock_Pool was deallocated explicitly with
Unchecked_Deallocation, there is no problem: the access is already
erroneous. But what if we had used a collection instead of a pool? These
aren't explicitly deallocated, but storage is reclaimed (13.11(18)). Is this
covered by 13.11.2(16)? (That is, is such an object "nonexistent"?) The
standard gives the definition of "nonexistent" to be in 13.11.2(10), which
is only talking about "Free", and not collection freeing. Luckily, the word
"nonexistent" is never actually defined in the standard, so it is only a
tiny leap to say that it is intended to imply to the freeing of collections
(and also to values created by 'Unchecked_Access). Does everyone agree with
this?

---

All of this implies that programmers had better mark finalized objects as
such, so that any "late" accesses will treat the objects as invalid.
Otherwise, weird things may happen if they are accessed after finalization,
and that is clearly possible, even in non-erroneous cases.

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

From: Tucker Taft
Date: Monday, December 10, 2001  9:31 PM

> The problem is, there appear to be cases where it has to be erroneous.
> However, I think if we separate the memory and protected object problems, we
> can have it be "raise Program_Error" for the protected object case, and
> erroneous for the memory case.
> ...

I agree that these cases can be distinguished.  If the protected
object still "exists" then it would be erroneous for its
storage to have been reclaimed (see 13.11(21) and 7.6.1(11.b)).
Hence, so long as the protected object exists, calling one
of its protected operations should not (by itself) be erroneous.
However, if the protected object has been finalized, it
seems reasonable to consider this a bounded error.

I don't agree that we should specify Program_Error, especially
since we have gone out of our way to allow other bounded errors
relating to protected objects to have other effects.  Why impose
an extra overhead now with this relatively rare situation?

So I would recommend it be a bounded error, but that Program_Error
be only one of various possible results.

> ...
> Luckily, this problem is not really with access to the finalized protected
> object, but rather to the deallocated memory. As long as access to the
> deallocated memory (for *any* reason) is erroneous, it probably is OK to
> insist on always raising Program_Error when accessing a finalized protected
> object. (Can anyone find a counter-example?)

As mentioned above, I wouldn't insist on Program_Error, but it
shouldn't be erroneous either.

> However, I'm not sure that all of the deallocated memory cases are handled
> by the standard. If the memory in Lock_Pool was deallocated explicitly with
> Unchecked_Deallocation, there is no problem: the access is already
> erroneous. But what if we had used a collection instead of a pool? These
> aren't explicitly deallocated, but storage is reclaimed (13.11(18)). Is this
> covered by 13.11.2(16)? (That is, is such an object "nonexistent"?) The
> standard gives the definition of "nonexistent" to be in 13.11.2(10), which
> is only talking about "Free", and not collection freeing. Luckily, the word
> "nonexistent" is never actually defined in the standard, so it is only a
> tiny leap to say that it is intended to imply to the freeing of collections
> (and also to values created by 'Unchecked_Access). Does everyone agree with
> this?

A storage collection may not be reclaimed until the master is "left"
(see 13.11(18)), so the objects in the collection must no longer exist.
Storage allocated from an (explicit) storage pool may not be reclaimed
while the object exists (see 13.11(21) and 7.6.1(11.b)).  These two rules
together mean that so long as an object "officially" exists (essentially
equivalent to being accessible unless deleted via Unchecked_Deallocation),
it's storage must not be reclaimed.  So there is no need to special-case
objects allocated from a collection -- they exist until the enclosing
master is left, if not deleted via Unchecked_Deallocation.

> ---
>
> All of this implies that programmers had better mark finalized objects as
> such, so that any "late" accesses will treat the objects as invalid.
> Otherwise, weird things may happen if they are accessed after finalization,
> and that is clearly possible, even in non-erroneous cases.

The notion of a "well-defined finalized state" is mentioned
explicitly in 7.6.1(11.g).

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

From: Randy Brukardt
Date: Tuesday, December 11, 2001  3:21 PM

> A storage collection may not be reclaimed until the master is "left"
> (see 13.11(18)), so the objects in the collection must no longer exist.
> Storage allocated from an (explicit) storage pool may not be reclaimed
> while the object exists (see 13.11(21) and 7.6.1(11.b)).  These two rules
> together mean that so long as an object "officially" exists (essentially
> equivalent to being accessible unless deleted via Unchecked_Deallocation),
> it's storage must not be reclaimed.  So there is no need to special-case
> objects allocated from a collection -- they exist until the enclosing
> master is left, if not deleted via Unchecked_Deallocation.

But there is no definition of "exist" in the RM. The only place that it is
ever used is in the Unchecked_Deallocation text. Clearly, we want objects to
exist until their memory is reclaimed (either by scope leaving or until an
Unchecked_Deallocation call) -- but the RM never says that.

The rules about when a collection can be reclaimed are fine, but since we're
without a definition of "exist", its unclear exactly when an item no longer
exists (and thus a reference becomes erroneous). The issue is important
because of the potential use of 'Unchecked_Access. Certainly, we want to
allow the reclamation of storage, and we want 13.11(16) to apply at some
reasonable point. And exactly when memory can be reclaimed during scope
leaving is not spelled out by the RM.

This is a real issue for me, as I've always assumed that an object ceased to
"exist" after the completion of its finalization (or the finalization of its
collection, for an allocated object). That's of course slightly before the
master is "left". That's how Janus/Ada 95 is implemented, with
compiler-managed memory objects being freed immediately after the
finalization of the object. (Storage management, finalization, and task
waiting is handled by one integrated mechanism.) To delay all storage
management until the master is "left" would require a completely separate
(but substantially equal) storage management scheme, effectively doubling
the overhead in both time and space.

Admittedly, I don't see any support in the RM for my interpretation. But,
since it seemed to me to be the only reasonable interpretation, I never
investigated further. Apparently, Tucker has a different interpretation
(which also is unsupported in the RM). Sigh.

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

From: Tucker Taft
Date: Tuesday, December 11, 2001  4:41 PM

Of course I think there is more support for my position than yours, though
I sympathize.  The AARM goes out of its way to say objects need to be
in a "well-defined finalized state" when they are accessible
after they have been finalized.  Ignoring Unchecked_Access for a moment,
if we presume an object "exists" as long as it is accessible, and has
not been explicitly (unchecked) deallocated, then the object can
exist after it has been finalized.  I believe this means that you shouldn't
reclaim any storage for objects until all finalization for the scope
is complete, since finalization routines can generally "see" any
object in the scope.  13.11(18) says as much for collections; 7.6.1(11.g)
says as much for other objects.

Equivalently, since the RM does not say it is erroneous to refer to an
object after it has been finalized, the implementation must not
free the storage if it can be referenced by a yet to be invoked
finalization routine.

Hence, I think this implies that if you have per-object work to
do storage reclamation, finalizing a master requires three separate
sequences:
        1) wait for all subtasks
        2) finalize all controlled/protected objects
        3) reclaim all storage

Trying to intermingle any of these three will violate the RM in my view.
This might suggest having three "cleanup" lists per master, one for
task waiting, one for finalization, and one for storage reclamation.

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

From: Randy Brukardt
Date: Tuesday, December 11, 2001  5:31 PM

> Equivalently, since the RM does not say it is erroneous to refer to an
> object after it has been finalized, the implementation must not
> free the storage if it can be referenced by a yet to be invoked
> finalization routine.

The RM never anywhere says that it is erroneous to access through an
'Unchecked_Access to an object that is out of scope. That's because "exists"
is never defined at all. But it's clear that something has to be erroneous
here. The only question is how much.

> Hence, I think this implies that if you have per-object work to
> do storage reclamation, finalizing a master requires three separate
> sequences:
>         1) wait for all subtasks
>         2) finalize all controlled/protected objects
>         3) reclaim all storage
>
> Trying to intermingle any of these three will violate the RM in my view.
> This might suggest having three "cleanup" lists per master, one for
> task waiting, one for finalization, and one for storage reclamation.

Tasks aren't a problem. You don't need to wait for them until they are
activated, and that is always that last thing in the declarative part. So
you just put the "wait block" on the chain as the first step of activating
tasks. (The "master block" is put on the chain first, in order to clean up
any unactivated tasks. That has no visible sematic effects.)

In any case, have three sets of chains, with identical semantics is simply
an unacceptable overhead. You can't use registers for them if there are
three (no way that you can allocate six registers to these guys!), and
you'll have to copy all three on the subprogram linkage.

A simpler solution would be to put a storage pool object on the finalization
chain as the first step of every master (and then allocate from that pool).
The problem with that is one of overhead: since you have to do it absolutely
first, it is very hard to optimize it away. (The current scheme of waiting
until a use to allocate a thumb would have to be abandoned.) Especially
given that it could be passed into thunks (assignment, initialize, etc.)
without being used. And without optimization, the overhead on simple
subprograms would be prohibitive.

Which brings up my other question. Why is it that the system defined storage
pools have to operate very differently than user-defined ones? A user cannot
write a pool with behavior like that. Certainly, a user-defined pool has to
deallocate its memory when it is finalized. If it didn't do that, it could
never do it. For most pools, deallocation is mandatory. (My pool that
directly uses the Windows virtual memory system to allocate large blocks
would require rebooting older Windows OSes to get the memory back if it
doesn't free it.)

However, for some reason, the same behavior for the system defined
collection pool is illegal. Yet, it has the same problem ('Storage_Size does
not need to be static and can be larger than the allowed stack frame, so it
has to be prepared to allocate memory from the heap).

Sigh. I give up. Anybody need an Ada engineer 45% time?

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

From: Cyrille Comar
Date: Tuesday, December 11, 2001  3:09 AM

Tucker Taft writes:
 > I don't agree that we should specify Program_Error, especially
 > since we have gone out of our way to allow other bounded errors
 > relating to protected objects to have other effects.  Why impose
 > an extra overhead now with this relatively rare situation?

That's fine with me (not to mandate PE) although at the implementation
level it won't make a huge difference and the simplest is to always
raise PE. Especially if the Ada runtime is built on top of pthreads
where you want to release the locks when the protected object is
finalized in order to avoid leaks. Once you have made this choice,
there is little possibility to avoid the extra check (is the object
already finalized) either to raise PE or to avoid using a
released lock...

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

From: Randy Brukardt
Date: Tuesday, December 11, 2001  3:25 PM

I agree with you when you are on top of an OS (the case I'm usually in as
well).

But a bare machine implementation using ceiling priorities may not have a
lock at all. And for simple function and procedure calls, there may not need
to be any checking at all. I think that's the case that Tucker is thinking
about, not the entry call (queued) case or on an OS, where you'll probably
have to make the check in any case.

I don't object to "Program_Error or work normally" as a bounded error. But
certainly we need to allow the raising of Program_Error here.

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

From: Steve Baird
Date: Tuesday, March 26, 2002  6:49 PM

In addition to the access-after-finalization problems already described
in AI-280, there are analogous problems with access types.

The finalization associated with a non-derived access type is described
in 7.6.1(11).

This "collection finalization" consists of iterating over the set of
allocated objects and finalizing them in some order.

The RM states that each allocated object "that still exists" at the point
of collection finalization is finalized. This suggests a fixed set which
is unaffected by subsequent allocations and deallocations.

It is not clear what happens if
   a) Objects are added to the set during this iteration (via an
      allocator).
   b) Objects are deleted from this set during this iteration (via
      a call to an instance of Unchecked_Deallocation).
   c) Objects are added to the set after this finalization process is
      complete (via an allocator).

There are also problems with tasks which are allocated after the master
of the access type has completed the first step of its finalization,
waiting for the termination of any tasks dependent on the master (9.3(5)).

To demonstrate that these scenarios are possible, consider the following
example:

     with Ada.Finalization;
     with Ada.Unchecked_Deallocation;
     package P is
         type T1 is new Ada.Finalization.Controlled with null record;
         procedure Finalize (X : in out T1);

         type T2 is new Ada.Finalization.Controlled with null record;
         procedure Finalize (X : in out T2);

         task type Tsk;
         type Tsk_Ref is access Tsk;

         X1 : T1;

         type T2_Ref is access T2;

         procedure Free is new Ada.Unchecked_Deallocation (T2, T2_Ref);
     end P;

   Assuming that Ref's finalization is non-null (i.e. that the set of allocated
   objects to be iterated over is non-empty), P.T2's Finalize procedure will be
   invoked during P.T2_Ref's collection finalization.

   P.T1's finalize procedure will be invoked after P.T2_Ref's collection
   finalization is complete (because P.X1 is declared before P.T2_Ref).

   Either of these two procedures might contain allocators of type T2_Ref or
   Tsk_Ref, or calls to P.Free.

I propose
   1) A clarification of the collection finalization rules to take into account
      changes to the set of objects associated with a collection during the
      collection's finalization.
         a) If an object is allocated during this period, it will be
            finalized eventually.
         b) If an object is deallocated during this period, there are 3
            cases to consider:
              i)   If the object being freed has already been finalized as
                   part of collection finalization, it is simply finalized
                   again and its storage is deallocated.
              ii)  If the object's finalization is currently in progress,
                   the object is recursively finalized, its storage is
                   deallocated, and the first Finalize invocation typically
                   must be careful not to refer to its parameter
                   (whose storage has now been deallocated).
              iii) If the object's finalization has not begun yet, it is
                   finalized and its storage is deallocated. The (now
                   deallocated) object is not finalized as part of collection
                   finalization.

    2) After a collection's finalization has finished, evaluation of an
       allocator of a descendant of the access type should raise Program_Error.
       This rule is really only needed if the designated type "requires
       nontrivial finalization" (i.e. it is controlled, is protected, or has
       protected or controlled subcomponents); without this rule, the
       resulting object would never be finalized. It might be more regular
       to impose the rule in all cases, but the costs in overhead and
       compatibility in the trivial-finalization case are probably too high to
       justify this.

    3) An attempt to allocate a task after the master of the access type has
       finished waiting for the termination of its dependent tasks should raise
       Program_Error.

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

From: Ted Baker
Date: Wednesday, March 27, 2002  4:58 AM

|     2) After a collection's finalization has finished, evaluation
| of an allocator of a descendant of the access type should raise
| Program_Error.

Why not simply raise Program_Error for any attempt to allocate
after the collections finalization has *started*?
                                        =======

It is hard for me to imagine writing (and adequately testing!)
finalization code for a collection that I would trust to be
correct for concurrent allocations and deallocations of items in
the collection.

Requiring/allowing such concurrency of collection finalization
and allocation/deallocation activity is just asking for trouble.

| 3) An attempt to allocate a task after the master of the
| access type has finished waiting for the termination of its
| dependent tasks should raise Program_Error.

Of course.

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

From: Randy Brukardt
Date: Wednesday, April 17, 2002  8:13 PM

Ted said:

> |     2) After a collection's finalization has finished, evaluation
> | of an allocator of a descendant of the access type should raise
> | Program_Error.
>
> Why not simply raise Program_Error for any attempt to allocate
> after the collections finalization has *started*?

Good question. It's a lot simpler than Steve's proposal. The problem with
Steve's proposal is easily seen by looking at his case 1bii:

  If the object's finalization is currently in progress, the object
  is recursively finalized, its storage is deallocated, and the
  first Finalize invocation typically must be careful not to refer to
  its parameter (whose storage has now been deallocated).

But this appears impossible. How can I write a Finalize that "is careful not
to refer to its parameter"? Even if we don't have to worry about other tasks
(because they all must necessarily have been waited for), we can still
easily do this by (mistakenly) calling some subprogram. What happens if we
aren't "careful"? Presumably the program is erroneous. That doesn't seem
like a useful way to handle what is most likely a bug.

The question is, is there some useful capability that requires all of this
extra definition? I would say no: this check is most likely going to turn up
a bug in the user's finalization code than anything useful. Even when the
deallocation is benign, we more than likely would prefer to avoid it.

So I would simplify the proposal to:

For an access type with whose designated type has a controlled or protected
part, once a collection's finalization has started, evaluation of an
allocator or a call of an instance of Unchecked_Deallocation of a descendant
of the access type raises Program_Error. For other access types (whose
designated type does not have a controlled or protected part), evaluation of
an allocator or a call of an instance of Unchecked_Deallocation of a
descendant of the access type is a bounded error. If the error is detected,
Program_Error is raised. Otherwise, the allocation or deallocation proceeds
normally. For an allocator, whether the object is ever finalized is
unspecified. [Such a finalization cannot have a visible effect.]

An attempt to allocate a task after the master of the access type has
finished waiting for the termination of its dependent tasks raises
Program_Error.

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

From: Randy Brukardt
Date: Wednesday, April 17, 2002  10:10 PM

I said:

> The question is, is there some useful capability that requires all of this
> extra definition? I would say no: this check is most likely going to turn
up
> a bug in the user's finalization code than anything useful. Even when the
> deallocation is benign, we more than likely would prefer to avoid it.

Unfortunately, I've kept thinking about this while writing up the AI, and
I've found a reason that (part of) this capability is useful.

Claw has a classwide access type that can point at any window object. Claw
also enforces a rule that all child windows have to be destroyed before
their parent (necessary as Windows does it automatically, but if we let
Windows do it, we wouldn't call the appropriate, possibly overridden
finalizer). In our examples, Claw objects are generally allocated on the
stack, but nothing prevents a program from allocating them instead.

So, if we have a program like:

     Window, Button : Claw.Any_Window_Access_Type;
   begin
     Button := new Claw.Buttons.Button_Type;
     Window := new Claw.Basic_Window.Basic_Window_Type;
     Create (Window.all, ....);
     Create (Button.all, Parent => Window.all, ...);
     ...

Now, if these objects are never deallocated, the collection finalization of
Claw.Any_Window_Access_Type will finalize them. Let's assume that Window is
finalized first. That finalization will destroy Button (as it is a child of
Window).

In Claw, there is no problem, since we only operate on objects, leaving
memory management to the caller. However, it is easy to imagine Claw* which
uses access types, with Create calls returning pointers to allocated
objects. (This structure is common in objects ported from C++ or Java.)
Claw* would deallocate objects when it destroyed them. In that structure,
the destruction of Button would deallocate an object for the collection that
we are finalizing.

Clearly, this structure is not so weird that we can safely outlaw it. Thus,
I reluctantly conclude that we have to allow deallocations until the
collection is completely finalized.

However, the situation is different for allocators. Creating something (of
the same type) during finalization of a type is pretty weird. We can safely
eliminate from consideration.

Steve notes (implicitly) in his writeup that deallocation after the
finalization completes does not need a special check. It can only do
something interesting if an allocation after the finalization completes
previously happened. So we do not need a special rule for that. Moreover, we
don't need a special rule for either of Steve's cases 1bi and 1biii. These
are what would happen simply by following the rules of the RM. (We should
describe them in the AI and AARM, though.) In addition, Ted's concern is a
non-issue for deallocation alone. That's because the standard says that the
finalization is done in an arbitrary order. Thus, an implementation which
depends on the order of finalization is already wrong. And all that explicit
deallocations do is possibly change the order. Case 1bii (deallocating the
object itself) is also not a real problem. If it is referenced after
deallocation, the execution is erroneous (by a reasonable interpretation of
"nonexistent" in 13.11.2(16)). We may want a rule for this case anyway (to
avoid making implementations support this case; without a rule, the runtime
cannot access the object again after calling Finalize, and this seems overly
constraining). There is no benefit to mandating a check here (and it would
be hard to perform anyway).

Conclusion: we do not need to change anything in the current RM for the
deallocation case. In particular, we do not need a check for deallocations.

This conclusion frees us to make the check for allocations at any convenient
point. And at the start of finalization is certainly easier for
implementations (the runtime can iterate through a list without having to
worry about someone adding something), and doesn't seem to cause problems
for programs (at least until I think of a counter-example. :-)

That makes the proposal:

For an access type with whose designated type has a controlled or protected
part, once a collection's finalization has started, evaluation of an
allocator
of a descendant of the access type raises Program_Error. For other access
types (whose designated type does not have a controlled or protected part),
evaluation of an allocator of a descendant of the access type is a bounded
error. If the error is detected, Program_Error is raised. Otherwise, the
allocation proceeds normally; when the object is finalized (or if it ever is)
is unspecified. [Such a finalization cannot have a visible effect.]

An attempt to allocate a task after the master of the access type has
finished waiting for the termination of its dependent tasks raises
Program_Error.

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

From: Randy Brukardt
Date: Wednesday, November 3, 2004  7:54 PM

AI-280 adds a number of checks on allocation after finalization of master
or pool. There is no obvious check name in 11.5 to represent these checks;
but it seems likely that these should be able to be suppressed.

Should these have a check name? If so, what should it be?

The best I could come up with is Finalized_Check or After_Finalization_Check
but that seems to be discussing something to do with finalization. Other
ideas were Allocation_Too_Late_Check or Baird_Bug_Check. :-)

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

From: John Barnes
Date: Thursday, November 4, 2004  2:23 AM

Why not just Allocation_Check?

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

From: Randy Brukardt
Date: Thursday, November 4, 2004  5:48 PM

OK, seems good.

I've added the following before 11.5(20):

Allocation_Check
For an allocator, check that the master of any tasks has not yet finished
waiting for tasks, and that the finalization of the collection has not
started.

I also moved Accessibility_Check so that the checks in this grouping are in
alphabetical order (as the other groupings are).

As this AI is in editorial review, and this is mainly an editorial change
(we just forgot to define the check name for this, and probably other checks
that we've defined), it will go directly to WG9 without further
consideration by the ARG unless someone objects. (In which case, we'll
withdraw the AI from WG9 and reconsider it in Atlanta.)

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

From: Tucker Taft
Date: Thursday, November 4, 2004  7:54 PM

I might recommend:

   For an allocator, check that the master of any task created by the
   allocator has not already finished waiting for its dependents, and that
   any finalization associated with the type of the allocator has not
   already started.

The term "collection" is not defined in the manual, as far as I know.
I guess this is a gripe about AI-280 in general.  It uses the
term "collection" several times without defining it.  I would rather
not introduce the term unless we really need it.  It will almost
certainly get confused with "storage pool" in the user's mind.

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

From: Randy Brukardt
Date: Thursday, November 4, 2004  8:28 PM

Don't forget that these are one-liners intended to be simple and
non-normative. This already rather long for this section. (Of course, they
shouldn't contradict the normative wording.)

The term "finalization of the collection" was defined in the AI in
7.6.1(11). It refers to a very specific action. "any finalization associated
with the type of the allocator" is far too vague to be meaningful. It would
be OK here as this isn't normative, but certainly not in the normative
wording -- and it's way too wordy for this text. Of course, like all
technical terms, it will be indexed in the index, probably both as
"finalization of the collection" and "collection, finalization of".

In any case, this wording is a simplified version of the normative wording
of the AI. If you're saying that you have problems with the normative
wording of the AI, that's fine but then we'll have to reopen the AI. And
it's already in the AARM and I sure as heck don't want to take it out. The
term "finalization of the collection" has been in every version of the AI, I
believe, and certainly no one has complained about it before (I just checked
all of the minutes on this AI).

You could of course do an editorial review on the AI like you're supposed to
anyway and make any suggestions. :-)

The only change I made was to replace the second "tasks" with "dependents"
so that the wording wasn't quite as confusing. But feel free to try again to
produce a one-liner for this use.

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

From: John Barnes
Date: Friday, November 5, 2004  10:14 AM

Well I'm happy with this despite what Tuck says.

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


Questions? Ask the ACAA Technical Agent