dbus-mempool.c

00001 /* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
00002 /* dbus-mempool.h Memory pools
00003  * 
00004  * Copyright (C) 2002, 2003  Red Hat, Inc.
00005  *
00006  * Licensed under the Academic Free License version 2.1
00007  * 
00008  * This program is free software; you can redistribute it and/or modify
00009  * it under the terms of the GNU General Public License as published by
00010  * the Free Software Foundation; either version 2 of the License, or
00011  * (at your option) any later version.
00012  *
00013  * This program is distributed in the hope that it will be useful,
00014  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00015  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00016  * GNU General Public License for more details.
00017  * 
00018  * You should have received a copy of the GNU General Public License
00019  * along with this program; if not, write to the Free Software
00020  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00021  *
00022  */
00023 
00024 #include "dbus-mempool.h"
00025 #include "dbus-internals.h"
00026 
00052 typedef struct DBusFreedElement DBusFreedElement;
00053 
00059 struct DBusFreedElement
00060 {
00061   DBusFreedElement *next; 
00062 };
00063 
00068 #define ELEMENT_PADDING 4
00069 
00074 typedef struct DBusMemBlock DBusMemBlock;
00075 
00080 struct DBusMemBlock
00081 {
00082   DBusMemBlock *next;  
00087   /* this is a long so that "elements" is aligned */
00088   long used_so_far;     
00090   unsigned char elements[ELEMENT_PADDING]; 
00091 };
00092 
00096 struct DBusMemPool
00097 {
00098   int element_size;                
00099   int block_size;                  
00100   unsigned int zero_elements : 1;  
00102   DBusFreedElement *free_elements; 
00103   DBusMemBlock *blocks;            
00104   int allocated_elements;          
00105 };
00106 
00135 DBusMemPool*
00136 _dbus_mem_pool_new (int element_size,
00137                     dbus_bool_t zero_elements)
00138 {
00139   DBusMemPool *pool;
00140 
00141   pool = dbus_new0 (DBusMemPool, 1);
00142   if (pool == NULL)
00143     return NULL;
00144 
00145   /* Make the element size at least 8 bytes. */
00146   if (element_size < 8)
00147     element_size = 8;
00148   
00149   /* these assertions are equivalent but the first is more clear
00150    * to programmers that see it fail.
00151    */
00152   _dbus_assert (element_size >= (int) sizeof (void*));
00153   _dbus_assert (element_size >= (int) sizeof (DBusFreedElement));
00154 
00155   /* align the element size to a pointer boundary so we won't get bus
00156    * errors under other architectures.  
00157    */
00158   pool->element_size = _DBUS_ALIGN_VALUE (element_size, sizeof (void *));
00159 
00160   pool->zero_elements = zero_elements != FALSE;
00161 
00162   pool->allocated_elements = 0;
00163   
00164   /* pick a size for the first block; it increases
00165    * for each block we need to allocate. This is
00166    * actually half the initial block size
00167    * since _dbus_mem_pool_alloc() unconditionally
00168    * doubles it prior to creating a new block.  */
00169   pool->block_size = pool->element_size * 8;
00170 
00171   _dbus_assert ((pool->block_size %
00172                  pool->element_size) == 0);
00173   
00174   return pool;
00175 }
00176 
00182 void
00183 _dbus_mem_pool_free (DBusMemPool *pool)
00184 {
00185   DBusMemBlock *block;
00186 
00187   block = pool->blocks;
00188   while (block != NULL)
00189     {
00190       DBusMemBlock *next = block->next;
00191 
00192       dbus_free (block);
00193 
00194       block = next;
00195     }
00196 
00197   dbus_free (pool);
00198 }
00199 
00207 void*
00208 _dbus_mem_pool_alloc (DBusMemPool *pool)
00209 {
00210 #ifdef DBUS_BUILD_TESTS
00211   if (_dbus_disable_mem_pools ())
00212     {
00213       DBusMemBlock *block;
00214       int alloc_size;
00215       
00216       /* This is obviously really silly, but it's
00217        * debug-mode-only code that is compiled out
00218        * when tests are disabled (_dbus_disable_mem_pools()
00219        * is a constant expression FALSE so this block
00220        * should vanish)
00221        */
00222       
00223       alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING +
00224         pool->element_size;
00225       
00226       if (pool->zero_elements)
00227         block = dbus_malloc0 (alloc_size);
00228       else
00229         block = dbus_malloc (alloc_size);
00230 
00231       if (block != NULL)
00232         {
00233           block->next = pool->blocks;
00234           pool->blocks = block;
00235           pool->allocated_elements += 1;
00236 
00237           return (void*) &block->elements[0];
00238         }
00239       else
00240         return NULL;
00241     }
00242   else
00243 #endif
00244     {
00245       if (_dbus_decrement_fail_alloc_counter ())
00246         {
00247           _dbus_verbose (" FAILING mempool alloc\n");
00248           return NULL;
00249         }
00250       else if (pool->free_elements)
00251         {
00252           DBusFreedElement *element = pool->free_elements;
00253 
00254           pool->free_elements = pool->free_elements->next;
00255 
00256           if (pool->zero_elements)
00257             memset (element, '\0', pool->element_size);
00258 
00259           pool->allocated_elements += 1;
00260           
00261           return element;
00262         }
00263       else
00264         {
00265           void *element;
00266       
00267           if (pool->blocks == NULL ||
00268               pool->blocks->used_so_far == pool->block_size)
00269             {
00270               /* Need a new block */
00271               DBusMemBlock *block;
00272               int alloc_size;
00273 #ifdef DBUS_BUILD_TESTS
00274               int saved_counter;
00275 #endif
00276           
00277               if (pool->block_size <= _DBUS_INT_MAX / 4) /* avoid overflow */
00278                 {
00279                   /* use a larger block size for our next block */
00280                   pool->block_size *= 2;
00281                   _dbus_assert ((pool->block_size %
00282                                  pool->element_size) == 0);
00283                 }
00284 
00285               alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING + pool->block_size;
00286 
00287 #ifdef DBUS_BUILD_TESTS
00288               /* We save/restore the counter, so that memory pools won't
00289                * cause a given function to have different number of
00290                * allocations on different invocations. i.e.  when testing
00291                * we want consistent alloc patterns. So we skip our
00292                * malloc here for purposes of failed alloc simulation.
00293                */
00294               saved_counter = _dbus_get_fail_alloc_counter ();
00295               _dbus_set_fail_alloc_counter (_DBUS_INT_MAX);
00296 #endif
00297           
00298               if (pool->zero_elements)
00299                 block = dbus_malloc0 (alloc_size);
00300               else
00301                 block = dbus_malloc (alloc_size);
00302 
00303 #ifdef DBUS_BUILD_TESTS
00304               _dbus_set_fail_alloc_counter (saved_counter);
00305               _dbus_assert (saved_counter == _dbus_get_fail_alloc_counter ());
00306 #endif
00307           
00308               if (block == NULL)
00309                 return NULL;
00310 
00311               block->used_so_far = 0;
00312               block->next = pool->blocks;
00313               pool->blocks = block;          
00314             }
00315       
00316           element = &pool->blocks->elements[pool->blocks->used_so_far];
00317           
00318           pool->blocks->used_so_far += pool->element_size;
00319 
00320           pool->allocated_elements += 1;
00321           
00322           return element;
00323         }
00324     }
00325 }
00326 
00335 dbus_bool_t
00336 _dbus_mem_pool_dealloc (DBusMemPool *pool,
00337                         void        *element)
00338 {
00339 #ifdef DBUS_BUILD_TESTS
00340   if (_dbus_disable_mem_pools ())
00341     {
00342       DBusMemBlock *block;
00343       DBusMemBlock *prev;
00344 
00345       /* mmm, fast. ;-) debug-only code, so doesn't matter. */
00346       
00347       prev = NULL;
00348       block = pool->blocks;
00349 
00350       while (block != NULL)
00351         {
00352           if (block->elements == (unsigned char*) element)
00353             {
00354               if (prev)
00355                 prev->next = block->next;
00356               else
00357                 pool->blocks = block->next;
00358               
00359               dbus_free (block);
00360 
00361               _dbus_assert (pool->allocated_elements > 0);
00362               pool->allocated_elements -= 1;
00363               
00364               if (pool->allocated_elements == 0)
00365                 _dbus_assert (pool->blocks == NULL);
00366               
00367               return pool->blocks == NULL;
00368             }
00369           prev = block;
00370           block = block->next;
00371         }
00372       
00373       _dbus_assert_not_reached ("freed nonexistent block");
00374       return FALSE;
00375     }
00376   else
00377 #endif
00378     {
00379       DBusFreedElement *freed;
00380       
00381       freed = element;
00382       freed->next = pool->free_elements;
00383       pool->free_elements = freed;
00384       
00385       _dbus_assert (pool->allocated_elements > 0);
00386       pool->allocated_elements -= 1;
00387       
00388       return pool->allocated_elements == 0;
00389     }
00390 }
00391 
00394 #ifdef DBUS_BUILD_TESTS
00395 #include "dbus-test.h"
00396 #include <stdio.h>
00397 #include <time.h>
00398 
00399 static void
00400 time_for_size (int size)
00401 {
00402   int i;
00403   int j;
00404   clock_t start;
00405   clock_t end;
00406 #define FREE_ARRAY_SIZE 512
00407 #define N_ITERATIONS FREE_ARRAY_SIZE * 512
00408   void *to_free[FREE_ARRAY_SIZE];
00409   DBusMemPool *pool;
00410 
00411   _dbus_verbose ("Timings for size %d\n", size);
00412   
00413   _dbus_verbose (" malloc\n");
00414   
00415   start = clock ();
00416   
00417   i = 0;
00418   j = 0;
00419   while (i < N_ITERATIONS)
00420     {
00421       to_free[j] = dbus_malloc (size);
00422       _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */
00423 
00424       ++j;
00425 
00426       if (j == FREE_ARRAY_SIZE)
00427         {
00428           j = 0;
00429           while (j < FREE_ARRAY_SIZE)
00430             {
00431               dbus_free (to_free[j]);
00432               ++j;
00433             }
00434 
00435           j = 0;
00436         }
00437       
00438       ++i;
00439     }
00440 
00441   end = clock ();
00442 
00443   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
00444                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
00445 
00446 
00447 
00448   _dbus_verbose (" mempools\n");
00449   
00450   start = clock ();
00451 
00452   pool = _dbus_mem_pool_new (size, FALSE);
00453   
00454   i = 0;
00455   j = 0;
00456   while (i < N_ITERATIONS)
00457     {
00458       to_free[j] = _dbus_mem_pool_alloc (pool); 
00459       _dbus_assert (to_free[j] != NULL);  /* in a real app of course this is wrong */
00460 
00461       ++j;
00462 
00463       if (j == FREE_ARRAY_SIZE)
00464         {
00465           j = 0;
00466           while (j < FREE_ARRAY_SIZE)
00467             {
00468               _dbus_mem_pool_dealloc (pool, to_free[j]);
00469               ++j;
00470             }
00471 
00472           j = 0;
00473         }
00474       
00475       ++i;
00476     }
00477 
00478   _dbus_mem_pool_free (pool);
00479   
00480   end = clock ();
00481 
00482   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
00483                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
00484 
00485   _dbus_verbose (" zeroed malloc\n");
00486     
00487   start = clock ();
00488   
00489   i = 0;
00490   j = 0;
00491   while (i < N_ITERATIONS)
00492     {
00493       to_free[j] = dbus_malloc0 (size);
00494       _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */
00495 
00496       ++j;
00497 
00498       if (j == FREE_ARRAY_SIZE)
00499         {
00500           j = 0;
00501           while (j < FREE_ARRAY_SIZE)
00502             {
00503               dbus_free (to_free[j]);
00504               ++j;
00505             }
00506 
00507           j = 0;
00508         }
00509       
00510       ++i;
00511     }
00512 
00513   end = clock ();
00514 
00515   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
00516                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
00517   
00518   _dbus_verbose (" zeroed mempools\n");
00519   
00520   start = clock ();
00521 
00522   pool = _dbus_mem_pool_new (size, TRUE);
00523   
00524   i = 0;
00525   j = 0;
00526   while (i < N_ITERATIONS)
00527     {
00528       to_free[j] = _dbus_mem_pool_alloc (pool); 
00529       _dbus_assert (to_free[j] != NULL);  /* in a real app of course this is wrong */
00530 
00531       ++j;
00532 
00533       if (j == FREE_ARRAY_SIZE)
00534         {
00535           j = 0;
00536           while (j < FREE_ARRAY_SIZE)
00537             {
00538               _dbus_mem_pool_dealloc (pool, to_free[j]);
00539               ++j;
00540             }
00541 
00542           j = 0;
00543         }
00544       
00545       ++i;
00546     }
00547 
00548   _dbus_mem_pool_free (pool);
00549   
00550   end = clock ();
00551 
00552   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
00553                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
00554 }
00555 
00561 dbus_bool_t
00562 _dbus_mem_pool_test (void)
00563 {
00564   int i;
00565   int element_sizes[] = { 4, 8, 16, 50, 124 };
00566   
00567   i = 0;
00568   while (i < _DBUS_N_ELEMENTS (element_sizes))
00569     {
00570       time_for_size (element_sizes[i]);
00571       ++i;
00572     }
00573   
00574   return TRUE;
00575 }
00576 
00577 #endif /* DBUS_BUILD_TESTS */

Generated on Tue Feb 24 16:40:39 2009 for D-Bus by  doxygen 1.5.1