diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/vppinfra/CMakeLists.txt | 5 | ||||
| -rw-r--r-- | src/vppinfra/cuckoo_16_8.h | 130 | ||||
| -rw-r--r-- | src/vppinfra/cuckoo_8_8.h | 4 | ||||
| -rw-r--r-- | src/vppinfra/cuckoo_template.c | 53 | ||||
| -rw-r--r-- | src/vppinfra/cuckoo_template.h | 4 |
5 files changed, 170 insertions, 26 deletions
diff --git a/src/vppinfra/CMakeLists.txt b/src/vppinfra/CMakeLists.txt index 7723e6bad5d..3e396e35371 100644 --- a/src/vppinfra/CMakeLists.txt +++ b/src/vppinfra/CMakeLists.txt @@ -43,7 +43,6 @@ set(VPPINFRA_SRCS backtrace.c bihash_all_vector.c cpu.c - cuckoo_template.c dlmalloc.c elf.c elog.c @@ -109,6 +108,10 @@ set(VPPINFRA_HEADERS clib.h cpu.h crc32.h + cuckoo_8_8.h + cuckoo_16_8.h + cuckoo_template.h + cuckoo_template.c dlist.h dlmalloc.h elf_clib.h diff --git a/src/vppinfra/cuckoo_16_8.h b/src/vppinfra/cuckoo_16_8.h new file mode 100644 index 00000000000..0cc7b57bee0 --- /dev/null +++ b/src/vppinfra/cuckoo_16_8.h @@ -0,0 +1,130 @@ +/* + * Copyright (c) 2017 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. + */ +#undef CLIB_CUCKOO_TYPE + +#define CLIB_CUCKOO_TYPE _16_8 +#define CLIB_CUCKOO_KVP_PER_BUCKET (4) +#define CLIB_CUCKOO_LOG2_KVP_PER_BUCKET (2) +#define CLIB_CUCKOO_BFS_MAX_STEPS (2000) +#define CLIB_CUCKOO_BFS_MAX_PATH_LENGTH (8) + +#ifndef __included_cuckoo_16_8_h__ +#define __included_cuckoo_16_8_h__ + +#include <vppinfra/heap.h> +#include <vppinfra/format.h> +#include <vppinfra/pool.h> +#include <vppinfra/xxhash.h> +#include <vppinfra/cuckoo_debug.h> +#include <vppinfra/cuckoo_common.h> + +#undef CLIB_CUCKOO_OPTIMIZE_PREFETCH +#undef CLIB_CUCKOO_OPTIMIZE_CMP_REDUCED_HASH +#undef CLIB_CUCKOO_OPTIMIZE_UNROLL +#undef CLIB_CUCKOO_OPTIMIZE_USE_COUNT_LIMITS_SEARCH +#define CLIB_CUCKOO_OPTIMIZE_PREFETCH 1 +#define CLIB_CUCKOO_OPTIMIZE_CMP_REDUCED_HASH 1 +#define CLIB_CUCKOO_OPTIMIZE_UNROLL 1 +#define CLIB_CUCKOO_OPTIMIZE_USE_COUNT_LIMITS_SEARCH 1 + +#if __SSE4_2__ && !defined (__i386__) +#include <x86intrin.h> +#endif + +/** 8 octet key, 8 octet key value pair */ +typedef struct +{ + u64 key[2]; /**< the key */ + u64 value; /**< the value */ +} clib_cuckoo_kv_16_8_t; + +/** Decide if a clib_cuckoo_kv_16_8_t instance is free + @param v- pointer to the (key,value) pair +*/ +always_inline int +clib_cuckoo_kv_is_free_16_8 (const clib_cuckoo_kv_16_8_t * v) +{ + if (v->key[0] == ~0ULL && v->value == ~0ULL) + return 1; + return 0; +} + +always_inline void +clib_cuckoo_kv_set_free_16_8 (clib_cuckoo_kv_16_8_t * v) +{ + clib_memset (v, 0xff, sizeof (*v)); +} + +/** Format a clib_cuckoo_kv_16_8_t instance + @param s - u8 * vector under construction + @param args (vararg) - the (key,value) pair to format + @return s - the u8 * vector under construction +*/ +always_inline u8 * +format_cuckoo_kvp_16_8 (u8 * s, va_list * args) +{ + clib_cuckoo_kv_16_8_t *v = va_arg (*args, clib_cuckoo_kv_16_8_t *); + + if (clib_cuckoo_kv_is_free_16_8 (v)) + { + s = format (s, " -- empty -- "); + } + else + { + s = + format (s, "key %llu%llu value %llu", v->key[0], v->key[1], v->value); + } + return s; +} + +always_inline u64 +clib_cuckoo_hash_16_8 (clib_cuckoo_kv_16_8_t * v) +{ +#ifdef clib_crc32c_uses_intrinsics + return clib_crc32c ((u8 *) v->key, 16); +#else + u64 tmp = v->key[0] ^ v->key[1]; + return clib_xxhash (tmp); +#endif +} + +/** Compare two clib_cuckoo_kv_16_8_t instances + @param a - first key + @param b - second key +*/ +always_inline int +clib_cuckoo_key_compare_16_8 (u64 * a, u64 * b) +{ +#if defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE) + u64x2 v; + v = u64x2_load_unaligned (a) ^ u64x2_load_unaligned (b); + return u64x2_is_all_zero (v); +#else + return ((a[0] ^ b[0]) | (a[1] ^ b[1])) == 0; +#endif +} + +#undef __included_cuckoo_template_h__ +#include <vppinfra/cuckoo_template.h> + +#endif /* __included_cuckoo_16_8_h__ */ + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ diff --git a/src/vppinfra/cuckoo_8_8.h b/src/vppinfra/cuckoo_8_8.h index a3d07c870eb..ace535b58f6 100644 --- a/src/vppinfra/cuckoo_8_8.h +++ b/src/vppinfra/cuckoo_8_8.h @@ -79,7 +79,7 @@ format_cuckoo_kvp_8_8 (u8 * s, va_list * args) if (clib_cuckoo_kv_is_free_8_8 (v)) { - s = format (s, " -- empty -- ", v->key, v->value); + s = format (s, " -- empty -- "); } else { @@ -108,10 +108,8 @@ clib_cuckoo_key_compare_8_8 (u64 a, u64 b) return a == b; } -#if 0 #undef __included_cuckoo_template_h__ #include <vppinfra/cuckoo_template.h> -#endif #endif /* __included_cuckoo_8_8_h__ */ diff --git a/src/vppinfra/cuckoo_template.c b/src/vppinfra/cuckoo_template.c index c48032a319c..8cd2a2be2b5 100644 --- a/src/vppinfra/cuckoo_template.c +++ b/src/vppinfra/cuckoo_template.c @@ -21,7 +21,6 @@ */ #include <vppinfra/vec.h> -#include <vppinfra/cuckoo_template.h> int CV (clib_cuckoo_search) (CVT (clib_cuckoo) * h, CVT (clib_cuckoo_kv) * search_v, @@ -100,8 +99,7 @@ static void CV (clib_cuckoo_deep_self_check) (CVT (clib_cuckoo) * h) CVT (clib_cuckoo_bucket) * bucket; uword bucket_idx = 0; /* *INDENT-OFF* */ - clib_cuckoo_foreach_bucket (bucket, h) - { + clib_cuckoo_foreach_bucket (bucket, h, { int i = 0; int used = 0; clib_cuckoo_bucket_foreach_idx (i) @@ -110,8 +108,8 @@ static void CV (clib_cuckoo_deep_self_check) (CVT (clib_cuckoo) * h) if (!CV (clib_cuckoo_kv_is_free) (elt)) { u64 hash = CV (clib_cuckoo_hash) (elt); - clib_cuckoo_lookup_info_t lookup = CV (clib_cuckoo_calc_lookup) ( - CV (clib_cuckoo_get_snapshot) (h), hash); + clib_cuckoo_lookup_info_t lookup = + CV (clib_cuckoo_calc_lookup) (h->buckets, hash); CVT (clib_cuckoo_kv) kv = *elt; int rv = CV (clib_cuckoo_search) (h, &kv, &kv); if (CLIB_CUCKOO_ERROR_SUCCESS != rv) @@ -121,7 +119,7 @@ static void CV (clib_cuckoo_deep_self_check) (CVT (clib_cuckoo) * h) bucket->reduced_hashes[i]); CLIB_CUCKOO_DBG ("%U", CV (format_cuckoo), h, 1); } - ASSERT (aux.bucket1 == bucket_idx || aux.bucket2 == bucket_idx); + ASSERT (lookup.bucket1 == bucket_idx || lookup.bucket2 == bucket_idx); ASSERT (CLIB_CUCKOO_ERROR_SUCCESS == rv); ++used; } @@ -129,7 +127,7 @@ static void CV (clib_cuckoo_deep_self_check) (CVT (clib_cuckoo) * h) clib_cuckoo_bucket_aux_t aux = bucket->aux; ASSERT (used == clib_cuckoo_bucket_aux_get_use_count (aux)); ++bucket_idx; - } + }); /* *INDENT-ON* */ // CLIB_CUCKOO_DBG ("Deep self check passed: %U", CV (format_cuckoo), h); } @@ -820,14 +818,15 @@ static int CV (clib_cuckoo_bucket_search_internal) (CVT (clib_cuckoo) * h, } int CV (clib_cuckoo_add_del) (CVT (clib_cuckoo) * h, - CVT (clib_cuckoo_kv) * kvp, int is_add) + CVT (clib_cuckoo_kv) * kvp, int is_add, + int dont_overwrite) { CLIB_CUCKOO_DBG ("%s %U", is_add ? "Add" : "Del", CV (format_cuckoo_kvp), kvp); clib_cuckoo_lookup_info_t lookup; u64 hash = CV (clib_cuckoo_hash) (kvp); - clib_spinlock_lock (&h->writer_lock); u8 reduced_hash = clib_cuckoo_reduce_hash (hash); + clib_spinlock_lock (&h->writer_lock); restart: lookup = CV (clib_cuckoo_calc_lookup) (h->buckets, hash); CVT (clib_cuckoo_bucket) * b = @@ -846,19 +845,30 @@ restart: { if (is_add) { - /* prevent readers reading this bucket while we switch the values */ - clib_cuckoo_bucket_aux_t aux = - CV (clib_cuckoo_bucket_version_bump_and_lock) (b); - clib_memcpy (&found->value, &kvp->value, sizeof (found->value)); - CLIB_CUCKOO_DBG ("Replaced existing %U", CV (format_cuckoo_elt), - found, b->reduced_hashes[found - b->elts]); - CV (clib_cuckoo_bucket_unlock) (b, aux); + if (dont_overwrite) + { + CLIB_CUCKOO_DBG ("Refused replacing existing %U", + CV (format_cuckoo_elt), found, + b->reduced_hashes[found - b->elts]); + rv = CLIB_CUCKOO_ERROR_AGAIN; + } + else + { + /* prevent readers reading this bucket while we switch the values */ + clib_cuckoo_bucket_aux_t aux = + CV (clib_cuckoo_bucket_version_bump_and_lock) (b); + clib_memcpy (&found->value, &kvp->value, sizeof (found->value)); + CLIB_CUCKOO_DBG ("Replaced existing %U", CV (format_cuckoo_elt), + found, b->reduced_hashes[found - b->elts]); + CV (clib_cuckoo_bucket_unlock) (b, aux); + rv = CLIB_CUCKOO_ERROR_SUCCESS; + } } else { CV (clib_cuckoo_free_elt_in_bucket) (b, found); + rv = CLIB_CUCKOO_ERROR_SUCCESS; } - rv = CLIB_CUCKOO_ERROR_SUCCESS; CLIB_CUCKOO_DEEP_SELF_CHECK (h); goto unlock; } @@ -876,9 +886,12 @@ restart: CLIB_CUCKOO_DEEP_SELF_CHECK (h); if (CLIB_CUCKOO_ERROR_SUCCESS != rv) { - CLIB_CUCKOO_DBG ("Fast insert failed, bucket 1: %wu, bucket 2: %wu\n%U%U", aux.bucket1, aux.bucket2, CV (format_cuckoo_bucket), CV (clib_cuckoo_bucindent: Standaindent: Standard input: 903: Error: Unmatched 'else' rd input: 865: Error:Unmatched 'else' ket_at_index) (h, aux.bucket1), - CV (format_cuckoo_bucket), - CV (clib_cuckoo_bucket_at_index) (h, aux.bucket2)); + CLIB_CUCKOO_DBG + ("Fast insert failed, bucket 1: %wu, bucket 2: %wu\n%U%U", + lookup.bucket1, lookup.bucket2, CV (format_cuckoo_bucket), + CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket1), + CV (format_cuckoo_bucket), + CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket2)); /* slow path */ rv = CV (clib_cuckoo_add_slow) (h, kvp, &lookup, reduced_hash); CLIB_CUCKOO_DEEP_SELF_CHECK (h); diff --git a/src/vppinfra/cuckoo_template.h b/src/vppinfra/cuckoo_template.h index c3b2bc98aaa..06c4afdc79b 100644 --- a/src/vppinfra/cuckoo_template.h +++ b/src/vppinfra/cuckoo_template.h @@ -35,7 +35,6 @@ #include <vppinfra/error.h> #include <vppinfra/hash.h> #include <vppinfra/cache.h> -#include <vppinfra/cuckoo_8_8.h> #ifndef CLIB_CUCKOO_TYPE #error CLIB_CUCKOO_TYPE not defined @@ -301,7 +300,8 @@ void CV (clib_cuckoo_garbage_collect) (CVT (clib_cuckoo) * h); void CV (clib_cuckoo_free) (CVT (clib_cuckoo) * h); int CV (clib_cuckoo_add_del) (CVT (clib_cuckoo) * h, - CVT (clib_cuckoo_kv) * add_v, int is_add); + CVT (clib_cuckoo_kv) * add_v, int is_add, + int dont_overwrite); int CV (clib_cuckoo_search) (CVT (clib_cuckoo) * h, CVT (clib_cuckoo_kv) * search_v, CVT (clib_cuckoo_kv) * return_v); |