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