[dpdk-dev] [PATCH 0/3] changes for enabling cuckoo hash into table library

[dpdk-dev] [PATCH 0/3] changes for enabling cuckoo hash into table library

[Sankar Chokkalingam]

From: Guruprasad Rao <guruprasadx.rao@intel.com>


Guruprasad Rao (3):
  lib/librte_table: enabling cuckoo hash into table library
  app/test-pipeline: added cuckoo hash for benchmarking
  app/test: adding cuckoo hash table for testing

 app/test-pipeline/config.c               |  20 +-
 app/test-pipeline/main.c                 |  12 +-
 app/test-pipeline/main.h                 |  12 +-
 app/test-pipeline/pipeline_hash.c        |  59 +++++
 app/test/test_table_combined.c           |  72 +++++-
 app/test/test_table_combined.h           |   3 +-
 app/test/test_table_tables.c             | 167 +++++++++++++-
 app/test/test_table_tables.h             |   3 +-
 lib/librte_table/Makefile                |   4 +-
 lib/librte_table/rte_table_hash.h        |  31 ++-
 lib/librte_table/rte_table_hash_cuckoo.c | 382 +++++++++++++++++++++++++++++++
 lib/librte_table/rte_table_version.map   |   7 +
 12 files changed, 763 insertions(+), 9 deletions(-)
 create mode 100644 lib/librte_table/rte_table_hash_cuckoo.c

-- 
2.5.0

[dpdk-dev] [PATCH 1/3] lib/librte_table: enabling cuckoo hash into table library

[Sankar Chokkalingam]

From: Guruprasad Rao <guruprasadx.rao@intel.com>

This patch provides table apis for dosig version of cuckoo hash
via  rte_table_hash_cuckoo_dosig_ops

The following apis are implemented for cuckoo hash
	rte_table_hash_cuckoo_create
	rte_table_hash_cuckoo_free
	rte_table_hash_cuckoo_entry_add
	rte_table_hash_cuckoo_entry_delete
	rte_table_hash_cuckoo_lookup_dosig
	rte_table_hash_cuckoo_stats_read

Signed-off-by: Sankar Chokkalingam <sankarx.chokkalingam@intel.com>
Signed-off-by: Guruprasad Rao <guruprasadx.rao@intel.com>
---
v2:
* fix coding style errors
* resolved review comments from <jasvinder.singh@intel.com>
* resolved clang compilation issue

v1:
* changes to lib/librte_table files to enableThis  cuckoo hash into
  table library

 lib/librte_table/Makefile                |   4 +-
 lib/librte_table/rte_table_hash.h        |  31 ++-
 lib/librte_table/rte_table_hash_cuckoo.c | 382 +++++++++++++++++++++++++++++++
 lib/librte_table/rte_table_version.map   |   7 +
 4 files changed, 422 insertions(+), 2 deletions(-)
 create mode 100644 lib/librte_table/rte_table_hash_cuckoo.c

diff --git a/lib/librte_table/Makefile b/lib/librte_table/Makefile
index 7a8a3f3..c82c769 100644
--- a/lib/librte_table/Makefile
+++ b/lib/librte_table/Makefile
@@ -1,6 +1,6 @@
 #   BSD LICENSE
 #
-#   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
+#   Copyright(c) 2010-2016 Intel Corporation. All rights reserved.
 #   All rights reserved.
 #
 #   Redistribution and use in source and binary forms, with or without
@@ -51,6 +51,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_TABLE) += rte_table_lpm_ipv6.c
 ifeq ($(CONFIG_RTE_LIBRTE_ACL),y)
 SRCS-$(CONFIG_RTE_LIBRTE_TABLE) += rte_table_acl.c
 endif
+SRCS-$(CONFIG_RTE_LIBRTE_TABLE) += rte_table_hash_cuckoo.c
 SRCS-$(CONFIG_RTE_LIBRTE_TABLE) += rte_table_hash_key8.c
 SRCS-$(CONFIG_RTE_LIBRTE_TABLE) += rte_table_hash_key16.c
 SRCS-$(CONFIG_RTE_LIBRTE_TABLE) += rte_table_hash_key32.c
@@ -80,5 +81,6 @@ DEPDIRS-$(CONFIG_RTE_LIBRTE_TABLE) += lib/librte_lpm
 ifeq ($(CONFIG_RTE_LIBRTE_ACL),y)
 DEPDIRS-$(CONFIG_RTE_LIBRTE_TABLE) += lib/librte_acl
 endif
+DEPDIRS-$(CONFIG_RTE_LIBRTE_TABLE) += lib/librte_hash
 
 include $(RTE_SDK)/mk/rte.lib.mk
diff --git a/lib/librte_table/rte_table_hash.h b/lib/librte_table/rte_table_hash.h
index 9d17516..57505a6 100644
--- a/lib/librte_table/rte_table_hash.h
+++ b/lib/librte_table/rte_table_hash.h
@@ -1,7 +1,7 @@
 /*-
  *   BSD LICENSE
  *
- *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
+ *   Copyright(c) 2010-2016 Intel Corporation. All rights reserved.
  *   All rights reserved.
  *
  *   Redistribution and use in source and binary forms, with or without
@@ -363,6 +363,35 @@ struct rte_table_hash_key32_ext_params {
 /** Extendible bucket hash table operations */
 extern struct rte_table_ops rte_table_hash_key32_ext_ops;
 
