Version 1.6 of ai05s/ai05-0107-1.txt

Unformatted version of ai05s/ai05-0107-1.txt version 1.6
Other versions for file 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 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"); -- (1)
... Obj.all := (5, "ABCDE"); -- (2)
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:
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:
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