| Message ID | 1536253938-192391-5-git-send-email-honnappa.nagarahalli@arm.com |
|---|---|
| State | New |
| Headers | show |
| Series | Address reader-writer concurrency in rte_hash | expand |
Reply inlined: >-----Original Message----- >From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Honnappa Nagarahalli >Sent: Thursday, September 6, 2018 10:12 AM >To: Richardson, Bruce <bruce.richardson@intel.com>; De Lara Guarch, Pablo <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 <honnappa.nagarahalli@arm.com> >Subject: [dpdk-dev] [PATCH 4/4] 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. > >+/** Flag to support lock free reader writer concurrency */ >+#define RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF 0x08 [Wang, Yipeng] It would be good to indicate that the lockless implementation works for single writer multiple readers. Also, if people use a mix of the flags for example set both multiwriter and LF flags, then I guess either we need to return an error or maybe multiwriter should have higher priority. Currently the RW_CONCURRENCY will assume MULTI_WRITER_ADD I think. >+ > /** 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'. [Wang, Yipeng] Could you be more specific on this description? When add_key API is called, the users do not know if it will update an existing entry or inserting a new one, do they? > * > * @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); > [Wang, Yipeng] If possible, how about having a new delete function instead of modifying the current one? I think it does not need to be tied with the lockless implementation, it is orthogonal to multi-threading implementation. people using locks may still want this new deletion behavior. If people want old behavior, they can call current API, otherwise they can call the new deletion function, followed by Rte_hash_free_key_with_position later.
> > > >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. > > > >+/** Flag to support lock free reader writer concurrency */ #define > >+RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF 0x08 > [Wang, Yipeng] It would be good to indicate that the lockless implementation > works for single writer multiple readers. Multi-writers are supported by using the rw-lock or transactional memory. Essentially, we still have single writer. This patch works fine with multi-writer as defined by ' MULTI_WRITER_ADD' flag. I have tested it as well. I will enable this test case in V2. > Also, if people use a mix of the flags for example set both multiwriter and LF > flags, then I guess either we need to return an error or maybe multiwriter > should have higher priority. Currently the RW_CONCURRENCY will assume > MULTI_WRITER_ADD I think. As mentioned above, multi-writer and LF combination is supported. Yes, RW_CONCURRENCY currently assumes MULTI_WRITER_ADD. I think we should separate them. > >+ > > /** 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'. > [Wang, Yipeng] Could you be more specific on this description? > When add_key API is called, the users do not know if it will update an existing > entry or inserting a new one, do they? I think, it will depend on the application. The applications I have worked on so far, added a hash entry as a result of receiving an event and updated it on receiving another event. I can change the comments to indicate that the applications need to be aware of add/update operations. > > > * > > * @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); > > > [Wang, Yipeng] If possible, how about having a new delete function instead of > modifying the current one? > I think it does not need to be tied with the lockless implementation, it is > orthogonal to multi-threading implementation. > people using locks may still want this new deletion behavior. > If people want old behavior, they can call current API, otherwise they can call > the new deletion function, followed by Rte_hash_free_key_with_position later. I like the terms 'delete' and 'free'. I am finding it hard to come up with a good name for the API. It will be on the lines of 'rte_hash_del_key_with_hash_no_free' - I do not like the name much. Instead, we could have a configuration flag for the hash table, 'RTE_HASH_EXTRA_FLAGS_FREE_MEM_ON_DEL'. If this is enabled, 'rte_hash_del_...' APIs will free the key store index and any internal memory. Enabling lock-free RW concurrency will enable this flag. User can enable this flag explicitly while not using lock-free RW concurrency as well.
>-----Original Message----- >From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com] >Sent: Sunday, September 30, 2018 9:11 PM >To: Wang, Yipeng1 <yipeng1.wang@intel.com>; Richardson, Bruce <bruce.richardson@intel.com>; De Lara Guarch, Pablo ><pablo.de.lara.guarch@intel.com> >Cc: dev@dpdk.org; Gavin Hu (Arm Technology China) <Gavin.Hu@arm.com>; Steve Capper <Steve.Capper@arm.com>; Ola Liljedahl ><Ola.Liljedahl@arm.com>; nd <nd@arm.com>; Gobriel, Sameh <sameh.gobriel@intel.com> >Subject: RE: [dpdk-dev] [PATCH 4/4] 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. >> > >> >+/** Flag to support lock free reader writer concurrency */ #define >> >+RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF 0x08 >> [Wang, Yipeng] It would be good to indicate that the lockless implementation >> works for single writer multiple readers. >Multi-writers are supported by using the rw-lock or transactional memory. Essentially, we still have single writer. This patch works fine >with multi-writer as defined by ' MULTI_WRITER_ADD' flag. I have tested it as well. I will enable this test case in V2. > >> Also, if people use a mix of the flags for example set both multiwriter and LF >> flags, then I guess either we need to return an error or maybe multiwriter >> should have higher priority. Currently the RW_CONCURRENCY will assume >> MULTI_WRITER_ADD I think. >As mentioned above, multi-writer and LF combination is supported. Yes, RW_CONCURRENCY currently assumes MULTI_WRITER_ADD. >I think we should separate them. [Wang, Yipeng] It would be great if you could just add a little bit more comments to both of the flags to be more specific on what Read write concurrency mean in both cases, just in case users got confused. You may also want to update the documentation later (https://doc.dpdk.org/guides/prog_guide/hash_lib.html). > >> >+ >> > /** 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'. >> [Wang, Yipeng] Could you be more specific on this description? >> When add_key API is called, the users do not know if it will update an existing >> entry or inserting a new one, do they? >I think, it will depend on the application. The applications I have worked on so far, added a hash entry as a result of receiving an event >and updated it on receiving another event. I can change the comments to indicate that the applications need to be aware of >add/update operations. [Wang, Yipeng] Even if for current rte_hash, after update, the application may still use the old data. It is the upper level application's Responsibility. How is it specific to lock free implementation? > >> > 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); >> > >> [Wang, Yipeng] If possible, how about having a new delete function instead of >> modifying the current one? >> I think it does not need to be tied with the lockless implementation, it is >> orthogonal to multi-threading implementation. >> people using locks may still want this new deletion behavior. >> If people want old behavior, they can call current API, otherwise they can call >> the new deletion function, followed by Rte_hash_free_key_with_position later. >I like the terms 'delete' and 'free'. I am finding it hard to come up with a good name for the API. It will be on the lines of >'rte_hash_del_key_with_hash_no_free' - I do not like the name much. >Instead, we could have a configuration flag for the hash table, 'RTE_HASH_EXTRA_FLAGS_FREE_MEM_ON_DEL'. If this is enabled, >'rte_hash_del_...' APIs will free the key store index and any internal memory. Enabling lock-free RW concurrency will enable this flag. >User can enable this flag explicitly while not using lock-free RW concurrency as well. [Wang, Yipeng] I am OK with either way. For flag, maybe we should call it RTE_HASH_EXTRA_FLAGS_RECYCLE _ON_DEL, since The key-data pair index is recycled to be more specific. User should know that the index might be re-used by another write. BTW, current flag is only 8 bit, as we specify more and more flags, maybe we should announce an API change to change it to 32bit for next release.
> >> > > >> >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. > >> > > >> >+/** Flag to support lock free reader writer concurrency */ #define > >> >+RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF 0x08 > >> [Wang, Yipeng] It would be good to indicate that the lockless > >> implementation works for single writer multiple readers. > >Multi-writers are supported by using the rw-lock or transactional > >memory. Essentially, we still have single writer. This patch works fine with > multi-writer as defined by ' MULTI_WRITER_ADD' flag. I have tested it as well. > I will enable this test case in V2. > > > >> Also, if people use a mix of the flags for example set both > >> multiwriter and LF flags, then I guess either we need to return an > >> error or maybe multiwriter should have higher priority. Currently the > >> RW_CONCURRENCY will assume MULTI_WRITER_ADD I think. > >As mentioned above, multi-writer and LF combination is supported. Yes, > RW_CONCURRENCY currently assumes MULTI_WRITER_ADD. > >I think we should separate them. > [Wang, Yipeng] It would be great if you could just add a little bit more > comments to both of the flags to be more specific on what Read write > concurrency mean in both cases, just in case users got confused. > You may also want to update the documentation later > (https://doc.dpdk.org/guides/prog_guide/hash_lib.html). I will add the documentation once the patch is accepted. > > > > >> >+ > >> > /** 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'. > >> [Wang, Yipeng] Could you be more specific on this description? > >> When add_key API is called, the users do not know if it will update > >> an existing entry or inserting a new one, do they? > >I think, it will depend on the application. The applications I have > >worked on so far, added a hash entry as a result of receiving an event > >and updated it on receiving another event. I can change the comments to > indicate that the applications need to be aware of add/update operations. > [Wang, Yipeng] Even if for current rte_hash, after update, the application may > still use the old data. It is the upper level application's Responsibility. How is it > specific to lock free implementation? I agree. I think it makes sense to keep this warning, but make it not specific to lock-free algorithm. I will make this change in V3. > > > >> > 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); > >> > > >> [Wang, Yipeng] If possible, how about having a new delete function > >> instead of modifying the current one? > >> I think it does not need to be tied with the lockless implementation, > >> it is orthogonal to multi-threading implementation. > >> people using locks may still want this new deletion behavior. > >> If people want old behavior, they can call current API, otherwise > >> they can call the new deletion function, followed by > Rte_hash_free_key_with_position later. > >I like the terms 'delete' and 'free'. I am finding it hard to come up > >with a good name for the API. It will be on the lines of > 'rte_hash_del_key_with_hash_no_free' - I do not like the name much. > >Instead, we could have a configuration flag for the hash table, > >'RTE_HASH_EXTRA_FLAGS_FREE_MEM_ON_DEL'. If this is enabled, > 'rte_hash_del_...' APIs will free the key store index and any internal memory. > Enabling lock-free RW concurrency will enable this flag. > >User can enable this flag explicitly while not using lock-free RW concurrency > as well. > [Wang, Yipeng] I am OK with either way. For flag, maybe we should call it > RTE_HASH_EXTRA_FLAGS_RECYCLE _ON_DEL, since The key-data pair index is > recycled to be more specific. User should know that the index might be re- > used by another write. > BTW, current flag is only 8 bit, as we specify more and more flags, maybe we > should announce an API change to change it to 32bit for next release. I agree. Do you know how to do this? Do you want to take care of this?
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 <stdint.h> #include <stddef.h> +#include <rte_compat.h> + #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; + +};