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) 2006 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/qhash.h>
40 #define QHASH_ALL_VALID ((1 << QHASH_KEYS_PER_BUCKET) - 1)
43 _qhash_resize (void * v, uword length, uword elt_bytes)
48 l = clib_max (max_log2 (length), 2 + QHASH_LOG2_KEYS_PER_BUCKET);
50 /* Round up if less than 1/2 full. */
51 l += ((f64) length / (f64) (1 << l)) < .5;
53 v = _vec_resize (0, 1 << l,
56 /* align */ sizeof (uword));
60 h->log2_hash_size = l;
61 h->hash_keys = clib_mem_alloc_aligned_no_fail (sizeof (h->hash_keys[0]) << l,
62 CLIB_CACHE_LINE_BYTES);
63 vec_resize (h->hash_key_valid_bitmap,
64 1 << (l - QHASH_LOG2_KEYS_PER_BUCKET));
65 memset (v, ~0, elt_bytes << l);
70 static u8 min_log2_table[256];
73 qhash_min_log2 (uword x)
77 return min_log2_table[x];
80 static void qhash_min_log2_init ()
83 for (i = 0; i < 256; i++)
84 min_log2_table[i] = min_log2 (i);
88 qhash_get_valid_elt_mask (qhash_t * h, uword i)
89 { return h->hash_key_valid_bitmap[i / QHASH_KEYS_PER_BUCKET]; }
92 qhash_set_valid_elt_mask (qhash_t * h, uword i, uword mask)
93 { h->hash_key_valid_bitmap[i / QHASH_KEYS_PER_BUCKET] = mask; }
96 qhash_search_bucket (uword * hash_keys, uword search_key,
100 #define _(i) ((hash_keys[i] == search_key) << i)
101 t = (_ (0) | _ (1) | _ (2) | _ (3));
102 if (QHASH_KEYS_PER_BUCKET > 4)
103 t |= (_ (4) | _ (5) | _ (6) | _ (7));
104 if (QHASH_KEYS_PER_BUCKET > 8)
105 t |= (_ (8) | _ (9) | _ (10) | _ (11)
106 | _ (12) | _ (13) | _ (14) | _ (15));
111 /* Lookup multiple keys in the same hash table. */
113 qhash_get_multiple (void * v,
116 u32 * result_indices)
118 qhash_t * h = qhash_header (v);
119 uword * k, * hash_keys;
120 uword n_left, bucket_mask;
125 memset (result_indices, ~0, sizeof (result_indices[0]) * n_search_keys);
129 bucket_mask = pow2_mask (h->log2_hash_size) &~ (QHASH_KEYS_PER_BUCKET - 1);
132 n_left = n_search_keys;
133 hash_keys = h->hash_keys;
138 u32 a0, b0, c0, bi0, valid0, match0;
139 u32 a1, b1, c1, bi1, valid1, match1;
140 uword k0, k1, * h0, * h1;
147 a0 = a1 = h->hash_seeds[0];
148 b0 = b1 = h->hash_seeds[1];
149 c0 = c1 = h->hash_seeds[2];
157 hash_mix32_step_1 (a0, b0, c0);
158 hash_mix32_step_1 (a1, b1, c1);
159 hash_mix32_step_2 (a0, b0, c0);
160 hash_mix32_step_2 (a1, b1, c1);
161 hash_mix32_step_3 (a0, b0, c0);
162 hash_mix32_step_3 (a1, b1, c1);
164 bi0 = c0 & bucket_mask;
165 bi1 = c1 & bucket_mask;
167 h0 = hash_keys + bi0;
168 h1 = hash_keys + bi1;
170 /* Search two buckets. */
171 valid0 = qhash_get_valid_elt_mask (h, bi0);
172 valid1 = qhash_get_valid_elt_mask (h, bi1);
174 match0 = qhash_search_bucket (h0, k0, valid0);
175 match1 = qhash_search_bucket (h1, k1, valid1);
177 bi0 += qhash_min_log2 (match0);
178 bi1 += qhash_min_log2 (match1);
180 r[0] = match0 ? bi0 : ~0;
181 r[1] = match1 ? bi1 : ~0;
184 /* Full buckets trigger search of overflow hash. */
185 if (PREDICT_FALSE (! match0 && valid0 == QHASH_ALL_VALID))
187 uword * p = hash_get (h->overflow_hash, k0);
188 r[-2] = p ? p[0] : ~0;
191 /* Full buckets trigger search of overflow hash. */
192 if (PREDICT_FALSE (! match1 && valid1 == QHASH_ALL_VALID))
194 uword * p = hash_get (h->overflow_hash, k1);
195 r[-1] = p ? p[0] : ~0;
201 u32 a0, b0, c0, bi0, valid0, match0;
208 a0 = h->hash_seeds[0];
209 b0 = h->hash_seeds[1];
210 c0 = h->hash_seeds[2];
216 hash_mix32 (a0, b0, c0);
218 bi0 = c0 & bucket_mask;
220 h0 = hash_keys + bi0;
222 /* Search one bucket. */
223 valid0 = qhash_get_valid_elt_mask (h, bi0);
224 match0 = qhash_search_bucket (h0, k0, valid0);
226 bi0 += qhash_min_log2 (match0);
228 r[0] = match0 ? bi0 : ~0;
231 /* Full buckets trigger search of overflow hash. */
232 if (PREDICT_FALSE (! match0 && valid0 == QHASH_ALL_VALID))
234 uword * p = hash_get (h->overflow_hash, k0);
235 r[-1] = p ? p[0] : ~0;
240 /* Lookup multiple keys in the same hash table.
241 Returns index of first matching key. */
243 qhash_get_first_match (void * v,
246 uword * matching_key)
248 qhash_t * h = qhash_header (v);
249 uword * k, * hash_keys;
250 uword n_left, match_mask, bucket_mask;
256 bucket_mask = pow2_mask (h->log2_hash_size) &~ (QHASH_KEYS_PER_BUCKET - 1);
259 n_left = n_search_keys;
260 hash_keys = h->hash_keys;
263 u32 a0, b0, c0, bi0, valid0;
264 u32 a1, b1, c1, bi1, valid1;
265 uword k0, k1, * h0, * h1;
272 a0 = a1 = h->hash_seeds[0];
273 b0 = b1 = h->hash_seeds[1];
274 c0 = c1 = h->hash_seeds[2];
282 hash_mix32_step_1 (a0, b0, c0);
283 hash_mix32_step_1 (a1, b1, c1);
284 hash_mix32_step_2 (a0, b0, c0);
285 hash_mix32_step_2 (a1, b1, c1);
286 hash_mix32_step_3 (a0, b0, c0);
287 hash_mix32_step_3 (a1, b1, c1);
289 bi0 = c0 & bucket_mask;
290 bi1 = c1 & bucket_mask;
292 h0 = hash_keys + bi0;
293 h1 = hash_keys + bi1;
295 /* Search two buckets. */
296 valid0 = qhash_get_valid_elt_mask (h, bi0);
297 valid1 = qhash_get_valid_elt_mask (h, bi1);
298 match_mask = qhash_search_bucket (h0, k0, valid0);
299 match_mask |= (qhash_search_bucket (h1, k1, valid1)
300 << QHASH_KEYS_PER_BUCKET);
305 bi = qhash_min_log2 (match_mask);
306 is_match1 = bi >= QHASH_KEYS_PER_BUCKET;
308 bi += ((is_match1 ? bi1 : bi0)
309 - (is_match1 << QHASH_LOG2_KEYS_PER_BUCKET));
310 *matching_key = (k - 2 - search_keys) + is_match1;
314 /* Full buckets trigger search of overflow hash. */
315 if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID
316 || valid1 == QHASH_ALL_VALID))
319 uword ki = k - 2 - search_keys;
321 if (valid0 == QHASH_ALL_VALID)
322 p = hash_get (h->overflow_hash, k0);
324 if (! p && valid1 == QHASH_ALL_VALID)
326 p = hash_get (h->overflow_hash, k1);
340 u32 a0, b0, c0, bi0, valid0;
347 a0 = h->hash_seeds[0];
348 b0 = h->hash_seeds[1];
349 c0 = h->hash_seeds[2];
355 hash_mix32 (a0, b0, c0);
357 bi0 = c0 & bucket_mask;
359 h0 = hash_keys + bi0;
361 /* Search one bucket. */
362 valid0 = qhash_get_valid_elt_mask (h, bi0);
363 match_mask = qhash_search_bucket (h0, k0, valid0);
367 bi = bi0 + qhash_min_log2 (match_mask);
368 *matching_key = (k - 1 - search_keys);
372 /* Full buckets trigger search of overflow hash. */
373 if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID))
375 uword * p = hash_get (h->overflow_hash, k0);
378 *matching_key = (k - 1 - search_keys);
388 qhash_set_overflow (void * v, uword elt_bytes,
393 qhash_t * h = qhash_header (v);
394 uword * p = hash_get (h->overflow_hash, key);
397 bi /= QHASH_KEYS_PER_BUCKET;
403 uword l = vec_len (h->overflow_free_indices);
406 i = h->overflow_free_indices[l - 1];
407 _vec_len (h->overflow_free_indices) = l - 1;
410 i = (1 << h->log2_hash_size) + hash_elts (h->overflow_hash);
411 hash_set (h->overflow_hash, key, i);
412 vec_validate (h->overflow_counts, bi);
413 h->overflow_counts[bi] += 1;
419 uword dl = round_pow2 (1 + i - l, 8);
420 v = _vec_resize (v, dl,
421 (l + dl) * elt_bytes,
423 /* align */ sizeof (uword));
424 memset (v + l*elt_bytes, ~0, dl * elt_bytes);
434 qhash_unset_overflow (void * v, uword key, uword bi, uword * n_elts)
436 qhash_t * h = qhash_header (v);
437 uword * p = hash_get (h->overflow_hash, key);
440 bi /= QHASH_KEYS_PER_BUCKET;
445 hash_unset (h->overflow_hash, key);
446 ASSERT (bi < vec_len (h->overflow_counts));
447 ASSERT (h->overflow_counts[bi] > 0);
448 ASSERT (*n_elts > 0);
449 vec_add1 (h->overflow_free_indices, result);
450 h->overflow_counts[bi] -= 1;
460 qhash_find_free (uword i, uword valid_mask)
461 { return first_set (~valid_mask & pow2_mask (QHASH_KEYS_PER_BUCKET)); }
464 _qhash_set_multiple (void * v,
468 u32 * result_indices)
470 qhash_t * h = qhash_header (v);
471 uword * k, * hash_keys;
472 uword n_left, n_elts, bucket_mask;
475 if (vec_len (v) < n_search_keys)
476 v = _qhash_resize (v, n_search_keys, elt_bytes);
478 if (qhash_min_log2 (2) != 1)
480 qhash_min_log2_init ();
481 ASSERT (qhash_min_log2 (2) == 1);
486 bucket_mask = pow2_mask (h->log2_hash_size) &~ (QHASH_KEYS_PER_BUCKET - 1);
488 hash_keys = h->hash_keys;
491 n_left = n_search_keys;
496 u32 a0, b0, c0, bi0, match0, valid0, free0;
497 u32 a1, b1, c1, bi1, match1, valid1, free1;
504 /* Keys must be unique. */
510 a0 = a1 = h->hash_seeds[0];
511 b0 = b1 = h->hash_seeds[1];
512 c0 = c1 = h->hash_seeds[2];
520 hash_mix32_step_1 (a0, b0, c0);
521 hash_mix32_step_1 (a1, b1, c1);
522 hash_mix32_step_2 (a0, b0, c0);
523 hash_mix32_step_2 (a1, b1, c1);
524 hash_mix32_step_3 (a0, b0, c0);
525 hash_mix32_step_3 (a1, b1, c1);
527 bi0 = c0 & bucket_mask;
528 bi1 = c1 & bucket_mask;
530 h0 = hash_keys + bi0;
531 h1 = hash_keys + bi1;
533 /* Search two buckets. */
534 valid0 = qhash_get_valid_elt_mask (h, bi0);
535 valid1 = qhash_get_valid_elt_mask (h, bi1);
537 match0 = qhash_search_bucket (h0, k0, valid0);
538 match1 = qhash_search_bucket (h1, k1, valid1);
540 /* Find first free element starting at hash offset into bucket. */
541 free0 = qhash_find_free (c0 & (QHASH_KEYS_PER_BUCKET - 1), valid0);
543 valid1 = valid1 | (bi0 == bi1 ? free0 : 0);
544 free1 = qhash_find_free (c1 & (QHASH_KEYS_PER_BUCKET - 1), valid1);
546 n_elts += (match0 == 0) + (match1 == 0);
548 match0 = match0 ? match0 : free0;
549 match1 = match1 ? match1 : free1;
554 h0 += qhash_min_log2 (match0);
555 h1 += qhash_min_log2 (match1);
557 if (PREDICT_FALSE (! match0 || ! match1))
562 r[0] = h0 - hash_keys;
563 r[1] = h1 - hash_keys;
565 qhash_set_valid_elt_mask (h, bi0, valid0);
566 qhash_set_valid_elt_mask (h, bi1, valid1);
573 v = qhash_set_overflow (v, elt_bytes, k0, bi0, &n_elts, &r[0]);
578 r[0] = h0 - hash_keys;
579 qhash_set_valid_elt_mask (h, bi0, valid0);
584 v = qhash_set_overflow (v, elt_bytes, k1, bi1, &n_elts, &r[1]);
589 r[1] = h1 - hash_keys;
590 qhash_set_valid_elt_mask (h, bi1, valid1);
597 u32 a0, b0, c0, bi0, match0, valid0, free0;
604 a0 = h->hash_seeds[0];
605 b0 = h->hash_seeds[1];
606 c0 = h->hash_seeds[2];
612 hash_mix32 (a0, b0, c0);
614 bi0 = c0 & bucket_mask;
616 h0 = hash_keys + bi0;
618 valid0 = qhash_get_valid_elt_mask (h, bi0);
620 /* Find first free element starting at hash offset into bucket. */
621 free0 = qhash_find_free (c0 & (QHASH_KEYS_PER_BUCKET - 1), valid0);
623 match0 = qhash_search_bucket (h0, k0, valid0);
625 n_elts += (match0 == 0);
627 match0 = match0 ? match0 : free0;
631 h0 += qhash_min_log2 (match0);
633 if (PREDICT_FALSE (! match0))
637 r[0] = h0 - hash_keys;
639 qhash_set_valid_elt_mask (h, bi0, valid0);
644 v = qhash_set_overflow (v, elt_bytes, k0, bi0, &n_elts, &r[0]);
648 h = qhash_header (v);
655 unset_slow_path (void * v, uword elt_bytes,
656 uword k0, uword bi0, uword valid0, uword match0,
659 qhash_t * h = qhash_header (v);
660 uword i, j = 0, k, l, t = ~0;
661 hash_pair_t * p, * found;
665 if (valid0 == QHASH_ALL_VALID)
666 t = qhash_unset_overflow (v, k0, bi0, n_elts);
670 i = bi0 / QHASH_KEYS_PER_BUCKET;
671 t = bi0 + qhash_min_log2 (match0);
673 if (valid0 == QHASH_ALL_VALID
674 && i < vec_len (h->overflow_counts)
675 && h->overflow_counts[i] > 0)
678 hash_foreach_pair (p, h->overflow_hash, ({
679 j = qhash_hash_mix (h, p->key) / QHASH_KEYS_PER_BUCKET;
691 hash_unset3 (h->overflow_hash, k, &j);
692 vec_add1 (h->overflow_free_indices, j);
693 h->overflow_counts[i] -= 1;
695 qhash_set_valid_elt_mask (h, bi0, valid0);
698 clib_memswap (v + t*elt_bytes,
704 qhash_set_valid_elt_mask (h, bi0, valid0 ^ match0);
710 _qhash_unset_multiple (void * v,
714 u32 * result_indices)
716 qhash_t * h = qhash_header (v);
717 uword * k, * hash_keys;
718 uword n_left, n_elts, bucket_mask;
724 for (i = 0; i < n_search_keys; i++)
725 result_indices[i] = ~0;
728 bucket_mask = pow2_mask (h->log2_hash_size) &~ (QHASH_KEYS_PER_BUCKET - 1);
730 hash_keys = h->hash_keys;
733 n_left = n_search_keys;
738 u32 a0, b0, c0, bi0, match0, valid0;
739 u32 a1, b1, c1, bi1, match1, valid1;
746 /* Keys must be unique. */
752 a0 = a1 = h->hash_seeds[0];
753 b0 = b1 = h->hash_seeds[1];
754 c0 = c1 = h->hash_seeds[2];
762 hash_mix32_step_1 (a0, b0, c0);
763 hash_mix32_step_1 (a1, b1, c1);
764 hash_mix32_step_2 (a0, b0, c0);
765 hash_mix32_step_2 (a1, b1, c1);
766 hash_mix32_step_3 (a0, b0, c0);
767 hash_mix32_step_3 (a1, b1, c1);
769 bi0 = c0 & bucket_mask;
770 bi1 = c1 & bucket_mask;
772 h0 = hash_keys + bi0;
773 h1 = hash_keys + bi1;
775 /* Search two buckets. */
776 valid0 = qhash_get_valid_elt_mask (h, bi0);
777 valid1 = qhash_get_valid_elt_mask (h, bi1);
779 match0 = qhash_search_bucket (h0, k0, valid0);
780 match1 = qhash_search_bucket (h1, k1, valid1);
782 n_elts -= (match0 != 0) + (match1 != 0);
784 if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID
785 || valid1 == QHASH_ALL_VALID))
789 qhash_set_valid_elt_mask (h, bi0, valid0);
791 valid1 = bi0 == bi1 ? valid0 : valid1;
794 qhash_set_valid_elt_mask (h, bi1, valid1);
796 r[0] = match0 ? bi0 + qhash_min_log2 (match0) : ~0;
797 r[1] = match1 ? bi1 + qhash_min_log2 (match1) : ~0;
802 r[0] = unset_slow_path (v, elt_bytes, k0, bi0, valid0, match0,
806 /* Search again in same bucket to test new overflow element. */
807 valid1 = qhash_get_valid_elt_mask (h, bi0);
810 match1 = qhash_search_bucket (h1, k1, valid1);
811 n_elts -= (match1 != 0);
814 r[1] = unset_slow_path (v, elt_bytes, k1, bi1, valid1, match1,
821 u32 a0, b0, c0, bi0, match0, valid0;
828 a0 = h->hash_seeds[0];
829 b0 = h->hash_seeds[1];
830 c0 = h->hash_seeds[2];
836 hash_mix32 (a0, b0, c0);
838 bi0 = c0 & bucket_mask;
840 h0 = hash_keys + bi0;
842 valid0 = qhash_get_valid_elt_mask (h, bi0);
844 match0 = qhash_search_bucket (h0, k0, valid0);
845 n_elts -= (match0 != 0);
846 qhash_set_valid_elt_mask (h, bi0, valid0 ^ match0);
848 r[0] = match0 ? bi0 + qhash_min_log2 (match0) : ~0;
851 if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID))
852 r[-1] = unset_slow_path (v, elt_bytes, k0, bi0, valid0, match0,