Version 1.7 of ai05s/ai05-0111-3.txt

Unformatted version of ai05s/ai05-0111-3.txt version 1.7
Other versions for file ai05s/ai05-0111-3.txt

!standard 4.8(2) 11-01-15 AI05-0111-3/06
!standard 4.8(3/2)
!standard 4.8(10.3/2)
!standard 13.11(16/3)
!standard 13.11.4 (0)
!standard 13.11.5 (0)
!class Amendment 10-10-13
!status work item 10-10-13
!status received 10-10-13
!priority Medium
!difficulty Hard
!subject Subpools, allocators, and control of finalization

!summary

Subpools are added to Ada.

[Editor's note: The above is given to ensure John is happy during editorial review. :-)]

!problem

One often wants to manage dynamically allocated objects in multiple heaps with different lifetimes. Ada provides this automatically if things can be arranged so that all of the objects created with a given access type have the same lifetime. The finalization of the storage pool associated with the access type provides for the reclamation of the objects allocated using these access types. However, it is common for the access types to be declared at the library level, while there need to be multiple heaps that are reclaimed at a more nested level.

One possible way to support multiple heaps is to allow the subset of the storage pool for a dynamically allocated object to be specified explicitly at the point of the allocator. The subset can then be reclaimed at one time with a single deallocation call.

This is exactly as safe as reclaiming the objects one at a time with Unchecked_Deallocation (in that dangling pointers can be created). However, this approach adds flexiblity in storage management (as the memory can be reclaimed with a single operation), and can be used as a building block for safer allocations.

!proposal

Allow the storage pool associated with one or more access types to be split into multiple, separately reclaimable "subpools," and allow the particular subpool to be used for a given allocator to be specified at the point of the allocator, with the following syntax:

X := new (Subpool) T'(ABC);

The objects allocated from a subpool are reclaimed when Unchecked_Subpool_Deallocation is called. All of the objects in the subpool are finalized before the storage pool finalizes the storage.

!wording

Modify 4.8(2) as follows:

allocator ::= new [subpool_specification] subtype_indication | new [subpool_specification] qualified_expression

subpool_specification ::= '(' *subpool_handle*_name ')'

Add at the end of 4.8(3/1):

A subpool_handle_name is expected to be of any descendant of System.Storage_Pools.Subpools.Subpool_Handle, the type used to identify a subpool defined in the language-defined package System.Storage_Pools.Subpools (see 13.11.4).

Add after 4.8(10.3/2):

If the allocator includes a subpool_handle_name, the allocator raises Program_Error if the subpool is non-null and does not belong (see 13.11.4) to the storage pool of the access type of the allocator.

AARM Implementation Note: This can be implemented by comparing the result of Pool_of_Subpool to a reference to the storage pool object.

AARM Reason: This detects cases where the subpool belongs to another pool, or to no pool at all. This includes detecting dangling subpool handles so long as the subpool object (the object designated by the handle) still exists. (If the subpool object has been deallocated, execution is erroneous; it is likely that this check will still detect the problem, but there cannot be a guarentee.)

Add after 7.6.1(20):

Implementation Permissions

The implementation may finalize objects created by allocators for an access type whose storage pool supports subpools (see 13.11.4) as if the objects were created (in an arbitrary object) at the point where the storage pool was elaborated instead of the first freezing point of the access type.

AARM Ramification: This allows the finalization of such objects to occur later than they otherwise would, but still as part of the finalization of the same master.

AARM Implementation Note: This permission is intended to allow the allocated objects to "belong" to the subpool objects and to allow those objects to be finalized at the time that the storage pool is finalized (if they are not finalized earlier). This is expected to ease implementation, as the objects will only need to belong to the subpool and not also the collection.

Modify 13.11(16/3):

An allocator of type T {without a subpool_specification} 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. {An allocator with a subpool_specification allocates storage from the specified subpool of T's storage pool, by calling Allocate_From_Subpool as described in subclause 13.11.4.}

Add a new section:

13.11.4 Storage Subpools

This subclause defines a package to support the partitioning of a storage pool into subpools. A subpool may be specified as the default to be used for allocation from the associated storage pool, or a particular subpool may be specified as part of an allocator (see 4.8).

The following language-defined library package exists:

with System.Storage_Elements; package System.Storage_Pools.Subpools is pragma Preelaborated (System.Storage_Pools.Subpools);

type Root_Storage_Pool_with_Subpools is abstract new Root_Storage_Pool with private; -- An access type must have a storage pool of a type -- descended from this type to use subpools.

type Root_Subpool is abstract tagged limited private; -- The subpool object type. Objects of this type are managed by -- the storage pool; usually only the handles are exposed -- to clients.

type Subpool_Handle is access all Root_Subpool'Class; for Subpool_Handle'Storage_Size use 0; -- This provides a reference to a subpool, and serves to identify -- the subpool within the program.

function Create_Subpool(Pool : in out Root_Storage_Pool_with_Subpools; Storage_Size : Storage_Elements.Storage_Count := Storage_Elements.Storage_Count'Last) return not null Subpool_Handle is abstract; -- Create subpool within given storage pool manager. Storage_Size -- specifies a limit on the amount of storage for the subpool. -- NOTE: Additional functions that create subpools may be -- defined for a given storage pool that supports subpools. -- [Editor's Note: This uses AI05-0143-1 to allow an in out parameter; "access" -- could be used instead but would be less convenient.]

function Pool_of_Subpool(Subpool : not null Subpool_Handle) return access Root_Storage_Pool_with_Subpools'Class; -- Return access to underlying storage pool of given handle.

procedure Set_Pool_of_Subpool(Subpool : not null Subpool_Handle; To : in out Root_Storage_Pool_with_Subpools'Class); -- Set the Pool for a newly created subpool or a subpool which -- is being reused after a call to Deallocate_Subpool (this routine -- should only be used as part of the implementation of Create_Subpool -- or similar subpool constructors). -- Raises Program_Error if the Pool has already been set for Subpool -- since the last explicit finalization (if any) of the subpool.

procedure Allocate_From_Subpool( Pool : in out Root_Storage_Pool_with_Subpools; Storage_Address : out Address; Size_In_Storage_Elements : in Storage_Elements.Storage_Count; Alignment : in Storage_Elements.Storage_Count; Subpool : not null Subpool_Handle) is abstract with Pre'Class => Pool_of_Subpool(Subpool) = Pool'access; -- Allocate space from specified subpool. -- [Editor's note: The precondition is as described in AI05-0145-2 and -- AI05-0183-1. It could be omitted if necessary.]

procedure Deallocate_Subpool( Pool : in out Root_Storage_Pool_with_Subpools; Subpool : in out Subpool_Handle) is abstract with Pre'Class => Pool_of_Subpool(Subpool) = Pool'access; -- Deallocate the space for all of the objects allocated from the -- specified subpool, and destroy the subpool. The subpool handle -- is set to null after this call.

function Default_Subpool_for_Pool( Pool : in Root_Storage_Pool_with_Subpools) return not null Subpool_Handle; -- Returns a handle of the default subpool for Pool. -- Note: If no default subpool is supported, this routine should -- raise Storage_Error.

private ... -- not specified by the language

end System.Storage_Pools.Subpools;

A subpool is a separately reclaimable portion of a storage pool, identified by an object of type Subpool_Handle (a subpool handle). A subpool handle also identifies the enclosing storage pool, a storage pool that supports subpools, which is a storage pool whose type is descended from Root_Storage_Pool_with_Subpools. When an allocator for a type whose storage pool supports subpools is evaluated, a call is made on Allocate_From_Subpool passing in a Subpool_Handle, in addition to the parameters as defined for calls on Allocate (see 13.11). The subpool handle is the one given in the allocator if a subpool_handle_name is specified, or otherwise the handle obtained by calling Default_Subpool_for_Pool on the pool of the type of the allocator. All requirements on the Allocate procedure also apply to Allocate_from_Subpool.

Legality Rules

If a storage pool that supports subpools is specified as the Storage_Pool for an access type, the access type is called a subpool access type. A subpool access type shall be a pool-specific access type.

The accessibility level of the subpool access type shall not be statically deeper than that of the storage pool object.

Dynamic Semantics

When a subpool access type is frozen (see 13.14), a check is made that the accessibility level of the subpool access type is not deeper than that of the storage pool object. Program_Error is raised if this check fails.

AARM Reason: This check (and its static counterpart) ensures that the type of the allocated objects exist at least as long as the storage pool object, so that the subpools are finalized (which finalizes any remaining allocated objects) before the type of the objects cease to exist. The access type itself will cease to exist before the storage pool.

13.11.5 Subpool Reclamation

The following language-defined library procedure exists:

procedure Ada.Unchecked_Deallocate_Subpool

(Subpool : in out System.Storage_Pools.Subpools.Subpool_Handle);

A subpool may be explicitly deallocated using Unchecked_Deallocate_Subpool.

If Subpool is null, a call on Unchecked_Deallocate_Subpool has no effect. Otherwise, a call on Unchecked_Deallocate_Subpool has the following effects:

* Any task allocated from the subpool designated by Subpool that is

waiting at an open terminate alternative and having all of its subtasks (if any) either completed or similarly waiting at an open terminate alternative, is completed;

* Next, the call waits for any completed tasks allocated from that subpool

(including ones completed by the previous bullet) to complete their finalization;

* Then any of the objects allocated from the subpool that still exist

are finalized in an arbitrary order;

* Now, the following Redundant[dispatching] call is made

System.Storage_Pools.Subpools.Deallocate_Subpool (

System.Storage_Pools.Subpools.Pool_of_Subpool(Subpool).all, Subpool);

* Finally, Subpool is set to null.

It is a bounded error if there are any tasks allocated from the subpool that are not terminated when the call to Deallocate_Subpool is made. The possible effects are as given for the unchecked deallocation of an object with a task part (see 13.11.2).

Example

Here is a simple but complete implementation of the classic Mark/Release pool using subpools:

with System.Storage_Pools.Subpools; with Ada.Unchecked_Deallocate_Subpool; package MR_Pool is

-- Mark and Release work in a stack fashion, and allocations are not allowed -- from a subpool other than the one at the top of the stack. This is also -- the default pool.

subtype Subpool_Handle is System.Storage_Pools.Subpools.Subpool_Handle;

type Mark_Release_Pool_Type (Pool_Size : System.Storage_Elements.Storage_Count) is new System.Storage_Pools.Subpools.Root_Storage_Pool_with_Subpools with private;

function Mark (Pool : in out Mark_Release_Pool_Type; Storage_Size : System.Storage_Elements.Storage_Count := System.Storage_Elements.Storage_Count'Last) return not null Subpool_Handle;

procedure Release (Subpool : in out Subpool_Handle) renames Ada.Unchecked_Deallocate_Subpool;

private

type MR_Subpool is new System.Storage_Pools.Subpools.Root_Subpool with record Start : System.Storage_Elements.Storage_Count; end record; subtype Subpool_Indexes is Positive range 1 .. 10; type Subpool_Array is array (Subpool_Indexes) of aliased MR_Subpool;

type Mark_Release_Pool_Type (Pool_Size : System.Storage_Elements.Storage_Count) is new System.Storage_Pools.Subpools.Root_Storage_Pool_with_Subpools with record Storage : System.Storage_Elements.Storage_Array (1..Pool_Size); Next_Allocation : System.Storage_Elements.Storage_Count := 1; Markers : Subpool_Array; Current_Pool : Subpool_Indexes := 1; end record;

overriding function Create_Subpool (Pool : aliased in out Mark_Release_Pool_Type; Storage_Size : System.Storage_Elements.Storage_Count := System.Storage_Elements.Storage_Count'Last) return not null Subpool_Handle;

overriding procedure Allocate_From_Subpool ( Pool : in out Mark_Release_Pool_Type; Storage_Address : out System.Address; Size_In_Storage_Elements : in System.Storage_Elements.Storage_Count; Alignment : in System.Storage_Elements.Storage_Count; Subpool : not null Subpool_Handle);

overriding procedure Deallocate_Subpool ( Pool : in out Mark_Release_Pool_Type; Subpool : in out Subpool_Handle);

overriding function Default_Subpool_for_Pool ( Pool : in Mark_Release_Pool_Type) return not null Subpool_Handle;

overriding procedure Allocate ( Pool : in out Mark_Release_Pool_Type; Storage_Address : out System.Address; Size_In_Storage_Elements : in System.Storage_Elements.Storage_Count; Alignment : in System.Storage_Elements.Storage_Count);

overriding procedure Deallocate ( Pool : in out Mark_Release_Pool_Type; Storage_Address : in System.Address; Size_In_Storage_Elements : in System.Storage_Elements.Storage_Count; Alignment : in System.Storage_Elements.Storage_Count);

overriding function Storage_Size (Pool : Mark_Release_Pool_Type) return System.Storage_Elements.Storage_Count;

overriding procedure Initialize (Pool : in out Mark_Release_Pool_Type);

-- We don't need Finalize.

end MR_Pool;

package body MR_Pool is

procedure Initialize (Pool : in out Mark_Release_Pool_Type) is -- Initialize the first default subpool. begin Pool.Markers(1).Start := 1; System.Storage_Pools.Subpools.Set_Pool_for_Subpool (Pool.Markers(1)'Unchecked_Access, Pool'Unchecked_Access); end Initialize;

function Create_Subpool (Pool : in out Mark_Release_Pool_Type; Storage_Size : System.Storage_Elements.Storage_Count := System.Storage_Elements.Storage_Count'Last) return not null Subpool_Handle is -- Mark the current allocation location. begin if Pool.Current_Pool = Subpool_Indexes'Last then raise Storage_Error; -- No more subpools. end if; Pool.Current_Pool := Pool.Current_Pool + 1; -- More to the next subpool Pool.Markers(Pool.Current_Pool).Start := Pool.Next_Allocation; System.Storage_Pools.Subpools.Set_Pool_for_Subpool (Pool.Markers(Pool.Current_Pool)'Unchecked_Access, Pool'Unchecked_Access); return Pool(Pool.Current_Pool).Markers'Unchecked_Access; end Create_Subpool;

procedure Deallocate_Subpool ( Pool : in out Mark_Release_Pool_Type; Subpool : in out Subpool_Handle) is begin if Subpool /= Pool(Pool.Current_Pool).Markers'Unchecked_Access then raise Program_Error; -- Only the last marked subpool can be released. end if; if Pool.Current_Pool /= 1 then Pool.Next_Allocation := Pool.Markers(Pool.Current_Pool); Pool.Current_Pool := Pool.Current_Pool - 1; -- More to the previous subpool else -- Reinitialize the default subpool: Pool.Next_Allocation := 1; System.Storage_Pools.Subpools.Set_Pool_for_Subpool (Pool.Markers(1)'Unchecked_Access, Pool'Unchecked_Access); end if; end Deallocate_Subpool;

function Default_Subpool_for_Pool ( Pool : in Mark_Release_Pool_Type) return not null Subpool_Handle is begin return Pool(Pool.Current_Pool).Markers'Unchecked_Access; end Default_Subpool_for_Pool;

procedure Allocate_From_Subpool ( Pool : in out Mark_Release_Pool_Type; Storage_Address : out System.Address; Size_In_Storage_Elements : in System.Storage_Elements.Storage_Count; Alignment : in Storage_Elements.Storage_Count; Subpool : not null Subpool_Handle) is begin if Subpool /= Pool(Pool.Current_Pool).Markers'Unchecked_Access then raise Program_Error; -- Only the last marked subpool can be used for allocations. end if; Allocate (Pool, Storage_Address, Size_In_Storage_Elements, Alignment); end Allocate_From_Subpool;

procedure Allocate ( Pool : in out Mark_Release_Pool_Type; Storage_Address : out System.Address; Size_In_Storage_Elements : in System.Storage_Elements.Storage_Count; Alignment : in System.Storage_Elements.Storage_Count) is -- Allocate from the default subpool: begin -- Correct the alignment if necessary: Pool.Next_Allocation := Pool.Next_Allocation + ((-Pool.Next_Allocation) mod Alignment); if Pool.Next_Allocation + Size_In_Storage_Elements > Pool.Pool_Size then raise Storage_Error; -- Out of space. end if; Storage_Address := Pool.Storage (Pool.Next_Allocation)'Address; Pool.Next_Allocation := Pool.Next_Allocation + Size_In_Storage_Elements; end Allocate;

procedure Deallocate ( Pool : in out Mark_Release_Pool_Type; Storage_Address : in System.Address; Size_In_Storage_Elements : in System.Storage_Elements.Storage_Count; Alignment : in System.Storage_Elements.Storage_Count) is begin -- No deallocation other than from Release, so do nothing here. null; end Deallocate;

function Storage_Size (Pool : Mark_Release_Pool_Type) return System.Storage_Elements.Storage_Count is begin return Pool.Pool_Size; end Storage_Size;

end MR_Pool;

[End 13.11.5.]

Update the existing pool example to depend on package MR_Pool as defined above:

Modify 13.11(38):

As usual, a derivative of Root_Storage_Pool may define additional operations. For example, [presuming that]{consider the} Mark_Release_Pool_Type {defined in 13.11.5, that} has two additional operations, Mark and Release, the following is a possible use:

Delete the Block_Size discriminant from 13.11(39/1), and add a comment "As defined in 13.11.5".

Delete the Block_Size discriminant from 13.11(41), and add after it: My_Mark : MR_Pool.Subpool_Handle; -- See 13.11.5

Replace 13.11(43):

My_Mark := Mark(MR_Pool); ... -- Allocate objects using "new (My_Mark) Designated(...)" Release(My_Mark);

!discussion

The implementor of the storage pool type is supposed to worry about actually managing the storage and keeping track of which storage has been allocated to which subpools. The subpool object type can also be extended. So the implementor of the storage pool can keep some information in a per-subpool data structure (by extending Root_Subpool), and some globally for the overall storage pool (by extending Root_Storage_Pool_with_Subpools).

Meanwhile, the "root part" of the subpool object type will be used by the Ada implementation to implement task dependence and finalization for the subpools, as well as managing the connection between subpools and their parent pool. (The Ada implementation may also use the "root part" of the storage pool for this purpose.)

Note that the intention is that the actual subpool object (as opposed to the handle) is an extension created in the body of the package that defines the storage pool, and is not exposed to the clients of the storage pool. Moreover, subpool objects are expected to logically belong to the storage pool; if the storage pool is finalized, any remaining subpools are also finalized.

The only extra requirement on the programmer of a storage pool that supports subpools is that the actual subpool object is passed to a call of Set_Pool_for_Subpool before it is used. (If this is not done, any allocator on that subpool handle will raise Program_Error.) The implementation may use this routine to initialize the data structures it uses to handle finalization and task dependence. Note that the routine can be used to reuse a subpool object after the object is explicitly finalized and the associated storage freed. This allows the use of statically allocated subpool objects (as in the example below).

DANGLING SUBPOOL HANDLES

It is possible for the designated object of a subpool handle to cease to exist, for instance because it was destroyed by a call to an instance of Unchecked_Deallocation. We don't need special rules to handle these cases, as a subpool handle is a normal Ada access type, and the implementation of the pool is written by some programmer in Ada. Thus the existing rules for access types cover all needed rules.

However, those rules just mean that execution may become erroneous. To help prevent that, we've taken several measures:

* We null the provided subpool handle when calling Unchecked_Deallocate_Subpool

to minimize the cases of dangling subpool handles.

* We make a check on the provided subpool handle in an allocator that it

actually belongs to the appropriate pool. If it does not, Program_Error is raised. This check will catch all cases of dangling subpool handles when the designated subpool object still exists, and will catch a large percentage in practice even when the object was deallocated (as it is unlikely that a reused object will have a pointer at the right pool in the right place).

task TERMINATION MODEL

The basic model of task termination is unaltered; the tasks allocated from a subpool belong to the master of the access type. This works because of the accessibility check on the pool object - the pool object has to be in the same scope as the access type. Moreover, all tasks for a given scope terminate together, so it isn't possible to differentiate between them "belonging" to the pool object or the access type.

Unchecked_Deallocation has no effect on task termination. This means that server tasks embedded in a deallocated object may continue to wait at terminate alternatives, even though they are no longer accessible. It is felt that it is not a hardship for the client to call a 'shutdown' routine before deallocating them (although such a requirement damages encapsulation).

However, this model does not work for subpools. In order to call a shutdown entry on each object, it would be necessary to enumerate all of the contained objects (or at least those that need a shutdown routine called). That would defeat the purpose of subpools (which is to support a mass deallocation of all of the related objects without having to enumerate them).

Therefore, we adopt rules that have tasks allocated from a subpool that are waiting at a terminate alternative (with the same requirements as 9.3(3-6)) become completed, and then the finalization of all completed tasks is waited for. This means that it is safe to deallocate a subpool containing tasks -- even if those tasks have discriminants -- so long as the tasks are completed. For other tasks, this is a bounded error as it is for Unchecked_Deallocation.

We considered adopting this rule for Unchecked_Deallocation as well, as it would reduce the cases of bounded errors and the associated bugs. Unfortunately, it could be inconsistent with the behavior of Ada 95 and Ada 2005 programs, as the finalization could take a long time or even block. In extreme cases, deadlock is possible. That seems like too much of an inconsistency to allow, so we do not change the behavior of Unchecked_Deallocation.

FINALIZATION MODEL

The model used here is that subpools are really part of the pool object; they are finalized when the pool is finalized. The subpool objects may be created directly as part of the pool object, or may be separately allocated and managed by the pool.

Objects allocated into a subpool will be finalized when the subpool is explicitly deallocated. If that never happens, the objects can be finalized in the normal place for the access type, or the implementation can finalize them when the entire pool is finalized.

Since the objects allocated into a subpool may be finalized before or after the associated access type(s), we have to take care that the objects are not finalized after their (sub)type ceases to exist. Note that the important (sub)type is the designated type (that is the type of the allocated objects), not the access type. Even so, the easiest way to make this check is to require that the access type is not deeper than the pool.

Alternatives

This accessibility check does put restrictions on the location of access types that use subpools. We considered doing without the check by adding an additional runtime rule that the finalization of a collection for an access type also finalizes any objects allocated from a subpool for that access type. (Along with a similar rule for task dependence.)

This eliminates the static restrictions and would allow subpools to be used on access types with nested designated types and the like.

However, the implementation would be complex. An obvious implementation would put subpool allocated objects on both a chain for the collection and a chain for the subpool (removing it from both when it is finalized). However, this would appear to have a distributed space overhead, as there would need to be links to put an object on two lists for any controlled type that could be allocated (which would seem to be any such type), as well as a small distributed time overhead to initialize the second set of pointers and to remove the object from the second list when it is finalized.

However, it is possible to do better (with some complexity). If the subpool keeps a separate finalization list for each access type, then only the subpool need be put on the access type's collection list. This would complicate finalization somewhat, but only when subpools are used. This would require some unique way to identify the access type to the subpool; this could be done by assigning at elaboration time a unique serial number to each access type that uses a storage pool that supports subpools.

Similar implementation complexity would also apply to task dependence. Because of this complexity, we chose the simpler model.

The other alternative would be to decouple subpools from the underlying pool. The subpool could be required to have a shorter lifetime than the access type (or the designated type), which eliminates the finalization problem. However, it makes dangling subpool handles much more likely. That could be solved with reference counting -- but of course that brings us back to the more complex proposal of AI05-0111-2. So this option was rejected.

USE AS A BUILDING BLOCK

This package provides facilities that can be used to provide safer abstractions.

One possibility would be to wrap the subpool handle in a controlled object that managed reference counting. When the count reached zero, the subpool would be automatically deallocated. This is basically the idea of AI05-0111-2 (without the checks on the contained pointers).

One could even imagine going further, by wrapping the access type in a similar reference counted record, with an indication of the containing pool. Checks could be done at assignments and uses to prevent dangling pointers.

Creative use of the reference aspect (see AI05-139-2) could make these wrappers easy to use. Unfortunately, the wrappers themselves can't have a reference aspect, as the required access discriminant would prevent useful assignments. But a helper function and object could do the job safely.

!example

See the example given in the !wording.

---

Another way that subpools can be used is to partition data. Imagine a long-running web server for a retail establishment, which builds up in-memory representations of historical customer information, current product information, and each active customer's current shopping cart. There is a desire to be able to reclaim this in-memory information when it has not been recently referenced. However, the various representations are interlinked, such that a shopping cart refers to the in-memory representation for the products it contains, and the historical customer information and the current shopping cart might refer to each other.

Although these representations might be made up of multiple heap objects, linked into hash tables, sets, lists, trees, etc., reclamation generally happens at the unit of an entire customer history, shopping cart, or product description, so there is a desire to avoid individual object-by-object deallocation. Hence, we would establish a separate subpool for each separately reclaimable item, namely one for each customer historical record, one for each product description, and one for each shopping cart.

!ACATS test

Create ACATS C-Tests to test this facility.

!ASIS

Some new ASIS routine needs to be added to handle the subpool syntax for allocators.

Details TBD. ***

!appendix


From: Randy Brukardt
Sent: Tuesday, October 19, 2010  5:48 PM

I've posted my "simple as possible but no simpler" subpool proposal as
AI05-0111-3. It can be found in the normal place:

http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai05s/ai05-0111-3.txt

[This was version /02 of the AI - Editor.]

Steve has suggested that there are some problems with the model (which is
almost certain when Steve reviews any proposal!), but it is clear to me that
I'm not going to have time to work on this further before the meeting, so I am
posting it now so everyone can have a chance to review it before the meeting.

I've included a complete example of how the subpools can be used to create a
simple mark/release pool. The example should compile and run unmodified on an
Ada 2012 compiler; it includes the allocation code as well as the subpools.

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

From: Tucker Taft
Sent: Monday, October 25, 2010  3:35 PM

I don't have the time or energy to update the version of ai05-0111 I had been
working on before.  I suggest we use Randy's proposal as a new starting point,
and see if we can get it to be acceptable to the group.

I'll spend some time reviewing it in detail before the meeting, and I see Steve
has already weighed in on it. Others interested in this functionality, I
encourage you also to look at this proposal in advance.

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

From: Brad Moore
Sent: Friday, October 29, 2010  7:17 PM

Looks really good!
Much easier to understand than other versions.

I have a few comments.


1) 4.8(10.3/2) AARM Reason: "it is likely that
   this check will still detect the problem,"

"Likely" seems a bit strong here, as it implies that most vendors will implement
this, when that remains to be seen. I suggest replacing "likely" with
"possibly".

2) I am just raising the question whether it makes sense to have the package
   Subpools as a child of Storage_Pools? I think I prefer it the way it is
   currently, but it is probably good to at least ask the question.

3) Can the Subpools package be Preelaborated? Storage_Pools is, so it seems a
   bit odd that Storage_Pools isn't.

4) Set_Pool_of_Subpool spec comments.
    "which be being reused"

5) In the example, I think it would be nice if the overriding indicator were
   used where appropriate.

6) In the example, I presume the package is designed to allow further
   derivations. If it were desired that this be a final derivation in a class
   hierarchy, then the calls Allocate_From_Subpoop, Deallocate_Subpool,
   Allocate, and Deallocate, could be moved into the private section, to hide
   those details from the client, thus providing a simpler interface. If this is
   a possibility, perhaps it would improve the example if this were done.

7) In the problem section it mentions that this package could be used as a
   building block to create safer allocations, though the current package allows
   for dangling references. It would be helpful to add a few sentences to
   provide this vision to suggest how such safer storage pools might be created.


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

