aboutsummaryrefslogtreecommitdiffstats
path: root/lib/librte_member
diff options
context:
space:
mode:
authorLuca Boccassi <luca.boccassi@gmail.com>2017-11-08 14:15:11 +0000
committerLuca Boccassi <luca.boccassi@gmail.com>2017-11-08 14:45:54 +0000
commit055c52583a2794da8ba1e85a48cce3832372b12f (patch)
tree8ceb1cb78fbb46a0f341f8ee24feb3c6b5540013 /lib/librte_member
parentf239aed5e674965691846e8ce3f187dd47523689 (diff)
New upstream version 17.11-rc3
Change-Id: I6a5baa40612fe0c20f30b5fa773a6cbbac63a685 Signed-off-by: Luca Boccassi <luca.boccassi@gmail.com>
Diffstat (limited to 'lib/librte_member')
-rw-r--r--lib/librte_member/Makefile52
-rw-r--r--lib/librte_member/rte_member.c336
-rw-r--r--lib/librte_member/rte_member.h513
-rw-r--r--lib/librte_member/rte_member_ht.c586
-rw-r--r--lib/librte_member/rte_member_ht.h94
-rw-r--r--lib/librte_member/rte_member_vbf.c350
-rw-r--r--lib/librte_member/rte_member_vbf.h82
-rw-r--r--lib/librte_member/rte_member_version.map16
-rw-r--r--lib/librte_member/rte_member_x86.h107
9 files changed, 2136 insertions, 0 deletions
diff --git a/lib/librte_member/Makefile b/lib/librte_member/Makefile
new file mode 100644
index 00000000..f4cf101e
--- /dev/null
+++ b/lib/librte_member/Makefile
@@ -0,0 +1,52 @@
+# 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 := -I$(SRCDIR) $(CFLAGS)
+CFLAGS += $(WERROR_FLAGS) -O3
+
+LDLIBS += -lm
+LDLIBS += -lrte_eal -lrte_hash
+
+EXPORT_MAP := rte_member_version.map
+
+LIBABIVER := 1
+
+# all source are stored in SRCS-y
+SRCS-$(CONFIG_RTE_LIBRTE_MEMBER) += rte_member.c rte_member_ht.c rte_member_vbf.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 00000000..cc9ea84a
--- /dev/null
+++ b/lib/librte_member/rte_member.c
@@ -0,0 +1,336 @@
+/*-
+ * 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 <string.h>
+
+#include <rte_eal.h>
+#include <rte_eal_memconfig.h>
+#include <rte_memory.h>
+#include <rte_malloc.h>
+#include <rte_errno.h>
+
+#include "rte_member.h"
+#include "rte_member_ht.h"
+#include "rte_member_vbf.h"
+
+int librte_member_logtype;
+
+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)
+
+struct rte_member_setsum *
+rte_member_find_existing(const char *name)
+{
+ struct rte_member_setsum *setsum = NULL;
+ 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(struct rte_member_setsum *setsum)
+{
+ struct rte_member_list *member_list;
+ struct rte_tailq_entry *te;
+
+ if (setsum == NULL)
+ return;
+ 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 == (void *)setsum)
+ 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);
+}
+
+struct rte_member_setsum *
+rte_member_create(const struct rte_member_parameters *params)
+{
+ struct rte_tailq_entry *te;
+ struct rte_member_list *member_list;
+ struct rte_member_setsum *setsum;
+ int ret;
+
+ if (params == NULL) {
+ rte_errno = EINVAL;
+ return NULL;
+ }
+
+ if (params->key_len == 0 ||
+ params->prim_hash_seed == params->sec_hash_seed) {
+ rte_errno = EINVAL;
+ RTE_MEMBER_LOG(ERR, "Create setsummary 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_MEMBER_LOG(ERR, "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_MEMBER_LOG(ERR, "Create setsummary failed\n");
+ goto error_unlock_exit;
+ }
+ snprintf(setsum->name, sizeof(setsum->name), "%s", params->name);
+ setsum->type = params->type;
+ setsum->socket_id = params->socket_id;
+ setsum->key_len = params->key_len;
+ setsum->num_set = params->num_set;
+ 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_MEMBER_LOG(DEBUG, "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 struct rte_member_setsum *setsum, const void *key,
+ member_set_t set_id)
+{
+ if (setsum == NULL || key == NULL)
+ return -EINVAL;
+
+ switch (setsum->type) {
+ case RTE_MEMBER_TYPE_HT:
+ return rte_member_add_ht(setsum, key, set_id);
+ case RTE_MEMBER_TYPE_VBF:
+ return rte_member_add_vbf(setsum, key, set_id);
+ default:
+ return -EINVAL;
+ }
+}
+
+int
+rte_member_lookup(const struct rte_member_setsum *setsum, const void *key,
+ member_set_t *set_id)
+{
+ if (setsum == NULL || key == NULL || set_id == NULL)
+ return -EINVAL;
+
+ switch (setsum->type) {
+ case RTE_MEMBER_TYPE_HT:
+ return rte_member_lookup_ht(setsum, key, set_id);
+ case RTE_MEMBER_TYPE_VBF:
+ return rte_member_lookup_vbf(setsum, key, set_id);
+ default:
+ return -EINVAL;
+ }
+}
+
+int
+rte_member_lookup_bulk(const struct rte_member_setsum *setsum,
+ const void **keys, uint32_t num_keys,
+ member_set_t *set_ids)
+{
+ if (setsum == NULL || keys == NULL || set_ids == NULL)
+ return -EINVAL;
+
+ switch (setsum->type) {
+ case RTE_MEMBER_TYPE_HT:
+ return rte_member_lookup_bulk_ht(setsum, keys, num_keys,
+ set_ids);
+ case RTE_MEMBER_TYPE_VBF:
+ return rte_member_lookup_bulk_vbf(setsum, keys, num_keys,
+ set_ids);
+ default:
+ return -EINVAL;
+ }
+}
+
+int
+rte_member_lookup_multi(const struct rte_member_setsum *setsum, const void *key,
+ uint32_t match_per_key, member_set_t *set_id)
+{
+ if (setsum == NULL || key == NULL || set_id == NULL)
+ return -EINVAL;
+
+ switch (setsum->type) {
+ case RTE_MEMBER_TYPE_HT:
+ return rte_member_lookup_multi_ht(setsum, key, match_per_key,
+ set_id);
+ case RTE_MEMBER_TYPE_VBF:
+ return rte_member_lookup_multi_vbf(setsum, key, match_per_key,
+ set_id);
+ default:
+ return -EINVAL;
+ }
+}
+
+int
+rte_member_lookup_multi_bulk(const struct rte_member_setsum *setsum,
+ const void **keys, uint32_t num_keys,
+ uint32_t max_match_per_key, uint32_t *match_count,
+ member_set_t *set_ids)
+{
+ if (setsum == NULL || keys == NULL || set_ids == NULL ||
+ match_count == NULL)
+ return -EINVAL;
+
+ switch (setsum->type) {
+ case RTE_MEMBER_TYPE_HT:
+ return rte_member_lookup_multi_bulk_ht(setsum, keys, num_keys,
+ max_match_per_key, match_count, set_ids);
+ case RTE_MEMBER_TYPE_VBF:
+ return rte_member_lookup_multi_bulk_vbf(setsum, keys, num_keys,
+ max_match_per_key, match_count, set_ids);
+ default:
+ return -EINVAL;
+ }
+}
+
+int
+rte_member_delete(const struct rte_member_setsum *setsum, const void *key,
+ member_set_t set_id)
+{
+ if (setsum == NULL || key == NULL)
+ return -EINVAL;
+
+ switch (setsum->type) {
+ case RTE_MEMBER_TYPE_HT:
+ return rte_member_delete_ht(setsum, key, set_id);
+ /* current vBF implementation does not support delete function */
+ case RTE_MEMBER_TYPE_VBF:
+ default:
+ return -EINVAL;
+ }
+}
+
+void
+rte_member_reset(const struct rte_member_setsum *setsum)
+{
+ if (setsum == NULL)
+ return;
+ switch (setsum->type) {
+ case RTE_MEMBER_TYPE_HT:
+ rte_member_reset_ht(setsum);
+ return;
+ case RTE_MEMBER_TYPE_VBF:
+ rte_member_reset_vbf(setsum);
+ return;
+ default:
+ return;
+ }
+}
+
+RTE_INIT(librte_member_init_log);
+
+static void
+librte_member_init_log(void)
+{
+ librte_member_logtype = rte_log_register("librte.member");
+ if (librte_member_logtype >= 0)
+ rte_log_set_level(librte_member_logtype, RTE_LOG_DEBUG);
+}
diff --git a/lib/librte_member/rte_member.h b/lib/librte_member/rte_member.h
new file mode 100644
index 00000000..9b0c8f99
--- /dev/null
+++ b/lib/librte_member/rte_member.h
@@ -0,0 +1,513 @@
+/*-
+ * 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 and cuckoo 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 subtypes 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
+ */
+
+/**
+ * <!--
+ * +==========+=====================+================+=========================+
+ * | type | vbf | HT-cache | HT-non-cache |
+ * +==========+=====================+==========================================+
+ * |structure | bloom-filter array | hash-table like without storing key |
+ * +----------+---------------------+------------------------------------------+
+ * |set id | limited by bf count | [1, 0x7fff] |
+ * | | up to 32. | |
+ * +----------+---------------------+------------------------------------------+
+ * |usages & | small set range, | can delete, | cache most recent keys, |
+ * |properties| user-specified | big set range, | have both false-positive|
+ * | | false-positive rate,| small false | and false-negative |
+ * | | no deletion support.| positive depend| depend on table size, |
+ * | | | on table size, | automatic overwritten. |
+ * | | | new key does | |
+ * | | | not overwrite | |
+ * | | | existing key. | |
+ * +----------+---------------------+----------------+-------------------------+
+ * -->
+ */
+
+#ifndef _RTE_MEMBER_H_
+#define _RTE_MEMBER_H_
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <stdint.h>
+
+/** The set ID type that stored internally in hash table based set summary. */
+typedef uint16_t member_set_t;
+/** 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 Hash function used by membership library. */
+#if defined(RTE_ARCH_X86) || defined(RTE_MACHINE_CPUFLAG_CRC32)
+#include <rte_hash_crc.h>
+#define MEMBER_HASH_FUNC rte_hash_crc
+#else
+#include <rte_jhash.h>
+#define MEMBER_HASH_FUNC rte_jhash
+#endif
+
+extern int librte_member_logtype;
+
+#define RTE_MEMBER_LOG(level, fmt, args...) \
+rte_log(RTE_LOG_ ## level, librte_member_logtype, "%s(): " fmt, \
+ __func__, ## args)
+
+/** @internal setsummary structure. */
+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; /* Type of the set summary. */
+ uint32_t key_len; /* Length of key. */
+ uint32_t prim_hash_seed; /* Primary hash function seed. */
+ uint32_t sec_hash_seed; /* Secondary hash function seed. */
+
+ /* Hash table based. */
+ uint32_t bucket_cnt; /* Number of buckets. */
+ uint32_t bucket_mask; /* Bit mask to get bucket index. */
+ /* For runtime selecting AVX, scalar, etc for signature comparison. */
+ enum rte_member_sig_compare_function sig_cmp_fn;
+ uint8_t cache; /* If it is cache mode for ht based. */
+
+ /* Vector bloom filter. */
+ uint32_t num_set; /* Number of set (bf) in vbf. */
+ uint32_t bits; /* Number of bits in each bf. */
+ uint32_t bit_mask; /* Bit mask to get bit location in bf. */
+ uint32_t num_hashes; /* Number of hash values to index bf. */
+
+ uint32_t mul_shift; /* vbf internal variable used during bit test. */
+ uint32_t div_shift; /* vbf internal variable used during bit test. */
+
+ void *table; /* This is the handler of hash table or vBF array. */
+
+
+ /* Second cache line should start here. */
+ uint32_t socket_id; /* NUMA Socket ID for memory. */
+ char name[RTE_MEMBER_NAMESIZE]; /* Name of this set summary. */
+} __rte_cache_aligned;
+
+/**
+ * @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;
+
+ /**
+ * is_cache is only used for HT based setsummary.
+ *
+ * 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 is_cache 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 is_cache;
+
+ /**
+ * For HT setsummary, num_keys equals to the number of entries of the
+ * table. When the number of keys inserted in 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 used for vBF, but not used for HT 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_positive_rate is only used for vBF, but not used for HT
+ * setsummary.
+ *
+ * For vBF, false_positive_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.
+ *
+ * For HT, This parameter is not directly set by users.
+ * 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_positive_rate is not
+ * directly set by users for HT mode.
+ */
+ 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
+ */
+struct rte_member_setsum *
+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.
+ */
+struct rte_member_setsum *
+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 to be looked up.
+ * @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 struct rte_member_setsum *setsum, const void *key,
+ member_set_t *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 the bulk of keys to be looked up.
+ * @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 struct rte_member_setsum *setsum,
+ const void **keys, uint32_t num_keys,
+ member_set_t *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
+ * Pointer of the key that to be looked up.
+ * @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 struct rte_member_setsum *setsum,
+ const void *key, uint32_t max_match_per_key,
+ member_set_t *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
+ * Pointer of the keys to be looked up.
+ * @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. Users 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 struct rte_member_setsum *setsum,
+ const void **keys, uint32_t num_keys,
+ uint32_t max_match_per_key,
+ uint32_t *match_count,
+ member_set_t *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
+ * Pointer of the key 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 non-cache mode if success,
+ * -ENOSPC for full, and 1 if cuckoo eviction happens.
+ * Always returns 0 for vBF mode.
+ */
+int
+rte_member_add(const struct rte_member_setsum *setsum, const void *key,
+ member_set_t 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(struct rte_member_setsum *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 struct rte_member_setsum *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
+ * Pointer of 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(const struct rte_member_setsum *setsum, const void *key,
+ member_set_t set_id);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_MEMBER_H_ */
diff --git a/lib/librte_member/rte_member_ht.c b/lib/librte_member/rte_member_ht.c
new file mode 100644
index 00000000..59332d56
--- /dev/null
+++ b/lib/librte_member/rte_member_ht.c
@@ -0,0 +1,586 @@
+/*-
+ * 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_errno.h>
+#include <rte_malloc.h>
+#include <rte_prefetch.h>
+#include <rte_random.h>
+#include <rte_log.h>
+
+#include "rte_member.h"
+#include "rte_member_ht.h"
+
+#if defined(RTE_ARCH_X86)
+#include "rte_member_x86.h"
+#endif
+
+/* Search bucket for entry with tmp_sig and update set_id */
+static inline int
+update_entry_search(uint32_t bucket_id, member_sig_t tmp_sig,
+ struct member_ht_bucket *buckets,
+ member_set_t set_id)
+{
+ uint32_t i;
+
+ for (i = 0; i < RTE_MEMBER_BUCKET_ENTRIES; i++) {
+ if (buckets[bucket_id].sigs[i] == tmp_sig) {
+ buckets[bucket_id].sets[i] = set_id;
+ return 1;
+ }
+ }
+ return 0;
+}
+
+static inline int
+search_bucket_single(uint32_t bucket_id, member_sig_t tmp_sig,
+ struct member_ht_bucket *buckets,
+ member_set_t *set_id)
+{
+ uint32_t iter;
+
+ for (iter = 0; iter < RTE_MEMBER_BUCKET_ENTRIES; iter++) {
+ if (tmp_sig == buckets[bucket_id].sigs[iter] &&
+ buckets[bucket_id].sets[iter] !=
+ RTE_MEMBER_NO_MATCH) {
+ *set_id = buckets[bucket_id].sets[iter];
+ return 1;
+ }
+ }
+ return 0;
+}
+
+static inline void
+search_bucket_multi(uint32_t bucket_id, member_sig_t tmp_sig,
+ struct member_ht_bucket *buckets,
+ uint32_t *counter,
+ uint32_t matches_per_key,
+ member_set_t *set_id)
+{
+ uint32_t iter;
+
+ for (iter = 0; iter < RTE_MEMBER_BUCKET_ENTRIES; iter++) {
+ if (tmp_sig == buckets[bucket_id].sigs[iter] &&
+ buckets[bucket_id].sets[iter] !=
+ RTE_MEMBER_NO_MATCH) {
+ set_id[*counter] = buckets[bucket_id].sets[iter];
+ (*counter)++;
+ if (*counter >= matches_per_key)
+ return;
+ }
+ }
+}
+
+int
+rte_member_create_ht(struct rte_member_setsum *ss,
+ const struct rte_member_parameters *params)
+{
+ uint32_t i, j;
+ uint32_t size_bucket_t;
+ uint32_t num_entries = rte_align32pow2(params->num_keys);
+
+ if ((num_entries > RTE_MEMBER_ENTRIES_MAX) ||
+ !rte_is_power_of_2(RTE_MEMBER_BUCKET_ENTRIES) ||
+ num_entries < RTE_MEMBER_BUCKET_ENTRIES) {
+ rte_errno = EINVAL;
+ RTE_MEMBER_LOG(ERR,
+ "Membership HT create with invalid parameters\n");
+ return -EINVAL;
+ }
+
+ uint32_t num_buckets = num_entries / RTE_MEMBER_BUCKET_ENTRIES;
+
+ size_bucket_t = sizeof(struct member_ht_bucket);
+
+ struct member_ht_bucket *buckets = rte_zmalloc_socket(NULL,
+ num_buckets * size_bucket_t,
+ RTE_CACHE_LINE_SIZE, ss->socket_id);
+
+ if (buckets == NULL) {
+ RTE_MEMBER_LOG(ERR, "memory allocation failed for HT "
+ "setsummary\n");
+ return -ENOMEM;
+ }
+
+ ss->table = buckets;
+ ss->bucket_cnt = num_buckets;
+ ss->bucket_mask = num_buckets - 1;
+ ss->cache = params->is_cache;
+
+ for (i = 0; i < num_buckets; i++) {
+ for (j = 0; j < RTE_MEMBER_BUCKET_ENTRIES; j++)
+ buckets[i].sets[j] = RTE_MEMBER_NO_MATCH;
+ }
+#if defined(RTE_ARCH_X86)
+ if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX2) &&
+ RTE_MEMBER_BUCKET_ENTRIES == 16)
+ ss->sig_cmp_fn = RTE_MEMBER_COMPARE_AVX2;
+ else
+#endif
+ ss->sig_cmp_fn = RTE_MEMBER_COMPARE_SCALAR;
+
+ RTE_MEMBER_LOG(DEBUG, "Hash table based filter created, "
+ "the table has %u entries, %u buckets\n",
+ num_entries, num_buckets);
+ return 0;
+}
+
+static inline void
+get_buckets_index(const struct rte_member_setsum *ss, const void *key,
+ uint32_t *prim_bkt, uint32_t *sec_bkt, member_sig_t *sig)
+{
+ uint32_t first_hash = MEMBER_HASH_FUNC(key, ss->key_len,
+ ss->prim_hash_seed);
+ uint32_t sec_hash = MEMBER_HASH_FUNC(&first_hash, sizeof(uint32_t),
+ ss->sec_hash_seed);
+ /*
+ * We use the first hash value for the signature, and the second hash
+ * value to derive the primary and secondary bucket locations.
+ *
+ * For non-cache mode, we use the lower bits for the primary bucket
+ * location. Then we xor primary bucket location and the signature
+ * to get the secondary bucket location. This is called "partial-key
+ * cuckoo hashing" proposed by B. Fan, et al's paper
+ * "Cuckoo Filter: Practically Better Than Bloom". The benefit to use
+ * xor is that one could derive the alternative bucket location
+ * by only using the current bucket location and the signature. This is
+ * generally required by non-cache mode's eviction and deletion
+ * process without the need to store alternative hash value nor the full
+ * key.
+ *
+ * For cache mode, we use the lower bits for the primary bucket
+ * location and the higher bits for the secondary bucket location. In
+ * cache mode, keys are simply overwritten if bucket is full. We do not
+ * use xor since lower/higher bits are more independent hash values thus
+ * should provide slightly better table load.
+ */
+ *sig = first_hash;
+ if (ss->cache) {
+ *prim_bkt = sec_hash & ss->bucket_mask;
+ *sec_bkt = (sec_hash >> 16) & ss->bucket_mask;
+ } else {
+ *prim_bkt = sec_hash & ss->bucket_mask;
+ *sec_bkt = (*prim_bkt ^ *sig) & ss->bucket_mask;
+ }
+}
+
+int
+rte_member_lookup_ht(const struct rte_member_setsum *ss,
+ const void *key, member_set_t *set_id)
+{
+ uint32_t prim_bucket, sec_bucket;
+ member_sig_t tmp_sig;
+ struct member_ht_bucket *buckets = ss->table;
+
+ *set_id = RTE_MEMBER_NO_MATCH;
+ get_buckets_index(ss, key, &prim_bucket, &sec_bucket, &tmp_sig);
+
+ switch (ss->sig_cmp_fn) {
+#if defined(RTE_ARCH_X86) && defined(RTE_MACHINE_CPUFLAG_AVX2)
+ case RTE_MEMBER_COMPARE_AVX2:
+ if (search_bucket_single_avx(prim_bucket, tmp_sig, buckets,
+ set_id) ||
+ search_bucket_single_avx(sec_bucket, tmp_sig,
+ buckets, set_id))
+ return 1;
+ break;
+#endif
+ default:
+ if (search_bucket_single(prim_bucket, tmp_sig, buckets,
+ set_id) ||
+ search_bucket_single(sec_bucket, tmp_sig,
+ buckets, set_id))
+ return 1;
+ }
+
+ return 0;
+}
+
+uint32_t
+rte_member_lookup_bulk_ht(const struct rte_member_setsum *ss,
+ const void **keys, uint32_t num_keys, member_set_t *set_id)
+{
+ uint32_t i;
+ uint32_t num_matches = 0;
+ struct member_ht_bucket *buckets = ss->table;
+ member_sig_t tmp_sig[RTE_MEMBER_LOOKUP_BULK_MAX];
+ uint32_t prim_buckets[RTE_MEMBER_LOOKUP_BULK_MAX];
+ uint32_t sec_buckets[RTE_MEMBER_LOOKUP_BULK_MAX];
+
+ for (i = 0; i < num_keys; i++) {
+ get_buckets_index(ss, keys[i], &prim_buckets[i],
+ &sec_buckets[i], &tmp_sig[i]);
+ rte_prefetch0(&buckets[prim_buckets[i]]);
+ rte_prefetch0(&buckets[sec_buckets[i]]);
+ }
+
+ for (i = 0; i < num_keys; i++) {
+ switch (ss->sig_cmp_fn) {
+#if defined(RTE_ARCH_X86) && defined(RTE_MACHINE_CPUFLAG_AVX2)
+ case RTE_MEMBER_COMPARE_AVX2:
+ if (search_bucket_single_avx(prim_buckets[i],
+ tmp_sig[i], buckets, &set_id[i]) ||
+ search_bucket_single_avx(sec_buckets[i],
+ tmp_sig[i], buckets, &set_id[i]))
+ num_matches++;
+ else
+ set_id[i] = RTE_MEMBER_NO_MATCH;
+ break;
+#endif
+ default:
+ if (search_bucket_single(prim_buckets[i], tmp_sig[i],
+ buckets, &set_id[i]) ||
+ search_bucket_single(sec_buckets[i],
+ tmp_sig[i], buckets, &set_id[i]))
+ num_matches++;
+ else
+ set_id[i] = RTE_MEMBER_NO_MATCH;
+ }
+ }
+ return num_matches;
+}
+
+uint32_t
+rte_member_lookup_multi_ht(const struct rte_member_setsum *ss,
+ const void *key, uint32_t match_per_key,
+ member_set_t *set_id)
+{
+ uint32_t num_matches = 0;
+ uint32_t prim_bucket, sec_bucket;
+ member_sig_t tmp_sig;
+ struct member_ht_bucket *buckets = ss->table;
+
+ get_buckets_index(ss, key, &prim_bucket, &sec_bucket, &tmp_sig);
+
+ switch (ss->sig_cmp_fn) {
+#if defined(RTE_ARCH_X86) && defined(RTE_MACHINE_CPUFLAG_AVX2)
+ case RTE_MEMBER_COMPARE_AVX2:
+ search_bucket_multi_avx(prim_bucket, tmp_sig, buckets,
+ &num_matches, match_per_key, set_id);
+ if (num_matches < match_per_key)
+ search_bucket_multi_avx(sec_bucket, tmp_sig,
+ buckets, &num_matches, match_per_key, set_id);
+ return num_matches;
+#endif
+ default:
+ search_bucket_multi(prim_bucket, tmp_sig, buckets, &num_matches,
+ match_per_key, set_id);
+ if (num_matches < match_per_key)
+ search_bucket_multi(sec_bucket, tmp_sig,
+ buckets, &num_matches, match_per_key, set_id);
+ return num_matches;
+ }
+}
+
+uint32_t
+rte_member_lookup_multi_bulk_ht(const struct rte_member_setsum *ss,
+ const void **keys, uint32_t num_keys, uint32_t match_per_key,
+ uint32_t *match_count,
+ member_set_t *set_ids)
+{
+ uint32_t i;
+ uint32_t num_matches = 0;
+ struct member_ht_bucket *buckets = ss->table;
+ uint32_t match_cnt_tmp;
+ member_sig_t tmp_sig[RTE_MEMBER_LOOKUP_BULK_MAX];
+ uint32_t prim_buckets[RTE_MEMBER_LOOKUP_BULK_MAX];
+ uint32_t sec_buckets[RTE_MEMBER_LOOKUP_BULK_MAX];
+
+ for (i = 0; i < num_keys; i++) {
+ get_buckets_index(ss, keys[i], &prim_buckets[i],
+ &sec_buckets[i], &tmp_sig[i]);
+ rte_prefetch0(&buckets[prim_buckets[i]]);
+ rte_prefetch0(&buckets[sec_buckets[i]]);
+ }
+ for (i = 0; i < num_keys; i++) {
+ match_cnt_tmp = 0;
+
+ switch (ss->sig_cmp_fn) {
+#if defined(RTE_ARCH_X86) && defined(RTE_MACHINE_CPUFLAG_AVX2)
+ case RTE_MEMBER_COMPARE_AVX2:
+ search_bucket_multi_avx(prim_buckets[i], tmp_sig[i],
+ buckets, &match_cnt_tmp, match_per_key,
+ &set_ids[i*match_per_key]);
+ if (match_cnt_tmp < match_per_key)
+ search_bucket_multi_avx(sec_buckets[i],
+ tmp_sig[i], buckets, &match_cnt_tmp,
+ match_per_key,
+ &set_ids[i*match_per_key]);
+ match_count[i] = match_cnt_tmp;
+ if (match_cnt_tmp != 0)
+ num_matches++;
+ break;
+#endif
+ default:
+ search_bucket_multi(prim_buckets[i], tmp_sig[i],
+ buckets, &match_cnt_tmp, match_per_key,
+ &set_ids[i*match_per_key]);
+ if (match_cnt_tmp < match_per_key)
+ search_bucket_multi(sec_buckets[i], tmp_sig[i],
+ buckets, &match_cnt_tmp, match_per_key,
+ &set_ids[i*match_per_key]);
+ match_count[i] = match_cnt_tmp;
+ if (match_cnt_tmp != 0)
+ num_matches++;
+ }
+ }
+ return num_matches;
+}
+
+static inline int
+try_insert(struct member_ht_bucket *buckets, uint32_t prim, uint32_t sec,
+ member_sig_t sig, member_set_t set_id)
+{
+ int i;
+ /* If not full then insert into one slot */
+ for (i = 0; i < RTE_MEMBER_BUCKET_ENTRIES; i++) {
+ if (buckets[prim].sets[i] == RTE_MEMBER_NO_MATCH) {
+ buckets[prim].sigs[i] = sig;
+ buckets[prim].sets[i] = set_id;
+ return 0;
+ }
+ }
+ /* If prim failed, we need to access second bucket */
+ for (i = 0; i < RTE_MEMBER_BUCKET_ENTRIES; i++) {
+ if (buckets[sec].sets[i] == RTE_MEMBER_NO_MATCH) {
+ buckets[sec].sigs[i] = sig;
+ buckets[sec].sets[i] = set_id;
+ return 0;
+ }
+ }
+ return -1;
+}
+
+static inline int
+try_update(struct member_ht_bucket *buckets, uint32_t prim, uint32_t sec,
+ member_sig_t sig, member_set_t set_id,
+ enum rte_member_sig_compare_function cmp_fn)
+{
+ switch (cmp_fn) {
+#if defined(RTE_ARCH_X86) && defined(RTE_MACHINE_CPUFLAG_AVX2)
+ case RTE_MEMBER_COMPARE_AVX2:
+ if (update_entry_search_avx(prim, sig, buckets, set_id) ||
+ update_entry_search_avx(sec, sig, buckets,
+ set_id))
+ return 0;
+ break;
+#endif
+ default:
+ if (update_entry_search(prim, sig, buckets, set_id) ||
+ update_entry_search(sec, sig, buckets,
+ set_id))
+ return 0;
+ }
+ return -1;
+}
+
+static inline int
+evict_from_bucket(void)
+{
+ /* For now, we randomly pick one entry to evict */
+ return rte_rand() & (RTE_MEMBER_BUCKET_ENTRIES - 1);
+}
+
+/*
+ * This function is similar to the cuckoo hash make_space function in hash
+ * library
+ */
+static inline int
+make_space_bucket(const struct rte_member_setsum *ss, uint32_t bkt_idx,
+ unsigned int *nr_pushes)
+{
+ unsigned int i, j;
+ int ret;
+ struct member_ht_bucket *buckets = ss->table;
+ uint32_t next_bucket_idx;
+ struct member_ht_bucket *next_bkt[RTE_MEMBER_BUCKET_ENTRIES];
+ struct member_ht_bucket *bkt = &buckets[bkt_idx];
+ /* MSB is set to indicate if an entry has been already pushed */
+ member_set_t flag_mask = 1U << (sizeof(member_set_t) * 8 - 1);
+
+ /*
+ * Push existing item (search for bucket with space in
+ * alternative locations) to its alternative location
+ */
+ for (i = 0; i < RTE_MEMBER_BUCKET_ENTRIES; i++) {
+ /* Search for space in alternative locations */
+ next_bucket_idx = (bkt->sigs[i] ^ bkt_idx) & ss->bucket_mask;
+ next_bkt[i] = &buckets[next_bucket_idx];
+ for (j = 0; j < RTE_MEMBER_BUCKET_ENTRIES; j++) {
+ if (next_bkt[i]->sets[j] == RTE_MEMBER_NO_MATCH)
+ break;
+ }
+
+ if (j != RTE_MEMBER_BUCKET_ENTRIES)
+ break;
+ }
+
+ /* Alternative location has spare room (end of recursive function) */
+ if (i != RTE_MEMBER_BUCKET_ENTRIES) {
+ next_bkt[i]->sigs[j] = bkt->sigs[i];
+ next_bkt[i]->sets[j] = bkt->sets[i];
+ return i;
+ }
+
+ /* Pick entry that has not been pushed yet */
+ for (i = 0; i < RTE_MEMBER_BUCKET_ENTRIES; i++)
+ if ((bkt->sets[i] & flag_mask) == 0)
+ break;
+
+ /* All entries have been pushed, so entry cannot be added */
+ if (i == RTE_MEMBER_BUCKET_ENTRIES ||
+ ++(*nr_pushes) > RTE_MEMBER_MAX_PUSHES)
+ return -ENOSPC;
+
+ next_bucket_idx = (bkt->sigs[i] ^ bkt_idx) & ss->bucket_mask;
+ /* Set flag to indicate that this entry is going to be pushed */
+ bkt->sets[i] |= flag_mask;
+
+ /* Need room in alternative bucket to insert the pushed entry */
+ ret = make_space_bucket(ss, next_bucket_idx, nr_pushes);
+ /*
+ * After recursive function.
+ * Clear flags and insert the pushed entry
+ * in its alternative location if successful,
+ * or return error
+ */
+ bkt->sets[i] &= ~flag_mask;
+ if (ret >= 0) {
+ next_bkt[i]->sigs[ret] = bkt->sigs[i];
+ next_bkt[i]->sets[ret] = bkt->sets[i];
+ return i;
+ } else
+ return ret;
+}
+
+int
+rte_member_add_ht(const struct rte_member_setsum *ss,
+ const void *key, member_set_t set_id)
+{
+ int ret;
+ unsigned int nr_pushes = 0;
+ uint32_t prim_bucket, sec_bucket;
+ member_sig_t tmp_sig;
+ struct member_ht_bucket *buckets = ss->table;
+ member_set_t flag_mask = 1U << (sizeof(member_set_t) * 8 - 1);
+
+ if (set_id == RTE_MEMBER_NO_MATCH || (set_id & flag_mask) != 0)
+ return -EINVAL;
+
+ get_buckets_index(ss, key, &prim_bucket, &sec_bucket, &tmp_sig);
+
+ /*
+ * If it is cache based setsummary, we try overwriting (updating)
+ * existing entry with the same signature first. In cache mode, we allow
+ * false negatives and only cache the most recent keys.
+ *
+ * For non-cache mode, we do not update existing entry with the same
+ * signature. This is because if two keys with same signature update
+ * each other, false negative may happen, which is not the expected
+ * behavior for non-cache setsummary.
+ */
+ if (ss->cache) {
+ ret = try_update(buckets, prim_bucket, sec_bucket, tmp_sig,
+ set_id, ss->sig_cmp_fn);
+ if (ret != -1)
+ return ret;
+ }
+ /* If not full then insert into one slot */
+ ret = try_insert(buckets, prim_bucket, sec_bucket, tmp_sig, set_id);
+ if (ret != -1)
+ return ret;
+
+ /* Random pick prim or sec for recursive displacement */
+ uint32_t select_bucket = (tmp_sig && 1U) ? prim_bucket : sec_bucket;
+ if (ss->cache) {
+ ret = evict_from_bucket();
+ buckets[select_bucket].sigs[ret] = tmp_sig;
+ buckets[select_bucket].sets[ret] = set_id;
+ return 1;
+ }
+
+ ret = make_space_bucket(ss, select_bucket, &nr_pushes);
+ if (ret >= 0) {
+ buckets[select_bucket].sigs[ret] = tmp_sig;
+ buckets[select_bucket].sets[ret] = set_id;
+ ret = 1;
+ }
+
+ return ret;
+}
+
+void
+rte_member_free_ht(struct rte_member_setsum *ss)
+{
+ rte_free(ss->table);
+}
+
+int
+rte_member_delete_ht(const struct rte_member_setsum *ss, const void *key,
+ member_set_t set_id)
+{
+ int i;
+ uint32_t prim_bucket, sec_bucket;
+ member_sig_t tmp_sig;
+ struct member_ht_bucket *buckets = ss->table;
+
+ get_buckets_index(ss, key, &prim_bucket, &sec_bucket, &tmp_sig);
+
+ for (i = 0; i < RTE_MEMBER_BUCKET_ENTRIES; i++) {
+ if (tmp_sig == buckets[prim_bucket].sigs[i] &&
+ set_id == buckets[prim_bucket].sets[i]) {
+ buckets[prim_bucket].sets[i] = RTE_MEMBER_NO_MATCH;
+ return 0;
+ }
+ }
+
+ for (i = 0; i < RTE_MEMBER_BUCKET_ENTRIES; i++) {
+ if (tmp_sig == buckets[sec_bucket].sigs[i] &&
+ set_id == buckets[sec_bucket].sets[i]) {
+ buckets[sec_bucket].sets[i] = RTE_MEMBER_NO_MATCH;
+ return 0;
+ }
+ }
+ return -ENOENT;
+}
+
+void
+rte_member_reset_ht(const struct rte_member_setsum *ss)
+{
+ uint32_t i, j;
+ struct member_ht_bucket *buckets = ss->table;
+
+ for (i = 0; i < ss->bucket_cnt; i++) {
+ for (j = 0; j < RTE_MEMBER_BUCKET_ENTRIES; j++)
+ buckets[i].sets[j] = RTE_MEMBER_NO_MATCH;
+ }
+}
diff --git a/lib/librte_member/rte_member_ht.h b/lib/librte_member/rte_member_ht.h
new file mode 100644
index 00000000..3148a492
--- /dev/null
+++ b/lib/librte_member/rte_member_ht.h
@@ -0,0 +1,94 @@
+/*-
+ * 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.
+ */
+
+#ifndef _RTE_MEMBER_HT_H_
+#define _RTE_MEMBER_HT_H_
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/* Maximum number of pushes for cuckoo path in HT mode. */
+#define RTE_MEMBER_MAX_PUSHES 50
+
+typedef uint16_t member_sig_t; /* signature size is 16 bit */
+
+/* The bucket struct for ht setsum */
+struct member_ht_bucket {
+ member_sig_t sigs[RTE_MEMBER_BUCKET_ENTRIES]; /* 2-byte signature */
+ member_set_t sets[RTE_MEMBER_BUCKET_ENTRIES]; /* 2-byte set */
+} __rte_cache_aligned;
+
+int
+rte_member_create_ht(struct rte_member_setsum *ss,
+ const struct rte_member_parameters *params);
+
+int
+rte_member_lookup_ht(const struct rte_member_setsum *setsum,
+ const void *key, member_set_t *set_id);
+
+uint32_t
+rte_member_lookup_bulk_ht(const struct rte_member_setsum *setsum,
+ const void **keys, uint32_t num_keys,
+ member_set_t *set_ids);
+
+uint32_t
+rte_member_lookup_multi_ht(const struct rte_member_setsum *setsum,
+ const void *key, uint32_t match_per_key,
+ member_set_t *set_id);
+
+uint32_t
+rte_member_lookup_multi_bulk_ht(const struct rte_member_setsum *setsum,
+ const void **keys, uint32_t num_keys, uint32_t match_per_key,
+ uint32_t *match_count,
+ member_set_t *set_ids);
+
+int
+rte_member_add_ht(const struct rte_member_setsum *setsum,
+ const void *key, member_set_t set_id);
+
+void
+rte_member_free_ht(struct rte_member_setsum *setsum);
+
+int
+rte_member_delete_ht(const struct rte_member_setsum *ss, const void *key,
+ member_set_t set_id);
+
+void
+rte_member_reset_ht(const struct rte_member_setsum *setsum);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_MEMBER_HT_H_ */
diff --git a/lib/librte_member/rte_member_vbf.c b/lib/librte_member/rte_member_vbf.c
new file mode 100644
index 00000000..1a98ac84
--- /dev/null
+++ b/lib/librte_member/rte_member_vbf.c
@@ -0,0 +1,350 @@
+/*-
+ * 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 <math.h>
+#include <string.h>
+
+#include <rte_malloc.h>
+#include <rte_memory.h>
+#include <rte_errno.h>
+#include <rte_log.h>
+
+#include "rte_member.h"
+#include "rte_member_vbf.h"
+
+/*
+ * vBF currently implemented as a big array.
+ * The BFs have a vertical layout. Bits in same location of all bfs will stay
+ * in the same cache line.
+ * For example, if we have 32 bloom filters, we use a uint32_t array to
+ * represent all of them. array[0] represent the first location of all the
+ * bloom filters, array[1] represents the second location of all the
+ * bloom filters, etc. The advantage of this layout is to minimize the average
+ * number of memory accesses to test all bloom filters.
+ *
+ * Currently the implementation supports vBF containing 1,2,4,8,16,32 BFs.
+ */
+int
+rte_member_create_vbf(struct rte_member_setsum *ss,
+ const struct rte_member_parameters *params)
+{
+
+ if (params->num_set > RTE_MEMBER_MAX_BF ||
+ !rte_is_power_of_2(params->num_set) ||
+ params->num_keys == 0 ||
+ params->false_positive_rate == 0 ||
+ params->false_positive_rate > 1) {
+ rte_errno = EINVAL;
+ RTE_MEMBER_LOG(ERR, "Membership vBF create with invalid parameters\n");
+ return -EINVAL;
+ }
+
+ /* We assume expected keys evenly distribute to all BFs */
+ uint32_t num_keys_per_bf = 1 + (params->num_keys - 1) / ss->num_set;
+
+ /*
+ * Note that the false positive rate is for all BFs in the vBF
+ * such that the single BF's false positive rate needs to be
+ * calculated.
+ * Assume each BF's False positive rate is fp_one_bf. The total false
+ * positive rate is fp = 1-(1-fp_one_bf)^n.
+ * => fp_one_bf = 1 - (1-fp)^(1/n)
+ */
+
+ float fp_one_bf = 1 - pow((1 - params->false_positive_rate),
+ 1.0 / ss->num_set);
+
+ if (fp_one_bf == 0) {
+ rte_errno = EINVAL;
+ RTE_MEMBER_LOG(ERR, "Membership BF false positive rate is too small\n");
+ return -EINVAL;
+ }
+
+ uint32_t bits = ceil((num_keys_per_bf *
+ log(fp_one_bf)) /
+ log(1.0 / (pow(2.0, log(2.0)))));
+
+ /* We round to power of 2 for performance during lookup */
+ ss->bits = rte_align32pow2(bits);
+
+ ss->num_hashes = (uint32_t)(log(2.0) * bits / num_keys_per_bf);
+ ss->bit_mask = ss->bits - 1;
+
+ /*
+ * Since we round the bits to power of 2, the final false positive
+ * rate will probably not be same as the user specified. We log the
+ * new value as debug message.
+ */
+ float new_fp = pow((1 - pow((1 - 1.0 / ss->bits), num_keys_per_bf *
+ ss->num_hashes)), ss->num_hashes);
+ new_fp = 1 - pow((1 - new_fp), ss->num_set);
+
+ /*
+ * Reduce hash function count, until we approach the user specified
+ * false-positive rate. Otherwise it is too conservative
+ */
+ int tmp_num_hash = ss->num_hashes;
+
+ while (tmp_num_hash > 1) {
+ float tmp_fp = new_fp;
+
+ tmp_num_hash--;
+ new_fp = pow((1 - pow((1 - 1.0 / ss->bits), num_keys_per_bf *
+ tmp_num_hash)), tmp_num_hash);
+ new_fp = 1 - pow((1 - new_fp), ss->num_set);
+
+ if (new_fp > params->false_positive_rate) {
+ new_fp = tmp_fp;
+ tmp_num_hash++;
+ break;
+ }
+ }
+
+ ss->num_hashes = tmp_num_hash;
+
+ /*
+ * To avoid multiplication and division:
+ * mul_shift is used for multiplication shift during bit test
+ * div_shift is used for division shift, to be divided by number of bits
+ * represented by a uint32_t variable
+ */
+ ss->mul_shift = __builtin_ctzl(ss->num_set);
+ ss->div_shift = __builtin_ctzl(32 >> ss->mul_shift);
+
+ RTE_MEMBER_LOG(DEBUG, "vector bloom filter created, "
+ "each bloom filter expects %u keys, needs %u bits, %u hashes, "
+ "with false positive rate set as %.5f, "
+ "The new calculated vBF false positive rate is %.5f\n",
+ num_keys_per_bf, ss->bits, ss->num_hashes, fp_one_bf, new_fp);
+
+ ss->table = rte_zmalloc_socket(NULL, ss->num_set * (ss->bits >> 3),
+ RTE_CACHE_LINE_SIZE, ss->socket_id);
+ if (ss->table == NULL)
+ return -ENOMEM;
+
+ return 0;
+}
+
+static inline uint32_t
+test_bit(uint32_t bit_loc, const struct rte_member_setsum *ss)
+{
+ uint32_t *vbf = ss->table;
+ uint32_t n = ss->num_set;
+ uint32_t div_shift = ss->div_shift;
+ uint32_t mul_shift = ss->mul_shift;
+ /*
+ * a is how many bits in one BF are represented by one 32bit
+ * variable.
+ */
+ uint32_t a = 32 >> mul_shift;
+ /*
+ * x>>b is the divide, x & (a-1) is the mod, & (1<<n-1) to mask out bits
+ * we do not need
+ */
+ return (vbf[bit_loc >> div_shift] >>
+ ((bit_loc & (a - 1)) << mul_shift)) & ((1ULL << n) - 1);
+}
+
+static inline void
+set_bit(uint32_t bit_loc, const struct rte_member_setsum *ss, int32_t set)
+{
+ uint32_t *vbf = ss->table;
+ uint32_t div_shift = ss->div_shift;
+ uint32_t mul_shift = ss->mul_shift;
+ uint32_t a = 32 >> mul_shift;
+
+ vbf[bit_loc >> div_shift] |=
+ 1UL << (((bit_loc & (a - 1)) << mul_shift) + set - 1);
+}
+
+int
+rte_member_lookup_vbf(const struct rte_member_setsum *ss, const void *key,
+ member_set_t *set_id)
+{
+ uint32_t j;
+ uint32_t h1 = MEMBER_HASH_FUNC(key, ss->key_len, ss->prim_hash_seed);
+ uint32_t h2 = MEMBER_HASH_FUNC(&h1, sizeof(uint32_t),
+ ss->sec_hash_seed);
+ uint32_t mask = ~0;
+ uint32_t bit_loc;
+
+ for (j = 0; j < ss->num_hashes; j++) {
+ bit_loc = (h1 + j * h2) & ss->bit_mask;
+ mask &= test_bit(bit_loc, ss);
+ }
+
+ if (mask) {
+ *set_id = __builtin_ctzl(mask) + 1;
+ return 1;
+ }
+
+ *set_id = RTE_MEMBER_NO_MATCH;
+ return 0;
+}
+
+uint32_t
+rte_member_lookup_bulk_vbf(const struct rte_member_setsum *ss,
+ const void **keys, uint32_t num_keys, member_set_t *set_ids)
+{
+ uint32_t i, k;
+ uint32_t num_matches = 0;
+ uint32_t mask[RTE_MEMBER_LOOKUP_BULK_MAX];
+ uint32_t h1[RTE_MEMBER_LOOKUP_BULK_MAX], h2[RTE_MEMBER_LOOKUP_BULK_MAX];
+ uint32_t bit_loc;
+
+ for (i = 0; i < num_keys; i++)
+ h1[i] = MEMBER_HASH_FUNC(keys[i], ss->key_len,
+ ss->prim_hash_seed);
+ for (i = 0; i < num_keys; i++)
+ h2[i] = MEMBER_HASH_FUNC(&h1[i], sizeof(uint32_t),
+ ss->sec_hash_seed);
+ for (i = 0; i < num_keys; i++) {
+ mask[i] = ~0;
+ for (k = 0; k < ss->num_hashes; k++) {
+ bit_loc = (h1[i] + k * h2[i]) & ss->bit_mask;
+ mask[i] &= test_bit(bit_loc, ss);
+ }
+ }
+ for (i = 0; i < num_keys; i++) {
+ if (mask[i]) {
+ set_ids[i] = __builtin_ctzl(mask[i]) + 1;
+ num_matches++;
+ } else
+ set_ids[i] = RTE_MEMBER_NO_MATCH;
+ }
+ return num_matches;
+}
+
+uint32_t
+rte_member_lookup_multi_vbf(const struct rte_member_setsum *ss,
+ const void *key, uint32_t match_per_key,
+ member_set_t *set_id)
+{
+ uint32_t num_matches = 0;
+ uint32_t j;
+ uint32_t h1 = MEMBER_HASH_FUNC(key, ss->key_len, ss->prim_hash_seed);
+ uint32_t h2 = MEMBER_HASH_FUNC(&h1, sizeof(uint32_t),
+ ss->sec_hash_seed);
+ uint32_t mask = ~0;
+ uint32_t bit_loc;
+
+ for (j = 0; j < ss->num_hashes; j++) {
+ bit_loc = (h1 + j * h2) & ss->bit_mask;
+ mask &= test_bit(bit_loc, ss);
+ }
+ while (mask) {
+ uint32_t loc = __builtin_ctzl(mask);
+ set_id[num_matches] = loc + 1;
+ num_matches++;
+ if (num_matches >= match_per_key)
+ return num_matches;
+ mask &= ~(1UL << loc);
+ }
+ return num_matches;
+}
+
+uint32_t
+rte_member_lookup_multi_bulk_vbf(const struct rte_member_setsum *ss,
+ const void **keys, uint32_t num_keys, uint32_t match_per_key,
+ uint32_t *match_count,
+ member_set_t *set_ids)
+{
+ uint32_t i, k;
+ uint32_t num_matches = 0;
+ uint32_t match_cnt_t;
+ uint32_t mask[RTE_MEMBER_LOOKUP_BULK_MAX];
+ uint32_t h1[RTE_MEMBER_LOOKUP_BULK_MAX], h2[RTE_MEMBER_LOOKUP_BULK_MAX];
+ uint32_t bit_loc;
+
+ for (i = 0; i < num_keys; i++)
+ h1[i] = MEMBER_HASH_FUNC(keys[i], ss->key_len,
+ ss->prim_hash_seed);
+ for (i = 0; i < num_keys; i++)
+ h2[i] = MEMBER_HASH_FUNC(&h1[i], sizeof(uint32_t),
+ ss->sec_hash_seed);
+ for (i = 0; i < num_keys; i++) {
+ mask[i] = ~0;
+ for (k = 0; k < ss->num_hashes; k++) {
+ bit_loc = (h1[i] + k * h2[i]) & ss->bit_mask;
+ mask[i] &= test_bit(bit_loc, ss);
+ }
+ }
+ for (i = 0; i < num_keys; i++) {
+ match_cnt_t = 0;
+ while (mask[i]) {
+ uint32_t loc = __builtin_ctzl(mask[i]);
+ set_ids[i * match_per_key + match_cnt_t] = loc + 1;
+ match_cnt_t++;
+ if (match_cnt_t >= match_per_key)
+ break;
+ mask[i] &= ~(1UL << loc);
+ }
+ match_count[i] = match_cnt_t;
+ if (match_cnt_t != 0)
+ num_matches++;
+ }
+ return num_matches;
+}
+
+int
+rte_member_add_vbf(const struct rte_member_setsum *ss,
+ const void *key, member_set_t set_id)
+{
+ uint32_t i, h1, h2;
+ uint32_t bit_loc;
+
+ if (set_id > ss->num_set || set_id == RTE_MEMBER_NO_MATCH)
+ return -EINVAL;
+
+ h1 = MEMBER_HASH_FUNC(key, ss->key_len, ss->prim_hash_seed);
+ h2 = MEMBER_HASH_FUNC(&h1, sizeof(uint32_t), ss->sec_hash_seed);
+
+ for (i = 0; i < ss->num_hashes; i++) {
+ bit_loc = (h1 + i * h2) & ss->bit_mask;
+ set_bit(bit_loc, ss, set_id);
+ }
+ return 0;
+}
+
+void
+rte_member_free_vbf(struct rte_member_setsum *ss)
+{
+ rte_free(ss->table);
+}
+
+void
+rte_member_reset_vbf(const struct rte_member_setsum *ss)
+{
+ uint32_t *vbf = ss->table;
+ memset(vbf, 0, (ss->num_set * ss->bits) >> 3);
+}
diff --git a/lib/librte_member/rte_member_vbf.h b/lib/librte_member/rte_member_vbf.h
new file mode 100644
index 00000000..5bc158b9
--- /dev/null
+++ b/lib/librte_member/rte_member_vbf.h
@@ -0,0 +1,82 @@
+/*-
+ * 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.
+ */
+
+#ifndef _RTE_MEMBER_VBF_H_
+#define _RTE_MEMBER_VBF_H_
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/* Currently we only support up to 32 sets in vBF */
+#define RTE_MEMBER_MAX_BF 32
+
+int
+rte_member_create_vbf(struct rte_member_setsum *ss,
+ const struct rte_member_parameters *params);
+
+int
+rte_member_lookup_vbf(const struct rte_member_setsum *setsum,
+ const void *key, member_set_t *set_id);
+
+uint32_t
+rte_member_lookup_bulk_vbf(const struct rte_member_setsum *setsum,
+ const void **keys, uint32_t num_keys,
+ member_set_t *set_ids);
+
+uint32_t
+rte_member_lookup_multi_vbf(const struct rte_member_setsum *setsum,
+ const void *key, uint32_t match_per_key,
+ member_set_t *set_id);
+
+uint32_t
+rte_member_lookup_multi_bulk_vbf(const struct rte_member_setsum *setsum,
+ const void **keys, uint32_t num_keys, uint32_t match_per_key,
+ uint32_t *match_count,
+ member_set_t *set_ids);
+
+int
+rte_member_add_vbf(const struct rte_member_setsum *setsum,
+ const void *key, member_set_t set_id);
+
+void
+rte_member_free_vbf(struct rte_member_setsum *ss);
+
+void
+rte_member_reset_vbf(const struct rte_member_setsum *setsum);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_MEMBER_VBF_H_ */
diff --git a/lib/librte_member/rte_member_version.map b/lib/librte_member/rte_member_version.map
new file mode 100644
index 00000000..019e4cd9
--- /dev/null
+++ b/lib/librte_member/rte_member_version.map
@@ -0,0 +1,16 @@
+DPDK_17.11 {
+ global:
+
+ rte_member_add;
+ rte_member_create;
+ rte_member_delete;
+ rte_member_find_existing;
+ rte_member_free;
+ rte_member_lookup;
+ rte_member_lookup_bulk;
+ rte_member_lookup_multi;
+ rte_member_lookup_multi_bulk;
+ rte_member_reset;
+
+ local: *;
+};
diff --git a/lib/librte_member/rte_member_x86.h b/lib/librte_member/rte_member_x86.h
new file mode 100644
index 00000000..d29dd3fe
--- /dev/null
+++ b/lib/librte_member/rte_member_x86.h
@@ -0,0 +1,107 @@
+/*-
+ * 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.
+ */
+
+#ifndef _RTE_MEMBER_X86_H_
+#define _RTE_MEMBER_X86_H_
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <x86intrin.h>
+
+#if defined(RTE_MACHINE_CPUFLAG_AVX2)
+
+static inline int
+update_entry_search_avx(uint32_t bucket_id, member_sig_t tmp_sig,
+ struct member_ht_bucket *buckets,
+ member_set_t set_id)
+{
+ uint32_t hitmask = _mm256_movemask_epi8((__m256i)_mm256_cmpeq_epi16(
+ _mm256_load_si256((__m256i const *)buckets[bucket_id].sigs),
+ _mm256_set1_epi16(tmp_sig)));
+ if (hitmask) {
+ uint32_t hit_idx = __builtin_ctzl(hitmask) >> 1;
+ buckets[bucket_id].sets[hit_idx] = set_id;
+ return 1;
+ }
+ return 0;
+}
+
+static inline int
+search_bucket_single_avx(uint32_t bucket_id, member_sig_t tmp_sig,
+ struct member_ht_bucket *buckets,
+ member_set_t *set_id)
+{
+ uint32_t hitmask = _mm256_movemask_epi8((__m256i)_mm256_cmpeq_epi16(
+ _mm256_load_si256((__m256i const *)buckets[bucket_id].sigs),
+ _mm256_set1_epi16(tmp_sig)));
+ while (hitmask) {
+ uint32_t hit_idx = __builtin_ctzl(hitmask) >> 1;
+ if (buckets[bucket_id].sets[hit_idx] != RTE_MEMBER_NO_MATCH) {
+ *set_id = buckets[bucket_id].sets[hit_idx];
+ return 1;
+ }
+ hitmask &= ~(3U << ((hit_idx) << 1));
+ }
+ return 0;
+}
+
+static inline void
+search_bucket_multi_avx(uint32_t bucket_id, member_sig_t tmp_sig,
+ struct member_ht_bucket *buckets,
+ uint32_t *counter,
+ uint32_t match_per_key,
+ member_set_t *set_id)
+{
+ uint32_t hitmask = _mm256_movemask_epi8((__m256i)_mm256_cmpeq_epi16(
+ _mm256_load_si256((__m256i const *)buckets[bucket_id].sigs),
+ _mm256_set1_epi16(tmp_sig)));
+ while (hitmask) {
+ uint32_t hit_idx = __builtin_ctzl(hitmask) >> 1;
+ if (buckets[bucket_id].sets[hit_idx] != RTE_MEMBER_NO_MATCH) {
+ set_id[*counter] = buckets[bucket_id].sets[hit_idx];
+ (*counter)++;
+ if (*counter >= match_per_key)
+ return;
+ }
+ hitmask &= ~(3U << ((hit_idx) << 1));
+ }
+}
+#endif
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_MEMBER_X86_H_ */