src/lib/temp-mempool.c

	temp-mempool.c revision a3b6849ec9a7e7cb209d0e330211aed6395daabd
bcb4e51a409d94ae670de96afb8483a4f7855294Stephan Bosch/*
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen temp-mempool.c : Memory pool for temporary memory allocations
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen    Copyright (c) 2001-2002 Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen    Permission is hereby granted, free of charge, to any person obtaining
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen    a copy of this software and associated documentation files (the
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen    "Software"), to deal in the Software without restriction, including
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen    without limitation the rights to use, copy, modify, merge, publish,
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen    distribute, sublicense, and/or sell copies of the Software, and to
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen    permit persons to whom the Software is furnished to do so, subject to
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen    the following conditions:
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen
decdff03c32cb5d0e99d71c5678fd008714de70bTimo Sirainen    The above copyright notice and this permission notice shall be
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen    included in all copies or substantial portions of the Software.
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen    OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen    IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen    CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen    TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen    SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen*/
0d1b8b6bec79746c5d89d57dd8c1688946bd9237Josef 'Jeff' Sipek
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen#include "lib.h"
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen#include "temp-mempool.h"
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen#include <stdlib.h>
038c2831447440bf0bef89b43dd0968afc298abcStephan Bosch
038c2831447440bf0bef89b43dd0968afc298abcStephan Bosch/* #define TEMP_POOL_DISABLE */
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen#ifndef TEMP_POOL_DISABLE
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen/* max. number of bytes to even try to allocate. This is done just to avoid
038c2831447440bf0bef89b43dd0968afc298abcStephan Bosch   allocating less memory than was actually requested because of integer
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen   overflows. */
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen#define MAX_ALLOC_SIZE (UINT_MAX - (MEM_ALIGN_SIZE-1))
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen/* Initial pool size - this should be kept in a size that doesn't exceed
038c2831447440bf0bef89b43dd0968afc298abcStephan Bosch   in a normal use to keep it fast. */
9766afd8dc3976d238e1c71712d6bafa316f2e06Timo Sirainen#define INITIAL_POOL_SIZE (1024*32)
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainentypedef struct _MemBlock MemBlock;
29cda2d6eb57b7fb65a55115ea8bcb6ab6938477Timo Sirainentypedef struct _MemBlockStack MemBlockStack;
29cda2d6eb57b7fb65a55115ea8bcb6ab6938477Timo Sirainen
29cda2d6eb57b7fb65a55115ea8bcb6ab6938477Timo Sirainenstruct _MemBlock {
29cda2d6eb57b7fb65a55115ea8bcb6ab6938477Timo Sirainen	MemBlock *next;
29cda2d6eb57b7fb65a55115ea8bcb6ab6938477Timo Sirainen
29cda2d6eb57b7fb65a55115ea8bcb6ab6938477Timo Sirainen	unsigned int size, left;
29cda2d6eb57b7fb65a55115ea8bcb6ab6938477Timo Sirainen	unsigned char data[1];
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen};
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen/* current_stack contains last t_push()ed blocks. After that new
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen   MemBlockStack is created and it's ->prev is set to current_stack. */
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen#define MEM_LIST_BLOCK_COUNT 16
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainenstruct _MemBlockStack {
038c2831447440bf0bef89b43dd0968afc298abcStephan Bosch	MemBlockStack *prev;
038c2831447440bf0bef89b43dd0968afc298abcStephan Bosch
038c2831447440bf0bef89b43dd0968afc298abcStephan Bosch	MemBlock *block[MEM_LIST_BLOCK_COUNT];
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen        int block_space_used[MEM_LIST_BLOCK_COUNT];
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen};
9766afd8dc3976d238e1c71712d6bafa316f2e06Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainenstatic int stack_pos; /* next free position in current_stack->block[] */
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainenstatic MemBlockStack *current_stack; /* current stack position */
9766afd8dc3976d238e1c71712d6bafa316f2e06Timo Sirainenstatic MemBlockStack *unused_stack_list; /* unused stack blocks */
9766afd8dc3976d238e1c71712d6bafa316f2e06Timo Sirainen
9766afd8dc3976d238e1c71712d6bafa316f2e06Timo Sirainenstatic MemBlock *current_block; /* block currently used for allocation */
9766afd8dc3976d238e1c71712d6bafa316f2e06Timo Sirainenstatic MemBlock *unused_block; /* largest unused block is kept here */
a77d7cc71b6a1d66fa33516582890c2256516c26Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainenstatic int last_alloc_size;
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainenstatic MemBlock *last_buffer_block;
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainenstatic unsigned int last_buffer_size;
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen
29cda2d6eb57b7fb65a55115ea8bcb6ab6938477Timo Sirainenint t_push(void)
29cda2d6eb57b7fb65a55115ea8bcb6ab6938477Timo Sirainen{
29cda2d6eb57b7fb65a55115ea8bcb6ab6938477Timo Sirainen        MemBlockStack *stack;
29cda2d6eb57b7fb65a55115ea8bcb6ab6938477Timo Sirainen
29cda2d6eb57b7fb65a55115ea8bcb6ab6938477Timo Sirainen	if (stack_pos == MEM_LIST_BLOCK_COUNT) {
29cda2d6eb57b7fb65a55115ea8bcb6ab6938477Timo Sirainen		/* stack list full */
29cda2d6eb57b7fb65a55115ea8bcb6ab6938477Timo Sirainen		stack_pos = 0;
29cda2d6eb57b7fb65a55115ea8bcb6ab6938477Timo Sirainen		if (unused_stack_list == NULL) {
29cda2d6eb57b7fb65a55115ea8bcb6ab6938477Timo Sirainen			/* allocate new stack */
29cda2d6eb57b7fb65a55115ea8bcb6ab6938477Timo Sirainen			stack = calloc(sizeof(MemBlockStack), 1);
29cda2d6eb57b7fb65a55115ea8bcb6ab6938477Timo Sirainen			if (stack == NULL)
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen				i_panic("t_push(): Out of memory");
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen		} else {
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen			/* use existing unused stack */
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen			stack = unused_stack_list;
038c2831447440bf0bef89b43dd0968afc298abcStephan Bosch			unused_stack_list = unused_stack_list->prev;
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen		}
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen		stack->prev = current_stack;
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen		current_stack = stack;
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen	}
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen	/* mark our current position */
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen	current_stack->block[stack_pos] = current_block;
decdff03c32cb5d0e99d71c5678fd008714de70bTimo Sirainen	current_stack->block_space_used[stack_pos] = current_block->left;
decdff03c32cb5d0e99d71c5678fd008714de70bTimo Sirainen
decdff03c32cb5d0e99d71c5678fd008714de70bTimo Sirainen        return stack_pos++;
decdff03c32cb5d0e99d71c5678fd008714de70bTimo Sirainen}
decdff03c32cb5d0e99d71c5678fd008714de70bTimo Sirainen
decdff03c32cb5d0e99d71c5678fd008714de70bTimo Sirainenstatic void free_blocks(MemBlock *block)
decdff03c32cb5d0e99d71c5678fd008714de70bTimo Sirainen{
8e0eb6a0cfc2cb66385bdf05a70a38d753bc1e24Timo Sirainen	/* free all the blocks, except if any of them is bigger than
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen	   unused_block, replace it */
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen	while (block != NULL) {
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen		if (unused_block == NULL || block->size > unused_block->size) {
038c2831447440bf0bef89b43dd0968afc298abcStephan Bosch			free(unused_block);
038c2831447440bf0bef89b43dd0968afc298abcStephan Bosch			unused_block = block;
038c2831447440bf0bef89b43dd0968afc298abcStephan Bosch		} else {
29cda2d6eb57b7fb65a55115ea8bcb6ab6938477Timo Sirainen			free(block);
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen		}
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen		block = block->next;
29cda2d6eb57b7fb65a55115ea8bcb6ab6938477Timo Sirainen	}
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen}
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainenint t_pop(void)
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen{
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen	MemBlockStack *stack;
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen	if (stack_pos == 0)
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen		i_panic("t_pop() called with empty stack");
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen	stack_pos--;
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen	/* update the current block */
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen	current_block = current_stack->block[stack_pos];
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen	current_block->left = current_stack->block_space_used[stack_pos];
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen	if (current_block->next != NULL) {
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen		/* free unused blocks */
decdff03c32cb5d0e99d71c5678fd008714de70bTimo Sirainen		free_blocks(current_block->next);
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen		current_block->next = NULL;
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen	}
038c2831447440bf0bef89b43dd0968afc298abcStephan Bosch
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen	if (stack_pos == 0) {
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen		/* stack block is now unused, add it to unused list */
25fb397382c6f7d39bfeee85774e7675f02bfb3cTimo Sirainen		stack_pos = MEM_LIST_BLOCK_COUNT;
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen		stack = current_stack;
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen		current_stack = stack->prev;
2974dca6be5120e49279f06c8aa952e5fac56048Timo Sirainen
854b4074ac77a138b3983d72510b4d8779d15040Timo Sirainen		stack->prev = unused_stack_list;
		unused_stack_list = stack;
	}

        return stack_pos;
}

