diff mbox

[dpdk-dev] table: add dedicated params struct for cuckoo hash

Message ID 20180508141718.18706-1-jasvinder.singh@intel.com (mailing list archive)
State Accepted, archived
Delegated to: Cristian Dumitrescu
Headers

Checks

Context Check Description
ci/checkpatch success coding style OK

Commit Message

Jasvinder Singh May 8, 2018, 2:17 p.m. UTC 
  Add dedicated parameter structure for cuckoo hash. The cuckoo hash from
librte_hash uses slightly different prototype for the hash function (no
key_mask parameter, 32-bit seed and return value) that require either
of the following approaches:
   1/ Function pointer conversion: gcc 8.1 warning [1], misleading [2]
   2/ Union within the parameter structure: pollutes a very generic API
      parameter structure with some implementation dependent detail
      (i.e. key mask not available for one of the available
      implementations)
   3/ Using opaque pointer for hash function: same issue from 2/
   4/ Different parameter structure: avoid issue from 2/; hopefully,
      it won't be long before librte_hash implements the key mask feature,
      so the generic API structure could be used.

[1] http://www.dpdk.org/ml/archives/dev/2018-April/094950.html
[2] http://www.dpdk.org/ml/archives/dev/2018-April/096250.html

Fixes: 5a80bf0ae613 ("table: add cuckoo hash")

Signed-off-by: Jasvinder Singh <jasvinder.singh@intel.com>
Acked-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
---
 lib/librte_table/Makefile                |  1 +
 lib/librte_table/meson.build             |  1 +
 lib/librte_table/rte_table_hash.h        |  3 --
 lib/librte_table/rte_table_hash_cuckoo.c | 11 +++---
 lib/librte_table/rte_table_hash_cuckoo.h | 57 ++++++++++++++++++++++++++++++++
 test/test-pipeline/main.h                |  4 +++
 test/test-pipeline/pipeline_hash.c       | 26 ++++++++++++++-
 test/test/test_table.c                   | 11 ++++++
 test/test/test_table.h                   |  6 ++++
 test/test/test_table_combined.c          |  4 +--
 test/test/test_table_tables.c            |  6 ++--
 11 files changed, 115 insertions(+), 15 deletions(-)
 create mode 100644 lib/librte_table/rte_table_hash_cuckoo.h

Comments

Cristian Dumitrescu May 8, 2018, 2:30 p.m. UTC | #1 
> -----Original Message-----
> From: Singh, Jasvinder
> Sent: Tuesday, May 8, 2018 3:17 PM
> To: dev@dpdk.org
> Cc: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> Subject: [PATCH] table: add dedicated params struct for cuckoo hash
> 
> Add dedicated parameter structure for cuckoo hash. The cuckoo hash from
> librte_hash uses slightly different prototype for the hash function (no
> key_mask parameter, 32-bit seed and return value) that require either
> of the following approaches:
>    1/ Function pointer conversion: gcc 8.1 warning [1], misleading [2]
>    2/ Union within the parameter structure: pollutes a very generic API
>       parameter structure with some implementation dependent detail
>       (i.e. key mask not available for one of the available
>       implementations)
>    3/ Using opaque pointer for hash function: same issue from 2/
>    4/ Different parameter structure: avoid issue from 2/; hopefully,
>       it won't be long before librte_hash implements the key mask feature,
>       so the generic API structure could be used.
> 
> [1] http://www.dpdk.org/ml/archives/dev/2018-April/094950.html
> [2] http://www.dpdk.org/ml/archives/dev/2018-April/096250.html
> 
> Fixes: 5a80bf0ae613 ("table: add cuckoo hash")
> 
> Signed-off-by: Jasvinder Singh <jasvinder.singh@intel.com>
> Acked-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
> ---

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

Applied to next-pipeline tree, thanks!
Andy Green May 8, 2018, 2:34 p.m. UTC | #2 
On May 8, 2018 10:17:18 PM GMT+08:00, Jasvinder Singh <jasvinder.singh@intel.com> wrote:
>Add dedicated parameter structure for cuckoo hash. The cuckoo hash from
>librte_hash uses slightly different prototype for the hash function (no
>key_mask parameter, 32-bit seed and return value) that require either
>of the following approaches:
>   1/ Function pointer conversion: gcc 8.1 warning [1], misleading [2]

