#+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, destroy 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_destroy=.

  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_destroy= ::

  Free all data in a =Pool= structure, along with the structure itself. After a
  pool is destroyed, 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=.

* Thread safety

The library can be optionally compiled with multithreading support, allowing the
user to perform operations on the pool (allocations, frees, expansions) from
different threads. To enable thread safety, compile the library with
=LIBPOOL_THREAD_SAFE= defined.

Furthermore, if =LIBPOOL_NO_STDLIB= is defined, the user is responsible for
assigning 4 function pointers:

- =pool_ext_mutex_new=, which should return a pointer to a unspecified mutex type,
  which will be used by the other multithreading functions from within each
  pool.
- =pool_ext_mutex_destroy=, which should destroy (deinitialize, free, etc.) a
  mutex pointer, previously allocated through =pool_ext_mutex_new=.
- =pool_ext_mutex_lock=, which should receive a mutex pointer and lock it to the
  current thread.
- =pool_ext_mutex_unlock=, which should receive a previously-locked mutex pointer
  and unlock it, so that other threads can lock it.

* 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.