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