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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 Copyright (c) 2010 Eliot Dresselhaus
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:
26 The above copyright notice and this permission notice shall be
27 included in all copies or substantial portions of the Software.
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.
38 #include <vppinfra/vhash.h>
40 #ifdef CLIB_HAVE_VEC128
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. */
45 /* 4 results for this bucket. */
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;
52 /* n_key_u32s u32x4s of key data follow. */
54 } vhash_overflow_search_bucket_t;
57 set_overflow_result (vhash_overflow_search_bucket_t * b,
62 b->result.as_u32[i] = result;
63 b->key_hash.as_u32[i] = key_hash;
67 free_overflow_bucket (vhash_overflow_buckets_t * ob,
68 vhash_overflow_search_bucket_t * b,
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);
76 always_inline vhash_overflow_search_bucket_t *
77 get_overflow_search_bucket (vhash_overflow_buckets_t * obs, u32 i, u32 n_key_u32s)
79 return ((vhash_overflow_search_bucket_t *)
80 vec_elt_at_index (obs->search_buckets, i));
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]; }
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))
93 vhash_get_overflow (vhash_t * h,
98 vhash_overflow_buckets_t * ob = vhash_get_overflow_buckets (h, key_hash);
99 vhash_overflow_search_bucket_t * b;
102 foreach_vhash_overflow_bucket (b, ob, n_key_u32s)
104 u32x4 r = b->result.as_u32x4;
106 for (i = 0; i < n_key_u32s; i++)
107 r &= vhash_bucket_compare (h, &b->key[0], i, vi);
109 result = vhash_merge_results (r);
118 vhash_set_overflow (vhash_t * h,
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;
128 foreach_vhash_overflow_bucket (b, ob, n_key_u32s)
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);
136 old_result = vhash_merge_results (r);
139 i_set = vhash_non_empty_result_index (r);
140 set_overflow_result (b, i_set, new_result, key_hash);
145 /* Check free list. */
146 if (vec_len (ob->free_indices) == 0)
148 /* Out of free overflow buckets. Resize. */
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++)
159 i = vec_pop (ob->free_indices);
162 b = ((vhash_overflow_search_bucket_t *)
163 vec_elt_at_index (ob->search_buckets, i / 4));
166 set_overflow_result (b, i_set, new_result, key_hash);
169 for (i = 0; i < n_key_u32s; i++)
170 b->key[i].as_u32[i_set] = vhash_get_key_word (h, i, vi);
175 return /* old result was invalid */ 0;
179 vhash_unset_overflow (vhash_t * h,
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;
188 foreach_vhash_overflow_bucket (b, ob, n_key_u32s)
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);
196 old_result = vhash_merge_results (r);
199 i_set = vhash_non_empty_result_index (r);
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);
206 free_overflow_bucket (ob, b, i_set);
208 ASSERT (ob->n_overflow > 0);
215 /* Could not find key. */
220 vhash_unset_refill_from_overflow (vhash_t * h,
221 vhash_search_bucket_t * sb,
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];
229 /* Find overflow element with matching key hash. */
230 foreach_vhash_overflow_bucket (ob, obs, n_key_u32s)
232 for (i = 0; i < 4; i++)
234 if (! ob->result.as_u32[i])
236 if ((ob->key_hash.as_u32[i] & bucket_mask)
237 != (key_hash & bucket_mask))
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);
251 void vhash_init (vhash_t * h, u32 log2_n_keys, u32 n_key_u32, u32 * hash_seeds)
254 vhash_search_bucket_t * b;
256 memset (h, 0, sizeof (h[0]));
258 /* Must have at least 4 keys (e.g. one search bucket). */
259 log2_n_keys = clib_max (log2_n_keys, 2);
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;
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);
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));
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];
279 static_always_inline u32
280 vhash_main_key_gather (void * _vm, u32 vi, u32 wi, u32 n_key_u32)
282 vhash_main_t * vm = _vm;
283 return vec_elt (vm->keys, vi * n_key_u32 + wi);
286 static_always_inline u32x4
287 vhash_main_4key_gather (void * _vm, u32 vi, u32 wi, u32 n_key_u32s)
289 vhash_main_t * vm = _vm;
292 ASSERT (n_key_u32s == vm->n_key_u32);
293 ASSERT (wi < n_key_u32s);
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);
302 static_always_inline u32
303 vhash_main_set_result (void * _vm, u32 vi, u32 old_result, u32 n_key_u32)
305 vhash_main_t * vm = _vm;
306 u32 * p = vec_elt_at_index (vm->results, vi);
307 u32 new_result = p[0];
312 static_always_inline u32
313 vhash_main_get_result (void * _vm, u32 vi, u32 old_result, u32 n_key_u32)
315 vhash_main_t * vm = _vm;
316 vec_elt (vm->results, vi) = old_result;
320 static_always_inline u32x4
321 vhash_main_get_4result (void * _vm, u32 vi, u32x4 old_result, u32 n_key_u32)
323 vhash_main_t * vm = _vm;
324 u32x4 * p = (u32x4 *) vec_elt_at_index (vm->results, vi);
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); } \
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); } \
338 clib_pipeline_stage_static \
339 (vhash_main_gather_keys_stage_##N_KEY_U32, \
340 vhash_main_t *, vm, i, \
342 vhash_gather_4key_stage \
344 /* vector_index */ i, \
345 vhash_main_4key_gather_##N_KEY_U32, \
350 clib_pipeline_stage_no_inline \
351 (vhash_main_gather_keys_mod_stage_##N_KEY_U32, \
352 vhash_main_t *, vm, i, \
354 vhash_gather_key_stage \
356 /* vector_index */ vm->n_vectors_div_4, \
357 /* n_vectors */ vm->n_vectors_mod_4, \
358 vhash_main_key_gather_##N_KEY_U32, \
363 clib_pipeline_stage \
364 (vhash_main_hash_finalize_stage_##N_KEY_U32, \
365 vhash_main_t *, vm, i, \
367 vhash_finalize_stage (vm->vhash, i, N_KEY_U32); \
370 clib_pipeline_stage_no_inline \
371 (vhash_main_hash_finalize_mod_stage_##N_KEY_U32, \
372 vhash_main_t *, vm, i, \
374 vhash_finalize_stage (vm->vhash, vm->n_vectors_div_4, N_KEY_U32); \
377 clib_pipeline_stage_static \
378 (vhash_main_get_stage_##N_KEY_U32, \
379 vhash_main_t *, vm, i, \
381 vhash_get_4_stage (vm->vhash, \
382 /* vector_index */ i, \
383 vhash_main_get_4result, \
387 clib_pipeline_stage_no_inline \
388 (vhash_main_get_mod_stage_##N_KEY_U32, \
389 vhash_main_t *, vm, i, \
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, \
398 clib_pipeline_stage_static \
399 (vhash_main_set_stage_##N_KEY_U32, \
400 vhash_main_t *, vm, i, \
402 vhash_set_stage (vm->vhash, \
403 /* vector_index */ i, \
404 /* n_vectors */ VECTOR_WORD_TYPE_LEN (u32), \
405 vhash_main_set_result, \
409 clib_pipeline_stage_no_inline \
410 (vhash_main_set_mod_stage_##N_KEY_U32, \
411 vhash_main_t *, vm, i, \
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, \
420 clib_pipeline_stage_static \
421 (vhash_main_unset_stage_##N_KEY_U32, \
422 vhash_main_t *, vm, i, \
424 vhash_unset_stage (vm->vhash, \
425 /* vector_index */ i, \
426 /* n_vectors */ VECTOR_WORD_TYPE_LEN (u32), \
427 vhash_main_get_result, \
431 clib_pipeline_stage_no_inline \
432 (vhash_main_unset_mod_stage_##N_KEY_U32, \
433 vhash_main_t *, vm, i, \
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, \
451 #define _(N_KEY_U32) \
452 clib_pipeline_stage \
453 (vhash_main_hash_mix_stage_##N_KEY_U32, \
454 vhash_main_t *, vm, i, \
456 vhash_mix_stage (vm->vhash, i, N_KEY_U32); \
459 clib_pipeline_stage_no_inline \
460 (vhash_main_hash_mix_mod_stage_##N_KEY_U32, \
461 vhash_main_t *, vm, i, \
463 vhash_mix_stage (vm->vhash, vm->n_vectors_div_4, N_KEY_U32); \
477 vhash_main_op (vhash_main_t * vm, vhash_main_op_t op)
479 u32 n_keys = vec_len (vm->results);
481 vm->n_key_u32 = vm->vhash->n_key_u32;
483 vhash_validate_sizes (vm->vhash, vm->n_key_u32, n_keys);
485 vm->n_vectors_div_4 = n_keys / 4;
486 vm->n_vectors_mod_4 = n_keys % 4;
488 if (vm->n_vectors_div_4 > 0)
490 switch (vm->n_key_u32)
496 #define _(N_KEY_U32) \
499 clib_pipeline_run_3_stage \
500 (vm->n_vectors_div_4, \
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, \
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); \
513 clib_pipeline_run_3_stage \
514 (vm->n_vectors_div_4, \
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); \
527 #define _(N_KEY_U32) \
530 clib_pipeline_run_4_stage \
531 (vm->n_vectors_div_4, \
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, \
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); \
546 clib_pipeline_run_4_stage \
547 (vm->n_vectors_div_4, \
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); \
564 if (vm->n_vectors_mod_4 > 0)
566 switch (vm->n_key_u32)
572 #define _(N_KEY_U32) \
575 clib_pipeline_run_3_stage \
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 \
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); \
589 clib_pipeline_run_3_stage \
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); \
603 #define _(N_KEY_U32) \
606 clib_pipeline_run_4_stage \
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 \
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); \
622 clib_pipeline_run_4_stage \
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); \
640 void vhash_main_get (vhash_main_t * vm)
641 { vhash_main_op (vm, GET); }
643 void vhash_main_set (vhash_main_t * vm)
644 { vhash_main_op (vm, SET); }
646 void vhash_main_unset (vhash_main_t * vm)
647 { vhash_main_op (vm, UNSET); }
649 u32 vhash_resize_incremental (vhash_resize_t * vr, u32 vector_index, u32 n_keys_this_call)
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;
656 n_key_u32 = old->n_key_u32;
658 if (vector_index == 0)
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);
667 vec_reset_length (vm->keys);
668 vec_reset_length (vm->results);
670 if (0 == (vector_index >> old->log2_n_keys))
672 for (i = vector_index; 0 == (i >> (old->log2_n_keys - 2)); i++)
674 vhash_search_bucket_t * b = vhash_get_search_bucket_with_index (old, 4 * i, n_key_u32);
678 if ((r = b->result.as_u32[I]) != 0) \
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]; \
693 if (vec_len (vm->results) >= n_keys_this_call)
695 vhash_main_op (vm, SET);
701 /* Add overflow buckets. */
703 vhash_overflow_buckets_t * ob;
704 vhash_overflow_search_bucket_t * b;
706 for (ob = old->overflow_buckets;
707 ob < old->overflow_buckets + ARRAY_LEN (old->overflow_buckets);
710 foreach_vhash_overflow_bucket (b, ob, old->n_key_u32)
715 if ((r = b->result.as_u32[I]) != 0) \
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]; \
733 vhash_main_op (vm, SET);
735 /* Let caller know we are done. */
739 void vhash_resize (vhash_t * old, u32 log2_n_keys)
741 static vhash_resize_t vr;
750 i = vhash_resize_incremental (&vr, i, 1024);
759 #endif /* CLIB_HAVE_VEC128 */