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

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.

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

From: Brad Moore
Sent: Friday, October 29, 2010  7:17 PM

Looks really good!
Much easier to understand than other versions.

I have a few comments.


1) 4.8(10.3/2) AARM Reason: "it is likely that
   this check will still detect the problem,"

"Likely" seems a bit strong here, as it implies that most vendors will implement
this, when that remains to be seen. I suggest replacing "likely" with
"possibly".

2) I am just raising the question whether it makes sense to have the package
   Subpools as a child of Storage_Pools? I think I prefer it the way it is
   currently, but it is probably good to at least ask the question.

3) Can the Subpools package be Preelaborated? Storage_Pools is, so it seems a
   bit odd that Storage_Pools isn't.

4) Set_Pool_of_Subpool spec comments.
    "which be being reused"

5) In the example, I think it would be nice if the overriding indicator were
   used where appropriate.

6) In the example, I presume the package is designed to allow further
   derivations. If it were desired that this be a final derivation in a class
   hierarchy, then the calls Allocate_From_Subpoop, Deallocate_Subpool,
   Allocate, and Deallocate, could be moved into the private section, to hide
   those details from the client, thus providing a simpler interface. If this is
   a possibility, perhaps it would improve the example if this were done.

7) In the problem section it mentions that this package could be used as a
   building block to create safer allocations, though the current package allows
   for dangling references. It would be helpful to add a few sentences to
   provide this vision to suggest how such safer storage pools might be created.


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

From: Randy Brukardt
Sent: Saturday, October 30, 2010  9:54 PM

>    1) 4.8(10.3/2) AARM Reason: "it is likely that
>       this check will still detect the problem,"
>
>    "Likely" seems a bit strong here, as it implies that most vendors
> will implement this, when that remains to be seen. I suggest replacing
> "likely" with "possibly".

We certainly assume an Ada 2012 implementation in the Ada 2012 standard. And
this check is not optional. So I think I stand by my original comment (I might
have misunderstood your concern, however).

...
>  6) In the example, I presume the package is designed to allow further derivations.
>     If it were desired that this be a final derivation in a class hierarchy, then
>     the calls Allocate_From_Subpoop, Deallocate_Subpool, Allocate, and
>     Deallocate, could be moved into the private section, to hide those details from
>     the client, thus providing a simpler interface. If this is a possibility, perhaps it
>     would improve the example if this were done.

Tucker suggested something on this line. I'll try to do that.

>    7) In the problem section it mentions that this package could be used as a building
>       block to create safer allocations, though the current package allows for dangling
>       references. It would be helpful to add a few sentences to provide this vision to
>       suggest how such safer storage pools might be created.

OK.

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

From: Randy Brukardt
Sent: Saturday, October 30, 2010  11:11 PM

Attached find the /04 update for the subpool proposal.

I made the changes requested by Brad and by the ARG discussion, except for 2:

I didn't follow Bob's two subtype proposal because it would complicate the use
for users; I used direct "not null" instead.

I didn't follow Tucker's fully private example suggestion, because that would
make the type not a storage pool to clients, meaning they couldn't use it to
specify 'Storage_Pool, making it useless. I was able to do the rest of the
rearranging, so I think it is better separated into client and implementation
parts.

I also did the following three changes:


Added a Default_Subpool_for_Pool routine. Otherwise, the implementation would
not know what subpool to use as the master for the allocated objects. That would
be bad.

Also reworded Unchecked_Subpool_Deallocate to handle the null subpool case
(can't use not null there as the handle is nulled out by this call).

Also noticed missing System prefixes in the example.

Finally, added discussion of possible safer ways to use this, as requested by
Brad. It's in the discussion, not the problem.

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

From: Robert Dewar
Sent: Monday, November 8, 2010  3:19 AM

> 1) 4.8(10.3/2) AARM Reason: "it is likely that this check will still
> detect the problem,"
> "Likely" seems a bit strong here, as it implies that most vendors will
> implement this, when that remains to be seen. I suggest replacing
> "likely" with "possibly".

I would keep likely, the immediate issue is really whether GNAT implements
this or not, so just get the answer to that question!

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

From: Randy Brukardt
Sent: Monday, November 8, 2010  5:51 PM

Bob said at the meeting that he wants to implement it in GNAT whether or not it
gets standardized. That's a pretty strong endorsement!

Anyway, this was the one place where I didn't understand Brad's comment and did
not act on it in the next draft (written Saturday night and discussed on Sunday
at the meeting). None of this is interesting if it isn't implemented, and this
note is discussing a runtime check on a subpool handle. If there aren't any
subpool handles, there surely isn't any check (and if there are, there surely is
a check, it's easy to implement and an allocator that fails the check is
nonsense), so I don't understand what the relevance of implementation is.

Some background. This AARM note is applied to the runtime check that a subpool
handle represents a subpool of the pool of the access type being allocated. The
allocator would be nonsense if it was allocating objects from some other *pool*
than the one defined for the type. Thus there is a runtime check (all subpool
handles being equivalent as far as the Ada implementation is concerned).

The AARM note is discussing the issue of allocating from a "dangling" subpool
handle; that is, a subpool handle for a subpool that has already been
deallocated. It was intended to note that this pool check will also "likely"
detect a dangling subpool handle.

Whether the check can detect a dangling subpool handle depends on the
implementation of the pool (something totally under the control of the pool
implementor, not the Ada implementer). When a subpool is deallocated, the Ada
implementation is required to sever the connection between the subpool and the
pool, thus the check will automatically fail for a dangling subpool so long as
the subpool object still exists. (This is easily implemented by simply setting
the connection to null.) Therefore, the check will always detect dangling
handles if the subpool objects are statically part of the pool object (as in the
example in the AI). However, if the subpool objects are themselves deallocated
when the subpool is deallocated, then the subpool handle is really dangling in
an Ada sense and the check is technically doing something erroneous. (That's OK,
because the use of the subpool handle as an allocator is also erroneous in that
case, so there is no additional erroneousness created by the check.) Still, the
check is likely to detect a problem, as the implementation will have broken the
connection before the memory was deallocated. Thus, practically, the check would
only pass (that is, fail to detect the error) if the same memory was allocated
as another subpool object for the same pool before the check is made. If it is
allocated to some other kind of entity, it is highly unlikely that it would have
the right memory contents for the check to pass.

This is too much explanation for an AARM note. It's probably even too much
explanation for the !discussion section of the AI; but it is just right in the
!appendix, which is why I just spent 10 minutes writing it up.

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

From: Bob Duff
Sent: Monday, November 8, 2010  6:00 PM

Thank you.  Good explanation.  So "likely" is correct.

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

From: Tucker Taft
Sent: Monday, November 8, 2010  6:11 PM

Your discussion makes sense to me.
The run-time check for whether the
subpool is from the right pool is not optional.
The "likeliness" issue is merely based on the vagaries of reusing storage, etc.,
and as Randy points out, is in (partial) control of the subpool implementor, not
the Ada implementor.

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

Following a a summary of a private conversation in November 2010 about the
termination semantics of subpool deallocation.

Randy Brukardt:

Let me remind you where we are.

The big change to the AI that we decided on was to drop all of the master stuff
from the AI.

(The following discussion will ignore Unchecked_Deallocate_Subpool; I'll get to
that in a moment...)

This works because all of the tasks and controlled objects allocated for an
access type will "belong" to the master of the scope in which the access type is
declared. Because of the accessibility check on a storage pool, this is the same
master as that of the storage pool. Therefore, any tasks and controlled objects
allocated from subpools will "belong" to the same master whether they are
implemented as belonging to the subpool object or whether they are implemented
as belonging to the access type.

For tasks, the ordering of the elaboration of the entities is irrelevant; all
tasks "belonging" to a master are awaited at once. So we need do nothing special
for this case.

For controlled objects, they are finalized in the reverse order of their
elaboration. The collections of the access types are deemed to have elaborated
at the freezing point of the type. The storage pool object is finalized at the
point of its elaboration (which necessarily must be before the freezing point of
the access type; therefore it must finalize later). As noted previously, these
both have to be as part of the same master.

In order to allow the controlled objects to finalize with the storage pool
rather than the access type's collection, we add the following Implementation
Permission (added after 7.61(20)):

The implementation may finalize objects created by allocators for an access type
whose storage pool supports subpools (see 13.11.4) as if the objects were
created (in an arbitrary object) at the point where the storage pool was
elaborated rather instead of the first freezing point of the access type.

AARM Ramification: This allows the finalization of such objects to occur later
than they otherwise would, but still as part of the finalization of the same
master.

AARM Implementation Note: This permission is intended to allow the allocated
objects to "belong" to the subpool objects and to allow those objects to be
finalized at the time that the storage pool is finalized (if they are not
finalized earlier).

==============

The above is the easy part. The other issue is any special termination semantics
for tasks in for Unchecked_Deallocate_Subpool. Let me start with some Bairdian
free association.

(1) Steve was worried about nested tasks of a task that is waiting on a
    terminate alternative. These are not a (language) problem (or no more so
    than they are in other Ada code). The selection of a terminate alternative
    makes a task immediately completed (NOT terminated). After the task is
    completed (whether by the selection of a terminate alternative or simply by
    reaching the end of the code), task waiting and other finalizations proceeds
    normally.

(2) Because tasks that are waiting on a terminate alternative have to wait on
    tasks and finalize, they can take arbitrarily long to actually terminate. Of
    course, this is under control of the user; they don't have to write nested
    tasks and finalization that blocks. ;-)

(3) It seems to me that if we are going to do something special for
    Unchecked_Deallocate_Subpool, we ought to consider doing the same for
    Unchecked_Deallocation. After all, these are essentially the same. Moreover,
    in both cases, access to the tasks from outside of themselves is erroneous
    (it has to be accomplished through a dangling pointer), so there can be no
    correct code that depends on such tasks continuing to wait and/or run.

(4) A task that is completed is essentially in the same state as one waiting on
    a terminate alternative (in that both have to complete finalization before
    terminating), other than the former is not waiting. Depending on the purpose
    of the rule, we may want to include completed tasks in it. Specifically, if
    the purpose is to allow implementations to free task memory sooner, then the
    same rule ought to be applied to both. (I admit I don't know what the
    purpose of this rule is, other than to make allocated tasks work more like
    you would expect.)

(5) I wonder if we need some sort of bounded error for all non-terminated tasks
    in subpools. That's because in the case of subpools, there is no way to
    suppress the deallocation of memory (doing it for the entire subpool would
    prevent the memory from getting freed until the pool goes away -- uggh). Or
    are we requiring that tasks are allocated independently of any other
    allocated memory? That seems limiting (especially as it means that tasks
    never get freed at all -- at least not until their master goes away). I
    recall a number of "bug" reports on this for Janus/Ada 83; I had to explain
    to people that the tasks continue to exist until the master goes away, and
    on 640K MS-DOS, you could run out of space for TCB's in a hurry. One hopes
    that we are not continuing that mistake...

OK, enough free association. Here's the latest version of the rule that Tucker
has proposed; this would appear in the Unchecked_Deallocate_Subpool text (I've
left the original Tucker text as alone as possible):

Otherwise, a call on Unchecked_Deallocate_Subpool causes following actions on
the subpool designated by Subpool:

* Any tasks allocated from the subpool that are waiting at an open terminate
  alternative are completed, then waiting for their termination;

* Then any of the objects allocated from the subpool that still exist are
  finalized in an arbitrary order;

* Finally, Subpool is set to null.

The first thing that strikes me about this rule is that it waits for the
termination (read finalization) of any tasks with open terminate alternatives.
But it *doesn't* wait for any tasks that are already completed but have not yet
finished their finalization. I don't see any good reason for the difference.
Either not waiting for finalization is harmless, in which case neither ought to
do that; or it *does* eliminate problems, in which case both ought to do it. I
don't see any justification for a difference. Thus I suggest replacing the above
by:

Otherwise, a call on Unchecked_Deallocate_Subpool causes following actions on
the subpool designated by Subpool:

* Any tasks allocated from the subpool that are waiting at an open terminate
  alternative are completed;

* Next, the call waits for any completed tasks (including ones completed by the
  previous bullet) to complete their finalization;

* Then any of the objects allocated from the subpool that still exist are
  finalized in an arbitrary order;

* Finally, Subpool is set to null.

(If we decide to never wait, the second bullet can just be deleted.) I think I'm
in favor of waiting, because it definitely would reduce the bounded error
possibilities (the bounded error occurs when a nonterminated task with
discriminants is deallocated), and would allow the task storage to be freed in
more cases.

The question of whether to change the rules for Unchecked_Deallocation also come
up here. Waiting definitely would be an execution inconsistency (although almost
exclusively in terms of time). Making server tasks complete would also be
inconsistent, but only to the extent that the task's finalization does something
"interesting"; the interesting thing would happen earlier than it does now.

Either way, the main advantage to this rule would be to allow allocated server
tasks to shut down once they no longer can be accessed. That seems to be an
important thing to allow no matter how the tasks are deallocated. Waiting for
them to finalize is secondary and seems less important.

One could argue that for Unchecked_Deallocation, it would be easy enough to wait
for a task to terminate before freeing it (just write a loop on termination),
and it also would be easy enough to add a shutdown entry to call before
deallocating an object containing a task. That seems true, but it also seems to
mess up designs.

Also note that using the same semantics for both would make it easier to convert
from single deallocations to the use of a subpool or vice versa (much less
likely for there to be trouble).

Finally, it is clear that not having any termination semantics for subpools
would make it hard to deallocate memory. We seem to need something.

Summarizing the questions:

(1) What is the purpose of special rules for task termination?

(2) Do the special rules apply to both Unchecked_Deallocation and
    Unchecked_Deallocate_Subpool, or just the latter?

(3) Do the special rules apply to completed but not yet terminated tasks? To
    tasks waiting on a terminate alternative? To already terminated tasks?

(4) Do the special rules involve waiting for the completion of the finalization
    of the tasks (that is, the termination of the tasks)?

---

Tucker Taft:

One of the original goals was to support a mark/release approach to memory
management that properly handled finalization.  Clearly task waiting is tied up
with finalization, so I am reluctant to ignore the problem just because
Unchecked_Deallocation did so. With Unchecked_Deallocation, you are freeing just
one object, so it is feasible to do some amount of checking of the state, etc.,
if there might be an embedded task involved.  When freeing a whole subpool, that
isn't very practical.

So I don't feel a strong need to make these two kinds of deallocation consistent
as far as task waiting.

Another thing to mention is that the rules in 9.3(6-9) require that the tasks
not only be waiting at a terminate alternative, but that they be dependent on a
completed master all of whose dependents are either terminated or waiting on a
terminate alternative.  That means there can't be any subtasks that will need to
be awaited -- all that remains is finalization for the tasks waiting at
terminate alternatives.

So I think I would suggest we try to match the requirements of 9.3(6-9) in
AI05-0111-3.  Here are the current bullets from 111:

   * Any tasks allocated from the subpool desigated by Subpool that are
   waiting at an open terminate alternative are completed (see 9.2);

   * Next, the call waits for any completed tasks allocated from that subpool
   (including ones completed by the previous bullet) to complete their
   finalization;

   * Then any of the objects allocated from the subpool that still exist
   are finalized in an arbitrary order;

I would suggest the following:

   * Any task allocated from the subpool designated by Subpool that is
   waiting at an open terminate alternative and having all of its subtasks
   (if any) either completed or similarly waiting at an open terminate
   alternative, is completed;

   * Next, the call waits for any completed tasks allocated from that subpool
   (including ones completed by the previous bullet) to complete their
   finalization;

   * Then any of the objects allocated from the subpool that still exist
   are finalized in an arbitrary order;

  It is a bounded error if there are any tasks allocated from the subpool
  that are not terminated at this point (with the same bounds as
  for Unchecked_Deallocation).

This is actually pretty consistent with Unchecked_Deallocation, in that it only
waits for finalization to complete.  It doesn't wait for a task to complete that
isn't already "ready" to complete.  In practice, presumably you would throw in a
"delay 1.0" or something before doing an Unchecked_Deallocate_Subpool if there
were tasks involved, to give them a chance to reach their terminate
alternatives.  The nice thing is it allows terminate alternatives to "work" for
such tasks, which Unchecked_Deallocation doesn't allow.  But again, with
individual Unchecked_Deallocation, you could pretty easily call some "Shut_Down"
entry of the task before deallocating it.

---

Randy Brukardt:

> One of the original goals was to support a mark/release approach to
> memory management that properly handled finalization.  Clearly task
> waiting is tied up with finalization, so I am reluctant to ignore the
> problem just because Unchecked_Deallocation did so.
> With Unchecked_Deallocation, you are freeing just one object, so it is
> feasible to do some amount of checking of the state, etc., if there
> might be an embedded task involved.  When freeing a whole subpool,
> that isn't very practical.

Right, although if your have properly encapsulated types, it isn't very feasible
in either case (you'd have to export a "Before_UD_Call_This" operation, which is
nasty to an abstraction and doesn't work well when used as a component).

> So I don't feel a strong need to make these two kinds of deallocation
> consistent as far as task waiting.

I did think about that, but I came to the opposite conclusion. For me, the
current rules for Unchecked_Deallocation are not very good, and the only reason
for *not* fixing it is to avoid runtime inconsistency.

However, waiting for termination means waiting for finalization, and that
can block. (Note that finalization that blocks is not that unusual; finalization
of some Claw objects need to seize an exclusion lock, which can take a long time
if the program is incorrectly structured [Claw does have deadlock-breaking
timeouts on many entry calls, but those raise exceptions and only serve to
highlight a problem.])

That means that we probably can't apply the rules to Unchecked_Deallocation
(simply because there is a chance of deadlock, as might happen in Claw, and that
is too much inconsistency to stomach). I don't buy your rationalization for not
fixing Unchecked_Deallocation, but the inconsistency with Ada 95 and 2005 is a
sufficient reason.

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

From: Brad Moore
Sent: Sunday, March 13, 2011  12:12 AM

I hope its not too late to consider another storage pool proposal.
I think this one is quite a bit simpler, safer, and easier to use than the
previous proposals.

I have been experimenting with storage pools, and have implemented an Ada 2005
storage pool that is a wrapper around a popular C library that does provides
subpool and mark and release functionality. (Anyone interested in this can view
the source at https://sourceforge.net/projects/deepend/files/ )

This effort highlighted what is missing from Ada 2005, namely;
 1) Permitting early finalization of objects and tasks in the storage pool,
     using a mark-release strategy.
 2) Syntactic sugar to provide the storage pool object to the new operator.

My thought was to provide no more and no less than this functionality, which
ended up with the attached proposal.

To summarize the differences from the previous proposals.
  1) Subpools are not defined. I found that subpools are not needed for
      Mark and Release. They are useful however for extending the lifetime of a
      storage pool, however one you have the above missing functionality, it is
      easy for the storage pool writer to provide a subpool abstraction, if it
      is needed.
  2) Instead of subpools, we have dynamic storage pools, where the storage
      pool object can be dynamically specified using a similar syntax as the
     previous proposal, except instead of subpool handles, the storage pool
     objects are specified directly.
  3) Dynamic storage pools do not need to be associated with a root storage
      pool. They can be completely independent storage pools.
  4) There is no need to worry about dangling subpool handles. They don't
      exist.
  5) The storage pool implementer has more freedom in defining the
      abstraction for the storage management.
  6) Unchecked_Deallocate of the Dynamic Storage Pool does not release
      the storage of the pool. It only deallocates the objects in the pool.
      Freeing the memory of the pool can easily be provided by the
      storage pool writer if needed.
  7) The new package is much smaller than the subpools package. All
      that is provided is a new dynamic storage pool type, and a call to
      deallocate the objects in the pool.

Incidentally, I also found other uses for subpools and mark and release.
The pool I am interested in is intended to be very efficient. A precondition
guarantees that exactly one task can allocate from its subpool object abstraction.
This eliminates the need to worry about concurrency, as each task gets its own subpool to work with, that are chained together and finalized with a top
level storage pool, resulting in fast allocations. Each task can deallocate its
subpool independently of the other tasks.

======================

[Editor's note: Added '%' in front of '!' to avoid confusing tools and readers.]

%!standard 4.8(2)                         11-01-28 AI05-0111-4/01
%!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)
%!standard 13.11.6 (0)
%!class Amendment 10-10-13
%!status work item 10-10-13
%!status received 10-10-13
%!priority Medium
%!difficulty Hard

%!subject Dynamic pools, allocators, and control of finalization

%!summary

Dynamic pools are added to Ada.

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

%!proposal

Allow the storage pool object associated with an access type to be specified at
the point of the allocator, with the following syntax:

X := new (Dynamic_Pool) T'(ABC);

The objects allocated from a dynamic pool are reclaimed when
Unchecked_Deallocate is called. All of the objects in the dynamic pool are
finalized before the dynamic pool finalizes the storage.

%!wording

Modify 4.8(2) as follows:

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

dynamic_pool_specification ::= '(' dynamic_pool_name ')'

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

A dynamic_pool_name is expected to be the name of an object of any descendant of
System.Storage_Pools.Dynamic_Pools.Dynamic_Storage_Pool, the type representing
dynamic storage pools defined in the language-defined package
System.Storage_Pools.Dynamic_Pools (see 13.11.4).

Add after 7.6.1(20):

Implementation Permissions

The implementation may finalize objects created by allocators for an access type
whose storage pool supports dynamic pools (see 13.11.4) as if the objects were
created (in an arbitrary object) at the point where the storage pool was
elaborated instead of the first freezing point of the access type.

AARM Ramification: This allows the finalization of such objects to occur later
than they otherwise would, but still as part of the finalization of the same
master.

AARM Implementation Note: This permission is intended to allow the allocated
objects to "belong" to the dynamic pool objects and to allow those objects to be
finalized at the time that the dynamic storage pool is finalized (if they are
not finalized earlier). This is expected to ease implementation, as the objects
will only need to belong to the dynamic pool and not also the collection.

Modify 13.11(1):

Each access-to-object type has an associated storage pool. The storage
allocated by an allocator {of a type T without a dynamic_pool specification}
comes from this pool; instances of Unchecked_Deallocation return storage to the
pool. Several access types can share the same pool.

Modify 13.11(16/3):

