src/lib/mempool-alloconly.c

	mempool-alloconly.c revision e4af52c1ff7edb2bdecc3b99520cbf062db3e6af
bcb4e51a409d94ae670de96afb8483a4f7855294Stephan Bosch/*
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen mempool-alloconly.c : Memory pool for fast allocation of memory without
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen                       need to free it in small blocks
0536ccb51d41e3078c3a9fa33e509fb4b2420f95Timo Sirainen
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen    Copyright (c) 2002 Timo Sirainen
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen
252db51b6c0a605163326b3ea5d09e9936ca3b29Timo Sirainen    Permission is hereby granted, free of charge, to any person obtaining
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen    a copy of this software and associated documentation files (the
9511a40d933181045343110c8101b75887062aaeTimo Sirainen    "Software"), to deal in the Software without restriction, including
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen    without limitation the rights to use, copy, modify, merge, publish,
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen    distribute, sublicense, and/or sell copies of the Software, and to
4aa7fe81503a20bc972ae625da4dd9e6996fbdbfTimo Sirainen    permit persons to whom the Software is furnished to do so, subject to
4aa7fe81503a20bc972ae625da4dd9e6996fbdbfTimo Sirainen    the following conditions:
4aa7fe81503a20bc972ae625da4dd9e6996fbdbfTimo Sirainen
4aa7fe81503a20bc972ae625da4dd9e6996fbdbfTimo Sirainen    The above copyright notice and this permission notice shall be
4aa7fe81503a20bc972ae625da4dd9e6996fbdbfTimo Sirainen    included in all copies or substantial portions of the Software.
4aa7fe81503a20bc972ae625da4dd9e6996fbdbfTimo Sirainen
4aa7fe81503a20bc972ae625da4dd9e6996fbdbfTimo Sirainen    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
4aa7fe81503a20bc972ae625da4dd9e6996fbdbfTimo Sirainen    OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
4aa7fe81503a20bc972ae625da4dd9e6996fbdbfTimo Sirainen    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
4aa7fe81503a20bc972ae625da4dd9e6996fbdbfTimo Sirainen    IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
4aa7fe81503a20bc972ae625da4dd9e6996fbdbfTimo Sirainen    CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
4aa7fe81503a20bc972ae625da4dd9e6996fbdbfTimo Sirainen    TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
4aa7fe81503a20bc972ae625da4dd9e6996fbdbfTimo Sirainen    SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
4aa7fe81503a20bc972ae625da4dd9e6996fbdbfTimo Sirainen*/
a94936bafd127680184da114c6a177b37ff656e5Timo Sirainen
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen#include "lib.h"
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen#include "mempool.h"
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen#include <stdlib.h>
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen#define MAX_ALLOC_SIZE SSIZE_T_MAX
3f8303bae0f70df6db9337ad1d1476d290f9b1a3Timo Sirainen
3f8303bae0f70df6db9337ad1d1476d290f9b1a3Timo Sirainentypedef struct _PoolBlock PoolBlock;
3f8303bae0f70df6db9337ad1d1476d290f9b1a3Timo Sirainen
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainentypedef struct {
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen    struct Pool pool;
859cc94211b759825db5e15b0c88754da902ca14Timo Sirainen    int refcount;
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen
859cc94211b759825db5e15b0c88754da902ca14Timo Sirainen    PoolBlock *block;
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen    size_t last_alloc_size;
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen    char name[MEM_ALIGN_SIZE]; /* variable size */
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen} AlloconlyPool;
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen#define SIZEOF_ALLOCONLYPOOL (sizeof(AlloconlyPool)-MEM_ALIGN_SIZE)
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainenstruct _PoolBlock {
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen    PoolBlock *prev;
bcd286622779a93f809b11993db0550f8c7cc9b5Timo Sirainen
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen    size_t size;
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen    size_t left;
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen    /* unsigned char data[]; */
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen};
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen#define SIZEOF_POOLBLOCK (MEM_ALIGN(sizeof(PoolBlock)))
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen#define POOL_BLOCK_DATA(block) \
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen    ((char *) (block) + SIZEOF_POOLBLOCK)
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainentypedef struct {
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen    union {
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen        size_t size;
1117aa7adc2909c750031fd7551a58a486d100d8Timo Sirainen        unsigned char alignment[MEM_ALIGN_SIZE];
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen    } size;
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen    unsigned char data[MEM_ALIGN_SIZE]; /* variable size */
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen} PoolAlloc;
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen#define SIZEOF_POOLALLOC (sizeof(PoolAlloc)-MEM_ALIGN_SIZE)
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainen
8887a9bb6d2e3f664cf741b763643a0e5610fa4dTimo Sirainenstatic void pool_alloconly_ref(Pool pool);
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainenstatic void pool_alloconly_unref(Pool pool);
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainenstatic void *pool_alloconly_malloc(Pool pool, size_t size);
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainenstatic void pool_alloconly_free(Pool pool, void *mem);
01f4ee4a0243f3fe9af763e1a540cd5cff0d63f5Timo Sirainenstatic void *pool_alloconly_realloc(Pool pool, void *mem, size_t size);
a94936bafd127680184da114c6a177b37ff656e5Timo Sirainenstatic void *pool_alloconly_realloc_min(Pool pool, void *mem, size_t size);
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainenstatic void pool_alloconly_clear(Pool pool);
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen
07e4875d250e7a7157cd99132aafc773cf3cdf83Timo Sirainenstatic void block_alloc(AlloconlyPool *pool, size_t size);
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen
2c0f1cb7a0564d48ec43c7315ea46ea38d2abd19Timo Sirainenstatic struct Pool static_alloconly_pool = {
2c0f1cb7a0564d48ec43c7315ea46ea38d2abd19Timo Sirainen    pool_alloconly_ref,
01f4ee4a0243f3fe9af763e1a540cd5cff0d63f5Timo Sirainen    pool_alloconly_unref,
2c0f1cb7a0564d48ec43c7315ea46ea38d2abd19Timo Sirainen
07e4875d250e7a7157cd99132aafc773cf3cdf83Timo Sirainen    pool_alloconly_malloc,
07e4875d250e7a7157cd99132aafc773cf3cdf83Timo Sirainen    pool_alloconly_free,
07e4875d250e7a7157cd99132aafc773cf3cdf83Timo Sirainen
07e4875d250e7a7157cd99132aafc773cf3cdf83Timo Sirainen    pool_alloconly_realloc,
01f4ee4a0243f3fe9af763e1a540cd5cff0d63f5Timo Sirainen    pool_alloconly_realloc_min,
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen    pool_alloconly_clear
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen};
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen
4b9f99761df5014c659cd87fddaf6854af428cfcTimo SirainenPool pool_alloconly_create(const char *name, size_t size)
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen{
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen    AlloconlyPool *apool;
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen    int len;
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen    len = strlen(name);
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen    apool = calloc(SIZEOF_ALLOCONLYPOOL + len+1, 1);
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen    if (apool == NULL)
01f4ee4a0243f3fe9af763e1a540cd5cff0d63f5Timo Sirainen        i_panic("pool_alloconly_create(): Out of memory");
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen    apool->pool = static_alloconly_pool;
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen    apool->refcount = 1;
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen    block_alloc(apool, size);
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen    strcpy(apool->name, name);
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen    return (Pool) apool;
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen}
10c96a244935de4add8213ba0b894178dfb889a5Timo Sirainen
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainenstatic void pool_alloconly_destroy(AlloconlyPool *apool)
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen{
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen    /* destroy all but the last block */
fe363b433b8038a69b55169da9dca27892ad7d18Timo Sirainen    pool_alloconly_clear(&apool->pool);
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen
597dba3488c648ffb375ee4a552bd52ac4346979Timo Sirainen    /* destroy the last block */
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen    free(apool->block);
4aa7fe81503a20bc972ae625da4dd9e6996fbdbfTimo Sirainen    free(apool);
a94936bafd127680184da114c6a177b37ff656e5Timo Sirainen}
a94936bafd127680184da114c6a177b37ff656e5Timo Sirainen
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainenstatic void pool_alloconly_ref(Pool pool)
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen{
da2aa032ccfa8e7e4a4380ef738014549f4d2c2dTimo Sirainen    AlloconlyPool *apool = (AlloconlyPool *) pool;
c06f4017027263cf3a08becc551f5126409e2a83Timo Sirainen
411d6baa37f31d90730e90c4a28c43e1974bbe58Timo Sirainen    apool->refcount++;
9511a40d933181045343110c8101b75887062aaeTimo Sirainen}
2974dca6be5120e49279f06c8aa952e5fac56048Timo Sirainen
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainenstatic void pool_alloconly_unref(Pool pool)
bdcb00145ad87765e3fd22d4ebc4d2c029a326b9Timo Sirainen{
bdcb00145ad87765e3fd22d4ebc4d2c029a326b9Timo Sirainen    AlloconlyPool *apool = (AlloconlyPool *) pool;
bdcb00145ad87765e3fd22d4ebc4d2c029a326b9Timo Sirainen
bdcb00145ad87765e3fd22d4ebc4d2c029a326b9Timo Sirainen    if (--apool->refcount == 0)
bdcb00145ad87765e3fd22d4ebc4d2c029a326b9Timo Sirainen        pool_alloconly_destroy(apool);
bdcb00145ad87765e3fd22d4ebc4d2c029a326b9Timo Sirainen}
bdcb00145ad87765e3fd22d4ebc4d2c029a326b9Timo Sirainen
bdcb00145ad87765e3fd22d4ebc4d2c029a326b9Timo Sirainenstatic void block_alloc(AlloconlyPool *apool, size_t size)
bdcb00145ad87765e3fd22d4ebc4d2c029a326b9Timo Sirainen{
bdcb00145ad87765e3fd22d4ebc4d2c029a326b9Timo Sirainen    PoolBlock *block;
bdcb00145ad87765e3fd22d4ebc4d2c029a326b9Timo Sirainen
bdcb00145ad87765e3fd22d4ebc4d2c029a326b9Timo Sirainen    /* each block is at least twice the size of the previous one */
    if (apool->block != NULL)
        size += apool->block->size;

    if (size <= SIZEOF_POOLBLOCK)
        size += SIZEOF_POOLBLOCK;
    size = nearest_power(size);

    block = calloc(size, 1);
    if (block == NULL)
        i_panic("block_alloc(): Out of memory");
    block->prev = apool->block;
    apool->block = block;

    block->size = size - SIZEOF_POOLBLOCK;
    block->left = block->size;
}

