From patchwork Tue Apr 6 19:50:41 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 90752 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 DA3B9A0546; Tue, 6 Apr 2021 21:50:55 +0200 (CEST) Received: from [217.70.189.124] (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 4BFA8140F8E; Tue, 6 Apr 2021 21:50:52 +0200 (CEST) Received: from mga12.intel.com (mga12.intel.com [192.55.52.136]) by mails.dpdk.org (Postfix) with ESMTP id BE74D140F8B for ; Tue, 6 Apr 2021 21:50:50 +0200 (CEST) IronPort-SDR: xkxpYWI2Jr9UcQ6hd196vSa4ST57eyEskuh/vwDjnzHf5HzupghuX+Wt0s/fikTr5/KcQ2T8YO H4OeoAxG2Ziw== X-IronPort-AV: E=McAfee;i="6000,8403,9946"; a="172619767" X-IronPort-AV: E=Sophos;i="5.82,201,1613462400"; d="scan'208";a="172619767" Received: from fmsmga002.fm.intel.com ([10.253.24.26]) by fmsmga106.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 06 Apr 2021 12:50:50 -0700 IronPort-SDR: IPvSzT5mevaqBPCeuvU2eIyvMFVBngC2JW4ceVoKs9UKMx3JsvZiXKVgzLH1sM4hdFNjE7A1Gx 7qP5yYR59gfA== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.82,201,1613462400"; d="scan'208";a="448740699" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by fmsmga002.fm.intel.com with ESMTP; 06 Apr 2021 12:50:48 -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, 6 Apr 2021 20:50:41 +0100 Message-Id: <1617738643-258635-2-git-send-email-vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1617738643-258635-1-git-send-email-vladimir.medvedkin@intel.com> References: <1617738643-258635-1-git-send-email-vladimir.medvedkin@intel.com> 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 v2 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..38a641b 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-sequence 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; };