D-Bus  1.4.10
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 
54 
61 {
63 };
64 
69 #define ELEMENT_PADDING 4
70 
75 typedef struct DBusMemBlock DBusMemBlock;
76 
82 {
88  /* this is a long so that "elements" is aligned */
89  long used_so_far;
91  unsigned char elements[ELEMENT_PADDING];
92 };
93 
98 {
101  unsigned int zero_elements : 1;
106 };
107 
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 
183 void
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 
208 void*
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 
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 
395 #ifdef DBUS_BUILD_TESTS
396 #include "dbus-test.h"
397 #include <stdio.h>
398 #include <time.h>
399 
400 static void
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 
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 */