What are storage pools ?

Storage pools are Ada's way of letting users control memory management in their applications. A pool is an object associated with one or more specific types via a Storage_Pool attribute. Whenever the application performs memory allocation via the new operator, or frees memory via an instance of Unchecked_Deallocation, the storage pool Allocate and Deallocate primitives are used, instead of doing a direct call to the system's libraries for memory management.

There are multiple reasons why such a pool might be useful in your application. The typical two benefits are:

• performance
  By using your own pool, you can allocate for instance a single large buffer and then reuse it for multiple objects in your application, without having to go call the slower system malloc every time.
• automatic memory reclamation
  With the above approach, the buffer can be freed all at once, without freeing each of the objects individually.

Header storage pools

In this post, we will study another usage for storage pools. The goal is to allocate an extra header whenever we allocate memory for an object. This header is user-defined, and can be used to store per-object information, independently of the exact type of the object.

Here are two examples of use:

• reference counting
  To implement reference counting for types, we need to store a counter for the number of references to the object. This counter can be stored in an extra header, rather than be allocated elsewhere in memory.
• more efficient list nodes
  A doubly-linked list needs to store Previous and Next pointers for each of its nodes. We can store them in the extra header.

In both cases, storing information in the header results in improved performance, since we can do a single call to the system malloc, instead of two. This is further improved by taking advantage of hardware prefetching and caching, since the data from the extra header is kept close to the element data in memory.

Implementation details

Implementing such a pool is a bit tricky, since there are several details to take care of:

• alignment
  A lot of processors expect memory blocks to be aligned on specific memory boundaries (bytes, words or double-words) for more efficient access. The system malloc takes care of that, of course, but that only means that our header will be properly aligned. We need some extra care to ensure that the element itself is also properly aligned.
• fat pointers
  In Ada, some types require extra information. For instance, an unconstrained array needs access to its bounds (First and Last). GNAT typically uses a "fat pointer" for this purpose: the access itself is in fact a record of two pointers, one of which points to the bounds, the other points to the data. This representation is not appropriate in the case of the header storage pool, so we need to change the memory layout here.
• efficiency
  Of course, we would like our storage pool to have a minimal overhead.

Let's start by setting up our storage pool. This will be a generic package, since we want the contents of the extra header to be user-defined. Since the handling of fat pointers is also type specific, we will pass the type of element as another formal parameter. This means that for each type, we will need a different storage pool, they can't be shared by multiple types.

In practice, the implementation we have now added in the GNAT Components Library (GNATCOLL.Storage_Pools.Headers) uses multiple generic packages to share code as much as possible and reduce the impact on code size, but for the sake of this presentation we will take a simpler approach.

The extra header must be a constrained type, since we need to know its size in advance. The element type, however, can be any type (hence the use of keyword limited and the (<>) in its declaration) since its actual size will be known when the user calls the new operator (and that size is passed automatically to Allocate).

This example also uses Ada 2012, for instance to use the Inline aspect. This can easily be replaced with a pragma Inline, though. This aspect is used in a number of places, to satisfy our efficiency requirement.

Pointers to the element type

As we mentioned before, we need to ensure that the bounds for unconstrained arrays are stored next to the element, not in a separate memory block, to improve performance. This is done by setting the Size attribute on the type. When we set this size to that of a standard pointer, GNAT automatically changes the layout, so that we now have:

 +-------+------+---------+
 | First | Last | Element |
 +-------+------+---------+

The result of the new operator still returns a pointer to the Element in the above, so the application does not have direct access to First and Last (except, of course, via the 'First and 'Last attributes).

At the same time that we declare this access to the element, we also associate it with the pool so that allocations and deallocations are done by the pool:

Size computation

Whenever Allocate is called (via the new operator), it is given the size we need to allocate for the element itself. This size does not include the bounds (First and Last in the previous section), nor the size of the extra header itself. So we need to do a bit of computation to get the exact size we need to request from the system.

The size for the bounds is given by the attribute Descriptor_Size. For most types, the value of this attribute is 0. However, in the case of unconstrained array types, it is the size of two integers.

In some cases, GNAT needs to allocate even more memory in fact. When a type is potentially a controlled type (a class-wide type for instance, or an array of controlled types), GNAT needs to store this type in a linked list so that it can find all such instances and properly finalize them when the program terminates. This extra size is the size of two pointers (Previous and Next) that are used to implement the list.

Unfortunately, there is currently no attribute that provides this size for a given element type. This is being added to the compiler, but for now we will need to systematically allocate this extra size, even if the type doesn't actually need those.

As a summary, the actual layout of the memory block we will allocate is the following:

 +--------+-------+------+----------+------+---------+
 | Header | First | Last | Previous | Next | Element |
 +--------+-------+------+----------+------+---------+

Note that most of the components (First, Last, Previous and Next) might not be needed (or even allocated) for all types of elements, so we are not wasting all that memory when it isn't needed.

There is still one more difficulty. The Element part in the above needs to be properly aligned on memory boundaries. So the size of the header needs to be rounded up.

The exact computation thus becomes:

And now we can implement our Allocate as such:

The last part to implement is the deallocation. This procedure gets passed the address returned by Allocate (so a pointer to the Element part of the block). We need to convert this to the address of the beginning of the block allocated by malloc, so that we can call free on it.

This computation is actually also needed to retrieve a pointer to the header so that the application can store and access the header data. So we will make a separate function for that.

The implementation of Deallocate becomes the trivial

Conclusion

As shown by this lengthy post, implementing storage pools is not a trivial task, as there are a lot of details to take into account. Since this is a very low-level part of the code, there are also often some compiler-specific things to take into account, like the layout of types in memory.

However, there are generally only a few storage pool types used in an application, so they should be made generic when possible, and the implementation reused as much as possible.

The implementation described above is now part of the GNAT Components Collection (GNATCOLL.Storage_Pools.Headers), in a slightly different way. We use two generic packages, so that most of the code can be shared among the pools that want the same extra_header, and only a few additions in a second, type-specific, package.

Our current implementation wastes some memory for the Previous and Next pointers used for potentially controlled types. An improvement in the compiler is forthcoming, so that we do not need to allocate space for these pointers if they are not needed by the compiler. This will be transparent for the application code, although of course it will save a bit of memory at run time.

Future posts will describe how this pool was reused to implement reference counting in an efficient manner.