From: Randy Brukardt
Sent: Saturday, October 30, 2010  9:54 PM

>    1) 4.8(10.3/2) AARM Reason: "it is likely that
>       this check will still detect the problem,"
>
>    "Likely" seems a bit strong here, as it implies that most vendors
> will implement this, when that remains to be seen. I suggest replacing
> "likely" with "possibly".

We certainly assume an Ada 2012 implementation in the Ada 2012 standard. And
this check is not optional. So I think I stand by my original comment (I might
have misunderstood your concern, however).

...
>  6) In the example, I presume the package is designed to allow further derivations.
>     If it were desired that this be a final derivation in a class hierarchy, then
>     the calls Allocate_From_Subpoop, Deallocate_Subpool, Allocate, and
>     Deallocate, could be moved into the private section, to hide those details from
>     the client, thus providing a simpler interface. If this is a possibility, perhaps it
>     would improve the example if this were done.

Tucker suggested something on this line. I'll try to do that.

>    7) In the problem section it mentions that this package could be used as a building
>       block to create safer allocations, though the current package allows for dangling
>       references. It would be helpful to add a few sentences to provide this vision to
>       suggest how such safer storage pools might be created.

OK.

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

From: Randy Brukardt
Sent: Saturday, October 30, 2010  11:11 PM

