From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR02-VE1-obe.outbound.protection.outlook.com (mail-eopbgr20086.outbound.protection.outlook.com [40.107.2.86]) by dpdk.org (Postfix) with ESMTP id C981D1B153 for ; Fri, 28 Sep 2018 23:11:20 +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=bZqW3/6KxxhcnVWC2HMclSXcmj+RjpkfSfQLw/0ZXbA=; b=rBwH6pvBWrW7qvoIKAeeRYWg186T8VNkHhunIdh/B529vGYLVvcaEVEDio6e+9v5UQkeya/k1hjKHXRh5+BiEcmUYoulUAv9bonvBjBYdgFtZm7i6+IsSTc1euLaoxsC+teNXBRKv1tbJv9Z1PpTkeFvjeLc1DC7U8y5oFJv3xU= Received: from DB7PR08MB3674.eurprd08.prod.outlook.com (20.177.120.156) by DB7PR08MB2955.eurprd08.prod.outlook.com (52.134.109.145) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1164.25; Fri, 28 Sep 2018 21:11:19 +0000 Received: from DB7PR08MB3674.eurprd08.prod.outlook.com ([fe80::c41d:b908:aa56:5874]) by DB7PR08MB3674.eurprd08.prod.outlook.com ([fe80::c41d:b908:aa56:5874%4]) with mapi id 15.20.1164.027; Fri, 28 Sep 2018 21:11:19 +0000 From: Honnappa Nagarahalli To: "Wang, Yipeng1" , "Richardson, Bruce" , "De Lara Guarch, Pablo" CC: "dev@dpdk.org" , "honnappa.nagarahalli@dpdk.org" , "Gavin Hu (Arm Technology China)" , Steve Capper , Ola Liljedahl , nd , "Gobriel, Sameh" Thread-Topic: [dpdk-dev] [PATCH 0/4] Address reader-writer concurrency in rte_hash Thread-Index: AQHURgTKqGcS9ICsZUeJFhcyzG1braUE7FCAgAFWTlA= Date: Fri, 28 Sep 2018 21:11:18 +0000 Message-ID: References: <1536253938-192391-1-git-send-email-honnappa.nagarahalli@arm.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; DB7PR08MB2955; 6:OdhGIgMAIxnxjo2DOQ7UKbsD1nJoa/E507Ve+Ah8Zu/HKnq7U1kjupaR8jRiEqYfX8uTfxg5tekAsj4R+RbAJ7Q5aLRWeKzXinvuixVdC08hc8+azsQyHh4Gv0E6MwkwKldA4V7CYPFVzEOGa/Ps8UwNfTx6u7JSg0zF0X1H3UrNjBDoP/qtqQmNNrfdTjGJ1GY/zTVgf3oFVSlmnU+HJfzpzYeuhUbfbt6O8AiYU3/9ldveiwzKm6GCmpoKt4JRWljNy7gCDNp5moAyyQxLUf3HokNzeIGhJz4wZ+WPpJT2WpaNTaIwTELUV2wv8zzFrEHn4dtMNkx11d0VS/EqlJjrWv0zeZtg+Vh3Upc6kSD0nSQFAdHx4DPZgbteZZveaTaongJOfb/4DU0MmqGOeuyQEMJOOlZPdwU9vJQfNQjHjPFpqyYM0gWhMDgq6GEroCCWhu6rUOIczQ1h23c1/g==; 5:8k8/cwX5idZ0Upj6res43/QTKAXB8+QCAEWsb9EyTFzDf/sryyYFivX0AoxecbWy7LWO4KixR1YD7viuvrgcNi4V2Q+Yo9V+mi6fu6VVgVUcmRAfD8tHDgSJjLSHJYQOkebPM3KV8ZmKqVcpWNz5NDgaEwlRlo8Cl/9h1OxQzIw=; 7:jVfGCJQmcDRrdyc/IIedlZFchnaXoZ9o1m16FqD0h6Uq0pw5Xq9j/lAuGE5DQTFIPYJFroRA0n7sbukvEM7zKHvQSPUcmMW4U0fUPca2dT99R1V3/Oh7wzJf2Eo0D/KYXyXhoMst+9Y8L4Dq6JgjLsyI9lcUO9sxoqni7Z4qF0EkRC0p/fi2WvtkPF3jC5bsQ9eVX++fqFl2SwfJ423cb/ooWZ96NlBBqm7PUjnpr4cjbkDdvxwSB/XC3+ajjz9p x-ms-exchange-antispam-srfa-diagnostics: SOS;SOR; x-ms-office365-filtering-correlation-id: d447e34b-fa69-48e0-1591-08d62586ef55 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:DB7PR08MB2955; x-ms-traffictypediagnostic: DB7PR08MB2955: nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:; 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)(10201501046)(3002001)(6055026)(149066)(150057)(6041310)(20161123560045)(20161123564045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123562045)(20161123558120)(201708071742011)(7699051); SRVR:DB7PR08MB2955; BCL:0; PCL:0; RULEID:; SRVR:DB7PR08MB2955; x-forefront-prvs: 0809C12563 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(396003)(346002)(39860400002)(136003)(366004)(376002)(13464003)(199004)(51914003)(189003)(25786009)(105586002)(26005)(55016002)(7736002)(71200400001)(71190400001)(33656002)(6506007)(34290500001)(106356001)(4326008)(7696005)(229853002)(2900100001)(66066001)(81166006)(6246003)(76176011)(186003)(345774005)(305945005)(8676002)(3846002)(99286004)(8936002)(6436002)(74316002)(102836004)(81156014)(53936002)(9686003)(68736007)(6116002)(11346002)(2906002)(72206003)(476003)(110136005)(446003)(86362001)(97736004)(14444005)(5660300001)(54906003)(486006)(14454004)(316002)(256004)(478600001)(5250100002)(21314002); DIR:OUT; SFP:1101; SCL:1; SRVR:DB7PR08MB2955; H:DB7PR08MB3674.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: bOLjVyoRvnHUKk/bB4w2IGAh7fdaqktFfyTq8Lc4Tz0Sgvz0gT0zDCBQ+a56E65AOLixaVAMOlQtbHveM6Hk7hA62AUg/Cyj41jy3bFVLKZhBBnloW+N1baSzBYdDrS2zPM2VEWSGXM59oyYd07ZUu7Hd+RmyEseCLiRM36D2vwSuRLdu8wq+32gAp/RWzJ8UmGCUF+JYT7KPdi8AWgG/TwVVxqy5uLOwbSIUcphB5AGcdHvxTioHrOlagojgVa0oqgwXKOkAIX55YSs4BNpW7BuFnD95n39uGjPWtgo5h47fJtxw3eA4bJQinvBNGaDp58xhbBeaheYaMLzStmccSQQ1iS7/HpT6uTh3KxuCQg= 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: d447e34b-fa69-48e0-1591-08d62586ef55 X-MS-Exchange-CrossTenant-originalarrivaltime: 28 Sep 2018 21:11:18.9929 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB7PR08MB2955 Subject: Re: [dpdk-dev] [PATCH 0/4] Address reader-writer concurrency in rte_hash 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: Fri, 28 Sep 2018 21:11:21 -0000 >=20 > Hi Honnappa, >=20 > Reply inlined: Hi Yipeng, Thank you so much for reviewing. >=20 > >-----Original Message----- > > > > Currently, reader-writer concurrency problems in rte_hash are > > addressed using reader-writer locks. Use of reader-writer locks > > results in following issues: > > > > 1) In many of the use cases for the hash table, writer threads > > are running on control plane. If the writer is preempted while > > holding the lock, it will block the readers for an extended perio= d > > resulting in packet drops. This problem seems to apply for platfo= rms > > with transactional memory support as well because of the algorith= m > > used for rte_rwlock_write_lock_tm: > > > > static inline void > > rte_rwlock_write_lock_tm(rte_rwlock_t *rwl) > > { > > if (likely(rte_try_tm(&rwl->cnt))) > > return; > > rte_rwlock_write_lock(rwl); > > } > > > > i.e. there is a posibility of using rte_rwlock_write_lock in > > failure cases. > [Wang, Yipeng] In our test, TSX failure happens very rarely on a TSX > platform. But we agree that without TSX, the current rte_rwlock > implementation may make the writer to hold a lock for a period of time. >=20 > > 2) Reader-writer lock based solution does not address the following > > issue. > > rte_hash_lookup_xxx APIs return the index of the element in > > the key store. Application(reader) can use that index to referenc= e > > other data structures in its scope. Because of this, the > > index should not be freed till the application completes > > using the index. > [Wang, Yipeng] I agree on this use case. But I think we should provide n= ew > API functions for deletion to users who want this behavior, without > changing the meaning of current API if that is possible. In the lock-free algorithm, the rte_hash_delete API will not free the index= . The new API rte_hash_free will free the index. The solution for the algor= ithm with rw locks needs to be thought about. >=20 > > Current code: > > Cores Lookup Lookup > > with add > > 2 474 246 > > 4 935 579 > > 6 1387 1048 > > 8 1766 1480 > > 10 2119 1951 > > 12 2546 2441 > > > > With this patch: > > Cores Lookup Lookup > > with add > > 2 291 211 > > 4 297 196 > > 6 304 198 > > 8 309 202 > > 10 315 205 > > 12 319 209 > > > [Wang, Yipeng] It would be good if you could provide the platform > information on these results. Apologies, I should have done that. The machine I am using is: Intel(R) Xeo= n(R) CPU E5-2660 v4 @ 2.00GHz, 64G memory. This is a hacked test case which= is not upstreamed. In the case of 'Lookup with add' - I had equal number o= f threads calling 'rte_hash_add' and 'rte_hash_lookup'. In the case of 'Loo= kup' - a set of entries were added and all the threads called 'rte_hash_loo= kup'. Note that these are the numbers without htm. We have created another = test case which I will upstream as next version of this patch. I will publi= sh the numbers with that test case. So, you should be able to reproduce the= numbers with that test case. >=20 > Another comment is as you know we also have a new extension to rte_hash > to enable extendable buckets and partial-key hashing. Thanks for the > comments btw. Could you check if your lockless scheme also applies to > those extensions? Thank you for reminding me on this. I thought I had covered everything. On = a relook, I have missed few key issues. I will reply on the other email thr= ead.