From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR04-DB3-obe.outbound.protection.outlook.com (mail-eopbgr60082.outbound.protection.outlook.com [40.107.6.82]) by dpdk.org (Postfix) with ESMTP id 0FD241B1F2 for ; Thu, 27 Sep 2018 21:21: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=vscgToondmIKRXTc7S3b6+XnA6trljMRVcPdJlML6Ss=; b=o5qsnpaTvAp/R+F4baMDJ+Bst2p4JqelG7+j3i6yRPB6+oQPN9Zg68/b2D0007sfGXw5BQ8DpruJ0ADPFreSneS5+lHgGsCBriB/aydoxcddmDqt08wAx5IXOWs3fTbE7jlAZHovoYQCYJX7xj8sIcUNU3a097ixKwJNeYGxq6s= Received: from AM6PR08MB3672.eurprd08.prod.outlook.com (20.177.115.29) by AM6PR08MB3157.eurprd08.prod.outlook.com (52.135.164.18) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1164.25; Thu, 27 Sep 2018 19:21:38 +0000 Received: from AM6PR08MB3672.eurprd08.prod.outlook.com ([fe80::589e:d3cf:9777:5ff9]) by AM6PR08MB3672.eurprd08.prod.outlook.com ([fe80::589e:d3cf:9777:5ff9%2]) with mapi id 15.20.1164.024; Thu, 27 Sep 2018 19:21:38 +0000 From: Honnappa Nagarahalli To: Bruce Richardson CC: Yipeng Wang , "dev@dpdk.org" , "michel@digirati.com.br" Thread-Topic: [PATCH v2 5/7] hash: add extendable bucket feature Thread-Index: AQHUUgpSs/Eh6+azy0Oe76JhXbgpcqUAKviwgAPXngCAAIbVcA== Date: Thu, 27 Sep 2018 19:21:38 +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> <20180927111501.GC19604@bricha3-MOBL.ger.corp.intel.com> In-Reply-To: <20180927111501.GC19604@bricha3-MOBL.ger.corp.intel.com> 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; AM6PR08MB3157; 6:M3TJ3hichHmyt14vga6qMcq4ky5Dq4dkqfQc57qm93yMM8X+qHYJNbyqzL577TaNBlrMEvz5TkFzqETnL5kLb/ye4pKblKjELVlI1XM1K8a6I1C3RCdVLTekoVjVwvqzqQjuUZ0FNdbFfNCdUiOKJTMaJlAaEZiDWKEPZU6riBDU1a4QQCtpQzYQPiZu1LLA29N68iYQOUSMjfU92y4Y7g0VVXUvF8AAEcvXuf4xvFV5H4ewpDoWeaOj6Q6yGRr48xEY2knzPDIb43HJLg2I5As1BQMnZd4LF9PPgoPteR7C+cc31c8Osvo6sxwxA8FKCdDORJgO0RDxgaxHsgl1OadI+Tzbg8awu4vkwV9bi1SK5/M4XJpWg6FE6z1gA8x6uwmOkHZYsDS1QCqLDvq0Qr5cFwlrJh3WQp1QQFJRZeC/5rWLUF9cglsRa+fujgXil5cqA5N4yey3+zNNl8qeBQ==; 5:CxTGl2oCbE1YSKWL3iOf+CiT15spBi3ORyuzvmJ4MLGhTdi8AEwm6K3DhLggeWbBIQPQROvCEEVGo6GqvWBhChXTHCVn5iACCEZF4Mo9w9KLbsuM8iVI4Ws8j+1Eb2RvosnRluuvhx7yF6SFzIFolaBaxlKhaIfYNdecKNXlIjA=; 7:k6u8SZDTKun4j9morI1zsZ02MyoGpZf8l0UMYuY/ZyNMm0BOirD1wnE0yFN5Cr2LTMaOMT0aRwiE5sbTC4ybp6X+zGGPPKFiPCDlbHISH/m2Ns0TXanhPQ7d1RmINCIoJ/QFxzA/CTYQkGvteg+ZmkRSuoYRa7E8PUrI9/NOTgHHZP5wq5SOwMMhNXR9mjmkb7piHVOsEW6oNvsYl3JdQi+xN0/Xjnz926r/klzXpHsGRqnHfSiAvPoIy0vFYw7O x-ms-exchange-antispam-srfa-diagnostics: SOS; x-ms-office365-filtering-correlation-id: ee1baa11-108e-4963-e007-08d624ae725d 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:AM6PR08MB3157; x-ms-traffictypediagnostic: AM6PR08MB3157: x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(17755550239193)(228905959029699); x-ms-exchange-senderadcheck: 1 x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(8121501046)(5005006)(10201501046)(3002001)(3231355)(944501410)(52105095)(93006095)(93001095)(6055026)(149066)(150057)(6041310)(20161123558120)(20161123564045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123560045)(20161123562045)(201708071742011)(7699051); SRVR:AM6PR08MB3157; BCL:0; PCL:0; RULEID:; SRVR:AM6PR08MB3157; x-forefront-prvs: 0808323E97 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(39860400002)(366004)(346002)(396003)(136003)(376002)(40434004)(189003)(199004)(97736004)(81166006)(81156014)(5024004)(14444005)(5250100002)(53936002)(102836004)(68736007)(71190400001)(2906002)(71200400001)(305945005)(8676002)(7696005)(7736002)(55016002)(8936002)(76176011)(33656002)(106356001)(6506007)(316002)(105586002)(93886005)(9686003)(86362001)(99286004)(5660300001)(14454004)(72206003)(478600001)(74316002)(6246003)(6436002)(4326008)(3846002)(6116002)(186003)(11346002)(54906003)(256004)(229853002)(486006)(25786009)(26005)(2900100001)(446003)(6916009)(34290500001)(476003)(66066001); DIR:OUT; SFP:1101; SCL:1; SRVR:AM6PR08MB3157; H:AM6PR08MB3672.eurprd08.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; MX:1; A:1; received-spf: None (protection.outlook.com: arm.com does not designate permitted sender hosts) x-microsoft-antispam-message-info: CM6o8UVkFeqhIdGz4aHkP/CxG48BbVIcI+q2ZGPUo3gXuRbaH85HAOMGlPtrUizyUqui8RtpFAFv4xYHMCLAWRbBPl9LRYOSQBGKE2GMMZ5znzUk2jaH3APZOHyH1gpiDIl7+vaJjvQfLb3wIg/7c9pu7qUVQb6EXdFKjhIJgKp/+mEfuGzk/ASIAbebRq/ZXW2vFOM/56Oa8ad6e5BLn8MmZKU9/iuIQT1Hafun8eAG5axtH7XSYN3zeO2wyv6SCmcEOuX3BAqCuiqD2HmYTqZrQdhfO/zDPjd6JM1P7zkQYCV3rDbZrlSfYpMwGwBOhCGWzrtj1sy7FRL3u69sUlkQVnHHJ0iC+2Mn6EfbSZ0= 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: ee1baa11-108e-4963-e007-08d624ae725d X-MS-Exchange-CrossTenant-originalarrivaltime: 27 Sep 2018 19:21:38.0327 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR08MB3157 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: Thu, 27 Sep 2018 19:21:39 -0000 > > > > > > Signed-off-by: Yipeng Wang > > > --- > > > lib/librte_hash/rte_cuckoo_hash.c | 326 > > > +++++++++++++++++++++++++++++++++----- > > > lib/librte_hash/rte_cuckoo_hash.h | 5 + > > > lib/librte_hash/rte_hash.h | 3 + > > > 3 files changed, 292 insertions(+), 42 deletions(-) > > > > > > diff --git a/lib/librte_hash/rte_cuckoo_hash.c > > > b/lib/librte_hash/rte_cuckoo_hash.c > > > index f7b86c8..616900b 100644 > > > --- a/lib/librte_hash/rte_cuckoo_hash.c > > > +++ b/lib/librte_hash/rte_cuckoo_hash.c > > > @@ -31,6 +31,10 @@ > > > #include "rte_hash.h" > > > #include "rte_cuckoo_hash.h" > > > > > > +#define FOR_EACH_BUCKET(CURRENT_BKT, START_BUCKET) > > > \ > > > +for (CURRENT_BKT =3D START_BUCKET; = \ > > > +CURRENT_BKT !=3D NULL; \ > > > +CURRENT_BKT =3D CURRENT_BKT->next) > > > > > > TAILQ_HEAD(rte_hash_list, rte_tailq_entry); > > > > > > @@ -63,6 +67,14 @@ rte_hash_find_existing(const char *name) return > > > h; } > > > > > > +static inline struct rte_hash_bucket * rte_hash_get_last_bkt(struct > > > +rte_hash_bucket *lst_bkt) { while (lst_bkt->next !=3D NULL) lst_bkt = =3D > > > +lst_bkt->next; return lst_bkt; } > > > + > > > void rte_hash_set_cmp_func(struct rte_hash *h, rte_hash_cmp_eq_t > > > func) { h->cmp_jump_table_idx =3D KEY_CUSTOM; @@ -85,13 +97,17 @@ > > > rte_hash_create(const struct rte_hash_parameters > > > *params) > > > struct rte_tailq_entry *te =3D NULL; > > > struct rte_hash_list *hash_list; > > > struct rte_ring *r =3D NULL; > > > +struct rte_ring *r_ext =3D NULL; > > > char hash_name[RTE_HASH_NAMESIZE]; > > > void *k =3D NULL; > > > void *buckets =3D NULL; > > > +void *buckets_ext =3D NULL; > > > char ring_name[RTE_RING_NAMESIZE]; > > > +char ext_ring_name[RTE_RING_NAMESIZE]; > > > unsigned num_key_slots; > > > unsigned i; > > > unsigned int hw_trans_mem_support =3D 0, multi_writer_support =3D 0; > > > +unsigned int ext_table_support =3D 0; > > > unsigned int readwrite_concur_support =3D 0; > > > > > > rte_hash_function default_hash_func =3D (rte_hash_function)rte_jhash= ; > > > @@ -124,6 +140,9 @@ rte_hash_create(const struct > rte_hash_parameters > > > *params) > > > multi_writer_support =3D 1; > > > } > > > > > > +if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_EXT_TABLE) > > > +ext_table_support =3D 1; > > > + > > > /* Store all keys and leave the first entry as a dummy entry for > > > lookup_bulk */ if (multi_writer_support) > > > /* > > > @@ -145,6 +164,24 @@ rte_hash_create(const struct > > > rte_hash_parameters > > > *params) > > > goto err; > > > } > > > > > > +const uint32_t num_buckets =3D rte_align32pow2(params->entries) / > > > +RTE_HASH_BUCKET_ENTRIES; > > > + > > > +snprintf(ext_ring_name, sizeof(ext_ring_name), "HT_EXT_%s", > > > +params- > > > >name); > > Can be inside the if statement below. > > > > > +/* Create ring for extendable buckets. */ if (ext_table_support) { > > > +r_ext =3D rte_ring_create(ext_ring_name, rte_align32pow2(num_buckets > > > ++ 1), > > > +params->socket_id, 0); > > > + > > > +if (r_ext =3D=3D NULL) { > > > +RTE_LOG(ERR, HASH, "ext buckets memory allocation > > > " > > > +"failed\n"); > > > +goto err; > > > +} > > > +} > > > + > > > snprintf(hash_name, sizeof(hash_name), "HT_%s", params->name); > > > > > > rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); > > > @@ -177,18 +214,34 @@ rte_hash_create(const struct > > > rte_hash_parameters > > > *params) > > > goto err_unlock; > > > } > > > > > > -const uint32_t num_buckets =3D rte_align32pow2(params->entries) -/ > > > RTE_HASH_BUCKET_ENTRIES; > > > - > > > buckets =3D rte_zmalloc_socket(NULL, > > > num_buckets * sizeof(struct rte_hash_bucket), RTE_CACHE_LINE_SIZE, > > > params->socket_id); > > > > > > if (buckets =3D=3D NULL) { > > > -RTE_LOG(ERR, HASH, "memory allocation failed\n"); > > > +RTE_LOG(ERR, HASH, "buckets memory allocation failed\n"); > > > goto err_unlock; > > > } > > > > > > +/* Allocate same number of extendable buckets */ > > IMO, we are allocating too much memory to support this feature. Especia= lly, > when we claim that keys ending up in the extendable table is a rare > occurrence. By doubling the memory we are effectively saying that the mai= n > table might have 50% utilization. It will also significantly increase the= cycles > required to iterate the complete hash table (in rte_hash_iterate API) eve= n > when we expect that the extendable table contains very few entries. > > > > I am wondering if we can provide options to control the amount of extra > memory that gets allocated and make the memory allocation dynamic (or on > demand basis). I think this also goes well with the general direction DPD= K is > taking - allocate resources as needed rather than allocating all the reso= urces > during initialization. > > > > Given that adding new entries should not normally be a fast-path function= , > how about allowing memory allocation in add itself. Why not initialize wi= th a > fairly small number of extra bucket entries, and then each time they are = all > used, double the number of entries. That will give efficient resource sca= ling, I > think. > +1 'small number of extra bucket entries' =3D=3D 5% of total capacity requeste= d (assuming cuckoo hash will provide 95% efficiency) > /Bruce IMPORTANT NOTICE: The contents of this email and any attachments are confid= ential and may also be privileged. If you are not the intended recipient, p= lease notify the sender immediately and do not disclose the contents to any= other person, use it for any purpose, or store or copy the information in = any medium. Thank you.