CVS difference for ai05s/ai05-0111-1.txt

Differences between 1.4 and version 1.5
Log of other versions for file ai05s/ai05-0111-1.txt

--- ai05s/ai05-0111-1.txt	2008/10/25 04:53:14	1.4
+++ ai05s/ai05-0111-1.txt	2008/11/08 03:19:42	1.5
@@ -1,4 +1,4 @@
-!standard  4.8(2)                                       08-08-13    AI05-0111-1/02
+!standard  4.8(2)                                       08-10-25    AI05-0111-1/03
 !standard  4.8(3/2)
 !standard  4.8(5.3/2)
 !standard  4.8(7/2)
@@ -16,416 +16,300 @@
 
 !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 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 storage pool
-for a dynamically allocated object to be specified explicitly 
-at the point of the allocator.  However, it is desirable if there
-are protections against dangling references, and allowing storage
-pools of short lifetimes to be specified in an allocator for a
-long-lived access type clearly does not provide such protection.
+for a dynamically allocated object to be specified explicitly at the
+point of the allocator.  However, it is desirable that there be
+protections against dangling references, and allowing storage pools of
+short lifetimes to be specified in an allocator for a long-lived access
+type clearly does not inherently provide such protection.
 
 !proposal
 
-Add new syntax for specifying the storage pool at the point of
-an allocator, with a syntax like:
+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);
+
+To protect against a subpool being reclaimed while there are still
+access values outside the subpool designating objects residing within
+it, a reference count is maintained for each subpool.  Various
+compile-time and run-time checks are used to ensure that as long as
+there might be access values outside the subpool that designate objects
+in the subpool, the reference count on the subpool is greater than zero.
+Once the reference count drops to zero, the subpool may be safely
+reclaimed.  If a set of subpools have references to each other, but
+there are no external references to any of the subpools, the entire set
+of mutually-referencing subpools may be reclaimed.
+
+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 that need finalization.  When a
+subpool is ready to be reclaimed, this is analogous to a static master
+being completed.  Any tasks dependent on the master are awaited, and
+then once all the tasks are completed or terminable, the objects in the
+subpool are finalized and the subpool is reclaimed.
+
+SUBPOOL REFERENCES
+
+We propose four kinds of references to a subpool:
+
+  1) Static subpool handle
+  2) Dynamic subpool handle
+  3) Strong object reference
+  4) Weak object reference
+  
+A "static subpool handle" is a counted reference to a subpool
+represented by a controlled immutable object declared within a static
+master.  A "dynamic subpool handle" is an immutable, counted reference
+to a subpool from another subpool. Both kinds of handles, once
+established, remain in place until the handle is finalized, and are
+immutable in the sense that they always refer to the same subpool for as
+long as they exist.  Static subpool handles are the objects used in an
+allocator to identify the subpool for the allocation. A dynamic subpool
+handle is used to allow access values residing in one subpool to
+designate objects in another subpool.  A dynamic subpool handle is
+created by calling a language-defined procedure "Allow_Reference
+(From_Subpool, To_Subpool)," where the subpools are identified by static
+handles.
+
+We use the terminology that a handle "gives access" to a subpool, as
+well as its constituent objects and associated master, if it references
+that subpool directly, or it references a subpool that has a dynamic
+handle that gives access to the subpool.  In other words "gives access"
+is essentially a closure over the "handle" relationship.  Similarly we
+say that a subpool or master "has access" to another subpool, master, or
+object if it has a handle that gives access to that subpool, master, or
+object.  A subpool or master also "has access" to itself and its
+constituent objects. Furthermore a static master "has access" to
+anything to which an enclosing static master has access.  Because
+handles are immutable, the "gives access" and "has access" relationship
+are similarly immutable. Given this terminology,  we can say that it is
+"safe" for an access value within a given master to designate an object
+in a subpool to which that master *has access,* because the access value
+cannot "outlive" the subpool.
+
+A "strong object reference" is a combination of a counted reference on a
+subpool and an access value designating some object to which the subpool
+has access.  For programmatic use, a strong object reference can be
+converted into a static handle and an access value.  A strong object
+reference can be assigned a new value, given a static handle on a
+subpool and an access value designating an object to which the handle
+gives access.  When a strong object reference is changed, the reference
+count is transferred from the original target subpool to the new target
+subpool.  A strong object reference may also be set to be a null
+reference, designating no subpool or object.  This is the default
+initial value of a strong object reference.  A strong object reference
+may be stored anywhere that the associated access type is defined.
+
+A "weak object reference" is a combination of a managed reference on a
+subpool and an access value designating some object to which the subpool
+has access. The reference is "managed" in the sense that if the subpool
+is about to be finalized, all weak object references designating the
+subpool are located and set to be null references.  For programmatic
+use, a weak object reference can be converted to a strong object
+reference, and from there to a handle and access value, though the
+resulting static handle and access value might be null. Weak object
+references may be assigned from other weak object references or strong
+object references.  A weak object reference may be stored anywhere that
+the associated access type is defined.
+
+ACCESSIBILITY CHECKS
+
+If an access type is associated with a storage pool that has subpools,
+then checks are performed on assignment and function return to make sure
+that an access value never outlives the subpool containing the object it
+designates (the "designated subpool").  On assignment of an access value
+to a stand-alone access object, or to a component of an
+immutably-limited composite object, an accessibility check will be
+performed to ensure that the master of the assigned object has access to
+the designated subpool.  On assignment to a component of a composite
+object that is not immutably limited, a check is made that the type of
+the composite object does not outlive the designated subpool (i.e. that
+the master of the composite type has access to the designated subpool).
+This latter rule ensures that on assignment of composite objects, no
+component-by-component accessibility checks need be performed.  We make
+an exception for immutably-limited composite types because there is no
+place where an object of such a type could be assignable to another
+object of the type, and hence no place where component-by-component
+checks would be necessary.
+
+When assigning to OUT or IN OUT parameters, the master of the object is
+presumed to be the innermost master enclosing the call, so the check
+ensures that that master has access to the designated subpool. Similarly
+on function return of an access value, the check is against the
+innermost master enclosing the call.  On assignment to a component of an
+immutably-limited return object, the check is against the actual
+eventual master of the return object, since this is known due to the
+build-in-place requirements for such a type.
+
+COMPILE-TIME CHECKING
+
+It is the intent that many of these checks can be performed at
+compile-time.  This is enabled by the transitive nature of the "has
+access" relationship.  For example, if a function returns an access
+value and the return statement is not "inside" some local master having
+a static handle on some subpool, then no accessibility check is
+necessary as part of the return.   This is because, whatever is the
+designated subpool, the master immediately enclosing the call must have
+access to it, since only the presence of a static subpool handle can
+cause a nested master to have more access than its enclosing master.
+This property ensures that most access value manipulations need no
+checks.  
+
+It is only if an assignment or function return is "crossing" a master
+having a static subpool handle that any check need be performed.
+Furthermore, if the compiler can trace the origin of the access value to
+a point outside any handle being "crossed," then again, no check is
+required.  For example, if the access value came from a formal
+parameter, perhaps after following various intermediate indirections, it
+is always safe to return it, even if the function did have local masters
+with static subpool handles.  
+
+Note that this means that existing Ada code that takes an access value,
+and follows one or more levels of indirection to retrieve another access
+value, and then returns it, could be used as is with no additional
+run-time checks required, since clearly existing code has no explicit
+use of subpool handles.
+
+RUN-TIME CHECKING
+
+Despite the goal of making most of these checks be performable at
+compile time, some run-time checking may be necessary. To enable such
+checks to be performed at run-time, the implementation of a storage pool
+with subpools must provide an operation "Originating_Subpool
+(Storage_Pool, Address)" that, given an address returned from "Allocate"
+from one of its subpools, will return a static handle on the subpool.
+This might be implemented by storing a reference to the subpool
+immediately preceding each object allocated from the subpool, or by
+using separate memory pages for separate subpools, and having a
+reference to the associated subpool at the start of each page, or by a
+combination of techniques.  An attribute_function, perhaps
+<access_type>'Subpool(acc_val), might be applicable to a non-null access
+value of the type, and be equivalent to calling the appropriate
+Originating_Subpool function on acc_val.all'Address.
+
+Once the designated subpool of a given access value is determined, the
+required check can be performed.  Note that although the implementor of
+the storage pool is required to provide the Originating_Subpool
+operation, it is the underlying Ada implementation that actually
+maintains the reference counts associated with subpool handles and
+strong references, and the lists associated with weak references.  It
+also performs whatever run-time checks are required.  One way to think
+about it is that the Ada implemention worries about the masters,
+while the user code can take over allocation from and reclamation of
+the subpools.
+
+!wording
 
