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   hash_foreach_pair (p0, h, {
  90     p1 = hash_next (h, &hn);
  91     error = CLIB_ERROR_ASSERT (p0 == p1);
  92     if (error)
  93       break;
  94   });
  95
  96   if (!error)
  97     error = CLIB_ERROR_ASSERT (!hash_next (h, &hn));
  98
  99   return error;
 100 }
 101
 102 static u8 *
 103 test1_format (u8 * s, va_list * args)
 104 {
 105   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 106   void *v = va_arg (*args, void *);
 107   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 108   hash_t *h = hash_header (v);
 109
 110   return format (s, "0x%8U -> 0x%8U",
 111                  format_hex_bytes, &p->key, sizeof (p->key),
 112                  format_hex_bytes, &p->value[0], hash_value_bytes (h));
 113 }
 114
 115 static clib_error_t *
 116 test_word_key (hash_test_t * ht)
 117 {
 118   word *h = 0;
 119   word i, j;
 120
 121   word *keys = 0, *vals = 0;
 122   uword *is_inserted = 0;
 123
 124   clib_error_t *error = 0;
 125
 126   vec_resize (keys, ht->n_pairs);
 127   vec_resize (vals, vec_len (keys));
 128
 129   h = hash_create (ht->fixed_hash_size, sizeof (vals[0]));
 130
 131   hash_set_pair_format (h, test1_format, 0);
 132   if (ht->fixed_hash_size)
 133     hash_set_flags (h, HASH_FLAG_NO_AUTO_GROW | HASH_FLAG_NO_AUTO_SHRINK);
 134
 135   {
 136     uword *unique = 0;
 137     u32 k;
 138
 139     for (i = 0; i < vec_len (keys); i++)
 140       {
 141         do
 142           {
 143             k = random_u32 (&ht->seed) & 0xfffff;
 144           }
 145         while (clib_bitmap_get (unique, k));
 146         unique = clib_bitmap_ori (unique, k);
 147         keys[i] = k;
 148         vals[i] = i;
 149       }
 150
 151     clib_bitmap_free (unique);
 152   }
 153
 154   for (i = 0; i < ht->n_iterations; i++)
 155     {
 156       u32 vi = random_u32 (&ht->seed) % vec_len (keys);
 157
 158       if (clib_bitmap_get (is_inserted, vi))
 159         hash_unset (h, keys[vi]);
 160       else
 161         hash_set (h, keys[vi], vals[vi]);
 162
 163       is_inserted = clib_bitmap_xori (is_inserted, vi);
 164
 165       if (ht->n_iterations_per_print > 0
 166           && ((i + 1) % ht->n_iterations_per_print) == 0)
 167         if_verbose ("iteration %d\n  %U", i + 1, format_hash, h, ht->verbose);
 168
 169       if (ht->n_iterations_per_validate == 0
 170           || (i + 1) % ht->n_iterations_per_validate)
 171         continue;
 172
 173       {
 174         hash_pair_t *p;
 175         uword ki;
 176
 177           hash_foreach_pair (p, h, {
 178               ki = p->value[0];
 179               ASSERT (keys[ki] == p->key);
 180           });
 181       }
 182
 183       if ((error = hash_validate (h)))
 184         goto done;
 185
 186       for (j = 0; j < vec_len (keys); j++)
 187         {
 188           uword *v;
 189           v = hash_get (h, keys[j]);
 190           if ((error =
 191                CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
 192                                   (v != 0))))
 193             goto done;
 194           if (v)
 195             {
 196               if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
 197                 goto done;
 198             }
 199         }
 200     }
 201
 202   if ((error = hash_next_test (h)))
 203     goto done;
 204
 205   if_verbose ("%U", format_hash, h, ht->verbose);
 206
 207   for (i = 0; i < vec_len (keys); i++)
 208     {
 209       if (!clib_bitmap_get (is_inserted, i))
 210         continue;
 211
 212       hash_unset (h, keys[i]);
 213       is_inserted = clib_bitmap_xori (is_inserted, i);
 214
 215       if (ht->n_iterations_per_validate == 0
 216           || (i + 1) % ht->n_iterations_per_validate)
 217         continue;
 218
 219       if ((error = hash_validate (h)))
 220         goto done;
 221
 222       for (j = 0; j < vec_len (keys); j++)
 223         {
 224           uword *v;
 225           v = hash_get (h, keys[j]);
 226           if ((error =
 227                CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
 228                                   (v != 0))))
 229             goto done;
 230           if (v)
 231             {
 232               if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
 233                 goto done;
 234             }
 235         }
 236     }
 237
 238 done:
 239   hash_free (h);
 240   vec_free (keys);
 241   vec_free (vals);
 242   clib_bitmap_free (is_inserted);
 243
 244   if (verbose)
 245     fformat (stderr, "%U\n", format_clib_mem_usage, /* verbose */ 0);
 246
 247   return error;
 248 }
 249
 250 static u8 *
 251 test2_format (u8 * s, va_list * args)
 252 {
 253   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 254   void *v = va_arg (*args, void *);
 255   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 256   hash_t *h = hash_header (v);
 257
 258   return format (s, "0x%8U <- %v",
 259                  format_hex_bytes, &p->value[0], hash_value_bytes (h),
 260                  p->key);
 261 }
 262
 263 static clib_error_t *
 264 test_string_key (hash_test_t * ht)
 265 {
 266   word i, j;
 267
 268   u8 **keys = 0;
 269   word *vals = 0;
 270   uword *is_inserted = 0;
 271
 272   word *h = 0;
 273
 274   clib_error_t *error = 0;
 275
 276   vec_resize (keys, ht->n_pairs);
 277   vec_resize (vals, vec_len (keys));
 278
 279   h =
 280     hash_create_vec (ht->fixed_hash_size, sizeof (keys[0][0]),
 281                      sizeof (uword));
 282   hash_set_pair_format (h, test2_format, 0);
 283   if (ht->fixed_hash_size)
 284     hash_set_flags (h, HASH_FLAG_NO_AUTO_SHRINK | HASH_FLAG_NO_AUTO_GROW);
 285
 286   for (i = 0; i < vec_len (keys); i++)
 287     {
 288       keys[i] = random_string (&ht->seed, 5 + (random_u32 (&ht->seed) & 0xf));
 289       keys[i] = format (keys[i], "%x", i);
 290       vals[i] = random_u32 (&ht->seed);
 291     }
 292
 293   for (i = 0; i < ht->n_iterations; i++)
 294     {
 295       u32 vi = random_u32 (&ht->seed) % vec_len (keys);
 296
 297       if (clib_bitmap_get (is_inserted, vi))
 298         hash_unset_mem (h, keys[vi]);
 299       else
 300         hash_set_mem (h, keys[vi], vals[vi]);
 301
 302       is_inserted = clib_bitmap_xori (is_inserted, vi);
 303
 304       if (ht->n_iterations_per_print > 0
 305           && ((i + 1) % ht->n_iterations_per_print) == 0)
 306         if_verbose ("iteration %d\n  %U", i + 1, format_hash, h, ht->verbose);
 307
 308       if (ht->n_iterations_per_validate == 0
 309           || (i + 1) % ht->n_iterations_per_validate)
 310         continue;
 311
 312       if ((error = hash_validate (h)))
 313         goto done;
 314
 315       for (j = 0; j < vec_len (keys); j++)
 316         {
 317           uword *v;
 318           v = hash_get_mem (h, keys[j]);
 319           if ((error =
 320                CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
 321                                   (v != 0))))
 322             goto done;
 323           if (v)
 324             {
 325               if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
 326                 goto done;
 327             }
 328         }
 329     }
 330
 331   if ((error = hash_next_test (h)))
 332     goto done;
 333
 334   if_verbose ("%U", format_hash, h, ht->verbose);
 335
 336   for (i = 0; i < vec_len (keys); i++)
 337     {
 338       if (!clib_bitmap_get (is_inserted, i))
 339         continue;
 340
 341       hash_unset_mem (h, keys[i]);
 342       is_inserted = clib_bitmap_xori (is_inserted, i);
 343
 344       if (ht->n_iterations_per_validate == 0
 345           || (i + 1) % ht->n_iterations_per_validate)
 346         continue;
 347
 348       if ((error = hash_validate (h)))
 349         goto done;
 350
 351       for (j = 0; j < vec_len (keys); j++)
 352         {
 353           uword *v;
 354           v = hash_get_mem (h, keys[j]);
 355           if ((error =
 356                CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
 357                                   (v != 0))))
 358             goto done;
 359           if (v)
 360             {
 361               if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
 362                 goto done;
 363             }
 364         }
 365     }
 366
 367 done:
 368   hash_free (h);
 369   vec_free (vals);
 370   clib_bitmap_free (is_inserted);
 371
 372   for (i = 0; i < vec_len (keys); i++)
 373     vec_free (keys[i]);
 374   vec_free (keys);
 375
 376   if (verbose)
 377     fformat (stderr, "%U\n", format_clib_mem_usage, /* verbose */ 0);
 378
 379   return error;
 380 }
 381
 382 int
 383 test_hash_main (unformat_input_t * input)
 384 {
 385   hash_test_t _ht = { 0 }, *ht = &_ht;
 386   clib_error_t *error;
 387
 388   ht->n_iterations = 100;
 389   ht->n_pairs = 10;
 390   ht->fixed_hash_size = 0;      /* zero means non-fixed size */
 391
 392   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 393     {
 394       if (0 == unformat (input, "iter %d", &ht->n_iterations)
 395           && 0 == unformat (input, "print %d", &ht->n_iterations_per_print)
 396           && 0 == unformat (input, "elts %d", &ht->n_pairs)
 397           && 0 == unformat (input, "size %d", &ht->fixed_hash_size)
 398           && 0 == unformat (input, "seed %d", &ht->seed)
 399           && 0 == unformat (input, "verbose %=", &ht->verbose, 1)
 400           && 0 == unformat (input, "valid %d",
 401                             &ht->n_iterations_per_validate))
 402         {
 403           clib_warning ("unknown input `%U'", format_unformat_error, input);
 404           return 1;
 405         }
 406     }
 407
 408   if (!ht->seed)
 409     ht->seed = random_default_seed ();
 410
 411   if_verbose ("testing %d iterations, seed %d", ht->n_iterations, ht->seed);
 412
 413   error = test_word_key (ht);
 414   if (error)
 415     clib_error_report (error);
 416
 417   error = test_string_key (ht);
 418   if (error)
 419     clib_error_report (error);
 420
 421   return 0;
 422 }
 423
 424 #ifdef CLIB_UNIX
 425 int
 426 main (int argc, char *argv[])
 427 {
 428   unformat_input_t i;
 429   int ret;
 430
 431   clib_mem_init (0, 3ULL << 30);
 432
 433   verbose = (argc > 1);
 434   unformat_init_command_line (&i, argv);
 435   ret = test_hash_main (&i);
 436   unformat_free (&i);
 437
 438   return ret;
 439 }
 440 #endif /* CLIB_UNIX */
 441
 442 /*
 443  * fd.io coding-style-patch-verification: ON
 444  *
 445  * Local Variables:
 446  * eval: (c-set-style "gnu")
 447  * End:
 448  */