static MemBlock *mem_block_alloc(unsigned int min_size)
{
	MemBlock *block;
	unsigned int prev_size, alloc_size;

	prev_size = current_block == NULL ? 0 : current_block->size;
	alloc_size = nearest_power(prev_size + min_size);

	block = malloc(sizeof(MemBlock)-1 + alloc_size);
	if (block == NULL) {
		i_panic("mem_block_alloc(): "
			"Out of memory when allocating %u bytes",
			sizeof(MemBlock)-1 + alloc_size);
	}
	block->size = alloc_size;
	block->next = NULL;

	return block;
}

static void *t_malloc_real(unsigned int size, int permanent)
{
	MemBlock *block;
        void *ret;

	if (size == 0)
		return NULL;

	if (size > MAX_ALLOC_SIZE)
		i_panic("Trying to allocate too much memory");

	/* reset t_buffer_get() mark - not really needed but makes it easier
	   to notice if t_malloc() is called between t_buffer_get() and
	   t_buffer_alloc() */
        last_buffer_block = NULL;

	/* allocate only aligned amount of memory so alignment comes
	   always properly */
	size = MEM_ALIGN(size);

	/* used for t_try_grow() */
	last_alloc_size = size;

	if (current_block->left >= size) {
		/* enough space in current block, use it */
		ret = current_block->data +
			(current_block->size - current_block->left);
                if (permanent)
			current_block->left -= size;
		return ret;
	}

	/* current block is full, see if we can use the unused_block */
	if (unused_block != NULL && unused_block->size >= size) {
		block = unused_block;
		unused_block = NULL;
	} else {
		block = mem_block_alloc(size);
	}

	block->left = block->size;
	if (permanent)
		block->left -= size;
	block->next = NULL;

	current_block->next = block;
	current_block = block;

        return current_block->data;
}

