From patchwork Thu Oct 11 04:59:31 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Honnappa Nagarahalli X-Patchwork-Id: 148603 Delivered-To: patch@linaro.org Received: by 2002:a2e:8595:0:0:0:0:0 with SMTP id b21-v6csp1682771lji; Wed, 10 Oct 2018 22:00:38 -0700 (PDT) X-Google-Smtp-Source: ACcGV62UfNnsCzD1XaA+rqXjjvWrk2JTYa/gBOzbFubSa7bp5XREZfwBOwWNOB/36Mb+g0+VdZ4z X-Received: by 2002:a17:906:1f87:: with SMTP id t7-v6mr392287ejr.153.1539234038061; Wed, 10 Oct 2018 22:00:38 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1539234038; cv=none; d=google.com; s=arc-20160816; b=SR8x2ssPSd6kAnMGbolhPI68EplEST7iKsB6USFxilTMgSp2Hlskv6FcAgldU/L164 V7PzLHTi8Yfku57eT8G9JZ1U6Citph4Be0TU7GRcWevOnmA3evv2z7bTqjml2sorulUc aojZBmIRSaRKBPr7cDkluaZ3edk1Dj3m6tK89WguPRtbFR1miGTv6x7kJAAHosMasN5C PYqaY/3p2B2xYhqFWT9b4f5J2lpzVwgneSt3mnXXsKUOXtabnM3O3uwd4s613K5sEIFk rE+V1idRHGH9jl4pYK6CBxzIz8Khlrygj5EcoBQvskpoFAtHnUfiUjmxTKMSmVCCnKoP I3rg== 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=VTQtFG2ZfNeofK2+EYkGszAcCpW3dpharGrG2qcv2yg=; b=qXZ8CEZrfxy7ICRtUFXSvCQ0xnP/MaUqVXdDCT8jPDEJS1hbdMz4ylZfKbozH81mCY ReVi+ZzwPBM/oDAAwyXWZSVrcFcX08jBYRSndvTZJVTdo2tGiRyhBvln289PZHT4gjgP lMnGXxRK+vxkKJkBWomzfBl+TSf8UnBg2HKL6PwuMxo9BeGIo4EutfVUe2OGtETR3h8g hSUKjxhTmncRFRmWytKm31vAdfKmp/YPEgX3KHgWDhpr5fFBz7WujRSsUKMFf1YerU1i REwAi/Z+CEZ/GX88b54PKH0Z3C0OeyRS2qOJ/VsZrJrUe5Ks/JFMaKQ9Y1SWDzpye9IE 3e6g== 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 i14-v6si15745308ejh.50.2018.10.10.22.00.37; Wed, 10 Oct 2018 22:00:38 -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 6F8961B440; Thu, 11 Oct 2018 06:59:59 +0200 (CEST) Received: from foss.arm.com (foss.arm.com [217.140.101.70]) by dpdk.org (Postfix) with ESMTP id 8ED991B3B8 for ; Thu, 11 Oct 2018 06:59:49 +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 0A1757A9; Wed, 10 Oct 2018 21:59:49 -0700 (PDT) Received: from 2p2660v4-1.austin.arm.com (2p2660v4-1.austin.arm.com [10.118.12.190]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id A1E833F5B3; Wed, 10 Oct 2018 21:59:48 -0700 (PDT) From: Honnappa Nagarahalli To: bruce.richardson@intel.com, pablo.de.lara.guarch@intel.com Cc: dev@dpdk.org, yipeng1.wang@intel.com, honnappa.nagarahalli@arm.com, Dharmik.Thakkar@arm.com, nd@arm.com Date: Wed, 10 Oct 2018 23:59:31 -0500 Message-Id: <1539233972-49860-7-git-send-email-honnappa.nagarahalli@arm.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1539233972-49860-1-git-send-email-honnappa.nagarahalli@arm.com> References: <1539233972-49860-1-git-send-email-honnappa.nagarahalli@arm.com> Subject: [dpdk-dev] [PATCH v2 6/7] 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 Reviewed-by: Yipeng Wang --- lib/librte_hash/rte_cuckoo_hash.c | 64 +++++++++++++++++++++--------------- lib/librte_hash/rte_cuckoo_hash.h | 2 ++ lib/librte_hash/rte_hash.h | 58 +++++++++++++++++++++++++++----- lib/librte_hash/rte_hash_version.map | 7 ++++ 4 files changed, 96 insertions(+), 35 deletions(-) -- 2.7.4 diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index dfd5f2a..1b13dd0 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -97,6 +97,7 @@ rte_hash_create(const struct rte_hash_parameters *params) unsigned int writer_takes_lock = 0; unsigned int recycle_on_del = 1; uint32_t *tbl_chng_cnt = NULL; + unsigned int readwrite_concur_lf_support = 0; rte_hash_function default_hash_func = (rte_hash_function)rte_jhash; @@ -133,6 +134,12 @@ rte_hash_create(const struct rte_hash_parameters *params) if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RECYCLE_ON_DEL) recycle_on_del = 0; + if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF) { + readwrite_concur_lf_support = 1; + /* Disable freeing internal memory/index on delete */ + recycle_on_del = 0; + } + /* Store all keys and leave the first entry as a dummy entry for lookup_bulk */ if (multi_writer_support) /* @@ -292,6 +299,7 @@ rte_hash_create(const struct rte_hash_parameters *params) h->readwrite_concur_support = readwrite_concur_support; h->writer_takes_lock = writer_takes_lock; h->recycle_on_del = recycle_on_del; + h->readwrite_concur_lf_support = readwrite_concur_lf_support; #if defined(RTE_ARCH_X86) if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX2)) @@ -671,19 +679,21 @@ rte_hash_cuckoo_move_insert_mw(const 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 @@ -703,19 +713,21 @@ 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); + 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; diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h index cf50ada..2e05d08 100644 --- a/lib/librte_hash/rte_cuckoo_hash.h +++ b/lib/librte_hash/rte_cuckoo_hash.h @@ -177,6 +177,8 @@ struct rte_hash { * the deleted entry. * This flag is enabled by default. */ + uint8_t readwrite_concur_lf_support; + /**< If read-write concurrency lock free support is enabled */ uint8_t writer_takes_lock; /**< Indicates if the writer threads need to take lock */ rte_hash_function hash_func; /**< Function used to calculate hash. */ diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h index dd59cb0..fb88510 100644 --- a/lib/librte_hash/rte_hash.h +++ b/lib/librte_hash/rte_hash.h @@ -41,9 +41,14 @@ extern "C" { /** Flag to disable freeing of internal memory/indices on hash delete. * Refer to rte_hash_del_xxx APIs for more details. + * This is enabled by default when RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF + * is enabled. */ #define RTE_HASH_EXTRA_FLAGS_RECYCLE_ON_DEL 0x08 +/** Flag to support lock free reader writer concurrency */ +#define RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF 0x10 + /** Signature of key that is stored internally. */ typedef uint32_t hash_sig_t; @@ -126,7 +131,11 @@ void rte_hash_free(struct rte_hash *h); /** - * Reset all hash structure, by zeroing all entries + * Reset all hash structure, by zeroing all entries. + * When RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled, + * it is application's responsibility to make sure that + * none of the readers are referencing the hash table. + * * @param h * Hash table to reset */ @@ -150,6 +159,12 @@ 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 RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled, + * the writer needs to be aware if this API is called to update + * an existing entry. The application should free any memory + * allocated for the existing 'data' only after all the readers + * have stopped referrencing it. RCU mechanisms can be used to + * determine such a state. * * @param h * Hash table to add the key to. @@ -172,6 +187,12 @@ rte_hash_add_key_data(const 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 RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled, + * the writer needs to be aware if this API is called to update + * an existing entry. The application should free any memory + * allocated for the existing 'data' only after all the readers + * have stopped referencing it. RCU mechanisms can be used to + * determine such a state. * * @param h * Hash table to add the key to. @@ -237,10 +258,15 @@ rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t * and should only be called from one thread by default. * Thread safety can be enabled by setting flag during * table creation. - * If RTE_HASH_EXTRA_FLAGS_RECYCLE_ON_DEL is enabled, - * the hash library's internal memory/index will not be freed by this + * If RTE_HASH_EXTRA_FLAGS_RECYCLE_ON_DEL or + * RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled, + * the hash library's internal memory will not be freed by this * API. rte_hash_free_key_with_position API must be called additionally - * to free the internal memory/index associated with the key. + * to free any internal memory associated with the key. + * If RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled, + * rte_hash_free_key_with_position API should be called after all + * the readers have stopped referencing the entry corresponding to + * this key. RCU mechanisms can be used to determine such a state. * * @param h * Hash table to remove the key from. @@ -252,6 +278,8 @@ rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t * - 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); @@ -262,10 +290,15 @@ 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 RTE_HASH_EXTRA_FLAGS_RECYCLE_ON_DEL is enabled, - * the hash library's internal memory/index will not be freed by this + * If RTE_HASH_EXTRA_FLAGS_RECYCLE_ON_DEL or + * RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled, + * the hash library's internal memory will not be freed by this * API. rte_hash_free_key_with_position API must be called additionally - * to free the internal memory/index associated with the key. + * to free any internal memory associated with the key. + * If RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled, + * rte_hash_free_key_with_position API should be called after all + * the readers have stopped referencing the entry corresponding to + * this key. RCU mechanisms can be used to determine such a state. * * @param h * Hash table to remove the key from. @@ -279,6 +312,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); @@ -312,10 +347,15 @@ rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t 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 RTE_HASH_EXTRA_FLAGS_RECYCLE_ON_DEL is enabled, - * the hash library's internal memory/index must be freed using this API + * If RTE_HASH_EXTRA_FLAGS_RECYCLE_ON_DEL or + * RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF 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 APIs. * This API does not validate if the key is already freed. + * If RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF is enabled, + * this API should be called only after all the readers have stopped + * referencing the entry corresponding to this key. RCU mechanisms can + * be used to determine such a state. * * @param h * Hash table to free the key from. 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; + +};