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