ARI: Add ability to raise arbitrary User Events
[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 /*! \file
18  *
19  * \brief Functions implementing astobj2 objects.
20  *
21  * \author Richard Mudgett <rmudgett@digium.com>
22  */
23
24 /*** MODULEINFO
25         <support_level>core</support_level>
26  ***/
27
28 #include "asterisk.h"
29
30 ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
31
32 #include "asterisk/_private.h"
33 #include "asterisk/astobj2.h"
34 #include "asterisk/dlinkedlists.h"
35 #include "asterisk/utils.h"
36 #include "asterisk/cli.h"
37 #include "asterisk/paths.h"
38
39 #if defined(TEST_FRAMEWORK)
40 /* We are building with the test framework enabled so enable AO2 debug tests as well. */
41 #define AO2_DEBUG 1
42 #endif  /* defined(TEST_FRAMEWORK) */
43
44 static FILE *ref_log;
45
46 /*!
47  * astobj2 objects are always preceded by this data structure,
48  * which contains a reference counter,
49  * option flags and a pointer to a destructor.
50  * The refcount is used to decide when it is time to
51  * invoke the destructor.
52  * The magic number is used for consistency check.
53  */
54 struct __priv_data {
55         int ref_counter;
56         ao2_destructor_fn destructor_fn;
57         /*! User data size for stats */
58         size_t data_size;
59         /*! The ao2 object option flags */
60         uint32_t options;
61         /*! magic number.  This is used to verify that a pointer passed in is a
62          *  valid astobj2 */
63         uint32_t magic;
64 };
65
66 #define AO2_MAGIC       0xa570b123
67
68 /*!
69  * What an astobj2 object looks like: fixed-size private data
70  * followed by variable-size user data.
71  */
72 struct astobj2 {
73         struct __priv_data priv_data;
74         void *user_data[0];
75 };
76
77 struct ao2_lock_priv {
78         ast_mutex_t lock;
79 };
80
81 /* AstObj2 with recursive lock. */
82 struct astobj2_lock {
83         struct ao2_lock_priv mutex;
84         struct __priv_data priv_data;
85         void *user_data[0];
86 };
87
88 struct ao2_rwlock_priv {
89         ast_rwlock_t lock;
90         /*! Count of the number of threads holding a lock on this object. -1 if it is the write lock. */
91         int num_lockers;
92 };
93
94 /* AstObj2 with RW lock. */
95 struct astobj2_rwlock {
96         struct ao2_rwlock_priv rwlock;
97         struct __priv_data priv_data;
98         void *user_data[0];
99 };
100
101 #if defined(AST_DEVMODE)
102 #define AO2_DEVMODE_STAT(stat)  stat
103 #else
104 #define AO2_DEVMODE_STAT(stat)
105 #endif  /* defined(AST_DEVMODE) */
106
107 #ifdef AO2_DEBUG
108 struct ao2_stats {
109         volatile int total_objects;
110         volatile int total_mem;
111         volatile int total_containers;
112         volatile int total_refs;
113         volatile int total_locked;
114 };
115
116 static struct ao2_stats ao2;
117 #endif
118
119 #ifdef HAVE_BKTR
120 #include <execinfo.h>    /* for backtrace */
121 #endif
122
123 void ao2_bt(void)
124 {
125 #ifdef HAVE_BKTR
126         int depth;
127         int idx;
128 #define N1      20
129         void *addresses[N1];
130         char **strings;
131
132         depth = backtrace(addresses, N1);
133         strings = ast_bt_get_symbols(addresses, depth);
134         ast_verbose("backtrace returned: %d\n", depth);
135         for (idx = 0; idx < depth; ++idx) {
136                 ast_verbose("%d: %p %s\n", idx, addresses[idx], strings[idx]);
137         }
138         ast_std_free(strings);
139 #endif
140 }
141
142 #define INTERNAL_OBJ_MUTEX(user_data) \
143         ((struct astobj2_lock *) (((char *) (user_data)) - sizeof(struct astobj2_lock)))
144
145 #define INTERNAL_OBJ_RWLOCK(user_data) \
146         ((struct astobj2_rwlock *) (((char *) (user_data)) - sizeof(struct astobj2_rwlock)))
147
148 /*!
149  * \brief convert from a pointer _p to a user-defined object
150  *
151  * \return the pointer to the astobj2 structure
152  */
153 static inline struct astobj2 *INTERNAL_OBJ(void *user_data)
154 {
155         struct astobj2 *p;
156
157         if (!user_data) {
158                 ast_log(LOG_ERROR, "user_data is NULL\n");
159                 return NULL;
160         }
161
162         p = (struct astobj2 *) ((char *) user_data - sizeof(*p));
163         if (AO2_MAGIC != p->priv_data.magic) {
164                 if (p->priv_data.magic) {
165                         ast_log(LOG_ERROR, "bad magic number 0x%x for object %p\n",
166                                 p->priv_data.magic, user_data);
167                 } else {
168                         ast_log(LOG_ERROR,
169                                 "bad magic number for object %p. Object is likely destroyed.\n",
170                                 user_data);
171                 }
172                 ast_assert(0);
173                 return NULL;
174         }
175
176         return p;
177 }
178
179 /*!
180  * \brief convert from a pointer _p to an astobj2 object
181  *
182  * \return the pointer to the user-defined portion.
183  */
184 #define EXTERNAL_OBJ(_p)        ((_p) == NULL ? NULL : (_p)->user_data)
185
186 int __ao2_lock(void *user_data, enum ao2_lock_req lock_how, const char *file, const char *func, int line, const char *var)
187 {
188         struct astobj2 *obj = INTERNAL_OBJ(user_data);
189         struct astobj2_lock *obj_mutex;
190         struct astobj2_rwlock *obj_rwlock;
191         int res = 0;
192
193         if (obj == NULL) {
194                 ast_assert(0);
195                 return -1;
196         }
197
198         switch (obj->priv_data.options & AO2_ALLOC_OPT_LOCK_MASK) {
199         case AO2_ALLOC_OPT_LOCK_MUTEX:
200                 obj_mutex = INTERNAL_OBJ_MUTEX(user_data);
201                 res = __ast_pthread_mutex_lock(file, line, func, var, &obj_mutex->mutex.lock);
202 #ifdef AO2_DEBUG
203                 if (!res) {
204                         ast_atomic_fetchadd_int(&ao2.total_locked, 1);
205                 }
206 #endif
207                 break;
208         case AO2_ALLOC_OPT_LOCK_RWLOCK:
209                 obj_rwlock = INTERNAL_OBJ_RWLOCK(user_data);
210                 switch (lock_how) {
211                 case AO2_LOCK_REQ_MUTEX:
212                 case AO2_LOCK_REQ_WRLOCK:
213                         res = __ast_rwlock_wrlock(file, line, func, &obj_rwlock->rwlock.lock, var);
214                         if (!res) {
215                                 ast_atomic_fetchadd_int(&obj_rwlock->rwlock.num_lockers, -1);
216 #ifdef AO2_DEBUG
217                                 ast_atomic_fetchadd_int(&ao2.total_locked, 1);
218 #endif
219                         }
220                         break;
221                 case AO2_LOCK_REQ_RDLOCK:
222                         res = __ast_rwlock_rdlock(file, line, func, &obj_rwlock->rwlock.lock, var);
223                         if (!res) {
224                                 ast_atomic_fetchadd_int(&obj_rwlock->rwlock.num_lockers, +1);
225 #ifdef AO2_DEBUG
226                                 ast_atomic_fetchadd_int(&ao2.total_locked, 1);
227 #endif
228                         }
229                         break;
230                 }
231                 break;
232         case AO2_ALLOC_OPT_LOCK_NOLOCK:
233                 /* The ao2 object has no lock. */
234                 break;
235         default:
236                 ast_log(__LOG_ERROR, file, line, func, "Invalid lock option on ao2 object %p\n",
237                         user_data);
238                 return -1;
239         }
240
241         return res;
242 }
243
244 int __ao2_unlock(void *user_data, const char *file, const char *func, int line, const char *var)
245 {
246         struct astobj2 *obj = INTERNAL_OBJ(user_data);
247         struct astobj2_lock *obj_mutex;
248         struct astobj2_rwlock *obj_rwlock;
249         int res = 0;
250         int current_value;
251
252         if (obj == NULL) {
253                 ast_assert(0);
254                 return -1;
255         }
256
257         switch (obj->priv_data.options & AO2_ALLOC_OPT_LOCK_MASK) {
258         case AO2_ALLOC_OPT_LOCK_MUTEX:
259                 obj_mutex = INTERNAL_OBJ_MUTEX(user_data);
260                 res = __ast_pthread_mutex_unlock(file, line, func, var, &obj_mutex->mutex.lock);
261 #ifdef AO2_DEBUG
262                 if (!res) {
263                         ast_atomic_fetchadd_int(&ao2.total_locked, -1);
264                 }
265 #endif
266                 break;
267         case AO2_ALLOC_OPT_LOCK_RWLOCK:
268                 obj_rwlock = INTERNAL_OBJ_RWLOCK(user_data);
269
270                 current_value = ast_atomic_fetchadd_int(&obj_rwlock->rwlock.num_lockers, -1) - 1;
271                 if (current_value < 0) {
272                         /* It was a WRLOCK that we are unlocking.  Fix the count. */
273                         ast_atomic_fetchadd_int(&obj_rwlock->rwlock.num_lockers, -current_value);
274                 }
275                 res = __ast_rwlock_unlock(file, line, func, &obj_rwlock->rwlock.lock, var);
276 #ifdef AO2_DEBUG
277                 if (!res) {
278                         ast_atomic_fetchadd_int(&ao2.total_locked, -1);
279                 }
280 #endif
281                 break;
282         case AO2_ALLOC_OPT_LOCK_NOLOCK:
283                 /* The ao2 object has no lock. */
284                 break;
285         default:
286                 ast_log(__LOG_ERROR, file, line, func, "Invalid lock option on ao2 object %p\n",
287                         user_data);
288                 res = -1;
289                 break;
290         }
291         return res;
292 }
293
294 int __ao2_trylock(void *user_data, enum ao2_lock_req lock_how, const char *file, const char *func, int line, const char *var)
295 {
296         struct astobj2 *obj = INTERNAL_OBJ(user_data);
297         struct astobj2_lock *obj_mutex;
298         struct astobj2_rwlock *obj_rwlock;
299         int res = 0;
300
301         if (obj == NULL) {
302                 ast_assert(0);
303                 return -1;
304         }
305
306         switch (obj->priv_data.options & AO2_ALLOC_OPT_LOCK_MASK) {
307         case AO2_ALLOC_OPT_LOCK_MUTEX:
308                 obj_mutex = INTERNAL_OBJ_MUTEX(user_data);
309                 res = __ast_pthread_mutex_trylock(file, line, func, var, &obj_mutex->mutex.lock);
310 #ifdef AO2_DEBUG
311                 if (!res) {
312                         ast_atomic_fetchadd_int(&ao2.total_locked, 1);
313                 }
314 #endif
315                 break;
316         case AO2_ALLOC_OPT_LOCK_RWLOCK:
317                 obj_rwlock = INTERNAL_OBJ_RWLOCK(user_data);
318                 switch (lock_how) {
319                 case AO2_LOCK_REQ_MUTEX:
320                 case AO2_LOCK_REQ_WRLOCK:
321                         res = __ast_rwlock_trywrlock(file, line, func, &obj_rwlock->rwlock.lock, var);
322                         if (!res) {
323                                 ast_atomic_fetchadd_int(&obj_rwlock->rwlock.num_lockers, -1);
324 #ifdef AO2_DEBUG
325                                 ast_atomic_fetchadd_int(&ao2.total_locked, 1);
326 #endif
327                         }
328                         break;
329                 case AO2_LOCK_REQ_RDLOCK:
330                         res = __ast_rwlock_tryrdlock(file, line, func, &obj_rwlock->rwlock.lock, var);
331                         if (!res) {
332                                 ast_atomic_fetchadd_int(&obj_rwlock->rwlock.num_lockers, +1);
333 #ifdef AO2_DEBUG
334                                 ast_atomic_fetchadd_int(&ao2.total_locked, 1);
335 #endif
336                         }
337                         break;
338                 }
339                 break;
340         case AO2_ALLOC_OPT_LOCK_NOLOCK:
341                 /* The ao2 object has no lock. */
342                 return 0;
343         default:
344                 ast_log(__LOG_ERROR, file, line, func, "Invalid lock option on ao2 object %p\n",
345                         user_data);
346                 return -1;
347         }
348
349
350         return res;
351 }
352
353 /*!
354  * \internal
355  * \brief Adjust an object's lock to the requested level.
356  *
357  * \param user_data An ao2 object to adjust lock level.
358  * \param lock_how What level to adjust lock.
359  * \param keep_stronger TRUE if keep original lock level if it is stronger.
360  *
361  * \pre The ao2 object is already locked.
362  *
363  * \details
364  * An ao2 object with a RWLOCK will have its lock level adjusted
365  * to the specified level if it is not already there.  An ao2
366  * object with a different type of lock is not affected.
367  *
368  * \return Original lock level.
369  */
370 static enum ao2_lock_req adjust_lock(void *user_data, enum ao2_lock_req lock_how, int keep_stronger)
371 {
372         struct astobj2 *obj = INTERNAL_OBJ(user_data);
373         struct astobj2_rwlock *obj_rwlock;
374         enum ao2_lock_req orig_lock;
375
376         switch (obj->priv_data.options & AO2_ALLOC_OPT_LOCK_MASK) {
377         case AO2_ALLOC_OPT_LOCK_RWLOCK:
378                 obj_rwlock = INTERNAL_OBJ_RWLOCK(user_data);
379                 if (obj_rwlock->rwlock.num_lockers < 0) {
380                         orig_lock = AO2_LOCK_REQ_WRLOCK;
381                 } else {
382                         orig_lock = AO2_LOCK_REQ_RDLOCK;
383                 }
384                 switch (lock_how) {
385                 case AO2_LOCK_REQ_MUTEX:
386                         lock_how = AO2_LOCK_REQ_WRLOCK;
387                         /* Fall through */
388                 case AO2_LOCK_REQ_WRLOCK:
389                         if (lock_how != orig_lock) {
390                                 /* Switch from read lock to write lock. */
391                                 ao2_unlock(user_data);
392                                 ao2_wrlock(user_data);
393                         }
394                         break;
395                 case AO2_LOCK_REQ_RDLOCK:
396                         if (!keep_stronger && lock_how != orig_lock) {
397                                 /* Switch from write lock to read lock. */
398                                 ao2_unlock(user_data);
399                                 ao2_rdlock(user_data);
400                         }
401                         break;
402                 }
403                 break;
404         default:
405                 ast_log(LOG_ERROR, "Invalid lock option on ao2 object %p\n", user_data);
406                 /* Fall through */
407         case AO2_ALLOC_OPT_LOCK_NOLOCK:
408         case AO2_ALLOC_OPT_LOCK_MUTEX:
409                 orig_lock = AO2_LOCK_REQ_MUTEX;
410                 break;
411         }
412
413         return orig_lock;
414 }
415
416 void *ao2_object_get_lockaddr(void *user_data)
417 {
418         struct astobj2 *obj = INTERNAL_OBJ(user_data);
419         struct astobj2_lock *obj_mutex;
420
421         if (obj == NULL) {
422                 ast_assert(0);
423                 return NULL;
424         }
425
426         switch (obj->priv_data.options & AO2_ALLOC_OPT_LOCK_MASK) {
427         case AO2_ALLOC_OPT_LOCK_MUTEX:
428                 obj_mutex = INTERNAL_OBJ_MUTEX(user_data);
429                 return &obj_mutex->mutex.lock;
430         default:
431                 break;
432         }
433
434         return NULL;
435 }
436
437 static int internal_ao2_ref(void *user_data, int delta, const char *file, int line, const char *func)
438 {
439         struct astobj2 *obj = INTERNAL_OBJ(user_data);
440         struct astobj2_lock *obj_mutex;
441         struct astobj2_rwlock *obj_rwlock;
442         int current_value;
443         int ret;
444
445         if (obj == NULL) {
446                 ast_assert(0);
447                 return -1;
448         }
449
450         /* if delta is 0, just return the refcount */
451         if (delta == 0) {
452                 return obj->priv_data.ref_counter;
453         }
454
455         /* we modify with an atomic operation the reference counter */
456         ret = ast_atomic_fetchadd_int(&obj->priv_data.ref_counter, delta);
457         current_value = ret + delta;
458
459 #ifdef AO2_DEBUG
460         ast_atomic_fetchadd_int(&ao2.total_refs, delta);
461 #endif
462
463         if (0 < current_value) {
464                 /* The object still lives. */
465                 return ret;
466         }
467
468         /* this case must never happen */
469         if (current_value < 0) {
470                 ast_log(__LOG_ERROR, file, line, func,
471                         "Invalid refcount %d on ao2 object %p\n", current_value, user_data);
472         }
473
474         /* last reference, destroy the object */
475         if (obj->priv_data.destructor_fn != NULL) {
476                 obj->priv_data.destructor_fn(user_data);
477         }
478
479 #ifdef AO2_DEBUG
480         ast_atomic_fetchadd_int(&ao2.total_mem, - obj->priv_data.data_size);
481         ast_atomic_fetchadd_int(&ao2.total_objects, -1);
482 #endif
483
484         /* In case someone uses an object after it's been freed */
485         obj->priv_data.magic = 0;
486
487         switch (obj->priv_data.options & AO2_ALLOC_OPT_LOCK_MASK) {
488         case AO2_ALLOC_OPT_LOCK_MUTEX:
489                 obj_mutex = INTERNAL_OBJ_MUTEX(user_data);
490                 ast_mutex_destroy(&obj_mutex->mutex.lock);
491
492                 ast_free(obj_mutex);
493                 break;
494         case AO2_ALLOC_OPT_LOCK_RWLOCK:
495                 obj_rwlock = INTERNAL_OBJ_RWLOCK(user_data);
496                 ast_rwlock_destroy(&obj_rwlock->rwlock.lock);
497
498                 ast_free(obj_rwlock);
499                 break;
500         case AO2_ALLOC_OPT_LOCK_NOLOCK:
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                 ast_log_backtrace();
518                 ast_assert(0);
519                 return -1;
520         }
521
522         if (ref_log) {
523                 if (obj->priv_data.ref_counter + delta == 0) {
524                         fprintf(ref_log, "%p,%d,%d,%s,%d,%s,**destructor**,%s\n", user_data, delta, ast_get_tid(), file, line, func, tag);
525                         fflush(ref_log);
526                 } else if (delta != 0) {
527                         fprintf(ref_log, "%p,%s%d,%d,%s,%d,%s,%d,%s\n", user_data, (delta < 0 ? "" : "+"),
528                                 delta, ast_get_tid(), file, line, func, obj ? obj->priv_data.ref_counter : -1, tag);
529                         fflush(ref_log);
530                 }
531         }
532         return internal_ao2_ref(user_data, delta, file, line, func);
533 }
534
535 int __ao2_ref(void *user_data, int delta)
536 {
537         return internal_ao2_ref(user_data, delta, __FILE__, __LINE__, __FUNCTION__);
538 }
539
540 void __ao2_cleanup_debug(void *obj, const char *file, int line, const char *function)
541 {
542         if (obj) {
543                 __ao2_ref_debug(obj, -1, "ao2_cleanup", file, line, function);
544         }
545 }
546
547 void __ao2_cleanup(void *obj)
548 {
549         if (obj) {
550                 ao2_ref(obj, -1);
551         }
552 }
553
554 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)
555 {
556         /* allocation */
557         struct astobj2 *obj;
558         struct astobj2_lock *obj_mutex;
559         struct astobj2_rwlock *obj_rwlock;
560
561         switch (options & AO2_ALLOC_OPT_LOCK_MASK) {
562         case AO2_ALLOC_OPT_LOCK_MUTEX:
563 #if defined(__AST_DEBUG_MALLOC)
564                 obj_mutex = __ast_calloc(1, sizeof(*obj_mutex) + data_size, file, line, func);
565 #else
566                 obj_mutex = ast_calloc(1, sizeof(*obj_mutex) + data_size);
567 #endif
568                 if (obj_mutex == NULL) {
569                         return NULL;
570                 }
571
572                 ast_mutex_init(&obj_mutex->mutex.lock);
573                 obj = (struct astobj2 *) &obj_mutex->priv_data;
574                 break;
575         case AO2_ALLOC_OPT_LOCK_RWLOCK:
576 #if defined(__AST_DEBUG_MALLOC)
577                 obj_rwlock = __ast_calloc(1, sizeof(*obj_rwlock) + data_size, file, line, func);
578 #else
579                 obj_rwlock = ast_calloc(1, sizeof(*obj_rwlock) + data_size);
580 #endif
581                 if (obj_rwlock == NULL) {
582                         return NULL;
583                 }
584
585                 ast_rwlock_init(&obj_rwlock->rwlock.lock);
586                 obj = (struct astobj2 *) &obj_rwlock->priv_data;
587                 break;
588         case AO2_ALLOC_OPT_LOCK_NOLOCK:
589 #if defined(__AST_DEBUG_MALLOC)
590                 obj = __ast_calloc(1, sizeof(*obj) + data_size, file, line, func);
591 #else
592                 obj = ast_calloc(1, sizeof(*obj) + data_size);
593 #endif
594                 if (obj == NULL) {
595                         return NULL;
596                 }
597                 break;
598         default:
599                 /* Invalid option value. */
600                 ast_log(__LOG_DEBUG, file, line, func, "Invalid lock option requested\n");
601                 return NULL;
602         }
603
604         /* Initialize common ao2 values. */
605         obj->priv_data.ref_counter = 1;
606         obj->priv_data.destructor_fn = destructor_fn;   /* can be NULL */
607         obj->priv_data.data_size = data_size;
608         obj->priv_data.options = options;
609         obj->priv_data.magic = AO2_MAGIC;
610
611 #ifdef AO2_DEBUG
612         ast_atomic_fetchadd_int(&ao2.total_objects, 1);
613         ast_atomic_fetchadd_int(&ao2.total_mem, data_size);
614         ast_atomic_fetchadd_int(&ao2.total_refs, 1);
615 #endif
616
617         /* return a pointer to the user data */
618         return EXTERNAL_OBJ(obj);
619 }
620
621 void *__ao2_alloc_debug(size_t data_size, ao2_destructor_fn destructor_fn, unsigned int options, const char *tag,
622         const char *file, int line, const char *func, int ref_debug)
623 {
624         /* allocation */
625         void *obj;
626
627         if ((obj = internal_ao2_alloc(data_size, destructor_fn, options, file, line, func)) == NULL) {
628                 return NULL;
629         }
630
631         if (ref_log) {
632                 fprintf(ref_log, "%p,+1,%d,%s,%d,%s,**constructor**,%s\n", obj, ast_get_tid(), file, line, func, tag);
633                 fflush(ref_log);
634         }
635
636         /* return a pointer to the user data */
637         return obj;
638 }
639
640 void *__ao2_alloc(size_t data_size, ao2_destructor_fn destructor_fn, unsigned int options)
641 {
642         return internal_ao2_alloc(data_size, destructor_fn, options, __FILE__, __LINE__, __FUNCTION__);
643 }
644
645
646 void __ao2_global_obj_release(struct ao2_global_obj *holder, const char *tag, const char *file, int line, const char *func, const char *name)
647 {
648         if (!holder) {
649                 /* For sanity */
650                 ast_log(LOG_ERROR, "Must be called with a global object!\n");
651                 ast_assert(0);
652                 return;
653         }
654         if (__ast_rwlock_wrlock(file, line, func, &holder->lock, name)) {
655                 /* Could not get the write lock. */
656                 ast_assert(0);
657                 return;
658         }
659
660         /* Release the held ao2 object. */
661         if (holder->obj) {
662                 if (tag) {
663                         __ao2_ref_debug(holder->obj, -1, tag, file, line, func);
664                 } else {
665                         __ao2_ref(holder->obj, -1);
666                 }
667                 holder->obj = NULL;
668         }
669
670         __ast_rwlock_unlock(file, line, func, &holder->lock, name);
671 }
672
673 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)
674 {
675         void *obj_old;
676
677         if (!holder) {
678                 /* For sanity */
679                 ast_log(LOG_ERROR, "Must be called with a global object!\n");
680                 ast_assert(0);
681                 return NULL;
682         }
683         if (__ast_rwlock_wrlock(file, line, func, &holder->lock, name)) {
684                 /* Could not get the write lock. */
685                 ast_assert(0);
686                 return NULL;
687         }
688
689         if (obj) {
690                 if (tag) {
691                         __ao2_ref_debug(obj, +1, tag, file, line, func);
692                 } else {
693                         __ao2_ref(obj, +1);
694                 }
695         }
696         obj_old = holder->obj;
697         holder->obj = obj;
698
699         __ast_rwlock_unlock(file, line, func, &holder->lock, name);
700
701         return obj_old;
702 }
703
704 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)
705 {
706         void *obj_old;
707
708         obj_old = __ao2_global_obj_replace(holder, obj, tag, file, line, func, name);
709         if (obj_old) {
710                 if (tag) {
711                         __ao2_ref_debug(obj_old, -1, tag, file, line, func);
712                 } else {
713                         __ao2_ref(obj_old, -1);
714                 }
715                 return 1;
716         }
717         return 0;
718 }
719
720 void *__ao2_global_obj_ref(struct ao2_global_obj *holder, const char *tag, const char *file, int line, const char *func, const char *name)
721 {
722         void *obj;
723
724         if (!holder) {
725                 /* For sanity */
726                 ast_log(LOG_ERROR, "Must be called with a global object!\n");
727                 ast_assert(0);
728                 return NULL;
729         }
730
731         if (__ast_rwlock_rdlock(file, line, func, &holder->lock, name)) {
732                 /* Could not get the read lock. */
733                 ast_assert(0);
734                 return NULL;
735         }
736
737         obj = holder->obj;
738         if (obj) {
739                 if (tag) {
740                         __ao2_ref_debug(obj, +1, tag, file, line, func);
741                 } else {
742                         __ao2_ref(obj, +1);
743                 }
744         }
745
746         __ast_rwlock_unlock(file, line, func, &holder->lock, name);
747
748         return obj;
749 }
750
751 enum ao2_callback_type {
752         AO2_CALLBACK_DEFAULT,
753         AO2_CALLBACK_WITH_DATA,
754 };
755
756 enum ao2_container_insert {
757         /*! The node was inserted into the container. */
758         AO2_CONTAINER_INSERT_NODE_INSERTED,
759         /*! The node object replaced an existing node object. */
760         AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED,
761         /*! The node was rejected (duplicate). */
762         AO2_CONTAINER_INSERT_NODE_REJECTED,
763 };
764
765 enum ao2_container_rtti {
766         /*! This is a hash container */
767         AO2_CONTAINER_RTTI_HASH,
768         /*! This is a red-black tree container */
769         AO2_CONTAINER_RTTI_RBTREE,
770 };
771
772 /*!
773  * \brief Generic container node.
774  *
775  * \details This is the base container node type that contains
776  * values common to all container nodes.
777  */
778 struct ao2_container_node {
779         /*! Stored object in node. */
780         void *obj;
781         /*! Container holding the node.  (Does not hold a reference.) */
782         struct ao2_container *my_container;
783         /*! TRUE if the node is linked into the container. */
784         unsigned int is_linked:1;
785 };
786
787 /*!
788  * \brief Destroy this container.
789  *
790  * \param self Container to operate upon.
791  *
792  * \return Nothing
793  */
794 typedef void (*ao2_container_destroy_fn)(struct ao2_container *self);
795
796 /*!
797  * \brief Create an empty copy of this container.
798  *
799  * \param self Container to operate upon.
800  *
801  * \retval empty-container on success.
802  * \retval NULL on error.
803  */
804 typedef struct ao2_container *(*ao2_container_alloc_empty_clone_fn)(struct ao2_container *self);
805
806 /*!
807  * \brief Create an empty copy of this container. (Debug version)
808  *
809  * \param self Container to operate upon.
810  * \param tag used for debugging.
811  * \param file Debug file name invoked from
812  * \param line Debug line invoked from
813  * \param func Debug function name invoked from
814  * \param ref_debug TRUE if to output a debug reference message.
815  *
816  * \retval empty-container on success.
817  * \retval NULL on error.
818  */
819 typedef struct ao2_container *(*ao2_container_alloc_empty_clone_debug_fn)(struct ao2_container *self, const char *tag, const char *file, int line, const char *func, int ref_debug);
820
821 /*!
822  * \brief Create a new container node.
823  *
824  * \param self Container to operate upon.
825  * \param obj_new Object to put into the node.
826  * \param tag used for debugging.
827  * \param file Debug file name invoked from
828  * \param line Debug line invoked from
829  * \param func Debug function name invoked from
830  *
831  * \retval initialized-node on success.
832  * \retval NULL on error.
833  */
834 typedef struct ao2_container_node *(*ao2_container_new_node_fn)(struct ao2_container *self, void *obj_new, const char *tag, const char *file, int line, const char *func);
835
836 /*!
837  * \brief Insert a node into this container.
838  *
839  * \param self Container to operate upon.
840  * \param node Container node to insert into the container.
841  *
842  * \return enum ao2_container_insert value.
843  */
844 typedef enum ao2_container_insert (*ao2_container_insert_fn)(struct ao2_container *self, struct ao2_container_node *node);
845
846 /*!
847  * \brief Find the first container node in a traversal.
848  *
849  * \param self Container to operate upon.
850  * \param flags search_flags to control traversing the container
851  * \param arg Comparison callback arg parameter.
852  * \param v_state Traversal state to restart container traversal.
853  *
854  * \retval node-ptr of found node (Reffed).
855  * \retval NULL when no node found.
856  */
857 typedef struct ao2_container_node *(*ao2_container_find_first_fn)(struct ao2_container *self, enum search_flags flags, void *arg, void *v_state);
858
859 /*!
860  * \brief Find the next container node in a traversal.
861  *
862  * \param self Container to operate upon.
863  * \param v_state Traversal state to restart container traversal.
864  * \param prev Previous node returned by the traversal search functions.
865  *    The ref ownership is passed back to this function.
866  *
867  * \retval node-ptr of found node (Reffed).
868  * \retval NULL when no node found.
869  */
870 typedef struct ao2_container_node *(*ao2_container_find_next_fn)(struct ao2_container *self, void *v_state, struct ao2_container_node *prev);
871
872 /*!
873  * \brief Cleanup the container traversal state.
874  *
875  * \param v_state Traversal state to cleanup.
876  *
877  * \return Nothing
878  */
879 typedef void (*ao2_container_find_cleanup_fn)(void *v_state);
880
881 /*!
882  * \brief Find the next non-empty iteration node in the container.
883  *
884  * \param self Container to operate upon.
885  * \param prev Previous node returned by the iterator.
886  * \param flags search_flags to control iterating the container.
887  *   Only AO2_ITERATOR_DESCENDING is useful by the method.
888  *
889  * \note The container is already locked.
890  *
891  * \retval node on success.
892  * \retval NULL on error or no more nodes in the container.
893  */
894 typedef struct ao2_container_node *(*ao2_iterator_next_fn)(struct ao2_container *self, struct ao2_container_node *prev, enum ao2_iterator_flags flags);
895
896 /*!
897  * \brief Display contents of the specified container.
898  *
899  * \param self Container to dump.
900  * \param where User data needed by prnt to determine where to put output.
901  * \param prnt Print output callback function to use.
902  * \param prnt_obj Callback function to print the given object's key. (NULL if not available)
903  *
904  * \return Nothing
905  */
906 typedef void (*ao2_container_display)(struct ao2_container *self, void *where, ao2_prnt_fn *prnt, ao2_prnt_obj_fn *prnt_obj);
907
908 /*!
909  * \brief Display statistics of the specified container.
910  *
911  * \param self Container to display statistics.
912  * \param where User data needed by prnt to determine where to put output.
913  * \param prnt Print output callback function to use.
914  *
915  * \note The container is already locked for reading.
916  *
917  * \return Nothing
918  */
919 typedef void (*ao2_container_statistics)(struct ao2_container *self, void *where, ao2_prnt_fn *prnt);
920
921 /*!
922  * \brief Perform an integrity check on the specified container.
923  *
924  * \param self Container to check integrity.
925  *
926  * \note The container is already locked for reading.
927  *
928  * \retval 0 on success.
929  * \retval -1 on error.
930  */
931 typedef int (*ao2_container_integrity)(struct ao2_container *self);
932
933 /*! Container virtual methods template. */
934 struct ao2_container_methods {
935         /*! Run Time Type Identification */
936         enum ao2_container_rtti type;
937         /*! Destroy this container. */
938         ao2_container_destroy_fn destroy;
939         /*! \brief Create an empty copy of this container. */
940         ao2_container_alloc_empty_clone_fn alloc_empty_clone;
941         /*! \brief Create an empty copy of this container. (Debug version) */
942         ao2_container_alloc_empty_clone_debug_fn alloc_empty_clone_debug;
943         /*! Create a new container node. */
944         ao2_container_new_node_fn new_node;
945         /*! Insert a node into this container. */
946         ao2_container_insert_fn insert;
947         /*! Traverse the container, find the first node. */
948         ao2_container_find_first_fn traverse_first;
949         /*! Traverse the container, find the next node. */
950         ao2_container_find_next_fn traverse_next;
951         /*! Traverse the container, cleanup state. */
952         ao2_container_find_cleanup_fn traverse_cleanup;
953         /*! Find the next iteration element in the container. */
954         ao2_iterator_next_fn iterator_next;
955 #if defined(AST_DEVMODE)
956         /*! Display container contents. (Method for debug purposes) */
957         ao2_container_display dump;
958         /*! Display container debug statistics. (Method for debug purposes) */
959         ao2_container_statistics stats;
960         /*! Perform an integrity check on the container. (Method for debug purposes) */
961         ao2_container_integrity integrity;
962 #endif  /* defined(AST_DEVMODE) */
963 };
964
965 /*!
966  * \brief Generic container type.
967  *
968  * \details This is the base container type that contains values
969  * common to all container types.
970  *
971  * \todo Linking and unlinking container objects is typically
972  * expensive, as it involves a malloc()/free() of a small object
973  * which is very inefficient.  To optimize this, we can allocate
974  * larger arrays of container nodes when we run out of them, and
975  * then manage our own freelist.  This will be more efficient as
976  * we can do the freelist management while we hold the lock
977  * (that we need anyway).
978  */
979 struct ao2_container {
980         /*! Container virtual method table. */
981         const struct ao2_container_methods *v_table;
982         /*! Container sort function if the container is sorted. */
983         ao2_sort_fn *sort_fn;
984         /*! Container traversal matching function for ao2_find. */
985         ao2_callback_fn *cmp_fn;
986         /*! The container option flags */
987         uint32_t options;
988         /*! Number of elements in the container. */
989         int elements;
990 #if defined(AST_DEVMODE)
991         /*! Number of nodes in the container. */
992         int nodes;
993         /*! Maximum number of empty nodes in the container. (nodes - elements) */
994         int max_empty_nodes;
995 #endif  /* defined(AST_DEVMODE) */
996         /*!
997          * \brief TRUE if the container is being destroyed.
998          *
999          * \note The destruction traversal should override any requested
1000          * search order to do the most efficient order for destruction.
1001          *
1002          * \note There should not be any empty nodes in the container
1003          * during destruction.  If there are then an error needs to be
1004          * issued about container node reference leaks.
1005          */
1006         unsigned int destroying:1;
1007 };
1008
1009 /*!
1010  * return the number of elements in the container
1011  */
1012 int ao2_container_count(struct ao2_container *c)
1013 {
1014         return ast_atomic_fetchadd_int(&c->elements, 0);
1015 }
1016
1017 #if defined(AST_DEVMODE)
1018 static void hash_ao2_link_node_stat(struct ao2_container *hash, struct ao2_container_node *hash_node);
1019 static void hash_ao2_unlink_node_stat(struct ao2_container *hash, struct ao2_container_node *hash_node);
1020 #endif  /* defined(AST_DEVMODE) */
1021
1022 /*!
1023  * \internal
1024  * \brief Link an object into this container.  (internal)
1025  *
1026  * \param self Container to operate upon.
1027  * \param obj_new Object to insert into the container.
1028  * \param flags search_flags to control linking the object.  (OBJ_NOLOCK)
1029  * \param tag used for debugging.
1030  * \param file Debug file name invoked from
1031  * \param line Debug line invoked from
1032  * \param func Debug function name invoked from
1033  *
1034  * \retval 0 on errors.
1035  * \retval 1 on success.
1036  */
1037 static int internal_ao2_link(struct ao2_container *self, void *obj_new, int flags, const char *tag, const char *file, int line, const char *func)
1038 {
1039         int res;
1040         enum ao2_lock_req orig_lock;
1041         struct ao2_container_node *node;
1042
1043         if (!INTERNAL_OBJ(obj_new) || !INTERNAL_OBJ(self)
1044                 || !self->v_table || !self->v_table->new_node || !self->v_table->insert) {
1045                 /* Sanity checks. */
1046                 ast_assert(0);
1047                 return 0;
1048         }
1049
1050         if (flags & OBJ_NOLOCK) {
1051                 orig_lock = adjust_lock(self, AO2_LOCK_REQ_WRLOCK, 1);
1052         } else {
1053                 ao2_wrlock(self);
1054                 orig_lock = AO2_LOCK_REQ_MUTEX;
1055         }
1056
1057         res = 0;
1058         node = self->v_table->new_node(self, obj_new, tag, file, line, func);
1059         if (node) {
1060 #if defined(AO2_DEBUG) && defined(AST_DEVMODE)
1061                 switch (self->v_table->type) {
1062                 case AO2_CONTAINER_RTTI_HASH:
1063                         if (!self->sort_fn) {
1064                                 /*
1065                                  * XXX chan_iax2 plays games with the hash function so we cannot
1066                                  * routinely do an integrity check on this type of container.
1067                                  * chan_iax2 should be changed to not abuse the hash function.
1068                                  */
1069                                 break;
1070                         }
1071                         /* Fall through. */
1072                 case AO2_CONTAINER_RTTI_RBTREE:
1073                         if (ao2_container_check(self, OBJ_NOLOCK)) {
1074                                 ast_log(LOG_ERROR, "Container integrity failed before insert.\n");
1075                         }
1076                         break;
1077                 }
1078 #endif  /* defined(AO2_DEBUG) && defined(AST_DEVMODE) */
1079                 /* Insert the new node. */
1080                 switch (self->v_table->insert(self, node)) {
1081                 case AO2_CONTAINER_INSERT_NODE_INSERTED:
1082                         node->is_linked = 1;
1083                         ast_atomic_fetchadd_int(&self->elements, 1);
1084 #if defined(AST_DEVMODE)
1085                         AO2_DEVMODE_STAT(++self->nodes);
1086                         switch (self->v_table->type) {
1087                         case AO2_CONTAINER_RTTI_HASH:
1088                                 hash_ao2_link_node_stat(self, node);
1089                                 break;
1090                         case AO2_CONTAINER_RTTI_RBTREE:
1091                                 break;
1092                         }
1093 #endif  /* defined(AST_DEVMODE) */
1094
1095                         res = 1;
1096                         break;
1097                 case AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED:
1098                         res = 1;
1099                         /* Fall through */
1100                 case AO2_CONTAINER_INSERT_NODE_REJECTED:
1101                         __ao2_ref(node, -1);
1102                         break;
1103                 }
1104 #if defined(AO2_DEBUG) && defined(AST_DEVMODE)
1105                 if (res) {
1106                         switch (self->v_table->type) {
1107                         case AO2_CONTAINER_RTTI_HASH:
1108                                 if (!self->sort_fn) {
1109                                         /*
1110                                          * XXX chan_iax2 plays games with the hash function so we cannot
1111                                          * routinely do an integrity check on this type of container.
1112                                          * chan_iax2 should be changed to not abuse the hash function.
1113                                          */
1114                                         break;
1115                                 }
1116                                 /* Fall through. */
1117                         case AO2_CONTAINER_RTTI_RBTREE:
1118                                 if (ao2_container_check(self, OBJ_NOLOCK)) {
1119                                         ast_log(LOG_ERROR, "Container integrity failed after insert.\n");
1120                                 }
1121                                 break;
1122                         }
1123                 }
1124 #endif  /* defined(AO2_DEBUG) && defined(AST_DEVMODE) */
1125         }
1126
1127         if (flags & OBJ_NOLOCK) {
1128                 adjust_lock(self, orig_lock, 0);
1129         } else {
1130                 ao2_unlock(self);
1131         }
1132
1133         return res;
1134 }
1135
1136 int __ao2_link_debug(struct ao2_container *c, void *obj_new, int flags, const char *tag, const char *file, int line, const char *func)
1137 {
1138         return internal_ao2_link(c, obj_new, flags, tag, file, line, func);
1139 }
1140
1141 int __ao2_link(struct ao2_container *c, void *obj_new, int flags)
1142 {
1143         return internal_ao2_link(c, obj_new, flags, NULL, __FILE__, __LINE__, __PRETTY_FUNCTION__);
1144 }
1145
1146 /*!
1147  * \brief another convenience function is a callback that matches on address
1148  */
1149 int ao2_match_by_addr(void *user_data, void *arg, int flags)
1150 {
1151         return (user_data == arg) ? (CMP_MATCH | CMP_STOP) : 0;
1152 }
1153
1154 /*
1155  * Unlink an object from the container
1156  * and destroy the associated * bucket_entry structure.
1157  */
1158 void *__ao2_unlink_debug(struct ao2_container *c, void *user_data, int flags,
1159         const char *tag, const char *file, int line, const char *func)
1160 {
1161         if (!INTERNAL_OBJ(user_data)) {
1162                 /* Sanity checks. */
1163                 ast_assert(0);
1164                 return NULL;
1165         }
1166
1167         flags &= ~OBJ_SEARCH_MASK;
1168         flags |= (OBJ_UNLINK | OBJ_SEARCH_OBJECT | OBJ_NODATA);
1169         __ao2_callback_debug(c, flags, ao2_match_by_addr, user_data, tag, file, line, func);
1170
1171         return NULL;
1172 }
1173
1174 void *__ao2_unlink(struct ao2_container *c, void *user_data, int flags)
1175 {
1176         if (!INTERNAL_OBJ(user_data)) {
1177                 /* Sanity checks. */
1178                 ast_assert(0);
1179                 return NULL;
1180         }
1181
1182         flags &= ~OBJ_SEARCH_MASK;
1183         flags |= (OBJ_UNLINK | OBJ_SEARCH_OBJECT | OBJ_NODATA);
1184         __ao2_callback(c, flags, ao2_match_by_addr, user_data);
1185
1186         return NULL;
1187 }
1188
1189 /*!
1190  * \brief special callback that matches all
1191  */
1192 static int cb_true(void *user_data, void *arg, int flags)
1193 {
1194         return CMP_MATCH;
1195 }
1196
1197 /*!
1198  * \brief similar to cb_true, but is an ao2_callback_data_fn instead
1199  */
1200 static int cb_true_data(void *user_data, void *arg, void *data, int flags)
1201 {
1202         return CMP_MATCH;
1203 }
1204
1205 /*! Allow enough room for container specific traversal state structs */
1206 #define AO2_TRAVERSAL_STATE_SIZE        100
1207
1208 /*!
1209  * \internal
1210  * \brief Traverse the container.  (internal)
1211  *
1212  * \param self Container to operate upon.
1213  * \param flags search_flags to control traversing the container
1214  * \param cb_fn Comparison callback function.
1215  * \param arg Comparison callback arg parameter.
1216  * \param data Data comparison callback data parameter.
1217  * \param type Type of comparison callback cb_fn.
1218  * \param tag used for debugging.
1219  * \param file Debug file name invoked from
1220  * \param line Debug line invoked from
1221  * \param func Debug function name invoked from
1222  *
1223  * \retval NULL on failure or no matching object found.
1224  *
1225  * \retval object found if OBJ_MULTIPLE is not set in the flags
1226  * parameter.
1227  *
1228  * \retval ao2_iterator pointer if OBJ_MULTIPLE is set in the
1229  * flags parameter.  The iterator must be destroyed with
1230  * ao2_iterator_destroy() when the caller no longer needs it.
1231  */
1232 static void *internal_ao2_traverse(struct ao2_container *self, enum search_flags flags,
1233         void *cb_fn, void *arg, void *data, enum ao2_callback_type type,
1234         const char *tag, const char *file, int line, const char *func)
1235 {
1236         void *ret;
1237         ao2_callback_fn *cb_default = NULL;
1238         ao2_callback_data_fn *cb_withdata = NULL;
1239         struct ao2_container_node *node;
1240         void *traversal_state;
1241
1242         enum ao2_lock_req orig_lock;
1243         struct ao2_container *multi_container = NULL;
1244         struct ao2_iterator *multi_iterator = NULL;
1245
1246         if (!INTERNAL_OBJ(self) || !self->v_table || !self->v_table->traverse_first
1247                 || !self->v_table->traverse_next) {
1248                 /* Sanity checks. */
1249                 ast_assert(0);
1250                 return NULL;
1251         }
1252
1253         /*
1254          * This logic is used so we can support OBJ_MULTIPLE with OBJ_NODATA
1255          * turned off.  This if statement checks for the special condition
1256          * where multiple items may need to be returned.
1257          */
1258         if ((flags & (OBJ_MULTIPLE | OBJ_NODATA)) == OBJ_MULTIPLE) {
1259                 /* we need to return an ao2_iterator with the results,
1260                  * as there could be more than one. the iterator will
1261                  * hold the only reference to a container that has all the
1262                  * matching objects linked into it, so when the iterator
1263                  * is destroyed, the container will be automatically
1264                  * destroyed as well.
1265                  */
1266                 multi_container = ao2_t_container_alloc_list(AO2_ALLOC_OPT_LOCK_NOLOCK, 0, NULL,
1267                         NULL, "OBJ_MULTIPLE return container creation");
1268                 if (!multi_container) {
1269                         return NULL;
1270                 }
1271                 if (!(multi_iterator = ast_calloc(1, sizeof(*multi_iterator)))) {
1272                         ao2_t_ref(multi_container, -1, "OBJ_MULTIPLE interator creation failed.");
1273                         return NULL;
1274                 }
1275         }
1276
1277         if (!cb_fn) {
1278                 /* Match everything if no callback match function provided. */
1279                 if (type == AO2_CALLBACK_WITH_DATA) {
1280                         cb_withdata = cb_true_data;
1281                 } else {
1282                         cb_default = cb_true;
1283                 }
1284         } else {
1285                 /*
1286                  * We do this here to avoid the per object casting penalty (even
1287                  * though that is probably optimized away anyway).
1288                  */
1289                 if (type == AO2_CALLBACK_WITH_DATA) {
1290                         cb_withdata = cb_fn;
1291                 } else {
1292                         cb_default = cb_fn;
1293                 }
1294         }
1295
1296         /* avoid modifications to the content */
1297         if (flags & OBJ_NOLOCK) {
1298                 if (flags & OBJ_UNLINK) {
1299                         orig_lock = adjust_lock(self, AO2_LOCK_REQ_WRLOCK, 1);
1300                 } else {
1301                         orig_lock = adjust_lock(self, AO2_LOCK_REQ_RDLOCK, 1);
1302                 }
1303         } else {
1304                 orig_lock = AO2_LOCK_REQ_MUTEX;
1305                 if (flags & OBJ_UNLINK) {
1306                         ao2_wrlock(self);
1307                 } else {
1308                         ao2_rdlock(self);
1309                 }
1310         }
1311
1312         /* Create a buffer for the traversal state. */
1313         traversal_state = alloca(AO2_TRAVERSAL_STATE_SIZE);
1314
1315         ret = NULL;
1316         for (node = self->v_table->traverse_first(self, flags, arg, traversal_state);
1317                 node;
1318                 node = self->v_table->traverse_next(self, traversal_state, node)) {
1319                 int match;
1320
1321                 /* Visit the current node. */
1322                 match = (CMP_MATCH | CMP_STOP);
1323                 if (type == AO2_CALLBACK_WITH_DATA) {
1324                         match &= cb_withdata(node->obj, arg, data, flags);
1325                 } else {
1326                         match &= cb_default(node->obj, arg, flags);
1327                 }
1328                 if (match == 0) {
1329                         /* no match, no stop, continue */
1330                         continue;
1331                 }
1332                 if (match == CMP_STOP) {
1333                         /* no match but stop, we are done */
1334                         break;
1335                 }
1336
1337                 /*
1338                  * CMP_MATCH is set here
1339                  *
1340                  * we found the object, performing operations according to flags
1341                  */
1342                 if (node->obj) {
1343                         /* The object is still in the container. */
1344                         if (!(flags & OBJ_NODATA)) {
1345                                 /*
1346                                  * We are returning the object, record the value.  It is
1347                                  * important to handle this case before the unlink.
1348                                  */
1349                                 if (multi_container) {
1350                                         /*
1351                                          * Link the object into the container that will hold the
1352                                          * results.
1353                                          */
1354                                         if (tag) {
1355                                                 __ao2_link_debug(multi_container, node->obj, flags,
1356                                                         tag, file, line, func);
1357                                         } else {
1358                                                 __ao2_link(multi_container, node->obj, flags);
1359                                         }
1360                                 } else {
1361                                         ret = node->obj;
1362                                         /* Returning a single object. */
1363                                         if (!(flags & OBJ_UNLINK)) {
1364                                                 /*
1365                                                  * Bump the ref count since we are not going to unlink and
1366                                                  * transfer the container's object ref to the returned object.
1367                                                  */
1368                                                 if (tag) {
1369                                                         __ao2_ref_debug(ret, 1, tag, file, line, func);
1370                                                 } else {
1371                                                         ao2_t_ref(ret, 1, "Traversal found object");
1372                                                 }
1373                                         }
1374                                 }
1375                         }
1376
1377                         if (flags & OBJ_UNLINK) {
1378                                 /* update number of elements */
1379                                 ast_atomic_fetchadd_int(&self->elements, -1);
1380 #if defined(AST_DEVMODE)
1381                                 {
1382                                         int empty = self->nodes - self->elements;
1383
1384                                         if (self->max_empty_nodes < empty) {
1385                                                 self->max_empty_nodes = empty;
1386                                         }
1387                                 }
1388                                 switch (self->v_table->type) {
1389                                 case AO2_CONTAINER_RTTI_HASH:
1390                                         hash_ao2_unlink_node_stat(self, node);
1391                                         break;
1392                                 case AO2_CONTAINER_RTTI_RBTREE:
1393                                         break;
1394                                 }
1395 #endif  /* defined(AST_DEVMODE) */
1396
1397                                 /*
1398                                  * - When unlinking and not returning the result, OBJ_NODATA is
1399                                  * set, the ref from the container must be decremented.
1400                                  *
1401                                  * - When unlinking with a multi_container the ref from the
1402                                  * original container must be decremented.  This is because the
1403                                  * result is returned in a new container that already holds its
1404                                  * own ref for the object.
1405                                  *
1406                                  * If the ref from the original container is not accounted for
1407                                  * here a memory leak occurs.
1408                                  */
1409                                 if (multi_container || (flags & OBJ_NODATA)) {
1410                                         if (tag) {
1411                                                 __ao2_ref_debug(node->obj, -1, tag, file, line, func);
1412                                         } else {
1413                                                 ao2_t_ref(node->obj, -1, "Unlink container obj reference.");
1414                                         }
1415                                 }
1416                                 node->obj = NULL;
1417
1418                                 /* Unref the node from the container. */
1419                                 __ao2_ref(node, -1);
1420                         }
1421                 }
1422
1423                 if ((match & CMP_STOP) || !(flags & OBJ_MULTIPLE)) {
1424                         /* We found our only (or last) match, so we are done */
1425                         break;
1426                 }
1427         }
1428         if (self->v_table->traverse_cleanup) {
1429                 self->v_table->traverse_cleanup(traversal_state);
1430         }
1431         if (node) {
1432                 /* Unref the node from self->v_table->traverse_first/traverse_next() */
1433                 __ao2_ref(node, -1);
1434         }
1435
1436         if (flags & OBJ_NOLOCK) {
1437                 adjust_lock(self, orig_lock, 0);
1438         } else {
1439                 ao2_unlock(self);
1440         }
1441
1442         /* if multi_container was created, we are returning multiple objects */
1443         if (multi_container) {
1444                 *multi_iterator = ao2_iterator_init(multi_container,
1445                         AO2_ITERATOR_UNLINK | AO2_ITERATOR_MALLOCD);
1446                 ao2_t_ref(multi_container, -1,
1447                         "OBJ_MULTIPLE for multiple objects traversal complete.");
1448                 return multi_iterator;
1449         } else {
1450                 return ret;
1451         }
1452 }
1453
1454 void *__ao2_callback_debug(struct ao2_container *c, enum search_flags flags,
1455         ao2_callback_fn *cb_fn, void *arg, const char *tag, const char *file, int line,
1456         const char *func)
1457 {
1458         return internal_ao2_traverse(c, flags, cb_fn, arg, NULL, AO2_CALLBACK_DEFAULT, tag, file, line, func);
1459 }
1460
1461 void *__ao2_callback(struct ao2_container *c, enum search_flags flags,
1462         ao2_callback_fn *cb_fn, void *arg)
1463 {
1464         return internal_ao2_traverse(c, flags, cb_fn, arg, NULL, AO2_CALLBACK_DEFAULT, NULL, NULL, 0, NULL);
1465 }
1466
1467 void *__ao2_callback_data_debug(struct ao2_container *c, enum search_flags flags,
1468         ao2_callback_data_fn *cb_fn, void *arg, void *data, const char *tag, const char *file,
1469         int line, const char *func)
1470 {
1471         return internal_ao2_traverse(c, flags, cb_fn, arg, data, AO2_CALLBACK_WITH_DATA, tag, file, line, func);
1472 }
1473
1474 void *__ao2_callback_data(struct ao2_container *c, enum search_flags flags,
1475         ao2_callback_data_fn *cb_fn, void *arg, void *data)
1476 {
1477         return internal_ao2_traverse(c, flags, cb_fn, arg, data, AO2_CALLBACK_WITH_DATA, NULL, NULL, 0, NULL);
1478 }
1479
1480 /*!
1481  * the find function just invokes the default callback with some reasonable flags.
1482  */
1483 void *__ao2_find_debug(struct ao2_container *c, const void *arg, enum search_flags flags,
1484         const char *tag, const char *file, int line, const char *func)
1485 {
1486         void *arged = (void *) arg;/* Done to avoid compiler const warning */
1487
1488         if (!c) {
1489                 /* Sanity checks. */
1490                 ast_assert(0);
1491                 return NULL;
1492         }
1493         return __ao2_callback_debug(c, flags, c->cmp_fn, arged, tag, file, line, func);
1494 }
1495
1496 void *__ao2_find(struct ao2_container *c, const void *arg, enum search_flags flags)
1497 {
1498         void *arged = (void *) arg;/* Done to avoid compiler const warning */
1499
1500         if (!c) {
1501                 /* Sanity checks. */
1502                 ast_assert(0);
1503                 return NULL;
1504         }
1505         return __ao2_callback(c, flags, c->cmp_fn, arged);
1506 }
1507
1508 /*!
1509  * initialize an iterator so we start from the first object
1510  */
1511 struct ao2_iterator ao2_iterator_init(struct ao2_container *c, int flags)
1512 {
1513         struct ao2_iterator a = {
1514                 .c = c,
1515                 .flags = flags
1516         };
1517
1518         ao2_t_ref(c, +1, "Init iterator with container.");
1519
1520         return a;
1521 }
1522
1523 void ao2_iterator_restart(struct ao2_iterator *iter)
1524 {
1525         /* Release the last container node reference if we have one. */
1526         if (iter->last_node) {
1527                 enum ao2_lock_req orig_lock;
1528
1529                 /*
1530                  * Do a read lock in case the container node unref does not
1531                  * destroy the node.  If the container node is destroyed then
1532                  * the lock will be upgraded to a write lock.
1533                  */
1534                 if (iter->flags & AO2_ITERATOR_DONTLOCK) {
1535                         orig_lock = adjust_lock(iter->c, AO2_LOCK_REQ_RDLOCK, 1);
1536                 } else {
1537                         orig_lock = AO2_LOCK_REQ_MUTEX;
1538                         ao2_rdlock(iter->c);
1539                 }
1540
1541                 __ao2_ref(iter->last_node, -1);
1542                 iter->last_node = NULL;
1543
1544                 if (iter->flags & AO2_ITERATOR_DONTLOCK) {
1545                         adjust_lock(iter->c, orig_lock, 0);
1546                 } else {
1547                         ao2_unlock(iter->c);
1548                 }
1549         }
1550
1551         /* The iteration is no longer complete. */
1552         iter->complete = 0;
1553 }
1554
1555 void ao2_iterator_destroy(struct ao2_iterator *iter)
1556 {
1557         /* Release any last container node reference. */
1558         ao2_iterator_restart(iter);
1559
1560         /* Release the iterated container reference. */
1561         ao2_t_ref(iter->c, -1, "Unref iterator in ao2_iterator_destroy");
1562         iter->c = NULL;
1563
1564         /* Free the malloced iterator. */
1565         if (iter->flags & AO2_ITERATOR_MALLOCD) {
1566                 ast_free(iter);
1567         }
1568 }
1569
1570 void ao2_iterator_cleanup(struct ao2_iterator *iter)
1571 {
1572         if (iter) {
1573                 ao2_iterator_destroy(iter);
1574         }
1575 }
1576
1577 /*
1578  * move to the next element in the container.
1579  */
1580 static void *internal_ao2_iterator_next(struct ao2_iterator *iter, const char *tag, const char *file, int line, const char *func)
1581 {
1582         enum ao2_lock_req orig_lock;
1583         struct ao2_container_node *node;
1584         void *ret;
1585
1586         if (!INTERNAL_OBJ(iter->c) || !iter->c->v_table || !iter->c->v_table->iterator_next) {
1587                 /* Sanity checks. */
1588                 ast_assert(0);
1589                 return NULL;
1590         }
1591
1592         if (iter->complete) {
1593                 /* Don't return any more objects. */
1594                 return NULL;
1595         }
1596
1597         if (iter->flags & AO2_ITERATOR_DONTLOCK) {
1598                 if (iter->flags & AO2_ITERATOR_UNLINK) {
1599                         orig_lock = adjust_lock(iter->c, AO2_LOCK_REQ_WRLOCK, 1);
1600                 } else {
1601                         orig_lock = adjust_lock(iter->c, AO2_LOCK_REQ_RDLOCK, 1);
1602                 }
1603         } else {
1604                 orig_lock = AO2_LOCK_REQ_MUTEX;
1605                 if (iter->flags & AO2_ITERATOR_UNLINK) {
1606                         ao2_wrlock(iter->c);
1607                 } else {
1608                         ao2_rdlock(iter->c);
1609                 }
1610         }
1611
1612         node = iter->c->v_table->iterator_next(iter->c, iter->last_node, iter->flags);
1613         if (node) {
1614                 ret = node->obj;
1615
1616                 if (iter->flags & AO2_ITERATOR_UNLINK) {
1617                         /* update number of elements */
1618                         ast_atomic_fetchadd_int(&iter->c->elements, -1);
1619 #if defined(AST_DEVMODE)
1620                         {
1621                                 int empty = iter->c->nodes - iter->c->elements;
1622
1623                                 if (iter->c->max_empty_nodes < empty) {
1624                                         iter->c->max_empty_nodes = empty;
1625                                 }
1626                         }
1627                         switch (iter->c->v_table->type) {
1628                         case AO2_CONTAINER_RTTI_HASH:
1629                                 hash_ao2_unlink_node_stat(iter->c, node);
1630                                 break;
1631                         case AO2_CONTAINER_RTTI_RBTREE:
1632                                 break;
1633                         }
1634 #endif  /* defined(AST_DEVMODE) */
1635
1636                         /* Transfer the object ref from the container to the returned object. */
1637                         node->obj = NULL;
1638
1639                         /* Transfer the container's node ref to the iterator. */
1640                 } else {
1641                         /* Bump ref of returned object */
1642                         if (tag) {
1643                                 __ao2_ref_debug(ret, +1, tag, file, line, func);
1644                         } else {
1645                                 ao2_t_ref(ret, +1, "Next iterator object.");
1646                         }
1647
1648                         /* Bump the container's node ref for the iterator. */
1649                         __ao2_ref(node, +1);
1650                 }
1651         } else {
1652                 /* The iteration has completed. */
1653                 iter->complete = 1;
1654                 ret = NULL;
1655         }
1656
1657         /* Replace the iterator's node */
1658         if (iter->last_node) {
1659                 __ao2_ref(iter->last_node, -1);
1660         }
1661         iter->last_node = node;
1662
1663         if (iter->flags & AO2_ITERATOR_DONTLOCK) {
1664                 adjust_lock(iter->c, orig_lock, 0);
1665         } else {
1666                 ao2_unlock(iter->c);
1667         }
1668
1669         return ret;
1670 }
1671
1672 void *__ao2_iterator_next_debug(struct ao2_iterator *iter, const char *tag, const char *file, int line, const char *func)
1673 {
1674         return internal_ao2_iterator_next(iter, tag, file, line, func);
1675 }
1676
1677 void *__ao2_iterator_next(struct ao2_iterator *iter)
1678 {
1679         return internal_ao2_iterator_next(iter, NULL, __FILE__, __LINE__, __PRETTY_FUNCTION__);
1680 }
1681
1682 int ao2_iterator_count(struct ao2_iterator *iter)
1683 {
1684         return ao2_container_count(iter->c);
1685 }
1686
1687 static void container_destruct(void *_c)
1688 {
1689         struct ao2_container *c = _c;
1690
1691         /* Unlink any stored objects in the container. */
1692         c->destroying = 1;
1693         __ao2_callback(c, OBJ_UNLINK | OBJ_NODATA | OBJ_MULTIPLE, NULL, NULL);
1694
1695         /* Perform any extra container cleanup. */
1696         if (c->v_table && c->v_table->destroy) {
1697                 c->v_table->destroy(c);
1698         }
1699
1700 #ifdef AO2_DEBUG
1701         ast_atomic_fetchadd_int(&ao2.total_containers, -1);
1702 #endif
1703 }
1704
1705 static void container_destruct_debug(void *_c)
1706 {
1707         struct ao2_container *c = _c;
1708
1709         /* Unlink any stored objects in the container. */
1710         c->destroying = 1;
1711         __ao2_callback_debug(c, OBJ_UNLINK | OBJ_NODATA | OBJ_MULTIPLE, NULL, NULL,
1712                 "container_destruct_debug called", __FILE__, __LINE__, __PRETTY_FUNCTION__);
1713
1714         /* Perform any extra container cleanup. */
1715         if (c->v_table && c->v_table->destroy) {
1716                 c->v_table->destroy(c);
1717         }
1718
1719 #ifdef AO2_DEBUG
1720         ast_atomic_fetchadd_int(&ao2.total_containers, -1);
1721 #endif
1722 }
1723
1724 /*!
1725  * \internal
1726  * \brief Put obj into the arg container.
1727  * \since 11.0
1728  *
1729  * \param obj  pointer to the (user-defined part) of an object.
1730  * \param arg callback argument from ao2_callback()
1731  * \param flags flags from ao2_callback()
1732  *
1733  * \retval 0 on success.
1734  * \retval CMP_STOP|CMP_MATCH on error.
1735  */
1736 static int dup_obj_cb(void *obj, void *arg, int flags)
1737 {
1738         struct ao2_container *dest = arg;
1739
1740         return __ao2_link(dest, obj, OBJ_NOLOCK) ? 0 : (CMP_MATCH | CMP_STOP);
1741 }
1742
1743 int ao2_container_dup(struct ao2_container *dest, struct ao2_container *src, enum search_flags flags)
1744 {
1745         void *obj;
1746         int res = 0;
1747
1748         if (!(flags & OBJ_NOLOCK)) {
1749                 ao2_rdlock(src);
1750                 ao2_wrlock(dest);
1751         }
1752         obj = __ao2_callback(src, OBJ_NOLOCK, dup_obj_cb, dest);
1753         if (obj) {
1754                 /* Failed to put this obj into the dest container. */
1755                 ao2_t_ref(obj, -1, "Failed to put this object into the dest container.");
1756
1757                 /* Remove all items from the dest container. */
1758                 __ao2_callback(dest, OBJ_NOLOCK | OBJ_UNLINK | OBJ_NODATA | OBJ_MULTIPLE, NULL,
1759                         NULL);
1760                 res = -1;
1761         }
1762         if (!(flags & OBJ_NOLOCK)) {
1763                 ao2_unlock(dest);
1764                 ao2_unlock(src);
1765         }
1766
1767         return res;
1768 }
1769
1770 struct ao2_container *__ao2_container_clone(struct ao2_container *orig, enum search_flags flags)
1771 {
1772         struct ao2_container *clone;
1773         int failed;
1774
1775         /* Create the clone container with the same properties as the original. */
1776         if (!INTERNAL_OBJ(orig) || !orig->v_table || !orig->v_table->alloc_empty_clone) {
1777                 /* Sanity checks. */
1778                 ast_assert(0);
1779                 return NULL;
1780         }
1781         clone = orig->v_table->alloc_empty_clone(orig);
1782         if (!clone) {
1783                 return NULL;
1784         }
1785
1786         if (flags & OBJ_NOLOCK) {
1787                 ao2_wrlock(clone);
1788         }
1789         failed = ao2_container_dup(clone, orig, flags);
1790         if (flags & OBJ_NOLOCK) {
1791                 ao2_unlock(clone);
1792         }
1793         if (failed) {
1794                 /* Object copy into the clone container failed. */
1795                 ao2_t_ref(clone, -1, "Clone creation failed.");
1796                 clone = NULL;
1797         }
1798         return clone;
1799 }
1800
1801 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)
1802 {
1803         struct ao2_container *clone;
1804         int failed;
1805
1806         /* Create the clone container with the same properties as the original. */
1807         if (!INTERNAL_OBJ(orig) || !orig->v_table || !orig->v_table->alloc_empty_clone_debug) {
1808                 /* Sanity checks. */
1809                 ast_assert(0);
1810                 return NULL;
1811         }
1812         clone = orig->v_table->alloc_empty_clone_debug(orig, tag, file, line, func, ref_debug);
1813         if (!clone) {
1814                 return NULL;
1815         }
1816
1817         if (flags & OBJ_NOLOCK) {
1818                 ao2_wrlock(clone);
1819         }
1820         failed = ao2_container_dup(clone, orig, flags);
1821         if (flags & OBJ_NOLOCK) {
1822                 ao2_unlock(clone);
1823         }
1824         if (failed) {
1825                 /* Object copy into the clone container failed. */
1826                 if (ref_debug) {
1827                         __ao2_ref_debug(clone, -1, tag, file, line, func);
1828                 } else {
1829                         ao2_t_ref(clone, -1, "Clone creation failed.");
1830                 }
1831                 clone = NULL;
1832         }
1833         return clone;
1834 }
1835
1836 void ao2_container_dump(struct ao2_container *self, enum search_flags flags, const char *name, void *where, ao2_prnt_fn *prnt, ao2_prnt_obj_fn *prnt_obj)
1837 {
1838         if (!INTERNAL_OBJ(self) || !self->v_table) {
1839                 prnt(where, "Invalid container\n");
1840                 ast_assert(0);
1841                 return;
1842         }
1843
1844         if (!(flags & OBJ_NOLOCK)) {
1845                 ao2_rdlock(self);
1846         }
1847         if (name) {
1848                 prnt(where, "Container name: %s\n", name);
1849         }
1850 #if defined(AST_DEVMODE)
1851         if (self->v_table->dump) {
1852                 self->v_table->dump(self, where, prnt, prnt_obj);
1853         } else
1854 #endif  /* defined(AST_DEVMODE) */
1855         {
1856                 prnt(where, "Container dump not available.\n");
1857         }
1858         if (!(flags & OBJ_NOLOCK)) {
1859                 ao2_unlock(self);
1860         }
1861 }
1862
1863 void ao2_container_stats(struct ao2_container *self, enum search_flags flags, const char *name, void *where, ao2_prnt_fn *prnt)
1864 {
1865         if (!INTERNAL_OBJ(self) || !self->v_table) {
1866                 prnt(where, "Invalid container\n");
1867                 ast_assert(0);
1868                 return;
1869         }
1870
1871         if (!(flags & OBJ_NOLOCK)) {
1872                 ao2_rdlock(self);
1873         }
1874         if (name) {
1875                 prnt(where, "Container name: %s\n", name);
1876         }
1877         prnt(where, "Number of objects: %d\n", self->elements);
1878 #if defined(AST_DEVMODE)
1879         prnt(where, "Number of nodes: %d\n", self->nodes);
1880         prnt(where, "Number of empty nodes: %d\n", self->nodes - self->elements);
1881         /*
1882          * XXX
1883          * If the max_empty_nodes count gets out of single digits you
1884          * likely have a code path where ao2_iterator_destroy() is not
1885          * called.
1886          *
1887          * Empty nodes do not harm the container but they do make
1888          * container operations less efficient.
1889          */
1890         prnt(where, "Maximum empty nodes: %d\n", self->max_empty_nodes);
1891         if (self->v_table->stats) {
1892                 self->v_table->stats(self, where, prnt);
1893         }
1894 #endif  /* defined(AST_DEVMODE) */
1895         if (!(flags & OBJ_NOLOCK)) {
1896                 ao2_unlock(self);
1897         }
1898 }
1899
1900 int ao2_container_check(struct ao2_container *self, enum search_flags flags)
1901 {
1902         int res = 0;
1903
1904         if (!INTERNAL_OBJ(self) || !self->v_table) {
1905                 /* Sanity checks. */
1906                 ast_assert(0);
1907                 return -1;
1908         }
1909 #if defined(AST_DEVMODE)
1910         if (!self->v_table->integrity) {
1911                 /* No ingetrigy check available.  Assume container is ok. */
1912                 return 0;
1913         }
1914
1915         if (!(flags & OBJ_NOLOCK)) {
1916                 ao2_rdlock(self);
1917         }
1918         res = self->v_table->integrity(self);
1919         if (!(flags & OBJ_NOLOCK)) {
1920                 ao2_unlock(self);
1921         }
1922 #endif  /* defined(AST_DEVMODE) */
1923         return res;
1924 }
1925
1926 /*!
1927  * A structure to create a linked list of entries,
1928  * used within a bucket.
1929  */
1930 struct hash_bucket_node {
1931         /*!
1932          * \brief Items common to all container nodes.
1933          * \note Must be first in the specific node struct.
1934          */
1935         struct ao2_container_node common;
1936         /*! Next node links in the list. */
1937         AST_DLLIST_ENTRY(hash_bucket_node) links;
1938         /*! Hash bucket holding the node. */
1939         int my_bucket;
1940 };
1941
1942 struct hash_bucket {
1943         /*! List of objects held in the bucket. */
1944         AST_DLLIST_HEAD_NOLOCK(, hash_bucket_node) list;
1945 #if defined(AST_DEVMODE)
1946         /*! Number of elements currently in the bucket. */
1947         int elements;
1948         /*! Maximum number of elements in the bucket. */
1949         int max_elements;
1950 #endif  /* defined(AST_DEVMODE) */
1951 };
1952
1953 /*!
1954  * A hash container in addition to values common to all
1955  * container types, stores the hash callback function, the
1956  * number of hash buckets, and the hash bucket heads.
1957  */
1958 struct ao2_container_hash {
1959         /*!
1960          * \brief Items common to all containers.
1961          * \note Must be first in the specific container struct.
1962          */
1963         struct ao2_container common;
1964         ao2_hash_fn *hash_fn;
1965         /*! Number of hash buckets in this container. */
1966         int n_buckets;
1967         /*! Hash bucket array of n_buckets.  Variable size. */
1968         struct hash_bucket buckets[0];
1969 };
1970
1971 /*!
1972  * \internal
1973  * \brief Create an empty copy of this container.
1974  * \since 12.0.0
1975  *
1976  * \param self Container to operate upon.
1977  *
1978  * \retval empty-clone-container on success.
1979  * \retval NULL on error.
1980  */
1981 static struct ao2_container *hash_ao2_alloc_empty_clone(struct ao2_container_hash *self)
1982 {
1983         struct astobj2 *orig_obj;
1984         unsigned int ao2_options;
1985
1986         /* Get container ao2 options. */
1987         orig_obj = INTERNAL_OBJ(self);
1988         if (!orig_obj) {
1989                 return NULL;
1990         }
1991         ao2_options = orig_obj->priv_data.options;
1992
1993         return ao2_t_container_alloc_hash(ao2_options, self->common.options, self->n_buckets,
1994                 self->hash_fn, self->common.sort_fn, self->common.cmp_fn, "Clone hash container");
1995 }
1996
1997 /*!
1998  * \internal
1999  * \brief Create an empty copy of this container. (Debug version)
2000  * \since 12.0.0
2001  *
2002  * \param self Container to operate upon.
2003  * \param tag used for debugging.
2004  * \param file Debug file name invoked from
2005  * \param line Debug line invoked from
2006  * \param func Debug function name invoked from
2007  * \param ref_debug TRUE if to output a debug reference message.
2008  *
2009  * \retval empty-clone-container on success.
2010  * \retval NULL on error.
2011  */
2012 static struct ao2_container *hash_ao2_alloc_empty_clone_debug(struct ao2_container_hash *self, const char *tag, const char *file, int line, const char *func, int ref_debug)
2013 {
2014         struct astobj2 *orig_obj;
2015         unsigned int ao2_options;
2016
2017         /* Get container ao2 options. */
2018         orig_obj = INTERNAL_OBJ(self);
2019         if (!orig_obj) {
2020                 return NULL;
2021         }
2022         ao2_options = orig_obj->priv_data.options;
2023
2024         return __ao2_container_alloc_hash_debug(ao2_options, self->common.options,
2025                 self->n_buckets, self->hash_fn, self->common.sort_fn, self->common.cmp_fn,
2026                 tag, file, line, func, ref_debug);
2027 }
2028
2029 /*!
2030  * \internal
2031  * \brief Destroy a hash container list node.
2032  * \since 12.0.0
2033  *
2034  * \param v_doomed Container node to destroy.
2035  *
2036  * \details
2037  * The container node unlinks itself from the container as part
2038  * of its destruction.  The node must be destroyed while the
2039  * container is already locked.
2040  *
2041  * \note The container must be locked when the node is
2042  * unreferenced.
2043  *
2044  * \return Nothing
2045  */
2046 static void hash_ao2_node_destructor(void *v_doomed)
2047 {
2048         struct hash_bucket_node *doomed = v_doomed;
2049
2050         if (doomed->common.is_linked) {
2051                 struct ao2_container_hash *my_container;
2052                 struct hash_bucket *bucket;
2053
2054                 /*
2055                  * Promote to write lock if not already there.  Since
2056                  * adjust_lock() can potentially release and block waiting for a
2057                  * write lock, care must be taken to ensure that node references
2058                  * are released before releasing the container references.
2059                  *
2060                  * Node references held by an iterator can only be held while
2061                  * the iterator also holds a reference to the container.  These
2062                  * node references must be unreferenced before the container can
2063                  * be unreferenced to ensure that the node will not get a
2064                  * negative reference and the destructor called twice for the
2065                  * same node.
2066                  */
2067                 my_container = (struct ao2_container_hash *) doomed->common.my_container;
2068                 adjust_lock(my_container, AO2_LOCK_REQ_WRLOCK, 1);
2069
2070 #if defined(AO2_DEBUG) && defined(AST_DEVMODE)
2071                 /*
2072                  * XXX chan_iax2 plays games with the hash function so we cannot
2073                  * routinely do an integrity check on this type of container.
2074                  * chan_iax2 should be changed to not abuse the hash function.
2075                  */
2076                 if (!my_container->common.destroying
2077                         && my_container->common.sort_fn
2078                         && ao2_container_check(doomed->common.my_container, OBJ_NOLOCK)) {
2079                         ast_log(LOG_ERROR, "Container integrity failed before node deletion.\n");
2080                 }
2081 #endif  /* defined(AO2_DEBUG) && defined(AST_DEVMODE) */
2082                 bucket = &my_container->buckets[doomed->my_bucket];
2083                 AST_DLLIST_REMOVE(&bucket->list, doomed, links);
2084                 AO2_DEVMODE_STAT(--my_container->common.nodes);
2085         }
2086
2087         /*
2088          * We could have an object in the node if the container is being
2089          * destroyed or the node had not been linked in yet.
2090          */
2091         if (doomed->common.obj) {
2092                 ao2_t_ref(doomed->common.obj, -1, "Container node destruction");
2093                 doomed->common.obj = NULL;
2094         }
2095 }
2096
2097 /*!
2098  * \internal
2099  * \brief Create a new container node.
2100  * \since 12.0.0
2101  *
2102  * \param self Container to operate upon.
2103  * \param obj_new Object to put into the node.
2104  * \param tag used for debugging.
2105  * \param file Debug file name invoked from
2106  * \param line Debug line invoked from
2107  * \param func Debug function name invoked from
2108  *
2109  * \retval initialized-node on success.
2110  * \retval NULL on error.
2111  */
2112 static struct hash_bucket_node *hash_ao2_new_node(struct ao2_container_hash *self, void *obj_new, const char *tag, const char *file, int line, const char *func)
2113 {
2114         struct hash_bucket_node *node;
2115         int i;
2116
2117         node = __ao2_alloc(sizeof(*node), hash_ao2_node_destructor, AO2_ALLOC_OPT_LOCK_NOLOCK);
2118         if (!node) {
2119                 return NULL;
2120         }
2121
2122         i = abs(self->hash_fn(obj_new, OBJ_SEARCH_OBJECT));
2123         i %= self->n_buckets;
2124
2125         if (tag) {
2126                 __ao2_ref_debug(obj_new, +1, tag, file, line, func);
2127         } else {
2128                 ao2_t_ref(obj_new, +1, "Container node creation");
2129         }
2130         node->common.obj = obj_new;
2131         node->common.my_container = (struct ao2_container *) self;
2132         node->my_bucket = i;
2133
2134         return node;
2135 }
2136
2137 /*!
2138  * \internal
2139  * \brief Insert a node into this container.
2140  * \since 12.0.0
2141  *
2142  * \param self Container to operate upon.
2143  * \param node Container node to insert into the container.
2144  *
2145  * \return enum ao2_container_insert value.
2146  */
2147 static enum ao2_container_insert hash_ao2_insert_node(struct ao2_container_hash *self, struct hash_bucket_node *node)
2148 {
2149         int cmp;
2150         struct hash_bucket *bucket;
2151         struct hash_bucket_node *cur;
2152         ao2_sort_fn *sort_fn;
2153         uint32_t options;
2154
2155         bucket = &self->buckets[node->my_bucket];
2156         sort_fn = self->common.sort_fn;
2157         options = self->common.options;
2158
2159         if (options & AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN) {
2160                 if (sort_fn) {
2161                         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&bucket->list, cur, links) {
2162                                 cmp = sort_fn(cur->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
2163                                 if (cmp > 0) {
2164                                         continue;
2165                                 }
2166                                 if (cmp < 0) {
2167                                         AST_DLLIST_INSERT_AFTER_CURRENT(node, links);
2168                                         return AO2_CONTAINER_INSERT_NODE_INSERTED;
2169                                 }
2170                                 switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
2171                                 default:
2172                                 case AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW:
2173                                         break;
2174                                 case AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT:
2175                                         /* Reject all objects with the same key. */
2176                                         return AO2_CONTAINER_INSERT_NODE_REJECTED;
2177                                 case AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT:
2178                                         if (cur->common.obj == node->common.obj) {
2179                                                 /* Reject inserting the same object */
2180                                                 return AO2_CONTAINER_INSERT_NODE_REJECTED;
2181                                         }
2182                                         break;
2183                                 case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE:
2184                                         SWAP(cur->common.obj, node->common.obj);
2185                                         return AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED;
2186                                 }
2187                         }
2188                         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END;
2189                 }
2190                 AST_DLLIST_INSERT_HEAD(&bucket->list, node, links);
2191         } else {
2192                 if (sort_fn) {
2193                         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&bucket->list, cur, links) {
2194                                 cmp = sort_fn(cur->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
2195                                 if (cmp < 0) {
2196                                         continue;
2197                                 }
2198                                 if (cmp > 0) {
2199                                         AST_DLLIST_INSERT_BEFORE_CURRENT(node, links);
2200                                         return AO2_CONTAINER_INSERT_NODE_INSERTED;
2201                                 }
2202                                 switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
2203                                 default:
2204                                 case AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW:
2205                                         break;
2206                                 case AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT:
2207                                         /* Reject all objects with the same key. */
2208                                         return AO2_CONTAINER_INSERT_NODE_REJECTED;
2209                                 case AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT:
2210                                         if (cur->common.obj == node->common.obj) {
2211                                                 /* Reject inserting the same object */
2212                                                 return AO2_CONTAINER_INSERT_NODE_REJECTED;
2213                                         }
2214                                         break;
2215                                 case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE:
2216                                         SWAP(cur->common.obj, node->common.obj);
2217                                         return AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED;
2218                                 }
2219                         }
2220                         AST_DLLIST_TRAVERSE_SAFE_END;
2221                 }
2222                 AST_DLLIST_INSERT_TAIL(&bucket->list, node, links);
2223         }
2224         return AO2_CONTAINER_INSERT_NODE_INSERTED;
2225 }
2226
2227 /*! Traversal state to restart a hash container traversal. */
2228 struct hash_traversal_state {
2229         /*! Active sort function in the traversal if not NULL. */
2230         ao2_sort_fn *sort_fn;
2231         /*! Saved comparison callback arg pointer. */
2232         void *arg;
2233         /*! Starting hash bucket */
2234         int bucket_start;
2235         /*! Stopping hash bucket */
2236         int bucket_last;
2237         /*! Saved search flags to control traversing the container. */
2238         enum search_flags flags;
2239         /*! TRUE if it is a descending search */
2240         unsigned int descending:1;
2241 };
2242
2243 struct hash_traversal_state_check {
2244         /*
2245          * If we have a division by zero compile error here then there
2246          * is not enough room for the state.  Increase AO2_TRAVERSAL_STATE_SIZE.
2247          */
2248         char check[1 / (AO2_TRAVERSAL_STATE_SIZE / sizeof(struct hash_traversal_state))];
2249 };
2250
2251 /*!
2252  * \internal
2253  * \brief Find the first hash container node in a traversal.
2254  * \since 12.0.0
2255  *
2256  * \param self Container to operate upon.
2257  * \param flags search_flags to control traversing the container
2258  * \param arg Comparison callback arg parameter.
2259  * \param state Traversal state to restart hash container traversal.
2260  *
2261  * \retval node-ptr of found node (Reffed).
2262  * \retval NULL when no node found.
2263  */
2264 static struct hash_bucket_node *hash_ao2_find_first(struct ao2_container_hash *self, enum search_flags flags, void *arg, struct hash_traversal_state *state)
2265 {
2266         struct hash_bucket_node *node;
2267         int bucket_cur;
2268         int cmp;
2269
2270         memset(state, 0, sizeof(*state));
2271         state->arg = arg;
2272         state->flags = flags;
2273
2274         /* Determine traversal order. */
2275         switch (flags & OBJ_ORDER_MASK) {
2276         case OBJ_ORDER_POST:
2277         case OBJ_ORDER_DESCENDING:
2278                 state->descending = 1;
2279                 break;
2280         case OBJ_ORDER_PRE:
2281         case OBJ_ORDER_ASCENDING:
2282         default:
2283                 break;
2284         }
2285
2286         /*
2287          * If lookup by pointer or search key, run the hash and optional
2288          * sort functions.  Otherwise, traverse the whole container.
2289          */
2290         switch (flags & OBJ_SEARCH_MASK) {
2291         case OBJ_SEARCH_OBJECT:
2292         case OBJ_SEARCH_KEY:
2293                 /* we know hash can handle this case */
2294                 bucket_cur = abs(self->hash_fn(arg, flags & OBJ_SEARCH_MASK));
2295                 bucket_cur %= self->n_buckets;
2296                 state->sort_fn = self->common.sort_fn;
2297                 break;
2298         case OBJ_SEARCH_PARTIAL_KEY:
2299                 /* scan all buckets for partial key matches */
2300                 bucket_cur = -1;
2301                 state->sort_fn = self->common.sort_fn;
2302                 break;
2303         default:
2304                 /* don't know, let's scan all buckets */
2305                 bucket_cur = -1;
2306                 state->sort_fn = NULL;
2307                 break;
2308         }
2309
2310         if (state->descending) {
2311                 /*
2312                  * Determine the search boundaries of a descending traversal.
2313                  *
2314                  * bucket_cur downto state->bucket_last
2315                  */
2316                 if (bucket_cur < 0) {
2317                         bucket_cur = self->n_buckets - 1;
2318                         state->bucket_last = 0;
2319                 } else {
2320                         state->bucket_last = bucket_cur;
2321                 }
2322                 state->bucket_start = bucket_cur;
2323
2324                 /* For each bucket */
2325                 for (; state->bucket_last <= bucket_cur; --bucket_cur) {
2326                         /* For each node in the bucket. */
2327                         for (node = AST_DLLIST_LAST(&self->buckets[bucket_cur].list);
2328                                 node;
2329                                 node = AST_DLLIST_PREV(node, links)) {
2330                                 if (!node->common.obj) {
2331                                         /* Node is empty */
2332                                         continue;
2333                                 }
2334
2335                                 if (state->sort_fn) {
2336                                         /* Filter node through the sort_fn */
2337                                         cmp = state->sort_fn(node->common.obj, arg, flags & OBJ_SEARCH_MASK);
2338                                         if (cmp > 0) {
2339                                                 continue;
2340                                         }
2341                                         if (cmp < 0) {
2342                                                 /* No more nodes in this bucket are possible to match. */
2343                                                 break;
2344                                         }
2345                                 }
2346
2347                                 /* We have the first traversal node */
2348                                 __ao2_ref(node, +1);
2349                                 return node;
2350                         }
2351                 }
2352         } else {
2353                 /*
2354                  * Determine the search boundaries of an ascending traversal.
2355                  *
2356                  * bucket_cur to state->bucket_last-1
2357                  */
2358                 if (bucket_cur < 0) {
2359                         bucket_cur = 0;
2360                         state->bucket_last = self->n_buckets;
2361                 } else {
2362                         state->bucket_last = bucket_cur + 1;
2363                 }
2364                 state->bucket_start = bucket_cur;
2365
2366                 /* For each bucket */
2367                 for (; bucket_cur < state->bucket_last; ++bucket_cur) {
2368                         /* For each node in the bucket. */
2369                         for (node = AST_DLLIST_FIRST(&self->buckets[bucket_cur].list);
2370                                 node;
2371                                 node = AST_DLLIST_NEXT(node, links)) {
2372                                 if (!node->common.obj) {
2373                                         /* Node is empty */
2374                                         continue;
2375                                 }
2376
2377                                 if (state->sort_fn) {
2378                                         /* Filter node through the sort_fn */
2379                                         cmp = state->sort_fn(node->common.obj, arg, flags & OBJ_SEARCH_MASK);
2380                                         if (cmp < 0) {
2381                                                 continue;
2382                                         }
2383                                         if (cmp > 0) {
2384                                                 /* No more nodes in this bucket are possible to match. */
2385                                                 break;
2386                                         }
2387                                 }
2388
2389                                 /* We have the first traversal node */
2390                                 __ao2_ref(node, +1);
2391                                 return node;
2392                         }
2393                 }
2394         }
2395
2396         return NULL;
2397 }
2398
2399 /*!
2400  * \internal
2401  * \brief Find the next hash container node in a traversal.
2402  * \since 12.0.0
2403  *
2404  * \param self Container to operate upon.
2405  * \param state Traversal state to restart hash container traversal.
2406  * \param prev Previous node returned by the traversal search functions.
2407  *    The ref ownership is passed back to this function.
2408  *
2409  * \retval node-ptr of found node (Reffed).
2410  * \retval NULL when no node found.
2411  */
2412 static struct hash_bucket_node *hash_ao2_find_next(struct ao2_container_hash *self, struct hash_traversal_state *state, struct hash_bucket_node *prev)
2413 {
2414         struct hash_bucket_node *node;
2415         void *arg;
2416         enum search_flags flags;
2417         int bucket_cur;
2418         int cmp;
2419
2420         arg = state->arg;
2421         flags = state->flags;
2422         bucket_cur = prev->my_bucket;
2423         node = prev;
2424
2425         /*
2426          * This function is structured the same as hash_ao2_find_first()
2427          * intentionally.  We are resuming the search loops from
2428          * hash_ao2_find_first() in order to find the next node.  The
2429          * search loops must be resumed where hash_ao2_find_first()
2430          * returned with the first node.
2431          */
2432         if (state->descending) {
2433                 goto hash_descending_resume;
2434
2435                 /* For each bucket */
2436                 for (; state->bucket_last <= bucket_cur; --bucket_cur) {
2437                         /* For each node in the bucket. */
2438                         for (node = AST_DLLIST_LAST(&self->buckets[bucket_cur].list);
2439                                 node;
2440                                 node = AST_DLLIST_PREV(node, links)) {
2441                                 if (!node->common.obj) {
2442                                         /* Node is empty */
2443                                         continue;
2444                                 }
2445
2446                                 if (state->sort_fn) {
2447                                         /* Filter node through the sort_fn */
2448                                         cmp = state->sort_fn(node->common.obj, arg, flags & OBJ_SEARCH_MASK);
2449                                         if (cmp > 0) {
2450                                                 continue;
2451                                         }
2452                                         if (cmp < 0) {
2453                                                 /* No more nodes in this bucket are possible to match. */
2454                                                 break;
2455                                         }
2456                                 }
2457
2458                                 /* We have the next traversal node */
2459                                 __ao2_ref(node, +1);
2460
2461                                 /*
2462                                  * Dereferencing the prev node may result in our next node
2463                                  * object being removed by another thread.  This could happen if
2464                                  * the container uses RW locks and the container was read
2465                                  * locked.
2466                                  */
2467                                 __ao2_ref(prev, -1);
2468                                 if (node->common.obj) {
2469                                         return node;
2470                                 }
2471                                 prev = node;
2472
2473 hash_descending_resume:;
2474                         }
2475                 }
2476         } else {
2477                 goto hash_ascending_resume;
2478
2479                 /* For each bucket */
2480                 for (; bucket_cur < state->bucket_last; ++bucket_cur) {
2481                         /* For each node in the bucket. */
2482                         for (node = AST_DLLIST_FIRST(&self->buckets[bucket_cur].list);
2483                                 node;
2484                                 node = AST_DLLIST_NEXT(node, links)) {
2485                                 if (!node->common.obj) {
2486                                         /* Node is empty */
2487                                         continue;
2488                                 }
2489
2490                                 if (state->sort_fn) {
2491                                         /* Filter node through the sort_fn */
2492                                         cmp = state->sort_fn(node->common.obj, arg, flags & OBJ_SEARCH_MASK);
2493                                         if (cmp < 0) {
2494                                                 continue;
2495                                         }
2496                                         if (cmp > 0) {
2497                                                 /* No more nodes in this bucket are possible to match. */
2498                                                 break;
2499                                         }
2500                                 }
2501
2502                                 /* We have the next traversal node */
2503                                 __ao2_ref(node, +1);
2504
2505                                 /*
2506                                  * Dereferencing the prev node may result in our next node
2507                                  * object being removed by another thread.  This could happen if
2508                                  * the container uses RW locks and the container was read
2509                                  * locked.
2510                                  */
2511                                 __ao2_ref(prev, -1);
2512                                 if (node->common.obj) {
2513                                         return node;
2514                                 }
2515                                 prev = node;
2516
2517 hash_ascending_resume:;
2518                         }
2519                 }
2520         }
2521
2522         /* No more nodes in the container left to traverse. */
2523         __ao2_ref(prev, -1);
2524         return NULL;
2525 }
2526
2527 /*!
2528  * \internal
2529  * \brief Find the next non-empty iteration node in the container.
2530  * \since 12.0.0
2531  *
2532  * \param self Container to operate upon.
2533  * \param node Previous node returned by the iterator.
2534  * \param flags search_flags to control iterating the container.
2535  *   Only AO2_ITERATOR_DESCENDING is useful by the method.
2536  *
2537  * \note The container is already locked.
2538  *
2539  * \retval node on success.
2540  * \retval NULL on error or no more nodes in the container.
2541  */
2542 static struct hash_bucket_node *hash_ao2_iterator_next(struct ao2_container_hash *self, struct hash_bucket_node *node, enum ao2_iterator_flags flags)
2543 {
2544         int cur_bucket;
2545
2546         if (flags & AO2_ITERATOR_DESCENDING) {
2547                 if (node) {
2548                         cur_bucket = node->my_bucket;
2549
2550                         /* Find next non-empty node. */
2551                         for (;;) {
2552                                 node = AST_DLLIST_PREV(node, links);
2553                                 if (!node) {
2554                                         break;
2555                                 }
2556                                 if (node->common.obj) {
2557                                         /* Found a non-empty node. */
2558                                         return node;
2559                                 }
2560                         }
2561                 } else {
2562                         /* Find first non-empty node. */
2563                         cur_bucket = self->n_buckets;
2564                 }
2565
2566                 /* Find a non-empty node in the remaining buckets */
2567                 while (0 <= --cur_bucket) {
2568                         node = AST_DLLIST_LAST(&self->buckets[cur_bucket].list);
2569                         while (node) {
2570                                 if (node->common.obj) {
2571                                         /* Found a non-empty node. */
2572                                         return node;
2573                                 }
2574                                 node = AST_DLLIST_PREV(node, links);
2575                         }
2576                 }
2577         } else {
2578                 if (node) {
2579                         cur_bucket = node->my_bucket;
2580
2581                         /* Find next non-empty node. */
2582                         for (;;) {
2583                                 node = AST_DLLIST_NEXT(node, links);
2584                                 if (!node) {
2585                                         break;
2586                                 }
2587                                 if (node->common.obj) {
2588                                         /* Found a non-empty node. */
2589                                         return node;
2590                                 }
2591                         }
2592                 } else {
2593                         /* Find first non-empty node. */
2594                         cur_bucket = -1;
2595                 }
2596
2597                 /* Find a non-empty node in the remaining buckets */
2598                 while (++cur_bucket < self->n_buckets) {
2599                         node = AST_DLLIST_FIRST(&self->buckets[cur_bucket].list);
2600                         while (node) {
2601                                 if (node->common.obj) {
2602                                         /* Found a non-empty node. */
2603                                         return node;
2604                                 }
2605                                 node = AST_DLLIST_NEXT(node, links);
2606                         }
2607                 }
2608         }
2609
2610         /* No more nodes to visit in the container. */
2611         return NULL;
2612 }
2613
2614 #if defined(AST_DEVMODE)
2615 /*!
2616  * \internal
2617  * \brief Increment the hash container linked object statistic.
2618  * \since 12.0.0
2619  *
2620  * \param hash Container to operate upon.
2621  * \param hash_node Container node linking object to.
2622  *
2623  * \return Nothing
2624  */
2625 static void hash_ao2_link_node_stat(struct ao2_container *hash, struct ao2_container_node *hash_node)
2626 {
2627         struct ao2_container_hash *self = (struct ao2_container_hash *) hash;
2628         struct hash_bucket_node *node = (struct hash_bucket_node *) hash_node;
2629         int i = node->my_bucket;
2630
2631         ++self->buckets[i].elements;
2632         if (self->buckets[i].max_elements < self->buckets[i].elements) {
2633                 self->buckets[i].max_elements = self->buckets[i].elements;
2634         }
2635 }
2636 #endif  /* defined(AST_DEVMODE) */
2637
2638 #if defined(AST_DEVMODE)
2639 /*!
2640  * \internal
2641  * \brief Decrement the hash container linked object statistic.
2642  * \since 12.0.0
2643  *
2644  * \param hash Container to operate upon.
2645  * \param hash_node Container node unlinking object from.
2646  *
2647  * \return Nothing
2648  */
2649 static void hash_ao2_unlink_node_stat(struct ao2_container *hash, struct ao2_container_node *hash_node)
2650 {
2651         struct ao2_container_hash *self = (struct ao2_container_hash *) hash;
2652         struct hash_bucket_node *node = (struct hash_bucket_node *) hash_node;
2653
2654         --self->buckets[node->my_bucket].elements;
2655 }
2656 #endif  /* defined(AST_DEVMODE) */
2657
2658 /*!
2659  * \internal
2660  *
2661  * \brief Destroy this container.
2662  * \since 12.0.0
2663  *
2664  * \param self Container to operate upon.
2665  *
2666  * \return Nothing
2667  */
2668 static void hash_ao2_destroy(struct ao2_container_hash *self)
2669 {
2670         int idx;
2671
2672         /* Check that the container no longer has any nodes */
2673         for (idx = self->n_buckets; idx--;) {
2674                 if (!AST_DLLIST_EMPTY(&self->buckets[idx].list)) {
2675                         ast_log(LOG_ERROR, "Node ref leak.  Hash container still has nodes!\n");
2676                         ast_assert(0);
2677                         break;
2678                 }
2679         }
2680 }
2681
2682 #if defined(AST_DEVMODE)
2683 /*!
2684  * \internal
2685  * \brief Display contents of the specified container.
2686  * \since 12.0.0
2687  *
2688  * \param self Container to dump.
2689  * \param where User data needed by prnt to determine where to put output.
2690  * \param prnt Print output callback function to use.
2691  * \param prnt_obj Callback function to print the given object's key. (NULL if not available)
2692  *
2693  * \return Nothing
2694  */
2695 static void hash_ao2_dump(struct ao2_container_hash *self, void *where, ao2_prnt_fn *prnt, ao2_prnt_obj_fn *prnt_obj)
2696 {
2697 #define FORMAT  "%6s, %16s, %16s, %16s, %16s, %s\n"
2698 #define FORMAT2 "%6d, %16p, %16p, %16p, %16p, "
2699
2700         int bucket;
2701         int suppressed_buckets = 0;
2702         struct hash_bucket_node *node;
2703
2704         prnt(where, "Number of buckets: %d\n\n", self->n_buckets);
2705
2706         prnt(where, FORMAT, "Bucket", "Node", "Prev", "Next", "Obj", "Key");
2707         for (bucket = 0; bucket < self->n_buckets; ++bucket) {
2708                 node = AST_DLLIST_FIRST(&self->buckets[bucket].list);
2709                 if (node) {
2710                         suppressed_buckets = 0;
2711                         do {
2712                                 prnt(where, FORMAT2,
2713                                         bucket,
2714                                         node,
2715                                         AST_DLLIST_PREV(node, links),
2716                                         AST_DLLIST_NEXT(node, links),
2717                                         node->common.obj);
2718                                 if (node->common.obj && prnt_obj) {
2719                                         prnt_obj(node->common.obj, where, prnt);
2720                                 }
2721                                 prnt(where, "\n");
2722
2723                                 node = AST_DLLIST_NEXT(node, links);
2724                         } while (node);
2725                 } else if (!suppressed_buckets) {
2726                         suppressed_buckets = 1;
2727                         prnt(where, "...\n");
2728                 }
2729         }
2730
2731 #undef FORMAT
2732 #undef FORMAT2
2733 }
2734 #endif  /* defined(AST_DEVMODE) */
2735
2736 #if defined(AST_DEVMODE)
2737 /*!
2738  * \internal
2739  * \brief Display statistics of the specified container.
2740  * \since 12.0.0
2741  *
2742  * \param self Container to display statistics.
2743  * \param where User data needed by prnt to determine where to put output.
2744  * \param prnt Print output callback function to use.
2745  *
2746  * \note The container is already locked for reading.
2747  *
2748  * \return Nothing
2749  */
2750 static void hash_ao2_stats(struct ao2_container_hash *self, void *where, ao2_prnt_fn *prnt)
2751 {
2752 #define FORMAT  "%10.10s %10.10s %10.10s\n"
2753 #define FORMAT2 "%10d %10d %10d\n"
2754
2755         int bucket;
2756         int suppressed_buckets = 0;
2757
2758         prnt(where, "Number of buckets: %d\n\n", self->n_buckets);
2759
2760         prnt(where, FORMAT, "Bucket", "Objects", "Max");
2761         for (bucket = 0; bucket < self->n_buckets; ++bucket) {
2762                 if (self->buckets[bucket].max_elements) {
2763                         suppressed_buckets = 0;
2764                         prnt(where, FORMAT2, bucket, self->buckets[bucket].elements,
2765                                 self->buckets[bucket].max_elements);
2766                 } else if (!suppressed_buckets) {
2767                         suppressed_buckets = 1;
2768                         prnt(where, "...\n");
2769                 }
2770         }
2771
2772 #undef FORMAT
2773 #undef FORMAT2
2774 }
2775 #endif  /* defined(AST_DEVMODE) */
2776
2777 #if defined(AST_DEVMODE)
2778 /*!
2779  * \internal
2780  * \brief Perform an integrity check on the specified container.
2781  * \since 12.0.0
2782  *
2783  * \param self Container to check integrity.
2784  *
2785  * \note The container is already locked for reading.
2786  *
2787  * \retval 0 on success.
2788  * \retval -1 on error.
2789  */
2790 static int hash_ao2_integrity(struct ao2_container_hash *self)
2791 {
2792         int bucket_exp;
2793         int bucket;
2794         int count_obj;
2795         int count_total_obj;
2796         int count_total_node;
2797         void *obj_last;
2798         struct hash_bucket_node *node;
2799         struct hash_bucket_node *prev;
2800         struct hash_bucket_node *next;
2801
2802         count_total_obj = 0;
2803         count_total_node = 0;
2804
2805         /* For each bucket in the container. */
2806         for (bucket = 0; bucket < self->n_buckets; ++bucket) {
2807                 if (!AST_DLLIST_FIRST(&self->buckets[bucket].list)
2808                         && !AST_DLLIST_LAST(&self->buckets[bucket].list)) {
2809                         /* The bucket list is empty. */
2810                         continue;
2811                 }
2812
2813                 count_obj = 0;
2814                 obj_last = NULL;
2815
2816                 /* Check bucket list links and nodes. */
2817                 node = AST_DLLIST_LAST(&self->buckets[bucket].list);
2818                 if (!node) {
2819                         ast_log(LOG_ERROR, "Bucket %d list tail is NULL when it should not be!\n",
2820                                 bucket);
2821                         return -1;
2822                 }
2823                 if (AST_DLLIST_NEXT(node, links)) {
2824                         ast_log(LOG_ERROR, "Bucket %d list tail node is not the last node!\n",
2825                                 bucket);
2826                         return -1;
2827                 }
2828                 node = AST_DLLIST_FIRST(&self->buckets[bucket].list);
2829                 if (!node) {
2830                         ast_log(LOG_ERROR, "Bucket %d list head is NULL when it should not be!\n",
2831                                 bucket);
2832                         return -1;
2833                 }
2834                 if (AST_DLLIST_PREV(node, links)) {
2835                         ast_log(LOG_ERROR, "Bucket %d list head node is not the first node!\n",
2836                                 bucket);
2837                         return -1;
2838                 }
2839                 for (; node; node = next) {
2840                         /* Check backward link. */
2841                         prev = AST_DLLIST_PREV(node, links);
2842                         if (prev) {
2843                                 if (prev == node) {
2844                                         ast_log(LOG_ERROR, "Bucket %d list node's prev pointer points to itself!\n",
2845                                                 bucket);
2846                                         return -1;
2847                                 }
2848                                 if (node != AST_DLLIST_NEXT(prev, links)) {
2849                                         ast_log(LOG_ERROR, "Bucket %d list node's prev node does not link back!\n",
2850                                                 bucket);
2851                                         return -1;
2852                                 }
2853                         } else if (node != AST_DLLIST_FIRST(&self->buckets[bucket].list)) {
2854                                 ast_log(LOG_ERROR, "Bucket %d backward list chain is broken!\n",
2855                                         bucket);
2856                                 return -1;
2857                         }
2858
2859                         /* Check forward link. */
2860                         next = AST_DLLIST_NEXT(node, links);
2861                         if (next) {
2862                                 if (next == node) {
2863                                         ast_log(LOG_ERROR, "Bucket %d list node's next pointer points to itself!\n",
2864                                                 bucket);
2865                                         return -1;
2866                                 }
2867                                 if (node != AST_DLLIST_PREV(next, links)) {
2868                                         ast_log(LOG_ERROR, "Bucket %d list node's next node does not link back!\n",
2869                                                 bucket);
2870                                         return -1;
2871                                 }
2872                         } else if (node != AST_DLLIST_LAST(&self->buckets[bucket].list)) {
2873                                 ast_log(LOG_ERROR, "Bucket %d forward list chain is broken!\n",
2874                                         bucket);
2875                                 return -1;
2876                         }
2877
2878                         if (bucket != node->my_bucket) {
2879                                 ast_log(LOG_ERROR, "Bucket %d node claims to be in bucket %d!\n",
2880                                         bucket, node->my_bucket);
2881                                 return -1;
2882                         }
2883
2884                         ++count_total_node;
2885                         if (!node->common.obj) {
2886                                 /* Node is empty. */
2887                                 continue;
2888                         }
2889                         ++count_obj;
2890
2891                         /* Check container hash key for expected bucket. */
2892                         bucket_exp = abs(self->hash_fn(node->common.obj, OBJ_SEARCH_OBJECT));
2893                         bucket_exp %= self->n_buckets;
2894                         if (bucket != bucket_exp) {
2895                                 ast_log(LOG_ERROR, "Bucket %d node hashes to bucket %d!\n",
2896                                         bucket, bucket_exp);
2897                                 return -1;
2898                         }
2899
2900                         /* Check sort if configured. */
2901                         if (self->common.sort_fn) {
2902                                 if (obj_last
2903                                         && self->common.sort_fn(obj_last, node->common.obj, OBJ_SEARCH_OBJECT) > 0) {
2904                                         ast_log(LOG_ERROR, "Bucket %d nodes out of sorted order!\n",
2905                                                 bucket);
2906                                         return -1;
2907                                 }
2908                                 obj_last = node->common.obj;
2909                         }
2910                 }
2911
2912                 /* Check bucket obj count statistic. */
2913                 if (count_obj != self->buckets[bucket].elements) {
2914                         ast_log(LOG_ERROR, "Bucket %d object count of %d does not match stat of %d!\n",
2915                                 bucket, count_obj, self->buckets[bucket].elements);
2916                         return -1;
2917                 }
2918
2919                 /* Accumulate found object counts. */
2920                 count_total_obj += count_obj;
2921         }
2922
2923         /* Check total obj count. */
2924         if (count_total_obj != ao2_container_count(&self->common)) {
2925                 ast_log(LOG_ERROR,
2926                         "Total object count of %d does not match ao2_container_count() of %d!\n",
2927                         count_total_obj, ao2_container_count(&self->common));
2928                 return -1;
2929         }
2930
2931         /* Check total node count. */
2932         if (count_total_node != self->common.nodes) {
2933                 ast_log(LOG_ERROR, "Total node count of %d does not match stat of %d!\n",
2934                         count_total_node, self->common.nodes);
2935                 return -1;
2936         }
2937
2938         return 0;
2939 }
2940 #endif  /* defined(AST_DEVMODE) */
2941
2942 /*! Hash container virtual method table. */
2943 static const struct ao2_container_methods v_table_hash = {
2944         .type = AO2_CONTAINER_RTTI_HASH,
2945         .alloc_empty_clone = (ao2_container_alloc_empty_clone_fn) hash_ao2_alloc_empty_clone,
2946         .alloc_empty_clone_debug =
2947                 (ao2_container_alloc_empty_clone_debug_fn) hash_ao2_alloc_empty_clone_debug,
2948         .new_node = (ao2_container_new_node_fn) hash_ao2_new_node,
2949         .insert = (ao2_container_insert_fn) hash_ao2_insert_node,
2950         .traverse_first = (ao2_container_find_first_fn) hash_ao2_find_first,
2951         .traverse_next = (ao2_container_find_next_fn) hash_ao2_find_next,
2952         .iterator_next = (ao2_iterator_next_fn) hash_ao2_iterator_next,
2953         .destroy = (ao2_container_destroy_fn) hash_ao2_destroy,
2954 #if defined(AST_DEVMODE)
2955         .dump = (ao2_container_display) hash_ao2_dump,
2956         .stats = (ao2_container_statistics) hash_ao2_stats,
2957         .integrity = (ao2_container_integrity) hash_ao2_integrity,
2958 #endif  /* defined(AST_DEVMODE) */
2959 };
2960
2961 /*!
2962  * \brief always zero hash function
2963  *
2964  * it is convenient to have a hash function that always returns 0.
2965  * This is basically used when we want to have a container that is
2966  * a simple linked list.
2967  *
2968  * \returns 0
2969  */
2970 static int hash_zero(const void *user_obj, const int flags)
2971 {
2972         return 0;
2973 }
2974
2975 /*!
2976  * \brief Initialize a hash container with the desired number of buckets.
2977  *
2978  * \param self Container to initialize.
2979  * \param options Container behaviour options (See enum ao2_container_opts)
2980  * \param n_buckets Number of buckets for hash
2981  * \param hash_fn Pointer to a function computing a hash value.
2982  * \param sort_fn Pointer to a sort function.
2983  * \param cmp_fn Pointer to a compare function used by ao2_find.
2984  *
2985  * \return A pointer to a struct container.
2986  */
2987 static struct ao2_container *hash_ao2_container_init(
2988         struct ao2_container_hash *self, unsigned int options, unsigned int n_buckets,
2989         ao2_hash_fn *hash_fn, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn)
2990 {
2991         if (!self) {
2992                 return NULL;
2993         }
2994
2995         self->common.v_table = &v_table_hash;
2996         self->common.sort_fn = sort_fn;
2997         self->common.cmp_fn = cmp_fn;
2998         self->common.options = options;
2999         self->hash_fn = hash_fn ? hash_fn : hash_zero;
3000         self->n_buckets = n_buckets;
3001
3002 #ifdef AO2_DEBUG
3003         ast_atomic_fetchadd_int(&ao2.total_containers, 1);
3004 #endif
3005
3006         return (struct ao2_container *) self;
3007 }
3008
3009 struct ao2_container *__ao2_container_alloc_hash(unsigned int ao2_options,
3010         unsigned int container_options, unsigned int n_buckets, ao2_hash_fn *hash_fn,
3011         ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn)
3012 {
3013         unsigned int num_buckets;
3014         size_t container_size;
3015         struct ao2_container_hash *self;
3016
3017         num_buckets = hash_fn ? n_buckets : 1;
3018         container_size = sizeof(struct ao2_container_hash) + num_buckets * sizeof(struct hash_bucket);
3019
3020         self = ao2_t_alloc_options(container_size, container_destruct, ao2_options,
3021                 "New hash container");
3022         return hash_ao2_container_init(self, container_options, num_buckets,
3023                 hash_fn, sort_fn, cmp_fn);
3024 }
3025
3026 struct ao2_container *__ao2_container_alloc_hash_debug(unsigned int ao2_options,
3027         unsigned int container_options, unsigned int n_buckets, ao2_hash_fn *hash_fn,
3028         ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn,
3029         const char *tag, const char *file, int line, const char *func, int ref_debug)
3030 {
3031         unsigned int num_buckets;
3032         size_t container_size;
3033         struct ao2_container_hash *self;
3034
3035         num_buckets = hash_fn ? n_buckets : 1;
3036         container_size = sizeof(struct ao2_container_hash) + num_buckets * sizeof(struct hash_bucket);
3037
3038         self = __ao2_alloc_debug(container_size,
3039                 ref_debug ? container_destruct_debug : container_destruct, ao2_options,
3040                 tag, file, line, func, ref_debug);
3041         return hash_ao2_container_init(self, container_options, num_buckets, hash_fn,
3042                 sort_fn, cmp_fn);
3043 }
3044
3045 struct ao2_container *__ao2_container_alloc_list(unsigned int ao2_options,
3046         unsigned int container_options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn)
3047 {
3048         return __ao2_container_alloc_hash(ao2_options, container_options, 1, NULL, sort_fn,
3049                 cmp_fn);
3050 }
3051
3052 struct ao2_container *__ao2_container_alloc_list_debug(unsigned int ao2_options,
3053         unsigned int container_options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn,
3054         const char *tag, const char *file, int line, const char *func, int ref_debug)
3055 {
3056         return __ao2_container_alloc_hash_debug(ao2_options, container_options, 1, NULL,
3057                 sort_fn, cmp_fn, tag, file, line, func, ref_debug);
3058 }
3059
3060 /*!
3061  * A structure to hold the object held by the container and
3062  * where it is located in it.
3063  *
3064  * A red-black tree has the following properties:
3065  *
3066  * 1) Every node is either black or red.
3067  *
3068  * 2) The root is black.
3069  *
3070  * 3) If a node has a NULL child, that "child" is considered
3071  * black.
3072  *
3073  * 4) If a node is red, then both of its children are black.
3074  *
3075  * 5) Every path from a node to a descendant NULL child has the
3076  * same number of black nodes.  (Including the black NULL
3077  * child.)
3078  */
3079 struct rbtree_node {
3080         /*!
3081          * \brief Items common to all container nodes.
3082          * \note Must be first in the specific node struct.
3083          */
3084         struct ao2_container_node common;
3085         /*! Parent node of this node. NULL if this is the root node. */
3086         struct rbtree_node *parent;
3087         /*! Left child node of this node.  NULL if does not have this child. */
3088         struct rbtree_node *left;
3089         /*! Right child node of this node.  NULL if does not have this child. */
3090         struct rbtree_node *right;
3091         /*! TRUE if the node is red. */
3092         unsigned int is_red:1;
3093 };
3094
3095 /*!
3096  * A rbtree container in addition to values common to all
3097  * container types, stores the pointer to the root node of the
3098  * tree.
3099  */
3100 struct ao2_container_rbtree {
3101         /*!
3102          * \brief Items common to all containers.
3103          * \note Must be first in the specific container struct.
3104          */
3105         struct ao2_container common;
3106         /*! Root node of the tree.  NULL if the tree is empty. */
3107         struct rbtree_node *root;
3108 #if defined(AST_DEVMODE)
3109         struct {
3110                 /*! Fixup insert left cases 1-3 */
3111                 int fixup_insert_left[3];
3112                 /*! Fixup insert right cases 1-3 */
3113                 int fixup_insert_right[3];
3114                 /*! Fixup delete left cases 1-4 */
3115                 int fixup_delete_left[4];
3116                 /*! Fixup delete right cases 1-4 */
3117                 int fixup_delete_right[4];
3118                 /*! Deletion of node with number of children (0-2). */
3119                 int delete_children[3];
3120         } stats;
3121 #endif  /* defined(AST_DEVMODE) */
3122 };
3123
3124 /*!
3125  * \internal
3126  * \brief Get the most left node in the tree.
3127  * \since 12.0.0
3128  *
3129  * \param node Starting node to find the most left node.
3130  *
3131  * \return Left most node.  Never NULL.
3132  */
3133 static struct rbtree_node *rb_node_most_left(struct rbtree_node *node)
3134 {
3135         while (node->left) {
3136                 node = node->left;
3137         }
3138
3139         return node;
3140 }
3141
3142 /*!
3143  * \internal
3144  * \brief Get the most right node in the tree.
3145  * \since 12.0.0
3146  *
3147  * \param node Starting node to find the most right node.
3148  *
3149  * \return Right most node.  Never NULL.
3150  */
3151 static struct rbtree_node *rb_node_most_right(struct rbtree_node *node)
3152 {
3153         while (node->right) {
3154                 node = node->right;
3155         }
3156
3157         return node;
3158 }
3159
3160 /*!
3161  * \internal
3162  * \brief Get the next node in ascending sequence.
3163  * \since 12.0.0
3164  *
3165  * \param node Starting node to find the next node.
3166  *
3167  * \retval node on success.
3168  * \retval NULL if no node.
3169  */
3170 static struct rbtree_node *rb_node_next(struct rbtree_node *node)
3171 {
3172         if (node->right) {
3173                 return rb_node_most_left(node->right);
3174         }
3175
3176         /* Find the parent that the node is a left child of. */
3177         while (node->parent) {
3178                 if (node->parent->left == node) {
3179                         /* We are the left child.  The parent is the next node. */
3180                         return node->parent;
3181                 }
3182                 node = node->parent;
3183         }
3184         return NULL;
3185 }
3186
3187 /*!
3188  * \internal
3189  * \brief Get the next node in descending sequence.
3190  * \since 12.0.0
3191  *
3192  * \param node Starting node to find the previous node.
3193  *
3194  * \retval node on success.
3195  * \retval NULL if no node.
3196  */
3197 static struct rbtree_node *rb_node_prev(struct rbtree_node *node)
3198 {
3199         if (node->left) {
3200                 return rb_node_most_right(node->left);
3201         }
3202
3203         /* Find the parent that the node is a right child of. */
3204         while (node->parent) {
3205                 if (node->parent->right == node) {
3206                         /* We are the right child.  The parent is the previous node. */
3207                         return node->parent;
3208                 }
3209                 node = node->parent;
3210         }
3211         return NULL;
3212 }
3213
3214 /*!
3215  * \internal
3216  * \brief Get the next node in pre-order sequence.
3217  * \since 12.0.0
3218  *
3219  * \param node Starting node to find the next node.
3220  *
3221  * \retval node on success.
3222  * \retval NULL if no node.
3223  */
3224 static struct rbtree_node *rb_node_pre(struct rbtree_node *node)
3225 {
3226         /* Visit the children if the node has any. */
3227         if (node->left) {
3228                 return node->left;
3229         }
3230         if (node->right) {
3231                 return node->right;
3232         }
3233
3234         /* Time to go back up. */
3235         for (;;) {
3236                 if (!node->parent) {
3237                         return NULL;
3238                 }
3239                 if (node->parent->left == node && node->parent->right) {
3240                         /*
3241                          * We came up the left child and there's a right child.  Visit
3242                          * it.
3243                          */
3244                         return node->parent->right;
3245                 }
3246                 node = node->parent;
3247         }
3248 }
3249
3250 /*!
3251  * \internal
3252  * \brief Get the next node in post-order sequence.
3253  * \since 12.0.0
3254  *
3255  * \param node Starting node to find the next node.
3256  *