+/** Cuckoo hash table parameters */
+struct rte_table_hash_cuckoo_params {
+    /** Key size (number of bytes */
+		uint32_t key_size;
+
+	/** Maximum number of hash table entries */
+	uint32_t n_keys;
+
+	/** Hash function used to calculate hash */
+	rte_table_hash_op_hash f_hash;
+
+	/** Seed value or Init value used by f_hash */
+	uint32_t seed;
+
+	/** Byte offset within packet meta-data where the 4-byte key signature
+	is located. Valid for pre-computed key signature tables, ignored for
+	do-sig tables. */
+	uint32_t signature_offset;
+
+	/** Byte offset within packet meta-data where the key is located */
+	uint32_t key_offset;
+
+	/** Hash table name */
+	const char *name;
+};
+
+/** Cuckoo hash table operations */
+extern struct rte_table_ops rte_table_hash_cuckoo_dosig_ops;
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/lib/librte_table/rte_table_hash_cuckoo.c b/lib/librte_table/rte_table_hash_cuckoo.c
new file mode 100644
index 0000000..ff7baee
--- /dev/null
+++ b/lib/librte_table/rte_table_hash_cuckoo.c
@@ -0,0 +1,382 @@
+/*-
+ *	 BSD LICENSE
+ *
+ *	 Copyright(c) 2016 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 <stdio.h>
+
+#include <rte_common.h>
+#include <rte_mbuf.h>
+#include <rte_memory.h>
+#include <rte_malloc.h>
+#include <rte_log.h>
+
+#include <rte_hash.h>
+#include "rte_table_hash.h"
+
+#ifdef RTE_TABLE_STATS_COLLECT
+
+#define RTE_TABLE_HASH_CUCKOO_STATS_PKTS_IN_ADD(table, val) \
+	(table->stats.n_pkts_in += val)
+#define RTE_TABLE_HASH_CUCKOO_STATS_PKTS_LOOKUP_MISS(table, val) \
+	(table->stats.n_pkts_lookup_miss += val)
+
+#else
+
+#define RTE_TABLE_HASH_CUCKOO_STATS_PKTS_IN_ADD(table, val)
+#define RTE_TABLE_HASH_CUCKOO_STATS_PKTS_LOOKUP_MISS(table, val)
+
+#endif
+
+
+struct rte_table_hash {
+	struct rte_table_stats stats;
+
+	/* Input parameters */
+	uint32_t key_size;
+	uint32_t entry_size;
+	uint32_t n_keys;
+	rte_table_hash_op_hash f_hash;
+	uint32_t seed;
+	uint32_t signature_offset;
+	uint32_t key_offset;
+	const char *name;
+
+	/* cuckoo hash table object */
+	struct rte_hash *h_table;
+
+	/* Lookup table */
+	uint8_t memory[0] __rte_cache_aligned; };
+
+static int
+check_params_create_hash_cuckoo(const struct
+rte_table_hash_cuckoo_params *params) {
+	/* Check for valid parameters */
+	if (params == NULL) {
+		RTE_LOG(ERR, TABLE, "NULL Input Parameters.\n");
+		return -EINVAL;
+	}
+
+	if (params->key_size == 0) {
+		RTE_LOG(ERR, TABLE, "Invalid key_size.\n");
+		return -EINVAL;
+	}
+
+	if (params->n_keys == 0) {
+		RTE_LOG(ERR, TABLE, "Invalid n_keys.\n");
+		return -EINVAL;
+	}
+
+	if (params->f_hash == NULL) {
+		RTE_LOG(ERR, TABLE, "f_hash is NULL.\n");
+		return -EINVAL;
+	}
+
+	if (params->name == NULL) {
+		RTE_LOG(ERR, TABLE, "Table name is NULL.\n");
+		return -EINVAL;
+	}
+
+	return 0;
+}
+
+static void *
+rte_table_hash_cuckoo_create(void *params,
+			int socket_id,
+			uint32_t entry_size)
+{
+	struct rte_hash *rte_hash_handle;
+	struct rte_table_hash *t;
+	uint32_t total_size, total_cl_size;
+
+	/* Check input parameters */
+	struct rte_table_hash_cuckoo_params *p =
+		(struct rte_table_hash_cuckoo_params *) params;
+
+	if (check_params_create_hash_cuckoo(params))
+		return NULL;
+
+	/* Memory allocation */
+	total_cl_size =
+		(sizeof(struct rte_table_hash) +
+		 RTE_CACHE_LINE_SIZE) / RTE_CACHE_LINE_SIZE;
+	total_cl_size += (p->n_keys * entry_size +
+			RTE_CACHE_LINE_SIZE) / RTE_CACHE_LINE_SIZE;
+	total_size = total_cl_size * RTE_CACHE_LINE_SIZE;
+
+	t = rte_zmalloc_socket("TABLE",
+			total_size,
+			RTE_CACHE_LINE_SIZE,
+			socket_id);
+	if (t == NULL) {
+		RTE_LOG(ERR, TABLE,
+			"%s: Cannot allocate %u bytes for Cuckoo hash table\n",
+			__func__,
+			(uint32_t)sizeof(struct rte_table_hash));
+		return NULL;
+	}
+
+	/* Create cuckoo hash table */
+	struct rte_hash_parameters hash_cuckoo_params = {
+		.entries = p->n_keys,
+		.key_len = p->key_size,
+		.hash_func = (rte_hash_function)(p->f_hash),
+		.hash_func_init_val = p->seed,
+		.socket_id = socket_id,
+		.name = p->name
+	};
+
+	rte_hash_handle = rte_hash_find_existing(p->name);
+	if (rte_hash_handle == NULL) {
+		rte_hash_handle = rte_hash_create(&hash_cuckoo_params);
+		if (NULL == rte_hash_handle) {
+			RTE_LOG(ERR, TABLE,
+				"%s: failed to create cuckoo hash table. keysize: %u",
+				__func__, hash_cuckoo_params.key_len);
+			rte_free(t);
+			return NULL;
+		}
+	}
+
+	/* initialize the cuckoo hash parameters */
+	t->key_size = p->key_size;
+	t->entry_size = entry_size;
+	t->n_keys = p->n_keys;
+	t->f_hash = p->f_hash;
+	t->seed = p->seed;
+	t->signature_offset = p->signature_offset;
+	t->key_offset = p->key_offset;
+	t->name = p->name;
+	t->h_table = rte_hash_handle;
+
+	RTE_LOG(INFO, TABLE,
+		"%s: Cuckoo Hash table memory footprint is %u bytes\n",
+		__func__, total_size);
+	return t;
+}
+
+static int
+rte_table_hash_cuckoo_free(void *table) {
+	if (table == NULL) {
+		RTE_LOG(ERR, TABLE, "%s: table parameter is NULL\n", __func__);
+		return -EINVAL;
+	}
+
+	struct rte_table_hash *t = (struct rte_table_hash *)table;
+
+	rte_hash_free(t->h_table);
+	rte_free(t);
+
+	return 0;
+}
+
+static int
+rte_table_hash_cuckoo_entry_add(void *table, void *key, void *entry,
+		int *key_found, void **entry_ptr) {
+	int pos = 0;
+
+	if (table == NULL) {
+		RTE_LOG(ERR, TABLE, "%s: table parameter is NULL\n", __func__);
+		return -EINVAL;
+	}
+
+	if (key == NULL) {
+		RTE_LOG(ERR, TABLE, "%s: key parameter is NULL\n", __func__);
+		return -EINVAL;
+	}
+
+	if (entry == NULL) {
+		RTE_LOG(ERR, TABLE, "%s: entry parameter is NULL\n", __func__);
+		return -EINVAL;
+	}
+
+	struct rte_table_hash *t = (struct rte_table_hash *)table;
+
+	/*  Find Existing entries */
+	pos = rte_hash_lookup(t->h_table, key);
+	if (pos >= 0) {
+		uint8_t *existing_entry;
+
+		*key_found = 1;
+		existing_entry = &t->memory[pos * t->entry_size];
+		memcpy(existing_entry, entry, t->entry_size);
+		*entry_ptr = existing_entry;
+
+		return 0;
+} else if (pos == -ENOENT) {
+	/* Entry not found. Adding new entry */
+		uint8_t *new_entry;
+
+		pos = rte_hash_add_key(t->h_table, key);
+		if (pos < 0) {
+			RTE_LOG(ERR, TABLE,
+				"%s: Entry not added, status : %u\n",
+				__func__, pos);
+			return pos;
+		}
+
+		new_entry = &t->memory[pos * t->entry_size];
+		memcpy(new_entry, entry, t->entry_size);
+
+		*key_found = 0;
+		*entry_ptr = new_entry;
+		return 0;
+	}
+	return pos;
+}
+
+static int
+rte_table_hash_cuckoo_entry_delete(void *table, void *key,
+		int *key_found, __rte_unused void *entry) {
+	int pos = 0;
+
+	if (table == NULL) {
+		RTE_LOG(ERR, TABLE, "%s: table parameter is NULL\n", __func__);
+		return -EINVAL;
+	}
+
+	if (key == NULL) {
+		RTE_LOG(ERR, TABLE, "%s: key parameter is NULL\n", __func__);
+		return -EINVAL;
+	}
+
+	struct rte_table_hash *t = (struct rte_table_hash *)table;
+
+	pos = rte_hash_del_key(t->h_table, key);
+	if (pos >= 0) {
+		*key_found = 1;
+		uint8_t *entry_ptr = &t->memory[pos * t->entry_size];
+
+		if (entry)
+			memcpy(entry, entry_ptr, t->entry_size);
+
+		memset(&t->memory[pos * t->entry_size], 0, t->entry_size);
+	}
+
+	return pos;
+}
+
+
+static int
+rte_table_hash_cuckoo_lookup_dosig(void *table,
+	struct rte_mbuf **pkts,
+	uint64_t pkts_mask,
+	uint64_t *lookup_hit_mask,
+	void **entries)
+{
+	struct rte_table_hash *t = (struct rte_table_hash *)table;
+	uint64_t pkts_mask_out = 0;
+	uint32_t i;
+
+	__rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
+
+	RTE_TABLE_HASH_CUCKOO_STATS_PKTS_IN_ADD(t, n_pkts_in);
+
+	if ((pkts_mask & (pkts_mask + 1)) == 0) {
+		const uint8_t *keys[64];
+		int32_t positions[64], status;
+
+		/* Keys for bulk lookup */
+		for (i = 0; i < n_pkts_in; i++)
+			keys[i] = RTE_MBUF_METADATA_UINT8_PTR(pkts[i],
+					t->key_offset);
+
+		/* Bulk Lookup */
+		status = rte_hash_lookup_bulk(t->h_table,
+				(const void **) keys,
+				n_pkts_in,
+				positions);
+
+		if (status == 0) {
+			for (i = 0; i < n_pkts_in; i++) {
+				if (likely(positions[i] >= 0)) {
+					uint64_t pkt_mask = 1LLU << i;
+
+					entries[i] = &t->memory[positions[i]
+						* t->entry_size];
+					pkts_mask_out |= pkt_mask;
+				}
+			}
+		}
+	} else {
+		for (i = 0; i < (uint32_t)(RTE_PORT_IN_BURST_SIZE_MAX
+					- __builtin_clzll(pkts_mask)); i++) {
+			uint64_t pkt_mask = 1LLU << i;
+
+			if (pkt_mask & pkts_mask) {
+				struct rte_mbuf *pkt = pkts[i];
+				uint8_t *key = RTE_MBUF_METADATA_UINT8_PTR(pkt,
+						t->key_offset);
+				int pos;
+
+				pos = rte_hash_lookup(t->h_table, key);
+				if (likely(pos >= 0)) {
+					entries[i] = &t->memory[pos
+						* t->entry_size];
+					pkts_mask_out |= pkt_mask;
+				}
+			}
+		}
+	}
+
+	*lookup_hit_mask = pkts_mask_out;
+	RTE_TABLE_HASH_CUCKOO_STATS_PKTS_LOOKUP_MISS(t,
+			n_pkts_in - __builtin_popcountll(pkts_mask_out));
+
+	return 0;
+
+}
+
+static int
+rte_table_hash_cuckoo_stats_read(void *table, struct rte_table_stats *stats,
+	int clear)
+{
+	struct rte_table_hash *t = (struct rte_table_hash *) table;
+
+	if (stats != NULL)
+		memcpy(stats, &t->stats, sizeof(t->stats));
+
+	if (clear)
+		memset(&t->stats, 0, sizeof(t->stats));
+
+	return 0;
+}
+
+struct rte_table_ops rte_table_hash_cuckoo_dosig_ops = {
+	.f_create = rte_table_hash_cuckoo_create,
+	.f_free = rte_table_hash_cuckoo_free,
+	.f_add = rte_table_hash_cuckoo_entry_add,
+	.f_delete = rte_table_hash_cuckoo_entry_delete,
+	.f_add_bulk = NULL,
+	.f_delete_bulk = NULL,
+	.f_lookup = rte_table_hash_cuckoo_lookup_dosig,
+	.f_stats = rte_table_hash_cuckoo_stats_read,
+};
diff --git a/lib/librte_table/rte_table_version.map b/lib/librte_table/rte_table_version.map
index 459c2da..e1eaa27 100644
--- a/lib/librte_table/rte_table_version.map
+++ b/lib/librte_table/rte_table_version.map
@@ -28,4 +28,11 @@ DPDK_2.2 {
 	rte_table_hash_key16_ext_dosig_ops;
 	rte_table_hash_key16_lru_dosig_ops;
 
+};
+
+DPDK_16.07 {
+       global:
+
+       rte_table_hash_cuckoo_dosig_ops;
+
 } DPDK_2.0;
