From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id A6122A0524; Sun, 11 Apr 2021 20:52:27 +0200 (CEST) Received: from [217.70.189.124] (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 8D8DA141429; Sun, 11 Apr 2021 20:52:27 +0200 (CEST) Received: from mga05.intel.com (mga05.intel.com [192.55.52.43]) by mails.dpdk.org (Postfix) with ESMTP id BFD531413EF for ; Sun, 11 Apr 2021 20:52:26 +0200 (CEST) IronPort-SDR: aWWSmFVdBM5uOTKM+3NP7xULBj/LMEoVOfiT989s1BbkNv2gohKFKZ06A/7qNLT0iPbatEevxH hd/AJaQd/K2A== X-IronPort-AV: E=McAfee;i="6000,8403,9951"; a="279353431" X-IronPort-AV: E=Sophos;i="5.82,214,1613462400"; d="scan'208";a="279353431" Received: from orsmga002.jf.intel.com ([10.7.209.21]) by fmsmga105.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 11 Apr 2021 11:52:25 -0700 IronPort-SDR: 9onD5VZVAGxztt/fgiiZo2nmTlHlMmjoGKBY3sR3jfdjz3e+Xqm7u1ufwVaBqI3OOPCijHyufu xM9ZD43mQbvg== X-IronPort-AV: E=Sophos;i="5.82,214,1613462400"; d="scan'208";a="398117584" Received: from vmedvedk-mobl.ger.corp.intel.com (HELO [10.252.4.10]) ([10.252.4.10]) by orsmga002-auth.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 11 Apr 2021 11:52:23 -0700 To: "Wang, Yipeng1" , "dev@dpdk.org" Cc: "Ananyev, Konstantin" , "Chilikin, Andrey" , "Kinsella, Ray" , "Gobriel, Sameh" , "Richardson, Bruce" , Stephen Hemminger References: <1615919077-77774-1-git-send-email-vladimir.medvedkin@intel.com> <1617738643-258635-2-git-send-email-vladimir.medvedkin@intel.com> From: "Medvedkin, Vladimir" Message-ID: <4a669605-8eaf-b57f-ba42-29c3366e61e3@intel.com> Date: Sun, 11 Apr 2021 21:52:21 +0300 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.9.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-US Content-Transfer-Encoding: 7bit Subject: Re: [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" On 10/04/2021 03:05, Wang, Yipeng1 wrote: >> -----Original Message----- >> From: Medvedkin, Vladimir >> Sent: Tuesday, April 6, 2021 12:51 PM >> To: dev@dpdk.org >> Cc: Ananyev, Konstantin ; Chilikin, Andrey >> ; Kinsella, Ray ; Wang, >> Yipeng1 ; Gobriel, Sameh >> ; Richardson, Bruce >> >> Subject: [PATCH v2 1/3] hash: add predictable RSS API >> >> 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 >> >> + * LFSR will ignore if generated m-sequence has more than 2^n -1 bits >> +*/ > [Wang, Yipeng] > I haven't fully got the significance/reasons behind the two flags. > For the comment above, 2^n is the reta_size right? Here "2^n - 1" is a length of m-sequence - a pseudorandom bit sequence which has a number of mathematical properties we need. > If so, it is better than commenting 2^n. > > For the first flag: > What would be the issue for overflow? I understand that multiple helpers may overlap > on the m-sequence, but since they are for different tuples, what would be the issue? > M-sequence has a period and after (2^n - 1) bits it the sequence it repeats. Eventually it is written to the rss hash key. In some circumstances an attack with spoofed packets can be made to overflow particular NIC queue. So generally this flag should be used for tests, for example to spread evenly traffic from the packet generator among the queues. > For the second flag: is it always good to keep it minimum for each helper? > Not always, without this flag an m-sequence till be generated for all variable bits, for example for 16 bits of port. And if we know that all values of this 16-bit port are equally probable then the distribution of the hash LSB's will be even. On the other hand, if the user have a number of helpers which shares a single m-sequence, then there could be an overflow. And having this flag could break a single m-sequence with two independent. > The goal is to have the best default values for user who do not understand the algorithm details. > Less flags is usually better. > I think the default value of 0 for flags is the best general use case. >> +#define RTE_THASH_IGNORE_PERIOD_OVERFLOW0x1 >> +/** >> + * Generate minimal required bit (equal to ReTa LSB) sequence into >> + * the hash_key >> + */ >> +#define RTE_THASH_MINIMAL_SEQ0x2 >> + >> +/** @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 > [Wang, Yipeng] Key will be modified by helper anyway. What is the reason of having > the users to specify the key here? > In some cases user will want to specify particular key. For example, if user wants to symmetrically load balance ipv4/tcp and do the NAT inside the tunnel without decapsulation, user will submit key with repeated 2-byte values. >> + * 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); >> + >> +/** >> + * 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 > [Wang, Yipeng] > Add requirement here so user know the expectation. > e.g. Len should be no shorter than log(reta_size). > Agree, I'll add >> + * length in bits of the target subtuple >> + * @param offset >> + * offset in bits of the subtuple >> + * @return >> + * 0 on success >> + * negative on error >> + */ > [Wang, Yipeng] thread-safety for the APIs? > Better to add thread-safety info in the comments. > Agree, I'll add >> +__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 > [Wang, Yipeng] > Should it be complimentary->complementary? compliment -> complement? > Agree, will fix >> + * partial toeplitz hash collision. It muxt be XOR'ed with the > [Wang, Yipeng] typo *must be will fix >> + * 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; >> }; >> -- >> 2.7.4 > -- Regards, Vladimir