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 #include "dbus-internals.h"
  26
  27 /**
  28  * @defgroup DBusMemPool memory pools
  29  * @ingroup  DBusInternals
  30  * @brief DBusMemPool object
  31  *
  32  * Types and functions related to DBusMemPool.  A memory pool is used
  33  * to decrease memory fragmentation/overhead and increase speed for
  34  * blocks of small uniformly-sized objects. The main point is to avoid
  35  * the overhead of a malloc block for each small object, speed is
  36  * secondary.
  37  */
  38
  39 /**
  40  * @defgroup DBusMemPoolInternals Memory pool implementation details
  41  * @ingroup  DBusInternals
  42  * @brief DBusMemPool implementation details
  43  *
  44  * The guts of DBusMemPool.
  45  *
  46  * @{
  47  */
  48
  49 /**
  50  * typedef so DBusFreedElement struct can refer to itself.
  51  */
  52 typedef struct DBusFreedElement DBusFreedElement;
  53
  54 /**
  55  * struct representing an element on the free list.
  56  * We just cast freed elements to this so we can
  57  * make a list out of them.
  58  */
  59 struct DBusFreedElement
  60 {
  61   DBusFreedElement *next; /**< next element of the free list */
  62 };
  63
  64 /**
  65  * The dummy size of the variable-length "elements"
  66  * field in DBusMemBlock
  67  */
  68 #define ELEMENT_PADDING 4
  69
  70 /**
  71  * Typedef for DBusMemBlock so the struct can recursively
  72  * point to itself.
  73  */
  74 typedef struct DBusMemBlock DBusMemBlock;
  75
  76 /**
  77  * DBusMemBlock object represents a single malloc()-returned
  78  * block that gets chunked up into objects in the memory pool.
  79  */
  80 struct DBusMemBlock
  81 {
  82   DBusMemBlock *next;  /**< next block in the list, which is already used up;
  83                         *   only saved so we can free all the blocks
  84                         *   when we free the mem pool.
  85                         */
  86
  87   int used_so_far;     /**< bytes of this block already allocated as elements. */
  88
  89   unsigned char elements[ELEMENT_PADDING]; /**< the block data, actually allocated to required size */
  90 };
  91
  92 /**
  93  * Internals fields of DBusMemPool
  94  */
  95 struct DBusMemPool
  96 {
  97   int element_size;                /**< size of a single object in the pool */
  98   int block_size;                  /**< size of most recently allocated block */
  99   unsigned int zero_elements : 1;  /**< whether to zero-init allocated elements */
 100
 101   DBusFreedElement *free_elements; /**< a free list of elements to recycle */
 102   DBusMemBlock *blocks;            /**< blocks of memory from malloc() */
 103   int allocated_elements;          /**< Count of outstanding allocated elements */
 104 };
 105
 106 /** @} */
 107
 108 /**
 109  * @addtogroup DBusMemPool
 110  *
 111  * @{
 112  */
 113
 114 /**
 115  * @typedef DBusMemPool
 116  *
 117  * Opaque object representing a memory pool. Memory pools allow
 118  * avoiding per-malloc-block memory overhead when allocating a lot of
 119  * small objects that are all the same size. They are slightly
 120  * faster than calling malloc() also.
 121  */
 122
 123 /**
 124  * Creates a new memory pool, or returns #NULL on failure.  Objects in
 125  * the pool must be at least sizeof(void*) bytes each, due to the way
 126  * memory pools work. To avoid creating 64 bit problems, this means at
 127  * least 8 bytes on all platforms, unless you are 4 bytes on 32-bit
 128  * and 8 bytes on 64-bit.
 129  *
 130  * @param element_size size of an element allocated from the pool.
 131  * @param zero_elements whether to zero-initialize elements
 132  * @returns the new pool or #NULL
 133  */
 134 DBusMemPool*
 135 _dbus_mem_pool_new (int element_size,
 136                     dbus_bool_t zero_elements)
 137 {
 138   DBusMemPool *pool;
 139
 140   pool = dbus_new0 (DBusMemPool, 1);
 141   if (pool == NULL)
 142     return NULL;
 143
 144   /* Make the element size at least 8 bytes. */
 145   if (element_size < 8)
 146     element_size = 8;
 147
 148   /* these assertions are equivalent but the first is more clear
 149    * to programmers that see it fail.
 150    */
 151   _dbus_assert (element_size >= (int) sizeof (void*));
 152   _dbus_assert (element_size >= (int) sizeof (DBusFreedElement));
 153
 154   /* align the element size to a pointer boundary so we won't get bus
 155    * errors under other architectures.
 156    */
 157   pool->element_size = _DBUS_ALIGN_VALUE (element_size, sizeof (void *));
 158
 159   pool->zero_elements = zero_elements != FALSE;
 160
 161   pool->allocated_elements = 0;
 162
 163   /* pick a size for the first block; it increases
 164    * for each block we need to allocate. This is
 165    * actually half the initial block size
 166    * since _dbus_mem_pool_alloc() unconditionally
 167    * doubles it prior to creating a new block.  */
 168   pool->block_size = pool->element_size * 8;
 169
 170   _dbus_assert ((pool->block_size %
 171                  pool->element_size) == 0);
 172
 173   return pool;
 174 }
 175
 176 /**
 177  * Frees a memory pool (and all elements allocated from it).
 178  *
 179  * @param pool the memory pool.
 180  */
 181 void
 182 _dbus_mem_pool_free (DBusMemPool *pool)
 183 {
 184   DBusMemBlock *block;
 185
 186   block = pool->blocks;
 187   while (block != NULL)
 188     {
 189       DBusMemBlock *next = block->next;
 190
 191       dbus_free (block);
 192
 193       block = next;
 194     }
 195
 196   dbus_free (pool);
 197 }
 198
 199 /**
 200  * Allocates an object from the memory pool.
 201  * The object must be freed with _dbus_mem_pool_dealloc().
 202  *
 203  * @param pool the memory pool
 204  * @returns the allocated object or #NULL if no memory.
 205  */
 206 void*
 207 _dbus_mem_pool_alloc (DBusMemPool *pool)
 208 {
 209   if (_dbus_disable_mem_pools ())
 210     {
 211       DBusMemBlock *block;
 212       int alloc_size;
 213
 214       /* This is obviously really silly, but it's
 215        * debug-mode-only code that is compiled out
 216        * when tests are disabled (_dbus_disable_mem_pools()
 217        * is a constant expression FALSE so this block
 218        * should vanish)
 219        */
 220
 221       alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING +
 222         pool->element_size;
 223
 224       if (pool->zero_elements)
 225         block = dbus_malloc0 (alloc_size);
 226       else
 227         block = dbus_malloc (alloc_size);
 228
 229       if (block != NULL)
 230         {
 231           block->next = pool->blocks;
 232           pool->blocks = block;
 233           pool->allocated_elements += 1;
 234
 235           return (void*) &block->elements[0];
 236         }
 237       else
 238         return NULL;
 239     }
 240   else
 241     {
 242       if (_dbus_decrement_fail_alloc_counter ())
 243         {
 244           _dbus_verbose (" FAILING mempool alloc\n");
 245           return NULL;
 246         }
 247       else if (pool->free_elements)
 248         {
 249           DBusFreedElement *element = pool->free_elements;
 250
 251           pool->free_elements = pool->free_elements->next;
 252
 253           if (pool->zero_elements)
 254             memset (element, '\0', pool->element_size);
 255
 256           pool->allocated_elements += 1;
 257
 258           return element;
 259         }
 260       else
 261         {
 262           void *element;
 263
 264           if (pool->blocks == NULL ||
 265               pool->blocks->used_so_far == pool->block_size)
 266             {
 267               /* Need a new block */
 268               DBusMemBlock *block;
 269               int alloc_size;
 270 #ifdef DBUS_BUILD_TESTS
 271               int saved_counter;
 272 #endif
 273
 274               if (pool->block_size <= _DBUS_INT_MAX / 4) /* avoid overflow */
 275                 {
 276                   /* use a larger block size for our next block */
 277                   pool->block_size *= 2;
 278                   _dbus_assert ((pool->block_size %
 279                                  pool->element_size) == 0);
 280                 }
 281
 282               alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING + pool->block_size;
 283
 284 #ifdef DBUS_BUILD_TESTS
 285               /* We save/restore the counter, so that memory pools won't
 286                * cause a given function to have different number of
 287                * allocations on different invocations. i.e.  when testing
 288                * we want consistent alloc patterns. So we skip our
 289                * malloc here for purposes of failed alloc simulation.
 290                */
 291               saved_counter = _dbus_get_fail_alloc_counter ();
 292               _dbus_set_fail_alloc_counter (_DBUS_INT_MAX);
 293 #endif
 294
 295               if (pool->zero_elements)
 296                 block = dbus_malloc0 (alloc_size);
 297               else
 298                 block = dbus_malloc (alloc_size);
 299
 300 #ifdef DBUS_BUILD_TESTS
 301               _dbus_set_fail_alloc_counter (saved_counter);
 302               _dbus_assert (saved_counter == _dbus_get_fail_alloc_counter ());
 303 #endif
 304
 305               if (block == NULL)
 306                 return NULL;
 307
 308               block->used_so_far = 0;
 309               block->next = pool->blocks;
 310               pool->blocks = block;
 311             }
 312
 313           element = &pool->blocks->elements[pool->blocks->used_so_far];
 314
 315           pool->blocks->used_so_far += pool->element_size;
 316
 317           pool->allocated_elements += 1;
 318
 319           return element;
 320         }
 321     }
 322 }
 323
 324 /**
 325  * Deallocates an object previously created with
 326  * _dbus_mem_pool_alloc(). The previous object
 327  * must have come from this same pool.
 328  * @param pool the memory pool
 329  * @param element the element earlier allocated.
 330  * @returns #TRUE if there are no remaining allocated elements
 331  */
 332 dbus_bool_t
 333 _dbus_mem_pool_dealloc (DBusMemPool *pool,
 334                         void        *element)
 335 {
 336   if (_dbus_disable_mem_pools ())
 337     {
 338       DBusMemBlock *block;
 339       DBusMemBlock *prev;
 340
 341       /* mmm, fast. ;-) debug-only code, so doesn't matter. */
 342
 343       prev = NULL;
 344       block = pool->blocks;
 345
 346       while (block != NULL)
 347         {
 348           if (block->elements == (unsigned char*) element)
 349             {
 350               if (prev)
 351                 prev->next = block->next;
 352               else
 353                 pool->blocks = block->next;
 354
 355               dbus_free (block);
 356
 357               _dbus_assert (pool->allocated_elements > 0);
 358               pool->allocated_elements -= 1;
 359
 360               if (pool->allocated_elements == 0)
 361                 _dbus_assert (pool->blocks == NULL);
 362
 363               return pool->blocks == NULL;
 364             }
 365           prev = block;
 366           block = block->next;
 367         }
 368
 369       _dbus_assert_not_reached ("freed nonexistent block");
 370       return FALSE;
 371     }
 372   else
 373     {
 374       DBusFreedElement *freed;
 375
 376       freed = element;
 377       freed->next = pool->free_elements;
 378       pool->free_elements = freed;
 379
 380       _dbus_assert (pool->allocated_elements > 0);
 381       pool->allocated_elements -= 1;
 382
 383       return pool->allocated_elements == 0;
 384     }
 385 }
 386
 387 /** @} */
 388
 389 #ifdef DBUS_BUILD_TESTS
 390 #include "dbus-test.h"
 391 #include <stdio.h>
 392 #include <time.h>
 393
 394 static void
 395 time_for_size (int size)
 396 {
 397   int i;
 398   int j;
 399   clock_t start;
 400   clock_t end;
 401 #define FREE_ARRAY_SIZE 512
 402 #define N_ITERATIONS FREE_ARRAY_SIZE * 512
 403   void *to_free[FREE_ARRAY_SIZE];
 404   DBusMemPool *pool;
 405
 406   _dbus_verbose ("Timings for size %d\n", size);
 407
 408   _dbus_verbose (" malloc\n");
 409
 410   start = clock ();
 411
 412   i = 0;
 413   j = 0;
 414   while (i < N_ITERATIONS)
 415     {
 416       to_free[j] = dbus_malloc (size);
 417       _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */
 418
 419       ++j;
 420
 421       if (j == FREE_ARRAY_SIZE)
 422         {
 423           j = 0;
 424           while (j < FREE_ARRAY_SIZE)
 425             {
 426               dbus_free (to_free[j]);
 427               ++j;
 428             }
 429
 430           j = 0;
 431         }
 432
 433       ++i;
 434     }
 435
 436   end = clock ();
 437
 438   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
 439                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
 440
 441
 442
 443   _dbus_verbose (" mempools\n");
 444
 445   start = clock ();
 446
 447   pool = _dbus_mem_pool_new (size, FALSE);
 448
 449   i = 0;
 450   j = 0;
 451   while (i < N_ITERATIONS)
 452     {
 453       to_free[j] = _dbus_mem_pool_alloc (pool);
 454       _dbus_assert (to_free[j] != NULL);  /* in a real app of course this is wrong */
 455
 456       ++j;
 457
 458       if (j == FREE_ARRAY_SIZE)
 459         {
 460           j = 0;
 461           while (j < FREE_ARRAY_SIZE)
 462             {
 463               _dbus_mem_pool_dealloc (pool, to_free[j]);
 464               ++j;
 465             }
 466
 467           j = 0;
 468         }
 469
 470       ++i;
 471     }
 472
 473   _dbus_mem_pool_free (pool);
 474
 475   end = clock ();
 476
 477   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
 478                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
 479
 480   _dbus_verbose (" zeroed malloc\n");
 481
 482   start = clock ();
 483
 484   i = 0;
 485   j = 0;
 486   while (i < N_ITERATIONS)
 487     {
 488       to_free[j] = dbus_malloc0 (size);
 489       _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */
 490
 491       ++j;
 492
 493       if (j == FREE_ARRAY_SIZE)
 494         {
 495           j = 0;
 496           while (j < FREE_ARRAY_SIZE)
 497             {
 498               dbus_free (to_free[j]);
 499               ++j;
 500             }
 501
 502           j = 0;
 503         }
 504
 505       ++i;
 506     }
 507
 508   end = clock ();
 509
 510   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
 511                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
 512
 513   _dbus_verbose (" zeroed mempools\n");
 514
 515   start = clock ();
 516
 517   pool = _dbus_mem_pool_new (size, TRUE);
 518
 519   i = 0;
 520   j = 0;
 521   while (i < N_ITERATIONS)
 522     {
 523       to_free[j] = _dbus_mem_pool_alloc (pool);
 524       _dbus_assert (to_free[j] != NULL);  /* in a real app of course this is wrong */
 525
 526       ++j;
 527
 528       if (j == FREE_ARRAY_SIZE)
 529         {
 530           j = 0;
 531           while (j < FREE_ARRAY_SIZE)
 532             {
 533               _dbus_mem_pool_dealloc (pool, to_free[j]);
 534               ++j;
 535             }
 536
 537           j = 0;
 538         }
 539
 540       ++i;
 541     }
 542
 543   _dbus_mem_pool_free (pool);
 544
 545   end = clock ();
 546
 547   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
 548                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
 549 }
 550
 551 /**
 552  * @ingroup DBusMemPoolInternals
 553  * Unit test for DBusMemPool
 554  * @returns #TRUE on success.
 555  */
 556 dbus_bool_t
 557 _dbus_mem_pool_test (void)
 558 {
 559   int i;
 560   int element_sizes[] = { 4, 8, 16, 50, 124 };
 561
 562   i = 0;
 563   while (i < _DBUS_N_ELEMENTS (element_sizes))
 564     {
 565       time_for_size (element_sizes[i]);
 566       ++i;
 567     }
 568
 569   return TRUE;
 570 }
 571
 572 #endif /* DBUS_BUILD_TESTS */