Dynamic memory allocation (especially deallocation) using the C runtime heap, through malloc, free, strdup, calloc, realloc, etc. can result in performance degradation and out-of-memory conditions.

This is due to fragmentation of the heap. The degraded performance and exhausted memory result from indirect interactions within the heap between unrelated application code. These issues are non-deterministic, and can be very difficult to rectify.

Memory Pools offer a powerful solution. They trade-off a deterministic amount of memory for

deterministic behaviour,
O(1) allocation and release performance, and
built-in memory allocation tracking.

And it brings the power of destructors to C!

Overview

The most basic usage involves:

Creating a pool (usually done once at process start-up)
Allocating objects (memory blocks) from a pool
Releasing objects back to their pool.

Pools generally can't be deleted. You create them when your process starts-up, and use them until your process terminates. It's up to the OS to clean-up the memory pools, along with everything else your process is using, when your process terminates. (Although, if you find yourself really needing to delete pools, Sub-Pools could offer you a solution.)

Pools also support the following advanced features:

reference counting
destructors
statistics
multi-threading
sub-pools (pools that can be deleted).

The following sections describe these, beginning with the most basic usage and working up to more advanced topics.

Creating a Pool

Before allocating memory from a pool, the pool must be created using le_mem_CreatePool(), passing it the name of the pool and the size of the objects to be allocated from that pool. This returns a reference to the new pool, which has zero free objects in it.

