ralloc.c 10.3 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
 * Copyright © 2010 Intel Corporation
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice (including the next
 * paragraph) shall be included in all copies or substantial portions of the
 * Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 */

#include <assert.h>
#include <stdlib.h>
#include <stdarg.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>

31
32
33
34
35
/* Android defines SIZE_MAX in limits.h, instead of the standard stdint.h */
#ifdef ANDROID
#include <limits.h>
#endif

36
37
38
39
40
41
/* Some versions of MinGW are missing _vscprintf's declaration, although they
 * still provide the symbol in the import library. */
#ifdef __MINGW32__
_CRTIMP int _vscprintf(const char *format, va_list argptr);
#endif

42
43
#include "ralloc.h"

Jose Fonseca's avatar
Jose Fonseca committed
44
45
46
47
48
49
50
51
#ifndef va_copy
#ifdef __va_copy
#define va_copy(dest, src) __va_copy((dest), (src))
#else
#define va_copy(dest, src) (dest) = (src)
#endif
#endif

52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#define CANARY 0x5A1106

struct ralloc_header
{
   /* A canary value used to determine whether a pointer is ralloc'd. */
   unsigned canary;

   struct ralloc_header *parent;

   /* The first child (head of a linked list) */
   struct ralloc_header *child;

   /* Linked list of siblings */
   struct ralloc_header *prev;
   struct ralloc_header *next;

   void (*destructor)(void *);
};

typedef struct ralloc_header ralloc_header;

static void unlink_block(ralloc_header *info);
static void unsafe_free(ralloc_header *info);

static ralloc_header *
get_header(const void *ptr)
{
   ralloc_header *info = (ralloc_header *) (((char *) ptr) -
					    sizeof(ralloc_header));
   assert(info->canary == CANARY);
   return info;
}

#define PTR_FROM_HEADER(info) (((char *) info) + sizeof(ralloc_header))

static void
add_child(ralloc_header *parent, ralloc_header *info)
{
   if (parent != NULL) {
      info->parent = parent;
      info->next = parent->child;
      parent->child = info;

      if (info->next != NULL)
	 info->next->prev = info;
   }
}

100
101
102
void *
ralloc_context(const void *ctx)
{
103
   return ralloc_size(ctx, 0);
104
105
106
107
108
}

void *
ralloc_size(const void *ctx, size_t size)
{
109
110
111
112
113
114
115
116
117
118
   void *block = calloc(1, size + sizeof(ralloc_header));

   ralloc_header *info = (ralloc_header *) block;
   ralloc_header *parent = ctx != NULL ? get_header(ctx) : NULL;

   add_child(parent, info);

   info->canary = CANARY;

   return PTR_FROM_HEADER(info);
119
120
121
122
123
}

void *
rzalloc_size(const void *ctx, size_t size)
{
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
   void *ptr = ralloc_size(ctx, size);
   if (likely(ptr != NULL))
      memset(ptr, 0, size);
   return ptr;
}

/* helper function - assumes ptr != NULL */
static void *
resize(void *ptr, size_t size)
{
   ralloc_header *child, *old, *info;

   old = get_header(ptr);
   info = realloc(old, size + sizeof(ralloc_header));

   if (info == NULL)
      return NULL;

   /* Update parent and sibling's links to the reallocated node. */
   if (info != old && info->parent != NULL) {
      if (info->parent->child == old)
	 info->parent->child = info;

      if (info->prev != NULL)
	 info->prev->next = info;

      if (info->next != NULL)
	 info->next->prev = info;
   }

   /* Update child->parent links for all children */
   for (child = info->child; child != NULL; child = child->next)
      child->parent = info;

   return PTR_FROM_HEADER(info);
159
160
161
162
163
}

void *
reralloc_size(const void *ctx, void *ptr, size_t size)
{
164
165
166
167
168
   if (unlikely(ptr == NULL))
      return ralloc_size(ctx, size);

   assert(ralloc_parent(ptr) == ctx);
   return resize(ptr, size);
169
170
171
172
173
174
175
176
}