Attached find the /04 update for the subpool proposal.

I made the changes requested by Brad and by the ARG discussion, except for 2:

I didn't follow Bob's two subtype proposal because it would complicate the use
for users; I used direct "not null" instead.

I didn't follow Tucker's fully private example suggestion, because that would
make the type not a storage pool to clients, meaning they couldn't use it to
specify 'Storage_Pool, making it useless. I was able to do the rest of the
rearranging, so I think it is better separated into client and implementation
parts.

I also did the following three changes:


Added a Default_Subpool_for_Pool routine. Otherwise, the implementation would
not know what subpool to use as the master for the allocated objects. That would
be bad.

Also reworded Unchecked_Subpool_Deallocate to handle the null subpool case
(can't use not null there as the handle is nulled out by this call).

Also noticed missing System prefixes in the example.

Finally, added discussion of possible safer ways to use this, as requested by
Brad. It's in the discussion, not the problem.

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

From: Robert Dewar
Sent: Monday, November 8, 2010  3:19 AM

> 1) 4.8(10.3/2) AARM Reason: "it is likely that this check will still
> detect the problem,"
> "Likely" seems a bit strong here, as it implies that most vendors will
> implement this, when that remains to be seen. I suggest replacing
> "likely" with "possibly".

I would keep likely, the immediate issue is really whether GNAT implements
this or not, so just get the answer to that question!

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

