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 B8DAF2C0C for ; Wed, 3 Oct 2018 01:41:02 +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; 02 Oct 2018 16:41:01 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.54,333,1534834800"; d="scan'208";a="262351818" Received: from fmsmsx106.amr.corp.intel.com ([10.18.124.204]) by orsmga005.jf.intel.com with ESMTP; 02 Oct 2018 16:39:53 -0700 Received: from fmsmsx112.amr.corp.intel.com (10.18.116.6) by FMSMSX106.amr.corp.intel.com (10.18.124.204) with Microsoft SMTP Server (TLS) id 14.3.319.2; Tue, 2 Oct 2018 16:39:53 -0700 Received: from fmsmsx151.amr.corp.intel.com ([169.254.7.87]) by FMSMSX112.amr.corp.intel.com ([169.254.5.184]) with mapi id 14.03.0319.002; Tue, 2 Oct 2018 16:39:52 -0700 From: "Wang, Yipeng1" To: Honnappa Nagarahalli , "Richardson, Bruce" CC: "Ananyev, Konstantin" , "dev@dpdk.org" , "Gobriel, Sameh" , nd Thread-Topic: [PATCH v4 2/4] hash: add extendable bucket feature Thread-Index: AQHUV4tn5zytEct7aE6GLUXLgUt5Y6UK4rDwgAG+fjA= Date: Tue, 2 Oct 2018 23:39:51 +0000 Message-ID: References: <1537993618-92630-1-git-send-email-yipeng1.wang@intel.com> <1538155426-145177-1-git-send-email-yipeng1.wang@intel.com> <1538155426-145177-3-git-send-email-yipeng1.wang@intel.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: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiZmViMDkwNzYtNjM5MC00Yzc0LWFiZTgtYmNkMmFmOTkzZjk2IiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoiblhZdWFLanVXaGx6dTYzMzFKSkp6c1JSSk9ZMTZTZjBBdEtUOTc1bko0Z2pvUlpyREpPaVpuRE5qQm0ydWRTVCJ9 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 v4 2/4] hash: add extendable bucket feature 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: Tue, 02 Oct 2018 23:41:03 -0000 >-----Original Message----- >From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com] >> + >> + 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]; >> + cur_bkt->sig_alt[pos] =3D last_bkt->sig_alt[i]; >> + last_bkt->sig_current[i] =3D NULL_SIGNATURE; >> + last_bkt->sig_alt[i] =3D NULL_SIGNATURE; >> + last_bkt->key_idx[i] =3D EMPTY_SLOT; >> + return; >In lock-free algorithm, this will require the global counter increment. > [Wang, Yipeng] I agree. Similar to your protect for cuckoo displacement, pr= otecting the copy part. >> + while (last_bkt->next) { >> + prev_bkt =3D last_bkt; >> + last_bkt =3D last_bkt->next; >> + } >Minor: We are trying to find the last bucket here, along with its previous= . May be we can modify 'rte_hash_get_last_bkt' instead? > [Wang, Yipeng] Then there will be one more store in each iteration for the = regular find_last. I was having an individual function for this but since it is only used here I removed that. If you think it is nece= ssary or you may reuse it somewhere else for LF, I can add it back. >> + >> + for (i =3D 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { >> + if (last_bkt->key_idx[i] !=3D EMPTY_SLOT) >> + break; >> + } >> + /* found empty bucket and recycle */ >> + if (i =3D=3D RTE_HASH_BUCKET_ENTRIES) { >> + prev_bkt->next =3D last_bkt->next =3D NULL; >> + uint32_t index =3D last_bkt - h->buckets_ext + 1; >> + rte_ring_sp_enqueue(h->free_ext_bkts, (void >> *)(uintptr_t)index); >In the lock-less algorithm, the bucket cannot be freed immediately. I look= ed at couple of solutions. The bucket needs to be stored >internally and should be associated with the key-store index (or position)= . I am thinking that I will add a field to 'struct rte_hash_key' >to store the bucket pointer or index. [Wang, Yipeng] Even if the bucket is recycled immediately, what's the worst= could happen? Even if there are readers currently iterating the deleted Bucket, it is still fine right? It is a miss anyway.=20 > >>From the code, my understanding is that we will free only the last bucket.= We will never free the middle bucket, please correct me if I >am wrong. This will keep it simple for the lock-free algorithm. [Wang, Yipeng] It is correct. > >I could work through these issues. So, I do not see any issues for lock-fr= ee algorithm (as of now :) ). > >> + >> + /* Out of bounds of all buckets (both main table and ext table */ >Typo: missing ')' > [Wang, Yipeng] Yeah thanks!