Version 1.3 of ai05s/ai05-0111-2.txt

Unformatted version of ai05s/ai05-0111-2.txt version 1.3
Other versions for file ai05s/ai05-0111-2.txt

!standard 4.8(2) 10-05-20 AI05-0111-2/01
!standard 4.8(3/2)
!standard 4.8(10.1/3)
!standard 13.11(16/3)
!standard 13.11.4 (0)
!standard 13.11.5 (0)
!standard 13.11.6 (0)
!class Amendment 10-05-20
!status No Action (9-0-0) 10-10-29
!status work item 10-05-20
!status received 10-05-20
!priority Medium
!difficulty Hard
!subject Specifying a pool on an allocator (without reachability checks)

!summary

(See proposal.)

!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. Although it is desirable that there be protections against dangling references, and allowing storage pools of short lifetimes to be specified in an allocator for a long-lived access type clearly does not inherently provide such protection, this variant of the AI is exploring a simpler version where the user worries about the problem of dangling references.

!proposal

Allow the storage pool associated with one or more access types to be split into multiple, separately reclaimable "subpools," and allow the particular subpool to be used for a given allocator to be specified at the point of the allocator, with the following syntax:

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

Subpool "handles" are used to determine when to reclaim a subpool, by using reference counting. When the reference count drops to zero and all task objects in the subpool are terminable, the subpool will be automatically reclaimed. In addition, a subpool may be deallocated explicitly.

For any given task, a default subpool may be established for a given access type, within a given scope. An allocator without specifying a subpool explicitly for the access type will use the innermost default subpool specification for the type, if any.

DYNAMIC MASTERS

Associated with each subpool is a "dynamic master," similar to the "static" masters associated with the execution of various language constructs. The dynamic master associated with a subpool is the master for all objects residing in the subpool that need finalization. When a subpool is ready to be reclaimed, this is analogous to a static master being completed. If a subpool is reclaimed before all the tasks dependent on its associated dynamic master are terminable, Program_Error is raised.

To provide safety, automatic reclamation of a subpool is deferred until any tasks dependent on the master are terminable, as with the normal exit from a scope with a (static) master. If a subpool is explicitly deallocated, it is a bounded error if any tasks dependent on the subpool's master are not terminable. The possible effects of the bounded error are as for the unchecked deallocation of an object with a task part.

SUBPOOL REFERENCES

We define the notion of a reference-counted "handle" on a subpool. A "static subpool handle" is a counted reference to a subpool represented by a controlled immutable object declared within a static master. A "dynamic subpool handle" is an immutable, counted reference to a subpool from another subpool. Both kinds of handles, once established, remain in place until the handle is finalized, and are immutable in the sense that they always refer to the same subpool for as long as they exist. Static subpool handles are the objects used in an allocator to identify the subpool for the allocation. A dynamic subpool handle is used to ensure that access values residing in one subpool may safely designate objects in another subpool. A dynamic subpool handle is created by calling a language-defined procedure "Allow_Reference (From_Subpool, To_Subpool)," where the subpools are identified by static handles.

!wording

Modify 4.8(2) as follows:

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

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

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

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

Modify 4.8(10.1/3) as follows:

... a check is made that the accessibility level of the anonymous access type of each access discriminant is not deeper than that of the type of the allocator. {If a subpool_specification is provided, a check is made that storage pool of the type of the allocator is the subpool manager of the identified subpool.} Program_Error is raised if [either such check fails] {any of these checks fail}.

Modify 13.11(16/3):

An allocator of type T {without a subpool_specification} allocates storage from T's storage pool. If the storage pool is a user-defined object, then the storage is allocated by calling Allocate as described below. {An allocator with a subpool_specification allocates storage from the specified subpool of T's storage pool, by calling Allocate_From_Subpool as described in subclause 13.11.4.}

Add a new section:

13.11.4 Storage Subpools

This subclause defines a package to support the partitioning of a storage pool into subpools. A subpool may be specified as the default to be used for allocation from the associated storage pool, or a particular subpool may be specified as part of an allocator (see 4.8).

The following language-defined library package exists:

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

type Root_Subpool_Manager is abstract new Storage_Pools.Root_Storage_Pool with private; -- An access type must have a storage pool of a type -- descended from this type to use subpools.

type Subpool_Handle(<>) is limited private; -- This is a reference-counted handle on an underlying -- subpool descriptor (see Subpools.Implementation)

function Create_Subpool(Manager : [access]{aliased in out} Root_Subpool_Manager; Storage_Size : Storage_Elements.Storage_Count := Storage_Elements.Storage_Count'Last) return Subpool_Handle is abstract; -- Create subpool within given subpool manager. Storage_Size -- specifies a limit on the amount of storage for the subpool. -- NOTE: Additional functions that create subpools may be -- defined for a given Subpool manager type.

function Subpool_Manager(Subpool : Subpool_Handle) return access Root_Subpool_Manager'Class; -- Return access to underlying subpool manager of given handle.

procedure Allocate_From_Subpool( Manager : in out Root_Subpool_Manager; Storage_Address : out Address; Size_In_Storage_Elements : in Storage_Elements.Storage_Count; Alignment : in Storage_Elements.Storage_Count; Subpool : Subpool_Handle) is abstract with Pre'Class => Subpool_Manager(Subpool) = Manager'access; -- Allocate space from specified subpool.

procedure Allow_Reference(From : Subpool_Handle; To : Subpool_Handle) with Pre => Manager(From) = Manager(To); -- Allow pointers in "From" subpool to safely designate objects -- in "To" subpool, by ensuring that the "To" subpool is not -- reclaimed prior to reclaiming the "From" subpool.

type Default_Subpool_Specifier(<>) is limited private; -- Type used to keep track of the default subpool for a given task. function Establish_Default_Subpool(Subpool : Subpool_Handle) return Default_Subpool_Specifier; -- Set the default subpool for the current task within the -- given subpool's manager. function Default_Subpool(Manager : access Root_Subpool_Manager'Class) return Subpool_Handle; -- Return the default subpool for the current task within the -- given subpool manager. If no default subpool has been established, -- then this returns a subpool handle which identifies the -- manager's "initial" subpool. Calls on Allocate for a subpool -- manager will allocate from the default subpool for the -- calling task.

