X-Git-Url: https://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Ftal%2Ftal.c;h=c78185be01aa12715a0499088974ab8f561ccee6;hp=ff25db19afb8a3b16da50ef254687a85b50cc71e;hb=737dcc0fe959d67eb29f57df37b0d7f188e0213d;hpb=dfe59969500a0c4e3b82ce6e7f8227d1a6e7b178

diff --git a/ccan/tal/tal.c b/ccan/tal/tal.c
index ff25db19..c78185be 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 <ccan/tal/tal.h>
 #include <ccan/compiler/compiler.h>
-#include <ccan/hash/hash.h>
 #include <ccan/list/list.h>
+#include <ccan/take/take.h>
 #include <assert.h>
 #include <stdio.h>
 #include <stdarg.h>
 #include <stddef.h>
 #include <string.h>
 #include <limits.h>
+#include <errno.h>
 
 //#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 count;
+};
+
+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,76 @@ 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 bool initialized = false;
+/* 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)
+static bool get_destroying_bit(struct children *parent_child)
 {
-	return (size_t)next & 1;
+	return (size_t)parent_child & 1;
 }
 
-static void set_destroying_bit(struct tal_hdr **next)
+static void set_destroying_bit(struct children **parent_child)
 {
-	*next = (void *)((size_t)next | 1);
+	*parent_child = (void *)((size_t)*parent_child | 1);
 }
 
-static struct tal_hdr *ignore_destroying_bit(struct tal_hdr *next)
+static struct children *ignore_destroying_bit(struct children *parent_child)
 {
-	return (void *)((size_t)next & ~(size_t)1);
+	return (void *)((size_t)parent_child & ~(size_t)1);
 }
 
-static struct group *next_group(struct group *group)
+/* This means valgrind can see leaks. */
+static void tal_cleanup(void)
 {
-	return list_entry(group->list.n.next, struct group, list.n);
+	struct tal_hdr *i;
+
+	while ((i = list_top(&null_parent.c.children, struct tal_hdr, list)))
+		list_del(&i->list);
+
+	/* Cleanup any taken pointers. */
+	take_cleanup();
 }
 
-static bool atexit_set = false;
-/* This means valgrind can see leaks. */
-static void unlink_null(void)
+/* For allocation failures inside ccan/take */
+static void take_alloc_failed(const void *p)
 {
-	struct group *i, *next;
+	tal_free(p);
+}
 
-	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;
+/* 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 +167,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 +182,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 +207,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 +275,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,13 +327,16 @@ 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)
+static struct length *add_length_property(struct tal_hdr *t, size_t count)
 {
-	init_property(&group->hdr, child, GROUP);
-	group->parent_child = parent_child;
-	group->first_child = child;
+	struct length *prop;
+
+	prop = allocate(sizeof(*prop));
+	if (prop) {
+		init_property(&prop->hdr, t, LENGTH);
+		prop->count = count;
+	}
+	return prop;
 }
 
 static struct children *add_child_property(struct tal_hdr *parent,
@@ -291,128 +346,59 @@ 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);
-		update_bounds(&prop->group);
+		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) {
+		if (unlikely(!initialized)) {
+			atexit(tal_cleanup);
+			take_allocfail(take_alloc_failed);
+			initialized = true;
+		}
 		children = add_child_property(parent, child);
 		if (!children)
 			return false;
-		list_head_init(&children->group.list);
-
-		/* 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)
-			freefn(p);
+		freefn(p);
         }
         freefn(t);
 }
@@ -432,101 +418,139 @@ void *tal_alloc_(const tal_t *ctx, size_t size, bool clear, const char *label)
 		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;
-
-	/* 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. */
+        if (*size + sizeof(struct tal_hdr) < sizeof(struct tal_hdr))
+		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_count, const char *label)
 {
-        struct tal_hdr *t;
+	void *ret;
 
-        if (!ctx)
-                return;
+	if (!adjust_size(&size, count))
+		return NULL;
 
-        t = debug_tal(to_tal_hdr(ctx));
-        remove_node(t);
-        del_tree(t);
+	ret = tal_alloc_(ctx, size, clear, label);
+	if (likely(ret) && add_count) {
+		if (unlikely(!add_length_property(to_tal_hdr(ret), count)))
+			ret = tal_free(ret);
+	}
+	return ret;
+}
+
+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 +575,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 +597,26 @@ const char *tal_name(const tal_t *t)
 	return n->name;
 }
 
+size_t tal_count(const tal_t *ptr)
+{
+	struct length *l;
+
+	l = find_property(debug_tal(to_tal_hdr(ptr)), LENGTH);
+	if (!l)
+		return 0;
+	return l->count;
+}
+
 /* 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)
@@ -607,7 +632,6 @@ tal_t *tal_first(const tal_t *root)
 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);
@@ -616,20 +640,17 @@ tal_t *tal_next(const tal_t *root, const tal_t *prev)
 
         top = to_tal_hdr_or_null(root);
         do {
-		struct group *next;
+		struct tal_hdr *next;
+		struct list_node *end;
 
-		/* Are we back to first child in group? */
-		group = find_property(t, GROUP);
-		if (!group)
-                        return from_tal_hdr(t->next);
+		end = &ignore_destroying_bit(t->parent_child)->children.n;
 
-		/* 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);
+		next = list_entry(t->list.next, struct tal_hdr, list);
+		if (&next->list != end)
+			return from_tal_hdr(next);
 
                 /* OK, go back to parent. */
-                t = group->parent_child->parent;
+                t = ignore_destroying_bit(t->parent_child)->parent;
         } while (t != top);
 
         return NULL;
