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