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