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. */
46 /* 4 results for this bucket. */
49 /* 4 hash codes for this bucket. These are used to refill main
50 search buckets from overflow buckets when space becomes available. */
51 u32x4_union_t key_hash;
53 /* n_key_u32s u32x4s of key data follow. */
55 } vhash_overflow_search_bucket_t;
58 set_overflow_result (vhash_overflow_search_bucket_t * b,
59 u32 i, u32 result, u32 key_hash)
61 b->result.as_u32[i] = result;
62 b->key_hash.as_u32[i] = key_hash;
66 free_overflow_bucket (vhash_overflow_buckets_t * ob,
67 vhash_overflow_search_bucket_t * b, u32 i)
69 u32 o = (u32x4_union_t *) b - ob->search_buckets;
70 ASSERT (o < vec_len (ob->search_buckets));
71 vec_add1 (ob->free_indices, 4 * o + i);
74 always_inline vhash_overflow_search_bucket_t *
75 get_overflow_search_bucket (vhash_overflow_buckets_t * obs, u32 i,
78 return ((vhash_overflow_search_bucket_t *)
79 vec_elt_at_index (obs->search_buckets, i));
82 always_inline vhash_overflow_search_bucket_t *
83 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];
88 #define foreach_vhash_overflow_bucket(b,ob,n_key_u32s) \
89 for ((b) = (vhash_overflow_search_bucket_t *) ob->search_buckets; \
90 (u32x4_union_t *) (b) < vec_end (ob->search_buckets); \
91 b = next_overflow_bucket (b, n_key_u32s))
94 vhash_get_overflow (vhash_t * h, u32 key_hash, u32 vi, u32 n_key_u32s)
96 vhash_overflow_buckets_t *ob = vhash_get_overflow_buckets (h, key_hash);
97 vhash_overflow_search_bucket_t *b;
100 foreach_vhash_overflow_bucket (b, ob, n_key_u32s)
102 u32x4 r = b->result.as_u32x4;
104 for (i = 0; i < n_key_u32s; i++)
105 r &= vhash_bucket_compare (h, &b->key[0], i, vi);
107 result = vhash_merge_results (r);
116 vhash_set_overflow (vhash_t * h,
117 u32 key_hash, u32 vi, u32 new_result, u32 n_key_u32s)
119 vhash_overflow_buckets_t *ob = vhash_get_overflow_buckets (h, key_hash);
120 vhash_overflow_search_bucket_t *b;
121 u32 i_set, i, old_result;
123 foreach_vhash_overflow_bucket (b, ob, n_key_u32s)
127 r = b->result.as_u32x4;
128 for (i = 0; i < n_key_u32s; i++)
129 r &= vhash_bucket_compare (h, &b->key[0], i, vi);
131 old_result = vhash_merge_results (r);
134 i_set = vhash_non_empty_result_index (r);
135 set_overflow_result (b, i_set, new_result, key_hash);
140 /* Check free list. */
141 if (vec_len (ob->free_indices) == 0)
143 /* Out of free overflow buckets. Resize. */
145 i = vec_len (ob->search_buckets);
146 vec_resize_aligned (ob->search_buckets,
147 sizeof (b[0]) / sizeof (u32x4) + n_key_u32s,
148 CLIB_CACHE_LINE_BYTES);
149 vec_add2 (ob->free_indices, p, 4);
150 for (j = 0; j < 4; j++)
154 i = vec_pop (ob->free_indices);
157 b = ((vhash_overflow_search_bucket_t *)
158 vec_elt_at_index (ob->search_buckets, i / 4));
161 set_overflow_result (b, i_set, new_result, key_hash);
164 for (i = 0; i < n_key_u32s; i++)
165 b->key[i].as_u32[i_set] = vhash_get_key_word (h, i, vi);
170 return /* old result was invalid */ 0;
174 vhash_unset_overflow (vhash_t * h, u32 key_hash, u32 vi, u32 n_key_u32s)
176 vhash_overflow_buckets_t *ob = vhash_get_overflow_buckets (h, key_hash);
177 vhash_overflow_search_bucket_t *b;
178 u32 i_set, i, old_result;
180 foreach_vhash_overflow_bucket (b, ob, n_key_u32s)
184 r = b->result.as_u32x4;
185 for (i = 0; i < n_key_u32s; i++)
186 r &= vhash_bucket_compare (h, &b->key[0], i, vi);
188 old_result = vhash_merge_results (r);
191 i_set = vhash_non_empty_result_index (r);
193 /* Invalidate result and invert key hash so that this will
194 never match since all keys in this overflow bucket have
195 matching key hashs. */
196 set_overflow_result (b, i_set, 0, ~key_hash);
198 free_overflow_bucket (ob, b, i_set);
200 ASSERT (ob->n_overflow > 0);
207 /* Could not find key. */
212 vhash_unset_refill_from_overflow (vhash_t * h,
213 vhash_search_bucket_t * sb,
214 u32 key_hash, u32 n_key_u32s)
216 vhash_overflow_buckets_t *obs = vhash_get_overflow_buckets (h, key_hash);
217 vhash_overflow_search_bucket_t *ob;
218 u32 i, j, i_refill, bucket_mask = h->bucket_mask.as_u32[0];
220 /* Find overflow element with matching key hash. */
221 foreach_vhash_overflow_bucket (ob, obs, n_key_u32s)
223 for (i = 0; i < 4; i++)
225 if (!ob->result.as_u32[i])
227 if ((ob->key_hash.as_u32[i] & bucket_mask)
228 != (key_hash & bucket_mask))
231 i_refill = vhash_empty_result_index (sb->result.as_u32x4);
232 sb->result.as_u32[i_refill] = ob->result.as_u32[i];
233 for (j = 0; j < n_key_u32s; j++)
234 sb->key[j].as_u32[i_refill] = ob->key[j].as_u32[i];
235 set_overflow_result (ob, i, 0, ~key_hash);
236 free_overflow_bucket (obs, ob, i);
243 vhash_init (vhash_t * h, u32 log2_n_keys, u32 n_key_u32, u32 * hash_seeds)
246 vhash_search_bucket_t *b;
248 memset (h, 0, sizeof (h[0]));
250 /* Must have at least 4 keys (e.g. one search bucket). */
251 log2_n_keys = clib_max (log2_n_keys, 2);
253 h->log2_n_keys = log2_n_keys;
254 h->n_key_u32 = n_key_u32;
255 m = pow2_mask (h->log2_n_keys) & ~3;
256 for (i = 0; i < VECTOR_WORD_TYPE_LEN (u32); i++)
257 h->bucket_mask.as_u32[i] = m;
259 /* Allocate and zero search buckets. */
260 i = (sizeof (b[0]) / sizeof (u32x4) + n_key_u32) << (log2_n_keys - 2);
261 vec_validate_aligned (h->search_buckets, i - 1, CLIB_CACHE_LINE_BYTES);
263 for (i = 0; i < ARRAY_LEN (h->find_first_zero_table); i++)
264 h->find_first_zero_table[i] = min_log2 (first_set (~i));
266 for (i = 0; i < ARRAY_LEN (h->hash_seeds); i++)
267 for (j = 0; j < VECTOR_WORD_TYPE_LEN (u32); j++)
268 h->hash_seeds[i].as_u32[j] = hash_seeds[i];
271 static_always_inline u32
272 vhash_main_key_gather (void *_vm, u32 vi, u32 wi, u32 n_key_u32)
274 vhash_main_t *vm = _vm;
275 return vec_elt (vm->keys, vi * n_key_u32 + wi);
278 static_always_inline u32x4
279 vhash_main_4key_gather (void *_vm, u32 vi, u32 wi, u32 n_key_u32s)
281 vhash_main_t *vm = _vm;
284 ASSERT (n_key_u32s == vm->n_key_u32);
285 ASSERT (wi < n_key_u32s);
287 x.as_u32[0] = vec_elt (vm->keys, (vi + 0) * n_key_u32s + wi);
288 x.as_u32[1] = vec_elt (vm->keys, (vi + 1) * n_key_u32s + wi);
289 x.as_u32[2] = vec_elt (vm->keys, (vi + 2) * n_key_u32s + wi);
290 x.as_u32[3] = vec_elt (vm->keys, (vi + 3) * n_key_u32s + wi);
294 static_always_inline u32
295 vhash_main_set_result (void *_vm, u32 vi, u32 old_result, u32 n_key_u32)
297 vhash_main_t *vm = _vm;
298 u32 *p = vec_elt_at_index (vm->results, vi);
299 u32 new_result = p[0];
304 static_always_inline u32
305 vhash_main_get_result (void *_vm, u32 vi, u32 old_result, u32 n_key_u32)
307 vhash_main_t *vm = _vm;
308 vec_elt (vm->results, vi) = old_result;
312 static_always_inline u32x4
313 vhash_main_get_4result (void *_vm, u32 vi, u32x4 old_result, u32 n_key_u32)
315 vhash_main_t *vm = _vm;
316 u32x4 *p = (u32x4 *) vec_elt_at_index (vm->results, vi);
321 #define _(N_KEY_U32) \
322 static_always_inline u32 \
323 vhash_main_key_gather_##N_KEY_U32 (void * _vm, u32 vi, u32 i) \
324 { return vhash_main_key_gather (_vm, vi, i, N_KEY_U32); } \
326 static_always_inline u32x4 \
327 vhash_main_4key_gather_##N_KEY_U32 (void * _vm, u32 vi, u32 i) \
328 { return vhash_main_4key_gather (_vm, vi, i, N_KEY_U32); } \
330 clib_pipeline_stage_static \
331 (vhash_main_gather_keys_stage_##N_KEY_U32, \
332 vhash_main_t *, vm, i, \
334 vhash_gather_4key_stage \
336 /* vector_index */ i, \
337 vhash_main_4key_gather_##N_KEY_U32, \
342 clib_pipeline_stage_no_inline \
343 (vhash_main_gather_keys_mod_stage_##N_KEY_U32, \
344 vhash_main_t *, vm, i, \
346 vhash_gather_key_stage \
348 /* vector_index */ vm->n_vectors_div_4, \
349 /* n_vectors */ vm->n_vectors_mod_4, \
350 vhash_main_key_gather_##N_KEY_U32, \
355 clib_pipeline_stage \
356 (vhash_main_hash_finalize_stage_##N_KEY_U32, \
357 vhash_main_t *, vm, i, \
359 vhash_finalize_stage (vm->vhash, i, N_KEY_U32); \
362 clib_pipeline_stage_no_inline \
363 (vhash_main_hash_finalize_mod_stage_##N_KEY_U32, \
364 vhash_main_t *, vm, i, \
366 vhash_finalize_stage (vm->vhash, vm->n_vectors_div_4, N_KEY_U32); \
369 clib_pipeline_stage_static \
370 (vhash_main_get_stage_##N_KEY_U32, \
371 vhash_main_t *, vm, i, \
373 vhash_get_4_stage (vm->vhash, \
374 /* vector_index */ i, \
375 vhash_main_get_4result, \
379 clib_pipeline_stage_no_inline \
380 (vhash_main_get_mod_stage_##N_KEY_U32, \
381 vhash_main_t *, vm, i, \
383 vhash_get_stage (vm->vhash, \
384 /* vector_index */ vm->n_vectors_div_4, \
385 /* n_vectors */ vm->n_vectors_mod_4, \
386 vhash_main_get_result, \
390 clib_pipeline_stage_static \
391 (vhash_main_set_stage_##N_KEY_U32, \
392 vhash_main_t *, vm, i, \
394 vhash_set_stage (vm->vhash, \
395 /* vector_index */ i, \
396 /* n_vectors */ VECTOR_WORD_TYPE_LEN (u32), \
397 vhash_main_set_result, \
401 clib_pipeline_stage_no_inline \
402 (vhash_main_set_mod_stage_##N_KEY_U32, \
403 vhash_main_t *, vm, i, \
405 vhash_set_stage (vm->vhash, \
406 /* vector_index */ vm->n_vectors_div_4, \
407 /* n_vectors */ vm->n_vectors_mod_4, \
408 vhash_main_set_result, \
412 clib_pipeline_stage_static \
413 (vhash_main_unset_stage_##N_KEY_U32, \
414 vhash_main_t *, vm, i, \
416 vhash_unset_stage (vm->vhash, \
417 /* vector_index */ i, \
418 /* n_vectors */ VECTOR_WORD_TYPE_LEN (u32), \
419 vhash_main_get_result, \
423 clib_pipeline_stage_no_inline \
424 (vhash_main_unset_mod_stage_##N_KEY_U32, \
425 vhash_main_t *, vm, i, \
427 vhash_unset_stage (vm->vhash, \
428 /* vector_index */ vm->n_vectors_div_4, \
429 /* n_vectors */ vm->n_vectors_mod_4, \
430 vhash_main_get_result, \
443 #define _(N_KEY_U32) \
444 clib_pipeline_stage \
445 (vhash_main_hash_mix_stage_##N_KEY_U32, \
446 vhash_main_t *, vm, i, \
448 vhash_mix_stage (vm->vhash, i, N_KEY_U32); \
451 clib_pipeline_stage_no_inline \
452 (vhash_main_hash_mix_mod_stage_##N_KEY_U32, \
453 vhash_main_t *, vm, i, \
455 vhash_mix_stage (vm->vhash, vm->n_vectors_div_4, N_KEY_U32); \
470 vhash_main_op (vhash_main_t * vm, vhash_main_op_t op)
472 u32 n_keys = vec_len (vm->results);
474 vm->n_key_u32 = vm->vhash->n_key_u32;
476 vhash_validate_sizes (vm->vhash, vm->n_key_u32, n_keys);
478 vm->n_vectors_div_4 = n_keys / 4;
479 vm->n_vectors_mod_4 = n_keys % 4;
481 if (vm->n_vectors_div_4 > 0)
483 switch (vm->n_key_u32)
489 #define _(N_KEY_U32) \
492 clib_pipeline_run_3_stage \
493 (vm->n_vectors_div_4, \
495 vhash_main_gather_keys_stage_##N_KEY_U32, \
496 vhash_main_hash_finalize_stage_##N_KEY_U32, \
497 vhash_main_get_stage_##N_KEY_U32); \
498 else if (op == SET) \
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_set_stage_##N_KEY_U32); \
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_unset_stage_##N_KEY_U32); \
520 #define _(N_KEY_U32) \
523 clib_pipeline_run_4_stage \
524 (vm->n_vectors_div_4, \
526 vhash_main_gather_keys_stage_##N_KEY_U32, \
527 vhash_main_hash_mix_stage_##N_KEY_U32, \
528 vhash_main_hash_finalize_stage_##N_KEY_U32, \
529 vhash_main_get_stage_##N_KEY_U32); \
530 else if (op == SET) \
531 clib_pipeline_run_4_stage \
532 (vm->n_vectors_div_4, \
534 vhash_main_gather_keys_stage_##N_KEY_U32, \
535 vhash_main_hash_mix_stage_##N_KEY_U32, \
536 vhash_main_hash_finalize_stage_##N_KEY_U32, \
537 vhash_main_set_stage_##N_KEY_U32); \
539 clib_pipeline_run_4_stage \
540 (vm->n_vectors_div_4, \
542 vhash_main_gather_keys_stage_##N_KEY_U32, \
543 vhash_main_hash_mix_stage_##N_KEY_U32, \
544 vhash_main_hash_finalize_stage_##N_KEY_U32, \
545 vhash_main_unset_stage_##N_KEY_U32); \
557 if (vm->n_vectors_mod_4 > 0)
559 switch (vm->n_key_u32)
565 #define _(N_KEY_U32) \
568 clib_pipeline_run_3_stage \
571 vhash_main_gather_keys_mod_stage_##N_KEY_U32, \
572 vhash_main_hash_finalize_mod_stage_##N_KEY_U32, \
573 vhash_main_get_mod_stage_##N_KEY_U32); \
574 else if (op == SET) \
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_set_mod_stage_##N_KEY_U32); \
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_unset_mod_stage_##N_KEY_U32); \
596 #define _(N_KEY_U32) \
599 clib_pipeline_run_4_stage \
602 vhash_main_gather_keys_mod_stage_##N_KEY_U32, \
603 vhash_main_hash_mix_mod_stage_##N_KEY_U32, \
604 vhash_main_hash_finalize_mod_stage_##N_KEY_U32, \
605 vhash_main_get_mod_stage_##N_KEY_U32); \
606 else if (op == SET) \
607 clib_pipeline_run_4_stage \
610 vhash_main_gather_keys_mod_stage_##N_KEY_U32, \
611 vhash_main_hash_mix_mod_stage_##N_KEY_U32, \
612 vhash_main_hash_finalize_mod_stage_##N_KEY_U32, \
613 vhash_main_set_mod_stage_##N_KEY_U32); \
615 clib_pipeline_run_4_stage \
618 vhash_main_gather_keys_mod_stage_##N_KEY_U32, \
619 vhash_main_hash_mix_mod_stage_##N_KEY_U32, \
620 vhash_main_hash_finalize_mod_stage_##N_KEY_U32, \
621 vhash_main_unset_mod_stage_##N_KEY_U32); \
634 vhash_main_get (vhash_main_t * vm)
636 vhash_main_op (vm, GET);
640 vhash_main_set (vhash_main_t * vm)
642 vhash_main_op (vm, SET);
646 vhash_main_unset (vhash_main_t * vm)
648 vhash_main_op (vm, UNSET);
652 vhash_resize_incremental (vhash_resize_t * vr, u32 vector_index,
653 u32 n_keys_this_call)
655 vhash_t *old = vr->old;
656 vhash_main_t *vm = &vr->new;
657 vhash_t *new = vm->vhash;
658 uword i, j, n_key_u32;
660 n_key_u32 = old->n_key_u32;
662 if (vector_index == 0)
665 hash_seeds[0] = old->hash_seeds[0].as_u32[0];
666 hash_seeds[1] = old->hash_seeds[1].as_u32[0];
667 hash_seeds[2] = old->hash_seeds[2].as_u32[0];
668 vhash_init (new, old->log2_n_keys + 1, n_key_u32, hash_seeds);
671 vec_reset_length (vm->keys);
672 vec_reset_length (vm->results);
674 if (0 == (vector_index >> old->log2_n_keys))
676 for (i = vector_index; 0 == (i >> (old->log2_n_keys - 2)); i++)
678 vhash_search_bucket_t *b =
679 vhash_get_search_bucket_with_index (old, 4 * i, n_key_u32);
683 if ((r = b->result.as_u32[I]) != 0) \
685 vec_add1 (vm->results, r - 1); \
686 vec_add2 (vm->keys, k, n_key_u32); \
687 for (j = 0; j < n_key_u32; j++) \
688 k[j] = b->key[j].as_u32[I]; \
698 if (vec_len (vm->results) >= n_keys_this_call)
700 vhash_main_op (vm, SET);
706 /* Add overflow buckets. */
708 vhash_overflow_buckets_t *ob;
709 vhash_overflow_search_bucket_t *b;
711 for (ob = old->overflow_buckets;
712 ob < old->overflow_buckets + ARRAY_LEN (old->overflow_buckets); ob++)
714 foreach_vhash_overflow_bucket (b, ob, old->n_key_u32)
719 if ((r = b->result.as_u32[I]) != 0) \
721 vec_add1 (vm->results, r - 1); \
722 vec_add2 (vm->keys, k, n_key_u32); \
723 for (j = 0; j < n_key_u32; j++) \
724 k[j] = b->key[j].as_u32[I]; \
737 vhash_main_op (vm, SET);
739 /* Let caller know we are done. */
744 vhash_resize (vhash_t * old, u32 log2_n_keys)
746 static vhash_resize_t vr;
755 i = vhash_resize_incremental (&vr, i, 1024);
764 #endif /* CLIB_HAVE_VEC128 */
767 * fd.io coding-style-patch-verification: ON
770 * eval: (c-set-style "gnu")