From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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: , X-List-Received-Date: Fri, 12 Oct 2018 06:32:15 -0000 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(-) 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; + +}; -- 2.7.4