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*
_dbus_mem_pool_new(int element_size,dbus_bool_t zero_elements)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
_dbus_mem_pool_free(DBusMemPool * pool)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*
_dbus_mem_pool_alloc(DBusMemPool * pool)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
_dbus_mem_pool_dealloc(DBusMemPool * pool,void * element)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 /** @} */
394
395 #ifdef DBUS_BUILD_TESTS
396 #include "dbus-test.h"
397 #include <stdio.h>
398 #include <time.h>
399
400 static void
time_for_size(int size)401 time_for_size (int size)
402 {
403 int i;
404 int j;
405 clock_t start;
406 clock_t end;
407 #define FREE_ARRAY_SIZE 512
408 #define N_ITERATIONS FREE_ARRAY_SIZE * 512
409 void *to_free[FREE_ARRAY_SIZE];
410 DBusMemPool *pool;
411
412 _dbus_verbose ("Timings for size %d\n", size);
413
414 _dbus_verbose (" malloc\n");
415
416 start = clock ();
417
418 i = 0;
419 j = 0;
420 while (i < N_ITERATIONS)
421 {
422 to_free[j] = dbus_malloc (size);
423 _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */
424
425 ++j;
426
427 if (j == FREE_ARRAY_SIZE)
428 {
429 j = 0;
430 while (j < FREE_ARRAY_SIZE)
431 {
432 dbus_free (to_free[j]);
433 ++j;
434 }
435
436 j = 0;
437 }
438
439 ++i;
440 }
441
442 end = clock ();
443
444 _dbus_verbose (" created/destroyed %d elements in %g seconds\n",
445 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
446
447
448
449 _dbus_verbose (" mempools\n");
450
451 start = clock ();
452
453 pool = _dbus_mem_pool_new (size, FALSE);
454
455 i = 0;
456 j = 0;
457 while (i < N_ITERATIONS)
458 {
459 to_free[j] = _dbus_mem_pool_alloc (pool);
460 _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */
461
462 ++j;
463
464 if (j == FREE_ARRAY_SIZE)
465 {
466 j = 0;
467 while (j < FREE_ARRAY_SIZE)
468 {
469 _dbus_mem_pool_dealloc (pool, to_free[j]);
470 ++j;
471 }
472
473 j = 0;
474 }
475
476 ++i;
477 }
478
479 _dbus_mem_pool_free (pool);
480
481 end = clock ();
482
483 _dbus_verbose (" created/destroyed %d elements in %g seconds\n",
484 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
485
486 _dbus_verbose (" zeroed malloc\n");
487
488 start = clock ();
489
490 i = 0;
491 j = 0;
492 while (i < N_ITERATIONS)
493 {
494 to_free[j] = dbus_malloc0 (size);
495 _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */
496
497 ++j;
498
499 if (j == FREE_ARRAY_SIZE)
500 {
501 j = 0;
502 while (j < FREE_ARRAY_SIZE)
503 {
504 dbus_free (to_free[j]);
505 ++j;
506 }
507
508 j = 0;
509 }
510
511 ++i;
512 }
513
514 end = clock ();
515
516 _dbus_verbose (" created/destroyed %d elements in %g seconds\n",
517 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
518
519 _dbus_verbose (" zeroed mempools\n");
520
521 start = clock ();
522
523 pool = _dbus_mem_pool_new (size, TRUE);
524
525 i = 0;
526 j = 0;
527 while (i < N_ITERATIONS)
528 {
529 to_free[j] = _dbus_mem_pool_alloc (pool);
530 _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */
531
532 ++j;
533
534 if (j == FREE_ARRAY_SIZE)
535 {
536 j = 0;
537 while (j < FREE_ARRAY_SIZE)
538 {
539 _dbus_mem_pool_dealloc (pool, to_free[j]);
540 ++j;
541 }
542
543 j = 0;
544 }
545
546 ++i;
547 }
548
549 _dbus_mem_pool_free (pool);
550
551 end = clock ();
552
553 _dbus_verbose (" created/destroyed %d elements in %g seconds\n",
554 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
555 }
556
557 /**
558 * @ingroup DBusMemPoolInternals
559 * Unit test for DBusMemPool
560 * @returns #TRUE on success.
561 */
562 dbus_bool_t
_dbus_mem_pool_test(void)563 _dbus_mem_pool_test (void)
564 {
565 int i;
566 int element_sizes[] = { 4, 8, 16, 50, 124 };
567
568 i = 0;
569 while (i < _DBUS_N_ELEMENTS (element_sizes))
570 {
571 time_for_size (element_sizes[i]);
572 ++i;
573 }
574
575 return TRUE;
576 }
577
578 #endif /* DBUS_BUILD_TESTS */
579