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 D83E9A0353; Tue, 5 Nov 2019 14:28:24 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 97E9F1BE95; Tue, 5 Nov 2019 14:28:24 +0100 (CET) Received: from EUR03-AM5-obe.outbound.protection.outlook.com (mail-eopbgr30072.outbound.protection.outlook.com [40.107.3.72]) by dpdk.org (Postfix) with ESMTP id 319511BE0C for ; Tue, 5 Nov 2019 14:28:24 +0100 (CET) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=EeP7fS4xOtR+Gzb8gPS4NHxiTmHNxUY609A7kA3VvUlw/GIpKqpdOcxLMCsaUH6IwxIkGEppag0fGRUdxsyL/SKnU7gDtNESrsvR3zJ4YHmuDcdULUYpqnt66ZfScwUn7OzpJJ8ATYAQZ4SwMp3t9cht/ZSeo9rgHFPF+s5ZLZm6aX/Y1B0FW3R0+YZIKKabOUYWEbPksG/z83LgN1Ovo2qisA3eYhCwn1pxcF/3xc11VNP315VQYT7PWGTZYUvK1tbX9yFrAVeer2p7sYLaoO9rAv7RYySFsF/PsVGIUS6swqPrgk7Dn5GbhBHPXSoM/njQEO53FPH/fz/kgnGWcQ== 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=c22MRx5eaHb5UPQBnOGu10jZ1H886iAJgqwqqD74Ocs=; b=G32Nxe46x6rmGu9t7B4NNeYHMwJEMhHrIEq1dPmL2i71HVlLhz4AokPGreKs9p8/4hlUEdfX19DO4Az6zB/qr97s5EhaoRV9qTRRjyMKm90T6Iuyjvs66VoJPUuKEkhUE4hv2efZmS1owFK5QjtRwkzBmA8bDF3jGO/ROYYEyt+7To9fqq0LQuFHN9E2ChVToA+lipWec9Skg026A/gh6bup7iPN9d8yB/Htu5s5j++bwIkj3jbdaiKHQQp1XWtlvrv27HEy27YWJcNtZhYre9xXaH5Mcg8L5NOUpK2+PzckU8mL01xZTgKSKQJfQXCbJMTEZV2jsVBKoi/LYlnbTA== 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=c22MRx5eaHb5UPQBnOGu10jZ1H886iAJgqwqqD74Ocs=; b=HzLB5jdvp4S9sMYSDjw1t93Ozv2I7yu4fff/GRcrYXgJs+lXnbWfcKssncYkcYaCF8K17OzWPDPJc0NI77IWyUsE0NZXkKzxsqwB0Ihh7tvuOpv30O5TFIH6NahOzIWbG8Xz6b+sPqTwsEzUfy5vdFCeVpDmqfYlrLUnTMevjlI= Received: from AM4PR05MB3265.eurprd05.prod.outlook.com (10.171.188.154) by AM4PR05MB3426.eurprd05.prod.outlook.com (10.171.188.139) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2430.20; Tue, 5 Nov 2019 13:28:21 +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 13:28:21 +0000 From: Slava Ovsiienko To: Bing Zhao , Ori Kam , Raslan Darawsheh CC: "dev@dpdk.org" , Bing Zhao Thread-Topic: [PATCH] net/mlx5: introdue mlx5 hash list Thread-Index: AQHVk9zEXVesd9KLX0GN27Y5qqJp7qd8kfJg Date: Tue, 5 Nov 2019 13:28:21 +0000 Message-ID: References: <1572960441-78720-1-git-send-email-bingz@pegasus02.mtr.labs.mlnx> In-Reply-To: <1572960441-78720-1-git-send-email-bingz@pegasus02.mtr.labs.mlnx> 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: 1a6d9221-354f-4ad4-0c15-08d761f4074a x-ms-traffictypediagnostic: AM4PR05MB3426:|AM4PR05MB3426: 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)(376002)(346002)(39860400002)(136003)(366004)(396003)(199004)(189003)(13464003)(33656002)(99286004)(74316002)(66476007)(66066001)(76176011)(66946007)(25786009)(7696005)(5660300002)(76116006)(8936002)(316002)(305945005)(7736002)(107886003)(2906002)(71200400001)(71190400001)(14454004)(256004)(14444005)(54906003)(81166006)(6246003)(110136005)(81156014)(8676002)(30864003)(6636002)(486006)(66556008)(4326008)(6436002)(52536014)(55016002)(186003)(229853002)(86362001)(66446008)(9686003)(6506007)(53546011)(102836004)(26005)(64756008)(476003)(11346002)(446003)(478600001)(6116002)(3846002); DIR:OUT; SFP:1101; SCL:1; SRVR:AM4PR05MB3426; 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: a/buAAFVth8GkaGFVrpw0R2AcMs68DCLJ7MdvT0IKIReueKaYq+TSewFXAjAfIuDZnP8OP/1u4DkV3lixUyoIOv8pMrkeIHoMEKsQS1kU8Uc7+qJBFREcHHltyCcvu96LPBd6gtSOA3zc2ZfP77eHZXlK8JlRC4uY9eeTe2ax/lyrc5aiHv7cxsbpfGL/jyio0NnmpOkMPWsI38/OrcPBG3iY3zaujlUZkDwYwXVYqw1xYnu2fHI3gnLfDGlJ7SVek0xovMk/9PE+aVEC47oH5fOMqcf6h4Kom4I25Qmej26wwYvRKhhbQH3XYo1vww3GmkRoGTg0880rwyigTpu8WowiYI2lFSoi5RxPSBAad3Zb81UUzk99IoxfPqGI+2qIYOq6MtZTi/WclcWU7LKnuAzXrz3cj5k0AVT8uvdf+yangHTfm6wJMQgz0mAcFyE 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: 1a6d9221-354f-4ad4-0c15-08d761f4074a X-MS-Exchange-CrossTenant-originalarrivaltime: 05 Nov 2019 13:28:21.6833 (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: Xf2vrXcjuqF8tHs31jPs9zACIxp9oTol5fRWddgne9DAVE5CfMdimCgc8sZQzFxrasMSGNYOXQ7me+oCdiXSL1ssSSahGNRcaLHydheWuB8= X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM4PR05MB3426 Subject: Re: [dpdk-dev] [PATCH] net/mlx5: introdue 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 15:27 > To: Ori Kam ; Slava Ovsiienko > ; Raslan Darawsheh > Cc: dev@dpdk.org; Bing Zhao > Subject: [PATCH] net/mlx5: introdue mlx5 hash list >=20 > From: Bing Zhao >=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