From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR02-VE1-obe.outbound.protection.outlook.com (mail-eopbgr20067.outbound.protection.outlook.com [40.107.2.67]) by dpdk.org (Postfix) with ESMTP id B5596160 for ; Mon, 1 Oct 2018 00:21:01 +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=AG50JgrxutaKmRqswbRnv7/VSI5cRfLrk/8Vj2HXq84=; b=o+keDswFXEupNDkfzlt/PH2MbvBxWTRL82iM6SqC73KsxJ74DEr5oXcaBQIiM5ZAQBanD/zYWWDrfDgpIKeQmGLL2KSMbKr3SOo1wjLOF2zrOW68Iq4uf1bwjI2GoG3XqM2r1SaWLXNTNETviJVWu4CUaDPSXkzP51TCMIJg4AM= Received: from AM6PR08MB3672.eurprd08.prod.outlook.com (20.177.115.29) by AM6PR08MB3256.eurprd08.prod.outlook.com (52.135.164.149) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1185.24; Sun, 30 Sep 2018 22:21:00 +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; Sun, 30 Sep 2018 22:20:59 +0000 From: Honnappa Nagarahalli To: "Wang, Yipeng1" , "Richardson, Bruce" , "De Lara Guarch, Pablo" CC: "dev@dpdk.org" , "Gavin Hu (Arm Technology China)" , Steve Capper , Ola Liljedahl , nd Thread-Topic: [dpdk-dev] [PATCH 2/4] hash: add memory ordering to avoid race conditions Thread-Index: AQHUWQvdIBDpyOqaXE6tyONJmfJFcg== Date: Sun, 30 Sep 2018 22:20:59 +0000 Message-ID: References: <1536253938-192391-1-git-send-email-honnappa.nagarahalli@arm.com> <1536253938-192391-3-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; AM6PR08MB3256; 6:VH7YY/Uua991+3vfVeM5ZpN/LgEJeOJBb5macejVIN/NxBcupNyyRzUVOp708cbyxbs+t5/Bh4G0ekr4dhZPT7udLUP4mZOjTj+N3yaXNQASRdpnOi7d8V3CpH/+WOEJyc/Ai8gDk4OG71WVVr+BkiVnF8NGQ+bySZaEE5b+VDNorvlYR4Aqgq9SMplBzIAaaSyg7xl1booUp32Hd3Dzg76/tQwyX6IGYW6u0As4m1SnhIKT7cQ9x3zLGNYuf+jVIAA671OYaLhqkQuL4QS+02oiGSjwLTvPLPUFxt7oUMZEzxlBL1Z/U+ndG5sUJiRHdlO9/Mtiq5jjR3JhilEg7QvlXiMqIwfLD0lKlubqdXDYLrwW1tUe3vjGjKY4yJEuxkvkQzunfRw5EHPtq+6NrT6R7+mJV4NjbXtYtATOG5r/gnJ8HY/YtTrfR3wIdvfVqgLIG6RbYRhVw/42tyk0LA==; 5:uLEkZnQ4oj4UnfcoLiwZSwwzzeMs2okxBrsYgcN4hK8RCkoIYxuRZXWzh3yjRIr2Bt/R/odRsAJIv9sNJtdovTruT3NJoFqWvMITTQc182y1CrWmhsF+39/xAHqprCKNatPEPI6kZ4CiPxGH5Vsgcnu7stplNukXxWdZ/ys1LCs=; 7:FCtqVJ+wYxOLjPk3wKwH0hEFRbVK2se99B/81m0+U59lVGjckFteUuy11Fzz2kJbSgQMwaBzJK8fLgirc9a7bBowWguE1mSnvxhonGFUIEtG/C2eMjm+ogZyljCuEQRMdB3ehvLHHvL5rJZZkxv7E6W2MGqy1GOF1b3uTuUSd8A7kgpM2F2eyg3U7BtE1Bt4cWxFEOR3NXZ/csfsqiiY0xBL/SMpwFd6sqtyOWuEBSRlMRR4NPH79LLYRZhGtKoC x-ms-exchange-antispam-srfa-diagnostics: SOS;SOR; x-ms-office365-filtering-correlation-id: 150378a4-ef59-4188-d75d-08d62723001c 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:AM6PR08MB3256; x-ms-traffictypediagnostic: AM6PR08MB3256: nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(131327999870524); x-ms-exchange-senderadcheck: 1 x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(5005006)(8121501046)(3002001)(3231355)(944501410)(52105095)(10201501046)(93006095)(93001095)(6055026)(149066)(150057)(6041310)(20161123560045)(20161123564045)(20161123558120)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123562045)(201708071742011)(7699051); SRVR:AM6PR08MB3256; BCL:0; PCL:0; RULEID:; SRVR:AM6PR08MB3256; x-forefront-prvs: 08118EFC2B x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(39850400004)(396003)(346002)(376002)(136003)(366004)(13464003)(199004)(57704003)(189003)(4326008)(476003)(7736002)(74316002)(71200400001)(229853002)(102836004)(478600001)(72206003)(26005)(186003)(2900100001)(97736004)(81166006)(8936002)(54906003)(25786009)(53936002)(2906002)(256004)(71190400001)(110136005)(316002)(81156014)(14454004)(305945005)(14444005)(106356001)(76176011)(6116002)(105586002)(3846002)(486006)(66066001)(7696005)(6506007)(6436002)(5660300001)(9686003)(446003)(55016002)(68736007)(6246003)(5250100002)(34290500001)(11346002)(86362001)(33656002)(99286004); DIR:OUT; SFP:1101; SCL:1; SRVR:AM6PR08MB3256; 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: AyTOR9XszaWDSIvL0wtfdLxt68qK6180sYYIkzdD1wmDk3kY8b6XJC2dWM7bRjHSbqeb6sp47/Pbf3suirG9EiuwQT+avmXNL5zmnVgqSAilN5nOnks5wR6lXxF21lQux3Sb+LKHoCI4BGSzG3BrKbJXNvG0CeO2/jGjXjQpl9++wqlvSkhBWEikmfvHp3S4/fMFt8Iz+weTXRu5bigK2mMt0i/eK6mHZVI7k9OkK3Q5mx5RevJotQar7DP1DAsTraG9LKd9iXC5zJUmNQqNdXNoQ5dtsg4tKVvD3YNsNLkOGXEx2WYIiZ9AoxfyiW5q/tT+GUTDRirh5mls96gad7edkGEl03ypAe6f5o+UUzk= 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: 150378a4-ef59-4188-d75d-08d62723001c X-MS-Exchange-CrossTenant-originalarrivaltime: 30 Sep 2018 22:20:59.7638 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR08MB3256 Subject: Re: [dpdk-dev] [PATCH 2/4] hash: add memory ordering to avoid race conditions 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: Sun, 30 Sep 2018 22:21:02 -0000 >=20 > Some general comments for the various __atomic_store/load added, >=20 > 1. Although it passes the compiler check, but I just want to confirm that= if we > should use GCC/clang builtins, or if There are higher level APIs in DPDK = to do > atomic operations? >=20 I have used gcc builtins (just like rte_ring does) > 2. We believe compiler will translate the atomic_store/load to regular MO= V > instruction on Total Store Order architecture (e.g. X86_64). But we run t= he > perf test on x86 and here is the relative slowdown on lookup comparing to > master head. I am not sure if the performance drop comes from the atomic > buitins. >=20 C11 atomics also block compiler reordering. Other than this, the retry loop= is an addition to lookup. The patch also has the alignment corrected. I am not sure how is that affec= ting the perf numbers. > Keysize | single lookup | bulk lookup > 4 | 0.93 | 0.95 > 8 | 0.95 | 0.96 > 16 | 0.97 | 0.96 > 32 | 0.97 | 1.00 > 48 | 1.03 | 0.99 > 64 | 1.04 | 0.98 > 9 | 0.91 | 0.96 > 13 | 0.97 | 0.98 > 37 | 1.04 | 1.03 > 40 | 1.02 | 0.98 >=20 I assume this is the data from the test cases in test_hash_perf.c file. I t= ried to reproduce this data, but my data is worse. Can you specify the actu= al test from test_hash_perf.c you are using (With locks/Pre-computed hash/W= ith data/Elements in primary)? IMO, the differences you have provided are not high. > Other comments inlined. >=20 > >-----Original Message----- > >Only race condition that can occur is - using the key store element > >before the key write is completed. Hence, while inserting the element > >the release memory order is used. Any other race condition is caught by > >the key comparison. Memory orderings are added only where needed. > >For ex: reads in the writer's context do not need memory ordering as > >there is a single writer. > > > [Wang, Yipeng] I assume this commit works together with the next one to > enable read-write concurrency on relaxed memory ordering machine. This > commit by itself does not do that, right? > If this is the case, should we merge the two commits, or maybe just expla= in it > a little bit more in the commit message? This commit works only with the next commit. I kept it separated to make it= easy for review. I will merge it in the final patch. >=20 > >key_idx in the bucket entry and pdata in the key store element are used > >for synchronisation. key_idx is used to release an inserted entry in > >the bucket to the reader. Use of pdata for synchronisation is required > >due to updation of an existing entry where-in only the pdata is updated > >without updating key_idx. > > > > > >-/* Search a key from bucket and update its data */ > >+/* Search a key from bucket and update its data. > >+ * Writer holds the lock before calling this. > >+ */ > > static inline int32_t > > search_and_update(const struct rte_hash *h, void *data, const void *key= , > > struct rte_hash_bucket *bkt, hash_sig_t sig, hash_sig_t alt_hash) @@ > >-499,8 +501,13 @@ search_and_update(const struct rte_hash *h, void *data= , > const void *key, > > k =3D (struct rte_hash_key *) ((char *)keys + > > bkt->key_idx[i] * h->key_entry_size); > > if (rte_hash_cmp_eq(key, k->key, h) =3D=3D 0) { > >- /* Update data */ > >- k->pdata =3D data; > >+ /* 'pdata' acts as the synchronization point > >+ * when an existing hash entry is updated. > >+ * Key is not updated in this case. > >+ */ > [Wang, Yipeng] I did not quite understand why do we need synchronization > for hash data update. > Since pdata write is already atomic, the lookup will either read out the = stale > data or the new data, which should be fine without synchronization. > Is it to ensure the order of multiple reads in lookup threads? Yes, it is to ensure the order of reads in the lookup threads. There might = be reads in the application and we want to make sure they do not get reorde= red with this. >=20 > >@@ -1243,11 +1289,19 @@ __rte_hash_lookup_bulk(const struct rte_hash > *h, const void **keys, > > while (sec_hitmask[i]) { > > uint32_t hit_index =3D __builtin_ctzl(sec_hitmask[i]); > > > >- uint32_t key_idx =3D secondary_bkt[i]- > >key_idx[hit_index]; > >+ uint32_t key_idx =3D > >+ __atomic_load_n( > >+ &secondary_bkt[i]->key_idx[hit_index], > >+ __ATOMIC_ACQUIRE); > > const struct rte_hash_key *key_slot =3D > > (const struct rte_hash_key *)( > > (const char *)h->key_store + > > key_idx * h->key_entry_size); > >+ > >+ if (key_idx !=3D EMPTY_SLOT) > [Wang, Yipeng] I think even for current code, we need to check empty_slot= . > Could you export this as a bug fix commit? >=20 In the existing code, there is check 'if (!!key_idx & !rte_hash....)'. Are = you referring to '!!key_idx'? I think this should be changed to '(key_idx != =3D EMPTY_SLOT)'.