#+TITLE: libpool #+AUTHOR: 8dcc #+OPTIONS: toc:nil #+STARTUP: showeverything

Tiny (ANSI) C library for pool allocation.

This library implements a very simple [[https://en.wikipedia.org/wiki/Memory_pool][pool allocator]] in ANSI C. This library was originally inspired by [[http://dmitrysoshnikov.com/compilers/writing-a-pool-allocator/][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 [[https://8dcc.github.io/programming/pool-allocator.html][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 [[file:src/libpool.c][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 [[file:src/libpool-test.c][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 [[https://valgrind.org/][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.

• Alignment

By default, when initializing a new pool with =pool_new=, the chunk sizes will be internally aligned to the size of a =void*=, so that all pointers returned by =pool_alloc= are also aligned.

In some specific cases, this can lead to unexpected pool sizes, so this behavior can be disabled at compile-time by defining =LIBPOOL_NO_ALIGNMENT=.

However, note that, when compiling the library with alignment disabled, the =pool_new= function will expect a chunk size greater or equal to the size of a =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*)=, the function will return =NULL=.

• Building the example

Clone the repository and build the project using =make=.

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

...

#+end_src

Then, run =libpool-test.out=.

#+begin_src bash ./libpool-test.out

...

#+end_src

• Benchmarking against =malloc=

You can benchmark the library by running =make benchmark=.

#+begin_src bash make benchmark

...

Benchmarking [10000..100000] allocations of 10000 bytes. Ignoring first 100000 calls.

...

Logging finished, plotting to 'benchmark.svg'...

All done

#+end_src

These are the results in my machine:

[[file:assets/benchmark_logarithmic.svg]]

Without using a logarithmic scale in the Y axis:

[[file:assets/benchmark.svg]]

You can adjust these values in the [[file:benchmark.sh][benchmark.sh]] script.