D-Bus
1.4.18
|
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 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 /* this is a long so that "elements" is aligned */ 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 /* Make the element size at least 8 bytes. */ 00147 if (element_size < 8) 00148 element_size = 8; 00149 00150 /* these assertions are equivalent but the first is more clear 00151 * to programmers that see it fail. 00152 */ 00153 _dbus_assert (element_size >= (int) sizeof (void*)); 00154 _dbus_assert (element_size >= (int) sizeof (DBusFreedElement)); 00155 00156 /* align the element size to a pointer boundary so we won't get bus 00157 * errors under other architectures. 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 /* pick a size for the first block; it increases 00166 * for each block we need to allocate. This is 00167 * actually half the initial block size 00168 * since _dbus_mem_pool_alloc() unconditionally 00169 * doubles it prior to creating a new block. */ 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 /* This is obviously really silly, but it's 00218 * debug-mode-only code that is compiled out 00219 * when tests are disabled (_dbus_disable_mem_pools() 00220 * is a constant expression FALSE so this block 00221 * should vanish) 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 /* Need a new block */ 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) /* avoid overflow */ 00279 { 00280 /* use a larger block size for our next block */ 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 /* We save/restore the counter, so that memory pools won't 00290 * cause a given function to have different number of 00291 * allocations on different invocations. i.e. when testing 00292 * we want consistent alloc patterns. So we skip our 00293 * malloc here for purposes of failed alloc simulation. 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 /* mmm, fast. ;-) debug-only code, so doesn't matter. */ 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); /* in a real app of course this is wrong */ 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); /* in a real app of course this is wrong */ 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); /* in a real app of course this is wrong */ 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); /* in a real app of course this is wrong */ 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 /* DBUS_BUILD_TESTS */