static void *pool_alloconly_malloc(Pool pool, size_t size)
{
    AlloconlyPool *apool = (AlloconlyPool *) pool;
    PoolAlloc *alloc;

    size = MEM_ALIGN(size);

    if (apool->block->left < size + SIZEOF_POOLALLOC) {
        /* we need a new block */
        block_alloc(apool, size);
    }

    alloc = (PoolAlloc *) (POOL_BLOCK_DATA(apool->block) +
                   apool->block->size - apool->block->left);
    alloc->size.size = size;

    apool->block->left -= size + SIZEOF_POOLALLOC;
    apool->last_alloc_size = size;
    return alloc->data;
}

static void pool_alloconly_free(Pool pool __attr_unused__,
                void *mem __attr_unused__)
{
    /* ignore */
}

static void *pool_alloconly_realloc(Pool pool, void *mem, size_t size)
{
    /* there's no point in shrinking the memory usage,
       so just do the same as realloc_min() */
    return pool_alloconly_realloc_min(pool, mem, size);
}

static int pool_try_grow(AlloconlyPool *apool, void *mem, size_t size)
{
    /* see if we want to grow the memory we allocated last */
    if (POOL_BLOCK_DATA(apool->block) + (apool->block->size -
                         apool->block->left -
                         apool->last_alloc_size) == mem) {
        /* yeah, see if we can grow */
        if (apool->block->left >= size-apool->last_alloc_size) {
            /* just shrink the available size */
            apool->block->left -= size - apool->last_alloc_size;
            apool->last_alloc_size = size;
            return TRUE;
        }
    }

    return FALSE;
}

