--- /dev/null
+/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
+/* 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 <stdio.h>
+#include <time.h>
+
+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 */
projects / monky / blobdiff