function Initial_Subpool(Manager : access Root_Subpool_Manager'Class) return Subpool_Handle; -- Return a handle on the "initial" subpool of the given subpool -- manager. The initial subpool is used when no other subpool has -- been established for a given task. The initial subpool is not -- reclaimed until the enclosing subpool manager is reclaimed.

function Is_Initial_Subpool(Subpool : Subpool_Handle) return Boolean; -- Indicates whether the given subpool is the initial subpool for -- its subpool manager.

private ... -- not specified by the language

end System.Subpools;

A subpool is a separately reclaimable portion of a storage pool, identified by an object of type Subpool_Handle (a subpool handle). A subpool handle also identifies the enclosing storage pool, called the subpool manager, which is a storage pool whose type is descended from Root_Subpool_Manager. When an allocator with a subpool_specification is evaluated, a call is made on Allocate_From_Subpool passing in the given Subpool_Handle, in addition to the parameters as defined for calls on Allocate (see 13.11).

If a subpool manager is specified as the Storage_Pool for an access type, the access type shall be a pool-specific access type. When converting an access value of such a type to a general access type, the accessibility level is that of the innermost program unit or declare block enclosing the conversion.

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

When a task creates an object of the type Default_Subpool_Specifier by calling Establish_Default_Subpool, the specified Subpool becomes the default subpool for the subpool's manager, for the given task. When an allocator without a subpool_specification is evaluated and the storage pool is a subpool manager, the default subpool for that task is used. If no default has been established for a given task, the initial subpool of the subpool manager is used. Finalizing an object of type Defaut_Subpool_Specifier restores the default subpool for the given task and subpool manager to its state immediately prior to the creation of the object.

[Bounded Error: creating an object of type Establish_Default_Subpool with an allocator.]

[Redundant: There is a master associated with the execution of certain constructs (see 7.6.1),] called a construct master. In addition, each subpool has its own unique master, called the master for the subpool, which is used for the objects allocated from the subpool.

When an object is created by an allocator and the object is allocated from a subpool, then the master of the allocated object (and of any parts that are task objects) is the master for the subpool, rather than that of the access type's collection. When a subpool is *ready to be finalized* (see below), its finalization proceeds by completing any tasks dependent on the subpool's master that are waiting at an open terminate alternative, waiting for their termination, and then finalizing any of the objects allocated from the subpool that still exist. After a subpool has been finalized, any storage allocated for objects in the subpool can be reclaimed.

The type Subpool_Handle needs finalization.

13.11.5 Subpool Reclamation

The following language-defined library procedure exists:

procedure System.Subpools.Unchecked_Deallocate_Subpool

(Subpool : in out Subpool_Handle);

Subpools are automatically finalized and reclaimed when there are no further handles designating them. In addition, a subpool may be explicitly deallocated using Unchecked_Deallocate_Subpool.

[Redundant: The master of an object is the innermost (construct) master that included the elaboration of the object, for an object that is part of a declared object. The master of an object that is part of an object created by an allocator is the master for the subpool if it is allocated from a subpool; otherwise it is the (construct) master of the ultimate ancestor of the type of the allocator.]

If a subpool is not reachable from any construct master, any strong references, nor any master for a subpool with one or more nonterminable tasks that depend on it, the given subpool is ready to be finalized.

When Unchecked_Deallocate_Subpool is called with a given subpool handle, a check is made that it is the only remaining handle on the subpool. If not, Program_Error is raised. It is a bounded error if nonterminable tasks depend on the master of the subpool being deallocated. The possible effects are as given for the unchecked deallocation of an object with a task part (see 13.11.2).

13.11.6 Subpool Descriptors

The following language-defined package exists:

package System.Subpools.Descriptors is -- This package is used to support the implementation of a subpool manager.

-- A call on Create_Subpool goes to the subpool manager, -- which allocates a subpool descriptor, and -- then calls New_Subpool_Handle to create a handle.

-- When a subpool is ready to be reclaimed, the Ada implementation -- waits for any tasks, finalizes the objects in the subpool, then -- calls Reclaim_Subpool_Storage. Finally, it calls Deallocate -- with the address of the subpool descriptor.

type Root_Subpool_Descriptor( Manager : not null access Root_Subpool_Manager'Class) is abstract tagged limited private; -- This type is used to represent a storage pool within a subpool manager. -- The Ada implementation uses this to represent the master for the subpool. -- It holds the reference count of handles. -- The subpool manager also uses some extension of this type to keep -- track of the actual storage associated with the subpool so it -- may be reclaimed.

procedure Reclaim_Subpool_Storage(Subpool : access Root_Subpool_Descriptor) is abstract; -- This is called by the Ada implementation when the subpool is no longer -- reachable from any non-terminable task.

function New_Subpool_Handle( Subpool : access Root_Subpool_Descriptor'Class) return Subpool_Handle; -- Create a subpool handle given a descriptor of the subpool

end System.Subpools.Descriptors;

Subpools are represented internally by objects of a type descended from Root_Subpool_Descriptor, which are allocated from the initial subpool of the subpool manager. The abstract operations on Root_Subpool_Manager and Root_Subpool_Descriptor are not provided by the Ada implementation. All other operations within System.Subpools and System.Subpools.Descriptors are provided by the Ada implementation, for use in implementing overridings of the abstract operations.

!discussion

There is a delicate "dance" here between code provided by the Ada implementation and code provided by the implementor of the subpool manager type. The Ada implementation is responsible for worrying about reference counting, task dependence, finalization chains, reachability checks, weak references. Essentially everything having to do with avoiding dangling references. The implementor of the subpool manager type is supposed to worry about actually managing the storage and keeping track of which storage has been allocated to which subpools. The subpool descriptor type can also be extended. So the implementor of the subpool manager can keep some information in a per-subpool data structure (by extending Root_Subpool_Descriptor), and some globally for the overall storage pool (by extending Root_Subpool_Manager).

Meanwhile, the "root part" of these two types will be used by the Ada implementation to implement its part of the equation, such as finalization, reachability checking, etc.

COMPILE-TIME CHECKING

It is the intent that many of these checks can be performed at compile-time. This is enabled by the transitive nature of the "reachability" relationship. For example, if a function returns an access value and the return statement is not "inside" some local master having a static handle on some subpool, then no reachability check is necessary as part of the return. This is because, whatever is the designated subpool, the master immediately enclosing the call must be able to reach it, since only the presence of a static subpool handle can cause a nested master to reach more than its enclosing master. This property ensures that most access value manipulations need no checks.

It is only if an assignment or function return is "crossing" a master having a static subpool handle that any check need be performed. Furthermore, if the compiler can trace the origin of the access value to a point outside any handle being "crossed," then again, no check is required. For example, if the access value came from a formal parameter, perhaps after following various intermediate indirections, it is always safe to return it, even if the function did have local masters with static subpool handles.

Note that this means that existing Ada code that takes an access value, and follows one or more levels of indirection to retrieve another access value, and then returns it, could be used as is with no additional run-time checks required, since clearly existing code has no explicit use of subpool handles.

RUN-TIME CHECKING

Despite the goal of making most of these checks be performable at compile time, some run-time checking may be necessary. To enable such checks to be performed at run-time, the implementation of a storage pool with subpools must provide an operation "Originating_Subpool (Storage_Pool, Address)" that, given an address returned from "Allocate" from one of its subpools, will return a static handle on the subpool. This might be implemented by storing a reference to the subpool immediately preceding each object allocated from the subpool, or by using separate memory pages for separate subpools, and having a reference to the associated subpool at the start of each page, or by a combination of techniques. An attribute_function, perhaps <access_type>'Subpool(acc_val), might be applicable to a non-null access value of the type, and be equivalent to calling the appropriate Originating_Subpool function on acc_val.all'Address.

Once the designated subpool of a given access value is determined, the required check can be performed. Note that although the implementor of the storage pool is required to provide the Originating_Subpool operation, it is the underlying Ada implementation that actually maintains the reference counts associated with subpool handles and strong references, and the structures associated with weak references. It also performs whatever run-time checks are required. One way to think about it is that the Ada implemention worries about the masters, while the user code can take over allocation from and reclamation of the subpools.

PERFORMANCE

To make run-time checks efficient, the Ada implementation may create auxiliary data structures and do additional computing as part of creating new dynamic subpool handles in response to Allow_Reference calls. The intent is that many checks can be done using a simple comparison based on an analogue of the static accessibility levels, and only if the simple check fails would a more complex check be necessary. For example, because subpool handles are immutable, once two subpools can reach each other directly or indirectly, they can effectively be treated as a single combined subpool from the point of view of lifetime. That is, neither can be reclaimed until both can be. Using an algorithm such as Tarjan's "union find" algorithm, subpools participating in cyclic dependencies can be combined efficiently, with any one of them acting as the representative of them all. What this means is that an arbitrary directed graph of dependencies between subpools can be reduced to a forest of strict trees between subpool "combines," simplifying the job of relative lifetime determination.

For weak references, we would recommend using an intermediate structure that lives as long as there is any weak reference to a given subpool, even after the subpool itself is finalized. This intermediate structure would have a count of weak references to the subpool, and the subpool and this intermediate structure would have pointers to one another. When the first weak reference to a subpool is created, this intermediate structure could be allocated out of the "main" subpool. It would be released back to the main subpool when the last weak reference was finalized. When the target subpool was finalized, the intermediate structure would be marked so that any future conversions of a weak reference to a strong reference would result in null.

DEFAULT SUBPOOL

In the absence of an explicit subpool specified on an allocator for an access type with subpools, which subpool should be used? The "original" one (i.e. access_type'Storage_Pool). We would recommend allowing a static subpool handle to be marked as a "default allocation handle," and then the innermost such handle associated with the storage pool of the access type would be used. This latter approach would be more flexible, and allow existing code to be used without having to annotate existing allocators with explicit subpools. On the other hand, it can create possibilities for confusion, since the identification of the handle might be far removed from the actual allocator. Another alternative is to base the subpool on the target of the allocator, if it is being stored directly into a component of a subpool-resident object.

The other major advantage of defining a notion of "default subpool" is that implementations could provide a subpool capability without extending the syntax of the language.

SUMMARY

Reference-Counted Region-Based Storage Management

* Pointers into regions are protected by Handles on regions, which are reference-counted.

* Static handles protect pointers on the stack.

* Dynamic handles protect pointers from region to region.

* Static and dynamic handles are immutable -- once created they remain

pointing at the same region as long as they exist

=> Need not ref-count/track individual pointers.

* Regions exist while handles on them exist. Pointers into region

only possible while handles exist.

=> No dangling references.

* Allocator takes static handle and returns pointer into region:

P := new (Region_Handle) T'(Initial_Value);

Strong and Weak References

* Strong reference combines mutable ref-counted handle with a private pointer into a region

- Pointer only usable by splitting strong reference into static handle and visible pointer.

* Weak reference combines managed handle with private nullable pointer

- Usable by converting to strong pointer and then splitting into handle and visible pointer.

- Private pointer nulled-out automatically when region reclaimed.

* Strong reference stored in another region to commit work.

* Weak reference can be used for revocable cache; preserves

zero-ref-count region while space is "plentiful".

A Day in the Life of a Region and its Objects

Create Region:

Static_Handle <- Create_Region(Region_Size)

Allow_Reference (create Dynamic handle):

Allow_Reference(From_Region_Handle, To_Region_Handle)

Allocator: Pointer <- new (Static_Handle) T�(Initial_Value)

Assign: Pointer [protected by Outer Handle] <- Pointer

exit scope of Static_Handle:

Region.Ref_Count <- Region.Ref_Count - 1 if Region.Ref_Count = 0 then if Region.Has_Weak_Refs then Add_To_Reclaimable_List(Region) else Destroy(Region)

!example

{Show a real example.}

As an example of the use of subpools, imagine a long-running web server for a retail establishment, which builds up in-memory representations of historical customer information, current product information, and each active customer's current shopping cart. There is a desire to be able to reclaim this in-memory information when it has not been recently referenced. However, the various representations are interlinked, such that a shopping cart refers to the in-memory representation for the products it contains, and the historical customer information and the current shopping cart might refer to each other.

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

Weak object references could be used in a table indexed by customer name or product name. Before retrieving information from the persistent database, a check would be made in the table to see if there is a weak reference, and whether upon converting into a strong reference it is non-null. If so, then the existing in-memory information can be reused.

If it is null, then the information must be retrieved from the

persistent database, and the appropriate in-memory data structures created, again depositing a weak reference in the table for future reference. Meanwhile strong references would be kept in the web server's table of active sessions, so the information in use by an active session would not be prematurely reclaimed. Finally there would be appropriate dynamic subpool handles or strong object refernces between the subpools representing related shopping carts, customers, and products, ensuring that, for example, as long as a shopping cart remained active the associated customer history record remained active.

Whenever a subprogram would actually need to "walk" through an in-memory data structure, a strong object reference, presumably to the "root" node of the designated data structure, would be converted into a static subpool handle and an access value to the root node. The static subpool handle would reside in a local master, protecting all local use of the access value, and anything reachable from the access value, until the local master was completed and the static subpool handle was finalized.

To avoid reclaiming subpools as soon as the last reference from an active session went away, since the information might be needed again relatively soon, a separate caching task could keep strong references in a list, ordered by recency of use. When the storage pool implementation detects that the total space occupied by all of its subpools exceeds some threshhold, it could request that the caching task start discarding strong references to the least recently used subpools. This presumes the application would notify the caching task on each "significant" use of the subpool, so the recency of significant use could be determined.

Alternatively, as we suggested above at the end of the section on "SUBPOOL REFERENCES," the implementation could automatically defer reclaiming subpools with outstanding weak references, as long as free memory is "plentiful." This would eliminate the need for each application to have its own "caching" task to accomplish the same goal.

!ACATS test

Create ACATS C-Tests to test this facility.

!appendix


From: Bob Duff
Sent: Monday, May 17, 2010  2:55 PM

Here's my last bit of homework, in preparation for the phone meeting this
Thurday, May 20, at 3:00 PM EST.

This is from the Minutes of Meeting #40:

> Action item to everyone to look at this and see how (or if) they might
> use it.

OK, I've studied this stuff some more.

If it existed, I would certainly use it sometimes.
I'd use it whenever large numbers of objects can be grouped into those with
similar lifetimes.  E.g. a giant hash table, where all the nodes go away when
the hash table does.

In fact, I've built the same sort of stuff myself, except without language
support, it necessarily had some drawbacks:

(1) Unsafe (possible dangling pointers), because there was no
    check that when you copy an access value, the right subpool
    is "reachable".

(2) Unreadable, because there was no syntax for specifying the
    subpool on the "new".  Instead, I had a global "current subpool"
    variable, which had to be set up beforehand.  (Actually, a
    stack of them, with limited-controlled types managing the
    setup and teardown -- quite complicated.)

(3) Task-unsafe, because of that global variable.

(4) No support for allocating controlled objects or tasks
    within a subpool (if you try, the runtime system gets
    deeply confused).

(5) It was technically wrong (relied on implementation-specific
    behavior not guaranteed by the language).

I would be pretty happy with a solution that solved just (2) and (3), which
seems pretty easy (see the title of this AI!).  In the past, this suggestion has
been shot down, saying "we can't have a new way of creating erroneous behavior"
(i.e. (1) above).  I have never understood that argument.  If a new feature is
unsafe, you have to look at what it replaces.  Unsafe subpools would replace
some uses of Unchecked_Dealloc.  Unsafe subpools are unsafe, but they're still
safer than Unchecked_Dealloc -- by far, in my experience.  So unsafe subpools
would make Ada programs safer, on the whole.

Support for unsafe subpools exists in C and C++, which is our competition if
you're looking at the embedded world.  If a C++ programmer says "Ada can't do
X", we can usually answer, "Oh, yes it can, you just have to do it in a more
disciplined, safer way."  That's fine. But in this case, our current answer is,
"Right, you can't do that in Ada, and we're not going to let you, because it's
unsafe." That's not an acceptable answer to someone who needs to do X.

Given the widespread use of unsafe subpools (AKA user-defined malloc, placement
new, etc) in C and C++, I find the question posed in the minutes "see... if...
they might use it" to be rather puzzling.

Safe subpools, as proposed by this AI, prevent (1), which is very cool.
On the other hand, there's a fair amount of implementation complexity for that.

I can't get too excited about (4).  From a practical point of view, I'd be happy
if allocating such "fancy" things raised an exception.  That's ugly of course --
but that's a more theoretical point of view.  There's a huge implementation
complexity in solving (4).

I believe that a modern, efficient implementation of garbage collection would do
far more to promote the use of Ada than this AI.  The !example, of a
"long-running web server" seems appropriate for GC -- no hard real-time
constraints, not safety critical, etc.  On the other hand, the implementation
cost of this AI is far less than that of a really good GC.

Summary: I have mixed feelings.  :-(

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

From: Bob Duff
Sent: Monday, May 17, 2010  3:11 PM

> Action item to everyone to look at this and see how (or if) they might
> use it.

Anecdote: Last weekend, I was helping my son Bill who is writing an Ada program
to do some text processing, involving reading (arbitrarily long) lines of text
from input files, and grinding upon them in various ways.  This required fairly
complicated data structures containing Strings and other stuff.

Subpools (safe or unsafe) containing Strings would have come in very handy.
We ended up using Unbounded_Strings, which works, but it's awfully heavy
syntactically.  You end up either converting back and forth between String and
Unbounded_String all over, or using calls to Element, Replace_Element, and the
like instead of normal array indexing and the like.  A loop such as:

    loop
        create subpool;
        process one file, doing "new String..." a lot;
        destroy subpool;
    end loop;

would have made the code rather more readable, I think.
And it's not too hard to make sure the subpool is destroyed at the right time to
avoid dangling pointers.

GC would have been another good solution.

I suspect any of the three (safe subpools, unsafe subpools, or GC) would have
been more efficient than all that string copying we ended up doing.   (E.g. what
do you do when you want to rename a slice of an Unbounded_String?!)

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

From: Bob Duff
Sent: Monday, May 17, 2010  3:18 PM

> Anecdote: Last weekend, I was helping my son Bill who is writing

For a good time, google "the plural of anecdote is data".  ;-)

Anybody else going to do this homework?...

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

From: Randy Brukardt
Sent: Monday, May 17, 2010  8:37 PM

> We ended up using Unbounded_Strings, which works, but it's awfully
> heavy syntactically.  You end up either converting back and forth
> between String and Unbounded_String all over, or using calls to
> Element, Replace_Element, and the like instead of normal array
> indexing and the like.  A loop such as:

That's a problem with unbounded strings that doesn't seem to have much to do
with subpools. Unbounded_Strings shouldn't be so clunky, period. Unfortunately,
fixing that would take a fairly massive redesign, and would be incompatible in
some corner cases.

Tucker's indexing syntax might help with this as well. (We ought to consider
defining it for bounded and unbounded strings.)

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

From: Randy Brukardt
Sent: Monday, May 17, 2010  8:48 PM

> Given the widespread use of unsafe subpools (AKA user-defined malloc,
> placement new, etc) in C and C++, I find the question posed in the
> minutes "see... if... they might use it" to be rather puzzling.

I totally agree with this logic. I don't actually see the point of "safe
subpools"; they're a lot of work to fix something that isn't (seriously) broken.

> Safe subpools, as proposed by this AI, prevent (1), which is very
> cool.
> On the other hand, there's a fair amount of implementation complexity
> for that.
>
> I can't get too excited about (4).  From a practical point of view,
> I'd be happy if allocating such "fancy" things raised an exception.
> That's ugly of course -- but that's a more theoretical point of view.
> There's a huge implementation complexity in solving (4).

Here I disagree with you, on both points. If we had simple unsafe subpools, it
makes perfect sense for the allocated objects to be associated with the subpool,
and thus go away when the subpool does. That's simple to implement in that it
works the same way as it does for declared access types, just associated with a
different object. The only problem that might come up is if the implementation
cannot handle a dynamically determined object for the "master" of an allocated
object. That shouldn't be the case for a chain-based implementation (only the
root of the chain needs to be identified, and that can be treated as a normal
object [an address]). An implementation that does things statically might have
more trouble, but I can't figure out how a static implementation would even work
for allocated objects - it seems like there would have to be a list somewhere.

> I believe that a modern, efficient implementation of garbage
> collection would do far more to promote the use of Ada than this AI.
> The !example, of a "long-running web server" seems appropriate for GC
> -- no hard real-time constraints, not safety critical, etc.  On the
> other hand, the implementation cost of this AI is far less than that
> of a really good GC.
>
> Summary: I have mixed feelings.  :-(

Mine aren't mixed. Tucker's current proposal is too much. Solving (2), (3), and
(4) is relatively easy and might be worthwhile, but I see no reason to go beyond
that. And I'd rather do nothing than make a large implementation burden for a
relatively rare use. (Remember that we've made it quite a bit easier to create a
container that can handle all of this stuff at a higher level; that doesn't
solve every problem but it solves a whole lot of them.)

I had seriously considered writing an alternative AI that did just (2), (3), and
(4), but I decided to go on vacation instead. Now I don't have time... ;-)

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

From: Tucker Taft
Sent: Tuesday, May 18, 2010  9:07 PM

One thing worth noting in the update
to AI05-0111, is that there are no
compile-time checks required to support
the "reachability" requirements.
My guess is that this simplifies
the implementation significantly,
since it can be offloaded almost
entirely to the run-time system,
which is almost always easier
to update and debug than the compiler.

Also, the reachability checks are
now described in just a handful of
paragraphs, in 13.11.6, and are
hopefully easier to understand than before.

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

From: Tucker Taft
Sent: Friday, May 21, 2010  12:52 AM

Here is a simplified version of AI05-0111, now labeled as variant 2, which is
very similar to variant 1, except that there are no reachability checks, no
strong references, and no weak references.

The discussion has *not* been updated.  There may be some remaining vestiges of
references or reachability checks in the !wording.  Feel free to point those
out.

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

From: Steve Baird
Sent: Monday, June  7, 2010  7:02 PM

> . Report on possible uses of AI05-0111-1.
>

I think that this is an important AI.

Rational felt the need to invent a mechanism for this kind of storage management
many years ago. This was done via the implementation-defined pragmas
Segmented_Heap and Heap.

The details of the pragmas are unimportant for today's discussion. My point is
that there were a relatively small number of omissions in Ada83 that were viewed
as being so severe as to require an implementation-specific solution and all but
one of these holes have been addressed (e.g., by the introduction of tagged
types, or of unknown discriminants).

It seems odd that this one wasn't taken care of a long time ago, but we should
certainly do something about it now.

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

From: Jean-Pierre Rosen
Sent: Wednesday, June  9, 2010  12:15 AM

Although I understand the possible uses of subpools, I, personnally, me, myself, never felt the need for such a feature.

TBH, there are still some things that I didn't get.
1) there is still a (hum) reference to strong references
2) why is it necessary to have two concepts: subpool handle and subpool manager?
   Apparently, the handle is used mainly in the allocator. Why not pass the
   manager?
3) The AI mentions often reference counting, but not how it works. What happens
   when an access value of a subpool is assigned?
