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                 list_head_init(&children->group.list);
 321
 322                 /* Child links to itself. */
 323                 child->next = child;
 324                 return true;
 325         }
 326
 327         /* Last one (may be children->group itself). */
 328         group = next_group(&children->group);
 329
 330         /* Empty group can happen: null_parent, or all children freed. */
 331         if (unlikely(!group->first_child)) {
 332                 assert(group == &children->group);
 333                 /* This hits on first child appended to null parent. */
 334                 if (unlikely(!atexit_set)) {
 335                         atexit(unlink_null);
 336                         atexit_set = true;
 337                 }
 338                 /* Link group into this child, make it the first one. */
 339                 group->hdr.next = child->prop;
 340                 child->prop = &group->hdr;
 341                 group->first_child = child;
 342
 343                 /* Child links to itself. */
 344                 child->next = child;
 345                 return true;
 346         }
 347
 348         if (unlikely(hash_pointer(child, 0) % GROUP_NODE_AVERAGE == 0)) {
 349                 struct group *newgroup;
 350
 351                 newgroup = add_group_property(child, children);
 352                 if (likely(newgroup)) {
 353                         list_add(&children->group.list, &newgroup->list.n);
 354
 355                         /* Child links to itself. */
 356                         child->next = child;
 357                         return true;
 358                 }
 359                 /* Fall through: on allocation failure reuse old group. */
 360         }
 361
 362         /* We insert after head, otherwise we'd need to find end. */
 363         child->next = group->first_child->next;
 364         group->first_child->next = child;
 365         return true;
 366 }
 367
 368 static void del_tree(struct tal_hdr *t)
 369 {
 370         struct prop_hdr **prop, *p, *next;
 371
 372         /* Already being destroyed?  Don't loop. */
 373         if (unlikely(get_destroying_bit(t->next)))
 374                 return;
 375
 376         set_destroying_bit(&t->next);
 377
 378         /* Carefully call destructors, removing as we go. */
 379         while ((prop = find_property_ptr(t, DESTRUCTOR))) {
 380                 struct destructor *d = (struct destructor *)*prop;
 381                 d->destroy(from_tal_hdr(t));
 382                 *prop = d->hdr.next;
 383                 freefn(d);
 384         }
 385
 386         /* Now free children and groups. */
 387         prop = find_property_ptr(t, CHILDREN);
 388         if (prop) {
 389                 struct children *c = (struct children *)*prop;
 390                 struct group *group, *next;
 391
 392                 group = &c->group;
 393                 do {
 394                         next = next_group(group);
 395                         if (group->first_child) {
 396                                 struct tal_hdr *i, *nextc;
 397
 398                                 i = group->first_child;
 399                                 do {
 400                                         nextc = i->next;
 401                                         del_tree(i);
 402                                         i = nextc;
 403                                 } while (i != group->first_child);
 404                         }
 405                         if (group != &c->group)
 406                                 freefn(group);
 407                         group = next;
 408                 } while (group != &c->group);
 409         }
 410
 411         /* Finally free our properties (groups are freed by parent). */
 412         for (p = t->prop; p && !is_literal(p); p = next) {
 413                 next = p->next;
 414                 if (p->type != GROUP)
 415                         freefn(p);
 416         }
 417         freefn(t);
 418 }
 419
 420 void *tal_alloc_(const tal_t *ctx, size_t size, bool clear, const char *label)
 421 {
 422         struct tal_hdr *child, *parent = debug_tal(to_tal_hdr_or_null(ctx));
 423
 424         child = allocate(sizeof(struct tal_hdr) + size);
 425         if (!child)
 426                 return NULL;
 427         if (clear)
 428                 memset(from_tal_hdr(child), 0, size);
 429         child->prop = (void *)label;
 430         if (!add_child(parent, child)) {
 431                 freefn(child);
 432                 return NULL;
 433         }
 434         debug_tal(parent);
 435         return from_tal_hdr(debug_tal(child));
 436 }
 437
 438 /* Update back ptrs, etc, as required.
 439  * May return pointer to parent. */
 440 static struct tal_hdr *remove_node(struct tal_hdr *t)
 441 {
 442         struct prop_hdr **prop;
 443         struct tal_hdr *prev;
 444
 445         /* Loop around to find previous node. */
 446         for (prev = t->next; prev->next != t; prev = prev->next);
 447
 448         /* Unlink ourselves. */
 449         prev->next = t->next;
 450
 451         /* Are we the node with the group property? */
 452         prop = find_property_ptr(t, GROUP);
 453         if (prop) {
 454                 struct group *group = (struct group *)*prop;
 455
 456                 /* Are we the only one? */
 457                 if (prev == t) {
 458                         struct children *c = group->parent_child;
 459                         /* Is this the group embedded in the child property? */
 460                         if (group == &c->group) {
 461                                 group->first_child = NULL;
 462                         } else {
 463                                 /* Empty group, so free it. */
 464                                 list_del_from(&c->group.list, &group->list.n);
 465                                 *prop = group->hdr.next;
 466                                 freefn(group);
 467                         }
 468                         return c->parent;
 469                 } else {
 470                         /* Move property to next node. */
 471                         group->first_child = t->next;
 472
 473                         *prop = group->hdr.next;
 474                         group->hdr.next = t->next->prop;
 475                         t->next->prop = &group->hdr;
 476                 }
 477         }
 478         return NULL;
 479 }
 480
 481 void tal_free(const tal_t *ctx)
 482 {
 483         struct tal_hdr *t;
 484
 485         if (!ctx)
 486                 return;
 487
 488         t = debug_tal(to_tal_hdr(ctx));
 489         remove_node(t);
 490         del_tree(t);
 491 }
 492
 493 void *tal_steal_(const tal_t *new_parent, const tal_t *ctx)
 494 {
 495         if (ctx) {
 496                 struct tal_hdr *newpar, *t, *old_next, *old_parent;
 497
 498                 newpar = debug_tal(to_tal_hdr_or_null(new_parent));
 499                 t = debug_tal(to_tal_hdr(ctx));
 500
 501                 /* Save enough data to get us back if we fail! */
 502                 old_next = t->next;
 503
 504                 /* Unlink it from old parent. */
 505                 old_parent = remove_node(t);
 506                 if (unlikely(!add_child(newpar, t))) {
 507                         /* If we were last child, parent returned by
 508                          * remove_node, otherwise search old siblings
 509                          * for it. */
 510                         if (!old_parent) {
 511                                 struct group *g;
 512                                 while (!(g = find_property(old_next, GROUP)))
 513                                         old_next = old_next->next;
 514                                 old_parent = g->parent_child->parent;
 515                         }
 516                         /* We can always add to old parent, becuase it has one
 517                          * group already. */
 518                         if (!add_child(old_parent, t))
 519                                 abort();
 520                         return NULL;
 521                 }
 522                 debug_tal(newpar);
 523         }
 524         return (void *)ctx;
 525 }
 526
 527 bool tal_add_destructor_(tal_t *ctx, void (*destroy)(void *me))
 528 {
 529         return add_destructor_property(debug_tal(to_tal_hdr(ctx)), destroy);
 530 }
 531
 532 bool tal_set_name_(tal_t *ctx, const char *name, bool literal)
 533 {
 534         struct tal_hdr *t = debug_tal(to_tal_hdr(ctx));
 535         struct prop_hdr **prop = find_property_ptr(t, NAME);
 536
 537         /* Get rid of any old name */
 538         if (prop) {
 539                 struct name *name = (struct name *)*prop;
 540                 if (is_literal(&name->hdr))
 541                         *prop = NULL;
 542                 else {
 543                         *prop = name->hdr.next;
 544                         freefn(name);
 545                 }
 546         }
 547
 548         if (literal && name[0]) {
 549                 struct prop_hdr **p;
 550
 551                 /* Append literal. */
 552                 for (p = &t->prop; *p && !is_literal(*p); p = &(*p)->next);
 553                 *p = (struct prop_hdr *)name;
 554                 return true;
 555         }
 556         if (!add_name_property(t, name))
 557                 return false;
 558         debug_tal(t);
 559         return true;
 560 }
 561
 562 const char *tal_name(const tal_t *t)
 563 {
 564         struct name *n;
 565
 566         n = find_property(debug_tal(to_tal_hdr(t)), NAME);
 567         if (!n)
 568                 return NULL;
 569
 570         if (is_literal(&n->hdr))
 571                 return (const char *)n;
 572         return n->name;
 573 }
 574
 575 /* Start one past first child: make stopping natural in circ. list. */
 576 static struct tal_hdr *first_child(struct tal_hdr *parent)
 577 {
 578         struct children *child;
 579         struct group *group;
 580
 581         child = find_property(parent, CHILDREN);
 582         if (!child)
 583                 return NULL;
 584
 585         /* Careful of empty group embedded in child property. */
 586         if (child->group.first_child)
 587                 return child->group.first_child->next;
 588
 589         /* There could still be another group! */
 590         group = next_group(&child->group);
 591         if (group == &child->group)
 592                 return NULL;
 593
 594         return group->first_child->next;
 595 }
 596
 597 tal_t *tal_first(const tal_t *root)
 598 {
 599         struct tal_hdr *c, *t = debug_tal(to_tal_hdr_or_null(root));
 600
 601         c = first_child(t);
 602         if (!c)
 603                 return NULL;
 604         return from_tal_hdr(c);
 605 }
 606
 607 tal_t *tal_next(const tal_t *root, const tal_t *prev)
 608 {
 609         struct tal_hdr *c, *t = debug_tal(to_tal_hdr(prev)), *top;
 610         struct group *group;
 611
 612         /* Children? */
 613         c = first_child(t);
 614         if (c)
 615                 return from_tal_hdr(c);
 616
 617         top = to_tal_hdr_or_null(root);
 618         do {
 619                 struct group *next;
 620
 621                 /* Are we back to first child in group? */
 622                 group = find_property(t, GROUP);
 623                 if (!group)
 624                         return from_tal_hdr(t->next);
 625
 626                 /* Last group is one inside children property. */
 627                 next = next_group(group);
 628                 if (next != &group->parent_child->group)
 629                         return from_tal_hdr(next->first_child->next);
 630
 631                 /* OK, go back to parent. */
 632                 t = group->parent_child->parent;
 633         } while (t != top);
 634
 635         return NULL;
 636 }
 637
 638 tal_t *tal_parent(const tal_t *ctx)
 639 {
 640         struct group *group;
 641         struct tal_hdr *t;
 642
 643         if (!ctx)
 644                 return NULL;
 645
 646         t = debug_tal(to_tal_hdr(ctx));
 647
 648         while (!(group = find_property(t, GROUP)))
 649                 t = t->next;
 650
 651         if (group->parent_child->parent == &null_parent.hdr)
 652                 return NULL;
 653         return from_tal_hdr(group->parent_child->parent);
 654 }
 655
 656 void *tal_realloc_(tal_t *ctx, size_t size)
 657 {
 658         struct tal_hdr *old_t, *t, **prev;
 659         struct group *group;
 660         struct children *child;
 661
 662         old_t = debug_tal(to_tal_hdr(ctx));
 663
 664         t = resizefn(old_t, size + sizeof(struct tal_hdr));
 665         if (!t) {
 666                 call_error("Reallocation failure");
 667                 tal_free(old_t);
 668                 return NULL;
 669         }
 670         if (t == old_t)
 671                 return ctx;
 672         update_bounds(t);
 673
 674         /* Fix up linked list pointer. */
 675         for (prev = &t->next; *prev != old_t; prev = &(*prev)->next);
 676         *prev = t;
 677
 678         /* Fix up group pointer, if any. */
 679         group = find_property(t, GROUP);
 680         if (group) {
 681                 assert(group->first_child == old_t);
 682                 group->first_child = t;
 683         }
 684
 685         /* Fix up child propertie's parent pointer. */
 686         child = find_property(t, CHILDREN);
 687         if (child) {
 688                 assert(child->parent == old_t);
 689                 child->parent = t;
 690         }
 691
 692         return from_tal_hdr(debug_tal(t));
 693 }
 694
 695 char *tal_strdup(const tal_t *ctx, const char *p)
 696 {
 697         return tal_memdup(ctx, p, strlen(p)+1);
 698 }
 699
 700 char *tal_strndup(const tal_t *ctx, const char *p, size_t n)
 701 {
 702         char *ret;
 703
 704         if (strlen(p) < n)
 705                 n = strlen(p);
 706         ret = tal_memdup(ctx, p, n+1);
 707         if (ret)
 708                 ret[n] = '\0';
 709         return ret;
 710 }
 711
 712 void *tal_memdup(const tal_t *ctx, const void *p, size_t n)
 713 {
 714         void *ret;
 715
 716         if (ctx == TAL_TAKE)
 717                 return (void *)p;
 718
 719         ret = tal_arr(ctx, char, n);
 720         if (ret)
 721                 memcpy(ret, p, n);
 722         return ret;
 723 }
 724
 725 char *tal_asprintf(const tal_t *ctx, const char *fmt, ...)
 726 {
 727         va_list ap;
 728         char *ret;
 729
 730         va_start(ap, fmt);
 731         ret = tal_vasprintf(ctx, fmt, ap);
 732         va_end(ap);
 733
 734         return ret;
 735 }
 736
 737 char *tal_vasprintf(const tal_t *ctx, const char *fmt, va_list ap)
 738 {
 739         size_t max = strlen(fmt) * 2;
 740         char *buf;
 741         int ret;
 742
 743         if (ctx == TAL_TAKE)
 744                 buf = tal_arr(tal_parent(fmt), char, max);
 745         else
 746                 buf = tal_arr(ctx, char, max);
 747
 748         while (buf) {
 749                 va_list ap2;
 750
 751                 va_copy(ap2, ap);
 752                 ret = vsnprintf(buf, max, fmt, ap2);
 753                 va_end(ap2);
 754
 755                 if (ret < max)
 756                         break;
 757                 buf = tal_resize(buf, max *= 2);
 758         }
 759         if (ctx == TAL_TAKE)
 760                 tal_free(fmt);
 761         return buf;
 762 }
 763
 764 void tal_set_backend(void *(*alloc_fn)(size_t size),
 765                      void *(*resize_fn)(void *, size_t size),
 766                      void (*free_fn)(void *),
 767                      void (*error_fn)(const char *msg))
 768 {
 769         if (alloc_fn)
 770                 allocfn = alloc_fn;
 771         if (resize_fn)
 772                 resizefn = resize_fn;
 773         if (free_fn)
 774                 freefn = free_fn;
 775         if (error_fn)
 776                 errorfn = error_fn;
 777 }
 778
 779 #ifdef CCAN_TAL_DEBUG
 780 static void dump_node(unsigned int indent, const struct tal_hdr *t)
 781 {
 782         unsigned int i;
 783         const struct prop_hdr *p;
 784
 785         for (i = 0; i < indent; i++)
 786                 printf("  ");
 787         printf("%p", t);
 788         for (p = t->prop; p; p = p->next) {
 789                 struct group *g;
 790                 struct children *c;
 791                 struct destructor *d;
 792                 struct name *n;
 793                 if (is_literal(p)) {
 794                         printf(" \"%s\"", (const char *)p);
 795                         break;
 796                 }
 797                 switch (p->type) {
 798                 case CHILDREN:
 799                         c = (struct children *)p;
 800                         printf(" CHILDREN(%p):parent=%p,group=%p\n",
 801                                p, c->parent, &c->group);
 802                         g = &c->group;
 803                         printf("  GROUP(%p):list={%p,%p},parent_ch=%p,first=%p",
 804                                g, g->list.n.next, g->list.n.next,
 805                                g->parent_child, g->first_child);
 806                         break;
 807                 case GROUP:
 808                         g = (struct group *)p;
 809                         printf(" GROUP(%p):list={%p,%p},,parent_ch=%p,first=%p",
 810                                p, g->list.n.next, g->list.n.next,
 811                                g->parent_child, g->first_child);
 812                         break;
 813                 case DESTRUCTOR:
 814                         d = (struct destructor *)p;
 815                         printf(" DESTRUCTOR(%p):fn=%p", p, d->destroy);
 816                         break;
 817                 case NAME:
 818                         n = (struct name *)p;
 819                         printf(" NAME(%p):%s", p, n->name);
 820                         break;
 821                 default:
 822                         printf(" **UNKNOWN(%p):%i**", p, p->type);
 823                 }
 824         }
 825         printf("\n");
 826 }
 827
 828 static void tal_dump_(unsigned int level, const struct tal_hdr *t)
 829 {
 830         struct children *children;
 831         struct group *group;
 832
 833         dump_node(level, t);
 834
 835         children = find_property(t, CHILDREN);
 836         if (!children)
 837                 return;
 838
 839         group = &children->group;
 840         do {
 841                 struct tal_hdr *i;
 842
 843                 i = group->first_child;
 844                 if (i) {
 845                         do {
 846                                 tal_dump_(level+1, i);
 847                                 i = i->next;
 848                         } while (i != group->first_child);
 849                 }
 850                 group = next_group(group);
 851         } while (group != &children->group);
 852 }
 853
 854 void tal_dump(void)
 855 {
 856         tal_dump_(0, &null_parent.hdr);
 857 }
 858 #endif /* CCAN_TAL_DEBUG */
 859
 860 #ifndef NDEBUG
 861 static bool check_err(struct tal_hdr *t, const char *errorstr,
 862                       const char *errmsg)
 863 {
 864         if (errorstr) {
 865                 /* Try not to malloc: it may be corrupted. */
 866                 char msg[strlen(errorstr) + 20 + strlen(errmsg) + 1];
 867                 sprintf(msg, "%s:%p %s", errorstr, from_tal_hdr(t), errmsg);
 868                 call_error(msg);
 869         }
 870         return false;
 871 }
 872
 873 static bool check_group(struct group *group,
 874                         struct tal_hdr *t, const char *errorstr);
 875
 876 static bool check_node(struct group *group,
 877                        struct tal_hdr *t, const char *errorstr)
 878 {
 879         struct prop_hdr *p;
 880         struct name *name = NULL;
 881         struct children *children = NULL;
 882         struct group *gr = NULL;
 883
 884         if (t != &null_parent.hdr && !in_bounds(t))
 885                 return check_err(t, errorstr, "invalid pointer");
 886
 887         for (p = t->prop; p; p = p->next) {
 888                 if (is_literal(p)) {
 889                         if (name)
 890                                 return check_err(t, errorstr,
 891                                                  "has extra literal");
 892                         name = (struct name *)p;
 893                         break;
 894                 }
 895                 if (p != &null_parent.c.hdr && p != &null_parent.c.group.hdr
 896                     && !in_bounds(p))
 897                         return check_err(t, errorstr,
 898                                          "has bad property pointer");
 899
 900                 switch (p->type) {
 901                 case GROUP:
 902                         if (gr)
 903                                 return check_err(t, errorstr,
 904                                                  "has two groups");
 905                         gr = (struct group *)p;
 906                         break;
 907                 case CHILDREN:
 908                         if (children)
 909                                 return check_err(t, errorstr,
 910                                                  "has two child nodes");
 911                         children = (struct children *)p;
 912                         break;
 913                 case DESTRUCTOR:
 914                         break;
 915                 case NAME:
 916                         if (name)
 917                                 return check_err(t, errorstr,
 918                                                  "has two names");
 919                         name = (struct name *)p;
 920                         break;
 921                 default:
 922                         return check_err(t, errorstr, "has unknown property");
 923                 }
 924         }
 925         if (group && gr != group)
 926                 return check_err(t, errorstr, "has bad group");
 927
 928         if (children) {
 929                 if (!list_check(&children->group.list, errorstr))
 930                         return false;
 931                 gr = &children->group;
 932                 do {
 933                         if (gr->first_child) {
 934                                 if (!check_group(gr, gr->first_child, errorstr))
 935                                         return false;
 936                         } else if (gr != &children->group) {
 937                                 /* Empty groups should be deleted! */
 938                                 return check_err(t, errorstr,
 939                                                  "has empty group");
 940                         }
 941                         gr = next_group(gr);
 942                 } while (gr != &children->group);
 943         }
 944         return true;
 945 }
 946
 947 static bool check_group(struct group *group,
 948                         struct tal_hdr *t, const char *errorstr)
 949 {
 950         struct tal_hdr *i;
 951
 952         i = t;
 953         do {
 954                 if (!check_node(group, i, errorstr))
 955                         return false;
 956                 group = NULL;
 957                 i = i->next;
 958         } while (i != t);
 959         return true;
 960 }
 961
 962 bool tal_check(const tal_t *ctx, const char *errorstr)
 963 {
 964         struct tal_hdr *t = to_tal_hdr_or_null(ctx);
 965
 966         return check_node(NULL, t, errorstr);
 967 }
 968 #else /* NDEBUG */
 969 bool tal_check(const tal_t *ctx, const char *errorstr)
 970 {
 971         return true;
 972 }
 973 #endif