Safe Pointers

Author: Christoph Karl Walter Grein

Updated on 14.07.2014 Download

Access types in Ada have been designed in a way to prevent the occurrence of dangling references, i.e. they can never designate objects that have gone out of scope. There remains however one problem: When Unchecked_Deallocation is used in order to reclaim storage, we might access already freed storage or, even worse, storage occupied by new objects of different types, unless utmost care is taken (this is the very reason why the generic is called unchecked deallocation). Thus in the following fragment (with a suitable instantiation for Free), B.all no longer exists when it is referenced, but no exception is generally raised:

(Note however that A.all would raise Constraint_Error. B.all might raise an exception; it depends on what it references at the time.)

In Ada83, there was no way to prevent this in a safe way (since we had no control about objects going out of scope, we could never know for sure how many access objects were currently designating the same object), but in Ada95 with the controlled types, we are able to provide an abstraction of safe pointers for which dereferencing as in the example above will inevitably raise Constraint_Error.

Ada2005 has brought further changes, the most important ones in this context are the removal of return-by-reference functions and the possibility to instantiate certain generics like our safe pointers in local contexts. The former language change has necessitated a fundamental code change. Hence both versions (Ada95 and Ada2005) are available. This text describes the Ada2005 version; the original Ada95 version description is available as a MS word document.

As we shall see, our safe pointers work like access types while keeping track of all pointers to an object.1 So the maximum set of operations that we have to provide comprises:

Note however that Ada provides a plethora of type classes for which some of the above operations do not exist: e.g. limited, private, definite, indefinit types, and combinations thereof. So defining one root package as a container for children providing safe pointer types for different type classes is a good idea.

We will now present a generic child unit providing a safe pointer type designating objects of a definite type, i.e. of a type with the maximum set of operations.

The idea behind the implementation is to allocate each object designated by a safe pointer exactly once and to count all pointers designating the same object. Only when this counter is zero can we finalize the pointer, i.e. free all occupied storage. (See specification and body.)

We will show in a few examples how safe pointers work. For comparison, the corresponding statements with access types are also given.

After their declaration (without an initial value), they both point to nothing (the object with component Null_Track returned by Null_Pointer in the case of P and Q and null in the case of A and B).

The call of Allocate decreases the counter of the object designated by P (currently there is none, so it is finalized) and creates a new object and tracker; there is now one pointer to the new object.

The assignment decreases the counter of (the object designated by) Q (again there is none) and increases the counter of P; there are now two pointers to the object.

The call of procedure Assign assigns a value to P. Since P and Q designate the same object, dereferencing either returns the given object. The same is of course true for A and B.

(Functionality removed, see below)

R points to the aliased object O, the counter is one; note that the 'Unchecked_Access attribute has to be used because of the accessibility rules. In the assignment, the counter is decremented and R can be finalized - there is no pointer left designating O. After the assignment, there are three pointers to the object designated by P. When R leaves its scope, it is finalized again, so two pointers remain.

So far we have seen nothing special about safe pointers. The big difference from access types will be shown in a moment.

This fragment deallocates the object designated by P and Q, decreases the counter of Q (which is also the counter of P), and sets Q to Null_Pointer (this leaves P unchanged). Although the internal representations of P and Q are now different, the equality operator will return True in all three cases above, which is not the case for access types as shown. And also other than with access types, dereferencing with either pointer (as well as with A) will inevitably raise Constraint_Error, whereas dereferencing with B will return the old object, although it no longer exists. What still exists is the storage location where it had been sitting and also the bit pattern at that place, so that B, ignorant of the facts, interprets it in the usual way.

Since pointers do reference counting, deallocation is actually not needed. Assignment of Null_Pointer or letting go pointers out of scope also deallocates automatically the object as soon as the last pointer has disappeared. You can write a complete application without ever deallocating without leaking storage. Deallocate is simply provided because it also exists for access types.

For each object created, a tracker is created as well, which with each allocation or assignment operation and also when a pointer is finalized updates the number of pointers designating this object. The storage occupied by an object and its tracker are automatically reclaimed if there is no pointer left designating this object after such an operation.

Storage occupied by an object can also be deallocated explicitly. With this operation, any other pointers designating this object are set to a null value. Thus, if X and Y are pointers designating the same object, erroneous access through Y after deallocation of X is impossible. The exception Constraint_Error is raised instead.

There is one problem with safe pointers that also haunts the Ada container library: There is no way to write directly to components of composite objects in a completely safe way; you must alway take a copy of the whole object, make the assignment to the component, then store whole object again.

