DPDK patches and discussions
 help / color / mirror / Atom feed
* [dpdk-dev] [PATCH 0/4] Address reader-writer concurrency in rte_hash
@ 2018-09-06 17:12 Honnappa Nagarahalli
  2018-09-06 17:12 ` [dpdk-dev] [PATCH 1/4] hash: correct key store element alignment Honnappa Nagarahalli
                   ` (5 more replies)
  0 siblings, 6 replies; 36+ messages in thread
From: Honnappa Nagarahalli @ 2018-09-06 17:12 UTC (permalink / raw)
  To: bruce.richardson, pablo.de.lara.guarch
  Cc: dev, honnappa.nagarahalli, gavin.hu, steve.capper, ola.liljedahl,
	nd, Honnappa Nagarahalli

    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

^ permalink raw reply	[flat|nested] 36+ messages in thread

end of thread, other threads:[~2018-10-11  5:24 UTC | newest]

Thread overview: 36+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-09-06 17:12 [dpdk-dev] [PATCH 0/4] Address reader-writer concurrency in rte_hash Honnappa Nagarahalli
2018-09-06 17:12 ` [dpdk-dev] [PATCH 1/4] hash: correct key store element alignment Honnappa Nagarahalli
2018-09-27 23:58   ` Wang, Yipeng1
2018-09-06 17:12 ` [dpdk-dev] [PATCH 2/4] hash: add memory ordering to avoid race conditions Honnappa Nagarahalli
2018-09-28  0:43   ` Wang, Yipeng1
2018-09-30 22:20     ` Honnappa Nagarahalli
2018-10-01 22:41       ` Wang, Yipeng1
2018-10-01 10:42     ` Ola Liljedahl
2018-10-02  1:52       ` Wang, Yipeng1
2018-09-06 17:12 ` [dpdk-dev] [PATCH 3/4] hash: fix rw concurrency while moving keys Honnappa Nagarahalli
2018-09-28  1:00   ` Wang, Yipeng1
2018-09-28  8:26     ` Bruce Richardson
2018-09-28  8:55       ` Van Haaren, Harry
2018-09-30 22:33         ` Honnappa Nagarahalli
2018-10-02 13:17           ` Van Haaren, Harry
2018-10-02 23:58             ` Wang, Yipeng1
2018-10-03 17:32               ` Honnappa Nagarahalli
2018-10-03 17:56                 ` Wang, Yipeng1
2018-10-03 23:05                   ` Ola Liljedahl
2018-10-04  3:32                   ` Honnappa Nagarahalli
2018-10-04  3:54                 ` Honnappa Nagarahalli
2018-10-04 19:16                   ` Wang, Yipeng1
2018-09-30 23:05     ` Honnappa Nagarahalli
2018-10-01 22:56       ` Wang, Yipeng1
2018-10-03  0:16       ` Wang, Yipeng1
2018-10-03 17:39         ` Honnappa Nagarahalli
2018-09-06 17:12 ` [dpdk-dev] [PATCH 4/4] hash: enable lock-free reader-writer concurrency Honnappa Nagarahalli
2018-09-28  1:33   ` Wang, Yipeng1
2018-10-01  4:11     ` Honnappa Nagarahalli
2018-10-01 23:54       ` Wang, Yipeng1
2018-10-11  5:24         ` Honnappa Nagarahalli
2018-09-14 21:18 ` [dpdk-dev] [PATCH 0/4] Address reader-writer concurrency in rte_hash Honnappa Nagarahalli
2018-09-26 14:36   ` Honnappa Nagarahalli
2018-09-27 23:45 ` Wang, Yipeng1
2018-09-28 21:11   ` Honnappa Nagarahalli
2018-10-02  0:30     ` Wang, Yipeng1

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).