[dpdk-dev] [PATCH] net/mlx5: optimize tag traversal with hash list

[Bing Zhao <bingz@mellanox.com>]

Tag action for flow mark/flag could be reused by different flows.
When creating a new flow with mark, the existing tag resources will
be traversed in order to confirm if the action is already created.
If only one linked list is used, the searching rate will drop
significantly with the number of tag actions increasing.
By using a hash lists table, it will speed up the searching process
and in the meanwhile, the memory consumption won't be large if only
a small number tag action resources are created(compared to other
hash table implementations). The list heads array size could be
optimized with some extendable hash table in the future.

Signed-off-by: Bing Zhao <bingz@mellanox.com>
---
 drivers/net/mlx5/mlx5.c         | 20 ++++++++++++-
 drivers/net/mlx5/mlx5.h         |  2 +-
 drivers/net/mlx5/mlx5_flow.h    |  7 ++---
 drivers/net/mlx5/mlx5_flow_dv.c | 63 +++++++++++++++++++++++------------------
 4 files changed, 59 insertions(+), 33 deletions(-)

diff --git a/drivers/net/mlx5/mlx5.c b/drivers/net/mlx5/mlx5.c
index 6474c53..96d515f 100644
--- a/drivers/net/mlx5/mlx5.c
+++ b/drivers/net/mlx5/mlx5.c
@@ -185,6 +185,7 @@ struct mlx5_dev_spawn_data {
 #define MLX5_ID_GENERATION_ARRAY_FACTOR 16
 
 #define MLX5_FLOW_TABLE_HLIST_ARRAY_SIZE 4096
+#define MLX5_TAGS_HLIST_ARRAY_SIZE 8192
 
 /**
  * Allocate ID pool structure.
@@ -719,7 +720,7 @@ struct mlx5_flow_id_pool *
 		sh->esw_drop_action = mlx5_glue->dr_create_flow_action_drop();
 	}
 #endif
-	snprintf(s, sizeof(s) - 1, "%s_flow_table", priv->sh->ibdev_name);
+	snprintf(s, sizeof(s), "%s_flow_table", priv->sh->ibdev_name);
 	sh->flow_tbls = mlx5_hlist_create(s,
 					  MLX5_FLOW_TABLE_HLIST_ARRAY_SIZE);
 	if (!sh->flow_tbls) {
@@ -727,6 +728,14 @@ struct mlx5_flow_id_pool *
 		err = -ENOMEM;
 		goto error;
 	}
+	/* create tags hash list table. */
+	snprintf(s, sizeof(s), "%s_tags", priv->sh->ibdev_name);
+	sh->tag_table = mlx5_hlist_create(s, MLX5_TAGS_HLIST_ARRAY_SIZE);
+	if (!sh->flow_tbls) {
+		DRV_LOG(ERR, "tags with hash creation failed.\n");
+		err = -ENOMEM;
+		goto error;
+	}
 	sh->pop_vlan_action = mlx5_glue->dr_create_flow_action_pop_vlan();
 	sh->dv_refcnt++;
 	priv->dr_shared = 1;
@@ -746,6 +755,10 @@ struct mlx5_flow_id_pool *
 		mlx5_glue->dr_destroy_domain(sh->fdb_domain);
 		sh->fdb_domain = NULL;
 	}
+	if (sh->flow_tbls) {
+		mlx5_hlist_destroy(sh->flow_tbls, NULL, NULL);
+		sh->flow_tbls = NULL;
+	}
 	if (sh->esw_drop_action) {
 		mlx5_glue->destroy_flow_action(sh->esw_drop_action);
 		sh->esw_drop_action = NULL;
@@ -786,6 +799,11 @@ struct mlx5_flow_id_pool *
 		mlx5_hlist_destroy(sh->flow_tbls, NULL, NULL);
 		sh->flow_tbls = NULL;
 	}
