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