dbus-mempool.c revision 17fbe2b702cdc880abd6cbe117e620b6432f42e0
1/* -*- mode: C; c-file-style: "gnu" -*- */ 2/* dbus-mempool.h Memory pools 3 * 4 * Copyright (C) 2002 Red Hat, Inc. 5 * 6 * Licensed under the Academic Free License version 1.2 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 26/** 27 * @defgroup DBusMemPool memory pools 28 * @ingroup DBusInternals 29 * @brief DBusMemPool object 30 * 31 * Types and functions related to DBusMemPool. A memory pool is used 32 * to decrease memory fragmentation/overhead and increase speed for 33 * blocks of small uniformly-sized objects. The main point is to avoid 34 * the overhead of a malloc block for each small object, speed is 35 * secondary. 36 */ 37 38/** 39 * @defgroup DBusMemPoolInternals Memory pool implementation details 40 * @ingroup DBusInternals 41 * @brief DBusMemPool implementation details 42 * 43 * The guts of DBusMemPool. 44 * 45 * @{ 46 */ 47 48/** 49 * typedef so DBusFreedElement struct can refer to itself. 50 */ 51typedef struct DBusFreedElement DBusFreedElement; 52 53/** 54 * struct representing an element on the free list. 55 * We just cast freed elements to this so we can 56 * make a list out of them. 57 */ 58struct DBusFreedElement 59{ 60 DBusFreedElement *next; /**< next element of the free list */ 61}; 62 63/** 64 * The dummy size of the variable-length "elements" 65 * field in DBusMemBlock 66 */ 67#define ELEMENT_PADDING 4 68 69/** 70 * Typedef for DBusMemBlock so the struct can recursively 71 * point to itself. 72 */ 73typedef struct DBusMemBlock DBusMemBlock; 74 75/** 76 * DBusMemBlock object represents a single malloc()-returned 77 * block that gets chunked up into objects in the memory pool. 78 */ 79struct DBusMemBlock 80{ 81 DBusMemBlock *next; /**< next block in the list, which is already used up; 82 * only saved so we can free all the blocks 83 * when we free the mem pool. 84 */ 85 86 int used_so_far; /**< bytes of this block already allocated as elements. */ 87 88 unsigned char elements[ELEMENT_PADDING]; /**< the block data, actually allocated to required size */ 89}; 90 91/** 92 * Internals fields of DBusMemPool 93 */ 94struct DBusMemPool 95{ 96 int element_size; /**< size of a single object in the pool */ 97 int block_size; /**< size of most recently allocated block */ 98 unsigned int zero_elements : 1; /**< whether to zero-init allocated elements */ 99 100 DBusFreedElement *free_elements; /**< a free list of elements to recycle */ 101 DBusMemBlock *blocks; /**< blocks of memory from malloc() */ 102}; 103 104/** @} */ 105 106/** 107 * @addtogroup DBusMemPool 108 * 109 * @{ 110 */ 111 112/** 113 * @typedef DBusMemPool 114 * 115 * Opaque object representing a memory pool. Memory pools allow 116 * avoiding per-malloc-block memory overhead when allocating a lot of 117 * small objects that are all the same size. They are slightly 118 * faster than calling malloc() also. 119 */ 120 121/** 122 * Creates a new memory pool, or returns #NULL on failure. Objects in 123 * the pool must be at least sizeof(void*) bytes each, due to the way 124 * memory pools work. To avoid creating 64 bit problems, this means at 125 * least 8 bytes on all platforms, unless you are 4 bytes on 32-bit 126 * and 8 bytes on 64-bit. 127 * 128 * @param element_size size of an element allocated from the pool. 129 * @param zero_elements whether to zero-initialize elements 130 * @returns the new pool or #NULL 131 */ 132DBusMemPool* 133_dbus_mem_pool_new (int element_size, 134 dbus_bool_t zero_elements) 135{ 136 DBusMemPool *pool; 137 138 pool = dbus_new0 (DBusMemPool, 1); 139 if (pool == NULL) 140 return NULL; 141 142 /* these assertions are equivalent but the first is more clear 143 * to programmers that see it fail. 144 */ 145 _dbus_assert (element_size >= (int) sizeof (void*)); 146 _dbus_assert (element_size >= (int) sizeof (DBusFreedElement)); 147 148 pool->element_size = element_size; 149 pool->zero_elements = zero_elements != FALSE; 150 151 /* pick a size for the first block; it increases 152 * for each block we need to allocate. This is 153 * actually half the initial block size 154 * since _dbus_mem_pool_alloc() unconditionally 155 * doubles it prior to creating a new block. 156 */ 157 pool->block_size = element_size * 8; 158 159 _dbus_assert ((pool->block_size % 160 pool->element_size) == 0); 161 162 return pool; 163} 164 165/** 166 * Frees a memory pool (and all elements allocated from it). 167 * 168 * @param pool the memory pool. 169 */ 170void 171_dbus_mem_pool_free (DBusMemPool *pool) 172{ 173 DBusMemBlock *block; 174 175 block = pool->blocks; 176 while (block != NULL) 177 { 178 DBusMemBlock *next = block->next; 179 180 dbus_free (block); 181 182 block = next; 183 } 184 185 dbus_free (pool); 186} 187 188/** 189 * Allocates an object from the memory pool. 190 * The object must be freed with _dbus_mem_pool_dealloc(). 191 * 192 * @param pool the memory pool 193 * @returns the allocated object or #NULL if no memory. 194 */ 195void* 196_dbus_mem_pool_alloc (DBusMemPool *pool) 197{ 198 if (pool->free_elements) 199 { 200 DBusFreedElement *element = pool->free_elements; 201 202 pool->free_elements = pool->free_elements->next; 203 204 if (pool->zero_elements) 205 memset (element, '\0', pool->element_size); 206 207 return element; 208 } 209 else 210 { 211 void *element; 212 213 if (pool->blocks == NULL || 214 pool->blocks->used_so_far == pool->block_size) 215 { 216 /* Need a new block */ 217 DBusMemBlock *block; 218 int alloc_size; 219 220 if (pool->block_size <= _DBUS_INT_MAX / 4) /* avoid overflow */ 221 { 222 /* use a larger block size for our next block */ 223 pool->block_size *= 2; 224 _dbus_assert ((pool->block_size % 225 pool->element_size) == 0); 226 } 227 228 alloc_size = sizeof (DBusMemBlock) - ELEMENT_PADDING + pool->block_size; 229 230 if (pool->zero_elements) 231 block = dbus_malloc0 (alloc_size); 232 else 233 block = dbus_malloc (alloc_size); 234 235 if (block == NULL) 236 return NULL; 237 238 block->used_so_far = 0; 239 block->next = pool->blocks; 240 pool->blocks = block; 241 } 242 243 element = &pool->blocks->elements[pool->blocks->used_so_far]; 244 245 pool->blocks->used_so_far += pool->element_size; 246 247 return element; 248 } 249} 250 251/** 252 * Deallocates an object previously created with 253 * _dbus_mem_pool_alloc(). The previous object 254 * must have come from this same pool. 255 * @param pool the memory pool 256 * @param element the element earlier allocated. 257 */ 258void 259_dbus_mem_pool_dealloc (DBusMemPool *pool, 260 void *element) 261{ 262 DBusFreedElement *freed; 263 264 freed = element; 265 freed->next = pool->free_elements; 266 pool->free_elements = freed; 267} 268 269/** @} */ 270 271#ifdef DBUS_BUILD_TESTS 272#include "dbus-test.h" 273#include <stdio.h> 274#include <time.h> 275 276static void 277time_for_size (int size) 278{ 279 int i; 280 int j; 281 clock_t start; 282 clock_t end; 283#define FREE_ARRAY_SIZE 512 284#define N_ITERATIONS FREE_ARRAY_SIZE * 512 285 void *to_free[FREE_ARRAY_SIZE]; 286 DBusMemPool *pool; 287 288 printf ("Timings for size %d\n", size); 289 290 printf (" malloc\n"); 291 292 start = clock (); 293 294 i = 0; 295 j = 0; 296 while (i < N_ITERATIONS) 297 { 298 to_free[j] = dbus_malloc (size); 299 _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */ 300 301 ++j; 302 303 if (j == FREE_ARRAY_SIZE) 304 { 305 j = 0; 306 while (j < FREE_ARRAY_SIZE) 307 { 308 dbus_free (to_free[j]); 309 ++j; 310 } 311 312 j = 0; 313 } 314 315 ++i; 316 } 317 318 end = clock (); 319 320 printf (" created/destroyed %d elements in %g seconds\n", 321 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC); 322 323 324 325 printf (" mempools\n"); 326 327 start = clock (); 328 329 pool = _dbus_mem_pool_new (size, FALSE); 330 331 i = 0; 332 j = 0; 333 while (i < N_ITERATIONS) 334 { 335 to_free[j] = _dbus_mem_pool_alloc (pool); 336 _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */ 337 338 ++j; 339 340 if (j == FREE_ARRAY_SIZE) 341 { 342 j = 0; 343 while (j < FREE_ARRAY_SIZE) 344 { 345 _dbus_mem_pool_dealloc (pool, to_free[j]); 346 ++j; 347 } 348 349 j = 0; 350 } 351 352 ++i; 353 } 354 355 _dbus_mem_pool_free (pool); 356 357 end = clock (); 358 359 printf (" created/destroyed %d elements in %g seconds\n", 360 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC); 361 362 printf (" zeroed malloc\n"); 363 364 start = clock (); 365 366 i = 0; 367 j = 0; 368 while (i < N_ITERATIONS) 369 { 370 to_free[j] = dbus_malloc0 (size); 371 _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */ 372 373 ++j; 374 375 if (j == FREE_ARRAY_SIZE) 376 { 377 j = 0; 378 while (j < FREE_ARRAY_SIZE) 379 { 380 dbus_free (to_free[j]); 381 ++j; 382 } 383 384 j = 0; 385 } 386 387 ++i; 388 } 389 390 end = clock (); 391 392 printf (" created/destroyed %d elements in %g seconds\n", 393 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC); 394 395 printf (" zeroed mempools\n"); 396 397 start = clock (); 398 399 pool = _dbus_mem_pool_new (size, TRUE); 400 401 i = 0; 402 j = 0; 403 while (i < N_ITERATIONS) 404 { 405 to_free[j] = _dbus_mem_pool_alloc (pool); 406 _dbus_assert (to_free[j] != NULL); /* in a real app of course this is wrong */ 407 408 ++j; 409 410 if (j == FREE_ARRAY_SIZE) 411 { 412 j = 0; 413 while (j < FREE_ARRAY_SIZE) 414 { 415 _dbus_mem_pool_dealloc (pool, to_free[j]); 416 ++j; 417 } 418 419 j = 0; 420 } 421 422 ++i; 423 } 424 425 _dbus_mem_pool_free (pool); 426 427 end = clock (); 428 429 printf (" created/destroyed %d elements in %g seconds\n", 430 N_ITERATIONS, (end - start) / (double) CLOCKS_PER_SEC); 431} 432 433/** 434 * @ingroup DBusMemPoolInternals 435 * Unit test for DBusMemPool 436 * @returns #TRUE on success. 437 */ 438dbus_bool_t 439_dbus_mem_pool_test (void) 440{ 441 int i; 442 int element_sizes[] = { 4, 8, 16, 50, 124 }; 443 444 i = 0; 445 while (i < _DBUS_N_ELEMENTS (element_sizes)) 446 { 447 time_for_size (element_sizes[i]); 448 ++i; 449 } 450 451 return TRUE; 452} 453 454#endif /* DBUS_BUILD_TESTS */ 455