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