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