nostrdb

an unfairly fast embedded nostr database backed by lmdb
git clone git://jb55.com/nostrdb
Log | Files | Refs | Submodules | README | LICENSE

tal.c (25669B)


      1 /* Licensed under BSD-MIT - see LICENSE file for details */
      2 #include "tal.h"
      3 #include "../compiler.h"
      4 #include "list.h"
      5 #include "alignof.h"
      6 
      7 #include <assert.h>
      8 #include <stdio.h>
      9 #include <stddef.h>
     10 #include <string.h>
     11 #include <limits.h>
     12 #include <stdint.h>
     13 #include <errno.h>
     14 
     15 //#define TAL_DEBUG 1
     16 
     17 #define NOTIFY_IS_DESTRUCTOR 512
     18 #define NOTIFY_EXTRA_ARG 1024
     19 
     20 /* This makes our parent_child ptr stand out for to_tal_hdr checks */
     21 #define TAL_PTR_OBFUSTICATOR ((intptr_t)0x1984200820142016ULL)
     22 
     23 /* 32-bit type field, first byte 0 in either endianness. */
     24 enum prop_type {
     25     CHILDREN = 0x00c1d500,
     26     NAME = 0x00111100,
     27     NOTIFIER = 0x00071f00,
     28 };
     29 
     30 struct tal_hdr {
     31     struct list_node list;
     32     struct prop_hdr *prop;
     33     /* XOR with TAL_PTR_OBFUSTICATOR */
     34     intptr_t parent_child;
     35     size_t bytelen;
     36 };
     37 
     38 struct prop_hdr {
     39     enum prop_type type;
     40     struct prop_hdr *next;
     41 };
     42 
     43 struct children {
     44     struct prop_hdr hdr; /* CHILDREN */
     45     struct tal_hdr *parent;
     46     struct list_head children; /* Head of siblings. */
     47 };
     48 
     49 struct name {
     50     struct prop_hdr hdr; /* NAME */
     51     char name[];
     52 };
     53 
     54 struct notifier {
     55     struct prop_hdr hdr; /* NOTIFIER */
     56     enum tal_notify_type types;
     57     union notifier_cb {
     58         void (*notifyfn)(tal_t *, enum tal_notify_type, void *);
     59         void (*destroy)(tal_t *); /* If NOTIFY_IS_DESTRUCTOR set */
     60         void (*destroy2)(tal_t *, void *); /* If NOTIFY_EXTRA_ARG */
     61     } u;
     62 };
     63 
     64 /* Extra arg */
     65 struct notifier_extra_arg {
     66     struct notifier n;
     67     void *arg;
     68 };
     69 
     70 #define EXTRA_ARG(n) (((struct notifier_extra_arg *)(n))->arg)
     71 
     72 static struct {
     73     struct tal_hdr hdr;
     74     struct children c;
     75 } null_parent = { { { &null_parent.hdr.list, &null_parent.hdr.list },
     76             &null_parent.c.hdr, TAL_PTR_OBFUSTICATOR, 0 },
     77           { { CHILDREN, NULL },
     78             &null_parent.hdr,
     79             { { &null_parent.c.children.n,
     80             &null_parent.c.children.n } }
     81           }
     82 };
     83 
     84 
     85 static void *(*allocfn)(size_t size) = malloc;
     86 static void *(*resizefn)(void *, size_t size) = realloc;
     87 static void (*freefn)(void *) = free;
     88 static void (*errorfn)(const char *msg) = (void *)abort;
     89 /* Count on non-destrutor notifiers; often stays zero. */
     90 static size_t notifiers = 0;
     91 
     92 static inline void COLD call_error(const char *msg)
     93 {
     94     errorfn(msg);
     95 }
     96 
     97 static bool get_destroying_bit(intptr_t parent_child)
     98 {
     99     return parent_child & 1;
    100 }
    101 
    102 static void set_destroying_bit(intptr_t *parent_child)
    103 {
    104     *parent_child |= 1;
    105 }
    106 
    107 static struct children *ignore_destroying_bit(intptr_t parent_child)
    108 {
    109     return (void *)((parent_child ^ TAL_PTR_OBFUSTICATOR) & ~(intptr_t)1);
    110 }
    111 
    112 /* This means valgrind can see leaks. */
    113 void tal_cleanup(void)
    114 {
    115     struct tal_hdr *i;
    116 
    117     while ((i = list_top(&null_parent.c.children, struct tal_hdr, list))) {
    118         list_del(&i->list);
    119         memset(i, 0, sizeof(*i));
    120     }
    121 
    122     /* Cleanup any taken pointers. */
    123     take_cleanup();
    124 }
    125 
    126 /* We carefully start all real properties with a zero byte. */
    127 static bool is_literal(const struct prop_hdr *prop)
    128 {
    129     return ((char *)prop)[0] != 0;
    130 }
    131 
    132 #ifndef NDEBUG
    133 static const void *bounds_start, *bounds_end;
    134 
    135 static void update_bounds(const void *new, size_t size)
    136 {
    137     if (unlikely(!bounds_start)) {
    138         bounds_start = new;
    139         bounds_end = (char *)new + size;
    140     } else if (new < bounds_start)
    141         bounds_start = new;
    142     else if ((char *)new + size > (char *)bounds_end)
    143         bounds_end = (char *)new + size;
    144 }
    145 
    146 static bool in_bounds(const void *p)
    147 {
    148     return !p
    149         || (p >= (void *)&null_parent && p <= (void *)(&null_parent + 1))
    150         || (p >= bounds_start && p <= bounds_end);
    151 }
    152 #else
    153 static void update_bounds(const void *new, size_t size)
    154 {
    155 }
    156 
    157 static bool in_bounds(const void *p)
    158 {
    159     return true;
    160 }
    161 #endif
    162 
    163 static void check_bounds(const void *p)
    164 {
    165     if (!in_bounds(p))
    166         call_error("Not a valid header");
    167 }
    168 
    169 static struct tal_hdr *to_tal_hdr(const void *ctx)
    170 {
    171     struct tal_hdr *t;
    172 
    173     t = (struct tal_hdr *)((char *)ctx - sizeof(struct tal_hdr));
    174     check_bounds(t);
    175     check_bounds(ignore_destroying_bit(t->parent_child));
    176     check_bounds(t->list.next);
    177     check_bounds(t->list.prev);
    178     if (t->prop && !is_literal(t->prop))
    179         check_bounds(t->prop);
    180     return t;
    181 }
    182 
    183 static struct tal_hdr *to_tal_hdr_or_null(const void *ctx)
    184 {
    185     if (!ctx)
    186         return &null_parent.hdr;
    187     return to_tal_hdr(ctx);
    188 }
    189 
    190 static void *from_tal_hdr(const struct tal_hdr *hdr)
    191 {
    192     return (void *)(hdr + 1);
    193 }
    194 
    195 static void *from_tal_hdr_or_null(const struct tal_hdr *hdr)
    196 {
    197     if (hdr == &null_parent.hdr)
    198         return NULL;
    199     return from_tal_hdr(hdr);
    200 }
    201 
    202 #ifdef TAL_DEBUG
    203 static struct tal_hdr *debug_tal(struct tal_hdr *tal)
    204 {
    205     tal_check(from_tal_hdr_or_null(tal), "TAL_DEBUG ");
    206     return tal;
    207 }
    208 #else
    209 static struct tal_hdr *debug_tal(struct tal_hdr *tal)
    210 {
    211     return tal;
    212 }
    213 #endif
    214 
    215 static void notify(const struct tal_hdr *ctx,
    216            enum tal_notify_type type, const void *info,
    217            int saved_errno)
    218 {
    219         const struct prop_hdr *p;
    220 
    221         for (p = ctx->prop; p; p = p->next) {
    222         struct notifier *n;
    223 
    224                 if (is_literal(p))
    225             break;
    226                 if (p->type != NOTIFIER)
    227             continue;
    228         n = (struct notifier *)p;
    229         if (n->types & type) {
    230             errno = saved_errno;
    231             if (n->types & NOTIFY_IS_DESTRUCTOR) {
    232                 /* Blatt this notifier in case it tries to
    233                  * tal_del_destructor() from inside */
    234                 union notifier_cb cb = n->u;
    235                 /* It's a union, so this NULLs destroy2 too! */
    236                 n->u.destroy = NULL;
    237                 if (n->types & NOTIFY_EXTRA_ARG)
    238                     cb.destroy2(from_tal_hdr(ctx),
    239                             EXTRA_ARG(n));
    240                 else
    241                     cb.destroy(from_tal_hdr(ctx));
    242             } else
    243                 n->u.notifyfn(from_tal_hdr_or_null(ctx), type,
    244                           (void *)info);
    245         }
    246     }
    247 }
    248 
    249 static void *allocate(size_t size)
    250 {
    251     void *ret = allocfn(size);
    252     if (!ret)
    253         call_error("allocation failed");
    254     else
    255         update_bounds(ret, size);
    256     return ret;
    257 }
    258 
    259 static struct prop_hdr **find_property_ptr(const struct tal_hdr *t,
    260                        enum prop_type type)
    261 {
    262         struct prop_hdr **p;
    263 
    264         for (p = (struct prop_hdr **)&t->prop; *p; p = &(*p)->next) {
    265                 if (is_literal(*p)) {
    266                         if (type == NAME)
    267                                 return p;
    268                         break;
    269                 }
    270                 if ((*p)->type == type)
    271                         return p;
    272         }
    273         return NULL;
    274 }
    275 
    276 static void *find_property(const struct tal_hdr *parent, enum prop_type type)
    277 {
    278         struct prop_hdr **p = find_property_ptr(parent, type);
    279 
    280         if (p)
    281                 return *p;
    282         return NULL;
    283 }
    284 
    285 static void init_property(struct prop_hdr *hdr,
    286               struct tal_hdr *parent,
    287               enum prop_type type)
    288 {
    289     hdr->type = type;
    290     hdr->next = parent->prop;
    291     parent->prop = hdr;
    292 }
    293 
    294 static struct notifier *add_notifier_property(struct tal_hdr *t,
    295                           enum tal_notify_type types,
    296                           void (*fn)(void *,
    297                              enum tal_notify_type,
    298                              void *),
    299                           void *extra_arg)
    300 {
    301     struct notifier *prop;
    302 
    303     if (types & NOTIFY_EXTRA_ARG)
    304         prop = allocate(sizeof(struct notifier_extra_arg));
    305     else
    306         prop = allocate(sizeof(struct notifier));
    307 
    308     if (prop) {
    309         init_property(&prop->hdr, t, NOTIFIER);
    310         prop->types = types;
    311         prop->u.notifyfn = fn;
    312         if (types & NOTIFY_EXTRA_ARG)
    313             EXTRA_ARG(prop) = extra_arg;
    314     }
    315     return prop;
    316 }
    317 
    318 static enum tal_notify_type del_notifier_property(struct tal_hdr *t,
    319                           void (*fn)(tal_t *,
    320                                  enum tal_notify_type,
    321                                  void *),
    322                           bool match_extra_arg,
    323                           void *extra_arg)
    324 {
    325         struct prop_hdr **p;
    326 
    327         for (p = (struct prop_hdr **)&t->prop; *p; p = &(*p)->next) {
    328         struct notifier *n;
    329         enum tal_notify_type types;
    330 
    331                 if (is_literal(*p))
    332             break;
    333                 if ((*p)->type != NOTIFIER)
    334             continue;
    335         n = (struct notifier *)*p;
    336         if (n->u.notifyfn != fn)
    337             continue;
    338 
    339         types = n->types;
    340         if ((types & NOTIFY_EXTRA_ARG)
    341             && match_extra_arg
    342             && extra_arg != EXTRA_ARG(n))
    343             continue;
    344 
    345         *p = (*p)->next;
    346         freefn(n);
    347         return types & ~(NOTIFY_IS_DESTRUCTOR|NOTIFY_EXTRA_ARG);
    348         }
    349         return 0;
    350 }
    351 
    352 static struct name *add_name_property(struct tal_hdr *t, const char *name)
    353 {
    354     struct name *prop;
    355 
    356     prop = allocate(sizeof(*prop) + strlen(name) + 1);
    357     if (prop) {
    358         init_property(&prop->hdr, t, NAME);
    359         strcpy(prop->name, name);
    360     }
    361     return prop;
    362 }
    363 
    364 static struct children *add_child_property(struct tal_hdr *parent,
    365                        struct tal_hdr *child UNNEEDED)
    366 {
    367     struct children *prop = allocate(sizeof(*prop));
    368     if (prop) {
    369         init_property(&prop->hdr, parent, CHILDREN);
    370         prop->parent = parent;
    371         list_head_init(&prop->children);
    372     }
    373     return prop;
    374 }
    375 
    376 static bool add_child(struct tal_hdr *parent, struct tal_hdr *child)
    377 {
    378     struct children *children = find_property(parent, CHILDREN);
    379 
    380         if (!children) {
    381         children = add_child_property(parent, child);
    382         if (!children)
    383             return false;
    384     }
    385     list_add(&children->children, &child->list);
    386     child->parent_child = (intptr_t)children ^ TAL_PTR_OBFUSTICATOR;
    387     return true;
    388 }
    389 
    390 static void del_tree(struct tal_hdr *t, const tal_t *orig, int saved_errno)
    391 {
    392     struct prop_hdr **prop, *p, *next;
    393 
    394     assert(!taken(from_tal_hdr(t)));
    395 
    396         /* Already being destroyed?  Don't loop. */
    397         if (unlikely(get_destroying_bit(t->parent_child)))
    398                 return;
    399 
    400         set_destroying_bit(&t->parent_child);
    401 
    402     /* Call free notifiers. */
    403     notify(t, TAL_NOTIFY_FREE, (tal_t *)orig, saved_errno);
    404 
    405     /* Now free children and groups. */
    406     prop = find_property_ptr(t, CHILDREN);
    407     if (prop) {
    408         struct tal_hdr *i;
    409         struct children *c = (struct children *)*prop;
    410 
    411         while ((i = list_top(&c->children, struct tal_hdr, list))) {
    412             list_del(&i->list);
    413             del_tree(i, orig, saved_errno);
    414         }
    415     }
    416 
    417         /* Finally free our properties. */
    418         for (p = t->prop; p && !is_literal(p); p = next) {
    419                 next = p->next;
    420         freefn(p);
    421         }
    422         freefn(t);
    423 }
    424 
    425 void *tal_alloc_(const tal_t *ctx, size_t size, bool clear, const char *label)
    426 {
    427         struct tal_hdr *child, *parent = debug_tal(to_tal_hdr_or_null(ctx));
    428 
    429         child = allocate(sizeof(struct tal_hdr) + size);
    430     if (!child)
    431         return NULL;
    432     if (clear)
    433         memset(from_tal_hdr(child), 0, size);
    434         child->prop = (void *)label;
    435     child->bytelen = size;
    436 
    437         if (!add_child(parent, child)) {
    438         freefn(child);
    439         return NULL;
    440     }
    441     debug_tal(parent);
    442     if (notifiers)
    443         notify(parent, TAL_NOTIFY_ADD_CHILD, from_tal_hdr(child), 0);
    444     return from_tal_hdr(debug_tal(child));
    445 }
    446 
    447 static bool adjust_size(size_t *size, size_t count)
    448 {
    449     const size_t extra = sizeof(struct tal_hdr);
    450 
    451     /* Multiplication wrap */
    452         if (count && unlikely(*size * count / *size != count))
    453         goto overflow;
    454 
    455         *size *= count;
    456 
    457         /* Make sure we don't wrap adding header. */
    458         if (*size + extra < extra)
    459         goto overflow;
    460     return true;
    461 overflow:
    462     call_error("allocation size overflow");
    463     return false;
    464 }
    465 
    466 void *tal_alloc_arr_(const tal_t *ctx, size_t size, size_t count, bool clear,
    467              const char *label)
    468 {
    469     if (!adjust_size(&size, count))
    470         return NULL;
    471 
    472     return tal_alloc_(ctx, size, clear, label);
    473 }
    474 
    475 void *tal_free(const tal_t *ctx)
    476 {
    477         if (ctx) {
    478         struct tal_hdr *t;
    479         int saved_errno = errno;
    480         t = debug_tal(to_tal_hdr(ctx));
    481         if (unlikely(get_destroying_bit(t->parent_child)))
    482             return NULL;
    483         if (notifiers)
    484             notify(ignore_destroying_bit(t->parent_child)->parent,
    485                    TAL_NOTIFY_DEL_CHILD, ctx, saved_errno);
    486         list_del(&t->list);
    487         del_tree(t, ctx, saved_errno);
    488         errno = saved_errno;
    489     }
    490     return NULL;
    491 }
    492 
    493 void *tal_steal_(const tal_t *new_parent, const tal_t *ctx)
    494 {
    495         if (ctx) {
    496         struct tal_hdr *newpar, *t, *old_parent;
    497 
    498                 newpar = debug_tal(to_tal_hdr_or_null(new_parent));
    499                 t = debug_tal(to_tal_hdr(ctx));
    500 
    501                 /* Unlink it from old parent. */
    502         list_del(&t->list);
    503         old_parent = ignore_destroying_bit(t->parent_child)->parent;
    504 
    505                 if (unlikely(!add_child(newpar, t))) {
    506             /* We can always add to old parent, because it has a
    507              * children property already. */
    508             if (!add_child(old_parent, t))
    509                 abort();
    510             return NULL;
    511         }
    512         debug_tal(newpar);
    513         if (notifiers)
    514             notify(t, TAL_NOTIFY_STEAL, new_parent, 0);
    515         }
    516         return (void *)ctx;
    517 }
    518 
    519 bool tal_add_destructor_(const tal_t *ctx, void (*destroy)(void *me))
    520 {
    521     tal_t *t = debug_tal(to_tal_hdr(ctx));
    522     return add_notifier_property(t, TAL_NOTIFY_FREE|NOTIFY_IS_DESTRUCTOR,
    523                      (void *)destroy, NULL);
    524 }
    525 
    526 bool tal_add_destructor2_(const tal_t *ctx, void (*destroy)(void *me, void *arg),
    527               void *arg)
    528 {
    529     tal_t *t = debug_tal(to_tal_hdr(ctx));
    530     return add_notifier_property(t, TAL_NOTIFY_FREE|NOTIFY_IS_DESTRUCTOR
    531                      |NOTIFY_EXTRA_ARG,
    532                      (void *)destroy, arg);
    533 }
    534 
    535 /* We could support notifiers with an extra arg, but we didn't add to API */
    536 bool tal_add_notifier_(const tal_t *ctx, enum tal_notify_type types,
    537                void (*callback)(tal_t *, enum tal_notify_type, void *))
    538 {
    539     struct tal_hdr *t = debug_tal(to_tal_hdr_or_null(ctx));
    540     struct notifier *n;
    541 
    542     assert(types);
    543     assert((types & ~(TAL_NOTIFY_FREE | TAL_NOTIFY_STEAL | TAL_NOTIFY_MOVE
    544               | TAL_NOTIFY_RESIZE | TAL_NOTIFY_RENAME
    545               | TAL_NOTIFY_ADD_CHILD | TAL_NOTIFY_DEL_CHILD
    546               | TAL_NOTIFY_ADD_NOTIFIER
    547               | TAL_NOTIFY_DEL_NOTIFIER)) == 0);
    548 
    549     /* Don't call notifier about itself: set types after! */
    550         n = add_notifier_property(t, 0, callback, NULL);
    551     if (unlikely(!n))
    552         return false;
    553 
    554     if (notifiers)
    555         notify(t, TAL_NOTIFY_ADD_NOTIFIER, callback, 0);
    556 
    557     n->types = types;
    558     if (types != TAL_NOTIFY_FREE)
    559         notifiers++;
    560     return true;
    561 }
    562 
    563 bool tal_del_notifier_(const tal_t *ctx,
    564                void (*callback)(tal_t *, enum tal_notify_type, void *),
    565                bool match_extra_arg, void *extra_arg)
    566 {
    567     struct tal_hdr *t = debug_tal(to_tal_hdr_or_null(ctx));
    568     enum tal_notify_type types;
    569 
    570         types = del_notifier_property(t, callback, match_extra_arg, extra_arg);
    571     if (types) {
    572         notify(t, TAL_NOTIFY_DEL_NOTIFIER, callback, 0);
    573         if (types != TAL_NOTIFY_FREE)
    574             notifiers--;
    575         return true;
    576     }
    577     return false;
    578 }
    579 
    580 bool tal_del_destructor_(const tal_t *ctx, void (*destroy)(void *me))
    581 {
    582     return tal_del_notifier_(ctx, (void *)destroy, false, NULL);
    583 }
    584 
    585 bool tal_del_destructor2_(const tal_t *ctx, void (*destroy)(void *me, void *arg),
    586               void *arg)
    587 {
    588     return tal_del_notifier_(ctx, (void *)destroy, true, arg);
    589 }
    590 
    591 bool tal_set_name_(tal_t *ctx, const char *name, bool literal)
    592 {
    593         struct tal_hdr *t = debug_tal(to_tal_hdr(ctx));
    594         struct prop_hdr **prop = find_property_ptr(t, NAME);
    595 
    596         /* Get rid of any old name */
    597         if (prop) {
    598                 struct name *name = (struct name *)*prop;
    599                 if (is_literal(&name->hdr))
    600                         *prop = NULL;
    601                 else {
    602                         *prop = name->hdr.next;
    603             freefn(name);
    604                 }
    605         }
    606 
    607         if (literal && name[0]) {
    608                 struct prop_hdr **p;
    609 
    610                 /* Append literal. */
    611                 for (p = &t->prop; *p && !is_literal(*p); p = &(*p)->next);
    612                 *p = (struct prop_hdr *)name;
    613         } else if (!add_name_property(t, name))
    614         return false;
    615 
    616     debug_tal(t);
    617     if (notifiers)
    618         notify(t, TAL_NOTIFY_RENAME, name, 0);
    619     return true;
    620 }
    621 
    622 const char *tal_name(const tal_t *t)
    623 {
    624         struct name *n;
    625 
    626     n = find_property(debug_tal(to_tal_hdr(t)), NAME);
    627     if (!n)
    628         return NULL;
    629 
    630     if (is_literal(&n->hdr))
    631         return (const char *)n;
    632     return n->name;
    633 }
    634 
    635 size_t tal_bytelen(const tal_t *ptr)
    636 {
    637     /* NULL -> null_parent which has bytelen 0 */
    638     struct tal_hdr *t = debug_tal(to_tal_hdr_or_null(ptr));
    639 
    640     return t->bytelen;
    641 }
    642 
    643 /* Start one past first child: make stopping natural in circ. list. */
    644 static struct tal_hdr *first_child(struct tal_hdr *parent)
    645 {
    646     struct children *child;
    647 
    648     child = find_property(parent, CHILDREN);
    649         if (!child)
    650                 return NULL;
    651 
    652     return list_top(&child->children, struct tal_hdr, list);
    653 }
    654 
    655 tal_t *tal_first(const tal_t *root)
    656 {
    657         struct tal_hdr *c, *t = debug_tal(to_tal_hdr_or_null(root));
    658 
    659     c = first_child(t);
    660     if (!c)
    661         return NULL;
    662     return from_tal_hdr(c);
    663 }
    664 
    665 tal_t *tal_next(const tal_t *prev)
    666 {
    667         struct tal_hdr *next, *prevhdr = debug_tal(to_tal_hdr(prev));
    668     struct list_head *head;
    669 
    670     head = &ignore_destroying_bit(prevhdr->parent_child)->children;
    671     next = list_next(head, prevhdr, list);
    672     if (!next)
    673         return NULL;
    674     return from_tal_hdr(next);
    675 }
    676 
    677 tal_t *tal_parent(const tal_t *ctx)
    678 {
    679         struct tal_hdr *t;
    680 
    681     if (!ctx)
    682         return NULL;
    683 
    684     t = debug_tal(to_tal_hdr(ctx));
    685     if (ignore_destroying_bit(t->parent_child)->parent == &null_parent.hdr)
    686         return NULL;
    687         return from_tal_hdr(ignore_destroying_bit(t->parent_child)->parent);
    688 }
    689 
    690 bool tal_resize_(tal_t **ctxp, size_t size, size_t count, bool clear)
    691 {
    692         struct tal_hdr *old_t, *t;
    693         struct children *child;
    694 
    695         old_t = debug_tal(to_tal_hdr(*ctxp));
    696 
    697     if (!adjust_size(&size, count))
    698         return false;
    699 
    700         t = resizefn(old_t, sizeof(struct tal_hdr) + size);
    701     if (!t) {
    702         call_error("Reallocation failure");
    703         return false;
    704     }
    705 
    706     /* Clear between old end and new end. */
    707     if (clear && size > t->bytelen) {
    708         char *old_end = (char *)(t + 1) + t->bytelen;
    709         memset(old_end, 0, size - t->bytelen);
    710     }
    711 
    712     /* Update length. */
    713     t->bytelen = size;
    714     update_bounds(t, sizeof(struct tal_hdr) + size);
    715 
    716     /* If it didn't move, we're done! */
    717         if (t != old_t) {
    718         /* Fix up linked list pointers. */
    719         t->list.next->prev = t->list.prev->next = &t->list;
    720 
    721         /* Copy take() property. */
    722         if (taken(from_tal_hdr(old_t)))
    723             take(from_tal_hdr(t));
    724 
    725         /* Fix up child property's parent pointer. */
    726         child = find_property(t, CHILDREN);
    727         if (child) {
    728             assert(child->parent == old_t);
    729             child->parent = t;
    730         }
    731         *ctxp = from_tal_hdr(debug_tal(t));
    732         if (notifiers)
    733             notify(t, TAL_NOTIFY_MOVE, from_tal_hdr(old_t), 0);
    734     }
    735     if (notifiers)
    736         notify(t, TAL_NOTIFY_RESIZE, (void *)size, 0);
    737 
    738     return true;
    739 }
    740 
    741 bool tal_expand_(tal_t **ctxp, const void *src, size_t size, size_t count)
    742 {
    743     size_t old_len;
    744     bool ret = false;
    745 
    746     old_len = debug_tal(to_tal_hdr(*ctxp))->bytelen;
    747 
    748     /* Check for additive overflow */
    749     if (old_len + count * size < old_len) {
    750         call_error("dup size overflow");
    751         goto out;
    752     }
    753 
    754     /* Don't point src inside thing we're expanding! */
    755     assert(src < *ctxp
    756            || (char *)src >= (char *)(*ctxp) + old_len);
    757 
    758     if (!tal_resize_(ctxp, size, old_len/size + count, false))
    759         goto out;
    760 
    761     memcpy((char *)*ctxp + old_len, src, count * size);
    762     ret = true;
    763 
    764 out:
    765     if (taken(src))
    766         tal_free(src);
    767     return ret;
    768 }
    769 
    770 void *tal_dup_(const tal_t *ctx, const void *p, size_t size,
    771            size_t n, size_t extra, bool nullok, const char *label)
    772 {
    773     void *ret;
    774     size_t nbytes = size;
    775 
    776     if (nullok && p == NULL) {
    777         /* take(NULL) works. */
    778         (void)taken(p);
    779         return NULL;
    780     }
    781 
    782     if (!adjust_size(&nbytes, n)) {
    783         if (taken(p))
    784             tal_free(p);
    785         return NULL;
    786     }
    787 
    788     /* Beware addition overflow! */
    789     if (n + extra < n) {
    790         call_error("dup size overflow");
    791         if (taken(p))
    792             tal_free(p);
    793         return NULL;
    794     }
    795 
    796     if (taken(p)) {
    797         if (unlikely(!p))
    798             return NULL;
    799         if (unlikely(!tal_resize_((void **)&p, size, n + extra, false)))
    800             return tal_free(p);
    801         if (unlikely(!tal_steal(ctx, p)))
    802             return tal_free(p);
    803         return (void *)p;
    804     }
    805 
    806     ret = tal_alloc_arr_(ctx, size, n + extra, false, label);
    807     if (ret)
    808         memcpy(ret, p, nbytes);
    809     return ret;
    810 }
    811 
    812 void *tal_dup_talarr_(const tal_t *ctx, const tal_t *src TAKES, const char *label)
    813 {
    814     return tal_dup_(ctx, src, 1, tal_bytelen(src), 0, true, label);
    815 }
    816 
    817 void tal_set_backend(void *(*alloc_fn)(size_t size),
    818              void *(*resize_fn)(void *, size_t size),
    819              void (*free_fn)(void *),
    820              void (*error_fn)(const char *msg))
    821 {
    822     if (alloc_fn)
    823         allocfn = alloc_fn;
    824     if (resize_fn)
    825         resizefn = resize_fn;
    826     if (free_fn)
    827         freefn = free_fn;
    828     if (error_fn)
    829         errorfn = error_fn;
    830 }
    831 
    832 #ifdef CCAN_TAL_DEBUG
    833 static void dump_node(unsigned int indent, const struct tal_hdr *t)
    834 {
    835     unsigned int i;
    836         const struct prop_hdr *p;
    837 
    838     for (i = 0; i < indent; i++)
    839         fprintf(stderr, "  ");
    840     fprintf(stderr, "%p len=%zu", t, t->bytelen);
    841         for (p = t->prop; p; p = p->next) {
    842         struct children *c;
    843         struct name *n;
    844         struct notifier *no;
    845                 if (is_literal(p)) {
    846             fprintf(stderr, " \"%s\"", (const char *)p);
    847             break;
    848         }
    849         switch (p->type) {
    850         case CHILDREN:
    851             c = (struct children *)p;
    852             fprintf(stderr, " CHILDREN(%p):parent=%p,children={%p,%p}",
    853                    p, c->parent,
    854                    c->children.n.prev, c->children.n.next);
    855             break;
    856         case NAME:
    857             n = (struct name *)p;
    858             fprintf(stderr, " NAME(%p):%s", p, n->name);
    859             break;
    860         case NOTIFIER:
    861             no = (struct notifier *)p;
    862             fprintf(stderr, " NOTIFIER(%p):fn=%p", p, no->u.notifyfn);
    863             break;
    864         default:
    865             fprintf(stderr, " **UNKNOWN(%p):%i**", p, p->type);
    866         }
    867     }
    868     fprintf(stderr, "\n");
    869 }
    870 
    871 static void tal_dump_(unsigned int level, const struct tal_hdr *t)
    872 {
    873         struct children *children;
    874 
    875     dump_node(level, t);
    876 
    877     children = find_property(t, CHILDREN);
    878     if (children) {
    879         struct tal_hdr *i;
    880 
    881         list_for_each(&children->children, i, list)
    882             tal_dump_(level + 1, i);
    883     }
    884 }
    885 
    886 void tal_dump(void)
    887 {
    888     tal_dump_(0, &null_parent.hdr);
    889 }
    890 #endif /* CCAN_TAL_DEBUG */
    891 
    892 #ifndef NDEBUG
    893 static bool check_err(struct tal_hdr *t, const char *errorstr,
    894               const char *errmsg)
    895 {
    896     if (errorstr) {
    897         /* Try not to malloc: it may be corrupted. */
    898         char msg[strlen(errorstr) + 20 + strlen(errmsg) + 1];
    899         sprintf(msg, "%s:%p %s", errorstr, from_tal_hdr(t), errmsg);
    900         call_error(msg);
    901     }
    902     return false;
    903 }
    904 
    905 static bool check_node(struct children *parent_child,
    906                struct tal_hdr *t, const char *errorstr)
    907 {
    908     struct prop_hdr *p;
    909     struct name *name = NULL;
    910     struct children *children = NULL;
    911 
    912     if (!in_bounds(t))
    913         return check_err(t, errorstr, "invalid pointer");
    914 
    915     if (ignore_destroying_bit(t->parent_child) != parent_child)
    916         return check_err(t, errorstr, "incorrect parent");
    917 
    918     for (p = t->prop; p; p = p->next) {
    919         if (is_literal(p)) {
    920             if (name)
    921                 return check_err(t, errorstr,
    922                          "has extra literal");
    923             break;
    924         }
    925         if (!in_bounds(p))
    926             return check_err(t, errorstr,
    927                      "has bad property pointer");
    928 
    929         switch (p->type) {
    930         case CHILDREN:
    931             if (children)
    932                 return check_err(t, errorstr,
    933                          "has two child nodes");
    934             children = (struct children *)p;
    935             break;
    936         case NOTIFIER:
    937             break;
    938         case NAME:
    939             if (name)
    940                 return check_err(t, errorstr,
    941                          "has two names");
    942             name = (struct name *)p;
    943             break;
    944         default:
    945             return check_err(t, errorstr, "has unknown property");
    946         }
    947     }
    948     if (children) {
    949         struct tal_hdr *i;
    950 
    951         if (!list_check(&children->children, errorstr))
    952             return false;
    953         list_for_each(&children->children, i, list) {
    954             if (!check_node(children, i, errorstr))
    955                 return false;
    956         }
    957     }
    958     return true;
    959 }
    960 
    961 bool tal_check(const tal_t *ctx, const char *errorstr)
    962 {
    963     struct tal_hdr *t = to_tal_hdr_or_null(ctx);
    964 
    965     return check_node(ignore_destroying_bit(t->parent_child), t, errorstr);
    966 }
    967 #else /* NDEBUG */
    968 bool tal_check(const tal_t *ctx, const char *errorstr)
    969 {
    970     return true;
    971 }
    972 #endif