dbus/dbus-mempool.c

   1 /* -*- mode: C; c-file-style: "gnu" -*- */
   2 /* dbus-mempool.h Memory pools
   3  *
   4  * Copyright (C) 2002, 2003  Red Hat, Inc.
   5  *
   6  * Licensed under the Academic Free License version 1.2
   7  *
   8  * This program is free software; you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License as published by
  10  * the Free Software Foundation; either version 2 of the License, or
  11  * (at your option) any later version.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with this program; if not, write to the Free Software
  20  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  21  *
  22  */
  23
  24 #include "dbus-mempool.h"
  25
  26 /**
  27  * @defgroup DBusMemPool memory pools
  28  * @ingroup  DBusInternals
  29  * @brief DBusMemPool object
  30  *
  31  * Types and functions related to DBusMemPool.  A memory pool is used
  32  * to decrease memory fragmentation/overhead and increase speed for
  33  * blocks of small uniformly-sized objects. The main point is to avoid
  34  * the overhead of a malloc block for each small object, speed is
  35  * secondary.
  36  */
  37
  38 /**
  39  * @defgroup DBusMemPoolInternals Memory pool implementation details
  40  * @ingroup  DBusInternals
  41  * @brief DBusMemPool implementation details
  42  *
  43  * The guts of DBusMemPool.
  44  *
  45  * @{
  46  */
  47
  48 /**
  49  * typedef so DBusFreedElement struct can refer to itself.
  50  */
  51 typedef struct DBusFreedElement DBusFreedElement;
  52
  53 /**
  54  * struct representing an element on the free list.
  55  * We just cast freed elements to this so we can
  56  * make a list out of them.
  57  */
  58 struct DBusFreedElement
  59 {
  60   DBusFreedElement *next; /**< next element of the free list */
  61 };
  62
  63 /**
  64  * The dummy size of the variable-length "elements"
  65  * field in DBusMemBlock
  66  */
  67 #define ELEMENT_PADDING 4
  68
  69 /**
  70  * Typedef for DBusMemBlock so the struct can recursively
  71  * point to itself.
  72  */
  73 typedef struct DBusMemBlock DBusMemBlock;
  74
  75 /**
  76  * DBusMemBlock object represents a single malloc()-returned
  77  * block that gets chunked up into objects in the memory pool.
  78  */
  79 struct DBusMemBlock
  80 {
  81   DBusMemBlock *next;  /**< next block in the list, which is already used up;
  82                         *   only saved so we can free all the blocks
  83                         *   when we free the mem pool.
  84                         */
  85
  86   int used_so_far;     /**< bytes of this block already allocated as elements. */
  87
  88   unsigned char elements[ELEMENT_PADDING]; /**< the block data, actually allocated to required size */
  89 };
  90
  91 /**
  92  * Internals fields of DBusMemPool
  93  */
  94 struct DBusMemPool
  95 {
  96   int element_size;                /**< size of a single object in the pool */
  97   int block_size;                  /**< size of most recently allocated block */
  98   unsigned int zero_elements : 1;  /**< whether to zero-init allocated elements */
  99
 100   DBusFreedElement *free_elements; /**< a free list of elements to recycle */
 101   DBusMemBlock *blocks;            /**< blocks of memory from malloc() */
 102 };
 103
 104 /** @} */
 105
 106 /**
 107  * @addtogroup DBusMemPool
 108  *
 109  * @{
 110  */
 111
 112 /**
 113  * @typedef DBusMemPool
 114  *
 115  * Opaque object representing a memory pool. Memory pools allow
 116  * avoiding per-malloc-block memory overhead when allocating a lot of
 117  * small objects that are all the same size. They are slightly
 118  * faster than calling malloc() also.
 119  */
 120
 121 /**
 122  * Creates a new memory pool, or returns #NULL on failure.  Objects in
 123  * the pool must be at least sizeof(void*) bytes each, due to the way
 124  * memory pools work. To avoid creating 64 bit problems, this means at
 125  * least 8 bytes on all platforms, unless you are 4 bytes on 32-bit
 126  * and 8 bytes on 64-bit.
 127  *
 128  * @param element_size size of an element allocated from the pool.
 129  * @param zero_elements whether to zero-initialize elements
 130  * @returns the new pool or #NULL
 131  */
 132 DBusMemPool*
 133 _dbus_mem_pool_new (int element_size,
 134                     dbus_bool_t zero_elements)
 135 {
 136   DBusMemPool *pool;
 137
 138   pool = dbus_new0 (DBusMemPool, 1);
 139   if (pool == NULL)
 140     return NULL;
 141
 142   /* Make the element size at least 8 bytes. */
 143   if (element_size < 8)
 144     element_size = 8;
 145
 146   /* these assertions are equivalent but the first is more clear
 147    * to programmers that see it fail.
 148    */
 149   _dbus_assert (element_size >= (int) sizeof (void*));
 150   _dbus_assert (element_size >= (int) sizeof (DBusFreedElement));
 151
 152   /* align the element size to a pointer boundary so we won't get bus
 153    * errors under other architectures.
 154    */
 155   pool->element_size = _DBUS_ALIGN_VALUE (element_size, sizeof (void *));
 156
 157   pool->zero_elements = zero_elements != FALSE;
 158
 159   /* pick a size for the first block; it increases
 160    * for each block we need to allocate. This is
 161    * actually half the initial block size
 162    * since _dbus_mem_pool_alloc() unconditionally
 163    * doubles it prior to creating a new block.  */
 164   pool->block_size = pool->element_size * 8;
 165
 166   _dbus_assert ((pool->block_size %
 167                  pool->element_size) == 0);
 168
 169   return pool;
 170 }
 171
 172 /**
 173  * Frees a memory pool (and all elements allocated from it).
 174  *
 175  * @param pool the memory pool.
 176  */
 177 void
 178 _dbus_mem_pool_free (DBusMemPool *pool)
 179 {
 180   DBusMemBlock *block;
 181
 182   block = pool->blocks;
 183   while (block != NULL)
 184     {
 185       DBusMemBlock *next = block->next;
 186
 187       dbus_free (block);
 188
 189       block = next;
 190     }
 191
 192   dbus_free (pool);
 193 }
 194
 195 /**
 196  * Allocates an object from the memory pool.
 197  * The object must be freed with _dbus_mem_pool_dealloc().
 198  *
 199  * @param pool the memory pool
 200  * @returns the allocated object or #NULL if no memory.
 201  */
 202 void*
 203 _dbus_mem_pool_alloc (DBusMemPool *pool)
 204 {
 205   if (_dbus_decrement_fail_alloc_counter ())
 206     {
 207       _dbus_verbose (" FAILING mempool alloc\n");
 208       return NULL;
 209     }
 210
 211   if (pool->free_elements)
 212     {
 213       DBusFreedElement *element = pool->free_elements;
 214
 215       pool->free_elements = pool->free_elements->next;
 216
 217       if (pool->zero_elements)
 218         memset (element, '\0', pool->element_size);
 219
 220       return element;
 221     }
 222   else
 223     {
 224       void *element;
 225
 226       if (pool->blocks == NULL ||
 227           pool->blocks->used_so_far == pool->block_size)
 228         {
 229           /* Need a new block */
 230           DBusMemBlock *block;
 231           int alloc_size;
 232 #ifdef DBUS_BUILD_TESTS
 233           int saved_counter;
 234 #endif
 235
 236           if (pool->block_size <= _DBUS_INT_MAX / 4) /* avoid overflow */
 237             {
 238               /* use a larger block size for our next block */
 239               pool->block_size *= 2;
 240               _dbus_assert ((pool->block_size %
 241                              pool->element_size) == 0);
 242             }
 243
 244           alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING + pool->block_size;
 245
 246 #ifdef DBUS_BUILD_TESTS
 247           /* We save/restore the counter, so that memory pools won't
 248            * cause a given function to have different number of
 249            * allocations on different invocations. i.e.  when testing
 250            * we want consistent alloc patterns. So we skip our
 251            * malloc here for purposes of failed alloc simulation.
 252            */
 253           saved_counter = _dbus_get_fail_alloc_counter ();
 254           _dbus_set_fail_alloc_counter (_DBUS_INT_MAX);
 255 #endif
 256
 257           if (pool->zero_elements)
 258             block = dbus_malloc0 (alloc_size);
 259           else
 260             block = dbus_malloc (alloc_size);
 261
 262 #ifdef DBUS_BUILD_TESTS
 263           _dbus_set_fail_alloc_counter (saved_counter);
 264 #endif
 265
 266           if (block == NULL)
 267             return NULL;
 268
 269           block->used_so_far = 0;
 270           block->next = pool->blocks;
 271           pool->blocks = block;
 272         }
 273
 274       element = &pool->blocks->elements[pool->blocks->used_so_far];
 275
 276       pool->blocks->used_so_far += pool->element_size;
 277
 278       return element;
 279     }
 280 }
 281
 282 /**
 283  * Deallocates an object previously created with
 284  * _dbus_mem_pool_alloc(). The previous object
 285  * must have come from this same pool.
 286  * @param pool the memory pool
 287  * @param element the element earlier allocated.
 288  */
 289 void
 290 _dbus_mem_pool_dealloc (DBusMemPool *pool,
 291                         void        *element)
 292 {
 293   DBusFreedElement *freed;
 294
 295   freed = element;
 296   freed->next = pool->free_elements;
 297   pool->free_elements = freed;
 298 }
 299
 300 /** @} */
 301
 302 #ifdef DBUS_BUILD_TESTS
 303 #include "dbus-test.h"
 304 #include <stdio.h>
 305 #include <time.h>
 306
 307 static void
 308 time_for_size (int size)
 309 {
 310   int i;
 311   int j;
 312   clock_t start;
 313   clock_t end;
 314 #define FREE_ARRAY_SIZE 512
 315 #define N_ITERATIONS FREE_ARRAY_SIZE * 512
 316   void *to_free[FREE_ARRAY_SIZE];
 317   DBusMemPool *pool;
 318
 319   _dbus_verbose ("Timings for size %d\n", size);
 320
 321   _dbus_verbose (" malloc\n");
 322
 323   start = clock ();
 324
 325   i = 0;
 326   j = 0;
 327   while (i < N_ITERATIONS)
 328     {
 329       to_free[j] = dbus_malloc (size);
 330       _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */
 331
 332       ++j;
 333
 334       if (j == FREE_ARRAY_SIZE)
 335         {
 336           j = 0;
 337           while (j < FREE_ARRAY_SIZE)
 338             {
 339               dbus_free (to_free[j]);
 340               ++j;
 341             }
 342
 343           j = 0;
 344         }
 345
 346       ++i;
 347     }
 348
 349   end = clock ();
 350
 351   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
 352                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
 353
 354
 355
 356   _dbus_verbose (" mempools\n");
 357
 358   start = clock ();
 359
 360   pool = _dbus_mem_pool_new (size, FALSE);
 361
 362   i = 0;
 363   j = 0;
 364   while (i < N_ITERATIONS)
 365     {
 366       to_free[j] = _dbus_mem_pool_alloc (pool);
 367       _dbus_assert (to_free[j] != NULL);  /* in a real app of course this is wrong */
 368
 369       ++j;
 370
 371       if (j == FREE_ARRAY_SIZE)
 372         {
 373           j = 0;
 374           while (j < FREE_ARRAY_SIZE)
 375             {
 376               _dbus_mem_pool_dealloc (pool, to_free[j]);
 377               ++j;
 378             }
 379
 380           j = 0;
 381         }
 382
 383       ++i;
 384     }
 385
 386   _dbus_mem_pool_free (pool);
 387
 388   end = clock ();
 389
 390   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
 391                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
 392
 393   _dbus_verbose (" zeroed malloc\n");
 394
 395   start = clock ();
 396
 397   i = 0;
 398   j = 0;
 399   while (i < N_ITERATIONS)
 400     {
 401       to_free[j] = dbus_malloc0 (size);
 402       _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */
 403
 404       ++j;
 405
 406       if (j == FREE_ARRAY_SIZE)
 407         {
 408           j = 0;
 409           while (j < FREE_ARRAY_SIZE)
 410             {
 411               dbus_free (to_free[j]);
 412               ++j;
 413             }
 414
 415           j = 0;
 416         }
 417
 418       ++i;
 419     }
 420
 421   end = clock ();
 422
 423   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
 424                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
 425
 426   _dbus_verbose (" zeroed mempools\n");
 427
 428   start = clock ();
 429
 430   pool = _dbus_mem_pool_new (size, TRUE);
 431
 432   i = 0;
 433   j = 0;
 434   while (i < N_ITERATIONS)
 435     {
 436       to_free[j] = _dbus_mem_pool_alloc (pool);
 437       _dbus_assert (to_free[j] != NULL);  /* in a real app of course this is wrong */
 438
 439       ++j;
 440
 441       if (j == FREE_ARRAY_SIZE)
 442         {
 443           j = 0;
 444           while (j < FREE_ARRAY_SIZE)
 445             {
 446               _dbus_mem_pool_dealloc (pool, to_free[j]);
 447               ++j;
 448             }
 449
 450           j = 0;
 451         }
 452
 453       ++i;
 454     }
 455
 456   _dbus_mem_pool_free (pool);
 457
 458   end = clock ();
 459
 460   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
 461                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
 462 }
 463
 464 /**
 465  * @ingroup DBusMemPoolInternals
 466  * Unit test for DBusMemPool
 467  * @returns #TRUE on success.
 468  */
 469 dbus_bool_t
 470 _dbus_mem_pool_test (void)
 471 {
 472   int i;
 473   int element_sizes[] = { 4, 8, 16, 50, 124 };
 474
 475   i = 0;
 476   while (i < _DBUS_N_ELEMENTS (element_sizes))
 477     {
 478       time_for_size (element_sizes[i]);
 479       ++i;
 480     }
 481
 482   return TRUE;
 483 }
 484
 485 #endif /* DBUS_BUILD_TESTS */