[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
  

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@arm.com>
> Sent: Wednesday, October 10, 2018 11:59 PM
> To: bruce.richardson@intel.com; pablo.de.lara.guarch@intel.com
> Cc: dev@dpdk.org; yipeng1.wang@intel.com; Honnappa Nagarahalli
> <Honnappa.Nagarahalli@arm.com>; Dharmik Thakkar
> <Dharmik.Thakkar@arm.com>; nd <nd@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