4) I didn't understand what subpool descriptors are for

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

From: Tucker Taft
Sent: Wednesday, June  9, 2010  7:47 AM

> TBH, there are still some things that I didn't get.
> 1) there is still a (hum) reference to strong references

Thanks, I'll search for that (or you can tell me where you saw it).

> 2) why is it necessary to have two concepts: subpool handle and
> subpool manager? Apparently, the handle is used mainly in the
> allocator. Why not pass the manager?

There is one subpool manager, and many subpools.  The subpool manager is the
storage pool associated with the access type as a whole, while it is the
separate subpools which are separately reclaimable.

> 3) The AI mentions often reference counting, but not how it works.
> What happens when an access value of a subpool is assigned?

Subpool handles are effectively reference-counted pointers to subpool
descriptors.  Subpool handles would be controlled types, and creating or
finalizing one would correspondingly increment or decrement the reference count
on the designated subpool descriptor.

> 4) I didn't understand what subpool descriptors are for

They are the objects that are designated by subpool handles.  They would contain
the reference count, which would be incremented and decremented when subpool
handles are created/finalized.

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

From: Randy Brukardt
Sent: Thursday, June 10, 2010  1:56 AM

> > 4) I didn't understand what subpool descriptors are for
>
> They are the objects that are designated by subpool handles.
> They would contain the reference count, which would be incremented and
> decremented when subpool handles are created/finalized.

