Reference counting

Reference counting is a way to automatically reclaim unused memory. An element is automatically deallocated as soon as there are no more references to it in the program.

The general idea is to implement a type similar to a pointer (often called a smart pointer). In addition to pointing to the element data, this type also counts the number of times it is used in the program. When this smart pointer is copied, the reference count is increased by one. When the smart pointer is finalized (goes out of scope), the reference count is decreased. If it reaches 0, then it is safe to deallocate the element.

Such a pointer is therefore implemented as a controlled type, and the compiler automatically calls the Adjust and Finalize primitives, which take care of manipulating the reference counter. This has a definite performance impact (since a lot of calls to Adjust and Finalize are added to your application), but smart pointers might greatly simplify memory management in your application.

A lot of modern languages use this approach (C++, Swift, Python, Objective-C, Perl,...). Others use a more general approach via garbage collection.

Storing the reference counter

There are several ways that such a smart pointer can be implemented:

• Intrusive reference counting
  The AdaCore Gem #97 described an intrusive approach. The element itself must contain its reference count. For this purpose, the element type must extend a base tagged type (named Refcounted in our implementation). This approach is the basis for GNATCOLL.Refcount.Smart_Pointers.
  One of advantages of this approach is that it is efficient, since the smart pointer only needs to allocate memory once for the element and the counter (memory allocation is generally slow, so we must do as little of it as possible, at least in this context).
  One drawback of course is that the element type must be tagged and derived from a specific base type. This reduces flexibility.
• Nonintrusive reference counting
  Another approach is to accept any element type, and store the reference counter independently. This counter needs to be shared by all smart pointers to the same element, so we also need to allocate memory for it.
  This means that in general we need to do two memory allocations: one for the element, and one for the counter.
  This provides a more flexible API since any type can be wrapped in a smart pointer. The performance cost (two memory allocations) can be cancelled by using an appropriate storage pool, so that when we allocate space for the element we also reserve space for its reference counter.
  See the "Larger than it looks" blog post for more information on how this storage pool is implemented.

This second approach has now been implemented in the GNAT Components Collection, as the GNATCOLL.Refcount.Shared_Pointers package (the name is inspired by the C++ shared_ptr template, which plays a similar role).

Reviewing the Get API

The implementation described in Gem #97 was unsafe. Get would return an access to the element, which has several drawbacks (highlighted in a later Gem #107):

• Users might try to free the element access
  This would of course result in invalid memory access later on, but even if users do not try this, that still makes the API more confusing because we need explicit comments to describe who has the ownership of the data.
• Users might store the element access in a local variable or record
  This access might be freed at any time if the last reference to it disappears, and therefore accessing it is dangerous. Much better to always access it via the shared pointer.

Instead, the new API in GNATCOLL.Refcount.Shared_Pointers now returns a reference type for Get. Such types were introduced in Ada 2012 for the standard containers. They are basically records with access discriminants, and they use the Implicit_Dereference aspect. Here is an example:

Since the discriminant can only be read and not converted, it cannot easily be deallocated in practice.

The reference type itself has been made limited, so that it cannot be stored in a record. This encourages users to store the shared pointer instead, which in turn guarantees that the element remains live while the record exists.

We still do not prevent storing the access type in a record, but this has to be done via an anonymous access type. This could still result in invalid memory accesses though, as in the following example:

The GNAT compiler team recently significantly improved the performance for reference types. Their size is known at compile time, but since they are unconstrained types anyway, the compiler used to return them on the secondary stack, requiring extra calls to malloc. They are now just as efficient as using pointers, except that they are safer.

Reviewing the Set API

The intrusive version of the smart pointers described in Gem #97 had two versions of Set:

This API is safe in the context of intrusive smart pointers, since they contain their own reference count. As a result, if we are to do something like:

In this case, E will not be freed while either R1 or R2 exists.

This approach is however not suitable in the case of nonintrusive shared pointers, since they need to be allocated through the special storage pool we mentioned before. For that reason, only the first version of Set is provided, and will allocate the memory and copy the Data as needed.

However, there are cases where we need one extra subprogram. Let's say our Element_Type is a tagged type, with a primitive operation that uses an access parameter, as in:

In the procedure, we definitely do not want to initialize R with a call like R.Set (Self.all). This would store a copy of Self in R, which likely is not what we want. This could even be dangerous since R will be finalized when Primitive exits, resulting in a freeing of the element stored in R (a copy of Self), which might end up freeing some data stored in Self. R2 itself since accesses Self, we might end up using deallocated memory.

Instead, the proper approach is to use:

This call must only be used when Self is indeed already managed by a shared pointer. It ensures that Self and its data will not be freed while either R or R2 exist.

Conclusion

The new package GNATCOLL.Refcount.Shared_Pointers provides a number of enhancements over the older GNATCOLL.Refcount.Smart_Pointers. The API is more flexible since any Element_Type can be put under control of a shared pointer. They are also more efficient thanks to various internal optimizations.

More importantly, perhaps, they are actually safer since the API will prevent cases where users might end up using deallocated memory.

This post did not mention other aspects which are of course preserved in this new API: task-safety and weak pointers.