vppinfra/vppinfra/test_pfhash.c

   1 /*
   2   Copyright (c) 2013 Cisco and/or its affiliates.
   3
   4   * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15 */
  16
  17 #include <vppinfra/pfhash.h>
  18 #include <vppinfra/format.h>
  19 #include <vppinfra/random.h>
  20
  21 #if defined(CLIB_HAVE_VEC128) && ! defined (__ALTIVEC__)
  22
  23 int verbose = 0;
  24
  25 always_inline u8 *
  26 random_aligned_string (u32 * seed, uword len)
  27 {
  28   u8 * alphabet = (u8 *) "abcdefghijklmnopqrstuvwxyz";
  29   u8 * s = 0;
  30   word i;
  31
  32   vec_resize_aligned (s, len, 16);
  33   for (i = 0; i < len; i++)
  34     s[i] = alphabet[random_u32 (seed) % 26];
  35
  36   return s;
  37 }
  38
  39 void exit(int);
  40
  41 int test_pfhash_main (unformat_input_t * input)
  42 {
  43     u32 seed = 0xdeaddabe;
  44     int i, iter;
  45     u32 nkeys = 4;
  46     u32 niter = 1;
  47     u32 nbuckets = 1;
  48     u32 bucket;
  49     u32 sizes[3] = {16, 8, 4}, this_size, size;
  50     u8 ** keys = 0;
  51     pfhash_t _rec, * p = &_rec;
  52
  53     while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
  54       {
  55         if (unformat (input, "seed %d", &seed))
  56           ;
  57         else if (unformat (input, "niter %d", &niter))
  58           ;
  59         else if (unformat (input, "nkeys %d", &nkeys))
  60           ;
  61         else if (unformat (input, "nbuckets %d", &nbuckets))
  62           ;
  63         else if (unformat (input, "verbose %d", &verbose))
  64           ;
  65         else if (unformat (input, "verbose"))
  66           verbose = 1;
  67         else
  68           clib_error ("unknown input `%U'", format_unformat_error, input);
  69       }
  70
  71     vec_validate (keys, nkeys-1);
  72
  73     for (i = 0; i < nkeys; i++)
  74       {
  75         int j, k;
  76
  77       again:
  78         keys[i] = random_aligned_string (&seed, 16);
  79         for (j = 0; j < (i - 1); j++)
  80           {
  81             /* Make sure we don't have a dup key in the min key size */
  82             for (k = 0; k < 4; k++)
  83               {
  84                 if (keys[i][k] != keys[j][k])
  85                   goto check_next_key;
  86               }
  87             vec_free (keys[i]);
  88             goto again;
  89           check_next_key:
  90             ;
  91           }
  92       }
  93
  94     /* test 8 byte key, 8 byte value case separately */
  95
  96     for (size = 8; size < 9; size++)
  97       {
  98         this_size = 8;
  99
 100         fformat (stdout, "%d-byte key 8 byte value test\n", this_size);
 101
 102         pfhash_init (p, "test", 8 /* key size */ , 8 /* value size */,
 103                      nbuckets+1);
 104
 105         for (iter = 0; iter < niter; iter++)
 106           {
 107             bucket = 0;
 108             for (i = 0; i < nkeys; i++)
 109               {
 110                 bucket = (i % nbuckets)+1;
 111                 pfhash_set (p, bucket, keys[i],
 112                             (void *) (u64) 0x100000000ULL + i+1);
 113               }
 114
 115             for (i = 0; i < nkeys; i++)
 116               {
 117                 bucket = (i % nbuckets)+1;
 118                 if (pfhash_get (p, bucket, keys[i])
 119                     != (u64) 0x100000000ULL + i+1)
 120                   {
 121                     clib_warning ("key %d bucket %d lookup FAIL\n", i, bucket);
 122                     (void) pfhash_get (p, bucket , keys[i]);
 123                   }
 124               }
 125
 126             /* test inline functions */
 127             for (i = 0; i < nkeys; i++)
 128               {
 129                 u32 bucket_contents;
 130                 u64 value = 0xdeadbeef;
 131                 bucket = (i % nbuckets)+1;
 132
 133                 pfhash_prefetch_bucket (p, bucket);
 134                 bucket_contents = pfhash_read_bucket_prefetch_kv (p, bucket);
 135
 136                 value = pfhash_search_kv_8v8 (p, bucket_contents,
 137                                               (u64 *) keys[i]);
 138                 if (value != (u64) 0x100000000ULL + i+1)
 139                   clib_warning ("key %d bucket %d lookup FAIL\n", i, bucket);
 140               }
 141
 142             if (verbose)
 143               fformat (stdout, "%U\n", format_pfhash, p, verbose > 1);
 144
 145             for (i = 0; i < nkeys; i++)
 146               {
 147                 bucket = (i % nbuckets)+1;
 148                 pfhash_unset (p, bucket, keys[i]);
 149               }
 150
 151             for (i = 0; i < nkeys; i++)
 152               {
 153                 bucket = (i % nbuckets)+1;
 154                 if (pfhash_get (p, bucket , keys[i]) != (u64)~0)
 155                   {
 156                     clib_warning ("key %d bucket %d lookup FAIL\n", i, bucket);
 157                     (void) pfhash_get (p, bucket , keys[i]);
 158                   }
 159               }
 160             /* test inline functions */
 161             for (i = 0; i < nkeys; i++)
 162               {
 163                 u32 bucket_contents;
 164                 u64 value = 0xdeadbeef;
 165                 bucket = (i % nbuckets)+1;
 166
 167                 pfhash_prefetch_bucket (p, bucket);
 168                 bucket_contents = pfhash_read_bucket_prefetch_kv (p, bucket);
 169
 170                 value = pfhash_search_kv_8v8 (p, bucket_contents,
 171                                               (u64 *) keys[i]);
 172
 173                 if (value != (u64)~0)
 174                   clib_warning ("key %d bucket %d lookup FAIL\n", i, bucket);
 175               }
 176           }
 177         pfhash_free (p);
 178       }
 179
 180     /* test other cases */
 181
 182     for (size = 0; size < ARRAY_LEN(sizes); size++)
 183       {
 184         this_size = sizes[size];
 185
 186         fformat (stdout, "%d-byte key test\n", this_size);
 187
 188         pfhash_init (p, "test", this_size, 4 /* value size */, nbuckets+1);
 189
 190         for (iter = 0; iter < niter; iter++)
 191           {
 192             bucket = 0;
 193             for (i = 0; i < nkeys; i++)
 194               {
 195                 bucket = (i % nbuckets)+1;
 196                 pfhash_set (p, bucket, keys[i], (void *)(u64)i+1);
 197               }
 198
 199             for (i = 0; i < nkeys; i++)
 200               {
 201                 bucket = (i % nbuckets)+1;
 202                 if (pfhash_get (p, bucket , keys[i]) != i+1)
 203                   {
 204                     clib_warning ("key %d bucket %d lookup FAIL\n", i, bucket);
 205                     (void) pfhash_get (p, bucket , keys[i]);
 206                   }
 207               }
 208
 209             /* test inline functions */
 210             for (i = 0; i < nkeys; i++)
 211               {
 212                 u32 bucket_contents;
 213                 u32 value = 0xdeadbeef;
 214                 bucket = (i % nbuckets)+1;
 215
 216                 pfhash_prefetch_bucket (p, bucket);
 217                 bucket_contents = pfhash_read_bucket_prefetch_kv (p, bucket);
 218                 switch(p->key_size)
 219                   {
 220                   case 16:
 221                     value = pfhash_search_kv_16 (p, bucket_contents, (u32x4 *) keys[i]);
 222                     break;
 223                   case 8:
 224                     value = pfhash_search_kv_8 (p, bucket_contents, (u64 *) keys[i]);
 225                     break;
 226                   case 4:
 227                     value = pfhash_search_kv_4 (p, bucket_contents, (u32 *) keys[i]);
 228                     break;
 229                   }
 230
 231                 if (value != (i+1))
 232                   clib_warning ("key %d bucket %d lookup FAIL\n", i, bucket);
 233               }
 234
 235             if (verbose)
 236               fformat (stdout, "%U\n", format_pfhash, p, verbose > 1);
 237
 238             for (i = 0; i < nkeys; i++)
 239               {
 240                 bucket = (i % nbuckets)+1;
 241                 pfhash_unset (p, bucket, keys[i]);
 242               }
 243
 244             for (i = 0; i < nkeys; i++)
 245               {
 246                 bucket = (i % nbuckets)+1;
 247                 if (pfhash_get (p, bucket , keys[i]) != (u64)~0)
 248                   {
 249                     clib_warning ("key %d bucket %d lookup FAIL\n", i, bucket);
 250                     (void) pfhash_get (p, bucket , keys[i]);
 251                   }
 252               }
 253             /* test inline functions */
 254             for (i = 0; i < nkeys; i++)
 255               {
 256                 u32 bucket_contents;
 257                 u32 value = 0xdeadbeef;
 258                 bucket = (i % nbuckets)+1;
 259
 260                 pfhash_prefetch_bucket (p, bucket);
 261                 bucket_contents = pfhash_read_bucket_prefetch_kv (p, bucket);
 262                 switch(p->key_size)
 263                   {
 264                   case 16:
 265                     value = pfhash_search_kv_16 (p, bucket_contents, (u32x4 *) keys[i]);
 266                     break;
 267                   case 8:
 268                     value = pfhash_search_kv_8 (p, bucket_contents, (u64 *) keys[i]);
 269                     break;
 270                   case 4:
 271                     value = pfhash_search_kv_4 (p, bucket_contents, (u32 *) keys[i]);
 272                     break;
 273                   }
 274                 if (value != (u32)~0)
 275                   clib_warning ("key %d bucket %d lookup FAIL\n", i, bucket);
 276               }
 277           }
 278         pfhash_free (p);
 279       }
 280
 281     exit (0);
 282 }
 283 #else
 284 int test_pfhash_main (unformat_input_t * input)
 285 {
 286   clib_warning ("MMX unit not available");
 287   return 0;
 288 }
 289 #endif
 290
 291 #ifdef CLIB_UNIX
 292 int main (int argc, char * argv[])
 293 {
 294   unformat_input_t i;
 295   int ret;
 296
 297   unformat_init_command_line (&i, argv);
 298   ret = test_pfhash_main (&i);
 299   unformat_free (&i);
 300
 301   return ret;
 302 }
 303 #endif /* CLIB_UNIX */