Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

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