00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 #include <config.h>
00025 #include "dbus-mempool.h"
00026 #include "dbus-internals.h"
00027 #include "dbus-valgrind-internal.h"
00028
00054 typedef struct DBusFreedElement DBusFreedElement;
00055
00061 struct DBusFreedElement
00062 {
00063 DBusFreedElement *next;
00064 };
00065
00070 #define ELEMENT_PADDING 4
00071
00076 typedef struct DBusMemBlock DBusMemBlock;
00077
00082 struct DBusMemBlock
00083 {
00084 DBusMemBlock *next;
00089
00090 long used_so_far;
00092 unsigned char elements[ELEMENT_PADDING];
00093 };
00094
00098 struct DBusMemPool
00099 {
00100 int element_size;
00101 int block_size;
00102 unsigned int zero_elements : 1;
00104 DBusFreedElement *free_elements;
00105 DBusMemBlock *blocks;
00106 int allocated_elements;
00107 };
00108
00137 DBusMemPool*
00138 _dbus_mem_pool_new (int element_size,
00139 dbus_bool_t zero_elements)
00140 {
00141 DBusMemPool *pool;
00142
00143 pool = dbus_new0 (DBusMemPool, 1);
00144 if (pool == NULL)
00145 return NULL;
00146
00147
00148 if (element_size < 8)
00149 element_size = 8;
00150
00151
00152
00153
00154 _dbus_assert (element_size >= (int) sizeof (void*));
00155 _dbus_assert (element_size >= (int) sizeof (DBusFreedElement));
00156
00157
00158
00159
00160 pool->element_size = _DBUS_ALIGN_VALUE (element_size, sizeof (void *));
00161
00162 pool->zero_elements = zero_elements != FALSE;
00163
00164 pool->allocated_elements = 0;
00165
00166
00167
00168
00169
00170
00171 pool->block_size = pool->element_size * 8;
00172
00173 _dbus_assert ((pool->block_size %
00174 pool->element_size) == 0);
00175
00176 VALGRIND_CREATE_MEMPOOL (pool, 0, zero_elements)
00177
00178 return pool;
00179 }
00180
00186 void
00187 _dbus_mem_pool_free (DBusMemPool *pool)
00188 {
00189 DBusMemBlock *block;
00190
00191 VALGRIND_DESTROY_MEMPOOL (pool)
00192
00193 block = pool->blocks;
00194 while (block != NULL)
00195 {
00196 DBusMemBlock *next = block->next;
00197
00198 dbus_free (block);
00199
00200 block = next;
00201 }
00202
00203 dbus_free (pool);
00204 }
00205
00213 void*
00214 _dbus_mem_pool_alloc (DBusMemPool *pool)
00215 {
00216 #ifdef DBUS_BUILD_TESTS
00217 if (_dbus_disable_mem_pools ())
00218 {
00219 DBusMemBlock *block;
00220 int alloc_size;
00221
00222
00223
00224
00225
00226
00227
00228
00229 alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING +
00230 pool->element_size;
00231
00232 if (pool->zero_elements)
00233 block = dbus_malloc0 (alloc_size);
00234 else
00235 block = dbus_malloc (alloc_size);
00236
00237 if (block != NULL)
00238 {
00239 block->next = pool->blocks;
00240 pool->blocks = block;
00241 pool->allocated_elements += 1;
00242
00243 VALGRIND_MEMPOOL_ALLOC (pool, (void *) &block->elements[0],
00244 pool->element_size)
00245 return (void*) &block->elements[0];
00246 }
00247 else
00248 return NULL;
00249 }
00250 else
00251 #endif
00252 {
00253 if (_dbus_decrement_fail_alloc_counter ())
00254 {
00255 _dbus_verbose (" FAILING mempool alloc\n");
00256 return NULL;
00257 }
00258 else if (pool->free_elements)
00259 {
00260 DBusFreedElement *element = pool->free_elements;
00261
00262 pool->free_elements = pool->free_elements->next;
00263
00264 VALGRIND_MEMPOOL_ALLOC (pool, element, pool->element_size)
00265
00266 if (pool->zero_elements)
00267 memset (element, '\0', pool->element_size);
00268
00269 pool->allocated_elements += 1;
00270
00271 return element;
00272 }
00273 else
00274 {
00275 void *element;
00276
00277 if (pool->blocks == NULL ||
00278 pool->blocks->used_so_far == pool->block_size)
00279 {
00280
00281 DBusMemBlock *block;
00282 int alloc_size;
00283 #ifdef DBUS_BUILD_TESTS
00284 int saved_counter;
00285 #endif
00286
00287 if (pool->block_size <= _DBUS_INT_MAX / 4)
00288 {
00289
00290 pool->block_size *= 2;
00291 _dbus_assert ((pool->block_size %
00292 pool->element_size) == 0);
00293 }
00294
00295 alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING + pool->block_size;
00296
00297 #ifdef DBUS_BUILD_TESTS
00298
00299
00300
00301
00302
00303
00304 saved_counter = _dbus_get_fail_alloc_counter ();
00305 _dbus_set_fail_alloc_counter (_DBUS_INT_MAX);
00306 #endif
00307
00308 if (pool->zero_elements)
00309 block = dbus_malloc0 (alloc_size);
00310 else
00311 block = dbus_malloc (alloc_size);
00312
00313 #ifdef DBUS_BUILD_TESTS
00314 _dbus_set_fail_alloc_counter (saved_counter);
00315 _dbus_assert (saved_counter == _dbus_get_fail_alloc_counter ());
00316 #endif
00317
00318 if (block == NULL)
00319 return NULL;
00320
00321 block->used_so_far = 0;
00322 block->next = pool->blocks;
00323 pool->blocks = block;
00324 }
00325
00326 element = &pool->blocks->elements[pool->blocks->used_so_far];
00327
00328 pool->blocks->used_so_far += pool->element_size;
00329
00330 pool->allocated_elements += 1;
00331
00332 VALGRIND_MEMPOOL_ALLOC (pool, element, pool->element_size)
00333 return element;
00334 }
00335 }
00336 }
00337
00346 dbus_bool_t
00347 _dbus_mem_pool_dealloc (DBusMemPool *pool,
00348 void *element)
00349 {
00350 VALGRIND_MEMPOOL_FREE (pool, element)
00351
00352 #ifdef DBUS_BUILD_TESTS
00353 if (_dbus_disable_mem_pools ())
00354 {
00355 DBusMemBlock *block;
00356 DBusMemBlock *prev;
00357
00358
00359
00360 prev = NULL;
00361 block = pool->blocks;
00362
00363 while (block != NULL)
00364 {
00365 if (block->elements == (unsigned char*) element)
00366 {
00367 if (prev)
00368 prev->next = block->next;
00369 else
00370 pool->blocks = block->next;
00371
00372 dbus_free (block);
00373
00374 _dbus_assert (pool->allocated_elements > 0);
00375 pool->allocated_elements -= 1;
00376
00377 if (pool->allocated_elements == 0)
00378 _dbus_assert (pool->blocks == NULL);
00379
00380 return pool->blocks == NULL;
00381 }
00382 prev = block;
00383 block = block->next;
00384 }
00385
00386 _dbus_assert_not_reached ("freed nonexistent block");
00387 return FALSE;
00388 }
00389 else
00390 #endif
00391 {
00392 DBusFreedElement *freed;
00393
00394 freed = element;
00395
00396 VALGRIND_MAKE_MEM_UNDEFINED (freed, sizeof (freed));
00397
00398 freed->next = pool->free_elements;
00399 pool->free_elements = freed;
00400
00401 _dbus_assert (pool->allocated_elements > 0);
00402 pool->allocated_elements -= 1;
00403
00404 return pool->allocated_elements == 0;
00405 }
00406 }
00407
00408 #ifdef DBUS_ENABLE_STATS
00409 void
00410 _dbus_mem_pool_get_stats (DBusMemPool *pool,
00411 dbus_uint32_t *in_use_p,
00412 dbus_uint32_t *in_free_list_p,
00413 dbus_uint32_t *allocated_p)
00414 {
00415 DBusMemBlock *block;
00416 DBusFreedElement *freed;
00417 dbus_uint32_t in_use = 0;
00418 dbus_uint32_t in_free_list = 0;
00419 dbus_uint32_t allocated = 0;
00420
00421 if (pool != NULL)
00422 {
00423 in_use = pool->element_size * pool->allocated_elements;
00424
00425 for (freed = pool->free_elements; freed != NULL; freed = freed->next)
00426 {
00427 in_free_list += pool->element_size;
00428 }
00429
00430 for (block = pool->blocks; block != NULL; block = block->next)
00431 {
00432 if (block == pool->blocks)
00433 allocated += pool->block_size;
00434 else
00435 allocated += block->used_so_far;
00436 }
00437 }
00438
00439 if (in_use_p != NULL)
00440 *in_use_p = in_use;
00441
00442 if (in_free_list_p != NULL)
00443 *in_free_list_p = in_free_list;
00444
00445 if (allocated_p != NULL)
00446 *allocated_p = allocated;
00447 }
00448 #endif
00449
00452 #ifdef DBUS_BUILD_TESTS
00453 #include "dbus-test.h"
00454 #include <stdio.h>
00455 #include <time.h>
00456
00457 static void
00458 time_for_size (int size)
00459 {
00460 int i;
00461 int j;
00462 clock_t start;
00463 clock_t end;
00464 #define FREE_ARRAY_SIZE 512
00465 #define N_ITERATIONS FREE_ARRAY_SIZE * 512
00466 void *to_free[FREE_ARRAY_SIZE];
00467 DBusMemPool *pool;
00468
00469 _dbus_verbose ("Timings for size %d\n", size);
00470
00471 _dbus_verbose (" malloc\n");
00472
00473 start = clock ();
00474
00475 i = 0;
00476 j = 0;
00477 while (i < N_ITERATIONS)
00478 {
00479 to_free[j] = dbus_malloc (size);
00480 _dbus_assert (to_free[j] != NULL);
00481
00482 ++j;
00483
00484 if (j == FREE_ARRAY_SIZE)
00485 {
00486 j = 0;
00487 while (j < FREE_ARRAY_SIZE)
00488 {
00489 dbus_free (to_free[j]);
00490 ++j;
00491 }
00492
00493 j = 0;
00494 }
00495
00496 ++i;
00497 }
00498
00499 end = clock ();
00500
00501 _dbus_verbose (" created/destroyed %d elements in %g seconds\n",
00502 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
00503
00504
00505
00506 _dbus_verbose (" mempools\n");
00507
00508 start = clock ();
00509
00510 pool = _dbus_mem_pool_new (size, FALSE);
00511
00512 i = 0;
00513 j = 0;
00514 while (i < N_ITERATIONS)
00515 {
00516 to_free[j] = _dbus_mem_pool_alloc (pool);
00517 _dbus_assert (to_free[j] != NULL);
00518
00519 ++j;
00520
00521 if (j == FREE_ARRAY_SIZE)
00522 {
00523 j = 0;
00524 while (j < FREE_ARRAY_SIZE)
00525 {
00526 _dbus_mem_pool_dealloc (pool, to_free[j]);
00527 ++j;
00528 }
00529
00530 j = 0;
00531 }
00532
00533 ++i;
00534 }
00535
00536 _dbus_mem_pool_free (pool);
00537
00538 end = clock ();
00539
00540 _dbus_verbose (" created/destroyed %d elements in %g seconds\n",
00541 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
00542
00543 _dbus_verbose (" zeroed malloc\n");
00544
00545 start = clock ();
00546
00547 i = 0;
00548 j = 0;
00549 while (i < N_ITERATIONS)
00550 {
00551 to_free[j] = dbus_malloc0 (size);
00552 _dbus_assert (to_free[j] != NULL);
00553
00554 ++j;
00555
00556 if (j == FREE_ARRAY_SIZE)
00557 {
00558 j = 0;
00559 while (j < FREE_ARRAY_SIZE)
00560 {
00561 dbus_free (to_free[j]);
00562 ++j;
00563 }
00564
00565 j = 0;
00566 }
00567
00568 ++i;
00569 }
00570
00571 end = clock ();
00572
00573 _dbus_verbose (" created/destroyed %d elements in %g seconds\n",
00574 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
00575
00576 _dbus_verbose (" zeroed mempools\n");
00577
00578 start = clock ();
00579
00580 pool = _dbus_mem_pool_new (size, TRUE);
00581
00582 i = 0;
00583 j = 0;
00584 while (i < N_ITERATIONS)
00585 {
00586 to_free[j] = _dbus_mem_pool_alloc (pool);
00587 _dbus_assert (to_free[j] != NULL);
00588
00589 ++j;
00590
00591 if (j == FREE_ARRAY_SIZE)
00592 {
00593 j = 0;
00594 while (j < FREE_ARRAY_SIZE)
00595 {
00596 _dbus_mem_pool_dealloc (pool, to_free[j]);
00597 ++j;
00598 }
00599
00600 j = 0;
00601 }
00602
00603 ++i;
00604 }
00605
00606 _dbus_mem_pool_free (pool);
00607
00608 end = clock ();
00609
00610 _dbus_verbose (" created/destroyed %d elements in %g seconds\n",
00611 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
00612 }
00613
00619 dbus_bool_t
00620 _dbus_mem_pool_test (void)
00621 {
00622 int i;
00623 int element_sizes[] = { 4, 8, 16, 50, 124 };
00624
00625 i = 0;
00626 while (i < _DBUS_N_ELEMENTS (element_sizes))
00627 {
00628 time_for_size (element_sizes[i]);
00629 ++i;
00630 }
00631
00632 return TRUE;
00633 }
00634
00635 #endif