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