I think this model is still more complex than necessary; there seems like a lot
going on still that isn't related to the issues that the language has to manage.
I wish I had time to try to come up with the ultra-simple version; maybe after I
get to Spain. (I spent more than a day trying to set up my new laptop, which I
managed to brick by using the automated update process. Had to reload the
factory install several times -- a massive waste of time.)

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

From: John Barnes
Sent: Thursday, June 10, 2010  1:46 AM

Those answers to Jean-Pierre are really valuable. They really must be part of
the discussion in the AI and maybe briefly in the AARM..

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

From: Brad Moore
Sent: Thursday, June 10, 2010  11:36 AM

I am thinking about where the subpool idea could have been applied in systems I
have been involved in the past.

Part of the system I was involved with included a distributed network of nodes.
These nodes were embedded firmware devices, and one of the development
constraints for that platform was the desire to ensure as best as possible to
eliminate dynamic heap allocation, since memory was limited, there was a desire
to avoid memory leaks. The system was written in Ada 83, but the idea of storage
pools was used to allocate buffers from static pools. There were several pools,
mostly based on the size of allocation. One of the areas of use for these
subpools involved in messaging between nodes. An abstraction of a message
exchange was created. Objects would get created as needed to support a messaging
exchange, and typically objects could not be freed until after the exchange was
terminated. The memory deallocation was error prone, and required careful
attention to avoid memory leaks.

