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