2007-07-13 Havoc Pennington <hp@redhat.com>
[platform/upstream/dbus.git] / dbus / dbus-mempool.c
1 /* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
2 /* dbus-mempool.h Memory pools
3  * 
4  * Copyright (C) 2002, 2003  Red Hat, Inc.
5  *
6  * Licensed under the Academic Free License version 2.1
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 #include "dbus-internals.h"
26
27 /**
28  * @defgroup DBusMemPool memory pools
29  * @ingroup  DBusInternals
30  * @brief DBusMemPool object
31  *
32  * Types and functions related to DBusMemPool.  A memory pool is used
33  * to decrease memory fragmentation/overhead and increase speed for
34  * blocks of small uniformly-sized objects. The main point is to avoid
35  * the overhead of a malloc block for each small object, speed is
36  * secondary.
37  */
38
39 /**
40  * @defgroup DBusMemPoolInternals Memory pool implementation details
41  * @ingroup  DBusInternals
42  * @brief DBusMemPool implementation details
43  *
44  * The guts of DBusMemPool.
45  *
46  * @{
47  */
48
49 /**
50  * typedef so DBusFreedElement struct can refer to itself.
51  */
52 typedef struct DBusFreedElement DBusFreedElement;
53
54 /**
55  * struct representing an element on the free list.
56  * We just cast freed elements to this so we can
57  * make a list out of them.
58  */
59 struct DBusFreedElement
60 {
61   DBusFreedElement *next; /**< next element of the free list */
62 };
63
64 /**
65  * The dummy size of the variable-length "elements"
66  * field in DBusMemBlock
67  */
68 #define ELEMENT_PADDING 4
69
70 /**
71  * Typedef for DBusMemBlock so the struct can recursively
72  * point to itself.
73  */
74 typedef struct DBusMemBlock DBusMemBlock;
75
76 /**
77  * DBusMemBlock object represents a single malloc()-returned
78  * block that gets chunked up into objects in the memory pool.
79  */
80 struct DBusMemBlock
81 {
82   DBusMemBlock *next;  /**< next block in the list, which is already used up;
83                         *   only saved so we can free all the blocks
84                         *   when we free the mem pool.
85                         */
86
87   /* this is a long so that "elements" is aligned */
88   long used_so_far;     /**< bytes of this block already allocated as elements. */
89   
90   unsigned char elements[ELEMENT_PADDING]; /**< the block data, actually allocated to required size */
91 };
92
93 /**
94  * Internals fields of DBusMemPool
95  */
96 struct DBusMemPool
97 {
98   int element_size;                /**< size of a single object in the pool */
99   int block_size;                  /**< size of most recently allocated block */
100   unsigned int zero_elements : 1;  /**< whether to zero-init allocated elements */
101
102   DBusFreedElement *free_elements; /**< a free list of elements to recycle */
103   DBusMemBlock *blocks;            /**< blocks of memory from malloc() */
104   int allocated_elements;          /**< Count of outstanding allocated elements */
105 };
106
107 /** @} */
108
109 /**
110  * @addtogroup DBusMemPool
111  *
112  * @{
113  */
114
115 /**
116  * @typedef DBusMemPool
117  *
118  * Opaque object representing a memory pool. Memory pools allow
119  * avoiding per-malloc-block memory overhead when allocating a lot of
120  * small objects that are all the same size. They are slightly
121  * faster than calling malloc() also.
122  */
123
124 /**
125  * Creates a new memory pool, or returns #NULL on failure.  Objects in
126  * the pool must be at least sizeof(void*) bytes each, due to the way
127  * memory pools work. To avoid creating 64 bit problems, this means at
128  * least 8 bytes on all platforms, unless you are 4 bytes on 32-bit
129  * and 8 bytes on 64-bit.
130  *
131  * @param element_size size of an element allocated from the pool.
132  * @param zero_elements whether to zero-initialize elements
133  * @returns the new pool or #NULL
134  */
135 DBusMemPool*
136 _dbus_mem_pool_new (int element_size,
137                     dbus_bool_t zero_elements)
138 {
139   DBusMemPool *pool;
140
141   pool = dbus_new0 (DBusMemPool, 1);
142   if (pool == NULL)
143     return NULL;
144
145   /* Make the element size at least 8 bytes. */
146   if (element_size < 8)
147     element_size = 8;
148   
149   /* these assertions are equivalent but the first is more clear
150    * to programmers that see it fail.
151    */
152   _dbus_assert (element_size >= (int) sizeof (void*));
153   _dbus_assert (element_size >= (int) sizeof (DBusFreedElement));
154
155   /* align the element size to a pointer boundary so we won't get bus
156    * errors under other architectures.  
157    */
158   pool->element_size = _DBUS_ALIGN_VALUE (element_size, sizeof (void *));
159
160   pool->zero_elements = zero_elements != FALSE;
161
162   pool->allocated_elements = 0;
163   
164   /* pick a size for the first block; it increases
165    * for each block we need to allocate. This is
166    * actually half the initial block size
167    * since _dbus_mem_pool_alloc() unconditionally
168    * doubles it prior to creating a new block.  */
169   pool->block_size = pool->element_size * 8;
170
171   _dbus_assert ((pool->block_size %
172                  pool->element_size) == 0);
173   
174   return pool;
175 }
176
177 /**
178  * Frees a memory pool (and all elements allocated from it).
179  *
180  * @param pool the memory pool.
181  */
182 void
183 _dbus_mem_pool_free (DBusMemPool *pool)
184 {
185   DBusMemBlock *block;
186
187   block = pool->blocks;
188   while (block != NULL)
189     {
190       DBusMemBlock *next = block->next;
191
192       dbus_free (block);
193
194       block = next;
195     }
196
197   dbus_free (pool);
198 }
199
200 /**
201  * Allocates an object from the memory pool.
202  * The object must be freed with _dbus_mem_pool_dealloc().
203  *
204  * @param pool the memory pool
205  * @returns the allocated object or #NULL if no memory.
206  */
207 void*
208 _dbus_mem_pool_alloc (DBusMemPool *pool)
209 {
210 #ifdef DBUS_BUILD_TESTS
211   if (_dbus_disable_mem_pools ())
212     {
213       DBusMemBlock *block;
214       int alloc_size;
215       
216       /* This is obviously really silly, but it's
217        * debug-mode-only code that is compiled out
218        * when tests are disabled (_dbus_disable_mem_pools()
219        * is a constant expression FALSE so this block
220        * should vanish)
221        */
222       
223       alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING +
224         pool->element_size;
225       
226       if (pool->zero_elements)
227         block = dbus_malloc0 (alloc_size);
228       else
229         block = dbus_malloc (alloc_size);
230
231       if (block != NULL)
232         {
233           block->next = pool->blocks;
234           pool->blocks = block;
235           pool->allocated_elements += 1;
236
237           return (void*) &block->elements[0];
238         }
239       else
240         return NULL;
241     }
242   else
243 #endif
244     {
245       if (_dbus_decrement_fail_alloc_counter ())
246         {
247           _dbus_verbose (" FAILING mempool alloc\n");
248           return NULL;
249         }
250       else if (pool->free_elements)
251         {
252           DBusFreedElement *element = pool->free_elements;
253
254           pool->free_elements = pool->free_elements->next;
255
256           if (pool->zero_elements)
257             memset (element, '\0', pool->element_size);
258
259           pool->allocated_elements += 1;
260           
261           return element;
262         }
263       else
264         {
265           void *element;
266       
267           if (pool->blocks == NULL ||
268               pool->blocks->used_so_far == pool->block_size)
269             {
270               /* Need a new block */
271               DBusMemBlock *block;
272               int alloc_size;
273 #ifdef DBUS_BUILD_TESTS
274               int saved_counter;
275 #endif
276           
277               if (pool->block_size <= _DBUS_INT_MAX / 4) /* avoid overflow */
278                 {
279                   /* use a larger block size for our next block */
280                   pool->block_size *= 2;
281                   _dbus_assert ((pool->block_size %
282                                  pool->element_size) == 0);
283                 }
284
285               alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING + pool->block_size;
286
287 #ifdef DBUS_BUILD_TESTS
288               /* We save/restore the counter, so that memory pools won't
289                * cause a given function to have different number of
290                * allocations on different invocations. i.e.  when testing
291                * we want consistent alloc patterns. So we skip our
292                * malloc here for purposes of failed alloc simulation.
293                */
294               saved_counter = _dbus_get_fail_alloc_counter ();
295               _dbus_set_fail_alloc_counter (_DBUS_INT_MAX);
296 #endif
297           
298               if (pool->zero_elements)
299                 block = dbus_malloc0 (alloc_size);
300               else
301                 block = dbus_malloc (alloc_size);
302
303 #ifdef DBUS_BUILD_TESTS
304               _dbus_set_fail_alloc_counter (saved_counter);
305               _dbus_assert (saved_counter == _dbus_get_fail_alloc_counter ());
306 #endif
307           
308               if (block == NULL)
309                 return NULL;
310
311               block->used_so_far = 0;
312               block->next = pool->blocks;
313               pool->blocks = block;          
314             }
315       
316           element = &pool->blocks->elements[pool->blocks->used_so_far];
317           
318           pool->blocks->used_so_far += pool->element_size;
319
320           pool->allocated_elements += 1;
321           
322           return element;
323         }
324     }
325 }
326
327 /**
328  * Deallocates an object previously created with
329  * _dbus_mem_pool_alloc(). The previous object
330  * must have come from this same pool.
331  * @param pool the memory pool
332  * @param element the element earlier allocated.
333  * @returns #TRUE if there are no remaining allocated elements
334  */
335 dbus_bool_t
336 _dbus_mem_pool_dealloc (DBusMemPool *pool,
337                         void        *element)
338 {
339 #ifdef DBUS_BUILD_TESTS
340   if (_dbus_disable_mem_pools ())
341     {
342       DBusMemBlock *block;
343       DBusMemBlock *prev;
344
345       /* mmm, fast. ;-) debug-only code, so doesn't matter. */
346       
347       prev = NULL;
348       block = pool->blocks;
349
350       while (block != NULL)
351         {
352           if (block->elements == (unsigned char*) element)
353             {
354               if (prev)
355                 prev->next = block->next;
356               else
357                 pool->blocks = block->next;
358               
359               dbus_free (block);
360
361               _dbus_assert (pool->allocated_elements > 0);
362               pool->allocated_elements -= 1;
363               
364               if (pool->allocated_elements == 0)
365                 _dbus_assert (pool->blocks == NULL);
366               
367               return pool->blocks == NULL;
368             }
369           prev = block;
370           block = block->next;
371         }
372       
373       _dbus_assert_not_reached ("freed nonexistent block");
374       return FALSE;
375     }
376   else
377 #endif
378     {
379       DBusFreedElement *freed;
380       
381       freed = element;
382       freed->next = pool->free_elements;
383       pool->free_elements = freed;
384       
385       _dbus_assert (pool->allocated_elements > 0);
386       pool->allocated_elements -= 1;
387       
388       return pool->allocated_elements == 0;
389     }
390 }
391
392 /** @} */
393
394 #ifdef DBUS_BUILD_TESTS
395 #include "dbus-test.h"
396 #include <stdio.h>
397 #include <time.h>
398
399 static void
400 time_for_size (int size)
401 {
402   int i;
403   int j;
404   clock_t start;
405   clock_t end;
406 #define FREE_ARRAY_SIZE 512
407 #define N_ITERATIONS FREE_ARRAY_SIZE * 512
408   void *to_free[FREE_ARRAY_SIZE];
409   DBusMemPool *pool;
410
411   _dbus_verbose ("Timings for size %d\n", size);
412   
413   _dbus_verbose (" malloc\n");
414   
415   start = clock ();
416   
417   i = 0;
418   j = 0;
419   while (i < N_ITERATIONS)
420     {
421       to_free[j] = dbus_malloc (size);
422       _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */
423
424       ++j;
425
426       if (j == FREE_ARRAY_SIZE)
427         {
428           j = 0;
429           while (j < FREE_ARRAY_SIZE)
430             {
431               dbus_free (to_free[j]);
432               ++j;
433             }
434
435           j = 0;
436         }
437       
438       ++i;
439     }
440
441   end = clock ();
442
443   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
444                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
445
446
447
448   _dbus_verbose (" mempools\n");
449   
450   start = clock ();
451
452   pool = _dbus_mem_pool_new (size, FALSE);
453   
454   i = 0;
455   j = 0;
456   while (i < N_ITERATIONS)
457     {
458       to_free[j] = _dbus_mem_pool_alloc (pool); 
459       _dbus_assert (to_free[j] != NULL);  /* in a real app of course this is wrong */
460
461       ++j;
462
463       if (j == FREE_ARRAY_SIZE)
464         {
465           j = 0;
466           while (j < FREE_ARRAY_SIZE)
467             {
468               _dbus_mem_pool_dealloc (pool, to_free[j]);
469               ++j;
470             }
471
472           j = 0;
473         }
474       
475       ++i;
476     }
477
478   _dbus_mem_pool_free (pool);
479   
480   end = clock ();
481
482   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
483                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
484
485   _dbus_verbose (" zeroed malloc\n");
486     
487   start = clock ();
488   
489   i = 0;
490   j = 0;
491   while (i < N_ITERATIONS)
492     {
493       to_free[j] = dbus_malloc0 (size);
494       _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */
495
496       ++j;
497
498       if (j == FREE_ARRAY_SIZE)
499         {
500           j = 0;
501           while (j < FREE_ARRAY_SIZE)
502             {
503               dbus_free (to_free[j]);
504               ++j;
505             }
506
507           j = 0;
508         }
509       
510       ++i;
511     }
512
513   end = clock ();
514
515   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
516                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
517   
518   _dbus_verbose (" zeroed mempools\n");
519   
520   start = clock ();
521
522   pool = _dbus_mem_pool_new (size, TRUE);
523   
524   i = 0;
525   j = 0;
526   while (i < N_ITERATIONS)
527     {
528       to_free[j] = _dbus_mem_pool_alloc (pool); 
529       _dbus_assert (to_free[j] != NULL);  /* in a real app of course this is wrong */
530
531       ++j;
532
533       if (j == FREE_ARRAY_SIZE)
534         {
535           j = 0;
536           while (j < FREE_ARRAY_SIZE)
537             {
538               _dbus_mem_pool_dealloc (pool, to_free[j]);
539               ++j;
540             }
541
542           j = 0;
543         }
544       
545       ++i;
546     }
547
548   _dbus_mem_pool_free (pool);
549   
550   end = clock ();
551
552   _dbus_verbose ("  created/destroyed %d elements in %g seconds\n",
553                  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
554 }
555
556 /**
557  * @ingroup DBusMemPoolInternals
558  * Unit test for DBusMemPool
559  * @returns #TRUE on success.
560  */
561 dbus_bool_t
562 _dbus_mem_pool_test (void)
563 {
564   int i;
565   int element_sizes[] = { 4, 8, 16, 50, 124 };
566   
567   i = 0;
568   while (i < _DBUS_N_ELEMENTS (element_sizes))
569     {
570       time_for_size (element_sizes[i]);
571       ++i;
572     }
573   
574   return TRUE;
575 }
576
577 #endif /* DBUS_BUILD_TESTS */