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
00053 typedef struct DBusFreedElement DBusFreedElement;
00054
00060 struct DBusFreedElement
00061 {
00062 DBusFreedElement *next;
00063 };
00064
00069 #define ELEMENT_PADDING 4
00070
00075 typedef struct DBusMemBlock DBusMemBlock;
00076
00081 struct DBusMemBlock
00082 {
00083 DBusMemBlock *next;
00088
00089 long used_so_far;
00091 unsigned char elements[ELEMENT_PADDING];
00092 };
00093
00097 struct DBusMemPool
00098 {
00099 int element_size;
00100 int block_size;
00101 unsigned int zero_elements : 1;
00103 DBusFreedElement *free_elements;
00104 DBusMemBlock *blocks;
00105 int allocated_elements;
00106 };
00107
00136 DBusMemPool*
00137 _dbus_mem_pool_new (int element_size,
00138 dbus_bool_t zero_elements)
00139 {
00140 DBusMemPool *pool;
00141
00142 pool = dbus_new0 (DBusMemPool, 1);
00143 if (pool == NULL)
00144 return NULL;
00145
00146
00147 if (element_size < 8)
00148 element_size = 8;
00149
00150
00151
00152
00153 _dbus_assert (element_size >= (int) sizeof (void*));
00154 _dbus_assert (element_size >= (int) sizeof (DBusFreedElement));
00155
00156
00157
00158
00159 pool->element_size = _DBUS_ALIGN_VALUE (element_size, sizeof (void *));
00160
00161 pool->zero_elements = zero_elements != FALSE;
00162
00163 pool->allocated_elements = 0;
00164
00165
00166
00167
00168
00169
00170 pool->block_size = pool->element_size * 8;
00171
00172 _dbus_assert ((pool->block_size %
00173 pool->element_size) == 0);
00174
00175 return pool;
00176 }
00177
00183 void
00184 _dbus_mem_pool_free (DBusMemPool *pool)
00185 {
00186 DBusMemBlock *block;
00187
00188 block = pool->blocks;
00189 while (block != NULL)
00190 {
00191 DBusMemBlock *next = block->next;
00192
00193 dbus_free (block);
00194
00195 block = next;
00196 }
00197
00198 dbus_free (pool);
00199 }
00200
00208 void*
00209 _dbus_mem_pool_alloc (DBusMemPool *pool)
00210 {
00211 #ifdef DBUS_BUILD_TESTS
00212 if (_dbus_disable_mem_pools ())
00213 {
00214 DBusMemBlock *block;
00215 int alloc_size;
00216
00217
00218
00219
00220
00221
00222
00223
00224 alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING +
00225 pool->element_size;
00226
00227 if (pool->zero_elements)
00228 block = dbus_malloc0 (alloc_size);
00229 else
00230 block = dbus_malloc (alloc_size);
00231
00232 if (block != NULL)
00233 {
00234 block->next = pool->blocks;
00235 pool->blocks = block;
00236 pool->allocated_elements += 1;
00237
00238 return (void*) &block->elements[0];
00239 }
00240 else
00241 return NULL;
00242 }
00243 else
00244 #endif
00245 {
00246 if (_dbus_decrement_fail_alloc_counter ())
00247 {
00248 _dbus_verbose (" FAILING mempool alloc\n");
00249 return NULL;
00250 }
00251 else if (pool->free_elements)
00252 {
00253 DBusFreedElement *element = pool->free_elements;
00254
00255 pool->free_elements = pool->free_elements->next;
00256
00257 if (pool->zero_elements)
00258 memset (element, '\0', pool->element_size);
00259
00260 pool->allocated_elements += 1;
00261
00262 return element;
00263 }
00264 else
00265 {
00266 void *element;
00267
00268 if (pool->blocks == NULL ||
00269 pool->blocks->used_so_far == pool->block_size)
00270 {
00271
00272 DBusMemBlock *block;
00273 int alloc_size;
00274 #ifdef DBUS_BUILD_TESTS
00275 int saved_counter;
00276 #endif
00277
00278 if (pool->block_size <= _DBUS_INT_MAX / 4)
00279 {
00280
00281 pool->block_size *= 2;
00282 _dbus_assert ((pool->block_size %
00283 pool->element_size) == 0);
00284 }
00285
00286 alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING + pool->block_size;
00287
00288 #ifdef DBUS_BUILD_TESTS
00289
00290
00291
00292
00293
00294
00295 saved_counter = _dbus_get_fail_alloc_counter ();
00296 _dbus_set_fail_alloc_counter (_DBUS_INT_MAX);
00297 #endif
00298
00299 if (pool->zero_elements)
00300 block = dbus_malloc0 (alloc_size);
00301 else
00302 block = dbus_malloc (alloc_size);
00303
00304 #ifdef DBUS_BUILD_TESTS
00305 _dbus_set_fail_alloc_counter (saved_counter);
00306 _dbus_assert (saved_counter == _dbus_get_fail_alloc_counter ());
00307 #endif
00308
00309 if (block == NULL)
00310 return NULL;
00311
00312 block->used_so_far = 0;
00313 block->next = pool->blocks;
00314 pool->blocks = block;
00315 }
00316
00317 element = &pool->blocks->elements[pool->blocks->used_so_far];
00318
00319 pool->blocks->used_so_far += pool->element_size;
00320
00321 pool->allocated_elements += 1;
00322
00323 return element;
00324 }
00325 }
00326 }
00327
00336 dbus_bool_t
00337 _dbus_mem_pool_dealloc (DBusMemPool *pool,
00338 void *element)
00339 {
00340 #ifdef DBUS_BUILD_TESTS
00341 if (_dbus_disable_mem_pools ())
00342 {
00343 DBusMemBlock *block;
00344 DBusMemBlock *prev;
00345
00346
00347
00348 prev = NULL;
00349 block = pool->blocks;
00350
00351 while (block != NULL)
00352 {
00353 if (block->elements == (unsigned char*) element)
00354 {
00355 if (prev)
00356 prev->next = block->next;
00357 else
00358 pool->blocks = block->next;
00359
00360 dbus_free (block);
00361
00362 _dbus_assert (pool->allocated_elements > 0);
00363 pool->allocated_elements -= 1;
00364
00365 if (pool->allocated_elements == 0)
00366 _dbus_assert (pool->blocks == NULL);
00367
00368 return pool->blocks == NULL;
00369 }
00370 prev = block;
00371 block = block->next;
00372 }
00373
00374 _dbus_assert_not_reached ("freed nonexistent block");
00375 return FALSE;
00376 }
00377 else
00378 #endif
00379 {
00380 DBusFreedElement *freed;
00381
00382 freed = element;
00383 freed->next = pool->free_elements;
00384 pool->free_elements = freed;
00385
00386 _dbus_assert (pool->allocated_elements > 0);
00387 pool->allocated_elements -= 1;
00388
00389 return pool->allocated_elements == 0;
00390 }
00391 }
00392
00395 #ifdef DBUS_BUILD_TESTS
00396 #include "dbus-test.h"
00397 #include <stdio.h>
00398 #include <time.h>
00399
00400 static void
00401 time_for_size (int size)
00402 {
00403 int i;
00404 int j;
00405 clock_t start;
00406 clock_t end;
00407 #define FREE_ARRAY_SIZE 512
00408 #define N_ITERATIONS FREE_ARRAY_SIZE * 512
00409 void *to_free[FREE_ARRAY_SIZE];
00410 DBusMemPool *pool;
00411
00412 _dbus_verbose ("Timings for size %d\n", size);
00413
00414 _dbus_verbose (" malloc\n");
00415
00416 start = clock ();
00417
00418 i = 0;
00419 j = 0;
00420 while (i < N_ITERATIONS)
00421 {
00422 to_free[j] = dbus_malloc (size);
00423 _dbus_assert (to_free[j] != NULL);
00424
00425 ++j;
00426
00427 if (j == FREE_ARRAY_SIZE)
00428 {
00429 j = 0;
00430 while (j < FREE_ARRAY_SIZE)
00431 {
00432 dbus_free (to_free[j]);
00433 ++j;
00434 }
00435
00436 j = 0;
00437 }
00438
00439 ++i;
00440 }
00441
00442 end = clock ();
00443
00444 _dbus_verbose (" created/destroyed %d elements in %g seconds\n",
00445 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
00446
00447
00448
00449 _dbus_verbose (" mempools\n");
00450
00451 start = clock ();
00452
00453 pool = _dbus_mem_pool_new (size, FALSE);
00454
00455 i = 0;
00456 j = 0;
00457 while (i < N_ITERATIONS)
00458 {
00459 to_free[j] = _dbus_mem_pool_alloc (pool);
00460 _dbus_assert (to_free[j] != NULL);
00461
00462 ++j;
00463
00464 if (j == FREE_ARRAY_SIZE)
00465 {
00466 j = 0;
00467 while (j < FREE_ARRAY_SIZE)
00468 {
00469 _dbus_mem_pool_dealloc (pool, to_free[j]);
00470 ++j;
00471 }
00472
00473 j = 0;
00474 }
00475
00476 ++i;
00477 }
00478
00479 _dbus_mem_pool_free (pool);
00480
00481 end = clock ();
00482
00483 _dbus_verbose (" created/destroyed %d elements in %g seconds\n",
00484 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
00485
00486 _dbus_verbose (" zeroed malloc\n");
00487
00488 start = clock ();
00489
00490 i = 0;
00491 j = 0;
00492 while (i < N_ITERATIONS)
00493 {
00494 to_free[j] = dbus_malloc0 (size);
00495 _dbus_assert (to_free[j] != NULL);
00496
00497 ++j;
00498
00499 if (j == FREE_ARRAY_SIZE)
00500 {
00501 j = 0;
00502 while (j < FREE_ARRAY_SIZE)
00503 {
00504 dbus_free (to_free[j]);
00505 ++j;
00506 }
00507
00508 j = 0;
00509 }
00510
00511 ++i;
00512 }
00513
00514 end = clock ();
00515
00516 _dbus_verbose (" created/destroyed %d elements in %g seconds\n",
00517 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
00518
00519 _dbus_verbose (" zeroed mempools\n");
00520
00521 start = clock ();
00522
00523 pool = _dbus_mem_pool_new (size, TRUE);
00524
00525 i = 0;
00526 j = 0;
00527 while (i < N_ITERATIONS)
00528 {
00529 to_free[j] = _dbus_mem_pool_alloc (pool);
00530 _dbus_assert (to_free[j] != NULL);
00531
00532 ++j;
00533
00534 if (j == FREE_ARRAY_SIZE)
00535 {
00536 j = 0;
00537 while (j < FREE_ARRAY_SIZE)
00538 {
00539 _dbus_mem_pool_dealloc (pool, to_free[j]);
00540 ++j;
00541 }
00542
00543 j = 0;
00544 }
00545
00546 ++i;
00547 }
00548
00549 _dbus_mem_pool_free (pool);
00550
00551 end = clock ();
00552
00553 _dbus_verbose (" created/destroyed %d elements in %g seconds\n",
00554 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC);
00555 }
00556
00562 dbus_bool_t
00563 _dbus_mem_pool_test (void)
00564 {
00565 int i;
00566 int element_sizes[] = { 4, 8, 16, 50, 124 };
00567
00568 i = 0;
00569 while (i < _DBUS_N_ELEMENTS (element_sizes))
00570 {
00571 time_for_size (element_sizes[i]);
00572 ++i;
00573 }
00574
00575 return TRUE;
00576 }
00577
00578 #endif