An allocator of type T {without a dynamic_pool_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 dynamic_pool_specification allocates storage from the specified dynamic pool,
by calling Allocate as described below.

Add three new clauses:

13.11.4 Dynamic Storage Pools

This subclause defines a package to support the dynamic selection of the storage
pool to be associated with an allocator for an access type (see 4.8).

The following language-defined library package exists:

package System.Storage_Pools.Dynamic_Pools is

   pragma Preelaborate (System.Storage_Pools.Dynamic_Pools);

   type Dynamic_Storage_Pool is abstract new Root_Storage_Pool with private;
   -- An access type must have a storage pool of a type
   -- descended from this type to use dynamic storage pools.

   procedure Unchecked_Deallocate (Pool : in out Dynamic_Storage_Pool);
   --  Deallocates all objects in the pool. This does not actually release the
   --  storage of the pool, it just allows the storage to be reused for
   --  subsequent allocations.

private

... -- not specified by the language

end System.Storage_Pools.Dynamic_Pools;

A dynamic storage pool is a storage pool that can be reclaimed any number of
times prior to the finalization of the pool object.

Legality Rules

If a storage pool that supports dynamic pools is specified as the Storage_Pool
for an access type, the access type is called a dynamic pool access type. A
dynamic pool access type shall be a pool-specific access type.

The accessibility level of the dynamic pool access type shall not be statically
deeper than that of the storage pool object of the allocator.

Dynamic Semantics

When a dynamic pool access type is frozen (see 13.14), a check is made that the
accessibility level of the dynamic pool access type is not deeper than that of
its storage pool object. Program_Error is raised if this check fails.

When Allocate is called (see 13.11) for an allocator with a
dynamic_pool_specification, a check is made that the accessibility level of the
dynamic pool access type is not deeper than that of the storage pool object of
the allocator. Program_Error is raised if this check fails.

AARM Reason: These checks (and their static counterpart) ensures that the type
of the allocated objects exist at least as long as the storage pool object, so
that the dynamic pools 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 Dynamic Pool Reclamation

   procedure Unchecked_Deallocate (Pool : in out Dynamic_Storage_Pool);

The objects of a dynamic pool may be explicitly deallocated using
Unchecked_Deallocate.

A call on Unchecked_Deallocate has the following effects:

* Any task allocated from the pool that is waiting at an open terminate
  alternative and having all of its subtasks (if any) either completed or
  similarly waiting at an open terminate alternative, is completed;

* Next, the call waits for any completed tasks allocated from that pool
  (including ones completed by the previous bullet) to complete their
  finalization;

* Finally, any of the objects allocated from the subpool that still exist are
  finalized in an arbitrary order.

It is a bounded error if there are any tasks allocated from the pool that are
not terminated when the call to Unchecked_Deallocate is made. The possible
effects are as given for the unchecked deallocation of an object with a task
part (see 13.11.2).

Unchecked_Deallocate is a potentially blocking operation (see 9.5.1).

13.11.6 Storage Subpool Example

The following example is a simple but complete implementation of the classic
Mark/Release pool using dynamic pools:

   with System.Storage_Pools.Dynamic_Pools;
   with System.Storage_Elements;

   package MR_Pool is

      use System.Storage_Pools;
      --  [Note: For uses of Dynamic_Pools.]

      use System.Storage_Elements;
      --  [Note: For uses of Storage_Count and Storage_Array.]

      --  Mark and Release work in a stack fashion, and allocations are not
      --  allowed from a subpool other than the one at the top of the stack.
      --  This is also the default pool.

      type Mark_Release_Pool_Type (Pool_Size : Storage_Count) is new
         Dynamic_Pools.Dynamic_Storage_Pool with private;

      function Is_Released (Pool : Mark_Release_Pool_Type) return Boolean;

      function Mark (Pool : aliased in out Mark_Release_Pool_Type;
                     Pool_Size : Storage_Count := Storage_Count'Last)
                     return Mark_Release_Pool_Type;

      procedure Release (Pool : in out Mark_Release_Pool_Type)
         with Pre => not Is_Released (Pool);

   private

      type Mark_Release_Pool_Type (Pool_Size : Storage_Count) is new
        Dynamic_Pools.Dynamic_Storage_Pool with record
         Storage : Storage_Array (1 .. Pool_Size);
         Next_Allocation : Storage_Count := 1;
         Parent : access Mark_Release_Pool_Type := null;
         Child : access Mark_Release_Pool_Type := null;
         Released : Boolean := False;
      end record;

      overriding procedure Allocate
        (Pool : in out Mark_Release_Pool_Type;
         Storage_Address : out System.Address;
         Size_In_Storage_Elements : Storage_Count;
         Alignment : Storage_Count)
        with Pre => not Is_Released (Pool);

      overriding procedure Deallocate
        (Pool : in out Mark_Release_Pool_Type;
         Storage_Address : System.Address;
         Size_In_Storage_Elements : Storage_Count;
         Alignment : Storage_Count)
      is null;

      overriding function Storage_Size
        (Pool : Mark_Release_Pool_Type) return Storage_Count;

      --  Dont need Initialize

      overriding procedure Finalize
        (Pool : in out Mark_Release_Pool_Type)
      with Pre => Is_Released (Pool);

      function Is_Released (Pool : Mark_Release_Pool_Type) return Boolean is
      begin
         return Pool.Released;
      end Is_Release;

      function Storage_Size
        (Pool : Mark_Release_Pool_Type)
         return Storage_Count is
      begin
         return Pool.Pool_Size;
      end Storage_Size;

   end MR_Pool;

   package body MR_Pool is

      overriding procedure Finalize
        (Pool : in out Mark_Release_Pool_Type) is
      begin
         if Pool.Parent /= null then
            Pool.Parent.Child := null;
         end if;
      end Finalize;

      function Mark
        (Pool      : aliased in out Mark_Release_Pool_Type;
         Pool_Size : Storage_Count := Storage_Count'Last)
         return         Mark_Release_Pool_Type is
      begin
         return New_Pool : aliased Mark_Release_Pool_Type :=
              (Dynamic_Pools.Dynamic_Storage_Pool with
               Pool_Size       => Pool_Size,
               Storage         => <>,
               Next_Allocation => 1,
               Parent          => Pool'Unchecked_Access,
               Child           => null,
               Released        => False)
         do
            Pool.Child := New_Pool'Unchecked_Access;
         end return;

      end Mark;

      procedure Release (Pool : in out Mark_Release_Pool_Type) is
      begin
         Unchecked_Deallocate (Pool);
         Pool.Next_Allocation := 1;
         Pool.Released := True;
      end Release;

      procedure Allocate
        (Pool                     : in out Mark_Release_Pool_Type;
         Storage_Address          : out System.Address;
         Size_In_Storage_Elements : Storage_Count;
         Alignment                : Storage_Count) is
      begin
         if Pool.Child /= null then
            --  Can only allocate from the lowest scope
            raise Program_Error;
         end if;

         --  Correct the alignment if necessary:
         Pool.Next_Allocation :=
           Pool.Next_Allocation + ((-Pool.Next_Allocation) mod Alignment);

         if Pool.Next_Allocation +
              Size_In_Storage_Elements > Pool.Pool_Size then
            raise Storage_Error;
            --  Out of space.
         end if;

         Storage_Address      := Pool.Storage (Pool.Next_Allocation)'Address;
         Pool.Next_Allocation := Pool.Next_Allocation +
                                 Size_In_Storage_Elements;
      end Allocate;

   end MR_Pool;

[End 13.11.6.]

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

Modify 13.11(38):

As usual, a derivative of Root_Storage_Pool may define additional operations.
For example, [presuming that]{consider the} Mark_Release_Pool_Type {defined in
13.11.5, that} has two additional operations, Mark and Release, the following
is a possible use:

Delete the Block_Size discriminant from 13.11(39/1), and add a comment
"As defined in 13.11.5".

Replace 13.11(41) with

My_MR_Pool : aliased MR_Pool.Mark_Release_Pool_Type (Pool_Size => 2000);

Replace 13.11(43):

My_Mark : MR_Pool.Mark_Release_Pool_Type :=
   MR_Pool.Mark (Pool, Pool_Size => 1000); -- See 13.11.5

-- Allocate objects using "new (My_Mark) Designated(...)"
My_Mark.Release; ...
-- Allocate objects using "new (My_MR_Pool) Designated(...)"
My_MR_Pool.Release;

%!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 dynamic storage pools. The dynamic storage pool object type can also be
extended. So the implementor of the storage pool can keep some information
globally for the overall storage pool (by extending Dynamic_Storage_Pool), and
then some per subpool data structure (by extending the overall storage pool
object).

Meanwhile, the "root part" of the dynamic storage pool object type will be used
by the Ada implementation to implement task dependence and finalization for the
dynamic storage pools.

task TERMINATION MODEL

The basic model of task termination is unaltered; the tasks allocated from a
dynamic storage pool belong to the master of the access type. This works because
of the accessibility checks on the pool object - the pool object has to be in
the same scope as the access type. Moreover, all tasks for a given scope
terminate together, so it isn't possible to differentiate between them
"belonging" to the pool object or the access type.

Unchecked_Deallocation has no effect on task termination. This means that server
tasks embedded in a deallocated object may continue to wait at terminate
alternatives, even though they are no longer accessible. It is felt that it is
not a hardship for the client to call a 'shutdown' routine before deallocating
them (although such a requirement damages encapsulation).

However, this model does not work for dynamic storage pools. In order to call a
shutdown entry on each object, it would be necessary to enumerate all of the
contained objects (or at least those that need a shutdown routine called). That
would defeat the purpose of subpools (which is to support a mass deallocation of
all of the related objects without having to enumerate them).

Therefore, we adopt rules that have tasks allocated from a dynamic storage pool
that are waiting at a terminate alternative (with the same requirements as
9.3(3-6)) become completed, and then the finalization of all completed tasks is
waited for. This means that it is safe to deallocate a dynamic storage pool
containing tasks -- even if those tasks have discriminants -- so long as the
tasks are completed. For other tasks, this is a bounded error as it is for
Unchecked_Deallocation.

We considered adopting this rule for Unchecked_Deallocation as well, as it would
reduce the cases of bounded errors and the associated bugs. Unfortunately, it
could be inconsistent with the behavior of Ada 95 and Ada 2005 programs, as the
finalization could take a long time or even block. In extreme cases, deadlock is
possible. That seems like too much of an inconsistency to allow, so we do not
change the behavior of Unchecked_Deallocation.

FINALIZATION MODEL

Objects allocated into a dynamic storage pool will be finalized when the
dynamic storage pool is explicitly deallocated. If that never happens, the
objects can be finalized in the normal place for the access type, or the
implementation can finalize them when the pool is finalized.

Since the objects allocated into a dynamic storage pool 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.

One difference between this proposal and the previous one (AI05-0111-3) is
that an additional accessibility check is performed on each call to Allocate
for an allocator with a dynamic_pool_specification. This seemed like additional
distributed overhead compared to the previous proposal, but it is really no
different, because for that proposal, there needs to be some sort of check that
the subpool handle belongs to the correct storage pool.

Alternatives

The accessibility checks do 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 dynamic storage pools to
be used on access types with nested designated types and the like.
However, the implementation would be complex. An obvious implementation would
put dynamic storage pool 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 dynamic
storage pool keeps a separate finalization list for each access type, then only
the dynamic storage pool need be put on the access type's collection list. This
would complicate finalization somewhat, but only when dynamic storage pools 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 dynamic
storage pools.
Similar implementation complexity would also apply to task dependence. Because
of this complexity, we chose the simpler model.

USE AS A BUILDING BLOCK

This package provides facilities that can be used to provide safer abstractions.

One possibility would be to wrap the dynamic storage pool handle in a controlled
object that managed reference counting. When the count reached zero, the
dynamic storage pool would be automatically deallocated. This is basically the
idea of AI05-0111-2 (without the checks on the contained pointers).

%!example

See the example given in the !wording.
---
Another way that subpools can be used is to partition data. Imagine a
long-running web server for a retail establishment, which builds up in-memory
representations of historical customer information, current product information,
and each active customer's current shopping cart. There is a desire to be able
to reclaim this in-memory information when it has not been recently referenced.

However, the various representations are interlinked, such that a shopping cart
refers to the in-memory representation for the products it contains, and the
historical customer information and the current shopping cart might refer to
each other.

Although these representations might be made up of multiple heap objects, linked
into hash tables, sets, lists, trees, etc., reclamation generally happens at the
unit of an entire customer history, shopping cart, or product description, so
there is a desire to avoid individual object-by-object deallocation. Hence, we
would establish a separate subpool for each separately reclaimable item, namely
one for each customer historical record, one for each product description, and
one for each shopping cart.

%!ACATS test

Create ACATS C-Tests to test this facility.

%!ASIS
Some new ASIS routine needs to be added to handle the subpool syntax for allocators.
Details TBD. ***

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

From: Robert Dewar
Sent: Sunday, March 13, 2011  6:58 AM

> I hope its not too late to consider another storage pool proposal.
> I think this one is quite a bit simpler, safer, and easier to use than
> the previous proposals.

I must say I find this proposal attractive, up to now I have found the subpool
proposals over complex. Robert

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

From: Bob Duff
Sent: Sunday, March 13, 2011  8:29 AM

Anyway, Robert sent me the initial part of Brad's message (thanks!), so no need
to send it again.  But I still think it could be usefully moved into the
!discussion, as a contrast with the -3 version, and rationale for the diffs.

(Am I right that the -1 and -2 versions are pretty-much dead, and this -4
version should be seen as an alternative to -3?)

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

From: Brad Moore
Sent: Sunday, March 13, 2011  9:24 AM

> Brad, if you've got something useful to say about it, like why it's
> simpler than the -3 version, why not say so in the !discussion

Good point. I could resubmit with the high-level summary merged into the
discussion, though maybe I should wait until some more comments are received, in
the name of saving trees, or whatever it is that emails are made out of.

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

From: Brad Moore
Sent: Sunday, March 13, 2011  9:30 AM

> (Am I right that the -1 and -2 versions are pretty-much dead, and this
> -4 version should be seen as an alternative to -3?)
That is my understanding. The other two proposals have a status of no action.

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

From: Bob Duff
Sent: Sunday, March 13, 2011  10:02 AM

> I hope its not too late to consider another storage pool proposal.
> I think this one is quite a bit simpler, safer, and easier to use than
> the previous proposals.

How "safer"?

It would be worth explaining why Dynamic_Storage_Pool needs to be a separate
type from Root_Storage_Pool.  Is it just a boolean flag on an access type (if
its storage pool is a dynamic one, then the new syntax is allowed)?

Note: some of the following questions are really for Tucker, since they actually
come from the -3 version.

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

I very strongly disagree with the last sentence above, which has now propagated
from the -3 version to here.  Reclaiming them all at once is MUCH safer. I have
a lot of experience to prove that.  I suggest:

    This can create dangling pointers, as can Unchecked_Deallocation.
    However, managing entire groups of objects at once is much
    less error prone.  It is also likely to be much more efficient.

Randy, if nobody objects, could you fix it in both versions of the AI, before
somebody creates the -5 one?!

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

There are several occurrences of "subpool", including the one above.  Did you
intend to replace them all with "dynamic pool"?

> dynamic_pool_specification ::= '(' dynamic_pool_name ')'
>
> Add at the end of 4.8(3/1):
>
> A dynamic_pool_name is expected to be the name of an object of any
> descendant of System.Storage_Pools.Dynamic_Pools.Dynamic_Storage_Pool,
> the type representing dynamic storage pools defined in the
> language-defined package System.Storage_Pools.Dynamic_Pools (see 13.11.4).
>
> Add after 7.6.1(20):
>
> Implementation Permissions
>
> The implementation may finalize objects created by allocators for an
> access type whose storage pool supports dynamic pools (see 13.11.4) as
> if the objects were created (in an arbitrary object) at the point
> where the storage pool was

"object" --> "order".

> elaborated instead of the first freezing point of the access type.

The notion of "pool supports dynamic pools" made more sense in the -3 version.
Here, it seems to be just a property of the access type.

But I don't understand why this is a permission.  Finalize of the pool is
(presumably) going to deallocate memory, so don't we need to REQUIRE finalizing
the pool components first?

...
> 13.11.4 Dynamic Storage Pools
>
> This subclause defines a package to support the dynamic selection of
> the storage pool to be associated with an allocator for an access type (see 4.8).
>
> The following language-defined library package exists:
>
> package System.Storage_Pools.Dynamic_Pools is
>
>    pragma Preelaborate (System.Storage_Pools.Dynamic_Pools);
>
>    type Dynamic_Storage_Pool is abstract new Root_Storage_Pool with private;
>    -- An access type must have a storage pool of a type
>    -- descended from this type to use dynamic storage pools.
>
>    procedure Unchecked_Deallocate (Pool : in out Dynamic_Storage_Pool);
>    --  Deallocates all objects in the pool. This does not actually release the
>    --  storage of the pool, it just allows the storage to be reused for
>    --  subsequent allocations.

I don't understand this Unchecked_Deallocate.  Dynamic_Storage_Pool is abstract,
so Unchecked_Deallocate needs to be abstract, too, right? This package doesn't
know how to deallocate the memory -- that's the job of types that extend
Dynamic_Storage_Pool.  And "actually release storage" means exactly the same
thing as "allows the storage to be reused". I mean, deallocating storage doesn't
remove memory chips from the computer.  ;-)

I think you need a "magic" primitive that finalizes all the objects in the pool
(and waits for tasks?).  You can't free memory containing controlled objects
until they've been finalized!  (Well, unless you make it erroneous.)

> private
>
> ... -- not specified by the language
>
> end System.Storage_Pools.Dynamic_Pools;
>
> A dynamic storage pool is a storage pool that can be reclaimed any
> number of times prior to the finalization of the pool object.
>
> Legality Rules
>
> If a storage pool that supports dynamic pools is specified as the
> Storage_Pool for an access type, the access type is called a dynamic
> pool access type. A dynamic pool access type shall be a pool-specific access
> type.

Why "pool-specific"?

> The accessibility level of the dynamic pool access type shall not be
> statically deeper than that of the storage pool object of the allocator.
>
> Dynamic Semantics
>
> When a dynamic pool access type is frozen (see 13.14), a check is made
> that the accessibility level of the dynamic pool access type is not
> deeper than that of its storage pool object. Program_Error is raised if this check fails.
>
> When Allocate is called (see 13.11) for an allocator with a
> dynamic_pool_specification, a check is made that the accessibility
> level of the dynamic pool access type is not deeper than that of the
> storage pool object of the allocator. Program_Error is raised if this check fails.
>
> AARM Reason: These checks (and their static counterpart) ensures that
> the type of the allocated objects exist at least as long as the
> storage pool object, so that the dynamic pools 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.

Last sentence seems backwards.  Or am I confused?

> 13.11.5 Dynamic Pool Reclamation
>
>    procedure Unchecked_Deallocate (Pool : in out Dynamic_Storage_Pool);
>
> The objects of a dynamic pool may be explicitly deallocated using
> Unchecked_Deallocate.
>
> A call on Unchecked_Deallocate has the following effects:

Ah, here's the magic.  Shouldn't this thing dispatch to a user-overridden
deallocation routine?  Or else this should be called Finalize_Pool_Components or
something.

> * Any task allocated from the pool that is waiting at an open terminate
>   alternative and having all of its subtasks (if any) either completed or
>   similarly waiting at an open terminate alternative, is completed;
>
> * Next, the call waits for any completed tasks allocated from that pool
>   (including ones completed by the previous bullet) to complete their
>   finalization;
>
> * Finally, any of the objects allocated from the subpool that still exist are
>   finalized in an arbitrary order.
>
> It is a bounded error if there are any tasks allocated from the pool
> that are not terminated when the call to Unchecked_Deallocate is made.
> The possible effects are as given for the unchecked deallocation of an
> object with a task part (see 13.11.2).

That last paragraph contradicts the previous bullets, no?

> Unchecked_Deallocate is a potentially blocking operation (see 9.5.1).

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

From: Bob Duff
Sent: Sunday, March 13, 2011  10:06 AM

> (Anyone interested in this can view the source at
> https://sourceforge.net/projects/deepend/files/ )

OK, here's a code review.

What does "deepend" stand for?

> --  A Mark and Release Storage pool that provides a binding to the
> --  Apache Runtime Pools Implementation. In addition to Mark and
> --  Release memory management, the Storage pool also provides
> --  Subpool capabilities.

This is a nice pool implementation.  But it's not a mark/release pool
-- there's no Mark operation, and Release just deallocates everything.

A mark/release pool allows you to do Mark/Release in a properly-nested
(stacklike) way, and Release releases back to the most recent Mark.
I don't like mark/release pools.  I prefer the way you've done it here, where
subpools can be freed at will -- I just think the name is wrong.

>    type Mode_Kinds is
>      (Auto_Unchecked_Deallocation,
>       Manual_Unchecked_Deallocation);
>    --  Auto_Unchecked_Deallocation Mode permits the root storage pool to
>    --  finalize without an explicit call to Unchecked_Pool_Deallocation.
>    --
>    --  Manual_Unchecked_Deallocation Mode requires that an explicit call to
>    --  Unchecked_Pool_Deallocation be made before the storage pool is
>    --  finalized.

I don't understand the need for the two modes.

>    type Unbounded_Mark_Release_Pool
>      (Mode : Mode_Kinds;
>       Declaring_Task_Allocates : Boolean) is new
>      System.Storage_Pools.Root_Storage_Pool with private;

Need a comment explaining Declaring_Task_Allocates.

Apparently, it controls whether the initial owner is the current task, or null.
So why not have a discriminant:

    Initial_Owner : Ada.Task_Identification.Task_Id := Current_Task

?

>    overriding function Storage_Size
>      (Pool : Unbounded_Mark_Release_Pool)
>       return System.Storage_Elements.Storage_Count;
>
>    pragma Precondition (not Is_Finalized (Pool));
>
>    overriding procedure Allocate
>      (Pool         : in out Unbounded_Mark_Release_Pool;
>       Address      : out System.Address;
>       Storage_Size : System.Storage_Elements.Storage_Count;
>       Alignment    : System.Storage_Elements.Storage_Count);
>
>    pragma Precondition (not Is_Finalized (Pool) and
>                           Is_Owner (Pool, Current_Task));
>    --  Allocate must be called by the task that created the Pool or Subpool.
>    --  The pool may be a subpool of a pool owned by a different task
>    --  however.
>
>    overriding procedure Deallocate
>      (Pool         : in out Unbounded_Mark_Release_Pool;
>       Address      : System.Address;
>       Storage_Size : System.Storage_Elements.Storage_Count;
>       Alignment    : System.Storage_Elements.Storage_Count)
>    is null;
>    --  Deallocate is not meant to be called, so it has no effect.
>    --  This is a mark-release pool, Deallocation occurs when the
>    --  Storage pool object is finalized (or when Release is called).
>    --  The nice thing about this, there is no need to use
>    --  Unchecked_Deallocation.

OK, but I think this should have the same precondition as Allocate.
You might have a different pool type where Deallocate actually does something,
so it would be helpful if the interface is as similar as possible.

>    procedure Release
>      (Pool : in out Unbounded_Mark_Release_Pool);
>    --  Releases all memory in the pools. This does not actually free the
>    --  memory, it just allows the memory to be reused for subsequent
>    --  allocations.

I find that a little confusing, because from the point of view of the client, it
DOES free.  Maybe add "not free ... as seen by Apache" or something.  Now I see
where this came from -- it really doesn't belong in the AI, at least not in this
form.

>    pragma Precondition (not Is_Finalized (Pool) and
>                           Is_Owner (Pool, Current_Task));
>
>    function Create_Subpool
>      (Parent : Unbounded_Mark_Release_Pool) return Unbounded_Mark_Release_Pool;
>    --  The lifetime of a subpool is the same as that of its parent pool.
>    --
>    --  This function is thread-safe, in the sense that multiple tasks
>    --  can safely create subpools of the same parent pool concurrently.
>    --  Similarly, a subpool can be created by one task at the same
>    --  time that another thread accesses the parent pool.
>
>    pragma Compile_Time_Warning
>      (True,
>       "For Ada 2012, use in out parameter instead of in");
>
>    pragma Precondition (not Is_Finalized (Parent));
>    pragma Postcondition (not Is_Finalized (Create_Subpool'Result) and
>                         Is_Ancestor (Parent, Create_Subpool'Result));
>
>    procedure Unchecked_Subpool_Deallocation
>      (Pool : in out Unbounded_Mark_Release_Pool);
>
>    pragma Precondition (not Is_Finalized (Pool) and
>                           Is_Owner (Pool, Current_Task));
>    pragma Postcondition (Is_Finalized (Pool));
>
>    function Is_Ancestor
>      (Ancestor, Child : Unbounded_Mark_Release_Pool) return Boolean;
>    --  Returns True is Ancestor is an ancestor of Child

"is" --> "if".

>    pragma Precondition (not Is_Finalized (Ancestor) and
>                         not Is_Finalized (Child));
>
>    function Is_Finalized
>      (Pool : Unbounded_Mark_Release_Pool) return Boolean;
>
>    function Is_Owner
>      (Pool : Unbounded_Mark_Release_Pool;
>       T : Task_Id := Current_Task) return Boolean;

If you're going to have a default for T, why not use it in the preconditions?

>    pragma Precondition (not Is_Finalized (Pool));
>
>    procedure Set_Owner
>      (Pool : in out Unbounded_Mark_Release_Pool;
>       T : Task_Id := Current_Task);
>
>    pragma Precondition (Is_Owner (Pool, Null_Task_Id));
>    pragma Postcondition (Is_Owner (Pool, Current_Task));

That postcondition doesn't seem right -- it only works if T defaults.

>    generic
>       type Allocation_Type is private;
>       type Allocation_Type_Access is access Allocation_Type;
>    function Allocation
>      (Pool : access Unbounded_Mark_Release_Pool) return
> Allocation_Type_Access;
>
>    pragma Compile_Time_Warning
>      (True,
>       "For Ada 2012, use in out parameter instead of access");

GNAT supports a lot of Ada 2012 now, I think including this feature.
Maybe you should switch.

Comment: Allocation_Type has to be definite.  At least, I don't think it works
for indefinite types.  And it won't work for fat pointers.

>    --  This generic routine provides a mechanism to allocate from a subpool.
>    --  The "new" has to be associated with the root storage pool, and currently
>    --  there is no way to override the storage pool object for the "new"
>    --  operator.
>    --
>    --  This function allows the storage pool object to be specified, which
>    --  may be either the root pool object, or any subpool object.
>
> --     generic
> --        type Allocation_Type is private;
> --        type Allocation_Type_Access is access Allocation_Type;
> --     procedure Allocation_Proc
> --       (Pool : in out Unbounded_Mark_Release_Pool;
> --        New_Item : out Allocation_Type_Access);

Shouldn't New_Item be 'in' instead of 'out'?
And why is it commented out?  It seems useful to be able to do an initialized
allocator.

> private
>
>    type Unbounded_Mark_Release_Pool
>      (Mode : Mode_Kinds;
>       Declaring_Task_Allocates : Boolean) is
>      new System.Storage_Pools.Root_Storage_Pool with
>       record
>          Pool : Apache_Runtime.Pools.Pool_Type;
>          Is_A_Subpool : Boolean;
>          Owner : Ada.Task_Identification.Task_Id;
>       end record;
>
>    overriding procedure Initialize (Item : in out Unbounded_Mark_Release_Pool);
>
>    pragma Postcondition (not Item.Is_A_Subpool);
>
>    overriding procedure Finalize   (Item : in out Unbounded_Mark_Release_Pool);
>
>    pragma Precondition
>      (Item.Mode = Auto_Unchecked_Deallocation or
>         Item.Pool = System.Null_Address or Item.Is_A_Subpool);

Seems like this precondition should be in the visible part (at least as a
comment).  I'm not sure I understand the rationale, though.

>    pragma Inline (Storage_Size, Allocate, Create_Subpool, Release);
>    pragma Inline (Is_Ancestor, Is_Finalized, Is_Owner, Set_Owner);
> --     pragma Inline (Get_Parent);
>
> end Pool_Mark_Release;


> package body Pool_Mark_Release is

>    function Allocation
>      (Pool : access Unbounded_Mark_Release_Pool)
>       return Allocation_Type_Access
>    is
>       function Convert is new Ada.Unchecked_Conversion
>         (Source => System.Address,
>          Target => Allocation_Type_Access);
>    begin
>       pragma Assert (not Is_Finalized (Pool.all) and
>                        Is_Owner (Pool.all, Current_Task));
>       return Convert
>         (Apache_Runtime.Pools.Allocate
>            (Pool => Pool.all.Pool,
>             Size => Apache_Runtime.Apr_Size
>               (Allocation_Type'Size / Interfaces.Unsigned_8'Size)));

Shouldn't you use 'Max_Size_In_Storage_Elements here?

>    end Allocation;

>    function Create_Subpool
>      (Parent : Unbounded_Mark_Release_Pool)
>       return Unbounded_Mark_Release_Pool
>    is
>       use type Apache_Runtime.Apr_Status;
>    begin
>       return  New_Pool : Unbounded_Mark_Release_Pool
>         := (System.Storage_Pools.Root_Storage_Pool with
>             Mode => Auto_Unchecked_Deallocation,
>             Declaring_Task_Allocates => True,
>             Pool => System.Null_Address,
>             Owner => Ada.Task_Identification.Current_Task,
>             Is_A_Subpool => True)
>       do
>
>          if Apache_Runtime.Pools.Create
>           (New_Pool => New_Pool.Pool'Address,
>            Parent   => Parent.Pool) /= 0 then
>             raise Storage_Error;
>          end if;
>          New_Pool.Is_A_Subpool := True;

That last statement is redundant -- the aggregate already set it.

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

From: Bob Duff
Sent: Sunday, March 13, 2011  11:00 AM

A couple more comments:

> >    generic
> >       type Allocation_Type is private;
> >       type Allocation_Type_Access is access Allocation_Type;
> >    function Allocation
> >      (Pool : access Unbounded_Mark_Release_Pool) return
> > Allocation_Type_Access;

Shouldn't Allocation_Type be limited?

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

From: Bob Duff
Sent: Sunday, March 13, 2011  11:02 AM

Does Ada 2012 have anything like C++ "placement new"?
I think you can do it by trickery in Ada 2005, but it's pretty ugly.  Maybe we
could add it to AI-111 (whichever version). It's pretty trivial, and very
useful.

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

From: Brad Moore
Sent: Sunday, March 13, 2011  11:42 AM

>> I hope its not too late to consider another storage pool proposal.
>> I think this one is quite a bit simpler, safer, and easier to use
>> than the previous proposals.
> How "safer"?

For one, the previous version talks about having to worry about dangling subpool
handles. This proposal doesnt involve access handles to pool objects, so there
is no such thing as a subpool handle, let alone a dangling one.

> It would be worth explaining why Dynamic_Storage_Pool needs to be a
> separate type from Root_Storage_Pool.  Is it just a boolean flag on an
> access type (if its storage pool is a dynamic one, then the new syntax is allowed)?

I agree. Basically though a Root_Storage_Pool doesn't expose any way to early
finalize the objects in the storage pool. A dynamic storage pool exposes the
Unchecked_Deallocate call, which is supposed to be able to do this, based on
some implementation specific components in the Dynamic_Storage pool abstract
type.

> Note: some of the following questions are really for Tucker, since
> they actually come from the -3 version.
>
>> ...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).
> I very strongly disagree with the last sentence above, which has now
> propagated from the -3 version to here.  Reclaiming them all at once is MUCH safer.
> I have a lot of experience to prove that.  I suggest:
>
>      This can create dangling pointers, as can Unchecked_Deallocation.
>      However, managing entire groups of objects at once is much
>      less error prone.  It is also likely to be much more efficient.
>
> Randy, if nobody objects, could you fix it in both versions of the AI,
> before somebody creates the -5 one?!

I agree. It is certainly not "exactly" as safe.

>> allocator ::=
>> new [dynamic_pool_specification] subtype_indication
>> | new [subpool_specification] qualified_expression
> There are several occurrences of "subpool", including the one above.
> Did you intend to replace them all with "dynamic pool"?
>
Yes, I must have missed a few. They should all be dynamic storage pool.

>> dynamic_pool_specification ::= '(' dynamic_pool_name ')'
>>
>> Add at the end of 4.8(3/1):
>>
>> A dynamic_pool_name is expected to be the name of an object of any
>> descendant of
>> System.Storage_Pools.Dynamic_Pools.Dynamic_Storage_Pool, the type
>> representing dynamic storage pools defined in the language-defined package System.Storage_Pools.Dynamic_Pools (see 13.11.4).
>>
>> Add after 7.6.1(20):
>>
>> Implementation Permissions
>>
>> The implementation may finalize objects created by allocators for an
>> access type whose storage pool supports dynamic pools (see 13.11.4)
>> as if the objects were created (in an arbitrary object) at the point
>> where the storage pool was
> "object" -->  "order".

Agree

>> elaborated instead of the first freezing point of the access type.
> The notion of "pool supports dynamic pools" made more sense in the -3 version.
> Here, it seems to be just a property of the access type.
>
> But I don't understand why this is a permission.  Finalize of the pool
> is
> (presumably) going to deallocate memory, so don't we need to REQUIRE
> finalizing the pool components first?

I think the point of this is that the objects in the storage pool don't
necessarily have to be finalized exactly when the access type is finalized, it
can be finalized as part of finalizing the storage pool object, which should be
very close to when the access type is finalized. In any case, the pool
components still need to be finalized before the pool. Hopefully that is implied
from the wording.

...
>>     procedure Unchecked_Deallocate (Pool : in out Dynamic_Storage_Pool);
>>     --  Deallocates all objects in the pool. This does not actually release the
>>     --  storage of the pool, it just allows the storage to be reused for
>>     --  subsequent allocations.
> I don't understand this Unchecked_Deallocate.  Dynamic_Storage_Pool is
> abstract, so Unchecked_Deallocate needs to be abstract, too, right?

It shouldn't need to be abstract. If the vendor implementation can put
components in the abstract object, why cant the Unchecked_Deallocate operate on
those components? For example some sort of finalization list could be in the
object, and Unchecked_Deallocate could operate on that list.

> This package doesn't know how to deallocate the memory -- that's the
> job of types that extend Dynamic_Storage_Pool.  And "actually release
> storage" means exactly the same thing as "allows the storage to be reused".
> I mean, deallocating storage doesn't remove memory chips from the
> computer.  ;-)

I probably should state instead that the storage associated with the pool is not
released to the system. Thats another difference between this proposal and -3.
That one frees the storage of the pool, and sets the subpool handle to null.

> I think you need a "magic" primitive that finalizes all the objects in
> the pool (and waits for tasks?).  You can't free memory containing
> controlled objects until they've been finalized!  (Well, unless you
> make it erroneous.)

I dont see why Unchecked_Deallocate couldnt do this.

...
>> Legality Rules
>>
>> If a storage pool that supports dynamic pools is specified as the
>> Storage_Pool for an access type, the access type is called a dynamic
>> pool access type. A dynamic pool access type shall be a pool-specific access type.
> Why "pool-specific"?

Good point. This was a carry over from the -3 proposal. With subpools that made
more sense because subpools had to come from the same storage pool. With dynamic
storage pools, you can use completely different pools, so I dont think we need
this restriction with this proposal.

>> AARM Reason: These checks (and their static counterpart) ensures that
>> the type of the allocated objects exist at least as long as the
>> storage pool object, so that the dynamic pools 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.
> Last sentence seems backwards.  Or am I confused?

I think I agree (but not sure). We have permissions to allow the finalization of
objects of the access type to occur later, when the storage pool is being
finalized. So, I guess that means the access type has to cease to exist right
after the finalization of the storage pool.

>> 13.11.5 Dynamic Pool Reclamation
>>
>>     procedure Unchecked_Deallocate (Pool : in out
>> Dynamic_Storage_Pool);
>>
>> The objects of a dynamic pool may be explicitly deallocated using
>> Unchecked_Deallocate.
>>
>> A call on Unchecked_Deallocate has the following effects:
> Ah, here's the magic.  Shouldn't this thing dispatch to a
> user-overridden deallocation routine?  Or else this should be called
> Finalize_Pool_Components or something.

Unchecked_Deallocate is a primitive subprogram, so it can be overridden by the
user. Is that what you mean?

>> * Any task allocated from the pool that is waiting at an open terminate
>>    alternative and having all of its subtasks (if any) either completed or
>>    similarly waiting at an open terminate alternative, is completed;
>>
>> * Next, the call waits for any completed tasks allocated from that pool
>>    (including ones completed by the previous bullet) to complete their
>>    finalization;
>>
>> * Finally, any of the objects allocated from the subpool that still exist are
>>    finalized in an arbitrary order.
>>
>> It is a bounded error if there are any tasks allocated from the pool
>> that are not terminated when the call to Unchecked_Deallocate is
>> made. The possible effects are as given for the unchecked
>> deallocation of an object with a task part (see 13.11.2).
> That last paragraph contradicts the previous bullets, no?

I think it should say "not completed and not blocked at a select_statement with
an open terminate_alternative" instead of "not terminated"

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

From: Tucker Taft
Sent: Sunday, March 13, 2011  12:06 PM

I haven't studied this in depth,
but some of the complexity of other
proposals relates to issues such as conversion, explicit unchecked deallocation,
anonymous access types, etc.

One reason for the subpool notion was that if you allow multiple unrelated
storage pools to be used with a single access type, you lose any way of
distinguishing values designating objects allocated from distinct storage pools.

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

From: Bob Duff
Sent: Sunday, March 13, 2011  12:17 PM

> I haven't studied this in depth,
> but some of the complexity of other
> proposals relates to issues such as conversion, explicit unchecked
> deallocation, anonymous access types, etc.

Maybe Brad should update based on my comments, and THEN you should study it.
What do you think, Brad?

> One reason for the subpool notion was that if you allow multiple
> unrelated storage pools to be used with a single access type, you lose
> any way of distinguishing values designating objects allocated from
> distinct storage pools.

I don't understand what you mean by that.  Distinguishing at compile time?  At
run time?

Some of these proposals had an operation that asks "what [sub]pool is this
object allocated in?", presumably based on address trickery and BiBOP.  Why did
that disappear from -3 and -4?  Do we need it?  Is it related to whatever you
meant by "distinguishing" above?

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

From: Brad Moore
Sent: Sunday, March 13, 2011  12:36 PM

>> (Anyone interested in this can view the source at
>> https://sourceforge.net/projects/deepend/files/ )
> OK, here's a code review.

Thanks for the review. It's been quite some time since anyone has reviewed my
Ada code. Especially a topnotch Ada expert ;-).

> What does "deepend" stand for?
Its kind of a cutesy name. It could stand for;

   1) A pool has to be pretty deep if it is to have subs floating in it.
   2) Hopefully it can be used to write deependable software.
   3) Hopefully it doesn't mean this is something the author has gone off of.

