utils/hashtest.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 ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
  33
  34 #include <pthread.h>
  35 #include <sys/stat.h>
  36 #include <signal.h>
  37 #include <errno.h>
  38 #include "asterisk/lock.h"
  39 #include "asterisk/hashtab.h"
  40 #include "asterisk/channel.h"
  41 #include "asterisk/utils.h"
  42 #include "asterisk/module.h"
  43 int testno = 1;
  44
  45 /* stuff we need to make this work with the hashtab stuff */
  46 #if !defined(LOW_MEMORY)
  47 int64_t ast_mark(int prof_id, int x)
  48 {
  49         return 0;
  50 }
  51 #endif
  52
  53 struct ht_element
  54 {
  55         char *key;
  56         char *val;
  57 };
  58
  59 static int hashtab_compare_strings_nocase(const void *a, const void *b)
  60 {
  61         const struct ht_element *ae = a, *be = b;
  62         return ast_hashtab_compare_strings_nocase(ae->key, be->key);
  63 }
  64
  65 #if 0
  66 static int hashtab_compare_strings(const void *a, const void *b)
  67 {
  68         const struct ht_element *ae = a, *be = b;
  69         return ast_hashtab_compare_strings(ae->key, be->key);
  70 }
  71
  72 static unsigned int hashtab_hash_string(const void *obj)
  73 {
  74         const struct ht_element *o = obj;
  75         return ast_hashtab_hash_string((const void *)o->key);
  76 }
  77 #endif
  78
  79 static unsigned int hashtab_hash_string_nocase(const void *obj)
  80 {
  81         const struct ht_element *o = obj;
  82         return ast_hashtab_hash_string_nocase((const void*)o->key);
  83 }
  84
  85 /* random numbers */
  86
  87 static int my_rand(int incl_low, int incl_high, unsigned int *seedp)
  88 {
  89         if (incl_high == 0)
  90                 return 0;
  91
  92         return incl_low + (rand_r(seedp) % incl_high);
  93 }
  94
  95
  96
  97
  98 /* the testing routines */
  99
 100 static int glob_highwater = 0;
 101 struct ast_hashtab *glob_hashtab = 0;
 102 unsigned int glob_seed = 0;
 103 int els_removed = 0;
 104 int els_added = 0;
 105 int els_lookedup = 0;
 106 int els_found = 0;
 107 int els_traversals = 0;
 108
 109 /* all the operations to perform on the hashtab */
 110
 111 static void add_element(void)
 112 {
 113         char keybuf[100];
 114         struct ht_element *x = malloc(sizeof(struct ht_element));
 115         sprintf(keybuf,"key%08d", glob_highwater++);
 116         x->key = strdup(keybuf);
 117         x->val = strdup("interesting data");
 118         ast_hashtab_insert_immediate(glob_hashtab, x);
 119         els_added++;
 120 }
 121
 122 static void traverse_elements(void)
 123 {
 124         struct ht_element *el;
 125         int c=0;
 126         struct ast_hashtab_iter *it = ast_hashtab_start_write_traversal(glob_hashtab);
 127 #ifdef DEBUG
 128         printf("Traverse hashtab\n");
 129 #endif
 130         while ((el = ast_hashtab_next(it))) {
 131                 c++;
 132         }
 133         ast_hashtab_end_traversal(it);
 134         els_traversals++; /* unprotected, sometimes off, but, not really important, either */
 135 }
 136
 137 static void * del_element(unsigned int *seedp)
 138 {
 139         char keybuf[100];
 140         struct ht_element *el, lookup;
 141         int x;
 142
 143         /* pick a random element from 0 to highwater-1 */
 144         x = my_rand(0,glob_highwater-1,seedp);
 145         sprintf(keybuf, "key%08d", x);
 146 #ifdef DEBUG
 147         printf("Removing %s", keybuf);
 148 #endif
 149         lookup.key = keybuf;
 150         el = ast_hashtab_remove_object_via_lookup(glob_hashtab, &lookup);
 151
 152         if (el) {
 153 #ifdef DEBUG
 154                 printf("...YES (el=%x)\n", (unsigned long)el);
 155 #endif
 156                 free(el->key);
 157                 free(el->val);
 158                 free(el);
 159                 els_removed++;
 160         } else {
 161 #ifdef DEBUG
 162                 printf("...NO.\n");
 163 #endif
 164                 return 0;
 165         }
 166
 167
 168         return el;
 169 }
 170
 171 static int lookup_element(unsigned int *seedp)
 172 {
 173         char keybuf[100];
 174         struct ht_element *el, lookup;
 175         int x;
 176
 177         /* pick a random element from 0 to highwater-1 */
 178         x = my_rand(0,glob_highwater-1,seedp);
 179         sprintf(keybuf, "key%08d", x);
 180         lookup.key = keybuf;
 181         el = ast_hashtab_lookup(glob_hashtab, &lookup);
 182         els_lookedup++;
 183         if (el)
 184                 els_found++;
 185         if (el)
 186                 return 1;
 187         return 0;
 188 }
 189
 190
 191 static void *hashtest(void *data)
 192 {
 193         int my_els_removed = 0;
 194         int my_els_added = 0;
 195         int my_els_lookedup = 0;
 196         int my_els_found = 0;
 197         int my_els_traversals = 0;
 198         int my_testno = testno++;
 199         int its;
 200
 201         /* data will be a random number == use as a seed for random numbers */
 202         unsigned long seed = (unsigned long)data;
 203
 204         printf("hashtest thread created... test beginning\n");
 205
 206         /* main test routine-- a global hashtab exists, pound it like crazy  */
 207         for(its=0;its<100000;its++)
 208         {
 209                 void *seed2 = &seed;
 210                 int op = my_rand(0,100, seed2);
 211                 if (op<60) {
 212                         my_els_lookedup++;
 213 #ifdef DEBUG
 214                         printf("%d[%d]: LOOKUP\n", my_testno, its);
 215 #endif
 216                         if ((my_els_lookedup%1000)==0) {
 217                                 printf(".");
 218                                 fflush(stdout);
 219                         }
 220                         if (lookup_element(seed2))
 221                                 my_els_found++;
 222                 } else if (op < 61) { /* make this 61 and it'll take 15 minutes to run */
 223 #ifdef DEBUG
 224                         printf("%d[%d]: TRAVERSE\n", my_testno, its);
 225 #endif
 226                         traverse_elements();
 227                         my_els_traversals++;
 228
 229                 } else if (op < 80) {
 230 #ifdef DEBUG
 231                         printf("%d[%d]: REMOVE\n", my_testno, its);
 232 #endif
 233                         if (del_element(seed2))
 234                                 my_els_removed++;
 235                 } else {
 236                         my_els_added++;
 237 #ifdef DEBUG
 238                         printf("%d[%d]: ADD\n", my_testno, its);
 239 #endif
 240                         add_element();
 241                 }
 242         }
 243         printf("\nhashtest thread %d exiting.... lookups=%d/%d, added=%d, removed=%d, traversals=%d;\n",
 244                    my_testno, my_els_found, my_els_lookedup, my_els_added, my_els_removed, my_els_traversals);
 245         printf("\ntotals..................... lookups=%d/%d, added=%d, removed=%d, traversals=%d;\n",
 246                    els_found, els_lookedup, els_added, els_removed,els_traversals);
 247         pthread_exit(0);
 248 }
 249
 250 static void run_hashtest(int numthr)
 251 {
 252         pthread_t thr[numthr];
 253         void *thrres[numthr];
 254         int i, biggest, resize_cnt, numobjs, numbuckets;
 255
 256         /* init a single global hashtab, then... */
 257         glob_hashtab = ast_hashtab_create(180000, hashtab_compare_strings_nocase, ast_hashtab_resize_java, ast_hashtab_newsize_java, hashtab_hash_string_nocase, 1);
 258         printf("starting with %d elements in the hashtable...\n", ast_hashtab_capacity(glob_hashtab));
 259         /* set a random seed  */
 260         glob_seed = (unsigned int)time(0);
 261         srand(glob_seed);
 262
 263         /* create threads, each running hashtest */
 264         for(i=0;i<numthr;i++)
 265         {
 266                 unsigned long z = rand();
 267
 268                 printf("starting hashtest thread %d....\n",i+1);
 269                 if (ast_pthread_create(&thr[i], NULL, hashtest, (void*)z)) {
 270                         printf("Sorry, couldn't create thread #%d\n", i+1);
 271                 }
 272                 printf("hashtest thread spawned.... \n");
 273         }
 274         /* collect threads, each running hashtest */
 275         for(i=0;i<numthr;i++)
 276         {
 277                 printf("waiting for thread %d....\n", i+1);
 278                 if (pthread_join(thr[i], &thrres[i])) {
 279                         printf("Sorry, couldn't join thread #%d\n", i+1);
 280                 }
 281                 printf("hashtest thread %d done.... \n",i+1);
 282         }
 283         /* user has to kill/intr the process to stop the test? */
 284         ast_hashtab_get_stats(glob_hashtab, &biggest, &resize_cnt, &numobjs, &numbuckets);
 285         printf("Some stats: longest bucket chain: %d;  number of resizes: %d; number of objects: %d;  capacity: %d\n",
 286                         biggest, resize_cnt, numobjs, numbuckets);
 287 }
 288
 289
 290 int main(int argc,char **argv)
 291 {
 292         if (argc < 2 || argc > 2 || atoi(argv[1]) < 1)
 293         {
 294                 printf("Usage: hashtest <number of threads>\n");
 295                 exit(1);
 296         }
 297
 298         /* one arg == number of threads to create */
 299         run_hashtest(atoi(argv[1]));
 300
 301         return 0;
 302 }
 303 #if !defined(LOW_MEMORY)
 304 int  ast_add_profile(const char *x, uint64_t scale)
 305 {
 306         return 0;
 307 }
 308 #endif
 309
 310 int ast_loader_register(int (*updater)(void))
 311 {
 312         return 1;
 313 }
 314
 315 int ast_loader_unregister(int (*updater)(void))
 316 {
 317         return 1;
 318 }
 319 void ast_module_register(const struct ast_module_info *x)
 320 {
 321 }
 322
 323 void ast_module_unregister(const struct ast_module_info *x)
 324 {
 325 }
 326
 327
 328 void ast_register_file_version(const char *file, const char *version);
 329 void ast_register_file_version(const char *file, const char *version)
 330 {
 331 }
 332
 333 void ast_unregister_file_version(const char *file);
 334 void ast_unregister_file_version(const char *file)
 335 {
 336
 337 }
 338
 339 void ast_log(int level, const char *file, int line, const char *function, const char *fmt, ...)
 340 {
 341         va_list vars;
 342         va_start(vars,fmt);
 343         printf("LOG: lev:%d file:%s  line:%d func: %s  ",
 344                    level, file, line, function);
 345         vprintf(fmt, vars);
 346         fflush(stdout);
 347         va_end(vars);
 348 }
 349
 350 void __ast_verbose(const char *file, int line, const char *func, const char *fmt, ...)
 351 {
 352         va_list vars;
 353         va_start(vars,fmt);
 354
 355         printf("VERBOSE: ");
 356         vprintf(fmt, vars);
 357         fflush(stdout);
 358         va_end(vars);
 359 }
 360
 361 void ast_register_thread(char *name)
 362 {
 363
 364 }
 365
 366 void ast_unregister_thread(void *id)
 367 {
 368 }
 369
 370 #ifdef HAVE_BKTR
 371 struct ast_bt *ast_bt_create(void);
 372 struct ast_bt *ast_bt_create(void)
 373 {
 374         return NULL;
 375 }
 376
 377 int ast_bt_get_addresses(struct ast_bt *bt);
 378 int ast_bt_get_addresses(struct ast_bt *bt)
 379 {
 380         return 0;
 381 }
 382
 383 void *ast_bt_destroy(struct ast_bt *bt);
 384 void *ast_bt_destroy(struct ast_bt *bt)
 385 {
 386         return NULL;
 387 }
 388 #endif