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   /* these assertions are equivalent but the first is more clear
 143    * to programmers that see it fail.
 144    */
 145   _dbus_assert (element_size >= (int) sizeof (void*));
 146   _dbus_assert (element_size >= (int) sizeof (DBusFreedElement));
 147
 148   pool->element_size = element_size;
 149   pool->zero_elements = zero_elements != FALSE;
 150
 151   /* pick a size for the first block; it increases
 152    * for each block we need to allocate. This is
 153    * actually half the initial block size
 154    * since _dbus_mem_pool_alloc() unconditionally
 155    * doubles it prior to creating a new block.
 156    */
 157   pool->block_size = element_size * 8;
 158
 159   _dbus_assert ((pool->block_size %
 160                  pool->element_size) == 0);
 161
 162   return pool;
 163 }
 164
 165 /**
 166  * Frees a memory pool (and all elements allocated from it).
 167  *
 168  * @param pool the memory pool.
 169  */
 170 void
 171 _dbus_mem_pool_free (DBusMemPool *pool)
 172 {
 173   DBusMemBlock *block;
 174
 175   block = pool->blocks;
 176   while (block != NULL)
 177     {
 178       DBusMemBlock *next = block->next;
 179
 180       dbus_free (block);
 181
 182       block = next;
 183     }
 184
 185   dbus_free (pool);
 186 }
 187
 188 /**
 189  * Allocates an object from the memory pool.
 190  * The object must be freed with _dbus_mem_pool_dealloc().
 191  *
 192  * @param pool the memory pool
 193  * @returns the allocated object or #NULL if no memory.
 194  */
 195 void*
 196 _dbus_mem_pool_alloc (DBusMemPool *pool)
 197 {
 198   if (_dbus_decrement_fail_alloc_counter ())
 199     return NULL;
 200
 201   if (pool->free_elements)
 202     {
 203       DBusFreedElement *element = pool->free_elements;
 204
 205       pool->free_elements = pool->free_elements->next;
 206
 207       if (pool->zero_elements)
 208         memset (element, '\0', pool->element_size);
 209
 210       return element;
 211     }
 212   else
 213     {
 214       void *element;
 215
 216       if (pool->blocks == NULL ||
 217           pool->blocks->used_so_far == pool->block_size)
 218         {
 219           /* Need a new block */
 220           DBusMemBlock *block;
 221           int alloc_size;
 222 #ifdef DBUS_BUILD_TESTS
 223           int saved_counter;
 224 #endif
 225
 226           if (pool->block_size <= _DBUS_INT_MAX / 4) /* avoid overflow */
 227             {
 228               /* use a larger block size for our next block */
 229               pool->block_size *= 2;
 230               _dbus_assert ((pool->block_size %
 231                              pool->element_size) == 0);
 232             }
 233
 234           alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING + pool->block_size;
 235
 236 #ifdef DBUS_BUILD_TESTS
 237           /* We save/restore the counter, so that memory pools won't
 238            * cause a given function to have different number of
 239            * allocations on different invocations. i.e.  when testing
 240            * we want consistent alloc patterns. So we skip our
 241            * malloc here for purposes of failed alloc simulation.
 242            */
 243           saved_counter = _dbus_get_fail_alloc_counter ();
 244           _dbus_set_fail_alloc_counter (_DBUS_INT_MAX);
 245 #endif
 246
 247           if (pool->zero_elements)
 248             block = dbus_malloc0 (alloc_size);
 249           else
 250             block = dbus_malloc (alloc_size);
 251
 252 #ifdef DBUS_BUILD_TESTS
 253           _dbus_set_fail_alloc_counter (saved_counter);
 254 #endif
 255
 256           if (block == NULL)
 257             return NULL;
 258
 259           block->used_so_far = 0;
 260           block->next = pool->blocks;
 261           pool->blocks = block;
 262         }
 263
 264       element = &pool->blocks->elements[pool->blocks->used_so_far];
 265
 266       pool->blocks->used_so_far += pool->element_size;
 267
 268       return element;
 269     }
 270 }
 271
 272 /**
 273  * Deallocates an object previously created with
 274  * _dbus_mem_pool_alloc(). The previous object
 275  * must have come from this same pool.
 276  * @param pool the memory pool
 277  * @param element the element earlier allocated.
 278  */
 279 void
 280 _dbus_mem_pool_dealloc (DBusMemPool *pool,
 281                         void        *element)
 282 {
 283   DBusFreedElement *freed;
 284
 285   freed = element;
 286   freed->next = pool->free_elements;
 287   pool->free_elements = freed;
 288 }
 289
 290 /** @} */
 291
 292 #ifdef DBUS_BUILD_TESTS
 293 #include "dbus-test.h"
 294 #include <stdio.h>
 295 #include <time.h>
 296
 297 static void
 298 time_for_size (int size)
 299 {
 300   int i;
 301   int j;
 302   clock_t start;
 303   clock_t end;
 304 #define FREE_ARRAY_SIZE 512
 305 #define N_ITERATIONS FREE_ARRAY_SIZE * 512
 306   void *to_free[FREE_ARRAY_SIZE];
 307   DBusMemPool *pool;
 308
 309   _dbus_verbose ("Timings for size %d\n", size);
 310
 311   _dbus_verbose (" malloc\n");
 312
 313   start = clock ();
 314
 315   i = 0;
 316   j = 0;
 317   while (i < N_ITERATIONS)
 318     {
 319       to_free[j] = dbus_malloc (size);
 320       _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */
 321
 322       ++j;
 323
 324       if (j == FREE_ARRAY_SIZE)
 325         {
 326           j = 0;
 327           while (j < FREE_ARRAY_SIZE)
 328             {
 329               dbus_free (to_free[j]);
 330               ++j;
 331             }
 332
 333           j = 0;
 334         }
 335
 336       ++i;
 337     }
 338
 339   end = clock ();
 340
 341   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
 342                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
 343
 344
 345
 346   _dbus_verbose (" mempools\n");
 347
 348   start = clock ();
 349
 350   pool = _dbus_mem_pool_new (size, FALSE);
 351
 352   i = 0;
 353   j = 0;
 354   while (i < N_ITERATIONS)
 355     {
 356       to_free[j] = _dbus_mem_pool_alloc (pool);
 357       _dbus_assert (to_free[j] != NULL);  /* in a real app of course this is wrong */
 358
 359       ++j;
 360
 361       if (j == FREE_ARRAY_SIZE)
 362         {
 363           j = 0;
 364           while (j < FREE_ARRAY_SIZE)
 365             {
 366               _dbus_mem_pool_dealloc (pool, to_free[j]);
 367               ++j;
 368             }
 369
 370           j = 0;
 371         }
 372
 373       ++i;
 374     }
 375
 376   _dbus_mem_pool_free (pool);
 377
 378   end = clock ();
 379
 380   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
 381                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
 382
 383   _dbus_verbose (" zeroed malloc\n");
 384
 385   start = clock ();
 386
 387   i = 0;
 388   j = 0;
 389   while (i < N_ITERATIONS)
 390     {
 391       to_free[j] = dbus_malloc0 (size);
 392       _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */
 393
 394       ++j;
 395
 396       if (j == FREE_ARRAY_SIZE)
 397         {
 398           j = 0;
 399           while (j < FREE_ARRAY_SIZE)
 400             {
 401               dbus_free (to_free[j]);
 402               ++j;
 403             }
 404
 405           j = 0;
 406         }
 407
 408       ++i;
 409     }
 410
 411   end = clock ();
 412
 413   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
 414                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
 415
 416   _dbus_verbose (" zeroed mempools\n");
 417
 418   start = clock ();
 419
 420   pool = _dbus_mem_pool_new (size, TRUE);
 421
 422   i = 0;
 423   j = 0;
 424   while (i < N_ITERATIONS)
 425     {
 426       to_free[j] = _dbus_mem_pool_alloc (pool);
 427       _dbus_assert (to_free[j] != NULL);  /* in a real app of course this is wrong */
 428
 429       ++j;
 430
 431       if (j == FREE_ARRAY_SIZE)
 432         {
 433           j = 0;
 434           while (j < FREE_ARRAY_SIZE)
 435             {
 436               _dbus_mem_pool_dealloc (pool, to_free[j]);
 437               ++j;
 438             }
 439
 440           j = 0;
 441         }
 442
 443       ++i;
 444     }
 445
 446   _dbus_mem_pool_free (pool);
 447
 448   end = clock ();
 449
 450   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
 451                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
 452 }
 453
 454 /**
 455  * @ingroup DBusMemPoolInternals
 456  * Unit test for DBusMemPool
 457  * @returns #TRUE on success.
 458  */
 459 dbus_bool_t
 460 _dbus_mem_pool_test (void)
 461 {
 462   int i;
 463   int element_sizes[] = { 4, 8, 16, 50, 124 };
 464
 465   i = 0;
 466   while (i < _DBUS_N_ELEMENTS (element_sizes))
 467     {
 468       time_for_size (element_sizes[i]);
 469       ++i;
 470     }
 471
 472   return TRUE;
 473 }
 474
 475 #endif /* DBUS_BUILD_TESTS */