libpool

Tiny (ANSI) C library for pool allocation.

This library implements a very simple pool allocator in ANSI C. This library was originally inspired by Dmitry Soshnikov’s article.

Below is a simple explanation of how the allocator works, but more details about a sample implementation can be found in the article on my blog.

Similarly to malloc, a pool allocator allows the user to allocate memory at run time. The pool allocator, however, is much faster than malloc, at the cost of having a fixed pool size. It allows the user to allocate and free memory blocks (referred to as chunks, from now on) in O(1) linear time.

The code of the allocator is heavily commented, so it should be easy to understand how everything works, and why it is so efficient.

This library uses very little memory: When calling pool_new (described below), a very small Pool structure is allocated, along with the pool itself. Free chunks are used to store information, so the memory impact is minimal.

The library doesn’t have any dependencies, not even to the standard C library (as long as it’s compiled with LIBPOOL_NO_STDLIB defined). For more information, see the Usage section below.

Usage

If you want to use this library, simply copy the detour source and headers to your project, include the libpool.h header in your source files and compile the libpool.c source along with the rest of your code.

The library doesn’t depend on any specific allocation method; it uses two function pointers, pool_ext_alloc and pool_ext_free (which by default point to malloc and free) for allocating the Pool structures and the pools themselves. The libpool.c source can be compiled with LIBPOOL_NO_STDLIB defined, and these pointers won’t be initialized. It’s up to the user to specify a valid function for allocating and freeing memory.

This is the basic process for using this allocator, using the functions described below:

1. Create a new pool, specifying the number of elements and the size of each element.
2. Allocate necessary chunks from the pool, and use them.
3. When a chunk is no longer needed, free it so it can be used by subsequent allocations.
4. Optionally expand the pool, if you run out of chunks.
5. When the pool itself is no longer needed, close it.

For a full example, see src/libpool-test.c.

Functions

This library consists of only 5 functions:

Function: pool_new

Allocate and initialize a new Pool structure, with the specified number of chunks, each with the specified size. If the initialization fails, NULL is returned.

This function will allocate a Pool structure, along with the array of chunks used for later allocations. The caller must free the returned pointer using pool_close.

Note that the chunk_sz argument must be greater or equal than sizeof(void*). For more information, see the Caveats section.

Function: pool_expand

Expand the specified pool, adding extra_sz free chunks.

On success, it returns true; otherwise, it returns false and leaves the pool unchanged.

Function: pool_close

Free all data in a Pool structure, along with the structure itself. After a pool is closed, all data previously allocated from that pool (with pool_alloc) becomes unusable.

Allows NULL as the argument.

Function: pool_alloc

Allocate a fixed-size chunk from the specified pool. If no chunks are available, NULL is returned.

Function: pool_free

Free a fixed-size chunk from the specified pool. Allows NULL as both pool and ptr arguments.

Valgrind support

This library has support for the valgrind framework, unless it has been compiled with the LIBPOOL_NO_VALGRIND macro defined. Among other things, this allows the programmer to check for memory leaks and invalid memory accesses in his program with the valgrind tool, just like it would with a program that uses malloc. Note that the valgrind macros don’t affect the behavior of the program when it’s not running under valgrind.

For example, after compiling the test program with valgrind disabled (i.e. with LIBPOOL_NO_VALGRIND defined), if we run valgrind ./libpool-test.out we will see 9 allocations, corresponding to the malloc calls. However, if we enable valgrind support, we will see 111 allocations because it also checked the calls to pool_alloc and pool_free.

You might need to install some valgrind-devel package in your system in order to include the necessary headers.

Building the example

Clone the repository and build the project using make.

git clone https://github.com/8dcc/libpool
cd libpool
make
# ...

Then, run libpool-test.out.

./libpool-test.out
# ...

Benchmarking against malloc

You can benchmark the library by running make benchmark. These are the results in my machine:

make benchmark
# ...
Benchmarking 1100000 allocations of 10000 bytes. Ignoring first 100000 calls.
Time when using 'malloc'....: 2.46 - 0.22 = 2.24 seconds
Time when using 'libpool'...: 0.81 - 0.06 = 0.75 seconds

You can adjust these values in the benchmark.sh script.

Caveats

When creating a new pool, each element needs to be greater or equal to the size of void*. This is necessary because the implementation uses free chunks to build a linked list, which is what makes the library so efficient. If the chunk_sz parameter of pool_new is smaller than sizeof(void*), it will return NULL.