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>
15 /* How large should grouips get? */
16 #define GROUP_NODE_AVERAGE 32
18 /* 32-bit type field, first byte 0 in either endianness. */
20 CHILDREN = 0x00c1d500,
22 DESTRUCTOR = 0x00de5700,
28 struct prop_hdr *prop;
33 struct prop_hdr *next;
36 /* Unlike other properties, this is owned by parent, not child! */
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;
46 struct prop_hdr hdr; /* CHILDREN */
47 struct tal_hdr *parent;
48 /* We always have one group. Others may be added. */
53 struct prop_hdr hdr; /* DESTRUCTOR */
54 void (*destroy)(void *me);
58 struct prop_hdr hdr; /* NAME */
65 } null_parent = { { NULL, &null_parent.c.hdr },
69 { { &null_parent.c.group.list.n,
70 &null_parent.c.group.list.n } },
71 &null_parent.c, NULL } }
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;
80 static inline void COLD call_error(const char *msg)
85 static bool get_destroying_bit(struct tal_hdr *next)
87 return (size_t)next & 1;
90 static void set_destroying_bit(struct tal_hdr **next)
92 *next = (void *)((size_t)next | 1);
95 static struct tal_hdr *ignore_destroying_bit(struct tal_hdr *next)
97 return (void *)((size_t)next & ~(size_t)1);
100 static struct group *next_group(struct group *group)
102 return list_entry(group->list.n.next, struct group, list.n);
105 static bool atexit_set = false;
106 /* This means valgrind can see leaks. */
107 static void unlink_null(void)
109 struct group *i, *next;
111 for (i = next_group(&null_parent.c.group);
112 i != &null_parent.c.group;
114 next = next_group(i);
117 null_parent.c.group.first_child = NULL;
121 static const void *bounds_start, *bounds_end;
123 static void update_bounds(const void *new)
125 if (unlikely(!bounds_start))
126 bounds_start = bounds_end = new;
127 else if (new < bounds_start)
129 else if (new > bounds_end)
133 static bool in_bounds(const void *p)
135 return !p || (p >= bounds_start && p <= bounds_end);
138 static void update_bounds(const void *new)
142 static bool in_bounds(const void *p)
148 static void check_bounds(const void *p)
151 call_error("Not a valid header");
154 static struct tal_hdr *to_tal_hdr(const void *ctx)
158 t = (struct tal_hdr *)((char *)ctx - sizeof(struct tal_hdr));
160 check_bounds(ignore_destroying_bit(t->next));
164 static struct tal_hdr *to_tal_hdr_or_null(const void *ctx)
167 return &null_parent.hdr;
168 return to_tal_hdr(ctx);
171 static void *from_tal_hdr(struct tal_hdr *hdr)
177 static void *from_tal_hdr_or_null(struct tal_hdr *hdr)
179 if (hdr == &null_parent.hdr)
181 return from_tal_hdr(hdr);
184 static struct tal_hdr *debug_tal(struct tal_hdr *tal)
186 tal_check(from_tal_hdr_or_null(tal), "TAL_DEBUG ");
190 static struct tal_hdr *debug_tal(struct tal_hdr *tal)
196 static void *allocate(size_t size)
200 /* Don't hand silly sizes to malloc. */
201 if (size >> (CHAR_BIT*sizeof(size) - 1)) {
202 call_error("allocation size overflow");
208 call_error("allocation failed");
214 /* We carefully start all real properties with a zero byte. */
215 static bool is_literal(const struct prop_hdr *prop)
217 return ((char *)prop)[0] != 0;
220 static struct prop_hdr **find_property_ptr(const struct tal_hdr *t,
225 for (p = (struct prop_hdr **)&t->prop; *p; p = &(*p)->next) {
226 if (is_literal(*p)) {
231 if ((*p)->type == type)
237 static void *find_property(const struct tal_hdr *parent, enum prop_type type)
239 struct prop_hdr **p = find_property_ptr(parent, type);
246 static void init_property(struct prop_hdr *hdr,
247 struct tal_hdr *parent,
251 hdr->next = parent->prop;
255 static struct destructor *add_destructor_property(struct tal_hdr *t,
256 void (*destroy)(void *))
258 struct destructor *prop = allocate(sizeof(*prop));
260 init_property(&prop->hdr, t, DESTRUCTOR);
261 prop->destroy = destroy;
266 static struct name *add_name_property(struct tal_hdr *t, const char *name)
270 prop = allocate(sizeof(*prop) + strlen(name) + 1);
272 init_property(&prop->hdr, t, NAME);
273 strcpy(prop->name, name);
278 static void init_group_property(struct group *group,
279 struct children *parent_child,
280 struct tal_hdr *child)
282 init_property(&group->hdr, child, GROUP);
283 group->parent_child = parent_child;
284 group->first_child = child;
287 static struct children *add_child_property(struct tal_hdr *parent,
288 struct tal_hdr *child)
290 struct children *prop = allocate(sizeof(*prop));
292 init_property(&prop->hdr, parent, CHILDREN);
293 prop->parent = parent;
295 init_group_property(&prop->group, prop, child);
296 list_head_init(&prop->group.list);
297 update_bounds(&prop->group);
302 static struct group *add_group_property(struct tal_hdr *child,
303 struct children *parent_child)
305 struct group *prop = allocate(sizeof(*prop));
307 init_group_property(prop, parent_child, child);
311 static bool add_child(struct tal_hdr *parent, struct tal_hdr *child)
314 struct children *children = find_property(parent, CHILDREN);
317 children = add_child_property(parent, child);
320 children->group.list.n.next = children->group.list.n.prev
321 = &children->group.list.n;
323 /* Child links to itself. */
328 /* Last one (may be children->group itself). */
329 group = next_group(&children->group);
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)) {
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;
344 /* Child links to itself. */
349 if (unlikely(hash_pointer(child, 0) % GROUP_NODE_AVERAGE == 0)) {
350 struct group *newgroup;
352 newgroup = add_group_property(child, children);
353 if (likely(newgroup)) {
354 list_add(&children->group.list, &newgroup->list.n);
356 /* Child links to itself. */
360 /* Fall through: on allocation failure reuse old group. */
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;
369 static void del_tree(struct tal_hdr *t)
371 struct prop_hdr **prop, *p, *next;
373 /* Already being destroyed? Don't loop. */
374 if (unlikely(get_destroying_bit(t->next)))
377 set_destroying_bit(&t->next);
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));
387 /* Now free children and groups. */
388 prop = find_property_ptr(t, CHILDREN);
390 struct children *c = (struct children *)*prop;
391 struct group *group, *next;
395 next = next_group(group);
396 if (group->first_child) {
397 struct tal_hdr *i, *nextc;
399 i = group->first_child;
404 } while (i != group->first_child);
406 if (group != &c->group)
409 } while (group != &c->group);
412 /* Finally free our properties (groups are freed by parent). */
413 for (p = t->prop; p && !is_literal(p); p = next) {
415 if (p->type != GROUP)
421 void *tal_alloc_(const tal_t *ctx, size_t size, bool clear, const char *label)
423 struct tal_hdr *child, *parent = debug_tal(to_tal_hdr_or_null(ctx));
425 child = allocate(sizeof(struct tal_hdr) + size);
429 memset(from_tal_hdr(child), 0, size);
430 child->prop = (void *)label;
431 if (!add_child(parent, child)) {
436 return from_tal_hdr(debug_tal(child));
439 /* Update back ptrs, etc, as required.
440 * May return pointer to parent. */
441 static struct tal_hdr *remove_node(struct tal_hdr *t)
443 struct prop_hdr **prop;
444 struct tal_hdr *prev;
446 /* Loop around to find previous node. */
447 for (prev = t->next; prev->next != t; prev = prev->next);
449 /* Unlink ourselves. */
450 prev->next = t->next;
452 /* Are we the node with the group property? */
453 prop = find_property_ptr(t, GROUP);
455 struct group *group = (struct group *)*prop;
457 /* Are we the only one? */
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;
464 /* Empty group, so free it. */
465 list_del_from(&c->group.list, &group->list.n);
466 *prop = group->hdr.next;
471 /* Move property to next node. */
472 group->first_child = t->next;
474 *prop = group->hdr.next;
475 group->hdr.next = t->next->prop;
476 t->next->prop = &group->hdr;
482 void tal_free(const tal_t *ctx)
489 t = debug_tal(to_tal_hdr(ctx));
494 void *tal_steal_(const tal_t *new_parent, const tal_t *ctx)
497 struct tal_hdr *newpar, *t, *old_next, *old_parent;
499 newpar = debug_tal(to_tal_hdr_or_null(new_parent));
500 t = debug_tal(to_tal_hdr(ctx));
502 /* Save enough data to get us back if we fail! */
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
513 while (!(g = find_property(old_next, GROUP)))
514 old_next = old_next->next;
515 old_parent = g->parent_child->parent;
517 /* We can always add to old parent, becuase it has one
519 if (!add_child(old_parent, t))
528 bool tal_add_destructor_(tal_t *ctx, void (*destroy)(void *me))
530 return add_destructor_property(debug_tal(to_tal_hdr(ctx)), destroy);
533 bool tal_set_name_(tal_t *ctx, const char *name, bool literal)
535 struct tal_hdr *t = debug_tal(to_tal_hdr(ctx));
536 struct prop_hdr **prop = find_property_ptr(t, NAME);
538 /* Get rid of any old name */
540 struct name *name = (struct name *)*prop;
541 if (is_literal(&name->hdr))
544 *prop = name->hdr.next;
549 if (literal && name[0]) {
552 /* Append literal. */
553 for (p = &t->prop; *p && !is_literal(*p); p = &(*p)->next);
554 *p = (struct prop_hdr *)name;
557 if (!add_name_property(t, name))
563 const char *tal_name(const tal_t *t)
567 n = find_property(debug_tal(to_tal_hdr(t)), NAME);
571 if (is_literal(&n->hdr))
572 return (const char *)n;
576 /* Start one past first child: make stopping natural in circ. list. */
577 static struct tal_hdr *first_child(struct tal_hdr *parent)
579 struct children *child;
582 child = find_property(parent, CHILDREN);
586 /* Careful of empty group embedded in child property. */
587 if (child->group.first_child)
588 return child->group.first_child->next;
590 /* There could still be another group! */
591 group = next_group(&child->group);
592 if (group == &child->group)
595 return group->first_child->next;
598 tal_t *tal_first(const tal_t *root)
600 struct tal_hdr *c, *t = debug_tal(to_tal_hdr_or_null(root));
605 return from_tal_hdr(c);
608 tal_t *tal_next(const tal_t *root, const tal_t *prev)
610 struct tal_hdr *c, *t = debug_tal(to_tal_hdr(prev)), *top;
616 return from_tal_hdr(c);
618 top = to_tal_hdr_or_null(root);
622 /* Are we back to first child in group? */
623 group = find_property(t, GROUP);
625 return from_tal_hdr(t->next);
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);
632 /* OK, go back to parent. */
633 t = group->parent_child->parent;
639 tal_t *tal_parent(const tal_t *ctx)
642 struct tal_hdr *t = debug_tal(to_tal_hdr(ctx));
644 while (!(group = find_property(t, GROUP)))
647 if (group->parent_child->parent == &null_parent.hdr)
649 return from_tal_hdr(group->parent_child->parent);
652 void *tal_realloc_(tal_t *ctx, size_t size)
654 struct tal_hdr *old_t, *t, **prev;
656 struct children *child;
658 old_t = debug_tal(to_tal_hdr(ctx));
660 t = resizefn(old_t, size + sizeof(struct tal_hdr));
662 call_error("Reallocation failure");
670 /* Fix up linked list pointer. */
671 for (prev = &t->next; *prev != old_t; prev = &(*prev)->next);
674 /* Fix up group pointer, if any. */
675 group = find_property(t, GROUP);
677 assert(group->first_child == old_t);
678 group->first_child = t;
681 /* Fix up child propertie's parent pointer. */
682 child = find_property(t, CHILDREN);
684 assert(child->parent == old_t);
688 return from_tal_hdr(debug_tal(t));
691 char *tal_strdup(const tal_t *ctx, const char *p)
693 return tal_memdup(ctx, p, strlen(p)+1);
696 char *tal_strndup(const tal_t *ctx, const char *p, size_t n)
702 ret = tal_memdup(ctx, p, n+1);
708 void *tal_memdup(const tal_t *ctx, const void *p, size_t n)
715 ret = tal_arr(ctx, char, n);
721 char *tal_asprintf(const tal_t *ctx, const char *fmt, ...)
727 ret = tal_vasprintf(ctx, fmt, ap);
733 char *tal_vasprintf(const tal_t *ctx, const char *fmt, va_list ap)
735 size_t max = strlen(fmt) * 2;
740 buf = tal_arr(tal_parent(fmt), char, max);
742 buf = tal_arr(ctx, char, max);
748 ret = vsnprintf(buf, max, fmt, ap2);
753 buf = tal_resize(buf, max *= 2);
760 void tal_set_backend(void *(*alloc_fn)(size_t size),
761 void *(*resize_fn)(void *, size_t size),
762 void (*free_fn)(void *),
763 void (*error_fn)(const char *msg))
768 resizefn = resize_fn;
775 #ifdef CCAN_TAL_DEBUG
776 static void dump_node(unsigned int indent, const struct tal_hdr *t)
779 const struct prop_hdr *p;
781 for (i = 0; i < indent; i++)
784 for (p = t->prop; p; p = p->next) {
787 struct destructor *d;
790 printf(" \"%s\"", (const char *)p);
795 c = (struct children *)p;
796 printf(" CHILDREN(%p):parent=%p,group=%p\n",
797 p, c->parent, &c->group);
799 printf(" GROUP(%p):list={%p,%p},parent_ch=%p,first=%p",
800 g, g->list.n.next, g->list.n.next,
801 g->parent_child, g->first_child);
804 g = (struct group *)p;
805 printf(" GROUP(%p):list={%p,%p},,parent_ch=%p,first=%p",
806 p, g->list.n.next, g->list.n.next,
807 g->parent_child, g->first_child);
810 d = (struct destructor *)p;
811 printf(" DESTRUCTOR(%p):fn=%p", p, d->destroy);
814 n = (struct name *)p;
815 printf(" NAME(%p):%s", p, n->name);
818 printf(" **UNKNOWN(%p):%i**", p, p->type);
824 static void tal_dump_(unsigned int level, const struct tal_hdr *t)
826 struct children *children;
831 children = find_property(t, CHILDREN);
835 group = &children->group;
839 i = group->first_child;
842 tal_dump_(level+1, i);
844 } while (i != group->first_child);
846 group = next_group(group);
847 } while (group != &children->group);
852 tal_dump_(0, &null_parent.hdr);
854 #endif /* CCAN_TAL_DEBUG */
857 static bool check_err(struct tal_hdr *t, const char *errorstr,
861 /* Try not to malloc: it may be corrupted. */
862 char msg[strlen(errorstr) + 20 + strlen(errmsg) + 1];
863 sprintf(msg, "%s:%p %s", errorstr, from_tal_hdr(t), errmsg);
869 static bool check_group(struct group *group,
870 struct tal_hdr *t, const char *errorstr);
872 static bool check_node(struct group *group,
873 struct tal_hdr *t, const char *errorstr)
876 struct name *name = NULL;
877 struct children *children = NULL;
878 struct group *gr = NULL;
880 if (t != &null_parent.hdr && !in_bounds(t))
881 return check_err(t, errorstr, "invalid pointer");
883 for (p = t->prop; p; p = p->next) {
886 return check_err(t, errorstr,
887 "has extra literal");
888 name = (struct name *)p;
891 if (p != &null_parent.c.hdr && p != &null_parent.c.group.hdr
893 return check_err(t, errorstr,
894 "has bad property pointer");
899 return check_err(t, errorstr,
901 gr = (struct group *)p;
905 return check_err(t, errorstr,
906 "has two child nodes");
907 children = (struct children *)p;
913 return check_err(t, errorstr,
915 name = (struct name *)p;
918 return check_err(t, errorstr, "has unknown property");
921 if (group && gr != group)
922 return check_err(t, errorstr, "has bad group");
925 if (!list_check(&children->group.list, errorstr))
927 gr = &children->group;
929 if (gr->first_child) {
930 if (!check_group(gr, gr->first_child, errorstr))
932 } else if (gr != &children->group) {
933 /* Empty groups should be deleted! */
934 return check_err(t, errorstr,
938 } while (gr != &children->group);
943 static bool check_group(struct group *group,
944 struct tal_hdr *t, const char *errorstr)
950 if (!check_node(group, i, errorstr))
958 bool tal_check(const tal_t *ctx, const char *errorstr)
960 struct tal_hdr *t = to_tal_hdr_or_null(ctx);
962 return check_node(NULL, t, errorstr);
965 bool tal_check(const tal_t *ctx, const char *errorstr)