• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 /**
25  * \file ralloc.h
26  *
27  * ralloc: a recursive memory allocator
28  *
29  * The ralloc memory allocator creates a hierarchy of allocated
30  * objects. Every allocation is in reference to some parent, and
31  * every allocated object can in turn be used as the parent of a
32  * subsequent allocation. This allows for extremely convenient
33  * discarding of an entire tree/sub-tree of allocations by calling
34  * ralloc_free on any particular object to free it and all of its
35  * children.
36  *
37  * The conceptual working of ralloc was directly inspired by Andrew
38  * Tridgell's talloc, but ralloc is an independent implementation
39  * released under the MIT license and tuned for Mesa.
40  *
41  * talloc is more sophisticated than ralloc in that it includes reference
42  * counting and useful debugging features.  However, it is released under
43  * a non-permissive open source license.
44  */
45 
46 #ifndef RALLOC_H
47 #define RALLOC_H
48 
49 #include <stddef.h>
50 #include <stdarg.h>
51 #include <stdbool.h>
52 
53 #include "macros.h"
54 
55 #ifdef __cplusplus
56 extern "C" {
57 #endif
58 
59 /**
60  * \def ralloc(ctx, type)
61  * Allocate a new object chained off of the given context.
62  *
63  * This is equivalent to:
64  * \code
65  * ((type *) ralloc_size(ctx, sizeof(type))
66  * \endcode
67  */
68 #define ralloc(ctx, type)  ((type *) ralloc_size(ctx, sizeof(type)))
69 
70 /**
71  * \def rzalloc(ctx, type)
72  * Allocate a new object out of the given context and initialize it to zero.
73  *
74  * This is equivalent to:
75  * \code
76  * ((type *) rzalloc_size(ctx, sizeof(type))
77  * \endcode
78  */
79 #define rzalloc(ctx, type) ((type *) rzalloc_size(ctx, sizeof(type)))
80 
81 /**
82  * Allocate a new ralloc context.
83  *
84  * While any ralloc'd pointer can be used as a context, sometimes it is useful
85  * to simply allocate a context with no associated memory.
86  *
87  * It is equivalent to:
88  * \code
89  * ((type *) ralloc_size(ctx, 0)
90  * \endcode
91  */
92 void *ralloc_context(const void *ctx);
93 
94 /**
95  * Allocate memory chained off of the given context.
96  *
97  * This is the core allocation routine which is used by all others.  It
98  * simply allocates storage for \p size bytes and returns the pointer,
99  * similar to \c malloc.
100  */
101 void *ralloc_size(const void *ctx, size_t size) MALLOCLIKE;
102 
103 /**
104  * Allocate zero-initialized memory chained off of the given context.
105  *
106  * This is similar to \c calloc with a size of 1.
107  */
108 void *rzalloc_size(const void *ctx, size_t size) MALLOCLIKE;
109 
110 /**
111  * Resize a piece of ralloc-managed memory, preserving data.
112  *
113  * Similar to \c realloc.  Unlike C89, passing 0 for \p size does not free the
114  * memory.  Instead, it resizes it to a 0-byte ralloc context, just like
115  * calling ralloc_size(ctx, 0).  This is different from talloc.
116  *
117  * \param ctx  The context to use for new allocation.  If \p ptr != NULL,
118  *             it must be the same as ralloc_parent(\p ptr).
119  * \param ptr  Pointer to the memory to be resized.  May be NULL.
120  * \param size The amount of memory to allocate, in bytes.
121  */
122 void *reralloc_size(const void *ctx, void *ptr, size_t size);
123 
124 /// \defgroup array Array Allocators @{
125 
126 /**
127  * \def ralloc_array(ctx, type, count)
128  * Allocate an array of objects chained off the given context.
129  *
130  * Similar to \c calloc, but does not initialize the memory to zero.
131  *
132  * More than a convenience function, this also checks for integer overflow when
133  * multiplying \c sizeof(type) and \p count.  This is necessary for security.
134  *
135  * This is equivalent to:
136  * \code
137  * ((type *) ralloc_array_size(ctx, sizeof(type), count)
138  * \endcode
139  */
140 #define ralloc_array(ctx, type, count) \
141    ((type *) ralloc_array_size(ctx, sizeof(type), count))
142 
143 /**
144  * \def rzalloc_array(ctx, type, count)
145  * Allocate a zero-initialized array chained off the given context.
146  *
147  * Similar to \c calloc.
148  *
149  * More than a convenience function, this also checks for integer overflow when
150  * multiplying \c sizeof(type) and \p count.  This is necessary for security.
151  *
152  * This is equivalent to:
153  * \code
154  * ((type *) rzalloc_array_size(ctx, sizeof(type), count)
155  * \endcode
156  */
157 #define rzalloc_array(ctx, type, count) \
158    ((type *) rzalloc_array_size(ctx, sizeof(type), count))
159 
160 /**
161  * \def reralloc(ctx, ptr, type, count)
162  * Resize a ralloc-managed array, preserving data.
163  *
164  * Similar to \c realloc.  Unlike C89, passing 0 for \p size does not free the
165  * memory.  Instead, it resizes it to a 0-byte ralloc context, just like
166  * calling ralloc_size(ctx, 0).  This is different from talloc.
167  *
168  * More than a convenience function, this also checks for integer overflow when
169  * multiplying \c sizeof(type) and \p count.  This is necessary for security.
170  *
171  * \param ctx   The context to use for new allocation.  If \p ptr != NULL,
172  *              it must be the same as ralloc_parent(\p ptr).
173  * \param ptr   Pointer to the array to be resized.  May be NULL.
174  * \param type  The element type.
175  * \param count The number of elements to allocate.
176  */
177 #define reralloc(ctx, ptr, type, count) \
178    ((type *) reralloc_array_size(ctx, ptr, sizeof(type), count))
179 
180 /**
181  * Allocate memory for an array chained off the given context.
182  *
183  * Similar to \c calloc, but does not initialize the memory to zero.
184  *
185  * More than a convenience function, this also checks for integer overflow when
186  * multiplying \p size and \p count.  This is necessary for security.
187  */
188 void *ralloc_array_size(const void *ctx, size_t size, unsigned count) MALLOCLIKE;
189 
190 /**
191  * Allocate a zero-initialized array chained off the given context.
192  *
193  * Similar to \c calloc.
194  *
195  * More than a convenience function, this also checks for integer overflow when
196  * multiplying \p size and \p count.  This is necessary for security.
197  */
198 void *rzalloc_array_size(const void *ctx, size_t size, unsigned count) MALLOCLIKE;
199 
200 /**
201  * Resize a ralloc-managed array, preserving data.
202  *
203  * Similar to \c realloc.  Unlike C89, passing 0 for \p size does not free the
204  * memory.  Instead, it resizes it to a 0-byte ralloc context, just like
205  * calling ralloc_size(ctx, 0).  This is different from talloc.
206  *
207  * More than a convenience function, this also checks for integer overflow when
208  * multiplying \c sizeof(type) and \p count.  This is necessary for security.
209  *
210  * \param ctx   The context to use for new allocation.  If \p ptr != NULL,
211  *              it must be the same as ralloc_parent(\p ptr).
212  * \param ptr   Pointer to the array to be resized.  May be NULL.
213  * \param size  The size of an individual element.
214  * \param count The number of elements to allocate.
215  *
216  * \return True unless allocation failed.
217  */
218 void *reralloc_array_size(const void *ctx, void *ptr, size_t size,
219 			  unsigned count);
220 /// @}
221 
222 /**
223  * Free a piece of ralloc-managed memory.
224  *
225  * This will also free the memory of any children allocated this context.
226  */
227 void ralloc_free(void *ptr);
228 
229 /**
230  * "Steal" memory from one context, changing it to another.
231  *
232  * This changes \p ptr's context to \p new_ctx.  This is quite useful if
233  * memory is allocated out of a temporary context.
234  */
235 void ralloc_steal(const void *new_ctx, void *ptr);
236 
237 /**
238  * Reparent all children from one context to another.
239  *
240  * This effectively calls ralloc_steal(new_ctx, child) for all children of \p old_ctx.
241  */
242 void ralloc_adopt(const void *new_ctx, void *old_ctx);
243 
244 /**
245  * Return the given pointer's ralloc context.
246  */
247 void *ralloc_parent(const void *ptr);
248 
249 /**
250  * Set a callback to occur just before an object is freed.
251  */
252 void ralloc_set_destructor(const void *ptr, void(*destructor)(void *));
253 
254 /// \defgroup array String Functions @{
255 /**
256  * Duplicate a string, allocating the memory from the given context.
257  */
258 char *ralloc_strdup(const void *ctx, const char *str) MALLOCLIKE;
259 
260 /**
261  * Duplicate a string, allocating the memory from the given context.
262  *
263  * Like \c strndup, at most \p n characters are copied.  If \p str is longer
264  * than \p n characters, \p n are copied, and a termining \c '\0' byte is added.
265  */
266 char *ralloc_strndup(const void *ctx, const char *str, size_t n) MALLOCLIKE;
267 
268 /**
269  * Concatenate two strings, allocating the necessary space.
270  *
271  * This appends \p str to \p *dest, similar to \c strcat, using ralloc_resize
272  * to expand \p *dest to the appropriate size.  \p dest will be updated to the
273  * new pointer unless allocation fails.
274  *
275  * The result will always be null-terminated.
276  *
277  * \return True unless allocation failed.
278  */
279 bool ralloc_strcat(char **dest, const char *str);
280 
281 /**
282  * Concatenate two strings, allocating the necessary space.
283  *
284  * This appends at most \p n bytes of \p str to \p *dest, using ralloc_resize
285  * to expand \p *dest to the appropriate size.  \p dest will be updated to the
286  * new pointer unless allocation fails.
287  *
288  * The result will always be null-terminated; \p str does not need to be null
289  * terminated if it is longer than \p n.
290  *
291  * \return True unless allocation failed.
292  */
293 bool ralloc_strncat(char **dest, const char *str, size_t n);
294 
295 /**
296  * Concatenate two strings, allocating the necessary space.
297  *
298  * This appends \p n bytes of \p str to \p *dest, using ralloc_resize
299  * to expand \p *dest to the appropriate size.  \p dest will be updated to the
300  * new pointer unless allocation fails.
301  *
302  * The result will always be null-terminated.
303  *
304  * This function differs from ralloc_strcat() and ralloc_strncat() in that it
305  * does not do any strlen() calls which can become costly on large strings.
306  *
307  * \return True unless allocation failed.
308  */
309 bool
310 ralloc_str_append(char **dest, const char *str,
311                   size_t existing_length, size_t str_size);
312 
313 /**
314  * Print to a string.
315  *
316  * This is analogous to \c sprintf, but allocates enough space (using \p ctx
317  * as the context) for the resulting string.
318  *
319  * \return The newly allocated string.
320  */
321 char *ralloc_asprintf (const void *ctx, const char *fmt, ...) PRINTFLIKE(2, 3) MALLOCLIKE;
322 
323 /**
324  * Print to a string, given a va_list.
325  *
326  * This is analogous to \c vsprintf, but allocates enough space (using \p ctx
327  * as the context) for the resulting string.
328  *
329  * \return The newly allocated string.
330  */
331 char *ralloc_vasprintf(const void *ctx, const char *fmt, va_list args) MALLOCLIKE;
332 
333 /**
334  * Rewrite the tail of an existing string, starting at a given index.
335  *
336  * Overwrites the contents of *str starting at \p start with newly formatted
337  * text, including a new null-terminator.  Allocates more memory as necessary.
338  *
339  * This can be used to append formatted text when the length of the existing
340  * string is already known, saving a strlen() call.
341  *
342  * \sa ralloc_asprintf_append
343  *
344  * \param str   The string to be updated.
345  * \param start The index to start appending new data at.
346  * \param fmt   A printf-style formatting string
347  *
348  * \p str will be updated to the new pointer unless allocation fails.
349  * \p start will be increased by the length of the newly formatted text.
350  *
351  * \return True unless allocation failed.
352  */
353 bool ralloc_asprintf_rewrite_tail(char **str, size_t *start,
354 				  const char *fmt, ...)
355 				  PRINTFLIKE(3, 4);
356 
357 /**
358  * Rewrite the tail of an existing string, starting at a given index.
359  *
360  * Overwrites the contents of *str starting at \p start with newly formatted
361  * text, including a new null-terminator.  Allocates more memory as necessary.
362  *
363  * This can be used to append formatted text when the length of the existing
364  * string is already known, saving a strlen() call.
365  *
366  * \sa ralloc_vasprintf_append
367  *
368  * \param str   The string to be updated.
369  * \param start The index to start appending new data at.
370  * \param fmt   A printf-style formatting string
371  * \param args  A va_list containing the data to be formatted
372  *
373  * \p str will be updated to the new pointer unless allocation fails.
374  * \p start will be increased by the length of the newly formatted text.
375  *
376  * \return True unless allocation failed.
377  */
378 bool ralloc_vasprintf_rewrite_tail(char **str, size_t *start, const char *fmt,
379 				   va_list args);
380 
381 /**
382  * Append formatted text to the supplied string.
383  *
384  * This is equivalent to
385  * \code
386  * ralloc_asprintf_rewrite_tail(str, strlen(*str), fmt, ...)
387  * \endcode
388  *
389  * \sa ralloc_asprintf
390  * \sa ralloc_asprintf_rewrite_tail
391  * \sa ralloc_strcat
392  *
393  * \p str will be updated to the new pointer unless allocation fails.
394  *
395  * \return True unless allocation failed.
396  */
397 bool ralloc_asprintf_append (char **str, const char *fmt, ...)
398 			     PRINTFLIKE(2, 3);
399 
400 /**
401  * Append formatted text to the supplied string, given a va_list.
402  *
403  * This is equivalent to
404  * \code
405  * ralloc_vasprintf_rewrite_tail(str, strlen(*str), fmt, args)
406  * \endcode
407  *
408  * \sa ralloc_vasprintf
409  * \sa ralloc_vasprintf_rewrite_tail
410  * \sa ralloc_strcat
411  *
412  * \p str will be updated to the new pointer unless allocation fails.
413  *
414  * \return True unless allocation failed.
415  */
416 bool ralloc_vasprintf_append(char **str, const char *fmt, va_list args);
417 /// @}
418 
419 /**
420  * Declare C++ new and delete operators which use ralloc.
421  *
422  * Placing this macro in the body of a class makes it possible to do:
423  *
424  * TYPE *var = new(mem_ctx) TYPE(...);
425  * delete var;
426  *
427  * which is more idiomatic in C++ than calling ralloc.
428  */
429 #define DECLARE_ALLOC_CXX_OPERATORS_TEMPLATE(TYPE, ALLOC_FUNC)           \
430 private:                                                                 \
431    static void _ralloc_destructor(void *p)                               \
432    {                                                                     \
433       reinterpret_cast<TYPE *>(p)->~TYPE();                              \
434    }                                                                     \
435 public:                                                                  \
436    static void* operator new(size_t size, void *mem_ctx)                 \
437    {                                                                     \
438       void *p = ALLOC_FUNC(mem_ctx, size);                               \
439       assert(p != NULL);                                                 \
440       if (!HAS_TRIVIAL_DESTRUCTOR(TYPE))                                 \
441          ralloc_set_destructor(p, _ralloc_destructor);                   \
442       return p;                                                          \
443    }                                                                     \
444                                                                          \
445    static void operator delete(void *p)                                  \
446    {                                                                     \
447       /* The object's destructor is guaranteed to have already been      \
448        * called by the delete operator at this point -- Make sure it's   \
449        * not called again.                                               \
450        */                                                                \
451       if (!HAS_TRIVIAL_DESTRUCTOR(TYPE))                                 \
452          ralloc_set_destructor(p, NULL);                                 \
453       ralloc_free(p);                                                    \
454    }
455 
456 #define DECLARE_RALLOC_CXX_OPERATORS(type) \
457    DECLARE_ALLOC_CXX_OPERATORS_TEMPLATE(type, ralloc_size)
458 
459 #define DECLARE_RZALLOC_CXX_OPERATORS(type) \
460    DECLARE_ALLOC_CXX_OPERATORS_TEMPLATE(type, rzalloc_size)
461 
462 #define DECLARE_LINEAR_ALLOC_CXX_OPERATORS(type) \
463    DECLARE_ALLOC_CXX_OPERATORS_TEMPLATE(type, linear_alloc_child)
464 
465 #define DECLARE_LINEAR_ZALLOC_CXX_OPERATORS(type) \
466    DECLARE_ALLOC_CXX_OPERATORS_TEMPLATE(type, linear_zalloc_child)
467 
468 
469 /**
470  * Do a fast allocation from the linear buffer, also known as the child node
471  * from the allocator's point of view. It can't be freed directly. You have
472  * to free the parent or the ralloc parent.
473  *
474  * \param parent   parent node of the linear allocator
475  * \param size     size to allocate (max 32 bits)
476  */
477 void *linear_alloc_child(void *parent, unsigned size);
478 
479 /**
480  * Allocate a parent node that will hold linear buffers. The returned
481  * allocation is actually the first child node, but it's also the handle
482  * of the parent node. Use it for all child node allocations.
483  *
484  * \param ralloc_ctx  ralloc context, must not be NULL
485  * \param size        size to allocate (max 32 bits)
486  */
487 void *linear_alloc_parent(void *ralloc_ctx, unsigned size);
488 
489 /**
490  * Same as linear_alloc_child, but also clears memory.
491  */
492 void *linear_zalloc_child(void *parent, unsigned size);
493 
494 /**
495  * Same as linear_alloc_parent, but also clears memory.
496  */
497 void *linear_zalloc_parent(void *ralloc_ctx, unsigned size);
498 
499 /**
500  * Free the linear parent node. This will free all child nodes too.
501  * Freeing the ralloc parent will also free this.
502  */
503 void linear_free_parent(void *ptr);
504 
505 /**
506  * Same as ralloc_steal, but steals the linear parent node.
507  */
508 void ralloc_steal_linear_parent(void *new_ralloc_ctx, void *ptr);
509 
510 /**
511  * Return the ralloc parent of the linear parent node.
512  */
513 void *ralloc_parent_of_linear_parent(void *ptr);
514 
515 /**
516  * Same as realloc except that the linear allocator doesn't free child nodes,
517  * so it's reduced to memory duplication. It's used in places where
518  * reallocation is required. Don't use it often. It's much slower than
519  * realloc.
520  */
521 void *linear_realloc(void *parent, void *old, unsigned new_size);
522 
523 /* The functions below have the same semantics as their ralloc counterparts,
524  * except that they always allocate a linear child node.
525  */
526 char *linear_strdup(void *parent, const char *str);
527 char *linear_asprintf(void *parent, const char *fmt, ...);
528 char *linear_vasprintf(void *parent, const char *fmt, va_list args);
529 bool linear_asprintf_append(void *parent, char **str, const char *fmt, ...);
530 bool linear_vasprintf_append(void *parent, char **str, const char *fmt,
531                              va_list args);
532 bool linear_asprintf_rewrite_tail(void *parent, char **str, size_t *start,
533                                   const char *fmt, ...);
534 bool linear_vasprintf_rewrite_tail(void *parent, char **str, size_t *start,
535                                    const char *fmt, va_list args);
536 bool linear_strcat(void *parent, char **dest, const char *str);
537 
538 #ifdef __cplusplus
539 } /* end of extern "C" */
540 #endif
541 
542 #endif
543