From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga07.intel.com (mga07.intel.com [134.134.136.100]) by dpdk.org (Postfix) with ESMTP id A5B325B36 for ; Thu, 7 Mar 2019 18:49:37 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga001.fm.intel.com ([10.253.24.23]) by orsmga105.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 07 Mar 2019 09:49:36 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.58,451,1544515200"; d="scan'208";a="152966460" Received: from orsmsx101.amr.corp.intel.com ([10.22.225.128]) by fmsmga001.fm.intel.com with ESMTP; 07 Mar 2019 09:49:36 -0800 Received: from orsmsx152.amr.corp.intel.com (10.22.226.39) by ORSMSX101.amr.corp.intel.com (10.22.225.128) with Microsoft SMTP Server (TLS) id 14.3.408.0; Thu, 7 Mar 2019 09:49:35 -0800 Received: from orsmsx104.amr.corp.intel.com ([169.254.4.6]) by ORSMSX152.amr.corp.intel.com ([169.254.8.92]) with mapi id 14.03.0415.000; Thu, 7 Mar 2019 09:49:34 -0800 From: "Wang, Yipeng1" To: Dharmik Thakkar , "Gobriel, Sameh" , "Richardson, Bruce" , "De Lara Guarch, Pablo" , "Mcnamara, John" , "Kovacevic, Marko" CC: "dev@dpdk.org" , "Tai, Charlie" Thread-Topic: [RFC 1/2] hash: add lock free support for extendable bucket Thread-Index: AQHU0I5B8fApX8JDXUWI9qjnwKHssaYAeaQA Date: Thu, 7 Mar 2019 17:49:34 +0000 Message-ID: References: <20190302002334.7911-1-dharmik.thakkar@arm.com> <20190302002334.7911-2-dharmik.thakkar@arm.com> In-Reply-To: <20190302002334.7911-2-dharmik.thakkar@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: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiZDNmMDkwZGQtN2RkOS00MjU2LWExOTUtYTdkNTc0MGI3ZmQ0IiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoiRkJtQkNcLzNGSUZrVVRwYk0rYXZraWJkWnpneTlRaWJZN2JBSzJUeCtCaVB1VTJMcENpSWdYQ29Bd0ZhNnkyQmEifQ== x-originating-ip: [10.22.254.139] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Subject: Re: [dpdk-dev] [RFC 1/2] hash: add lock free support for extendable bucket 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: Thu, 07 Mar 2019 17:49:38 -0000 Thanks for this patch! Some initial comments inlined: >-----Original Message----- >From: Dharmik Thakkar [mailto:dharmik.thakkar@arm.com] >Sent: Friday, March 1, 2019 4:24 PM >To: Wang, Yipeng1 ; Gobriel, Sameh ; Richardson, Bruce >; De Lara Guarch, Pablo ; Mcnamara, John >; Kovacevic, Marko >Cc: dev@dpdk.org; Dharmik Thakkar >Subject: [RFC 1/2] hash: add lock free support for extendable bucket > >This patch enables lock-free read-write concurrency support for >extendable bucket feature. > >Suggested-by: Honnappa Nagarahalli >Signed-off-by: Dharmik Thakkar >--- > doc/guides/prog_guide/hash_lib.rst | 3 +- > lib/librte_hash/rte_cuckoo_hash.c | 150 +++++++++++++++++++---------- > lib/librte_hash/rte_cuckoo_hash.h | 8 ++ > 3 files changed, 110 insertions(+), 51 deletions(-) > >diff --git a/doc/guides/prog_guide/hash_lib.rst b/doc/guides/prog_guide/ha= sh_lib.rst >index 85a6edfa8b16..b00446e949ba 100644 >--- a/doc/guides/prog_guide/hash_lib.rst >+++ b/doc/guides/prog_guide/hash_lib.rst >@@ -108,8 +108,7 @@ Extendable Bucket Functionality support > An extra flag is used to enable this functionality (flag is not set by de= fault). When the (RTE_HASH_EXTRA_FLAGS_EXT_TABLE) is set >and > in the very unlikely case due to excessive hash collisions that a key has= failed to be inserted, the hash table bucket is extended with a >linked > list to insert these failed keys. This feature is important for the workl= oads (e.g. telco workloads) that need to insert up to 100% of the >-hash table size and can't tolerate any key insertion failure (even if ver= y few). Currently the extendable bucket is not supported >-with the lock-free concurrency implementation (RTE_HASH_EXTRA_FLAGS_RW_CO= NCURRENCY_LF). >+hash table size and can't tolerate any key insertion failure (even if ver= y few). > > > Implementation Details (non Extendable Bucket Case) >diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cucko= o_hash.c >index c01489ba5193..54762533ce36 100644 >--- a/lib/librte_hash/rte_cuckoo_hash.c >+++ b/lib/librte_hash/rte_cuckoo_hash.c >@@ -170,15 +170,6 @@ rte_hash_create(const struct rte_hash_parameters *par= ams) > return NULL; > } > >- if ((params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF) && >- (params->extra_flag & RTE_HASH_EXTRA_FLAGS_EXT_TABLE)) { >- rte_errno =3D EINVAL; >- RTE_LOG(ERR, HASH, "rte_hash_create: extendable bucket " >- "feature not supported with rw concurrency " >- "lock free\n"); >- return NULL; >- } >- > /* Check extra flags field to check extra options. */ > if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT) > hw_trans_mem_support =3D 1; >@@ -1054,7 +1045,15 @@ __rte_hash_add_key_with_hash(const struct rte_hash = *h, const void *key, > /* Check if slot is available */ > if (likely(cur_bkt->key_idx[i] =3D=3D EMPTY_SLOT)) { > cur_bkt->sig_current[i] =3D short_sig; >- cur_bkt->key_idx[i] =3D new_idx; >+ /* Key can be of arbitrary length, so it is >+ * not possible to store it atomically. >+ * Hence the new key element's memory stores >+ * (key as well as data) should be complete >+ * before it is referenced. >+ */ >+ __atomic_store_n(&cur_bkt->key_idx[i], >+ new_idx, >+ __ATOMIC_RELEASE); > __hash_rw_writer_unlock(h); > return new_idx - 1; > } >@@ -1072,10 +1071,23 @@ __rte_hash_add_key_with_hash(const struct rte_hash= *h, const void *key, > bkt_id =3D (uint32_t)((uintptr_t)ext_bkt_id) - 1; > /* Use the first location of the new bucket */ > (h->buckets_ext[bkt_id]).sig_current[0] =3D short_sig; >- (h->buckets_ext[bkt_id]).key_idx[0] =3D new_idx; >+ /* Key can be of arbitrary length, so it is >+ * not possible to store it atomically. >+ * Hence the new key element's memory stores >+ * (key as well as data) should be complete >+ * before it is referenced. >+ */ >+ __atomic_store_n(&(h->buckets_ext[bkt_id]).key_idx[0], >+ new_idx, >+ __ATOMIC_RELEASE); [Wang, Yipeng] Since it has not been linked and later on the linking is pr= otected by release, do we really need atomic store here? > /* Link the new bucket to sec bucket linked list */ > last =3D rte_hash_get_last_bkt(sec_bkt); >- last->next =3D &h->buckets_ext[bkt_id]; >+ /* New bucket's memory stores (key as well as data) >+ * should be complete before it is referenced >+ */ >+ __atomic_store_n(&last->next, >+ &h->buckets_ext[bkt_id], >+ __ATOMIC_RELEASE); > __hash_rw_writer_unlock(h); > return new_idx - 1; > >@@ -1366,7 +1378,8 @@ remove_entry(const struct rte_hash *h, struct rte_ha= sh_bucket *bkt, unsigned i) > * empty slot. > */ > static inline void >-__rte_hash_compact_ll(struct rte_hash_bucket *cur_bkt, int pos) { >+__rte_hash_compact_ll(const struct rte_hash *h, >+ struct rte_hash_bucket *cur_bkt, int pos) { > int i; > struct rte_hash_bucket *last_bkt; > >@@ -1377,10 +1390,27 @@ __rte_hash_compact_ll(struct rte_hash_bucket *cur_= bkt, int pos) { > > for (i =3D RTE_HASH_BUCKET_ENTRIES - 1; i >=3D 0; i--) { > if (last_bkt->key_idx[i] !=3D EMPTY_SLOT) { >- cur_bkt->key_idx[pos] =3D last_bkt->key_idx[i]; > cur_bkt->sig_current[pos] =3D last_bkt->sig_current[i]; >+ __atomic_store_n(&cur_bkt->key_idx[pos], >+ last_bkt->key_idx[i], >+ __ATOMIC_RELEASE); >+ if (h->readwrite_concur_lf_support) { >+ /* Inform the readers that the table has changed >+ * 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); >+ } > last_bkt->sig_current[i] =3D NULL_SIGNATURE; >- last_bkt->key_idx[i] =3D EMPTY_SLOT; >+ __atomic_store_n(&last_bkt->key_idx[i], >+ EMPTY_SLOT, >+ __ATOMIC_RELEASE); > return; > } > } >@@ -1449,7 +1479,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *= h, const void *key, > /* look for key in primary bucket */ > ret =3D search_and_remove(h, key, prim_bkt, short_sig, &pos); > if (ret !=3D -1) { >- __rte_hash_compact_ll(prim_bkt, pos); >+ __rte_hash_compact_ll(h, prim_bkt, pos); > last_bkt =3D prim_bkt->next; > prev_bkt =3D prim_bkt; > goto return_bkt; >@@ -1461,7 +1491,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *= h, const void *key, > FOR_EACH_BUCKET(cur_bkt, sec_bkt) { > ret =3D search_and_remove(h, key, cur_bkt, short_sig, &pos); > if (ret !=3D -1) { >- __rte_hash_compact_ll(cur_bkt, pos); >+ __rte_hash_compact_ll(h, cur_bkt, pos); > last_bkt =3D sec_bkt->next; > prev_bkt =3D sec_bkt; > goto return_bkt; >@@ -1488,11 +1518,21 @@ __rte_hash_del_key_with_hash(const struct rte_hash= *h, const void *key, > } > /* found empty bucket and recycle */ > if (i =3D=3D RTE_HASH_BUCKET_ENTRIES) { >- prev_bkt->next =3D last_bkt->next =3D NULL; >+ __atomic_store_n(&prev_bkt->next, >+ NULL, >+ __ATOMIC_RELEASE); > uint32_t index =3D last_bkt - h->buckets_ext + 1; >- rte_ring_sp_enqueue(h->free_ext_bkts, (void *)(uintptr_t)index); >- } >+ if (!h->no_free_on_del) >+ rte_ring_sp_enqueue(h->free_ext_bkts, (void *)(uintptr_t)index); >+ else { >+ struct rte_hash_key *key_slot =3D >+ (struct rte_hash_key *)( >+ (char *)h->key_store + >+ ret * h->key_entry_size); >+ key_slot->ext_bkt_to_free =3D index; [Wang, Yipeng] Is there chance that a key_slot may already have one previou= s ext_bkt and now got overwritten, so that the previous one gone forever? > >+ } >+ } > __hash_rw_writer_unlock(h); > return ret; > } >@@ -1567,6 +1607,14 @@ rte_hash_free_key_with_position(const struct rte_ha= sh *h, > (void *)((uintptr_t)position)); > } > >+ const struct rte_hash_key *key_slot =3D (const struct rte_hash_key *)( >+ (const char *)h->key_store + >+ position * h->key_entry_size); >+ uint32_t index =3D key_slot->ext_bkt_to_free; >+ if (!index) >+ /* Recycle empty ext bkt to free list. */ >+ rte_ring_sp_enqueue(h->free_ext_bkts, (void *)(uintptr_t)index); >+ > return 0; > } > >@@ -1855,6 +1903,9 @@ __rte_hash_lookup_bulk_lf(const struct rte_hash *h, = const void **keys, > rte_prefetch0(secondary_bkt[i]); > } > >+ for (i =3D 0; i < num_keys; i++) >+ positions[i] =3D -ENOENT; [Wang, Yipeng] So is this for performance reason? >+ > do { > /* Load the table change counter before the lookup > * starts. Acquire semantics will make sure that >@@ -1899,7 +1950,6 @@ __rte_hash_lookup_bulk_lf(const struct rte_hash *h, = const void **keys, > > /* Compare keys, first hits in primary first */ > for (i =3D 0; i < num_keys; i++) { >- positions[i] =3D -ENOENT; > while (prim_hitmask[i]) { > uint32_t hit_index =3D > __builtin_ctzl(prim_hitmask[i]) >@@ -1972,6 +2022,36 @@ __rte_hash_lookup_bulk_lf(const struct rte_hash *h,= const void **keys, > continue; > } > >+ >+ /* all found, do not need to go through ext bkt */ >+ if (hits =3D=3D ((1ULL << num_keys) - 1)) { >+ if (hit_mask !=3D NULL) >+ *hit_mask =3D hits; [Wang, Yipeng] I think you need to check the version counter before return, and how about the fence? >+ return; >+ } >+ /* need to check ext buckets for match */ >+ if (h->ext_table_support) { >+ for (i =3D 0; i < num_keys; i++) { >+ if ((hits & (1ULL << i)) !=3D 0) >+ continue; >+ next_bkt =3D secondary_bkt[i]->next; >+ FOR_EACH_BUCKET(cur_bkt, next_bkt) { >+ if (data !=3D NULL) >+ ret =3D search_one_bucket_lf(h, >+ keys[i], sig[i], >+ &data[i], cur_bkt); >+ else >+ ret =3D search_one_bucket_lf(h, >+ keys[i], sig[i], >+ NULL, cur_bkt); >+ if (ret !=3D -1) { >+ positions[i] =3D ret; >+ hits |=3D 1ULL << i; >+ break; >+ } >+ } >+ } >+ } > /* The loads of sig_current in compare_signatures > * should not move below the load from tbl_chng_cnt. > */ >@@ -1988,34 +2068,6 @@ __rte_hash_lookup_bulk_lf(const struct rte_hash *h,= const void **keys, > __ATOMIC_ACQUIRE); > } while (cnt_b !=3D cnt_a); > >- /* all found, do not need to go through ext bkt */ >- if ((hits =3D=3D ((1ULL << num_keys) - 1)) || !h->ext_table_support) { >- if (hit_mask !=3D NULL) >- *hit_mask =3D hits; >- __hash_rw_reader_unlock(h); >- return; >- } >- >- /* need to check ext buckets for match */ >- for (i =3D 0; i < num_keys; i++) { >- if ((hits & (1ULL << i)) !=3D 0) >- continue; >- next_bkt =3D secondary_bkt[i]->next; >- FOR_EACH_BUCKET(cur_bkt, next_bkt) { >- if (data !=3D NULL) >- ret =3D search_one_bucket_lf(h, keys[i], >- sig[i], &data[i], cur_bkt); >- else >- ret =3D search_one_bucket_lf(h, keys[i], >- sig[i], NULL, cur_bkt); >- if (ret !=3D -1) { >- positions[i] =3D ret; >- hits |=3D 1ULL << i; >- break; >- } >- } >- } >- > if (hit_mask !=3D NULL) > *hit_mask =3D hits; > } >diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cucko= o_hash.h >index eacdaa8d4684..062cc2dd0296 100644 >--- a/lib/librte_hash/rte_cuckoo_hash.h >+++ b/lib/librte_hash/rte_cuckoo_hash.h >@@ -129,6 +129,14 @@ struct lcore_cache { > > /* Structure that stores key-value pair */ > struct rte_hash_key { >+ /* Stores index of an empty ext bkt to be recycled on calling >+ * rte_hash_del_xxx APIs. When lock free read-wrie concurrency is [Wang, Yipeng] typo >+ * enabled, an empty ext bkt cannot be put into free list immediately >+ * (as readers might be using it still). Hence freeing of the ext bkt >+ * is piggy-backed to freeing of the key index. >+ */ [Wang, Yipeng] I am thinking if this breaks the "guarantee" provided by ext= table, Since a whole bucket could not be reused if one key not freed. Is there any funda= mental issue with a new API to recycle ext bucket or you just do not want to add a new API? >+ uint32_t ext_bkt_to_free; >+ > union { > uintptr_t idata; > void *pdata; >-- >2.17.1