void *t_malloc(unsigned int size)
{
        return t_malloc_real(size, TRUE);
}

void *t_malloc0(unsigned int size)
{
	void *mem;

	mem = t_malloc_real(size, TRUE);
	memset(mem, 0, size);
        return mem;
}

int t_try_grow(void *mem, unsigned int size)
{
	/* see if we want to grow the memory we allocated last */
	if (current_block->data + (current_block->size -
				   current_block->left -
				   last_alloc_size) == mem) {
		/* yeah, see if we can grow */
		size = MEM_ALIGN(size);
		if (current_block->left >= size-last_alloc_size) {
			/* just shrink the available size */
			current_block->left -= size - last_alloc_size;
			last_alloc_size = size;
			return TRUE;
		}
	}

	return FALSE;
}

void *t_buffer_get(unsigned int size)
{
	void *ret;

	ret = t_malloc_real(size, FALSE);

	last_buffer_size = size;
	last_buffer_block = current_block;
	return ret;
}

void *t_buffer_reget(void *buffer, unsigned int size)
{
	unsigned int old_size;
        void *new_buffer;

	old_size = last_buffer_size;
	if (size <= old_size)
                return buffer;

	new_buffer = t_buffer_get(size);
	if (new_buffer != buffer)
                memcpy(new_buffer, buffer, old_size);

        return new_buffer;
}

