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