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