From: Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>
To: "Wang, Yipeng1" <yipeng1.wang@intel.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 Technology China)" <Gavin.Hu@arm.com>,
Steve Capper <Steve.Capper@arm.com>,
Ola Liljedahl <Ola.Liljedahl@arm.com>, nd <nd@arm.com>
Subject: Re: [dpdk-dev] [PATCH 3/4] hash: fix rw concurrency while moving keys
Date: Sun, 30 Sep 2018 23:05:51 +0000 [thread overview]
Message-ID: <AM6PR08MB36724E09B9AF737412D166C598EE0@AM6PR08MB3672.eurprd08.prod.outlook.com> (raw)
In-Reply-To: <D2C4A16CA39F7F4E8E384D204491D7A6614D81EE@FMSMSX151.amr.corp.intel.com>
> >
> >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.
'__atomic_thread_fence(__ATOMIC_RELEASE)' provides load-load and load-store fence [1]. Hence, it should not add any barriers for x86.
[1] https://preshing.com/20130922/acquire-and-release-fences/
>
> >@@ -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?
>
I relooked at this paper. My patch makes use of the fact that during the process of shifting the key will be present in both primary and secondary buckets. The check for odd version counter is not required as the full key comparison would have identified any false signature matches.
> >--- 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-30 23:05 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
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 [this message]
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=AM6PR08MB36724E09B9AF737412D166C598EE0@AM6PR08MB3672.eurprd08.prod.outlook.com \
--to=honnappa.nagarahalli@arm.com \
--cc=Gavin.Hu@arm.com \
--cc=Ola.Liljedahl@arm.com \
--cc=Steve.Capper@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).