From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga02.intel.com (mga02.intel.com [134.134.136.20]) by dpdk.org (Postfix) with ESMTP id 527597CE5 for ; Tue, 22 Aug 2017 02:20:59 +0200 (CEST) Received: from fmsmga004.fm.intel.com ([10.253.24.48]) by orsmga101.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 21 Aug 2017 17:20:58 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.41,410,1498546800"; d="scan'208";a="302858542" Received: from bdw-yipeng.jf.intel.com ([10.54.81.30]) by fmsmga004.fm.intel.com with ESMTP; 21 Aug 2017 17:20:57 -0700 From: Yipeng Wang To: vincent.jardin@6wind.com, stephen@networkplumber.org, bruce.richardson@intel.com, konstantin.ananyev@intel.com, thomas@monjalon.net Cc: dev@dpdk.org, yipeng1.wang@intel.com, charlie.tai@intel.com, sameh.gobriel@intel.com, ren.wang@intel.com Date: Mon, 21 Aug 2017 17:19:47 -0700 Message-Id: <1503361193-36699-2-git-send-email-yipeng1.wang@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1503361193-36699-1-git-send-email-yipeng1.wang@intel.com> References: <1503361193-36699-1-git-send-email-yipeng1.wang@intel.com> Subject: [dpdk-dev] [PATCH 1/7] member: implement main API 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: , X-List-Received-Date: Tue, 22 Aug 2017 00:21:00 -0000 Membership library is an extension and generalization of a traditional filter (for example Bloom Filter) structure. In general, the Membership library is a data structure that provides a "set-summary" and responds to set-membership queries of whether a certain element belongs to a set(s). A membership test for an element will return the set this element belongs to or not-found if the element is never inserted into the set-summary. The results of the membership test is not 100% accurate. Certain false positive or false negative probability could exist. However, comparing to a "full-blown" complete list of elements, a "set-summary" is memory efficient and fast on lookup. This patch add the main API definition. Signed-off-by: Yipeng Wang --- lib/Makefile | 2 + lib/librte_eal/common/eal_common_log.c | 1 + lib/librte_eal/common/include/rte_log.h | 1 + lib/librte_member/Makefile | 48 +++ lib/librte_member/rte_member.c | 357 +++++++++++++++++++++ lib/librte_member/rte_member.h | 518 +++++++++++++++++++++++++++++++ lib/librte_member/rte_member_version.map | 15 + 7 files changed, 942 insertions(+) create mode 100644 lib/librte_member/Makefile create mode 100644 lib/librte_member/rte_member.c create mode 100644 lib/librte_member/rte_member.h create mode 100644 lib/librte_member/rte_member_version.map diff --git a/lib/Makefile b/lib/Makefile index 86caba1..c82033a 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -108,6 +108,8 @@ DIRS-$(CONFIG_RTE_LIBRTE_REORDER) += librte_reorder DEPDIRS-librte_reorder := librte_eal librte_mempool librte_mbuf DIRS-$(CONFIG_RTE_LIBRTE_PDUMP) += librte_pdump DEPDIRS-librte_pdump := librte_eal librte_mempool librte_mbuf librte_ether +DIRS-$(CONFIG_RTE_LIBRTE_MEMBER) += librte_member +DEPDIRS-librte_member := librte_eal librte_hash ifeq ($(CONFIG_RTE_EXEC_ENV_LINUXAPP),y) DIRS-$(CONFIG_RTE_LIBRTE_KNI) += librte_kni diff --git a/lib/librte_eal/common/eal_common_log.c b/lib/librte_eal/common/eal_common_log.c index 0e3b932..90db6a3 100644 --- a/lib/librte_eal/common/eal_common_log.c +++ b/lib/librte_eal/common/eal_common_log.c @@ -279,6 +279,7 @@ static const struct logtype logtype_strings[] = { {RTE_LOGTYPE_CRYPTODEV, "cryptodev"}, {RTE_LOGTYPE_EFD, "efd"}, {RTE_LOGTYPE_EVENTDEV, "eventdev"}, + {RTE_LOGTYPE_MEMBER, "member"}, {RTE_LOGTYPE_USER1, "user1"}, {RTE_LOGTYPE_USER2, "user2"}, {RTE_LOGTYPE_USER3, "user3"}, diff --git a/lib/librte_eal/common/include/rte_log.h b/lib/librte_eal/common/include/rte_log.h index ec8dba7..ce1a3d0 100644 --- a/lib/librte_eal/common/include/rte_log.h +++ b/lib/librte_eal/common/include/rte_log.h @@ -87,6 +87,7 @@ extern struct rte_logs rte_logs; #define RTE_LOGTYPE_CRYPTODEV 17 /**< Log related to cryptodev. */ #define RTE_LOGTYPE_EFD 18 /**< Log related to EFD. */ #define RTE_LOGTYPE_EVENTDEV 19 /**< Log related to eventdev. */ +#define RTE_LOGTYPE_MEMBER 20 /**< Log related to membership. */ /* these log types can be used in an application */ #define RTE_LOGTYPE_USER1 24 /**< User-defined log type 1. */ diff --git a/lib/librte_member/Makefile b/lib/librte_member/Makefile new file mode 100644 index 0000000..997c825 --- /dev/null +++ b/lib/librte_member/Makefile @@ -0,0 +1,48 @@ +# BSD LICENSE +# +# Copyright(c) 2017 Intel Corporation. All rights reserved. +# All rights reserved. +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions +# are met: +# +# * Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above copyright +# notice, this list of conditions and the following disclaimer in +# the documentation and/or other materials provided with the +# distribution. +# * Neither the name of Intel Corporation nor the names of its +# contributors may be used to endorse or promote products derived +# from this software without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +include $(RTE_SDK)/mk/rte.vars.mk + +# library name +LIB = librte_member.a + +CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR) -O3 + +EXPORT_MAP := rte_member_version.map + +LIBABIVER := 1 + +# all source are stored in SRCS-y +SRCS-$(CONFIG_RTE_LIBRTE_MEMBER) += rte_member.c +# install includes +SYMLINK-$(CONFIG_RTE_LIBRTE_MEMBER)-include := rte_member.h + +include $(RTE_SDK)/mk/rte.lib.mk diff --git a/lib/librte_member/rte_member.c b/lib/librte_member/rte_member.c new file mode 100644 index 0000000..560b754 --- /dev/null +++ b/lib/librte_member/rte_member.c @@ -0,0 +1,357 @@ +/*- + * BSD LICENSE + * + * Copyright(c) 2017 Intel Corporation. All rights reserved. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Intel Corporation nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include + +#include +#include +#include +#include +#include +#include + +#include "rte_member.h" +#include "rte_member_ht.h" +#include "rte_member_vbf.h" + +TAILQ_HEAD(rte_member_list, rte_tailq_entry); +static struct rte_tailq_elem rte_member_tailq = { + .name = "RTE_MEMBER", +}; +EAL_REGISTER_TAILQ(rte_member_tailq) + + +void * +rte_member_find_existing(const char *name) +{ + struct rte_member_setsum *setsum; + struct rte_tailq_entry *te; + struct rte_member_list *member_list; + + member_list = RTE_TAILQ_CAST(rte_member_tailq.head, rte_member_list); + + rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK); + TAILQ_FOREACH(te, member_list, next) { + setsum = (struct rte_member_setsum *) te->data; + if (strncmp(name, setsum->name, RTE_MEMBER_NAMESIZE) == 0) + break; + } + rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK); + + if (te == NULL) { + rte_errno = ENOENT; + return NULL; + } + return setsum; +} + +void +rte_member_free(void *ss) +{ + struct rte_member_setsum *setsum; + struct rte_member_list *member_list = NULL; + struct rte_tailq_entry *te; + + if (ss == NULL) + return; + setsum = ss; + member_list = RTE_TAILQ_CAST(rte_member_tailq.head, rte_member_list); + rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); + TAILQ_FOREACH(te, member_list, next) { + if (te->data == ss) + break; + } + if (te == NULL) { + rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); + return; + } + TAILQ_REMOVE(member_list, te, next); + rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); + + switch (setsum->type) { + case RTE_MEMBER_TYPE_HT: + rte_member_free_ht(setsum); + break; + case RTE_MEMBER_TYPE_VBF: + rte_member_free_vbf(setsum); + break; + default: + break; + } + rte_free(setsum); + rte_free(te); +} + + +void * +rte_member_create(const struct rte_member_parameters *params) +{ + struct rte_tailq_entry *te; + struct rte_member_list *member_list = NULL; + struct rte_member_setsum *setsum = NULL; + int ret; + + if (params == NULL) { + rte_errno = EINVAL; + return NULL; + } + + if ((params->key_len == 0)) { + rte_errno = EINVAL; + RTE_LOG(ERR, MEMBER, + "Memship create with invalid parameters\n"); + return NULL; + } + + member_list = RTE_TAILQ_CAST(rte_member_tailq.head, rte_member_list); + + rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); + + TAILQ_FOREACH(te, member_list, next) { + setsum = (struct rte_member_setsum *) te->data; + if (strncmp(params->name, setsum->name, + RTE_MEMBER_NAMESIZE) == 0) + break; + } + setsum = NULL; + if (te != NULL) { + rte_errno = EEXIST; + te = NULL; + goto error_unlock_exit; + } + te = rte_zmalloc("MEMBER_TAILQ_ENTRY", sizeof(*te), 0); + if (te == NULL) { + RTE_LOG(ERR, MEMBER, "tailq entry allocation failed\n"); + goto error_unlock_exit; + } + + /* Create a new setsum structure */ + setsum = (struct rte_member_setsum *) rte_zmalloc_socket(params->name, + sizeof(struct rte_member_setsum), RTE_CACHE_LINE_SIZE, + params->socket_id); + if (setsum == NULL) { + RTE_LOG(ERR, MEMBER, "Create setsummary failed\n"); + goto error_unlock_exit; + } + setsum->type = params->type; + setsum->socket_id = params->socket_id; + setsum->key_len = params->key_len; + setsum->num_set = params->num_set; + setsum->name = params->name; + setsum->prim_hash_seed = params->prim_hash_seed; + setsum->sec_hash_seed = params->sec_hash_seed; + + switch (setsum->type) { + case RTE_MEMBER_TYPE_HT: + ret = rte_member_create_ht(setsum, params); + break; + case RTE_MEMBER_TYPE_VBF: + ret = rte_member_create_vbf(setsum, params); + break; + default: + goto error_unlock_exit; + } + if (ret < 0) + goto error_unlock_exit; + RTE_LOG(DEBUG, MEMBER, "Creating a setsummary table with mode %u\n", + setsum->type); + + te->data = (void *)setsum; + TAILQ_INSERT_TAIL(member_list, te, next); + rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); + return setsum; + +error_unlock_exit: + rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); + rte_member_free(setsum); + return NULL; +} + + +int +rte_member_add(const void *ss, const void *key, MEMBER_SET_TYPE set_id) +{ + const struct rte_member_setsum *setsum = ss; + + if (setsum == NULL || key == NULL) + return -EINVAL; + int ret = 0; + switch (setsum->type) { + case RTE_MEMBER_TYPE_HT: + ret = rte_member_add_ht(setsum, key, set_id); + break; + case RTE_MEMBER_TYPE_VBF: + ret = rte_member_add_vbf(setsum, key, set_id); + break; + default: + return -EINVAL; + } + return ret; +} + + +int +rte_member_lookup(const void *ss, const void *key, + MEMBER_SET_TYPE *set_id) +{ + const struct rte_member_setsum *setsum = ss; + if (setsum == NULL || key == NULL || set_id == NULL) + return -EINVAL; + + int ret = 0; + switch (setsum->type) { + case RTE_MEMBER_TYPE_HT: + ret = rte_member_lookup_ht(setsum, key, set_id); + break; + case RTE_MEMBER_TYPE_VBF: + ret = rte_member_lookup_vbf(setsum, key, set_id); + break; + default: + return -EINVAL; + } + return ret; +} + + +int +rte_member_lookup_bulk(const void *ss, const void **keys, uint32_t num_keys, + MEMBER_SET_TYPE *set_ids) +{ + const struct rte_member_setsum *setsum = ss; + + if (setsum == NULL || keys == NULL || set_ids == NULL) + return -EINVAL; + + int ret = 0; + switch (setsum->type) { + case RTE_MEMBER_TYPE_HT: + ret = rte_member_lookup_bulk_ht(setsum, keys, num_keys, + set_ids); + break; + case RTE_MEMBER_TYPE_VBF: + ret = rte_member_lookup_bulk_vbf(setsum, keys, num_keys, + set_ids); + break; + default: + return -EINVAL; + } + return ret; +} + +int +rte_member_lookup_multi(const void *ss, const void *key, + uint32_t match_per_key, MEMBER_SET_TYPE *set_id) +{ + const struct rte_member_setsum *setsum = ss; + + if (setsum == NULL || key == NULL || set_id == NULL) + return -EINVAL; + int ret = 0; + switch (setsum->type) { + case RTE_MEMBER_TYPE_HT: + ret = rte_member_lookup_multi_ht(setsum, key, match_per_key, + set_id); + break; + case RTE_MEMBER_TYPE_VBF: + ret = rte_member_lookup_multi_vbf(setsum, key, match_per_key, + set_id); + break; + default: + return -EINVAL; + } + return ret; +} + + +int +rte_member_lookup_multi_bulk(const void *ss, const void **keys, + uint32_t num_keys, uint32_t max_match_per_key, + uint32_t *match_count, MEMBER_SET_TYPE *set_ids) +{ + const struct rte_member_setsum *setsum = ss; + if (setsum == NULL || keys == NULL || set_ids == NULL || + match_count == NULL) + return -EINVAL; + int ret = 0; + switch (setsum->type) { + case RTE_MEMBER_TYPE_HT: + ret = rte_member_lookup_multi_bulk_ht(setsum, keys, num_keys, + max_match_per_key, match_count, set_ids); + break; + case RTE_MEMBER_TYPE_VBF: + ret = rte_member_lookup_multi_bulk_vbf(setsum, keys, num_keys, + max_match_per_key, match_count, set_ids); + break; + default: + return -EINVAL; + } + return ret; +} + + +int +rte_member_delete(void *ss, const void *key, MEMBER_SET_TYPE set_id) +{ + struct rte_member_setsum *setsum = ss; + if (setsum == NULL || key == NULL) + return -EINVAL; + int ret = 0; + switch (setsum->type) { + case RTE_MEMBER_TYPE_HT: + ret = rte_member_delete_ht(setsum, key, set_id); + break; + case RTE_MEMBER_TYPE_VBF: + default: + return -EINVAL; + } + return ret; +} + + +void +rte_member_reset(const void *ss) +{ + const struct rte_member_setsum *setsum = ss; + if (setsum == NULL) + return; + switch (setsum->type) { + case RTE_MEMBER_TYPE_HT: + rte_member_reset_ht(setsum); + break; + case RTE_MEMBER_TYPE_VBF: + rte_member_reset_vbf(setsum); + break; + default: + break; + } +} diff --git a/lib/librte_member/rte_member.h b/lib/librte_member/rte_member.h new file mode 100644 index 0000000..de44b1b --- /dev/null +++ b/lib/librte_member/rte_member.h @@ -0,0 +1,518 @@ +/*- + * BSD LICENSE + * + * Copyright(c) 2017 Intel Corporation. All rights reserved. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Intel Corporation nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + + + +/** + * @file + * + * RTE Membership Library + * + * The Membership Library is an extension and generalization of a traditional + * filter (for example Bloom Filter) structure that has multiple usages in a + * variety of workloads and applications. The library is used to test if a key + * belongs to certain sets. Two types of such "set-summary" structures are + * implemented: hash-table based (HT) and vector bloom filter (vBF). For HT + * setsummary, two subtype or modes are available, cache and non-cache modes. + * The table below summarize some properties of the different implementations. + * + * @warning + * @b EXPERIMENTAL: this API may change without prior notice + */ + + +/** + * + */ + + +#ifndef _RTE_MEMBER_H_ +#define _RTE_MEMBER_H_ + + + +#ifdef __cplusplus +extern "C" { +#endif +#include +#include +#include + +/** The set ID type that stored internally in hash table based set summary. */ +typedef uint16_t MEMBER_SET_TYPE; +/** Invalid set ID used to mean no match found. */ +#define RTE_MEMBER_NO_MATCH 0 +/** Maximum size of hash table that can be created. */ +#define RTE_MEMBER_ENTRIES_MAX (1 << 30) +/** Maximum number of keys that can be searched as a bulk */ +#define RTE_MEMBER_LOOKUP_BULK_MAX 64 +/** Entry count per bucket in hash table based mode. */ +#define RTE_MEMBER_BUCKET_ENTRIES 16 +/** Maximum number of characters in setsum name. */ +#define RTE_MEMBER_NAMESIZE 32 + +/** @internal Primary hash function to calculate 1st independent hash. */ +#define MEMBER_PRIM_HASH(key, key_len, seed) \ + (uint32_t)(rte_hash_crc(key, key_len, seed)) +/** @internal Secondary hash function to calculate 2nd independent hash. */ +#define MEMBER_SEC_HASH(key, key_len, seed) \ + (uint32_t)(rte_hash_crc(key, key_len, seed)) + + +struct rte_member_setsum; + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice + * + * Parameter struct used to create set summary + */ +struct rte_member_parameters; + + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice + * + * Define different set summary types + */ +enum rte_member_setsum_type { + RTE_MEMBER_TYPE_HT = 0, /**< Hash table based set summary. */ + RTE_MEMBER_TYPE_VBF, /**< vector of bloom filters. */ + RTE_MEMBER_NUM_TYPE +}; + +/** @internal compare function for different arch. */ +enum rte_member_sig_compare_function { + RTE_MEMBER_COMPARE_SCALAR = 0, + RTE_MEMBER_COMPARE_AVX2, + RTE_MEMBER_COMPARE_NUM +}; + +/** @internal setsummary structure. */ +struct rte_member_setsum { + enum rte_member_setsum_type type; + const char *name; + uint32_t key_len; + uint32_t socket_id; /* NUMA Socket ID for memory. */ + uint32_t prim_hash_seed; + uint32_t sec_hash_seed; + + + /* hash table based */ + uint32_t bucket_cnt; + uint32_t bucket_mask; + uint8_t cache; + enum rte_member_sig_compare_function sig_cmp_fn; + + /* vector bloom filter*/ + uint32_t num_set; + uint32_t bits; + uint32_t bit_mask; + uint32_t num_hashes; + void *table; +}; + + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice + * + * Parameters used when create the set summary table. Currently user can + * specify two types of setsummary: HT based and vBF. For HT based, user can + * specify cache or non-cache mode. Here is a table to describe some differences + * + */ +struct rte_member_parameters { + const char *name; /**< Name of the hash. */ + + /** + * User to specify the type of the setsummary from one of + * rte_member_setsum_type. + * + * HT based setsummary is implemented like a hash table. User should use + * this type when there are many sets. + * + * vBF setsummary is a vector of bloom filters. It is used when number + * of sets is not big (less than 32 for current implementation). + */ + enum rte_member_setsum_type type; + /** + * If it is HT based setsummary, user to specify the subtype or mode + * of the setsummary. It could be cache, or non-cache mode. + * Set iscache to be 1 if to use as cache mode. + * + * For cache mode, keys can be evicted out of the HT setsummary. Keys + * with the same signature and map to the same bucket + * will overwrite each other in the setsummary table. + * This mode is useful for the case that the set-summary only + * needs to keep record of the recently inserted keys. Both + * false-negative and false-positive could happen. + * + * For non-cache mode, keys cannot be evicted out of the cache. So for + * this mode the setsummary will become full eventually. Keys with the + * same signature but map to the same bucket will still occupy multiple + * entries. This mode does not give false-negative result. + */ + uint8_t iscache; + + /** + * For HT setsummary, num_keys equals to the number of entries of the + * table. When the number of keys that inserted to the HT setsummary + * approaches this number, eviction could happen. For cache mode, + * keys could be evicted out of the table. For non-cache mode, keys will + * be evicted to other buckets like cuckoo hash. The table will also + * likely to become full before the number of inserted keys equal to the + * total number of entries. + * + * For vBF, num_keys equal to the expected number of keys that will + * be inserted into the vBF. The implementation assumes the keys are + * evenly distributed to each BF in vBF. This is used to calculate the + * number of bits we need for each BF. User does not specify the size of + * each BF directly because the optimal size depends on the num_keys + * and false positive rate. + */ + uint32_t num_keys; + + + /** + * The length of key is used for hash calculation. Since key is not + * stored in set-summary, large key does not require more memory space. + */ + uint32_t key_len; + + + /** + * num_set is only relevant to vBF based setsummary. + * num_set is equal to the number of BFs in vBF. For current + * implementation, it only supports 1,2,4,8,16,32 BFs in one vBF set + * summary. If other number of sets are needed, for example 5, the user + * should allocate the minimum available value that larger than 5, + * which is 8. + */ + uint32_t num_set; + + /** + * false_postive_rate is only relevant to vBF based setsummary. + * false_postivie_rate is the user-defined false positive rate + * given expected number of inserted keys (num_keys). It is used to + * calculate the total number of bits for each BF, and the number of + * hash values used during lookup and insertion. For details please + * refer to vBF implementation and membership library documentation. + * + * HT setsummary's false positive rate is in the order of: + * false_pos = (1/bucket_count)*(1/2^16), since we use 16-bit signature. + * This is because two keys needs to map to same bucket and same + * signature to have a collision (false positive). bucket_count is equal + * to number of entries (num_keys) divided by entry count per bucket + * (RTE_MEMBER_BUCKET_ENTRIES). Thus, the false_postivie_rate is not + * directly set by users. + */ + float false_positive_rate; + + /** + * We use two seeds to calculate two independent hashes for each key. + * + * For HT type, one hash is used as signature, and the other is used + * for bucket location. + * For vBF type, these two hashes and their combinations are used as + * hash locations to index the bit array. + */ + uint32_t prim_hash_seed; + + /** + * The secondary seed should be a different value from the primary seed. + */ + uint32_t sec_hash_seed; + + int socket_id; /**< NUMA Socket ID for memory. */ +}; + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice + * + * Find an existing set-summary and return a pointer to it. + * + * @param name + * Name of the set-summary + * @return + * Pointer to the set-summary or NULL if object not found + * with rte_errno set appropriately. Possible rte_errno values include: + * - ENOENT - value not available for return + */ +void * +rte_member_find_existing(const char *name); + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice + * + * Create set-summary (SS). + * + * @param params + * parameters to initialize the setsummary + * @return + * return the pointer to the setsummary + * return value is NULL if the creation failed + */ + +void * +rte_member_create(const struct rte_member_parameters *params); + + + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice + * + * Lookup key in set-summary (SS). + * Single key lookup and return as soon as the first match found + * @param setsum + * pointer of a setsummary + * @param key + * pointer of the key that needs to lookup + * @param set_id + * output the set id matches the key + * @return + * return 1 for found a match and 0 for not found a match + */ + +int +rte_member_lookup(const void *setsum, + const void *key, MEMBER_SET_TYPE *set_id); + + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice + * + * lookup bulk of keys in set-summary (SS). + * Each key lookup returns as soon as the first match found + * @param setsum + * Pointer of a setsummary + * @param keys + * Pointer of bulk of keys that to be lookup + * @param num_keys + * Number of keys that will be lookup + * @param set_ids + * Output set ids for all the keys to this array. + * User should preallocate array that can contain all results, which size is + * the num_keys. + * @return + * The number of keys that found a match + */ + + +int +rte_member_lookup_bulk(const void *setsum, + const void **keys, uint32_t num_keys, + MEMBER_SET_TYPE *set_ids); + + + + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice + * + * Lookup a key in set-summary (SS) for multiple matches. + * The key lookup will find all matched entries (multiple match). + * Note that for cache mode of HT, each key can have at most one match. This is + * because keys with same signature that maps to same bucket will overwrite + * each other. So multi-match lookup should be used for vBF and non-cache HT. + * @param setsum + * pointer of a set-summary + * @param key + * The key that to be lookup + * @param max_match_per_key + * User specified maximum number of matches for each key. The function returns + * as soon as this number of matches found for the key. + * @param set_id + * Output set ids for all the matches of the key. User needs to preallocate + * the array that can contain max_match_per_key number of results. + * @return + * The number of matches that found for the key. + * For cache mode HT set-summary, the number should be at most 1 + */ + +int +rte_member_lookup_multi(const void *setsum, + const void *key, uint32_t max_match_per_key, + MEMBER_SET_TYPE *set_id); + + + + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice + * + * Lookup a bulk of keys in set-summary (SS) for multiple matches each key. + * Each key lookup will find all matched entries (multiple match). + * Note that for cache mode HT, each key can have at most one match. So + * multi-match function is mainly used for vBF and non-cache mode HT. + * @param setsum + * pointer of a setsummary + * @param keys + * The keys that to be lookup + * @param num_keys + * The number of keys that will be lookup + * @param max_match_per_key + * The possible maximum number of matches for each key + * @param match_count + * Output the number of matches for each key in an array + * @param set_ids + * Return set ids for all the matches of all keys. User pass in a preallocated + * 2D array with first dimension as key index and second dimension as match + * index. For example set_ids[bulk_size][max_match_per_key] + * @return + * The number of keys that found one or more matches in the set-summary + */ + +int +rte_member_lookup_multi_bulk(const void *setsum, + const void **keys, uint32_t num_keys, + uint32_t max_match_per_key, + uint32_t *match_count, + MEMBER_SET_TYPE *set_ids); + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice + * + * Insert key into set-summary (SS). + * + * @param setsum + * pointer of a set-summary + * @param key + * the key that needs to be added + * @param set_id + * The set id associated with the key that needs to be added. Different mode + * supports different set_id ranges. 0 cannot be used as set_id since + * RTE_MEMBER_NO_MATCH by default is set as 0. + * For HT mode, the set_id has range as [1, 0x7FFF], MSB is reserved. + * For vBF mode the set id is limited by the num_set parameter when create + * the set-summary. + * @return + * HT (cache mode) and vBF should never fail unless the set_id is not in the + * valid range. In such case -EINVAL is returned. + * For HT (non-cache mode) it could fail with -ENOSPC error code when table is + * full. + * For success it returns different values for different modes to provide + * extra information for users. + * Return 0 for HT (cache mode) if the add does not cause + * eviction, return 1 otherwise. Return 0 for HT mode if success, -ENOSPC for + * full, and 1 if cuckoo eviction happens. Always return 0 for vBF mode. + */ + +int +rte_member_add(const void *setsum, const void *key, + MEMBER_SET_TYPE set_id); + + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice + * + * De-allocate memory used by set-summary. + * @param setsum + * Pointer to the set summary + */ +void +rte_member_free(void *setsum); + + + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice + * + * Reset the set-summary tables. E.g. reset bits to be 0 in BF, + * reset set_id in each entry to be RTE_MEMBER_NO_MATCH in HT based SS. + * @param setsum + * Pointer to the set-summary + */ +void +rte_member_reset(const void *setsum); + + + + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice + * + * Delete items from the set-summary. Note that vBF does not support deletion + * in current implementation. For vBF, error code of -EINVAL will be returned. + * @param setsum + * Pointer to the set-summary + * @param key + * The key to be deleted + * @param set_id + * For HT mode, we need both key and its corresponding set_id to + * properly delete the key. Without set_id, we may delete other keys with the + * same signature + * @return + * If no entry found to delete, an error code of -ENOENT could be returned + */ + +int +rte_member_delete(void *setsum, const void *key, + MEMBER_SET_TYPE set_id); + + + +#ifdef __cplusplus +} +#endif + +#endif /* _RTE_MEMBER_H_ */ diff --git a/lib/librte_member/rte_member_version.map b/lib/librte_member/rte_member_version.map new file mode 100644 index 0000000..b0977e1 --- /dev/null +++ b/lib/librte_member/rte_member_version.map @@ -0,0 +1,15 @@ +DPDK_17.11 { + global: + + rte_member_create; + rte_member_lookup; + rte_member_lookup_bulk; + rte_member_lookup_multi; + rte_member_lookup_multi_bulk; + rte_member_add; + rte_member_free; + rte_member_reset; + rte_member_delete; + + local: *; +}; -- 2.7.4