Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/28297/?format=api
{ "id": 28297, "url": "http://patches.dpdk.org/api/patches/28297/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/patch/1504315481-12854-2-git-send-email-yipeng1.wang@intel.com/", "project": { "id": 1, "url": "http://patches.dpdk.org/api/projects/1/?format=api", "name": "DPDK", "link_name": "dpdk", "list_id": "dev.dpdk.org", "list_email": "dev@dpdk.org", "web_url": "http://core.dpdk.org", "scm_url": "git://dpdk.org/dpdk", "webscm_url": "http://git.dpdk.org/dpdk", "list_archive_url": "https://inbox.dpdk.org/dev", "list_archive_url_format": "https://inbox.dpdk.org/dev/{}", "commit_url_format": "" }, "msgid": "<1504315481-12854-2-git-send-email-yipeng1.wang@intel.com>", "list_archive_url": "https://inbox.dpdk.org/dev/1504315481-12854-2-git-send-email-yipeng1.wang@intel.com", "date": "2017-09-02T01:24:35", "name": "[dpdk-dev,v2,1/7] member: implement main API", "commit_ref": null, "pull_url": null, "state": "superseded", "archived": true, "hash": "5106d99c2eb876441317e6fa91a5b3a7ba459ec3", "submitter": { "id": 754, "url": "http://patches.dpdk.org/api/people/754/?format=api", "name": "Wang, Yipeng1", "email": "yipeng1.wang@intel.com" }, "delegate": null, "mbox": "http://patches.dpdk.org/project/dpdk/patch/1504315481-12854-2-git-send-email-yipeng1.wang@intel.com/mbox/", "series": [], "comments": "http://patches.dpdk.org/api/patches/28297/comments/", "check": "success", "checks": "http://patches.dpdk.org/api/patches/28297/checks/", "tags": {}, "related": [], "headers": { "Return-Path": "<dev-bounces@dpdk.org>", "X-Original-To": "patchwork@dpdk.org", "Delivered-To": "patchwork@dpdk.org", "Received": [ "from [92.243.14.124] (localhost [IPv6:::1])\n\tby dpdk.org (Postfix) with ESMTP id 00866568A;\n\tSat, 2 Sep 2017 03:25:10 +0200 (CEST)", "from mga06.intel.com (mga06.intel.com [134.134.136.31])\n\tby dpdk.org (Postfix) with ESMTP id 887C45689\n\tfor <dev@dpdk.org>; Sat, 2 Sep 2017 03:25:08 +0200 (CEST)", "from fmsmga006.fm.intel.com ([10.253.24.20])\n\tby orsmga104.jf.intel.com with ESMTP; 01 Sep 2017 18:25:08 -0700", "from bdw-yipeng.jf.intel.com ([10.54.81.30])\n\tby fmsmga006.fm.intel.com with ESMTP; 01 Sep 2017 18:25:07 -0700" ], "X-ExtLoop1": "1", "X-IronPort-AV": "E=Sophos;i=\"5.41,459,1498546800\"; d=\"scan'208\";a=\"147303371\"", "From": "Yipeng Wang <yipeng1.wang@intel.com>", "To": "dev@dpdk.org", "Cc": "stephen@networkplumber.org, luca.boccassi@gmail.com,\n\tcharlie.tai@intel.com, sameh.gobriel@intel.com, ren.wang@intel.com,\n\tpablo.de.lara.guarch@intel.com, yipeng1.wang@intel.com", "Date": "Fri, 1 Sep 2017 18:24:35 -0700", "Message-Id": "<1504315481-12854-2-git-send-email-yipeng1.wang@intel.com>", "X-Mailer": "git-send-email 2.7.4", "In-Reply-To": "<1504315481-12854-1-git-send-email-yipeng1.wang@intel.com>", "References": "<1503361193-36699-1-git-send-email-yipeng1.wang@intel.com>\n\t<1504315481-12854-1-git-send-email-yipeng1.wang@intel.com>", "Subject": "[dpdk-dev] [PATCH v2 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 <dev.dpdk.org>", "List-Unsubscribe": "<http://dpdk.org/ml/options/dev>,\n\t<mailto:dev-request@dpdk.org?subject=unsubscribe>", "List-Archive": "<http://dpdk.org/ml/archives/dev/>", "List-Post": "<mailto:dev@dpdk.org>", "List-Help": "<mailto:dev-request@dpdk.org?subject=help>", "List-Subscribe": "<http://dpdk.org/ml/listinfo/dev>,\n\t<mailto:dev-request@dpdk.org?subject=subscribe>", "Errors-To": "dev-bounces@dpdk.org", "Sender": "\"dev\" <dev-bounces@dpdk.org>" }, "content": "Membership library is an extension and generalization of a traditional\nfilter (for example Bloom Filter) structure. In general, the Membership\nlibrary is a data structure that provides a \"set-summary\" and responds\nto set-membership queries of whether a certain element belongs to a\nset(s). A membership test for an element will return the set this element\nbelongs to or not-found if the element is never inserted into the\nset-summary.\n\nThe results of the membership test is not 100% accurate. Certain\nfalse positive or false negative probability could exist. However,\ncomparing to a \"full-blown\" complete list of elements, a \"set-summary\"\nis memory efficient and fast on lookup.\n\nThis patch add the main API definition.\n\nSigned-off-by: Yipeng Wang <yipeng1.wang@intel.com>\n---\n lib/Makefile | 2 +\n lib/librte_eal/common/eal_common_log.c | 1 +\n lib/librte_eal/common/include/rte_log.h | 1 +\n lib/librte_member/Makefile | 49 +++\n lib/librte_member/rte_member.c | 342 ++++++++++++++++++++\n lib/librte_member/rte_member.h | 518 +++++++++++++++++++++++++++++++\n lib/librte_member/rte_member_version.map | 16 +\n 7 files changed, 929 insertions(+)\n create mode 100644 lib/librte_member/Makefile\n create mode 100644 lib/librte_member/rte_member.c\n create mode 100644 lib/librte_member/rte_member.h\n create mode 100644 lib/librte_member/rte_member_version.map", "diff": "diff --git a/lib/Makefile b/lib/Makefile\nindex 86caba1..c82033a 100644\n--- a/lib/Makefile\n+++ b/lib/Makefile\n@@ -108,6 +108,8 @@ DIRS-$(CONFIG_RTE_LIBRTE_REORDER) += librte_reorder\n DEPDIRS-librte_reorder := librte_eal librte_mempool librte_mbuf\n DIRS-$(CONFIG_RTE_LIBRTE_PDUMP) += librte_pdump\n DEPDIRS-librte_pdump := librte_eal librte_mempool librte_mbuf librte_ether\n+DIRS-$(CONFIG_RTE_LIBRTE_MEMBER) += librte_member\n+DEPDIRS-librte_member := librte_eal librte_hash\n \n ifeq ($(CONFIG_RTE_EXEC_ENV_LINUXAPP),y)\n DIRS-$(CONFIG_RTE_LIBRTE_KNI) += librte_kni\ndiff --git a/lib/librte_eal/common/eal_common_log.c b/lib/librte_eal/common/eal_common_log.c\nindex 0e3b932..90db6a3 100644\n--- a/lib/librte_eal/common/eal_common_log.c\n+++ b/lib/librte_eal/common/eal_common_log.c\n@@ -279,6 +279,7 @@ static const struct logtype logtype_strings[] = {\n \t{RTE_LOGTYPE_CRYPTODEV, \"cryptodev\"},\n \t{RTE_LOGTYPE_EFD, \"efd\"},\n \t{RTE_LOGTYPE_EVENTDEV, \"eventdev\"},\n+\t{RTE_LOGTYPE_MEMBER, \"member\"},\n \t{RTE_LOGTYPE_USER1, \"user1\"},\n \t{RTE_LOGTYPE_USER2, \"user2\"},\n \t{RTE_LOGTYPE_USER3, \"user3\"},\ndiff --git a/lib/librte_eal/common/include/rte_log.h b/lib/librte_eal/common/include/rte_log.h\nindex ec8dba7..ce1a3d0 100644\n--- a/lib/librte_eal/common/include/rte_log.h\n+++ b/lib/librte_eal/common/include/rte_log.h\n@@ -87,6 +87,7 @@ extern struct rte_logs rte_logs;\n #define RTE_LOGTYPE_CRYPTODEV 17 /**< Log related to cryptodev. */\n #define RTE_LOGTYPE_EFD 18 /**< Log related to EFD. */\n #define RTE_LOGTYPE_EVENTDEV 19 /**< Log related to eventdev. */\n+#define RTE_LOGTYPE_MEMBER 20 /**< Log related to membership. */\n \n /* these log types can be used in an application */\n #define RTE_LOGTYPE_USER1 24 /**< User-defined log type 1. */\ndiff --git a/lib/librte_member/Makefile b/lib/librte_member/Makefile\nnew file mode 100644\nindex 0000000..1a79eaa\n--- /dev/null\n+++ b/lib/librte_member/Makefile\n@@ -0,0 +1,49 @@\n+# BSD LICENSE\n+#\n+# Copyright(c) 2017 Intel Corporation. All rights reserved.\n+# All rights reserved.\n+#\n+# Redistribution and use in source and binary forms, with or without\n+# modification, are permitted provided that the following conditions\n+# are met:\n+#\n+# * Redistributions of source code must retain the above copyright\n+# notice, this list of conditions and the following disclaimer.\n+# * Redistributions in binary form must reproduce the above copyright\n+# notice, this list of conditions and the following disclaimer in\n+# the documentation and/or other materials provided with the\n+# distribution.\n+# * Neither the name of Intel Corporation nor the names of its\n+# contributors may be used to endorse or promote products derived\n+# from this software without specific prior written permission.\n+#\n+# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS\n+# \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT\n+# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR\n+# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT\n+# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n+# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT\n+# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,\n+# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY\n+# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT\n+# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE\n+# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n+\n+include $(RTE_SDK)/mk/rte.vars.mk\n+\n+# library name\n+LIB = librte_member.a\n+\n+CFLAGS := -I$(SRCDIR) $(CFLAGS)\n+CFLAGS += $(WERROR_FLAGS) -O3\n+\n+EXPORT_MAP := rte_member_version.map\n+\n+LIBABIVER := 1\n+\n+# all source are stored in SRCS-y\n+SRCS-$(CONFIG_RTE_LIBRTE_MEMBER) += rte_member.c\n+# install includes\n+SYMLINK-$(CONFIG_RTE_LIBRTE_MEMBER)-include := rte_member.h\n+\n+include $(RTE_SDK)/mk/rte.lib.mk\ndiff --git a/lib/librte_member/rte_member.c b/lib/librte_member/rte_member.c\nnew file mode 100644\nindex 0000000..71b066d\n--- /dev/null\n+++ b/lib/librte_member/rte_member.c\n@@ -0,0 +1,342 @@\n+/*-\n+ * BSD LICENSE\n+ *\n+ * Copyright(c) 2017 Intel Corporation. All rights reserved.\n+ * All rights reserved.\n+ *\n+ * Redistribution and use in source and binary forms, with or without\n+ * modification, are permitted provided that the following conditions\n+ * are met:\n+ *\n+ * * Redistributions of source code must retain the above copyright\n+ * notice, this list of conditions and the following disclaimer.\n+ * * Redistributions in binary form must reproduce the above copyright\n+ * notice, this list of conditions and the following disclaimer in\n+ * the documentation and/or other materials provided with the\n+ * distribution.\n+ * * Neither the name of Intel Corporation nor the names of its\n+ * contributors may be used to endorse or promote products derived\n+ * from this software without specific prior written permission.\n+ *\n+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS\n+ * \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT\n+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR\n+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT\n+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT\n+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,\n+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY\n+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT\n+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE\n+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n+ */\n+\n+#include <string.h>\n+\n+#include <rte_eal.h>\n+#include <rte_eal_memconfig.h>\n+#include <rte_memory.h>\n+#include <rte_memzone.h>\n+#include <rte_malloc.h>\n+#include <rte_errno.h>\n+\n+#include \"rte_member.h\"\n+#include \"rte_member_ht.h\"\n+#include \"rte_member_vbf.h\"\n+\n+TAILQ_HEAD(rte_member_list, rte_tailq_entry);\n+static struct rte_tailq_elem rte_member_tailq = {\n+\t.name = \"RTE_MEMBER\",\n+};\n+EAL_REGISTER_TAILQ(rte_member_tailq)\n+\n+\n+void *\n+rte_member_find_existing(const char *name)\n+{\n+\tstruct rte_member_setsum *setsum = NULL;\n+\tstruct rte_tailq_entry *te;\n+\tstruct rte_member_list *member_list;\n+\n+\tmember_list = RTE_TAILQ_CAST(rte_member_tailq.head, rte_member_list);\n+\n+\trte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);\n+\tTAILQ_FOREACH(te, member_list, next) {\n+\t\tsetsum = (struct rte_member_setsum *) te->data;\n+\t\tif (strncmp(name, setsum->name, RTE_MEMBER_NAMESIZE) == 0)\n+\t\t\tbreak;\n+\t}\n+\trte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);\n+\n+\tif (te == NULL) {\n+\t\trte_errno = ENOENT;\n+\t\treturn NULL;\n+\t}\n+\treturn setsum;\n+}\n+\n+void\n+rte_member_free(void *ss)\n+{\n+\tstruct rte_member_setsum *setsum;\n+\tstruct rte_member_list *member_list = NULL;\n+\tstruct rte_tailq_entry *te;\n+\n+\tif (ss == NULL)\n+\t\treturn;\n+\tsetsum = ss;\n+\tmember_list = RTE_TAILQ_CAST(rte_member_tailq.head, rte_member_list);\n+\trte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);\n+\tTAILQ_FOREACH(te, member_list, next) {\n+\t\tif (te->data == ss)\n+\t\t\tbreak;\n+\t}\n+\tif (te == NULL) {\n+\t\trte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);\n+\t\treturn;\n+\t}\n+\tTAILQ_REMOVE(member_list, te, next);\n+\trte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);\n+\n+\tswitch (setsum->type) {\n+\tcase RTE_MEMBER_TYPE_HT:\n+\t\trte_member_free_ht(setsum);\n+\t\tbreak;\n+\tcase RTE_MEMBER_TYPE_VBF:\n+\t\trte_member_free_vbf(setsum);\n+\t\tbreak;\n+\tdefault:\n+\t\tbreak;\n+\t}\n+\trte_free(setsum);\n+\trte_free(te);\n+}\n+\n+\n+void *\n+rte_member_create(const struct rte_member_parameters *params)\n+{\n+\tstruct rte_tailq_entry *te;\n+\tstruct rte_member_list *member_list = NULL;\n+\tstruct rte_member_setsum *setsum = NULL;\n+\tint ret;\n+\n+\tif (params == NULL) {\n+\t\trte_errno = EINVAL;\n+\t\treturn NULL;\n+\t}\n+\n+\tif ((params->key_len == 0)) {\n+\t\trte_errno = EINVAL;\n+\t\tRTE_LOG(ERR, MEMBER,\n+\t\t\t\"Memship create with invalid parameters\\n\");\n+\t\treturn NULL;\n+\t}\n+\n+\tmember_list = RTE_TAILQ_CAST(rte_member_tailq.head, rte_member_list);\n+\n+\trte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);\n+\n+\tTAILQ_FOREACH(te, member_list, next) {\n+\t\tsetsum = (struct rte_member_setsum *) te->data;\n+\t\tif (strncmp(params->name, setsum->name,\n+\t\t\t\tRTE_MEMBER_NAMESIZE) == 0)\n+\t\t\tbreak;\n+\t}\n+\tsetsum = NULL;\n+\tif (te != NULL) {\n+\t\trte_errno = EEXIST;\n+\t\tte = NULL;\n+\t\tgoto error_unlock_exit;\n+\t}\n+\tte = rte_zmalloc(\"MEMBER_TAILQ_ENTRY\", sizeof(*te), 0);\n+\tif (te == NULL) {\n+\t\tRTE_LOG(ERR, MEMBER, \"tailq entry allocation failed\\n\");\n+\t\tgoto error_unlock_exit;\n+\t}\n+\n+\t/* Create a new setsum structure */\n+\tsetsum = (struct rte_member_setsum *) rte_zmalloc_socket(params->name,\n+\t\t\tsizeof(struct rte_member_setsum), RTE_CACHE_LINE_SIZE,\n+\t\t\tparams->socket_id);\n+\tif (setsum == NULL) {\n+\t\tRTE_LOG(ERR, MEMBER, \"Create setsummary failed\\n\");\n+\t\tgoto error_unlock_exit;\n+\t}\n+\tsetsum->type = params->type;\n+\tsetsum->socket_id = params->socket_id;\n+\tsetsum->key_len = params->key_len;\n+\tsetsum->num_set = params->num_set;\n+\tsetsum->name = params->name;\n+\tsetsum->prim_hash_seed = params->prim_hash_seed;\n+\tsetsum->sec_hash_seed = params->sec_hash_seed;\n+\n+\tswitch (setsum->type) {\n+\tcase RTE_MEMBER_TYPE_HT:\n+\t\tret = rte_member_create_ht(setsum, params);\n+\t\tbreak;\n+\tcase RTE_MEMBER_TYPE_VBF:\n+\t\tret = rte_member_create_vbf(setsum, params);\n+\t\tbreak;\n+\tdefault:\n+\t\tgoto error_unlock_exit;\n+\t}\n+\tif (ret < 0)\n+\t\tgoto error_unlock_exit;\n+\tRTE_LOG(DEBUG, MEMBER, \"Creating a setsummary table with mode %u\\n\",\n+\t\t\tsetsum->type);\n+\n+\tte->data = (void *)setsum;\n+\tTAILQ_INSERT_TAIL(member_list, te, next);\n+\trte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);\n+\treturn setsum;\n+\n+error_unlock_exit:\n+\trte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);\n+\trte_member_free(setsum);\n+\treturn NULL;\n+}\n+\n+\n+int\n+rte_member_add(const void *ss, const void *key, MEMBER_SET_TYPE set_id)\n+{\n+\tconst struct rte_member_setsum *setsum = ss;\n+\n+\tif (setsum == NULL || key == NULL)\n+\t\treturn -EINVAL;\n+\n+\tswitch (setsum->type) {\n+\tcase RTE_MEMBER_TYPE_HT:\n+\t\treturn rte_member_add_ht(setsum, key, set_id);\n+\tcase RTE_MEMBER_TYPE_VBF:\n+\t\treturn rte_member_add_vbf(setsum, key, set_id);\n+\tdefault:\n+\t\treturn -EINVAL;\n+\t}\n+}\n+\n+\n+int\n+rte_member_lookup(const void *ss, const void *key,\n+\t\tMEMBER_SET_TYPE *set_id)\n+{\n+\tconst struct rte_member_setsum *setsum = ss;\n+\n+\tif (setsum == NULL || key == NULL || set_id == NULL)\n+\t\treturn -EINVAL;\n+\n+\tswitch (setsum->type) {\n+\tcase RTE_MEMBER_TYPE_HT:\n+\t\treturn rte_member_lookup_ht(setsum, key, set_id);\n+\tcase RTE_MEMBER_TYPE_VBF:\n+\t\treturn rte_member_lookup_vbf(setsum, key, set_id);\n+\tdefault:\n+\t\treturn -EINVAL;\n+\t}\n+}\n+\n+\n+int\n+rte_member_lookup_bulk(const void *ss, const void **keys, uint32_t num_keys,\n+\t\tMEMBER_SET_TYPE *set_ids)\n+{\n+\tconst struct rte_member_setsum *setsum = ss;\n+\n+\tif (setsum == NULL || keys == NULL || set_ids == NULL)\n+\t\treturn -EINVAL;\n+\n+\tswitch (setsum->type) {\n+\tcase RTE_MEMBER_TYPE_HT:\n+\t\treturn rte_member_lookup_bulk_ht(setsum, keys, num_keys,\n+\t\t\t\tset_ids);\n+\tcase RTE_MEMBER_TYPE_VBF:\n+\t\treturn rte_member_lookup_bulk_vbf(setsum, keys, num_keys,\n+\t\t\t\tset_ids);\n+\tdefault:\n+\t\treturn -EINVAL;\n+\t}\n+}\n+\n+int\n+rte_member_lookup_multi(const void *ss, const void *key,\n+\t\tuint32_t match_per_key, MEMBER_SET_TYPE *set_id)\n+{\n+\tconst struct rte_member_setsum *setsum = ss;\n+\n+\tif (setsum == NULL || key == NULL || set_id == NULL)\n+\t\treturn -EINVAL;\n+\n+\tswitch (setsum->type) {\n+\tcase RTE_MEMBER_TYPE_HT:\n+\t\treturn rte_member_lookup_multi_ht(setsum, key, match_per_key,\n+\t\t\t\tset_id);\n+\tcase RTE_MEMBER_TYPE_VBF:\n+\t\treturn rte_member_lookup_multi_vbf(setsum, key, match_per_key,\n+\t\t\t\tset_id);\n+\tdefault:\n+\t\treturn -EINVAL;\n+\t}\n+}\n+\n+\n+int\n+rte_member_lookup_multi_bulk(const void *ss, const void **keys,\n+\t\tuint32_t num_keys, uint32_t max_match_per_key,\n+\t\tuint32_t *match_count, MEMBER_SET_TYPE *set_ids)\n+{\n+\tconst struct rte_member_setsum *setsum = ss;\n+\n+\tif (setsum == NULL || keys == NULL || set_ids == NULL ||\n+\t\t\tmatch_count == NULL)\n+\t\treturn -EINVAL;\n+\n+\tswitch (setsum->type) {\n+\tcase RTE_MEMBER_TYPE_HT:\n+\t\treturn rte_member_lookup_multi_bulk_ht(setsum, keys, num_keys,\n+\t\t\t\tmax_match_per_key, match_count, set_ids);\n+\tcase RTE_MEMBER_TYPE_VBF:\n+\t\treturn rte_member_lookup_multi_bulk_vbf(setsum, keys, num_keys,\n+\t\t\t\tmax_match_per_key, match_count, set_ids);\n+\tdefault:\n+\t\treturn -EINVAL;\n+\t}\n+}\n+\n+\n+int\n+rte_member_delete(void *ss, const void *key, MEMBER_SET_TYPE set_id)\n+{\n+\tstruct rte_member_setsum *setsum = ss;\n+\n+\tif (setsum == NULL || key == NULL)\n+\t\treturn -EINVAL;\n+\n+\tswitch (setsum->type) {\n+\tcase RTE_MEMBER_TYPE_HT:\n+\t\treturn rte_member_delete_ht(setsum, key, set_id);\n+\tcase RTE_MEMBER_TYPE_VBF:\n+\tdefault:\n+\t\treturn -EINVAL;\n+\t}\n+}\n+\n+\n+void\n+rte_member_reset(const void *ss)\n+{\n+\tconst struct rte_member_setsum *setsum = ss;\n+\n+\tif (setsum == NULL)\n+\t\treturn;\n+\tswitch (setsum->type) {\n+\tcase RTE_MEMBER_TYPE_HT:\n+\t\trte_member_reset_ht(setsum);\n+\t\treturn;\n+\tcase RTE_MEMBER_TYPE_VBF:\n+\t\trte_member_reset_vbf(setsum);\n+\t\treturn;\n+\tdefault:\n+\t\treturn;\n+\t}\n+}\ndiff --git a/lib/librte_member/rte_member.h b/lib/librte_member/rte_member.h\nnew file mode 100644\nindex 0000000..de44b1b\n--- /dev/null\n+++ b/lib/librte_member/rte_member.h\n@@ -0,0 +1,518 @@\n+/*-\n+ * BSD LICENSE\n+ *\n+ * Copyright(c) 2017 Intel Corporation. All rights reserved.\n+ * All rights reserved.\n+ *\n+ * Redistribution and use in source and binary forms, with or without\n+ * modification, are permitted provided that the following conditions\n+ * are met:\n+ *\n+ * * Redistributions of source code must retain the above copyright\n+ * notice, this list of conditions and the following disclaimer.\n+ * * Redistributions in binary form must reproduce the above copyright\n+ * notice, this list of conditions and the following disclaimer in\n+ * the documentation and/or other materials provided with the\n+ * distribution.\n+ * * Neither the name of Intel Corporation nor the names of its\n+ * contributors may be used to endorse or promote products derived\n+ * from this software without specific prior written permission.\n+ *\n+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS\n+ * \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT\n+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR\n+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT\n+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT\n+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,\n+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY\n+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT\n+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE\n+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n+ */\n+\n+\n+\n+/**\n+ * @file\n+ *\n+ * RTE Membership Library\n+ *\n+ * The Membership Library is an extension and generalization of a traditional\n+ * filter (for example Bloom Filter) structure that has multiple usages in a\n+ * variety of workloads and applications. The library is used to test if a key\n+ * belongs to certain sets. Two types of such \"set-summary\" structures are\n+ * implemented: hash-table based (HT) and vector bloom filter (vBF). For HT\n+ * setsummary, two subtype or modes are available, cache and non-cache modes.\n+ * The table below summarize some properties of the different implementations.\n+ *\n+ * @warning\n+ * @b EXPERIMENTAL: this API may change without prior notice\n+ */\n+\n+\n+/**\n+ * <!--\n+ * +==========+=====================+================+=========================+\n+ * | type | vbf | HT-cache | HT-non-cache |\n+ * +==========+=====================+==========================================+\n+ * |structure | bloom-filter array | hash-table like without storing key |\n+ * +----------+---------------------+------------------------------------------+\n+ * |set id | limited by bf count | [1, 0x7fff] |\n+ * | | up to 32. | |\n+ * +----------+---------------------+------------------------------------------+\n+ * |usages & | small set range, | can delete, | cache most recent keys, |\n+ * |properties| user-specified | big set range, | have both false-positive|\n+ * | | false-positive rate,| small false | and false-negative |\n+ * | | no deletion support.| positive depend| depend on table size, |\n+ * | | | on table size, | automatic overwritten. |\n+ * | | | new key does | |\n+ * | | | not overwrite | |\n+ * | | | existing key. | |\n+ * +----------+---------------------+----------------+-------------------------+\n+ * -->\n+ */\n+\n+\n+#ifndef _RTE_MEMBER_H_\n+#define _RTE_MEMBER_H_\n+\n+\n+\n+#ifdef __cplusplus\n+extern \"C\" {\n+#endif\n+#include <stdio.h>\n+#include <stdint.h>\n+#include <rte_hash_crc.h>\n+\n+/** The set ID type that stored internally in hash table based set summary. */\n+typedef uint16_t MEMBER_SET_TYPE;\n+/** Invalid set ID used to mean no match found. */\n+#define RTE_MEMBER_NO_MATCH 0\n+/** Maximum size of hash table that can be created. */\n+#define RTE_MEMBER_ENTRIES_MAX (1 << 30)\n+/** Maximum number of keys that can be searched as a bulk */\n+#define RTE_MEMBER_LOOKUP_BULK_MAX 64\n+/** Entry count per bucket in hash table based mode. */\n+#define RTE_MEMBER_BUCKET_ENTRIES 16\n+/** Maximum number of characters in setsum name. */\n+#define RTE_MEMBER_NAMESIZE 32\n+\n+/** @internal Primary hash function to calculate 1st independent hash. */\n+#define MEMBER_PRIM_HASH(key, key_len, seed) \\\n+\t(uint32_t)(rte_hash_crc(key, key_len, seed))\n+/** @internal Secondary hash function to calculate 2nd independent hash. */\n+#define MEMBER_SEC_HASH(key, key_len, seed) \\\n+\t(uint32_t)(rte_hash_crc(key, key_len, seed))\n+\n+\n+struct rte_member_setsum;\n+\n+/**\n+ * @warning\n+ * @b EXPERIMENTAL: this API may change without prior notice\n+ *\n+ * Parameter struct used to create set summary\n+ */\n+struct rte_member_parameters;\n+\n+\n+/**\n+ * @warning\n+ * @b EXPERIMENTAL: this API may change without prior notice\n+ *\n+ * Define different set summary types\n+ */\n+enum rte_member_setsum_type {\n+\tRTE_MEMBER_TYPE_HT = 0, /**< Hash table based set summary. */\n+\tRTE_MEMBER_TYPE_VBF, /**< vector of bloom filters. */\n+\tRTE_MEMBER_NUM_TYPE\n+};\n+\n+/** @internal compare function for different arch. */\n+enum rte_member_sig_compare_function {\n+\tRTE_MEMBER_COMPARE_SCALAR = 0,\n+\tRTE_MEMBER_COMPARE_AVX2,\n+\tRTE_MEMBER_COMPARE_NUM\n+};\n+\n+/** @internal setsummary structure. */\n+struct rte_member_setsum {\n+\tenum rte_member_setsum_type type;\n+\tconst char *name;\n+\tuint32_t key_len;\n+\tuint32_t socket_id; /* NUMA Socket ID for memory. */\n+\tuint32_t prim_hash_seed;\n+\tuint32_t sec_hash_seed;\n+\n+\n+\t/* hash table based */\n+\tuint32_t bucket_cnt;\n+\tuint32_t bucket_mask;\n+\tuint8_t cache;\n+\tenum rte_member_sig_compare_function sig_cmp_fn;\n+\n+\t/* vector bloom filter*/\n+\tuint32_t num_set;\n+\tuint32_t bits;\n+\tuint32_t bit_mask;\n+\tuint32_t num_hashes;\n+\tvoid *table;\n+};\n+\n+\n+/**\n+ * @warning\n+ * @b EXPERIMENTAL: this API may change without prior notice\n+ *\n+ * Parameters used when create the set summary table. Currently user can\n+ * specify two types of setsummary: HT based and vBF. For HT based, user can\n+ * specify cache or non-cache mode. Here is a table to describe some differences\n+ *\n+ */\n+struct rte_member_parameters {\n+\tconst char *name;\t\t\t/**< Name of the hash. */\n+\n+\t/**\n+\t * User to specify the type of the setsummary from one of\n+\t * rte_member_setsum_type.\n+\t *\n+\t * HT based setsummary is implemented like a hash table. User should use\n+\t * this type when there are many sets.\n+\t *\n+\t * vBF setsummary is a vector of bloom filters. It is used when number\n+\t * of sets is not big (less than 32 for current implementation).\n+\t */\n+\tenum rte_member_setsum_type type;\n+\t/**\n+\t * If it is HT based setsummary, user to specify the subtype or mode\n+\t * of the setsummary. It could be cache, or non-cache mode.\n+\t * Set iscache to be 1 if to use as cache mode.\n+\t *\n+\t * For cache mode, keys can be evicted out of the HT setsummary. Keys\n+\t * with the same signature and map to the same bucket\n+\t * will overwrite each other in the setsummary table.\n+\t * This mode is useful for the case that the set-summary only\n+\t * needs to keep record of the recently inserted keys. Both\n+\t * false-negative and false-positive could happen.\n+\t *\n+\t * For non-cache mode, keys cannot be evicted out of the cache. So for\n+\t * this mode the setsummary will become full eventually. Keys with the\n+\t * same signature but map to the same bucket will still occupy multiple\n+\t * entries. This mode does not give false-negative result.\n+\t */\n+\tuint8_t iscache;\n+\n+\t/**\n+\t * For HT setsummary, num_keys equals to the number of entries of the\n+\t * table. When the number of keys that inserted to the HT setsummary\n+\t * approaches this number, eviction could happen. For cache mode,\n+\t * keys could be evicted out of the table. For non-cache mode, keys will\n+\t * be evicted to other buckets like cuckoo hash. The table will also\n+\t * likely to become full before the number of inserted keys equal to the\n+\t * total number of entries.\n+\t *\n+\t * For vBF, num_keys equal to the expected number of keys that will\n+\t * be inserted into the vBF. The implementation assumes the keys are\n+\t * evenly distributed to each BF in vBF. This is used to calculate the\n+\t * number of bits we need for each BF. User does not specify the size of\n+\t * each BF directly because the optimal size depends on the num_keys\n+\t * and false positive rate.\n+\t */\n+\tuint32_t num_keys;\n+\n+\n+\t/**\n+\t * The length of key is used for hash calculation. Since key is not\n+\t * stored in set-summary, large key does not require more memory space.\n+\t */\n+\tuint32_t key_len;\n+\n+\n+\t/**\n+\t * num_set is only relevant to vBF based setsummary.\n+\t * num_set is equal to the number of BFs in vBF. For current\n+\t * implementation, it only supports 1,2,4,8,16,32 BFs in one vBF set\n+\t * summary. If other number of sets are needed, for example 5, the user\n+\t * should allocate the minimum available value that larger than 5,\n+\t * which is 8.\n+\t */\n+\tuint32_t num_set;\n+\n+\t/**\n+\t * false_postive_rate is only relevant to vBF based setsummary.\n+\t * false_postivie_rate is the user-defined false positive rate\n+\t * given expected number of inserted keys (num_keys). It is used to\n+\t * calculate the total number of bits for each BF, and the number of\n+\t * hash values used during lookup and insertion. For details please\n+\t * refer to vBF implementation and membership library documentation.\n+\t *\n+\t * HT setsummary's false positive rate is in the order of:\n+\t * false_pos = (1/bucket_count)*(1/2^16), since we use 16-bit signature.\n+\t * This is because two keys needs to map to same bucket and same\n+\t * signature to have a collision (false positive). bucket_count is equal\n+\t * to number of entries (num_keys) divided by entry count per bucket\n+\t * (RTE_MEMBER_BUCKET_ENTRIES). Thus, the false_postivie_rate is not\n+\t * directly set by users.\n+\t */\n+\tfloat false_positive_rate;\n+\n+\t/**\n+\t * We use two seeds to calculate two independent hashes for each key.\n+\t *\n+\t * For HT type, one hash is used as signature, and the other is used\n+\t * for bucket location.\n+\t * For vBF type, these two hashes and their combinations are used as\n+\t * hash locations to index the bit array.\n+\t */\n+\tuint32_t prim_hash_seed;\n+\n+\t/**\n+\t * The secondary seed should be a different value from the primary seed.\n+\t */\n+\tuint32_t sec_hash_seed;\n+\n+\tint socket_id;\t\t\t/**< NUMA Socket ID for memory. */\n+};\n+\n+/**\n+ * @warning\n+ * @b EXPERIMENTAL: this API may change without prior notice\n+ *\n+ * Find an existing set-summary and return a pointer to it.\n+ *\n+ * @param name\n+ * Name of the set-summary\n+ * @return\n+ * Pointer to the set-summary or NULL if object not found\n+ * with rte_errno set appropriately. Possible rte_errno values include:\n+ * - ENOENT - value not available for return\n+ */\n+void *\n+rte_member_find_existing(const char *name);\n+\n+/**\n+ * @warning\n+ * @b EXPERIMENTAL: this API may change without prior notice\n+ *\n+ * Create set-summary (SS).\n+ *\n+ * @param params\n+ * parameters to initialize the setsummary\n+ * @return\n+ * return the pointer to the setsummary\n+ * return value is NULL if the creation failed\n+ */\n+\n+void *\n+rte_member_create(const struct rte_member_parameters *params);\n+\n+\n+\n+/**\n+ * @warning\n+ * @b EXPERIMENTAL: this API may change without prior notice\n+ *\n+ * Lookup key in set-summary (SS).\n+ * Single key lookup and return as soon as the first match found\n+ * @param setsum\n+ * pointer of a setsummary\n+ * @param key\n+ * pointer of the key that needs to lookup\n+ * @param set_id\n+ * output the set id matches the key\n+ * @return\n+ * return 1 for found a match and 0 for not found a match\n+ */\n+\n+int\n+rte_member_lookup(const void *setsum,\n+\t\tconst void *key, MEMBER_SET_TYPE *set_id);\n+\n+\n+/**\n+ * @warning\n+ * @b EXPERIMENTAL: this API may change without prior notice\n+ *\n+ * lookup bulk of keys in set-summary (SS).\n+ * Each key lookup returns as soon as the first match found\n+ * @param setsum\n+ * Pointer of a setsummary\n+ * @param keys\n+ * Pointer of bulk of keys that to be lookup\n+ * @param num_keys\n+ * Number of keys that will be lookup\n+ * @param set_ids\n+ * Output set ids for all the keys to this array.\n+ * User should preallocate array that can contain all results, which size is\n+ * the num_keys.\n+ * @return\n+ * The number of keys that found a match\n+ */\n+\n+\n+int\n+rte_member_lookup_bulk(const void *setsum,\n+\t\tconst void **keys, uint32_t num_keys,\n+\t\tMEMBER_SET_TYPE *set_ids);\n+\n+\n+\n+\n+/**\n+ * @warning\n+ * @b EXPERIMENTAL: this API may change without prior notice\n+ *\n+ * Lookup a key in set-summary (SS) for multiple matches.\n+ * The key lookup will find all matched entries (multiple match).\n+ * Note that for cache mode of HT, each key can have at most one match. This is\n+ * because keys with same signature that maps to same bucket will overwrite\n+ * each other. So multi-match lookup should be used for vBF and non-cache HT.\n+ * @param setsum\n+ * pointer of a set-summary\n+ * @param key\n+ * The key that to be lookup\n+ * @param max_match_per_key\n+ * User specified maximum number of matches for each key. The function returns\n+ * as soon as this number of matches found for the key.\n+ * @param set_id\n+ * Output set ids for all the matches of the key. User needs to preallocate\n+ * the array that can contain max_match_per_key number of results.\n+ * @return\n+ * The number of matches that found for the key.\n+ * For cache mode HT set-summary, the number should be at most 1\n+ */\n+\n+int\n+rte_member_lookup_multi(const void *setsum,\n+\t\tconst void *key, uint32_t max_match_per_key,\n+\t\tMEMBER_SET_TYPE *set_id);\n+\n+\n+\n+\n+/**\n+ * @warning\n+ * @b EXPERIMENTAL: this API may change without prior notice\n+ *\n+ * Lookup a bulk of keys in set-summary (SS) for multiple matches each key.\n+ * Each key lookup will find all matched entries (multiple match).\n+ * Note that for cache mode HT, each key can have at most one match. So\n+ * multi-match function is mainly used for vBF and non-cache mode HT.\n+ * @param setsum\n+ * pointer of a setsummary\n+ * @param keys\n+ * The keys that to be lookup\n+ * @param num_keys\n+ * The number of keys that will be lookup\n+ * @param max_match_per_key\n+ * The possible maximum number of matches for each key\n+ * @param match_count\n+ * Output the number of matches for each key in an array\n+ * @param set_ids\n+ * Return set ids for all the matches of all keys. User pass in a preallocated\n+ * 2D array with first dimension as key index and second dimension as match\n+ * index. For example set_ids[bulk_size][max_match_per_key]\n+ * @return\n+ * The number of keys that found one or more matches in the set-summary\n+ */\n+\n+int\n+rte_member_lookup_multi_bulk(const void *setsum,\n+\t\tconst void **keys, uint32_t num_keys,\n+\t\tuint32_t max_match_per_key,\n+\t\tuint32_t *match_count,\n+\t\tMEMBER_SET_TYPE *set_ids);\n+\n+/**\n+ * @warning\n+ * @b EXPERIMENTAL: this API may change without prior notice\n+ *\n+ * Insert key into set-summary (SS).\n+ *\n+ * @param setsum\n+ * pointer of a set-summary\n+ * @param key\n+ * the key that needs to be added\n+ * @param set_id\n+ * The set id associated with the key that needs to be added. Different mode\n+ * supports different set_id ranges. 0 cannot be used as set_id since\n+ * RTE_MEMBER_NO_MATCH by default is set as 0.\n+ * For HT mode, the set_id has range as [1, 0x7FFF], MSB is reserved.\n+ * For vBF mode the set id is limited by the num_set parameter when create\n+ * the set-summary.\n+ * @return\n+ * HT (cache mode) and vBF should never fail unless the set_id is not in the\n+ * valid range. In such case -EINVAL is returned.\n+ * For HT (non-cache mode) it could fail with -ENOSPC error code when table is\n+ * full.\n+ * For success it returns different values for different modes to provide\n+ * extra information for users.\n+ * Return 0 for HT (cache mode) if the add does not cause\n+ * eviction, return 1 otherwise. Return 0 for HT mode if success, -ENOSPC for\n+ * full, and 1 if cuckoo eviction happens. Always return 0 for vBF mode.\n+ */\n+\n+int\n+rte_member_add(const void *setsum, const void *key,\n+\t\tMEMBER_SET_TYPE set_id);\n+\n+\n+/**\n+ * @warning\n+ * @b EXPERIMENTAL: this API may change without prior notice\n+ *\n+ * De-allocate memory used by set-summary.\n+ * @param setsum\n+ * Pointer to the set summary\n+ */\n+void\n+rte_member_free(void *setsum);\n+\n+\n+\n+/**\n+ * @warning\n+ * @b EXPERIMENTAL: this API may change without prior notice\n+ *\n+ * Reset the set-summary tables. E.g. reset bits to be 0 in BF,\n+ * reset set_id in each entry to be RTE_MEMBER_NO_MATCH in HT based SS.\n+ * @param setsum\n+ * Pointer to the set-summary\n+ */\n+void\n+rte_member_reset(const void *setsum);\n+\n+\n+\n+\n+/**\n+ * @warning\n+ * @b EXPERIMENTAL: this API may change without prior notice\n+ *\n+ * Delete items from the set-summary. Note that vBF does not support deletion\n+ * in current implementation. For vBF, error code of -EINVAL will be returned.\n+ * @param setsum\n+ * Pointer to the set-summary\n+ * @param key\n+ * The key to be deleted\n+ * @param set_id\n+ * For HT mode, we need both key and its corresponding set_id to\n+ * properly delete the key. Without set_id, we may delete other keys with the\n+ * same signature\n+ * @return\n+ * If no entry found to delete, an error code of -ENOENT could be returned\n+ */\n+\n+int\n+rte_member_delete(void *setsum, const void *key,\n+\t\tMEMBER_SET_TYPE set_id);\n+\n+\n+\n+#ifdef __cplusplus\n+}\n+#endif\n+\n+#endif /* _RTE_MEMBER_H_ */\ndiff --git a/lib/librte_member/rte_member_version.map b/lib/librte_member/rte_member_version.map\nnew file mode 100644\nindex 0000000..a5877c9\n--- /dev/null\n+++ b/lib/librte_member/rte_member_version.map\n@@ -0,0 +1,16 @@\n+DPDK_17.11 {\n+\tglobal:\n+\n+\trte_member_create;\n+\trte_member_find_existing;\n+\trte_member_lookup;\n+\trte_member_lookup_bulk;\n+\trte_member_lookup_multi;\n+\trte_member_lookup_multi_bulk;\n+\trte_member_add;\n+\trte_member_free;\n+\trte_member_reset;\n+\trte_member_delete;\n+\n+\tlocal: *;\n+};\n", "prefixes": [ "dpdk-dev", "v2", "1/7" ] }