Thus Ada definitely needs a safe method to return references. There are some deliberations in this vein in Ada Issue AI05-142, but whether this will make it into the next revision and in which form, even the gods don't know.

A solution which comes near this goal is presented by the function Reference. It returns an accessor of which only the discriminant is of interest: It grants direct access to the object in a nearly uncompromisable way.

where X is some object with a component C. A reference object is limited so it cannot be copied - you can just use it for dereferencing. Further while this reference exists, any attempt to deallocate the referenced object (the Ada Reference Manual calls this tampering) leads to Program_Error, so the reference cannot become dangling. Lifetimes of such objects tend to be short.

Lifetime is even shorter if you don't use a local store as above. Here, the reference is finalized directly after the assignment:

In RM language (7.6.1(3/2)), the assignment statement is the master of the local reference object. (Note: GNAT GPL 2009 does not finalize, it needs a block as above; GNAT GPL 2011 works correctly.)

You might think that also the following code shows tampering attempts:

While the reference still exists, P stops pointing to the referenced value. While this is true, it's not really a problem, since the value still exists, other than when deallocation is called, so you do not access a dangling pointer. (The body of Allocate could easily be changed to also raise Program_Error in this case, but I have not found a way to prevent the assignment. Consistency requires that either both, assignment and allocation, raise Program_Error or none do.)

You are even safe against inadvertantly storing a copy of the discriminant Value in an access type that has a longer lifetime. Accessibility checks make the following program fragment illegal. (Note: GNAT GPL 2009 still accepts this code; GNAT GPL 2011 works correctly.)

I would also have liked to construct the type Accessor in such a way that a declaration of an accessor object without initialization by a call of Reference would have raised Program_Error, but I didn't find a (satisfactory) way to do so. But also without this, such an accessor object is harmless, because it is completely useless.

(This is the reason why the aliasing functionality has been removed. You can find the code still in the Ada 95 version.) One severe error however remains possible:

We can call this the law of constant malice. This happens because we have to use the 'Unchecked_Access attribute (RM 3.10.2). Inadvertant use of the simple 'Access attribute leads to a disastrous effect:

Program_Error is raised and the pointer's internal representation is destroyed leading to complete chaos. We need a double block to cure the situation!

As an excercise, the reader is invited to investigate what exactly happens.

So safe pointers clean up behind themselves properly; no dangling references can ever be produced. The astute reader will however note that this does not mean safety against storage leaks. We can always create inaccessible islands, e.g. a ring of cyclically connected objects that is not accessible from outside.

The really enthusiastic reader might care to construct child packages for other type classes.

As a concluding example, the specification of a child package for safe pointers on limited indefinite types is given. Only dereferencing operations are available for such types. We cannot allocate an object without giving an initial value, because the type has unknown discriminants - nor can we allocate with an initial value, because assignment is not available. So in fact, safe pointers behave exactly like access types for such types - the whole package does not make much sense!


with Ada.Finalization;

generic

  type Object (<>) is limited private;

package Safe_Pointers.On_Limited_Indefinite_Types is

  type Safe_Pointer is private;

  type Accessor (Value: not null access Object) is limited private;

  function Null_Pointer return Safe_Pointer;

  function "=" (Left, Right: Safe_Pointer) return Boolean;

  function Reference (Pointer: Safe_Pointer) return Accessor;

private

  type Object_Pointer is access Object;

  type Track is record
    Object: Object_Pointer;
    Count : Natural := 0;
  end record;

  type Tracker is access Track;
  pragma Controlled (Tracker);

  Null_Track: constant Tracker := new Track;

  type Safe_Pointer is new Ada.Finalization.Controlled with record
    Track: Tracker := Null_Track;
  end record;

  procedure Adjust   (Pointer: in out Safe_Pointer);
  procedure Finalize (Pointer: in out Safe_Pointer);

  type Accessor (Value: not null access Object) is ...;

end Safe_Pointers.On_Limited_Indefinite_Types;


1 This is similar to some garbage collection algorithms known as Reference Counting.

Download Ada 95 and Ada 2005 packages together with test programs in zip format.


History
14.07.2014 Bug fix RM 7.5(2/2) Accessor (full definition)
13.07.2011 Ada 2012 drops pragma Controlled; didn't do anything anyway, so removed already now
05.07.2011 For Ada 2005 version only:
Free for client type added (needed when the type has components that need to be freed as well);
bug fix in Finalize (must be idempotent)
12.02.2009 Added an Ada 2005 version
1999 First release

Also see Smart Pointers, an alternative implementation.


Published in Ada User Journal, Volume 20, Number 2 (Juli 1999)
and as a reprint in Ada Letters, Volume XIX, Number 4, December 1999.