From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga18.intel.com (mga18.intel.com [134.134.136.126]) by dpdk.org (Postfix) with ESMTP id 5F25F7D4E for ; Fri, 28 Sep 2018 10:26:16 +0200 (CEST) X-Amp-Result: UNSCANNABLE X-Amp-File-Uploaded: False Received: from orsmga002.jf.intel.com ([10.7.209.21]) by orsmga106.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 28 Sep 2018 01:26:15 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.54,314,1534834800"; d="scan'208";a="95724902" Received: from bricha3-mobl.ger.corp.intel.com ([10.237.221.107]) by orsmga002.jf.intel.com with SMTP; 28 Sep 2018 01:26:12 -0700 Received: by (sSMTP sendmail emulation); Fri, 28 Sep 2018 09:26:10 +0100 Date: Fri, 28 Sep 2018 09:26:10 +0100 From: Bruce Richardson To: "Wang, Yipeng1" Cc: Honnappa Nagarahalli , "De Lara Guarch, Pablo" , "dev@dpdk.org" , "gavin.hu@arm.com" , "steve.capper@arm.com" , "ola.liljedahl@arm.com" , "nd@arm.com" Message-ID: <20180928082610.GA7592@bricha3-MOBL.ger.corp.intel.com> References: <1536253938-192391-1-git-send-email-honnappa.nagarahalli@arm.com> <1536253938-192391-4-git-send-email-honnappa.nagarahalli@arm.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: Organization: Intel Research and Development Ireland Ltd. User-Agent: Mutt/1.10.1 (2018-07-13) Subject: Re: [dpdk-dev] [PATCH 3/4] hash: fix rw concurrency while moving keys X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 28 Sep 2018 08:26:17 -0000 On Fri, Sep 28, 2018 at 02:00:00AM +0100, Wang, Yipeng1 wrote: > 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 ; De Lara Guarch, Pablo > >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 > >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. Just removing a const should not change the ABI, I believe, since the const is just advisory hint to the compiler. Actual parameter size and count remains unchanged so I don't believe there is an issue. [ABI experts, please correct me if I'm wrong on this] /Bruce