utils/hashtest2.c

   1 /*
   2  * Asterisk -- An open source telephony toolkit.
   3  *
   4  * Copyright (C) 2007, Steve Murphy
   5  *
   6  * Steve Murphy <murf@digium.com>
   7  *
   8  * See http://www.asterisk.org for more information about
   9  * the Asterisk project. Please do not directly contact
  10  * any of the maintainers of this project for assistance;
  11  * the project provides a web site, mailing lists and IRC
  12  * channels for your use.
  13  *
  14  * This program is free software, distributed under the terms of
  15  * the GNU General Public License Version 2. See the LICENSE file
  16  * at the top of the source tree.
  17  */
  18 /*! \file
  19  *
  20  *  \brief A program to thoroughly thrash a hash table, testing
  21  *         out locking safety, and making sure all functionality
  22  *         is functioning. Run with 5 or more threads to get that
  23  *         fully intense firestorm of activity. If your
  24  *         hash tables don't crash, lock up, or go weird, it must
  25  *         be good code! Even features some global counters
  26  *         that will get slightly behind because they aren't lock-protected.
  27  *
  28  *  \author Steve Murphy <murf@digium.com>
  29  */
  30
  31 #include "asterisk.h"
  32
  33 ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
  34
  35 #include <pthread.h>
  36 #include <sys/stat.h>
  37 #include <signal.h>
  38
  39 #include "asterisk/lock.h"
  40 #include "asterisk/astobj2.h"
  41 #include "asterisk/channel.h"
  42 #include "asterisk/utils.h"
  43 #include "asterisk/module.h"
  44
  45 int testno = 2;
  46
  47 /* stuff we need to make this work with the astobj2 stuff */
  48 #if !defined(LOW_MEMORY)
  49 int64_t ast_mark(int prof_id, int x)
  50 {
  51         return 0;
  52 }
  53 #endif
  54
  55 /* my OBJECT */
  56 struct ht_element
  57 {
  58         char *key;
  59         char *val;
  60 };
  61
  62
  63 static int hash_string(const void *obj, const int flags)
  64 {
  65         char *str = ((struct ht_element*)obj)->key;
  66         int total;
  67
  68         for (total=0; *str; str++)
  69         {
  70                 unsigned int tmp = total;
  71                 total <<= 1; /* multiply by 2 */
  72                 total += tmp; /* multiply by 3 */
  73                 total <<= 2; /* multiply by 12 */
  74                 total += tmp; /* multiply by 13 */
  75
  76                 total += ((unsigned int)(*str));
  77         }
  78         if (total < 0)
  79                 total = -total;
  80         return total;
  81 }
  82
  83 static int hashtab_compare_strings(void *a, void *b, int flags)
  84 {
  85         const struct ht_element *ae = a, *be = b;
  86         return !strcmp(ae->key, be->key) ? CMP_MATCH : 0;
  87 }
  88
  89 /* random numbers */
  90
  91 static int my_rand(int incl_low, int incl_high, unsigned int *seedp)
  92 {
  93         if (incl_high == 0)
  94                 return 0;
  95
  96         return incl_low + (rand_r(seedp) % incl_high);
  97 }
  98
  99
 100
 101
 102 /* the testing routines */
 103
 104 static int glob_highwater = 0;
 105 struct ao2_container *glob_hashtab = 0;
 106 unsigned int glob_seed = 0;
 107 int els_removed = 0;
 108 int els_added = 0;
 109 int els_lookedup = 0;
 110 int els_found = 0;
 111 int els_traversals = 0;
 112
 113 /* all the operations to perform on the hashtab */
 114
 115 static void ht_destroy(void *obj)
 116 {
 117         const struct ht_element *o = obj;
 118         if (o->key)
 119                 free(o->key);
 120         if (o->val)
 121                 free(o->val);
 122 }
 123
 124
 125 static void add_element(void)
 126 {
 127         char keybuf[100];
 128         struct ht_element *x = ao2_alloc(sizeof(struct ht_element), ht_destroy);
 129         sprintf(keybuf,"key%08d", glob_highwater++);
 130         x->key = strdup(keybuf);
 131         x->val = strdup("interesting data");
 132 #ifdef DEBUG
 133         printf("+ %s\n", keybuf);
 134 #endif
 135         ao2_link(glob_hashtab, x);
 136
 137         els_added++; /* unprotected, sometimes off, but, not really important, either */
 138 }
 139
 140 static int do_nothing_cb(void *obj, void *arg, int flags)
 141 {
 142         return 0;
 143 }
 144
 145 static void traverse_elements(void)
 146 {
 147 #ifdef DEBUG
 148         printf("Traverse hashtab\n");
 149 #endif
 150         ao2_callback(glob_hashtab, OBJ_NODATA, do_nothing_cb, NULL);
 151         els_traversals++; /* unprotected, sometimes off, but, not really important, either */
 152 }
 153
 154 static void * del_element(unsigned int *seedp)
 155 {
 156         char keybuf[100];
 157         struct ht_element *el, lookup;
 158         int x;
 159
 160         /* pick a random element from 0 to highwater-1 */
 161         x = my_rand(0,glob_highwater-1,seedp);
 162         sprintf(keybuf, "key%08d", x);
 163 #ifdef DEBUG
 164         printf("- %s", keybuf);
 165 #endif
 166         lookup.key = keybuf;
 167         el = ao2_find(glob_hashtab, &lookup, OBJ_POINTER);
 168         if (el) {
 169 #ifdef DEBUG
 170                 printf("...YES (el=%x)\n", (unsigned long)el);
 171 #endif
 172                 ao2_unlink(glob_hashtab, el); /* mistakenly tried to use ao2_ref(c,-2) here to unlink. Bad Boy! */
 173                 els_removed++;
 174         } else {
 175 #ifdef DEBUG
 176                 printf("...NO.\n");
 177 #endif
 178                 return 0;
 179         }
 180         return el;
 181 }
 182
 183 static int lookup_element(unsigned int *seedp)
 184 {
 185         char keybuf[100];
 186         struct ht_element *el, lookup;
 187         int x;
 188
 189         /* pick a random element from 0 to highwater-1 */
 190         x = my_rand(0,glob_highwater-1,seedp);
 191         sprintf(keybuf, "key%08d", x);
 192         lookup.key = keybuf;
 193         el = ao2_find(glob_hashtab, &lookup, OBJ_POINTER);
 194         els_lookedup++;
 195         if (el) {
 196                 els_found++;
 197                 ao2_ref(el, -1); /* toss out this ref, no longer needed */
 198                 return 1;
 199         } else {
 200                 return 0;
 201         }
 202 }
 203
 204
 205 static void *hashtest(void *data)
 206 {
 207         int my_els_removed = 0;
 208         int my_els_added = 0;
 209         int my_els_lookedup = 0;
 210         int my_els_found = 0;
 211         int my_els_traversals = 0;
 212         int my_testno = testno++;
 213         int its;
 214
 215         /* data will be a random number == use as a seed for random numbers */
 216         unsigned long seed = (unsigned long)data;
 217         printf("hashtest thread created... test beginning\n");
 218
 219         /* main test routine-- a global hashtab exists, pound it like crazy  */
 220         for(its=0;its<100000;its++)
 221         {
 222                 void *seed2 = &seed;
 223                 int op = my_rand(0,100, seed2);
 224                 if (op<60) {
 225                         my_els_lookedup++;
 226 #ifdef DEBUG
 227                         printf("%d[%d]: LOOKUP\n", my_testno, its);
 228 #endif
 229                         if ((my_els_lookedup%1000)==0) {
 230                                 printf(".");
 231                                 fflush(stdout);
 232                         }
 233                         if (lookup_element(seed2))
 234                                 my_els_found++;
 235                 } else if (op < 61) { /* make this 61 and it'll take 16 minutes to run */
 236 #ifdef DEBUG
 237                         printf("%d[%d]: TRAVERSE\n", my_testno, its);
 238 #endif
 239                         traverse_elements();
 240                         my_els_traversals++;
 241
 242                 } else if (op < 80) {
 243 #ifdef DEBUG
 244                         printf("%d[%d]: REMOVE\n", my_testno, its);
 245 #endif
 246                         if (del_element(seed2))
 247                                 my_els_removed++;
 248                 } else {
 249                         my_els_added++;
 250 #ifdef DEBUG
 251                         printf("%d[%d]: ADD\n", my_testno, its);
 252 #endif
 253                         add_element();
 254                 }
 255         }
 256         printf("\nhashtest thread %d exiting.... lookups=%d/%d, added=%d, removed=%d, traversals=%d;\n",
 257                    my_testno, my_els_found, my_els_lookedup, my_els_added, my_els_removed, my_els_traversals);
 258         printf("\ntotals..................... lookups=%d/%d, added=%d, removed=%d; traversals=%d\n",
 259                    els_found, els_lookedup, els_added, els_removed, els_traversals);
 260         pthread_exit(0);
 261         return NULL;
 262 }
 263
 264 static void run_hashtest(int numthr)
 265 {
 266         pthread_t thr[numthr];
 267         void *thrres[numthr];
 268         int i;
 269
 270         /* init a single global hashtab, then... */
 271         glob_hashtab = ao2_container_alloc(180000, hash_string, hashtab_compare_strings);
 272
 273         /* set a random seed  */
 274         glob_seed = (unsigned int)time(0);
 275         srand(glob_seed);
 276
 277         /* create threads, each running hashtest */
 278         for(i=0;i<numthr;i++)
 279         {
 280                 unsigned long z = rand();
 281
 282                 printf("starting hashtest thread %d....\n",i+1);
 283                 if (ast_pthread_create(&thr[i], NULL, hashtest, (void*)z)) {
 284                         printf("Sorry, couldn't create thread #%d\n", i+1);
 285                 }
 286                 printf("hashtest thread spawned.... \n");
 287         }
 288         /* collect threads, each running hashtest */
 289         for(i=0;i<numthr;i++)
 290         {
 291                 printf("waiting for thread %d....\n", i+1);
 292                 if (pthread_join(thr[i], &thrres[i])) {
 293                         printf("Sorry, couldn't join thread #%d\n", i+1);
 294                 }
 295                 printf("hashtest thread %d done.... \n",i+1);
 296         }
 297         /* user has to kill/intr the process to stop the test? */
 298 }
 299
 300
 301 int main(int argc,char **argv)
 302 {
 303         if (argc < 2 || argc > 2 || atoi(argv[1]) < 1)
 304         {
 305                 printf("Usage: hashtest <number of threads>\n");
 306                 exit(1);
 307         }
 308
 309         /* one arg == number of threads to create */
 310         run_hashtest(atoi(argv[1]));
 311
 312         return 0;
 313 }
 314
 315 #if !defined(LOW_MEMORY)
 316 int ast_add_profile(const char *x, uint64_t scale)
 317 {
 318         return 0;
 319 }
 320 #endif
 321
 322 int ast_loader_register(int (*updater)(void))
 323 {
 324         return 1;
 325 }
 326
 327 int ast_loader_unregister(int (*updater)(void))
 328 {
 329         return 1;
 330 }
 331 void ast_module_register(const struct ast_module_info *x)
 332 {
 333 }
 334
 335 void ast_module_unregister(const struct ast_module_info *x)
 336 {
 337 }
 338
 339
 340 void ast_register_file_version(const char *file, const char *version);
 341 void ast_register_file_version(const char *file, const char *version)
 342 {
 343 }
 344
 345 void ast_unregister_file_version(const char *file);
 346 void ast_unregister_file_version(const char *file)
 347 {
 348
 349 }
 350
 351 void ast_log(int level, const char *file, int line, const char *function, const char *fmt, ...)
 352 {
 353         va_list vars;
 354         va_start(vars,fmt);
 355         printf("LOG: lev:%d file:%s  line:%d func: %s  ",
 356                    level, file, line, function);
 357         vprintf(fmt, vars);
 358         fflush(stdout);
 359         va_end(vars);
 360 }
 361
 362 void __ast_verbose(const char *file, int line, const char *func, const char *fmt, ...)
 363 {
 364         va_list vars;
 365         va_start(vars,fmt);
 366
 367         printf("VERBOSE: ");
 368         vprintf(fmt, vars);
 369         fflush(stdout);
 370         va_end(vars);
 371 }
 372
 373 void ast_register_thread(char *name)
 374 {
 375
 376 }
 377
 378 void ast_unregister_thread(void *id)
 379 {
 380 }
 381
 382 #ifdef HAVE_BKTR
 383 struct ast_bt* ast_bt_create(void)
 384 {
 385         return NULL;
 386 }
 387
 388 int ast_bt_get_addresses(struct ast_bt *bt)
 389 {
 390         return -1;
 391 }
 392
 393 void *ast_bt_destroy(struct ast_bt *bt)
 394 {
 395         return NULL;
 396 }
 397 #endif