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>,
honnappa.nagarahalli
<IMCEAINVALID-honnappa+2Enagarahalli@eurprd08.prod.outlook.com>,
"Gavin Hu (Arm Technology China)" <Gavin.Hu@arm.com>,
Steve Capper <Steve.Capper@arm.com>,
Ola Liljedahl <Ola.Liljedahl@arm.com>, nd <nd@arm.com>,
"yipeng1.wang@intel.com" <yipeng1.wang@intel.com>,
Michel Machado <michel@digirati.com.br>,
"sameh.gobriel@intel.com" <sameh.gobriel@intel.com>
Subject: Re: [dpdk-dev] [PATCH 0/4] Address reader-writer concurrency in rte_hash
Date: Fri, 14 Sep 2018 21:18:39 +0000 [thread overview]
Message-ID: <AM6PR08MB3672DCC3B1216CA9F730B03698190@AM6PR08MB3672.eurprd08.prod.outlook.com> (raw)
In-Reply-To: <1536253938-192391-1-git-send-email-honnappa.nagarahalli@arm.com>
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@arm.com>
Sent: Thursday, September 6, 2018 12:12 PM
To: bruce.richardson@intel.com; pablo.de.lara.guarch@intel.com
Cc: dev@dpdk.org; honnappa.nagarahalli; Gavin Hu (Arm Technology China) <Gavin.Hu@arm.com>; Steve Capper <Steve.Capper@arm.com>; Ola Liljedahl <Ola.Liljedahl@arm.com>; nd <nd@arm.com>; Honnappa Nagarahalli <Honnappa.Nagarahalli@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
next prev parent reply other threads:[~2018-09-14 21:18 UTC|newest]
Thread overview: 36+ messages / expand[flat|nested] mbox.gz Atom feed top
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
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 ` Honnappa Nagarahalli [this message]
2018-09-26 14:36 ` [dpdk-dev] [PATCH 0/4] Address reader-writer concurrency in rte_hash Honnappa Nagarahalli
2018-09-27 23:45 ` Wang, Yipeng1
2018-09-28 21:11 ` Honnappa Nagarahalli
2018-10-02 0:30 ` Wang, Yipeng1
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=AM6PR08MB3672DCC3B1216CA9F730B03698190@AM6PR08MB3672.eurprd08.prod.outlook.com \
--to=honnappa.nagarahalli@arm.com \
--cc=Gavin.Hu@arm.com \
--cc=IMCEAINVALID-honnappa+2Enagarahalli@eurprd08.prod.outlook.com \
--cc=Ola.Liljedahl@arm.com \
--cc=Steve.Capper@arm.com \
--cc=bruce.richardson@intel.com \
--cc=dev@dpdk.org \
--cc=michel@digirati.com.br \
--cc=nd@arm.com \
--cc=pablo.de.lara.guarch@intel.com \
--cc=sameh.gobriel@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).