src/vppinfra/test_bihash_template.c

   1 /*
   2  * Copyright (c) 2015 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 #include <vppinfra/time.h>
  16 #include <vppinfra/cache.h>
  17 #include <vppinfra/error.h>
  18 #include <sys/resource.h>
  19 #include <stdio.h>
  20 #include <pthread.h>
  21
  22 #include <vppinfra/bihash_8_8.h>
  23 #include <vppinfra/bihash_template.h>
  24
  25 #include <vppinfra/bihash_template.c>
  26
  27 typedef struct
  28 {
  29   volatile u32 thread_barrier;
  30   volatile u32 threads_running;
  31   volatile u64 sequence_number;
  32   u64 seed;
  33   u32 nbuckets;
  34   u32 nitems;
  35   u32 ncycles;
  36   u32 report_every_n;
  37   u32 search_iter;
  38   int careful_delete_tests;
  39   int verbose;
  40   int non_random_keys;
  41   u32 nthreads;
  42   uword *key_hash;
  43   u64 *keys;
  44   uword hash_memory_size;
  45     BVT (clib_bihash) hash;
  46   clib_time_t clib_time;
  47   void *global_heap;
  48
  49   unformat_input_t *input;
  50
  51 } test_main_t;
  52
  53 test_main_t test_main;
  54
  55 uword
  56 vl (void *v)
  57 {
  58   return vec_len (v);
  59 }
  60
  61 static clib_error_t *
  62 test_bihash_vec64 (test_main_t * tm)
  63 {
  64   u32 user_buckets = 1228800;
  65   u32 user_memory_size = 209715200;
  66   BVT (clib_bihash_kv) kv;
  67   int i, j;
  68   f64 before;
  69   f64 *cum_times = 0;
  70   BVT (clib_bihash) * h;
  71
  72   h = &tm->hash;
  73
  74   BV (clib_bihash_init) (h, "test", user_buckets, user_memory_size);
  75
  76   before = clib_time_now (&tm->clib_time);
  77
  78   for (j = 0; j < 10; j++)
  79     {
  80       for (i = 1; i <= j * 1000 + 1; i++)
  81         {
  82           kv.key = i;
  83           kv.value = 1;
  84
  85           BV (clib_bihash_add_del) (h, &kv, 1 /* is_add */ );
  86         }
  87
  88       vec_add1 (cum_times, clib_time_now (&tm->clib_time) - before);
  89     }
  90
  91   for (j = 0; j < vec_len (cum_times); j++)
  92     fformat (stdout, "Cum time for %d: %.4f (us)\n", (j + 1) * 1000,
  93              cum_times[j] * 1e6);
  94
  95   return 0;
  96 }
  97
  98 void *
  99 test_bihash_thread_fn (void *arg)
 100 {
 101   BVT (clib_bihash) * h;
 102   BVT (clib_bihash_kv) kv;
 103   test_main_t *tm = &test_main;
 104
 105   int i, j;
 106
 107   u32 my_thread_index = (u32) (u64) arg;
 108   __os_thread_index = my_thread_index;
 109   clib_mem_set_per_cpu_heap (tm->global_heap);
 110
 111   while (tm->thread_barrier)
 112     ;
 113
 114   h = &tm->hash;
 115
 116   for (i = 0; i < tm->ncycles; i++)
 117     {
 118       for (j = 0; j < tm->nitems; j++)
 119         {
 120           kv.key = ((u64) my_thread_index << 32) | (u64) j;
 121           kv.value = ((u64) my_thread_index << 32) | (u64) j;
 122           (void) __atomic_add_fetch (&tm->sequence_number, 1,
 123                                      __ATOMIC_ACQUIRE);
 124           BV (clib_bihash_add_del) (h, &kv, 1 /* is_add */ );
 125         }
 126       for (j = 0; j < tm->nitems; j++)
 127         {
 128           kv.key = ((u64) my_thread_index << 32) | (u64) j;
 129           kv.value = ((u64) my_thread_index << 32) | (u64) j;
 130           (void) __atomic_add_fetch (&tm->sequence_number, 1,
 131                                      __ATOMIC_ACQUIRE);
 132           BV (clib_bihash_add_del) (h, &kv, 0 /* is_add */ );
 133         }
 134     }
 135
 136   (void) __atomic_sub_fetch (&tm->threads_running, 1, __ATOMIC_ACQUIRE);
 137   while (1)
 138     {
 139       struct timespec ts, tsrem;
 140       ts.tv_sec = 1;
 141       ts.tv_nsec = 0;
 142
 143       while (nanosleep (&ts, &tsrem) < 0)
 144         ts = tsrem;
 145     }
 146   return (0);                   /* not so much */
 147 }
 148
 149 static clib_error_t *
 150 test_bihash_threads (test_main_t * tm)
 151 {
 152   int i;
 153   pthread_t handle;
 154   BVT (clib_bihash) * h;
 155   int rv;
 156
 157   h = &tm->hash;
 158
 159   BV (clib_bihash_init) (h, "test", tm->nbuckets, tm->hash_memory_size);
 160
 161   tm->thread_barrier = 1;
 162
 163   /* Start the worker threads */
 164   for (i = 0; i < tm->nthreads; i++)
 165     {
 166       rv = pthread_create (&handle, NULL, test_bihash_thread_fn,
 167                            (void *) (u64) i);
 168       if (rv)
 169         {
 170           clib_unix_warning ("pthread_create returned %d", rv);
 171         }
 172     }
 173   tm->threads_running = i;
 174   tm->sequence_number = 0;
 175   CLIB_MEMORY_BARRIER ();
 176
 177   /* start the workers */
 178   tm->thread_barrier = 0;
 179
 180   while (tm->threads_running)
 181     {
 182       struct timespec ts, tsrem;
 183       ts.tv_sec = 0;
 184       ts.tv_nsec = 20 * 1000 * 1000;    /* sleep for 20ms at a time */
 185
 186       while (nanosleep (&ts, &tsrem) < 0)
 187         ts = tsrem;
 188     }
 189
 190   return 0;
 191 }
 192
 193
 194 static clib_error_t *
 195 test_bihash (test_main_t * tm)
 196 {
 197   int i, j;
 198   uword *p;
 199   uword total_searches;
 200   f64 before, delta;
 201   BVT (clib_bihash) * h;
 202   BVT (clib_bihash_kv) kv;
 203   u32 acycle;
 204
 205   h = &tm->hash;
 206
 207   BV (clib_bihash_init) (h, "test", tm->nbuckets, tm->hash_memory_size);
 208
 209   for (acycle = 0; acycle < tm->ncycles; acycle++)
 210     {
 211       if ((acycle % tm->report_every_n) == 0)
 212         {
 213           fformat (stdout, "Cycle %lld out of %lld...\n",
 214                    acycle, tm->ncycles);
 215
 216           fformat (stdout, "Pick %lld unique %s keys...\n",
 217                    tm->nitems, tm->non_random_keys ? "non-random" : "random");
 218         }
 219
 220       for (i = 0; i < tm->nitems; i++)
 221         {
 222           u64 rndkey;
 223
 224           if (tm->non_random_keys == 0)
 225             {
 226
 227             again:
 228               rndkey = random_u64 (&tm->seed);
 229
 230               p = hash_get (tm->key_hash, rndkey);
 231               if (p)
 232                 goto again;
 233             }
 234           else
 235             rndkey = (u64) (i + 1) << 16;
 236           rndkey += acycle;
 237
 238           hash_set (tm->key_hash, rndkey, i + 1);
 239           vec_add1 (tm->keys, rndkey);
 240         }
 241
 242
 243       if ((acycle % tm->report_every_n) == 0)
 244         fformat (stdout, "Add items...\n");
 245
 246       for (i = 0; i < tm->nitems; i++)
 247         {
 248           kv.key = tm->keys[i];
 249           kv.value = i + 1;
 250
 251           BV (clib_bihash_add_del) (h, &kv, 1 /* is_add */ );
 252
 253           if (tm->verbose > 1)
 254             {
 255               fformat (stdout, "--------------------\n");
 256               fformat (stdout, "After adding key %llu value %lld...\n",
 257                        tm->keys[i], (u64) (i + 1));
 258               fformat (stdout, "%U", BV (format_bihash), h,
 259                        2 /* very verbose */ );
 260             }
 261         }
 262
 263       if ((acycle % tm->report_every_n) == 0)
 264         {
 265           fformat (stdout, "%U", BV (format_bihash), h,
 266                    0 /* very verbose */ );
 267
 268           fformat (stdout, "Search for items %d times...\n", tm->search_iter);
 269         }
 270
 271       before = clib_time_now (&tm->clib_time);
 272
 273       for (j = 0; j < tm->search_iter; j++)
 274         {
 275           for (i = 0; i < tm->nitems; i++)
 276             {
 277               kv.key = tm->keys[i];
 278               if (BV (clib_bihash_search) (h, &kv, &kv) < 0)
 279                 if (BV (clib_bihash_search) (h, &kv, &kv) < 0)
 280                   clib_warning
 281                     ("[%d] search for key %lld failed unexpectedly\n", i,
 282                      tm->keys[i]);
 283               if (kv.value != (u64) (i + 1))
 284                 clib_warning
 285                   ("[%d] search for key %lld returned %lld, not %lld\n", i,
 286                    tm->keys, kv.value, (u64) (i + 1));
 287             }
 288         }
 289
 290       if ((acycle % tm->report_every_n) == 0)
 291         {
 292           delta = clib_time_now (&tm->clib_time) - before;
 293           total_searches = (uword) tm->search_iter * (uword) tm->nitems;
 294
 295           if (delta > 0)
 296             fformat (stdout, "%.f searches per second\n",
 297                      ((f64) total_searches) / delta);
 298
 299           fformat (stdout, "%lld searches in %.6f seconds\n", total_searches,
 300                    delta);
 301
 302           fformat (stdout, "Standard E-hash search for items %d times...\n",
 303                    tm->search_iter);
 304         }
 305
 306       before = clib_time_now (&tm->clib_time);
 307
 308       for (j = 0; j < tm->search_iter; j++)
 309         {
 310           for (i = 0; i < tm->nitems; i++)
 311             {
 312               p = hash_get (tm->key_hash, tm->keys[i]);
 313               if (p == 0 || p[0] != (uword) (i + 1))
 314                 clib_warning ("ugh, couldn't find %lld\n", tm->keys[i]);
 315             }
 316         }
 317
 318       delta = clib_time_now (&tm->clib_time) - before;
 319       total_searches = (uword) tm->search_iter * (uword) tm->nitems;
 320
 321       if ((acycle % tm->report_every_n) == 0)
 322         {
 323           fformat (stdout, "%lld searches in %.6f seconds\n",
 324                    total_searches, delta);
 325
 326           if (delta > 0)
 327             fformat (stdout, "%.f searches per second\n",
 328                      ((f64) total_searches) / delta);
 329           fformat (stdout, "Delete items...\n");
 330         }
 331
 332       for (i = 0; i < tm->nitems; i++)
 333         {
 334           int j;
 335           int rv;
 336
 337           kv.key = tm->keys[i];
 338           kv.value = (u64) (i + 1);
 339           rv = BV (clib_bihash_add_del) (h, &kv, 0 /* is_add */ );
 340
 341           if (rv < 0)
 342             clib_warning ("delete key %lld not ok but should be",
 343                           tm->keys[i]);
 344
 345           if (tm->careful_delete_tests)
 346             {
 347               for (j = 0; j < tm->nitems; j++)
 348                 {
 349                   kv.key = tm->keys[j];
 350                   rv = BV (clib_bihash_search) (h, &kv, &kv);
 351                   if (j <= i && rv >= 0)
 352                     {
 353                       clib_warning
 354                         ("i %d j %d search ok but should not be, value %lld",
 355                          i, j, kv.value);
 356                     }
 357                   if (j > i && rv < 0)
 358                     {
 359                       clib_warning ("i %d j %d search not ok but should be",
 360                                     i, j);
 361                     }
 362                 }
 363             }
 364         }
 365       if ((acycle % tm->report_every_n) == 0)
 366         {
 367           struct rusage r_usage;
 368           getrusage (RUSAGE_SELF, &r_usage);
 369           fformat (stdout, "Kernel RSS: %ld bytes\n", r_usage.ru_maxrss);
 370           fformat (stdout, "%U\n", BV (format_bihash), h, 0 /* verbose */ );
 371         }
 372
 373       /* Clean up side-bet hash table and random key vector */
 374       hash_free (tm->key_hash);
 375       vec_reset_length (tm->keys);
 376       /* Recreate hash table if we're going to need it again */
 377       if (acycle != (tm->ncycles - 1))
 378         tm->key_hash = hash_create (tm->nitems, sizeof (uword));
 379     }
 380
 381   fformat (stdout, "End of run, should be empty...\n");
 382
 383   fformat (stdout, "%U", BV (format_bihash), h, 0 /* very verbose */ );
 384   return 0;
 385 }
 386
 387 clib_error_t *
 388 test_bihash_main (test_main_t * tm)
 389 {
 390   unformat_input_t *i = tm->input;
 391   clib_error_t *error;
 392   int which = 0;
 393
 394   tm->report_every_n = 1;
 395   tm->hash_memory_size = 4095ULL << 20;
 396
 397   while (unformat_check_input (i) != UNFORMAT_END_OF_INPUT)
 398     {
 399       if (unformat (i, "seed %u", &tm->seed))
 400         ;
 401
 402       else if (unformat (i, "nbuckets %d", &tm->nbuckets))
 403         ;
 404       else if (unformat (i, "non-random-keys"))
 405         tm->non_random_keys = 1;
 406       else if (unformat (i, "nitems %d", &tm->nitems))
 407         ;
 408       else if (unformat (i, "ncycles %d", &tm->ncycles))
 409         ;
 410       else if (unformat (i, "careful %d", &tm->careful_delete_tests))
 411         ;
 412       else if (unformat (i, "verbose %d", &tm->verbose))
 413         ;
 414       else if (unformat (i, "search %d", &tm->search_iter))
 415         ;
 416       else if (unformat (i, "report-every %d", &tm->report_every_n))
 417         ;
 418       else if (unformat (i, "memory-size %U",
 419                          unformat_memory_size, &tm->hash_memory_size))
 420         ;
 421       else if (unformat (i, "vec64"))
 422         which = 1;
 423       else if (unformat (i, "threads %u", &tm->nthreads))
 424         which = 2;
 425       else if (unformat (i, "verbose"))
 426         tm->verbose = 1;
 427       else
 428         return clib_error_return (0, "unknown input '%U'",
 429                                   format_unformat_error, i);
 430     }
 431
 432   /* Preallocate hash table, key vector */
 433   tm->key_hash = hash_create (tm->nitems, sizeof (uword));
 434   vec_validate (tm->keys, tm->nitems - 1);
 435   _vec_len (tm->keys) = 0;
 436
 437
 438   switch (which)
 439     {
 440     case 0:
 441       error = test_bihash (tm);
 442       break;
 443
 444     case 1:
 445       error = test_bihash_vec64 (tm);
 446       break;
 447
 448     case 2:
 449       error = test_bihash_threads (tm);
 450       break;
 451
 452     default:
 453       return clib_error_return (0, "no such test?");
 454     }
 455
 456   return error;
 457 }
 458
 459 #ifdef CLIB_UNIX
 460 int
 461 main (int argc, char *argv[])
 462 {
 463   unformat_input_t i;
 464   clib_error_t *error;
 465   test_main_t *tm = &test_main;
 466
 467   clib_mem_init (0, 4095ULL << 20);
 468
 469   tm->global_heap = clib_mem_get_per_cpu_heap ();
 470
 471   tm->input = &i;
 472   tm->seed = 0xdeaddabe;
 473
 474   tm->nbuckets = 2;
 475   tm->nitems = 5;
 476   tm->ncycles = 1;
 477   tm->verbose = 1;
 478   tm->search_iter = 1;
 479   tm->careful_delete_tests = 0;
 480   clib_time_init (&tm->clib_time);
 481
 482   unformat_init_command_line (&i, argv);
 483   error = test_bihash_main (tm);
 484   unformat_free (&i);
 485
 486   if (error)
 487     {
 488       clib_error_report (error);
 489       return 1;
 490     }
 491   return 0;
 492 }
 493 #endif /* CLIB_UNIX */
 494
 495 /*
 496  * fd.io coding-style-patch-verification: ON
 497  *
 498  * Local Variables:
 499  * eval: (c-set-style "gnu")
 500  * End:
 501  */