void *
ralloc_array_size(const void *ctx, size_t size, unsigned count)
{
   if (count > SIZE_MAX/size)
      return NULL;

177
   return ralloc_size(ctx, size * count);
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
}

void *
rzalloc_array_size(const void *ctx, size_t size, unsigned count)
{
   if (count > SIZE_MAX/size)
      return NULL;

   return rzalloc_size(ctx, size * count);
}

void *
reralloc_array_size(const void *ctx, void *ptr, size_t size, unsigned count)
{
   if (count > SIZE_MAX/size)
193
      return NULL;
194
195
196
197
198
199
200

   return reralloc_size(ctx, ptr, size * count);
}

void
ralloc_free(void *ptr)
{
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
   ralloc_header *info;

   if (ptr == NULL)
      return;

   info = get_header(ptr);
   unlink_block(info);
   unsafe_free(info);
}

static void
unlink_block(ralloc_header *info)
{
   /* Unlink from parent & siblings */
   if (info->parent != NULL) {
      if (info->parent->child == info)
	 info->parent->child = info->next;

      if (info->prev != NULL)
	 info->prev->next = info->next;

      if (info->next != NULL)
	 info->next->prev = info->prev;
   }
   info->parent = NULL;
   info->prev = NULL;
   info->next = NULL;
}

static void
unsafe_free(ralloc_header *info)
{
   /* Recursively free any children...don't waste time unlinking them. */
   ralloc_header *temp;
   while (info->child != NULL) {
      temp = info->child;
      info->child = temp->next;
      unsafe_free(temp);
   }

   /* Free the block itself.  Call the destructor first, if any. */
   if (info->destructor != NULL)
      info->destructor(PTR_FROM_HEADER(info));

   free(info);
246
247
248
249
250
}

void
ralloc_steal(const void *new_ctx, void *ptr)
{
251
252
253
254
255
256
257
258
259
260
261
   ralloc_header *info, *parent;

   if (unlikely(ptr == NULL))
      return;

   info = get_header(ptr);
   parent = get_header(new_ctx);

   unlink_block(info);

   add_child(parent, info);
262
263
264
265
266
}

void *
ralloc_parent(const void *ptr)
{
267
268
269
270
271
272
   ralloc_header *info;

   if (unlikely(ptr == NULL))
      return NULL;

   info = get_header(ptr);
273
   return info->parent ? PTR_FROM_HEADER(info->parent) : NULL;
274
275
276
277
278
279
280
281
}

static void *autofree_context = NULL;

static void
autofree(void)
{
   ralloc_free(autofree_context);
282
283
284
285
286
}

void *
ralloc_autofree_context(void)
{
287
288
289
290
291
   if (unlikely(autofree_context == NULL)) {
      autofree_context = ralloc_context(NULL);
      atexit(autofree);
   }
   return autofree_context;
292
293
294
295
296
}

void
ralloc_set_destructor(const void *ptr, void(*destructor)(void *))
{
297
298
   ralloc_header *info = get_header(ptr);
   info->destructor = destructor;
299
300
301
302
303
}

char *
ralloc_strdup(const void *ctx, const char *str)
{
304
305
306
307
308
309
310
311
312
313
314
   size_t n;
   char *ptr;

   if (unlikely(str == NULL))
      return NULL;

   n = strlen(str);
   ptr = ralloc_array(ctx, char, n + 1);
   memcpy(ptr, str, n);
   ptr[n] = '\0';
   return ptr;
315
316
317
318
319
}

char *
ralloc_strndup(const void *ctx, const char *str, size_t max)
{
320
321
322
323
324
325
326
327
328
329
330
331
332
333
   size_t n;
   char *ptr;

   if (unlikely(str == NULL))
      return NULL;

   n = strlen(str);
   if (n > max)
      n = max;

   ptr = ralloc_array(ctx, char, n + 1);
   memcpy(ptr, str, n);
   ptr[n] = '\0';
   return ptr;
334
335
}