I should add this to the README
>> --  A Mark and Release Storage pool that provides a binding to the
>> --  Apache Runtime Pools Implementation. In addition to Mark and
>> --  Release memory management, the Storage pool also provides
>> --  Subpool capabilities.
>
> This is a nice pool implementation.  But it's not a mark/release pool
> -- there's no Mark operation, and Release just deallocates everything.
>
> A mark/release pool allows you to do Mark/Release in a properly-nested
> (stacklike) way, and Release releases back to the most recent Mark.
> I don't like mark/release pools.  I prefer the way you've done it
> here, where subpools can be freed at will -- I just think the name is
> wrong.

Good point. I'm not sure what you'd call this type of pool then. You could use
it in a stack-like way to do mark-release, but as you say, you can use it in
other ways that go beyond the abstraction of mark release.

Incidentally, I have a test program that was written to test a binary tree
benchmark, for a computer language shootout, based on some discusson on
comp.lang.ada.

http://shootout.alioth.debian.org/u32/benchmark.php?test=binarytrees&lang=all

The current submission has Ada in the 21st place spot.

My thought was to use the same library that the no. 1 spot (written in C is
using), and see how Ada fared. I found that the Ada was comparable to the C
version. I then added some additional parallelism by having some of the trees
being created at the same time. I found then that the Ada time actually beat the
C program by about 10% faster. I submitted the program a couple of weeks ago,
but so far haven't seen any change in the standings. Hopefully when they get
around to updating the website, Ada will be in the no. 1 spot for this test.

Incidentally, I tried running the same program using the default GNAT storage
pool, and the times were way off the map.

I can really see the advantage of using such a pool. I'm thinking I would
probably want to use this sort of pool as the default for all new projects I
work on. It's nice not having to have any Unchecked_Deallocation calls.

If you are interested, I could send you the binary tree benchmark test code.
>>     type Mode_Kinds is
>>       (Auto_Unchecked_Deallocation,
>>        Manual_Unchecked_Deallocation);
>>     --  Auto_Unchecked_Deallocation Mode permits the root storage pool to
>>     --  finalize without an explicit call to Unchecked_Pool_Deallocation.
>>     --
>>     --  Manual_Unchecked_Deallocation Mode requires that an explicit call to
>>     --  Unchecked_Pool_Deallocation be made before the storage pool is
>>     --  finalized.
> I don't understand the need for the two modes.
>
I think you would almost always want Auto_Unchecked_Deallocation. I was thinking
that there might be some who would want to see explicit calls to
Unchecked_Deallocate to acknowledge that any unchecked deallocating that is
occurring was intentional by the programmer.

>>     type Unbounded_Mark_Release_Pool
>>       (Mode : Mode_Kinds;
>>        Declaring_Task_Allocates : Boolean) is new
>>       System.Storage_Pools.Root_Storage_Pool with private;
> Need a comment explaining Declaring_Task_Allocates.

Agree

> Apparently, it controls whether the initial owner is the current task,
> or null.  So why not have a discriminant:

Because this would make the type mutable, as the other discrimants dont have
defaults. I'm not sure that matters much though. I like your suggestion. I will
try it out.

>>     overriding function Storage_Size
>>       (Pool : Unbounded_Mark_Release_Pool)
>>        return System.Storage_Elements.Storage_Count;
>>
>>     pragma Precondition (not Is_Finalized (Pool));
>>
>>     overriding procedure Allocate
>>       (Pool         : in out Unbounded_Mark_Release_Pool;
>>        Address      : out System.Address;
>>        Storage_Size : System.Storage_Elements.Storage_Count;
>>        Alignment    : System.Storage_Elements.Storage_Count);
>>
>>     pragma Precondition (not Is_Finalized (Pool) and
>>                            Is_Owner (Pool, Current_Task));
>>     --  Allocate must be called by the task that created the Pool or Subpool.
>>     --  The pool may be a subpool of a pool owned by a different task
>>     --  however.
>>
>>     overriding procedure Deallocate
>>       (Pool         : in out Unbounded_Mark_Release_Pool;
>>        Address      : System.Address;
>>        Storage_Size : System.Storage_Elements.Storage_Count;
>>        Alignment    : System.Storage_Elements.Storage_Count)
>>     is null;
>>     --  Deallocate is not meant to be called, so it has no effect.
>>     --  This is a mark-release pool, Deallocation occurs when the
>>     --  Storage pool object is finalized (or when Release is called).
>>     --  The nice thing about this, there is no need to use
>>     --  Unchecked_Deallocation.
> OK, but I think this should have the same precondition as Allocate.
> You might have a different pool type where Deallocate actually does
> something, so it would be helpful if the interface is as similar as
> possible.

Good point

>>     procedure Release
>>       (Pool : in out Unbounded_Mark_Release_Pool);
>>     --  Releases all memory in the pools. This does not actually free the
>>     --  memory, it just allows the memory to be reused for subsequent
>>     --  allocations.
> I find that a little confusing, because from the point of view of the
> client, it DOES free.  Maybe add "not free ... as seen by Apache"
> or something.  Now I see where this came from -- it really doesn't
> belong in the AI, at least not in this form.

Well, the Unchecked_Deallocate of the AI essentially corresponds to this
procedure.

...
>>     function Is_Ancestor
>>       (Ancestor, Child : Unbounded_Mark_Release_Pool) return Boolean;
>>     --  Returns True is Ancestor is an ancestor of Child
> "is" -->  "if".
Agree

...
>>     function Is_Owner
>>       (Pool : Unbounded_Mark_Release_Pool;
>>        T : Task_Id := Current_Task) return Boolean;
> If you're going to have a default for T, why not use it in the
> preconditions?

You mean something like Pre => T /= Ada.Null_Task_Id?

>>     pragma Precondition (not Is_Finalized (Pool));
>>
>>     procedure Set_Owner
>>       (Pool : in out Unbounded_Mark_Release_Pool;
>>        T : Task_Id := Current_Task);
>>
>>     pragma Precondition (Is_Owner (Pool, Null_Task_Id));
>>     pragma Postcondition (Is_Owner (Pool, Current_Task));
> That postcondition doesn't seem right -- it only works if T defaults.
Agree, It should be T

>>     generic
>>        type Allocation_Type is private;
>>        type Allocation_Type_Access is access Allocation_Type;
>>     function Allocation
>>       (Pool : access Unbounded_Mark_Release_Pool) return Allocation_Type_Access;
>>
>>     pragma Compile_Time_Warning
>>       (True,
>>        "For Ada 2012, use in out parameter instead of access");
> GNAT supports a lot of Ada 2012 now, I think including this feature.
> Maybe you should switch.

I'm using the GPL version. Would that one have some of these features?

> Comment: Allocation_Type has to be definite.  At least, I don't think
> it works for indefinite types.  And it won't work for fat pointers.

Good to now. I should add that to the comments of the routine. I seem to recall
there is some GNAT attribute that indicates whether the type is definite. Maybe
I could use that attribute in a precondition. Actually, I think I tried using
the precondition pragma on a generic function and it didn't work, but maybe I
can still use it as an assert in the body.

>>     --  This generic routine provides a mechanism to allocate from a subpool.
>>     --  The "new" has to be associated with the root storage pool, and currently
>>     --  there is no way to override the storage pool object for the "new"
>>     --  operator.
>>     --
>>     --  This function allows the storage pool object to be specified, which
>>     --  may be either the root pool object, or any subpool object.
>>
>> --     generic
>> --        type Allocation_Type is private;
>> --        type Allocation_Type_Access is access Allocation_Type;
>> --     procedure Allocation_Proc
>> --       (Pool : in out Unbounded_Mark_Release_Pool;
>> --        New_Item : out Allocation_Type_Access);
> Shouldn't New_Item be 'in' instead of 'out'?
> And why is it commented out?  It seems useful to be able to do an
> initialized allocator.

Makes sense.

...
>>     overriding procedure Finalize   (Item : in out Unbounded_Mark_Release_Pool);
>>
>>     pragma Precondition
>>       (Item.Mode = Auto_Unchecked_Deallocation or
>>          Item.Pool = System.Null_Address or Item.Is_A_Subpool);
> Seems like this precondition should be in the visible part (at least
> as a comment).  I'm not sure I understand the rationale, though.
>
The idea is to catch cases where the pool must be explicitly deallocated for the
Manual_Unchecked_Deallocation mode. If the pool is a subpool of another pool,
its lifetime is extended to the parent pool, so the finalization does nothing
and is allowed. The finalization of the parent will finalize the children. So
long as the parent is explicitly Deallocated before it is finalized, it
satisfies the contract. This should be a visible comment though, as you say.

...
>> package body Pool_Mark_Release is
>>     function Allocation
>>       (Pool : access Unbounded_Mark_Release_Pool)
>>        return Allocation_Type_Access
>>     is
>>        function Convert is new Ada.Unchecked_Conversion
>>          (Source =>  System.Address,
>>           Target =>  Allocation_Type_Access);
>>     begin
>>        pragma Assert (not Is_Finalized (Pool.all) and
>>                         Is_Owner (Pool.all, Current_Task));
>>        return Convert
>>          (Apache_Runtime.Pools.Allocate
>>             (Pool =>  Pool.all.Pool,
>>              Size =>  Apache_Runtime.Apr_Size
>>                (Allocation_Type'Size / Interfaces.Unsigned_8'Size)));
> Shouldn't you use 'Max_Size_In_Storage_Elements here?

Yes

...
>>           if Apache_Runtime.Pools.Create
>>            (New_Pool =>  New_Pool.Pool'Address,
>>             Parent   =>  Parent.Pool) /= 0 then
>>              raise Storage_Error;
>>           end if;
>>           New_Pool.Is_A_Subpool := True;
> That last statement is redundant -- the aggregate already set it.

Agree

Thanks again for your comments. I will update when I get a chance.

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

From: Brad Moore
Sent: Sunday, March 13, 2011  12:48 PM

>>>     generic
>>>        type Allocation_Type is private;
>>>        type Allocation_Type_Access is access Allocation_Type;
>>>     function Allocation
>>>       (Pool : access Unbounded_Mark_Release_Pool) return
>>> Allocation_Type_Access;
> Shouldn't Allocation_Type be limited?

I don't think so. I want to be able to use this to allocate any kind of type,
not just limited types.

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

From: Brad Moore
Sent: Sunday, March 13, 2011  1:01 PM

>> I haven't studied this in depth,
>> but some of the complexity of other
>> proposals relates to issues such as conversion, explicit unchecked
>> deallocation, anonymous access types, etc.
> Maybe Brad should update based on my comments, and THEN you should
> study it.  What do you think, Brad?

Will do.

>> One reason for the subpool notion was that if you allow multiple
>> unrelated storage pools to be used with a single access type, you
>> lose any way of distinguishing values designating objects allocated
>> from distinct storage pools.
> I don't understand what you mean by that.  Distinguishing at compile
> time?  At run time?


I dont understand this well enough to comment.
Hopefully Tucker can provide an explanation of when this distinguishing would be
needed.

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

From: Bob Duff
Sent: Sunday, March 13, 2011  1:46 PM

> > A couple more comments:

Well, I had a couple, but I decided the second one was stupid, so I erased it.  ;-)

> > Shouldn't Allocation_Type be limited?
> >
> I don't think so. I want to be able to use this to allocate any kind
> of type, not just limited types.

If the formal is limited, the actual can be nonlimited, but not 'tother way
'round.

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

From: Bob Duff
Sent: Sunday, March 13, 2011  2:10 PM

> Its kind of a cutesy name.

I like it.

> Good point. I'm not sure what you'd call this type of pool then.

Well, it's based specifically on Apache, so I'd probably include that in the
name.

I did more-or-less the same thing in pure Ada, and I called it ... guess what?  "Subpool".  ;-)  Tucker hi-jacked the term for AI-111, to mean something rather different, but it makes sense in his sense, too.

>... I found then that the Ada time actually beat  the C program  by
>about 10% faster.

Very cool!

> Incidentally, I tried running the same program using the default GNAT
> storage pool, and the times were way off the map.

I've been meaning to add some useful pools to GNAT (probably in GNATCOLL), but I
never seem to get a round tuit.

> If you are interested, I could send you the binary tree benchmark test code.

Sure, but I won't promise I'll have time to look at it carefully.

> I think you would almost always want Auto_Unchecked_Deallocation. I
> was thinking that there might be some who would want to see explicit
> calls to Unchecked_Deallocate to acknowledge that any unchecked
> deallocating that is occurring was intentional by the programmer.

I see.  Makes sense.

>...So why not have a discriminant:
>
> Because this would make the type mutable, as the other discrimants
> dont have defaults.

Yeah, you'd have to pick a default for the other discrim.

But it won't be mutable, because the type is limited.
Note that defaults on discrims of tagged types are pretty new -- I don't
remember if GNAT has implemented that yet.

> I'm not sure that matters much though. I like your suggestion. I will
> try it out.

> >>     function Is_Owner
> >>       (Pool : Unbounded_Mark_Release_Pool;
> >>        T : Task_Id := Current_Task) return Boolean;
> > If you're going to have a default for T, why not use it in the
> > preconditions?
> >
> You mean something like Pre => T /= Ada.Null_Task_Id?
> >>     pragma Precondition (not Is_Finalized (Pool));

No, I meant that I saw some preconditions that say "Is_Owner(Pool,
Current_Task)".  If you think it's good to have a default for T, then you should
write "Is_Owner(Pool)".  If you DON'T think it's good, then you shouldn't have a
default.

I have no strong opinion one way or the other.
I'm usually wary of defaults, but I guess it's good in this case.

> I'm using the GPL version. Would that one have some of these features?

I don't know -- I have trouble keeping track of all the versions.
If not, the next one will.

> > Comment: Allocation_Type has to be definite.  At least, I don't
> > think it works for indefinite types.  And it won't work for fat pointers.
>
> Good to now. I should add that to the comments of the routine. I seem
> to recall there is some GNAT attribute that indicates whether the type
> is definite. Maybe I could use that attribute in a precondition.
> Actually, I think I tried using the precondition pragma on a generic
> function and it didn't work, but maybe I can still use it as an assert
> in the body.

Actually, I was confused when I wrote that.  You didn't say "(<>)"
(unknown discrims) so it won't allow indefinite actuals.
I suppose a comment explaining why wouldn't hurt (it needs to know the size, so
size must be the same for all objects of the subtype).

You could have another generic that works for unconstrained arrays.  This
proliferation of generics shows why we need AI-111-X!

> Thanks again for your comments.

You're welcome.  Did I mention that I have an inexplicable fascination with
memory management?

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

From: Bob Duff
Sent: Sunday, March 13, 2011  12:12 PM

I added a proper subject, by the way.
Best not to expect people to memorize AI numbers, I think.  ;-)

> > I hope its not too late to consider another storage pool proposal.
> >> I think this one is quite a bit simpler, safer, and easier to use
> >> than the previous proposals.
> > How "safer"?
> >
> For one, the previous version talks about having to worry about
> dangling subpool handles.
> This proposal doesnt involve access handles to pool objects, so there
> is no such thing as a subpool handle, let alone a dangling one.

Well, in practice a lot of programs are going to create dynamic pools / subpools
on the heap.  In fact, that means the package really ought to declare an
access-to-dynamic-pool'Class type. Which is what Subpool_Handle is in the -3
version.

_Handle seems like a wrong name, by the way.  To me, a handle is a pointer
(could be represented as an access type or an index into a table or ...), that
designates a limited private type -- that is, clients know it's a reference, but
should know what it points to.

> > But I don't understand why this is a permission.  Finalize of the
> > pool is
> > (presumably) going to deallocate memory, so don't we need to REQUIRE
> > finalizing the pool components first?
>
> I think the point of this is that the objects in the storage pool
> don't necessarily have to be finalized exactly when the access type is
> finalized, it can be finalized as part of finalizing the storage pool
> object, which should be very close to when the access type is
> finalized. In any case, the pool components still need to be finalized
> before the pool. Hopefully that is implied from the wording.

This part confuses me (for both -3 and -4).  You declare access types at library
level, and nested pools, so the collection finalization won't happen until after
the pool finalization. Therefore, the pool finalization MUST finalize the
objects.

> > I don't understand this Unchecked_Deallocate.  Dynamic_Storage_Pool
> > is abstract, so Unchecked_Deallocate needs to be abstract, too, right?
>
> It shouldn't need to be abstract. If the vendor implementation can put
> components in the abstract object, why cant the Unchecked_Deallocate
> operate on those components?
> For example some sort of finalization list could be in the object, and
> Unchecked_Deallocate could operate on that list.

Well, as I said elsewhere, I think you need 2 operations:
one class-wide, which walks the finalization list, and the other abstract, which
deallocates storage. The first is implemented by the Ada implementor, the second
by the Ada programmer writing a pool package. The first should call the second
dispatchingly.

As it is currently, Unchecked_Deallocate can/will be overridden, which means the
finalization work could get skipped.

> > This package doesn't know how to deallocate the memory -- that's the
> > job of types that extend Dynamic_Storage_Pool.  And "actually
> > release storage" means exactly the same thing as "allows the storage to be reused".
> > I mean, deallocating storage doesn't remove memory chips from the
> > computer.  ;-)
> I probably should state instead that the storage associated with the
> pool is not released to the system.
> Thats another difference between this proposal and -3. That one frees
> the storage of the pool, and sets the subpool handle to null.

I don't see how this is possible.  The Ada implementation doesn't know how to
manage the storage.

Whether storage is "released to the system" (a concept unknown in the Ada RM)
has to be up to the pool programmer.

> >> If a storage pool that supports dynamic pools is specified as the
> >> Storage_Pool for an access type, the access type is called a
> >> dynamic pool access type. A dynamic pool access type shall be a pool-specific access type.
> > Why "pool-specific"?
> Good point. This was a carry over from the -3 proposal.

I don't understand it in the -3 context, either.
It seems overly restrictive.  Typically, lots of access types will share the
same subpool/dynamic-pool. And they may be acc-to'Class, in which case you need
to convert amongst them, so you want "all".

>... With subpools
> that made more sense because
> subpools had to come from the same storage pool.

But many access types can share that same storage pool.

> > Ah, here's the magic.  Shouldn't this thing dispatch to a
> > user-overridden deallocation routine?  Or else this should be called
> > Finalize_Pool_Components or something.
>
> Unchecked_Deallocate is a primitive subprogram, so it can be
> overridden by the user.
> Is that what you mean?

Well, I wasn't sure what I meant, but now I think I mean:
You're mixing two things in one operation (see above about why they should be
two procedures).