-- 
2.5.0

[dpdk-dev] [PATCH 2/3] app/test-pipeline: added cuckoo hash for benchmarking

[Sankar Chokkalingam]

From: Guruprasad Rao <guruprasadx.rao@intel.com>

This patch inclides cuckoo hash table into test-pipeline
This allows to benchmark the performance of the cuckoo hash table
The following key sizes are supported for cuckoo hash table
8, 16, 32, 48, 64, 80, 96, 112 and 128.

The test-pipeline can be run using the following command
say for key size 8
./app/testpipeline -c 0xe -n 4 -- -p 0xf --hash-cuckoo-8

Signed-off-by: Sankar Chokkalingam <sankarx.chokkalingam@intel.com>
Signed-off-by: Guruprasad Rao <guruprasadx.rao@intel.com>
---
v2:
* Fixed coding style errors

v1:
* changes to app/test-pipeline files to include cuckoo hash table
  test-pipeline

 app/test-pipeline/config.c        | 20 ++++++++++++-
 app/test-pipeline/main.c          | 12 +++++++-
 app/test-pipeline/main.h          | 12 +++++++-
 app/test-pipeline/pipeline_hash.c | 59 +++++++++++++++++++++++++++++++++++++++
 4 files changed, 100 insertions(+), 3 deletions(-)

