D-Bus
1.10.12
|
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_ENABLE_EMBEDDED_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_ENABLE_EMBEDDED_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_ENABLE_EMBEDDED_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_ENABLE_EMBEDDED_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_ENABLE_EMBEDDED_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_ENABLE_EMBEDDED_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 #ifdef DBUS_ENABLE_VERBOSE_MODE 00463 clock_t start; 00464 clock_t end; 00465 #endif 00466 #define FREE_ARRAY_SIZE 512 00467 #define N_ITERATIONS FREE_ARRAY_SIZE * 512 00468 void *to_free[FREE_ARRAY_SIZE]; 00469 DBusMemPool *pool; 00470 00471 _dbus_verbose ("Timings for size %d\n", size); 00472 00473 _dbus_verbose (" malloc\n"); 00474 00475 #ifdef DBUS_ENABLE_VERBOSE_MODE 00476 start = clock (); 00477 #endif 00478 00479 i = 0; 00480 j = 0; 00481 while (i < N_ITERATIONS) 00482 { 00483 to_free[j] = dbus_malloc (size); 00484 _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */ 00485 00486 ++j; 00487 00488 if (j == FREE_ARRAY_SIZE) 00489 { 00490 j = 0; 00491 while (j < FREE_ARRAY_SIZE) 00492 { 00493 dbus_free (to_free[j]); 00494 ++j; 00495 } 00496 00497 j = 0; 00498 } 00499 00500 ++i; 00501 } 00502 00503 #ifdef DBUS_ENABLE_VERBOSE_MODE 00504 end = clock (); 00505 00506 _dbus_verbose (" created/destroyed %d elements in %g seconds\n", 00507 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC); 00508 00509 00510 00511 _dbus_verbose (" mempools\n"); 00512 00513 start = clock (); 00514 #endif 00515 00516 pool = _dbus_mem_pool_new (size, FALSE); 00517 00518 i = 0; 00519 j = 0; 00520 while (i < N_ITERATIONS) 00521 { 00522 to_free[j] = _dbus_mem_pool_alloc (pool); 00523 _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */ 00524 00525 ++j; 00526 00527 if (j == FREE_ARRAY_SIZE) 00528 { 00529 j = 0; 00530 while (j < FREE_ARRAY_SIZE) 00531 { 00532 _dbus_mem_pool_dealloc (pool, to_free[j]); 00533 ++j; 00534 } 00535 00536 j = 0; 00537 } 00538 00539 ++i; 00540 } 00541 00542 _dbus_mem_pool_free (pool); 00543 00544 #ifdef DBUS_ENABLE_VERBOSE_MODE 00545 end = clock (); 00546 00547 _dbus_verbose (" created/destroyed %d elements in %g seconds\n", 00548 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC); 00549 00550 _dbus_verbose (" zeroed malloc\n"); 00551 00552 start = clock (); 00553 #endif 00554 00555 i = 0; 00556 j = 0; 00557 while (i < N_ITERATIONS) 00558 { 00559 to_free[j] = dbus_malloc0 (size); 00560 _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */ 00561 00562 ++j; 00563 00564 if (j == FREE_ARRAY_SIZE) 00565 { 00566 j = 0; 00567 while (j < FREE_ARRAY_SIZE) 00568 { 00569 dbus_free (to_free[j]); 00570 ++j; 00571 } 00572 00573 j = 0; 00574 } 00575 00576 ++i; 00577 } 00578 00579 #ifdef DBUS_ENABLE_VERBOSE_MODE 00580 end = clock (); 00581 00582 _dbus_verbose (" created/destroyed %d elements in %g seconds\n", 00583 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC); 00584 00585 _dbus_verbose (" zeroed mempools\n"); 00586 00587 start = clock (); 00588 #endif 00589 00590 pool = _dbus_mem_pool_new (size, TRUE); 00591 00592 i = 0; 00593 j = 0; 00594 while (i < N_ITERATIONS) 00595 { 00596 to_free[j] = _dbus_mem_pool_alloc (pool); 00597 _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */ 00598 00599 ++j; 00600 00601 if (j == FREE_ARRAY_SIZE) 00602 { 00603 j = 0; 00604 while (j < FREE_ARRAY_SIZE) 00605 { 00606 _dbus_mem_pool_dealloc (pool, to_free[j]); 00607 ++j; 00608 } 00609 00610 j = 0; 00611 } 00612 00613 ++i; 00614 } 00615 00616 _dbus_mem_pool_free (pool); 00617 00618 #ifdef DBUS_ENABLE_VERBOSE_MODE 00619 end = clock (); 00620 00621 _dbus_verbose (" created/destroyed %d elements in %g seconds\n", 00622 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC); 00623 #endif 00624 } 00625 00631 dbus_bool_t 00632 _dbus_mem_pool_test (void) 00633 { 00634 int i; 00635 int element_sizes[] = { 4, 8, 16, 50, 124 }; 00636 00637 i = 0; 00638 while (i < _DBUS_N_ELEMENTS (element_sizes)) 00639 { 00640 time_for_size (element_sizes[i]); 00641 ++i; 00642 } 00643 00644 return TRUE; 00645 } 00646 00647 #endif /* DBUS_ENABLE_EMBEDDED_TESTS */