From: Randy Brukardt
Sent: Monday, November 8, 2010  5:51 PM

Bob said at the meeting that he wants to implement it in GNAT whether or not it
gets standardized. That's a pretty strong endorsement!

Anyway, this was the one place where I didn't understand Brad's comment and did
not act on it in the next draft (written Saturday night and discussed on Sunday
at the meeting). None of this is interesting if it isn't implemented, and this
note is discussing a runtime check on a subpool handle. If there aren't any
subpool handles, there surely isn't any check (and if there are, there surely is
a check, it's easy to implement and an allocator that fails the check is
nonsense), so I don't understand what the relevance of implementation is.

Some background. This AARM note is applied to the runtime check that a subpool
handle represents a subpool of the pool of the access type being allocated. The
allocator would be nonsense if it was allocating objects from some other *pool*
than the one defined for the type. Thus there is a runtime check (all subpool
handles being equivalent as far as the Ada implementation is concerned).

The AARM note is discussing the issue of allocating from a "dangling" subpool
handle; that is, a subpool handle for a subpool that has already been
deallocated. It was intended to note that this pool check will also "likely"
detect a dangling subpool handle.

Whether the check can detect a dangling subpool handle depends on the
implementation of the pool (something totally under the control of the pool
implementor, not the Ada implementer). When a subpool is deallocated, the Ada
implementation is required to sever the connection between the subpool and the
pool, thus the check will automatically fail for a dangling subpool so long as
the subpool object still exists. (This is easily implemented by simply setting
the connection to null.) Therefore, the check will always detect dangling
handles if the subpool objects are statically part of the pool object (as in the
example in the AI). However, if the subpool objects are themselves deallocated
when the subpool is deallocated, then the subpool handle is really dangling in
an Ada sense and the check is technically doing something erroneous. (That's OK,
because the use of the subpool handle as an allocator is also erroneous in that
case, so there is no additional erroneousness created by the check.) Still, the
check is likely to detect a problem, as the implementation will have broken the
connection before the memory was deallocated. Thus, practically, the check would
only pass (that is, fail to detect the error) if the same memory was allocated
as another subpool object for the same pool before the check is made. If it is
allocated to some other kind of entity, it is highly unlikely that it would have
the right memory contents for the check to pass.

