tal: take implies NULL passthrough.
[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         struct tal_hdr *t;
499         int saved_errno = errno;
500
501         if (!ctx)
502                 return;
503
504         t = debug_tal(to_tal_hdr(ctx));
505         remove_node(t);
506         del_tree(t);
507         errno = saved_errno;
508 }
509
510 void *tal_steal_(const tal_t *new_parent, const tal_t *ctx)
511 {
512         if (ctx) {
513                 struct tal_hdr *newpar, *t, *old_next, *old_parent;
514
515                 newpar = debug_tal(to_tal_hdr_or_null(new_parent));
516                 t = debug_tal(to_tal_hdr(ctx));
517
518                 /* Save enough data to get us back if we fail! */
519                 old_next = t->next;
520
521                 /* Unlink it from old parent. */
522                 old_parent = remove_node(t);
523                 if (unlikely(!add_child(newpar, t))) {
524                         /* If we were last child, parent returned by
525                          * remove_node, otherwise search old siblings
526                          * for it. */
527                         if (!old_parent) {
528                                 struct group *g;
529                                 while (!(g = find_property(old_next, GROUP)))
530                                         old_next = old_next->next;
531                                 old_parent = g->parent_child->parent;
532                         }
533                         /* We can always add to old parent, becuase it has one
534                          * group already. */
535                         if (!add_child(old_parent, t))
536                                 abort();
537                         return NULL;
538                 }
539                 debug_tal(newpar);
540         }
541         return (void *)ctx;
542 }
543
544 bool tal_add_destructor_(tal_t *ctx, void (*destroy)(void *me))
545 {
546         return add_destructor_property(debug_tal(to_tal_hdr(ctx)), destroy);
547 }
548
549 bool tal_set_name_(tal_t *ctx, const char *name, bool literal)
550 {
551         struct tal_hdr *t = debug_tal(to_tal_hdr(ctx));
552         struct prop_hdr **prop = find_property_ptr(t, NAME);
553
554         /* Get rid of any old name */
555         if (prop) {
556                 struct name *name = (struct name *)*prop;
557                 if (is_literal(&name->hdr))
558                         *prop = NULL;
559                 else {
560                         *prop = name->hdr.next;
561                         freefn(name);
562                 }
563         }
564
565         if (literal && name[0]) {
566                 struct prop_hdr **p;
567
568                 /* Append literal. */
569                 for (p = &t->prop; *p && !is_literal(*p); p = &(*p)->next);
570                 *p = (struct prop_hdr *)name;
571                 return true;
572         }
573         if (!add_name_property(t, name))
574                 return false;
575         debug_tal(t);
576         return true;
577 }
578
579 const char *tal_name(const tal_t *t)
580 {
581         struct name *n;
582
583         n = find_property(debug_tal(to_tal_hdr(t)), NAME);
584         if (!n)
585                 return NULL;
586
587         if (is_literal(&n->hdr))
588                 return (const char *)n;
589         return n->name;
590 }
591
592 /* Start one past first child: make stopping natural in circ. list. */
593 static struct tal_hdr *first_child(struct tal_hdr *parent)
594 {
595         struct children *child;
596         struct group *group;
597
598         child = find_property(parent, CHILDREN);
599         if (!child)
600                 return NULL;
601
602         /* Careful of empty group embedded in child property. */
603         if (child->group.first_child)
604                 return child->group.first_child->next;
605
606         /* There could still be another group! */
607         group = next_group(&child->group);
608         if (group == &child->group)
609                 return NULL;
610
611         return group->first_child->next;
612 }
613
614 tal_t *tal_first(const tal_t *root)
615 {
616         struct tal_hdr *c, *t = debug_tal(to_tal_hdr_or_null(root));
617
618         c = first_child(t);
619         if (!c)
620                 return NULL;
621         return from_tal_hdr(c);
622 }
623
624 tal_t *tal_next(const tal_t *root, const tal_t *prev)
625 {
626         struct tal_hdr *c, *t = debug_tal(to_tal_hdr(prev)), *top;
627         struct group *group;
628
629         /* Children? */
630         c = first_child(t);
631         if (c)
632                 return from_tal_hdr(c);
633
634         top = to_tal_hdr_or_null(root);
635         do {
636                 struct group *next;
637
638                 /* Are we back to first child in group? */
639                 group = find_property(t, GROUP);
640                 if (!group)
641                         return from_tal_hdr(t->next);
642
643                 /* Last group is one inside children property. */
644                 next = next_group(group);
645                 if (next != &group->parent_child->group)
646                         return from_tal_hdr(next->first_child->next);
647
648                 /* OK, go back to parent. */
649                 t = group->parent_child->parent;
650         } while (t != top);
651
652         return NULL;
653 }
654
655 tal_t *tal_parent(const tal_t *ctx)
656 {
657         struct group *group;
658         struct tal_hdr *t;
659
660         if (!ctx)
661                 return NULL;
662
663         t = debug_tal(to_tal_hdr(ctx));
664
665         while (!(group = find_property(t, GROUP)))
666                 t = t->next;
667
668         if (group->parent_child->parent == &null_parent.hdr)
669                 return NULL;
670         return from_tal_hdr(group->parent_child->parent);
671 }
672
673 bool tal_resize_(tal_t **ctxp, size_t size)
674 {
675         struct tal_hdr *old_t, *t, **prev;
676         struct group *group;
677         struct children *child;
678
679         old_t = debug_tal(to_tal_hdr(*ctxp));
680
681         /* Don't hand silly sizes to realloc. */
682         if (size >> (CHAR_BIT*sizeof(size) - 1)) {
683                 call_error("Reallocation size overflow");
684                 return false;
685         }
686
687         t = resizefn(old_t, size + sizeof(struct tal_hdr));
688         if (!t) {
689                 call_error("Reallocation failure");
690                 return false;
691         }
692
693         /* If it didn't move, we're done! */
694         if (t == old_t)
695                 return true;
696         update_bounds(t);
697
698         /* Fix up linked list pointer. */
699         for (prev = &t->next; *prev != old_t; prev = &(*prev)->next);
700         *prev = t;
701
702         /* Fix up group pointer, if any. */
703         group = find_property(t, GROUP);
704         if (group) {
705                 assert(group->first_child == old_t);
706                 group->first_child = t;
707         }
708
709         /* Fix up child propertie's parent pointer. */
710         child = find_property(t, CHILDREN);
711         if (child) {
712                 assert(child->parent == old_t);
713                 child->parent = t;
714         }
715         *ctxp = from_tal_hdr(debug_tal(t));
716         return true;
717 }
718
719 char *tal_strdup(const tal_t *ctx, const char *p)
720 {
721         /* We have to let through NULL for take(). */
722         return tal_dup(ctx, char, p, p ? strlen(p) + 1: 1, 0);
723 }
724
725 char *tal_strndup(const tal_t *ctx, const char *p, size_t n)
726 {
727         size_t len;
728         char *ret;
729
730         /* We have to let through NULL for take(). */
731         if (likely(p)) {
732                 len = strlen(p);
733                 if (len > n)
734                         len = n;
735         } else
736                 len = n;
737
738         ret = tal_dup(ctx, char, p, len, 1);
739         if (ret)
740                 ret[len] = '\0';
741         return ret;
742 }
743
744 void *tal_dup_(const tal_t *ctx, const void *p, size_t n, size_t extra,
745                const char *label)
746 {
747         void *ret;
748
749         /* Beware overflow! */
750         if (n + extra < n || n + extra + sizeof(struct tal_hdr) < n) {
751                 call_error("dup size overflow");
752                 if (taken(p))
753                         tal_free(p);
754                 return NULL;
755         }
756
757         if (taken(p)) {
758                 if (unlikely(!p))
759                         return NULL;
760                 if (unlikely(!tal_resize_((void **)&p, n + extra))) {
761                         tal_free(p);
762                         return NULL;
763                 }
764                 if (unlikely(!tal_steal(ctx, p))) {
765                         tal_free(p);
766                         return NULL;
767                 }
768                 return (void *)p;
769         }
770         ret = tal_alloc_(ctx, n + extra, false, label);
771         if (ret)
772                 memcpy(ret, p, n);
773         return ret;
774 }
775
776 char *tal_asprintf(const tal_t *ctx, const char *fmt, ...)
777 {
778         va_list ap;
779         char *ret;
780
781         va_start(ap, fmt);
782         ret = tal_vasprintf(ctx, fmt, ap);
783         va_end(ap);
784
785         return ret;
786 }
787
788 char *tal_vasprintf(const tal_t *ctx, const char *fmt, va_list ap)
789 {
790         size_t max;
791         char *buf;
792         int ret;
793
794         if (!fmt && taken(fmt))
795                 return NULL;
796
797         /* A decent guess to start. */
798         max = strlen(fmt) * 2;
799         buf = tal_arr(ctx, char, max);
800         while (buf) {
801                 va_list ap2;
802
803                 va_copy(ap2, ap);
804                 ret = vsnprintf(buf, max, fmt, ap2);
805                 va_end(ap2);
806
807                 if (ret < max)
808                         break;
809                 if (!tal_resize(&buf, max *= 2)) {
810                         tal_free(buf);
811                         buf = NULL;
812                 }
813         }
814         if (taken(fmt))
815                 tal_free(fmt);
816         return buf;
817 }
818
819 void tal_set_backend(void *(*alloc_fn)(size_t size),
820                      void *(*resize_fn)(void *, size_t size),
821                      void (*free_fn)(void *),
822                      void (*error_fn)(const char *msg))
823 {
824         if (alloc_fn)
825                 allocfn = alloc_fn;
826         if (resize_fn)
827                 resizefn = resize_fn;
828         if (free_fn)
829                 freefn = free_fn;
830         if (error_fn)
831                 errorfn = error_fn;
832 }
833
834 #ifdef CCAN_TAL_DEBUG
835 static void dump_node(unsigned int indent, const struct tal_hdr *t)
836 {
837         unsigned int i;
838         const struct prop_hdr *p;
839
840         for (i = 0; i < indent; i++)
841                 printf("  ");
842         printf("%p", t);
843         for (p = t->prop; p; p = p->next) {
844                 struct group *g;
845                 struct children *c;
846                 struct destructor *d;
847                 struct name *n;
848                 if (is_literal(p)) {
849                         printf(" \"%s\"", (const char *)p);
850                         break;
851                 }
852                 switch (p->type) {
853                 case CHILDREN:
854                         c = (struct children *)p;
855                         printf(" CHILDREN(%p):parent=%p,group=%p\n",
856                                p, c->parent, &c->group);
857                         g = &c->group;
858                         printf("  GROUP(%p):list={%p,%p},parent_ch=%p,first=%p",
859                                g, g->list.n.next, g->list.n.next,
860                                g->parent_child, g->first_child);
861                         break;
862                 case GROUP:
863                         g = (struct group *)p;
864                         printf(" GROUP(%p):list={%p,%p},,parent_ch=%p,first=%p",
865                                p, g->list.n.next, g->list.n.next,
866                                g->parent_child, g->first_child);
867                         break;
868                 case DESTRUCTOR:
869                         d = (struct destructor *)p;
870                         printf(" DESTRUCTOR(%p):fn=%p", p, d->destroy);
871                         break;
872                 case NAME:
873                         n = (struct name *)p;
874                         printf(" NAME(%p):%s", p, n->name);
875                         break;
876                 default:
877                         printf(" **UNKNOWN(%p):%i**", p, p->type);
878                 }
879         }
880         printf("\n");
881 }
882
883 static void tal_dump_(unsigned int level, const struct tal_hdr *t)
884 {
885         struct children *children;
886         struct group *group;
887
888         dump_node(level, t);
889
890         children = find_property(t, CHILDREN);
891         if (!children)
892                 return;
893
894         group = &children->group;
895         do {
896                 struct tal_hdr *i;
897
898                 i = group->first_child;
899                 if (i) {
900                         do {
901                                 tal_dump_(level+1, i);
902                                 i = i->next;
903                         } while (i != group->first_child);
904                 }
905                 group = next_group(group);
906         } while (group != &children->group);
907 }
908
909 void tal_dump(void)
910 {
911         tal_dump_(0, &null_parent.hdr);
912 }
913 #endif /* CCAN_TAL_DEBUG */
914
915 #ifndef NDEBUG
916 static bool check_err(struct tal_hdr *t, const char *errorstr,
917                       const char *errmsg)
918 {
919         if (errorstr) {
920                 /* Try not to malloc: it may be corrupted. */
921                 char msg[strlen(errorstr) + 20 + strlen(errmsg) + 1];
922                 sprintf(msg, "%s:%p %s", errorstr, from_tal_hdr(t), errmsg);
923                 call_error(msg);
924         }
925         return false;
926 }
927
928 static bool check_group(struct group *group,
929                         struct tal_hdr *t, const char *errorstr);
930
931 static bool check_node(struct group *group,
932                        struct tal_hdr *t, const char *errorstr)
933 {
934         struct prop_hdr *p;
935         struct name *name = NULL;
936         struct children *children = NULL;
937         struct group *gr = NULL;
938
939         if (t != &null_parent.hdr && !in_bounds(t))
940                 return check_err(t, errorstr, "invalid pointer");
941
942         for (p = t->prop; p; p = p->next) {
943                 if (is_literal(p)) {
944                         if (name)
945                                 return check_err(t, errorstr,
946                                                  "has extra literal");
947                         name = (struct name *)p;
948                         break;
949                 }
950                 if (p != &null_parent.c.hdr && p != &null_parent.c.group.hdr
951                     && !in_bounds(p))
952                         return check_err(t, errorstr,
953                                          "has bad property pointer");
954
955                 switch (p->type) {
956                 case GROUP:
957                         if (gr)
958                                 return check_err(t, errorstr,
959                                                  "has two groups");
960                         gr = (struct group *)p;
961                         break;
962                 case CHILDREN:
963                         if (children)
964                                 return check_err(t, errorstr,
965                                                  "has two child nodes");
966                         children = (struct children *)p;
967                         break;
968                 case DESTRUCTOR:
969                         break;
970                 case NAME:
971                         if (name)
972                                 return check_err(t, errorstr,
973                                                  "has two names");
974                         name = (struct name *)p;
975                         break;
976                 default:
977                         return check_err(t, errorstr, "has unknown property");
978                 }
979         }
980         if (group && gr != group)
981                 return check_err(t, errorstr, "has bad group");
982
983         if (children) {
984                 if (!list_check(&children->group.list, errorstr))
985                         return false;
986                 gr = &children->group;
987                 do {
988                         if (gr->first_child) {
989                                 if (!check_group(gr, gr->first_child, errorstr))
990                                         return false;
991                         } else if (gr != &children->group) {
992                                 /* Empty groups should be deleted! */
993                                 return check_err(t, errorstr,
994                                                  "has empty group");
995                         }
996                         gr = next_group(gr);
997                 } while (gr != &children->group);
998         }
999         return true;
1000 }
1001
1002 static bool check_group(struct group *group,
1003                         struct tal_hdr *t, const char *errorstr)
1004 {
1005         struct tal_hdr *i;
1006
1007         i = t;
1008         do {
1009                 if (!check_node(group, i, errorstr))
1010                         return false;
1011                 group = NULL;
1012                 i = i->next;
1013         } while (i != t);
1014         return true;
1015 }
1016
1017 bool tal_check(const tal_t *ctx, const char *errorstr)
1018 {
1019         struct tal_hdr *t = to_tal_hdr_or_null(ctx);
1020
1021         return check_node(NULL, t, errorstr);
1022 }
1023 #else /* NDEBUG */
1024 bool tal_check(const tal_t *ctx, const char *errorstr)
1025 {
1026         return true;
1027 }
1028 #endif