D-Bus  1.13.7
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 #include "dbus-valgrind-internal.h"
28 
55 
62 {
64 };
65 
70 #define ELEMENT_PADDING 4
71 
76 typedef struct DBusMemBlock DBusMemBlock;
77 
83 {
89  /* this is a long so that "elements" is aligned */
90  long used_so_far;
92  unsigned char elements[ELEMENT_PADDING];
93 };
94 
99 {
102  unsigned int zero_elements : 1;
107 };
108 
138 _dbus_mem_pool_new (int element_size,
139  dbus_bool_t zero_elements)
140 {
141  DBusMemPool *pool;
142 
143  pool = dbus_new0 (DBusMemPool, 1);
144  if (pool == NULL)
145  return NULL;
146 
147  /* Make the element size at least 8 bytes. */
148  if (element_size < 8)
149  element_size = 8;
150 
151  /* these assertions are equivalent but the first is more clear
152  * to programmers that see it fail.
153  */
154  _dbus_assert (element_size >= (int) sizeof (void*));
155  _dbus_assert (element_size >= (int) sizeof (DBusFreedElement));
156 
157  /* align the element size to a pointer boundary so we won't get bus
158  * errors under other architectures.
159  */
160  pool->element_size = _DBUS_ALIGN_VALUE (element_size, sizeof (void *));
161 
162  pool->zero_elements = zero_elements != FALSE;
163 
164  pool->allocated_elements = 0;
165 
166  /* pick a size for the first block; it increases
167  * for each block we need to allocate. This is
168  * actually half the initial block size
169  * since _dbus_mem_pool_alloc() unconditionally
170  * doubles it prior to creating a new block. */
171  pool->block_size = pool->element_size * 8;
172 
173  _dbus_assert ((pool->block_size %
174  pool->element_size) == 0);
175 
176  VALGRIND_CREATE_MEMPOOL (pool, 0, zero_elements);
177 
178  return pool;
179 }
180 
186 void
188 {
189  DBusMemBlock *block;
190 
191  VALGRIND_DESTROY_MEMPOOL (pool);
192 
193  block = pool->blocks;
194  while (block != NULL)
195  {
196  DBusMemBlock *next = block->next;
197 
198  dbus_free (block);
199 
200  block = next;
201  }
202 
203  dbus_free (pool);
204 }
205 
213 void*
215 {
216 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
217  if (_dbus_disable_mem_pools ())
218  {
219  DBusMemBlock *block;
220  int alloc_size;
221 
222  /* This is obviously really silly, but it's
223  * debug-mode-only code that is compiled out
224  * when tests are disabled (_dbus_disable_mem_pools()
225  * is a constant expression FALSE so this block
226  * should vanish)
227  */
228 
229  alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING +
230  pool->element_size;
231 
232  if (pool->zero_elements)
233  block = dbus_malloc0 (alloc_size);
234  else
235  block = dbus_malloc (alloc_size);
236 
237  if (block != NULL)
238  {
239  block->next = pool->blocks;
240  pool->blocks = block;
241  pool->allocated_elements += 1;
242 
243  VALGRIND_MEMPOOL_ALLOC (pool, (void *) &block->elements[0],
244  pool->element_size);
245  return (void*) &block->elements[0];
246  }
247  else
248  return NULL;
249  }
250  else
251 #endif
252  {
253  if (_dbus_decrement_fail_alloc_counter ())
254  {
255  _dbus_verbose (" FAILING mempool alloc\n");
256  return NULL;
257  }
258  else if (pool->free_elements)
259  {
260  DBusFreedElement *element = pool->free_elements;
261 
262  pool->free_elements = pool->free_elements->next;
263 
264  VALGRIND_MEMPOOL_ALLOC (pool, element, pool->element_size);
265 
266  if (pool->zero_elements)
267  memset (element, '\0', pool->element_size);
268 
269  pool->allocated_elements += 1;
270 
271  return element;
272  }
273  else
274  {
275  void *element;
276 
277  if (pool->blocks == NULL ||
278  pool->blocks->used_so_far == pool->block_size)
279  {
280  /* Need a new block */
281  DBusMemBlock *block;
282  int alloc_size;
283 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
284  int saved_counter;
285 #endif
286 
287  if (pool->block_size <= _DBUS_INT_MAX / 4) /* avoid overflow */
288  {
289  /* use a larger block size for our next block */
290  pool->block_size *= 2;
291  _dbus_assert ((pool->block_size %
292  pool->element_size) == 0);
293  }
294 
295  alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING + pool->block_size;
296 
297 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
298  /* We save/restore the counter, so that memory pools won't
299  * cause a given function to have different number of
300  * allocations on different invocations. i.e. when testing
301  * we want consistent alloc patterns. So we skip our
302  * malloc here for purposes of failed alloc simulation.
303  */
304  saved_counter = _dbus_get_fail_alloc_counter ();
305  _dbus_set_fail_alloc_counter (_DBUS_INT_MAX);
306 #endif
307 
308  if (pool->zero_elements)
309  block = dbus_malloc0 (alloc_size);
310  else
311  block = dbus_malloc (alloc_size);
312 
313 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
314  _dbus_set_fail_alloc_counter (saved_counter);
315  _dbus_assert (saved_counter == _dbus_get_fail_alloc_counter ());
316 #endif
317 
318  if (block == NULL)
319  return NULL;
320 
321  block->used_so_far = 0;
322  block->next = pool->blocks;
323  pool->blocks = block;
324  }
325 
326  element = &pool->blocks->elements[pool->blocks->used_so_far];
327 
328  pool->blocks->used_so_far += pool->element_size;
329 
330  pool->allocated_elements += 1;
331 
332  VALGRIND_MEMPOOL_ALLOC (pool, element, pool->element_size);
333  return element;
334  }
335  }
336 }
337 
348  void *element)
349 {
350  VALGRIND_MEMPOOL_FREE (pool, element);
351 
352 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
353  if (_dbus_disable_mem_pools ())
354  {
355  DBusMemBlock *block;
356  DBusMemBlock *prev;
357 
358  /* mmm, fast. ;-) debug-only code, so doesn't matter. */
359 
360  prev = NULL;
361  block = pool->blocks;
362 
363  while (block != NULL)
364  {
365  if (block->elements == (unsigned char*) element)
366  {
367  if (prev)
368  prev->next = block->next;
369  else
370  pool->blocks = block->next;
371 
372  dbus_free (block);
373 
374  _dbus_assert (pool->allocated_elements > 0);
375  pool->allocated_elements -= 1;
376 
377  if (pool->allocated_elements == 0)
378  _dbus_assert (pool->blocks == NULL);
379 
380  return pool->blocks == NULL;
381  }
382  prev = block;
383  block = block->next;
384  }
385 
386  _dbus_assert_not_reached ("freed nonexistent block");
387  return FALSE;
388  }
389  else
390 #endif
391  {
392  DBusFreedElement *freed;
393 
394  freed = element;
395  /* used for internal mempool administration */
396  VALGRIND_MAKE_MEM_UNDEFINED (freed, sizeof (*freed));
397 
398  freed->next = pool->free_elements;
399  pool->free_elements = freed;
400 
401  _dbus_assert (pool->allocated_elements > 0);
402  pool->allocated_elements -= 1;
403 
404  return pool->allocated_elements == 0;
405  }
406 }
407 
408 #ifdef DBUS_ENABLE_STATS
409 void
410 _dbus_mem_pool_get_stats (DBusMemPool *pool,
411  dbus_uint32_t *in_use_p,
412  dbus_uint32_t *in_free_list_p,
413  dbus_uint32_t *allocated_p)
414 {
415  DBusMemBlock *block;
416  DBusFreedElement *freed;
417  dbus_uint32_t in_use = 0;
418  dbus_uint32_t in_free_list = 0;
419  dbus_uint32_t allocated = 0;
420 
421  if (pool != NULL)
422  {
423  in_use = pool->element_size * pool->allocated_elements;
424 
425  for (freed = pool->free_elements; freed != NULL; freed = freed->next)
426  {
427  in_free_list += pool->element_size;
428  }
429 
430  for (block = pool->blocks; block != NULL; block = block->next)
431  {
432  if (block == pool->blocks)
433  allocated += pool->block_size;
434  else
435  allocated += block->used_so_far;
436  }
437  }
438 
439  if (in_use_p != NULL)
440  *in_use_p = in_use;
441 
442  if (in_free_list_p != NULL)
443  *in_free_list_p = in_free_list;
444 
445  if (allocated_p != NULL)
446  *allocated_p = allocated;
447 }
448 #endif /* DBUS_ENABLE_STATS */
449 
452 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
453 #include "dbus-test.h"
454 #include <stdio.h>
455 #include <time.h>
456 
457 static void
458 time_for_size (int size)
459 {
460  int i;
461  int j;
462 #ifdef DBUS_ENABLE_VERBOSE_MODE
463  clock_t start;
464  clock_t end;
465 #endif
466 #define FREE_ARRAY_SIZE 512
467 #define N_ITERATIONS FREE_ARRAY_SIZE * 512
468  void *to_free[FREE_ARRAY_SIZE];
469  DBusMemPool *pool;
470 
471  _dbus_verbose ("Timings for size %d\n", size);
472 
473  _dbus_verbose (" malloc\n");
474 
475 #ifdef DBUS_ENABLE_VERBOSE_MODE
476  start = clock ();
477 #endif
478 
479  i = 0;
480  j = 0;
481  while (i < N_ITERATIONS)
482  {
483  to_free[j] = dbus_malloc (size);
484  _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */
485 
486  ++j;
487 
488  if (j == FREE_ARRAY_SIZE)
489  {
490  j = 0;
491  while (j < FREE_ARRAY_SIZE)
492  {
493  dbus_free (to_free[j]);
494  ++j;
495  }
496 
497  j = 0;
498  }
499 
500  ++i;
501  }
502 
503 #ifdef DBUS_ENABLE_VERBOSE_MODE
504  end = clock ();
505 
506  _dbus_verbose (" created/destroyed %d elements in %g seconds\n",
507  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
508 
509 
510 
511  _dbus_verbose (" mempools\n");
512 
513  start = clock ();
514 #endif
515 
516  pool = _dbus_mem_pool_new (size, FALSE);
517 
518  i = 0;
519  j = 0;
520  while (i < N_ITERATIONS)
521  {
522  to_free[j] = _dbus_mem_pool_alloc (pool);
523  _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */
524 
525  ++j;
526 
527  if (j == FREE_ARRAY_SIZE)
528  {
529  j = 0;
530  while (j < FREE_ARRAY_SIZE)
531  {
532  _dbus_mem_pool_dealloc (pool, to_free[j]);
533  ++j;
534  }
535 
536  j = 0;
537  }
538 
539  ++i;
540  }
541 
542  _dbus_mem_pool_free (pool);
543 
544 #ifdef DBUS_ENABLE_VERBOSE_MODE
545  end = clock ();
546 
547  _dbus_verbose (" created/destroyed %d elements in %g seconds\n",
548  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
549 
550  _dbus_verbose (" zeroed malloc\n");
551 
552  start = clock ();
553 #endif
554 
555  i = 0;
556  j = 0;
557  while (i < N_ITERATIONS)
558  {
559  to_free[j] = dbus_malloc0 (size);
560  _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */
561 
562  ++j;
563 
564  if (j == FREE_ARRAY_SIZE)
565  {
566  j = 0;
567  while (j < FREE_ARRAY_SIZE)
568  {
569  dbus_free (to_free[j]);
570  ++j;
571  }
572 
573  j = 0;
574  }
575 
576  ++i;
577  }
578 
579 #ifdef DBUS_ENABLE_VERBOSE_MODE
580  end = clock ();
581 
582  _dbus_verbose (" created/destroyed %d elements in %g seconds\n",
583  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
584 
585  _dbus_verbose (" zeroed mempools\n");
586 
587  start = clock ();
588 #endif
589 
590  pool = _dbus_mem_pool_new (size, TRUE);
591 
592  i = 0;
593  j = 0;
594  while (i < N_ITERATIONS)
595  {
596  to_free[j] = _dbus_mem_pool_alloc (pool);
597  _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */
598 
599  ++j;
600 
601  if (j == FREE_ARRAY_SIZE)
602  {
603  j = 0;
604  while (j < FREE_ARRAY_SIZE)
605  {
606  _dbus_mem_pool_dealloc (pool, to_free[j]);
607  ++j;
608  }
609 
610  j = 0;
611  }
612 
613  ++i;
614  }
615 
616  _dbus_mem_pool_free (pool);
617 
618 #ifdef DBUS_ENABLE_VERBOSE_MODE
619  end = clock ();
620 
621  _dbus_verbose (" created/destroyed %d elements in %g seconds\n",
622  N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
623 #endif
624 }
625 
632 _dbus_mem_pool_test (void)
633 {
634  int i;
635  int element_sizes[] = { 4, 8, 16, 50, 124 };
636 
637  i = 0;
638  while (i < _DBUS_N_ELEMENTS (element_sizes))
639  {
640  time_for_size (element_sizes[i]);
641  ++i;
642  }
643 
644  return TRUE;
645 }
646 
647 #endif /* DBUS_ENABLE_EMBEDDED_TESTS */
DBusMemBlock * next
next block in the list, which is already used up; only saved so we can free all the blocks when we fr...
Definition: dbus-mempool.c:84
#define NULL
A null pointer, defined appropriately for C or C++.
void * _dbus_mem_pool_alloc(DBusMemPool *pool)
Allocates an object from the memory pool.
Definition: dbus-mempool.c:214
void dbus_free(void *memory)
Frees a block of memory previously allocated by dbus_malloc() or dbus_malloc0().
Definition: dbus-memory.c:703
struct DBusMemBlock DBusMemBlock
Typedef for DBusMemBlock so the struct can recursively point to itself.
Definition: dbus-mempool.c:76
DBusFreedElement * free_elements
a free list of elements to recycle
Definition: dbus-mempool.c:104
#define _dbus_assert(condition)
Aborts with an error message if the condition is false.
unsigned char elements[ELEMENT_PADDING]
the block data, actually allocated to required size
Definition: dbus-mempool.c:92
dbus_bool_t _dbus_mem_pool_dealloc(DBusMemPool *pool, void *element)
Deallocates an object previously created with _dbus_mem_pool_alloc().
Definition: dbus-mempool.c:347
DBusMemBlock object represents a single malloc()-returned block that gets chunked up into objects in ...
Definition: dbus-mempool.c:82
#define _DBUS_INT_MAX
Maximum value of type "int".
void * dbus_malloc(size_t bytes)
Allocates the given number of bytes, as with standard malloc().
Definition: dbus-memory.c:463
#define dbus_new0(type, count)
Safe macro for using dbus_malloc0().
Definition: dbus-memory.h:58
int allocated_elements
Count of outstanding allocated elements.
Definition: dbus-mempool.c:106
dbus_uint32_t dbus_bool_t
A boolean, valid values are TRUE and FALSE.
Definition: dbus-types.h:35
int block_size
size of most recently allocated block
Definition: dbus-mempool.c:101
DBusMemBlock * blocks
blocks of memory from malloc()
Definition: dbus-mempool.c:105
void _dbus_mem_pool_free(DBusMemPool *pool)
Frees a memory pool (and all elements allocated from it).
Definition: dbus-mempool.c:187
Internals fields of DBusMemPool.
Definition: dbus-mempool.c:98
#define _DBUS_N_ELEMENTS(array)
Computes the number of elements in a fixed-size array using sizeof().
#define TRUE
Expands to "1".
#define _dbus_assert_not_reached(explanation)
Aborts with an error message if called.
DBusFreedElement * next
next element of the free list
Definition: dbus-mempool.c:63
long used_so_far
bytes of this block already allocated as elements.
Definition: dbus-mempool.c:90
struct representing an element on the free list.
Definition: dbus-mempool.c:61
unsigned int zero_elements
whether to zero-init allocated elements
Definition: dbus-mempool.c:102
#define FALSE
Expands to "0".
void * dbus_malloc0(size_t bytes)
Allocates the given number of bytes, as with standard malloc(), but all bytes are initialized to zero...
Definition: dbus-memory.c:533
int element_size
size of a single object in the pool
Definition: dbus-mempool.c:100
DBusMemPool * _dbus_mem_pool_new(int element_size, dbus_bool_t zero_elements)
Creates a new memory pool, or returns NULL on failure.
Definition: dbus-mempool.c:138
#define ELEMENT_PADDING
The dummy size of the variable-length "elements" field in DBusMemBlock.
Definition: dbus-mempool.c:70