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