static void *pool_alloconly_realloc_min(Pool pool, void *mem, size_t size)
{
    AlloconlyPool *apool = (AlloconlyPool *) pool;
    PoolAlloc *alloc;
    unsigned char *new_mem;
    size_t old_size;

    if (mem == NULL) {
        alloc = NULL;
        old_size = 0;
    } else {
        /* get old size */
                alloc = (PoolAlloc *) ((char *) mem - SIZEOF_POOLALLOC);
        old_size = alloc->size.size;
    }

    if (old_size >= size)
        return mem;

    size = MEM_ALIGN(size);

    /* see if we can directly grow it */
    if (!pool_try_grow(apool, mem, size)) {
        /* slow way - allocate + copy */
        new_mem = pool_alloconly_malloc(pool, size);
        memcpy(new_mem, mem, old_size);
        mem = new_mem;
    }

    if (size > old_size) {
                /* clear new data */
        memset((char *) mem + old_size, 0, size - old_size);
    }

        return mem;
}

static void pool_alloconly_clear(Pool pool)
{
    AlloconlyPool *apool = (AlloconlyPool *) pool;
    PoolBlock *block;

    /* destroy all blocks but the last, which is the largest */
    while (apool->block->prev != NULL) {
        block = apool->block;
        apool->block = block->prev;

        free(block);
    }

    /* clear the last block */
    memset(POOL_BLOCK_DATA(apool->block), 0,
           apool->block->size - apool->block->left);
    apool->block->left = apool->block->size;

    apool->last_alloc_size = 0;
}