From: "Wang, Yipeng1" <yipeng1.wang@intel.com>
To: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>,
"Richardson, Bruce" <bruce.richardson@intel.com>,
"De Lara Guarch, Pablo" <pablo.de.lara.guarch@intel.com>
Cc: "dev@dpdk.org" <dev@dpdk.org>,
"gavin.hu@arm.com" <gavin.hu@arm.com>,
"steve.capper@arm.com" <steve.capper@arm.com>,
"ola.liljedahl@arm.com" <ola.liljedahl@arm.com>,
"nd@arm.com" <nd@arm.com>
Subject: Re: [dpdk-dev] [PATCH 3/4] hash: fix rw concurrency while moving keys
Date: Fri, 28 Sep 2018 01:00:00 +0000 [thread overview]
Message-ID: <D2C4A16CA39F7F4E8E384D204491D7A6614D81EE@FMSMSX151.amr.corp.intel.com> (raw)
In-Reply-To: <1536253938-192391-4-git-send-email-honnappa.nagarahalli@arm.com>
Reply inlined:
>-----Original Message-----
>From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Honnappa Nagarahalli
>Sent: Thursday, September 6, 2018 10:12 AM
>To: Richardson, Bruce <bruce.richardson@intel.com>; De Lara Guarch, Pablo <pablo.de.lara.guarch@intel.com>
>Cc: dev@dpdk.org; honnappa.nagarahalli@dpdk.org; gavin.hu@arm.com; steve.capper@arm.com; ola.liljedahl@arm.com;
>nd@arm.com; Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>
>Subject: [dpdk-dev] [PATCH 3/4] hash: fix rw concurrency while moving keys
>
>Reader-writer concurrency issue, caused by moving the keys
>to their alternative locations during key insert, is solved
>by introducing a global counter(tbl_chng_cnt) indicating a
>change in table.
>
>@@ -662,6 +679,20 @@ rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h,
> curr_bkt = curr_node->bkt;
> }
>
>+ /* Inform the previous move. The current move need
>+ * not be informed now as the current bucket entry
>+ * is present in both primary and secondary.
>+ * Since there is one writer, load acquires on
>+ * tbl_chng_cnt are not required.
>+ */
>+ __atomic_store_n(&h->tbl_chng_cnt,
>+ h->tbl_chng_cnt + 1,
>+ __ATOMIC_RELEASE);
>+ /* The stores to sig_alt and sig_current should not
>+ * move above the store to tbl_chng_cnt.
>+ */
>+ __atomic_thread_fence(__ATOMIC_RELEASE);
>+
[Wang, Yipeng] I believe for X86 this fence should not be compiled to any code, otherwise
we need macros for the compile time check.
>@@ -926,30 +957,56 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
> uint32_t bucket_idx;
> hash_sig_t alt_hash;
> struct rte_hash_bucket *bkt;
>+ uint32_t cnt_b, cnt_a;
> int ret;
>
>- bucket_idx = sig & h->bucket_bitmask;
>- bkt = &h->buckets[bucket_idx];
>-
> __hash_rw_reader_lock(h);
>
>- /* Check if key is in primary location */
>- ret = search_one_bucket(h, key, sig, data, bkt);
>- if (ret != -1) {
>- __hash_rw_reader_unlock(h);
>- return ret;
>- }
>- /* Calculate secondary hash */
>- alt_hash = rte_hash_secondary_hash(sig);
>- bucket_idx = alt_hash & h->bucket_bitmask;
>- bkt = &h->buckets[bucket_idx];
>+ do {
[Wang, Yipeng] As far as I know, the MemC3 paper "MemC3: Compact and Concurrent
MemCache with Dumber Caching and Smarter Hashing"
as well as OvS cmap uses similar version counter to implement read-write concurrency for hash table,
but one difference is reader checks even/odd of the version counter to make sure there is no
concurrent writer. Could you just double check and confirm that this is not needed for your implementation?
>--- a/lib/librte_hash/rte_hash.h
>+++ b/lib/librte_hash/rte_hash.h
>@@ -156,7 +156,7 @@ rte_hash_count(const struct rte_hash *h);
> * - -ENOSPC if there is no space in the hash for this key.
> */
> int
>-rte_hash_add_key_data(const struct rte_hash *h, const void *key, void *data);
>+rte_hash_add_key_data(struct rte_hash *h, const void *key, void *data);
>
> /**
> * Add a key-value pair with a pre-computed hash value
>@@ -180,7 +180,7 @@ rte_hash_add_key_data(const struct rte_hash *h, const void *key, void *data);
> * - -ENOSPC if there is no space in the hash for this key.
> */
> int32_t
>-rte_hash_add_key_with_hash_data(const struct rte_hash *h, const void *key,
>+rte_hash_add_key_with_hash_data(struct rte_hash *h, const void *key,
> hash_sig_t sig, void *data);
>
> /**
>@@ -200,7 +200,7 @@ rte_hash_add_key_with_hash_data(const struct rte_hash *h, const void *key,
> * array of user data. This value is unique for this key.
> */
> int32_t
>-rte_hash_add_key(const struct rte_hash *h, const void *key);
>+rte_hash_add_key(struct rte_hash *h, const void *key);
>
> /**
> * Add a key to an existing hash table.
>@@ -222,7 +222,7 @@ rte_hash_add_key(const struct rte_hash *h, const void *key);
> * array of user data. This value is unique for this key.
> */
> int32_t
>-rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig);
>+rte_hash_add_key_with_hash(struct rte_hash *h, const void *key, hash_sig_t sig);
>
> /
I think the above changes will break ABI by changing the parameter type? Other people may know better on this.
next prev parent reply other threads:[~2018-09-28 1:00 UTC|newest]
Thread overview: 36+ messages / expand[flat|nested] mbox.gz Atom feed top
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 [this message]
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
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=D2C4A16CA39F7F4E8E384D204491D7A6614D81EE@FMSMSX151.amr.corp.intel.com \
--to=yipeng1.wang@intel.com \
--cc=bruce.richardson@intel.com \
--cc=dev@dpdk.org \
--cc=gavin.hu@arm.com \
--cc=honnappa.nagarahalli@arm.com \
--cc=nd@arm.com \
--cc=ola.liljedahl@arm.com \
--cc=pablo.de.lara.guarch@intel.com \
--cc=steve.capper@arm.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).