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 EB33CA0597; Thu, 9 Apr 2020 01:23:11 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id E2F991C1EE; Thu, 9 Apr 2020 01:23:10 +0200 (CEST) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id AFC501C1EC for ; Thu, 9 Apr 2020 01:23:09 +0200 (CEST) IronPort-SDR: n9/7sD12H6868KxFgKj+RvJh0XGCB6NDTYiiitMBvrdkVSOIPxim5GTHKeO8NYujjwHgaiCTKY uiOxuAyvX8Ww== X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga004.jf.intel.com ([10.7.209.38]) by orsmga102.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 08 Apr 2020 16:23:08 -0700 IronPort-SDR: /njWRqWecSVtkYVR7ICrES6M9a/GBd03TX9RqTzWfGjCoK341BbYcW5SzgDyd7GulTMPpgTHog e2xCMZp/5M8A== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.72,360,1580803200"; d="scan'208";a="398363546" Received: from orsmsx105.amr.corp.intel.com ([10.22.225.132]) by orsmga004.jf.intel.com with ESMTP; 08 Apr 2020 16:23:08 -0700 Received: from orsmsx151.amr.corp.intel.com (10.22.226.38) by ORSMSX105.amr.corp.intel.com (10.22.225.132) with Microsoft SMTP Server (TLS) id 14.3.439.0; Wed, 8 Apr 2020 16:23:07 -0700 Received: from ORSEDG002.ED.cps.intel.com (10.7.248.5) by ORSMSX151.amr.corp.intel.com (10.22.226.38) with Microsoft SMTP Server (TLS) id 14.3.439.0; Wed, 8 Apr 2020 16:23:07 -0700 Received: from NAM11-DM6-obe.outbound.protection.outlook.com (104.47.57.172) by edgegateway.intel.com (134.134.137.101) with Microsoft SMTP Server (TLS) id 14.3.439.0; Wed, 8 Apr 2020 16:23:07 -0700 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=LftiL4rhPBF9mnEHGlt6qYBxyhPlytmpeICpjXURtMi+pZpCi0/2JKcpgIdsyzoBkuKHpifdRUmaiN+NWMJQL5ClnP8lWCnSACwbBdiAhUJOO9jwvmezUfAgHNqWdJ8rnzrB2ZSXExh5e8u8pQA6rjx9AD5Rhag/Spfl4pUuq/tnNZ2NT2aBo5+WA2F9KAlbpe/oiEmq/V6/w6lOw/hjf+KVxz1KjDTPGxwfgff7rROZBXutpSaCVMqEI2ZPQAha6JE05YEi4KvI7aQQySTssdQH0Lq+mlDnPCgO6M9OtxH0K+Qn7pZ1CC7hi0EWlm/U9acZ/0BfhKJ2jqgB01pIXg== 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=1a1gZlP/FuQSKs0W8EaV4rTRM55DSY6H/DMh1wy6FAA=; b=W13hNLdHO8uG9H60/ZqbS2YXKBvonJGuG72CCIaLYaxx36BUZ15+0ywtQwkinUzB+CX81xX4e28nU85+NqtNYU2KI9JLKe2PJcC1+qwqPW9SE8s54jriRd3/KvdCCPSbs3R+cw4vhYMXlhALQOyvUqZ34hZa8E6xzZgCFjLnqDB79c+P5h0T+cK2vEEIiGExNwq163PAc/7xgD4+BhmNTIffDV3hR/T60p0DvyMZbXjcr5GS3IKdbVyp6wH1F7AlGoYYHGa9Bipf1GuXz9RI10AyKdsniWQhHB9xYwYfTtA9VEjT1zZHIxww8nfsrI+mkAdP9u1G8Ckp8Si45YYEKQ== 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=1a1gZlP/FuQSKs0W8EaV4rTRM55DSY6H/DMh1wy6FAA=; b=Nv08RcKHj/C6wXOZaroAnRaFZHJmYJMZ5uwr8ppMgB29OJ/Ut814gC2YfXAtE4CpOCKd3HAAVhYH0K0jc/hx0eOM3hGnow0AeTwMaCx/uw/ZFk98oBhikb9+mviqtMPrMAdZwAmxnyYevT3OL2c5qYvpIY3K4TBwsYcbx+pKdyI= Received: from SN6PR11MB2558.namprd11.prod.outlook.com (2603:10b6:805:5d::19) by SN6PR11MB2960.namprd11.prod.outlook.com (2603:10b6:805:d4::12) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2878.21; Wed, 8 Apr 2020 23:23:04 +0000 Received: from SN6PR11MB2558.namprd11.prod.outlook.com ([fe80::3982:ee47:b95a:4ed4]) by SN6PR11MB2558.namprd11.prod.outlook.com ([fe80::3982:ee47:b95a:4ed4%3]) with mapi id 15.20.2900.015; Wed, 8 Apr 2020 23:23:04 +0000 From: "Ananyev, Konstantin" To: "Medvedkin, Vladimir" , "dev@dpdk.org" CC: "Wang, Yipeng1" , "Gobriel, Sameh" , "Richardson, Bruce" Thread-Topic: [PATCH v2 1/4] hash: add k32v64 hash library Thread-Index: AQHWDdJwOZomp1W24EeU0a8xZa7E+6hv2n8A Date: Wed, 8 Apr 2020 23:23:04 +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: spf=none (sender IP is ) smtp.mailfrom=konstantin.ananyev@intel.com; x-originating-ip: [192.198.151.164] x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: 45996d98-bd8c-4987-4a55-08d7dc13ca0c x-ms-traffictypediagnostic: SN6PR11MB2960: 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:8273; x-forefront-prvs: 0367A50BB1 x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:SN6PR11MB2558.namprd11.prod.outlook.com; PTR:; CAT:NONE; SFTY:; SFS:(10019020)(39860400002)(136003)(366004)(346002)(396003)(376002)(66556008)(2906002)(54906003)(8676002)(66476007)(4326008)(5660300002)(66446008)(64756008)(26005)(66946007)(81156014)(52536014)(186003)(86362001)(9686003)(33656002)(316002)(71200400001)(55016002)(107886003)(7696005)(76116006)(478600001)(81166007)(110136005)(6506007)(8936002); DIR:OUT; SFP:1102; x-ms-exchange-senderadcheck: 1 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: iN8xX+AFf7EYjlnWPF10G7U0/NC94HZ0QW/V6He3ENcGJwHZxwBwOR5gBhYNDqSD3BgNNh2/lh3WTXzuSh5ShnJUB/h85ZrxeZs2u7WQGTNCm6NXZsj9iD585/Qwbrt0ND+AemTF8z6HEq4s1fEHaPVKcSS5RhNO1he5Ezn18CvOgIRQqnXM4WebQMxeaBqmNUjVB/pWoRk8pdnXKyBj1+SGefKbPJaG2bdk98EvyBw/plZaY/9iZx6tbLNT/FZQX/zhM/ywD+u7SrwceAncIgbL3dNfP0ZwB3Mwje7JZJEBTeHkNwD8RCtsv5QvclGyLNGKnSG8QDKU7CmYlMzMYWH7abHa3p9KW22HZnkEVUkQdF0iJGtKdrwZ9rP4fH3TR7mtsJEkPdXt5DoT+wkq3DV9FQ0k78AYYQOI1mNsUu/obnnQ+MX4cOnf3E+a0KAg x-ms-exchange-antispam-messagedata: 2+p9a8ic31XY6rtWlifgb9r5L09MUy3+51ie+FhgSmFxbHm+IUayhkYrUugf212DtVBrg8s3MrELMOhZi4JFUeCjGH5HBHd58o8OycsHyhTxFTnyFuNonrnOCJcvzFVwmPKMvQpAAwFV2odqXqVeAA== Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-MS-Exchange-CrossTenant-Network-Message-Id: 45996d98-bd8c-4987-4a55-08d7dc13ca0c X-MS-Exchange-CrossTenant-originalarrivaltime: 08 Apr 2020 23:23:04.4429 (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: qXeSi6QZLnxreAGPlOndQ43JjaydMuLW1gBsDNoE+aV+SWYu2b2fGayFlk7u/qdpr4GEnvqBNCSjcS4CgyFz5enaZCjk3+LAukv4bXk2zm4= X-MS-Exchange-Transport-CrossTenantHeadersStamped: SN6PR11MB2960 X-OriginatorOrg: intel.com Subject: Re: [dpdk-dev] [PATCH v2 1/4] hash: add k32v64 hash library X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Hi Vladimir, I didn't look at actual implementation (yet), just some compatibility comments. =20 > K32V64 hash is a hash table that supports 32 bit keys and 64 bit values. > This table is hash function agnostic so user must provide > precalculated hash signature for add/delete/lookup operations. >=20 > Signed-off-by: Vladimir Medvedkin > --- > diff --git a/lib/librte_hash/rte_k32v64_hash.h b/lib/librte_hash/rte_k32v= 64_hash.h > new file mode 100644 > index 0000000..d25660c > --- /dev/null > +++ b/lib/librte_hash/rte_k32v64_hash.h > @@ -0,0 +1,214 @@ > +/* SPDX-License-Identifier: BSD-3-Clause > + * Copyright(c) 2020 Intel Corporation > + */ > + > +#ifndef _RTE_K32V64_HASH_H_ > +#define _RTE_K32V64_HASH_H_ > + > +#ifdef __cplusplus > +extern "C" { > +#endif > + > +#include > +#include > +#include > + > +#include How that supposed to compile on non-X86 box? > + > +#define RTE_K32V64_HASH_NAMESIZE 32 > +#define RTE_K32V64_KEYS_PER_BUCKET 4 > +#define RTE_K32V64_WRITE_IN_PROGRESS 1 > + > +struct rte_k32v64_hash_params { > + const char *name; > + uint32_t entries; > + int socket_id; > +}; > + > +struct rte_k32v64_ext_ent { > + SLIST_ENTRY(rte_k32v64_ext_ent) next; > + uint32_t key; > + uint64_t val; > +}; > + > +struct rte_k32v64_hash_bucket { > + uint32_t key[RTE_K32V64_KEYS_PER_BUCKET]; > + uint64_t val[RTE_K32V64_KEYS_PER_BUCKET]; > + uint8_t key_mask; > + rte_atomic32_t cnt; > + SLIST_HEAD(rte_k32v64_list_head, rte_k32v64_ext_ent) head; > +} __rte_cache_aligned; > + > +struct rte_k32v64_hash_table { > + char name[RTE_K32V64_HASH_NAMESIZE]; /**< Name of the hash. */ > + uint32_t nb_ent; > + uint32_t nb_ext_ent; > + uint32_t max_ent; > + uint32_t bucket_msk; > + struct rte_mempool *ext_ent_pool; > + __extension__ struct rte_k32v64_hash_bucket t[0]; > +}; > + > +static inline int > +cmp_keys(struct rte_k32v64_hash_bucket *bucket, uint32_t key, > + uint64_t *val) > +{ > + int i; > + > + for (i =3D 0; i < RTE_K32V64_KEYS_PER_BUCKET; i++) { > + if ((key =3D=3D bucket->key[i]) && > + (bucket->key_mask & (1 << i))) { > + *val =3D bucket->val[i]; > + return 1; > + } > + } > + > + return 0; > +} > + > +#ifdef __AVX512VL__ > +static inline int > +cmp_keys_vec(struct rte_k32v64_hash_bucket *bucket, uint32_t key, > + uint64_t *val) > +{ > + __m128i keys, srch_key; > + __mmask8 msk; > + > + keys =3D _mm_load_si128((void *)bucket); > + srch_key =3D _mm_set1_epi32(key); > + > + msk =3D _mm_mask_cmpeq_epi32_mask(bucket->key_mask, keys, srch_key); What if you'll run it on IA cpu without avx512 support? Think you need there some run-time selection to decide which function to us= e, depending on the underlying HW. > + if (msk) { > + *val =3D bucket->val[__builtin_ctz(msk)]; > + return 1; > + } > + > + return 0; > +} > +#endif > + > +static inline int > +rte_k32v64_hash_lookup(struct rte_k32v64_hash_table *table, uint32_t key= , > + uint32_t hash, uint64_t *value) > +{ > + uint64_t val =3D 0; > + struct rte_k32v64_ext_ent *ent; > + int32_t cnt; > + int i __rte_unused, found =3D 0; > + uint32_t bucket =3D hash & table->bucket_msk; > + > + do { > + do > + cnt =3D rte_atomic32_read(&table->t[bucket].cnt); > + while (unlikely(cnt & RTE_K32V64_WRITE_IN_PROGRESS)); > + > +#ifdef __AVX512VL__ > + found =3D cmp_keys_vec(&table->t[bucket], key, &val); > +#else > + found =3D cmp_keys(&table->t[bucket], key, &val); > +#endif > + if (unlikely((found =3D=3D 0) && > + (!SLIST_EMPTY(&table->t[bucket].head)))) { > + SLIST_FOREACH(ent, &table->t[bucket].head, next) { > + if (ent->key =3D=3D key) { > + val =3D ent->val; > + found =3D 1; > + break; > + } > + } > + } > + > + } while (unlikely(cnt !=3D rte_atomic32_read(&table->t[bucket].cnt))); > + > + if (found =3D=3D 1) { > + *value =3D val; > + return 0; > + } else > + return -ENOENT; > +} > + > +/** > + * Add a key to an existing hash table with hash value. > + * This operation is not multi-thread safe > + * and should only be called from one thread. > + * > + * @param ht > + * Hash table to add the key to. > + * @param key > + * Key to add to the hash table. > + * @param value > + * Value to associate with key. > + * @param hash > + * Hash value associated with key. > + * @return > + * 0 if ok, or negative value on error. > + */ > +__rte_experimental > +int > +rte_k32v64_hash_add(struct rte_k32v64_hash_table *table, uint32_t key, > + uint32_t hash, uint64_t value); > + > +/** > + * Remove a key with a given hash value from an existing hash table. > + * This operation is not multi-thread > + * safe and should only be called from one thread. > + * > + * @param ht > + * Hash table to remove the key from. > + * @param key > + * Key to remove from the hash table. > + * @param hash > + * hash value associated with key. > + * @return > + * 0 if ok, or negative value on error. > + */ > +__rte_experimental > +int > +rte_k32v64_hash_delete(struct rte_k32v64_hash_table *table, uint32_t key= , > + uint32_t hash); > + > + > +/** > + * Performs a lookup for an existing hash table, and returns a pointer t= o > + * the table if found. > + * > + * @param name > + * Name of the hash table to find > + * > + * @return > + * pointer to hash table structure or NULL on error with rte_errno > + * set appropriately. > + */ > +__rte_experimental > +struct rte_k32v64_hash_table * > +rte_k32v64_hash_find_existing(const char *name); > + > +/** > + * Create a new hash table for use with four byte keys. > + * > + * @param params > + * Parameters used in creation of hash table. > + * > + * @return > + * Pointer to hash table structure that is used in future hash table > + * operations, or NULL on error with rte_errno set appropriately. > + */ > +__rte_experimental > +struct rte_k32v64_hash_table * > +rte_k32v64_hash_create(const struct rte_k32v64_hash_params *params); > + > +/** > + * Free all memory used by a hash table. > + * > + * @param table > + * Hash table to deallocate. > + */ > +__rte_experimental > +void > +rte_k32v64_hash_free(struct rte_k32v64_hash_table *table); > + > +#ifdef __cplusplus > +} > +#endif > + > +#endif /* _RTE_K32V64_HASH_H_ */ > -- > 2.7.4