diff mbox series

[v3,6/7] hash: enable lock-free reader-writer concurrency

Message ID 1539325918-125438-7-git-send-email-honnappa.nagarahalli@arm.com
State New
Headers show
Series Address reader-writer concurrency in rte_hash | expand

Commit Message

Honnappa Nagarahalli Oct. 12, 2018, 6:31 a.m. UTC 
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 <honnappa.nagarahalli@arm.com>

Reviewed-by: Gavin Hu <gavin.hu@arm.com>

Reviewed-by: Ola Liljedahl <ola.liljedahl@arm.com>

Reviewed-by: Steve Capper <steve.capper@arm.com>

Reviewed-by: Yipeng Wang <yipeng1.wang@intel.com>

---
 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

Comments

Wang, Yipeng1 Oct. 13, 2018, 2:32 a.m. UTC | #1 
>-----Original Message-----

>From: Honnappa Nagarahalli [mailto:honnappa.nagarahalli@arm.com]

>Sent: Thursday, October 11, 2018 11:32 PM

>To: Richardson, Bruce <bruce.richardson@intel.com>; De Lara Guarch, Pablo <pablo.de.lara.guarch@intel.com>

>Cc: dev@dpdk.org; Wang, Yipeng1 <yipeng1.wang@intel.com>; honnappa.nagarahalli@arm.com; dharmik.thakkar@arm.com;

>gavin.hu@arm.com; nd@arm.com

>Subject: [PATCH v3 6/7] hash: enable lock-free reader-writer concurrency

>

>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 <honnappa.nagarahalli@arm.com>

>Reviewed-by: Gavin Hu <gavin.hu@arm.com>

>Reviewed-by: Ola Liljedahl <ola.liljedahl@arm.com>

>Reviewed-by: Steve Capper <steve.capper@arm.com>

>Reviewed-by: Yipeng Wang <yipeng1.wang@intel.com>

>

>+/** Flag to support lock free reader writer concurrency. Writer can be

>+ * single writer/multi writer.

[Wang, Yipeng] "Writer can be multi-writer when the RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD flag is also set."
>+ * Currently, extended bucket table feature is not supported with

[Wang, Yipeng] "extendable bucket table", I also used wrong name sometimes but please use this one.
>@@ -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.

>  *

[Wang, Yipeng] 
This comment to me is assuming a specific user use case, and not the library's responsibility.
How about a more general description:
If the added key is already in the table, the function will update the data of the key.
In such case, it is the user's responsibility to properly handle the old data if the old data
is still being referenced by other threads.
Please let me know if I understand it wrong.
Honnappa Nagarahalli Oct. 17, 2018, 1:54 p.m. UTC | #2 
> >Subject: [PATCH v3 6/7] hash: enable lock-free reader-writer

> >concurrency

> >

> >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 <honnappa.nagarahalli@arm.com>

> >Reviewed-by: Gavin Hu <gavin.hu@arm.com>

> >Reviewed-by: Ola Liljedahl <ola.liljedahl@arm.com>

> >Reviewed-by: Steve Capper <steve.capper@arm.com>

> >Reviewed-by: Yipeng Wang <yipeng1.wang@intel.com>

> >

> >+/** Flag to support lock free reader writer concurrency. Writer can be

> >+ * single writer/multi writer.

> [Wang, Yipeng] "Writer can be multi-writer when the

> RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD flag is also set."

Agree. What I am trying to say is that lock free reader writer concurrency is support for both single writer or multi writer use cases. This was one of your questions in the earlier version.

> >+ * Currently, extended bucket table feature is not supported with

> [Wang, Yipeng] "extendable bucket table", I also used wrong name sometimes

> but please use this one.

> >@@ -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.

> >  *

> [Wang, Yipeng]

> This comment to me is assuming a specific user use case, and not the library's

> responsibility.

> How about a more general description:

> If the added key is already in the table, the function will update the data of the

> key.

> In such case, it is the user's responsibility to properly handle the old data if

> the old data is still being referenced by other threads.

> Please let me know if I understand it wrong.

Your understanding is correct. I have changed the wordings.
diff mbox series

Patch

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;
+
+};