src/vppinfra/test_cuckoo_template.c

   1 /*
   2  * Copyright (c) 2017 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 #include <vppinfra/heap.h>
  20 #include <vppinfra/format.h>
  21 #include <vppinfra/pool.h>
  22 #include <vppinfra/error.h>
  23 #include <vppinfra/hash.h>
  24 #include <vppinfra/cache.h>
  25
  26 #include <vppinfra/time.h>
  27 #include <vppinfra/cache.h>
  28 #include <vppinfra/error.h>
  29
  30 #include <vppinfra/cuckoo_8_8.h>
  31 #include <vppinfra/cuckoo_template.h>
  32 #include <vppinfra/cuckoo_template.c>
  33
  34 typedef struct
  35 {
  36   u64 seed;
  37   u32 nbuckets;
  38   u32 nitems;
  39   u32 search_iter;
  40   int careful_delete_tests;
  41   int verbose;
  42   int non_random_keys;
  43   uword *key_hash;
  44   u64 *keys;
  45     CVT (clib_cuckoo) hash;
  46   clib_time_t clib_time;
  47
  48   unformat_input_t *input;
  49
  50 } test_main_t;
  51
  52 test_main_t test_main;
  53
  54 uword
  55 vl (void *v)
  56 {
  57   return vec_len (v);
  58 }
  59
  60 void
  61 do_search (test_main_t * tm, CVT (clib_cuckoo) * h)
  62 {
  63   int i, j;
  64   CVT (clib_cuckoo_kv) kv;
  65   for (j = 0; j < tm->search_iter; j++)
  66     {
  67       for (i = 0; i < tm->nitems; i++)
  68         {
  69           kv.key = tm->keys[i];
  70           if (CV (clib_cuckoo_search) (h, &kv, &kv) < 0)
  71             if (CV (clib_cuckoo_search) (h, &kv, &kv) < 0)
  72               clib_warning ("[%d] search for key %llu failed unexpectedly\n",
  73                             i, tm->keys[i]);
  74           if (kv.value != (u64) (i + 1))
  75             clib_warning
  76               ("[%d] search for key %llu returned %llu, not %llu\n", i,
  77                tm->keys[i], kv.value, (u64) (i + 1));
  78         }
  79     }
  80 }
  81
  82 static void
  83 cb (CVT (clib_cuckoo) * h, void *ctx)
  84 {
  85   fformat (stdout, "Garbage callback called...");
  86   if (clib_cpu_time_now () % 3)
  87     {
  88       fformat (stdout, "collecting garbage...\n");
  89       CV (clib_cuckoo_garbage_collect) (h);
  90     }
  91   else
  92     {
  93       fformat (stdout, "ignoring for now...\n");
  94     }
  95 }
  96
  97 static clib_error_t *
  98 test_cuckoo (test_main_t * tm)
  99 {
 100   int i;
 101   uword *p;
 102   uword total_searches;
 103   f64 before, delta;
 104   CVT (clib_cuckoo) * h;
 105   CVT (clib_cuckoo_kv) kv;
 106
 107   h = &tm->hash;
 108
 109   CV (clib_cuckoo_init) (h, "test", tm->nbuckets, cb, NULL);
 110
 111   fformat (stdout, "Pick %lld unique %s keys...\n", tm->nitems,
 112            tm->non_random_keys ? "non-random" : "random");
 113
 114   for (i = 0; i < tm->nitems; i++)
 115     {
 116       u64 rndkey;
 117
 118       if (tm->non_random_keys == 0)
 119         {
 120
 121         again:
 122           rndkey = random_u64 (&tm->seed);
 123
 124           p = hash_get (tm->key_hash, rndkey);
 125           if (p)
 126             goto again;
 127         }
 128       else
 129         rndkey = (u64) (i + 1) << 16;
 130
 131       hash_set (tm->key_hash, rndkey, i + 1);
 132       vec_add1 (tm->keys, rndkey);
 133     }
 134
 135   fformat (stdout, "Add items...\n");
 136   for (i = 0; i < tm->nitems; i++)
 137     {
 138       kv.key = tm->keys[i];
 139       kv.value = i + 1;
 140
 141       CV (clib_cuckoo_add_del) (h, &kv, 1 /* is_add */ ,
 142                                 0 /* overwrite */ );
 143
 144       if (tm->verbose > 1)
 145         {
 146           fformat (stdout, "--------------------\n");
 147           fformat (stdout, "After adding key %llu value %lld...\n",
 148                    tm->keys[i], (u64) (i + 1));
 149           fformat (stdout, "%U", CV (format_cuckoo), h,
 150                    2 /* very verbose */ );
 151         }
 152
 153       CVT (clib_cuckoo_kv) kv2;
 154       int rv = CV (clib_cuckoo_search) (h, &kv, &kv2);
 155       ASSERT (CLIB_CUCKOO_ERROR_SUCCESS == rv);
 156     }
 157
 158   fformat (stdout, "%U", CV (format_cuckoo), h, 0 /* very verbose */ );
 159
 160   fformat (stdout, "Search for items %d times...\n", tm->search_iter);
 161
 162   before = clib_time_now (&tm->clib_time);
 163
 164   do_search (tm, h);
 165
 166   delta = clib_time_now (&tm->clib_time) - before;
 167   total_searches = (uword) tm->search_iter * (uword) tm->nitems;
 168
 169   if (delta > 0)
 170     fformat (stdout, "%.f searches per second\n",
 171              ((f64) total_searches) / delta);
 172
 173   fformat (stdout, "%lld searches in %.6f seconds\n", total_searches, delta);
 174
 175 #if 0
 176   int j;
 177   fformat (stdout, "Standard E-hash search for items %d times...\n",
 178            tm->search_iter);
 179
 180   before = clib_time_now (&tm->clib_time);
 181
 182   for (j = 0; j < tm->search_iter; j++)
 183     {
 184       for (i = 0; i < tm->nitems; i++)
 185         {
 186           p = hash_get (tm->key_hash, tm->keys[i]);
 187           if (p == 0 || p[0] != (uword) (i + 1))
 188             clib_warning ("ugh, couldn't find %lld\n", tm->keys[i]);
 189         }
 190     }
 191
 192   delta = clib_time_now (&tm->clib_time) - before;
 193   total_searches = (uword) tm->search_iter * (uword) tm->nitems;
 194
 195   fformat (stdout, "%lld searches in %.6f seconds\n", total_searches, delta);
 196
 197   if (delta > 0)
 198     fformat (stdout, "%.f searches per second\n",
 199              ((f64) total_searches) / delta);
 200
 201 #endif
 202   fformat (stdout, "Delete items...\n");
 203
 204   for (i = 0; i < tm->nitems; i++)
 205     {
 206       int j;
 207       int rv;
 208
 209       kv.key = tm->keys[i];
 210       kv.value = (u64) (i + 1);
 211       rv = CV (clib_cuckoo_add_del) (h, &kv, 0 /* is_add */ ,
 212                                      0 /* dont_overwrite */ );
 213
 214       if (rv < 0)
 215         clib_warning ("delete key %lld not ok but should be", tm->keys[i]);
 216
 217       if (tm->careful_delete_tests)
 218         {
 219           for (j = 0; j < tm->nitems; j++)
 220             {
 221               kv.key = tm->keys[j];
 222               rv = CV (clib_cuckoo_search) (h, &kv, &kv);
 223               if (j <= i && rv >= 0)
 224                 {
 225                   clib_warning
 226                     ("i %d j %d search ok but should not be, value %lld", i,
 227                      j, kv.value);
 228                 }
 229               if (j > i && rv < 0)
 230                 {
 231                   clib_warning ("i %d j %d search not ok but should be", i,
 232                                 j);
 233                 }
 234             }
 235         }
 236     }
 237
 238   fformat (stdout, "After deletions, should be empty...\n");
 239
 240   fformat (stdout, "%U", CV (format_cuckoo), h, 0 /* very verbose */ );
 241   return 0;
 242 }
 243
 244 clib_error_t *
 245 test_cuckoo_main (test_main_t * tm)
 246 {
 247   unformat_input_t *i = tm->input;
 248   clib_error_t *error;
 249
 250   while (unformat_check_input (i) != UNFORMAT_END_OF_INPUT)
 251     {
 252       if (unformat (i, "seed %u", &tm->seed))
 253         ;
 254       else if (unformat (i, "nbuckets %d", &tm->nbuckets))
 255         ;
 256       else if (unformat (i, "non-random-keys"))
 257         tm->non_random_keys = 1;
 258       else if (unformat (i, "nitems %d", &tm->nitems))
 259         ;
 260       else if (unformat (i, "careful %d", &tm->careful_delete_tests))
 261         ;
 262       else if (unformat (i, "verbose %d", &tm->verbose))
 263         ;
 264       else if (unformat (i, "search %d", &tm->search_iter))
 265         ;
 266       else if (unformat (i, "verbose"))
 267         tm->verbose = 1;
 268       else
 269         return clib_error_return (0, "unknown input '%U'",
 270                                   format_unformat_error, i);
 271     }
 272
 273   error = test_cuckoo (tm);
 274
 275   return error;
 276 }
 277
 278 #ifdef CLIB_UNIX
 279 int
 280 main (int argc, char *argv[])
 281 {
 282   unformat_input_t i;
 283   clib_error_t *error;
 284   test_main_t *tm = &test_main;
 285
 286   clib_mem_init (0, 3ULL << 30);
 287
 288   tm->input = &i;
 289   tm->seed = 0xdeaddabe;
 290
 291   tm->nbuckets = 2;
 292   tm->nitems = 100000;
 293   tm->verbose = 1;
 294   tm->search_iter = 10000;
 295   tm->careful_delete_tests = 0;
 296   tm->key_hash = hash_create (0, sizeof (uword));
 297   clib_time_init (&tm->clib_time);
 298
 299   unformat_init_command_line (&i, argv);
 300   error = test_cuckoo_main (tm);
 301   unformat_free (&i);
 302
 303   if (error)
 304     {
 305       clib_error_report (error);
 306       return 1;
 307     }
 308   return 0;
 309 }
 310 #endif /* CLIB_UNIX */
 311
 312 /*
 313  * fd.io coding-style-patch-verification: ON
 314  *
 315  * Local Variables:
 316  * eval: (c-set-style "gnu")
 317  * End:
 318  */