From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR03-VE1-obe.outbound.protection.outlook.com (mail-eopbgr50047.outbound.protection.outlook.com [40.107.5.47]) by dpdk.org (Postfix) with ESMTP id 1F17F5B2E for ; Mon, 1 Oct 2018 22:56:39 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector1-arm-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=2oBvtFEJP0Qi4nvhoR4bkXnDV0hRoxU7KD5UHvwBH1w=; b=NklHtVZ9O/s4DhybmxdZWdrHYzUOwc/94nQJOca0hlqE2WYzdR1CejK5UTqlIHNO35xJM/NbhIy8snjyE9LpNjcilAym+r2Xm8Iaj4CYeF7nrDDoWf0kWRYQN7JZRatTSS7WqqxzFWkHtX/DHKs7bUsIguOYA7twKC+g5zKiYQc= Received: from AM6PR08MB3672.eurprd08.prod.outlook.com (20.177.115.29) by AM6PR08MB3511.eurprd08.prod.outlook.com (20.177.114.204) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1185.22; Mon, 1 Oct 2018 20:56:38 +0000 Received: from AM6PR08MB3672.eurprd08.prod.outlook.com ([fe80::f423:e46a:a03c:e928]) by AM6PR08MB3672.eurprd08.prod.outlook.com ([fe80::f423:e46a:a03c:e928%2]) with mapi id 15.20.1185.024; Mon, 1 Oct 2018 20:56:37 +0000 From: Honnappa Nagarahalli To: "Wang, Yipeng1" , "Richardson, Bruce" CC: "dev@dpdk.org" , "michel@digirati.com.br" , "Gobriel, Sameh" , Honnappa Nagarahalli , nd Thread-Topic: [PATCH v2 5/7] hash: add extendable bucket feature Thread-Index: AQHUUgpSs/Eh6+azy0Oe76JhXbgpcqUAKviwgAZPqxCABG+ycA== Date: Mon, 1 Oct 2018 20:56:37 +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: authentication-results: spf=none (sender IP is ) smtp.mailfrom=Honnappa.Nagarahalli@arm.com; x-originating-ip: [217.140.111.135] x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1; AM6PR08MB3511; 6:KFT99noDTlaFgJgeCPcflyAZAJqye38C/lM/SdRXVaZHYr5D0Dnp4bMW2zGAbEiCcP6Bar/TGbMIxnr/WCOqLWO/9TtOmTXkBQ5QYnJ+4QSst5rtctJjtGpmZwWUs0C5wvTGGpdO+tqqmcD2PScfGPFWsQrCRaQGG0veloNcuY/RuMwkoKBB199/bN9JPF7iWowWUvpUGxF781oytYPRpHkIVi9dQT9zfiYHdL/K+M5eAl41Mbjp2gxmb4OPB2rZoO8ZnP9glTnb5hI6Wun0mfVjsSwsUsrgefreaM0OvUfjs4VkuVUJFR+yZ1Rme3+2iPA6TU1Jx7c32PZyFb9E2zt9UXHRThPrKApZqamWYiwlXHSj76Pi6NubToxQew3JTAV5n0tHQc12uYDK9aWGKfbCwmbWD1pbgSBoytQuY+gxdC9SJz0fQVFgtxLUXPRoalmmhcp84NVapzdoy1i+JA==; 5:sInmfvV0X4mqb2OK/nG4buz1MTWNv9YHSgfaHTNIzRk+FMcs1C0t2joE/9hK/z3QtEJC7X8kr1USY/jGJz4gB4MU/2zmqw5E+mgfQAVCJnL2REiaFT24zV55kLGrCsTYxK6PILa77cUR4I2pZnKbzMb3Mbew23JbiqPlznNDHV0=; 7:eqE9rzYFNWpNWfG/aHFsptrXRnQemgJ2AK2fr+ZA4vGcpgl0mxAk9JNnmVe5hYhUfscjoyKyXQ39ezOG62Kkd+pIAZwItpfu9VY1P/DVQ5T7Pf5k36R8MuMfol3w/OMb4MV8nbiWjkR34u7JZOMgHwhdH8Z2kOhaYyxobxibnGUNJZGayi/xZaiB/ZLY6suavJ+/9or0jCefJbPj5bV3uLbPA0Upytd3+vBCKTFPrHO+n9JKAPxdS5smDCgbqZZD x-ms-exchange-antispam-srfa-diagnostics: SOS;SOR; x-ms-office365-filtering-correlation-id: f2914e49-a904-43c3-2159-08d627e06163 x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: BCL:0; PCL:0; RULEID:(7020095)(4652040)(8989299)(4534165)(4627221)(201703031133081)(201702281549075)(8990200)(5600074)(711020)(4618075)(2017052603328)(7153060)(7193020); SRVR:AM6PR08MB3511; x-ms-traffictypediagnostic: AM6PR08MB3511: nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(180628864354917)(17755550239193); x-ms-exchange-senderadcheck: 1 x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(5005006)(8121501046)(93006095)(93001095)(3231355)(944501410)(52105095)(3002001)(10201501046)(6055026)(149066)(150057)(6041310)(20161123562045)(20161123564045)(20161123560045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123558120)(201708071742011)(7699051); SRVR:AM6PR08MB3511; BCL:0; PCL:0; RULEID:; SRVR:AM6PR08MB3511; x-forefront-prvs: 0812095267 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(376002)(346002)(136003)(39860400002)(366004)(396003)(13464003)(199004)(189003)(2900100001)(25786009)(105586002)(74316002)(7696005)(106356001)(6116002)(97736004)(33656002)(3846002)(305945005)(8676002)(6246003)(316002)(81166006)(81156014)(7736002)(68736007)(6506007)(76176011)(71200400001)(4326008)(71190400001)(476003)(93886005)(478600001)(54906003)(66066001)(72206003)(110136005)(55016002)(446003)(53936002)(11346002)(2906002)(5250100002)(86362001)(14454004)(9686003)(26005)(5660300001)(102836004)(229853002)(99286004)(486006)(256004)(6436002)(14444005)(186003)(8936002); DIR:OUT; SFP:1101; SCL:1; SRVR:AM6PR08MB3511; H:AM6PR08MB3672.eurprd08.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:1; MX:1; received-spf: None (protection.outlook.com: arm.com does not designate permitted sender hosts) x-microsoft-antispam-message-info: bVgd1G5zmjxHGAwrxFF+blpjCCGdswWwfycXN6sYGbDHZywsGW10wujlgSqcFMBkuKOLT1zNmSxZz3CUu2arLUiPiQ+0x1jFStcet9a58VeH9jN3yGK2xacpRYVgFKjhiXkXOmztL2obRel0MqXUffgrBA+/0ZStraswU5SwsKgtwku5YqUTgy35gHmdXiBGWUpO5AWW9r9ej+qFixbpXmljB0+Kbt2kfHrqAyDDn6Y2t7CG6tPdixEtmAffxCvv6uv+TGFZmE0tUXyhRyVZCKC3Yie3F7gwW41LhmYZ7PGDpqOHxfaM+uAYWEjMxndz3jJVvZpEKBmTkv9ICHxR+V7KldXapeWaR/g5n2ATvKE= spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-Network-Message-Id: f2914e49-a904-43c3-2159-08d627e06163 X-MS-Exchange-CrossTenant-originalarrivaltime: 01 Oct 2018 20:56:37.8766 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR08MB3511 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: Mon, 01 Oct 2018 20:56:39 -0000 > >-----Original Message----- > >From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com] > >> > >> Extendable bucket table composes of buckets that can be linked list > >> to current main table. When extendable bucket is enabled, the table > >> utilization can always acheive 100%. > >IMO, referring to this as 'table utilization' indicates an efficiency > >about 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! >=20 > >> +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 > index Is from 1 to num_buckets. So I guess reserving 0 means reserving th= e > 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 fr= ee > Bucket ring for use? I understand it now. I mis-read the 'similar to the key-data slot' comment.= I see that the changes are correct. Minor comment, I am not particular: I think it makes sense to change it to = the same logic followed for key-data slot. i.e. allocate an extra bucket. > > > >> 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++) Minor comment: If we are not changing the logic, I suggest we change the for loop as follo= ws (like it is done earlier) for (i =3D 1; i <=3D h->num_buckets; i++) > >Index 0 is reserved as per the comments. Condition should be 'i < h- > >num_buckets'. > [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 ar= ray 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 = got > a bucket index we need to -1 To get the bucket array subscript. > >> +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 (*nex= t > >> +- 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 while loop. It presents a problem if 'position' becomes EMPTY_SLOT. > >'position' should be read as part of the while loop. Since it is 32b val= ue, it > should be atomic on most platforms. This issue applies to existing code a= s > well. > > > [Wang, Yipeng] I agree. I add a new bug fix commit to fix this in V4. Bas= ically I > just extend the current critical region to cover The while loop. Please c= heck if > that works. Thanks. >=20 > >__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! > >