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
  21 #include <vppinfra/bihash_8_8.h>
  22 #include <vppinfra/bihash_template.h>
  23
  24 #include <vppinfra/bihash_template.c>
  25
  26 typedef struct
  27 {
  28   u64 seed;
  29   u32 nbuckets;
  30   u32 nitems;
  31   u32 ncycles;
  32   u32 report_every_n;
  33   u32 search_iter;
  34   int careful_delete_tests;
  35   int verbose;
  36   int non_random_keys;
  37   uword *key_hash;
  38   u64 *keys;
  39   uword hash_memory_size;
  40     BVT (clib_bihash) hash;
  41   clib_time_t clib_time;
  42
  43   unformat_input_t *input;
  44
  45 } test_main_t;
  46
  47 test_main_t test_main;
  48
  49 uword
  50 vl (void *v)
  51 {
  52   return vec_len (v);
  53 }
  54
  55 static clib_error_t *
  56 test_bihash_vec64 (test_main_t * tm)
  57 {
  58   u32 user_buckets = 1228800;
  59   u32 user_memory_size = 209715200;
  60   BVT (clib_bihash_kv) kv;
  61   int i, j;
  62   f64 before;
  63   f64 *cum_times = 0;
  64   BVT (clib_bihash) * h;
  65
  66   h = &tm->hash;
  67
  68   BV (clib_bihash_init) (h, "test", user_buckets, user_memory_size);
  69
  70   before = clib_time_now (&tm->clib_time);
  71
  72   for (j = 0; j < 10; j++)
  73     {
  74       for (i = 1; i <= j * 1000 + 1; i++)
  75         {
  76           kv.key = i;
  77           kv.value = 1;
  78
  79           BV (clib_bihash_add_del) (h, &kv, 1 /* is_add */ );
  80         }
  81
  82       vec_add1 (cum_times, clib_time_now (&tm->clib_time) - before);
  83     }
  84
  85   for (j = 0; j < vec_len (cum_times); j++)
  86     fformat (stdout, "Cum time for %d: %.4f (us)\n", (j + 1) * 1000,
  87              cum_times[j] * 1e6);
  88
  89   return 0;
  90 }
  91
  92 static clib_error_t *
  93 test_bihash (test_main_t * tm)
  94 {
  95   int i, j;
  96   uword *p;
  97   uword total_searches;
  98   f64 before, delta;
  99   BVT (clib_bihash) * h;
 100   BVT (clib_bihash_kv) kv;
 101   u32 acycle;
 102
 103   h = &tm->hash;
 104
 105   BV (clib_bihash_init) (h, "test", tm->nbuckets, tm->hash_memory_size);
 106
 107   for (acycle = 0; acycle < tm->ncycles; acycle++)
 108     {
 109       if ((acycle % tm->report_every_n) == 0)
 110         {
 111           fformat (stdout, "Cycle %lld out of %lld...\n",
 112                    acycle, tm->ncycles);
 113
 114           fformat (stdout, "Pick %lld unique %s keys...\n",
 115                    tm->nitems, tm->non_random_keys ? "non-random" : "random");
 116         }
 117
 118       for (i = 0; i < tm->nitems; i++)
 119         {
 120           u64 rndkey;
 121
 122           if (tm->non_random_keys == 0)
 123             {
 124
 125             again:
 126               rndkey = random_u64 (&tm->seed);
 127
 128               p = hash_get (tm->key_hash, rndkey);
 129               if (p)
 130                 goto again;
 131             }
 132           else
 133             rndkey = (u64) (i + 1) << 16;
 134           rndkey += acycle;
 135
 136           hash_set (tm->key_hash, rndkey, i + 1);
 137           vec_add1 (tm->keys, rndkey);
 138         }
 139
 140
 141       if ((acycle % tm->report_every_n) == 0)
 142         fformat (stdout, "Add items...\n");
 143
 144       for (i = 0; i < tm->nitems; i++)
 145         {
 146           kv.key = tm->keys[i];
 147           kv.value = i + 1;
 148
 149           BV (clib_bihash_add_del) (h, &kv, 1 /* is_add */ );
 150
 151           if (tm->verbose > 1)
 152             {
 153               fformat (stdout, "--------------------\n");
 154               fformat (stdout, "After adding key %llu value %lld...\n",
 155                        tm->keys[i], (u64) (i + 1));
 156               fformat (stdout, "%U", BV (format_bihash), h,
 157                        2 /* very verbose */ );
 158             }
 159         }
 160
 161       if ((acycle % tm->report_every_n) == 0)
 162         {
 163           fformat (stdout, "%U", BV (format_bihash), h,
 164                    0 /* very verbose */ );
 165
 166           fformat (stdout, "Search for items %d times...\n", tm->search_iter);
 167         }
 168
 169       before = clib_time_now (&tm->clib_time);
 170
 171       for (j = 0; j < tm->search_iter; j++)
 172         {
 173           for (i = 0; i < tm->nitems; i++)
 174             {
 175               kv.key = tm->keys[i];
 176               if (BV (clib_bihash_search) (h, &kv, &kv) < 0)
 177                 if (BV (clib_bihash_search) (h, &kv, &kv) < 0)
 178                   clib_warning
 179                     ("[%d] search for key %lld failed unexpectedly\n", i,
 180                      tm->keys[i]);
 181               if (kv.value != (u64) (i + 1))
 182                 clib_warning
 183                   ("[%d] search for key %lld returned %lld, not %lld\n", i,
 184                    tm->keys, kv.value, (u64) (i + 1));
 185             }
 186         }
 187
 188       if ((acycle % tm->report_every_n) == 0)
 189         {
 190           delta = clib_time_now (&tm->clib_time) - before;
 191           total_searches = (uword) tm->search_iter * (uword) tm->nitems;
 192
 193           if (delta > 0)
 194             fformat (stdout, "%.f searches per second\n",
 195                      ((f64) total_searches) / delta);
 196
 197           fformat (stdout, "%lld searches in %.6f seconds\n", total_searches,
 198                    delta);
 199
 200           fformat (stdout, "Standard E-hash search for items %d times...\n",
 201                    tm->search_iter);
 202         }
 203
 204       before = clib_time_now (&tm->clib_time);
 205
 206       for (j = 0; j < tm->search_iter; j++)
 207         {
 208           for (i = 0; i < tm->nitems; i++)
 209             {
 210               p = hash_get (tm->key_hash, tm->keys[i]);
 211               if (p == 0 || p[0] != (uword) (i + 1))
 212                 clib_warning ("ugh, couldn't find %lld\n", tm->keys[i]);
 213             }
 214         }
 215
 216       delta = clib_time_now (&tm->clib_time) - before;
 217       total_searches = (uword) tm->search_iter * (uword) tm->nitems;
 218
 219       if ((acycle % tm->report_every_n) == 0)
 220         {
 221           fformat (stdout, "%lld searches in %.6f seconds\n",
 222                    total_searches, delta);
 223
 224           if (delta > 0)
 225             fformat (stdout, "%.f searches per second\n",
 226                      ((f64) total_searches) / delta);
 227           fformat (stdout, "Delete items...\n");
 228         }
 229
 230       for (i = 0; i < tm->nitems; i++)
 231         {
 232           int j;
 233           int rv;
 234
 235           kv.key = tm->keys[i];
 236           kv.value = (u64) (i + 1);
 237           rv = BV (clib_bihash_add_del) (h, &kv, 0 /* is_add */ );
 238
 239           if (rv < 0)
 240             clib_warning ("delete key %lld not ok but should be",
 241                           tm->keys[i]);
 242
 243           if (tm->careful_delete_tests)
 244             {
 245               for (j = 0; j < tm->nitems; j++)
 246                 {
 247                   kv.key = tm->keys[j];
 248                   rv = BV (clib_bihash_search) (h, &kv, &kv);
 249                   if (j <= i && rv >= 0)
 250                     {
 251                       clib_warning
 252                         ("i %d j %d search ok but should not be, value %lld",
 253                          i, j, kv.value);
 254                     }
 255                   if (j > i && rv < 0)
 256                     {
 257                       clib_warning ("i %d j %d search not ok but should be",
 258                                     i, j);
 259                     }
 260                 }
 261             }
 262         }
 263       if ((acycle % tm->report_every_n) == 0)
 264         {
 265           struct rusage r_usage;
 266           getrusage (RUSAGE_SELF, &r_usage);
 267           fformat (stdout, "Kernel RSS: %ld bytes\n", r_usage.ru_maxrss);
 268           fformat (stdout, "%U\n", BV (format_bihash), h, 0 /* verbose */ );
 269         }
 270
 271       /* Clean up side-bet hash table and random key vector */
 272       hash_free (tm->key_hash);
 273       vec_reset_length (tm->keys);
 274       /* Recreate hash table if we're going to need it again */
 275       if (acycle != (tm->ncycles - 1))
 276         tm->key_hash = hash_create (tm->nitems, sizeof (uword));
 277     }
 278
 279   fformat (stdout, "End of run, should be empty...\n");
 280
 281   fformat (stdout, "%U", BV (format_bihash), h, 0 /* very verbose */ );
 282   return 0;
 283 }
 284
 285 clib_error_t *
 286 test_bihash_cache (test_main_t * tm)
 287 {
 288   u32 lru;
 289   BVT (clib_bihash_bucket) _b, *b = &_b;
 290
 291   BV (clib_bihash_reset_cache) (b);
 292
 293   fformat (stdout, "Initial LRU config: %U\n", BV (format_bihash_lru), b);
 294
 295   BV (clib_bihash_update_lru_not_inline) (b, 3);
 296
 297   fformat (stdout, "use slot 3, LRU config: %U\n", BV (format_bihash_lru), b);
 298
 299   BV (clib_bihash_update_lru) (b, 1);
 300
 301   fformat (stdout, "use slot 1 LRU config: %U\n", BV (format_bihash_lru), b);
 302
 303   lru = BV (clib_bihash_get_lru) (b);
 304
 305   fformat (stdout, "least-recently-used is %d\n", lru);
 306
 307   BV (clib_bihash_update_lru) (b, 4);
 308
 309   fformat (stdout, "use slot 4 LRU config: %U\n", BV (format_bihash_lru), b);
 310
 311   lru = BV (clib_bihash_get_lru) (b);
 312
 313   fformat (stdout, "least-recently-used is %d\n", lru);
 314
 315   return 0;
 316 }
 317
 318 clib_error_t *
 319 test_bihash_main (test_main_t * tm)
 320 {
 321   unformat_input_t *i = tm->input;
 322   clib_error_t *error;
 323   int which = 0;
 324
 325   tm->report_every_n = 1;
 326   tm->hash_memory_size = 4095ULL << 20;
 327
 328   while (unformat_check_input (i) != UNFORMAT_END_OF_INPUT)
 329     {
 330       if (unformat (i, "seed %u", &tm->seed))
 331         ;
 332
 333       else if (unformat (i, "nbuckets %d", &tm->nbuckets))
 334         ;
 335       else if (unformat (i, "non-random-keys"))
 336         tm->non_random_keys = 1;
 337       else if (unformat (i, "nitems %d", &tm->nitems))
 338         ;
 339       else if (unformat (i, "ncycles %d", &tm->ncycles))
 340         ;
 341       else if (unformat (i, "careful %d", &tm->careful_delete_tests))
 342         ;
 343       else if (unformat (i, "verbose %d", &tm->verbose))
 344         ;
 345       else if (unformat (i, "search %d", &tm->search_iter))
 346         ;
 347       else if (unformat (i, "report-every %d", &tm->report_every_n))
 348         ;
 349       else if (unformat (i, "memory-size %U",
 350                          unformat_memory_size, &tm->hash_memory_size))
 351         ;
 352       else if (unformat (i, "vec64"))
 353         which = 1;
 354       else if (unformat (i, "cache"))
 355         which = 2;
 356
 357       else if (unformat (i, "verbose"))
 358         tm->verbose = 1;
 359       else
 360         return clib_error_return (0, "unknown input '%U'",
 361                                   format_unformat_error, i);
 362     }
 363
 364   /* Preallocate hash table, key vector */
 365   tm->key_hash = hash_create (tm->nitems, sizeof (uword));
 366   vec_validate (tm->keys, tm->nitems - 1);
 367   _vec_len (tm->keys) = 0;
 368
 369
 370   switch (which)
 371     {
 372     case 0:
 373       error = test_bihash (tm);
 374       break;
 375
 376     case 1:
 377       error = test_bihash_vec64 (tm);
 378       break;
 379
 380     case 2:
 381       error = test_bihash_cache (tm);
 382       break;
 383
 384     default:
 385       return clib_error_return (0, "no such test?");
 386     }
 387
 388   return error;
 389 }
 390
 391 #ifdef CLIB_UNIX
 392 int
 393 main (int argc, char *argv[])
 394 {
 395   unformat_input_t i;
 396   clib_error_t *error;
 397   test_main_t *tm = &test_main;
 398
 399   clib_mem_init (0, 4095ULL << 20);
 400
 401   tm->input = &i;
 402   tm->seed = 0xdeaddabe;
 403
 404   tm->nbuckets = 2;
 405   tm->nitems = 5;
 406   tm->ncycles = 1;
 407   tm->verbose = 1;
 408   tm->search_iter = 1;
 409   tm->careful_delete_tests = 0;
 410   clib_time_init (&tm->clib_time);
 411
 412   unformat_init_command_line (&i, argv);
 413   error = test_bihash_main (tm);
 414   unformat_free (&i);
 415
 416   if (error)
 417     {
 418       clib_error_report (error);
 419       return 1;
 420     }
 421   return 0;
 422 }
 423 #endif /* CLIB_UNIX */
 424
 425 /*
 426  * fd.io coding-style-patch-verification: ON
 427  *
 428  * Local Variables:
 429  * eval: (c-set-style "gnu")
 430  * End:
 431  */