From patchwork Fri Nov 9 16:39:16 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Honnappa Nagarahalli X-Patchwork-Id: 150686 Delivered-To: patch@linaro.org Received: by 2002:a2e:299d:0:0:0:0:0 with SMTP id p29-v6csp73266ljp; Fri, 9 Nov 2018 08:40:15 -0800 (PST) X-Google-Smtp-Source: AJdET5dOHCkLzt4gzIqMLwVtNzLFbAkTL7vPMyRb/VyPLHnnu+RFLnbJfv6t9bnKxuufuKCt//Zt X-Received: by 2002:a17:906:d289:: with SMTP id ay9-v6mr2319329ejb.155.1541781615312; Fri, 09 Nov 2018 08:40:15 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1541781615; cv=none; d=google.com; s=arc-20160816; b=XEp9y5WfAQJGZLOIaC2MbiNyqYWb0dJ/BsGQVMJyxuiKmTYEQXyrDR16qDu2a7+DTG bioFej6rKNMic4+0wHchKSAEkCrAHtIfzcpmAiGZaNvQTXpxAD0NuwHvXUJROZNs+eDT 4ITvL8C36yjgSEQp/qIwOrTopzUyB1UdjQfmjiQ9muEjUXIiR3V6ez0wjl5IbUhRnDzL wQcEajypjuciF3d6ZPczmaj+PhMTLc80dyGyKOmKu0Klyzcu+gFOBTys1RARY8i1ao+X WWfFSG1Q/wVuBJy+mzx7WP+63A93SOI5Ggbc96cnAzLmLvM9CjweJnozlHrBip7LBEZw 4D/A== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:subject:references:in-reply-to :message-id:date:cc:to:from; bh=vVbYM3C7wT7dHBFzSWgTXCmUB9rdbWTyKtIg4GTkZIM=; b=Z0QI5mBJRFmtw0kKjI0qySnXruDpBZxGH/Yevjw3vFdz5xBeMHwzfpxPJTpJDU6fLl zgMDL/Zj8ubiUgX4eLTTOO+dy8Zo7Ts7wqCQjxM0NssPBUn0KDBLOLqqhZ02DmYovx/g uJ8fOHo8QkB4oNy4Y1J16c6qwo+sz8uMOKOmpYSwT9KcFKkLVkJCsqZG2cSQN3dJ7MVK ZgQjxtKft1OimlpOYcfWi+rMKpL8z7Q3pnK8MAuhf/56gSkhLuyZewWHFGYJwln12Lm0 3UFJMBmc6cYtgcAQE2etvY85KmFBLMRk1z+FO7Xe7C2Usn5T+XAQQYdC2+5RiujJteEE aqcg== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) smtp.mailfrom=dev-bounces@dpdk.org Return-Path: Received: from dpdk.org (dpdk.org. [92.243.14.124]) by mx.google.com with ESMTP id a22-v6si704585eje.78.2018.11.09.08.40.14; Fri, 09 Nov 2018 08:40:15 -0800 (PST) Received-SPF: pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) client-ip=92.243.14.124; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) smtp.mailfrom=dev-bounces@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 1F9A54F98; Fri, 9 Nov 2018 17:39:51 +0100 (CET) Received: from foss.arm.com (foss.arm.com [217.140.101.70]) by dpdk.org (Postfix) with ESMTP id 219134CA5 for ; Fri, 9 Nov 2018 17:39:45 +0100 (CET) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 484D31650; Fri, 9 Nov 2018 08:39:44 -0800 (PST) Received: from qc2400f-1.austin.arm.com (qc2400f-1.austin.arm.com [10.118.12.122]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id BAE833F5BD; Fri, 9 Nov 2018 08:39:43 -0800 (PST) From: Honnappa Nagarahalli To: bruce.richardson@intel.com, pablo.de.lara.guarch@intel.com Cc: dev@dpdk.org, jerin.jacob@caviumnetworks.com, hemant.agrawal@nxp.com, chaozhu@linux.vnet.ibm.com, yipeng1.wang@intel.com, dharmik.thakkar@arm.com, gavin.hu@arm.com, honnappa.nagarahalli@arm.com, nd@arm.com Date: Fri, 9 Nov 2018 10:39:16 -0600 Message-Id: <20181109163917.16845-4-honnappa.nagarahalli@arm.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20181109163917.16845-1-honnappa.nagarahalli@arm.com> References: <20181109163917.16845-1-honnappa.nagarahalli@arm.com> Subject: [dpdk-dev] [PATCH 3/4] hash: remove memory orderings from rw-lock lookup fns 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" Remove the memory orderings from lookup functions using rw-lock. This is an intermediate commit meant to ease the review process. Fixes: e605a1d36 ("hash: add lock-free r/w concurrency") Cc: honnappa.nagarahalli@arm.com Suggested-by: Jerin Jacob Signed-off-by: Honnappa Nagarahalli Reviewed-by: Ola Liljedahl Reviewed-by: Gavin Hu --- lib/librte_hash/rte_cuckoo_hash.c | 277 +++++++++++------------------- 1 file changed, 105 insertions(+), 172 deletions(-) -- 2.17.1 diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index e6b84c6bc..9390dc5e4 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -1135,27 +1135,22 @@ search_one_bucket(const struct rte_hash *h, const void *key, uint16_t sig, void **data, const struct rte_hash_bucket *bkt) { int i; - uint32_t key_idx; - void *pdata; struct rte_hash_key *k, *keys = h->key_store; for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { - key_idx = __atomic_load_n(&bkt->key_idx[i], - __ATOMIC_ACQUIRE); - if (bkt->sig_current[i] == sig && key_idx != EMPTY_SLOT) { + if (bkt->sig_current[i] == sig && + bkt->key_idx[i] != EMPTY_SLOT) { k = (struct rte_hash_key *) ((char *)keys + - key_idx * h->key_entry_size); - pdata = __atomic_load_n(&k->pdata, - __ATOMIC_ACQUIRE); + bkt->key_idx[i] * h->key_entry_size); if (rte_hash_cmp_eq(key, k->key, h) == 0) { if (data != NULL) - *data = pdata; + *data = k->pdata; /* * Return index where key is stored, * subtracting the first dummy index */ - return key_idx - 1; + return bkt->key_idx[i] - 1; } } } @@ -1201,7 +1196,6 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, { uint32_t prim_bucket_idx, sec_bucket_idx; struct rte_hash_bucket *bkt, *cur_bkt; - uint32_t cnt_b, cnt_a; int ret; uint16_t short_sig; @@ -1211,49 +1205,25 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, __hash_rw_reader_lock(h); - do { - /* Load the table change counter before the lookup - * starts. Acquire semantics will make sure that - * loads in search_one_bucket are not hoisted. - */ - cnt_b = __atomic_load_n(h->tbl_chng_cnt, - __ATOMIC_ACQUIRE); + /* Check if key is in primary location */ + bkt = &h->buckets[prim_bucket_idx]; + ret = search_one_bucket(h, key, short_sig, data, bkt); + if (ret != -1) { + __hash_rw_reader_unlock(h); + return ret; + } + /* Calculate secondary hash */ + bkt = &h->buckets[sec_bucket_idx]; - /* Check if key is in primary location */ - bkt = &h->buckets[prim_bucket_idx]; - ret = search_one_bucket(h, key, short_sig, data, bkt); + /* Check if key is in secondary location */ + FOR_EACH_BUCKET(cur_bkt, bkt) { + ret = search_one_bucket(h, key, short_sig, + data, cur_bkt); if (ret != -1) { __hash_rw_reader_unlock(h); return ret; } - /* Calculate secondary hash */ - bkt = &h->buckets[sec_bucket_idx]; - - /* Check if key is in secondary location */ - FOR_EACH_BUCKET(cur_bkt, bkt) { - ret = search_one_bucket(h, key, short_sig, - data, cur_bkt); - if (ret != -1) { - __hash_rw_reader_unlock(h); - return ret; - } - } - - /* The loads of sig_current in search_one_bucket - * should not move below the load from tbl_chng_cnt. - */ - __atomic_thread_fence(__ATOMIC_ACQUIRE); - /* Re-read the table change counter to check if the - * table has changed during search. If yes, re-do - * the search. - * This load should not get hoisted. The load - * acquires on cnt_b, key index in primary bucket - * and key index in secondary bucket will make sure - * that it does not get hoisted. - */ - cnt_a = __atomic_load_n(h->tbl_chng_cnt, - __ATOMIC_ACQUIRE); - } while (cnt_b != cnt_a); + } __hash_rw_reader_unlock(h); @@ -1638,8 +1608,6 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, uint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0}; uint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0}; struct rte_hash_bucket *cur_bkt, *next_bkt; - void *pdata[RTE_HASH_LOOKUP_BULK_MAX]; - uint32_t cnt_b, cnt_a; /* Prefetch first keys */ for (i = 0; i < PREFETCH_OFFSET && i < num_keys; i++) @@ -1681,138 +1649,103 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, } __hash_rw_reader_lock(h); - do { - /* Load the table change counter before the lookup - * starts. Acquire semantics will make sure that - * loads in compare_signatures are not hoisted. - */ - cnt_b = __atomic_load_n(h->tbl_chng_cnt, - __ATOMIC_ACQUIRE); - - /* Compare signatures and prefetch key slot of first hit */ - for (i = 0; i < num_keys; i++) { - compare_signatures(&prim_hitmask[i], &sec_hitmask[i], - primary_bkt[i], secondary_bkt[i], - sig[i], h->sig_cmp_fn); - - if (prim_hitmask[i]) { - uint32_t first_hit = - __builtin_ctzl(prim_hitmask[i]) - >> 1; - uint32_t key_idx = - primary_bkt[i]->key_idx[first_hit]; - const struct rte_hash_key *key_slot = - (const struct rte_hash_key *)( - (const char *)h->key_store + - key_idx * h->key_entry_size); - rte_prefetch0(key_slot); - continue; - } - if (sec_hitmask[i]) { - uint32_t first_hit = - __builtin_ctzl(sec_hitmask[i]) - >> 1; - uint32_t key_idx = - secondary_bkt[i]->key_idx[first_hit]; - const struct rte_hash_key *key_slot = - (const struct rte_hash_key *)( - (const char *)h->key_store + - key_idx * h->key_entry_size); - rte_prefetch0(key_slot); - } + /* Compare signatures and prefetch key slot of first hit */ + for (i = 0; i < num_keys; i++) { + compare_signatures(&prim_hitmask[i], &sec_hitmask[i], + primary_bkt[i], secondary_bkt[i], + sig[i], h->sig_cmp_fn); + + if (prim_hitmask[i]) { + uint32_t first_hit = + __builtin_ctzl(prim_hitmask[i]) + >> 1; + uint32_t key_idx = + primary_bkt[i]->key_idx[first_hit]; + const struct rte_hash_key *key_slot = + (const struct rte_hash_key *)( + (const char *)h->key_store + + key_idx * h->key_entry_size); + rte_prefetch0(key_slot); + continue; } - /* Compare keys, first hits in primary first */ - for (i = 0; i < num_keys; i++) { - positions[i] = -ENOENT; - while (prim_hitmask[i]) { - uint32_t hit_index = - __builtin_ctzl(prim_hitmask[i]) - >> 1; - uint32_t key_idx = - __atomic_load_n( - &primary_bkt[i]->key_idx[hit_index], - __ATOMIC_ACQUIRE); - const struct rte_hash_key *key_slot = - (const struct rte_hash_key *)( - (const char *)h->key_store + - key_idx * h->key_entry_size); + if (sec_hitmask[i]) { + uint32_t first_hit = + __builtin_ctzl(sec_hitmask[i]) + >> 1; + uint32_t key_idx = + secondary_bkt[i]->key_idx[first_hit]; + const struct rte_hash_key *key_slot = + (const struct rte_hash_key *)( + (const char *)h->key_store + + key_idx * h->key_entry_size); + rte_prefetch0(key_slot); + } + } - if (key_idx != EMPTY_SLOT) - pdata[i] = __atomic_load_n( - &key_slot->pdata, - __ATOMIC_ACQUIRE); - /* - * If key index is 0, do not compare key, - * as it is checking the dummy slot - */ - if (!!key_idx & - !rte_hash_cmp_eq( - key_slot->key, keys[i], h)) { - if (data != NULL) - data[i] = pdata[i]; + /* Compare keys, first hits in primary first */ + for (i = 0; i < num_keys; i++) { + positions[i] = -ENOENT; + while (prim_hitmask[i]) { + uint32_t hit_index = + __builtin_ctzl(prim_hitmask[i]) + >> 1; + uint32_t key_idx = + primary_bkt[i]->key_idx[hit_index]; + const struct rte_hash_key *key_slot = + (const struct rte_hash_key *)( + (const char *)h->key_store + + key_idx * h->key_entry_size); + + /* + * If key index is 0, do not compare key, + * as it is checking the dummy slot + */ + if (!!key_idx & + !rte_hash_cmp_eq( + key_slot->key, keys[i], h)) { + if (data != NULL) + data[i] = key_slot->pdata; - hits |= 1ULL << i; - positions[i] = key_idx - 1; - goto next_key; - } - prim_hitmask[i] &= ~(3ULL << (hit_index << 1)); + hits |= 1ULL << i; + positions[i] = key_idx - 1; + goto next_key; } + prim_hitmask[i] &= ~(3ULL << (hit_index << 1)); + } - while (sec_hitmask[i]) { - uint32_t hit_index = - __builtin_ctzl(sec_hitmask[i]) - >> 1; - uint32_t key_idx = - __atomic_load_n( - &secondary_bkt[i]->key_idx[hit_index], - __ATOMIC_ACQUIRE); - const struct rte_hash_key *key_slot = - (const struct rte_hash_key *)( - (const char *)h->key_store + - key_idx * h->key_entry_size); - - if (key_idx != EMPTY_SLOT) - pdata[i] = __atomic_load_n( - &key_slot->pdata, - __ATOMIC_ACQUIRE); - /* - * If key index is 0, do not compare key, - * as it is checking the dummy slot - */ + while (sec_hitmask[i]) { + uint32_t hit_index = + __builtin_ctzl(sec_hitmask[i]) + >> 1; + uint32_t key_idx = + secondary_bkt[i]->key_idx[hit_index]; + const struct rte_hash_key *key_slot = + (const struct rte_hash_key *)( + (const char *)h->key_store + + key_idx * h->key_entry_size); + + /* + * If key index is 0, do not compare key, + * as it is checking the dummy slot + */ - if (!!key_idx & - !rte_hash_cmp_eq( - key_slot->key, keys[i], h)) { - if (data != NULL) - data[i] = pdata[i]; + if (!!key_idx & + !rte_hash_cmp_eq( + key_slot->key, keys[i], h)) { + if (data != NULL) + data[i] = key_slot->pdata; - hits |= 1ULL << i; - positions[i] = key_idx - 1; - goto next_key; - } - sec_hitmask[i] &= ~(3ULL << (hit_index << 1)); + hits |= 1ULL << i; + positions[i] = key_idx - 1; + goto next_key; } -next_key: - continue; + sec_hitmask[i] &= ~(3ULL << (hit_index << 1)); } - - /* The loads of sig_current in compare_signatures - * should not move below the load from tbl_chng_cnt. - */ - __atomic_thread_fence(__ATOMIC_ACQUIRE); - /* Re-read the table change counter to check if the - * table has changed during search. If yes, re-do - * the search. - * This load should not get hoisted. The load - * acquires on cnt_b, primary key index and secondary - * key index will make sure that it does not get - * hoisted. - */ - cnt_a = __atomic_load_n(h->tbl_chng_cnt, - __ATOMIC_ACQUIRE); - } while (cnt_b != cnt_a); +next_key: + continue; + } /* all found, do not need to go through ext bkt */ if ((hits == ((1ULL << num_keys) - 1)) || !h->ext_table_support) {