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 */
43 always_inline void zero_pair (hash_t * h, hash_pair_t * p)
44 { memset (p, 0, hash_pair_bytes (h)); }
46 always_inline void init_pair (hash_t * h, hash_pair_t * p)
47 { memset (p->value, ~0, hash_value_bytes (h)); }
49 always_inline hash_pair_union_t *
50 get_pair (void * v, uword i)
52 hash_t * h = hash_header (v);
54 ASSERT (i < vec_len (v));
56 p += i << h->log2_pair_size;
57 return (hash_pair_union_t *) p;
60 always_inline void set_is_user (void * v, uword i, uword is_user)
62 hash_t * h = hash_header (v);
63 uword i0 = i / BITS(h->is_user[0]);
64 uword i1 = (uword) 1 << (i % BITS(h->is_user[0]));
68 h->is_user[i0] &= ~i1;
71 static u8 * hash_format_pair_default (u8 * s, va_list * args);
75 static inline u64 zap64 (u64 x, word n)
77 #define _(n) (((u64) 1 << (u64) (8*(n))) - (u64) 1)
78 static u64 masks_little_endian[] = {
79 0, _(1), _(2), _(3), _(4), _(5), _(6), _(7),
81 static u64 masks_big_endian[] = {
82 0, ~_(7), ~_(6), ~_(5), ~_(4), ~_(3), ~_(2), ~_(1),
85 if (clib_arch_is_big_endian)
86 return x & masks_big_endian[n];
88 return x & masks_little_endian[n];
91 static inline u64 hash_memory64 (void * p, word n_bytes, u64 state)
96 a = b = 0x9e3779b97f4a7c13LL;
100 while (n >= 3 * sizeof(u64))
102 a += clib_mem_unaligned (q + 0, u64);
103 b += clib_mem_unaligned (q + 1, u64);
104 c += clib_mem_unaligned (q + 2, u64);
105 hash_mix64 (a, b, c);
111 switch (n / sizeof (u64))
114 a += clib_mem_unaligned (q + 0, u64);
115 b += clib_mem_unaligned (q + 1, u64);
116 if (n % sizeof (u64))
117 c += zap64 (clib_mem_unaligned (q + 2, u64),
118 n % sizeof (u64)) << 8;
122 a += clib_mem_unaligned (q + 0, u64);
123 if (n % sizeof (u64))
124 b += zap64 (clib_mem_unaligned (q + 1, u64),
129 if (n % sizeof (u64))
130 a += zap64 (clib_mem_unaligned (q + 0, u64),
135 hash_mix64 (a, b, c);
140 #else /* if uword_bits == 64 */
142 static inline u32 zap32 (u32 x, word n)
144 #define _(n) (((u32) 1 << (u32) (8*(n))) - (u32) 1)
145 static u32 masks_little_endian[] = {
148 static u32 masks_big_endian[] = {
149 0, ~_(3), ~_(2), ~_(1),
152 if (clib_arch_is_big_endian)
153 return x & masks_big_endian[n];
155 return x & masks_little_endian[n];
158 static inline u32 hash_memory32 (void * p, word n_bytes, u32 state)
167 while (n >= 3 * sizeof(u32))
169 a += clib_mem_unaligned (q + 0, u32);
170 b += clib_mem_unaligned (q + 1, u32);
171 c += clib_mem_unaligned (q + 2, u32);
172 hash_mix32 (a, b, c);
178 switch (n / sizeof (u32))
181 a += clib_mem_unaligned (q + 0, u32);
182 b += clib_mem_unaligned (q + 1, u32);
183 if (n % sizeof (u32))
184 c += zap32 (clib_mem_unaligned (q + 2, u32),
185 n % sizeof (u32)) << 8;
189 a += clib_mem_unaligned (q + 0, u32);
190 if (n % sizeof (u32))
191 b += zap32 (clib_mem_unaligned (q + 1, u32),
196 if (n % sizeof (u32))
197 a += zap32 (clib_mem_unaligned (q + 0, u32),
202 hash_mix32 (a, b, c);
208 uword hash_memory (void * p, word n_bytes, uword state)
213 return hash_memory64 (q, n_bytes, state);
215 return hash_memory32 (q, n_bytes, state);
220 always_inline uword hash_uword (uword x)
224 a = b = 0x9e3779b97f4a7c13LL;
227 hash_mix64 (a, b, c);
231 always_inline uword hash_uword (uword x)
238 hash_mix32 (a, b, c);
243 /* Call sum function. Hash code will be sum function value
244 modulo the prime length of the hash table. */
245 always_inline uword key_sum (hash_t * h, uword key)
248 switch (pointer_to_uword ((void *) h->key_sum))
251 sum = hash_uword (key);
254 case KEY_FUNC_POINTER_UWORD:
255 sum = hash_uword (* uword_to_pointer (key, uword *));
258 case KEY_FUNC_POINTER_U32:
259 sum = hash_uword (* uword_to_pointer (key, u32 *));
262 case KEY_FUNC_STRING:
263 sum = string_key_sum (h, key);
267 sum = h->key_sum (h, key);
274 always_inline uword key_equal1 (hash_t * h, uword key1, uword key2, uword e)
276 switch (pointer_to_uword ((void *) h->key_equal))
281 case KEY_FUNC_POINTER_UWORD:
282 e = * uword_to_pointer (key1, uword *) == * uword_to_pointer (key2, uword *);
285 case KEY_FUNC_POINTER_U32:
286 e = * uword_to_pointer (key1, u32 *) == * uword_to_pointer (key2, u32 *);
289 case KEY_FUNC_STRING:
290 e = string_key_equal (h, key1, key2);
294 e = h->key_equal (h, key1, key2);
300 /* Compares two keys: returns 1 if equal, 0 if not. */
301 always_inline uword key_equal (hash_t * h, uword key1, uword key2)
303 uword e = key1 == key2;
304 if (CLIB_DEBUG > 0 && key1 == key2)
305 ASSERT (key_equal1 (h, key1, key2, e));
307 e = key_equal1 (h, key1, key2, e);
311 static hash_pair_union_t *
312 get_indirect (void * v, hash_pair_indirect_t * pi, uword key)
314 hash_t * h = hash_header (v);
315 hash_pair_t * p0, * p1;
318 if (h->log2_pair_size > 0)
319 p1 = hash_forward (h, p0, indirect_pair_get_len (pi));
325 if (key_equal (h, p0->key, key))
326 return (hash_pair_union_t *) p0;
327 p0 = hash_forward1 (h, p0);
330 return (hash_pair_union_t *) 0;
333 static hash_pair_union_t *
334 set_indirect_is_user (void * v,
336 hash_pair_union_t * p,
339 hash_t * h = hash_header (v);
341 hash_pair_indirect_t * pi = &p->indirect;
342 uword log2_bytes = 0;
344 if (h->log2_pair_size == 0)
345 q = vec_new (hash_pair_t, 2);
348 log2_bytes = 1 + hash_pair_log2_bytes (h);
349 q = clib_mem_alloc (1ULL << log2_bytes);
351 clib_memcpy (q, &p->direct, hash_pair_bytes (h));
354 if (h->log2_pair_size > 0)
355 indirect_pair_set (pi, log2_bytes, 2);
357 set_is_user (v, i, 0);
359 /* First element is used by existing pair, second will be used by caller. */
360 q = hash_forward1 (h, q);
363 return (hash_pair_union_t *) q;
366 static hash_pair_union_t *
367 set_indirect (void * v, hash_pair_indirect_t * pi, uword key,
370 hash_t * h = hash_header (v);
371 hash_pair_t * new_pair;
372 hash_pair_union_t * q;
374 q = get_indirect (v, pi, key);
381 if (h->log2_pair_size == 0)
382 vec_add2 (pi->pairs, new_pair, 1);
385 uword len, new_len, log2_bytes;
387 len = indirect_pair_get_len (pi);
388 log2_bytes = indirect_pair_get_log2_bytes (pi);
391 if (new_len * hash_pair_bytes (h) > (1ULL << log2_bytes))
393 pi->pairs = clib_mem_realloc (pi->pairs,
394 1 << (log2_bytes + 1),
399 indirect_pair_set (pi, log2_bytes, new_len);
400 new_pair = pi->pairs + (len << h->log2_pair_size);
403 init_pair (h, new_pair);
405 return (hash_pair_union_t *) new_pair;
408 static void unset_indirect (void * v, uword i, hash_pair_t * q)
410 hash_t * h = hash_header (v);
411 hash_pair_union_t * p = get_pair (v, i);
413 hash_pair_indirect_t * pi = &p->indirect;
416 is_vec = h->log2_pair_size == 0;
418 ASSERT (! hash_is_user (v, i));
419 len = is_vec ? vec_len (pi->pairs) : indirect_pair_get_len (pi);
420 e = hash_forward (h, pi->pairs, len - 1);
421 ASSERT (q >= pi->pairs && q <= e);
423 /* We have two or fewer pairs and we are delete one pair.
424 Make indirect pointer direct and free indirect memory. */
427 hash_pair_t * r = pi->pairs;
431 clib_memcpy (p, q == r ? hash_forward1 (h, r) : r, hash_pair_bytes (h));
432 set_is_user (v, i, 1);
435 zero_pair (h, &p->direct);
444 /* If deleting a pair we need to keep non-null pairs together. */
446 clib_memcpy (q, e, hash_pair_bytes (h));
450 _vec_len (pi->pairs) -= 1;
452 indirect_pair_set (pi,
453 indirect_pair_get_log2_bytes (pi),
464 static hash_pair_t * lookup (void * v, uword key, enum lookup_opcode op,
465 void * new_value, void * old_value)
467 hash_t * h = hash_header (v);
468 hash_pair_union_t * p = 0;
475 i = key_sum (h, key) & (_vec_len (v) - 1);
478 if (hash_is_user (v, i))
480 found_key = key_equal (h, p->direct.key, key);
485 set_is_user (v, i, 0);
487 clib_memcpy (old_value, p->direct.value, hash_value_bytes (h));
488 zero_pair (h, &p->direct);
494 p = set_indirect_is_user (v, i, p, key);
501 hash_pair_indirect_t * pi = &p->indirect;
508 set_is_user (v, i, 1);
511 p = set_indirect (v, pi, key, &found_key);
515 p = get_indirect (v, pi, key);
517 if (found_key && op == UNSET)
520 clib_memcpy (old_value, &p->direct.value, hash_value_bytes (h));
522 unset_indirect (v, i, &p->direct);
524 /* Nullify p (since it's just been deleted).
525 Otherwise we might be tempted to play with it. */
531 if (op == SET && p != 0)
533 /* Save away old value for caller. */
534 if (old_value && found_key)
535 clib_memcpy (old_value, &p->direct.value, hash_value_bytes (h));
536 clib_memcpy (&p->direct.value, new_value, hash_value_bytes (h));
540 h->elts += !found_key;
542 h->elts -= found_key;
547 /* Fetch value of key. */
548 uword * _hash_get (void * v, uword key)
550 hash_t * h = hash_header (v);
553 /* Don't even search table if its empty. */
554 if (! v || h->elts == 0)
557 p = lookup (v, key, GET, 0, 0);
560 if (h->log2_pair_size == 0)
566 hash_pair_t * _hash_get_pair (void * v, uword key)
567 { return lookup (v, key, GET, 0, 0); }
569 hash_pair_t * hash_next (void * v, hash_next_t * hn)
571 hash_t * h = hash_header (v);
576 if (hn->i == 0 && hn->j == 0)
581 /* Prevent others from re-sizing hash table. */
583 (HASH_FLAG_NO_AUTO_GROW
584 | HASH_FLAG_NO_AUTO_SHRINK
585 | HASH_FLAG_HASH_NEXT_IN_PROGRESS);
587 else if (hn->i >= hash_capacity (v))
591 memset (hn, 0, sizeof (hn[0]));
595 p = hash_forward (h, v, hn->i);
596 if (hash_is_user (v, hn->i))
603 hash_pair_indirect_t * pi = (void *) p;
606 if (h->log2_pair_size > 0)
607 n = indirect_pair_get_len (pi);
609 n = vec_len (pi->pairs);
617 return hash_forward (h, pi->pairs, hn->j++);
622 /* Remove key from table. */
623 void * _hash_unset (void * v, uword key, void * old_value)
630 (void) lookup (v, key, UNSET, 0, old_value);
633 if (! (h->flags & HASH_FLAG_NO_AUTO_SHRINK))
635 /* Resize when 1/4 full. */
636 if (h->elts > 32 && 4 * (h->elts + 1) < vec_len (v))
637 v = hash_resize (v, vec_len (v) / 2);
643 void * _hash_create (uword elts, hash_t * h_user)
646 uword log2_pair_size;
649 /* Size of hash is power of 2 >= ELTS and larger than
650 number of bits in is_user bitmap elements. */
651 elts = clib_max (elts, BITS (h->is_user[0]));
652 elts = 1ULL << max_log2 (elts);
656 log2_pair_size = h_user->log2_pair_size;
660 /* data bytes: */ (elts << log2_pair_size) * sizeof (hash_pair_t),
661 /* header bytes: */ sizeof (h[0]) + (elts / BITS (h->is_user[0])) * sizeof (h->is_user[0]),
662 /* alignment */ sizeof (hash_pair_t));
668 h->log2_pair_size = log2_pair_size;
671 /* Default flags to never shrinking hash tables.
672 Shrinking tables can cause "jackpot" cases. */
674 h->flags = HASH_FLAG_NO_AUTO_SHRINK;
676 if (! h->format_pair)
678 h->format_pair = hash_format_pair_default;
679 h->format_pair_arg = 0;
685 void * _hash_free (void * v)
687 hash_t * h = hash_header (v);
688 hash_pair_union_t * p;
694 /* We zero all freed memory in case user would be tempted to use it. */
695 for (i = 0; i < hash_capacity (v); i++)
697 if (hash_is_user (v, i))
700 if (h->log2_pair_size == 0)
701 vec_free (p->indirect.pairs);
702 else if (p->indirect.pairs)
703 clib_mem_free (p->indirect.pairs);
711 static void * hash_resize_internal (void * old, uword new_size, uword free_old)
719 hash_t * h = old ? hash_header (old) : 0;
720 new = _hash_create (new_size, h);
721 hash_foreach_pair (p, old, {
722 new = _hash_set3 (new, p->key, &p->value[0], 0);
731 void * hash_resize (void * old, uword new_size)
732 { return hash_resize_internal (old, new_size, 1); }
734 void * hash_dup (void * old)
735 { return hash_resize_internal (old, vec_len (old), 0); }
737 void * _hash_set3 (void * v, uword key, void * value, void * old_value)
742 v = hash_create (0, sizeof (uword));
745 (void) lookup (v, key, SET, value, old_value);
747 if (! (h->flags & HASH_FLAG_NO_AUTO_GROW))
749 /* Resize when 3/4 full. */
750 if (4 * (h->elts + 1) > 3 * vec_len (v))
751 v = hash_resize (v, 2 * vec_len (v));
757 uword vec_key_sum (hash_t * h, uword key)
759 void * v = uword_to_pointer (key, void *);
760 return hash_memory (v, vec_len (v) * h->user, 0);
763 uword vec_key_equal (hash_t * h, uword key1, uword key2)
765 void * v1 = uword_to_pointer (key1, void *);
766 void * v2 = uword_to_pointer (key2, void *);
767 uword l1 = vec_len (v1);
768 uword l2 = vec_len (v2);
769 return l1 == l2 && 0 == memcmp (v1, v2, l1 * h->user);
772 u8 * vec_key_format_pair (u8 * s, va_list * args)
774 void * CLIB_UNUSED (user_arg) = va_arg (*args, void *);
775 void * v = va_arg (*args, void *);
776 hash_pair_t * p = va_arg (*args, hash_pair_t *);
777 hash_t * h = hash_header (v);
778 void * u = uword_to_pointer (p->key, void *);
783 s = format (s, "%v", u);
789 for (i = 0; i < vec_len (w); i++)
790 s = format (s, "0x%x, ", w[i]);
797 for (i = 0; i < vec_len (w); i++)
798 s = format (s, "0x%x, ", w[i]);
805 for (i = 0; i < vec_len (w); i++)
806 s = format (s, "0x%Lx, ", w[i]);
811 s = format (s, "0x%U", format_hex_bytes, u, vec_len (u) * h->user);
815 if (hash_value_bytes (h) > 0)
816 s = format (s, " -> 0x%wx", p->value[0]);
821 uword mem_key_sum (hash_t * h, uword key)
823 uword * v = uword_to_pointer (key, void *);
824 return hash_memory (v, h->user, 0);
827 uword mem_key_equal (hash_t * h, uword key1, uword key2)
829 void * v1 = uword_to_pointer (key1, void *);
830 void * v2 = uword_to_pointer (key2, void *);
831 return v1 && v2 && 0 == memcmp (v1, v2, h->user);
834 uword string_key_sum (hash_t * h, uword key)
836 char * v = uword_to_pointer (key, char *);
837 return hash_memory (v, strlen (v), 0);
840 uword string_key_equal (hash_t * h, uword key1, uword key2)
842 void * v1 = uword_to_pointer (key1, void *);
843 void * v2 = uword_to_pointer (key2, void *);
844 return v1 && v2 && 0 == strcmp (v1, v2);
847 u8 * string_key_format_pair (u8 * s, va_list * args)
849 void * CLIB_UNUSED (user_arg) = va_arg (*args, void *);
850 void * v = va_arg (*args, void *);
851 hash_pair_t * p = va_arg (*args, hash_pair_t *);
852 hash_t * h = hash_header (v);
853 void * u = uword_to_pointer (p->key, void *);
855 s = format (s, "%s", u);
857 if (hash_value_bytes (h) > 0)
858 s = format (s, " -> 0x%8U", format_hex_bytes, &p->value[0], hash_value_bytes (h));
863 static u8 * hash_format_pair_default (u8 * s, va_list * args)
865 void * CLIB_UNUSED (user_arg) = va_arg (*args, void *);
866 void * v = va_arg (*args, void *);
867 hash_pair_t * p = va_arg (*args, hash_pair_t *);
868 hash_t * h = hash_header (v);
870 s = format (s, "0x%08x", p->key);
871 if (hash_value_bytes (h) > 0)
872 s = format (s, " -> 0x%8U", format_hex_bytes, &p->value[0], hash_value_bytes (h));
876 uword hash_bytes (void * v)
879 hash_t * h = hash_header (v);
884 bytes = vec_capacity (v, hash_header_bytes (v));
886 for (i = 0; i < hash_capacity (v); i++)
888 if (! hash_is_user (v, i))
890 hash_pair_union_t * p = get_pair (v, i);
891 if (h->log2_pair_size > 0)
892 bytes += 1<< indirect_pair_get_log2_bytes (&p->indirect);
894 bytes += vec_capacity (p->indirect.pairs, 0);
900 u8 * format_hash (u8 * s, va_list * va)
902 void * v = va_arg (*va, void *);
903 int verbose = va_arg (*va, int);
905 hash_t * h = hash_header (v);
908 s = format (s, "hash %p, %wd elts, capacity %wd, %wd bytes used,\n",
909 v, hash_elts (v), hash_capacity (v),
913 uword * occupancy = 0;
915 /* Count number of buckets with each occupancy. */
916 for (i = 0; i < hash_capacity (v); i++)
920 if (hash_is_user (v, i))
926 hash_pair_union_t * p = get_pair (v, i);
927 if (h->log2_pair_size > 0)
928 j = indirect_pair_get_len (&p->indirect);
930 j = vec_len (p->indirect.pairs);
933 vec_validate (occupancy, j);
937 s = format (s, " profile ");
938 for (i = 0; i < vec_len (occupancy); i++)
939 s = format (s, "%wd%c", occupancy[i],
940 i + 1 == vec_len (occupancy) ? '\n' : ' ');
942 s = format (s, " lookup # of compares: ");
943 for (i = 1; i < vec_len (occupancy); i++)
944 s = format (s, "%wd: .%03d%c", i,
945 (1000 * i * occupancy[i]) / hash_elts (v),
946 i + 1 == vec_len (occupancy) ? '\n' : ' ');
948 vec_free (occupancy);
953 hash_foreach_pair (p, v, {
954 s = format (s, " %U\n", h->format_pair, h->format_pair_arg, v, p);
962 unformat_hash_string_internal (unformat_input_t * input,
966 uword * hash = va_arg (*va, uword *);
967 int * result = va_arg (*va, int *);
971 if (! unformat (input, is_vec ? "%v%_" : "%s%_", &string))
974 p = hash_get_mem (hash, string);
983 unformat_hash_vec_string (unformat_input_t * input, va_list * va)
984 { return unformat_hash_string_internal (input, va, /* is_vec */ 1); }
987 unformat_hash_string (unformat_input_t * input, va_list * va)
988 { return unformat_hash_string_internal (input, va, /* is_vec */ 0); }
990 clib_error_t * hash_validate (void * v)
992 hash_t * h = hash_header (v);
995 clib_error_t * error = 0;
997 #define CHECK(x) if ((error = ERROR_ASSERT (x))) goto done;
999 for (i = 0; i < hash_capacity (v); i++)
1001 hash_pair_union_t * pu = get_pair (v, i);
1003 if (hash_is_user (v, i))
1005 CHECK (pu->direct.key != 0);
1006 vec_add1 (keys, pu->direct.key);
1011 hash_pair_indirect_t * pi = &pu->indirect;
1014 n = h->log2_pair_size > 0
1015 ? indirect_pair_get_len (pi)
1016 : vec_len (pi->pairs);
1018 for (p = pi->pairs; n-- > 0; p = hash_forward1 (h, p))
1020 /* Assert key uniqueness. */
1021 for (j = 0; j < vec_len (keys); j++)
1022 CHECK (keys[j] != p->key);
1023 vec_add1 (keys, p->key);
1028 CHECK (vec_len (keys) == h->elts);