DPDK patches and discussions
 help / color / Atom feed
From: Viacheslav Ovsiienko <viacheslavo@mellanox.com>
To: dev@dpdk.org
Cc: matan@mellanox.com, rasland@mellanox.com, thomas@monjalon.net,
	orika@mellanox.com, Yongseok Koh <yskoh@mellanox.com>
Subject: [dpdk-dev] [PATCH 17/20] net/mlx5: add simple hash table
Date: Tue,  5 Nov 2019 08:01:52 +0000
Message-ID: <1572940915-29416-18-git-send-email-viacheslavo@mellanox.com> (raw)
In-Reply-To: <1572940915-29416-1-git-send-email-viacheslavo@mellanox.com>

Simple hash table is added. Hash function is modulo operator and no
conflict is allowed. Key must be unique. It would be useful in managing
a resource pool having finite unique keys, e.g. flow table entry with
unique flow ID.

Signed-off-by: Yongseok Koh <yskoh@mellanox.com>
Signed-off-by: Viacheslav Ovsiienko <viacheslavo@mellanox.com>
Acked-by: Matan Azrad <matan@mellanox.com>
---
 drivers/net/mlx5/mlx5_utils.h | 115 ++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 112 insertions(+), 3 deletions(-)

diff --git a/drivers/net/mlx5/mlx5_utils.h b/drivers/net/mlx5/mlx5_utils.h
index 97092c7..5a7de62 100644
--- a/drivers/net/mlx5/mlx5_utils.h
+++ b/drivers/net/mlx5/mlx5_utils.h
@@ -6,12 +6,13 @@
 #ifndef RTE_PMD_MLX5_UTILS_H_
 #define RTE_PMD_MLX5_UTILS_H_
 
+#include <assert.h>
+#include <errno.h>
+#include <limits.h>
 #include <stddef.h>
 #include <stdint.h>
 #include <stdio.h>
-#include <limits.h>
-#include <assert.h>
-#include <errno.h>
+#include <sys/queue.h>
 
 #include "mlx5_defs.h"
 
@@ -150,6 +151,114 @@
 	\
 	snprintf(name, sizeof(name), __VA_ARGS__)
 
