--- /dev/null
+/*
+ * 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:
+ */
*/
#include <vppinfra/vec.h>
-#include <vppinfra/cuckoo_template.h>
int CV (clib_cuckoo_search) (CVT (clib_cuckoo) * h,
CVT (clib_cuckoo_kv) * search_v,
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)
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)
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;
}
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);
}
}
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 =
{
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;
}
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);
Code Review / vpp.git / commitdiff