dbus/dbus-mempool.c

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