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