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

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

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:

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.

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

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

The expected type for a subpool_handle_name is System.Storage_Subpools.Subpool_Handle, the type used to identify a subpool defined in the language-defined package System.Storage_Subpools (see 13.11.4).

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

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

with System.Storage_Pools; with System.Storage_Elements; package System.Subpools is

type Root_Storage_Pool_with_Subpools is abstract new Storage_Pools.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 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 : aliased in out Root_Storage_Pool_with_Subpools; Storage_Size : Storage_Elements.Storage_Count := Storage_Elements.Storage_Count'Last) return 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 Subpool manager type. -- [Editor's Note: This uses AI05-0142-4 and AI05-0143-1 features; "access" -- could be used instead.]

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

procedure Reset_Pool_of_Subpool(Subpool : Subpool_Handle; To : in out Root_Storage_Pool_with_Subpools'Class); -- (Re)set the Pool for a newly created subpool or a subpool which -- be 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 : Subpool_Handle) is abstract with Pre'Class => Pool_of_Subpool(Subpool) = Pool'access; -- Allocate space from specified subpool. -- If the subpool handle is null, use the default subpool (if any). -- [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.

private ... -- not specified by the language

end System.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 with a subpool_specification is evaluated, a call is made on Allocate_From_Subpool passing in the given Subpool_Handle, in addition to the parameters as defined for calls on Allocate (see 13.11). 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 Reset_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.

When converting an access value of a subpool access type to a general access type, the accessibility level is that of the innermost program unit or declare block enclosing the conversion.

AARM NOTE: In other words, it can only be converted to a local access type, or to an access discriminant or access parameter. Converting back from the access parameter to a named general access type is similarly limited to a local access type.]

Editor's note for version /2: I'm not sure that we really need this rule. I left it for now, but note that it makes it impossible to use anonyomous access types to work around the ordering rule. As this is intended to be exactly as safe as Unchecked_Deallocation (for which there is no special restriction), I don't off-hand know of any need for it.]

* the latest subtype with a non-static constraint of the subtype_mark of the subtype_indication defining S if the constraint of the subtype_indication is static (see 4.9) Redundant[; including when there is no constraint];

A check is made that the elaboration of the latest subtype with a non-static constraint of the designated type of a subpool access type S occurs before the elaboration of the storage pool object of S and that the elaboration is executed by the same task. Program_Error is raised if this check fails.

[Editor's note: This could be a post-compilation check; I didn't make it one as it is closely related to elaboration checks, and those checks are regular runtime checks. It might actually be easier to implement as a post-compilation check (no runtime description of the elaboration order of packages is needed). There is more on this check in the discussion section.]

AARM Reason: This check ensures that the type and any constraints of the allocated objects exist longer than the storage pool object, so that the subpools are finalized (which finalizes any remaining allocated objects) before the type of the objects ceases to exist. The access type itself will cease to exist before the storage pool. The check excludes subtypes with static constraints (or no constraints) as these cannot depend on any elaboration; excluding them gives a longer window in which the storage pool object may be declared.

AARM Implementation Note: This check can be implemented with a minimum of distributed overhead. Both the latest subtype with a non-static constraint of the designated subtype and the storage pool object have to be within the scope of the access type (otherwise, they could not have been given in the declaration). If the two declarations are in the same compilation unit (or one is in a subunit of the compilation unit containing the other), then the compiler can examine the structure of the unit to determine whether or not the check fails. (If the subtype and object are in the same declarative part, examining the order of declarations will determine the answer; if the subtype is more nested than the object, the check fails; otherwise, if the object and subtype are in different tasks, the check fails.)

If the two declarations are in different compilation units, it is a bit more complex. If the subtype is declared in a procedure, the check fails; if the object is declared in a procedure the check succeeds. If both items are declared at library level in packages, it is necessary to check the order of elaboration of the two packages: the check fails if the package containing the object is elaborated before the package containing the subtype. End AARM Implementation Note.

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

