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