diff --git a/app/test-pipeline/config.c b/app/test-pipeline/config.c
index c7bc937..dd80ed6 100644
--- a/app/test-pipeline/config.c
+++ b/app/test-pipeline/config.c
@@ -1,7 +1,7 @@
 /*-
  *   BSD LICENSE
  *
- *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
+ *   Copyright(c) 2010-2016 Intel Corporation. All rights reserved.
  *   All rights reserved.
  *
  *   Redistribution and use in source and binary forms, with or without
@@ -139,6 +139,15 @@ struct {
 	{"acl", e_APP_PIPELINE_ACL},
 	{"lpm", e_APP_PIPELINE_LPM},
 	{"lpm-ipv6", e_APP_PIPELINE_LPM_IPV6},
+	{"hash-cuckoo-8", e_APP_PIPELINE_HASH_CUCKOO_KEY8},
+	{"hash-cuckoo-16", e_APP_PIPELINE_HASH_CUCKOO_KEY16},
+	{"hash-cuckoo-32", e_APP_PIPELINE_HASH_CUCKOO_KEY32},
+	{"hash-cuckoo-48", e_APP_PIPELINE_HASH_CUCKOO_KEY48},
+	{"hash-cuckoo-64", e_APP_PIPELINE_HASH_CUCKOO_KEY64},
+	{"hash-cuckoo-80", e_APP_PIPELINE_HASH_CUCKOO_KEY80},
+	{"hash-cuckoo-96", e_APP_PIPELINE_HASH_CUCKOO_KEY96},
+	{"hash-cuckoo-112", e_APP_PIPELINE_HASH_CUCKOO_KEY112},
+	{"hash-cuckoo-128", e_APP_PIPELINE_HASH_CUCKOO_KEY128},
 };
 
 int
@@ -166,6 +175,15 @@ app_parse_args(int argc, char **argv)
 		{"acl", 0, 0, 0},
 		{"lpm", 0, 0, 0},
 		{"lpm-ipv6", 0, 0, 0},
+		{"hash-cuckoo-8", 0, 0, 0},
+		{"hash-cuckoo-16", 0, 0, 0},
+		{"hash-cuckoo-32", 0, 0, 0},
+		{"hash-cuckoo-48", 0, 0, 0},
+		{"hash-cuckoo-64", 0, 0, 0},
+		{"hash-cuckoo-80", 0, 0, 0},
+		{"hash-cuckoo-96", 0, 0, 0},
+		{"hash-cuckoo-112", 0, 0, 0},
+		{"hash-cuckoo-128", 0, 0, 0},
 		{NULL, 0, 0, 0}
 	};
 	uint32_t lcores[3], n_lcores, lcore_id, pipeline_type_provided;
diff --git a/app/test-pipeline/main.c b/app/test-pipeline/main.c
index c57e4dd..71ab6ad 100644
--- a/app/test-pipeline/main.c
+++ b/app/test-pipeline/main.c
@@ -1,7 +1,7 @@
 /*-
  *   BSD LICENSE
  *
- *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
+ *   Copyright(c) 2010-2016 Intel Corporation. All rights reserved.
  *   All rights reserved.
  *
  *   Redistribution and use in source and binary forms, with or without
@@ -143,6 +143,16 @@ app_lcore_main_loop(__attribute__((unused)) void *arg)
 		case e_APP_PIPELINE_HASH_SPEC_KEY16_LRU:
 		case e_APP_PIPELINE_HASH_SPEC_KEY32_EXT:
 		case e_APP_PIPELINE_HASH_SPEC_KEY32_LRU:
+		/* cases for cuckoo hash table types */
+		case e_APP_PIPELINE_HASH_CUCKOO_KEY8:
+		case e_APP_PIPELINE_HASH_CUCKOO_KEY16:
+		case e_APP_PIPELINE_HASH_CUCKOO_KEY32:
+		case e_APP_PIPELINE_HASH_CUCKOO_KEY48:
+		case e_APP_PIPELINE_HASH_CUCKOO_KEY64:
+		case e_APP_PIPELINE_HASH_CUCKOO_KEY80:
+		case e_APP_PIPELINE_HASH_CUCKOO_KEY96:
+		case e_APP_PIPELINE_HASH_CUCKOO_KEY112:
+		case e_APP_PIPELINE_HASH_CUCKOO_KEY128:
 			app_main_loop_worker_pipeline_hash();
 			return 0;
 
