ccan/tal: always include a length field.
authorRusty Russell <rusty@rustcorp.com.au>
Fri, 27 Jul 2018 04:29:18 +0000 (13:59 +0930)
committerRusty Russell <rusty@rustcorp.com.au>
Fri, 27 Jul 2018 04:29:18 +0000 (13:59 +0930)
The current semantics of tal_count() / tal_bytelen() are to return 0
for anything not allocated using tal_arr*.  This is because we tried
to save a native-length word in the header, but produces an awkward
API.

(To make it worse, defining CCAN_TAL_DEBUG turns length to always on,
and we enable that for c-lightning developer mode, which hides bugs!).

However, for c-lightning, just over half of allocations want a length:
these use 3 words each, so we're actually worse off overall.

The answer is to always have a length field in the header.  This also
simplfies the tal code.

samba-allocs stats before:
Tal time: 1237102-1305755(1.251e+06+/-2.1e+04)ns
Tal_free time: 1346871-1514514(1.37844e+06+/-5.2e+04)ns

After:
Tal time: 1115180-1180633(1.1351e+06+/-2.1e+04)ns
Tal_free time: 1334381-1465933(1.39148e+06+/-4.7e+04)ns

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
ccan/tal/benchmark/samba-allocs.c
ccan/tal/tal.c
ccan/tal/tal.h
ccan/tal/test/run-count.c

index f2259a4e3d54fc41655a73dc8cd3cebd48058895..4bed1b2a211cbd56b8849c447ba4a61d81367884 100644 (file)
@@ -178,15 +178,8 @@ static void do_tals(struct node *node)
        unsigned int i;
        static int count;
 
-       /* Tal pays a penalty for arrays, but we can't tell which is an array
-        * and which isn't.  Grepping samba source gives 1221 talloc_array of
-        * 33137 talloc occurrences, so conservatively assume 1 in 16 */
-       if (count++ % 16 == 0)
-               node->n = tal_arr(node->parent ? node->parent->n : NULL,
-                                 char, node->len);
-       else
-               node->n = tal_alloc_(node->parent ? node->parent->n : NULL,
-                                    node->len, false, false, TAL_LABEL(type, ""));
+       node->n = tal_arr(node->parent ? node->parent->n : NULL,
+                         char, node->len);
 
        if (node->destructor)
                tal_add_destructor(node->n, unused_tal_destructor);
