vppinfra/vppinfra/vhash.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) 2010 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 #include <vppinfra/vhash.h>
  39
  40 #ifdef CLIB_HAVE_VEC128
  41
  42 /* Overflow search buckets have an extra u32x4 for saving key_hash data.
  43    This makes it easier to refill main search bucket from overflow vector. */
  44 typedef struct {
  45   /* 4 results for this bucket. */
  46   u32x4_union_t result;
  47
  48   /* 4 hash codes for this bucket.  These are used to refill main
  49      search buckets from overflow buckets when space becomes available. */
  50   u32x4_union_t key_hash;
  51
  52   /* n_key_u32s u32x4s of key data follow. */
  53   u32x4_union_t key[0];
  54 } vhash_overflow_search_bucket_t;
  55
  56 always_inline void
  57 set_overflow_result (vhash_overflow_search_bucket_t * b,
  58                      u32 i,
  59                      u32 result,
  60                      u32 key_hash)
  61 {
  62   b->result.as_u32[i] = result;
  63   b->key_hash.as_u32[i] = key_hash;
  64 }
  65
  66 always_inline void
  67 free_overflow_bucket (vhash_overflow_buckets_t * ob,
  68                       vhash_overflow_search_bucket_t * b,
  69                       u32 i)
  70 {
  71   u32 o = (u32x4_union_t *) b - ob->search_buckets;
  72   ASSERT (o < vec_len (ob->search_buckets));
  73   vec_add1 (ob->free_indices, 4 * o + i);
  74 }
  75
  76 always_inline vhash_overflow_search_bucket_t *
  77 get_overflow_search_bucket (vhash_overflow_buckets_t * obs, u32 i, u32 n_key_u32s)
  78 {
  79   return ((vhash_overflow_search_bucket_t *)
  80           vec_elt_at_index (obs->search_buckets, i));
  81 }
  82
  83 always_inline vhash_overflow_search_bucket_t *
  84 next_overflow_bucket (vhash_overflow_search_bucket_t * b, u32 n_key_u32s)
  85 { return (vhash_overflow_search_bucket_t *) &b->key[n_key_u32s]; }
  86
  87 #define foreach_vhash_overflow_bucket(b,ob,n_key_u32s)                  \
  88   for ((b) = (vhash_overflow_search_bucket_t *) ob->search_buckets;     \
  89        (u32x4_union_t *) (b) < vec_end (ob->search_buckets);            \
  90        b = next_overflow_bucket (b, n_key_u32s))
  91
  92 u32
  93 vhash_get_overflow (vhash_t * h,
  94                     u32 key_hash,
  95                     u32 vi,
  96                     u32 n_key_u32s)
  97 {
  98   vhash_overflow_buckets_t * ob = vhash_get_overflow_buckets (h, key_hash);
  99   vhash_overflow_search_bucket_t * b;
 100   u32 i, result = 0;
 101
 102   foreach_vhash_overflow_bucket (b, ob, n_key_u32s)
 103     {
 104       u32x4 r = b->result.as_u32x4;
 105
 106       for (i = 0; i < n_key_u32s; i++)
 107         r &= vhash_bucket_compare (h, &b->key[0], i, vi);
 108
 109       result = vhash_merge_results (r);
 110       if (result)
 111         break;
 112     }
 113
 114   return result;
 115 }
 116
 117 u32
 118 vhash_set_overflow (vhash_t * h,
 119                     u32 key_hash,
 120                     u32 vi,
 121                     u32 new_result,
 122                     u32 n_key_u32s)
 123 {
 124   vhash_overflow_buckets_t * ob = vhash_get_overflow_buckets (h, key_hash);
 125   vhash_overflow_search_bucket_t * b;
 126   u32 i_set, i, old_result;
 127
 128   foreach_vhash_overflow_bucket (b, ob, n_key_u32s)
 129     {
 130       u32x4 r;
 131
 132       r = b->result.as_u32x4;
 133       for (i = 0; i < n_key_u32s; i++)
 134         r &= vhash_bucket_compare (h, &b->key[0], i, vi);
 135
 136       old_result = vhash_merge_results (r);
 137       if (old_result)
 138         {
 139           i_set = vhash_non_empty_result_index (r);
 140           set_overflow_result (b, i_set, new_result, key_hash);
 141           return old_result;
 142         }
 143     }
 144
 145   /* Check free list. */
 146   if (vec_len (ob->free_indices) == 0)
 147     {
 148       /* Out of free overflow buckets.  Resize. */
 149       u32 j, * p;
 150       i = vec_len (ob->search_buckets);
 151       vec_resize_aligned (ob->search_buckets,
 152                           sizeof (b[0]) / sizeof (u32x4) + n_key_u32s,
 153                           CLIB_CACHE_LINE_BYTES);
 154       vec_add2 (ob->free_indices, p, 4);
 155       for (j = 0; j < 4; j++)
 156         p[j] = 4 * i + j;
 157     }
 158
 159   i = vec_pop (ob->free_indices);
 160
 161   i_set = i & 3;
 162   b = ((vhash_overflow_search_bucket_t *)
 163        vec_elt_at_index (ob->search_buckets, i / 4));
 164
 165   /* Insert result. */
 166   set_overflow_result (b, i_set, new_result, key_hash);
 167
 168   /* Insert key. */
 169   for (i = 0; i < n_key_u32s; i++)
 170     b->key[i].as_u32[i_set] = vhash_get_key_word (h, i, vi);
 171
 172   ob->n_overflow++;
 173   h->n_elts++;
 174
 175   return /* old result was invalid */ 0;
 176 }
 177
 178 u32
 179 vhash_unset_overflow (vhash_t * h,
 180                       u32 key_hash,
 181                       u32 vi,
 182                       u32 n_key_u32s)
 183 {
 184   vhash_overflow_buckets_t * ob = vhash_get_overflow_buckets (h, key_hash);
 185   vhash_overflow_search_bucket_t * b;
 186   u32 i_set, i, old_result;
 187
 188   foreach_vhash_overflow_bucket (b, ob, n_key_u32s)
 189     {
 190       u32x4 r;
 191
 192       r = b->result.as_u32x4;
 193       for (i = 0; i < n_key_u32s; i++)
 194         r &= vhash_bucket_compare (h, &b->key[0], i, vi);
 195
 196       old_result = vhash_merge_results (r);
 197       if (old_result)
 198         {
 199           i_set = vhash_non_empty_result_index (r);
 200
 201           /* Invalidate result and invert key hash so that this will
 202              never match since all keys in this overflow bucket have
 203              matching key hashs. */
 204           set_overflow_result (b, i_set, 0, ~key_hash);
 205
 206           free_overflow_bucket (ob, b, i_set);
 207
 208           ASSERT (ob->n_overflow > 0);
 209           ob->n_overflow--;
 210           h->n_elts--;
 211           return old_result;
 212         }
 213     }
 214
 215   /* Could not find key. */
 216   return 0;
 217 }
 218
 219 void
 220 vhash_unset_refill_from_overflow (vhash_t * h,
 221                                   vhash_search_bucket_t * sb,
 222                                   u32 key_hash,
 223                                   u32 n_key_u32s)
 224 {
 225   vhash_overflow_buckets_t * obs = vhash_get_overflow_buckets (h, key_hash);
 226   vhash_overflow_search_bucket_t * ob;
 227   u32 i, j, i_refill, bucket_mask = h->bucket_mask.as_u32[0];
 228
 229   /* Find overflow element with matching key hash. */
 230   foreach_vhash_overflow_bucket (ob, obs, n_key_u32s)
 231     {
 232       for (i = 0; i < 4; i++)
 233         {
 234           if (! ob->result.as_u32[i])
 235             continue;
 236           if ((ob->key_hash.as_u32[i] & bucket_mask)
 237               != (key_hash & bucket_mask))
 238             continue;
 239
 240           i_refill = vhash_empty_result_index (sb->result.as_u32x4);
 241           sb->result.as_u32[i_refill] = ob->result.as_u32[i];
 242           for (j = 0; j < n_key_u32s; j++)
 243             sb->key[j].as_u32[i_refill] = ob->key[j].as_u32[i];
 244           set_overflow_result (ob, i, 0, ~key_hash);
 245           free_overflow_bucket (obs, ob, i);
 246           return;
 247         }
 248     }
 249 }
 250
 251 void vhash_init (vhash_t * h, u32 log2_n_keys, u32 n_key_u32, u32 * hash_seeds)
 252 {
 253   uword i, j, m;
 254   vhash_search_bucket_t * b;
 255
 256   memset (h, 0, sizeof (h[0]));
 257
 258   /* Must have at least 4 keys (e.g. one search bucket). */
 259   log2_n_keys = clib_max (log2_n_keys, 2);
 260
 261   h->log2_n_keys = log2_n_keys;
 262   h->n_key_u32 = n_key_u32;
 263   m = pow2_mask (h->log2_n_keys) &~ 3;
 264   for (i = 0; i < VECTOR_WORD_TYPE_LEN (u32); i++)
 265     h->bucket_mask.as_u32[i] = m;
 266
 267   /* Allocate and zero search buckets. */
 268   i = (sizeof (b[0]) / sizeof (u32x4) + n_key_u32) << (log2_n_keys - 2);
 269   vec_validate_aligned (h->search_buckets, i - 1, CLIB_CACHE_LINE_BYTES);
 270
 271   for (i = 0; i < ARRAY_LEN (h->find_first_zero_table); i++)
 272     h->find_first_zero_table[i] = min_log2 (first_set (~i));
 273
 274   for (i = 0; i < ARRAY_LEN (h->hash_seeds); i++)
 275     for (j = 0; j < VECTOR_WORD_TYPE_LEN (u32); j++)
 276       h->hash_seeds[i].as_u32[j] = hash_seeds[i];
 277 }
 278
 279 static_always_inline u32
 280 vhash_main_key_gather (void * _vm, u32 vi, u32 wi, u32 n_key_u32)
 281 {
 282   vhash_main_t * vm = _vm;
 283   return vec_elt (vm->keys, vi * n_key_u32 + wi);
 284 }
 285
 286 static_always_inline u32x4
 287 vhash_main_4key_gather (void * _vm, u32 vi, u32 wi, u32 n_key_u32s)
 288 {
 289   vhash_main_t * vm = _vm;
 290   u32x4_union_t x;
 291
 292   ASSERT (n_key_u32s == vm->n_key_u32);
 293   ASSERT (wi < n_key_u32s);
 294
 295   x.as_u32[0] = vec_elt (vm->keys, (vi + 0) * n_key_u32s + wi);
 296   x.as_u32[1] = vec_elt (vm->keys, (vi + 1) * n_key_u32s + wi);
 297   x.as_u32[2] = vec_elt (vm->keys, (vi + 2) * n_key_u32s + wi);
 298   x.as_u32[3] = vec_elt (vm->keys, (vi + 3) * n_key_u32s + wi);
 299   return x.as_u32x4;
 300 }
 301
 302 static_always_inline u32
 303 vhash_main_set_result (void * _vm, u32 vi, u32 old_result, u32 n_key_u32)
 304 {
 305   vhash_main_t * vm = _vm;
 306   u32 * p = vec_elt_at_index (vm->results, vi);
 307   u32 new_result = p[0];
 308   p[0] = old_result;
 309   return new_result;
 310 }
 311
 312 static_always_inline u32
 313 vhash_main_get_result (void * _vm, u32 vi, u32 old_result, u32 n_key_u32)
 314 {
 315   vhash_main_t * vm = _vm;
 316   vec_elt (vm->results, vi) = old_result;
 317   return old_result;
 318 }
 319
 320 static_always_inline u32x4
 321 vhash_main_get_4result (void * _vm, u32 vi, u32x4 old_result, u32 n_key_u32)
 322 {
 323   vhash_main_t * vm = _vm;
 324   u32x4 * p = (u32x4 *) vec_elt_at_index (vm->results, vi);
 325   p[0] = old_result;
 326   return old_result;
 327 }
 328
 329 #define _(N_KEY_U32)                                                    \
 330   static_always_inline u32                                              \
 331   vhash_main_key_gather_##N_KEY_U32 (void * _vm, u32 vi, u32 i)         \
 332   { return vhash_main_key_gather (_vm, vi, i, N_KEY_U32); }             \
 333                                                                         \
 334   static_always_inline u32x4                                            \
 335   vhash_main_4key_gather_##N_KEY_U32 (void * _vm, u32 vi, u32 i)        \
 336   { return vhash_main_4key_gather (_vm, vi, i, N_KEY_U32); }            \
 337                                                                         \
 338   clib_pipeline_stage_static                                            \
 339   (vhash_main_gather_keys_stage_##N_KEY_U32,                            \
 340    vhash_main_t *, vm, i,                                               \
 341    {                                                                    \
 342      vhash_gather_4key_stage                                            \
 343        (vm->vhash,                                                      \
 344         /* vector_index */ i,                                           \
 345         vhash_main_4key_gather_##N_KEY_U32,                             \
 346         vm,                                                             \
 347         N_KEY_U32);                                                     \
 348    })                                                                   \
 349                                                                         \
 350   clib_pipeline_stage_no_inline                                         \
 351   (vhash_main_gather_keys_mod_stage_##N_KEY_U32,                        \
 352    vhash_main_t *, vm, i,                                               \
 353    {                                                                    \
 354      vhash_gather_key_stage                                             \
 355        (vm->vhash,                                                      \
 356         /* vector_index */ vm->n_vectors_div_4,                         \
 357         /* n_vectors */ vm->n_vectors_mod_4,                            \
 358         vhash_main_key_gather_##N_KEY_U32,                              \
 359         vm,                                                             \
 360         N_KEY_U32);                                                     \
 361    })                                                                   \
 362                                                                         \
 363   clib_pipeline_stage                                                   \
 364   (vhash_main_hash_finalize_stage_##N_KEY_U32,                          \
 365    vhash_main_t *, vm, i,                                               \
 366    {                                                                    \
 367      vhash_finalize_stage (vm->vhash, i, N_KEY_U32);                    \
 368    })                                                                   \
 369                                                                         \
 370   clib_pipeline_stage_no_inline                                         \
 371   (vhash_main_hash_finalize_mod_stage_##N_KEY_U32,                      \
 372    vhash_main_t *, vm, i,                                               \
 373    {                                                                    \
 374      vhash_finalize_stage (vm->vhash, vm->n_vectors_div_4, N_KEY_U32);  \
 375    })                                                                   \
 376                                                                         \
 377   clib_pipeline_stage_static                                            \
 378   (vhash_main_get_stage_##N_KEY_U32,                                    \
 379    vhash_main_t *, vm, i,                                               \
 380    {                                                                    \
 381      vhash_get_4_stage (vm->vhash,                                      \
 382                         /* vector_index */ i,                           \
 383                         vhash_main_get_4result,                         \
 384                         vm, N_KEY_U32);                                 \
 385    })                                                                   \
 386                                                                         \
 387   clib_pipeline_stage_no_inline                                         \
 388   (vhash_main_get_mod_stage_##N_KEY_U32,                                \
 389    vhash_main_t *, vm, i,                                               \
 390    {                                                                    \
 391      vhash_get_stage (vm->vhash,                                        \
 392                       /* vector_index */ vm->n_vectors_div_4,           \
 393                       /* n_vectors */ vm->n_vectors_mod_4,              \
 394                       vhash_main_get_result,                            \
 395                       vm, N_KEY_U32);                                   \
 396    })                                                                   \
 397                                                                         \
 398   clib_pipeline_stage_static                                            \
 399   (vhash_main_set_stage_##N_KEY_U32,                                    \
 400    vhash_main_t *, vm, i,                                               \
 401    {                                                                    \
 402      vhash_set_stage (vm->vhash,                                        \
 403                       /* vector_index */ i,                             \
 404                       /* n_vectors */ VECTOR_WORD_TYPE_LEN (u32),       \
 405                       vhash_main_set_result,                            \
 406                       vm, N_KEY_U32);                                   \
 407    })                                                                   \
 408                                                                         \
 409   clib_pipeline_stage_no_inline                                         \
 410   (vhash_main_set_mod_stage_##N_KEY_U32,                                \
 411    vhash_main_t *, vm, i,                                               \
 412    {                                                                    \
 413      vhash_set_stage (vm->vhash,                                        \
 414                       /* vector_index */ vm->n_vectors_div_4,           \
 415                       /* n_vectors */ vm->n_vectors_mod_4,              \
 416                       vhash_main_set_result,                            \
 417                       vm, N_KEY_U32);                                   \
 418    })                                                                   \
 419                                                                         \
 420   clib_pipeline_stage_static                                            \
 421   (vhash_main_unset_stage_##N_KEY_U32,                                  \
 422    vhash_main_t *, vm, i,                                               \
 423    {                                                                    \
 424      vhash_unset_stage (vm->vhash,                                      \
 425                       /* vector_index */ i,                             \
 426                       /* n_vectors */ VECTOR_WORD_TYPE_LEN (u32),       \
 427                       vhash_main_get_result,                            \
 428                       vm, N_KEY_U32);                                   \
 429    })                                                                   \
 430                                                                         \
 431   clib_pipeline_stage_no_inline                                         \
 432   (vhash_main_unset_mod_stage_##N_KEY_U32,                              \
 433    vhash_main_t *, vm, i,                                               \
 434    {                                                                    \
 435      vhash_unset_stage (vm->vhash,                                      \
 436                       /* vector_index */ vm->n_vectors_div_4,           \
 437                       /* n_vectors */ vm->n_vectors_mod_4,              \
 438                       vhash_main_get_result,                            \
 439                       vm, N_KEY_U32);                                   \
 440    })
 441
 442 _ (1);
 443 _ (2);
 444 _ (3);
 445 _ (4);
 446 _ (5);
 447 _ (6);
 448
 449 #undef _
 450
 451 #define _(N_KEY_U32)                                                    \
 452   clib_pipeline_stage                                                   \
 453   (vhash_main_hash_mix_stage_##N_KEY_U32,                               \
 454    vhash_main_t *, vm, i,                                               \
 455    {                                                                    \
 456      vhash_mix_stage (vm->vhash, i, N_KEY_U32);                         \
 457    })                                                                   \
 458                                                                         \
 459   clib_pipeline_stage_no_inline                                         \
 460   (vhash_main_hash_mix_mod_stage_##N_KEY_U32,                           \
 461    vhash_main_t *, vm, i,                                               \
 462    {                                                                    \
 463      vhash_mix_stage (vm->vhash, vm->n_vectors_div_4, N_KEY_U32);       \
 464    })
 465
 466 _ (4);
 467 _ (5);
 468 _ (6);
 469
 470 #undef _
 471
 472 typedef enum {
 473   GET, SET, UNSET,
 474 } vhash_main_op_t;
 475
 476 static void
 477 vhash_main_op (vhash_main_t * vm, vhash_main_op_t op)
 478 {
 479   u32 n_keys = vec_len (vm->results);
 480
 481   vm->n_key_u32 = vm->vhash->n_key_u32;
 482
 483   vhash_validate_sizes (vm->vhash, vm->n_key_u32, n_keys);
 484
 485   vm->n_vectors_div_4 = n_keys / 4;
 486   vm->n_vectors_mod_4 = n_keys % 4;
 487
 488   if (vm->n_vectors_div_4 > 0)
 489     {
 490       switch (vm->n_key_u32)
 491         {
 492         default:
 493           ASSERT (0);
 494           break;
 495
 496 #define _(N_KEY_U32)                                            \
 497         case N_KEY_U32:                                         \
 498           if (op == GET)                                        \
 499             clib_pipeline_run_3_stage                           \
 500               (vm->n_vectors_div_4,                             \
 501                vm,                                              \
 502                vhash_main_gather_keys_stage_##N_KEY_U32,        \
 503                vhash_main_hash_finalize_stage_##N_KEY_U32,      \
 504                vhash_main_get_stage_##N_KEY_U32);               \
 505           else if (op == SET)                                   \
 506             clib_pipeline_run_3_stage                           \
 507               (vm->n_vectors_div_4,                             \
 508                vm,                                              \
 509                vhash_main_gather_keys_stage_##N_KEY_U32,        \
 510                vhash_main_hash_finalize_stage_##N_KEY_U32,      \
 511                vhash_main_set_stage_##N_KEY_U32);               \
 512           else                                                  \
 513             clib_pipeline_run_3_stage                           \
 514               (vm->n_vectors_div_4,                             \
 515                vm,                                              \
 516                vhash_main_gather_keys_stage_##N_KEY_U32,        \
 517                vhash_main_hash_finalize_stage_##N_KEY_U32,      \
 518                vhash_main_unset_stage_##N_KEY_U32);             \
 519           break;
 520
 521               _ (1);
 522               _ (2);
 523               _ (3);
 524
 525 #undef _
 526
 527 #define _(N_KEY_U32)                                            \
 528         case N_KEY_U32:                                         \
 529           if (op == GET)                                        \
 530             clib_pipeline_run_4_stage                           \
 531               (vm->n_vectors_div_4,                             \
 532                vm,                                              \
 533                vhash_main_gather_keys_stage_##N_KEY_U32,        \
 534                vhash_main_hash_mix_stage_##N_KEY_U32,           \
 535                vhash_main_hash_finalize_stage_##N_KEY_U32,      \
 536                vhash_main_get_stage_##N_KEY_U32);               \
 537           else if (op == SET)                                   \
 538             clib_pipeline_run_4_stage                           \
 539               (vm->n_vectors_div_4,                             \
 540                vm,                                              \
 541                vhash_main_gather_keys_stage_##N_KEY_U32,        \
 542                vhash_main_hash_mix_stage_##N_KEY_U32,           \
 543                vhash_main_hash_finalize_stage_##N_KEY_U32,      \
 544                vhash_main_set_stage_##N_KEY_U32);               \
 545           else                                                  \
 546             clib_pipeline_run_4_stage                           \
 547               (vm->n_vectors_div_4,                             \
 548                vm,                                              \
 549                vhash_main_gather_keys_stage_##N_KEY_U32,        \
 550                vhash_main_hash_mix_stage_##N_KEY_U32,           \
 551                vhash_main_hash_finalize_stage_##N_KEY_U32,      \
 552                vhash_main_unset_stage_##N_KEY_U32);             \
 553           break;
 554
 555               _ (4);
 556               _ (5);
 557               _ (6);
 558
 559 #undef _
 560         }
 561     }
 562
 563
 564   if (vm->n_vectors_mod_4 > 0)
 565     {
 566       switch (vm->n_key_u32)
 567         {
 568         default:
 569           ASSERT (0);
 570           break;
 571
 572 #define _(N_KEY_U32)                                            \
 573         case N_KEY_U32:                                         \
 574           if (op == GET)                                        \
 575             clib_pipeline_run_3_stage                           \
 576               (1,                                               \
 577                vm,                                              \
 578                vhash_main_gather_keys_mod_stage_##N_KEY_U32,    \
 579                vhash_main_hash_finalize_mod_stage_##N_KEY_U32,  \
 580                vhash_main_get_mod_stage_##N_KEY_U32);           \
 581           else if (op == SET)                                   \
 582             clib_pipeline_run_3_stage                           \
 583               (1,                                               \
 584                vm,                                              \
 585                vhash_main_gather_keys_mod_stage_##N_KEY_U32,    \
 586                vhash_main_hash_finalize_mod_stage_##N_KEY_U32,  \
 587                vhash_main_set_mod_stage_##N_KEY_U32);           \
 588           else                                                  \
 589             clib_pipeline_run_3_stage                           \
 590               (1,                                               \
 591                vm,                                              \
 592                vhash_main_gather_keys_mod_stage_##N_KEY_U32,    \
 593                vhash_main_hash_finalize_mod_stage_##N_KEY_U32,  \
 594                vhash_main_unset_mod_stage_##N_KEY_U32);         \
 595         break;
 596
 597       _ (1);
 598       _ (2);
 599       _ (3);
 600
 601 #undef _
 602
 603 #define _(N_KEY_U32)                                            \
 604         case N_KEY_U32:                                         \
 605           if (op == GET)                                        \
 606             clib_pipeline_run_4_stage                           \
 607               (1,                                               \
 608                vm,                                              \
 609                vhash_main_gather_keys_mod_stage_##N_KEY_U32,    \
 610                vhash_main_hash_mix_mod_stage_##N_KEY_U32,       \
 611                vhash_main_hash_finalize_mod_stage_##N_KEY_U32,  \
 612                vhash_main_get_mod_stage_##N_KEY_U32);           \
 613           else if (op == SET)                                   \
 614             clib_pipeline_run_4_stage                           \
 615               (1,                                               \
 616                vm,                                              \
 617                vhash_main_gather_keys_mod_stage_##N_KEY_U32,    \
 618                vhash_main_hash_mix_mod_stage_##N_KEY_U32,       \
 619                vhash_main_hash_finalize_mod_stage_##N_KEY_U32,  \
 620                vhash_main_set_mod_stage_##N_KEY_U32);           \
 621           else                                                  \
 622             clib_pipeline_run_4_stage                           \
 623               (1,                                               \
 624                vm,                                              \
 625                vhash_main_gather_keys_mod_stage_##N_KEY_U32,    \
 626                vhash_main_hash_mix_mod_stage_##N_KEY_U32,       \
 627                vhash_main_hash_finalize_mod_stage_##N_KEY_U32,  \
 628                vhash_main_unset_mod_stage_##N_KEY_U32);         \
 629           break;
 630
 631               _ (4);
 632               _ (5);
 633               _ (6);
 634
 635 #undef _
 636         }
 637     }
 638 }
 639
 640 void vhash_main_get (vhash_main_t * vm)
 641 { vhash_main_op (vm, GET); }
 642
 643 void vhash_main_set (vhash_main_t * vm)
 644 { vhash_main_op (vm, SET); }
 645
 646 void vhash_main_unset (vhash_main_t * vm)
 647 { vhash_main_op (vm, UNSET); }
 648
 649 u32 vhash_resize_incremental (vhash_resize_t * vr, u32 vector_index, u32 n_keys_this_call)
 650 {
 651   vhash_t * old = vr->old;
 652   vhash_main_t * vm = &vr->new;
 653   vhash_t * new = vm->vhash;
 654   uword i, j, n_key_u32;
 655
 656   n_key_u32 = old->n_key_u32;
 657
 658   if (vector_index == 0)
 659     {
 660       u32 hash_seeds[3];
 661       hash_seeds[0] = old->hash_seeds[0].as_u32[0];
 662       hash_seeds[1] = old->hash_seeds[1].as_u32[0];
 663       hash_seeds[2] = old->hash_seeds[2].as_u32[0];
 664       vhash_init (new, old->log2_n_keys + 1, n_key_u32, hash_seeds);
 665     }
 666
 667   vec_reset_length (vm->keys);
 668   vec_reset_length (vm->results);
 669
 670   if (0 == (vector_index >> old->log2_n_keys))
 671     {
 672       for (i = vector_index; 0 == (i >> (old->log2_n_keys - 2)); i++)
 673         {
 674           vhash_search_bucket_t * b = vhash_get_search_bucket_with_index (old, 4 * i, n_key_u32);
 675           u32 r, * k;
 676
 677 #define _(I)                                    \
 678   if ((r = b->result.as_u32[I]) != 0)           \
 679     {                                           \
 680       vec_add1 (vm->results, r - 1);            \
 681       vec_add2 (vm->keys, k, n_key_u32);        \
 682       for (j = 0; j < n_key_u32; j++)           \
 683         k[j] = b->key[j].as_u32[I];             \
 684     }
 685
 686           _ (0);
 687           _ (1);
 688           _ (2);
 689           _ (3);
 690
 691 #undef _
 692
 693           if (vec_len (vm->results) >= n_keys_this_call)
 694             {
 695               vhash_main_op (vm, SET);
 696               return i;
 697             }
 698         }
 699     }
 700
 701   /* Add overflow buckets. */
 702   {
 703     vhash_overflow_buckets_t * ob;
 704     vhash_overflow_search_bucket_t * b;
 705
 706     for (ob = old->overflow_buckets;
 707          ob < old->overflow_buckets + ARRAY_LEN (old->overflow_buckets);
 708          ob++)
 709       {
 710         foreach_vhash_overflow_bucket (b, ob, old->n_key_u32)
 711           {
 712             u32 r, * k;
 713
 714 #define _(I)                                    \
 715   if ((r = b->result.as_u32[I]) != 0)           \
 716     {                                           \
 717       vec_add1 (vm->results, r - 1);            \
 718       vec_add2 (vm->keys, k, n_key_u32);        \
 719       for (j = 0; j < n_key_u32; j++)           \
 720         k[j] = b->key[j].as_u32[I];             \
 721     }
 722
 723           _ (0);
 724           _ (1);
 725           _ (2);
 726           _ (3);
 727
 728 #undef _
 729           }
 730       }
 731   }
 732
 733   vhash_main_op (vm, SET);
 734
 735   /* Let caller know we are done. */
 736   return ~0;
 737 }
 738
 739 void vhash_resize (vhash_t * old, u32 log2_n_keys)
 740 {
 741   static vhash_resize_t vr;
 742   vhash_t new;
 743   u32 i = 0;
 744
 745   vr.old = old;
 746   vr.new.vhash = &new;
 747
 748   while (1)
 749     {
 750       i = vhash_resize_incremental (&vr, i, 1024);
 751       if (i == ~0)
 752         break;
 753     }
 754
 755   vhash_free (old);
 756   *old = new;
 757 }
 758
 759 #endif /* CLIB_HAVE_VEC128 */