FD.io VPP  v18.01.2-1-g9b554f3
Vector Packet Processing
qhash.c
Go to the documentation of this file.
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) 2006 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/qhash.h>
39 
40 #define QHASH_ALL_VALID ((1 << QHASH_KEYS_PER_BUCKET) - 1)
41 
42 void *
43 _qhash_resize (void *v, uword length, uword elt_bytes)
44 {
45  qhash_t *h;
46  uword l;
47 
48  l = clib_max (max_log2 (length), 2 + QHASH_LOG2_KEYS_PER_BUCKET);
49 
50  /* Round up if less than 1/2 full. */
51  l += ((f64) length / (f64) (1 << l)) < .5;
52 
53  v = _vec_resize (0, 1 << l, elt_bytes << l, sizeof (h[0]),
54  /* align */ sizeof (uword));
55 
56  h = qhash_header (v);
57  h->n_elts = 0;
58  h->log2_hash_size = l;
59  h->hash_keys =
60  clib_mem_alloc_aligned_no_fail (sizeof (h->hash_keys[0]) << l,
63  1 << (l - QHASH_LOG2_KEYS_PER_BUCKET));
64  memset (v, ~0, elt_bytes << l);
65 
66  return v;
67 }
68 
69 static u8 min_log2_table[256];
70 
71 static inline uword
73 {
74  ASSERT (is_pow2 (x));
75  ASSERT (x < 256);
76  return min_log2_table[x];
77 }
78 
79 static void
81 {
82  int i;
83  for (i = 0; i < 256; i++)
84  min_log2_table[i] = min_log2 (i);
85 }
86 
89 {
91 }
92 
93 always_inline void
95 {
97 }
98 
100 qhash_search_bucket (uword * hash_keys, uword search_key, uword m)
101 {
102  uword t;
103 #define _(i) ((hash_keys[i] == search_key) << i)
104  t = (_(0) | _(1) | _(2) | _(3));
105  if (QHASH_KEYS_PER_BUCKET > 4)
106  t |= (_(4) | _(5) | _(6) | _(7));
107  if (QHASH_KEYS_PER_BUCKET > 8)
108  t |= (_(8) | _(9) | _(10) | _(11) | _(12) | _(13) | _(14) | _(15));
109 #undef _
110  return m & t;
111 }
112 
113 /* Lookup multiple keys in the same hash table. */
114 void
116  uword * search_keys,
117  uword n_search_keys, u32 * result_indices)
118 {
119  qhash_t *h = qhash_header (v);
120  uword *k, *hash_keys;
121  uword n_left, bucket_mask;
122  u32 *r;
123 
124  if (!v)
125  {
126  memset (result_indices, ~0, sizeof (result_indices[0]) * n_search_keys);
127  return;
128  }
129 
130  bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1);
131 
132  k = search_keys;
133  n_left = n_search_keys;
134  hash_keys = h->hash_keys;
135  r = result_indices;
136 
137  while (n_left >= 2)
138  {
139  u32 a0, b0, c0, bi0, valid0, match0;
140  u32 a1, b1, c1, bi1, valid1, match1;
141  uword k0, k1, *h0, *h1;
142 
143  k0 = k[0];
144  k1 = k[1];
145  n_left -= 2;
146  k += 2;
147 
148  a0 = a1 = h->hash_seeds[0];
149  b0 = b1 = h->hash_seeds[1];
150  c0 = c1 = h->hash_seeds[2];
151  a0 ^= k0;
152  a1 ^= k1;
153 #if uword_bits == 64
154  b0 ^= k0 >> 32;
155  b1 ^= k1 >> 32;
156 #endif
157 
158  hash_mix32_step_1 (a0, b0, c0);
159  hash_mix32_step_1 (a1, b1, c1);
160  hash_mix32_step_2 (a0, b0, c0);
161  hash_mix32_step_2 (a1, b1, c1);
162  hash_mix32_step_3 (a0, b0, c0);
163  hash_mix32_step_3 (a1, b1, c1);
164 
165  bi0 = c0 & bucket_mask;
166  bi1 = c1 & bucket_mask;
167 
168  h0 = hash_keys + bi0;
169  h1 = hash_keys + bi1;
170 
171  /* Search two buckets. */
172  valid0 = qhash_get_valid_elt_mask (h, bi0);
173  valid1 = qhash_get_valid_elt_mask (h, bi1);
174 
175  match0 = qhash_search_bucket (h0, k0, valid0);
176  match1 = qhash_search_bucket (h1, k1, valid1);
177 
178  bi0 += qhash_min_log2 (match0);
179  bi1 += qhash_min_log2 (match1);
180 
181  r[0] = match0 ? bi0 : ~0;
182  r[1] = match1 ? bi1 : ~0;
183  r += 2;
184 
185  /* Full buckets trigger search of overflow hash. */
186  if (PREDICT_FALSE (!match0 && valid0 == QHASH_ALL_VALID))
187  {
188  uword *p = hash_get (h->overflow_hash, k0);
189  r[-2] = p ? p[0] : ~0;
190  }
191 
192  /* Full buckets trigger search of overflow hash. */
193  if (PREDICT_FALSE (!match1 && valid1 == QHASH_ALL_VALID))
194  {
195  uword *p = hash_get (h->overflow_hash, k1);
196  r[-1] = p ? p[0] : ~0;
197  }
198  }
199 
200  while (n_left >= 1)
201  {
202  u32 a0, b0, c0, bi0, valid0, match0;
203  uword k0, *h0;
204 
205  k0 = k[0];
206  n_left -= 1;
207  k += 1;
208 
209  a0 = h->hash_seeds[0];
210  b0 = h->hash_seeds[1];
211  c0 = h->hash_seeds[2];
212  a0 ^= k0;
213 #if uword_bits == 64
214  b0 ^= k0 >> 32;
215 #endif
216 
217  hash_mix32 (a0, b0, c0);
218 
219  bi0 = c0 & bucket_mask;
220 
221  h0 = hash_keys + bi0;
222 
223  /* Search one bucket. */
224  valid0 = qhash_get_valid_elt_mask (h, bi0);
225  match0 = qhash_search_bucket (h0, k0, valid0);
226 
227  bi0 += qhash_min_log2 (match0);
228 
229  r[0] = match0 ? bi0 : ~0;
230  r += 1;
231 
232  /* Full buckets trigger search of overflow hash. */
233  if (PREDICT_FALSE (!match0 && valid0 == QHASH_ALL_VALID))
234  {
235  uword *p = hash_get (h->overflow_hash, k0);
236  r[-1] = p ? p[0] : ~0;
237  }
238  }
239 }
240 
241 /* Lookup multiple keys in the same hash table.
242  Returns index of first matching key. */
243 u32
245  uword * search_keys,
246  uword n_search_keys, uword * matching_key)
247 {
248  qhash_t *h = qhash_header (v);
249  uword *k, *hash_keys;
250  uword n_left, match_mask, bucket_mask;
251 
252  if (!v)
253  return ~0;
254 
255  match_mask = 0;
256  bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1);
257 
258  k = search_keys;
259  n_left = n_search_keys;
260  hash_keys = h->hash_keys;
261  while (n_left >= 2)
262  {
263  u32 a0, b0, c0, bi0, valid0;
264  u32 a1, b1, c1, bi1, valid1;
265  uword k0, k1, *h0, *h1;
266 
267  k0 = k[0];
268  k1 = k[1];
269  n_left -= 2;
270  k += 2;
271 
272  a0 = a1 = h->hash_seeds[0];
273  b0 = b1 = h->hash_seeds[1];
274  c0 = c1 = h->hash_seeds[2];
275  a0 ^= k0;
276  a1 ^= k1;
277 #if uword_bits == 64
278  b0 ^= k0 >> 32;
279  b1 ^= k1 >> 32;
280 #endif
281 
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);
288 
289  bi0 = c0 & bucket_mask;
290  bi1 = c1 & bucket_mask;
291 
292  h0 = hash_keys + bi0;
293  h1 = hash_keys + bi1;
294 
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)
301  if (match_mask)
302  {
303  uword bi, is_match1;
304 
305  bi = qhash_min_log2 (match_mask);
306  is_match1 = bi >= QHASH_KEYS_PER_BUCKET;
307 
308  bi += ((is_match1 ? bi1 : bi0)
309  - (is_match1 << QHASH_LOG2_KEYS_PER_BUCKET));
310  *matching_key = (k - 2 - search_keys) + is_match1;
311  return bi;
312  }
313 
314  /* Full buckets trigger search of overflow hash. */
315  if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID
316  || valid1 == QHASH_ALL_VALID))
317  {
318  uword *p = 0;
319  uword ki = k - 2 - search_keys;
320 
321  if (valid0 == QHASH_ALL_VALID)
322  p = hash_get (h->overflow_hash, k0);
323 
324  if (!p && valid1 == QHASH_ALL_VALID)
325  {
326  p = hash_get (h->overflow_hash, k1);
327  ki++;
328  }
329 
330  if (p)
331  {
332  *matching_key = ki;
333  return p[0];
334  }
335  }
336  }
337 
338  while (n_left >= 1)
339  {
340  u32 a0, b0, c0, bi0, valid0;
341  uword k0, *h0;
342 
343  k0 = k[0];
344  n_left -= 1;
345  k += 1;
346 
347  a0 = h->hash_seeds[0];
348  b0 = h->hash_seeds[1];
349  c0 = h->hash_seeds[2];
350  a0 ^= k0;
351 #if uword_bits == 64
352  b0 ^= k0 >> 32;
353 #endif
354 
355  hash_mix32 (a0, b0, c0);
356 
357  bi0 = c0 & bucket_mask;
358 
359  h0 = hash_keys + bi0;
360 
361  /* Search one bucket. */
362  valid0 = qhash_get_valid_elt_mask (h, bi0);
363  match_mask = qhash_search_bucket (h0, k0, valid0);
364  if (match_mask)
365  {
366  uword bi;
367  bi = bi0 + qhash_min_log2 (match_mask);
368  *matching_key = (k - 1 - search_keys);
369  return bi;
370  }
371 
372  /* Full buckets trigger search of overflow hash. */
373  if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID))
374  {
375  uword *p = hash_get (h->overflow_hash, k0);
376  if (p)
377  {
378  *matching_key = (k - 1 - search_keys);
379  return p[0];
380  }
381  }
382  }
383 
384  return ~0;
385 }
386 
387 static void *
388 qhash_set_overflow (void *v, uword elt_bytes,
389  uword key, uword bi, uword * n_elts, u32 * result)
390 {
391  qhash_t *h = qhash_header (v);
392  uword *p = hash_get (h->overflow_hash, key);
393  uword i;
394 
395  bi /= QHASH_KEYS_PER_BUCKET;
396 
397  if (p)
398  i = p[0];
399  else
400  {
402  if (l > 0)
403  {
404  i = h->overflow_free_indices[l - 1];
405  _vec_len (h->overflow_free_indices) = l - 1;
406  }
407  else
408  i = (1 << h->log2_hash_size) + hash_elts (h->overflow_hash);
409  hash_set (h->overflow_hash, key, i);
410  vec_validate (h->overflow_counts, bi);
411  h->overflow_counts[bi] += 1;
412  *n_elts += 1;
413 
414  l = vec_len (v);
415  if (i >= l)
416  {
417  uword dl = round_pow2 (1 + i - l, 8);
418  v = _vec_resize (v, dl, (l + dl) * elt_bytes, sizeof (h[0]),
419  /* align */ sizeof (uword));
420  memset (v + l * elt_bytes, ~0, dl * elt_bytes);
421  }
422  }
423 
424  *result = i;
425 
426  return v;
427 }
428 
429 static uword
430 qhash_unset_overflow (void *v, uword key, uword bi, uword * n_elts)
431 {
432  qhash_t *h = qhash_header (v);
433  uword *p = hash_get (h->overflow_hash, key);
434  uword result;
435 
436  bi /= QHASH_KEYS_PER_BUCKET;
437 
438  if (p)
439  {
440  result = p[0];
441  hash_unset (h->overflow_hash, key);
442  ASSERT (bi < vec_len (h->overflow_counts));
443  ASSERT (h->overflow_counts[bi] > 0);
444  ASSERT (*n_elts > 0);
445  vec_add1 (h->overflow_free_indices, result);
446  h->overflow_counts[bi] -= 1;
447  *n_elts -= 1;
448  }
449  else
450  result = ~0;
451 
452  return result;
453 }
454 
457 {
458  return first_set (~valid_mask & pow2_mask (QHASH_KEYS_PER_BUCKET));
459 }
460 
461 void *
462 _qhash_set_multiple (void *v,
463  uword elt_bytes,
464  uword * search_keys,
465  uword n_search_keys, u32 * result_indices)
466 {
467  qhash_t *h = qhash_header (v);
468  uword *k, *hash_keys;
469  uword n_left, n_elts, bucket_mask;
470  u32 *r;
471 
472  if (vec_len (v) < n_search_keys)
473  v = _qhash_resize (v, n_search_keys, elt_bytes);
474 
475  if (qhash_min_log2 (2) != 1)
476  {
478  ASSERT (qhash_min_log2 (2) == 1);
479  }
480 
481  ASSERT (v != 0);
482 
483  bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1);
484 
485  hash_keys = h->hash_keys;
486  k = search_keys;
487  r = result_indices;
488  n_left = n_search_keys;
489  n_elts = h->n_elts;
490 
491  while (n_left >= 2)
492  {
493  u32 a0, b0, c0, bi0, match0, valid0, free0;
494  u32 a1, b1, c1, bi1, match1, valid1, free1;
495  uword k0, *h0;
496  uword k1, *h1;
497 
498  k0 = k[0];
499  k1 = k[1];
500 
501  /* Keys must be unique. */
502  ASSERT (k0 != k1);
503 
504  n_left -= 2;
505  k += 2;
506 
507  a0 = a1 = h->hash_seeds[0];
508  b0 = b1 = h->hash_seeds[1];
509  c0 = c1 = h->hash_seeds[2];
510  a0 ^= k0;
511  a1 ^= k1;
512 #if uword_bits == 64
513  b0 ^= k0 >> 32;
514  b1 ^= k1 >> 32;
515 #endif
516 
517  hash_mix32_step_1 (a0, b0, c0);
518  hash_mix32_step_1 (a1, b1, c1);
519  hash_mix32_step_2 (a0, b0, c0);
520  hash_mix32_step_2 (a1, b1, c1);
521  hash_mix32_step_3 (a0, b0, c0);
522  hash_mix32_step_3 (a1, b1, c1);
523 
524  bi0 = c0 & bucket_mask;
525  bi1 = c1 & bucket_mask;
526 
527  h0 = hash_keys + bi0;
528  h1 = hash_keys + bi1;
529 
530  /* Search two buckets. */
531  valid0 = qhash_get_valid_elt_mask (h, bi0);
532  valid1 = qhash_get_valid_elt_mask (h, bi1);
533 
534  match0 = qhash_search_bucket (h0, k0, valid0);
535  match1 = qhash_search_bucket (h1, k1, valid1);
536 
537  /* Find first free element starting at hash offset into bucket. */
538  free0 = qhash_find_free (c0 & (QHASH_KEYS_PER_BUCKET - 1), valid0);
539 
540  valid1 = valid1 | (bi0 == bi1 ? free0 : 0);
541  free1 = qhash_find_free (c1 & (QHASH_KEYS_PER_BUCKET - 1), valid1);
542 
543  n_elts += (match0 == 0) + (match1 == 0);
544 
545  match0 = match0 ? match0 : free0;
546  match1 = match1 ? match1 : free1;
547 
548  valid0 |= match0;
549  valid1 |= match1;
550 
551  h0 += qhash_min_log2 (match0);
552  h1 += qhash_min_log2 (match1);
553 
554  if (PREDICT_FALSE (!match0 || !match1))
555  goto slow_path2;
556 
557  h0[0] = k0;
558  h1[0] = k1;
559  r[0] = h0 - hash_keys;
560  r[1] = h1 - hash_keys;
561  r += 2;
562  qhash_set_valid_elt_mask (h, bi0, valid0);
563  qhash_set_valid_elt_mask (h, bi1, valid1);
564  continue;
565 
566  slow_path2:
567  if (!match0)
568  {
569  n_elts -= 1;
570  v = qhash_set_overflow (v, elt_bytes, k0, bi0, &n_elts, &r[0]);
571  }
572  else
573  {
574  h0[0] = k0;
575  r[0] = h0 - hash_keys;
576  qhash_set_valid_elt_mask (h, bi0, valid0);
577  }
578  if (!match1)
579  {
580  n_elts -= 1;
581  v = qhash_set_overflow (v, elt_bytes, k1, bi1, &n_elts, &r[1]);
582  }
583  else
584  {
585  h1[0] = k1;
586  r[1] = h1 - hash_keys;
587  qhash_set_valid_elt_mask (h, bi1, valid1);
588  }
589  r += 2;
590  }
591 
592  while (n_left >= 1)
593  {
594  u32 a0, b0, c0, bi0, match0, valid0, free0;
595  uword k0, *h0;
596 
597  k0 = k[0];
598  n_left -= 1;
599  k += 1;
600 
601  a0 = h->hash_seeds[0];
602  b0 = h->hash_seeds[1];
603  c0 = h->hash_seeds[2];
604  a0 ^= k0;
605 #if uword_bits == 64
606  b0 ^= k0 >> 32;
607 #endif
608 
609  hash_mix32 (a0, b0, c0);
610 
611  bi0 = c0 & bucket_mask;
612 
613  h0 = hash_keys + bi0;
614 
615  valid0 = qhash_get_valid_elt_mask (h, bi0);
616 
617  /* Find first free element starting at hash offset into bucket. */
618  free0 = qhash_find_free (c0 & (QHASH_KEYS_PER_BUCKET - 1), valid0);
619 
620  match0 = qhash_search_bucket (h0, k0, valid0);
621 
622  n_elts += (match0 == 0);
623 
624  match0 = match0 ? match0 : free0;
625 
626  valid0 |= match0;
627 
628  h0 += qhash_min_log2 (match0);
629 
630  if (PREDICT_FALSE (!match0))
631  goto slow_path1;
632 
633  h0[0] = k0;
634  r[0] = h0 - hash_keys;
635  r += 1;
636  qhash_set_valid_elt_mask (h, bi0, valid0);
637  continue;
638 
639  slow_path1:
640  n_elts -= 1;
641  v = qhash_set_overflow (v, elt_bytes, k0, bi0, &n_elts, &r[0]);
642  r += 1;
643  }
644 
645  h = qhash_header (v);
646  h->n_elts = n_elts;
647 
648  return v;
649 }
650 
651 static uword
652 unset_slow_path (void *v, uword elt_bytes,
653  uword k0, uword bi0, uword valid0, uword match0,
654  uword * n_elts)
655 {
656  qhash_t *h = qhash_header (v);
657  uword i, j = 0, k, l, t = ~0;
658  hash_pair_t *p, *found;
659 
660  if (!match0)
661  {
662  if (valid0 == QHASH_ALL_VALID)
663  t = qhash_unset_overflow (v, k0, bi0, n_elts);
664  return t;
665  }
666 
667  i = bi0 / QHASH_KEYS_PER_BUCKET;
668  t = bi0 + qhash_min_log2 (match0);
669 
670  if (valid0 == QHASH_ALL_VALID
671  && i < vec_len (h->overflow_counts) && h->overflow_counts[i] > 0)
672  {
673  found = 0;
674  /* *INDENT-OFF* */
676  j = qhash_hash_mix (h, p->key) / QHASH_KEYS_PER_BUCKET;
677  if (j == i)
678  {
679  found = p;
680  break;
681  }
682  }));
683  /* *INDENT-ON* */
684  ASSERT (found != 0);
685  ASSERT (j == i);
686 
687  l = found->value[0];
688  k = found->key;
689  hash_unset3 (h->overflow_hash, k, &j);
691  h->overflow_counts[i] -= 1;
692 
693  qhash_set_valid_elt_mask (h, bi0, valid0);
694 
695  h->hash_keys[t] = k;
696  clib_memswap (v + t * elt_bytes, v + l * elt_bytes, elt_bytes);
697  t = l;
698  }
699  else
700  qhash_set_valid_elt_mask (h, bi0, valid0 ^ match0);
701 
702  return t;
703 }
704 
705 void
706 _qhash_unset_multiple (void *v,
707  uword elt_bytes,
708  uword * search_keys,
709  uword n_search_keys, u32 * result_indices)
710 {
711  qhash_t *h = qhash_header (v);
712  uword *k, *hash_keys;
713  uword n_left, n_elts, bucket_mask;
714  u32 *r;
715 
716  if (!v)
717  {
718  uword i;
719  for (i = 0; i < n_search_keys; i++)
720  result_indices[i] = ~0;
721  }
722 
723  bucket_mask = pow2_mask (h->log2_hash_size) & ~(QHASH_KEYS_PER_BUCKET - 1);
724 
725  hash_keys = h->hash_keys;
726  k = search_keys;
727  r = result_indices;
728  n_left = n_search_keys;
729  n_elts = h->n_elts;
730 
731  while (n_left >= 2)
732  {
733  u32 a0, b0, c0, bi0, match0, valid0;
734  u32 a1, b1, c1, bi1, match1, valid1;
735  uword k0, *h0;
736  uword k1, *h1;
737 
738  k0 = k[0];
739  k1 = k[1];
740 
741  /* Keys must be unique. */
742  ASSERT (k0 != k1);
743 
744  n_left -= 2;
745  k += 2;
746 
747  a0 = a1 = h->hash_seeds[0];
748  b0 = b1 = h->hash_seeds[1];
749  c0 = c1 = h->hash_seeds[2];
750  a0 ^= k0;
751  a1 ^= k1;
752 #if uword_bits == 64
753  b0 ^= k0 >> 32;
754  b1 ^= k1 >> 32;
755 #endif
756 
757  hash_mix32_step_1 (a0, b0, c0);
758  hash_mix32_step_1 (a1, b1, c1);
759  hash_mix32_step_2 (a0, b0, c0);
760  hash_mix32_step_2 (a1, b1, c1);
761  hash_mix32_step_3 (a0, b0, c0);
762  hash_mix32_step_3 (a1, b1, c1);
763 
764  bi0 = c0 & bucket_mask;
765  bi1 = c1 & bucket_mask;
766 
767  h0 = hash_keys + bi0;
768  h1 = hash_keys + bi1;
769 
770  /* Search two buckets. */
771  valid0 = qhash_get_valid_elt_mask (h, bi0);
772  valid1 = qhash_get_valid_elt_mask (h, bi1);
773 
774  match0 = qhash_search_bucket (h0, k0, valid0);
775  match1 = qhash_search_bucket (h1, k1, valid1);
776 
777  n_elts -= (match0 != 0) + (match1 != 0);
778 
779  if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID
780  || valid1 == QHASH_ALL_VALID))
781  goto slow_path2;
782 
783  valid0 ^= match0;
784  qhash_set_valid_elt_mask (h, bi0, valid0);
785 
786  valid1 = bi0 == bi1 ? valid0 : valid1;
787  valid1 ^= match1;
788 
789  qhash_set_valid_elt_mask (h, bi1, valid1);
790 
791  r[0] = match0 ? bi0 + qhash_min_log2 (match0) : ~0;
792  r[1] = match1 ? bi1 + qhash_min_log2 (match1) : ~0;
793  r += 2;
794  continue;
795 
796  slow_path2:
797  r[0] = unset_slow_path (v, elt_bytes, k0, bi0, valid0, match0, &n_elts);
798  if (bi0 == bi1)
799  {
800  /* Search again in same bucket to test new overflow element. */
801  valid1 = qhash_get_valid_elt_mask (h, bi0);
802  if (!match1)
803  {
804  match1 = qhash_search_bucket (h1, k1, valid1);
805  n_elts -= (match1 != 0);
806  }
807  }
808  r[1] = unset_slow_path (v, elt_bytes, k1, bi1, valid1, match1, &n_elts);
809  r += 2;
810  }
811 
812  while (n_left >= 1)
813  {
814  u32 a0, b0, c0, bi0, match0, valid0;
815  uword k0, *h0;
816 
817  k0 = k[0];
818  n_left -= 1;
819  k += 1;
820 
821  a0 = h->hash_seeds[0];
822  b0 = h->hash_seeds[1];
823  c0 = h->hash_seeds[2];
824  a0 ^= k0;
825 #if uword_bits == 64
826  b0 ^= k0 >> 32;
827 #endif
828 
829  hash_mix32 (a0, b0, c0);
830 
831  bi0 = c0 & bucket_mask;
832 
833  h0 = hash_keys + bi0;
834 
835  valid0 = qhash_get_valid_elt_mask (h, bi0);
836 
837  match0 = qhash_search_bucket (h0, k0, valid0);
838  n_elts -= (match0 != 0);
839  qhash_set_valid_elt_mask (h, bi0, valid0 ^ match0);
840 
841  r[0] = match0 ? bi0 + qhash_min_log2 (match0) : ~0;
842  r += 1;
843 
844  if (PREDICT_FALSE (valid0 == QHASH_ALL_VALID))
845  r[-1] = unset_slow_path (v, elt_bytes, k0, bi0, valid0, match0,
846  &n_elts);
847  }
848 
849  h->n_elts = n_elts;
850 }
851 
852 /*
853  * fd.io coding-style-patch-verification: ON
854  *
855  * Local Variables:
856  * eval: (c-set-style "gnu")
857  * End:
858  */
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:432
void clib_memswap(void *_a, void *_b, uword bytes)
Definition: string.c:43
#define hash_set(h, key, value)
Definition: hash.h:254
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:337
#define hash_unset(h, key)
Definition: hash.h:260
static void qhash_min_log2_init()
Definition: qhash.c:80
static qhash_t * qhash_header(void *v)
Definition: qhash.h:66
static uword qhash_search_bucket(uword *hash_keys, uword search_key, uword m)
Definition: qhash.c:100
u32 n_elts
Definition: qhash.h:48
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:518
#define QHASH_KEYS_PER_BUCKET
Definition: qhash.h:84
static uword qhash_find_free(uword i, uword valid_mask)
Definition: qhash.c:456
static uword min_log2(uword x)
Definition: clib.h:197
u32 * overflow_counts
Definition: qhash.h:58
uword value[0]
Definition: hash.h:164
static uword qhash_unset_overflow(void *v, uword key, uword bi, uword *n_elts)
Definition: qhash.c:430
#define always_inline
Definition: clib.h:92
static uword pow2_mask(uword x)
Definition: clib.h:265
#define vec_resize(V, N)
Resize a vector (no header, unspecified alignment) Add N elements to end of given vector V...
Definition: vec.h:237
u32 log2_hash_size
Definition: qhash.h:50
static uword unset_slow_path(void *v, uword elt_bytes, uword k0, uword bi0, uword valid0, uword match0, uword *n_elts)
Definition: qhash.c:652
static void * qhash_set_overflow(void *v, uword elt_bytes, uword key, uword bi, uword *n_elts, u32 *result)
Definition: qhash.c:388
#define hash_get(h, key)
Definition: hash.h:248
uword * overflow_hash
Definition: qhash.h:56
#define v
Definition: acl.c:341
#define PREDICT_FALSE(x)
Definition: clib.h:105
#define QHASH_ALL_VALID
Definition: qhash.c:40
vec_header_t h
Definition: buffer.c:282
#define hash_mix32(a0, b0, c0)
Definition: hash.h:538
static uword round_pow2(uword x, uword pow2)
Definition: clib.h:286
static uword first_set(uword x)
Definition: clib.h:298
static uword hash_elts(void *v)
Definition: hash.h:117
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
static uword qhash_min_log2(uword x)
Definition: qhash.c:72
u32 hash_seeds[3]
Definition: qhash.h:53
#define QHASH_LOG2_KEYS_PER_BUCKET
Definition: qhash.h:83
#define clib_max(x, y)
Definition: clib.h:333
static uword is_pow2(uword x)
Definition: clib.h:280
void qhash_get_multiple(void *v, uword *search_keys, uword n_search_keys, u32 *result_indices)
Definition: qhash.c:115
u64 uword
Definition: types.h:112
#define clib_mem_alloc_aligned_no_fail(size, align)
Definition: mem.h:146
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
double f64
Definition: types.h:142
static u8 min_log2_table[256]
Definition: qhash.c:69
unsigned char u8
Definition: types.h:56
#define hash_foreach_pair(p, v, body)
Iterate over hash pairs.
Definition: hash.h:372
static uword max_log2(uword x)
Definition: clib.h:236
static void qhash_set_valid_elt_mask(qhash_t *h, uword i, uword mask)
Definition: qhash.c:94
Definition: qhash.h:45
uword * hash_keys
Definition: qhash.h:62
#define hash_mix32_step_1(a, b, c)
Definition: hash.h:519
u32 qhash_get_first_match(void *v, uword *search_keys, uword n_search_keys, uword *matching_key)
Definition: qhash.c:244
#define hash_mix32_step_2(a, b, c)
Definition: hash.h:520
#define hash_mix32_step_3(a, b, c)
Definition: hash.h:521
#define CLIB_CACHE_LINE_BYTES
Definition: cache.h:67
u32 * overflow_free_indices
Definition: qhash.h:58
static uword qhash_get_valid_elt_mask(qhash_t *h, uword i)
Definition: qhash.c:88
uword key
Definition: hash.h:161
#define hash_unset3(h, key, old_value)
Definition: hash.h:263
u8 * hash_key_valid_bitmap
Definition: qhash.h:60