+++ /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