A call on System.Subpools.Unchecked_Deallocate_Subpool causes the subpool to be explicitly finalized (see 13.11.4); followed by a Redundant[dispatching] call on System.Subpools.Deallocate_Subpool (

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

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 Reset_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 is called "Reset_xxx" rather than "Set_xxx"; this means that it 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).

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.

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 is finalized. Note that the important (sub)type is the designated type (that is the type of the allocated objects), not the access type. Thus we adopt a straightforward rule that the designated subtype has to be elaborated before the storage pool object.

The rule is designed to ignore subtypes with static (or no) constraints, in order to give the maximum "window" in which to declare the storage pool object. A subtype with a static constraint cannot depend on any runtime elaborated entities, so it is safe to ignore for the purposes of this check.

In the interest of simplicity, we require both the designated subtype and the storage pool object to be elaborated by the same task. In almost all uses, the types and objects will all be declared at library-level, so this is not going to have a significant effect on usability, and it simplifies the implementation of the check. (This restriction also makes it possible to implement this check as a post-compilation check.)

This check does make structuring code that uses subpools harder. 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.)

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.

with System.Subpools; with System.Subpools.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.

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

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

function Mark (Pool : aliased in out Mark_Release_Pool_Type; Storage_Size : Storage_Elements.Storage_Count := Storage_Elements.Storage_Count'Last) return Subpool_Handle renames Create_Subpool;

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

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

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

type MR_Subpool is new System.Subpools.Root_Subpool with record Start : 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 : Storage_Elements.Storage_Count) is new System.Subpools.Root_Storage_Pool_with_Subpools with record Storage : Storage_Elements.Storage_Array (1..Pool_Size); Next_Allocation : Storage_Elements.Storage_Count := 1; Markers : Subpool_Array; Current_Pool : Subpool_Indexes := 1; end record;

procedure Initialize (Pool : in out Mark_Release_Pool_Type);

-- We don't need Finalize.

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.Subpools.Reset_Pool_for_Subpool (Pool.Markers(1)'Unchecked_Access, Pool'Unchecked_Access); end Initialize;

function Create_Subpool (Pool : aliased in out Mark_Release_Pool_Type; Storage_Size : Storage_Elements.Storage_Count := Storage_Elements.Storage_Count'Last) return 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.Subpools.Reset_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.Current_Pool := Pool.Current_Pool - 1; -- More to the previous subpool Pool.Next_Allocation := Pool.Markers(Pool.Current_Pool); else -- Reinitialize the default subpool: Pool.Next_Allocation := 1; System.Subpools.Reset_Pool_for_Subpool (Pool.Markers(1)'Unchecked_Access, Pool'Unchecked_Access); end if; end Deallocate_Subpool;

procedure Allocate_From_Subpool ( Pool : in out Mark_Release_Pool_Type; Storage_Address : out Address; Size_In_Storage_Elements : in Storage_Elements.Storage_Count; Alignment : in Storage_Elements.Storage_Count; Subpool : 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 Address; Size_In_Storage_Elements : in Storage_Elements.Storage_Count; Alignment : in Storage_Elements.Storage_Count) is -- Allocate from the default subpool: begin -- Correct the alignment if necessary: while Pool.Next_Allocation mod Alignment /= 0 loop Pool.Next_Allocation := Pool.Next_Allocation + 1; end loop; -- [Editor's note: Yes, this sucks. But it's also correct. -- Every other one I've written is wrong until it is extensively tested. -- I don't have time for that...] 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 Address; Size_In_Storage_Elements : in Storage_Elements.Storage_Count; Alignment : in 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 Storage_Elements.Storage_Count is begin return Pool.Pool_Size; end Storage_Size;

[Editor's note: It might be worth considering including this example in the Standard, as it shows one way to use the subpool feature. Or possibly a block allocator of some sort.]

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.