Version 1.7 of ai05s/ai05-0107-1.txt
!standard 7.6.1(20) 09-10-12 AI05-0107-1/04
!standard 13.11(16)
!standard 13.11(21)
!standard 13.11.2(9/2)
!class binding interpretation 08-08-07
!status Amendment 201Z 09-06-27
!status WG9 Approved 09-11-05
!status ARG Approved 7-0-0 09-06-14
!status work item 08-08-07
!status received 06-06-21
!priority Medium
!difficulty Hard
!qualifier Omission
!subject A failed allocator need not leak memory
!summary
If an allocator fails (raises an exception), the implementation is allowed to
immediately finalize any components previously initialized and then call
Deallocate the appropriate number of times to free the memory.
The Allocate and Deallocate procedures of a storage pool can be implicitly
called during the execution of allocators, assignment operations,
build-in-place aggregates and return statements, and (for Deallocate),
during an instance of Unchecked_Deallocation.
!question
When an allocator raises an exception after allocating memory, we do not want
to be required to drop that memory on the floor. However, the language rules
as currently written seem to have that effect.
First, there needs to be a permission to finalize any parts of the allocated
object that were successfully initialized. Since their master is that of the
access type, once their initialization has finished, they have to stick around
until the collection of the type is finalized (since there is no explicit
access value to explicitly free in this case).
Second, there needs to be a permission that the Deallocate of a user-defined
storage pool can be called in such a case (not just from an explicit call to
Unchecked_Deallocation). Otherwise, the memory cannot be freed unless a
standard pool is used.
Should these problems be fixed? (Yes.)
!recommendation
(See summary.)
!wording
Add after 7.6.1(20):
Implementation Permissions
If the execution of an allocator propagates an exception, any parts of the
allocated object that were successfully initialized may be finalized as
part of the finalization of the innermost master enclosing the allocator.
AARM Reason: This allows deallocating the memory for the allocated object
at the innermost master, preventing a storage leak. Otherwise, the
object would have to stay around until the finalization of the collection
that it belongs to, which could be the entire life of the program if the
associated access type is library level.
Replace 13.11(16) by:
An allocator of type T allocates storage from T's storage pool. If the storage
pool is a user-defined object, then the storage is allocated by calling Allocate
as described below.
Add after 13.11(21):
Implementation Requirements
The Allocate procedure of a user-defined storage pool object P may be called by
the implementation only to allocate storage for a type T whose pool is P and:
* During the execution of an allocator of type T;
AARM Ramification: This includes during the evaluation of the initializing expression
such as an aggregate; this is important if the initializing expression is
built in place. We need to allow allocation to be deferred until the size of the
object is known.
* During the execution of a return statement for a function whose result is
built-in-place in the result of an allocator of type T;
AARM Reason: We need this bullet as well as the preceding one in order that exceptions
that propagate from such a call to Allocate can be handled within the return statement.
We don't want to require the generation of special handling code in this unusual case,
as it would add overhead to most return statements of composite types.
* During the execution of an assignment operation with a target of an allocated
object of type T with a part that has an unconstrained discriminated subtype with
defaults.
AARM Reason:
We allow Allocate to be called during assignment of objects with mutable parts so
that mutable objects can be implemented with reallocation on assignment.
(Unfortunately, the term "mutable" is only defined in the AARM, so we have to use
the long-winded wording shown here.)
AARM Discussion: Of course, explicit calls to the procedure are also allowed and
are not bound by any of the rules found here.
for one of the calls of Allocate described above, P (equivalent to T'Storage_Pool)
is passed as the Pool parameter. The Size_In_Storage_Elements parameter indicates the
number of storage elements to be allocated, and is no more than
D'Max_Size_In_Storage_Elements, where D is the designated subtype of T.
The Alignment parameter is D'Alignment if D is a specific type, and otherwise is
the alignment of the specific type identified by the tag of the object being
created. The result returned in the Storage_Address parameter is used as the
address of the allocated storage, which is a contiguous block of memory of
Size_In_Storage_Elements storage elements. Redundant: [Any exception propagated
by Allocate is propagated by the construct that contained the call.]
[Editor's Note: The above paragraph contains the changes made by AI05-0116-1. The
following AARM note is moved from 13.11(16.b).]
AARM Ramification: Note that the implementation does not turn other exceptions
into Storage_Error.
The number of calls to Allocate needed to implement an allocator for any
particular type is unspecified. The number of calls to Deallocate
needed to implement an instance of Unchecked_Deallocation (see 13.11.2) for
any particular object is the same as the number of Allocate calls for that
object.
AARM Reason: This supports objects that are allocated in one or more parts. The
second sentence prevents extra or missing calls to Deallocate.
The Deallocate procedure of a user-defined storage pool object P may be called
by the implementation to deallocate storage for a type T whose pool is P only at
the places when an Allocate call is allowed for P, during the execution of an
instance of Unchecked_Deallocation for T, or as part of the finalization of the
collection of T. For such a call of Deallocate, P (equivalent to T'Storage_Pool)
is passed as the Pool parameter. The value of the Storage_Address parameter for a
call to Deallocate is the value returned in the Storage_Address parameter of the
corresponding successful call to Allocate. The values of the Size_In_Storage_Elements and
Alignment parameters are the same values passed to the corresponding Allocate call.
Any exception propagated by Deallocate is propagated by the construct that
contained the call.
AARM Reason: We allow Deallocate to be called anywhere that Allocate is,
in order to allow the recovery of storage from failed allocations (that
is, those that raise exceptions); from extended return statements that
exit via a goto, exit, or locally handled exception; and from objects
which are reallocated when they are assigned. In each of these cases,
we would have a storage leak if the implementation did not recover
the storage (there is no way for the programmer to do it). We do not
require such recovery, however, as it could be a serious performance
drag on these operations.
Modify 13.11.2(9/2):
3. Free(X), when X is not equal to null first performs finalization of
the object designated by X (and any coextensions of the object — see
3.10.2), as described in 7.6.1. It then deallocates the storage
occupied by the object designated by X (and any coextensions). If
the storage pool is a user-defined object, then the storage is
deallocated by calling Deallocate {as described in 13.11}[, passing
access_to_variable_subtype_name'Storage_Pool as the Pool parameter.
Storage_Address is the value returned in the Storage_Address parameter
of the corresponding Allocate call. Size_In_Storage_Elements and
Alignment are the same values passed to the corresponding Allocate
call]. There is one exception: if the object being freed contains
tasks, the object might not be deallocated.
[Editor's note: the deleted rules were moved to 13.11 as described above,
as they apply to all calls to Deallocate, even ones that are generated by the
compiler to prevent storage leaks and that are not directly associated with
a call of Unchecked_Deallocation.]
!discussion
We are using the definition of "built in place" as defined by AI05-0067-1.
These rules give additional permissions to implementations; they are not
intended to put any new requirements on implementations.
We have worded the list of places where Allocate and Deallocate are allowed
to be called implicitly as specifically as possible. We could have used more
general wording, possibly going as far as allowing it to be called at
any time. But that seems bad; we don't want programmers to have to worry about
Allocate being called in unusual places or by random tasks.
---
We've reorganized the wording so that all of the description of what is passed
to Allocate and Deallocate are Implementation Requirements. These are requirements
on the implementation (as opposed to a description of how the routines operate),
so this is the appropriate heading.
Additionally, these requirements apply to all implementation-generated calls
on Allocate and Deallocate, not just those directly associated with allocators
and Unchecked_Deallocation. So it makes the most sense to give those as separate
requirements, not tied to particular syntax.
---
AARM 13.11(16.a) says that multiple calls to Allocate are OK, so the rule to
that effect is not strictly needed. But with the explicit specification
of where calls are allowed, it seems important to also specify how many
calls are allowed. OTOH, the rule stating the number of calls to Deallocate
are the same is needed. It disallows Deallocate from being called multiple
times with the same parameters (different, unrelated parameters are not allowed
by other implementation requirements).
The rules about the parameters to Deallocate needing to be the same as the
Allocate call were moved from 13.11.2 to 13.11, as they apply
equally to the deallocations associated with failed allocators and with
reallocation on assignment. It is important that the behavior in all of these
cases be specified, so that an implementer of a custom pool can rely on
the behavior of the compiled code.
Moreover, it is weird that the rules specifying how a pool is used by the
implementation are separated from the definition of the pool. Moving those
rules puts them altogether, making it easier for the implementer of custom
pools to find them.
---
The early finalization permission
It has been said that there is no need to allow early finalization in order
to prevent leaks. The reason given (by usually knowledgable people) is that
the object isn't "allocated" until the initialization finishes successfully.
This reason doesn't hold water, however, as it fails to take into account
controlled components. A controlled component may finish its initialization
but the whole object may not by a later exception during the initialization
of some other component. The Ada model surely does not allow dropping this
object on the floor without finalization for the controlled components that
finished initialization. Nor do we have any permission to do the finalization
early: the master of the controlled component is that of the access type,
and (unlike a return statement) there is no rule that makes it something else
early. Task parts aren't a problem however, as they never start executing
in this scenario.
We only allow this early finalization to occur at the innermost enclosing
master. We could have allowed any enclosing master, but there doesn't seem
to be any need to do so in order to prevent the storage leak: implementations
will want to be able to free the storage as soon as possible. We also could
have allowed it sooner, but we do not want finalization occurring at any
random point in a program (which would make reasoning about finalization
harder and could cause task synchronization issues); we want it only to
occur at well-defined points.
This permission only allows early finalization in the case of a failed allocator.
One could imagine extending this permission to allow finalizing of any
allocated object that can no longer be accessed by the program (other than for
finalization). That would allow more general storage management. However,
it is also more complicated, in that it would have to allow finalization at
any enclosing master and also decide if the permission ought to be extended
to task parts. Thus, we did not attempt a more general permission.
---
Reallocation on assignment:
This particular permission is considered quite important by the author.
The memory model of Janus/Ada assumes that Allocate and Deallocate can
be called at any time that's convenient to the compiler. That was the model
for the Janus/Ada 83 compiler, and it just got moved over to Ada 95 and its
user-defined storage pools.
For instance:
type Dyn_Str (Len : Natural := 0) is record
Str : String (1 .. Len);
end record;
type Acc_Dyn_Str is access Dyn_Str;
for Acc_Dyn_Str'Storage_Pool use ...;
Obj : Acc_Dyn_Str := new Dyn_Str'(2, "12"); --
...
Obj.all := (5, "ABCDE"); --
The Allocate of the pool will be called twice (once for the bulk of the record, and once
for the dynamically sized string data part) at (1). At (2), the original dynamically
allocated string part is Deallocated and then a new, larger dynamically sized string
part is allocated. This is an assignment statement, and that is not one of the
classic places for allocation.
In this interpretation, we need to do nothing to allow allocation and deallocation
anywhere. But it's not clear that the language allows that; it should. The author's
understanding has been that the language has always intended to allow (not require)
discontiguous objects and reallocation on assignment as long as the high-level
semantics is preserved. (Or the author will need a new day job...) 13.11(23) seems
to confirm this (as it wouldn't be necessary to talk about something not allowed),
as do various AARM notes.
One could imagine requiring that such reallocated parts be always required to be
allocated from a system pool (rather than a user-defined pool). But that would seem to
defeat the purpose of user-defined pools: the actual data (and the bulk of the storage)
would be in the system pool, not the user-defined pool. It makes much more sense to
allocate all of the parts of an object from the same pool; again, 13.11(23) appears
to confirm that was the intent.
As such, the rules have been written to make it clear that this implementation is
allowed.
!corrigendum 7.6.1(20)
Insert after the paragraph:
- For a Finalize invoked by a transfer of control due to an abort or selection
of a terminate alternative, the exception is ignored; any other finalizations due to
be performed are performed.
the new paragraph:
Implementation Permissions
If the execution of an allocator propagates an exception, any parts of the
allocated object that were successfully initialized may be finalized as
part of the finalization of the innermost master enclosing the allocator.
!corrigendum 13.11(16)
Replace the paragraph:
An allocator of type T allocates storage from T's storage pool. If the storage pool
is a user-defined object, then the storage is allocated by calling Allocate, passing
T'Storage_Pool as the Pool parameter. The Size_In_Storage_Elements parameter indicates
the number of storage elements to be allocated, and is no more than D'Max_Size_In_Storage_Elements,
where D is the designated subtype. The Alignment parameter is D'Alignment. The result returned
in the Storage_Address parameter is used by the allocator as the address of the
allocated storage, which is a contiguous block of memory of Size_In_Storage_Elements storage
elements. Any exception propagated by Allocate is propagated by the allocator.
by:
An allocator of type T allocates storage from T's storage pool. If the storage
pool is a user-defined object, then the storage is allocated by calling Allocate
as described below.
!corrigendum 13.11(21)
Insert after the paragraph:
If Storage_Pool is specified for an access type, then if Allocate can satisfy the request,
it should allocate a contiguous block of memory, and return the address of the first storage
element in Storage_Address. The block should contain Size_In_Storage_Elements storage elements,
and should be aligned according to Alignment. The allocated storage should not be used for
any other purpose while the pool element remains in existence. If the request cannot be
satisfied, then Allocate should propagate an exception (such as Storage_Error). If Allocate
behaves in any other manner, then the program execution is erroneous.
the new paragraphs:
Implementation Requirements
The Allocate procedure of a user-defined storage pool object P may be called by
the implementation only to allocate storage for a type T whose pool is P and:
- During the execution of an allocator of type T;
- During the execution of a return statement for a function whose result is
built-in-place in the result of an allocator of type T;
- During the execution of an assignment operation with a target of an allocated
object of type T with a part that has an unconstrained discriminated subtype with
defaults.
For one of the calls of Allocate described above, P (equivalent to T'Storage_Pool)
is passed as the Pool parameter. The Size_In_Storage_Elements parameter indicates the
number of storage elements to be allocated, and is no more than
D'Max_Size_In_Storage_Elements, where D is the designated subtype of T.
The Alignment parameter is D'Alignment if D is a specific type, and otherwise is
the alignment of the specific type identified by the tag of the object being
created. The result returned in the Storage_Address parameter is used as the
address of the allocated storage, which is a contiguous block of memory of
Size_In_Storage_Elements storage elements. Any exception propagated
by Allocate is propagated by the construct that contained the call.
The number of calls to Allocate needed to implement an allocator for any
particular type is unspecified. The number of calls to Deallocate
needed to implement an instance of Unchecked_Deallocation (see 13.11.2) for
any particular object is the same as the number of Allocate calls for that
object.
The Deallocate procedure of a user-defined storage pool object P may be called
by the implementation to deallocate storage for a type T whose pool is P
only at the places when an Allocate call is allowed for P, during the execution
of an instance of Unchecked_Deallocation for T, or as part of the finalization
of the collection of T. For such a call of Deallocate, P (equivalent to
T'Storage_Pool) is passed as the Pool parameter. The value of the Storage_Address
parameter for a call to Deallocate is the value returned in the Storage_Address parameter
of the corresponding successful call to Allocate. The values of the Size_In_Storage_Elements
and Alignment parameters are the same values passed to the corresponding Allocate call.
Any exception propagated by Deallocate is propagated by the construct that
contained the call.
!corrigendum 13.11.2(9/2)
Replace the paragraph:
- 3.
- Free(X), when X is not equal to null first performs finalization of
the object designated by X (and any coextensions of the object — see
3.10.2), as described in 7.6.1. It then deallocates the storage
occupied by the object designated by X (and any coextensions). If
the storage pool is a user-defined object, then the storage is
deallocated by calling Deallocate, passing
access_to_variable_subtype_name'Storage_Pool as the Pool parameter.
Storage_Address is the value returned in the Storage_Address parameter
of the corresponding Allocate call. Size_In_Storage_Elements and
Alignment are the same values passed to the corresponding Allocate
call. There is one exception: if the object being freed contains
tasks, the object might not be deallocated.
by:
- 3.
- Free(X), when X is not equal to null first performs finalization of
the object designated by X (and any coextensions of the object — see
3.10.2), as described in 7.6.1. It then deallocates the storage
occupied by the object designated by X (and any coextensions). If
the storage pool is a user-defined object, then the storage is
deallocated by calling Deallocate as described in 13.11.
There is one exception: if the object being freed contains
tasks, the object might not be deallocated.
!ACATS Test
Permissions are hard to usefully test, and the ACATS isn't supposed to be testing
implementation choices anyway. It might be possible to test that these things
don't happen in the wrong place -- but it's not clear that we can guess where
those wrong places are.
!appendix
From: Randy Brukardt
Sent: Thursday, August 7, 2008 9:16 PM
I've been working on this AI off-and-on for a month, and I hope I've been on the
right track. [This is version /01 of the AI - ED.]
The problem I've been struggling with was whether we need to describe the use
of these procedures in detail. I decided to do so, as it probably is easier
to remove the detail. And I was bothered that the other permitted calls would
have no description at all -- which doesn't seem right.
What I don't know is if I described something that is different than how
existing implementations do things. The intent here is to add permissions
to make calls in other places, not to force implementations to change
anything that they are doing (presuming it makes sense vis-a-vis the Standard).
So comments are welcome.
****************************************************************
From: Randy Brukardt
Added: Saturday, May 23, 2009
The minutes of the Tallahassee meeting suggested moving paragraphs 16-20
under Dynamic Semantics. I didn't do that because (1) we later decided
to move most of the new text to be Implementation Requirements, meaning this is
not a necessary change anymore; (2) paragraphs 17-19 define the storage pool of a
type, which can be construed to be a Static Semantics definition; (3) Actually doing
this in our document tools would require deleting and reinserting these paragraphs,
which is messy and would seem to imply more change than actually has occurred.
****************************************************************
Questions? Ask the ACAA Technical Agent