Skip to contentSkip to conversation

net/mlx5: hash list optimization

PATCH Superseded Suanming Mou 2 participants 7 messages Dec 2, 2020 – Dec 8, 2020 Network drivers

lore
Share & tools
lore
#0 lore raw

cover net/mlx5: hash list optimization

This patch set contains the hash list optimization for the lock and memory.

Suanming Mou (2):
net/mlx5: optimize hash list synchronization
net/mlx5: optimize the hash list entry memory

 drivers/net/mlx5/linux/mlx5_os.c |  5 ++-
 drivers/net/mlx5/mlx5.c          |  3 +-
 drivers/net/mlx5/mlx5_flow.c     | 43 ++++++++++++++++----
 drivers/net/mlx5/mlx5_flow.h     | 23 +++++++++--
 drivers/net/mlx5/mlx5_flow_dv.c  | 57 +++++++++++++++++++--------
 drivers/net/mlx5/mlx5_utils.c    | 85 ++++++++++++++++++++--------------------
 drivers/net/mlx5/mlx5_utils.h    | 16 +++++---
 7 files changed, 155 insertions(+), 77 deletions(-)
Signature · 1 line
1.8.3.1
#1 lore raw

PATCH 1/2 net/mlx5: optimize hash list synchronization

Since all the hash table operations are related with one dedicated bucket, the hash table lock and gen_cnt can be allocated per-bucket.

Currently, the hash table uses one global lock to protect all the buckets, that global lock avoids the buckets to be operated at one time, it hurts the hash table performance. And the gen_cnt updated by the entire hash table causes incorrect redundant list research.

This commit optimized the lock and gen_cnt to bucket solid allows different bucket entries can be operated more efficiently.

---
 drivers/net/mlx5/mlx5_utils.c | 76 +++++++++++++++++++++++++------------------
 drivers/net/mlx5/mlx5_utils.h | 12 +++++--
 2 files changed, 54 insertions(+), 34 deletions(-)
drivers/net/mlx5/mlx5_utils.c +45 -31
index 848d108..42e5d80 100644
@@ -41,6 +41,7 @@ struct mlx5_hlist *
 	struct mlx5_hlist *h;
 	uint32_t act_size;
 	uint32_t alloc_size;
+	uint32_t i;
 
 	if (!size || (!cb_create ^ !cb_remove))
 		return NULL;
@@ -53,7 +54,7 @@ struct mlx5_hlist *
 		act_size = size;
 	}
 	alloc_size = sizeof(struct mlx5_hlist) +
-		     sizeof(struct mlx5_hlist_head) * act_size;
+		     sizeof(struct mlx5_hlist_bucket) * act_size;
 	/* Using zmalloc, then no need to initialize the heads. */
 	h = mlx5_malloc(MLX5_MEM_ZERO, alloc_size, RTE_CACHE_LINE_SIZE,
 			SOCKET_ID_ANY);
@@ -72,25 +73,22 @@ struct mlx5_hlist *
 	h->cb_create = cb_create ? cb_create : mlx5_hlist_default_create_cb;
 	h->cb_match = cb_match ? cb_match : mlx5_hlist_default_match_cb;
 	h->cb_remove = cb_remove ? cb_remove : mlx5_hlist_default_remove_cb;
-	rte_rwlock_init(&h->lock);
+	for (i = 0; i < act_size; i++)
+		rte_rwlock_init(&h->buckets[i].lock);
 	DRV_LOG(DEBUG, "Hash list with %s size 0x%" PRIX32 " is created.",
 		h->name, act_size);
 	return h;
 }
 
 static struct mlx5_hlist_entry *
