From patchwork Thu Sep 6 17:12:15 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Honnappa Nagarahalli X-Patchwork-Id: 146116 Delivered-To: patch@linaro.org Received: by 2002:a2e:1648:0:0:0:0:0 with SMTP id 8-v6csp126080ljw; Thu, 6 Sep 2018 10:12:37 -0700 (PDT) X-Google-Smtp-Source: ANB0VdailGWe4RXHgWh/uLF0Htd2o7VG0Id0aAc2NaYDazUSKV09t72nSNjL8iP/WoK1qXh+2+tq X-Received: by 2002:a1c:7e13:: with SMTP id z19-v6mr2632164wmc.156.1536253957187; Thu, 06 Sep 2018 10:12:37 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1536253957; cv=none; d=google.com; s=arc-20160816; b=fv0gh/j5Ew5Lf6PnFfD6JfBinAdqP5C4LBOiRc5S0MIb7VkQopcMcmumi5pPTlMIcj nZg7atY4VotbcJ0FrdvLbJtlQ1MfckmqzLlm+qIBhhOL13r8ocO2g+51O4MLaJLGPNkG qbhsM6Fl3qpXsoFbGaR3c6BYTDWPHxkzMf2tKIHInP7DWG/JS+n6oia/qorphDjPWjKZ pn6710SiNPwBZc/nvgtrIPi0mz5TU/rzb3O1Iptby+6S6aTkFCZ702zUW/drWcd1PlJN GWgZmx+TrlOSQLazagTvkcvFJms53ssr+uO78guAu2wEVEzX+aj70pWuUCvNeRJyd85O BVvw== 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=YjLGn6/Hbns7UlGHvb8WY/F7VhAmRV6UvqdoyQwGuCQ=; b=TcRisjTXCJnifHo/z9VYxzg2cB3sC4JY6Q8TNn8GBkvXwIStow16/PC/ILZ1op22cY 7ahM4rvn2HCOjZ8wYAkFQIB47cQ3wgTZH7qu+NYq/6P2jj2LhEKQNQuw0KzhExOdQwrY mX7khfVAffAg8HsHsOmaZSPKCCZlRvaKZjXe+ESetxOQj59yv0nrXRzfEK5wnaXFut0b 7UtsRrpTlUtPzw4mGMUXkf2hR68z2kjjn0/DFmhP9wYXqIrvxd1wJ5NuUrPNtAqMq9Na CfvR+EQxbuqqeYe30ubIScR6r1htYukXKBrbr+lKgvhC6oOe69kngtKE7WmVp5tkDMHj u6NA== 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 n18-v6si5178869wrq.29.2018.09.06.10.12.36; Thu, 06 Sep 2018 10:12:37 -0700 (PDT) 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 348834C80; Thu, 6 Sep 2018 19:12:32 +0200 (CEST) Received: from foss.arm.com (usa-sjc-mx-foss1.foss.arm.com [217.140.101.70]) by dpdk.org (Postfix) with ESMTP id 31D2D4C77 for ; Thu, 6 Sep 2018 19:12:30 +0200 (CEST) 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 8BB047A9; Thu, 6 Sep 2018 10:12:29 -0700 (PDT) Received: from 2p2660v4-1.austin.arm.com (2p2660v4-1.austin.arm.com [10.118.12.164]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 1E2333F557; Thu, 6 Sep 2018 10:12:29 -0700 (PDT) From: Honnappa Nagarahalli To: bruce.richardson@intel.com, pablo.de.lara.guarch@intel.com Cc: dev@dpdk.org, honnappa.nagarahalli@dpdk.org, gavin.hu@arm.com, steve.capper@arm.com, ola.liljedahl@arm.com, nd@arm.com, Honnappa Nagarahalli Date: Thu, 6 Sep 2018 12:12:15 -0500 Message-Id: <1536253938-192391-2-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 1/4] hash: correct key store element alignment 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" Correct the key store array element alignment. This is required to make 'pdata' in 'struct rte_hash_key' align on the correct boundary. Signed-off-by: Honnappa Nagarahalli Reviewed-by: Gavin Hu Reviewed-by: Ola Liljedahl Reviewed-by: Steve Capper --- lib/librte_hash/rte_cuckoo_hash.c | 4 +++- lib/librte_hash/rte_cuckoo_hash.h | 2 +- 2 files changed, 4 insertions(+), 2 deletions(-) -- 2.7.4 diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index f7b86c8..33acfc9 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -189,7 +189,9 @@ rte_hash_create(const struct rte_hash_parameters *params) goto err_unlock; } - const uint32_t key_entry_size = sizeof(struct rte_hash_key) + params->key_len; + const uint32_t key_entry_size = + RTE_ALIGN(sizeof(struct rte_hash_key) + params->key_len, + KEY_ALIGNMENT); const uint64_t key_tbl_size = (uint64_t) key_entry_size * num_key_slots; k = rte_zmalloc_socket(NULL, key_tbl_size, diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h index b43f467..b0c7ef9 100644 --- a/lib/librte_hash/rte_cuckoo_hash.h +++ b/lib/librte_hash/rte_cuckoo_hash.h @@ -125,7 +125,7 @@ struct rte_hash_key { }; /* Variable key size */ char key[0]; -} __attribute__((aligned(KEY_ALIGNMENT))); +}; /* All different signature compare functions */ enum rte_hash_sig_compare_function { From patchwork Thu Sep 6 17:12: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: 146117 Delivered-To: patch@linaro.org Received: by 2002:a2e:1648:0:0:0:0:0 with SMTP id 8-v6csp126248ljw; Thu, 6 Sep 2018 10:12:46 -0700 (PDT) X-Google-Smtp-Source: ANB0VdZ8VrOgdXjUGndF3QyeBjE8Yj8NZLVZwgh18Tge5XByYYtq2+PLQX1vXRQ3ShxC0WTfqko1 X-Received: by 2002:a1c:7305:: with SMTP id d5-v6mr2832395wmb.53.1536253966441; Thu, 06 Sep 2018 10:12:46 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1536253966; cv=none; d=google.com; s=arc-20160816; b=I7xEFQA6Ru5j05g2zzGSDzpDx4D7LSbHqKpTD7lULjHRX9Dvh7BnAWg1qGs5tJE31y Vm1kJ1nhGnKFAko5Z3zZqKo2YjfUNlx6uaSb7FzlRo1PGmGkIt2EffUyz1Grr4tP8tGs er+w6bGZ5Z5+3MlcSlMtgZpqmKr+t4h+0XY4PsA1JEb2WHnjPQrx/O924V0MN2PN4pN7 BP2IjPIWsuufMA3dNFyLYEXc7NVnTyY3gvjC5SGPJMOZ/k+8qFKi3YpGfQ6uuqrl5I/f zFuzuUjbbxkOHSAbudcOpz4XX9L/B8hDCjoe6RiB/KFXkQ55ibpZDlzXo3H/VE+EVT4l n3gA== 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=bqXTyh77tYNL9Yz8I2eLGUSIVVpZzKY3rDnzOgyiycw=; b=IXxKv/rcWgRXlPmkbOXC8n5C67wveY6P+NTWsMTeabSKHzNxrK7m6gdzJsrXYD+Hiz FMcUFysFnF1Mh3JpLtIy6djuLwUYOMQfvCD0n4pI7i23DHqVXDCJKZonwH8maS04796U iDTBlmy/u3k6+WlX1/jYZ6FFvo1sb7V+CVdC2r2Z/4lj1okPktHexA8ksxty1Ny3UCH0 9eSJmcMe/hMSwrAsCiIJdUwE+FjnGoxGVy7XbRri41HucPwT1jnbPy6ge7rd2F93DvMS DyQzMoMl/QQXeMM8yWz1PWGmiSv/cjpdE7/3T5WZHmMY3CAkHLRsIVqM6Fosl8Aw0inQ rRyw== 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 i4-v6si5809882wrc.177.2018.09.06.10.12.46; Thu, 06 Sep 2018 10:12:46 -0700 (PDT) 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 A7E854C9D; Thu, 6 Sep 2018 19:12:33 +0200 (CEST) Received: from foss.arm.com (foss.arm.com [217.140.101.70]) by dpdk.org (Postfix) with ESMTP id 3C3254C88 for ; Thu, 6 Sep 2018 19:12:32 +0200 (CEST) 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 A27097A9; Thu, 6 Sep 2018 10:12:31 -0700 (PDT) Received: from 2p2660v4-1.austin.arm.com (2p2660v4-1.austin.arm.com [10.118.12.164]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 342633F557; Thu, 6 Sep 2018 10:12:31 -0700 (PDT) From: Honnappa Nagarahalli To: bruce.richardson@intel.com, pablo.de.lara.guarch@intel.com Cc: dev@dpdk.org, honnappa.nagarahalli@dpdk.org, gavin.hu@arm.com, steve.capper@arm.com, ola.liljedahl@arm.com, nd@arm.com, Honnappa Nagarahalli 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 conditions 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" Only race condition that can occur is - using the key store element before the key write is completed. Hence, while inserting the element the release memory order is used. Any other race condition is caught by the key comparison. Memory orderings are added only where needed. For ex: reads in the writer's context do not need memory ordering as there is a single writer. key_idx in the bucket entry and pdata in the key store element are used for synchronisation. key_idx is used to release an inserted entry in the bucket to the reader. Use of pdata for synchronisation is required due to updation of an existing entry where-in only the pdata is updated without updating key_idx. Signed-off-by: Honnappa Nagarahalli Reviewed-by: Gavin Hu Reviewed-by: Ola Liljedahl Reviewed-by: Steve Capper --- lib/librte_hash/rte_cuckoo_hash.c | 111 ++++++++++++++++++++++++++++---------- 1 file changed, 82 insertions(+), 29 deletions(-) -- 2.7.4 diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index 33acfc9..2d89158 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -485,7 +485,9 @@ enqueue_slot_back(const struct rte_hash *h, rte_ring_sp_enqueue(h->free_slots, slot_id); } -/* Search a key from bucket and update its data */ +/* Search a key from bucket and update its data. + * Writer holds the lock before calling this. + */ static inline int32_t search_and_update(const struct rte_hash *h, void *data, const void *key, struct rte_hash_bucket *bkt, hash_sig_t sig, hash_sig_t alt_hash) @@ -499,8 +501,13 @@ search_and_update(const struct rte_hash *h, void *data, const void *key, k = (struct rte_hash_key *) ((char *)keys + bkt->key_idx[i] * h->key_entry_size); if (rte_hash_cmp_eq(key, k->key, h) == 0) { - /* Update data */ - k->pdata = data; + /* 'pdata' acts as the synchronization point + * when an existing hash entry is updated. + * Key is not updated in this case. + */ + __atomic_store_n(&k->pdata, + data, + __ATOMIC_RELEASE); /* * Return index where key is stored, * subtracting the first dummy index @@ -554,7 +561,15 @@ rte_hash_cuckoo_insert_mw(const struct rte_hash *h, if (likely(prim_bkt->key_idx[i] == EMPTY_SLOT)) { prim_bkt->sig_current[i] = sig; prim_bkt->sig_alt[i] = alt_hash; - prim_bkt->key_idx[i] = new_idx; + /* Key can be of arbitrary length, so it is + * not possible to store it atomically. + * Hence the new key element's memory stores + * (key as well as data) should be complete + * before it is referenced. + */ + __atomic_store_n(&prim_bkt->key_idx[i], + new_idx, + __ATOMIC_RELEASE); break; } } @@ -637,8 +652,10 @@ rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h, prev_bkt->sig_current[prev_slot]; curr_bkt->sig_current[curr_slot] = prev_bkt->sig_alt[prev_slot]; - curr_bkt->key_idx[curr_slot] = - prev_bkt->key_idx[prev_slot]; + /* Release the updated bucket entry */ + __atomic_store_n(&curr_bkt->key_idx[curr_slot], + prev_bkt->key_idx[prev_slot], + __ATOMIC_RELEASE); curr_slot = prev_slot; curr_node = prev_node; @@ -647,7 +664,10 @@ rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h, curr_bkt->sig_current[curr_slot] = sig; curr_bkt->sig_alt[curr_slot] = alt_hash; - curr_bkt->key_idx[curr_slot] = new_idx; + /* Release the new bucket entry */ + __atomic_store_n(&curr_bkt->key_idx[curr_slot], + new_idx, + __ATOMIC_RELEASE); __hash_rw_writer_unlock(h); @@ -778,8 +798,15 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, new_idx = (uint32_t)((uintptr_t) slot_id); /* Copy key */ rte_memcpy(new_k->key, key, h->key_len); - new_k->pdata = data; - + /* Key can be of arbitrary length, so it is not possible to store + * it atomically. Hence the new key element's memory stores + * (key as well as data) should be complete before it is referenced. + * 'pdata' acts as the synchronization point when an existing hash + * entry is updated. + */ + __atomic_store_n(&new_k->pdata, + data, + __ATOMIC_RELEASE); /* Find an empty slot and insert */ ret = rte_hash_cuckoo_insert_mw(h, prim_bkt, sec_bkt, key, data, @@ -865,21 +892,27 @@ search_one_bucket(const struct rte_hash *h, const void *key, hash_sig_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++) { - if (bkt->sig_current[i] == sig && - bkt->key_idx[i] != EMPTY_SLOT) { + key_idx = __atomic_load_n(&bkt->key_idx[i], + __ATOMIC_ACQUIRE); + if (bkt->sig_current[i] == sig && key_idx != EMPTY_SLOT) { k = (struct rte_hash_key *) ((char *)keys + - bkt->key_idx[i] * h->key_entry_size); + key_idx * h->key_entry_size); + pdata = __atomic_load_n(&k->pdata, + __ATOMIC_ACQUIRE); + if (rte_hash_cmp_eq(key, k->key, h) == 0) { if (data != NULL) - *data = k->pdata; + *data = pdata; /* * Return index where key is stored, * subtracting the first dummy index */ - return bkt->key_idx[i] - 1; + return key_idx - 1; } } } @@ -980,31 +1013,36 @@ remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i) } } -/* Search one bucket and remove the matched key */ +/* Search one bucket and remove the matched key. + * Writer is expected to hold the lock while calling this + * function. + */ static inline int32_t search_and_remove(const struct rte_hash *h, const void *key, struct rte_hash_bucket *bkt, hash_sig_t sig) { struct rte_hash_key *k, *keys = h->key_store; unsigned int i; - int32_t ret; + uint32_t key_idx; /* Check if key is in primary location */ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { - if (bkt->sig_current[i] == sig && - bkt->key_idx[i] != EMPTY_SLOT) { + key_idx = __atomic_load_n(&bkt->key_idx[i], + __ATOMIC_ACQUIRE); + if (bkt->sig_current[i] == sig && key_idx != EMPTY_SLOT) { k = (struct rte_hash_key *) ((char *)keys + - bkt->key_idx[i] * h->key_entry_size); + key_idx * h->key_entry_size); if (rte_hash_cmp_eq(key, k->key, h) == 0) { remove_entry(h, bkt, i); + __atomic_store_n(&bkt->key_idx[i], + EMPTY_SLOT, + __ATOMIC_RELEASE); /* * Return index where key is stored, * subtracting the first dummy index */ - ret = bkt->key_idx[i] - 1; - bkt->key_idx[i] = EMPTY_SLOT; - return ret; + return key_idx - 1; } } } @@ -1151,6 +1189,7 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, const struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX]; uint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0}; uint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0}; + void *pdata[RTE_HASH_LOOKUP_BULK_MAX]; /* Prefetch first keys */ for (i = 0; i < PREFETCH_OFFSET && i < num_keys; i++) @@ -1220,18 +1259,25 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, while (prim_hitmask[i]) { uint32_t hit_index = __builtin_ctzl(prim_hitmask[i]); - uint32_t key_idx = primary_bkt[i]->key_idx[hit_index]; + 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 (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] = key_slot->pdata; + data[i] = pdata[i]; hits |= 1ULL << i; positions[i] = key_idx - 1; @@ -1243,11 +1289,19 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, while (sec_hitmask[i]) { uint32_t hit_index = __builtin_ctzl(sec_hitmask[i]); - uint32_t key_idx = secondary_bkt[i]->key_idx[hit_index]; + 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 @@ -1255,7 +1309,7 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, if (!!key_idx & !rte_hash_cmp_eq(key_slot->key, keys[i], h)) { if (data != NULL) - data[i] = key_slot->pdata; + data[i] = pdata[i]; hits |= 1ULL << i; positions[i] = key_idx - 1; @@ -1320,7 +1374,8 @@ rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32 idx = *next % RTE_HASH_BUCKET_ENTRIES; /* If current position is empty, go to the next one */ - while (h->buckets[bucket_idx].key_idx[idx] == EMPTY_SLOT) { + while ((position = __atomic_load_n(&h->buckets[bucket_idx].key_idx[idx], + __ATOMIC_ACQUIRE)) == EMPTY_SLOT) { (*next)++; /* End of table */ if (*next == total_entries) @@ -1329,8 +1384,6 @@ rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32 idx = *next % RTE_HASH_BUCKET_ENTRIES; } __hash_rw_reader_lock(h); - /* Get position of entry in key table */ - position = h->buckets[bucket_idx].key_idx[idx]; next_key = (struct rte_hash_key *) ((char *)h->key_store + position * h->key_entry_size); /* Return key and data */ From patchwork Thu Sep 6 17:12:17 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Honnappa Nagarahalli X-Patchwork-Id: 146118 Delivered-To: patch@linaro.org Received: by 2002:a2e:1648:0:0:0:0:0 with SMTP id 8-v6csp126506ljw; Thu, 6 Sep 2018 10:12:59 -0700 (PDT) X-Google-Smtp-Source: ANB0VdYR8CdRcDCPzpmWrVc6+jZntDJKfpQUq9AWyuP/WPIJaBjpvtdPW86qOOJn6WspIZUsxw/8 X-Received: by 2002:a5d:4a87:: with SMTP id o7-v6mr2945047wrq.132.1536253979289; Thu, 06 Sep 2018 10:12:59 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1536253979; cv=none; d=google.com; s=arc-20160816; b=HTUtpE7i97S/Xg5DjVL/9H3tNAefApli9syaOHYB6ZQ+eR3zuZpHc60kFlUk2hCdmS vMF4Raatpc00vBtuqudt+CefjyGlQIu/JI0GnXGDeJCQAr2SYuBhyw++OUjNXxKh1zrE 9fzoz8DXuG2VAIIt9nl99UDKOYU7Fug+BrZDUQcq4Hd6MqZoA+5fx30FAPTOtMC9PAwB msc9kVZWy2xY+MPEDJQOlTYn6fgwptSeZqjqYA2Ngujm4BvD8USor/kQ1Ywo6hq7UFuX hqRXBq03F9YSVEYCy+tZJnkGjgw6yGaKU+Fk+iE27aRU1wp7Y6ez6TNz6THlG3N2iQvX aHTQ== 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=BUt73tXqs1ZE8PhVd0r1QQRvZPE0lgAOOhEidDjiM/I=; b=Pw0jMhDpsqDysEk9DbIB2g4Zo0ZqmD8CwQXx75UmovtN8AJIBHsNbSfWbvGRblILlB AM+QkDXmlgCl8f7qnunXpkK301FVHkkExhjnNwsZyDCY41x606c9SIqFE1B27GLhJEQ4 R4IpfNA95QqFqBKxyOgqXORUn7WMalqHUZjDZIIBmzoLPFE6uTcn8rNsXbRQv+lPAQGA TkGi4CXtzYqxiXACBW3OlAXVaRz1EDy6gJeLafHl/HOhQNQpRkWIjZEHhyVQtu4+GgKk pwrhrGY8eOh3NqF0GMS+FiHwht0UZb8KX+auU4TroRAdg5lvglNs+a3w3uoJsxtyYAJO xI5g== 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 v6-v6si6342783wrf.74.2018.09.06.10.12.59; Thu, 06 Sep 2018 10:12:59 -0700 (PDT) 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 0DABF4CE4; Thu, 6 Sep 2018 19:12:36 +0200 (CEST) Received: from foss.arm.com (usa-sjc-mx-foss1.foss.arm.com [217.140.101.70]) by dpdk.org (Postfix) with ESMTP id 262084CB3 for ; Thu, 6 Sep 2018 19:12:34 +0200 (CEST) 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 863127A9; Thu, 6 Sep 2018 10:12:33 -0700 (PDT) Received: from 2p2660v4-1.austin.arm.com (2p2660v4-1.austin.arm.com [10.118.12.164]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 0FBE33F557; Thu, 6 Sep 2018 10:12:33 -0700 (PDT) From: Honnappa Nagarahalli To: bruce.richardson@intel.com, pablo.de.lara.guarch@intel.com Cc: dev@dpdk.org, honnappa.nagarahalli@dpdk.org, gavin.hu@arm.com, steve.capper@arm.com, ola.liljedahl@arm.com, nd@arm.com, Honnappa Nagarahalli Date: Thu, 6 Sep 2018 12:12:17 -0500 Message-Id: <1536253938-192391-4-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 3/4] hash: fix rw concurrency while moving keys 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" Reader-writer concurrency issue, caused by moving the keys to their alternative locations during key insert, is solved by introducing a global counter(tbl_chng_cnt) indicating a change in table. Signed-off-by: Honnappa Nagarahalli Reviewed-by: Gavin Hu Reviewed-by: Ola Liljedahl Reviewed-by: Steve Capper --- lib/librte_hash/rte_cuckoo_hash.c | 307 +++++++++++++++++++++++++------------- lib/librte_hash/rte_cuckoo_hash.h | 2 + lib/librte_hash/rte_hash.h | 8 +- 3 files changed, 206 insertions(+), 111 deletions(-) -- 2.7.4 diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index 2d89158..1e4a8d4 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -256,6 +256,7 @@ rte_hash_create(const struct rte_hash_parameters *params) #endif /* Setup hash context */ snprintf(h->name, sizeof(h->name), "%s", params->name); + h->tbl_chng_cnt = 0; h->entries = params->entries; h->key_len = params->key_len; h->key_entry_size = key_entry_size; @@ -588,7 +589,7 @@ rte_hash_cuckoo_insert_mw(const struct rte_hash *h, * return 0 if succeeds. */ static inline int -rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h, +rte_hash_cuckoo_move_insert_mw(struct rte_hash *h, struct rte_hash_bucket *bkt, struct rte_hash_bucket *alt_bkt, const struct rte_hash_key *key, void *data, @@ -639,11 +640,27 @@ rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h, if (unlikely(&h->buckets[prev_alt_bkt_idx] != curr_bkt)) { /* revert it to empty, otherwise duplicated keys */ - curr_bkt->key_idx[curr_slot] = EMPTY_SLOT; + __atomic_store_n(&curr_bkt->key_idx[curr_slot], + EMPTY_SLOT, + __ATOMIC_RELEASE); __hash_rw_writer_unlock(h); return -1; } + /* Inform the previous move. The current move need + * not be informed now as the current bucket entry + * is present in both primary and secondary. + * Since there is one writer, load acquires on + * tbl_chng_cnt are not required. + */ + __atomic_store_n(&h->tbl_chng_cnt, + h->tbl_chng_cnt + 1, + __ATOMIC_RELEASE); + /* The stores to sig_alt and sig_current should not + * move above the store to tbl_chng_cnt. + */ + __atomic_thread_fence(__ATOMIC_RELEASE); + /* Need to swap current/alt sig to allow later * Cuckoo insert to move elements back to its * primary bucket if available @@ -662,6 +679,20 @@ rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h, curr_bkt = curr_node->bkt; } + /* Inform the previous move. The current move need + * not be informed now as the current bucket entry + * is present in both primary and secondary. + * Since there is one writer, load acquires on + * tbl_chng_cnt are not required. + */ + __atomic_store_n(&h->tbl_chng_cnt, + h->tbl_chng_cnt + 1, + __ATOMIC_RELEASE); + /* The stores to sig_alt and sig_current should not + * move above the store to tbl_chng_cnt. + */ + __atomic_thread_fence(__ATOMIC_RELEASE); + curr_bkt->sig_current[curr_slot] = sig; curr_bkt->sig_alt[curr_slot] = alt_hash; /* Release the new bucket entry */ @@ -680,7 +711,7 @@ rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h, * Cuckoo */ static inline int -rte_hash_cuckoo_make_space_mw(const struct rte_hash *h, +rte_hash_cuckoo_make_space_mw(struct rte_hash *h, struct rte_hash_bucket *bkt, struct rte_hash_bucket *sec_bkt, const struct rte_hash_key *key, void *data, @@ -728,7 +759,7 @@ rte_hash_cuckoo_make_space_mw(const struct rte_hash *h, } static inline int32_t -__rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, +__rte_hash_add_key_with_hash(struct rte_hash *h, const void *key, hash_sig_t sig, void *data) { hash_sig_t alt_hash; @@ -844,7 +875,7 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, } int32_t -rte_hash_add_key_with_hash(const struct rte_hash *h, +rte_hash_add_key_with_hash(struct rte_hash *h, const void *key, hash_sig_t sig) { RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); @@ -852,14 +883,14 @@ rte_hash_add_key_with_hash(const struct rte_hash *h, } int32_t -rte_hash_add_key(const struct rte_hash *h, const void *key) +rte_hash_add_key(struct rte_hash *h, const void *key) { RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), 0); } int -rte_hash_add_key_with_hash_data(const struct rte_hash *h, +rte_hash_add_key_with_hash_data(struct rte_hash *h, const void *key, hash_sig_t sig, void *data) { int ret; @@ -873,7 +904,7 @@ rte_hash_add_key_with_hash_data(const struct rte_hash *h, } int -rte_hash_add_key_data(const struct rte_hash *h, const void *key, void *data) +rte_hash_add_key_data(struct rte_hash *h, const void *key, void *data) { int ret; @@ -926,30 +957,56 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, uint32_t bucket_idx; hash_sig_t alt_hash; struct rte_hash_bucket *bkt; + uint32_t cnt_b, cnt_a; int ret; - bucket_idx = sig & h->bucket_bitmask; - bkt = &h->buckets[bucket_idx]; - __hash_rw_reader_lock(h); - /* Check if key is in primary location */ - ret = search_one_bucket(h, key, sig, data, bkt); - if (ret != -1) { - __hash_rw_reader_unlock(h); - return ret; - } - /* Calculate secondary hash */ - alt_hash = rte_hash_secondary_hash(sig); - bucket_idx = alt_hash & h->bucket_bitmask; - bkt = &h->buckets[bucket_idx]; + 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); + + bucket_idx = sig & h->bucket_bitmask; + bkt = &h->buckets[bucket_idx]; + + /* Check if key is in primary location */ + ret = search_one_bucket(h, key, sig, data, bkt); + if (ret != -1) { + __hash_rw_reader_unlock(h); + return ret; + } + /* Calculate secondary hash */ + alt_hash = rte_hash_secondary_hash(sig); + bucket_idx = alt_hash & h->bucket_bitmask; + bkt = &h->buckets[bucket_idx]; + + /* Check if key is in secondary location */ + ret = search_one_bucket(h, key, alt_hash, data, 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); - /* Check if key is in secondary location */ - ret = search_one_bucket(h, key, alt_hash, data, bkt); - if (ret != -1) { - __hash_rw_reader_unlock(h); - return ret; - } __hash_rw_reader_unlock(h); return -ENOENT; } @@ -1190,6 +1247,7 @@ __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}; 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++) @@ -1225,102 +1283,137 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, } __hash_rw_reader_lock(h); - /* Compare signatures and prefetch key slot of first hit */ - for (i = 0; i < num_keys; i++) { - compare_signatures(&prim_hitmask[i], &sec_hitmask[i], + 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], prim_hash[i], sec_hash[i], h->sig_cmp_fn); - if (prim_hitmask[i]) { - uint32_t first_hit = __builtin_ctzl(prim_hitmask[i]); - 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 (prim_hitmask[i]) { + uint32_t first_hit = + __builtin_ctzl(prim_hitmask[i]); + 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]); - 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 (sec_hitmask[i]) { + uint32_t first_hit = + __builtin_ctzl(sec_hitmask[i]); + 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 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]); + /* 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]); - 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 (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]; + 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); - hits |= 1ULL << i; - positions[i] = key_idx - 1; - goto next_key; + 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]; + + hits |= 1ULL << i; + positions[i] = key_idx - 1; + goto next_key; + } + prim_hitmask[i] &= ~(1 << (hit_index)); } - prim_hitmask[i] &= ~(1 << (hit_index)); - } - while (sec_hitmask[i]) { - uint32_t hit_index = __builtin_ctzl(sec_hitmask[i]); + while (sec_hitmask[i]) { + uint32_t hit_index = + __builtin_ctzl(sec_hitmask[i]); - 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 - */ + 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 & !rte_hash_cmp_eq(key_slot->key, keys[i], h)) { - if (data != NULL) - data[i] = pdata[i]; + 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 + */ - hits |= 1ULL << i; - positions[i] = key_idx - 1; - goto next_key; + if (!!key_idx & + !rte_hash_cmp_eq( + key_slot->key, keys[i], h)) { + if (data != NULL) + data[i] = pdata[i]; + + hits |= 1ULL << i; + positions[i] = key_idx - 1; + goto next_key; + } + sec_hitmask[i] &= ~(1 << (hit_index)); } - sec_hitmask[i] &= ~(1 << (hit_index)); - } next_key: - continue; - } + continue; + } + + /* 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); __hash_rw_reader_unlock(h); diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h index b0c7ef9..5ce864c 100644 --- a/lib/librte_hash/rte_cuckoo_hash.h +++ b/lib/librte_hash/rte_cuckoo_hash.h @@ -186,6 +186,8 @@ struct rte_hash { * to the key table. */ rte_rwlock_t *readwrite_lock; /**< Read-write lock thread-safety. */ + uint32_t tbl_chng_cnt; + /**< Indicates if the hash table changed from last read. */ } __rte_cache_aligned; struct queue_node { diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h index 9e7d931..05e024b 100644 --- a/lib/librte_hash/rte_hash.h +++ b/lib/librte_hash/rte_hash.h @@ -156,7 +156,7 @@ rte_hash_count(const struct rte_hash *h); * - -ENOSPC if there is no space in the hash for this key. */ int -rte_hash_add_key_data(const struct rte_hash *h, const void *key, void *data); +rte_hash_add_key_data(struct rte_hash *h, const void *key, void *data); /** * Add a key-value pair with a pre-computed hash value @@ -180,7 +180,7 @@ rte_hash_add_key_data(const struct rte_hash *h, const void *key, void *data); * - -ENOSPC if there is no space in the hash for this key. */ int32_t -rte_hash_add_key_with_hash_data(const struct rte_hash *h, const void *key, +rte_hash_add_key_with_hash_data(struct rte_hash *h, const void *key, hash_sig_t sig, void *data); /** @@ -200,7 +200,7 @@ rte_hash_add_key_with_hash_data(const struct rte_hash *h, const void *key, * array of user data. This value is unique for this key. */ int32_t -rte_hash_add_key(const struct rte_hash *h, const void *key); +rte_hash_add_key(struct rte_hash *h, const void *key); /** * Add a key to an existing hash table. @@ -222,7 +222,7 @@ rte_hash_add_key(const struct rte_hash *h, const void *key); * array of user data. This value is unique for this key. */ int32_t -rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig); +rte_hash_add_key_with_hash(struct rte_hash *h, const void *key, hash_sig_t sig); /** * Remove a key from an existing hash table. From patchwork Thu Sep 6 17:12:18 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Honnappa Nagarahalli X-Patchwork-Id: 146119 Delivered-To: patch@linaro.org Received: by 2002:a2e:1648:0:0:0:0:0 with SMTP id 8-v6csp126797ljw; Thu, 6 Sep 2018 10:13:14 -0700 (PDT) X-Google-Smtp-Source: ANB0VdYDGwYqEw5Qiba/Z68AHp2b9nyM3Nvj8+rOhSJghp6pg/rSMIqkYTMLNyRo+CvALgVlYI7Y X-Received: by 2002:adf:ac6a:: with SMTP id v97-v6mr2957067wrc.7.1536253994506; Thu, 06 Sep 2018 10:13:14 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1536253994; cv=none; d=google.com; s=arc-20160816; b=Y0e8Qv/glZFK94OdI3yB+3H65EBxtD++7nJd0+ZQiisLbpQJIcBrMiv9XMoB/drcGY RUWYMrcVbj/FvvqEk64fqi0sq7fsIJPRg0AUsiHjTgoW6/6zen9gsNr3Zwi0D0yPZT3o msisuXnGqc85i5cVLtz47Vc9J3fA7CffvIYuLQxBIwbO+6MAs6dXi5CJfk6gOxs9GU2D DUkW219ozMS747n+PnhwH7ktpgog+DbheSeKds9Bp8IwsbvJruerR6rhC6zKojMPHum4 k3Nr8ftpO9VYXiwY8ImLeha7Ncu4AZ7wyHbI30ybiMGLKVT8HdTB/HerNupCi2xrp3wQ KkrA== 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=W6QeF1oK53CUIL7vtGza9tYGYNnJKGlNz4hKUAthlVk=; b=QJfr9LRyD8WEs2W47MK3swfGj9zhIOVo5Z7SH6n//a6J2fU9xLEM/eIwCS4UP6Bngf F729rTmY8QgOGfXqiXCXdeReDWbM7vTgqPrFRSdm0ufGelXpcIQmfJoOvpNxOzx4TAXA nazBDxjFh92JRH/XeHbOv4Qh3FvhjleZB9Wfpr1mBrVu/jC/4wDYhYYEffgeF5fsSjpg 5u93PyQlS0Wc4Abt7SA9/SXaHZ0Jw/GOz6VrA4CXUoz2e2OaiI80i7MpFRFucJO7l8S/ ry7dvxORdXZWKZlIttgey6NptGiToCNcVQJCb62T0YsCKf8GtpwcPeE9aZ0hFGVk933B 3wdg== 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 d12-v6si5482405wrn.105.2018.09.06.10.13.14; Thu, 06 Sep 2018 10:13:14 -0700 (PDT) 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 BD344532C; Thu, 6 Sep 2018 19:12:37 +0200 (CEST) Received: from foss.arm.com (foss.arm.com [217.140.101.70]) by dpdk.org (Postfix) with ESMTP id CB1DE4CBB for ; Thu, 6 Sep 2018 19:12:35 +0200 (CEST) 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 490FD7A9; Thu, 6 Sep 2018 10:12:35 -0700 (PDT) Received: from 2p2660v4-1.austin.arm.com (2p2660v4-1.austin.arm.com [10.118.12.164]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id CE8D63F557; Thu, 6 Sep 2018 10:12:34 -0700 (PDT) From: Honnappa Nagarahalli To: bruce.richardson@intel.com, pablo.de.lara.guarch@intel.com Cc: dev@dpdk.org, honnappa.nagarahalli@dpdk.org, gavin.hu@arm.com, steve.capper@arm.com, ola.liljedahl@arm.com, nd@arm.com, Honnappa Nagarahalli Date: Thu, 6 Sep 2018 12:12:18 -0500 Message-Id: <1536253938-192391-5-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 4/4] hash: enable lock-free reader-writer concurrency 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" Add the flag to enable reader-writer concurrency during run time. The rte_hash_del_xxx APIs do not free the keystore element when this flag is enabled. Hence a new API, rte_hash_free_key_with_position, to free the key store element is added. Signed-off-by: Honnappa Nagarahalli Reviewed-by: Gavin Hu Reviewed-by: Ola Liljedahl Reviewed-by: Steve Capper --- lib/librte_hash/rte_cuckoo_hash.c | 105 ++++++++++++++++++++++++++--------- lib/librte_hash/rte_cuckoo_hash.h | 2 + lib/librte_hash/rte_hash.h | 55 ++++++++++++++++++ lib/librte_hash/rte_hash_version.map | 7 +++ 4 files changed, 142 insertions(+), 27 deletions(-) -- 2.7.4 diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index 1e4a8d4..bf51a73 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -93,6 +93,7 @@ rte_hash_create(const struct rte_hash_parameters *params) unsigned i; unsigned int hw_trans_mem_support = 0, multi_writer_support = 0; unsigned int readwrite_concur_support = 0; + unsigned int readwrite_concur_lf_support = 0; rte_hash_function default_hash_func = (rte_hash_function)rte_jhash; @@ -124,6 +125,9 @@ rte_hash_create(const struct rte_hash_parameters *params) multi_writer_support = 1; } + if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF) + readwrite_concur_lf_support = 1; + /* Store all keys and leave the first entry as a dummy entry for lookup_bulk */ if (multi_writer_support) /* @@ -272,6 +276,7 @@ rte_hash_create(const struct rte_hash_parameters *params) h->hw_trans_mem_support = hw_trans_mem_support; h->multi_writer_support = multi_writer_support; h->readwrite_concur_support = readwrite_concur_support; + h->readwrite_concur_lf_support = readwrite_concur_lf_support; #if defined(RTE_ARCH_X86) if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX2)) @@ -647,19 +652,21 @@ rte_hash_cuckoo_move_insert_mw(struct rte_hash *h, return -1; } - /* Inform the previous move. The current move need - * not be informed now as the current bucket entry - * is present in both primary and secondary. - * Since there is one writer, load acquires on - * tbl_chng_cnt are not required. - */ - __atomic_store_n(&h->tbl_chng_cnt, - h->tbl_chng_cnt + 1, - __ATOMIC_RELEASE); - /* The stores to sig_alt and sig_current should not - * move above the store to tbl_chng_cnt. - */ - __atomic_thread_fence(__ATOMIC_RELEASE); + if (h->readwrite_concur_lf_support) { + /* Inform the previous move. The current move need + * not be informed now as the current bucket entry + * is present in both primary and secondary. + * Since there is one writer, load acquires on + * tbl_chng_cnt are not required. + */ + __atomic_store_n(&h->tbl_chng_cnt, + h->tbl_chng_cnt + 1, + __ATOMIC_RELEASE); + /* The stores to sig_alt and sig_current should not + * move above the store to tbl_chng_cnt. + */ + __atomic_thread_fence(__ATOMIC_RELEASE); + } /* Need to swap current/alt sig to allow later * Cuckoo insert to move elements back to its @@ -679,19 +686,21 @@ rte_hash_cuckoo_move_insert_mw(struct rte_hash *h, curr_bkt = curr_node->bkt; } - /* Inform the previous move. The current move need - * not be informed now as the current bucket entry - * is present in both primary and secondary. - * Since there is one writer, load acquires on - * tbl_chng_cnt are not required. - */ - __atomic_store_n(&h->tbl_chng_cnt, - h->tbl_chng_cnt + 1, - __ATOMIC_RELEASE); - /* The stores to sig_alt and sig_current should not - * move above the store to tbl_chng_cnt. - */ - __atomic_thread_fence(__ATOMIC_RELEASE); + if (h->readwrite_concur_lf_support) { + /* Inform the previous move. The current move need + * not be informed now as the current bucket entry + * is present in both primary and secondary. + * Since there is one writer, load acquires on + * tbl_chng_cnt are not required. + */ + __atomic_store_n(&h->tbl_chng_cnt, + h->tbl_chng_cnt + 1, + __ATOMIC_RELEASE); + /* The stores to sig_alt and sig_current should not + * move above the store to tbl_chng_cnt. + */ + __atomic_thread_fence(__ATOMIC_RELEASE); + } curr_bkt->sig_current[curr_slot] = sig; curr_bkt->sig_alt[curr_slot] = alt_hash; @@ -1090,7 +1099,12 @@ search_and_remove(const struct rte_hash *h, const void *key, k = (struct rte_hash_key *) ((char *)keys + key_idx * h->key_entry_size); if (rte_hash_cmp_eq(key, k->key, h) == 0) { - remove_entry(h, bkt, i); + /* Do not free the key store element if + * lock-free concurrency is enabled as + * readers might still be using it. + */ + if (!h->readwrite_concur_lf_support) + remove_entry(h, bkt, i); __atomic_store_n(&bkt->key_idx[i], EMPTY_SLOT, @@ -1177,6 +1191,43 @@ rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position, return 0; } +int __rte_experimental +rte_hash_free_key_with_position(const struct rte_hash *h, + const int32_t position) +{ + RETURN_IF_TRUE(((h == NULL) || (position == EMPTY_SLOT)), -EINVAL); + + unsigned int lcore_id, n_slots; + struct lcore_cache *cached_free_slots; + const int32_t total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES; + + /* Out of bounds */ + if (position >= total_entries) + return -EINVAL; + + if (h->multi_writer_support) { + lcore_id = rte_lcore_id(); + cached_free_slots = &h->local_free_slots[lcore_id]; + /* Cache full, need to free it. */ + if (cached_free_slots->len == LCORE_CACHE_SIZE) { + /* Need to enqueue the free slots in global ring. */ + n_slots = rte_ring_mp_enqueue_burst(h->free_slots, + cached_free_slots->objs, + LCORE_CACHE_SIZE, NULL); + cached_free_slots->len -= n_slots; + } + /* Put index of new free slot in cache. */ + cached_free_slots->objs[cached_free_slots->len] = + (void *)((uintptr_t)position); + cached_free_slots->len++; + } else { + rte_ring_sp_enqueue(h->free_slots, + (void *)((uintptr_t)position)); + } + + return 0; +} + static inline void compare_signatures(uint32_t *prim_hash_matches, uint32_t *sec_hash_matches, const struct rte_hash_bucket *prim_bkt, diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h index 5ce864c..08d67b8 100644 --- a/lib/librte_hash/rte_cuckoo_hash.h +++ b/lib/librte_hash/rte_cuckoo_hash.h @@ -168,6 +168,8 @@ struct rte_hash { /**< If multi-writer support is enabled. */ uint8_t readwrite_concur_support; /**< If read-write concurrency support is enabled */ + uint8_t readwrite_concur_lf_support; + /**< If read-write concurrency lock free support is enabled */ rte_hash_function hash_func; /**< Function used to calculate hash. */ uint32_t hash_func_init_val; /**< Init value used by hash_func. */ rte_hash_cmp_eq_t rte_hash_custom_cmp_eq; diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h index 05e024b..7d7372e 100644 --- a/lib/librte_hash/rte_hash.h +++ b/lib/librte_hash/rte_hash.h @@ -14,6 +14,8 @@ #include #include +#include + #ifdef __cplusplus extern "C" { #endif @@ -37,6 +39,9 @@ extern "C" { /** Flag to support reader writer concurrency */ #define RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY 0x04 +/** Flag to support lock free reader writer concurrency */ +#define RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF 0x08 + /** Signature of key that is stored internally. */ typedef uint32_t hash_sig_t; @@ -143,6 +148,11 @@ rte_hash_count(const struct rte_hash *h); * and should only be called from one thread by default. * Thread safety can be enabled by setting flag during * table creation. + * When lock free reader writer concurrency is enabled, + * if this API is called to update an existing entry, + * the application should free any memory allocated for + * previous 'data' only after all the readers have stopped + * using previous 'data'. * * @param h * Hash table to add the key to. @@ -165,6 +175,11 @@ rte_hash_add_key_data(struct rte_hash *h, const void *key, void *data); * and should only be called from one thread by default. * Thread safety can be enabled by setting flag during * table creation. + * When lock free reader writer concurrency is enabled, + * if this API is called to update an existing entry, + * the application should free any memory allocated for + * previous 'data' only after all the readers have stopped + * using previous 'data'. * * @param h * Hash table to add the key to. @@ -230,6 +245,12 @@ rte_hash_add_key_with_hash(struct rte_hash *h, const void *key, hash_sig_t sig); * and should only be called from one thread by default. * Thread safety can be enabled by setting flag during * table creation. + * If lock free reader writer concurrency is enabled, + * the hash library's internal memory for the deleted + * key is not freed. It should be freed by calling + * rte_hash_free_key_with_position API after all + * the readers have stopped using the hash entry + * corresponding to this key. * * @param h * Hash table to remove the key from. @@ -241,6 +262,8 @@ rte_hash_add_key_with_hash(struct rte_hash *h, const void *key, hash_sig_t sig); * - A positive value that can be used by the caller as an offset into an * array of user data. This value is unique for this key, and is the same * value that was returned when the key was added. + * When lock free concurrency is enabled, this value should be used + * while calling the rte_hash_free_key_with_position API. */ int32_t rte_hash_del_key(const struct rte_hash *h, const void *key); @@ -251,6 +274,12 @@ rte_hash_del_key(const struct rte_hash *h, const void *key); * and should only be called from one thread by default. * Thread safety can be enabled by setting flag during * table creation. + * If lock free reader writer concurrency is enabled, + * the hash library's internal memory for the deleted + * key is not freed. It should be freed by calling + * rte_hash_free_key_with_position API after all + * the readers have stopped using the hash entry + * corresponding to this key. * * @param h * Hash table to remove the key from. @@ -264,6 +293,8 @@ rte_hash_del_key(const struct rte_hash *h, const void *key); * - A positive value that can be used by the caller as an offset into an * array of user data. This value is unique for this key, and is the same * value that was returned when the key was added. + * When lock free concurrency is enabled, this value should be used + * while calling the rte_hash_free_key_with_position API. */ int32_t rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig); @@ -290,6 +321,30 @@ rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position, void **key); /** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice + * + * Free hash library's internal memory given the position + * of the key. This operation is not multi-thread safe and should + * only be called from one thread by default. Thread safety + * can be enabled by setting flag during table creation. + * If lock free reader writer concurrency is enabled, + * the hash library's internal memory must be freed using this API + * after the key is deleted using rte_hash_del_key_xxx API. + * + * @param h + * Hash table to get the key from. + * @param position + * Position returned when the key was deleted. + * @return + * - 0 if freed successfully + * - -EINVAL if the parameters are invalid. + */ +int __rte_experimental +rte_hash_free_key_with_position(const struct rte_hash *h, + const int32_t position); + +/** * Find a key-value pair in the hash table. * This operation is multi-thread safe with regarding to other lookup threads. * Read-write concurrency can be enabled by setting flag during diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_version.map index e216ac8..734ae28 100644 --- a/lib/librte_hash/rte_hash_version.map +++ b/lib/librte_hash/rte_hash_version.map @@ -53,3 +53,10 @@ DPDK_18.08 { rte_hash_count; } DPDK_16.07; + +EXPERIMENTAL { + global: + + rte_hash_free_key_with_position; + +};