> >> It is a bounded error if there are any tasks allocated from the
> >> pool that are not terminated when the call to Unchecked_Deallocate
> >> is made. The possible effects are as given for the unchecked
> >> deallocation of an object with a task part (see 13.11.2).
> > That last paragraph contradicts the previous bullets, no?
> I think it should say "not completed and not blocked at a
> select_statement with an open terminate_alternative" instead of "not
> terminated"

I think it's just a mis-translation of from -3.

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

From: Tucker Taft
Sent: Sunday, March 13, 2011  3:08 PM

> I don't understand it in the -3 context, either.
> It seems overly restrictive.  Typically, lots of access types will
> share the same subpool/dynamic-pool.
> And they may be acc-to'Class, in which case you need to convert
> amongst them, so you want "all".

We don't want to allow conversion *to* such an access type.
It is OK to allow conversion *from* such an access type, so you could ultimately
convert them all to the same general acc-to-'Class type, but when you create
them, you would create them with a pool-specific access type.  Similarly, if you
decide to free one object individually, you would need to use the pool-specific
access type for unchecked deallocation.

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

From: Bob Duff
Sent: Sunday, March 13, 2011  4:08 PM

> We don't want to allow conversion *to* such an access type.

I suspect I'm being dense, but...

Could you please explain why?

> It is OK to allow conversion *from* such an access type, so you could
> ultimately convert them all to the same general acc-to-'Class type,
> but when you create them, you would create them with a pool-specific
> access type.  Similarly, if you decide to free one object
> individually, you would need to use the pool-specific access type for
> unchecked deallocation.

Right.  But that means you can't convert back to that type.  So you have to keep
the pool-specific pointer around, even though you have general ones also.
Doesn't that seem like a pain in some cases?

Of course, if you're deallocating the whole subpool at once, which will be
common, it's not a problem, since you won't call U_D on individual objects at
all.

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

From: Tucker Taft
Sent: Sunday, March 13, 2011  4:21 PM

>> We don't want to allow conversion *to* such an access type.
>
> I suspect I'm being dense, but...
>
> Could you please explain why?

Actually, no... ;-)  It has been too long since I immersed myself in this stuff
to reconstruct why that was important.  Maybe it isn't.  This whole thing has
the potential for a lot of nasty interactions, and I haven't got the energy to
dig deep enough into it at the moment to decide which restrictions are still
important and why.  I know I thought very long and very hard about this problem
at one point.  Perhaps over the next few days I will find time to re-engage, but
I can't do it right now because of a lot of other looming deadlines...

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

From: Randy Brukardt
Sent: Sunday, March 13, 2011  4:22 PM

>I hope its not too late to consider another storage pool proposal.

It's too late to consider any new proposal.

To be specific, we really have three choices at this point:

(1) Go ahead as currently approved;
(2) Decide that the current proposal isn't sufficiently mature and remove it
    from Ada 2012;
(3) Delay the Ada 2012 another year in order to properly vet a new proposal.

If we chose (3), I think we'll also need to find a new editor. (More on that in
my other message, should I chose to send it.)

>I think this one is quite a bit simpler, safer, and easier to use than
>the previous proposals.

I haven't studied this proposal in detail (mainly because I can't convince
Outlook to open it in anything but Notepad, meaning it is unreadable), but while
it may be simpler, it surely is no safer (and appears to be much less safe to
me), and I can't see any difference in *use*. (It might be easy to write a
storage pool in this proposal, but hardly anyone should need to do that.)

...
>To summarize the differences from the previous proposals.
>	  1) Subpools are not defined. I found that subpools are not needed for
>	      Mark and Release. They are useful however for extending the lifetime of
>	      a storage pool, however one you have the above missing functionality, it is
>	      easy for the storage pool writer to provide a subpool abstraction, if it is
>	      needed.

I don't find Mark/Release worthwhile for anything. Release en-mass is
worthwhile, but there is no "Marking" involved, just an identification of which
(sub)pool is involved.

>	  2) Instead of subpools, we have dynamic storage pools, where the storage
>	      pool object can be dynamically specified using a similar syntax as the
>	     previous proposal, except instead of subpool handles, the storage pool
>	     objects are specified directly.

This is a change of name, not functionality.

>	  3) Dynamic storage pools do not need to be associated with a root storage
>	      pool. They can be completely independent storage pools.

This doesn't work (more below).

>	  4) There is no need to worry about dangling subpool handles. They don't exist.

Bull. Your dynamic pools will almost always need to be allocated from the heap.
As such, you'll have the exact same problems of dangling pointers -- you've just
removed it from sight. Moreover, while dangling subpool handles are detected at
runtime in all but the most extreme cases, using a pointer at a dangling dynamic
pool will just be erroneous with no detection possible. I fail to see how this
is safer.

>	  5) The storage pool implementer has more freedom in defining the
>	      abstraction for the storage management.

This is puffery at best. I cannot imagine how you can get "more" freedom when in
both cases you are writing Ada code that can essentially do anything.

>	  6) Unchecked_Deallocate of the Dynamic Storage Pool does not release
>	      the storage of the pool. It only deallocates the objects in the pool.
>	      Freeing the memory of the pool can easily be provided by the
>	      storage pool writer if needed.

This makes no sense whatsoever in a summary. I suspect you are making a
distinction between "Unchecked_Deallocate" and "Unchecked_Deallocation", but
these names are far too similar to be understandable. Especially as most calls
to Unchecked_Deallocate (of the contents of the dyn pool) would be immediately
followed by an Unchecked_Deallocation (of the dyn pool).

>	   7) The new package is much smaller than the subpools package. All
>	       that is provided is a new dynamic storage pool type, and a call to
>	       deallocate the objects in the pool.

Sure, but we all know that size doesn't matter. ;-)

Anyway, I see a number of major problems with this proposal. Once they are
fixed, you'll be a lot closer to the existing subpools proposal -- I have wonder
if there would remain any significant difference.

First, making this a separate type from Root_Storage_Pool is a non-starter. That
is completely unimplementable in Janus/Ada, and I suspect it would cause
problems for other implementations and user packages as well.

A bit of background: Janus/Ada uses thunks to implement operations on most
record types (as it supports non-contiguous record representations). There are
thunks to create, initialize, compare, assign, and destroy objects. These thunks
take parameters representing the context as needed, including a master, a
finalization chain, an activation chain, and of course a storage pool.
(Parameters are omitted if they cannot be needed; if for instance the type is
non-limited, we don't pass a master or activation chain.)

The thunks allocate memory as needed from the passed in storage pool; this is
done with a dispatching call. Pretty much all allocations are done this way,
including temporary objects, return objects, dynamically sized objects, and
more. (Only stand-alone top-level objects are handled specially with stack
allocation.)

To implement 111-3 would simply require passing a subpool handle in addition to
the pool; then an allocation would test the subpool handle and call the correct
routine based on whether the subpool handle is empty or not.

OTOH, if we have a batch of unrelated pool types, there is no practical way to
determine what routine to call or how to call it.

There are similar issues in the implementation of shared generics (not that I
expect anyone to care).

But I do expect them to care that a similar problem occurs in user-defined
packages. If you have a generic package that takes a storage pool object, you
would not be able to use that generic with dynamic pools (as the types would be
different). You would have to make a duplicate of the package in order to use it
with dynamic pools. (With subpools as defined in 111-3, you could simply add a
subpool handle parameter and default it appropriately.)


Second, the conversion problem that Tucker has been trying to point out is quite
important. Your proposal destroys the invariant that a pool-specific type
belongs to one and only one pool. That means that you are now introducing
erroneousness where none previously existed (presuming that you are not
proposing any change in reprsentation of pointers).

In particular, calls to Unchecked_Deallocation will no longer have any way to
find out what pool needs to be deallocated from. This is currently a problem for
general access types, but it doesn't happen for pool-specific types (which is
one reason that allocation/deallocation is best done only for such types).
However, if you can allocate from multiple pools, this invariant is destroyed,
and Unchecked_Deallocation is itself no longer "safe" (in that it is always safe
to deallocate a pointer of a pool-specific type; what is not safe is to use it
afterwards).

For instance, in something like:
               type Fooey is access Anything;
               procedure Free is new Unchecked_Deallocation (Anything, Fooey);
               Dyn : Dynamic_Pool;
               P1, P2 : Fooey;

               P1 := new Fooey;
               P2 := new (Dyn) Fooey;

               Free (P1); -- Frees from default pool.
               Free (P2); -- Also frees from default pool, but wasn't allocated from there.

The assumption that no one will ever want to free objects allocated from a
dynamic pool simply does not fly with me. If you have some temporary part of a
data structure that you are done with early (say because it is being replaced),
you will want to get rid of it immediately. Just dropping it on the floor means
that memory is being wasted, potentially for a long time.


As previously noted, this proposal eliminates the checks for dangling pool
pointers (by removing the handle concept). That makes it a lot less safe in
cases where pools are stored in other data structures. (A common case, I think.)
That seems like a step backwards to me.


One of Bob's messages was answered as follows:

>>> A call on Unchecked_Deallocate has the following effects:
>> Ah, here's the magic.  Shouldn't this thing dispatch to a
>> user-overridden deallocation routine?  Or else this should be called
>> Finalize_Pool_Components or something.
>
>Unchecked_Deallocate is a primitive subprogram, so it can be overridden
>by the user.
>Is that what you mean?

I suppose it could be overridden, but I can't imagine anything useful that such
an overriding could do. (It would have no access to the contained objects, and
the overriding should not do anything with the memory of the pool.) So why allow
that at all? (The subpool proposal does not allow that, I think.)

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

From: Robert Dewar
Sent: Sunday, March 13, 2011  5:37 PM

> (1) Go ahead as currently approved;
> (2) Decide that the current proposal isn't sufficiently mature and
> remove it from Ada 2012;
> (3) Delay the Ada 2012 another year in order to properly vet a new proposal.
>
> If we chose (3), I think we'll also need to find a new editor. (More
> on that in my other message, should I chose to send it.)

Whats so terrible about (2). After all the great majority of the Ada world has
not even moved to Ada 2005 yet, so the universe does not come to an end if some
neat new feature is delayed beyond Ada 2012.

> I haven't studied this proposal in detail (mainly because I can't
> convince Outlook to open it in anything but Notepad, meaning it is
> unreadable), but while it may be simpler, it surely is no safer (and
> appears to be much less safe to me), and I can't see any difference in
> *use*. (It might be easy to write a storage pool in this proposal, but
> hardly anyone should need to do
> that.)

Surely you can just save an attachment, if not outlook is more of a piece of
junk than I thought!

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

From: Randy Brukardt
Sent: Sunday, March 13, 2011  5:48 PM

...
> Whats so terrible about (2). After all the great majority of the Ada
> world has not even moved to Ada 2005 yet, so the universe does not
> come to an end if some neat new feature is delayed beyond Ada 2012.

Nothing is wrong with (2). I think some people think Ada needs better storage
management, but perhaps that isn't sufficiently important...

> > I haven't studied this proposal in detail (mainly because I can't
> > convince Outlook to open it in anything but Notepad, meaning it is
> > unreadable), but while it may be simpler, it surely is no safer (and
> > appears to be much less safe to me), and I can't see any difference
> > in *use*. (It might be easy to write a storage pool in this
> > proposal, but hardly anyone should need to do that.)
>
> Surely you can just save an attachment, if not outlook is more of a
> piece of junk than I thought!

Yeah, but I was pretty upset and not being able to read it pissed me off more.
Saving it and filtering it and opening it with my regular editor is possible but
is a lot of messing around for a quick scan.

But I found out that I can read it on my phone, so I don't have to mess around
with it.

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

From: Brad Moore
Sent: Sunday, March 13, 2011  4:28 PM

A new version of the proposal that addresses Bob's comments.
I put back in the line about the access type using a dynamic storage pool being a pool-specific type, based on Tuckers comment for now.

=======

%!standard 4.8(2)          11-01-28 AI05-0111-4/01
%!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)
%!standard 13.11.6 (0)
%!class Amendment 10-10-13
%!status work item 10-10-13
%!status received 10-10-13
%!priority Medium
%!difficulty Hard

%!subject Dynamic pools, allocators, and control of finalization

%!summary

Dynamic pools are added to Ada.

%!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 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 can create dangling pointers, as can
Unchecked_Deallocation. However managing entire groups of objects at once is
much less error prone. It is also likely to be much more efficient.
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.

%!proposal

Allow the storage pool object associated with an access type to be specified at
the point of the allocator, with the following syntax:

X := new (Dynamic_Pool) T'(ABC);

The objects allocated from a dynamic pool are reclaimed when
Unchecked_Deallocate is called. All of the objects in the dynamic pool are
finalized before the dynamic pool finalizes the storage.

%!wording

Modify 4.8(2) as follows:

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

dynamic_pool_specification ::= '(' dynamic_pool_name ')'

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

A dynamic_pool_name is expected to be the name of an object of any descendant of
System.Storage_Pools.Dynamic_Pools.Dynamic_Storage_Pool, the type representing
dynamic storage pools defined in the language-defined package
System.Storage_Pools.Dynamic_Pools (see 13.11.4).

Add after 7.6.1(20):

Implementation Permissions

The implementation may finalize objects of a dynamic storage pool created by
allocators for an access type as if the objects were created (in an arbitrary
order) at the point where the storage pool was elaborated instead of the first
freezing point of the access type.

AARM Ramification: This allows the finalization of such objects to occur later
than they otherwise would, but still as part of the finalization of the same
master.

AARM Implementation Note: This permission is intended to allow the allocated
objects to "belong" to the dynamic pool objects and to allow those objects to be
finalized at the time that the dynamic storage pool is finalized (if they are
not finalized earlier). This is expected to ease implementation, as the objects
will only need to belong to the dynamic pool and not also the collection.

Modify 13.11(1):

Each access-to-object type has an associated storage pool. The storage
allocated by an allocator {of a type T without a dynamic_pool specification}
comes from this pool; instances of Unchecked_Deallocation return storage to the
pool. Several access types can share the same pool.

Modify 13.11(16/3):

An allocator of type T {without a dynamic_pool_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 dynamic_pool_specification allocates storage from the specified dynamic pool,
by calling Allocate as described below.

Add three new clauses:

13.11.4 Dynamic Storage Pools

This subclause defines a package to support the dynamic selection of the storage
pool to be associated with an allocator for an access type (see 4.8).

The following language-defined library package exists:

   package System.Storage_Pools.Dynamic_Pools is

      pragma Preelaborate (System.Storage_Pools.Dynamic_Pools);

      type Dynamic_Storage_Pool is abstract new Root_Storage_Pool with private;
      -- An access type must have a storage pool of a type
      -- descended from this type to use dynamic storage pools.

      procedure Deallocate_Pool (Pool : in out Dynamic_Storage_Pool) is null
      with Pre => Is_Reclaimed (Pool);
      -- Performs further storage management associated with
      -- the Unchecked_Deallocate call. This is not intended to be called
      -- directly, but only via the Unchecked_Deallocate call.

      type Pool_Access is access Dynamic_Storage_Pool'Class;
      -- Convenience for heap allocated pools

      procedure Unchecked_Deallocate (Pool : in out Dynamic_Storage_Pool'Class);
      -- Deallocates all objects in the pool, then dispatches to
      -- Deallocate_Pool.

      function Is_Reclaimed (Pool : Dynamic_Storage_Pool'Class) return Boolean;
      -- Returns True if there are currently no objects allocated from the pool.

      procedure Unchecked_Deallocate (Pool : in out Dynamic_Storage_Pool);

private

... -- not specified by the language

end System.Storage_Pools.Dynamic_Pools;

A dynamic storage pool is a storage pool that can be reclaimed any number of
times prior to the finalization of the pool object.

Legality Rules

If a storage pool that supports dynamic pools is specified as the Storage_Pool
for an access type, the access type is called a dynamic pool access type.
A dynammic pool access type shall be a pool-specific access type.

The accessibility level of the dynamic pool access type shall not be statically
deeper than that of the storage pool object of the allocator.

Dynamic Semantics

When a dynamic pool access type is frozen (see 13.14), a check is made that the
accessibility level of the dynamic pool access type is not deeper than that of
its storage pool object. Program_Error is raised if this check fails.

When Allocate is called (see 13.11) for an allocator with a
dynamic_pool_specification, a check is made that the accessibility level of the
dynamic pool access type is not deeper than that of the storage pool object of
the allocator. Program_Error is raised if this check fails.

AARM Reason: These checks (and their static counterpart) ensures that the type
of the allocated objects exist at least as long as the storage pool object, so
that the dynamic pools 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 after the storage pool.

13.11.5 Dynamic Pool Reclamation

   procedure Unchecked_Deallocate (Pool : in out Dynamic_Storage_Pool);

The objects of a dynamic pool may be explicitly deallocated using
Unchecked_Deallocate.

A call on Unchecked_Deallocate has the following effects:

* Any task allocated from the pool that is waiting at an open terminate
  alternative and having all of its subtasks (if any) either completed or
  similarly waiting at an open terminate alternative, is completed;

* Next, the call waits for any completed tasks allocated from that pool
  (including ones completed by the previous bullet) to complete their
  finalization;

* Finally, any of the objects allocated from the pool that still exist are
  finalized in an arbitrary order.

It is a bounded error if there are any tasks allocated from the pool that are
not completed and not waiting at an open terminate alternative when the call
to Unchecked_Deallocate is made. The possible effects are as given for the
unchecked deallocation of an object with a task part (see 13.11.2).

Unchecked_Deallocate is a potentially blocking operation (see 9.5.1).

13.11.6 Dynamic Storage Pool Example

The following example is a simple but complete implementation of the classic
Mark/Release pool using dynamic pools:

   with System.Storage_Pools.Dynamic_Pools;
   with System.Storage_Elements;

   package MR_Pool is

      use System.Storage_Pools;
      --  [Note: For uses of Dynamic_Pools.]

      use System.Storage_Elements;
      --  [Note: For uses of Storage_Count and Storage_Array.]

      --  Mark and Release work in a stack fashion, and allocations are not
      --  allowed from a pool other than the one at the top of the stack.
      --  This is also the default pool.

      type Mark_Release_Pool_Type (Pool_Size : Storage_Count) is new
         Dynamic_Pools.Dynamic_Storage_Pool with private;

      function Is_Released (Pool : Mark_Release_Pool_Type) return Boolean;

      function Mark (Pool : aliased in out Mark_Release_Pool_Type;
                     Pool_Size : Storage_Count := Storage_Count'Last)
                     return Mark_Release_Pool_Type;

      procedure Release (Pool : in out Mark_Release_Pool_Type)
         with Pre => not Is_Released (Pool);

   private

      type Mark_Release_Pool_Type (Pool_Size : Storage_Count) is new
        Dynamic_Pools.Dynamic_Storage_Pool with record
         Storage : Storage_Array (1 .. Pool_Size);
         Next_Allocation : Storage_Count := 1;
         Parent : access Mark_Release_Pool_Type := null;
         Child : access Mark_Release_Pool_Type := null;
         Released : Boolean := False;
      end record;

      overriding procedure Allocate
        (Pool : in out Mark_Release_Pool_Type;
         Storage_Address : out System.Address;
         Size_In_Storage_Elements : Storage_Count;
         Alignment : Storage_Count)
        with Pre => not Is_Released (Pool);

      overriding procedure Deallocate
        (Pool : in out Mark_Release_Pool_Type;
         Storage_Address : System.Address;
         Size_In_Storage_Elements : Storage_Count;
         Alignment : Storage_Count)
      is null;

      overriding function Storage_Size
        (Pool : Mark_Release_Pool_Type) return Storage_Count;

      --  Dont need Initialize

      overriding procedure Finalize
        (Pool : in out Mark_Release_Pool_Type)
      with Pre => Is_Released (Pool);

      function Is_Released (Pool : Mark_Release_Pool_Type) return Boolean is
      begin
         return Pool.Released;
      end Is_Release;

      function Storage_Size
        (Pool : Mark_Release_Pool_Type)
         return Storage_Count is
      begin
         return Pool.Pool_Size;
      end Storage_Size;

   end MR_Pool;

   package body MR_Pool is

      overriding procedure Finalize
        (Pool : in out Mark_Release_Pool_Type) is
      begin
         if Pool.Parent /= null then
            Pool.Parent.Child := null;
         end if;
      end Finalize;

      function Mark
        (Pool      : aliased in out Mark_Release_Pool_Type;
         Pool_Size : Storage_Count := Storage_Count'Last)
         return         Mark_Release_Pool_Type is
      begin
         return New_Pool : aliased Mark_Release_Pool_Type :=
              (Dynamic_Pools.Dynamic_Storage_Pool with
               Pool_Size       => Pool_Size,
               Storage         => <>,
               Next_Allocation => 1,
               Parent          => Pool'Unchecked_Access,
               Child           => null,
               Released        => False)
         do
            Pool.Child := New_Pool'Unchecked_Access;
         end return;

      end Mark;

      procedure Release (Pool : in out Mark_Release_Pool_Type) is
      begin
         Unchecked_Deallocate (Pool);
         Pool.Next_Allocation := 1;
         Pool.Released := True;
      end Release;

      procedure Allocate
        (Pool                     : in out Mark_Release_Pool_Type;
         Storage_Address          : out System.Address;
         Size_In_Storage_Elements : Storage_Count;
         Alignment                : Storage_Count) is
      begin
         if Pool.Child /= null then
            --  Can only allocate from the lowest scope
            raise Program_Error;
         end if;

         --  Correct the alignment if necessary:
         Pool.Next_Allocation :=
           Pool.Next_Allocation + ((-Pool.Next_Allocation) mod Alignment);

         if Pool.Next_Allocation +
              Size_In_Storage_Elements > Pool.Pool_Size then
            raise Storage_Error;
            --  Out of space.
         end if;

         Storage_Address      := Pool.Storage (Pool.Next_Allocation)'Address;
         Pool.Next_Allocation := Pool.Next_Allocation +
                                 Size_In_Storage_Elements;
      end Allocate;

   end MR_Pool;

[End 13.11.6.]

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

Modify 13.11(38):

As usual, a derivative of Root_Storage_Pool may define additional operations.
For example, [presuming that]{consider the} Mark_Release_Pool_Type {defined in
13.11.5, that} has two additional operations, Mark and Release, the following
is a possible use:

Delete the Block_Size discriminant from 13.11(39/1), and add a comment
"As defined in 13.11.5".

Replace 13.11(41) with

My_MR_Pool : aliased MR_Pool.Mark_Release_Pool_Type (Pool_Size => 2000);

Replace 13.11(43):

My_Mark : MR_Pool.Mark_Release_Pool_Type :=
   MR_Pool.Mark (Pool, Pool_Size => 1000); -- See 13.11.5

-- Allocate objects using "new (My_Mark) Designated(...)"
My_Mark.Release; ...
-- Allocate objects using "new (My_MR_Pool) Designated(...)"
My_MR_Pool.Release;

%!discussion

This proposal focuses on the language features that are missing from Ada 2005
with regard to storage management and storage pools, namely;
 1) Permitting early finalization of objects and tasks in the storage pool,
     using a mark-release strategy.
 2) Syntactic sugar to provide the storage pool object to the new operator.

The initial thought was to provide no more and no less than this functionality.

To summarize some of the key features of this proposal;
  1) A new Storage_Pool type is defined called a Dynamic_Storage_Pool. It is a
     descendant of System.Storage_Pools.Root_Storage_Pool, and provides calls
     to permit early finalization of the storage pool.

  2) Subpools are not defined. Strictly speaking, subpools are not needed for
     Mark and Release style storage management. They are useful however for
     extending the lifetime of a storage pool. However once you have the above
     missing functionality, it is easy enough for the storage pool writer to
     provide a subpool abstraction, if it is needed.

  3) Instead of subpools, we have dynamic storage pools, where the storage
     pool object can be dynamically specified at the allocator.

  4) The dynamic storage pools associated with an access type do not need to be
     associated with a root storage pool. Allocators for an access type can
     specify completely independent storage pools.

  5) There is no need to worry about dangling subpool handles. They don't
     exist. A dynamic storage pool object may itself be dynamicallly allocated,
     in the same way that Root_Storage_Pool objects can be dynamically
     allocated if needed. It should even be possible to define a dynamic storage
     pool that contains dynamic storage pools. The possibility of creating
     storage pools without involving access types should provide possibilities
     for safer storage management.

  6) The storage pool implementer has more freedom in defining the
      abstraction for the storage management.

  7) Unchecked_Deallocate is a class-wide operation of the Dynamic Storage Pools
     that deallocates the objects in the pool. It then dispatches to
     Deallocate_Pool which can overridden to provide further management of the
     storage associated with the pool.

  8) The Dynamic_Pools package is small and concise.

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 dynamic storage pools. The dynamic storage pool object type can also be
extended. So the implementor of the storage pool can keep some information
globally for the overall storage pool (by extending Dynamic_Storage_Pool), and
then some per subpool data structure (by extending the overall storage pool
object).

Meanwhile, the "root part" of the dynamic storage pool object type will be used
by the Ada implementation to implement task dependence and finalization for the
dynamic storage pools.

task TERMINATION MODEL

The basic model of task termination is unaltered; the tasks allocated from a
dynamic storage pool belong to the master of the access type. This works because
of the accessibility checks on the pool object - the pool object has to be in
the same scope as the access type. Moreover, all tasks for a given scope
terminate together, so it isn't possible to differentiate between them
"belonging" to the pool object or the access type.

Unchecked_Deallocation has no effect on task termination. This means that server
tasks embedded in a deallocated object may continue to wait at terminate
alternatives, even though they are no longer accessible. It is felt that it is
not a hardship for the client to call a 'shutdown' routine before deallocating
them (although such a requirement damages encapsulation).

However, this model does not work for dynamic storage pools. In order to call a
shutdown entry on each object, it would be necessary to enumerate all of the
contained objects (or at least those that need a shutdown routine called). That
would defeat the purpose of dynamic storage pools (which is to support a mass
deallocation of all of the related objects without having to enumerate them).

Therefore, we adopt rules that have tasks allocated from a dynamic storage pool
that are waiting at a terminate alternative (with the same requirements as
9.3(3-6)) become completed, and then the finalization of all completed tasks is
waited for. This means that it is safe to deallocate a dynamic storage pool
containing tasks -- even if those tasks have discriminants -- so long as the
tasks are completed. For other tasks, this is a bounded error as it is for
Unchecked_Deallocation.

We considered adopting this rule for Unchecked_Deallocation as well, as it would
reduce the cases of bounded errors and the associated bugs. Unfortunately, it
could be inconsistent with the behavior of Ada 95 and Ada 2005 programs, as the
finalization could take a long time or even block. In extreme cases, deadlock is
possible. That seems like too much of an inconsistency to allow, so we do not
change the behavior of Unchecked_Deallocation.

