From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR03-AM5-obe.outbound.protection.outlook.com (mail-eopbgr30050.outbound.protection.outlook.com [40.107.3.50]) by dpdk.org (Postfix) with ESMTP id BA3E95B12 for ; Tue, 10 Jul 2018 20:00:30 +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=lOFLbaliBPe9MUUjEljyu6ZYlUNvo4OLF6wQKkBuY4g=; b=WlGVXfShon4g9XKlqfFon+02WjfVQLMsYzrcZs13sI32+dWh4QxCyoerXLJwRQc6JehjAYfd6/WebpDG6TzGlAiX4mggeu9TEbRuti033k4tYEydtncx/IVvDqvUvM5oE4DUQwvRUbZJN7mIrk5nn7VcQPkaIEKAQpLFnBQ5z84= Received: from HE1PR0801MB1930.eurprd08.prod.outlook.com (10.168.94.136) by HE1PR0801MB1484.eurprd08.prod.outlook.com (10.167.190.138) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.930.20; Tue, 10 Jul 2018 18:00:27 +0000 Received: from HE1PR0801MB1930.eurprd08.prod.outlook.com ([fe80::a9b8:cd68:dca0:4798]) by HE1PR0801MB1930.eurprd08.prod.outlook.com ([fe80::a9b8:cd68:dca0:4798%3]) with mapi id 15.20.0930.022; Tue, 10 Jul 2018 18:00:27 +0000 From: Honnappa Nagarahalli To: Yipeng Wang , "pablo.de.lara.guarch@intel.com" CC: "dev@dpdk.org" , "bruce.richardson@intel.com" , "vguvva@caviumnetworks.com" , "brijesh.s.singh@gmail.com" , nd Thread-Topic: [PATCH v4 0/8] Add read-write concurrency to rte_hash library Thread-Index: AQHUF62YwhyVjzHFE0OvaR+WdSizdKSItMYA Date: Tue, 10 Jul 2018 18:00:27 +0000 Message-ID: References: <1528455078-328182-1-git-send-email-yipeng1.wang@intel.com> <1531133103-437316-1-git-send-email-yipeng1.wang@intel.com> In-Reply-To: <1531133103-437316-1-git-send-email-yipeng1.wang@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; HE1PR0801MB1484; 7:0Zn4UPHF8juJqCMCTIXLlquNuZXK8X6xDpkfyeNl3SkalDKXDPjB7bwY8R5ff3AVx3H6Tgt/2VmR0gEI8CAha56rpATVVb46PqmdfbYkGdfi98ZBmn/iF6oBKZWuSdEpr44ThZRyZQVfVl5z48Dqcyr4eJw4/sT6+nI8Io9W6aJ77XhnkOO+j4MXzwM9AZBMTGZYTcsCimeFgwdpbx1TPUUCidAr4s+NOl4/bljS3GyfJfYlW/bx+2P6f+jsZxRg x-ms-exchange-antispam-srfa-diagnostics: SOS; x-ms-office365-filtering-correlation-id: 75d4f80a-c552-4862-98d0-08d5e68f04b1 x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(7020095)(4652040)(8989117)(5600053)(711020)(4534165)(4627221)(201703031133081)(201702281549075)(8990107)(48565401081)(2017052603328)(7153060)(7193020); SRVR:HE1PR0801MB1484; x-ms-traffictypediagnostic: HE1PR0801MB1484: nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(180628864354917)(85827821059158)(228905959029699); x-ms-exchange-senderadcheck: 1 x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(5005006)(8121501046)(93006095)(93001095)(3002001)(3231311)(944501410)(52105095)(10201501046)(6055026)(149027)(150027)(6041310)(20161123558120)(20161123564045)(20161123562045)(20161123560045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(6072148)(201708071742011)(7699016); SRVR:HE1PR0801MB1484; BCL:0; PCL:0; RULEID:; SRVR:HE1PR0801MB1484; x-forefront-prvs: 0729050452 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(366004)(376002)(396003)(136003)(39860400002)(346002)(189003)(199004)(13464003)(229853002)(53546011)(3846002)(6116002)(14454004)(8936002)(81156014)(86362001)(33656002)(26005)(102836004)(76176011)(186003)(7696005)(97736004)(6506007)(68736007)(316002)(110136005)(54906003)(5660300001)(478600001)(8676002)(2501003)(99286004)(4326008)(2906002)(7736002)(81166006)(305945005)(9686003)(55016002)(25786009)(476003)(6246003)(486006)(39060400002)(6436002)(106356001)(11346002)(105586002)(66066001)(53936002)(14444005)(446003)(72206003)(2900100001)(5250100002)(74316002)(256004); DIR:OUT; SFP:1101; SCL:1; SRVR:HE1PR0801MB1484; H:HE1PR0801MB1930.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: zdIZ9qHdvs28X35TJd2XsbhJMac1T9r/Gyfu8hVM936vC7O23oEI8b03cG0ktM67gh4IROfp1H5ystIrUE7X9Kyaa19Pm11ucerygbSFcX7dIhsWDQWcizWbR8wqa4fPgIUtkfFXy4riYQ+6NC6PZaKwJwkIgKTS6dmP9CnpgxdGOUMaRZjtvhrMegDgsLBtRcMXVg71nqNj1E7YneZrIFCBZkq8oniOdsTDrIWxQnSiX0Ixrw8ulPZnQDdnr6v2/NIck8XIeqQ+iRwuGs/Mve7ao+Cy4DMZlUNvXDJGQYxFZ005ZaeVzA2Q6ypRMa1rbxWhNY/xIFlNoatoA8DX3G0K3M1ROWUJx7wX4K+ouvM= 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: 75d4f80a-c552-4862-98d0-08d5e68f04b1 X-MS-Exchange-CrossTenant-originalarrivaltime: 10 Jul 2018 18:00:27.4721 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: HE1PR0801MB1484 Subject: Re: [dpdk-dev] [PATCH v4 0/8] Add read-write concurrency to rte_hash library 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: Tue, 10 Jul 2018 18:00:31 -0000 Hi Yipeng/Pablo, Apologies for my delayed comments -----Original Message----- From: Yipeng Wang =20 Sent: Monday, July 9, 2018 5:45 AM To: pablo.de.lara.guarch@intel.com Cc: dev@dpdk.org; yipeng1.wang@intel.com; bruce.richardson@intel.com; Honna= ppa Nagarahalli ; vguvva@caviumnetworks.com; = brijesh.s.singh@gmail.com Subject: [PATCH v4 0/8] Add read-write concurrency to rte_hash library This patch set adds the read-write concurrency support in rte_hash. A new flag value is added to indicate if read-write concurrency is needed d= uring creation time. Test cases are implemented to do functional and perfor= mance tests. The new concurrency model is based on rte_rwlock. When Intel TSX is availab= le and the users indicate to use it, the TM version of the rte_rwlock will = be called. Both multi-writer and read-write concurrency are protected by th= e rte_rwlock instead of the x86 specific RTM instructions, so the x86 speci= fic header rte_cuckoo_hash_x86.h is removed and the code is infused into th= e main .c file. IMO, at a high-level, there are two use cases for the rte_hash library: 1) Writers are on control plane and data plane are readers 2) Writers and readers are on data plane This distinction is required as in the case of 1) writers are pre-emptible.= If I consider platforms without TSX (I do not know how Intel TSX works), t= he rte_rwlock implementation is blocking. A writer on the control plane can= take the lock and get pre-empted. Since rte_rwlock is used for read-write = concurrency, it will block the readers (on the data plane) for an extended = duration. I think, support for RCU is required to solve this issue. A new rte_hash_count API is proposed to count how many keys are inserted in= to the hash table. v3->v4: 1. Change commit message titles as Pablo suggested. (Pablo) 2. hash: remove= unnecessary changes in commit 4. (Pablo) 3. test: remove unnecessary doubl= e blank lines. (Pablo) 4. Add Pablo's ack in commit message. v2->v3: 1. hash: Concurrency bug fix: after beginning cuckoo path moving, the last = empty slot needs to be verified again in case other writers raced into this= slot and occupy it. A new commit is added to do this bug fix since it appl= ies to master head as well. 2. hash: Concurrency bug fix: if cuckoo path is detected to be invalid, the= current slot needs to be emptied since it is duplicated to its target buck= et. 3. hash: "const" is used for types in multiple locations. (Pablo) 4. hash: = rte_malloc used for readwriter lock used wrong align argument. Similar fix = applies to master head so a new commit is created. (Pablo) 5. hash: ring si= ze calculation fix is moved to front. (Pablo) 6. hash: search-and-remove fu= nction is refactored to be more aligned with other search function. (Pablo)= 7. test: using jhash in functional test for read-write concurrency. It is because jhash with sequential keys incur more cuckoo path. 8. Multiple coding style, typo, commit message fixes. (Pablo) v1->v2: 1. Split each commit into two commits for easier review (Pablo). 2. Add more comments in various places (Pablo). 3. hash: In key insertion function, move duplicated key checking to earlier= location and protect it using locks. Checking duplicated key should happen= first and data updates should be protected. 4. hash: In lookup bulk function, put signature comparison in lock, since w= riters could happen between signature match on two buckets. 5. hash: Add write locks to reset function as well to protect resets. 5. test: Fix 32-bit compilation error in read-write test (Pablo). 6. test: Check total physical core count in read-write test. Don't test wit= h thread count that larger than physical core count. 7. Other minor fixes such as typos (Pablo). Yipeng Wang (8): hash: fix multiwriter lock memory allocation hash: fix a multi-writer race condition hash: fix key slot size accuracy hash: make duplicated code into functions hash: add read and write concurrency support test: add tests in hash table perf test test: add test case for read write concurrency hash: add new API function to query the key count lib/librte_hash/meson.build | 1 - lib/librte_hash/rte_cuckoo_hash.c | 701 +++++++++++++++++++++---------= ---- lib/librte_hash/rte_cuckoo_hash.h | 18 +- lib/librte_hash/rte_cuckoo_hash_x86.h | 164 -------- lib/librte_hash/rte_hash.h | 14 + lib/librte_hash/rte_hash_version.map | 8 + test/test/Makefile | 1 + test/test/test_hash.c | 12 + test/test/test_hash_multiwriter.c | 9 + test/test/test_hash_perf.c | 36 +- test/test/test_hash_readwrite.c | 637 ++++++++++++++++++++++++++++++ 11 files changed, 1156 insertions(+), 445 deletions(-) delete mode 100644= lib/librte_hash/rte_cuckoo_hash_x86.h create mode 100644 test/test/test_hash_readwrite.c -- 2.7.4