From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id B85A8A0352; Tue, 5 Nov 2019 09:07:38 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 73ED61BEFD; Tue, 5 Nov 2019 09:02:39 +0100 (CET) Received: from mellanox.co.il (mail-il-dmz.mellanox.com [193.47.165.129]) by dpdk.org (Postfix) with ESMTP id 054651BEA8 for ; Tue, 5 Nov 2019 09:02:18 +0100 (CET) Received: from Internal Mail-Server by MTLPINE1 (envelope-from viacheslavo@mellanox.com) with ESMTPS (AES256-SHA encrypted); 5 Nov 2019 10:02:16 +0200 Received: from pegasus11.mtr.labs.mlnx (pegasus11.mtr.labs.mlnx [10.210.16.104]) by labmailer.mlnx (8.13.8/8.13.8) with ESMTP id xA582Ggr026536; Tue, 5 Nov 2019 10:02:16 +0200 Received: from pegasus11.mtr.labs.mlnx (localhost [127.0.0.1]) by pegasus11.mtr.labs.mlnx (8.14.7/8.14.7) with ESMTP id xA582GnZ030791; Tue, 5 Nov 2019 08:02:16 GMT Received: (from viacheslavo@localhost) by pegasus11.mtr.labs.mlnx (8.14.7/8.14.7/Submit) id xA582G40030790; Tue, 5 Nov 2019 08:02:16 GMT X-Authentication-Warning: pegasus11.mtr.labs.mlnx: viacheslavo set sender to viacheslavo@mellanox.com using -f From: Viacheslav Ovsiienko To: dev@dpdk.org Cc: matan@mellanox.com, rasland@mellanox.com, thomas@monjalon.net, orika@mellanox.com, Yongseok Koh Date: Tue, 5 Nov 2019 08:01:52 +0000 Message-Id: <1572940915-29416-18-git-send-email-viacheslavo@mellanox.com> X-Mailer: git-send-email 1.8.3.1 In-Reply-To: <1572940915-29416-1-git-send-email-viacheslavo@mellanox.com> References: <1572940915-29416-1-git-send-email-viacheslavo@mellanox.com> Subject: [dpdk-dev] [PATCH 17/20] net/mlx5: add simple hash table X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" 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 Signed-off-by: Viacheslav Ovsiienko Acked-by: Matan Azrad --- 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 +#include +#include #include #include #include -#include -#include -#include +#include #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