!standard 7.6.1(20) 08-08-07 AI05-0107-1/01 !standard 13.11(16) !standard 13.11(21) !standard 13.11.2(9/2) !class binding interpretation 08-08-07 !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 to call Deallocate the appropriate number of times to free the memory. The Allocate and Deallocate procedures of a storage pool can be implicitly called at 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 can 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 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. [Editor's note: How calls operate should be in dynamic semantics, and the rules need to apply to more than just allocators anyway, so I split them out.] Add after 13.11(21): Dynamic Semantics The Allocate procedure of a user-defined storage pool object P may only be called by the implementation to allocate storage for a type T whose pool is P and: * During the execution of an allocator of type T; * During the execution an aggregate that is built-in-place in the result 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 of an allocated object of type T with a part that has an unconstrained discriminated subtype with defaults. AARM Discussion: Of course, explicit calls to the procedure are also allowed and are not bound by any of the rules found here. AARM Reason: We allow Allocate to be called during build-in-place operations so that the allocation can be deferred until the size of the object is known. 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.) End AARM Reason. For one of the calls of Allocate described above, P (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. 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. AARM Reason: This supports objects that are allocated in one or more parts. The second sentence prevents extra or missing calls to Deallocate. [Editor's note: should the number of Allocate calls be implementation-defined instead? Also see the !discussion.] The Deallocate procedure of a user-defined storage pool object P may only be called by the implementation to deallocate storage for a type T whose pool is P and, at the places when an Allocate call is allowed for P or during the execution of an instance of Unchecked_Deallocation for T. For such a call of Deallocate, P (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 Allocate call. 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 they apply to all calls to Deallocate.] !discussion The definition of "built-in-place" is as defined in AI05-0067-1. The intent is that 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 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. Still, we could simplify the wording somewhat at the cost of more unusual cases potentially being allowed. The right trade-off is not completely clear. Here is some simpler wording: The Allocate procedure of a user-defined storage pool may only be called by the implementation: * During the execution of an allocator; * During the execution an aggregate that is built-in-place; * During the execution of a return statement for a function whose result is built-in-place; * During the execution of an assignment operation of an object with a part that has an unconstrained discriminated subtype. This drops three things that aren't really necessary: the specification of which pool we are talking about; the requirement for the object to be allocated in the other bullets, and the requirement for defaults on the unconstrained discriminated part. In the first case, it's not clear that there is any realistic chance of an implementation calling Allocate on other kinds of objects. In the second case, the only additional cases allowed would be top-level objects constrained by their initial value, which seems harmless. (Unconstrained discriminated components without defaults are indefinite and thus are illegal.) --- 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 rules). Also note that the rules for calling Deallocate are given in 13.11, while the existing wording gives those rules in 13.11.2. It seems weird to separate the rules which really are paired; and the definition of a storage pool shouldn't be widely separated so that a potential implementer of a pool can find all of the important rules in one place. The rules about the parameters to Deallocate needing to be the same as the Allocate call was moved from 13.11.2, as they apply equally to the deallocations associated with failed allocators and with reallocation on assignment. --- 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 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 convinient to the compiler. Surely that is how our Ada 83 compiler worked, 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. 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. My 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 I have to find a new 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. As such, I've written the rules to make it clear that this implementation is allowed. --!corrigendum 13.11(20) !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 ****************************************************************