Chapter 5: Programming Practices - TOC - 5.4 DATA STRUCTURES

5.4.5 Dynamic Data

guideline

Differentiate between static and dynamic data. Use dynamically allocated objects with caution.

Use dynamically allocated data structures only when it is necessary to create and destroy them dynamically or to be able to reference them by different names.

Do not drop pointers to undeallocated objects.

Do not leave dangling references to deallocated objects.

Initialize all access variables and components within a record.

Do not rely on memory deallocation.

Deallocate explicitly.

Use length clauses to specify total allocation size.

Provide handlers for Storage_Error .

Use controlled types to implement private types that manipulate dynamic data.

Avoid unconstrained record objects unless your run-time environment reliably reclaims dynamic heap storage.

Unless your run-time environment reliably reclaims dynamic heap storage, declare the following items only in the outermost, unnested declarative part of either a library package, a main subprogram, or a permanent task:

- Access types

- Constrained composite objects with nonstatic bounds

- Objects of an unconstrained composite type other than unconstrained records

- Composite objects large enough (at compile time) for the compiler to allocate implicitly on the heap

Unless your run-time environment reliably reclaims dynamic heap storage or you are creating permanent, dynamically allocated tasks, avoid declaring tasks in the following situations:

- Unconstrained array subtypes whose components are tasks

- Discriminated record subtypes containing a component that is an array of tasks, where the array size depends on the value of the discriminant

- Any declarative region other than the outermost, unnested declarative part of either a library package or a main subprogram

- Arrays of tasks that are not statically constrained

example

These lines show how a dangling reference might be created:

P1 := new Object;
P2 := P1;
Unchecked_Object_Deallocation(P2);

This line can raise an exception due to referencing the deallocated object:

X := P1.all;

In the following three lines, if there is no intervening assignment of the value of P1 to any other pointer, the object created on the first line is no longer accessible after the third line. The only pointer to the allocated object has been dropped:

P1 := new Object;
...
P1 := P2;

The following code shows an example of using Finalize to make sure that when an object is finalized (i.e., goes out of scope), the dynamically allocated elements are chained on a free list:

with Ada.Finalization;
package List is
   type Object is private;
   function "=" (Left, Right : Object) return Boolean;  -- element-by-element comparison
   ... -- Operations go here
private
   type Handle is access List.Object;
   type Object is new Ada.Finalization.Controlled with
      record
         Next : List.Handle;
         ... -- Useful information go here
      end record;
   procedure Adjust (L : in out List.Object);
   procedure Finalize (L : in out List.Object);
end List;
package body List is
   Free_List : List.Handle;
   ...
   procedure Adjust (L : in out List.Object) is
   begin
      L := Deep_Copy (L);
   end Adjust;
   procedure Finalize (L : in out List.Object) is
   begin
      -- Chain L to Free_List
   end Finalize;
end List;

rationale

See also Guidelines 5.9.1, 5.9.2, 6.1.5, and 6.3.2 for variations on these problems. A dynamically allocated object is an object created by the execution of an allocator (new). Allocated objects referenced by access variables allow you to generate aliases , which are multiple references to the same object. Anomalous behavior can arise when you reference a deallocated object by another name. This is called a dangling reference. Totally disassociating a still-valid object from all names is called dropping a pointer. A dynamically allocated object that is not associated with a name cannot be referenced or explicitly deallocated.

A dropped pointer depends on an implicit memory manager for reclamation of space. It also raises questions for the reader as to whether the loss of access to the object was intended or accidental.

An Ada environment is not required to provide deallocation of dynamically allocated objects. If provided, it may be provided implicitly (objects are deallocated when their access type goes out of scope), explicitly (objects are deallocated when Ada.Unchecked_Deallocation is called), or both. To increase the likelihood of the storage space being reclaimed, it is best to call Ada.Unchecked_Deallocation explicitly for each dynamically created object when you are finished using it. Calls to Ada.Unchecked_Deallocation also document a deliberate decision to abandon an object, making the code easier to read and understand. To be absolutely certain that space is reclaimed and reused, manage your own "free list." Keep track of which objects you are finished with, and reuse them instead of dynamically allocating new objects later.

The dangers of dangling references are that you may attempt to use them, thereby accessing memory that you have released to the memory manager and that may have been subsequently allocated for another purpose in another part of your program. When you read from such memory, unexpected errors may occur because the other part of your program may have previously written totally unrelated data there. Even worse, when you write to such memory you can cause errors in an apparently unrelated part of the code by changing values of variables dynamically allocated by that code. This type of error can be very difficult to find. Finally, such errors may be triggered in parts of your environment that you did not write, for example, in the memory management system itself, which may dynamically allocate memory to keep records about your dynamically allocated memory.

Keep in mind that any unreset component of a record or array can also be a dangling reference or carry a bit pattern representing inconsistent data. Components of an access type are always initialized by default to null; however, you should not rely on this default initialization. To enhance readability and maintainability, you should include explicit initialization.

Whenever you use dynamic allocation, it is possible to run out of space. Ada provides a facility (a length clause) for requesting the size of the pool of allocation space at compile time. Anticipate that you can still run out at run time. Prepare handlers for the exception Storage_Error, and consider carefully what alternatives you may be able to include in the program for each such situation.

There is a school of thought that dictates avoidance of all dynamic allocation. It is largely based on the fear of running out of memory during execution. Facilities, such as length clauses and exception handlers for Storage_Error, provide explicit control over memory partitioning and error recovery, making this fear unfounded.

When implementing a complex data structure (tree, list, sparse matrices, etc.), you often use access types. If you are not careful, you can consume all your storage with these dynamically allocated objects. You could export a deallocate operation, but it is impossible to ensure that it is called at the proper places; you are, in effect, trusting the clients. If you derive from controlled types (see Guidelines 5.3.3, 5.9.6, 8.3.1, 8.3.3, and 9.2.3 for more information), you can use finalization to deal with deallocation of dynamic data, thus avoiding storage exhaustion. User-defined storage pools give better control over the allocation policy.

A related but distinct issue is that of shared versus copy semantics: even if the data structure is implemented using access types, you do not necessarily want shared semantics. In some instances you really want := to create a copy, not a new reference, and you really want = to compare the contents, not the reference. You should implement your structure as a controlled type. If you want copy semantics, you can redefine Adjust to perform a deep copy and = to perform a comparison on the contents. You can also redefine Finalize to make sure that when an object is finalized (i.e., goes out of scope) the dynamically allocated elements are chained on a free list (or deallocated by Ada.Unchecked_Deallocation).

The implicit use of dynamic (heap) storage by an Ada program during execution poses significant risks that software failures may occur. An Ada run-time environment may use implicit dynamic (heap) storage in association with composite objects, dynamically created tasks, and catenation. Often, the algorithms used to manage the dynamic allocation and reclamation of heap storage cause fragmentation or leakage, which can lead to storage exhaustion. It is usually very difficult or impossible to recover from storage exhaustion or Storage_Error without reloading and restarting the Ada program. It would be very restrictive to avoid all uses of implicit allocation. On the other hand, preventing both explicit and implicit deallocation significantly reduces the risks of fragmentation and leakage without overly restricting your use of composite objects, access values, task objects, and catenation.

exceptions

If a composite object is large enough to be allocated on the heap, you can still declare it as an in or in out formal parameter. The guideline is meant to discourage declaring the object in an object declaration, a formal out parameter, or the value returned by a function.

You should monitor the leakage and/or fragmentation from the heap. If they become steady-state and do not continually increase during program or partition execution, you can use the constructs described in the guidelines.