libarena: Custom Memory Allocator Interface

description

libarena is a custom memory allocator interface and implementation. Four allocators are provided: flat LIFO arena allocator, object pool allocator and two malloc(3) wrappers: one which returns the pointers unadulterated and one which obeys the requested, arbitrary alignment. These can be used directly, or through their exported prototype interfaces.

libarena is meant to provide a baseline interface so allocator's can be stacked, and to provide a simple and well defined interface for libraries and applications without becoming mired in features or capabilities. It is not meant to restrict or confine what custom allocators can actually accomplish. For instance, the included pool and arena allocators include a suite of string utilities which aren't available in the generic exportable interface. Note that these string utilities are built upon a generic interface (see util.h) which can take the prototypical allocation context, so they are also available to any 3rd party compatible allocators.

Surprisingly few malloc(3) library "replacements" or plug-in interfaces support a context pointer argument. They're useless for many or most of the tasks where the ability to specify an alternate malloc(3) could actually be useful, e.g. poor man's RAII. For network daemons especially this feature is useful; all allocations for a particular session can be freed simply by closing the lowest-level allocator object. For counter examples, see talloc, nedmalloc and lua.

For the C pedants, the alignment arguments in the interface circumvent the fact that it's technically impossible to derive the native system alignment in a portable manner. However, being able to pass the alignment has the side effect of allowing one to compact string allocations (using an alignment of `1'). Some BSD's, for instance, align on 16 byte boundaries, which could almost double memory requirements in scenararios where many short strings are allocated. Passing an alignment of `0' to the provided arena or pool allocator will align on 8 byte boundaries. This is the default for ptmalloc, the GNU libc allocator. A macro is provided in util.h--arena_alignof()--which can portably determine a safe alignment (though not necessarily the smallest). Unlike the common C compiler extension typeof operator, it will not work if passed bare objects, only explicit types or the result of the typeof operator.

The arena allocator behaves similarly to GNU obstacks. If allocations are freed in reverse order than the underlying buffers will be freed accordingly; out-of-order deallocations will lead to fragmentation. The arena allocator also supports position marking. The state at any given instance can be stored and the allocator later reset to that state. All allocations which occured after, in time, the saved state will behave as-if they were explicitly deallocated.

The pool allocator keeps a pool of sets of fixed sized buffers. Each buffer size can be arbitrary. Allocations which cannot be met from the existing buckets will result in the creation of a new bucket. Memory returned to the pool will be reused. Currently the pool will never shrink, only grow.