I think the subpool idea would have been very helpful here if this were
available back then when the system was built.

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

From: Tucker Taft
Sent: Thursday, June 10, 2010  8:25 AM

> ...
> I think this model is still more complex than necessary; there seems
> like a lot going on still that isn't related to the issues that the
> language has to manage.

Having a reference-counted handle that designates a subpool descriptor could be seen as unnecessary complexity, when the subpool descriptor could be potentially declared directly as a local variable.  However, a common paradigm in my experience is that you
 build up a data structure in a local scope, and then depending on the kind of the data structure, or on the success of the construction, you either want to discard it on leaving the scope, or hook it into a longer-lived data structure.

This is similar to a database transaction, where you can either abort/rollback, or commit the transaction.
By inserting a level of indirection, namely the handle, we allow for the subpool to outlive the scope in which it is first created and largely filled in.  The basic idea is that immediately prior to leaving the scope, if the subpool is to remain in existen
ce, then you call "Allow_Reference" hooking it into some outer subpool.
If it is to go away, then by simply exiting the scope the local handle is the last reference, and so the subpool is reclaimed.

In a compiler-like environment, the outer subpool might represent the overall program library, while the inner subpool might represent a local unit, where if it turns out to be a generic body (presuming you are using macro expansion) or a package body cont
aining some inlinable subprograms, you would want to hold onto the subpool, but if it is a normal subprogram body (with a separate spec! ;-), you could discard the subpool once it has been processed.

