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