diff options
Diffstat (limited to 'src/vppinfra/pfhash.c')
| -rw-r--r-- | src/vppinfra/pfhash.c | 689 |
1 files changed, 689 insertions, 0 deletions
diff --git a/src/vppinfra/pfhash.c b/src/vppinfra/pfhash.c new file mode 100644 index 00000000000..3b9fa8f34aa --- /dev/null +++ b/src/vppinfra/pfhash.c @@ -0,0 +1,689 @@ +/* + Copyright (c) 2013 Cisco and/or its affiliates. + + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +#include <vppinfra/pfhash.h> +#include <vppinfra/format.h> + +/* This is incredibly handy when debugging */ +u32 vl (void *v) __attribute__ ((weak)); +u32 +vl (void *v) +{ + return vec_len (v); +} + +#if defined(CLIB_HAVE_VEC128) && ! defined (__ALTIVEC__) + +typedef struct +{ + u8 *key[16]; + u64 value; +} pfhash_show_t; + +static int +sh_compare (pfhash_show_t * sh0, pfhash_show_t * sh1) +{ + return ((i32) (sh0->value) - ((i32) sh1->value)); +} + +u8 * +format_pfhash (u8 * s, va_list * args) +{ + pfhash_t *p = va_arg (*args, pfhash_t *); + int verbose = va_arg (*args, int); + + if (p == 0 || p->overflow_hash == 0 || p->buckets == 0) + { + s = format (s, "*** uninitialized ***"); + return s; + } + + s = format (s, "Prefetch hash '%s'\n", p->name); + s = + format (s, " %d buckets, %u bucket overflows, %.1f%% bucket overflow \n", + vec_len (p->buckets), p->overflow_count, + 100.0 * ((f64) p->overflow_count) / ((f64) vec_len (p->buckets))); + if (p->nitems) + s = + format (s, + " %u items, %u items in overflow, %.1f%% items in overflow\n", + p->nitems, p->nitems_in_overflow, + 100.0 * ((f64) p->nitems_in_overflow) / ((f64) p->nitems)); + + if (verbose) + { + pfhash_show_t *shs = 0, *sh; + hash_pair_t *hp; + int i, j; + + for (i = 0; i < vec_len (p->buckets); i++) + { + pfhash_kv_t *kv; + pfhash_kv_16_t *kv16; + pfhash_kv_8_t *kv8; + pfhash_kv_8v8_t *kv8v8; + pfhash_kv_4_t *kv4; + + if (p->buckets[i] == 0 || p->buckets[i] == PFHASH_BUCKET_OVERFLOW) + continue; + + kv = pool_elt_at_index (p->kvp, p->buckets[i]); + + switch (p->key_size) + { + case 16: + kv16 = &kv->kv16; + for (j = 0; j < 3; j++) + { + if (kv16->values[j] != (u32) ~ 0) + { + vec_add2 (shs, sh, 1); + clib_memcpy (sh->key, &kv16->kb.k_u32x4[j], + p->key_size); + sh->value = kv16->values[j]; + } + } + break; + case 8: + if (p->value_size == 4) + { + kv8 = &kv->kv8; + for (j = 0; j < 5; j++) + { + if (kv8->values[j] != (u32) ~ 0) + { + vec_add2 (shs, sh, 1); + clib_memcpy (sh->key, &kv8->kb.k_u64[j], + p->key_size); + sh->value = kv8->values[j]; + } + } + } + else + { + kv8v8 = &kv->kv8v8; + for (j = 0; j < 4; j++) + { + if (kv8v8->values[j] != (u64) ~ 0) + { + vec_add2 (shs, sh, 1); + clib_memcpy (sh->key, &kv8v8->kb.k_u64[j], + p->key_size); + sh->value = kv8v8->values[j]; + } + } + + } + break; + case 4: + kv4 = &kv->kv4; + for (j = 0; j < 8; j++) + { + if (kv4->values[j] != (u32) ~ 0) + { + vec_add2 (shs, sh, 1); + clib_memcpy (sh->key, &kv4->kb.kb[j], p->key_size); + sh->value = kv4->values[j]; + } + } + break; + } + } + + /* *INDENT-OFF* */ + hash_foreach_pair (hp, p->overflow_hash, + ({ + vec_add2 (shs, sh, 1); + clib_memcpy (sh->key, (u8 *)hp->key, p->key_size); + sh->value = hp->value[0]; + })); + /* *INDENT-ON* */ + + vec_sort_with_function (shs, sh_compare); + + for (i = 0; i < vec_len (shs); i++) + { + sh = vec_elt_at_index (shs, i); + s = format (s, " %U value %u\n", format_hex_bytes, sh->key, + p->key_size, sh->value); + } + vec_free (shs); + } + return s; +} + + +void abort (void); + +void +pfhash_init (pfhash_t * p, char *name, u32 key_size, u32 value_size, + u32 nbuckets) +{ + pfhash_kv_t *kv; + memset (p, 0, sizeof (*p)); + u32 key_bytes; + + switch (key_size) + { + case 4: + key_bytes = 4; + break; + case 8: + key_bytes = 8; + break; + case 16: + key_bytes = 16; + break; + default: + ASSERT (0); + abort (); + } + + switch (value_size) + { + case 4: + case 8: + break; + default: + ASSERT (0); + abort (); + } + + + p->name = format (0, "%s", name); + vec_add1 (p->name, 0); + p->overflow_hash = hash_create_mem (0, key_bytes, sizeof (uword)); + + nbuckets = 1 << (max_log2 (nbuckets)); + + /* This sets the entire bucket array to zero */ + vec_validate (p->buckets, nbuckets - 1); + p->key_size = key_size; + p->value_size = value_size; + + /* + * Unset buckets implicitly point at the 0th pool elt. + * All search routines will return ~0 if they go there. + */ + pool_get_aligned (p->kvp, kv, 16); + memset (kv, 0xff, sizeof (*kv)); +} + +static pfhash_kv_16_t * +pfhash_get_kv_16 (pfhash_t * p, u32 bucket_contents, + u32x4 * key, u32 * match_index) +{ + u32x4 diff[3]; + u32 is_equal[3]; + pfhash_kv_16_t *kv = 0; + + *match_index = (u32) ~ 0; + + kv = &p->kvp[bucket_contents].kv16; + + diff[0] = u32x4_sub (kv->kb.k_u32x4[0], key[0]); + diff[1] = u32x4_sub (kv->kb.k_u32x4[1], key[0]); + diff[2] = u32x4_sub (kv->kb.k_u32x4[2], key[0]); + + is_equal[0] = u32x4_zero_byte_mask (diff[0]) == 0xffff; + is_equal[1] = u32x4_zero_byte_mask (diff[1]) == 0xffff; + is_equal[2] = u32x4_zero_byte_mask (diff[2]) == 0xffff; + + if (is_equal[0]) + *match_index = 0; + if (is_equal[1]) + *match_index = 1; + if (is_equal[2]) + *match_index = 2; + + return kv; +} + +static pfhash_kv_8_t * +pfhash_get_kv_8 (pfhash_t * p, u32 bucket_contents, + u64 * key, u32 * match_index) +{ + pfhash_kv_8_t *kv; + + *match_index = (u32) ~ 0; + + kv = &p->kvp[bucket_contents].kv8; + + if (kv->kb.k_u64[0] == key[0]) + *match_index = 0; + if (kv->kb.k_u64[1] == key[0]) + *match_index = 1; + if (kv->kb.k_u64[2] == key[0]) + *match_index = 2; + if (kv->kb.k_u64[3] == key[0]) + *match_index = 3; + if (kv->kb.k_u64[4] == key[0]) + *match_index = 4; + + return kv; +} + +static pfhash_kv_8v8_t * +pfhash_get_kv_8v8 (pfhash_t * p, + u32 bucket_contents, u64 * key, u32 * match_index) +{ + pfhash_kv_8v8_t *kv; + + *match_index = (u32) ~ 0; + + kv = &p->kvp[bucket_contents].kv8v8; + + if (kv->kb.k_u64[0] == key[0]) + *match_index = 0; + if (kv->kb.k_u64[1] == key[0]) + *match_index = 1; + if (kv->kb.k_u64[2] == key[0]) + *match_index = 2; + if (kv->kb.k_u64[3] == key[0]) + *match_index = 3; + + return kv; +} + +static pfhash_kv_4_t * +pfhash_get_kv_4 (pfhash_t * p, u32 bucket_contents, + u32 * key, u32 * match_index) +{ + u32x4 vector_key; + u32x4 is_equal[2]; + u32 zbm[2], winner_index; + pfhash_kv_4_t *kv; + + *match_index = (u32) ~ 0; + + kv = &p->kvp[bucket_contents].kv4; + + vector_key = u32x4_splat (key[0]); + + is_equal[0] = u32x4_is_equal (kv->kb.k_u32x4[0], vector_key); + is_equal[1] = u32x4_is_equal (kv->kb.k_u32x4[1], vector_key); + zbm[0] = ~u32x4_zero_byte_mask (is_equal[0]) & 0xFFFF; + zbm[1] = ~u32x4_zero_byte_mask (is_equal[1]) & 0xFFFF; + + if (PREDICT_FALSE ((zbm[0] == 0) && (zbm[1] == 0))) + return kv; + + winner_index = min_log2 (zbm[0]) >> 2; + winner_index = zbm[1] ? (4 + (min_log2 (zbm[1]) >> 2)) : winner_index; + + *match_index = winner_index; + return kv; +} + +static pfhash_kv_t * +pfhash_get_internal (pfhash_t * p, u32 bucket_contents, + void *key, u32 * match_index) +{ + pfhash_kv_t *kv = 0; + + switch (p->key_size) + { + case 16: + kv = + (pfhash_kv_t *) pfhash_get_kv_16 (p, bucket_contents, key, + match_index); + break; + case 8: + if (p->value_size == 4) + kv = (pfhash_kv_t *) pfhash_get_kv_8 (p, bucket_contents, + key, match_index); + else + kv = (pfhash_kv_t *) pfhash_get_kv_8v8 (p, bucket_contents, + key, match_index); + break; + case 4: + kv = + (pfhash_kv_t *) pfhash_get_kv_4 (p, bucket_contents, key, + match_index); + break; + default: + ASSERT (0); + } + return kv; +} + +u64 +pfhash_get (pfhash_t * p, u32 bucket, void *key) +{ + pfhash_kv_t *kv; + u32 match_index = ~0; + pfhash_kv_16_t *kv16; + pfhash_kv_8_t *kv8; + pfhash_kv_8v8_t *kv8v8; + pfhash_kv_4_t *kv4; + + u32 bucket_contents = pfhash_read_bucket_prefetch_kv (p, bucket); + + if (bucket_contents == PFHASH_BUCKET_OVERFLOW) + { + uword *hp; + + hp = hash_get_mem (p->overflow_hash, key); + if (hp) + return hp[0]; + return (u64) ~ 0; + } + + kv = pfhash_get_internal (p, bucket_contents, key, &match_index); + if (match_index == (u32) ~ 0) + return (u64) ~ 0; + + kv16 = (void *) kv; + kv8 = (void *) kv; + kv4 = (void *) kv; + kv8v8 = (void *) kv; + + switch (p->key_size) + { + case 16: + return (kv16->values[match_index] == (u32) ~ 0) + ? (u64) ~ 0 : (u64) kv16->values[match_index]; + case 8: + if (p->value_size == 4) + return (kv8->values[match_index] == (u32) ~ 0) + ? (u64) ~ 0 : (u64) kv8->values[match_index]; + else + return kv8v8->values[match_index]; + case 4: + return (kv4->values[match_index] == (u32) ~ 0) + ? (u64) ~ 0 : (u64) kv4->values[match_index]; + default: + ASSERT (0); + } + return (u64) ~ 0; +} + +void +pfhash_set (pfhash_t * p, u32 bucket, void *key, void *value) +{ + u32 bucket_contents = pfhash_read_bucket_prefetch_kv (p, bucket); + u32 match_index = (u32) ~ 0; + pfhash_kv_t *kv; + pfhash_kv_16_t *kv16; + pfhash_kv_8_t *kv8; + pfhash_kv_8v8_t *kv8v8; + pfhash_kv_4_t *kv4; + int i; + u8 *kcopy; + + if (bucket_contents == PFHASH_BUCKET_OVERFLOW) + { + hash_pair_t *hp; + hp = hash_get_pair_mem (p->overflow_hash, key); + if (hp) + { + clib_warning ("replace value 0x%08x with value 0x%08x", + hp->value[0], (u64) value); + hp->value[0] = (u64) value; + return; + } + kcopy = clib_mem_alloc (p->key_size); + clib_memcpy (kcopy, key, p->key_size); + hash_set_mem (p->overflow_hash, kcopy, value); + p->nitems++; + p->nitems_in_overflow++; + return; + } + + if (bucket_contents == 0) + { + pool_get_aligned (p->kvp, kv, 16); + memset (kv, 0xff, sizeof (*kv)); + p->buckets[bucket] = kv - p->kvp; + } + else + kv = pfhash_get_internal (p, bucket_contents, key, &match_index); + + kv16 = (void *) kv; + kv8 = (void *) kv; + kv8v8 = (void *) kv; + kv4 = (void *) kv; + + p->nitems++; + + if (match_index != (u32) ~ 0) + { + switch (p->key_size) + { + case 16: + kv16->values[match_index] = (u32) (u64) value; + return; + + case 8: + if (p->value_size == 4) + kv8->values[match_index] = (u32) (u64) value; + else + kv8v8->values[match_index] = (u64) value; + return; + + case 4: + kv4->values[match_index] = (u64) value; + return; + + default: + ASSERT (0); + } + } + + switch (p->key_size) + { + case 16: + for (i = 0; i < 3; i++) + { + if (kv16->values[i] == (u32) ~ 0) + { + clib_memcpy (&kv16->kb.k_u32x4[i], key, p->key_size); + kv16->values[i] = (u32) (u64) value; + return; + } + } + /* copy bucket contents to overflow hash tbl */ + for (i = 0; i < 3; i++) + { + kcopy = clib_mem_alloc (p->key_size); + clib_memcpy (kcopy, &kv16->kb.k_u32x4[i], p->key_size); + hash_set_mem (p->overflow_hash, kcopy, kv16->values[i]); + p->nitems_in_overflow++; + } + /* Add new key to overflow */ + kcopy = clib_mem_alloc (p->key_size); + clib_memcpy (kcopy, key, p->key_size); + hash_set_mem (p->overflow_hash, kcopy, value); + p->buckets[bucket] = PFHASH_BUCKET_OVERFLOW; + p->overflow_count++; + p->nitems_in_overflow++; + return; + + case 8: + if (p->value_size == 4) + { + for (i = 0; i < 5; i++) + { + if (kv8->values[i] == (u32) ~ 0) + { + clib_memcpy (&kv8->kb.k_u64[i], key, 8); + kv8->values[i] = (u32) (u64) value; + return; + } + } + /* copy bucket contents to overflow hash tbl */ + for (i = 0; i < 5; i++) + { + kcopy = clib_mem_alloc (p->key_size); + clib_memcpy (kcopy, &kv8->kb.k_u64[i], 8); + hash_set_mem (p->overflow_hash, kcopy, kv8->values[i]); + p->nitems_in_overflow++; + } + } + else + { + for (i = 0; i < 4; i++) + { + if (kv8v8->values[i] == (u64) ~ 0) + { + clib_memcpy (&kv8v8->kb.k_u64[i], key, 8); + kv8v8->values[i] = (u64) value; + return; + } + } + /* copy bucket contents to overflow hash tbl */ + for (i = 0; i < 4; i++) + { + kcopy = clib_mem_alloc (p->key_size); + clib_memcpy (kcopy, &kv8v8->kb.k_u64[i], 8); + hash_set_mem (p->overflow_hash, kcopy, kv8v8->values[i]); + p->nitems_in_overflow++; + } + + } + /* Add new key to overflow */ + kcopy = clib_mem_alloc (p->key_size); + clib_memcpy (kcopy, key, p->key_size); + hash_set_mem (p->overflow_hash, kcopy, value); + p->buckets[bucket] = PFHASH_BUCKET_OVERFLOW; + p->overflow_count++; + p->nitems_in_overflow++; + return; + + case 4: + for (i = 0; i < 8; i++) + { + if (kv4->values[i] == (u32) ~ 0) + { + clib_memcpy (&kv4->kb.kb[i], key, 4); + kv4->values[i] = (u32) (u64) value; + return; + } + } + /* copy bucket contents to overflow hash tbl */ + for (i = 0; i < 8; i++) + { + kcopy = clib_mem_alloc (p->key_size); + clib_memcpy (kcopy, &kv4->kb.kb[i], 4); + hash_set_mem (p->overflow_hash, kcopy, kv4->values[i]); + p->nitems_in_overflow++; + } + /* Add new key to overflow */ + kcopy = clib_mem_alloc (p->key_size); + clib_memcpy (kcopy, key, p->key_size); + hash_set_mem (p->overflow_hash, kcopy, value); + p->buckets[bucket] = PFHASH_BUCKET_OVERFLOW; + p->overflow_count++; + p->nitems_in_overflow++; + return; + + default: + ASSERT (0); + } +} + +void +pfhash_unset (pfhash_t * p, u32 bucket, void *key) +{ + u32 bucket_contents = pfhash_read_bucket_prefetch_kv (p, bucket); + u32 match_index = (u32) ~ 0; + pfhash_kv_t *kv; + pfhash_kv_16_t *kv16; + pfhash_kv_8_t *kv8; + pfhash_kv_8v8_t *kv8v8; + pfhash_kv_4_t *kv4; + void *oldkey; + + if (bucket_contents == PFHASH_BUCKET_OVERFLOW) + { + hash_pair_t *hp; + hp = hash_get_pair_mem (p->overflow_hash, key); + if (hp) + { + oldkey = (void *) hp->key; + hash_unset_mem (p->overflow_hash, key); + clib_mem_free (oldkey); + p->nitems--; + p->nitems_in_overflow--; + } + return; + } + + kv = pfhash_get_internal (p, bucket_contents, key, &match_index); + if (match_index == (u32) ~ 0) + return; + + p->nitems--; + + kv16 = (void *) kv; + kv8 = (void *) kv; + kv8v8 = (void *) kv; + kv4 = (void *) kv; + + switch (p->key_size) + { + case 16: + kv16->values[match_index] = (u32) ~ 0; + return; + + case 8: + if (p->value_size == 4) + kv8->values[match_index] = (u32) ~ 0; + else + kv8v8->values[match_index] = (u64) ~ 0; + return; + + case 4: + kv4->values[match_index] = (u32) ~ 0; + return; + + default: + ASSERT (0); + } +} + +void +pfhash_free (pfhash_t * p) +{ + hash_pair_t *hp; + int i; + u8 **keys = 0; + + vec_free (p->name); + + pool_free (p->kvp); + + /* *INDENT-OFF* */ + hash_foreach_pair (hp, p->overflow_hash, + ({ + vec_add1 (keys, (u8 *)hp->key); + })); + /* *INDENT-ON* */ + hash_free (p->overflow_hash); + for (i = 0; i < vec_len (keys); i++) + vec_free (keys[i]); + vec_free (keys); +} + +#endif + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ |