From patchwork Tue Mar 16 18:24:35 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 89259 X-Patchwork-Delegate: david.marchand@redhat.com Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id 51598A054F; Tue, 16 Mar 2021 19:24:56 +0100 (CET) Received: from [217.70.189.124] (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 26A5424295A; Tue, 16 Mar 2021 19:24:51 +0100 (CET) Received: from mga07.intel.com (mga07.intel.com [134.134.136.100]) by mails.dpdk.org (Postfix) with ESMTP id 69A984069F for ; Tue, 16 Mar 2021 19:24:49 +0100 (CET) IronPort-SDR: HT8CqRqxz8ejiISlNBs7F2p6P3E8fjSyxmBog6Or3p8N+HWN9u/uiodCpUIpg+jCgPEggYxMKK llqXiFTLYwJg== X-IronPort-AV: E=McAfee;i="6000,8403,9925"; a="253329736" X-IronPort-AV: E=Sophos;i="5.81,254,1610438400"; d="scan'208";a="253329736" Received: from orsmga007.jf.intel.com ([10.7.209.58]) by orsmga105.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 16 Mar 2021 11:24:49 -0700 IronPort-SDR: raKAEkRwwiLgoE6ba8GF4j+F1cncPR/WvxLJDs8F7u7hrdoQ6+cMDkeYrriEpks1YXT7IRy7N7 eOhXnqxWC25w== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.81,254,1610438400"; d="scan'208";a="411155910" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by orsmga007.jf.intel.com with ESMTP; 16 Mar 2021 11:24:47 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: konstantin.ananyev@intel.com, andrey.chilikin@intel.com, ray.kinsella@intel.com, yipeng1.wang@intel.com, sameh.gobriel@intel.com, bruce.richardson@intel.com Date: Tue, 16 Mar 2021 18:24:35 +0000 Message-Id: <1615919077-77774-2-git-send-email-vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1615919077-77774-1-git-send-email-vladimir.medvedkin@intel.com> References: <1615919077-77774-1-git-send-email-vladimir.medvedkin@intel.com> Subject: [dpdk-dev] [PATCH v1 1/3] hash: add predictable RSS API X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" This patch adds predictable RSS API. It is based on the idea of searching partial Toeplitz hash collisions. Signed-off-by: Vladimir Medvedkin --- lib/librte_hash/meson.build | 3 +- lib/librte_hash/rte_thash.c | 96 ++++++++++++++++++++++++++++++ lib/librte_hash/rte_thash.h | 138 ++++++++++++++++++++++++++++++++++++++++++++ lib/librte_hash/version.map | 7 +++ 4 files changed, 243 insertions(+), 1 deletion(-) create mode 100644 lib/librte_hash/rte_thash.c diff --git a/lib/librte_hash/meson.build b/lib/librte_hash/meson.build index 242859f..3546014 100644 --- a/lib/librte_hash/meson.build +++ b/lib/librte_hash/meson.build @@ -8,6 +8,7 @@ headers = files('rte_fbk_hash.h', 'rte_thash.h') indirect_headers += files('rte_crc_arm64.h') -sources = files('rte_cuckoo_hash.c', 'rte_fbk_hash.c') +sources = files('rte_cuckoo_hash.c', 'rte_fbk_hash.c', 'rte_thash.c') +deps += ['net'] deps += ['ring'] deps += ['rcu'] diff --git a/lib/librte_hash/rte_thash.c b/lib/librte_hash/rte_thash.c new file mode 100644 index 0000000..79e8724 --- /dev/null +++ b/lib/librte_hash/rte_thash.c @@ -0,0 +1,96 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2021 Intel Corporation + */ + +#include +#include +#include +#include +#include +#include +#include +#include + +#define THASH_NAME_LEN 64 + +struct thash_lfsr { + uint32_t ref_cnt; + uint32_t poly; + /**< polynomial associated with the lfsr */ + uint32_t rev_poly; + /**< polynomial to generate the sequence in reverse direction */ + uint32_t state; + /**< current state of the lfsr */ + uint32_t rev_state; + /**< current state of the lfsr for reverse direction */ + uint32_t deg; /**< polynomial degree*/ + uint32_t bits_cnt; /**< number of bits generated by lfsr*/ +}; + +struct rte_thash_subtuple_helper { + char name[THASH_NAME_LEN]; /** < Name of subtuple configuration */ + LIST_ENTRY(rte_thash_subtuple_helper) next; + struct thash_lfsr *lfsr; + uint32_t offset; /** < Offset in bits of the subtuple */ + uint32_t len; /** < Length in bits of the subtuple */ + uint32_t lsb_msk; /** < (1 << reta_sz_log) - 1 */ + __extension__ uint32_t compl_table[0] __rte_cache_aligned; + /** < Complimentary table */ +}; + +struct rte_thash_ctx { + char name[THASH_NAME_LEN]; + LIST_HEAD(, rte_thash_subtuple_helper) head; + uint32_t key_len; /** < Length of the NIC RSS hash key */ + uint32_t reta_sz_log; /** < size of the RSS ReTa in bits */ + uint32_t subtuples_nb; /** < number of subtuples */ + uint32_t flags; + uint8_t hash_key[0]; +}; + +struct rte_thash_ctx * +rte_thash_init_ctx(const char *name __rte_unused, + uint32_t key_len __rte_unused, uint32_t reta_sz __rte_unused, + uint8_t *key __rte_unused, uint32_t flags __rte_unused) +{ + return NULL; +} + +struct rte_thash_ctx * +rte_thash_find_existing(const char *name __rte_unused) +{ + return NULL; +} + +void +rte_thash_free_ctx(struct rte_thash_ctx *ctx __rte_unused) +{ +} + +int +rte_thash_add_helper(struct rte_thash_ctx *ctx __rte_unused, + const char *name __rte_unused, uint32_t len __rte_unused, + uint32_t offset __rte_unused) +{ + return 0; +} + +struct rte_thash_subtuple_helper * +rte_thash_get_helper(struct rte_thash_ctx *ctx __rte_unused, + const char *name __rte_unused) +{ + return NULL; +} + +uint32_t +rte_thash_get_compliment(struct rte_thash_subtuple_helper *h __rte_unused, + uint32_t hash __rte_unused, uint32_t desired_hash __rte_unused) +{ + return 0; +} + +const uint8_t * +rte_thash_get_key(struct rte_thash_ctx *ctx __rte_unused) +{ + return NULL; +} diff --git a/lib/librte_hash/rte_thash.h b/lib/librte_hash/rte_thash.h index 061efa2..b30a85c 100644 --- a/lib/librte_hash/rte_thash.h +++ b/lib/librte_hash/rte_thash.h @@ -1,5 +1,6 @@ /* SPDX-License-Identifier: BSD-3-Clause * Copyright(c) 2015-2019 Vladimir Medvedkin + * Copyright(c) 2021 Intel Corporation */ #ifndef _RTE_THASH_H @@ -222,6 +223,143 @@ rte_softrss_be(uint32_t *input_tuple, uint32_t input_len, return ret; } +/** + * LFSR will ignore if generated m-seqence has more than 2^n -1 bits + */ +#define RTE_THASH_IGNORE_PERIOD_OVERFLOW 0x1 +/** + * Generate minimal required bit (equal to ReTa LSB) sequence into + * the hash_key + */ +#define RTE_THASH_MINIMAL_SEQ 0x2 + +/** @internal thash context structure. */ +struct rte_thash_ctx; +/** @internal thash helper structure. */ +struct rte_thash_subtuple_helper; + +/** + * Create a new thash context. + * + * @param name + * context name + * @param key_len + * length of the toeplitz hash key + * @param reta_sz + * logarithm of the NIC's Redirection Table (ReTa) size, + * i.e. number of the LSBs if the hash used to determine + * the reta entry. + * @param key + * pointer to the key used to init an internal key state. + * Could be NULL, in this case internal key will be inited with random. + * @param flags + * supported flags are: + * RTE_THASH_IGNORE_PERIOD_OVERFLOW + * RTE_THASH_MINIMAL_SEQ + * @return + * A pointer to the created context on success + * NULL otherwise + */ +__rte_experimental +struct rte_thash_ctx * +rte_thash_init_ctx(const char *name, uint32_t key_len, uint32_t reta_sz, + uint8_t *key, uint32_t flags); + +/** + * Find an existing thash context and return a pointer to it. + * + * @param name + * Name of the thash context + * @return + * Pointer to the thash context or NULL if it was not found with rte_errno + * set appropriately. Possible rte_errno values include: + * - ENOENT - required entry not available to return. + */ +__rte_experimental +struct rte_thash_ctx * +rte_thash_find_existing(const char *name); + +/** + * Free a thash context object + * + * @param ctx + * thash context + * @return + * None + */ +__rte_experimental +void +rte_thash_free_ctx(struct rte_thash_ctx *ctx); + +/** + * Add a special properties to the toeplitz hash key inside a thash context. + * Creates an internal helper struct which has a complimentary table + * to calculate toeplitz hash collisions. + * + * @param ctx + * thash context + * @param name + * name of the helper + * @param len + * length in bits of the target subtuple + * @param offset + * offset in bits of the subtuple + * @return + * 0 on success + * negative on error + */ +__rte_experimental +int +rte_thash_add_helper(struct rte_thash_ctx *ctx, const char *name, uint32_t len, + uint32_t offset); + +/** + * Find a helper in the context by the given name + * + * @param ctx + * thash context + * @param name + * name of the helper + * @return + * Pointer to the thash helper or NULL if it was not found. + */ +__rte_experimental +struct rte_thash_subtuple_helper * +rte_thash_get_helper(struct rte_thash_ctx *ctx, const char *name); + +/** + * Get a complimentary value for the subtuple to produce a + * partial toeplitz hash collision. It muxt be XOR'ed with the + * subtuple to produce the hash value with the desired hash LSB's + * + * @param h + * Pointer to the helper struct + * @param hash + * toeplitz hash value calculated for the given tuple + * @param desired_hash + * desired hash value to find a collision for + * @return + * A complimentary value which must be xored with the corresponding subtuple + */ +__rte_experimental +uint32_t +rte_thash_get_compliment(struct rte_thash_subtuple_helper *h, + uint32_t hash, uint32_t desired_hash); + +/** + * Get a pointer to the toeplitz hash contained in the context. + * It changes after each addition of a helper. It should be installed to + * the NIC. + * + * @param ctx + * thash context + * @return + * A pointer to the toeplitz hash key + */ +__rte_experimental +const uint8_t * +rte_thash_get_key(struct rte_thash_ctx *ctx); + #ifdef __cplusplus } #endif diff --git a/lib/librte_hash/version.map b/lib/librte_hash/version.map index c6d7308..93cb230 100644 --- a/lib/librte_hash/version.map +++ b/lib/librte_hash/version.map @@ -37,4 +37,11 @@ EXPERIMENTAL { rte_hash_lookup_with_hash_bulk_data; rte_hash_max_key_id; rte_hash_rcu_qsbr_add; + rte_thash_add_helper; + rte_thash_find_existing; + rte_thash_free_ctx; + rte_thash_get_compliment; + rte_thash_get_helper; + rte_thash_get_key; + rte_thash_init_ctx; };