00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #include "asterisk.h"
00021
00022 ASTERISK_FILE_VERSION(__FILE__, "$Revision: 298345 $")
00023
00024 #include "asterisk/astobj2.h"
00025 #include "asterisk/utils.h"
00026 #include "asterisk/cli.h"
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 struct __priv_data {
00039 ast_mutex_t lock;
00040 int ref_counter;
00041 ao2_destructor_fn destructor_fn;
00042
00043 size_t data_size;
00044
00045
00046 uint32_t magic;
00047 };
00048
00049 #define AO2_MAGIC 0xa570b123
00050
00051
00052
00053
00054
00055 struct astobj2 {
00056 struct __priv_data priv_data;
00057 void *user_data[0];
00058 };
00059
00060 #ifdef AST_DEVMODE
00061 #define AO2_DEBUG 1
00062 #endif
00063
00064 #ifdef AO2_DEBUG
00065 struct ao2_stats {
00066 volatile int total_objects;
00067 volatile int total_mem;
00068 volatile int total_containers;
00069 volatile int total_refs;
00070 volatile int total_locked;
00071 };
00072
00073 static struct ao2_stats ao2;
00074 #endif
00075
00076 #ifndef HAVE_BKTR
00077 void ao2_bt(void) {}
00078 #else
00079 #include <execinfo.h>
00080
00081 void ao2_bt(void)
00082 {
00083 int c, i;
00084 #define N1 20
00085 void *addresses[N1];
00086 char **strings;
00087
00088 c = backtrace(addresses, N1);
00089 strings = backtrace_symbols(addresses,c);
00090 ast_verbose("backtrace returned: %d\n", c);
00091 for(i = 0; i < c; i++) {
00092 ast_verbose("%d: %p %s\n", i, addresses[i], strings[i]);
00093 }
00094 free(strings);
00095 }
00096 #endif
00097
00098
00099
00100
00101
00102
00103 static inline struct astobj2 *INTERNAL_OBJ(void *user_data)
00104 {
00105 struct astobj2 *p;
00106
00107 if (!user_data) {
00108 ast_log(LOG_ERROR, "user_data is NULL\n");
00109 return NULL;
00110 }
00111
00112 p = (struct astobj2 *) ((char *) user_data - sizeof(*p));
00113 if (AO2_MAGIC != (p->priv_data.magic) ) {
00114 ast_log(LOG_ERROR, "bad magic number 0x%x for %p\n", p->priv_data.magic, p);
00115 p = NULL;
00116 }
00117
00118 return p;
00119 }
00120
00121
00122
00123
00124
00125
00126 #define EXTERNAL_OBJ(_p) ((_p) == NULL ? NULL : (_p)->user_data)
00127
00128 #ifdef DEBUG_THREADS
00129
00130 #undef ao2_lock
00131 #undef ao2_trylock
00132 #undef ao2_unlock
00133 #endif
00134
00135 int ao2_lock(void *user_data)
00136 {
00137 struct astobj2 *p = INTERNAL_OBJ(user_data);
00138
00139 if (p == NULL)
00140 return -1;
00141
00142 #ifdef AO2_DEBUG
00143 ast_atomic_fetchadd_int(&ao2.total_locked, 1);
00144 #endif
00145
00146 return ast_mutex_lock(&p->priv_data.lock);
00147 }
00148
00149 int __ao2_lock(void *user_data, const char *file, const char *func, int line, const char *var)
00150 {
00151 struct astobj2 *p = INTERNAL_OBJ(user_data);
00152
00153 if (p == NULL)
00154 return -1;
00155
00156 #ifdef AO2_DEBUG
00157 ast_atomic_fetchadd_int(&ao2.total_locked, 1);
00158 #endif
00159
00160 #ifndef DEBUG_THREADS
00161 return ast_mutex_lock(&p->priv_data.lock);
00162 #else
00163 return __ast_pthread_mutex_lock(file, line, func, var, &p->priv_data.lock);
00164 #endif
00165 }
00166
00167 int ao2_trylock(void *user_data)
00168 {
00169 struct astobj2 *p = INTERNAL_OBJ(user_data);
00170 int res;
00171
00172 if (p == NULL)
00173 return -1;
00174
00175 res = ast_mutex_trylock(&p->priv_data.lock);
00176
00177 #ifdef AO2_DEBUG
00178 if (!res) {
00179 ast_atomic_fetchadd_int(&ao2.total_locked, 1);
00180 }
00181 #endif
00182
00183 return res;
00184 }
00185
00186 int __ao2_trylock(void *user_data, const char *file, const char *func, int line, const char *var)
00187 {
00188 struct astobj2 *p = INTERNAL_OBJ(user_data);
00189 int res;
00190
00191 if (p == NULL)
00192 return -1;
00193
00194 #ifndef DEBUG_THREADS
00195 res = ast_mutex_trylock(&p->priv_data.lock);
00196 #else
00197 res = __ast_pthread_mutex_trylock(file, line, func, var, &p->priv_data.lock);
00198 #endif
00199
00200 #ifdef AO2_DEBUG
00201 if (!res) {
00202 ast_atomic_fetchadd_int(&ao2.total_locked, 1);
00203 }
00204 #endif
00205
00206 return res;
00207 }
00208
00209 int ao2_unlock(void *user_data)
00210 {
00211 struct astobj2 *p = INTERNAL_OBJ(user_data);
00212
00213 if (p == NULL)
00214 return -1;
00215
00216 #ifdef AO2_DEBUG
00217 ast_atomic_fetchadd_int(&ao2.total_locked, -1);
00218 #endif
00219
00220 return ast_mutex_unlock(&p->priv_data.lock);
00221 }
00222
00223 int __ao2_unlock(void *user_data, const char *file, const char *func, int line, const char *var)
00224 {
00225 struct astobj2 *p = INTERNAL_OBJ(user_data);
00226
00227 if (p == NULL)
00228 return -1;
00229
00230 #ifdef AO2_DEBUG
00231 ast_atomic_fetchadd_int(&ao2.total_locked, -1);
00232 #endif
00233
00234 #ifndef DEBUG_THREADS
00235 return ast_mutex_unlock(&p->priv_data.lock);
00236 #else
00237 return __ast_pthread_mutex_unlock(file, line, func, var, &p->priv_data.lock);
00238 #endif
00239 }
00240
00241
00242
00243
00244 int ao2_ref(void *user_data, const int delta)
00245 {
00246 int current_value;
00247 int ret;
00248 struct astobj2 *obj = INTERNAL_OBJ(user_data);
00249
00250 if (obj == NULL)
00251 return -1;
00252
00253
00254 if (delta == 0)
00255 return (obj->priv_data.ref_counter);
00256
00257
00258 ret = ast_atomic_fetchadd_int(&obj->priv_data.ref_counter, delta);
00259 current_value = ret + delta;
00260
00261 #ifdef AO2_DEBUG
00262 ast_atomic_fetchadd_int(&ao2.total_refs, delta);
00263 #endif
00264
00265
00266 if (current_value < 0)
00267 ast_log(LOG_ERROR, "refcount %d on object %p\n", current_value, user_data);
00268
00269 if (current_value <= 0) {
00270 if (obj->priv_data.destructor_fn != NULL)
00271 obj->priv_data.destructor_fn(user_data);
00272
00273 ast_mutex_destroy(&obj->priv_data.lock);
00274 #ifdef AO2_DEBUG
00275 ast_atomic_fetchadd_int(&ao2.total_mem, - obj->priv_data.data_size);
00276 ast_atomic_fetchadd_int(&ao2.total_objects, -1);
00277 #endif
00278
00279
00280
00281 bzero(obj, sizeof(struct astobj2 *) + sizeof(void *) );
00282 free(obj);
00283 }
00284
00285 return ret;
00286 }
00287
00288
00289
00290
00291
00292 void *ao2_alloc(size_t data_size, ao2_destructor_fn destructor_fn)
00293 {
00294
00295 struct astobj2 *obj;
00296
00297 if (data_size < sizeof(void *))
00298 data_size = sizeof(void *);
00299
00300 obj = ast_calloc(1, sizeof(*obj) + data_size);
00301
00302 if (obj == NULL)
00303 return NULL;
00304
00305 ast_mutex_init(&obj->priv_data.lock);
00306 obj->priv_data.magic = AO2_MAGIC;
00307 obj->priv_data.data_size = data_size;
00308 obj->priv_data.ref_counter = 1;
00309 obj->priv_data.destructor_fn = destructor_fn;
00310
00311 #ifdef AO2_DEBUG
00312 ast_atomic_fetchadd_int(&ao2.total_objects, 1);
00313 ast_atomic_fetchadd_int(&ao2.total_mem, data_size);
00314 ast_atomic_fetchadd_int(&ao2.total_refs, 1);
00315 #endif
00316
00317
00318 return EXTERNAL_OBJ(obj);
00319 }
00320
00321
00322 static void container_destruct(void *c);
00323
00324
00325 AST_LIST_HEAD_NOLOCK(bucket, bucket_list);
00326
00327
00328
00329
00330
00331
00332
00333
00334
00335
00336
00337
00338
00339
00340
00341
00342
00343
00344
00345
00346
00347
00348
00349 struct ao2_container {
00350 ao2_hash_fn hash_fn;
00351 ao2_callback_fn cmp_fn;
00352 int n_buckets;
00353
00354 int elements;
00355
00356 int version;
00357
00358 struct bucket buckets[0];
00359 };
00360
00361
00362
00363
00364
00365
00366
00367
00368
00369
00370 static int hash_zero(const void *user_obj, const int flags)
00371 {
00372 return 0;
00373 }
00374
00375
00376
00377
00378 struct ao2_container *
00379 ao2_container_alloc(const unsigned int n_buckets, ao2_hash_fn hash_fn,
00380 ao2_callback_fn cmp_fn)
00381 {
00382
00383
00384 size_t container_size = sizeof(struct ao2_container) + n_buckets * sizeof(struct bucket);
00385
00386 struct ao2_container *c = ao2_alloc(container_size, container_destruct);
00387
00388 if (!c)
00389 return NULL;
00390
00391 c->version = 1;
00392 c->n_buckets = n_buckets;
00393 c->hash_fn = hash_fn ? hash_fn : hash_zero;
00394 c->cmp_fn = cmp_fn;
00395
00396 #ifdef AO2_DEBUG
00397 ast_atomic_fetchadd_int(&ao2.total_containers, 1);
00398 #endif
00399
00400 return c;
00401 }
00402
00403
00404
00405
00406 int ao2_container_count(struct ao2_container *c)
00407 {
00408 return c->elements;
00409 }
00410
00411
00412
00413
00414
00415
00416 struct bucket_list {
00417 AST_LIST_ENTRY(bucket_list) entry;
00418 int version;
00419 struct astobj2 *astobj;
00420 };
00421
00422
00423
00424
00425 void *__ao2_link(struct ao2_container *c, void *user_data, int iax2_hack)
00426 {
00427 int i;
00428
00429 struct bucket_list *p;
00430 struct astobj2 *obj = INTERNAL_OBJ(user_data);
00431
00432 if (!obj)
00433 return NULL;
00434
00435 if (INTERNAL_OBJ(c) == NULL)
00436 return NULL;
00437
00438 p = ast_calloc(1, sizeof(*p));
00439 if (!p)
00440 return NULL;
00441
00442 i = abs(c->hash_fn(user_data, OBJ_POINTER));
00443
00444 ao2_lock(c);
00445 i %= c->n_buckets;
00446 p->astobj = obj;
00447 p->version = ast_atomic_fetchadd_int(&c->version, 1);
00448 if (iax2_hack)
00449 AST_LIST_INSERT_HEAD(&c->buckets[i], p, entry);
00450 else
00451 AST_LIST_INSERT_TAIL(&c->buckets[i], p, entry);
00452 ast_atomic_fetchadd_int(&c->elements, 1);
00453 ao2_ref(user_data, +1);
00454 ao2_unlock(c);
00455
00456 return p;
00457 }
00458
00459
00460
00461
00462 int ao2_match_by_addr(void *user_data, void *arg, int flags)
00463 {
00464 return (user_data == arg) ? (CMP_MATCH | CMP_STOP) : 0;
00465 }
00466
00467
00468
00469
00470
00471 void *ao2_unlink(struct ao2_container *c, void *user_data)
00472 {
00473 if (INTERNAL_OBJ(user_data) == NULL)
00474 return NULL;
00475
00476 ao2_callback(c, OBJ_UNLINK | OBJ_POINTER | OBJ_NODATA, ao2_match_by_addr, user_data);
00477
00478 return NULL;
00479 }
00480
00481
00482
00483
00484 static int cb_true(void *user_data, void *arg, int flags)
00485 {
00486 return CMP_MATCH;
00487 }
00488
00489
00490
00491
00492
00493
00494 void *ao2_callback(struct ao2_container *c,
00495 const enum search_flags flags,
00496 ao2_callback_fn cb_fn, void *arg)
00497 {
00498 int i, start, last;
00499 void *ret = NULL;
00500
00501 if (INTERNAL_OBJ(c) == NULL)
00502 return NULL;
00503
00504 if ((flags & (OBJ_MULTIPLE | OBJ_NODATA)) == OBJ_MULTIPLE) {
00505 ast_log(LOG_WARNING, "multiple data return not implemented yet (flags %x)\n", flags);
00506 return NULL;
00507 }
00508
00509
00510 #if 0
00511
00512
00513
00514
00515 if (flags & OBJ_POINTER)
00516 cb_fn = match_by_addr;
00517 else
00518 #endif
00519 if (cb_fn == NULL)
00520 cb_fn = cb_true;
00521
00522
00523
00524
00525
00526
00527 if ((flags & OBJ_POINTER))
00528 start = i = c->hash_fn(arg, flags & OBJ_POINTER) % c->n_buckets;
00529 else
00530 start = i = -1;
00531
00532
00533 if (i < 0) {
00534 start = i = 0;
00535 last = c->n_buckets;
00536 } else if ((flags & OBJ_CONTINUE)) {
00537 last = c->n_buckets;
00538 } else {
00539 last = i + 1;
00540 }
00541
00542 ao2_lock(c);
00543
00544 for (; i < last ; i++) {
00545
00546 struct bucket_list *cur;
00547
00548 AST_LIST_TRAVERSE_SAFE_BEGIN(&c->buckets[i], cur, entry) {
00549 int match = cb_fn(EXTERNAL_OBJ(cur->astobj), arg, flags) & (CMP_MATCH | CMP_STOP);
00550
00551
00552 if (match == 0) {
00553 continue;
00554 } else if (match == CMP_STOP) {
00555 i = last;
00556 break;
00557 }
00558
00559 if (!(flags & OBJ_NODATA)) {
00560
00561 ret = EXTERNAL_OBJ(cur->astobj);
00562 ao2_ref(ret, 1);
00563 }
00564
00565 if (flags & OBJ_UNLINK) {
00566 struct bucket_list *x = cur;
00567
00568
00569 ast_atomic_fetchadd_int(&c->version, 1);
00570 AST_LIST_REMOVE_CURRENT(&c->buckets[i], entry);
00571
00572 ast_atomic_fetchadd_int(&c->elements, -1);
00573 ao2_ref(EXTERNAL_OBJ(x->astobj), -1);
00574 free(x);
00575 }
00576
00577 if ((match & CMP_STOP) || (flags & OBJ_MULTIPLE) == 0) {
00578
00579 i = last;
00580 break;
00581 }
00582 if (!(flags & OBJ_NODATA)) {
00583 #if 0
00584
00585
00586
00587
00588 #endif
00589 }
00590 }
00591 AST_LIST_TRAVERSE_SAFE_END
00592
00593 if (ret) {
00594
00595 break;
00596 }
00597
00598 if (i == c->n_buckets - 1 && (flags & OBJ_POINTER) && (flags & OBJ_CONTINUE)) {
00599
00600 i = -1;
00601 last = start;
00602 }
00603 }
00604 ao2_unlock(c);
00605 return ret;
00606 }
00607
00608
00609
00610
00611 void *ao2_find(struct ao2_container *c, void *arg, enum search_flags flags)
00612 {
00613 return ao2_callback(c, flags, c->cmp_fn, arg);
00614 }
00615
00616
00617
00618
00619 struct ao2_iterator ao2_iterator_init(struct ao2_container *c, int flags)
00620 {
00621 struct ao2_iterator a = {
00622 .c = c,
00623 .flags = flags
00624 };
00625
00626 ao2_ref(c, +1);
00627
00628 return a;
00629 }
00630
00631
00632
00633
00634 void ao2_iterator_destroy(struct ao2_iterator *i)
00635 {
00636 ao2_ref(i->c, -1);
00637 i->c = NULL;
00638 }
00639
00640
00641
00642
00643 void * ao2_iterator_next(struct ao2_iterator *a)
00644 {
00645 int lim;
00646 struct bucket_list *p = NULL;
00647 void *ret = NULL;
00648
00649 if (INTERNAL_OBJ(a->c) == NULL)
00650 return NULL;
00651
00652 if (!(a->flags & AO2_ITERATOR_DONTLOCK))
00653 ao2_lock(a->c);
00654
00655
00656
00657
00658 if (a->c->version == a->c_version && (p = a->obj) ) {
00659 if ( (p = AST_LIST_NEXT(p, entry)) )
00660 goto found;
00661
00662 a->bucket++;
00663 a->version = 0;
00664 a->obj = NULL;
00665 }
00666
00667 lim = a->c->n_buckets;
00668
00669
00670
00671
00672
00673
00674
00675 for (; a->bucket < lim; a->bucket++, a->version = 0) {
00676
00677 AST_LIST_TRAVERSE(&a->c->buckets[a->bucket], p, entry) {
00678 if (p->version > a->version)
00679 goto found;
00680 }
00681 }
00682
00683 found:
00684 if (p) {
00685 a->version = p->version;
00686 a->obj = p;
00687 a->c_version = a->c->version;
00688 ret = EXTERNAL_OBJ(p->astobj);
00689
00690 ao2_ref(ret, 1);
00691 }
00692
00693 if (!(a->flags & AO2_ITERATOR_DONTLOCK))
00694 ao2_unlock(a->c);
00695
00696 return ret;
00697 }
00698
00699
00700
00701
00702 static int cd_cb(void *obj, void *arg, int flag)
00703 {
00704 ao2_ref(obj, -1);
00705 return 0;
00706 }
00707
00708 static void container_destruct(void *_c)
00709 {
00710 struct ao2_container *c = _c;
00711 int i;
00712
00713 ao2_callback(c, OBJ_UNLINK, cd_cb, NULL);
00714
00715 for (i = 0; i < c->n_buckets; i++) {
00716 struct bucket_list *cur;
00717
00718 while ((cur = AST_LIST_REMOVE_HEAD(&c->buckets[i], entry))) {
00719 ast_free(cur);
00720 }
00721 }
00722
00723 #ifdef AO2_DEBUG
00724 ast_atomic_fetchadd_int(&ao2.total_containers, -1);
00725 #endif
00726 }
00727
00728 #ifdef AO2_DEBUG
00729 static int print_cb(void *obj, void *arg, int flag)
00730 {
00731 int *fd = arg;
00732 char *s = (char *)obj;
00733
00734 ast_cli(*fd, "string <%s>\n", s);
00735 return 0;
00736 }
00737
00738
00739
00740
00741 static int handle_astobj2_stats(int fd, int argc, char *argv[])
00742 {
00743 ast_cli(fd, "Objects : %d\n", ao2.total_objects);
00744 ast_cli(fd, "Containers : %d\n", ao2.total_containers);
00745 ast_cli(fd, "Memory : %d\n", ao2.total_mem);
00746 ast_cli(fd, "Locked : %d\n", ao2.total_locked);
00747 ast_cli(fd, "Refs : %d\n", ao2.total_refs);
00748 return 0;
00749 }
00750
00751
00752
00753
00754 static int handle_astobj2_test(int fd, int argc, char *argv[])
00755 {
00756 struct ao2_container *c1;
00757 int i, lim;
00758 char *obj;
00759 static int prof_id = -1;
00760
00761 if (argc != 3) {
00762 return RESULT_SHOWUSAGE;
00763 }
00764
00765 if (prof_id == -1)
00766 prof_id = ast_add_profile("ao2_alloc", 0);
00767
00768 ast_cli(fd, "argc %d argv %s %s %s\n", argc, argv[0], argv[1], argv[2]);
00769 lim = atoi(argv[2]);
00770 ast_cli(fd, "called astobj_test\n");
00771
00772 handle_astobj2_stats(fd, 0, NULL);
00773
00774
00775
00776
00777 c1 = ao2_container_alloc(100, NULL , NULL );
00778 ast_cli(fd, "container allocated as %p\n", c1);
00779
00780
00781
00782
00783
00784
00785 for (i = 0; i < lim; i++) {
00786 ast_mark(prof_id, 1 );
00787 obj = ao2_alloc(80, NULL);
00788 ast_mark(prof_id, 0 );
00789 ast_cli(fd, "object %d allocated as %p\n", i, obj);
00790 sprintf(obj, "-- this is obj %d --", i);
00791 ao2_link(c1, obj);
00792 ao2_ref(obj, -1);
00793 }
00794 ast_cli(fd, "testing callbacks\n");
00795 ao2_callback(c1, 0, print_cb, &fd);
00796
00797 ast_cli(fd, "testing iterators, remove every second object\n");
00798 {
00799 struct ao2_iterator ai;
00800 int x = 0;
00801
00802 ai = ao2_iterator_init(c1, 0);
00803 while ( (obj = ao2_iterator_next(&ai)) ) {
00804 ast_cli(fd, "iterator on <%s>\n", obj);
00805 if (x++ & 1)
00806 ao2_unlink(c1, obj);
00807 ao2_ref(obj, -1);
00808 }
00809 ao2_iterator_destroy(&ai);
00810 ast_cli(fd, "testing iterators again\n");
00811 ai = ao2_iterator_init(c1, 0);
00812 while ( (obj = ao2_iterator_next(&ai)) ) {
00813 ast_cli(fd, "iterator on <%s>\n", obj);
00814 ao2_ref(obj, -1);
00815 }
00816 ao2_iterator_destroy(&ai);
00817 }
00818 ast_cli(fd, "testing callbacks again\n");
00819 ao2_callback(c1, 0, print_cb, &fd);
00820
00821 ast_verbose("now you should see an error message:\n");
00822 ao2_ref(&i, -1);
00823
00824 ast_cli(fd, "destroy container\n");
00825 ao2_ref(c1, -1);
00826 handle_astobj2_stats(fd, 0, NULL);
00827 return 0;
00828 }
00829
00830 static struct ast_cli_entry cli_astobj2[] = {
00831 { { "astobj2", "stats", NULL },
00832 handle_astobj2_stats, "Print astobj2 statistics", },
00833 { { "astobj2", "test", NULL } , handle_astobj2_test, "Test astobj2", },
00834 };
00835 #endif
00836
00837 int astobj2_init(void)
00838 {
00839 #ifdef AO2_DEBUG
00840 ast_cli_register_multiple(cli_astobj2, ARRAY_LEN(cli_astobj2));
00841 #endif
00842
00843 return 0;
00844 }