src/vppinfra/test_mhash.c

   1 /* SPDX-License-Identifier: Apache-2.0
   2  * Copyright(c) 2023 Yandex LLC.
   3  */
   4
   5 #ifdef CLIB_LINUX_KERNEL
   6 #include <linux/unistd.h>
   7 #endif
   8
   9 #ifdef CLIB_UNIX
  10 #include <unistd.h>
  11 #include <stdlib.h>
  12 #include <stdio.h>
  13 #include <vppinfra/time.h>
  14 #endif
  15
  16 #include <vppinfra/random.h>
  17 #include <vppinfra/mem.h>
  18 #include <vppinfra/hash.h>
  19 #include <vppinfra/mhash.h>
  20 #include <vppinfra/error.h>
  21 #include <vppinfra/format.h>
  22 #include <vppinfra/bitmap.h>
  23
  24 static int verbose;
  25 #define if_verbose(format, args...)                                           \
  26   if (verbose)                                                                \
  27     {                                                                         \
  28       clib_warning (format, ##args);                                          \
  29     }
  30
  31 typedef struct
  32 {
  33   int n_iterations;
  34
  35   int n_iterations_per_print;
  36
  37   /* Number of pairs to insert into mhash. */
  38   int n_pairs;
  39
  40   /* True to validate correctness of mhash functions. */
  41   int n_iterations_per_validate;
  42
  43   /* Verbosity level for mhash formats. */
  44   int verbose;
  45
  46   /* Random number seed. */
  47   u32 seed;
  48 } mhash_test_t;
  49
  50 static clib_error_t *
  51 mhash_next_test (mhash_t *h)
  52 {
  53   hash_next_t hn = { 0 };
  54   hash_pair_t *p0, *p1;
  55   clib_error_t *error = 0;
  56
  57   hash_foreach_pair (p0, h->hash, {
  58     p1 = hash_next (h->hash, &hn);
  59     error = CLIB_ERROR_ASSERT (p0 == p1);
  60     if (error)
  61       break;
  62   });
  63
  64   if (!error)
  65     error = CLIB_ERROR_ASSERT (!hash_next (h->hash, &hn));
  66
  67   return error;
  68 }
  69
  70 static clib_error_t *
  71 test_word_key (mhash_test_t *ht)
  72 {
  73   mhash_t _h = { 0 }, *h = &_h;
  74   word i, j;
  75
  76   word *keys = 0, *vals = 0;
  77   uword *is_inserted = 0;
  78
  79   clib_error_t *error = 0;
  80
  81   vec_resize (keys, ht->n_pairs);
  82   vec_resize (vals, vec_len (keys));
  83
  84   mhash_init (h, sizeof (vals[0]), sizeof (keys[0]));
  85   /* borrow 0 elt to make index keys non-zero */
  86   vec_validate (h->key_vector_or_heap, 0);
  87
  88   {
  89     uword *unique = 0;
  90     u32 k;
  91
  92     for (i = 0; i < vec_len (keys); i++)
  93       {
  94         do
  95           {
  96             k = random_u32 (&ht->seed) & 0xfffff;
  97           }
  98         while (clib_bitmap_get (unique, k));
  99         unique = clib_bitmap_ori (unique, k);
 100         keys[i] = k;
 101         vals[i] = i;
 102       }
 103
 104     clib_bitmap_free (unique);
 105   }
 106
 107   for (i = 0; i < ht->n_iterations; i++)
 108     {
 109       u32 vi = random_u32 (&ht->seed) % vec_len (keys);
 110
 111       if (clib_bitmap_get (is_inserted, vi))
 112         {
 113           mhash_unset (h, &keys[vi], 0);
 114           mhash_unset (h, &keys[vi], 0);
 115         }
 116       else
 117         {
 118           mhash_set (h, &keys[vi], vals[vi], 0);
 119           mhash_set (h, &keys[vi], vals[vi], 0);
 120         }
 121
 122       is_inserted = clib_bitmap_xori (is_inserted, vi);
 123
 124       if (ht->n_iterations_per_print > 0 &&
 125           ((i + 1) % ht->n_iterations_per_print) == 0)
 126         if_verbose ("iteration %d\n  %U", i + 1, format_mhash, h, ht->verbose);
 127
 128       if (ht->n_iterations_per_validate == 0 ||
 129           (i + 1) % ht->n_iterations_per_validate)
 130         continue;
 131
 132       {
 133         uword ki, *k, *v;
 134
 135         mhash_foreach (k, v, h, {
 136           ki = v[0];
 137           ASSERT (keys[ki] == k[0]);
 138         });
 139       }
 140
 141       if ((error = hash_validate (h->hash)))
 142         goto done;
 143
 144       for (j = 0; j < vec_len (keys); j++)
 145         {
 146           uword *v;
 147           v = mhash_get (h, &keys[j]);
 148           if ((error = CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
 149                                           (v != 0))))
 150             goto done;
 151           if (v)
 152             {
 153               if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
 154                 goto done;
 155             }
 156         }
 157     }
 158
 159   if ((error = mhash_next_test (h)))
 160     goto done;
 161
 162   if_verbose ("%U", format_mhash, h, ht->verbose);
 163
 164   for (i = 0; i < vec_len (keys); i++)
 165     {
 166       if (!clib_bitmap_get (is_inserted, i))
 167         continue;
 168
 169       mhash_unset (h, &keys[i], 0);
 170       mhash_unset (h, &keys[i], 0);
 171       is_inserted = clib_bitmap_xori (is_inserted, i);
 172
 173       if (ht->n_iterations_per_validate == 0 ||
 174           (i + 1) % ht->n_iterations_per_validate)
 175         continue;
 176
 177       if ((error = hash_validate (h->hash)))
 178         goto done;
 179
 180       for (j = 0; j < vec_len (keys); j++)
 181         {
 182           uword *v;
 183           v = mhash_get (h, &keys[j]);
 184           if ((error = CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
 185                                           (v != 0))))
 186             goto done;
 187           if (v)
 188             {
 189               if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
 190                 goto done;
 191             }
 192         }
 193     }
 194
 195 done:
 196   mhash_free (h);
 197   vec_free (keys);
 198   vec_free (vals);
 199   clib_bitmap_free (is_inserted);
 200
 201   if (verbose)
 202     fformat (stderr, "%U\n", format_clib_mem_usage, /* verbose */ 0);
 203
 204   return error;
 205 }
 206
 207 static u8 *
 208 test2_format (u8 *s, va_list *args)
 209 {
 210   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 211   void *v = va_arg (*args, void *);
 212   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 213   hash_t *h = hash_header (v);
 214   mhash_t *mh = uword_to_pointer (h->user, mhash_t *);
 215
 216   return format (s, "0x%8U <- %U", format_hex_bytes, &p->value[0],
 217                  hash_value_bytes (h), format_mhash_key, mh, (u32) p->key);
 218 }
 219
 220 static clib_error_t *
 221 test_string_key (mhash_test_t *ht, uword is_c_string)
 222 {
 223   mhash_t _h = { 0 }, *h = &_h;
 224   word i, j;
 225
 226   u8 **keys = 0;
 227   word *vals = 0;
 228   uword *is_inserted = 0;
 229
 230   clib_error_t *error = 0;
 231
 232   vec_resize (keys, ht->n_pairs);
 233   vec_resize (vals, vec_len (keys));
 234
 235   if (is_c_string)
 236     mhash_init_c_string (h, sizeof (vals[0]));
 237   else
 238     mhash_init_vec_string (h, sizeof (vals[0]));
 239   hash_set_pair_format (h->hash, test2_format, 0);
 240
 241   for (i = 0; i < vec_len (keys); i++)
 242     {
 243       keys[i] = random_string (&ht->seed, 5 + (random_u32 (&ht->seed) & 0xf));
 244       keys[i] = format (keys[i], "%x", i);
 245       if (is_c_string)
 246         vec_terminate_c_string (keys[i]);
 247       vals[i] = random_u32 (&ht->seed);
 248     }
 249
 250   for (i = 0; i < ht->n_iterations; i++)
 251     {
 252       u32 vi = random_u32 (&ht->seed) % vec_len (keys);
 253
 254       if (clib_bitmap_get (is_inserted, vi))
 255         {
 256           mhash_unset (h, keys[vi], 0);
 257           mhash_unset (h, keys[vi], 0);
 258         }
 259       else
 260         {
 261           mhash_set (h, keys[vi], vals[vi], 0);
 262           mhash_set (h, keys[vi], vals[vi], 0);
 263         }
 264
 265       is_inserted = clib_bitmap_xori (is_inserted, vi);
 266
 267       if (ht->n_iterations_per_print > 0 &&
 268           ((i + 1) % ht->n_iterations_per_print) == 0)
 269         if_verbose ("iteration %d\n  %U", i + 1, format_mhash, h, ht->verbose);
 270
 271       if (ht->n_iterations_per_validate == 0 ||
 272           (i + 1) % ht->n_iterations_per_validate)
 273         continue;
 274
 275       if ((error = hash_validate (h->hash)))
 276         goto done;
 277
 278       for (j = 0; j < vec_len (keys); j++)
 279         {
 280           uword *v;
 281           v = mhash_get (h, keys[j]);
 282           if ((error = CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
 283                                           (v != 0))))
 284             goto done;
 285           if (v)
 286             {
 287               if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
 288                 goto done;
 289             }
 290         }
 291     }
 292
 293   if ((error = mhash_next_test (h)))
 294     goto done;
 295
 296   if_verbose ("%U", format_mhash, h, ht->verbose);
 297
 298   for (i = 0; i < vec_len (keys); i++)
 299     {
 300       if (!clib_bitmap_get (is_inserted, i))
 301         continue;
 302
 303       mhash_unset (h, keys[i], 0);
 304       mhash_unset (h, keys[i], 0);
 305       is_inserted = clib_bitmap_xori (is_inserted, i);
 306
 307       if (ht->n_iterations_per_validate == 0 ||
 308           (i + 1) % ht->n_iterations_per_validate)
 309         continue;
 310
 311       if ((error = hash_validate (h->hash)))
 312         goto done;
 313
 314       for (j = 0; j < vec_len (keys); j++)
 315         {
 316           uword *v;
 317           v = mhash_get (h, keys[j]);
 318           if ((error = CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) ==
 319                                           (v != 0))))
 320             goto done;
 321           if (v)
 322             {
 323               if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
 324                 goto done;
 325             }
 326         }
 327     }
 328
 329 done:
 330   mhash_free (h);
 331   vec_free (vals);
 332   clib_bitmap_free (is_inserted);
 333
 334   for (i = 0; i < vec_len (keys); i++)
 335     vec_free (keys[i]);
 336   vec_free (keys);
 337
 338   if (verbose)
 339     fformat (stderr, "%U\n", format_clib_mem_usage, /* verbose */ 0);
 340
 341   return error;
 342 }
 343
 344 int
 345 test_mhash_main (unformat_input_t *input)
 346 {
 347   mhash_test_t _ht = { 0 }, *ht = &_ht;
 348   clib_error_t *error;
 349
 350   ht->n_iterations = 100;
 351   ht->n_pairs = 10;
 352
 353   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 354     {
 355       if (0 == unformat (input, "iter %d", &ht->n_iterations) &&
 356           0 == unformat (input, "print %d", &ht->n_iterations_per_print) &&
 357           0 == unformat (input, "elts %d", &ht->n_pairs) &&
 358           0 == unformat (input, "seed %d", &ht->seed) &&
 359           0 == unformat (input, "verbose %=", &ht->verbose, 1) &&
 360           0 == unformat (input, "valid %d", &ht->n_iterations_per_validate))
 361         {
 362           clib_warning ("unknown input `%U'", format_unformat_error, input);
 363           return 1;
 364         }
 365     }
 366
 367   if (!ht->seed)
 368     ht->seed = random_default_seed ();
 369
 370   if_verbose ("testing %d iterations, seed %d", ht->n_iterations, ht->seed);
 371
 372   error = test_word_key (ht);
 373   if (error)
 374     clib_error_report (error);
 375
 376   error = test_string_key (ht, 0);
 377   if (error)
 378     clib_error_report (error);
 379
 380   error = test_string_key (ht, 1);
 381   if (error)
 382     clib_error_report (error);
 383
 384   return 0;
 385 }
 386
 387 #ifdef CLIB_UNIX
 388 int
 389 main (int argc, char *argv[])
 390 {
 391   unformat_input_t i;
 392   int ret;
 393
 394   clib_mem_init (0, 3ULL << 30);
 395
 396   verbose = (argc > 1);
 397   unformat_init_command_line (&i, argv);
 398   ret = test_mhash_main (&i);
 399   unformat_free (&i);
 400
 401   return ret;
 402 }
 403 #endif /* CLIB_UNIX */