src/vppinfra/test_flowhash_template.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 #include <vppinfra/time.h>
  17 #include <vppinfra/cache.h>
  18 #include <vppinfra/error.h>
  19
  20 #include <vppinfra/heap.h>
  21 #include <vppinfra/format.h>
  22 #include <vppinfra/random.h>
  23 #include <vppinfra/hash.h>
  24
  25 #include <vppinfra/flowhash_8_8.h>
  26
  27 /* Not actually tested here. But included for compilation purposes. */
  28 #include <vppinfra/flowhash_24_16.h>
  29
  30 typedef struct
  31 {
  32   u64 seed;
  33   u32 fixed_entries;
  34   u32 collision_buckets;
  35   u32 nitems;
  36   u32 iterations;
  37   u32 prefetch;
  38   int non_random_keys;
  39   uword *key_hash;
  40   flowhash_lkey_8_8_t *keys;
  41   flowhash_8_8_t *hash;
  42   clib_time_t clib_time;
  43   unformat_input_t *input;
  44 } test_main_t;
  45
  46 test_main_t test_main;
  47
  48 static clib_error_t *
  49 test_flowhash (test_main_t * tm)
  50 {
  51   f64 before, delta;
  52   u64 total;
  53   u32 overflow;
  54   int i, j;
  55   uword *p;
  56   tm->hash = flowhash_alloc_8_8 (tm->fixed_entries, tm->collision_buckets);
  57   if (tm->hash == NULL)
  58     return clib_error_return (0, "Could not alloc hash");
  59
  60   fformat (stdout, "Allocated hash memory size: %llu\n",
  61            flowhash_memory_size (tm->hash));
  62
  63   fformat (stdout, "Pick %lld unique %s keys...\n",
  64            tm->nitems, tm->non_random_keys ? "non-random" : "random");
  65
  66   for (i = 0; i < tm->nitems; i++)
  67     {
  68       flowhash_lkey_8_8_t rndkey;
  69       if (tm->non_random_keys == 0)
  70         {
  71         again:
  72           rndkey.as_u64[0] = random_u64 (&tm->seed);
  73           if ((p = hash_get (tm->key_hash, rndkey.as_u64[0])))
  74             goto again;
  75         }
  76       else
  77         rndkey.as_u64[0] = (u64) (i + 1) << 16;
  78
  79       hash_set (tm->key_hash, rndkey.as_u64[0], i + 1);
  80       vec_add1 (tm->keys, rndkey);
  81     }
  82
  83   hash_free (tm->key_hash);
  84
  85   /* Additions */
  86   overflow = 0;
  87   before = clib_time_now (&tm->clib_time);
  88   fformat (stdout, "Adding %u items...\n", tm->nitems);
  89   for (i = 0; i < tm->nitems; i++)
  90     {
  91       u32 hash = flowhash_hash_8_8 (&tm->keys[i]);
  92       u32 ei;
  93       flowhash_get_8_8 (tm->hash, &tm->keys[i], hash, 1, &ei);
  94       if (flowhash_is_overflow (ei))
  95         overflow++;
  96
  97       /* Set value (No matter if success) */
  98       flowhash_value (tm->hash, ei)->as_u64[0] = i + 1;
  99
 100       /* Save value until time > 1 */
 101       flowhash_timeout (tm->hash, ei) = 1;
 102     }
 103
 104   delta = clib_time_now (&tm->clib_time) - before;
 105   total = tm->nitems;
 106   fformat (stdout, "%lld additions in %.6f seconds\n", total, delta);
 107   if (delta > 0)
 108     fformat (stdout, "%.f additions per second\n", ((f64) total) / delta);
 109
 110   fformat (stdout, "%u elements in table\n", flowhash_elts_8_8 (tm->hash, 1));
 111   fformat (stdout, "Flowhash counters:\n");
 112   fformat (stdout, "  collision-lookup: %lu\n",
 113            tm->hash->collision_lookup_counter);
 114   fformat (stdout, "  not-enough-buckets: %lu\n",
 115            tm->hash->not_enough_buckets_counter);
 116   fformat (stdout, "  overflows: %lu\n", overflow);
 117
 118   /* Lookups (very similar to additions) */
 119   overflow = 0;
 120   before = clib_time_now (&tm->clib_time);
 121   fformat (stdout, "Looking up %u items %u times...\n", tm->nitems,
 122            tm->iterations);
 123
 124   for (j = 0; j < tm->iterations; j++)
 125     {
 126       i = 0;
 127       if (tm->prefetch)
 128         for (; i < tm->nitems - tm->prefetch; i++)
 129           {
 130             u32 ei;
 131             u32 hash = flowhash_hash_8_8 (&tm->keys[i + tm->prefetch]);
 132             flowhash_prefetch (tm->hash, hash);
 133             hash = flowhash_hash_8_8 (&tm->keys[i]);
 134             flowhash_get_8_8 (tm->hash, &tm->keys[i], hash, 1, &ei);
 135             if (flowhash_is_overflow (ei))
 136               overflow++;
 137             else if (flowhash_timeout (tm->hash, ei) != 1)
 138               clib_warning ("Key not found: %lld\n", tm->keys[i].as_u64[0]);
 139             else if (flowhash_value (tm->hash, ei)->as_u64[0] != i + 1)
 140               clib_warning ("Value mismatch for key %lld\n",
 141                             tm->keys[i].as_u64[0]);
 142           }
 143
 144       for (; i < tm->nitems; i++)
 145         {
 146           u32 ei;
 147           u32 hash = flowhash_hash_8_8 (&tm->keys[i]);
 148           flowhash_get_8_8 (tm->hash, &tm->keys[i], hash, 1, &ei);
 149           if (flowhash_is_overflow (ei))
 150             overflow++;
 151           else if (flowhash_timeout (tm->hash, ei) != 1)
 152             clib_warning ("Key not found: %lld\n", tm->keys[i].as_u64[0]);
 153           else if (flowhash_value (tm->hash, ei)->as_u64[0] != i + 1)
 154             clib_warning ("Value mismatch for key %lld\n",
 155                           tm->keys[i].as_u64[0]);
 156         }
 157     }
 158
 159   delta = clib_time_now (&tm->clib_time) - before;
 160   total = tm->nitems * tm->iterations;
 161   fformat (stdout, "%lld lookups in %.6f seconds\n", total, delta);
 162   if (delta > 0)
 163     fformat (stdout, "%.f lookups per second\n", ((f64) total) / delta);
 164
 165   /* Delete */
 166   for (i = 0; i < tm->nitems; i++)
 167     {
 168       u32 hash = flowhash_hash_8_8 (&tm->keys[i]);
 169       u32 ei;
 170       flowhash_get_8_8 (tm->hash, &tm->keys[i], hash, 1, &ei);
 171       flowhash_timeout (tm->hash, ei) = 0;
 172     }
 173
 174   fformat (stdout, "%u elements in table\n", flowhash_elts_8_8 (tm->hash, 1));
 175
 176   vec_free (tm->keys);
 177   flowhash_free_8_8 (tm->hash);
 178
 179   return NULL;
 180 }
 181
 182 clib_error_t *
 183 test_flowhash_main (test_main_t * tm)
 184 {
 185   unformat_input_t *i = tm->input;
 186   clib_error_t *error;
 187
 188   while (unformat_check_input (i) != UNFORMAT_END_OF_INPUT)
 189     {
 190       if (unformat (i, "seed %u", &tm->seed))
 191         ;
 192       else if (unformat (i, "fixed-entries %d", &tm->fixed_entries))
 193         ;
 194       else if (unformat (i, "collision-buckets %d", &tm->collision_buckets))
 195         ;
 196       else if (unformat (i, "non-random-keys"))
 197         tm->non_random_keys = 1;
 198       else if (unformat (i, "nitems %d", &tm->nitems))
 199         ;
 200       else if (unformat (i, "prefetch %d", &tm->prefetch))
 201         ;
 202       else if (unformat (i, "iterations %d", &tm->iterations))
 203         ;
 204       else
 205         return clib_error_return (0, "unknown input '%U'",
 206                                   format_unformat_error, i);
 207     }
 208
 209   error = test_flowhash (tm);
 210   return error;
 211 }
 212
 213 #ifdef CLIB_UNIX
 214 int
 215 main (int argc, char *argv[])
 216 {
 217
 218   unformat_input_t i;
 219   clib_error_t *error;
 220   test_main_t *tm = &test_main;
 221
 222   clib_mem_init (0, 3ULL << 30);
 223
 224   tm->fixed_entries = 8 << 20;
 225   tm->collision_buckets = 1 << 20;
 226   tm->seed = 0xdeadf00l;
 227   tm->iterations = 1;
 228   tm->input = &i;
 229   tm->nitems = 1000;
 230   tm->non_random_keys = 0;
 231   tm->key_hash = hash_create (0, sizeof (uword));
 232   tm->prefetch = 0;
 233   clib_time_init (&tm->clib_time);
 234
 235   unformat_init_command_line (&i, argv);
 236   error = test_flowhash_main (tm);
 237   unformat_free (&i);
 238
 239   if (error)
 240     {
 241       clib_error_report (error);
 242       return 1;
 243     }
 244   return 0;
 245
 246   return 0;
 247 }
 248 #endif /* CLIB_UNIX */
 249
 250
 251 /*
 252  * fd.io coding-style-patch-verification: ON
 253  *
 254  * Local Variables:
 255  * eval: (c-set-style "gnu")
 256  * End:
 257  */