[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