[dpdk-dev] [PATCH 0/4] Address reader-writer concurrency in rte_hash

[Honnappa Nagarahalli]

Hi Bruce/Pablo,
    I need to get this into 18.11, appreciate any review/feedback soon.

Thank you,
Honnappa

> -----Original Message-----
> From: Honnappa Nagarahalli
> Sent: Friday, September 14, 2018 4:19 PM
> To: Honnappa Nagarahalli <honnappa.nagarahalli at arm.com>;
> bruce.richardson at intel.com; pablo.de.lara.guarch at intel.com
> Cc: dev at dpdk.org; honnappa.nagarahalli; Gavin Hu (Arm Technology China)
> <Gavin.Hu at arm.com>; Steve Capper <Steve.Capper at arm.com>; Ola Liljedahl
> <Ola.Liljedahl at arm.com>; nd <nd at arm.com>; yipeng1.wang at intel.com;
> Michel Machado <michel at digirati.com.br>; sameh.gobriel at intel.com
> Subject: RE: [PATCH 0/4] Address reader-writer concurrency in rte_hash
> 
> I have added the memory ordering ladder diagrams to the DPDK summit slides
> to help understand the changes. The slides are available at:
> https://dpdkuserspace2018.sched.com/event/G44w/lock-free-read-write-
> concurrency-in-rtehash. Please look at the backup slides.
> 
> Thank you,
> Honnappa
> 
> -----Original Message-----
> From: Honnappa Nagarahalli <honnappa.nagarahalli at arm.com>
> Sent: Thursday, September 6, 2018 12:12 PM
> To: bruce.richardson at intel.com; pablo.de.lara.guarch at intel.com
> Cc: dev at dpdk.org; honnappa.nagarahalli; Gavin Hu (Arm Technology China)
> <Gavin.Hu at arm.com>; Steve Capper <Steve.Capper at arm.com>; Ola Liljedahl
> <Ola.Liljedahl at arm.com>; nd <nd at arm.com>; Honnappa Nagarahalli
> <Honnappa.Nagarahalli at arm.com>
> Subject: [PATCH 0/4] 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) Correct the alignment for the key store entry to prep for
>        memory ordering.
>     2) Add memory ordering to prevent race conditions when a new key
>        is added to the table.
> 
>     3) 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.
> 
>     4) 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. 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).
> 
>     4) Finally, a lock free reader-writer concurrency flag is added
>        to enable this feature at run time.
> 
>     Performance numbers:
>     Scenario: Equal number of writer/reader threads for concurrent
> 	      writers and readers. For readers only test, the
>               entries are added upfront.
> 
>     Current code:
> 	Cores	Lookup     Lookup
> 		with add
> 	2	474	   246
> 	4	935        579
> 	6	1387       1048
> 	8	1766       1480
> 	10	2119       1951
> 	12	2546       2441
> 
>     With this patch:
> 	Cores	Lookup     Lookup
> 		with add
> 	2	291	   211
> 	4	297	   196
> 	6	304	   198
> 	8	309	   202
> 	10	315	   205
> 	12	319	   209
> 
> Honnappa Nagarahalli (4):
>   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    | 445 +++++++++++++++++++++++++-------
> ---
>  lib/librte_hash/rte_cuckoo_hash.h    |   6 +-
>  lib/librte_hash/rte_hash.h           |  63 ++++-
>  lib/librte_hash/rte_hash_version.map |   7 +
>  4 files changed, 393 insertions(+), 128 deletions(-)
> 
> --
> 2.7.4