* [PATCH 0/6] pipeline: make the hash function configurable per table
@ 2022-08-18 11:44 Cristian Dumitrescu
2022-08-18 11:44 ` [PATCH 1/6] table: add hash function prototype Cristian Dumitrescu
` (6 more replies)
0 siblings, 7 replies; 17+ messages in thread
From: Cristian Dumitrescu @ 2022-08-18 11:44 UTC (permalink / raw)
To: dev
The exact match and learner tables use a hash function for the lookup
operation. This patch set makes the hash function configurable and
removes some limitations.
The hash function previously used by these table types had the
following limitations:
a) Not configurable: An internally hardcoded version was used;
b) Mask-based: This prevents using most of the available
hash functions, as they are not mask-based;
c) Key size limited to 64 bytes or less.
The new hash function is:
a) Configurable;
b) Not mask-based;
c) Not limited to key sizes to less than or equal to 64 bytes.
Also, since this flexibility has some performance cost, this patch set
also introduces key comparison functions specialized for each key size
value. Since the key size is fixed for each table, the key comparison
function can be selected at initialization as opposed to using a
generic function that can handle any key size. This strategy result in
a performance improvement for the table lookup operation of around 5%.
Depends-on: series-24117 ("pipeline: pipeline configuration and build improvements")
Cristian Dumitrescu (6):
table: add hash function prototype
table: add key comparison functions
table: configure the hash function for regular tables
pipeline: configure the hash function for regular tables
table: configure the hash function for learner tables
pipeline: configure the hash function for learner tables
lib/pipeline/rte_swx_ctl.c | 1 +
lib/pipeline/rte_swx_ctl.h | 3 +
lib/pipeline/rte_swx_pipeline.c | 22 ++
lib/pipeline/rte_swx_pipeline.h | 30 ++-
lib/pipeline/rte_swx_pipeline_internal.h | 2 +
lib/pipeline/rte_swx_pipeline_spec.c | 70 +++++-
lib/pipeline/rte_swx_pipeline_spec.h | 2 +
lib/table/meson.build | 2 +
lib/table/rte_swx_hash_func.h | 39 ++++
lib/table/rte_swx_keycmp.c | 166 ++++++++++++++
lib/table/rte_swx_keycmp.h | 49 +++++
lib/table/rte_swx_table.h | 8 +
lib/table/rte_swx_table_em.c | 266 ++++-------------------
lib/table/rte_swx_table_learner.c | 220 +++----------------
lib/table/rte_swx_table_learner.h | 6 +
15 files changed, 450 insertions(+), 436 deletions(-)
create mode 100644 lib/table/rte_swx_hash_func.h
create mode 100644 lib/table/rte_swx_keycmp.c
create mode 100644 lib/table/rte_swx_keycmp.h
--
2.34.1
^ permalink raw reply [flat|nested] 17+ messages in thread
* [PATCH 1/6] table: add hash function prototype
2022-08-18 11:44 [PATCH 0/6] pipeline: make the hash function configurable per table Cristian Dumitrescu
@ 2022-08-18 11:44 ` Cristian Dumitrescu
2022-08-18 11:44 ` [PATCH 2/6] table: add key comparison functions Cristian Dumitrescu
` (5 subsequent siblings)
6 siblings, 0 replies; 17+ messages in thread
From: Cristian Dumitrescu @ 2022-08-18 11:44 UTC (permalink / raw)
To: dev; +Cc: Kamalakannan R .
Add hash function prototype to be used by the exact match and the
learner table types. The hash function is not mask-based, so the table
key fields have to be contiguous in memory.
Signed-off-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
Signed-off-by: Kamalakannan R. <kamalakannan.r@intel.com>
---
lib/table/meson.build | 1 +
lib/table/rte_swx_hash_func.h | 39 +++++++++++++++++++++++++++++++++++
2 files changed, 40 insertions(+)
create mode 100644 lib/table/rte_swx_hash_func.h
diff --git a/lib/table/meson.build b/lib/table/meson.build
index d1f2f9dcf6..6d4272c4ef 100644
--- a/lib/table/meson.build
+++ b/lib/table/meson.build
@@ -26,6 +26,7 @@ sources = files(
)
headers = files(
'rte_lru.h',
+ 'rte_swx_hash_func.h',
'rte_swx_table.h',
'rte_swx_table_em.h',
'rte_swx_table_learner.h',
diff --git a/lib/table/rte_swx_hash_func.h b/lib/table/rte_swx_hash_func.h
new file mode 100644
index 0000000000..04f3d543e7
--- /dev/null
+++ b/lib/table/rte_swx_hash_func.h
@@ -0,0 +1,39 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2022 Intel Corporation
+ */
+#ifndef __INCLUDE_RTE_SWX_HASH_FUNC_H__
+#define __INCLUDE_RTE_SWX_HASH_FUNC_H__
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ * @file
+ * RTE SWX Hash Function
+ */
+
+#include <stdint.h>
+
+/**
+ * Hash function prototype
+ *
+ * @param[in] key
+ * Key to hash. Must be non-NULL.
+ * @param[in] length
+ * Key length in bytes.
+ * @param[in] seed
+ * Hash seed.
+ * @return
+ * Hash value.
+ */
+typedef uint32_t
+(*rte_swx_hash_func_t)(const void *key,
+ uint32_t length,
+ uint32_t seed);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
--
2.34.1
^ permalink raw reply [flat|nested] 17+ messages in thread
* [PATCH 2/6] table: add key comparison functions
2022-08-18 11:44 [PATCH 0/6] pipeline: make the hash function configurable per table Cristian Dumitrescu
2022-08-18 11:44 ` [PATCH 1/6] table: add hash function prototype Cristian Dumitrescu
@ 2022-08-18 11:44 ` Cristian Dumitrescu
2022-08-18 11:44 ` [PATCH 3/6] table: configure the hash function for regular tables Cristian Dumitrescu
` (4 subsequent siblings)
6 siblings, 0 replies; 17+ messages in thread
From: Cristian Dumitrescu @ 2022-08-18 11:44 UTC (permalink / raw)
To: dev; +Cc: Kamalakannan R .
Add key comparison functions to be used by the exact match and the
learner table types as part of the performance critical lookup
operation. Since the key size is fixed, it is possible to select a
specialized memory copy function as opposed to using the variable size
version, resulting in a performance improvement of around 5%.
Signed-off-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
Signed-off-by: Kamalakannan R. <kamalakannan.r@intel.com>
---
lib/table/meson.build | 1 +
lib/table/rte_swx_keycmp.c | 166 +++++++++++++++++++++++++++++++++++++
lib/table/rte_swx_keycmp.h | 49 +++++++++++
3 files changed, 216 insertions(+)
create mode 100644 lib/table/rte_swx_keycmp.c
create mode 100644 lib/table/rte_swx_keycmp.h
diff --git a/lib/table/meson.build b/lib/table/meson.build
index 6d4272c4ef..af749e4007 100644
--- a/lib/table/meson.build
+++ b/lib/table/meson.build
@@ -8,6 +8,7 @@ if is_windows
endif
sources = files(
+ 'rte_swx_keycmp.c',
'rte_swx_table_em.c',
'rte_swx_table_learner.c',
'rte_swx_table_selector.c',
diff --git a/lib/table/rte_swx_keycmp.c b/lib/table/rte_swx_keycmp.c
new file mode 100644
index 0000000000..ec65f5c822
--- /dev/null
+++ b/lib/table/rte_swx_keycmp.c
@@ -0,0 +1,166 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2022 Intel Corporation
+ */
+#include <rte_common.h>
+
+#include "rte_swx_keycmp.h"
+
+static uint32_t
+keycmp_generic(void *key1, void *key2, uint32_t key_size)
+{
+ return memcmp(key1, key2, key_size) ? 0 : 1;
+}
+
+#define KEYCMP(N) \
+static uint32_t \
+keycmp##N(void *key1, void *key2, uint32_t key_size __rte_unused) \
+{ \
+ return memcmp(key1, key2, N) ? 0 : 1; \
+}
+
+KEYCMP(1)
+KEYCMP(2)
+KEYCMP(3)
+KEYCMP(4)
+KEYCMP(5)
+KEYCMP(6)
+KEYCMP(7)
+KEYCMP(8)
+KEYCMP(9)
+
+KEYCMP(10)
+KEYCMP(11)
+KEYCMP(12)
+KEYCMP(13)
+KEYCMP(14)
+KEYCMP(15)
+KEYCMP(16)
+KEYCMP(17)
+KEYCMP(18)
+KEYCMP(19)
+
+KEYCMP(20)
+KEYCMP(21)
+KEYCMP(22)
+KEYCMP(23)
+KEYCMP(24)
+KEYCMP(25)
+KEYCMP(26)
+KEYCMP(27)
+KEYCMP(28)
+KEYCMP(29)
+
+KEYCMP(30)
+KEYCMP(31)
+KEYCMP(32)
+KEYCMP(33)
+KEYCMP(34)
+KEYCMP(35)
+KEYCMP(36)
+KEYCMP(37)
+KEYCMP(38)
+KEYCMP(39)
+
+KEYCMP(40)
+KEYCMP(41)
+KEYCMP(42)
+KEYCMP(43)
+KEYCMP(44)
+KEYCMP(45)
+KEYCMP(46)
+KEYCMP(47)
+KEYCMP(48)
+KEYCMP(49)
+
+KEYCMP(50)
+KEYCMP(51)
+KEYCMP(52)
+KEYCMP(53)
+KEYCMP(54)
+KEYCMP(55)
+KEYCMP(56)
+KEYCMP(57)
+KEYCMP(58)
+KEYCMP(59)
+
+KEYCMP(60)
+KEYCMP(61)
+KEYCMP(62)
+KEYCMP(63)
+KEYCMP(64)
+
+static rte_swx_keycmp_func_t keycmp_funcs[] = {
+ keycmp1,
+ keycmp2,
+ keycmp3,
+ keycmp4,
+ keycmp5,
+ keycmp6,
+ keycmp7,
+ keycmp8,
+ keycmp9,
+ keycmp10,
+ keycmp11,
+ keycmp12,
+ keycmp13,
+ keycmp14,
+ keycmp15,
+ keycmp16,
+ keycmp17,
+ keycmp18,
+ keycmp19,
+ keycmp20,
+ keycmp21,
+ keycmp22,
+ keycmp23,
+ keycmp24,
+ keycmp25,
+ keycmp26,
+ keycmp27,
+ keycmp28,
+ keycmp29,
+ keycmp30,
+ keycmp31,
+ keycmp32,
+ keycmp33,
+ keycmp34,
+ keycmp35,
+ keycmp36,
+ keycmp37,
+ keycmp38,
+ keycmp39,
+ keycmp40,
+ keycmp41,
+ keycmp42,
+ keycmp43,
+ keycmp44,
+ keycmp45,
+ keycmp46,
+ keycmp47,
+ keycmp48,
+ keycmp49,
+ keycmp50,
+ keycmp51,
+ keycmp52,
+ keycmp53,
+ keycmp54,
+ keycmp55,
+ keycmp56,
+ keycmp57,
+ keycmp58,
+ keycmp59,
+ keycmp60,
+ keycmp61,
+ keycmp62,
+ keycmp63,
+ keycmp64,
+};
+
+rte_swx_keycmp_func_t
+rte_swx_keycmp_func_get(uint32_t key_size)
+{
+ if (key_size && key_size <= 64)
+ return keycmp_funcs[key_size - 1];
+
+ return keycmp_generic;
+}
diff --git a/lib/table/rte_swx_keycmp.h b/lib/table/rte_swx_keycmp.h
new file mode 100644
index 0000000000..09fb1be869
--- /dev/null
+++ b/lib/table/rte_swx_keycmp.h
@@ -0,0 +1,49 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2022 Intel Corporation
+ */
+#ifndef __INCLUDE_RTE_SWX_KEYCMP_H__
+#define __INCLUDE_RTE_SWX_KEYCMP_H__
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ * @file
+ * RTE SWX Key Comparison Functions
+ */
+
+#include <stdint.h>
+#include <string.h>
+
+/**
+ * Key comparison function prototype
+ *
+ * @param[in] key1
+ * First key to compare. Must be non-NULL.
+ * @param[in] key2
+ * Second key to compare. Must be non-NULL.
+ * @param[in] key_size
+ * Key size in bytes.
+ * @return
+ * 0 when keys are different, 1 when keys are equal.
+ */
+typedef uint32_t
+(*rte_swx_keycmp_func_t)(void *key1, void *key2, uint32_t key_size);
+
+/**
+ * Key comparison function get
+ *
+ * @param[in] key_size
+ * Key size in bytes.
+ * @return
+ * Key comparison function for the given key size
+ */
+rte_swx_keycmp_func_t
+rte_swx_keycmp_func_get(uint32_t key_size);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
--
2.34.1
^ permalink raw reply [flat|nested] 17+ messages in thread
* [PATCH 3/6] table: configure the hash function for regular tables
2022-08-18 11:44 [PATCH 0/6] pipeline: make the hash function configurable per table Cristian Dumitrescu
2022-08-18 11:44 ` [PATCH 1/6] table: add hash function prototype Cristian Dumitrescu
2022-08-18 11:44 ` [PATCH 2/6] table: add key comparison functions Cristian Dumitrescu
@ 2022-08-18 11:44 ` Cristian Dumitrescu
2022-08-18 11:44 ` [PATCH 4/6] pipeline: " Cristian Dumitrescu
` (3 subsequent siblings)
6 siblings, 0 replies; 17+ messages in thread
From: Cristian Dumitrescu @ 2022-08-18 11:44 UTC (permalink / raw)
To: dev; +Cc: Kamalakannan R .
Make the hash function configurable. The internal hash function that
was not configurable, mask-based and limited to 64 bytes is removed.
Signed-off-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
Signed-off-by: Kamalakannan R. <kamalakannan.r@intel.com>
---
lib/table/rte_swx_table.h | 8 ++
lib/table/rte_swx_table_em.c | 266 ++++++-----------------------------
2 files changed, 49 insertions(+), 225 deletions(-)
diff --git a/lib/table/rte_swx_table.h b/lib/table/rte_swx_table.h
index c1383c2e57..4b8dc06798 100644
--- a/lib/table/rte_swx_table.h
+++ b/lib/table/rte_swx_table.h
@@ -19,6 +19,8 @@ extern "C" {
#include <rte_os.h>
+#include "rte_swx_hash_func.h"
+
/** Match type. */
enum rte_swx_table_match_type {
/** Wildcard Match (WM). */
@@ -58,6 +60,12 @@ struct rte_swx_table_params {
*/
uint32_t action_data_size;
+ /** Hash function. Ignored when not needed by the table implementation.
+ * When needed but set to NULL, the table implementation will select the
+ * hash function to use.
+ */
+ rte_swx_hash_func_t hash_func;
+
/** Maximum number of keys to be stored in the table together with their
* associated data.
*/
diff --git a/lib/table/rte_swx_table_em.c b/lib/table/rte_swx_table_em.c
index f783cfe282..568e76e249 100644
--- a/lib/table/rte_swx_table_em.c
+++ b/lib/table/rte_swx_table_em.c
@@ -7,7 +7,10 @@
#include <rte_common.h>
#include <rte_prefetch.h>
+#include <rte_jhash.h>
+#include <rte_hash_crc.h>
+#include "rte_swx_keycmp.h"
#include "rte_swx_table_em.h"
#define CHECK(condition, err_code) \
@@ -54,181 +57,10 @@ env_free(void *start, size_t size)
#endif
-#if defined(RTE_ARCH_X86_64)
-
-#include <x86intrin.h>
-
-#define crc32_u64(crc, v) _mm_crc32_u64(crc, v)
-
-#else
-
-static inline uint64_t
-crc32_u64_generic(uint64_t crc, uint64_t value)
-{
- int i;
-
- crc = (crc & 0xFFFFFFFFLLU) ^ value;
- for (i = 63; i >= 0; i--) {
- uint64_t mask;
-
- mask = -(crc & 1LLU);
- crc = (crc >> 1LLU) ^ (0x82F63B78LLU & mask);
- }
-
- return crc;
-}
-
-#define crc32_u64(crc, v) crc32_u64_generic(crc, v)
-
-#endif
-
-/* Key size needs to be one of: 8, 16, 32 or 64. */
-static inline uint32_t
-hash(void *key, void *key_mask, uint32_t key_size, uint32_t seed)
-{
- uint64_t *k = key;
- uint64_t *m = key_mask;
- uint64_t k0, k2, k5, crc0, crc1, crc2, crc3, crc4, crc5;
-
- switch (key_size) {
- case 8:
- crc0 = crc32_u64(seed, k[0] & m[0]);
- return crc0;
-
- case 16:
- k0 = k[0] & m[0];
-
- crc0 = crc32_u64(k0, seed);
- crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
-
- crc0 ^= crc1;
-
- return crc0;
-
- case 32:
- k0 = k[0] & m[0];
- k2 = k[2] & m[2];
-
- crc0 = crc32_u64(k0, seed);
- crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
-
- crc2 = crc32_u64(k2, k[3] & m[3]);
- crc3 = k2 >> 32;
-
- crc0 = crc32_u64(crc0, crc1);
- crc1 = crc32_u64(crc2, crc3);
-
- crc0 ^= crc1;
-
- return crc0;
-
- case 64:
- k0 = k[0] & m[0];
- k2 = k[2] & m[2];
- k5 = k[5] & m[5];
-
- crc0 = crc32_u64(k0, seed);
- crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
-
- crc2 = crc32_u64(k2, k[3] & m[3]);
- crc3 = crc32_u64(k2 >> 32, k[4] & m[4]);
-
- crc4 = crc32_u64(k5, k[6] & m[6]);
- crc5 = crc32_u64(k5 >> 32, k[7] & m[7]);
-
- crc0 = crc32_u64(crc0, (crc1 << 32) ^ crc2);
- crc1 = crc32_u64(crc3, (crc4 << 32) ^ crc5);
-
- crc0 ^= crc1;
-
- return crc0;
-
- default:
- crc0 = 0;
- return crc0;
- }
-}
-
-/* n_bytes needs to be a multiple of 8 bytes. */
static void
-keycpy(void *dst, void *src, void *src_mask, uint32_t n_bytes)
+keycpy(void *dst, void *src, uint32_t n_bytes)
{
- uint64_t *dst64 = dst, *src64 = src, *src_mask64 = src_mask;
- uint32_t i;
-
- for (i = 0; i < n_bytes / sizeof(uint64_t); i++)
- dst64[i] = src64[i] & src_mask64[i];
-}
-
-/*
- * Return: 0 = Keys are NOT equal; 1 = Keys are equal.
- */
-static inline uint32_t
-keycmp(void *a, void *b, void *b_mask, uint32_t n_bytes)
-{
- uint64_t *a64 = a, *b64 = b, *b_mask64 = b_mask;
-
- switch (n_bytes) {
- case 8: {
- uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
- uint32_t result = 1;
-
- if (xor0)
- result = 0;
- return result;
- }
-
- case 16: {
- uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
- uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]);
- uint64_t or = xor0 | xor1;
- uint32_t result = 1;
-
- if (or)
- result = 0;
- return result;
- }
-
- case 32: {
- uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
- uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]);
- uint64_t xor2 = a64[2] ^ (b64[2] & b_mask64[2]);
- uint64_t xor3 = a64[3] ^ (b64[3] & b_mask64[3]);
- uint64_t or = (xor0 | xor1) | (xor2 | xor3);
- uint32_t result = 1;
-
- if (or)
- result = 0;
- return result;
- }
-
- case 64: {
- uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
- uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]);
- uint64_t xor2 = a64[2] ^ (b64[2] & b_mask64[2]);
- uint64_t xor3 = a64[3] ^ (b64[3] & b_mask64[3]);
- uint64_t xor4 = a64[4] ^ (b64[4] & b_mask64[4]);
- uint64_t xor5 = a64[5] ^ (b64[5] & b_mask64[5]);
- uint64_t xor6 = a64[6] ^ (b64[6] & b_mask64[6]);
- uint64_t xor7 = a64[7] ^ (b64[7] & b_mask64[7]);
- uint64_t or = ((xor0 | xor1) | (xor2 | xor3)) |
- ((xor4 | xor5) | (xor6 | xor7));
- uint32_t result = 1;
-
- if (or)
- result = 0;
- return result;
- }
-
- default: {
- uint32_t i;
-
- for (i = 0; i < n_bytes / sizeof(uint64_t); i++)
- if (a64[i] != (b64[i] & b_mask64[i]))
- return 0;
- return 1;
- }
- }
+ memcpy(dst, src, n_bytes);
}
#define KEYS_PER_BUCKET 4
@@ -244,8 +76,6 @@ struct table {
struct rte_swx_table_params params;
/* Internal. */
- uint32_t key_size;
- uint32_t data_size;
uint32_t key_size_shl;
uint32_t data_size_shl;
uint32_t n_buckets;
@@ -253,9 +83,9 @@ struct table {
uint32_t key_stack_tos;
uint32_t bkt_ext_stack_tos;
uint64_t total_size;
+ rte_swx_keycmp_func_t keycmp_func;
/* Memory arrays. */
- uint8_t *key_mask;
struct bucket_extension *buckets;
struct bucket_extension *buckets_ext;
uint8_t *keys;
@@ -279,8 +109,7 @@ table_key_data(struct table *t, uint32_t key_id)
static inline int
bkt_is_empty(struct bucket_extension *bkt)
{
- return (!bkt->sig[0] && !bkt->sig[1] && !bkt->sig[2] && !bkt->sig[3]) ?
- 1 : 0;
+ return (!bkt->sig[0] && !bkt->sig[1] && !bkt->sig[2] && !bkt->sig[3]) ? 1 : 0;
}
/* Return:
@@ -311,7 +140,7 @@ bkt_keycmp(struct table *t,
/* Key comparison. */
bkt_key_id = bkt->key_id[bkt_pos];
bkt_key = table_key(t, bkt_key_id);
- return keycmp(bkt_key, input_key, t->key_mask, t->key_size);
+ return t->keycmp_func(bkt_key, input_key, t->params.key_size);
}
static inline void
@@ -331,15 +160,13 @@ bkt_key_install(struct table *t,
/* Key. */
bkt->key_id[bkt_pos] = bkt_key_id;
bkt_key = table_key(t, bkt_key_id);
- keycpy(bkt_key, input->key, t->key_mask, t->key_size);
+ keycpy(bkt_key, input->key, t->params.key_size);
/* Key data. */
bkt_data = table_key_data(t, bkt_key_id);
bkt_data[0] = input->action_id;
if (t->params.action_data_size && input->action_data)
- memcpy(&bkt_data[1],
- input->action_data,
- t->params.action_data_size);
+ memcpy(&bkt_data[1], input->action_data, t->params.action_data_size);
}
static inline void
@@ -358,9 +185,7 @@ bkt_key_data_update(struct table *t,
bkt_data = table_key_data(t, bkt_key_id);
bkt_data[0] = input->action_id;
if (t->params.action_data_size && input->action_data)
- memcpy(&bkt_data[1],
- input->action_data,
- t->params.action_data_size);
+ memcpy(&bkt_data[1], input->action_data, t->params.action_data_size);
}
#define CL RTE_CACHE_LINE_ROUNDUP
@@ -374,9 +199,9 @@ __table_create(struct table **table,
{
struct table *t;
uint8_t *memory;
- size_t table_meta_sz, key_mask_sz, bucket_sz, bucket_ext_sz, key_sz,
+ size_t table_meta_sz, bucket_sz, bucket_ext_sz, key_sz,
key_stack_sz, bkt_ext_stack_sz, data_sz, total_size;
- size_t key_mask_offset, bucket_offset, bucket_ext_offset, key_offset,
+ size_t bucket_offset, bucket_ext_offset, key_offset,
key_stack_offset, bkt_ext_stack_offset, data_offset;
uint32_t key_size, key_data_size, n_buckets, n_buckets_ext, i;
@@ -384,30 +209,34 @@ __table_create(struct table **table,
CHECK(params, EINVAL);
CHECK(params->match_type == RTE_SWX_TABLE_MATCH_EXACT, EINVAL);
CHECK(params->key_size, EINVAL);
- CHECK(params->key_size <= 64, EINVAL);
+
+ if (params->key_mask0) {
+ for (i = 0; i < params->key_size; i++)
+ if (params->key_mask0[i] != 0xFF)
+ break;
+
+ CHECK(i == params->key_size, EINVAL);
+ }
+
CHECK(params->n_keys_max, EINVAL);
/* Memory allocation. */
key_size = rte_align64pow2(params->key_size);
- if (key_size < 8)
- key_size = 8;
key_data_size = rte_align64pow2(params->action_data_size + 8);
- n_buckets = params->n_keys_max / KEYS_PER_BUCKET;
- n_buckets_ext = params->n_keys_max / KEYS_PER_BUCKET;
+ n_buckets = rte_align64pow2((params->n_keys_max + KEYS_PER_BUCKET - 1) / KEYS_PER_BUCKET);
+ n_buckets_ext = n_buckets;
table_meta_sz = CL(sizeof(struct table));
- key_mask_sz = CL(key_size);
bucket_sz = CL(n_buckets * sizeof(struct bucket_extension));
bucket_ext_sz = CL(n_buckets_ext * sizeof(struct bucket_extension));
key_sz = CL(params->n_keys_max * key_size);
key_stack_sz = CL(params->n_keys_max * sizeof(uint32_t));
bkt_ext_stack_sz = CL(n_buckets_ext * sizeof(uint32_t));
data_sz = CL(params->n_keys_max * key_data_size);
- total_size = table_meta_sz + key_mask_sz + bucket_sz + bucket_ext_sz +
+ total_size = table_meta_sz + bucket_sz + bucket_ext_sz +
key_sz + key_stack_sz + bkt_ext_stack_sz + data_sz;
- key_mask_offset = table_meta_sz;
- bucket_offset = key_mask_offset + key_mask_sz;
+ bucket_offset = table_meta_sz;
bucket_ext_offset = bucket_offset + bucket_sz;
key_offset = bucket_ext_offset + bucket_ext_sz;
key_stack_offset = key_offset + key_sz;
@@ -427,16 +256,17 @@ __table_create(struct table **table,
/* Initialization. */
t = (struct table *)memory;
memcpy(&t->params, params, sizeof(*params));
+ t->params.key_mask0 = NULL;
+ if (!params->hash_func)
+ t->params.hash_func = rte_hash_crc;
- t->key_size = key_size;
- t->data_size = key_data_size;
t->key_size_shl = __builtin_ctzl(key_size);
t->data_size_shl = __builtin_ctzl(key_data_size);
t->n_buckets = n_buckets;
t->n_buckets_ext = n_buckets_ext;
t->total_size = total_size;
+ t->keycmp_func = rte_swx_keycmp_func_get(params->key_size);
- t->key_mask = &memory[key_mask_offset];
t->buckets = (struct bucket_extension *)&memory[bucket_offset];
t->buckets_ext = (struct bucket_extension *)&memory[bucket_ext_offset];
t->keys = &memory[key_offset];
@@ -444,13 +274,6 @@ __table_create(struct table **table,
t->bkt_ext_stack = (uint32_t *)&memory[bkt_ext_stack_offset];
t->data = &memory[data_offset];
- t->params.key_mask0 = t->key_mask;
-
- if (!params->key_mask0)
- memset(t->key_mask, 0xFF, params->key_size);
- else
- memcpy(t->key_mask, params->key_mask0, params->key_size);
-
for (i = 0; i < t->params.n_keys_max; i++)
t->key_stack[i] = t->params.n_keys_max - 1 - i;
t->key_stack_tos = t->params.n_keys_max;
@@ -485,7 +308,7 @@ table_add(void *table, struct rte_swx_table_entry *entry)
CHECK(entry, EINVAL);
CHECK(entry->key, EINVAL);
- input_sig = hash(entry->key, t->key_mask, t->key_size, 0);
+ input_sig = t->params.hash_func(entry->key, t->params.key_size, 0);
bkt_id = input_sig & (t->n_buckets - 1);
bkt0 = &t->buckets[bkt_id];
input_sig = (input_sig >> 16) | 1;
@@ -506,10 +329,8 @@ table_add(void *table, struct rte_swx_table_entry *entry)
/* Allocate new key & install. */
CHECK(t->key_stack_tos, ENOSPC);
- new_bkt_key_id =
- t->key_stack[--t->key_stack_tos];
- bkt_key_install(t, bkt, entry, i,
- new_bkt_key_id, input_sig);
+ new_bkt_key_id = t->key_stack[--t->key_stack_tos];
+ bkt_key_install(t, bkt, entry, i, new_bkt_key_id, input_sig);
return 0;
}
@@ -526,8 +347,7 @@ table_add(void *table, struct rte_swx_table_entry *entry)
/* Allocate new key & install. */
new_bkt_key_id = t->key_stack[--t->key_stack_tos];
- bkt_key_install(t, new_bkt, entry, 0,
- new_bkt_key_id, input_sig);
+ bkt_key_install(t, new_bkt, entry, 0, new_bkt_key_id, input_sig);
return 0;
}
@@ -545,7 +365,7 @@ table_del(void *table, struct rte_swx_table_entry *entry)
CHECK(entry, EINVAL);
CHECK(entry->key, EINVAL);
- input_sig = hash(entry->key, t->key_mask, t->key_size, 0);
+ input_sig = t->params.hash_func(entry->key, t->params.key_size, 0);
bkt_id = input_sig & (t->n_buckets - 1);
bkt0 = &t->buckets[bkt_id];
input_sig = (input_sig >> 16) | 1;
@@ -556,17 +376,13 @@ table_del(void *table, struct rte_swx_table_entry *entry)
if (bkt_keycmp(t, bkt, entry->key, i, input_sig)) {
/* Key free. */
bkt->sig[i] = 0;
- t->key_stack[t->key_stack_tos++] =
- bkt->key_id[i];
+ t->key_stack[t->key_stack_tos++] = bkt->key_id[i];
- /* Bucket extension free if empty and not the
- * 1st in bucket.
- */
+ /* Bucket extension free if empty and not the 1st in bucket. */
if (bkt_prev && bkt_is_empty(bkt)) {
bkt_prev->next = bkt->next;
bkt_id = bkt - t->buckets_ext;
- t->bkt_ext_stack[t->bkt_ext_stack_tos++]
- = bkt_id;
+ t->bkt_ext_stack[t->bkt_ext_stack_tos++] = bkt_id;
}
return 0;
@@ -596,7 +412,7 @@ table_lookup_unoptimized(void *table,
input_key = &(*key)[t->params.key_offset];
- input_sig = hash(input_key, t->key_mask, t->key_size, 0);
+ input_sig = t->params.hash_func(input_key, t->params.key_size, 0);
bkt_id = input_sig & (t->n_buckets - 1);
bkt0 = &t->buckets[bkt_id];
input_sig = (input_sig >> 16) | 1;
@@ -695,7 +511,7 @@ table_lookup(void *table,
struct bucket_extension *bkt;
uint32_t input_sig, bkt_id;
- input_sig = hash(input_key, t->key_mask, t->key_size, 0);
+ input_sig = t->params.hash_func(input_key, t->params.key_size, 0);
bkt_id = input_sig & (t->n_buckets - 1);
bkt = &t->buckets[bkt_id];
rte_prefetch0(bkt);
@@ -756,7 +572,7 @@ table_lookup(void *table,
uint64_t *bkt_data = table_key_data(t, bkt_key_id);
uint32_t lkp_hit;
- lkp_hit = keycmp(bkt_key, input_key, t->key_mask, t->key_size);
+ lkp_hit = t->keycmp_func(bkt_key, input_key, t->params.key_size);
lkp_hit &= m->sig_match;
*action_id = bkt_data[0];
*action_data = (uint8_t *)&bkt_data[1];
--
2.34.1
^ permalink raw reply [flat|nested] 17+ messages in thread
* [PATCH 4/6] pipeline: configure the hash function for regular tables
2022-08-18 11:44 [PATCH 0/6] pipeline: make the hash function configurable per table Cristian Dumitrescu
` (2 preceding siblings ...)
2022-08-18 11:44 ` [PATCH 3/6] table: configure the hash function for regular tables Cristian Dumitrescu
@ 2022-08-18 11:44 ` Cristian Dumitrescu
2022-08-18 11:44 ` [PATCH 5/6] table: configure the hash function for learner tables Cristian Dumitrescu
` (2 subsequent siblings)
6 siblings, 0 replies; 17+ messages in thread
From: Cristian Dumitrescu @ 2022-08-18 11:44 UTC (permalink / raw)
To: dev; +Cc: Kamalakannan R .
Make the hash function configurable for the regular pipeline tables.
Signed-off-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
Signed-off-by: Kamalakannan R. <kamalakannan.r@intel.com>
---
lib/pipeline/rte_swx_ctl.c | 1 +
lib/pipeline/rte_swx_ctl.h | 3 ++
lib/pipeline/rte_swx_pipeline.c | 10 +++++++
lib/pipeline/rte_swx_pipeline.h | 24 +++++-----------
lib/pipeline/rte_swx_pipeline_internal.h | 1 +
lib/pipeline/rte_swx_pipeline_spec.c | 35 +++++++++++++++++++++++-
lib/pipeline/rte_swx_pipeline_spec.h | 1 +
7 files changed, 57 insertions(+), 18 deletions(-)
diff --git a/lib/pipeline/rte_swx_ctl.c b/lib/pipeline/rte_swx_ctl.c
index bdbcd8f50a..b6449f5f0c 100644
--- a/lib/pipeline/rte_swx_ctl.c
+++ b/lib/pipeline/rte_swx_ctl.c
@@ -272,6 +272,7 @@ table_params_get(struct rte_swx_ctl_pipeline *ctl, uint32_t table_id)
table->params.key_offset = key_offset;
table->params.key_mask0 = key_mask;
table->params.action_data_size = action_data_size;
+ table->params.hash_func = table->info.hash_func;
table->params.n_keys_max = table->info.size;
table->mf_first = first;
diff --git a/lib/pipeline/rte_swx_ctl.h b/lib/pipeline/rte_swx_ctl.h
index 63ee479e47..0694df557a 100644
--- a/lib/pipeline/rte_swx_ctl.h
+++ b/lib/pipeline/rte_swx_ctl.h
@@ -236,6 +236,9 @@ struct rte_swx_ctl_table_info {
*/
int default_action_is_const;
+ /** Hash function. */
+ rte_swx_hash_func_t hash_func;
+
/** Table size parameter. */
uint32_t size;
};
diff --git a/lib/pipeline/rte_swx_pipeline.c b/lib/pipeline/rte_swx_pipeline.c
index 2cac4caa95..e1227cbfcc 100644
--- a/lib/pipeline/rte_swx_pipeline.c
+++ b/lib/pipeline/rte_swx_pipeline.c
@@ -7986,6 +7986,7 @@ rte_swx_pipeline_table_config(struct rte_swx_pipeline *p,
struct table *t = NULL;
struct action *default_action;
struct header *header = NULL;
+ struct hash_func *hf = NULL;
uint32_t action_data_size_max = 0, i;
int status = 0;
@@ -8042,6 +8043,12 @@ rte_swx_pipeline_table_config(struct rte_swx_pipeline *p,
CHECK((default_action->st && params->default_action_args) || !params->default_action_args,
EINVAL);
+ /* Hash function checks. */
+ if (params->hash_func_name) {
+ hf = hash_func_find(p, params->hash_func_name);
+ CHECK(hf, EINVAL);
+ }
+
/* Table type checks. */
if (recommended_table_type_name)
CHECK_NAME(recommended_table_type_name, EINVAL);
@@ -8141,6 +8148,7 @@ rte_swx_pipeline_table_config(struct rte_swx_pipeline *p,
t->default_action_is_const = params->default_action_is_const;
t->action_data_size_max = action_data_size_max;
+ t->hf = hf;
t->size = size;
t->id = p->n_tables;
@@ -8227,6 +8235,7 @@ table_params_get(struct table *table)
params->key_offset = key_offset;
params->key_mask0 = key_mask;
params->action_data_size = action_data_size;
+ params->hash_func = table->hf ? table->hf->func : NULL;
params->n_keys_max = table->size;
return params;
@@ -10265,6 +10274,7 @@ rte_swx_ctl_table_info_get(struct rte_swx_pipeline *p,
table->n_match_fields = t->n_fields;
table->n_actions = t->n_actions;
table->default_action_is_const = t->default_action_is_const;
+ table->hash_func = t->hf ? t->hf->func : NULL;
table->size = t->size;
return 0;
}
diff --git a/lib/pipeline/rte_swx_pipeline.h b/lib/pipeline/rte_swx_pipeline.h
index 9c629d4118..09c75180f8 100644
--- a/lib/pipeline/rte_swx_pipeline.h
+++ b/lib/pipeline/rte_swx_pipeline.h
@@ -331,23 +331,6 @@ rte_swx_pipeline_extern_func_register(struct rte_swx_pipeline *p,
* Hash function.
*/
-/**
- * Hash function prototype
- *
- * @param[in] key
- * Key to hash. Must be non-NULL.
- * @param[in] length
- * Key length in bytes.
- * @param[in] seed
- * Hash seed.
- * @return
- * Hash value.
- */
-typedef uint32_t
-(*rte_swx_hash_func_t)(const void *key,
- uint32_t length,
- uint32_t seed);
-
/**
* Pipeline hash function register
*
@@ -699,6 +682,13 @@ struct rte_swx_pipeline_table_params {
* list.
*/
int default_action_is_const;
+
+ /** Hash function name. When not set to NULL, it must point to one of
+ * the hash functions that were registered for the current pipeline.
+ * Ignored by the table implementation when not needed. When needed but
+ * NULL, the table implementation will select the hash function to use.
+ */
+ const char *hash_func_name;
};
/**
diff --git a/lib/pipeline/rte_swx_pipeline_internal.h b/lib/pipeline/rte_swx_pipeline_internal.h
index 6d65b635c6..ee579c6656 100644
--- a/lib/pipeline/rte_swx_pipeline_internal.h
+++ b/lib/pipeline/rte_swx_pipeline_internal.h
@@ -828,6 +828,7 @@ struct table {
int *action_is_for_table_entries;
int *action_is_for_default_entry;
+ struct hash_func *hf;
uint32_t size;
uint32_t id;
};
diff --git a/lib/pipeline/rte_swx_pipeline_spec.c b/lib/pipeline/rte_swx_pipeline_spec.c
index 1b4183ef55..c0ca7335ff 100644
--- a/lib/pipeline/rte_swx_pipeline_spec.c
+++ b/lib/pipeline/rte_swx_pipeline_spec.c
@@ -509,7 +509,7 @@ action_block_parse(struct action_spec *s,
static void
table_spec_free(struct table_spec *s)
{
- uintptr_t default_action_name, default_action_args;
+ uintptr_t default_action_name, default_action_args, hash_func_name;
uint32_t i;
if (!s)
@@ -556,6 +556,10 @@ table_spec_free(struct table_spec *s)
s->params.default_action_is_const = 0;
+ hash_func_name = (uintptr_t)s->params.hash_func_name;
+ free((void *)hash_func_name);
+ s->params.hash_func_name = NULL;
+
free(s->recommended_table_type_name);
s->recommended_table_type_name = NULL;
@@ -935,6 +939,35 @@ table_block_parse(struct table_spec *s,
err_line,
err_msg);
+ if (!strcmp(tokens[0], "hash")) {
+ if (n_tokens != 2) {
+ if (err_line)
+ *err_line = n_lines;
+ if (err_msg)
+ *err_msg = "Invalid hash statement.";
+ return -EINVAL;
+ }
+
+ if (s->params.hash_func_name) {
+ if (err_line)
+ *err_line = n_lines;
+ if (err_msg)
+ *err_msg = "Duplicate hash statement.";
+ return -EINVAL;
+ }
+
+ s->params.hash_func_name = strdup(tokens[1]);
+ if (!s->params.hash_func_name) {
+ if (err_line)
+ *err_line = n_lines;
+ if (err_msg)
+ *err_msg = "Memory allocation failed.";
+ return -ENOMEM;
+ }
+
+ return 0;
+ }
+
if (!strcmp(tokens[0], "instanceof")) {
if (n_tokens != 2) {
if (err_line)
diff --git a/lib/pipeline/rte_swx_pipeline_spec.h b/lib/pipeline/rte_swx_pipeline_spec.h
index 62ac4ecfc4..dbe1b40adc 100644
--- a/lib/pipeline/rte_swx_pipeline_spec.h
+++ b/lib/pipeline/rte_swx_pipeline_spec.h
@@ -88,6 +88,7 @@ struct action_spec {
* ...
* }
* default_action ACTION_NAME args none | ARG0_NAME ARG0_VALUE ... [ const ]
+ * hash HASH_FUNCTION_NAME
* instanceof TABLE_TYPE_NAME
* pragma ARGS
* size SIZE
--
2.34.1
^ permalink raw reply [flat|nested] 17+ messages in thread
* [PATCH 5/6] table: configure the hash function for learner tables
2022-08-18 11:44 [PATCH 0/6] pipeline: make the hash function configurable per table Cristian Dumitrescu
` (3 preceding siblings ...)
2022-08-18 11:44 ` [PATCH 4/6] pipeline: " Cristian Dumitrescu
@ 2022-08-18 11:44 ` Cristian Dumitrescu
2022-08-18 11:44 ` [PATCH 6/6] pipeline: " Cristian Dumitrescu
2022-08-19 19:52 ` [PATCH V2 0/6] pipeline: make the hash function configurable per table Cristian Dumitrescu
6 siblings, 0 replies; 17+ messages in thread
From: Cristian Dumitrescu @ 2022-08-18 11:44 UTC (permalink / raw)
To: dev; +Cc: Kamalakannan R .
Make the hash function configurable. The internal hash function that
was not configurable, mask-based and limited to 64 bytes is removed.
Signed-off-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
Signed-off-by: Kamalakannan R. <kamalakannan.r@intel.com>
---
lib/table/rte_swx_table_learner.c | 220 ++++--------------------------
lib/table/rte_swx_table_learner.h | 6 +
2 files changed, 34 insertions(+), 192 deletions(-)
diff --git a/lib/table/rte_swx_table_learner.c b/lib/table/rte_swx_table_learner.c
index f7f8e8aea9..c1045a1082 100644
--- a/lib/table/rte_swx_table_learner.c
+++ b/lib/table/rte_swx_table_learner.c
@@ -8,7 +8,10 @@
#include <rte_common.h>
#include <rte_cycles.h>
#include <rte_prefetch.h>
+#include <rte_jhash.h>
+#include <rte_hash_crc.h>
+#include "rte_swx_keycmp.h"
#include "rte_swx_table_learner.h"
#ifndef RTE_SWX_TABLE_LEARNER_USE_HUGE_PAGES
@@ -62,181 +65,10 @@ env_free(void *start, size_t size)
#endif
-#if defined(RTE_ARCH_X86_64)
-
-#include <x86intrin.h>
-
-#define crc32_u64(crc, v) _mm_crc32_u64(crc, v)
-
-#else
-
-static inline uint64_t
-crc32_u64_generic(uint64_t crc, uint64_t value)
-{
- int i;
-
- crc = (crc & 0xFFFFFFFFLLU) ^ value;
- for (i = 63; i >= 0; i--) {
- uint64_t mask;
-
- mask = -(crc & 1LLU);
- crc = (crc >> 1LLU) ^ (0x82F63B78LLU & mask);
- }
-
- return crc;
-}
-
-#define crc32_u64(crc, v) crc32_u64_generic(crc, v)
-
-#endif
-
-/* Key size needs to be one of: 8, 16, 32 or 64. */
-static inline uint32_t
-hash(void *key, void *key_mask, uint32_t key_size, uint32_t seed)
-{
- uint64_t *k = key;
- uint64_t *m = key_mask;
- uint64_t k0, k2, k5, crc0, crc1, crc2, crc3, crc4, crc5;
-
- switch (key_size) {
- case 8:
- crc0 = crc32_u64(seed, k[0] & m[0]);
- return crc0;
-
- case 16:
- k0 = k[0] & m[0];
-
- crc0 = crc32_u64(k0, seed);
- crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
-
- crc0 ^= crc1;
-
- return crc0;
-
- case 32:
- k0 = k[0] & m[0];
- k2 = k[2] & m[2];
-
- crc0 = crc32_u64(k0, seed);
- crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
-
- crc2 = crc32_u64(k2, k[3] & m[3]);
- crc3 = k2 >> 32;
-
- crc0 = crc32_u64(crc0, crc1);
- crc1 = crc32_u64(crc2, crc3);
-
- crc0 ^= crc1;
-
- return crc0;
-
- case 64:
- k0 = k[0] & m[0];
- k2 = k[2] & m[2];
- k5 = k[5] & m[5];
-
- crc0 = crc32_u64(k0, seed);
- crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
-
- crc2 = crc32_u64(k2, k[3] & m[3]);
- crc3 = crc32_u64(k2 >> 32, k[4] & m[4]);
-
- crc4 = crc32_u64(k5, k[6] & m[6]);
- crc5 = crc32_u64(k5 >> 32, k[7] & m[7]);
-
- crc0 = crc32_u64(crc0, (crc1 << 32) ^ crc2);
- crc1 = crc32_u64(crc3, (crc4 << 32) ^ crc5);
-
- crc0 ^= crc1;
-
- return crc0;
-
- default:
- crc0 = 0;
- return crc0;
- }
-}
-
-/* n_bytes needs to be a multiple of 8 bytes. */
static void
-table_keycpy(void *dst, void *src, void *src_mask, uint32_t n_bytes)
-{
- uint64_t *dst64 = dst, *src64 = src, *src_mask64 = src_mask;
- uint32_t i;
-
- for (i = 0; i < n_bytes / sizeof(uint64_t); i++)
- dst64[i] = src64[i] & src_mask64[i];
-}
-
-/*
- * Return: 0 = Keys are NOT equal; 1 = Keys are equal.
- */
-static inline uint32_t
-table_keycmp(void *a, void *b, void *b_mask, uint32_t n_bytes)
+table_keycpy(void *dst, void *src, uint32_t n_bytes)
{
- uint64_t *a64 = a, *b64 = b, *b_mask64 = b_mask;
-
- switch (n_bytes) {
- case 8: {
- uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
- uint32_t result = 1;
-
- if (xor0)
- result = 0;
- return result;
- }
-
- case 16: {
- uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
- uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]);
- uint64_t or = xor0 | xor1;
- uint32_t result = 1;
-
- if (or)
- result = 0;
- return result;
- }
-
- case 32: {
- uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
- uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]);
- uint64_t xor2 = a64[2] ^ (b64[2] & b_mask64[2]);
- uint64_t xor3 = a64[3] ^ (b64[3] & b_mask64[3]);
- uint64_t or = (xor0 | xor1) | (xor2 | xor3);
- uint32_t result = 1;
-
- if (or)
- result = 0;
- return result;
- }
-
- case 64: {
- uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
- uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]);
- uint64_t xor2 = a64[2] ^ (b64[2] & b_mask64[2]);
- uint64_t xor3 = a64[3] ^ (b64[3] & b_mask64[3]);
- uint64_t xor4 = a64[4] ^ (b64[4] & b_mask64[4]);
- uint64_t xor5 = a64[5] ^ (b64[5] & b_mask64[5]);
- uint64_t xor6 = a64[6] ^ (b64[6] & b_mask64[6]);
- uint64_t xor7 = a64[7] ^ (b64[7] & b_mask64[7]);
- uint64_t or = ((xor0 | xor1) | (xor2 | xor3)) |
- ((xor4 | xor5) | (xor6 | xor7));
- uint32_t result = 1;
-
- if (or)
- result = 0;
- return result;
- }
-
- default: {
- uint32_t i;
-
- for (i = 0; i < n_bytes / sizeof(uint64_t); i++)
- if (a64[i] != (b64[i] & b_mask64[i]))
- return 0;
- return 1;
- }
- }
+ memcpy(dst, src, n_bytes);
}
#define TABLE_KEYS_PER_BUCKET 4
@@ -259,10 +91,7 @@ struct table_params {
/* The real key size. Must be non-zero. */
size_t key_size;
- /* They key size upgrated to the next power of 2. This used for hash generation (in
- * increments of 8 bytes, from 8 to 64 bytes) and for run-time key comparison. This is why
- * key sizes bigger than 64 bytes are not allowed.
- */
+ /* The key size upgrated to the next power of 2. */
size_t key_size_pow2;
/* log2(key_size_pow2). Purpose: avoid multiplication with non-power-of-2 numbers. */
@@ -299,6 +128,12 @@ struct table_params {
/* log2(bucket_size). Purpose: avoid multiplication with non-power of 2 numbers. */
size_t bucket_size_log2;
+ /* Hash function. */
+ rte_swx_hash_func_t hash_func;
+
+ /* Key comparison function. */
+ rte_swx_keycmp_func_t keycmp_func;
+
/* Set of all possible key timeout values measured in CPU clock cycles. */
uint64_t key_timeout[RTE_SWX_TABLE_LEARNER_N_KEY_TIMEOUTS_MAX];
@@ -313,9 +148,6 @@ struct table {
/* Table parameters. */
struct table_params params;
- /* Key mask. Array of *key_size* bytes. */
- uint8_t key_mask0[RTE_CACHE_LINE_SIZE];
-
/* Table buckets. */
uint8_t buckets[];
} __rte_cache_aligned;
@@ -344,7 +176,6 @@ table_params_get(struct table_params *p, struct rte_swx_table_learner_params *pa
/* Check input parameters. */
if (!params ||
!params->key_size ||
- (params->key_size > 64) ||
!params->n_keys_max ||
(params->n_keys_max > 1U << 31) ||
!params->key_timeout ||
@@ -352,6 +183,15 @@ table_params_get(struct table_params *p, struct rte_swx_table_learner_params *pa
(params->n_key_timeouts > RTE_SWX_TABLE_LEARNER_N_KEY_TIMEOUTS_MAX))
return -EINVAL;
+ if (params->key_mask0) {
+ for (i = 0; i < params->key_size; i++)
+ if (params->key_mask0[i] != 0xFF)
+ break;
+
+ if (i < params->key_size)
+ return -EINVAL;
+ }
+
for (i = 0; i < params->n_key_timeouts; i++)
if (!params->key_timeout[i])
return -EINVAL;
@@ -360,8 +200,6 @@ table_params_get(struct table_params *p, struct rte_swx_table_learner_params *pa
p->key_size = params->key_size;
p->key_size_pow2 = rte_align64pow2(p->key_size);
- if (p->key_size_pow2 < 8)
- p->key_size_pow2 = 8;
p->key_size_log2 = __builtin_ctzll(p->key_size_pow2);
@@ -387,6 +225,10 @@ table_params_get(struct table_params *p, struct rte_swx_table_learner_params *pa
p->bucket_size_log2 = __builtin_ctzll(p->bucket_size);
+ p->hash_func = params->hash_func ? params->hash_func : rte_hash_crc;
+
+ p->keycmp_func = rte_swx_keycmp_func_get(params->key_size);
+
/* Timeout. */
for (i = 0; i < params->n_key_timeouts; i++)
p->key_timeout[i] = timeout_convert(params->key_timeout[i]);
@@ -452,11 +294,6 @@ rte_swx_table_learner_create(struct rte_swx_table_learner_params *params, int nu
/* Memory initialization. */
memcpy(&t->params, &p, sizeof(struct table_params));
- if (params->key_mask0)
- memcpy(t->key_mask0, params->key_mask0, params->key_size);
- else
- memset(t->key_mask0, 0xFF, params->key_size);
-
return t;
}
@@ -534,7 +371,7 @@ rte_swx_table_learner_lookup(void *table,
uint32_t input_sig;
input_key = &(*key)[t->params.key_offset];
- input_sig = hash(input_key, t->key_mask0, t->params.key_size_pow2, 0);
+ input_sig = t->params.hash_func(input_key, t->params.key_size, 0);
bucket_id = input_sig & t->params.bucket_mask;
b = table_bucket_get(t, bucket_id);
@@ -558,13 +395,12 @@ rte_swx_table_learner_lookup(void *table,
uint64_t time = b->time[i];
uint32_t sig = b->sig[i];
uint8_t *key = table_bucket_key_get(t, b, i);
- uint32_t key_size_pow2 = t->params.key_size_pow2;
time <<= 32;
if ((time > input_time) &&
(sig == m->input_sig) &&
- table_keycmp(key, m->input_key, t->key_mask0, key_size_pow2)) {
+ t->params.keycmp_func(key, m->input_key, t->params.key_size)) {
uint64_t *data = table_bucket_data_get(t, b, i);
/* Hit. */
@@ -703,7 +539,7 @@ rte_swx_table_learner_add(void *table,
b->time[i] = (input_time + key_timeout) >> 32;
b->sig[i] = m->input_sig;
b->key_timeout_id[i] = (uint8_t)key_timeout_id;
- table_keycpy(key, m->input_key, t->key_mask0, t->params.key_size_pow2);
+ table_keycpy(key, m->input_key, t->params.key_size);
/* Install the key data. */
data[0] = action_id;
diff --git a/lib/table/rte_swx_table_learner.h b/lib/table/rte_swx_table_learner.h
index 1fee306806..d72b6b88ff 100644
--- a/lib/table/rte_swx_table_learner.h
+++ b/lib/table/rte_swx_table_learner.h
@@ -50,6 +50,8 @@ extern "C" {
#include <rte_compat.h>
+#include "rte_swx_hash_func.h"
+
/** Maximum number of key timeout values per learner table. */
#ifndef RTE_SWX_TABLE_LEARNER_N_KEY_TIMEOUTS_MAX
#define RTE_SWX_TABLE_LEARNER_N_KEY_TIMEOUTS_MAX 16
@@ -77,6 +79,10 @@ struct rte_swx_table_learner_params {
*/
uint32_t action_data_size;
+ /** Hash function. When NULL, the default hash function will be used.
+ */
+ rte_swx_hash_func_t hash_func;
+
/** Maximum number of keys to be stored in the table together with their associated data. */
uint32_t n_keys_max;
--
2.34.1
^ permalink raw reply [flat|nested] 17+ messages in thread
* [PATCH 6/6] pipeline: configure the hash function for learner tables
2022-08-18 11:44 [PATCH 0/6] pipeline: make the hash function configurable per table Cristian Dumitrescu
` (4 preceding siblings ...)
2022-08-18 11:44 ` [PATCH 5/6] table: configure the hash function for learner tables Cristian Dumitrescu
@ 2022-08-18 11:44 ` Cristian Dumitrescu
2022-08-19 19:52 ` [PATCH V2 0/6] pipeline: make the hash function configurable per table Cristian Dumitrescu
6 siblings, 0 replies; 17+ messages in thread
From: Cristian Dumitrescu @ 2022-08-18 11:44 UTC (permalink / raw)
To: dev; +Cc: Kamalakannan R .
Make the hash function configurable for the learner pipeline tables.
Signed-off-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
Signed-off-by: Kamalakannan R. <kamalakannan.r@intel.com>
---
lib/pipeline/rte_swx_pipeline.c | 12 ++++++++
lib/pipeline/rte_swx_pipeline.h | 6 ++++
lib/pipeline/rte_swx_pipeline_internal.h | 1 +
lib/pipeline/rte_swx_pipeline_spec.c | 35 +++++++++++++++++++++++-
lib/pipeline/rte_swx_pipeline_spec.h | 1 +
5 files changed, 54 insertions(+), 1 deletion(-)
diff --git a/lib/pipeline/rte_swx_pipeline.c b/lib/pipeline/rte_swx_pipeline.c
index e1227cbfcc..e9e024029e 100644
--- a/lib/pipeline/rte_swx_pipeline.c
+++ b/lib/pipeline/rte_swx_pipeline.c
@@ -8893,6 +8893,7 @@ rte_swx_pipeline_learner_config(struct rte_swx_pipeline *p,
struct learner *l = NULL;
struct action *default_action;
struct header *header = NULL;
+ struct hash_func *hf = NULL;
uint32_t action_data_size_max = 0, i;
int status = 0;
@@ -8955,6 +8956,12 @@ rte_swx_pipeline_learner_config(struct rte_swx_pipeline *p,
CHECK((default_action->st && params->default_action_args) || !params->default_action_args,
EINVAL);
+ /* Hash function checks. */
+ if (params->hash_func_name) {
+ hf = hash_func_find(p, params->hash_func_name);
+ CHECK(hf, EINVAL);
+ }
+
/* Any other checks. */
CHECK(size, EINVAL);
CHECK(timeout, EINVAL);
@@ -9043,6 +9050,8 @@ rte_swx_pipeline_learner_config(struct rte_swx_pipeline *p,
l->action_data_size_max = action_data_size_max;
+ l->hf = hf;
+
l->size = size;
for (i = 0; i < n_timeouts; i++)
@@ -9132,6 +9141,9 @@ learner_params_get(struct learner *l)
/* Action data size. */
params->action_data_size = l->action_data_size_max;
+ /* Hash function. */
+ params->hash_func = l->hf ? l->hf->func : NULL;
+
/* Maximum number of keys. */
params->n_keys_max = l->size;
diff --git a/lib/pipeline/rte_swx_pipeline.h b/lib/pipeline/rte_swx_pipeline.h
index 09c75180f8..2c9cc6ee44 100644
--- a/lib/pipeline/rte_swx_pipeline.h
+++ b/lib/pipeline/rte_swx_pipeline.h
@@ -829,6 +829,12 @@ struct rte_swx_pipeline_learner_params {
* list.
*/
int default_action_is_const;
+
+ /** Hash function name. When not set to NULL, it must point to one of
+ * the hash functions that were registered for the current pipeline.
+ * When NULL, the default hash function will be used.
+ */
+ const char *hash_func_name;
};
/**
diff --git a/lib/pipeline/rte_swx_pipeline_internal.h b/lib/pipeline/rte_swx_pipeline_internal.h
index ee579c6656..ef60288dca 100644
--- a/lib/pipeline/rte_swx_pipeline_internal.h
+++ b/lib/pipeline/rte_swx_pipeline_internal.h
@@ -900,6 +900,7 @@ struct learner {
int *action_is_for_table_entries;
int *action_is_for_default_entry;
+ struct hash_func *hf;
uint32_t size;
uint32_t timeout[RTE_SWX_TABLE_LEARNER_N_KEY_TIMEOUTS_MAX];
uint32_t n_timeouts;
diff --git a/lib/pipeline/rte_swx_pipeline_spec.c b/lib/pipeline/rte_swx_pipeline_spec.c
index c0ca7335ff..5a07edd519 100644
--- a/lib/pipeline/rte_swx_pipeline_spec.c
+++ b/lib/pipeline/rte_swx_pipeline_spec.c
@@ -1350,7 +1350,7 @@ selector_block_parse(struct selector_spec *s,
static void
learner_spec_free(struct learner_spec *s)
{
- uintptr_t default_action_name, default_action_args;
+ uintptr_t default_action_name, default_action_args, hash_func_name;
uint32_t i;
if (!s)
@@ -1397,6 +1397,10 @@ learner_spec_free(struct learner_spec *s)
s->params.default_action_is_const = 0;
+ hash_func_name = (uintptr_t)s->params.hash_func_name;
+ free((void *)hash_func_name);
+ s->params.hash_func_name = NULL;
+
s->size = 0;
free(s->timeout);
@@ -1853,6 +1857,35 @@ learner_block_parse(struct learner_spec *s,
err_line,
err_msg);
+ if (!strcmp(tokens[0], "hash")) {
+ if (n_tokens != 2) {
+ if (err_line)
+ *err_line = n_lines;
+ if (err_msg)
+ *err_msg = "Invalid hash statement.";
+ return -EINVAL;
+ }
+
+ if (s->params.hash_func_name) {
+ if (err_line)
+ *err_line = n_lines;
+ if (err_msg)
+ *err_msg = "Duplicate hash statement.";
+ return -EINVAL;
+ }
+
+ s->params.hash_func_name = strdup(tokens[1]);
+ if (!s->params.hash_func_name) {
+ if (err_line)
+ *err_line = n_lines;
+ if (err_msg)
+ *err_msg = "Memory allocation failed.";
+ return -ENOMEM;
+ }
+
+ return 0;
+ }
+
if (!strcmp(tokens[0], "size")) {
char *p = tokens[1];
diff --git a/lib/pipeline/rte_swx_pipeline_spec.h b/lib/pipeline/rte_swx_pipeline_spec.h
index dbe1b40adc..123e175f8b 100644
--- a/lib/pipeline/rte_swx_pipeline_spec.h
+++ b/lib/pipeline/rte_swx_pipeline_spec.h
@@ -134,6 +134,7 @@ struct selector_spec {
* ...
* }
* default_action ACTION_NAME args none | ARG0_NAME ARG0_VALUE ... [ const ]
+ * hash HASH_FUNCTION_NAME
* size SIZE
* timeout {
* TIMEOUT_IN_SECONDS
--
2.34.1
^ permalink raw reply [flat|nested] 17+ messages in thread
* [PATCH V2 0/6] pipeline: make the hash function configurable per table
2022-08-18 11:44 [PATCH 0/6] pipeline: make the hash function configurable per table Cristian Dumitrescu
` (5 preceding siblings ...)
2022-08-18 11:44 ` [PATCH 6/6] pipeline: " Cristian Dumitrescu
@ 2022-08-19 19:52 ` Cristian Dumitrescu
2022-08-19 19:52 ` [PATCH V2 1/6] table: add hash function prototype Cristian Dumitrescu
` (7 more replies)
6 siblings, 8 replies; 17+ messages in thread
From: Cristian Dumitrescu @ 2022-08-19 19:52 UTC (permalink / raw)
To: dev
The exact match and learner tables use a hash function for the lookup
operation. This patch set makes the hash function configurable and
removes some limitations.
The hash function previously used by these table types had the
following limitations:
a) Not configurable: An internally hardcoded version was used;
b) Mask-based: This prevents using most of the available
hash functions, as they are not mask-based;
c) Key size limited to 64 bytes or less.
The new hash function is:
a) Configurable;
b) Not mask-based;
c) Not limited to key sizes to less than or equal to 64 bytes.
Also, since this flexibility has some performance cost, this patch set
also introduces key comparison functions specialized for each key size
value. Since the key size is fixed for each table, the key comparison
function can be selected at initialization as opposed to using a
generic function that can handle any key size. This strategy result in
a performance improvement for the table lookup operation of around 5%.
Depends-on: series-24117 ("pipeline: pipeline configuration and build improvements")
Change log:
V2:
-Added check for table match fields to be contiguous for exact match tables.
-Fixed bug in the specification file parsing related to hash function configuration.
Cristian Dumitrescu (6):
table: add hash function prototype
table: add key comparison functions
table: configure the hash function for regular tables
pipeline: configure the hash function for regular tables
table: configure the hash function for learner tables
pipeline: configure the hash function for learner tables
lib/pipeline/rte_swx_ctl.c | 1 +
lib/pipeline/rte_swx_ctl.h | 3 +
lib/pipeline/rte_swx_pipeline.c | 134 ++++++++++--
lib/pipeline/rte_swx_pipeline.h | 30 ++-
lib/pipeline/rte_swx_pipeline_internal.h | 2 +
lib/pipeline/rte_swx_pipeline_spec.c | 83 ++++++-
lib/pipeline/rte_swx_pipeline_spec.h | 2 +
lib/table/meson.build | 2 +
lib/table/rte_swx_hash_func.h | 39 ++++
lib/table/rte_swx_keycmp.c | 166 ++++++++++++++
lib/table/rte_swx_keycmp.h | 49 +++++
lib/table/rte_swx_table.h | 8 +
lib/table/rte_swx_table_em.c | 266 ++++-------------------
lib/table/rte_swx_table_learner.c | 220 +++----------------
lib/table/rte_swx_table_learner.h | 6 +
15 files changed, 555 insertions(+), 456 deletions(-)
create mode 100644 lib/table/rte_swx_hash_func.h
create mode 100644 lib/table/rte_swx_keycmp.c
create mode 100644 lib/table/rte_swx_keycmp.h
--
2.34.1
^ permalink raw reply [flat|nested] 17+ messages in thread
* [PATCH V2 1/6] table: add hash function prototype
2022-08-19 19:52 ` [PATCH V2 0/6] pipeline: make the hash function configurable per table Cristian Dumitrescu
@ 2022-08-19 19:52 ` Cristian Dumitrescu
2022-08-19 19:52 ` [PATCH V2 2/6] table: add key comparison functions Cristian Dumitrescu
` (6 subsequent siblings)
7 siblings, 0 replies; 17+ messages in thread
From: Cristian Dumitrescu @ 2022-08-19 19:52 UTC (permalink / raw)
To: dev; +Cc: Kamalakannan R .
Add hash function prototype to be used by the exact match and the
learner table types. The hash function is not mask-based, so the table
key fields have to be contiguous in memory.
Signed-off-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
Signed-off-by: Kamalakannan R. <kamalakannan.r@intel.com>
---
lib/table/meson.build | 1 +
lib/table/rte_swx_hash_func.h | 39 +++++++++++++++++++++++++++++++++++
2 files changed, 40 insertions(+)
create mode 100644 lib/table/rte_swx_hash_func.h
diff --git a/lib/table/meson.build b/lib/table/meson.build
index d1f2f9dcf6..6d4272c4ef 100644
--- a/lib/table/meson.build
+++ b/lib/table/meson.build
@@ -26,6 +26,7 @@ sources = files(
)
headers = files(
'rte_lru.h',
+ 'rte_swx_hash_func.h',
'rte_swx_table.h',
'rte_swx_table_em.h',
'rte_swx_table_learner.h',
diff --git a/lib/table/rte_swx_hash_func.h b/lib/table/rte_swx_hash_func.h
new file mode 100644
index 0000000000..04f3d543e7
--- /dev/null
+++ b/lib/table/rte_swx_hash_func.h
@@ -0,0 +1,39 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2022 Intel Corporation
+ */
+#ifndef __INCLUDE_RTE_SWX_HASH_FUNC_H__
+#define __INCLUDE_RTE_SWX_HASH_FUNC_H__
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ * @file
+ * RTE SWX Hash Function
+ */
+
+#include <stdint.h>
+
+/**
+ * Hash function prototype
+ *
+ * @param[in] key
+ * Key to hash. Must be non-NULL.
+ * @param[in] length
+ * Key length in bytes.
+ * @param[in] seed
+ * Hash seed.
+ * @return
+ * Hash value.
+ */
+typedef uint32_t
+(*rte_swx_hash_func_t)(const void *key,
+ uint32_t length,
+ uint32_t seed);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
--
2.34.1
^ permalink raw reply [flat|nested] 17+ messages in thread
* [PATCH V2 2/6] table: add key comparison functions
2022-08-19 19:52 ` [PATCH V2 0/6] pipeline: make the hash function configurable per table Cristian Dumitrescu
2022-08-19 19:52 ` [PATCH V2 1/6] table: add hash function prototype Cristian Dumitrescu
@ 2022-08-19 19:52 ` Cristian Dumitrescu
2022-08-19 19:52 ` [PATCH V2 3/6] table: configure the hash function for regular tables Cristian Dumitrescu
` (5 subsequent siblings)
7 siblings, 0 replies; 17+ messages in thread
From: Cristian Dumitrescu @ 2022-08-19 19:52 UTC (permalink / raw)
To: dev; +Cc: Kamalakannan R .
Add key comparison functions to be used by the exact match and the
learner table types as part of the performance critical lookup
operation. Since the key size is fixed, it is possible to select a
specialized memory copy function as opposed to using the variable size
version, resulting in a performance improvement of around 5%.
Signed-off-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
Signed-off-by: Kamalakannan R. <kamalakannan.r@intel.com>
---
lib/table/meson.build | 1 +
lib/table/rte_swx_keycmp.c | 166 +++++++++++++++++++++++++++++++++++++
lib/table/rte_swx_keycmp.h | 49 +++++++++++
3 files changed, 216 insertions(+)
create mode 100644 lib/table/rte_swx_keycmp.c
create mode 100644 lib/table/rte_swx_keycmp.h
diff --git a/lib/table/meson.build b/lib/table/meson.build
index 6d4272c4ef..af749e4007 100644
--- a/lib/table/meson.build
+++ b/lib/table/meson.build
@@ -8,6 +8,7 @@ if is_windows
endif
sources = files(
+ 'rte_swx_keycmp.c',
'rte_swx_table_em.c',
'rte_swx_table_learner.c',
'rte_swx_table_selector.c',
diff --git a/lib/table/rte_swx_keycmp.c b/lib/table/rte_swx_keycmp.c
new file mode 100644
index 0000000000..ec65f5c822
--- /dev/null
+++ b/lib/table/rte_swx_keycmp.c
@@ -0,0 +1,166 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2022 Intel Corporation
+ */
+#include <rte_common.h>
+
+#include "rte_swx_keycmp.h"
+
+static uint32_t
+keycmp_generic(void *key1, void *key2, uint32_t key_size)
+{
+ return memcmp(key1, key2, key_size) ? 0 : 1;
+}
+
+#define KEYCMP(N) \
+static uint32_t \
+keycmp##N(void *key1, void *key2, uint32_t key_size __rte_unused) \
+{ \
+ return memcmp(key1, key2, N) ? 0 : 1; \
+}
+
+KEYCMP(1)
+KEYCMP(2)
+KEYCMP(3)
+KEYCMP(4)
+KEYCMP(5)
+KEYCMP(6)
+KEYCMP(7)
+KEYCMP(8)
+KEYCMP(9)
+
+KEYCMP(10)
+KEYCMP(11)
+KEYCMP(12)
+KEYCMP(13)
+KEYCMP(14)
+KEYCMP(15)
+KEYCMP(16)
+KEYCMP(17)
+KEYCMP(18)
+KEYCMP(19)
+
+KEYCMP(20)
+KEYCMP(21)
+KEYCMP(22)
+KEYCMP(23)
+KEYCMP(24)
+KEYCMP(25)
+KEYCMP(26)
+KEYCMP(27)
+KEYCMP(28)
+KEYCMP(29)
+
+KEYCMP(30)
+KEYCMP(31)
+KEYCMP(32)
+KEYCMP(33)
+KEYCMP(34)
+KEYCMP(35)
+KEYCMP(36)
+KEYCMP(37)
+KEYCMP(38)
+KEYCMP(39)
+
+KEYCMP(40)
+KEYCMP(41)
+KEYCMP(42)
+KEYCMP(43)
+KEYCMP(44)
+KEYCMP(45)
+KEYCMP(46)
+KEYCMP(47)
+KEYCMP(48)
+KEYCMP(49)
+
+KEYCMP(50)
+KEYCMP(51)
+KEYCMP(52)
+KEYCMP(53)
+KEYCMP(54)
+KEYCMP(55)
+KEYCMP(56)
+KEYCMP(57)
+KEYCMP(58)
+KEYCMP(59)
+
+KEYCMP(60)
+KEYCMP(61)
+KEYCMP(62)
+KEYCMP(63)
+KEYCMP(64)
+
+static rte_swx_keycmp_func_t keycmp_funcs[] = {
+ keycmp1,
+ keycmp2,
+ keycmp3,
+ keycmp4,
+ keycmp5,
+ keycmp6,
+ keycmp7,
+ keycmp8,
+ keycmp9,
+ keycmp10,
+ keycmp11,
+ keycmp12,
+ keycmp13,
+ keycmp14,
+ keycmp15,
+ keycmp16,
+ keycmp17,
+ keycmp18,
+ keycmp19,
+ keycmp20,
+ keycmp21,
+ keycmp22,
+ keycmp23,
+ keycmp24,
+ keycmp25,
+ keycmp26,
+ keycmp27,
+ keycmp28,
+ keycmp29,
+ keycmp30,
+ keycmp31,
+ keycmp32,
+ keycmp33,
+ keycmp34,
+ keycmp35,
+ keycmp36,
+ keycmp37,
+ keycmp38,
+ keycmp39,
+ keycmp40,
+ keycmp41,
+ keycmp42,
+ keycmp43,
+ keycmp44,
+ keycmp45,
+ keycmp46,
+ keycmp47,
+ keycmp48,
+ keycmp49,
+ keycmp50,
+ keycmp51,
+ keycmp52,
+ keycmp53,
+ keycmp54,
+ keycmp55,
+ keycmp56,
+ keycmp57,
+ keycmp58,
+ keycmp59,
+ keycmp60,
+ keycmp61,
+ keycmp62,
+ keycmp63,
+ keycmp64,
+};
+
+rte_swx_keycmp_func_t
+rte_swx_keycmp_func_get(uint32_t key_size)
+{
+ if (key_size && key_size <= 64)
+ return keycmp_funcs[key_size - 1];
+
+ return keycmp_generic;
+}
diff --git a/lib/table/rte_swx_keycmp.h b/lib/table/rte_swx_keycmp.h
new file mode 100644
index 0000000000..09fb1be869
--- /dev/null
+++ b/lib/table/rte_swx_keycmp.h
@@ -0,0 +1,49 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2022 Intel Corporation
+ */
+#ifndef __INCLUDE_RTE_SWX_KEYCMP_H__
+#define __INCLUDE_RTE_SWX_KEYCMP_H__
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ * @file
+ * RTE SWX Key Comparison Functions
+ */
+
+#include <stdint.h>
+#include <string.h>
+
+/**
+ * Key comparison function prototype
+ *
+ * @param[in] key1
+ * First key to compare. Must be non-NULL.
+ * @param[in] key2
+ * Second key to compare. Must be non-NULL.
+ * @param[in] key_size
+ * Key size in bytes.
+ * @return
+ * 0 when keys are different, 1 when keys are equal.
+ */
+typedef uint32_t
+(*rte_swx_keycmp_func_t)(void *key1, void *key2, uint32_t key_size);
+
+/**
+ * Key comparison function get
+ *
+ * @param[in] key_size
+ * Key size in bytes.
+ * @return
+ * Key comparison function for the given key size
+ */
+rte_swx_keycmp_func_t
+rte_swx_keycmp_func_get(uint32_t key_size);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
--
2.34.1
^ permalink raw reply [flat|nested] 17+ messages in thread
* [PATCH V2 3/6] table: configure the hash function for regular tables
2022-08-19 19:52 ` [PATCH V2 0/6] pipeline: make the hash function configurable per table Cristian Dumitrescu
2022-08-19 19:52 ` [PATCH V2 1/6] table: add hash function prototype Cristian Dumitrescu
2022-08-19 19:52 ` [PATCH V2 2/6] table: add key comparison functions Cristian Dumitrescu
@ 2022-08-19 19:52 ` Cristian Dumitrescu
2022-08-19 19:52 ` [PATCH V2 4/6] pipeline: " Cristian Dumitrescu
` (4 subsequent siblings)
7 siblings, 0 replies; 17+ messages in thread
From: Cristian Dumitrescu @ 2022-08-19 19:52 UTC (permalink / raw)
To: dev; +Cc: Kamalakannan R .
Make the hash function configurable. The internal hash function that
was not configurable, mask-based and limited to 64 bytes is removed.
Signed-off-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
Signed-off-by: Kamalakannan R. <kamalakannan.r@intel.com>
---
lib/table/rte_swx_table.h | 8 ++
lib/table/rte_swx_table_em.c | 266 ++++++-----------------------------
2 files changed, 49 insertions(+), 225 deletions(-)
diff --git a/lib/table/rte_swx_table.h b/lib/table/rte_swx_table.h
index c1383c2e57..4b8dc06798 100644
--- a/lib/table/rte_swx_table.h
+++ b/lib/table/rte_swx_table.h
@@ -19,6 +19,8 @@ extern "C" {
#include <rte_os.h>
+#include "rte_swx_hash_func.h"
+
/** Match type. */
enum rte_swx_table_match_type {
/** Wildcard Match (WM). */
@@ -58,6 +60,12 @@ struct rte_swx_table_params {
*/
uint32_t action_data_size;
+ /** Hash function. Ignored when not needed by the table implementation.
+ * When needed but set to NULL, the table implementation will select the
+ * hash function to use.
+ */
+ rte_swx_hash_func_t hash_func;
+
/** Maximum number of keys to be stored in the table together with their
* associated data.
*/
diff --git a/lib/table/rte_swx_table_em.c b/lib/table/rte_swx_table_em.c
index f783cfe282..568e76e249 100644
--- a/lib/table/rte_swx_table_em.c
+++ b/lib/table/rte_swx_table_em.c
@@ -7,7 +7,10 @@
#include <rte_common.h>
#include <rte_prefetch.h>
+#include <rte_jhash.h>
+#include <rte_hash_crc.h>
+#include "rte_swx_keycmp.h"
#include "rte_swx_table_em.h"
#define CHECK(condition, err_code) \
@@ -54,181 +57,10 @@ env_free(void *start, size_t size)
#endif
-#if defined(RTE_ARCH_X86_64)
-
-#include <x86intrin.h>
-
-#define crc32_u64(crc, v) _mm_crc32_u64(crc, v)
-
-#else
-
-static inline uint64_t
-crc32_u64_generic(uint64_t crc, uint64_t value)
-{
- int i;
-
- crc = (crc & 0xFFFFFFFFLLU) ^ value;
- for (i = 63; i >= 0; i--) {
- uint64_t mask;
-
- mask = -(crc & 1LLU);
- crc = (crc >> 1LLU) ^ (0x82F63B78LLU & mask);
- }
-
- return crc;
-}
-
-#define crc32_u64(crc, v) crc32_u64_generic(crc, v)
-
-#endif
-
-/* Key size needs to be one of: 8, 16, 32 or 64. */
-static inline uint32_t
-hash(void *key, void *key_mask, uint32_t key_size, uint32_t seed)
-{
- uint64_t *k = key;
- uint64_t *m = key_mask;
- uint64_t k0, k2, k5, crc0, crc1, crc2, crc3, crc4, crc5;
-
- switch (key_size) {
- case 8:
- crc0 = crc32_u64(seed, k[0] & m[0]);
- return crc0;
-
- case 16:
- k0 = k[0] & m[0];
-
- crc0 = crc32_u64(k0, seed);
- crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
-
- crc0 ^= crc1;
-
- return crc0;
-
- case 32:
- k0 = k[0] & m[0];
- k2 = k[2] & m[2];
-
- crc0 = crc32_u64(k0, seed);
- crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
-
- crc2 = crc32_u64(k2, k[3] & m[3]);
- crc3 = k2 >> 32;
-
- crc0 = crc32_u64(crc0, crc1);
- crc1 = crc32_u64(crc2, crc3);
-
- crc0 ^= crc1;
-
- return crc0;
-
- case 64:
- k0 = k[0] & m[0];
- k2 = k[2] & m[2];
- k5 = k[5] & m[5];
-
- crc0 = crc32_u64(k0, seed);
- crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
-
- crc2 = crc32_u64(k2, k[3] & m[3]);
- crc3 = crc32_u64(k2 >> 32, k[4] & m[4]);
-
- crc4 = crc32_u64(k5, k[6] & m[6]);
- crc5 = crc32_u64(k5 >> 32, k[7] & m[7]);
-
- crc0 = crc32_u64(crc0, (crc1 << 32) ^ crc2);
- crc1 = crc32_u64(crc3, (crc4 << 32) ^ crc5);
-
- crc0 ^= crc1;
-
- return crc0;
-
- default:
- crc0 = 0;
- return crc0;
- }
-}
-
-/* n_bytes needs to be a multiple of 8 bytes. */
static void
-keycpy(void *dst, void *src, void *src_mask, uint32_t n_bytes)
+keycpy(void *dst, void *src, uint32_t n_bytes)
{
- uint64_t *dst64 = dst, *src64 = src, *src_mask64 = src_mask;
- uint32_t i;
-
- for (i = 0; i < n_bytes / sizeof(uint64_t); i++)
- dst64[i] = src64[i] & src_mask64[i];
-}
-
-/*
- * Return: 0 = Keys are NOT equal; 1 = Keys are equal.
- */
-static inline uint32_t
-keycmp(void *a, void *b, void *b_mask, uint32_t n_bytes)
-{
- uint64_t *a64 = a, *b64 = b, *b_mask64 = b_mask;
-
- switch (n_bytes) {
- case 8: {
- uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
- uint32_t result = 1;
-
- if (xor0)
- result = 0;
- return result;
- }
-
- case 16: {
- uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
- uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]);
- uint64_t or = xor0 | xor1;
- uint32_t result = 1;
-
- if (or)
- result = 0;
- return result;
- }
-
- case 32: {
- uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
- uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]);
- uint64_t xor2 = a64[2] ^ (b64[2] & b_mask64[2]);
- uint64_t xor3 = a64[3] ^ (b64[3] & b_mask64[3]);
- uint64_t or = (xor0 | xor1) | (xor2 | xor3);
- uint32_t result = 1;
-
- if (or)
- result = 0;
- return result;
- }
-
- case 64: {
- uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
- uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]);
- uint64_t xor2 = a64[2] ^ (b64[2] & b_mask64[2]);
- uint64_t xor3 = a64[3] ^ (b64[3] & b_mask64[3]);
- uint64_t xor4 = a64[4] ^ (b64[4] & b_mask64[4]);
- uint64_t xor5 = a64[5] ^ (b64[5] & b_mask64[5]);
- uint64_t xor6 = a64[6] ^ (b64[6] & b_mask64[6]);
- uint64_t xor7 = a64[7] ^ (b64[7] & b_mask64[7]);
- uint64_t or = ((xor0 | xor1) | (xor2 | xor3)) |
- ((xor4 | xor5) | (xor6 | xor7));
- uint32_t result = 1;
-
- if (or)
- result = 0;
- return result;
- }
-
- default: {
- uint32_t i;
-
- for (i = 0; i < n_bytes / sizeof(uint64_t); i++)
- if (a64[i] != (b64[i] & b_mask64[i]))
- return 0;
- return 1;
- }
- }
+ memcpy(dst, src, n_bytes);
}
#define KEYS_PER_BUCKET 4
@@ -244,8 +76,6 @@ struct table {
struct rte_swx_table_params params;
/* Internal. */
- uint32_t key_size;
- uint32_t data_size;
uint32_t key_size_shl;
uint32_t data_size_shl;
uint32_t n_buckets;
@@ -253,9 +83,9 @@ struct table {
uint32_t key_stack_tos;
uint32_t bkt_ext_stack_tos;
uint64_t total_size;
+ rte_swx_keycmp_func_t keycmp_func;
/* Memory arrays. */
- uint8_t *key_mask;
struct bucket_extension *buckets;
struct bucket_extension *buckets_ext;
uint8_t *keys;
@@ -279,8 +109,7 @@ table_key_data(struct table *t, uint32_t key_id)
static inline int
bkt_is_empty(struct bucket_extension *bkt)
{
- return (!bkt->sig[0] && !bkt->sig[1] && !bkt->sig[2] && !bkt->sig[3]) ?
- 1 : 0;
+ return (!bkt->sig[0] && !bkt->sig[1] && !bkt->sig[2] && !bkt->sig[3]) ? 1 : 0;
}
/* Return:
@@ -311,7 +140,7 @@ bkt_keycmp(struct table *t,
/* Key comparison. */
bkt_key_id = bkt->key_id[bkt_pos];
bkt_key = table_key(t, bkt_key_id);
- return keycmp(bkt_key, input_key, t->key_mask, t->key_size);
+ return t->keycmp_func(bkt_key, input_key, t->params.key_size);
}
static inline void
@@ -331,15 +160,13 @@ bkt_key_install(struct table *t,
/* Key. */
bkt->key_id[bkt_pos] = bkt_key_id;
bkt_key = table_key(t, bkt_key_id);
- keycpy(bkt_key, input->key, t->key_mask, t->key_size);
+ keycpy(bkt_key, input->key, t->params.key_size);
/* Key data. */
bkt_data = table_key_data(t, bkt_key_id);
bkt_data[0] = input->action_id;
if (t->params.action_data_size && input->action_data)
- memcpy(&bkt_data[1],
- input->action_data,
- t->params.action_data_size);
+ memcpy(&bkt_data[1], input->action_data, t->params.action_data_size);
}
static inline void
@@ -358,9 +185,7 @@ bkt_key_data_update(struct table *t,
bkt_data = table_key_data(t, bkt_key_id);
bkt_data[0] = input->action_id;
if (t->params.action_data_size && input->action_data)
- memcpy(&bkt_data[1],
- input->action_data,
- t->params.action_data_size);
+ memcpy(&bkt_data[1], input->action_data, t->params.action_data_size);
}
#define CL RTE_CACHE_LINE_ROUNDUP
@@ -374,9 +199,9 @@ __table_create(struct table **table,
{
struct table *t;
uint8_t *memory;
- size_t table_meta_sz, key_mask_sz, bucket_sz, bucket_ext_sz, key_sz,
+ size_t table_meta_sz, bucket_sz, bucket_ext_sz, key_sz,
key_stack_sz, bkt_ext_stack_sz, data_sz, total_size;
- size_t key_mask_offset, bucket_offset, bucket_ext_offset, key_offset,
+ size_t bucket_offset, bucket_ext_offset, key_offset,
key_stack_offset, bkt_ext_stack_offset, data_offset;
uint32_t key_size, key_data_size, n_buckets, n_buckets_ext, i;
@@ -384,30 +209,34 @@ __table_create(struct table **table,
CHECK(params, EINVAL);
CHECK(params->match_type == RTE_SWX_TABLE_MATCH_EXACT, EINVAL);
CHECK(params->key_size, EINVAL);
- CHECK(params->key_size <= 64, EINVAL);
+
+ if (params->key_mask0) {
+ for (i = 0; i < params->key_size; i++)
+ if (params->key_mask0[i] != 0xFF)
+ break;
+
+ CHECK(i == params->key_size, EINVAL);
+ }
+
CHECK(params->n_keys_max, EINVAL);
/* Memory allocation. */
key_size = rte_align64pow2(params->key_size);
- if (key_size < 8)
- key_size = 8;
key_data_size = rte_align64pow2(params->action_data_size + 8);
- n_buckets = params->n_keys_max / KEYS_PER_BUCKET;
- n_buckets_ext = params->n_keys_max / KEYS_PER_BUCKET;
+ n_buckets = rte_align64pow2((params->n_keys_max + KEYS_PER_BUCKET - 1) / KEYS_PER_BUCKET);
+ n_buckets_ext = n_buckets;
table_meta_sz = CL(sizeof(struct table));
- key_mask_sz = CL(key_size);
bucket_sz = CL(n_buckets * sizeof(struct bucket_extension));
bucket_ext_sz = CL(n_buckets_ext * sizeof(struct bucket_extension));
key_sz = CL(params->n_keys_max * key_size);
key_stack_sz = CL(params->n_keys_max * sizeof(uint32_t));
bkt_ext_stack_sz = CL(n_buckets_ext * sizeof(uint32_t));
data_sz = CL(params->n_keys_max * key_data_size);
- total_size = table_meta_sz + key_mask_sz + bucket_sz + bucket_ext_sz +
+ total_size = table_meta_sz + bucket_sz + bucket_ext_sz +
key_sz + key_stack_sz + bkt_ext_stack_sz + data_sz;
- key_mask_offset = table_meta_sz;
- bucket_offset = key_mask_offset + key_mask_sz;
+ bucket_offset = table_meta_sz;
bucket_ext_offset = bucket_offset + bucket_sz;
key_offset = bucket_ext_offset + bucket_ext_sz;
key_stack_offset = key_offset + key_sz;
@@ -427,16 +256,17 @@ __table_create(struct table **table,
/* Initialization. */
t = (struct table *)memory;
memcpy(&t->params, params, sizeof(*params));
+ t->params.key_mask0 = NULL;
+ if (!params->hash_func)
+ t->params.hash_func = rte_hash_crc;
- t->key_size = key_size;
- t->data_size = key_data_size;
t->key_size_shl = __builtin_ctzl(key_size);
t->data_size_shl = __builtin_ctzl(key_data_size);
t->n_buckets = n_buckets;
t->n_buckets_ext = n_buckets_ext;
t->total_size = total_size;
+ t->keycmp_func = rte_swx_keycmp_func_get(params->key_size);
- t->key_mask = &memory[key_mask_offset];
t->buckets = (struct bucket_extension *)&memory[bucket_offset];
t->buckets_ext = (struct bucket_extension *)&memory[bucket_ext_offset];
t->keys = &memory[key_offset];
@@ -444,13 +274,6 @@ __table_create(struct table **table,
t->bkt_ext_stack = (uint32_t *)&memory[bkt_ext_stack_offset];
t->data = &memory[data_offset];
- t->params.key_mask0 = t->key_mask;
-
- if (!params->key_mask0)
- memset(t->key_mask, 0xFF, params->key_size);
- else
- memcpy(t->key_mask, params->key_mask0, params->key_size);
-
for (i = 0; i < t->params.n_keys_max; i++)
t->key_stack[i] = t->params.n_keys_max - 1 - i;
t->key_stack_tos = t->params.n_keys_max;
@@ -485,7 +308,7 @@ table_add(void *table, struct rte_swx_table_entry *entry)
CHECK(entry, EINVAL);
CHECK(entry->key, EINVAL);
- input_sig = hash(entry->key, t->key_mask, t->key_size, 0);
+ input_sig = t->params.hash_func(entry->key, t->params.key_size, 0);
bkt_id = input_sig & (t->n_buckets - 1);
bkt0 = &t->buckets[bkt_id];
input_sig = (input_sig >> 16) | 1;
@@ -506,10 +329,8 @@ table_add(void *table, struct rte_swx_table_entry *entry)
/* Allocate new key & install. */
CHECK(t->key_stack_tos, ENOSPC);
- new_bkt_key_id =
- t->key_stack[--t->key_stack_tos];
- bkt_key_install(t, bkt, entry, i,
- new_bkt_key_id, input_sig);
+ new_bkt_key_id = t->key_stack[--t->key_stack_tos];
+ bkt_key_install(t, bkt, entry, i, new_bkt_key_id, input_sig);
return 0;
}
@@ -526,8 +347,7 @@ table_add(void *table, struct rte_swx_table_entry *entry)
/* Allocate new key & install. */
new_bkt_key_id = t->key_stack[--t->key_stack_tos];
- bkt_key_install(t, new_bkt, entry, 0,
- new_bkt_key_id, input_sig);
+ bkt_key_install(t, new_bkt, entry, 0, new_bkt_key_id, input_sig);
return 0;
}
@@ -545,7 +365,7 @@ table_del(void *table, struct rte_swx_table_entry *entry)
CHECK(entry, EINVAL);
CHECK(entry->key, EINVAL);
- input_sig = hash(entry->key, t->key_mask, t->key_size, 0);
+ input_sig = t->params.hash_func(entry->key, t->params.key_size, 0);
bkt_id = input_sig & (t->n_buckets - 1);
bkt0 = &t->buckets[bkt_id];
input_sig = (input_sig >> 16) | 1;
@@ -556,17 +376,13 @@ table_del(void *table, struct rte_swx_table_entry *entry)
if (bkt_keycmp(t, bkt, entry->key, i, input_sig)) {
/* Key free. */
bkt->sig[i] = 0;
- t->key_stack[t->key_stack_tos++] =
- bkt->key_id[i];
+ t->key_stack[t->key_stack_tos++] = bkt->key_id[i];
- /* Bucket extension free if empty and not the
- * 1st in bucket.
- */
+ /* Bucket extension free if empty and not the 1st in bucket. */
if (bkt_prev && bkt_is_empty(bkt)) {
bkt_prev->next = bkt->next;
bkt_id = bkt - t->buckets_ext;
- t->bkt_ext_stack[t->bkt_ext_stack_tos++]
- = bkt_id;
+ t->bkt_ext_stack[t->bkt_ext_stack_tos++] = bkt_id;
}
return 0;
@@ -596,7 +412,7 @@ table_lookup_unoptimized(void *table,
input_key = &(*key)[t->params.key_offset];
- input_sig = hash(input_key, t->key_mask, t->key_size, 0);
+ input_sig = t->params.hash_func(input_key, t->params.key_size, 0);
bkt_id = input_sig & (t->n_buckets - 1);
bkt0 = &t->buckets[bkt_id];
input_sig = (input_sig >> 16) | 1;
@@ -695,7 +511,7 @@ table_lookup(void *table,
struct bucket_extension *bkt;
uint32_t input_sig, bkt_id;
- input_sig = hash(input_key, t->key_mask, t->key_size, 0);
+ input_sig = t->params.hash_func(input_key, t->params.key_size, 0);
bkt_id = input_sig & (t->n_buckets - 1);
bkt = &t->buckets[bkt_id];
rte_prefetch0(bkt);
@@ -756,7 +572,7 @@ table_lookup(void *table,
uint64_t *bkt_data = table_key_data(t, bkt_key_id);
uint32_t lkp_hit;
- lkp_hit = keycmp(bkt_key, input_key, t->key_mask, t->key_size);
+ lkp_hit = t->keycmp_func(bkt_key, input_key, t->params.key_size);
lkp_hit &= m->sig_match;
*action_id = bkt_data[0];
*action_data = (uint8_t *)&bkt_data[1];
--
2.34.1
^ permalink raw reply [flat|nested] 17+ messages in thread
* [PATCH V2 4/6] pipeline: configure the hash function for regular tables
2022-08-19 19:52 ` [PATCH V2 0/6] pipeline: make the hash function configurable per table Cristian Dumitrescu
` (2 preceding siblings ...)
2022-08-19 19:52 ` [PATCH V2 3/6] table: configure the hash function for regular tables Cristian Dumitrescu
@ 2022-08-19 19:52 ` Cristian Dumitrescu
2022-08-19 19:52 ` [PATCH V2 5/6] table: configure the hash function for learner tables Cristian Dumitrescu
` (3 subsequent siblings)
7 siblings, 0 replies; 17+ messages in thread
From: Cristian Dumitrescu @ 2022-08-19 19:52 UTC (permalink / raw)
To: dev; +Cc: Kamalakannan R .
Make the hash function configurable for the regular pipeline tables.
Signed-off-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
Signed-off-by: Kamalakannan R. <kamalakannan.r@intel.com>
---
lib/pipeline/rte_swx_ctl.c | 1 +
lib/pipeline/rte_swx_ctl.h | 3 ++
lib/pipeline/rte_swx_pipeline.c | 56 +++++++++++++++++++-----
lib/pipeline/rte_swx_pipeline.h | 24 +++-------
lib/pipeline/rte_swx_pipeline_internal.h | 1 +
lib/pipeline/rte_swx_pipeline_spec.c | 42 +++++++++++++++++-
lib/pipeline/rte_swx_pipeline_spec.h | 1 +
7 files changed, 100 insertions(+), 28 deletions(-)
diff --git a/lib/pipeline/rte_swx_ctl.c b/lib/pipeline/rte_swx_ctl.c
index bdbcd8f50a..b6449f5f0c 100644
--- a/lib/pipeline/rte_swx_ctl.c
+++ b/lib/pipeline/rte_swx_ctl.c
@@ -272,6 +272,7 @@ table_params_get(struct rte_swx_ctl_pipeline *ctl, uint32_t table_id)
table->params.key_offset = key_offset;
table->params.key_mask0 = key_mask;
table->params.action_data_size = action_data_size;
+ table->params.hash_func = table->info.hash_func;
table->params.n_keys_max = table->info.size;
table->mf_first = first;
diff --git a/lib/pipeline/rte_swx_ctl.h b/lib/pipeline/rte_swx_ctl.h
index 63ee479e47..0694df557a 100644
--- a/lib/pipeline/rte_swx_ctl.h
+++ b/lib/pipeline/rte_swx_ctl.h
@@ -236,6 +236,9 @@ struct rte_swx_ctl_table_info {
*/
int default_action_is_const;
+ /** Hash function. */
+ rte_swx_hash_func_t hash_func;
+
/** Table size parameter. */
uint32_t size;
};
diff --git a/lib/pipeline/rte_swx_pipeline.c b/lib/pipeline/rte_swx_pipeline.c
index 2cac4caa95..0b21adacbc 100644
--- a/lib/pipeline/rte_swx_pipeline.c
+++ b/lib/pipeline/rte_swx_pipeline.c
@@ -7866,6 +7866,7 @@ rte_swx_pipeline_table_type_register(struct rte_swx_pipeline *p,
static int
table_match_type_resolve(struct rte_swx_match_field_params *fields,
uint32_t n_fields,
+ int contiguous_fields,
enum rte_swx_table_match_type *match_type)
{
uint32_t n_fields_em = 0, n_fields_lpm = 0, i;
@@ -7884,7 +7885,7 @@ table_match_type_resolve(struct rte_swx_match_field_params *fields,
(n_fields_lpm && (n_fields_em != n_fields - 1)))
return -EINVAL;
- *match_type = (n_fields_em == n_fields) ?
+ *match_type = ((n_fields_em == n_fields) && contiguous_fields) ?
RTE_SWX_TABLE_MATCH_EXACT :
RTE_SWX_TABLE_MATCH_WILDCARD;
@@ -7894,11 +7895,12 @@ table_match_type_resolve(struct rte_swx_match_field_params *fields,
static int
table_match_fields_check(struct rte_swx_pipeline *p,
struct rte_swx_pipeline_table_params *params,
- struct header **header)
+ struct header **header,
+ int *contiguous_fields)
{
struct header *h0 = NULL;
struct field *hf, *mf;
- uint32_t *offset = NULL, i;
+ uint32_t *offset = NULL, *n_bits = NULL, n_fields_with_valid_next = 0, i;
int status = 0;
/* Return if no match fields. */
@@ -7911,12 +7913,16 @@ table_match_fields_check(struct rte_swx_pipeline *p,
if (header)
*header = NULL;
+ if (contiguous_fields)
+ *contiguous_fields = 0;
+
return 0;
}
/* Memory allocation. */
offset = calloc(params->n_fields, sizeof(uint32_t));
- if (!offset) {
+ n_bits = calloc(params->n_fields, sizeof(uint32_t));
+ if (!offset || !n_bits) {
status = -ENOMEM;
goto end;
}
@@ -7932,6 +7938,7 @@ table_match_fields_check(struct rte_swx_pipeline *p,
}
offset[0] = h0 ? hf->offset : mf->offset;
+ n_bits[0] = h0 ? hf->n_bits : mf->n_bits;
for (i = 1; i < params->n_fields; i++)
if (h0) {
@@ -7944,6 +7951,7 @@ table_match_fields_check(struct rte_swx_pipeline *p,
}
offset[i] = hf->offset;
+ n_bits[i] = hf->n_bits;
} else {
mf = metadata_field_parse(p, params->fields[i].name);
if (!mf) {
@@ -7952,6 +7960,7 @@ table_match_fields_check(struct rte_swx_pipeline *p,
}
offset[i] = mf->offset;
+ n_bits[i] = mf->n_bits;
}
/* Check that there are no duplicated match fields. */
@@ -7965,12 +7974,28 @@ table_match_fields_check(struct rte_swx_pipeline *p,
}
}
+ /* Detect if the match fields are contiguous or not. */
+ for (i = 0; i < params->n_fields; i++) {
+ uint32_t offset_next = offset[i] + n_bits[i];
+ uint32_t j;
+
+ for (j = 0; j < params->n_fields; j++)
+ if (offset[j] == offset_next) {
+ n_fields_with_valid_next++;
+ break;
+ }
+ }
+
/* Return. */
if (header)
*header = h0;
+ if (contiguous_fields)
+ *contiguous_fields = (n_fields_with_valid_next == params->n_fields - 1) ? 1 : 0;
+
end:
free(offset);
+ free(n_bits);
return status;
}
@@ -7982,12 +8007,13 @@ rte_swx_pipeline_table_config(struct rte_swx_pipeline *p,
const char *args,
uint32_t size)
{
- struct table_type *type;
+ struct table_type *type = NULL;
struct table *t = NULL;
struct action *default_action;
struct header *header = NULL;
+ struct hash_func *hf = NULL;
uint32_t action_data_size_max = 0, i;
- int status = 0;
+ int contiguous_fields = 0, status = 0;
CHECK(p, EINVAL);
@@ -7999,7 +8025,7 @@ rte_swx_pipeline_table_config(struct rte_swx_pipeline *p,
CHECK(params, EINVAL);
/* Match checks. */
- status = table_match_fields_check(p, params, &header);
+ status = table_match_fields_check(p, params, &header, &contiguous_fields);
if (status)
return status;
@@ -8042,6 +8068,12 @@ rte_swx_pipeline_table_config(struct rte_swx_pipeline *p,
CHECK((default_action->st && params->default_action_args) || !params->default_action_args,
EINVAL);
+ /* Hash function checks. */
+ if (params->hash_func_name) {
+ hf = hash_func_find(p, params->hash_func_name);
+ CHECK(hf, EINVAL);
+ }
+
/* Table type checks. */
if (recommended_table_type_name)
CHECK_NAME(recommended_table_type_name, EINVAL);
@@ -8049,14 +8081,15 @@ rte_swx_pipeline_table_config(struct rte_swx_pipeline *p,
if (params->n_fields) {
enum rte_swx_table_match_type match_type;
- status = table_match_type_resolve(params->fields, params->n_fields, &match_type);
+ status = table_match_type_resolve(params->fields,
+ params->n_fields,
+ contiguous_fields,
+ &match_type);
if (status)
return status;
type = table_type_resolve(p, recommended_table_type_name, match_type);
CHECK(type, EINVAL);
- } else {
- type = NULL;
}
/* Memory allocation. */
@@ -8141,6 +8174,7 @@ rte_swx_pipeline_table_config(struct rte_swx_pipeline *p,
t->default_action_is_const = params->default_action_is_const;
t->action_data_size_max = action_data_size_max;
+ t->hf = hf;
t->size = size;
t->id = p->n_tables;
@@ -8227,6 +8261,7 @@ table_params_get(struct table *table)
params->key_offset = key_offset;
params->key_mask0 = key_mask;
params->action_data_size = action_data_size;
+ params->hash_func = table->hf ? table->hf->func : NULL;
params->n_keys_max = table->size;
return params;
@@ -10265,6 +10300,7 @@ rte_swx_ctl_table_info_get(struct rte_swx_pipeline *p,
table->n_match_fields = t->n_fields;
table->n_actions = t->n_actions;
table->default_action_is_const = t->default_action_is_const;
+ table->hash_func = t->hf ? t->hf->func : NULL;
table->size = t->size;
return 0;
}
diff --git a/lib/pipeline/rte_swx_pipeline.h b/lib/pipeline/rte_swx_pipeline.h
index 9c629d4118..09c75180f8 100644
--- a/lib/pipeline/rte_swx_pipeline.h
+++ b/lib/pipeline/rte_swx_pipeline.h
@@ -331,23 +331,6 @@ rte_swx_pipeline_extern_func_register(struct rte_swx_pipeline *p,
* Hash function.
*/
-/**
- * Hash function prototype
- *
- * @param[in] key
- * Key to hash. Must be non-NULL.
- * @param[in] length
- * Key length in bytes.
- * @param[in] seed
- * Hash seed.
- * @return
- * Hash value.
- */
-typedef uint32_t
-(*rte_swx_hash_func_t)(const void *key,
- uint32_t length,
- uint32_t seed);
-
/**
* Pipeline hash function register
*
@@ -699,6 +682,13 @@ struct rte_swx_pipeline_table_params {
* list.
*/
int default_action_is_const;
+
+ /** Hash function name. When not set to NULL, it must point to one of
+ * the hash functions that were registered for the current pipeline.
+ * Ignored by the table implementation when not needed. When needed but
+ * NULL, the table implementation will select the hash function to use.
+ */
+ const char *hash_func_name;
};
/**
diff --git a/lib/pipeline/rte_swx_pipeline_internal.h b/lib/pipeline/rte_swx_pipeline_internal.h
index 6d65b635c6..ee579c6656 100644
--- a/lib/pipeline/rte_swx_pipeline_internal.h
+++ b/lib/pipeline/rte_swx_pipeline_internal.h
@@ -828,6 +828,7 @@ struct table {
int *action_is_for_table_entries;
int *action_is_for_default_entry;
+ struct hash_func *hf;
uint32_t size;
uint32_t id;
};
diff --git a/lib/pipeline/rte_swx_pipeline_spec.c b/lib/pipeline/rte_swx_pipeline_spec.c
index 1b4183ef55..e9fde4f241 100644
--- a/lib/pipeline/rte_swx_pipeline_spec.c
+++ b/lib/pipeline/rte_swx_pipeline_spec.c
@@ -509,7 +509,7 @@ action_block_parse(struct action_spec *s,
static void
table_spec_free(struct table_spec *s)
{
- uintptr_t default_action_name, default_action_args;
+ uintptr_t default_action_name, default_action_args, hash_func_name;
uint32_t i;
if (!s)
@@ -556,6 +556,10 @@ table_spec_free(struct table_spec *s)
s->params.default_action_is_const = 0;
+ hash_func_name = (uintptr_t)s->params.hash_func_name;
+ free((void *)hash_func_name);
+ s->params.hash_func_name = NULL;
+
free(s->recommended_table_type_name);
s->recommended_table_type_name = NULL;
@@ -935,6 +939,35 @@ table_block_parse(struct table_spec *s,
err_line,
err_msg);
+ if (!strcmp(tokens[0], "hash")) {
+ if (n_tokens != 2) {
+ if (err_line)
+ *err_line = n_lines;
+ if (err_msg)
+ *err_msg = "Invalid hash statement.";
+ return -EINVAL;
+ }
+
+ if (s->params.hash_func_name) {
+ if (err_line)
+ *err_line = n_lines;
+ if (err_msg)
+ *err_msg = "Duplicate hash statement.";
+ return -EINVAL;
+ }
+
+ s->params.hash_func_name = strdup(tokens[1]);
+ if (!s->params.hash_func_name) {
+ if (err_line)
+ *err_line = n_lines;
+ if (err_msg)
+ *err_msg = "Memory allocation failed.";
+ return -ENOMEM;
+ }
+
+ return 0;
+ }
+
if (!strcmp(tokens[0], "instanceof")) {
if (n_tokens != 2) {
if (err_line)
@@ -2419,6 +2452,13 @@ pipeline_spec_codegen(FILE *f,
fprintf(f, "\t\t\t.default_action_is_const = %d,\n",
table_spec->params.default_action_is_const);
+
+ if (table_spec->params.hash_func_name)
+ fprintf(f, "\t\t\t.hash_func_name = \"%s\",\n",
+ table_spec->params.hash_func_name);
+ else
+ fprintf(f, "\t\t\t.hash_func_name = NULL,\n");
+
fprintf(f, "\t\t},\n");
if (table_spec->recommended_table_type_name)
diff --git a/lib/pipeline/rte_swx_pipeline_spec.h b/lib/pipeline/rte_swx_pipeline_spec.h
index 62ac4ecfc4..dbe1b40adc 100644
--- a/lib/pipeline/rte_swx_pipeline_spec.h
+++ b/lib/pipeline/rte_swx_pipeline_spec.h
@@ -88,6 +88,7 @@ struct action_spec {
* ...
* }
* default_action ACTION_NAME args none | ARG0_NAME ARG0_VALUE ... [ const ]
+ * hash HASH_FUNCTION_NAME
* instanceof TABLE_TYPE_NAME
* pragma ARGS
* size SIZE
--
2.34.1
^ permalink raw reply [flat|nested] 17+ messages in thread
* [PATCH V2 5/6] table: configure the hash function for learner tables
2022-08-19 19:52 ` [PATCH V2 0/6] pipeline: make the hash function configurable per table Cristian Dumitrescu
` (3 preceding siblings ...)
2022-08-19 19:52 ` [PATCH V2 4/6] pipeline: " Cristian Dumitrescu
@ 2022-08-19 19:52 ` Cristian Dumitrescu
2022-08-19 19:52 ` [PATCH V2 6/6] pipeline: " Cristian Dumitrescu
` (2 subsequent siblings)
7 siblings, 0 replies; 17+ messages in thread
From: Cristian Dumitrescu @ 2022-08-19 19:52 UTC (permalink / raw)
To: dev; +Cc: Kamalakannan R .
Make the hash function configurable. The internal hash function that
was not configurable, mask-based and limited to 64 bytes is removed.
Signed-off-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
Signed-off-by: Kamalakannan R. <kamalakannan.r@intel.com>
---
lib/table/rte_swx_table_learner.c | 220 ++++--------------------------
lib/table/rte_swx_table_learner.h | 6 +
2 files changed, 34 insertions(+), 192 deletions(-)
diff --git a/lib/table/rte_swx_table_learner.c b/lib/table/rte_swx_table_learner.c
index f7f8e8aea9..c1045a1082 100644
--- a/lib/table/rte_swx_table_learner.c
+++ b/lib/table/rte_swx_table_learner.c
@@ -8,7 +8,10 @@
#include <rte_common.h>
#include <rte_cycles.h>
#include <rte_prefetch.h>
+#include <rte_jhash.h>
+#include <rte_hash_crc.h>
+#include "rte_swx_keycmp.h"
#include "rte_swx_table_learner.h"
#ifndef RTE_SWX_TABLE_LEARNER_USE_HUGE_PAGES
@@ -62,181 +65,10 @@ env_free(void *start, size_t size)
#endif
-#if defined(RTE_ARCH_X86_64)
-
-#include <x86intrin.h>
-
-#define crc32_u64(crc, v) _mm_crc32_u64(crc, v)
-
-#else
-
-static inline uint64_t
-crc32_u64_generic(uint64_t crc, uint64_t value)
-{
- int i;
-
- crc = (crc & 0xFFFFFFFFLLU) ^ value;
- for (i = 63; i >= 0; i--) {
- uint64_t mask;
-
- mask = -(crc & 1LLU);
- crc = (crc >> 1LLU) ^ (0x82F63B78LLU & mask);
- }
-
- return crc;
-}
-
-#define crc32_u64(crc, v) crc32_u64_generic(crc, v)
-
-#endif
-
-/* Key size needs to be one of: 8, 16, 32 or 64. */
-static inline uint32_t
-hash(void *key, void *key_mask, uint32_t key_size, uint32_t seed)
-{
- uint64_t *k = key;
- uint64_t *m = key_mask;
- uint64_t k0, k2, k5, crc0, crc1, crc2, crc3, crc4, crc5;
-
- switch (key_size) {
- case 8:
- crc0 = crc32_u64(seed, k[0] & m[0]);
- return crc0;
-
- case 16:
- k0 = k[0] & m[0];
-
- crc0 = crc32_u64(k0, seed);
- crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
-
- crc0 ^= crc1;
-
- return crc0;
-
- case 32:
- k0 = k[0] & m[0];
- k2 = k[2] & m[2];
-
- crc0 = crc32_u64(k0, seed);
- crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
-
- crc2 = crc32_u64(k2, k[3] & m[3]);
- crc3 = k2 >> 32;
-
- crc0 = crc32_u64(crc0, crc1);
- crc1 = crc32_u64(crc2, crc3);
-
- crc0 ^= crc1;
-
- return crc0;
-
- case 64:
- k0 = k[0] & m[0];
- k2 = k[2] & m[2];
- k5 = k[5] & m[5];
-
- crc0 = crc32_u64(k0, seed);
- crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
-
- crc2 = crc32_u64(k2, k[3] & m[3]);
- crc3 = crc32_u64(k2 >> 32, k[4] & m[4]);
-
- crc4 = crc32_u64(k5, k[6] & m[6]);
- crc5 = crc32_u64(k5 >> 32, k[7] & m[7]);
-
- crc0 = crc32_u64(crc0, (crc1 << 32) ^ crc2);
- crc1 = crc32_u64(crc3, (crc4 << 32) ^ crc5);
-
- crc0 ^= crc1;
-
- return crc0;
-
- default:
- crc0 = 0;
- return crc0;
- }
-}
-
-/* n_bytes needs to be a multiple of 8 bytes. */
static void
-table_keycpy(void *dst, void *src, void *src_mask, uint32_t n_bytes)
-{
- uint64_t *dst64 = dst, *src64 = src, *src_mask64 = src_mask;
- uint32_t i;
-
- for (i = 0; i < n_bytes / sizeof(uint64_t); i++)
- dst64[i] = src64[i] & src_mask64[i];
-}
-
-/*
- * Return: 0 = Keys are NOT equal; 1 = Keys are equal.
- */
-static inline uint32_t
-table_keycmp(void *a, void *b, void *b_mask, uint32_t n_bytes)
+table_keycpy(void *dst, void *src, uint32_t n_bytes)
{
- uint64_t *a64 = a, *b64 = b, *b_mask64 = b_mask;
-
- switch (n_bytes) {
- case 8: {
- uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
- uint32_t result = 1;
-
- if (xor0)
- result = 0;
- return result;
- }
-
- case 16: {
- uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
- uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]);
- uint64_t or = xor0 | xor1;
- uint32_t result = 1;
-
- if (or)
- result = 0;
- return result;
- }
-
- case 32: {
- uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
- uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]);
- uint64_t xor2 = a64[2] ^ (b64[2] & b_mask64[2]);
- uint64_t xor3 = a64[3] ^ (b64[3] & b_mask64[3]);
- uint64_t or = (xor0 | xor1) | (xor2 | xor3);
- uint32_t result = 1;
-
- if (or)
- result = 0;
- return result;
- }
-
- case 64: {
- uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
- uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]);
- uint64_t xor2 = a64[2] ^ (b64[2] & b_mask64[2]);
- uint64_t xor3 = a64[3] ^ (b64[3] & b_mask64[3]);
- uint64_t xor4 = a64[4] ^ (b64[4] & b_mask64[4]);
- uint64_t xor5 = a64[5] ^ (b64[5] & b_mask64[5]);
- uint64_t xor6 = a64[6] ^ (b64[6] & b_mask64[6]);
- uint64_t xor7 = a64[7] ^ (b64[7] & b_mask64[7]);
- uint64_t or = ((xor0 | xor1) | (xor2 | xor3)) |
- ((xor4 | xor5) | (xor6 | xor7));
- uint32_t result = 1;
-
- if (or)
- result = 0;
- return result;
- }
-
- default: {
- uint32_t i;
-
- for (i = 0; i < n_bytes / sizeof(uint64_t); i++)
- if (a64[i] != (b64[i] & b_mask64[i]))
- return 0;
- return 1;
- }
- }
+ memcpy(dst, src, n_bytes);
}
#define TABLE_KEYS_PER_BUCKET 4
@@ -259,10 +91,7 @@ struct table_params {
/* The real key size. Must be non-zero. */
size_t key_size;
- /* They key size upgrated to the next power of 2. This used for hash generation (in
- * increments of 8 bytes, from 8 to 64 bytes) and for run-time key comparison. This is why
- * key sizes bigger than 64 bytes are not allowed.
- */
+ /* The key size upgrated to the next power of 2. */
size_t key_size_pow2;
/* log2(key_size_pow2). Purpose: avoid multiplication with non-power-of-2 numbers. */
@@ -299,6 +128,12 @@ struct table_params {
/* log2(bucket_size). Purpose: avoid multiplication with non-power of 2 numbers. */
size_t bucket_size_log2;
+ /* Hash function. */
+ rte_swx_hash_func_t hash_func;
+
+ /* Key comparison function. */
+ rte_swx_keycmp_func_t keycmp_func;
+
/* Set of all possible key timeout values measured in CPU clock cycles. */
uint64_t key_timeout[RTE_SWX_TABLE_LEARNER_N_KEY_TIMEOUTS_MAX];
@@ -313,9 +148,6 @@ struct table {
/* Table parameters. */
struct table_params params;
- /* Key mask. Array of *key_size* bytes. */
- uint8_t key_mask0[RTE_CACHE_LINE_SIZE];
-
/* Table buckets. */
uint8_t buckets[];
} __rte_cache_aligned;
@@ -344,7 +176,6 @@ table_params_get(struct table_params *p, struct rte_swx_table_learner_params *pa
/* Check input parameters. */
if (!params ||
!params->key_size ||
- (params->key_size > 64) ||
!params->n_keys_max ||
(params->n_keys_max > 1U << 31) ||
!params->key_timeout ||
@@ -352,6 +183,15 @@ table_params_get(struct table_params *p, struct rte_swx_table_learner_params *pa
(params->n_key_timeouts > RTE_SWX_TABLE_LEARNER_N_KEY_TIMEOUTS_MAX))
return -EINVAL;
+ if (params->key_mask0) {
+ for (i = 0; i < params->key_size; i++)
+ if (params->key_mask0[i] != 0xFF)
+ break;
+
+ if (i < params->key_size)
+ return -EINVAL;
+ }
+
for (i = 0; i < params->n_key_timeouts; i++)
if (!params->key_timeout[i])
return -EINVAL;
@@ -360,8 +200,6 @@ table_params_get(struct table_params *p, struct rte_swx_table_learner_params *pa
p->key_size = params->key_size;
p->key_size_pow2 = rte_align64pow2(p->key_size);
- if (p->key_size_pow2 < 8)
- p->key_size_pow2 = 8;
p->key_size_log2 = __builtin_ctzll(p->key_size_pow2);
@@ -387,6 +225,10 @@ table_params_get(struct table_params *p, struct rte_swx_table_learner_params *pa
p->bucket_size_log2 = __builtin_ctzll(p->bucket_size);
+ p->hash_func = params->hash_func ? params->hash_func : rte_hash_crc;
+
+ p->keycmp_func = rte_swx_keycmp_func_get(params->key_size);
+
/* Timeout. */
for (i = 0; i < params->n_key_timeouts; i++)
p->key_timeout[i] = timeout_convert(params->key_timeout[i]);
@@ -452,11 +294,6 @@ rte_swx_table_learner_create(struct rte_swx_table_learner_params *params, int nu
/* Memory initialization. */
memcpy(&t->params, &p, sizeof(struct table_params));
- if (params->key_mask0)
- memcpy(t->key_mask0, params->key_mask0, params->key_size);
- else
- memset(t->key_mask0, 0xFF, params->key_size);
-
return t;
}
@@ -534,7 +371,7 @@ rte_swx_table_learner_lookup(void *table,
uint32_t input_sig;
input_key = &(*key)[t->params.key_offset];
- input_sig = hash(input_key, t->key_mask0, t->params.key_size_pow2, 0);
+ input_sig = t->params.hash_func(input_key, t->params.key_size, 0);
bucket_id = input_sig & t->params.bucket_mask;
b = table_bucket_get(t, bucket_id);
@@ -558,13 +395,12 @@ rte_swx_table_learner_lookup(void *table,
uint64_t time = b->time[i];
uint32_t sig = b->sig[i];
uint8_t *key = table_bucket_key_get(t, b, i);
- uint32_t key_size_pow2 = t->params.key_size_pow2;
time <<= 32;
if ((time > input_time) &&
(sig == m->input_sig) &&
- table_keycmp(key, m->input_key, t->key_mask0, key_size_pow2)) {
+ t->params.keycmp_func(key, m->input_key, t->params.key_size)) {
uint64_t *data = table_bucket_data_get(t, b, i);
/* Hit. */
@@ -703,7 +539,7 @@ rte_swx_table_learner_add(void *table,
b->time[i] = (input_time + key_timeout) >> 32;
b->sig[i] = m->input_sig;
b->key_timeout_id[i] = (uint8_t)key_timeout_id;
- table_keycpy(key, m->input_key, t->key_mask0, t->params.key_size_pow2);
+ table_keycpy(key, m->input_key, t->params.key_size);
/* Install the key data. */
data[0] = action_id;
diff --git a/lib/table/rte_swx_table_learner.h b/lib/table/rte_swx_table_learner.h
index 1fee306806..d72b6b88ff 100644
--- a/lib/table/rte_swx_table_learner.h
+++ b/lib/table/rte_swx_table_learner.h
@@ -50,6 +50,8 @@ extern "C" {
#include <rte_compat.h>
+#include "rte_swx_hash_func.h"
+
/** Maximum number of key timeout values per learner table. */
#ifndef RTE_SWX_TABLE_LEARNER_N_KEY_TIMEOUTS_MAX
#define RTE_SWX_TABLE_LEARNER_N_KEY_TIMEOUTS_MAX 16
@@ -77,6 +79,10 @@ struct rte_swx_table_learner_params {
*/
uint32_t action_data_size;
+ /** Hash function. When NULL, the default hash function will be used.
+ */
+ rte_swx_hash_func_t hash_func;
+
/** Maximum number of keys to be stored in the table together with their associated data. */
uint32_t n_keys_max;
--
2.34.1
^ permalink raw reply [flat|nested] 17+ messages in thread
* [PATCH V2 6/6] pipeline: configure the hash function for learner tables
2022-08-19 19:52 ` [PATCH V2 0/6] pipeline: make the hash function configurable per table Cristian Dumitrescu
` (4 preceding siblings ...)
2022-08-19 19:52 ` [PATCH V2 5/6] table: configure the hash function for learner tables Cristian Dumitrescu
@ 2022-08-19 19:52 ` Cristian Dumitrescu
2022-08-31 16:23 ` [PATCH V2 0/6] pipeline: make the hash function configurable per table Stephen Hemminger
2022-09-23 15:58 ` Thomas Monjalon
7 siblings, 0 replies; 17+ messages in thread
From: Cristian Dumitrescu @ 2022-08-19 19:52 UTC (permalink / raw)
To: dev; +Cc: Kamalakannan R .
Make the hash function configurable for the learner pipeline tables.
Signed-off-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
Signed-off-by: Kamalakannan R. <kamalakannan.r@intel.com>
---
lib/pipeline/rte_swx_pipeline.c | 78 +++++++++++++++++++++---
lib/pipeline/rte_swx_pipeline.h | 6 ++
lib/pipeline/rte_swx_pipeline_internal.h | 1 +
lib/pipeline/rte_swx_pipeline_spec.c | 41 ++++++++++++-
lib/pipeline/rte_swx_pipeline_spec.h | 1 +
5 files changed, 116 insertions(+), 11 deletions(-)
diff --git a/lib/pipeline/rte_swx_pipeline.c b/lib/pipeline/rte_swx_pipeline.c
index 0b21adacbc..1c49622be7 100644
--- a/lib/pipeline/rte_swx_pipeline.c
+++ b/lib/pipeline/rte_swx_pipeline.c
@@ -8789,31 +8789,55 @@ learner_match_fields_check(struct rte_swx_pipeline *p,
{
struct header *h0 = NULL;
struct field *hf, *mf;
- uint32_t i;
+ uint32_t *offset = NULL, *n_bits = NULL, n_fields_with_valid_next = 0, i;
+ int status = 0;
/* Return if no match fields. */
if (!params->n_fields || !params->field_names)
return -EINVAL;
+ /* Memory allocation. */
+ offset = calloc(params->n_fields, sizeof(uint32_t));
+ n_bits = calloc(params->n_fields, sizeof(uint32_t));
+ if (!offset || !n_bits) {
+ status = -ENOMEM;
+ goto end;
+ }
+
/* Check that all the match fields either belong to the same header
* or are all meta-data fields.
*/
hf = header_field_parse(p, params->field_names[0], &h0);
mf = metadata_field_parse(p, params->field_names[0]);
- if (!hf && !mf)
- return -EINVAL;
+ if ((!hf && !mf) || (hf && hf->var_size)) {
+ status = -EINVAL;
+ goto end;
+ }
+
+ offset[0] = h0 ? hf->offset : mf->offset;
+ n_bits[0] = h0 ? hf->n_bits : mf->n_bits;
for (i = 1; i < params->n_fields; i++)
if (h0) {
struct header *h;
hf = header_field_parse(p, params->field_names[i], &h);
- if (!hf || (h->id != h0->id))
- return -EINVAL;
+ if (!hf || (h->id != h0->id) || hf->var_size) {
+ status = -EINVAL;
+ goto end;
+ }
+
+ offset[i] = hf->offset;
+ n_bits[i] = hf->n_bits;
} else {
mf = metadata_field_parse(p, params->field_names[i]);
- if (!mf)
- return -EINVAL;
+ if (!mf) {
+ status = -EINVAL;
+ goto end;
+ }
+
+ offset[i] = mf->offset;
+ n_bits[i] = mf->n_bits;
}
/* Check that there are no duplicated match fields. */
@@ -8822,15 +8846,37 @@ learner_match_fields_check(struct rte_swx_pipeline *p,
uint32_t j;
for (j = i + 1; j < params->n_fields; j++)
- if (!strcmp(params->field_names[j], field_name))
- return -EINVAL;
+ if (!strcmp(params->field_names[j], field_name)) {
+ status = -EINVAL;
+ goto end;
+ }
+ }
+
+ /* Check that the match fields are contiguous. */
+ for (i = 0; i < params->n_fields; i++) {
+ uint32_t offset_next = offset[i] + n_bits[i];
+ uint32_t j;
+
+ for (j = 0; j < params->n_fields; j++)
+ if (offset[j] == offset_next) {
+ n_fields_with_valid_next++;
+ break;
+ }
+ }
+
+ if (n_fields_with_valid_next != params->n_fields - 1) {
+ status = -EINVAL;
+ goto end;
}
/* Return. */
if (header)
*header = h0;
- return 0;
+end:
+ free(offset);
+ free(n_bits);
+ return status;
}
static int
@@ -8919,6 +8965,7 @@ rte_swx_pipeline_learner_config(struct rte_swx_pipeline *p,
struct learner *l = NULL;
struct action *default_action;
struct header *header = NULL;
+ struct hash_func *hf = NULL;
uint32_t action_data_size_max = 0, i;
int status = 0;
@@ -8981,6 +9028,12 @@ rte_swx_pipeline_learner_config(struct rte_swx_pipeline *p,
CHECK((default_action->st && params->default_action_args) || !params->default_action_args,
EINVAL);
+ /* Hash function checks. */
+ if (params->hash_func_name) {
+ hf = hash_func_find(p, params->hash_func_name);
+ CHECK(hf, EINVAL);
+ }
+
/* Any other checks. */
CHECK(size, EINVAL);
CHECK(timeout, EINVAL);
@@ -9069,6 +9122,8 @@ rte_swx_pipeline_learner_config(struct rte_swx_pipeline *p,
l->action_data_size_max = action_data_size_max;
+ l->hf = hf;
+
l->size = size;
for (i = 0; i < n_timeouts; i++)
@@ -9158,6 +9213,9 @@ learner_params_get(struct learner *l)
/* Action data size. */
params->action_data_size = l->action_data_size_max;
+ /* Hash function. */
+ params->hash_func = l->hf ? l->hf->func : NULL;
+
/* Maximum number of keys. */
params->n_keys_max = l->size;
diff --git a/lib/pipeline/rte_swx_pipeline.h b/lib/pipeline/rte_swx_pipeline.h
index 09c75180f8..2c9cc6ee44 100644
--- a/lib/pipeline/rte_swx_pipeline.h
+++ b/lib/pipeline/rte_swx_pipeline.h
@@ -829,6 +829,12 @@ struct rte_swx_pipeline_learner_params {
* list.
*/
int default_action_is_const;
+
+ /** Hash function name. When not set to NULL, it must point to one of
+ * the hash functions that were registered for the current pipeline.
+ * When NULL, the default hash function will be used.
+ */
+ const char *hash_func_name;
};
/**
diff --git a/lib/pipeline/rte_swx_pipeline_internal.h b/lib/pipeline/rte_swx_pipeline_internal.h
index ee579c6656..ef60288dca 100644
--- a/lib/pipeline/rte_swx_pipeline_internal.h
+++ b/lib/pipeline/rte_swx_pipeline_internal.h
@@ -900,6 +900,7 @@ struct learner {
int *action_is_for_table_entries;
int *action_is_for_default_entry;
+ struct hash_func *hf;
uint32_t size;
uint32_t timeout[RTE_SWX_TABLE_LEARNER_N_KEY_TIMEOUTS_MAX];
uint32_t n_timeouts;
diff --git a/lib/pipeline/rte_swx_pipeline_spec.c b/lib/pipeline/rte_swx_pipeline_spec.c
index e9fde4f241..9116f38ed2 100644
--- a/lib/pipeline/rte_swx_pipeline_spec.c
+++ b/lib/pipeline/rte_swx_pipeline_spec.c
@@ -1350,7 +1350,7 @@ selector_block_parse(struct selector_spec *s,
static void
learner_spec_free(struct learner_spec *s)
{
- uintptr_t default_action_name, default_action_args;
+ uintptr_t default_action_name, default_action_args, hash_func_name;
uint32_t i;
if (!s)
@@ -1397,6 +1397,10 @@ learner_spec_free(struct learner_spec *s)
s->params.default_action_is_const = 0;
+ hash_func_name = (uintptr_t)s->params.hash_func_name;
+ free((void *)hash_func_name);
+ s->params.hash_func_name = NULL;
+
s->size = 0;
free(s->timeout);
@@ -1853,6 +1857,35 @@ learner_block_parse(struct learner_spec *s,
err_line,
err_msg);
+ if (!strcmp(tokens[0], "hash")) {
+ if (n_tokens != 2) {
+ if (err_line)
+ *err_line = n_lines;
+ if (err_msg)
+ *err_msg = "Invalid hash statement.";
+ return -EINVAL;
+ }
+
+ if (s->params.hash_func_name) {
+ if (err_line)
+ *err_line = n_lines;
+ if (err_msg)
+ *err_msg = "Duplicate hash statement.";
+ return -EINVAL;
+ }
+
+ s->params.hash_func_name = strdup(tokens[1]);
+ if (!s->params.hash_func_name) {
+ if (err_line)
+ *err_line = n_lines;
+ if (err_msg)
+ *err_msg = "Memory allocation failed.";
+ return -ENOMEM;
+ }
+
+ return 0;
+ }
+
if (!strcmp(tokens[0], "size")) {
char *p = tokens[1];
@@ -2692,6 +2725,12 @@ pipeline_spec_codegen(FILE *f,
fprintf(f, "\t\t\t.default_action_is_const = %d,\n",
learner_spec->params.default_action_is_const);
+ if (learner_spec->params.hash_func_name)
+ fprintf(f, "\t\t\t.hash_func_name = \"%s\",\n",
+ learner_spec->params.hash_func_name);
+ else
+ fprintf(f, "\t\t\t.hash_func_name = NULL,\n");
+
fprintf(f, "\t\t},\n");
fprintf(f, "\t\t.size = %u,\n", learner_spec->size);
diff --git a/lib/pipeline/rte_swx_pipeline_spec.h b/lib/pipeline/rte_swx_pipeline_spec.h
index dbe1b40adc..123e175f8b 100644
--- a/lib/pipeline/rte_swx_pipeline_spec.h
+++ b/lib/pipeline/rte_swx_pipeline_spec.h
@@ -134,6 +134,7 @@ struct selector_spec {
* ...
* }
* default_action ACTION_NAME args none | ARG0_NAME ARG0_VALUE ... [ const ]
+ * hash HASH_FUNCTION_NAME
* size SIZE
* timeout {
* TIMEOUT_IN_SECONDS
--
2.34.1
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [PATCH V2 0/6] pipeline: make the hash function configurable per table
2022-08-19 19:52 ` [PATCH V2 0/6] pipeline: make the hash function configurable per table Cristian Dumitrescu
` (5 preceding siblings ...)
2022-08-19 19:52 ` [PATCH V2 6/6] pipeline: " Cristian Dumitrescu
@ 2022-08-31 16:23 ` Stephen Hemminger
2022-09-01 8:11 ` Morten Brørup
2022-09-23 15:58 ` Thomas Monjalon
7 siblings, 1 reply; 17+ messages in thread
From: Stephen Hemminger @ 2022-08-31 16:23 UTC (permalink / raw)
To: Cristian Dumitrescu; +Cc: dev
On Fri, 19 Aug 2022 19:52:19 +0000
Cristian Dumitrescu <cristian.dumitrescu@intel.com> wrote:
> Also, since this flexibility has some performance cost, this patch set
> also introduces key comparison functions specialized for each key size
> value. Since the key size is fixed for each table, the key comparison
> function can be selected at initialization as opposed to using a
> generic function that can handle any key size. This strategy result in
> a performance improvement for the table lookup operation of around 5%.
I wonder if DPDK should start to adopt the Linux kernel optimizations
around indirect calls. For most all cases, the function pointer will be
a certain value and the cpu can do direct rather than indirect call.
As in:
if (likely(hash_func == crc32_hash))
crc32_hash(x, y)
else
(*hash_func)(x, y)
This was done in Linux kernel because of the overhead of the Spectre/Meltdown
mitigation's, but could apply more generally in DPDK.
^ permalink raw reply [flat|nested] 17+ messages in thread
* RE: [PATCH V2 0/6] pipeline: make the hash function configurable per table
2022-08-31 16:23 ` [PATCH V2 0/6] pipeline: make the hash function configurable per table Stephen Hemminger
@ 2022-09-01 8:11 ` Morten Brørup
0 siblings, 0 replies; 17+ messages in thread
From: Morten Brørup @ 2022-09-01 8:11 UTC (permalink / raw)
To: Stephen Hemminger, Cristian Dumitrescu; +Cc: dev
> From: Stephen Hemminger [mailto:stephen@networkplumber.org]
> Sent: Wednesday, 31 August 2022 18.23
> Subject: Re: [PATCH V2 0/6] pipeline: make the hash function
> configurable per table
>
> On Fri, 19 Aug 2022 19:52:19 +0000
> Cristian Dumitrescu <cristian.dumitrescu@intel.com> wrote:
>
> > Also, since this flexibility has some performance cost, this patch
> set
> > also introduces key comparison functions specialized for each key
> size
> > value. Since the key size is fixed for each table, the key comparison
> > function can be selected at initialization as opposed to using a
> > generic function that can handle any key size. This strategy result
> in
> > a performance improvement for the table lookup operation of around
> 5%.
>
> I wonder if DPDK should start to adopt the Linux kernel optimizations
> around indirect calls. For most all cases, the function pointer will be
> a certain value and the cpu can do direct rather than indirect call.
>
> As in:
>
> if (likely(hash_func == crc32_hash))
> crc32_hash(x, y)
> else
> (*hash_func)(x, y)
>
> This was done in Linux kernel because of the overhead of the
> Spectre/Meltdown
> mitigation's, but could apply more generally in DPDK.
+1 to that!
Along the very same lines, I remember reading on LWN about the Linux kernel using some magic to avoid function pointers, or to install optimized functions: At locations in the code where multiple variants of a function could be used, the address of the correct/optimized function is written directly into those locations in the code at startup. I didn't read the article in depth back then, and I can't find it now. Perhaps you know what I'm referring to, Stephen? I wonder if that also might be relevant for DPDK.
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [PATCH V2 0/6] pipeline: make the hash function configurable per table
2022-08-19 19:52 ` [PATCH V2 0/6] pipeline: make the hash function configurable per table Cristian Dumitrescu
` (6 preceding siblings ...)
2022-08-31 16:23 ` [PATCH V2 0/6] pipeline: make the hash function configurable per table Stephen Hemminger
@ 2022-09-23 15:58 ` Thomas Monjalon
7 siblings, 0 replies; 17+ messages in thread
From: Thomas Monjalon @ 2022-09-23 15:58 UTC (permalink / raw)
To: Cristian Dumitrescu; +Cc: dev
19/08/2022 21:52, Cristian Dumitrescu:
> The exact match and learner tables use a hash function for the lookup
> operation. This patch set makes the hash function configurable and
> removes some limitations.
>
> The hash function previously used by these table types had the
> following limitations:
> a) Not configurable: An internally hardcoded version was used;
> b) Mask-based: This prevents using most of the available
> hash functions, as they are not mask-based;
> c) Key size limited to 64 bytes or less.
>
> The new hash function is:
> a) Configurable;
> b) Not mask-based;
> c) Not limited to key sizes to less than or equal to 64 bytes.
>
> Also, since this flexibility has some performance cost, this patch set
> also introduces key comparison functions specialized for each key size
> value. Since the key size is fixed for each table, the key comparison
> function can be selected at initialization as opposed to using a
> generic function that can handle any key size. This strategy result in
> a performance improvement for the table lookup operation of around 5%.
>
> Depends-on: series-24117 ("pipeline: pipeline configuration and build improvements")
>
> Change log:
>
> V2:
> -Added check for table match fields to be contiguous for exact match tables.
> -Fixed bug in the specification file parsing related to hash function configuration.
>
> Cristian Dumitrescu (6):
> table: add hash function prototype
> table: add key comparison functions
> table: configure the hash function for regular tables
> pipeline: configure the hash function for regular tables
> table: configure the hash function for learner tables
> pipeline: configure the hash function for learner tables
Applied, thanks.
^ permalink raw reply [flat|nested] 17+ messages in thread
end of thread, other threads:[~2022-09-23 15:58 UTC | newest]
Thread overview: 17+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-08-18 11:44 [PATCH 0/6] pipeline: make the hash function configurable per table Cristian Dumitrescu
2022-08-18 11:44 ` [PATCH 1/6] table: add hash function prototype Cristian Dumitrescu
2022-08-18 11:44 ` [PATCH 2/6] table: add key comparison functions Cristian Dumitrescu
2022-08-18 11:44 ` [PATCH 3/6] table: configure the hash function for regular tables Cristian Dumitrescu
2022-08-18 11:44 ` [PATCH 4/6] pipeline: " Cristian Dumitrescu
2022-08-18 11:44 ` [PATCH 5/6] table: configure the hash function for learner tables Cristian Dumitrescu
2022-08-18 11:44 ` [PATCH 6/6] pipeline: " Cristian Dumitrescu
2022-08-19 19:52 ` [PATCH V2 0/6] pipeline: make the hash function configurable per table Cristian Dumitrescu
2022-08-19 19:52 ` [PATCH V2 1/6] table: add hash function prototype Cristian Dumitrescu
2022-08-19 19:52 ` [PATCH V2 2/6] table: add key comparison functions Cristian Dumitrescu
2022-08-19 19:52 ` [PATCH V2 3/6] table: configure the hash function for regular tables Cristian Dumitrescu
2022-08-19 19:52 ` [PATCH V2 4/6] pipeline: " Cristian Dumitrescu
2022-08-19 19:52 ` [PATCH V2 5/6] table: configure the hash function for learner tables Cristian Dumitrescu
2022-08-19 19:52 ` [PATCH V2 6/6] pipeline: " Cristian Dumitrescu
2022-08-31 16:23 ` [PATCH V2 0/6] pipeline: make the hash function configurable per table Stephen Hemminger
2022-09-01 8:11 ` Morten Brørup
2022-09-23 15:58 ` Thomas Monjalon
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).