From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR03-AM5-obe.outbound.protection.outlook.com (mail-eopbgr30047.outbound.protection.outlook.com [40.107.3.47]) by dpdk.org (Postfix) with ESMTP id AE7FE374E for ; Fri, 17 Aug 2018 04:33:38 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector1-arm-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=To4tc5BDGfK+++fq8oJLHiYZFbFpWhT1BHY9FX+AbFA=; b=baswM/8FmfFwK7MaCbAj/F+I1R/EG/SVaHAEwHJ80D6b55AU0ZJc3FQHZ3h/AUtXnaZsuF1WDR52TxYqJrjShEPP8xorlUFxtEslkvqLMEm/orkTCAR4xBGrdN9Aqsr9OmFv3Paswe/qb/s2iYuBUlbKH65tuB9rNgwLNrPXtyw= Received: from AM6PR08MB3672.eurprd08.prod.outlook.com (20.177.115.29) by AM6PR08MB3461.eurprd08.prod.outlook.com (20.177.113.22) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1038.23; Fri, 17 Aug 2018 02:33:37 +0000 Received: from AM6PR08MB3672.eurprd08.prod.outlook.com ([fe80::649b:b10d:ef69:7fd2]) by AM6PR08MB3672.eurprd08.prod.outlook.com ([fe80::649b:b10d:ef69:7fd2%3]) with mapi id 15.20.1038.025; Fri, 17 Aug 2018 02:33:37 +0000 From: Honnappa Nagarahalli To: "Fu, Qiaobin" , "Richardson, Bruce" , "De Lara Guarch, Pablo" CC: "dev@dpdk.org" , Michel Machado , "Doucette, Cody, Joseph" , "Wang, Yipeng1" , "Wiles, Keith" , "Gobriel, Sameh" , "Tai, Charlie" , Stephen Hemminger , nd Thread-Topic: [dpdk-dev] [PATCH v2] hash table: add an iterator over conflicting entries Thread-Index: AQHUNTL0vpyW83vm50Sk6UDivk6yg6TDIttg Date: Fri, 17 Aug 2018 02:33:36 +0000 Message-ID: References: In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [217.140.111.135] x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1; AM6PR08MB3461; 6:1e9T3zA8qus977O3ybAt2Diqpp/1uutwneyFdTc3du/u4zna4EwxcGAPoo64udrqnNWB6+WtUOVVF6ocfSppt0bsG/XG+tr0mojUXNisTO1UmTLqJWFgoL4oPsNQ2QyF3pLkBo98oTkBViXBn3FtRAftUKxxGC8WKGw2NnFuJY273f7SmimH+N7LbBEG5ugFQ1a4j9djAQP821LlT6ArwksJL428B/dvR95lTnFZhtM3KHs3aaHIlIw8yK933IiHmYtBEs3EwDBfs5UPPzXZFrOusywuBVfISlvLfcDFBzMO73C+6MKGRYUt1Nr6PNzmZiIUW4TCv/SVqS88jh3ldEjeq/ql4QYSjvSyWfyBvZzUeuyGtVIfRKaOHNe+o9FFLyURtLN4g9kqz3V5xg85dz3wk9hHcGY+3scNQ6GnuHTVVTnWN0/69+RzyaOcmzQwyVguVj0pXimvJmisC9alKQ==; 5:lJuwXlwBW3e6e38H6mL4akt/rJYUVGs9SoI8zXPef0db7sI6RYI6/8PPewGwRCyXob9ORuXyuifA0fljQVUlawUFOdBfcJjdxD1m5ZNj+74fMSJhicliTzS8scDAA0lJwRhM11ReijWu4AJCfZ4DyRv807j7XWqURr3qm9u78Yc=; 7:vYZIcMEMW70ibAf6qOLuVyK9OHmapDjyqlcnGB21A8jXnjd1/3+xUW9lGoNDve9A+3muUoADTL+B8K6nBBqZqQ+rjULj1QotnF1L8qmJN9KhlczaYkK1JulJS8kgyqvkppVF7V2bcFc0P4FjiD/e2ckO9TBvzgi8jvpNC9+WhVPPkn2ScIqOKa51qsOoY3gulgOOrnirh/c7T94Yf8Gwki1GJOw7SGbP4KAVU8CygPzJl27zEdK7KwCYNvY2n+cF x-ms-exchange-antispam-srfa-diagnostics: SOS; x-ms-office365-filtering-correlation-id: 628a3ebc-210f-4787-a5cd-08d603e9d5e2 x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: BCL:0; PCL:0; RULEID:(7020095)(4652040)(8989137)(4534165)(4627221)(201703031133081)(201702281549075)(8990107)(5600074)(711020)(4618075)(2017052603328)(7153060)(7193020); SRVR:AM6PR08MB3461; x-ms-traffictypediagnostic: AM6PR08MB3461: authentication-results: spf=none (sender IP is ) smtp.mailfrom=Honnappa.Nagarahalli@arm.com; nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(238701278423138)(166494164430575)(228905959029699); x-ms-exchange-senderadcheck: 1 x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(5005006)(8121501046)(823301054)(3231311)(944501410)(52105095)(93006095)(93001095)(10201501046)(3002001)(6055026)(149027)(150027)(6041310)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123562045)(20161123560045)(20161123558120)(20161123564045)(201708071742011)(7699016); SRVR:AM6PR08MB3461; BCL:0; PCL:0; RULEID:; SRVR:AM6PR08MB3461; x-forefront-prvs: 076777155F x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(346002)(376002)(366004)(39860400002)(136003)(396003)(13464003)(199004)(189003)(14454004)(54906003)(256004)(7416002)(110136005)(316002)(2906002)(97736004)(14444005)(6116002)(3846002)(53936002)(9686003)(5660300001)(4326008)(486006)(478600001)(66066001)(68736007)(72206003)(2171002)(55016002)(25786009)(6246003)(476003)(53546011)(6506007)(345774005)(105586002)(81156014)(81166006)(7696005)(86362001)(74316002)(8936002)(6436002)(229853002)(76176011)(11346002)(26005)(446003)(186003)(7736002)(33656002)(106356001)(2900100001)(102836004)(5250100002)(305945005)(99286004); DIR:OUT; SFP:1101; SCL:1; SRVR:AM6PR08MB3461; H:AM6PR08MB3672.eurprd08.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:1; MX:1; received-spf: None (protection.outlook.com: arm.com does not designate permitted sender hosts) x-microsoft-antispam-message-info: ruzs0Artab7PREymCi9agaPNpPdzEHHotYZkO3MUn7atETZ4WjASLc0NTMTsC4HMatShWCTcZON/h/+uWWmPLU+g+D9HovLP52c7v4CIGKRQ+KZgU1dWVB/9liRpjemmXMIM3npTWc6dV/lvf1PsEY/zCw8WJWYfnPjHevy/yrskyuLzz8DtRXqTRl5Y98hoYgJNSl7fHduWY6qGDPAA4pQ2O65UiK3jAsX99IoKFNq20jcrOGaVXEA4uQvkHso1PFd7rPnJLQbe2kJ8JwuuNLLdnvUdoYw+ozCA/qAkNZW7WQuOTi503fUuHHhbKbNPPV8FincIxLIKD6FwVmg9eyGi3cxpLgOqrq+X32YfTEY= spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-Network-Message-Id: 628a3ebc-210f-4787-a5cd-08d603e9d5e2 X-MS-Exchange-CrossTenant-originalarrivaltime: 17 Aug 2018 02:33:36.9386 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR08MB3461 Subject: Re: [dpdk-dev] [PATCH v2] hash table: add an iterator over conflicting entries 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: , X-List-Received-Date: Fri, 17 Aug 2018 02:33:39 -0000 Hi Fu, Thank you for the patch. I have few comments below. Thank you, Honnappa -----Original Message----- From: dev On Behalf Of Fu, Qiaobin Sent: Thursday, August 16, 2018 2:30 AM To: Richardson, Bruce ; De Lara Guarch, Pablo <= pablo.de.lara.guarch@intel.com> Cc: dev@dpdk.org; Michel Machado ; Doucette, Cody, = Joseph ; Wang, Yipeng1 ; Wiles, Ke= ith ; Gobriel, Sameh ; Tai,= Charlie ; Stephen Hemminger ; Fu, Qiaobin Subject: [dpdk-dev] [PATCH v2] hash table: add an iterator over conflicting= entries Function rte_hash_iterate_conflict_entries() iterates over the entries that= conflict with an incoming entry. Iterating over conflicting entries enables one to decide if the incoming en= try is more valuable than the entries already in the hash table. This is pa= rticularly useful after an insertion failure. v2: * Fix the style issue * Make the API more universal Signed-off-by: Qiaobin Fu Reviewed-by: Cody Doucette Reviewed-by: Michel Machado Reviewed-by: Keith Wiles Reviewed-by: Yipeng Wang --- lib/librte_hash/rte_cuckoo_hash.c | 81 ++++++++++++++++++++++++++++ lib/librte_hash/rte_hash.h | 41 ++++++++++++++ lib/librte_hash/rte_hash_version.map | 7 +++ 3 files changed, 129 insertions(+) diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo= _hash.c index a07543a29..de69f9966 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -42,6 +42,13 @@ static struct rte_tailq_elem rte_hash_tailq =3D { }; EAL_REGISTER_TAILQ(rte_hash_tailq) =20 +struct rte_hash_iterator_conflict_entries_state { + const struct rte_hash *h; + uint32_t vnext; + uint32_t primary_bidx; + uint32_t secondary_bidx; +}; + struct rte_hash * rte_hash_find_existing(const char *name) { @@ -1160,3 +1167,77 @@ rte_has= h_iterate(const struct rte_hash *h, const void **key, void **data, uint32 =20 return position - 1; } + +/* Get the primary bucket index given the precomputed hash value. */=20 +static inline uint32_t rte_hash_get_primary_bucket(const struct=20 +rte_hash *h, hash_sig_t sig) { + return sig & h->bucket_bitmask; +} + +/* Get the secondary bucket index given the precomputed hash value. */=20 +static inline uint32_t rte_hash_get_secondary_bucket(const struct=20 +rte_hash *h, hash_sig_t sig) { + return rte_hash_secondary_hash(sig) & h->bucket_bitmask; } + IMO, to keep the code consistent, we do not need to have the above 2 functi= ons. +int32_t __rte_experimental +rte_hash_iterator_conflict_entries_init(const struct rte_hash *h, + hash_sig_t sig, struct rte_conflict_iterator_state *state) { + struct rte_hash_iterator_conflict_entries_state *__state; + + RETURN_IF_TRUE(((h =3D=3D NULL) || (state =3D=3D NULL)), -EINVAL); + + __state =3D (struct rte_hash_iterator_conflict_entries_state *)state; + __state->h =3D h; + __state->vnext =3D 0; + __state->primary_bidx =3D rte_hash_get_primary_bucket(h, sig); + __state->secondary_bidx =3D rte_hash_get_secondary_bucket(h, sig); + + return 0; +} + +int32_t __rte_experimental +rte_hash_iterate_conflict_entries(struct rte_conflict_iterator_state *stat= e, + const void **key, const void **data) +{ + struct rte_hash_iterator_conflict_entries_state *__state; + + RETURN_IF_TRUE(((state =3D=3D NULL) || (key =3D=3D NULL) || + (data =3D=3D NULL)), -EINVAL); + + __state =3D (struct rte_hash_iterator_conflict_entries_state *)state; + + while (__state->vnext < RTE_HASH_BUCKET_ENTRIES * 2) { + uint32_t bidx =3D (__state->vnext < RTE_HASH_BUCKET_ENTRIES) ? + __state->primary_bidx : __state->secondary_bidx; + uint32_t next =3D __state->vnext & (RTE_HASH_BUCKET_ENTRIES - 1); + uint32_t position =3D __state->h->buckets[bidx].key_idx[next]; + struct rte_hash_key *next_key; + /* + * The test below is unlikely because this iterator is meant + * to be used after a failed insert. + * */ + if (unlikely(position =3D=3D EMPTY_SLOT)) + goto next; + + /* Get the entry in key table. */ + next_key =3D (struct rte_hash_key *) ( + (char *)__state->h->key_store + + position * __state->h->key_entry_size); + /* Return key and data. */ + *key =3D next_key->key; + *data =3D next_key->pdata; + +next: + /* Increment iterator. */ + __state->vnext++; + + if (likely(position !=3D EMPTY_SLOT)) + return position - 1; + } + + return -ENOENT; +} I think, we can make this API similar to 'rte_hash_iterate'. I suggest the = following API signature: int32_t rte_hash_iterate_conflict_entries (const struct rte_hash *h, const void **k= ey, void **data, hash_sig_t sig, uint32_t *next) primary and secondary bucket indices can be calculated from 'sig', 'next' i= s the iterator for the entries in the bucket (or conflicted entries). 'next= ' can go across the primary and secondary buckets. This will avoid creating= 'rte_hash_iterator_conflict_entries_init' API. I also suggest to change the API name to ' rte_hash_iterate_bucket_entries'= - 'bucket' is a well understood term in the context of hash algorithms. Do we also need to have 'rte_hash_iterate_conflict_entries_with_hash' API? diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h index = f71ca9fbf..7ecb6a7eb 100644 --- a/lib/librte_hash/rte_hash.h +++ b/lib/librte_hash/rte_hash.h @@ -61,6 +61,11 @@ struct rte_hash_parameters { /** @internal A hash table structure. */ struct rte_hash; =20 +/** @internal A hash table conflict iterator state structure. */ struct=20 +rte_conflict_iterator_state { + uint8_t space[64]; +}; + The size depends on the current size of the state, which is subject to chan= ge with the algorithm used. /** * Create a new hash table. * @@ -419,6 +424,42 @@ rte_hash_lookup_bulk(const struct rte_hash *h, const v= oid **keys, */ int32_t rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, = uint32_t *next); + +/** + * Initialize the iterator over entries that conflict with a new entry. + * + * @param h + * Hash table to iterate + * @param sig + * Precomputed hash value for the new entry. + * @return + * - 0 if successful. + * - -EINVAL if the parameters are invalid. + */ +int32_t __rte_experimental +rte_hash_iterator_conflict_entries_init(const struct rte_hash *h, + hash_sig_t sig, struct rte_conflict_iterator_state *state); + +/** + * Iterate over entries that conflict with a new entry. + * + * @param state + * Pointer to the iterator state. + * @param key + * Output containing the key where current iterator + * was pointing at. + * @param data + * Output containing the data associated with key. + * Returns NULL if data was not stored. + * @return + * Position where key was stored, if successful. + * - -EINVAL if the parameters are invalid. + * - -ENOENT if there is no more conflicting entries. + */ +int32_t __rte_experimental +rte_hash_iterate_conflict_entries(struct rte_conflict_iterator_state *stat= e, + const void **key, const void **data); + #ifdef __cplusplus } #endif diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_has= h_version.map index 52a2576f9..c1c343e52 100644 --- a/lib/librte_hash/rte_hash_version.map +++ b/lib/librte_hash/rte_hash_version.map @@ -45,3 +45,10 @@ DPDK_16.07 { rte_hash_get_key_with_position; =20 } DPDK_2.2; + +EXPERIMENTAL { + global: + + rte_hash_iterator_conflict_entries_init; + rte_hash_iterate_conflict_entries; +}; -- 2.17.1