vppinfra/vppinfra/test_hash.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 /*
  16   Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
  17
  18   Permission is hereby granted, free of charge, to any person obtaining
  19   a copy of this software and associated documentation files (the
  20   "Software"), to deal in the Software without restriction, including
  21   without limitation the rights to use, copy, modify, merge, publish,
  22   distribute, sublicense, and/or sell copies of the Software, and to
  23   permit persons to whom the Software is furnished to do so, subject to
  24   the following conditions:
  25
  26   The above copyright notice and this permission notice shall be
  27   included in all copies or substantial portions of the Software.
  28
  29   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  30   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  31   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  32   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  33   LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  34   OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  35   WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  36 */
  37
  38 #ifdef CLIB_LINUX_KERNEL
  39 #include <linux/unistd.h>
  40 #endif
  41
  42 #ifdef CLIB_UNIX
  43 #include <unistd.h>
  44 #include <stdlib.h>
  45 #include <stdio.h>
  46 #include <vppinfra/time.h>
  47 #endif
  48
  49 #include <vppinfra/random.h>
  50 #include <vppinfra/mem.h>
  51 #include <vppinfra/hash.h>
  52 #include <vppinfra/error.h>
  53 #include <vppinfra/format.h>
  54 #include <vppinfra/bitmap.h>
  55
  56 static int verbose;
  57 #define if_verbose(format,args...) \
  58   if (verbose) { clib_warning(format, ## args); }
  59
  60 typedef struct
  61 {
  62   int n_iterations;
  63
  64   int n_iterations_per_print;
  65
  66   /* Number of pairs to insert into hash. */
  67   int n_pairs;
  68
  69   /* True to validate correctness of hash functions. */
  70   int n_iterations_per_validate;
  71
  72   /* Non-zero if hash table size is to be fixed. */
  73   int fixed_hash_size;
  74
  75   /* Verbosity level for hash formats. */
  76   int verbose;
  77
  78   /* Random number seed. */
  79   u32 seed;
  80 } hash_test_t;
  81
  82 static clib_error_t *
  83 hash_next_test (word * h)
  84 {
  85   hash_next_t hn = { 0 };
  86   hash_pair_t *p0, *p1;
  87   clib_error_t *error = 0;
  88
  89   /* *INDENT-OFF* */
  90   hash_foreach_pair (p0, h, {
  91     p1 = hash_next (h, &hn);
  92     error = CLIB_ERROR_ASSERT (p0 == p1);
  93     if (error)
  94       break;
  95   });
  96   /* *INDENT-ON* */
  97
  98   if (!error)
  99     error = CLIB_ERROR_ASSERT (!hash_next (h, &hn));
 100
 101   return error;
 102 }
 103
 104 static u8 *
 105 test1_format (u8 * s, va_list * args)
 106 {
 107   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 108   void *v = va_arg (*args, void *);
 109   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 110   hash_t *h = hash_header (v);
 111
 112   return format (s, "0x%8U -> 0x%8U",
 113                  format_hex_bytes, &p->key, sizeof (p->key),
 114                  format_hex_bytes, &p->value[0], hash_value_bytes (h));
 115 }
 116
 117 static clib_error_t *
 118 test_word_key (hash_test_t * ht)
 119 {
 120   word *h = 0;
 121   word i, j;
 122
 123   word *keys = 0, *vals = 0;
 124   uword *is_inserted = 0;
 125
 126   clib_error_t *error = 0;
 127
 128   vec_resize (keys, ht->n_pairs);
 129   vec_resize (vals, vec_len (keys));
 130
 131   h = hash_create (ht->fixed_hash_size, sizeof (vals[0]));
 132
 133   hash_set_pair_format (h, test1_format, 0);
 134   if (ht->fixed_hash_size)
 135     hash_set_flags (h, HASH_FLAG_NO_AUTO_GROW | HASH_FLAG_NO_AUTO_SHRINK);
 136
 137   {
 138     uword *unique = 0;
 139     u32 k;
 140
 141     for (i = 0; i < vec_len (keys); i++)
 142       {
 143         do
 144           {
 145             k = random_u32 (&ht->seed) & 0xfffff;
 146           }
 147         while (clib_bitmap_get (unique, k));
 148         unique = clib_bitmap_ori (unique, k);
 149         keys[i] = k;
 150         vals[i] = i;
 151       }
 152
 153     clib_bitmap_free (unique);
 154   }
 155
 156   for (i = 0; i < ht->n_iterations; i++)
 157     {
 158       u32 vi = random_u32 (&ht->seed) % vec_len (keys);
 159
 160       if (clib_bitmap_get (is_inserted, vi))
 161         hash_unset (h, keys[vi]);
 162       else
 163         hash_set (h, keys[vi], vals[vi]);
 164
 165       is_inserted = clib_bitmap_xori (is_inserted, vi);
 166
 167       if (ht->n_iterations_per_print > 0
 168           && ((i + 1) % ht->n_iterations_per_print) == 0)
 169         if_verbose ("iteration %d\n  %U", i + 1, format_hash, h, ht->verbose);
 170
 171       if (ht->n_iterations_per_validate == 0
 172           || (i + 1) % ht->n_iterations_per_validate)
 173         continue;
 174
 175       {
 176         hash_pair_t *p;
 177         uword ki;
 178
 179           /* *INDENT-OFF* */
 180           hash_foreach_pair (p, h, {
 181               ki = p->value[0];
 182               ASSERT (keys[ki] == p->key);
 183           });
 184           /* *INDENT-ON* */
 185       }
 186
 187       clib_mem_validate ();
 188
 189       if ((error = hash_validate (h)))
 190         goto done;
 191
 192       for (j = 0; j < vec_len (keys); j++)
 193         {
 194           uword *v;
 195           v = hash_get (h, keys[j]);
 196           if ((error =
 197                CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
 198                                   (v != 0))))
 199             goto done;
 200           if (v)
 201             {
 202               if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
 203                 goto done;
 204             }
 205         }
 206     }
 207
 208   if ((error = hash_next_test (h)))
 209     goto done;
 210
 211   if_verbose ("%U", format_hash, h, ht->verbose);
 212
 213   for (i = 0; i < vec_len (keys); i++)
 214     {
 215       if (!clib_bitmap_get (is_inserted, i))
 216         continue;
 217
 218       hash_unset (h, keys[i]);
 219       is_inserted = clib_bitmap_xori (is_inserted, i);
 220
 221       if (ht->n_iterations_per_validate == 0
 222           || (i + 1) % ht->n_iterations_per_validate)
 223         continue;
 224
 225       clib_mem_validate ();
 226
 227       if ((error = hash_validate (h)))
 228         goto done;
 229
 230       for (j = 0; j < vec_len (keys); j++)
 231         {
 232           uword *v;
 233           v = hash_get (h, keys[j]);
 234           if ((error =
 235                CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
 236                                   (v != 0))))
 237             goto done;
 238           if (v)
 239             {
 240               if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
 241                 goto done;
 242             }
 243         }
 244     }
 245
 246 done:
 247   hash_free (h);
 248   vec_free (keys);
 249   vec_free (vals);
 250   clib_bitmap_free (is_inserted);
 251
 252   if (verbose)
 253     fformat (stderr, "%U\n", format_clib_mem_usage, /* verbose */ 0);
 254
 255   return error;
 256 }
 257
 258 static u8 *
 259 test2_format (u8 * s, va_list * args)
 260 {
 261   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 262   void *v = va_arg (*args, void *);
 263   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 264   hash_t *h = hash_header (v);
 265
 266   return format (s, "0x%8U <- %v",
 267                  format_hex_bytes, &p->value[0], hash_value_bytes (h),
 268                  p->key);
 269 }
 270
 271 static clib_error_t *
 272 test_string_key (hash_test_t * ht)
 273 {
 274   word i, j;
 275
 276   u8 **keys = 0;
 277   word *vals = 0;
 278   uword *is_inserted = 0;
 279
 280   word *h = 0;
 281
 282   clib_error_t *error = 0;
 283
 284   vec_resize (keys, ht->n_pairs);
 285   vec_resize (vals, vec_len (keys));
 286
 287   h =
 288     hash_create_vec (ht->fixed_hash_size, sizeof (keys[0][0]),
 289                      sizeof (uword));
 290   hash_set_pair_format (h, test2_format, 0);
 291   if (ht->fixed_hash_size)
 292     hash_set_flags (h, HASH_FLAG_NO_AUTO_SHRINK | HASH_FLAG_NO_AUTO_GROW);
 293
 294   for (i = 0; i < vec_len (keys); i++)
 295     {
 296       keys[i] = random_string (&ht->seed, 5 + (random_u32 (&ht->seed) & 0xf));
 297       keys[i] = format (keys[i], "%x", i);
 298       vals[i] = random_u32 (&ht->seed);
 299     }
 300
 301   for (i = 0; i < ht->n_iterations; i++)
 302     {
 303       u32 vi = random_u32 (&ht->seed) % vec_len (keys);
 304
 305       if (clib_bitmap_get (is_inserted, vi))
 306         hash_unset_mem (h, keys[vi]);
 307       else
 308         hash_set_mem (h, keys[vi], vals[vi]);
 309
 310       is_inserted = clib_bitmap_xori (is_inserted, vi);
 311
 312       if (ht->n_iterations_per_print > 0
 313           && ((i + 1) % ht->n_iterations_per_print) == 0)
 314         if_verbose ("iteration %d\n  %U", i + 1, format_hash, h, ht->verbose);
 315
 316       if (ht->n_iterations_per_validate == 0
 317           || (i + 1) % ht->n_iterations_per_validate)
 318         continue;
 319
 320       clib_mem_validate ();
 321
 322       if ((error = hash_validate (h)))
 323         goto done;
 324
 325       for (j = 0; j < vec_len (keys); j++)
 326         {
 327           uword *v;
 328           v = hash_get_mem (h, keys[j]);
 329           if ((error =
 330                CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
 331                                   (v != 0))))
 332             goto done;
 333           if (v)
 334             {
 335               if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
 336                 goto done;
 337             }
 338         }
 339     }
 340
 341   if ((error = hash_next_test (h)))
 342     goto done;
 343
 344   if_verbose ("%U", format_hash, h, ht->verbose);
 345
 346   for (i = 0; i < vec_len (keys); i++)
 347     {
 348       if (!clib_bitmap_get (is_inserted, i))
 349         continue;
 350
 351       hash_unset_mem (h, keys[i]);
 352       is_inserted = clib_bitmap_xori (is_inserted, i);
 353
 354       if (ht->n_iterations_per_validate == 0
 355           || (i + 1) % ht->n_iterations_per_validate)
 356         continue;
 357
 358       clib_mem_validate ();
 359
 360       if ((error = hash_validate (h)))
 361         goto done;
 362
 363       for (j = 0; j < vec_len (keys); j++)
 364         {
 365           uword *v;
 366           v = hash_get_mem (h, keys[j]);
 367           if ((error =
 368                CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
 369                                   (v != 0))))
 370             goto done;
 371           if (v)
 372             {
 373               if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
 374                 goto done;
 375             }
 376         }
 377     }
 378
 379 done:
 380   hash_free (h);
 381   vec_free (vals);
 382   clib_bitmap_free (is_inserted);
 383
 384   for (i = 0; i < vec_len (keys); i++)
 385     vec_free (keys[i]);
 386   vec_free (keys);
 387
 388   if (verbose)
 389     fformat (stderr, "%U\n", format_clib_mem_usage, /* verbose */ 0);
 390
 391   return error;
 392 }
 393
 394 int
 395 test_hash_main (unformat_input_t * input)
 396 {
 397   hash_test_t _ht = { 0 }, *ht = &_ht;
 398   clib_error_t *error;
 399
 400   ht->n_iterations = 100;
 401   ht->n_pairs = 10;
 402   ht->fixed_hash_size = 0;      /* zero means non-fixed size */
 403
 404   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 405     {
 406       if (0 == unformat (input, "iter %d", &ht->n_iterations)
 407           && 0 == unformat (input, "print %d", &ht->n_iterations_per_print)
 408           && 0 == unformat (input, "elts %d", &ht->n_pairs)
 409           && 0 == unformat (input, "size %d", &ht->fixed_hash_size)
 410           && 0 == unformat (input, "seed %d", &ht->seed)
 411           && 0 == unformat (input, "verbose %=", &ht->verbose, 1)
 412           && 0 == unformat (input, "valid %d",
 413                             &ht->n_iterations_per_validate))
 414         {
 415           clib_warning ("unknown input `%U'", format_unformat_error, input);
 416           return 1;
 417         }
 418     }
 419
 420   if (!ht->seed)
 421     ht->seed = random_default_seed ();
 422
 423   if_verbose ("testing %d iterations, seed %d", ht->n_iterations, ht->seed);
 424
 425   error = test_word_key (ht);
 426   if (error)
 427     clib_error_report (error);
 428
 429   error = test_string_key (ht);
 430   if (error)
 431     clib_error_report (error);
 432
 433   return 0;
 434 }
 435
 436 #ifdef CLIB_UNIX
 437 int
 438 main (int argc, char *argv[])
 439 {
 440   unformat_input_t i;
 441   int ret;
 442
 443   verbose = (argc > 1);
 444   unformat_init_command_line (&i, argv);
 445   ret = test_hash_main (&i);
 446   unformat_free (&i);
 447
 448   return ret;
 449 }
 450 #endif /* CLIB_UNIX */
 451
 452 /*
 453  * fd.io coding-style-patch-verification: ON
 454  *
 455  * Local Variables:
 456  * eval: (c-set-style "gnu")
 457  * End:
 458  */