From patchwork Fri May 8 19:58:50 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Medvedkin, Vladimir" X-Patchwork-Id: 70012 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 8F6D8A0352; Fri, 8 May 2020 21:59:09 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 733B61DA33; Fri, 8 May 2020 21:59:03 +0200 (CEST) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id 91C8C1DA11 for ; Fri, 8 May 2020 21:58:59 +0200 (CEST) IronPort-SDR: VqBxR7oGy26DHkFZra2nMRVNG1Xsfi6byjSwTgsmRtVhAF+iVS1Zmdny2F/p1LStTo2Ffy9riv swDT4yitUZCw== X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga004.fm.intel.com ([10.253.24.48]) by orsmga102.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 08 May 2020 12:58:59 -0700 IronPort-SDR: SnneGw/iPy9RRgareKF210ii5e68S00+22o3xAsVV8L2oFwRLLes91klbK5yoCRViGV+UwDIRo Qrwgm2A6hZEA== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.73,368,1583222400"; d="scan'208";a="285584876" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by fmsmga004.fm.intel.com with ESMTP; 08 May 2020 12:58:57 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: konstantin.ananyev@intel.com, yipeng1.wang@intel.com, sameh.gobriel@intel.com, bruce.richardson@intel.com Date: Fri, 8 May 2020 20:58:50 +0100 Message-Id: X-Mailer: git-send-email 2.7.4 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH v4 1/4] hash: add kv hash library X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" KV hash is a special optimized key-value storage for fixed key and value sizes. At the moment it supports 32 bit keys and 64 bit values. This table is hash function agnostic so user must provide precalculated hash signature for add/delete/lookup operations. Signed-off-by: Vladimir Medvedkin --- lib/Makefile | 2 +- lib/librte_hash/Makefile | 14 +- lib/librte_hash/k32v64_hash.c | 277 +++++++++++++++++++++++++++++++++ lib/librte_hash/k32v64_hash.h | 98 ++++++++++++ lib/librte_hash/k32v64_hash_avx512vl.c | 59 +++++++ lib/librte_hash/meson.build | 17 +- lib/librte_hash/rte_hash_version.map | 6 +- lib/librte_hash/rte_kv_hash.c | 184 ++++++++++++++++++++++ lib/librte_hash/rte_kv_hash.h | 169 ++++++++++++++++++++ 9 files changed, 821 insertions(+), 5 deletions(-) create mode 100644 lib/librte_hash/k32v64_hash.c create mode 100644 lib/librte_hash/k32v64_hash.h create mode 100644 lib/librte_hash/k32v64_hash_avx512vl.c create mode 100644 lib/librte_hash/rte_kv_hash.c create mode 100644 lib/librte_hash/rte_kv_hash.h diff --git a/lib/Makefile b/lib/Makefile index 9d24609..42769e9 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -48,7 +48,7 @@ DIRS-$(CONFIG_RTE_LIBRTE_VHOST) += librte_vhost DEPDIRS-librte_vhost := librte_eal librte_mempool librte_mbuf librte_ethdev \ librte_net librte_hash librte_cryptodev DIRS-$(CONFIG_RTE_LIBRTE_HASH) += librte_hash -DEPDIRS-librte_hash := librte_eal librte_ring +DEPDIRS-librte_hash := librte_eal librte_ring librte_mempool DIRS-$(CONFIG_RTE_LIBRTE_EFD) += librte_efd DEPDIRS-librte_efd := librte_eal librte_ring librte_hash DIRS-$(CONFIG_RTE_LIBRTE_RIB) += librte_rib diff --git a/lib/librte_hash/Makefile b/lib/librte_hash/Makefile index ec9f864..a0cdee9 100644 --- a/lib/librte_hash/Makefile +++ b/lib/librte_hash/Makefile @@ -8,13 +8,15 @@ LIB = librte_hash.a CFLAGS += -O3 CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR) -LDLIBS += -lrte_eal -lrte_ring +LDLIBS += -lrte_eal -lrte_ring -lrte_mempool EXPORT_MAP := rte_hash_version.map # all source are stored in SRCS-y SRCS-$(CONFIG_RTE_LIBRTE_HASH) := rte_cuckoo_hash.c SRCS-$(CONFIG_RTE_LIBRTE_HASH) += rte_fbk_hash.c +SRCS-$(CONFIG_RTE_LIBRTE_HASH) += rte_kv_hash.c +SRCS-$(CONFIG_RTE_LIBRTE_HASH) += k32v64_hash.c # install this header file SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include := rte_hash.h @@ -27,5 +29,15 @@ endif SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_jhash.h SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_thash.h SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_fbk_hash.h +SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_kv_hash.h + +CC_AVX512VL_SUPPORT=$(shell $(CC) -mavx512vl -dM -E - &1 | \ +grep -q __AVX512VL__ && echo 1) + +ifeq ($(CC_AVX512VL_SUPPORT), 1) + SRCS-$(CONFIG_RTE_LIBRTE_HASH) += k32v64_hash_avx512vl.c + CFLAGS_k32v64_hash_avx512vl.o += -mavx512vl + CFLAGS_k32v64_hash.o += -DCC_AVX512VL_SUPPORT +endif include $(RTE_SDK)/mk/rte.lib.mk diff --git a/lib/librte_hash/k32v64_hash.c b/lib/librte_hash/k32v64_hash.c new file mode 100644 index 0000000..24cd63a --- /dev/null +++ b/lib/librte_hash/k32v64_hash.c @@ -0,0 +1,277 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2020 Intel Corporation + */ + +#include + +#include +#include +#include + +#include "k32v64_hash.h" + +static inline int +k32v64_hash_lookup(struct k32v64_hash_table *table, uint32_t key, + uint32_t hash, uint64_t *value) +{ + return __k32v64_hash_lookup(table, key, hash, value, __kv_cmp_keys); +} + +static int +k32v64_hash_bulk_lookup(struct rte_kv_hash_table *ht, void *keys_p, + uint32_t *hashes, void *values_p, unsigned int n) +{ + struct k32v64_hash_table *table = (struct k32v64_hash_table *)ht; + uint32_t *keys = keys_p; + uint64_t *values = values_p; + int ret, cnt = 0; + unsigned int i; + + if (unlikely((table == NULL) || (keys == NULL) || (hashes == NULL) || + (values == NULL))) + return -EINVAL; + + for (i = 0; i < n; i++) { + ret = k32v64_hash_lookup(table, keys[i], hashes[i], + &values[i]); + if (ret == 0) + cnt++; + } + return cnt; +} + +#ifdef CC_AVX512VL_SUPPORT +int +k32v64_hash_bulk_lookup_avx512vl(struct rte_kv_hash_table *ht, + void *keys_p, uint32_t *hashes, void *values_p, unsigned int n); +#endif + +static rte_kv_hash_bulk_lookup_t +get_lookup_bulk_fn(void) +{ +#ifdef CC_AVX512VL_SUPPORT + if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX512VL)) + return k32v64_hash_bulk_lookup_avx512vl; +#endif + return k32v64_hash_bulk_lookup; +} + +static int +k32v64_hash_add(struct k32v64_hash_table *table, uint32_t key, + uint32_t hash, uint64_t value, uint64_t *old_value, int *found) +{ + uint32_t bucket; + int i, idx, ret; + uint8_t msk; + struct k32v64_ext_ent *tmp, *ent, *prev = NULL; + + if (table == NULL) + return -EINVAL; + + bucket = hash & table->bucket_msk; + /* Search key in table. Update value if exists */ + for (i = 0; i < K32V64_KEYS_PER_BUCKET; i++) { + if ((key == table->t[bucket].key[i]) && + (table->t[bucket].key_mask & (1 << i))) { + *old_value = table->t[bucket].val[i]; + *found = 1; + __atomic_fetch_add(&table->t[bucket].cnt, 1, + __ATOMIC_ACQUIRE); + table->t[bucket].val[i] = value; + __atomic_fetch_add(&table->t[bucket].cnt, 1, + __ATOMIC_RELEASE); + return 0; + } + } + + if (!SLIST_EMPTY(&table->t[bucket].head)) { + SLIST_FOREACH(ent, &table->t[bucket].head, next) { + if (ent->key == key) { + *old_value = ent->val; + *found = 1; + __atomic_fetch_add(&table->t[bucket].cnt, 1, + __ATOMIC_ACQUIRE); + ent->val = value; + __atomic_fetch_add(&table->t[bucket].cnt, 1, + __ATOMIC_RELEASE); + return 0; + } + } + } + + msk = ~table->t[bucket].key_mask & VALID_KEY_MSK; + if (msk) { + idx = __builtin_ctz(msk); + table->t[bucket].key[idx] = key; + table->t[bucket].val[idx] = value; + __atomic_or_fetch(&table->t[bucket].key_mask, 1 << idx, + __ATOMIC_RELEASE); + table->nb_ent++; + *found = 0; + return 0; + } + + ret = rte_mempool_get(table->ext_ent_pool, (void **)&ent); + if (ret < 0) + return ret; + + SLIST_NEXT(ent, next) = NULL; + ent->key = key; + ent->val = value; + rte_smp_wmb(); + SLIST_FOREACH(tmp, &table->t[bucket].head, next) + prev = tmp; + + if (prev == NULL) + SLIST_INSERT_HEAD(&table->t[bucket].head, ent, next); + else + SLIST_INSERT_AFTER(prev, ent, next); + + table->nb_ent++; + table->nb_ext_ent++; + *found = 0; + return 0; +} + +static int +k32v64_hash_delete(struct k32v64_hash_table *table, uint32_t key, + uint32_t hash, uint64_t *old_value) +{ + uint32_t bucket; + int i; + struct k32v64_ext_ent *ent; + + if (table == NULL) + return -EINVAL; + + bucket = hash & table->bucket_msk; + + for (i = 0; i < K32V64_KEYS_PER_BUCKET; i++) { + if ((key == table->t[bucket].key[i]) && + (table->t[bucket].key_mask & (1 << i))) { + *old_value = table->t[bucket].val[i]; + ent = SLIST_FIRST(&table->t[bucket].head); + if (ent) { + __atomic_fetch_add(&table->t[bucket].cnt, 1, + __ATOMIC_ACQUIRE); + table->t[bucket].key[i] = ent->key; + table->t[bucket].val[i] = ent->val; + SLIST_REMOVE_HEAD(&table->t[bucket].head, next); + __atomic_fetch_add(&table->t[bucket].cnt, 1, + __ATOMIC_RELEASE); + table->nb_ext_ent--; + } else + __atomic_and_fetch(&table->t[bucket].key_mask, + ~(1 << i), __ATOMIC_RELEASE); + if (ent) + rte_mempool_put(table->ext_ent_pool, ent); + table->nb_ent--; + return 0; + } + } + + SLIST_FOREACH(ent, &table->t[bucket].head, next) + if (ent->key == key) + break; + + if (ent == NULL) + return -ENOENT; + + *old_value = ent->val; + + __atomic_fetch_add(&table->t[bucket].cnt, 1, __ATOMIC_ACQUIRE); + SLIST_REMOVE(&table->t[bucket].head, ent, k32v64_ext_ent, next); + __atomic_fetch_add(&table->t[bucket].cnt, 1, __ATOMIC_RELEASE); + rte_mempool_put(table->ext_ent_pool, ent); + + table->nb_ext_ent--; + table->nb_ent--; + + return 0; +} + +static int +k32v64_modify(struct rte_kv_hash_table *table, void *key_p, uint32_t hash, + enum rte_kv_modify_op op, void *value_p, int *found) +{ + struct k32v64_hash_table *ht = (struct k32v64_hash_table *)table; + uint32_t *key = key_p; + uint64_t value; + + if ((ht == NULL) || (key == NULL) || (value_p == NULL) || + (found == NULL) || (op >= RTE_KV_MODIFY_OP_MAX)) { + return -EINVAL; + } + + value = *(uint64_t *)value_p; + switch (op) { + case RTE_KV_MODIFY_ADD: + return k32v64_hash_add(ht, *key, hash, value, value_p, found); + case RTE_KV_MODIFY_DEL: + return k32v64_hash_delete(ht, *key, hash, value_p); + default: + break; + } + + return -EINVAL; +} + +struct rte_kv_hash_table * +k32v64_hash_create(const struct rte_kv_hash_params *params) +{ + char hash_name[RTE_KV_HASH_NAMESIZE]; + struct k32v64_hash_table *ht = NULL; + uint32_t mem_size, nb_buckets, max_ent; + int ret; + struct rte_mempool *mp; + + if ((params == NULL) || (params->name == NULL) || + (params->entries == 0)) { + rte_errno = EINVAL; + return NULL; + } + + ret = snprintf(hash_name, sizeof(hash_name), "KV_%s", params->name); + if (ret < 0 || ret >= RTE_KV_HASH_NAMESIZE) { + rte_errno = ENAMETOOLONG; + return NULL; + } + + max_ent = rte_align32pow2(params->entries); + nb_buckets = max_ent / K32V64_KEYS_PER_BUCKET; + mem_size = sizeof(struct k32v64_hash_table) + + sizeof(struct k32v64_hash_bucket) * nb_buckets; + + mp = rte_mempool_create(hash_name, max_ent, + sizeof(struct k32v64_ext_ent), 0, 0, NULL, NULL, NULL, NULL, + params->socket_id, 0); + + if (mp == NULL) + return NULL; + + ht = rte_zmalloc_socket(hash_name, mem_size, + RTE_CACHE_LINE_SIZE, params->socket_id); + if (ht == NULL) { + rte_mempool_free(mp); + return NULL; + } + + memcpy(ht->pub.name, hash_name, sizeof(ht->pub.name)); + ht->max_ent = max_ent; + ht->bucket_msk = nb_buckets - 1; + ht->ext_ent_pool = mp; + ht->pub.lookup = get_lookup_bulk_fn(); + ht->pub.modify = k32v64_modify; + + return (struct rte_kv_hash_table *)ht; +} + +void +k32v64_hash_free(struct rte_kv_hash_table *ht) +{ + if (ht == NULL) + return; + + rte_mempool_free(((struct k32v64_hash_table *)ht)->ext_ent_pool); + rte_free(ht); +} diff --git a/lib/librte_hash/k32v64_hash.h b/lib/librte_hash/k32v64_hash.h new file mode 100644 index 0000000..10061a5 --- /dev/null +++ b/lib/librte_hash/k32v64_hash.h @@ -0,0 +1,98 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2020 Intel Corporation + */ + +#include + +#define K32V64_KEYS_PER_BUCKET 4 +#define K32V64_WRITE_IN_PROGRESS 1 +#define VALID_KEY_MSK ((1 << K32V64_KEYS_PER_BUCKET) - 1) + +struct k32v64_ext_ent { + SLIST_ENTRY(k32v64_ext_ent) next; + uint32_t key; + uint64_t val; +}; + +struct k32v64_hash_bucket { + uint32_t key[K32V64_KEYS_PER_BUCKET]; + uint64_t val[K32V64_KEYS_PER_BUCKET]; + uint8_t key_mask; + uint32_t cnt; + SLIST_HEAD(k32v64_list_head, k32v64_ext_ent) head; +} __rte_cache_aligned; + +struct k32v64_hash_table { + struct rte_kv_hash_table pub; /**< Public part */ + uint32_t nb_ent; /**< Number of entities in the table*/ + uint32_t nb_ext_ent; /**< Number of extended entities */ + uint32_t max_ent; /**< Maximum number of entities */ + uint32_t bucket_msk; + struct rte_mempool *ext_ent_pool; + __extension__ struct k32v64_hash_bucket t[0]; +}; + +typedef int (*k32v64_cmp_fn_t) +(struct k32v64_hash_bucket *bucket, uint32_t key, uint64_t *val); + +static inline int +__kv_cmp_keys(struct k32v64_hash_bucket *bucket, uint32_t key, + uint64_t *val) +{ + int i; + + for (i = 0; i < K32V64_KEYS_PER_BUCKET; i++) { + if ((key == bucket->key[i]) && + (bucket->key_mask & (1 << i))) { + *val = bucket->val[i]; + return 1; + } + } + + return 0; +} + +static inline int +__k32v64_hash_lookup(struct k32v64_hash_table *table, uint32_t key, + uint32_t hash, uint64_t *value, k32v64_cmp_fn_t cmp_f) +{ + uint64_t val = 0; + struct k32v64_ext_ent *ent; + uint32_t cnt; + int found = 0; + uint32_t bucket = hash & table->bucket_msk; + + do { + + do { + cnt = __atomic_load_n(&table->t[bucket].cnt, + __ATOMIC_ACQUIRE); + } while (unlikely(cnt & K32V64_WRITE_IN_PROGRESS)); + + found = cmp_f(&table->t[bucket], key, &val); + if (unlikely((found == 0) && + (!SLIST_EMPTY(&table->t[bucket].head)))) { + SLIST_FOREACH(ent, &table->t[bucket].head, next) { + if (ent->key == key) { + val = ent->val; + found = 1; + break; + } + } + } + __atomic_thread_fence(__ATOMIC_RELEASE); + } while (unlikely(cnt != __atomic_load_n(&table->t[bucket].cnt, + __ATOMIC_RELAXED))); + + if (found == 1) { + *value = val; + return 0; + } else + return -ENOENT; +} + +struct rte_kv_hash_table * +k32v64_hash_create(const struct rte_kv_hash_params *params); + +void +k32v64_hash_free(struct rte_kv_hash_table *ht); diff --git a/lib/librte_hash/k32v64_hash_avx512vl.c b/lib/librte_hash/k32v64_hash_avx512vl.c new file mode 100644 index 0000000..75cede5 --- /dev/null +++ b/lib/librte_hash/k32v64_hash_avx512vl.c @@ -0,0 +1,59 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2020 Intel Corporation + */ + +#include "k32v64_hash.h" + +int +k32v64_hash_bulk_lookup_avx512vl(struct rte_kv_hash_table *ht, void *keys_p, + uint32_t *hashes, void *values_p, unsigned int n); + +static inline int +k32v64_cmp_keys_avx512vl(struct k32v64_hash_bucket *bucket, uint32_t key, + uint64_t *val) +{ + __m128i keys, srch_key; + __mmask8 msk; + + keys = _mm_load_si128((void *)bucket); + srch_key = _mm_set1_epi32(key); + + msk = _mm_mask_cmpeq_epi32_mask(bucket->key_mask, keys, srch_key); + if (msk) { + *val = bucket->val[__builtin_ctz(msk)]; + return 1; + } + + return 0; +} + +static inline int +k32v64_hash_lookup_avx512vl(struct k32v64_hash_table *table, uint32_t key, + uint32_t hash, uint64_t *value) +{ + return __k32v64_hash_lookup(table, key, hash, value, + k32v64_cmp_keys_avx512vl); +} + +int +k32v64_hash_bulk_lookup_avx512vl(struct rte_kv_hash_table *ht, void *keys_p, + uint32_t *hashes, void *values_p, unsigned int n) +{ + struct k32v64_hash_table *table = (struct k32v64_hash_table *)ht; + uint32_t *keys = keys_p; + uint64_t *values = values_p; + int ret, cnt = 0; + unsigned int i; + + if (unlikely((table == NULL) || (keys == NULL) || (hashes == NULL) || + (values == NULL))) + return -EINVAL; + + for (i = 0; i < n; i++) { + ret = k32v64_hash_lookup_avx512vl(table, keys[i], hashes[i], + &values[i]); + if (ret == 0) + cnt++; + } + return cnt; +} diff --git a/lib/librte_hash/meson.build b/lib/librte_hash/meson.build index 6ab46ae..0d014ea 100644 --- a/lib/librte_hash/meson.build +++ b/lib/librte_hash/meson.build @@ -3,10 +3,23 @@ headers = files('rte_crc_arm64.h', 'rte_fbk_hash.h', + 'rte_kv_hash.h', 'rte_hash_crc.h', 'rte_hash.h', 'rte_jhash.h', 'rte_thash.h') -sources = files('rte_cuckoo_hash.c', 'rte_fbk_hash.c') -deps += ['ring'] +sources = files('rte_cuckoo_hash.c', 'rte_fbk_hash.c', 'rte_kv_hash.c', 'k32v64_hash.c') +deps += ['ring', 'mempool'] + +if dpdk_conf.has('RTE_ARCH_X86') + if cc.has_argument('-mavx512vl') + avx512_tmplib = static_library('avx512_tmp', + 'k32v64_hash_avx512vl.c', + dependencies: static_rte_mempool, + c_args: cflags + ['-mavx512vl']) + objs += avx512_tmplib.extract_objects('k32v64_hash_avx512vl.c') + cflags += '-DCC_AVX512VL_SUPPORT' + + endif +endif diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_version.map index c2a9094..614e0a5 100644 --- a/lib/librte_hash/rte_hash_version.map +++ b/lib/librte_hash/rte_hash_version.map @@ -36,5 +36,9 @@ EXPERIMENTAL { rte_hash_lookup_with_hash_bulk; rte_hash_lookup_with_hash_bulk_data; rte_hash_max_key_id; - + rte_kv_hash_create; + rte_kv_hash_find_existing; + rte_kv_hash_free; + rte_kv_hash_add; + rte_kv_hash_delete; }; diff --git a/lib/librte_hash/rte_kv_hash.c b/lib/librte_hash/rte_kv_hash.c new file mode 100644 index 0000000..03df8db --- /dev/null +++ b/lib/librte_hash/rte_kv_hash.c @@ -0,0 +1,184 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2020 Intel Corporation + */ + +#include + +#include +#include +#include +#include +#include + +#include +#include "k32v64_hash.h" + +TAILQ_HEAD(rte_kv_hash_list, rte_tailq_entry); + +static struct rte_tailq_elem rte_kv_hash_tailq = { + .name = "RTE_KV_HASH", +}; + +EAL_REGISTER_TAILQ(rte_kv_hash_tailq); + +int +rte_kv_hash_add(struct rte_kv_hash_table *table, void *key, + uint32_t hash, void *value, int *found) +{ + if (table == NULL) + return -EINVAL; + + return table->modify(table, key, hash, RTE_KV_MODIFY_ADD, + value, found); +} + +int +rte_kv_hash_delete(struct rte_kv_hash_table *table, void *key, + uint32_t hash, void *value) +{ + int found; + + if (table == NULL) + return -EINVAL; + + return table->modify(table, key, hash, RTE_KV_MODIFY_DEL, + value, &found); +} + +struct rte_kv_hash_table * +rte_kv_hash_find_existing(const char *name) +{ + struct rte_kv_hash_table *h = NULL; + struct rte_tailq_entry *te; + struct rte_kv_hash_list *kv_hash_list; + + kv_hash_list = RTE_TAILQ_CAST(rte_kv_hash_tailq.head, + rte_kv_hash_list); + + rte_mcfg_tailq_read_lock(); + TAILQ_FOREACH(te, kv_hash_list, next) { + h = (struct rte_kv_hash_table *) te->data; + if (strncmp(name, h->name, RTE_KV_HASH_NAMESIZE) == 0) + break; + } + rte_mcfg_tailq_read_unlock(); + if (te == NULL) { + rte_errno = ENOENT; + return NULL; + } + return h; +} + +struct rte_kv_hash_table * +rte_kv_hash_create(const struct rte_kv_hash_params *params) +{ + char hash_name[RTE_KV_HASH_NAMESIZE]; + struct rte_kv_hash_table *ht, *tmp_ht = NULL; + struct rte_tailq_entry *te; + struct rte_kv_hash_list *kv_hash_list; + int ret; + + if ((params == NULL) || (params->name == NULL) || + (params->entries == 0) || + (params->type >= RTE_KV_HASH_MAX)) { + rte_errno = EINVAL; + return NULL; + } + + kv_hash_list = RTE_TAILQ_CAST(rte_kv_hash_tailq.head, + rte_kv_hash_list); + + ret = snprintf(hash_name, sizeof(hash_name), "KV_%s", params->name); + if (ret < 0 || ret >= RTE_KV_HASH_NAMESIZE) { + rte_errno = ENAMETOOLONG; + return NULL; + } + + switch (params->type) { + case RTE_KV_HASH_K32V64: + ht = k32v64_hash_create(params); + break; + default: + rte_errno = EINVAL; + return NULL; + } + if (ht == NULL) + return ht; + + rte_mcfg_tailq_write_lock(); + TAILQ_FOREACH(te, kv_hash_list, next) { + tmp_ht = (struct rte_kv_hash_table *) te->data; + if (strncmp(params->name, tmp_ht->name, + RTE_KV_HASH_NAMESIZE) == 0) + break; + } + if (te != NULL) { + rte_errno = EEXIST; + goto exit; + } + + te = rte_zmalloc("KV_HASH_TAILQ_ENTRY", sizeof(*te), 0); + if (te == NULL) { + RTE_LOG(ERR, HASH, "Failed to allocate tailq entry\n"); + goto exit; + } + + ht->type = params->type; + te->data = (void *)ht; + TAILQ_INSERT_TAIL(kv_hash_list, te, next); + + rte_mcfg_tailq_write_unlock(); + + return ht; + +exit: + rte_mcfg_tailq_write_unlock(); + switch (params->type) { + case RTE_KV_HASH_K32V64: + k32v64_hash_free(ht); + break; + default: + break; + } + return NULL; +} + +void +rte_kv_hash_free(struct rte_kv_hash_table *ht) +{ + struct rte_tailq_entry *te; + struct rte_kv_hash_list *kv_hash_list; + + if (ht == NULL) + return; + + kv_hash_list = RTE_TAILQ_CAST(rte_kv_hash_tailq.head, + rte_kv_hash_list); + + rte_mcfg_tailq_write_lock(); + + /* find out tailq entry */ + TAILQ_FOREACH(te, kv_hash_list, next) { + if (te->data == (void *) ht) + break; + } + + + if (te == NULL) { + rte_mcfg_tailq_write_unlock(); + return; + } + + TAILQ_REMOVE(kv_hash_list, te, next); + + rte_mcfg_tailq_write_unlock(); + + switch (ht->type) { + case RTE_KV_HASH_K32V64: + k32v64_hash_free(ht); + break; + default: + break; + } + rte_free(te); +} diff --git a/lib/librte_hash/rte_kv_hash.h b/lib/librte_hash/rte_kv_hash.h new file mode 100644 index 0000000..c0375d1 --- /dev/null +++ b/lib/librte_hash/rte_kv_hash.h @@ -0,0 +1,169 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2020 Intel Corporation + */ + +#ifndef _RTE_KV_HASH_H_ +#define _RTE_KV_HASH_H_ + +#ifdef __cplusplus +extern "C" { +#endif + +#include +#include +#include + +#define RTE_KV_HASH_NAMESIZE 32 + +enum rte_kv_hash_type { + RTE_KV_HASH_K32V64, + RTE_KV_HASH_MAX +}; + +enum rte_kv_modify_op { + RTE_KV_MODIFY_ADD, + RTE_KV_MODIFY_DEL, + RTE_KV_MODIFY_OP_MAX +}; + +struct rte_kv_hash_params { + const char *name; + uint32_t entries; + int socket_id; + enum rte_kv_hash_type type; +}; + +struct rte_kv_hash_table; + +typedef int (*rte_kv_hash_bulk_lookup_t) +(struct rte_kv_hash_table *table, void *keys, uint32_t *hashes, + void *values, unsigned int n); + +typedef int (*rte_kv_hash_modify_t) +(struct rte_kv_hash_table *table, void *key, uint32_t hash, + enum rte_kv_modify_op op, void *value, int *found); + +struct rte_kv_hash_table { + char name[RTE_KV_HASH_NAMESIZE]; /**< Name of the hash. */ + rte_kv_hash_bulk_lookup_t lookup; + rte_kv_hash_modify_t modify; + enum rte_kv_hash_type type; +}; + +/** + * Lookup bulk of keys. + * This function is multi-thread safe with regarding to other lookup threads. + * + * @param table + * Hash table to add the key to. + * @param keys + * Pointer to array of keys + * @param hashes + * Pointer to array of hash values associated with keys. + * @param values + * Pointer to array of value corresponded to keys + * If the key was not found the corresponding value remains intact. + * @param n + * Number of keys to lookup in batch. + * @return + * -EINVAL if there's an error, otherwise number of successful lookups. + */ +static inline int +rte_kv_hash_bulk_lookup(struct rte_kv_hash_table *table, + void *keys, uint32_t *hashes, void *values, unsigned int n) +{ + return table->lookup(table, keys, hashes, values, n); +} + +/** + * Add a key to an existing hash table with hash value. + * This operation is not multi-thread safe regarding to add/delete functions + * and should only be called from one thread. + * However it is safe to call it along with lookup. + * + * @param table + * Hash table to add the key to. + * @param key + * Key to add to the hash table. + * @param value + * Value to associate with key. + * @param hash + * Hash value associated with key. + * @found + * 0 if no previously added key was found + * 1 previously added key was found, old value associated with the key + * was written to *value + * @return + * 0 if ok, or negative value on error. + */ +__rte_experimental +int +rte_kv_hash_add(struct rte_kv_hash_table *table, void *key, + uint32_t hash, void *value, int *found); + +/** + * Remove a key with a given hash value from an existing hash table. + * This operation is not multi-thread safe regarding to add/delete functions + * and should only be called from one thread. + * However it is safe to call it along with lookup. + * + * @param table + * Hash table to remove the key from. + * @param key + * Key to remove from the hash table. + * @param hash + * hash value associated with key. + * @param value + * pointer to memory where the old value will be written to on success + * @return + * 0 if ok, or negative value on error. + */ +__rte_experimental +int +rte_kv_hash_delete(struct rte_kv_hash_table *table, void *key, + uint32_t hash, void *value); + +/** + * Performs a lookup for an existing hash table, and returns a pointer to + * the table if found. + * + * @param name + * Name of the hash table to find + * + * @return + * pointer to hash table structure or NULL on error with rte_errno + * set appropriately. + */ +__rte_experimental +struct rte_kv_hash_table * +rte_kv_hash_find_existing(const char *name); + +/** + * Create a new hash table for use with four byte keys. + * + * @param params + * Parameters used in creation of hash table. + * + * @return + * Pointer to hash table structure that is used in future hash table + * operations, or NULL on error with rte_errno set appropriately. + */ +__rte_experimental +struct rte_kv_hash_table * +rte_kv_hash_create(const struct rte_kv_hash_params *params); + +/** + * Free all memory used by a hash table. + * + * @param table + * Hash table to deallocate. + */ +__rte_experimental +void +rte_kv_hash_free(struct rte_kv_hash_table *table); + +#ifdef __cplusplus +} +#endif + +#endif /* _RTE_KV_HASH_H_ */ From patchwork Fri May 8 19:58:51 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: "Medvedkin, Vladimir" X-Patchwork-Id: 70013 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 1ED8CA0352; Fri, 8 May 2020 21:59:19 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id DF9CB1DA49; Fri, 8 May 2020 21:59:04 +0200 (CEST) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id 057511DA1C for ; Fri, 8 May 2020 21:59:00 +0200 (CEST) IronPort-SDR: yuHXyVK5fVcs3KhJqvdt0vqPay633CS7yc3/GsDjk3jzdLRa+l0HPF1CzMoIUf2ylcmS44ixsx lolr3TQuMVmw== X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga004.fm.intel.com ([10.253.24.48]) by orsmga102.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 08 May 2020 12:59:00 -0700 IronPort-SDR: 8SxWuMT+fUEUstK+648IyUVe5pKHAEmd0EHEI5FBHNPOLXTDT7vEj5hdjRYHxQ1dtmq8FqPveT 8FOScgq4shzA== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.73,368,1583222400"; d="scan'208";a="285584888" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by fmsmga004.fm.intel.com with ESMTP; 08 May 2020 12:58:59 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: konstantin.ananyev@intel.com, yipeng1.wang@intel.com, sameh.gobriel@intel.com, bruce.richardson@intel.com Date: Fri, 8 May 2020 20:58:51 +0100 Message-Id: X-Mailer: git-send-email 2.7.4 In-Reply-To: References: MIME-Version: 1.0 In-Reply-To: References: Subject: [dpdk-dev] [PATCH v4 2/4] hash: add documentation for kv hash library X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Add programmers guide and doxygen API for kv hash library Signed-off-by: Vladimir Medvedkin --- doc/api/doxy-api-index.md | 1 + doc/guides/prog_guide/index.rst | 1 + doc/guides/prog_guide/kv_hash_lib.rst | 66 +++++++++++++++++++++++++++++++++++ 3 files changed, 68 insertions(+) create mode 100644 doc/guides/prog_guide/kv_hash_lib.rst diff --git a/doc/api/doxy-api-index.md b/doc/api/doxy-api-index.md index 93f0d93..eade5f5 100644 --- a/doc/api/doxy-api-index.md +++ b/doc/api/doxy-api-index.md @@ -121,6 +121,7 @@ The public API headers are grouped by topics: [jhash] (@ref rte_jhash.h), [thash] (@ref rte_thash.h), [FBK hash] (@ref rte_fbk_hash.h), + [KV hash] (@ref rte_kv_hash.h), [CRC hash] (@ref rte_hash_crc.h) - **classification** diff --git a/doc/guides/prog_guide/index.rst b/doc/guides/prog_guide/index.rst index f0ae3c1..28ddb2b 100644 --- a/doc/guides/prog_guide/index.rst +++ b/doc/guides/prog_guide/index.rst @@ -31,6 +31,7 @@ Programmer's Guide link_bonding_poll_mode_drv_lib timer_lib hash_lib + kv_hash_lib efd_lib member_lib lpm_lib diff --git a/doc/guides/prog_guide/kv_hash_lib.rst b/doc/guides/prog_guide/kv_hash_lib.rst new file mode 100644 index 0000000..44ed99a --- /dev/null +++ b/doc/guides/prog_guide/kv_hash_lib.rst @@ -0,0 +1,66 @@ +.. SPDX-License-Identifier: BSD-3-Clause + Copyright(c) 2020 Intel Corporation. + +.. _kv_hash_Library: + +KV Hash Library +=================== + +This hash library implementation is intended to be better optimized for some fixed key-value sizes when compared to existing Cuckoo hash-based rte_hash implementation. At the moment it supports 32-bit keys and 64 bit values. Current rte_fbk implementation is pretty fast but it has a number of drawbacks such as 2 byte values and limited collision resolving capabilities. rte_hash (which is based on Cuckoo hash algorithm) doesn't have these drawbacks, but it comes at a cost of lower performance compared to rte_fbk. + +The following flow illustrates the source of performance penalties of Cuckoo hash: + +* Loading two buckets at once (extra memory consumption) +* Сomparing signatures first (extra step before key comparison) +* If signature comparison hits, get a key index, find memory location with a key itself, and get the key (memory pressure and indirection) +* Using indirect call to memcmp() to compare two uint32_t (function call overhead) + +KV hash table doesn't have the drawbacks associated with rte_fbk while offering the same performance as rte_fbk. The bucket contains 4 consecutive keys which can be compared very quickly, and subsequent keys are kept in a linked list. + +The main disadvantage compared to rte_hash is performance degradation with high average table utilization due to chain resolving for 5th and subsequent collisions. + +To estimate the probability of 5th collision we can use "birthday paradox" approach. We can figure out the number of insertions (can be treated as a load factor) that will likely yield a 50% probability of 5th collision for a given number of buckets. + +It could be calculated with an asymptotic formula from [1]: + +E(n, k) ~= (k!)^(1/k)*Γ(1 + 1/k)*n^(1-1/k), n -> inf + +,where + +k - level of collision + +n - number of buckets + +Г - gamma function + +So, for k = 5 (5th collision), and given the fact that number of buckets is a power of 2, we can simplify formula: + +E(n) = 2.392 * 2^(m * 4/5) , where number of buckets n = 2^m + +.. note:: + + You can calculate it by yourself using Wolfram Alpha [2]. For example for 8k buckets: + + solve ((k!)^(1/k)*Γ(1 + 1/k)*n^(1-1/k), n = 8192, k = 5) + + +API Overview +----------------- + +The main configuration parameters for the hash table are: + +* Total number of hash entries in the table +* Socket id + +KV hash is "hash function-less", so user must specify precalculated hash value for every key. The main methods exported by the Hash Library are: + +* Add entry with key and precomputed hash: The key, precomputed hash and value are provided as input. +* Delete entry with key and precomputed hash: The key and precomputed hash are provided as input. +* Lookup entry with key and precomputed hash: The key, precomputed hash and a pointer to expected value are provided as input. If an entry with the specified key is found in the hash table (i.e. lookup hit), then the value associated with the key will be written to the memory specified by the pointer, and the function will return 0; otherwise (i.e. a lookup miss) a negative value is returned, and memory described by the pointer is not modified. + +References +---------- + +[1] M.S. Klamkin and D.J. Newman, Extensions of the Birthday Surprise + +[2] https://www.wolframalpha.com/ From patchwork Fri May 8 19:58:52 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Medvedkin, Vladimir" X-Patchwork-Id: 70014 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id CC826A0352; Fri, 8 May 2020 21:59:28 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id C34B21DA68; Fri, 8 May 2020 21:59:06 +0200 (CEST) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id 7E8CE1DA2B for ; Fri, 8 May 2020 21:59:02 +0200 (CEST) IronPort-SDR: qhg/P/K4+VETq5TMO5CNPaMyzrIFhxSyJVA7xYXZNJPKRErS3ViEPHef5lDX4IpUZMZPEep/ab ouPfMCiMxo5g== X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga004.fm.intel.com ([10.253.24.48]) by orsmga102.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 08 May 2020 12:59:02 -0700 IronPort-SDR: bx87CJo7Z5OQgogdrDIIppUO1z5RLKA1saaU/m5dih5iw+MslvlaOvN6sjJ6GjrPeZd4nvOSHK 3rCJ5Fv9GFkA== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.73,368,1583222400"; d="scan'208";a="285584899" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by fmsmga004.fm.intel.com with ESMTP; 08 May 2020 12:59:00 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: konstantin.ananyev@intel.com, yipeng1.wang@intel.com, sameh.gobriel@intel.com, bruce.richardson@intel.com Date: Fri, 8 May 2020 20:58:52 +0100 Message-Id: <79e3e7c72c0b72c45ee6a9ac3c8a6268417157aa.1588967562.git.vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH v4 3/4] test: add kv hash autotests X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Add autotests for rte_kv_hash library Signed-off-by: Vladimir Medvedkin --- app/test/Makefile | 1 + app/test/autotest_data.py | 12 +++ app/test/meson.build | 3 + app/test/test_kv_hash.c | 242 ++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 258 insertions(+) create mode 100644 app/test/test_kv_hash.c diff --git a/app/test/Makefile b/app/test/Makefile index 4e8ecab..298650f 100644 --- a/app/test/Makefile +++ b/app/test/Makefile @@ -73,6 +73,7 @@ SRCS-y += test_bitmap.c SRCS-y += test_reciprocal_division.c SRCS-y += test_reciprocal_division_perf.c SRCS-y += test_fbarray.c +SRCS-y += test_kv_hash.c SRCS-y += test_external_mem.c SRCS-y += test_rand_perf.c diff --git a/app/test/autotest_data.py b/app/test/autotest_data.py index 7b1d013..a1351b7 100644 --- a/app/test/autotest_data.py +++ b/app/test/autotest_data.py @@ -99,6 +99,18 @@ "Report": None, }, { + "Name": "KV hash autotest", + "Command": "kv_hash_autotest", + "Func": default_autotest, + "Report": None, + }, + { + "Name": "KV hash autotest", + "Command": "kv_hash_slow_autotest", + "Func": default_autotest, + "Report": None, + }, + { "Name": "LPM autotest", "Command": "lpm_autotest", "Func": default_autotest, diff --git a/app/test/meson.build b/app/test/meson.build index f8ed9d8..8740255 100644 --- a/app/test/meson.build +++ b/app/test/meson.build @@ -45,6 +45,7 @@ test_sources = files('commands.c', 'test_eventdev.c', 'test_external_mem.c', 'test_fbarray.c', + 'test_kv_hash.c', 'test_fib.c', 'test_fib_perf.c', 'test_fib6.c', @@ -203,6 +204,7 @@ fast_tests = [ ['hash_autotest', true], ['interrupt_autotest', true], ['ipfrag_autotest', false], + ['kv_hash_autotest', true], ['logs_autotest', true], ['lpm_autotest', true], ['lpm6_autotest', true], @@ -291,6 +293,7 @@ perf_test_names = [ 'hash_readwrite_perf_autotest', 'hash_readwrite_lf_perf_autotest', 'trace_perf_autotest', + 'kv_hash_slow_autotest', ] driver_test_names = [ diff --git a/app/test/test_kv_hash.c b/app/test/test_kv_hash.c new file mode 100644 index 0000000..646bead --- /dev/null +++ b/app/test/test_kv_hash.c @@ -0,0 +1,242 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2020 Intel Corporation + */ + +#include +#include +#include + +#include +#include +#include + +#include "test.h" + +typedef int32_t (*rte_kv_hash_test)(void); + +static int32_t test_create_invalid(void); +static int32_t test_multiple_create(void); +static int32_t test_free_null(void); +static int32_t test_add_del_invalid(void); +static int32_t test_basic(void); + +#define MAX_ENT (1 << 22) + +/* + * Check that rte_kv_hash_create fails gracefully for incorrect user input + * arguments + */ +int32_t +test_create_invalid(void) +{ + struct rte_kv_hash_table *kv_hash = NULL; + struct rte_kv_hash_params config; + + config.name = "test_kv_hash"; + config.socket_id = rte_socket_id(); + config.entries = MAX_ENT; + config.type = RTE_KV_HASH_K32V64; + + /* rte_kv_hash_create: kv_hash name == NULL */ + config.name = NULL; + kv_hash = rte_kv_hash_create(&config); + RTE_TEST_ASSERT(kv_hash == NULL, + "Call succeeded with invalid parameters\n"); + config.name = "test_kv_hash"; + + /* rte_kv_hash_create: config == NULL */ + kv_hash = rte_kv_hash_create(NULL); + RTE_TEST_ASSERT(kv_hash == NULL, + "Call succeeded with invalid parameters\n"); + + /* socket_id < -1 is invalid */ + config.socket_id = -2; + kv_hash = rte_kv_hash_create(&config); + RTE_TEST_ASSERT(kv_hash == NULL, + "Call succeeded with invalid parameters\n"); + config.socket_id = rte_socket_id(); + + /* rte_kv_hash_create: entries = 0 */ + config.entries = 0; + kv_hash = rte_kv_hash_create(&config); + RTE_TEST_ASSERT(kv_hash == NULL, + "Call succeeded with invalid parameters\n"); + config.entries = MAX_ENT; + + /* rte_kv_hash_create: invalid type*/ + config.type = RTE_KV_HASH_MAX; + kv_hash = rte_kv_hash_create(&config); + RTE_TEST_ASSERT(kv_hash == NULL, + "Call succeeded with invalid parameters\n"); + + return TEST_SUCCESS; +} + +/* + * Create kv_hash table then delete kv_hash table 10 times + * Use a slightly different rules size each time + */ +#include +int32_t +test_multiple_create(void) +{ + struct rte_kv_hash_table *kv_hash = NULL; + struct rte_kv_hash_params config; + int32_t i; + + for (i = 0; i < 100; i++) { + config.name = "test_kv_hash"; + config.socket_id = -1; + config.entries = MAX_ENT - i; + config.type = RTE_KV_HASH_K32V64; + + kv_hash = rte_kv_hash_create(&config); + RTE_TEST_ASSERT(kv_hash != NULL, + "Failed to create kv hash\n"); + rte_kv_hash_free(kv_hash); + } + + return TEST_SUCCESS; +} + +/* + * Call rte_kv_hash_free for NULL pointer user input. + * Note: free has no return and therefore it is impossible + * to check for failure but this test is added to + * increase function coverage metrics and to validate that + * freeing null does not crash. + */ +int32_t +test_free_null(void) +{ + struct rte_kv_hash_table *kv_hash = NULL; + struct rte_kv_hash_params config; + + config.name = "test_kv"; + config.socket_id = -1; + config.entries = MAX_ENT; + config.type = RTE_KV_HASH_K32V64; + + kv_hash = rte_kv_hash_create(&config); + RTE_TEST_ASSERT(kv_hash != NULL, "Failed to create kv hash\n"); + + rte_kv_hash_free(kv_hash); + rte_kv_hash_free(NULL); + return TEST_SUCCESS; +} + +/* + * Check that rte_kv_hash_add fails gracefully for + * incorrect user input arguments + */ +int32_t +test_add_del_invalid(void) +{ + uint32_t key = 10; + uint64_t val = 20; + int ret, found; + + /* rte_kv_hash_add: kv_hash == NULL */ + ret = rte_kv_hash_add(NULL, &key, rte_hash_crc_4byte(key, 0), + &val, &found); + RTE_TEST_ASSERT(ret == -EINVAL, + "Call succeeded with invalid parameters\n"); + + /* rte_kv_hash_delete: kv_hash == NULL */ + ret = rte_kv_hash_delete(NULL, &key, rte_hash_crc_4byte(key, 0), &val); + RTE_TEST_ASSERT(ret == -EINVAL, + "Call succeeded with invalid parameters\n"); + + return TEST_SUCCESS; +} + +/* + * Call add, lookup and delete for a single rule + */ +int32_t +test_basic(void) +{ + struct rte_kv_hash_table *kv_hash = NULL; + struct rte_kv_hash_params config; + uint32_t key = 10; + uint64_t value = 20; + uint64_t ret_val = 0; + int ret, found; + uint32_t hash_sig; + + config.name = "test_kv"; + config.socket_id = -1; + config.entries = MAX_ENT; + config.type = RTE_KV_HASH_K32V64; + + kv_hash = rte_kv_hash_create(&config); + RTE_TEST_ASSERT(kv_hash != NULL, "Failed to create kv hash\n"); + + hash_sig = rte_hash_crc_4byte(key, 0); + ret = rte_kv_hash_bulk_lookup(kv_hash, &key, + &hash_sig, &ret_val, 1); + RTE_TEST_ASSERT(ret == 0, "Lookup return incorrect result\n"); + + ret = rte_kv_hash_delete(kv_hash, &key, hash_sig, &ret_val); + RTE_TEST_ASSERT(ret == -ENOENT, "Delete return incorrect result\n"); + + ret = rte_kv_hash_add(kv_hash, &key, hash_sig, &value, &found); + RTE_TEST_ASSERT(ret == 0, "Can not add key into the table\n"); + + ret = rte_kv_hash_bulk_lookup(kv_hash, &key, + &hash_sig, &ret_val, 1); + RTE_TEST_ASSERT(((ret == 1) && (value == ret_val)), + "Lookup return incorrect result\n"); + + ret = rte_kv_hash_delete(kv_hash, &key, hash_sig, &ret_val); + RTE_TEST_ASSERT(ret == 0, "Can not delete key from table\n"); + + ret = rte_kv_hash_bulk_lookup(kv_hash, &key, + &hash_sig, &ret_val, 1); + RTE_TEST_ASSERT(ret == 0, "Lookup return incorrect result\n"); + + rte_kv_hash_free(kv_hash); + + return TEST_SUCCESS; +} + +static struct unit_test_suite kv_hash_tests = { + .suite_name = "kv_hash autotest", + .setup = NULL, + .teardown = NULL, + .unit_test_cases = { + TEST_CASE(test_create_invalid), + TEST_CASE(test_free_null), + TEST_CASE(test_add_del_invalid), + TEST_CASE(test_basic), + TEST_CASES_END() + } +}; + +static struct unit_test_suite kv_hash_slow_tests = { + .suite_name = "kv_hash slow autotest", + .setup = NULL, + .teardown = NULL, + .unit_test_cases = { + TEST_CASE(test_multiple_create), + TEST_CASES_END() + } +}; + +/* + * Do all unit tests. + */ +static int +test_kv_hash(void) +{ + return unit_test_suite_runner(&kv_hash_tests); +} + +static int +test_slow_kv_hash(void) +{ + return unit_test_suite_runner(&kv_hash_slow_tests); +} + +REGISTER_TEST_COMMAND(kv_hash_autotest, test_kv_hash); +REGISTER_TEST_COMMAND(kv_hash_slow_autotest, test_slow_kv_hash); From patchwork Fri May 8 19:58:53 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Medvedkin, Vladimir" X-Patchwork-Id: 70015 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 1682CA0352; Fri, 8 May 2020 21:59:37 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 0B43A1DA75; Fri, 8 May 2020 21:59:08 +0200 (CEST) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id E73511DA3F for ; Fri, 8 May 2020 21:59:03 +0200 (CEST) IronPort-SDR: T18bwIimZQMe9pmlF2T+GQgrXI7wt0pTO6N4yMT9IF4u6reqYdFg2I/YKn8uB3DR2O9qspCcDg DKcFgGf861vQ== X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga004.fm.intel.com ([10.253.24.48]) by orsmga102.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 08 May 2020 12:59:03 -0700 IronPort-SDR: UCm/PZjVKwfO6LgAVU8H7KcyZrUwxQFpPdyNBGKzWWPOOpm0Sp0ecQ69Cg8m31KkhPeThUjpqV AomA1gRQtmIA== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.73,368,1583222400"; d="scan'208";a="285584905" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by fmsmga004.fm.intel.com with ESMTP; 08 May 2020 12:59:02 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: konstantin.ananyev@intel.com, yipeng1.wang@intel.com, sameh.gobriel@intel.com, bruce.richardson@intel.com Date: Fri, 8 May 2020 20:58:53 +0100 Message-Id: X-Mailer: git-send-email 2.7.4 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH v4 4/4] test: add kv perf tests X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Add performance tests for rte_kv_hash Signed-off-by: Vladimir Medvedkin --- app/test/test_hash_perf.c | 111 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 111 insertions(+) diff --git a/app/test/test_hash_perf.c b/app/test/test_hash_perf.c index 76cdac5..3d4c13d 100644 --- a/app/test/test_hash_perf.c +++ b/app/test/test_hash_perf.c @@ -12,8 +12,10 @@ #include #include #include +#include #include #include +#include #include "test.h" @@ -29,6 +31,8 @@ #define NUM_SHUFFLES 10 #define BURST_SIZE 16 +#define CRC_INIT_VAL 0xdeadbeef + enum operations { ADD = 0, LOOKUP, @@ -719,6 +723,110 @@ fbk_hash_perf_test(void) return 0; } +static uint32_t * +shuf_arr(uint32_t *arr, int n, int l) +{ + int i, j; + uint32_t tmp; + uint32_t *ret_arr; + + ret_arr = rte_zmalloc(NULL, l * sizeof(uint32_t), 0); + for (i = 0; i < n; i++) { + j = rte_rand() % n; + tmp = arr[j]; + arr[j] = arr[i]; + arr[i] = tmp; + } + for (i = 0; i < l; i++) + ret_arr[i] = arr[i % n]; + + return ret_arr; +} + +static int +kv_hash_perf_test(void) +{ + struct rte_kv_hash_params params = { + .name = "kv_hash_test", + .entries = ENTRIES * 2, + .socket_id = rte_socket_id(), + .type = RTE_KV_HASH_K32V64, + }; + struct rte_kv_hash_table *handle = NULL; + uint32_t *keys; + uint32_t *lookup_keys; + uint64_t lookup_time = 0; + uint64_t begin; + uint64_t end; + unsigned int added = 0; + uint32_t key, hash_sig; + uint16_t val; + unsigned int i, j, k; + int found, ret = 0; + uint32_t hashes[64]; + uint64_t vals[64]; + + handle = rte_kv_hash_create(¶ms); + if (handle == NULL) { + printf("Error creating table\n"); + return -1; + } + + keys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0); + if (keys == NULL) { + printf("fbk hash: memory allocation for key store failed\n"); + return -1; + } + + /* Generate random keys and values. */ + for (i = 0; i < ENTRIES; i++) { + key = (uint32_t)rte_rand(); + val = rte_rand(); + hash_sig = rte_hash_crc_4byte(key, CRC_INIT_VAL); + + if (rte_kv_hash_add(handle, &key, hash_sig, &val, + &found) == 0) { + keys[added] = key; + added++; + } + } + + lookup_keys = shuf_arr(keys, added, TEST_SIZE); + + lookup_time = 0; + for (i = 0; i < TEST_ITERATIONS; i++) { + + begin = rte_rdtsc(); + /* Do lookups */ + + for (j = 0; j < TEST_SIZE; j += 64) { + for (k = 0; k < 64; k++) { + hashes[k] = + rte_hash_crc_4byte(lookup_keys[j + k], + CRC_INIT_VAL); + } + + ret += rte_kv_hash_bulk_lookup(handle, + &lookup_keys[j], hashes, vals, 64); + } + + end = rte_rdtsc(); + lookup_time += (double)(end - begin); + } + + printf("\n\n *** KV Hash function performance test results ***\n"); + if (ret != 0) + printf("Number of ticks per bulk lookup = %g\n", + (double)lookup_time / + ((double)TEST_ITERATIONS * (double)TEST_SIZE)); + + rte_free(keys); + rte_free(lookup_keys); + rte_kv_hash_free(handle); + + return 0; +} + static int test_hash_perf(void) { @@ -746,6 +854,9 @@ test_hash_perf(void) if (fbk_hash_perf_test() < 0) return -1; + if (kv_hash_perf_test() < 0) + return -1; + return 0; }