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