The Ada Resource Association
Safe Pointers in Ada

Safe Pointers

Author: Christoph Karl Walter Grein

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:

A, B: Some_Access_Type;
A := new Accessed_Object;
B := A;
Free (A);
... B.all ...

(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.

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:

  • a null pointer (not designating anything) [null]
  • assignment (to both, pointers and referenced objects)
  • equality
  • allocation (with and without a value) [new]
  • deallocation [Unchecked_Deallocation]
  • dereferencing [all]
  • referencing ['[Unchecked_]Access]

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.

package Safe_Pointers is
  pragma Pure;
end Safe_Pointers;

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.

P, Q: Safe_Pointer;
A, B: Some_Access_Type;
... P = Q = Null_Pointer ...
... A = B = null ...

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).

Allocate (P);
A := new Accessed_Object;

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.

Q := P;
A := B;

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.

Assign (P, Object);
... Value (P) = Value (Q) ...
... Value (P) = Object ...
A.all := Accessed_Object;
... A.all = B.all ...

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.

declare
  O: aliased Accessed_Object;
  R: Safe_Pointer;
begin
  Alias (R, O'Unchecked_Access);
  R := P;
end;

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.

Deallocate (Q);
... Q = Null_Pointer ...
... P = Null_Pointer ...
... Q = P ...
... Value (P) ... -- Constraint_Error
... Value (Q) ... -- Constraint_Error
Free (A);
... A  = null ...
... B /= null ...
... A.all ... -- Constraint_Error
... B.all ... -- no Constraint_Error

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.

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 is automatically reclaimed if there is no pointer left designating this object after such an operation.

There is one point we have to be very careful about when deallocating storage: We must not free aliased objects lest the program become erroneous! Since there is no language-defined way to recognize pool elements (elements created by an allocator) 2, a boolean component Pool_Element has been defined: Only if it is True for a tracker object, can we safely apply Free to it.

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.

So safe pointers clean up behind themselves properly. 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.

One severe error however remains possible:

declare
  O: aliased Accessed_Object;
  R: Safe_Pointer;
begin
  Alias (R, O'Unchecked_Access);
  P := R;
end;  -- out-of-scope O remains
      -- accessible via global P!

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:

begin
  declare
    O: aliased Accessed_Object;
    R: Safe_Pointer;
  begin
    begin
      Alias (R, O'Access);
    exception
      when Program_Error => null;
    end;
    R := Null_Pointer;
  end;
exception
  when Program_Error => null;
end;

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. 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 aliasing and 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;

  function Null_Pointer return Safe_Pointer;

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

  procedure Alias (Pointer: in out Safe_Pointer;
                   Value  : access Object);
  function  Value (Pointer:        Safe_Pointer)
                            return Object;
private

  type Object_Pointer is access all 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);

end Safe_Pointers.On_Limited_Indefinite_Types;

1 This is similar to some garbage collection algorithms known as Reference Counting.
2 There is no general way to do this.

Download packages together with test program in zip format. The code has been tried out with Gnat 3.10p1.


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