+	if (sh->tag_table) {
+		/* tags should be destroyed with flow before. */
+		mlx5_hlist_destroy(sh->tag_table, NULL, NULL);
+		sh->tag_table = NULL;
+	}
 	if (sh->rx_domain) {
 		mlx5_glue->dr_destroy_domain(sh->rx_domain);
 		sh->rx_domain = NULL;
diff --git a/drivers/net/mlx5/mlx5.h b/drivers/net/mlx5/mlx5.h
index 91442fe..7d7afee 100644
--- a/drivers/net/mlx5/mlx5.h
+++ b/drivers/net/mlx5/mlx5.h
@@ -652,7 +652,7 @@ struct mlx5_ibv_shared {
 	void *pop_vlan_action; /* Pointer to DR pop VLAN action. */
 	LIST_HEAD(encap_decap, mlx5_flow_dv_encap_decap_resource) encaps_decaps;
 	LIST_HEAD(modify_cmd, mlx5_flow_dv_modify_hdr_resource) modify_cmds;
-	LIST_HEAD(tag, mlx5_flow_dv_tag_resource) tags;
+	struct mlx5_hlist *tag_table;
 	LIST_HEAD(port_id_action_list, mlx5_flow_dv_port_id_action_resource)
 		port_id_action_list; /* List of port ID actions. */
 	LIST_HEAD(push_vlan_action_list, mlx5_flow_dv_push_vlan_action_resource)
diff --git a/drivers/net/mlx5/mlx5_flow.h b/drivers/net/mlx5/mlx5_flow.h
index df5f604..6b93695 100644
--- a/drivers/net/mlx5/mlx5_flow.h
+++ b/drivers/net/mlx5/mlx5_flow.h
@@ -357,12 +357,11 @@ struct mlx5_flow_dv_encap_decap_resource {
 
 /* Tag resource structure. */
 struct mlx5_flow_dv_tag_resource {
-	LIST_ENTRY(mlx5_flow_dv_tag_resource) next;
-	/* Pointer to next element. */
-	rte_atomic32_t refcnt; /**< Reference counter. */
+	struct mlx5_hlist_entry entry;
+	/**< hash list entry for tag resource, tag value as the key. */
 	void *action;
 	/**< Verbs tag action object. */
-	uint32_t tag; /**< the tag value. */
+	rte_atomic32_t refcnt; /**< Reference counter. */
 };
 
 /*
diff --git a/drivers/net/mlx5/mlx5_flow_dv.c b/drivers/net/mlx5/mlx5_flow_dv.c
index d33d4fd..34700c3 100644
--- a/drivers/net/mlx5/mlx5_flow_dv.c
+++ b/drivers/net/mlx5/mlx5_flow_dv.c
@@ -6305,8 +6305,8 @@ struct field_modify_info modify_tcp[] = {
  *
  * @param dev[in, out]
  *   Pointer to rte_eth_dev structure.
- * @param[in, out] resource
- *   Pointer to tag resource.
+ * @param[in, out] tag_be24
+ *   Tag value in big endian then R-shift 8.
  * @parm[in, out] dev_flow
  *   Pointer to the dev_flow.
  * @param[out] error
@@ -6318,34 +6318,35 @@ struct field_modify_info modify_tcp[] = {
 static int
 flow_dv_tag_resource_register
 			(struct rte_eth_dev *dev,
-			 struct mlx5_flow_dv_tag_resource *resource,
+			 uint32_t tag_be24,
 			 struct mlx5_flow *dev_flow,
 			 struct rte_flow_error *error)
 {
 	struct mlx5_priv *priv = dev->data->dev_private;
 	struct mlx5_ibv_shared *sh = priv->sh;
 	struct mlx5_flow_dv_tag_resource *cache_resource;
+	struct mlx5_hlist_entry *entry;
 
 	/* Lookup a matching resource from cache. */
-	LIST_FOREACH(cache_resource, &sh->tags, next) {
-		if (resource->tag == cache_resource->tag) {
-			DRV_LOG(DEBUG, "tag resource %p: refcnt %d++",
-				(void *)cache_resource,
-				rte_atomic32_read(&cache_resource->refcnt));
-			rte_atomic32_inc(&cache_resource->refcnt);
-			dev_flow->dv.tag_resource = cache_resource;
-			return 0;
-		}
+	entry = mlx5_hlist_lookup(sh->tag_table, (uint64_t)tag_be24);
+	if (entry) {
+		cache_resource = container_of
+			(entry, struct mlx5_flow_dv_tag_resource, entry);
+		rte_atomic32_inc(&cache_resource->refcnt);
+		dev_flow->dv.tag_resource = cache_resource;
+		DRV_LOG(DEBUG, "cached tag resource %p: refcnt now %d++",
+			(void *)cache_resource,
+			rte_atomic32_read(&cache_resource->refcnt));
+		return 0;
 	}
-	/* Register new  resource. */
+	/* Register new resource. */
 	cache_resource = rte_calloc(__func__, 1, sizeof(*cache_resource), 0);
 	if (!cache_resource)
 		return rte_flow_error_set(error, ENOMEM,
 					  RTE_FLOW_ERROR_TYPE_UNSPECIFIED, NULL,
 					  "cannot allocate resource memory");
-	*cache_resource = *resource;
-	cache_resource->action = mlx5_glue->dv_create_flow_action_tag
-		(resource->tag);
+	cache_resource->entry.key = (uint64_t)tag_be24;
+	cache_resource->action = mlx5_glue->dv_create_flow_action_tag(tag_be24);
 	if (!cache_resource->action) {
 		rte_free(cache_resource);
 		return rte_flow_error_set(error, ENOMEM,
@@ -6354,9 +6355,15 @@ struct field_modify_info modify_tcp[] = {
 	}
 	rte_atomic32_init(&cache_resource->refcnt);
 	rte_atomic32_inc(&cache_resource->refcnt);
-	LIST_INSERT_HEAD(&sh->tags, cache_resource, next);
+	if (mlx5_hlist_insert(sh->tag_table, &cache_resource->entry)) {
+		mlx5_glue->destroy_flow_action(cache_resource->action);
+		rte_free(cache_resource);
+		return rte_flow_error_set(error, EEXIST,
+					  RTE_FLOW_ERROR_TYPE_UNSPECIFIED,
+					  NULL, "cannot insert tag");
+	}
 	dev_flow->dv.tag_resource = cache_resource;
-	DRV_LOG(DEBUG, "new tag resource %p: refcnt %d++",
+	DRV_LOG(DEBUG, "new tag resource %p: refcnt now %d++",
 		(void *)cache_resource,
 		rte_atomic32_read(&cache_resource->refcnt));
 	return 0;
@@ -6377,13 +6384,16 @@ struct field_modify_info modify_tcp[] = {
 flow_dv_tag_release(struct rte_eth_dev *dev,
 		    struct mlx5_flow_dv_tag_resource *tag)
 {
+	struct mlx5_priv *priv = dev->data->dev_private;
+	struct mlx5_ibv_shared *sh = priv->sh;
+
 	assert(tag);
 	DRV_LOG(DEBUG, "port %u tag %p: refcnt %d--",
 		dev->data->port_id, (void *)tag,
 		rte_atomic32_read(&tag->refcnt));
 	if (rte_atomic32_dec_and_test(&tag->refcnt)) {
 		claim_zero(mlx5_glue->destroy_flow_action(tag->action));
-		LIST_REMOVE(tag, next);
+		mlx5_hlist_remove(sh->tag_table, &tag->entry);
 		DRV_LOG(DEBUG, "port %u tag %p: removed",
 			dev->data->port_id, (void *)tag);
 		rte_free(tag);
@@ -6524,7 +6534,7 @@ struct field_modify_info modify_tcp[] = {
 					  MLX5DV_FLOW_TABLE_TYPE_NIC_RX
 	};
 	union flow_dv_attr flow_attr = { .attr = 0 };
-	struct mlx5_flow_dv_tag_resource tag_resource;
+	uint32_t tag_be;
 	union mlx5_flow_tbl_key tbl_key;
 	uint32_t modify_action_position = UINT32_MAX;
 	void *match_mask = matcher.mask.buf;
@@ -6585,12 +6595,11 @@ struct field_modify_info modify_tcp[] = {
 				action_flags |= MLX5_FLOW_ACTION_MARK_EXT;
 				break;
 			}
-			tag_resource.tag =
-				mlx5_flow_mark_set(MLX5_FLOW_MARK_DEFAULT);
+			tag_be = mlx5_flow_mark_set(MLX5_FLOW_MARK_DEFAULT);
 			if (!dev_flow->dv.tag_resource)
 				if (flow_dv_tag_resource_register
-				    (dev, &tag_resource, dev_flow, error))
-					return errno;
+				    (dev, tag_be, dev_flow, error))
+					return -rte_errno;
 			dev_flow->dv.actions[actions_n++] =
 				dev_flow->dv.tag_resource->action;
 			break;
@@ -6611,13 +6620,13 @@ struct field_modify_info modify_tcp[] = {
 			/* Fall-through */
 		case MLX5_RTE_FLOW_ACTION_TYPE_MARK:
 			/* Legacy (non-extensive) MARK action. */
-			tag_resource.tag = mlx5_flow_mark_set
+			tag_be = mlx5_flow_mark_set
 			      (((const struct rte_flow_action_mark *)
 			       (actions->conf))->id);
 			if (!dev_flow->dv.tag_resource)
 				if (flow_dv_tag_resource_register
-				    (dev, &tag_resource, dev_flow, error))
-					return errno;
+				    (dev, tag_be, dev_flow, error))
+					return -rte_errno;
 			dev_flow->dv.actions[actions_n++] =
 				dev_flow->dv.tag_resource->action;
 			break;
-- 
1.8.3.1