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 3082BA034E; Thu, 7 Nov 2019 10:20:35 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 57A861E983; Thu, 7 Nov 2019 10:20:34 +0100 (CET) Received: from EUR02-HE1-obe.outbound.protection.outlook.com (mail-eopbgr10080.outbound.protection.outlook.com [40.107.1.80]) by dpdk.org (Postfix) with ESMTP id 16B671E95C for ; Thu, 7 Nov 2019 10:20:33 +0100 (CET) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=dd6Focjb1VjSZyUD07Xf2+aZKK/WZQ9QwmsEzd3X+FVQCJVix6DDhEdMPN3/myedsHJyGAYrAHZ80a9b2NBUmpJz0LF4Ru+fVmGyrIqGX0rQTPgVxM978NJamKizPn60GqIoxnaiDWr3o/n8MJt6m0DERF0Y+/NcAJLF8R4SgPzXkszUyxdbrJCiyBohj6coCArP5Z3MxqkxnfA0xLbUTyZ7FtjgDOQEnKejwRLPgaeNLbv+d1CttVoo+1p8cF4VPiTEL0IvnIcw9m5L4P+JrRLWeJF0eAljQZgHIdYmGuCcgwvTA/thBVCct7Qg8yZ7CiKwgZVpXKn4XnFuOLqXig== 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=IkQ+WKqjr7V6xq7jE2uthvdPpPRXdXyxkqGg5glJsVY=; b=nm1BJ15ltywlajJWa394x/1unNLmjgGkddCpKgrfyeT3srGdKGbjfLvrb6mZZDMSlpDxovf7jJRyqaMkIGSBqWoTyHLmGy8r+xrV+VmllZETl2/P4qHJ44LMa68YRFUotARsk7PIEc26AZi/T6cxazSduDd9RzYkJQHiYx24wlcfuG5b2CjuGygCwoxFCD9u9qNhYF+ttW0YQXSj+asJzo6kfIcc9Zh1NjEHuEH4CYWvUoqEbgIKOuoT9RG9HrcMcNP/ILNKz0QkHVTuJhf/sgT3X/WtewrqQvM+DCJmYAMcck1wqZfnV6PfEvS3IMdlpWYGD4hC/as1UlysFuP7Ig== 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=IkQ+WKqjr7V6xq7jE2uthvdPpPRXdXyxkqGg5glJsVY=; b=UufaYPOWOnTwzbRmDzQgkXLlnsq6p/cQ/jAyiT0716BgfP1XHTFTnksP8gdnfzax6ahTzSYBrkMgCDo2qyrdYwVWali/nXLP23bE55D8J4AmDwuqdW/Pd+UKbEgQsDD+JTnVHPByIuQXsNE2fBPdM3BAFhUEv0htY23+QxZbbTc= Received: from VI1PR05MB4192.eurprd05.prod.outlook.com (10.171.183.18) by VI1PR05MB5504.eurprd05.prod.outlook.com (20.177.201.16) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2430.20; Thu, 7 Nov 2019 09:20:30 +0000 Received: from VI1PR05MB4192.eurprd05.prod.outlook.com ([fe80::20a1:86fa:a0ec:472]) by VI1PR05MB4192.eurprd05.prod.outlook.com ([fe80::20a1:86fa:a0ec:472%7]) with mapi id 15.20.2430.020; Thu, 7 Nov 2019 09:20:30 +0000 From: Bing Zhao To: Bing Zhao , Slava Ovsiienko , Stephen Hemminger CC: Ori Kam , Raslan Darawsheh , "dev@dpdk.org" Thread-Topic: [dpdk-dev] [PATCH v2] net/mlx5: introduce mlx5 hash list Thread-Index: AQHVlKNEi9vaWd1j2EyMv2ikM8S8Cqd/bjvw Date: Thu, 7 Nov 2019 09:20:30 +0000 Message-ID: References: <1572967680-93338-1-git-send-email-bingz@mellanox.com> <1573045676-175122-1-git-send-email-bingz@mellanox.com> In-Reply-To: <1573045676-175122-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=bingz@mellanox.com; x-originating-ip: [112.10.107.37] x-ms-publictraffictype: Email x-ms-office365-filtering-ht: Tenant x-ms-office365-filtering-correlation-id: db91a8f4-8bf3-4bf9-dad5-08d76363bc32 x-ms-traffictypediagnostic: VI1PR05MB5504:|VI1PR05MB5504: 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:530; x-forefront-prvs: 0214EB3F68 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(4636009)(396003)(366004)(376002)(136003)(39850400004)(346002)(13464003)(189003)(199004)(51874003)(99286004)(486006)(8676002)(11346002)(8936002)(7736002)(478600001)(9686003)(305945005)(6506007)(102836004)(66066001)(6436002)(7696005)(26005)(52536014)(2906002)(25786009)(74316002)(6246003)(446003)(55016002)(4326008)(14454004)(476003)(5660300002)(53546011)(66556008)(71190400001)(66476007)(30864003)(64756008)(66446008)(81156014)(81166006)(86362001)(33656002)(3846002)(256004)(186003)(76176011)(71200400001)(76116006)(316002)(66946007)(110136005)(54906003)(14444005)(6116002)(229853002); DIR:OUT; SFP:1101; SCL:1; SRVR:VI1PR05MB5504; H:VI1PR05MB4192.eurprd05.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; MX:1; A: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: OvlGIczise4xlhwabj1Fl0FY234QJiGUAvc8STawbJg4TvZpl+rxUGS2cxljk/Rm4QbRIf5CI8RuLxrdk4SsLg+KLTSDoNDWDt+jW++vX5pcu5GXbdsJsvPFMSNjFN+W2X+5a81K6bQaiFBgJ8mfSAayMORIIN1DXwGhZyjcR+6MrfohHv3FKkLt5bhX4NK+qCiy8HYC4uN3eWcSF7sxUgfPOgIP7N4QHl7cpMoauUYdEaBRQufZZ2iYTTkbzJ2r7uhstYddOPVdzH9Fk8JnXTTUM/Ep/InvQ+CcHD2w49qY2S/Bdu2lju7m5/XOX9HoDWZ84mL5HF/TYHG2JC16xMVMzliRxebEn31kHB4aqkmgjeJvKH4JzJX411NOYJbbomC5UGYrBE2B8RKM4kPyIP/BEaVvwOYugm5QCNOB5KfehiEHGwdcC/V5jVLuQRZy 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: db91a8f4-8bf3-4bf9-dad5-08d76363bc32 X-MS-Exchange-CrossTenant-originalarrivaltime: 07 Nov 2019 09:20:30.5036 (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: uYhk5cpWIpi7Us70NLRPUzEzr2fGLLPiUrijk0VNrEXN6L/IbAD5m3hNUIeDODgutA3x8NKrgJNmD+Dsyf506A== X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR05MB5504 Subject: Re: [dpdk-dev] [PATCH v2] 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" Adding Stephen Hi Stephen, would you please help to review the V2? Many thanks in advance. :-) BR. Bing > -----Original Message----- > From: dev On Behalf Of Bing Zhao > Sent: Wednesday, November 6, 2019 9:08 PM > To: Slava Ovsiienko ; dev@dpdk.org > Cc: Ori Kam ; Raslan Darawsheh > > Subject: [dpdk-dev] [PATCH v2] 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 th= e > table and linked to the corresponding list head. User should guarantee > there is no collision of the key and provide a callback function to handl= e > 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 better performance. The LSB of the 'key' is used to > calculate the index of the head 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 | 2 + > drivers/net/mlx5/mlx5_utils.c | 119 > ++++++++++++++++++++++++++++++++++++++++++ > drivers/net/mlx5/mlx5_utils.h | 107 > ++++++++++++++++++++++++++++++++++++- > 4 files changed, 227 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..b72ddb4 100644 > --- a/drivers/net/mlx5/meson.build > +++ b/drivers/net/mlx5/meson.build > @@ -38,6 +38,7 @@ endforeach >=20 > if build > allow_experimental_apis =3D true > + deps +=3D ['hash'] > ext_deps +=3D libs > sources =3D files( > 'mlx5.c', > @@ -58,6 +59,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..5d86615 > --- /dev/null > +++ b/drivers/net/mlx5/mlx5_utils.c > @@ -0,0 +1,119 @@ > +/* SPDX-License-Identifier: BSD-3-Clause > + * Copyright 2019 Mellanox Technologies, Ltd */ > + > +#include > +#include > + > +#include "mlx5_utils.h" > + > +struct mlx5_hlist * > +mlx5_hlist_create(const char *name, uint32_t size) { > + struct mlx5_hlist *h; > + uint32_t act_size; > + uint32_t alloc_size; > + > + if (!size) > + return NULL; > + /* Align to the next power of 2, 32bits integer is enough now. > */ > + if (!rte_is_power_of_2(size)) { > + act_size =3D rte_align32pow2(size); > + DRV_LOG(WARNING, "Size 0x%" PRIX32 " is not power > of 2, will " > + "be aligned to 0x%" PRIX32 ".\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); > + h->table_sz =3D act_size; > + h->mask =3D act_size - 1; > + DRV_LOG(DEBUG, "Hash list with %s size 0x%" PRIX32 " is > created.\n", > + h->name, act_size); > + return h; > +} > + > +struct mlx5_hlist_entry * > +mlx5_hlist_lookup(struct mlx5_hlist *h, uint64_t key) { > + uint32_t idx; > + struct mlx5_hlist_head *first; > + struct mlx5_hlist_entry *node; > + > + assert(h); > + idx =3D rte_hash_crc_8byte(key, 0) & 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) > +{ > + uint32_t idx; > + struct mlx5_hlist_head *first; > + struct mlx5_hlist_entry *node; > + > + assert(h && entry); > + idx =3D rte_hash_crc_8byte(entry->key, 0) & 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, > + mlx5_hlist_destroy_callback_fn cb, void *ctx) { > + uint32_t idx; > + struct mlx5_hlist_entry *entry; > + > + assert(h); > + 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) > + cb(entry, ctx); > + 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..b4ed8c6 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,107 @@ > 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, void *ctx); > + > +/** 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. */ > + uint32_t table_sz; > + /**< mask to get the index of the list heads. */ > + uint32_t mask; > + 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. Key of each entry will be calculated with CRC in > +order to > + * generate a little fairer distribution. > + * > + * @param name > + * Name of the hash list(optional). > + * @param size > + * Heads array size of the hash list. > + * > + * @return > + * Pointer of the hash list table created, NULL on failure. > + */ > +struct mlx5_hlist *mlx5_hlist_create(const char *name, uint32_t size); > + > +/** > + * 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. > + * @param cb > + * Callback function for each inserted entry when destroying the > hash list. > + * @param ctx > + * Common context parameter used by callback function for each > entry. > + */ > +void mlx5_hlist_destroy(struct mlx5_hlist *h, > + mlx5_hlist_destroy_callback_fn cb, void *ctx); > + > #endif /* RTE_PMD_MLX5_UTILS_H_ */ > -- > 1.8.3.1