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>
16 /* How large should grouips get? */
17 #define GROUP_NODE_AVERAGE 32
19 /* 32-bit type field, first byte 0 in either endianness. */
21 CHILDREN = 0x00c1d500,
23 DESTRUCTOR = 0x00de5700,
29 struct prop_hdr *prop;
34 struct prop_hdr *next;
37 /* Unlike other properties, this is owned by parent, not child! */
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;
47 struct prop_hdr hdr; /* CHILDREN */
48 struct tal_hdr *parent;
49 /* We always have one group. Others may be added. */
54 struct prop_hdr hdr; /* DESTRUCTOR */
55 void (*destroy)(void *me);
59 struct prop_hdr hdr; /* NAME */
66 } null_parent = { { NULL, &null_parent.c.hdr },
70 { { &null_parent.c.group.list.n,
71 &null_parent.c.group.list.n } },
72 &null_parent.c, NULL } }
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;
81 static inline void COLD call_error(const char *msg)
86 static bool get_destroying_bit(struct tal_hdr *next)
88 return (size_t)next & 1;
91 static void set_destroying_bit(struct tal_hdr **next)
93 *next = (void *)((size_t)next | 1);
96 static struct tal_hdr *ignore_destroying_bit(struct tal_hdr *next)
98 return (void *)((size_t)next & ~(size_t)1);
101 static struct group *next_group(struct group *group)
103 return list_entry(group->list.n.next, struct group, list.n);
106 static bool atexit_set = false;
107 /* This means valgrind can see leaks. */
108 static void unlink_null(void)
110 struct group *i, *next;
112 for (i = next_group(&null_parent.c.group);
113 i != &null_parent.c.group;
115 next = next_group(i);
118 null_parent.c.group.first_child = NULL;
122 static const void *bounds_start, *bounds_end;
124 static void update_bounds(const void *new)
126 if (unlikely(!bounds_start))
127 bounds_start = bounds_end = new;
128 else if (new < bounds_start)
130 else if (new > bounds_end)
134 static bool in_bounds(const void *p)
136 return !p || (p >= bounds_start && p <= bounds_end);
139 static void update_bounds(const void *new)
143 static bool in_bounds(const void *p)
149 static void check_bounds(const void *p)
152 call_error("Not a valid header");
155 static struct tal_hdr *to_tal_hdr(const void *ctx)
159 t = (struct tal_hdr *)((char *)ctx - sizeof(struct tal_hdr));
161 check_bounds(ignore_destroying_bit(t->next));
165 static struct tal_hdr *to_tal_hdr_or_null(const void *ctx)
168 return &null_parent.hdr;
169 return to_tal_hdr(ctx);
172 static void *from_tal_hdr(struct tal_hdr *hdr)
178 static void *from_tal_hdr_or_null(struct tal_hdr *hdr)
180 if (hdr == &null_parent.hdr)
182 return from_tal_hdr(hdr);
185 static struct tal_hdr *debug_tal(struct tal_hdr *tal)
187 tal_check(from_tal_hdr_or_null(tal), "TAL_DEBUG ");
191 static struct tal_hdr *debug_tal(struct tal_hdr *tal)
197 static void *allocate(size_t size)
201 /* Don't hand silly sizes to malloc. */
202 if (size >> (CHAR_BIT*sizeof(size) - 1)) {
203 call_error("allocation size overflow");
209 call_error("allocation failed");
215 /* We carefully start all real properties with a zero byte. */
216 static bool is_literal(const struct prop_hdr *prop)
218 return ((char *)prop)[0] != 0;
221 static struct prop_hdr **find_property_ptr(const struct tal_hdr *t,
226 for (p = (struct prop_hdr **)&t->prop; *p; p = &(*p)->next) {
227 if (is_literal(*p)) {
232 if ((*p)->type == type)
238 static void *find_property(const struct tal_hdr *parent, enum prop_type type)
240 struct prop_hdr **p = find_property_ptr(parent, type);
247 static void init_property(struct prop_hdr *hdr,
248 struct tal_hdr *parent,
252 hdr->next = parent->prop;
256 static struct destructor *add_destructor_property(struct tal_hdr *t,
257 void (*destroy)(void *))
259 struct destructor *prop = allocate(sizeof(*prop));
261 init_property(&prop->hdr, t, DESTRUCTOR);
262 prop->destroy = destroy;
267 static struct name *add_name_property(struct tal_hdr *t, const char *name)
271 prop = allocate(sizeof(*prop) + strlen(name) + 1);
273 init_property(&prop->hdr, t, NAME);
274 strcpy(prop->name, name);
279 static void init_group_property(struct group *group,
280 struct children *parent_child,
281 struct tal_hdr *child)
283 init_property(&group->hdr, child, GROUP);
284 group->parent_child = parent_child;
285 group->first_child = child;
288 static struct children *add_child_property(struct tal_hdr *parent,
289 struct tal_hdr *child)
291 struct children *prop = allocate(sizeof(*prop));
293 init_property(&prop->hdr, parent, CHILDREN);
294 prop->parent = parent;
296 init_group_property(&prop->group, prop, child);
297 list_head_init(&prop->group.list);
298 update_bounds(&prop->group);
303 static struct group *add_group_property(struct tal_hdr *child,
304 struct children *parent_child)
306 struct group *prop = allocate(sizeof(*prop));
308 init_group_property(prop, parent_child, child);
312 static bool add_child(struct tal_hdr *parent, struct tal_hdr *child)
315 struct children *children = find_property(parent, CHILDREN);
318 children = add_child_property(parent, child);
321 list_head_init(&children->group.list);
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 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;
465 /* Empty group, so free it. */
466 list_del_from(&c->group.list, &group->list.n);
472 /* Move property to next node. */
473 group->first_child = t->next;
475 *prop = group->hdr.next;
476 group->hdr.next = t->next->prop;
477 t->next->prop = &group->hdr;
483 void tal_free(const tal_t *ctx)
486 int saved_errno = errno;
491 t = debug_tal(to_tal_hdr(ctx));
497 void *tal_steal_(const tal_t *new_parent, const tal_t *ctx)
500 struct tal_hdr *newpar, *t, *old_next, *old_parent;
502 newpar = debug_tal(to_tal_hdr_or_null(new_parent));
503 t = debug_tal(to_tal_hdr(ctx));
505 /* Save enough data to get us back if we fail! */
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
516 while (!(g = find_property(old_next, GROUP)))
517 old_next = old_next->next;
518 old_parent = g->parent_child->parent;
520 /* We can always add to old parent, becuase it has one
522 if (!add_child(old_parent, t))
531 bool tal_add_destructor_(tal_t *ctx, void (*destroy)(void *me))
533 return add_destructor_property(debug_tal(to_tal_hdr(ctx)), destroy);
536 bool tal_set_name_(tal_t *ctx, const char *name, bool literal)
538 struct tal_hdr *t = debug_tal(to_tal_hdr(ctx));
539 struct prop_hdr **prop = find_property_ptr(t, NAME);
541 /* Get rid of any old name */
543 struct name *name = (struct name *)*prop;
544 if (is_literal(&name->hdr))
547 *prop = name->hdr.next;
552 if (literal && name[0]) {
555 /* Append literal. */
556 for (p = &t->prop; *p && !is_literal(*p); p = &(*p)->next);
557 *p = (struct prop_hdr *)name;
560 if (!add_name_property(t, name))
566 const char *tal_name(const tal_t *t)
570 n = find_property(debug_tal(to_tal_hdr(t)), NAME);
574 if (is_literal(&n->hdr))
575 return (const char *)n;
579 /* Start one past first child: make stopping natural in circ. list. */
580 static struct tal_hdr *first_child(struct tal_hdr *parent)
582 struct children *child;
585 child = find_property(parent, CHILDREN);
589 /* Careful of empty group embedded in child property. */
590 if (child->group.first_child)
591 return child->group.first_child->next;
593 /* There could still be another group! */
594 group = next_group(&child->group);
595 if (group == &child->group)
598 return group->first_child->next;
601 tal_t *tal_first(const tal_t *root)
603 struct tal_hdr *c, *t = debug_tal(to_tal_hdr_or_null(root));
608 return from_tal_hdr(c);
611 tal_t *tal_next(const tal_t *root, const tal_t *prev)
613 struct tal_hdr *c, *t = debug_tal(to_tal_hdr(prev)), *top;
619 return from_tal_hdr(c);
621 top = to_tal_hdr_or_null(root);
625 /* Are we back to first child in group? */
626 group = find_property(t, GROUP);
628 return from_tal_hdr(t->next);
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);
635 /* OK, go back to parent. */
636 t = group->parent_child->parent;
642 tal_t *tal_parent(const tal_t *ctx)
650 t = debug_tal(to_tal_hdr(ctx));
652 while (!(group = find_property(t, GROUP)))
655 if (group->parent_child->parent == &null_parent.hdr)
657 return from_tal_hdr(group->parent_child->parent);
660 void *tal_realloc_(tal_t *ctx, size_t size)
662 struct tal_hdr *old_t, *t, **prev;
664 struct children *child;
666 old_t = debug_tal(to_tal_hdr(ctx));
668 t = resizefn(old_t, size + sizeof(struct tal_hdr));
670 call_error("Reallocation failure");
678 /* Fix up linked list pointer. */
679 for (prev = &t->next; *prev != old_t; prev = &(*prev)->next);
682 /* Fix up group pointer, if any. */
683 group = find_property(t, GROUP);
685 assert(group->first_child == old_t);
686 group->first_child = t;
689 /* Fix up child propertie's parent pointer. */
690 child = find_property(t, CHILDREN);
692 assert(child->parent == old_t);
696 return from_tal_hdr(debug_tal(t));
699 char *tal_strdup(const tal_t *ctx, const char *p)
701 return tal_memdup(ctx, p, strlen(p)+1);
704 char *tal_strndup(const tal_t *ctx, const char *p, size_t n)
710 ret = tal_memdup(ctx, p, n+1);
716 void *tal_memdup(const tal_t *ctx, const void *p, size_t n)
723 ret = tal_arr(ctx, char, n);
729 char *tal_asprintf(const tal_t *ctx, const char *fmt, ...)
735 ret = tal_vasprintf(ctx, fmt, ap);
741 char *tal_vasprintf(const tal_t *ctx, const char *fmt, va_list ap)
743 size_t max = strlen(fmt) * 2;
748 buf = tal_arr(tal_parent(fmt), char, max);
750 buf = tal_arr(ctx, char, max);
756 ret = vsnprintf(buf, max, fmt, ap2);
761 buf = tal_resize(buf, max *= 2);
768 void tal_set_backend(void *(*alloc_fn)(size_t size),
769 void *(*resize_fn)(void *, size_t size),
770 void (*free_fn)(void *),
771 void (*error_fn)(const char *msg))
776 resizefn = resize_fn;
783 #ifdef CCAN_TAL_DEBUG
784 static void dump_node(unsigned int indent, const struct tal_hdr *t)
787 const struct prop_hdr *p;
789 for (i = 0; i < indent; i++)
792 for (p = t->prop; p; p = p->next) {
795 struct destructor *d;
798 printf(" \"%s\"", (const char *)p);
803 c = (struct children *)p;
804 printf(" CHILDREN(%p):parent=%p,group=%p\n",
805 p, c->parent, &c->group);
807 printf(" GROUP(%p):list={%p,%p},parent_ch=%p,first=%p",
808 g, g->list.n.next, g->list.n.next,
809 g->parent_child, g->first_child);
812 g = (struct group *)p;
813 printf(" GROUP(%p):list={%p,%p},,parent_ch=%p,first=%p",
814 p, g->list.n.next, g->list.n.next,
815 g->parent_child, g->first_child);
818 d = (struct destructor *)p;
819 printf(" DESTRUCTOR(%p):fn=%p", p, d->destroy);
822 n = (struct name *)p;
823 printf(" NAME(%p):%s", p, n->name);
826 printf(" **UNKNOWN(%p):%i**", p, p->type);
832 static void tal_dump_(unsigned int level, const struct tal_hdr *t)
834 struct children *children;
839 children = find_property(t, CHILDREN);
843 group = &children->group;
847 i = group->first_child;
850 tal_dump_(level+1, i);
852 } while (i != group->first_child);
854 group = next_group(group);
855 } while (group != &children->group);
860 tal_dump_(0, &null_parent.hdr);
862 #endif /* CCAN_TAL_DEBUG */
865 static bool check_err(struct tal_hdr *t, const char *errorstr,
869 /* Try not to malloc: it may be corrupted. */
870 char msg[strlen(errorstr) + 20 + strlen(errmsg) + 1];
871 sprintf(msg, "%s:%p %s", errorstr, from_tal_hdr(t), errmsg);
877 static bool check_group(struct group *group,
878 struct tal_hdr *t, const char *errorstr);
880 static bool check_node(struct group *group,
881 struct tal_hdr *t, const char *errorstr)
884 struct name *name = NULL;
885 struct children *children = NULL;
886 struct group *gr = NULL;
888 if (t != &null_parent.hdr && !in_bounds(t))
889 return check_err(t, errorstr, "invalid pointer");
891 for (p = t->prop; p; p = p->next) {
894 return check_err(t, errorstr,
895 "has extra literal");
896 name = (struct name *)p;
899 if (p != &null_parent.c.hdr && p != &null_parent.c.group.hdr
901 return check_err(t, errorstr,
902 "has bad property pointer");
907 return check_err(t, errorstr,
909 gr = (struct group *)p;
913 return check_err(t, errorstr,
914 "has two child nodes");
915 children = (struct children *)p;
921 return check_err(t, errorstr,
923 name = (struct name *)p;
926 return check_err(t, errorstr, "has unknown property");
929 if (group && gr != group)
930 return check_err(t, errorstr, "has bad group");
933 if (!list_check(&children->group.list, errorstr))
935 gr = &children->group;
937 if (gr->first_child) {
938 if (!check_group(gr, gr->first_child, errorstr))
940 } else if (gr != &children->group) {
941 /* Empty groups should be deleted! */
942 return check_err(t, errorstr,
946 } while (gr != &children->group);
951 static bool check_group(struct group *group,
952 struct tal_hdr *t, const char *errorstr)
958 if (!check_node(group, i, errorstr))
966 bool tal_check(const tal_t *ctx, const char *errorstr)
968 struct tal_hdr *t = to_tal_hdr_or_null(ctx);
970 return check_node(NULL, t, errorstr);
973 bool tal_check(const tal_t *ctx, const char *errorstr)