To populate your new pool with free objects, you call le_mem_ExpandPool(). This is separated into two functions (rather than having one function with three parameters) to make it virtually impossible to accidentally get the parameters in the wrong order (which would result in nasty bugs that couldn't be caught by the compiler). The ability to expand pools comes in handy (see Managing Pool Sizes).

This code sample defines a class "Point" and a pool "PointPool" used to allocate memory for objects of that class:

#define MAX_POINTS 12  // Maximum number of points that can be handled.
typedef struct
{
    int x;  // pixel position along x-axis
    int y;  // pixel position along y-axis
}
Point_t;
le_mem_PoolRef_t PointPool;
int xx_pt_ProcessStart(void)
{
    PointPool = le_mem_CreatePool("xx.pt.Points", sizeof(Point_t));
    le_mem_ExpandPool(PointPool, MAX_POINTS);
    return SUCCESS;
}

To make things easier for power-users, le_mem_ExpandPool() returns the same pool reference that it was given. This allows the xx_pt_ProcessStart() function to be re-implemented as follows:

int xx_pt_ProcessStart(void)
{
    PointPool = le_mem_ExpandPool(le_mem_CreatePool(sizeof(Point_t)), MAX_POINTS);
    return SUCCESS;
}

Although this requires a dozen or so fewer keystrokes of typing and occupies one less line of code, it's arguably less readable than the previous example.

For a discussion on how to pick the number of objects to have in your pools, see Managing Pool Sizes.

Allocating From a Pool

Allocating from a pool has multiple options:

le_mem_TryAlloc() - Quietly return NULL if there are no free blocks in the pool.
le_mem_AssertAlloc() - Log an error and take down the process if there are no free blocks in the pool.
le_mem_ForceAlloc() - If there are no free blocks in the pool, log a warning and automatically expand the pool (or log an error and terminate the calling process there's not enough free memory to expand the pool).

All of these functions take a pool reference and return a pointer to the object allocated from the pool.

The first option, using le_mem_TryAlloc(), is the closest to the way good old malloc() works. It requires the caller check the return code to see if it's NULL. This can be annoying enough that a lot of people get lazy and don't check the return code (Bad programmer! Bad!). It turns out that this option isn't really what people usually want (but occasionally they do)

The second option, using le_mem_AssertAlloc(), is only used when the allocation should never fail, by design; a failure to allocate a block is a fatal error. This isn't often used, but can save a lot of boilerplate error checking code.

The third option, using le_mem_ForceAlloc(), is the one that gets used most often. It allows developers to avoid writing error checking code, because the allocation will essentially never fail because it's handled inside the memory allocator. It also allows developers to defer fine tuning their pool sizes until after they get things working. Later, they check the logs for pool size usage, and then modify their pool sizes accordingly. If a particular pool is continually growing, it's a good indication there's a memory leak. This permits seeing exactly what objects are being leaked. If certain debug options are turned on, they can even find out which line in which file allocated the blocks being leaked.

Releasing Back Into a Pool

Releasing memory back to a pool never fails, so there's no need to check a return code. Also, each object knows which pool it came from, so the code that releases the object doesn't have to care. All it has to do is call le_mem_Release() and pass a pointer to the object to be released.

The critical thing to remember is that once an object has been released, it must never be accessed again . Here is a very bad code example:

Point_t* pointPtr = le_mem_ForceAlloc(PointPool);
pointPtr->x = 5;
pointPtr->y = 10;
le_mem_Release(pointPtr);
printf("Point is at position (%d, %d).\n", pointPtr->x, pointPtr->y);

Reference Counting

Reference counting is a powerful feature of our memory pools. Here's how it works:

Every object allocated from a pool starts with a reference count of 1.
Whenever someone calls le_mem_AddRef() on an object, its reference count is incremented by 1.
When it's released, its reference count is decremented by 1.
When its reference count reaches zero, it's destroyed (i.e., its memory is released back into the pool.)

This allows one function to:

create an object.
work with it.
increment its reference count and pass a pointer to the object to another function (or thread, data structure, etc.).
work with it some more.
release the object without having to worry about when the other function is finished with it.

The other function also releases the object when it's done with it. So, the object will exist until both functions are done.

If there are multiple threads involved, be careful to protect the shared object from race conditions(see the Multi-Threading).

Another great advantage of reference counting is it enables Destructors.

Destructors

Destructors are a powerful feature of C++. Anyone who has any non-trivial experience with C++ has used them. Because C was created before object-oriented programming was around, there's no native language support for destructors in C. Object-oriented design is still possible and highly desireable even when the programming is done in C.

In Legato, it's possible to call le_mem_SetDestructor() to attach a function to a memory pool to be used as a destructor for objects allocated from that pool. If a pool has a destructor, whenever the reference count reaches zero for an object allocated from that pool, the pool's destructor function will pass a pointer to that object. After the destructor returns, the object will be fully destroyed, and its memory will be released back into the pool for later reuse by another object.

Here's a destructor code sample:

static void PointDestructor(void* objPtr)
{
    Point_t* pointPtr = objPtr;
    printf("Destroying point (%d, %d)\n", pointPtr->x, pointPtr->y);
    @todo Add more to sample.
}
int xx_pt_ProcessStart(void)
{
    PointPool = le_mem_CreatePool(sizeof(Point_t));
    le_mem_ExpandPool(PointPool, MAX_POINTS);
    le_mem_SetDestructor(PointPool, PointDestructor);
    return SUCCESS;
}
static void DeletePointList(Point_t** pointList, size_t numPoints)
{
    size_t i;
    for (i = 0; i < numPoints; i++)
    {
        le_mem_Release(pointList[i]);
    }
}

In this sample, when DeletePointList() is called (with a pointer to an array of pointers to Point_t objects with reference counts of 1), each of the objects in the pointList is released. This causes their reference counts to hit 0, which triggers executing PointDestructor() for each object in the pointList, and the "Destroying point..." message will be printed for each.

Statistics

Some statistics are gathered for each memory pool:

Number of allocations.
Number of currently free objects.
Number of overflows (times that le_mem_ForceAlloc() had to expand the pool).

Statistics (and other pool properties) can be checked using functions:

Statistics are fetched together atomically using a single function call. This prevents inconsistencies between them if in a multi-threaded program.

If you don't have a reference to a specified pool, but you have the name of the pool, you can get a reference to the pool using le_mem_FindPool().

In addition to programmatically fetching these, they're also available through the "poolstat" console command (unless your process's main thread is blocked).

To reset the pool statistics, use le_mem_ResetStats().

Diagnostics

The memory system also supports two different forms of diagnostics. Both are enabled by defining special preprocessor macros when building the framework.

The first of which is LE_MEM_TRACE. When you define LE_MEM_TRACE every pool is given a tracepoint with the name of the pool on creation.

For instance, the configTree node pool is called, "configTree.nodePool". So to enable a trace of all config tree node creation and deletion one would use the log tool as follows:

$ log trace configTree.nodePool

The second diagnostic build flag is LE_MEM_VALGRIND. When LE_MEM_VALGRIND is enabled, the pools are disabled and instead malloc and free are directly used. Thus enabling the use of tools like Valgrind.

Multi-Threading

All functions in this API are thread-safe, but not async-safe . The objects allocated from pools are not inherently protected from races between threads.

Allocating and releasing objects, checking stats, incrementing reference counts, etc. can all be done from multiple threads (excluding signal handlers) without having to worry about corrupting the memory pools' hidden internal data structures.

There's no magical way to prevent different threads from interferring with each other if they both access the contents of the same object at the same time.

The best way to prevent multi-threaded race conditions is simply don't share data between threads. If multiple threads must access the same data structure, then mutexes, semaphores, or similar methods should be used to synchronize threads and avoid data structure corruption or thread misbehaviour.

Although memory pools are thread-safe, they are not async-safe. This means that memory pools can be corrupted if they are accessed by a signal handler while they are being accessed by a normal thread. To be safe, don't call any memory pool functions from within a signal handler.

One problem using destructor functions in a multi-threaded environment is that the destructor function modifies a data structure shared between threads, so it's easy to forget to synchronize calls to le_mem_Release() with other code accessing the data structure. If a mutex is used to coordinate access to the data structure, then the mutex must be held by the thread that calls le_mem_Release() to ensure there's no other thread accessing the data structure when the destructor runs.

Managing Pool Sizes

We know it's possible to have pools automatically expand when they are exhausted, but we don't really want that to happen normally. Ideally, the pools should be fully allocated to their maximum sizes at start-up so there aren't any surprises later when certain feature combinations cause the system to run out of memory in the field. If we allocate everything we think is needed up-front, then we are much more likely to uncover any memory shortages during testing, before it's in the field.

Choosing the right size for your pools correctly at start-up is easy to do if there is a maximum number of fixed, external things that are being represented by the objects being allocated from the pool. If the pool holds "call objects" representing phone calls over a T1 carrier that will never carry more than 24 calls at a time, then it's obvious that you need to size your call object pool at 24.

Other times, it's not so easy to choose the pool size like code to be reused in different products or different configurations that have different needs. In those cases, you still have a few options:

At start-up, query the operating environment and base the pool sizes.
Read a configuration setting from a file or other configuration data source.
Use a build-time configuration setting.

The build-time configuration setting is the easiest, and generally requires less interaction between components at start-up simplifying APIs and reducing boot times.

If the pool size must be determined at start-up, use le_mem_ExpandPool(). Perhaps there's a service-provider module designed to allocate objects on behalf of client. It can have multiple clients at the same time, but it doesn't know how many clients or what their resource needs will be until the clients register with it at start-up. We'd want those clients to be as decoupled from each other as possible (i.e., we want the clients know as little as possible about each other); we don't want the clients to get together and add up all their needs before telling the service-provider. We'd rather have the clients independently report their own needs to the service-provider. Also, we don't want each client to have to wait for all the other clients to report their needs before starting to use the services offered by the service-provider. That would add more complexity to the interactions between the clients and the service-provider.

This is what should happen when the service-provider can't wait for all clients to report their needs before creating the pool:

When the service-provider starts up, it creates an empty pool.
Whenever a client registers itself with the service-provider, the client can tell the service-provider what its specific needs are, and the service-provider can expand its object pool accordingly.
Since registrations happen at start-up, pool expansion occurs at start-up, and testing will likely find any pool sizing before going into the field.

Where clients dynamically start and stop during runtime in response to external events (e.g., when someone is using the device's Web UI), we still have a problem because we can't shrink pools or delete pools when clients go away. This is where Sub-Pools is useful.

Sub-Pools

Essentially, a Sub-Pool is a memory pool that gets its blocks from another pool (the super-pool). Sub Pools can be deleted, causing its blocks to be released back into the super-pool.

This is useful when a service-provider module needs to handle clients that dynamically pop into existence and later disappear again. When a client attaches to the service and says it will probably need a maximum of X of the service-provider's resources, the service provider can set aside that many of those resources in a sub-pool for that client. If that client goes over its limit, the sub-pool will log a warning message.

The problem of sizing the super-pool correctly at start-up still exists, so what's the point of having a sub-pool, when all of the resources could just be allocated from the super-pool?

The benefit is really gained in troubleshooting. If client A, B, C, D and E are all behaving nicely, but client F is leaking resources, the sub-pool created on behalf of client F will start warning about the memory leak; time won't have to be wasted looking at clients A through E to rule them out.

To create a sub-pool, call le_mem_CreateSubPool(). It takes a reference to the super-pool and the objects specified to the sub-pool, and it returns a reference to the new sub-pool.

To delete a sub-pool, call le_mem_DeleteSubPool(). Do not try to use it to delete a pool that was created using le_mem_CreatePool(). It's only for sub-pools created using le_mem_CreateSubPool(). Also, it's not okay to delete a sub-pool while there are still blocks allocated from it. You'll see errors in your logs if you do that.

Sub-Pools automatically inherit their parent's destructor function.

Note: You can't create sub-pools of sub-pools (i.e., sub-pools that get their blocks from another sub-pool).

Copyright (C) Sierra Wireless Inc. Use of this work is subject to license.