Main Page | Modules | Data Structures | File List | Data Fields | Related Pages

dbus-mempool.c

00001 /* -*- mode: C; c-file-style: "gnu" -*- */ 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 00021 * 00022 */ 00023 00024 #include "dbus-mempool.h" 00025 #include "dbus-internals.h" 00026 00052 typedef struct DBusFreedElement DBusFreedElement; 00053 00059 struct DBusFreedElement 00060 { 00061 DBusFreedElement *next; 00062 }; 00063 00068 #define ELEMENT_PADDING 4 00069 00074 typedef struct DBusMemBlock DBusMemBlock; 00075 00080 struct DBusMemBlock 00081 { 00082 DBusMemBlock *next; 00087 /* this is a long so that "elements" is aligned */ 00088 long used_so_far; 00090 unsigned char elements[ELEMENT_PADDING]; 00091 }; 00092 00096 struct DBusMemPool 00097 { 00098 int element_size; 00099 int block_size; 00100 unsigned int zero_elements : 1; 00102 DBusFreedElement *free_elements; 00103 DBusMemBlock *blocks; 00104 int allocated_elements; 00105 }; 00106 00135 DBusMemPool* 00136 _dbus_mem_pool_new (int element_size, 00137 dbus_bool_t zero_elements) 00138 { 00139 DBusMemPool *pool; 00140 00141 pool = dbus_new0 (DBusMemPool, 1); 00142 if (pool == NULL) 00143 return NULL; 00144 00145 /* Make the element size at least 8 bytes. */ 00146 if (element_size < 8) 00147 element_size = 8; 00148 00149 /* these assertions are equivalent but the first is more clear 00150 * to programmers that see it fail. 00151 */ 00152 _dbus_assert (element_size >= (int) sizeof (void*)); 00153 _dbus_assert (element_size >= (int) sizeof (DBusFreedElement)); 00154 00155 /* align the element size to a pointer boundary so we won't get bus 00156 * errors under other architectures. 00157 */ 00158 pool->element_size = _DBUS_ALIGN_VALUE (element_size, sizeof (void *)); 00159 00160 pool->zero_elements = zero_elements != FALSE; 00161 00162 pool->allocated_elements = 0; 00163 00164 /* pick a size for the first block; it increases 00165 * for each block we need to allocate. This is 00166 * actually half the initial block size 00167 * since _dbus_mem_pool_alloc() unconditionally 00168 * doubles it prior to creating a new block. */ 00169 pool->block_size = pool->element_size * 8; 00170 00171 _dbus_assert ((pool->block_size % 00172 pool->element_size) == 0); 00173 00174 return pool; 00175 } 00176 00182 void 00183 _dbus_mem_pool_free (DBusMemPool *pool) 00184 { 00185 DBusMemBlock *block; 00186 00187 block = pool->blocks; 00188 while (block != NULL) 00189 { 00190 DBusMemBlock *next = block->next; 00191 00192 dbus_free (block); 00193 00194 block = next; 00195 } 00196 00197 dbus_free (pool); 00198 } 00199 00207 void* 00208 _dbus_mem_pool_alloc (DBusMemPool *pool) 00209 { 00210 #ifdef DBUS_BUILD_TESTS 00211 if (_dbus_disable_mem_pools ()) 00212 { 00213 DBusMemBlock *block; 00214 int alloc_size; 00215 00216 /* This is obviously really silly, but it's 00217 * debug-mode-only code that is compiled out 00218 * when tests are disabled (_dbus_disable_mem_pools() 00219 * is a constant expression FALSE so this block 00220 * should vanish) 00221 */ 00222 00223 alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING + 00224 pool->element_size; 00225 00226 if (pool->zero_elements) 00227 block = dbus_malloc0 (alloc_size); 00228 else 00229 block = dbus_malloc (alloc_size); 00230 00231 if (block != NULL) 00232 { 00233 block->next = pool->blocks; 00234 pool->blocks = block; 00235 pool->allocated_elements += 1; 00236 00237 return (void*) &block->elements[0]; 00238 } 00239 else 00240 return NULL; 00241 } 00242 else 00243 #endif 00244 { 00245 if (_dbus_decrement_fail_alloc_counter ()) 00246 { 00247 _dbus_verbose (" FAILING mempool alloc\n"); 00248 return NULL; 00249 } 00250 else if (pool->free_elements) 00251 { 00252 DBusFreedElement *element = pool->free_elements; 00253 00254 pool->free_elements = pool->free_elements->next; 00255 00256 if (pool->zero_elements) 00257 memset (element, '\0', pool->element_size); 00258 00259 pool->allocated_elements += 1; 00260 00261 return element; 00262 } 00263 else 00264 { 00265 void *element; 00266 00267 if (pool->blocks == NULL || 00268 pool->blocks->used_so_far == pool->block_size) 00269 { 00270 /* Need a new block */ 00271 DBusMemBlock *block; 00272 int alloc_size; 00273 #ifdef DBUS_BUILD_TESTS 00274 int saved_counter; 00275 #endif 00276 00277 if (pool->block_size <= _DBUS_INT_MAX / 4) /* avoid overflow */ 00278 { 00279 /* use a larger block size for our next block */ 00280 pool->block_size *= 2; 00281 _dbus_assert ((pool->block_size % 00282 pool->element_size) == 0); 00283 } 00284 00285 alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING + pool->block_size; 00286 00287 #ifdef DBUS_BUILD_TESTS 00288 /* We save/restore the counter, so that memory pools won't 00289 * cause a given function to have different number of 00290 * allocations on different invocations. i.e. when testing 00291 * we want consistent alloc patterns. So we skip our 00292 * malloc here for purposes of failed alloc simulation. 00293 */ 00294 saved_counter = _dbus_get_fail_alloc_counter (); 00295 _dbus_set_fail_alloc_counter (_DBUS_INT_MAX); 00296 #endif 00297 00298 if (pool->zero_elements) 00299 block = dbus_malloc0 (alloc_size); 00300 else 00301 block = dbus_malloc (alloc_size); 00302 00303 #ifdef DBUS_BUILD_TESTS 00304 _dbus_set_fail_alloc_counter (saved_counter); 00305 _dbus_assert (saved_counter == _dbus_get_fail_alloc_counter ()); 00306 #endif 00307 00308 if (block == NULL) 00309 return NULL; 00310 00311 block->used_so_far = 0; 00312 block->next = pool->blocks; 00313 pool->blocks = block; 00314 } 00315 00316 element = &pool->blocks->elements[pool->blocks->used_so_far]; 00317 00318 pool->blocks->used_so_far += pool->element_size; 00319 00320 pool->allocated_elements += 1; 00321 00322 return element; 00323 } 00324 } 00325 } 00326 00335 dbus_bool_t 00336 _dbus_mem_pool_dealloc (DBusMemPool *pool, 00337 void *element) 00338 { 00339 #ifdef DBUS_BUILD_TESTS 00340 if (_dbus_disable_mem_pools ()) 00341 { 00342 DBusMemBlock *block; 00343 DBusMemBlock *prev; 00344 00345 /* mmm, fast. ;-) debug-only code, so doesn't matter. */ 00346 00347 prev = NULL; 00348 block = pool->blocks; 00349 00350 while (block != NULL) 00351 { 00352 if (block->elements == (unsigned char*) element) 00353 { 00354 if (prev) 00355 prev->next = block->next; 00356 else 00357 pool->blocks = block->next; 00358 00359 dbus_free (block); 00360 00361 _dbus_assert (pool->allocated_elements > 0); 00362 pool->allocated_elements -= 1; 00363 00364 if (pool->allocated_elements == 0) 00365 _dbus_assert (pool->blocks == NULL); 00366 00367 return pool->blocks == NULL; 00368 } 00369 prev = block; 00370 block = block->next; 00371 } 00372 00373 _dbus_assert_not_reached ("freed nonexistent block"); 00374 return FALSE; 00375 } 00376 else 00377 #endif 00378 { 00379 DBusFreedElement *freed; 00380 00381 freed = element; 00382 freed->next = pool->free_elements; 00383 pool->free_elements = freed; 00384 00385 _dbus_assert (pool->allocated_elements > 0); 00386 pool->allocated_elements -= 1; 00387 00388 return pool->allocated_elements == 0; 00389 } 00390 } 00391 00394 #ifdef DBUS_BUILD_TESTS 00395 #include "dbus-test.h" 00396 #include <stdio.h> 00397 #include <time.h> 00398 00399 static void 00400 time_for_size (int size) 00401 { 00402 int i; 00403 int j; 00404 clock_t start; 00405 clock_t end; 00406 #define FREE_ARRAY_SIZE 512 00407 #define N_ITERATIONS FREE_ARRAY_SIZE * 512 00408 void *to_free[FREE_ARRAY_SIZE]; 00409 DBusMemPool *pool; 00410 00411 _dbus_verbose ("Timings for size %d\n", size); 00412 00413 _dbus_verbose (" malloc\n"); 00414 00415 start = clock (); 00416 00417 i = 0; 00418 j = 0; 00419 while (i < N_ITERATIONS) 00420 { 00421 to_free[j] = dbus_malloc (size); 00422 _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */ 00423 00424 ++j; 00425 00426 if (j == FREE_ARRAY_SIZE) 00427 { 00428 j = 0; 00429 while (j < FREE_ARRAY_SIZE) 00430 { 00431 dbus_free (to_free[j]); 00432 ++j; 00433 } 00434 00435 j = 0; 00436 } 00437 00438 ++i; 00439 } 00440 00441 end = clock (); 00442 00443 _dbus_verbose (" created/destroyed %d elements in %g seconds\n", 00444 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC); 00445 00446 00447 00448 _dbus_verbose (" mempools\n"); 00449 00450 start = clock (); 00451 00452 pool = _dbus_mem_pool_new (size, FALSE); 00453 00454 i = 0; 00455 j = 0; 00456 while (i < N_ITERATIONS) 00457 { 00458 to_free[j] = _dbus_mem_pool_alloc (pool); 00459 _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */ 00460 00461 ++j; 00462 00463 if (j == FREE_ARRAY_SIZE) 00464 { 00465 j = 0; 00466 while (j < FREE_ARRAY_SIZE) 00467 { 00468 _dbus_mem_pool_dealloc (pool, to_free[j]); 00469 ++j; 00470 } 00471 00472 j = 0; 00473 } 00474 00475 ++i; 00476 } 00477 00478 _dbus_mem_pool_free (pool); 00479 00480 end = clock (); 00481 00482 _dbus_verbose (" created/destroyed %d elements in %g seconds\n", 00483 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC); 00484 00485 _dbus_verbose (" zeroed malloc\n"); 00486 00487 start = clock (); 00488 00489 i = 0; 00490 j = 0; 00491 while (i < N_ITERATIONS) 00492 { 00493 to_free[j] = dbus_malloc0 (size); 00494 _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */ 00495 00496 ++j; 00497 00498 if (j == FREE_ARRAY_SIZE) 00499 { 00500 j = 0; 00501 while (j < FREE_ARRAY_SIZE) 00502 { 00503 dbus_free (to_free[j]); 00504 ++j; 00505 } 00506 00507 j = 0; 00508 } 00509 00510 ++i; 00511 } 00512 00513 end = clock (); 00514 00515 _dbus_verbose (" created/destroyed %d elements in %g seconds\n", 00516 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC); 00517 00518 _dbus_verbose (" zeroed mempools\n"); 00519 00520 start = clock (); 00521 00522 pool = _dbus_mem_pool_new (size, TRUE); 00523 00524 i = 0; 00525 j = 0; 00526 while (i < N_ITERATIONS) 00527 { 00528 to_free[j] = _dbus_mem_pool_alloc (pool); 00529 _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */ 00530 00531 ++j; 00532 00533 if (j == FREE_ARRAY_SIZE) 00534 { 00535 j = 0; 00536 while (j < FREE_ARRAY_SIZE) 00537 { 00538 _dbus_mem_pool_dealloc (pool, to_free[j]); 00539 ++j; 00540 } 00541 00542 j = 0; 00543 } 00544 00545 ++i; 00546 } 00547 00548 _dbus_mem_pool_free (pool); 00549 00550 end = clock (); 00551 00552 _dbus_verbose (" created/destroyed %d elements in %g seconds\n", 00553 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC); 00554 } 00555 00561 dbus_bool_t 00562 _dbus_mem_pool_test (void) 00563 { 00564 int i; 00565 int element_sizes[] = { 4, 8, 16, 50, 124 }; 00566 00567 i = 0; 00568 while (i < _DBUS_N_ELEMENTS (element_sizes)) 00569 { 00570 time_for_size (element_sizes[i]); 00571 ++i; 00572 } 00573 00574 return TRUE; 00575 } 00576 00577 #endif /* DBUS_BUILD_TESTS */

Generated on Mon Aug 16 17:40:09 2004 for D-BUS by doxygen 1.3.8