e82b49b98a18d88ce2d150c68b88bf15d2037148
[asterisk/asterisk.git] / main / stringfields.c
1 /*
2  * Asterisk -- An open source telephony toolkit.
3  *
4  * Copyright (C) 2006, Digium, Inc.
5  *
6  * Kevin P. Fleming <kpfleming@digium.com>
7  *
8  * See http://www.asterisk.org for more information about
9  * the Asterisk project. Please do not directly contact
10  * any of the maintainers of this project for assistance;
11  * the project provides a web site, mailing lists and IRC
12  * channels for your use.
13  *
14  * This program is free software, distributed under the terms of
15  * the GNU General Public License Version 2. See the LICENSE file
16  * at the top of the source tree.
17  */
18
19 /*! \file
20  *
21  * \brief String fields
22  *
23  * \author Kevin P. Fleming <kpfleming@digium.com>
24  */
25
26 #include "asterisk.h"
27
28 ASTERISK_REGISTER_FILE()
29
30 #include "asterisk/stringfields.h"
31 #include "asterisk/utils.h"
32
33 /* this is a little complex... string fields are stored with their
34    allocated size in the bytes preceding the string; even the
35    constant 'empty' string has to be this way, so the code that
36    checks to see if there is enough room for a new string doesn't
37    have to have any special case checks
38 */
39
40 static const struct {
41         ast_string_field_allocation allocation;
42         char string[1];
43 } __ast_string_field_empty_buffer;
44
45 ast_string_field __ast_string_field_empty = __ast_string_field_empty_buffer.string;
46
47 #define ALLOCATOR_OVERHEAD 48
48
49 static size_t optimal_alloc_size(size_t size)
50 {
51         unsigned int count;
52
53         size += ALLOCATOR_OVERHEAD;
54
55         for (count = 1; size; size >>= 1, count++);
56
57         return (1 << count) - ALLOCATOR_OVERHEAD;
58 }
59
60 static void *calloc_wrapper(unsigned int num_structs, size_t struct_size,
61         const char *file, int lineno, const char *func)
62 {
63 #if defined(__AST_DEBUG_MALLOC)
64         return __ast_calloc(num_structs, struct_size, file, lineno, func);
65 #else
66         return ast_calloc(num_structs, struct_size);
67 #endif
68 }
69
70 /*! \brief add a new block to the pool.
71  * We can only allocate from the topmost pool, so the
72  * fields in *mgr reflect the size of that only.
73  */
74 static int add_string_pool(struct ast_string_field_mgr *mgr, struct ast_string_field_pool **pool_head,
75         size_t size, const char *file, int lineno, const char *func)
76 {
77         struct ast_string_field_pool *pool;
78         size_t alloc_size = optimal_alloc_size(sizeof(*pool) + size);
79
80         if (!(pool = calloc_wrapper(1, alloc_size, file, lineno, func))) {
81                 return -1;
82         }
83
84         pool->prev = *pool_head;
85         pool->size = alloc_size - sizeof(*pool);
86         *pool_head = pool;
87         mgr->last_alloc = NULL;
88
89         return 0;
90 }
91
92 static void reset_field(const char **p)
93 {
94         *p = __ast_string_field_empty;
95 }
96
97 /*!
98  * \brief Internal cleanup function
99  * \internal
100  * \param mgr
101  * \param pool_head
102  * \param cleanup_type
103  *           0: Reset all string fields and free all pools except the last or embedded pool.
104  *              Keep the internal management structures so the structure can be reused.
105  *          -1: Reset all string fields and free all pools except the embedded pool.
106  *              Free the internal management structures.
107  * \param file
108  * \param lineno
109  * \param func
110  *
111  * \retval 0 Success
112  * \retval -1 Failure
113  */
114 int __ast_string_field_free_memory(struct ast_string_field_mgr *mgr,
115         struct ast_string_field_pool **pool_head, enum ast_stringfield_cleanup_type cleanup_type,
116         const char *file, int lineno, const char *func)
117 {
118         struct ast_string_field_pool *cur = NULL;
119         struct ast_string_field_pool *preserve = NULL;
120
121         /* reset all the fields regardless of cleanup type */
122         AST_VECTOR_CALLBACK_VOID(&mgr->string_fields, reset_field);
123
124         switch (cleanup_type) {
125         case AST_STRINGFIELD_DESTROY:
126                 AST_VECTOR_FREE(&mgr->string_fields);
127
128                 if (mgr->embedded_pool) { /* ALWAYS preserve the embedded pool if there is one */
129                         preserve = mgr->embedded_pool;
130                         preserve->used = preserve->active = 0;
131                 }
132
133                 break;
134         case AST_STRINGFIELD_RESET:
135                 /* Preserve the embedded pool if there is one, otherwise the last pool */
136                 if (mgr->embedded_pool) {
137                         preserve = mgr->embedded_pool;
138                 } else {
139                         if (*pool_head == NULL) {
140                                 ast_log(LOG_WARNING, "trying to reset empty pool\n");
141                                 return -1;
142                         }
143                         preserve = *pool_head;
144                 }
145                 preserve->used = preserve->active = 0;
146                 break;
147         default:
148                 return -1;
149         }
150
151         cur = *pool_head;
152         while (cur) {
153                 struct ast_string_field_pool *prev = cur->prev;
154
155                 if (cur != preserve) {
156                         ast_free(cur);
157                 }
158                 cur = prev;
159         }
160
161         *pool_head = preserve;
162         if (preserve) {
163                 preserve->prev = NULL;
164         }
165
166         return 0;
167 }
168
169 /*!
170  * \brief Internal initialization function
171  * \internal
172  * \param mgr
173  * \param pool_head
174  * \param needed
175  * \param file
176  * \param lineno
177  * \param func
178  *
179  * \retval 0 Success
180  * \retval -1 Failure
181  */
182 int __ast_string_field_init(struct ast_string_field_mgr *mgr, struct ast_string_field_pool **pool_head,
183         int needed, const char *file, int lineno, const char *func)
184 {
185         const char **p = (const char **) pool_head + 1;
186         size_t initial_vector_size = ((size_t) (((char *)mgr) - ((char *)p))) / sizeof(*p);
187
188         if (needed <= 0) {
189                 return __ast_string_field_free_memory(mgr, pool_head, needed, file, lineno, func);
190         }
191
192         mgr->last_alloc = NULL;
193 #if defined(__AST_DEBUG_MALLOC)
194         mgr->owner_file = file;
195         mgr->owner_func = func;
196         mgr->owner_line = lineno;
197 #endif
198
199         if (AST_VECTOR_INIT(&mgr->string_fields, initial_vector_size)) {
200                 return -1;
201         }
202
203         while ((struct ast_string_field_mgr *) p != mgr) {
204                 AST_VECTOR_APPEND(&mgr->string_fields, p);
205                 *p++ = __ast_string_field_empty;
206         }
207
208         *pool_head = NULL;
209         mgr->embedded_pool = NULL;
210         if (add_string_pool(mgr, pool_head, needed, file, lineno, func)) {
211                 AST_VECTOR_FREE(&mgr->string_fields);
212                 return -1;
213         }
214
215         return 0;
216 }
217
218 ast_string_field __ast_string_field_alloc_space(struct ast_string_field_mgr *mgr,
219         struct ast_string_field_pool **pool_head, size_t needed)
220 {
221         char *result = NULL;
222         size_t space = (*pool_head)->size - (*pool_head)->used;
223         size_t to_alloc;
224
225         /* Make room for ast_string_field_allocation and make it a multiple of that. */
226         to_alloc = ast_make_room_for(needed, ast_string_field_allocation);
227         ast_assert(to_alloc % ast_alignof(ast_string_field_allocation) == 0);
228
229         if (__builtin_expect(to_alloc > space, 0)) {
230                 size_t new_size = (*pool_head)->size;
231
232                 while (new_size < to_alloc) {
233                         new_size *= 2;
234                 }
235
236 #if defined(__AST_DEBUG_MALLOC)
237                 if (add_string_pool(mgr, pool_head, new_size, mgr->owner_file, mgr->owner_line, mgr->owner_func))
238                         return NULL;
239 #else
240                 if (add_string_pool(mgr, pool_head, new_size, __FILE__, __LINE__, __FUNCTION__))
241                         return NULL;
242 #endif
243         }
244
245         /* pool->base is always aligned (gcc aligned attribute). We ensure that
246          * to_alloc is also a multiple of ast_alignof(ast_string_field_allocation)
247          * causing result to always be aligned as well; which in turn fixes that
248          * AST_STRING_FIELD_ALLOCATION(result) is aligned. */
249         result = (*pool_head)->base + (*pool_head)->used;
250         (*pool_head)->used += to_alloc;
251         (*pool_head)->active += needed;
252         result += ast_alignof(ast_string_field_allocation);
253         AST_STRING_FIELD_ALLOCATION(result) = needed;
254         mgr->last_alloc = result;
255
256         return result;
257 }
258
259 int __ast_string_field_ptr_grow(struct ast_string_field_mgr *mgr,
260         struct ast_string_field_pool **pool_head, size_t needed, const ast_string_field *ptr)
261 {
262         ssize_t grow = needed - AST_STRING_FIELD_ALLOCATION(*ptr);
263         size_t space = (*pool_head)->size - (*pool_head)->used;
264
265         if (*ptr != mgr->last_alloc) {
266                 return 1;
267         }
268
269         if (space < grow) {
270                 return 1;
271         }
272
273         (*pool_head)->used += grow;
274         (*pool_head)->active += grow;
275         AST_STRING_FIELD_ALLOCATION(*ptr) += grow;
276
277         return 0;
278 }
279
280 void __ast_string_field_release_active(struct ast_string_field_pool *pool_head,
281         const ast_string_field ptr)
282 {
283         struct ast_string_field_pool *pool, *prev;
284
285         if (ptr == __ast_string_field_empty) {
286                 return;
287         }
288
289         for (pool = pool_head, prev = NULL; pool; prev = pool, pool = pool->prev) {
290                 if ((ptr >= pool->base) && (ptr <= (pool->base + pool->size))) {
291                         pool->active -= AST_STRING_FIELD_ALLOCATION(ptr);
292                         if (pool->active == 0) {
293                                 if (prev) {
294                                         prev->prev = pool->prev;
295                                         ast_free(pool);
296                                 } else {
297                                         pool->used = 0;
298                                 }
299                         }
300                         break;
301                 }
302         }
303 }
304
305 void __ast_string_field_ptr_build_va(struct ast_string_field_mgr *mgr,
306         struct ast_string_field_pool **pool_head, ast_string_field *ptr,
307         const char *format, va_list ap)
308 {
309         size_t needed;
310         size_t available;
311         size_t space = (*pool_head)->size - (*pool_head)->used;
312         int res;
313         ssize_t grow;
314         char *target;
315         va_list ap2;
316
317         /* if the field already has space allocated, try to reuse it;
318            otherwise, try to use the empty space at the end of the current
319            pool
320         */
321         if (*ptr != __ast_string_field_empty) {
322                 target = (char *) *ptr;
323                 available = AST_STRING_FIELD_ALLOCATION(*ptr);
324                 if (*ptr == mgr->last_alloc) {
325                         available += space;
326                 }
327         } else {
328                 /* pool->used is always a multiple of ast_alignof(ast_string_field_allocation)
329                  * so we don't need to re-align anything here.
330                  */
331                 target = (*pool_head)->base + (*pool_head)->used + ast_alignof(ast_string_field_allocation);
332                 if (space > ast_alignof(ast_string_field_allocation)) {
333                         available = space - ast_alignof(ast_string_field_allocation);
334                 } else {
335                         available = 0;
336                 }
337         }
338
339         va_copy(ap2, ap);
340         res = vsnprintf(target, available, format, ap2);
341         va_end(ap2);
342
343         if (res < 0) {
344                 /* Are we out of memory? */
345                 return;
346         }
347         if (res == 0) {
348                 __ast_string_field_release_active(*pool_head, *ptr);
349                 *ptr = __ast_string_field_empty;
350                 return;
351         }
352         needed = (size_t)res + 1; /* NUL byte */
353
354         if (needed > available) {
355                 /* the allocation could not be satisfied using the field's current allocation
356                    (if it has one), or the space available in the pool (if it does not). allocate
357                    space for it, adding a new string pool if necessary.
358                 */
359                 if (!(target = (char *) __ast_string_field_alloc_space(mgr, pool_head, needed))) {
360                         return;
361                 }
362                 vsprintf(target, format, ap);
363                 va_end(ap); /* XXX va_end without va_start? */
364                 __ast_string_field_release_active(*pool_head, *ptr);
365                 *ptr = target;
366         } else if (*ptr != target) {
367                 /* the allocation was satisfied using available space in the pool, but not
368                    using the space already allocated to the field
369                 */
370                 __ast_string_field_release_active(*pool_head, *ptr);
371                 mgr->last_alloc = *ptr = target;
372                 ast_assert(needed < (ast_string_field_allocation)-1);
373                 AST_STRING_FIELD_ALLOCATION(target) = (ast_string_field_allocation)needed;
374                 (*pool_head)->used += ast_make_room_for(needed, ast_string_field_allocation);
375                 (*pool_head)->active += needed;
376         } else if ((grow = (needed - AST_STRING_FIELD_ALLOCATION(*ptr))) > 0) {
377                 /* the allocation was satisfied by using available space in the pool *and*
378                    the field was the last allocated field from the pool, so it grew
379                 */
380                 AST_STRING_FIELD_ALLOCATION(*ptr) += grow;
381                 (*pool_head)->used += ast_align_for(grow, ast_string_field_allocation);
382                 (*pool_head)->active += grow;
383         }
384 }
385
386 void __ast_string_field_ptr_build(struct ast_string_field_mgr *mgr,
387         struct ast_string_field_pool **pool_head, ast_string_field *ptr, const char *format, ...)
388 {
389         va_list ap;
390
391         va_start(ap, format);
392         __ast_string_field_ptr_build_va(mgr, pool_head, ptr, format, ap);
393         va_end(ap);
394 }
395
396 void *__ast_calloc_with_stringfields(unsigned int num_structs, size_t struct_size,
397         size_t field_mgr_offset, size_t field_mgr_pool_offset, size_t pool_size, const char *file,
398         int lineno, const char *func)
399 {
400         struct ast_string_field_mgr *mgr;
401         struct ast_string_field_pool *pool;
402         struct ast_string_field_pool **pool_head;
403         size_t pool_size_needed = sizeof(*pool) + pool_size;
404         size_t size_to_alloc = optimal_alloc_size(struct_size + pool_size_needed);
405         void *allocation;
406         const char **p;
407         size_t initial_vector_size;
408
409         ast_assert(num_structs == 1);
410
411         if (!(allocation = calloc_wrapper(num_structs, size_to_alloc, file, lineno, func))) {
412                 return NULL;
413         }
414
415         mgr = allocation + field_mgr_offset;
416
417         pool = allocation + struct_size;
418         pool_head = allocation + field_mgr_pool_offset;
419         p = (const char **) pool_head + 1;
420         initial_vector_size = ((size_t) (((char *)mgr) - ((char *)p))) / sizeof(*p);
421
422         if (AST_VECTOR_INIT(&mgr->string_fields, initial_vector_size)) {
423                 ast_free(allocation);
424                 return NULL;
425         }
426
427         while ((struct ast_string_field_mgr *) p != mgr) {
428                 AST_VECTOR_APPEND(&mgr->string_fields, p);
429                 *p++ = __ast_string_field_empty;
430         }
431
432         mgr->embedded_pool = pool;
433         *pool_head = pool;
434         pool->size = size_to_alloc - struct_size - sizeof(*pool);
435 #if defined(__AST_DEBUG_MALLOC)
436                 mgr->owner_file = file;
437                 mgr->owner_func = func;
438                 mgr->owner_line = lineno;
439 #endif
440
441         return allocation;
442 }
443
444 int __ast_string_fields_cmp(struct ast_string_field_vector *left,
445         struct ast_string_field_vector *right)
446 {
447         int i;
448         int res = 0;
449
450         ast_assert(AST_VECTOR_SIZE(left) == AST_VECTOR_SIZE(right));
451
452         for (i = 0; i < AST_VECTOR_SIZE(left); i++) {
453                 if ((res = strcmp(*AST_VECTOR_GET(left, i), *AST_VECTOR_GET(right, i)))) {
454                         return res;
455                 }
456         }
457
458         return res;
459 }
460
461 int __ast_string_fields_copy(struct ast_string_field_pool *copy_pool,
462         struct ast_string_field_mgr *copy_mgr, struct ast_string_field_mgr *orig_mgr)
463 {
464         int i;
465         struct ast_string_field_vector *dest = &(copy_mgr->string_fields);
466         struct ast_string_field_vector *src = &(orig_mgr->string_fields);
467
468         ast_assert(AST_VECTOR_SIZE(dest) == AST_VECTOR_SIZE(src));
469
470         for (i = 0; i < AST_VECTOR_SIZE(dest); i++) {
471                 __ast_string_field_release_active(copy_pool, *AST_VECTOR_GET(dest, i));
472                 *AST_VECTOR_GET(dest, i) = __ast_string_field_empty;
473         }
474
475         for (i = 0; i < AST_VECTOR_SIZE(dest); i++) {
476                 if (ast_string_field_ptr_set_by_fields(copy_pool, *copy_mgr, AST_VECTOR_GET(dest, i),
477                         *AST_VECTOR_GET(src, i))) {
478                         return -1;
479                 }
480         }
481
482         return 0;
483 }