Version 1.1 of ais/ai-00280.txt

!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.

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