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 0AA14A0350; Tue, 23 Jun 2020 17:44:15 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 9EB431D6A2; Tue, 23 Jun 2020 17:44:14 +0200 (CEST) Received: from mga17.intel.com (mga17.intel.com [192.55.52.151]) by dpdk.org (Postfix) with ESMTP id E29D1E07 for ; Tue, 23 Jun 2020 17:44:12 +0200 (CEST) IronPort-SDR: EfTRVOg0SF4BppfiJaemW9N1DdGNcn3s7LLowTApLI16WYHQIZgshncyZRp2/xyamkJAVjPLXw jC5ItgkDm3aA== X-IronPort-AV: E=McAfee;i="6000,8403,9661"; a="124368974" X-IronPort-AV: E=Sophos;i="5.75,271,1589266800"; d="scan'208";a="124368974" X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga008.jf.intel.com ([10.7.209.65]) by fmsmga107.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 23 Jun 2020 08:44:11 -0700 IronPort-SDR: hSIwWbcehMIdQKU1mpxoJ/36Cb7sZ/HVf9hswl0FzD4oDajhRF/n8E/h7c1MNf5Y0tqluD2WA2 wnWOayKSivFw== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.75,271,1589266800"; d="scan'208";a="310494352" Received: from orsmsx103.amr.corp.intel.com ([10.22.225.130]) by orsmga008.jf.intel.com with ESMTP; 23 Jun 2020 08:44:10 -0700 Received: from orsmsx603.amr.corp.intel.com (10.22.229.16) by ORSMSX103.amr.corp.intel.com (10.22.225.130) with Microsoft SMTP Server (TLS) id 14.3.439.0; Tue, 23 Jun 2020 08:44:10 -0700 Received: from orsmsx603.amr.corp.intel.com (10.22.229.16) by ORSMSX603.amr.corp.intel.com (10.22.229.16) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.1713.5; Tue, 23 Jun 2020 08:44:10 -0700 Received: from ORSEDG001.ED.cps.intel.com (10.7.248.4) by orsmsx603.amr.corp.intel.com (10.22.229.16) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256) id 15.1.1713.5 via Frontend Transport; Tue, 23 Jun 2020 08:44:10 -0700 Received: from NAM02-CY1-obe.outbound.protection.outlook.com (104.47.37.59) by edgegateway.intel.com (134.134.137.100) with Microsoft SMTP Server (TLS) id 14.3.439.0; Tue, 23 Jun 2020 08:44:09 -0700 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=NrjRtU6WAg4TNmQHlmFxPBkRNic5oJxGaBTyM/5ZCb9MeRxYmSxddvpThoqL74IZEXzQwU1omuwomcyGclI3DHh0WFVszCoNMHHiJu7LVZ6GsvrVvCMXbYU6I58jMQqmfgY9Kju7IhcdVcdzgnpGm6VX5IqB3lQ65kXCrRAwwaQrtHEyh6z89W017bAvUFt2dYDpG5haBee5PfuGnIlI28pThQ0KvhENJMoJIjcuMNxAHoAi051ofFK3yhBcwCYXxKeYcLToNHxFxDZzbA+l40caTfJEANawtJjxM+/PF+Cc6xc7Kh0huPGJscAioFU/yHSkAbgktKVlz3bTrCj82Q== 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=b8D9Mp8ZMED/RIlYRviS1UOwh+FxTGiBoeNtI9Y0jOU=; b=liX7BSfqPiGIZ28oGreHI7nUrqW55Ok7D8khchlHOsMChN0VpNaTtZzPZcVJJ7fDM02FXMW4zlpA4VTjwoSHJa8C8+XOBpqxmaBSg6JTlJDs0XdnT4jdYZZID23zuApoNctsJ0J73FKuFcpM8V4CecIWXdUvrJHbn+YNJXSu1SQHna0AaZAkmnvO+kirUyRL/OdlrESfQVnjXmVstB1ItjhN6LZuNUs8y1YOFaFp07Hv1zHt1y+ZcS12KRUICjeIKe0SsB6FJ8BVsA3ut+nkGYUx+UHRmPjGeKPJqQsoHUV3eGsYUdTEUgynItXVJcjEQImFsWwCIVlsujt/5pRcDw== 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=b8D9Mp8ZMED/RIlYRviS1UOwh+FxTGiBoeNtI9Y0jOU=; b=FxZ1AVQxTXHDd5UDiI+W6hBQYjAvrxLnpZDzCKOQVco4sn5fDY4d1IIzRG9L5VPvfnahVn0d5e0FtnOKlo2TrZP7vfmCAvemZmOJ7w/Hci8ulPYs4EHCY5gWFkBJkFYH7HnNw3WAX9IN+CScGnVbAFJTweI89mGR/6ogCCAE46k= Received: from BYAPR11MB3301.namprd11.prod.outlook.com (2603:10b6:a03:7f::26) by BY5PR11MB3894.namprd11.prod.outlook.com (2603:10b6:a03:18c::20) 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 15:44:06 +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 15:44:06 +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/4AKjmllRA Date: Tue, 23 Jun 2020 15:44:06 +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.168] x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: 54a71698-1953-4444-e200-08d8178c4364 x-ms-traffictypediagnostic: BY5PR11MB3894: 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:2512; x-forefront-prvs: 04433051BF x-ms-exchange-senderadcheck: 1 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: YMEBcqE5/6SYqi8XwDpPG+JmJAyaglBTrBhsYny20UznuS6Zksn7KxTz1r6geT7cR929CIDfxXTb1Gqia9mJxywTf4xStNdzIU/tLyWz9h8S/vEVRmm6d8hfVllL0wXm/YciPJop/gXq59MSFWdwEH+hB455TJv2N/NeCWhHxqp6KbgSb7+XpjiGkpMnvO+Qzz4rFcxBDhU01KZybH+wYyjJOuz9IkyApHatLyuprkMMkec+8+z/0B2oPcefza3ZTrMwsvGlGuuQH7iK1NIdBK3w/UhV8mw9pydfw230VyZxteUrwIjxuTTtePqQhgFB 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)(396003)(366004)(346002)(136003)(39860400002)(376002)(71200400001)(33656002)(107886003)(7696005)(52536014)(478600001)(54906003)(55016002)(110136005)(83380400001)(2906002)(5660300002)(186003)(9686003)(8936002)(26005)(4326008)(66446008)(66946007)(316002)(86362001)(8676002)(64756008)(66476007)(66556008)(76116006)(6506007); DIR:OUT; SFP:1102; x-ms-exchange-antispam-messagedata: OxjyFMDYfZhUvrvecAnPLF4zF01IDpz+U6GgSy5VeyZXO/Y5p7Huj0kQXSn0R8ar/GJFKcVVuB/cMYyQYh9kFViv9rvptA5KGyPL2+jLy+9kzYE3uVsf2P51ek7kvN8uT15AQDSYNze4DaGrmPj4N4B2y6b5VcGmzXXFIavFx5YxBCoyvHKyCN29mSFgHf3fHst8N6b5Hyy80fS0Mrk7MlGuM1BvMgIzwtkdLscLlT0jdTBNXHFOyK6HgMz6n04l1T2IduCwZzXn5lKucLjfTRnxwgdNXiS8xKBctykuJ8NZcQ4H5iecqwNrPLowyyvN3TXQ8mdJ3Rl1UujRGDIJbbX21bb7fqvySy9XLjeunsBO0L37zBGM/kWEMmYGin7NkTPQGtEAShhyzBHBwylzZqppXHbn1JXUoyiEv7ZLlP4N19gubJiumWqMufPcBi33Do2BvR4orl7gFPfR8n3Xg3t8wYpiYpCt3NSyy51+r/e2bIT3oibv14KQtUj4Vn0G Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-MS-Exchange-CrossTenant-Network-Message-Id: 54a71698-1953-4444-e200-08d8178c4364 X-MS-Exchange-CrossTenant-originalarrivaltime: 23 Jun 2020 15:44:06.5301 (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: EZsT6vyuuvGZIsxjIVpfpswcgXnNH71tGjtVQQg98LOSC4GizA5XrIx9vNlC6U4oke6T6FAwrtPIBoyDIVN3g//iEnDK1OU5dXrhUX0t8RM= X-MS-Exchange-Transport-CrossTenantHeadersStamped: BY5PR11MB3894 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, > --- /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; > + > + 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); > + 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); I think this case also has to guarded with table->t[bucket].cnt updates. > + 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(); __atomic_thread_fence(__ATOMIC_RELEASE); ? > + 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); Same thought as above - safer to guard this mask update with cnt update. > + if (ent) > + rte_mempool_put(table->ext_ent_pool, ent); 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; > +} > +