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 842F4A04A2; Tue, 5 Nov 2019 16:29:49 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 4E63A1BF55; Tue, 5 Nov 2019 16:29:49 +0100 (CET) Received: from EUR04-VI1-obe.outbound.protection.outlook.com (mail-eopbgr80074.outbound.protection.outlook.com [40.107.8.74]) by dpdk.org (Postfix) with ESMTP id 69BB61BED9 for ; Tue, 5 Nov 2019 16:29:48 +0100 (CET) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=Oj1KEo7FTVb/PDzM4rHgJWHqIUhodA15nF+Dl5XMs4mi0TETIWW/gUha46ovf6RHtqZWTnpCgYuRFIhxOarxl+hdBu86JMkPcO17xFm/xyjWezP15BTU3jhY6yJ2YVwqLdKbKRkd1kQX1WRExGCW4W6vD2tvU/cVwlmtdDtbp9C27Sc2UzKvynKgF8Gh+xAH8fy2q991pmLGqOUJEVvTqnQ3WPOY4eCzYJkj6lcMobn3ruHom1DPill+FRqTPmeb0wlRRGHKZIFOVi/eFnjUzhalJf/ScdNrebUgoqhK+Q0y3K+h7szAiMocLofYk+S1xlpdO+1R+HV5f3DtVKyafQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=VCGa74hQu+YHwGyRECxOSOVswwIi4lnUk6ZI7f1aUzU=; b=nfDLOT6W7XUw1p/dCk76zPb2ZScqDme/+4TiJU8Wep/vh+iuEQRB7NSuEBPe/izmikAI3+pbaPdoLi7bBRUyiI/xSJyIgrVMtAJh4P7yHxfFqh9X1p+YGoq4f+LF9UacyjPeu6sRlUmpaZLWKPdbQXXxQfL9Y1zgos4CvOEoF06keyc3xsDpfOQ5QCANloZtfdth5SrqGFO4NlidLUI8Zr7tlt9nvtnbDsofpKRka0g1ASfb98r+yGl79ZP/xCa7DXaeqU+A6R99PPHXTfVdywJ1ZehmVSNI65a9chVz4YweCP65styYBBZ7oE2XLooIEOXymrjxbqrwQH4NuPqbcw== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=mellanox.com; dmarc=pass action=none header.from=mellanox.com; dkim=pass header.d=mellanox.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=Mellanox.com; s=selector2; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=VCGa74hQu+YHwGyRECxOSOVswwIi4lnUk6ZI7f1aUzU=; b=cCrfQjl/PYsWg5tETclB7dZ2PKT3ZXdS7v9fBb2rfEc06N/yMeh0uL0k6Qi217I1XWqsX94nRhsaIKMhzIp5y8XxHX9zn3Kha/7lqTecA7x9sVwFcbtYaPd4igfQZR2nqcR/GlGXgbL94/AkVRa0lSHjBK+LviTyNalmL6SXNNs= Received: from AM4PR05MB3265.eurprd05.prod.outlook.com (10.171.188.154) by AM4PR05MB3314.eurprd05.prod.outlook.com (10.171.191.24) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2408.24; Tue, 5 Nov 2019 15:29:41 +0000 Received: from AM4PR05MB3265.eurprd05.prod.outlook.com ([fe80::9940:94f2:db23:aa2c]) by AM4PR05MB3265.eurprd05.prod.outlook.com ([fe80::9940:94f2:db23:aa2c%4]) with mapi id 15.20.2408.024; Tue, 5 Nov 2019 15:29:41 +0000 From: Slava Ovsiienko To: Bing Zhao , Ori Kam , Raslan Darawsheh , "dev@dpdk.org" Thread-Topic: [PATCH] net/mlx5: introduce mlx5 hash list Thread-Index: AQHVk+2hhBHtZYKbK0qrE1Jzz4dDFKd8s7og Date: Tue, 5 Nov 2019 15:29:41 +0000 Message-ID: References: <1572967680-93338-1-git-send-email-bingz@mellanox.com> In-Reply-To: <1572967680-93338-1-git-send-email-bingz@mellanox.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: authentication-results: spf=none (sender IP is ) smtp.mailfrom=viacheslavo@mellanox.com; x-originating-ip: [95.164.10.10] x-ms-publictraffictype: Email x-ms-office365-filtering-ht: Tenant x-ms-office365-filtering-correlation-id: 5d115991-9da0-4ec5-07ef-08d76204fa84 x-ms-traffictypediagnostic: AM4PR05MB3314:|AM4PR05MB3314: x-ld-processed: a652971c-7d2e-4d9b-a6a4-d149256f461b,ExtFwd x-ms-exchange-transport-forked: True x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:1388; x-forefront-prvs: 0212BDE3BE x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(4636009)(366004)(199004)(189003)(13464003)(55016002)(64756008)(76116006)(110136005)(25786009)(86362001)(66476007)(2906002)(7736002)(8936002)(26005)(81166006)(81156014)(229853002)(6506007)(52536014)(76176011)(7696005)(74316002)(33656002)(5660300002)(66066001)(99286004)(486006)(30864003)(71190400001)(71200400001)(6116002)(446003)(3846002)(9686003)(11346002)(102836004)(256004)(14444005)(53546011)(2501003)(8676002)(305945005)(66446008)(498600001)(14454004)(186003)(476003)(66556008)(6246003)(6436002)(66946007); DIR:OUT; SFP:1101; SCL:1; SRVR:AM4PR05MB3314; H:AM4PR05MB3265.eurprd05.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:1; MX:1; received-spf: None (protection.outlook.com: mellanox.com does not designate permitted sender hosts) x-ms-exchange-senderadcheck: 1 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: xxrtLVbO8wOUo8kOU6Kd6i4z1ia3iDQddtUKznMw5pShynH/4krkh6QFs8wUTu3my/jHFrqy5jRid5YJ98R1MdhYz3L/HwixXZYU9wd2x/B9S0viYpsszria0n1fCJM3xW1w3HGKP5PhBqpXAkJ9tJNx9dvG6zdE55e48AIBTKjAroJNCpQTJf/cNj19dZUs9NfQhYWOWenCSpeKsa3Fd9KSqzAHICBVpFSI6YnN2mN+niHdvLitszRmWbjeaWttH80zDhQW6X+MDD8/fGoXA37UF3Q83zB4oN9KfYlNtvZxLG33ql+Dv6oMXZUJPmhlZgbvplnnuPKpb/V/Tmfd5Z8KjqGo2bu5HH4Zpvren+LRz5DLWqj7uVo0Lc7QEN/Z+5DDFriOCaHSfKuYtvYCgWZrjoAE8yU7iXM0zgBGvaD5q04G57kidwR+wkCeuIxY Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: Mellanox.com X-MS-Exchange-CrossTenant-Network-Message-Id: 5d115991-9da0-4ec5-07ef-08d76204fa84 X-MS-Exchange-CrossTenant-originalarrivaltime: 05 Nov 2019 15:29:41.6973 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: a652971c-7d2e-4d9b-a6a4-d149256f461b X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-CrossTenant-userprincipalname: hMtEllJBWLp36C3Amb2wVWP9WHJTtln0ZP1u3smNyidNTqCAE8Y2fIPE0b5uj7ZbBr4C7YdFzpnrvP2IoHe/mPk6MOxQ91SukGUCgNJHMic= X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM4PR05MB3314 Subject: Re: [dpdk-dev] [PATCH] net/mlx5: introduce mlx5 hash list 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" > -----Original Message----- > From: Bing Zhao > Sent: Tuesday, November 5, 2019 17:28 > To: Ori Kam ; Slava Ovsiienko > ; Raslan Darawsheh > ; dev@dpdk.org > Subject: [PATCH] net/mlx5: introduce mlx5 hash list >=20 > Introduce simple hash list to the mlx5 utilities. User can define its own= data > structure containing the mlx5_hlist_entry and create the hash list table = via > the creation interface. Then the entry will be inserted into the table an= d > linked to the corresponding list head. User should guarantee there is no > collision of the key and provide a callback function to handle all the > remaining entries in the table when destroying the hash list. User should > define a proper number of the list heads in the table in order to get a b= etter > performance. The LSB of the 'key' is used to calculate the index of the h= ead > in the list heads array. > This implementation is not multi-threads safe right now. >=20 > Signed-off-by: Bing Zhao Acked-by: Viacheslav Ovsiienko > --- > drivers/net/mlx5/Makefile | 1 + > drivers/net/mlx5/meson.build | 1 + > drivers/net/mlx5/mlx5_utils.c | 126 > ++++++++++++++++++++++++++++++++++++++++++ > drivers/net/mlx5/mlx5_utils.h | 106 > ++++++++++++++++++++++++++++++++++- > 4 files changed, 232 insertions(+), 2 deletions(-) create mode 100644 > drivers/net/mlx5/mlx5_utils.c >=20 > diff --git a/drivers/net/mlx5/Makefile b/drivers/net/mlx5/Makefile index > dae5b9f..44cc26a 100644 > --- a/drivers/net/mlx5/Makefile > +++ b/drivers/net/mlx5/Makefile > @@ -37,6 +37,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_MLX5_PMD) +=3D > mlx5_flow_verbs.c > SRCS-$(CONFIG_RTE_LIBRTE_MLX5_PMD) +=3D mlx5_mp.c > SRCS-$(CONFIG_RTE_LIBRTE_MLX5_PMD) +=3D mlx5_nl.c > SRCS-$(CONFIG_RTE_LIBRTE_MLX5_PMD) +=3D mlx5_devx_cmds.c > +SRCS-$(CONFIG_RTE_LIBRTE_MLX5_PMD) +=3D mlx5_utils.c >=20 > ifeq ($(CONFIG_RTE_IBVERBS_LINK_DLOPEN),y) > INSTALL-$(CONFIG_RTE_LIBRTE_MLX5_PMD)-lib +=3D $(LIB_GLUE) diff --git > a/drivers/net/mlx5/meson.build b/drivers/net/mlx5/meson.build index > 02494cf..344f109 100644 > --- a/drivers/net/mlx5/meson.build > +++ b/drivers/net/mlx5/meson.build > @@ -58,6 +58,7 @@ if build > 'mlx5_txq.c', > 'mlx5_vlan.c', > 'mlx5_devx_cmds.c', > + 'mlx5_utils.c', > ) > if (dpdk_conf.has('RTE_ARCH_X86_64') > or dpdk_conf.has('RTE_ARCH_ARM64') > diff --git a/drivers/net/mlx5/mlx5_utils.c b/drivers/net/mlx5/mlx5_utils.= c > new file mode 100644 index 0000000..0181f49 > --- /dev/null > +++ b/drivers/net/mlx5/mlx5_utils.c > @@ -0,0 +1,126 @@ > +/* SPDX-License-Identifier: BSD-3-Clause > + * Copyright 2019 Mellanox Technologies, Ltd */ > + > +#include > + > +#include "mlx5_utils.h" > + > +struct mlx5_hlist * > +mlx5_hlist_create(char *name, uint64_t size, > +mlx5_hlist_destroy_callback_fn cb) { > + struct mlx5_hlist *h; > + uint64_t act_size; > + uint64_t alloc_size; > + > + if (!size) > + return NULL; > + /* If the low 32B is power of 2, then the 64B integer is too. */ > + if (!rte_is_power_of_2((uint32_t)size)) { > + act_size =3D rte_align64pow2(size); > + DRV_LOG(WARNING, "Size 0x%" PRIX64 " is not power of 2, > will " > + "be aligned to 0x%" PRIX64 ".\n", size, act_size); > + } else { > + act_size =3D size; > + } > + alloc_size =3D sizeof(struct mlx5_hlist) + > + sizeof(struct mlx5_hlist_head) * act_size; > + /* Using zmalloc, then no need to initialize the heads. */ > + h =3D rte_zmalloc(name, alloc_size, RTE_CACHE_LINE_SIZE); > + if (!h) { > + DRV_LOG(ERR, "No memory for hash list %s creation\n", > + name ? name : "None"); > + return NULL; > + } > + if (name) > + snprintf(h->name, MLX5_HLIST_NAMESIZE, "%s", name); > + if (!cb) > + DRV_LOG(WARNING, "No callback function is specified, will > use " > + "rte_free when destroying hlist %p %s\n", > + (void *)h, h->name); > + else > + h->cb =3D cb; > + h->table_sz =3D act_size; > + h->mask =3D act_size - 1; > + DRV_LOG(DEBUG, "Hash list with %s size 0x%" PRIX64 ", callback " > + "0x%" PRIX64 "is created.\n", > + h->name, act_size, (uint64_t)(uintptr_t)cb); > + return h; > +} > + > +struct mlx5_hlist_entry * > +mlx5_hlist_lookup(struct mlx5_hlist *h, uint64_t key) { > + uint64_t idx; > + struct mlx5_hlist_head *first; > + struct mlx5_hlist_entry *node; > + > + assert(h); > + idx =3D key & h->mask; > + first =3D &h->heads[idx]; > + LIST_FOREACH(node, first, next) { > + if (node->key =3D=3D key) > + return node; > + } > + return NULL; > +} > + > +int > +mlx5_hlist_insert(struct mlx5_hlist *h, struct mlx5_hlist_entry *entry) > +{ > + uint64_t idx; > + struct mlx5_hlist_head *first; > + struct mlx5_hlist_entry *node; > + > + assert(h && entry); > + idx =3D entry->key & h->mask; > + first =3D &h->heads[idx]; > + /* No need to reuse the lookup function. */ > + LIST_FOREACH(node, first, next) { > + if (node->key =3D=3D entry->key) > + 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) > +{ > + assert(entry && entry->next.le_prev); > + LIST_REMOVE(entry, next); > + /* Set to NULL to get rid of removing action for more than once. */ > + entry->next.le_prev =3D NULL; > +} > + > +void > +mlx5_hlist_destroy(struct mlx5_hlist *h) { > + uint64_t idx; > + struct mlx5_hlist_entry *entry; > + mlx5_hlist_destroy_callback_fn cb; > + > + assert(h); > + cb =3D h->cb; > + for (idx =3D 0; idx < h->table_sz; ++idx) { > + /* no LIST_FOREACH_SAFE, using while instead */ > + while (!LIST_EMPTY(&h->heads[idx])) { > + entry =3D LIST_FIRST(&h->heads[idx]); > + LIST_REMOVE(entry, next); > + /* > + * The owner of whole element which contains data > entry > + * is the user, so it's the user's duty to do the clean > + * up and the free work because someone may not > put the > + * hlist entry at the beginning(suggested to locate at > + * the beginning). Or else the default free function > + * will be used. > + */ > + if (cb) > + h->cb(entry); > + else > + rte_free(entry); > + } > + } > + rte_free(h); > +} > diff --git a/drivers/net/mlx5/mlx5_utils.h b/drivers/net/mlx5/mlx5_utils.= h > index 97092c7..81da50d 100644 > --- a/drivers/net/mlx5/mlx5_utils.h > +++ b/drivers/net/mlx5/mlx5_utils.h > @@ -151,13 +151,13 @@ > snprintf(name, sizeof(name), __VA_ARGS__) >=20 > /** > - * Return nearest power of two above input value. > + * Return logarithm of the nearest power of two above input value. > * > * @param v > * Input value. > * > * @return > - * Nearest power of two above input value. > + * Logarithm of the nearest power of two above input value. > */ > static inline unsigned int > log2above(unsigned int v) > @@ -170,4 +170,106 @@ > return l + r; > } >=20 > +/** Maximum size of string for naming the hlist table. */ > +#define MLX5_HLIST_NAMESIZE 32 > + > +/** > + * Structure of the entry in the hash list, user should define its own > +struct > + * that contains this in order to store the data. The 'key' is 64-bits > +right > + * now and its user's responsibility to guarantee there is no collision. > + */ > +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. */ > +}; > + > +/** Structure for hash head. */ > +LIST_HEAD(mlx5_hlist_head, mlx5_hlist_entry); > + > +/** Type of function that is used to handle the data before freeing. */ > +typedef void (*mlx5_hlist_destroy_callback_fn)(void *p); > + > +/** hash list table structure */ > +struct mlx5_hlist { > + char name[MLX5_HLIST_NAMESIZE]; /**< Name of the hash list. */ > + /**< number of heads, need to be power of 2. */ > + uint64_t table_sz; > + /**< mask to get the index of the list heads. */ > + uint64_t mask; > + /**< The callback function before free when destroying hash list. */ > + mlx5_hlist_destroy_callback_fn cb; > + struct mlx5_hlist_head heads[]; /**< list head arrays. */ > +}; > + > +/** > + * Create a hash list table, the user can specify the list heads array > +size > + * of the table, now the size should be a power of 2 in order to get > +better > + * distribution for the entries. Each entry is a part of the whole data > +element > + * and the caller should be responsible for the data element's > +allocation and > + * cleanup / free. > + * > + * @param name > + * Name of the hash list(optional). > + * @param size > + * Heads array size of the hash list. > + * @param cb > + * Callback function for each inserted entries when destroying the has= h list. > + * > + * @return > + * Pointer of the hash list table created, NULL on failure. > + */ > +struct mlx5_hlist *mlx5_hlist_create(char *name, uint64_t size, > + mlx5_hlist_destroy_callback_fn cb); > + > +/** > + * Search an entry matching the key. > + * > + * @param h > + * Pointer to the hast list table. > + * @param key > + * Key for the searching entry. > + * > + * @return > + * Pointer of the hlist entry if found, NULL otherwise. > + */ > +struct mlx5_hlist_entry *mlx5_hlist_lookup(struct mlx5_hlist *h, > +uint64_t key); > + > +/** > + * Insert an entry to the hash list table, the entry is only part of > +whole data > + * element and a 64B key is used for matching. User should construct > +the key or > + * give a calculated hash signature and guarantee there is no collision. > + * > + * @param h > + * Pointer to the hast list table. > + * @param entry > + * Entry to be inserted into the hash list table. > + * > + * @return > + * - zero for success. > + * - -EEXIST if the entry is already inserted. > + */ > +int mlx5_hlist_insert(struct mlx5_hlist *h, struct mlx5_hlist_entry > +*entry); > + > +/** > + * Remove an entry from the hash list table. User should guarantee the > +validity > + * of the entry. > + * > + * @param h > + * Pointer to the hast list table. (not used) > + * @param entry > + * Entry to be removed from the hash list table. > + */ > +void mlx5_hlist_remove(struct mlx5_hlist *h __rte_unused, > + struct mlx5_hlist_entry *entry); > + > +/** > + * Destroy the hash list table, all the entries already inserted into > +the lists > + * will be handled by the callback function provided by the user > +(including > + * free if needed) before the table is freed. > + * > + * @param h > + * Pointer to the hast list table. > + */ > +void mlx5_hlist_destroy(struct mlx5_hlist *h); > + > #endif /* RTE_PMD_MLX5_UTILS_H_ */ > -- > 1.8.3.1