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 EE511A00C5; Wed, 29 Apr 2020 23:29:57 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id A913B1D965; Wed, 29 Apr 2020 23:29:56 +0200 (CEST) Received: from EUR05-VI1-obe.outbound.protection.outlook.com (mail-vi1eur05on2072.outbound.protection.outlook.com [40.107.21.72]) by dpdk.org (Postfix) with ESMTP id 89B901D961 for ; Wed, 29 Apr 2020 23:29:55 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector2-armh-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=cS1YH8nEY05liYbCYcK7dAPZYGuZrLLWeg9ZwrcX4mI=; b=W9wczIBito9UPA90wkUe77QN1YhUENGRpvs2/j+f4Ojgw/eI7ZryM1Le5FfZKdZueJ39YI74Bh/3i74NrEc11Ezl5EqzYmNzHWsuVdJsg5Si0kQ/Xij3LG20B6nazfGnwrgDEDpbe4KHPkYdlM4J5VVr3jDTwpc1nrjnGQavbdM= Received: from MR2P264CA0011.FRAP264.PROD.OUTLOOK.COM (2603:10a6:500:1::23) by HE1PR0801MB1930.eurprd08.prod.outlook.com (2603:10a6:3:57::17) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2937.22; Wed, 29 Apr 2020 21:29:52 +0000 Received: from VE1EUR03FT009.eop-EUR03.prod.protection.outlook.com (2603:10a6:500:1:cafe::44) by MR2P264CA0011.outlook.office365.com (2603:10a6:500:1::23) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2958.19 via Frontend Transport; Wed, 29 Apr 2020 21:29:52 +0000 Authentication-Results: spf=pass (sender IP is 63.35.35.123) smtp.mailfrom=arm.com; dpdk.org; dkim=pass (signature was verified) header.d=armh.onmicrosoft.com;dpdk.org; dmarc=bestguesspass action=none header.from=arm.com; Received-SPF: Pass (protection.outlook.com: domain of arm.com designates 63.35.35.123 as permitted sender) receiver=protection.outlook.com; client-ip=63.35.35.123; helo=64aa7808-outbound-1.mta.getcheckrecipient.com; Received: from 64aa7808-outbound-1.mta.getcheckrecipient.com (63.35.35.123) by VE1EUR03FT009.mail.protection.outlook.com (10.152.18.92) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2958.20 via Frontend Transport; Wed, 29 Apr 2020 21:29:51 +0000 Received: ("Tessian outbound 5abcb386707e:v54"); Wed, 29 Apr 2020 21:29:51 +0000 X-CheckRecipientChecked: true X-CR-MTA-CID: fe7c4c569ae60b06 X-CR-MTA-TID: 64aa7808 Received: from 33a37d76ea8a.2 by 64aa7808-outbound-1.mta.getcheckrecipient.com id 8E373D0D-8E38-410F-BFD4-CB5FB4564D79.1; Wed, 29 Apr 2020 21:29:46 +0000 Received: from EUR05-AM6-obe.outbound.protection.outlook.com by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id 33a37d76ea8a.2 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384); Wed, 29 Apr 2020 21:29:46 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=TkCcrEt1KnSZIe8/Mv9zfbd4L4EakKkwl9+8CGhfRitwwuGDqfsnezyoO1ml0B+fsonaNLwiyEgLc/AVgPzYHZiZkiEZcjy/lFftKgdhvCj4OUHmCBjGbt8IjOS1zf/s2gIS5J56TI5v246rlm3DoI0iJMxXtpDKAGvNQVQwenkODdE0oxaU3SJAuw+GeFLNRLaXOWuwjzRkg4WFh5l+/3APuPAu35E6YOZb35zdCl/Ovcba/qyGCjqo8c2E69R2p1L/O4gHwVeT2Eh/tsZjGkHQLoTa2M6ATmeYb4Qmyw3g5g7uiMaxnJyptmYXxAloeyfGRbi1vYBRXrUyzGLEAQ== 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=cS1YH8nEY05liYbCYcK7dAPZYGuZrLLWeg9ZwrcX4mI=; b=FUVvk3NI33giVLUWLHi+u4bKA6fZukNrMr/QV4viu1PitSXH1eaYbvNqAtEDVCrXBYN4bQxPpiOY2yDX8QqVCGudLvPBbDNZpWawuYp5x5mq2XFhuNXlHxsMKE4SZrf9K6i2Vnx3z1QcOdWlPkgz22U0hsLkKCO6fHwQU7nPkFrtgmc2aJlkJPQhlsqOyVbGbXoZ/em7Cv1tKpRfx1UPaEJn3VqweXOZ5wxZir71UUZye3cEtyqH7J86uUmDGDu7HrP3VZmmdqTyCC0cwGVOzWj8GyK9Bf4x9DhjSVNF2sv39ttqkj9DIjPBdSvPYLmXqgENGyKG+gcmqxqH/VXFdA== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=arm.com; dmarc=pass action=none header.from=arm.com; dkim=pass header.d=arm.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector2-armh-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=cS1YH8nEY05liYbCYcK7dAPZYGuZrLLWeg9ZwrcX4mI=; b=W9wczIBito9UPA90wkUe77QN1YhUENGRpvs2/j+f4Ojgw/eI7ZryM1Le5FfZKdZueJ39YI74Bh/3i74NrEc11Ezl5EqzYmNzHWsuVdJsg5Si0kQ/Xij3LG20B6nazfGnwrgDEDpbe4KHPkYdlM4J5VVr3jDTwpc1nrjnGQavbdM= Received: from DBBPR08MB4646.eurprd08.prod.outlook.com (2603:10a6:10:f5::16) by DBBPR08MB4361.eurprd08.prod.outlook.com (2603:10a6:10:c8::21) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2937.22; Wed, 29 Apr 2020 21:29:39 +0000 Received: from DBBPR08MB4646.eurprd08.prod.outlook.com ([fe80::1870:afc4:b90f:609d]) by DBBPR08MB4646.eurprd08.prod.outlook.com ([fe80::1870:afc4:b90f:609d%5]) with mapi id 15.20.2958.020; Wed, 29 Apr 2020 21:29:39 +0000 From: Honnappa Nagarahalli To: Vladimir Medvedkin , "dev@dpdk.org" CC: "konstantin.ananyev@intel.com" , "yipeng1.wang@intel.com" , "sameh.gobriel@intel.com" , "bruce.richardson@intel.com" , nd , Honnappa Nagarahalli , nd Thread-Topic: [dpdk-dev] [PATCH v3 1/4] hash: add k32v64 hash library Thread-Index: AQHWE1InVyKSqIJovkKG8w1Zw9fib6iPTvgA Date: Wed, 29 Apr 2020 21:29:39 +0000 Message-ID: References: <0e767e9171c4e90d57ec06b50d6bf3b7d79828b1.1586974411.git.vladimir.medvedkin@intel.com> In-Reply-To: <0e767e9171c4e90d57ec06b50d6bf3b7d79828b1.1586974411.git.vladimir.medvedkin@intel.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-ts-tracking-id: f6fc3a0b-5917-4283-81cd-0fee37a685c1.0 Authentication-Results-Original: intel.com; dkim=none (message not signed) header.d=none;intel.com; dmarc=none action=none header.from=arm.com; x-originating-ip: [217.140.111.135] x-ms-publictraffictype: Email X-MS-Office365-Filtering-HT: Tenant X-MS-Office365-Filtering-Correlation-Id: 31bc73bc-a7fb-4478-4b47-08d7ec8473d5 x-ms-traffictypediagnostic: DBBPR08MB4361:|DBBPR08MB4361:|HE1PR0801MB1930: x-ms-exchange-transport-forked: True X-Microsoft-Antispam-PRVS: x-checkrecipientrouted: true nodisclaimer: true x-ms-oob-tlc-oobclassifiers: OLM:9508;OLM:9508; x-forefront-prvs: 03883BD916 X-Forefront-Antispam-Report-Untrusted: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:DBBPR08MB4646.eurprd08.prod.outlook.com; PTR:; CAT:NONE; SFTY:; SFS:(4636009)(366004)(39860400002)(346002)(376002)(396003)(136003)(30864003)(86362001)(54906003)(2906002)(52536014)(66446008)(55016002)(76116006)(66946007)(66476007)(64756008)(110136005)(5660300002)(186003)(66556008)(9686003)(8676002)(478600001)(71200400001)(4326008)(53546011)(6506007)(26005)(8936002)(7696005)(316002)(33656002)(579004); DIR:OUT; SFP:1101; X-MS-Exchange-SenderADCheck: 1 X-Microsoft-Antispam-Untrusted: BCL:0; X-Microsoft-Antispam-Message-Info-Original: IUW9LNK7mS+WgfAjTi7ZkXeBrMXAAy8024K/SBax5mbxoYvt1hoc3tceQSbrXhhaQYsAQl6eT6cpu+CULOkcUtB8a25XiY8mKifJNy1PROusvJdzYZj3VEX6ShVdZsU+D2oeCadUUwVjkulJudgqziWvrN3NWUWiUZEUxloHyI9LD8DgUhnFBHlrteWJfYxAKd5E4KmDLD3J/yG5OwiATPypPQBy4CGdHKXj2s9pWY5KPLSjcR3+Zi209LeI217DsIOu4wxfDlHjK2MpvOTJPE6lfF9PAwMCQumt47xadEkGX7aD4QuzpsAQZLkCmJqvhxf4tMbRwCgYIK6wWwa9ytOcu/q3kCVEcDOr2SigEo4vrWvp78ku4r3BhpaK/I3fBSJbnGtOXF5Lw2m4zDdEDbB5gny8ssQ8KA6B8gu/F/1RGndSvneSn7TTjIvCMQH1 x-ms-exchange-antispam-messagedata: IM+enXiy0IgXFFHaj0cQe8HCwYJldFNC4RQ3b5dSZhNMpp/XP+pw+8v91JQxzuXSJLidNWbHX7wpP4tn4U19UgbcnrFQ2BE84xTvycdiO9Od5ft3VtZochGSZv+HYbbzGI76lkSwZUxEHsNXFjCtM5Cfeklz5rFPJ2HVP0mWERJspsVzoz6XT/9nYapA5xZyhYWGkFPF4w9aCcJfRtcna7Bb0HAO7zTwMPmtcseFdVx/yPa29KCV6FZUjNg7bv3liVJJSdgO8HlGtcNR2mjWREBVBggA9CSdUAlTrDig1Zj/WPQC7sJlUHQIIGTscO+bItuPxzrtdNuRjPCzM7k7NghYz2Tf7D1nFAYItcBYw/L3oaMcVLmPKmq6kb1NoHmJP2NO3Hic+uKTZqrcxP3zTNjk/irN595ptP+zvA7jgd6KA3bTFVsVNZ1/hXAh3ZIdzC2hBVMWl+rlmhXpQ4M2Qe/cbNcSyGwRZcmCHcSCruF14fPoiFxFZDqstayr/4HlM+I2uf7He0KPG8quxjnNBRgkDsNSNfCdVFOH5ikiDFzv2X49vC6G9HgO6ZjuYhRfJAhgUoIeHQwsaZO+CtjhTu9xukdofD/XqkWAnJGsLKdk1w2KryNhKGp7FsAepKmyj9T7qU57ucAXD1IOpy0RKBInW7JLBkb232LhY28ROoNHHSj5Vp9isRLFVQSnEMTLuxD4XKoE2rZPtYQkSSG48MP3ZLMJ/eckKtg0FlY4JW74csj5AssbdI2rTI/D+6098hxbp1B+7As/rIy1STxZg9FqE0bI/nh4S/XDXHY2hpVSmTZA9ZcmxsRoMARTCAJx Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-MS-Exchange-Transport-CrossTenantHeadersStamped: DBBPR08MB4361 Original-Authentication-Results: intel.com; dkim=none (message not signed) header.d=none;intel.com; dmarc=none action=none header.from=arm.com; X-EOPAttributedMessage: 0 X-MS-Exchange-Transport-CrossTenantHeadersStripped: VE1EUR03FT009.eop-EUR03.prod.protection.outlook.com X-Forefront-Antispam-Report: CIP:63.35.35.123; CTRY:IE; LANG:en; SCL:1; SRV:; IPV:CAL; SFV:NSPM; H:64aa7808-outbound-1.mta.getcheckrecipient.com; PTR:ec2-63-35-35-123.eu-west-1.compute.amazonaws.com; CAT:NONE; SFTY:; SFS:(4636009)(376002)(136003)(346002)(39860400002)(396003)(46966005)(55016002)(478600001)(36906005)(70206006)(70586007)(26005)(5660300002)(47076004)(7696005)(82310400002)(110136005)(82740400003)(54906003)(356005)(81166007)(33656002)(30864003)(53546011)(316002)(52536014)(8936002)(6506007)(4326008)(186003)(336012)(86362001)(9686003)(8676002)(2906002); DIR:OUT; SFP:1101; X-MS-Office365-Filtering-Correlation-Id-Prvs: 8c8b6531-1d5a-42f3-397a-08d7ec846c7d X-Forefront-PRVS: 03883BD916 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: 64P8fDq2+7jivKHatkmMvPG9fs+wQZqN04yZZZXW8FCpJ+ORbrRWWbFp4hKKPvmhOMC/oAM0J9JP3Ye+GEiW5S2UgE7cHuX1hYttEurJHSrZ51y8Ofte9jB1ylfdL3b5elgQgT9OahWL7CQDQ28cHJixc9MP4UHrFPbut0Buyctaq56aVbvGe7m8soHEoJ601QKPPXS+yZWUTbaRaKi5Trf64e2ZXNjSvXICoO/dH0kIUx9BxrqMKKp3Hft+hq9gus+56hRMNWJvao8fkOwvPAhLwsD6XNk+9axq+HCwYcCJn2+K/KLMa8uLD7PUG9xLA2fsqfktAI9BCi13cn5fKMCFtOJ9GJTs/jvsDxxH7JjfTmjKjCgfiLDMOtQmNgVWHhvuwC4+iaaMZvAcL7P83GfRXzB17sjmO/7xGhcBu0eGuoV/j/DqoAYIj7vBwt4hgAOh3gwbvU4Yh6GpeqhZLaLGAlaHxEo8w5het8Bz90BdD0zK5GllRfFJsXuFElCk X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 29 Apr 2020 21:29:51.8001 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 31bc73bc-a7fb-4478-4b47-08d7ec8473d5 X-MS-Exchange-CrossTenant-Id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=f34e5979-57d9-4aaa-ad4d-b122a662184d; Ip=[63.35.35.123]; Helo=[64aa7808-outbound-1.mta.getcheckrecipient.com] X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: HE1PR0801MB1930 Subject: Re: [dpdk-dev] [PATCH v3 1/4] hash: add k32v64 hash library 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" Hi Vladimir, I am not sure which way the decision is made, but few comments inline. Ple= ase use C11 built-ins for synchronization. > -----Original Message----- > From: dev On Behalf Of Vladimir Medvedkin > Sent: Wednesday, April 15, 2020 1:17 PM > To: dev@dpdk.org > Cc: konstantin.ananyev@intel.com; yipeng1.wang@intel.com; > sameh.gobriel@intel.com; bruce.richardson@intel.com > Subject: [dpdk-dev] [PATCH v3 1/4] hash: add k32v64 hash library >=20 > K32V64 hash is a hash table that supports 32 bit keys and 64 bit values. > This table is hash function agnostic so user must provide precalculated h= ash > signature for add/delete/lookup operations. >=20 > Signed-off-by: Vladimir Medvedkin > --- > lib/Makefile | 2 +- > lib/librte_hash/Makefile | 13 +- > lib/librte_hash/k32v64_hash_avx512vl.c | 56 ++++++ > lib/librte_hash/meson.build | 17 +- > lib/librte_hash/rte_hash_version.map | 6 +- > lib/librte_hash/rte_k32v64_hash.c | 315 > +++++++++++++++++++++++++++++++++ > lib/librte_hash/rte_k32v64_hash.h | 211 ++++++++++++++++++++++ > 7 files changed, 615 insertions(+), 5 deletions(-) create mode 100644 > lib/librte_hash/k32v64_hash_avx512vl.c > create mode 100644 lib/librte_hash/rte_k32v64_hash.c create mode > 100644 lib/librte_hash/rte_k32v64_hash.h >=20 > diff --git a/lib/Makefile b/lib/Makefile index 46b91ae..a8c02e4 100644 > --- a/lib/Makefile > +++ b/lib/Makefile > @@ -48,7 +48,7 @@ DIRS-$(CONFIG_RTE_LIBRTE_VHOST) +=3D librte_vhost > DEPDIRS-librte_vhost :=3D librte_eal librte_mempool librte_mbuf librte_et= hdev > \ > librte_net librte_hash librte_cryptodev > DIRS-$(CONFIG_RTE_LIBRTE_HASH) +=3D librte_hash -DEPDIRS-librte_hash := =3D > librte_eal librte_ring > +DEPDIRS-librte_hash :=3D librte_eal librte_ring librte_mempool > DIRS-$(CONFIG_RTE_LIBRTE_EFD) +=3D librte_efd DEPDIRS-librte_efd :=3D > librte_eal librte_ring librte_hash > DIRS-$(CONFIG_RTE_LIBRTE_RIB) +=3D librte_rib diff --git > a/lib/librte_hash/Makefile b/lib/librte_hash/Makefile index > ec9f864..023689d 100644 > --- a/lib/librte_hash/Makefile > +++ b/lib/librte_hash/Makefile > @@ -8,13 +8,14 @@ LIB =3D librte_hash.a >=20 > CFLAGS +=3D -O3 > CFLAGS +=3D $(WERROR_FLAGS) -I$(SRCDIR) > -LDLIBS +=3D -lrte_eal -lrte_ring > +LDLIBS +=3D -lrte_eal -lrte_ring -lrte_mempool >=20 > EXPORT_MAP :=3D rte_hash_version.map >=20 > # all source are stored in SRCS-y > SRCS-$(CONFIG_RTE_LIBRTE_HASH) :=3D rte_cuckoo_hash.c > SRCS-$(CONFIG_RTE_LIBRTE_HASH) +=3D rte_fbk_hash.c > +SRCS-$(CONFIG_RTE_LIBRTE_HASH) +=3D rte_k32v64_hash.c >=20 > # install this header file > SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include :=3D rte_hash.h @@ -27,5 > +28,15 @@ endif SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include +=3D > rte_jhash.h SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include +=3D rte_thash.h > SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include +=3D rte_fbk_hash.h > +SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include +=3D rte_k32v64_hash.h > + > +CC_AVX512VL_SUPPORT=3D$(shell $(CC) -mavx512vl -dM -E - &1 > | > +\ grep -q __AVX512VL__ && echo 1) > + > +ifeq ($(CC_AVX512VL_SUPPORT), 1) > + SRCS-$(CONFIG_RTE_LIBRTE_HASH) +=3D k32v64_hash_avx512vl.c > + CFLAGS_k32v64_hash_avx512vl.o +=3D -mavx512vl > + CFLAGS_rte_k32v64_hash.o +=3D -DCC_AVX512VL_SUPPORT endif >=20 > include $(RTE_SDK)/mk/rte.lib.mk > diff --git a/lib/librte_hash/k32v64_hash_avx512vl.c > b/lib/librte_hash/k32v64_hash_avx512vl.c > new file mode 100644 > index 0000000..7c70dd2 > --- /dev/null > +++ b/lib/librte_hash/k32v64_hash_avx512vl.c > @@ -0,0 +1,56 @@ > +/* SPDX-License-Identifier: BSD-3-Clause > + * Copyright(c) 2020 Intel Corporation > + */ > + > +#include > + > +int > +k32v64_hash_bulk_lookup_avx512vl(struct rte_k32v64_hash_table *table, > + uint32_t *keys, uint32_t *hashes, uint64_t *values, unsigned int n); > + > +static inline int > +k32v64_cmp_keys_avx512vl(struct rte_k32v64_hash_bucket *bucket, > uint32_t key, > + uint64_t *val) > +{ > + __m128i keys, srch_key; > + __mmask8 msk; > + > + keys =3D _mm_load_si128((void *)bucket); > + srch_key =3D _mm_set1_epi32(key); > + > + msk =3D _mm_mask_cmpeq_epi32_mask(bucket->key_mask, keys, > srch_key); > + if (msk) { > + *val =3D bucket->val[__builtin_ctz(msk)]; > + return 1; > + } > + > + return 0; > +} > + > +static inline int > +k32v64_hash_lookup_avx512vl(struct rte_k32v64_hash_table *table, > uint32_t key, > + uint32_t hash, uint64_t *value) > +{ > + return __k32v64_hash_lookup(table, key, hash, value, > + k32v64_cmp_keys_avx512vl); > +} > + > +int > +k32v64_hash_bulk_lookup_avx512vl(struct rte_k32v64_hash_table *table, > + uint32_t *keys, uint32_t *hashes, uint64_t *values, unsigned int n) { > + int ret, cnt =3D 0; > + unsigned int i; > + > + if (unlikely((table =3D=3D NULL) || (keys =3D=3D NULL) || (hashes =3D= =3D NULL) || > + (values =3D=3D NULL))) > + return -EINVAL; > + > + for (i =3D 0; i < n; i++) { > + ret =3D k32v64_hash_lookup_avx512vl(table, keys[i], hashes[i], > + &values[i]); > + if (ret =3D=3D 0) > + cnt++; > + } > + return cnt; > +} > diff --git a/lib/librte_hash/meson.build b/lib/librte_hash/meson.build in= dex > 6ab46ae..8a37cc4 100644 > --- a/lib/librte_hash/meson.build > +++ b/lib/librte_hash/meson.build > @@ -3,10 +3,23 @@ >=20 > headers =3D files('rte_crc_arm64.h', > 'rte_fbk_hash.h', > + 'rte_k32v64_hash.h', > 'rte_hash_crc.h', > 'rte_hash.h', > 'rte_jhash.h', > 'rte_thash.h') >=20 > -sources =3D files('rte_cuckoo_hash.c', 'rte_fbk_hash.c') -deps +=3D ['ri= ng'] > +sources =3D files('rte_cuckoo_hash.c', 'rte_fbk_hash.c', > +'rte_k32v64_hash.c') deps +=3D ['ring', 'mempool'] > + > +if dpdk_conf.has('RTE_ARCH_X86') > + if cc.has_argument('-mavx512vl') > + avx512_tmplib =3D static_library('avx512_tmp', > + 'k32v64_hash_avx512vl.c', > + dependencies: static_rte_mempool, > + c_args: cflags + ['-mavx512vl']) > + objs +=3D avx512_tmplib.extract_objects('k32v64_hash_avx= 512vl.c') > + cflags +=3D '-DCC_AVX512VL_SUPPORT' > + > + endif > +endif > diff --git a/lib/librte_hash/rte_hash_version.map > b/lib/librte_hash/rte_hash_version.map > index a8fbbc3..9a4f2f6 100644 > --- a/lib/librte_hash/rte_hash_version.map > +++ b/lib/librte_hash/rte_hash_version.map > @@ -34,5 +34,9 @@ EXPERIMENTAL { >=20 > rte_hash_free_key_with_position; > rte_hash_max_key_id; > - > + rte_k32v64_hash_create; > + rte_k32v64_hash_find_existing; > + rte_k32v64_hash_free; > + rte_k32v64_hash_add; > + rte_k32v64_hash_delete; > }; > diff --git a/lib/librte_hash/rte_k32v64_hash.c > b/lib/librte_hash/rte_k32v64_hash.c > new file mode 100644 > index 0000000..7ed94b4 > --- /dev/null > +++ b/lib/librte_hash/rte_k32v64_hash.c > @@ -0,0 +1,315 @@ > +/* SPDX-License-Identifier: BSD-3-Clause > + * Copyright(c) 2020 Intel Corporation > + */ > + > +#include > + > +#include > +#include > +#include > +#include > +#include > + > +#include > + > +TAILQ_HEAD(rte_k32v64_hash_list, rte_tailq_entry); > + > +static struct rte_tailq_elem rte_k32v64_hash_tailq =3D { > + .name =3D "RTE_K32V64_HASH", > +}; > + > +EAL_REGISTER_TAILQ(rte_k32v64_hash_tailq); > + > +#define VALID_KEY_MSK ((1 << RTE_K32V64_KEYS_PER_BUCKET) - 1) > + > +#ifdef CC_AVX512VL_SUPPORT > +int > +k32v64_hash_bulk_lookup_avx512vl(struct rte_k32v64_hash_table *table, > + uint32_t *keys, uint32_t *hashes, uint64_t *values, unsigned int n); > +#endif > + > +static int > +k32v64_hash_bulk_lookup(struct rte_k32v64_hash_table *table, uint32_t > *keys, > + uint32_t *hashes, uint64_t *values, unsigned int n) { > + int ret, cnt =3D 0; > + unsigned int i; > + > + if (unlikely((table =3D=3D NULL) || (keys =3D=3D NULL) || (hashes =3D= =3D NULL) || > + (values =3D=3D NULL))) > + return -EINVAL; > + > + for (i =3D 0; i < n; i++) { > + ret =3D rte_k32v64_hash_lookup(table, keys[i], hashes[i], > + &values[i]); > + if (ret =3D=3D 0) > + cnt++; > + } > + return cnt; > +} > + > +static rte_k32v64_hash_bulk_lookup_t > +get_lookup_bulk_fn(void) > +{ > +#ifdef CC_AVX512VL_SUPPORT > + if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX512F)) > + return k32v64_hash_bulk_lookup_avx512vl; #endif > + return k32v64_hash_bulk_lookup; > +} > + > +int > +rte_k32v64_hash_add(struct rte_k32v64_hash_table *table, uint32_t key, > + uint32_t hash, uint64_t value) > +{ > + uint32_t bucket; > + int i, idx, ret; > + uint8_t msk; > + struct rte_k32v64_ext_ent *tmp, *ent, *prev =3D NULL; > + > + if (table =3D=3D NULL) > + return -EINVAL; > + > + bucket =3D hash & table->bucket_msk; > + /* Search key in table. Update value if exists */ > + for (i =3D 0; i < RTE_K32V64_KEYS_PER_BUCKET; i++) { > + if ((key =3D=3D table->t[bucket].key[i]) && > + (table->t[bucket].key_mask & (1 << i))) { > + table->t[bucket].val[i] =3D value; The old value of val[i] might be getting used in the reader. It needs to be= returned to the caller so that it can be put on the RCU defer queue to fre= e later. You might also want to use an atomic store to ensure the stores are not spl= it. > + return 0; > + } > + } > + > + if (!SLIST_EMPTY(&table->t[bucket].head)) { > + SLIST_FOREACH(ent, &table->t[bucket].head, next) { > + if (ent->key =3D=3D key) { > + ent->val =3D value; Same here, need to return the old value. > + return 0; > + } > + } > + } > + > + msk =3D ~table->t[bucket].key_mask & VALID_KEY_MSK; > + if (msk) { > + idx =3D __builtin_ctz(msk); > + table->t[bucket].key[idx] =3D key; > + table->t[bucket].val[idx] =3D value; > + rte_smp_wmb(); > + table->t[bucket].key_mask |=3D 1 << idx; The barrier and the store can be replaced with a store-release in C11. > + table->nb_ent++; > + return 0; > + } > + > + ret =3D rte_mempool_get(table->ext_ent_pool, (void **)&ent); > + if (ret < 0) > + return ret; > + > + SLIST_NEXT(ent, next) =3D NULL; > + ent->key =3D key; > + ent->val =3D value; > + rte_smp_wmb(); > + SLIST_FOREACH(tmp, &table->t[bucket].head, next) > + prev =3D tmp; > + > + if (prev =3D=3D NULL) > + SLIST_INSERT_HEAD(&table->t[bucket].head, ent, next); > + else > + SLIST_INSERT_AFTER(prev, ent, next); Need C11 SLIST > + > + table->nb_ent++; > + table->nb_ext_ent++; > + return 0; > +} > + > +int > +rte_k32v64_hash_delete(struct rte_k32v64_hash_table *table, uint32_t key= , > + uint32_t hash) This should return the value corresponding to the deleted key > +{ > + uint32_t bucket; > + int i; > + struct rte_k32v64_ext_ent *ent; > + > + if (table =3D=3D NULL) > + return -EINVAL; > + > + bucket =3D hash & table->bucket_msk; > + > + for (i =3D 0; i < RTE_K32V64_KEYS_PER_BUCKET; i++) { > + if ((key =3D=3D table->t[bucket].key[i]) && > + (table->t[bucket].key_mask & (1 << i))) { > + ent =3D SLIST_FIRST(&table->t[bucket].head); > + if (ent) { > + rte_atomic32_inc(&table->t[bucket].cnt); > + table->t[bucket].key[i] =3D ent->key; In this case, both key and value are changing and it is not atomic. There i= s a possibility that the lookup function will receive incorrect value of 'v= al[i]'. Suggest following the method described below. > + table->t[bucket].val[i] =3D ent->val; > + SLIST_REMOVE_HEAD(&table->t[bucket].head, > next); > + rte_atomic32_inc(&table->t[bucket].cnt); > + table->nb_ext_ent--; > + } else Suggest changing this into a 2 step process: 1) Delete the entry from the fixed bucket (update key_mask) 2) Move the head of extended bucket to the fixed bucket 2a) Insert the key/value from the head into the deleted index and update t= he key_mask (this will ensure that the reader has the entry available while= it is being removed from the extended bucket) 2b) increment the counter indicating the extended bucket is changing 2c) remove the head 2d) increment the counter indicating the extended bucket change is done The above procedure will result in removing the spinning (resulting from st= ep 2b) in the lookup function (comment is added in the lookup function), re= aders will not be blocked if the writer is scheduled out. This logic is implemented in rte_hash using cuckoo hash, suggest to take a = look for required memory orderings. > + table->t[bucket].key_mask &=3D ~(1 << i); > + if (ent) > + rte_mempool_put(table->ext_ent_pool, ent); Entry cannot be put to free list immediately as the readers are still using= it. > + table->nb_ent--; > + return 0; > + } > + } > + > + SLIST_FOREACH(ent, &table->t[bucket].head, next) > + if (ent->key =3D=3D key) > + break; > + > + if (ent =3D=3D NULL) > + return -ENOENT; > + > + rte_atomic32_inc(&table->t[bucket].cnt); > + SLIST_REMOVE(&table->t[bucket].head, ent, rte_k32v64_ext_ent, > next); > + rte_atomic32_inc(&table->t[bucket].cnt); > + rte_mempool_put(table->ext_ent_pool, ent); Entry might be getting used by the readers still. > + > + table->nb_ext_ent--; > + table->nb_ent--; > + > + return 0; > +} > + > +struct rte_k32v64_hash_table * > +rte_k32v64_hash_find_existing(const char *name) { > + struct rte_k32v64_hash_table *h =3D NULL; > + struct rte_tailq_entry *te; > + struct rte_k32v64_hash_list *k32v64_hash_list; > + > + k32v64_hash_list =3D RTE_TAILQ_CAST(rte_k32v64_hash_tailq.head, > + rte_k32v64_hash_list); > + > + rte_mcfg_tailq_read_lock(); > + TAILQ_FOREACH(te, k32v64_hash_list, next) { > + h =3D (struct rte_k32v64_hash_table *) te->data; > + if (strncmp(name, h->name, RTE_K32V64_HASH_NAMESIZE) > =3D=3D 0) > + break; > + } > + rte_mcfg_tailq_read_unlock(); > + if (te =3D=3D NULL) { > + rte_errno =3D ENOENT; > + return NULL; > + } > + return h; > +} > + > +struct rte_k32v64_hash_table * > +rte_k32v64_hash_create(const struct rte_k32v64_hash_params *params) { > + char hash_name[RTE_K32V64_HASH_NAMESIZE]; > + struct rte_k32v64_hash_table *ht =3D NULL; > + struct rte_tailq_entry *te; > + struct rte_k32v64_hash_list *k32v64_hash_list; > + uint32_t mem_size, nb_buckets, max_ent; > + int ret; > + struct rte_mempool *mp; > + > + if ((params =3D=3D NULL) || (params->name =3D=3D NULL) || > + (params->entries =3D=3D 0)) { > + rte_errno =3D EINVAL; > + return NULL; > + } > + > + k32v64_hash_list =3D RTE_TAILQ_CAST(rte_k32v64_hash_tailq.head, > + rte_k32v64_hash_list); > + > + ret =3D snprintf(hash_name, sizeof(hash_name), "K32V64_%s", params- > >name); > + if (ret < 0 || ret >=3D RTE_K32V64_HASH_NAMESIZE) { > + rte_errno =3D ENAMETOOLONG; > + return NULL; > + } > + > + max_ent =3D rte_align32pow2(params->entries); > + nb_buckets =3D max_ent / RTE_K32V64_KEYS_PER_BUCKET; > + mem_size =3D sizeof(struct rte_k32v64_hash_table) + > + sizeof(struct rte_k32v64_hash_bucket) * nb_buckets; > + > + mp =3D rte_mempool_create(hash_name, max_ent, > + sizeof(struct rte_k32v64_ext_ent), 0, 0, NULL, NULL, NULL, > NULL, > + params->socket_id, 0); > + > + if (mp =3D=3D NULL) > + return NULL; > + > + rte_mcfg_tailq_write_lock(); > + TAILQ_FOREACH(te, k32v64_hash_list, next) { > + ht =3D (struct rte_k32v64_hash_table *) te->data; > + if (strncmp(params->name, ht->name, > + RTE_K32V64_HASH_NAMESIZE) =3D=3D 0) > + break; > + } > + ht =3D NULL; > + if (te !=3D NULL) { > + rte_errno =3D EEXIST; > + rte_mempool_free(mp); > + goto exit; > + } > + > + te =3D rte_zmalloc("K32V64_HASH_TAILQ_ENTRY", sizeof(*te), 0); > + if (te =3D=3D NULL) { > + RTE_LOG(ERR, HASH, "Failed to allocate tailq entry\n"); > + rte_mempool_free(mp); > + goto exit; > + } > + > + ht =3D rte_zmalloc_socket(hash_name, mem_size, > + RTE_CACHE_LINE_SIZE, params->socket_id); > + if (ht =3D=3D NULL) { > + RTE_LOG(ERR, HASH, "Failed to allocate fbk hash table\n"); > + rte_free(te); > + rte_mempool_free(mp); > + goto exit; > + } > + > + memcpy(ht->name, hash_name, sizeof(ht->name)); > + ht->max_ent =3D max_ent; > + ht->bucket_msk =3D nb_buckets - 1; > + ht->ext_ent_pool =3D mp; > + ht->lookup =3D get_lookup_bulk_fn(); > + > + te->data =3D (void *)ht; > + TAILQ_INSERT_TAIL(k32v64_hash_list, te, next); > + > +exit: > + rte_mcfg_tailq_write_unlock(); > + > + return ht; > +} > + > +void > +rte_k32v64_hash_free(struct rte_k32v64_hash_table *ht) { > + struct rte_tailq_entry *te; > + struct rte_k32v64_hash_list *k32v64_hash_list; > + > + if (ht =3D=3D NULL) > + return; > + > + k32v64_hash_list =3D RTE_TAILQ_CAST(rte_k32v64_hash_tailq.head, > + rte_k32v64_hash_list); > + > + rte_mcfg_tailq_write_lock(); > + > + /* find out tailq entry */ > + TAILQ_FOREACH(te, k32v64_hash_list, next) { > + if (te->data =3D=3D (void *) ht) > + break; > + } > + > + > + if (te =3D=3D NULL) { > + rte_mcfg_tailq_write_unlock(); > + return; > + } > + > + TAILQ_REMOVE(k32v64_hash_list, te, next); > + > + rte_mcfg_tailq_write_unlock(); > + > + rte_mempool_free(ht->ext_ent_pool); > + rte_free(ht); > + rte_free(te); > +} > diff --git a/lib/librte_hash/rte_k32v64_hash.h > b/lib/librte_hash/rte_k32v64_hash.h > new file mode 100644 > index 0000000..b2c52e9 > --- /dev/null > +++ b/lib/librte_hash/rte_k32v64_hash.h > @@ -0,0 +1,211 @@ > +/* SPDX-License-Identifier: BSD-3-Clause > + * Copyright(c) 2020 Intel Corporation > + */ > + > +#ifndef _RTE_K32V64_HASH_H_ > +#define _RTE_K32V64_HASH_H_ > + > +#ifdef __cplusplus > +extern "C" { > +#endif > + > +#include > +#include > +#include > + > +#define RTE_K32V64_HASH_NAMESIZE 32 > +#define RTE_K32V64_KEYS_PER_BUCKET 4 > +#define RTE_K32V64_WRITE_IN_PROGRESS 1 > + > +struct rte_k32v64_hash_params { > + const char *name; > + uint32_t entries; > + int socket_id; > +}; > + > +struct rte_k32v64_ext_ent { > + SLIST_ENTRY(rte_k32v64_ext_ent) next; > + uint32_t key; > + uint64_t val; > +}; > + > +struct rte_k32v64_hash_bucket { > + uint32_t key[RTE_K32V64_KEYS_PER_BUCKET]; > + uint64_t val[RTE_K32V64_KEYS_PER_BUCKET]; > + uint8_t key_mask; > + rte_atomic32_t cnt; > + SLIST_HEAD(rte_k32v64_list_head, rte_k32v64_ext_ent) head; } > +__rte_cache_aligned; > + > +struct rte_k32v64_hash_table; > + > +typedef int (*rte_k32v64_hash_bulk_lookup_t) (struct > +rte_k32v64_hash_table *table, uint32_t *keys, uint32_t *hashes, > + uint64_t *values, unsigned int n); > + > +struct rte_k32v64_hash_table { > + char name[RTE_K32V64_HASH_NAMESIZE]; /**< Name of the > hash. */ > + uint32_t nb_ent; /**< Number of entities in the table*/ > + uint32_t nb_ext_ent; /**< Number of extended entities */ > + uint32_t max_ent; /**< Maximum number of entities */ > + uint32_t bucket_msk; > + struct rte_mempool *ext_ent_pool; > + rte_k32v64_hash_bulk_lookup_t lookup; > + __extension__ struct rte_k32v64_hash_bucket t[0]; > +}; > + > +typedef int (*rte_k32v64_cmp_fn_t) > +(struct rte_k32v64_hash_bucket *bucket, uint32_t key, uint64_t *val); > + > +static inline int > +__k32v64_cmp_keys(struct rte_k32v64_hash_bucket *bucket, uint32_t key, > + uint64_t *val) > +{ > + int i; > + > + for (i =3D 0; i < RTE_K32V64_KEYS_PER_BUCKET; i++) { > + if ((key =3D=3D bucket->key[i]) && > + (bucket->key_mask & (1 << i))) { > + *val =3D bucket->val[i]; This load can happen speculatively. You have to use the guard variable and payload concept here for reader-writ= er concurrency. On the writer: store -> key store -> val store_release -> key_mask (or there will be a rte_smp_wmb before this) 'key= _mask' acts as the guard variable On the reader: load_acquire -> key_mask (or there will be a rte_smp_rmb after this) if statement etc..... > + return 1; > + } > + } > + > + return 0; > +} > + > +static inline int > +__k32v64_hash_lookup(struct rte_k32v64_hash_table *table, uint32_t key, > + uint32_t hash, uint64_t *value, rte_k32v64_cmp_fn_t cmp_f) { > + uint64_t val =3D 0; > + struct rte_k32v64_ext_ent *ent; > + int32_t cnt; > + int found =3D 0; > + uint32_t bucket =3D hash & table->bucket_msk; > + > + do { > + do > + cnt =3D rte_atomic32_read(&table->t[bucket].cnt); > + while (unlikely(cnt & RTE_K32V64_WRITE_IN_PROGRESS)); The reader can hang here if the writer increments the counter and gets sche= duled out. Using the method suggested above, you can remove this code. > + > + found =3D cmp_f(&table->t[bucket], key, &val); > + if (unlikely((found =3D=3D 0) && > + (!SLIST_EMPTY(&table->t[bucket].head)))) { > + SLIST_FOREACH(ent, &table->t[bucket].head, next) { > + if (ent->key =3D=3D key) { > + val =3D ent->val; > + found =3D 1; > + break; > + } > + } > + } > + > + } while (unlikely(cnt !=3D rte_atomic32_read(&table->t[bucket].cnt))); With the logic mentioned in delete function, the counter needs to be read a= t the beginning of the loop. Suggest looking at rte_hash-cuckoo hash for th= e memory ordering required for the counter. > + > + if (found =3D=3D 1) { > + *value =3D val; > + return 0; > + } else > + return -ENOENT; > +} > + > +static inline int > +rte_k32v64_hash_lookup(struct rte_k32v64_hash_table *table, uint32_t key= , > + uint32_t hash, uint64_t *value) > +{ > + return __k32v64_hash_lookup(table, key, hash, value, > +__k32v64_cmp_keys); } > + > +static inline int > +rte_k32v64_hash_bulk_lookup(struct rte_k32v64_hash_table *table, > + uint32_t *keys, uint32_t *hashes, uint64_t *values, unsigned int n) { > + return table->lookup(table, keys, hashes, values, n); } > + > +/** > + * Add a key to an existing hash table with hash value. > + * This operation is not multi-thread safe > + * and should only be called from one thread. > + * > + * @param ht > + * Hash table to add the key to. > + * @param key > + * Key to add to the hash table. > + * @param value > + * Value to associate with key. > + * @param hash > + * Hash value associated with key. > + * @return > + * 0 if ok, or negative value on error. > + */ > +__rte_experimental > +int > +rte_k32v64_hash_add(struct rte_k32v64_hash_table *table, uint32_t key, > + uint32_t hash, uint64_t value); > + > +/** > + * Remove a key with a given hash value from an existing hash table. > + * This operation is not multi-thread > + * safe and should only be called from one thread. > + * > + * @param ht > + * Hash table to remove the key from. > + * @param key > + * Key to remove from the hash table. > + * @param hash > + * hash value associated with key. > + * @return > + * 0 if ok, or negative value on error. > + */ > +__rte_experimental > +int > +rte_k32v64_hash_delete(struct rte_k32v64_hash_table *table, uint32_t key= , > + uint32_t hash); > + > + > +/** > + * Performs a lookup for an existing hash table, and returns a pointer > +to > + * the table if found. > + * > + * @param name > + * Name of the hash table to find > + * > + * @return > + * pointer to hash table structure or NULL on error with rte_errno > + * set appropriately. > + */ > +__rte_experimental > +struct rte_k32v64_hash_table * > +rte_k32v64_hash_find_existing(const char *name); > + > +/** > + * Create a new hash table for use with four byte keys. > + * > + * @param params > + * Parameters used in creation of hash table. > + * > + * @return > + * Pointer to hash table structure that is used in future hash table > + * operations, or NULL on error with rte_errno set appropriately. > + */ > +__rte_experimental > +struct rte_k32v64_hash_table * > +rte_k32v64_hash_create(const struct rte_k32v64_hash_params *params); > + > +/** > + * Free all memory used by a hash table. > + * > + * @param table > + * Hash table to deallocate. > + */ > +__rte_experimental > +void > +rte_k32v64_hash_free(struct rte_k32v64_hash_table *table); > + > +#ifdef __cplusplus > +} > +#endif > + > +#endif /* _RTE_K32V64_HASH_H_ */ > -- > 2.7.4