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 prop_hdr *next = (*prop)->next;
 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                                 freefn(group);
 467                         }
 468                         *prop = next;
 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;
 643
 644         if (!ctx)
 645                 return NULL;
 646
 647         t = debug_tal(to_tal_hdr(ctx));
 648
 649         while (!(group = find_property(t, GROUP)))
 650                 t = t->next;
 651
 652         if (group->parent_child->parent == &null_parent.hdr)
 653                 return NULL;
 654         return from_tal_hdr(group->parent_child->parent);
 655 }
 656
 657 void *tal_realloc_(tal_t *ctx, size_t size)
 658 {
 659         struct tal_hdr *old_t, *t, **prev;
 660         struct group *group;
 661         struct children *child;
 662
 663         old_t = debug_tal(to_tal_hdr(ctx));
 664
 665         t = resizefn(old_t, size + sizeof(struct tal_hdr));
 666         if (!t) {
 667                 call_error("Reallocation failure");
 668                 tal_free(old_t);
 669                 return NULL;
 670         }
 671         if (t == old_t)
 672                 return ctx;
 673         update_bounds(t);
 674
 675         /* Fix up linked list pointer. */
 676         for (prev = &t->next; *prev != old_t; prev = &(*prev)->next);
 677         *prev = t;
 678
 679         /* Fix up group pointer, if any. */
 680         group = find_property(t, GROUP);
 681         if (group) {
 682                 assert(group->first_child == old_t);
 683                 group->first_child = t;
 684         }
 685
 686         /* Fix up child propertie's parent pointer. */
 687         child = find_property(t, CHILDREN);
 688         if (child) {
 689                 assert(child->parent == old_t);
 690                 child->parent = t;
 691         }
 692
 693         return from_tal_hdr(debug_tal(t));
 694 }
 695
 696 char *tal_strdup(const tal_t *ctx, const char *p)
 697 {
 698         return tal_memdup(ctx, p, strlen(p)+1);
 699 }
 700
 701 char *tal_strndup(const tal_t *ctx, const char *p, size_t n)
 702 {
 703         char *ret;
 704
 705         if (strlen(p) < n)
 706                 n = strlen(p);
 707         ret = tal_memdup(ctx, p, n+1);
 708         if (ret)
 709                 ret[n] = '\0';
 710         return ret;
 711 }
 712
 713 void *tal_memdup(const tal_t *ctx, const void *p, size_t n)
 714 {
 715         void *ret;
 716
 717         if (ctx == TAL_TAKE)
 718                 return (void *)p;
 719
 720         ret = tal_arr(ctx, char, n);
 721         if (ret)
 722                 memcpy(ret, p, n);
 723         return ret;
 724 }
 725
 726 char *tal_asprintf(const tal_t *ctx, const char *fmt, ...)
 727 {
 728         va_list ap;
 729         char *ret;
 730
 731         va_start(ap, fmt);
 732         ret = tal_vasprintf(ctx, fmt, ap);
 733         va_end(ap);
 734
 735         return ret;
 736 }
 737
 738 char *tal_vasprintf(const tal_t *ctx, const char *fmt, va_list ap)
 739 {
 740         size_t max = strlen(fmt) * 2;
 741         char *buf;
 742         int ret;
 743
 744         if (ctx == TAL_TAKE)
 745                 buf = tal_arr(tal_parent(fmt), char, max);
 746         else
 747                 buf = tal_arr(ctx, char, max);
 748
 749         while (buf) {
 750                 va_list ap2;
 751
 752                 va_copy(ap2, ap);
 753                 ret = vsnprintf(buf, max, fmt, ap2);
 754                 va_end(ap2);
 755
 756                 if (ret < max)
 757                         break;
 758                 buf = tal_resize(buf, max *= 2);
 759         }
 760         if (ctx == TAL_TAKE)
 761                 tal_free(fmt);
 762         return buf;
 763 }
 764
 765 void tal_set_backend(void *(*alloc_fn)(size_t size),
 766                      void *(*resize_fn)(void *, size_t size),
 767                      void (*free_fn)(void *),
 768                      void (*error_fn)(const char *msg))
 769 {
 770         if (alloc_fn)
 771                 allocfn = alloc_fn;
 772         if (resize_fn)
 773                 resizefn = resize_fn;
 774         if (free_fn)
 775                 freefn = free_fn;
 776         if (error_fn)
 777                 errorfn = error_fn;
 778 }
 779
 780 #ifdef CCAN_TAL_DEBUG
 781 static void dump_node(unsigned int indent, const struct tal_hdr *t)
 782 {
 783         unsigned int i;
 784         const struct prop_hdr *p;
 785
 786         for (i = 0; i < indent; i++)
 787                 printf("  ");
 788         printf("%p", t);
 789         for (p = t->prop; p; p = p->next) {
 790                 struct group *g;
 791                 struct children *c;
 792                 struct destructor *d;
 793                 struct name *n;
 794                 if (is_literal(p)) {
 795                         printf(" \"%s\"", (const char *)p);
 796                         break;
 797                 }
 798                 switch (p->type) {
 799                 case CHILDREN:
 800                         c = (struct children *)p;
 801                         printf(" CHILDREN(%p):parent=%p,group=%p\n",
 802                                p, c->parent, &c->group);
 803                         g = &c->group;
 804                         printf("  GROUP(%p):list={%p,%p},parent_ch=%p,first=%p",
 805                                g, g->list.n.next, g->list.n.next,
 806                                g->parent_child, g->first_child);
 807                         break;
 808                 case GROUP:
 809                         g = (struct group *)p;
 810                         printf(" GROUP(%p):list={%p,%p},,parent_ch=%p,first=%p",
 811                                p, g->list.n.next, g->list.n.next,
 812                                g->parent_child, g->first_child);
 813                         break;
 814                 case DESTRUCTOR:
 815                         d = (struct destructor *)p;
 816                         printf(" DESTRUCTOR(%p):fn=%p", p, d->destroy);
 817                         break;
 818                 case NAME:
 819                         n = (struct name *)p;
 820                         printf(" NAME(%p):%s", p, n->name);
 821                         break;
 822                 default:
 823                         printf(" **UNKNOWN(%p):%i**", p, p->type);
 824                 }
 825         }
 826         printf("\n");
 827 }
 828
 829 static void tal_dump_(unsigned int level, const struct tal_hdr *t)
 830 {
 831         struct children *children;
 832         struct group *group;
 833
 834         dump_node(level, t);
 835
 836         children = find_property(t, CHILDREN);
 837         if (!children)
 838                 return;
 839
 840         group = &children->group;
 841         do {
 842                 struct tal_hdr *i;
 843
 844                 i = group->first_child;
 845                 if (i) {
 846                         do {
 847                                 tal_dump_(level+1, i);
 848                                 i = i->next;
 849                         } while (i != group->first_child);
 850                 }
 851                 group = next_group(group);
 852         } while (group != &children->group);
 853 }
 854
 855 void tal_dump(void)
 856 {
 857         tal_dump_(0, &null_parent.hdr);
 858 }
 859 #endif /* CCAN_TAL_DEBUG */
 860
 861 #ifndef NDEBUG
 862 static bool check_err(struct tal_hdr *t, const char *errorstr,
 863                       const char *errmsg)
 864 {
 865         if (errorstr) {
 866                 /* Try not to malloc: it may be corrupted. */
 867                 char msg[strlen(errorstr) + 20 + strlen(errmsg) + 1];
 868                 sprintf(msg, "%s:%p %s", errorstr, from_tal_hdr(t), errmsg);
 869                 call_error(msg);
 870         }
 871         return false;
 872 }
 873
 874 static bool check_group(struct group *group,
 875                         struct tal_hdr *t, const char *errorstr);
 876
 877 static bool check_node(struct group *group,
 878                        struct tal_hdr *t, const char *errorstr)
 879 {
 880         struct prop_hdr *p;
 881         struct name *name = NULL;
 882         struct children *children = NULL;
 883         struct group *gr = NULL;
 884
 885         if (t != &null_parent.hdr && !in_bounds(t))
 886                 return check_err(t, errorstr, "invalid pointer");
 887
 888         for (p = t->prop; p; p = p->next) {
 889                 if (is_literal(p)) {
 890                         if (name)
 891                                 return check_err(t, errorstr,
 892                                                  "has extra literal");
 893                         name = (struct name *)p;
 894                         break;
 895                 }
 896                 if (p != &null_parent.c.hdr && p != &null_parent.c.group.hdr
 897                     && !in_bounds(p))
 898                         return check_err(t, errorstr,
 899                                          "has bad property pointer");
 900
 901                 switch (p->type) {
 902                 case GROUP:
 903                         if (gr)
 904                                 return check_err(t, errorstr,
 905                                                  "has two groups");
 906                         gr = (struct group *)p;
 907                         break;
 908                 case CHILDREN:
 909                         if (children)
 910                                 return check_err(t, errorstr,
 911                                                  "has two child nodes");
 912                         children = (struct children *)p;
 913                         break;
 914                 case DESTRUCTOR:
 915                         break;
 916                 case NAME:
 917                         if (name)
 918                                 return check_err(t, errorstr,
 919                                                  "has two names");
 920                         name = (struct name *)p;
 921                         break;
 922                 default:
 923                         return check_err(t, errorstr, "has unknown property");
 924                 }
 925         }
 926         if (group && gr != group)
 927                 return check_err(t, errorstr, "has bad group");
 928
 929         if (children) {
 930                 if (!list_check(&children->group.list, errorstr))
 931                         return false;
 932                 gr = &children->group;
 933                 do {
 934                         if (gr->first_child) {
 935                                 if (!check_group(gr, gr->first_child, errorstr))
 936                                         return false;
 937                         } else if (gr != &children->group) {
 938                                 /* Empty groups should be deleted! */
 939                                 return check_err(t, errorstr,
 940                                                  "has empty group");
 941                         }
 942                         gr = next_group(gr);
 943                 } while (gr != &children->group);
 944         }
 945         return true;
 946 }
 947
 948 static bool check_group(struct group *group,
 949                         struct tal_hdr *t, const char *errorstr)
 950 {
 951         struct tal_hdr *i;
 952
 953         i = t;
 954         do {
 955                 if (!check_node(group, i, errorstr))
 956                         return false;
 957                 group = NULL;
 958                 i = i->next;
 959         } while (i != t);
 960         return true;
 961 }
 962
 963 bool tal_check(const tal_t *ctx, const char *errorstr)
 964 {
 965         struct tal_hdr *t = to_tal_hdr_or_null(ctx);
 966
 967         return check_node(NULL, t, errorstr);
 968 }
 969 #else /* NDEBUG */
 970 bool tal_check(const tal_t *ctx, const char *errorstr)
 971 {
 972         return true;
 973 }
 974 #endif