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