From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga03.intel.com (mga03.intel.com [134.134.136.65]) by dpdk.org (Postfix) with ESMTP id 2DDA95B20 for ; Tue, 2 Oct 2018 01:05:11 +0200 (CEST) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga005.jf.intel.com ([10.7.209.41]) by orsmga103.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 01 Oct 2018 16:05:11 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.54,329,1534834800"; d="scan'208";a="262030008" Received: from fmsmsx106.amr.corp.intel.com ([10.18.124.204]) by orsmga005.jf.intel.com with ESMTP; 01 Oct 2018 15:56:30 -0700 Received: from fmsmsx156.amr.corp.intel.com (10.18.116.74) by FMSMSX106.amr.corp.intel.com (10.18.124.204) with Microsoft SMTP Server (TLS) id 14.3.319.2; Mon, 1 Oct 2018 15:56:29 -0700 Received: from fmsmsx151.amr.corp.intel.com ([169.254.7.87]) by fmsmsx156.amr.corp.intel.com ([169.254.13.194]) with mapi id 14.03.0319.002; Mon, 1 Oct 2018 15:56:29 -0700 From: "Wang, Yipeng1" To: Honnappa Nagarahalli , "Richardson, Bruce" , "De Lara Guarch, Pablo" CC: "dev@dpdk.org" , "Gavin Hu (Arm Technology China)" , Steve Capper , Ola Liljedahl , nd , "Gobriel, Sameh" Thread-Topic: [dpdk-dev] [PATCH 3/4] hash: fix rw concurrency while moving keys Thread-Index: AQHURgTmZ0unqwDLWkeaG/7/RcGoo6UE/J/wgAUQ84CAARZ74A== Date: Mon, 1 Oct 2018 22:56:28 +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: 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: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiMGJkYzAzNTItMmYzOC00NzFiLTkyOTEtZWFkOTRlNDcwOTFmIiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoiS0drek9lSUdcLzdDNmR6NmJmdU84SDgzXC80SEdxY2tpUmczbmJuSlMrSGMyQjZsYXNMOEo5ZlloVkI3MFhcL2M5eCJ9 x-originating-ip: [10.1.200.107] 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: Mon, 01 Oct 2018 23:05:12 -0000 >-----Original Message----- >From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com] >Sent: Sunday, September 30, 2018 4:06 PM >To: Wang, Yipeng1 ; Richardson, Bruce ; De Lara Guarch, Pablo > >Cc: dev@dpdk.org; Gavin Hu (Arm Technology China) ; Stev= e Capper ; Ola Liljedahl >; nd >Subject: RE: [dpdk-dev] [PATCH 3/4] hash: fix rw concurrency while moving = keys > >> >+ __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 an= y >> code, otherwise we need macros for the compile time check. >'__atomic_thread_fence(__ATOMIC_RELEASE)' provides load-load and load-stor= e fence [1]. Hence, it should not add any barriers for >x86. > >[1] https://preshing.com/20130922/acquire-and-release-fences/ > [Wang, Yipeng] Thanks for the link, it is very informative! >> >> >@@ -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 >> 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 yo= u 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 p= rocess of shifting the key will be present in both primary and >secondary buckets. The check for odd version counter is not required as th= e full key comparison would have identified any false >signature matches. [Wang, Yipeng] I was thinking about another corner case and wondering if th= e version counter needs to be done on key deletion as well. For example, a reader reads out the index and falsely matches a signature, = before it reads out the data and the key, the key-data pair got deleted, removed, and recycled by another writer thread. This writer parti= ally overwrote the key (because key store is too large to be atomic). Now, the reader begins to compare the key, and accidentally matches the key= (because the key is partially written and accidentally matches), will The reader read the wrong data out (which should have been a lookup miss)?