1 /* -*- mode: C; c-file-style: "gnu" -*- */
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*
_dbus_mem_pool_new(int element_size,dbus_bool_t zero_elements)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
_dbus_mem_pool_free(DBusMemPool * pool)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*
_dbus_mem_pool_alloc(DBusMemPool * pool)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
_dbus_mem_pool_dealloc(DBusMemPool * pool,void * element)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
time_for_size(int size)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
_dbus_mem_pool_test(void)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 */
578