FINALIZATION MODEL

Objects allocated into a dynamic storage pool will be finalized when the
dynamic storage pool is explicitly deallocated. If that never happens, the
objects can be finalized in the normal place for the access type, or the
implementation can finalize them when the pool is finalized.

Since the objects allocated into a dynamic storage pool 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.

One difference between this proposal and the previous one (AI05-0111-3) is
that an additional accessibility check is performed on each call to Allocate
for an allocator with a dynamic_pool_specification. This seemed like additional
distributed overhead compared to the previous proposal, but it is really no
different, because for that proposal, there needs to be some sort of check that
the subpool handle belongs to the correct storage pool.

Alternatives

The accessibility checks do put restrictions on the location of access types
that use dynamic storage pools. 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 dynamic storage pools for that
access type. (Along with a similar rule for task dependence.)

This eliminates the static restrictions and would allow dynamic storage pools to
be used on access types with nested designated types and the like.
However, the implementation would be complex. An obvious implementation would
put dynamic storage pool allocated objects on both a chain for the collection
and a chain for the dynamic storage pool (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 dynamic
storage pool keeps a separate finalization list for each access type, then only
the dynamic storage pool need be put on the access type's collection list. This
would complicate finalization somewhat, but only when dynamic storage pools are
used. This would require some unique way to identify the access type to the
dynamic storage pool; this could be done by assigning at elaboration time a
unique serial number to each access type that uses a storage pool that supports
dynamic storage pools.
Similar implementation complexity would also apply to task dependence. Because
of this complexity, we chose the simpler model.

USE AS A BUILDING BLOCK

This package provides facilities that can be used to provide safer abstractions.

One possibility would be to wrap the dynamic storage pool handle in a controlled
object that managed reference counting. When the count reached zero, the
dynamic storage pool would be automatically deallocated. This is basically the
idea of AI05-0111-2 (without the checks on the contained pointers).

%!example

See the example given in the !wording.
---
Another way that dynamic storage pools 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 dynamic storage pool 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.

%!ASIS
Some new ASIS routine needs to be added to handle the dynamic storage pool
syntax for allocators.
Details TBD. ***

%!appendix

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

From: Robert Dewar
Sent: Sunday, March 13, 2011  5:38 PM

Reading Randy's message, I completely withdraw any implication of support for
this new proposal, I agree with him that it is too late.

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

From: Randy Brukardt
Sent: Sunday, March 13, 2011  6:05 PM

Having managed to read this version in Gmail, there are a number of things that
strike me as odd:

(1) Having to specify a dynamic pool on the access type makes little sense. I
    understand that the idea is to somehow mark that the type is a "dynamic pool
    access type", but this pool is one that usually is just a placeholder: you
    would never want to actually allocate something from it. And it makes one of
    these pools special, which seems to be what you are trying to avoid.

    I think you would be better off making Dynamic_Pool an aspect; then you
    could also disallow instantiating Unchecked_Deallocation on the type. (I
    think you have to do that in order to prevent erroneousness; see my earlier
    message.)

(2) While I understand the need for the accessibility checks, these are going to
    feel very limiting. They will prevent any locally allocated dynamic pools --
    in practice the pools will have to be allocated from some other pool.
    (Subpools are only useful on library-level access types in general, and I
    don't see that changing with this proposal.)

    As previously noted, the fact that these will be allocated means that
    dangling dynamic pool pointers will be a real problem in practice, even if
    they've been eliminated from the wording. The accessibility check probably
    will be more expensive than the dangling subpool check (which is a simple
    compare), but the subpool handle check prevents almost all erroneousness;
    the accessibility only prevents finalization problems.

(3) I don't understand your Mark_Release example at all. Since each pool
    contains it's own storage, "Mark" is just creating a new pool. And you have
    to give a maximum size when you do that. Why even bother with Mark in that
    case? Just create [allocate] each pool when you need it (giving the size),
    and destroy [deallocate] it when you don't need it anymore. That's even more
    flexible and much simpler.

    As I said previously, I don't find Mark/Release very interesting. (It's only
    useful when the storage is shared, which is not happening here, and when the
    objects are allocated in a stack-like fashion -- which is rare, and often
    better handled by stack allocation in Ada.) Moreover, nothing in your actual
    proposal is actually using or requiring such a strategy. So I would talk
    about it as little as possible.

For instance, you say that Ada 2005:
 1) Permitting early finalization of objects and tasks in the storage pool,
     using a mark-release strategy.

But there is nothing whatsoever about this strategy in your proposal. If you
dropped everything after the comma, you would still be making the same point.
And seriously, if a proposal *only* supported Mark/Release, I would oppose it on
the basis of being insufficiently valuable.

(4) I don't understand why you have a separate section 13.11.5. This is
    describing the operation of a routine defined in the package defined in the
    previous section; it needs to be in that section.

    Moreover, the name of the routine is bogus. It doesn't "Deallocate"
    anything, so it should not have that in its name. All it does is finalizes
    all of the pool objects. It's more like "Unchecked_Finalize".

    I also wish it was clear that client pools do not need to provide this
    routine, because this differs from everything else in a storage pool. (Not
    sure of how to do that.)

(5) You can disregard the discussion of implementability from my previous
    message; this is a type derived from Root_Storage_Pool (not sure why your
    other e-mails implied otherwise) which is my main concern.

(6) I think you need a rule which says that "Unchecked_Finalize" (with whatever
    name it ultimately has) is called when a dynamic storage pool object is
    finalized. That's important when such a pool is freed by
    Unchecked_Deallocation, as it is likely that the storage of the contained
    objects is going away. It's also important to make it clear that extra calls
    to "Unchecked_Finalize" don't have any effect - the objects are only
    finalized once. Also, are you allowing additional objects to be allocated
    after "Unchecked_Finalize" is called? Generally, we do not allow additional
    allocations after the collection is finalized; otherwise there is a chance
    that they would never get finalized. Using a different pool object doesn't
    sound bad, so I would suggest that this semantics apply to these pools as
    well.

I do find that finalizing objects without freeing their memory is odd - it
almost seems like a bug. But I suppose one could get used to that.

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

From: Bob Duff
Sent: Wednesday, April  6, 2011  8:07 AM

While trying to implement this one:

AI05-0111-3: Subpools, allocators, and control of finalization

we came up with some comments and questions.

First issue: "new".

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

The above seems reasonable.  But it contradicts what 13.11.4 says:

> When an allocator for a type whose storage pool supports subpools is
> evaluated, a call is made on Allocate_From_Subpool passing in a
> Subpool_Handle, in addition to the parameters as defined for calls on
> Allocate (see 13.11). The subpool handle is the one given in the
> allocator if a *subpool_handle_*name is specified, or otherwise the
> handle obtained by calling Default_Subpool_for_Pool on the pool of the
> type of the allocator. All requirements on the Allocate procedure also apply
> to Allocate_from_Subpool.

