FD.io VPP  v20.09-64-g4f7b92f0a
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
227 hash_memory32 (void *p, word n_bytes, u32 state)
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 uword
275 hash_memory (void *p, word n_bytes, uword state)
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)
527  clib_memcpy_fast (q, e, hash_pair_bytes (h));
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 i;
552 
553  if (!v)
554  return 0;
555 
556  i = key_sum (h, key) & (_vec_len (v) - 1);
557  p = get_pair (v, i);
558 
559  if (hash_is_user (v, i))
560  {
561  found_key = key_equal (h, p->direct.key, key);
562  if (found_key)
563  {
564  if (op == UNSET)
565  {
566  set_is_user (v, i, 0);
567  if (old_value)
568  clib_memcpy_fast (old_value, p->direct.value,
569  hash_value_bytes (h));
570  zero_pair (h, &p->direct);
571  }
572  }
573  else
574  {
575  if (op == SET)
576  p = set_indirect_is_user (v, i, p, key);
577  else
578  p = 0;
579  }
580  }
581  else
582  {
583  hash_pair_indirect_t *pi = &p->indirect;
584 
585  if (op == SET)
586  {
587  if (!pi->pairs)
588  {
589  p->direct.key = key;
590  set_is_user (v, i, 1);
591  }
592  else
593  p = set_indirect (v, pi, key, &found_key);
594  }
595  else
596  {
597  p = get_indirect (v, pi, key);
598  found_key = p != 0;
599  if (found_key && op == UNSET)
600  {
601  if (old_value)
602  clib_memcpy_fast (old_value, &p->direct.value,
603  hash_value_bytes (h));
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)
615  {
616  /* Save away old value for caller. */
617  if (old_value && found_key)
618  clib_memcpy_fast (old_value, &p->direct.value, hash_value_bytes (h));
619  clib_memcpy_fast (&p->direct.value, new_value, hash_value_bytes (h));
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 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 hash_pair_t *
651 _hash_get_pair (void *v, uword key)
652 {
653  return lookup (v, key, GET, 0, 0);
654 }
655 
656 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 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 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)
767 
768  if (!h->format_pair)
769  {
771  h->format_pair_arg = 0;
772  }
773 
774  return v;
775 }
776 
777 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 void *
834 hash_dup (void *old)
835 {
836  return hash_resize_internal (old, vec_len (old), 0);
837 }
838 
839 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 uword
862 {
863  void *v = uword_to_pointer (key, void *);
864  return hash_memory (v, vec_len (v) * h->user, 0);
865 }
866 
867 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 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 uword
930 {
931  uword *v = uword_to_pointer (key, void *);
932  return hash_memory (v, h->user, 0);
933 }
934 
935 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 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 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 uword
1103 {
1104  return unformat_hash_string_internal (input, va, /* is_vec */ 1);
1105 }
1106 
1107 uword
1109 {
1110  return unformat_hash_string_internal (input, va, /* is_vec */ 0);
1111 }
1112 
1113 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  */
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:509
vl_api_address_t end_addr
Definition: ikev2_types.api:38
lookup_opcode
Definition: hash.c:537
any user
Definition: hash.h:86
#define KEY_FUNC_NONE
Definition: hash.h:76
u8 * string_key_format_pair(u8 *s, va_list *args)
Definition: hash.c:959
static void unset_indirect(void *v, uword i, hash_pair_t *q)
Definition: hash.c:488
static void init_pair(hash_t *h, hash_pair_t *p)
Definition: hash.c:50
#define CLIB_UNUSED(x)
Definition: clib.h:87
uword mem_key_equal(hash_t *h, uword key1, uword key2)
Definition: hash.c:936
static uword indirect_pair_get_len(hash_pair_indirect_t *p)
Definition: hash.h:203
void * format_pair_arg
Definition: hash.h:92
void * hash_resize(void *old, uword new_size)
Definition: hash.c:828
a
Definition: bitmap.h:538
#define KEY_FUNC_STRING
Definition: hash.h:79
u64 as_u64
Definition: bihash_doc.h:63
#define PREDICT_TRUE(x)
Definition: clib.h:121
unsigned long u64
Definition: types.h:89
#define KEY_FUNC_POINTER_UWORD
Definition: hash.h:77
vl_api_address_t start_addr
Definition: ikev2_types.api:37
#define clib_memcpy_fast(a, b, c)
Definition: string.h:81
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
hash_pair_t * pairs
Definition: hash.h:176
static void * clib_mem_realloc(void *p, uword new_size, uword old_size)
Definition: mem.h:228
#define HASH_FLAG_NO_AUTO_GROW
Definition: hash.h:62
#define vec_free_header(h)
Free vector user header (syntactic sugar)
Definition: vec.h:388
static hash_pair_union_t * get_indirect(void *v, hash_pair_indirect_t *pi, uword key)
Definition: hash.c:394
uword j
Definition: hash.h:478
#define KEY_FUNC_MEM
Definition: hash.h:80
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:592
static void zero_pair(hash_t *h, hash_pair_t *p)
Definition: hash.c:44
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
Definition: vec.h:630
static void indirect_pair_set(hash_pair_indirect_t *p, uword log2_alloc, uword len)
Definition: hash.h:213
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:424
unsigned char u8
Definition: types.h:56
static uword hash_header_bytes(void *v)
Definition: hash.h:101
uword value[0]
Definition: hash.h:165
#define CLIB_MEM_OVERFLOW(a, b, c)
Definition: sanitizer.h:48
uword elts
Definition: hash.h:56
u32 log2_pair_size
Definition: hash.h:68
static u32 zap32(u32 x, word n)
Definition: hash.c:210
i64 word
Definition: types.h:111
#define KEY_FUNC_POINTER_U32
Definition: hash.h:78
#define vec_new(T, N)
Create new vector of given type and length (unspecified alignment, no header).
Definition: vec.h:350
static void set_is_user(void *v, uword i, uword is_user)
Definition: hash.c:67
hash_key_equal_function_t * key_equal
Definition: hash.h:83
static uword key_equal1(hash_t *h, uword key1, uword key2, uword e)
Definition: hash.c:349
u8 * format_hex_bytes(u8 *s, va_list *va)
Definition: std-formats.c:84
static uword key_sum(hash_t *h, uword key)
Definition: hash.c:315
unsigned int u32
Definition: types.h:88
uword vec_key_sum(hash_t *h, uword key)
Definition: hash.c:861
u8 * format_hash(u8 *s, va_list *va)
Definition: hash.c:1019
uword f
Definition: hash.h:478
static uword hash_value_bytes(hash_t *h)
Definition: hash.h:316
u8 * vec_key_format_pair(u8 *s, va_list *args)
Definition: hash.c:878
static hash_pair_union_t * set_indirect(void *v, hash_pair_indirect_t *pi, uword key, uword *found_key)
Definition: hash.c:446
static hash_t * hash_header(void *v)
Definition: hash.h:111
static uword hash_capacity(void *v)
Definition: hash.h:126
clib_error_t * hash_validate(void *v)
Definition: hash.c:1114
static uword hash_is_user(void *v, uword i)
Definition: hash.h:133
static u8 * hash_format_pair_default(u8 *s, va_list *args)
Definition: hash.c:978
static uword hash_pair_bytes(hash_t *h)
Definition: hash.h:337
struct _unformat_input_t unformat_input_t
unsigned short u16
Definition: types.h:57
uword hash_bytes(void *v)
Definition: hash.c:994
vec_header_t h
Definition: buffer.c:322
#define hash_free(h)
Definition: hash.h:310
#define always_inline
Definition: ipsec.h:28
u32 flags
Definition: hash.h:59
Definition: hash.c:539
u8 len
Definition: ip_types.api:92
format_function_t * format_pair
Definition: hash.h:89
static uword hash_pair_log2_bytes(hash_t *h)
Definition: hash.h:324
hash_pair_t * hash_next(void *v, hash_next_t *hn)
Definition: hash.c:657
static void * hash_resize_internal(void *old, uword new_size, uword free_old)
Definition: hash.c:805
static hash_pair_t * lookup(void *v, uword key, enum lookup_opcode op, void *new_value, void *old_value)
Definition: hash.c:545
hash_pair_indirect_t indirect
Definition: hash.h:188
#define clib_arch_is_big_endian
Definition: byte_order.h:53
#define hash_mix64(a0, b0, c0)
Definition: hash.h:531
svmdb_client_t * c
#define CHECK(x)
sll srl srl sll sra u16x4 i
Definition: vector_sse42.h:317
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:380
static void * hash_forward1(hash_t *h, void *v)
Definition: hash.h:344
#define hash_mix32(a0, b0, c0)
Definition: hash.h:539
static uword hash_uword(uword x)
Definition: hash.c:300
#define HASH_FLAG_HASH_NEXT_IN_PROGRESS
Definition: hash.h:66
Definition: hash.c:540
#define vec_capacity(v, b)
Total number of bytes that can fit in vector with current allocation.
static uword indirect_pair_get_log2_bytes(hash_pair_indirect_t *p)
Definition: hash.h:196
static uword unformat_hash_string_internal(unformat_input_t *input, va_list *va, int is_vec)
Definition: hash.c:1082
static hash_pair_union_t * get_pair(void *v, uword i)
Definition: hash.c:56
void * hash_dup(void *old)
Definition: hash.c:834
#define hash_create(elts, value_bytes)
Definition: hash.h:696
#define uword_to_pointer(u, type)
Definition: types.h:136
static hash_pair_union_t * set_indirect_is_user(void *v, uword i, hash_pair_union_t *p, uword key)
Definition: hash.c:416
u8 value
Definition: qos.api:54
static uword hash_elts(void *v)
Definition: hash.h:118
#define ASSERT(truth)
static void * hash_forward(hash_t *h, void *v, uword n)
Definition: hash.h:351
uword string_key_sum(hash_t *h, uword key)
Definition: hash.c:944
uword hash_memory(void *p, word n_bytes, uword state)
Definition: hash.c:275
static void clib_mem_free(void *p)
Definition: mem.h:215
uword i
Definition: hash.h:478
#define clib_mem_unaligned(pointer, type)
Definition: types.h:155
static void * clib_mem_alloc(uword size)
Definition: mem.h:157
uword unformat_hash_string(unformat_input_t *input, va_list *va)
Definition: hash.c:1108
static uword pointer_to_uword(const void *p)
Definition: types.h:131
#define clib_max(x, y)
Definition: clib.h:320
typedef key
Definition: ipsec_types.api:85
hash_pair_t direct
Definition: hash.h:187
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
#define hash_foreach_pair(p, v, body)
Iterate over hash pairs.
Definition: hash.h:373
static uword max_log2(uword x)
Definition: clib.h:208
Definition: hash.c:541
u64 uword
Definition: types.h:112
#define hash_get_mem(h, key)
Definition: hash.h:269
uword string_key_equal(hash_t *h, uword key1, uword key2)
Definition: hash.c:951
uword unformat_hash_vec_string(unformat_input_t *input, va_list *va)
Definition: hash.c:1102
vl_api_dhcp_client_state_t state
Definition: dhcp.api:201
uword mem_key_sum(hash_t *h, uword key)
Definition: hash.c:929
#define HASH_FLAG_NO_AUTO_SHRINK
Definition: hash.h:64
#define BITS(x)
Definition: clib.h:66
static uword key_equal(hash_t *h, uword key1, uword key2)
Definition: hash.c:383
vl_api_ikev2_keys_t keys
uword is_user[0]
Definition: hash.h:96
uword vec_key_equal(hash_t *h, uword key1, uword key2)
Definition: hash.c:868
hash_key_sum_function_t * key_sum
Definition: hash.h:73
uword key
Definition: hash.h:162
uword unformat(unformat_input_t *i, const char *fmt,...)
Definition: unformat.c:978
static u32 hash_memory32(void *p, word n_bytes, u32 state)
Definition: hash.c:227