-   X := new (Local_Storage_Pool) T'(ABC);
+[**TBD**]
 
-To protect against a local storage pool being reclaimed
-while there are still references designating objects
-allocated from it, accessibility checks would be added
-on assignment for an access type whose storage pool is
-broken up into multiple storage "subpools."  These accessibility
-checks will make sure that the object containing the
-left-hand side of the assignment will not outlive the 
-object designated by the right-hand-side of the assignment
-(or more precisely, that the master of the LHS will not outlive
-the master of the RHS).
-
-Given an access value of an access type that allows subpools, 
-it will be possible to determine at run time
-the accessibility level, or more precisely, the master, 
-associated with the subpool from which the object
-it designates was allocated.  If an object allocated
-from a subpool contains a task, the master of the task
-is determined by the master of the subpool.  For subpools 
-that are themselves dynamically allocated, they will become
-"dynamic" masters for all objects allocated from
-them, and reference counts or an equivalent mechanism
-will be used to determine whether they can be safely 
-finalized (as part of a "checked" deallocation operation,
-called "Release").  These reference counts (or equivalent) will 
-track the number of other unfinalized masters that might have 
-objects with references designating objects of the
-dynamic master, so that finalization of a Release'd
-object actually occurs when the external reference
-count drops to zero.  Cyclic references will be properly handled,
-so that Release will not cause finalization immediately
-if there are references, unless they are merely cyclic
-references from other subpools that have been Release'd,
-in which case all will be finalized.
-
-If an access type is to support subpools, then its 'Storage_Pool 
-must denote an object of a type descended from the type 
-System.Storage_Pools.Subpools.Root_Subpool.  Root_Subpool
-is itself descended from Root_Storage_Pool, but with some
-extra operations, including one for determining, given
-a non-null access value of the type, the subpool from which
-the object it designates is allocated.  From the subpool,
-the implementation can presumably determine the associated
-(possibly dynamic) master so it can perform accessibility
-checks.
-
-Another operation on a subpool is one used to specify that
-it may henceforth designate objects in another particular subpool. 
-This operation might be named "May_Reference."  May_Reference(A, B)
-would mean that subpool A may contains objects that designate
-objects allocated from subpool B.  May_Reference is
-only relevant for subpools that are themselves dynamically
-allocated and hence have dynamic masters.  The relative
-lifetime of a dynamic master would be determined by calls on this
-operation, and in turn would be checked on access value assignment.
-May_Reference establishes a partial order, and is presumed
-transitive.  
-
-Each subpool "knows" the ultimate ancestor storage pool with
-which it is associated.  When a subpool is specified in an
-allocator, a check is made that its ancestor storage pool is
-the one associated with the access type of the allocator.
-
-Replace 4.8(2) with:
-
-   allocator ::=
-      NEW [subpool_specifier] subtype_indication | 
-      NEW [subpool_specifier] qualified_expression
-      
-   subpool_specifier ::= ( *subpool_*name )
-   
-   
-Add after 4.8(3/2):
-
-   The expected type for the *subpool_*name of the subpool_specifier, 
-   if any, is System.Storage_Pools.Subpools.Root_Subpool'Class (see 13.11).
-
-Add after 4.8(5.3/2):
-
-   If a subpool_specifier is present, the *subpool_*name of the
-   subpool_specifier shall denote a variable.
-
-Add before 4.8(7/2):
-
-   If a subpool_specifier is present, a check is made that the storage
-   pool associated with the type of the allocator is an ancestor pool 
-   of the object denoted by the *subpool_*name (see 13.11).  If this 
-   check fails, Program_Error is raised.
-   
-Add after 13.11(15):
-
-   The following language-defined library package exists:
-   
-     package System.Storage_Pools.Subpools is
-         type Root_Subpool is abstract new Root_Storage_Pool with private;
-         pragma Preelaborable_Initialization(Root_Subpool);
-         
-         -- Allocate, Deallocate, and Storage_Size are inherited
-         
-         -- Additional dispatching operations on subpools
-         function Create_Subpool(Pool : access Root_Subpool) 
-           return Root_Subpool'Class is abstract;
-                  
-         function Is_Ancestor_Pool
-            (Ancestor_Pool : Root_Subpool; Subpool : Root_Subpool'Class) 
-           return Boolean is abstract;
-           
-         function Originating_Subpool
-             (Pool : Root_Subpool; Storage_Address : System.Address)
-           return access Root_Subpool'Class is abstract;
-           
-         -- Classwide operations on subpools
-         procedure Release_Subpool(Pool : access Root_Subpool'Class);
-         
-         procedure May_Reference(Referencing_Pool : access Root_Subpool'Class;
-           Referenced_Pool : access Root_Subpool'Class);
-     private
-         ... -- not specified by the language
-     end System.Storage_Pools.Subpools;
-     
-   A *subpool type* is a descendant of Root_Subpool.  A *subpool* is an object whose
-   type is a subpool type.  A subpool P is an *ancestor pool* of a second subpool S if 
-   P and S denote the same subpool, if S was the result of calling Create_Subpool(P), 
-   if Is_Ancestor_Pool(P, S) returns True, or if P is an ancestor pool of a third pool
-   R which is in turn an ancestor pool of S.  
-   
-   An element of a pool P *references* a pool R if a part of
-   the element is of an access-to-object type, and it designates an
-   element of pool R.  A pool P *may reference* a pool R if May_Reference(P, R)
-   has been invoked.
-         
 !discussion
 
-It is valuable to be able to specify the storage pool (aka "region")
-at the point of allocation, rather than at the point of access type
-declaration.  However, an access type that designates objects from
-pools with lifetimes shorter than that of the access type
-is clearly error prone.  How do we deal with this issue?
-
-- At the point of declaration, we need to know that the access
-  type is such an access type with per-allocator storage pools.
-  We might specify a 'Storage_Pool_Type rather than an explicit
-  'Storage_Pool for such an access type.
-
-- Objects designated by such an access type need to keep track of
-  what pool/region they come from so unchecked deallocation can
-  operate properly, and to prevent a pointer to such an object 
-  being stored in a place that will outlive the object.  A 'Storage_Pool
-  attribute of access *values* might be a way to accomplish this.
-  This implies that storage-pool types that can be used for access
-  types with per-allocator storage pools must provide an operation
-  that can determine the storage pool from an address.  This needs
-  to work even for addresses allocated from storage pools of a type
-  descended from the given type, if we permit the specification of
-  a class-wide type.  Perhaps we shouldn't allow that specifically
-  because of this problem.
-
-- Access parameters would need a 'Storage_Pool attribute as well.
-  This could be used instead of the accessibility level attribute,
-  presuming that storage pools have some kind of accessibility level
-  residing in them.
-
-- An operation to compare lifetimes of storage pools should be available,
-  so we can verify at run-time that the object where a pointer is being
-  stored lives no longer than the designated object.  This is a check
-  performed by the compiler on storage pools (and perhaps any
-  two controlled objects?).
-
-- We need an "open" operation or equivalent on a storage pool to make
-  sure it is safe to allocate objects in the storage pool and hold the
-  access values in local variables.  This needs to be an operation that
-  is somehow "scoped" in that we don't want the pool to be "closed"
-  in the middle of the scope of local variables.
-  One way to accomplish this is to make the "open" operation be something
-  that is accomplished as a side-efffect of declaring a controlled object,
-  similar to the "within" or "pin" operations we use now with subpools
-  in the Inspector.  
-
-  Does this deserve new syntax?  I wouldn't want to introduce it just
-  for this purpose.  In the long run you could imagine that a procedure
-  might have a matching "finalize" operation that is called automatically
-  on scope exit.  But the explicit object approach does it awfully cleanly,
-  since it captures the parameters (which must all be by-copy since they
-  are discriminants) and can record the old state, etc., if desired.
-  But it feels odd to require this notion of "open" but not provide any
-  simple way to do it.  Perhaps if we presume that for most pools, they
-  are open throughout their lifetime, and the only time anything is reclaimed
-  is when everything is reclaimed, when the pool is finalized.
-  Mark/release is best done by creating effectively a new pool that just
-  happens to share part of a page with an enclosing pool, which is
-  frozen during that period.  Freeze and unfreeze are safer than open
-  and close, perhaps.  And freeze simply means no allocations.  Deallocations
-  would only be via finalization.
-
-  The "Finalize" routine for the Root type allowed for storage pools 
-  supporting per-allocator pools would finalize all of the objects
-  in the storage pool.  It need not be called explicitly, since it will
-  be performed implicitly because it will use a controlled component.
-  Hmmm, that doesn't really work, since we want finalization to happen
-  *before* the pages of the pool are freed.  Hence, I think we need an
-  explicit operation that finalizes the objects, and which will produce
-  an error if it is called implicitly.
-  Which implies that 
-
-- comparing pool lifetimes should be based on some kind of partial ordering
-  established by an explicit directed graph with reference counts.  Edges
-  can be set up when the pool is created, such as the mark/release (sub)pool
-  imagined above, or a subpool (subregion) that keeps a list of its
-  components to be freed when the subpool goes away.  (There are many
-  ways a subpool could know how to release its own objects but no others
-  on its finalization.)
-
-- between invoking an allocation and "safely" storing the pointer into
-  some other heap object, the compiler could provide a reference count, which
-  would prevent premature deallocation.  It would only need to keep track
-  of local variables and temps, and only one per master, since anything 
-  in the heap must have a storage-pool to storage-pool link to ensure 
-  lifetime.  Conceivably this could be a list of access values if we wanted
-  to prevent storage leaks.  Each access value corresponds to the value of an
-  allocator that has *not* yet been stored into another heap object.
-  But to just prevent dangling references, all we need is that when
-  doing an allocator, we add a cleanup object to the stack which contains
-  the address of the pool to "pin"/"freeze."   On the other hand,
-  the pool must have been passed into the routine to do the allocator,
-  so it would be essentially a multi-tasking no-no to delete it while
-  it was being used in that way.
-
-- The implementation can take care of creating a list of items needing 
-  finalization using the "root" part of the Storage_Pool.  It can also
-  provide an operation for checking the respective lifetimes.  In general
-  types needing finalization will need extra overhead in heaps, which
-  should be factored into the Max_Size_In_Storage_Elements.
-
-- If a particular container type often has its own storage pool for its
-  elements, then it should identify it via an access discriminant, 
-  so that the pool gets finalized automatically if it is newly allocated 
-  as part of creating the container, but doesn't if it is a 
-  preexisting pool.
-  
-DYNAMIC MASTER MODEL
+PERFORMANCE
 
-It seems helpful to think of a dynamic master as somewhat like
-a task.  Releasing the associated subpool is equivalent to the
-task completing.  It then proceeds to wait for its dependents
-to terminate or become terminable.  A dependent subpool's dynamic
-master is "terminable" if it has been released and all of its dependents
-are similarly terminable.  Note that we can have cyclic dependencies
-between dynamic masters.  But that still works presuming they have all
-been released and all of the dependent tasks are terminable.
-
-We don't really want to introduce another task, both for efficiency
-and because we don't want any finalization to happen completely
-asynchronously.  Essentially when the last subtask, if any,
-becomes terminable, or the last Release is performed, that causes
-the finalization to occur.  This does mean that the finalization
-can be performed on the thread of a subtask.  Is that acceptable?
-Is there any alternative?  If there are subtasks, you have the
-possibility of finalizations occuring inside the subtasks, so
-you have multi-threaded finalization already.
-
-Presumably after a Release, no further allocations may be performed
-on the subpool.
-
-MAY REFERENCE RULES
-
-Calls on May_Reference(A, B) effectively create a dependence of A on B.
-A need not be a subpool -- it can be a "regular" pool.  B must be
-a subpool.   May_Reference will fail if the accessibility level of
-B's ultimate ancestor pool is deeper than A's ultimate ancestor pool.
-In other words, May_Reference will raise Program_Error if an attempt
-to convert from B's associated access type to A's would fail the 
-"normal" Ada 95 accessibility check.  We make this restriction because
-May_Reference(A, B) is designed only to extend the lifetime of B,
-not shorten the life of A, and should never cause dangling 
-references if A lives out its "full" life.
-
-Note that if A is a "normal" pool, this effectively means that
-B will live at least until the (non-dynamic) master associated 
-with A completes.  This is also a way to allow regular local variables
-to refer to B.  
-
-By allowing A to be a normal pool, we require that all pools can
-be on the dependent list of a subpool.  Only subpools need to
-maintain dependent lists/counts.
-
-Perhaps we need a unary operation such as Locals_May_Reference(B) 
-or equivalent, which will make sure B doesn't disappear before 
-the current stack frame.  Of course if we pass a reference to B 
-as a parameter, we want to be sure B doesn't disappear.  How 
-does that work?  It would seem that any frame in which an allocator
-occurs should be dependent on B.  Also any frame that gets back
-a return result that was allocated inside the called function
-should be dependent on B.  Is it legal to create a local subpool
-and then return an allocated object?  Hopefully not!
-Hence, there needs to be a check on return of a value of an access type with
-subpools, since it is effectively being stored in the caller's
-frame.  Similarly, storing into a heap object or a global requires
-a check.
-
-COUNTED REFERENCES *NOT* FROM OTHER SUBPOOLS
-
-How do we deal with simple stack-based references?  What is the equivalent
-of May_Reference for stack-based references?  Probably a local
-"Reference" object whose finalization releases the dependence.
-This is similar to the notion of "opening" or "pinning" the subpool.
-
-But how do between-subpool references work?  In particular, is there
-a way to have a reference that can be deleted and the corresponding
-dependence goes away?  This sounds like a counted reference which
-is not from one subpool to the next, but is rather a single object
-that combines the subpool dependence and the subpool pointer, so
-it can be stored in a hash table, say.  So we really have two
-kinds of things, one are counted references from an object to
-a subpool, and counted references from a subpool to a subpool
-The latter only go away when the subpool goes away, since their
-are an unknown number of "subordinate" uncounted references
-relying on it.  On the other hand, counted references from an object
-to a subpool can be deleted, or changed to point to some other
-subpool.  Note that these can't be cyclic, since the origin of the
-counted reference is not a subpool.  However, I suppose if it is
-inside a subpool, and the subpool is finalized, the counted reference
-will go away automatically.  But we probably don't need to recognize
-such cyclic dependences, because they can be explicitly broken when
-desired.  Subpool-to-subpool dependences cannot be explicitly
-broken, because of the subordinate uncounted references.
-
-Counted references could be either "weak" or "strong."  A "strong"
-counted reference keeps the designated subpool from going away 
-until the strong reference is destroyed.  A "weak" counted reference
-does not impose any such requirement.  Instead, a weak reference
-can generate a strong reference upon request, presuming the designated
-subpool is still in existence.  If not, the weak reference returns
-"null," indicating the subpool is gone.  Hence, a weak reference
-could be stored in a cache, and if the designated subpool is chosen
-for destruction because it hasn't been recently used, then the
-weak reference would reflect that.  Strong references need only be
-counted.  Weak references probably need to be on a list so they
-can be nulled out.  Alternatively, weak references could refer
-to objects that are only reused as weak-ref targets, in the same
-way we handle tasks in the AdaMagic RTS, using a generation number
-technique to establish whether the target still exists.
-
-COMPOSITE OBJECTS WITH ACCESS VALUE SUBCOMPONENTS
-
-Things get more challenging when we start talking about assigning
-composite objects that have one or more subcomponents that are
-access values of subpool'ed access types.  Basically we need to
-be sure that the LHS of the assignment does not outlive any of the 
-subpools designated by the RHS subcomponents.
-
-We want to avoid any operation that needs to iterate through
-the subcomponents.  In general, we associate a master with the
-entire object.  This master is guaranteed to not outlive any
-of the subpools designated by its subcomponents.  This works
-so long as the master is associated with a heap object.  However,
-if the master is simply a local stack frame, then you couldn't
-assign into a formal parameter or return it from a function.
-We need to have a longer-lived master assocatiated with a stack
-object.  We could associate a subpool with a local object.
-That is sort of what we do in an extended return statement.
-If we are doing an aggregate assignment into an OUT parameter,
-the aggregate could be treated as though it were part of the
-subpool holding the OUT parameter.  We may need a more general
-way to associate a local variable with its ultimate target.
-Perhaps we can specify the pool as an attribute, or with a
-rep clause, on the local variable.
-
-Perhaps a better approach is as follows:
-
-If a composite type is non-limited, then the accessibility level
-of the declaration of (the ultimate ancestor of) the composite type
-will determine the presumed lifetime of any object of the type.
-This allows objects of the composite type to be freely interassigned
-without having to recheck accessibility.  Any accessibility checks
-are performed when assigning to an access value component of such
-a composite object, presuming the object will ultimately be assigned
-to an object that lives at the same level as the composite type.
-
-On the other hand, if a composite type is limited, then no composite
-assignments are possible, and each object of the type is created
-in its final resting place, so the accessibility level is known,
-and can be checked when an assignment is performed to an access value
-component.
+To make run-time checks efficient, the Ada implementation may create
+auxiliary data structures and do additional computing as part of
+creating new dynamic subpool handles in response to Allow_Reference
+calls. The intent is that many checks can be done using a simple
+comparison based on an analogue of the static accessibility levels, and
+only if the simple check fails would a more complex check be necessary.
+For example, because subpool handles are immutable, once two subpools
+reference each other directly or indirectly, they can effectively be
+treated as a single combined subpool from the point of view of lifetime.
+That is, neither can be reclaimed until both can be.  Using an algorithm
+such as Tarjan's "union find" algorithm, subpools participating in
+cyclic dependencies can be combined efficiently, with any one of them
+acting as the representative of them all.  What this means is that an
+arbitrary directed graph of dependencies between subpools can be reduced
+to a forest of strict trees between subpool "combines," simplifying the
+job of relative lifetime determination.
+
+DEFAULT SUBPOOL?
+
+In the absence of an explicit subpool specified on an allocator for an
+access type with subpools, which subpool should be used?  The "original"
+one (i.e. access_type'Storage_Pool).  Perhaps we could allow a static
+subpool handle to be marked as a "default allocation handle," and then
+the innermost such handle associated with the storage pool of the access
+type would be used. Obviously the latter would be more flexible, and
+allow existing code to be used without having to annotate existing
+allocators with explicit subpools.  On the other hand, it creates many
+possibilities for confusion and bugs, since the identification of the
+handle might be far removed from the actual allocator.  Another
+alternative is to base it on the target of the allocator, if it is being
+stored directly into a component of an immutably-limited
+subpool-resident object.
 
 !example
 
+As an example of the use of subpools, 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.
+
+Weak object references could be used in a table indexed by customer name
+or product name.  Before retrieving information from the persistent
+database, a check would be made in the table to see if there is a weak
+reference, and whether upon converting into a strong reference it is
+non-null.  If so, then the existing in-memory information can be reused.
+ If it is null, then the information must be retrieved from the
+persistent database, and the appropriate in-memory data structures
+created, again depositing a weak reference in the table for future
+reference. Meanwhile strong references would be kept in the web server's
+table of active sessions, so the information in use by an active session
+would not be prematurely reclaimed.  Finally there would be appropriate
+dynamic subpool handles or strong object refernces between the subpools
+representing related shopping carts, customers, and products, ensuring
+that, for example, as long as a shopping cart remained active the
+associated customer history record remained active.
+
+Whenever a subprogram would actually need to "walk" through an in-memory
+data structure, a strong object reference, presumably to the "root" node
+of the designated data structure, would be converted into a static
+subpool handle and an access value to the root node.  The static subpool
+handle would reside in a local master, protecting all local use of the
+access value, and anything reachable from the access value, until the
+local master was completed and the static subpool handle was finalized.
+
+To avoid reclaiming subpools as soon as the last reference from an
+active session went away, since the information might be needed again
+relatively soon, a separate caching task could keep strong references in
+a list, ordered by recency of use.  When the storage pool implementation
+detects that the total space occupied by all of its subpools exceeds
+some threshhold, it could request that the caching task start discarding
+strong references to the least recently used subpools.  This presumes
+the application would notify the caching task on each "significant" use
+of the subpool, so the recency of significant use could be determined.
 
+
+
 !ACATS test
 
 
@@ -3712,5 +3596,24 @@
 access values that are components.  See below.
 
 [This is version /02 of the AI - Editor.]
+
+****************************************************************
+
+From: Tucker Taft
+Sent: Staurday, October 25, 2008  2:02 PM
+
+I presented some of the ideas associated with per-allocator pools to the "container"
+working group recently at a meeting we held to discuss new kinds of containers, and
+as a result refined my thinking on this topic quite a bit.  I realize it is past the
+deadline, but it seems worth providing this latest incarnation, so we don't end up
+discussing out-of-date ideas.
+
+This is presumably pretty low on the priority list in any case, so this might end up
+being more of an over-lunch or in-the-bar discussion anyway.
+
+I ended up throwing away all of the !wording section, since I felt it was
+premature, so you will find a !proposal, a !discussion, and an Example.
+
+[This is version /03 of the AI - Editor.]
 
 ****************************************************************

Questions? Ask the ACAA Technical Agent