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