From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR01-VE1-obe.outbound.protection.outlook.com (mail-ve1eur01on0062.outbound.protection.outlook.com [104.47.1.62]) by dpdk.org (Postfix) with ESMTP id AA9314C99 for ; Tue, 2 Oct 2018 06:27:00 +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=WgWD8tbQBEtnvcyXtvMvlMcSzAlwZ+hXX/F3iTs5GYU=; b=H3xHHveXeLvNsxVfsuBX27ZoYt6G3KoquMS453bzeflliiU626JVDMeufQH0Zz9wXJNAGbaMM5t9JBiDcdXDWjBerplNjJdvGp0udh2/LveSBRNGUUar33OjLmzsI6pOa2b79evyKBy0DbQN6zu9HRZgn/pCc9hNZWTuvJ4eobI= Received: from AM6PR08MB3672.eurprd08.prod.outlook.com (20.177.115.29) by AM6PR08MB3557.eurprd08.prod.outlook.com (20.177.114.214) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1164.25; Tue, 2 Oct 2018 04:26:59 +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.024; Tue, 2 Oct 2018 04:26:59 +0000 From: Honnappa Nagarahalli To: "Wang, Yipeng1" , "Richardson, Bruce" CC: "Ananyev, Konstantin" , "dev@dpdk.org" , "Gobriel, Sameh" , nd , Honnappa Nagarahalli Thread-Topic: [PATCH v4 1/4] hash: fix race condition in iterate Thread-Index: AQHUV4tm+fMzDOJTHUePY/TAu0BeyKUK2QOwgABCpYCAAD8FUA== Date: Tue, 2 Oct 2018 04:26:59 +0000 Message-ID: References: <1537993618-92630-1-git-send-email-yipeng1.wang@intel.com> <1538155426-145177-1-git-send-email-yipeng1.wang@intel.com> <1538155426-145177-2-git-send-email-yipeng1.wang@intel.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.103.75] x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1; AM6PR08MB3557; 6:5pRLgnx0Np2NcMw93HdlXv/cU0liqt8edMqplBqvgt7KtvOwJvzTReHx5LKHQDOdjTEbyGP1IrUNQUV+y91d7a1gzcJcqxPZHcwx8mCkkuedY4IQfZPquc4CLCC77NiBve+x3BOEdp2xtZEqZN80zO1zkSDclrYULJYNTL14gDV6kFOQVtSBqh33KsCgrKU7lzZK2J8hcTefNvTYE+9UQiGGJsSTs9vvm9Qbca9fWi86C1+w7V1YHMM4qNyVHp7gErXHd+zgu4Smfy5qkCr8jG5ALMADrSStm2NOdO4n1KU2qh5Qqo3Dem6iZD0hLzxOiiibGfRbI83zGkEEkNw+OjExMgF6401li5VatRq3dfm0FnBRalCHlBQldt8OnwF1GFJ1CUID9TXgKfAyFjKjmjn73o3srxBDgzvcydQ9b9ntiteZrMgKJY4nXT3xCEy8HCJkEzbT1tMfrSufkft3bQ==; 5:wrXp/qjWx4jD/zPyzUstypzIniWrXxTy5Gm8C1BMzUnhUds5tzHCsaOCcU4fBlDMlxYzFddNLFZFsjLh65QavORnhhMNE33Z10qDg7lzjwxSdErRjrHBbsl+6o+lCczquLYWqN1qM86WXWRemHpZysZ39lblarJaQvKwJJ35VAE=; 7:TaI18oZWwGVX3QiC1gQS2JFC5YvX4VkPlxgIfL0nXQX/fY1rFoDV5kFxLAWk3ViAN/Ska8RD//7NiGqLGsX714jBNvqX+xZ/3TlPGIE7U6Sa9nGY2ikOmyHGFQTdnyDz+L5GU7P6oLTGfsrQu9g1nhHdfqeguDJ8uv/B0PyBFbeK3qkPYEWQp20xtCnujV5fm/JkaUjfwZ0KDrumNu8E1BbFOb8UJ/PuxKu8sLhu00Od+qoySmoYpH7h1WKeeV+F x-ms-exchange-antispam-srfa-diagnostics: SOS;SOR; x-ms-office365-filtering-correlation-id: e89df175-b67c-4e06-8247-08d6281f4b62 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:AM6PR08MB3557; x-ms-traffictypediagnostic: AM6PR08MB3557: nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(180628864354917); x-ms-exchange-senderadcheck: 1 x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(8121501046)(5005006)(93006095)(93001095)(10201501046)(3002001)(3231355)(944501410)(52105095)(6055026)(149066)(150057)(6041310)(20161123564045)(20161123560045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123558120)(20161123562045)(201708071742011)(7699051); SRVR:AM6PR08MB3557; BCL:0; PCL:0; RULEID:; SRVR:AM6PR08MB3557; x-forefront-prvs: 0813C68E65 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(366004)(39860400002)(346002)(376002)(396003)(136003)(199004)(189003)(57704003)(13464003)(7736002)(105586002)(316002)(14444005)(446003)(93886005)(476003)(33656002)(486006)(6246003)(2906002)(256004)(11346002)(14454004)(68736007)(478600001)(186003)(5660300001)(76176011)(102836004)(966005)(86362001)(2900100001)(3846002)(9686003)(71200400001)(99286004)(110136005)(54906003)(26005)(72206003)(7696005)(4326008)(97736004)(71190400001)(5250100002)(6306002)(229853002)(55016002)(66066001)(8676002)(81166006)(8936002)(81156014)(6436002)(53936002)(74316002)(6116002)(305945005)(25786009)(6506007)(106356001); DIR:OUT; SFP:1101; SCL:1; SRVR:AM6PR08MB3557; H:AM6PR08MB3672.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: gRqyMjguGIoDe87/4BGrxGFIQWnIrwZZl3z2lCbRGmiNcHDLYqV0sHKjE0/0cDmeZivpRV38wt7gAdG9M/OZ2X8KCN/bMe+04Z0G+RvEobiC8EJ7WF5OrBj4SLXlUjBpuT3nBIt5SePDDXTTw+oelEXQe1Rq9Vf728O5csvaLeqzzNFuFOjPJJFZws0v+yHbEAH9nvc4VmO+ZXZY/gMSPhZILrwOt/h4DFphbmtRnWI07DbhK+oH8sl/fY1nbt72gZwdPbU68kupe5Me0AVAXG7rljxv9fsja4tAo7B0rht9w3+LMJYaYocjEJhKrgePHHx05+QGmpizc3TiDCO0QtErxz9kZWCYQmQsM/pG+rU= 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: e89df175-b67c-4e06-8247-08d6281f4b62 X-MS-Exchange-CrossTenant-originalarrivaltime: 02 Oct 2018 04:26:59.2566 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR08MB3557 Subject: Re: [dpdk-dev] [PATCH v4 1/4] hash: fix race condition in iterate 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, 02 Oct 2018 04:27:00 -0000 >=20 > >-----Original Message----- > >From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com] > >> @@ -1317,16 +1317,19 @@ rte_hash_iterate(const struct rte_hash *h, > >> const void **key, void **data, uint32 > >> bucket_idx =3D *next / RTE_HASH_BUCKET_ENTRIES; > >> idx =3D *next % RTE_HASH_BUCKET_ENTRIES; > >> > >> + __hash_rw_reader_lock(h); > >This does not work well with the lock-less changes I am making. We > >should leave the lock in its original position. Instead change the while= loop as > follows: > > > >while ((position =3D h->buckets[bucket_idx].key_idx[idx]) =3D=3D EMPTY_S= LOT) > > > >> /* If current position is empty, go to the next one */ > >> while (h->buckets[bucket_idx].key_idx[idx] =3D=3D EMPTY_SLOT) { > >> (*next)++; > >> /* End of table */ > >> - if (*next =3D=3D total_entries) > >> + if (*next =3D=3D total_entries) { > >> + __hash_rw_reader_unlock(h); > >> return -ENOENT; > >> + } > >> bucket_idx =3D *next / RTE_HASH_BUCKET_ENTRIES; > >> idx =3D *next % RTE_HASH_BUCKET_ENTRIES; > >> } > >> - __hash_rw_reader_lock(h); > >> + > >> /* Get position of entry in key table */ > >> position =3D h->buckets[bucket_idx].key_idx[idx]; > >If we change the while loop as I suggested as above, we can remove this = line. > > > >> next_key =3D (struct rte_hash_key *) ((char *)h->key_store + >=20 > [Wang, Yipeng] Sorry that I did not realize you already have it in your p= atch > set and I agree. > Do you want to export it as a bug fix in your patch set? I will remove my > change. Sure, I will make a separate commit for this. >=20 > For the lock free, do we need to protect it with version counter? Imagine= the > following corner case: > While the iterator read the key and data, there is a writer deleted, remo= ved, > and recycled the key-data pair, and write a new key and data into it. Whi= le the > writer are writing, will the reader reads out wrong key/data, or mismatch= ed > key/data? >=20 In the lock-free algorithm, the key-data is not 'freed' until the readers h= ave completed all their references to the 'deleted' key-data. Hence, the wr= iters will not be able to allocate the same key store index till the reader= s have stopped referring to the 'deleted' key-data. I re-checked my ladder diagrams [1] and I could not find any issues. [1] https://dpdkuserspace2018.sched.com/event/G44w/lock-free-read-write-con= currency-in-rtehash (PPT)