b689dbbe579ed84aa1a17380c1b0e27ddd99193e
[asterisk/asterisk.git] / main / astobj2.c
1 /*
2  * astobj2 - replacement containers for asterisk data structures.
3  *
4  * Copyright (C) 2006 Marta Carbone, Luigi Rizzo - Univ. di Pisa, Italy
5  *
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.
11  *
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.
15  */
16
17 /*
18  * Function implementing astobj2 objects.
19  */
20 #include "asterisk.h"
21
22 ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
23
24 #include "asterisk/_private.h"
25 #include "asterisk/astobj2.h"
26 #include "asterisk/utils.h"
27 #include "asterisk/cli.h"
28 #define REF_FILE "/tmp/refs"
29
30 #if defined(TEST_FRAMEWORK)
31 /* We are building with the test framework enabled so enable AO2 debug tests as well. */
32 #define AO2_DEBUG 1
33 #endif  /* defined(TEST_FRAMEWORK) */
34
35 /*!
36  * astobj2 objects are always preceded by this data structure,
37  * which contains a reference counter,
38  * option flags and a pointer to a destructor.
39  * The refcount is used to decide when it is time to
40  * invoke the destructor.
41  * The magic number is used for consistency check.
42  */
43 struct __priv_data {
44         int ref_counter;
45         ao2_destructor_fn destructor_fn;
46         /*! User data size for stats */
47         size_t data_size;
48         /*! The ao2 object option flags */
49         uint32_t options;
50         /*! magic number.  This is used to verify that a pointer passed in is a
51          *  valid astobj2 */
52         uint32_t magic;
53 };
54
55 #define AO2_MAGIC       0xa570b123
56
57 /*!
58  * What an astobj2 object looks like: fixed-size private data
59  * followed by variable-size user data.
60  */
61 struct astobj2 {
62         struct __priv_data priv_data;
63         void *user_data[0];
64 };
65
66 struct ao2_lock_priv {
67         ast_mutex_t lock;
68 };
69
70 /* AstObj2 with recursive lock. */
71 struct astobj2_lock {
72         struct ao2_lock_priv mutex;
73         struct __priv_data priv_data;
74         void *user_data[0];
75 };
76
77 struct ao2_rwlock_priv {
78         ast_rwlock_t lock;
79         /*! Count of the number of threads holding a lock on this object. -1 if it is the write lock. */
80         int num_lockers;
81 };
82
83 /* AstObj2 with RW lock. */
84 struct astobj2_rwlock {
85         struct ao2_rwlock_priv rwlock;
86         struct __priv_data priv_data;
87         void *user_data[0];
88 };
89
90 #ifdef AO2_DEBUG
91 struct ao2_stats {
92         volatile int total_objects;
93         volatile int total_mem;
94         volatile int total_containers;
95         volatile int total_refs;
96         volatile int total_locked;
97 };
98
99 static struct ao2_stats ao2;
100 #endif
101
102 #ifndef HAVE_BKTR       /* backtrace support */
103 void ao2_bt(void) {}
104 #else
105 #include <execinfo.h>    /* for backtrace */
106
107 void ao2_bt(void)
108 {
109         int c, i;
110 #define N1      20
111         void *addresses[N1];
112         char **strings;
113
114         c = backtrace(addresses, N1);
115         strings = ast_bt_get_symbols(addresses,c);
116         ast_verbose("backtrace returned: %d\n", c);
117         for(i = 0; i < c; i++) {
118                 ast_verbose("%d: %p %s\n", i, addresses[i], strings[i]);
119         }
120         free(strings);
121 }
122 #endif
123
124 #define INTERNAL_OBJ_MUTEX(user_data) \
125         ((struct astobj2_lock *) (((char *) (user_data)) - sizeof(struct astobj2_lock)))
126
127 #define INTERNAL_OBJ_RWLOCK(user_data) \
128         ((struct astobj2_rwlock *) (((char *) (user_data)) - sizeof(struct astobj2_rwlock)))
129
130 /*!
131  * \brief convert from a pointer _p to a user-defined object
132  *
133  * \return the pointer to the astobj2 structure
134  */
135 static inline struct astobj2 *INTERNAL_OBJ(void *user_data)
136 {
137         struct astobj2 *p;
138
139         if (!user_data) {
140                 ast_log(LOG_ERROR, "user_data is NULL\n");
141                 return NULL;
142         }
143
144         p = (struct astobj2 *) ((char *) user_data - sizeof(*p));
145         if (AO2_MAGIC != p->priv_data.magic) {
146                 if (p->priv_data.magic) {
147                         ast_log(LOG_ERROR, "bad magic number 0x%x for %p\n", p->priv_data.magic, p);
148                 } else {
149                         ast_log(LOG_ERROR,
150                                 "bad magic number for %p. Object is likely destroyed.\n", p);
151                 }
152                 return NULL;
153         }
154
155         return p;
156 }
157
158 enum ao2_callback_type {
159         DEFAULT,
160         WITH_DATA,
161 };
162
163 /*!
164  * \brief convert from a pointer _p to an astobj2 object
165  *
166  * \return the pointer to the user-defined portion.
167  */
168 #define EXTERNAL_OBJ(_p)        ((_p) == NULL ? NULL : (_p)->user_data)
169
170 int __ao2_lock(void *user_data, enum ao2_lock_req lock_how, const char *file, const char *func, int line, const char *var)
171 {
172         struct astobj2 *obj = INTERNAL_OBJ(user_data);
173         struct astobj2_lock *obj_mutex;
174         struct astobj2_rwlock *obj_rwlock;
175         int res = 0;
176
177         if (obj == NULL) {
178                 return -1;
179         }
180
181         switch (obj->priv_data.options & AO2_ALLOC_OPT_LOCK_MASK) {
182         case AO2_ALLOC_OPT_LOCK_MUTEX:
183                 obj_mutex = INTERNAL_OBJ_MUTEX(user_data);
184                 res = __ast_pthread_mutex_lock(file, line, func, var, &obj_mutex->mutex.lock);
185 #ifdef AO2_DEBUG
186                 if (!res) {
187                         ast_atomic_fetchadd_int(&ao2.total_locked, 1);
188                 }
189 #endif
190                 break;
191         case AO2_ALLOC_OPT_LOCK_RWLOCK:
192                 obj_rwlock = INTERNAL_OBJ_RWLOCK(user_data);
193                 switch (lock_how) {
194                 case AO2_LOCK_REQ_MUTEX:
195                 case AO2_LOCK_REQ_WRLOCK:
196                         res = __ast_rwlock_wrlock(file, line, func, &obj_rwlock->rwlock.lock, var);
197                         if (!res) {
198                                 ast_atomic_fetchadd_int(&obj_rwlock->rwlock.num_lockers, -1);
199 #ifdef AO2_DEBUG
200                                 ast_atomic_fetchadd_int(&ao2.total_locked, 1);
201 #endif
202                         }
203                         break;
204                 case AO2_LOCK_REQ_RDLOCK:
205                         res = __ast_rwlock_rdlock(file, line, func, &obj_rwlock->rwlock.lock, var);
206                         if (!res) {
207                                 ast_atomic_fetchadd_int(&obj_rwlock->rwlock.num_lockers, +1);
208 #ifdef AO2_DEBUG
209                                 ast_atomic_fetchadd_int(&ao2.total_locked, 1);
210 #endif
211                         }
212                         break;
213                 }
214                 break;
215         case AO2_ALLOC_OPT_LOCK_NOLOCK:
216                 /* The ao2 object has no lock. */
217                 break;
218         default:
219                 ast_log(__LOG_ERROR, file, line, func, "Invalid lock option on ao2 object %p\n",
220                         user_data);
221                 return -1;
222         }
223
224         return res;
225 }
226
227 int __ao2_unlock(void *user_data, const char *file, const char *func, int line, const char *var)
228 {
229         struct astobj2 *obj = INTERNAL_OBJ(user_data);
230         struct astobj2_lock *obj_mutex;
231         struct astobj2_rwlock *obj_rwlock;
232         int res = 0;
233         int current_value;
234
235         if (obj == NULL) {
236                 return -1;
237         }
238
239         switch (obj->priv_data.options & AO2_ALLOC_OPT_LOCK_MASK) {
240         case AO2_ALLOC_OPT_LOCK_MUTEX:
241                 obj_mutex = INTERNAL_OBJ_MUTEX(user_data);
242                 res = __ast_pthread_mutex_unlock(file, line, func, var, &obj_mutex->mutex.lock);
243 #ifdef AO2_DEBUG
244                 if (!res) {
245                         ast_atomic_fetchadd_int(&ao2.total_locked, -1);
246                 }
247 #endif
248                 break;
249         case AO2_ALLOC_OPT_LOCK_RWLOCK:
250                 obj_rwlock = INTERNAL_OBJ_RWLOCK(user_data);
251
252                 current_value = ast_atomic_fetchadd_int(&obj_rwlock->rwlock.num_lockers, -1) - 1;
253                 if (current_value < 0) {
254                         /* It was a WRLOCK that we are unlocking.  Fix the count. */
255                         ast_atomic_fetchadd_int(&obj_rwlock->rwlock.num_lockers, -current_value);
256                 }
257                 res = __ast_rwlock_unlock(file, line, func, &obj_rwlock->rwlock.lock, var);
258 #ifdef AO2_DEBUG
259                 if (!res) {
260                         ast_atomic_fetchadd_int(&ao2.total_locked, -1);
261                 }
262 #endif
263                 break;
264         case AO2_ALLOC_OPT_LOCK_NOLOCK:
265                 /* The ao2 object has no lock. */
266                 break;
267         default:
268                 ast_log(__LOG_ERROR, file, line, func, "Invalid lock option on ao2 object %p\n",
269                         user_data);
270                 res = -1;
271                 break;
272         }
273         return res;
274 }
275
276 int __ao2_trylock(void *user_data, enum ao2_lock_req lock_how, const char *file, const char *func, int line, const char *var)
277 {
278         struct astobj2 *obj = INTERNAL_OBJ(user_data);
279         struct astobj2_lock *obj_mutex;
280         struct astobj2_rwlock *obj_rwlock;
281         int res = 0;
282
283         if (obj == NULL) {
284                 return -1;
285         }
286
287         switch (obj->priv_data.options & AO2_ALLOC_OPT_LOCK_MASK) {
288         case AO2_ALLOC_OPT_LOCK_MUTEX:
289                 obj_mutex = INTERNAL_OBJ_MUTEX(user_data);
290                 res = __ast_pthread_mutex_trylock(file, line, func, var, &obj_mutex->mutex.lock);
291 #ifdef AO2_DEBUG
292                 if (!res) {
293                         ast_atomic_fetchadd_int(&ao2.total_locked, 1);
294                 }
295 #endif
296                 break;
297         case AO2_ALLOC_OPT_LOCK_RWLOCK:
298                 obj_rwlock = INTERNAL_OBJ_RWLOCK(user_data);
299                 switch (lock_how) {
300                 case AO2_LOCK_REQ_MUTEX:
301                 case AO2_LOCK_REQ_WRLOCK:
302                         res = __ast_rwlock_trywrlock(file, line, func, &obj_rwlock->rwlock.lock, var);
303                         if (!res) {
304                                 ast_atomic_fetchadd_int(&obj_rwlock->rwlock.num_lockers, -1);
305 #ifdef AO2_DEBUG
306                                 ast_atomic_fetchadd_int(&ao2.total_locked, 1);
307 #endif
308                         }
309                         break;
310                 case AO2_LOCK_REQ_RDLOCK:
311                         res = __ast_rwlock_tryrdlock(file, line, func, &obj_rwlock->rwlock.lock, var);
312                         if (!res) {
313                                 ast_atomic_fetchadd_int(&obj_rwlock->rwlock.num_lockers, +1);
314 #ifdef AO2_DEBUG
315                                 ast_atomic_fetchadd_int(&ao2.total_locked, 1);
316 #endif
317                         }
318                         break;
319                 }
320                 break;
321         case AO2_ALLOC_OPT_LOCK_NOLOCK:
322                 /* The ao2 object has no lock. */
323                 return 0;
324         default:
325                 ast_log(__LOG_ERROR, file, line, func, "Invalid lock option on ao2 object %p\n",
326                         user_data);
327                 return -1;
328         }
329
330
331         return res;
332 }
333
334 /*!
335  * \internal
336  * \brief Adjust an object's lock to the requested level.
337  *
338  * \param user_data An ao2 object to adjust lock level.
339  * \param lock_how What level to adjust lock.
340  * \param keep_stronger TRUE if keep original lock level if it is stronger.
341  *
342  * \pre The ao2 object is already locked.
343  *
344  * \details
345  * An ao2 object with a RWLOCK will have its lock level adjusted
346  * to the specified level if it is not already there.  An ao2
347  * object with a different type of lock is not affected.
348  *
349  * \return Original lock level.
350  */
351 static enum ao2_lock_req adjust_lock(void *user_data, enum ao2_lock_req lock_how, int keep_stronger)
352 {
353         struct astobj2 *obj = INTERNAL_OBJ(user_data);
354         struct astobj2_rwlock *obj_rwlock;
355         enum ao2_lock_req orig_lock;
356
357         switch (obj->priv_data.options & AO2_ALLOC_OPT_LOCK_MASK) {
358         case AO2_ALLOC_OPT_LOCK_RWLOCK:
359                 obj_rwlock = INTERNAL_OBJ_RWLOCK(user_data);
360                 if (obj_rwlock->rwlock.num_lockers < 0) {
361                         orig_lock = AO2_LOCK_REQ_WRLOCK;
362                 } else {
363                         orig_lock = AO2_LOCK_REQ_RDLOCK;
364                 }
365                 switch (lock_how) {
366                 case AO2_LOCK_REQ_MUTEX:
367                         lock_how = AO2_LOCK_REQ_WRLOCK;
368                         /* Fall through */
369                 case AO2_LOCK_REQ_WRLOCK:
370                         if (lock_how != orig_lock) {
371                                 /* Switch from read lock to write lock. */
372                                 ao2_unlock(user_data);
373                                 ao2_wrlock(user_data);
374                         }
375                         break;
376                 case AO2_LOCK_REQ_RDLOCK:
377                         if (!keep_stronger && lock_how != orig_lock) {
378                                 /* Switch from write lock to read lock. */
379                                 ao2_unlock(user_data);
380                                 ao2_rdlock(user_data);
381                         }
382                         break;
383                 }
384                 break;
385         default:
386                 ast_log(LOG_ERROR, "Invalid lock option on ao2 object %p\n", user_data);
387                 /* Fall through */
388         case AO2_ALLOC_OPT_LOCK_NOLOCK:
389         case AO2_ALLOC_OPT_LOCK_MUTEX:
390                 orig_lock = AO2_LOCK_REQ_MUTEX;
391                 break;
392         }
393
394         return orig_lock;
395 }
396
397 void *ao2_object_get_lockaddr(void *user_data)
398 {
399         struct astobj2 *obj = INTERNAL_OBJ(user_data);
400         struct astobj2_lock *obj_mutex;
401
402         if (obj == NULL) {
403                 return NULL;
404         }
405
406         switch (obj->priv_data.options & AO2_ALLOC_OPT_LOCK_MASK) {
407         case AO2_ALLOC_OPT_LOCK_MUTEX:
408                 obj_mutex = INTERNAL_OBJ_MUTEX(user_data);
409                 return &obj_mutex->mutex.lock;
410         default:
411                 break;
412         }
413
414         return NULL;
415 }
416
417 static int internal_ao2_ref(void *user_data, int delta, const char *file, int line, const char *func)
418 {
419         struct astobj2 *obj = INTERNAL_OBJ(user_data);
420         struct astobj2_lock *obj_mutex;
421         struct astobj2_rwlock *obj_rwlock;
422         int current_value;
423         int ret;
424
425         if (obj == NULL) {
426                 return -1;
427         }
428
429         /* if delta is 0, just return the refcount */
430         if (delta == 0) {
431                 return obj->priv_data.ref_counter;
432         }
433
434         /* we modify with an atomic operation the reference counter */
435         ret = ast_atomic_fetchadd_int(&obj->priv_data.ref_counter, delta);
436         current_value = ret + delta;
437
438 #ifdef AO2_DEBUG
439         ast_atomic_fetchadd_int(&ao2.total_refs, delta);
440 #endif
441
442         if (0 < current_value) {
443                 /* The object still lives. */
444                 return ret;
445         }
446
447         /* this case must never happen */
448         if (current_value < 0) {
449                 ast_log(__LOG_ERROR, file, line, func,
450                         "Invalid refcount %d on ao2 object %p\n", current_value, user_data);
451         }
452
453         /* last reference, destroy the object */
454         if (obj->priv_data.destructor_fn != NULL) {
455                 obj->priv_data.destructor_fn(user_data);
456         }
457
458 #ifdef AO2_DEBUG
459         ast_atomic_fetchadd_int(&ao2.total_mem, - obj->priv_data.data_size);
460         ast_atomic_fetchadd_int(&ao2.total_objects, -1);
461 #endif
462
463         switch (obj->priv_data.options & AO2_ALLOC_OPT_LOCK_MASK) {
464         case AO2_ALLOC_OPT_LOCK_MUTEX:
465                 obj_mutex = INTERNAL_OBJ_MUTEX(user_data);
466                 ast_mutex_destroy(&obj_mutex->mutex.lock);
467
468                 /*
469                  * For safety, zero-out the astobj2_lock header and also the
470                  * first word of the user-data, which we make sure is always
471                  * allocated.
472                  */
473                 memset(obj_mutex, '\0', sizeof(*obj_mutex) + sizeof(void *) );
474                 ast_free(obj_mutex);
475                 break;
476         case AO2_ALLOC_OPT_LOCK_RWLOCK:
477                 obj_rwlock = INTERNAL_OBJ_RWLOCK(user_data);
478                 ast_rwlock_destroy(&obj_rwlock->rwlock.lock);
479
480                 /*
481                  * For safety, zero-out the astobj2_rwlock header and also the
482                  * first word of the user-data, which we make sure is always
483                  * allocated.
484                  */
485                 memset(obj_rwlock, '\0', sizeof(*obj_rwlock) + sizeof(void *) );
486                 ast_free(obj_rwlock);
487                 break;
488         case AO2_ALLOC_OPT_LOCK_NOLOCK:
489                 /*
490                  * For safety, zero-out the astobj2 header and also the first
491                  * word of the user-data, which we make sure is always
492                  * allocated.
493                  */
494                 memset(obj, '\0', sizeof(*obj) + sizeof(void *) );
495                 ast_free(obj);
496                 break;
497         default:
498                 ast_log(__LOG_ERROR, file, line, func,
499                         "Invalid lock option on ao2 object %p\n", user_data);
500                 break;
501         }
502
503         return ret;
504 }
505
506 int __ao2_ref_debug(void *user_data, int delta, const char *tag, const char *file, int line, const char *func)
507 {
508         struct astobj2 *obj = INTERNAL_OBJ(user_data);
509
510         if (obj == NULL)
511                 return -1;
512
513         if (delta != 0) {
514                 FILE *refo = fopen(REF_FILE, "a");
515                 if (refo) {
516                         fprintf(refo, "%p %s%d   %s:%d:%s (%s) [@%d]\n", user_data, (delta < 0 ? "" : "+"),
517                                 delta, file, line, func, tag, obj->priv_data.ref_counter);
518                         fclose(refo);
519                 }
520         }
521         if (obj->priv_data.ref_counter + delta == 0 && obj->priv_data.destructor_fn != NULL) { /* this isn't protected with lock; just for o/p */
522                 FILE *refo = fopen(REF_FILE, "a");
523                 if (refo) {
524                         fprintf(refo, "%p **call destructor** %s:%d:%s (%s)\n", user_data, file, line, func, tag);
525                         fclose(refo);
526                 }
527         }
528         return internal_ao2_ref(user_data, delta, file, line, func);
529 }
530
531 int __ao2_ref(void *user_data, int delta)
532 {
533         return internal_ao2_ref(user_data, delta, __FILE__, __LINE__, __FUNCTION__);
534 }
535
536 static void *internal_ao2_alloc(size_t data_size, ao2_destructor_fn destructor_fn, unsigned int options, const char *file, int line, const char *func)
537 {
538         /* allocation */
539         struct astobj2 *obj;
540         struct astobj2_lock *obj_mutex;
541         struct astobj2_rwlock *obj_rwlock;
542
543         if (data_size < sizeof(void *)) {
544                 /*
545                  * We always alloc at least the size of a void *,
546                  * for debugging purposes.
547                  */
548                 data_size = sizeof(void *);
549         }
550
551         switch (options & AO2_ALLOC_OPT_LOCK_MASK) {
552         case AO2_ALLOC_OPT_LOCK_MUTEX:
553 #if defined(__AST_DEBUG_MALLOC)
554                 obj_mutex = __ast_calloc(1, sizeof(*obj_mutex) + data_size, file, line, func);
555 #else
556                 obj_mutex = ast_calloc(1, sizeof(*obj_mutex) + data_size);
557 #endif
558                 if (obj_mutex == NULL) {
559                         return NULL;
560                 }
561
562                 ast_mutex_init(&obj_mutex->mutex.lock);
563                 obj = (struct astobj2 *) &obj_mutex->priv_data;
564                 break;
565         case AO2_ALLOC_OPT_LOCK_RWLOCK:
566 #if defined(__AST_DEBUG_MALLOC)
567                 obj_rwlock = __ast_calloc(1, sizeof(*obj_rwlock) + data_size, file, line, func);
568 #else
569                 obj_rwlock = ast_calloc(1, sizeof(*obj_rwlock) + data_size);
570 #endif
571                 if (obj_rwlock == NULL) {
572                         return NULL;
573                 }
574
575                 ast_rwlock_init(&obj_rwlock->rwlock.lock);
576                 obj = (struct astobj2 *) &obj_rwlock->priv_data;
577                 break;
578         case AO2_ALLOC_OPT_LOCK_NOLOCK:
579 #if defined(__AST_DEBUG_MALLOC)
580                 obj = __ast_calloc(1, sizeof(*obj) + data_size, file, line, func);
581 #else
582                 obj = ast_calloc(1, sizeof(*obj) + data_size);
583 #endif
584                 if (obj == NULL) {
585                         return NULL;
586                 }
587                 break;
588         default:
589                 /* Invalid option value. */
590                 ast_log(__LOG_DEBUG, file, line, func, "Invalid lock option requested\n");
591                 return NULL;
592         }
593
594         /* Initialize common ao2 values. */
595         obj->priv_data.ref_counter = 1;
596         obj->priv_data.destructor_fn = destructor_fn;   /* can be NULL */
597         obj->priv_data.data_size = data_size;
598         obj->priv_data.options = options;
599         obj->priv_data.magic = AO2_MAGIC;
600
601 #ifdef AO2_DEBUG
602         ast_atomic_fetchadd_int(&ao2.total_objects, 1);
603         ast_atomic_fetchadd_int(&ao2.total_mem, data_size);
604         ast_atomic_fetchadd_int(&ao2.total_refs, 1);
605 #endif
606
607         /* return a pointer to the user data */
608         return EXTERNAL_OBJ(obj);
609 }
610
611 void *__ao2_alloc_debug(size_t data_size, ao2_destructor_fn destructor_fn, unsigned int options, const char *tag,
612         const char *file, int line, const char *func, int ref_debug)
613 {
614         /* allocation */
615         void *obj;
616         FILE *refo;
617
618         if ((obj = internal_ao2_alloc(data_size, destructor_fn, options, file, line, func)) == NULL) {
619                 return NULL;
620         }
621
622         if (ref_debug && (refo = fopen(REF_FILE, "a"))) {
623                 fprintf(refo, "%p =1   %s:%d:%s (%s)\n", obj, file, line, func, tag);
624                 fclose(refo);
625         }
626
627         /* return a pointer to the user data */
628         return obj;
629 }
630
631 void *__ao2_alloc(size_t data_size, ao2_destructor_fn destructor_fn, unsigned int options)
632 {
633         return internal_ao2_alloc(data_size, destructor_fn, options, __FILE__, __LINE__, __FUNCTION__);
634 }
635
636
637 void __ao2_global_obj_release(struct ao2_global_obj *array, const char *tag, const char *file, int line, const char *func, const char *name)
638 {
639         unsigned int idx;
640
641         if (!array) {
642                 /* For sanity */
643                 return;
644         }
645         if (__ast_rwlock_wrlock(file, line, func, &array->lock, name)) {
646                 /* Could not get the write lock. */
647                 return;
648         }
649
650         /* Release all contained ao2 objects. */
651         idx = array->num_elements;
652         while (idx--) {
653                 if (array->obj[idx]) {
654                         __ao2_ref_debug(array->obj[idx], -1, tag, file, line, func);
655                         array->obj[idx] = NULL;
656                 }
657         }
658
659         __ast_rwlock_unlock(file, line, func, &array->lock, name);
660 }
661
662 void *__ao2_global_obj_replace(struct ao2_global_obj *array, unsigned int idx, void *obj, const char *tag, const char *file, int line, const char *func, const char *name)
663 {
664         void *obj_old;
665
666         if (!array || array->num_elements <= idx) {
667                 /* For sanity */
668                 return NULL;
669         }
670         if (__ast_rwlock_wrlock(file, line, func, &array->lock, name)) {
671                 /* Could not get the write lock. */
672                 return NULL;
673         }
674
675         if (obj) {
676                 __ao2_ref_debug(obj, +1, tag, file, line, func);
677         }
678         obj_old = array->obj[idx];
679         array->obj[idx] = obj;
680
681         __ast_rwlock_unlock(file, line, func, &array->lock, name);
682
683         return obj_old;
684 }
685
686 void *__ao2_global_obj_ref(struct ao2_global_obj *array, unsigned int idx, const char *tag, const char *file, int line, const char *func, const char *name)
687 {
688         void *obj;
689
690         if (!array || array->num_elements <= idx) {
691                 /* For sanity */
692                 return NULL;
693         }
694         if (__ast_rwlock_rdlock(file, line, func, &array->lock, name)) {
695                 /* Could not get the read lock. */
696                 return NULL;
697         }
698
699         obj = array->obj[idx];
700         if (obj) {
701                 __ao2_ref_debug(obj, +1, tag, file, line, func);
702         }
703
704         __ast_rwlock_unlock(file, line, func, &array->lock, name);
705
706         return obj;
707 }
708
709
710 /* internal callback to destroy a container. */
711 static void container_destruct(void *c);
712
713 /* internal callback to destroy a container. */
714 static void container_destruct_debug(void *c);
715
716 /*!
717  * A structure to create a linked list of entries,
718  * used within a bucket.
719  * XXX \todo this should be private to the container code
720  */
721 struct bucket_entry {
722         AST_LIST_ENTRY(bucket_entry) entry;
723         int version;
724         struct astobj2 *astobj;/* pointer to internal data */
725 };
726
727 /* each bucket in the container is a tailq. */
728 AST_LIST_HEAD_NOLOCK(bucket, bucket_entry);
729
730 /*!
731  * A container; stores the hash and callback functions, information on
732  * the size, the hash bucket heads, and a version number, starting at 0
733  * (for a newly created, empty container)
734  * and incremented every time an object is inserted or deleted.
735  * The assumption is that an object is never moved in a container,
736  * but removed and readded with the new number.
737  * The version number is especially useful when implementing iterators.
738  * In fact, we can associate a unique, monotonically increasing number to
739  * each object, which means that, within an iterator, we can store the
740  * version number of the current object, and easily look for the next one,
741  * which is the next one in the list with a higher number.
742  * Since all objects have a version >0, we can use 0 as a marker for
743  * 'we need the first object in the bucket'.
744  *
745  * \todo Linking and unlink objects is typically expensive, as it
746  * involves a malloc() of a small object which is very inefficient.
747  * To optimize this, we allocate larger arrays of bucket_entry's
748  * when we run out of them, and then manage our own freelist.
749  * This will be more efficient as we can do the freelist management while
750  * we hold the lock (that we need anyways).
751  */
752 struct ao2_container {
753         ao2_hash_fn *hash_fn;
754         ao2_callback_fn *cmp_fn;
755         int n_buckets;
756         /*! Number of elements in the container */
757         int elements;
758         /*! described above */
759         int version;
760         /*! variable size */
761         struct bucket buckets[0];
762 };
763
764 /*!
765  * \brief always zero hash function
766  *
767  * it is convenient to have a hash function that always returns 0.
768  * This is basically used when we want to have a container that is
769  * a simple linked list.
770  *
771  * \returns 0
772  */
773 static int hash_zero(const void *user_obj, const int flags)
774 {
775         return 0;
776 }
777
778 /*
779  * A container is just an object, after all!
780  */
781 static struct ao2_container *internal_ao2_container_alloc(struct ao2_container *c,
782         unsigned int n_buckets, ao2_hash_fn *hash_fn, ao2_callback_fn *cmp_fn)
783 {
784         /* XXX maybe consistency check on arguments ? */
785         /* compute the container size */
786
787         if (!c) {
788                 return NULL;
789         }
790
791         c->version = 1; /* 0 is a reserved value here */
792         c->n_buckets = hash_fn ? n_buckets : 1;
793         c->hash_fn = hash_fn ? hash_fn : hash_zero;
794         c->cmp_fn = cmp_fn;
795
796 #ifdef AO2_DEBUG
797         ast_atomic_fetchadd_int(&ao2.total_containers, 1);
798 #endif
799
800         return c;
801 }
802
803 struct ao2_container *__ao2_container_alloc_debug(unsigned int options,
804         unsigned int n_buckets, ao2_hash_fn *hash_fn, ao2_callback_fn *cmp_fn,
805         const char *tag, const char *file, int line, const char *func, int ref_debug)
806 {
807         /* XXX maybe consistency check on arguments ? */
808         /* compute the container size */
809         unsigned int num_buckets = hash_fn ? n_buckets : 1;
810         size_t container_size = sizeof(struct ao2_container) + num_buckets * sizeof(struct bucket);
811         struct ao2_container *c = __ao2_alloc_debug(container_size, container_destruct_debug, options, tag, file, line, func, ref_debug);
812
813         return internal_ao2_container_alloc(c, num_buckets, hash_fn, cmp_fn);
814 }
815
816 struct ao2_container *__ao2_container_alloc(unsigned int options,
817         unsigned int n_buckets, ao2_hash_fn *hash_fn, ao2_callback_fn *cmp_fn)
818 {
819         /* XXX maybe consistency check on arguments ? */
820         /* compute the container size */
821         const unsigned int num_buckets = hash_fn ? n_buckets : 1;
822         size_t container_size = sizeof(struct ao2_container) + num_buckets * sizeof(struct bucket);
823         struct ao2_container *c = __ao2_alloc(container_size, container_destruct, options);
824
825         return internal_ao2_container_alloc(c, num_buckets, hash_fn, cmp_fn);
826 }
827
828 /*!
829  * return the number of elements in the container
830  */
831 int ao2_container_count(struct ao2_container *c)
832 {
833         return c->elements;
834 }
835
836 /*
837  * link an object to a container
838  */
839 static struct bucket_entry *internal_ao2_link(struct ao2_container *c, void *user_data, int flags, const char *tag, const char *file, int line, const char *func)
840 {
841         int i;
842         enum ao2_lock_req orig_lock;
843         /* create a new list entry */
844         struct bucket_entry *p;
845         struct astobj2 *obj = INTERNAL_OBJ(user_data);
846
847         if (obj == NULL) {
848                 return NULL;
849         }
850
851         if (INTERNAL_OBJ(c) == NULL) {
852                 return NULL;
853         }
854
855         p = ast_calloc(1, sizeof(*p));
856         if (!p) {
857                 return NULL;
858         }
859
860         i = abs(c->hash_fn(user_data, OBJ_POINTER));
861
862         if (flags & OBJ_NOLOCK) {
863                 orig_lock = adjust_lock(c, AO2_LOCK_REQ_WRLOCK, 1);
864         } else {
865                 ao2_wrlock(c);
866                 orig_lock = AO2_LOCK_REQ_MUTEX;
867         }
868
869         i %= c->n_buckets;
870         p->astobj = obj;
871         p->version = ast_atomic_fetchadd_int(&c->version, 1);
872         AST_LIST_INSERT_TAIL(&c->buckets[i], p, entry);
873         ast_atomic_fetchadd_int(&c->elements, 1);
874
875         if (tag) {
876                 __ao2_ref_debug(user_data, +1, tag, file, line, func);
877         } else {
878                 __ao2_ref(user_data, +1);
879         }
880
881         if (flags & OBJ_NOLOCK) {
882                 adjust_lock(c, orig_lock, 0);
883         } else {
884                 ao2_unlock(c);
885         }
886
887         return p;
888 }
889
890 void *__ao2_link_debug(struct ao2_container *c, void *obj_new, int flags, const char *tag, const char *file, int line, const char *func)
891 {
892         return internal_ao2_link(c, obj_new, flags, tag, file, line, func);
893 }
894
895 void *__ao2_link(struct ao2_container *c, void *obj_new, int flags)
896 {
897         return internal_ao2_link(c, obj_new, flags, NULL, __FILE__, __LINE__, __PRETTY_FUNCTION__);
898 }
899
900 /*!
901  * \brief another convenience function is a callback that matches on address
902  */
903 int ao2_match_by_addr(void *user_data, void *arg, int flags)
904 {
905         return (user_data == arg) ? (CMP_MATCH | CMP_STOP) : 0;
906 }
907
908 /*
909  * Unlink an object from the container
910  * and destroy the associated * bucket_entry structure.
911  */
912 void *__ao2_unlink_debug(struct ao2_container *c, void *user_data, int flags,
913         const char *tag, const char *file, int line, const char *func)
914 {
915         if (INTERNAL_OBJ(user_data) == NULL) {  /* safety check on the argument */
916                 return NULL;
917         }
918
919         flags |= (OBJ_UNLINK | OBJ_POINTER | OBJ_NODATA);
920         __ao2_callback_debug(c, flags, ao2_match_by_addr, user_data, tag, file, line, func);
921
922         return NULL;
923 }
924
925 void *__ao2_unlink(struct ao2_container *c, void *user_data, int flags)
926 {
927         if (INTERNAL_OBJ(user_data) == NULL) {  /* safety check on the argument */
928                 return NULL;
929         }
930
931         flags |= (OBJ_UNLINK | OBJ_POINTER | OBJ_NODATA);
932         __ao2_callback(c, flags, ao2_match_by_addr, user_data);
933
934         return NULL;
935 }
936
937 /*!
938  * \brief special callback that matches all
939  */
940 static int cb_true(void *user_data, void *arg, int flags)
941 {
942         return CMP_MATCH;
943 }
944
945 /*!
946  * \brief similar to cb_true, but is an ao2_callback_data_fn instead
947  */
948 static int cb_true_data(void *user_data, void *arg, void *data, int flags)
949 {
950         return CMP_MATCH;
951 }
952
953 /*!
954  * Browse the container using different stategies accoding the flags.
955  * \return Is a pointer to an object or to a list of object if OBJ_MULTIPLE is
956  * specified.
957  * Luckily, for debug purposes, the added args (tag, file, line, func)
958  * aren't an excessive load to the system, as the callback should not be
959  * called as often as, say, the ao2_ref func is called.
960  */
961 static void *internal_ao2_callback(struct ao2_container *c, enum search_flags flags,
962         void *cb_fn, void *arg, void *data, enum ao2_callback_type type, const char *tag,
963         const char *file, int line, const char *func)
964 {
965         int i, start, last;     /* search boundaries */
966         enum ao2_lock_req orig_lock;
967         void *ret = NULL;
968         ao2_callback_fn *cb_default = NULL;
969         ao2_callback_data_fn *cb_withdata = NULL;
970         struct ao2_container *multi_container = NULL;
971         struct ao2_iterator *multi_iterator = NULL;
972
973         if (INTERNAL_OBJ(c) == NULL) {  /* safety check on the argument */
974                 return NULL;
975         }
976
977         /*
978          * This logic is used so we can support OBJ_MULTIPLE with OBJ_NODATA
979          * turned off.  This if statement checks for the special condition
980          * where multiple items may need to be returned.
981          */
982         if ((flags & (OBJ_MULTIPLE | OBJ_NODATA)) == OBJ_MULTIPLE) {
983                 /* we need to return an ao2_iterator with the results,
984                  * as there could be more than one. the iterator will
985                  * hold the only reference to a container that has all the
986                  * matching objects linked into it, so when the iterator
987                  * is destroyed, the container will be automatically
988                  * destroyed as well.
989                  */
990                 multi_container = __ao2_container_alloc(AO2_ALLOC_OPT_LOCK_NOLOCK, 1, NULL, NULL);
991                 if (!multi_container) {
992                         return NULL;
993                 }
994                 if (!(multi_iterator = ast_calloc(1, sizeof(*multi_iterator)))) {
995                         ao2_ref(multi_container, -1);
996                         return NULL;
997                 }
998         }
999
1000         /* override the match function if necessary */
1001         if (cb_fn == NULL) { /* if NULL, match everything */
1002                 if (type == WITH_DATA) {
1003                         cb_withdata = cb_true_data;
1004                 } else {
1005                         cb_default = cb_true;
1006                 }
1007         } else {
1008                 /* We do this here to avoid the per object casting penalty (even though
1009                    that is probably optimized away anyway). */
1010                 if (type == WITH_DATA) {
1011                         cb_withdata = cb_fn;
1012                 } else {
1013                         cb_default = cb_fn;
1014                 }
1015         }
1016
1017         /*
1018          * XXX this can be optimized.
1019          * If we have a hash function and lookup by pointer,
1020          * run the hash function. Otherwise, scan the whole container
1021          * (this only for the time being. We need to optimize this.)
1022          */
1023         if ((flags & (OBJ_POINTER | OBJ_KEY))) {
1024                 /* we know hash can handle this case */
1025                 start = i = c->hash_fn(arg, flags & (OBJ_POINTER | OBJ_KEY)) % c->n_buckets;
1026         } else {
1027                 /* don't know, let's scan all buckets */
1028                 start = i = -1;         /* XXX this must be fixed later. */
1029         }
1030
1031         /* determine the search boundaries: i..last-1 */
1032         if (i < 0) {
1033                 start = i = 0;
1034                 last = c->n_buckets;
1035         } else if ((flags & OBJ_CONTINUE)) {
1036                 last = c->n_buckets;
1037         } else {
1038                 last = i + 1;
1039         }
1040
1041         /* avoid modifications to the content */
1042         if (flags & OBJ_NOLOCK) {
1043                 if (flags & OBJ_UNLINK) {
1044                         orig_lock = adjust_lock(c, AO2_LOCK_REQ_WRLOCK, 1);
1045                 } else {
1046                         orig_lock = adjust_lock(c, AO2_LOCK_REQ_RDLOCK, 1);
1047                 }
1048         } else {
1049                 orig_lock = AO2_LOCK_REQ_MUTEX;
1050                 if (flags & OBJ_UNLINK) {
1051                         ao2_wrlock(c);
1052                 } else {
1053                         ao2_rdlock(c);
1054                 }
1055         }
1056
1057         for (; i < last ; i++) {
1058                 /* scan the list with prev-cur pointers */
1059                 struct bucket_entry *cur;
1060
1061                 AST_LIST_TRAVERSE_SAFE_BEGIN(&c->buckets[i], cur, entry) {
1062                         int match = (CMP_MATCH | CMP_STOP);
1063
1064                         if (type == WITH_DATA) {
1065                                 match &= cb_withdata(EXTERNAL_OBJ(cur->astobj), arg, data, flags);
1066                         } else {
1067                                 match &= cb_default(EXTERNAL_OBJ(cur->astobj), arg, flags);
1068                         }
1069
1070                         /* we found the object, performing operations according flags */
1071                         if (match == 0) {       /* no match, no stop, continue */
1072                                 continue;
1073                         } else if (match == CMP_STOP) { /* no match but stop, we are done */
1074                                 i = last;
1075                                 break;
1076                         }
1077
1078                         /* we have a match (CMP_MATCH) here */
1079                         if (!(flags & OBJ_NODATA)) {    /* if must return the object, record the value */
1080                                 /* it is important to handle this case before the unlink */
1081                                 ret = EXTERNAL_OBJ(cur->astobj);
1082                                 if (!(flags & (OBJ_UNLINK | OBJ_MULTIPLE))) {
1083                                         if (tag) {
1084                                                 __ao2_ref_debug(ret, 1, tag, file, line, func);
1085                                         } else {
1086                                                 __ao2_ref(ret, 1);
1087                                         }
1088                                 }
1089                         }
1090
1091                         /* If we are in OBJ_MULTIPLE mode and OBJ_NODATA is off,
1092                          * link the object into the container that will hold the results.
1093                          */
1094                         if (ret && (multi_container != NULL)) {
1095                                 if (tag) {
1096                                         __ao2_link_debug(multi_container, ret, flags, tag, file, line, func);
1097                                 } else {
1098                                         __ao2_link(multi_container, ret, flags);
1099                                 }
1100                                 ret = NULL;
1101                         }
1102
1103                         if (flags & OBJ_UNLINK) {       /* must unlink */
1104                                 /* we are going to modify the container, so update version */
1105                                 ast_atomic_fetchadd_int(&c->version, 1);
1106                                 AST_LIST_REMOVE_CURRENT(entry);
1107                                 /* update number of elements */
1108                                 ast_atomic_fetchadd_int(&c->elements, -1);
1109
1110                                 /* - When unlinking and not returning the result, (OBJ_NODATA), the ref from the container
1111                                  * must be decremented.
1112                                  * - When unlinking with OBJ_MULTIPLE the ref from the original container
1113                                  * must be decremented regardless if OBJ_NODATA is used. This is because the result is
1114                                  * returned in a new container that already holds its own ref for the object. If the ref
1115                                  * from the original container is not accounted for here a memory leak occurs. */
1116                                 if (flags & (OBJ_NODATA | OBJ_MULTIPLE)) {
1117                                         if (tag)
1118                                                 __ao2_ref_debug(EXTERNAL_OBJ(cur->astobj), -1, tag, file, line, func);
1119                                         else
1120                                                 __ao2_ref(EXTERNAL_OBJ(cur->astobj), -1);
1121                                 }
1122                                 ast_free(cur);  /* free the link record */
1123                         }
1124
1125                         if ((match & CMP_STOP) || !(flags & OBJ_MULTIPLE)) {
1126                                 /* We found our only (or last) match, so force an exit from
1127                                    the outside loop. */
1128                                 i = last;
1129                                 break;
1130                         }
1131                 }
1132                 AST_LIST_TRAVERSE_SAFE_END;
1133
1134                 if (ret) {
1135                         break;
1136                 }
1137
1138                 if (i == c->n_buckets - 1 && (flags & OBJ_POINTER) && (flags & OBJ_CONTINUE)) {
1139                         /* Move to the beginning to ensure we check every bucket */
1140                         i = -1;
1141                         last = start;
1142                 }
1143         }
1144
1145         if (flags & OBJ_NOLOCK) {
1146                 adjust_lock(c, orig_lock, 0);
1147         } else {
1148                 ao2_unlock(c);
1149         }
1150
1151         /* if multi_container was created, we are returning multiple objects */
1152         if (multi_container != NULL) {
1153                 *multi_iterator = ao2_iterator_init(multi_container,
1154                         AO2_ITERATOR_UNLINK | AO2_ITERATOR_MALLOCD);
1155                 ao2_ref(multi_container, -1);
1156                 return multi_iterator;
1157         } else {
1158                 return ret;
1159         }
1160 }
1161
1162 void *__ao2_callback_debug(struct ao2_container *c, enum search_flags flags,
1163         ao2_callback_fn *cb_fn, void *arg, const char *tag, const char *file, int line,
1164         const char *func)
1165 {
1166         return internal_ao2_callback(c,flags, cb_fn, arg, NULL, DEFAULT, tag, file, line, func);
1167 }
1168
1169 void *__ao2_callback(struct ao2_container *c, enum search_flags flags,
1170         ao2_callback_fn *cb_fn, void *arg)
1171 {
1172         return internal_ao2_callback(c,flags, cb_fn, arg, NULL, DEFAULT, NULL, NULL, 0, NULL);
1173 }
1174
1175 void *__ao2_callback_data_debug(struct ao2_container *c, enum search_flags flags,
1176         ao2_callback_data_fn *cb_fn, void *arg, void *data, const char *tag, const char *file,
1177         int line, const char *func)
1178 {
1179         return internal_ao2_callback(c, flags, cb_fn, arg, data, WITH_DATA, tag, file, line, func);
1180 }
1181
1182 void *__ao2_callback_data(struct ao2_container *c, enum search_flags flags,
1183         ao2_callback_data_fn *cb_fn, void *arg, void *data)
1184 {
1185         return internal_ao2_callback(c, flags, cb_fn, arg, data, WITH_DATA, NULL, NULL, 0, NULL);
1186 }
1187
1188 /*!
1189  * the find function just invokes the default callback with some reasonable flags.
1190  */
1191 void *__ao2_find_debug(struct ao2_container *c, const void *arg, enum search_flags flags,
1192         const char *tag, const char *file, int line, const char *func)
1193 {
1194         void *arged = (void *) arg;/* Done to avoid compiler const warning */
1195
1196         return __ao2_callback_debug(c, flags, c->cmp_fn, arged, tag, file, line, func);
1197 }
1198
1199 void *__ao2_find(struct ao2_container *c, const void *arg, enum search_flags flags)
1200 {
1201         void *arged = (void *) arg;/* Done to avoid compiler const warning */
1202
1203         return __ao2_callback(c, flags, c->cmp_fn, arged);
1204 }
1205
1206 /*!
1207  * initialize an iterator so we start from the first object
1208  */
1209 struct ao2_iterator ao2_iterator_init(struct ao2_container *c, int flags)
1210 {
1211         struct ao2_iterator a = {
1212                 .c = c,
1213                 .flags = flags
1214         };
1215
1216         ao2_ref(c, +1);
1217
1218         return a;
1219 }
1220
1221 /*!
1222  * destroy an iterator
1223  */
1224 void ao2_iterator_destroy(struct ao2_iterator *iter)
1225 {
1226         ao2_ref(iter->c, -1);
1227         if (iter->flags & AO2_ITERATOR_MALLOCD) {
1228                 ast_free(iter);
1229         } else {
1230                 iter->c = NULL;
1231         }
1232 }
1233
1234 /*
1235  * move to the next element in the container.
1236  */
1237 static void *internal_ao2_iterator_next(struct ao2_iterator *iter, const char *tag, const char *file, int line, const char *func)
1238 {
1239         int lim;
1240         enum ao2_lock_req orig_lock;
1241         struct bucket_entry *p = NULL;
1242         void *ret;
1243
1244         if (INTERNAL_OBJ(iter->c) == NULL) {
1245                 return NULL;
1246         }
1247
1248         if (iter->flags & AO2_ITERATOR_DONTLOCK) {
1249                 if (iter->flags & AO2_ITERATOR_UNLINK) {
1250                         orig_lock = adjust_lock(iter->c, AO2_LOCK_REQ_WRLOCK, 1);
1251                 } else {
1252                         orig_lock = adjust_lock(iter->c, AO2_LOCK_REQ_RDLOCK, 1);
1253                 }
1254         } else {
1255                 orig_lock = AO2_LOCK_REQ_MUTEX;
1256                 if (iter->flags & AO2_ITERATOR_UNLINK) {
1257                         ao2_wrlock(iter->c);
1258                 } else {
1259                         ao2_rdlock(iter->c);
1260                 }
1261         }
1262
1263         /* optimization. If the container is unchanged and
1264          * we have a pointer, try follow it
1265          */
1266         if (iter->c->version == iter->c_version && (p = iter->obj)) {
1267                 if ((p = AST_LIST_NEXT(p, entry))) {
1268                         goto found;
1269                 }
1270                 /* nope, start from the next bucket */
1271                 iter->bucket++;
1272                 iter->version = 0;
1273                 iter->obj = NULL;
1274         }
1275
1276         lim = iter->c->n_buckets;
1277
1278         /* Browse the buckets array, moving to the next
1279          * buckets if we don't find the entry in the current one.
1280          * Stop when we find an element with version number greater
1281          * than the current one (we reset the version to 0 when we
1282          * switch buckets).
1283          */
1284         for (; iter->bucket < lim; iter->bucket++, iter->version = 0) {
1285                 /* scan the current bucket */
1286                 AST_LIST_TRAVERSE(&iter->c->buckets[iter->bucket], p, entry) {
1287                         if (p->version > iter->version) {
1288                                 goto found;
1289                         }
1290                 }
1291         }
1292
1293 found:
1294         if (p) {
1295                 ret = EXTERNAL_OBJ(p->astobj);
1296                 if (iter->flags & AO2_ITERATOR_UNLINK) {
1297                         /* we are going to modify the container, so update version */
1298                         ast_atomic_fetchadd_int(&iter->c->version, 1);
1299                         AST_LIST_REMOVE(&iter->c->buckets[iter->bucket], p, entry);
1300                         /* update number of elements */
1301                         ast_atomic_fetchadd_int(&iter->c->elements, -1);
1302                         iter->version = 0;
1303                         iter->obj = NULL;
1304                         iter->c_version = iter->c->version;
1305                         ast_free(p);
1306                 } else {
1307                         iter->version = p->version;
1308                         iter->obj = p;
1309                         iter->c_version = iter->c->version;
1310
1311                         /* inc refcount of returned object */
1312                         if (tag) {
1313                                 __ao2_ref_debug(ret, 1, tag, file, line, func);
1314                         } else {
1315                                 __ao2_ref(ret, 1);
1316                         }
1317                 }
1318         } else {
1319                 ret = NULL;
1320         }
1321
1322         if (iter->flags & AO2_ITERATOR_DONTLOCK) {
1323                 adjust_lock(iter->c, orig_lock, 0);
1324         } else {
1325                 ao2_unlock(iter->c);
1326         }
1327
1328         return ret;
1329 }
1330
1331 void *__ao2_iterator_next_debug(struct ao2_iterator *iter, const char *tag, const char *file, int line, const char *func)
1332 {
1333         return internal_ao2_iterator_next(iter, tag, file, line, func);
1334 }
1335
1336 void *__ao2_iterator_next(struct ao2_iterator *iter)
1337 {
1338         return internal_ao2_iterator_next(iter, NULL, __FILE__, __LINE__, __PRETTY_FUNCTION__);
1339 }
1340
1341 /* callback for destroying container.
1342  * we can make it simple as we know what it does
1343  */
1344 static int cd_cb(void *obj, void *arg, int flag)
1345 {
1346         __ao2_ref(obj, -1);
1347         return 0;
1348 }
1349
1350 static int cd_cb_debug(void *obj, void *arg, int flag)
1351 {
1352         __ao2_ref_debug(obj, -1, "deref object via container destroy",  __FILE__, __LINE__, __PRETTY_FUNCTION__);
1353         return 0;
1354 }
1355
1356 static void container_destruct(void *_c)
1357 {
1358         struct ao2_container *c = _c;
1359         int i;
1360
1361         __ao2_callback(c, OBJ_UNLINK, cd_cb, NULL);
1362
1363         for (i = 0; i < c->n_buckets; i++) {
1364                 struct bucket_entry *current;
1365
1366                 while ((current = AST_LIST_REMOVE_HEAD(&c->buckets[i], entry))) {
1367                         ast_free(current);
1368                 }
1369         }
1370
1371 #ifdef AO2_DEBUG
1372         ast_atomic_fetchadd_int(&ao2.total_containers, -1);
1373 #endif
1374 }
1375
1376 static void container_destruct_debug(void *_c)
1377 {
1378         struct ao2_container *c = _c;
1379         int i;
1380
1381         __ao2_callback_debug(c, OBJ_UNLINK, cd_cb_debug, NULL, "container_destruct_debug called", __FILE__, __LINE__, __PRETTY_FUNCTION__);
1382
1383         for (i = 0; i < c->n_buckets; i++) {
1384                 struct bucket_entry *current;
1385
1386                 while ((current = AST_LIST_REMOVE_HEAD(&c->buckets[i], entry))) {
1387                         ast_free(current);
1388                 }
1389         }
1390
1391 #ifdef AO2_DEBUG
1392         ast_atomic_fetchadd_int(&ao2.total_containers, -1);
1393 #endif
1394 }
1395
1396 /*!
1397  * \internal
1398  * \brief Put obj into the arg container.
1399  * \since 11.0
1400  *
1401  * \param obj  pointer to the (user-defined part) of an object.
1402  * \param arg callback argument from ao2_callback()
1403  * \param flags flags from ao2_callback()
1404  *
1405  * \retval 0 on success.
1406  * \retval CMP_STOP|CMP_MATCH on error.
1407  */
1408 static int dup_obj_cb(void *obj, void *arg, int flags)
1409 {
1410         struct ao2_container *dest = arg;
1411
1412         return __ao2_link(dest, obj, OBJ_NOLOCK) ? 0 : (CMP_MATCH | CMP_STOP);
1413 }
1414
1415 int ao2_container_dup(struct ao2_container *dest, struct ao2_container *src, enum search_flags flags)
1416 {
1417         void *obj;
1418         int res = 0;
1419
1420         if (!(flags & OBJ_NOLOCK)) {
1421                 ao2_rdlock(src);
1422                 ao2_wrlock(dest);
1423         }
1424         obj = __ao2_callback(src, OBJ_NOLOCK, dup_obj_cb, dest);
1425         if (obj) {
1426                 /* Failed to put this obj into the dest container. */
1427                 __ao2_ref(obj, -1);
1428
1429                 /* Remove all items from the dest container. */
1430                 __ao2_callback(dest, OBJ_NOLOCK | OBJ_UNLINK | OBJ_NODATA | OBJ_MULTIPLE, NULL,
1431                         NULL);
1432                 res = -1;
1433         }
1434         if (!(flags & OBJ_NOLOCK)) {
1435                 ao2_unlock(dest);
1436                 ao2_unlock(src);
1437         }
1438
1439         return res;
1440 }
1441
1442 struct ao2_container *__ao2_container_clone(struct ao2_container *orig, enum search_flags flags)
1443 {
1444         struct ao2_container *clone;
1445         struct astobj2 *orig_obj;
1446         unsigned int options;
1447         int failed;
1448
1449         orig_obj = INTERNAL_OBJ(orig);
1450         if (!orig_obj) {
1451                 return NULL;
1452         }
1453         options = orig_obj->priv_data.options;
1454
1455         /* Create the clone container with the same properties as the original. */
1456         clone = __ao2_container_alloc(options, orig->n_buckets, orig->hash_fn, orig->cmp_fn);
1457         if (!clone) {
1458                 return NULL;
1459         }
1460
1461         if (flags & OBJ_NOLOCK) {
1462                 ao2_wrlock(clone);
1463         }
1464         failed = ao2_container_dup(clone, orig, flags);
1465         if (flags & OBJ_NOLOCK) {
1466                 ao2_unlock(clone);
1467         }
1468         if (failed) {
1469                 /* Object copy into the clone container failed. */
1470                 __ao2_ref(clone, -1);
1471                 clone = NULL;
1472         }
1473         return clone;
1474 }
1475
1476 struct ao2_container *__ao2_container_clone_debug(struct ao2_container *orig, enum search_flags flags, const char *tag, const char *file, int line, const char *func, int ref_debug)
1477 {
1478         struct ao2_container *clone;
1479         struct astobj2 *orig_obj;
1480         unsigned int options;
1481         int failed;
1482
1483         orig_obj = INTERNAL_OBJ(orig);
1484         if (!orig_obj) {
1485                 return NULL;
1486         }
1487         options = orig_obj->priv_data.options;
1488
1489         /* Create the clone container with the same properties as the original. */
1490         clone = __ao2_container_alloc_debug(options, orig->n_buckets, orig->hash_fn,
1491                 orig->cmp_fn, tag, file, line, func, ref_debug);
1492         if (!clone) {
1493                 return NULL;
1494         }
1495
1496         if (flags & OBJ_NOLOCK) {
1497                 ao2_wrlock(clone);
1498         }
1499         failed = ao2_container_dup(clone, orig, flags);
1500         if (flags & OBJ_NOLOCK) {
1501                 ao2_unlock(clone);
1502         }
1503         if (failed) {
1504                 /* Object copy into the clone container failed. */
1505                 if (ref_debug) {
1506                         __ao2_ref_debug(clone, -1, tag, file, line, func);
1507                 } else {
1508                         __ao2_ref(clone, -1);
1509                 }
1510                 clone = NULL;
1511         }
1512         return clone;
1513 }
1514
1515 #ifdef AO2_DEBUG
1516 static int print_cb(void *obj, void *arg, int flag)
1517 {
1518         struct ast_cli_args *a = (struct ast_cli_args *) arg;
1519         char *s = (char *)obj;
1520
1521         ast_cli(a->fd, "string <%s>\n", s);
1522         return 0;
1523 }
1524
1525 /*
1526  * Print stats
1527  */
1528 static char *handle_astobj2_stats(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
1529 {
1530         switch (cmd) {
1531         case CLI_INIT:
1532                 e->command = "astobj2 show stats";
1533                 e->usage = "Usage: astobj2 show stats\n"
1534                            "       Show astobj2 show stats\n";
1535                 return NULL;
1536         case CLI_GENERATE:
1537                 return NULL;
1538         }
1539         ast_cli(a->fd, "Objects    : %d\n", ao2.total_objects);
1540         ast_cli(a->fd, "Containers : %d\n", ao2.total_containers);
1541         ast_cli(a->fd, "Memory     : %d\n", ao2.total_mem);
1542         ast_cli(a->fd, "Locked     : %d\n", ao2.total_locked);
1543         ast_cli(a->fd, "Refs       : %d\n", ao2.total_refs);
1544         return CLI_SUCCESS;
1545 }
1546
1547 /*
1548  * This is testing code for astobj
1549  */
1550 static char *handle_astobj2_test(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
1551 {
1552         struct ao2_container *c1;
1553         struct ao2_container *c2;
1554         int i, lim;
1555         char *obj;
1556         static int prof_id = -1;
1557         struct ast_cli_args fake_args = { a->fd, 0, NULL };
1558
1559         switch (cmd) {
1560         case CLI_INIT:
1561                 e->command = "astobj2 test";
1562                 e->usage = "Usage: astobj2 test <num>\n"
1563                            "       Runs astobj2 test. Creates 'num' objects,\n"
1564                            "       and test iterators, callbacks and may be other stuff\n";
1565                 return NULL;
1566         case CLI_GENERATE:
1567                 return NULL;
1568         }
1569
1570         if (a->argc != 3) {
1571                 return CLI_SHOWUSAGE;
1572         }
1573
1574         if (prof_id == -1)
1575                 prof_id = ast_add_profile("ao2_alloc", 0);
1576
1577         ast_cli(a->fd, "argc %d argv %s %s %s\n", a->argc, a->argv[0], a->argv[1], a->argv[2]);
1578         lim = atoi(a->argv[2]);
1579         ast_cli(a->fd, "called astobj_test\n");
1580
1581         handle_astobj2_stats(e, CLI_HANDLER, &fake_args);
1582         /*
1583          * allocate a container with no default callback, and no hash function.
1584          * No hash means everything goes in the same bucket.
1585          */
1586         c1 = ao2_t_container_alloc(100, NULL /* no callback */, NULL /* no hash */,"test");
1587         ast_cli(a->fd, "container allocated as %p\n", c1);
1588
1589         /*
1590          * fill the container with objects.
1591          * ao2_alloc() gives us a reference which we pass to the
1592          * container when we do the insert.
1593          */
1594         for (i = 0; i < lim; i++) {
1595                 ast_mark(prof_id, 1 /* start */);
1596                 obj = ao2_t_alloc(80, NULL,"test");
1597                 ast_mark(prof_id, 0 /* stop */);
1598                 ast_cli(a->fd, "object %d allocated as %p\n", i, obj);
1599                 sprintf(obj, "-- this is obj %d --", i);
1600                 ao2_link(c1, obj);
1601                 /* At this point, the refcount on obj is 2 due to the allocation
1602                  * and linking. We can go ahead and reduce the refcount by 1
1603                  * right here so that when the container is unreffed later, the
1604                  * objects will be freed
1605                  */
1606                 ao2_t_ref(obj, -1, "test");
1607         }
1608
1609         ast_cli(a->fd, "testing callbacks\n");
1610         ao2_t_callback(c1, 0, print_cb, a, "test callback");
1611
1612         ast_cli(a->fd, "testing container cloning\n");
1613         c2 = ao2_container_clone(c1, 0);
1614         if (ao2_container_count(c1) != ao2_container_count(c2)) {
1615                 ast_cli(a->fd, "Cloned container does not have the same number of objects!\n");
1616         }
1617         ao2_t_callback(c2, 0, print_cb, a, "test callback");
1618
1619         ast_cli(a->fd, "testing iterators, remove every second object\n");
1620         {
1621                 struct ao2_iterator ai;
1622                 int x = 0;
1623
1624                 ai = ao2_iterator_init(c1, 0);
1625                 while ( (obj = ao2_t_iterator_next(&ai,"test")) ) {
1626                         ast_cli(a->fd, "iterator on <%s>\n", obj);
1627                         if (x++ & 1)
1628                                 ao2_t_unlink(c1, obj,"test");
1629                         ao2_t_ref(obj, -1,"test");
1630                 }
1631                 ao2_iterator_destroy(&ai);
1632                 ast_cli(a->fd, "testing iterators again\n");
1633                 ai = ao2_iterator_init(c1, 0);
1634                 while ( (obj = ao2_t_iterator_next(&ai,"test")) ) {
1635                         ast_cli(a->fd, "iterator on <%s>\n", obj);
1636                         ao2_t_ref(obj, -1,"test");
1637                 }
1638                 ao2_iterator_destroy(&ai);
1639         }
1640
1641         ast_cli(a->fd, "testing callbacks again\n");
1642         ao2_t_callback(c1, 0, print_cb, a, "test callback");
1643
1644         ast_verbose("now you should see an error message:\n");
1645         ao2_t_ref(&i, -1, "");  /* i is not a valid object so we print an error here */
1646
1647         ast_cli(a->fd, "destroy container\n");
1648         ao2_t_ref(c1, -1, "");  /* destroy container */
1649         ao2_t_ref(c2, -1, "");  /* destroy container */
1650         handle_astobj2_stats(e, CLI_HANDLER, &fake_args);
1651         return CLI_SUCCESS;
1652 }
1653
1654 static struct ast_cli_entry cli_astobj2[] = {
1655         AST_CLI_DEFINE(handle_astobj2_stats, "Print astobj2 statistics"),
1656         AST_CLI_DEFINE(handle_astobj2_test, "Test astobj2"),
1657 };
1658 #endif /* AO2_DEBUG */
1659
1660 int astobj2_init(void)
1661 {
1662 #ifdef AO2_DEBUG
1663         ast_cli_register_multiple(cli_astobj2, ARRAY_LEN(cli_astobj2));
1664 #endif
1665
1666         return 0;
1667 }