diff --git a/app/test-pipeline/main.h b/app/test-pipeline/main.h
index 8dcd459..3685849 100644
--- a/app/test-pipeline/main.h
+++ b/app/test-pipeline/main.h
@@ -1,7 +1,7 @@
 /*-
  *   BSD LICENSE
  *
- *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
+ *   Copyright(c) 2010-2016 Intel Corporation. All rights reserved.
  *   All rights reserved.
  *
  *   Redistribution and use in source and binary forms, with or without
@@ -116,6 +116,16 @@ enum {
 	e_APP_PIPELINE_ACL,
 	e_APP_PIPELINE_LPM,
 	e_APP_PIPELINE_LPM_IPV6,
+
+	e_APP_PIPELINE_HASH_CUCKOO_KEY8,
+	e_APP_PIPELINE_HASH_CUCKOO_KEY16,
+	e_APP_PIPELINE_HASH_CUCKOO_KEY32,
+	e_APP_PIPELINE_HASH_CUCKOO_KEY48,
+	e_APP_PIPELINE_HASH_CUCKOO_KEY64,
+	e_APP_PIPELINE_HASH_CUCKOO_KEY80,
+	e_APP_PIPELINE_HASH_CUCKOO_KEY96,
+	e_APP_PIPELINE_HASH_CUCKOO_KEY112,
+	e_APP_PIPELINE_HASH_CUCKOO_KEY128,
 	e_APP_PIPELINES
 };
 
diff --git a/app/test-pipeline/pipeline_hash.c b/app/test-pipeline/pipeline_hash.c
index f8aac0d..8cdba49 100644
--- a/app/test-pipeline/pipeline_hash.c
+++ b/app/test-pipeline/pipeline_hash.c
@@ -43,6 +43,7 @@
 
 #include <rte_port_ring.h>
 #include <rte_table_hash.h>
+#include <rte_hash.h>
 #include <rte_pipeline.h>
 
 #include "main.h"
@@ -77,6 +78,25 @@ translate_options(uint32_t *special, uint32_t *ext, uint32_t *key_size)
 	case e_APP_PIPELINE_HASH_SPEC_KEY32_LRU:
 		*special = 1; *ext = 0; *key_size = 32; return;
 
+	case e_APP_PIPELINE_HASH_CUCKOO_KEY8:
+		*special = 0; *ext = 0; *key_size = 8; return;
+	case e_APP_PIPELINE_HASH_CUCKOO_KEY16:
+		*special = 0; *ext = 0; *key_size = 16; return;
+	case e_APP_PIPELINE_HASH_CUCKOO_KEY32:
+		*special = 0; *ext = 0; *key_size = 32; return;
+	case e_APP_PIPELINE_HASH_CUCKOO_KEY48:
+		*special = 0; *ext = 0; *key_size = 48; return;
+	case e_APP_PIPELINE_HASH_CUCKOO_KEY64:
+		*special = 0; *ext = 0; *key_size = 64; return;
+	case e_APP_PIPELINE_HASH_CUCKOO_KEY80:
+		*special = 0; *ext = 0; *key_size = 80; return;
+	case e_APP_PIPELINE_HASH_CUCKOO_KEY96:
+		*special = 0; *ext = 0; *key_size = 96; return;
+	case e_APP_PIPELINE_HASH_CUCKOO_KEY112:
+		*special = 0; *ext = 0; *key_size = 112; return;
+	case e_APP_PIPELINE_HASH_CUCKOO_KEY128:
+		*special = 0; *ext = 0; *key_size = 128; return;
+
 	default:
 		rte_panic("Invalid hash table type or key size\n");
 	}
@@ -360,6 +380,45 @@ app_main_loop_worker_pipeline_hash(void) {
 	}
 	break;
 
+	case e_APP_PIPELINE_HASH_CUCKOO_KEY8:
+	case e_APP_PIPELINE_HASH_CUCKOO_KEY16:
+	case e_APP_PIPELINE_HASH_CUCKOO_KEY32:
+	case e_APP_PIPELINE_HASH_CUCKOO_KEY48:
+	case e_APP_PIPELINE_HASH_CUCKOO_KEY64:
+	case e_APP_PIPELINE_HASH_CUCKOO_KEY80:
+	case e_APP_PIPELINE_HASH_CUCKOO_KEY96:
+	case e_APP_PIPELINE_HASH_CUCKOO_KEY112:
+	case e_APP_PIPELINE_HASH_CUCKOO_KEY128:
+	{
+		char hash_name[RTE_HASH_NAMESIZE];
+
+		snprintf(hash_name, sizeof(hash_name), "RTE_TH_CUCKOO_%d",
+			app.pipeline_type);
+
+		struct rte_table_hash_cuckoo_params table_hash_params = {
+			.key_size = key_size,
+			.n_keys = (1 << 24) + 1,
+			.f_hash = test_hash,
+			.seed = 0,
+			.signature_offset = APP_METADATA_OFFSET(0),
+			.key_offset = APP_METADATA_OFFSET(32),
+			.name = hash_name,
+		};
+
+		struct rte_pipeline_table_params table_params = {
+			.ops = &rte_table_hash_cuckoo_dosig_ops,
+			.arg_create = &table_hash_params,
+			.f_action_hit = NULL,
+			.f_action_miss = NULL,
+			.arg_ah = NULL,
+			.action_data_size = 0,
+		};
+
+		if (rte_pipeline_table_create(p, &table_params, &table_id))
+			rte_panic("Unable to configure the hash table\n");
+	}
+	break;
+
 	default:
 		rte_panic("Invalid hash table type or key size\n");
 	}
-- 
2.5.0

[dpdk-dev] [PATCH 3/3] app/test: adding cuckoo hash table for testing

[Sankar Chokkalingam]

From: Guruprasad Rao <guruprasadx.rao@intel.com>

This patch includes cuckoo hash table for testing all the APIs
The cuckoo hash is added for both test_table_tables and
test_table_combined cases.
The testing is completed and the results are OK.

Signed-off-by: Sankar Chokkalingam <sankarx.chokkalingam@intel.com>
Signed-off-by: Guruprasad Rao <guruprasadx.rao@intel.com>
---
v2:
* Fixed coding style errors

v1:
* changes to app/test/test_table files to test cuckoo hash table APIs

 app/test/test_table_combined.c |  72 +++++++++++++++++-
 app/test/test_table_combined.h |   3 +-
 app/test/test_table_tables.c   | 167 ++++++++++++++++++++++++++++++++++++++++-
 app/test/test_table_tables.h   |   3 +-
 4 files changed, 241 insertions(+), 4 deletions(-)

diff --git a/app/test/test_table_combined.c b/app/test/test_table_combined.c
index acb4f4d..518ece0 100644
--- a/app/test/test_table_combined.c
+++ b/app/test/test_table_combined.c
@@ -1,7 +1,7 @@
 /*-
  *   BSD LICENSE
  *
- *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
+ *   Copyright(c) 2010-2016 Intel Corporation. All rights reserved.
  *   All rights reserved.
  *
  *   Redistribution and use in source and binary forms, with or without
@@ -69,6 +69,7 @@ combined_table_test table_tests_combined[] = {
 	test_table_hash16ext,
 	test_table_hash32lru,
 	test_table_hash32ext,
+	test_table_hash_cuckoo_combined,
 };
 
 unsigned n_table_tests_combined = RTE_DIM(table_tests_combined);
@@ -786,3 +787,72 @@ test_table_hash32ext(void)
 
 	return 0;
 }
+
+int
+test_table_hash_cuckoo_combined(void)
+{
+	int status, i;
+
+	/* Traffic flow */
+	struct rte_table_hash_cuckoo_params cuckoo_params = {
+		.key_size = 32,
+		.n_keys = 1<<16,
+		.f_hash = pipeline_test_hash,
+		.seed = 0,
+		.signature_offset = APP_METADATA_OFFSET(0),
+		.key_offset = APP_METADATA_OFFSET(32),
+		.name = "CUCKOO_HASH",
+	};
+
+	uint8_t key_cuckoo[32];
+	uint32_t *kcuckoo = (uint32_t *) key_cuckoo;
+
+	memset(key_cuckoo, 0, sizeof(key_cuckoo));
+	kcuckoo[0] = 0xadadadad;
+
+	struct table_packets table_packets;
+
+	printf("--------------\n");
+	printf("RUNNING TEST - %s\n", __func__);
+	printf("--------------\n");
+	for (i = 0; i < 50; i++)
+		table_packets.hit_packet[i] = 0xadadadad;
+
+	for (i = 0; i < 50; i++)
+		table_packets.miss_packet[i] = 0xbdadadad;
+
+	table_packets.n_hit_packets = 50;
+	table_packets.n_miss_packets = 50;
+
+	status = test_table_type(&rte_table_hash_cuckoo_dosig_ops,
+		(void *)&cuckoo_params, (void *)key_cuckoo, &table_packets,
+		NULL, 0);
+	VERIFY(status, CHECK_TABLE_OK);
+
+	/* Invalid parameters */
+	cuckoo_params.key_size = 0;
+
+	status = test_table_type(&rte_table_hash_cuckoo_dosig_ops,
+		(void *)&cuckoo_params, (void *)key_cuckoo, &table_packets,
+		NULL, 0);
+	VERIFY(status, CHECK_TABLE_TABLE_CONFIG);
+
+	cuckoo_params.key_size = 32;
+	cuckoo_params.n_keys = 0;
+
+	status = test_table_type(&rte_table_hash_cuckoo_dosig_ops,
+		(void *)&cuckoo_params, (void *)key_cuckoo, &table_packets,
+		NULL, 0);
+	VERIFY(status, CHECK_TABLE_TABLE_CONFIG);
+
+	cuckoo_params.n_keys = 1<<16;
+	cuckoo_params.f_hash = NULL;
+
+	status = test_table_type(&rte_table_hash_cuckoo_dosig_ops,
+		(void *)&cuckoo_params, (void *)key_cuckoo, &table_packets,
+		NULL, 0);
+	VERIFY(status, CHECK_TABLE_TABLE_CONFIG);
+
+	return 0;
+}
+
diff --git a/app/test/test_table_combined.h b/app/test/test_table_combined.h
index f94f09f..e1619f9 100644
--- a/app/test/test_table_combined.h
+++ b/app/test/test_table_combined.h
@@ -1,7 +1,7 @@
 /*-
  *   BSD LICENSE
  *
- *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
+ *   Copyright(c) 2010-2016 Intel Corporation. All rights reserved.
  *   All rights reserved.
  *
  *   Redistribution and use in source and binary forms, with or without
@@ -47,6 +47,7 @@ int test_table_hash16ext(void);
 int test_table_hash32unoptimized(void);
 int test_table_hash32lru(void);
 int test_table_hash32ext(void);
+int test_table_hash_cuckoo_combined(void);
 
 /* Extern variables */
 typedef int (*combined_table_test)(void);
