[dpdk-dev] [PATCH v2 0/7] Address reader-writer concurrency in rte_hash
Honnappa Nagarahalli
Honnappa.Nagarahalli at arm.com
Thu Oct 11 08:04:52 CEST 2018
Hi Yipeng,
I will rebase this further with your V7 and submit V3. Please let me know if you have any comments in the meantime. Due to time constraints, I do not plan to support lock-free for extended bucket feature in this release. I will add that support in the next release. Please let me know if you have any concerns.
Thank you,
Honnappa
> -----Original Message-----
> From: Honnappa Nagarahalli <honnappa.nagarahalli at arm.com>
> Sent: Wednesday, October 10, 2018 11:59 PM
> To: bruce.richardson at intel.com; pablo.de.lara.guarch at intel.com
> Cc: dev at dpdk.org; yipeng1.wang at intel.com; Honnappa Nagarahalli
> <Honnappa.Nagarahalli at arm.com>; Dharmik Thakkar
> <Dharmik.Thakkar at arm.com>; nd <nd at arm.com>
> Subject: [PATCH v2 0/7] Address reader-writer concurrency in rte_hash
>
> Currently, reader-writer concurrency problems in rte_hash are
> addressed using reader-writer locks. Use of reader-writer locks
> results in following issues:
>
> 1) In many of the use cases for the hash table, writer threads
> are running on control plane. If the writer is preempted while
> holding the lock, it will block the readers for an extended period
> resulting in packet drops. This problem seems to apply for platforms
> with transactional memory support as well because of the algorithm
> used for rte_rwlock_write_lock_tm:
>
> static inline void
> rte_rwlock_write_lock_tm(rte_rwlock_t *rwl)
> {
> if (likely(rte_try_tm(&rwl->cnt)))
> return;
> rte_rwlock_write_lock(rwl);
> }
>
> i.e. there is a posibility of using rte_rwlock_write_lock in
> failure cases.
> 2) Reader-writer lock based solution does not address the following
> issue.
> rte_hash_lookup_xxx APIs return the index of the element in
> the key store. Application(reader) can use that index to reference
> other data structures in its scope. Because of this, the
> index should not be freed till the application completes
> using the index.
> 3) Since writer blocks all the readers, the hash lookup
> rate comes down significantly when there is activity on the writer.
> This happens even for unrelated entries. Performance numbers
> given below clearly indicate this.
>
> Lock-free solution is required to solve these problems. This patch
> series adds the lock-free capabilities in the following steps:
>
> 1) Add support to not free the key-store index upon calling
> rte_hash_del_xxx APIs. This solves the issue in 2).
>
> 2) Correct the alignment for the key store entry to prep for
> memory ordering.
>
> 3) Add memory ordering to prevent race conditions when a new key
> is added to the table.
>
> 4) Reader-writer concurrency issue, caused by moving the keys
> to their alternate locations during key insert, is solved
> by introducing an atomic global counter indicating a change
> in table.
>
> 5) This solution also has to solve the issue of readers using
> key store element even after the key is deleted from
> control plane.
> To solve this issue, the hash_del_key_xxx APIs do not free
> the key store element when lock-free algorithm is enabled.
> The key store element has to be freed using the newly introduced
> rte_hash_free_key_with_position API. It needs to be called once
> all the readers have stopped using the key store element. How this
> is determined is outside the scope of this patch (RCU is one such
> mechanism that the application can use).
>
> 6) Finally, a lock free reader-writer concurrency flag is added
> to enable this feature at run time.
>
> Performance numbers can be got from the additional test case added
> as part of this patch.
>
> v1->v2
> 1) Separate multi-writer capability from rw concurrency
> 2) Add do not recycle on delete feature (Yipeng)
> 3) Add Arm copyright
> 4) Add test case to test lock-free algorithm and multi-writer
> test case (Yipeng)
> 5) Additional API documentation to indicate RCU usage (Yipeng)
> 6) Additional documentation on rte_hash_reset API (Yipeng)
> 7) Allocate memory for the global counter and avoid API
> changes (Yipeng)
>
> Dharmik Thakkar (1):
> test/hash: read-write lock-free concurrency test
>
> Honnappa Nagarahalli (6):
> hash: separate multi-writer from rw-concurrency
> hash: support do not recycle on delete
> hash: correct key store element alignment
> hash: add memory ordering to avoid race conditions
> hash: fix rw concurrency while moving keys
> hash: enable lock-free reader-writer concurrency
>
> lib/librte_hash/rte_cuckoo_hash.c | 483 +++++++++++----
> lib/librte_hash/rte_cuckoo_hash.h | 17 +-
> lib/librte_hash/rte_hash.h | 82 ++-
> lib/librte_hash/rte_hash_version.map | 7 +
> test/test/Makefile | 1 +
> test/test/meson.build | 1 +
> test/test/test_hash.c | 140 ++++-
> test/test/test_hash_readwrite.c | 6 +-
> test/test/test_hash_readwrite_lf.c | 1084
> ++++++++++++++++++++++++++++++++++
> 9 files changed, 1686 insertions(+), 135 deletions(-) create mode 100644
> test/test/test_hash_readwrite_lf.c
>
> --
> 2.7.4
More information about the dev
mailing list