From patchwork Fri Oct 12 06:31:57 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Honnappa Nagarahalli X-Patchwork-Id: 148721 Delivered-To: patch@linaro.org Received: by 2002:a2e:8595:0:0:0:0:0 with SMTP id b21-v6csp368493lji; Thu, 11 Oct 2018 23:33:00 -0700 (PDT) X-Google-Smtp-Source: ACcGV61j3Cu+3PJVpmVhkz8owcRvpAiJDUFmblp1GdljU6rcOYbNtl2GzidS4oYihIpWM3Cn02vg X-Received: by 2002:a50:adca:: with SMTP id b10-v6mr7184866edd.184.1539325979972; Thu, 11 Oct 2018 23:32:59 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1539325979; cv=none; d=google.com; s=arc-20160816; b=ejIEqsNGlB28jxD+oP73q3nfx0c3QGF1fc+nXBDrXfgPtbTuIq97vxrMe8o8ZLOOuU SGey65E2tWp7w6LRHw3k+v6MTNYH+opOlqrBR/2F6hS4gKKKeRy1MyLe1kIuMdN1f/Sg vtKZHXnV1r1S5pi9I+b7xPCyRjuKazqbQ8A7JlguYfWcvAUoMkfVJWSYp+5y40ks1Lfm pGzV8OotxiZkFEeFavHzf4FLM1r+4Z/Z0cEh+sV4feIhRNxHGa/yboz/J12UL3CzX/Se 5kt6yJZd9lURpHkrTW8HtcqyvXnsUB5FL5gv67b9h3+ynW0689Q17oZoUbOvbKP2JzD2 qKGA== 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=Sl8brzFe7x04jwc/Ki4TuHaZ/1aF1Ncnp+Ww9Go+RNI=; b=Xi6UHE/ngtjLq5cgPE+T1zzsotb1xL6wQ/P3l7puIAuOnrxJxiIQ7ixjcwqJAZMhpt G+vf0PX/cZRFz/zZJziZ4TEu9iuUmKso4Nv+JJvTe1UjlkOLKdxNiCEFrrF0LMPxZofB RBc1QbP+oMV+t3aaX0u9npBKB1N2QOEOP93lYXM+aNJnBSuu1HUH0b2mZuXUuo6L7TVq vlOK1Dw68Y9fwCgtb+CnvuJCItA7n4cRgKPm0VyAiy3KpIyk5HpeTNBSyxKrvZo77UFs DRnsljA3PrbdHS/AFBRKoMMrTWsjynEM8/U72fFhGi/A025azaLgk4g8kZQdOzsyAPvB nGrA== 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 r17-v6si471211edc.269.2018.10.11.23.32.59; Thu, 11 Oct 2018 23:32: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 BFD8C1B14F; Fri, 12 Oct 2018 08:32:24 +0200 (CEST) Received: from foss.arm.com (foss.arm.com [217.140.101.70]) by dpdk.org (Postfix) with ESMTP id 6E9F01B10D for ; Fri, 12 Oct 2018 08:32:14 +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 DABE315BF; Thu, 11 Oct 2018 23:32:13 -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 7544D3F5B3; Thu, 11 Oct 2018 23:32:13 -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, gavin.hu@arm.com, nd@arm.com Date: Fri, 12 Oct 2018 01:31:57 -0500 Message-Id: <1539325918-125438-7-git-send-email-honnappa.nagarahalli@arm.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1539325918-125438-1-git-send-email-honnappa.nagarahalli@arm.com> References: <1539325918-125438-1-git-send-email-honnappa.nagarahalli@arm.com> Subject: [dpdk-dev] [PATCH v3 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 | 82 ++++++++++++++++++++++++------------ 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, 114 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 262162c..4622ece 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -143,6 +143,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; @@ -162,6 +163,24 @@ rte_hash_create(const struct rte_hash_parameters *params) return NULL; } + /* Validate correct usage of extra options */ + if ((params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY) && + (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF)) { + rte_errno = EINVAL; + RTE_LOG(ERR, HASH, "rte_hash_create choose rw concurrency or " + "rw concurrency lock free\n"); + return NULL; + } + + if ((params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF) && + (params->extra_flag & RTE_HASH_EXTRA_FLAGS_EXT_TABLE)) { + rte_errno = EINVAL; + RTE_LOG(ERR, HASH, "rte_hash_create extendable bucket " + "feature not supported with rw concurrency " + "lock free\n"); + return NULL; + } + /* Check extra flags field to check extra options. */ if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT) hw_trans_mem_support = 1; @@ -182,6 +201,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) /* @@ -378,6 +403,7 @@ rte_hash_create(const struct rte_hash_parameters *params) h->ext_table_support = ext_table_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_SSE2)) @@ -765,19 +791,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 @@ -795,19 +823,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; /* Release the new bucket entry */ diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h index 728cd17..0c23957 100644 --- a/lib/librte_hash/rte_cuckoo_hash.h +++ b/lib/librte_hash/rte_cuckoo_hash.h @@ -175,6 +175,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 3e5d336..22def5e 100644 --- a/lib/librte_hash/rte_hash.h +++ b/lib/librte_hash/rte_hash.h @@ -44,9 +44,18 @@ 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 0x10 +/** Flag to support lock free reader writer concurrency. Writer can be + * single writer/multi writer. + * Currently, extended bucket table feature is not supported with + * this feature. + */ +#define RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF 0x20 + /** * The type of hash value of a key. * It should be a value of at least 32bit with fully random pattern. @@ -132,7 +141,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 */ @@ -156,6 +169,10 @@ 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. + * 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. * * @param h * Hash table to add the key to. @@ -178,6 +195,10 @@ 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. + * 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. * * @param h * Hash table to add the key to. @@ -243,10 +264,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. @@ -258,6 +284,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); @@ -268,10 +296,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. @@ -285,6 +318,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); @@ -318,10 +353,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; + +};