void t_buffer_alloc(unsigned int size)
{
	i_assert(last_buffer_block != NULL);
	i_assert(last_buffer_size >= size);
	i_assert(current_block->left >= size);

	/* we've already reserved the space, now we just mark it used */
	t_malloc_real(size, TRUE);
}

void temp_mempool_init(void)
{
	current_block = mem_block_alloc(INITIAL_POOL_SIZE);
	current_block->left = current_block->size;
	current_block->next = NULL;

	current_stack = NULL;
	unused_stack_list = NULL;
	stack_pos = MEM_LIST_BLOCK_COUNT;

	t_push();

        last_alloc_size = 0;

        last_buffer_block = NULL;
	last_buffer_size = 0;
}

void temp_mempool_deinit(void)
{
	t_pop();

	if (stack_pos != MEM_LIST_BLOCK_COUNT)
		i_panic("Missing t_pop() call");

	while (unused_stack_list != NULL) {
                MemBlockStack *stack = unused_stack_list;
		unused_stack_list = unused_stack_list->prev;

                free(stack);
	}

	free(current_block);
	free(unused_block);
}

#else

typedef struct _Stack Stack;
typedef struct _Alloc Alloc;

struct _Stack {
	Stack *next;
	Alloc *allocs;
};

struct _Alloc {
	Alloc *next;
	void *mem;
};

static int stack_counter;
static Stack *current_stack;
static void *buffer_mem;

int t_push(void)
{
	Stack *stack;

	stack = malloc(sizeof(Stack));
	stack->allocs = NULL;

	stack->next = current_stack;
	current_stack = stack;
	return stack_counter++;
}

int t_pop(void)
{
	Stack *stack;
	Alloc *alloc;

	stack = current_stack;
	current_stack = stack->next;

	while (stack->allocs != NULL) {
		alloc = stack->allocs;
		stack->allocs = alloc->next;

		free(alloc->mem);
		free(alloc);
	}

	free(stack);
	return --stack_counter;
}

static void add_alloc(void *mem)
{
	Alloc *alloc;

	alloc = malloc(sizeof(Alloc));
	alloc->mem = mem;
	alloc->next = current_stack->allocs;
	current_stack->allocs = alloc;

	if (buffer_mem != NULL) {
		free(buffer_mem);
		buffer_mem = NULL;
	}
}

void *t_malloc(unsigned int size)
{
	void *mem;

	mem = malloc(size);
	add_alloc(mem);
	return mem;
}

void *t_malloc0(unsigned int size)
{
	void *mem;

	mem = calloc(size, 1);
	add_alloc(mem);
	return mem;
}

int t_try_grow(void *mem, unsigned int size)
{
	void *new_mem;

	new_mem = realloc(mem, size);
	if (new_mem == mem)
		return TRUE;

	free(new_mem);
	return FALSE;
}

void *t_buffer_get(unsigned int size)
{
	buffer_mem = realloc(buffer_mem, size);
	return buffer_mem;
}

void *t_buffer_reget(void *buffer, unsigned int size)
{
	i_assert(buffer == buffer_mem);

	buffer_mem = realloc(buffer_mem, size);
	return buffer_mem;
}

void t_buffer_alloc(unsigned int size)
{
	void *mem;

	i_assert(buffer_mem != NULL);

	mem = buffer_mem;
	buffer_mem = NULL;

	add_alloc(mem);
}

void temp_mempool_init(void)
{
        stack_counter = 0;
	current_stack = NULL;
	buffer_mem = NULL;

	t_push();
}

void temp_mempool_deinit(void)
{
	t_pop();

	if (stack_counter != 0)
		i_panic("Missing t_pop() call");
}

#endif