FD.io VPP  v21.06-3-gbb25fbf28
Vector Packet Processing
hash.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) 2001-2005 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/hash.h>
39 #include <vppinfra/error.h>
40 #include <vppinfra/mem.h>
41 #include <vppinfra/byte_order.h> /* for clib_arch_is_big_endian */
42 
43 always_inline void
45 {
46  clib_memset (p, 0, hash_pair_bytes (h));
47 }
48 
49 always_inline void
51 {
52  clib_memset (p->value, ~0, hash_value_bytes (h));
53 }
54 
56 get_pair (void *v, uword i)
57 {
58  hash_t *h = hash_header (v);
59  hash_pair_t *p;
60  ASSERT (i < vec_len (v));
61  p = v;
62  p += i << h->log2_pair_size;
63  return (hash_pair_union_t *) p;
64 }
65 
66 always_inline void
67 set_is_user (void *v, uword i, uword is_user)
68 {
69  hash_t *h = hash_header (v);
70  uword i0 = i / BITS (h->is_user[0]);
71  uword i1 = (uword) 1 << (i % BITS (h->is_user[0]));
72  if (is_user)
73  h->is_user[i0] |= i1;
74  else
75  h->is_user[i0] &= ~i1;
76 }
77 
78 static u8 *hash_format_pair_default (u8 * s, va_list * args);
79 
80 #if uword_bits == 64
81 
82 static inline u64
83 zap64 (u64 x, word n)
84 {
85 #define _(n) (((u64) 1 << (u64) (8*(n))) - (u64) 1)
86  static u64 masks_little_endian[] = {
87  0, _(1), _(2), _(3), _(4), _(5), _(6), _(7),
88  };
89  static u64 masks_big_endian[] = {
90  0, ~_(7), ~_(6), ~_(5), ~_(4), ~_(3), ~_(2), ~_(1),
91  };
92 #undef _
94  return x & masks_big_endian[n];
95  else
96  return x & masks_little_endian[n];
97 }
98 
99 /**
100  * make address-sanitizer skip this:
101  * clib_mem_unaligned + zap64 casts its input as u64, computes a mask
102  * according to the input length, and returns the casted maked value.
103  * Therefore all the 8 Bytes of the u64 are systematically read, which
104  * rightfully causes address-sanitizer to raise an error on smaller inputs.
105  *
106  * However the invalid Bytes are discarded within zap64(), which is why
107  * this can be silenced safely.
108  *
109  * The above is true *unless* the extra bytes cross a page boundary
110  * into unmapped or no-access space, hence the boundary crossing check.
111  */
112 static inline u64
113 hash_memory64 (void *p, word n_bytes, u64 state)
114 {
115  u64 *q = p;
116  u64 a, b, c, n;
117  int page_boundary_crossing;
119  union
120  {
121  u8 as_u8[8];
122  u64 as_u64;
123  } tmp;
124 
125  /*
126  * If the request crosses a 4k boundary, it's not OK to assume
127  * that the zap64 game is safe. 4k is the minimum known page size.
128  */
129  start_addr = (u64) p;
130  end_addr = start_addr + n_bytes + 7;
131  page_boundary_crossing = (start_addr >> 12) != (end_addr >> 12);
132 
133  a = b = 0x9e3779b97f4a7c13LL;
134  c = state;
135  n = n_bytes;
136 
137  while (n >= 3 * sizeof (u64))
138  {
139  a += clib_mem_unaligned (q + 0, u64);
140  b += clib_mem_unaligned (q + 1, u64);
141  c += clib_mem_unaligned (q + 2, u64);
142  hash_mix64 (a, b, c);
143  n -= 3 * sizeof (u64);
144  q += 3;
145  }
146 
147  c += n_bytes;
148  switch (n / sizeof (u64))
149  {
150  case 2:
151  a += clib_mem_unaligned (q + 0, u64);
152  b += clib_mem_unaligned (q + 1, u64);
153  if (n % sizeof (u64))
154  {
155  if (PREDICT_TRUE (page_boundary_crossing == 0))
156  c +=
157  zap64 (CLIB_MEM_OVERFLOW
158  (clib_mem_unaligned (q + 2, u64), q + 2, sizeof (u64)),
159  n % sizeof (u64)) << 8;
160  else
161  {
162  clib_memcpy_fast (tmp.as_u8, q + 2, n % sizeof (u64));
163  c += zap64 (tmp.as_u64, n % sizeof (u64)) << 8;
164  }
165  }
166  break;
167 
168  case 1:
169  a += clib_mem_unaligned (q + 0, u64);
170  if (n % sizeof (u64))
171  {
172  if (PREDICT_TRUE (page_boundary_crossing == 0))
173  b +=
174  zap64 (CLIB_MEM_OVERFLOW
175  (clib_mem_unaligned (q + 1, u64), q + 1, sizeof (u64)),
176  n % sizeof (u64));
177  else
178  {
179  clib_memcpy_fast (tmp.as_u8, q + 1, n % sizeof (u64));
180  b += zap64 (tmp.as_u64, n % sizeof (u64));
181  }
182  }
183  break;
184 
185  case 0:
186  if (n % sizeof (u64))
187  {
188  if (PREDICT_TRUE (page_boundary_crossing == 0))
189  a +=
190  zap64 (CLIB_MEM_OVERFLOW
191  (clib_mem_unaligned (q + 0, u64), q + 0, sizeof (u64)),
192  n % sizeof (u64));
193  else
194  {
195  clib_memcpy_fast (tmp.as_u8, q, n % sizeof (u64));
196  a += zap64 (tmp.as_u64, n % sizeof (u64));
197  }
198  }
199  break;
200  }
201 
202  hash_mix64 (a, b, c);
203 
204  return c;
205 }
206 
207 #else /* if uword_bits == 64 */
208 
209 static inline u32
210 zap32 (u32 x, word n)
211 {
212 #define _(n) (((u32) 1 << (u32) (8*(n))) - (u32) 1)
213  static u32 masks_little_endian[] = {
214  0, _(1), _(2), _(3),
215  };
216  static u32 masks_big_endian[] = {
217  0, ~_(3), ~_(2), ~_(1),
218  };
219 #undef _
221  return x & masks_big_endian[n];
222  else
223  return x & masks_little_endian[n];
224 }
225 
226 static inline u32
228 {
229  u32 *q = p;
230  u32 a, b, c, n;
231 
232  a = b = 0x9e3779b9;
233  c = state;
234  n = n_bytes;
235 
236  while (n >= 3 * sizeof (u32))
237  {
238  a += clib_mem_unaligned (q + 0, u32);
239  b += clib_mem_unaligned (q + 1, u32);
240  c += clib_mem_unaligned (q + 2, u32);
241  hash_mix32 (a, b, c);
242  n -= 3 * sizeof (u32);
243  q += 3;
244  }
245 
246  c += n_bytes;
247  switch (n / sizeof (u32))
248  {
249  case 2:
250  a += clib_mem_unaligned (q + 0, u32);
251  b += clib_mem_unaligned (q + 1, u32);
252  if (n % sizeof (u32))
253  c += zap32 (clib_mem_unaligned (q + 2, u32), n % sizeof (u32)) << 8;
254  break;
255 
256  case 1:
257  a += clib_mem_unaligned (q + 0, u32);
258  if (n % sizeof (u32))
259  b += zap32 (clib_mem_unaligned (q + 1, u32), n % sizeof (u32));
260  break;
261 
262  case 0:
263  if (n % sizeof (u32))
264  a += zap32 (clib_mem_unaligned (q + 0, u32), n % sizeof (u32));
265  break;
266  }
267 
268  hash_mix32 (a, b, c);
269 
270  return c;
271 }
272 #endif
273 
274 __clib_export uword
276 {
277  uword *q = p;
278 
279 #if uword_bits == 64
280  return hash_memory64 (q, n_bytes, state);
281 #else
282  return hash_memory32 (q, n_bytes, state);
283 #endif
284 }
285 
286 #if uword_bits == 64
288 hash_uword (uword x)
289 {
290  u64 a, b, c;
291 
292  a = b = 0x9e3779b97f4a7c13LL;
293  c = 0;
294  a += x;
295  hash_mix64 (a, b, c);
296  return c;
297 }
298 #else
301 {
302  u32 a, b, c;
303 
304  a = b = 0x9e3779b9;
305  c = 0;
306  a += x;
307  hash_mix32 (a, b, c);
308  return c;
309 }
310 #endif
311 
312 /* Call sum function. Hash code will be sum function value
313  modulo the prime length of the hash table. */
316 {
317  uword sum;
318  switch (pointer_to_uword ((void *) h->key_sum))
319  {
320  case KEY_FUNC_NONE:
321  sum = hash_uword (key);
322  break;
323 
325  sum = hash_uword (*uword_to_pointer (key, uword *));
326  break;
327 
329  sum = hash_uword (*uword_to_pointer (key, u32 *));
330  break;
331 
332  case KEY_FUNC_STRING:
333  sum = string_key_sum (h, key);
334  break;
335 
336  case KEY_FUNC_MEM:
337  sum = mem_key_sum (h, key);
338  break;
339 
340  default:
341  sum = h->key_sum (h, key);
342  break;
343  }
344 
345  return sum;
346 }
347 
349 key_equal1 (hash_t * h, uword key1, uword key2, uword e)
350 {
351  switch (pointer_to_uword ((void *) h->key_equal))
352  {
353  case KEY_FUNC_NONE:
354  break;
355 
357  e =
358  *uword_to_pointer (key1, uword *) == *uword_to_pointer (key2,
359  uword *);
360  break;
361 
363  e = *uword_to_pointer (key1, u32 *) == *uword_to_pointer (key2, u32 *);
364  break;
365 
366  case KEY_FUNC_STRING:
367  e = string_key_equal (h, key1, key2);
368  break;
369 
370  case KEY_FUNC_MEM:
371  e = mem_key_equal (h, key1, key2);
372  break;
373 
374  default:
375  e = h->key_equal (h, key1, key2);
376  break;
377  }
378  return e;
379 }
380 
381 /* Compares two keys: returns 1 if equal, 0 if not. */
383 key_equal (hash_t * h, uword key1, uword key2)
384 {
385  uword e = key1 == key2;
386  if (CLIB_DEBUG > 0 && key1 == key2)
387  ASSERT (key_equal1 (h, key1, key2, e));
388  if (!e)
389  e = key_equal1 (h, key1, key2, e);
390  return e;
391 }
392 
393 static hash_pair_union_t *
395 {
396  hash_t *h = hash_header (v);
397  hash_pair_t *p0, *p1;
398 
399  p0 = p1 = pi->pairs;
400  if (h->log2_pair_size > 0)
401  p1 = hash_forward (h, p0, indirect_pair_get_len (pi));
402  else
403  p1 += vec_len (p0);
404 
405  while (p0 < p1)
406  {
407  if (key_equal (h, p0->key, key))
408  return (hash_pair_union_t *) p0;
409  p0 = hash_forward1 (h, p0);
410  }
411 
412  return (hash_pair_union_t *) 0;
413 }
414 
415 static hash_pair_union_t *
417 {
418  hash_t *h = hash_header (v);
419  hash_pair_t *q;
420  hash_pair_indirect_t *pi = &p->indirect;
421  uword log2_bytes = 0;
422 
423  if (h->log2_pair_size == 0)
424  q = vec_new (hash_pair_t, 2);
425  else
426  {
427  log2_bytes = 1 + hash_pair_log2_bytes (h);
428  q = clib_mem_alloc (1ULL << log2_bytes);
429  }
431 
432  pi->pairs = q;
433  if (h->log2_pair_size > 0)
434  indirect_pair_set (pi, log2_bytes, 2);
435 
436  set_is_user (v, i, 0);
437 
438  /* First element is used by existing pair, second will be used by caller. */
439  q = hash_forward1 (h, q);
440  q->key = key;
441  init_pair (h, q);
442  return (hash_pair_union_t *) q;
443 }
444 
445 static hash_pair_union_t *
447  uword * found_key)
448 {
449  hash_t *h = hash_header (v);
450  hash_pair_t *new_pair;
452 
453  q = get_indirect (v, pi, key);
454  if (q)
455  {
456  *found_key = 1;
457  return q;
458  }
459 
460  if (h->log2_pair_size == 0)
461  vec_add2 (pi->pairs, new_pair, 1);
462  else
463  {
464  uword len, new_len, log2_bytes;
465 
466  len = indirect_pair_get_len (pi);
467  log2_bytes = indirect_pair_get_log2_bytes (pi);
468 
469  new_len = len + 1;
470  if (new_len * hash_pair_bytes (h) > (1ULL << log2_bytes))
471  {
472  pi->pairs = clib_mem_realloc (pi->pairs,
473  1ULL << (log2_bytes + 1),
474  1ULL << log2_bytes);
475  log2_bytes++;
476  }
477 
478  indirect_pair_set (pi, log2_bytes, new_len);
479  new_pair = pi->pairs + (len << h->log2_pair_size);
480  }
481  new_pair->key = key;
482  init_pair (h, new_pair);
483  *found_key = 0;
484  return (hash_pair_union_t *) new_pair;
485 }
486 
487 static void
489 {
490  hash_t *h = hash_header (v);
491  hash_pair_union_t *p = get_pair (v, i);
492  hash_pair_t *e;
493  hash_pair_indirect_t *pi = &p->indirect;
494  uword len, is_vec;
495 
496  is_vec = h->log2_pair_size == 0;
497 
498  ASSERT (!hash_is_user (v, i));
499  len = is_vec ? vec_len (pi->pairs) : indirect_pair_get_len (pi);
500  e = hash_forward (h, pi->pairs, len - 1);
501  ASSERT (q >= pi->pairs && q <= e);
502 
503  /* We have two or fewer pairs and we are delete one pair.
504  Make indirect pointer direct and free indirect memory. */
505  if (len <= 2)
506  {
507  hash_pair_t *r = pi->pairs;
508 
509  if (len == 2)
510  {
511  clib_memcpy_fast (p, q == r ? hash_forward1 (h, r) : r,
512  hash_pair_bytes (h));
513  set_is_user (v, i, 1);
514  }
515  else
516  zero_pair (h, &p->direct);
517 
518  if (is_vec)
519  vec_free (r);
520  else if (r)
521  clib_mem_free (r);
522  }
523  else
524  {
525  /* If deleting a pair we need to keep non-null pairs together. */
526  if (q < e)
528  else
529  zero_pair (h, q);
530  if (is_vec)
531  _vec_len (pi->pairs) -= 1;
532  else
534  }
535 }
536 
538 {
539  GET = 1,
540  SET = 2,
541  UNSET = 3,
542 };
543 
544 static hash_pair_t *
545 lookup (void *v, uword key, enum lookup_opcode op,
546  void *new_value, void *old_value)
547 {
548  hash_t *h = hash_header (v);
549  hash_pair_union_t *p = 0;
550  uword found_key = 0;
551  uword value_bytes;
552  uword i;
553 
554  if (!v)
555  return 0;
556 
557  i = key_sum (h, key) & (_vec_len (v) - 1);
558  p = get_pair (v, i);
559  value_bytes = hash_value_bytes (h);
560 
561  if (hash_is_user (v, i))
562  {
563  found_key = key_equal (h, p->direct.key, key);
564  if (found_key)
565  {
566  if (op == UNSET)
567  {
568  set_is_user (v, i, 0);
569  if (old_value && value_bytes)
570  clib_memcpy_fast (old_value, p->direct.value, value_bytes);
571  zero_pair (h, &p->direct);
572  }
573  }
574  else
575  {
576  if (op == SET)
577  p = set_indirect_is_user (v, i, p, key);
578  else
579  p = 0;
580  }
581  }
582  else
583  {
584  hash_pair_indirect_t *pi = &p->indirect;
585 
586  if (op == SET)
587  {
588  if (!pi->pairs)
589  {
590  p->direct.key = key;
591  set_is_user (v, i, 1);
592  }
593  else
594  p = set_indirect (v, pi, key, &found_key);
595  }
596  else
597  {
598  p = get_indirect (v, pi, key);
599  found_key = p != 0;
600  if (found_key && op == UNSET)
601  {
602  if (old_value && value_bytes)
603  clib_memcpy_fast (old_value, &p->direct.value, value_bytes);
604 
605  unset_indirect (v, i, &p->direct);
606 
607  /* Nullify p (since it's just been deleted).
608  Otherwise we might be tempted to play with it. */
609  p = 0;
610  }
611  }
612  }
613 
614  if (op == SET && p != 0 && value_bytes)
615  {
616  /* Save away old value for caller. */
617  if (old_value && found_key)
618  clib_memcpy_fast (old_value, &p->direct.value, value_bytes);
619  clib_memcpy_fast (&p->direct.value, new_value, value_bytes);
620  }
621 
622  if (op == SET)
623  h->elts += !found_key;
624  if (op == UNSET)
625  h->elts -= found_key;
626 
627  return &p->direct;
628 }
629 
630 /* Fetch value of key. */
631 __clib_export uword *
632 _hash_get (void *v, uword key)
633 {
634  hash_t *h = hash_header (v);
635  hash_pair_t *p;
636 
637  /* Don't even search table if its empty. */
638  if (!v || h->elts == 0)
639  return 0;
640 
641  p = lookup (v, key, GET, 0, 0);
642  if (!p)
643  return 0;
644  if (h->log2_pair_size == 0)
645  return &p->key;
646  else
647  return &p->value[0];
648 }
649 
650 __clib_export hash_pair_t *
651 _hash_get_pair (void *v, uword key)
652 {
653  return lookup (v, key, GET, 0, 0);
654 }
655 
656 __clib_export hash_pair_t *
657 hash_next (void *v, hash_next_t *hn)
658 {
659  hash_t *h = hash_header (v);
660  hash_pair_t *p;
661 
662  while (1)
663  {
664  if (hn->i == 0 && hn->j == 0)
665  {
666  /* Save flags. */
667  hn->f = h->flags;
668 
669  /* Prevent others from re-sizing hash table. */
670  h->flags |=
673  }
674  else if (hn->i >= hash_capacity (v))
675  {
676  /* Restore flags. */
677  h->flags = hn->f;
678  clib_memset (hn, 0, sizeof (hn[0]));
679  return 0;
680  }
681 
682  p = hash_forward (h, v, hn->i);
683  if (hash_is_user (v, hn->i))
684  {
685  hn->i++;
686  return p;
687  }
688  else
689  {
690  hash_pair_indirect_t *pi = (void *) p;
691  uword n;
692 
693  if (h->log2_pair_size > 0)
694  n = indirect_pair_get_len (pi);
695  else
696  n = vec_len (pi->pairs);
697 
698  if (hn->j >= n)
699  {
700  hn->i++;
701  hn->j = 0;
702  }
703  else
704  return hash_forward (h, pi->pairs, hn->j++);
705  }
706  }
707 }
708 
709 /* Remove key from table. */
710 __clib_export void *
711 _hash_unset (void *v, uword key, void *old_value)
712 {
713  hash_t *h;
714 
715  if (!v)
716  return v;
717 
718  (void) lookup (v, key, UNSET, 0, old_value);
719 
720  h = hash_header (v);
721  if (!(h->flags & HASH_FLAG_NO_AUTO_SHRINK))
722  {
723  /* Resize when 1/4 full. */
724  if (h->elts > 32 && 4 * (h->elts + 1) < vec_len (v))
725  v = hash_resize (v, vec_len (v) / 2);
726  }
727 
728  return v;
729 }
730 
731 __clib_export void *
732 _hash_create (uword elts, hash_t * h_user)
733 {
734  hash_t *h;
735  uword log2_pair_size;
736  void *v;
737 
738  /* Size of hash is power of 2 >= ELTS and larger than
739  number of bits in is_user bitmap elements. */
740  elts = clib_max (elts, BITS (h->is_user[0]));
741  elts = 1ULL << max_log2 (elts);
742 
743  log2_pair_size = 1;
744  if (h_user)
745  log2_pair_size = h_user->log2_pair_size;
746 
747  v = _vec_resize ((void *) 0,
748  /* vec len: */ elts,
749  /* data bytes: */
750  (elts << log2_pair_size) * sizeof (hash_pair_t),
751  /* header bytes: */
752  sizeof (h[0]) +
753  (elts / BITS (h->is_user[0])) * sizeof (h->is_user[0]),
754  /* alignment */ sizeof (hash_pair_t));
755  h = hash_header (v);
756 
757  if (h_user)
758  h[0] = h_user[0];
759 
760  h->log2_pair_size = log2_pair_size;
761  h->elts = 0;
762 
763  /* Default flags to never shrinking hash tables.
764  Shrinking tables can cause "jackpot" cases. */
765  if (!h_user)
766  h->flags = HASH_FLAG_NO_AUTO_SHRINK;
767 
768  if (!h->format_pair)
769  {
770  h->format_pair = hash_format_pair_default;
771  h->format_pair_arg = 0;
772  }
773 
774  return v;
775 }
776 
777 __clib_export void *
778 _hash_free (void *v)
779 {
780  hash_t *h = hash_header (v);
782  uword i;
783 
784  if (!v)
785  return v;
786 
787  /* We zero all freed memory in case user would be tempted to use it. */
788  for (i = 0; i < hash_capacity (v); i++)
789  {
790  if (hash_is_user (v, i))
791  continue;
792  p = get_pair (v, i);
793  if (h->log2_pair_size == 0)
794  vec_free (p->indirect.pairs);
795  else if (p->indirect.pairs)
797  }
798 
799  vec_free_header (h);
800 
801  return 0;
802 }
803 
804 static void *
805 hash_resize_internal (void *old, uword new_size, uword free_old)
806 {
807  void *new;
808  hash_pair_t *p;
809 
810  new = 0;
811  if (new_size > 0)
812  {
813  hash_t *h = old ? hash_header (old) : 0;
814  new = _hash_create (new_size, h);
815  /* *INDENT-OFF* */
816  hash_foreach_pair (p, old, {
817  new = _hash_set3 (new, p->key, &p->value[0], 0);
818  });
819  /* *INDENT-ON* */
820  }
821 
822  if (free_old)
823  hash_free (old);
824  return new;
825 }
826 
827 void *
828 hash_resize (void *old, uword new_size)
829 {
830  return hash_resize_internal (old, new_size, 1);
831 }
832 
833 __clib_export void *
834 hash_dup (void *old)
835 {
836  return hash_resize_internal (old, vec_len (old), 0);
837 }
838 
839 __clib_export void *
840 _hash_set3 (void *v, uword key, void *value, void *old_value)
841 {
842  hash_t *h;
843 
844  if (!v)
845  v = hash_create (0, sizeof (uword));
846 
847  h = hash_header (v);
848  (void) lookup (v, key, SET, value, old_value);
849 
850  if (!(h->flags & HASH_FLAG_NO_AUTO_GROW))
851  {
852  /* Resize when 3/4 full. */
853  if (4 * (h->elts + 1) > 3 * vec_len (v))
854  v = hash_resize (v, 2 * vec_len (v));
855  }
856 
857  return v;
858 }
859 
860 __clib_export uword
862 {
863  void *v = uword_to_pointer (key, void *);
864  return hash_memory (v, vec_len (v) * h->user, 0);
865 }
866 
867 __clib_export uword
869 {
870  void *v1 = uword_to_pointer (key1, void *);
871  void *v2 = uword_to_pointer (key2, void *);
872  uword l1 = vec_len (v1);
873  uword l2 = vec_len (v2);
874  return l1 == l2 && 0 == memcmp (v1, v2, l1 * h->user);
875 }
876 
877 __clib_export u8 *
878 vec_key_format_pair (u8 * s, va_list * args)
879 {
880  void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
881  void *v = va_arg (*args, void *);
882  hash_pair_t *p = va_arg (*args, hash_pair_t *);
883  hash_t *h = hash_header (v);
884  void *u = uword_to_pointer (p->key, void *);
885  int i;
886 
887  switch (h->user)
888  {
889  case 1:
890  s = format (s, "%v", u);
891  break;
892 
893  case 2:
894  {
895  u16 *w = u;
896  for (i = 0; i < vec_len (w); i++)
897  s = format (s, "0x%x, ", w[i]);
898  break;
899  }
900 
901  case 4:
902  {
903  u32 *w = u;
904  for (i = 0; i < vec_len (w); i++)
905  s = format (s, "0x%x, ", w[i]);
906  break;
907  }
908 
909  case 8:
910  {
911  u64 *w = u;
912  for (i = 0; i < vec_len (w); i++)
913  s = format (s, "0x%Lx, ", w[i]);
914  break;
915  }
916 
917  default:
918  s = format (s, "0x%U", format_hex_bytes, u, vec_len (u) * h->user);
919  break;
920  }
921 
922  if (hash_value_bytes (h) > 0)
923  s = format (s, " -> 0x%wx", p->value[0]);
924 
925  return s;
926 }
927 
928 __clib_export uword
930 {
931  uword *v = uword_to_pointer (key, void *);
932  return hash_memory (v, h->user, 0);
933 }
934 
935 __clib_export uword
937 {
938  void *v1 = uword_to_pointer (key1, void *);
939  void *v2 = uword_to_pointer (key2, void *);
940  return v1 && v2 && 0 == memcmp (v1, v2, h->user);
941 }
942 
943 uword
945 {
946  char *v = uword_to_pointer (key, char *);
947  return hash_memory (v, strlen (v), 0);
948 }
949 
950 uword
952 {
953  void *v1 = uword_to_pointer (key1, void *);
954  void *v2 = uword_to_pointer (key2, void *);
955  return v1 && v2 && 0 == strcmp (v1, v2);
956 }
957 
958 u8 *
959 string_key_format_pair (u8 * s, va_list * args)
960 {
961  void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
962  void *v = va_arg (*args, void *);
963  hash_pair_t *p = va_arg (*args, hash_pair_t *);
964  hash_t *h = hash_header (v);
965  void *u = uword_to_pointer (p->key, void *);
966 
967  s = format (s, "%s", u);
968 
969  if (hash_value_bytes (h) > 0)
970  s =
971  format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
972  hash_value_bytes (h));
973 
974  return s;
975 }
976 
977 static u8 *
978 hash_format_pair_default (u8 * s, va_list * args)
979 {
980  void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
981  void *v = va_arg (*args, void *);
982  hash_pair_t *p = va_arg (*args, hash_pair_t *);
983  hash_t *h = hash_header (v);
984 
985  s = format (s, "0x%08x", p->key);
986  if (hash_value_bytes (h) > 0)
987  s =
988  format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
989  hash_value_bytes (h));
990  return s;
991 }
992 
993 __clib_export uword
994 hash_bytes (void *v)
995 {
996  uword i, bytes;
997  hash_t *h = hash_header (v);
998 
999  if (!v)
1000  return 0;
1001 
1002  bytes = vec_capacity (v, hash_header_bytes (v));
1003 
1004  for (i = 0; i < hash_capacity (v); i++)
1005  {
1006  if (!hash_is_user (v, i))
1007  {
1008  hash_pair_union_t *p = get_pair (v, i);
1009  if (h->log2_pair_size > 0)
1010  bytes += 1 << indirect_pair_get_log2_bytes (&p->indirect);
1011  else
1012  bytes += vec_capacity (p->indirect.pairs, 0);
1013  }
1014  }
1015  return bytes;
1016 }
1017 
1018 __clib_export u8 *
1019 format_hash (u8 *s, va_list *va)
1020 {
1021  void *v = va_arg (*va, void *);
1022  int verbose = va_arg (*va, int);
1023  hash_pair_t *p;
1024  hash_t *h = hash_header (v);
1025  uword i;
1026 
1027  s = format (s, "hash %p, %wd elts, capacity %wd, %wd bytes used,\n",
1028  v, hash_elts (v), hash_capacity (v), hash_bytes (v));
1029 
1030  {
1031  uword *occupancy = 0;
1032 
1033  /* Count number of buckets with each occupancy. */
1034  for (i = 0; i < hash_capacity (v); i++)
1035  {
1036  uword j;
1037 
1038  if (hash_is_user (v, i))
1039  {
1040  j = 1;
1041  }
1042  else
1043  {
1044  hash_pair_union_t *p = get_pair (v, i);
1045  if (h->log2_pair_size > 0)
1046  j = indirect_pair_get_len (&p->indirect);
1047  else
1048  j = vec_len (p->indirect.pairs);
1049  }
1050 
1051  vec_validate (occupancy, j);
1052  occupancy[j]++;
1053  }
1054 
1055  s = format (s, " profile ");
1056  for (i = 0; i < vec_len (occupancy); i++)
1057  s = format (s, "%wd%c", occupancy[i],
1058  i + 1 == vec_len (occupancy) ? '\n' : ' ');
1059 
1060  s = format (s, " lookup # of compares: ");
1061  for (i = 1; i < vec_len (occupancy); i++)
1062  s = format (s, "%wd: .%03d%c", i,
1063  (1000 * i * occupancy[i]) / hash_elts (v),
1064  i + 1 == vec_len (occupancy) ? '\n' : ' ');
1065 
1066  vec_free (occupancy);
1067  }
1068 
1069  if (verbose)
1070  {
1071  /* *INDENT-OFF* */
1072  hash_foreach_pair (p, v, {
1073  s = format (s, " %U\n", h->format_pair, h->format_pair_arg, v, p);
1074  });
1075  /* *INDENT-ON* */
1076  }
1077 
1078  return s;
1079 }
1080 
1081 static uword
1083  va_list * va, int is_vec)
1084 {
1085  uword *hash = va_arg (*va, uword *);
1086  int *result = va_arg (*va, int *);
1087  u8 *string = 0;
1088  uword *p;
1089 
1090  if (!unformat (input, is_vec ? "%v%_" : "%s%_", &string))
1091  return 0;
1092 
1093  p = hash_get_mem (hash, string);
1094  if (p)
1095  *result = *p;
1096 
1097  vec_free (string);
1098  return p ? 1 : 0;
1099 }
1100 
1101 __clib_export uword
1103 {
1104  return unformat_hash_string_internal (input, va, /* is_vec */ 1);
1105 }
1106 
1107 __clib_export uword
1109 {
1110  return unformat_hash_string_internal (input, va, /* is_vec */ 0);
1111 }
1112 
1113 __clib_export clib_error_t *
1114 hash_validate (void *v)
1115 {
1116  hash_t *h = hash_header (v);
1117  uword i, j;
1118  uword *keys = 0;
1119  clib_error_t *error = 0;
1120 
1121 #define CHECK(x) if ((error = ERROR_ASSERT (x))) goto done;
1122 
1123  for (i = 0; i < hash_capacity (v); i++)
1124  {
1125  hash_pair_union_t *pu = get_pair (v, i);
1126 
1127  if (hash_is_user (v, i))
1128  {
1129  CHECK (pu->direct.key != 0);
1130  vec_add1 (keys, pu->direct.key);
1131  }
1132  else
1133  {
1134  hash_pair_t *p;
1135  hash_pair_indirect_t *pi = &pu->indirect;
1136  uword n;
1137 
1138  n = h->log2_pair_size > 0
1139  ? indirect_pair_get_len (pi) : vec_len (pi->pairs);
1140 
1141  for (p = pi->pairs; n-- > 0; p = hash_forward1 (h, p))
1142  {
1143  /* Assert key uniqueness. */
1144  for (j = 0; j < vec_len (keys); j++)
1145  CHECK (keys[j] != p->key);
1146  vec_add1 (keys, p->key);
1147  }
1148  }
1149  }
1150 
1151  CHECK (vec_len (keys) == h->elts);
1152 
1153  vec_free (keys);
1154 done:
1155  return error;
1156 }
1157 
1158 /*
1159  * fd.io coding-style-patch-verification: ON
1160  *
1161  * Local Variables:
1162  * eval: (c-set-style "gnu")
1163  * End:
1164  */
HASH_FLAG_HASH_NEXT_IN_PROGRESS
#define HASH_FLAG_HASH_NEXT_IN_PROGRESS
Definition: hash.h:66
hash_header
Definition: hash.h:53
tmp
u32 * tmp
Definition: interface_output.c:1078
hash_next_t::j
uword j
Definition: hash.h:477
end_addr
vl_api_address_t end_addr
Definition: ikev2_types.api:38
vec_key_sum
__clib_export uword vec_key_sum(hash_t *h, uword key)
Definition: hash.c:861
string_key_equal
uword string_key_equal(hash_t *h, uword key1, uword key2)
Definition: hash.c:951
key_equal1
static uword key_equal1(hash_t *h, uword key1, uword key2, uword e)
Definition: hash.c:349
hash_is_user
static uword hash_is_user(void *v, uword i)
Definition: hash.h:133
vec_new
#define vec_new(T, N)
Create new vector of given type and length (unspecified alignment, no header).
Definition: vec.h:365
clib_mem_realloc
static void * clib_mem_realloc(void *p, uword new_size, uword old_size)
Definition: mem.h:325
vec_key_format_pair
__clib_export u8 * vec_key_format_pair(u8 *s, va_list *args)
Definition: hash.c:878
clib_max
#define clib_max(x, y)
Definition: clib.h:335
zero_pair
static void zero_pair(hash_t *h, hash_pair_t *p)
Definition: hash.c:44
unformat_hash_string
__clib_export uword unformat_hash_string(unformat_input_t *input, va_list *va)
Definition: hash.c:1108
pointer_to_uword
static uword pointer_to_uword(const void *p)
Definition: types.h:131
hash_mix32
#define hash_mix32(a0, b0, c0)
Definition: hash.h:538
keys
vl_api_ikev2_keys_t keys
Definition: ikev2_types.api:125
indirect_pair_get_log2_bytes
static uword indirect_pair_get_log2_bytes(hash_pair_indirect_t *p)
Definition: hash.h:196
set_indirect
static hash_pair_union_t * set_indirect(void *v, hash_pair_indirect_t *pi, uword key, uword *found_key)
Definition: hash.c:446
format_hash
__clib_export u8 * format_hash(u8 *s, va_list *va)
Definition: hash.c:1019
hash_header
static hash_t * hash_header(void *v)
Definition: hash.h:111
hash_pair_indirect_t
Definition: hash.h:173
clib_mem_free
static void clib_mem_free(void *p)
Definition: mem.h:311
format_hex_bytes
u8 * format_hex_bytes(u8 *s, va_list *va)
Definition: std-formats.c:84
lookup
static hash_pair_t * lookup(void *v, uword key, enum lookup_opcode op, void *new_value, void *old_value)
Definition: hash.c:545
get_pair
static hash_pair_union_t * get_pair(void *v, uword i)
Definition: hash.c:56
hash_next_t
Definition: hash.h:475
hash_pair_log2_bytes
static uword hash_pair_log2_bytes(hash_t *h)
Definition: hash.h:324
hash_memory32
static u32 hash_memory32(void *p, word n_bytes, u32 state)
Definition: hash.c:227
clib_arch_is_big_endian
#define clib_arch_is_big_endian
Definition: byte_order.h:53
hash_header_bytes
static uword hash_header_bytes(void *v)
Definition: hash.h:101
vec_capacity
#define vec_capacity(v, b)
Total number of bytes that can fit in vector with current allocation.
Definition: vec_bootstrap.h:165
u16
unsigned short u16
Definition: types.h:57
get_indirect
static hash_pair_union_t * get_indirect(void *v, hash_pair_indirect_t *pi, uword key)
Definition: hash.c:394
hash_capacity
static uword hash_capacity(void *v)
Definition: hash.h:126
HASH_FLAG_NO_AUTO_SHRINK
#define HASH_FLAG_NO_AUTO_SHRINK
Definition: hash.h:64
byte_order.h
state
vl_api_dhcp_client_state_t state
Definition: dhcp.api:201
unformat_input_t
struct _unformat_input_t unformat_input_t
start_addr
vl_api_address_t start_addr
Definition: ikev2_types.api:37
r
vnet_hw_if_output_node_runtime_t * r
Definition: interface_output.c:1071
set_is_user
static void set_is_user(void *v, uword i, uword is_user)
Definition: hash.c:67
hash_create
#define hash_create(elts, value_bytes)
Definition: hash.h:695
set_indirect_is_user
static hash_pair_union_t * set_indirect_is_user(void *v, uword i, hash_pair_union_t *p, uword key)
Definition: hash.c:416
CHECK
#define CHECK(x)
clib_memcpy_fast
static_always_inline void * clib_memcpy_fast(void *restrict dst, const void *restrict src, size_t n)
Definition: string.h:92
h
h
Definition: flowhash_template.h:372
error
Definition: cJSON.c:88
unset_indirect
static void unset_indirect(void *v, uword i, hash_pair_t *q)
Definition: hash.c:488
hash_dup
__clib_export void * hash_dup(void *old)
Definition: hash.c:834
init_pair
static void init_pair(hash_t *h, hash_pair_t *p)
Definition: hash.c:50
key
typedef key
Definition: ipsec_types.api:88
hash_foreach_pair
#define hash_foreach_pair(p, v, body)
Iterate over hash pairs.
Definition: hash.h:373
hash_header::log2_pair_size
u32 log2_pair_size
Definition: hash.h:68
max_log2
static uword max_log2(uword x)
Definition: clib.h:223
unformat
uword unformat(unformat_input_t *i, const char *fmt,...)
Definition: unformat.c:978
string_key_format_pair
u8 * string_key_format_pair(u8 *s, va_list *args)
Definition: hash.c:959
indirect_pair_set
static void indirect_pair_set(hash_pair_indirect_t *p, uword log2_alloc, uword len)
Definition: hash.h:213
vec_len
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
Definition: vec_bootstrap.h:142
len
u8 len
Definition: ip_types.api:103
error.h
hash_pair_bytes
static uword hash_pair_bytes(hash_t *h)
Definition: hash.h:337
vec_add2
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
Definition: vec.h:644
vec_add1
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:606
hash_forward
static void * hash_forward(hash_t *h, void *v, uword n)
Definition: hash.h:351
hash_pair_t::value
uword value[0]
Definition: hash.h:165
CLIB_UNUSED
#define CLIB_UNUSED(x)
Definition: clib.h:90
hash_free
#define hash_free(h)
Definition: hash.h:310
BITS
#define BITS(x)
Definition: clib.h:69
c
svmdb_client_t * c
Definition: vpp_get_metrics.c:48
uword
u64 uword
Definition: types.h:112
hash_resize_internal
static void * hash_resize_internal(void *old, uword new_size, uword free_old)
Definition: hash.c:805
clib_mem_unaligned
#define clib_mem_unaligned(pointer, type)
Definition: types.h:155
string_key_sum
uword string_key_sum(hash_t *h, uword key)
Definition: hash.c:944
i
sll srl srl sll sra u16x4 i
Definition: vector_sse42.h:261
vec_key_equal
__clib_export uword vec_key_equal(hash_t *h, uword key1, uword key2)
Definition: hash.c:868
hash_next_t::i
uword i
Definition: hash.h:477
vec_validate
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment)
Definition: vec.h:523
KEY_FUNC_NONE
#define KEY_FUNC_NONE
Definition: hash.h:76
lookup_opcode
lookup_opcode
Definition: hash.c:537
KEY_FUNC_MEM
#define KEY_FUNC_MEM
Definition: hash.h:80
hash_pair_indirect_t::pairs
hash_pair_t * pairs
Definition: hash.h:176
UNSET
@ UNSET
Definition: hash.c:541
hash_memory
__clib_export uword hash_memory(void *p, word n_bytes, uword state)
Definition: hash.c:275
hash_pair_union_t::indirect
hash_pair_indirect_t indirect
Definition: hash.h:188
hash_validate
__clib_export clib_error_t * hash_validate(void *v)
Definition: hash.c:1114
KEY_FUNC_POINTER_U32
#define KEY_FUNC_POINTER_U32
Definition: hash.h:78
KEY_FUNC_POINTER_UWORD
#define KEY_FUNC_POINTER_UWORD
Definition: hash.h:77
hash_next
__clib_export hash_pair_t * hash_next(void *v, hash_next_t *hn)
Definition: hash.c:657
hash_elts
static uword hash_elts(void *v)
Definition: hash.h:118
vec_free
#define vec_free(V)
Free vector's memory (no header).
Definition: vec.h:395
always_inline
#define always_inline
Definition: rdma_mlx5dv.h:23
hash_pair_union_t
Definition: hash.h:185
hash_get_mem
#define hash_get_mem(h, key)
Definition: hash.h:269
u64
unsigned long u64
Definition: types.h:89
format
description fragment has unexpected format
Definition: map.api:433
ASSERT
#define ASSERT(truth)
Definition: error_bootstrap.h:69
mem_key_equal
__clib_export uword mem_key_equal(hash_t *h, uword key1, uword key2)
Definition: hash.c:936
u32
unsigned int u32
Definition: types.h:88
KEY_FUNC_STRING
#define KEY_FUNC_STRING
Definition: hash.h:79
indirect_pair_get_len
static uword indirect_pair_get_len(hash_pair_indirect_t *p)
Definition: hash.h:203
n_bytes
u32 n_bytes
Definition: interface_output.c:401
hash_pair_union_t::direct
hash_pair_t direct
Definition: hash.h:187
hash_resize
void * hash_resize(void *old, uword new_size)
Definition: hash.c:828
hash_value_bytes
static uword hash_value_bytes(hash_t *h)
Definition: hash.h:316
hash_pair_t::key
uword key
Definition: hash.h:162
as_u64
u64 as_u64
Definition: bihash_doc.h:63
CLIB_MEM_OVERFLOW
#define CLIB_MEM_OVERFLOW(a, b, c)
Definition: sanitizer.h:48
mem_key_sum
__clib_export uword mem_key_sum(hash_t *h, uword key)
Definition: hash.c:929
value
u8 value
Definition: qos.api:54
hash_mix64
#define hash_mix64(a0, b0, c0)
Definition: hash.h:530
zap32
static u32 zap32(u32 x, word n)
Definition: hash.c:210
GET
@ GET
Definition: hash.c:539
key_equal
static uword key_equal(hash_t *h, uword key1, uword key2)
Definition: hash.c:383
clib_memset
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
hash_format_pair_default
static u8 * hash_format_pair_default(u8 *s, va_list *args)
Definition: hash.c:978
hash.h
b
vlib_buffer_t ** b
Definition: nat44_ei_out2in.c:717
u8
unsigned char u8
Definition: types.h:56
clib_error_t
Definition: clib_error.h:21
a
a
Definition: bitmap.h:544
uword_to_pointer
#define uword_to_pointer(u, type)
Definition: types.h:136
hash_bytes
__clib_export uword hash_bytes(void *v)
Definition: hash.c:994
word
i64 word
Definition: types.h:111
mem.h
SET
@ SET
Definition: hash.c:540
hash_next_t::f
uword f
Definition: hash.h:477
PREDICT_TRUE
#define PREDICT_TRUE(x)
Definition: clib.h:125
vec_free_header
#define vec_free_header(h)
Free vector user header (syntactic sugar)
Definition: vec.h:403
unformat_hash_string_internal
static uword unformat_hash_string_internal(unformat_input_t *input, va_list *va, int is_vec)
Definition: hash.c:1082
clib_mem_alloc
static void * clib_mem_alloc(uword size)
Definition: mem.h:253
unformat_hash_vec_string
__clib_export uword unformat_hash_vec_string(unformat_input_t *input, va_list *va)
Definition: hash.c:1102
hash_uword
static uword hash_uword(uword x)
Definition: hash.c:300
hash_pair_t
Definition: hash.h:159
hash_forward1
static void * hash_forward1(hash_t *h, void *v)
Definition: hash.h:344
HASH_FLAG_NO_AUTO_GROW
#define HASH_FLAG_NO_AUTO_GROW
Definition: hash.h:62
key_sum
static uword key_sum(hash_t *h, uword key)
Definition: hash.c:315