whalloc  whalloc_pager

The "Pager" API

Files: whalloc_pager.h, whalloc_pager.c

Contained in whalloc_pager.h is an allocator API which works much differently than the other memory pools. The pager manages only de/allocation of individual objects of a given size, and is intended for applications where a specific (usually small) type must be instantiated very often. This mechanism builds in the recycling of allocated objects as they are freed. It can use the standard allocators or a custom allocator (such as one of the memory pool classes) for allocation of its memory. It supports two levels of abstraction: individual pages or a "book" of pages (a higher-level abstraction which manages the addition of new pages as needed).

Example:

const uint16_t objectsPerPage = 20;
const uint16_t objectSize = sizeof(MyType);
whalloc_book * b = whalloc_book_open( objectsPerPage, objectSize,
				      NULL, NULL, NULL, NULL );

MyType * my = (MyType*) whalloc_book_alloc( b );
/* ^^^^ semantically equivalent to malloc(objectSize). */
... use my ...
whalloc_book_free( b, my ); /* no ironic pun intended */
/* ^^^^ semantically equivalent to free(my). */
whalloc_book_close( b ); // frees b and any opened pages.

The "book" class manages an arbitrary number of "pages" (as a linked list). Each page allocates space for a set amount of objects (above: objectsPerPage) of a set size (above: objectSize). (All pages in a book have the same sizing parameters.) As a book fills up, it dynamically adds pages, but it never allocates new pages while any page has a free memory chunk. As objects are deallocated page entries are marked as free. (During de/allocation it also re-arranges its page list to try to ensure fast allocation.) By default a book does not discard empty pages (those for which all allocations have been freed by the client), but whalloc_book_vacuum(bookObject) can be used to remove (and deallocate) any pages which are empty (i.e. are not hosting any client-allocated objects).

The NULL arguments to the initialization function can be used to set up custom de/allocators for the book and its memory pages. This can be used together with the other whalloc allocators to allow the paging API to use, e.g. stack-allocated memory, for its storage.

Using together with whalloc_bt

The page-based manager can be used together with whalloc_bt in order to use client-supplied memory for the pool. (Note that the whalloc_ht allocator does not directly support a realloc-compliant operation, which is required for this feature.)

/* Custom allocator function. Assumes that allocState is-a
   whalloc_bt object.
*/
static void * my_realloc( void * mem, unsigned int n, void * allocState )
{
    whalloc_bt * bt = (whalloc_bt *)allocState;
    return whalloc_bt_realloc( bt, mem, n );
}


// Set up the bt memory pool using a block size optimized for
// storing our page objects:
enum { PoolSize = 1024 * 2 };
static unsigned char pool[PoolSize];
static unsigned int objectPerPage = 10;
static unsigned int objSize = sizeof(MyType);
const uint16_t pageSize = whalloc_page_calc_size( objectPerPage, objSize );
whalloc_bt bt = whalloc_bt_empty;
int rc = 0;
rc = whalloc_bt_init( &bt, pool, PoolSize, pageSize );
if( rc ) { ... pool init failed ... }
// OPTIONAL: tell the bt pool to use malloc()/free() for new allocations
// if it runs out of space:
bt.base.fallback = whalloc_fallback_stdalloc;
// ^^^ Without that, the pool will produce OOM errors if it runs
// out of space. (Maybe that's what you want!)

// Create a paging allocator which is allocated from bt
// and uses bt for future allocations:
whalloc_book * b = whalloc_book_open( objectPerPage, objSize,
                                      my_realloc, &bt,
                                      my_realloc, &bt );
if( ! b ) { ... error! ... }

// Now allocate objects from the pager:
MyType * my = (MyType*) whalloc_book_alloc(b);
// ^^^^ my now lives somewhere inside bt memory pool

... use my, then clean it up: ...
whalloc_book_free( b, my );
// ^^^ semantically equivalent to free()

// Clean up the pager:
whalloc_book_close( b );

// Clean up bt:
whalloc_bt_drain( &bt );

The above example shows a lot of details, and can be simplified a bit. The following example is similar, but also optimizes the stack-allocated pool size for a perfect (or near-perfect) fit:

enum { objsPerPage = 10,
        objSize = sizeof(MyType),
        pageSize = WHALLOC_PAGER_PAGE_CALC_SIZE( objsPerPage, objSize ),
        poolSize = pageSize * 10
    };
int rc = 0;
unsigned char pool[poolSize];
whalloc_bt bt = whalloc_bt_empty;
whalloc_pager_book * b = NULL;
rc = whalloc_bt_init( &bt, pool, PoolSize, pageSize );
if( rc ) { ... error ... }
b = whalloc_book_from_bt( &bt, objsPerPage, objSize );

Note that cleaning up the pager and bt object in this case is not strictly necessary unless we used the optional "fallback" allocator noted above. If we use the fallback allocator then we need to clean up to be certain that we also clean up allocations made via the fallback allocator. If we don't use the fallback allocator then the memory doesn't need releasing because it is stack allocated (and the memory pool won't allocate more than that if it has no fallback allocator).

As you may have deduced from the code, this approach allows the pager to operate without using malloc() and friends, assuming the underlying memory pool is large enough. Optimizing the pool's block size to match the allocation size of a book's pages ensures optimal de/allocation speed and memory utilization within the pool.