DPDK patches and discussions
 help / color / mirror / Atom feed
From: "Wang, Yipeng1" <yipeng1.wang@intel.com>
To: "Medvedkin, Vladimir" <vladimir.medvedkin@intel.com>,
	"dev@dpdk.org" <dev@dpdk.org>
Cc: "Ananyev, Konstantin" <konstantin.ananyev@intel.com>,
	"Chilikin, Andrey" <andrey.chilikin@intel.com>,
	"Kinsella, Ray" <ray.kinsella@intel.com>,
	"Gobriel, Sameh" <sameh.gobriel@intel.com>,
	"Richardson, Bruce" <bruce.richardson@intel.com>,
	Stephen Hemminger <stephen@networkplumber.org>
Subject: Re: [dpdk-dev] [PATCH v2 1/3] hash: add predictable RSS API
Date: Sat, 10 Apr 2021 00:05:01 +0000
Message-ID: <BYAPR11MB3494EDE3E8CBE25EF4CF4D5AC3729@BYAPR11MB3494.namprd11.prod.outlook.com> (raw)
In-Reply-To: <1617738643-258635-2-git-send-email-vladimir.medvedkin@intel.com>

> -----Original Message-----
> From: Medvedkin, Vladimir <vladimir.medvedkin@intel.com>
> Sent: Tuesday, April 6, 2021 12:51 PM
> To: dev@dpdk.org
> Cc: Ananyev, Konstantin <konstantin.ananyev@intel.com>; Chilikin, Andrey
> <andrey.chilikin@intel.com>; Kinsella, Ray <ray.kinsella@intel.com>; Wang,
> Yipeng1 <yipeng1.wang@intel.com>; Gobriel, Sameh
> <sameh.gobriel@intel.com>; Richardson, Bruce
> <bruce.richardson@intel.com>
> 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 <vladimir.medvedkin@intel.com>
> ---
>  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 <rte_thash.h>
> +#include <rte_tailq.h>
> +#include <rte_random.h>
> +#include <rte_memcpy.h>
> +#include <rte_errno.h>
> +#include <rte_eal.h>
> +#include <rte_eal_memconfig.h>
> +#include <rte_malloc.h>
> +
> +#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 <medvedkinv@gmail.com>
> + * 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
> +*/
[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?
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?

For the second flag: is it always good to keep it minimum for each helper?

The goal is to have the best default values for user who do not understand the algorithm details.
Less flags is usually better.

> +#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
[Wang, Yipeng] Key will be modified by helper anyway. What is the reason of having
the users to specify the key here?

> + *  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
[Wang, Yipeng] 
Add requirement here so user know the expectation.
e.g. Len should be no shorter than log(reta_size).

> + *  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.

> +__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?

> + * partial toeplitz hash collision. It muxt be XOR'ed with the
[Wang, Yipeng] typo *must be
> + * 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


  reply	other threads:[~2021-04-10  0:05 UTC|newest]

Thread overview: 45+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-03-16 18:24 [dpdk-dev] [PATCH v1 0/3] Predictable RSS feature Vladimir Medvedkin
2021-03-16 18:24 ` [dpdk-dev] [PATCH v1 1/3] hash: add predictable RSS API Vladimir Medvedkin
2021-03-16 18:24 ` [dpdk-dev] [PATCH v1 2/3] hash: add predictable RSS implementation Vladimir Medvedkin
2021-03-16 18:24 ` [dpdk-dev] [PATCH v1 3/3] test/hash: add additional thash tests Vladimir Medvedkin
2021-04-06 19:50 ` [dpdk-dev] [PATCH v2 0/3] Predictable RSS feature Vladimir Medvedkin
2021-04-08 15:56   ` Stephen Hemminger
2021-04-11 18:51     ` Medvedkin, Vladimir
2021-04-10  0:32   ` Wang, Yipeng1
2021-04-11 18:51     ` Medvedkin, Vladimir
2021-04-11 19:11   ` [dpdk-dev] [PATCH v3 " Vladimir Medvedkin
2021-04-13 13:19     ` [dpdk-dev] [PATCH v4 " Vladimir Medvedkin
2021-04-14 18:04       ` Wang, Yipeng1
2021-04-15  8:29         ` David Marchand
2021-04-19 15:59       ` [dpdk-dev] [PATCH v5 0/5] " Vladimir Medvedkin
2021-04-20 21:31         ` Thomas Monjalon
2021-04-19 15:59       ` [dpdk-dev] [PATCH v5 1/5] hash: add predictable RSS API Vladimir Medvedkin
2021-04-19 15:59       ` [dpdk-dev] [PATCH v5 2/5] hash: add predictable RSS implementation Vladimir Medvedkin
2021-04-19 15:59       ` [dpdk-dev] [PATCH v5 3/5] test/hash: add additional thash tests Vladimir Medvedkin
2021-04-29  9:13         ` David Marchand
2021-04-29  9:17           ` Medvedkin, Vladimir
2021-04-29 18:45             ` Stanislaw Kardach
2021-05-04 14:06               ` Medvedkin, Vladimir
2021-04-19 15:59       ` [dpdk-dev] [PATCH v5 4/5] doc: add thash documentation Vladimir Medvedkin
2021-04-20 11:25         ` Mcnamara, John
2021-04-19 15:59       ` [dpdk-dev] [PATCH v5 5/5] maintainers: claim maintainership of the hash library Vladimir Medvedkin
2021-04-13 13:19     ` [dpdk-dev] [PATCH v4 1/3] hash: add predictable RSS API Vladimir Medvedkin
2021-04-14 17:06       ` Wang, Yipeng1
2021-04-13 13:19     ` [dpdk-dev] [PATCH v4 2/3] hash: add predictable RSS implementation Vladimir Medvedkin
2021-04-14 17:51       ` Wang, Yipeng1
2021-04-13 13:19     ` [dpdk-dev] [PATCH v4 3/3] test/hash: add additional thash tests Vladimir Medvedkin
2021-04-14 17:56       ` Wang, Yipeng1
2021-04-11 19:11   ` [dpdk-dev] [PATCH v3 1/3] hash: add predictable RSS API Vladimir Medvedkin
2021-04-11 19:11   ` [dpdk-dev] [PATCH v3 2/3] hash: add predictable RSS implementation Vladimir Medvedkin
2021-04-11 19:11   ` [dpdk-dev] [PATCH v3 3/3] test/hash: add additional thash tests Vladimir Medvedkin
2021-04-06 19:50 ` [dpdk-dev] [PATCH v2 1/3] hash: add predictable RSS API Vladimir Medvedkin
2021-04-10  0:05   ` Wang, Yipeng1 [this message]
2021-04-11 18:52     ` Medvedkin, Vladimir
2021-04-06 19:50 ` [dpdk-dev] [PATCH v2 2/3] hash: add predictable RSS implementation Vladimir Medvedkin
2021-04-07 12:53   ` Ananyev, Konstantin
2021-04-11 18:51     ` Medvedkin, Vladimir
2021-04-12  9:47       ` Ananyev, Konstantin
2021-04-13 12:28         ` Medvedkin, Vladimir
2021-04-10  0:10   ` Wang, Yipeng1
2021-04-11 18:52     ` Medvedkin, Vladimir
2021-04-06 19:50 ` [dpdk-dev] [PATCH v2 3/3] test/hash: add additional thash tests Vladimir Medvedkin

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=BYAPR11MB3494EDE3E8CBE25EF4CF4D5AC3729@BYAPR11MB3494.namprd11.prod.outlook.com \
    --to=yipeng1.wang@intel.com \
    --cc=andrey.chilikin@intel.com \
    --cc=bruce.richardson@intel.com \
    --cc=dev@dpdk.org \
    --cc=konstantin.ananyev@intel.com \
    --cc=ray.kinsella@intel.com \
    --cc=sameh.gobriel@intel.com \
    --cc=stephen@networkplumber.org \
    --cc=vladimir.medvedkin@intel.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

DPDK patches and discussions

This inbox may be cloned and mirrored by anyone:

	git clone --mirror https://inbox.dpdk.org/dev/0 dev/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 dev dev/ https://inbox.dpdk.org/dev \
		dev@dpdk.org
	public-inbox-index dev

Example config snippet for mirrors.
Newsgroup available over NNTP:
	nntp://inbox.dpdk.org/inbox.dpdk.dev


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git