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

!standard 4.8(2) 10-10-30 AI05-0111-3/04
!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

Subpools are added to Ada.

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

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.

Associated with each subpool is a "dynamic master," similar to the "static" masters associated with the execution of various language constructs. The dynamic master associated with a subpool is the master for all objects residing in the subpool. When a subpool is reclaimed, this is analogous to a static master being completed for the objects in the subpool.

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:

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.

Modify 4.8(2) as follows:

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

The expected type for a subpool_handle_name is a 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 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.)

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

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:

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.

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.

[Redundant: There is a master associated with the execution of certain constructs (see 7.6.1),] called a construct master. In addition, each subpool has its own unique master, called the master for the subpool, which is used for the objects allocated from the subpool.

When an object is created by an allocator and the object is allocated from a subpool, then the master of the allocated object (and of any parts that are task objects) is the master for the subpool, rather than that of the access type's collection. When a subpool is *explicitly finalized* (see below), its finalization proceeds by completing any tasks dependent on the subpool's master that are waiting at an open terminate alternative, waiting for their termination, and then finalizing any of the objects allocated from the subpool that still exist. After a subpool has been finalized, any storage allocated for objects in the subpool can be reclaimed.

As the first step of finalizing an object of type Root_Storage_Pools_with_Subpools, any subpools belonging to the pool not previously explicitly finalized are explicitly finalized. (A subpool belongs to the pool which was passed to the call of Set_Pool_of_Subpool for the subpool. The relationship continues until the designated object of the subpool handle is finalized.)

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.

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:

A subpool may be explicitly deallocated using Unchecked_Deallocate_Subpool.

[Redundant: The master of an object is the innermost (construct) master that included the elaboration of the object, for an object that is part of a declared object. The master of an object that is part of an object created by an allocator is the master for the subpool if it is allocated from a subpool; otherwise it is the (construct) master of the ultimate ancestor of the type of the allocator.]

If Subpool is null, a call on Unchecked_Deallocate_Subpool has no effect. Otherwise, a call on Unchecked_Deallocate_Subpool causes the subpool designated by Subpool to be explicitly finalized (see 13.11.4); followed by a Redundant[dispatching] call on System.Storage_Pools.Subpools.Deallocate_Subpool (

finally Subpool is set to null.

It is a bounded error if nonterminable tasks depend on the master of the subpool being deallocated. The possible effects are as given for the unchecked deallocation of an object with a task part (see 13.11.2).

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

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

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; Root_Storage_Pool_with_Subpools; Subpool : in out Subpool_Handle 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;

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;

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 renames Create_Subpool;

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 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);

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;

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

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

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 the 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

* 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).

The model used here is that subpools are really part of the pool object; they are finalized when the pool is finalized. The 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 have a master of that subpool, and will be finalized when the subpool is explicitly deallocated (or when the entire pool is finalized). This point of finalization has no relationship to the point of declaration of the access type, unlike "normal" access types.

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.

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. But we do need to look at some real examples to see if the proposed check is too restrictive in practice (for instance, access to incomplete types deferred to a body cannot use subpools with this check).

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

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.