From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR01-VE1-obe.outbound.protection.outlook.com (mail-ve1eur01on0082.outbound.protection.outlook.com [104.47.1.82]) by dpdk.org (Postfix) with ESMTP id 32FE21B1BB for ; Thu, 11 Oct 2018 08:04:54 +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=P1XA29JJDdxvXtfSDVa+GFC264B0VKYsiOBhlrcsPWQ=; b=L0YvYpcWwrwYYMhcoHXgyBBgszsfjngVF6SMZ91tL+/Jo9HzDdwPYwEItKs9Abv4nHvFPOvRuvLk4+GIFrQ0NLPwdEoXBQRKkw44ZA3dP/UGKoMcjRIbH2UjExtaTtMh69xRuSuKPHX4PztyDPll/++3m6SmuMOAE3rYdnh0iMQ= Received: from AM6PR08MB3672.eurprd08.prod.outlook.com (20.177.115.29) by AM6PR08MB3687.eurprd08.prod.outlook.com (20.177.199.160) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1228.21; Thu, 11 Oct 2018 06:04:52 +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.027; Thu, 11 Oct 2018 06:04:52 +0000 From: Honnappa Nagarahalli To: Honnappa Nagarahalli , "bruce.richardson@intel.com" , "pablo.de.lara.guarch@intel.com" CC: "dev@dpdk.org" , "yipeng1.wang@intel.com" , Dharmik Thakkar , nd Thread-Topic: [PATCH v2 0/7] Address reader-writer concurrency in rte_hash Thread-Index: AQHUYR852FmoYnRPmEOIa/xfm/Y6w6UZjaIQ Date: Thu, 11 Oct 2018 06:04:52 +0000 Message-ID: References: <1539233972-49860-1-git-send-email-honnappa.nagarahalli@arm.com> In-Reply-To: <1539233972-49860-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.103.75] x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1; AM6PR08MB3687; 6:Izb6Ur/TJjTLbUCRo2o8/UQtSJpLTlK4HW2Rb2bfwyjo7MHxG5rai/CzxvDicRRy4FhKcYI4oBaaOH4xJk8QWqH1UbhWdB+u7zrRUa039pBMYejR40ylLHEHV8xAKfb4okDfpxXT55s3Igo37Hro4HRKeNXN6usd2nlhAG5FplKBW2nLqsZbbAc3a8S7ADOEaRJYGeTMqProhoeAWbR2zC7nBtQSbxUD/4WBypV1+sJCxY+rNDYBNNyGLdK+8TVunLr4xvg5C65ypmkGoUI3ofLsnDz2N2gI88/17IELpkSeoUd1KI27rODdqGnFjfEJERIKk/scmbSJzNhZ3dxquFO0ci7lZx1jR6braRwZfWdNAI137T+2Th1M0A8aFKOcW3mZO6v/zaT9tcbe3dIjEuF7w6BaNMYMvLBaTqVB4IL03hhAMzNmKx7XpdR5EJ0jgxWmvLbvU+mUTg1heWd2kg==; 5:32n/+ce/3J7c/Xx8/dytvz0eUb3jYD2yXjKAouD4XSJO0WIzTVzmL5LgAieW6TS//ARpfz8EPKukekVC2S96L4gr8MNUm7k3nqolKFc3nOcpQyas87czXNEvNzOOtj1JEVC6UE3YrL/KxfOPW1iowdWorh/XVG0Pdw5/CTdfYg8=; 7:wez8uBYnDkBaM3Nf6TPunDUvSpecGdkWz1OC/6VIhLPyYmPiv1JCimz41yR/hgOtVJOrbQnFYQXLml7mmwrykLxBzXFAju5/84yFBaRQBePwkXgkOtwlWVazP1Pf8gxmn0+3kQ86zzo5RMcSNwykGZwxttNgSeVHNbuX1Evc14TWCAIeiXwM9oBjE/AXrd+qMj38r4zQqbMfT9y6cmfMuE5qcZl8J+2k1K5Z78223fWE8rWOlEYc62ouPKygE+nb x-ms-exchange-antispam-srfa-diagnostics: SOS;SOR; x-ms-office365-filtering-correlation-id: a1b43847-9bf8-401c-2b9e-08d62f3f75e1 x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: BCL:0; PCL:0; RULEID:(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600074)(711020)(4618075)(2017052603328)(7153060)(7193020); SRVR:AM6PR08MB3687; x-ms-traffictypediagnostic: AM6PR08MB3687: nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(228905959029699)(180628864354917); x-ms-exchange-senderadcheck: 1 x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(8121501046)(5005006)(3231355)(944501410)(52105095)(3002001)(10201501046)(93006095)(93001095)(6055026)(149066)(150057)(6041310)(20161123560045)(20161123564045)(20161123558120)(20161123562045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(201708071742011)(7699051)(76991055); SRVR:AM6PR08MB3687; BCL:0; PCL:0; RULEID:; SRVR:AM6PR08MB3687; x-forefront-prvs: 08220FA8D6 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(366004)(396003)(39860400002)(136003)(346002)(376002)(13464003)(189003)(199004)(55674003)(14454004)(486006)(14444005)(256004)(476003)(478600001)(446003)(106356001)(105586002)(33656002)(72206003)(71200400001)(71190400001)(97736004)(186003)(305945005)(74316002)(53936002)(9686003)(11346002)(7736002)(5660300001)(2900100001)(3846002)(6116002)(4326008)(2501003)(102836004)(6246003)(66066001)(5250100002)(6436002)(6346003)(26005)(25786009)(55016002)(110136005)(99286004)(54906003)(81156014)(81166006)(8676002)(8936002)(68736007)(6506007)(76176011)(7696005)(86362001)(53546011)(2906002)(316002)(229853002)(2201001)(21314002); DIR:OUT; SFP:1101; SCL:1; SRVR:AM6PR08MB3687; 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: CuiPZqbRfBH5NJSJo77J6Iv0cL7NSTakn9QKakXWafBUx86Xg9F1b/IYsro1yEImQ5GFUPLqx6WUvoEvB6IDCetYqpY47WxrhphtmLK7Nu5tidvj/jNegxvoO1Ge+2DbMgJ+39FH7LzNvYU1LeB7CUmR1ilI8intUTozFlLbdPkq0HKc+eHP6y/ONpn0areCBu+7tC8gw+m/XRamPKaZGCe/31Zan+vbt6DAit6Kss0mAVx1yb/mNkZMHuhMJfItPWmSFvvXGUAR7BbNK9CZTfL3LuRunbUjOBrDxBADaLsLsgGmD3rfm8EcGWebT2jb5TycdaNuKPwN6IU+q+8Rksn7cLkvefxLFEX5vBtrefQ= 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: a1b43847-9bf8-401c-2b9e-08d62f3f75e1 X-MS-Exchange-CrossTenant-originalarrivaltime: 11 Oct 2018 06:04:52.5390 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR08MB3687 Subject: Re: [dpdk-dev] [PATCH v2 0/7] 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: Thu, 11 Oct 2018 06:04:54 -0000 Hi Yipeng, I will rebase this further with your V7 and submit V3. Please let me know = if you have any comments in the meantime. Due to time constraints, I do not= plan to support lock-free for extended bucket feature in this release. I w= ill add that support in the next release. Please let me know if you have an= y concerns. Thank you, Honnappa > -----Original Message----- > From: Honnappa Nagarahalli > Sent: Wednesday, October 10, 2018 11:59 PM > To: bruce.richardson@intel.com; pablo.de.lara.guarch@intel.com > Cc: dev@dpdk.org; yipeng1.wang@intel.com; Honnappa Nagarahalli > ; Dharmik Thakkar > ; nd > Subject: [PATCH v2 0/7] Address reader-writer concurrency in rte_hash >=20 > 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 platfor= ms > 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) Add support to not free the key-store index upon calling > rte_hash_del_xxx APIs. This solves the issue in 2). >=20 > 2) Correct the alignment for the key store entry to prep for > memory ordering. >=20 > 3) Add memory ordering to prevent race conditions when a new key > is added to the table. >=20 > 4) 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 > 5) 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 when lock-free algorithm is enabled. > 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 > 6) Finally, a lock free reader-writer concurrency flag is added > to enable this feature at run time. >=20 > Performance numbers can be got from the additional test case added > as part of this patch. >=20 > v1->v2 > 1) Separate multi-writer capability from rw concurrency > 2) Add do not recycle on delete feature (Yipeng) > 3) Add Arm copyright > 4) Add test case to test lock-free algorithm and multi-writer > test case (Yipeng) > 5) Additional API documentation to indicate RCU usage (Yipeng) > 6) Additional documentation on rte_hash_reset API (Yipeng) > 7) Allocate memory for the global counter and avoid API > changes (Yipeng) >=20 > Dharmik Thakkar (1): > test/hash: read-write lock-free concurrency test >=20 > Honnappa Nagarahalli (6): > hash: separate multi-writer from rw-concurrency > hash: support do not recycle on delete > 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 >=20 > lib/librte_hash/rte_cuckoo_hash.c | 483 +++++++++++---- > lib/librte_hash/rte_cuckoo_hash.h | 17 +- > lib/librte_hash/rte_hash.h | 82 ++- > lib/librte_hash/rte_hash_version.map | 7 + > test/test/Makefile | 1 + > test/test/meson.build | 1 + > test/test/test_hash.c | 140 ++++- > test/test/test_hash_readwrite.c | 6 +- > test/test/test_hash_readwrite_lf.c | 1084 > ++++++++++++++++++++++++++++++++++ > 9 files changed, 1686 insertions(+), 135 deletions(-) create mode 10064= 4 > test/test/test_hash_readwrite_lf.c >=20 > -- > 2.7.4