336
337
338
/* helper routine for strcat/strncat - n is the exact amount to copy */
static bool
cat(char **dest, const char *str, size_t n)
339
{
340
341
342
   char *both;
   size_t existing_length;
   assert(dest != NULL && *dest != NULL);
343

344
345
346
   existing_length = strlen(*dest);
   both = resize(*dest, existing_length + n + 1);
   if (unlikely(both == NULL))
347
348
      return false;

349
350
351
352
   memcpy(both + existing_length, str, n);
   both[existing_length + n] = '\0';

   *dest = both;
353
354
355
   return true;
}

356

357
bool
358
ralloc_strcat(char **dest, const char *str)
359
{
360
361
   return cat(dest, str, strlen(str));
}
362

363
364
365
366
367
368
369
bool
ralloc_strncat(char **dest, const char *str, size_t n)
{
   /* Clamp n to the string length */
   size_t str_length = strlen(str);
   if (str_length < n)
      n = str_length;
370

371
   return cat(dest, str, n);
372
373
374
375
376
377
378
379
380
381
382
383
384
}

char *
ralloc_asprintf(const void *ctx, const char *fmt, ...)
{
   char *ptr;
   va_list args;
   va_start(args, fmt);
   ptr = ralloc_vasprintf(ctx, fmt, args);
   va_end(args);
   return ptr;
}

385
386
387
388
389
390
391
392
393
394
395
396
397
/* Return the length of the string that would be generated by a printf-style
 * format and argument list, not including the \0 byte.
 */
static size_t
printf_length(const char *fmt, va_list untouched_args)
{
   int size;
   char junk;

   /* Make a copy of the va_list so the original caller can still use it */
   va_list args;
   va_copy(args, untouched_args);

398
#ifdef _WIN32
399
400
401
402
403
404
   /* We need to use _vcsprintf to calculate the size as vsnprintf returns -1
    * if the number of characters to write is greater than count.
    */
   size = _vscprintf(fmt, args);
   (void)junk;
#else
405
   size = vsnprintf(&junk, 1, fmt, args);
406
#endif
407
408
   assert(size >= 0);

409
410
   va_end(args);

411
412
413
   return size;
}

414
415
416
char *
ralloc_vasprintf(const void *ctx, const char *fmt, va_list args)
{
417
418
419
420
421
422
423
   size_t size = printf_length(fmt, args) + 1;

   char *ptr = ralloc_size(ctx, size);
   if (ptr != NULL)
      vsnprintf(ptr, size, fmt, args);

   return ptr;
424
425
426
427
428
}

bool
ralloc_asprintf_append(char **str, const char *fmt, ...)
{
429
   bool success;
430
431
   va_list args;
   va_start(args, fmt);
432
   success = ralloc_vasprintf_append(str, fmt, args);
433
   va_end(args);
434
   return success;
435
436
437
438
439
}

bool
ralloc_vasprintf_append(char **str, const char *fmt, va_list args)
{
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
450
451
452
453
454
455
456
457
{
   bool success;
   va_list args;
   va_start(args, fmt);
   success = ralloc_vasprintf_rewrite_tail(str, start, fmt, args);
   va_end(args);
   return success;
}

bool
458
ralloc_vasprintf_rewrite_tail(char **str, size_t *start, const char *fmt,
459
460
461
			      va_list args)
{
   size_t new_length;
462
463
   char *ptr;

464
465
   assert(str != NULL);

466
467
468
469
470
471
472
473
   if (unlikely(*str == NULL)) {
      // Assuming a NULL context is probably bad, but it's expected behavior.
      *str = ralloc_vasprintf(NULL, fmt, args);
      return true;
   }

   new_length = printf_length(fmt, args);

474
   ptr = resize(*str, *start + new_length + 1);
475
476
477
   if (unlikely(ptr == NULL))
      return false;

478
   vsnprintf(ptr + *start, new_length + 1, fmt, args);
479
   *str = ptr;
480
   *start += new_length;
481
482
   return true;
}