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 clib_memset (p, 0, hash_pair_bytes (h));
50 init_pair (hash_t * h, hash_pair_t * p)
52 clib_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 = mem_key_sum (h, key);
290 sum = h->key_sum (h, key);
298 key_equal1 (hash_t * h, uword key1, uword key2, uword e)
300 switch (pointer_to_uword ((void *) h->key_equal))
305 case KEY_FUNC_POINTER_UWORD:
307 *uword_to_pointer (key1, uword *) == *uword_to_pointer (key2,
311 case KEY_FUNC_POINTER_U32:
312 e = *uword_to_pointer (key1, u32 *) == *uword_to_pointer (key2, u32 *);
315 case KEY_FUNC_STRING:
316 e = string_key_equal (h, key1, key2);
320 e = mem_key_equal (h, key1, key2);
324 e = h->key_equal (h, key1, key2);
330 /* Compares two keys: returns 1 if equal, 0 if not. */
332 key_equal (hash_t * h, uword key1, uword key2)
334 uword e = key1 == key2;
335 if (CLIB_DEBUG > 0 && key1 == key2)
336 ASSERT (key_equal1 (h, key1, key2, e));
338 e = key_equal1 (h, key1, key2, e);
342 static hash_pair_union_t *
343 get_indirect (void *v, hash_pair_indirect_t * pi, uword key)
345 hash_t *h = hash_header (v);
346 hash_pair_t *p0, *p1;
349 if (h->log2_pair_size > 0)
350 p1 = hash_forward (h, p0, indirect_pair_get_len (pi));
356 if (key_equal (h, p0->key, key))
357 return (hash_pair_union_t *) p0;
358 p0 = hash_forward1 (h, p0);
361 return (hash_pair_union_t *) 0;
364 static hash_pair_union_t *
365 set_indirect_is_user (void *v, uword i, hash_pair_union_t * p, uword key)
367 hash_t *h = hash_header (v);
369 hash_pair_indirect_t *pi = &p->indirect;
370 uword log2_bytes = 0;
372 if (h->log2_pair_size == 0)
373 q = vec_new (hash_pair_t, 2);
376 log2_bytes = 1 + hash_pair_log2_bytes (h);
377 q = clib_mem_alloc (1ULL << log2_bytes);
379 clib_memcpy_fast (q, &p->direct, hash_pair_bytes (h));
382 if (h->log2_pair_size > 0)
383 indirect_pair_set (pi, log2_bytes, 2);
385 set_is_user (v, i, 0);
387 /* First element is used by existing pair, second will be used by caller. */
388 q = hash_forward1 (h, q);
391 return (hash_pair_union_t *) q;
394 static hash_pair_union_t *
395 set_indirect (void *v, hash_pair_indirect_t * pi, uword key,
398 hash_t *h = hash_header (v);
399 hash_pair_t *new_pair;
400 hash_pair_union_t *q;
402 q = get_indirect (v, pi, key);
409 if (h->log2_pair_size == 0)
410 vec_add2 (pi->pairs, new_pair, 1);
413 uword len, new_len, log2_bytes;
415 len = indirect_pair_get_len (pi);
416 log2_bytes = indirect_pair_get_log2_bytes (pi);
419 if (new_len * hash_pair_bytes (h) > (1ULL << log2_bytes))
421 pi->pairs = clib_mem_realloc (pi->pairs,
422 1ULL << (log2_bytes + 1),
427 indirect_pair_set (pi, log2_bytes, new_len);
428 new_pair = pi->pairs + (len << h->log2_pair_size);
431 init_pair (h, new_pair);
433 return (hash_pair_union_t *) new_pair;
437 unset_indirect (void *v, uword i, hash_pair_t * q)
439 hash_t *h = hash_header (v);
440 hash_pair_union_t *p = get_pair (v, i);
442 hash_pair_indirect_t *pi = &p->indirect;
445 is_vec = h->log2_pair_size == 0;
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);
452 /* We have two or fewer pairs and we are delete one pair.
453 Make indirect pointer direct and free indirect memory. */
456 hash_pair_t *r = pi->pairs;
460 clib_memcpy_fast (p, q == r ? hash_forward1 (h, r) : r,
461 hash_pair_bytes (h));
462 set_is_user (v, i, 1);
465 zero_pair (h, &p->direct);
474 /* If deleting a pair we need to keep non-null pairs together. */
476 clib_memcpy_fast (q, e, hash_pair_bytes (h));
480 _vec_len (pi->pairs) -= 1;
482 indirect_pair_set (pi, indirect_pair_get_log2_bytes (pi), len - 1);
494 lookup (void *v, uword key, enum lookup_opcode op,
495 void *new_value, void *old_value)
497 hash_t *h = hash_header (v);
498 hash_pair_union_t *p = 0;
505 i = key_sum (h, key) & (_vec_len (v) - 1);
508 if (hash_is_user (v, i))
510 found_key = key_equal (h, p->direct.key, key);
515 set_is_user (v, i, 0);
517 clib_memcpy_fast (old_value, p->direct.value,
518 hash_value_bytes (h));
519 zero_pair (h, &p->direct);
525 p = set_indirect_is_user (v, i, p, key);
532 hash_pair_indirect_t *pi = &p->indirect;
539 set_is_user (v, i, 1);
542 p = set_indirect (v, pi, key, &found_key);
546 p = get_indirect (v, pi, key);
548 if (found_key && op == UNSET)
551 clib_memcpy_fast (old_value, &p->direct.value,
552 hash_value_bytes (h));
554 unset_indirect (v, i, &p->direct);
556 /* Nullify p (since it's just been deleted).
557 Otherwise we might be tempted to play with it. */
563 if (op == SET && p != 0)
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));
572 h->elts += !found_key;
574 h->elts -= found_key;
579 /* Fetch value of key. */
581 _hash_get (void *v, uword key)
583 hash_t *h = hash_header (v);
586 /* Don't even search table if its empty. */
587 if (!v || h->elts == 0)
590 p = lookup (v, key, GET, 0, 0);
593 if (h->log2_pair_size == 0)
600 _hash_get_pair (void *v, uword key)
602 return lookup (v, key, GET, 0, 0);
606 hash_next (void *v, hash_next_t * hn)
608 hash_t *h = hash_header (v);
613 if (hn->i == 0 && hn->j == 0)
618 /* Prevent others from re-sizing hash table. */
620 (HASH_FLAG_NO_AUTO_GROW
621 | HASH_FLAG_NO_AUTO_SHRINK | HASH_FLAG_HASH_NEXT_IN_PROGRESS);
623 else if (hn->i >= hash_capacity (v))
627 clib_memset (hn, 0, sizeof (hn[0]));
631 p = hash_forward (h, v, hn->i);
632 if (hash_is_user (v, hn->i))
639 hash_pair_indirect_t *pi = (void *) p;
642 if (h->log2_pair_size > 0)
643 n = indirect_pair_get_len (pi);
645 n = vec_len (pi->pairs);
653 return hash_forward (h, pi->pairs, hn->j++);
658 /* Remove key from table. */
660 _hash_unset (void *v, uword key, void *old_value)
667 (void) lookup (v, key, UNSET, 0, old_value);
670 if (!(h->flags & HASH_FLAG_NO_AUTO_SHRINK))
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);
681 _hash_create (uword elts, hash_t * h_user)
684 uword log2_pair_size;
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);
694 log2_pair_size = h_user->log2_pair_size;
696 v = _vec_resize ((void *) 0,
699 (elts << log2_pair_size) * sizeof (hash_pair_t),
702 (elts / BITS (h->is_user[0])) * sizeof (h->is_user[0]),
703 /* alignment */ sizeof (hash_pair_t));
709 h->log2_pair_size = log2_pair_size;
712 /* Default flags to never shrinking hash tables.
713 Shrinking tables can cause "jackpot" cases. */
715 h->flags = HASH_FLAG_NO_AUTO_SHRINK;
719 h->format_pair = hash_format_pair_default;
720 h->format_pair_arg = 0;
729 hash_t *h = hash_header (v);
730 hash_pair_union_t *p;
736 /* We zero all freed memory in case user would be tempted to use it. */
737 for (i = 0; i < hash_capacity (v); i++)
739 if (hash_is_user (v, i))
742 if (h->log2_pair_size == 0)
743 vec_free (p->indirect.pairs);
744 else if (p->indirect.pairs)
745 clib_mem_free (p->indirect.pairs);
754 hash_resize_internal (void *old, uword new_size, uword free_old)
762 hash_t *h = old ? hash_header (old) : 0;
763 new = _hash_create (new_size, h);
765 hash_foreach_pair (p, old, {
766 new = _hash_set3 (new, p->key, &p->value[0], 0);
777 hash_resize (void *old, uword new_size)
779 return hash_resize_internal (old, new_size, 1);
785 return hash_resize_internal (old, vec_len (old), 0);
789 _hash_set3 (void *v, uword key, void *value, void *old_value)
794 v = hash_create (0, sizeof (uword));
797 (void) lookup (v, key, SET, value, old_value);
799 if (!(h->flags & HASH_FLAG_NO_AUTO_GROW))
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));
810 vec_key_sum (hash_t * h, uword key)
812 void *v = uword_to_pointer (key, void *);
813 return hash_memory (v, vec_len (v) * h->user, 0);
817 vec_key_equal (hash_t * h, uword key1, uword key2)
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);
827 vec_key_format_pair (u8 * s, va_list * args)
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 *);
839 s = format (s, "%v", u);
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%x, ", w[i]);
861 for (i = 0; i < vec_len (w); i++)
862 s = format (s, "0x%Lx, ", w[i]);
867 s = format (s, "0x%U", format_hex_bytes, u, vec_len (u) * h->user);
871 if (hash_value_bytes (h) > 0)
872 s = format (s, " -> 0x%wx", p->value[0]);
878 mem_key_sum (hash_t * h, uword key)
880 uword *v = uword_to_pointer (key, void *);
881 return hash_memory (v, h->user, 0);
885 mem_key_equal (hash_t * h, uword key1, uword key2)
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);
893 string_key_sum (hash_t * h, uword key)
895 char *v = uword_to_pointer (key, char *);
896 return hash_memory (v, strlen (v), 0);
900 string_key_equal (hash_t * h, uword key1, uword key2)
902 void *v1 = uword_to_pointer (key1, void *);
903 void *v2 = uword_to_pointer (key2, void *);
904 return v1 && v2 && 0 == strcmp (v1, v2);
908 string_key_format_pair (u8 * s, va_list * args)
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 *);
916 s = format (s, "%s", u);
918 if (hash_value_bytes (h) > 0)
920 format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
921 hash_value_bytes (h));
927 hash_format_pair_default (u8 * s, va_list * args)
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);
934 s = format (s, "0x%08x", p->key);
935 if (hash_value_bytes (h) > 0)
937 format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
938 hash_value_bytes (h));
946 hash_t *h = hash_header (v);
951 bytes = vec_capacity (v, hash_header_bytes (v));
953 for (i = 0; i < hash_capacity (v); i++)
955 if (!hash_is_user (v, i))
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);
961 bytes += vec_capacity (p->indirect.pairs, 0);
968 format_hash (u8 * s, va_list * va)
970 void *v = va_arg (*va, void *);
971 int verbose = va_arg (*va, int);
973 hash_t *h = hash_header (v);
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));
980 uword *occupancy = 0;
982 /* Count number of buckets with each occupancy. */
983 for (i = 0; i < hash_capacity (v); i++)
987 if (hash_is_user (v, i))
993 hash_pair_union_t *p = get_pair (v, i);
994 if (h->log2_pair_size > 0)
995 j = indirect_pair_get_len (&p->indirect);
997 j = vec_len (p->indirect.pairs);
1000 vec_validate (occupancy, j);
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' : ' ');
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' : ' ');
1015 vec_free (occupancy);
1021 hash_foreach_pair (p, v, {
1022 s = format (s, " %U\n", h->format_pair, h->format_pair_arg, v, p);
1031 unformat_hash_string_internal (unformat_input_t * input,
1032 va_list * va, int is_vec)
1034 uword *hash = va_arg (*va, uword *);
1035 int *result = va_arg (*va, int *);
1039 if (!unformat (input, is_vec ? "%v%_" : "%s%_", &string))
1042 p = hash_get_mem (hash, string);
1051 unformat_hash_vec_string (unformat_input_t * input, va_list * va)
1053 return unformat_hash_string_internal (input, va, /* is_vec */ 1);
1057 unformat_hash_string (unformat_input_t * input, va_list * va)
1059 return unformat_hash_string_internal (input, va, /* is_vec */ 0);
1063 hash_validate (void *v)
1065 hash_t *h = hash_header (v);
1068 clib_error_t *error = 0;
1070 #define CHECK(x) if ((error = ERROR_ASSERT (x))) goto done;
1072 for (i = 0; i < hash_capacity (v); i++)
1074 hash_pair_union_t *pu = get_pair (v, i);
1076 if (hash_is_user (v, i))
1078 CHECK (pu->direct.key != 0);
1079 vec_add1 (keys, pu->direct.key);
1084 hash_pair_indirect_t *pi = &pu->indirect;
1087 n = h->log2_pair_size > 0
1088 ? indirect_pair_get_len (pi) : vec_len (pi->pairs);
1090 for (p = pi->pairs; n-- > 0; p = hash_forward1 (h, p))
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);
1100 CHECK (vec_len (keys) == h->elts);
1108 * fd.io coding-style-patch-verification: ON
1111 * eval: (c-set-style "gnu")