Note that "type whose storage pool supports subpools" is not a statically-known
thing.  (You could say "for ...'Storage_Pool use X;", where X is of type
Root_Storage_Pool, and we don't know if X in Root_Storage_Pool_with_Subpools.

For "new T", we certainly don't want to check at run time whether to do a
dispatching call to Allocate or Allocate_From_Subpool -- the dispatching itself
should do the necessary run-time thing.  We want to simply call
Allocate(T'Storage_Pool, ...) as 13.11(16/3) above says.

It makes no sense for somebody to write storage management code twice -- once in
Allocate, and once in Allocate_From_Subpool. Therefore, I think there should be
a concrete overriding of Allocate on Root_Storage_Pool_with_Subpools, which
does:

    procedure Allocate (...) is
    ...
        Allocate_From_Subpool
            (Pool,
             Storage_Address, Size_In_Storage_Elements, Alignment,
             Subpool => Default_Subpool_for_Pool (Pool));

I suppose types derived from Root_Storage_Pool_with_Subpools could override
that, but I don't see why they would want to. And I don't see why we want to
require them to (which is the current situation -- Allocate is abstract).

It's done the other way around in the example (Allocate_From_Subpool calls
Allocate), but that seems backwards to me, and only works in this example
because of the primitive nature of "mark/release".

Once you choose the "subpools" world, you want to all the allocation in
subpools, not some hybrid mixture of pools and subpools.  Allocate for
(Root_Storage_Pool_with_Subpools) is just a bridge into the subpools world.

So the rule about what "new" does should be based on the syntax of the "new": if
it doesn't specify a subpool, it calls Allocate, if it does specify a subpool,
it calls Allocate_From_Subpool.

----------------

Do we need a legality rule preventing "new (Subpool) ..." if the pool type is
not statically known to support subpools?

    type Not_Subpool_Acc is access all Integer;
    --  No "for Not_Subpool_Acc'Storage_Pool" clause!
    X : Not_Subpool_Acc := new (Some_Misc_Subpool) Integer;

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

Is this intended to prevent the above case.  I.e. the initial value of X should
raise Program_Error?  If so, it certainly deserves an AARM comment.

Why non-null?  Shouldn't "new (null) ..." raise an exception?
I realize Allocate_From_Subpool says "not null", but it still seems confusing
here.

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

----------------

>        function Default_Subpool_for_Pool(
>          Pool : in Root_Storage_Pool_with_Subpools) return not null Subpool_Handle;
>            -- Returns a handle of the default subpool for Pool.
>            -- Note: If no default subpool is supported, this routine should
>            -- raise Storage_Error.

Is this one intended to be abstract?  If not, then there needs to be wording
saying what the body does.  I don't understand how it's supposed to work. Seems
like either the pool-writer, or the Ada implementation, should be responsible
for default pools -- not both.

> A subpool may be specified as the default to be used for allocation
> from the associated storage pool, ...

How?  By whom?  There's no Set_Default_Subpool operation.

----------------

There's no mention of Unchecked_Deallocation of objects from subpools.
Is the following a correct understanding of finalization of an object allocated
in a subpool?

    - When U_D is called, the object is finalized,
      and then Deallocate is called on the Pool,
      which typically will do nothing.  If it wants to do
      something, it will probably need some way to get from
      the address to the subpool -- that's the user's problem.

      There is no Deallocate_From_Subpool.

    - If U_D is not called, the object will be finalized
      when Unchecked_Deallocate_Subpool is called.

    - If that's never called, then it will be finalized
      when the Pool_With_Subpools is finalized (by permission --
      it might happen when the collection of the access type
      is finalized).

Right?

> Add after 7.6.1(20):
>
> Implementation Permissions
>
> The implementation may finalize objects created by allocators for an
> access type whose storage pool supports subpools (see 13.11.4) as if
> the objects were created (in an arbitrary object) at the point where
> the storage pool was elaborated instead

"object" --> "order"?

AI 190 is messing around in this same area, and somebody needs to verify that it
all makes sense.

Why is this a permission?  Seems like it should be a requirement.
Why don't we say that finalization of a subpool finalizes everything allocated
in it, and finalization of a pool that supports subpools finalizes all the
remaining subpools?

> of the first freezing point of the access type.
>
> AARM Ramification: This allows the finalization of such objects to
> occur later than they otherwise would, but still as part of the finalization
> of the same master.

", but still..." -->

"Rules below ensure this happens as part of the same master."

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

From: Bob Duff
Sent: Wednesday, April  6, 2011  11:12 AM

AI05-0111-3: Subpools, allocators, and control of finalization

Question about task termination.
The AI says:

    If Subpool is null, a call on Unchecked_Deallocate_Subpool
    has no effect. Otherwise, a call on Unchecked_Deallocate_Subpool has
    the following effects:

    * Any task allocated from the subpool designated by Subpool that is
      waiting at an open terminate alternative and having all of its subtasks
      (if any) either completed or similarly waiting at an open terminate
      alternative, is completed;

    * Next, the call waits for any completed tasks allocated from that subpool
      (including ones completed by the previous bullet) to complete their
      finalization;

    [...finalization stuff]

    * [Deallocate_Subpool is called]  <--- step 4

    [...[

    It is a bounded error if there are any tasks allocated from the subpool
    that are not terminated when the call to Deallocate_Subpool is made. The
    possible effects are as given for the unchecked deallocation of an object with a
    task part (see 13.11.2).

(Don't confuse Unchecked_Deallocate_Subpool and Deallocate_Subpool!)

So at the time Unchecked_Deallocate_Subpool is called, the subpool contains some
tasks (A) waiting on terminate alternatives (i.e. ready to terminate), (B) some
completed tasks, and some (C) running tasks.  First we poke (A).  Then we await
(A) and (B).

(At this point, what if some (C) task decides to go into state (A) or (B)?)

Then, if there are any (C) tasks, we've got a bounded error.

What's the rationale for all this?  It would seem a lot easier to implement if a
subpool behaved more like a regular master: wait until all tasks in the subpool
are in state (A) or (B). Poke the (A) ones.  Wait for everything to be done. It
seems complicated to have a task that belongs to a subpool and also to a master;
shouldn't it be one or the other? We don't know ahead of time whether it will be
waiting on a terminate alt when U_D_S is called.

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

From: Randy Brukardt
Sent: Wednesday, April  6, 2011  2:55 PM

(1) We don't want to wait for uncompleted tasks, because we want this to work
    similarly to Unchecked_Deallocation. It should be reasonably easy to convert
    from U_D to U_D_S without significantly changing the runtime performance. (I
    think U_D also ought to wait for completed tasks to terminate, but that is
    runtime inconsistent, so we didn't do that.)

(2) We originally had a subpool being a master, and the model was considered too
    complex. So we got rid it, and now you are complaining that the model is too
    complex. Can't win. ;-)

(3) I envisioned the tasks being on a linked list associated with the subpool.
    This is *not* in any way a master, it's much closer to the task activation
    list. (Indeed, I'd use the task activation list to implement it, making a
    copy into the subpool list before activating the tasks of an allocator.) If
    U_D_S is called, you'd walk the list, poke each task, walk the list again,
    wait for each if necessary. This is definitely not as efficient as possible,
    but it is easy. If someone actually cares, you can worry about doing a
    better job. You probably can write this using the existing primitives in
    your task system (especially if there is a wait for terminate routine; else
    you'd have to use a slow busy-wait loop, which is definitely not optimal).

Keep in mind that embedding tasks in a complex data structure is extremely rare.
I've never done it outside of the ACATS. I have plenty of tasks that contain a
data structure, but the most complex task data structure I've ever used is an
array of tasks. So the performance of the solution for U_D_S is secondary, at
least until there is a customer demand for improvement. (And remember that
premature optimization is the root of a lot of evil!)

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

From: Brad Moore
Sent: Thursday, April  7, 2011  2:15 PM

I also have some comments on this AI

The biggest one having to do with safety concerns with regard to dangling
reference possibilities. I still believe the AI05-0111-4 is safer than the -3
version, but if there isn't time to consider that proposal, then perhaps there
is time to consider tweaking the  -3 proposal to address this safety concern.

I see the issue as having to expose subpool handles that are access types to the subpool objects.

Forcing the use of access types is error prone, and lends itself to dangling
reference problems.

It would be safer if the subpool handle was itself a limited controlled type
that contained the reference to the subpool internally.

I see subpool handles typically having different lifespans from subpool objects.
Handles can dissappear before the subpool object, and subpool objects can
disappear before the subpool handle.

The subpool object could contain a component(s) that are access to references
from the handles. This allows;

   1) The subpool object can know exactly how many references exist to itself.
   2) Since subpool handles are controlled types, when they are finalized, they can "detach" from the
       subpool by setting its access reference in the subpool object to null. Similarly, when a subpool
       object is deallocated, if its access to handle reference isn't already null, it can reach into the
       handle and set its reference to null. If its access to handle reference is already null, because
       the handle has gone away, then there is no need to do anything.

Using this approach, I think should avoid problems with dangling subpool
references.

The syntax for allocating from subpools remains the same, its just the type of
the subpool handle that is different.

I have sketched out some differences to the package below, but the main point is
that most of the -3 proposal is intact, with some tweaks here and there.

Also, I have updated the deepend storage pool to be written fully in Ada. (It no
longer binds to the Apache Runtim Library) I wanted to see if I could make the
dynamic pool abstraction work on top of the -3 proposal, so if you download the
current  source, you will see two preview subfolders for the Ada 2012 version.
One shows the abstraction on top of the current -3 proposal, and the other (with
"safer" in the folder name) shows dynamic pools using a version of -3 with the
mentioned tweaks.

see https://sourceforge.net/projects/deepend/files/
or
  mkdir sandbox
  cd sandbox
  git clone git://deepend.git.sourceforge.net/gitroot/deepend/deepend


My concern is that safety is an important aspect of Ada, and that we will be
missing an opportunity to make these subpools safer to use, and that down the
road the decision to use subpool handles that are access types will be viewed as
a mistake.


package System.Storage_Pools.Subpools is ..
   type Root_Storage_Pool_with_Subpools is
      abstract new Root_Storage_Pool with private;

    type Root_Subpool is abstract tagged limited private;

   type Subpool_Handle is abstract new
     Ada.Finalization.Limited_Controlled with private;

   function Create_Subpool
     (Pool : in out  Root_Storage_Pool_with_Subpools;
      Storage_Size : Storage_Elements.Storage_Count :=
        Storage_Elements.Storage_Count'Last) return Subpool_Handle'Class is abstract;

...
   procedure Attach
     (Handle : in out Subpool_Handle;
      To : access Root_Subpool'Class);
   --  Attach the Subpool_Handle to  for a newly created subpool or a subpool
   --  which is being reused after a call to Deallocate_Subpool (this
   --  routine should only be used as part of the implementation of
   --  Create_Subpool or similar subpool constructors).
   --  Raises Program_Error if the handle is already attached to a subpool
   --  since the last explicit finalization (if any) of the subpool.

   procedure Detach
     (Handle : in out Subpool_Handle);
   pragma Precondition (Pool_of_Subpool (Handle) /= null);
   --  Detach the Subpool_Handle from its subpool, as part of the
   --  finalization of the subpool handle. The subpool may live longer than
   --  than the subpool handle. Once the handle has been detached from
   --  the subpool, deallocating the subpool will not result in attempting to
   --  clean up the dangling reference from the subpool handle, since it is
   --  assumed the subpool handle no longer exists.
   --  Raises Program_Error if the handle is already detached from its subpool.

   procedure Detach
     (Subpool : in out Root_Subpool'Class);
   --  pragma Precondition (Pool_of_Subpool (Handle) /= null);
   --  Detach the Subpool_Handle from its subpool, as part of the
   --  finalization of the subpool handle. The subpool may live longer than
   --  than the subpool handle. Once the handle has been detached from
   --  the subpool, deallocating the subpool will not result in attempting to
   --  clean up the dangling reference from the subpool handle, since it is
   --  assumed the subpool handle no longer exists.
   --  Raises Program_Error if the handle is already detached from its subpool.

   type Subpool_Access is access all Root_Subpool'Class;

   function Get_Access (Subpool : Subpool_Handle'Class) return
     Subpool_Access;

private

   type Root_Storage_Pool_with_Subpools is
      abstract new Root_Storage_Pool with null record;

   type Root_Subpool is abstract tagged limited
      record
         Pool : access Root_Storage_Pool_with_Subpools'Class;
         Handle_Reference : access Subpool_Access;
         --  While the Subpool_Handle exists, this component provides
         --  a means to set the subpool handle's reference to null if the
         --  subpool is deallocated.
         --  Conversely, if the Subpool_Handle ceases to exist before the
         --  subpool is deallocated, its finalization needs to set the
         --  Handle_Reference to null, so that when the subpool is deallocated,
         --  it knows not to set the handles reference to null, since the
         --  handle no longer exists.
   end record;

   type Subpool_Handle is abstract new
     Ada.Finalization.Limited_Controlled with
      record
         Subpool : aliased Subpool_Access;
      end record;

end System.Storage_Pools.Subpools;

package body System.Storage_Pools.Subpools is

   procedure Attach
     (Handle : in out Subpool_Handle;
      To : access Root_Subpool'Class) is
   begin
      Handle.Subpool := Subpool_Access (To);
      Handle.Subpool.Handle_Reference := Handle.Subpool'Unchecked_Access;
   end Attach;

   procedure Detach
     (Handle : in out Subpool_Handle) is
   begin
      Handle.Subpool.Handle_Reference := null;
      Handle.Subpool := null;
   end Detach;

   procedure Detach
     (Subpool : in out Root_Subpool'Class) is
   begin
      if Subpool.Handle_Reference /= null then
         Subpool.Handle_Reference.all := null;
         Subpool.Handle_Reference := null;
      end if;
   end Detach;

   function Get_Access (Subpool : Subpool_Handle'Class) return
     Subpool_Access is
   begin
      return Subpool.Subpool;
   end Get_Access;
...
end System.Storage_Pools.Subpools;

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

From: Bob Duff
Sent: Thursday, April  7, 2011  6:21 PM

> The biggest one having to do with safety concerns with regard to
> dangling reference possibilities.  I still believe the AI05-0111-4 is
> safer than the
> -3 version, but if there isn't time to consider that proposal, then
> perhaps there is time to consider tweaking the -3 proposal to address
> this safety concern.

I think we shouldn't worry about safety with respect to subpools.
Subpools are a replacement for Unchecked_Deallocation, which already allows
dangling pointers, so the only issue is whether subpools are less safe than
that.  I have plenty of experience showing that they're not -- it's much easier
to manage objects with similar lifetimes all together, and get it right.

Your ideas about keeping track of which handles belong to which subpools are
probably good.  But they can be implemented in Ada 2012, on top of the subpools
feature.  I don't think we should add implementation complexity and overhead in
the language feature itself.

Anyway, you're worrying about dangling subpool handles.  I don't think they're a
big problem -- the big problem is dangling pointers to objects in subpools.

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

From: Randy Brukardt
Sent: Thursday, April  7, 2011  11:24 PM

I agree with Bob. Indeed, I would argue that in practice that a dangling subpool
handle is safer than a dangling (container) cursor; the language rules require
it to be detected 99% of the time (the language does not *require* detection of
a dangling cursor, although it can be detected 99% of the time as well). In
order for a dangling subpool handle to go undetected, it has to point at memory
that *happens* to contain a pointer to the correct pool for the allocator, an
unlikely occurrence (especially as the language requires that pointer to be
cleared when the subpool is destroyed; it can only have the correct value if
some subsequent operation has reopened the subpool).

This is *not* a problem in any sense of the word; it is necessary to talk about
this in the context of a language definition (as all contingencies have to be
addressed), but it is not something that is going to happen in practice.

Note that -4 proposal is not really safer; since "dynamic pools" have to be
created at exactly the same accessibility level as the access type and before
that access type (that's the requirement of the -3 proposal, and my
understanding is that you meant to keep it, else you need different rules for
finalization than -3 ones), they're probably going to have to be allocated and
in that case they're *more* likely to be dangling (you don't get the benefit of
the current subpool check). And even if they are not allocated, there seems to
be much more likelyhood of using the wrong dynamic pool at runtime (meaning a
different set of problems).

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

From: Bob Duff
Sent: Thursday, April  7, 2011  6:42 PM

I would also like to hear from Tucker and others.
I really think this AI needs substantial work, and it's important AI, so we
should expend the effort (even though I know Randy is frustrated about things
taking too long!).

> (1) We don't want to wait for uncompleted tasks, because we want this
> to work similarly to Unchecked_Deallocation.

But the current semantics require U_D_S to do all kinds of complicated stuff
that U_D doesn't do.

If you really want U_D_S to be like U_D, then it should not "poke" the tasks
waiting at terminate alternatives, and it should not wait for anything.
(Terminate alternatives are a cool feature, but I think they're mainly useful at
library-level -- they allow you to cleanly shut down the whole program. Adding
complexity to support terminate alternatives in subpools is ludicrous, IMHO.)

>...It should be reasonably easy to
> convert from U_D to U_D_S without significantly changing the runtime
>performance.

Performance is not an issue.  Most subpools won't contain tasks and controlled
stuff, so all that complicated stuff won't happen.

>...(I think U_D also ought to wait for completed tasks to  terminate,
>but that is runtime inconsistent, so we didn't do that.)

I agree.  It's a big hole in Ada that there's no way to wait for tasks to
terminate, except when leaving a master.  E.g. a library-level task, allocated
by "new" -- you can't wait for it to terminate without doing a busy-wait loop,
or quitting the whole program.

Here's our chance to fix that!

> (2) We originally had a subpool being a master, and the model was
> considered too complex. So we got rid it, and now you are complaining
> that the model is too complex.

Exactly.  I think subpool-as-master is substantially LESS complicated, because
we already know how to do master completion.

>...Can't win. ;-)

Well, we can't win if we add complexity in order to simplify things.  ;-)

> (3) I envisioned the tasks being on a linked list associated with the
> subpool. This is *not* in any way a master, it's much closer to the
> task activation list. (Indeed, I'd use the task activation list to
> implement it, making a copy into the subpool list before activating the tasks of an
> allocator.)                         ^^^^^^^^^^^^^^^^^

I don't see what it has to do with activation.

And if you're going to reuse activation list links for this unrelated purpose,
don't you mean "after activating", rather than "before activating" above?

>...If U_D_S is called, you'd walk the list, poke each task, walk  the
>list again, wait for each if necessary. This is definitely not as
>efficient as possible, but it is easy. If someone actually cares, you
>can  worry about doing a better job. You probably can write this using
>the  existing primitives in your task system (especially if there is a
>wait for  terminate routine; else you'd have to use a slow busy-wait
>loop, which is  definitely not optimal).

I don't see how this can work.  The AI says you wait for the ones that are
completed.  But the ones that are running can complete (or get to a terminate
alternative) while all this is going on.

Anyway, I don't think there's a "wait for a particular task to terminate" in our
runtimes.  There's a "complete master" primitive, which waits for a group of
tasks to terminate (or get to terminate alternatives).  It works by counting
tasks.  That's why I think it's simplest to say that a subpool is a master.

(Well, simplest would be to raise an exception if anybody allocates objects
containing tasks in subpools.  I advocated that before, but it didn't fly.)

> Keep in mind that embedding tasks in a complex data structure is
> extremely rare. I've never done it outside of the ACATS. I have plenty
> of tasks that contain a data structure, but the most complex task data
> structure I've ever used is an array of tasks. So the performance of
> the solution for U_D_S is secondary, at least until there is a
> customer demand for improvement. (And remember that premature
> optimization is the root of a lot of evil!)

I'm not at all concerned with efficiency of tasks in subpools.
I'm just complaining about implementation effort for a feature that, as you say,
will be rare.

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

From: Randy Brukardt
Sent: Thursday, April  7, 2011  7:35 PM

> I would also like to hear from Tucker and others.
> I really think this AI needs substantial work, and it's important AI,
> so we should expend the effort (even though I know Randy is frustrated
> about things taking too long!).

I can believe it needs a couple of tweaks, but not "substantial work".
Unless you want to re-argue the same points we've already discussed...

At this point, we can make some minor fixes, but a major redo means it's out
completely. Besides, if we consider that, we have to seriously consider Brad's
proposal as well (it *does* seem simpler still, even if it doesn't work as
written).

> > (1) We don't want to wait for uncompleted tasks, because we want
> > this to work similarly to Unchecked_Deallocation.
>
> But the current semantics require U_D_S to do all kinds of complicated
> stuff that U_D doesn't do.

There is an important reason for that, as described in the AI. The notion is
that U_D doesn't need to wait for tasks as it is easy to call a shutdown entry
before doing the U_D. That would completely violate the purpose of U_D_S, since
it would require iterating the entire set of objects.

I don't completely buy this rationale: I think U_D is wrong and should also
terminate its tasks if possible. But waiting is for *uncompleted* tasks is not
an option.

> If you really want U_D_S to be like U_D, then it should not "poke" the
> tasks waiting at terminate alternatives, and it should not wait for
> anything.  (Terminate alternatives are a cool feature, but I think
> they're mainly useful at library-level
> -- they allow you to cleanly shut down the whole program.
> Adding complexity to support terminate alternatives in subpools is
> ludicrous, IMHO.)

That wasn't my idea. I'd be just as happy raising Program_Error if you tried to
allocate a task from a subpool. But that's too weird.

> >...It should be reasonably easy to
> > convert from U_D to U_D_S without significantly changing the runtime
> >performance.
>
> Performance is not an issue.  Most subpools won't contain tasks and
> controlled stuff, so all that complicated stuff won't happen.

Yes it is an issue, if there is a task, waiting makes a massive performance
difference. If there is no task, none of this matters.

> >...(I think U_D also ought to wait for completed tasks to terminate,
> >but that is runtime inconsistent, so we didn't do that.)
>
> I agree.  It's a big hole in Ada that there's no way to wait for tasks
> to terminate, except when leaving a master.  E.g. a library-level
> task, allocated by "new" -- you can't wait for it to terminate without
> doing a busy-wait loop, or quitting the whole program.
>
> Here's our chance to fix that!

Exactly, and we did, and you aren't happy.

But note that waiting for an *uncompleted* task is not contemplated ever,
because it would be far too incompatible with U_D. You couldn't change to using
a subpool at all if any tasks are involved (assuming the original design is
correct).

A full waiting model is a non-starter. I think U_D should have done full
waiting, but there is no way to fix that now. I still think it should terminate
completed (but not uncompleted) tasks, exact compatibility be damned. And U_D_S
has to be similar - but it has to be able to complete tasks, else they live
forever.

> > (2) We originally had a subpool being a master, and the model was
> > considered too complex. So we got rid it, and now you are
> > complaining that the model is too complex.
>
> Exactly.  I think subpool-as-master is substantially LESS complicated,
> because we already know how to do master completion.

It's definitely not less complicated in language-definition terms, and that is
what the discussion was about. The implementation appears to be about the same
to me.

> >...Can't win. ;-)
>
> Well, we can't win if we add complexity in order to simplify things.
> ;-)

No complexity added here to the language, maybe to the implementation, but if
the question is trading off between complexity in the language versus complexity
in the implementation, the language will win every time.

> > (3) I envisioned the tasks being on a linked list associated with
> > the subpool. This is *not* in any way a master, it's much closer to
> > the task activation list. (Indeed, I'd use the task activation list
> > to implement it, making a copy into the subpool list before
> > activating the tasks of an
> > allocator.)                         ^^^^^^^^^^^^^^^^^
>
> I don't see what it has to do with activation.

It has nothing to do with activation, I'd just use that data structure to
implement it. (There is a list of tasks waiting to be activated; this is the
same sort of list of tasks.) I'd probably use a separate copy rather than
sharing it, but I'd use the same structure to avoid having to create a new set
of task operations.

I'm thinking very specifically as to how tasks are implemented in Janus/Ada.
There is a simple "task ring" data structure that is used for lots of things
(the activation list, priority/delay/read queues, waiting lists, etc.) That's
what I'd use here. The task master data structure is far more complex, involving
layers of whom owns who, lists of tasks in different states, and more. I would
*not* use that here.

> And if you're going to reuse activation list links for this unrelated
> purpose, don't you mean "after activating", rather than "before
> activating" above?

Possibly. But if the list is a separate list (which is what I was thinking),
then it doesn't matter.

> >...If U_D_S is called, you'd walk the list, poke each task, walk  the
> >list again, wait for each if necessary. This is definitely not as
> >efficient as possible, but it is easy. If someone actually cares, you
> >can worry about doing a better job. You probably can write this using
> >the existing primitives in your task system (especially if there is a
> >wait for terminate routine; else you'd have to use a slow busy-wait
> >loop, which is definitely not optimal).
>
> I don't see how this can work.  The AI says you wait for the ones that
> are completed.  But the ones that are running can complete (or get to
> a terminate alternative) while all this is going on.

There is clearly a race condition here, but that is always true with task
termination. Since termination is a one-way thing, it doesn't matter.

I've probably over simplified this a bit -- perhaps you have to set a flag on
the first pass to determine which ones need to be waited for. I don't see a
major problem.

> Anyway, I don't think there's a "wait for a particular task to
> terminate" in our runtimes.  There's a "complete master"
> primitive, which waits for a group of tasks to terminate (or get to
> terminate alternatives).  It works by counting tasks.
> That's why I think it's simplest to say that a subpool is a master.

Yes, but that is such a complex data structure that there is no chance of
reusing without a lot of change (even for something this similar). And in any
case, we don't want to wait for running tasks, just kill off the ones that are
already done.

> (Well, simplest would be to raise an exception if anybody allocates
> objects containing tasks in subpools.  I advocated that before, but it
> didn't fly.)

I have too. I suspect that you and I are closer than you think here.

The problem that I have with that is the fact that programs in the future are
probably going to have a lot more tasks. And you always say that you don't want
artificial choices (that is, I can use tasks or I can use subpools, but I can't
have both).

> > Keep in mind that embedding tasks in a complex data structure is
> > extremely rare. I've never done it outside of the ACATS. I have
> > plenty of tasks that contain a data structure, but the most complex
> > task data structure I've ever used is an array of tasks. So the
> > performance of the solution for U_D_S is secondary, at least until
> > there is a customer demand for improvement. (And remember that
> > premature optimization is the root of a lot of evil!)
>
> I'm not at all concerned with efficiency of tasks in subpools.
> I'm just complaining about implementation effort for a feature that,
> as you say, will be rare.

I don't see it as that hard (as described above), presuming you don't care about
the quality. You could even use a slow busy-wait loop if you don't have a "wait
for termination":

    for T of Subpool_Task_List loop -- T is a TCB or whatever data structure represents a task.
        if T.Waiting_at_Terminate then
            Trigger_Terminate(T);
            T.Subpool_Wait := True;
        elsif T.Completed then -- T'Completed
            T.Subpool_Wait := True;
        else
            T.Subpool_Wait := False;
        end if;
    end loop;
    for T of Subpool_Task_List loop
        if T.Subpool_Wait then -- Wait for T to become terminated.
            while not T.Terminated loop -- T'Terminated
                Yield; -- Delay 0.0; -- Give up slice and let others tasks run, hopefully including T.
            end loop;
        end if;
    end loop;

Surely not optimal, but it works, and it sure isn't complicated. This adds at
*most* one list and one flag (the other things all have to exist in some form).
Hard to imagine how that is a big deal.

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

From: Randy Brukardt
Sent: Friday, April  8, 2011  12:54 AM

...
> First issue: "new".
>
> > 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.}
>
> The above seems reasonable.

This is wrong. It depends on the type of the pool, not the syntax of the
allocator. The pool should not have to care about how the allocator is written.

>  But it contradicts what 13.11.4 says:
>
> > When an allocator for a type whose storage pool supports subpools is
> > evaluated, a call is made on Allocate_From_Subpool passing in a
> > Subpool_Handle, in addition to the parameters as defined for calls
> > on Allocate (see 13.11). The subpool handle is the one given in the
> > allocator if a *subpool_handle_*name is specified, or otherwise the
> > handle obtained by calling Default_Subpool_for_Pool on the pool of
> > the type of the allocator. All requirements on the Allocate
> > procedure also apply to Allocate_from_Subpool.
>
> Note that "type whose storage pool supports subpools" is not a
> statically-known thing.  (You could say "for ...'Storage_Pool use X;",
> where X is of type Root_Storage_Pool, and we don't know if X in
> Root_Storage_Pool_with_Subpools.

Right.

> For "new T", we certainly don't want to check at run time whether to
> do a dispatching call to Allocate or Allocate_From_Subpool -- the
> dispatching itself should do the necessary run-time thing.  We want to
> simply call Allocate(T'Storage_Pool, ...) as 13.11(16/3) above says.

I understand; but this design is fully intentional. Not only does it make more
sense (as noted above), but it also eases implementation (at least if you are
clever enough :-).

Beyond that, I can't implement a syntax-based rule without excessive overhead.
So I wrote the rules that I could implement reasonably, and still make sense.

Let me try to explain the problem and the implementation that I wanted to use.

The vast majority of allocations in Janus/Ada 95 are through some storage pool
(including most temporaries and the contents of what GNAT calls the "secondary
stack"). Also, most complex composite types are allocated (and assigned and
compared and...) via thunks. The thunks all take a storage pool parameter.

In order to implement subpools, we'd have to add a subpool parameter to those
thunks. That's easy enough, but then we're faced with the problem of how to
implement them. The best solution is to dispatch just to Allocate_from_Subpool,
and let it call Allocate if needed for compatibility.

What I wanted from the beginning is a single storage pool type. That type would
have Allocate_from_Subpool, which would by default dispatch to Allocate (so it
remains compatible). (Indeed, the inability to do this is why I opposed the
early versions of this proposal.)

But it doesn't make much sense to have Allocate_from_Subpool in the root pool
type which doesn't have any subpools. But it is perfectly OK to have such an
operation in the private part of Root_Storage_Pool. That operation would always
dispatch to Allocate (it has to dispatch as it will remain unchanged all the way
up the non-subpool hierarchy, so static binding would fail).

The only problem is to get the Root_Subpool to use the same slot for the visible
Allocate_from_Subpool (as it is "overriding" in this design, even though the
thing it is overriding is invisible). Luckily, these types are built-in to
Janus/Ada, so making sure the slots are the same just requires using the same
named constant in each (the fact that Ada would do something different is
irrelevant).

So, with that (invisible and compatible) change to Root_Storage_Pool, we never
have to call Allocate directly; we always call Allocate_from_Subpool.

However, there is the one obvious side-effect: there cannot be any rules in the
language that require calling Allocate directly for a storage pool that supports
storage pools. That's why the rules are the way that they are.

Since 95% of the time, the kind of pool is known statically for an allocator,
compilers can optimize this to call Allocate directly when they know the kind.
Janus/Ada at least will always call Allocate_from_Subpool in the other cases,
using the result of Default_Subpool_for_Pool (which also is dispatching, and
will return something of the right size for a "regular" pool), and it will
always call Allocate_from_Subpool inside of thunks.

The alternatives to this design pretty much either require duplicating all of
the thunks, duplicating the contents of the thunks, or passing additional
parameters to describe the type of the allocator. That adds a lot of extra code
size and compiler complexity; the code size isn't acceptable for a compiler that
is designed to minimize code size at every step. (Who would want a compiler that
generates large and slow code?? :-)

To me this is a show-stopper; the only way that I ever supported this proposal
is because the implementation I described would work. If we decide to change
this, I will withdraw my support for this AI (Brad's proposal, even with all of
its problems, would be easier to implement within our model -- so I will lobby
to kill this completely as it is too late to seriously consider his
alternative). Sorry about the threat, but I would rather have nothing than a
feature in that standard that is too much of a drag on our implementation, no
matter how cool it is.

> It makes no sense for somebody to write storage management code twice
> -- once in Allocate, and once in Allocate_From_Subpool.

Correct, they only need to write Allocate_From_Subpool.

> Therefore, I think there should be a concrete overriding of Allocate
> on Root_Storage_Pool_with_Subpools, which does:
>
>     procedure Allocate (...) is
>     ...
>         Allocate_From_Subpool
>             (Pool,
>              Storage_Address, Size_In_Storage_Elements, Alignment,
>              Subpool => Default_Subpool_for_Pool (Pool));
>
> I suppose types derived from Root_Storage_Pool_with_Subpools could
> override that, but I don't see why they would want to.
> And I don't see why we want to require them to (which is the current
> situation -- Allocate is abstract).

That's not a bad idea, but Ada has never required bodies, and I don't know how
to describe the above in words.

OTOH, since no one and nothing should ever call this Allocate, it might as well
just raise Program_Error. The only reason I didn't write it this way is not
wanting to violate LSP that obviously. (But no matter what we do, this design
horribly violates LSP!)

> It's done the other way around in the example (Allocate_From_Subpool
> calls Allocate), but that seems backwards to me, and only works in
> this example because of the primitive nature of "mark/release".

It was simpler, not better.

> Once you choose the "subpools" world, you want to all the allocation
> in subpools, not some hybrid mixture of pools and subpools.  Allocate for
> (Root_Storage_Pool_with_Subpools) is just a bridge into the subpools world.

Right, and nothing should ever call Allocate, it doesn't have the needed
information.

> So the rule about what "new" does should be based on the syntax of the
> "new": if it doesn't specify a subpool, it calls Allocate, if it does
> specify a subpool, it calls Allocate_From_Subpool.

As previously noted, I can't implement that as the "inner" allocate has no way
to find out what the "syntax" of "new" is. The top-level allocate can see that,
but that doesn't work in general. (There are similar problems for allocations of
generic formal types in our generic bodies -- requiring two pairs of thunks or
passing an extra parameter and doubling the code is just going too far,
especially for something that will be used as rarely as this.)

Beyond that, I don't think there is any sane reason to ever call Allocate for
this sort of pool. It just makes sense to not have to think about it or confuse
the user to try to figure out that there is a magic implementation of Allocate
that exists. The only reason the specification even has the routine is that it
is inherited from the root pool type. I don't think calling Allocate half of the
time is going to help understanding any.

> ----------------
>
> Do we need a legality rule preventing "new (Subpool) ..." if the pool
> type is not statically known to support subpools?
>
>     type Not_Subpool_Acc is access all Integer;
>     --  No "for Not_Subpool_Acc'Storage_Pool" clause!
>     X : Not_Subpool_Acc := new (Some_Misc_Subpool) Integer;

No idea. I only worried about dynamic rules, and as you point out, this is not
something that is known all of the time, so it gets messy to define a rule.
Off-hand, I can't think of any way to describe this that would allow "unknown"
pools (classwide pools) and Pools with subpools but not allow types derived from
Root_Storage_Pool (directly or indirectly). If you want to propose something, go
ahead.

> > 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.
>
> Is this intended to prevent the above case.  I.e. the initial value of
> X should raise Program_Error?  If so, it certainly deserves an AARM
> comment.

Yes, this will definitely prevent the above.

> Why non-null?  Shouldn't "new (null) ..." raise an exception?
> I realize Allocate_From_Subpool says "not null", but it still seems
> confusing here.

You can't do *this* check on a null pool, because it is implemented by a call on
Pool_of_Subpool, and that has a not null parameter. A null subpool should
violate some other check (but that seems to be missing).

Alternatively, we could have said:

If the allocator includes a *subpool_handle_*name, the allocator raises
Program_Error if the subpool is null or does not *belong* (see 13.11.4) to the
storage pool of the access type of the allocator.

which would make null subpools raise Program_Error before trying to call
Pool_of_Subpool.

It's not clear to me that there is a formal definition of "belong" anywhere,
either. But perhaps it is obvious enough.

...
> >        function Default_Subpool_for_Pool(
> >          Pool : in Root_Storage_Pool_with_Subpools) return not null Subpool_Handle;
> >            -- Returns a handle of the default subpool for Pool.
> >            -- Note: If no default subpool is supported, this routine should
> >            -- raise Storage_Error.
>
> Is this one intended to be abstract?

Yes, I think it is supposed to be abstract.

> If not, then there
> needs to be wording saying what the body does.  I don't understand how
> it's supposed to work.
> Seems like either the pool-writer, or the Ada implementation, should
> be responsible for default pools -- not both.
>
> > A subpool may be specified as the default to be used for allocation
> > from the associated storage pool, ...
>
> How?  By whom?  There's no Set_Default_Subpool operation.

By the pool implementer, by implementing this routine.

> ----------------
>
> There's no mention of Unchecked_Deallocation of objects from subpools.

That's intentional. It isn't supposed to be changed from the "normal"
version. In either case, it has to be removed from the "collection".

> Is the following a correct understanding of finalization of an object
> allocated in a subpool?
>
>     - When U_D is called, the object is finalized,
>       and then Deallocate is called on the Pool,
>       which typically will do nothing.  If it wants to do
>       something, it will probably need some way to get from
>       the address to the subpool -- that's the user's problem.

Right.

>       There is no Deallocate_From_Subpool.

Right, because that would require the language to keep the subpools in the
pointers or objects somehow. We don't want to do that.

>     - If U_D is not called, the object will be finalized
>       when Unchecked_Deallocate_Subpool is called.

Right.

>     - If that's never called, then it will be finalized
>       when the Pool_With_Subpools is finalized (by permission --
>       it might happen when the collection of the access type
>       is finalized).
>
> Right?

Right.

> > Add after 7.6.1(20):
> >
> > Implementation Permissions
> >
> > The implementation may finalize objects created by allocators for an
> > access type whose storage pool supports subpools (see 13.11.4) as if
> > the objects were created (in an arbitrary object) at the point where
> > the storage pool was elaborated instead
>
> "object" --> "order"?

Yup. Mistake #3.

> AI 190 is messing around in this same area, and somebody needs to
> verify that it all makes sense.

Isn't that the author of the latest AI? (i.e. AI05-0190-1, some guy named Duff.
:-)

> Why is this a permission?  Seems like it should be a requirement.
> Why don't we say that finalization of a subpool finalizes everything
> allocated in it, and finalization of a pool that supports subpools
> finalizes all the remaining subpools?

Because there was a bunch of people that didn't like the changing the model of
the masters, so we left them identical, with just this permission to finalize a
bit late. I doubt many implementers are going to do it the normal way, but it
shouldn't matter either way (depending on the details of finalization in a
single scope is always iffy, although sometimes it can't be helped).

> > of the first freezing point of the access type.
> >
> > AARM Ramification: This allows the finalization of such objects to
> > occur later than they otherwise would, but still as part of
> the finalization of the same master.
>
> ", but still..." -->
>
> "Rules below ensure this happens as part of the same master."

I don't think this is an improvement. I'm not talking about why, that's
irrelevant here, only that the finalization is certain to be in the same master.
This is a Ramification, not a Master's degree program. (Pun intended.)

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

From: Bob Duff
Sent: Friday, April  8, 2011  5:29 AM

> I agree with Bob. Indeed, I would argue that in practice that a
> dangling subpool handle is safer than a dangling (container) cursor;
> the language rules require it to be detected 99% of the time (the
> language does not
> *require* detection of a dangling cursor, although it can be detected
> 99% of the time as well). In order for a dangling subpool handle to go
> undetected, it has to point at memory that *happens* to contain a
> pointer to the correct pool for the allocator, an unlikely occurrence
> (especially as the language requires that pointer to be cleared when
> the subpool is destroyed; it can only have the correct value if some
> subsequent operation has reopened the subpool).

Yes, that's a good point, which I missed yesterday.  The AI even points this out
-- the "is correct subpool?" check will likely catch such problems.

By the way, to clarify my position on efficiency of subpools: I don't much care
about efficiency of the "fancy" stuff (tasks, controlled). But efficiency of
subpool allocation is critical for plain vanilla records and the like.  It will
be important for any program that allocates large numbers of small-ish things
(which is exactly what subpools are for).

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

From: Bob Duff
Sent: Friday, April  8, 2011  10:14 AM

> > I would also like to hear from Tucker and others.
> > I really think this AI needs substantial work, and it's important
> > AI, so we should expend the effort (even though I know Randy is
> > frustrated about things taking too long!).
>
> I can believe it needs a couple of tweaks, but not "substantial work".

Well, you're probably right -- it needs some tweaks.
But these are substantive enough that we need to withdraw the "ARG Approved"
status and have some serious technical discussion, and another vote.

> Unless you want to re-argue the same points we've already discussed...

Yes, I do.  This is the first time that people have seriously tried to implement
the AI.  As far as I'm concerned it's pretty much unimplementable in its present
form. But I do agree that it could be fixed with a few details changed.

> At this point, we can make some minor fixes, but a major redo means
> it's out completely.

As far as I'm concerned, it should be out completely, if we can't or won't fix
it.  AdaCore can always implement something along these lines, perhaps for
possible standardization in Ada 2020.

(from another email):

> To me this is a show-stopper; the only way that I ever supported this
> proposal is because the implementation I described would work. If we
> decide to change this, I will withdraw my support for this AI (Brad's
> proposal, even with all of its problems, would be easier to implement
> within our model
> -- so I will lobby to kill this completely as it is too late to
> seriously consider his alternative). Sorry about the threat, but I
> would rather have nothing than a feature in that standard that is too
> much of a drag on our implementation, no matter how cool it is.

I understand, and sympathize, with your threat.  But I must say that I'm about
ready to play the same trump card.

Several people in AdaCore have already suggested that GNAT should simply refuse
to implement all this stuff.

>... Besides, if we consider that, we have to seriously consider  Brad's
>proposal as well (it *does* seem simpler still, even if it doesn't
>work as written).

I did consider it, and sent some comments about why I think it's not the best
approach.  I think the -3 version should be fixed, rather than going with the -4
version.

>...But waiting is for *uncompleted* tasks is  not an option.

I really think shooting down my reasonable ideas with "not an option"
and "nonstarter" and "unacceptable" and the like is unhelpful.  We need
technical reasons for our decisions, not pronouncements from on high about what
is and is not allowed to be considered.

> No complexity added here to the language, maybe to the implementation,
> but if the question is trading off between complexity in the language
> versus complexity in the implementation, the language will win every time.

I really hope you don't mean that seriously.  It's language lawyers run amok!
Inventing useless semantics, with huge implementation costs, just to make the RM
wording easier is just nuts!

Anyway, if wording is worrying you, I'm willing to take over wording of this AI,
so long as we can more-or-less agree on what we want.

> > (Well, simplest would be to raise an exception if anybody allocates
> > objects containing tasks in subpools.  I advocated that before, but
> > it didn't fly.)
>
> I have too. I suspect that you and I are closer than you think here.

:-)

> I don't see it as that hard (as described above), presuming you don't
> care about the quality. You could even use a slow busy-wait loop if
> you don't have a "wait for termination":
>
>     for T of Subpool_Task_List loop -- T is a TCB or whatever data
> structure ...[details snipped]

In other words, you agree with me that a task must be a part of two separate
termination-related data structures.  Your pseudo code is all well and good, but
it's rather incomplete -- it doesn't show any locking, and all these data
structures need to be untangled at various times (abort, ATC, task completion).

I recently fixed a bug in the task termination code, which had been causing
intermittent failures (test hangs 1 / 1000 runs), which we've known about for
years, and nobody was willing and able to fix, and it took me 3 days to track
down the problem.  A race condition in an "if T is waiting on terminate ..."
(might be False now, but might become True soon) -- quite similar to one of the
issues I raise on this AI.

It would be completely irresponsible of me to do any major surgery on that
delicate code.  To use your term, an additional termination-related task list is
a non-starter, for me.

Also non-starters:

    - A dynamic check whether to call Allocate or Allocate_From_Subpool.
      Dispatching calls are supposed to do dynamic checks automatically.

    - Can't think of any others, right now, so I'll end my
      rant here. ;-)

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

From: Tucker Taft
Sent: Friday, April  8, 2011  11:04 AM

It does seem important to learn from this early implementation experience.  In
fact, it is great that we have this kind of early feedback.  Much better than a
bunch of AIs in a year or two.

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

From: Edmond Schonberg
Sent: Friday, April  8, 2011  11:26 AM

Indeed, and the outcome of these implementation discussions at AdaCore is that
most everyone here is in favor of dropping subpools altogether. There are too
many semantic holes and too many implementation difficulties, and precious
little perceived need for this complex feature.

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

From: Tucker Taft
Sent: Friday, April  8, 2011  11:43 AM

Well that is not quite the kind of feedback that *I* was interested in. I was
interested in feedback which would allow us to "tweak" the definition to make
sure it is implementable.  At this point I would agree with Randy that the
burden of proof is on the implementor to show that the existing proposal is
unimplementable and cannot be fixed with a modest amount of rewording, given
that the AI has already been approved by the ARG.

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

From: Arnaud Charlet
Sent: Friday, April  8, 2011  12:32 PM

OK well, as the AdaCore main tasking expert I had a look at this proposal, and
the handling of task termination is just not applicable and will not fit into
GNAT's tasking run-time model.

I'd suggest we let Bob try to come up with something simpler, but if we can't
agree on something implementable by everyone involved, we should delay the
proposal for Ada 2020 IMO.

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

From: Edmond Schonberg
Sent: Friday, April  8, 2011  1:27 PM

I'm not sure about the weight of that "burden of proof"!  If our experts in
particular aspects of our technology find that there is no way to do something
without a major architectural redesign, I don't see a counter-argument that
would say "yes you can do it". Right now the sense of those that have looked
more closely at subpools is that tasks present unacceptable difficulties. It
tasks are somehow forbidden in subpools we will re-evaluate the implementation
burden of the rest.

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

From: Brad Moore
Sent: Friday, April  8, 2011  2:09 PM

Not sure if I agree about perceived need.
For example, with a single announcement on comp.lang.ada as well as mentioning
on the ARG list, the Deepend pool stats already show 61 downloads at
sourceforge.net, including downloads from the following countries. US, Canada,
Italy, Sweden, Germany, France, Belgium, UK, and India.

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

From: Edmond Schonberg
Sent: Friday, April  8, 2011  2:22 PM

I notice that Deepend specifically excludes tasks and anything that might
require finalization. At that point indeed subpools are a simple and convenient
mechanism for fast storage reclamation, and the implementation costs must be
very small.  However, the current AI is not amenable to implementation by "a
binding to Apache run time pool management"!

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

From: Randy Brukardt
Sent: Friday, April  8, 2011  2:56 PM

...
> I notice that Deepend specifically excludes tasks and anything that
> might require finalization. At that point indeed subpools are a simple
> and convenient mechanism for fast storage reclamation, and the
> implementation costs must be very small.  However, the current AI is
> not amenable to implementation by "a binding to Apache run time pool
> management"!

Right. If that exclusion is acceptable, then you can write whatever you want in
Ada 95 and the ARG need not get involved. (It's necessarily erroneous, but so
are 95% of the real programs that you can write in Ada.)

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

From: Brad Moore
Sent: Friday, April  8, 2011  3:28 PM

Yes, it excludes tasks and things needing finalization since there is no
portable way to do that currently. My point was that if there is this level of
interest in the deepend subpools, (even with all the limitations that Deepend
has), then it seems logicial to me that having portable language defined subpool
capability without these limitations would generate a higher level of interest.

Going out on a limb here, I suspect that as more people learn of subpool storage
management, I'm thinking subpools will be seen as a better alternative to GC
(which doesnt exist in Ada currently anyway), and normal heap U_D, subpool
storage management stands a good chance to catch on and conceivably become the
storage pool style of choice for many projects. I've spent a more than enough
time time finding and fixing memory leaks, memory corruption, etc. I'm thinking
I would want to generally use subpools as the default storage pool on new
projects if at all possible.

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

From: Brad Moore
Sent: Friday, April  8, 2011  2:20 PM

Some other "tweaks" and editorial comments are;

In the subpools package:
1) pramga Preelaborated  should be pragma Preelaborate
2) In the Set_Pool_Of_Subpool call, the "To" parameter is defined as;

      To : in out Root_Storage_Pool_With_Subpools'Class

      In the body, I could not store the reference to To in the subpool object.
      I think this parameter needs to be an access parameter as in;

      To : access Root_Storage_Pool_With_Subpools'Class

3. Default_Subpool_Of_Pool
     Like Bob, I found that I needed to make this abstract

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

From: Randy Brukardt
Sent: Friday, April  8, 2011  2:54 PM

> 2) In the Set_Pool_Of_Subpool call, the "To" parameter is defined as;

>      To : in out Root_Storage_Pool_With_Subpools'Class

>      In the body, I could not store the reference to To in the subpool object.

You need to use Unchecked_Access for that; you will in any event. (You can never
use 'Access with a parameter, and since that is pretty much the only time I need
'Access, I find it useless.) It's safe because the subpool can't outlive the
pool, so the accessibility check just gets in the way. We already had this
discussion at an ARG meeting.

>      I think this parameter needs to be an access parameter as in;
>
>	      To : access Root_Storage_Pool_With_Subpools'Class

That won't help, because the dynamic accessibility check might (probably) will
fail. And in any case, we don't want the overhead.

The other two things are bugs that need to be fixed.

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

From: Tucker Taft
Sent: Friday, April  8, 2011  3:39 PM

I think we could outlaw tasks (or make the behavior implementation-defined or a
bounded error) in these things. What really matters is having finalization work
properly.

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

From: Randy Brukardt
Sent: Friday, April  8, 2011  3:43 PM

Bob Duff writes:
> "Randy Brukardt" <randy@rrsoftware.com> wrote:
>
> > Bob Duff writes:
> > > I would also like to hear from Tucker and others.
> > > I really think this AI needs substantial work, and it's important
> > > AI, so we should expend the effort (even though I know Randy is
> > > frustrated about things taking too long!).
> >
> > I can believe it needs a couple of tweaks, but not
> "substantial work".
>
> Well, you're probably right -- it needs some tweaks.
> But these are substantive enough that we need to withdraw the "ARG
> Approved" status and have some serious technical discussion, and
> another vote.

That will be to withdraw permanently. It is too late for anything else.

> > Unless you want to re-argue the same points we've already discussed...
>
> Yes, I do.  This is the first time that people have seriously tried to
> implement the AI.  As far as I'm concerned it's pretty much
> unimplementable in its present form.
> But I do agree that it could be fixed with a few details changed.

OK, then I don't think there is much point in continuing. I'll give it one more
go, but that's it.

> > At this point, we can make some minor fixes, but a major redo means
> > it's out completely.
>
> As far as I'm concerned, it should be out completely, if we can't or
> won't fix it.  AdaCore can always implement something along these
> lines, perhaps for possible standardization in Ada 2020.

There is no way that what you are describing could be standardized while I'm
around. It's a dead-body issue for me. I'll fight it any way I can.

> (from another email):
>
> > To me this is a show-stopper; the only way that I ever supported
> > this proposal is because the implementation I described would work.
> > If we decide to change this, I will withdraw my support for this AI
> > (Brad's proposal, even with all of its problems, would be easier to
> > implement within our model -- so I will lobby to kill this
> > completely as it is too late to seriously consider his alternative).
> > Sorry about the threat, but I would rather have nothing than a
> > feature in that standard that is too much of a drag on our
> > implementation, no matter how cool it is.
>
> I understand, and sympathize, with your threat.  But I must say that
> I'm about ready to play the same trump card.

Fair enough. That's why I'm not going to spend much more time on technical
discussion.

> Several people in AdaCore have already suggested that GNAT should
> simply refuse to implement all this stuff.

That says that we should kill the AI permanently. This is pretty close to the
best solution that we can come up with.

> >... Besides, if we consider that, we have to seriously consider
> >Brad's proposal as well (it *does* seem simpler still, even if it
> >doesn't work as written).
>
> I did consider it, and sent some comments about why I think it's not
> the best approach.  I think the -3 version should be fixed, rather
> than going with the -4 version.

OK, but the problems that you are complaining about don't occur in Brad's
version. I do agree his version is much less safe in practice (a lot which can
be checked in -3 cannot be checked in -4), but it surely is more implementable.

> >...But waiting is for *uncompleted* tasks is  not an option.
>
> I really think shooting down my reasonable ideas with "not an option"
> and "nonstarter" and "unacceptable" and the like is unhelpful.  We
> need technical reasons for our decisions, not pronouncements from on
> high about what is and is not allowed to be considered.

I gave the technical reason, and followed that by saying ignoring that technical
reason is a nonstarter in my view. If you chose to ignore my technical arguments
and solely answer my hyperbole (which is what you did in this message), you are
more guilty than I of refusing to understand/discuss.

To repeat: being able to convert current uses of U_D to U_D_S without much
disruption is a critical capability in my view. (I don't expect to be starting
many *new* Ada projects, but I'd like to be able to use this facility in
*existing* projects.)

As such, tasks need to work roughly the same way. U_D waits for no tasks.
Waiting for completed tasks to finalize should take very little time (unless the
tasks are terribly designed), but waiting for uncompleted ones could take huge
amounts of time and really change the way that programs operate. I don't think
this is an acceptable trade-off.

If we have to change the U_D_S semantics, it would be to not wait at all (making
it identical to U_D). I don't think waiting all the time is a good idea.

> > No complexity added here to the language, maybe to the
> > implementation, but if the question is trading off between
> > complexity in the language versus complexity in the implementation,
> > the language will win every time.
>
> I really hope you don't mean that seriously.  It's language lawyers
> run amok!  Inventing useless semantics, with huge implementation
> costs, just to make the RM wording easier is just nuts!

This is *not* useless semantics. Completed tasks of access types hang around
forever (until the access type goes away, which is effectively forever), and
this is a huge drag on usability of tasks in Ada. Janus/Ada, for instance, can
only create about 400 simultaneous tasks due to the way the stack is implemented
on Windows. (We don't use threads, and Windows traps any calls where the stack
pointer points to non-stack memory, so we have to use part of the main stack for
task stacks.) The inability to terminate those tasks means that zombies hang
around forever and make some program architectures impossible. (Once terminated,
we can free and reuse the task stacks.)

The idea of the U_D_S semantics is to kill those zombies, but do so with a
minimum of wait time. I believe the U_D should also have these semantics: the
fact that I can't finalize those inaccessible, completed tasks is criminal. But
I couldn't convince anyone to take the incompatibility.

But in any case, my point was that the full ARG was unwilling to accept the
complications of dynamic masters. The only way that it appeared that we could
get this AI through the ARG was to drop that semantics.

We could make U_D_S like U_D, although that would make it less useful on
Janus/Ada and probably most other compilers.

> Anyway, if wording is worrying you, I'm willing to take over wording
> of this AI, so long as we can more-or-less agree on what we want.

No, the wording was fine. The problem was that the ARG as a whole would not
accept the introduction of dynamic masters.

Keep in mind that the only strong supporters of this idea are you and Tucker.
(Maybe Brad.) The rest of us are trying to make you guys happy.

> > > (Well, simplest would be to raise an exception if anybody
> > > allocates objects containing tasks in subpools.  I advocated that
> > > before, but it didn't fly.)
> >
> > I have too. I suspect that you and I are closer than you think here.
>
> :-)

I do worry that we both are programming in the 1990's. Both tasks and controlled
types are very important to the problems that will be tackled in the future,
tasks because of machines with many cores, and controlled types because of OOP
and containers. Just because we haven't seen a lot of those uses in the past
doesn't mean that they won't be seen in the future.

> > I don't see it as that hard (as described above), presuming you
> > don't care about the quality. You could even use a slow busy-wait
> > loop if you don't have a "wait for termination":
> >
> >     for T of Subpool_Task_List loop -- T is a TCB or whatever data
> > structure ...[details snipped]
>
> In other words, you agree with me that a task must be a part of two
> separate termination-related data structures.  Your pseudo code is all
> well and good, but it's rather incomplete
> -- it doesn't show any locking, and all these data structures need to
> be untangled at various times (abort, ATC, task completion).
>
> I recently fixed a bug in the task termination code, which had been
> causing intermittent failures (test hangs 1 / 1000 runs), which we've
> known about for years, and nobody was willing and able to fix, and it
> took me 3 days to track down the problem.  A race condition in an "if
> T is waiting on terminate ..." (might be False now, but might become
> True
> soon) -- quite similar to one of the issues I raise on this AI.
>
> It would be completely irresponsible of me to do any major surgery on
> that delicate code.  To use your term, an additional
> termination-related task list is a non-starter, for me.

OK. Based on previous ARG discussions, this leaves us with four options on this
point:

(1) Don't allow tasks at all (raise Program_Error).
(2) Make U_D_S the same as U_D -- it has no effect on tasks.
(3) Convince Bob and the rest of AdaCore that they are wrong.
(4) Drop the AI.

(1) seems to say that Ada doesn't want to play nice with multicores.
(2) leaves a long-standing problem with Ada unfixed, and effectively says that
    Ada doesn't want to play nice with multicores.
(3) is unlikely, to say the least.

I could live with (2), but (4) looks more likely.

> Also non-starters:
>
>     - A dynamic check whether to call Allocate or Allocate_From_Subpool.
>       Dispatching calls are supposed to do dynamic checks automatically.

Exactly, if you need to do that you are doing something wrong. We actually want
exactly the same thing!

I explained how to implement the proposed rules with a single dispatching call
last night.

For me, the rule is that new T == new (Default_Subpool) T. I don't want any
difference between these, because that requires exactly what you say you can't
live with above -- a dynamic check to decide whether to call Allocate or
Allocate_From_Subpool. That happens in our thunks, in generic bodies, and
probably other places as well.

I want *all* allocators, regardless of form, to call a single dispatching
routine (the obvious candidate is Allocate_From_Subpool, but it could be a
hidden routine as well). I don't want *any* allocators being required to
directly call Allocate! (The rules themselves may appear to say otherwise for
compatibility reasons

Note this is an issue not just for allocators, but also for later allocations
from the same pool (such as the ones that happen during assignment of mutable
types). Having to have two different assignment routines that depend on the form
of the original allocator is just not sane -- for one thing, that would require
storing the form of the allocator into the object.

Now, when the pool is known, the compiler can and should optimize these into
direct calls to the appropriate routine. But what we are talking about is the
cases where the pool is not known.

We could make this model more explicit by adding an additional, concrete
allocator routine to Root_Storage_Pool. That routine would  take an "opaque"
extra parameter, and for Root_Storage_Pool would redispatch to Allocate. For
Pool_with_Subpools, it would redispatch to Allocate_with_Subpool, passing the
"opaque" parameter as the subpool handle.

I really don't have any choice on this one, as noted above. If we cannot agree
to a single dispatching model for allocation, then I have to vote *no* at every
level and in every way on this proposal. Forever and ever and ever. (I suppose
AdaCore could buy me off with a job or project, but I don't see enough desire
for this to want to do that.)

Let me repeat: making the syntax of the allocator relevant in what routine is
called would require me to store that form in every mutable object. And make
every allocator call in not just allocators but also initializations and
assignments conditional on that form. It's just too much overhead.

This is not a "line in the sand" for me, this is a brick wall. This feature is
nowhere near useful enough to destroy our entire memory allocation model.

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

From: Edmond Schonberg
Sent: Friday, April  8, 2011  4:01 PM

>OK. Based on previous ARG discussions, this leaves us with four options on
>this point:
>
>(1) Don't allow tasks at all (raise Program_Error).
>(2) Make U_D_S the same as U_D -- it has no effect on tasks.
>(3) Convince Bob and the rest of AdaCore that they are wrong.
>(4) Drop the AI.
>
>(1) seems to say that Ada doesn't want to play nice with multicores.

This is an extreme statement. Having local arrays of tasks in subprograms will
map perfectly well on multicores, and will clean up as well as it did in Ada83.
It is not subpools with dynamic task allocation that will give Ada the multicore
market :-)!

>(2) leaves a long-standing problem with Ada unfixed, and effectively says that
>Ada doesn't want to play nice with multicores.
>
>(3) is unlikely, to say the least.

>I could live with (2), but (4) looks more likely.

Without tasks we think that we can handle properly finalization in subpools (to
the extent we understand the current semantics).

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

From: Randy Brukardt
Sent: Friday, April  8, 2011  4:28 PM

>>	(1) seems to say that Ada doesn't want to play nice with multicores.
>
>	This is an extreme statement. Having local arrays of tasks in subprograms
>       will map perfectly well on multicores, and will clean up
>	as well as it did in Ada83.  It is not subpools with dynamic task
>       allocation that will give Ada the multicore market :-)!

I don't think so, but let me explain my logic:
(A) Supposedly, processors with hundreds or thousands of multicores are right
    around the corner.
(B) Many (most?) new designs are object-oriented in nature.
(C) New O-O designs are likely to include active elements in the objects (that
    is, embedded tasks).
(D) The Containers don't allow limited elements, so hand-written data structures
    will be needed to contain these O-O designs with active elements.
(E) Assuming Subpools are a good thing at all, they will be a good thing for
    these hand-written data structures. (They're unnecessary for designs using
    the Ada.Containers, which do storage management just fine, thank you.)

If people are managing hundreds of active elements, a simple flat structure is
unlikely to be sufficient. That's especially true if they need to be created and
destroyed. You are saying that it is OK if we prevent these users from ever
using subpools. *That* seems like an extreme statement to me.

Besides, I agree with Bob when he says that the existing Ada semantics is
unnecessarily hard to work with. You're suggesting that it be harder still. That
makes no sense.

OTOH,
>	(2) leaves a long-standing problem with Ada unfixed, and effectively says
>	that Ada doesn't want to play nice with multicores.

I would understand if you had said that (2) is an extreme statement, since it is
not as clear that clean-up alone is a sufficient problem. Perhaps by 2020, we'll
have so much memory and cores that it is perfectly OK to have tens of thousands
of zombie tasks hanging around.

I realized that this statement was a bit over the top when I wrote it.

>>	(3) is unlikely, to say the least.
>>
>>	I could live with (2), but (4) looks more likely.

>	Without tasks we think that we can handle properly finalization in
>       subpools (to the extent we understand the current semantics).

Sure, but Ada becomes unusable for complex active data structures. Maybe that
won't matter, but I will wager that if that happens, it is because tasks have
been replaced by something better (more structured) and not because of lack of
use.

[Note that personally I don't care that much about tasking, so I would live with
either (1) or (2). But I think (1) would be a long-term mistake, even if it is
expedient in the short-term. And the zombie task problem is not going away...but
I could imagine trying to solve that in some more consistent way that applies to
all types of destruction -- perhaps by adding a task aspect that says that the
task finalizes as soon as it completes.]

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

From: Robert Dewar
Sent: Friday, April  8, 2011  6:16 PM

>> I would also like to hear from Tucker and others.
>> I really think this AI needs substantial work, and it's important AI,
>> so we should expend the effort (even though I know Randy is
>> frustrated about things taking too long!).
>
> I can believe it needs a couple of tweaks, but not "substantial work".
> Unless you want to re-argue the same points we've already discussed...

I think we need to
>
> At this point, we can make some minor fixes, but a major redo means
> it's out completely. Besides, if we consider that, we have to
> seriously consider Brad's proposal as well (it *does* seem simpler
> still, even if it doesn't work as written).

Out completely may well be the appropriate status for this AI

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

From: Bob Duff
Sent: Sunday, April  10, 2011  7:13 AM

Let me focus on just one issue:

Basically, Randy wants Allocate_From_Subpool to dispatch to Allocate.
Bob wants to do it 'tother way 'round (Allocate dispatches to
Allocate_From_Subpool).  I might be willing to go along with Randy's way, but
first let me ask some questions:

> I understand; but this design is fully intentional. Not only does it
> make more sense (as noted above), but it also eases implementation (at
> least if you are clever enough :-).
>
> Beyond that, I can't implement a syntax-based rule without excessive
> overhead. So I wrote the rules that I could implement reasonably, and
> still make sense.
>
> Let me try to explain the problem and the implementation that I wanted
> to use.
>
> The vast majority of allocations in Janus/Ada 95 are through some
> storage pool (including most temporaries and the contents of what GNAT
> calls the "secondary stack"). Also, most complex composite types are
> allocated (and assigned and compared and...) via thunks. The thunks
> all take a storage pool parameter.
>
> In order to implement subpools, we'd have to add a subpool parameter
> to those thunks. That's easy enough, but then we're faced with the
> problem of how to implement them. The best solution is to dispatch
> just to Allocate_from_Subpool, and let it call Allocate if needed for compatibility.

Please explain what code you want to generate for "new T" and for "new
(My_Subpool) T".  Will both call the same thunk? And pass Subpool => null in the
former case?

What are these thunks?  One per access type?

> What I wanted from the beginning is a single storage pool type. That
> type would have Allocate_from_Subpool, which would by default dispatch
> to Allocate (so it remains compatible). (Indeed, the inability to do
> this is why I opposed the early versions of this proposal.)
>
> But it doesn't make much sense to have Allocate_from_Subpool in the
> root pool type which doesn't have any subpools. But it is perfectly OK
> to have such an operation in the private part of Root_Storage_Pool.
> That operation would always dispatch to Allocate (it has to dispatch
> as it will remain unchanged all the way up the non-subpool hierarchy,
> so static binding would fail).
>
> The only problem is to get the Root_Subpool to use the same slot for
> the visible Allocate_from_Subpool (as it is "overriding" in this
> design, even though the thing it is overriding is invisible). Luckily,
> these types are built-in to Janus/Ada, so making sure the slots are
> the same just requires using the same named constant in each (the fact
> that Ada would do something different is irrelevant).

I don't think this "magic" is necessary.

If it were necessary, I think it might be a show-stopper, for me, especially
given the way GNAT supports interface to C++, with inter-language dispatching
calls in both directions. It's a complicated area.

But fortunately, I don't think there's any problem:  Subpools is a child of
Storage_Pools, so if Storage_Pools has a primitive Allocate_from_Subpool in its
private part, and Subpools overrides that in its visible part, it will just
work.  The compiler can always generate a call to Allocate_from_Subpool, and if
it's not a supports-subpools pool, that will just dispatch to Allocate.  Or, the
compiler could choose to call Allocate directly.

This is a key point.  Please verify that I'm not missing something, here!

> So, with that (invisible and compatible) change to Root_Storage_Pool,
> we never have to call Allocate directly; we always call Allocate_from_Subpool.
>
> However, there is the one obvious side-effect: there cannot be any
> rules in the language that require calling Allocate directly for a
> storage pool that supports storage pools. That's why the rules are the way that they are.
           ^^^^^^^^^^^^^ You mean "subpools" here.

So, in your view, "new" on a pool that supports subpools, would never call
Allocate.  It would always call Allocate_from_Subpool, passing either the
specified subpool, or the Default_Subpool_for_Pool.

So there's never any reason for a type derived from
Root_Storage_Pool_with_Subpools to override Allocate. The only way Allocate
could be called is if the programmer writes "Allocate(...)".

So Root_Storage_Pool_with_Subpools could override Allocate, and have it raise
Program_Error, or call Allocate_from_Subpool, or whatever we like -- it doesn't
matter.

So we should change the example in the AI to avoid overriding and calling
Allocate.

> Since 95% of the time, the kind of pool is known statically for an
> allocator, ...

More like 99% !  ;-)

>...compilers can optimize this to call Allocate directly when they
>know the kind. Janus/Ada at least will always call
>Allocate_from_Subpool in  the other cases, using the result of
>Default_Subpool_for_Pool (which also is  dispatching, and will return something of the right size for a "regular"
> pool), and it will always call Allocate_from_Subpool inside of thunks.
>
> The alternatives to this design pretty much either require duplicating
> all of the thunks, duplicating the contents of the thunks, or passing
> additional parameters to describe the type of the allocator. That adds
> a lot of extra code size and compiler complexity; the code size isn't
> acceptable for a compiler that is designed to minimize code size at
> every step. (Who would want a compiler that generates large and slow
> code?? :-)
>
> To me this is a show-stopper; the only way that I ever supported this
> proposal is because the implementation I described would work. If we
> decide to change this, I will withdraw my support for this AI (Brad's
> proposal, even with all of its problems, would be easier to implement
> within our model
> -- so I will lobby to kill this completely as it is too late to
> seriously consider his alternative). Sorry about the threat, but I
> would rather have nothing than a feature in that standard that is too
> much of a drag on our implementation, no matter how cool it is.
>
> > It makes no sense for somebody to write storage management code
> > twice -- once in Allocate, and once in Allocate_From_Subpool.
>
> Correct, they only need to write Allocate_From_Subpool.

And Default_Subpool_for_Pool, right?

> > Therefore, I think there should be a concrete overriding of Allocate
> > on Root_Storage_Pool_with_Subpools, which does:
> >
> >     procedure Allocate (...) is
> >     ...
> >         Allocate_From_Subpool
> >             (Pool,
> >              Storage_Address, Size_In_Storage_Elements, Alignment,
> >              Subpool => Default_Subpool_for_Pool (Pool));
> >
> > I suppose types derived from Root_Storage_Pool_with_Subpools could
> > override that, but I don't see why they would want to.
> > And I don't see why we want to require them to (which is the current
> > situation -- Allocate is abstract).
>
> That's not a bad idea, but Ada has never required bodies, and I don't
> know how to describe the above in words.

Leave the wording to me!  If I can come up with something that's acceptable to
everyone, we can go with that.  If not, we'll forget the whole thing, and maybe
GNAT will implement a non-standard feature, or maybe not.

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

From: Robert Dewar
Sent: Sunday, April  10, 2011  8:40 AM

Reading the continued discussion on this item makes it clear at least to me that
we do not understand the issues well enough to set them in stone in a standard,
especially if it is done in a rush.

I think this is a feature that would be better handled by doing some
experimental implementations and see how they work out, then we can revisit
standardization next time around.

I don't think the Ada standard updates should be an opportunity for language
design in areas that we don't have a very clear idea of what we want.

I know people worry that this is an important feature, but if the existing 2012
implementations implement some version of this feature, that goes a long way to
taking care of things (for the majority of users, whether something is official
and in the standard is not a crucial point).

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

From: Randy Brukardt
Sent: Sunday, April  10, 2011  8:44 PM

...
> > In order to implement subpools, we'd have to add a subpool parameter
> > to those thunks. That's easy enough, but then we're faced with the
> > problem of how to implement them. The best solution is to dispatch
> > just to Allocate_from_Subpool, and let it call Allocate if needed
> > for compatibility.
>
> Please explain what code you want to generate for "new T" and for "new
> (My_Subpool) T".  Will both call the same thunk?
> And pass Subpool => null in the former case?

Yes, both will call the same thunk. The former case will pass whatever the
result of Default_Subpool_for_Pool is. (Null would almost work, see below.)

> What are these thunks?  One per access type?

The thunks are per record type (or a type that might be a record, like a private
type). Only the actual record type declaration has enough information to
generate one of these thunks.

Janus/Ada always removes statically uncalled subprograms (and even tries to do
so for dispatching calls), so if there are no access types, the allocation thunk
is removed.

The problem with generating two thunks (one for subpools, one for no subpools)
is that it is likely that both would be needed if a type with subpools is used.
That doubles the code size.

> > What I wanted from the beginning is a single storage pool type. That
> > type would have Allocate_from_Subpool, which would by default
> > dispatch to Allocate (so it remains compatible). (Indeed, the
> > inability to do this is why I opposed the early versions of this
> > proposal.)
> >
> > But it doesn't make much sense to have Allocate_from_Subpool in the
> > root pool type which doesn't have any subpools. But it is perfectly
> > OK to have such an operation in the private part of Root_Storage_Pool.
> > That operation would always dispatch to Allocate (it has to dispatch
> > as it will remain unchanged all the way up the non-subpool
> > hierarchy, so static binding would fail).
> >
> > The only problem is to get the Root_Subpool to use the same slot for
> > the visible Allocate_from_Subpool (as it is "overriding" in this
> > design, even though the thing it is overriding is invisible).
> > Luckily, these types are built-in to Janus/Ada, so making sure the
> > slots are the same just requires using the same named constant in
> > each (the fact that Ada would do something different is irrelevant).
>
> I don't think this "magic" is necessary.

I still do.

> If it were necessary, I think it might be a show-stopper, for me,
> especially given the way GNAT supports interface to C++, with
> inter-language dispatching calls in both directions.
> It's a complicated area.

But I don't see this (perhaps a lack of knowledge).

> But fortunately, I don't think there's any problem:  Subpools is a
> child of Storage_Pools, so if Storage_Pools has a primitive
> Allocate_from_Subpool in its private part, and Subpools overrides that
> in its visible part, it will just work.  The compiler can always
> generate a call to Allocate_from_Subpool, and if it's not a
> supports-subpools pool, that will just dispatch to Allocate.  Or, the
> compiler could choose to call Allocate directly.

No, unfortunately that is not true. *Ada* will not let you override an operation
declared in the private part in the visible part of another package (unless that
is a private package). Letting that overriding happen is the "magic" I was
referring to. Nothing more. I don't see how this particular magic would be a
problem vis-a-vis C++, since it is simply an artifact of the Ada visibility
model.

As I mentioned, since the packages are constructed by hand (as they are
built-ins) for Janus/Ada, supporting the otherwise illegal overriding is easy.
But I would not expect it to be quite that easy for another compiler.

> This is a key point.  Please verify that I'm not missing something, here!

Sadly, you were missing something here. Not a big deal, IMHO, but still more
than nothing.

> > So, with that (invisible and compatible) change to
> > Root_Storage_Pool, we never have to call Allocate directly; we
> > always call Allocate_from_Subpool.

Right, the change to Root_Storage_Pool is compatible and invisible.

Let me muddy the waters a bit with two other points.

I believe that my intention with this draft was that:
   new T  ===>  new (null) T   ===>  new (Default_Subpool_for_Pool) T
The main problem with this is that the wording describing that model is missing,
which is why you were confused about the use of "non-null".

Also, my original idea was that "null" would simply represent the default
subpool. Thus, we wouldn't need the routine Default_Subpool_for_Pool. However, I
recall that someone (I think it was you) insisted that we use "not null" on the
subpool parameters. That killed the "null" is the default subpool model.

Also note that that prevents using "null" for the subpool for "regular" pools.
(Unless we used more overriding magic, which I don't recommend - leaving "not
null" off of the private Allocate_from_Subpool would mean that profiles would
not be quite subtype conformant.) That's why I've been talking about a
dispatching call to Default_Subpool_for_Pool in that case.

I'd be happy to revert to my original model (it's simpler, even if a bit
weirder), as that would get rid of the Default_Subpool_for_Pool altogether.
(We'd also get rid of the "not null" on the Allocate_from_Subpool.)

> > However, there is the one obvious side-effect: there cannot be any
> > rules in the language that require calling Allocate directly for a
> > storage pool that supports storage pools. That's why the rules are
> > the way that they are.
>            ^^^^^^^^^^^^^ You mean "subpools" here.

Yes, of course.

> So, in your view, "new" on a pool that supports subpools, would never
> call Allocate.  It would always call Allocate_from_Subpool, passing
> either the specified subpool, or the Default_Subpool_for_Pool.

Right.

> So there's never any reason for a type derived from
> Root_Storage_Pool_with_Subpools to override Allocate.
> The only way Allocate could be called is if the programmer writes
> "Allocate(...)".

Well, there is one reason: it is abstract unless we decide to define it some
other way.

Note that explicit calls are not that uncommon; it's a typical construction in a
"wrapper" pool that provides some valuable service (like dangling pointer
checking). So it would be bad if they didn't work at all.

> So Root_Storage_Pool_with_Subpools could override Allocate, and have
> it raise Program_Error, or call Allocate_from_Subpool, or whatever we
> like -- it doesn't matter.

Right, except if someone is doing manual allocations for Pool'Class (or passing
a pool as a generic formal, it is effectively the same thing).

> So we should change the example in the AI to avoid overriding and
> calling Allocate.

Yes, I think would be a good idea.

I suspect that my original draft of this had missed some of these subtleties,
and I never went back and updated everything after I changed the model. (I'm
pretty sure I wrote it up some other way originally.)

> > Since 95% of the time, the kind of pool is known statically for an
> > allocator, ...
>
> More like 99% !  ;-)

Ah, you don't have shared generics. A formal pool object acts very much like a
class-wide pool object in Janus/Ada. If you are passing a pool into a container
generic, the access types will not know the kind.

...
> > > It makes no sense for somebody to write storage management code
> > > twice -- once in Allocate, and once in Allocate_From_Subpool.
> >
> > Correct, they only need to write Allocate_From_Subpool.
>
> And Default_Subpool_for_Pool, right?

Right. And the deallocator code, of course.

> > > Therefore, I think there should be a concrete overriding of
> > > Allocate on Root_Storage_Pool_with_Subpools, which does:
> > >
> > >     procedure Allocate (...) is
> > >     ...
> > >         Allocate_From_Subpool
> > >             (Pool,
> > >              Storage_Address, Size_In_Storage_Elements, Alignment,
> > >              Subpool => Default_Subpool_for_Pool (Pool));
> > >
> > > I suppose types derived from Root_Storage_Pool_with_Subpools could
> > > override that, but I don't see why they would want to.
> > > And I don't see why we want to require them to (which is the
> > > current situation -- Allocate is abstract).
> >
> > That's not a bad idea, but Ada has never required bodies, and I
> > don't know how to describe the above in words.
>
> Leave the wording to me!  If I can come up with something that's
> acceptable to everyone, we can go with that.  If not, we'll forget the
> whole thing, and maybe GNAT will implement a non-standard feature, or
> maybe not.

