Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/55378/?format=api
{ "id": 55378, "url": "http://patches.dpdk.org/api/patches/55378/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/patch/20190625211520.43181-3-honnappa.nagarahalli@arm.com/", "project": { "id": 1, "url": "http://patches.dpdk.org/api/projects/1/?format=api", "name": "DPDK", "link_name": "dpdk", "list_id": "dev.dpdk.org", "list_email": "dev@dpdk.org", "web_url": "http://core.dpdk.org", "scm_url": "git://dpdk.org/dpdk", "webscm_url": "http://git.dpdk.org/dpdk", "list_archive_url": "https://inbox.dpdk.org/dev", "list_archive_url_format": "https://inbox.dpdk.org/dev/{}", "commit_url_format": "" }, "msgid": "<20190625211520.43181-3-honnappa.nagarahalli@arm.com>", "list_archive_url": "https://inbox.dpdk.org/dev/20190625211520.43181-3-honnappa.nagarahalli@arm.com", "date": "2019-06-25T21:15:19", "name": "[2/3] lib/hash: load pData after full key compare", "commit_ref": null, "pull_url": null, "state": "superseded", "archived": true, "hash": "4fd8fe37fb30bddcd4d3b30fdcce6620a2fcdc23", "submitter": { "id": 1045, "url": "http://patches.dpdk.org/api/people/1045/?format=api", "name": "Honnappa Nagarahalli", "email": "honnappa.nagarahalli@arm.com" }, "delegate": { "id": 1, "url": "http://patches.dpdk.org/api/users/1/?format=api", "username": "tmonjalo", "first_name": "Thomas", "last_name": "Monjalon", "email": "thomas@monjalon.net" }, "mbox": "http://patches.dpdk.org/project/dpdk/patch/20190625211520.43181-3-honnappa.nagarahalli@arm.com/mbox/", "series": [ { "id": 5166, "url": "http://patches.dpdk.org/api/series/5166/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/list/?series=5166", "date": "2019-06-25T21:15:17", "name": "lib/hash: perf improvements for lock-free", "version": 1, "mbox": "http://patches.dpdk.org/series/5166/mbox/" } ], "comments": "http://patches.dpdk.org/api/patches/55378/comments/", "check": "fail", "checks": "http://patches.dpdk.org/api/patches/55378/checks/", "tags": {}, "related": [], "headers": { "Return-Path": "<dev-bounces@dpdk.org>", "X-Original-To": "patchwork@dpdk.org", "Delivered-To": "patchwork@dpdk.org", "Received": [ "from [92.243.14.124] (localhost [127.0.0.1])\n\tby dpdk.org (Postfix) with ESMTP id 6E5B81B9B4;\n\tTue, 25 Jun 2019 23:15:49 +0200 (CEST)", "from foss.arm.com (foss.arm.com [217.140.110.172])\n\tby dpdk.org (Postfix) with ESMTP id C1D9E1B99C;\n\tTue, 25 Jun 2019 23:15:40 +0200 (CEST)", "from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14])\n\tby usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 1A4B7ED1;\n\tTue, 25 Jun 2019 14:15:40 -0700 (PDT)", "from qc2400f-1.austin.arm.com (qc2400f-1.austin.arm.com\n\t[10.118.12.65])\n\tby usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id\n\t04B923F246; Tue, 25 Jun 2019 14:15:40 -0700 (PDT)" ], "From": "Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>", "To": "yipeng1.wang@intel.com, sameh.gobriel@intel.com,\n\tbruce.richardson@intel.com, pablo.de.lara.guarch@intel.com,\n\thonnappa.nagarahalli@arm.com", "Cc": "gavin.hu@arm.com, ruifeng.wang@arm.com, dev@dpdk.org, nd@arm.com,\n\tstable@dpdk.org", "Date": "Tue, 25 Jun 2019 16:15:19 -0500", "Message-Id": "<20190625211520.43181-3-honnappa.nagarahalli@arm.com>", "X-Mailer": "git-send-email 2.17.1", "In-Reply-To": "<20190625211520.43181-1-honnappa.nagarahalli@arm.com>", "References": "<20190625211520.43181-1-honnappa.nagarahalli@arm.com>", "Subject": "[dpdk-dev] [PATCH 2/3] lib/hash: load pData after full key compare", "X-BeenThere": "dev@dpdk.org", "X-Mailman-Version": "2.1.15", "Precedence": "list", "List-Id": "DPDK patches and discussions <dev.dpdk.org>", "List-Unsubscribe": "<https://mails.dpdk.org/options/dev>,\n\t<mailto:dev-request@dpdk.org?subject=unsubscribe>", "List-Archive": "<http://mails.dpdk.org/archives/dev/>", "List-Post": "<mailto:dev@dpdk.org>", "List-Help": "<mailto:dev-request@dpdk.org?subject=help>", "List-Subscribe": "<https://mails.dpdk.org/listinfo/dev>,\n\t<mailto:dev-request@dpdk.org?subject=subscribe>", "Errors-To": "dev-bounces@dpdk.org", "Sender": "\"dev\" <dev-bounces@dpdk.org>" }, "content": "When a hash entry is added, there are 2 sets of stores.\n\n1) The application writes its data to memory (whose address\nis provided in rte_hash_add_key_with_hash_data API (or NULL))\n2) The rte_hash library writes to its own internal data structures;\nkey store entry and the hash table.\n\nThe only ordering requirement between these 2 is that - the store\nto the application data must complete before the store to key_index.\nThere are no ordering requirements between the stores to the\nkey/signature and store to application data. The synchronization\npoint for application data can be any point between the 'store to\napplication data' and 'store to the key_index'. So, pData should not\nbe a guard variable for the data in hash table. It should be a guard\nvariable only for the application data written to the memory location\npointed by pData. Hence, pData can be loaded after full key comparison.\n\nFixes: e605a1d36 (\"hash: add lock-free r/w concurrency\")\nCc: stable@dpdk.org\n\nSigned-off-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>\nReviewed-by: Gavin Hu <gavin.hu@arm.com>\nTested-by: Ruifeng Wang <ruifeng.wang@arm.com>\n---\n lib/librte_hash/rte_cuckoo_hash.c | 67 +++++++++++++++----------------\n 1 file changed, 32 insertions(+), 35 deletions(-)", "diff": "diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c\nindex f37f6957d..077328fed 100644\n--- a/lib/librte_hash/rte_cuckoo_hash.c\n+++ b/lib/librte_hash/rte_cuckoo_hash.c\n@@ -649,9 +649,11 @@ search_and_update(const struct rte_hash *h, void *data, const void *key,\n \t\t\tk = (struct rte_hash_key *) ((char *)keys +\n \t\t\t\t\tbkt->key_idx[i] * h->key_entry_size);\n \t\t\tif (rte_hash_cmp_eq(key, k->key, h) == 0) {\n-\t\t\t\t/* 'pdata' acts as the synchronization point\n-\t\t\t\t * when an existing hash entry is updated.\n-\t\t\t\t * Key is not updated in this case.\n+\t\t\t\t/* The store to application data at *data\n+\t\t\t\t * should not leak after the store to pdata\n+\t\t\t\t * in the key store. i.e. pdata is the guard\n+\t\t\t\t * variable. Release the application data\n+\t\t\t\t * to the readers.\n \t\t\t\t */\n \t\t\t\t__atomic_store_n(&k->pdata,\n \t\t\t\t\tdata,\n@@ -711,11 +713,10 @@ rte_hash_cuckoo_insert_mw(const struct rte_hash *h,\n \t\t/* Check if slot is available */\n \t\tif (likely(prim_bkt->key_idx[i] == EMPTY_SLOT)) {\n \t\t\tprim_bkt->sig_current[i] = sig;\n-\t\t\t/* Key can be of arbitrary length, so it is\n-\t\t\t * not possible to store it atomically.\n-\t\t\t * Hence the new key element's memory stores\n-\t\t\t * (key as well as data) should be complete\n-\t\t\t * before it is referenced.\n+\t\t\t/* Store to signature and key should not\n+\t\t\t * leak after the store to key_idx. i.e.\n+\t\t\t * key_idx is the guard variable for signature\n+\t\t\t * and key.\n \t\t\t */\n \t\t\t__atomic_store_n(&prim_bkt->key_idx[i],\n \t\t\t\t\t new_idx,\n@@ -990,17 +991,15 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \n \tnew_k = RTE_PTR_ADD(keys, (uintptr_t)slot_id * h->key_entry_size);\n \tnew_idx = (uint32_t)((uintptr_t) slot_id);\n-\t/* Copy key */\n-\tmemcpy(new_k->key, key, h->key_len);\n-\t/* Key can be of arbitrary length, so it is not possible to store\n-\t * it atomically. Hence the new key element's memory stores\n-\t * (key as well as data) should be complete before it is referenced.\n-\t * 'pdata' acts as the synchronization point when an existing hash\n-\t * entry is updated.\n+\t/* The store to application data (by the application) at *data should\n+\t * not leak after the store of pdata in the key store. i.e. pdata is\n+\t * the guard variable. Release the application data to the readers.\n \t */\n \t__atomic_store_n(&new_k->pdata,\n \t\tdata,\n \t\t__ATOMIC_RELEASE);\n+\t/* Copy key */\n+\tmemcpy(new_k->key, key, h->key_len);\n \n \t/* Find an empty slot and insert */\n \tret = rte_hash_cuckoo_insert_mw(h, prim_bkt, sec_bkt, key, data,\n@@ -1064,8 +1063,10 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \t\t\t/* Check if slot is available */\n \t\t\tif (likely(cur_bkt->key_idx[i] == EMPTY_SLOT)) {\n \t\t\t\tcur_bkt->sig_current[i] = short_sig;\n-\t\t\t\t/* Store to signature should not leak after\n-\t\t\t\t * the store to key_idx\n+\t\t\t\t/* Store to signature and key should not\n+\t\t\t\t * leak after the store to key_idx. i.e.\n+\t\t\t\t * key_idx is the guard variable for signature\n+\t\t\t\t * and key.\n \t\t\t\t */\n \t\t\t\t__atomic_store_n(&cur_bkt->key_idx[i],\n \t\t\t\t\t\t new_idx,\n@@ -1087,8 +1088,9 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \tbkt_id = (uint32_t)((uintptr_t)ext_bkt_id) - 1;\n \t/* Use the first location of the new bucket */\n \t(h->buckets_ext[bkt_id]).sig_current[0] = short_sig;\n-\t/* Store to signature should not leak after\n-\t * the store to key_idx\n+\t/* Store to signature and key should not leak after\n+\t * the store to key_idx. i.e. key_idx is the guard variable\n+\t * for signature and key.\n \t */\n \t__atomic_store_n(&(h->buckets_ext[bkt_id]).key_idx[0],\n \t\t\t new_idx,\n@@ -1184,7 +1186,6 @@ search_one_bucket_lf(const struct rte_hash *h, const void *key, uint16_t sig,\n {\n \tint i;\n \tuint32_t key_idx;\n-\tvoid *pdata;\n \tstruct rte_hash_key *k, *keys = h->key_store;\n \n \tfor (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {\n@@ -1199,12 +1200,13 @@ search_one_bucket_lf(const struct rte_hash *h, const void *key, uint16_t sig,\n \t\t\tif (key_idx != EMPTY_SLOT) {\n \t\t\t\tk = (struct rte_hash_key *) ((char *)keys +\n \t\t\t\t\t\tkey_idx * h->key_entry_size);\n-\t\t\t\tpdata = __atomic_load_n(&k->pdata,\n-\t\t\t\t\t\t__ATOMIC_ACQUIRE);\n \n \t\t\t\tif (rte_hash_cmp_eq(key, k->key, h) == 0) {\n-\t\t\t\t\tif (data != NULL)\n-\t\t\t\t\t\t*data = pdata;\n+\t\t\t\t\tif (data != NULL) {\n+\t\t\t\t\t\t*data = __atomic_load_n(\n+\t\t\t\t\t\t\t&k->pdata,\n+\t\t\t\t\t\t\t__ATOMIC_ACQUIRE);\n+\t\t\t\t\t}\n \t\t\t\t\t/*\n \t\t\t\t\t * Return index where key is stored,\n \t\t\t\t\t * subtracting the first dummy index\n@@ -1902,7 +1904,6 @@ __rte_hash_lookup_bulk_lf(const struct rte_hash *h, const void **keys,\n \tuint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};\n \tuint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};\n \tstruct rte_hash_bucket *cur_bkt, *next_bkt;\n-\tvoid *pdata[RTE_HASH_LOOKUP_BULK_MAX];\n \tuint32_t cnt_b, cnt_a;\n \n \t/* Prefetch first keys */\n@@ -2004,10 +2005,6 @@ __rte_hash_lookup_bulk_lf(const struct rte_hash *h, const void **keys,\n \t\t\t\t\t(const char *)h->key_store +\n \t\t\t\t\tkey_idx * h->key_entry_size);\n \n-\t\t\t\tif (key_idx != EMPTY_SLOT)\n-\t\t\t\t\tpdata[i] = __atomic_load_n(\n-\t\t\t\t\t\t\t&key_slot->pdata,\n-\t\t\t\t\t\t\t__ATOMIC_ACQUIRE);\n \t\t\t\t/*\n \t\t\t\t * If key index is 0, do not compare key,\n \t\t\t\t * as it is checking the dummy slot\n@@ -2016,7 +2013,9 @@ __rte_hash_lookup_bulk_lf(const struct rte_hash *h, const void **keys,\n \t\t\t\t\t!rte_hash_cmp_eq(\n \t\t\t\t\t\tkey_slot->key, keys[i], h)) {\n \t\t\t\t\tif (data != NULL)\n-\t\t\t\t\t\tdata[i] = pdata[i];\n+\t\t\t\t\t\tdata[i] = __atomic_load_n(\n+\t\t\t\t\t\t\t&key_slot->pdata,\n+\t\t\t\t\t\t\t__ATOMIC_ACQUIRE);\n \n \t\t\t\t\thits |= 1ULL << i;\n \t\t\t\t\tpositions[i] = key_idx - 1;\n@@ -2038,10 +2037,6 @@ __rte_hash_lookup_bulk_lf(const struct rte_hash *h, const void **keys,\n \t\t\t\t\t(const char *)h->key_store +\n \t\t\t\t\tkey_idx * h->key_entry_size);\n \n-\t\t\t\tif (key_idx != EMPTY_SLOT)\n-\t\t\t\t\tpdata[i] = __atomic_load_n(\n-\t\t\t\t\t\t\t&key_slot->pdata,\n-\t\t\t\t\t\t\t__ATOMIC_ACQUIRE);\n \t\t\t\t/*\n \t\t\t\t * If key index is 0, do not compare key,\n \t\t\t\t * as it is checking the dummy slot\n@@ -2051,7 +2046,9 @@ __rte_hash_lookup_bulk_lf(const struct rte_hash *h, const void **keys,\n \t\t\t\t\t!rte_hash_cmp_eq(\n \t\t\t\t\t\tkey_slot->key, keys[i], h)) {\n \t\t\t\t\tif (data != NULL)\n-\t\t\t\t\t\tdata[i] = pdata[i];\n+\t\t\t\t\t\tdata[i] = __atomic_load_n(\n+\t\t\t\t\t\t\t&key_slot->pdata,\n+\t\t\t\t\t\t\t__ATOMIC_ACQUIRE);\n \n \t\t\t\t\thits |= 1ULL << i;\n \t\t\t\t\tpositions[i] = key_idx - 1;\n", "prefixes": [ "2/3" ] }