From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id A053FA0559; Mon, 16 Mar 2020 14:38:47 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 89E311C028; Mon, 16 Mar 2020 14:38:40 +0100 (CET) Received: from mga14.intel.com (mga14.intel.com [192.55.52.115]) by dpdk.org (Postfix) with ESMTP id 0F615CF3 for ; Mon, 16 Mar 2020 14:38:38 +0100 (CET) IronPort-SDR: hJ4CEFQ1QZcd11bA828hwt135CkVSpncJ+6BoM1GkaT9JT0KuQEHZR+Lh/YSJherARHV2ebPsz Uph0tt4qTvYg== X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga007.jf.intel.com ([10.7.209.58]) by fmsmga103.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 16 Mar 2020 06:38:38 -0700 IronPort-SDR: a/sEf36lbTb59/ynZZQZ2dYorO2WPZNFwhgFTLOgpfNZkiqJzlixdgA87Jdiq6QRIus+lStPe+ DTv0OUn+qKhQ== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.70,560,1574150400"; d="scan'208";a="233166914" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by orsmga007.jf.intel.com with ESMTP; 16 Mar 2020 06:38:36 -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: Mon, 16 Mar 2020 13:38:27 +0000 Message-Id: <1d4e62745420259cc24baac3d941f8fe5a70b339.1584360151.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 1/3] hash: add dwk 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" DWK hash is a Double Word Key(uint32_t) hash table. The value is uint64_t. 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 | 4 +- lib/librte_hash/meson.build | 5 +- lib/librte_hash/rte_dwk_hash.c | 271 +++++++++++++++++++++++++++++++++++ lib/librte_hash/rte_dwk_hash.h | 178 +++++++++++++++++++++++ lib/librte_hash/rte_hash_version.map | 5 + 6 files changed, 461 insertions(+), 4 deletions(-) create mode 100644 lib/librte_hash/rte_dwk_hash.c create mode 100644 lib/librte_hash/rte_dwk_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 9b36097..9944963 100644 --- a/lib/librte_hash/Makefile +++ b/lib/librte_hash/Makefile @@ -8,13 +8,14 @@ LIB = librte_hash.a CFLAGS += -O3 -DALLOW_EXPERIMENTAL_API 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_dwk_hash.c # install this header file SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include := rte_hash.h @@ -27,5 +28,6 @@ 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_dwk_hash.h include $(RTE_SDK)/mk/rte.lib.mk diff --git a/lib/librte_hash/meson.build b/lib/librte_hash/meson.build index bce11ad..42c89ab 100644 --- a/lib/librte_hash/meson.build +++ b/lib/librte_hash/meson.build @@ -3,13 +3,14 @@ headers = files('rte_crc_arm64.h', 'rte_fbk_hash.h', + 'rte_dwk_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_dwk_hash.c') +deps += ['ring', 'mempool'] # rte ring reset is not yet part of stable API allow_experimental_apis = true diff --git a/lib/librte_hash/rte_dwk_hash.c b/lib/librte_hash/rte_dwk_hash.c new file mode 100644 index 0000000..8c1dadd --- /dev/null +++ b/lib/librte_hash/rte_dwk_hash.c @@ -0,0 +1,271 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2020 Intel Corporation + */ + +#include + +#include +#include +#include +#include +#include + +#include + +TAILQ_HEAD(rte_dwk_hash_list, rte_tailq_entry); + +static struct rte_tailq_elem rte_dwk_hash_tailq = { + .name = "RTE_DWK_HASH", +}; + +EAL_REGISTER_TAILQ(rte_dwk_hash_tailq); + +#define VALID_KEY_MSK ((1 << RTE_DWK_KEYS_PER_BUCKET) - 1) + +int +rte_dwk_hash_add(struct rte_dwk_hash_table *table, uint32_t key, + uint32_t hash, uint64_t value) +{ + uint32_t bucket; + int i, idx, ret; + uint8_t msk; + struct rte_dwk_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_DWK_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; + 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); + + return 0; +} + +int +rte_dwk_hash_delete(struct rte_dwk_hash_table *table, uint32_t key, + uint32_t hash) +{ + uint32_t bucket; + int i; + struct rte_dwk_ext_ent *ent; + + if (table == NULL) + return -EINVAL; + + bucket = hash & table->bucket_msk; + + for (i = 0; i < RTE_DWK_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); + } else + table->t[bucket].key_mask &= ~(1 << i); + if (ent) + rte_mempool_put(table->ext_ent_pool, 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_dwk_ext_ent, next); + rte_atomic32_inc(&table->t[bucket].cnt); + rte_mempool_put(table->ext_ent_pool, ent); + + return 0; +} + +struct rte_dwk_hash_table * +rte_dwk_hash_find_existing(const char *name) +{ + struct rte_dwk_hash_table *h = NULL; + struct rte_tailq_entry *te; + struct rte_dwk_hash_list *dwk_hash_list; + + dwk_hash_list = RTE_TAILQ_CAST(rte_dwk_hash_tailq.head, + rte_dwk_hash_list); + + rte_mcfg_tailq_read_lock(); + TAILQ_FOREACH(te, dwk_hash_list, next) { + h = (struct rte_dwk_hash_table *) te->data; + if (strncmp(name, h->name, RTE_DWK_HASH_NAMESIZE) == 0) + break; + } + rte_mcfg_tailq_read_unlock(); + if (te == NULL) { + rte_errno = ENOENT; + return NULL; + } + return h; +} + +struct rte_dwk_hash_table * +rte_dwk_hash_create(const struct rte_dwk_hash_params *params) +{ + char hash_name[RTE_DWK_HASH_NAMESIZE]; + struct rte_dwk_hash_table *ht = NULL; + struct rte_tailq_entry *te; + struct rte_dwk_hash_list *dwk_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; + } + + dwk_hash_list = RTE_TAILQ_CAST(rte_dwk_hash_tailq.head, + rte_dwk_hash_list); + + ret = snprintf(hash_name, sizeof(hash_name), "DWK_%s", params->name); + if (ret < 0 || ret >= RTE_DWK_HASH_NAMESIZE) { + rte_errno = ENAMETOOLONG; + return NULL; + } + + max_ent = rte_align32pow2(params->entries); + nb_buckets = max_ent / RTE_DWK_KEYS_PER_BUCKET; + mem_size = sizeof(struct rte_dwk_hash_table) + + sizeof(struct rte_dwk_hash_bucket) * nb_buckets; + + mp = rte_mempool_create(hash_name, max_ent, + sizeof(struct rte_dwk_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, dwk_hash_list, next) { + ht = (struct rte_dwk_hash_table *) te->data; + if (strncmp(params->name, ht->name, + RTE_DWK_HASH_NAMESIZE) == 0) + break; + } + ht = NULL; + if (te != NULL) { + rte_errno = EEXIST; + rte_mempool_free(mp); + goto exit; + } + + te = rte_zmalloc("DWK_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; + + te->data = (void *)ht; + TAILQ_INSERT_TAIL(dwk_hash_list, te, next); + +exit: + rte_mcfg_tailq_write_unlock(); + + return ht; +} + +void +rte_dwk_hash_free(struct rte_dwk_hash_table *ht) +{ + struct rte_tailq_entry *te; + struct rte_dwk_hash_list *dwk_hash_list; + + if (ht == NULL) + return; + + dwk_hash_list = RTE_TAILQ_CAST(rte_dwk_hash_tailq.head, + rte_dwk_hash_list); + + rte_mcfg_tailq_write_lock(); + + /* find out tailq entry */ + TAILQ_FOREACH(te, dwk_hash_list, next) { + if (te->data == (void *) ht) + break; + } + + + if (te == NULL) { + rte_mcfg_tailq_write_unlock(); + return; + } + + TAILQ_REMOVE(dwk_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_dwk_hash.h b/lib/librte_hash/rte_dwk_hash.h new file mode 100644 index 0000000..98e21ee --- /dev/null +++ b/lib/librte_hash/rte_dwk_hash.h @@ -0,0 +1,178 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2020 Intel Corporation + */ + +#ifndef _RTE_DWK_HASH_H_ +#define _RTE_DWK_HASH_H_ + +#ifdef __cplusplus +extern "C" { +#endif + +#include +#include +#include + +#define RTE_DWK_HASH_NAMESIZE 32 +#define RTE_DWK_KEYS_PER_BUCKET 4 +#define RTE_DWK_WRITE_IN_PROGRESS 1 + +struct rte_dwk_hash_params { + const char *name; + uint32_t entries; + int socket_id; +}; + +struct rte_dwk_ext_ent { + SLIST_ENTRY(rte_dwk_ext_ent) next; + uint32_t key; + uint64_t val; +}; + +struct rte_dwk_hash_bucket { + uint32_t key[RTE_DWK_KEYS_PER_BUCKET]; + uint64_t val[RTE_DWK_KEYS_PER_BUCKET]; + uint8_t key_mask; + rte_atomic32_t cnt; + SLIST_HEAD(rte_dwk_list_head, rte_dwk_ext_ent) head; +} __rte_cache_aligned; + +struct rte_dwk_hash_table { + char name[RTE_DWK_HASH_NAMESIZE]; /**< Name of the hash. */ + uint32_t nb_ent; + uint32_t max_ent; + uint32_t bucket_msk; + struct rte_mempool *ext_ent_pool; + __extension__ struct rte_dwk_hash_bucket t[0]; +}; + +static inline int +rte_dwk_hash_lookup(struct rte_dwk_hash_table *table, uint32_t key, + uint32_t hash, uint64_t *value) +{ + uint64_t val = 0; + struct rte_dwk_ext_ent *ent; + int32_t cnt; + int i, found = 0; + uint32_t bucket = hash & table->bucket_msk; + + do { + do + cnt = rte_atomic32_read(&table->t[bucket].cnt); + while (unlikely(cnt & RTE_DWK_WRITE_IN_PROGRESS)); + + for (i = 0; i < RTE_DWK_KEYS_PER_BUCKET; i++) { + if ((key == table->t[bucket].key[i]) && + (table->t[bucket].key_mask & + (1 << i))) { + val = table->t[bucket].val[i]; + found = 1; + break; + } + } + + 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; +} + +/** + * 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_dwk_hash_add(struct rte_dwk_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_dwk_hash_delete(struct rte_dwk_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_dwk_hash_table * +rte_dwk_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_dwk_hash_table * +rte_dwk_hash_create(const struct rte_dwk_hash_params *params); + +/** + * Free all memory used by a hash table. + * + * @param table + * Hash table to deallocate. + */ +__rte_experimental +void +rte_dwk_hash_free(struct rte_dwk_hash_table *table); + +#ifdef __cplusplus +} +#endif + +#endif /* _RTE_DWK_HASH_H_ */ diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_version.map index a8fbbc3..65d2bda 100644 --- a/lib/librte_hash/rte_hash_version.map +++ b/lib/librte_hash/rte_hash_version.map @@ -35,4 +35,9 @@ EXPERIMENTAL { rte_hash_free_key_with_position; rte_hash_max_key_id; + rte_dwk_hash_create; + rte_dwk_hash_find_existing; + rte_dwk_hash_free; + rte_dwk_hash_add; + rte_dwk_hash_delete; }; -- 2.7.4