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