This is too much explanation for an AARM note. It's probably even too much
explanation for the !discussion section of the AI; but it is just right in the
!appendix, which is why I just spent 10 minutes writing it up.

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

From: Bob Duff
Sent: Monday, November 8, 2010  6:00 PM

Thank you.  Good explanation.  So "likely" is correct.

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

From: Tucker Taft
Sent: Monday, November 8, 2010  6:11 PM

Your discussion makes sense to me.
The run-time check for whether the
subpool is from the right pool is not optional.
The "likeliness" issue is merely based on the vagaries of reusing storage, etc.,
and as Randy points out, is in (partial) control of the subpool implementor, not
the Ada implementor.

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

Following a a summary of a private conversation in November 2010 about the
termination semantics of subpool deallocation.

Randy Brukardt:

Let me remind you where we are.

The big change to the AI that we decided on was to drop all of the master stuff
from the AI.

(The following discussion will ignore Unchecked_Deallocate_Subpool; I'll get to
that in a moment...)

This works because all of the tasks and controlled objects allocated for an
access type will "belong" to the master of the scope in which the access type is
declared. Because of the accessibility check on a storage pool, this is the same
master as that of the storage pool. Therefore, any tasks and controlled objects
allocated from subpools will "belong" to the same master whether they are
implemented as belonging to the subpool object or whether they are implemented
as belonging to the access type.

