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