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 70F43A0350; Wed, 24 Jun 2020 01:06:48 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 599171D6E8; Wed, 24 Jun 2020 01:06:47 +0200 (CEST) Received: from mga17.intel.com (mga17.intel.com [192.55.52.151]) by dpdk.org (Postfix) with ESMTP id 2DFE21D6E5 for ; Wed, 24 Jun 2020 01:06:46 +0200 (CEST) IronPort-SDR: DdZrXu3wrxT1JaRX8+K5p3hRSQu1tugEz/lNVLkceHOBJYyHXnw/T0r0rkfW/qSzq8ao4YJJ2q 5e6PJ4K2qMRA== X-IronPort-AV: E=McAfee;i="6000,8403,9661"; a="124509070" X-IronPort-AV: E=Sophos;i="5.75,272,1589266800"; d="scan'208";a="124509070" X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga001.jf.intel.com ([10.7.209.18]) by fmsmga107.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 23 Jun 2020 16:06:45 -0700 IronPort-SDR: rRZUJl+w0X8I/wPA2dx0p5AP6G6cI5pl3z11YJ7LzPitQEEPdMj8QazerafbQ3rXmeEVuU2XzS 9wwbrg+oONjg== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.75,272,1589266800"; d="scan'208";a="353956505" Received: from orsmsx107.amr.corp.intel.com ([10.22.240.5]) by orsmga001.jf.intel.com with ESMTP; 23 Jun 2020 16:06:44 -0700 Received: from orsmsx163.amr.corp.intel.com (10.22.240.88) by ORSMSX107.amr.corp.intel.com (10.22.240.5) with Microsoft SMTP Server (TLS) id 14.3.439.0; Tue, 23 Jun 2020 16:06:44 -0700 Received: from ORSEDG001.ED.cps.intel.com (10.7.248.4) by ORSMSX163.amr.corp.intel.com (10.22.240.88) with Microsoft SMTP Server (TLS) id 14.3.439.0; Tue, 23 Jun 2020 16:06:44 -0700 Received: from NAM10-BN7-obe.outbound.protection.outlook.com (104.47.70.108) by edgegateway.intel.com (134.134.137.100) with Microsoft SMTP Server (TLS) id 14.3.439.0; Tue, 23 Jun 2020 16:06:43 -0700 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=mw2LZaL1c9V2zlCgPFLbSKXHZsvsF7lxbjeugeB8w+M1KIz8Av4yxK2k8q9lvxJVT4O3EpXnDSWifx8iWHisq9upY6OLH+MRJdTvZRI0YuNZzcdQkRi9NxX4YZ6K71DXOMgGexSq3QB22z5noE5ex549JQ48ut4EAAuiC7jF6VuysEHjS2Q1EVArJUhVYiKOoSTZzKTKN+788zQxlUH/s61oY47/7iUTQM8pU6W4mpslq7QDz+5u6AWFDxlq3AprTvZQnV6IICux4SIvuYRRQowPlBJfq7z9ixW2r4k1MNy4JPDzhHym1NmWSpgSEK7kjJgFZHCbb+t4QYRepkDfqQ== 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=eoUOiyrj0t1qJytyVNPq6NfOm9prEFg61YvZeqMsbDs=; b=la/63w5ejzd2vbr5nOD4OdNywCAGRSSsZHOAy7EO2PtMXZ7gKS3qi0p3tBABpy2FS6aFU0PCdGVh1MSklS8wrEtYrXWAejR5pMz38iwaijOh1lbpiJZnvU6HqcOYtyFI64Af2wAKRF9Nn1Qgrl73yfzTToNeZNngjB+BSmvRARbsME1QxkwFks0S2/uT/M7VIBZ8RK7vhzRj7CSI/HuLE7JfLJPjL8BIGgXLsMmunyHIpR5mWsz1x5sOYwLfikhF1LfM7lCIjA1oBO/lGUPwYtsZx2gItpe/QxTsisSjgDFSm0VjPXCMEfeAL2aAHEG48f/ThERB4ptfV6vaRM8QHA== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=intel.com; dmarc=pass action=none header.from=intel.com; dkim=pass header.d=intel.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=intel.onmicrosoft.com; s=selector2-intel-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=eoUOiyrj0t1qJytyVNPq6NfOm9prEFg61YvZeqMsbDs=; b=iHPFwErEUxWDtwYRsEHDHfu7GPilKZyjij3OPB+oBIchyFBVGxr6eRVHsAiFLQOs5RZSEKEzBDZrDEx4+O63YLInGDSEtNF4S40Ckunwwk5LkmGrBbA2NBJY5qJ2bSzaN/5EFI8oEnfSOtPQ5hTWRWl+EAvIOegkpW27AF8h3xc= Received: from BYAPR11MB3301.namprd11.prod.outlook.com (2603:10b6:a03:7f::26) by BY5PR11MB3909.namprd11.prod.outlook.com (2603:10b6:a03:191::13) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3109.22; Tue, 23 Jun 2020 23:06:41 +0000 Received: from BYAPR11MB3301.namprd11.prod.outlook.com ([fe80::f160:29ab:b8f9:4189]) by BYAPR11MB3301.namprd11.prod.outlook.com ([fe80::f160:29ab:b8f9:4189%6]) with mapi id 15.20.3109.027; Tue, 23 Jun 2020 23:06:41 +0000 From: "Ananyev, Konstantin" To: "Medvedkin, Vladimir" , "dev@dpdk.org" CC: "Wang, Yipeng1" , "Gobriel, Sameh" , "Richardson, Bruce" Thread-Topic: [PATCH v4 1/4] hash: add kv hash library Thread-Index: AQHWJXM0zXpRGwrYl06SBHjKZH/4AKjmllRAgAB/+TA= Date: Tue, 23 Jun 2020 23:06:41 +0000 Message-ID: References: In-Reply-To: Accept-Language: en-GB, en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: dlp-product: dlpe-windows dlp-reaction: no-action dlp-version: 11.2.0.6 authentication-results: intel.com; dkim=none (message not signed) header.d=none;intel.com; dmarc=none action=none header.from=intel.com; x-originating-ip: [192.198.151.182] x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: 305630f0-51ff-4a40-afcc-08d817ca1773 x-ms-traffictypediagnostic: BY5PR11MB3909: x-ld-processed: 46c98d88-e344-4ed4-8496-4ed7712e255d,ExtAddr x-ms-exchange-transport-forked: True x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:4941; x-forefront-prvs: 04433051BF x-ms-exchange-senderadcheck: 1 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: EdGjtBbXloQSROFocanX255oj6tq9va6ldlPdGAWuzIm7xzyUIq7PonBa15I7WH4s1Tho434SS+8exlXHjCkl5IpUgDkcy7FE/jYrPxIMIsZjupJxW571QW7LKuR9AyT7jVzD8EvZ4wW3iQCTqMKs7i53LOY8R2aXGqf/xEvpe4PScH8v/LHuvRFr4Hx5yal/ZNRdwveeo/CFCPC3UF+ga0Ko9rGqErMEs5d07QC/A6cIDJhWNfCmWq6qOWud/BK33iwzURc9t5+lSn3wfanwUrUc1yVYi3PlGZxOU7WFDdNut+NMuR1ic5RPdXU8cdqN5QDLgG0h0+48r49UTQnVg== x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:BYAPR11MB3301.namprd11.prod.outlook.com; PTR:; CAT:NONE; SFTY:; SFS:(4636009)(366004)(346002)(136003)(39860400002)(396003)(376002)(54906003)(71200400001)(9686003)(110136005)(5660300002)(76116006)(66946007)(66476007)(2906002)(33656002)(66446008)(64756008)(66556008)(52536014)(2940100002)(55016002)(107886003)(83380400001)(86362001)(4326008)(8676002)(26005)(186003)(6506007)(7696005)(478600001)(316002)(8936002); DIR:OUT; SFP:1102; x-ms-exchange-antispam-messagedata: daP3XWhYjKODmAFlzhzQCzhB4pdr8i0B4PmLT7AA7y1ptpnNwmSt4HAYruNBJcACyEnU9wh2QR09Z/1Wg7Zdl8uPm4Hh9h7n9iaX4k3XXltziqP1r4aCoR4fIXmtpA10VMbf58jKuJc5aCPxp6L7SwZQgr9O1jc8PRpun2lCs1gTttmBYnWsWS7g3lBlZinEKubHIhW8yGHH3q7FdOBzhQE0krEwembJUKBFRdMjrm/pqH34hQxAOxsTZ/Wq7MAAybHlcIawkeuKgmXVA/Ilrs3sA50QDhxQQazROuUd7oj94r2ulhgwdjXJdN/hQw4L+uMiysJhMcY6ndurFeGblkAUbRq3fujYOj7p8u7Q+8fsBCffhnZQkxlwCJc/bHCqBLtZTfocznbsZ+94nKJ1Q8niEG7j7hkaotjeNrFoPfsQuWRmUOgTE+wpE2fTzVgU+JfcubJbLHKcqUz6qJ+BtxGA83/fpnZLt7uY3+k10nDJJlDEw0vNVHJEEAfD4oxJ Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-MS-Exchange-CrossTenant-Network-Message-Id: 305630f0-51ff-4a40-afcc-08d817ca1773 X-MS-Exchange-CrossTenant-originalarrivaltime: 23 Jun 2020 23:06:41.5016 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: 46c98d88-e344-4ed4-8496-4ed7712e255d X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-CrossTenant-userprincipalname: GSwCbD3gmxDFQrOBO+hOzGaw2kP49Gk3eAluOWTIJaGbziURodU2V6Fg/qkDzrsSR4xScqOVDqNbe7Yv95ED4o+eY5AwCsvlp3nSh6N+L7s= X-MS-Exchange-Transport-CrossTenantHeadersStamped: BY5PR11MB3909 X-OriginatorOrg: intel.com Subject: Re: [dpdk-dev] [PATCH v4 1/4] hash: add kv 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, >=20 > > --- /dev/null > > +++ b/lib/librte_hash/k32v64_hash.c > > @@ -0,0 +1,277 @@ > > +/* SPDX-License-Identifier: BSD-3-Clause > > + * Copyright(c) 2020 Intel Corporation > > + */ > > + > > +#include > > + > > +#include > > +#include > > +#include > > + > > +#include "k32v64_hash.h" > > + > > +static inline int > > +k32v64_hash_lookup(struct k32v64_hash_table *table, uint32_t key, > > + uint32_t hash, uint64_t *value) > > +{ > > + return __k32v64_hash_lookup(table, key, hash, value, __kv_cmp_keys); > > +} > > + > > +static int > > +k32v64_hash_bulk_lookup(struct rte_kv_hash_table *ht, void *keys_p, > > + uint32_t *hashes, void *values_p, unsigned int n) > > +{ > > + struct k32v64_hash_table *table =3D (struct k32v64_hash_table *)ht; > > + uint32_t *keys =3D keys_p; > > + uint64_t *values =3D values_p; > > + 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; As a nit - this formal parameter checking better to do in public function (rte_kv_hash_bulk_lookup) before de-refencing table and calling actual look= up(). =20 Same story for modify() - formal parameter checking can be done at the top = of public function. BTW, why to unite add/delete into modify(), if internally you have 2 differ= ent functions (for add/delete) anyway? > > + > > + for (i =3D 0; i < n; i++) { > > + ret =3D k32v64_hash_lookup(table, keys[i], hashes[i], > > + &values[i]); > > + if (ret =3D=3D 0) > > + cnt++; > > + } > > + return cnt; > > +} > > + > > +#ifdef CC_AVX512VL_SUPPORT > > +int > > +k32v64_hash_bulk_lookup_avx512vl(struct rte_kv_hash_table *ht, > > + void *keys_p, uint32_t *hashes, void *values_p, unsigned int n); > > +#endif > > + > > +static rte_kv_hash_bulk_lookup_t > > +get_lookup_bulk_fn(void) > > +{ > > +#ifdef CC_AVX512VL_SUPPORT > > + if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX512VL)) > > + return k32v64_hash_bulk_lookup_avx512vl; > > +#endif > > + return k32v64_hash_bulk_lookup; > > +} > > + > > +static int > > +k32v64_hash_add(struct k32v64_hash_table *table, uint32_t key, > > + uint32_t hash, uint64_t value, uint64_t *old_value, int *found) > > +{ > > + uint32_t bucket; > > + int i, idx, ret; > > + uint8_t msk; > > + struct 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 < K32V64_KEYS_PER_BUCKET; i++) { > > + if ((key =3D=3D table->t[bucket].key[i]) && > > + (table->t[bucket].key_mask & (1 << i))) { > > + *old_value =3D table->t[bucket].val[i]; > > + *found =3D 1; > > + __atomic_fetch_add(&table->t[bucket].cnt, 1, > > + __ATOMIC_ACQUIRE); After another thought - atomic add is probably an overkill here. Something like: void update_start(struct k32v64_hash_bucket *bkt) { bkt->cnt++; __atomic_thread_fence(__ATOMIC_ACQ_REL); } void update_finish(struct k32v64_hash_bucket *bkt) { __atomic_thread_fence(__ATOMIC_ACQ_REL); bkt->cnt++; } I think should be sufficient here. > > + table->t[bucket].val[i] =3D value; > > + __atomic_fetch_add(&table->t[bucket].cnt, 1, > > + __ATOMIC_RELEASE); > > + return 0; > > + } > > + } > > + > > + if (!SLIST_EMPTY(&table->t[bucket].head)) { > > + SLIST_FOREACH(ent, &table->t[bucket].head, next) { > > + if (ent->key =3D=3D key) { > > + *old_value =3D ent->val; > > + *found =3D 1; > > + __atomic_fetch_add(&table->t[bucket].cnt, 1, > > + __ATOMIC_ACQUIRE); > > + ent->val =3D value; > > + __atomic_fetch_add(&table->t[bucket].cnt, 1, > > + __ATOMIC_RELEASE); > > + 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; > > + __atomic_or_fetch(&table->t[bucket].key_mask, 1 << idx, > > + __ATOMIC_RELEASE); >=20 > I think this case also has to guarded with table->t[bucket].cnt updates. >=20 > > + table->nb_ent++; > > + *found =3D 0; > > + 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(); >=20 > __atomic_thread_fence(__ATOMIC_RELEASE); > ? >=20 > > + 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); > > + > > + table->nb_ent++; > > + table->nb_ext_ent++; > > + *found =3D 0; > > + return 0; > > +} > > + > > +static int > > +k32v64_hash_delete(struct k32v64_hash_table *table, uint32_t key, > > + uint32_t hash, uint64_t *old_value) > > +{ > > + uint32_t bucket; > > + int i; > > + struct k32v64_ext_ent *ent; > > + > > + if (table =3D=3D NULL) > > + return -EINVAL; > > + > > + bucket =3D hash & table->bucket_msk; > > + > > + for (i =3D 0; i < K32V64_KEYS_PER_BUCKET; i++) { > > + if ((key =3D=3D table->t[bucket].key[i]) && > > + (table->t[bucket].key_mask & (1 << i))) { > > + *old_value =3D table->t[bucket].val[i]; > > + ent =3D SLIST_FIRST(&table->t[bucket].head); > > + if (ent) { > > + __atomic_fetch_add(&table->t[bucket].cnt, 1, > > + __ATOMIC_ACQUIRE); > > + table->t[bucket].key[i] =3D ent->key; > > + table->t[bucket].val[i] =3D ent->val; > > + SLIST_REMOVE_HEAD(&table->t[bucket].head, next); > > + __atomic_fetch_add(&table->t[bucket].cnt, 1, > > + __ATOMIC_RELEASE); > > + table->nb_ext_ent--; > > + } else > > + __atomic_and_fetch(&table->t[bucket].key_mask, > > + ~(1 << i), __ATOMIC_RELEASE); >=20 > Same thought as above - safer to guard this mask update with cnt update. >=20 > > + if (ent) > > + rte_mempool_put(table->ext_ent_pool, ent); >=20 > Can't this 'if(ent)' be merged with previous 'if (ent) {...}' above? >=20 > > + 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; > > + > > + *old_value =3D ent->val; > > + > > + __atomic_fetch_add(&table->t[bucket].cnt, 1, __ATOMIC_ACQUIRE); > > + SLIST_REMOVE(&table->t[bucket].head, ent, k32v64_ext_ent, next); > > + __atomic_fetch_add(&table->t[bucket].cnt, 1, __ATOMIC_RELEASE); > > + rte_mempool_put(table->ext_ent_pool, ent); > > + > > + table->nb_ext_ent--; > > + table->nb_ent--; > > + > > + return 0; > > +} > > +