From patchwork Wed Apr 15 18:17:24 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 68577 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 D26AAA0563; Wed, 15 Apr 2020 20:17:39 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 1CA7D1D9C7; Wed, 15 Apr 2020 20:17:36 +0200 (CEST) Received: from mga12.intel.com (mga12.intel.com [192.55.52.136]) by dpdk.org (Postfix) with ESMTP id E4DD31C1B1 for ; Wed, 15 Apr 2020 20:17:32 +0200 (CEST) IronPort-SDR: 7boYSaw10P4iOc2vV339ke1/aSb0VEmCKEp2QvzUzuKY8MV6tYhdxhrjro/b7XavjD52S/G94w HbkRwSMHL9Qw== X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga004.fm.intel.com ([10.253.24.48]) by fmsmga106.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 15 Apr 2020 11:17:32 -0700 IronPort-SDR: LYC/uRUx8MZEAUQxXI2kYgnl6zBXUH/yAPZ8LQj9csAij0D/C7FiNVr3qOIkieVGPUo6BSYSlT 3D7N3YfQyKbA== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.72,388,1580803200"; d="scan'208";a="277702356" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by fmsmga004.fm.intel.com with ESMTP; 15 Apr 2020 11:17:30 -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: Wed, 15 Apr 2020 19:17:24 +0100 Message-Id: <0e767e9171c4e90d57ec06b50d6bf3b7d79828b1.1586974411.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 v3 1/4] hash: add k32v64 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" K32V64 hash is a hash table that 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 | 13 +- lib/librte_hash/k32v64_hash_avx512vl.c | 56 ++++++ lib/librte_hash/meson.build | 17 +- lib/librte_hash/rte_hash_version.map | 6 +- lib/librte_hash/rte_k32v64_hash.c | 315 +++++++++++++++++++++++++++++++++ lib/librte_hash/rte_k32v64_hash.h | 211 ++++++++++++++++++++++ 7 files changed, 615 insertions(+), 5 deletions(-) create mode 100644 lib/librte_hash/k32v64_hash_avx512vl.c create mode 100644 lib/librte_hash/rte_k32v64_hash.c create mode 100644 lib/librte_hash/rte_k32v64_hash.h diff --git a/lib/Makefile b/lib/Makefile index 46b91ae..a8c02e4 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..023689d 100644 --- a/lib/librte_hash/Makefile +++ b/lib/librte_hash/Makefile @@ -8,13 +8,14 @@ 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_k32v64_hash.c # install this header file SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include := rte_hash.h @@ -27,5 +28,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_k32v64_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_rte_k32v64_hash.o += -DCC_AVX512VL_SUPPORT +endif include $(RTE_SDK)/mk/rte.lib.mk diff --git a/lib/librte_hash/k32v64_hash_avx512vl.c b/lib/librte_hash/k32v64_hash_avx512vl.c new file mode 100644 index 0000000..7c70dd2 --- /dev/null +++ b/lib/librte_hash/k32v64_hash_avx512vl.c @@ -0,0 +1,56 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2020 Intel Corporation + */ + +#include + +int +k32v64_hash_bulk_lookup_avx512vl(struct rte_k32v64_hash_table *table, + uint32_t *keys, uint32_t *hashes, uint64_t *values, unsigned int n); + +static inline int +k32v64_cmp_keys_avx512vl(struct rte_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 rte_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_k32v64_hash_table *table, + uint32_t *keys, uint32_t *hashes, uint64_t *values, unsigned int n) +{ + 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..8a37cc4 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_k32v64_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_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 a8fbbc3..9a4f2f6 100644 --- a/lib/librte_hash/rte_hash_version.map +++ b/lib/librte_hash/rte_hash_version.map @@ -34,5 +34,9 @@ EXPERIMENTAL { rte_hash_free_key_with_position; rte_hash_max_key_id; - + rte_k32v64_hash_create; + rte_k32v64_hash_find_existing; + rte_k32v64_hash_free; + rte_k32v64_hash_add; + rte_k32v64_hash_delete; }; diff --git a/lib/librte_hash/rte_k32v64_hash.c b/lib/librte_hash/rte_k32v64_hash.c new file mode 100644 index 0000000..7ed94b4 --- /dev/null +++ b/lib/librte_hash/rte_k32v64_hash.c @@ -0,0 +1,315 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2020 Intel Corporation + */ + +#include + +#include +#include +#include +#include +#include + +#include + +TAILQ_HEAD(rte_k32v64_hash_list, rte_tailq_entry); + +static struct rte_tailq_elem rte_k32v64_hash_tailq = { + .name = "RTE_K32V64_HASH", +}; + +EAL_REGISTER_TAILQ(rte_k32v64_hash_tailq); + +#define VALID_KEY_MSK ((1 << RTE_K32V64_KEYS_PER_BUCKET) - 1) + +#ifdef CC_AVX512VL_SUPPORT +int +k32v64_hash_bulk_lookup_avx512vl(struct rte_k32v64_hash_table *table, + uint32_t *keys, uint32_t *hashes, uint64_t *values, unsigned int n); +#endif + +static int +k32v64_hash_bulk_lookup(struct rte_k32v64_hash_table *table, uint32_t *keys, + uint32_t *hashes, uint64_t *values, unsigned int n) +{ + 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 = rte_k32v64_hash_lookup(table, keys[i], hashes[i], + &values[i]); + if (ret == 0) + cnt++; + } + return cnt; +} + +static rte_k32v64_hash_bulk_lookup_t +get_lookup_bulk_fn(void) +{ +#ifdef CC_AVX512VL_SUPPORT + if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX512F)) + return k32v64_hash_bulk_lookup_avx512vl; +#endif + return k32v64_hash_bulk_lookup; +} + +int +rte_k32v64_hash_add(struct rte_k32v64_hash_table *table, uint32_t key, + uint32_t hash, uint64_t value) +{ + uint32_t bucket; + int i, idx, ret; + uint8_t msk; + struct rte_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 < RTE_K32V64_KEYS_PER_BUCKET; i++) { + if ((key == table->t[bucket].key[i]) && + (table->t[bucket].key_mask & (1 << i))) { + table->t[bucket].val[i] = value; + return 0; + } + } + + if (!SLIST_EMPTY(&table->t[bucket].head)) { + SLIST_FOREACH(ent, &table->t[bucket].head, next) { + if (ent->key == key) { + ent->val = value; + 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; + rte_smp_wmb(); + table->t[bucket].key_mask |= 1 << idx; + table->nb_ent++; + 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++; + return 0; +} + +int +rte_k32v64_hash_delete(struct rte_k32v64_hash_table *table, uint32_t key, + uint32_t hash) +{ + uint32_t bucket; + int i; + struct rte_k32v64_ext_ent *ent; + + if (table == NULL) + return -EINVAL; + + bucket = hash & table->bucket_msk; + + for (i = 0; i < RTE_K32V64_KEYS_PER_BUCKET; i++) { + if ((key == table->t[bucket].key[i]) && + (table->t[bucket].key_mask & (1 << i))) { + ent = SLIST_FIRST(&table->t[bucket].head); + if (ent) { + rte_atomic32_inc(&table->t[bucket].cnt); + table->t[bucket].key[i] = ent->key; + table->t[bucket].val[i] = ent->val; + SLIST_REMOVE_HEAD(&table->t[bucket].head, next); + rte_atomic32_inc(&table->t[bucket].cnt); + table->nb_ext_ent--; + } else + table->t[bucket].key_mask &= ~(1 << i); + 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; + + rte_atomic32_inc(&table->t[bucket].cnt); + SLIST_REMOVE(&table->t[bucket].head, ent, rte_k32v64_ext_ent, next); + rte_atomic32_inc(&table->t[bucket].cnt); + rte_mempool_put(table->ext_ent_pool, ent); + + table->nb_ext_ent--; + table->nb_ent--; + + return 0; +} + +struct rte_k32v64_hash_table * +rte_k32v64_hash_find_existing(const char *name) +{ + struct rte_k32v64_hash_table *h = NULL; + struct rte_tailq_entry *te; + struct rte_k32v64_hash_list *k32v64_hash_list; + + k32v64_hash_list = RTE_TAILQ_CAST(rte_k32v64_hash_tailq.head, + rte_k32v64_hash_list); + + rte_mcfg_tailq_read_lock(); + TAILQ_FOREACH(te, k32v64_hash_list, next) { + h = (struct rte_k32v64_hash_table *) te->data; + if (strncmp(name, h->name, RTE_K32V64_HASH_NAMESIZE) == 0) + break; + } + rte_mcfg_tailq_read_unlock(); + if (te == NULL) { + rte_errno = ENOENT; + return NULL; + } + return h; +} + +struct rte_k32v64_hash_table * +rte_k32v64_hash_create(const struct rte_k32v64_hash_params *params) +{ + char hash_name[RTE_K32V64_HASH_NAMESIZE]; + struct rte_k32v64_hash_table *ht = NULL; + struct rte_tailq_entry *te; + struct rte_k32v64_hash_list *k32v64_hash_list; + 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; + } + + k32v64_hash_list = RTE_TAILQ_CAST(rte_k32v64_hash_tailq.head, + rte_k32v64_hash_list); + + ret = snprintf(hash_name, sizeof(hash_name), "K32V64_%s", params->name); + if (ret < 0 || ret >= RTE_K32V64_HASH_NAMESIZE) { + rte_errno = ENAMETOOLONG; + return NULL; + } + + max_ent = rte_align32pow2(params->entries); + nb_buckets = max_ent / RTE_K32V64_KEYS_PER_BUCKET; + mem_size = sizeof(struct rte_k32v64_hash_table) + + sizeof(struct rte_k32v64_hash_bucket) * nb_buckets; + + mp = rte_mempool_create(hash_name, max_ent, + sizeof(struct rte_k32v64_ext_ent), 0, 0, NULL, NULL, NULL, NULL, + params->socket_id, 0); + + if (mp == NULL) + return NULL; + + rte_mcfg_tailq_write_lock(); + TAILQ_FOREACH(te, k32v64_hash_list, next) { + ht = (struct rte_k32v64_hash_table *) te->data; + if (strncmp(params->name, ht->name, + RTE_K32V64_HASH_NAMESIZE) == 0) + break; + } + ht = NULL; + if (te != NULL) { + rte_errno = EEXIST; + rte_mempool_free(mp); + goto exit; + } + + te = rte_zmalloc("K32V64_HASH_TAILQ_ENTRY", sizeof(*te), 0); + if (te == NULL) { + RTE_LOG(ERR, HASH, "Failed to allocate tailq entry\n"); + rte_mempool_free(mp); + goto exit; + } + + ht = rte_zmalloc_socket(hash_name, mem_size, + RTE_CACHE_LINE_SIZE, params->socket_id); + if (ht == NULL) { + RTE_LOG(ERR, HASH, "Failed to allocate fbk hash table\n"); + rte_free(te); + rte_mempool_free(mp); + goto exit; + } + + memcpy(ht->name, hash_name, sizeof(ht->name)); + ht->max_ent = max_ent; + ht->bucket_msk = nb_buckets - 1; + ht->ext_ent_pool = mp; + ht->lookup = get_lookup_bulk_fn(); + + te->data = (void *)ht; + TAILQ_INSERT_TAIL(k32v64_hash_list, te, next); + +exit: + rte_mcfg_tailq_write_unlock(); + + return ht; +} + +void +rte_k32v64_hash_free(struct rte_k32v64_hash_table *ht) +{ + struct rte_tailq_entry *te; + struct rte_k32v64_hash_list *k32v64_hash_list; + + if (ht == NULL) + return; + + k32v64_hash_list = RTE_TAILQ_CAST(rte_k32v64_hash_tailq.head, + rte_k32v64_hash_list); + + rte_mcfg_tailq_write_lock(); + + /* find out tailq entry */ + TAILQ_FOREACH(te, k32v64_hash_list, next) { + if (te->data == (void *) ht) + break; + } + + + if (te == NULL) { + rte_mcfg_tailq_write_unlock(); + return; + } + + TAILQ_REMOVE(k32v64_hash_list, te, next); + + rte_mcfg_tailq_write_unlock(); + + rte_mempool_free(ht->ext_ent_pool); + rte_free(ht); + rte_free(te); +} diff --git a/lib/librte_hash/rte_k32v64_hash.h b/lib/librte_hash/rte_k32v64_hash.h new file mode 100644 index 0000000..b2c52e9 --- /dev/null +++ b/lib/librte_hash/rte_k32v64_hash.h @@ -0,0 +1,211 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2020 Intel Corporation + */ + +#ifndef _RTE_K32V64_HASH_H_ +#define _RTE_K32V64_HASH_H_ + +#ifdef __cplusplus +extern "C" { +#endif + +#include +#include +#include + +#define RTE_K32V64_HASH_NAMESIZE 32 +#define RTE_K32V64_KEYS_PER_BUCKET 4 +#define RTE_K32V64_WRITE_IN_PROGRESS 1 + +struct rte_k32v64_hash_params { + const char *name; + uint32_t entries; + int socket_id; +}; + +struct rte_k32v64_ext_ent { + SLIST_ENTRY(rte_k32v64_ext_ent) next; + uint32_t key; + uint64_t val; +}; + +struct rte_k32v64_hash_bucket { + uint32_t key[RTE_K32V64_KEYS_PER_BUCKET]; + uint64_t val[RTE_K32V64_KEYS_PER_BUCKET]; + uint8_t key_mask; + rte_atomic32_t cnt; + SLIST_HEAD(rte_k32v64_list_head, rte_k32v64_ext_ent) head; +} __rte_cache_aligned; + +struct rte_k32v64_hash_table; + +typedef int (*rte_k32v64_hash_bulk_lookup_t) +(struct rte_k32v64_hash_table *table, uint32_t *keys, uint32_t *hashes, + uint64_t *values, unsigned int n); + +struct rte_k32v64_hash_table { + char name[RTE_K32V64_HASH_NAMESIZE]; /**< Name of the hash. */ + 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; + rte_k32v64_hash_bulk_lookup_t lookup; + __extension__ struct rte_k32v64_hash_bucket t[0]; +}; + +typedef int (*rte_k32v64_cmp_fn_t) +(struct rte_k32v64_hash_bucket *bucket, uint32_t key, uint64_t *val); + +static inline int +__k32v64_cmp_keys(struct rte_k32v64_hash_bucket *bucket, uint32_t key, + uint64_t *val) +{ + int i; + + for (i = 0; i < RTE_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 rte_k32v64_hash_table *table, uint32_t key, + uint32_t hash, uint64_t *value, rte_k32v64_cmp_fn_t cmp_f) +{ + uint64_t val = 0; + struct rte_k32v64_ext_ent *ent; + int32_t cnt; + int found = 0; + uint32_t bucket = hash & table->bucket_msk; + + do { + do + cnt = rte_atomic32_read(&table->t[bucket].cnt); + while (unlikely(cnt & RTE_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; + } + } + } + + } while (unlikely(cnt != rte_atomic32_read(&table->t[bucket].cnt))); + + if (found == 1) { + *value = val; + return 0; + } else + return -ENOENT; +} + +static inline int +rte_k32v64_hash_lookup(struct rte_k32v64_hash_table *table, uint32_t key, + uint32_t hash, uint64_t *value) +{ + return __k32v64_hash_lookup(table, key, hash, value, __k32v64_cmp_keys); +} + +static inline int +rte_k32v64_hash_bulk_lookup(struct rte_k32v64_hash_table *table, + uint32_t *keys, uint32_t *hashes, uint64_t *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 + * and should only be called from one thread. + * + * @param ht + * 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. + * @return + * 0 if ok, or negative value on error. + */ +__rte_experimental +int +rte_k32v64_hash_add(struct rte_k32v64_hash_table *table, uint32_t key, + uint32_t hash, uint64_t value); + +/** + * Remove a key with a given hash value from an existing hash table. + * This operation is not multi-thread + * safe and should only be called from one thread. + * + * @param ht + * Hash table to remove the key from. + * @param key + * Key to remove from the hash table. + * @param hash + * hash value associated with key. + * @return + * 0 if ok, or negative value on error. + */ +__rte_experimental +int +rte_k32v64_hash_delete(struct rte_k32v64_hash_table *table, uint32_t key, + uint32_t hash); + + +/** + * 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_k32v64_hash_table * +rte_k32v64_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_k32v64_hash_table * +rte_k32v64_hash_create(const struct rte_k32v64_hash_params *params); + +/** + * Free all memory used by a hash table. + * + * @param table + * Hash table to deallocate. + */ +__rte_experimental +void +rte_k32v64_hash_free(struct rte_k32v64_hash_table *table); + +#ifdef __cplusplus +} +#endif + +#endif /* _RTE_K32V64_HASH_H_ */ From patchwork Wed Apr 15 18:17:25 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 68578 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 B9852A0563; Wed, 15 Apr 2020 20:17:49 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id C1D701D9CF; Wed, 15 Apr 2020 20:17:37 +0200 (CEST) Received: from mga12.intel.com (mga12.intel.com [192.55.52.136]) by dpdk.org (Postfix) with ESMTP id 986A01D9C3 for ; Wed, 15 Apr 2020 20:17:34 +0200 (CEST) IronPort-SDR: SYUXpVdaKXKDfRJBdsV5eb6Tv6UpXsq7iZZ5cuHLfl1YKOQzZSk6hKdg4/GPB0XMfrJ1ViCQH8 8/azUJ5+6Qnw== X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga004.fm.intel.com ([10.253.24.48]) by fmsmga106.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 15 Apr 2020 11:17:34 -0700 IronPort-SDR: /CtFvZoqXjORdcBvuCh3i9ZyWRRbc4smov2J7b6AyHr11SjMh7wEXI07hGlEw2SZE4jCtK3C1E WkJuk0RRotgQ== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.72,388,1580803200"; d="scan'208";a="277702364" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by fmsmga004.fm.intel.com with ESMTP; 15 Apr 2020 11:17:32 -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, john.mcnamara@intel.com Date: Wed, 15 Apr 2020 19:17:25 +0100 Message-Id: <34e8fe21cbfd9cbf7d5c208564180274ee63d518.1586974411.git.vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: References: MIME-Version: 1.0 In-Reply-To: References: Subject: [dpdk-dev] [PATCH v3 2/4] hash: add documentation for k32v64 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 k32v64 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/k32v64_hash_lib.rst | 66 +++++++++++++++++++++++++++++++ 3 files changed, 68 insertions(+) create mode 100644 doc/guides/prog_guide/k32v64_hash_lib.rst diff --git a/doc/api/doxy-api-index.md b/doc/api/doxy-api-index.md index dff496b..ed3e8d7 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), + [K32V64 hash] (@ref rte_k32v64_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 fb250ab..ac56da5 100644 --- a/doc/guides/prog_guide/index.rst +++ b/doc/guides/prog_guide/index.rst @@ -30,6 +30,7 @@ Programmer's Guide link_bonding_poll_mode_drv_lib timer_lib hash_lib + k32v64_hash_lib efd_lib member_lib lpm_lib diff --git a/doc/guides/prog_guide/k32v64_hash_lib.rst b/doc/guides/prog_guide/k32v64_hash_lib.rst new file mode 100644 index 0000000..238033a --- /dev/null +++ b/doc/guides/prog_guide/k32v64_hash_lib.rst @@ -0,0 +1,66 @@ +.. SPDX-License-Identifier: BSD-3-Clause + Copyright(c) 2020 Intel Corporation. + +.. _k32v64_hash_Library: + +K32V64 Hash Library +=================== + +This hash library implementation is intended to be better optimized for 32-bit keys when compared to existing Cuckoo hash-based rte_hash implementation. 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) + +K32V64 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 + +K32V64 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 Wed Apr 15 18:17:26 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 68579 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 65E67A0563; Wed, 15 Apr 2020 20:18:00 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id D30261D9DD; Wed, 15 Apr 2020 20:17:41 +0200 (CEST) Received: from mga12.intel.com (mga12.intel.com [192.55.52.136]) by dpdk.org (Postfix) with ESMTP id 04B461D9C3 for ; Wed, 15 Apr 2020 20:17:35 +0200 (CEST) IronPort-SDR: gEB3BT1Xnj3CyxyoGKDUfBukxe+B5Jmx8h0VorpHDgZz9rM8MEaHSvuV/rBTzqAF5TXdMyKETQ 3ZyWXVfWqp1g== X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga004.fm.intel.com ([10.253.24.48]) by fmsmga106.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 15 Apr 2020 11:17:35 -0700 IronPort-SDR: aKeRP/JZCtNasso552tiqqY7AW+uhpTU38IosoWS7kBzWWvfw5RD1m+6RGK5T8/Zr6/yzZjSuP QkIB7cTqjk0w== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.72,388,1580803200"; d="scan'208";a="277702373" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by fmsmga004.fm.intel.com with ESMTP; 15 Apr 2020 11:17:34 -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: Wed, 15 Apr 2020 19:17:26 +0100 Message-Id: X-Mailer: git-send-email 2.7.4 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH v3 3/4] test: add k32v64 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_k32v64_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_k32v64_hash.c | 229 ++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 245 insertions(+) create mode 100644 app/test/test_k32v64_hash.c diff --git a/app/test/Makefile b/app/test/Makefile index be53d33..c0e2a28 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_k32v64_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..e7ec502 100644 --- a/app/test/autotest_data.py +++ b/app/test/autotest_data.py @@ -99,6 +99,18 @@ "Report": None, }, { + "Name": "K32V64 hash autotest", + "Command": "k32v64_hash_autotest", + "Func": default_autotest, + "Report": None, + }, + { + "Name": "K32V64 hash autotest", + "Command": "k32v64_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 04b59cf..9d1c965 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_k32v64_hash.c', 'test_fib.c', 'test_fib_perf.c', 'test_fib6.c', @@ -187,6 +188,7 @@ fast_tests = [ ['flow_classify_autotest', false], ['hash_autotest', true], ['interrupt_autotest', true], + ['k32v64_hash_autotest', true], ['logs_autotest', true], ['lpm_autotest', true], ['lpm6_autotest', true], @@ -272,6 +274,7 @@ perf_test_names = [ 'rand_perf_autotest', 'hash_readwrite_perf_autotest', 'hash_readwrite_lf_perf_autotest', + 'k32v64_hash_slow_autotest', ] driver_test_names = [ diff --git a/app/test/test_k32v64_hash.c b/app/test/test_k32v64_hash.c new file mode 100644 index 0000000..3cf3b8d --- /dev/null +++ b/app/test/test_k32v64_hash.c @@ -0,0 +1,229 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2020 Intel Corporation + */ + +#include +#include +#include + +#include +#include +#include + +#include "test.h" + +typedef int32_t (*rte_k32v64_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_k32v64_hash_create fails gracefully for incorrect user input + * arguments + */ +int32_t +test_create_invalid(void) +{ + struct rte_k32v64_hash_table *k32v64_hash = NULL; + struct rte_k32v64_hash_params config; + + /* rte_k32v64_hash_create: k32v64_hash name == NULL */ + config.name = NULL; + k32v64_hash = rte_k32v64_hash_create(&config); + RTE_TEST_ASSERT(k32v64_hash == NULL, + "Call succeeded with invalid parameters\n"); + config.name = "test_k32v64_hash"; + + /* rte_k32v64_hash_create: config == NULL */ + k32v64_hash = rte_k32v64_hash_create(NULL); + RTE_TEST_ASSERT(k32v64_hash == NULL, + "Call succeeded with invalid parameters\n"); + + /* socket_id < -1 is invalid */ + config.socket_id = -2; + k32v64_hash = rte_k32v64_hash_create(&config); + RTE_TEST_ASSERT(k32v64_hash == NULL, + "Call succeeded with invalid parameters\n"); + config.socket_id = rte_socket_id(); + + /* rte_k32v64_hash_create: entries = 0 */ + config.entries = 0; + k32v64_hash = rte_k32v64_hash_create(&config); + RTE_TEST_ASSERT(k32v64_hash == NULL, + "Call succeeded with invalid parameters\n"); + config.entries = MAX_ENT; + + return TEST_SUCCESS; +} + +/* + * Create k32v64_hash table then delete k32v64_hash table 10 times + * Use a slightly different rules size each time + */ +#include +int32_t +test_multiple_create(void) +{ + struct rte_k32v64_hash_table *k32v64_hash = NULL; + struct rte_k32v64_hash_params config; + int32_t i; + + + for (i = 0; i < 100; i++) { + config.name = "test_k32v64_hash"; + config.socket_id = -1; + config.entries = MAX_ENT - i; + + k32v64_hash = rte_k32v64_hash_create(&config); + RTE_TEST_ASSERT(k32v64_hash != NULL, + "Failed to create k32v64 hash\n"); + rte_k32v64_hash_free(k32v64_hash); + } + + return TEST_SUCCESS; +} + +/* + * Call rte_k32v64_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_k32v64_hash_table *k32v64_hash = NULL; + struct rte_k32v64_hash_params config; + + config.name = "test_k32v64"; + config.socket_id = -1; + config.entries = MAX_ENT; + + k32v64_hash = rte_k32v64_hash_create(&config); + RTE_TEST_ASSERT(k32v64_hash != NULL, "Failed to create k32v64 hash\n"); + + rte_k32v64_hash_free(k32v64_hash); + rte_k32v64_hash_free(NULL); + return TEST_SUCCESS; +} + +/* + * Check that rte_k32v64_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; + + /* rte_k32v64_hash_add: k32v64_hash == NULL */ + ret = rte_k32v64_hash_add(NULL, key, rte_hash_crc_4byte(key, 0), val); + RTE_TEST_ASSERT(ret == -EINVAL, + "Call succeeded with invalid parameters\n"); + + /* rte_k32v64_hash_delete: k32v64_hash == NULL */ + ret = rte_k32v64_hash_delete(NULL, key, rte_hash_crc_4byte(key, 0)); + 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_k32v64_hash_table *k32v64_hash = NULL; + struct rte_k32v64_hash_params config; + uint32_t key = 10; + uint64_t value = 20; + uint64_t ret_val = 0; + int ret; + + config.name = "test_k32v64"; + config.socket_id = -1; + config.entries = MAX_ENT; + + k32v64_hash = rte_k32v64_hash_create(&config); + RTE_TEST_ASSERT(k32v64_hash != NULL, "Failed to create k32v64 hash\n"); + + ret = rte_k32v64_hash_lookup(k32v64_hash, key, + rte_hash_crc_4byte(key, 0), &ret_val); + RTE_TEST_ASSERT(ret == -ENOENT, "Lookup return incorrect result\n"); + + ret = rte_k32v64_hash_delete(k32v64_hash, key, + rte_hash_crc_4byte(key, 0)); + RTE_TEST_ASSERT(ret == -ENOENT, "Delete return incorrect result\n"); + + ret = rte_k32v64_hash_add(k32v64_hash, key, + rte_hash_crc_4byte(key, 0), value); + RTE_TEST_ASSERT(ret == 0, "Can not add key into the table\n"); + + ret = rte_k32v64_hash_lookup(k32v64_hash, key, + rte_hash_crc_4byte(key, 0), &ret_val); + RTE_TEST_ASSERT(((ret == 0) && (value == ret_val)), + "Lookup return incorrect result\n"); + + ret = rte_k32v64_hash_delete(k32v64_hash, key, + rte_hash_crc_4byte(key, 0)); + RTE_TEST_ASSERT(ret == 0, "Can not delete key from table\n"); + + ret = rte_k32v64_hash_lookup(k32v64_hash, key, + rte_hash_crc_4byte(key, 0), &ret_val); + RTE_TEST_ASSERT(ret == -ENOENT, "Lookup return incorrect result\n"); + + rte_k32v64_hash_free(k32v64_hash); + + return TEST_SUCCESS; +} + +static struct unit_test_suite k32v64_hash_tests = { + .suite_name = "k32v64_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 k32v64_hash_slow_tests = { + .suite_name = "k32v64_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_k32v64_hash(void) +{ + return unit_test_suite_runner(&k32v64_hash_tests); +} + +static int +test_slow_k32v64_hash(void) +{ + return unit_test_suite_runner(&k32v64_hash_slow_tests); +} + +REGISTER_TEST_COMMAND(k32v64_hash_autotest, test_k32v64_hash); +REGISTER_TEST_COMMAND(k32v64_hash_slow_autotest, test_slow_k32v64_hash); From patchwork Wed Apr 15 18:17:27 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 68580 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 064BFA0563; Wed, 15 Apr 2020 20:18:08 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 9BDA51D9E1; Wed, 15 Apr 2020 20:17:43 +0200 (CEST) Received: from mga12.intel.com (mga12.intel.com [192.55.52.136]) by dpdk.org (Postfix) with ESMTP id 7399E1D9CB for ; Wed, 15 Apr 2020 20:17:37 +0200 (CEST) IronPort-SDR: gzf6riDXXPWRHVQy9pGYobfEhjMDDS3K+uptRsOhiPbnJRyyo/3lpYX951ijZKGQUIOlK9l/DY 3Uv3QdMYhK2w== X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga004.fm.intel.com ([10.253.24.48]) by fmsmga106.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 15 Apr 2020 11:17:37 -0700 IronPort-SDR: jxFFw4t32nWjQHR8i95SVAXbO2pN5OykAAS8i9MhTIc7F4FTHwHrMzXD/fcahfiUiCqfzczs7E vAwqmHCYsrTQ== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.72,388,1580803200"; d="scan'208";a="277702382" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by fmsmga004.fm.intel.com with ESMTP; 15 Apr 2020 11:17:35 -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: Wed, 15 Apr 2020 19:17:27 +0100 Message-Id: X-Mailer: git-send-email 2.7.4 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH v3 4/4] test: add k32v64 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_k32v64_hash Signed-off-by: Vladimir Medvedkin --- app/test/test_hash_perf.c | 130 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 130 insertions(+) diff --git a/app/test/test_hash_perf.c b/app/test/test_hash_perf.c index a438eae..f45a8d9 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, @@ -668,6 +672,129 @@ 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 +k32v64_hash_perf_test(void) +{ + struct rte_k32v64_hash_params params = { + .name = "k32v64_hash_test", + .entries = ENTRIES * 2, + .socket_id = rte_socket_id(), + }; + struct rte_k32v64_hash_table *handle = NULL; + uint32_t *keys; + uint32_t *lookup_keys; + uint64_t tmp_val; + uint64_t lookup_time = 0; + uint64_t begin; + uint64_t end; + unsigned int added = 0; + uint32_t key; + uint16_t val; + unsigned int i, j, k; + int ret = 0; + uint32_t hashes[64]; + uint64_t vals[64]; + + handle = rte_k32v64_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(); + + if (rte_k32v64_hash_add(handle, key, rte_hash_crc_4byte(key, + CRC_INIT_VAL), val) == 0) { + keys[added] = key; + added++; + } + } + + lookup_keys = shuf_arr(keys, added, TEST_SIZE); + + for (i = 0; i < TEST_ITERATIONS; i++) { + + begin = rte_rdtsc(); + /* Do lookups */ + + for (j = 0; j < TEST_SIZE; j++) + ret += rte_k32v64_hash_lookup(handle, lookup_keys[j], + rte_hash_crc_4byte(lookup_keys[j], + CRC_INIT_VAL), &tmp_val); + + end = rte_rdtsc(); + lookup_time += (double)(end - begin); + } + + printf("\n\n *** K32V64 Hash function performance test results ***\n"); + if (ret == 0) + printf("Number of ticks per lookup = %g\n", + (double)lookup_time / + ((double)TEST_ITERATIONS * (double)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_k32v64_hash_bulk_lookup(handle, + &lookup_keys[j], hashes, vals, 64); + } + + end = rte_rdtsc(); + lookup_time += (double)(end - begin); + } + + printf("\n\n *** K32V64 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_k32v64_hash_free(handle); + + return 0; +} + static int test_hash_perf(void) { @@ -695,6 +822,9 @@ test_hash_perf(void) if (fbk_hash_perf_test() < 0) return -1; + if (k32v64_hash_perf_test() < 0) + return -1; + return 0; }