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