As I wrote earlier this is broken on master currently... gcc 8.0.1, shipping on Fedora 28, is able to appreciate the existing cast is completely wrong and build errors out.  It's not a compiler version quirk so much as what is in master is actually broken.

>   2/ Union within the parameter structure: pollutes a very generic API
>      parameter structure with some implementation dependent detail
>      (i.e. key mask not available for one of the available
>      implementations)
>   3/ Using opaque pointer for hash function: same issue from 2/
>   4/ Different parameter structure: avoid issue from 2/; hopefully,
>   it won't be long before librte_hash implements the key mask feature,
>      so the generic API structure could be used.

Unifying them in a single function pointer type is obviously best since they're trying to do the same thing.

> static int
>-check_params_create_hash_cuckoo(struct rte_table_hash_params *params)
>+check_params_create_hash_cuckoo(struct rte_table_hash_cuckoo_params
>*params)

...

> {
> 	if (params == NULL) {
> 		RTE_LOG(ERR, TABLE, "NULL Input Parameters.\n");
>@@ -82,7 +81,7 @@ rte_table_hash_cuckoo_create(void *params,
> 			int socket_id,
> 			uint32_t entry_size)
> {
>-	struct rte_table_hash_params *p = params;
>+	struct rte_table_hash_cuckoo_params *p = params;

I think a proper solution will have to get rid of the void * params...

>-		.hash_func = (rte_hash_function)(p->f_hash),
>+		.hash_func = p->f_hash,

-Andy
Cristian Dumitrescu May 8, 2018, 4:46 p.m. UTC | #3 
From: Andy Green [mailto:andy@warmcat.com]

Sent: Tuesday, May 8, 2018 3:35 PM
To: dev@dpdk.org; Singh, Jasvinder <jasvinder.singh@intel.com>
Cc: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
Subject: Re: [dpdk-dev] [PATCH] table: add dedicated params struct for cuckoo hash



On May 8, 2018 10:17:18 PM GMT+08:00, Jasvinder Singh <jasvinder.singh@intel.com<mailto:jasvinder.singh@intel.com>> wrote:
>Add dedicated parameter structure for cuckoo hash. The cuckoo hash from

>librte_hash uses slightly different prototype for the hash function (no

>key_mask parameter, 32-bit seed and return value) that require either

>of the following approaches:

> 1/ Function pointer conversion: gcc 8.1 warning [1], misleading [2]


As I wrote earlier this is broken on master currently... gcc 8.0.1, shipping on Fedora 28, is able to appreciate the existing cast is completely wrong and build errors out. It's not a compiler version quirk so much as what is in master is actually broken.

[Cristian] Right, this is why we fixed it with this patch.


> 2/ Union within the parameter structure: pollutes a very generic API

> parameter structure with some implementation dependent detail

> (i.e. key mask not available for one of the available

> implementations)

> 3/ Using opaque pointer for hash function: same issue from 2/

> 4/ Different parameter structure: avoid issue from 2/; hopefully,

> it won't be long before librte_hash implements the key mask feature,

> so the generic API structure could be used.


Unifying them in a single function pointer type is obviously best since they're trying to do the same thing.

[Cristian] It is not a bad solution, but we decided to go for a dedicated params structure for cuckoo hash for the above reasons. It is functionally equivalent and it removes the root cause of the problem (i.e. no function pointer conversion required).


> static int

>-check_params_create_hash_cuckoo(struct rte_table_hash_params *params)

>+check_params_create_hash_cuckoo(struct rte_table_hash_cuckoo_params

>*params)


...

> {

> if (params == NULL) {

> RTE_LOG(ERR, TABLE, "NULL Input Parameters.\n");

>@@ -82,7 +81,7 @@ rte_table_hash_cuckoo_create(void *params,

> int socket_id,

> uint32_t entry_size)

> {

>- struct rte_table_hash_params *p = params;

>+ struct rte_table_hash_cuckoo_params *p = params;


I think a proper solution will have to get rid of the void * params...

[Cristian] You should probably go and spend some time understand how the rte_table.h API works.


>- .hash_func = (rte_hash_function)(p->f_hash),

>+ .hash_func = p->f_hash,


-Andy
diff mbox

Patch

diff --git a/lib/librte_table/Makefile b/lib/librte_table/Makefile
index c4a9acb..276d476 100644
--- a/lib/librte_table/Makefile
+++ b/lib/librte_table/Makefile
@@ -45,6 +45,7 @@  ifeq ($(CONFIG_RTE_LIBRTE_ACL),y)
 SYMLINK-$(CONFIG_RTE_LIBRTE_TABLE)-include += rte_table_acl.h
 endif
 SYMLINK-$(CONFIG_RTE_LIBRTE_TABLE)-include += rte_table_hash.h
+SYMLINK-$(CONFIG_RTE_LIBRTE_TABLE)-include += rte_table_hash_cuckoo.h
 SYMLINK-$(CONFIG_RTE_LIBRTE_TABLE)-include += rte_lru.h
 ifeq ($(CONFIG_RTE_ARCH_X86),y)
 SYMLINK-$(CONFIG_RTE_LIBRTE_TABLE)-include += rte_lru_x86.h
diff --git a/lib/librte_table/meson.build b/lib/librte_table/meson.build
index 39ffaf1..8b2f841 100644
--- a/lib/librte_table/meson.build
+++ b/lib/librte_table/meson.build
@@ -18,6 +18,7 @@  headers = files('rte_table.h',
 		'rte_table_lpm.h',
 		'rte_table_lpm_ipv6.h',
 		'rte_table_hash.h',
+		'rte_table_hash_cuckoo.h',
 		'rte_lru.h',
 		'rte_table_array.h',
 		'rte_table_stub.h')
diff --git a/lib/librte_table/rte_table_hash.h b/lib/librte_table/rte_table_hash.h
index 7aad84f..6f55bd5 100644
--- a/lib/librte_table/rte_table_hash.h
+++ b/lib/librte_table/rte_table_hash.h
@@ -99,9 +99,6 @@  extern struct rte_table_ops rte_table_hash_key8_lru_ops;
 extern struct rte_table_ops rte_table_hash_key16_lru_ops;
 extern struct rte_table_ops rte_table_hash_key32_lru_ops;
 
-/** Cuckoo hash table operations */
-extern struct rte_table_ops rte_table_hash_cuckoo_ops;
-
 #ifdef __cplusplus
 }
 #endif
diff --git a/lib/librte_table/rte_table_hash_cuckoo.c b/lib/librte_table/rte_table_hash_cuckoo.c
index dcb4fe9..f024303 100644
--- a/lib/librte_table/rte_table_hash_cuckoo.c
+++ b/lib/librte_table/rte_table_hash_cuckoo.c
@@ -10,8 +10,7 @@ 
 #include <rte_malloc.h>
 #include <rte_log.h>
 
-#include <rte_hash.h>
-#include "rte_table_hash.h"
+#include "rte_table_hash_cuckoo.h"
 
 #ifdef RTE_TABLE_STATS_COLLECT
 
@@ -35,7 +34,7 @@  struct rte_table_hash {
 	uint32_t key_size;
 	uint32_t entry_size;
 	uint32_t n_keys;
-	rte_table_hash_op_hash f_hash;
+	rte_hash_function f_hash;
 	uint32_t seed;
 	uint32_t key_offset;
 
@@ -47,7 +46,7 @@  struct rte_table_hash {
 };
 
 static int
-check_params_create_hash_cuckoo(struct rte_table_hash_params *params)
+check_params_create_hash_cuckoo(struct rte_table_hash_cuckoo_params *params)
 {
 	if (params == NULL) {
 		RTE_LOG(ERR, TABLE, "NULL Input Parameters.\n");
@@ -82,7 +81,7 @@  rte_table_hash_cuckoo_create(void *params,
 			int socket_id,
 			uint32_t entry_size)
 {
-	struct rte_table_hash_params *p = params;
+	struct rte_table_hash_cuckoo_params *p = params;
 	struct rte_hash *h_table;
 	struct rte_table_hash *t;
 	uint32_t total_size;
@@ -107,7 +106,7 @@  rte_table_hash_cuckoo_create(void *params,
 	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 = p->f_hash,
 		.hash_func_init_val = p->seed,
 		.socket_id = socket_id,
 		.name = p->name
diff --git a/lib/librte_table/rte_table_hash_cuckoo.h b/lib/librte_table/rte_table_hash_cuckoo.h
new file mode 100644
index 0000000..d9d4312
--- /dev/null
+++ b/lib/librte_table/rte_table_hash_cuckoo.h
@@ -0,0 +1,57 @@ 
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Intel Corporation
+ */
+
+#ifndef __INCLUDE_RTE_TABLE_HASH_CUCKOO_H__
+#define __INCLUDE_RTE_TABLE_HASH_CUCKOO_H__
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ * @file
+ * RTE Table Hash Cuckoo
+ *
+ ***/
+#include <stdint.h>
+
+#include <rte_hash.h>
+
+#include "rte_table.h"
+
+/** Hash table parameters */
+struct rte_table_hash_cuckoo_params {
+	/** Name */
+	const char *name;
+
+	/** Key size (number of bytes) */
+	uint32_t key_size;
+
+	/** Byte offset within packet meta-data where the key is located */
+	uint32_t key_offset;
+
+	/** Key mask */
+	uint8_t *key_mask;
+
+	/** Number of keys */
+	uint32_t n_keys;
+
+	/** Number of buckets */
+	uint32_t n_buckets;
+
+	/** Hash function */
+	rte_hash_function f_hash;
+
+	/** Seed value for the hash function */
+	uint32_t seed;
+};
+
+/** Cuckoo hash table operations */
+extern struct rte_table_ops rte_table_hash_cuckoo_ops;
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/test/test-pipeline/main.h b/test/test-pipeline/main.h
index f844e94..59dcfdd 100644
--- a/test/test-pipeline/main.h
+++ b/test/test-pipeline/main.h
@@ -107,6 +107,10 @@  uint64_t test_hash(void *key,
 	uint32_t key_size,
 	uint64_t seed);
 
+uint32_t test_hash_cuckoo(const void *key,
+	uint32_t key_size,
+	uint32_t seed);
+
 void app_main_loop_worker(void);
 void app_main_loop_worker_pipeline_stub(void);
 void app_main_loop_worker_pipeline_hash(void);
diff --git a/test/test-pipeline/pipeline_hash.c b/test/test-pipeline/pipeline_hash.c
index 11e2402..c201472 100644
--- a/test/test-pipeline/pipeline_hash.c
+++ b/test/test-pipeline/pipeline_hash.c
@@ -15,6 +15,7 @@ 
 #include <rte_port_ring.h>
 #include <rte_table_hash.h>
 #include <rte_hash.h>
+#include <rte_table_hash_cuckoo.h>
 #include <rte_pipeline.h>
 
 #include "main.h"
@@ -151,6 +152,17 @@  app_main_loop_worker_pipeline_hash(void) {
 		.seed = 0,
 	};
 
+	struct rte_table_hash_cuckoo_params table_hash_cuckoo_params = {
+		.name = "TABLE",
+		.key_size = key_size,
+		.key_offset = APP_METADATA_OFFSET(32),
+		.key_mask = NULL,
+		.n_keys = 1 << 24,
+		.n_buckets = 1 << 22,
+		.f_hash = test_hash_cuckoo,
+		.seed = 0,
+	};
+
 	/* Table configuration */
 	switch (app.pipeline_type) {
 	case e_APP_PIPELINE_HASH_KEY8_EXT:
@@ -298,7 +310,7 @@  app_main_loop_worker_pipeline_hash(void) {
 	{
 		struct rte_pipeline_table_params table_params = {
 			.ops = &rte_table_hash_cuckoo_ops,
-			.arg_create = &table_hash_params,
+			.arg_create = &table_hash_cuckoo_params,
 			.f_action_hit = NULL,
 			.f_action_miss = NULL,
 			.arg_ah = NULL,
@@ -379,6 +391,18 @@  uint64_t test_hash(
 	return signature;
 }
 
+uint32_t test_hash_cuckoo(
+	const void *key,
+	__attribute__((unused)) uint32_t key_size,
+	__attribute__((unused)) uint32_t seed)
+{
+	const uint32_t *k32 = key;
+	uint32_t ip_dst = rte_be_to_cpu_32(k32[0]);
+	uint32_t signature = (ip_dst >> 2) | ((ip_dst & 0x3) << 30);
+
+	return signature;
+}
+
 void
 app_main_loop_rx_metadata(void) {
 	uint32_t i, j;
diff --git a/test/test/test_table.c b/test/test/test_table.c
index f01652d..a4b0ed6 100644
--- a/test/test/test_table.c
+++ b/test/test/test_table.c
@@ -54,6 +54,17 @@  uint64_t pipeline_test_hash(void *key,
 	return signature;
 }
 
+uint32_t pipeline_test_hash_cuckoo(const void *key,
+		__attribute__((unused)) uint32_t key_size,
+		__attribute__((unused)) uint32_t seed)
+{
+	const uint32_t *k32 = key;
+	uint32_t ip_dst = rte_be_to_cpu_32(k32[0]);
+	uint32_t signature = ip_dst;
+
+	return signature;
+}
+
 static void
 app_free_resources(void) {
 	int i;
diff --git a/test/test/test_table.h b/test/test/test_table.h
index a4d3ca0..a66342c 100644
--- a/test/test/test_table.h
+++ b/test/test/test_table.h
@@ -6,6 +6,7 @@ 
 #include <rte_table_lpm.h>
 #include <rte_table_lpm_ipv6.h>
 #include <rte_table_hash.h>
+#include <rte_table_hash_cuckoo.h>
 #include <rte_table_array.h>
 #include <rte_pipeline.h>
 
@@ -106,6 +107,11 @@  uint64_t pipeline_test_hash(
 	__attribute__((unused)) uint32_t key_size,
 	__attribute__((unused)) uint64_t seed);
 
+uint32_t pipeline_test_hash_cuckoo(
+	const void *key,
+	__attribute__((unused)) uint32_t key_size,
+	__attribute__((unused)) uint32_t seed);
+
 /* Extern variables */
 extern struct rte_pipeline *p;
 extern struct rte_ring *rings_rx[N_PORTS];
diff --git a/test/test/test_table_combined.c b/test/test/test_table_combined.c
index 5e8e119..73ad015 100644
--- a/test/test/test_table_combined.c
+++ b/test/test/test_table_combined.c
@@ -778,14 +778,14 @@  test_table_hash_cuckoo_combined(void)
 	int status, i;
 
 	/* Traffic flow */
-	struct rte_table_hash_params cuckoo_params = {
+	struct rte_table_hash_cuckoo_params cuckoo_params = {
 		.name = "TABLE",
 		.key_size = 32,
 		.key_offset = APP_METADATA_OFFSET(32),
 		.key_mask = NULL,
 		.n_keys = 1 << 16,
 		.n_buckets = 1 << 16,
-		.f_hash = pipeline_test_hash,
+		.f_hash = pipeline_test_hash_cuckoo,
 		.seed = 0,
 	};
 
diff --git a/test/test/test_table_tables.c b/test/test/test_table_tables.c
index a7a69b8..20df2e9 100644
--- a/test/test/test_table_tables.c
+++ b/test/test/test_table_tables.c
@@ -903,14 +903,14 @@  test_table_hash_cuckoo(void)
 	uint32_t entry_size = 1;
 
 	/* Initialize params and create tables */
-	struct rte_table_hash_params cuckoo_params = {
+	struct rte_table_hash_cuckoo_params cuckoo_params = {
 		.name = "TABLE",
 		.key_size = 32,
 		.key_offset = APP_METADATA_OFFSET(32),
 		.key_mask = NULL,
 		.n_keys = 1 << 16,
 		.n_buckets = 1 << 16,
-		.f_hash = (rte_table_hash_op_hash)pipeline_test_hash,
+		.f_hash = pipeline_test_hash_cuckoo,
 		.seed = 0, 
 	};
 
@@ -941,7 +941,7 @@  test_table_hash_cuckoo(void)
 	if (table != NULL)
 		return -4;
 
-	cuckoo_params.f_hash = pipeline_test_hash;
+	cuckoo_params.f_hash = pipeline_test_hash_cuckoo;
 	cuckoo_params.name = NULL;
 
 	table = rte_table_hash_cuckoo_ops.f_create(&cuckoo_params,