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