1 /* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */ 2 /* dbus-mempool.h Memory pools 3 * 4 * Copyright (C) 2002, 2003 Red Hat, Inc. 5 * 6 * Licensed under the Academic Free License version 2.1 7 * 8 * This program is free software; you can redistribute it and/or modify 9 * it under the terms of the GNU General Public License as published by 10 * the Free Software Foundation; either version 2 of the License, or 11 * (at your option) any later version. 12 * 13 * This program is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 * GNU General Public License for more details. 17 * 18 * You should have received a copy of the GNU General Public License 19 * along with this program; if not, write to the Free Software 20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 21 * 22 */ 23 24 #include <config.h> 25 #include "dbus-mempool.h" 26 #include "dbus-internals.h" 27 28 /** 29 * @defgroup DBusMemPool memory pools 30 * @ingroup DBusInternals 31 * @brief DBusMemPool object 32 * 33 * Types and functions related to DBusMemPool. A memory pool is used 34 * to decrease memory fragmentation/overhead and increase speed for 35 * blocks of small uniformly-sized objects. The main point is to avoid 36 * the overhead of a malloc block for each small object, speed is 37 * secondary. 38 */ 39 40 /** 41 * @defgroup DBusMemPoolInternals Memory pool implementation details 42 * @ingroup DBusInternals 43 * @brief DBusMemPool implementation details 44 * 45 * The guts of DBusMemPool. 46 * 47 * @{ 48 */ 49 50 /** 51 * typedef so DBusFreedElement struct can refer to itself. 52 */ 53 typedef struct DBusFreedElement DBusFreedElement; 54 55 /** 56 * struct representing an element on the free list. 57 * We just cast freed elements to this so we can 58 * make a list out of them. 59 */ 60 struct DBusFreedElement 61 { 62 DBusFreedElement *next; /**< next element of the free list */ 63 }; 64 65 /** 66 * The dummy size of the variable-length "elements" 67 * field in DBusMemBlock 68 */ 69 #define ELEMENT_PADDING 4 70 71 /** 72 * Typedef for DBusMemBlock so the struct can recursively 73 * point to itself. 74 */ 75 typedef struct DBusMemBlock DBusMemBlock; 76 77 /** 78 * DBusMemBlock object represents a single malloc()-returned 79 * block that gets chunked up into objects in the memory pool. 80 */ 81 struct DBusMemBlock 82 { 83 DBusMemBlock *next; /**< next block in the list, which is already used up; 84 * only saved so we can free all the blocks 85 * when we free the mem pool. 86 */ 87 88 /* this is a long so that "elements" is aligned */ 89 long used_so_far; /**< bytes of this block already allocated as elements. */ 90 91 unsigned char elements[ELEMENT_PADDING]; /**< the block data, actually allocated to required size */ 92 }; 93 94 /** 95 * Internals fields of DBusMemPool 96 */ 97 struct DBusMemPool 98 { 99 int element_size; /**< size of a single object in the pool */ 100 int block_size; /**< size of most recently allocated block */ 101 unsigned int zero_elements : 1; /**< whether to zero-init allocated elements */ 102 103 DBusFreedElement *free_elements; /**< a free list of elements to recycle */ 104 DBusMemBlock *blocks; /**< blocks of memory from malloc() */ 105 int allocated_elements; /**< Count of outstanding allocated elements */ 106 }; 107 108 /** @} */ 109 110 /** 111 * @addtogroup DBusMemPool 112 * 113 * @{ 114 */ 115 116 /** 117 * @typedef DBusMemPool 118 * 119 * Opaque object representing a memory pool. Memory pools allow 120 * avoiding per-malloc-block memory overhead when allocating a lot of 121 * small objects that are all the same size. They are slightly 122 * faster than calling malloc() also. 123 */ 124 125 /** 126 * Creates a new memory pool, or returns #NULL on failure. Objects in 127 * the pool must be at least sizeof(void*) bytes each, due to the way 128 * memory pools work. To avoid creating 64 bit problems, this means at 129 * least 8 bytes on all platforms, unless you are 4 bytes on 32-bit 130 * and 8 bytes on 64-bit. 131 * 132 * @param element_size size of an element allocated from the pool. 133 * @param zero_elements whether to zero-initialize elements 134 * @returns the new pool or #NULL 135 */ 136 DBusMemPool* 137 _dbus_mem_pool_new (int element_size, 138 dbus_bool_t zero_elements) 139 { 140 DBusMemPool *pool; 141 142 pool = dbus_new0 (DBusMemPool, 1); 143 if (pool == NULL) 144 return NULL; 145 146 /* Make the element size at least 8 bytes. */ 147 if (element_size < 8) 148 element_size = 8; 149 150 /* these assertions are equivalent but the first is more clear 151 * to programmers that see it fail. 152 */ 153 _dbus_assert (element_size >= (int) sizeof (void*)); 154 _dbus_assert (element_size >= (int) sizeof (DBusFreedElement)); 155 156 /* align the element size to a pointer boundary so we won't get bus 157 * errors under other architectures. 158 */ 159 pool->element_size = _DBUS_ALIGN_VALUE (element_size, sizeof (void *)); 160 161 pool->zero_elements = zero_elements != FALSE; 162 163 pool->allocated_elements = 0; 164 165 /* pick a size for the first block; it increases 166 * for each block we need to allocate. This is 167 * actually half the initial block size 168 * since _dbus_mem_pool_alloc() unconditionally 169 * doubles it prior to creating a new block. */ 170 pool->block_size = pool->element_size * 8; 171 172 _dbus_assert ((pool->block_size % 173 pool->element_size) == 0); 174 175 return pool; 176 } 177 178 /** 179 * Frees a memory pool (and all elements allocated from it). 180 * 181 * @param pool the memory pool. 182 */ 183 void 184 _dbus_mem_pool_free (DBusMemPool *pool) 185 { 186 DBusMemBlock *block; 187 188 block = pool->blocks; 189 while (block != NULL) 190 { 191 DBusMemBlock *next = block->next; 192 193 dbus_free (block); 194 195 block = next; 196 } 197 198 dbus_free (pool); 199 } 200 201 /** 202 * Allocates an object from the memory pool. 203 * The object must be freed with _dbus_mem_pool_dealloc(). 204 * 205 * @param pool the memory pool 206 * @returns the allocated object or #NULL if no memory. 207 */ 208 void* 209 _dbus_mem_pool_alloc (DBusMemPool *pool) 210 { 211 #ifdef DBUS_BUILD_TESTS 212 if (_dbus_disable_mem_pools ()) 213 { 214 DBusMemBlock *block; 215 int alloc_size; 216 217 /* This is obviously really silly, but it's 218 * debug-mode-only code that is compiled out 219 * when tests are disabled (_dbus_disable_mem_pools() 220 * is a constant expression FALSE so this block 221 * should vanish) 222 */ 223 224 alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING + 225 pool->element_size; 226 227 if (pool->zero_elements) 228 block = dbus_malloc0 (alloc_size); 229 else 230 block = dbus_malloc (alloc_size); 231 232 if (block != NULL) 233 { 234 block->next = pool->blocks; 235 pool->blocks = block; 236 pool->allocated_elements += 1; 237 238 return (void*) &block->elements[0]; 239 } 240 else 241 return NULL; 242 } 243 else 244 #endif 245 { 246 if (_dbus_decrement_fail_alloc_counter ()) 247 { 248 _dbus_verbose (" FAILING mempool alloc\n"); 249 return NULL; 250 } 251 else if (pool->free_elements) 252 { 253 DBusFreedElement *element = pool->free_elements; 254 255 pool->free_elements = pool->free_elements->next; 256 257 if (pool->zero_elements) 258 memset (element, '\0', pool->element_size); 259 260 pool->allocated_elements += 1; 261 262 return element; 263 } 264 else 265 { 266 void *element; 267 268 if (pool->blocks == NULL || 269 pool->blocks->used_so_far == pool->block_size) 270 { 271 /* Need a new block */ 272 DBusMemBlock *block; 273 int alloc_size; 274 #ifdef DBUS_BUILD_TESTS 275 int saved_counter; 276 #endif 277 278 if (pool->block_size <= _DBUS_INT_MAX / 4) /* avoid overflow */ 279 { 280 /* use a larger block size for our next block */ 281 pool->block_size *= 2; 282 _dbus_assert ((pool->block_size % 283 pool->element_size) == 0); 284 } 285 286 alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING + pool->block_size; 287 288 #ifdef DBUS_BUILD_TESTS 289 /* We save/restore the counter, so that memory pools won't 290 * cause a given function to have different number of 291 * allocations on different invocations. i.e. when testing 292 * we want consistent alloc patterns. So we skip our 293 * malloc here for purposes of failed alloc simulation. 294 */ 295 saved_counter = _dbus_get_fail_alloc_counter (); 296 _dbus_set_fail_alloc_counter (_DBUS_INT_MAX); 297 #endif 298 299 if (pool->zero_elements) 300 block = dbus_malloc0 (alloc_size); 301 else 302 block = dbus_malloc (alloc_size); 303 304 #ifdef DBUS_BUILD_TESTS 305 _dbus_set_fail_alloc_counter (saved_counter); 306 _dbus_assert (saved_counter == _dbus_get_fail_alloc_counter ()); 307 #endif 308 309 if (block == NULL) 310 return NULL; 311 312 block->used_so_far = 0; 313 block->next = pool->blocks; 314 pool->blocks = block; 315 } 316 317 element = &pool->blocks->elements[pool->blocks->used_so_far]; 318 319 pool->blocks->used_so_far += pool->element_size; 320 321 pool->allocated_elements += 1; 322 323 return element; 324 } 325 } 326 } 327 328 /** 329 * Deallocates an object previously created with 330 * _dbus_mem_pool_alloc(). The previous object 331 * must have come from this same pool. 332 * @param pool the memory pool 333 * @param element the element earlier allocated. 334 * @returns #TRUE if there are no remaining allocated elements 335 */ 336 dbus_bool_t 337 _dbus_mem_pool_dealloc (DBusMemPool *pool, 338 void *element) 339 { 340 #ifdef DBUS_BUILD_TESTS 341 if (_dbus_disable_mem_pools ()) 342 { 343 DBusMemBlock *block; 344 DBusMemBlock *prev; 345 346 /* mmm, fast. ;-) debug-only code, so doesn't matter. */ 347 348 prev = NULL; 349 block = pool->blocks; 350 351 while (block != NULL) 352 { 353 if (block->elements == (unsigned char*) element) 354 { 355 if (prev) 356 prev->next = block->next; 357 else 358 pool->blocks = block->next; 359 360 dbus_free (block); 361 362 _dbus_assert (pool->allocated_elements > 0); 363 pool->allocated_elements -= 1; 364 365 if (pool->allocated_elements == 0) 366 _dbus_assert (pool->blocks == NULL); 367 368 return pool->blocks == NULL; 369 } 370 prev = block; 371 block = block->next; 372 } 373 374 _dbus_assert_not_reached ("freed nonexistent block"); 375 return FALSE; 376 } 377 else 378 #endif 379 { 380 DBusFreedElement *freed; 381 382 freed = element; 383 freed->next = pool->free_elements; 384 pool->free_elements = freed; 385 386 _dbus_assert (pool->allocated_elements > 0); 387 pool->allocated_elements -= 1; 388 389 return pool->allocated_elements == 0; 390 } 391 } 392 393 /** @} */ 394 395 #ifdef DBUS_BUILD_TESTS 396 #include "dbus-test.h" 397 #include <stdio.h> 398 #include <time.h> 399 400 static void 401 time_for_size (int size) 402 { 403 int i; 404 int j; 405 clock_t start; 406 clock_t end; 407 #define FREE_ARRAY_SIZE 512 408 #define N_ITERATIONS FREE_ARRAY_SIZE * 512 409 void *to_free[FREE_ARRAY_SIZE]; 410 DBusMemPool *pool; 411 412 _dbus_verbose ("Timings for size %d\n", size); 413 414 _dbus_verbose (" malloc\n"); 415 416 start = clock (); 417 418 i = 0; 419 j = 0; 420 while (i < N_ITERATIONS) 421 { 422 to_free[j] = dbus_malloc (size); 423 _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */ 424 425 ++j; 426 427 if (j == FREE_ARRAY_SIZE) 428 { 429 j = 0; 430 while (j < FREE_ARRAY_SIZE) 431 { 432 dbus_free (to_free[j]); 433 ++j; 434 } 435 436 j = 0; 437 } 438 439 ++i; 440 } 441 442 end = clock (); 443 444 _dbus_verbose (" created/destroyed %d elements in %g seconds\n", 445 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC); 446 447 448 449 _dbus_verbose (" mempools\n"); 450 451 start = clock (); 452 453 pool = _dbus_mem_pool_new (size, FALSE); 454 455 i = 0; 456 j = 0; 457 while (i < N_ITERATIONS) 458 { 459 to_free[j] = _dbus_mem_pool_alloc (pool); 460 _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */ 461 462 ++j; 463 464 if (j == FREE_ARRAY_SIZE) 465 { 466 j = 0; 467 while (j < FREE_ARRAY_SIZE) 468 { 469 _dbus_mem_pool_dealloc (pool, to_free[j]); 470 ++j; 471 } 472 473 j = 0; 474 } 475 476 ++i; 477 } 478 479 _dbus_mem_pool_free (pool); 480 481 end = clock (); 482 483 _dbus_verbose (" created/destroyed %d elements in %g seconds\n", 484 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC); 485 486 _dbus_verbose (" zeroed malloc\n"); 487 488 start = clock (); 489 490 i = 0; 491 j = 0; 492 while (i < N_ITERATIONS) 493 { 494 to_free[j] = dbus_malloc0 (size); 495 _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */ 496 497 ++j; 498 499 if (j == FREE_ARRAY_SIZE) 500 { 501 j = 0; 502 while (j < FREE_ARRAY_SIZE) 503 { 504 dbus_free (to_free[j]); 505 ++j; 506 } 507 508 j = 0; 509 } 510 511 ++i; 512 } 513 514 end = clock (); 515 516 _dbus_verbose (" created/destroyed %d elements in %g seconds\n", 517 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC); 518 519 _dbus_verbose (" zeroed mempools\n"); 520 521 start = clock (); 522 523 pool = _dbus_mem_pool_new (size, TRUE); 524 525 i = 0; 526 j = 0; 527 while (i < N_ITERATIONS) 528 { 529 to_free[j] = _dbus_mem_pool_alloc (pool); 530 _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */ 531 532 ++j; 533 534 if (j == FREE_ARRAY_SIZE) 535 { 536 j = 0; 537 while (j < FREE_ARRAY_SIZE) 538 { 539 _dbus_mem_pool_dealloc (pool, to_free[j]); 540 ++j; 541 } 542 543 j = 0; 544 } 545 546 ++i; 547 } 548 549 _dbus_mem_pool_free (pool); 550 551 end = clock (); 552 553 _dbus_verbose (" created/destroyed %d elements in %g seconds\n", 554 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC); 555 } 556 557 /** 558 * @ingroup DBusMemPoolInternals 559 * Unit test for DBusMemPool 560 * @returns #TRUE on success. 561 */ 562 dbus_bool_t 563 _dbus_mem_pool_test (void) 564 { 565 int i; 566 int element_sizes[] = { 4, 8, 16, 50, 124 }; 567 568 i = 0; 569 while (i < _DBUS_N_ELEMENTS (element_sizes)) 570 { 571 time_for_size (element_sizes[i]); 572 ++i; 573 } 574 575 return TRUE; 576 } 577 578 #endif /* DBUS_BUILD_TESTS */ 579