@@ -637,88 +658,121 @@ tal_t *tal_next(const tal_t *root, const tal_t *prev)
 
 tal_t *tal_parent(const tal_t *ctx)
 {
-        struct group *group;
         struct tal_hdr *t;
 
 	if (!ctx)
 		return NULL;
 
 	t = debug_tal(to_tal_hdr(ctx));
-
-	while (!(group = find_property(t, GROUP)))
-		t = t->next;
-
-	if (group->parent_child->parent == &null_parent.hdr)
+	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)
 {
-        struct tal_hdr *old_t, *t, **prev;
-        struct group *group;
+        struct tal_hdr *old_t, *t;
         struct children *child;
+	struct length *len;
 
-        old_t = debug_tal(to_tal_hdr(ctx));
+        old_t = debug_tal(to_tal_hdr(*ctxp));
+
+	if (!adjust_size(&size, count))
+		return false;
 
         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;
+		return false;
 	}
 
-	/* Fix up child propertie's parent pointer. */
-	child = find_property(t, CHILDREN);
-	if (child) {
-		assert(child->parent == old_t);
-		child->parent = t;
+	/* If it didn't move, we're done! */
+        if (t != old_t) {
+		update_bounds(t, size + sizeof(struct tal_hdr));
+
+		/* Fix up linked list pointers. */
+		if (list_entry(t->list.next, struct tal_hdr, list) != old_t)
+			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));
 	}
+	len = find_property(t, LENGTH);
+	if (len)
+		len->count = count;
+	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)
 {
-	return tal_memdup(ctx, p, strlen(p)+1);
+	/* We have to let through NULL for take(). */
+	return tal_dup_(ctx, p, 1, p ? strlen(p) + 1: 1, 0, false,
+			TAL_LABEL(char, "[]"));
 }
 
 char *tal_strndup(const tal_t *ctx, const char *p, size_t n)
 {
+	size_t len;
 	char *ret;
 
-	if (strlen(p) < n)
-		n = strlen(p);
-	ret = tal_memdup(ctx, p, n+1);
+	/* We have to let through NULL for take(). */
+	if (likely(p)) {
+		len = strlen(p);
+		if (len > n)
+			len = n;
+	} else
+		len = n;
+
+	ret = tal_dup_(ctx, p, 1, len, 1, false, TAL_LABEL(char, "[]"));
 	if (ret)
-		ret[n] = '\0';
+		ret[len] = '\0';
 	return ret;
 }
 
-void *tal_memdup(const tal_t *ctx, const void *p, size_t n)
+void *tal_dup_(const tal_t *ctx, const void *p, size_t size,
+	       size_t n, size_t extra, bool add_count,
+	       const char *label)
 {
 	void *ret;
+	size_t nbytes = size;
+
+	if (!adjust_size(&nbytes, n)) {
+		if (taken(p))
+			tal_free(p);
+		return NULL;
+	}
+
+	/* Beware addition overflow! */
+	if (n + extra < n) {
+		call_error("dup size overflow");
+		if (taken(p))
+			tal_free(p);
+		return NULL;
+	}
 
-	if (ctx == TAL_TAKE)
+	if (taken(p)) {
+		if (unlikely(!p))
+			return NULL;
+		if (unlikely(!tal_resize_((void **)&p, size, n + extra)))
+			return tal_free(p);
+		if (unlikely(!tal_steal(ctx, p)))
+			return tal_free(p);
 		return (void *)p;
+	}
 
-	ret = tal_arr(ctx, char, n);
+	ret = tal_alloc_arr_(ctx, size, n + extra, false, add_count, label);
 	if (ret)
-		memcpy(ret, p, n);
+		memcpy(ret, p, nbytes);
 	return ret;
 }
 
@@ -736,15 +790,16 @@ char *tal_asprintf(const tal_t *ctx, const char *fmt, ...)
 
 char *tal_vasprintf(const tal_t *ctx, const char *fmt, va_list ap)
 {
-	size_t max = strlen(fmt) * 2;
+	size_t max;
 	char *buf;
 	int ret;
 
-	if (ctx == TAL_TAKE)
-		buf = tal_arr(tal_parent(fmt), char, max);
-	else
-		buf = tal_arr(ctx, char, max);
+	if (!fmt && taken(fmt))
+		return NULL;
 
+	/* A decent guess to start. */
+	max = strlen(fmt) * 2;
+	buf = tal_arr(ctx, char, max);
 	while (buf) {
 		va_list ap2;
 
@@ -754,9 +809,10 @@ char *tal_vasprintf(const tal_t *ctx, const char *fmt, va_list ap)
 
 		if (ret < max)
 			break;
-		buf = tal_resize(buf, max *= 2);
+		if (!tal_resize(&buf, max *= 2))
+			buf = tal_free(buf);
 	}
-	if (ctx == TAL_TAKE)
+	if (taken(fmt))
 		tal_free(fmt);
 	return buf;
 }
@@ -786,10 +842,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;
@@ -797,27 +853,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):count=%zu", p, l->count);
+			break;
 		default:
 			printf(" **UNKNOWN(%p):%i**", p, p->type);
 		}
@@ -828,27 +879,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)
@@ -870,20 +910,20 @@ 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)
@@ -892,25 +932,24 @@ static bool check_node(struct group *group,
 			name = (struct name *)p;
 			break;
 		}
-		if (p != &null_parent.c.hdr && p != &null_parent.c.group.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)
@@ -922,40 +961,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;
 }
 
@@ -963,7 +978,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)