* Re: Ada design documents
1999-11-05 0:00 Ada design documents Ehud Lamm
1999-11-08 0:00 ` Tucker Taft
@ 1999-11-11 0:00 ` Tucker Taft
1 sibling, 0 replies; 3+ messages in thread
From: Tucker Taft @ 1999-11-11 0:00 UTC (permalink / raw)
Ehud Lamm wrote:
>
> Hi,
>
> I always find reading the Ada9x (and older) design documents fascinating.
> Arecent discussion here pointed to an older discussion of
> access-to-subprogram types, whcih referred to the MRT documents. Reading
> those was very informative.
> Reading Tuft's LSN about multiple inheritance is another example, and the
> LSN about hierarchical libraries is also highly recommended to reaaders
> that are not from the Ada9x team/DR etc.
>
> I was looking for a discussion of the "storage pool" mechanism, but wasn't
> able to find it.
> Can anyone point me in the reight direction?
I found an old "Mapping Specification" document in the "history"
section of the Ada Information Clearinghouse (www.adaic.org). I have
attached below the section of the Rationale relating
to storage pools.
> Thanks
>
> P.S
> If anyone wants to read the documents I referred to, he may go to the AJPO
> directory at http://wuarchive.wustl.edu/languages/ada/ajpo/ . Going into
> the pol-history direcotry will bring you to many interesting documents.
>
> Ehud Lamm mslamm@mscc.huji.ac.il
> http://purl.oclc.org/NET/ehudlamm <== My home on the web
> Check it out and subscribe to the E-List- for interesting essays and more!
--
-Tucker Taft stt@averstar.com http://www.averstar.com/~stt/
Technical Director, Distributed IT Solutions (www.averstar.com/tools)
AverStar (formerly Intermetrics, Inc.) Burlington, MA USA
-----------------------------
Extract from:
http://www.adaic.org/pol-hist/history/9x-history/mapping/map-spec-Mar92.txt
-----------------------------
S.G.3. User-Defined Allocators
User-defined allocators provide the application programmer with control over
the management of dynamically allocated storage. Examples of critical details
that a user might need to control include the placement of objects in pages of
different kinds of memory, control over fragmentation, and trade-offs between
speed of allocation and deallocation versus economy of storage space.
An alternative to a language-defined interface, such as the one specified here,
is for the user to avoid the use of allocator expressions and
UNCHECKED_DEALLOCATION, and perform all allocation and deallocation directly
through user-defined procedures. There are limitations to this alternative.
Some of these are:
- A compiler might represent certain types of data in a way that
permits the storage to be non-contiguous. That is, there might be
implicit indirect references (i.e. pointers) within the
representation of the data, from one part to another. There is no
way for a user-defined allocation procedure to determine whether this
is required, and to initialize the pointers properly. With the
present specification, the compiler-generated code can do this, after
the address of the storage is obtained from the user-defined
allocator.
- A compiler might need to allocate extra storage for implementation
data with certain types of objects (examples include the index bounds
of an array and storage for the discriminants of a record). In some
contexts explicit representation of such implementation data might
not be necessary, since the constraints of the object are statically
determinable. Determining whether extra storage is required, how
much space it occupies, and how it needs to be initialized, presents
a problem for a user-defined storage allocation scheme, similar to
the problem with non-contiguous representation. In fact, this
problem is likely to co-occur with the previous one, since the
implementation data might be stored discontiguously from the rest of
the object.
- A compiler might assume special alignment (e.g. even-numbered
addresses) for certain types of data. Without some special interface
such as is provided here, the user would be limited to defining
storage allocators for types where the compiler does not assume any
special alignment.
- To be completely equivalent, the user-defined allocation procedure
would also need to perform any default initialization required for
the object. This would require complete visibility of the object
type declaration, and any operations that need to be performed in the
course of the initialization, which is not possible for limited and
private types.
S.G.3.1. STORAGE_POOL Representation Clause
The proposed association of an access type with a storage pool using the
STORAGE_POOL attribute, allows the construction of user-defined allocators. In
Ada, the new statement provides two complementary features: dynamic allocation
of storage for data structures, and the initialization of these objects based
on the type information. With complex types (especially those that involve
unconstrained arrays and variant records), this initialization may be quite
complex. In these latter cases, it is often difficult for the user to mimic
the compiler work of initialization, if it chooses to provide the allocation
routines explicitly. On the other hand, there are many different storage
allocation algorithms. A large number of trade-offs are involved (e.g. whether
an allocation request should be temporarily held when storage is not available,
or immediately raise STORAGE_ERROR), and the right choice often depends on the
specific system architecture and application needs.
The separation of duties provided by user-defined allocators allows the
compiler to concentrate on using its knowledge of the type structure to perform
the correct and most efficient initialization, while providing a hook for the
user to choose and implement his favorite allocation technique without worrying
about initialization chores. (This of course is optional; the default behavior
is as in Ada 83 where the compiler/RTS do both tasks.)
The model provided by the user-defined allocator matches the Ada model
regarding the life-time of access types and their corresponding collections.
Collections are not required to be deallocated on scope exit (but in Ada 9X,
they do if the STORAGE_SIZE attribute is specified). Since a pool object may
serve multiple collections (or access types), the objects of a specific
designated type are not deallocated from the pool object when the scope of the
corresponding access type is exited. A user can achieve this effect by using
either finalization or UNCHECKED_DEALLOCATION. The entire pool object is, of
course, deallocated when it goes out of scope, but the rules ensure that no
access type that uses that pool can still be active at that point; thus there
is no danger of dangling references.
A pool object is similar to the default heap in most Ada 83 implementations:
multiple access types can share it, but objects of the designated types are not
automatically deallocated.
Allowing multiple access types to share a pool object provides the user with
the ability to share allocation algorithms for multiple types. It also
prevents unnecessary pre-allocation of storage (usually up to the maximum),
when it is known that ``groups'' of objects have disjoint life-times and thus
they can time-share a memory resource. The ALIGNMENT parameter of the ALLOCATE
procedure facilitates pool sharing by types of different alignment
requirements. Of course, such different alignment requests might not be
supported by a user-defined allocation routine.
The pool object concept encapsulates the allocation/deallocation routines with
the actual memory resource. The type ROOT_STORAGE_POOL is intentionally
similar to the CONTROLLED type. It is our intention to consider, in later
versions, a change that will make it a derived type of CONTROLLED because of
this inherent similarity.
It is envisioned that the ALLOCATE/DEALLOCATE operations will use mutual
exclusion mechanisms such as protected records to ensure their correct behavior
in a multi-tasking program.
Usually, if only one access type is associated with the same pool object, these
two should be in the same scope. It is illegal for the pool's scope to be any
``deeper'' than the access type scope, since then dangling references would be
possible. On the other hand, having the the access type scope be deeper will
leave the pool object alive longer than is required, and its storage will be
held unnecessarily.
If all the access types that are using a given pool are declared in subprograms
that are more deeply nested than that of the pool, then it is impossible to
have dangling references for the same argument as above. However, since
objects of the designated types may occupy the pool alternately (see example
below), there will be a trade-off between the frequency of entering and exiting
the access type scope and the overhead associated with allocating and
initializing the pool object itself. (Sometimes, the initialization of a pool
object may require splitting sub-blocks, setting bit-vectors, pointers arrays,
etc.)
If the access types are in different scopes (deeper than that of the object
pool itself), their storage will be held longer than necessary. If this is a
problem, then sub-pool objects may be created at the scope of each access type,
and point to the ``master'' pool. When the object representing the sub-pool is
no longer in scope (i.e., its associated access type is also out of scope), the
user-defined finalization routine can deallocate it, thus freeing space in the
master pool.
-- This example shows how a single pool object may be used
-- alternately by two access types living in sibling scopes.
procedure EXAMPLE is
-- Declare a pool object of some size to be shared by
-- multiple types
type BLOCK_LENGTH_TYPE is SYSTEM.STORAGE_COUNT (1..1000);
type MY_POOL_TYPE is new SYSTEM.ROOT_STORAGE_POOL
with record is
BLOCK : BLOCK_LENGTH_TYPE;
end record;
POOL_OBJECT : MY_POOL_TYPE;
-- Objects designated by T will be allocated in POOL_OBJECT
type T is access SOME_TYPE;;
for T'STORAGE_POOL use POOL_OBJECT;
PTR : T;
procedure PROC_1;
-- Objects designated by T1 will be allocated in POOL_OBJECT
type T1 is access SOME_TYPE_1;
for T1'STORAGE_POOL use T'STORAGE_POOL;
PTR_1 : T1;
begin
-- Perform various allocations using PTR_1 and T1
end PROC_1;
procedure PROC_2;
-- Objects designated by T2 will all be allocated in
-- POOL_OBJECT
type T2 is access SOME_TYPE_2;
for T2'STORAGE_POOL use T'STORAGE_POOL;
PTR_2 : T2;
begin
-- Perform various allocations using PTR_2 and T2
end PROC_2;
begin
for I in 1..N loop
PTR := new SOME_TYPE; -- (*1)
PROC_1;
-- (*2)
PROC_2;
end loop;
end EXAMPLE;
Notes on the example:
1. The memory occupied by these allocations (unless being unchecked
deallocated) will live until PROC is exited and POOL_OBJECT is
reclaimed.
2. Here, objects of SOME_TYPE_1 no longer exist. However, their
storage is still being held in POOL_OBJECT, unless explicitly
deallocated.
There are several trade-offs that need to be balanced by the user
here: The frequency and size of allocations vs the pool object
size; the cost of allocation/deallocation of specific objects; the
number of iterations and the relative length of the other code, etc.
Based on this trade-offs, the user can decide when and how often to
deallocate objects, and how to sub-divide the pool object.
We have considered other alternatives for supporting this functionality. One
alternative would simply associate two operations, ALLOCATE and DEALLOCATE,
with an access type. These operations would be called in the same way as in
the current proposal, but would have no implicit association with the pool
object. In fact, the concept of a pool object would not exist; it would be
represented as a hidden state of the operations (or the package in which they
are included). The heap used by these types will be finalized when the access
type goes out of scope. But since there are no INITIALIZE/FINALIZE routines,
which are called automatically by the generated code, this would all have to be
dealt with explicitly by the user. Furthermore, the code in these operations
would have no information about the types that use them, so the checks that
avoid invoking, for example, an allocation routine after the implied pool
object has gone, would be close to impossible to implement.
The issues of initialization and finalization of the user-defined ``heap''
would then have to be dealt with explicitly, and be much more error-prone, or
an additional set of rules would have to be specified. Therefore, the issues
of dangling references or heaps that live longer than necessary will have to be
addressed by the user in a way that is less safe and convenient.
Thus, we determined that this approach does not provide the desired
functionality and does not encapsulate well the service.
Another approach that was suggested was to specify the user-defined pool object
in the new construct itself. This would require modifying the source code in
every place where such an allocation takes place (and the possible occasional
omission of some). In the current proposal, everything is specified in one
place and applies to all allocations, deallocations, and finalizations of the
designated types.
S.G.3.2. Interactions with STORAGE_SIZE Attribute
The possibility of allowing STORAGE_SIZE to be specified for a type with
user-defined storage allocation was considered. The reasonable interpretation
of this combination is for the compiler to pass the user-specified storage size
to the user-defined storage manager upon initialization of the pool object.
This possibility was rejected, on the grounds that first, this information is
already present as part of the pool object declaration, and providing it in two
different ways would be redundant. Second, the information provided by the
STORAGE_SIZE clause could not be used effectively by a user-defined storage
manager. The user-defined pool object must be declared and elaborated prior to
the type to which it is bound. If the user-defined pool is to be allocated on
the stack, the size must be fixed by that point. The problem is that the
expression for STORAGE_SIZE need not be static, and so may not be evaluated
that early. By the time the information from the STORAGE_SIZE clause is
available, it is too late to use it. This problem of obtaining the size
information from the representation clause early enough to be used in sizing
the user-defined storage pool is aggravated if the user wants to use a single
storage pool for several access types.
S.G.3.3. MAX_STORAGE_SIZE Attribute
There is a well-defined requirement for user control over storage allocation
and recovery. A very important special case is where the user can achieve
constant-time allocation and deallocation operations, by using a pool of
same-sized storage blocks. The MAX_STORAGE_SIZE attribute is intended to tell
the user the size of block that would be required in this case.
Note that the SIZE attribute of a type does not meet this requirement, since it
yields the minimum number of bits needed to hold an object of this type.
^ permalink raw reply [flat|nested] 3+ messages in thread