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 54 struct 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 71 typedef struct ralloc_header ralloc_header; 72 73 static void unlink_block(ralloc_header *info); 74 static void unsafe_free(ralloc_header *info); 75 76 static ralloc_header * 77 get_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 87 static void 88 add_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 100 void * 101 ralloc_context(const void *ctx) 102 { 103 return ralloc_size(ctx, 0); 104 } 105 106 void * 107 ralloc_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 121 void * 122 rzalloc_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 */ 131 static void * 132 resize(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 161 void * 162 reralloc_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 171 void * 172 ralloc_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 180 void * 181 rzalloc_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 189 void * 190 reralloc_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 198 void 199 ralloc_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 211 static void 212 unlink_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 230 static void 231 unsafe_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 248 void 249 ralloc_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 264 void * 265 ralloc_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 276 static void *autofree_context = NULL; 277 278 static void 279 autofree(void) 280 { 281 ralloc_free(autofree_context); 282 } 283 284 void * 285 ralloc_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 294 void 295 ralloc_set_destructor(const void *ptr, void(*destructor)(void *)) 296 { 297 ralloc_header *info = get_header(ptr); 298 info->destructor = destructor; 299 } 300 301 char * 302 ralloc_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 317 char * 318 ralloc_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 */ 337 static bool 338 cat(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 357 bool 358 ralloc_strcat(char **dest, const char *str) 359 { 360 return cat(dest, str, strlen(str)); 361 } 362 363 bool 364 ralloc_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 374 char * 375 ralloc_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 */ 388 static size_t 389 printf_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 414 char * 415 ralloc_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 426 bool 427 ralloc_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 437 bool 438 ralloc_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 446 bool 447 ralloc_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 457 bool 458 ralloc_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