-__hlist_lookup(struct mlx5_hlist *h, uint64_t key, void *ctx, bool reuse)
+__hlist_lookup(struct mlx5_hlist *h, uint64_t key, uint32_t idx,
+	       void *ctx, bool reuse)
 {
-	uint32_t idx;
 	struct mlx5_hlist_head *first;
 	struct mlx5_hlist_entry *node;
 
 	MLX5_ASSERT(h);
-	if (h->direct_key)
-		idx = (uint32_t)(key & h->mask);
-	else
-		idx = rte_hash_crc_8byte(key, 0) & h->mask;
-	first = &h->heads[idx];
+	first = &h->buckets[idx].head;
 	LIST_FOREACH(node, first, next) {
 		if (!h->cb_match(h, node, key, ctx)) {
 			if (reuse) {
@@ -107,21 +105,28 @@ struct mlx5_hlist *
 }
 
 static struct mlx5_hlist_entry *
-hlist_lookup(struct mlx5_hlist *h, uint64_t key, void *ctx, bool reuse)
+hlist_lookup(struct mlx5_hlist *h, uint64_t key, uint32_t idx,
+	     void *ctx, bool reuse)
 {
 	struct mlx5_hlist_entry *node;
 
 	MLX5_ASSERT(h);
-	rte_rwlock_read_lock(&h->lock);
-	node = __hlist_lookup(h, key, ctx, reuse);
-	rte_rwlock_read_unlock(&h->lock);
+	rte_rwlock_read_lock(&h->buckets[idx].lock);
+	node = __hlist_lookup(h, key, idx, ctx, reuse);
+	rte_rwlock_read_unlock(&h->buckets[idx].lock);
 	return node;
 }
 
 struct mlx5_hlist_entry *
 mlx5_hlist_lookup(struct mlx5_hlist *h, uint64_t key, void *ctx)
 {
-	return hlist_lookup(h, key, ctx, false);
+	uint32_t idx;
+
+	if (h->direct_key)
+		idx = (uint32_t)(key & h->mask);
+	else
+		idx = rte_hash_crc_8byte(key, 0) & h->mask;
+	return hlist_lookup(h, key, idx, ctx, false);
 }
 
 struct mlx5_hlist_entry*
@@ -129,30 +134,32 @@ struct mlx5_hlist_entry*
 {
 	uint32_t idx;
 	struct mlx5_hlist_head *first;
+	struct mlx5_hlist_bucket *b;
 	struct mlx5_hlist_entry *entry;
 	uint32_t prev_gen_cnt = 0;
 
+	if (h->direct_key)
+		idx = (uint32_t)(key & h->mask);
+	else
+		idx = rte_hash_crc_8byte(key, 0) & h->mask;
 	MLX5_ASSERT(h);
+	b = &h->buckets[idx];
 	/* Use write lock directly for write-most list. */
 	if (!h->write_most) {
-		prev_gen_cnt = __atomic_load_n(&h->gen_cnt, __ATOMIC_ACQUIRE);
-		entry = hlist_lookup(h, key, ctx, true);
+		prev_gen_cnt = __atomic_load_n(&b->gen_cnt, __ATOMIC_ACQUIRE);
+		entry = hlist_lookup(h, key, idx, ctx, true);
 		if (entry)
 			return entry;
 	}
-	rte_rwlock_write_lock(&h->lock);
+	rte_rwlock_write_lock(&b->lock);
 	/* Check if the list changed by other threads. */
 	if (h->write_most ||
-	    prev_gen_cnt != __atomic_load_n(&h->gen_cnt, __ATOMIC_ACQUIRE)) {
-		entry = __hlist_lookup(h, key, ctx, true);
+	    prev_gen_cnt != __atomic_load_n(&b->gen_cnt, __ATOMIC_ACQUIRE)) {
+		entry = __hlist_lookup(h, key, idx, ctx, true);
 		if (entry)
 			goto done;
 	}
-	if (h->direct_key)
-		idx = (uint32_t)(key & h->mask);
-	else
-		idx = rte_hash_crc_8byte(key, 0) & h->mask;
-	first = &h->heads[idx];
+	first = &b->head;
 	entry = h->cb_create(h, key, ctx);
 	if (!entry) {
 		rte_errno = ENOMEM;
@@ -162,30 +169,37 @@ struct mlx5_hlist_entry*
 	entry->key = key;
 	entry->ref_cnt = 1;
 	LIST_INSERT_HEAD(first, entry, next);
-	__atomic_add_fetch(&h->gen_cnt, 1, __ATOMIC_ACQ_REL);
+	__atomic_add_fetch(&b->gen_cnt, 1, __ATOMIC_ACQ_REL);
 	DRV_LOG(DEBUG, "Hash list %s entry %p new: %u.",
 		h->name, (void *)entry, entry->ref_cnt);
 done:
-	rte_rwlock_write_unlock(&h->lock);
+	rte_rwlock_write_unlock(&b->lock);
 	return entry;
 }
 
 int
 mlx5_hlist_unregister(struct mlx5_hlist *h, struct mlx5_hlist_entry *entry)
 {
-	rte_rwlock_write_lock(&h->lock);
+	uint32_t idx;
+
+	if (h->direct_key)
+		idx = (uint32_t)(entry->key & h->mask);
+	else
+		idx = rte_hash_crc_8byte(entry->key, 0) & h->mask;
+
+	rte_rwlock_write_lock(&h->buckets[idx].lock);
 	MLX5_ASSERT(entry && entry->ref_cnt && entry->next.le_prev);
 	DRV_LOG(DEBUG, "Hash list %s entry %p deref: %u.",
 		h->name, (void *)entry, entry->ref_cnt);
 	if (--entry->ref_cnt) {
-		rte_rwlock_write_unlock(&h->lock);
+		rte_rwlock_write_unlock(&h->buckets[idx].lock);
 		return 1;
 	}
 	LIST_REMOVE(entry, next);
 	/* Set to NULL to get rid of removing action for more than once. */
 	entry->next.le_prev = NULL;
 	h->cb_remove(h, entry);
-	rte_rwlock_write_unlock(&h->lock);
+	rte_rwlock_write_unlock(&h->buckets[idx].lock);
 	DRV_LOG(DEBUG, "Hash list %s entry %p removed.",
 		h->name, (void *)entry);
 	return 0;
@@ -200,8 +214,8 @@ struct mlx5_hlist_entry*
 	MLX5_ASSERT(h);
 	for (idx = 0; idx < h->table_sz; ++idx) {
 		/* No LIST_FOREACH_SAFE, using while instead. */
-		while (!LIST_EMPTY(&h->heads[idx])) {
-			entry = LIST_FIRST(&h->heads[idx]);
+		while (!LIST_EMPTY(&h->buckets[idx].head)) {
+			entry = LIST_FIRST(&h->buckets[idx].head);
 			LIST_REMOVE(entry, next);
 			/*
 			 * The owner of whole element which contains data entry
drivers/net/mlx5/mlx5_utils.h +9 -3
index be6e5f6..6f25768 100644
@@ -328,6 +328,13 @@ typedef int (*mlx5_hlist_match_cb)(struct mlx5_hlist *list,
 				  (struct mlx5_hlist *list,
 				   uint64_t key, void *ctx);
 
+/* Hash list bucket head. */
+struct mlx5_hlist_bucket {
+	struct mlx5_hlist_head head; /* List head. */
+	rte_rwlock_t lock; /* Bucket lock. */
+	uint32_t gen_cnt; /* List modification will update generation count. */
+} __rte_cache_aligned;
+
 /**
  * Hash list table structure
  *
@@ -344,15 +351,14 @@ struct mlx5_hlist {
 	uint32_t entry_sz; /**< Size of entry, used to allocate entry. */
 	/**< mask to get the index of the list heads. */
 	uint32_t mask;
-	rte_rwlock_t lock;
-	uint32_t gen_cnt; /* List modification will update generation count. */
 	bool direct_key; /* Use the new entry key directly as hash index. */
 	bool write_most; /* List mostly used for append new or destroy. */
 	void *ctx;
 	mlx5_hlist_create_cb cb_create; /**< entry create callback. */
 	mlx5_hlist_match_cb cb_match; /**< entry match callback. */
 	mlx5_hlist_remove_cb cb_remove; /**< entry remove callback. */
-	struct mlx5_hlist_head heads[];	/**< list head arrays. */
+	struct mlx5_hlist_bucket buckets[] __rte_cache_aligned;
+	/**< list bucket arrays. */
 };
 
 /**
Signature · 1 line
1.8.3.1
#2 lore raw

PATCH 2/2 net/mlx5: optimize the hash list entry memory

In reply to Suanming Mou

Currently, the hash list saves the hash key in the hash entry. And the key is mostly used to get the bucket index only.

Save the entire 64 bits key to the entry will not be a good option if the key is only used to get the bucket index. Since 64 bits costs more memory for the entry, mostly the signature data in the key only uses 32 bits. And in the unregister function, the key in the entry causes extra bucket index calculation.

This commit saves the bucket index to the entry instead of the hash key. For the hash list like table, tag and mreg_copy which save the signature data in the key, the signature data is moved to the resource data struct itself.

---
 drivers/net/mlx5/linux/mlx5_os.c |  5 ++--
 drivers/net/mlx5/mlx5.c          |  3 ++-
 drivers/net/mlx5/mlx5_flow.c     | 43 ++++++++++++++++++++++++------
 drivers/net/mlx5/mlx5_flow.h     | 23 +++++++++++++---
 drivers/net/mlx5/mlx5_flow_dv.c  | 57 +++++++++++++++++++++++++++++-----------
 drivers/net/mlx5/mlx5_utils.c    | 21 +++------------
 drivers/net/mlx5/mlx5_utils.h    |  4 +--
 7 files changed, 107 insertions(+), 49 deletions(-)
drivers/net/mlx5/linux/mlx5_os.c +3 -2
index 4c863db..6c501c0 100644
@@ -264,7 +264,8 @@
 	snprintf(s, sizeof(s), "%s_tags", sh->ibdev_name);
 	sh->tag_table = mlx5_hlist_create(s, MLX5_TAGS_HLIST_ARRAY_SIZE, 0,
 					  MLX5_HLIST_WRITE_MOST,
-					  flow_dv_tag_create_cb, NULL,
+					  flow_dv_tag_create_cb,
+					  flow_dv_tag_match_cb,
 					  flow_dv_tag_remove_cb);
 	if (!sh->tag_table) {
 		DRV_LOG(ERR, "tags with hash creation failed.");
@@ -1564,7 +1565,7 @@
 						      MLX5_FLOW_MREG_HTABLE_SZ,
 						      0, 0,
 						      flow_dv_mreg_create_cb,
-						      NULL,
+						      flow_dv_mreg_match_cb,
 						      flow_dv_mreg_remove_cb);
 		if (!priv->mreg_cp_tbl) {
 			err = ENOMEM;
drivers/net/mlx5/mlx5.c +2 -1
index ca3667a..7d3f18c 100644
@@ -1152,7 +1152,8 @@ struct mlx5_dev_ctx_shared *
 	MLX5_ASSERT(sh);
 	snprintf(s, sizeof(s), "%s_flow_table", priv->sh->ibdev_name);
 	sh->flow_tbls = mlx5_hlist_create(s, MLX5_FLOW_TABLE_HLIST_ARRAY_SIZE,
-					  0, 0, flow_dv_tbl_create_cb, NULL,
+					  0, 0, flow_dv_tbl_create_cb,
+					  flow_dv_tbl_match_cb,
 					  flow_dv_tbl_remove_cb);
 	if (!sh->flow_tbls) {
 		DRV_LOG(ERR, "flow tables with hash creation failed.");
drivers/net/mlx5/mlx5_flow.c +35 -8

97 lines not on this page · raw message

drivers/net/mlx5/mlx5_flow.h +20 -3
index a249c29..d85dd19 100644
@@ -437,6 +437,7 @@ struct mlx5_flow_dv_tag_resource {
 	/**< Tag action object. */
 	uint32_t refcnt; /**< Reference counter. */
 	uint32_t idx; /**< Index for the index memory pool. */
+	uint32_t tag_id; /**< Tag ID. */
 };
 
 /*
@@ -509,6 +510,7 @@ struct mlx5_flow_mreg_copy_resource {
 	/* List entry for device flows. */
 	uint32_t idx;
 	uint32_t rix_flow; /* Built flow for copy. */
+	uint32_t mark_id;
 };
 
 /* Table tunnel parameter. */
@@ -532,9 +534,13 @@ struct mlx5_flow_tbl_data_entry {
 	/**< tunnel offload */
 	const struct mlx5_flow_tunnel *tunnel;
 	uint32_t group_id;
-	bool external;
-	bool tunnel_offload; /* Tunnel offlod table or not. */
-	bool is_egress; /**< Egress table. */
+	uint32_t external:1;
+	uint32_t tunnel_offload:1; /* Tunnel offlod table or not. */
+	uint32_t is_egress:1; /**< Egress table. */
+	uint32_t is_transfer:1; /**< Transfer table. */
+	uint32_t dummy:1; /**<  DR table. */
+	uint32_t reserve:27; /**< Reserved to future using. */
+	uint32_t table_id; /**< Table ID. */
 };
 
 /* Sub rdma-core actions list. */
@@ -954,6 +960,8 @@ struct mlx5_flow_tunnel_hub {
 struct tunnel_tbl_entry {
 	struct mlx5_hlist_entry hash;
 	uint32_t flow_table;
+	uint32_t tunnel_id;
+	uint32_t group;
 };
 
 static inline uint32_t
@@ -1416,6 +1424,9 @@ int mlx5_flow_meter_flush(struct rte_eth_dev *dev,
 /* Hash list callbacks for flow tables: */
 struct mlx5_hlist_entry *flow_dv_tbl_create_cb(struct mlx5_hlist *list,
 					       uint64_t key, void *entry_ctx);
+int flow_dv_tbl_match_cb(struct mlx5_hlist *list,
+			 struct mlx5_hlist_entry *entry, uint64_t key,
+			 void *cb_ctx);
 void flow_dv_tbl_remove_cb(struct mlx5_hlist *list,
 			   struct mlx5_hlist_entry *entry);
 struct mlx5_flow_tbl_resource *flow_dv_tbl_resource_get(struct rte_eth_dev *dev,
@@ -1425,6 +1436,9 @@ struct mlx5_flow_tbl_resource *flow_dv_tbl_resource_get(struct rte_eth_dev *dev,
 
 struct mlx5_hlist_entry *flow_dv_tag_create_cb(struct mlx5_hlist *list,
 					       uint64_t key, void *cb_ctx);
+int flow_dv_tag_match_cb(struct mlx5_hlist *list,
+			 struct mlx5_hlist_entry *entry, uint64_t key,
+			 void *cb_ctx);
 void flow_dv_tag_remove_cb(struct mlx5_hlist *list,
 			   struct mlx5_hlist_entry *entry);
 
@@ -1438,6 +1452,9 @@ void flow_dv_modify_remove_cb(struct mlx5_hlist *list,
 
 struct mlx5_hlist_entry *flow_dv_mreg_create_cb(struct mlx5_hlist *list,
 						uint64_t key, void *ctx);
+int flow_dv_mreg_match_cb(struct mlx5_hlist *list,
+			  struct mlx5_hlist_entry *entry, uint64_t key,
+			  void *cb_ctx);
 void flow_dv_mreg_remove_cb(struct mlx5_hlist *list,
 			    struct mlx5_hlist_entry *entry);
 
drivers/net/mlx5/mlx5_flow_dv.c +41 -16

118 lines not on this page · raw message

drivers/net/mlx5/mlx5_utils.c +4 -17
index 42e5d80..07373bf 100644
@@ -25,14 +25,6 @@
 	mlx5_free(entry);
 }
 
-static int
-mlx5_hlist_default_match_cb(struct mlx5_hlist *h __rte_unused,
-			    struct mlx5_hlist_entry *entry,
-			    uint64_t key, void *ctx __rte_unused)
-{
-	return entry->key != key;
-}
-
 struct mlx5_hlist *
 mlx5_hlist_create(const char *name, uint32_t size, uint32_t entry_size,
 		  uint32_t flags, mlx5_hlist_create_cb cb_create,
@@ -43,7 +35,7 @@ struct mlx5_hlist *
 	uint32_t alloc_size;
 	uint32_t i;
 
-	if (!size || (!cb_create ^ !cb_remove))
+	if (!size || !cb_match || (!cb_create ^ !cb_remove))
 		return NULL;
 	/* Align to the next power of 2, 32bits integer is enough now. */
 	if (!rte_is_power_of_2(size)) {
@@ -71,7 +63,7 @@ struct mlx5_hlist *
 	h->direct_key = !!(flags & MLX5_HLIST_DIRECT_KEY);
 	h->write_most = !!(flags & MLX5_HLIST_WRITE_MOST);
 	h->cb_create = cb_create ? cb_create : mlx5_hlist_default_create_cb;
-	h->cb_match = cb_match ? cb_match : mlx5_hlist_default_match_cb;
+	h->cb_match = cb_match;
 	h->cb_remove = cb_remove ? cb_remove : mlx5_hlist_default_remove_cb;
 	for (i = 0; i < act_size; i++)
 		rte_rwlock_init(&h->buckets[i].lock);
@@ -166,7 +158,7 @@ struct mlx5_hlist_entry*
 		DRV_LOG(DEBUG, "Can't allocate hash list %s entry.", h->name);
 		goto done;
 	}
-	entry->key = key;
+	entry->idx = idx;
 	entry->ref_cnt = 1;
 	LIST_INSERT_HEAD(first, entry, next);
 	__atomic_add_fetch(&b->gen_cnt, 1, __ATOMIC_ACQ_REL);
@@ -180,12 +172,7 @@ struct mlx5_hlist_entry*
 int
 mlx5_hlist_unregister(struct mlx5_hlist *h, struct mlx5_hlist_entry *entry)
 {
-	uint32_t idx;
-
-	if (h->direct_key)
-		idx = (uint32_t)(entry->key & h->mask);
-	else
-		idx = rte_hash_crc_8byte(entry->key, 0) & h->mask;
+	uint32_t idx = entry->idx;
 
 	rte_rwlock_write_lock(&h->buckets[idx].lock);
 	MLX5_ASSERT(entry && entry->ref_cnt && entry->next.le_prev);
drivers/net/mlx5/mlx5_utils.h +2 -2
index 6f25768..1971b17 100644
@@ -274,9 +274,9 @@ struct mlx5_indexed_pool {
  */
 struct mlx5_hlist_entry {
 	LIST_ENTRY(mlx5_hlist_entry) next; /* entry pointers in the list. */
-	uint64_t key; /* user defined 'key', could be the hash signature. */
+	uint32_t idx; /* Bucket index the entry belongs to. */
 	uint32_t ref_cnt; /* Reference count. */
-};
+} __rte_packed;
 
 /** Structure for hash head. */
 LIST_HEAD(mlx5_hlist_head, mlx5_hlist_entry);
Signature · 1 line
1.8.3.1
#3 lore raw

v2 cover net/mlx5: hash list optimization

In reply to Suanming Mou

This patch set contains the hash list optimization for the lock and memory.

v2:
- Remove the __rte_pack in struct mlx5_hlist_entry.

Suanming Mou (2):
net/mlx5: optimize hash list synchronization
net/mlx5: optimize the hash list entry memory

 drivers/net/mlx5/linux/mlx5_os.c |  5 +-
 drivers/net/mlx5/mlx5.c          |  3 +-
 drivers/net/mlx5/mlx5_flow.c     | 43 +++++++++++++---
 drivers/net/mlx5/mlx5_flow.h     | 23 +++++++--
 drivers/net/mlx5/mlx5_flow_dv.c  | 57 +++++++++++++++------
 drivers/net/mlx5/mlx5_utils.c    | 85 ++++++++++++++++----------------
 drivers/net/mlx5/mlx5_utils.h    | 14 ++++--
 7 files changed, 154 insertions(+), 76 deletions(-)
Signature · 1 line
2.25.1
#4 lore raw

PATCH v2 1/2 net/mlx5: optimize hash list synchronization

Since all the hash table operations are related with one dedicated bucket, the hash table lock and gen_cnt can be allocated per-bucket.

Currently, the hash table uses one global lock to protect all the buckets, that global lock avoids the buckets to be operated at one time, it hurts the hash table performance. And the gen_cnt updated by the entire hash table causes incorrect redundant list research.

This commit optimized the lock and gen_cnt to bucket solid allows different bucket entries can be operated more efficiently.

---
 drivers/net/mlx5/mlx5_utils.c | 76 +++++++++++++++++++++--------------
 drivers/net/mlx5/mlx5_utils.h | 12 ++++--
 2 files changed, 54 insertions(+), 34 deletions(-)
drivers/net/mlx5/mlx5_utils.c +45 -31
index 848d108bc6..42e5d80aee 100644
@@ -41,6 +41,7 @@ mlx5_hlist_create(const char *name, uint32_t size, uint32_t entry_size,
 	struct mlx5_hlist *h;
 	uint32_t act_size;
 	uint32_t alloc_size;
+	uint32_t i;
 
 	if (!size || (!cb_create ^ !cb_remove))
 		return NULL;
@@ -53,7 +54,7 @@ mlx5_hlist_create(const char *name, uint32_t size, uint32_t entry_size,
 		act_size = size;
 	}
 	alloc_size = sizeof(struct mlx5_hlist) +
-		     sizeof(struct mlx5_hlist_head) * act_size;
+		     sizeof(struct mlx5_hlist_bucket) * act_size;
 	/* Using zmalloc, then no need to initialize the heads. */
 	h = mlx5_malloc(MLX5_MEM_ZERO, alloc_size, RTE_CACHE_LINE_SIZE,
 			SOCKET_ID_ANY);
@@ -72,25 +73,22 @@ mlx5_hlist_create(const char *name, uint32_t size, uint32_t entry_size,
 	h->cb_create = cb_create ? cb_create : mlx5_hlist_default_create_cb;
 	h->cb_match = cb_match ? cb_match : mlx5_hlist_default_match_cb;
 	h->cb_remove = cb_remove ? cb_remove : mlx5_hlist_default_remove_cb;
-	rte_rwlock_init(&h->lock);
+	for (i = 0; i < act_size; i++)
+		rte_rwlock_init(&h->buckets[i].lock);
 	DRV_LOG(DEBUG, "Hash list with %s size 0x%" PRIX32 " is created.",
 		h->name, act_size);
 	return h;
 }
 
 static struct mlx5_hlist_entry *
-__hlist_lookup(struct mlx5_hlist *h, uint64_t key, void *ctx, bool reuse)
+__hlist_lookup(struct mlx5_hlist *h, uint64_t key, uint32_t idx,
+	       void *ctx, bool reuse)
 {
-	uint32_t idx;
 	struct mlx5_hlist_head *first;
 	struct mlx5_hlist_entry *node;
 
 	MLX5_ASSERT(h);
-	if (h->direct_key)
-		idx = (uint32_t)(key & h->mask);
-	else
-		idx = rte_hash_crc_8byte(key, 0) & h->mask;
-	first = &h->heads[idx];
+	first = &h->buckets[idx].head;
 	LIST_FOREACH(node, first, next) {
 		if (!h->cb_match(h, node, key, ctx)) {
 			if (reuse) {
@@ -107,21 +105,28 @@ __hlist_lookup(struct mlx5_hlist *h, uint64_t key, void *ctx, bool reuse)
 }
 
 static struct mlx5_hlist_entry *
-hlist_lookup(struct mlx5_hlist *h, uint64_t key, void *ctx, bool reuse)
+hlist_lookup(struct mlx5_hlist *h, uint64_t key, uint32_t idx,
+	     void *ctx, bool reuse)
 {
 	struct mlx5_hlist_entry *node;
 
 	MLX5_ASSERT(h);
-	rte_rwlock_read_lock(&h->lock);
-	node = __hlist_lookup(h, key, ctx, reuse);
-	rte_rwlock_read_unlock(&h->lock);
+	rte_rwlock_read_lock(&h->buckets[idx].lock);
+	node = __hlist_lookup(h, key, idx, ctx, reuse);
+	rte_rwlock_read_unlock(&h->buckets[idx].lock);
 	return node;
 }
 
 struct mlx5_hlist_entry *
 mlx5_hlist_lookup(struct mlx5_hlist *h, uint64_t key, void *ctx)
 {
-	return hlist_lookup(h, key, ctx, false);
+	uint32_t idx;
+
+	if (h->direct_key)
+		idx = (uint32_t)(key & h->mask);
+	else
+		idx = rte_hash_crc_8byte(key, 0) & h->mask;
+	return hlist_lookup(h, key, idx, ctx, false);
 }
 
 struct mlx5_hlist_entry*
@@ -129,30 +134,32 @@ mlx5_hlist_register(struct mlx5_hlist *h, uint64_t key, void *ctx)
 {
 	uint32_t idx;
 	struct mlx5_hlist_head *first;
+	struct mlx5_hlist_bucket *b;
 	struct mlx5_hlist_entry *entry;
 	uint32_t prev_gen_cnt = 0;
 
+	if (h->direct_key)
+		idx = (uint32_t)(key & h->mask);
+	else
+		idx = rte_hash_crc_8byte(key, 0) & h->mask;
 	MLX5_ASSERT(h);
+	b = &h->buckets[idx];
 	/* Use write lock directly for write-most list. */
 	if (!h->write_most) {
-		prev_gen_cnt = __atomic_load_n(&h->gen_cnt, __ATOMIC_ACQUIRE);
-		entry = hlist_lookup(h, key, ctx, true);
+		prev_gen_cnt = __atomic_load_n(&b->gen_cnt, __ATOMIC_ACQUIRE);
+		entry = hlist_lookup(h, key, idx, ctx, true);
 		if (entry)
 			return entry;
 	}
-	rte_rwlock_write_lock(&h->lock);
+	rte_rwlock_write_lock(&b->lock);
 	/* Check if the list changed by other threads. */
 	if (h->write_most ||
-	    prev_gen_cnt != __atomic_load_n(&h->gen_cnt, __ATOMIC_ACQUIRE)) {
-		entry = __hlist_lookup(h, key, ctx, true);
+	    prev_gen_cnt != __atomic_load_n(&b->gen_cnt, __ATOMIC_ACQUIRE)) {
+		entry = __hlist_lookup(h, key, idx, ctx, true);
 		if (entry)
 			goto done;
 	}
-	if (h->direct_key)
-		idx = (uint32_t)(key & h->mask);
-	else
-		idx = rte_hash_crc_8byte(key, 0) & h->mask;
-	first = &h->heads[idx];
+	first = &b->head;
 	entry = h->cb_create(h, key, ctx);
 	if (!entry) {
 		rte_errno = ENOMEM;
@@ -162,30 +169,37 @@ mlx5_hlist_register(struct mlx5_hlist *h, uint64_t key, void *ctx)
 	entry->key = key;
 	entry->ref_cnt = 1;
 	LIST_INSERT_HEAD(first, entry, next);
-	__atomic_add_fetch(&h->gen_cnt, 1, __ATOMIC_ACQ_REL);
+	__atomic_add_fetch(&b->gen_cnt, 1, __ATOMIC_ACQ_REL);
 	DRV_LOG(DEBUG, "Hash list %s entry %p new: %u.",
 		h->name, (void *)entry, entry->ref_cnt);
 done:
-	rte_rwlock_write_unlock(&h->lock);
+	rte_rwlock_write_unlock(&b->lock);
 	return entry;
 }
 
 int
 mlx5_hlist_unregister(struct mlx5_hlist *h, struct mlx5_hlist_entry *entry)
 {
-	rte_rwlock_write_lock(&h->lock);
+	uint32_t idx;
+
+	if (h->direct_key)
+		idx = (uint32_t)(entry->key & h->mask);
+	else
+		idx = rte_hash_crc_8byte(entry->key, 0) & h->mask;
+
+	rte_rwlock_write_lock(&h->buckets[idx].lock);
 	MLX5_ASSERT(entry && entry->ref_cnt && entry->next.le_prev);
 	DRV_LOG(DEBUG, "Hash list %s entry %p deref: %u.",
 		h->name, (void *)entry, entry->ref_cnt);
 	if (--entry->ref_cnt) {
-		rte_rwlock_write_unlock(&h->lock);
+		rte_rwlock_write_unlock(&h->buckets[idx].lock);
 		return 1;
 	}
 	LIST_REMOVE(entry, next);
 	/* Set to NULL to get rid of removing action for more than once. */
 	entry->next.le_prev = NULL;
 	h->cb_remove(h, entry);
-	rte_rwlock_write_unlock(&h->lock);
+	rte_rwlock_write_unlock(&h->buckets[idx].lock);
 	DRV_LOG(DEBUG, "Hash list %s entry %p removed.",
 		h->name, (void *)entry);
 	return 0;
@@ -200,8 +214,8 @@ mlx5_hlist_destroy(struct mlx5_hlist *h)
 	MLX5_ASSERT(h);
 	for (idx = 0; idx < h->table_sz; ++idx) {
 		/* No LIST_FOREACH_SAFE, using while instead. */
-		while (!LIST_EMPTY(&h->heads[idx])) {
-			entry = LIST_FIRST(&h->heads[idx]);
+		while (!LIST_EMPTY(&h->buckets[idx].head)) {
+			entry = LIST_FIRST(&h->buckets[idx].head);
 			LIST_REMOVE(entry, next);
 			/*
 			 * The owner of whole element which contains data entry
drivers/net/mlx5/mlx5_utils.h +9 -3
index be6e5f67aa..6f2576812b 100644
@@ -328,6 +328,13 @@ typedef struct mlx5_hlist_entry *(*mlx5_hlist_create_cb)
 				  (struct mlx5_hlist *list,
 				   uint64_t key, void *ctx);
 
+/* Hash list bucket head. */
+struct mlx5_hlist_bucket {
+	struct mlx5_hlist_head head; /* List head. */
+	rte_rwlock_t lock; /* Bucket lock. */
+	uint32_t gen_cnt; /* List modification will update generation count. */
+} __rte_cache_aligned;
+
 /**
  * Hash list table structure
  *
@@ -344,15 +351,14 @@ struct mlx5_hlist {
 	uint32_t entry_sz; /**< Size of entry, used to allocate entry. */
 	/**< mask to get the index of the list heads. */
 	uint32_t mask;
-	rte_rwlock_t lock;
-	uint32_t gen_cnt; /* List modification will update generation count. */
 	bool direct_key; /* Use the new entry key directly as hash index. */
 	bool write_most; /* List mostly used for append new or destroy. */
 	void *ctx;
 	mlx5_hlist_create_cb cb_create; /**< entry create callback. */
 	mlx5_hlist_match_cb cb_match; /**< entry match callback. */
 	mlx5_hlist_remove_cb cb_remove; /**< entry remove callback. */
-	struct mlx5_hlist_head heads[];	/**< list head arrays. */
+	struct mlx5_hlist_bucket buckets[] __rte_cache_aligned;
+	/**< list bucket arrays. */
 };
 
 /**
Signature · 1 line
2.25.1
#5 lore raw

PATCH v2 2/2 net/mlx5: optimize the hash list entry memory

In reply to Suanming Mou

Currently, the hash list saves the hash key in the hash entry. And the key is mostly used to get the bucket index only.

Save the entire 64 bits key to the entry will not be a good option if the key is only used to get the bucket index. Since 64 bits costs more memory for the entry, mostly the signature data in the key only uses 32 bits. And in the unregister function, the key in the entry causes extra bucket index calculation.

This commit saves the bucket index to the entry instead of the hash key. For the hash list like table, tag and mreg_copy which save the signature data in the key, the signature data is moved to the resource data struct itself.

---
 drivers/net/mlx5/linux/mlx5_os.c |  5 +--
 drivers/net/mlx5/mlx5.c          |  3 +-
 drivers/net/mlx5/mlx5_flow.c     | 43 +++++++++++++++++++-----
 drivers/net/mlx5/mlx5_flow.h     | 23 +++++++++++--
 drivers/net/mlx5/mlx5_flow_dv.c  | 57 +++++++++++++++++++++++---------
 drivers/net/mlx5/mlx5_utils.c    | 21 +++---------
 drivers/net/mlx5/mlx5_utils.h    |  2 +-
 7 files changed, 106 insertions(+), 48 deletions(-)
drivers/net/mlx5/linux/mlx5_os.c +3 -2
index 4c863db1a7..6c501c0443 100644
@@ -264,7 +264,8 @@ mlx5_alloc_shared_dr(struct mlx5_priv *priv)
 	snprintf(s, sizeof(s), "%s_tags", sh->ibdev_name);
 	sh->tag_table = mlx5_hlist_create(s, MLX5_TAGS_HLIST_ARRAY_SIZE, 0,
 					  MLX5_HLIST_WRITE_MOST,
-					  flow_dv_tag_create_cb, NULL,
+					  flow_dv_tag_create_cb,
+					  flow_dv_tag_match_cb,
 					  flow_dv_tag_remove_cb);
 	if (!sh->tag_table) {
 		DRV_LOG(ERR, "tags with hash creation failed.");
@@ -1564,7 +1565,7 @@ mlx5_dev_spawn(struct rte_device *dpdk_dev,
 						      MLX5_FLOW_MREG_HTABLE_SZ,
 						      0, 0,
 						      flow_dv_mreg_create_cb,
-						      NULL,
+						      flow_dv_mreg_match_cb,
 						      flow_dv_mreg_remove_cb);
 		if (!priv->mreg_cp_tbl) {
 			err = ENOMEM;
drivers/net/mlx5/mlx5.c +2 -1
index ca3667a469..7d3f18c6f7 100644
@@ -1152,7 +1152,8 @@ mlx5_alloc_table_hash_list(struct mlx5_priv *priv __rte_unused)
 	MLX5_ASSERT(sh);
 	snprintf(s, sizeof(s), "%s_flow_table", priv->sh->ibdev_name);
 	sh->flow_tbls = mlx5_hlist_create(s, MLX5_FLOW_TABLE_HLIST_ARRAY_SIZE,
-					  0, 0, flow_dv_tbl_create_cb, NULL,
+					  0, 0, flow_dv_tbl_create_cb,
+					  flow_dv_tbl_match_cb,
 					  flow_dv_tbl_remove_cb);
 	if (!sh->flow_tbls) {
 		DRV_LOG(ERR, "flow tables with hash creation failed.");
drivers/net/mlx5/mlx5_flow.c +35 -8

97 lines not on this page · raw message

drivers/net/mlx5/mlx5_flow.h +20 -3
index a249c292e3..d85dd19929 100644
@@ -437,6 +437,7 @@ struct mlx5_flow_dv_tag_resource {
 	/**< Tag action object. */
 	uint32_t refcnt; /**< Reference counter. */
 	uint32_t idx; /**< Index for the index memory pool. */
+	uint32_t tag_id; /**< Tag ID. */
 };
 
 /*
@@ -509,6 +510,7 @@ struct mlx5_flow_mreg_copy_resource {
 	/* List entry for device flows. */
 	uint32_t idx;
 	uint32_t rix_flow; /* Built flow for copy. */
+	uint32_t mark_id;
 };
 
 /* Table tunnel parameter. */
@@ -532,9 +534,13 @@ struct mlx5_flow_tbl_data_entry {
 	/**< tunnel offload */
 	const struct mlx5_flow_tunnel *tunnel;
 	uint32_t group_id;
-	bool external;
-	bool tunnel_offload; /* Tunnel offlod table or not. */
-	bool is_egress; /**< Egress table. */
+	uint32_t external:1;
+	uint32_t tunnel_offload:1; /* Tunnel offlod table or not. */
+	uint32_t is_egress:1; /**< Egress table. */
+	uint32_t is_transfer:1; /**< Transfer table. */
+	uint32_t dummy:1; /**<  DR table. */
+	uint32_t reserve:27; /**< Reserved to future using. */
+	uint32_t table_id; /**< Table ID. */
 };
 
 /* Sub rdma-core actions list. */
@@ -954,6 +960,8 @@ struct mlx5_flow_tunnel_hub {
 struct tunnel_tbl_entry {
 	struct mlx5_hlist_entry hash;
 	uint32_t flow_table;
+	uint32_t tunnel_id;
+	uint32_t group;
 };
 
 static inline uint32_t
@@ -1416,6 +1424,9 @@ int mlx5_alloc_tunnel_hub(struct mlx5_dev_ctx_shared *sh);
 /* Hash list callbacks for flow tables: */
 struct mlx5_hlist_entry *flow_dv_tbl_create_cb(struct mlx5_hlist *list,
 					       uint64_t key, void *entry_ctx);
+int flow_dv_tbl_match_cb(struct mlx5_hlist *list,
+			 struct mlx5_hlist_entry *entry, uint64_t key,
+			 void *cb_ctx);
 void flow_dv_tbl_remove_cb(struct mlx5_hlist *list,
 			   struct mlx5_hlist_entry *entry);
 struct mlx5_flow_tbl_resource *flow_dv_tbl_resource_get(struct rte_eth_dev *dev,
@@ -1425,6 +1436,9 @@ struct mlx5_flow_tbl_resource *flow_dv_tbl_resource_get(struct rte_eth_dev *dev,
 
 struct mlx5_hlist_entry *flow_dv_tag_create_cb(struct mlx5_hlist *list,
 					       uint64_t key, void *cb_ctx);
+int flow_dv_tag_match_cb(struct mlx5_hlist *list,
+			 struct mlx5_hlist_entry *entry, uint64_t key,
+			 void *cb_ctx);
 void flow_dv_tag_remove_cb(struct mlx5_hlist *list,
 			   struct mlx5_hlist_entry *entry);
 
@@ -1438,6 +1452,9 @@ void flow_dv_modify_remove_cb(struct mlx5_hlist *list,
 
 struct mlx5_hlist_entry *flow_dv_mreg_create_cb(struct mlx5_hlist *list,
 						uint64_t key, void *ctx);
+int flow_dv_mreg_match_cb(struct mlx5_hlist *list,
+			  struct mlx5_hlist_entry *entry, uint64_t key,
+			  void *cb_ctx);
 void flow_dv_mreg_remove_cb(struct mlx5_hlist *list,
 			    struct mlx5_hlist_entry *entry);
 
drivers/net/mlx5/mlx5_flow_dv.c +41 -16

118 lines not on this page · raw message

drivers/net/mlx5/mlx5_utils.c +4 -17
index 42e5d80aee..07373bff02 100644
@@ -25,14 +25,6 @@ mlx5_hlist_default_remove_cb(struct mlx5_hlist *h __rte_unused,
 	mlx5_free(entry);
 }
 
-static int
-mlx5_hlist_default_match_cb(struct mlx5_hlist *h __rte_unused,
-			    struct mlx5_hlist_entry *entry,
-			    uint64_t key, void *ctx __rte_unused)
-{
-	return entry->key != key;
-}
-
 struct mlx5_hlist *
 mlx5_hlist_create(const char *name, uint32_t size, uint32_t entry_size,
 		  uint32_t flags, mlx5_hlist_create_cb cb_create,
@@ -43,7 +35,7 @@ mlx5_hlist_create(const char *name, uint32_t size, uint32_t entry_size,
 	uint32_t alloc_size;
 	uint32_t i;
 
-	if (!size || (!cb_create ^ !cb_remove))
+	if (!size || !cb_match || (!cb_create ^ !cb_remove))
 		return NULL;
 	/* Align to the next power of 2, 32bits integer is enough now. */
 	if (!rte_is_power_of_2(size)) {
@@ -71,7 +63,7 @@ mlx5_hlist_create(const char *name, uint32_t size, uint32_t entry_size,
 	h->direct_key = !!(flags & MLX5_HLIST_DIRECT_KEY);
 	h->write_most = !!(flags & MLX5_HLIST_WRITE_MOST);
 	h->cb_create = cb_create ? cb_create : mlx5_hlist_default_create_cb;
-	h->cb_match = cb_match ? cb_match : mlx5_hlist_default_match_cb;
+	h->cb_match = cb_match;
 	h->cb_remove = cb_remove ? cb_remove : mlx5_hlist_default_remove_cb;
 	for (i = 0; i < act_size; i++)
 		rte_rwlock_init(&h->buckets[i].lock);
@@ -166,7 +158,7 @@ mlx5_hlist_register(struct mlx5_hlist *h, uint64_t key, void *ctx)
 		DRV_LOG(DEBUG, "Can't allocate hash list %s entry.", h->name);
 		goto done;
 	}
-	entry->key = key;
+	entry->idx = idx;
 	entry->ref_cnt = 1;
 	LIST_INSERT_HEAD(first, entry, next);
 	__atomic_add_fetch(&b->gen_cnt, 1, __ATOMIC_ACQ_REL);
@@ -180,12 +172,7 @@ mlx5_hlist_register(struct mlx5_hlist *h, uint64_t key, void *ctx)
 int
 mlx5_hlist_unregister(struct mlx5_hlist *h, struct mlx5_hlist_entry *entry)
 {
-	uint32_t idx;
-
-	if (h->direct_key)
-		idx = (uint32_t)(entry->key & h->mask);
-	else
-		idx = rte_hash_crc_8byte(entry->key, 0) & h->mask;
+	uint32_t idx = entry->idx;
 
 	rte_rwlock_write_lock(&h->buckets[idx].lock);
 	MLX5_ASSERT(entry && entry->ref_cnt && entry->next.le_prev);
drivers/net/mlx5/mlx5_utils.h +1 -1
index 6f2576812b..7a62187f8e 100644
@@ -274,7 +274,7 @@ struct mlx5_hlist;
  */
 struct mlx5_hlist_entry {
 	LIST_ENTRY(mlx5_hlist_entry) next; /* entry pointers in the list. */
-	uint64_t key; /* user defined 'key', could be the hash signature. */
+	uint32_t idx; /* Bucket index the entry belongs to. */
 	uint32_t ref_cnt; /* Reference count. */
 };
 
Signature · 1 line
2.25.1
#6 lore raw
In reply to Suanming Mou

Hi,

Quoted 26 lines

-----Original Message-----
From: Suanming Mou <[email protected]>
Sent: Thursday, December 3, 2020 4:19 AM
To: Slava Ovsiienko <[email protected]>; Matan Azrad <[email protected]>
Cc: Raslan Darawsheh <[email protected]>; [email protected]
Subject: [PATCH v2 0/2] net/mlx5: hash list optimization

This patch set contains the hash list optimization for the lock and memory.

v2:
- Remove the __rte_pack in struct mlx5_hlist_entry.

Suanming Mou (2):
net/mlx5: optimize hash list synchronization
net/mlx5: optimize the hash list entry memory

 drivers/net/mlx5/linux/mlx5_os.c |  5 +-
 drivers/net/mlx5/mlx5.c          |  3 +-
 drivers/net/mlx5/mlx5_flow.c     | 43 +++++++++++++---
 drivers/net/mlx5/mlx5_flow.h     | 23 +++++++--
 drivers/net/mlx5/mlx5_flow_dv.c  | 57 +++++++++++++++------
 drivers/net/mlx5/mlx5_utils.c    | 85 ++++++++++++++++----------------
 drivers/net/mlx5/mlx5_utils.h    | 14 ++++--
 7 files changed, 154 insertions(+), 76 deletions(-)
Quoted 2 lines

--
2.25.1

Series applied to next-net-mlx,

Kindest regards,
Raslan Darawsheh