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