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