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