D-Bus 1.4.20

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