OK, you have a new action item. :-)

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

From: Robert Dewar
Sent: Sunday, April  10, 2011  8:40 AM

Reading the continued discussion on this item makes it clear at least to me that
we do not understand the issues well enough to set them in stone in a standard,
especially if it is done in a rush.

I think this is a feature that would be better handled by doing some
experimental implementations and see how they work out, then we can revisit
standardization next time around.

I don't think the Ada standard updates should be an opportunity for language
design in areas that we don't have a very clear idea of what we want.

I know people worry that this is an important feature, but if the existing 2012
implementations implement some version of this feature, that goes a long way to
taking care of things (for the majority of users, whether something is official
and in the standard is not a crucial point).

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

From: Robert Dewar
Sent: Sunday, April 10, 2011  9:03 PM

> Reading the continued discussion on this item makes it clear at least
> to me that we do not understand the issues well enough to set them in
> stone in a standard, especially if it is done in a rush.

I think this is a misreading of the actual case. If anything, some of us have
*too* clear of an understanding, so we try to explore all sides of a discussion,
which might make it look like we don't know what we want. Speaking for myself, I
know exactly what I want here -- and we've already done the hard work to get
that definition into wording.

In any case, Bob and I are mostly talking about cases that will be rare to very
rare in practice. (Bob claimed 1% of allocators at most, I wouldn't go that
far.). There is no problem with the way this feature is expected to be used in
practice. Tucker has previously described this part of standards-making as being
similar to watching sausage being made - sometimes its better to not look to
closely!

