From 8ea41438832a360aed2b7ba49fb75e310a2ff1dc Mon Sep 17 00:00:00 2001 From: Jasvinder Singh Date: Tue, 8 May 2018 15:17:18 +0100 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 Acked-by: Cristian Dumitrescu --- 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 diff --git a/lib/librte_table/Makefile b/lib/librte_table/Makefile index c4a9acb046..276d476ab6 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 39ffaf11a0..8b2f8413b1 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 7aad84fae6..6f55bd5706 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 dcb4fe9783..f024303330 100644 --- a/lib/librte_table/rte_table_hash_cuckoo.c +++ b/lib/librte_table/rte_table_hash_cuckoo.c @@ -10,8 +10,7 @@ #include #include -#include -#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 0000000000..d9d4312190 --- /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 + +#include + +#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 f844e9411b..59dcfddbf4 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 11e2402d07..c20147234e 100644 --- a/test/test-pipeline/pipeline_hash.c +++ b/test/test-pipeline/pipeline_hash.c @@ -15,6 +15,7 @@ #include #include #include +#include #include #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 f01652dcd3..a4b0ed65f9 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 a4d3ca0cdc..a66342cb65 100644 --- a/test/test/test_table.h +++ b/test/test/test_table.h @@ -6,6 +6,7 @@ #include #include #include +#include #include #include @@ -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 5e8e119a14..73ad0155d6 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 a7a69b857e..20df2e9225 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, -- 2.20.1