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