src/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       if ((error = hash_validate (h)))
 188         goto done;
 189
 190       for (j = 0; j < vec_len (keys); j++)
 191         {
 192           uword *v;
 193           v = hash_get (h, keys[j]);
 194           if ((error =
 195                CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
 196                                   (v != 0))))
 197             goto done;
 198           if (v)
 199             {
 200               if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
 201                 goto done;
 202             }
 203         }
 204     }
 205
 206   if ((error = hash_next_test (h)))
 207     goto done;
 208
 209   if_verbose ("%U", format_hash, h, ht->verbose);
 210
 211   for (i = 0; i < vec_len (keys); i++)
 212     {
 213       if (!clib_bitmap_get (is_inserted, i))
 214         continue;
 215
 216       hash_unset (h, keys[i]);
 217       is_inserted = clib_bitmap_xori (is_inserted, i);
 218
 219       if (ht->n_iterations_per_validate == 0
 220           || (i + 1) % ht->n_iterations_per_validate)
 221         continue;
 222
 223       if ((error = hash_validate (h)))
 224         goto done;
 225
 226       for (j = 0; j < vec_len (keys); j++)
 227         {
 228           uword *v;
 229           v = hash_get (h, keys[j]);
 230           if ((error =
 231                CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
 232                                   (v != 0))))
 233             goto done;
 234           if (v)
 235             {
 236               if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
 237                 goto done;
 238             }
 239         }
 240     }
 241
 242 done:
 243   hash_free (h);
 244   vec_free (keys);
 245   vec_free (vals);
 246   clib_bitmap_free (is_inserted);
 247
 248   if (verbose)
 249     fformat (stderr, "%U\n", format_clib_mem_usage, /* verbose */ 0);
 250
 251   return error;
 252 }
 253
 254 static u8 *
 255 test2_format (u8 * s, va_list * args)
 256 {
 257   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 258   void *v = va_arg (*args, void *);
 259   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 260   hash_t *h = hash_header (v);
 261
 262   return format (s, "0x%8U <- %v",
 263                  format_hex_bytes, &p->value[0], hash_value_bytes (h),
 264                  p->key);
 265 }
 266
 267 static clib_error_t *
 268 test_string_key (hash_test_t * ht)
 269 {
 270   word i, j;
 271
 272   u8 **keys = 0;
 273   word *vals = 0;
 274   uword *is_inserted = 0;
 275
 276   word *h = 0;
 277
 278   clib_error_t *error = 0;
 279
 280   vec_resize (keys, ht->n_pairs);
 281   vec_resize (vals, vec_len (keys));
 282
 283   h =
 284     hash_create_vec (ht->fixed_hash_size, sizeof (keys[0][0]),
 285                      sizeof (uword));
 286   hash_set_pair_format (h, test2_format, 0);
 287   if (ht->fixed_hash_size)
 288     hash_set_flags (h, HASH_FLAG_NO_AUTO_SHRINK | HASH_FLAG_NO_AUTO_GROW);
 289
 290   for (i = 0; i < vec_len (keys); i++)
 291     {
 292       keys[i] = random_string (&ht->seed, 5 + (random_u32 (&ht->seed) & 0xf));
 293       keys[i] = format (keys[i], "%x", i);
 294       vals[i] = random_u32 (&ht->seed);
 295     }
 296
 297   for (i = 0; i < ht->n_iterations; i++)
 298     {
 299       u32 vi = random_u32 (&ht->seed) % vec_len (keys);
 300
 301       if (clib_bitmap_get (is_inserted, vi))
 302         hash_unset_mem (h, keys[vi]);
 303       else
 304         hash_set_mem (h, keys[vi], vals[vi]);
 305
 306       is_inserted = clib_bitmap_xori (is_inserted, vi);
 307
 308       if (ht->n_iterations_per_print > 0
 309           && ((i + 1) % ht->n_iterations_per_print) == 0)
 310         if_verbose ("iteration %d\n  %U", i + 1, format_hash, h, ht->verbose);
 311
 312       if (ht->n_iterations_per_validate == 0
 313           || (i + 1) % ht->n_iterations_per_validate)
 314         continue;
 315
 316       if ((error = hash_validate (h)))
 317         goto done;
 318
 319       for (j = 0; j < vec_len (keys); j++)
 320         {
 321           uword *v;
 322           v = hash_get_mem (h, keys[j]);
 323           if ((error =
 324                CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
 325                                   (v != 0))))
 326             goto done;
 327           if (v)
 328             {
 329               if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
 330                 goto done;
 331             }
 332         }
 333     }
 334
 335   if ((error = hash_next_test (h)))
 336     goto done;
 337
 338   if_verbose ("%U", format_hash, h, ht->verbose);
 339
 340   for (i = 0; i < vec_len (keys); i++)
 341     {
 342       if (!clib_bitmap_get (is_inserted, i))
 343         continue;
 344
 345       hash_unset_mem (h, keys[i]);
 346       is_inserted = clib_bitmap_xori (is_inserted, i);
 347
 348       if (ht->n_iterations_per_validate == 0
 349           || (i + 1) % ht->n_iterations_per_validate)
 350         continue;
 351
 352       if ((error = hash_validate (h)))
 353         goto done;
 354
 355       for (j = 0; j < vec_len (keys); j++)
 356         {
 357           uword *v;
 358           v = hash_get_mem (h, keys[j]);
 359           if ((error =
 360                CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
 361                                   (v != 0))))
 362             goto done;
 363           if (v)
 364             {
 365               if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
 366                 goto done;
 367             }
 368         }
 369     }
 370
 371 done:
 372   hash_free (h);
 373   vec_free (vals);
 374   clib_bitmap_free (is_inserted);
 375
 376   for (i = 0; i < vec_len (keys); i++)
 377     vec_free (keys[i]);
 378   vec_free (keys);
 379
 380   if (verbose)
 381     fformat (stderr, "%U\n", format_clib_mem_usage, /* verbose */ 0);
 382
 383   return error;
 384 }
 385
 386 int
 387 test_hash_main (unformat_input_t * input)
 388 {
 389   hash_test_t _ht = { 0 }, *ht = &_ht;
 390   clib_error_t *error;
 391
 392   ht->n_iterations = 100;
 393   ht->n_pairs = 10;
 394   ht->fixed_hash_size = 0;      /* zero means non-fixed size */
 395
 396   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 397     {
 398       if (0 == unformat (input, "iter %d", &ht->n_iterations)
 399           && 0 == unformat (input, "print %d", &ht->n_iterations_per_print)
 400           && 0 == unformat (input, "elts %d", &ht->n_pairs)
 401           && 0 == unformat (input, "size %d", &ht->fixed_hash_size)
 402           && 0 == unformat (input, "seed %d", &ht->seed)
 403           && 0 == unformat (input, "verbose %=", &ht->verbose, 1)
 404           && 0 == unformat (input, "valid %d",
 405                             &ht->n_iterations_per_validate))
 406         {
 407           clib_warning ("unknown input `%U'", format_unformat_error, input);
 408           return 1;
 409         }
 410     }
 411
 412   if (!ht->seed)
 413     ht->seed = random_default_seed ();
 414
 415   if_verbose ("testing %d iterations, seed %d", ht->n_iterations, ht->seed);
 416
 417   error = test_word_key (ht);
 418   if (error)
 419     clib_error_report (error);
 420
 421   error = test_string_key (ht);
 422   if (error)
 423     clib_error_report (error);
 424
 425   return 0;
 426 }
 427
 428 #ifdef CLIB_UNIX
 429 int
 430 main (int argc, char *argv[])
 431 {
 432   unformat_input_t i;
 433   int ret;
 434
 435   clib_mem_init (0, 3ULL << 30);
 436
 437   verbose = (argc > 1);
 438   unformat_init_command_line (&i, argv);
 439   ret = test_hash_main (&i);
 440   unformat_free (&i);
 441
 442   return ret;
 443 }
 444 #endif /* CLIB_UNIX */
 445
 446 /*
 447  * fd.io coding-style-patch-verification: ON
 448  *
 449  * Local Variables:
 450  * eval: (c-set-style "gnu")
 451  * End:
 452  */