From 0e34459a02e2615f50bac2767c7dce6632470946 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Sun, 18 Nov 2012 14:07:17 +1030 Subject: [PATCH] tal: new module. Signed-off-by: Rusty Russell --- ccan/tal/LICENSE | 1 + ccan/tal/_info | 103 ++++ ccan/tal/tal.c | 955 +++++++++++++++++++++++++++++++ ccan/tal/tal.h | 267 +++++++++ ccan/tal/test/run-allocfail.c | 126 ++++ ccan/tal/test/run-array.c | 39 ++ ccan/tal/test/run-destructor.c | 57 ++ ccan/tal/test/run-iter.c | 40 ++ ccan/tal/test/run-named.c | 29 + ccan/tal/test/run-overflow.c | 29 + ccan/tal/test/run-string.c | 32 ++ ccan/tal/test/run-test-backend.c | 77 +++ ccan/tal/test/run.c | 55 ++ 13 files changed, 1810 insertions(+) create mode 120000 ccan/tal/LICENSE create mode 100644 ccan/tal/_info create mode 100644 ccan/tal/tal.c create mode 100644 ccan/tal/tal.h create mode 100644 ccan/tal/test/run-allocfail.c create mode 100644 ccan/tal/test/run-array.c create mode 100644 ccan/tal/test/run-destructor.c create mode 100644 ccan/tal/test/run-iter.c create mode 100644 ccan/tal/test/run-named.c create mode 100644 ccan/tal/test/run-overflow.c create mode 100644 ccan/tal/test/run-string.c create mode 100644 ccan/tal/test/run-test-backend.c create mode 100644 ccan/tal/test/run.c diff --git a/ccan/tal/LICENSE b/ccan/tal/LICENSE new file mode 120000 index 00000000..2354d129 --- /dev/null +++ b/ccan/tal/LICENSE @@ -0,0 +1 @@ +../../licenses/BSD-MIT \ No newline at end of file diff --git a/ccan/tal/_info b/ccan/tal/_info new file mode 100644 index 00000000..2417de1c --- /dev/null +++ b/ccan/tal/_info @@ -0,0 +1,103 @@ +#include +#include +#include "config.h" + +/** + * tal - compact tree allocator routines (inspired by talloc) + * + * Tal is a hierarchical allocator; any pointer allocated by tal can + * become the parent of another allocation. When you free that parent, + * the children (and grandchildren, etc) are automatically freed. + * + * This allows you to build complex objects based on their lifetimes, eg: + * + * struct foo *X = tal(NULL, struct foo); + * X->name = tal_strdup(X, "foo"); + * + * and the pointer X->name would be a "child" of the tal context "X"; + * tal_free(X->name) would free X->name as expected, by tal_free(X) would + * free X and X->name. + * + * With an overhead of approximately 2.1 pointers per object (vs. talloc's + * 12 pointers), it's a little slower in freeing single objects, though + * comparable for allocation and freeing whole object trees). It does not + * support talloc's references or failing destructors. + * + * Example: + * #include + * #include + * #include + * #include + * + * // A structure containing a popened command. + * struct command { + * FILE *f; + * const char *command; + * }; + * + * // When struct command is freed, we also want to pclose pipe. + * static void close_cmd(struct command *cmd) + * { + * pclose(cmd->f); + * } + * + * // This function opens a writable pipe to the given command. + * static struct command *open_output_cmd(const tal_t *ctx, + * const char *fmt, ...) + * { + * va_list ap; + * struct command *cmd = tal(ctx, struct command); + * + * if (!cmd) + * return NULL; + * + * va_start(ap, fmt); + * cmd->command = tal_vasprintf(cmd, fmt, ap); + * va_end(ap); + * if (!cmd->command) { + * tal_free(cmd); + * return NULL; + * } + * + * cmd->f = popen(cmd->command, "w"); + * if (!cmd->f) { + * tal_free(cmd); + * return NULL; + * } + * tal_add_destructor(cmd, close_cmd); + * return cmd; + * } + * + * int main(int argc, char *argv[]) + * { + * struct command *cmd; + * + * if (argc != 2) + * errx(1, "Usage: %s \n", argv[0]); + * + * cmd = open_output_cmd(NULL, "%s hello", argv[1]); + * if (!cmd) + * err(1, "Running '%s hello'", argv[1]); + * fprintf(cmd->f, "This is a test\n"); + * tal_free(cmd); + * return 0; + * } + * + * License: BSD-MIT + */ +int main(int argc, char *argv[]) +{ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + printf("ccan/compiler\n"); + printf("ccan/hash\n"); + printf("ccan/likely\n"); + printf("ccan/list\n"); + printf("ccan/typesafe_cb\n"); + return 0; + } + + return 1; +} diff --git a/ccan/tal/tal.c b/ccan/tal/tal.c new file mode 100644 index 00000000..e5751305 --- /dev/null +++ b/ccan/tal/tal.c @@ -0,0 +1,955 @@ +/* Licensed under BSD-MIT - see LICENSE file for details */ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +//#define TAL_DEBUG 1 + +/* How large should grouips get? */ +#define GROUP_NODE_AVERAGE 32 + +/* 32-bit type field, first byte 0 in either endianness. */ +enum prop_type { + CHILDREN = 0x00c1d500, + GROUP = 0x00600d00, + DESTRUCTOR = 0x00de5700, + NAME = 0x00111100, +}; + +struct tal_hdr { + struct tal_hdr *next; + struct prop_hdr *prop; +}; + +struct prop_hdr { + enum prop_type type; + struct prop_hdr *next; +}; + +/* Unlike other properties, this is owned by parent, not child! */ +struct group { + struct prop_hdr hdr; /* GROUP */ + struct list_head list; /* Head for child->group, node for others. */ + /* We point to parent's children property, as it doesn't move! */ + struct children *parent_child; + struct tal_hdr *first_child; +}; + +struct children { + struct prop_hdr hdr; /* CHILDREN */ + struct tal_hdr *parent; + /* We always have one group. Others may be added. */ + struct group group; +}; + +struct destructor { + struct prop_hdr hdr; /* DESTRUCTOR */ + void (*destroy)(void *me); +}; + +struct name { + struct prop_hdr hdr; /* NAME */ + char name[]; +}; + +static struct { + struct tal_hdr hdr; + struct children c; +} null_parent = { { NULL, &null_parent.c.hdr }, + { { CHILDREN, NULL }, + &null_parent.hdr, + { { GROUP, NULL }, + { { &null_parent.c.group.list.n, + &null_parent.c.group.list.n } }, + &null_parent.c, NULL } } +}; + + +static void *(*allocfn)(size_t size) = malloc; +static void *(*resizefn)(void *, size_t size) = realloc; +static void (*freefn)(void *) = free; +static void (*errorfn)(const char *msg) = (void *)abort; + +static inline void COLD call_error(const char *msg) +{ + errorfn(msg); +} + +static bool get_destroying_bit(struct tal_hdr *next) +{ + return (size_t)next & 1; +} + +static void set_destroying_bit(struct tal_hdr **next) +{ + *next = (void *)((size_t)next | 1); +} + +static struct tal_hdr *ignore_destroying_bit(struct tal_hdr *next) +{ + return (void *)((size_t)next & ~(size_t)1); +} + +static struct group *next_group(struct group *group) +{ + return list_entry(group->list.n.next, struct group, list.n); +} + +static bool atexit_set = false; +/* This means valgrind can see leaks. */ +static void unlink_null(void) +{ + struct group *i, *next; + + for (i = next_group(&null_parent.c.group); + i != &null_parent.c.group; + i = next) { + next = next_group(i); + freefn(i); + } + null_parent.c.group.first_child = NULL; +} + +#ifndef NDEBUG +static const void *bounds_start, *bounds_end; + +static void update_bounds(const void *new) +{ + if (unlikely(!bounds_start)) + bounds_start = bounds_end = new; + else if (new < bounds_start) + bounds_start = new; + else if (new > bounds_end) + bounds_end = new; +} + +static bool in_bounds(const void *p) +{ + return !p || (p >= bounds_start && p <= bounds_end); +} +#else +static void update_bounds(const void *new) +{ +} + +static bool in_bounds(const void *p) +{ + return true; +} +#endif + +static void check_bounds(const void *p) +{ + if (!in_bounds(p)) + call_error("Not a valid header"); +} + +static struct tal_hdr *to_tal_hdr(const void *ctx) +{ + struct tal_hdr *t; + + t = (struct tal_hdr *)((char *)ctx - sizeof(struct tal_hdr)); + check_bounds(t); + check_bounds(ignore_destroying_bit(t->next)); + return t; +} + +static struct tal_hdr *to_tal_hdr_or_null(const void *ctx) +{ + if (!ctx) + return &null_parent.hdr; + return to_tal_hdr(ctx); +} + +static void *from_tal_hdr(struct tal_hdr *hdr) +{ + return hdr + 1; +} + +#ifdef TAL_DEBUG +static void *from_tal_hdr_or_null(struct tal_hdr *hdr) +{ + if (hdr == &null_parent.hdr) + return NULL; + return from_tal_hdr(hdr); +} + +static struct tal_hdr *debug_tal(struct tal_hdr *tal) +{ + tal_check(from_tal_hdr_or_null(tal), "TAL_DEBUG "); + return tal; +} +#else +static struct tal_hdr *debug_tal(struct tal_hdr *tal) +{ + return tal; +} +#endif + +static void *allocate(size_t size) +{ + void *ret; + + /* Don't hand silly sizes to malloc. */ + if (size >> (CHAR_BIT*sizeof(size) - 1)) { + call_error("allocation size overflow"); + return NULL; + } + + ret = allocfn(size); + if (!ret) + call_error("allocation failed"); + else + update_bounds(ret); + return ret; +} + +/* We carefully start all real properties with a zero byte. */ +static bool is_literal(const struct prop_hdr *prop) +{ + return ((char *)prop)[0] != 0; +} + +static struct prop_hdr **find_property_ptr(const struct tal_hdr *t, + enum prop_type type) +{ + struct prop_hdr **p; + + for (p = (struct prop_hdr **)&t->prop; *p; p = &(*p)->next) { + if (is_literal(*p)) { + if (type == NAME) + return p; + break; + } + if ((*p)->type == type) + return p; + } + return NULL; +} + +static void *find_property(const struct tal_hdr *parent, enum prop_type type) +{ + struct prop_hdr **p = find_property_ptr(parent, type); + + if (p) + return *p; + return NULL; +} + +static void init_property(struct prop_hdr *hdr, + struct tal_hdr *parent, + enum prop_type type) +{ + hdr->type = type; + hdr->next = parent->prop; + parent->prop = hdr; +} + +static struct destructor *add_destructor_property(struct tal_hdr *t, + void (*destroy)(void *)) +{ + struct destructor *prop = allocate(sizeof(*prop)); + if (prop) { + init_property(&prop->hdr, t, DESTRUCTOR); + prop->destroy = destroy; + } + return prop; +} + +static struct name *add_name_property(struct tal_hdr *t, const char *name) +{ + struct name *prop; + + prop = allocate(sizeof(*prop) + strlen(name) + 1); + if (prop) { + init_property(&prop->hdr, t, NAME); + strcpy(prop->name, name); + } + return prop; +} + +static void init_group_property(struct group *group, + struct children *parent_child, + struct tal_hdr *child) +{ + init_property(&group->hdr, child, GROUP); + group->parent_child = parent_child; + group->first_child = child; +} + +static struct children *add_child_property(struct tal_hdr *parent, + struct tal_hdr *child) +{ + struct children *prop = allocate(sizeof(*prop)); + if (prop) { + init_property(&prop->hdr, parent, CHILDREN); + prop->parent = parent; + + init_group_property(&prop->group, prop, child); + list_head_init(&prop->group.list); + } + return prop; +} + +static struct group *add_group_property(struct tal_hdr *child, + struct children *parent_child) +{ + struct group *prop = allocate(sizeof(*prop)); + if (prop) + init_group_property(prop, parent_child, child); + return prop; +} + +static bool add_child(struct tal_hdr *parent, struct tal_hdr *child) +{ + struct group *group; + struct children *children = find_property(parent, CHILDREN); + + if (!children) { + children = add_child_property(parent, child); + if (!children) + return false; + children->group.list.n.next = children->group.list.n.prev + = &children->group.list.n; + + /* Child links to itself. */ + child->next = child; + return true; + } + + /* Last one (may be children->group itself). */ + group = next_group(&children->group); + + /* Empty group can happen: null_parent, or all children freed. */ + if (unlikely(!group->first_child)) { + assert(group == &children->group); + /* This hits on first child appended to null parent. */ + if (unlikely(!atexit_set)) { + atexit(unlink_null); + atexit_set = true; + } + /* Link group into this child, make it the first one. */ + group->hdr.next = child->prop; + child->prop = &group->hdr; + group->first_child = child; + + /* Child links to itself. */ + child->next = child; + return true; + } + + if (unlikely(hash_pointer(child, 0) % GROUP_NODE_AVERAGE == 0)) { + struct group *newgroup; + + newgroup = add_group_property(child, children); + if (likely(newgroup)) { + list_add(&children->group.list, &newgroup->list.n); + + /* Child links to itself. */ + child->next = child; + return true; + } + /* Fall through: on allocation failure reuse old group. */ + } + + /* We insert after head, otherwise we'd need to find end. */ + child->next = group->first_child->next; + group->first_child->next = child; + return true; +} + +static void del_tree(struct tal_hdr *t) +{ + struct prop_hdr **prop, *p, *next; + + /* Already being destroyed? Don't loop. */ + if (unlikely(get_destroying_bit(t->next))) + return; + + set_destroying_bit(&t->next); + + /* Carefully call destructors, removing as we go. */ + while ((prop = find_property_ptr(t, DESTRUCTOR))) { + struct destructor *d = (struct destructor *)*prop; + d->destroy(from_tal_hdr(t)); + *prop = d->hdr.next; + freefn(d); + } + + /* Now free children and groups. */ + prop = find_property_ptr(t, CHILDREN); + if (prop) { + struct children *c = (struct children *)*prop; + struct group *group, *next; + + group = &c->group; + do { + next = next_group(group); + if (group->first_child) { + struct tal_hdr *i, *nextc; + + i = group->first_child; + do { + nextc = i->next; + del_tree(i); + i = nextc; + } while (i != group->first_child); + } + if (group != &c->group) + freefn(group); + group = next; + } while (group != &c->group); + } + + /* Finally free our properties (groups are freed by parent). */ + for (p = t->prop; p && !is_literal(p); p = next) { + next = p->next; + if (p->type != GROUP) + freefn(p); + } + freefn(t); +} + +void *tal_alloc_(const tal_t *ctx, size_t size, bool clear) +{ + struct tal_hdr *child, *parent = debug_tal(to_tal_hdr_or_null(ctx)); + + child = allocate(sizeof(struct tal_hdr) + size); + if (!child) + return NULL; + if (clear) + memset(from_tal_hdr(child), 0, size); + child->prop = NULL; + if (!add_child(parent, child)) { + freefn(child); + return NULL; + } + debug_tal(parent); + return from_tal_hdr(debug_tal(child)); +} + +/* Update back ptrs, etc, as required. + * May return pointer to parent. */ +static struct tal_hdr *remove_node(struct tal_hdr *t) +{ + struct prop_hdr **prop; + struct tal_hdr *prev; + + /* Loop around to find previous node. */ + for (prev = t->next; prev->next != t; prev = prev->next); + + /* Unlink ourselves. */ + prev->next = t->next; + + /* Are we the node with the group property? */ + prop = find_property_ptr(t, GROUP); + if (prop) { + struct group *group = (struct group *)*prop; + + /* Are we the only one? */ + if (prev == t) { + struct children *c = group->parent_child; + /* Is this the group embedded in the child property? */ + if (group == &c->group) { + group->first_child = NULL; + } else { + /* Empty group, so free it. */ + list_del_from(&c->group.list, &group->list.n); + *prop = group->hdr.next; + freefn(group); + } + return c->parent; + } else { + /* Move property to next node. */ + group->first_child = t->next; + + *prop = group->hdr.next; + group->hdr.next = t->next->prop; + t->next->prop = &group->hdr; + } + } + return NULL; +} + +void tal_free(const tal_t *ctx) +{ + struct tal_hdr *t; + + if (!ctx) + return; + + t = debug_tal(to_tal_hdr(ctx)); + remove_node(t); + del_tree(t); +} + +void *tal_steal_(const tal_t *new_parent, const tal_t *ctx) +{ + if (ctx) { + struct tal_hdr *newpar, *t, *old_next, *old_parent; + + newpar = debug_tal(to_tal_hdr_or_null(new_parent)); + t = debug_tal(to_tal_hdr(ctx)); + + /* Save enough data to get us back if we fail! */ + old_next = t->next; + + /* Unlink it from old parent. */ + old_parent = remove_node(t); + if (unlikely(!add_child(newpar, t))) { + /* If we were last child, parent returned by + * remove_node, otherwise search old siblings + * for it. */ + if (!old_parent) { + struct group *g; + while (!(g = find_property(old_next, GROUP))) + old_next = old_next->next; + old_parent = g->parent_child->parent; + } + /* We can always add to old parent, becuase it has one + * group already. */ + if (!add_child(old_parent, t)) + abort(); + return NULL; + } + debug_tal(newpar); + } + return (void *)ctx; +} + +bool tal_add_destructor_(tal_t *ctx, void (*destroy)(void *me)) +{ + return add_destructor_property(debug_tal(to_tal_hdr(ctx)), destroy); +} + +bool tal_set_name_(tal_t *ctx, const char *name, bool literal) +{ + struct tal_hdr *t = debug_tal(to_tal_hdr(ctx)); + struct prop_hdr **prop = find_property_ptr(t, NAME); + + /* Get rid of any old name */ + if (prop) { + struct name *name = (struct name *)*prop; + if (is_literal(&name->hdr)) + *prop = NULL; + else { + *prop = name->hdr.next; + freefn(name); + } + } + + if (literal && name[0]) { + struct prop_hdr **p; + + /* Append literal. */ + for (p = &t->prop; *p && !is_literal(*p); p = &(*p)->next); + *p = (struct prop_hdr *)name; + return true; + } + if (!add_name_property(t, name)) + return false; + debug_tal(t); + return true; +} + +const char *tal_name(const tal_t *t) +{ + struct name *n; + + n = find_property(debug_tal(to_tal_hdr(t)), NAME); + if (!n) + return NULL; + + if (is_literal(&n->hdr)) + return (const char *)n; + return n->name; +} + +/* Start one past first child: make stopping natural in circ. list. */ +static struct tal_hdr *first_child(struct tal_hdr *parent) +{ + struct children *child; + struct group *group; + + child = find_property(parent, CHILDREN); + if (!child) + return NULL; + + /* Careful of empty group embedded in child property. */ + if (child->group.first_child) + return child->group.first_child->next; + + /* There could still be another group! */ + group = next_group(&child->group); + if (group == &child->group) + return NULL; + + return group->first_child->next; +} + +tal_t *tal_first(const tal_t *root) +{ + struct tal_hdr *c, *t = debug_tal(to_tal_hdr_or_null(root)); + + c = first_child(t); + if (!c) + return NULL; + return from_tal_hdr(c); +} + +tal_t *tal_next(const tal_t *root, const tal_t *prev) +{ + struct tal_hdr *c, *t = debug_tal(to_tal_hdr(prev)), *top; + struct group *group; + + /* Children? */ + c = first_child(t); + if (c) + return from_tal_hdr(c); + + top = to_tal_hdr_or_null(root); + do { + struct group *next; + + /* Are we back to first child in group? */ + group = find_property(t, GROUP); + if (!group) + return from_tal_hdr(t->next); + + /* Last group is one inside children property. */ + next = next_group(group); + if (next != &group->parent_child->group) + return from_tal_hdr(next->first_child->next); + + /* OK, go back to parent. */ + t = group->parent_child->parent; + } while (t != top); + + return NULL; +} + +tal_t *tal_parent(const tal_t *ctx) +{ + struct group *group; + struct tal_hdr *t = debug_tal(to_tal_hdr(ctx)); + + while (!(group = find_property(t, GROUP))) + t = t->next; + + if (group->parent_child->parent == &null_parent.hdr) + return NULL; + return from_tal_hdr(group->parent_child->parent); +} + +void *tal_realloc_(tal_t *ctx, size_t size) +{ + struct tal_hdr *old_t, *t, **prev; + struct group *group; + struct children *child; + + old_t = debug_tal(to_tal_hdr(ctx)); + + t = resizefn(old_t, size + sizeof(struct tal_hdr)); + if (!t) { + call_error("Reallocation failure"); + tal_free(old_t); + return NULL; + } + if (t == old_t) + return ctx; + update_bounds(t); + + /* Fix up linked list pointer. */ + for (prev = &t->next; *prev != old_t; prev = &(*prev)->next); + *prev = t; + + /* Fix up group pointer, if any. */ + group = find_property(t, GROUP); + if (group) { + assert(group->first_child == old_t); + group->first_child = t; + } + + /* Fix up child propertie's parent pointer. */ + child = find_property(t, CHILDREN); + if (child) { + assert(child->parent == old_t); + child->parent = t; + } + + return from_tal_hdr(debug_tal(t)); +} + +char *tal_strdup(const tal_t *ctx, const char *p) +{ + return tal_memdup(ctx, p, strlen(p)+1); +} + +char *tal_strndup(const tal_t *ctx, const char *p, size_t n) +{ + char *ret; + + if (strlen(p) < n) + n = strlen(p); + ret = tal_memdup(ctx, p, n+1); + if (ret) + ret[n] = '\0'; + return ret; +} + +void *tal_memdup(const tal_t *ctx, const void *p, size_t n) +{ + void *ret = tal_arr(ctx, char, n); + if (ret) + memcpy(ret, p, n); + return ret; +} + +char *tal_asprintf(const tal_t *ctx, const char *fmt, ...) +{ + va_list ap; + char *ret; + + va_start(ap, fmt); + ret = tal_vasprintf(ctx, fmt, ap); + va_end(ap); + + return ret; +} + +char *tal_vasprintf(const tal_t *ctx, const char *fmt, va_list ap) +{ + size_t max = strlen(fmt) * 2; + char *buf = tal_arr(ctx, char, max); + int ret; + + while (buf) { + va_list ap2; + + va_copy(ap2, ap); + ret = vsnprintf(buf, max, fmt, ap2); + va_end(ap2); + + if (ret < max) + break; + buf = tal_resize(buf, max *= 2); + } + return buf; +} + +void tal_set_backend(void *(*alloc_fn)(size_t size), + void *(*resize_fn)(void *, size_t size), + void (*free_fn)(void *), + void (*error_fn)(const char *msg)) +{ + if (alloc_fn) + allocfn = alloc_fn; + if (resize_fn) + resizefn = resize_fn; + if (free_fn) + freefn = free_fn; + if (error_fn) + errorfn = error_fn; +} + +#ifdef CCAN_TAL_DEBUG +static void dump_node(unsigned int indent, const struct tal_hdr *t) +{ + unsigned int i; + const struct prop_hdr *p; + + for (i = 0; i < indent; i++) + printf(" "); + printf("%p", t); + for (p = t->prop; p; p = p->next) { + struct group *g; + struct children *c; + struct destructor *d; + struct name *n; + if (is_literal(p)) { + printf(" \"%s\"", (const char *)p); + break; + } + switch (p->type) { + case CHILDREN: + c = (struct children *)p; + printf(" CHILDREN(%p):parent=%p,group=%p\n", + p, c->parent, &c->group); + g = &c->group; + printf(" GROUP(%p):list={%p,%p},parent_ch=%p,first=%p", + g, g->list.n.next, g->list.n.next, + g->parent_child, g->first_child); + break; + case GROUP: + g = (struct group *)p; + printf(" GROUP(%p):list={%p,%p},,parent_ch=%p,first=%p", + p, g->list.n.next, g->list.n.next, + g->parent_child, g->first_child); + break; + case DESTRUCTOR: + d = (struct destructor *)p; + printf(" DESTRUCTOR(%p):fn=%p", p, d->destroy); + break; + case NAME: + n = (struct name *)p; + printf(" NAME(%p):%s", p, n->name); + break; + default: + printf(" **UNKNOWN(%p):%i**", p, p->type); + } + } + printf("\n"); +} + +static void tal_dump_(unsigned int level, const struct tal_hdr *t) +{ + struct children *children; + struct group *group; + + dump_node(level, t); + + children = find_property(t, CHILDREN); + if (!children) + return; + + group = &children->group; + do { + struct tal_hdr *i; + + i = group->first_child; + if (i) { + do { + tal_dump_(level+1, i); + i = i->next; + } while (i != group->first_child); + } + group = next_group(group); + } while (group != &children->group); +} + +void tal_dump(void) +{ + tal_dump_(0, &null_parent.hdr); +} +#endif /* CCAN_TAL_DEBUG */ + +#ifndef NDEBUG +static bool check_err(struct tal_hdr *t, const char *errorstr, + const char *errmsg) +{ + if (errorstr) { + /* Try not to malloc: it may be corrupted. */ + char msg[strlen(errorstr) + 20 + strlen(errmsg) + 1]; + sprintf(msg, "%s:%p %s", errorstr, from_tal_hdr(t), errmsg); + call_error(msg); + } + return false; +} + +static bool check_group(struct group *group, + struct tal_hdr *t, const char *errorstr); + +static bool check_node(struct group *group, + struct tal_hdr *t, const char *errorstr) +{ + struct prop_hdr *p; + struct name *name = NULL; + struct children *children = NULL; + struct group *gr = NULL; + + if (t != &null_parent.hdr && !in_bounds(t)) + return check_err(t, errorstr, "invalid pointer"); + + for (p = t->prop; p; p = p->next) { + if (is_literal(p)) { + if (name) + return check_err(t, errorstr, + "has extra literal"); + name = (struct name *)p; + break; + } + if (p != &null_parent.c.hdr && !in_bounds(p)) + return check_err(t, errorstr, + "has bad property pointer"); + + switch (p->type) { + case GROUP: + if (gr) + return check_err(t, errorstr, + "has two groups"); + gr = (struct group *)p; + break; + case CHILDREN: + if (children) + return check_err(t, errorstr, + "has two child nodes"); + children = (struct children *)p; + break; + case DESTRUCTOR: + break; + case NAME: + if (name) + return check_err(t, errorstr, + "has two names"); + name = (struct name *)p; + break; + default: + return check_err(t, errorstr, "has unknown property"); + } + } + if (group && gr != group) + return check_err(t, errorstr, "has bad group"); + + if (children) { + if (!list_check(&children->group.list, errorstr)) + return false; + gr = &children->group; + do { + if (gr->first_child) { + if (!check_group(gr, gr->first_child, errorstr)) + return false; + } else if (gr != &children->group) { + /* Empty groups should be deleted! */ + return check_err(t, errorstr, + "has empty group"); + } + gr = next_group(gr); + } while (gr != &children->group); + } + return true; +} + +static bool check_group(struct group *group, + struct tal_hdr *t, const char *errorstr) +{ + struct tal_hdr *i; + + i = t; + do { + if (!check_node(group, i, errorstr)) + return false; + group = NULL; + i = i->next; + } while (i != t); + return true; +} + +bool tal_check(const tal_t *ctx, const char *errorstr) +{ + struct tal_hdr *t = to_tal_hdr_or_null(ctx); + + return check_node(NULL, t, errorstr); +} +#else /* NDEBUG */ +bool tal_check(const tal_t *ctx, const char *errorstr) +{ + return true; +} +#endif diff --git a/ccan/tal/tal.h b/ccan/tal/tal.h new file mode 100644 index 00000000..d511e88a --- /dev/null +++ b/ccan/tal/tal.h @@ -0,0 +1,267 @@ +/* Licensed under BSD-MIT - see LICENSE file for details */ +#ifndef CCAN_TAL_H +#define CCAN_TAL_H +#include "config.h" +#include +#include +#include +#include +#include +#include + +/** + * tal_t - convenient alias for void to mark tal pointers. + * + * Since any pointer can be a tal-allocated pointer, it's often + * useful to use this typedef to mark them explicitly. + */ +typedef void tal_t; + +/** + * tal - basic allocator function + * @ctx: NULL, or tal allocated object to be parent. + * @type: the type to allocate. + * + * Allocates a specific type, with a given parent context. + */ +#define tal(ctx, type) tal_arr((ctx), type, 1) + +/** + * talz - zeroing allocator function + * @ctx: NULL, or tal allocated object to be parent. + * @type: the type to allocate. + * + * Equivalent to tal() followed by memset() to zero. + */ +#define talz(ctx, type) tal_arrz((ctx), type, 1) + +/** + * tal_free - free a tal-allocated pointer. + * @p: NULL, or tal allocated object to free. + * + * This calls the destructors for p (if any), then does the same for all its + * children (recursively) before finally freeing the memory. + */ +void tal_free(const tal_t *p); + +/** + * tal_arr - allocate an array of objects. + * @ctx: NULL, or tal allocated object to be parent. + * @type: the type to allocate. + * @count: the number to allocate. + */ +#define tal_arr(ctx, type, count) \ + ((type *)tal_alloc_((ctx), tal_sizeof_(sizeof(type), (count)), false)) + +/** + * tal_arrz - allocate an array of zeroed objects. + * @ctx: NULL, or tal allocated object to be parent. + * @type: the type to allocate. + * @count: the number to allocate. + */ +#define tal_arrz(ctx, type, count) \ + ((type *)tal_alloc_((ctx), tal_sizeof_(sizeof(type), (count)), true)) + +/** + * tal_resize - enlarge or reduce a tal_arr(z). + * @p: The tal allocated array to resize. + * @count: the number to allocate. + * + * This returns the new pointer, or NULL (and destroys the old one) + * on failure. + */ +#define tal_resize(p, count) \ + ((tal_typeof(p) tal_realloc_((p), tal_sizeof_(sizeof(*p), (count))))) + +/** + * tal_steal - change the parent of a tal-allocated pointer. + * @ctx: The new parent. + * @ptr: The tal allocated object to move. + * + * This may need to perform an allocation, in which case it may fail; thus + * it can return NULL, otherwise returns @ptr. + * + * Weird macro avoids gcc's 'warning: value computed is not used'. + */ +#if HAVE_STATEMENT_EXPR +#define tal_steal(ctx, ptr) \ + ({ (tal_typeof(ptr) tal_steal_((ctx),(ptr))); }) +#else +#define tal_steal(ctx, ptr) \ + (tal_typeof(ptr) tal_steal_((ctx),(ptr))) +#endif + +/** + * tal_add_destructor - add a callback function when this context is destroyed. + * @ptr: The tal allocated object. + * @function: the function to call before it's freed. + */ +#define tal_add_destructor(ptr, function) \ + tal_add_destructor_((ptr), typesafe_cb(void, void *, (function), (ptr))) + +/** + * tal_set_name - attach a name to a tal pointer. + * @ptr: The tal allocated object. + * @name: The name to use. + * + * The name is copied, unless we're certain it's a string literal. + */ +#define tal_set_name(ptr, name) \ + tal_set_name_((ptr), (name), TAL_IS_LITERAL(name)) + +/** + * tal_name - get the name for a tal pointer. + * @ptr: The tal allocated object. + * + * Returns NULL if no name has been set. + */ +const char *tal_name(const tal_t *ptr); + +/** + * tal_first - get the first tal object child. + * @root: The tal allocated object to start with, or NULL. + * + * Returns NULL if there are no children. + */ +tal_t *tal_first(const tal_t *root); + +/** + * tal_next - get the next tal object child. + * @root: The tal allocated object to start with, or NULL. + * @prev: The return value from tal_first or tal_next. + * + * Returns NULL if there are no more children. This should be safe to + * call on an altering tree unless @prev is no longer a descendent of + * @root. + */ +tal_t *tal_next(const tal_t *root, const tal_t *prev); + +/** + * tal_parent - get the parent of a tal object. + * @ctx: The tal allocated object. + * + * Returns the parent, which may be NULL. + */ +tal_t *tal_parent(const tal_t *ctx); + +/** + * tal_memdup - duplicate memory. + * @ctx: NULL, or tal allocated object to be parent. + * @p: the memory to copy + * @n: the number of bytes. + */ +void *tal_memdup(const tal_t *ctx, const void *p, size_t n); + +/** + * tal_strdup - duplicate a string. + * @ctx: NULL, or tal allocated object to be parent. + * @p: the string to copy + */ +char *tal_strdup(const tal_t *ctx, const char *p); + +/** + * tal_strndup - duplicate a limited amount of a string. + * @ctx: NULL, or tal allocated object to be parent. + * @p: the string to copy + * @n: the maximum length to copy. + * + * Always gives a nul-terminated string, with strlen() <= @n. + */ +char *tal_strndup(const tal_t *ctx, const char *p, size_t n); + +/** + * tal_asprintf - allocate a formatted string + * @ctx: NULL, or tal allocated object to be parent. + * @fmt: the printf-style format. + */ +char *tal_asprintf(const tal_t *ctx, const char *fmt, ...) PRINTF_FMT(2,3); + +/** + * tal_vasprintf - allocate a formatted string (va_list version) + * @ctx: NULL, or tal allocated object to be parent. + * @fmt: the printf-style format. + * @va: the va_list containing the format args. + */ +char *tal_vasprintf(const tal_t *ctx, const char *fmt, va_list ap) + PRINTF_FMT(2,0); + + +/** + * tal_set_backend - set the allocation or error functions to use + * @alloc_fn: allocator or NULL (default is malloc) + * @resize_fn: re-allocator or NULL (default is realloc) + * @free_fn: free function or NULL (default is free) + * @error_fn: called on errors or NULL (default is abort) + * + * The defaults are set up so tal functions never return NULL, but you + * can override erorr_fn to change that. error_fn can return, and is + * called if alloc_fn or resize_fn fail. + * + * If any parameter is NULL, that function is unchanged. + */ +void tal_set_backend(void *(*alloc_fn)(size_t size), + void *(*resize_fn)(void *, size_t size), + void (*free_fn)(void *), + void (*error_fn)(const char *msg)); + + +/** + * tal_check - set the allocation or error functions to use + * @ctx: a tal context, or NULL. + * @errorstr: a string to prepend calls to error_fn, or NULL. + * + * This sanity-checks a tal tree (unless NDEBUG is defined, in which case + * it simply returns true). If errorstr is not null, error_fn is called + * when a problem is found, otherwise it is not. + */ +bool tal_check(const tal_t *ctx, const char *errorstr); + +#ifdef CCAN_TAL_DEBUG +/** + * tal_dump - dump entire tal tree. + * + * This is a helper for debugging tal itself, which dumps all the tal internal + * state. + */ +void tal_dump(void); +#endif + +/* Internal support functions */ +#if HAVE_BUILTIN_CONSTANT_P +#define TAL_IS_LITERAL(str) __builtin_constant_p(str) +#else +#define TAL_IS_LITERAL(str) (sizeof(&*(str)) != sizeof(char *)) +#endif + +bool tal_set_name_(tal_t *ctx, const char *name, bool literal); + +static inline size_t tal_sizeof_(size_t size, size_t count) +{ + /* Multiplication wrap */ + if (count && unlikely(size * count / size != count)) + return (size_t)-1024; + + size *= count; + + /* Make sure we don't wrap adding header. */ + if (size > (size_t)-1024) + return (size_t)-1024; + + return size; +} + +#if HAVE_TYPEOF +#define tal_typeof(ptr) (__typeof__(ptr)) +#else +#define tal_typeof(ptr) +#endif + +void *tal_alloc_(const tal_t *ctx, size_t bytes, bool clear); + +tal_t *tal_steal_(const tal_t *new_parent, const tal_t *t); + +void *tal_realloc_(tal_t *ctx, size_t size); + +bool tal_add_destructor_(tal_t *ctx, void (*destroy)(void *me)); + +#endif /* CCAN_TAL_H */ diff --git a/ccan/tal/test/run-allocfail.c b/ccan/tal/test/run-allocfail.c new file mode 100644 index 00000000..dd6abff4 --- /dev/null +++ b/ccan/tal/test/run-allocfail.c @@ -0,0 +1,126 @@ +#include +#include +#include + +static int alloc_count, when_to_fail, err_count; +static bool stealing; + +static void *failing_alloc(size_t len) +{ + if (alloc_count++ == when_to_fail) + return NULL; + /* once we've failed once, it shouldn't ask again (steal can though). */ + assert(stealing || alloc_count <= when_to_fail); + + return malloc(len); +} + +static void nofail_on_error(const char *msg) +{ + diag("ERROR: %s", msg); + err_count++; +} + +static void destroy_p(void *p) +{ +} + +int main(void) +{ + void *p, *c1, *c2; + bool success; + + plan_tests(21); + + tal_set_backend(failing_alloc, NULL, NULL, nofail_on_error); + + /* Fail at each possible point in an allocation. */ + when_to_fail = err_count = 0; + do { + alloc_count = 0; + p = tal(NULL, char); + when_to_fail++; + } while (!p); + ok1(alloc_count >= 1); + ok1(when_to_fail > 1); + ok1(err_count == when_to_fail - 1); + + /* Do it again. */ + when_to_fail = err_count = 0; + do { + alloc_count = 0; + c1 = tal(p, char); + when_to_fail++; + } while (!c1); + ok1(alloc_count >= 1); + ok1(when_to_fail > 1); + ok1(err_count == when_to_fail - 1); + + /* Now for second child. */ + when_to_fail = err_count = 0; + do { + alloc_count = 0; + c2 = tal(p, char); + when_to_fail++; + } while (!c2); + ok1(alloc_count >= 1); + ok1(when_to_fail > 1); + /* Note: adding a child will fall through if group alloc fails. */ + ok1 (err_count == when_to_fail - 1 || err_count == when_to_fail); + + /* Now while adding a destructor. */ + when_to_fail = err_count = 0; + do { + alloc_count = 0; + success = tal_add_destructor(p, destroy_p); + when_to_fail++; + } while (!success); + ok1(alloc_count >= 1); + ok1(when_to_fail > 1); + ok1(err_count == when_to_fail - 1); + + /* Now while adding a name. */ + when_to_fail = err_count = 0; + do { + const char name[] = "some name"; + alloc_count = 0; + success = tal_set_name(p, name); + when_to_fail++; + } while (!success); + ok1(alloc_count >= 1); + ok1(when_to_fail > 1); + ok1(err_count == when_to_fail - 1); + + /* Now while stealing. */ + stealing = true; + when_to_fail = err_count = 0; + do { + alloc_count = 0; + success = tal_steal(c2, c1) != NULL; + when_to_fail++; + } while (!success); + ok1(alloc_count >= 1); + ok1(when_to_fail > 1); + ok1(err_count == when_to_fail - 1); + + /* Now stealing with more children (more coverage). */ + when_to_fail = 1000; + (void)tal(p, char); + c1 = tal(p, char); + c2 = tal(p, char); + (void)tal(p, char); + + /* Now steal again. */ + when_to_fail = err_count = 0; + do { + alloc_count = 0; + success = tal_steal(c2, c1) != NULL; + when_to_fail++; + } while (!success); + ok1(alloc_count >= 1); + ok1(when_to_fail > 1); + ok1(err_count == when_to_fail - 1); + + tal_free(p); + return exit_status(); +} diff --git a/ccan/tal/test/run-array.c b/ccan/tal/test/run-array.c new file mode 100644 index 00000000..53392da3 --- /dev/null +++ b/ccan/tal/test/run-array.c @@ -0,0 +1,39 @@ +#include +#include +#include + +int main(void) +{ + char *parent, *c[4]; + int i; + + plan_tests(9); + + parent = tal(NULL, char); + ok1(parent); + + /* Zeroing allocations. */ + for (i = 0; i < 4; i++) { + c[i] = talz(parent, char); + ok1(*c[i] == '\0'); + tal_free(c[i]); + } + + /* Array allocation. */ + for (i = 0; i < 4; i++) { + c[i] = tal_arr(parent, char, 4); + strcpy(c[i], "abc"); + tal_free(c[i]); + } + + /* Zeroing array allocation. */ + for (i = 0; i < 4; i++) { + c[i] = tal_arrz(parent, char, 4); + ok1(!c[i][0] && !c[i][1] && !c[i][2] && !c[i][3]); + strcpy(c[i], "abc"); + tal_free(c[i]); + } + tal_free(parent); + + return exit_status(); +} diff --git a/ccan/tal/test/run-destructor.c b/ccan/tal/test/run-destructor.c new file mode 100644 index 00000000..9d3a94e6 --- /dev/null +++ b/ccan/tal/test/run-destructor.c @@ -0,0 +1,57 @@ +#include +#include +#include + +static char *parent, *child; +static int destroy_count; + +/* Parent gets destroyed first. */ +static void destroy_parent(char *p) +{ + ok1(p == parent); + ok1(destroy_count == 0); + /* Can still access child. */ + *child = '1'; + destroy_count++; +} + +static void destroy_child(char *p) +{ + ok1(p == child); + ok1(destroy_count == 1); + /* Can still access parent (though destructor has been called). */ + *parent = '1'; + destroy_count++; +} + +static void destroy_inc(char *p) +{ + destroy_count++; +} + +int main(void) +{ + char *child2; + + plan_tests(12); + + parent = tal(NULL, char); + child = tal(parent, char); + ok1(tal_add_destructor(parent, destroy_parent)); + ok1(tal_add_destructor(child, destroy_child)); + + tal_free(parent); + ok1(destroy_count == 2); + + parent = tal(NULL, char); + child = tal(parent, char); + child2 = tal(parent, char); + ok1(tal_add_destructor(parent, destroy_inc)); + ok1(tal_add_destructor(parent, destroy_inc)); + ok1(tal_add_destructor(child, destroy_inc)); + ok1(tal_add_destructor(child2, destroy_inc)); + tal_free(parent); + ok1(destroy_count == 6); + + return exit_status(); +} diff --git a/ccan/tal/test/run-iter.c b/ccan/tal/test/run-iter.c new file mode 100644 index 00000000..6fc75371 --- /dev/null +++ b/ccan/tal/test/run-iter.c @@ -0,0 +1,40 @@ +#include +#include +#include + +#define NUM 1000 + +int main(void) +{ + char *p[NUM], *iter; + int i; + + plan_tests(NUM + 1 + NUM); + + /* Create a random tree, but make sure we get multiple + * top-level groups! */ + for (i = 0; i < NUM; i++) { + p[i] = tal(NULL, char); + *p[i] = '0'; + if (next_group(&null_parent.c.group) != &null_parent.c.group) + break; + } + for (i++; i < NUM; i++) { + p[i] = tal(p[rand() % i], char); + *p[i] = '0'; + } + + i = 0; + for (iter = tal_first(NULL); iter; iter = tal_next(NULL, iter)) { + i++; + ok1(*iter == '0'); + *iter = '1'; + } + ok1(i == NUM); + + for (i = NUM-1; i >= 0; i--) { + ok1(*p[i] == '1'); + tal_free(p[i]); + } + return exit_status(); +} diff --git a/ccan/tal/test/run-named.c b/ccan/tal/test/run-named.c new file mode 100644 index 00000000..d2c9b9e1 --- /dev/null +++ b/ccan/tal/test/run-named.c @@ -0,0 +1,29 @@ +#include +#include +#include + +int main(void) +{ + int *p; + char name[] = "test name"; + + plan_tests(5); + + p = tal(NULL, int); + ok1(tal_name(p) == NULL); + + tal_set_name(p, "some literal"); + ok1(strcmp(tal_name(p), "some literal") == 0); + + tal_set_name(p, name); + ok1(strcmp(tal_name(p), name) == 0); + /* You can't reuse my pointer though! */ + ok1(tal_name(p) != name); + + tal_set_name(p, "some other literal"); + ok1(strcmp(tal_name(p), "some other literal") == 0); + + tal_free(p); + + return exit_status(); +} diff --git a/ccan/tal/test/run-overflow.c b/ccan/tal/test/run-overflow.c new file mode 100644 index 00000000..dedeba3d --- /dev/null +++ b/ccan/tal/test/run-overflow.c @@ -0,0 +1,29 @@ +#include +#include +#include + +static int error_count; + +static void my_error(const char *msg) +{ + error_count++; + ok1(strstr(msg, "overflow")); +} + +int main(void) +{ + void *p; + + plan_tests(6); + + tal_set_backend(NULL, NULL, NULL, my_error); + + p = tal_arr(NULL, int, (size_t)-1); + ok1(!p); + ok1(error_count == 1); + + p = tal_arr(NULL, char, (size_t)-2); + ok1(!p); + ok1(error_count == 2); + return exit_status(); +} diff --git a/ccan/tal/test/run-string.c b/ccan/tal/test/run-string.c new file mode 100644 index 00000000..43a99da4 --- /dev/null +++ b/ccan/tal/test/run-string.c @@ -0,0 +1,32 @@ +#include +#include +#include + +int main(void) +{ + char *parent, *c; + + plan_tests(9); + + parent = tal(NULL, char); + ok1(parent); + + c = tal_strdup(parent, "hello"); + ok1(strcmp(c, "hello") == 0); + ok1(tal_parent(c) == parent); + + c = tal_strndup(parent, "hello", 3); + ok1(strcmp(c, "hel") == 0); + ok1(tal_parent(c) == parent); + + c = tal_memdup(parent, "hello", 6); + ok1(strcmp(c, "hello") == 0); + ok1(tal_parent(c) == parent); + + c = tal_asprintf(parent, "hello %s", "there"); + ok1(strcmp(c, "hello there") == 0); + ok1(tal_parent(c) == parent); + tal_free(parent); + + return exit_status(); +} diff --git a/ccan/tal/test/run-test-backend.c b/ccan/tal/test/run-test-backend.c new file mode 100644 index 00000000..2f9770a0 --- /dev/null +++ b/ccan/tal/test/run-test-backend.c @@ -0,0 +1,77 @@ +#include +#include + +/* Make sure it always uses our allocation/resize/free fns! */ +static bool my_alloc_called; + +static void *my_alloc(size_t len) +{ + my_alloc_called = true; + return (char *)malloc(len + 16) + 16; +} + +static void my_free(void *p) +{ + return free((char *)p - 16); +} + +static void *my_realloc(void *old, size_t new_size) +{ + return (char *)realloc((char *)old - 16, new_size + 16) + 16; +} + +#define free ((void (*)(void *))abort) +#define malloc ((void *(*)(size_t))abort) +#define realloc ((void *(*)(void *, size_t))abort) + +#include +#include +#include + +#define NUM_ALLOCS 1000 + +static void destroy_p(void *p) +{ +} + +int main(void) +{ + void *p, *c[NUM_ALLOCS]; + int i; + char *name; + + /* Mostly we rely on the allocator (or valgrind) crashing. */ + plan_tests(1); + + tal_set_backend(my_alloc, my_realloc, my_free, NULL); + + p = tal(NULL, char); + ok1(my_alloc_called); + + /* Adding properties makes us allocated. */ + tal_add_destructor(p, destroy_p); + + tal_set_name(p, "test"); + name = tal_asprintf(NULL, "test2"); + tal_set_name(p, name); + /* makes us free old name */ + tal_set_name(p, name); + tal_free(name); + + /* Add lots of children. */ + for (i = 0; i < NUM_ALLOCS; i++) + c[i] = tal(p, char); + + /* Now steal a few. */ + for (i = 1; i < NUM_ALLOCS / 2; i++) + tal_steal(c[0], c[i]); + + /* Now free individual ones.. */ + for (i = NUM_ALLOCS / 2; i < NUM_ALLOCS; i++) + tal_free(c[i]); + + /* Finally, free the parent. */ + tal_free(p); + + return exit_status(); +} diff --git a/ccan/tal/test/run.c b/ccan/tal/test/run.c new file mode 100644 index 00000000..69ffa2d3 --- /dev/null +++ b/ccan/tal/test/run.c @@ -0,0 +1,55 @@ +#include +#include +#include + +int main(void) +{ + char *parent, *c[4], *p; + int i, j; + + plan_tests(10); + + parent = tal(NULL, char); + ok1(parent); + + for (i = 0; i < 4; i++) + c[i] = tal(parent, char); + + for (i = 0; i < 4; i++) + ok1(tal_parent(c[i]) == parent); + + /* Iteration test. */ + i = 0; + for (p = tal_first(parent); p; p = tal_next(parent, p)) { + *p = '1'; + i++; + } + ok1(i == 4); + ok1(*c[0] == '1'); + ok1(*c[1] == '1'); + ok1(*c[2] == '1'); + ok1(*c[3] == '1'); + + /* Free parent. */ + tal_free(parent); + + parent = tal(NULL, char); + + /* Test freeing in every order */ + for (i = 0; i < 4; i++) { + for (j = 0; j < 4; j++) + c[j] = tal(parent, char); + + tal_free(c[i]); + debug_tal(to_tal_hdr(parent)); + tal_free(c[(i+1) % 4]); + debug_tal(to_tal_hdr(parent)); + tal_free(c[(i+2) % 4]); + debug_tal(to_tal_hdr(parent)); + tal_free(c[(i+3) % 4]); + debug_tal(to_tal_hdr(parent)); + } + tal_free(parent); + + return exit_status(); +} -- 2.39.2