+/*
+ * Simple Hash Table for Key-Data pair.
+ *
+ * Key must be unique. No conflict is allowed.
+ *
+ * mlx5_shtable_entry could be a part of the data structure to store, e.g.,
+ *
+ *   struct DATA {
+ *     struct mlx5_shtable_entry entry;
+ *     custom_data_t custom_data;
+ *   };
+ *
+ * And the actual hash table should be defined as,
+ *
+ *   struct mlx5_shtable_bucket TABLE[TABLE_SZ];
+ *
+ * Hash function is simply modulo (%) operator for now.
+ */
+
+/* Data entry for hash table. */
+struct mlx5_shtable_entry {
+	LIST_ENTRY(mlx5_shtable_entry) next;
+	uint32_t key;
+};
+
+/* Structure for hash bucket. */
+LIST_HEAD(mlx5_shtable_bucket, mlx5_shtable_entry);
+
+/**
+ * Search an entry matching the key.
+ *
+ * @param htable
+ *   Pointer to the table.
+ * @param tbl_sz
+ *   Size of the table.
+ * @param key
+ *   Key for the searching entry.
+ *
+ * @return
+ *   Pointer of the table entry if found, NULL otherwise.
+ */
+static inline struct mlx5_shtable_entry *
+mlx5_shtable_search(struct mlx5_shtable_bucket *htable, int tbl_sz,
+		    uint32_t key)
+{
+	struct mlx5_shtable_bucket *bucket;
+	struct mlx5_shtable_entry *node;
+	uint32_t idx;
+
+	idx = key % tbl_sz;
+	bucket = &htable[idx];
+	LIST_FOREACH(node, bucket, next) {
+		if (node->key == key)
+			return node;
+	}
+	return NULL;
+}
+
+/**
+ * Insert an entry.
+ *
+ * @param htable
+ *   Pointer to the table.
+ * @param tbl_sz
+ *   Size of the table.
+ * @param key
+ *   Key for the searching entry.
+ *
+ * @return
+ *   0 if succeed, -EEXIST if conflict.
+ */
+static inline int
+mlx5_shtable_insert(struct mlx5_shtable_bucket *htable, int tbl_sz,
+		    struct mlx5_shtable_entry *ent)
+{
+	struct mlx5_shtable_bucket *bucket;
+	struct mlx5_shtable_entry *node;
+	uint32_t idx;
+
+	idx = ent->key % tbl_sz;
+	bucket = &htable[idx];
+	LIST_FOREACH(node, bucket, next) {
+		if (node->key == ent->key)
+			return -EEXIST;
+	}
+	LIST_INSERT_HEAD(bucket, ent, next);
+	return 0;
+}
+
+/**
+ * Revmoe an entry from its table.
+ *
+ * @param htable
+ *   Pointer to the table.
+ * @param tbl_sz
+ *   Size of the table.
+ * @param key
+ *   Key for the searching entry.
+ */
+static inline void
+mlx5_shtable_remove(struct mlx5_shtable_entry *ent)
+{
+	/* Check if entry is not attached. */
+	if (!ent->next.le_prev)
+		return;
+	LIST_REMOVE(ent, next);
+}
+
 /**
  * Return nearest power of two above input value.
  *
-- 
1.8.3.1


  parent reply index

Thread overview: 64+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-11-05  8:01 [dpdk-dev] [PATCH 00/20] net/mlx5: implement extensive metadata feature Viacheslav Ovsiienko
2019-11-05  8:01 ` [dpdk-dev] [PATCH 01/20] net/mlx5: convert internal tag endianness Viacheslav Ovsiienko
2019-11-05  8:01 ` [dpdk-dev] [PATCH 02/20] net/mlx5: update modify header action translator Viacheslav Ovsiienko
2019-11-05  8:01 ` [dpdk-dev] [PATCH 03/20] net/mlx5: add metadata register copy Viacheslav Ovsiienko
2019-11-05  8:01 ` [dpdk-dev] [PATCH 04/20] net/mlx5: refactor flow structure Viacheslav Ovsiienko
2019-11-05  8:01 ` [dpdk-dev] [PATCH 05/20] net/mlx5: update flow functions Viacheslav Ovsiienko
2019-11-05  8:01 ` [dpdk-dev] [PATCH 06/20] net/mlx5: update meta register matcher set Viacheslav Ovsiienko
2019-11-05  8:01 ` [dpdk-dev] [PATCH 07/20] net/mlx5: rename structure and function Viacheslav Ovsiienko
2019-11-05  8:01 ` [dpdk-dev] [PATCH 08/20] net/mlx5: check metadata registers availability Viacheslav Ovsiienko
2019-11-05  8:01 ` [dpdk-dev] [PATCH 09/20] net/mlx5: add devarg for extensive metadata support Viacheslav Ovsiienko
2019-11-05  8:01 ` [dpdk-dev] [PATCH 10/20] net/mlx5: adjust shared register according to mask Viacheslav Ovsiienko
2019-11-05  8:01 ` [dpdk-dev] [PATCH 11/20] net/mlx5: check the maximal modify actions number Viacheslav Ovsiienko
2019-11-05  8:01 ` [dpdk-dev] [PATCH 12/20] net/mlx5: update metadata register id query Viacheslav Ovsiienko
2019-11-05  8:01 ` [dpdk-dev] [PATCH 13/20] net/mlx5: add flow tag support Viacheslav Ovsiienko
2019-11-05  8:01 ` [dpdk-dev] [PATCH 14/20] net/mlx5: extend flow mark support Viacheslav Ovsiienko
2019-11-05  8:01 ` [dpdk-dev] [PATCH 15/20] net/mlx5: extend flow meta data support Viacheslav Ovsiienko
2019-11-05  8:01 ` [dpdk-dev] [PATCH 16/20] net/mlx5: add meta data support to Rx datapath Viacheslav Ovsiienko
2019-11-05  8:01 ` Viacheslav Ovsiienko [this message]
2019-11-05  8:01 ` [dpdk-dev] [PATCH 18/20] net/mlx5: introduce flow splitters chain Viacheslav Ovsiienko
2019-11-05  8:01 ` [dpdk-dev] [PATCH 19/20] net/mlx5: split Rx flows to provide metadata copy Viacheslav Ovsiienko
2019-11-05  8:01 ` [dpdk-dev] [PATCH 20/20] net/mlx5: add metadata register copy table Viacheslav Ovsiienko
2019-11-05  9:35 ` [dpdk-dev] [PATCH 00/20] net/mlx5: implement extensive metadata feature Matan Azrad
2019-11-06 17:37 ` [dpdk-dev] [PATCH v2 00/19] " Viacheslav Ovsiienko
2019-11-06 17:37   ` [dpdk-dev] [PATCH v2 01/19] net/mlx5: convert internal tag endianness Viacheslav Ovsiienko
2019-11-06 17:37   ` [dpdk-dev] [PATCH v2 02/19] net/mlx5: update modify header action translator Viacheslav Ovsiienko
2019-11-06 17:37   ` [dpdk-dev] [PATCH v2 03/19] net/mlx5: add metadata register copy Viacheslav Ovsiienko
2019-11-06 17:37   ` [dpdk-dev] [PATCH v2 04/19] net/mlx5: refactor flow structure Viacheslav Ovsiienko
2019-11-06 17:37   ` [dpdk-dev] [PATCH v2 05/19] net/mlx5: update flow functions Viacheslav Ovsiienko
2019-11-06 17:37   ` [dpdk-dev] [PATCH v2 06/19] net/mlx5: update meta register matcher set Viacheslav Ovsiienko
2019-11-06 17:37   ` [dpdk-dev] [PATCH v2 07/19] net/mlx5: rename structure and function Viacheslav Ovsiienko
2019-11-06 17:37   ` [dpdk-dev] [PATCH v2 08/19] net/mlx5: check metadata registers availability Viacheslav Ovsiienko
2019-11-06 17:37   ` [dpdk-dev] [PATCH v2 09/19] net/mlx5: add devarg for extensive metadata support Viacheslav Ovsiienko
2019-11-06 17:37   ` [dpdk-dev] [PATCH v2 10/19] net/mlx5: adjust shared register according to mask Viacheslav Ovsiienko
2019-11-06 17:37   ` [dpdk-dev] [PATCH v2 11/19] net/mlx5: check the maximal modify actions number Viacheslav Ovsiienko
2019-11-06 17:37   ` [dpdk-dev] [PATCH v2 12/19] net/mlx5: update metadata register id query Viacheslav Ovsiienko
2019-11-06 17:37   ` [dpdk-dev] [PATCH v2 13/19] net/mlx5: add flow tag support Viacheslav Ovsiienko
2019-11-06 17:37   ` [dpdk-dev] [PATCH v2 14/19] net/mlx5: extend flow mark support Viacheslav Ovsiienko
2019-11-06 17:37   ` [dpdk-dev] [PATCH v2 15/19] net/mlx5: extend flow meta data support Viacheslav Ovsiienko
2019-11-06 17:37   ` [dpdk-dev] [PATCH v2 16/19] net/mlx5: add meta data support to Rx datapath Viacheslav Ovsiienko
2019-11-06 17:37   ` [dpdk-dev] [PATCH v2 17/19] net/mlx5: introduce flow splitters chain Viacheslav Ovsiienko
2019-11-06 17:37   ` [dpdk-dev] [PATCH v2 18/19] net/mlx5: split Rx flows to provide metadata copy Viacheslav Ovsiienko
2019-11-06 17:37   ` [dpdk-dev] [PATCH v2 19/19] net/mlx5: add metadata register copy table Viacheslav Ovsiienko
2019-11-07 17:09 ` [dpdk-dev] [PATCH v3 00/19] net/mlx5: implement extensive metadata feature Viacheslav Ovsiienko
2019-11-07 17:09   ` [dpdk-dev] [PATCH v3 01/19] net/mlx5: convert internal tag endianness Viacheslav Ovsiienko
2019-11-07 17:09   ` [dpdk-dev] [PATCH v3 02/19] net/mlx5: update modify header action translator Viacheslav Ovsiienko
2019-11-07 17:09   ` [dpdk-dev] [PATCH v3 03/19] net/mlx5: add metadata register copy Viacheslav Ovsiienko
2019-11-07 17:09   ` [dpdk-dev] [PATCH v3 04/19] net/mlx5: refactor flow structure Viacheslav Ovsiienko
2019-11-07 17:09   ` [dpdk-dev] [PATCH v3 05/19] net/mlx5: update flow functions Viacheslav Ovsiienko
2019-11-07 17:09   ` [dpdk-dev] [PATCH v3 06/19] net/mlx5: update meta register matcher set Viacheslav Ovsiienko
2019-11-07 17:09   ` [dpdk-dev] [PATCH v3 07/19] net/mlx5: rename structure and function Viacheslav Ovsiienko
2019-11-07 17:09   ` [dpdk-dev] [PATCH v3 08/19] net/mlx5: check metadata registers availability Viacheslav Ovsiienko
2019-11-07 17:09   ` [dpdk-dev] [PATCH v3 09/19] net/mlx5: add devarg for extensive metadata support Viacheslav Ovsiienko
2019-11-07 17:09   ` [dpdk-dev] [PATCH v3 10/19] net/mlx5: adjust shared register according to mask Viacheslav Ovsiienko
2019-11-07 17:09   ` [dpdk-dev] [PATCH v3 11/19] net/mlx5: check the maximal modify actions number Viacheslav Ovsiienko
2019-11-07 17:09   ` [dpdk-dev] [PATCH v3 12/19] net/mlx5: update metadata register id query Viacheslav Ovsiienko
2019-11-07 17:09   ` [dpdk-dev] [PATCH v3 13/19] net/mlx5: add flow tag support Viacheslav Ovsiienko
2019-11-07 17:09   ` [dpdk-dev] [PATCH v3 14/19] net/mlx5: extend flow mark support Viacheslav Ovsiienko
2019-11-07 17:10   ` [dpdk-dev] [PATCH v3 15/19] net/mlx5: extend flow meta data support Viacheslav Ovsiienko
2019-11-07 17:10   ` [dpdk-dev] [PATCH v3 16/19] net/mlx5: add meta data support to Rx datapath Viacheslav Ovsiienko
2019-11-25 14:24     ` David Marchand
2019-11-07 17:10   ` [dpdk-dev] [PATCH v3 17/19] net/mlx5: introduce flow splitters chain Viacheslav Ovsiienko
2019-11-07 17:10   ` [dpdk-dev] [PATCH v3 18/19] net/mlx5: split Rx flows to provide metadata copy Viacheslav Ovsiienko
2019-11-07 17:10   ` [dpdk-dev] [PATCH v3 19/19] net/mlx5: add metadata register copy table Viacheslav Ovsiienko
2019-11-07 22:46   ` [dpdk-dev] [PATCH v3 00/19] net/mlx5: implement extensive metadata feature Raslan Darawsheh

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=1572940915-29416-18-git-send-email-viacheslavo@mellanox.com \
    --to=viacheslavo@mellanox.com \
    --cc=dev@dpdk.org \
    --cc=matan@mellanox.com \
    --cc=orika@mellanox.com \
    --cc=rasland@mellanox.com \
    --cc=thomas@monjalon.net \
    --cc=yskoh@mellanox.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

DPDK patches and discussions

Archives are clonable:
	git clone --mirror http://inbox.dpdk.org/dev/0 dev/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 dev dev/ http://inbox.dpdk.org/dev \
		dev@dpdk.org
	public-inbox-index dev


Newsgroup available over NNTP:
	nntp://inbox.dpdk.org/inbox.dpdk.dev


AGPL code for this site: git clone https://public-inbox.org/ public-inbox