[dpdk-dev] [PATCH 1/2] net/mlx5: add hash list extended lookup and insert

[Raslan Darawsheh]

Hi,

> -----Original Message-----
> From: Suanming Mou <suanmingm at mellanox.com>
> Sent: Friday, July 31, 2020 6:34 AM
> To: Slava Ovsiienko <viacheslavo at mellanox.com>; Matan Azrad
> <matan at mellanox.com>
> Cc: Raslan Darawsheh <rasland at mellanox.com>; dev at dpdk.org
> Subject: [PATCH 1/2] net/mlx5: add hash list extended lookup and insert
> 
> The mlx5 PMD hashed list was designed in approach to contain the items
> with unique keys only. Now there is the need to store the objects with
> possible key collisions. It is not expected to have many collisions
> (very likely to have a few ones), but keys become not unique.
> 
> This commit adds the hash list extended functions in order to support
> insertion and lookup for the lists with non-unique keys.
> 
> Signed-off-by: Suanming Mou <suanmingm at mellanox.com>
> Acked-by: Viacheslav Ovsiienko <viacheslavo at mellanox.com>
> ---
>  drivers/net/mlx5/mlx5_utils.c | 38 +++++++++++++++++++++++++++++
>  drivers/net/mlx5/mlx5_utils.h | 57
> +++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 95 insertions(+)
> 
> diff --git a/drivers/net/mlx5/mlx5_utils.c b/drivers/net/mlx5/mlx5_utils.c
> index 25e8b27..fefe833 100644
> --- a/drivers/net/mlx5/mlx5_utils.c
> +++ b/drivers/net/mlx5/mlx5_utils.c
> @@ -81,6 +81,44 @@ struct mlx5_hlist_entry *
>  	return 0;
>  }
> 
> +struct mlx5_hlist_entry *
> +mlx5_hlist_lookup_ex(struct mlx5_hlist *h, uint64_t key,
> +		     mlx5_hlist_match_callback_fn cb, void *ctx)
> +{
> +	uint32_t idx;
> +	struct mlx5_hlist_head *first;
> +	struct mlx5_hlist_entry *node;
> +
> +	MLX5_ASSERT(h && cb && ctx);
> +	idx = rte_hash_crc_8byte(key, 0) & h->mask;
> +	first = &h->heads[idx];
> +	LIST_FOREACH(node, first, next) {
> +		if (!cb(node, ctx))
> +			return node;
> +	}
> +	return NULL;
> +}
> +
> +int
> +mlx5_hlist_insert_ex(struct mlx5_hlist *h, struct mlx5_hlist_entry *entry,
> +		     mlx5_hlist_match_callback_fn cb, void *ctx)
> +{
> +	uint32_t idx;
> +	struct mlx5_hlist_head *first;
> +	struct mlx5_hlist_entry *node;
> +
> +	MLX5_ASSERT(h && entry && cb && ctx);
> +	idx = rte_hash_crc_8byte(entry->key, 0) & h->mask;
> +	first = &h->heads[idx];
> +	/* No need to reuse the lookup function. */
> +	LIST_FOREACH(node, first, next) {
> +		if (!cb(node, ctx))
> +			return -EEXIST;
> +	}
> +	LIST_INSERT_HEAD(first, entry, next);
> +	return 0;
> +}
> +
>  void
>  mlx5_hlist_remove(struct mlx5_hlist *h __rte_unused,
>  		  struct mlx5_hlist_entry *entry)
> diff --git a/drivers/net/mlx5/mlx5_utils.h b/drivers/net/mlx5/mlx5_utils.h
> index 562b9b1..97d931f 100644
> --- a/drivers/net/mlx5/mlx5_utils.h
> +++ b/drivers/net/mlx5/mlx5_utils.h
> @@ -265,6 +265,20 @@ struct mlx5_hlist_entry {
>  /** Type of function that is used to handle the data before freeing. */
>  typedef void (*mlx5_hlist_destroy_callback_fn)(void *p, void *ctx);
> 
> +/**
> + * Type of function for user defined matching.
> + *
> + * @param entry
> + *   The entry in the list.
> + * @param ctx
> + *   The pointer to new entry context.
> + *
> + * @return
> + *   0 if matching, -1 otherwise.
> + */
> +typedef int (*mlx5_hlist_match_callback_fn)(struct mlx5_hlist_entry
> *entry,
> +					     void *ctx);
> +
>  /** hash list table structure */
>  struct mlx5_hlist {
>  	char name[MLX5_HLIST_NAMESIZE]; /**< Name of the hash list. */
> @@ -323,6 +337,49 @@ struct mlx5_hlist {
>  int mlx5_hlist_insert(struct mlx5_hlist *h, struct mlx5_hlist_entry *entry);
> 
>  /**
> + * Extended routine to search an entry matching the context with
> + * user defined match function.
> + *
> + * @param h
> + *   Pointer to the hast list table.
> + * @param key
> + *   Key for the searching entry.
> + * @param cb
> + *   Callback function to match the node with context.
> + * @param ctx
> + *   Common context parameter used by callback function.
> + *
> + * @return
> + *   Pointer of the hlist entry if found, NULL otherwise.
> + */
> +struct mlx5_hlist_entry *mlx5_hlist_lookup_ex(struct mlx5_hlist *h,
> +					      uint64_t key,
> +					      mlx5_hlist_match_callback_fn cb,
> +					      void *ctx);
> +
> +/**
> + * Extended routine to insert an entry to the list with key collisions.
> + *
> + * For the list have key collision, the extra user defined match function
> + * allows node with same key will be inserted.
> + *
> + * @param h
> + *   Pointer to the hast list table.
> + * @param entry
> + *   Entry to be inserted into the hash list table.
> + * @param cb
> + *   Callback function to match the node with context.
> + * @param ctx
> + *   Common context parameter used by callback function.
> + *
> + * @return
> + *   - zero for success.
> + *   - -EEXIST if the entry is already inserted.
> + */
> +int mlx5_hlist_insert_ex(struct mlx5_hlist *h, struct mlx5_hlist_entry
> *entry,
> +			 mlx5_hlist_match_callback_fn cb, void *ctx);
> +
> +/**
>   * Remove an entry from the hash list table. User should guarantee the
> validity
>   * of the entry.
>   *
> --
> 1.8.3.1

Series applied to next-net-mlx,

Kindest regards
Raslan Darawsheh