diff --git a/app/test/test_table_tables.c b/app/test/test_table_tables.c
index cbbbfc1..d835eb9 100644
--- a/app/test/test_table_tables.c
+++ b/app/test/test_table_tables.c
@@ -1,7 +1,7 @@
 /*-
  *   BSD LICENSE
  *
- *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
+ *   Copyright(c) 2010-2016 Intel Corporation. All rights reserved.
  *   All rights reserved.
  *
  *   Redistribution and use in source and binary forms, with or without
@@ -46,6 +46,7 @@ table_test table_tests[] = {
 	test_table_lpm_ipv6,
 	test_table_hash_lru,
 	test_table_hash_ext,
+	test_table_hash_cuckoo,
 };
 
 #define PREPARE_PACKET(mbuf, value) do {				\
@@ -942,3 +943,167 @@ test_table_hash_ext(void)
 
 	return 0;
 }
+
+
+int
+test_table_hash_cuckoo(void)
+{
+	int status, i;
+	uint64_t expected_mask = 0, result_mask;
+	struct rte_mbuf *mbufs[RTE_PORT_IN_BURST_SIZE_MAX];
+	void *table;
+	char *entries[RTE_PORT_IN_BURST_SIZE_MAX];
+	char entry;
+	void *entry_ptr;
+	int key_found;
+	uint32_t entry_size = 1;
+
+	/* Initialize params and create tables */
+	struct rte_table_hash_cuckoo_params cuckoo_params = {
+		.key_size = 32,
+		.n_keys = 1 << 24,
+		.f_hash = pipeline_test_hash,
+		.seed = 0,
+		.signature_offset = APP_METADATA_OFFSET(0),
+		.key_offset = APP_METADATA_OFFSET(32),
+		.name = "CUCKOO",
+	};
+
+	table = rte_table_hash_cuckoo_dosig_ops.f_create(NULL, 0, entry_size);
+	if (table != NULL)
+		return -1;
+
+	cuckoo_params.key_size = 0;
+
+	table = rte_table_hash_cuckoo_dosig_ops.f_create(&cuckoo_params,
+		0, entry_size);
+	if (table != NULL)
+		return -2;
+
+	cuckoo_params.key_size = 32;
+	cuckoo_params.n_keys = 0;
+
+	table = rte_table_hash_cuckoo_dosig_ops.f_create(&cuckoo_params,
+		0, entry_size);
+	if (table != NULL)
+		return -3;
+
+	cuckoo_params.n_keys = 1 << 24;
+	cuckoo_params.f_hash = NULL;
+
+	table = rte_table_hash_cuckoo_dosig_ops.f_create(&cuckoo_params,
+		0, entry_size);
+	if (table != NULL)
+		return -4;
+
+	cuckoo_params.f_hash = pipeline_test_hash;
+	cuckoo_params.name = NULL;
+
+	table = rte_table_hash_cuckoo_dosig_ops.f_create(&cuckoo_params,
+		0, entry_size);
+	if (table != NULL)
+		return -5;
+
+	cuckoo_params.name = "CUCKOO";
+
+	table = rte_table_hash_cuckoo_dosig_ops.f_create(&cuckoo_params,
+		0, entry_size);
+	if (table == NULL)
+		return -6;
+
+	/* Free */
+	status = rte_table_hash_cuckoo_dosig_ops.f_free(table);
+	if (status < 0)
+		return -7;
+
+	status = rte_table_hash_cuckoo_dosig_ops.f_free(NULL);
+	if (status == 0)
+		return -8;
+
+	/* Add */
+	uint8_t key_cuckoo[32];
+	uint32_t *kcuckoo = (uint32_t *) &key_cuckoo;
+
+	memset(key_cuckoo, 0, 32);
+	kcuckoo[0] = rte_be_to_cpu_32(0xadadadad);
+
+	table = rte_table_hash_cuckoo_dosig_ops.f_create(&cuckoo_params, 0, 1);
+	if (table == NULL)
+		return -9;
+
+	entry = 'A';
+	status = rte_table_hash_cuckoo_dosig_ops.f_add(NULL, &key_cuckoo,
+		&entry, &key_found, &entry_ptr);
+	if (status == 0)
+		return -10;
+
+	status = rte_table_hash_cuckoo_dosig_ops.f_add(table, NULL, &entry,
+		&key_found, &entry_ptr);
+	if (status == 0)
+		return -11;
+
+	status = rte_table_hash_cuckoo_dosig_ops.f_add(table, &key_cuckoo,
+		NULL, &key_found, &entry_ptr);
+	if (status == 0)
+		return -12;
+
+	status = rte_table_hash_cuckoo_dosig_ops.f_add(table, &key_cuckoo,
+		&entry, &key_found, &entry_ptr);
+	if (status != 0)
+		return -13;
+
+	status = rte_table_hash_cuckoo_dosig_ops.f_add(table, &key_cuckoo,
+		&entry, &key_found, &entry_ptr);
+	if (status != 0)
+		return -14;
+
+	/* Delete */
+	status = rte_table_hash_cuckoo_dosig_ops.f_delete(NULL, &key_cuckoo,
+		&key_found, NULL);
+	if (status == 0)
+		return -15;
+
+	status = rte_table_hash_cuckoo_dosig_ops.f_delete(table, NULL,
+		&key_found, NULL);
+	if (status == 0)
+		return -16;
+
+	status = rte_table_hash_cuckoo_dosig_ops.f_delete(table, &key_cuckoo,
+		&key_found, NULL);
+	if (status != 0)
+		return -17;
+
+	status = rte_table_hash_cuckoo_dosig_ops.f_delete(table, &key_cuckoo,
+		&key_found, NULL);
+	if (status != -ENOENT)
+		return -18;
+
+	/* Traffic flow */
+	entry = 'A';
+	status = rte_table_hash_cuckoo_dosig_ops.f_add(table, &key_cuckoo,
+		&entry, &key_found,
+		&entry_ptr);
+	if (status < 0)
+		return -19;
+
+	for (i = 0; i < RTE_PORT_IN_BURST_SIZE_MAX; i++)
+		if (i % 2 == 0) {
+			expected_mask |= (uint64_t)1 << i;
+			PREPARE_PACKET(mbufs[i], 0xadadadad);
+		} else
+			PREPARE_PACKET(mbufs[i], 0xadadadab);
+
+	rte_table_hash_cuckoo_dosig_ops.f_lookup(table, mbufs, -1,
+		&result_mask, (void **)entries);
+	if (result_mask != expected_mask)
+		return -20;
+
+	/* Free resources */
+	for (i = 0; i < RTE_PORT_IN_BURST_SIZE_MAX; i++)
+		rte_pktmbuf_free(mbufs[i]);
+
+	status = rte_table_hash_cuckoo_dosig_ops.f_free(table);
+
+	return 0;
+}
+
diff --git a/app/test/test_table_tables.h b/app/test/test_table_tables.h
index b368623..3531136 100644
--- a/app/test/test_table_tables.h
+++ b/app/test/test_table_tables.h
@@ -1,7 +1,7 @@
 /*-
  *   BSD LICENSE
  *
- *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
+ *   Copyright(c) 2010-2016 Intel Corporation. All rights reserved.
  *   All rights reserved.
  *
  *   Redistribution and use in source and binary forms, with or without
@@ -32,6 +32,7 @@
  */
 
 /* Test prototypes */
+int test_table_hash_cuckoo(void);
 int test_table_lpm(void);
 int test_table_lpm_ipv6(void);
 int test_table_array(void);
-- 
2.5.0

Re: [dpdk-dev] [PATCH 0/3] changes for enabling cuckoo hash into table library

[Dumitrescu, Cristian]

> -----Original Message-----
> From: Chokkalingam, SankarX
> Sent: Thursday, September 22, 2016 11:12 AM
> To: dev@dpdk.org
> Cc: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>; Singh, Jasvinder
> <jasvinder.singh@intel.com>; Chokkalingam, SankarX
> <sankarx.chokkalingam@intel.com>; Rao, GuruprasadX
> <guruprasadx.rao@intel.com>
> Subject: [PATCH 0/3] changes for enabling cuckoo hash into table library
> 
> From: Guruprasad Rao <guruprasadx.rao@intel.com>
> 
> 

Acked-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>

Re: [dpdk-dev] [PATCH 0/3] changes for enabling cuckoo hash into table library

[Thomas Monjalon]

> > From: Guruprasad Rao <guruprasadx.rao@intel.com>
> 
> Acked-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>

Applied, thanks