Gem #99: Reference Counting in Ada - Part 2: Task Safety

In Part 1, we described a reference-counted type that automatically frees memory when the last reference to it disappears. But this type is not task safe: when we decrement the counter, it might happen that two tasks see it as 0, and thus both will try to free the data. Likewise, the increment of the counter in Adjust is not an atomic operation, so it is possible that we will be missing some references.

In some applications this restriction is not a big issue (for instance, if there are no tasks, or if the types are only ever used from a single task). However, let's try to improve the situation.

The traditional solution is to use a lock while we are manipulating the counter. We could, for instance, use a protected type for this. However, this means that a nontasking application using our reference-counted types would have to initialize the whole tasking run-time, which could impact execution somewhat, since part of the code goes through slower code paths.

GNAT provides a global lock that we can reuse for that, and that does not require the full tasking run-time. We could use that lock in a function that changes the value of the counter atomically. We need to return the new value from that function: changing the value atomically solves the problem we highlighted for Adjust, but not the one we showed for Finalize, where two tasks could see the value as 0 if they read it separately.

function Atomic_Add
  (Ptr : access Integer; Inc : Integer) return Integer
is
   Result : Integer;
begin
   GNAT.Task_Lock.Lock;
   Ptr.all := Ptr.all + Value;
   Result := Ptr.all;
   GNAT.Task_Lock.Unlock;
   return Result;
end Atomic_Add;

On some systems there is actually a more efficient way to do this, by using an intrinsic function: this is a function provided by the compiler, generally implemented directly in assembly language using low-level capabilities of the target machine. We need special handling to check whether this facility is available, but if it is, we no longer need a lock. The GNATCOLL.Refcount package takes full advantage of this.

function Atomic_Add
  (Ptr : access Integer; Inc : Integer) return Integer
is
   function Intrinsic_Sync_Add_And_Fetch
     (Ptr   : access Interfaces.Integer_32;
      Value : Interfaces.Integer_32) return Interfaces.Integer_32;
   pragma Import
     (Intrinsic, Intrinsic_Sync_Add_And_Fetch, "__sync_add_and_fetch_4");
begin
   return Intrinsic_Sync_Add_And_Fetch (Ptr, Value);
end Atomic_Add;

(Note: In actual practice, it would be necessary to declare the access parameter of function Atomic_Add with type Interfaces.Integer_32, for type compatibility with the intrinsic.)

Once we have this Atomic_Add function we need to modify our reference-counted type implementation. The first change is to declare the Refcount field as aliased, in the definition of Refcounted. We then revise the code as follows:

overriding procedure Adjust (P : in out Ref) is
   Dummy : Integer;
begin
   if P.Data /= null then
      Dummy := Atomic_Add (P.Data.Refcount'Access, 1);
   end if;
end Adjust;

overriding procedure Finalize (P : in out Ref) is
   Data : Refcounted_Access := P.Data;
begin
   P.Data := null;
   if Data /= null 
      and then Atomic_Add (Data.Refcount'Access, -1) = 0
   then
      Free (Data.all);
      Unchecked_Free (Data);
   end if;
end Finalize;

The last Gem in this series will talk about a different kind of reference, generally known as a weak reference.