D-Bus  1.10.12
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 #include "dbus-valgrind-internal.h"
00028 
00054 typedef struct DBusFreedElement DBusFreedElement;
00055 
00061 struct DBusFreedElement
00062 {
00063   DBusFreedElement *next; 
00064 };
00065 
00070 #define ELEMENT_PADDING 4
00071 
00076 typedef struct DBusMemBlock DBusMemBlock;
00077 
00082 struct DBusMemBlock
00083 {
00084   DBusMemBlock *next;  
00089   /* this is a long so that "elements" is aligned */
00090   long used_so_far;     
00092   unsigned char elements[ELEMENT_PADDING]; 
00093 };
00094 
00098 struct DBusMemPool
00099 {
00100   int element_size;                
00101   int block_size;                  
00102   unsigned int zero_elements : 1;  
00104   DBusFreedElement *free_elements; 
00105   DBusMemBlock *blocks;            
00106   int allocated_elements;          
00107 };
00108 
00137 DBusMemPool*
00138 _dbus_mem_pool_new (int element_size,
00139                     dbus_bool_t zero_elements)
00140 {
00141   DBusMemPool *pool;
00142 
00143   pool = dbus_new0 (DBusMemPool, 1);
00144   if (pool == NULL)
00145     return NULL;
00146 
00147   /* Make the element size at least 8 bytes. */
00148   if (element_size < 8)
00149     element_size = 8;
00150   
00151   /* these assertions are equivalent but the first is more clear
00152    * to programmers that see it fail.
00153    */
00154   _dbus_assert (element_size >= (int) sizeof (void*));
00155   _dbus_assert (element_size >= (int) sizeof (DBusFreedElement));
00156 
00157   /* align the element size to a pointer boundary so we won't get bus
00158    * errors under other architectures.  
00159    */
00160   pool->element_size = _DBUS_ALIGN_VALUE (element_size, sizeof (void *));
00161 
00162   pool->zero_elements = zero_elements != FALSE;
00163 
00164   pool->allocated_elements = 0;
00165   
00166   /* pick a size for the first block; it increases
00167    * for each block we need to allocate. This is
00168    * actually half the initial block size
00169    * since _dbus_mem_pool_alloc() unconditionally
00170    * doubles it prior to creating a new block.  */
00171   pool->block_size = pool->element_size * 8;
00172 
00173   _dbus_assert ((pool->block_size %
00174                  pool->element_size) == 0);
00175 
00176   VALGRIND_CREATE_MEMPOOL (pool, 0, zero_elements);
00177 
00178   return pool;
00179 }
00180 
00186 void
00187 _dbus_mem_pool_free (DBusMemPool *pool)
00188 {
00189   DBusMemBlock *block;
00190 
00191   VALGRIND_DESTROY_MEMPOOL (pool);
00192 
00193   block = pool->blocks;
00194   while (block != NULL)
00195     {
00196       DBusMemBlock *next = block->next;
00197 
00198       dbus_free (block);
00199 
00200       block = next;
00201     }
00202 
00203   dbus_free (pool);
00204 }
00205 
00213 void*
00214 _dbus_mem_pool_alloc (DBusMemPool *pool)
00215 {
00216 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
00217   if (_dbus_disable_mem_pools ())
00218     {
00219       DBusMemBlock *block;
00220       int alloc_size;
00221       
00222       /* This is obviously really silly, but it's
00223        * debug-mode-only code that is compiled out
00224        * when tests are disabled (_dbus_disable_mem_pools()
00225        * is a constant expression FALSE so this block
00226        * should vanish)
00227        */
00228       
00229       alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING +
00230         pool->element_size;
00231       
00232       if (pool->zero_elements)
00233         block = dbus_malloc0 (alloc_size);
00234       else
00235         block = dbus_malloc (alloc_size);
00236 
00237       if (block != NULL)
00238         {
00239           block->next = pool->blocks;
00240           pool->blocks = block;
00241           pool->allocated_elements += 1;
00242 
00243           VALGRIND_MEMPOOL_ALLOC (pool, (void *) &block->elements[0],
00244               pool->element_size);
00245           return (void*) &block->elements[0];
00246         }
00247       else
00248         return NULL;
00249     }
00250   else
00251 #endif
00252     {
00253       if (_dbus_decrement_fail_alloc_counter ())
00254         {
00255           _dbus_verbose (" FAILING mempool alloc\n");
00256           return NULL;
00257         }
00258       else if (pool->free_elements)
00259         {
00260           DBusFreedElement *element = pool->free_elements;
00261 
00262           pool->free_elements = pool->free_elements->next;
00263 
00264           VALGRIND_MEMPOOL_ALLOC (pool, element, pool->element_size);
00265 
00266           if (pool->zero_elements)
00267             memset (element, '\0', pool->element_size);
00268 
00269           pool->allocated_elements += 1;
00270 
00271           return element;
00272         }
00273       else
00274         {
00275           void *element;
00276       
00277           if (pool->blocks == NULL ||
00278               pool->blocks->used_so_far == pool->block_size)
00279             {
00280               /* Need a new block */
00281               DBusMemBlock *block;
00282               int alloc_size;
00283 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
00284               int saved_counter;
00285 #endif
00286           
00287               if (pool->block_size <= _DBUS_INT_MAX / 4) /* avoid overflow */
00288                 {
00289                   /* use a larger block size for our next block */
00290                   pool->block_size *= 2;
00291                   _dbus_assert ((pool->block_size %
00292                                  pool->element_size) == 0);
00293                 }
00294 
00295               alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING + pool->block_size;
00296 
00297 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
00298               /* We save/restore the counter, so that memory pools won't
00299                * cause a given function to have different number of
00300                * allocations on different invocations. i.e.  when testing
00301                * we want consistent alloc patterns. So we skip our
00302                * malloc here for purposes of failed alloc simulation.
00303                */
00304               saved_counter = _dbus_get_fail_alloc_counter ();
00305               _dbus_set_fail_alloc_counter (_DBUS_INT_MAX);
00306 #endif
00307           
00308               if (pool->zero_elements)
00309                 block = dbus_malloc0 (alloc_size);
00310               else
00311                 block = dbus_malloc (alloc_size);
00312 
00313 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
00314               _dbus_set_fail_alloc_counter (saved_counter);
00315               _dbus_assert (saved_counter == _dbus_get_fail_alloc_counter ());
00316 #endif
00317           
00318               if (block == NULL)
00319                 return NULL;
00320 
00321               block->used_so_far = 0;
00322               block->next = pool->blocks;
00323               pool->blocks = block;          
00324             }
00325       
00326           element = &pool->blocks->elements[pool->blocks->used_so_far];
00327           
00328           pool->blocks->used_so_far += pool->element_size;
00329 
00330           pool->allocated_elements += 1;
00331 
00332           VALGRIND_MEMPOOL_ALLOC (pool, element, pool->element_size);
00333           return element;
00334         }
00335     }
00336 }
00337 
00346 dbus_bool_t
00347 _dbus_mem_pool_dealloc (DBusMemPool *pool,
00348                         void        *element)
00349 {
00350   VALGRIND_MEMPOOL_FREE (pool, element);
00351 
00352 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
00353   if (_dbus_disable_mem_pools ())
00354     {
00355       DBusMemBlock *block;
00356       DBusMemBlock *prev;
00357 
00358       /* mmm, fast. ;-) debug-only code, so doesn't matter. */
00359       
00360       prev = NULL;
00361       block = pool->blocks;
00362 
00363       while (block != NULL)
00364         {
00365           if (block->elements == (unsigned char*) element)
00366             {
00367               if (prev)
00368                 prev->next = block->next;
00369               else
00370                 pool->blocks = block->next;
00371               
00372               dbus_free (block);
00373 
00374               _dbus_assert (pool->allocated_elements > 0);
00375               pool->allocated_elements -= 1;
00376               
00377               if (pool->allocated_elements == 0)
00378                 _dbus_assert (pool->blocks == NULL);
00379               
00380               return pool->blocks == NULL;
00381             }
00382           prev = block;
00383           block = block->next;
00384         }
00385       
00386       _dbus_assert_not_reached ("freed nonexistent block");
00387       return FALSE;
00388     }
00389   else
00390 #endif
00391     {
00392       DBusFreedElement *freed;
00393       
00394       freed = element;
00395       /* used for internal mempool administration */
00396       VALGRIND_MAKE_MEM_UNDEFINED (freed, sizeof (*freed));
00397 
00398       freed->next = pool->free_elements;
00399       pool->free_elements = freed;
00400       
00401       _dbus_assert (pool->allocated_elements > 0);
00402       pool->allocated_elements -= 1;
00403       
00404       return pool->allocated_elements == 0;
00405     }
00406 }
00407 
00408 #ifdef DBUS_ENABLE_STATS
00409 void
00410 _dbus_mem_pool_get_stats (DBusMemPool   *pool,
00411                           dbus_uint32_t *in_use_p,
00412                           dbus_uint32_t *in_free_list_p,
00413                           dbus_uint32_t *allocated_p)
00414 {
00415   DBusMemBlock *block;
00416   DBusFreedElement *freed;
00417   dbus_uint32_t in_use = 0;
00418   dbus_uint32_t in_free_list = 0;
00419   dbus_uint32_t allocated = 0;
00420 
00421   if (pool != NULL)
00422     {
00423       in_use = pool->element_size * pool->allocated_elements;
00424 
00425       for (freed = pool->free_elements; freed != NULL; freed = freed->next)
00426         {
00427           in_free_list += pool->element_size;
00428         }
00429 
00430       for (block = pool->blocks; block != NULL; block = block->next)
00431         {
00432           if (block == pool->blocks)
00433             allocated += pool->block_size;
00434           else
00435             allocated += block->used_so_far;
00436         }
00437     }
00438 
00439   if (in_use_p != NULL)
00440     *in_use_p = in_use;
00441 
00442   if (in_free_list_p != NULL)
00443     *in_free_list_p = in_free_list;
00444 
00445   if (allocated_p != NULL)
00446     *allocated_p = allocated;
00447 }
00448 #endif /* DBUS_ENABLE_STATS */
00449 
00452 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
00453 #include "dbus-test.h"
00454 #include <stdio.h>
00455 #include <time.h>
00456 
00457 static void
00458 time_for_size (int size)
00459 {
00460   int i;
00461   int j;
00462 #ifdef DBUS_ENABLE_VERBOSE_MODE
00463   clock_t start;
00464   clock_t end;
00465 #endif
00466 #define FREE_ARRAY_SIZE 512
00467 #define N_ITERATIONS FREE_ARRAY_SIZE * 512
00468   void *to_free[FREE_ARRAY_SIZE];
00469   DBusMemPool *pool;
00470 
00471   _dbus_verbose ("Timings for size %d\n", size);
00472   
00473   _dbus_verbose (" malloc\n");
00474   
00475 #ifdef DBUS_ENABLE_VERBOSE_MODE
00476   start = clock ();
00477 #endif
00478 
00479   i = 0;
00480   j = 0;
00481   while (i < N_ITERATIONS)
00482     {
00483       to_free[j] = dbus_malloc (size);
00484       _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */
00485 
00486       ++j;
00487 
00488       if (j == FREE_ARRAY_SIZE)
00489         {
00490           j = 0;
00491           while (j < FREE_ARRAY_SIZE)
00492             {
00493               dbus_free (to_free[j]);
00494               ++j;
00495             }
00496 
00497           j = 0;
00498         }
00499       
00500       ++i;
00501     }
00502 
00503 #ifdef DBUS_ENABLE_VERBOSE_MODE
00504   end = clock ();
00505 
00506   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
00507                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
00508 
00509 
00510 
00511   _dbus_verbose (" mempools\n");
00512   
00513   start = clock ();
00514 #endif
00515 
00516   pool = _dbus_mem_pool_new (size, FALSE);
00517   
00518   i = 0;
00519   j = 0;
00520   while (i < N_ITERATIONS)
00521     {
00522       to_free[j] = _dbus_mem_pool_alloc (pool); 
00523       _dbus_assert (to_free[j] != NULL);  /* in a real app of course this is wrong */
00524 
00525       ++j;
00526 
00527       if (j == FREE_ARRAY_SIZE)
00528         {
00529           j = 0;
00530           while (j < FREE_ARRAY_SIZE)
00531             {
00532               _dbus_mem_pool_dealloc (pool, to_free[j]);
00533               ++j;
00534             }
00535 
00536           j = 0;
00537         }
00538       
00539       ++i;
00540     }
00541 
00542   _dbus_mem_pool_free (pool);
00543   
00544 #ifdef DBUS_ENABLE_VERBOSE_MODE
00545   end = clock ();
00546 
00547   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
00548                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
00549 
00550   _dbus_verbose (" zeroed malloc\n");
00551     
00552   start = clock ();
00553 #endif
00554   
00555   i = 0;
00556   j = 0;
00557   while (i < N_ITERATIONS)
00558     {
00559       to_free[j] = dbus_malloc0 (size);
00560       _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */
00561 
00562       ++j;
00563 
00564       if (j == FREE_ARRAY_SIZE)
00565         {
00566           j = 0;
00567           while (j < FREE_ARRAY_SIZE)
00568             {
00569               dbus_free (to_free[j]);
00570               ++j;
00571             }
00572 
00573           j = 0;
00574         }
00575       
00576       ++i;
00577     }
00578 
00579 #ifdef DBUS_ENABLE_VERBOSE_MODE
00580   end = clock ();
00581 
00582   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
00583                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
00584   
00585   _dbus_verbose (" zeroed mempools\n");
00586   
00587   start = clock ();
00588 #endif
00589 
00590   pool = _dbus_mem_pool_new (size, TRUE);
00591   
00592   i = 0;
00593   j = 0;
00594   while (i < N_ITERATIONS)
00595     {
00596       to_free[j] = _dbus_mem_pool_alloc (pool); 
00597       _dbus_assert (to_free[j] != NULL);  /* in a real app of course this is wrong */
00598 
00599       ++j;
00600 
00601       if (j == FREE_ARRAY_SIZE)
00602         {
00603           j = 0;
00604           while (j < FREE_ARRAY_SIZE)
00605             {
00606               _dbus_mem_pool_dealloc (pool, to_free[j]);
00607               ++j;
00608             }
00609 
00610           j = 0;
00611         }
00612       
00613       ++i;
00614     }
00615 
00616   _dbus_mem_pool_free (pool);
00617   
00618 #ifdef DBUS_ENABLE_VERBOSE_MODE
00619   end = clock ();
00620 
00621   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
00622                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
00623 #endif
00624 }
00625 
00631 dbus_bool_t
00632 _dbus_mem_pool_test (void)
00633 {
00634   int i;
00635   int element_sizes[] = { 4, 8, 16, 50, 124 };
00636   
00637   i = 0;
00638   while (i < _DBUS_N_ELEMENTS (element_sizes))
00639     {
00640       time_for_size (element_sizes[i]);
00641       ++i;
00642     }
00643   
00644   return TRUE;
00645 }
00646 
00647 #endif /* DBUS_ENABLE_EMBEDDED_TESTS */