Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/44351/?format=api
{ "id": 44351, "url": "http://patches.dpdk.org/api/patches/44351/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/patch/1536253938-192391-3-git-send-email-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": "<1536253938-192391-3-git-send-email-honnappa.nagarahalli@arm.com>", "list_archive_url": "https://inbox.dpdk.org/dev/1536253938-192391-3-git-send-email-honnappa.nagarahalli@arm.com", "date": "2018-09-06T17:12:16", "name": "[2/4] hash: add memory ordering to avoid race conditions", "commit_ref": null, "pull_url": null, "state": "superseded", "archived": true, "hash": "f56223d43272bdeb3b565501468d06a655e4b6ad", "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/1536253938-192391-3-git-send-email-honnappa.nagarahalli@arm.com/mbox/", "series": [ { "id": 1214, "url": "http://patches.dpdk.org/api/series/1214/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/list/?series=1214", "date": "2018-09-06T17:12:14", "name": "Address reader-writer concurrency in rte_hash", "version": 1, "mbox": "http://patches.dpdk.org/series/1214/mbox/" } ], "comments": "http://patches.dpdk.org/api/patches/44351/comments/", "check": "success", "checks": "http://patches.dpdk.org/api/patches/44351/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 A7E854C9D;\n\tThu, 6 Sep 2018 19:12:33 +0200 (CEST)", "from foss.arm.com (foss.arm.com [217.140.101.70])\n\tby dpdk.org (Postfix) with ESMTP id 3C3254C88\n\tfor <dev@dpdk.org>; Thu, 6 Sep 2018 19:12:32 +0200 (CEST)", "from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249])\n\tby usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id A27097A9;\n\tThu, 6 Sep 2018 10:12:31 -0700 (PDT)", "from 2p2660v4-1.austin.arm.com (2p2660v4-1.austin.arm.com\n\t[10.118.12.164])\n\tby usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id\n\t342633F557; Thu, 6 Sep 2018 10:12:31 -0700 (PDT)" ], "From": "Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>", "To": "bruce.richardson@intel.com,\n\tpablo.de.lara.guarch@intel.com", "Cc": "dev@dpdk.org, honnappa.nagarahalli@dpdk.org, gavin.hu@arm.com,\n\tsteve.capper@arm.com, ola.liljedahl@arm.com, nd@arm.com,\n\tHonnappa Nagarahalli <honnappa.nagarahalli@arm.com>", "Date": "Thu, 6 Sep 2018 12:12:16 -0500", "Message-Id": "<1536253938-192391-3-git-send-email-honnappa.nagarahalli@arm.com>", "X-Mailer": "git-send-email 2.7.4", "In-Reply-To": "<1536253938-192391-1-git-send-email-honnappa.nagarahalli@arm.com>", "References": "<1536253938-192391-1-git-send-email-honnappa.nagarahalli@arm.com>", "Subject": "[dpdk-dev] [PATCH 2/4] hash: add memory ordering to avoid race\n\tconditions", "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": "Only race condition that can occur is - using the key store element\nbefore the key write is completed. Hence, while inserting the element\nthe release memory order is used. Any other race condition is caught\nby the key comparison. Memory orderings are added only where needed.\nFor ex: reads in the writer's context do not need memory ordering\nas there is a single writer.\n\nkey_idx in the bucket entry and pdata in the key store element are\nused for synchronisation. key_idx is used to release an inserted\nentry in the bucket to the reader. Use of pdata for synchronisation\nis required due to updation of an existing entry where-in only\nthe pdata is updated without updating key_idx.\n\nSigned-off-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>\nReviewed-by: Gavin Hu <gavin.hu@arm.com>\nReviewed-by: Ola Liljedahl <ola.liljedahl@arm.com>\nReviewed-by: Steve Capper <steve.capper@arm.com>\n---\n lib/librte_hash/rte_cuckoo_hash.c | 111 ++++++++++++++++++++++++++++----------\n 1 file changed, 82 insertions(+), 29 deletions(-)", "diff": "diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c\nindex 33acfc9..2d89158 100644\n--- a/lib/librte_hash/rte_cuckoo_hash.c\n+++ b/lib/librte_hash/rte_cuckoo_hash.c\n@@ -485,7 +485,9 @@ enqueue_slot_back(const struct rte_hash *h,\n \t\trte_ring_sp_enqueue(h->free_slots, slot_id);\n }\n \n-/* Search a key from bucket and update its data */\n+/* Search a key from bucket and update its data.\n+ * Writer holds the lock before calling this.\n+ */\n static inline int32_t\n search_and_update(const struct rte_hash *h, void *data, const void *key,\n \tstruct rte_hash_bucket *bkt, hash_sig_t sig, hash_sig_t alt_hash)\n@@ -499,8 +501,13 @@ 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/* Update data */\n-\t\t\t\tk->pdata = data;\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 */\n+\t\t\t\t__atomic_store_n(&k->pdata,\n+\t\t\t\t\tdata,\n+\t\t\t\t\t__ATOMIC_RELEASE);\n \t\t\t\t/*\n \t\t\t\t * Return index where key is stored,\n \t\t\t\t * subtracting the first dummy index\n@@ -554,7 +561,15 @@ rte_hash_cuckoo_insert_mw(const struct rte_hash *h,\n \t\tif (likely(prim_bkt->key_idx[i] == EMPTY_SLOT)) {\n \t\t\tprim_bkt->sig_current[i] = sig;\n \t\t\tprim_bkt->sig_alt[i] = alt_hash;\n-\t\t\tprim_bkt->key_idx[i] = new_idx;\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 */\n+\t\t\t__atomic_store_n(&prim_bkt->key_idx[i],\n+\t\t\t\t\t new_idx,\n+\t\t\t\t\t __ATOMIC_RELEASE);\n \t\t\tbreak;\n \t\t}\n \t}\n@@ -637,8 +652,10 @@ rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h,\n \t\t\t prev_bkt->sig_current[prev_slot];\n \t\tcurr_bkt->sig_current[curr_slot] =\n \t\t\tprev_bkt->sig_alt[prev_slot];\n-\t\tcurr_bkt->key_idx[curr_slot] =\n-\t\t\tprev_bkt->key_idx[prev_slot];\n+\t\t/* Release the updated bucket entry */\n+\t\t__atomic_store_n(&curr_bkt->key_idx[curr_slot],\n+\t\t\tprev_bkt->key_idx[prev_slot],\n+\t\t\t__ATOMIC_RELEASE);\n \n \t\tcurr_slot = prev_slot;\n \t\tcurr_node = prev_node;\n@@ -647,7 +664,10 @@ rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h,\n \n \tcurr_bkt->sig_current[curr_slot] = sig;\n \tcurr_bkt->sig_alt[curr_slot] = alt_hash;\n-\tcurr_bkt->key_idx[curr_slot] = new_idx;\n+\t/* Release the new bucket entry */\n+\t__atomic_store_n(&curr_bkt->key_idx[curr_slot],\n+\t\t\t new_idx,\n+\t\t\t __ATOMIC_RELEASE);\n \n \t__hash_rw_writer_unlock(h);\n \n@@ -778,8 +798,15 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \tnew_idx = (uint32_t)((uintptr_t) slot_id);\n \t/* Copy key */\n \trte_memcpy(new_k->key, key, h->key_len);\n-\tnew_k->pdata = data;\n-\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 */\n+\t__atomic_store_n(&new_k->pdata,\n+\t\tdata,\n+\t\t__ATOMIC_RELEASE);\n \n \t/* Find an empty slot and insert */\n \tret = rte_hash_cuckoo_insert_mw(h, prim_bkt, sec_bkt, key, data,\n@@ -865,21 +892,27 @@ search_one_bucket(const struct rte_hash *h, const void *key, hash_sig_t sig,\n \t\t\tvoid **data, const struct rte_hash_bucket *bkt)\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-\t\tif (bkt->sig_current[i] == sig &&\n-\t\t\t\tbkt->key_idx[i] != EMPTY_SLOT) {\n+\t\tkey_idx = __atomic_load_n(&bkt->key_idx[i],\n+\t\t\t\t\t __ATOMIC_ACQUIRE);\n+\t\tif (bkt->sig_current[i] == sig && key_idx != EMPTY_SLOT) {\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\t\t\tkey_idx * h->key_entry_size);\n+\t\t\tpdata = __atomic_load_n(&k->pdata,\n+\t\t\t\t\t__ATOMIC_ACQUIRE);\n+\n \t\t\tif (rte_hash_cmp_eq(key, k->key, h) == 0) {\n \t\t\t\tif (data != NULL)\n-\t\t\t\t\t*data = k->pdata;\n+\t\t\t\t\t*data = pdata;\n \t\t\t\t/*\n \t\t\t\t * Return index where key is stored,\n \t\t\t\t * subtracting the first dummy index\n \t\t\t\t */\n-\t\t\t\treturn bkt->key_idx[i] - 1;\n+\t\t\t\treturn key_idx - 1;\n \t\t\t}\n \t\t}\n \t}\n@@ -980,31 +1013,36 @@ remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i)\n \t}\n }\n \n-/* Search one bucket and remove the matched key */\n+/* Search one bucket and remove the matched key.\n+ * Writer is expected to hold the lock while calling this\n+ * function.\n+ */\n static inline int32_t\n search_and_remove(const struct rte_hash *h, const void *key,\n \t\t\tstruct rte_hash_bucket *bkt, hash_sig_t sig)\n {\n \tstruct rte_hash_key *k, *keys = h->key_store;\n \tunsigned int i;\n-\tint32_t ret;\n+\tuint32_t key_idx;\n \n \t/* Check if key is in primary location */\n \tfor (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {\n-\t\tif (bkt->sig_current[i] == sig &&\n-\t\t\t\tbkt->key_idx[i] != EMPTY_SLOT) {\n+\t\tkey_idx = __atomic_load_n(&bkt->key_idx[i],\n+\t\t\t\t\t __ATOMIC_ACQUIRE);\n+\t\tif (bkt->sig_current[i] == sig && key_idx != EMPTY_SLOT) {\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\t\t\tkey_idx * h->key_entry_size);\n \t\t\tif (rte_hash_cmp_eq(key, k->key, h) == 0) {\n \t\t\t\tremove_entry(h, bkt, i);\n \n+\t\t\t\t__atomic_store_n(&bkt->key_idx[i],\n+\t\t\t\t\t\t EMPTY_SLOT,\n+\t\t\t\t\t\t __ATOMIC_RELEASE);\n \t\t\t\t/*\n \t\t\t\t * Return index where key is stored,\n \t\t\t\t * subtracting the first dummy index\n \t\t\t\t */\n-\t\t\t\tret = bkt->key_idx[i] - 1;\n-\t\t\t\tbkt->key_idx[i] = EMPTY_SLOT;\n-\t\t\t\treturn ret;\n+\t\t\t\treturn key_idx - 1;\n \t\t\t}\n \t\t}\n \t}\n@@ -1151,6 +1189,7 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,\n \tconst struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX];\n \tuint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};\n \tuint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};\n+\tvoid *pdata[RTE_HASH_LOOKUP_BULK_MAX];\n \n \t/* Prefetch first keys */\n \tfor (i = 0; i < PREFETCH_OFFSET && i < num_keys; i++)\n@@ -1220,18 +1259,25 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,\n \t\twhile (prim_hitmask[i]) {\n \t\t\tuint32_t hit_index = __builtin_ctzl(prim_hitmask[i]);\n \n-\t\t\tuint32_t key_idx = primary_bkt[i]->key_idx[hit_index];\n+\t\t\tuint32_t key_idx =\n+\t\t\t__atomic_load_n(\n+\t\t\t\t&primary_bkt[i]->key_idx[hit_index],\n+\t\t\t\t__ATOMIC_ACQUIRE);\n \t\t\tconst struct rte_hash_key *key_slot =\n \t\t\t\t(const struct rte_hash_key *)(\n \t\t\t\t(const char *)h->key_store +\n \t\t\t\tkey_idx * h->key_entry_size);\n+\n+\t\t\tif (key_idx != EMPTY_SLOT)\n+\t\t\t\tpdata[i] = __atomic_load_n(&key_slot->pdata,\n+\t\t\t\t\t\t__ATOMIC_ACQUIRE);\n \t\t\t/*\n \t\t\t * If key index is 0, do not compare key,\n \t\t\t * as it is checking the dummy slot\n \t\t\t */\n \t\t\tif (!!key_idx & !rte_hash_cmp_eq(key_slot->key, keys[i], h)) {\n \t\t\t\tif (data != NULL)\n-\t\t\t\t\tdata[i] = key_slot->pdata;\n+\t\t\t\t\tdata[i] = pdata[i];\n \n \t\t\t\thits |= 1ULL << i;\n \t\t\t\tpositions[i] = key_idx - 1;\n@@ -1243,11 +1289,19 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,\n \t\twhile (sec_hitmask[i]) {\n \t\t\tuint32_t hit_index = __builtin_ctzl(sec_hitmask[i]);\n \n-\t\t\tuint32_t key_idx = secondary_bkt[i]->key_idx[hit_index];\n+\t\t\tuint32_t key_idx =\n+\t\t\t__atomic_load_n(\n+\t\t\t\t&secondary_bkt[i]->key_idx[hit_index],\n+\t\t\t\t__ATOMIC_ACQUIRE);\n \t\t\tconst struct rte_hash_key *key_slot =\n \t\t\t\t(const struct rte_hash_key *)(\n \t\t\t\t(const char *)h->key_store +\n \t\t\t\tkey_idx * h->key_entry_size);\n+\n+\t\t\tif (key_idx != EMPTY_SLOT)\n+\t\t\t\tpdata[i] = __atomic_load_n(&key_slot->pdata,\n+\t\t\t\t\t\t__ATOMIC_ACQUIRE);\n+\n \t\t\t/*\n \t\t\t * If key index is 0, do not compare key,\n \t\t\t * as it is checking the dummy slot\n@@ -1255,7 +1309,7 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,\n \n \t\t\tif (!!key_idx & !rte_hash_cmp_eq(key_slot->key, keys[i], h)) {\n \t\t\t\tif (data != NULL)\n-\t\t\t\t\tdata[i] = key_slot->pdata;\n+\t\t\t\t\tdata[i] = pdata[i];\n \n \t\t\t\thits |= 1ULL << i;\n \t\t\t\tpositions[i] = key_idx - 1;\n@@ -1320,7 +1374,8 @@ rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32\n \tidx = *next % RTE_HASH_BUCKET_ENTRIES;\n \n \t/* If current position is empty, go to the next one */\n-\twhile (h->buckets[bucket_idx].key_idx[idx] == EMPTY_SLOT) {\n+\twhile ((position = __atomic_load_n(&h->buckets[bucket_idx].key_idx[idx],\n+\t\t\t\t\t__ATOMIC_ACQUIRE)) == EMPTY_SLOT) {\n \t\t(*next)++;\n \t\t/* End of table */\n \t\tif (*next == total_entries)\n@@ -1329,8 +1384,6 @@ rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32\n \t\tidx = *next % RTE_HASH_BUCKET_ENTRIES;\n \t}\n \t__hash_rw_reader_lock(h);\n-\t/* Get position of entry in key table */\n-\tposition = h->buckets[bucket_idx].key_idx[idx];\n \tnext_key = (struct rte_hash_key *) ((char *)h->key_store +\n \t\t\t\tposition * h->key_entry_size);\n \t/* Return key and data */\n", "prefixes": [ "2/4" ] }