src/util/ralloc.c

   1 /*
   2  * Copyright © 2010 Intel Corporation
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice (including the next
  12  * paragraph) shall be included in all copies or substantial portions of the
  13  * Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  21  * DEALINGS IN THE SOFTWARE.
  22  */
  23
  24 #include <assert.h>
  25 #include <stdlib.h>
  26 #include <stdarg.h>
  27 #include <stdio.h>
  28 #include <string.h>
  29 #include <stdint.h>
  30
  31 /* Some versions of MinGW are missing _vscprintf's declaration, although they
  32  * still provide the symbol in the import library. */
  33 #ifdef __MINGW32__
  34 _CRTIMP int _vscprintf(const char *format, va_list argptr);
  35 #endif
  36
  37 #include "ralloc.h"
  38
  39 #ifndef va_copy
  40 #ifdef __va_copy
  41 #define va_copy(dest, src) __va_copy((dest), (src))
  42 #else
  43 #define va_copy(dest, src) (dest) = (src)
  44 #endif
  45 #endif
  46
  47 #define CANARY 0x5A1106
  48
  49 /* Align the header's size so that ralloc() allocations will return with the
  50  * same alignment as a libc malloc would have (8 on 32-bit GLIBC, 16 on
  51  * 64-bit), avoiding performance penalities on x86 and alignment faults on
  52  * ARM.
  53  */
  54 struct
  55 #ifdef _MSC_VER
  56 #if _WIN64
  57 __declspec(align(16))
  58 #else
  59  __declspec(align(8))
  60 #endif
  61 #elif defined(__LP64__)
  62  __attribute__((aligned(16)))
  63 #else
  64  __attribute__((aligned(8)))
  65 #endif
  66    ralloc_header
  67 {
  68 #ifndef NDEBUG
  69    /* A canary value used to determine whether a pointer is ralloc'd. */
  70    unsigned canary;
  71 #endif
  72
  73    struct ralloc_header *parent;
  74
  75    /* The first child (head of a linked list) */
  76    struct ralloc_header *child;
  77
  78    /* Linked list of siblings */
  79    struct ralloc_header *prev;
  80    struct ralloc_header *next;
  81
  82    void (*destructor)(void *);
  83 };
  84
  85 typedef struct ralloc_header ralloc_header;
  86
  87 static void unlink_block(ralloc_header *info);
  88 static void unsafe_free(ralloc_header *info);
  89
  90 static ralloc_header *
  91 get_header(const void *ptr)
  92 {
  93    ralloc_header *info = (ralloc_header *) (((char *) ptr) -
  94                                             sizeof(ralloc_header));
  95    assert(info->canary == CANARY);
  96    return info;
  97 }
  98
  99 #define PTR_FROM_HEADER(info) (((char *) info) + sizeof(ralloc_header))
 100
 101 static void
 102 add_child(ralloc_header *parent, ralloc_header *info)
 103 {
 104    if (parent != NULL) {
 105       info->parent = parent;
 106       info->next = parent->child;
 107       parent->child = info;
 108
 109       if (info->next != NULL)
 110          info->next->prev = info;
 111    }
 112 }
 113
 114 void *
 115 ralloc_context(const void *ctx)
 116 {
 117    return ralloc_size(ctx, 0);
 118 }
 119
 120 void *
 121 ralloc_size(const void *ctx, size_t size)
 122 {
 123    void *block = malloc(size + sizeof(ralloc_header));
 124    ralloc_header *info;
 125    ralloc_header *parent;
 126
 127    if (unlikely(block == NULL))
 128       return NULL;
 129
 130    info = (ralloc_header *) block;
 131    /* measurements have shown that calloc is slower (because of
 132     * the multiplication overflow checking?), so clear things
 133     * manually
 134     */
 135    info->parent = NULL;
 136    info->child = NULL;
 137    info->prev = NULL;
 138    info->next = NULL;
 139    info->destructor = NULL;
 140
 141    parent = ctx != NULL ? get_header(ctx) : NULL;
 142
 143    add_child(parent, info);
 144
 145 #ifndef NDEBUG
 146    info->canary = CANARY;
 147 #endif
 148
 149    return PTR_FROM_HEADER(info);
 150 }
 151
 152 void *
 153 rzalloc_size(const void *ctx, size_t size)
 154 {
 155    void *ptr = ralloc_size(ctx, size);
 156
 157    if (likely(ptr))
 158       memset(ptr, 0, size);
 159
 160    return ptr;
 161 }
 162
 163 /* helper function - assumes ptr != NULL */
 164 static void *
 165 resize(void *ptr, size_t size)
 166 {
 167    ralloc_header *child, *old, *info;
 168
 169    old = get_header(ptr);
 170    info = realloc(old, size + sizeof(ralloc_header));
 171
 172    if (info == NULL)
 173       return NULL;
 174
 175    /* Update parent and sibling's links to the reallocated node. */
 176    if (info != old && info->parent != NULL) {
 177       if (info->parent->child == old)
 178          info->parent->child = info;
 179
 180       if (info->prev != NULL)
 181          info->prev->next = info;
 182
 183       if (info->next != NULL)
 184          info->next->prev = info;
 185    }
 186
 187    /* Update child->parent links for all children */
 188    for (child = info->child; child != NULL; child = child->next)
 189       child->parent = info;
 190
 191    return PTR_FROM_HEADER(info);
 192 }
 193
 194 void *
 195 reralloc_size(const void *ctx, void *ptr, size_t size)
 196 {
 197    if (unlikely(ptr == NULL))
 198       return ralloc_size(ctx, size);
 199
 200    assert(ralloc_parent(ptr) == ctx);
 201    return resize(ptr, size);
 202 }
 203
 204 void *
 205 rerzalloc_size(const void *ctx, void *ptr, size_t old_size, size_t new_size)
 206 {
 207    if (unlikely(ptr == NULL))
 208       return rzalloc_size(ctx, new_size);
 209
 210    assert(ralloc_parent(ptr) == ctx);
 211    ptr = resize(ptr, new_size);
 212
 213    if (new_size > old_size)
 214       memset((char *)ptr + old_size, 0, new_size - old_size);
 215
 216    return ptr;
 217 }
 218
 219 void *
 220 ralloc_array_size(const void *ctx, size_t size, unsigned count)
 221 {
 222    if (count > SIZE_MAX/size)
 223       return NULL;
 224
 225    return ralloc_size(ctx, size * count);
 226 }
 227
 228 void *
 229 rzalloc_array_size(const void *ctx, size_t size, unsigned count)
 230 {
 231    if (count > SIZE_MAX/size)
 232       return NULL;
 233
 234    return rzalloc_size(ctx, size * count);
 235 }
 236
 237 void *
 238 reralloc_array_size(const void *ctx, void *ptr, size_t size, unsigned count)
 239 {
 240    if (count > SIZE_MAX/size)
 241       return NULL;
 242
 243    return reralloc_size(ctx, ptr, size * count);
 244 }
 245
 246 void *
 247 rerzalloc_array_size(const void *ctx, void *ptr, size_t size,
 248                      unsigned old_count, unsigned new_count)
 249 {
 250    if (new_count > SIZE_MAX/size)
 251       return NULL;
 252
 253    return rerzalloc_size(ctx, ptr, size * old_count, size * new_count);
 254 }
 255
 256 void
 257 ralloc_free(void *ptr)
 258 {
 259    ralloc_header *info;
 260
 261    if (ptr == NULL)
 262       return;
 263
 264    info = get_header(ptr);
 265    unlink_block(info);
 266    unsafe_free(info);
 267 }
 268
 269 static void
 270 unlink_block(ralloc_header *info)
 271 {
 272    /* Unlink from parent & siblings */
 273    if (info->parent != NULL) {
 274       if (info->parent->child == info)
 275          info->parent->child = info->next;
 276
 277       if (info->prev != NULL)
 278          info->prev->next = info->next;
 279
 280       if (info->next != NULL)
 281          info->next->prev = info->prev;
 282    }
 283    info->parent = NULL;
 284    info->prev = NULL;
 285    info->next = NULL;
 286 }
 287
 288 static void
 289 unsafe_free(ralloc_header *info)
 290 {
 291    /* Recursively free any children...don't waste time unlinking them. */
 292    ralloc_header *temp;
 293    while (info->child != NULL) {
 294       temp = info->child;
 295       info->child = temp->next;
 296       unsafe_free(temp);
 297    }
 298
 299    /* Free the block itself.  Call the destructor first, if any. */
 300    if (info->destructor != NULL)
 301       info->destructor(PTR_FROM_HEADER(info));
 302
 303    free(info);
 304 }
 305
 306 void
 307 ralloc_steal(const void *new_ctx, void *ptr)
 308 {
 309    ralloc_header *info, *parent;
 310
 311    if (unlikely(ptr == NULL))
 312       return;
 313
 314    info = get_header(ptr);
 315    parent = new_ctx ? get_header(new_ctx) : NULL;
 316
 317    unlink_block(info);
 318
 319    add_child(parent, info);
 320 }
 321
 322 void
 323 ralloc_adopt(const void *new_ctx, void *old_ctx)
 324 {
 325    ralloc_header *new_info, *old_info, *child;
 326
 327    if (unlikely(old_ctx == NULL))
 328       return;
 329
 330    old_info = get_header(old_ctx);
 331    new_info = get_header(new_ctx);
 332
 333    /* If there are no children, bail. */
 334    if (unlikely(old_info->child == NULL))
 335       return;
 336
 337    /* Set all the children's parent to new_ctx; get a pointer to the last child. */
 338    for (child = old_info->child; child->next != NULL; child = child->next) {
 339       child->parent = new_info;
 340    }
 341    child->parent = new_info;
 342
 343    /* Connect the two lists together; parent them to new_ctx; make old_ctx empty. */
 344    child->next = new_info->child;
 345    if (child->next)
 346       child->next->prev = child;
 347    new_info->child = old_info->child;
 348    old_info->child = NULL;
 349 }
 350
 351 void *
 352 ralloc_parent(const void *ptr)
 353 {
 354    ralloc_header *info;
 355
 356    if (unlikely(ptr == NULL))
 357       return NULL;
 358
 359    info = get_header(ptr);
 360    return info->parent ? PTR_FROM_HEADER(info->parent) : NULL;
 361 }
 362
 363 void
 364 ralloc_set_destructor(const void *ptr, void(*destructor)(void *))
 365 {
 366    ralloc_header *info = get_header(ptr);
 367    info->destructor = destructor;
 368 }
 369
 370 char *
 371 ralloc_strdup(const void *ctx, const char *str)
 372 {
 373    size_t n;
 374    char *ptr;
 375
 376    if (unlikely(str == NULL))
 377       return NULL;
 378
 379    n = strlen(str);
 380    ptr = ralloc_array(ctx, char, n + 1);
 381    memcpy(ptr, str, n);
 382    ptr[n] = '\0';
 383    return ptr;
 384 }
 385
 386 char *
 387 ralloc_strndup(const void *ctx, const char *str, size_t max)
 388 {
 389    size_t n;
 390    char *ptr;
 391
 392    if (unlikely(str == NULL))
 393       return NULL;
 394
 395    n = strnlen(str, max);
 396    ptr = ralloc_array(ctx, char, n + 1);
 397    memcpy(ptr, str, n);
 398    ptr[n] = '\0';
 399    return ptr;
 400 }
 401
 402 /* helper routine for strcat/strncat - n is the exact amount to copy */
 403 static bool
 404 cat(char **dest, const char *str, size_t n)
 405 {
 406    char *both;
 407    size_t existing_length;
 408    assert(dest != NULL && *dest != NULL);
 409
 410    existing_length = strlen(*dest);
 411    both = resize(*dest, existing_length + n + 1);
 412    if (unlikely(both == NULL))
 413       return false;
 414
 415    memcpy(both + existing_length, str, n);
 416    both[existing_length + n] = '\0';
 417
 418    *dest = both;
 419    return true;
 420 }
 421
 422
 423 bool
 424 ralloc_strcat(char **dest, const char *str)
 425 {
 426    return cat(dest, str, strlen(str));
 427 }
 428
 429 bool
 430 ralloc_strncat(char **dest, const char *str, size_t n)
 431 {
 432    return cat(dest, str, strnlen(str, n));
 433 }
 434
 435 bool
 436 ralloc_str_append(char **dest, const char *str,
 437                   size_t existing_length, size_t str_size)
 438 {
 439    char *both;
 440    assert(dest != NULL && *dest != NULL);
 441
 442    both = resize(*dest, existing_length + str_size + 1);
 443    if (unlikely(both == NULL))
 444       return false;
 445
 446    memcpy(both + existing_length, str, str_size);
 447    both[existing_length + str_size] = '\0';
 448
 449    *dest = both;
 450
 451    return true;
 452 }
 453
 454 char *
 455 ralloc_asprintf(const void *ctx, const char *fmt, ...)
 456 {
 457    char *ptr;
 458    va_list args;
 459    va_start(args, fmt);
 460    ptr = ralloc_vasprintf(ctx, fmt, args);
 461    va_end(args);
 462    return ptr;
 463 }
 464
 465 /* Return the length of the string that would be generated by a printf-style
 466  * format and argument list, not including the \0 byte.
 467  */
 468 static size_t
 469 printf_length(const char *fmt, va_list untouched_args)
 470 {
 471    int size;
 472    char junk;
 473
 474    /* Make a copy of the va_list so the original caller can still use it */
 475    va_list args;
 476    va_copy(args, untouched_args);
 477
 478 #ifdef _WIN32
 479    /* We need to use _vcsprintf to calculate the size as vsnprintf returns -1
 480     * if the number of characters to write is greater than count.
 481     */
 482    size = _vscprintf(fmt, args);
 483    (void)junk;
 484 #else
 485    size = vsnprintf(&junk, 1, fmt, args);
 486 #endif
 487    assert(size >= 0);
 488
 489    va_end(args);
 490
 491    return size;
 492 }
 493
 494 char *
 495 ralloc_vasprintf(const void *ctx, const char *fmt, va_list args)
 496 {
 497    size_t size = printf_length(fmt, args) + 1;
 498
 499    char *ptr = ralloc_size(ctx, size);
 500    if (ptr != NULL)
 501       vsnprintf(ptr, size, fmt, args);
 502
 503    return ptr;
 504 }
 505
 506 bool
 507 ralloc_asprintf_append(char **str, const char *fmt, ...)
 508 {
 509    bool success;
 510    va_list args;
 511    va_start(args, fmt);
 512    success = ralloc_vasprintf_append(str, fmt, args);
 513    va_end(args);
 514    return success;
 515 }
 516
 517 bool
 518 ralloc_vasprintf_append(char **str, const char *fmt, va_list args)
 519 {
 520    size_t existing_length;
 521    assert(str != NULL);
 522    existing_length = *str ? strlen(*str) : 0;
 523    return ralloc_vasprintf_rewrite_tail(str, &existing_length, fmt, args);
 524 }
 525
 526 bool
 527 ralloc_asprintf_rewrite_tail(char **str, size_t *start, const char *fmt, ...)
 528 {
 529    bool success;
 530    va_list args;
 531    va_start(args, fmt);
 532    success = ralloc_vasprintf_rewrite_tail(str, start, fmt, args);
 533    va_end(args);
 534    return success;
 535 }
 536
 537 bool
 538 ralloc_vasprintf_rewrite_tail(char **str, size_t *start, const char *fmt,
 539                               va_list args)
 540 {
 541    size_t new_length;
 542    char *ptr;
 543
 544    assert(str != NULL);
 545
 546    if (unlikely(*str == NULL)) {
 547       // Assuming a NULL context is probably bad, but it's expected behavior.
 548       *str = ralloc_vasprintf(NULL, fmt, args);
 549       *start = strlen(*str);
 550       return true;
 551    }
 552
 553    new_length = printf_length(fmt, args);
 554
 555    ptr = resize(*str, *start + new_length + 1);
 556    if (unlikely(ptr == NULL))
 557       return false;
 558
 559    vsnprintf(ptr + *start, new_length + 1, fmt, args);
 560    *str = ptr;
 561    *start += new_length;
 562    return true;
 563 }
 564
 565 /***************************************************************************
 566  * Linear allocator for short-lived allocations.
 567  ***************************************************************************
 568  *
 569  * The allocator consists of a parent node (2K buffer), which requires
 570  * a ralloc parent, and child nodes (allocations). Child nodes can't be freed
 571  * directly, because the parent doesn't track them. You have to release
 572  * the parent node in order to release all its children.
 573  *
 574  * The allocator uses a fixed-sized buffer with a monotonically increasing
 575  * offset after each allocation. If the buffer is all used, another buffer
 576  * is allocated, sharing the same ralloc parent, so all buffers are at
 577  * the same level in the ralloc hierarchy.
 578  *
 579  * The linear parent node is always the first buffer and keeps track of all
 580  * other buffers.
 581  */
 582
 583 #define MIN_LINEAR_BUFSIZE 2048
 584 #define SUBALLOC_ALIGNMENT 8
 585 #define LMAGIC 0x87b9c7d3
 586
 587 struct
 588 #ifdef _MSC_VER
 589  __declspec(align(8))
 590 #elif defined(__LP64__)
 591  __attribute__((aligned(16)))
 592 #else
 593  __attribute__((aligned(8)))
 594 #endif
 595    linear_header {
 596 #ifndef NDEBUG
 597    unsigned magic;   /* for debugging */
 598 #endif
 599    unsigned offset;  /* points to the first unused byte in the buffer */
 600    unsigned size;    /* size of the buffer */
 601    void *ralloc_parent;          /* new buffers will use this */
 602    struct linear_header *next;   /* next buffer if we have more */
 603    struct linear_header *latest; /* the only buffer that has free space */
 604
 605    /* After this structure, the buffer begins.
 606     * Each suballocation consists of linear_size_chunk as its header followed
 607     * by the suballocation, so it goes:
 608     *
 609     * - linear_size_chunk
 610     * - allocated space
 611     * - linear_size_chunk
 612     * - allocated space
 613     * etc.
 614     *
 615     * linear_size_chunk is only needed by linear_realloc.
 616     */
 617 };
 618
 619 struct linear_size_chunk {
 620    unsigned size; /* for realloc */
 621    unsigned _padding;
 622 };
 623
 624 typedef struct linear_header linear_header;
 625 typedef struct linear_size_chunk linear_size_chunk;
 626
 627 #define LINEAR_PARENT_TO_HEADER(parent) \
 628    (linear_header*) \
 629    ((char*)(parent) - sizeof(linear_size_chunk) - sizeof(linear_header))
 630
 631 /* Allocate the linear buffer with its header. */
 632 static linear_header *
 633 create_linear_node(void *ralloc_ctx, unsigned min_size)
 634 {
 635    linear_header *node;
 636
 637    min_size += sizeof(linear_size_chunk);
 638
 639    if (likely(min_size < MIN_LINEAR_BUFSIZE))
 640       min_size = MIN_LINEAR_BUFSIZE;
 641
 642    node = ralloc_size(ralloc_ctx, sizeof(linear_header) + min_size);
 643    if (unlikely(!node))
 644       return NULL;
 645
 646 #ifndef NDEBUG
 647    node->magic = LMAGIC;
 648 #endif
 649    node->offset = 0;
 650    node->size = min_size;
 651    node->ralloc_parent = ralloc_ctx;
 652    node->next = NULL;
 653    node->latest = node;
 654    return node;
 655 }
 656
 657 void *
 658 linear_alloc_child(void *parent, unsigned size)
 659 {
 660    linear_header *first = LINEAR_PARENT_TO_HEADER(parent);
 661    linear_header *latest = first->latest;
 662    linear_header *new_node;
 663    linear_size_chunk *ptr;
 664    unsigned full_size;
 665
 666    assert(first->magic == LMAGIC);
 667    assert(!latest->next);
 668
 669    size = ALIGN_POT(size, SUBALLOC_ALIGNMENT);
 670    full_size = sizeof(linear_size_chunk) + size;
 671
 672    if (unlikely(latest->offset + full_size > latest->size)) {
 673       /* allocate a new node */
 674       new_node = create_linear_node(latest->ralloc_parent, size);
 675       if (unlikely(!new_node))
 676          return NULL;
 677
 678       first->latest = new_node;
 679       latest->latest = new_node;
 680       latest->next = new_node;
 681       latest = new_node;
 682    }
 683
 684    ptr = (linear_size_chunk *)((char*)&latest[1] + latest->offset);
 685    ptr->size = size;
 686    latest->offset += full_size;
 687
 688    assert((uintptr_t)&ptr[1] % SUBALLOC_ALIGNMENT == 0);
 689    return &ptr[1];
 690 }
 691
 692 void *
 693 linear_alloc_parent(void *ralloc_ctx, unsigned size)
 694 {
 695    linear_header *node;
 696
 697    if (unlikely(!ralloc_ctx))
 698       return NULL;
 699
 700    size = ALIGN_POT(size, SUBALLOC_ALIGNMENT);
 701
 702    node = create_linear_node(ralloc_ctx, size);
 703    if (unlikely(!node))
 704       return NULL;
 705
 706    return linear_alloc_child((char*)node +
 707                              sizeof(linear_header) +
 708                              sizeof(linear_size_chunk), size);
 709 }
 710
 711 void *
 712 linear_zalloc_child(void *parent, unsigned size)
 713 {
 714    void *ptr = linear_alloc_child(parent, size);
 715
 716    if (likely(ptr))
 717       memset(ptr, 0, size);
 718    return ptr;
 719 }
 720
 721 void *
 722 linear_zalloc_parent(void *parent, unsigned size)
 723 {
 724    void *ptr = linear_alloc_parent(parent, size);
 725
 726    if (likely(ptr))
 727       memset(ptr, 0, size);
 728    return ptr;
 729 }
 730
 731 void
 732 linear_free_parent(void *ptr)
 733 {
 734    linear_header *node;
 735
 736    if (unlikely(!ptr))
 737       return;
 738
 739    node = LINEAR_PARENT_TO_HEADER(ptr);
 740    assert(node->magic == LMAGIC);
 741
 742    while (node) {
 743       void *ptr = node;
 744
 745       node = node->next;
 746       ralloc_free(ptr);
 747    }
 748 }
 749
 750 void
 751 ralloc_steal_linear_parent(void *new_ralloc_ctx, void *ptr)
 752 {
 753    linear_header *node;
 754
 755    if (unlikely(!ptr))
 756       return;
 757
 758    node = LINEAR_PARENT_TO_HEADER(ptr);
 759    assert(node->magic == LMAGIC);
 760
 761    while (node) {
 762       ralloc_steal(new_ralloc_ctx, node);
 763       node->ralloc_parent = new_ralloc_ctx;
 764       node = node->next;
 765    }
 766 }
 767
 768 void *
 769 ralloc_parent_of_linear_parent(void *ptr)
 770 {
 771    linear_header *node = LINEAR_PARENT_TO_HEADER(ptr);
 772    assert(node->magic == LMAGIC);
 773    return node->ralloc_parent;
 774 }
 775
 776 void *
 777 linear_realloc(void *parent, void *old, unsigned new_size)
 778 {
 779    unsigned old_size = 0;
 780    ralloc_header *new_ptr;
 781
 782    new_ptr = linear_alloc_child(parent, new_size);
 783
 784    if (unlikely(!old))
 785       return new_ptr;
 786
 787    old_size = ((linear_size_chunk*)old)[-1].size;
 788
 789    if (likely(new_ptr && old_size))
 790       memcpy(new_ptr, old, MIN2(old_size, new_size));
 791
 792    return new_ptr;
 793 }
 794
 795 /* All code below is pretty much copied from ralloc and only the alloc
 796  * calls are different.
 797  */
 798
 799 char *
 800 linear_strdup(void *parent, const char *str)
 801 {
 802    unsigned n;
 803    char *ptr;
 804
 805    if (unlikely(!str))
 806       return NULL;
 807
 808    n = strlen(str);
 809    ptr = linear_alloc_child(parent, n + 1);
 810    if (unlikely(!ptr))
 811       return NULL;
 812
 813    memcpy(ptr, str, n);
 814    ptr[n] = '\0';
 815    return ptr;
 816 }
 817
 818 char *
 819 linear_asprintf(void *parent, const char *fmt, ...)
 820 {
 821    char *ptr;
 822    va_list args;
 823    va_start(args, fmt);
 824    ptr = linear_vasprintf(parent, fmt, args);
 825    va_end(args);
 826    return ptr;
 827 }
 828
 829 char *
 830 linear_vasprintf(void *parent, const char *fmt, va_list args)
 831 {
 832    unsigned size = printf_length(fmt, args) + 1;
 833
 834    char *ptr = linear_alloc_child(parent, size);
 835    if (ptr != NULL)
 836       vsnprintf(ptr, size, fmt, args);
 837
 838    return ptr;
 839 }
 840
 841 bool
 842 linear_asprintf_append(void *parent, char **str, const char *fmt, ...)
 843 {
 844    bool success;
 845    va_list args;
 846    va_start(args, fmt);
 847    success = linear_vasprintf_append(parent, str, fmt, args);
 848    va_end(args);
 849    return success;
 850 }
 851
 852 bool
 853 linear_vasprintf_append(void *parent, char **str, const char *fmt, va_list args)
 854 {
 855    size_t existing_length;
 856    assert(str != NULL);
 857    existing_length = *str ? strlen(*str) : 0;
 858    return linear_vasprintf_rewrite_tail(parent, str, &existing_length, fmt, args);
 859 }
 860
 861 bool
 862 linear_asprintf_rewrite_tail(void *parent, char **str, size_t *start,
 863                              const char *fmt, ...)
 864 {
 865    bool success;
 866    va_list args;
 867    va_start(args, fmt);
 868    success = linear_vasprintf_rewrite_tail(parent, str, start, fmt, args);
 869    va_end(args);
 870    return success;
 871 }
 872
 873 bool
 874 linear_vasprintf_rewrite_tail(void *parent, char **str, size_t *start,
 875                               const char *fmt, va_list args)
 876 {
 877    size_t new_length;
 878    char *ptr;
 879
 880    assert(str != NULL);
 881
 882    if (unlikely(*str == NULL)) {
 883       *str = linear_vasprintf(parent, fmt, args);
 884       *start = strlen(*str);
 885       return true;
 886    }
 887
 888    new_length = printf_length(fmt, args);
 889
 890    ptr = linear_realloc(parent, *str, *start + new_length + 1);
 891    if (unlikely(ptr == NULL))
 892       return false;
 893
 894    vsnprintf(ptr + *start, new_length + 1, fmt, args);
 895    *str = ptr;
 896    *start += new_length;
 897    return true;
 898 }
 899
 900 /* helper routine for strcat/strncat - n is the exact amount to copy */
 901 static bool
 902 linear_cat(void *parent, char **dest, const char *str, unsigned n)
 903 {
 904    char *both;
 905    unsigned existing_length;
 906    assert(dest != NULL && *dest != NULL);
 907
 908    existing_length = strlen(*dest);
 909    both = linear_realloc(parent, *dest, existing_length + n + 1);
 910    if (unlikely(both == NULL))
 911       return false;
 912
 913    memcpy(both + existing_length, str, n);
 914    both[existing_length + n] = '\0';
 915
 916    *dest = both;
 917    return true;
 918 }
 919
 920 bool
 921 linear_strcat(void *parent, char **dest, const char *str)
 922 {
 923    return linear_cat(parent, dest, str, strlen(str));
 924 }