X-Git-Url: http://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Ftal%2Ftal.c;h=79476772c585564b7e0840f215b59d09844723f1;hp=e575130568ca26913ad97ed00fa2feb6f4cf7740;hb=8f8c8b8804110b09c98f44b439d14303cc36542d;hpb=0e34459a02e2615f50bac2767c7dce6632470946 diff --git a/ccan/tal/tal.c b/ccan/tal/tal.c index e5751305..79476772 100644 --- a/ccan/tal/tal.c +++ b/ccan/tal/tal.c @@ -1,31 +1,32 @@ /* Licensed under BSD-MIT - see LICENSE file for details */ #include #include -#include #include +#include +#include #include #include -#include #include #include #include +#include //#define TAL_DEBUG 1 -/* How large should grouips get? */ -#define GROUP_NODE_AVERAGE 32 +#define NOTIFY_IS_DESTRUCTOR 512 /* 32-bit type field, first byte 0 in either endianness. */ enum prop_type { CHILDREN = 0x00c1d500, - GROUP = 0x00600d00, - DESTRUCTOR = 0x00de5700, NAME = 0x00111100, + NOTIFIER = 0x00071f00, + LENGTH = 0x00515300 }; struct tal_hdr { - struct tal_hdr *next; + struct list_node list; struct prop_hdr *prop; + struct children *parent_child; }; struct prop_hdr { @@ -33,25 +34,10 @@ struct prop_hdr { 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 list_head children; /* Head of siblings. */ }; struct name { @@ -59,16 +45,30 @@ struct name { char name[]; }; +struct length { + struct prop_hdr hdr; /* LENGTH */ + size_t len; +}; + +struct notifier { + struct prop_hdr hdr; /* NOTIFIER */ + enum tal_notify_type types; + union { + void (*notifyfn)(tal_t *, enum tal_notify_type, void *); + void (*destroy)(tal_t *); /* If NOTIFY_IS_DESTRUCTOR set */ + } u; +}; + static struct { struct tal_hdr hdr; struct children c; -} null_parent = { { NULL, &null_parent.c.hdr }, +} null_parent = { { { &null_parent.hdr.list, &null_parent.hdr.list }, + &null_parent.c.hdr, NULL }, { { CHILDREN, NULL }, &null_parent.hdr, - { { GROUP, NULL }, - { { &null_parent.c.group.list.n, - &null_parent.c.group.list.n } }, - &null_parent.c, NULL } } + { { &null_parent.c.children.n, + &null_parent.c.children.n } } + } }; @@ -76,66 +76,71 @@ 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; +/* Count on non-destrutor notifiers; often stays zero. */ +static size_t notifiers = 0; 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) +static bool get_destroying_bit(struct children *parent_child) { - *next = (void *)((size_t)next | 1); + return (size_t)parent_child & 1; } -static struct tal_hdr *ignore_destroying_bit(struct tal_hdr *next) +static void set_destroying_bit(struct children **parent_child) { - return (void *)((size_t)next & ~(size_t)1); + *parent_child = (void *)((size_t)*parent_child | 1); } -static struct group *next_group(struct group *group) +static struct children *ignore_destroying_bit(struct children *parent_child) { - return list_entry(group->list.n.next, struct group, list.n); + return (void *)((size_t)parent_child & ~(size_t)1); } -static bool atexit_set = false; /* This means valgrind can see leaks. */ -static void unlink_null(void) +void tal_cleanup(void) { - struct group *i, *next; + struct tal_hdr *i; - for (i = next_group(&null_parent.c.group); - i != &null_parent.c.group; - i = next) { - next = next_group(i); - freefn(i); + while ((i = list_top(&null_parent.c.children, struct tal_hdr, list))) { + list_del(&i->list); + memset(i, 0, sizeof(*i)); } - null_parent.c.group.first_child = NULL; + + /* Cleanup any taken pointers. */ + take_cleanup(); +} + +/* We carefully start all real properties with a zero byte. */ +static bool is_literal(const struct prop_hdr *prop) +{ + return ((char *)prop)[0] != 0; } #ifndef NDEBUG static const void *bounds_start, *bounds_end; -static void update_bounds(const void *new) +static void update_bounds(const void *new, size_t size) { - if (unlikely(!bounds_start)) - bounds_start = bounds_end = new; - else if (new < bounds_start) + if (unlikely(!bounds_start)) { + bounds_start = new; + bounds_end = (char *)new + size; + } else if (new < bounds_start) bounds_start = new; - else if (new > bounds_end) - bounds_end = new; + else if ((char *)new + size > (char *)bounds_end) + bounds_end = (char *)new + size; } static bool in_bounds(const void *p) { - return !p || (p >= bounds_start && p <= bounds_end); + return !p + || (p >= (void *)&null_parent && p <= (void *)(&null_parent + 1)) + || (p >= bounds_start && p <= bounds_end); } #else -static void update_bounds(const void *new) +static void update_bounds(const void *new, size_t size) { } @@ -157,7 +162,11 @@ static struct tal_hdr *to_tal_hdr(const void *ctx) t = (struct tal_hdr *)((char *)ctx - sizeof(struct tal_hdr)); check_bounds(t); - check_bounds(ignore_destroying_bit(t->next)); + check_bounds(ignore_destroying_bit(t->parent_child)); + check_bounds(t->list.next); + check_bounds(t->list.prev); + if (t->prop && !is_literal(t->prop)) + check_bounds(t->prop); return t; } @@ -168,9 +177,9 @@ static struct tal_hdr *to_tal_hdr_or_null(const void *ctx) return to_tal_hdr(ctx); } -static void *from_tal_hdr(struct tal_hdr *hdr) +static void *from_tal_hdr(const struct tal_hdr *hdr) { - return hdr + 1; + return (void *)(hdr + 1); } #ifdef TAL_DEBUG @@ -193,30 +202,39 @@ static struct tal_hdr *debug_tal(struct tal_hdr *tal) } #endif -static void *allocate(size_t size) +static void notify(const struct tal_hdr *ctx, + enum tal_notify_type type, const void *info) { - void *ret; + const struct prop_hdr *p; - /* Don't hand silly sizes to malloc. */ - if (size >> (CHAR_BIT*sizeof(size) - 1)) { - call_error("allocation size overflow"); - return NULL; + for (p = ctx->prop; p; p = p->next) { + struct notifier *n; + + if (is_literal(p)) + break; + if (p->type != NOTIFIER) + continue; + n = (struct notifier *)p; + if (n->types & type) { + if (n->types & NOTIFY_IS_DESTRUCTOR) + n->u.destroy(from_tal_hdr(ctx)); + else + n->u.notifyfn(from_tal_hdr(ctx), type, + (void *)info); + } } +} - ret = allocfn(size); +static void *allocate(size_t size) +{ + void *ret = allocfn(size); if (!ret) call_error("allocation failed"); else - update_bounds(ret); + update_bounds(ret, size); 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) { @@ -252,17 +270,46 @@ static void init_property(struct prop_hdr *hdr, parent->prop = hdr; } -static struct destructor *add_destructor_property(struct tal_hdr *t, - void (*destroy)(void *)) +static struct notifier *add_notifier_property(struct tal_hdr *t, + enum tal_notify_type types, + void (*fn)(void *, + enum tal_notify_type, + void *)) { - struct destructor *prop = allocate(sizeof(*prop)); + struct notifier *prop = allocate(sizeof(*prop)); if (prop) { - init_property(&prop->hdr, t, DESTRUCTOR); - prop->destroy = destroy; + init_property(&prop->hdr, t, NOTIFIER); + prop->types = types; + prop->u.notifyfn = fn; } return prop; } +static enum tal_notify_type del_notifier_property(struct tal_hdr *t, + void (*fn)(tal_t *, + enum tal_notify_type, + void *)) +{ + struct prop_hdr **p; + + for (p = (struct prop_hdr **)&t->prop; *p; p = &(*p)->next) { + struct notifier *n; + + if (is_literal(*p)) + break; + if ((*p)->type != NOTIFIER) + continue; + n = (struct notifier *)*p; + if (n->u.notifyfn == fn) { + enum tal_notify_type types = n->types; + *p = (*p)->next; + freefn(n); + return types & ~NOTIFY_IS_DESTRUCTOR; + } + } + return 0; +} + static struct name *add_name_property(struct tal_hdr *t, const char *name) { struct name *prop; @@ -275,15 +322,6 @@ static struct name *add_name_property(struct tal_hdr *t, const char *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) { @@ -291,242 +329,230 @@ static struct children *add_child_property(struct tal_hdr *parent, if (prop) { init_property(&prop->hdr, parent, CHILDREN); prop->parent = parent; - - init_group_property(&prop->group, prop, child); - list_head_init(&prop->group.list); + list_head_init(&prop->children); } 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; + list_add(&children->children, &child->list); + child->parent_child = children; return true; } -static void del_tree(struct tal_hdr *t) +static void del_tree(struct tal_hdr *t, const tal_t *orig) { struct prop_hdr **prop, *p, *next; /* Already being destroyed? Don't loop. */ - if (unlikely(get_destroying_bit(t->next))) + if (unlikely(get_destroying_bit(t->parent_child))) return; - set_destroying_bit(&t->next); + set_destroying_bit(&t->parent_child); - /* 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); - } + /* Call free notifiers. */ + notify(t, TAL_NOTIFY_FREE, (tal_t *)orig); /* Now free children and groups. */ prop = find_property_ptr(t, CHILDREN); if (prop) { + struct tal_hdr *i; 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); + + while ((i = list_top(&c->children, struct tal_hdr, list))) { + list_del(&i->list); + del_tree(i, orig); + } } - /* Finally free our properties (groups are freed by parent). */ + /* Finally free our properties. */ for (p = t->prop; p && !is_literal(p); p = next) { next = p->next; - if (p->type != GROUP) + /* LENGTH is appended, so don't free separately! */ + if (p->type != LENGTH) freefn(p); } freefn(t); } -void *tal_alloc_(const tal_t *ctx, size_t size, bool clear) +static size_t extra_for_length(size_t size) +{ + size_t extra; + const size_t align = ALIGNOF(struct length); + + /* Round up size, and add tailer. */ + extra = ((size + align-1) & ~(align-1)) - size; + extra += sizeof(struct length); + return extra; +} + +void *tal_alloc_(const tal_t *ctx, size_t size, + bool clear, bool add_length, const char *label) { + size_t req_size = size; struct tal_hdr *child, *parent = debug_tal(to_tal_hdr_or_null(ctx)); +#ifdef CCAN_TAL_DEBUG + /* Always record length if debugging. */ + add_length = true; +#endif + if (add_length) + size += extra_for_length(size); + child = allocate(sizeof(struct tal_hdr) + size); if (!child) return NULL; if (clear) - memset(from_tal_hdr(child), 0, size); - child->prop = NULL; + memset(from_tal_hdr(child), 0, req_size); + child->prop = (void *)label; + + if (add_length) { + struct length *lprop; + lprop = (struct length *)((char *)(child+1) + size) - 1; + init_property(&lprop->hdr, child, LENGTH); + lprop->len = req_size; + } if (!add_child(parent, child)) { freefn(child); return NULL; } debug_tal(parent); + if (notifiers) + notify(parent, TAL_NOTIFY_ADD_CHILD, from_tal_hdr(child)); 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) +static bool adjust_size(size_t *size, size_t count) { - struct prop_hdr **prop; - struct tal_hdr *prev; + const size_t extra = sizeof(struct tal_hdr) + sizeof(struct length)*2; - /* Loop around to find previous node. */ - for (prev = t->next; prev->next != t; prev = prev->next); + /* Multiplication wrap */ + if (count && unlikely(*size * count / *size != count)) + goto overflow; - /* Unlink ourselves. */ - prev->next = t->next; + *size *= count; - /* 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; + /* Make sure we don't wrap adding header/tailer. */ + if (*size + extra < extra) + goto overflow; + return true; +overflow: + call_error("allocation size overflow"); + return false; } -void tal_free(const tal_t *ctx) +void *tal_alloc_arr_(const tal_t *ctx, size_t size, size_t count, bool clear, + bool add_length, const char *label) { - struct tal_hdr *t; + if (!adjust_size(&size, count)) + return NULL; - if (!ctx) - return; + return tal_alloc_(ctx, size, clear, add_length, label); +} - t = debug_tal(to_tal_hdr(ctx)); - remove_node(t); - del_tree(t); +void *tal_free(const tal_t *ctx) +{ + if (ctx) { + struct tal_hdr *t; + int saved_errno = errno; + t = debug_tal(to_tal_hdr(ctx)); + if (notifiers) + notify(ignore_destroying_bit(t->parent_child)->parent, + TAL_NOTIFY_DEL_CHILD, ctx); + list_del(&t->list); + del_tree(t, ctx); + errno = saved_errno; + } + return NULL; } void *tal_steal_(const tal_t *new_parent, const tal_t *ctx) { if (ctx) { - struct tal_hdr *newpar, *t, *old_next, *old_parent; + struct tal_hdr *newpar, *t, *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); + list_del(&t->list); + old_parent = ignore_destroying_bit(t->parent_child)->parent; + 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. */ + /* We can always add to old parent, becuase it has a + * children property already. */ if (!add_child(old_parent, t)) abort(); return NULL; } debug_tal(newpar); + if (notifiers) + notify(t, TAL_NOTIFY_STEAL, new_parent); } return (void *)ctx; } -bool tal_add_destructor_(tal_t *ctx, void (*destroy)(void *me)) +bool tal_add_destructor_(const tal_t *ctx, void (*destroy)(void *me)) +{ + tal_t *t = debug_tal(to_tal_hdr(ctx)); + return add_notifier_property(t, TAL_NOTIFY_FREE|NOTIFY_IS_DESTRUCTOR, + (void *)destroy); +} + +bool tal_add_notifier_(const tal_t *ctx, enum tal_notify_type types, + void (*callback)(tal_t *, enum tal_notify_type, void *)) { - return add_destructor_property(debug_tal(to_tal_hdr(ctx)), destroy); + tal_t *t = debug_tal(to_tal_hdr(ctx)); + struct notifier *n; + + assert(types); + assert((types & ~(TAL_NOTIFY_FREE | TAL_NOTIFY_STEAL | TAL_NOTIFY_MOVE + | TAL_NOTIFY_RESIZE | TAL_NOTIFY_RENAME + | TAL_NOTIFY_ADD_CHILD | TAL_NOTIFY_DEL_CHILD + | TAL_NOTIFY_ADD_NOTIFIER + | TAL_NOTIFY_DEL_NOTIFIER)) == 0); + + /* Don't call notifier about itself: set types after! */ + n = add_notifier_property(t, 0, callback); + if (unlikely(!n)) + return false; + + if (notifiers) + notify(t, TAL_NOTIFY_ADD_NOTIFIER, callback); + + n->types = types; + if (types != TAL_NOTIFY_FREE) + notifiers++; + return true; +} + +bool tal_del_notifier_(const tal_t *ctx, + void (*callback)(tal_t *, enum tal_notify_type, void *)) +{ + struct tal_hdr *t = debug_tal(to_tal_hdr(ctx)); + enum tal_notify_type types; + + types = del_notifier_property(t, callback); + if (types) { + notify(t, TAL_NOTIFY_DEL_NOTIFIER, callback); + if (types != TAL_NOTIFY_FREE) + notifiers--; + return true; + } + return false; +} + +bool tal_del_destructor_(const tal_t *ctx, void (*destroy)(void *me)) +{ + return tal_del_notifier_(ctx, (void *)destroy); } bool tal_set_name_(tal_t *ctx, const char *name, bool literal) @@ -551,11 +577,12 @@ bool tal_set_name_(tal_t *ctx, const char *name, bool literal) /* 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)) + } else if (!add_name_property(t, name)) return false; + debug_tal(t); + if (notifiers) + notify(t, TAL_NOTIFY_RENAME, name); return true; } @@ -572,26 +599,26 @@ const char *tal_name(const tal_t *t) return n->name; } +size_t tal_len(const tal_t *ptr) +{ + struct length *l; + + l = find_property(debug_tal(to_tal_hdr(ptr)), LENGTH); + if (!l) + return 0; + return l->len; +} + /* 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; + return list_top(&child->children, struct tal_hdr, list); } tal_t *tal_first(const tal_t *root) @@ -604,144 +631,169 @@ tal_t *tal_first(const tal_t *root) return from_tal_hdr(c); } -tal_t *tal_next(const tal_t *root, const tal_t *prev) +tal_t *tal_next(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); + struct tal_hdr *next, *prevhdr = debug_tal(to_tal_hdr(prev)); + struct list_head *head; - return NULL; + head = &ignore_destroying_bit(prevhdr->parent_child)->children; + next = list_next(head, prevhdr, list); + if (!next) + return NULL; + return from_tal_hdr(next); } tal_t *tal_parent(const tal_t *ctx) { - struct group *group; - struct tal_hdr *t = debug_tal(to_tal_hdr(ctx)); + struct tal_hdr *t; - while (!(group = find_property(t, GROUP))) - t = t->next; + if (!ctx) + return NULL; - if (group->parent_child->parent == &null_parent.hdr) + t = debug_tal(to_tal_hdr(ctx)); + if (ignore_destroying_bit(t->parent_child)->parent == &null_parent.hdr) return NULL; - return from_tal_hdr(group->parent_child->parent); + return from_tal_hdr(ignore_destroying_bit(t->parent_child)->parent); } -void *tal_realloc_(tal_t *ctx, size_t size) +bool tal_resize_(tal_t **ctxp, size_t size, size_t count, bool clear) { - struct tal_hdr *old_t, *t, **prev; - struct group *group; + struct tal_hdr *old_t, *t; struct children *child; + struct prop_hdr **lenp; + struct length len; + size_t extra = 0; - old_t = debug_tal(to_tal_hdr(ctx)); + old_t = debug_tal(to_tal_hdr(*ctxp)); - t = resizefn(old_t, size + sizeof(struct tal_hdr)); + if (!adjust_size(&size, count)) + return false; + + lenp = find_property_ptr(old_t, LENGTH); + if (lenp) { + /* Copy here, in case we're shrinking! */ + len = *(struct length *)*lenp; + extra = extra_for_length(size); + } else /* If we don't have an old length, we can't clear! */ + assert(!clear); + + t = resizefn(old_t, sizeof(struct tal_hdr) + size + extra); if (!t) { call_error("Reallocation failure"); - tal_free(old_t); - return NULL; + return false; } - 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; + + /* Copy length to end. */ + if (lenp) { + struct length *new_len; + + /* Clear between old end and new end. */ + if (clear && size > len.len) { + char *old_end = (char *)(t + 1) + len.len; + memset(old_end, 0, size - len.len); + } + + new_len = (struct length *)((char *)(t + 1) + size + + extra - sizeof(len)); + len.len = size; + *new_len = len; + + /* Be careful replacing next ptr; could be old hdr. */ + if (lenp == &old_t->prop) + t->prop = &new_len->hdr; + else + *lenp = &new_len->hdr; } - /* Fix up child propertie's parent pointer. */ - child = find_property(t, CHILDREN); - if (child) { - assert(child->parent == old_t); - child->parent = t; + update_bounds(t, sizeof(struct tal_hdr) + size + extra); + + /* If it didn't move, we're done! */ + if (t != old_t) { + /* Fix up linked list pointers. */ + t->list.next->prev = t->list.prev->next = &t->list; + + /* Fix up child property's parent pointer. */ + child = find_property(t, CHILDREN); + if (child) { + assert(child->parent == old_t); + child->parent = t; + } + *ctxp = from_tal_hdr(debug_tal(t)); + if (notifiers) + notify(t, TAL_NOTIFY_MOVE, from_tal_hdr(old_t)); } + if (notifiers) + notify(t, TAL_NOTIFY_RESIZE, (void *)size); - return from_tal_hdr(debug_tal(t)); + return true; } -char *tal_strdup(const tal_t *ctx, const char *p) +bool tal_expand_(tal_t **ctxp, const void *src, size_t size, size_t count) { - return tal_memdup(ctx, p, strlen(p)+1); -} + struct length *l; + size_t old_len; + bool ret = false; -char *tal_strndup(const tal_t *ctx, const char *p, size_t n) -{ - char *ret; + l = find_property(debug_tal(to_tal_hdr(*ctxp)), LENGTH); + old_len = l->len; - if (strlen(p) < n) - n = strlen(p); - ret = tal_memdup(ctx, p, n+1); - if (ret) - ret[n] = '\0'; - return ret; -} + /* Check for additive overflow */ + if (old_len + count * size < old_len) { + call_error("dup size overflow"); + goto out; + } -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; -} + /* Don't point src inside thing we're expanding! */ + assert(src < *ctxp + || (char *)src >= (char *)(*ctxp) + old_len); -char *tal_asprintf(const tal_t *ctx, const char *fmt, ...) -{ - va_list ap; - char *ret; + if (!tal_resize_(ctxp, size, old_len/size + count, false)) + goto out; - va_start(ap, fmt); - ret = tal_vasprintf(ctx, fmt, ap); - va_end(ap); + memcpy((char *)*ctxp + old_len, src, count * size); + ret = true; +out: + if (taken(src)) + tal_free(src); return ret; } -char *tal_vasprintf(const tal_t *ctx, const char *fmt, va_list ap) +void *tal_dup_(const tal_t *ctx, const void *p, size_t size, + size_t n, size_t extra, bool add_length, + const char *label) { - size_t max = strlen(fmt) * 2; - char *buf = tal_arr(ctx, char, max); - int ret; + void *ret; + size_t nbytes = size; - while (buf) { - va_list ap2; + if (!adjust_size(&nbytes, n)) { + if (taken(p)) + tal_free(p); + return NULL; + } - va_copy(ap2, ap); - ret = vsnprintf(buf, max, fmt, ap2); - va_end(ap2); + /* Beware addition overflow! */ + if (n + extra < n) { + call_error("dup size overflow"); + if (taken(p)) + tal_free(p); + return NULL; + } - if (ret < max) - break; - buf = tal_resize(buf, max *= 2); + if (taken(p)) { + if (unlikely(!p)) + return NULL; + if (unlikely(!tal_resize_((void **)&p, size, n + extra, false))) + return tal_free(p); + if (unlikely(!tal_steal(ctx, p))) + return tal_free(p); + return (void *)p; } - return buf; + + ret = tal_alloc_arr_(ctx, size, n + extra, false, add_length, label); + if (ret) + memcpy(ret, p, nbytes); + return ret; } void tal_set_backend(void *(*alloc_fn)(size_t size), @@ -769,10 +821,10 @@ static void dump_node(unsigned int indent, const struct tal_hdr *t) printf(" "); printf("%p", t); for (p = t->prop; p; p = p->next) { - struct group *g; struct children *c; - struct destructor *d; struct name *n; + struct notifier *no; + struct length *l; if (is_literal(p)) { printf(" \"%s\"", (const char *)p); break; @@ -780,27 +832,22 @@ static void dump_node(unsigned int indent, const struct tal_hdr *t) 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); + printf(" CHILDREN(%p):parent=%p,children={%p,%p}\n", + p, c->parent, + c->children.n.prev, c->children.n.next); break; case NAME: n = (struct name *)p; printf(" NAME(%p):%s", p, n->name); break; + case NOTIFIER: + no = (struct notifier *)p; + printf(" NOTIFIER(%p):fn=%p", p, no->u.notifyfn); + break; + case LENGTH: + l = (struct length *)p; + printf(" LENGTH(%p):len=%zu", p, l->len); + break; default: printf(" **UNKNOWN(%p):%i**", p, p->type); } @@ -811,27 +858,16 @@ static void dump_node(unsigned int indent, const struct tal_hdr *t) 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 { + if (children) { 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); + list_for_each(&children->children, i, list) + tal_dump_(level + 1, i); + } } void tal_dump(void) @@ -853,46 +889,45 @@ static bool check_err(struct tal_hdr *t, const char *errorstr, return false; } -static bool check_group(struct group *group, - struct tal_hdr *t, const char *errorstr); - -static bool check_node(struct group *group, +static bool check_node(struct children *parent_child, struct tal_hdr *t, const char *errorstr) { struct prop_hdr *p; struct name *name = NULL; struct children *children = NULL; - struct group *gr = NULL; + struct length *length = NULL; - if (t != &null_parent.hdr && !in_bounds(t)) + if (!in_bounds(t)) return check_err(t, errorstr, "invalid pointer"); + if (ignore_destroying_bit(t->parent_child) != parent_child) + return check_err(t, errorstr, "incorrect parent"); + 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)) + if (!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: + case LENGTH: + if (length) + return check_err(t, errorstr, + "has two lengths"); + length = (struct length *)p; + break; + case NOTIFIER: break; case NAME: if (name) @@ -904,40 +939,16 @@ static bool check_node(struct group *group, 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; + struct tal_hdr *i; - i = t; - do { - if (!check_node(group, i, errorstr)) + if (!list_check(&children->children, errorstr)) return false; - group = NULL; - i = i->next; - } while (i != t); + list_for_each(&children->children, i, list) { + if (!check_node(children, i, errorstr)) + return false; + } + } return true; } @@ -945,7 +956,7 @@ 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); + return check_node(ignore_destroying_bit(t->parent_child), t, errorstr); } #else /* NDEBUG */ bool tal_check(const tal_t *ctx, const char *errorstr)