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