Hi,
> -----Original Message-----
> From: Suanming Mou <suanmi...@mellanox.com>
> Sent: Friday, July 31, 2020 6:34 AM
> To: Slava Ovsiienko <viachesl...@mellanox.com>; Matan Azrad
> <ma...@mellanox.com>
> Cc: Raslan Darawsheh <rasl...@mellanox.com>; dev@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 <suanmi...@mellanox.com>
> Acked-by: Viacheslav Ovsiienko <viachesl...@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
