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