1 /* 2 * region-allocator.c -- region based memory allocator. 3 * 4 * Copyright (c) 2001-2011, NLnet Labs. All rights reserved. 5 * 6 * See LICENSE for the license. 7 * 8 */ 9 10 #include "config.h" 11 12 #include <assert.h> 13 #include <stdlib.h> 14 #include <string.h> 15 16 #include "region-allocator.h" 17 18 #ifdef ALIGNMENT 19 #undef ALIGNMENT 20 #endif 21 #define ALIGN_UP(x, s) (((x) + s - 1) & (~(s - 1))) 22 #define ALIGNMENT (sizeof(void *)) 23 #define CHECK_DOUBLE_FREE 0 /* set to 1 to perform expensive check for double recycle() */ 24 25 typedef struct cleanup cleanup_type; 26 struct cleanup 27 { 28 void (*action)(void *); 29 void *data; 30 }; 31 32 struct recycle_elem { 33 struct recycle_elem* next; 34 }; 35 36 struct region 37 { 38 size_t total_allocated; 39 size_t small_objects; 40 size_t large_objects; 41 size_t chunk_count; 42 size_t unused_space; /* Unused space due to alignment, etc. */ 43 44 size_t allocated; 45 char *initial_data; 46 char *data; 47 48 void *(*allocator)(size_t); 49 void (*deallocator)(void *); 50 51 size_t maximum_cleanup_count; 52 size_t cleanup_count; 53 cleanup_type *cleanups; 54 55 size_t chunk_size; 56 size_t large_object_size; 57 58 /* if not NULL recycling is enabled. 59 * It is an array of linked lists of parts held for recycle. 60 * The parts are all pointers to within the allocated chunks. 61 * Array [i] points to elements of size i. */ 62 struct recycle_elem** recycle_bin; 63 /* amount of memory in recycle storage */ 64 size_t recycle_size; 65 }; 66 67 68 static region_type * 69 alloc_region_base(void *(*allocator)(size_t size), 70 void (*deallocator)(void *), 71 size_t initial_cleanup_count) 72 { 73 region_type *result = (region_type *) allocator(sizeof(region_type)); 74 if (!result) return NULL; 75 76 result->total_allocated = 0; 77 result->small_objects = 0; 78 result->large_objects = 0; 79 result->chunk_count = 1; 80 result->unused_space = 0; 81 result->recycle_bin = NULL; 82 result->recycle_size = 0; 83 84 result->allocated = 0; 85 result->data = NULL; 86 result->initial_data = NULL; 87 88 result->allocator = allocator; 89 result->deallocator = deallocator; 90 91 assert(initial_cleanup_count > 0); 92 result->maximum_cleanup_count = initial_cleanup_count; 93 result->cleanup_count = 0; 94 result->cleanups = (cleanup_type *) allocator( 95 result->maximum_cleanup_count * sizeof(cleanup_type)); 96 if (!result->cleanups) { 97 deallocator(result); 98 return NULL; 99 } 100 101 result->chunk_size = DEFAULT_CHUNK_SIZE; 102 result->large_object_size = DEFAULT_LARGE_OBJECT_SIZE; 103 return result; 104 } 105 106 region_type * 107 region_create(void *(*allocator)(size_t size), 108 void (*deallocator)(void *)) 109 { 110 region_type* result = alloc_region_base(allocator, deallocator, 111 DEFAULT_INITIAL_CLEANUP_SIZE); 112 if(!result) 113 return NULL; 114 result->data = (char *) allocator(result->chunk_size); 115 if (!result->data) { 116 deallocator(result->cleanups); 117 deallocator(result); 118 return NULL; 119 } 120 result->initial_data = result->data; 121 122 return result; 123 } 124 125 126 region_type *region_create_custom(void *(*allocator)(size_t), 127 void (*deallocator)(void *), 128 size_t chunk_size, 129 size_t large_object_size, 130 size_t initial_cleanup_size, 131 int recycle) 132 { 133 region_type* result = alloc_region_base(allocator, deallocator, 134 initial_cleanup_size); 135 if(!result) 136 return NULL; 137 assert(large_object_size <= chunk_size); 138 result->chunk_size = chunk_size; 139 result->large_object_size = large_object_size; 140 if(result->chunk_size > 0) { 141 result->data = (char *) allocator(result->chunk_size); 142 if (!result->data) { 143 deallocator(result->cleanups); 144 deallocator(result); 145 return NULL; 146 } 147 result->initial_data = result->data; 148 } 149 if(recycle) { 150 result->recycle_bin = allocator(sizeof(struct recycle_elem*) 151 * result->large_object_size); 152 if(!result->recycle_bin) { 153 region_destroy(result); 154 return NULL; 155 } 156 memset(result->recycle_bin, 0, sizeof(struct recycle_elem*) 157 * result->large_object_size); 158 } 159 return result; 160 } 161 162 163 void 164 region_destroy(region_type *region) 165 { 166 void (*deallocator)(void *); 167 if (!region) 168 return; 169 170 deallocator = region->deallocator; 171 172 region_free_all(region); 173 deallocator(region->cleanups); 174 deallocator(region->initial_data); 175 if(region->recycle_bin) 176 deallocator(region->recycle_bin); 177 deallocator(region); 178 } 179 180 181 size_t 182 region_add_cleanup(region_type *region, void (*action)(void *), void *data) 183 { 184 assert(action); 185 186 if (region->cleanup_count >= region->maximum_cleanup_count) { 187 cleanup_type *cleanups = (cleanup_type *) region->allocator( 188 2 * region->maximum_cleanup_count * sizeof(cleanup_type)); 189 if (!cleanups) 190 return 0; 191 192 memcpy(cleanups, region->cleanups, 193 region->cleanup_count * sizeof(cleanup_type)); 194 region->deallocator(region->cleanups); 195 196 region->cleanups = cleanups; 197 region->maximum_cleanup_count *= 2; 198 } 199 200 region->cleanups[region->cleanup_count].action = action; 201 region->cleanups[region->cleanup_count].data = data; 202 203 ++region->cleanup_count; 204 return region->cleanup_count; 205 } 206 207 void 208 region_remove_cleanup(region_type *region, void (*action)(void *), void *data) 209 { 210 size_t i; 211 for(i=0; i<region->cleanup_count; i++) { 212 if(region->cleanups[i].action == action && 213 region->cleanups[i].data == data) { 214 region->cleanup_count--; 215 region->cleanups[i] = 216 region->cleanups[region->cleanup_count]; 217 return; 218 } 219 } 220 } 221 222 void * 223 region_alloc(region_type *region, size_t size) 224 { 225 size_t aligned_size; 226 void *result; 227 228 if (size == 0) { 229 size = 1; 230 } 231 aligned_size = ALIGN_UP(size, ALIGNMENT); 232 233 if (aligned_size >= region->large_object_size) { 234 result = region->allocator(size); 235 if (!result) 236 return NULL; 237 238 if (!region_add_cleanup(region, region->deallocator, result)) { 239 region->deallocator(result); 240 return NULL; 241 } 242 243 region->total_allocated += size; 244 ++region->large_objects; 245 246 return result; 247 } 248 249 if (region->recycle_bin && region->recycle_bin[aligned_size]) { 250 result = (void*)region->recycle_bin[aligned_size]; 251 region->recycle_bin[aligned_size] = region->recycle_bin[aligned_size]->next; 252 region->recycle_size -= aligned_size; 253 region->unused_space += aligned_size - size; 254 return result; 255 } 256 257 if (region->allocated + aligned_size > region->chunk_size) { 258 void *chunk = region->allocator(region->chunk_size); 259 size_t wasted; 260 if (!chunk) 261 return NULL; 262 263 wasted = (region->chunk_size - region->allocated) & (~(ALIGNMENT-1)); 264 if(wasted >= ALIGNMENT) { 265 /* put wasted part in recycle bin for later use */ 266 region->total_allocated += wasted; 267 ++region->small_objects; 268 region_recycle(region, region->data+region->allocated, wasted); 269 region->allocated += wasted; 270 } 271 ++region->chunk_count; 272 region->unused_space += region->chunk_size - region->allocated; 273 274 if(!region_add_cleanup(region, region->deallocator, chunk)) { 275 region->deallocator(chunk); 276 region->chunk_count--; 277 region->unused_space -= 278 region->chunk_size - region->allocated; 279 return NULL; 280 } 281 region->allocated = 0; 282 region->data = (char *) chunk; 283 } 284 285 result = region->data + region->allocated; 286 region->allocated += aligned_size; 287 288 region->total_allocated += aligned_size; 289 region->unused_space += aligned_size - size; 290 ++region->small_objects; 291 292 return result; 293 } 294 295 void * 296 region_alloc_init(region_type *region, const void *init, size_t size) 297 { 298 void *result = region_alloc(region, size); 299 if (!result) return NULL; 300 memcpy(result, init, size); 301 return result; 302 } 303 304 void * 305 region_alloc_zero(region_type *region, size_t size) 306 { 307 void *result = region_alloc(region, size); 308 if (!result) return NULL; 309 memset(result, 0, size); 310 return result; 311 } 312 313 void 314 region_free_all(region_type *region) 315 { 316 size_t i; 317 assert(region); 318 assert(region->cleanups); 319 320 i = region->cleanup_count; 321 while (i > 0) { 322 --i; 323 assert(region->cleanups[i].action); 324 region->cleanups[i].action(region->cleanups[i].data); 325 } 326 327 if(region->recycle_bin) { 328 memset(region->recycle_bin, 0, sizeof(struct recycle_elem*) 329 * region->large_object_size); 330 region->recycle_size = 0; 331 } 332 333 region->data = region->initial_data; 334 region->cleanup_count = 0; 335 region->allocated = 0; 336 337 region->total_allocated = 0; 338 region->small_objects = 0; 339 region->large_objects = 0; 340 region->chunk_count = 1; 341 region->unused_space = 0; 342 } 343 344 345 char * 346 region_strdup(region_type *region, const char *string) 347 { 348 return (char *) region_alloc_init(region, string, strlen(string) + 1); 349 } 350 351 void 352 region_recycle(region_type *region, void *block, size_t size) 353 { 354 size_t aligned_size; 355 size_t i; 356 357 if(!block || !region->recycle_bin) 358 return; 359 360 if (size == 0) { 361 size = 1; 362 } 363 aligned_size = ALIGN_UP(size, ALIGNMENT); 364 365 if(aligned_size < region->large_object_size) { 366 struct recycle_elem* elem = (struct recycle_elem*)block; 367 /* we rely on the fact that ALIGNMENT is void* so the next will fit */ 368 assert(aligned_size >= sizeof(struct recycle_elem)); 369 370 if(CHECK_DOUBLE_FREE) { 371 /* make sure the same ptr is not freed twice. */ 372 struct recycle_elem *p = region->recycle_bin[aligned_size]; 373 while(p) { 374 assert(p != elem); 375 p = p->next; 376 } 377 } 378 379 elem->next = region->recycle_bin[aligned_size]; 380 region->recycle_bin[aligned_size] = elem; 381 region->recycle_size += aligned_size; 382 region->unused_space -= aligned_size - size; 383 return; 384 } 385 386 /* a large allocation */ 387 region->total_allocated -= size; 388 --region->large_objects; 389 for(i=0; i<region->cleanup_count; i++) { 390 while(region->cleanups[i].data == block) { 391 /* perform action (deallocator) on block */ 392 region->cleanups[i].action(block); 393 region->cleanups[i].data = NULL; 394 /* remove cleanup - move last entry here, check this one again */ 395 --region->cleanup_count; 396 region->cleanups[i].action = 397 region->cleanups[region->cleanup_count].action; 398 region->cleanups[i].data = 399 region->cleanups[region->cleanup_count].data; 400 } 401 } 402 } 403 404 void 405 region_dump_stats(region_type *region, FILE *out) 406 { 407 fprintf(out, "%lu objects (%lu small/%lu large), %lu bytes allocated (%lu wasted) in %lu chunks, %lu cleanups, %lu in recyclebin", 408 (unsigned long) (region->small_objects + region->large_objects), 409 (unsigned long) region->small_objects, 410 (unsigned long) region->large_objects, 411 (unsigned long) region->total_allocated, 412 (unsigned long) region->unused_space, 413 (unsigned long) region->chunk_count, 414 (unsigned long) region->cleanup_count, 415 (unsigned long) region->recycle_size); 416 if(1 && region->recycle_bin) { 417 /* print details of the recycle bin */ 418 size_t i; 419 for(i=0; i<region->large_object_size; i++) { 420 size_t count = 0; 421 struct recycle_elem* el = region->recycle_bin[i]; 422 while(el) { 423 count++; 424 el = el->next; 425 } 426 if(i%ALIGNMENT == 0 && i!=0) 427 fprintf(out, " %lu", (unsigned long)count); 428 } 429 } 430 } 431 432 size_t region_get_recycle_size(region_type* region) 433 { 434 return region->recycle_size; 435 } 436 437 /* debug routine, includes here to keep base region-allocator independent */ 438 #undef ALIGN_UP 439 #include "util.h" 440 void 441 region_log_stats(region_type *region) 442 { 443 char buf[10240], *str=buf; 444 int strl = sizeof(buf); 445 int len; 446 snprintf(str, strl, "%lu objects (%lu small/%lu large), %lu bytes allocated (%lu wasted) in %lu chunks, %lu cleanups, %lu in recyclebin", 447 (unsigned long) (region->small_objects + region->large_objects), 448 (unsigned long) region->small_objects, 449 (unsigned long) region->large_objects, 450 (unsigned long) region->total_allocated, 451 (unsigned long) region->unused_space, 452 (unsigned long) region->chunk_count, 453 (unsigned long) region->cleanup_count, 454 (unsigned long) region->recycle_size); 455 len = strlen(str); 456 str+=len; 457 strl-=len; 458 if(1 && region->recycle_bin) { 459 /* print details of the recycle bin */ 460 size_t i; 461 for(i=0; i<region->large_object_size; i++) { 462 size_t count = 0; 463 struct recycle_elem* el = region->recycle_bin[i]; 464 while(el) { 465 count++; 466 el = el->next; 467 } 468 if(i%ALIGNMENT == 0 && i!=0) { 469 snprintf(str, strl, " %lu", (unsigned long)count); 470 len = strlen(str); 471 str+=len; 472 strl-=len; 473 } 474 } 475 } 476 log_msg(LOG_INFO, "memory: %s", buf); 477 } 478