diff mbox series

[1/2] net/mlx5: add hash list extended lookup and insert

Message ID 1596166458-150683-2-git-send-email-suanmingm@mellanox.com (mailing list archive)
State Accepted, archived
Delegated to: Raslan Darawsheh
Headers
Series net/mlx5: manage modify actions with hashed list |

Checks

Context Check Description
ci/checkpatch success coding style OK
ci/iol-intel-Performance success Performance Testing PASS
ci/Intel-compilation success Compilation OK
ci/iol-testing success Testing PASS
ci/iol-mellanox-Performance success Performance Testing PASS

Commit Message

Suanming Mou July 31, 2020, 3:34 a.m. UTC 
  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@mellanox.com>
Acked-by: Viacheslav Ovsiienko <viacheslavo@mellanox.com>
---
 drivers/net/mlx5/mlx5_utils.c | 38 +++++++++++++++++++++++++++++
 drivers/net/mlx5/mlx5_utils.h | 57 +++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 95 insertions(+)

Comments

Raslan Darawsheh Aug. 23, 2020, 7:14 a.m. UTC | #1 
Hi,

> -----Original Message-----
> From: Suanming Mou <suanmingm@mellanox.com>
> Sent: Friday, July 31, 2020 6:34 AM
> To: Slava Ovsiienko <viacheslavo@mellanox.com>; Matan Azrad
> <matan@mellanox.com>
> Cc: Raslan Darawsheh <rasland@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 <suanmingm@mellanox.com>
> Acked-by: Viacheslav Ovsiienko <viacheslavo@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
diff mbox series

Patch

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