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

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

!standard 4.8(2)          10-10-28 AI05-0111-3/03
!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.
DYNAMIC MASTERS
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.
!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):
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).
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.)
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_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 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 : 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 Set_Pool_of_Subpool(Subpool : Subpool_Handle; To : in out Root_Storage_Pool_with_Subpools'Class); -- 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 Set_Pool_of_Subpool for the subpool. The relationship continues until the designated object of the subpool handle is finalized.)
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 System.Subpools.Unchecked_Deallocate_Subpool
(Subpool : in out Subpool_Handle);
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.]
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 (
System.Subpools.Pool_of_Subpool(Subpool).all, 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).
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 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
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).
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 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.
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. 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.
!example
Here is a simple but complete implementation of the classic Mark/Release pool using subpools:
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.
subtype Subpool_Handle is System.Subpools.Subpool_Handle;
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 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);
procedure Deallocate_Subpool ( Pool : in out Mark_Release_Pool_Type; Subpool : in out Subpool_Handle);
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);
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);
function Storage_Size (Pool : Mark_Release_Pool_Type) return Storage_Elements.Storage_Count;
private
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.
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.Subpools.Set_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.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.Subpools.Set_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;
end MR_Pool;
[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.
!ACATS test
Create ACATS C-Tests to test this facility.
!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.

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



Questions? Ask the ACAA Technical Agent