So I believe the level of indirection, and the ability to connect the subpools together, is important functionality.

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

From: Randy Brukardt
Sent: Thursday, June 10, 2010  2:24 PM

...
> Having a reference-counted handle that designates a subpool descriptor
> could be seen as unnecessary complexity, when the subpool descriptor
> could be potentially declared directly as a local variable.  However,
> a common paradigm in my experience is that you build up a data
> structure in a local scope, and then depending on the kind of the data
> structure, or on the success of the construction, you either want to
> discard it on leaving the scope, or hook it into a longer-lived data
> structure.

I suspect the we have totally different models of how these things would be
used, and that is coloring the design choices. I want them to be as simple as
possible in order for them to have maximum flexibility to the programmer that is
creating the abstraction. I view them as a very basic building block that is
combined with other Ada features to create useful abstractions. I would not ever
expect them to be used without some sort of wrapper. You seem to be expecting
this to provide the complex useful abstraction directly -- which I find limiting
because it forces a lot of potentially useless overhead and complexity on the
creator of the abstraction.

For instance, I have been imagining an unbounded container implementation where
each container included a subpool object. All of the allocations for the
container would be done out of that subpool. Then, the container finalize
becomes simply the discarding of the subpool, automatically freeing all of the
contained memory. (I'm being purposely vague on how the subpool is actually
implemented, as it isn't relevant to the usage model.) For this sort of use, I
wouldn't expect any connections between subpools.

More generally, you are allocating abstractions, not subpools. It makes sense to
think of each complex abstraction as having its own subpool. If another
abstraction needs to be linked to the original one to make them treated as one,
that is something that the abstraction should handle. I can imagine subpools
being created with that capability, but I don't see any good reason for it to be
automatic.

To use your example:
"In a compiler-like environment, the outer subpool might represent the
overall program library, while the inner subpool might represent a local
unit, where if it turns out to be a generic body (presuming you are using macro
expansion) or a package body containing some inlinable subprograms, you would
want to hold onto the subpool, but if it is a normal subprogram body (with a
separate spec! ;-), you could discard the subpool once it has been processed."

To me, this is a capability that the user-written subpool should have if needed.
The subpools would belong to the "unit" abstraction (be part of the header for
that). If the unit is to be discarded, it's deallocated. If it is to be linked
permanently in the program library, the unit subpool is passed to the subpool
for the library with the request to add it to that subpool for the purposes of
deallocation. It seems straightforward enough, and doesn't require any language
support or complex "handle" schemes.

(I'll ignore the fact that when we tried this sort of unit deallocation in
Janus/Ada we ended up with madness - we never got it to work reliably and gave
it up completely when we move to MS-DOS with the *huge* 256K of memory. Not
relevant, I hope.)

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

From: Tucker Taft
Sent: Thursday, June 10, 2010  3:00 PM

> More generally, you are allocating abstractions, not subpools. It
> makes sense to think of each complex abstraction as having its own
> subpool. If another abstraction needs to be linked to the original one
> to make them treated as one, that is something that the abstraction
> should handle. I can imagine subpools being created with that
> capability, but I don't see any good reason for it to be automatic....

I don't think our models are actually that different.
I am simply anticipating (based on experience) a need to create connections
between subpools.  You would rather defer that to the user.  But in my
experience, if you make the subpools themselves local objects you are stuck,
whereas if you make the local objects merely reference-counted "handles" on the
subpools, then you have the kind of flexibility you desire.  And making the
subpools a local object is a bit bogus anyway, because of course the actual
storage will be coming out of some kind of heap, so you really don't have the
subpool "sitting" on the stack.  Instead you have some kind of subpool "header"
object, with all of the storage off in perhaps a linked list of chunks.

So I believe pretty strongly that a reference-counted handle is important to
have the flexibility we want.  Other than that, I think we are arguing about
relatively minor details of presentation more than significant issues of
substance.

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

From: Randy Brukardt
Sent: Thursday, June 10, 2010  4:47 PM

...
> I don't think our models are actually that different.
> I am simply anticipating (based on experience) a need to create
> connections between subpools.  You would rather defer that to the
> user.  But in my experience, if you make the subpools themselves local
> objects you are stuck, whereas if you make the local objects merely
> reference-counted "handles"
> on the subpools, then you have the kind of flexibility you desire.

Sure, but you are setting up a straw man here. I'm expecting that the subpool
objects will be components in the header of the abstraction (for a container,
that's the container object). That header is storage-managed by the user of the
abstraction; the subpool takes care of managing the contents of the abstraction.
You never want to assume how the user of the abstraction is going to allocate
it; you need to given them maximum flexibility by assuming nothing so that they
can put the abstraction into a container, a local object, or a dynamically
allocated object (including in some other subpool).

In some cases (such as your program library example), that "header" doesn't
really exist, it's just a global variable somewhere. But there is clearly no
problem with that.

The one place that you would almost never put a subpool is as a local object.
Like everything, it has to be managed, and unless you are certain its lifetime
is only local (and I suppose that could happen occassionally), you shouldn't
declare it there. Anything else would be massively confusing. (We were very
careful to follow this model in Claw; if you declare a window object locally,
the window goes away when the routine is exited. If you need it to hang around
you need to declare the object somewhere else.)

> And making the subpools a local object is a bit bogus anyway, because
> of course the actual storage will be coming out of some kind of heap,
> so you really don't have the subpool "sitting" on the stack.  Instead
> you have some kind of subpool "header" object, with all of the storage
> off in perhaps a linked list of chunks.

Right, but that seems irrelevant to the question at hand. The implementor of the
subpool can define it anyway they want, and I don't think we should get in the
way.

> So I believe pretty strongly that a reference-counted handle is
> important to have the flexibility we want.  Other than that, I think
> we are arguing about relatively minor details of presentation more
> than significant issues of substance.

There are no other objects in the standard Ada library which are required to be
implemented by reference-counted handles. Why is this one different? You
allocate subpools whereever makes sense to get the lifetime you need, just like
any other Ada object. You don't expect some magic to change the lifetime for
you. The effect is that allocating local subpools that are supposed to live much
longer than that will be very confusing to causal Ada readers (and even to some
experienced ones).

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

From: Steve Baird
Sent: Thursday, June 10, 2010  3:42 PM

> I don't think our models are actually that different.
> I am simply anticipating (based on experience) a need to create
> connections between subpools.

I tend to agree with you, but I'm interested in your thoughts about thread
safety.

Hopefully Allow_Reference and related operations work correctly in the face of
unsynchronized/concurrent calls. (although I didn't see this mentioned
explicitly in the !wording).

Providing a predefined mechanism which is no better than a simple "Adjust
increments; Finalize decrements and checks for zero" implementation of reference
counting would (I think) be a mistake. Better no predefined mechanism at all
than an unsafe one.

On the other hand, this might introduce unwanted overhead in the case where
thread safety is not an issue.

If this argument has any weight (and it is not clear that it does), then this
would argue for Randy's leave-it-up-to-the-user approach.

What do you think?

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

From: Tucker Taft
Sent: Thursday, June 10, 2010  4:27 PM

>> I don't think our models are actually that different.
>> I am simply anticipating (based on experience) a need to create
>> connections between subpools.
>
> I tend to agree with you, but I'm interested in your thoughts about
> thread safety.

Language-defined packages are required
to be thread-safe (per RM A(3/2)), at least to some degree, so I presume this
one would be as well.  If we need to say more because of the limitations of
A(3/2), then we should.

You could always provide specialized non-thread-safe versions.  But
Allow_Reference is not called frequently, so there would be little if any reason
not to make that thread safe.  The actual allocator is ultimately calling
user-provided code, so they can be as thread safe as they feel necessary. The
language implementation generally only gets involved on whole-subpool
operations, and those are pretty infrequent.  The user code handles the
individual allocations and deallocations.

> Hopefully Allow_Reference and related operations work correctly in the
> face of unsynchronized/concurrent calls.
> (although I didn't see this mentioned explicitly in the !wording).
>
> Providing a predefined mechanism which is no better than a simple
> "Adjust increments; Finalize decrements and checks for zero"
> implementation of reference counting would (I think) be a mistake.
> Better no predefined mechanism at all than an unsafe one.
>
> On the other hand, this might introduce unwanted overhead in the case
> where thread safety is not an issue.

Doesn't seem too significant, given the relative rareness of this operation
compared to individual allocations and deallocations.

> If this argument has any weight (and it is not clear that it does),
> then this would argue for Randy's leave-it-up-to-the-user approach.

I'm not sure I agree.  Presuming it is thread safe, then this might be a good
reason to build in the reference counting capability, given how often the
average user gets these things wrong (again, based on personal experience...
;-).  And I believe reference counting is just one reason why it is useful to
build in the level of indirection.

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

From: Steve Baird
Sent: Thursday, June 10, 2010  5:25 PM

> Language-defined packages are required to be thread-safe (per RM
> A(3/2)), at least to some degree, so I presume this one would be as
> well.  If we need to say more because of the limitations of A(3/2),
> then we should.

I think additional wording is needed because of the "nonoverlapping objects"
clause in A(3/2).

>
> Doesn't seem too significant, given the relative rareness of this
> operation compared to individual allocations and deallocations.
>

Agreed.

>> If this argument has any weight (and it is not clear that
>> it does), then this would argue for Randy's
>> leave-it-up-to-the-user approach.
>
> I'm not sure I agree.

I understand what you're saying, but I think we do
agree on the main point.

You've made a good case that "if the performance argument
has any weight" is equivalent to "if false".

I'm sure we would both agree on most any
assertion that begins with "if false".

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

From: Tucker Taft
Sent: Thursday, June 10, 2010  5:27 PM

>...
>> So I believe pretty strongly that a reference-counted handle is
>> important to have the flexibility we want.  Other than that, I think
>> we are arguing about relatively minor details of presentation more
>> than significant issues of substance.
>
> There are no other objects in the standard Ada library which are
> required to be implemented by reference-counted handles. Why is this
> one different? You allocate subpools whereever makes sense to get the
> lifetime you need, just like any other Ada object. You don't expect
> some magic to change the lifetime for you. The effect is that
> allocating local subpools that are supposed to live much longer than
> that will be very confusing to causal Ada readers (and even to some
> experienced ones).

I guess I don't see it quite this way (surprise, surprise).
The thing that is new is that we are allowing subpools of a storage pool to be
reclaimed before the storage pool as a whole goes away.  We are also making each
of these things into masters, so they do the right thing with tasking and
finalization.  Clearly the implementation will be doing part of the work
(relating to tasking and finalization) and the user code the other part (storage
allocation/deallocation).  We don't really want the user code forcing stack
allocation of data structures having to do with finalization and task waiting.
So we use handles which creates a level of indirection, and allows the data
structures to survive as long as the implementation needs them, even if the
actual user can no longer do explicit allocations or deallocations.

Note that the language already does something pretty similar with task objects,
where those are really handles on underlying tasks.

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

From: Randy Brukardt
Sent: Thursday, June 10, 2010  5:47 PM

> I guess I don't see it quite this way (surprise, surprise).
> The thing that is new is that we are allowing subpools of a storage
> pool to be reclaimed before the storage pool as a whole goes away.  We
> are also making each of these things into masters, so they do the
> right thing with tasking and finalization.  Clearly the implementation
> will be doing part of the work (relating to tasking and
> finalization) and the user code the other part (storage
> allocation/deallocation).  We don't really want the user code forcing
> stack allocation of data structures having to do with finalization and
> task waiting.

Why not? Or, more accurately, why would it matter where those things are
allocated? They're logically on the stack now (each stack frame having a set),
and the compiler can do whatever they want with them. I don't see how having a
subpool object declaration locally is any different than having an access type
declaration locally or a regular storage pool declaration locally (both of which
are fully supported in Ada 95).

For the record, Janus/Ada declares the root of these things at the point that
they're needed (which can be locally). (Each of these things is a chain head,
the entities on the chain might live elsewhere, of course.) I again don't see
anything new here, *until* you start requiring indirect allocation. *That* I
don't know how to do sanely in our compiler (I can do it badly, of course).

> So we use handles which
> creates a level of indirection, and allows the data structures to
> survive as long as the implementation needs them, even if the actual
> user can no longer do explicit allocations or deallocations.

I don't see any need or value to this level of indirection. If the compiler
wants to add such a level, it can, but there should be no requirement to do so.

> Note that the language already does something pretty similar with task
> objects, where those are really handles on underlying tasks.

Which turned out to be a major problem when we added discriminants to tasks, so
now they're handles with discriminant components, and there are bizarre rules
giving the discriminants a different lifetime than everything else. A totally
messed up model. Let's not do that again...

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

From: Bob Duff
Sent: Sunday, June 13, 2010  8:35 PM

> Note that the language already does something pretty similar with task
> objects, where those are really handles on underlying tasks.

Most (all?) implementations do that, but I don't think the language forces it.
Does it?  I was under the impression that "task control blocks" could be
allocated entirely within task objects, with no heap allocation.

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

From: Tucker Taft
Sent: Monday, June 14, 2010  7:27 AM

One thing I should have said is that I
also wanted to preserve the level of
indirection because I believe it is
very helpful if someone wants to add back in some kind of automatic reclamation
in the presence of various kinds of references (e.g., pool-to-pool, strong
references, and weak references).  I realize I was requested to remove much of
that, but I wanted to make it possible for implementations to provide additional
functionality without having to completely revamp the basic model.

Weak references, in particular, are extremely useful to support caching, and
they really depend on a level of indirection.

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

From: Steve Baird
Sent: Monday, June 14, 2010  12:08 PM

>  I was under the impression that
> "task control blocks" could be allocated entirely within task objects,
> with no heap allocation.

In Ada95, you could have something like

   declare
     type R is record
       F1 : Integer := 123;
       F2 : Some_Task_Type;
     end record;

     R_Var : R;

     function F return R is
     begin
         return R_Var;
     end F;

     procedure P (X : R ) is
     begin
        R_Var.F1 := 456;
        pragma Assert (X.F1 = 123);
     end P;
   begin
     P (F);
   end;

Assuming that it is not ok to make a copy of a TCB, this is difficult to
implement correctly if a TCB is stored within the task object itself.

For later versions of the language, I think you are right.

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

From: Bob Duff
Sent: Monday, June 14, 2010  1:19 PM

Maybe I'm missing something, but that doesn't seem right to me.
R is a return-by-ref type (in Ada 95!), so F returns a view of R_Var, and X is a
view of that same thing, so after "R_Var.F1 := 456;", "X.F1" must be 456.  Not
copies needed or allowed.

> For later versions of the language, I think you are right.

Right, for later versions, the above is illegal.

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

From: Steve Baird
Sent: Monday, June 14, 2010  1:42 PM

You're right. I was confused.
Sorry about the noise.

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

From: Tucker Taft
Sent: Monday, June 14, 2010  1:22 PM

It is (much!) easier to implement the
unchecked-deallocation rules if
the TCBs are not embedded in the
task object.  Remember that tasks
keep executing after unchecked
deallocation.

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

From: Erhard Ploedereder
Sent: Sunday, June 20, 2010  5:34 PM

To combine Randy's notion of Unchecked_deallocation of subpools with the
ref-counting model and make dangling references commission errors again, try the
following semantics:

Unchecked_Deallocation (give it a different name, such as Unchecked_Free) of
subpools is the only way to deallocate them. Masters do not matter for
deallocation semantics. However, actual deallocation happens only if the
reference count of the subpool is zero. In any case, however, the
allow-references links emanating from the subpool are deleted and the subpool
cannot be used for allocation any more. It can still be used as target for
allow_references, though. (The latter to correctly deal with assignment to
components of surviving objects in the subpool.)

Now it is up to the deallocator/free-er to ensure that allow_references are set
sufficiently to avoid dangling references. It is a commission error (i.e.,
erroneous) to free a subpool while the allow-references are incorrectly set.

Maybe a disallow_references interface is needed to withdraw links individually.

(The model is probably not completely safe because manipulations of objects  in
an Unchecked_Free subpool can mess things up, but it is miles better than  the
dangling references due to omission errors.)

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

From: Tucker Taft
Sent: Tuesday, June 22, 2010 11:12 AM

This looks like an interesting compromise.

I would be against providing "Disallow_Reference"
as that dramatically increases complexity of implementation of circularity
handling. It also breaks several assumptions of the more sophisticated
approaches to safety which I still hope implementations can "layer on" at a
later time if they so choose.

I see "Allow_Reference" as a kind of "commit"
which cannot be withdrawn.  All you can do is get rid of the handle to the
"from" subpool (by doing an unchecked-delete-subpool) which will effectively
eliminate the reference to the "to" subpool once the "from" subpool is
unreachable.

Since this proposal does not allow immediate deletions of the subpool, but
rather deletes the handle on the subpool, it might mean that the routine's name
should reflect that, such as "unchecked_delete_subpool_handle."  This is saying
there are no further pointers to the subpool from local variables.  There might
still be pointers to the subpool from other subpools, and only when those
subpools are no longer reachable is the underlying subpool reclaimed.

It might be considered an error to exit the scope of a subpool handle without
explicitly calling a delete on the handle, as it would create a storage leak.
That error could presumably be eliminated in implementations that add
reachability checks, thereby allowing them the confidence that there are no
dangling references into the subpool.

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

Questions? Ask the ACAA Technical Agent