For tasks, the ordering of the elaboration of the entities is irrelevant; all
tasks "belonging" to a master are awaited at once. So we need do nothing special
for this case.

For controlled objects, they are finalized in the reverse order of their
elaboration. The collections of the access types are deemed to have elaborated
at the freezing point of the type. The storage pool object is finalized at the
point of its elaboration (which necessarily must be before the freezing point of
the access type; therefore it must finalize later). As noted previously, these
both have to be as part of the same master.

In order to allow the controlled objects to finalize with the storage pool
rather than the access type's collection, we add the following Implementation
Permission (added after 7.61(20)):

The implementation may finalize objects created by allocators for an access type
whose storage pool supports subpools (see 13.11.4) as if the objects were
created (in an arbitrary object) at the point where the storage pool was
elaborated rather instead of the first freezing point of the access type.

AARM Ramification: This allows the finalization of such objects to occur later
than they otherwise would, but still as part of the finalization of the same
master.

AARM Implementation Note: This permission is intended to allow the allocated
objects to "belong" to the subpool objects and to allow those objects to be
finalized at the time that the storage pool is finalized (if they are not
finalized earlier).

==============

The above is the easy part. The other issue is any special termination semantics
for tasks in for Unchecked_Deallocate_Subpool. Let me start with some Bairdian
free association.

