CVS difference for 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
@@ -16,416 +16,300 @@
-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.
-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.
+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.
+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
+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.
+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.
+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
+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.
+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
- X := new (Local_Storage_Pool) T'(ABC);
-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
-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
-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
-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);
- ... -- 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.
-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
-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
-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
+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.
+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
+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.
@@ -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