src/glsl/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 /* Android defines SIZE_MAX in limits.h, instead of the standard stdint.h */
  32 #ifdef ANDROID
  33 #include <limits.h>
  34 #endif
  35
  36 /* Some versions of MinGW are missing _vscprintf's declaration, although they
  37  * still provide the symbol in the import library. */
  38 #ifdef __MINGW32__
  39 _CRTIMP int _vscprintf(const char *format, va_list argptr);
  40 #endif
  41
  42 #include "ralloc.h"
  43
  44 #ifdef __GNUC__
  45 #define likely(x)       __builtin_expect(!!(x),1)
  46 #define unlikely(x)     __builtin_expect(!!(x),0)
  47 #else
  48 #define likely(x)       !!(x)
  49 #define unlikely(x)     !!(x)
  50 #endif
  51
  52 #ifndef va_copy
  53 #ifdef __va_copy
  54 #define va_copy(dest, src) __va_copy((dest), (src))
  55 #else
  56 #define va_copy(dest, src) (dest) = (src)
  57 #endif
  58 #endif
  59
  60 #define CANARY 0x5A1106
  61
  62 struct ralloc_header
  63 {
  64    /* A canary value used to determine whether a pointer is ralloc'd. */
  65    unsigned canary;
  66
  67    struct ralloc_header *parent;
  68
  69    /* The first child (head of a linked list) */
  70    struct ralloc_header *child;
  71
  72    /* Linked list of siblings */
  73    struct ralloc_header *prev;
  74    struct ralloc_header *next;
  75
  76    void (*destructor)(void *);
  77 };
  78
  79 typedef struct ralloc_header ralloc_header;
  80
  81 static void unlink_block(ralloc_header *info);
  82 static void unsafe_free(ralloc_header *info);
  83
  84 static ralloc_header *
  85 get_header(const void *ptr)
  86 {
  87    ralloc_header *info = (ralloc_header *) (((char *) ptr) -
  88                                             sizeof(ralloc_header));
  89    assert(info->canary == CANARY);
  90    return info;
  91 }
  92
  93 #define PTR_FROM_HEADER(info) (((char *) info) + sizeof(ralloc_header))
  94
  95 static void
  96 add_child(ralloc_header *parent, ralloc_header *info)
  97 {
  98    if (parent != NULL) {
  99       info->parent = parent;
 100       info->next = parent->child;
 101       parent->child = info;
 102
 103       if (info->next != NULL)
 104          info->next->prev = info;
 105    }
 106 }
 107
 108 void *
 109 ralloc_context(const void *ctx)
 110 {
 111    return ralloc_size(ctx, 0);
 112 }
 113
 114 void *
 115 ralloc_size(const void *ctx, size_t size)
 116 {
 117    void *block = calloc(1, size + sizeof(ralloc_header));
 118
 119    ralloc_header *info = (ralloc_header *) block;
 120    ralloc_header *parent = ctx != NULL ? get_header(ctx) : NULL;
 121
 122    add_child(parent, info);
 123
 124    info->canary = CANARY;
 125
 126    return PTR_FROM_HEADER(info);
 127 }
 128
 129 void *
 130 rzalloc_size(const void *ctx, size_t size)
 131 {
 132    void *ptr = ralloc_size(ctx, size);
 133    if (likely(ptr != NULL))
 134       memset(ptr, 0, size);
 135    return ptr;
 136 }
 137
 138 /* helper function - assumes ptr != NULL */
 139 static void *
 140 resize(void *ptr, size_t size)
 141 {
 142    ralloc_header *child, *old, *info;
 143
 144    old = get_header(ptr);
 145    info = realloc(old, size + sizeof(ralloc_header));
 146
 147    if (info == NULL)
 148       return NULL;
 149
 150    /* Update parent and sibling's links to the reallocated node. */
 151    if (info != old && info->parent != NULL) {
 152       if (info->parent->child == old)
 153          info->parent->child = info;
 154
 155       if (info->prev != NULL)
 156          info->prev->next = info;
 157
 158       if (info->next != NULL)
 159          info->next->prev = info;
 160    }
 161
 162    /* Update child->parent links for all children */
 163    for (child = info->child; child != NULL; child = child->next)
 164       child->parent = info;
 165
 166    return PTR_FROM_HEADER(info);
 167 }
 168
 169 void *
 170 reralloc_size(const void *ctx, void *ptr, size_t size)
 171 {
 172    if (unlikely(ptr == NULL))
 173       return ralloc_size(ctx, size);
 174
 175    assert(ralloc_parent(ptr) == ctx);
 176    return resize(ptr, size);
 177 }
 178
 179 void *
 180 ralloc_array_size(const void *ctx, size_t size, unsigned count)
 181 {
 182    if (count > SIZE_MAX/size)
 183       return NULL;
 184
 185    return ralloc_size(ctx, size * count);
 186 }
 187
 188 void *
 189 rzalloc_array_size(const void *ctx, size_t size, unsigned count)
 190 {
 191    if (count > SIZE_MAX/size)
 192       return NULL;
 193
 194    return rzalloc_size(ctx, size * count);
 195 }
 196
 197 void *
 198 reralloc_array_size(const void *ctx, void *ptr, size_t size, unsigned count)
 199 {
 200    if (count > SIZE_MAX/size)
 201       return NULL;
 202
 203    return reralloc_size(ctx, ptr, size * count);
 204 }
 205
 206 void
 207 ralloc_free(void *ptr)
 208 {
 209    ralloc_header *info;
 210
 211    if (ptr == NULL)
 212       return;
 213
 214    info = get_header(ptr);
 215    unlink_block(info);
 216    unsafe_free(info);
 217 }
 218
 219 static void
 220 unlink_block(ralloc_header *info)
 221 {
 222    /* Unlink from parent & siblings */
 223    if (info->parent != NULL) {
 224       if (info->parent->child == info)
 225          info->parent->child = info->next;
 226
 227       if (info->prev != NULL)
 228          info->prev->next = info->next;
 229
 230       if (info->next != NULL)
 231          info->next->prev = info->prev;
 232    }
 233    info->parent = NULL;
 234    info->prev = NULL;
 235    info->next = NULL;
 236 }
 237
 238 static void
 239 unsafe_free(ralloc_header *info)
 240 {
 241    /* Recursively free any children...don't waste time unlinking them. */
 242    ralloc_header *temp;
 243    while (info->child != NULL) {
 244       temp = info->child;
 245       info->child = temp->next;
 246       unsafe_free(temp);
 247    }
 248
 249    /* Free the block itself.  Call the destructor first, if any. */
 250    if (info->destructor != NULL)
 251       info->destructor(PTR_FROM_HEADER(info));
 252
 253    free(info);
 254 }
 255
 256 void
 257 ralloc_steal(const void *new_ctx, void *ptr)
 258 {
 259    ralloc_header *info, *parent;
 260
 261    if (unlikely(ptr == NULL))
 262       return;
 263
 264    info = get_header(ptr);
 265    parent = get_header(new_ctx);
 266
 267    unlink_block(info);
 268
 269    add_child(parent, info);
 270 }
 271
 272 void *
 273 ralloc_parent(const void *ptr)
 274 {
 275    ralloc_header *info;
 276
 277    if (unlikely(ptr == NULL))
 278       return NULL;
 279
 280    info = get_header(ptr);
 281    return info->parent ? PTR_FROM_HEADER(info->parent) : NULL;
 282 }
 283
 284 static void *autofree_context = NULL;
 285
 286 static void
 287 autofree(void)
 288 {
 289    ralloc_free(autofree_context);
 290 }
 291
 292 void *
 293 ralloc_autofree_context(void)
 294 {
 295    if (unlikely(autofree_context == NULL)) {
 296       autofree_context = ralloc_context(NULL);
 297       atexit(autofree);
 298    }
 299    return autofree_context;
 300 }
 301
 302 void
 303 ralloc_set_destructor(const void *ptr, void(*destructor)(void *))
 304 {
 305    ralloc_header *info = get_header(ptr);
 306    info->destructor = destructor;
 307 }
 308
 309 char *
 310 ralloc_strdup(const void *ctx, const char *str)
 311 {
 312    size_t n;
 313    char *ptr;
 314
 315    if (unlikely(str == NULL))
 316       return NULL;
 317
 318    n = strlen(str);
 319    ptr = ralloc_array(ctx, char, n + 1);
 320    memcpy(ptr, str, n);
 321    ptr[n] = '\0';
 322    return ptr;
 323 }
 324
 325 char *
 326 ralloc_strndup(const void *ctx, const char *str, size_t max)
 327 {
 328    size_t n;
 329    char *ptr;
 330
 331    if (unlikely(str == NULL))
 332       return NULL;
 333
 334    n = strlen(str);
 335    if (n > max)
 336       n = max;
 337
 338    ptr = ralloc_array(ctx, char, n + 1);
 339    memcpy(ptr, str, n);
 340    ptr[n] = '\0';
 341    return ptr;
 342 }
 343
 344 /* helper routine for strcat/strncat - n is the exact amount to copy */
 345 static bool
 346 cat(char **dest, const char *str, size_t n)
 347 {
 348    char *both;
 349    size_t existing_length;
 350    assert(dest != NULL && *dest != NULL);
 351
 352    existing_length = strlen(*dest);
 353    both = resize(*dest, existing_length + n + 1);
 354    if (unlikely(both == NULL))
 355       return false;
 356
 357    memcpy(both + existing_length, str, n);
 358    both[existing_length + n] = '\0';
 359
 360    *dest = both;
 361    return true;
 362 }
 363
 364
 365 bool
 366 ralloc_strcat(char **dest, const char *str)
 367 {
 368    return cat(dest, str, strlen(str));
 369 }
 370
 371 bool
 372 ralloc_strncat(char **dest, const char *str, size_t n)
 373 {
 374    /* Clamp n to the string length */
 375    size_t str_length = strlen(str);
 376    if (str_length < n)
 377       n = str_length;
 378
 379    return cat(dest, str, n);
 380 }
 381
 382 char *
 383 ralloc_asprintf(const void *ctx, const char *fmt, ...)
 384 {
 385    char *ptr;
 386    va_list args;
 387    va_start(args, fmt);
 388    ptr = ralloc_vasprintf(ctx, fmt, args);
 389    va_end(args);
 390    return ptr;
 391 }
 392
 393 /* Return the length of the string that would be generated by a printf-style
 394  * format and argument list, not including the \0 byte.
 395  */
 396 static size_t
 397 printf_length(const char *fmt, va_list untouched_args)
 398 {
 399    int size;
 400    char junk;
 401
 402    /* Make a copy of the va_list so the original caller can still use it */
 403    va_list args;
 404    va_copy(args, untouched_args);
 405
 406 #ifdef _WIN32
 407    /* We need to use _vcsprintf to calculate the size as vsnprintf returns -1
 408     * if the number of characters to write is greater than count.
 409     */
 410    size = _vscprintf(fmt, args);
 411    (void)junk;
 412 #else
 413    size = vsnprintf(&junk, 1, fmt, args);
 414 #endif
 415    assert(size >= 0);
 416
 417    va_end(args);
 418
 419    return size;
 420 }
 421
 422 char *
 423 ralloc_vasprintf(const void *ctx, const char *fmt, va_list args)
 424 {
 425    size_t size = printf_length(fmt, args) + 1;
 426
 427    char *ptr = ralloc_size(ctx, size);
 428    if (ptr != NULL)
 429       vsnprintf(ptr, size, fmt, args);
 430
 431    return ptr;
 432 }
 433
 434 bool
 435 ralloc_asprintf_append(char **str, const char *fmt, ...)
 436 {
 437    bool success;
 438    va_list args;
 439    va_start(args, fmt);
 440    success = ralloc_vasprintf_append(str, fmt, args);
 441    va_end(args);
 442    return success;
 443 }
 444
 445 bool
 446 ralloc_vasprintf_append(char **str, const char *fmt, va_list args)
 447 {
 448    size_t existing_length;
 449    assert(str != NULL);
 450    existing_length = *str ? strlen(*str) : 0;
 451    return ralloc_vasprintf_rewrite_tail(str, &existing_length, fmt, args);
 452 }
 453
 454 bool
 455 ralloc_asprintf_rewrite_tail(char **str, size_t *start, const char *fmt, ...)
 456 {
 457    bool success;
 458    va_list args;
 459    va_start(args, fmt);
 460    success = ralloc_vasprintf_rewrite_tail(str, start, fmt, args);
 461    va_end(args);
 462    return success;
 463 }
 464
 465 bool
 466 ralloc_vasprintf_rewrite_tail(char **str, size_t *start, const char *fmt,
 467                               va_list args)
 468 {
 469    size_t new_length;
 470    char *ptr;
 471
 472    assert(str != NULL);
 473
 474    if (unlikely(*str == NULL)) {
 475       // Assuming a NULL context is probably bad, but it's expected behavior.
 476       *str = ralloc_vasprintf(NULL, fmt, args);
 477       return true;
 478    }
 479
 480    new_length = printf_length(fmt, args);
 481
 482    ptr = resize(*str, *start + new_length + 1);
 483    if (unlikely(ptr == NULL))
 484       return false;
 485
 486    vsnprintf(ptr + *start, new_length + 1, fmt, args);
 487    *str = ptr;
 488    *start += new_length;
 489    return true;
 490 }