(1) Steve was worried about nested tasks of a task that is waiting on a
    terminate alternative. These are not a (language) problem (or no more so
    than they are in other Ada code). The selection of a terminate alternative
    makes a task immediately completed (NOT terminated). After the task is
    completed (whether by the selection of a terminate alternative or simply by
    reaching the end of the code), task waiting and other finalizations proceeds
    normally.

(2) Because tasks that are waiting on a terminate alternative have to wait on
    tasks and finalize, they can take arbitrarily long to actually terminate. Of
    course, this is under control of the user; they don't have to write nested
    tasks and finalization that blocks. ;-)

(3) It seems to me that if we are going to do something special for
    Unchecked_Deallocate_Subpool, we ought to consider doing the same for
    Unchecked_Deallocation. After all, these are essentially the same. Moreover,
    in both cases, access to the tasks from outside of themselves is erroneous
    (it has to be accomplished through a dangling pointer), so there can be no
    correct code that depends on such tasks continuing to wait and/or run.

(4) A task that is completed is essentially in the same state as one waiting on
    a terminate alternative (in that both have to complete finalization before
    terminating), other than the former is not waiting. Depending on the purpose
    of the rule, we may want to include completed tasks in it. Specifically, if
    the purpose is to allow implementations to free task memory sooner, then the
    same rule ought to be applied to both. (I admit I don't know what the
    purpose of this rule is, other than to make allocated tasks work more like
    you would expect.)

(5) I wonder if we need some sort of bounded error for all non-terminated tasks
    in subpools. That's because in the case of subpools, there is no way to
    suppress the deallocation of memory (doing it for the entire subpool would
    prevent the memory from getting freed until the pool goes away -- uggh). Or
    are we requiring that tasks are allocated independently of any other
    allocated memory? That seems limiting (especially as it means that tasks
    never get freed at all -- at least not until their master goes away). I
    recall a number of "bug" reports on this for Janus/Ada 83; I had to explain
    to people that the tasks continue to exist until the master goes away, and
    on 640K MS-DOS, you could run out of space for TCB's in a hurry. One hopes
    that we are not continuing that mistake...

OK, enough free association. Here's the latest version of the rule that Tucker
has proposed; this would appear in the Unchecked_Deallocate_Subpool text (I've
left the original Tucker text as alone as possible):

Otherwise, a call on Unchecked_Deallocate_Subpool causes following actions on
the subpool designated by Subpool:

* Any tasks allocated from the subpool that are waiting at an open terminate
  alternative are completed, then waiting for their termination;

* Then any of the objects allocated from the subpool that still exist are
  finalized in an arbitrary order;

* Finally, Subpool is set to null.

The first thing that strikes me about this rule is that it waits for the
termination (read finalization) of any tasks with open terminate alternatives.
But it *doesn't* wait for any tasks that are already completed but have not yet
finished their finalization. I don't see any good reason for the difference.
Either not waiting for finalization is harmless, in which case neither ought to
do that; or it *does* eliminate problems, in which case both ought to do it. I
don't see any justification for a difference. Thus I suggest replacing the above
by:

Otherwise, a call on Unchecked_Deallocate_Subpool causes following actions on
the subpool designated by Subpool:

* Any tasks allocated from the subpool that are waiting at an open terminate
  alternative are completed;

* Next, the call waits for any completed tasks (including ones completed by the
  previous bullet) to complete their finalization;

* Then any of the objects allocated from the subpool that still exist are
  finalized in an arbitrary order;

* Finally, Subpool is set to null.

(If we decide to never wait, the second bullet can just be deleted.) I think I'm
in favor of waiting, because it definitely would reduce the bounded error
possibilities (the bounded error occurs when a nonterminated task with
discriminants is deallocated), and would allow the task storage to be freed in
more cases.

