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