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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 Copyright (c) 2001-2005 Eliot Dresselhaus
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:
26 The above copyright notice and this permission notice shall be
27 included in all copies or substantial portions of the Software.
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.
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 */
44 zero_pair (hash_t * h, hash_pair_t * p)
46 memset (p, 0, hash_pair_bytes (h));
50 init_pair (hash_t * h, hash_pair_t * p)
52 memset (p->value, ~0, hash_value_bytes (h));
55 always_inline hash_pair_union_t *
56 get_pair (void *v, uword i)
58 hash_t *h = hash_header (v);
60 ASSERT (i < vec_len (v));
62 p += i << h->log2_pair_size;
63 return (hash_pair_union_t *) p;
67 set_is_user (void *v, uword i, uword is_user)
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]));
75 h->is_user[i0] &= ~i1;
78 static u8 *hash_format_pair_default (u8 * s, va_list * args);
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),
89 static u64 masks_big_endian[] = {
90 0, ~_(7), ~_(6), ~_(5), ~_(4), ~_(3), ~_(2), ~_(1),
93 if (clib_arch_is_big_endian)
94 return x & masks_big_endian[n];
96 return x & masks_little_endian[n];
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.
106 * However the invalid Bytes are discarded within zap64(), whicj is why
107 * this can be silenced safely.
109 static inline u64 __attribute__ ((no_sanitize_address))
110 hash_memory64 (void *p, word n_bytes, u64 state)
115 a = b = 0x9e3779b97f4a7c13LL;
119 while (n >= 3 * sizeof (u64))
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);
130 switch (n / sizeof (u64))
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;
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));
146 if (n % sizeof (u64))
147 a += zap64 (clib_mem_unaligned (q + 0, u64), n % sizeof (u64));
151 hash_mix64 (a, b, c);
156 #else /* if uword_bits == 64 */
159 zap32 (u32 x, word n)
161 #define _(n) (((u32) 1 << (u32) (8*(n))) - (u32) 1)
162 static u32 masks_little_endian[] = {
165 static u32 masks_big_endian[] = {
166 0, ~_(3), ~_(2), ~_(1),
169 if (clib_arch_is_big_endian)
170 return x & masks_big_endian[n];
172 return x & masks_little_endian[n];
176 hash_memory32 (void *p, word n_bytes, u32 state)
185 while (n >= 3 * sizeof (u32))
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);
196 switch (n / sizeof (u32))
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;
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));
212 if (n % sizeof (u32))
213 a += zap32 (clib_mem_unaligned (q + 0, u32), n % sizeof (u32));
217 hash_mix32 (a, b, c);
224 hash_memory (void *p, word n_bytes, uword state)
229 return hash_memory64 (q, n_bytes, state);
231 return hash_memory32 (q, n_bytes, state);
241 a = b = 0x9e3779b97f4a7c13LL;
244 hash_mix64 (a, b, c);
256 hash_mix32 (a, b, c);
261 /* Call sum function. Hash code will be sum function value
262 modulo the prime length of the hash table. */
264 key_sum (hash_t * h, uword key)
267 switch (pointer_to_uword ((void *) h->key_sum))
270 sum = hash_uword (key);
273 case KEY_FUNC_POINTER_UWORD:
274 sum = hash_uword (*uword_to_pointer (key, uword *));
277 case KEY_FUNC_POINTER_U32:
278 sum = hash_uword (*uword_to_pointer (key, u32 *));
281 case KEY_FUNC_STRING:
282 sum = string_key_sum (h, key);
286 sum = h->key_sum (h, key);
294 key_equal1 (hash_t * h, uword key1, uword key2, uword e)
296 switch (pointer_to_uword ((void *) h->key_equal))
301 case KEY_FUNC_POINTER_UWORD:
303 *uword_to_pointer (key1, uword *) == *uword_to_pointer (key2,
307 case KEY_FUNC_POINTER_U32:
308 e = *uword_to_pointer (key1, u32 *) == *uword_to_pointer (key2, u32 *);
311 case KEY_FUNC_STRING:
312 e = string_key_equal (h, key1, key2);
316 e = h->key_equal (h, key1, key2);
322 /* Compares two keys: returns 1 if equal, 0 if not. */
324 key_equal (hash_t * h, uword key1, uword key2)
326 uword e = key1 == key2;
327 if (CLIB_DEBUG > 0 && key1 == key2)
328 ASSERT (key_equal1 (h, key1, key2, e));
330 e = key_equal1 (h, key1, key2, e);
334 static hash_pair_union_t *
335 get_indirect (void *v, hash_pair_indirect_t * pi, uword key)
337 hash_t *h = hash_header (v);
338 hash_pair_t *p0, *p1;
341 if (h->log2_pair_size > 0)
342 p1 = hash_forward (h, p0, indirect_pair_get_len (pi));
348 if (key_equal (h, p0->key, key))
349 return (hash_pair_union_t *) p0;
350 p0 = hash_forward1 (h, p0);
353 return (hash_pair_union_t *) 0;
356 static hash_pair_union_t *
357 set_indirect_is_user (void *v, uword i, hash_pair_union_t * p, uword key)
359 hash_t *h = hash_header (v);
361 hash_pair_indirect_t *pi = &p->indirect;
362 uword log2_bytes = 0;
364 if (h->log2_pair_size == 0)
365 q = vec_new (hash_pair_t, 2);
368 log2_bytes = 1 + hash_pair_log2_bytes (h);
369 q = clib_mem_alloc (1ULL << log2_bytes);
371 clib_memcpy (q, &p->direct, hash_pair_bytes (h));
374 if (h->log2_pair_size > 0)
375 indirect_pair_set (pi, log2_bytes, 2);
377 set_is_user (v, i, 0);
379 /* First element is used by existing pair, second will be used by caller. */
380 q = hash_forward1 (h, q);
383 return (hash_pair_union_t *) q;
386 static hash_pair_union_t *
387 set_indirect (void *v, hash_pair_indirect_t * pi, uword key,
390 hash_t *h = hash_header (v);
391 hash_pair_t *new_pair;
392 hash_pair_union_t *q;
394 q = get_indirect (v, pi, key);
401 if (h->log2_pair_size == 0)
402 vec_add2 (pi->pairs, new_pair, 1);
405 uword len, new_len, log2_bytes;
407 len = indirect_pair_get_len (pi);
408 log2_bytes = indirect_pair_get_log2_bytes (pi);
411 if (new_len * hash_pair_bytes (h) > (1ULL << log2_bytes))
413 pi->pairs = clib_mem_realloc (pi->pairs,
414 1ULL << (log2_bytes + 1),
419 indirect_pair_set (pi, log2_bytes, new_len);
420 new_pair = pi->pairs + (len << h->log2_pair_size);
423 init_pair (h, new_pair);
425 return (hash_pair_union_t *) new_pair;
429 unset_indirect (void *v, uword i, hash_pair_t * q)
431 hash_t *h = hash_header (v);
432 hash_pair_union_t *p = get_pair (v, i);
434 hash_pair_indirect_t *pi = &p->indirect;
437 is_vec = h->log2_pair_size == 0;
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);
444 /* We have two or fewer pairs and we are delete one pair.
445 Make indirect pointer direct and free indirect memory. */
448 hash_pair_t *r = pi->pairs;
452 clib_memcpy (p, q == r ? hash_forward1 (h, r) : r,
453 hash_pair_bytes (h));
454 set_is_user (v, i, 1);
457 zero_pair (h, &p->direct);
466 /* If deleting a pair we need to keep non-null pairs together. */
468 clib_memcpy (q, e, hash_pair_bytes (h));
472 _vec_len (pi->pairs) -= 1;
474 indirect_pair_set (pi, indirect_pair_get_log2_bytes (pi), len - 1);
486 lookup (void *v, uword key, enum lookup_opcode op,
487 void *new_value, void *old_value)
489 hash_t *h = hash_header (v);
490 hash_pair_union_t *p = 0;
497 i = key_sum (h, key) & (_vec_len (v) - 1);
500 if (hash_is_user (v, i))
502 found_key = key_equal (h, p->direct.key, key);
507 set_is_user (v, i, 0);
509 clib_memcpy (old_value, p->direct.value,
510 hash_value_bytes (h));
511 zero_pair (h, &p->direct);
517 p = set_indirect_is_user (v, i, p, key);
524 hash_pair_indirect_t *pi = &p->indirect;
531 set_is_user (v, i, 1);
534 p = set_indirect (v, pi, key, &found_key);
538 p = get_indirect (v, pi, key);
540 if (found_key && op == UNSET)
543 clib_memcpy (old_value, &p->direct.value,
544 hash_value_bytes (h));
546 unset_indirect (v, i, &p->direct);
548 /* Nullify p (since it's just been deleted).
549 Otherwise we might be tempted to play with it. */
555 if (op == SET && p != 0)
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));
564 h->elts += !found_key;
566 h->elts -= found_key;
571 /* Fetch value of key. */
573 _hash_get (void *v, uword key)
575 hash_t *h = hash_header (v);
578 /* Don't even search table if its empty. */
579 if (!v || h->elts == 0)
582 p = lookup (v, key, GET, 0, 0);
585 if (h->log2_pair_size == 0)
592 _hash_get_pair (void *v, uword key)
594 return lookup (v, key, GET, 0, 0);
598 hash_next (void *v, hash_next_t * hn)
600 hash_t *h = hash_header (v);
605 if (hn->i == 0 && hn->j == 0)
610 /* Prevent others from re-sizing hash table. */
612 (HASH_FLAG_NO_AUTO_GROW
613 | HASH_FLAG_NO_AUTO_SHRINK | HASH_FLAG_HASH_NEXT_IN_PROGRESS);
615 else if (hn->i >= hash_capacity (v))
619 memset (hn, 0, sizeof (hn[0]));
623 p = hash_forward (h, v, hn->i);
624 if (hash_is_user (v, hn->i))
631 hash_pair_indirect_t *pi = (void *) p;
634 if (h->log2_pair_size > 0)
635 n = indirect_pair_get_len (pi);
637 n = vec_len (pi->pairs);
645 return hash_forward (h, pi->pairs, hn->j++);
650 /* Remove key from table. */
652 _hash_unset (void *v, uword key, void *old_value)
659 (void) lookup (v, key, UNSET, 0, old_value);
662 if (!(h->flags & HASH_FLAG_NO_AUTO_SHRINK))
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);
673 _hash_create (uword elts, hash_t * h_user)
676 uword log2_pair_size;
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);
686 log2_pair_size = h_user->log2_pair_size;
691 (elts << log2_pair_size) * sizeof (hash_pair_t),
694 (elts / BITS (h->is_user[0])) * sizeof (h->is_user[0]),
695 /* alignment */ sizeof (hash_pair_t));
701 h->log2_pair_size = log2_pair_size;
704 /* Default flags to never shrinking hash tables.
705 Shrinking tables can cause "jackpot" cases. */
707 h->flags = HASH_FLAG_NO_AUTO_SHRINK;
711 h->format_pair = hash_format_pair_default;
712 h->format_pair_arg = 0;
721 hash_t *h = hash_header (v);
722 hash_pair_union_t *p;
728 /* We zero all freed memory in case user would be tempted to use it. */
729 for (i = 0; i < hash_capacity (v); i++)
731 if (hash_is_user (v, i))
734 if (h->log2_pair_size == 0)
735 vec_free (p->indirect.pairs);
736 else if (p->indirect.pairs)
737 clib_mem_free (p->indirect.pairs);
746 hash_resize_internal (void *old, uword new_size, uword free_old)
754 hash_t *h = old ? hash_header (old) : 0;
755 new = _hash_create (new_size, h);
757 hash_foreach_pair (p, old, {
758 new = _hash_set3 (new, p->key, &p->value[0], 0);
769 hash_resize (void *old, uword new_size)
771 return hash_resize_internal (old, new_size, 1);
777 return hash_resize_internal (old, vec_len (old), 0);
781 _hash_set3 (void *v, uword key, void *value, void *old_value)
786 v = hash_create (0, sizeof (uword));
789 (void) lookup (v, key, SET, value, old_value);
791 if (!(h->flags & HASH_FLAG_NO_AUTO_GROW))
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));
802 vec_key_sum (hash_t * h, uword key)
804 void *v = uword_to_pointer (key, void *);
805 return hash_memory (v, vec_len (v) * h->user, 0);
809 vec_key_equal (hash_t * h, uword key1, uword key2)
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);
819 vec_key_format_pair (u8 * s, va_list * args)
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 *);
831 s = format (s, "%v", u);
837 for (i = 0; i < vec_len (w); i++)
838 s = format (s, "0x%x, ", w[i]);
845 for (i = 0; i < vec_len (w); i++)
846 s = format (s, "0x%x, ", w[i]);
853 for (i = 0; i < vec_len (w); i++)
854 s = format (s, "0x%Lx, ", w[i]);
859 s = format (s, "0x%U", format_hex_bytes, u, vec_len (u) * h->user);
863 if (hash_value_bytes (h) > 0)
864 s = format (s, " -> 0x%wx", p->value[0]);
870 mem_key_sum (hash_t * h, uword key)
872 uword *v = uword_to_pointer (key, void *);
873 return hash_memory (v, h->user, 0);
877 mem_key_equal (hash_t * h, uword key1, uword key2)
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);
885 string_key_sum (hash_t * h, uword key)
887 char *v = uword_to_pointer (key, char *);
888 return hash_memory (v, strlen (v), 0);
892 string_key_equal (hash_t * h, uword key1, uword key2)
894 void *v1 = uword_to_pointer (key1, void *);
895 void *v2 = uword_to_pointer (key2, void *);
896 return v1 && v2 && 0 == strcmp (v1, v2);
900 string_key_format_pair (u8 * s, va_list * args)
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 *);
908 s = format (s, "%s", u);
910 if (hash_value_bytes (h) > 0)
912 format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
913 hash_value_bytes (h));
919 hash_format_pair_default (u8 * s, va_list * args)
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);
926 s = format (s, "0x%08x", p->key);
927 if (hash_value_bytes (h) > 0)
929 format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
930 hash_value_bytes (h));
938 hash_t *h = hash_header (v);
943 bytes = vec_capacity (v, hash_header_bytes (v));
945 for (i = 0; i < hash_capacity (v); i++)
947 if (!hash_is_user (v, i))
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);
953 bytes += vec_capacity (p->indirect.pairs, 0);
960 format_hash (u8 * s, va_list * va)
962 void *v = va_arg (*va, void *);
963 int verbose = va_arg (*va, int);
965 hash_t *h = hash_header (v);
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));
972 uword *occupancy = 0;
974 /* Count number of buckets with each occupancy. */
975 for (i = 0; i < hash_capacity (v); i++)
979 if (hash_is_user (v, i))
985 hash_pair_union_t *p = get_pair (v, i);
986 if (h->log2_pair_size > 0)
987 j = indirect_pair_get_len (&p->indirect);
989 j = vec_len (p->indirect.pairs);
992 vec_validate (occupancy, j);
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' : ' ');
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' : ' ');
1007 vec_free (occupancy);
1013 hash_foreach_pair (p, v, {
1014 s = format (s, " %U\n", h->format_pair, h->format_pair_arg, v, p);
1023 unformat_hash_string_internal (unformat_input_t * input,
1024 va_list * va, int is_vec)
1026 uword *hash = va_arg (*va, uword *);
1027 int *result = va_arg (*va, int *);
1031 if (!unformat (input, is_vec ? "%v%_" : "%s%_", &string))
1034 p = hash_get_mem (hash, string);
1043 unformat_hash_vec_string (unformat_input_t * input, va_list * va)
1045 return unformat_hash_string_internal (input, va, /* is_vec */ 1);
1049 unformat_hash_string (unformat_input_t * input, va_list * va)
1051 return unformat_hash_string_internal (input, va, /* is_vec */ 0);
1055 hash_validate (void *v)
1057 hash_t *h = hash_header (v);
1060 clib_error_t *error = 0;
1062 #define CHECK(x) if ((error = ERROR_ASSERT (x))) goto done;
1064 for (i = 0; i < hash_capacity (v); i++)
1066 hash_pair_union_t *pu = get_pair (v, i);
1068 if (hash_is_user (v, i))
1070 CHECK (pu->direct.key != 0);
1071 vec_add1 (keys, pu->direct.key);
1076 hash_pair_indirect_t *pi = &pu->indirect;
1079 n = h->log2_pair_size > 0
1080 ? indirect_pair_get_len (pi) : vec_len (pi->pairs);
1082 for (p = pi->pairs; n-- > 0; p = hash_forward1 (h, p))
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);
1092 CHECK (vec_len (keys) == h->elts);
1100 * fd.io coding-style-patch-verification: ON
1103 * eval: (c-set-style "gnu")