...
> I know people worry that this is an important feature, but if the
> existing 2012 implementations implement some version of this feature,
> that goes a long way to taking care of things (for the majority of
> users, whether something is official and in the standard is not a
> crucial point).

This is *exactly* what worries me. If GNAT implements some subpool-like feature,
then next time the ARG will have a take-it or leave-it situation with this
feature -- simply because too many GNAT customers will be using it for us to
change it. But implementer-designed features almost always are designed to be
easy to implement in their archtecture -- the design choices may not be all that
appropriate for both/either the language and other implementations.

This has happened before (Pure_Function comes to mind), where standardizing the
intended function was abandoned because it would be too incompatible with the
existing GNAT implementation.

Given that there are only a handful of areas where there are issues, I don't see
how an "experimental" version could be much better than this one, but it could
be a lot worse (fewer ways to detect problems, much harder to implement, etc.)

I'm not going to rule out dropping this AI, but let's see what Bob comes up with
first; perhaps it will be acceptable to all (or almost all).

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

From: Bob Duff
Sent: Sunday, April 10, 2011  9:34 PM

> > But fortunately, I don't think there's any problem:  Subpools is a
> > child of Storage_Pools, so if Storage_Pools has a primitive
> > Allocate_from_Subpool in its private part, and Subpools overrides
> > that in its visible part, it will just work.  The compiler can
> > always generate a call to Allocate_from_Subpool, and if it's not a
> > supports-subpools pool, that will just dispatch to Allocate.  Or,
> > the compiler could choose to call Allocate directly.
>
> No, unfortunately that is not true. *Ada* will not let you override an
> operation declared in the private part in the visible part of another
> package (unless that is a private package).

Sure it will, so long as the "another package" is a child of the one with the
private operation, which is the case here. Other language lawyers:  Please
confirm or deny!

Here's an example.  What do you think it should print?
In GNAT, it prints:

Alloc(T)
Alloc(TT)

with Text_IO; use Text_IO;
package Parent is
   type T is tagged limited private;
   procedure Classwide (X : in out T'Class); private
   type T is tagged limited null record;
   procedure Alloc (X : in out T);
end Parent;

package body Parent is
   procedure Alloc (X : in out T) is
   begin
      Put_Line ("Alloc(T)");
   end Alloc;

   procedure Classwide (X : in out T'Class) is
   begin
      Alloc (X);
   end Classwide;
end Parent;

package Parent.Child is
   type TT is new T with private;
   procedure Alloc (X : in out TT);
private
   type TT is new T with null record;
end Parent.Child;

package body Parent.Child is
   overriding procedure Alloc (X : in out TT) is
   begin
      Put_Line ("Alloc(TT)");
   end Alloc;
end Parent.Child;

with Parent.Child;
procedure Main is
   X : Parent.T;
   Y : Parent.Child.TT;
begin
   Parent.Classwide(X);
   Parent.Classwide(Y);
end Main;

I think this reflects the structure you want (I used the name "Alloc", where you
want "Allocate_From_Subpool").

The "overriding" keyword would be illegal on the spec of Alloc(TT), because it's
not publicly overriding -- but it is overriding.

No magic -- I just compiled it with GNAT.

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

From: Gary Dismukes
Sent: Sunday, April  10, 2011  11:19 PM

I concur that it works the way you said.  It doesn't have to be a private
package.

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

From: Randy Brukardt
Sent: Monday, April 11, 2011  6:02 PM

> > No, unfortunately that is not true. *Ada* will not let you override
> > an operation declared in the private part in the visible part of
> > another package (unless that is a private package).
>
> Sure it will, so long as the "another package" is a child of the one
> with the private operation, which is the case here.
> Other language lawyers:  Please confirm or deny!

I used logic, rather than studying the language rules in detail. Apparently, "logic" and Ada are rarely in the same room... :-)

Specifically, Ada tries very hard to prevent "leakage" of private information.
Overriding a routine that you can't see is definitely an example of such
leakage, so I presumed it was banned.

> Here's an example.  What do you think it should print?

I would have expected it to print Alloc(T) twice.

> In GNAT, it prints:
>
> Alloc(T)
> Alloc(TT)

It does that in Janus/Ada, as well, so I take that as an indication that Ada is
requiring privacy leakage here. [If Janus/Ada does this, it is almost certainly
because there is an ACATS test requiring this behavior. It's very unlikely that
both GNAT and Janus/Ada would have the same bug.] In this case, that's what we
want, so it's good. Less sure about the big picture. But that's irrelevant in
any case (we're not changing this, no matter what it says).

...
> I think this reflects the structure you want (I used the name "Alloc",
> where you want "Allocate_From_Subpool").

Yes.

> The "overriding" keyword would be illegal on the spec of Alloc(TT),
> because it's not publicly overriding -- but it is overriding.

OK, that's clearly part of what I was thinking. I was thinking that if you can't
say "overriding", then it should never be overriding, but apparently the
language rules say something else.

(I hate this, BTW, it means that it is impossible to keep implementation stuff
in the private part of Claw private. Anyone can declare a child of Claw and
override these routines and export these routines, precisely what we were trying
to prevent by putting them into the private part. Sigh.)

> No magic -- I just compiled it with GNAT.

OK, but I still think this shouldn't work. It makes hiding stuff impossible.
But it doesn't matter at this late date, we're surely not changing this behavior
-- as we've learned, even "safe", compatible changes in this behavior are
impossible.

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

From: Bob Duff
Sent: Monday, April 11, 2011  9:31 PM

> I used logic, rather than studying the language rules in detail.
> Apparently, "logic" and Ada are rarely in the same room... :-)

Well, Ada has its surprises, but you have to admit there are worse languages out
there.  ;-)

> (I hate this, BTW, it means that it is impossible to keep
> implementation stuff in the private part of Claw private. Anyone can
> declare a child of Claw and override these routines and export these
> routines, precisely what we were trying to prevent by putting them
> into the private part. Sigh.)

I think you have to view "adding a child" like opening the back of an appliance
and mucking about in there with a screw driver.  "Warrantee void if ...."  ;-)
On the bright side, the child can't evilly sneak itself into a program --
somebody has to explicitly "with" it.

Anyway, whether this is a feature or a malfeature, it appears to do what you
wanted for Allocate_from_Subpool, without any magic. You will no doubt need to
comment the code.  ;-)

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

From: Robert Dewar
Sent: Monday, April 11, 2011  4:31 AM

> Ah, you don't have shared generics. A formal pool object acts very
> much like a class-wide pool object in Janus/Ada. If you are passing a
> pool into a container generic, the access types will not know the kind.

In my opinion, it is time to stop worrying about compilers that insist on doing
shared generics for all generics. It's distorting otherwise sensible language
decisions.

It reminds me of the situation with Ada 95, where we deferred to the Alsys
insistence on keeping compatible with the use of global displays and badly
damaged the language as a result, only to find out that this technology was
never adapated to Ada 95 after all, so we had done the damage for no reason.

I perfectly well understand that the Janus/Ada design is predicated on shared
generics for everything, but I think that approach is fundamentally flawed.
Real-life Ada compilers may be able to use shared generics for some particular
cases, but to insist on doing it in all cases is IMO misguided, and in any case
I don't think we should let it be the tail that wags the dog in terms of future
language design.

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

From: Randy Brukardt
Sent: Monday, April 11, 2011  6:39 PM

> > Ah, you don't have shared generics. A formal pool object acts very
> > much like a class-wide pool object in Janus/Ada. If you are passing a
> > pool into a container generic, the access types will not know the kind.
>
> In my opinion, it is time to stop worrying about compilers that insist
> on doing shared generics for all generics. It's distorting otherwise
> sensible language decisions.

This rant is completely misplaced, I was merely noting that a case that comes up
in any case is slightly more likely to happen if you have shared generics. There
is no impact whatsoever stemming from Janus/Ada's use of shared generics on
AI05-0111-3 (or on most other proposals, for that matter).

All of the issues I had with AI05-0111-3 had to with two things:
  (1) Our implementation of non-contiguous types; and
  (2) Use of storage pools with subpools in generics.

The former has nothing to do with shared generics (it's possible with any type
that contains a dynamic or discriminant-dependent array), and the latter is in
user code (having nothing to do with the compiler).

So you should have been ranting about Ada allowing compilers to implement
non-contiguous objects. :-)

> It reminds me of the situation with Ada 95, where we deferred to the
> Alsys insistence on keeping compatible with the use of global displays
> and badly damaged the language as a result, only to find out that this
> technology was never adapated to Ada 95 after all, so we had done the
> damage for no reason.

Umm, Janus/Ada uses displays, and it surely implemented the vast majority of Ada
95. And it can implement Ada 2005 using displays as well. It's ever pretty
efficient, even in the nasty cases (which only have to do with the shared
generics), because we determine the deepest level used by the code and only copy
that much (that is at most 3 levels in non-test code that I have seen).

If I ever got rid of displays, it would be because the native threading of
Windows and Linux are hostile to displays on the X86, not any reason having to
do with the language.

> I perfectly well understand that the Janus/Ada design is predicated on
> shared generics for everything, but I think that approach is
> fundamentally flawed. Real-life Ada compilers may be able to use
> shared generics for some particular cases, but to insist on doing it
> in all cases is IMO misguided, and in any case I don't think we should
> let it be the tail that wags the dog in terms of future language
> design.

Well, I'm sure you are about to say that the use of displays and the use of
non-contiguous objects is also "misguided". Even though all of these things were
intentionally allowed in the Ada Standard.

A couple of days ago, you said that that WG 9 would never allow the ARG to
remove capabilities from the Standard that are in actual use. So why does this
not apply to shared generics???

What I keep hearing here is that it is "misguided" to make a design decision
that is different from GNAT. And you would be happy if the Standard pretty much
only supported your design decisions.

I admit that going against the crowd was an intentional design decision with
Janus/Ada -- it was apparent that we could never compete by building exactly the
same thing that the companies with more engineers and more money were building.
Why would anyone risk using a smaller companies' product unless it was different
in some valuable way? And I surely admit that not all of those choices worked
out all that well. But those are not relevant.

What we do not want is a standard that only allows implementations that are all
identical. Because in that market, there can only be one winner (mostly likely
AdaCore) and everyone else will disappear. I doubt that can be good for Ada.

P.S. Note that using shared generics was not a "contrary" decision; it was the
only possible design that did not require body dependencies. And on the small,
slow machines that we were designing for, link-time compilation was just not
acceptable. (Compilation times averaged 3-5 minutes per file on the original IBM
PC; if each instance required a link-time compilation, we would have been
looking at link times on the order of 30 minutes even for small programs that
just used Text_IO.) Indeed, before I got this quad core machine in 2008,
link-time compilation of generic bodies would still have been too slow even for
the relatively small projects I work on.

If I was starting a compiler today, I would surely make a different set of
design choices (lots more memory is available, recompilation isn't a major
issue, etc.). But I'm not, and I'm not going to spend two years to change this
one...

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

From: Randy Brukardt
Sent: Monday, April 11, 2011  6:42 PM

> > I think we could outlaw tasks (or make the behavior
> > implementation-defined or a bounded error) in these things.
>
> That's what I did in the new version of this AI, which I will send out
> soon.  See the AI for detailed wording.
>
> Randy is concerned about converting existing code to use subpools.
> But I really think such conversions are going to require some
> substantial reprogramming anyway -- you have to analyze which objects
> have similar lifetimes, and write code to put those in the same
> subpool(s).  You're not going to have a million different types
> containing tasks -- you'll have a few, and you'll have to treat those
> specially.

I'm also worried about using Unchecked_Deallocation with subpool types (for
instance, when you do a tree transformation and delete a node).

But I definitely agree that tasks are much less important than finalization, and
I surely can live with a "no task" edict. My concern with that has mainly been
the future (with many-core machines), but I also think it is unlikely that we
will be using raw tasks to program machines with tens of thousands of cores. So
by then, we may have a better idea of what to do.

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

From: Bob Duff
Sent: Monday, April 11, 2011  9:21 AM

> I think we could outlaw tasks (or make the behavior
> implementation-defined or a bounded error) in these things.

That's what I did in the new version of this AI, which I will send out soon.
See the AI for detailed wording.

Randy is concerned about converting existing code to use subpools.
But I really think such conversions are going to require some substantial
reprogramming anyway -- you have to analyze which objects have similar
lifetimes, and write code to put those in the same subpool(s).  You're not going
to have a million different types containing tasks -- you'll have a few, and
you'll have to treat those specially.

My intent is that after some implementations gain experience, we might decide to
relax the tasking restriction in a future version of Ada.  Restrictions can
always be relaxed -- we're not stuck forever.

In any case, I think it's a reasonable compromise -- thanks for suggesting it,
Tucker.

> What really matters is having finalization work properly.

Hristian Kirtchev and I have analyzed this, and it looks feasible for GNAT.

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

From: Bob Duff
Sent: Monday, April 11, 2011  9:28 AM

Here's a new version of AI05-0111-3, Subpools, allocators, and control of
finalization. If this needs anything more than minor fixes, I suggest we drop
the AI. [This is version /08 of the AI.]

I did lots of polishing of the wording, and adding AARM stuff, and clarifying
things that were already the intent, and fixing contradictions. Once Randy puts
it in CVS, you can see the detailed diffs.

Here's a list of the important changes:

The type of the pool (the Tag really, since it could be at run time) determines
whether to call Allocate vs. Allocate_From_Subpool, as requested by Randy. The
previous version was unclear -- in at least one place, it said it depends on the
syntax of the allocator, which Randy doesn't like.

I made sure Randy's implementation model will work (declare a primitive
Allocate_From_Subpool in the private part of the parent package). I also made
sure that the other implementation model will work.

I removed the Storage_Size parameter from Create_Subpool. For many pools, it's
not needed. This is not a restriction though -- if you want a Storage_Size, you
can have a different function, or you can use a discriminant (as the example
section does). It seems simpler for users to add this functionality if and only
if they want it.

I added a legality rule that "new (Subpool) ..." requires a subpool-supporting
subpool (statically known to be so).  Perhaps that was already the intent.

I provide concrete overridings of the inherited operations from the parent
package. This is for convenience: most concrete types won't need to override
them. For example, they can inherit an "is null" version of Deallocate.

I use "Bounded Error" for the semantics of tasks, as suggested by Tucker. This
seems like a reasonable compromise, which can be relaxed later.

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

From: Randy Brukardt
Sent: Tuesday, April 12, 2011  1:57 AM

Some reasonably minor comments on your redraft (note: I didn't make any fixes at
all other than to remove extra spaces after periods):

You changed the wording of 4.8(3/1) from:

   A *subpool_handle*_name is expected to be of any descendant of
   System.Storage_Pools.Subpools.Subpool_Handle, the type used to identify a
   subpool, defined in the language-defined package
   System.Storage_Pools.Subpools (see 13.11.4).

to

   The expected type for a *subpool_handle*_name is Subpool_Handle, the type
   used to identify a subpool, declared package System.Storage_Pools.Subpools
   (see 13.11.4).

This eliminates the possibility to derive a type from Subpool_Handle in the
package for some user-written pool type. We previously decided that this makes
using a subpool-supporting pool much easier, and thus we reworded this rule to
allow derived types. (As we all know, a subtype is not equivalent to a derived
type, as no operators come along.) Note that we did this in the example (haven't
seen if you changed that or not).

Did you do this intentionally (and if so, why - you didn't mention it
anywhere)?? Or were you just trying to reword this and lost an intended
capability?

===================

You removed "with System.Storage_Elements;" from the subpool package.

My personal style is to always include withs of packages that are actually
referenced in a child package on that package, whether or not they are withed on
the parent package. That is clearer to readers, and allows maintenance on the
parents without worrying about the children.

I don't think the Standard has a style for this particular case, so I would
prefer to have this with on the package.

===================

You changed the exception description for Set_Pool_of_Subpool from:
           -- Raises Program_Error if the Pool has already been set for Subpool
           -- since the last explicit finalization (if any) of the subpool.
to:
           -- Raises Program_Error if the Pool already belongs to a pool.

Three problems with this: first, I can't find any definition of when a subpool
"belongs" to a pool; the only use of the term in normative wording is in the
allocator check, which hardly could be a normative definition. Second, there is
nothing named Pool here; perhaps you meant Subpool??. Third, there is no other
text which says that this "belongs" state is reset when the subpool is finalized
-- that surely needs to be said normatively.

Similarly, a lot of the normative wording for Deallocate_Subpool has disappeared
(why?). Specifically: "..., and destroy the subpool. The subpool handle is set
to null after this call." Where did this go?? You added
"Unchecked_Deallocate_Subpool calls this", but surely it can be called directly,
too, and if it is the subpool still has to be set to null (at the very least,
the option has to exist should the subpool object be allocated from the heap).
My preference is for this to be a requirement on the Deallocate_Subpool
implementation (that's what I had here), as the checking for allocators depends
on this, and it is best to treat anything that violates this as erroneous.

===================

Your lengthy discussion note after the subpool package seems like too much to
put in the AARM. It looks like something that belongs in the Rationale or an Ada
textbook. It also seems to encourage dangerous usage of subpools.

Specifically,
    - Declare concrete types derived from Root_Storage_Pool_with_Subpools and
      Root_Subpool.
If you're going to talk about this here, you absolutely have to mention that the
intent is that the type derived from Root_Subpool is created in the *body* of
the package in question, and is never exposed to clients, only the handles
should exposed.

Later, application programmers (we called them "users" for Claw, and I'll do so
here because it is a lot shorter):
    - Create subpool objects by calling Create_Subpool. Alternatively, declare
      subpool objects and attach them to the pool with Set_Pool_of_Subpool.
There is no intent that users ever call Set_Pool_of_Subpool. It has to be
visible here so that the pool programmer could call it, but it should be of no
use to users. That's in part because the subpool objects should never be exposed
to users.

    - Perform finalization and memory reclamation by calling
      Unchecked_Deallocate_Subpool. Alternatively, simply let a declared
      subpool go out of scope.
I don't think the latter works. If it does, it is purely by accident (there was
no intent to allow users to declare subpool objects, they only can use handles).

Even if we *allow* users to declare subpool objects, we need to emphasize that
pool creators aren't required to allow that. This is *not* obvious!!

I saw an old message of your tonight where you claimed that "subpool_handle" was
the wrong name because a handle is supposed to be an access to a private type.
But that is *exactly* the model of a "subpool_handle" for the user of a pool
supporting subpools; the subpool objects are never supposed to be visible to the
users (clients) of the pool.

======================

The Bounded Error

I'm a bit worried about this error. You talked about relaxing the "restriction"
in the future, but I don't see how that will work. If an implementation has just
raised Program_Error for any contained tasks, there is no future problem.

But if the implementation allows the allocator, the termination semantics are
then implementation-defined. Since the same semantics as U_D are easy, I suspect
many implementations will do that. But then if we want to apply "better"
(different) semantics in the future, that would break any code that depends on
the implementation-defined semantics.

Thus, we'll never be able to change this Bounded Error in the future (unless no
one supports tasks here, which I doubt will happen, especially if my predictions
about multicore come true).

I think it would be better to do one of the following:
  (1) Mandate Program_Error when allocating any tasks; or
  (2) Mandate the termination semantics of U_D (that is, none).

In case (1), I suspect that implementations would provide a way to turn this
behavior off (extensions mode, perhaps?). But that would not cause a
compatibility problem, and we could use any termination that we want.

For case (2), I can't see how this would be a problem with GNAT, since it would
be saying that tasks use the same semantics that access types currently have.
This would prevent us from doing better sometime in the future, but I'm
skeptical that that would ever happen anyway.

I actually prefer (2), since I think that the termination problem has little to
do with subpools and everything to do with insufficient control of tasks. If we
decide to fix that in the future, we ought to do it on all task types, and not
just for subpools. (That way, all parts of the task manager can share the pain.
;-) In that case, there is no good reason to disallow tasks now - the problem is
with the definition of tasks, not the way subpools deal with them.

====================

In the discussion:

Meanwhile, the "root part" of the subpool object type will be used by the Ada
implementation to implement 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.)

Not sure what "implement and finalization" means.

===================

For some reason, you moved the "another way that subpools can be used" from the
!example into the !discussion under "use as a building block". That section is
specifically about ways to be implement pools that do automatic reclamation;
this is not so much as an example as an attempt to show that the fancier
features of AI-0111-2 are not really necessary.

In any case, the "another way that subpools can be used" has nothing to do with
using this subpools construct to build more complex memory management. I could
imagine putting both things into the !example section, but random uses of this
construct definitely do not belong in the !discussion (which is supposed to be
about technical issues with the proposal).

===================

That's it. (Enough for sure.)

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