dbus/dbus-mempool.c

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