From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,3e0d5efc83f3702f X-Google-Attributes: gid103376,public From: Tucker Taft Subject: Re: Ada design documents Date: 1999/11/11 Message-ID: <382B1D0F.8FFA2963@averstar.com> X-Deja-AN: 547445396 Content-Transfer-Encoding: 7bit Sender: news@inmet.camb.inmet.com (USENET news) X-Nntp-Posting-Host: houdini.burl.averstar.com References: X-Accept-Language: en Content-Type: text/plain; charset=us-ascii Organization: AverStar (formerly Intermetrics) Burlington, MA USA Mime-Version: 1.0 Newsgroups: comp.lang.ada Date: 1999-11-11T00:00:00+00:00 List-Id: 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.