git.ozlabs.org Git - ccan/blob - ccan/tal/tal.c

   1 /* Licensed under BSD-MIT - see LICENSE file for details */
   2 #include <ccan/tal/tal.h>
   3 #include <ccan/compiler/compiler.h>
   4 #include <ccan/hash/hash.h>
   5 #include <ccan/list/list.h>
   6 #include <ccan/take/take.h>
   7 #include <assert.h>
   8 #include <stdio.h>
   9 #include <stdarg.h>
  10 #include <stddef.h>
  11 #include <string.h>
  12 #include <limits.h>
  13 #include <errno.h>
  14
  15 //#define TAL_DEBUG 1
  16
  17 /* How large should grouips get? */
  18 #define GROUP_NODE_AVERAGE 32
  19
  20 /* 32-bit type field, first byte 0 in either endianness. */
  21 enum prop_type {
  22         CHILDREN = 0x00c1d500,
  23         GROUP = 0x00600d00,
  24         DESTRUCTOR = 0x00de5700,
  25         NAME = 0x00111100,
  26 };
  27
  28 struct tal_hdr {
  29         struct tal_hdr *next;
  30         struct prop_hdr *prop;
  31 };
  32
  33 struct prop_hdr {
  34         enum prop_type type;
  35         struct prop_hdr *next;
  36 };
  37
  38 /* Unlike other properties, this is owned by parent, not child! */
  39 struct group {
  40         struct prop_hdr hdr; /* GROUP */
  41         struct list_head list; /* Head for child->group, node for others. */
  42         /* We point to parent's children property, as it doesn't move! */
  43         struct children *parent_child;
  44         struct tal_hdr *first_child;
  45 };
  46
  47 struct children {
  48         struct prop_hdr hdr; /* CHILDREN */
  49         struct tal_hdr *parent;
  50         /* We always have one group.  Others may be added. */
  51         struct group group;
  52 };
  53
  54 struct destructor {
  55         struct prop_hdr hdr; /* DESTRUCTOR */
  56         void (*destroy)(void *me);
  57 };
  58
  59 struct name {
  60         struct prop_hdr hdr; /* NAME */
  61         char name[];
  62 };
  63
  64 static struct {
  65         struct tal_hdr hdr;
  66         struct children c;
  67 } null_parent = { { NULL, &null_parent.c.hdr },
  68                   { { CHILDREN, NULL },
  69                     &null_parent.hdr,
  70                     { { GROUP, NULL },
  71                       { { &null_parent.c.group.list.n,
  72                           &null_parent.c.group.list.n } },
  73                       &null_parent.c, NULL } }
  74 };
  75
  76
  77 static void *(*allocfn)(size_t size) = malloc;
  78 static void *(*resizefn)(void *, size_t size) = realloc;
  79 static void (*freefn)(void *) = free;
  80 static void (*errorfn)(const char *msg) = (void *)abort;
  81
  82 static inline void COLD call_error(const char *msg)
  83 {
  84         errorfn(msg);
  85 }
  86
  87 static bool get_destroying_bit(struct tal_hdr *next)
  88 {
  89         return (size_t)next & 1;
  90 }
  91
  92 static void set_destroying_bit(struct tal_hdr **next)
  93 {
  94         *next = (void *)((size_t)next | 1);
  95 }
  96
  97 static struct tal_hdr *ignore_destroying_bit(struct tal_hdr *next)
  98 {
  99         return (void *)((size_t)next & ~(size_t)1);
 100 }
 101
 102 static struct group *next_group(struct group *group)
 103 {
 104         return list_entry(group->list.n.next, struct group, list.n);
 105 }
 106
 107 static bool initialized = false;
 108
 109 /* This means valgrind can see leaks. */
 110 static void tal_cleanup(void)
 111 {
 112         struct group *i, *next;
 113
 114         /* Unlink null_parent. */
 115         for (i = next_group(&null_parent.c.group);
 116              i != &null_parent.c.group;
 117              i = next) {
 118                 next = next_group(i);
 119                 freefn(i);
 120         }
 121         null_parent.c.group.first_child = NULL;
 122
 123         /* Cleanup any taken pointers. */
 124         take_cleanup();
 125 }
 126
 127 /* For allocation failures inside ccan/take */
 128 static void take_alloc_failed(const void *p)
 129 {
 130         tal_free(p);
 131 }
 132
 133 #ifndef NDEBUG
 134 static const void *bounds_start, *bounds_end;
 135
 136 static void update_bounds(const void *new)
 137 {
 138         if (unlikely(!bounds_start))
 139                 bounds_start = bounds_end = new;
 140         else if (new < bounds_start)
 141                 bounds_start = new;
 142         else if (new > bounds_end)
 143                 bounds_end = new;
 144 }
 145
 146 static bool in_bounds(const void *p)
 147 {
 148         return !p || (p >= bounds_start && p <= bounds_end);
 149 }
 150 #else
 151 static void update_bounds(const void *new)
 152 {
 153 }
 154
 155 static bool in_bounds(const void *p)
 156 {
 157         return true;
 158 }
 159 #endif
 160
 161 static void check_bounds(const void *p)
 162 {
 163         if (!in_bounds(p))
 164                 call_error("Not a valid header");
 165 }
 166
 167 static struct tal_hdr *to_tal_hdr(const void *ctx)
 168 {
 169         struct tal_hdr *t;
 170
 171         t = (struct tal_hdr *)((char *)ctx - sizeof(struct tal_hdr));
 172         check_bounds(t);
 173         check_bounds(ignore_destroying_bit(t->next));
 174         return t;
 175 }
 176
 177 static struct tal_hdr *to_tal_hdr_or_null(const void *ctx)
 178 {
 179         if (!ctx)
 180                 return &null_parent.hdr;
 181         return to_tal_hdr(ctx);
 182 }
 183
 184 static void *from_tal_hdr(struct tal_hdr *hdr)
 185 {
 186         return hdr + 1;
 187 }
 188
 189 #ifdef TAL_DEBUG
 190 static void *from_tal_hdr_or_null(struct tal_hdr *hdr)
 191 {
 192         if (hdr == &null_parent.hdr)
 193                 return NULL;
 194         return from_tal_hdr(hdr);
 195 }
 196
 197 static struct tal_hdr *debug_tal(struct tal_hdr *tal)
 198 {
 199         tal_check(from_tal_hdr_or_null(tal), "TAL_DEBUG ");
 200         return tal;
 201 }
 202 #else
 203 static struct tal_hdr *debug_tal(struct tal_hdr *tal)
 204 {
 205         return tal;
 206 }
 207 #endif
 208
 209 static void *allocate(size_t size)
 210 {
 211         void *ret;
 212
 213         /* Don't hand silly sizes to malloc. */
 214         if (size >> (CHAR_BIT*sizeof(size) - 1)) {
 215                 call_error("allocation size overflow");
 216                 return NULL;
 217         }
 218
 219         ret = allocfn(size);
 220         if (!ret)
 221                 call_error("allocation failed");
 222         else
 223                 update_bounds(ret);
 224         return ret;
 225 }
 226
 227 /* We carefully start all real properties with a zero byte. */
 228 static bool is_literal(const struct prop_hdr *prop)
 229 {
 230         return ((char *)prop)[0] != 0;
 231 }
 232
 233 static struct prop_hdr **find_property_ptr(const struct tal_hdr *t,
 234                                            enum prop_type type)
 235 {
 236         struct prop_hdr **p;
 237
 238         for (p = (struct prop_hdr **)&t->prop; *p; p = &(*p)->next) {
 239                 if (is_literal(*p)) {
 240                         if (type == NAME)
 241                                 return p;
 242                         break;
 243                 }
 244                 if ((*p)->type == type)
 245                         return p;
 246         }
 247         return NULL;
 248 }
 249
 250 static void *find_property(const struct tal_hdr *parent, enum prop_type type)
 251 {
 252         struct prop_hdr **p = find_property_ptr(parent, type);
 253
 254         if (p)
 255                 return *p;
 256         return NULL;
 257 }
 258
 259 static void init_property(struct prop_hdr *hdr,
 260                           struct tal_hdr *parent,
 261                           enum prop_type type)
 262 {
 263         hdr->type = type;
 264         hdr->next = parent->prop;
 265         parent->prop = hdr;
 266 }
 267
 268 static struct destructor *add_destructor_property(struct tal_hdr *t,
 269                                                   void (*destroy)(void *))
 270 {
 271         struct destructor *prop = allocate(sizeof(*prop));
 272         if (prop) {
 273                 init_property(&prop->hdr, t, DESTRUCTOR);
 274                 prop->destroy = destroy;
 275         }
 276         return prop;
 277 }
 278
 279 static struct name *add_name_property(struct tal_hdr *t, const char *name)
 280 {
 281         struct name *prop;
 282
 283         prop = allocate(sizeof(*prop) + strlen(name) + 1);
 284         if (prop) {
 285                 init_property(&prop->hdr, t, NAME);
 286                 strcpy(prop->name, name);
 287         }
 288         return prop;
 289 }
 290
 291 static void init_group_property(struct group *group,
 292                                 struct children *parent_child,
 293                                 struct tal_hdr *child)
 294 {
 295         init_property(&group->hdr, child, GROUP);
 296         group->parent_child = parent_child;
 297         group->first_child = child;
 298 }
 299
 300 static struct children *add_child_property(struct tal_hdr *parent,
 301                                            struct tal_hdr *child)
 302 {
 303         struct children *prop = allocate(sizeof(*prop));
 304         if (prop) {
 305                 init_property(&prop->hdr, parent, CHILDREN);
 306                 prop->parent = parent;
 307
 308                 init_group_property(&prop->group, prop, child);
 309                 list_head_init(&prop->group.list);
 310                 update_bounds(&prop->group);
 311         }
 312         return prop;
 313 }
 314
 315 static struct group *add_group_property(struct tal_hdr *child,
 316                                         struct children *parent_child)
 317 {
 318         struct group *prop = allocate(sizeof(*prop));
 319         if (prop)
 320                 init_group_property(prop, parent_child, child);
 321         return prop;
 322 }
 323
 324 static bool add_child(struct tal_hdr *parent, struct tal_hdr *child)
 325 {
 326         struct group *group;
 327         struct children *children = find_property(parent, CHILDREN);
 328
 329         if (!children) {
 330                 children = add_child_property(parent, child);
 331                 if (!children)
 332                         return false;
 333                 list_head_init(&children->group.list);
 334
 335                 /* Child links to itself. */
 336                 child->next = child;
 337                 return true;
 338         }
 339
 340         /* Last one (may be children->group itself). */
 341         group = next_group(&children->group);
 342
 343         /* Empty group can happen: null_parent, or all children freed. */
 344         if (unlikely(!group->first_child)) {
 345                 assert(group == &children->group);
 346                 /* This hits on first child appended to null parent. */
 347                 if (unlikely(!initialized)) {
 348                         atexit(tal_cleanup);
 349                         take_allocfail(take_alloc_failed);
 350                         initialized = true;
 351                 }
 352                 /* Link group into this child, make it the first one. */
 353                 group->hdr.next = child->prop;
 354                 child->prop = &group->hdr;
 355                 group->first_child = child;
 356
 357                 /* Child links to itself. */
 358                 child->next = child;
 359                 return true;
 360         }
 361
 362         if (unlikely(hash_pointer(child, 0) % GROUP_NODE_AVERAGE == 0)) {
 363                 struct group *newgroup;
 364
 365                 newgroup = add_group_property(child, children);
 366                 if (likely(newgroup)) {
 367                         list_add(&children->group.list, &newgroup->list.n);
 368
 369                         /* Child links to itself. */
 370                         child->next = child;
 371                         return true;
 372                 }
 373                 /* Fall through: on allocation failure reuse old group. */
 374         }
 375
 376         /* We insert after head, otherwise we'd need to find end. */
 377         child->next = group->first_child->next;
 378         group->first_child->next = child;
 379         return true;
 380 }
 381
 382 static void del_tree(struct tal_hdr *t)
 383 {
 384         struct prop_hdr **prop, *p, *next;
 385
 386         /* Already being destroyed?  Don't loop. */
 387         if (unlikely(get_destroying_bit(t->next)))
 388                 return;
 389
 390         set_destroying_bit(&t->next);
 391
 392         /* Carefully call destructors, removing as we go. */
 393         while ((prop = find_property_ptr(t, DESTRUCTOR))) {
 394                 struct destructor *d = (struct destructor *)*prop;
 395                 d->destroy(from_tal_hdr(t));
 396                 *prop = d->hdr.next;
 397                 freefn(d);
 398         }
 399
 400         /* Now free children and groups. */
 401         prop = find_property_ptr(t, CHILDREN);
 402         if (prop) {
 403                 struct children *c = (struct children *)*prop;
 404                 struct group *group, *next;
 405
 406                 group = &c->group;
 407                 do {
 408                         next = next_group(group);
 409                         if (group->first_child) {
 410                                 struct tal_hdr *i, *nextc;
 411
 412                                 i = group->first_child;
 413                                 do {
 414                                         nextc = i->next;
 415                                         del_tree(i);
 416                                         i = nextc;
 417                                 } while (i != group->first_child);
 418                         }
 419                         if (group != &c->group)
 420                                 freefn(group);
 421                         group = next;
 422                 } while (group != &c->group);
 423         }
 424
 425         /* Finally free our properties (groups are freed by parent). */
 426         for (p = t->prop; p && !is_literal(p); p = next) {
 427                 next = p->next;
 428                 if (p->type != GROUP)
 429                         freefn(p);
 430         }
 431         freefn(t);
 432 }
 433
 434 void *tal_alloc_(const tal_t *ctx, size_t size, bool clear, const char *label)
 435 {
 436         struct tal_hdr *child, *parent = debug_tal(to_tal_hdr_or_null(ctx));
 437
 438         child = allocate(sizeof(struct tal_hdr) + size);
 439         if (!child)
 440                 return NULL;
 441         if (clear)
 442                 memset(from_tal_hdr(child), 0, size);
 443         child->prop = (void *)label;
 444         if (!add_child(parent, child)) {
 445                 freefn(child);
 446                 return NULL;
 447         }
 448         debug_tal(parent);
 449         return from_tal_hdr(debug_tal(child));
 450 }
 451
 452 /* Update back ptrs, etc, as required.
 453  * May return pointer to parent. */
 454 static struct tal_hdr *remove_node(struct tal_hdr *t)
 455 {
 456         struct prop_hdr **prop;
 457         struct tal_hdr *prev;
 458
 459         /* Loop around to find previous node. */
 460         for (prev = t->next; prev->next != t; prev = prev->next);
 461
 462         /* Unlink ourselves. */
 463         prev->next = t->next;
 464
 465         /* Are we the node with the group property? */
 466         prop = find_property_ptr(t, GROUP);
 467         if (prop) {
 468                 struct group *group = (struct group *)*prop;
 469
 470                 /* Are we the only one? */
 471                 if (prev == t) {
 472                         struct prop_hdr *next = (*prop)->next;
 473                         struct children *c = group->parent_child;
 474                         /* Is this the group embedded in the child property? */
 475                         if (group == &c->group) {
 476                                 group->first_child = NULL;
 477                         } else {
 478                                 /* Empty group, so free it. */
 479                                 list_del_from(&c->group.list, &group->list.n);
 480                                 freefn(group);
 481                         }
 482                         *prop = next;
 483                         return c->parent;
 484                 } else {
 485                         /* Move property to next node. */
 486                         group->first_child = t->next;
 487
 488                         *prop = group->hdr.next;
 489                         group->hdr.next = t->next->prop;
 490                         t->next->prop = &group->hdr;
 491                 }
 492         }
 493         return NULL;
 494 }
 495
 496 void *tal_free(const tal_t *ctx)
 497 {
 498         if (ctx) {
 499                 struct tal_hdr *t;
 500                 int saved_errno = errno;
 501                 t = debug_tal(to_tal_hdr(ctx));
 502                 remove_node(t);
 503                 del_tree(t);
 504                 errno = saved_errno;
 505         }
 506         return NULL;
 507 }
 508
 509 void *tal_steal_(const tal_t *new_parent, const tal_t *ctx)
 510 {
 511         if (ctx) {
 512                 struct tal_hdr *newpar, *t, *old_next, *old_parent;
 513
 514                 newpar = debug_tal(to_tal_hdr_or_null(new_parent));
 515                 t = debug_tal(to_tal_hdr(ctx));
 516
 517                 /* Save enough data to get us back if we fail! */
 518                 old_next = t->next;
 519
 520                 /* Unlink it from old parent. */
 521                 old_parent = remove_node(t);
 522                 if (unlikely(!add_child(newpar, t))) {
 523                         /* If we were last child, parent returned by
 524                          * remove_node, otherwise search old siblings
 525                          * for it. */
 526                         if (!old_parent) {
 527                                 struct group *g;
 528                                 while (!(g = find_property(old_next, GROUP)))
 529                                         old_next = old_next->next;
 530                                 old_parent = g->parent_child->parent;
 531                         }
 532                         /* We can always add to old parent, becuase it has one
 533                          * group already. */
 534                         if (!add_child(old_parent, t))
 535                                 abort();
 536                         return NULL;
 537                 }
 538                 debug_tal(newpar);
 539         }
 540         return (void *)ctx;
 541 }
 542
 543 bool tal_add_destructor_(tal_t *ctx, void (*destroy)(void *me))
 544 {
 545         return add_destructor_property(debug_tal(to_tal_hdr(ctx)), destroy);
 546 }
 547
 548 bool tal_set_name_(tal_t *ctx, const char *name, bool literal)
 549 {
 550         struct tal_hdr *t = debug_tal(to_tal_hdr(ctx));
 551         struct prop_hdr **prop = find_property_ptr(t, NAME);
 552
 553         /* Get rid of any old name */
 554         if (prop) {
 555                 struct name *name = (struct name *)*prop;
 556                 if (is_literal(&name->hdr))
 557                         *prop = NULL;
 558                 else {
 559                         *prop = name->hdr.next;
 560                         freefn(name);
 561                 }
 562         }
 563
 564         if (literal && name[0]) {
 565                 struct prop_hdr **p;
 566
 567                 /* Append literal. */
 568                 for (p = &t->prop; *p && !is_literal(*p); p = &(*p)->next);
 569                 *p = (struct prop_hdr *)name;
 570                 return true;
 571         }
 572         if (!add_name_property(t, name))
 573                 return false;
 574         debug_tal(t);
 575         return true;
 576 }
 577
 578 const char *tal_name(const tal_t *t)
 579 {
 580         struct name *n;
 581
 582         n = find_property(debug_tal(to_tal_hdr(t)), NAME);
 583         if (!n)
 584                 return NULL;
 585
 586         if (is_literal(&n->hdr))
 587                 return (const char *)n;
 588         return n->name;
 589 }
 590
 591 /* Start one past first child: make stopping natural in circ. list. */
 592 static struct tal_hdr *first_child(struct tal_hdr *parent)
 593 {
 594         struct children *child;
 595         struct group *group;
 596
 597         child = find_property(parent, CHILDREN);
 598         if (!child)
 599                 return NULL;
 600
 601         /* Careful of empty group embedded in child property. */
 602         if (child->group.first_child)
 603                 return child->group.first_child->next;
 604
 605         /* There could still be another group! */
 606         group = next_group(&child->group);
 607         if (group == &child->group)
 608                 return NULL;
 609
 610         return group->first_child->next;
 611 }
 612
 613 tal_t *tal_first(const tal_t *root)
 614 {
 615         struct tal_hdr *c, *t = debug_tal(to_tal_hdr_or_null(root));
 616
 617         c = first_child(t);
 618         if (!c)
 619                 return NULL;
 620         return from_tal_hdr(c);
 621 }
 622
 623 tal_t *tal_next(const tal_t *root, const tal_t *prev)
 624 {
 625         struct tal_hdr *c, *t = debug_tal(to_tal_hdr(prev)), *top;
 626         struct group *group;
 627
 628         /* Children? */
 629         c = first_child(t);
 630         if (c)
 631                 return from_tal_hdr(c);
 632
 633         top = to_tal_hdr_or_null(root);
 634         do {
 635                 struct group *next;
 636
 637                 /* Are we back to first child in group? */
 638                 group = find_property(t, GROUP);
 639                 if (!group)
 640                         return from_tal_hdr(t->next);
 641
 642                 /* Last group is one inside children property. */
 643                 next = next_group(group);
 644                 if (next != &group->parent_child->group)
 645                         return from_tal_hdr(next->first_child->next);
 646
 647                 /* OK, go back to parent. */
 648                 t = group->parent_child->parent;
 649         } while (t != top);
 650
 651         return NULL;
 652 }
 653
 654 tal_t *tal_parent(const tal_t *ctx)
 655 {
 656         struct group *group;
 657         struct tal_hdr *t;
 658
 659         if (!ctx)
 660                 return NULL;
 661
 662         t = debug_tal(to_tal_hdr(ctx));
 663
 664         while (!(group = find_property(t, GROUP)))
 665                 t = t->next;
 666
 667         if (group->parent_child->parent == &null_parent.hdr)
 668                 return NULL;
 669         return from_tal_hdr(group->parent_child->parent);
 670 }
 671
 672 bool tal_resize_(tal_t **ctxp, size_t size)
 673 {
 674         struct tal_hdr *old_t, *t, **prev;
 675         struct group *group;
 676         struct children *child;
 677
 678         old_t = debug_tal(to_tal_hdr(*ctxp));
 679
 680         /* Don't hand silly sizes to realloc. */
 681         if (size >> (CHAR_BIT*sizeof(size) - 1)) {
 682                 call_error("Reallocation size overflow");
 683                 return false;
 684         }
 685
 686         t = resizefn(old_t, size + sizeof(struct tal_hdr));
 687         if (!t) {
 688                 call_error("Reallocation failure");
 689                 return false;
 690         }
 691
 692         /* If it didn't move, we're done! */
 693         if (t == old_t)
 694                 return true;
 695         update_bounds(t);
 696
 697         /* Fix up linked list pointer. */
 698         for (prev = &t->next; *prev != old_t; prev = &(*prev)->next);
 699         *prev = t;
 700
 701         /* Fix up group pointer, if any. */
 702         group = find_property(t, GROUP);
 703         if (group) {
 704                 assert(group->first_child == old_t);
 705                 group->first_child = t;
 706         }
 707
 708         /* Fix up child propertie's parent pointer. */
 709         child = find_property(t, CHILDREN);
 710         if (child) {
 711                 assert(child->parent == old_t);
 712                 child->parent = t;
 713         }
 714         *ctxp = from_tal_hdr(debug_tal(t));
 715         return true;
 716 }
 717
 718 char *tal_strdup(const tal_t *ctx, const char *p)
 719 {
 720         /* We have to let through NULL for take(). */
 721         return tal_dup(ctx, char, p, p ? strlen(p) + 1: 1, 0);
 722 }
 723
 724 char *tal_strndup(const tal_t *ctx, const char *p, size_t n)
 725 {
 726         size_t len;
 727         char *ret;
 728
 729         /* We have to let through NULL for take(). */
 730         if (likely(p)) {
 731                 len = strlen(p);
 732                 if (len > n)
 733                         len = n;
 734         } else
 735                 len = n;
 736
 737         ret = tal_dup(ctx, char, p, len, 1);
 738         if (ret)
 739                 ret[len] = '\0';
 740         return ret;
 741 }
 742
 743 void *tal_dup_(const tal_t *ctx, const void *p, size_t n, size_t extra,
 744                const char *label)
 745 {
 746         void *ret;
 747
 748         /* Beware overflow! */
 749         if (n + extra < n || n + extra + sizeof(struct tal_hdr) < n) {
 750                 call_error("dup size overflow");
 751                 if (taken(p))
 752                         tal_free(p);
 753                 return NULL;
 754         }
 755
 756         if (taken(p)) {
 757                 if (unlikely(!p))
 758                         return NULL;
 759                 if (unlikely(!tal_resize_((void **)&p, n + extra)))
 760                         return tal_free(p);
 761                 if (unlikely(!tal_steal(ctx, p)))
 762                         return tal_free(p);
 763                 return (void *)p;
 764         }
 765         ret = tal_alloc_(ctx, n + extra, false, label);
 766         if (ret)
 767                 memcpy(ret, p, n);
 768         return ret;
 769 }
 770
 771 char *tal_asprintf(const tal_t *ctx, const char *fmt, ...)
 772 {
 773         va_list ap;
 774         char *ret;
 775
 776         va_start(ap, fmt);
 777         ret = tal_vasprintf(ctx, fmt, ap);
 778         va_end(ap);
 779
 780         return ret;
 781 }
 782
 783 char *tal_vasprintf(const tal_t *ctx, const char *fmt, va_list ap)
 784 {
 785         size_t max;
 786         char *buf;
 787         int ret;
 788
 789         if (!fmt && taken(fmt))
 790                 return NULL;
 791
 792         /* A decent guess to start. */
 793         max = strlen(fmt) * 2;
 794         buf = tal_arr(ctx, char, max);
 795         while (buf) {
 796                 va_list ap2;
 797
 798                 va_copy(ap2, ap);
 799                 ret = vsnprintf(buf, max, fmt, ap2);
 800                 va_end(ap2);
 801
 802                 if (ret < max)
 803                         break;
 804                 if (!tal_resize(&buf, max *= 2))
 805                         buf = tal_free(buf);
 806         }
 807         if (taken(fmt))
 808                 tal_free(fmt);
 809         return buf;
 810 }
 811
 812 void tal_set_backend(void *(*alloc_fn)(size_t size),
 813                      void *(*resize_fn)(void *, size_t size),
 814                      void (*free_fn)(void *),
 815                      void (*error_fn)(const char *msg))
 816 {
 817         if (alloc_fn)
 818                 allocfn = alloc_fn;
 819         if (resize_fn)
 820                 resizefn = resize_fn;
 821         if (free_fn)
 822                 freefn = free_fn;
 823         if (error_fn)
 824                 errorfn = error_fn;
 825 }
 826
 827 #ifdef CCAN_TAL_DEBUG
 828 static void dump_node(unsigned int indent, const struct tal_hdr *t)
 829 {
 830         unsigned int i;
 831         const struct prop_hdr *p;
 832
 833         for (i = 0; i < indent; i++)
 834                 printf("  ");
 835         printf("%p", t);
 836         for (p = t->prop; p; p = p->next) {
 837                 struct group *g;
 838                 struct children *c;
 839                 struct destructor *d;
 840                 struct name *n;
 841                 if (is_literal(p)) {
 842                         printf(" \"%s\"", (const char *)p);
 843                         break;
 844                 }
 845                 switch (p->type) {
 846                 case CHILDREN:
 847                         c = (struct children *)p;
 848                         printf(" CHILDREN(%p):parent=%p,group=%p\n",
 849                                p, c->parent, &c->group);
 850                         g = &c->group;
 851                         printf("  GROUP(%p):list={%p,%p},parent_ch=%p,first=%p",
 852                                g, g->list.n.next, g->list.n.next,
 853                                g->parent_child, g->first_child);
 854                         break;
 855                 case GROUP:
 856                         g = (struct group *)p;
 857                         printf(" GROUP(%p):list={%p,%p},,parent_ch=%p,first=%p",
 858                                p, g->list.n.next, g->list.n.next,
 859                                g->parent_child, g->first_child);
 860                         break;
 861                 case DESTRUCTOR:
 862                         d = (struct destructor *)p;
 863                         printf(" DESTRUCTOR(%p):fn=%p", p, d->destroy);
 864                         break;
 865                 case NAME:
 866                         n = (struct name *)p;
 867                         printf(" NAME(%p):%s", p, n->name);
 868                         break;
 869                 default:
 870                         printf(" **UNKNOWN(%p):%i**", p, p->type);
 871                 }
 872         }
 873         printf("\n");
 874 }
 875
 876 static void tal_dump_(unsigned int level, const struct tal_hdr *t)
 877 {
 878         struct children *children;
 879         struct group *group;
 880
 881         dump_node(level, t);
 882
 883         children = find_property(t, CHILDREN);
 884         if (!children)
 885                 return;
 886
 887         group = &children->group;
 888         do {
 889                 struct tal_hdr *i;
 890
 891                 i = group->first_child;
 892                 if (i) {
 893                         do {
 894                                 tal_dump_(level+1, i);
 895                                 i = i->next;
 896                         } while (i != group->first_child);
 897                 }
 898                 group = next_group(group);
 899         } while (group != &children->group);
 900 }
 901
 902 void tal_dump(void)
 903 {
 904         tal_dump_(0, &null_parent.hdr);
 905 }
 906 #endif /* CCAN_TAL_DEBUG */
 907
 908 #ifndef NDEBUG
 909 static bool check_err(struct tal_hdr *t, const char *errorstr,
 910                       const char *errmsg)
 911 {
 912         if (errorstr) {
 913                 /* Try not to malloc: it may be corrupted. */
 914                 char msg[strlen(errorstr) + 20 + strlen(errmsg) + 1];
 915                 sprintf(msg, "%s:%p %s", errorstr, from_tal_hdr(t), errmsg);
 916                 call_error(msg);
 917         }
 918         return false;
 919 }
 920
 921 static bool check_group(struct group *group,
 922                         struct tal_hdr *t, const char *errorstr);
 923
 924 static bool check_node(struct group *group,
 925                        struct tal_hdr *t, const char *errorstr)
 926 {
 927         struct prop_hdr *p;
 928         struct name *name = NULL;
 929         struct children *children = NULL;
 930         struct group *gr = NULL;
 931
 932         if (t != &null_parent.hdr && !in_bounds(t))
 933                 return check_err(t, errorstr, "invalid pointer");
 934
 935         for (p = t->prop; p; p = p->next) {
 936                 if (is_literal(p)) {
 937                         if (name)
 938                                 return check_err(t, errorstr,
 939                                                  "has extra literal");
 940                         name = (struct name *)p;
 941                         break;
 942                 }
 943                 if (p != &null_parent.c.hdr && p != &null_parent.c.group.hdr
 944                     && !in_bounds(p))
 945                         return check_err(t, errorstr,
 946                                          "has bad property pointer");
 947
 948                 switch (p->type) {
 949                 case GROUP:
 950                         if (gr)
 951                                 return check_err(t, errorstr,
 952                                                  "has two groups");
 953                         gr = (struct group *)p;
 954                         break;
 955                 case CHILDREN:
 956                         if (children)
 957                                 return check_err(t, errorstr,
 958                                                  "has two child nodes");
 959                         children = (struct children *)p;
 960                         break;
 961                 case DESTRUCTOR:
 962                         break;
 963                 case NAME:
 964                         if (name)
 965                                 return check_err(t, errorstr,
 966                                                  "has two names");
 967                         name = (struct name *)p;
 968                         break;
 969                 default:
 970                         return check_err(t, errorstr, "has unknown property");
 971                 }
 972         }
 973         if (group && gr != group)
 974                 return check_err(t, errorstr, "has bad group");
 975
 976         if (children) {
 977                 if (!list_check(&children->group.list, errorstr))
 978                         return false;
 979                 gr = &children->group;
 980                 do {
 981                         if (gr->first_child) {
 982                                 if (!check_group(gr, gr->first_child, errorstr))
 983                                         return false;
 984                         } else if (gr != &children->group) {
 985                                 /* Empty groups should be deleted! */
 986                                 return check_err(t, errorstr,
 987                                                  "has empty group");
 988                         }
 989                         gr = next_group(gr);
 990                 } while (gr != &children->group);
 991         }
 992         return true;
 993 }
 994
 995 static bool check_group(struct group *group,
 996                         struct tal_hdr *t, const char *errorstr)
 997 {
 998         struct tal_hdr *i;
 999
1000         i = t;
1001         do {
1002                 if (!check_node(group, i, errorstr))
1003                         return false;
1004                 group = NULL;
1005                 i = i->next;
1006         } while (i != t);
1007         return true;
1008 }
1009
1010 bool tal_check(const tal_t *ctx, const char *errorstr)
1011 {
1012         struct tal_hdr *t = to_tal_hdr_or_null(ctx);
1013
1014         return check_node(NULL, t, errorstr);
1015 }
1016 #else /* NDEBUG */
1017 bool tal_check(const tal_t *ctx, const char *errorstr)
1018 {
1019         return true;
1020 }
1021 #endif