1 /* Licensed under BSD-MIT - see LICENSE file for details */
2 #include <ccan/tal/tal.h>
3 #include <ccan/compiler/compiler.h>
4 #include <ccan/hash/hash.h>
5 #include <ccan/list/list.h>
6 #include <ccan/take/take.h>
17 /* How large should grouips get? */
18 #define GROUP_NODE_AVERAGE 32
20 /* 32-bit type field, first byte 0 in either endianness. */
22 CHILDREN = 0x00c1d500,
24 DESTRUCTOR = 0x00de5700,
30 struct prop_hdr *prop;
35 struct prop_hdr *next;
38 /* Unlike other properties, this is owned by parent, not child! */
40 struct prop_hdr hdr; /* GROUP */
41 struct list_head list; /* Head for child->group, node for others. */
42 /* We point to parent's children property, as it doesn't move! */
43 struct children *parent_child;
44 struct tal_hdr *first_child;
48 struct prop_hdr hdr; /* CHILDREN */
49 struct tal_hdr *parent;
50 /* We always have one group. Others may be added. */
55 struct prop_hdr hdr; /* DESTRUCTOR */
56 void (*destroy)(void *me);
60 struct prop_hdr hdr; /* NAME */
67 } null_parent = { { NULL, &null_parent.c.hdr },
71 { { &null_parent.c.group.list.n,
72 &null_parent.c.group.list.n } },
73 &null_parent.c, NULL } }
77 static void *(*allocfn)(size_t size) = malloc;
78 static void *(*resizefn)(void *, size_t size) = realloc;
79 static void (*freefn)(void *) = free;
80 static void (*errorfn)(const char *msg) = (void *)abort;
82 static inline void COLD call_error(const char *msg)
87 static bool get_destroying_bit(struct tal_hdr *next)
89 return (size_t)next & 1;
92 static void set_destroying_bit(struct tal_hdr **next)
94 *next = (void *)((size_t)next | 1);
97 static struct tal_hdr *ignore_destroying_bit(struct tal_hdr *next)
99 return (void *)((size_t)next & ~(size_t)1);
102 static struct group *next_group(struct group *group)
104 return list_entry(group->list.n.next, struct group, list.n);
107 static bool initialized = false;
109 /* This means valgrind can see leaks. */
110 static void tal_cleanup(void)
112 struct group *i, *next;
114 /* Unlink null_parent. */
115 for (i = next_group(&null_parent.c.group);
116 i != &null_parent.c.group;
118 next = next_group(i);
121 null_parent.c.group.first_child = NULL;
123 /* Cleanup any taken pointers. */
127 /* For allocation failures inside ccan/take */
128 static void take_alloc_failed(const void *p)
134 static const void *bounds_start, *bounds_end;
136 static void update_bounds(const void *new)
138 if (unlikely(!bounds_start))
139 bounds_start = bounds_end = new;
140 else if (new < bounds_start)
142 else if (new > bounds_end)
146 static bool in_bounds(const void *p)
148 return !p || (p >= bounds_start && p <= bounds_end);
151 static void update_bounds(const void *new)
155 static bool in_bounds(const void *p)
161 static void check_bounds(const void *p)
164 call_error("Not a valid header");
167 static struct tal_hdr *to_tal_hdr(const void *ctx)
171 t = (struct tal_hdr *)((char *)ctx - sizeof(struct tal_hdr));
173 check_bounds(ignore_destroying_bit(t->next));
177 static struct tal_hdr *to_tal_hdr_or_null(const void *ctx)
180 return &null_parent.hdr;
181 return to_tal_hdr(ctx);
184 static void *from_tal_hdr(struct tal_hdr *hdr)
190 static void *from_tal_hdr_or_null(struct tal_hdr *hdr)
192 if (hdr == &null_parent.hdr)
194 return from_tal_hdr(hdr);
197 static struct tal_hdr *debug_tal(struct tal_hdr *tal)
199 tal_check(from_tal_hdr_or_null(tal), "TAL_DEBUG ");
203 static struct tal_hdr *debug_tal(struct tal_hdr *tal)
209 static void *allocate(size_t size)
213 /* Don't hand silly sizes to malloc. */
214 if (size >> (CHAR_BIT*sizeof(size) - 1)) {
215 call_error("allocation size overflow");
221 call_error("allocation failed");
227 /* We carefully start all real properties with a zero byte. */
228 static bool is_literal(const struct prop_hdr *prop)
230 return ((char *)prop)[0] != 0;
233 static struct prop_hdr **find_property_ptr(const struct tal_hdr *t,
238 for (p = (struct prop_hdr **)&t->prop; *p; p = &(*p)->next) {
239 if (is_literal(*p)) {
244 if ((*p)->type == type)
250 static void *find_property(const struct tal_hdr *parent, enum prop_type type)
252 struct prop_hdr **p = find_property_ptr(parent, type);
259 static void init_property(struct prop_hdr *hdr,
260 struct tal_hdr *parent,
264 hdr->next = parent->prop;
268 static struct destructor *add_destructor_property(struct tal_hdr *t,
269 void (*destroy)(void *))
271 struct destructor *prop = allocate(sizeof(*prop));
273 init_property(&prop->hdr, t, DESTRUCTOR);
274 prop->destroy = destroy;
279 static struct name *add_name_property(struct tal_hdr *t, const char *name)
283 prop = allocate(sizeof(*prop) + strlen(name) + 1);
285 init_property(&prop->hdr, t, NAME);
286 strcpy(prop->name, name);
291 static void init_group_property(struct group *group,
292 struct children *parent_child,
293 struct tal_hdr *child)
295 init_property(&group->hdr, child, GROUP);
296 group->parent_child = parent_child;
297 group->first_child = child;
300 static struct children *add_child_property(struct tal_hdr *parent,
301 struct tal_hdr *child)
303 struct children *prop = allocate(sizeof(*prop));
305 init_property(&prop->hdr, parent, CHILDREN);
306 prop->parent = parent;
308 init_group_property(&prop->group, prop, child);
309 list_head_init(&prop->group.list);
310 update_bounds(&prop->group);
315 static struct group *add_group_property(struct tal_hdr *child,
316 struct children *parent_child)
318 struct group *prop = allocate(sizeof(*prop));
320 init_group_property(prop, parent_child, child);
324 static bool add_child(struct tal_hdr *parent, struct tal_hdr *child)
327 struct children *children = find_property(parent, CHILDREN);
330 children = add_child_property(parent, child);
333 list_head_init(&children->group.list);
335 /* Child links to itself. */
340 /* Last one (may be children->group itself). */
341 group = next_group(&children->group);
343 /* Empty group can happen: null_parent, or all children freed. */
344 if (unlikely(!group->first_child)) {
345 assert(group == &children->group);
346 /* This hits on first child appended to null parent. */
347 if (unlikely(!initialized)) {
349 take_allocfail(take_alloc_failed);
352 /* Link group into this child, make it the first one. */
353 group->hdr.next = child->prop;
354 child->prop = &group->hdr;
355 group->first_child = child;
357 /* Child links to itself. */
362 if (unlikely(hash_pointer(child, 0) % GROUP_NODE_AVERAGE == 0)) {
363 struct group *newgroup;
365 newgroup = add_group_property(child, children);
366 if (likely(newgroup)) {
367 list_add(&children->group.list, &newgroup->list.n);
369 /* Child links to itself. */
373 /* Fall through: on allocation failure reuse old group. */
376 /* We insert after head, otherwise we'd need to find end. */
377 child->next = group->first_child->next;
378 group->first_child->next = child;
382 static void del_tree(struct tal_hdr *t)
384 struct prop_hdr **prop, *p, *next;
386 /* Already being destroyed? Don't loop. */
387 if (unlikely(get_destroying_bit(t->next)))
390 set_destroying_bit(&t->next);
392 /* Carefully call destructors, removing as we go. */
393 while ((prop = find_property_ptr(t, DESTRUCTOR))) {
394 struct destructor *d = (struct destructor *)*prop;
395 d->destroy(from_tal_hdr(t));
400 /* Now free children and groups. */
401 prop = find_property_ptr(t, CHILDREN);
403 struct children *c = (struct children *)*prop;
404 struct group *group, *next;
408 next = next_group(group);
409 if (group->first_child) {
410 struct tal_hdr *i, *nextc;
412 i = group->first_child;
417 } while (i != group->first_child);
419 if (group != &c->group)
422 } while (group != &c->group);
425 /* Finally free our properties (groups are freed by parent). */
426 for (p = t->prop; p && !is_literal(p); p = next) {
428 if (p->type != GROUP)
434 void *tal_alloc_(const tal_t *ctx, size_t size, bool clear, const char *label)
436 struct tal_hdr *child, *parent = debug_tal(to_tal_hdr_or_null(ctx));
438 child = allocate(sizeof(struct tal_hdr) + size);
442 memset(from_tal_hdr(child), 0, size);
443 child->prop = (void *)label;
444 if (!add_child(parent, child)) {
449 return from_tal_hdr(debug_tal(child));
452 /* Update back ptrs, etc, as required.
453 * May return pointer to parent. */
454 static struct tal_hdr *remove_node(struct tal_hdr *t)
456 struct prop_hdr **prop;
457 struct tal_hdr *prev;
459 /* Loop around to find previous node. */
460 for (prev = t->next; prev->next != t; prev = prev->next);
462 /* Unlink ourselves. */
463 prev->next = t->next;
465 /* Are we the node with the group property? */
466 prop = find_property_ptr(t, GROUP);
468 struct group *group = (struct group *)*prop;
470 /* Are we the only one? */
472 struct prop_hdr *next = (*prop)->next;
473 struct children *c = group->parent_child;
474 /* Is this the group embedded in the child property? */
475 if (group == &c->group) {
476 group->first_child = NULL;
478 /* Empty group, so free it. */
479 list_del_from(&c->group.list, &group->list.n);
485 /* Move property to next node. */
486 group->first_child = t->next;
488 *prop = group->hdr.next;
489 group->hdr.next = t->next->prop;
490 t->next->prop = &group->hdr;
496 void *tal_free(const tal_t *ctx)
500 int saved_errno = errno;
501 t = debug_tal(to_tal_hdr(ctx));
509 void *tal_steal_(const tal_t *new_parent, const tal_t *ctx)
512 struct tal_hdr *newpar, *t, *old_next, *old_parent;
514 newpar = debug_tal(to_tal_hdr_or_null(new_parent));
515 t = debug_tal(to_tal_hdr(ctx));
517 /* Save enough data to get us back if we fail! */
520 /* Unlink it from old parent. */
521 old_parent = remove_node(t);
522 if (unlikely(!add_child(newpar, t))) {
523 /* If we were last child, parent returned by
524 * remove_node, otherwise search old siblings
528 while (!(g = find_property(old_next, GROUP)))
529 old_next = old_next->next;
530 old_parent = g->parent_child->parent;
532 /* We can always add to old parent, becuase it has one
534 if (!add_child(old_parent, t))
543 bool tal_add_destructor_(tal_t *ctx, void (*destroy)(void *me))
545 return add_destructor_property(debug_tal(to_tal_hdr(ctx)), destroy);
548 bool tal_set_name_(tal_t *ctx, const char *name, bool literal)
550 struct tal_hdr *t = debug_tal(to_tal_hdr(ctx));
551 struct prop_hdr **prop = find_property_ptr(t, NAME);
553 /* Get rid of any old name */
555 struct name *name = (struct name *)*prop;
556 if (is_literal(&name->hdr))
559 *prop = name->hdr.next;
564 if (literal && name[0]) {
567 /* Append literal. */
568 for (p = &t->prop; *p && !is_literal(*p); p = &(*p)->next);
569 *p = (struct prop_hdr *)name;
572 if (!add_name_property(t, name))
578 const char *tal_name(const tal_t *t)
582 n = find_property(debug_tal(to_tal_hdr(t)), NAME);
586 if (is_literal(&n->hdr))
587 return (const char *)n;
591 /* Start one past first child: make stopping natural in circ. list. */
592 static struct tal_hdr *first_child(struct tal_hdr *parent)
594 struct children *child;
597 child = find_property(parent, CHILDREN);
601 /* Careful of empty group embedded in child property. */
602 if (child->group.first_child)
603 return child->group.first_child->next;
605 /* There could still be another group! */
606 group = next_group(&child->group);
607 if (group == &child->group)
610 return group->first_child->next;
613 tal_t *tal_first(const tal_t *root)
615 struct tal_hdr *c, *t = debug_tal(to_tal_hdr_or_null(root));
620 return from_tal_hdr(c);
623 tal_t *tal_next(const tal_t *root, const tal_t *prev)
625 struct tal_hdr *c, *t = debug_tal(to_tal_hdr(prev)), *top;
631 return from_tal_hdr(c);
633 top = to_tal_hdr_or_null(root);
637 /* Are we back to first child in group? */
638 group = find_property(t, GROUP);
640 return from_tal_hdr(t->next);
642 /* Last group is one inside children property. */
643 next = next_group(group);
644 if (next != &group->parent_child->group)
645 return from_tal_hdr(next->first_child->next);
647 /* OK, go back to parent. */
648 t = group->parent_child->parent;
654 tal_t *tal_parent(const tal_t *ctx)
662 t = debug_tal(to_tal_hdr(ctx));
664 while (!(group = find_property(t, GROUP)))
667 if (group->parent_child->parent == &null_parent.hdr)
669 return from_tal_hdr(group->parent_child->parent);
672 bool tal_resize_(tal_t **ctxp, size_t size)
674 struct tal_hdr *old_t, *t, **prev;
676 struct children *child;
678 old_t = debug_tal(to_tal_hdr(*ctxp));
680 /* Don't hand silly sizes to realloc. */
681 if (size >> (CHAR_BIT*sizeof(size) - 1)) {
682 call_error("Reallocation size overflow");
686 t = resizefn(old_t, size + sizeof(struct tal_hdr));
688 call_error("Reallocation failure");
692 /* If it didn't move, we're done! */
697 /* Fix up linked list pointer. */
698 for (prev = &t->next; *prev != old_t; prev = &(*prev)->next);
701 /* Fix up group pointer, if any. */
702 group = find_property(t, GROUP);
704 assert(group->first_child == old_t);
705 group->first_child = t;
708 /* Fix up child propertie's parent pointer. */
709 child = find_property(t, CHILDREN);
711 assert(child->parent == old_t);
714 *ctxp = from_tal_hdr(debug_tal(t));
718 char *tal_strdup(const tal_t *ctx, const char *p)
720 /* We have to let through NULL for take(). */
721 return tal_dup(ctx, char, p, p ? strlen(p) + 1: 1, 0);
724 char *tal_strndup(const tal_t *ctx, const char *p, size_t n)
729 /* We have to let through NULL for take(). */
737 ret = tal_dup(ctx, char, p, len, 1);
743 void *tal_dup_(const tal_t *ctx, const void *p, size_t n, size_t extra,
748 /* Beware overflow! */
749 if (n + extra < n || n + extra + sizeof(struct tal_hdr) < n) {
750 call_error("dup size overflow");
759 if (unlikely(!tal_resize_((void **)&p, n + extra)))
761 if (unlikely(!tal_steal(ctx, p)))
765 ret = tal_alloc_(ctx, n + extra, false, label);
771 char *tal_asprintf(const tal_t *ctx, const char *fmt, ...)
777 ret = tal_vasprintf(ctx, fmt, ap);
783 char *tal_vasprintf(const tal_t *ctx, const char *fmt, va_list ap)
789 if (!fmt && taken(fmt))
792 /* A decent guess to start. */
793 max = strlen(fmt) * 2;
794 buf = tal_arr(ctx, char, max);
799 ret = vsnprintf(buf, max, fmt, ap2);
804 if (!tal_resize(&buf, max *= 2))
812 void tal_set_backend(void *(*alloc_fn)(size_t size),
813 void *(*resize_fn)(void *, size_t size),
814 void (*free_fn)(void *),
815 void (*error_fn)(const char *msg))
820 resizefn = resize_fn;
827 #ifdef CCAN_TAL_DEBUG
828 static void dump_node(unsigned int indent, const struct tal_hdr *t)
831 const struct prop_hdr *p;
833 for (i = 0; i < indent; i++)
836 for (p = t->prop; p; p = p->next) {
839 struct destructor *d;
842 printf(" \"%s\"", (const char *)p);
847 c = (struct children *)p;
848 printf(" CHILDREN(%p):parent=%p,group=%p\n",
849 p, c->parent, &c->group);
851 printf(" GROUP(%p):list={%p,%p},parent_ch=%p,first=%p",
852 g, g->list.n.next, g->list.n.next,
853 g->parent_child, g->first_child);
856 g = (struct group *)p;
857 printf(" GROUP(%p):list={%p,%p},,parent_ch=%p,first=%p",
858 p, g->list.n.next, g->list.n.next,
859 g->parent_child, g->first_child);
862 d = (struct destructor *)p;
863 printf(" DESTRUCTOR(%p):fn=%p", p, d->destroy);
866 n = (struct name *)p;
867 printf(" NAME(%p):%s", p, n->name);
870 printf(" **UNKNOWN(%p):%i**", p, p->type);
876 static void tal_dump_(unsigned int level, const struct tal_hdr *t)
878 struct children *children;
883 children = find_property(t, CHILDREN);
887 group = &children->group;
891 i = group->first_child;
894 tal_dump_(level+1, i);
896 } while (i != group->first_child);
898 group = next_group(group);
899 } while (group != &children->group);
904 tal_dump_(0, &null_parent.hdr);
906 #endif /* CCAN_TAL_DEBUG */
909 static bool check_err(struct tal_hdr *t, const char *errorstr,
913 /* Try not to malloc: it may be corrupted. */
914 char msg[strlen(errorstr) + 20 + strlen(errmsg) + 1];
915 sprintf(msg, "%s:%p %s", errorstr, from_tal_hdr(t), errmsg);
921 static bool check_group(struct group *group,
922 struct tal_hdr *t, const char *errorstr);
924 static bool check_node(struct group *group,
925 struct tal_hdr *t, const char *errorstr)
928 struct name *name = NULL;
929 struct children *children = NULL;
930 struct group *gr = NULL;
932 if (t != &null_parent.hdr && !in_bounds(t))
933 return check_err(t, errorstr, "invalid pointer");
935 for (p = t->prop; p; p = p->next) {
938 return check_err(t, errorstr,
939 "has extra literal");
940 name = (struct name *)p;
943 if (p != &null_parent.c.hdr && p != &null_parent.c.group.hdr
945 return check_err(t, errorstr,
946 "has bad property pointer");
951 return check_err(t, errorstr,
953 gr = (struct group *)p;
957 return check_err(t, errorstr,
958 "has two child nodes");
959 children = (struct children *)p;
965 return check_err(t, errorstr,
967 name = (struct name *)p;
970 return check_err(t, errorstr, "has unknown property");
973 if (group && gr != group)
974 return check_err(t, errorstr, "has bad group");
977 if (!list_check(&children->group.list, errorstr))
979 gr = &children->group;
981 if (gr->first_child) {
982 if (!check_group(gr, gr->first_child, errorstr))
984 } else if (gr != &children->group) {
985 /* Empty groups should be deleted! */
986 return check_err(t, errorstr,
990 } while (gr != &children->group);
995 static bool check_group(struct group *group,
996 struct tal_hdr *t, const char *errorstr)
1002 if (!check_node(group, i, errorstr))
1010 bool tal_check(const tal_t *ctx, const char *errorstr)
1012 struct tal_hdr *t = to_tal_hdr_or_null(ctx);
1014 return check_node(NULL, t, errorstr);
1017 bool tal_check(const tal_t *ctx, const char *errorstr)