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