From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga14.intel.com (mga14.intel.com [192.55.52.115]) by dpdk.org (Postfix) with ESMTP id C1B9B1B107 for ; Sat, 29 Sep 2018 03:11:01 +0200 (CEST) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga004.fm.intel.com ([10.253.24.48]) by fmsmga103.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 28 Sep 2018 18:11:00 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.54,317,1534834800"; d="scan'208";a="93080557" Received: from fmsmsx105.amr.corp.intel.com ([10.18.124.203]) by fmsmga004.fm.intel.com with ESMTP; 28 Sep 2018 18:10:47 -0700 Received: from fmsmsx154.amr.corp.intel.com (10.18.116.70) by FMSMSX105.amr.corp.intel.com (10.18.124.203) with Microsoft SMTP Server (TLS) id 14.3.319.2; Fri, 28 Sep 2018 18:10:47 -0700 Received: from fmsmsx151.amr.corp.intel.com ([169.254.7.87]) by FMSMSX154.amr.corp.intel.com ([169.254.6.126]) with mapi id 14.03.0319.002; Fri, 28 Sep 2018 18:10:46 -0700 From: "Wang, Yipeng1" To: Honnappa Nagarahalli , "Richardson, Bruce" CC: "dev@dpdk.org" , "michel@digirati.com.br" , "Gobriel, Sameh" Thread-Topic: [PATCH v2 5/7] hash: add extendable bucket feature Thread-Index: AQHUUgpSs/Eh6+azy0Oe76JhXbgpcqUAKviwgAZPqxA= Date: Sat, 29 Sep 2018 01:10:45 +0000 Message-ID: References: <1536253745-133104-1-git-send-email-yipeng1.wang@intel.com> <1537550255-252066-1-git-send-email-yipeng1.wang@intel.com> <1537550255-252066-6-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: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiNDg1ZmQxYTgtMDg1Zi00MGY3LWI1YWEtODlkYzQ0YjkxODg1IiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoiQTBNRlRvakNpcHplR1pvS1wvUVlpOE5Uck9hM3pUendodkVqS01kZ0NuaFZFUkVXRlVPVTlaazZXalhObER5ZXYifQ== 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 v2 5/7] 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: Sat, 29 Sep 2018 01:11:02 -0000 >-----Original Message----- >From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com] >> >> Extendable bucket table composes of buckets that can be linked list to c= urrent >> main table. When extendable bucket is enabled, the table utilization can >> always acheive 100%. >IMO, referring to this as 'table utilization' indicates an efficiency abou= t memory utilization. Please consider changing this to indicate >that all of the configured number of entries will be accommodated? > [Wang, Yipeng] Improved in V4, please check! Thanks! >> +snprintf(ext_ring_name, sizeof(ext_ring_name), "HT_EXT_%s", >> +params- >> >name); >Can be inside the if statement below. [Wang, Yipeng] Done in V3, Thanks! > >> +/* Populate ext bkt ring. We reserve 0 similar to the >> + * key-data slot, just in case in future we want to >> + * use bucket index for the linked list and 0 means NULL >> + * for next bucket >> + */ >> +for (i =3D 1; i <=3D num_buckets; i++) >Since, the bucket index 0 is reserved, should be 'i < num_buckets' [Wang, Yipeng] So the bucket array is from 0 to num_buckets - 1, and the i= ndex Is from 1 to num_buckets. So I guess reserving 0 means reserving the index = 0 but not reduce the usable bucket count. So I guess we still need to enqueue index of 1 to num_buckets into the free Bucket ring for use? > >> rte_free(h->key_store); >> rte_free(h->buckets); >Add rte_free(h->buckets_ext); [Wang, Yipeng] Done in V3, thanks! > >> +for (i =3D 1; i < h->num_buckets + 1; i++) >Index 0 is reserved as per the comments. Condition should be 'i < h->num_b= uckets'. [Wang, Yipeng] Similar to previous one, I guess we still need the number of= num_buckets index To be inserted in the ring. > >> +bkt_id =3D (uint32_t)((uintptr_t)ext_bkt_id) - 1; >If index 0 is reserved, -1 is not required. > [Wang, Yipeng] Similar to previous one, bkt_id is the subscript to the arra= y so it ranges from 0 to num_bucket - 1. While the index is ranged from 1 to num_bucket. So I guess every time we go= t a bucket index we need to -1 To get the bucket array subscript.=20 >> +if (tobe_removed_bkt) { >> +uint32_t index =3D tobe_removed_bkt - h->buckets_ext + 1; >No need to increase the index by 1 if entry 0 is reserved. > [Wang, Yipeng] Similar to previous one. >> @@ -1308,10 +1519,13 @@ rte_hash_iterate(const struct rte_hash *h, const >> void **key, void **data, uint32 >> >> RETURN_IF_TRUE(((h =3D=3D NULL) || (next =3D=3D NULL)), -EINVAL); >> >> -const uint32_t total_entries =3D h->num_buckets * >> RTE_HASH_BUCKET_ENTRIES; >> +const uint32_t total_entries_main =3D h->num_buckets * >> + >> RTE_HASH_BUCKET_ENTRIES; >> +const uint32_t total_entries =3D total_entries_main << 1; >> + >> /* Out of bounds */ >Minor: update the comment to reflect the new code. [Wang, Yipeng] Done in V4, thanks! > >> @@ -1341,4 +1555,32 @@ rte_hash_iterate(const struct rte_hash *h, const >> void **key, void **data, uint32 >> (*next)++; >> >> return position - 1; >> + >> +extend_table: >> +/* Out of bounds */ >> +if (*next >=3D total_entries || !h->ext_table_support) >> +return -ENOENT; >> + >> +bucket_idx =3D (*next - total_entries_main) / >> RTE_HASH_BUCKET_ENTRIES; >> +idx =3D (*next - total_entries_main) % RTE_HASH_BUCKET_ENTRIES; >> + >> +while (h->buckets_ext[bucket_idx].key_idx[idx] =3D=3D EMPTY_SLOT) { >> +(*next)++; >> +if (*next =3D=3D total_entries) >> +return -ENOENT; >> +bucket_idx =3D (*next - total_entries_main) / >> +RTE_HASH_BUCKET_ENTRIES; >> +idx =3D (*next - total_entries_main) % >> RTE_HASH_BUCKET_ENTRIES; >> +} >> +/* Get position of entry in key table */ >> +position =3D h->buckets_ext[bucket_idx].key_idx[idx]; >There is a possibility that 'position' is not the same value read in the w= hile loop. It presents a problem if 'position' becomes >EMPTY_SLOT. 'position' should be read as part of the while loop. Since it = is 32b value, it should be atomic on most platforms. This issue >applies to existing code as well. > [Wang, Yipeng] I agree. I add a new bug fix commit to fix this in V4. Basic= ally I just extend the current critical region to cover The while loop. Please check if that works. Thanks. >__hash_rw_reader_lock(h) required >> +next_key =3D (struct rte_hash_key *) ((char *)h->key_store + >> +position * h->key_entry_size); >> +/* Return key and data */ >> +*key =3D next_key->key; >> +*data =3D next_key->pdata; >> + >__hash_rw_reader_unlock(h) required [Wang, Yipeng] Agree, done in V4. Thanks! >