From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR01-VE1-obe.outbound.protection.outlook.com (mail-ve1eur01on0058.outbound.protection.outlook.com [104.47.1.58]) by dpdk.org (Postfix) with ESMTP id A3D1C4CA6 for ; Fri, 14 Sep 2018 23:18:41 +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=MH0iJt6Pm9BuP8MOTyb7YLrlVC90HxkQoM0/MkKhqH0=; b=L2L0gpcoJIkG3WGK01OGadJGmv+JAiLu4Mi23QgUZ5UUN+3+AIksErkY90Td8JyJPNNNGCAssoge1u0T45jqPpFe1zcN1Dk8iuketIoAIwwLIPoLOa/NFeoMwTZG5sYB7IBz8ECz9ztImHu/APfXaEgUHXAyg+/egW9HTCIt+w0= Received: from AM6PR08MB3672.eurprd08.prod.outlook.com (20.177.115.29) by AM6PR08MB3160.eurprd08.prod.outlook.com (52.135.164.21) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1122.16; Fri, 14 Sep 2018 21:18:39 +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.1122.018; Fri, 14 Sep 2018 21:18:39 +0000 From: Honnappa Nagarahalli To: Honnappa Nagarahalli , "bruce.richardson@intel.com" , "pablo.de.lara.guarch@intel.com" CC: "dev@dpdk.org" , honnappa.nagarahalli , "Gavin Hu (Arm Technology China)" , Steve Capper , Ola Liljedahl , nd , "yipeng1.wang@intel.com" , Michel Machado , "sameh.gobriel@intel.com" Thread-Topic: [PATCH 0/4] Address reader-writer concurrency in rte_hash Thread-Index: AQHURgTKqGcS9ICsZUeJFhcyzG1braTwU7bw Date: Fri, 14 Sep 2018 21:18:39 +0000 Message-ID: References: <1536253938-192391-1-git-send-email-honnappa.nagarahalli@arm.com> In-Reply-To: <1536253938-192391-1-git-send-email-honnappa.nagarahalli@arm.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [217.140.111.135] x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1; AM6PR08MB3160; 6:pSkKIM/e7o/NGhgmV9KPJ4lUTXqR3rYuP8Spf7h3eGZHu/8sXgVsr2rAdvU1UdSFzHAe2V4V5+g+aQNnRi11jgWB+xkctrTdQaffoCBd5qQ36brSBEK1tUhPEOJX0DB8/EUcsrBDqn0Ky7d0BLJL4Gz4R19sc8BJgBGR0GmkRA10cDvqeRu+VAqNzSa5hGgoqVsY+G53L+hVjKHEDyccSuLSY/DMRB8oYOAsVJviyCWAuK/Z7Be1np1UWBcjBvfgJ+6LA8nlk3rO59lhSwQ6Kln8AOY1kZL12FQ4txN2u1P+VEkc7JKDxIe1Fl2NH/bGJ2TrDLfmdd3KHIJD0GA/5HO557FdMyg3KSWeeALvTYDWT5HVSIosY7Aw8f1zPcWTPhSjvRmarg1qeTzThxVNd0c1xHNYWljZMpARRRZAwUFMC89tZkw5+/2gS5FN0UBUx1ljQXPJKlZV8Vr1Tpif3Q==; 5:pjWAMOfUvl7R+CaGS7lR3i2A/ZxQOTLtIM4Jf8AMEQIuutybkQu6HBxoPbbfvxbVGpLBAAdRWYBaeFuThderwliKDt20uTIPZ0d312McShz4O/0BI+PkCdAhXjKaTfzBP1X+XUUMOHHwQBeGvUvAuD9UGFnUkM9fibBqlJbEDYo=; 7:3k7E3i0wdwB6tumhHhVaM+gDOJSTlUz1ZnYlPlcQF9sWJ29ZB+b0Y9VZM+CA5Zog8ZfhpZ53VNTMFuFDYx817pceKmR3mJirPkzoAOz3Z75UZZlOlcokHN57VtwVISFa1LH/lbFCAIKWgL3Hr3jKwx9C4mddf6uxFR5wCoL6In/vVNl3LzK4KBwsvM5BCj11MO77mS5Am1jqBvRPZ3mjhA240uVxgpAN4UxcDedo61HbPSQoHGr76fHq5SxfK1HA x-ms-exchange-antispam-srfa-diagnostics: SOS;SOR; x-ms-office365-filtering-correlation-id: 9bc4cd2e-6330-4656-c398-08d61a87a41f x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: BCL:0; PCL:0; RULEID:(7020095)(4652040)(8989137)(5600074)(711020)(4618075)(2017052603328)(7153060)(7193020); SRVR:AM6PR08MB3160; x-ms-traffictypediagnostic: AM6PR08MB3160: nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(180628864354917)(228905959029699); x-ms-exchange-senderadcheck: 1 x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(5005006)(8121501046)(3231344)(944501410)(52105095)(3002001)(10201501046)(93006095)(93001095)(6055026)(149027)(150027)(6041310)(20161123564045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123562045)(20161123560045)(20161123558120)(201708071742011)(7699050)(76991041); SRVR:AM6PR08MB3160; BCL:0; PCL:0; RULEID:; SRVR:AM6PR08MB3160; x-forefront-prvs: 07954CC105 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(39860400002)(366004)(136003)(396003)(346002)(376002)(189003)(199004)(13464003)(2900100001)(25786009)(106356001)(256004)(14454004)(6116002)(5660300001)(14444005)(229853002)(3846002)(446003)(53936002)(97736004)(105586002)(316002)(8936002)(54906003)(55016002)(4326008)(7696005)(6436002)(6246003)(76176011)(33656002)(110136005)(486006)(81156014)(81166006)(99286004)(8676002)(7736002)(2201001)(305945005)(6506007)(53546011)(72206003)(102836004)(86362001)(476003)(68736007)(9686003)(966005)(6346003)(478600001)(2906002)(26005)(6306002)(74316002)(11346002)(2501003)(66066001)(5250100002)(21314002); DIR:OUT; SFP:1101; SCL:1; SRVR:AM6PR08MB3160; 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) authentication-results: spf=none (sender IP is ) smtp.mailfrom=Honnappa.Nagarahalli@arm.com; x-microsoft-antispam-message-info: 3rvNeJmcXDmvafNjqf7rg0N7ZZcQCuMKJnanI+x+c9Tn/ZtbfHmln4pQlAZIpXYyvvqzcACpZTENCjcHcLUW97oY1STM34XQ9COxp5YwNjyRf3YbPkbWaWu1jQfYUZi7BgGdZlMWtXDsZZfCX6TNw8tMX9IoC/8ZXImF/FHYFJWGZfo0NO3/vonFjCIKpqxdIBodW8PZsmAHX0y+muWVLuf6P656y4aCpcz2oRmuLl4IsPFyGw8/237NhGY3fK7gNvD8wvqnau9cLfUwHNZrYLYWa8t9KHF01oESviGKDVUrP3Xo54VlyPxWKX5OJIvMv1nAk6H743YfeHhukBPEawelVCx1OLytpuigf6h66JA= 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: 9bc4cd2e-6330-4656-c398-08d61a87a41f X-MS-Exchange-CrossTenant-originalarrivaltime: 14 Sep 2018 21:18:39.4862 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR08MB3160 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, 14 Sep 2018 21:18:42 -0000 I have added the memory ordering ladder diagrams to the DPDK summit slides = to help understand the changes. The slides are available at: https://dpdkus= erspace2018.sched.com/event/G44w/lock-free-read-write-concurrency-in-rtehas= h. Please look at the backup slides. Thank you, Honnappa -----Original Message----- From: Honnappa Nagarahalli =20 Sent: Thursday, September 6, 2018 12:12 PM To: bruce.richardson@intel.com; pablo.de.lara.guarch@intel.com Cc: dev@dpdk.org; honnappa.nagarahalli; Gavin Hu (Arm Technology China) ; Steve Capper ; Ola Liljedahl ; nd ; Honnappa Nagarahalli Subject: [PATCH 0/4] Address reader-writer concurrency in rte_hash Currently, reader-writer concurrency problems in rte_hash are addressed using reader-writer locks. Use of reader-writer locks results in following issues: =20 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 period resulting in packet drops. This problem seems to apply for platforms with transactional memory support as well because of the algorithm used for rte_rwlock_write_lock_tm: =20 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); } =20 i.e. there is a posibility of using rte_rwlock_write_lock in failure cases. 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 reference other data structures in its scope. Because of this, the index should not be freed till the application completes using the index. 3) Since writer blocks all the readers, the hash lookup rate comes down significantly when there is activity on the writer. This happens even for unrelated entries. Performance numbers given below clearly indicate this. =20 Lock-free solution is required to solve these problems. This patch series adds the lock-free capabilities in the following steps: =20 1) Correct the alignment for the key store entry to prep for memory ordering. 2) Add memory ordering to prevent race conditions when a new key is added to the table. =20 3) Reader-writer concurrency issue, caused by moving the keys to their alternate locations during key insert, is solved by introducing an atomic global counter indicating a change in table. =20 4) This solution also has to solve the issue of readers using key store element even after the key is deleted from control plane. To solve this issue, the hash_del_key_xxx APIs do not free the key store element. The key store element has to be freed using the newly introduced rte_hash_free_key_with_position API. It needs to be called once all the readers have stopped using the key store element. How this is determined is outside the scope of this patch (RCU is one such mechanism that the application can use). =20 4) Finally, a lock free reader-writer concurrency flag is added to enable this feature at run time. =20 Performance numbers: Scenario: Equal number of writer/reader threads for concurrent writers and readers. For readers only test, the entries are added upfront. 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 Honnappa Nagarahalli (4): hash: correct key store element alignment hash: add memory ordering to avoid race conditions hash: fix rw concurrency while moving keys hash: enable lock-free reader-writer concurrency lib/librte_hash/rte_cuckoo_hash.c | 445 +++++++++++++++++++++++++------= ---- lib/librte_hash/rte_cuckoo_hash.h | 6 +- lib/librte_hash/rte_hash.h | 63 ++++- lib/librte_hash/rte_hash_version.map | 7 + 4 files changed, 393 insertions(+), 128 deletions(-) --=20 2.7.4