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 CB24EA0350; Thu, 25 Jun 2020 06:27:38 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 930BC5F69; Thu, 25 Jun 2020 06:27:37 +0200 (CEST) Received: from EUR01-VE1-obe.outbound.protection.outlook.com (mail-eopbgr140047.outbound.protection.outlook.com [40.107.14.47]) by dpdk.org (Postfix) with ESMTP id 0E7BB4F9C for ; Thu, 25 Jun 2020 06:27:36 +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=nv3J0X1aCaF+nTQg2AB1oStkqzzirhJijqEzV7XNS6s=; b=faSCg+c/VJFz3jnOrL0HKVCUlu7whXhZBLWq0iZlIRcQq1Wp7ZP+GzXK9RgunZ0Cll/CI371dI4tfuFGoSjEjXgkVXWit/zXypIq1soJEoHBH753UdKhbpaIltjXVFy32nu5o39iZryUOWgZSPTjd0FuyFClF5VrtxRLpBcMbMQ= Received: from AM6P191CA0076.EURP191.PROD.OUTLOOK.COM (2603:10a6:209:8a::17) by AM6PR08MB5254.eurprd08.prod.outlook.com (2603:10a6:20b:d6::15) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3109.25; Thu, 25 Jun 2020 04:27:33 +0000 Received: from VE1EUR03FT014.eop-EUR03.prod.protection.outlook.com (2603:10a6:209:8a:cafe::b9) by AM6P191CA0076.outlook.office365.com (2603:10a6:209:8a::17) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3131.20 via Frontend Transport; Thu, 25 Jun 2020 04:27:33 +0000 X-MS-Exchange-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 VE1EUR03FT014.mail.protection.outlook.com (10.152.19.38) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3131.20 via Frontend Transport; Thu, 25 Jun 2020 04:27:33 +0000 Received: ("Tessian outbound 2ba684f51d22:v59"); Thu, 25 Jun 2020 04:27:33 +0000 X-CR-MTA-TID: 64aa7808 Received: from f7fc0d51e803.2 by 64aa7808-outbound-1.mta.getcheckrecipient.com id BD4F86D6-7DDC-4E9B-99CE-E14249971725.1; Thu, 25 Jun 2020 04:27:27 +0000 Received: from EUR04-VI1-obe.outbound.protection.outlook.com by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id f7fc0d51e803.2 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384); Thu, 25 Jun 2020 04:27:27 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=Mfvm4YEdSArgNGgaqYmIGGRxsaIU1o6HAqQOOs4Hmi0kl/pez5NzIxuD4YTJ9hNKfWIDNbLOm+yTkJxpiVaIz9vbV//hfj1Jj5cXLbvOwmFlU0GYIWPMMZsHUBqCKQZlVdk0L15QQlS67FOWVyTCi4T5lVn8OcbmKEdjJr28e3gCpveczebumEFeJIizYxUmh77cs/mRuzJmP3B7YmLhC1Vv4oOkJ04lCp8ymhIb8Gn21rRdh9w6pNYOiblDJCypGNW2C98Pvk9cu4ZwpxryDbPipBN9vA5Pyc+hNbHRXETioFlgfFL1hJ9uDg+PPUjffgkuV9SpKYK5Fmg+TkAFqw== 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=nv3J0X1aCaF+nTQg2AB1oStkqzzirhJijqEzV7XNS6s=; b=eV3rqFZ3Z97pUoSpGUfgT2ikn3tReosZvQ9WLsbddtG5W5biH8I+KGXFthptqxL9yYMuf5qJ3xfEF3OyonZhCywOLi9sc9luSDP2q+fpKg+zcJXEaywDzd99qONzFCZ+SW5pAK5aB7afdorrTZL3DnYSKfaU6ce4Ptbe+AycQdUlxrTMONboWmKVAtC51IjwIVWtt4UdvTOQC1rMsclmj247+XsRB03LpdcST0VT0MmgAt2WhSFxzUID6xP7mjMzHM+UKxJGI2mTwMVF8gPqiTUFAqjm4seeZ5Gq49ovuNxG8QK9ZCsNvB9YEhKdl2OMKQuo81N6OqyhIjZIykAx9A== 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=nv3J0X1aCaF+nTQg2AB1oStkqzzirhJijqEzV7XNS6s=; b=faSCg+c/VJFz3jnOrL0HKVCUlu7whXhZBLWq0iZlIRcQq1Wp7ZP+GzXK9RgunZ0Cll/CI371dI4tfuFGoSjEjXgkVXWit/zXypIq1soJEoHBH753UdKhbpaIltjXVFy32nu5o39iZryUOWgZSPTjd0FuyFClF5VrtxRLpBcMbMQ= Received: from DB6PR0802MB2216.eurprd08.prod.outlook.com (2603:10a6:4:85::9) by DB6PR0802MB2501.eurprd08.prod.outlook.com (2603:10a6:4:a2::21) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3131.21; Thu, 25 Jun 2020 04:27:24 +0000 Received: from DB6PR0802MB2216.eurprd08.prod.outlook.com ([fe80::1128:b7e7:e832:310f]) by DB6PR0802MB2216.eurprd08.prod.outlook.com ([fe80::1128:b7e7:e832:310f%9]) with mapi id 15.20.3109.027; Thu, 25 Jun 2020 04:27:24 +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 v4 1/4] hash: add kv hash library Thread-Index: AQHWJXMkylb03/rR8kCSh4NTaVkvtKjoGykw Date: Thu, 25 Jun 2020 04:27:23 +0000 Message-ID: References: In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-ts-tracking-id: 68e4f18e-30fd-4bc4-a79c-392a3d0ec7b3.0 x-checkrecipientchecked: true 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: [107.77.221.106] x-ms-publictraffictype: Email X-MS-Office365-Filtering-HT: Tenant X-MS-Office365-Filtering-Correlation-Id: 6c384f4d-95cf-418e-de6f-08d818c014df x-ms-traffictypediagnostic: DB6PR0802MB2501:|AM6PR08MB5254: x-ms-exchange-transport-forked: True X-Microsoft-Antispam-PRVS: x-checkrecipientrouted: true nodisclaimer: true x-ms-oob-tlc-oobclassifiers: OLM:6430;OLM:6430; x-forefront-prvs: 0445A82F82 X-MS-Exchange-SenderADCheck: 1 X-Microsoft-Antispam-Untrusted: BCL:0; X-Microsoft-Antispam-Message-Info-Original: DtIabwxgti2FBN+caW0dzviw5Lv6GFAHXED8dn5p8Z/r5ohioA6fFgB0Hn/n+0s2wjBnY7VDYSRJuN+12G4LcjHCSWEEwR3qYP1CjTw6WQ5qlBmZ+pu21dch6ozl/OqrBog66snFxKeJyQaZqKCki5OsQps5jYrnuelXsDmPENRrNlcOtEJoPdN6TvzIo8ynuAOzlxcdniHYSZrpCGTov8f+4GTKdePhStUvxOFnGWuxKuoVzOecxzDlaAN5EluuUOGMz/lDgwCebZ0zGg9Cd3nBnhTLVG/a5Jrzf6u/lPMHh0xssjoA+wVhPT+NNVWihTAHpzqkMOhLOKrjQUjttw== X-Forefront-Antispam-Report-Untrusted: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:DB6PR0802MB2216.eurprd08.prod.outlook.com; PTR:; CAT:NONE; SFTY:; SFS:(4636009)(396003)(366004)(136003)(346002)(376002)(39860400002)(26005)(64756008)(33656002)(478600001)(66446008)(66476007)(7696005)(66556008)(186003)(66946007)(86362001)(8676002)(76116006)(5660300002)(53546011)(83380400001)(9686003)(316002)(71200400001)(2906002)(110136005)(6506007)(30864003)(4326008)(55016002)(8936002)(54906003)(52536014)(559001)(579004); DIR:OUT; SFP:1101; x-ms-exchange-antispam-messagedata: gmR6udr2V9M8oyJWEjW5hSUtMT0XXsggnKxXM5S+O2E4hlrRPQ4y12UfT5fsEXiZ8lF+qcknzrK+Rvauc7uWtOqGh0zv+Z8NoFpAuglLiz7xxR7YCiqF4dDLi20MDdYwv/CIuvo62zMR6amTXvBxt/9lql/300EyuoEQkJuB+0YyuQ8Y6Uojjt29UP3noUq56dbOs0OqFsPWzoBFr4ofRwPBMfsyQK+cZXQQ2S3W1/aR5JU8d+AzmlCWGEIpQ79YLdfvXLORcXxxpmEYvJIABwN+kgbFAaFYETp9lwzy7IP7Lh2V9LWciwqfabzNbqrG+XhEPnQS8RqdBU9LM7OQRfj7FRz44Y7uQdKM884VymzIBN6rvzdqtYf4y8V3aVfdsrGclrlbGVnTKt16pD0Tx9N/SXNTklu1x+6LebYhM2Jaq9vO8Fac/VZYohtfAeCSWTLmTWU4+sVJodE6GSJOVVQNGaXSncEU0KTGQJKsfzSRiPlVbvogbFbcFrIvCEGw Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB6PR0802MB2501 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: VE1EUR03FT014.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)(39860400002)(376002)(136003)(396003)(346002)(46966005)(316002)(30864003)(336012)(52536014)(54906003)(9686003)(81166007)(186003)(33656002)(82310400002)(53546011)(356005)(4326008)(110136005)(6506007)(47076004)(5660300002)(7696005)(478600001)(36906005)(82740400003)(8676002)(83380400001)(70206006)(70586007)(55016002)(86362001)(2906002)(8936002)(26005); DIR:OUT; SFP:1101; X-MS-Office365-Filtering-Correlation-Id-Prvs: 400e67fe-0e5a-490b-90c0-08d818c00f3a X-Forefront-PRVS: 0445A82F82 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: LlZnIw48j6fc3kjI0BqTRSh8fu5xAPgo0mEAtZV9saDh/DqoJCUcuHiI6BuCCq7z1AZR/uQGwc1n2qhvdOxyTAH273vhsUEXjya/UibHz30BR84h2lxDsLjWlzMIQ0Xj7dJeWhUQXPUEWROdQiCVtftszJ1KWQ3brIow8BIPwL99rFjtRYPrfdaVRAXRPe7HYWvffQ7kbD13AnPsJPCUo+eLAD52wGUmMnot1TFh0lCCppWKsHCBpa0yYewlEGD+BdLUEyejJtxCD6nc62G3EM/DksesDLKkgq0QB0LSVFxBx9YHZUw9OtL/0xbQyLue8JE/ia8+k493txoh0dzA1ArjdyrA38BSikIABmKSUric8HlLA2zC76/yV+zkqU5vPbNrNnpUDsV6v3wPD1j2+w== X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 25 Jun 2020 04:27:33.4379 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 6c384f4d-95cf-418e-de6f-08d818c014df 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: AM6PR08MB5254 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, Few comments inline. > -----Original Message----- > From: dev On Behalf Of Vladimir Medvedkin > Sent: Friday, May 8, 2020 2:59 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 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_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..a0cd= ee9 > 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 - &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); } Since, this is an inline function, would it be better to push this to the h= eader file? > + > +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; Suggest using C11 builtin to store value. As far as I know all the supporte= d platforms in DPDK have 64b atomic store in 32b mode. With this we will be able to avoid incrementing the counter. The reader wil= l either get old or the new 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; Same here. __atomic_store(&ent->val, value, __ATOMIC_RELAXED). > + __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++; Looks like bucket counter logic is needed for this case too. Please see the= comments below in k32v64_hash_delete. > + *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(); We need to avoid using rte_smp_* barriers as we are adopting C11 built-in a= tomics. See the below comment. > + 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); Both the inserts need to use release order when the 'ent' is inserted. I am= not sure where the SLIST is being picked up from. But looking at the SLIST= implementation in 'lib/librte_eal/windows/include/sys/queue.h', it is not = implemented using C11. I think we could move queue.h from windows directory= to a common directory and change the SLIST implementation. > + > + 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); (taking note from your responses to my comments in v3) It is possible that the reader might match the old key but get the new valu= e. 1) Reader: successful key match 2) Writer: k32v64_hash_delete followed by k32v64_hash_add 3) Reader: reads the value IMO, there are 2 ways to solve this issue: 1) Use the bucket count logic while adding an entry in the non-extended buc= ket (marked it in k32v64_hash_add). 2) Do not use the entry in the bucket till the readers indicate that they h= ave stopped using the entry > + 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); > + > + table->nb_ext_ent--; > + table->nb_ent--; > + > + return 0; > +} > + > +static int > +k32v64_modify(struct rte_kv_hash_table *table, void *key_p, uint32_t has= h, > + 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; > + } Suggest doing this check in rte_kv_hash_add/rte_kv_hash_delete. Then every = implementation does not have to do this. > + > + value =3D *(uint64_t *)value_p; In the API 'rte_kv_hash_add', value_p is 'void *' which does not convey tha= t it is a pointer to 64b data. What happens while running on 32b systems? > + 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; > + } > + > + return -EINVAL; > +} > + > +struct rte_kv_hash_table * > +k32v64_hash_create(const struct rte_kv_hash_params *params) { This is a private symbol, I think it needs to have '__rte' suffix? > + 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)) { > + rte_errno =3D EINVAL; > + return NULL; > + } nit, these checks were done already in 'rte_kv_hash_create', these checks c= an be skipped. > + > + 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; > + } Same here, this is checked in the calling function. > + > + max_ent =3D rte_align32pow2(params->entries); > + nb_buckets =3D max_ent / K32V64_KEYS_PER_BUCKET; > + 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(); > + ht->pub.modify =3D k32v64_modify; > + > + return (struct rte_kv_hash_table *)ht; } > + > +void > +k32v64_hash_free(struct rte_kv_hash_table *ht) { This is a private symbol, I think it needs to have '__rte' suffix? > + 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 */ > + 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) Changing __kv_cmp_keys to __k32v64_cmp_keys would be consistent > +{ > + 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; > + } > + } You have to load-acquire 'key_mask' (corresponding to store-release on 'key= _mask' in add). Suggest changing this as follows: __atomic_load(&bucket->key_mask, &key_mask, __ATOMIC_ACQUIRE); for (i =3D 0; i < K32V64_KEYS_PER_BUCKET; i++) { if ((key =3D=3D bucket->key[i]) && (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)); Agree that it is a small section. But the issue can happen. This also makes= the algorithm un-acceptable in many use cases. IMHO, since we have identif= ied the issue, we should fix it. The issue is mainly due to not following the reader-writer concurrency desi= gn principles. i.e. the data that we want to communicate from writer to rea= der (key and value in this case) is not being communicated atomically. For = ex: in rte_hash/cuckoo hash library, you can see that the key and pData are= being communicated atomically using the key store index. I might be wrong, but, I do not think we can make this block-free (readers = move forward even when the writer is not scheduled) using bucket counter. This problem does not exist in existing rte_hash library. It might not be p= erforming as good as this, but it is block-free. > + > + 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 > +#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) > + 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) { I did not see a test case for this. Please add a test case for 'rte_kv_hash= _find_existing'. > + 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); RTE_KV_HASH_NAMESIZE is a public #define. It is natural for the user to use= this to define the size of the hash table name. Now, we are taking 3 chara= cters from that space. I think it is better to increase the size of 'hash_n= ame' by 3 characters or skip adding 'KV_' to the name. This also has an impact on 'rte_kv_hash_find_existing' where the user passe= d string is being used as is without adding 'KV_'. Suggest adding a test ca= se for 'rte_kv_hash_find_existing'. > + 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(); I understand that the free is not thread safe. But, it might be safer if un= lock is after the call to 'k32v64_hash_free'. > + > + 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 > +}; This could be in a private header file. > + > +struct rte_kv_hash_params { > + const char *name; > + uint32_t entries; > + int socket_id; > + enum rte_kv_hash_type type; > +}; Since this is a public structure, suggest adding some reserved or flags fie= ld which are ignored now but could be used in the future for enhancements. > + > +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; There are separate APIs provided for add and delete. Is there any advantage= for combining add/delete into a single function pointer in the backend? If we keep 2 separate pointers, we can get rid of 'enum rte_kv_modify_op'. = It is simple to understand as well. > + enum rte_kv_hash_type type; > +}; > + > +/** > + * Lookup bulk of keys. > + * This function is multi-thread safe with regarding to other lookup thr= eads. It is safe with respect to the writer as well (reader-writer concurrency), = please capture this as well. > + * > + * @param table > + * Hash table to add the key to. nit, 'Hash table to lookup the keys' > + * @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= . > + */ > +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); } Consider making this a non-inline function. This is a bulk lookup and I thi= nk cost of calling a function should get amortized well. This will also allow for hiding the 'struct rte_kv_hash_table' from the use= r which is better for ABI. You can move the definition of the 'struct rte_k= v_hash_table' and function pointer declarations to a private header file. > + > +/** > + * 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. I think it needs to be called out here that it the data is of size 64b (eve= n in a 32b system) because of the implementation in function 'k32v64_modify= '. Why not make 'value' of type 'uint64_t *'? > + * @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. > + * > + * @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