From patchwork Thu Aug 16 07:30:06 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Fu, Qiaobin" X-Patchwork-Id: 43731 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id AE8F92C6A; Thu, 16 Aug 2018 09:30:09 +0200 (CEST) Received: from NAM05-DM3-obe.outbound.protection.outlook.com (mail-eopbgr730120.outbound.protection.outlook.com [40.107.73.120]) by dpdk.org (Postfix) with ESMTP id 4C41A2C58 for ; Thu, 16 Aug 2018 09:30:08 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bushare.onmicrosoft.com; s=selector1-bu-edu; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=Es8uurMK8RyUVHVA+kJE6alP20/Fxha0yUXQTvkwSR0=; b=m1BZBId0zQZprnW62wTU4jgAB6/moH+6ZxCUh4kp97FViyIroTwpeCd7HIDdhgQp1oiF6MzfkZ5kpt73xKY4jjRLazVc4KDnRptwaamiCIBQ/tND0pnqeHtKjsag3rGz6ZburcHDtyeRZPgCDktNrUftNqJzuKg47+W2Tu2epqY= Received: from MWHPR03MB3213.namprd03.prod.outlook.com (10.174.249.17) by MWHPR03MB3118.namprd03.prod.outlook.com (10.174.174.23) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1038.25; Thu, 16 Aug 2018 07:30:06 +0000 Received: from MWHPR03MB3213.namprd03.prod.outlook.com ([fe80::5826:9efc:eec7:3c52]) by MWHPR03MB3213.namprd03.prod.outlook.com ([fe80::5826:9efc:eec7:3c52%6]) with mapi id 15.20.1059.017; Thu, 16 Aug 2018 07:30:06 +0000 From: "Fu, Qiaobin" To: "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 , "Fu, Qiaobin" Thread-Topic: [PATCH v2] hash table: add an iterator over conflicting entries Thread-Index: AQHUNTL0vpyW83vm50Sk6UDivk6ygw== Date: Thu, 16 Aug 2018 07:30:06 +0000 Message-ID: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: authentication-results: spf=none (sender IP is ) smtp.mailfrom=qiaobinf@bu.edu; x-originating-ip: [67.180.169.0] x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1; MWHPR03MB3118; 6:bWGW0E2yBHAnuAjdFIXcE8eCRs/4215+vol5MpE03/MUjQlgNISMnUsFnvwaZ2ubiE3RipJVkeWxSh3wbiMGh1NcCW/LINiyauF3NgIet8IruDaG8Jkxd7cd5wDfgXmIuTuSRIoCkxM84LxeBnWGt6ZhmbpnhvplnXkoHmGzZk0N8C+B6u7S7xltrXR9amM64x9S0QgYz3CdXn2F7qYvbA3lAWPvcZXEfEV2KBYwvFiot+jiAeOKdRm2uXJkD0iWluEgo/SUMML/8+o+epV6zW7/c22lvkFcr2lB5mMEzNWltGmXGYjxnvT9nKxwAHE3mxgIZaY84/qqQ8pjVC+NryMbcX345IT5Iu7WohoYJ3FcyOcbApzHpYHg0Eryk+9e/rOch1Sjxs935AvqufiS5EY2eNMOMHP0z6buV+pAuWa2a6Siebrq8tE10XWYW217vnm0Er6qM+zPVsNVZC88pA==; 5:0w9kmcGNBUQvT6ZBj0ovrBMJp5olzwvMFTo0ZysFUjEkJH7PStHm69826hBpn+fj8Jlld8sxq5fU1XwPHBUbHBpPP10w/OXlDQpRHZbLRWPoyxJQdVrWWrFhanphoIu3o1KXDMJCCeFBGRDFvcw+lFtk7JJAGwFkkr2Y53cQnM0=; 7:DZvse3Mlp+uDCQnE3fJVIVByOkGwp9j6ngMq4lG1qLPW/weD3CLdgoFfN1UmFD00N0Rp+2UGBQXcftmu6O0fjFksKjfzWuf5Us9k/i1WJVLN68JFYiSIbg8ya5cN2AVHr4cSNSF5xl46gpS9VC+krwlBLiR7Xt3M6iys1Wse3E6nDgGhriCb1fR9XRe8MiMIhy6+xYwqdw+QbTXXbr71FSdYO6j7nd/cwdxC6jJtyo6mbsWvZRZ+UtXblyr03anM x-ms-exchange-antispam-srfa-diagnostics: SOS; x-ms-office365-filtering-correlation-id: f0ff8416-54af-4797-2791-08d6034a16a3 x-microsoft-antispam: BCL:0; PCL:0; RULEID:(7020095)(4652040)(8989137)(4534165)(4627221)(201703031133081)(201702281549075)(8990107)(5600074)(711020)(2017052603328)(7153060)(7193020); SRVR:MWHPR03MB3118; x-ms-traffictypediagnostic: MWHPR03MB3118: x-ld-processed: d57d32cc-c121-488f-b07b-dfe705680c71,ExtAddr 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)(3231311)(944501410)(52105095)(3002001)(93006095)(93001095)(10201501046)(149027)(150027)(6041310)(20161123558120)(20161123560045)(20161123564045)(20161123562045)(201703131423095)(201702281529075)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(201708071742011)(7699016); SRVR:MWHPR03MB3118; BCL:0; PCL:0; RULEID:; SRVR:MWHPR03MB3118; x-forefront-prvs: 07665BE9D1 x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(136003)(39860400002)(346002)(376002)(366004)(396003)(189003)(199004)(5250100002)(25786009)(486006)(4326008)(82746002)(81156014)(81166006)(83716003)(110136005)(75432002)(54906003)(786003)(316002)(7736002)(102836004)(256004)(53936002)(99286004)(6506007)(2900100001)(36756003)(305945005)(33656002)(66066001)(6436002)(476003)(106356001)(14444005)(478600001)(2616005)(26005)(14454004)(68736007)(6512007)(186003)(97736004)(86362001)(105586002)(2906002)(6486002)(8676002)(3846002)(88552002)(6116002)(5660300001)(8936002)(7756004); DIR:OUT; SFP:1102; SCL:1; SRVR:MWHPR03MB3118; H:MWHPR03MB3213.namprd03.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; MX:1; A:1; received-spf: None (protection.outlook.com: bu.edu does not designate permitted sender hosts) x-microsoft-antispam-message-info: j9rMb4XLyLciSqyp9hS4rnFToUuFVIbP9LYMeDkcJFgxwgmqbXE7s4SfJo8zqwQ6CEW4Mbr0S4FDAePmRl+DJcMDrA/5lViG8wgrCqNjof5nLHYN4JKznibqEC6G04M9QVqh/G98oZxP1PdudozH46PDyiSCtecmkDK6KRPq3m+g6Io3y/g4hAyiJljFHUwa5vqCgNdZHAgjkBsQ9OHpFrqv1VjzYEZMi9LfkECEw78m7FlJiCMxcqZFfdz22J5yuLIi9O18g8YrwYhp5L0tw6TFz76lvcxva0jkPWVfp2cwFj19RcbJ7HY3rR+KXnYdelrES9EMcksahmYPtj4bJyotDsBqRAIcO9Lot4/aJ18= spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-ID: <4E4882E1AC9D0446B4D8E01FCE781D65@namprd03.prod.outlook.com> MIME-Version: 1.0 X-OriginatorOrg: bu.edu X-MS-Exchange-CrossTenant-Network-Message-Id: f0ff8416-54af-4797-2791-08d6034a16a3 X-MS-Exchange-CrossTenant-originalarrivaltime: 16 Aug 2018 07:30:06.1248 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: d57d32cc-c121-488f-b07b-dfe705680c71 X-MS-Exchange-Transport-CrossTenantHeadersStamped: MWHPR03MB3118 Subject: [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: , Errors-To: dev-bounces@dpdk.org Sender: "dev" 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 entry is more valuable than the entries already in the hash table. This is particularly 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 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 = { }; EAL_REGISTER_TAILQ(rte_hash_tailq) +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_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32 return position - 1; } + +/* Get the primary bucket index given the precomputed hash value. */ +static inline uint32_t +rte_hash_get_primary_bucket(const struct rte_hash *h, hash_sig_t sig) +{ + return sig & h->bucket_bitmask; +} + +/* Get the secondary bucket index given the precomputed hash value. */ +static inline uint32_t +rte_hash_get_secondary_bucket(const struct rte_hash *h, hash_sig_t sig) +{ + return rte_hash_secondary_hash(sig) & h->bucket_bitmask; +} + +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 == NULL) || (state == NULL)), -EINVAL); + + __state = (struct rte_hash_iterator_conflict_entries_state *)state; + __state->h = h; + __state->vnext = 0; + __state->primary_bidx = rte_hash_get_primary_bucket(h, sig); + __state->secondary_bidx = rte_hash_get_secondary_bucket(h, sig); + + return 0; +} + +int32_t __rte_experimental +rte_hash_iterate_conflict_entries(struct rte_conflict_iterator_state *state, + const void **key, const void **data) +{ + struct rte_hash_iterator_conflict_entries_state *__state; + + RETURN_IF_TRUE(((state == NULL) || (key == NULL) || + (data == NULL)), -EINVAL); + + __state = (struct rte_hash_iterator_conflict_entries_state *)state; + + while (__state->vnext < RTE_HASH_BUCKET_ENTRIES * 2) { + uint32_t bidx = (__state->vnext < RTE_HASH_BUCKET_ENTRIES) ? + __state->primary_bidx : __state->secondary_bidx; + uint32_t next = __state->vnext & (RTE_HASH_BUCKET_ENTRIES - 1); + uint32_t position = __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 == EMPTY_SLOT)) + goto next; + + /* Get the entry in key table. */ + next_key = (struct rte_hash_key *) ( + (char *)__state->h->key_store + + position * __state->h->key_entry_size); + /* Return key and data. */ + *key = next_key->key; + *data = next_key->pdata; + +next: + /* Increment iterator. */ + __state->vnext++; + + if (likely(position != EMPTY_SLOT)) + return position - 1; + } + + return -ENOENT; +} 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; +/** @internal A hash table conflict iterator state structure. */ +struct rte_conflict_iterator_state { + uint8_t space[64]; +}; + /** * Create a new hash table. * @@ -419,6 +424,42 @@ rte_hash_lookup_bulk(const struct rte_hash *h, const void **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 *state, + const void **key, const void **data); + #ifdef __cplusplus } #endif diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_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; } DPDK_2.2; + +EXPERIMENTAL { + global: + + rte_hash_iterator_conflict_entries_init; + rte_hash_iterate_conflict_entries; +};