From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id 469741B152 for ; Fri, 28 Sep 2018 03:00:21 +0200 (CEST) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga005.fm.intel.com ([10.253.24.32]) by orsmga102.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 27 Sep 2018 18:00:20 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.54,312,1534834800"; d="scan'208";a="266595102" Received: from fmsmsx103.amr.corp.intel.com ([10.18.124.201]) by fmsmga005.fm.intel.com with ESMTP; 27 Sep 2018 18:00:03 -0700 Received: from fmsmsx118.amr.corp.intel.com (10.18.116.18) by FMSMSX103.amr.corp.intel.com (10.18.124.201) with Microsoft SMTP Server (TLS) id 14.3.319.2; Thu, 27 Sep 2018 18:00:01 -0700 Received: from fmsmsx151.amr.corp.intel.com ([169.254.7.87]) by fmsmsx118.amr.corp.intel.com ([169.254.1.230]) with mapi id 14.03.0319.002; Thu, 27 Sep 2018 18:00:01 -0700 From: "Wang, Yipeng1" To: Honnappa Nagarahalli , "Richardson, Bruce" , "De Lara Guarch, Pablo" CC: "dev@dpdk.org" , "gavin.hu@arm.com" , "steve.capper@arm.com" , "ola.liljedahl@arm.com" , "nd@arm.com" Thread-Topic: [dpdk-dev] [PATCH 3/4] hash: fix rw concurrency while moving keys Thread-Index: AQHURgTmZ0unqwDLWkeaG/7/RcGoo6UE/J/w Date: Fri, 28 Sep 2018 01:00:00 +0000 Message-ID: References: <1536253938-192391-1-git-send-email-honnappa.nagarahalli@arm.com> <1536253938-192391-4-git-send-email-honnappa.nagarahalli@arm.com> In-Reply-To: <1536253938-192391-4-git-send-email-honnappa.nagarahalli@arm.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: dlp-product: dlpe-windows dlp-version: 11.0.400.15 dlp-reaction: no-action x-ctpclassification: CTP_NT x-titus-metadata-40: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiZTZiMTAwMWMtYmUzYS00MTk4LTlkN2YtZDFlNDg3ZWJhMDdhIiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoiSFJpT3puQzFMVUMwTDJUS3ptdWtyNHhJNG9JeWdWSVZMVzFTcDZGQ2JadDQxcHZsc3FPb3J2TlI4cHZGemtMSyJ9 x-originating-ip: [10.1.200.106] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 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 01:00:21 -0000 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.c= apper@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 =3D 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 c= ode, 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 =3D sig & h->bucket_bitmask; >- bkt =3D &h->buckets[bucket_idx]; >- > __hash_rw_reader_lock(h); > >- /* Check if key is in primary location */ >- ret =3D search_one_bucket(h, key, sig, data, bkt); >- if (ret !=3D -1) { >- __hash_rw_reader_unlock(h); >- return ret; >- } >- /* Calculate secondary hash */ >- alt_hash =3D rte_hash_secondary_hash(sig); >- bucket_idx =3D alt_hash & h->bucket_bitmask; >- bkt =3D &h->buckets[bucket_idx]; >+ do { [Wang, Yipeng] As far as I know, the MemC3 paper "MemC3: Compact and Concur= rent MemCache with Dumber Caching and Smarter Hashing" as well as OvS cmap uses similar version counter to implement read-write co= ncurrency 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 *da= ta); >+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, has= h_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? Ot= her people may know better on this.