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     BVT (clib_bihash) hash;
  40   clib_time_t clib_time;
  41
  42   unformat_input_t *input;
  43
  44 } test_main_t;
  45
  46 test_main_t test_main;
  47
  48 uword
  49 vl (void *v)
  50 {
  51   return vec_len (v);
  52 }
  53
  54 static clib_error_t *
  55 test_bihash_vec64 (test_main_t * tm)
  56 {
  57   u32 user_buckets = 1228800;
  58   u32 user_memory_size = 209715200;
  59   BVT (clib_bihash_kv) kv;
  60   int i, j;
  61   f64 before;
  62   f64 *cum_times = 0;
  63   BVT (clib_bihash) * h;
  64
  65   h = &tm->hash;
  66
  67   BV (clib_bihash_init) (h, "test", user_buckets, user_memory_size);
  68
  69   before = clib_time_now (&tm->clib_time);
  70
  71   for (j = 0; j < 10; j++)
  72     {
  73       for (i = 1; i <= j * 1000 + 1; i++)
  74         {
  75           kv.key = i;
  76           kv.value = 1;
  77
  78           BV (clib_bihash_add_del) (h, &kv, 1 /* is_add */ );
  79         }
  80
  81       vec_add1 (cum_times, clib_time_now (&tm->clib_time) - before);
  82     }
  83
  84   for (j = 0; j < vec_len (cum_times); j++)
  85     fformat (stdout, "Cum time for %d: %.4f (us)\n", (j + 1) * 1000,
  86              cum_times[j] * 1e6);
  87
  88   return 0;
  89 }
  90
  91 static clib_error_t *
  92 test_bihash (test_main_t * tm)
  93 {
  94   int i, j;
  95   uword *p;
  96   uword total_searches;
  97   f64 before, delta;
  98   BVT (clib_bihash) * h;
  99   BVT (clib_bihash_kv) kv;
 100   u32 acycle;
 101
 102   h = &tm->hash;
 103
 104   BV (clib_bihash_init) (h, "test", tm->nbuckets, 3ULL << 30);
 105
 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       for (i = 0; i < tm->nitems; i++)
 273         hash_unset (tm->key_hash, tm->keys[i]);
 274
 275       vec_reset_length (tm->keys);
 276     }
 277
 278   fformat (stdout, "End of run, should be empty...\n");
 279
 280   fformat (stdout, "%U", BV (format_bihash), h, 0 /* very verbose */ );
 281   return 0;
 282 }
 283
 284 clib_error_t *
 285 test_bihash_cache (test_main_t * tm)
 286 {
 287   u32 lru;
 288   BVT (clib_bihash_bucket) _b, *b = &_b;
 289
 290   BV (clib_bihash_reset_cache) (b);
 291
 292   fformat (stdout, "Initial LRU config: %U\n", BV (format_bihash_lru), b);
 293
 294   BV (clib_bihash_update_lru_not_inline) (b, 3);
 295
 296   fformat (stdout, "use slot 3, LRU config: %U\n", BV (format_bihash_lru), b);
 297
 298   BV (clib_bihash_update_lru) (b, 1);
 299
 300   fformat (stdout, "use slot 1 LRU config: %U\n", BV (format_bihash_lru), b);
 301
 302   lru = BV (clib_bihash_get_lru) (b);
 303
 304   fformat (stdout, "least-recently-used is %d\n", lru);
 305
 306   BV (clib_bihash_update_lru) (b, 4);
 307
 308   fformat (stdout, "use slot 4 LRU config: %U\n", BV (format_bihash_lru), b);
 309
 310   lru = BV (clib_bihash_get_lru) (b);
 311
 312   fformat (stdout, "least-recently-used is %d\n", lru);
 313
 314   return 0;
 315 }
 316
 317 clib_error_t *
 318 test_bihash_main (test_main_t * tm)
 319 {
 320   unformat_input_t *i = tm->input;
 321   clib_error_t *error;
 322   int which = 0;
 323
 324   tm->report_every_n = 1;
 325
 326   while (unformat_check_input (i) != UNFORMAT_END_OF_INPUT)
 327     {
 328       if (unformat (i, "seed %u", &tm->seed))
 329         ;
 330
 331       else if (unformat (i, "nbuckets %d", &tm->nbuckets))
 332         ;
 333       else if (unformat (i, "non-random-keys"))
 334         tm->non_random_keys = 1;
 335       else if (unformat (i, "nitems %d", &tm->nitems))
 336         ;
 337       else if (unformat (i, "ncycles %d", &tm->ncycles))
 338         ;
 339       else if (unformat (i, "careful %d", &tm->careful_delete_tests))
 340         ;
 341       else if (unformat (i, "verbose %d", &tm->verbose))
 342         ;
 343       else if (unformat (i, "search %d", &tm->search_iter))
 344         ;
 345       else if (unformat (i, "report-every %d", &tm->report_every_n))
 346         ;
 347       else if (unformat (i, "vec64"))
 348         which = 1;
 349       else if (unformat (i, "cache"))
 350         which = 2;
 351
 352       else if (unformat (i, "verbose"))
 353         tm->verbose = 1;
 354       else
 355         return clib_error_return (0, "unknown input '%U'",
 356                                   format_unformat_error, i);
 357     }
 358
 359   switch (which)
 360     {
 361     case 0:
 362       error = test_bihash (tm);
 363       break;
 364
 365     case 1:
 366       error = test_bihash_vec64 (tm);
 367       break;
 368
 369     case 2:
 370       error = test_bihash_cache (tm);
 371       break;
 372
 373     default:
 374       return clib_error_return (0, "no such test?");
 375     }
 376
 377   return error;
 378 }
 379
 380 #ifdef CLIB_UNIX
 381 int
 382 main (int argc, char *argv[])
 383 {
 384   unformat_input_t i;
 385   clib_error_t *error;
 386   test_main_t *tm = &test_main;
 387
 388   clib_mem_init (0, 3ULL << 30);
 389
 390   tm->input = &i;
 391   tm->seed = 0xdeaddabe;
 392
 393   tm->nbuckets = 2;
 394   tm->nitems = 5;
 395   tm->ncycles = 1;
 396   tm->verbose = 1;
 397   tm->search_iter = 1;
 398   tm->careful_delete_tests = 0;
 399   tm->key_hash = hash_create (0, sizeof (uword));
 400   clib_time_init (&tm->clib_time);
 401
 402   unformat_init_command_line (&i, argv);
 403   error = test_bihash_main (tm);
 404   unformat_free (&i);
 405
 406   if (error)
 407     {
 408       clib_error_report (error);
 409       return 1;
 410     }
 411   return 0;
 412 }
 413 #endif /* CLIB_UNIX */
 414
 415 /*
 416  * fd.io coding-style-patch-verification: ON
 417  *
 418  * Local Variables:
 419  * eval: (c-set-style "gnu")
 420  * End:
 421  */