/* -*- mode: C; c-file-style: "gnu" -*- */ /* dbus-mempool.h Memory pools * * Copyright (C) 2002, 2003 Red Hat, Inc. * * Licensed under the Academic Free License version 2.1 * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * */ #include "dbus-mempool.h" #include "dbus-internals.h" /** * @defgroup DBusMemPool memory pools * @ingroup DBusInternals * @brief DBusMemPool object * * Types and functions related to DBusMemPool. A memory pool is used * to decrease memory fragmentation/overhead and increase speed for * blocks of small uniformly-sized objects. The main point is to avoid * the overhead of a malloc block for each small object, speed is * secondary. */ /** * @defgroup DBusMemPoolInternals Memory pool implementation details * @ingroup DBusInternals * @brief DBusMemPool implementation details * * The guts of DBusMemPool. * * @{ */ /** * typedef so DBusFreedElement struct can refer to itself. */ typedef struct DBusFreedElement DBusFreedElement; /** * struct representing an element on the free list. * We just cast freed elements to this so we can * make a list out of them. */ struct DBusFreedElement { DBusFreedElement *next; /**< next element of the free list */ }; /** * The dummy size of the variable-length "elements" * field in DBusMemBlock */ #define ELEMENT_PADDING 4 /** * Typedef for DBusMemBlock so the struct can recursively * point to itself. */ typedef struct DBusMemBlock DBusMemBlock; /** * DBusMemBlock object represents a single malloc()-returned * block that gets chunked up into objects in the memory pool. */ struct DBusMemBlock { DBusMemBlock *next; /**< next block in the list, which is already used up; * only saved so we can free all the blocks * when we free the mem pool. */ /* this is a long so that "elements" is aligned */ long used_so_far; /**< bytes of this block already allocated as elements. */ unsigned char elements[ELEMENT_PADDING]; /**< the block data, actually allocated to required size */ }; /** * Internals fields of DBusMemPool */ struct DBusMemPool { int element_size; /**< size of a single object in the pool */ int block_size; /**< size of most recently allocated block */ unsigned int zero_elements : 1; /**< whether to zero-init allocated elements */ DBusFreedElement *free_elements; /**< a free list of elements to recycle */ DBusMemBlock *blocks; /**< blocks of memory from malloc() */ int allocated_elements; /**< Count of outstanding allocated elements */ }; /** @} */ /** * @addtogroup DBusMemPool * * @{ */ /** * @typedef DBusMemPool * * Opaque object representing a memory pool. Memory pools allow * avoiding per-malloc-block memory overhead when allocating a lot of * small objects that are all the same size. They are slightly * faster than calling malloc() also. */ /** * Creates a new memory pool, or returns #NULL on failure. Objects in * the pool must be at least sizeof(void*) bytes each, due to the way * memory pools work. To avoid creating 64 bit problems, this means at * least 8 bytes on all platforms, unless you are 4 bytes on 32-bit * and 8 bytes on 64-bit. * * @param element_size size of an element allocated from the pool. * @param zero_elements whether to zero-initialize elements * @returns the new pool or #NULL */ DBusMemPool* _dbus_mem_pool_new (int element_size, dbus_bool_t zero_elements) { DBusMemPool *pool; pool = dbus_new0 (DBusMemPool, 1); if (pool == NULL) return NULL; /* Make the element size at least 8 bytes. */ if (element_size < 8) element_size = 8; /* these assertions are equivalent but the first is more clear * to programmers that see it fail. */ _dbus_assert (element_size >= (int) sizeof (void*)); _dbus_assert (element_size >= (int) sizeof (DBusFreedElement)); /* align the element size to a pointer boundary so we won't get bus * errors under other architectures. */ pool->element_size = _DBUS_ALIGN_VALUE (element_size, sizeof (void *)); pool->zero_elements = zero_elements != FALSE; pool->allocated_elements = 0; /* pick a size for the first block; it increases * for each block we need to allocate. This is * actually half the initial block size * since _dbus_mem_pool_alloc() unconditionally * doubles it prior to creating a new block. */ pool->block_size = pool->element_size * 8; _dbus_assert ((pool->block_size % pool->element_size) == 0); return pool; } /** * Frees a memory pool (and all elements allocated from it). * * @param pool the memory pool. */ void _dbus_mem_pool_free (DBusMemPool *pool) { DBusMemBlock *block; block = pool->blocks; while (block != NULL) { DBusMemBlock *next = block->next; dbus_free (block); block = next; } dbus_free (pool); } /** * Allocates an object from the memory pool. * The object must be freed with _dbus_mem_pool_dealloc(). * * @param pool the memory pool * @returns the allocated object or #NULL if no memory. */ void* _dbus_mem_pool_alloc (DBusMemPool *pool) { #ifdef DBUS_BUILD_TESTS if (_dbus_disable_mem_pools ()) { DBusMemBlock *block; int alloc_size; /* This is obviously really silly, but it's * debug-mode-only code that is compiled out * when tests are disabled (_dbus_disable_mem_pools() * is a constant expression FALSE so this block * should vanish) */ alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING + pool->element_size; if (pool->zero_elements) block = dbus_malloc0 (alloc_size); else block = dbus_malloc (alloc_size); if (block != NULL) { block->next = pool->blocks; pool->blocks = block; pool->allocated_elements += 1; return (void*) &block->elements[0]; } else return NULL; } else #endif { if (_dbus_decrement_fail_alloc_counter ()) { _dbus_verbose (" FAILING mempool alloc\n"); return NULL; } else if (pool->free_elements) { DBusFreedElement *element = pool->free_elements; pool->free_elements = pool->free_elements->next; if (pool->zero_elements) memset (element, '\0', pool->element_size); pool->allocated_elements += 1; return element; } else { void *element; if (pool->blocks == NULL || pool->blocks->used_so_far == pool->block_size) { /* Need a new block */ DBusMemBlock *block; int alloc_size; #ifdef DBUS_BUILD_TESTS int saved_counter; #endif if (pool->block_size <= _DBUS_INT_MAX / 4) /* avoid overflow */ { /* use a larger block size for our next block */ pool->block_size *= 2; _dbus_assert ((pool->block_size % pool->element_size) == 0); } alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING + pool->block_size; #ifdef DBUS_BUILD_TESTS /* We save/restore the counter, so that memory pools won't * cause a given function to have different number of * allocations on different invocations. i.e. when testing * we want consistent alloc patterns. So we skip our * malloc here for purposes of failed alloc simulation. */ saved_counter = _dbus_get_fail_alloc_counter (); _dbus_set_fail_alloc_counter (_DBUS_INT_MAX); #endif if (pool->zero_elements) block = dbus_malloc0 (alloc_size); else block = dbus_malloc (alloc_size); #ifdef DBUS_BUILD_TESTS _dbus_set_fail_alloc_counter (saved_counter); _dbus_assert (saved_counter == _dbus_get_fail_alloc_counter ()); #endif if (block == NULL) return NULL; block->used_so_far = 0; block->next = pool->blocks; pool->blocks = block; } element = &pool->blocks->elements[pool->blocks->used_so_far]; pool->blocks->used_so_far += pool->element_size; pool->allocated_elements += 1; return element; } } } /** * Deallocates an object previously created with * _dbus_mem_pool_alloc(). The previous object * must have come from this same pool. * @param pool the memory pool * @param element the element earlier allocated. * @returns #TRUE if there are no remaining allocated elements */ dbus_bool_t _dbus_mem_pool_dealloc (DBusMemPool *pool, void *element) { #ifdef DBUS_BUILD_TESTS if (_dbus_disable_mem_pools ()) { DBusMemBlock *block; DBusMemBlock *prev; /* mmm, fast. ;-) debug-only code, so doesn't matter. */ prev = NULL; block = pool->blocks; while (block != NULL) { if (block->elements == (unsigned char*) element) { if (prev) prev->next = block->next; else pool->blocks = block->next; dbus_free (block); _dbus_assert (pool->allocated_elements > 0); pool->allocated_elements -= 1; if (pool->allocated_elements == 0) _dbus_assert (pool->blocks == NULL); return pool->blocks == NULL; } prev = block; block = block->next; } _dbus_assert_not_reached ("freed nonexistent block"); return FALSE; } else #endif { DBusFreedElement *freed; freed = element; freed->next = pool->free_elements; pool->free_elements = freed; _dbus_assert (pool->allocated_elements > 0); pool->allocated_elements -= 1; return pool->allocated_elements == 0; } } /** @} */ #ifdef DBUS_BUILD_TESTS #include "dbus-test.h" #include #include static void time_for_size (int size) { int i; int j; clock_t start; clock_t end; #define FREE_ARRAY_SIZE 512 #define N_ITERATIONS FREE_ARRAY_SIZE * 512 void *to_free[FREE_ARRAY_SIZE]; DBusMemPool *pool; _dbus_verbose ("Timings for size %d\n", size); _dbus_verbose (" malloc\n"); start = clock (); i = 0; j = 0; while (i < N_ITERATIONS) { to_free[j] = dbus_malloc (size); _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */ ++j; if (j == FREE_ARRAY_SIZE) { j = 0; while (j < FREE_ARRAY_SIZE) { dbus_free (to_free[j]); ++j; } j = 0; } ++i; } end = clock (); _dbus_verbose (" created/destroyed %d elements in %g seconds\n", N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC); _dbus_verbose (" mempools\n"); start = clock (); pool = _dbus_mem_pool_new (size, FALSE); i = 0; j = 0; while (i < N_ITERATIONS) { to_free[j] = _dbus_mem_pool_alloc (pool); _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */ ++j; if (j == FREE_ARRAY_SIZE) { j = 0; while (j < FREE_ARRAY_SIZE) { _dbus_mem_pool_dealloc (pool, to_free[j]); ++j; } j = 0; } ++i; } _dbus_mem_pool_free (pool); end = clock (); _dbus_verbose (" created/destroyed %d elements in %g seconds\n", N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC); _dbus_verbose (" zeroed malloc\n"); start = clock (); i = 0; j = 0; while (i < N_ITERATIONS) { to_free[j] = dbus_malloc0 (size); _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */ ++j; if (j == FREE_ARRAY_SIZE) { j = 0; while (j < FREE_ARRAY_SIZE) { dbus_free (to_free[j]); ++j; } j = 0; } ++i; } end = clock (); _dbus_verbose (" created/destroyed %d elements in %g seconds\n", N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC); _dbus_verbose (" zeroed mempools\n"); start = clock (); pool = _dbus_mem_pool_new (size, TRUE); i = 0; j = 0; while (i < N_ITERATIONS) { to_free[j] = _dbus_mem_pool_alloc (pool); _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */ ++j; if (j == FREE_ARRAY_SIZE) { j = 0; while (j < FREE_ARRAY_SIZE) { _dbus_mem_pool_dealloc (pool, to_free[j]); ++j; } j = 0; } ++i; } _dbus_mem_pool_free (pool); end = clock (); _dbus_verbose (" created/destroyed %d elements in %g seconds\n", N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC); } /** * @ingroup DBusMemPoolInternals * Unit test for DBusMemPool * @returns #TRUE on success. */ dbus_bool_t _dbus_mem_pool_test (void) { int i; int element_sizes[] = { 4, 8, 16, 50, 124 }; i = 0; while (i < _DBUS_N_ELEMENTS (element_sizes)) { time_for_size (element_sizes[i]); ++i; } return TRUE; } #endif /* DBUS_BUILD_TESTS */