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