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 93A74A0350; Wed, 24 Jun 2020 03:19:39 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 9FDC71D6F9; Wed, 24 Jun 2020 03:19:38 +0200 (CEST) Received: from mga05.intel.com (mga05.intel.com [192.55.52.43]) by dpdk.org (Postfix) with ESMTP id C17BA1D6EF for ; Wed, 24 Jun 2020 03:19:36 +0200 (CEST) IronPort-SDR: BhdP9JlRLMDljDL/YoYXvfJzJ9+R2yLbrhNwVzdq0GBENyPYNOqkuCOe50+KiEIc5yKebb72bn PbxaGPAhOwYg== X-IronPort-AV: E=McAfee;i="6000,8403,9661"; a="228968803" X-IronPort-AV: E=Sophos;i="5.75,273,1589266800"; d="scan'208";a="228968803" X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga003.fm.intel.com ([10.253.24.29]) by fmsmga105.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 23 Jun 2020 18:19:35 -0700 IronPort-SDR: GNkPb0/+wGMJ6A6iUphqGr8oC+SKb+c0nhzy9mE+SmQAJDd+3YE1+s8afwBqgaj+8XL3YOJ8k3 NrYXKhpOKVnw== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.75,273,1589266800"; d="scan'208";a="319312724" Received: from orsmsx106.amr.corp.intel.com ([10.22.225.133]) by FMSMGA003.fm.intel.com with ESMTP; 23 Jun 2020 18:19:30 -0700 Received: from orsmsx602.amr.corp.intel.com (10.22.229.15) by ORSMSX106.amr.corp.intel.com (10.22.225.133) with Microsoft SMTP Server (TLS) id 14.3.439.0; Tue, 23 Jun 2020 18:19:30 -0700 Received: from orsmsx602.amr.corp.intel.com (10.22.229.15) by ORSMSX602.amr.corp.intel.com (10.22.229.15) 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 18:19:29 -0700 Received: from ORSEDG001.ED.cps.intel.com (10.7.248.4) by orsmsx602.amr.corp.intel.com (10.22.229.15) 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 18:19:29 -0700 Received: from NAM11-CO1-obe.outbound.protection.outlook.com (104.47.56.168) by edgegateway.intel.com (134.134.137.100) with Microsoft SMTP Server (TLS) id 14.3.439.0; Tue, 23 Jun 2020 18:19:29 -0700 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=jnNDyE26VYdA3M95SDpSdkJpGu75F7lpJvUxP4u+SxY27WP3vWI+gM/NF5QEpusJP6wefLzqEPS7QBADRSK1VYglmWLOitzNHqnyCIFKw01kDI+p68q7FjxhmSQ5z/3zR1vgWYTzvakEbZrTTL+OPUTWBbn1/3IVzXFZ2POuNvNYFOR+C3nPeZEksR9dOSeJwcMQD8pthSMi+gx2yShKu3EzcCt3Ae9rfDVbGvcEO/z4d5oWDhPRinXF+5lqoMLQ9hyPtgJSjoDaBHjaTOKdfgKQ3BFRqnA2htcRsWsWquoyQJiD/1jCZ2sQ1pvh13MEdu1K7vsdPj9irxap5CRJxw== 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=t+7UYW3z2JD2wFUFgI41cJtIYJSc7IeV38iPFxecj0o=; b=Fawc5lggOIBHhf3IW/GqO+gTff6bEiTohXJV/MT3Pw1YntMgNcbZZo/q+qUkykJySN5K46WwlEpXqa7mreWvzl4aSg7PX6QOJ6jJiGpZyWqI/tm3k26myGY9dt6CJJbAL8xuMoCQdNl/K7M6lLEwM4c1NZktC/YXJY9V/m4gDCQlMMMW2vXf95B8nEA+1ic2xJx1ZrgQShs2nFdaWhyGOGEDLVbs/h9pFyRWRrD2GQ4xPXCl/rKErbwULFFb6WQC8Ry5xFiH5w5kXRbuPacPscfwv+NP3Uv7UfiqhIuegTi8NmqAb6BE7FF8kT7bbvC82xlgnjhM4eOQWXXhx5BlzQ== 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=t+7UYW3z2JD2wFUFgI41cJtIYJSc7IeV38iPFxecj0o=; b=WQi+jM3LdbKE4R02BGMPrS1Mf17CLnZ8woAcWaB8Cp573tWoqg6TU7GiVKV6gzRxPlZ9Q6lXsDMnt3FB45zInQFr2JyT344dYUVegWVDW89G76Ib757g8nx15+f8YbA8EnZBpEG8Vn5DpYZy8WRmgG7h1mfuIXkzIPehAdKmk5s= Received: from BYAPR11MB3494.namprd11.prod.outlook.com (2603:10b6:a03:86::15) by BY5PR11MB4040.namprd11.prod.outlook.com (2603:10b6:a03:186::27) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3109.22; Wed, 24 Jun 2020 01:19:25 +0000 Received: from BYAPR11MB3494.namprd11.prod.outlook.com ([fe80::7d9c:1c6d:8919:c0ad]) by BYAPR11MB3494.namprd11.prod.outlook.com ([fe80::7d9c:1c6d:8919:c0ad%5]) with mapi id 15.20.3109.027; Wed, 24 Jun 2020 01:19:25 +0000 From: "Wang, Yipeng1" To: "Medvedkin, Vladimir" , "dev@dpdk.org" CC: "Ananyev, Konstantin" , "Gobriel, Sameh" , "Richardson, Bruce" Thread-Topic: [PATCH v4 1/4] hash: add kv hash library Thread-Index: AQHWJXM01+KgXopOGkiEA4nLxaInb6jnO16Q Date: Wed, 24 Jun 2020 01:19:25 +0000 Message-ID: References: In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: dlp-reaction: no-action dlp-version: 11.2.0.6 dlp-product: dlpe-windows 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: [134.134.136.223] x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: ea70fb50-3b48-4602-1c1d-08d817dca25b x-ms-traffictypediagnostic: BY5PR11MB4040: 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:2657; x-forefront-prvs: 0444EB1997 x-ms-exchange-senderadcheck: 1 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: Oa+fips1KlqSF5xQaFaCrkb/hZq2zoiDWPlvUuBjWoRQQcI4cjHNXWRqe9zHk0EZDQYtifEywwjKsy4sTQZtJO05n6wWrOEQVJ72VG8gLEeGXz2ZwYYC5efB3m6h7EoCSoRqgWhk2yFXhlbWAKoN568YAA+C6WtsdxJ5q3Df1Fj15lb9G5NaHG6UQDll7Oeu4rhk6gEo/+OUa/HGI+0dGlBvPHDnGx9Pmym0w/JwchIcl0KttZw30ZKnhzByx/f50qpumLCb7oWt+u7pmCtsehh+pcUgxxxAN2zMMvvqZ4c48la3KwTlhi/QsQ+Y3XtharI8c+TCO9yWKpH2idw2Uw== x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:BYAPR11MB3494.namprd11.prod.outlook.com; PTR:; CAT:NONE; SFTY:; SFS:(4636009)(346002)(396003)(366004)(39860400002)(136003)(376002)(5660300002)(66946007)(66446008)(64756008)(66556008)(66476007)(2906002)(86362001)(71200400001)(30864003)(52536014)(26005)(54906003)(76116006)(7696005)(53546011)(6506007)(4326008)(107886003)(316002)(110136005)(8676002)(55016002)(186003)(8936002)(9686003)(83380400001)(33656002)(478600001)(559001)(579004); DIR:OUT; SFP:1102; x-ms-exchange-antispam-messagedata: Q/UcOkRkdzEM8I7ZwQJBqqCRnl/0J7XQ2jA3hJ2HSOkIlFI6FXkfyVDxWUjg6MJMsa04K61zvQzgiUyoHNKCIil8n81dBjYuHDbtsUDH8f9cOBXJT+HuVIMpP0As3C+6YbXEQADUd5jWxzpayv86aVzdtysKd83FUeJ0y8kGH6Q7X9nzkS9Hv2KPsjVak0eGDfYqLkLyM2ud5BRywkdM0InFGMvr+6ejF/pvM8oqyIJxgo+7eiX+4ZMjyaqo7kTBA44fatWgckaWQZbdIYKNDE/V+G+kV09OOk8NqSkEe782IbT8ENo9pYSYjLOArqqbJ+p6iz0bOiodC4HdMz5CiCAB32LrQmDl9vlN7AaW3FsszbvMO0u3iUG2B+5wAjx1wAmXGN9d5ooOTLKx1bnygqPgwnPnEbnKGUC3VGcliDXQPTodvVCreLsqSVFhfyHg1cwXP6Tb0RxrZgffPGrml7r8P9QCvyIbq8DaktxZN+fwRrrTIIAawEHyqM1UhfJj Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-MS-Exchange-CrossTenant-Network-Message-Id: ea70fb50-3b48-4602-1c1d-08d817dca25b X-MS-Exchange-CrossTenant-originalarrivaltime: 24 Jun 2020 01:19:25.5839 (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: ZDYNHbcWPC0HWUtSkE0Dst97M1b2qyCL+v8mtqDpfwQmyo0LUjgsHLrhMvwIEBsNDpot1X5TKqLrkoUO2/UM3g== X-MS-Exchange-Transport-CrossTenantHeadersStamped: BY5PR11MB4040 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" > -----Original Message----- > From: Medvedkin, Vladimir > Sent: Friday, May 8, 2020 12:59 PM > To: dev@dpdk.org > Cc: Ananyev, Konstantin ; Wang, Yipeng1 > ; Gobriel, Sameh ; > Richardson, Bruce > Subject: [PATCH v4 1/4] hash: add kv hash library >=20 > KV hash is a special optimized key-value storage for fixed key and value = sizes. > At the moment it supports 32 bit keys and 64 bit values. This table is ha= sh > function agnostic so user must provide precalculated hash signature for > add/delete/lookup operations. >=20 > Signed-off-by: Vladimir Medvedkin > --- > lib/Makefile | 2 +- > lib/librte_hash/Makefile | 14 +- > lib/librte_hash/k32v64_hash.c | 277 > +++++++++++++++++++++++++++++++++ > lib/librte_hash/k32v64_hash.h | 98 ++++++++++++ > lib/librte_hash/k32v64_hash_avx512vl.c | 59 +++++++ > lib/librte_hash/meson.build | 17 +- > lib/librte_hash/rte_hash_version.map | 6 +- > lib/librte_hash/rte_kv_hash.c | 184 ++++++++++++++++++++++ > lib/librte_hash/rte_kv_hash.h | 169 ++++++++++++++++++++ > 9 files changed, 821 insertions(+), 5 deletions(-) create mode 100644 > lib/librte_hash/k32v64_hash.c create mode 100644 > lib/librte_hash/k32v64_hash.h create mode 100644 > lib/librte_hash/k32v64_hash_avx512vl.c > create mode 100644 lib/librte_hash/rte_kv_hash.c create mode 100644 > lib/librte_hash/rte_kv_hash.h >=20 > diff --git a/lib/Makefile b/lib/Makefile index 9d24609..42769e9 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_ethdev \ > 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..a0cdee9 100644 > --- a/lib/librte_hash/Makefile > +++ b/lib/librte_hash/Makefile > @@ -8,13 +8,15 @@ 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_kv_hash.c > +SRCS-$(CONFIG_RTE_LIBRTE_HASH) +=3D k32v64_hash.c >=20 > # install this header file > SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include :=3D rte_hash.h @@ -27,5 > +29,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_kv_hash.h > + > +CC_AVX512VL_SUPPORT=3D$(shell $(CC) -mavx512vl -dM -E - 2>&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_k32v64_hash.o +=3D -DCC_AVX512VL_SUPPORT endif >=20 > include $(RTE_SDK)/mk/rte.lib.mk > diff --git a/lib/librte_hash/k32v64_hash.c b/lib/librte_hash/k32v64_hash.= c > new file mode 100644 index 0000000..24cd63a > --- /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]); [Wang, Yipeng] You don't need to start a new line for values. > + if (ret =3D=3D 0) > + cnt++; > + } > + return cnt; > +} > + > +#ifdef CC_AVX512VL_SUPPORT [Wang, Yipeng] Why not use the already provided, e.g. #if defined(RTE_MACHI= NE_CPUFLAG_SSE2) like rte_hash does? > +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); > + 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(); > + 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); > + if (ent) > + rte_mempool_put(table->ext_ent_pool, > ent); > + 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); > + [Wang, Yipeng] I am not sure if delete can be called safely with other look= up threads. The item could be recycled to be used by another add while a lookup thread = traversing the linked list. This is similar to why we need the RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL flag= and related API in rte_hash. > + table->nb_ext_ent--; > + table->nb_ent--; > + > + return 0; > +} > + > +static int > +k32v64_modify(struct rte_kv_hash_table *table, void *key_p, uint32_t > hash, > + enum rte_kv_modify_op op, void *value_p, int *found) { > + struct k32v64_hash_table *ht =3D (struct k32v64_hash_table *)table; > + uint32_t *key =3D key_p; > + uint64_t value; > + > + if ((ht =3D=3D NULL) || (key =3D=3D NULL) || (value_p =3D=3D NULL) || > + (found =3D=3D NULL) || (op >=3D > RTE_KV_MODIFY_OP_MAX)) { > + return -EINVAL; > + } > + > + value =3D *(uint64_t *)value_p; > + switch (op) { > + case RTE_KV_MODIFY_ADD: > + return k32v64_hash_add(ht, *key, hash, value, value_p, > found); > + case RTE_KV_MODIFY_DEL: > + return k32v64_hash_delete(ht, *key, hash, value_p); > + default: > + break; > + } [Wang, Yipeng] A question would be why put del and add inside another mod w= rapper. If we don't wrap del and add like this, we could get rid of this branch. > + > + return -EINVAL; > +} > + > +struct rte_kv_hash_table * > +k32v64_hash_create(const struct rte_kv_hash_params *params) { > + char hash_name[RTE_KV_HASH_NAMESIZE]; > + struct k32v64_hash_table *ht =3D NULL; > + 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)) { [Wang, Yipeng] Should we check if entry count larger than keys_per_bucket a= s well? > + rte_errno =3D EINVAL; > + return NULL; > + } > + > + ret =3D snprintf(hash_name, sizeof(hash_name), "KV_%s", params- > >name); > + if (ret < 0 || ret >=3D RTE_KV_HASH_NAMESIZE) { > + rte_errno =3D ENAMETOOLONG; > + return NULL; > + } > + > + max_ent =3D rte_align32pow2(params->entries); > + nb_buckets =3D max_ent / K32V64_KEYS_PER_BUCKET; [Wang, Yipeng] Macro to check if keys_per_bucket need to be power of 2 > + mem_size =3D sizeof(struct k32v64_hash_table) + > + sizeof(struct k32v64_hash_bucket) * nb_buckets; > + > + mp =3D rte_mempool_create(hash_name, max_ent, > + sizeof(struct k32v64_ext_ent), 0, 0, NULL, NULL, NULL, NULL, > + params->socket_id, 0); > + > + if (mp =3D=3D NULL) > + return NULL; > + > + ht =3D rte_zmalloc_socket(hash_name, mem_size, > + RTE_CACHE_LINE_SIZE, params->socket_id); > + if (ht =3D=3D NULL) { > + rte_mempool_free(mp); > + return NULL; > + } > + > + memcpy(ht->pub.name, hash_name, sizeof(ht->pub.name)); > + ht->max_ent =3D max_ent; > + ht->bucket_msk =3D nb_buckets - 1; > + ht->ext_ent_pool =3D mp; > + ht->pub.lookup =3D get_lookup_bulk_fn(); [Wang, Yipeng] Inside the function, we also need to check the CPUID during = runtime to decide if AVX can be used, not only compile time. You could refer to example from rte_hash: ... if (rte_cpu_get_flag_enabled(= RTE_CPUFLAG_SSE2)) ... > + ht->pub.modify =3D k32v64_modify; > + > + return (struct rte_kv_hash_table *)ht; } > + > +void > +k32v64_hash_free(struct rte_kv_hash_table *ht) { > + if (ht =3D=3D NULL) > + return; > + > + rte_mempool_free(((struct k32v64_hash_table *)ht)- > >ext_ent_pool); > + rte_free(ht); > +} > diff --git a/lib/librte_hash/k32v64_hash.h b/lib/librte_hash/k32v64_hash.= h > new file mode 100644 index 0000000..10061a5 > --- /dev/null > +++ b/lib/librte_hash/k32v64_hash.h > @@ -0,0 +1,98 @@ > +/* SPDX-License-Identifier: BSD-3-Clause > + * Copyright(c) 2020 Intel Corporation > + */ > + > +#include > + > +#define K32V64_KEYS_PER_BUCKET 4 > +#define K32V64_WRITE_IN_PROGRESS 1 > +#define VALID_KEY_MSK ((1 << K32V64_KEYS_PER_BUCKET) - 1) > + > +struct k32v64_ext_ent { > + SLIST_ENTRY(k32v64_ext_ent) next; > + uint32_t key; > + uint64_t val; > +}; > + > +struct k32v64_hash_bucket { > + uint32_t key[K32V64_KEYS_PER_BUCKET]; > + uint64_t val[K32V64_KEYS_PER_BUCKET]; > + uint8_t key_mask; > + uint32_t cnt; > + SLIST_HEAD(k32v64_list_head, k32v64_ext_ent) head; } > +__rte_cache_aligned; > + > +struct k32v64_hash_table { > + struct rte_kv_hash_table pub; /**< Public part */ [Wang, Yipeng] Do we need to have the pub filed? Could we just init the pub= lic part in the public create function? > + 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; > + __extension__ struct k32v64_hash_bucket t[0]; > +}; > + > +typedef int (*k32v64_cmp_fn_t) > +(struct k32v64_hash_bucket *bucket, uint32_t key, uint64_t *val); > + > +static inline int > +__kv_cmp_keys(struct k32v64_hash_bucket *bucket, uint32_t key, > + uint64_t *val) > +{ > + int i; > + > + for (i =3D 0; i < K32V64_KEYS_PER_BUCKET; i++) { > + if ((key =3D=3D bucket->key[i]) && > + (bucket->key_mask & (1 << i))) { > + *val =3D bucket->val[i]; > + return 1; > + } > + } > + > + return 0; > +} > + > +static inline int > +__k32v64_hash_lookup(struct k32v64_hash_table *table, uint32_t key, > + uint32_t hash, uint64_t *value, k32v64_cmp_fn_t cmp_f) { > + uint64_t val =3D 0; > + struct k32v64_ext_ent *ent; > + uint32_t cnt; > + int found =3D 0; > + uint32_t bucket =3D hash & table->bucket_msk; > + > + do { > + > + do { > + cnt =3D __atomic_load_n(&table->t[bucket].cnt, > + __ATOMIC_ACQUIRE); > + } while (unlikely(cnt & K32V64_WRITE_IN_PROGRESS)); > + > + 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; > + } > + } > + } > + __atomic_thread_fence(__ATOMIC_RELEASE); > + } while (unlikely(cnt !=3D __atomic_load_n(&table->t[bucket].cnt, > + __ATOMIC_RELAXED))); > + > + if (found =3D=3D 1) { > + *value =3D val; > + return 0; > + } else > + return -ENOENT; > +} > + > +struct rte_kv_hash_table * > +k32v64_hash_create(const struct rte_kv_hash_params *params); > + > +void > +k32v64_hash_free(struct rte_kv_hash_table *ht); > diff --git a/lib/librte_hash/k32v64_hash_avx512vl.c > b/lib/librte_hash/k32v64_hash_avx512vl.c > new file mode 100644 > index 0000000..75cede5 > --- /dev/null > +++ b/lib/librte_hash/k32v64_hash_avx512vl.c > @@ -0,0 +1,59 @@ > +/* SPDX-License-Identifier: BSD-3-Clause > + * Copyright(c) 2020 Intel Corporation > + */ > + > +#include "k32v64_hash.h" > + > +int > +k32v64_hash_bulk_lookup_avx512vl(struct rte_kv_hash_table *ht, void > *keys_p, > + uint32_t *hashes, void *values_p, unsigned int n); > + > +static inline int > +k32v64_cmp_keys_avx512vl(struct 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 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_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_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..0d014ea 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_kv_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_kv_hash.c'= , > +'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 c2a9094..614e0a5 100644 > --- a/lib/librte_hash/rte_hash_version.map > +++ b/lib/librte_hash/rte_hash_version.map > @@ -36,5 +36,9 @@ EXPERIMENTAL { > rte_hash_lookup_with_hash_bulk; > rte_hash_lookup_with_hash_bulk_data; > rte_hash_max_key_id; > - > + rte_kv_hash_create; > + rte_kv_hash_find_existing; > + rte_kv_hash_free; > + rte_kv_hash_add; > + rte_kv_hash_delete; > }; > diff --git a/lib/librte_hash/rte_kv_hash.c b/lib/librte_hash/rte_kv_hash.= c > new file mode 100644 index 0000000..03df8db > --- /dev/null > +++ b/lib/librte_hash/rte_kv_hash.c > @@ -0,0 +1,184 @@ > +/* SPDX-License-Identifier: BSD-3-Clause > + * Copyright(c) 2020 Intel Corporation > + */ > + > +#include > + > +#include > +#include > +#include > +#include > +#include > + > +#include [Wang, Yipeng] I think for this header we should use quotes "" > +#include "k32v64_hash.h" > + > +TAILQ_HEAD(rte_kv_hash_list, rte_tailq_entry); > + > +static struct rte_tailq_elem rte_kv_hash_tailq =3D { > + .name =3D "RTE_KV_HASH", > +}; > + > +EAL_REGISTER_TAILQ(rte_kv_hash_tailq); > + > +int > +rte_kv_hash_add(struct rte_kv_hash_table *table, void *key, > + uint32_t hash, void *value, int *found) { > + if (table =3D=3D NULL) [Wang, Yipeng] To be more consistent, I think we should either also check key/value/found here, or just not chec= king at all and leave it to the next functions. > + return -EINVAL; > + > + return table->modify(table, key, hash, RTE_KV_MODIFY_ADD, > + value, found); > +} > + > +int > +rte_kv_hash_delete(struct rte_kv_hash_table *table, void *key, > + uint32_t hash, void *value) > +{ > + int found; > + > + if (table =3D=3D NULL) > + return -EINVAL; > + > + return table->modify(table, key, hash, RTE_KV_MODIFY_DEL, > + value, &found); > +} > + > +struct rte_kv_hash_table * > +rte_kv_hash_find_existing(const char *name) { > + struct rte_kv_hash_table *h =3D NULL; > + struct rte_tailq_entry *te; > + struct rte_kv_hash_list *kv_hash_list; > + > + kv_hash_list =3D RTE_TAILQ_CAST(rte_kv_hash_tailq.head, > + rte_kv_hash_list); > + > + rte_mcfg_tailq_read_lock(); > + TAILQ_FOREACH(te, kv_hash_list, next) { > + h =3D (struct rte_kv_hash_table *) te->data; > + if (strncmp(name, h->name, RTE_KV_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_kv_hash_table * > +rte_kv_hash_create(const struct rte_kv_hash_params *params) { > + char hash_name[RTE_KV_HASH_NAMESIZE]; > + struct rte_kv_hash_table *ht, *tmp_ht =3D NULL; > + struct rte_tailq_entry *te; > + struct rte_kv_hash_list *kv_hash_list; > + int ret; > + > + if ((params =3D=3D NULL) || (params->name =3D=3D NULL) || > + (params->entries =3D=3D 0) || > + (params->type >=3D RTE_KV_HASH_MAX)) { > + rte_errno =3D EINVAL; > + return NULL; > + } > + > + kv_hash_list =3D RTE_TAILQ_CAST(rte_kv_hash_tailq.head, > + rte_kv_hash_list); > + > + ret =3D snprintf(hash_name, sizeof(hash_name), "KV_%s", params- > >name); > + if (ret < 0 || ret >=3D RTE_KV_HASH_NAMESIZE) { > + rte_errno =3D ENAMETOOLONG; > + return NULL; > + } > + > + switch (params->type) { > + case RTE_KV_HASH_K32V64: > + ht =3D k32v64_hash_create(params); > + break; > + default: > + rte_errno =3D EINVAL; > + return NULL; > + } > + if (ht =3D=3D NULL) > + return ht; > + > + rte_mcfg_tailq_write_lock(); > + TAILQ_FOREACH(te, kv_hash_list, next) { > + tmp_ht =3D (struct rte_kv_hash_table *) te->data; > + if (strncmp(params->name, tmp_ht->name, > + RTE_KV_HASH_NAMESIZE) =3D=3D 0) > + break; > + } > + if (te !=3D NULL) { > + rte_errno =3D EEXIST; > + goto exit; > + } > + > + te =3D rte_zmalloc("KV_HASH_TAILQ_ENTRY", sizeof(*te), 0); > + if (te =3D=3D NULL) { > + RTE_LOG(ERR, HASH, "Failed to allocate tailq entry\n"); > + goto exit; > + } > + > + ht->type =3D params->type; > + te->data =3D (void *)ht; > + TAILQ_INSERT_TAIL(kv_hash_list, te, next); > + > + rte_mcfg_tailq_write_unlock(); > + > + return ht; > + > +exit: > + rte_mcfg_tailq_write_unlock(); > + switch (params->type) { > + case RTE_KV_HASH_K32V64: > + k32v64_hash_free(ht); > + break; > + default: > + break; > + } > + return NULL; > +} > + > +void > +rte_kv_hash_free(struct rte_kv_hash_table *ht) { > + struct rte_tailq_entry *te; > + struct rte_kv_hash_list *kv_hash_list; > + > + if (ht =3D=3D NULL) > + return; > + > + kv_hash_list =3D RTE_TAILQ_CAST(rte_kv_hash_tailq.head, > + rte_kv_hash_list); > + > + rte_mcfg_tailq_write_lock(); > + > + /* find out tailq entry */ > + TAILQ_FOREACH(te, kv_hash_list, next) { > + if (te->data =3D=3D (void *) ht) > + break; > + } > + > + > + if (te =3D=3D NULL) { > + rte_mcfg_tailq_write_unlock(); > + return; > + } > + > + TAILQ_REMOVE(kv_hash_list, te, next); > + > + rte_mcfg_tailq_write_unlock(); > + > + switch (ht->type) { > + case RTE_KV_HASH_K32V64: > + k32v64_hash_free(ht); > + break; > + default: > + break; > + } > + rte_free(te); > +} > diff --git a/lib/librte_hash/rte_kv_hash.h b/lib/librte_hash/rte_kv_hash.= h > new file mode 100644 index 0000000..c0375d1 > --- /dev/null > +++ b/lib/librte_hash/rte_kv_hash.h > @@ -0,0 +1,169 @@ > +/* SPDX-License-Identifier: BSD-3-Clause > + * Copyright(c) 2020 Intel Corporation > + */ > + > +#ifndef _RTE_KV_HASH_H_ > +#define _RTE_KV_HASH_H_ > + > +#ifdef __cplusplus > +extern "C" { > +#endif > + > +#include > +#include > +#include > + > +#define RTE_KV_HASH_NAMESIZE 32 > + > +enum rte_kv_hash_type { > + RTE_KV_HASH_K32V64, > + RTE_KV_HASH_MAX > +}; > + > +enum rte_kv_modify_op { > + RTE_KV_MODIFY_ADD, > + RTE_KV_MODIFY_DEL, > + RTE_KV_MODIFY_OP_MAX > +}; [Wang, Yipeng] Again, any particular reason that you combine add and del in= to an additional struct mod? > + > +struct rte_kv_hash_params { > + const char *name; > + uint32_t entries; > + int socket_id; > + enum rte_kv_hash_type type; > +}; > + > +struct rte_kv_hash_table; > + > +typedef int (*rte_kv_hash_bulk_lookup_t) (struct rte_kv_hash_table > +*table, void *keys, uint32_t *hashes, > + void *values, unsigned int n); > + > +typedef int (*rte_kv_hash_modify_t) > +(struct rte_kv_hash_table *table, void *key, uint32_t hash, > + enum rte_kv_modify_op op, void *value, int *found); > + > +struct rte_kv_hash_table { > + char name[RTE_KV_HASH_NAMESIZE]; /**< Name of the > hash. */ > + rte_kv_hash_bulk_lookup_t lookup; > + rte_kv_hash_modify_t modify; > + enum rte_kv_hash_type type; > +}; > + > +/** > + * Lookup bulk of keys. > + * This function is multi-thread safe with regarding to other lookup thr= eads. > + * > + * @param table > + * Hash table to add the key to. > + * @param keys > + * Pointer to array of keys > + * @param hashes > + * Pointer to array of hash values associated with keys. > + * @param values > + * Pointer to array of value corresponded to keys > + * If the key was not found the corresponding value remains intact. > + * @param n > + * Number of keys to lookup in batch. > + * @return > + * -EINVAL if there's an error, otherwise number of successful lookups= . > + */ [Wang, Yipeng] experimental tag > +static inline int > +rte_kv_hash_bulk_lookup(struct rte_kv_hash_table *table, > + void *keys, uint32_t *hashes, void *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 regarding to add/delete > +functions > + * and should only be called from one thread. > + * However it is safe to call it along with lookup. > + * > + * @param table > + * 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. > + * @found > + * 0 if no previously added key was found > + * 1 previously added key was found, old value associated with the key > + * was written to *value > + * @return > + * 0 if ok, or negative value on error. > + */ > +__rte_experimental > +int > +rte_kv_hash_add(struct rte_kv_hash_table *table, void *key, > + uint32_t hash, void *value, int *found); > + > +/** > + * Remove a key with a given hash value from an existing hash table. > + * This operation is not multi-thread safe regarding to add/delete > +functions > + * and should only be called from one thread. > + * However it is safe to call it along with lookup. > + * > + * @param table > + * Hash table to remove the key from. > + * @param key > + * Key to remove from the hash table. > + * @param hash > + * hash value associated with key. > + * @param value > + * pointer to memory where the old value will be written to on success > + * @return > + * 0 if ok, or negative value on error. > + */ > +__rte_experimental > +int > +rte_kv_hash_delete(struct rte_kv_hash_table *table, void *key, > + uint32_t hash, void *value); > + > +/** > + * 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_kv_hash_table * > +rte_kv_hash_find_existing(const char *name); > + > +/** > + * Create a new hash table for use with four byte keys. [Wang, Yipeng] inaccurate comment, not 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_kv_hash_table * > +rte_kv_hash_create(const struct rte_kv_hash_params *params); > + > +/** > + * Free all memory used by a hash table. > + * > + * @param table > + * Hash table to deallocate. > + */ > +__rte_experimental > +void > +rte_kv_hash_free(struct rte_kv_hash_table *table); > + > +#ifdef __cplusplus > +} > +#endif > + > +#endif /* _RTE_KV_HASH_H_ */ > -- > 2.7.4