2 * astobj2 - replacement containers for asterisk data structures.
4 * Copyright (C) 2006 Marta Carbone, Luigi Rizzo - Univ. di Pisa, Italy
6 * See http://www.asterisk.org for more information about
7 * the Asterisk project. Please do not directly contact
8 * any of the maintainers of this project for assistance;
9 * the project provides a web site, mailing lists and IRC
10 * channels for your use.
12 * This program is free software, distributed under the terms of
13 * the GNU General Public License Version 2. See the LICENSE file
14 * at the top of the source tree.
18 * Function implementing astobj2 objects.
22 ASTERISK_FILE_VERSION(__FILE__
, "$Revision$")
24 #include "asterisk/astobj2.h"
25 #include "asterisk/utils.h"
26 #include "asterisk/cli.h"
29 * astobj2 objects are always prepended this data structure,
30 * which contains a lock, a reference counter,
31 * the flags and a pointer to a destructor.
32 * The refcount is used to decide when it is time to
33 * invoke the destructor.
34 * The magic number is used for consistency check.
35 * XXX the lock is not always needed, and its initialization may be
36 * expensive. Consider making it external.
41 ao2_destructor_fn destructor_fn
;
44 /*! magic number. This is used to verify that a pointer passed in is a
49 #define AO2_MAGIC 0xa570b123
52 * What an astobj2 object looks like: fixed-size private data
53 * followed by variable-size user data.
56 struct __priv_data priv_data
;
66 volatile int total_objects
;
67 volatile int total_mem
;
68 volatile int total_containers
;
69 volatile int total_refs
;
70 volatile int total_locked
;
73 static struct ao2_stats ao2
;
76 #ifndef HAVE_BKTR /* backtrace support */
79 #include <execinfo.h> /* for backtrace */
88 c
= backtrace(addresses
, N1
);
89 strings
= backtrace_symbols(addresses
,c
);
90 ast_verbose("backtrace returned: %d\n", c
);
91 for(i
= 0; i
< c
; i
++) {
92 ast_verbose("%d: %p %s\n", i
, addresses
[i
], strings
[i
]);
99 * \brief convert from a pointer _p to a user-defined object
101 * \return the pointer to the astobj2 structure
103 static inline struct astobj2
*INTERNAL_OBJ(void *user_data
)
108 ast_log(LOG_ERROR
, "user_data is NULL\n");
112 p
= (struct astobj2
*) ((char *) user_data
- sizeof(*p
));
113 if (AO2_MAGIC
!= (p
->priv_data
.magic
) ) {
114 ast_log(LOG_ERROR
, "bad magic number 0x%x for %p\n", p
->priv_data
.magic
, p
);
122 * \brief convert from a pointer _p to an astobj2 object
124 * \return the pointer to the user-defined portion.
126 #define EXTERNAL_OBJ(_p) ((_p) == NULL ? NULL : (_p)->user_data)
128 int ao2_lock(void *user_data
)
130 struct astobj2
*p
= INTERNAL_OBJ(user_data
);
136 ast_atomic_fetchadd_int(&ao2
.total_locked
, 1);
139 return ast_mutex_lock(&p
->priv_data
.lock
);
142 int ao2_unlock(void *user_data
)
144 struct astobj2
*p
= INTERNAL_OBJ(user_data
);
150 ast_atomic_fetchadd_int(&ao2
.total_locked
, -1);
153 return ast_mutex_unlock(&p
->priv_data
.lock
);
157 * The argument is a pointer to the user portion.
159 int ao2_ref(void *user_data
, const int delta
)
163 struct astobj2
*obj
= INTERNAL_OBJ(user_data
);
168 /* if delta is 0, just return the refcount */
170 return (obj
->priv_data
.ref_counter
);
172 /* we modify with an atomic operation the reference counter */
173 ret
= ast_atomic_fetchadd_int(&obj
->priv_data
.ref_counter
, delta
);
174 current_value
= ret
+ delta
;
177 ast_atomic_fetchadd_int(&ao2
.total_refs
, delta
);
180 /* this case must never happen */
181 if (current_value
< 0)
182 ast_log(LOG_ERROR
, "refcount %d on object %p\n", current_value
, user_data
);
184 if (current_value
<= 0) { /* last reference, destroy the object */
185 if (obj
->priv_data
.destructor_fn
!= NULL
)
186 obj
->priv_data
.destructor_fn(user_data
);
188 ast_mutex_destroy(&obj
->priv_data
.lock
);
190 ast_atomic_fetchadd_int(&ao2
.total_mem
, - obj
->priv_data
.data_size
);
191 ast_atomic_fetchadd_int(&ao2
.total_objects
, -1);
193 /* for safety, zero-out the astobj2 header and also the
194 * first word of the user-data, which we make sure is always
196 bzero(obj
, sizeof(struct astobj2
*) + sizeof(void *) );
204 * We always alloc at least the size of a void *,
205 * for debugging purposes.
207 void *ao2_alloc(size_t data_size
, ao2_destructor_fn destructor_fn
)
212 if (data_size
< sizeof(void *))
213 data_size
= sizeof(void *);
215 obj
= ast_calloc(1, sizeof(*obj
) + data_size
);
220 ast_mutex_init(&obj
->priv_data
.lock
);
221 obj
->priv_data
.magic
= AO2_MAGIC
;
222 obj
->priv_data
.data_size
= data_size
;
223 obj
->priv_data
.ref_counter
= 1;
224 obj
->priv_data
.destructor_fn
= destructor_fn
; /* can be NULL */
227 ast_atomic_fetchadd_int(&ao2
.total_objects
, 1);
228 ast_atomic_fetchadd_int(&ao2
.total_mem
, data_size
);
229 ast_atomic_fetchadd_int(&ao2
.total_refs
, 1);
232 /* return a pointer to the user data */
233 return EXTERNAL_OBJ(obj
);
236 /* internal callback to destroy a container. */
237 static void container_destruct(void *c
);
239 /* each bucket in the container is a tailq. */
240 AST_LIST_HEAD_NOLOCK(bucket
, bucket_list
);
243 * A container; stores the hash and callback functions, information on
244 * the size, the hash bucket heads, and a version number, starting at 0
245 * (for a newly created, empty container)
246 * and incremented every time an object is inserted or deleted.
247 * The assumption is that an object is never moved in a container,
248 * but removed and readded with the new number.
249 * The version number is especially useful when implementing iterators.
250 * In fact, we can associate a unique, monotonically increasing number to
251 * each object, which means that, within an iterator, we can store the
252 * version number of the current object, and easily look for the next one,
253 * which is the next one in the list with a higher number.
254 * Since all objects have a version >0, we can use 0 as a marker for
255 * 'we need the first object in the bucket'.
257 * \todo Linking and unlink objects is typically expensive, as it
258 * involves a malloc() of a small object which is very inefficient.
259 * To optimize this, we allocate larger arrays of bucket_list's
260 * when we run out of them, and then manage our own freelist.
261 * This will be more efficient as we can do the freelist management while
262 * we hold the lock (that we need anyways).
264 struct ao2_container
{
266 ao2_callback_fn cmp_fn
;
268 /*! Number of elements in the container */
270 /*! described above */
273 struct bucket buckets
[0];
277 * \brief always zero hash function
279 * it is convenient to have a hash function that always returns 0.
280 * This is basically used when we want to have a container that is
281 * a simple linked list.
285 static int hash_zero(const void *user_obj
, const int flags
)
291 * A container is just an object, after all!
293 struct ao2_container
*
294 ao2_container_alloc(const uint n_buckets
, ao2_hash_fn hash_fn
,
295 ao2_callback_fn cmp_fn
)
297 /* XXX maybe consistency check on arguments ? */
298 /* compute the container size */
299 size_t container_size
= sizeof(struct ao2_container
) + n_buckets
* sizeof(struct bucket
);
301 struct ao2_container
*c
= ao2_alloc(container_size
, container_destruct
);
306 c
->version
= 1; /* 0 is a reserved value here */
307 c
->n_buckets
= n_buckets
;
308 c
->hash_fn
= hash_fn
? hash_fn
: hash_zero
;
312 ast_atomic_fetchadd_int(&ao2
.total_containers
, 1);
319 * return the number of elements in the container
321 int ao2_container_count(struct ao2_container
*c
)
327 * A structure to create a linked list of entries,
328 * used within a bucket.
329 * XXX \todo this should be private to the container code
332 AST_LIST_ENTRY(bucket_list
) entry
;
334 struct astobj2
*astobj
; /* pointer to internal data */
338 * link an object to a container
340 void *__ao2_link(struct ao2_container
*c
, void *user_data
, int iax2_hack
)
343 /* create a new list entry */
344 struct bucket_list
*p
;
345 struct astobj2
*obj
= INTERNAL_OBJ(user_data
);
350 if (INTERNAL_OBJ(c
) == NULL
)
353 p
= ast_calloc(1, sizeof(*p
));
357 i
= c
->hash_fn(user_data
, OBJ_POINTER
);
362 p
->version
= ast_atomic_fetchadd_int(&c
->version
, 1);
364 AST_LIST_INSERT_HEAD(&c
->buckets
[i
], p
, entry
);
366 AST_LIST_INSERT_TAIL(&c
->buckets
[i
], p
, entry
);
367 ast_atomic_fetchadd_int(&c
->elements
, 1);
368 ao2_ref(user_data
, +1);
375 * \brief another convenience function is a callback that matches on address
377 int ao2_match_by_addr(void *user_data
, void *arg
, int flags
)
379 return (user_data
== arg
) ? (CMP_MATCH
| CMP_STOP
) : 0;
383 * Unlink an object from the container
384 * and destroy the associated * ao2_bucket_list structure.
386 void *ao2_unlink(struct ao2_container
*c
, void *user_data
)
388 if (INTERNAL_OBJ(user_data
) == NULL
) /* safety check on the argument */
391 ao2_callback(c
, OBJ_UNLINK
| OBJ_POINTER
| OBJ_NODATA
, ao2_match_by_addr
, user_data
);
397 * \brief special callback that matches all
399 static int cb_true(void *user_data
, void *arg
, int flags
)
405 * Browse the container using different stategies accoding the flags.
406 * \return Is a pointer to an object or to a list of object if OBJ_MULTIPLE is
409 void *ao2_callback(struct ao2_container
*c
,
410 const enum search_flags flags
,
411 ao2_callback_fn cb_fn
, void *arg
)
413 int i
, last
; /* search boundaries */
416 if (INTERNAL_OBJ(c
) == NULL
) /* safety check on the argument */
419 if ((flags
& (OBJ_MULTIPLE
| OBJ_NODATA
)) == OBJ_MULTIPLE
) {
420 ast_log(LOG_WARNING
, "multiple data return not implemented yet (flags %x)\n", flags
);
424 /* override the match function if necessary */
426 /* Removing this slightly changes the meaning of OBJ_POINTER, but makes it
427 * do what I want it to. I'd like to hint to ao2_callback that the arg is
428 * of the same object type, so it can be passed to the hash function.
429 * However, I don't want to imply that this is the object being searched for. */
430 if (flags
& OBJ_POINTER
)
431 cb_fn
= match_by_addr
;
434 if (cb_fn
== NULL
) /* if NULL, match everything */
437 * XXX this can be optimized.
438 * If we have a hash function and lookup by pointer,
439 * run the hash function. Otherwise, scan the whole container
440 * (this only for the time being. We need to optimize this.)
442 if ((flags
& OBJ_POINTER
)) /* we know hash can handle this case */
443 i
= c
->hash_fn(arg
, flags
& OBJ_POINTER
) % c
->n_buckets
;
444 else /* don't know, let's scan all buckets */
445 i
= -1; /* XXX this must be fixed later. */
447 /* determine the search boundaries: i..last-1 */
455 ao2_lock(c
); /* avoid modifications to the content */
457 for (; i
< last
; i
++) {
458 /* scan the list with prev-cur pointers */
459 struct bucket_list
*cur
;
461 AST_LIST_TRAVERSE_SAFE_BEGIN(&c
->buckets
[i
], cur
, entry
) {
462 int match
= cb_fn(EXTERNAL_OBJ(cur
->astobj
), arg
, flags
) & (CMP_MATCH
| CMP_STOP
);
464 /* we found the object, performing operations according flags */
465 if (match
== 0) { /* no match, no stop, continue */
467 } else if (match
== CMP_STOP
) { /* no match but stop, we are done */
471 /* we have a match (CMP_MATCH) here */
472 if (!(flags
& OBJ_NODATA
)) { /* if must return the object, record the value */
473 /* it is important to handle this case before the unlink */
474 ret
= EXTERNAL_OBJ(cur
->astobj
);
478 if (flags
& OBJ_UNLINK
) { /* must unlink */
479 struct bucket_list
*x
= cur
;
481 /* we are going to modify the container, so update version */
482 ast_atomic_fetchadd_int(&c
->version
, 1);
483 AST_LIST_REMOVE_CURRENT(&c
->buckets
[i
], entry
);
484 /* update number of elements and version */
485 ast_atomic_fetchadd_int(&c
->elements
, -1);
486 ao2_ref(EXTERNAL_OBJ(x
->astobj
), -1);
487 free(x
); /* free the link record */
490 if ((match
& CMP_STOP
) || (flags
& OBJ_MULTIPLE
) == 0) {
491 /* We found the only match we need */
492 i
= last
; /* force exit from outer loop */
495 if (!(flags
& OBJ_NODATA
)) {
496 #if 0 /* XXX to be completed */
498 * This is the multiple-return case. We need to link
499 * the object in a list. The refcount is already increased.
504 AST_LIST_TRAVERSE_SAFE_END
511 * the find function just invokes the default callback with some reasonable flags.
513 void *ao2_find(struct ao2_container
*c
, void *arg
, enum search_flags flags
)
515 return ao2_callback(c
, flags
, c
->cmp_fn
, arg
);
519 * initialize an iterator so we start from the first object
521 struct ao2_iterator
ao2_iterator_init(struct ao2_container
*c
, int flags
)
523 struct ao2_iterator a
= {
532 * move to the next element in the container.
534 void * ao2_iterator_next(struct ao2_iterator
*a
)
537 struct bucket_list
*p
= NULL
;
540 if (INTERNAL_OBJ(a
->c
) == NULL
)
543 if (!(a
->flags
& F_AO2I_DONTLOCK
))
546 /* optimization. If the container is unchanged and
547 * we have a pointer, try follow it
549 if (a
->c
->version
== a
->c_version
&& (p
= a
->obj
) ) {
550 if ( (p
= AST_LIST_NEXT(p
, entry
)) )
552 /* nope, start from the next bucket */
558 lim
= a
->c
->n_buckets
;
560 /* Browse the buckets array, moving to the next
561 * buckets if we don't find the entry in the current one.
562 * Stop when we find an element with version number greater
563 * than the current one (we reset the version to 0 when we
566 for (; a
->bucket
< lim
; a
->bucket
++, a
->version
= 0) {
567 /* scan the current bucket */
568 AST_LIST_TRAVERSE(&a
->c
->buckets
[a
->bucket
], p
, entry
) {
569 if (p
->version
> a
->version
)
576 a
->version
= p
->version
;
578 a
->c_version
= a
->c
->version
;
579 ret
= EXTERNAL_OBJ(p
->astobj
);
580 /* inc refcount of returned object */
584 if (!(a
->flags
& F_AO2I_DONTLOCK
))
590 /* callback for destroying container.
591 * we can make it simple as we know what it does
593 static int cd_cb(void *obj
, void *arg
, int flag
)
599 static void container_destruct(void *_c
)
601 struct ao2_container
*c
= _c
;
603 ao2_callback(c
, OBJ_UNLINK
, cd_cb
, NULL
);
606 ast_atomic_fetchadd_int(&ao2
.total_containers
, -1);
611 static int print_cb(void *obj
, void *arg
, int flag
)
614 char *s
= (char *)obj
;
616 ast_cli(*fd
, "string <%s>\n", s
);
623 static int handle_astobj2_stats(int fd
, int argc
, char *argv
[])
625 ast_cli(fd
, "Objects : %d\n", ao2
.total_objects
);
626 ast_cli(fd
, "Containers : %d\n", ao2
.total_containers
);
627 ast_cli(fd
, "Memory : %d\n", ao2
.total_mem
);
628 ast_cli(fd
, "Locked : %d\n", ao2
.total_locked
);
629 ast_cli(fd
, "Refs : %d\n", ao2
.total_refs
);
634 * This is testing code for astobj
636 static int handle_astobj2_test(int fd
, int argc
, char *argv
[])
638 struct ao2_container
*c1
;
641 static int prof_id
= -1;
644 prof_id
= ast_add_profile("ao2_alloc", 0);
646 ast_cli(fd
, "argc %d argv %s %s %s\n", argc
, argv
[0], argv
[1], argv
[2]);
648 ast_cli(fd
, "called astobj_test\n");
650 handle_astobj2_stats(fd
, 0, NULL
);
652 * allocate a container with no default callback, and no hash function.
653 * No hash means everything goes in the same bucket.
655 c1
= ao2_container_alloc(100, NULL
/* no callback */, NULL
/* no hash */);
656 ast_cli(fd
, "container allocated as %p\n", c1
);
659 * fill the container with objects.
660 * ao2_alloc() gives us a reference which we pass to the
661 * container when we do the insert.
663 for (i
= 0; i
< lim
; i
++) {
664 ast_mark(prof_id
, 1 /* start */);
665 obj
= ao2_alloc(80, NULL
);
666 ast_mark(prof_id
, 0 /* stop */);
667 ast_cli(fd
, "object %d allocated as %p\n", i
, obj
);
668 sprintf(obj
, "-- this is obj %d --", i
);
671 ast_cli(fd
, "testing callbacks\n");
672 ao2_callback(c1
, 0, print_cb
, &fd
);
674 ast_cli(fd
, "testing iterators, remove every second object\n");
676 struct ao2_iterator ai
;
679 ai
= ao2_iterator_init(c1
, 0);
680 while ( (obj
= ao2_iterator_next(&ai
)) ) {
681 ast_cli(fd
, "iterator on <%s>\n", obj
);
686 ast_cli(fd
, "testing iterators again\n");
687 ai
= ao2_iterator_init(c1
, 0);
688 while ( (obj
= ao2_iterator_next(&ai
)) ) {
689 ast_cli(fd
, "iterator on <%s>\n", obj
);
693 ast_cli(fd
, "testing callbacks again\n");
694 ao2_callback(c1
, 0, print_cb
, &fd
);
696 ast_verbose("now you should see an error message:\n");
697 ao2_ref(&i
, -1); /* i is not a valid object so we print an error here */
699 ast_cli(fd
, "destroy container\n");
700 ao2_ref(c1
, -1); /* destroy container */
701 handle_astobj2_stats(fd
, 0, NULL
);
705 static struct ast_cli_entry cli_astobj2
[] = {
706 { { "astobj2", "stats", NULL
},
707 handle_astobj2_stats
, "Print astobj2 statistics", },
708 { { "astobj2", "test", NULL
} , handle_astobj2_test
, "Test astobj2", },
710 #endif /* AO2_DEBUG */
712 int astobj2_init(void)
715 ast_cli_register_multiple(cli_astobj2
, ARRAY_LEN(cli_astobj2
));