fIfO Malloc

Simplified Memory Allocator

IOMalloc is not a general Memory Allocator. IOMalloc strictly postulate that memory chunks are freed in the same ordering as they are allocated.

s1 = iomalloc(1); s2 = iomalloc(1); iofree(s1), iofree(s2); (Pseudocode)

Thus IOMalloc works just like a queue. It is a space efficient container that manage one larger chunk of memory and provide an API to get smaller chunks thereof. Currently IOMalloc use malloc to get a large chunk of memory from the system. But you can replace this code simple by dropping malloc and use a static memory area or use sbrk/mmap directly.

Queue API

IOMalloc is designed to work as a queue. The API therefore provides function to place data directly on the new allocated memory chunk. No need to allocate first and memcpy later. The same rule apply later if data is dequeued (called shift, similar to Perl's list). The shift function is called and memcpy'd to the provided area.

Push Modes

API

Initialize Allocator

Allocate a 1024 byte chunk from main memory (via glibc malloc - sbrk, mmap, this can be changed). This specify the upper usable memory limit for the allocator. The largest usable chunk is 1022 byte, not 1024 byte because of encoding overhead (each chunk consume additional 2 byte for encoding, 2 chunks 4 byte and so on).

The second parameter is a pointer to a struct iom_buffer. This data structure is the allocator context. The third argument - flags - is for fine tuning the allocator and has currently no functionality.

int ret, flags = 0;
struct iom_buffer *iomb;
ret = iom_init(1024, &iomb, flags);
if (ret) {
        fputs("Cannot allocate iom_buffer\n", stderr);
        return EXIT_FAILURE;
}

Size and Power of Two

The size argument must be a power of two because of CPU efficiency (we get rid of modulo operations). A helper function is provided to calculate the nearest power of two for a given integer: iom_nearest_power_two().

Flags

If the queue is mainly filled with one data chunk you can pass flag IOM_MAINLY_EMPTY. This do some pointer reseting to compress the management data segment of the allocator and the first data chunk. You will probably save one memory access cycle.

Allocate Memory and add Data

ret = iom_push(iomb, "1000", strlen("1000"), 0);
if (ret) {
        fprintf(stderr, "Failed to push buffer (%d)\n", ret);
        return EXIT_FAILURE;
}

Get data and mark chunk as free

int ret, rbuf_len;
unsigned char rbuf[2048];

ret = iom_shift(iom_buffer, rbuf, &rbuf_len, sizeof(rbuf));
if (ret) {
        fprintf(stderr, "Failed to get buffer (%d)\n", ret);
        return EXIT_FAILURE;
}

Allocator Destructor

iom_free(iom_buffer);

Doug Lea Malloc - dlmalloc

Doug Lea's malloc implementation is one of the most famous. Nearly all actual allocators are derived from dlmalloc. A Memory Allocator

Cicular Buffer

Key Features

Memory Layout

Space Efficient

No Memory Framentation happends due to the requirement to allocate and free memory in a strict FIFO ordering. The only component that allocate memory beside the actual chunk is the encoding cookie. The encoder cookie consume 16 bit in size. This leads to the maximum continues chunk: 65536 byte - 2 byte. The two byte for encoding.

The code is currently so structured that it is possible to encode smaller chunks in only 1 byte (e.g. chunks smaller then 128 byte). The code is already prepared to allow this encoding. As a secret: this encoding is partly finished in another experimental tree. ;-)

Optimized for Common Operations

CPU Efficient

Code is optimized to do thing fast. One major constraint: the size of the buffer must be a power of two:

This restriction allow some code optimization. Mainly to avoid CPU intensive modulo operation. If this is no issue and memory constraints require rather a exact memory size specification the the code can be un-optimized (ie. use modulo operation).

Memory Footprint

text	   data	    bss	    dec	    hex	filename
1794	      0	      0	   1794	    702	iomalloc.o

Determinstic

Memory allocator suffers from fragmentation. In the worst case memory is fragmented and allocation will fail if no contiguous chunk can be reclaimed.

Download and Development

Download

Development version (similar to stable):

iomalloc.tar.gz

Development

Send patches if you have extensions or bugs. Please base your work on the current master branch:

git clone http://git.jauu.net/iomalloc.git