Welcome to libwhalloc

whalloc (the WanderingHorse.net Allocator) is a small C library containing "alternate" memory allocators for C.

This site is a Fossil source repository, containing the source code, a wiki, bug tracker, etc. To be able to download the source code or use most of the hyperlinks, you must click the /login link and log in as "anonymous" with the password shown on the screen. This is to avoid that bots mindlessly waste gigabytes of bandwidth fishing through Fossil's network of hyperlinks, some of which generate a ZIP file of any given version of the whole repository.

Author: Stephan Beal (http://wanderinghorse.net) with input from Amir "Ashran" Mohammadkhani (http://modme.info)

License: Public Domain

Very brief overview:

This C library provides a several independent, but conceptually related, APIs which provide malloc()/free()-like features. The core allocator classes allocate memory from a user-specified memory range. The intention is to give it stack-allocated space, or a pre-malloc()ed block, and it will divide that space and use it for allocation.

This project started out as (and was intended to remain) a single allocator class, but it now has several different allocators, each with their own particular uses and trade-offs.

All of this code is part of my on-going fascination with reducing calls to malloc() in my libraries. More specifically, for libraries/applications where the memory requirements are highly predictable. The include APIs are intended for use cases where avoiding malloc() and friends is, for whatever reason, an important consideration, and for which the memory usage patterns can be predicted with a fair degree of accuracy. That said, memory usage for most applications cannot be well predicted, but sometimes specific parts of applications can get by with well-known amounts of memory. For such cases, this code might just be interesting.

The primary general-purpose allocator class, called whalloc_bt, provides the same features as the C-standard malloc(), free() and realloc(), and is used like this:

// Set up a stack-allocated memory area:
enum { BufLen = 1024 * 8 };
unsigned char buffer[BufLen];
// Set up our allocator/memory pool:
const whalloc_size_t blockSize = sizeof(my_type);
whalloc_bt pool = whalloc_bt_empty;
int rc = whalloc_bt_init(&pool, buffer, BufLen, blockSize );
if( rc ) { ... error ... }
my_type * m = (my_type *) whalloc_bt_alloc(&pool, blockSize );
// ^^^ Semantically equivalent to malloc(blockSize).
// ^^^ m now lives somewhere inside of buffer

// Cleaning up:
whalloc_bt_free( &pool, m );
// ^^^ semantically equivalent to free(m)

Since the memory buffer in the above example is statically allocated, we often don't need to clean up unless we also use our objects need it or we use the so-called fallback allocator option. The fallback option tells the pool to start using malloc() if its own memory runs out. In that case, the corresponding calls to free() will be handled by the pool if the memory passed to it is in the pool's managed range, otherwise it will be passed to free().

Features and Misfeatures

Features:

• Very small. Compiles (on my machine) in about 1/2 of a second.
• Well documented - it has more API docs than many libraries ten times its size do.
• Simplifies testing out-of-memory errors in applications (simply use a memory pool with a small size).
• Some of the test code needs C99, but the core lib compiles fine as C89, and it compiles cleanly in either mode using gcc's -pedantic/-Wall flags.
• Allows certain categories of applications/libraries to run without ever dynamically allocating memory (or doing so much less often).
• Some of the allocators optionally support locking via a client-supplied mutex (see WhallocConcurrency).
• Some of the allocators optionally support a "fallback allocator", which it can use to allocate memory if their own pool fills up (see WhallocFallback).
• An allocator can be as global or local as the client would like it to be. Use one allocator for your whole application or use different allocators in different parts of the application.

Misfeatures:

• Though it is syntactically compatible with C89, it requires a few header files which were first standardized in C99 (stdint.h and inttypes.h). If those are not available, the client will have to hack a small bit to define the required numeric typedefs. (We require the standardized integer types because that is the only portable way to get predictable/guaranteed sizeof() sizes of our primary integer types and structs.)
• The primary focus of most of the code is space-efficient internal management of memory (i.e. the allocators themselves strive to use as little memory as possible). This leads to memory-light code, but some de/re/allocation algorithms suffer linear components because of the lack of higher-order data management structures.

More information...

There are more details on the following pages:

• TableOfContents - The ToC for this site's wiki.
• WhallocBasics - An overview of the library's main properties and types.
• WhallocConfig - Compile-time configuration options.
• WhallocConcurrency - The mutex interface supported by some of the main allocators.
• WhallocFallback - How to provide the allocators with a backup plan if they run out of memory.
• whalloc_bt - the "bit table" allocator.
• whalloc_ht - the "hashtable" allocator.
• whalloc_region - a trivial region allocator.
• whalloc_pager - A page-based allocator which only handles allocations of a specific size.

News!

1 March 2010:

• Added the amalgamation build.

26 Feb 2010:

• Added the pager API, a page-based memory manager.
• Fixed a bug in whalloc_bt which caused it to not consider certain free blocks as free when looking for the next free block.