1 /* 2 * Similar core function to LGPL licensed talloc from Samba 3 */ 4 #define CHECK_ALLOCATION 0 5 6 #include "hieralloc.h" 7 #include <stdlib.h> 8 #include <string.h> 9 #include <assert.h> 10 11 #if CHECK_ALLOCATION 12 #include <set> 13 #endif 14 15 typedef struct hieralloc_header 16 { 17 unsigned beginMagic; 18 struct hieralloc_header * parent; 19 struct hieralloc_header * nextSibling, * prevSibling; 20 struct hieralloc_header * child; 21 const char * name; 22 unsigned size, childCount, refCount; 23 int (* destructor)(void *); 24 unsigned endMagic; 25 } hieralloc_header_t; 26 27 #define BEGIN_MAGIC() (13377331) 28 #define END_MAGIC(header) ((unsigned)((const hieralloc_header_t *)header + 1) % 0x10000 | 0x13370000) 29 30 static hieralloc_header_t hieralloc_global_header = {BEGIN_MAGIC(), 0, 0, 0, 0, "hieralloc_hieralloc_global_header", 0, 0 ,1, 0, 0x13370000}; 31 32 #if CHECK_ALLOCATION 33 static std::set<void *> allocations; 34 #endif 35 36 #ifdef __cplusplus 37 extern "C" { 38 #endif 39 40 // Returns 1 if it's a valid header 41 static inline int check_header(const hieralloc_header_t * header) 42 { 43 if (BEGIN_MAGIC() != header->beginMagic) 44 printf("*** hieralloc check_header fail: %p ***\n", header + 1); 45 assert(BEGIN_MAGIC() == header->beginMagic); 46 if (&hieralloc_global_header == header) 47 { 48 assert(0x13370000 == header->endMagic); 49 return 1; 50 } 51 assert(END_MAGIC(header) == header->endMagic); 52 assert(!header->nextSibling || header->nextSibling->prevSibling == header); 53 assert(!header->nextSibling || header->nextSibling->parent == header->parent); 54 assert(!header->prevSibling || header->prevSibling->nextSibling == header); 55 assert(!header->prevSibling || header->prevSibling->parent == header->parent); 56 return 1; 57 } 58 59 static inline hieralloc_header_t * get_header(const void *ptr) 60 { 61 hieralloc_header_t * header = (hieralloc_header_t *)(ptr) - 1; 62 check_header(header); 63 return header; 64 } 65 66 static void check_children(hieralloc_header_t * header) 67 { 68 check_header(header); 69 unsigned childCount = 0; 70 hieralloc_header_t * child = header->child; 71 while (child) 72 { 73 childCount++; 74 check_children(child); 75 child = child->nextSibling; 76 } 77 assert(childCount == header->childCount); 78 } 79 80 81 // attach to parent and siblings 82 static void add_to_parent(hieralloc_header_t * parent, hieralloc_header_t * header) 83 { 84 assert(NULL == header->parent); 85 assert(NULL == header->prevSibling); 86 assert(NULL == header->nextSibling); 87 88 if (parent->child) 89 { 90 // hieralloc_header_t * child = parent->child; 91 // while (child) 92 // { 93 // assert(child != header); 94 // child = child->nextSibling; 95 // } 96 parent->child->prevSibling = header; 97 } 98 header->nextSibling = parent->child; 99 header->prevSibling = NULL; 100 header->parent = parent; 101 parent->child = header; 102 parent->childCount++; 103 104 assert(!header->nextSibling || header->nextSibling->prevSibling == header); 105 assert(!header->nextSibling || header->nextSibling->parent == header->parent); 106 assert(!header->prevSibling || header->prevSibling->nextSibling == header); 107 assert(!header->prevSibling || header->prevSibling->parent == header->parent); 108 } 109 110 // detach from parent and siblings 111 static void remove_from_parent(hieralloc_header_t * header) 112 { 113 hieralloc_header_t * parent = header->parent; 114 hieralloc_header_t * sibling = header->prevSibling; 115 assert(!header->nextSibling || header->nextSibling->prevSibling == header); 116 assert(!header->nextSibling || header->nextSibling->parent == header->parent); 117 assert(!header->prevSibling || header->prevSibling->nextSibling == header); 118 assert(!header->prevSibling || header->prevSibling->parent == header->parent); 119 if (sibling) 120 { 121 if (sibling->nextSibling != header) 122 { 123 printf("&sibling->nextSibling=%p &header=%p \n", &sibling->nextSibling, &header); 124 printf("sibling->nextSibling=%p header=%p \n", sibling->nextSibling, header); 125 } 126 sibling->nextSibling = header->nextSibling; 127 if (header->nextSibling) 128 header->nextSibling->prevSibling = sibling; 129 header->prevSibling = NULL; 130 header->nextSibling = NULL; 131 } 132 else 133 { 134 assert(parent->child == header); 135 parent->child = header->nextSibling; 136 if (header->nextSibling) 137 header->nextSibling->prevSibling = NULL; 138 header->nextSibling = NULL; 139 } 140 header->parent = NULL; 141 parent->childCount--; 142 } 143 144 // allocate memory and attach to parent context and siblings 145 void * hieralloc_allocate(const void * context, unsigned size, const char * name) 146 { 147 hieralloc_header_t * ptr = (hieralloc_header_t *)malloc(size + sizeof(hieralloc_header_t)); 148 assert(ptr); 149 memset(ptr, 0xcd, sizeof(*ptr)); 150 ptr->beginMagic = BEGIN_MAGIC(); 151 ptr->parent = ptr->child = ptr->prevSibling = ptr->nextSibling = NULL; 152 ptr->name = name; 153 ptr->size = size; 154 ptr->childCount = 0; 155 ptr->refCount = 1; 156 ptr->destructor = NULL; 157 ptr->endMagic = END_MAGIC(ptr); 158 159 hieralloc_header_t * parent = NULL; 160 if (!context) 161 parent = &hieralloc_global_header; 162 else 163 parent = get_header(context); 164 add_to_parent(parent, ptr); 165 #if CHECK_ALLOCATION 166 assert(allocations.find(ptr + 1) == allocations.end()); 167 allocations.insert(ptr + 1); 168 #endif 169 return ptr + 1; 170 } 171 172 // (re)allocate memory and attach to parent context and siblings 173 void * hieralloc_reallocate(const void * context, void * ptr, unsigned size, const char * name) 174 { 175 if (NULL == ptr) 176 return hieralloc_allocate(context, size, name); 177 #if CHECK_ALLOCATION 178 assert(allocations.find(ptr) != allocations.end()); 179 #endif 180 if (NULL == context) 181 context = &hieralloc_global_header + 1; 182 183 hieralloc_header_t * header = get_header(ptr); 184 hieralloc_header_t * parent = header->parent; 185 186 if (get_header(context) != get_header(ptr)->parent) 187 { 188 remove_from_parent(header); 189 parent = get_header(context); 190 add_to_parent(parent, header); 191 } 192 193 header = (hieralloc_header_t *)realloc(header, size + sizeof(hieralloc_header_t)); 194 assert(header); 195 header->size = size; 196 header->name = name; 197 if (ptr == (header + 1)) 198 return ptr; // realloc didn't move allocation 199 200 header->beginMagic = BEGIN_MAGIC(); 201 header->endMagic = END_MAGIC(header); 202 if (header->nextSibling) 203 header->nextSibling->prevSibling = header; 204 if (header->prevSibling) 205 header->prevSibling->nextSibling = header; 206 else 207 parent->child = header; 208 209 hieralloc_header_t * child = header->child; 210 while (child) 211 { 212 child->parent = header; 213 child = child->nextSibling; 214 } 215 #if CHECK_ALLOCATION 216 allocations.erase(ptr); 217 assert(allocations.find(header + 1) == allocations.end()); 218 allocations.insert(header + 1); 219 #endif 220 return header + 1; 221 } 222 223 // calls destructor if set, and frees children. 224 // if destructor returns -1, then do nothing and return -1. 225 int hieralloc_free(void * ptr) 226 { 227 if (!ptr) 228 return 0; 229 230 hieralloc_header_t * header = get_header(ptr); 231 232 header->refCount--; 233 if (header->refCount > 0) 234 return -1; 235 236 if (header->destructor) 237 if (header->destructor(ptr)) 238 return -1; 239 240 int ret = 0; 241 242 //* TODO: implement reference and steal first 243 hieralloc_header_t * child = header->child; 244 while (child) 245 { 246 hieralloc_header_t * current = child; 247 assert(!current->prevSibling); 248 child = child->nextSibling; 249 if (hieralloc_free(current + 1)) 250 { 251 ret = -1; 252 remove_from_parent(current); 253 add_to_parent(header->parent, current); 254 assert(0); // shouldn't happen since reference is always 1 255 } 256 257 } 258 259 if (ret) 260 return -1; 261 262 assert(0 == header->childCount); 263 assert(!header->child); 264 remove_from_parent(header); 265 memset(header, 0xfe, header->size + sizeof(*header)); 266 #if CHECK_ALLOCATION 267 assert(allocations.find(ptr) != allocations.end()); 268 allocations.erase(ptr); 269 // don't free yet to force allocations to new addresses for checking double freeing 270 #else 271 free(header); 272 #endif 273 return 0; 274 } 275 276 // not implemented from talloc_reference 277 void * hieralloc_reference(const void * ref_ctx, const void * ptr) 278 { 279 return (void *)ptr; 280 } 281 282 // not implemented from talloc_unlink 283 int hieralloc_unlink(const void * ctx, void *ptr) 284 { 285 if (!ptr) 286 return -1; 287 //assert(get_header(ptr)->refCount > 0); 288 //get_header(ptr)->refCount--; 289 return 0; 290 } 291 292 // moves allocation to new parent context; maintain children but update siblings 293 // returns ptr on success 294 void * hieralloc_steal(const void * new_ctx, const void * ptr) 295 { 296 hieralloc_header_t * header = get_header(ptr); 297 remove_from_parent(header); 298 add_to_parent(get_header(new_ctx), header); 299 return (void *)ptr; 300 } 301 302 // creates 0 allocation to be used as parent context 303 void * hieralloc_init(const char * name) 304 { 305 return hieralloc_allocate(NULL, 0, name); 306 } 307 308 // returns global context 309 void * hieralloc_autofree_context() 310 { 311 return &hieralloc_global_header + 1; 312 } 313 314 // sets destructor to be called before freeing; dctor return -1 aborts free 315 void hieralloc_set_destructor(const void * ptr, int (* destructor)(void *)) 316 { 317 get_header(ptr)->destructor = destructor; 318 } 319 320 // gets parent context of allocated memory 321 void * hieralloc_parent(const void * ptr) 322 { 323 const hieralloc_header_t * header = get_header(ptr); 324 return header->parent + 1; 325 } 326 327 // allocate and zero memory 328 void * _hieralloc_zero(const void * ctx, unsigned size, const char * name) 329 { 330 void *p = hieralloc_allocate(ctx, size, name); 331 if (p) 332 memset(p, 0, size); 333 return p; 334 } 335 336 // allocate and copy 337 char * hieralloc_strndup(const void * ctx, const char * str, unsigned len) 338 { 339 if (!str) 340 return NULL; 341 342 const char *p = (const char *)memchr(str, '\0', len); 343 len = (p ? p - str : len); 344 char * ret = (char *)hieralloc_allocate(ctx, len + 1, str); 345 if (!ret) 346 return NULL; 347 memcpy(ret, str, len); 348 ret[len] = 0; 349 get_header(ret)->name = ret; 350 return ret; 351 } 352 353 // allocate and copy 354 char * hieralloc_strdup(const void * ctx, const char * str) 355 { 356 if (!str) 357 return NULL; 358 return hieralloc_strndup(ctx, str, strlen(str)); 359 } 360 361 static char * _hieralloc_strlendup_append(char * str, unsigned len, 362 const char * append, unsigned appendLen) 363 { 364 //char * ret = hieralloc_allocate(str, sizeof(char) * (len + appendLen + 1), str); 365 //memcpy(ret, str, len); 366 hieralloc_header_t * header = get_header(str); 367 char * ret = (char *)hieralloc_reallocate(header->parent + 1, str, sizeof(char) * (len + appendLen + 1), str); 368 if (!ret) 369 return NULL; 370 memcpy(ret + len, append, appendLen); 371 ret[len + appendLen] = 0; 372 get_header(ret)->name = ret; 373 return ret; 374 } 375 376 // reallocate and append 377 char * hieralloc_strdup_append(char * str, const char * append) 378 { 379 if (!str) 380 return hieralloc_strdup(NULL, append); 381 if (!append) 382 return str; 383 return _hieralloc_strlendup_append(str, strlen(str), append, strlen(append)); 384 } 385 386 // reallocate and append 387 char * hieralloc_strndup_append(char * str, const char * append, unsigned len) 388 { 389 if (!str) 390 return hieralloc_strdup(NULL, append); 391 if (!append) 392 return str; 393 const char *p = (const char *)memchr(append, '\0', len); 394 len = (p ? p - append : len); 395 return _hieralloc_strlendup_append(str, strlen(str), append, len); 396 } 397 398 // allocate and vsprintf 399 char * hieralloc_vasprintf(const void * ctx, const char * fmt, va_list va) 400 { 401 va_list va2; 402 va_copy(va2, va); 403 char c = 0; 404 int len = vsnprintf(&c, 1, fmt, va2); // count how many chars would be printed 405 va_end(va2); 406 407 assert(len >= 0); // some vsnprintf may return -1 408 if (len < 0) 409 return NULL; 410 411 char * ret = (char *)hieralloc_allocate(ctx, len + 1, fmt); 412 if (!ret) 413 return NULL; 414 415 va_copy(va2, va); 416 vsnprintf(ret, len + 1, fmt, va2); 417 va_end(va2); 418 419 get_header(ret)->name = ret; 420 return ret; 421 } 422 423 // allocate and sprintf 424 char * hieralloc_asprintf(const void * ctx, const char * fmt, ...) 425 { 426 va_list va; 427 va_start(va, fmt); 428 char * ret = hieralloc_vasprintf(ctx, fmt, va); 429 va_end(va); 430 return ret; 431 } 432 433 // reallocate and append vsprintf 434 char * hieralloc_vasprintf_append(char * str, const char * fmt, va_list va) 435 { 436 if (!str) 437 return hieralloc_vasprintf(NULL, fmt, va); 438 439 int len = strlen(str); 440 va_list va2; 441 va_copy(va2, va); 442 char c = 0; 443 int appendLen = vsnprintf(&c, 1, fmt, va2); // count how many chars would be printed 444 va_end(va2); 445 446 assert(appendLen >= 0); // some vsnprintf may return -1 447 if (appendLen < 0) 448 return str; 449 str = (char *)hieralloc_reallocate(NULL, str, sizeof(char) * (len + appendLen + 1), str); 450 if (!str) 451 return NULL; 452 453 va_copy(va2, va); 454 vsnprintf(str + len, appendLen + 1, fmt, va2); 455 va_end(va2); 456 457 get_header(str)->name = str; 458 return str; 459 } 460 461 // reallocate and append sprintf 462 char * hieralloc_asprintf_append(char * str, const char * fmt, ...) 463 { 464 va_list va; 465 va_start(va, fmt); 466 str = hieralloc_vasprintf_append(str, fmt, va); 467 va_end(va); 468 return str; 469 } 470 471 static void _hieralloc_report(const hieralloc_header_t * header, FILE * file, unsigned tab) 472 { 473 unsigned i = 0; 474 for (i = 0; i < tab; i++) 475 fputc(' ', file); 476 check_header(header); 477 fprintf(file, "%p: child=%d ref=%d size=%d dctor=%p name='%.256s' \n", header + 1, 478 header->childCount, header->refCount, header->size, header->destructor, header->name); 479 const hieralloc_header_t * child = header->child; 480 while (child) 481 { 482 _hieralloc_report(child, file, tab + 2); 483 child = child->nextSibling; 484 } 485 486 } 487 488 // report self and child allocations 489 void hieralloc_report(const void * ptr, FILE * file) 490 { 491 if (NULL == ptr) 492 ptr = &hieralloc_global_header + 1; 493 fputs("hieralloc_report: \n", file); 494 _hieralloc_report(get_header(ptr), file, 0); 495 } 496 497 static void _hieralloc_report_brief(const hieralloc_header_t * header, FILE * file, unsigned * data) 498 { 499 check_header(header); 500 data[0]++; 501 data[1] += header->size; 502 data[2] += header->childCount; 503 data[3] += header->refCount; 504 const hieralloc_header_t * child = header->child; 505 while (child) 506 { 507 _hieralloc_report_brief(child, file, data); 508 child = child->nextSibling; 509 } 510 } 511 512 void hieralloc_report_brief(const void * ptr, FILE * file) 513 { 514 if (NULL == ptr) 515 ptr = &hieralloc_global_header + 1; 516 unsigned data [4] = {0}; 517 _hieralloc_report_brief(get_header(ptr), file, data); 518 fprintf(file, "hieralloc_report %p total: count=%d size=%d child=%d ref=%d \n", 519 ptr, data[0], data[1], data[2], data[3]); 520 } 521 522 void hieralloc_report_lineage(const void * ptr, FILE * file, int tab) 523 { 524 const hieralloc_header_t * header = get_header(ptr); 525 if (header->parent) 526 hieralloc_report_lineage(header->parent + 1, file, tab + 2); 527 for (tab; tab >=0; tab--) 528 fputc(' ', file); 529 fprintf(file, "hieralloc_report_lineage %p: size=%d child=%d ref=%d name='%s' parent=%p \n", 530 ptr, header->size, header->childCount, header->refCount, header->name, header->parent ? header->parent + 1 : NULL); 531 } 532 533 int hieralloc_find(const void * top, const void * ptr, FILE * file, int tab) 534 { 535 int found = 0; 536 if (NULL == top) 537 top = &hieralloc_global_header + 1; 538 if (0 == tab && file) 539 fputs("hieralloc_find start \n", file); 540 if (top == ptr) 541 { 542 if (file) 543 fprintf(file, "hieralloc_found %p \n", ptr); 544 found++; 545 } 546 const hieralloc_header_t * start = get_header(top); 547 const hieralloc_header_t * child = start->child; 548 while (child) 549 { 550 found += hieralloc_find(child + 1, ptr, file, tab + 2); 551 child = child->nextSibling; 552 } 553 if (0 == tab && file) 554 fprintf(file, "hieralloc_find end found=%d \n", found); 555 return found; 556 } 557 558 #ifdef __cplusplus 559 } // extern "C" 560 #endif 561
