Tue Aug 20 16:34:25 2013

Asterisk developer's documentation


astobj2.c

Go to the documentation of this file.
00001 /*
00002  * astobj2 - replacement containers for asterisk data structures.
00003  *
00004  * Copyright (C) 2006 Marta Carbone, Luigi Rizzo - Univ. di Pisa, Italy
00005  *
00006  * See http://www.asterisk.org for more information about
00007  * the Asterisk project. Please do not directly contact
00008  * any of the maintainers of this project for assistance;
00009  * the project provides a web site, mailing lists and IRC
00010  * channels for your use.
00011  *
00012  * This program is free software, distributed under the terms of
00013  * the GNU General Public License Version 2. See the LICENSE file
00014  * at the top of the source tree.
00015  */
00016 
00017 /*
00018  * Function implementing astobj2 objects.
00019  */
00020 
00021 /*** MODULEINFO
00022    <support_level>core</support_level>
00023  ***/
00024 
00025 #include "asterisk.h"
00026 
00027 ASTERISK_FILE_VERSION(__FILE__, "$Revision: 379963 $")
00028 
00029 #include "asterisk/_private.h"
00030 #include "asterisk/astobj2.h"
00031 #include "asterisk/utils.h"
00032 #include "asterisk/cli.h"
00033 #define REF_FILE "/tmp/refs"
00034 
00035 /*!
00036  * astobj2 objects are always preceded by this data structure,
00037  * which contains a lock, a reference counter,
00038  * the flags and a pointer to a destructor.
00039  * The refcount is used to decide when it is time to
00040  * invoke the destructor.
00041  * The magic number is used for consistency check.
00042  * XXX the lock is not always needed, and its initialization may be
00043  * expensive. Consider making it external.
00044  */
00045 struct __priv_data {
00046    ast_mutex_t lock;
00047    int ref_counter;
00048    ao2_destructor_fn destructor_fn;
00049    /*! for stats */
00050    size_t data_size;
00051    /*! magic number.  This is used to verify that a pointer passed in is a
00052     *  valid astobj2 */
00053    uint32_t magic;
00054 };
00055 
00056 #define  AO2_MAGIC   0xa570b123
00057 
00058 /*!
00059  * What an astobj2 object looks like: fixed-size private data
00060  * followed by variable-size user data.
00061  */
00062 struct astobj2 {
00063    struct __priv_data priv_data;
00064    void *user_data[0];
00065 };
00066 
00067 #ifdef AST_DEVMODE
00068 /* #define AO2_DEBUG 1 */
00069 #endif
00070 
00071 #ifdef AO2_DEBUG
00072 struct ao2_stats {
00073    volatile int total_objects;
00074    volatile int total_mem;
00075    volatile int total_containers;
00076    volatile int total_refs;
00077    volatile int total_locked;
00078 };
00079 
00080 static struct ao2_stats ao2;
00081 #endif
00082 
00083 #ifndef HAVE_BKTR /* backtrace support */
00084 void ao2_bt(void) {}
00085 #else
00086 #include <execinfo.h>    /* for backtrace */
00087 
00088 void ao2_bt(void)
00089 {
00090    int c, i;
00091 #define N1  20
00092    void *addresses[N1];
00093    char **strings;
00094 
00095    c = backtrace(addresses, N1);
00096    strings = ast_bt_get_symbols(addresses,c);
00097    ast_verbose("backtrace returned: %d\n", c);
00098    for(i = 0; i < c; i++) {
00099       ast_verbose("%d: %p %s\n", i, addresses[i], strings[i]);
00100    }
00101    free(strings);
00102 }
00103 #endif
00104 
00105 /*!
00106  * \brief convert from a pointer _p to a user-defined object
00107  *
00108  * \return the pointer to the astobj2 structure
00109  */
00110 static inline struct astobj2 *INTERNAL_OBJ(void *user_data)
00111 {
00112    struct astobj2 *p;
00113 
00114    if (!user_data) {
00115       ast_log(LOG_ERROR, "user_data is NULL\n");
00116       return NULL;
00117    }
00118 
00119    p = (struct astobj2 *) ((char *) user_data - sizeof(*p));
00120    if (AO2_MAGIC != p->priv_data.magic) {
00121       if (p->priv_data.magic) {
00122          ast_log(LOG_ERROR, "bad magic number 0x%x for object %p\n",
00123             p->priv_data.magic, user_data);
00124       } else {
00125          ast_log(LOG_ERROR,
00126             "bad magic number for object %p. Object is likely destroyed.\n",
00127             user_data);
00128       }
00129       return NULL;
00130    }
00131 
00132    return p;
00133 }
00134 
00135 enum ao2_callback_type {
00136    DEFAULT,
00137    WITH_DATA,
00138 };
00139 
00140 /*!
00141  * \brief convert from a pointer _p to an astobj2 object
00142  *
00143  * \return the pointer to the user-defined portion.
00144  */
00145 #define EXTERNAL_OBJ(_p)   ((_p) == NULL ? NULL : (_p)->user_data)
00146 
00147 /* the underlying functions common to debug and non-debug versions */
00148 
00149 static int internal_ao2_ref(void *user_data, const int delta);
00150 static struct ao2_container *internal_ao2_container_alloc(struct ao2_container *c, const uint n_buckets, ao2_hash_fn *hash_fn,
00151                        ao2_callback_fn *cmp_fn);
00152 static struct bucket_entry *internal_ao2_link(struct ao2_container *c, void *user_data, const char *file, int line, const char *func);
00153 static void *internal_ao2_callback(struct ao2_container *c,
00154                const enum search_flags flags, void *cb_fn, void *arg, void *data, enum ao2_callback_type type,
00155                char *tag, char *file, int line, const char *funcname);
00156 static void *internal_ao2_iterator_next(struct ao2_iterator *a, struct bucket_entry **q);
00157 
00158 int __ao2_lock(void *user_data, const char *file, const char *func, int line, const char *var)
00159 {
00160    struct astobj2 *p = INTERNAL_OBJ(user_data);
00161 
00162    if (p == NULL)
00163       return -1;
00164 
00165 #ifdef AO2_DEBUG
00166    ast_atomic_fetchadd_int(&ao2.total_locked, 1);
00167 #endif
00168 
00169    return __ast_pthread_mutex_lock(file, line, func, var, &p->priv_data.lock);
00170 }
00171 
00172 int __ao2_unlock(void *user_data, const char *file, const char *func, int line, const char *var)
00173 {
00174    struct astobj2 *p = INTERNAL_OBJ(user_data);
00175 
00176    if (p == NULL)
00177       return -1;
00178 
00179 #ifdef AO2_DEBUG
00180    ast_atomic_fetchadd_int(&ao2.total_locked, -1);
00181 #endif
00182 
00183    return __ast_pthread_mutex_unlock(file, line, func, var, &p->priv_data.lock);
00184 }
00185 
00186 int __ao2_trylock(void *user_data, const char *file, const char *func, int line, const char *var)
00187 {
00188    struct astobj2 *p = INTERNAL_OBJ(user_data);
00189    int ret;
00190    
00191    if (p == NULL)
00192       return -1;
00193    ret = __ast_pthread_mutex_trylock(file, line, func, var, &p->priv_data.lock);
00194 
00195 #ifdef AO2_DEBUG
00196    if (!ret)
00197       ast_atomic_fetchadd_int(&ao2.total_locked, 1);
00198 #endif
00199    return ret;
00200 }
00201 
00202 void *ao2_object_get_lockaddr(void *obj)
00203 {
00204    struct astobj2 *p = INTERNAL_OBJ(obj);
00205    
00206    if (p == NULL)
00207       return NULL;
00208 
00209    return &p->priv_data.lock;
00210 }
00211 
00212 /*
00213  * The argument is a pointer to the user portion.
00214  */
00215 
00216 
00217 int __ao2_ref_debug(void *user_data, const int delta, const char *tag, const char *file, int line, const char *funcname)
00218 {
00219    struct astobj2 *obj = INTERNAL_OBJ(user_data);
00220    
00221    if (obj == NULL)
00222       return -1;
00223 
00224    if (delta != 0) {
00225       FILE *refo = fopen(REF_FILE, "a");
00226       if (refo) {
00227          fprintf(refo, "%p %s%d   %s:%d:%s (%s) [@%d]\n", user_data, (delta < 0 ? "" : "+"),
00228             delta, file, line, funcname, tag, obj ? obj->priv_data.ref_counter : -1);
00229          fclose(refo);
00230       }
00231    }
00232    if (obj->priv_data.ref_counter + delta == 0 && obj->priv_data.destructor_fn != NULL) { /* this isn't protected with lock; just for o/p */
00233       FILE *refo = fopen(REF_FILE, "a");
00234       if (refo) {
00235          fprintf(refo, "%p **call destructor** %s:%d:%s (%s)\n", user_data, file, line, funcname, tag);
00236          fclose(refo);
00237       }
00238    }
00239    return internal_ao2_ref(user_data, delta);
00240 }
00241 
00242 int __ao2_ref(void *user_data, const int delta)
00243 {
00244    return internal_ao2_ref(user_data, delta);
00245 }
00246 
00247 static int internal_ao2_ref(void *user_data, const int delta)
00248 {
00249    struct astobj2 *obj = INTERNAL_OBJ(user_data);
00250    int current_value;
00251    int ret;
00252 
00253    if (obj == NULL)
00254       return -1;
00255 
00256    /* if delta is 0, just return the refcount */
00257    if (delta == 0)
00258       return (obj->priv_data.ref_counter);
00259 
00260    /* we modify with an atomic operation the reference counter */
00261    ret = ast_atomic_fetchadd_int(&obj->priv_data.ref_counter, delta);
00262    current_value = ret + delta;
00263 
00264 #ifdef AO2_DEBUG  
00265    ast_atomic_fetchadd_int(&ao2.total_refs, delta);
00266 #endif
00267 
00268    /* this case must never happen */
00269    if (current_value < 0)
00270       ast_log(LOG_ERROR, "refcount %d on object %p\n", current_value, user_data);
00271 
00272    if (current_value <= 0) { /* last reference, destroy the object */
00273       if (obj->priv_data.destructor_fn != NULL) {
00274          obj->priv_data.destructor_fn(user_data);
00275       }
00276 
00277       ast_mutex_destroy(&obj->priv_data.lock);
00278 #ifdef AO2_DEBUG
00279       ast_atomic_fetchadd_int(&ao2.total_mem, - obj->priv_data.data_size);
00280       ast_atomic_fetchadd_int(&ao2.total_objects, -1);
00281 #endif
00282       /* for safety, zero-out the astobj2 header and also the
00283        * first word of the user-data, which we make sure is always
00284        * allocated. */
00285       memset(obj, '\0', sizeof(struct astobj2 *) + sizeof(void *) );
00286       ast_free(obj);
00287    }
00288 
00289    return ret;
00290 }
00291 
00292 /*
00293  * We always alloc at least the size of a void *,
00294  * for debugging purposes.
00295  */
00296 static void *internal_ao2_alloc(size_t data_size, ao2_destructor_fn destructor_fn, const char *file, int line, const char *funcname)
00297 {
00298    /* allocation */
00299    struct astobj2 *obj;
00300 
00301    if (data_size < sizeof(void *))
00302       data_size = sizeof(void *);
00303 
00304 #if defined(__AST_DEBUG_MALLOC)
00305    obj = __ast_calloc(1, sizeof(*obj) + data_size, file, line, funcname);
00306 #else
00307    obj = ast_calloc(1, sizeof(*obj) + data_size);
00308 #endif
00309 
00310    if (obj == NULL)
00311       return NULL;
00312 
00313    ast_mutex_init(&obj->priv_data.lock);
00314    obj->priv_data.magic = AO2_MAGIC;
00315    obj->priv_data.data_size = data_size;
00316    obj->priv_data.ref_counter = 1;
00317    obj->priv_data.destructor_fn = destructor_fn;   /* can be NULL */
00318 
00319 #ifdef AO2_DEBUG
00320    ast_atomic_fetchadd_int(&ao2.total_objects, 1);
00321    ast_atomic_fetchadd_int(&ao2.total_mem, data_size);
00322    ast_atomic_fetchadd_int(&ao2.total_refs, 1);
00323 #endif
00324 
00325    /* return a pointer to the user data */
00326    return EXTERNAL_OBJ(obj);
00327 }
00328 
00329 void *__ao2_alloc_debug(size_t data_size, ao2_destructor_fn destructor_fn, char *tag,
00330          const char *file, int line, const char *funcname, int ref_debug)
00331 {
00332    /* allocation */
00333    void *obj;
00334    FILE *refo;
00335 
00336    if ((obj = internal_ao2_alloc(data_size, destructor_fn, file, line, funcname)) == NULL) {
00337       return NULL;
00338    }
00339 
00340    if (ref_debug && (refo = fopen(REF_FILE, "a"))) {
00341       fprintf(refo, "%p =1   %s:%d:%s (%s)\n", obj, file, line, funcname, tag);
00342       fclose(refo);
00343    }
00344 
00345    /* return a pointer to the user data */
00346    return obj;
00347 }
00348 
00349 void *__ao2_alloc(size_t data_size, ao2_destructor_fn destructor_fn)
00350 {
00351    return internal_ao2_alloc(data_size, destructor_fn, __FILE__, __LINE__, __FUNCTION__);
00352 }
00353 
00354 
00355 /* internal callback to destroy a container. */
00356 static void container_destruct(void *c);
00357 
00358 /* internal callback to destroy a container. */
00359 static void container_destruct_debug(void *c);
00360 
00361 /* each bucket in the container is a tailq. */
00362 AST_LIST_HEAD_NOLOCK(bucket, bucket_entry);
00363 
00364 /*!
00365  * A container; stores the hash and callback functions, information on
00366  * the size, the hash bucket heads, and a version number, starting at 0
00367  * (for a newly created, empty container)
00368  * and incremented every time an object is inserted or deleted.
00369  * The assumption is that an object is never moved in a container,
00370  * but removed and readded with the new number.
00371  * The version number is especially useful when implementing iterators.
00372  * In fact, we can associate a unique, monotonically increasing number to
00373  * each object, which means that, within an iterator, we can store the
00374  * version number of the current object, and easily look for the next one,
00375  * which is the next one in the list with a higher number.
00376  * Since all objects have a version >0, we can use 0 as a marker for
00377  * 'we need the first object in the bucket'.
00378  *
00379  * \todo Linking and unlink objects is typically expensive, as it
00380  * involves a malloc() of a small object which is very inefficient.
00381  * To optimize this, we allocate larger arrays of bucket_entry's
00382  * when we run out of them, and then manage our own freelist.
00383  * This will be more efficient as we can do the freelist management while
00384  * we hold the lock (that we need anyways).
00385  */
00386 struct ao2_container {
00387    ao2_hash_fn *hash_fn;
00388    ao2_callback_fn *cmp_fn;
00389    int n_buckets;
00390    /*! Number of elements in the container */
00391    int elements;
00392    /*! described above */
00393    int version;
00394    /*! variable size */
00395    struct bucket buckets[0];
00396 };
00397  
00398 /*!
00399  * \brief always zero hash function
00400  *
00401  * it is convenient to have a hash function that always returns 0.
00402  * This is basically used when we want to have a container that is
00403  * a simple linked list.
00404  *
00405  * \returns 0
00406  */
00407 static int hash_zero(const void *user_obj, const int flags)
00408 {
00409    return 0;
00410 }
00411 
00412 /*
00413  * A container is just an object, after all!
00414  */
00415 static struct ao2_container *internal_ao2_container_alloc(struct ao2_container *c, const unsigned int n_buckets, ao2_hash_fn *hash_fn,
00416                        ao2_callback_fn *cmp_fn)
00417 {
00418    /* XXX maybe consistency check on arguments ? */
00419    /* compute the container size */
00420 
00421    if (!c)
00422       return NULL;
00423    
00424    c->version = 1;   /* 0 is a reserved value here */
00425    c->n_buckets = hash_fn ? n_buckets : 1;
00426    c->hash_fn = hash_fn ? hash_fn : hash_zero;
00427    c->cmp_fn = cmp_fn;
00428 
00429 #ifdef AO2_DEBUG
00430    ast_atomic_fetchadd_int(&ao2.total_containers, 1);
00431 #endif
00432 
00433    return c;
00434 }
00435 
00436 struct ao2_container *__ao2_container_alloc_debug(const unsigned int n_buckets, ao2_hash_fn *hash_fn,
00437                     ao2_callback_fn *cmp_fn, char *tag, char *file, int line,
00438                     const char *funcname, int ref_debug)
00439 {
00440    /* XXX maybe consistency check on arguments ? */
00441    /* compute the container size */
00442    const unsigned int num_buckets = hash_fn ? n_buckets : 1;
00443    size_t container_size = sizeof(struct ao2_container) + num_buckets * sizeof(struct bucket);
00444    struct ao2_container *c = __ao2_alloc_debug(container_size, container_destruct_debug, tag, file, line, funcname, ref_debug);
00445 
00446    return internal_ao2_container_alloc(c, num_buckets, hash_fn, cmp_fn);
00447 }
00448 
00449 struct ao2_container *__ao2_container_alloc(const unsigned int n_buckets, ao2_hash_fn *hash_fn,
00450                    ao2_callback_fn *cmp_fn)
00451 {
00452    /* XXX maybe consistency check on arguments ? */
00453    /* compute the container size */
00454 
00455    const unsigned int num_buckets = hash_fn ? n_buckets : 1;
00456    size_t container_size = sizeof(struct ao2_container) + num_buckets * sizeof(struct bucket);
00457    struct ao2_container *c = __ao2_alloc(container_size, container_destruct);
00458 
00459    return internal_ao2_container_alloc(c, num_buckets, hash_fn, cmp_fn);
00460 }
00461 
00462 /*!
00463  * return the number of elements in the container
00464  */
00465 int ao2_container_count(struct ao2_container *c)
00466 {
00467    return c->elements;
00468 }
00469 
00470 /*!
00471  * A structure to create a linked list of entries,
00472  * used within a bucket.
00473  * XXX \todo this should be private to the container code
00474  */
00475 struct bucket_entry {
00476    AST_LIST_ENTRY(bucket_entry) entry;
00477    int version;
00478    struct astobj2 *astobj;    /* pointer to internal data */
00479 }; 
00480 
00481 /*
00482  * link an object to a container
00483  */
00484 
00485 static struct bucket_entry *internal_ao2_link(struct ao2_container *c, void *user_data, const char *file, int line, const char *func)
00486 {
00487    int i;
00488    /* create a new list entry */
00489    struct bucket_entry *p;
00490    struct astobj2 *obj = INTERNAL_OBJ(user_data);
00491 
00492    if (obj == NULL)
00493       return NULL;
00494 
00495    if (INTERNAL_OBJ(c) == NULL)
00496       return NULL;
00497 
00498    p = ast_calloc(1, sizeof(*p));
00499    if (!p)
00500       return NULL;
00501 
00502    i = abs(c->hash_fn(user_data, OBJ_POINTER));
00503 
00504    ao2_lock(c);
00505    i %= c->n_buckets;
00506    p->astobj = obj;
00507    p->version = ast_atomic_fetchadd_int(&c->version, 1);
00508    AST_LIST_INSERT_TAIL(&c->buckets[i], p, entry);
00509    ast_atomic_fetchadd_int(&c->elements, 1);
00510 
00511    /* the last two operations (ao2_ref, ao2_unlock) must be done by the calling func */
00512    return p;
00513 }
00514 
00515 void *__ao2_link_debug(struct ao2_container *c, void *user_data, char *tag, char *file, int line, const char *funcname)
00516 {
00517    struct bucket_entry *p = internal_ao2_link(c, user_data, file, line, funcname);
00518 
00519    if (p) {
00520       __ao2_ref_debug(user_data, +1, tag, file, line, funcname);
00521       ao2_unlock(c);
00522    }
00523    return p;
00524 }
00525 
00526 void *__ao2_link(struct ao2_container *c, void *user_data)
00527 {
00528    struct bucket_entry *p = internal_ao2_link(c, user_data, __FILE__, __LINE__, __PRETTY_FUNCTION__);
00529 
00530    if (p) {
00531       __ao2_ref(user_data, +1);
00532       ao2_unlock(c);
00533    }
00534    return p;
00535 }
00536 
00537 /*!
00538  * \brief another convenience function is a callback that matches on address
00539  */
00540 int ao2_match_by_addr(void *user_data, void *arg, int flags)
00541 {
00542    return (user_data == arg) ? (CMP_MATCH | CMP_STOP) : 0;
00543 }
00544 
00545 /*
00546  * Unlink an object from the container
00547  * and destroy the associated * bucket_entry structure.
00548  */
00549 void *__ao2_unlink_debug(struct ao2_container *c, void *user_data, char *tag,
00550           char *file, int line, const char *funcname)
00551 {
00552    if (INTERNAL_OBJ(user_data) == NULL)   /* safety check on the argument */
00553       return NULL;
00554 
00555    __ao2_callback_debug(c, OBJ_UNLINK | OBJ_POINTER | OBJ_NODATA, ao2_match_by_addr, user_data, tag, file, line, funcname);
00556 
00557    return NULL;
00558 }
00559 
00560 void *__ao2_unlink(struct ao2_container *c, void *user_data)
00561 {
00562    if (INTERNAL_OBJ(user_data) == NULL)   /* safety check on the argument */
00563       return NULL;
00564 
00565    __ao2_callback(c, OBJ_UNLINK | OBJ_POINTER | OBJ_NODATA, ao2_match_by_addr, user_data);
00566 
00567    return NULL;
00568 }
00569 
00570 /*! 
00571  * \brief special callback that matches all 
00572  */ 
00573 static int cb_true(void *user_data, void *arg, int flags)
00574 {
00575    return CMP_MATCH;
00576 }
00577 
00578 /*!
00579  * \brief similar to cb_true, but is an ao2_callback_data_fn instead
00580  */
00581 static int cb_true_data(void *user_data, void *arg, void *data, int flags)
00582 {
00583    return CMP_MATCH;
00584 }
00585 
00586 /*!
00587  * Browse the container using different stategies accoding the flags.
00588  * \return Is a pointer to an object or to a list of object if OBJ_MULTIPLE is 
00589  * specified.
00590  * Luckily, for debug purposes, the added args (tag, file, line, funcname)
00591  * aren't an excessive load to the system, as the callback should not be
00592  * called as often as, say, the ao2_ref func is called.
00593  */
00594 static void *internal_ao2_callback(struct ao2_container *c,
00595                const enum search_flags flags, void *cb_fn, void *arg, void *data, enum ao2_callback_type type,
00596                char *tag, char *file, int line, const char *funcname)
00597 {
00598    int i, start, last;  /* search boundaries */
00599    void *ret = NULL;
00600    ao2_callback_fn *cb_default = NULL;
00601    ao2_callback_data_fn *cb_withdata = NULL;
00602    struct ao2_container *multi_container = NULL;
00603    struct ao2_iterator *multi_iterator = NULL;
00604 
00605    if (INTERNAL_OBJ(c) == NULL)  /* safety check on the argument */
00606       return NULL;
00607 
00608    /*
00609     * This logic is used so we can support OBJ_MULTIPLE with OBJ_NODATA
00610     * turned off.  This if statement checks for the special condition
00611     * where multiple items may need to be returned.
00612     */
00613    if ((flags & (OBJ_MULTIPLE | OBJ_NODATA)) == OBJ_MULTIPLE) {
00614       /* we need to return an ao2_iterator with the results,
00615        * as there could be more than one. the iterator will
00616        * hold the only reference to a container that has all the
00617        * matching objects linked into it, so when the iterator
00618        * is destroyed, the container will be automatically
00619        * destroyed as well.
00620        */
00621       if (!(multi_container = __ao2_container_alloc(1, NULL, NULL))) {
00622          return NULL;
00623       }
00624       if (!(multi_iterator = ast_calloc(1, sizeof(*multi_iterator)))) {
00625          ao2_ref(multi_container, -1);
00626          return NULL;
00627       }
00628    }
00629 
00630    /* override the match function if necessary */
00631    if (cb_fn == NULL) { /* if NULL, match everything */
00632       if (type == WITH_DATA) {
00633          cb_withdata = cb_true_data;
00634       } else {
00635          cb_default = cb_true;
00636       }
00637    } else {
00638       /* We do this here to avoid the per object casting penalty (even though
00639          that is probably optimized away anyway). */
00640       if (type == WITH_DATA) {
00641          cb_withdata = cb_fn;
00642       } else {
00643          cb_default = cb_fn;
00644       }
00645    }
00646 
00647    /*
00648     * XXX this can be optimized.
00649     * If we have a hash function and lookup by pointer,
00650     * run the hash function. Otherwise, scan the whole container
00651     * (this only for the time being. We need to optimize this.)
00652     */
00653    if ((flags & OBJ_POINTER)) /* we know hash can handle this case */
00654       start = i = c->hash_fn(arg, flags & OBJ_POINTER) % c->n_buckets;
00655    else        /* don't know, let's scan all buckets */
00656       start = i = -1;      /* XXX this must be fixed later. */
00657 
00658    /* determine the search boundaries: i..last-1 */
00659    if (i < 0) {
00660       start = i = 0;
00661       last = c->n_buckets;
00662    } else if ((flags & OBJ_CONTINUE)) {
00663       last = c->n_buckets;
00664    } else {
00665       last = i + 1;
00666    }
00667 
00668    ao2_lock(c);   /* avoid modifications to the content */
00669 
00670    for (; i < last ; i++) {
00671       /* scan the list with prev-cur pointers */
00672       struct bucket_entry *cur;
00673 
00674       AST_LIST_TRAVERSE_SAFE_BEGIN(&c->buckets[i], cur, entry) {
00675          int match = (CMP_MATCH | CMP_STOP);
00676 
00677          if (type == WITH_DATA) {
00678             match &= cb_withdata(EXTERNAL_OBJ(cur->astobj), arg, data, flags);
00679          } else {
00680             match &= cb_default(EXTERNAL_OBJ(cur->astobj), arg, flags);
00681          }
00682 
00683          /* we found the object, performing operations according flags */
00684          if (match == 0) { /* no match, no stop, continue */
00685             continue;
00686          } else if (match == CMP_STOP) {  /* no match but stop, we are done */
00687             i = last;
00688             break;
00689          }
00690 
00691          /* we have a match (CMP_MATCH) here */
00692          if (!(flags & OBJ_NODATA)) {  /* if must return the object, record the value */
00693             /* it is important to handle this case before the unlink */
00694             ret = EXTERNAL_OBJ(cur->astobj);
00695             if (!(flags & (OBJ_UNLINK | OBJ_MULTIPLE))) {
00696                if (tag)
00697                   __ao2_ref_debug(ret, 1, tag, file, line, funcname);
00698                else
00699                   __ao2_ref(ret, 1);
00700             }
00701          }
00702 
00703          /* If we are in OBJ_MULTIPLE mode and OBJ_NODATE is off, 
00704           * link the object into the container that will hold the results.
00705           */
00706          if (ret && (multi_container != NULL)) {
00707             if (tag) {
00708                __ao2_link_debug(multi_container, ret, tag, file, line, funcname);
00709             } else {
00710                __ao2_link(multi_container, ret);
00711             }
00712             ret = NULL;
00713          }
00714 
00715          if (flags & OBJ_UNLINK) {  /* must unlink */
00716             /* we are going to modify the container, so update version */
00717             ast_atomic_fetchadd_int(&c->version, 1);
00718             AST_LIST_REMOVE_CURRENT(entry);
00719             /* update number of elements */
00720             ast_atomic_fetchadd_int(&c->elements, -1);
00721 
00722             /* - When unlinking and not returning the result, (OBJ_NODATA), the ref from the container
00723              * must be decremented.
00724              * - When unlinking with OBJ_MULTIPLE the ref from the original container
00725              * must be decremented regardless if OBJ_NODATA is used. This is because the result is
00726              * returned in a new container that already holds its own ref for the object. If the ref
00727              * from the original container is not accounted for here a memory leak occurs. */
00728             if (flags & (OBJ_NODATA | OBJ_MULTIPLE)) {
00729                if (tag)
00730                   __ao2_ref_debug(EXTERNAL_OBJ(cur->astobj), -1, tag, file, line, funcname);
00731                else
00732                   __ao2_ref(EXTERNAL_OBJ(cur->astobj), -1);
00733             }
00734             ast_free(cur); /* free the link record */
00735          }
00736 
00737          if ((match & CMP_STOP) || !(flags & OBJ_MULTIPLE)) {
00738             /* We found our only (or last) match, so force an exit from
00739                the outside loop. */
00740             i = last;
00741             break;
00742          }
00743       }
00744       AST_LIST_TRAVERSE_SAFE_END;
00745 
00746       if (ret) {
00747          break;
00748       }
00749 
00750       if (i == c->n_buckets - 1 && (flags & OBJ_POINTER) && (flags & OBJ_CONTINUE)) {
00751          /* Move to the beginning to ensure we check every bucket */
00752          i = -1;
00753          last = start;
00754       }
00755    }
00756    ao2_unlock(c);
00757 
00758    /* if multi_container was created, we are returning multiple objects */
00759    if (multi_container != NULL) {
00760       *multi_iterator = ao2_iterator_init(multi_container,
00761                       AO2_ITERATOR_DONTLOCK | AO2_ITERATOR_UNLINK | AO2_ITERATOR_MALLOCD);
00762       ao2_ref(multi_container, -1);
00763       return multi_iterator;
00764    } else {
00765       return ret;
00766    }
00767 }
00768 
00769 void *__ao2_callback_debug(struct ao2_container *c,
00770             const enum search_flags flags,
00771             ao2_callback_fn *cb_fn, void *arg,
00772             char *tag, char *file, int line, const char *funcname)
00773 {
00774    return internal_ao2_callback(c,flags, cb_fn, arg, NULL, DEFAULT, tag, file, line, funcname);
00775 }
00776 
00777 void *__ao2_callback(struct ao2_container *c, const enum search_flags flags,
00778            ao2_callback_fn *cb_fn, void *arg)
00779 {
00780    return internal_ao2_callback(c,flags, cb_fn, arg, NULL, DEFAULT, NULL, NULL, 0, NULL);
00781 }
00782 
00783 void *__ao2_callback_data_debug(struct ao2_container *c,
00784             const enum search_flags flags,
00785             ao2_callback_data_fn *cb_fn, void *arg, void *data,
00786             char *tag, char *file, int line, const char *funcname)
00787 {
00788    return internal_ao2_callback(c, flags, cb_fn, arg, data, WITH_DATA, tag, file, line, funcname);
00789 }
00790 
00791 void *__ao2_callback_data(struct ao2_container *c, const enum search_flags flags,
00792            ao2_callback_data_fn *cb_fn, void *arg, void *data)
00793 {
00794    return internal_ao2_callback(c, flags, cb_fn, arg, data, WITH_DATA, NULL, NULL, 0, NULL);
00795 }
00796 
00797 /*!
00798  * the find function just invokes the default callback with some reasonable flags.
00799  */
00800 void *__ao2_find_debug(struct ao2_container *c, void *arg, enum search_flags flags, char *tag, char *file, int line, const char *funcname)
00801 {
00802    return __ao2_callback_debug(c, flags, c->cmp_fn, arg, tag, file, line, funcname);
00803 }
00804 
00805 void *__ao2_find(struct ao2_container *c, void *arg, enum search_flags flags)
00806 {
00807    return __ao2_callback(c, flags, c->cmp_fn, arg);
00808 }
00809 
00810 /*!
00811  * initialize an iterator so we start from the first object
00812  */
00813 struct ao2_iterator ao2_iterator_init(struct ao2_container *c, int flags)
00814 {
00815    struct ao2_iterator a = {
00816       .c = c,
00817       .flags = flags
00818    };
00819 
00820    ao2_ref(c, +1);
00821    
00822    return a;
00823 }
00824 
00825 /*!
00826  * destroy an iterator
00827  */
00828 void ao2_iterator_destroy(struct ao2_iterator *i)
00829 {
00830    ao2_ref(i->c, -1);
00831    if (i->flags & AO2_ITERATOR_MALLOCD) {
00832       ast_free(i);
00833    } else {
00834       i->c = NULL;
00835    }
00836 }
00837 
00838 /*
00839  * move to the next element in the container.
00840  */
00841 static void *internal_ao2_iterator_next(struct ao2_iterator *a, struct bucket_entry **q)
00842 {
00843    int lim;
00844    struct bucket_entry *p = NULL;
00845    void *ret = NULL;
00846 
00847    *q = NULL;
00848    
00849    if (INTERNAL_OBJ(a->c) == NULL)
00850       return NULL;
00851 
00852    if (!(a->flags & AO2_ITERATOR_DONTLOCK))
00853       ao2_lock(a->c);
00854 
00855    /* optimization. If the container is unchanged and
00856     * we have a pointer, try follow it
00857     */
00858    if (a->c->version == a->c_version && (p = a->obj)) {
00859       if ((p = AST_LIST_NEXT(p, entry)))
00860          goto found;
00861       /* nope, start from the next bucket */
00862       a->bucket++;
00863       a->version = 0;
00864       a->obj = NULL;
00865    }
00866 
00867    lim = a->c->n_buckets;
00868 
00869    /* Browse the buckets array, moving to the next
00870     * buckets if we don't find the entry in the current one.
00871     * Stop when we find an element with version number greater
00872     * than the current one (we reset the version to 0 when we
00873     * switch buckets).
00874     */
00875    for (; a->bucket < lim; a->bucket++, a->version = 0) {
00876       /* scan the current bucket */
00877       AST_LIST_TRAVERSE(&a->c->buckets[a->bucket], p, entry) {
00878          if (p->version > a->version)
00879             goto found;
00880       }
00881    }
00882 
00883 found:
00884    if (p) {
00885       ret = EXTERNAL_OBJ(p->astobj);
00886       if (a->flags & AO2_ITERATOR_UNLINK) {
00887          /* we are going to modify the container, so update version */
00888          ast_atomic_fetchadd_int(&a->c->version, 1);
00889          AST_LIST_REMOVE(&a->c->buckets[a->bucket], p, entry);
00890          /* update number of elements */
00891          ast_atomic_fetchadd_int(&a->c->elements, -1);
00892          a->version = 0;
00893          a->obj = NULL;
00894          a->c_version = a->c->version;
00895          ast_free(p);
00896       } else {
00897          a->version = p->version;
00898          a->obj = p;
00899          a->c_version = a->c->version;
00900          /* inc refcount of returned object */
00901          *q = p;
00902       }
00903    }
00904 
00905    return ret;
00906 }
00907 
00908 void *__ao2_iterator_next_debug(struct ao2_iterator *a, char *tag, char *file, int line, const char *funcname)
00909 {
00910    struct bucket_entry *p;
00911    void *ret = NULL;
00912 
00913    ret = internal_ao2_iterator_next(a, &p);
00914    
00915    if (p) {
00916       /* inc refcount of returned object */
00917       __ao2_ref_debug(ret, 1, tag, file, line, funcname);
00918    }
00919 
00920    if (!(a->flags & AO2_ITERATOR_DONTLOCK))
00921       ao2_unlock(a->c);
00922 
00923    return ret;
00924 }
00925 
00926 void *__ao2_iterator_next(struct ao2_iterator *a)
00927 {
00928    struct bucket_entry *p = NULL;
00929    void *ret = NULL;
00930 
00931    ret = internal_ao2_iterator_next(a, &p);
00932    
00933    if (p) {
00934       /* inc refcount of returned object */
00935       __ao2_ref(ret, 1);
00936    }
00937 
00938    if (!(a->flags & AO2_ITERATOR_DONTLOCK))
00939       ao2_unlock(a->c);
00940 
00941    return ret;
00942 }
00943 
00944 /* callback for destroying container.
00945  * we can make it simple as we know what it does
00946  */
00947 static int cd_cb(void *obj, void *arg, int flag)
00948 {
00949    __ao2_ref(obj, -1);
00950    return 0;
00951 }
00952    
00953 static int cd_cb_debug(void *obj, void *arg, int flag)
00954 {
00955    __ao2_ref_debug(obj, -1, "deref object via container destroy",  __FILE__, __LINE__, __PRETTY_FUNCTION__);
00956    return 0;
00957 }
00958    
00959 static void container_destruct(void *_c)
00960 {
00961    struct ao2_container *c = _c;
00962    int i;
00963 
00964    __ao2_callback(c, OBJ_UNLINK, cd_cb, NULL);
00965 
00966    for (i = 0; i < c->n_buckets; i++) {
00967       struct bucket_entry *current;
00968 
00969       while ((current = AST_LIST_REMOVE_HEAD(&c->buckets[i], entry))) {
00970          ast_free(current);
00971       }
00972    }
00973 
00974 #ifdef AO2_DEBUG
00975    ast_atomic_fetchadd_int(&ao2.total_containers, -1);
00976 #endif
00977 }
00978 
00979 static void container_destruct_debug(void *_c)
00980 {
00981    struct ao2_container *c = _c;
00982    int i;
00983 
00984    __ao2_callback_debug(c, OBJ_UNLINK, cd_cb_debug, NULL, "container_destruct_debug called", __FILE__, __LINE__, __PRETTY_FUNCTION__);
00985 
00986    for (i = 0; i < c->n_buckets; i++) {
00987       struct bucket_entry *current;
00988 
00989       while ((current = AST_LIST_REMOVE_HEAD(&c->buckets[i], entry))) {
00990          ast_free(current);
00991       }
00992    }
00993 
00994 #ifdef AO2_DEBUG
00995    ast_atomic_fetchadd_int(&ao2.total_containers, -1);
00996 #endif
00997 }
00998 
00999 #ifdef AO2_DEBUG
01000 static int print_cb(void *obj, void *arg, int flag)
01001 {
01002    struct ast_cli_args *a = (struct ast_cli_args *) arg;
01003    char *s = (char *)obj;
01004 
01005    ast_cli(a->fd, "string <%s>\n", s);
01006    return 0;
01007 }
01008 
01009 /*
01010  * Print stats
01011  */
01012 static char *handle_astobj2_stats(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
01013 {
01014    switch (cmd) {
01015    case CLI_INIT:
01016       e->command = "astobj2 show stats";
01017       e->usage = "Usage: astobj2 show stats\n"
01018             "       Show astobj2 show stats\n";
01019       return NULL;
01020    case CLI_GENERATE:
01021       return NULL;
01022    }
01023    ast_cli(a->fd, "Objects    : %d\n", ao2.total_objects);
01024    ast_cli(a->fd, "Containers : %d\n", ao2.total_containers);
01025    ast_cli(a->fd, "Memory     : %d\n", ao2.total_mem);
01026    ast_cli(a->fd, "Locked     : %d\n", ao2.total_locked);
01027    ast_cli(a->fd, "Refs       : %d\n", ao2.total_refs);
01028    return CLI_SUCCESS;
01029 }
01030 
01031 /*
01032  * This is testing code for astobj
01033  */
01034 static char *handle_astobj2_test(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
01035 {
01036    struct ao2_container *c1;
01037    int i, lim;
01038    char *obj;
01039    static int prof_id = -1;
01040    struct ast_cli_args fake_args = { a->fd, 0, NULL };
01041 
01042    switch (cmd) {
01043    case CLI_INIT:
01044       e->command = "astobj2 test";
01045       e->usage = "Usage: astobj2 test <num>\n"
01046             "       Runs astobj2 test. Creates 'num' objects,\n"
01047             "       and test iterators, callbacks and may be other stuff\n";
01048       return NULL;
01049    case CLI_GENERATE:
01050       return NULL;
01051    }
01052 
01053    if (a->argc != 3) {
01054       return CLI_SHOWUSAGE;
01055    }
01056 
01057    if (prof_id == -1)
01058       prof_id = ast_add_profile("ao2_alloc", 0);
01059 
01060    ast_cli(a->fd, "argc %d argv %s %s %s\n", a->argc, a->argv[0], a->argv[1], a->argv[2]);
01061    lim = atoi(a->argv[2]);
01062    ast_cli(a->fd, "called astobj_test\n");
01063 
01064    handle_astobj2_stats(e, CLI_HANDLER, &fake_args);
01065    /*
01066     * allocate a container with no default callback, and no hash function.
01067     * No hash means everything goes in the same bucket.
01068     */
01069    c1 = ao2_t_container_alloc(100, NULL /* no callback */, NULL /* no hash */,"test");
01070    ast_cli(a->fd, "container allocated as %p\n", c1);
01071 
01072    /*
01073     * fill the container with objects.
01074     * ao2_alloc() gives us a reference which we pass to the
01075     * container when we do the insert.
01076     */
01077    for (i = 0; i < lim; i++) {
01078       ast_mark(prof_id, 1 /* start */);
01079       obj = ao2_t_alloc(80, NULL,"test");
01080       ast_mark(prof_id, 0 /* stop */);
01081       ast_cli(a->fd, "object %d allocated as %p\n", i, obj);
01082       sprintf(obj, "-- this is obj %d --", i);
01083       ao2_link(c1, obj);
01084       /* At this point, the refcount on obj is 2 due to the allocation
01085        * and linking. We can go ahead and reduce the refcount by 1
01086        * right here so that when the container is unreffed later, the
01087        * objects will be freed
01088        */
01089       ao2_t_ref(obj, -1, "test");
01090    }
01091    ast_cli(a->fd, "testing callbacks\n");
01092    ao2_t_callback(c1, 0, print_cb, a, "test callback");
01093    ast_cli(a->fd, "testing iterators, remove every second object\n");
01094    {
01095       struct ao2_iterator ai;
01096       int x = 0;
01097 
01098       ai = ao2_iterator_init(c1, 0);
01099       while ( (obj = ao2_t_iterator_next(&ai,"test")) ) {
01100          ast_cli(a->fd, "iterator on <%s>\n", obj);
01101          if (x++ & 1)
01102             ao2_t_unlink(c1, obj,"test");
01103          ao2_t_ref(obj, -1,"test");
01104       }
01105       ao2_iterator_destroy(&ai);
01106       ast_cli(a->fd, "testing iterators again\n");
01107       ai = ao2_iterator_init(c1, 0);
01108       while ( (obj = ao2_t_iterator_next(&ai,"test")) ) {
01109          ast_cli(a->fd, "iterator on <%s>\n", obj);
01110          ao2_t_ref(obj, -1,"test");
01111       }
01112       ao2_iterator_destroy(&ai);
01113    }
01114    ast_cli(a->fd, "testing callbacks again\n");
01115    ao2_t_callback(c1, 0, print_cb, a, "test callback");
01116 
01117    ast_verbose("now you should see an error message:\n");
01118    ao2_t_ref(&i, -1, "");  /* i is not a valid object so we print an error here */
01119 
01120    ast_cli(a->fd, "destroy container\n");
01121    ao2_t_ref(c1, -1, "");  /* destroy container */
01122    handle_astobj2_stats(e, CLI_HANDLER, &fake_args);
01123    return CLI_SUCCESS;
01124 }
01125 
01126 static struct ast_cli_entry cli_astobj2[] = {
01127    AST_CLI_DEFINE(handle_astobj2_stats, "Print astobj2 statistics"),
01128    AST_CLI_DEFINE(handle_astobj2_test, "Test astobj2"),
01129 };
01130 #endif /* AO2_DEBUG */
01131 
01132 int astobj2_init(void)
01133 {
01134 #ifdef AO2_DEBUG
01135    ast_cli_register_multiple(cli_astobj2, ARRAY_LEN(cli_astobj2));
01136 #endif
01137 
01138    return 0;
01139 }

Generated on 20 Aug 2013 for Asterisk - The Open Source Telephony Project by  doxygen 1.6.1