git.ozlabs.org Git - ccan/blob - ccan/tal/tal.c

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