From: Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>
To: Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>,
"bruce.richardson@intel.com" <bruce.richardson@intel.com>,
"pablo.de.lara.guarch@intel.com" <pablo.de.lara.guarch@intel.com>
Cc: "dev@dpdk.org" <dev@dpdk.org>,
"yipeng1.wang@intel.com" <yipeng1.wang@intel.com>,
Dharmik Thakkar <Dharmik.Thakkar@arm.com>, nd <nd@arm.com>
Subject: Re: [dpdk-dev] [PATCH v2 0/7] Address reader-writer concurrency in rte_hash
Date: Thu, 11 Oct 2018 06:04:52 +0000 [thread overview]
Message-ID: <AM6PR08MB3672F371891F77EE5C29680E98E10@AM6PR08MB3672.eurprd08.prod.outlook.com> (raw)
In-Reply-To: <1539233972-49860-1-git-send-email-honnappa.nagarahalli@arm.com>
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
prev parent reply other threads:[~2018-10-11 6:04 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-10-11 4:59 Honnappa Nagarahalli
2018-10-11 4:59 ` [dpdk-dev] [PATCH v2 1/7] hash: separate multi-writer from rw-concurrency Honnappa Nagarahalli
2018-10-11 4:59 ` [dpdk-dev] [PATCH v2 2/7] hash: support do not recycle on delete Honnappa Nagarahalli
2018-10-11 4:59 ` [dpdk-dev] [PATCH v2 3/7] hash: correct key store element alignment Honnappa Nagarahalli
2018-10-11 4:59 ` [dpdk-dev] [PATCH v2 4/7] hash: add memory ordering to avoid race conditions Honnappa Nagarahalli
2018-10-11 4:59 ` [dpdk-dev] [PATCH v2 5/7] hash: fix rw concurrency while moving keys Honnappa Nagarahalli
2018-10-11 4:59 ` [dpdk-dev] [PATCH v2 6/7] hash: enable lock-free reader-writer concurrency Honnappa Nagarahalli
2018-10-11 4:59 ` [dpdk-dev] [PATCH v2 7/7] test/hash: read-write lock-free concurrency test Honnappa Nagarahalli
2018-10-11 6:04 ` Honnappa Nagarahalli [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=AM6PR08MB3672F371891F77EE5C29680E98E10@AM6PR08MB3672.eurprd08.prod.outlook.com \
--to=honnappa.nagarahalli@arm.com \
--cc=Dharmik.Thakkar@arm.com \
--cc=bruce.richardson@intel.com \
--cc=dev@dpdk.org \
--cc=nd@arm.com \
--cc=pablo.de.lara.guarch@intel.com \
--cc=yipeng1.wang@intel.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).