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