aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorKlement Sekera <ksekera@cisco.com>2020-02-20 11:39:58 +0000
committerDamjan Marion <dmarion@me.com>2020-03-21 12:14:31 +0000
commit39d0285fca412ea2921fe1ae98a231894cd193cf (patch)
tree75d579caf2f7b5f1adc26e4a1d62e260e095a30d /src
parentdd73bd321e2718dd9afced36dad53bd624af4f32 (diff)
vppinfra: fix minor cuckoo bugs and add cuckoo_16_8
Type: improvement Change-Id: If1164d2eb81e9d4748436cb1bb8b164857d70565 Signed-off-by: Klement Sekera <ksekera@cisco.com>
Diffstat (limited to 'src')
-rw-r--r--src/vppinfra/CMakeLists.txt5
-rw-r--r--src/vppinfra/cuckoo_16_8.h130
-rw-r--r--src/vppinfra/cuckoo_8_8.h4
-rw-r--r--src/vppinfra/cuckoo_template.c53
-rw-r--r--src/vppinfra/cuckoo_template.h4
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);