D-Bus
1.6.8
|
00001 /* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */ 00002 /* dbus-mempool.h Memory pools 00003 * 00004 * Copyright (C) 2002, 2003 Red Hat, Inc. 00005 * 00006 * Licensed under the Academic Free License version 2.1 00007 * 00008 * This program is free software; you can redistribute it and/or modify 00009 * it under the terms of the GNU General Public License as published by 00010 * the Free Software Foundation; either version 2 of the License, or 00011 * (at your option) any later version. 00012 * 00013 * This program is distributed in the hope that it will be useful, 00014 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00016 * GNU General Public License for more details. 00017 * 00018 * You should have received a copy of the GNU General Public License 00019 * along with this program; if not, write to the Free Software 00020 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 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 /* this is a long so that "elements" is aligned */ 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 /* Make the element size at least 8 bytes. */ 00148 if (element_size < 8) 00149 element_size = 8; 00150 00151 /* these assertions are equivalent but the first is more clear 00152 * to programmers that see it fail. 00153 */ 00154 _dbus_assert (element_size >= (int) sizeof (void*)); 00155 _dbus_assert (element_size >= (int) sizeof (DBusFreedElement)); 00156 00157 /* align the element size to a pointer boundary so we won't get bus 00158 * errors under other architectures. 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 /* pick a size for the first block; it increases 00167 * for each block we need to allocate. This is 00168 * actually half the initial block size 00169 * since _dbus_mem_pool_alloc() unconditionally 00170 * doubles it prior to creating a new block. */ 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 /* This is obviously really silly, but it's 00223 * debug-mode-only code that is compiled out 00224 * when tests are disabled (_dbus_disable_mem_pools() 00225 * is a constant expression FALSE so this block 00226 * should vanish) 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 /* Need a new block */ 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) /* avoid overflow */ 00288 { 00289 /* use a larger block size for our next block */ 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 /* We save/restore the counter, so that memory pools won't 00299 * cause a given function to have different number of 00300 * allocations on different invocations. i.e. when testing 00301 * we want consistent alloc patterns. So we skip our 00302 * malloc here for purposes of failed alloc simulation. 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 /* mmm, fast. ;-) debug-only code, so doesn't matter. */ 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 /* used for internal mempool administration */ 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 /* DBUS_ENABLE_STATS */ 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); /* in a real app of course this is wrong */ 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); /* in a real app of course this is wrong */ 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); /* in a real app of course this is wrong */ 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); /* in a real app of course this is wrong */ 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 /* DBUS_BUILD_TESTS */