Upon closing of the arena or pool allocator objects all memory used will be released back to their underlying allocator (either the one passed on instantiation, or by default `ARENA_STDLIB', the standard library wrapper.

todo

Valgrind integration so the included allocators don't subvert Valgrind's overflow checking capabilities.

news

2014-01-20

(0.3.7) Fix performance degradation with pool_realloc() when repeatedly growing a buffer which doesn't fit into any of the preallocated bucket sizes. Fix off-by-one read when copying data to new block. And use the correct computed bucket size when a realloc request specifies a stricter alignment.

Tagged rel-0.3.7 (07d292bb73e035997d3a0768234966778ba8a899).

2013-06-13

(0.3.6) Synchronize the debian package version with the Git release versions. Tagged rel-0.3.6 (e8d337a09ef12be4df9ff028d3ce70ac827cff2f).

2013-06-13

Fix debian package template bug which excluded the libarena.so symlink, preventing applications from linking against the dynamic library.

2013-03-13

Fix libtool invocation, and remove unused variable to silence compilers.

2012-09-12

(0.3.5) Apply Jeffrey Johnson's patch to remove expressions with side effects from assert statements, and tag rel-0.3.5.

2007-06-05

(0.3.4) Add Debian build rules, and fix install glitch which failed to copy align.h into the destination include directory.

2007-06-05

(0.3.3) Non-recursive make nirvana. Included Makefiles should work identically with both GNU Make and BSD [p]make.

2007-05-03

(0.3.2) Sequential reallocations which grow beyond the default block length pathologically fragments an arena. When an arena malloc request exceeds the block length, allocate a block 2x the request size to keep apace of the usage demands.

2006-06-12

Release 0.3.1 fixes a critical offset bug in pool_realloc(). The previous data was copied to the base pointer--where the bookkeeping info is kept--and not to the offset, which is returned to the caller.

2006-06-08

Version 0.3 fixes bugs where some free() and realloc() routines did not handle NULL pointer arguments properly, GNU Make target string substitution issue with paths that contained the string "/src", and changes ARENA_STDLIB to return unadorned pointers. ARENA_STDLIB_ALIGNED will give the old behavior of aligning system pointers according to the requested boundary.

2006-04-09

Released version 0.2 with some restructing of the installed headers. Source files moved into subdirectories.

This project is now being used with libevnet.

2006-03-04

Rolled version 0.1. Includes the first regression test. Hopefully not the last.

Includes a new Makefile which uses a non-recursive mode Rules.mk. This allows libarena to be easily included with libmime and liblookup (their top-level Makefile just sources libarena/Rules.mk). For better or worse, GNU Make is required to build as-is. Feel free to submit a different rules file for another platform.

license

Copyright (c) 2006, 2007 William Ahern

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

usage

Example usage can be found in the regress directory.

The library is underpinned by the core allocator interface specification as defined by the structure `arena_prototype'.

/*
* Generic memory allocator interface.
*
* .malloc
*     USAGE
*         malloc(<context>, <size>, <alignment>)
*
*     DESCRIPION
*         Allocates at least <size> bytes of memory, starting from
*         <alignment> boundary.
*
*     RETURN VALUE
*         Returns a pointer to the allocated memory on success, or a
*         NULL pointer on failure.
*
* .realloc
*     USAGE
*         realloc(<context>, <pointer>, <size>, <alignment>)
*
*     DESCRIPTION
*         Allocates a region of memory consisting of at least <size>
*         bytes with the same values as the previously allocated
*         region (up to the length of the lesser of the new and old
*         sizes) and aligned on an <alignment> byte boundary.
*
*     RETURN VALUE
*         Returns a pointer to the allocated region on success, or a
*         NULL pointer on failure. On success use of <pointer> is
*         undefined, on failure the region named by <pointer> remains
*         unchanged.
*
* .free
*     USAGE
*         free(<context>, <pointer>)
*
*     DESCRIPTION
*         Attempt to release all resources associated with the memory
*         region described by <pointer>.
*
*     RETURN VALUE
*         None.
*
* .instanceof
*     USAGE
*         instanceof(<context>)
*
*     DESCRIPTION
*         Returns a C string pointer which can be used by an allocator
*         specific interface or in an allocator specific manner to
*         uniquely determine the constructor of the arena instance.
*         The pointer value, and not the contents of the C string,
*         identifies the instance. The C string can be used in
*         debugging output, etc., to describe the allocation strategy
*         and/or mechanism of the instance.
*
*     RETURN VALUE
*         Returns a non-NULL, distinct pointer. However, there is no
*         guarantee any known allocator will be positively
*         identifiable.
*
* .strerror
*     USAGE
*         strerror(<context>)
*
*     DESCRIPTION
*         Provides a descriptive string describing the last known
*         error encountered.
*
*     RETURN VALUE
*         Immutable string describing last error, or ARENA_NOERROR if
*         no known error has occured.
*
* .clearerr
*     USAGE
*         clearerr(<context>)
*
*     DESCRIPTION
*         Erase all previous error conditions.
*
*     RETURN VALUE
*         None.
*/
typedef struct arena_prototype {
    void *(*malloc)(const struct arena_prototype *, size_t, size_t);

    void *(*realloc)(const struct arena_prototype *, void *, size_t, size_t);

    void (*free)(const struct arena_prototype *, void *);

    const char *(*instanceof)(const struct arena_prototype *);

    const char *(*strerror)(const struct arena_prototype *);

    void (*clearerr)(const struct arena_prototype *);
};

download

Download the latest 0.3.7 tarball.

Download the previous 0.3.6 tarball.

Download the previous 0.3.5 tarball.

Download the previous 0.3.4 tarball.

source

git clone http://25thandClement.com/~william/projects/libarena.git

other projects

airctl | bsdauth | cnippets | libmime | libarena | libevnet | authldap | streamlocal | libnostd | zoned | dns.c | delegate.c | llrb.h | lpegk | json.c | cqueues | siphash.h | hexdump.c | timeout.c | luapath | luaossl | lunix | phf | AnonNet