The question of whether to change the rules for Unchecked_Deallocation also come
up here. Waiting definitely would be an execution inconsistency (although almost
exclusively in terms of time). Making server tasks complete would also be
inconsistent, but only to the extent that the task's finalization does something
"interesting"; the interesting thing would happen earlier than it does now.

Either way, the main advantage to this rule would be to allow allocated server
tasks to shut down once they no longer can be accessed. That seems to be an
important thing to allow no matter how the tasks are deallocated. Waiting for
them to finalize is secondary and seems less important.

One could argue that for Unchecked_Deallocation, it would be easy enough to wait
for a task to terminate before freeing it (just write a loop on termination),
and it also would be easy enough to add a shutdown entry to call before
deallocating an object containing a task. That seems true, but it also seems to
mess up designs.

Also note that using the same semantics for both would make it easier to convert
from single deallocations to the use of a subpool or vice versa (much less
likely for there to be trouble).

Finally, it is clear that not having any termination semantics for subpools
would make it hard to deallocate memory. We seem to need something.

Summarizing the questions:

(1) What is the purpose of special rules for task termination?

(2) Do the special rules apply to both Unchecked_Deallocation and
    Unchecked_Deallocate_Subpool, or just the latter?

(3) Do the special rules apply to completed but not yet terminated tasks? To
    tasks waiting on a terminate alternative? To already terminated tasks?

(4) Do the special rules involve waiting for the completion of the finalization
    of the tasks (that is, the termination of the tasks)?

---

Tucker Taft:

One of the original goals was to support a mark/release approach to memory
management that properly handled finalization.  Clearly task waiting is tied up
with finalization, so I am reluctant to ignore the problem just because
Unchecked_Deallocation did so. With Unchecked_Deallocation, you are freeing just
one object, so it is feasible to do some amount of checking of the state, etc.,
if there might be an embedded task involved.  When freeing a whole subpool, that
isn't very practical.

So I don't feel a strong need to make these two kinds of deallocation consistent
as far as task waiting.

Another thing to mention is that the rules in 9.3(6-9) require that the tasks
not only be waiting at a terminate alternative, but that they be dependent on a
completed master all of whose dependents are either terminated or waiting on a
terminate alternative.  That means there can't be any subtasks that will need to
be awaited -- all that remains is finalization for the tasks waiting at
terminate alternatives.

So I think I would suggest we try to match the requirements of 9.3(6-9) in
AI05-0111-3.  Here are the current bullets from 111:

   * Any tasks allocated from the subpool desigated by Subpool that are
   waiting at an open terminate alternative are completed (see 9.2);

   * Next, the call waits for any completed tasks allocated from that subpool
   (including ones completed by the previous bullet) to complete their
   finalization;

   * Then any of the objects allocated from the subpool that still exist
   are finalized in an arbitrary order;

I would suggest the following:

   * Any task allocated from the subpool designated by Subpool that is
   waiting at an open terminate alternative and having all of its subtasks
   (if any) either completed or similarly waiting at an open terminate
   alternative, is completed;

   * Next, the call waits for any completed tasks allocated from that subpool
   (including ones completed by the previous bullet) to complete their
   finalization;

   * Then any of the objects allocated from the subpool that still exist
   are finalized in an arbitrary order;

  It is a bounded error if there are any tasks allocated from the subpool
  that are not terminated at this point (with the same bounds as
  for Unchecked_Deallocation).

This is actually pretty consistent with Unchecked_Deallocation, in that it only
waits for finalization to complete.  It doesn't wait for a task to complete that
isn't already "ready" to complete.  In practice, presumably you would throw in a
"delay 1.0" or something before doing an Unchecked_Deallocate_Subpool if there
were tasks involved, to give them a chance to reach their terminate
alternatives.  The nice thing is it allows terminate alternatives to "work" for
such tasks, which Unchecked_Deallocation doesn't allow.  But again, with
individual Unchecked_Deallocation, you could pretty easily call some "Shut_Down"
entry of the task before deallocating it.

---

Randy Brukardt:

> One of the original goals was to support a mark/release approach to
> memory management that properly handled finalization.  Clearly task
> waiting is tied up with finalization, so I am reluctant to ignore the
> problem just because Unchecked_Deallocation did so.
> With Unchecked_Deallocation, you are freeing just one object, so it is
> feasible to do some amount of checking of the state, etc., if there
> might be an embedded task involved.  When freeing a whole subpool,
> that isn't very practical.

Right, although if your have properly encapsulated types, it isn't very feasible
in either case (you'd have to export a "Before_UD_Call_This" operation, which is
nasty to an abstraction and doesn't work well when used as a component).

> So I don't feel a strong need to make these two kinds of deallocation
> consistent as far as task waiting.

I did think about that, but I came to the opposite conclusion. For me, the
current rules for Unchecked_Deallocation are not very good, and the only reason
for *not* fixing it is to avoid runtime inconsistency.

However, waiting for termination means waiting for finalization, and that
can block. (Note that finalization that blocks is not that unusual; finalization
of some Claw objects need to seize an exclusion lock, which can take a long time
if the program is incorrectly structured [Claw does have deadlock-breaking
timeouts on many entry calls, but those raise exceptions and only serve to
highlight a problem.])

That means that we probably can't apply the rules to Unchecked_Deallocation
(simply because there is a chance of deadlock, as might happen in Claw, and that
is too much inconsistency to stomach). I don't buy your rationalization for not
fixing Unchecked_Deallocation, but the inconsistency with Ada 95 and 2005 is a
sufficient reason.

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

Questions? Ask the ACAA Technical Agent