index 7018d9fc98b3d80f33fcdaab0f4ad0ea2609fbf7..3fac61129d1963654713c26d2495cf665a681f71 100644 (file)
@@ -24,7 +24,6 @@ enum prop_type {
        CHILDREN = 0x00c1d500,
        NAME = 0x00111100,
        NOTIFIER = 0x00071f00,
-       LENGTH = 0x00515300
 };
 
 struct tal_hdr {
@@ -32,6 +31,7 @@ struct tal_hdr {
        struct prop_hdr *prop;
        /* XOR with TAL_PTR_OBFUSTICATOR */
        intptr_t parent_child;
+       size_t bytelen;
 };
 
 struct prop_hdr {
@@ -50,11 +50,6 @@ 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;
@@ -77,7 +72,7 @@ static struct {
        struct tal_hdr hdr;
        struct children c;
 } null_parent = { { { &null_parent.hdr.list, &null_parent.hdr.list },
-                   &null_parent.c.hdr, TAL_PTR_OBFUSTICATOR },
+                   &null_parent.c.hdr, TAL_PTR_OBFUSTICATOR, 0 },
                  { { CHILDREN, NULL },
                    &null_parent.hdr,
                    { { &null_parent.c.children.n,
@@ -414,50 +409,23 @@ static void del_tree(struct tal_hdr *t, const tal_t *orig, int saved_errno)
         /* Finally free our properties. */
         for (p = t->prop; p && !is_literal(p); p = next) {
                 next = p->next;
-               /* LENGTH is appended, so don't free separately! */
-               if (p->type != LENGTH)
-                       freefn(p);
+               freefn(p);
         }
         freefn(t);
 }
 
-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)
+void *tal_alloc_(const tal_t *ctx, size_t size, bool clear, 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, req_size);
+               memset(from_tal_hdr(child), 0, size);
         child->prop = (void *)label;
+       child->bytelen = size;
 
-       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;
@@ -470,7 +438,7 @@ void *tal_alloc_(const tal_t *ctx, size_t size,
 
 static bool adjust_size(size_t *size, size_t count)
 {
-       const size_t extra = sizeof(struct tal_hdr) + sizeof(struct length)*2;
+       const size_t extra = sizeof(struct tal_hdr);
 
        /* Multiplication wrap */
         if (count && unlikely(*size * count / *size != count))
@@ -478,7 +446,7 @@ static bool adjust_size(size_t *size, size_t count)
 
         *size *= count;
 
-        /* Make sure we don't wrap adding header/tailer. */
+        /* Make sure we don't wrap adding header. */
         if (*size + extra < extra)
                goto overflow;
        return true;
@@ -488,12 +456,12 @@ overflow:
 }
 
 void *tal_alloc_arr_(const tal_t *ctx, size_t size, size_t count, bool clear,
-                    bool add_length, const char *label)
+                    const char *label)
 {
        if (!adjust_size(&size, count))
                return NULL;
 
-       return tal_alloc_(ctx, size, clear, add_length, label);
+       return tal_alloc_(ctx, size, clear, label);
 }
 
 void *tal_free(const tal_t *ctx)
@@ -658,15 +626,10 @@ const char *tal_name(const tal_t *t)
 
 size_t tal_bytelen(const tal_t *ptr)
 {
-       struct length *l;
+       /* NULL -> null_parent which has bytelen 0 */
+       struct tal_hdr *t = debug_tal(to_tal_hdr_or_null(ptr));
 
-       if (!ptr)
-               return 0;
-
-       l = find_property(debug_tal(to_tal_hdr(ptr)), LENGTH);
-       if (!l)
-               return 0;
-       return l->len;
+       return t->bytelen;
 }
 
 /* Start one past first child: make stopping natural in circ. list. */
@@ -720,52 +683,27 @@ bool tal_resize_(tal_t **ctxp, size_t size, size_t count, bool clear)
 {
         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(*ctxp));
 
        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);
+        t = resizefn(old_t, sizeof(struct tal_hdr) + size);
        if (!t) {
                call_error("Reallocation failure");
                return false;
        }
 
-       /* 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;
+       /* Clear between old end and new end. */
+       if (clear && size > t->bytelen) {
+               char *old_end = (char *)(t + 1) + t->bytelen;
+               memset(old_end, 0, size - t->bytelen);
        }
 
-       update_bounds(t, sizeof(struct tal_hdr) + size + extra);
+       /* Update length. */
+       t->bytelen = size;
+       update_bounds(t, sizeof(struct tal_hdr) + size);
 
        /* If it didn't move, we're done! */
         if (t != old_t) {
@@ -790,12 +728,10 @@ bool tal_resize_(tal_t **ctxp, size_t size, size_t count, bool clear)
 
 bool tal_expand_(tal_t **ctxp, const void *src, size_t size, size_t count)
 {
-       struct length *l;
        size_t old_len;
        bool ret = false;
 
-       l = find_property(debug_tal(to_tal_hdr(*ctxp)), LENGTH);
-       old_len = l->len;
+       old_len = debug_tal(to_tal_hdr(*ctxp))->bytelen;
 
        /* Check for additive overflow */
        if (old_len + count * size < old_len) {
@@ -820,8 +756,7 @@ out:
 }
 
 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 n, size_t extra, const char *label)
 {
        void *ret;
        size_t nbytes = size;
@@ -850,7 +785,7 @@ void *tal_dup_(const tal_t *ctx, const void *p, size_t size,
                return (void *)p;
        }
 
-       ret = tal_alloc_arr_(ctx, size, n + extra, false, add_length, label);
+       ret = tal_alloc_arr_(ctx, size, n + extra, false, label);
        if (ret)
                memcpy(ret, p, nbytes);
        return ret;
@@ -879,12 +814,11 @@ static void dump_node(unsigned int indent, const struct tal_hdr *t)
 
        for (i = 0; i < indent; i++)
                printf("  ");
-       printf("%p", t);
+       printf("%p len=%zu", t, t->bytelen);
         for (p = t->prop; p; p = p->next) {
                struct children *c;
                struct name *n;
                struct notifier *no;
-               struct length *l;
                 if (is_literal(p)) {
                        printf(" \"%s\"", (const char *)p);
                        break;
@@ -904,10 +838,6 @@ static void dump_node(unsigned int indent, const struct tal_hdr *t)
                        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);
                }
@@ -955,7 +885,6 @@ static bool check_node(struct children *parent_child,
        struct prop_hdr *p;
        struct name *name = NULL;
        struct children *children = NULL;
-       struct length *length = NULL;
 
        if (!in_bounds(t))
                return check_err(t, errorstr, "invalid pointer");
@@ -981,12 +910,6 @@ static bool check_node(struct children *parent_child,
                                                 "has two child nodes");
                        children = (struct children *)p;
                        break;
-               case LENGTH:
-                       if (length)
-                               return check_err(t, errorstr,
-                                                "has two lengths");
-                       length = (struct length *)p;
-                       break;
                case NOTIFIER:
                        break;
                case NAME:
index a4c69f405f297421f34882d05a208c6253a772b4..54318e1fa116864ae5d00268b9d6c3144ba86eb3 100644 (file)
@@ -28,6 +28,8 @@ typedef void tal_t;
  * of the object is a string of the type, but if CCAN_TAL_DEBUG is
  * defined it also contains the file and line which allocated it.
  *
+ * tal_count() of the return will be 1.
+ *
  * Example:
  *     int *p = tal(NULL, int);
  *     *p = 1;
@@ -71,8 +73,7 @@ void *tal_free(const tal_t *p);
  * @type: the type to allocate.
  * @count: the number to allocate.
  *
- * Note that an object allocated with tal_arr() has a length property;
- * see tal_count().
+ * tal_count() of the returned pointer will be @count.
  *
  * Example:
  *     p = tal_arr(NULL, int, 2);
@@ -88,8 +89,7 @@ void *tal_free(const tal_t *p);
  * @type: the type to allocate.
  * @count: the number to allocate.
  *
- * Note that an object allocated with tal_arrz() has a length property;
- * see tal_count().
+ * Equivalent to tal_arr() followed by memset() to zero.
  *
  * Example:
  *     p = tal_arrz(NULL, int, 2);
@@ -99,12 +99,12 @@ void *tal_free(const tal_t *p);
        tal_arrz_label(ctx, type, count, TAL_LABEL(type, "[]"))
 
 /**
- * tal_resize - enlarge or reduce a tal_arr[z].
+ * tal_resize - enlarge or reduce a tal object.
  * @p: A pointer to the tal allocated array to resize.
  * @count: the number to allocate.
  *
  * This returns true on success (and may move *@p), or false on failure.
- * If @p has a length property, it is updated on success.
+ * On success, tal_count() of *@p will be @count.
  *
  * Example:
  *     tal_resize(&p, 100);
@@ -113,13 +113,11 @@ void *tal_free(const tal_t *p);
        tal_resize_((void **)(p), sizeof**(p), (count), false)
 
 /**
- * tal_resizez - enlarge or reduce a tal_arr[z]; zero out extra.
+ * tal_resizez - enlarge or reduce a tal object; zero out extra.
  * @p: A pointer to the tal allocated array to resize.
  * @count: the number to allocate.
  *
  * This returns true on success (and may move *@p), or false on failure.
- * If @p has a length property, it is updated on success.
- * On expand, new elements are memset to 0 bytes.
  *
  * Example:
  *     tal_resizez(&p, 200);
@@ -302,20 +300,20 @@ enum tal_notify_type {
 const char *tal_name(const tal_t *ptr);
 
 /**
- * tal_count - get the count of objects in a tal_arr.
- * @ptr: The tal allocated object array (or NULL)
+ * tal_count - get the count of objects in a tal object.
+ * @ptr: The tal allocated object (or NULL)
  *
- * Returns 0 if @ptr has no length property or is NULL, but be aware
- * that that is also a valid size!
+ * Returns 0 if @ptr is NULL.  Note that if the allocation was done as a
+ * different type to @ptr, the result may not match the @count argument
+ * (or implied 1) of that allocation!
  */
 #define tal_count(p) (tal_bytelen(p) / sizeof(*p))
 
 /**
- * tal_bytelen - get the count of bytes in a tal_arr.
- * @ptr: The tal allocated object array (or NULL)
+ * tal_bytelen - get the count of bytes in a tal object.
+ * @ptr: The tal allocated object (or NULL)
  *
- * Returns 0 if @ptr has no length property or NULL, but be aware that that is
- * also a valid size!
+ * Returns 0 if @ptr is NULL.
  */
 size_t tal_bytelen(const tal_t *ptr);
 
@@ -368,21 +366,21 @@ tal_t *tal_parent(const tal_t *ctx);
 
 /* Lower-level interfaces, where you want to supply your own label string. */
 #define tal_label(ctx, type, label)                                            \
-       ((type *)tal_alloc_((ctx), sizeof(type), false, false, label))
+       ((type *)tal_alloc_((ctx), sizeof(type), false, label))
 #define talz_label(ctx, type, label)                                           \
-       ((type *)tal_alloc_((ctx), sizeof(type), true, false, label))
+       ((type *)tal_alloc_((ctx), sizeof(type), true, label))
 #define tal_arr_label(ctx, type, count, label)                                 \
-       ((type *)tal_alloc_arr_((ctx), sizeof(type), (count), false, true, label))
+       ((type *)tal_alloc_arr_((ctx), sizeof(type), (count), false, label))
 #define tal_arrz_label(ctx, type, count, label)                                        \
-       ((type *)tal_alloc_arr_((ctx), sizeof(type), (count), true, true, label))
+       ((type *)tal_alloc_arr_((ctx), sizeof(type), (count), true, label))
 #define tal_dup_label(ctx, type, p, label)                     \
        ((type *)tal_dup_((ctx), tal_typechk_(p, type *),       \
                          sizeof(type), 1, 0,                   \
-                         false, label))
+                         label))
 #define tal_dup_arr_label(ctx, type, p, n, extra, label)       \
        ((type *)tal_dup_((ctx), tal_typechk_(p, type *),       \
                          sizeof(type), (n), (extra),           \
-                         true, label))
+                         label))
 
 /**
  * tal_set_backend - set the allocation or error functions to use
@@ -496,14 +494,12 @@ bool tal_set_name_(tal_t *ctx, const char *name, bool literal);
 #define tal_typechk_(ptr, ptype) (ptr)
 #endif
 
-void *tal_alloc_(const tal_t *ctx, size_t bytes, bool clear,
-                bool add_length, const char *label);
+void *tal_alloc_(const tal_t *ctx, size_t bytes, bool clear, const char *label);
 void *tal_alloc_arr_(const tal_t *ctx, size_t bytes, size_t count, bool clear,
-                    bool add_length, const char *label);
+                    const char *label);
 
 void *tal_dup_(const tal_t *ctx, const void *p TAKES, size_t size,
-              size_t n, size_t extra, bool add_length,
-              const char *label);
+              size_t n, size_t extra, const char *label);
 
 tal_t *tal_steal_(const tal_t *new_parent, const tal_t *t);
 
index 54ba8c19ffe7ae486d096e4856f1dfa41dc91700..a621e1d8b7dd0fbe0c571998f817b15288e3556c 100644 (file)
@@ -54,7 +54,7 @@ int main(void)
 
                p1 = tal(NULL, char);
                ok1(p1);
-               ok1(tal_count(p1) == 0);
+               ok1(tal_count(p1) == 1);
 
                p2 = tal_arr(p1, char, 1);
                ok1(p2);